iOS/Pods/Realm/Realm/ObjectStore/src/impl/collection_change_builder.cpp

   1 ////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2016 Realm Inc.
   4 //
   5 // Licensed under the Apache License, Version 2.0 (the "License");
   6 // you may not use this file except in compliance with the License.
   7 // You may obtain a copy of the License at
   8 //
   9 // http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing, software
  12 // distributed under the License is distributed on an "AS IS" BASIS,
  13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 // See the License for the specific language governing permissions and
  15 // limitations under the License.
  16 //
  17 ////////////////////////////////////////////////////////////////////////////
  18
  19 #include "impl/collection_change_builder.hpp"
  20
  21 #include <realm/util/assert.hpp>
  22 #include <algorithm>
  23
  24 #include <algorithm>
  25
  26 using namespace realm;
  27 using namespace realm::_impl;
  28
  29 CollectionChangeBuilder::CollectionChangeBuilder(IndexSet deletions,
  30                                                  IndexSet insertions,
  31                                                  IndexSet modifications,
  32                                                  std::vector<Move> moves)
  33 : CollectionChangeSet({std::move(deletions), std::move(insertions), std::move(modifications), {}, std::move(moves)})
  34 {
  35     for (auto&& move : this->moves) {
  36         this->deletions.add(move.from);
  37         this->insertions.add(move.to);
  38     }
  39 }
  40
  41 void CollectionChangeBuilder::merge(CollectionChangeBuilder&& c)
  42 {
  43     if (c.empty())
  44         return;
  45     if (empty()) {
  46         *this = std::move(c);
  47         return;
  48     }
  49
  50     verify();
  51     c.verify();
  52
  53     auto for_each_col = [&](auto&& f) {
  54         f(modifications, c.modifications);
  55         if (m_track_columns) {
  56             if (columns.size() < c.columns.size())
  57                 columns.resize(c.columns.size());
  58             else if (columns.size() > c.columns.size())
  59                 c.columns.resize(columns.size());
  60             for (size_t i = 0; i < columns.size(); ++i)
  61                 f(columns[i], c.columns[i]);
  62         }
  63     };
  64
  65     // First update any old moves
  66     if (!c.moves.empty() || !c.deletions.empty() || !c.insertions.empty()) {
  67         auto it = std::remove_if(begin(moves), end(moves), [&](auto& old) {
  68             // Check if the moved row was moved again, and if so just update the destination
  69             auto it = find_if(begin(c.moves), end(c.moves), [&](auto const& m) {
  70                 return old.to == m.from;
  71             });
  72             if (it != c.moves.end()) {
  73                 for_each_col([&](auto& col, auto& other) {
  74                     if (col.contains(it->from))
  75                         other.add(it->to);
  76                 });
  77                 old.to = it->to;
  78                 *it = c.moves.back();
  79                 c.moves.pop_back();
  80                 return false;
  81             }
  82
  83             // Check if the destination was deleted
  84             // Removing the insert for this move will happen later
  85             if (c.deletions.contains(old.to))
  86                 return true;
  87
  88             // Update the destination to adjust for any new insertions and deletions
  89             old.to = c.insertions.shift(c.deletions.unshift(old.to));
  90             return false;
  91         });
  92         moves.erase(it, end(moves));
  93     }
  94
  95     // Ignore new moves of rows which were previously inserted (the implicit
  96     // delete from the move will remove the insert)
  97     if (!insertions.empty() && !c.moves.empty()) {
  98         c.moves.erase(std::remove_if(begin(c.moves), end(c.moves),
  99                               [&](auto const& m) { return insertions.contains(m.from); }),
 100                     end(c.moves));
 101     }
 102
 103     // Ensure that any previously modified rows which were moved are still modified
 104     if (!modifications.empty() && !c.moves.empty()) {
 105         for (auto const& move : c.moves) {
 106             for_each_col([&](auto& col, auto& other) {
 107                 if (col.contains(move.from))
 108                     other.add(move.to);
 109             });
 110         }
 111     }
 112
 113     // Update the source position of new moves to compensate for the changes made
 114     // in the old changeset
 115     if (!deletions.empty() || !insertions.empty()) {
 116         for (auto& move : c.moves)
 117             move.from = deletions.shift(insertions.unshift(move.from));
 118     }
 119
 120     moves.insert(end(moves), begin(c.moves), end(c.moves));
 121
 122     // New deletion indices have been shifted by the insertions, so unshift them
 123     // before adding
 124     deletions.add_shifted_by(insertions, c.deletions);
 125
 126     // Drop any inserted-then-deleted rows, then merge in new insertions
 127     insertions.erase_at(c.deletions);
 128     insertions.insert_at(c.insertions);
 129
 130     clean_up_stale_moves();
 131
 132     for_each_col([&](auto& col, auto& other) {
 133         col.erase_at(c.deletions);
 134         col.shift_for_insert_at(c.insertions);
 135         col.add(other);
 136     });
 137
 138     c = {};
 139     verify();
 140 }
 141
 142 void CollectionChangeBuilder::clean_up_stale_moves()
 143 {
 144     // Look for moves which are now no-ops, and remove them plus the associated
 145     // insert+delete. Note that this isn't just checking for from == to due to
 146     // that rows can also be shifted by other inserts and deletes
 147     moves.erase(std::remove_if(begin(moves), end(moves), [&](auto const& move) {
 148         if (move.from - deletions.count(0, move.from) != move.to - insertions.count(0, move.to))
 149             return false;
 150         deletions.remove(move.from);
 151         insertions.remove(move.to);
 152         return true;
 153     }), end(moves));
 154 }
 155
 156 void CollectionChangeBuilder::parse_complete()
 157 {
 158     moves.reserve(m_move_mapping.size());
 159     for (auto move : m_move_mapping) {
 160         REALM_ASSERT_DEBUG(deletions.contains(move.second));
 161         REALM_ASSERT_DEBUG(insertions.contains(move.first));
 162         if (move.first == move.second) {
 163             deletions.remove(move.second);
 164             insertions.remove(move.first);
 165         }
 166         else
 167             moves.push_back({move.second, move.first});
 168     }
 169     m_move_mapping.clear();
 170     std::sort(begin(moves), end(moves),
 171               [](auto const& a, auto const& b) { return a.from < b.from; });
 172 }
 173
 174 void CollectionChangeBuilder::modify(size_t ndx, size_t col)
 175 {
 176     modifications.add(ndx);
 177     if (!m_track_columns || col == IndexSet::npos)
 178         return;
 179
 180     if (col >= columns.size())
 181         columns.resize(col + 1);
 182     columns[col].add(ndx);
 183 }
 184
 185 template<typename Func>
 186 void CollectionChangeBuilder::for_each_col(Func&& f)
 187 {
 188     f(modifications);
 189     if (m_track_columns) {
 190         for (auto& col : columns)
 191             f(col);
 192     }
 193 }
 194
 195 void CollectionChangeBuilder::insert(size_t index, size_t count, bool track_moves)
 196 {
 197     REALM_ASSERT(count != 0);
 198
 199     for_each_col([=](auto& col) { col.shift_for_insert_at(index, count); });
 200     if (!track_moves)
 201         return;
 202
 203     insertions.insert_at(index, count);
 204
 205     for (auto& move : moves) {
 206         if (move.to >= index)
 207             move.to += count;
 208     }
 209
 210     if (m_move_mapping.empty())
 211         return;
 212
 213     // m_move_mapping is new_ndx -> old_ndx, so updating the keys requires
 214     // deleting and re-inserting at the new index
 215     std::vector<std::pair<size_t, size_t>> shifted;
 216     for (auto it = m_move_mapping.begin(); it != m_move_mapping.end(); ) {
 217         if (it->first >= index) {
 218             shifted.emplace_back(it->first + count, it->second);
 219             it = m_move_mapping.erase(it);
 220         }
 221         else {
 222             ++it;
 223         }
 224     }
 225     for (auto& pair : shifted)
 226         m_move_mapping.insert(pair);
 227 }
 228
 229 void CollectionChangeBuilder::erase(size_t index)
 230 {
 231     for_each_col([=](auto& col) { col.erase_at(index); });
 232     size_t unshifted = insertions.erase_or_unshift(index);
 233     if (unshifted != IndexSet::npos)
 234         deletions.add_shifted(unshifted);
 235
 236     for (size_t i = 0; i < moves.size(); ++i) {
 237         auto& move = moves[i];
 238         if (move.to == index) {
 239             moves.erase(moves.begin() + i);
 240             --i;
 241         }
 242         else if (move.to > index)
 243             --move.to;
 244     }
 245 }
 246
 247 void CollectionChangeBuilder::clear(size_t old_size)
 248 {
 249     if (old_size != std::numeric_limits<size_t>::max()) {
 250         for (auto range : deletions)
 251             old_size += range.second - range.first;
 252         for (auto range : insertions)
 253             old_size -= range.second - range.first;
 254     }
 255
 256     modifications.clear();
 257     insertions.clear();
 258     moves.clear();
 259     m_move_mapping.clear();
 260     columns.clear();
 261     deletions.set(old_size);
 262 }
 263
 264 void CollectionChangeBuilder::move(size_t from, size_t to)
 265 {
 266     REALM_ASSERT(from != to);
 267
 268     bool updated_existing_move = false;
 269     for (auto& move : moves) {
 270         if (move.to != from) {
 271             // Shift other moves if this row is moving from one side of them
 272             // to the other
 273             if (move.to >= to && move.to < from)
 274                 ++move.to;
 275             else if (move.to <= to && move.to > from)
 276                 --move.to;
 277             continue;
 278         }
 279         REALM_ASSERT(!updated_existing_move);
 280
 281         // Collapse A -> B, B -> C into a single A -> C move
 282         move.to = to;
 283         updated_existing_move = true;
 284
 285         insertions.erase_at(from);
 286         insertions.insert_at(to);
 287     }
 288
 289     if (!updated_existing_move) {
 290         auto shifted_from = insertions.erase_or_unshift(from);
 291         insertions.insert_at(to);
 292
 293         // Don't report deletions/moves for newly inserted rows
 294         if (shifted_from != IndexSet::npos) {
 295             shifted_from = deletions.add_shifted(shifted_from);
 296             moves.push_back({shifted_from, to});
 297         }
 298     }
 299
 300     for_each_col([=](auto& col) {
 301         bool modified = col.contains(from);
 302         col.erase_at(from);
 303
 304         if (modified)
 305             col.insert_at(to);
 306         else
 307             col.shift_for_insert_at(to);
 308     });
 309 }
 310
 311 void CollectionChangeBuilder::move_over(size_t row_ndx, size_t last_row, bool track_moves)
 312 {
 313     REALM_ASSERT(row_ndx <= last_row);
 314     REALM_ASSERT(insertions.empty() || prev(insertions.end())->second - 1 <= last_row);
 315     REALM_ASSERT(modifications.empty() || prev(modifications.end())->second - 1 <= last_row);
 316
 317     if (row_ndx == last_row) {
 318         if (track_moves) {
 319             auto shifted_from = insertions.erase_or_unshift(row_ndx);
 320             if (shifted_from != IndexSet::npos)
 321                 deletions.add_shifted(shifted_from);
 322             m_move_mapping.erase(row_ndx);
 323         }
 324         for_each_col([=](auto& col) { col.remove(row_ndx); });
 325         return;
 326     }
 327
 328     for_each_col([=](auto& col) {
 329         bool modified = col.contains(last_row);
 330         if (modified) {
 331             col.remove(last_row);
 332             col.add(row_ndx);
 333         }
 334         else
 335             col.remove(row_ndx);
 336     });
 337
 338     if (!track_moves)
 339         return;
 340
 341     bool row_is_insertion = insertions.contains(row_ndx);
 342     bool last_is_insertion = !insertions.empty() && prev(insertions.end())->second == last_row + 1;
 343     REALM_ASSERT_DEBUG(insertions.empty() || prev(insertions.end())->second <= last_row + 1);
 344
 345     // Collapse A -> B, B -> C into a single A -> C move
 346     bool last_was_already_moved = false;
 347     if (last_is_insertion) {
 348         auto it = m_move_mapping.find(last_row);
 349         if (it != m_move_mapping.end() && it->first == last_row) {
 350             m_move_mapping[row_ndx] = it->second;
 351             m_move_mapping.erase(it);
 352             last_was_already_moved = true;
 353         }
 354     }
 355
 356     // Remove moves to the row being deleted
 357     if (row_is_insertion && !last_was_already_moved) {
 358         auto it = m_move_mapping.find(row_ndx);
 359         if (it != m_move_mapping.end() && it->first == row_ndx)
 360             m_move_mapping.erase(it);
 361     }
 362
 363     // Don't report deletions/moves if last_row is newly inserted
 364     if (last_is_insertion) {
 365         insertions.remove(last_row);
 366     }
 367     // If it was previously moved, the unshifted source row has already been marked as deleted
 368     else if (!last_was_already_moved) {
 369         auto shifted_last_row = insertions.unshift(last_row);
 370         shifted_last_row = deletions.add_shifted(shifted_last_row);
 371         m_move_mapping[row_ndx] = shifted_last_row;
 372     }
 373
 374     // Don't mark the moved-over row as deleted if it was a new insertion
 375     if (!row_is_insertion) {
 376         deletions.add_shifted(insertions.unshift(row_ndx));
 377         insertions.add(row_ndx);
 378     }
 379     verify();
 380 }
 381
 382 void CollectionChangeBuilder::swap(size_t ndx_1, size_t ndx_2, bool track_moves)
 383 {
 384     REALM_ASSERT(ndx_1 != ndx_2);
 385     // The order of the two indices doesn't matter semantically, but making them
 386     // consistent simplifies the logic
 387     if (ndx_1 > ndx_2)
 388         std::swap(ndx_1, ndx_2);
 389
 390     for_each_col([=](auto& col) {
 391         bool row_1_modified = col.contains(ndx_1);
 392         bool row_2_modified = col.contains(ndx_2);
 393         if (row_1_modified != row_2_modified) {
 394             if (row_1_modified) {
 395                 col.remove(ndx_1);
 396                 col.add(ndx_2);
 397             }
 398             else {
 399                 col.remove(ndx_2);
 400                 col.add(ndx_1);
 401             }
 402         }
 403     });
 404
 405     if (!track_moves)
 406         return;
 407
 408     auto update_move = [&](auto existing_it, auto ndx_1, auto ndx_2) {
 409         // update the existing move to ndx_2 to point at ndx_1
 410         auto original = existing_it->second;
 411         m_move_mapping.erase(existing_it);
 412         m_move_mapping[ndx_1] = original;
 413
 414         // add a move from 1 -> 2 unless 1 was a new insertion
 415         if (!insertions.contains(ndx_1)) {
 416             m_move_mapping[ndx_2] = deletions.add_shifted(insertions.unshift(ndx_1));
 417             insertions.add(ndx_1);
 418         }
 419         REALM_ASSERT_DEBUG(insertions.contains(ndx_2));
 420     };
 421
 422     auto move_1 = m_move_mapping.find(ndx_1);
 423     auto move_2 = m_move_mapping.find(ndx_2);
 424     bool have_move_1 = move_1 != end(m_move_mapping) && move_1->first == ndx_1;
 425     bool have_move_2 = move_2 != end(m_move_mapping) && move_2->first == ndx_2;
 426     if (have_move_1 && have_move_2) {
 427         // both are already moves, so just swap the destinations
 428         std::swap(move_1->second, move_2->second);
 429     }
 430     else if (have_move_1) {
 431         update_move(move_1, ndx_2, ndx_1);
 432     }
 433     else if (have_move_2) {
 434         update_move(move_2, ndx_1, ndx_2);
 435     }
 436     else {
 437         // ndx_2 needs to be done before 1 to avoid incorrect shifting
 438         if (!insertions.contains(ndx_2)) {
 439             m_move_mapping[ndx_1] = deletions.add_shifted(insertions.unshift(ndx_2));
 440             insertions.add(ndx_2);
 441         }
 442         if (!insertions.contains(ndx_1)) {
 443             m_move_mapping[ndx_2] = deletions.add_shifted(insertions.unshift(ndx_1));
 444             insertions.add(ndx_1);
 445         }
 446     }
 447 }
 448
 449 void CollectionChangeBuilder::subsume(size_t old_ndx, size_t new_ndx, bool track_moves)
 450 {
 451     REALM_ASSERT(old_ndx != new_ndx);
 452
 453     for_each_col([=](auto& col) {
 454         if (col.contains(old_ndx)) {
 455             col.add(new_ndx);
 456         }
 457     });
 458
 459     if (!track_moves)
 460         return;
 461
 462     REALM_ASSERT_DEBUG(insertions.contains(new_ndx));
 463     REALM_ASSERT_DEBUG(!m_move_mapping.count(new_ndx));
 464
 465     // If the source row was already moved, update the existing move
 466     auto it = m_move_mapping.find(old_ndx);
 467     if (it != m_move_mapping.end() && it->first == old_ndx) {
 468         m_move_mapping[new_ndx] = it->second;
 469         m_move_mapping.erase(it);
 470     }
 471     // otherwise add a new move unless it was a new insertion
 472     else if (!insertions.contains(old_ndx)) {
 473         m_move_mapping[new_ndx] = deletions.shift(insertions.unshift(old_ndx));
 474     }
 475
 476     verify();
 477 }
 478
 479 void CollectionChangeBuilder::verify()
 480 {
 481 #ifdef REALM_DEBUG
 482     for (auto&& move : moves) {
 483         REALM_ASSERT(deletions.contains(move.from));
 484         REALM_ASSERT(insertions.contains(move.to));
 485     }
 486 #endif
 487 }
 488
 489 void CollectionChangeBuilder::insert_column(size_t ndx)
 490 {
 491     if (ndx < columns.size())
 492         columns.insert(columns.begin() + ndx, IndexSet{});
 493 }
 494
 495 void CollectionChangeBuilder::move_column(size_t from, size_t to)
 496 {
 497     if (from >= columns.size() && to >= columns.size())
 498         return;
 499     if (from >= columns.size() || to >= columns.size())
 500         columns.resize(std::max(from, to) + 1);
 501     if (from < to)
 502         std::rotate(begin(columns) + from, begin(columns) + from + 1, begin(columns) + to + 1);
 503     else
 504         std::rotate(begin(columns) + to, begin(columns) + from, begin(columns) + from + 1);
 505 }
 506
 507 namespace {
 508 struct RowInfo {
 509     size_t row_index;
 510     size_t prev_tv_index;
 511     size_t tv_index;
 512     size_t shifted_tv_index;
 513 };
 514
 515 // Calculates the insertions/deletions required for a query on a table without
 516 // a sort, where `removed` includes the rows which were modified to no longer
 517 // match the query (but not outright deleted rows, which are filtered out long
 518 // before any of this logic), and `move_candidates` tracks the rows which may
 519 // be the result of a move.
 520 //
 521 // This function is not strictly required, as calculate_moves_sorted() will
 522 // produce correct results even for the scenarios where this function is used.
 523 // However, this function has asymptotically better worst-case performance and
 524 // extremely cheap best-case performance, and is guaranteed to produce a minimal
 525 // diff when the only row moves are due to move_last_over().
 526 void calculate_moves_unsorted(std::vector<RowInfo>& new_rows, IndexSet& removed,
 527                               IndexSet const& move_candidates,
 528                               CollectionChangeSet& changeset)
 529 {
 530     // Here we track which row we expect to see, which in the absence of swap()
 531     // is always the row immediately after the last row which was not moved.
 532     size_t expected = 0;
 533     for (auto& row : new_rows) {
 534         if (row.shifted_tv_index == expected) {
 535             ++expected;
 536             continue;
 537         }
 538
 539         // We didn't find the row we were expecting to find, which means that
 540         // either a row was moved forward to here, the row we were expecting was
 541         // removed, or the row we were expecting moved back.
 542
 543         // First check if this row even could have moved. If it can't, just
 544         // treat it as a match and move on, and we'll handle the row we were
 545         // expecting when we hit it later.
 546         if (!move_candidates.contains(row.row_index)) {
 547             expected = row.shifted_tv_index + 1;
 548             continue;
 549         }
 550
 551         // Next calculate where we expect this row to be based on the insertions
 552         // and removals (i.e. rows changed to not match the query), as it could
 553         // be that the row actually ends up in this spot due to the rows before
 554         // it being removed.
 555         size_t calc_expected = row.tv_index - changeset.insertions.count(0, row.tv_index) + removed.count(0, row.prev_tv_index);
 556         if (row.shifted_tv_index == calc_expected) {
 557             expected = calc_expected + 1;
 558             continue;
 559         }
 560
 561         // The row still isn't the expected one, so record it as a move
 562         changeset.moves.push_back({row.prev_tv_index, row.tv_index});
 563         changeset.insertions.add(row.tv_index);
 564         removed.add(row.prev_tv_index);
 565     }
 566 }
 567
 568 class LongestCommonSubsequenceCalculator {
 569 public:
 570     // A pair of an index in the table and an index in the table view
 571     struct Row {
 572         size_t row_index;
 573         size_t tv_index;
 574     };
 575
 576     struct Match {
 577         // The index in `a` at which this match begins
 578         size_t i;
 579         // The index in `b` at which this match begins
 580         size_t j;
 581         // The length of this match
 582         size_t size;
 583         // The number of rows in this block which were modified
 584         size_t modified;
 585     };
 586     std::vector<Match> m_longest_matches;
 587
 588     LongestCommonSubsequenceCalculator(std::vector<Row>& a, std::vector<Row>& b,
 589                                        size_t start_index,
 590                                        IndexSet const& modifications)
 591     : m_modified(modifications)
 592     , a(a), b(b)
 593     {
 594         find_longest_matches(start_index, a.size(),
 595                              start_index, b.size());
 596         m_longest_matches.push_back({a.size(), b.size(), 0});
 597     }
 598
 599 private:
 600     IndexSet const& m_modified;
 601
 602     // The two arrays of rows being diffed
 603     // a is sorted by tv_index, b is sorted by row_index
 604     std::vector<Row> &a, &b;
 605
 606     // Find the longest matching range in (a + begin1, a + end1) and (b + begin2, b + end2)
 607     // "Matching" is defined as "has the same row index"; the TV index is just
 608     // there to let us turn an index in a/b into an index which can be reported
 609     // in the output changeset.
 610     //
 611     // This is done with the O(N) space variant of the dynamic programming
 612     // algorithm for longest common subsequence, where N is the maximum number
 613     // of the most common row index (which for everything but linkview-derived
 614     // TVs will be 1).
 615     Match find_longest_match(size_t begin1, size_t end1, size_t begin2, size_t end2)
 616     {
 617         struct Length {
 618             size_t j, len;
 619         };
 620         // The length of the matching block for each `j` for the previously checked row
 621         std::vector<Length> prev;
 622         // The length of the matching block for each `j` for the row currently being checked
 623         std::vector<Length> cur;
 624
 625         // Calculate the length of the matching block *ending* at b[j], which
 626         // is 1 if b[j - 1] did not match, and b[j - 1] + 1 otherwise.
 627         auto length = [&](size_t j) -> size_t {
 628             for (auto const& pair : prev) {
 629                 if (pair.j + 1 == j)
 630                     return pair.len + 1;
 631             }
 632             return 1;
 633         };
 634
 635         // Iterate over each `j` which has the same row index as a[i] and falls
 636         // within the range begin2 <= j < end2
 637         auto for_each_b_match = [&](size_t i, auto&& f) {
 638             size_t ai = a[i].row_index;
 639             // Find the TV indicies at which this row appears in the new results
 640             // There should always be at least one (or it would have been
 641             // filtered out earlier), but there can be multiple if there are dupes
 642             auto it = lower_bound(begin(b), end(b), ai,
 643                                   [](auto lft, auto rgt) { return lft.row_index < rgt; });
 644             REALM_ASSERT(it != end(b) && it->row_index == ai);
 645             for (; it != end(b) && it->row_index == ai; ++it) {
 646                 size_t j = it->tv_index;
 647                 if (j < begin2)
 648                     continue;
 649                 if (j >= end2)
 650                     break; // b is sorted by tv_index so this can't transition from false to true
 651                 f(j);
 652             }
 653         };
 654
 655         Match best = {begin1, begin2, 0, 0};
 656         for (size_t i = begin1; i < end1; ++i) {
 657             // prev = std::move(cur), but avoids discarding prev's heap allocation
 658             cur.swap(prev);
 659             cur.clear();
 660
 661             for_each_b_match(i, [&](size_t j) {
 662                 size_t size = length(j);
 663
 664                 cur.push_back({j, size});
 665
 666                 // If the matching block ending at a[i] and b[j] is longer than
 667                 // the previous one, select it as the best
 668                 if (size > best.size)
 669                     best = {i - size + 1, j - size + 1, size, IndexSet::npos};
 670                 // Given two equal-length matches, prefer the one with fewer modified rows
 671                 else if (size == best.size) {
 672                     if (best.modified == IndexSet::npos)
 673                         best.modified = m_modified.count(best.j - size + 1, best.j + 1);
 674                     auto count = m_modified.count(j - size + 1, j + 1);
 675                     if (count < best.modified)
 676                         best = {i - size + 1, j - size + 1, size, count};
 677                 }
 678
 679                 // The best block should always fall within the range being searched
 680                 REALM_ASSERT(best.i >= begin1 && best.i + best.size <= end1);
 681                 REALM_ASSERT(best.j >= begin2 && best.j + best.size <= end2);
 682             });
 683         }
 684         return best;
 685     }
 686
 687     void find_longest_matches(size_t begin1, size_t end1, size_t begin2, size_t end2)
 688     {
 689         // FIXME: recursion could get too deep here
 690         // recursion depth worst case is currently O(N) and each recursion uses 320 bytes of stack
 691         // could reduce worst case to O(sqrt(N)) (and typical case to O(log N))
 692         // biasing equal selections towards the middle, but that's still
 693         // insufficient for Android's 8 KB stacks
 694         auto m = find_longest_match(begin1, end1, begin2, end2);
 695         if (!m.size)
 696             return;
 697         if (m.i > begin1 && m.j > begin2)
 698             find_longest_matches(begin1, m.i, begin2, m.j);
 699         m_longest_matches.push_back(m);
 700         if (m.i + m.size < end2 && m.j + m.size < end2)
 701             find_longest_matches(m.i + m.size, end1, m.j + m.size, end2);
 702     }
 703 };
 704
 705 void calculate_moves_sorted(std::vector<RowInfo>& rows, CollectionChangeSet& changeset)
 706 {
 707     // The RowInfo array contains information about the old and new TV indices of
 708     // each row, which we need to turn into two sequences of rows, which we'll
 709     // then find matches in
 710     std::vector<LongestCommonSubsequenceCalculator::Row> a, b;
 711
 712     a.reserve(rows.size());
 713     for (auto& row : rows) {
 714         a.push_back({row.row_index, row.prev_tv_index});
 715     }
 716     std::sort(begin(a), end(a), [](auto lft, auto rgt) {
 717         return std::tie(lft.tv_index, lft.row_index) < std::tie(rgt.tv_index, rgt.row_index);
 718     });
 719
 720     // Before constructing `b`, first find the first index in `a` which will
 721     // actually differ in `b`, and skip everything else if there aren't any
 722     size_t first_difference = IndexSet::npos;
 723     for (size_t i = 0; i < a.size(); ++i) {
 724         if (a[i].row_index != rows[i].row_index) {
 725             first_difference = i;
 726             break;
 727         }
 728     }
 729     if (first_difference == IndexSet::npos)
 730         return;
 731
 732     // Note that `b` is sorted by row_index, while `a` is sorted by tv_index
 733     b.reserve(rows.size());
 734     for (size_t i = 0; i < rows.size(); ++i)
 735         b.push_back({rows[i].row_index, i});
 736     std::sort(begin(b), end(b), [](auto lft, auto rgt) {
 737         return std::tie(lft.row_index, lft.tv_index) < std::tie(rgt.row_index, rgt.tv_index);
 738     });
 739
 740     // Calculate the LCS of the two sequences
 741     auto matches = LongestCommonSubsequenceCalculator(a, b, first_difference,
 742                                                       changeset.modifications).m_longest_matches;
 743
 744     // And then insert and delete rows as needed to align them
 745     size_t i = first_difference, j = first_difference;
 746     for (auto match : matches) {
 747         for (; i < match.i; ++i)
 748             changeset.deletions.add(a[i].tv_index);
 749         for (; j < match.j; ++j)
 750             changeset.insertions.add(rows[j].tv_index);
 751         i += match.size;
 752         j += match.size;
 753     }
 754 }
 755
 756 } // Anonymous namespace
 757
 758 CollectionChangeBuilder CollectionChangeBuilder::calculate(std::vector<size_t> const& prev_rows,
 759                                                            std::vector<size_t> const& next_rows,
 760                                                            std::function<bool (size_t)> row_did_change,
 761                                                            util::Optional<IndexSet> const& move_candidates)
 762 {
 763     REALM_ASSERT_DEBUG(!move_candidates || std::is_sorted(begin(next_rows), end(next_rows)));
 764
 765     CollectionChangeBuilder ret;
 766
 767     size_t deleted = 0;
 768     std::vector<RowInfo> old_rows;
 769     old_rows.reserve(prev_rows.size());
 770     for (size_t i = 0; i < prev_rows.size(); ++i) {
 771         if (prev_rows[i] == IndexSet::npos) {
 772             ++deleted;
 773             ret.deletions.add(i);
 774         }
 775         else
 776             old_rows.push_back({prev_rows[i], IndexSet::npos, i, i - deleted});
 777     }
 778     std::sort(begin(old_rows), end(old_rows), [](auto& lft, auto& rgt) {
 779         return lft.row_index < rgt.row_index;
 780     });
 781
 782     std::vector<RowInfo> new_rows;
 783     new_rows.reserve(next_rows.size());
 784     for (size_t i = 0; i < next_rows.size(); ++i) {
 785         new_rows.push_back({next_rows[i], IndexSet::npos, i, 0});
 786     }
 787     std::sort(begin(new_rows), end(new_rows), [](auto& lft, auto& rgt) {
 788         return lft.row_index < rgt.row_index;
 789     });
 790
 791     // Don't add rows which were modified to not match the query to `deletions`
 792     // immediately because the unsorted move logic needs to be able to
 793     // distinguish them from rows which were outright deleted
 794     IndexSet removed;
 795
 796     // Now that our old and new sets of rows are sorted by row index, we can
 797     // iterate over them and either record old+new TV indices for rows present
 798     // in both, or mark them as inserted/deleted if they appear only in one
 799     size_t i = 0, j = 0;
 800     while (i < old_rows.size() && j < new_rows.size()) {
 801         auto old_index = old_rows[i];
 802         auto new_index = new_rows[j];
 803         if (old_index.row_index == new_index.row_index) {
 804             new_rows[j].prev_tv_index = old_rows[i].tv_index;
 805             new_rows[j].shifted_tv_index = old_rows[i].shifted_tv_index;
 806             ++i;
 807             ++j;
 808         }
 809         else if (old_index.row_index < new_index.row_index) {
 810             removed.add(old_index.tv_index);
 811             ++i;
 812         }
 813         else {
 814             ret.insertions.add(new_index.tv_index);
 815             ++j;
 816         }
 817     }
 818
 819     for (; i < old_rows.size(); ++i)
 820         removed.add(old_rows[i].tv_index);
 821     for (; j < new_rows.size(); ++j)
 822         ret.insertions.add(new_rows[j].tv_index);
 823
 824     // Filter out the new insertions since we don't need them for any of the
 825     // further calculations
 826     new_rows.erase(std::remove_if(begin(new_rows), end(new_rows),
 827                                   [](auto& row) { return row.prev_tv_index == IndexSet::npos; }),
 828                    end(new_rows));
 829     std::sort(begin(new_rows), end(new_rows),
 830               [](auto& lft, auto& rgt) { return lft.tv_index < rgt.tv_index; });
 831
 832     for (auto& row : new_rows) {
 833         if (row_did_change(row.row_index)) {
 834             ret.modifications.add(row.tv_index);
 835         }
 836     }
 837
 838     if (move_candidates) {
 839         calculate_moves_unsorted(new_rows, removed, *move_candidates, ret);
 840     }
 841     else {
 842         calculate_moves_sorted(new_rows, ret);
 843     }
 844     ret.deletions.add(removed);
 845     ret.verify();
 846
 847 #ifdef REALM_DEBUG
 848     { // Verify that applying the calculated change to prev_rows actually produces next_rows
 849         auto rows = prev_rows;
 850         auto it = util::make_reverse_iterator(ret.deletions.end());
 851         auto end = util::make_reverse_iterator(ret.deletions.begin());
 852         for (; it != end; ++it) {
 853             rows.erase(rows.begin() + it->first, rows.begin() + it->second);
 854         }
 855
 856         for (auto i : ret.insertions.as_indexes()) {
 857             rows.insert(rows.begin() + i, next_rows[i]);
 858         }
 859
 860         REALM_ASSERT(rows == next_rows);
 861     }
 862 #endif
 863
 864     return ret;
 865 }
 866
 867 CollectionChangeSet CollectionChangeBuilder::finalize() &&
 868 {
 869     // Calculate which indices in the old collection were modified
 870     auto modifications_in_old = modifications;
 871     modifications_in_old.erase_at(insertions);
 872     modifications_in_old.shift_for_insert_at(deletions);
 873
 874     // During changeset calculation we allow marking a row as both inserted and
 875     // modified in case changeset merging results in it no longer being an insert,
 876     // but we don't want inserts in the final modification set
 877     modifications.remove(insertions);
 878
 879     return {
 880         std::move(deletions),
 881         std::move(insertions),
 882         std::move(modifications_in_old),
 883         std::move(modifications),
 884         std::move(moves),
 885         std::move(columns)
 886     };
 887 }