1 files changed, 418 insertions, 0 deletions
diff --git a/src/libixion/dirty_cell_tracker.cpp b/src/libixion/dirty_cell_tracker.cpp
new file mode 100644
index 0000000..e5311bc
--- /dev/null
+++ b/src/libixion/dirty_cell_tracker.cpp
@@ -0,0 +1,418 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include "ixion/dirty_cell_tracker.hpp"
+#include "ixion/global.hpp"
+#include "ixion/formula_name_resolver.hpp"
+
+#include "depth_first_search.hpp"
+#include "debug.hpp"
+
+#include <mdds/rtree.hpp>
+#include <deque>
+#include <limits>
+
+namespace ixion {
+
+namespace {
+
+using rtree_type = mdds::rtree<rc_t, abs_range_set_t>;
+using rtree_array_type = std::deque<rtree_type>;
+
+} // anonymous namespace
+
+struct dirty_cell_tracker::impl
+{
+    rtree_array_type m_grids;
+    abs_range_set_t m_volatile_cells;
+
+    mutable std::unique_ptr<formula_name_resolver> m_resolver;
+
+    impl() {}
+
+    rtree_type& fetch_grid_or_resize(size_t n)
+    {
+        if (m_grids.size() <= n)
+            m_grids.resize(n+1);
+
+        return m_grids[n];
+    }
+
+    const rtree_type* fetch_grid(size_t n) const
+    {
+        return (n < m_grids.size()) ? &m_grids[n] : nullptr;
+    }
+
+    rtree_type* fetch_grid(size_t n)
+    {
+        return (n < m_grids.size()) ? &m_grids[n] : nullptr;
+    }
+
+    /**
+     * Given a modified cell range, return all ranges that are directly
+     * affected by it.
+     *
+     * @param range modified cell range.
+     *
+     * @return collection of ranges that are directly affected by the modified
+     *         cell range.
+     */
+    abs_range_set_t get_affected_cell_ranges(const abs_range_t& range) const
+    {
+        const rtree_type* grid = fetch_grid(range.first.sheet);
+        if (!grid)
+            return abs_range_set_t();
+
+        rtree_type::const_search_results res = grid->search(
+            {{range.first.row, range.first.column}, {range.last.row, range.last.column}},
+            rtree_type::search_type::overlap);
+
+        abs_range_set_t ranges;
+
+        for (const abs_range_set_t& range_set : res)
+            ranges.insert(range_set.begin(), range_set.end());
+
+        return ranges;
+    }
+
+    std::string print(const abs_range_t& range) const
+    {
+        if (!m_resolver)
+            m_resolver = formula_name_resolver::get(formula_name_resolver_t::excel_a1, nullptr);
+
+        abs_address_t origin(0, 0, 0);
+        range_t rrange = range;
+        rrange.set_absolute(false);
+
+        std::ostringstream os;
+        os << "Sheet" << (rrange.first.sheet+1) << '!';
+
+        if (rrange.first == rrange.last)
+            os << m_resolver->get_name(rrange.first, origin, false);
+        else
+            os << m_resolver->get_name(rrange, origin, false);
+
+        return os.str();
+    }
+};
+
+dirty_cell_tracker::dirty_cell_tracker() : mp_impl(std::make_unique<impl>()) {}
+dirty_cell_tracker::~dirty_cell_tracker() {}
+
+void dirty_cell_tracker::add(const abs_range_t& src, const abs_range_t& dest)
+{
+    if (!src.valid() || src.first.sheet != src.last.sheet)
+    {
+        // source range must be on one sheet.
+        std::ostringstream os;
+        os << "dirty_cell_tracker::add: invalid source range: src=" << src;
+        throw std::invalid_argument(os.str());
+    }
+
+    if (!dest.valid())
+    {
+        std::ostringstream os;
+        os << "dirty_cell_tracker::add: invalid destination range: src=" << src << "; dest=" << dest;
+        throw std::invalid_argument(os.str());
+    }
+
+    if (dest.all_columns() || dest.all_rows())
+    {
+        std::ostringstream os;
+        os << "dirty_cell_tracker::add: unset column or row range is not allowed " << dest;
+        throw std::invalid_argument(os.str());
+    }
+
+    for (sheet_t sheet = dest.first.sheet; sheet <= dest.last.sheet; ++sheet)
+    {
+        rtree_type& tree = mp_impl->fetch_grid_or_resize(sheet);
+
+        rtree_type::extent_type search_box(
+            {{dest.first.row, dest.first.column}, {dest.last.row, dest.last.column}});
+
+        rtree_type::search_results res = tree.search(search_box, rtree_type::search_type::match);
+
+        if (res.begin() == res.end())
+        {
+            // No listener for this destination range.  Insert a new one.
+            abs_range_set_t listener;
+            listener.emplace(src);
+            tree.insert(search_box, std::move(listener));
+        }
+        else
+        {
+            // A listener already exists for this destination cell.
+            abs_range_set_t& listener = *res.begin();
+            listener.emplace(src);
+        }
+    }
+}
+
+void dirty_cell_tracker::remove(const abs_range_t& src, const abs_range_t& dest)
+{
+    if (!src.valid() || src.first.sheet != src.last.sheet)
+    {
+        // source range must be on one sheet.
+        std::ostringstream os;
+        os << "dirty_cell_tracker::add: invalid source range: src=" << src;
+        throw std::invalid_argument(os.str());
+    }
+
+    if (!dest.valid())
+    {
+        std::ostringstream os;
+        os << "dirty_cell_tracker::remove: invalid destination range: src=" << src << "; dest=" << dest;
+        throw std::invalid_argument(os.str());
+    }
+
+    if (dest.all_columns() || dest.all_rows())
+    {
+        std::ostringstream os;
+        os << "dirty_cell_tracker::remove: unset column or row range is not allowed " << dest;
+        throw std::invalid_argument(os.str());
+    }
+
+    for (sheet_t sheet = dest.first.sheet; sheet <= dest.last.sheet; ++sheet)
+    {
+        rtree_type* tree = mp_impl->fetch_grid(sheet);
+        if (!tree)
+        {
+            IXION_DEBUG("Nothing is tracked on sheet " << sheet << ".");
+            continue;
+        }
+
+        rtree_type::extent_type search_box(
+            {{dest.first.row, dest.first.column}, {dest.last.row, dest.last.column}});
+
+        rtree_type::search_results res = tree->search(search_box, rtree_type::search_type::match);
+
+        if (res.begin() == res.end())
+        {
+            // No listener for this destination cell. Nothing to remove.
+            IXION_DEBUG(dest << " is not being tracked by anybody on sheet " << sheet << ".");
+            continue;
+        }
+
+        rtree_type::iterator it_listener = res.begin();
+        abs_range_set_t& listener = *it_listener;
+        size_t n_removed = listener.erase(src);
+
+        if (!n_removed)
+        {
+            IXION_DEBUG(src << " was not tracking " << dest << " on sheet " << sheet << ".");
+        }
+
+        if (listener.empty())
+            // Remove this from the R-tree.
+            tree->erase(it_listener);
+    }
+}
+
+void dirty_cell_tracker::add_volatile(const abs_range_t& pos)
+{
+    mp_impl->m_volatile_cells.insert(pos);
+}
+
+void dirty_cell_tracker::remove_volatile(const abs_range_t& pos)
+{
+    mp_impl->m_volatile_cells.erase(pos);
+}
+
+abs_range_set_t dirty_cell_tracker::query_dirty_cells(const abs_range_t& modified_cell) const
+{
+    abs_range_set_t mod_cells;
+    mod_cells.insert(modified_cell);
+    return query_dirty_cells(mod_cells);
+}
+
+abs_range_set_t dirty_cell_tracker::query_dirty_cells(const abs_range_set_t& modified_cells) const
+{
+    abs_range_set_t dirty_formula_cells;
+
+    // Volatile cells are in theory always formula cells and therefore always
+    // should be included.
+    dirty_formula_cells.insert(
+        mp_impl->m_volatile_cells.begin(), mp_impl->m_volatile_cells.end());
+
+    abs_range_set_t cur_modified_cells = modified_cells;
+    for (const abs_range_t& r : mp_impl->m_volatile_cells)
+        cur_modified_cells.insert(r);
+
+    while (!cur_modified_cells.empty())
+    {
+        abs_range_set_t next_modified_cells;
+
+        for (const abs_range_t& mc : cur_modified_cells)
+        {
+            abs_range_set_t affected_ranges = mp_impl->get_affected_cell_ranges(mc);
+            for (const abs_range_t& r : affected_ranges)
+            {
+                auto res = dirty_formula_cells.insert(r);
+                if (res.second)
+                    // This affected range has not yet been visited.  Put it
+                    // in the chain for the next round of checks.
+                    next_modified_cells.insert(r);
+            }
+        }
+
+        cur_modified_cells.swap(next_modified_cells);
+    }
+
+    return dirty_formula_cells;
+}
+
+std::vector<abs_range_t> dirty_cell_tracker::query_and_sort_dirty_cells(const abs_range_t& modified_cell) const
+{
+    abs_range_set_t mod_cells;
+    mod_cells.insert(modified_cell);
+    return query_and_sort_dirty_cells(mod_cells);
+}
+
+std::vector<abs_range_t> dirty_cell_tracker::query_and_sort_dirty_cells(
+    const abs_range_set_t& modified_cells, const abs_range_set_t* dirty_formula_cells) const
+{
+    abs_range_set_t cur_modified_cells = modified_cells;
+
+    abs_range_set_t final_dirty_formula_cells;
+
+    // Get the initial set of formula cells affected by the modified cells.
+    // Note that these modified cells are not dirty formula cells.
+    if (!cur_modified_cells.empty())
+    {
+        abs_range_set_t next_modified_cells;
+        for (const abs_range_t& mc : cur_modified_cells)
+        {
+            for (const abs_range_t& r : mp_impl->get_affected_cell_ranges(mc))
+            {
+                auto res = final_dirty_formula_cells.insert(r);
+                if (res.second)
+                    // This affected range has not yet been visited.  Put it
+                    // in the chain for the next round of checks.
+                    next_modified_cells.insert(r);
+            }
+        }
+
+        cur_modified_cells.swap(next_modified_cells);
+    }
+
+    // Because the modified cells in the subsequent rounds are all dirty
+    // formula cells, we need to track precedent-dependent relationships for
+    // later sorting.
+
+    cur_modified_cells.insert(mp_impl->m_volatile_cells.begin(), mp_impl->m_volatile_cells.end());
+
+    if (dirty_formula_cells)
+        cur_modified_cells.insert(dirty_formula_cells->begin(), dirty_formula_cells->end());
+
+    using dfs_type = depth_first_search<abs_range_t, abs_range_t::hash>;
+    dfs_type::relations rels;
+
+    while (!cur_modified_cells.empty())
+    {
+        abs_range_set_t next_modified_cells;
+        for (const abs_range_t& mc : cur_modified_cells)
+        {
+            for (const abs_range_t& r : mp_impl->get_affected_cell_ranges(mc))
+            {
+                // Record each precedent-dependent relationship (r =
+                // precedent; mc = dependent).
+                rels.insert(r, mc);
+
+                auto res = final_dirty_formula_cells.insert(r);
+                if (res.second)
+                    // This affected range has not yet been visited.  Put it
+                    // in the chain for the next round of checks.
+                    next_modified_cells.insert(r);
+            }
+        }
+
+        cur_modified_cells.swap(next_modified_cells);
+    }
+
+    // Volatile cells are always formula cells and therefore always should be
+    // included.
+    final_dirty_formula_cells.insert(
+        mp_impl->m_volatile_cells.begin(), mp_impl->m_volatile_cells.end());
+
+    if (dirty_formula_cells)
+    {
+        final_dirty_formula_cells.insert(
+            dirty_formula_cells->begin(), dirty_formula_cells->end());
+    }
+
+    // Perform topological sort on the dirty formula cell ranges.
+    std::vector<abs_range_t> retval;
+    dfs_type sorter(final_dirty_formula_cells.begin(), final_dirty_formula_cells.end(), rels, dfs_type::back_inserter(retval));
+    sorter.run();
+
+    return retval;
+}
+
+std::string dirty_cell_tracker::to_string() const
+{
+    auto resolver = formula_name_resolver::get(formula_name_resolver_t::excel_a1, nullptr);
+    const abs_address_t origin(0, 0, 0);
+
+    rc_t max_val = std::numeric_limits<rc_t>::max();
+    std::vector<std::string> lines;
+
+    for (rc_t i = 0, n = mp_impl->m_grids.size(); i < n; ++i)
+    {
+        const rtree_type& grid = mp_impl->m_grids[i];
+        rtree_type::const_search_results res =
+            grid.search({{0, 0}, {max_val, max_val}}, rtree_type::search_type::overlap);
+
+        for (auto it = res.cbegin(); it != res.cend(); ++it)
+        {
+            const rtree_type::extent_type& ext = it.extent();
+            const abs_range_set_t& srcs = *it;
+
+            range_t dest(
+                address_t(i, ext.start.d[0], ext.start.d[1]),
+                address_t(i, ext.end.d[0], ext.end.d[1]));
+
+            dest.set_absolute(false);
+
+            std::string dest_name = ext.is_point() ?
+                resolver->get_name(dest.first, origin, false) :
+                resolver->get_name(dest, origin, false);
+
+            for (const abs_range_t& src : srcs)
+            {
+                std::ostringstream os;
+                os << mp_impl->print(src);
+                os << " -> Sheet" << (dest.first.sheet+1) << '!' << dest_name;
+                lines.push_back(os.str());
+            }
+        }
+    }
+
+    if (lines.empty())
+        return std::string();
+
+    std::ostringstream os;
+    auto it = lines.begin();
+    os << *it;
+    for (++it; it != lines.end(); ++it)
+        os << std::endl << *it;
+    return os.str();
+}
+
+bool dirty_cell_tracker::empty() const
+{
+    for (const rtree_type& grid : mp_impl->m_grids)
+    {
+        if (!grid.empty())
+            return false;
+    }
+
+    return true;
+}
+
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */