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 }