pkg/analyzer_fe_comparison/lib/src/comparison_node.dart

// Copyright (c) 2018, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'dart:math';

/// [ComparisonNode] defines a simple tree structure that can be used to compare
/// two representations of Dart code.
///
/// Each node contains a textual string and a list of child nodes.
class ComparisonNode {
  final String text;
  final List<ComparisonNode> children;

  ComparisonNode(this.text, [List<ComparisonNode> children])
      : children = children ?? <ComparisonNode>[];

  factory ComparisonNode.sorted(
          String text, Iterable<ComparisonNode> children) =>
      ComparisonNode(text, sortList(children));

  @override
  bool operator ==(Object other) {
    if (other is ComparisonNode) {
      if (text != other.text) return false;
      if (children.length != other.children.length) return false;
      for (int i = 0; i < children.length; i++) {
        if (children[i] != other.children[i]) return false;
      }
      return true;
    }
    return false;
  }

  String toString({String newline: '\n'}) {
    var lines = ['$text'];
    var indentedNewline = '$newline  ';
    for (var child in children) {
      lines.add(child.toString(newline: indentedNewline));
    }
    return lines.join(indentedNewline);
  }

  static ComparisonNode diff(
      ComparisonNode a, ComparisonNode b, String aName, String bName) {
    if (a.text == b.text) {
      return ComparisonNode(
          a.text, diffLists(a.children, b.children, aName, bName));
    } else {
      return ComparisonNode('Root nodes differ',
          [_prefix('In $aName: ', a), _prefix('In $bName: ', b)]);
    }
  }

  static List<ComparisonNode> diffLists(List<ComparisonNode> a,
      List<ComparisonNode> b, String aName, String bName) {
    // Note: this is an O(n) "poor man's" diff algorithm; it produces optimal
    // results if the incoming results are sorted by text or if there is just
    // one contiguous hunk of differences.  Otherwise it may not find the
    // shortest diff.  This should be sufficient for our purposes, since we are
    // not expecting many diffs.

    // We'll exclude common nodes at the beginning of both lists
    var shorterLength = min(a.length, b.length);
    var commonInitialNodes = 0;
    while (commonInitialNodes < shorterLength &&
        a[commonInitialNodes] == b[commonInitialNodes]) {
      commonInitialNodes++;
    }

    // Fast exit if a == b
    if (commonInitialNodes == a.length && a.length == b.length) {
      return [];
    }

    // We'll exclude common nodes at the end of both lists (note: we don't want
    // to overcount by re-testing the common nodes identified above)
    var commonFinalNodes = 0;
    while (commonInitialNodes + commonFinalNodes < shorterLength &&
        a[a.length - commonFinalNodes - 1] ==
            b[b.length - commonFinalNodes - 1]) {
      commonFinalNodes++;
    }

    // Walk the remaining nodes starting at the first node that's different,
    // matching up nodes by their text.
    var aIndex = commonInitialNodes;
    var bIndex = commonInitialNodes;
    var aEnd = a.length - commonFinalNodes;
    var bEnd = b.length - commonFinalNodes;
    var result = <ComparisonNode>[];
    while (aIndex < aEnd && bIndex < bEnd) {
      var comparisonResult = a[aIndex].text.compareTo(b[bIndex].text);
      if (comparisonResult < 0) {
        // a[aIndex].text sorts before b[bIndex].text.  Assume that this means
        // a[aIndex] was removed.
        result.add(_prefix('Only in $aName: ', a[aIndex++]));
      } else if (comparisonResult > 0) {
        // b[bIndex].text sorts before a[aIndex].text.  Assume that this means
        // b[bIndex] was added.
        result.add(_prefix('Only in $bName: ', b[bIndex++]));
      } else {
        // a[aIndex].text matches b[bIndex].text, so diff the nodes if
        // necessary.
        var aNode = a[aIndex++];
        var bNode = b[bIndex++];
        if (aNode != bNode) {
          result.add(diff(aNode, bNode, aName, bName));
        }
      }
    }

    // Deal with any nodes left over.
    while (aIndex < aEnd) {
      result.add(_prefix('Only in $aName: ', a[aIndex++]));
    }
    while (bIndex < bEnd) {
      result.add(_prefix('Only in $bName: ', b[bIndex++]));
    }

    // If we get here and we haven't added any nodes, something has gone wrong.
    if (result.isEmpty) {
      throw StateError('Diff produced empty diff for non-matching lists');
    }

    return result;
  }

  static List<ComparisonNode> sortList(Iterable<ComparisonNode> nodes) {
    var result = nodes.toList();
    result.sort((a, b) => a.text.compareTo(b.text));
    return result;
  }

  static ComparisonNode _prefix(String prefixString, ComparisonNode node) {
    return ComparisonNode(prefixString + node.text, node.children);
  }
}