Fix pasting after when selections are overlapping

With overlapping selections, pasting after breaks assumption of
SelectionList::for_each as our changes are no longer happening in
increasing locations.

We hence cannot rely on the ForwardChangeTracker in that case and
have to rely on the more general (and more costly) ranges update logic.

This interacts poorly with paste linewise pastes and we try to preserve
the current behaviour by tracking the last paste position.

Overall, this change really begs for overlapping selections to be
removed, but we will fix them like that for now.

Fixes #4779

7 files changed, 55 insertions, 26 deletions

diff --git a/src/changes.hh b/src/changes.hh
index 9d0328d4..c5ad0134 100644
--- a/src/changes.hh
+++ b/src/changes.hh
@@ -82,7 +82,7 @@ void update_backward(ConstArrayView<Buffer::Change> changes, RangeContainer& ran
 }
 
 template<typename RangeContainer>
-void update_ranges(Buffer& buffer, size_t& timestamp, RangeContainer&& ranges)
+void update_ranges(Buffer& buffer, size_t timestamp, RangeContainer&& ranges)
 {
     if (timestamp == buffer.timestamp())
         return;
@@ -104,7 +104,6 @@ void update_ranges(Buffer& buffer, size_t& timestamp, RangeContainer&& ranges)
             change_it = backward_end;
         }
     }
-    timestamp = buffer.timestamp();
 }
 
 }
diff --git a/src/highlighters.cc b/src/highlighters.cc
index eed8f369..ed3426e8 100644
--- a/src/highlighters.cc
+++ b/src/highlighters.cc
@@ -1588,6 +1588,7 @@ void option_list_postprocess(Vector<RangeAndString, MemoryDomain::Options>& opt)
 void option_update(RangeAndStringList& opt, const Context& context)
 {
     update_ranges(context.buffer(), opt.prefix, opt.list);
+    opt.prefix = context.buffer().timestamp();
 }
 
 bool option_add_from_strings(Vector<RangeAndString, MemoryDomain::Options>& opt, ConstArrayView<String> strs)
@@ -1618,6 +1619,7 @@ private:
         auto& buffer = context.context.buffer();
         auto& range_and_faces = get_option(context);
         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
+        range_and_faces.prefix = buffer.timestamp();
 
         for (auto& [range, face] : range_and_faces.list)
         {
@@ -1662,6 +1664,7 @@ private:
         auto& sels = context.context.selections();
         auto& range_and_faces = get_option(context);
         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
+        range_and_faces.prefix = buffer.timestamp();
 
         for (auto& [range, spec] : range_and_faces.list)
         {
@@ -1693,6 +1696,7 @@ private:
         auto& range_and_faces = get_option(context);
         const int tabstop = context.context.options()["tabstop"].get<int>();
         update_ranges(buffer, range_and_faces.prefix, range_and_faces.list);
+        range_and_faces.prefix = buffer.timestamp();
 
         for (auto& [range, spec] : range_and_faces.list)
         {
diff --git a/src/input_handler.cc b/src/input_handler.cc
index 61a07a40..f90d2d22 100644
--- a/src/input_handler.cc
+++ b/src/input_handler.cc
@@ -1470,7 +1470,7 @@ private:
         context().selections().for_each([strings, &buffer=context().buffer()]
                                         (size_t index, Selection& sel) {
             Kakoune::insert(buffer, sel, sel.cursor(), strings[std::min(strings.size()-1, index)]);
-        });
+        }, false);
     }
 
     void insert(Codepoint key)
diff --git a/src/insert_completer.cc b/src/insert_completer.cc
index dd048733..83e51d63 100644
--- a/src/insert_completer.cc
+++ b/src/insert_completer.cc
@@ -495,6 +495,8 @@ void InsertCompleter::reset()
     {
         auto& buffer = m_context.buffer();
         update_ranges(buffer, m_completions.timestamp, m_inserted_ranges);
+        m_completions.timestamp = buffer.timestamp();
+
         hook_param = join(m_inserted_ranges | filter([](auto&& r) { return not r.empty(); }) | transform([&](auto&& r) {
                 return selection_to_string(ColumnType::Byte, buffer, {r.begin, buffer.char_prev(r.end)});
             }), ' ');
diff --git a/src/normal.cc b/src/normal.cc
index a6cabec1..1142d871 100644
--- a/src/normal.cc
+++ b/src/normal.cc
@@ -429,7 +429,7 @@ void replace_with_char(Context& context, NormalParams)
         context.selections().for_each([&](size_t index, Selection& sel) {
             CharCount count = char_length(buffer, sel);
             replace(buffer, sel, String{*cp, count});
-        });
+        }, false);
     }, "replace with char", "enter char to replace with\n");
 }
 
@@ -455,7 +455,7 @@ void for_each_codepoint(Context& context, NormalParams)
              begin != end; ++begin)
             utf8::dump(std::back_inserter(str), func(*begin));
         replace(buffer, sel, str);
-    });
+    }, false);
 }
 
 void command(const Context& context, EnvVarMap env_vars, char reg = 0)
@@ -664,14 +664,14 @@ enum class PasteMode
     Replace
 };
 
-BufferCoord paste_pos(Buffer& buffer, const Selection& sel, PasteMode mode, bool linewise)
+BufferCoord paste_pos(Buffer& buffer, BufferCoord min, BufferCoord max, PasteMode mode, bool linewise)
 {
     switch (mode)
     {
         case PasteMode::Append:
-            return linewise ? std::min(buffer.line_count(), sel.max().line+1) : buffer.char_next(sel.max());
+            return linewise ? std::min(buffer.line_count(), max.line+1) : buffer.char_next(max);
         case PasteMode::Insert:
-            return linewise ? sel.min().line : sel.min();
+            return linewise ? min.line : min;
         default:
             kak_assert(false);
             return {};
@@ -690,16 +690,17 @@ void paste(Context& context, NormalParams params)
     auto& buffer = context.buffer();
     ScopedEdition edition(context);
     ScopedSelectionEdition selection_edition{context};
-    context.selections().for_each([&](size_t index, Selection& sel) {
+    context.selections().for_each([&, last=BufferCoord{}](size_t index, Selection& sel) mutable {
         auto& str = strings[std::min(strings.size()-1, index)];
         auto& min = sel.min();
         auto& max = sel.max();
         BufferRange range = (mode == PasteMode::Replace) ?
             buffer.replace(min, buffer.char_next(max), str)
-          : buffer.insert(paste_pos(buffer, sel, mode, linewise), str);
+          : buffer.insert(paste_pos(buffer, min, std::max(max, last), mode, linewise), str);
         min = range.begin;
         max = range.end > range.begin ? buffer.char_prev(range.end) : range.begin;
-    });
+        last = max;
+    }, mode == PasteMode::Append);
 }
 
 template<PasteMode mode>
@@ -733,7 +734,7 @@ void paste_all(Context& context, NormalParams params)
         selections.for_each([&](size_t, const Selection& sel) {
             auto range = (mode == PasteMode::Replace) ?
                 buffer.replace(sel.min(), buffer.char_next(sel.max()), all)
-              : buffer.insert(paste_pos(buffer, sel, mode, linewise), all);
+              : buffer.insert(paste_pos(buffer, sel.min(), sel.max(), mode, linewise), all);
 
             ByteCount pos_offset = 0;
             BufferCoord pos = range.begin;
@@ -744,7 +745,7 @@ void paste_all(Context& context, NormalParams params)
                 pos = buffer.next(end);
                 pos_offset = offset;
             }
-        });
+        }, mode == PasteMode::Append);
     }
     selections = std::move(result);
 }
@@ -784,10 +785,10 @@ void insert_output(Context& context, NormalParams params)
 
                 auto& min = sel.min();
                 auto& max = sel.max();
-                auto range = insert(buffer, sel, paste_pos(buffer, sel, mode, false), out);
+                auto range = insert(buffer, sel, paste_pos(buffer, min, max, mode, false), out);
                 min = range.begin;
                 max = range.end > range.begin ? buffer.char_prev(range.end) : range.begin;
-            });
+            }, mode == PasteMode::Append);
             selections.set_main_index(old_main);
         });
 }
diff --git a/src/selection.cc b/src/selection.cc
index cbf9bef2..f0f0270c 100644
--- a/src/selection.cc
+++ b/src/selection.cc
@@ -362,22 +362,45 @@ static void fix_overflowing_selections(Vector<Selection>& selections,
     }
 }
 
-void SelectionList::for_each(ApplyFunc func)
+bool any_overlaps(ConstArrayView<Selection> sels)
+{
+    for (int i = 0; i + 1 < sels.size(); ++i)
+    {
+        if (overlaps(sels[i], sels[i+1]))
+            return true;
+    }
+    return false;
+}
+
+void SelectionList::for_each(ApplyFunc func, bool may_append)
 {
     update();
 
-    ForwardChangesTracker changes_tracker;
-    for (size_t index = 0; index < m_selections.size(); ++index)
+    if (may_append and any_overlaps(m_selections))
+    {
+        size_t timestamp = m_buffer->timestamp();
+        for (size_t index = 0; index < m_selections.size(); ++index)
+        {
+            auto& sel = m_selections[index];
+            update_ranges(*m_buffer, timestamp, ArrayView<Selection>(sel));
+            func(index, sel);
+        }
+    }
+    else
     {
-        auto& sel = m_selections[index];
+        ForwardChangesTracker changes_tracker;
+        for (size_t index = 0; index < m_selections.size(); ++index)
+        {
+            auto& sel = m_selections[index];
 
-        sel.anchor() = changes_tracker.get_new_coord_tolerant(sel.anchor());
-        sel.cursor() = changes_tracker.get_new_coord_tolerant(sel.cursor());
-        kak_assert(m_buffer->is_valid(sel.anchor()) and m_buffer->is_valid(sel.cursor()));
+            sel.anchor() = changes_tracker.get_new_coord_tolerant(sel.anchor());
+            sel.cursor() = changes_tracker.get_new_coord_tolerant(sel.cursor());
+            kak_assert(m_buffer->is_valid(sel.anchor()) and m_buffer->is_valid(sel.cursor()));
 
-        func(index, sel);
+            func(index, sel);
 
-        changes_tracker.update(*m_buffer, m_timestamp);
+            changes_tracker.update(*m_buffer, m_timestamp);
+        }
     }
 
     // We might just have been deleting text if strings were empty,
@@ -414,7 +437,7 @@ void SelectionList::replace(ConstArrayView<String> strings)
 
     for_each([&](size_t index, Selection& sel) {
         Kakoune::replace(*m_buffer, sel, strings[std::min(strings.size()-1, index)]);
-    });
+    }, false);
 }
 
 void SelectionList::erase()
diff --git a/src/selection.hh b/src/selection.hh
index 299406be..bdfd7d41 100644
--- a/src/selection.hh
+++ b/src/selection.hh
@@ -137,7 +137,7 @@ struct SelectionList
     void force_timestamp(size_t timestamp) { m_timestamp = timestamp; }
 
     using ApplyFunc = FunctionRef<void (size_t index, Selection& sel)>;
-    void for_each(ApplyFunc apply);
+    void for_each(ApplyFunc apply, bool may_append);
 
     void replace(ConstArrayView<String> strings);