kakoune

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

selection.cc (19103B)


      1 #include "selection.hh"
      2 
      3 #include "buffer_utils.hh"
      4 #include "changes.hh"
      5 #include "format.hh"
      6 #include "ranges.hh"
      7 #include "string_utils.hh"
      8 
      9 namespace Kakoune
     10 {
     11 
     12 SelectionList::~SelectionList() = default;
     13 
     14 SelectionList::SelectionList(Buffer& buffer, Selection s, size_t timestamp)
     15     : m_selections({ std::move(s) }), m_buffer(&buffer), m_timestamp(timestamp)
     16 {
     17     check_invariant();
     18 }
     19 
     20 SelectionList::SelectionList(Buffer& buffer, Selection s)
     21     : SelectionList(buffer, std::move(s), buffer.timestamp()) {}
     22 
     23 SelectionList::SelectionList(Buffer& buffer, Vector<Selection> list, size_t timestamp)
     24     : m_selections(std::move(list)), m_buffer(&buffer), m_timestamp(timestamp)
     25 {
     26     kak_assert(size() > 0);
     27     m_main = size() - 1;
     28     check_invariant();
     29 }
     30 
     31 SelectionList::SelectionList(Buffer& buffer, Vector<Selection> list)
     32     : SelectionList(buffer, std::move(list), buffer.timestamp()) {}
     33 
     34 SelectionList::SelectionList(const SelectionList&) = default;
     35 SelectionList::SelectionList(SelectionList&&) = default;
     36 SelectionList& SelectionList::operator=(const SelectionList&) = default;
     37 SelectionList& SelectionList::operator=(SelectionList&&) = default;
     38 
     39 void SelectionList::remove(size_t index)
     40 {
     41     m_selections.erase(begin() + index);
     42     if (index < m_main or m_main == m_selections.size())
     43         --m_main;
     44 }
     45 
     46 void SelectionList::remove_from(size_t index)
     47 {
     48     kak_assert(index > 0);
     49     m_selections.erase(begin() + index, end());
     50     if (index <= m_main)
     51         m_main = m_selections.size() - 1;
     52 }
     53 
     54 void SelectionList::set(Vector<Selection> list, size_t main)
     55 {
     56     kak_assert(main < list.size());
     57     m_selections = std::move(list);
     58     m_main = main;
     59     m_timestamp = m_buffer->timestamp();
     60     sort();
     61     check_invariant();
     62 }
     63 
     64 bool compare_selections(const Selection& lhs, const Selection& rhs)
     65 {
     66     const auto& lmin = lhs.min(), rmin = rhs.min();
     67     return lmin == rmin ? lhs.max() < rhs.max() : lmin < rmin;
     68 }
     69 
     70 namespace
     71 {
     72 
     73 BufferCoord update_insert(BufferCoord coord, BufferCoord begin, BufferCoord end)
     74 {
     75     if (coord < begin)
     76         return coord;
     77     if (begin.line == coord.line)
     78         coord.column += end.column - begin.column;
     79     coord.line += end.line - begin.line;
     80     kak_assert(coord.line >= 0 and coord.column >= 0);
     81     return coord;
     82 }
     83 
     84 /* For reference
     85 BufferCoord update_erase(BufferCoord coord, BufferCoord begin, BufferCoord end)
     86 {
     87     if (coord < begin)
     88         return coord;
     89     if (coord <= end)
     90         return begin;
     91     if (end.line == coord.line)
     92         coord.column -= end.column - begin.column;
     93     coord.line -= end.line - begin.line;
     94     kak_assert(coord.line >= 0 and coord.column >= 0);
     95     return coord;
     96 } */
     97 
     98 template<typename Iterator, typename OverlapsFunc>
     99 Iterator merge_overlapping(Iterator begin, Iterator end, size_t& main, OverlapsFunc overlaps)
    100 {
    101     if (begin == end)
    102         return begin;
    103 
    104     kak_assert(std::is_sorted(begin, end, compare_selections));
    105     size_t size = end - begin;
    106     size_t i = 0;
    107     for (size_t j = 1; j < size; ++j)
    108     {
    109         if (overlaps(begin[i], begin[j]))
    110         {
    111             begin[i].min() = std::min(begin[i].min(), begin[j].min());
    112             begin[i].max() = std::max(begin[i].max(), begin[j].max());
    113             if (i < main)
    114                 --main;
    115         }
    116         else if (++i != j)
    117         {
    118             begin[i] = std::move(begin[j]);
    119         }
    120     }
    121     kak_assert(std::is_sorted(begin, begin + i +1, compare_selections));
    122     return begin + i + 1;
    123 }
    124 
    125 }
    126 
    127 BufferCoord& get_first(Selection& sel) { return sel.min(); }
    128 BufferCoord& get_last(Selection& sel) { return sel.max(); }
    129 
    130 Vector<Selection> compute_modified_ranges(const Buffer& buffer, size_t timestamp)
    131 {
    132     Vector<Selection> ranges;
    133     auto changes = buffer.changes_since(timestamp);
    134     auto change_it = changes.begin();
    135     while (change_it != changes.end())
    136     {
    137         auto forward_end = forward_sorted_until(change_it, changes.end());
    138         auto backward_end = backward_sorted_until(change_it, changes.end());
    139 
    140         kak_assert(std::is_sorted(ranges.begin(), ranges.end(), compare_selections));
    141 
    142         size_t prev_size;
    143         size_t dummy = 0;
    144         if (forward_end >= backward_end)
    145         {
    146             update_forward({ change_it, forward_end }, ranges);
    147             ranges.erase(merge_overlapping(ranges.begin(), ranges.end(), dummy, overlaps), ranges.end());
    148             prev_size = ranges.size();
    149 
    150             ForwardChangesTracker changes_tracker;
    151             for (; change_it != forward_end; ++change_it)
    152             {
    153                 if (change_it->type == Buffer::Change::Insert)
    154                     ranges.emplace_back(change_it->begin, change_it->end);
    155                 else
    156                     ranges.emplace_back(change_it->begin);
    157                 changes_tracker.update(*change_it);
    158             }
    159         }
    160         else
    161         {
    162             update_backward({ change_it, backward_end }, ranges);
    163             ranges.erase(merge_overlapping(ranges.begin(), ranges.end(), dummy, overlaps), ranges.end());
    164             prev_size = ranges.size();
    165 
    166             using ReverseIt = std::reverse_iterator<const Buffer::Change*>;
    167             ForwardChangesTracker changes_tracker;
    168             for (ReverseIt it{backward_end}, end{change_it}; it != end; ++it)
    169             {
    170                 auto change = *it;
    171                 change.begin = changes_tracker.get_new_coord(change.begin);
    172                 change.end = changes_tracker.get_new_coord(change.end);
    173 
    174                 if (change.type == Buffer::Change::Insert)
    175                     ranges.emplace_back(change.begin, change.end);
    176                 else
    177                     ranges.emplace_back(change.begin);
    178                 changes_tracker.update(change);
    179             }
    180             change_it = backward_end;
    181         }
    182 
    183         kak_assert(std::is_sorted(ranges.begin() + prev_size, ranges.end(), compare_selections));
    184         std::inplace_merge(ranges.begin(), ranges.begin() + prev_size, ranges.end(), compare_selections);
    185         // The newly added ranges might be overlapping pre-existing ones
    186         ranges.erase(merge_overlapping(ranges.begin(), ranges.end(), dummy, overlaps), ranges.end());
    187     }
    188 
    189     const auto end_coord = buffer.end_coord();
    190     for (auto& range : ranges)
    191     {
    192         range.anchor() = std::min(range.anchor(), end_coord);
    193         range.cursor() = std::min<BufferCoord>(range.cursor(), end_coord);
    194     }
    195 
    196     auto touches = [&](const Selection& lhs, const Selection& rhs) {
    197         return lhs.max() == end_coord or buffer.char_next(lhs.max()) >= rhs.min();
    198     };
    199     size_t dummy = 0;
    200     ranges.erase(merge_overlapping(ranges.begin(), ranges.end(), dummy, touches), ranges.end());
    201 
    202     for (auto& sel : ranges)
    203     {
    204         kak_assert(buffer.is_valid(sel.anchor()));
    205         kak_assert(buffer.is_valid(sel.cursor()));
    206 
    207         if (buffer.is_end(sel.anchor()))
    208             sel.anchor() = buffer.back_coord();
    209         if (buffer.is_end(sel.cursor()))
    210             sel.cursor() = buffer.back_coord();
    211 
    212         if (sel.anchor() != sel.cursor())
    213             sel.cursor() = buffer.char_prev(sel.cursor());
    214     }
    215     return ranges;
    216 }
    217 
    218 static void clamp(Selection& sel, const Buffer& buffer)
    219 {
    220     sel.anchor() = buffer.clamp(sel.anchor());
    221     sel.cursor() = buffer.clamp(sel.cursor());
    222 }
    223 
    224 void clamp_selections(Vector<Selection>& selections, const Buffer& buffer)
    225 {
    226     for (auto& sel : selections)
    227         clamp(sel, buffer);
    228 }
    229 
    230 void update_selections(Vector<Selection>& selections, size_t& main, const Buffer& buffer, size_t timestamp, bool merge)
    231 {
    232     if (timestamp == buffer.timestamp())
    233         return;
    234 
    235     auto changes = buffer.changes_since(timestamp);
    236     auto change_it = changes.begin();
    237     while (change_it != changes.end())
    238     {
    239         auto forward_end = forward_sorted_until(change_it, changes.end());
    240         auto backward_end = backward_sorted_until(change_it, changes.end());
    241 
    242         if (forward_end >= backward_end)
    243         {
    244             update_forward({ change_it, forward_end }, selections);
    245             change_it = forward_end;
    246         }
    247         else
    248         {
    249             update_backward({ change_it, backward_end }, selections);
    250             change_it = backward_end;
    251         }
    252         kak_assert(std::is_sorted(selections.begin(), selections.end(),
    253                                   compare_selections));
    254     }
    255     for (auto& sel : selections)
    256         clamp(sel, buffer);
    257 
    258     if (merge)
    259         selections.erase(merge_overlapping(selections.begin(), selections.end(),
    260                                            main, overlaps), selections.end());
    261 }
    262 
    263 void SelectionList::update(bool merge)
    264 {
    265     update_selections(m_selections, m_main, *m_buffer, m_timestamp, merge);
    266     check_invariant();
    267     m_timestamp = m_buffer->timestamp();
    268 }
    269 
    270 void SelectionList::check_invariant() const
    271 {
    272 #ifdef KAK_DEBUG
    273     auto& buffer = this->buffer();
    274     kak_assert(size() > 0);
    275     kak_assert(m_main < size());
    276     const size_t timestamp = buffer.timestamp();
    277     kak_assert(timestamp >= m_timestamp);
    278 
    279     // cannot check further in that case
    280     if (timestamp != m_timestamp)
    281         return;
    282 
    283     const auto end_coord = buffer.end_coord();
    284     BufferCoord last_min{0,0};
    285     for (auto& sel : m_selections)
    286     {
    287         auto& min = sel.min();
    288         kak_assert(min >= last_min);
    289         last_min = min;
    290 
    291         const auto anchor = sel.anchor();
    292         kak_assert(anchor >= BufferCoord{0,0} and anchor < end_coord);
    293         kak_assert(anchor.column < buffer[anchor.line].length());
    294 
    295         const auto cursor = sel.cursor();
    296         kak_assert(cursor >= BufferCoord{0,0} and cursor < end_coord);
    297         kak_assert(cursor.column < buffer[cursor.line].length());
    298     }
    299 #endif
    300 }
    301 
    302 void sort_selections(Vector<Selection>& selections, size_t& main_index)
    303 {
    304     if (selections.size() == 1)
    305         return;
    306 
    307     const auto& main = selections[main_index];
    308     const auto main_begin = main.min();
    309     main_index = std::count_if(selections.begin(), selections.end(),
    310                                [&](const Selection& sel) {
    311         auto begin = sel.min();
    312         if (begin == main_begin)
    313             return &sel < &main;
    314         else
    315             return begin < main_begin;
    316     });
    317     std::stable_sort(selections.begin(), selections.end(), compare_selections);
    318 }
    319 
    320 void merge_overlapping_selections(Vector<Selection>& selections, size_t& main_index)
    321 {
    322     if (selections.size() == 1)
    323         return;
    324 
    325     selections.erase(Kakoune::merge_overlapping(selections.begin(), selections.end(),
    326                                                 main_index, overlaps), selections.end());
    327 }
    328 
    329 void SelectionList::sort()
    330 {
    331     sort_selections(m_selections, m_main);
    332 }
    333 
    334 void SelectionList::merge_overlapping()
    335 {
    336     merge_overlapping_selections(m_selections, m_main);
    337 }
    338 
    339 void SelectionList::merge_consecutive()
    340 {
    341     if (size() == 1)
    342         return;
    343 
    344     auto touches = [this](const Selection& lhs, const Selection& rhs) {
    345         return m_buffer->char_next(lhs.max()) >= rhs.min();
    346     };
    347     m_selections.erase(Kakoune::merge_overlapping(begin(), end(),
    348                                                   m_main, touches), end());
    349 }
    350 
    351 void SelectionList::sort_and_merge_overlapping()
    352 {
    353     sort();
    354     merge_overlapping();
    355 }
    356 
    357 static void fix_overflowing_selections(Vector<Selection>& selections,
    358                                        const Buffer& buffer)
    359 {
    360     const BufferCoord back_coord = buffer.back_coord();
    361     for (auto& sel : selections)
    362     {
    363         sel.cursor() = std::min(buffer.clamp(sel.cursor()), back_coord);
    364         sel.anchor() = std::min(buffer.clamp(sel.anchor()), back_coord);
    365     }
    366 }
    367 
    368 bool any_overlaps(ConstArrayView<Selection> sels)
    369 {
    370     for (int i = 0; i + 1 < sels.size(); ++i)
    371     {
    372         if (overlaps(sels[i], sels[i+1]))
    373             return true;
    374     }
    375     return false;
    376 }
    377 
    378 void SelectionList::for_each(ApplyFunc func, bool may_append)
    379 {
    380     update();
    381 
    382     if (may_append and any_overlaps(m_selections))
    383     {
    384         size_t timestamp = m_buffer->timestamp();
    385         for (size_t index = 0; index < m_selections.size(); ++index)
    386         {
    387             auto& sel = m_selections[index];
    388             update_ranges(*m_buffer, timestamp, ArrayView<Selection>(sel));
    389             func(index, sel);
    390         }
    391     }
    392     else
    393     {
    394         ForwardChangesTracker changes_tracker;
    395         for (size_t index = 0; index < m_selections.size(); ++index)
    396         {
    397             auto& sel = m_selections[index];
    398 
    399             sel.anchor() = changes_tracker.get_new_coord_tolerant(sel.anchor());
    400             sel.cursor() = changes_tracker.get_new_coord_tolerant(sel.cursor());
    401             kak_assert(m_buffer->is_valid(sel.anchor()) and m_buffer->is_valid(sel.cursor()));
    402 
    403             func(index, sel);
    404 
    405             changes_tracker.update(*m_buffer, m_timestamp);
    406         }
    407     }
    408 
    409     // We might just have been deleting text if strings were empty,
    410     // in which case we could have some selections pushed out of the buffer
    411     fix_overflowing_selections(m_selections, *m_buffer);
    412 
    413     check_invariant();
    414     m_buffer->check_invariant();
    415 }
    416 
    417 
    418 void replace(Buffer& buffer, Selection& sel, StringView content)
    419 {
    420     // we want min and max from *before* we do any change
    421     auto& min = sel.min();
    422     auto& max = sel.max();
    423     BufferRange range = buffer.replace(min, buffer.char_next(max), content);
    424     min = range.begin;
    425     max = range.end > range.begin ? buffer.char_prev(range.end) : range.begin;
    426 }
    427 
    428 BufferRange insert(Buffer& buffer, Selection& sel, BufferCoord pos, StringView content)
    429 {
    430     auto range = buffer.insert(pos, content);
    431     sel.anchor() = buffer.clamp(update_insert(sel.anchor(), range.begin, range.end));
    432     sel.cursor() = buffer.clamp(update_insert(sel.cursor(), range.begin, range.end));
    433     return range;
    434 }
    435 
    436 void SelectionList::replace(ConstArrayView<String> strings)
    437 {
    438     if (strings.empty())
    439         return;
    440 
    441     for_each([&](size_t index, Selection& sel) {
    442         Kakoune::replace(*m_buffer, sel, strings[std::min(strings.size()-1, index)]);
    443     }, false);
    444 }
    445 
    446 void SelectionList::erase()
    447 {
    448     update();
    449     merge_overlapping();
    450 
    451     ForwardChangesTracker changes_tracker;
    452     for (auto& sel : m_selections)
    453     {
    454         sel.anchor() = changes_tracker.get_new_coord(sel.anchor());
    455         kak_assert(m_buffer->is_valid(sel.anchor()));
    456         sel.cursor() = changes_tracker.get_new_coord(sel.cursor());
    457         kak_assert(m_buffer->is_valid(sel.cursor()));
    458 
    459         auto pos = Kakoune::erase(*m_buffer, sel);
    460         sel.anchor() = sel.cursor() = pos;
    461         changes_tracker.update(*m_buffer, m_timestamp);
    462     }
    463 
    464     fix_overflowing_selections(m_selections, *m_buffer);
    465     m_buffer->check_invariant();
    466 }
    467 
    468 String selection_to_string(ColumnType column_type, const Buffer& buffer, const Selection& selection, ColumnCount tabstop)
    469 {
    470     const auto& cursor = selection.cursor();
    471     const auto& anchor = selection.anchor();
    472     switch (column_type)
    473     {
    474     default:
    475     case ColumnType::Byte:
    476         return format("{}.{},{}.{}", anchor.line + 1, anchor.column + 1,
    477                       cursor.line + 1, cursor.column + 1);
    478     case ColumnType::Codepoint:
    479         return format("{}.{},{}.{}",
    480                       anchor.line + 1, buffer[anchor.line].char_count_to(anchor.column) + 1,
    481                       cursor.line + 1, buffer[cursor.line].char_count_to(cursor.column) + 1);
    482     case ColumnType::DisplayColumn:
    483         kak_assert(tabstop != -1);
    484         return format("{}.{},{}.{}",
    485                       anchor.line + 1, get_column(buffer, tabstop, anchor) + 1,
    486                       cursor.line + 1, get_column(buffer, tabstop, cursor) + 1);
    487     }
    488 }
    489 
    490 String selection_list_to_string(ColumnType column_type, const SelectionList& selections, ColumnCount tabstop)
    491 {
    492     auto& buffer = selections.buffer();
    493     kak_assert(selections.timestamp() == buffer.timestamp());
    494 
    495     auto to_string = [&](const Selection& selection) {
    496         return selection_to_string(column_type, buffer, selection, tabstop);
    497     };
    498 
    499     auto beg = &*selections.begin(), end = &*selections.end();
    500     auto main = beg + selections.main_index();
    501     using View = ConstArrayView<Selection>;
    502     return join(concatenated(View{main, end}, View{beg, main}) |
    503                 transform(to_string), ' ', false);
    504 }
    505 
    506 Selection selection_from_string(ColumnType column_type, const Buffer& buffer, StringView desc, ColumnCount tabstop)
    507 {
    508     auto comma = find(desc, ',');
    509     auto dot_anchor = find(StringView{desc.begin(), comma}, '.');
    510     auto dot_cursor = find(StringView{comma, desc.end()}, '.');
    511 
    512     if (comma == desc.end() or dot_anchor == comma or dot_cursor == desc.end())
    513         throw runtime_error(format("'{}' does not follow <line>.<column>,<line>.<column> format", desc));
    514 
    515     auto compute_coord = [&](int line, int column) -> BufferCoord {
    516         if (line < 0 or column < 0)
    517             throw runtime_error(format("coordinate {}.{} does not exist in buffer", line + 1, column + 1));
    518 
    519         switch (column_type)
    520         {
    521         default:
    522         case ColumnType::Byte: return {line, column};
    523         case ColumnType::Codepoint:
    524             if (buffer.line_count() <= line or buffer[line].char_length() <= column)
    525                 throw runtime_error(format("coordinate {}.{} does not exist in buffer", line + 1, column + 1));
    526             return {line, buffer[line].byte_count_to(CharCount{column})};
    527         case ColumnType::DisplayColumn:
    528             kak_assert(tabstop != -1);
    529             if (buffer.line_count() <= line or column_length(buffer, tabstop, line) <= column)
    530                 throw runtime_error(format("coordinate {}.{} does not exist in buffer", line + 1, column + 1));
    531             return {line, get_byte_to_column(buffer, tabstop, DisplayCoord{line, ColumnCount{column}})};
    532         }
    533     };
    534 
    535     auto anchor = compute_coord(str_to_int({desc.begin(), dot_anchor}) - 1,
    536                                 str_to_int({dot_anchor+1, comma}) - 1);
    537 
    538     auto cursor = compute_coord(str_to_int({comma+1, dot_cursor}) - 1,
    539                                 str_to_int({dot_cursor+1, desc.end()}) - 1);
    540 
    541     return Selection{anchor, cursor};
    542 }
    543 
    544 SelectionList selection_list_from_strings(Buffer& buffer, ColumnType column_type, ConstArrayView<String> descs, size_t timestamp, size_t main, ColumnCount tabstop)
    545 {
    546     if ((column_type != ColumnType::Byte and timestamp != buffer.timestamp()) or timestamp > buffer.timestamp())
    547         throw runtime_error{format("invalid timestamp '{}'", timestamp)};
    548 
    549     auto from_string = [&](StringView desc) {
    550         return selection_from_string(column_type, buffer, desc, tabstop);
    551     };
    552 
    553     auto sels = descs | transform(from_string) | gather<Vector<Selection>>();
    554     if (sels.empty())
    555         throw runtime_error{"empty selection description"};
    556     if (main >= sels.size())
    557         throw runtime_error{"invalid main selection index"};
    558 
    559     sort_selections(sels, main);
    560     merge_overlapping_selections(sels, main);
    561     if (timestamp < buffer.timestamp())
    562         update_selections(sels, main, buffer, timestamp);
    563     else
    564         clamp_selections(sels, buffer);
    565 
    566     SelectionList res{buffer, std::move(sels)};
    567     res.set_main_index(main);
    568     return res;
    569 }
    570 
    571 }