kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

line_modification.cc (11640B)


      1 #include "line_modification.hh"
      2 
      3 #include "buffer.hh"
      4 #include "unit_tests.hh"
      5 #include "ranges.hh"
      6 
      7 namespace Kakoune
      8 {
      9 
     10 static LineModification make_line_modif(const Buffer::Change& change)
     11 {
     12     LineCount num_added = 0, num_removed = 0;
     13     if (change.type == Buffer::Change::Insert)
     14         num_added = change.end.line - change.begin.line;
     15     else
     16         num_removed = change.end.line - change.begin.line;
     17     // modified a line
     18     if ((change.begin.column != 0 or change.end.column != 0))
     19     {
     20         ++num_removed;
     21         ++num_added;
     22     }
     23     return { change.begin.line, change.begin.line, num_removed, num_added };
     24 }
     25 
     26 Vector<LineModification> compute_line_modifications(const Buffer& buffer, size_t timestamp)
     27 {
     28     Vector<LineModification> res;
     29     for (auto& buf_change : buffer.changes_since(timestamp))
     30     {
     31         auto change = make_line_modif(buf_change);
     32 
     33         auto pos = std::upper_bound(res.begin(), res.end(), change.new_line,
     34                                     [](const LineCount& l, const LineModification& c)
     35                                     { return l < c.new_line; });
     36 
     37         if (pos != res.begin())
     38         {
     39             auto& prev = *(pos-1);
     40             if (change.new_line <= prev.new_line + prev.num_added)
     41             {
     42                 --pos;
     43                 const LineCount removed_from_previously_added_by_pos =
     44                     clamp(pos->new_line + pos->num_added - change.new_line,
     45                           0_line, std::min(pos->num_added, change.num_removed));
     46 
     47                 pos->num_removed += change.num_removed - removed_from_previously_added_by_pos;
     48                 pos->num_added += change.num_added - removed_from_previously_added_by_pos;
     49             }
     50             else
     51             {
     52                 change.old_line -= prev.diff();
     53                 pos = res.insert(pos, change);
     54             }
     55         }
     56         else
     57             pos = res.insert(pos, change);
     58 
     59         auto next = pos + 1;
     60         auto diff = buf_change.end.line - buf_change.begin.line;
     61         if (buf_change.type == Buffer::Change::Erase)
     62         {
     63             auto delend = std::upper_bound(next, res.end(), change.new_line + change.num_removed,
     64                                            [](const LineCount& l, const LineModification& c)
     65                                            { return l < c.new_line; });
     66 
     67             for (auto it = next; it != delend; ++it)
     68             {
     69                 const LineCount removed_from_previously_added_by_it =
     70                     std::min(it->num_added, change.new_line + change.num_removed - it->new_line);
     71 
     72                 pos->num_removed += it->num_removed - removed_from_previously_added_by_it;
     73                 pos->num_added += it->num_added - removed_from_previously_added_by_it;
     74             }
     75             next = res.erase(next, delend);
     76 
     77             if (diff != 0)
     78             {
     79                 for (auto it = next; it != res.end(); ++it)
     80                     it->new_line -= diff;
     81             }
     82         }
     83         else if (diff != 0)
     84         {
     85             for (auto it = next; it != res.end(); ++it)
     86                 it->new_line += diff;
     87         }
     88     }
     89     return res;
     90 }
     91 
     92 void LineRangeSet::update(ConstArrayView<LineModification> modifs)
     93 {
     94     if (modifs.empty())
     95         return;
     96 
     97     for (auto it = begin(); it != end(); ++it)
     98     {
     99         auto modif_beg = std::lower_bound(modifs.begin(), modifs.end(), it->begin,
    100                                           [](const LineModification& c, const LineCount& l)
    101                                           { return c.old_line + c.num_removed < l; });
    102         auto modif_end = std::upper_bound(modifs.begin(), modifs.end(), it->end,
    103                                           [](const LineCount& l, const LineModification& c)
    104                                           { return l < c.old_line; });
    105 
    106         if (modif_beg == modifs.end())
    107         {
    108             const auto diff = (modif_beg-1)->diff();
    109             it->begin += diff;
    110             it->end += diff;
    111             continue;
    112         }
    113 
    114         const auto diff = modif_beg->new_line - modif_beg->old_line;
    115         it->begin += diff;
    116         it->end += diff;
    117 
    118         while (modif_beg != modif_end)
    119         {
    120             auto& m = *modif_beg++;
    121             if (m.num_removed > 0)
    122             {
    123                 if (m.new_line < it->begin)
    124                     it->begin = std::max(m.new_line, it->begin - m.num_removed);
    125                 it->end = std::max(m.new_line, std::max(it->begin, it->end - m.num_removed));
    126             }
    127             if (m.num_added > 0)
    128             {
    129                 if (it->begin >= m.new_line)
    130                     it->begin += m.num_added;
    131                 else
    132                 {
    133                     it = insert(it, {it->begin, m.new_line}) + 1;
    134                     it->begin = m.new_line + m.num_added;
    135                 }
    136                 it->end += m.num_added;
    137             }
    138         }
    139     };
    140     erase(remove_if(*this, [](auto& r) { return r.begin >= r.end; }), end());
    141 }
    142 
    143 void LineRangeSet::add_range(LineRange range, FunctionRef<void (LineRange)> on_new_range)
    144 {
    145     auto insert_at = std::lower_bound(begin(), end(), range.begin,
    146                                       [](LineRange range, LineCount line) { return range.end < line; });
    147     if (insert_at == end() or insert_at->begin > range.end)
    148         on_new_range(range);
    149     else
    150     {
    151         auto pos = range.begin;
    152         auto it = insert_at;
    153         for (; it != end() and it->begin <= range.end; ++it)
    154         {
    155             if (pos < it->begin)
    156                 on_new_range({pos, it->begin});
    157 
    158             range = LineRange{std::min(range.begin, it->begin), std::max(range.end, it->end)};
    159             pos = it->end;
    160         }
    161         insert_at = erase(insert_at, it);
    162         if (pos < range.end)
    163             on_new_range({pos, range.end});
    164     }
    165     insert(insert_at, range);
    166 }
    167 
    168 void LineRangeSet::remove_range(LineRange range)
    169 {
    170     auto inside = [](LineCount line, LineRange range) {
    171         return range.begin <= line and line < range.end;
    172     };
    173 
    174     auto it = std::lower_bound(begin(), end(), range.begin,
    175                                [](LineRange range, LineCount line) { return range.end < line; });
    176     if (it == end() or it->begin > range.end)
    177         return;
    178     else while (it != end() and it->begin <= range.end)
    179     {
    180         if (it->begin < range.begin and range.end <= it->end)
    181         {
    182             it = insert(it, {it->begin, range.begin}) + 1;
    183             it->begin = range.end;
    184         }
    185         if (inside(it->begin, range))
    186             it->begin = range.end;
    187         if (inside(it->end, range))
    188             it->end = range.begin;
    189 
    190         if (it->end <= it->begin)
    191             it = erase(it);
    192         else
    193             ++it;
    194     }
    195 }
    196 
    197 
    198 UnitTest test_line_modifications{[]()
    199 {
    200     auto make_lines = [](auto&&... lines) { return BufferLines{StringData::create(lines)...}; };
    201 
    202     {
    203         Buffer buffer("test", Buffer::Flags::None, make_lines("line 1\n", "line 2\n"));
    204         auto ts = buffer.timestamp();
    205         buffer.erase({1, 0}, {2, 0});
    206 
    207         auto modifs = compute_line_modifications(buffer, ts);
    208         kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 1, 1, 1, 0 });
    209     }
    210 
    211     {
    212         Buffer buffer("test", Buffer::Flags::None, make_lines("line 1\n", "line 2\n"));
    213         auto ts = buffer.timestamp();
    214         buffer.insert({2, 0}, "line 3");
    215 
    216         auto modifs = compute_line_modifications(buffer, ts);
    217         kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 2, 2, 0, 1 });
    218     }
    219 
    220     {
    221         Buffer buffer("test", Buffer::Flags::None, make_lines("line 1\n", "line 2\n", "line 3\n"));
    222 
    223         auto ts = buffer.timestamp();
    224         buffer.insert({1, 4}, "hoho\nhehe");
    225         buffer.erase({0, 0}, {1, 0});
    226 
    227         auto modifs = compute_line_modifications(buffer, ts);
    228         kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 0, 0, 2, 2 });
    229     }
    230 
    231     {
    232         Buffer buffer("test", Buffer::Flags::None, make_lines("line 1\n", "line 2\n", "line 3\n", "line 4\n"));
    233 
    234         auto ts = buffer.timestamp();
    235         buffer.erase({0,0}, {3,0});
    236         buffer.insert({1,0}, "newline 1\nnewline 2\nnewline 3\n");
    237         buffer.erase({0,0}, {1,0});
    238         {
    239             auto modifs = compute_line_modifications(buffer, ts);
    240             kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 0, 0, 4, 3 });
    241         }
    242         buffer.insert({3,0}, "newline 4\n");
    243 
    244         {
    245             auto modifs = compute_line_modifications(buffer, ts);
    246             kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 0, 0, 4, 4 });
    247         }
    248     }
    249 
    250     {
    251         Buffer buffer("test", Buffer::Flags::None, make_lines("line 1\n"));
    252         auto ts = buffer.timestamp();
    253         buffer.insert({0,0}, "n");
    254         buffer.insert({0,1}, "e");
    255         buffer.insert({0,2}, "w");
    256         auto modifs = compute_line_modifications(buffer, ts);
    257         kak_assert(modifs.size() == 1 and modifs[0] == LineModification{ 0, 0, 1, 1 });
    258     }
    259 }};
    260 
    261 UnitTest test_line_range_set{[]{
    262     auto expect = [](ConstArrayView<LineRange> ranges) {
    263         return [it = ranges.begin(), end = ranges.end()](LineRange r) mutable {
    264             kak_assert(it != end);
    265             kak_assert(r == *it++);
    266         };
    267     };
    268 
    269     {
    270         LineRangeSet ranges;
    271         ranges.add_range({0, 5}, expect({{0, 5}}));
    272         ranges.add_range({10, 15}, expect({{10, 15}}));
    273         ranges.add_range({5, 10}, expect({{5, 10}}));
    274         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 15}}));
    275         ranges.add_range({5, 10}, expect({}));
    276         ranges.remove_range({3, 8});
    277         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 3}, {8, 15}}));
    278     }
    279     {
    280         LineRangeSet ranges;
    281         ranges.add_range({0, 7}, expect({{0, 7}}));
    282         ranges.add_range({9, 15}, expect({{9, 15}}));
    283         ranges.add_range({5, 10}, expect({{7, 9}}));
    284         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 15}}));
    285     }
    286     {
    287         LineRangeSet ranges;
    288         ranges.add_range({0, 7}, expect({{0, 7}}));
    289         ranges.add_range({11, 15}, expect({{11, 15}}));
    290         ranges.add_range({5, 10}, expect({{7, 10}}));
    291         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 10}, {11, 15}}));
    292         ranges.remove_range({8, 13});
    293         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 8}, {13, 15}}));
    294     }
    295     {
    296         LineRangeSet ranges;
    297         ranges.add_range({0, 5}, expect({{0, 5}}));
    298         ranges.add_range({10, 15}, expect({{10, 15}}));
    299         ranges.update(ConstArrayView<LineModification>{{3, 3, 3, 1}, {11, 9, 2, 4}});
    300         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 3}, {8, 9}, {13, 15}}));
    301     }
    302     {
    303         LineRangeSet ranges;
    304         ranges.add_range({0, 5}, expect({{0, 5}}));
    305         ranges.update(ConstArrayView<LineModification>{{2, 2, 2, 0}});
    306         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 3}}));
    307     }
    308     {
    309         LineRangeSet ranges;
    310         ranges.add_range({0, 5}, expect({{0, 5}}));
    311         ranges.update(ConstArrayView<LineModification>{{2, 2, 0, 2}});
    312         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 2}, {4, 7}}));
    313     }
    314     {
    315         LineRangeSet ranges;
    316         ranges.add_range({0, 1}, expect({{0, 1}}));
    317         ranges.add_range({5, 10}, expect({{5, 10}}));
    318         ranges.add_range({15, 20}, expect({{15, 20}}));
    319         ranges.add_range({25, 30}, expect({{25, 30}}));
    320         ranges.update(ConstArrayView<LineModification>{{2, 2, 3, 0}});
    321         kak_assert((ranges.view() == ConstArrayView<LineRange>{{0, 1}, {2, 7}, {12, 17}, {22, 27}}));
    322     }
    323 }};
    324 
    325 }