dependencies.cpp

/* This file is part of the KDE project
   Copyright 2004 Tomas Mecir <mecirt@gmail.com>
 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
 
   You should have received a copy of the GNU Library General Public License
   along with this library; see the file COPYING.LIB.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
*/
 
 
#include "dependencies.h"
 
#include "formula.h"
 
#include "kspread_cell.h"
#include "kspread_sheet.h"
 
#include <tqmap.h>
 
//rows x cols in one cell-chunk; bigger values lead to slower updating
//of range-dependencies, lower values will increase memory usage
#define CELLCHUNK_ROWS 128
#define CELLCHUNK_COLS 16
 
namespace KSpread {
 
 
class DependencyList {
 public:
  DependencyList (Sheet *s);
  ~DependencyList () { reset (); };
  void reset ();
 
  void cellChanged (const Point &cell);
 
  void generateDependencies (const Point &cell);
  void generateDependencies (const Range &range);
  void generateDependencies (const RangeList &rangeList);
 
  void processDependencies (const Point &cell);
  void processDependencies (const Range &range);
  void processDependencies (const RangeList &rangeList);
 
  RangeList getDependencies (const Point &cell);
  TQValueList<Point> getDependants (const Point &cell);
 
  void areaModified (const TQString &name);
  protected:
  void addDependency (const Point &cell1, const Point &cell2);
  void addRangeDependency (const RangeDependency &rd);
  void removeDependencies (const Point &cell);
 
  void processRangeDependencies (const Point &cell);
 
  void processRangeDependencies (const Range &range);
 
  void updateCell (const Point &cell) const;
 
  Point leadingCell (const Point &cell) const;
  TQValueList<Point> leadingCells (const Range &range) const;
  RangeList computeDependencies (const Point &cell) const;
 
  TQValueList<Point> getCellDeps(const Point& cell) const {
      CellDepsMap::const_iterator it = cellDeps.find( cell );
      return it == cellDeps.end() ? TQValueList<Point>() : *it;
  }
 
  void dump();
 
  Sheet *sheet;
 
  TQMap<Point, RangeList> dependencies;
  typedef TQMap<Point, TQValueList<Point> > CellDepsMap;
  CellDepsMap cellDeps;
  TQMap<Point, TQValueList<RangeDependency> > rangeDeps;
  TQMap<TQString, TQMap<Point, bool> > areaDeps;
};
 
} // namespace KSpread
 
using namespace KSpread;
 
// This is currently not called - but it's really convenient to call it from
// gdb or from debug output to check that everything is set up ok.
void DependencyList::dump()
{
  TQMap<Point, RangeList>::const_iterator it = dependencies.begin();
  for ( ; it != dependencies.end(); ++it ) {
    Point p = it.key();
    kdDebug() << "Cell " << p.sheetName() << " " << p.pos()
              << " depends on :" << endl;
    RangeList rl = (*it);
    TQValueList<Point>::const_iterator itp = rl.cells.begin();
    for ( ; itp != rl.cells.end(); ++itp )
      kdDebug() << "  cell " << (*itp).pos() << endl;
    TQValueList<Range>::const_iterator itr = rl.ranges.begin();
    for ( ; itr != rl.ranges.end(); ++itr )
      kdDebug() << "  range " << (*itr).toString() << endl;
  }
 
  CellDepsMap::const_iterator cit = cellDeps.begin();
  for ( ; cit != cellDeps.end(); ++cit )
  {
    Point p = cit.key();
    kdDebug() << "The cells that depend on " << p.sheetName() << " " << p.pos()
              << " are :" << endl;
    TQValueList<Point>::const_iterator itp = (*cit).begin();
    for ( ; itp != (*cit).end(); ++itp )
      kdDebug() << "  cell " << (*itp).pos() << endl;
  }
 
}
 
DependencyManager::DependencyManager (Sheet *s)
{
  deps = new DependencyList (s);
}
 
DependencyManager::~DependencyManager ()
{
  delete deps;
  deps = 0;
}
 
void DependencyManager::reset ()
{
  deps->reset();
}
 
void DependencyManager::cellChanged (const Point &cell)
{
  deps->cellChanged (cell);
}
 
void DependencyManager::rangeChanged (const Range &range)
{
  deps->generateDependencies (range);
  deps->processDependencies (range);
}
 
void DependencyManager::rangeListChanged (const RangeList &rangeList)
{
  deps->generateDependencies (rangeList);
  deps->processDependencies (rangeList);
}
 
void DependencyManager::areaModified (const TQString &name)
{
  deps->areaModified (name);
}
 
RangeList DependencyManager::getDependencies (const Point &cell)
{
  return deps->getDependencies (cell);
}
 
TQValueList<Point> DependencyManager::getDependants (const Point &cell)
{
  return deps->getDependants (cell);
}
 
DependencyList::DependencyList (Sheet *s)
    : sheet (s)
{
}
 
void DependencyList::reset ()
{
  dependencies.clear();
  cellDeps.clear();
  rangeDeps.clear();
}
 
void DependencyList::cellChanged (const Point &cell)
{
  Cell *c = cell.cell();
 
  // empty or default cell? do nothing
  if( c->isDefault() )
    return;
 
  //if the cell contains the circle error, we mustn't do anything
  if (c->testFlag (Cell::Flag_CircularCalculation))
    return;
 
  //don't re-generate dependencies if we're updating dependencies
  if ( !(c->testFlag (Cell::Flag_Progress)))
    generateDependencies (cell);
 
  processDependencies (cell);
}
 
RangeList DependencyList::getDependencies (const Point &cell)
{
  RangeList rl;
  //look if the cell has any dependencies
  if (!dependencies.contains (cell))
    return rl;  //it doesn't - return an empty list
 
  //the cell does have dependencies - return them!
  return dependencies[cell];
}
 
TQValueList<Point> DependencyList::getDependants (const Point &cell)
{
  //cell dependencies go first
  TQValueList<Point> list = getCellDeps( cell );
  //next, append range dependencies
  Point leading = leadingCell (cell);
  TQValueList<RangeDependency>::iterator it;
  if (!rangeDeps.count (leading))
    return list;  //no range dependencies in this cell chunk -> nothing more to do
 
  for (it = rangeDeps[leading].begin();
      it != rangeDeps[leading].end(); ++it)
  {
    //process all range dependencies, and for each range including the questioned cell,
    //add the depending cell to the list
    if ((*it).range.contains (cell))
    {
      Point c;
      c.setRow ((*it).cellrow);
      c.setColumn ((*it).cellcolumn);
      c.setSheet ( (*it).cellsheet );
      list.push_back (c);
    }
  }
 
  return list;
}
 
void DependencyList::areaModified (const TQString &name)
{
  // since area names are something like aliases, modifying an area name
  // basically means that all cells referencing this area should be treated
  // as modified - that will retrieve updated area ranges and also update
  // everything as necessary ...
  if (!areaDeps.contains (name))
    return;
 
  TQMap<Point, bool>::iterator it;
  for (it = areaDeps[name].begin(); it != areaDeps[name].end(); ++it)
  {
    Cell *c = it.key().cell();
    // this forces the cell to regenerate everything - new range dependencies
    // and so on
    c->setValue (c->value ());
  }
}
 
void DependencyList::addDependency (const Point &cell1,
    const Point &cell2)
{
  //cell2 can be in another sheet (inter-sheet dependency)
  Sheet *sh = cell2.sheet();
  if (!sh)
    sh = sheet;
 
  dependencies[cell1].cells.push_back (cell2);
  sh->dependencies()->deps->cellDeps[cell2].push_back (cell1);
}
 
void DependencyList::addRangeDependency (const RangeDependency &rd)
{
  //target range can be in another sheet (inter-sheet dependency)
  Sheet *sh = rd.range.sheet();
  if (!sh)
    sh = sheet;
 
  Point cell;
  cell.setSheet (rd.cellsheet);
  cell.setRow (rd.cellrow);
  cell.setColumn (rd.cellcolumn);
  dependencies[cell].ranges.push_back (rd.range);
 
  TQValueList<Point> leadings = leadingCells (rd.range);
  TQValueList<Point>::iterator it;
  for (it = leadings.begin(); it != leadings.end(); ++it)
    sh->dependencies()->deps->rangeDeps[*it].push_back (rd);
 
  // the target range could be a named area ...
  if (!rd.range.namedArea().isNull())
    areaDeps[rd.range.namedArea()][cell] = true;
}
 
void DependencyList::removeDependencies (const Point &cell)
{
  //look if the cell has any dependencies
  if (!dependencies.contains (cell))
    return;  //it doesn't - nothing more to do
 
  //first we remove cell-dependencies
  TQValueList<Point> cells = dependencies[cell].cells;
  TQValueList<Point>::iterator it1;
  for (it1 = cells.begin(); it1 != cells.end(); ++it1)
  {
    //get sheet-pointer - needed to handle inter-sheet dependencies correctly
    Sheet *sh = (*it1).sheet();
    if (!sh)
      sh = sheet;
 
    if (!sh->dependencies()->deps->cellDeps.contains (*it1))
      continue;  //this should never happen
 
    //we no longer depend on this cell
    TQValueList<Point>::iterator cit;
    cit = sh->dependencies()->deps->cellDeps[*it1].find (cell);
    if (cit != sh->dependencies()->deps->cellDeps[*it1].end())
      sh->dependencies()->deps->cellDeps[*it1].erase (cit);
  }
 
  //then range-dependencies are removed
  TQValueList<Range> ranges = dependencies[cell].ranges;
  TQValueList<Range>::iterator it2;
  TQValueList<Point> leads;
  for (it2 = ranges.begin(); it2 != ranges.end(); ++it2)
  {
    //we construct a list of cell-chunks containing a range and merge it
    //with lists generated from all previous ranges (duplicates are removed)
    TQValueList<Point> leadings = leadingCells (*it2);
    for (it1 = leadings.begin(); it1 != leadings.end(); ++it1)
      if (!leads.contains (*it1))
        leads.push_back (*it1);
  }
  for (it1 = leads.begin(); it1 != leads.end(); ++it1)
  {
    //get sheet-pointer - needed to handle inter-sheet dependencies correctly
    Sheet *sh = (*it1).sheet();
    if (!sh)
      sh = sheet;
 
    if (sh->dependencies()->deps->rangeDeps.contains (*it1))
    {
      TQValueList<RangeDependency>::iterator it3;
      it3 = sh->dependencies()->deps->rangeDeps[*it1].begin();
      //erase all range dependencies of this cell in this cell-chunk
      while (it3 != sh->dependencies()->deps->rangeDeps[*it1].end())
        if (((*it3).cellrow == cell.row()) &&
            ((*it3).cellcolumn == cell.column()))
          it3 = sh->dependencies()->deps->rangeDeps[*it1].erase (it3);
        else
          ++it3;
      //erase the list if we no longer need it
      if (sh->dependencies()->deps->rangeDeps[*it1].empty())
        sh->dependencies()->deps->rangeDeps.erase (*it1);
    }
  }
 
  // remove information about named area dependencies
  TQMap<TQString, TQMap<Point, bool> >::iterator itr;
  for (itr = areaDeps.begin(); itr != areaDeps.end(); ++itr) {
    if (itr.data().contains (cell))
      itr.data().remove (cell);
  }
 
  // finally, remove the entry about this cell
  dependencies[cell].cells.clear();
  dependencies[cell].ranges.clear();
  dependencies.erase (cell);
}
 
void DependencyList::generateDependencies (const Point &cell)
{
  //get rid of old dependencies first
  removeDependencies (cell);
 
  //new dependencies only need to be generated if the cell contains a formula
  Cell *c = sheet->cellAt (cell.column(), cell.row());
  if( c->isDefault() )
    return;
  if (!c->isFormula())
    return;
 
  //now we need to generate dependencies
  RangeList rl = computeDependencies (cell);
 
  //now that we have the new dependencies, we put them into our data structures
  //and we're done
  TQValueList<Point>::iterator it1;
  TQValueList<Range>::iterator it2;
 
  for (it1 = rl.cells.begin(); it1 != rl.cells.end(); ++it1)
    addDependency (cell, *it1);
  for (it2 = rl.ranges.begin(); it2 != rl.ranges.end(); ++it2)
  {
    RangeDependency rd;
    rd.cellrow = cell.row();
    rd.cellcolumn = cell.column();
    rd.cellsheet = sheet;
    rd.range = *it2;
 
    if (rd.range.sheet() == 0)
        rd.range.setSheet(sheet);
 
    addRangeDependency (rd);
  }
}
 
void DependencyList::generateDependencies (const Range &range)
{
  for (int row = range.startRow(); row <= range.endRow(); row++)
    for (int col = range.startCol(); col <= range.endCol(); col++)
    {
      Point c;
      c.setRow (row);
      c.setColumn (col);
      c.setSheet(sheet);
      generateDependencies (c);
    }
}
 
void DependencyList::generateDependencies (const RangeList &rangeList)
{
  TQValueList<Point>::const_iterator it1;
  TQValueList<Range>::const_iterator it2;
 
  for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
    generateDependencies (*it1);
  for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
    generateDependencies (*it2);
}
 
void DependencyList::processDependencies (const Point &cell)
{
  const TQValueList<Point> d = getCellDeps(cell);
  TQValueList<Point>::const_iterator it = d.begin();
  const TQValueList<Point>::const_iterator end = d.end();
  for (; it != end; ++it)
      updateCell (*it);
 
  processRangeDependencies (cell);
}
 
void DependencyList::processRangeDependencies (const Point &cell)
{
  Point leading = leadingCell (cell);
  if (!rangeDeps.count (leading))
    return;  //no range dependencies in this cell chunk
 
  const TQValueList<RangeDependency> rd = rangeDeps[leading];
 
  TQValueList<RangeDependency>::const_iterator it;
  for (it = rd.begin(); it != rd.end(); ++it)
  {
    //process all range dependencies, and for each range including the modified cell,
    //recalc the depending cell
    if ((*it).range.contains (cell))
    {
      Point c;
      c.setRow ((*it).cellrow);
      c.setColumn ((*it).cellcolumn);
      c.setSheet ( (*it).cellsheet );
      updateCell (c);
    }
  }
}
 
void DependencyList::processDependencies (const Range &range)
{
  //each cell's dependencies need to be updated - that cannot be helped - having a range
  //only helps with range dependencies
  for (int row = range.startRow(); row <= range.endRow(); row++)
    for (int col = range.startCol(); col <= range.endCol(); col++)
    {
      Point c;
      c.setRow (row);
      c.setColumn (col);
      c.setSheet( sheet );
 
      const TQValueList<Point> d = getCellDeps(c);
      TQValueList<Point>::const_iterator it = d.begin();
      const TQValueList<Point>::const_iterator end = d.end();
      for (; it != end; ++it)
          updateCell (*it);
    }
 
  processRangeDependencies (range);
}
 
void DependencyList::processRangeDependencies (const Range &range)
{
  //TODO: some optimization, so that we don't recompute cells depending of huge
  //ranges more than once (now we recompute them once per cell-chunk used by their dependency)
  //This will probably happen as a part of splitting this into dep manager
  //and recalc manager
 
  TQValueList<Point> leadings = leadingCells (range);
  TQValueList<Point>::iterator it;
  for (it = leadings.begin(); it != leadings.end(); ++it)
  {
    if (!rangeDeps.count (*it))
      continue;  //no range dependencies in this cell chunk
    TQValueList<RangeDependency>::iterator it2;
    for (it2 = rangeDeps[*it].begin(); it2 != rangeDeps[*it].end(); ++it2)
    {
      //process all range dependencies, and for each range intersecting with our range,
      //recalc the depending cell
      if ((*it2).range.intersects (range))
      {
        Point c;
        c.setRow ((*it2).range.startRow());
        c.setColumn ((*it2).range.startCol());
        c.setSheet(sheet);
        updateCell (c);
      }
    }
  }
}
 
void DependencyList::processDependencies (const RangeList &rangeList)
{
  TQValueList<Point>::const_iterator it1;
  TQValueList<Range>::const_iterator it2;
 
  for (it1 = rangeList.cells.begin(); it1 != rangeList.cells.end(); ++it1)
    processDependencies (*it1);
  for (it2 = rangeList.ranges.begin(); it2 != rangeList.ranges.end(); ++it2)
    processDependencies (*it2);
}
 
void DependencyList::updateCell (const Point &cell) const
{
  Cell *c = cell.cell();
  //prevent infinite recursion (circular dependencies)
  if (c->testFlag (Cell::Flag_Progress) ||
      c->testFlag (Cell::Flag_CircularCalculation))
  {
    kdError(36001) << "ERROR: Circle, cell " << c->fullName() <<
        ", in dep.manager for sheet " << sheet->name() << endl;
    Value v;
    // don't set anything if the cell already has all these things set
    // this prevents endless loop for inter-sheet curcular dependencies,
    // where the usual mechanisms fail doe to having multiple dependency
    // managers ...
    if (!c->testFlag (Cell::Flag_CircularCalculation))
    {
      c->setFlag(Cell::Flag_CircularCalculation);
      v.setError ( "####" );
      c->setValue (v);
    }
    //clear the computing-dependencies flag
    c->clearFlag (Cell::Flag_Progress);
    return;
  }
  //set the computing-dependencies flag
  c->setFlag (Cell::Flag_Progress);
 
  //mark the cell as calc-dirty
  c->setCalcDirtyFlag();
 
  //recalculate the cell
  c->calc (false);
 
  //clear the computing-dependencies flag
  c->clearFlag (Cell::Flag_Progress);
}
 
Point DependencyList::leadingCell (const Point &cell) const
{
  Point c;
  c.setRow (cell.row() - cell.row() % CELLCHUNK_ROWS + 1);
  c.setColumn (cell.column() - cell.column() % CELLCHUNK_COLS + 1);
  c.setSheet(cell.sheet());
  return c;
}
 
TQValueList<Point> DependencyList::leadingCells (const Range &range) const
{
  TQValueList<Point> cells;
  Point cell1, cell2, cell;
 
  cell1.setRow (range.startRow());
  cell1.setColumn (range.startCol());
  cell2.setRow (range.endRow());
  cell2.setColumn (range.endCol());
  cell1.setSheet(range.sheet());
  cell2.setSheet(range.sheet());
 
  cell1 = leadingCell (cell1);
  cell2 = leadingCell (cell2);
  for (int row = cell1.row(); row <= cell2.row(); row += CELLCHUNK_ROWS)
    for (int col = cell1.column(); col <= cell2.column();
        col += CELLCHUNK_COLS)
    {
      cell.setRow (row);
      cell.setColumn (col);
      cell.setSheet(range.sheet());
      cells.push_back (cell);
    }
  return cells;
}
 
RangeList DependencyList::computeDependencies (const Point &cell) const
{
  Cell *c = cell.cell();
 
  // Not a formula -> no dependencies
  if (!c->isFormula())
    return RangeList();
 
  // Broken formula -> meaningless dependencies
  // (tries to avoid c->formula() being null)
  if (c->hasError())
    return RangeList();
 
  Formula* f = c->formula();
  Q_ASSERT(f);
  if (f==NULL)
  {
    kdDebug() << "Cell at row " << cell.row() << ", col " << cell.column() << " marked as formula, but formula is NULL" << endl;
    return RangeList();
  }
 
  Tokens tokens = f->tokens();
 
  //return empty list if the tokens aren't valid
  if (!tokens.valid())
    return RangeList();
 
  RangeList rl;
  for( unsigned i = 0; i < tokens.count(); i++ )
  {
    Token token = tokens[i];
    Token::Type tokenType = token.type();
 
    //parse each cell/range and put it to our RangeList
    if (tokenType == Token::Cell)
    {
      TQString text = token.text();
      Point cell (text, sheet->workbook(), sheet);
      if (cell.isValid())
        rl.cells.push_back (cell);
    }
    else if (tokenType == Token::Range)
    {
      TQString text = token.text();
      Range range (text, sheet->workbook(), sheet);
      if (range.isValid())
        rl.ranges.push_back (range);
    }
  }
 
  return rl;
}