matchImpl method

ParseTree? matchImpl(ParseTree tree, ParseTree patternTree, MultiMap<String, ParseTree> labels)

Recursively walk tree against patternTree, filling {@code match.}{@link ParseTreeMatch#labels labels}.

@return the first node encountered in tree which does not match a corresponding node in patternTree, or null if the match was successful. The specific node returned depends on the matching algorithm used by the implementation, and may be overridden.

Implementation

ParseTree? matchImpl(
  ParseTree tree,
  ParseTree patternTree,
  MultiMap<String, ParseTree> labels,
) {
  // x and <ID>, x and y, or x and x; or could be mismatched types
  if (tree is TerminalNode && patternTree is TerminalNode) {
    final t1 = tree;
    final t2 = patternTree;
    late final ParseTree mismatchedNode;
    // both are tokens and they have same type
    if (t1.symbol.type == t2.symbol.type) {
      if (t2.symbol is TokenTagToken) {
        // x and <ID>
        final tokenTagToken = t2.symbol as TokenTagToken;
        // track label->list-of-nodes for both token name and label (if any)
        labels.put(tokenTagToken.tokenName, tree);
        if (tokenTagToken.label != null) {
          labels.put(tokenTagToken.label!, tree);
        }
      } else if (t1.text == t2.text) {
        // x and x
      } else {
        // x and y
        mismatchedNode = t1;
      }
    } else {
      mismatchedNode = t1;
    }

    return mismatchedNode;
  }

  if (tree is ParserRuleContext && patternTree is ParserRuleContext) {
    final r1 = tree;
    final r2 = patternTree;
    late final ParseTree mismatchedNode;
    // (expr ...) and <expr>
    final ruleTagToken = getRuleTagToken(r2);
    if (ruleTagToken != null) {
      if (r1.ruleContext.ruleIndex == r2.ruleContext.ruleIndex) {
        // track label->list-of-nodes for both rule name and label (if any)
        labels.put(ruleTagToken.ruleName, tree);
        if (ruleTagToken.label != null) {
          labels.put(ruleTagToken.label!, tree);
        }
      } else {
        mismatchedNode = r1;
      }

      return mismatchedNode;
    }

    // (expr ...) and (expr ...)
    if (r1.childCount != r2.childCount) {
      mismatchedNode = r1;

      return mismatchedNode;
    }

    final n = r1.childCount;
    for (var i = 0; i < n; i++) {
      final childMatch =
          matchImpl(r1.getChild(i)!, patternTree.getChild(i)!, labels);
      if (childMatch != null) {
        return childMatch;
      }
    }

    return null;
  }

  // if nodes aren't both tokens or both rule nodes, can't match
  return tree;
}