in ReactCommon/react/renderer/mounting/Differentiator.cpp [1084:1598]
static void calculateShadowViewMutationsV2(
BREADCRUMB_TYPE breadcrumb,
ViewNodePairScope &scope,
ShadowViewMutation::List &mutations,
ShadowView const &parentShadowView,
ShadowViewNodePair::NonOwningList &&oldChildPairs,
ShadowViewNodePair::NonOwningList &&newChildPairs) {
if (oldChildPairs.empty() && newChildPairs.empty()) {
return;
}
size_t index = 0;
// Lists of mutations
auto mutationContainer = OrderedMutationInstructionContainer{};
DEBUG_LOGS({
LOG(ERROR) << "Differ Entry: Child Pairs of node: [" << parentShadowView.tag
<< "]";
std::string strOldChildPairs;
for (size_t oldIndex = 0; oldIndex < oldChildPairs.size(); oldIndex++) {
strOldChildPairs.append(
std::to_string(oldChildPairs[oldIndex]->shadowView.tag));
strOldChildPairs.append(
oldChildPairs[oldIndex]->isConcreteView ? "" : "'");
strOldChildPairs.append(oldChildPairs[oldIndex]->flattened ? "*" : "");
strOldChildPairs.append(", ");
}
std::string strNewChildPairs;
for (size_t newIndex = 0; newIndex < newChildPairs.size(); newIndex++) {
strNewChildPairs.append(
std::to_string(newChildPairs[newIndex]->shadowView.tag));
strNewChildPairs.append(
newChildPairs[newIndex]->isConcreteView ? "" : "'");
strNewChildPairs.append(newChildPairs[newIndex]->flattened ? "*" : "");
strNewChildPairs.append(", ");
}
LOG(ERROR) << "Differ Entry: Old Child Pairs: " << strOldChildPairs;
LOG(ERROR) << "Differ Entry: New Child Pairs: " << strNewChildPairs;
});
// Stage 1: Collecting `Update` mutations
for (index = 0; index < oldChildPairs.size() && index < newChildPairs.size();
index++) {
auto &oldChildPair = *oldChildPairs[index];
auto &newChildPair = *newChildPairs[index];
if (oldChildPair.shadowView.tag != newChildPair.shadowView.tag) {
DEBUG_LOGS({
LOG(ERROR) << "Differ Branch 1.1: Tags Different: ["
<< oldChildPair.shadowView.tag << "] ["
<< newChildPair.shadowView.tag << "]"
<< " with parent: [" << parentShadowView.tag << "]";
});
// Totally different nodes, updating is impossible.
break;
}
// If either view was flattened, and that has changed this frame, don't
// try to update
if (oldChildPair.flattened != newChildPair.flattened ||
oldChildPair.isConcreteView != newChildPair.isConcreteView) {
break;
}
DEBUG_LOGS({
LOG(ERROR) << "Differ Branch 1.2: Same tags, update and recurse: ["
<< oldChildPair.shadowView.tag << "]"
<< (oldChildPair.flattened ? " (flattened)" : "")
<< (oldChildPair.isConcreteView ? " (concrete)" : "") << "["
<< newChildPair.shadowView.tag << "]"
<< (newChildPair.flattened ? " (flattened)" : "")
<< (newChildPair.isConcreteView ? " (concrete)" : "")
<< " with parent: [" << parentShadowView.tag << "]";
});
if (newChildPair.isConcreteView &&
oldChildPair.shadowView != newChildPair.shadowView) {
mutationContainer.updateMutations.push_back(
ShadowViewMutation::UpdateMutation(
oldChildPair.shadowView, newChildPair.shadowView));
}
// Recursively update tree if ShadowNode pointers are not equal
if (!oldChildPair.flattened &&
oldChildPair.shadowNode != newChildPair.shadowNode) {
ViewNodePairScope innerScope{};
auto oldGrandChildPairs = sliceChildShadowNodeViewPairsFromViewNodePair(
oldChildPair, innerScope);
auto newGrandChildPairs = sliceChildShadowNodeViewPairsFromViewNodePair(
newChildPair, innerScope);
calculateShadowViewMutationsV2(
DIFF_BREADCRUMB(
"Stage 1: Recurse on " +
std::to_string(oldChildPair.shadowView.tag)),
innerScope,
*(newGrandChildPairs.size()
? &mutationContainer.downwardMutations
: &mutationContainer.destructiveDownwardMutations),
oldChildPair.shadowView,
std::move(oldGrandChildPairs),
std::move(newGrandChildPairs));
}
}
size_t lastIndexAfterFirstStage = index;
if (index == newChildPairs.size()) {
// We've reached the end of the new children. We can delete+remove the
// rest.
for (; index < oldChildPairs.size(); index++) {
auto const &oldChildPair = *oldChildPairs[index];
DEBUG_LOGS({
LOG(ERROR) << "Differ Branch 2: Deleting Tag/Tree: ["
<< oldChildPair.shadowView.tag << "]"
<< " with parent: [" << parentShadowView.tag << "]";
});
if (!oldChildPair.isConcreteView) {
continue;
}
mutationContainer.deleteMutations.push_back(
ShadowViewMutation::DeleteMutation(oldChildPair.shadowView));
mutationContainer.removeMutations.push_back(
ShadowViewMutation::RemoveMutation(
parentShadowView,
oldChildPair.shadowView,
static_cast<int>(oldChildPair.mountIndex)));
// We also have to call the algorithm recursively to clean up the entire
// subtree starting from the removed view.
ViewNodePairScope innerScope{};
calculateShadowViewMutationsV2(
DIFF_BREADCRUMB(
"Trivial delete " + std::to_string(oldChildPair.shadowView.tag)),
innerScope,
mutationContainer.destructiveDownwardMutations,
oldChildPair.shadowView,
sliceChildShadowNodeViewPairsFromViewNodePair(
oldChildPair, innerScope),
{});
}
} else if (index == oldChildPairs.size()) {
// If we don't have any more existing children we can choose a fast path
// since the rest will all be create+insert.
for (; index < newChildPairs.size(); index++) {
auto const &newChildPair = *newChildPairs[index];
DEBUG_LOGS({
LOG(ERROR) << "Differ Branch 3: Creating Tag/Tree: ["
<< newChildPair.shadowView.tag << "]"
<< " with parent: [" << parentShadowView.tag << "]";
});
if (!newChildPair.isConcreteView) {
continue;
}
mutationContainer.insertMutations.push_back(
ShadowViewMutation::InsertMutation(
parentShadowView,
newChildPair.shadowView,
static_cast<int>(newChildPair.mountIndex)));
mutationContainer.createMutations.push_back(
ShadowViewMutation::CreateMutation(newChildPair.shadowView));
ViewNodePairScope innerScope{};
calculateShadowViewMutationsV2(
DIFF_BREADCRUMB(
"Trivial create " + std::to_string(newChildPair.shadowView.tag)),
innerScope,
mutationContainer.downwardMutations,
newChildPair.shadowView,
{},
sliceChildShadowNodeViewPairsFromViewNodePair(
newChildPair, innerScope));
}
} else {
// Collect map of tags in the new list
auto newRemainingPairs = TinyMap<Tag, ShadowViewNodePair *>{};
auto newInsertedPairs = TinyMap<Tag, ShadowViewNodePair *>{};
auto deletionCandidatePairs = TinyMap<Tag, ShadowViewNodePair const *>{};
for (; index < newChildPairs.size(); index++) {
auto &newChildPair = *newChildPairs[index];
newRemainingPairs.insert({newChildPair.shadowView.tag, &newChildPair});
}
// Walk through both lists at the same time
// We will perform updates, create+insert, remove+delete, remove+insert
// (move) here.
size_t oldIndex = lastIndexAfterFirstStage,
newIndex = lastIndexAfterFirstStage, newSize = newChildPairs.size(),
oldSize = oldChildPairs.size();
while (newIndex < newSize || oldIndex < oldSize) {
bool haveNewPair = newIndex < newSize;
bool haveOldPair = oldIndex < oldSize;
// Advance both pointers if pointing to the same element
if (haveNewPair && haveOldPair) {
auto const &oldChildPair = *oldChildPairs[oldIndex];
auto const &newChildPair = *newChildPairs[newIndex];
Tag newTag = newChildPair.shadowView.tag;
Tag oldTag = oldChildPair.shadowView.tag;
if (newTag == oldTag) {
DEBUG_LOGS({
LOG(ERROR) << "Differ Branch 5: Matched Tags at indices: "
<< oldIndex << " " << newIndex << ": ["
<< oldChildPair.shadowView.tag << "]"
<< (oldChildPair.flattened ? "(flattened)" : "")
<< (oldChildPair.isConcreteView ? "(concrete)" : "")
<< " [" << newChildPair.shadowView.tag << "]"
<< (newChildPair.flattened ? "(flattened)" : "")
<< (newChildPair.isConcreteView ? "(concrete)" : "")
<< " with parent: [" << parentShadowView.tag << "]";
});
updateMatchedPair(
DIFF_BREADCRUMB(
"Update Matched Pairs (1): " +
std::to_string(oldChildPair.shadowView.tag)),
mutationContainer,
true,
true,
parentShadowView,
oldChildPair,
newChildPair);
updateMatchedPairSubtrees(
DIFF_BREADCRUMB(
"Update Matched Pair Subtrees (1): " +
std::to_string(oldChildPair.shadowView.tag)),
scope,
mutationContainer,
newRemainingPairs,
oldChildPairs,
newChildPairs,
parentShadowView,
oldChildPair,
newChildPair);
newIndex++;
oldIndex++;
continue;
}
}
// We have an old pair, but we either don't have any remaining new pairs
// or we have one but it's not matched up with the old pair
if (haveOldPair) {
auto const &oldChildPair = *oldChildPairs[oldIndex];
Tag oldTag = oldChildPair.shadowView.tag;
// Was oldTag already inserted? This indicates a reordering, not just
// a move. The new node has already been inserted, we just need to
// remove the node from its old position now, and update the node's
// subtree.
auto const insertedIt = newInsertedPairs.find(oldTag);
if (insertedIt != newInsertedPairs.end()) {
auto const &newChildPair = *insertedIt->second;
updateMatchedPair(
DIFF_BREADCRUMB(
"Update Matched Pairs (2): " +
std::to_string(oldChildPair.shadowView.tag)),
mutationContainer,
true,
false,
parentShadowView,
oldChildPair,
newChildPair);
updateMatchedPairSubtrees(
DIFF_BREADCRUMB(
"Update Matched Pair Subtrees (2): " +
std::to_string(oldChildPair.shadowView.tag)),
scope,
mutationContainer,
newRemainingPairs,
oldChildPairs,
newChildPairs,
parentShadowView,
oldChildPair,
newChildPair);
newInsertedPairs.erase(insertedIt);
oldIndex++;
continue;
}
// Should we generate a delete+remove instruction for the old node?
// If there's an old node and it's not found in the "new" list, we
// generate remove+delete for this node and its subtree.
auto const newIt = newRemainingPairs.find(oldTag);
if (newIt == newRemainingPairs.end()) {
oldIndex++;
if (!oldChildPair.isConcreteView) {
continue;
}
// From here, we know the oldChildPair is concrete.
// We *probably* need to generate a REMOVE mutation (see edge-case
// notes below).
DEBUG_LOGS({
LOG(ERROR)
<< "Differ Branch 9: Removing tag that was not reinserted: "
<< oldIndex << ": [" << oldChildPair.shadowView.tag << "]"
<< (oldChildPair.flattened ? " (flattened)" : "")
<< (oldChildPair.isConcreteView ? " (concrete)" : "")
<< " with parent: [" << parentShadowView.tag << "] "
<< "node is in other tree? "
<< (oldChildPair.inOtherTree() ? "yes" : "no");
});
// Edge case: node is not found in `newRemainingPairs`, due to
// complex (un)flattening cases, but exists in other tree *and* is
// concrete.
if (oldChildPair.inOtherTree() &&
oldChildPair.otherTreePair->isConcreteView) {
ShadowView const &otherTreeView =
oldChildPair.otherTreePair->shadowView;
// Remove, but remove using the *new* node, since we know
// an UPDATE mutation from old -> new has been generated.
// Practically this shouldn't matter for most mounting layer
// implementations, but helps adhere to the invariant that
// for all mutation instructions, "oldViewShadowNode" == "current
// node on mounting layer / stubView".
// Here we do *not" need to generate a potential DELETE mutation
// because we know the view is concrete, and still in the new
// hierarchy.
mutationContainer.removeMutations.push_back(
ShadowViewMutation::RemoveMutation(
parentShadowView,
otherTreeView,
static_cast<int>(oldChildPair.mountIndex)));
continue;
}
mutationContainer.removeMutations.push_back(
ShadowViewMutation::RemoveMutation(
parentShadowView,
oldChildPair.shadowView,
static_cast<int>(oldChildPair.mountIndex)));
deletionCandidatePairs.insert(
{oldChildPair.shadowView.tag, &oldChildPair});
continue;
}
}
// At this point, oldTag is -1 or is in the new list, and hasn't been
// inserted or matched yet. We're not sure yet if the new node is in the
// old list - generate an insert instruction for the new node.
auto &newChildPair = *newChildPairs[newIndex];
DEBUG_LOGS({
LOG(ERROR)
<< "Differ Branch 10: Inserting tag/tree that was not (yet?) removed from hierarchy: "
<< newIndex << "/" << newSize << ": ["
<< newChildPair.shadowView.tag << "]"
<< (newChildPair.flattened ? " (flattened)" : "")
<< (newChildPair.isConcreteView ? " (concrete)" : "")
<< " with parent: [" << parentShadowView.tag << "]";
});
if (newChildPair.isConcreteView) {
mutationContainer.insertMutations.push_back(
ShadowViewMutation::InsertMutation(
parentShadowView,
newChildPair.shadowView,
static_cast<int>(newChildPair.mountIndex)));
}
// `inOtherTree` is only set to true during flattening/unflattening of
// parent. If the parent isn't (un)flattened, this will always be
// `false`, even if the node is in the other (old) tree. In this case,
// we expect the node to be removed from `newInsertedPairs` when we
// later encounter it in this loop.
if (!newChildPair.inOtherTree()) {
newInsertedPairs.insert({newChildPair.shadowView.tag, &newChildPair});
}
newIndex++;
}
// Penultimate step: generate Delete instructions for entirely deleted
// subtrees/nodes. We do this here because we need to traverse the entire
// list to make sure that a node was not reparented into an unflattened
// node that occurs *after* it in the hierarchy, due to zIndex ordering.
for (auto it = deletionCandidatePairs.begin();
it != deletionCandidatePairs.end();
it++) {
if (it->first == 0) {
continue;
}
auto const &oldChildPair = *it->second;
DEBUG_LOGS({
LOG(ERROR)
<< "Differ Branch 11: Deleting tag/tree that was not in new hierarchy: "
<< "[" << oldChildPair.shadowView.tag << "]"
<< (oldChildPair.flattened ? "(flattened)" : "")
<< (oldChildPair.isConcreteView ? "(concrete)" : "")
<< (oldChildPair.inOtherTree() ? "(in other tree)" : "")
<< " with parent: [" << parentShadowView.tag << "] ##"
<< std::hash<ShadowView>{}(oldChildPair.shadowView);
});
// This can happen when the parent is unflattened
if (!oldChildPair.inOtherTree() && oldChildPair.isConcreteView) {
mutationContainer.deleteMutations.push_back(
ShadowViewMutation::DeleteMutation(oldChildPair.shadowView));
// We also have to call the algorithm recursively to clean up the
// entire subtree starting from the removed view.
ViewNodePairScope innerScope{};
calculateShadowViewMutationsV2(
DIFF_BREADCRUMB(
"Non-trivial delete " +
std::to_string(oldChildPair.shadowView.tag)),
innerScope,
mutationContainer.destructiveDownwardMutations,
oldChildPair.shadowView,
sliceChildShadowNodeViewPairsFromViewNodePair(
oldChildPair, innerScope),
{});
}
}
// Final step: generate Create instructions for entirely new
// subtrees/nodes that are not the result of flattening or unflattening.
for (auto it = newInsertedPairs.begin(); it != newInsertedPairs.end();
it++) {
// Erased elements of a TinyMap will have a Tag/key of 0 - skip those
// These *should* be removed by the map; there are currently no KNOWN
// cases where TinyMap will do the wrong thing, but there are not yet
// any unit tests explicitly for TinyMap, so this is safer for now.
if (it->first == 0) {
continue;
}
auto const &newChildPair = *it->second;
DEBUG_LOGS({
LOG(ERROR)
<< "Differ Branch 12: Inserting tag/tree that was not in old hierarchy: "
<< "[" << newChildPair.shadowView.tag << "]"
<< (newChildPair.flattened ? "(flattened)" : "")
<< (newChildPair.isConcreteView ? "(concrete)" : "")
<< (newChildPair.inOtherTree() ? "(in other tree)" : "")
<< " with parent: [" << parentShadowView.tag << "]";
});
if (!newChildPair.isConcreteView) {
continue;
}
if (newChildPair.inOtherTree()) {
continue;
}
mutationContainer.createMutations.push_back(
ShadowViewMutation::CreateMutation(newChildPair.shadowView));
ViewNodePairScope innerScope{};
calculateShadowViewMutationsV2(
DIFF_BREADCRUMB(
"Non-trivial create " +
std::to_string(newChildPair.shadowView.tag)),
innerScope,
mutationContainer.downwardMutations,
newChildPair.shadowView,
{},
sliceChildShadowNodeViewPairsFromViewNodePair(
newChildPair, innerScope));
}
}
// All mutations in an optimal order:
std::move(
mutationContainer.destructiveDownwardMutations.begin(),
mutationContainer.destructiveDownwardMutations.end(),
std::back_inserter(mutations));
std::move(
mutationContainer.updateMutations.begin(),
mutationContainer.updateMutations.end(),
std::back_inserter(mutations));
std::move(
mutationContainer.removeMutations.rbegin(),
mutationContainer.removeMutations.rend(),
std::back_inserter(mutations));
std::move(
mutationContainer.deleteMutations.begin(),
mutationContainer.deleteMutations.end(),
std::back_inserter(mutations));
std::move(
mutationContainer.createMutations.begin(),
mutationContainer.createMutations.end(),
std::back_inserter(mutations));
std::move(
mutationContainer.downwardMutations.begin(),
mutationContainer.downwardMutations.end(),
std::back_inserter(mutations));
std::move(
mutationContainer.insertMutations.begin(),
mutationContainer.insertMutations.end(),
std::back_inserter(mutations));
}