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