1/* This file is part of the KDE project
2 Copyright 2010 Marijn Kruisselbrink <mkruisselbrink@kde.org>
3 Copyright 2006-2007 Stefan Nikolaus <stefan.nikolaus@kdemail.net>
4 Copyright 2004 Tomas Mecir <mecirt@gmail.com>
5
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Library General Public
8 License as published by the Free Software Foundation; either
9 version 2 of the License, or (at your option) any later version.
10
11 This library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Library General Public License for more details.
15
16 You should have received a copy of the GNU Library General Public License
17 along with this library; see the file COPYING.LIB. If not, write to
18 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.
20*/
21
22// Local
23#include "DependencyManager.h"
24#include "DependencyManager_p.h"
25
26#include "Cell.h"
27#include "CellStorage.h"
28#include "Formula.h"
29#include "FormulaStorage.h"
30#include "Map.h"
31#include "NamedAreaManager.h"
32#include "Region.h"
33#include "RTree.h"
34#include "Sheet.h"
35#include "Value.h"
36#include "DocBase.h"
37#include "ElapsedTime_p.h"
38
39#include <QHash>
40#include <QList>
41
42#include <KoUpdater.h>
43
44using namespace Calligra::Sheets;
45
46// This is currently not called - but it's really convenient to call it from
47// gdb or from debug output to check that everything is set up ok.
48void DependencyManager::Private::dump() const
49{
50 QMap<Cell, Region>::ConstIterator mend(providers.end());
51 for (QMap<Cell, Region>::ConstIterator mit(providers.begin()); mit != mend; ++mit) {
52 Cell cell = mit.key();
53
54 QStringList debugStr;
55 Region::ConstIterator rend((*mit).constEnd());
56 for (Region::ConstIterator rit((*mit).constBegin()); rit != rend; ++rit) {
57 debugStr << (*rit)->name();
58 }
59
60 kDebug(36002) << cell.name() << " consumes values of:" << debugStr.join(",");
61 }
62
63 foreach(Sheet* sheet, consumers.keys()) {
64 const QList< QPair<QRectF, Cell> > pairs = consumers[sheet]->intersectingPairs(QRect(1, 1, KS_colMax, KS_rowMax)).values();
65 QHash<QString, QString> table;
66 for (int i = 0; i < pairs.count(); ++i) {
67 Region tmpRange(pairs[i].first.toRect(), sheet);
68 table.insertMulti(tmpRange.name(), pairs[i].second.name());
69 }
70 foreach(const QString &uniqueKey, table.uniqueKeys()) {
71 QStringList debugStr(table.values(uniqueKey));
72 kDebug(36002) << uniqueKey << " provides values for:" << debugStr.join(",");
73 }
74 }
75
76 foreach(const Cell &cell, depths.keys()) {
77 QString cellName = cell.name();
78 while (cellName.count() < 4) cellName.prepend(' ');
79 kDebug(36002) << "depth(" << cellName << " ) =" << depths[cell];
80 }
81}
82
83DependencyManager::DependencyManager(const Map* map)
84 : d(new Private)
85{
86 d->map = map;
87}
88
89DependencyManager::~DependencyManager()
90{
91 qDeleteAll(d->consumers);
92 delete d;
93}
94
95void DependencyManager::reset()
96{
97 d->reset();
98}
99
100void DependencyManager::regionChanged(const Region& region)
101{
102 if (region.isEmpty())
103 return;
104 kDebug(36002) << "DependencyManager::regionChanged" << region.name();
105 Region::ConstIterator end(region.constEnd());
106 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
107 const QRect range = (*it)->rect();
108 const Sheet* sheet = (*it)->sheet();
109
110 for (int col = range.left(); col <= range.right(); ++col) {
111 for (int row = range.top(); row <= range.bottom(); ++row) {
112 Cell cell(sheet, col, row);
113 const Formula formula = cell.formula();
114
115 // remove it and all its consumers from the reference depth list
116 d->removeDepths(cell);
117
118 // cell without a formula? remove it
119 if (formula.expression().isEmpty()) {
120 d->removeDependencies(cell);
121 continue;
122 }
123
124 d->generateDependencies(cell, formula);
125 }
126 }
127 }
128 {
129 ElapsedTime et("Computing reference depths", ElapsedTime::PrintOnlyTime);
130 d->generateDepths(region);
131 }
132// d->dump();
133}
134
135void DependencyManager::namedAreaModified(const QString &name)
136{
137 d->namedAreaModified(name);
138}
139
140void DependencyManager::addSheet(Sheet *sheet)
141{
142 // Manages also the revival of a deleted sheet.
143 Q_UNUSED(sheet);
144#if 0 // TODO Stefan: Enable, if dependencies should not be tracked all the time.
145 ElapsedTime et("Generating dependencies", ElapsedTime::PrintOnlyTime);
146
147 // Clear orphaned dependencies (i.e. cells formerly containing formulas)
148 // FIXME Stefan: Iterate only over the consumers in sheet. Needs adjustment
149 // of the way the providers are stored. Now: only by cell.
150 // Future: QHash<Sheet*, QHash<Cell, Region> >
151 const QList<Cell> consumers = d->providers.keys();
152 foreach(const Cell& cell, consumers) {
153 if (cell.sheet() == sheet) {
154 // Those cells may had got providing regions. Clear them first.
155 // TODO
156
157 // Clear this cell as provider.
158 d->providers.remove(cell);
159 }
160 }
161
162 Cell cell;
163 for (int c = 0; c < sheet->formulaStorage()->count(); ++c) {
164 cell = Cell(sheet, sheet->formulaStorage()->col(c), sheet->formulaStorage()->row(c));
165
166 d->generateDependencies(cell, sheet->formulaStorage()->data(c));
167 if (!d->depths.contains(cell)) {
168 int depth = d->computeDepth(cell);
169 d->depths.insert(cell , depth);
170 }
171 }
172#endif
173}
174
175void DependencyManager::removeSheet(Sheet *sheet)
176{
177 Q_UNUSED(sheet);
178 // TODO Stefan: Implement, if dependencies should not be tracked all the time.
179}
180
181void DependencyManager::updateAllDependencies(const Map* map, KoUpdater *updater)
182{
183 ElapsedTime et("Generating dependencies", ElapsedTime::PrintOnlyTime);
184
185 // clear everything
186 d->providers.clear();
187 qDeleteAll(d->consumers);
188 d->consumers.clear();
189 d->namedAreaConsumers.clear();
190 d->depths.clear();
191
192 int cellsCount = 9;
193
194 if (updater) {
195 updater->setProgress(0);
196
197 foreach(const Sheet* sheet, map->sheetList())
198 cellsCount += sheet->formulaStorage()->count();
199 }
200
201 Cell cell;
202 int cellCurrent = 0;
203 foreach(const Sheet* sheet, map->sheetList()) {
204 for (int c = 0; c < sheet->formulaStorage()->count(); ++c, ++cellCurrent) {
205 cell = Cell(sheet, sheet->formulaStorage()->col(c), sheet->formulaStorage()->row(c));
206
207 d->generateDependencies(cell, sheet->formulaStorage()->data(c));
208 if (!sheet->formulaStorage()->data(c).isValid())
209 cell.setValue(Value::errorPARSE());
210
211 if (updater)
212 updater->setProgress(int(qreal(cellCurrent) / qreal(cellsCount) * 50.));
213 }
214 }
215 cellCurrent = 0;
216 foreach(const Sheet* sheet, map->sheetList()) {
217 for (int c = 0; c < sheet->formulaStorage()->count(); ++c, ++cellCurrent) {
218 cell = Cell(sheet, sheet->formulaStorage()->col(c), sheet->formulaStorage()->row(c));
219
220 if (!d->depths.contains(cell)) {
221 int depth = d->computeDepth(cell);
222 d->depths.insert(cell , depth);
223 }
224
225 if (updater)
226 updater->setProgress(50 + int(qreal(cellCurrent) / qreal(cellsCount) * 50.));
227 }
228 }
229
230 if (updater)
231 updater->setProgress(100);
232}
233
234QMap<Cell, int> DependencyManager::depths() const
235{
236 return d->depths;
237}
238
239Calligra::Sheets::Region DependencyManager::consumingRegion(const Cell& cell) const
240{
241 return d->consumingRegion(cell);
242}
243
244Calligra::Sheets::Region DependencyManager::reduceToProvidingRegion(const Region& region) const
245{
246 Region providingRegion;
247 QList< QPair<QRectF, Cell> > pairs;
248 Region::ConstIterator end(region.constEnd());
249 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
250 Sheet* const sheet = (*it)->sheet();
251 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = d->consumers.constFind(sheet);
252 if (cit == d->consumers.constEnd())
253 continue;
254
255 pairs = cit.value()->intersectingPairs((*it)->rect()).values();
256 for (int i = 0; i < pairs.count(); ++i)
257 providingRegion.add(pairs[i].first.toRect() & (*it)->rect(), sheet);
258 }
259 return providingRegion;
260}
261
262void DependencyManager::regionMoved(const Region& movedRegion, const Cell& destination)
263{
264 Region::Point locationOffset(destination.cellPosition() - movedRegion.boundingRect().topLeft());
265
266 Region::ConstIterator end(movedRegion.constEnd());
267 for (Region::ConstIterator it(movedRegion.constBegin()); it != end; ++it) {
268 Sheet* const sheet = (*it)->sheet();
269 locationOffset.setSheet((sheet == destination.sheet()) ? 0 : destination.sheet());
270
271 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = d->consumers.constFind(sheet);
272 if (cit == d->consumers.constEnd())
273 continue;
274
275 QList<Cell> dependentLocations = cit.value()->intersects((*it)->rect());
276 foreach(const Cell &c, dependentLocations) {
277 updateFormula(c, (*it), locationOffset);
278 }
279 }
280}
281
282void DependencyManager::updateFormula(const Cell& cell, const Region::Element* oldLocation, const Region::Point& offset)
283{
284 // Not a formula -> no dependencies
285 if (!cell.isFormula())
286 return;
287
288 const Formula formula = cell.formula();
289
290 // Broken formula -> meaningless dependencies
291 if (!formula.isValid())
292 return;
293
294 Tokens tokens = formula.tokens();
295
296 //return empty list if the tokens aren't valid
297 if (!tokens.valid())
298 return;
299
300 QString expression('=');
301 Sheet* sheet = cell.sheet();
302 foreach(const Token &token, tokens) {
303 //parse each cell/range and put it to our expression
304 if (token.type() == Token::Cell || token.type() == Token::Range) {
305 // FIXME Stefan: Special handling for named areas
306 const Region region(token.text(), sheet->map(), sheet);
307 //kDebug(36002) << region.name();
308
309 // the offset contains a sheet, only if it was an intersheet move.
310 if ((oldLocation->sheet() == region.firstSheet()) &&
311 (oldLocation->rect().contains(region.firstRange()))) {
312 const Region yetAnotherRegion(region.firstRange().translated(offset.pos()),
313 offset.sheet() ? offset.sheet() : sheet);
314 expression.append(yetAnotherRegion.name(sheet));
315 } else {
316 expression.append(token.text());
317 }
318 } else {
319 expression.append(token.text());
320 }
321 }
322 Cell(cell).parseUserInput(expression);
323}
324
325void DependencyManager::Private::reset()
326{
327 providers.clear();
328 consumers.clear();
329}
330
331Calligra::Sheets::Region DependencyManager::Private::consumingRegion(const Cell& cell) const
332{
333 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = consumers.constFind(cell.sheet());
334 if (cit == consumers.constEnd()) {
335 //kDebug(36002) << "No consumer tree found for the cell's sheet.";
336 return Region();
337 }
338
339 const QList<Cell> consumers = cit.value()->contains(cell.cellPosition());
340
341 Region region;
342 foreach(const Cell& c, consumers)
343 region.add(c.cellPosition(), c.sheet());
344 return region;
345}
346
347void DependencyManager::Private::namedAreaModified(const QString& name)
348{
349 // since area names are something like aliases, modifying an area name
350 // basically means that all cells referencing this area should be treated
351 // as modified - that will retrieve updated area ranges and also update
352 // everything as necessary ...
353 QHash<QString, QList<Cell> >::ConstIterator it = namedAreaConsumers.constFind(name);
354 if (it == namedAreaConsumers.constEnd())
355 return;
356
357 Region region;
358 const QList<Cell> namedAreaConsumersList = it.value();
359 foreach(const Cell &c, namedAreaConsumersList) {
360 generateDependencies(c, c.formula());
361 region.add(c.cellPosition(), c.sheet());
362 }
363 generateDepths(region);
364}
365
366void DependencyManager::Private::removeDependencies(const Cell& cell)
367{
368 // look if the cell has any providers
369 QMap<Cell, Region>::ConstIterator pit = providers.constFind(cell);
370 if (pit == providers.constEnd())
371 return; //it doesn't - nothing more to do
372
373 // first this cell is no longer a provider for all consumers
374 Region region = pit.value();
375 Region::ConstIterator end(region.constEnd());
376 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
377 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = consumers.constFind((*it)->sheet());
378 if (cit != consumers.constEnd()) {
379 cit.value()->remove((*it)->rect(), cell);
380 }
381 }
382
383 // remove information about named area dependencies
384 QHash<QString, QList<Cell> >::Iterator nit(namedAreaConsumers.begin()), nend(namedAreaConsumers.end());
385 while (nit != nend) {
386 nit.value().removeAll(cell);
387 if (nit.value().isEmpty())
388 nit = namedAreaConsumers.erase(nit);
389 else
390 ++nit;
391 }
392
393 // clear the circular dependency flags
394 removeCircularDependencyFlags(providers.value(cell), Backward);
395 removeCircularDependencyFlags(consumingRegion(cell), Forward);
396
397 // finally, remove the providers for this cell
398 providers.remove(cell);
399}
400
401void DependencyManager::Private::removeDepths(const Cell& cell)
402{
403 QMap<Cell, int>::Iterator dit = depths.find(cell);
404 if (dit == depths.end())
405 return;
406 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = consumers.constFind(cell.sheet());
407 if (cit == consumers.constEnd())
408 return;
409 depths.erase(dit);
410 const QList<Cell> consumers = cit.value()->contains(cell.cellPosition());
411 foreach(const Cell &c, consumers)
412 removeDepths(c);
413}
414
415void DependencyManager::Private::generateDependencies(const Cell& cell, const Formula& formula)
416{
417 //get rid of old dependencies first
418 removeDependencies(cell);
419
420 //new dependencies only need to be generated if the cell contains a formula
421// if (cell.isNull())
422// return;
423// if (!cell.isFormula())
424// return;
425
426 //now we need to generate the providing region
427 computeDependencies(cell, formula);
428}
429
430void DependencyManager::Private::generateDepths(const Region& region)
431{
432 QSet<Cell> computedDepths;
433
434 Region::ConstIterator end(region.constEnd());
435 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
436 const QRect range = (*it)->rect();
437 const Sheet* sheet = (*it)->sheet();
438 const CellStorage *cells = sheet->cellStorage();
439
440 int bottom = range.bottom();
441 if (bottom > cells->rows()) bottom = cells->rows();
442 int right = range.right();
443 if (right > cells->columns()) right = cells->columns();
444
445 for (int row = range.top(); row <= bottom; ++row) {
446 for (int col = range.left(); col <= right; ++col) {
447 Cell cell(sheet, col, row);
448 generateDepths(cell, computedDepths);
449 }
450 }
451 }
452}
453
454void DependencyManager::Private::generateDepths(Cell cell, QSet<Cell>& computedDepths)
455{
456 static QSet<Cell> processedCells;
457
458 //prevent infinite recursion (circular dependencies)
459 if (processedCells.contains(cell) || cell.value() == Value::errorCIRCLE()) {
460 kDebug(36002) << "Circular dependency at" << cell.fullName();
461 cell.setValue(Value::errorCIRCLE());
462 depths.insert(cell, 0);
463 return;
464 }
465 if (computedDepths.contains(cell)) {
466 return;
467 }
468
469 // set the compute reference depth flag
470 processedCells.insert(cell);
471
472 int depth = computeDepth(cell);
473 depths.insert(cell, depth);
474
475 computedDepths.insert(cell);
476
477 // Recursion. We need the whole dependency tree of the changed region.
478 // An infinite loop is prevented by the check above.
479 QHash<Sheet*, RTree<Cell>*>::ConstIterator cit = consumers.constFind(cell.sheet());
480 if (cit == consumers.constEnd()) {
481 processedCells.remove(cell);
482 return;
483 }
484 const QList<Cell> consumers = cit.value()->contains(cell.cellPosition());
485 foreach (const Cell &c, consumers) {
486 generateDepths(c, computedDepths);
487 }
488
489 // clear the compute reference depth flag
490 processedCells.remove(cell);
491}
492
493int DependencyManager::Private::computeDepth(Cell cell) const
494{
495 // a set of cell, which depth is currently calculated
496 static QSet<Cell> processedCells;
497
498 //prevent infinite recursion (circular dependencies)
499 if (processedCells.contains(cell) || cell.value() == Value::errorCIRCLE()) {
500 kDebug(36002) << "Circular dependency at" << cell.fullName();
501 cell.setValue(Value::errorCIRCLE());
502 return 0;
503 }
504
505 // set the compute reference depth flag
506 processedCells.insert(cell);
507
508 int depth = 0;
509
510 const Region region = providers.value(cell);
511
512 Region::ConstIterator end(region.constEnd());
513 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
514 const QRect range = (*it)->rect();
515 Sheet* sheet = (*it)->sheet();
516 const int right = range.right();
517 const int bottom = range.bottom();
518 for (int col = range.left(); col <= right; ++col) {
519 for (int row = range.top(); row <= bottom; ++row) {
520 Cell referencedCell = Cell(sheet, col, row);
521 if (!providers.contains(referencedCell)) {
522 // no further references
523 // depth is one at least
524 depth = qMax(depth, 1);
525 continue;
526 }
527
528 QMap<Cell, int>::ConstIterator it = depths.constFind(referencedCell);
529 if (it != depths.constEnd()) {
530 // the referenced cell depth was already computed
531 depth = qMax(it.value() + 1, depth);
532 continue;
533 }
534
535 // compute the depth of the referenced cell, add one and
536 // take it as new depth, if it's greater than the current one
537 depth = qMax(computeDepth(referencedCell) + 1, depth);
538 }
539 }
540 }
541
542 //clear the computing reference depth flag
543 processedCells.remove(cell);
544
545 return depth;
546}
547
548void DependencyManager::Private::computeDependencies(const Cell& cell, const Formula& formula)
549{
550 // Broken formula -> meaningless dependencies
551 if (!formula.isValid())
552 return;
553
554 const Tokens tokens = formula.tokens();
555
556 //return empty list if the tokens aren't valid
557 if (!tokens.valid())
558 return;
559
560 Sheet* sheet = cell.sheet();
561 int inAreasCall = 0;
562 Region providingRegion;
563 for (int i = 0; i < tokens.count(); i++) {
564 const Token &token = tokens[i];
565
566 if (inAreasCall) {
567 if (token.isOperator() && token.asOperator() == Token::LeftPar)
568 inAreasCall++;
569 else if (token.isOperator() && token.asOperator() == Token::RightPar)
570 inAreasCall--;
571 } else {
572 if (i > 0 && token.isOperator() && token.asOperator() == Token::LeftPar && tokens[i-1].isIdentifier() && QString::compare(tokens[i-1].text(), "AREAS", Qt::CaseInsensitive) == 0)
573 inAreasCall = 1;
574
575 //parse each cell/range and put it to our Region
576 if (token.type() == Token::Cell || token.type() == Token::Range) {
577 // check for named area
578 const bool isNamedArea = sheet->map()->namedAreaManager()->contains(token.text());
579 if (isNamedArea) {
580 // add cell as consumer of the named area
581 namedAreaConsumers[token.text()].append(cell);
582 }
583
584 // check if valid cell/range
585 Region region(token.text(), sheet->map(), sheet);
586 if (region.isValid()) {
587 if (isNamedArea) {
588 if ((i > 0 && tokens[i-1].isOperator()) || (i < tokens.count()-1 && tokens[i+1].isOperator())) {
589 // TODO: this check is not quite correct, to really properly determine if the entire range is referenced
590 // or just a single cell we would need to actually have the compile formula, not just the tokenized one
591 // basically this is the same logic as Formula::Private::valueOrElement
592
593 Region realRegion = region.intersectedWithRow(cell.row());
594 if (!realRegion.isEmpty()) {
595 region = realRegion;
596 }
597 }
598 }
599 // add it to the providers
600 providingRegion.add(region);
601
602 Sheet* sheet = region.firstSheet();
603
604 // create consumer tree, if not existing yet
605 QHash<Sheet*, RTree<Cell>*>::iterator it = consumers.find(sheet);
606 if (it == consumers.end()) {
607 it = consumers.insert(sheet, new RTree<Cell>());
608 }
609 // add cell as consumer of the range
610 it.value()->insert(region.firstRange(), cell);
611 }
612 }
613 }
614 }
615
616 // store the providing region
617 // NOTE Stefan: Also store cells without dependencies to avoid an
618 // iteration over all cells in a map/sheet on recalculation.
619 // empty region will be created automatically, if necessary
620 providers[cell].add(providingRegion);
621}
622
623void DependencyManager::Private::removeCircularDependencyFlags(const Region& region, Direction direction)
624{
625 // a set of cells, which circular dependency flag is currently removed
626 static QSet<Cell> processedCells;
627
628 Region::ConstIterator end(region.constEnd());
629 for (Region::ConstIterator it(region.constBegin()); it != end; ++it) {
630 const QRect range = (*it)->rect();
631 const Sheet* sheet = (*it)->sheet();
632 for (int col = range.left(); col <= range.right(); ++col) {
633 for (int row = range.top(); row <= range.bottom(); ++row) {
634 Cell cell(sheet, col, row);
635
636 if (processedCells.contains(cell))
637 continue;
638 processedCells.insert(cell);
639
640 if (cell.value() == Value::errorCIRCLE())
641 cell.setValue(Value::empty());
642
643 if (direction == Backward)
644 removeCircularDependencyFlags(providers.value(cell), Backward);
645 else // Forward
646 removeCircularDependencyFlags(consumingRegion(cell), Forward);
647
648 processedCells.remove(cell);
649 }
650 }
651 }
652}
653
654#include "DependencyManager.moc"
655