Add initial (and probably buggy) compute_modifications code

compute_modifications compiles a list of buffer change into
a list of Modifications that can be used for updating BufferCoord

4 files changed, 305 insertions, 5 deletions

diff --git a/src/modification.cc b/src/modification.cc
new file mode 100644
index 00000000..b5e91c1f
--- /dev/null
+++ b/src/modification.cc
@@ -0,0 +1,128 @@
+#include "modification.hh"
+
+#include "buffer.hh"
+
+namespace Kakoune
+{
+
+namespace
+{
+
+ByteCount change_added_column(const Buffer::Change& change)
+{
+    kak_assert(change.type == Buffer::Change::Insert);
+    if (change.begin.line == change.end.line)
+        return change.end.column - change.begin.column;
+    else
+        return change.end.column;
+}
+
+}
+
+std::vector<Modification> compute_modifications(memoryview<Buffer::Change> changes)
+{
+    std::vector<Modification> res;
+    for (auto& change : changes)
+    {
+        auto pos = std::upper_bound(res.begin(), res.end(), change.begin,
+                                    [](const ByteCoord& l, const Modification& c)
+                                    { return l < c.new_coord; });
+
+        if (pos != res.begin())
+        {
+            auto& prev = *(pos-1);
+            if (change.begin <= prev.added_end())
+                --pos;
+            else
+                pos = res.insert(pos, {prev.get_old_coord(change.begin), change.begin, {}, {}});
+        }
+        else
+            pos = res.insert(pos, {change.begin, change.begin, {}, {}});
+
+        auto& modif = *pos;
+        auto next = pos + 1;
+        if (change.type == Buffer::Change::Insert)
+        {
+            const LineCount last_line = modif.new_coord.line + modif.num_added.line;
+
+            ByteCoord num_added = { change.end.line - change.begin.line, 0 };
+
+            modif.num_added.line += num_added.line;
+
+            if (change.begin.line == last_line)
+            {
+                if (change.end.line == change.begin.line)
+                    num_added.column = change.end.column - change.begin.column;
+                else
+                    num_added.column = change.end.column - modif.num_added.column;
+
+                modif.num_added.column += num_added.column;
+                kak_assert(modif.num_added.column >= 0);
+            }
+
+            for (auto it = next; it != res.end(); ++it)
+            {
+                if (it->new_coord.line == change.begin.line and it->num_added.line == 0)
+                    it->new_coord.column += num_added.column;
+
+                it->new_coord.line += num_added.line;
+            }
+        }
+        else
+        {
+            ByteCoord num_removed = { change.end.line - change.begin.line, 0 };
+            if (num_removed.line != 0)
+                num_removed.column = change.end.column;
+            else
+                num_removed.column = change.end.column - change.begin.column;
+
+            auto delend = std::upper_bound(next, res.end(), change.end,
+                                           [](const ByteCoord& l, const Modification& c)
+                                           { return l < c.new_coord; });
+
+            for (auto it = next; it != delend; ++it)
+            {
+                {
+                    LineCount removed_from_it = (change.begin.line + num_removed.line - it->new_coord.line);
+                    modif.num_removed.line += it->num_removed.line - std::min(removed_from_it, it->num_added.line);
+                    modif.num_added.line += std::max(0_line, it->num_added.line - removed_from_it);
+                }
+
+                if (it->new_coord.line == change.end.line)
+                {
+                    ByteCount removed_from_it = num_removed.column - it->new_coord.column;
+                    modif.num_removed.column += it->num_removed.column - std::min(removed_from_it, it->num_added.column);
+                    modif.num_added.column += std::max(0_byte, it->num_added.column - removed_from_it);
+                }
+            }
+            next = res.erase(next, delend);
+
+            ByteCoord num_added_after_pos = { modif.new_coord.line + modif.num_added.line - change.begin.line, 0 };
+            if (change.begin.line == modif.new_coord.line + modif.num_added.line)
+            {
+                if (modif.num_added.line == 0)
+                    num_added_after_pos.column = modif.new_coord.column + modif.num_added.column - change.begin.column;
+                else
+                    num_added_after_pos.column = modif.num_added.column - change.begin.column;
+            }
+            ByteCoord num_removed_from_added = std::min(num_removed, num_added_after_pos);
+            modif.num_added -= num_removed_from_added;
+            modif.num_removed += num_removed - num_removed_from_added;
+
+            for (auto it = next; it != res.end(); ++it)
+            {
+                if (it->new_coord.line == change.end.line and it->num_added.line == 0)
+                    it->new_coord.column -= num_removed.column;
+                it->new_coord.line -= num_removed.line;
+            }
+        }
+    }
+    return res;
+}
+
+std::vector<Modification> compute_modifications(const Buffer& buffer, size_t timestamp)
+{
+    return compute_modifications(buffer.changes_since(timestamp));
+}
+
+}
diff --git a/src/modification.hh b/src/modification.hh
new file mode 100644
index 00000000..103a7520
--- /dev/null
+++ b/src/modification.hh
@@ -0,0 +1,88 @@
+#ifndef modification_hh_INCLUDED
+#define modification_hh_INCLUDED
+
+#include "coord.hh"
+#include "utils.hh"
+#include "buffer.hh"
+
+namespace Kakoune
+{
+
+struct Modification
+{
+    ByteCoord old_coord;
+    ByteCoord new_coord;
+    ByteCoord num_removed;
+    ByteCoord num_added;
+
+    ByteCoord added_end() const
+    {
+        if (num_added.line)
+            return { new_coord.line + num_added.line, num_added.column };
+        else
+            return { new_coord.line, new_coord.column + num_added.column };
+    }
+
+    ByteCoord get_old_coord(ByteCoord coord) const
+    {
+        if (coord.line == new_coord.line)
+        {
+            if (num_added.line == 0)
+                coord.column -= new_coord.column - old_coord.column + num_added.column - num_removed.column;
+            else
+                coord.column -= num_added.column - num_removed.column;
+        }
+        coord.line -= new_coord.line - old_coord.line + num_added.line - num_removed.line;
+        return coord;
+    }
+
+    ByteCoord get_new_coord(ByteCoord coord, bool& deleted) const
+    {
+        deleted = false;
+        if (coord < old_coord)
+            return coord;
+
+        // apply remove
+        if (coord.line < old_coord.line + num_removed.line or
+            (coord.line == old_coord.line + num_removed.line and
+             coord.column < old_coord.column + num_removed.column))
+        {
+            deleted = true;
+            coord = old_coord;
+        }
+        else if (coord.line == old_coord.line + num_removed.line)
+        {
+            coord.line = old_coord.line;
+            coord.column -= num_removed.column;
+        }
+
+        // apply move
+        coord.line += new_coord.line - old_coord.line;
+        coord.column += new_coord.column - old_coord.column;
+
+        // apply add
+        if (coord.line == new_coord.line)
+        {
+            if (num_added.line == 0)
+                coord.column += num_added.column;
+            else
+                coord.column += num_added.column - new_coord.column;
+        }
+        coord.line += num_added.line;
+
+        return coord;
+    }
+
+    ByteCoord get_new_coord(ByteCoord coord) const
+    {
+        bool dummy;
+        return get_new_coord(coord, dummy);
+    }
+};
+
+std::vector<Modification> compute_modifications(const Buffer& buffer, size_t timestamp);
+std::vector<Modification> compute_modifications(memoryview<Buffer::Change> changes);
+
+}
+
+#endif // modification_hh_INCLUDED
diff --git a/src/selection.cc b/src/selection.cc
index 1e8356ab..6b00dc54 100644
--- a/src/selection.cc
+++ b/src/selection.cc
@@ -1,6 +1,7 @@
 #include "selection.hh"
 
 #include "utf8.hh"
+#include "modification.hh"
 
 namespace Kakoune
 {
@@ -132,17 +133,34 @@ void update_erase(std::vector<Selection>& sels, ByteCoord begin, ByteCoord end,
     on_buffer_change<UpdateErase>(sels, begin, end, at_end, end.line);
 }
 
+static ByteCoord update_pos(memoryview<Modification> modifs, ByteCoord pos)
+{
+    auto modif_it = std::upper_bound(modifs.begin(), modifs.end(), pos,
+                                     [](const ByteCoord& c, const Modification& m)
+                                     { return c < m.old_coord; });
+    if (modif_it != modifs.begin())
+    {
+        auto& prev = *(modif_it-1);
+        return prev.get_new_coord(pos);
+    }
+    return pos;
+}
+
 void SelectionList::update()
 {
     if (m_timestamp == m_buffer->timestamp())
         return;
 
-    for (auto& change : m_buffer->changes_since(m_timestamp))
+    auto modifs = compute_modifications(*m_buffer, m_timestamp);
+    for (auto& sel : m_selections)
     {
-        if (change.type == Buffer::Change::Insert)
-            update_insert(m_selections, change.begin, change.end, change.at_end);
-        else
-            update_erase(m_selections, change.begin, change.end, change.at_end);
+        auto anchor = update_pos(modifs, sel.anchor());
+        kak_assert(m_buffer->is_valid(anchor));
+        sel.anchor() = anchor;
+
+        auto cursor = update_pos(modifs, sel.cursor());
+        kak_assert(m_buffer->is_valid(cursor));
+        sel.cursor() = cursor;
     }
 
     check_invariant();
diff --git a/src/unit_tests.cc b/src/unit_tests.cc
index 0bfa341b..fa21b736 100644
--- a/src/unit_tests.cc
+++ b/src/unit_tests.cc
@@ -4,6 +4,8 @@
 #include "selectors.hh"
 #include "word_db.hh"
 
+#include "modification.hh"
+
 using namespace Kakoune;
 
 void test_buffer()
@@ -139,6 +141,69 @@ void test_keys()
     kak_assert(keys == parsed_keys);
 }
 
+void test_modification()
+{
+    {
+        Modification modif = { {5, 10}, {5, 10}, {0, 0}, {4, 17} };
+        auto pos = modif.get_new_coord({5, 10});
+        kak_assert(pos == ByteCoord{9 COMMA 17});
+    }
+    {
+        Modification modif = { {7, 10}, {7, 10}, {0, 5}, {0, 0} };
+        auto pos = modif.get_new_coord({7, 10});
+        kak_assert(pos == ByteCoord{7 COMMA 10});
+    }
+    {
+        std::vector<Buffer::Change> change = {
+            { Buffer::Change::Insert, {1, 0}, {5, 161}, false },
+            { Buffer::Change::Insert, {5, 161}, {30, 0}, false },
+            { Buffer::Change::Insert, {30, 0}, {35, 0}, false },
+        };
+        auto modifs = compute_modifications(change);
+        kak_assert(modifs.size() == 1);
+        auto& modif = modifs[0];
+        kak_assert(modif.old_coord == ByteCoord{1 COMMA 0});
+        kak_assert(modif.new_coord == ByteCoord{1 COMMA 0});
+        kak_assert(modif.num_added == ByteCoord{34 COMMA 0});
+        kak_assert(modif.num_removed == ByteCoord{0 COMMA 0});
+    }
+
+    Buffer buffer("test", Buffer::Flags::None,
+                  { "tchou mutch\n",
+                    "tchou kanaky tchou\n",
+                    "\n",
+                    "tchaa tchaa\n",
+                    "allo\n"});
+
+    size_t timestamp = buffer.timestamp();
+
+    buffer.erase(buffer.iterator_at({0,0}), buffer.iterator_at({3,0}));
+    buffer.insert(buffer.iterator_at({0,0}), "youuhou\nniahaha");
+
+    buffer.insert(buffer.iterator_at({2,4}), "yeehaah\n");
+
+    auto modifs = compute_modifications(buffer, timestamp);
+    kak_assert(modifs.size() == 2);
+    {
+        auto& modif = modifs[0];
+        kak_assert(modif.old_coord == ByteCoord{0 COMMA 0});
+        kak_assert(modif.new_coord == ByteCoord{0 COMMA 0});
+        kak_assert(modif.num_added == ByteCoord{1 COMMA 7});
+        kak_assert(modif.num_removed == ByteCoord{3 COMMA 0});
+        bool deleted;
+        auto new_coord = modif.get_new_coord({1, 10}, deleted);
+        kak_assert(new_coord == ByteCoord{1 COMMA 7});
+        kak_assert(deleted);
+    }
+    {
+        auto& modif = modifs[1];
+        kak_assert(modif.old_coord == ByteCoord{4 COMMA 4});
+        kak_assert(modif.new_coord == ByteCoord{2 COMMA 4});
+        kak_assert(modif.num_added == ByteCoord{1 COMMA 0});
+        kak_assert(modif.num_removed == ByteCoord{0 COMMA 0});
+    }
+}
+
 void run_unit_tests()
 {
     test_utf8();
@@ -146,5 +211,6 @@ void run_unit_tests()
     test_keys();
     test_buffer();
     test_undo_group_optimizer();
+    test_modification();
     test_word_db();
 }