inspector_diff.cc | Explore in Territory

// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// The MyersDiff was taken from v8/src/debug/liveedit-diff.cc

#include "third_party/blink/renderer/core/inspector/inspector_diff.h"

#include <cmath>
#include <map>
#include <optional>
#include <vector>

#include "base/check.h"
#include "third_party/blink/renderer/platform/wtf/wtf_size_t.h"

namespace blink {

namespace {

// Implements Myer's Algorithm from
// "An O(ND) Difference Algorithm and Its Variations", particularly the
// linear space refinement mentioned in section 4b.
//
// The differ is input agnostic.
//
// The algorithm works by finding the shortest edit string (SES) in the edit
// graph. The SES describes how to get from a string A of length N to a string
// B of length M via deleting from A and inserting from B.
//
// Example: A = "abbaa", B = "abab"
//
//                  A
//
//          a   b   b   a    a
//        o---o---o---o---o---o
//      a | \ |   |   | \ | \ |
//        o---o---o---o---o---o
//      b |   | \ | \ |   |   |
//  B     o---o---o---o---o---o
//      a | \ |   |   | \ | \ |
//        o---o---o---o---o---o
//      b |   | \ | \ |   |   |
//        o---o---o---o---o---o
//
// The edit graph is constructed with the characters from string A on the x-axis
// and the characters from string B on the y-axis. Starting from (0, 0) we can:
//
//     - Move right, which is equivalent to deleting from A
//     - Move downwards, which is equivalent to inserting from B
//     - Move diagonally if the characters from string A and B match, which
//       means no insertion or deletion.
//
// Any path from (0, 0) to (N, M) describes a valid edit string, but we try to
// find the path with the most diagonals, conversely that is the path with the
// least insertions or deletions.
// Note that a path with "D" insertions/deletions is called a D-path.
class MyersDiffer { … };

class MappingInput : public InspectorDiff::Input { … };

// AddChunk is called whenever a chunk is different in two lists.
// For example, for [1, 8, 2, 3] and [4, 2, 5] It is called with these chunks:
// * pos1 = 0, pos2 = 0; len1 = 2, len2 = 1
// meaning that starting from index 0 there are 2 elements different in list_a
// and starting from index 0 there is 1 element different in list_b
// * pos1 = 3, pos2 = 2; len1 = 1, len2 = 1
// meaning that starting from index 3, there is 1 element different in list_a
// and starting from index 2 there are 1 element different in list_b
// Using this property shows that the elements between two difference chunks
// are the same.
// For the example, initial difference chunk ends at 2nd index for list_a
// and starts at 3rd index in the next difference chunk. Meaning that, 2nd index
// does not belong to a difference chunk.
class MappingOutput : public InspectorDiff::Output { … };

}  // namespace

void InspectorDiff::CalculateMatches(InspectorDiff::Input* input,
                                     InspectorDiff::Output* result_writer) { … }

// Finds the longest common subsequence of list_a and list_b
// then creates a mapping from a_to_b and b_to_a that holds
// which element in list_a exists in the longest common subsequence
// and corresponds to which index in list_b.
void InspectorDiff::FindLCSMapping(const Vector<String>& list_a,
                                   const Vector<String>& list_b,
                                   InspectorIndexMap* a_to_b,
                                   InspectorIndexMap* b_to_a) { … }

}  // namespace blink
chromium/third_party/blink/renderer/core/inspector/inspector_diff.cc
