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 }