1 /*************************************************************************
2  *
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * Copyright 2000, 2010 Oracle and/or its affiliates.
6  *
7  * OpenOffice.org - a multi-platform office productivity suite
8  *
9  * This file is part of OpenOffice.org.
10  *
11  * OpenOffice.org is free software: you can redistribute it and/or modify
12  * it under the terms of the GNU Lesser General Public License version 3
13  * only, as published by the Free Software Foundation.
14  *
15  * OpenOffice.org is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU Lesser General Public License version 3 for more details
19  * (a copy is included in the LICENSE file that accompanied this code).
20  *
21  * You should have received a copy of the GNU Lesser General Public License
22  * version 3 along with OpenOffice.org.  If not, see
23  * <http://www.openoffice.org/license.html>
24  * for a copy of the LGPLv3 License.
25  *
26  ************************************************************************/
27 
28 // MARKER(update_precomp.py): autogen include statement, do not remove
29 #include "precompiled_sc.hxx"
30 
31 
32 #include "reftokenhelper.hxx"
33 #include "document.hxx"
34 #include "rangeutl.hxx"
35 #include "compiler.hxx"
36 #include "tokenarray.hxx"
37 
38 #include "rtl/ustring.hxx"
39 #include "formula/grammar.hxx"
40 #include "formula/token.hxx"
41 
42 using namespace formula;
43 
44 using ::std::vector;
45 using ::std::auto_ptr;
46 using ::rtl::OUString;
47 
48 void ScRefTokenHelper::compileRangeRepresentation(
49     vector<ScSharedTokenRef>& rRefTokens, const OUString& rRangeStr, ScDocument* pDoc, FormulaGrammar::Grammar eGrammar)
50 {
51     const sal_Unicode cSep = GetScCompilerNativeSymbol(ocSep).GetChar(0);
52     const sal_Unicode cQuote = '\'';
53 
54     // #i107275# ignore parentheses
55     OUString aRangeStr = rRangeStr;
56     while( (aRangeStr.getLength() >= 2) && (aRangeStr[ 0 ] == '(') && (aRangeStr[ aRangeStr.getLength() - 1 ] == ')') )
57         aRangeStr = aRangeStr.copy( 1, aRangeStr.getLength() - 2 );
58 
59     bool bFailure = false;
60     sal_Int32 nOffset = 0;
61     while (nOffset >= 0 && !bFailure)
62     {
63         OUString aToken;
64         ScRangeStringConverter::GetTokenByOffset(aToken, aRangeStr, nOffset, cSep, cQuote);
65         if (nOffset < 0)
66             break;
67 
68         ScCompiler aCompiler(pDoc, ScAddress(0,0,0));
69         aCompiler.SetGrammar(eGrammar);
70         auto_ptr<ScTokenArray> pArray(aCompiler.CompileString(aToken));
71 
72         // There MUST be exactly one reference per range token and nothing
73         // else, and it MUST be a valid reference, not some #REF!
74         sal_uInt16 nLen = pArray->GetLen();
75         if (!nLen)
76             continue;   // Should a missing range really be allowed?
77         if (nLen != 1)
78             bFailure = true;
79         else
80         {
81             pArray->Reset();
82             const FormulaToken* p = pArray->GetNextReference();
83             if (!p)
84                 bFailure = true;
85             else
86             {
87                 const ScToken* pT = static_cast<const ScToken*>(p);
88                 switch (pT->GetType())
89                 {
90                     case svSingleRef:
91                         if (!pT->GetSingleRef().Valid())
92                             bFailure = true;
93                         break;
94                     case svDoubleRef:
95                         if (!pT->GetDoubleRef().Valid())
96                             bFailure = true;
97                         break;
98                     case svExternalSingleRef:
99                         if (!pT->GetSingleRef().ValidExternal())
100                             bFailure = true;
101                         break;
102                     case svExternalDoubleRef:
103                         if (!pT->GetDoubleRef().ValidExternal())
104                             bFailure = true;
105                         break;
106                     default:
107                         ;
108                 }
109                 if (!bFailure)
110                     rRefTokens.push_back(
111                             ScSharedTokenRef(static_cast<ScToken*>(p->Clone())));
112             }
113         }
114 
115 #if 0
116         switch (p->GetType())
117         {
118             case svSingleRef:
119                 fprintf(stdout, "ScChart2DataProvider::compileRangeRepresentation:   single ref\n");
120             break;
121             case svDoubleRef:
122                 fprintf(stdout, "ScChart2DataProvider::compileRangeRepresentation:   double ref\n");
123             break;
124             case svExternalSingleRef:
125                 fprintf(stdout, "ScChart2DataProvider::compileRangeRepresentation:   external single ref\n");
126             break;
127             case svExternalDoubleRef:
128                 fprintf(stdout, "ScChart2DataProvider::compileRangeRepresentation:   external double ref\n");
129             break;
130             default:
131                 ;
132         }
133 #endif
134 
135     }
136     if (bFailure)
137         rRefTokens.clear();
138 }
139 
140 bool ScRefTokenHelper::getRangeFromToken(ScRange& rRange, const ScSharedTokenRef& pToken, bool bExternal)
141 {
142     StackVar eType = pToken->GetType();
143     switch (pToken->GetType())
144     {
145         case svSingleRef:
146         case svExternalSingleRef:
147         {
148             if ((eType == svExternalSingleRef && !bExternal) ||
149                 (eType == svSingleRef && bExternal))
150                 return false;
151 
152             const ScSingleRefData& rRefData = pToken->GetSingleRef();
153             rRange.aStart.SetCol(rRefData.nCol);
154             rRange.aStart.SetRow(rRefData.nRow);
155             rRange.aStart.SetTab(rRefData.nTab);
156             rRange.aEnd = rRange.aStart;
157             return true;
158         }
159         case svDoubleRef:
160         case svExternalDoubleRef:
161         {
162             if ((eType == svExternalDoubleRef && !bExternal) ||
163                 (eType == svDoubleRef && bExternal))
164                 return false;
165 
166             const ScComplexRefData& rRefData = pToken->GetDoubleRef();
167             rRange.aStart.SetCol(rRefData.Ref1.nCol);
168             rRange.aStart.SetRow(rRefData.Ref1.nRow);
169             rRange.aStart.SetTab(rRefData.Ref1.nTab);
170             rRange.aEnd.SetCol(rRefData.Ref2.nCol);
171             rRange.aEnd.SetRow(rRefData.Ref2.nRow);
172             rRange.aEnd.SetTab(rRefData.Ref2.nTab);
173             return true;
174         }
175         default:
176             ; // do nothing
177     }
178     return false;
179 }
180 
181 void ScRefTokenHelper::getRangeListFromTokens(ScRangeList& rRangeList, const vector<ScSharedTokenRef>& rTokens)
182 {
183     vector<ScSharedTokenRef>::const_iterator itr = rTokens.begin(), itrEnd = rTokens.end();
184     for (; itr != itrEnd; ++itr)
185     {
186         ScRange aRange;
187         getRangeFromToken(aRange, *itr);
188         rRangeList.Append(aRange);
189     }
190 }
191 
192 void ScRefTokenHelper::getTokenFromRange(ScSharedTokenRef& pToken, const ScRange& rRange)
193 {
194     ScComplexRefData aData;
195     aData.InitFlags();
196     aData.Ref1.nCol = rRange.aStart.Col();
197     aData.Ref1.nRow = rRange.aStart.Row();
198     aData.Ref1.nTab = rRange.aStart.Tab();
199     aData.Ref1.SetColRel(false);
200     aData.Ref1.SetRowRel(false);
201     aData.Ref1.SetTabRel(false);
202     aData.Ref1.SetFlag3D(true);
203 
204     aData.Ref2.nCol = rRange.aEnd.Col();
205     aData.Ref2.nRow = rRange.aEnd.Row();
206     aData.Ref2.nTab = rRange.aEnd.Tab();
207     aData.Ref2.SetColRel(false);
208     aData.Ref2.SetRowRel(false);
209     aData.Ref2.SetTabRel(false);
210     // Display sheet name on 2nd reference only when the 1st and 2nd refs are on
211     // different sheets.
212     aData.Ref2.SetFlag3D(aData.Ref1.nTab != aData.Ref2.nTab);
213 
214     pToken.reset(new ScDoubleRefToken(aData));
215 }
216 
217 void ScRefTokenHelper::getTokensFromRangeList(vector<ScSharedTokenRef>& pTokens, const ScRangeList& rRanges)
218 {
219     vector<ScSharedTokenRef> aTokens;
220     sal_uInt32 nCount = rRanges.Count();
221     aTokens.reserve(nCount);
222     for (sal_uInt32 i = 0; i < nCount; ++i)
223     {
224         ScRange* pRange = static_cast<ScRange*>(rRanges.GetObject(i));
225         if (!pRange)
226             // failed.
227             return;
228 
229         ScSharedTokenRef pToken;
230         ScRefTokenHelper::getTokenFromRange(pToken,* pRange);
231         aTokens.push_back(pToken);
232     }
233     pTokens.swap(aTokens);
234 }
235 
236 bool ScRefTokenHelper::isRef(const ScSharedTokenRef& pToken)
237 {
238     switch (pToken->GetType())
239     {
240         case svSingleRef:
241         case svDoubleRef:
242         case svExternalSingleRef:
243         case svExternalDoubleRef:
244             return true;
245         default:
246             ;
247     }
248     return false;
249 }
250 
251 bool ScRefTokenHelper::isExternalRef(const ScSharedTokenRef& pToken)
252 {
253     switch (pToken->GetType())
254     {
255         case svExternalSingleRef:
256         case svExternalDoubleRef:
257             return true;
258         default:
259             ;
260     }
261     return false;
262 }
263 
264 bool ScRefTokenHelper::intersects(const vector<ScSharedTokenRef>& rTokens, const ScSharedTokenRef& pToken)
265 {
266     if (!isRef(pToken))
267         return false;
268 
269     bool bExternal = isExternalRef(pToken);
270     sal_uInt16 nFileId = bExternal ? pToken->GetIndex() : 0;
271 
272     ScRange aRange;
273     getRangeFromToken(aRange, pToken, bExternal);
274 
275     vector<ScSharedTokenRef>::const_iterator itr = rTokens.begin(), itrEnd = rTokens.end();
276     for (; itr != itrEnd; ++itr)
277     {
278         const ScSharedTokenRef& p = *itr;
279         if (!isRef(p))
280             continue;
281 
282         if (bExternal != isExternalRef(p))
283             continue;
284 
285         ScRange aRange2;
286         getRangeFromToken(aRange2, p, bExternal);
287 
288         if (bExternal && nFileId != p->GetIndex())
289             // different external file
290             continue;
291 
292         if (aRange.Intersects(aRange2))
293             return true;
294     }
295     return false;
296 }
297 
298 namespace {
299 
300 class JoinRefTokenRanges
301 {
302 public:
303     /**
304      * Insert a new reference token into the existing list of reference tokens,
305      * but in that process, try to join as many adjacent ranges as possible.
306      *
307      * @param rTokens existing list of reference tokens
308      * @param rToken new token
309      */
310     void operator() (vector<ScSharedTokenRef>& rTokens, const ScSharedTokenRef& pToken)
311     {
312         join(rTokens, pToken);
313     }
314 
315 private:
316 
317     /**
318      * Check two 1-dimensional ranges to see if they overlap each other.
319      *
320      * @param nMin1 min value of range 1
321      * @param nMax1 max value of range 1
322      * @param nMin2 min value of range 2
323      * @param nMax2 max value of range 2
324      * @param rNewMin min value of new range in case they overlap
325      * @param rNewMax max value of new range in case they overlap
326      */
327     template<typename T>
328     static bool overlaps(T nMin1, T nMax1, T nMin2, T nMax2, T& rNewMin, T& rNewMax)
329     {
330         bool bDisjoint1 = (nMin1 > nMax2) && (nMin1 - nMax2 > 1);
331         bool bDisjoint2  = (nMin2 > nMax1) && (nMin2 - nMax1 > 1);
332         if (bDisjoint1 || bDisjoint2)
333             // These two ranges cannot be joined.  Move on.
334             return false;
335 
336         T nMin = nMin1 < nMin2 ? nMin1 : nMin2;
337         T nMax = nMax1 > nMax2 ? nMax1 : nMax2;
338 
339         rNewMin = nMin;
340         rNewMax = nMax;
341 
342         return true;
343     }
344 
345     bool isContained(const ScComplexRefData& aOldData, const ScComplexRefData& aData) const
346     {
347         // Check for containment.
348         bool bRowsContained = (aOldData.Ref1.nRow <= aData.Ref1.nRow) && (aData.Ref2.nRow <= aOldData.Ref2.nRow);
349         bool bColsContained = (aOldData.Ref1.nCol <= aData.Ref1.nCol) && (aData.Ref2.nCol <= aOldData.Ref2.nCol);
350         return (bRowsContained && bColsContained);
351     }
352 
353     void join(vector<ScSharedTokenRef>& rTokens, const ScSharedTokenRef& pToken)
354     {
355         // Normalize the token to a double reference.
356         ScComplexRefData aData;
357         if (!ScRefTokenHelper::getDoubleRefDataFromToken(aData, pToken))
358             return;
359 
360         // Get the information of the new token.
361         bool bExternal = ScRefTokenHelper::isExternalRef(pToken);
362         sal_uInt16 nFileId = bExternal ? pToken->GetIndex() : 0;
363         String aTabName = bExternal ? pToken->GetString() : String();
364 
365         bool bJoined = false;
366         vector<ScSharedTokenRef>::iterator itr = rTokens.begin(), itrEnd = rTokens.end();
367         for (; itr != itrEnd; ++itr)
368         {
369             ScSharedTokenRef& pOldToken = *itr;
370 
371             if (!ScRefTokenHelper::isRef(pOldToken))
372                 // A non-ref token should not have been added here in the first
373                 // place!
374                 continue;
375 
376             if (bExternal != ScRefTokenHelper::isExternalRef(pOldToken))
377                 // External and internal refs don't mix.
378                 continue;
379 
380             if (bExternal)
381             {
382                 if (nFileId != pOldToken->GetIndex())
383                     // Different external files.
384                     continue;
385 
386                 if (aTabName != pOldToken->GetString())
387                     // Different table names.
388                     continue;
389             }
390 
391             ScComplexRefData aOldData;
392             if (!ScRefTokenHelper::getDoubleRefDataFromToken(aOldData, pOldToken))
393                 continue;
394 
395             if (aData.Ref1.nTab != aOldData.Ref1.nTab || aData.Ref2.nTab != aOldData.Ref2.nTab)
396                 // Sheet ranges differ.
397                 continue;
398 
399             if (isContained(aOldData, aData))
400                 // This new range is part of an existing range.  Skip it.
401                 return;
402 
403             bool bSameRows = (aData.Ref1.nRow == aOldData.Ref1.nRow) && (aData.Ref2.nRow == aOldData.Ref2.nRow);
404             bool bSameCols = (aData.Ref1.nCol == aOldData.Ref1.nCol) && (aData.Ref2.nCol == aOldData.Ref2.nCol);
405             ScComplexRefData aNewData = aOldData;
406             bool bJoinRanges = false;
407             if (bSameRows)
408             {
409                 bJoinRanges = overlaps(
410                     aData.Ref1.nCol, aData.Ref2.nCol, aOldData.Ref1.nCol, aOldData.Ref2.nCol,
411                     aNewData.Ref1.nCol, aNewData.Ref2.nCol);
412             }
413             else if (bSameCols)
414             {
415                 bJoinRanges = overlaps(
416                     aData.Ref1.nRow, aData.Ref2.nRow, aOldData.Ref1.nRow, aOldData.Ref2.nRow,
417                     aNewData.Ref1.nRow, aNewData.Ref2.nRow);
418             }
419 
420             if (bJoinRanges)
421             {
422                 if (bExternal)
423                     pOldToken.reset(new ScExternalDoubleRefToken(nFileId, aTabName, aNewData));
424                 else
425                     pOldToken.reset(new ScDoubleRefToken(aNewData));
426 
427                 bJoined = true;
428                 break;
429             }
430         }
431 
432         if (bJoined)
433         {
434             if (rTokens.size() == 1)
435                 // There is only one left.  No need to do more joining.
436                 return;
437 
438             // Pop the last token from the list, and keep joining recursively.
439             ScSharedTokenRef p = rTokens.back();
440             rTokens.pop_back();
441             join(rTokens, p);
442         }
443         else
444             rTokens.push_back(pToken);
445     }
446 };
447 
448 }
449 
450 void ScRefTokenHelper::join(vector<ScSharedTokenRef>& rTokens, const ScSharedTokenRef& pToken)
451 {
452     JoinRefTokenRanges join;
453     join(rTokens, pToken);
454 }
455 
456 bool ScRefTokenHelper::getDoubleRefDataFromToken(ScComplexRefData& rData, const ScSharedTokenRef& pToken)
457 {
458     switch (pToken->GetType())
459     {
460         case svSingleRef:
461         case svExternalSingleRef:
462         {
463             const ScSingleRefData& r = pToken->GetSingleRef();
464             rData.Ref1 = r;
465             rData.Ref1.SetFlag3D(true);
466             rData.Ref2 = r;
467             rData.Ref2.SetFlag3D(false); // Don't display sheet name on second reference.
468         }
469         break;
470         case svDoubleRef:
471         case svExternalDoubleRef:
472             rData = pToken->GetDoubleRef();
473         break;
474         default:
475             // Not a reference token.  Bail out.
476             return false;
477     }
478     return true;
479 }
480