pkg/vm/lib/testing/il_matchers.dart

// Copyright (c) 2021, 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.

/// A library to facilitate programmatic matching against flow graphs
/// collected during IL tests. See runtime/docs/infra/il_tests.md for more
/// info.

typedef Renamer = String Function(String);

/// Flow graph parsed from --print-flow-graph-as-json output.
class FlowGraph {
  final List<dynamic> blocks;
  final Map<String, InstructionDescriptor> descriptors;
  final Map<String, dynamic> flags;
  final Renamer rename;

  FlowGraph(this.blocks, Map<String, dynamic> desc, this.flags,
      {required this.rename})
      : descriptors = {
          for (var e in desc.entries)
            e.key: InstructionDescriptor.fromJson(e.value)
        };

  bool get soundNullSafety => flags['nnbd'];

  /// Match the sequence of blocks in this flow graph against the given
  /// sequence of matchers: `expected[i]` is expected to match `blocks[i]`,
  /// but there can be more blocks in the graph than matchers (the suffix is
  /// ignored).
  ///
  /// If [env] is provided it will be used as matching environment, otherwise
  /// a fresh instance of [Env] will be created and used.
  ///
  /// This function returns the populated matching environment.
  Env match(List<Matcher> expected, {Env? env}) {
    env ??= Env(rename: rename, descriptors: descriptors);

    for (var i = 0; i < expected.length; i++) {
      final result = expected[i].match(env, blocks[i]);
      if (result.isFail) {
        print('Failed to match: ${result.message}');
        dump();
        throw 'Failed to match';
      }
    }

    return env;
  }

  void dump() {
    for (var block in blocks) {
      print('B${block['b']}[${block['o']}]');
      for (var instr in [...?block['d'], ...?block['is']]) {
        final v = instr['v'] ?? -1;
        final prefix = v != -1 ? 'v$v <- ' : '';
        final inputs = instr['i']?.map((v) => 'v$v').join(', ') ?? '';
        final attrs = descriptors[instr['o']]
            ?.attributeIndex
            .entries
            .map((e) => '${e.key}: ${instr['d'][e.value]}')
            .join(',');
        final attrsWrapped = attrs != null ? '[$attrs]' : '';
        print('  ${prefix}${instr['o']}$attrsWrapped($inputs)');
      }
    }
  }
}

class InstructionDescriptor {
  final List<String> attributes;
  final Map<String, int> attributeIndex;

  InstructionDescriptor.fromJson(List<dynamic> attrs)
      : this._(attrs.map((v) => _demangle(v)).toList());

  InstructionDescriptor._(List<String> attrs)
      : attributes = attrs.cast<String>(),
        attributeIndex = {for (var i = 0; i < attrs.length; i++) attrs[i]: i};

  static String _demangle(String v) {
    final prefixLen = v.startsWith('&') ? 1 : 0;
    final suffixLen = v.endsWith('()') ? 2 : 0;
    return v.substring(prefixLen, v.length - suffixLen);
  }
}

/// Matching environment.
///
/// This is fundamentally just a name to id mapping which allows to track
/// correspondence between names given to some matchers and blocks/instructions
/// which matched those matchers.
///
/// This object is also used to carry around auxiliary information which might
/// be needed for matching, e.g. [Renamer].
class Env {
  final Map<String, InstructionDescriptor> descriptors;
  final Renamer rename;
  final Map<String, int> nameToId = {};

  Env({required this.rename, required this.descriptors});

  void bind(String name, Map<String, dynamic> instrOrBlock) {
    final id = instrOrBlock['v'] ?? instrOrBlock['b'];

    if (nameToId.containsKey(name) && nameToId[name] != id) {
      throw 'Binding mismatch for $name: got ${nameToId[name]} and $id';
    }

    nameToId[name] = id;
  }
}

abstract class Matcher {
  /// Try matching this matcher against the given value. Returns
  /// [MatchStatus.matched] if match succeeded and an instance of
  /// [MatchStatus.fail] otherwise.
  MatchStatus match(Env e, dynamic v);
}

class MatchStatus {
  final String? message;

  const MatchStatus._matched() : message = null;
  const MatchStatus.fail(String message) : message = message;

  bool get isMatch => message == null;
  bool get isFail => message != null;

  static const MatchStatus matched = MatchStatus._matched();

  void expectMatched(String s) {
    if (message != null) {
      throw 'Failed to match: $message';
    }
  }
}

/// Matcher which always succeeds.
class _AnyMatcher implements Matcher {
  const _AnyMatcher();

  @override
  MatchStatus match(Env e, v) => MatchStatus.matched;

  @override
  String toString() {
    return '*';
  }
}

/// Matcher which updates matching environment when it succeeds.
class _BoundMatcher implements Matcher {
  final String name;
  final Matcher nested;

  _BoundMatcher(this.name, this.nested);

  @override
  MatchStatus match(Env e, dynamic v) {
    final result = nested.match(e, v);
    if (result.isMatch) {
      e.bind(name, v);
    }
    return result;
  }

  @override
  String toString() {
    return '$name <- $nested';
  }
}

/// Matcher which matches a specified value [v].
class _EqualsMatcher implements Matcher {
  final dynamic v;

  _EqualsMatcher(this.v);

  @override
  MatchStatus match(Env e, v) {
    if (this.v == v) {
      return MatchStatus.matched;
    }

    // Some instructions refer to obfuscated names, try to rename
    // the expectation and try again.
    if (this.v is String && v is String && e.rename(this.v) == v) {
      return MatchStatus.matched;
    }

    return this.v == v
        ? MatchStatus.matched
        : MatchStatus.fail('expected ${this.v} got $v');
  }

  @override
  String toString() => '$v';
}

/// Matcher which matches the value which is equivalent to the binding
/// with the given [name] in the matching environment.
///
/// If this matcher is [binding] then it will populate the binding in the
/// matching environment if the [name] is not bound yet on the first call
/// to [match]. Otherwise if the [name] is not bound when [match] is called
/// an exception will be thrown.
///
/// Binding matchers are used when we might see the use of a value before its
/// definition (e.g. we usually use the name of the block in the `Goto` or
/// `Branch` before we see the block itself).
class _RefMatcher implements Matcher {
  final String name;
  final bool binding;

  _RefMatcher(this.name, {this.binding = false});

  @override
  MatchStatus match(Env e, v) {
    if (e.nameToId.containsKey(name)) {
      return e.nameToId[name] == v
          ? MatchStatus.matched
          : MatchStatus.fail(
              'expected $name to bind to ${e.nameToId[name]} but got $v');
    }

    if (!binding) {
      throw UnimplementedError('Unbound reference to ${name}');
    }

    e.nameToId[name] = v;
    return MatchStatus.matched;
  }

  @override
  String toString() {
    return name;
  }
}

/// A wrapper which matches a list of matchers against a list of values.
class _ListMatcher implements Matcher {
  final List<Matcher> expected;

  _ListMatcher(this.expected);

  @override
  MatchStatus match(Env e, dynamic got) {
    if (got is! List) {
      return MatchStatus.fail('expected List, got ${got.runtimeType}');
    }

    if (expected.length > got.length) {
      return MatchStatus.fail(
          'expected at least ${expected.length} elements got ${got.length}');
    }

    for (var i = 0; i < expected.length; i++) {
      final result = expected[i].match(e, got[i]);
      if (result.isFail) {
        return MatchStatus.fail(
            'mismatch at index ${i}, expected ${expected[i]} '
            'got ${got[i]}: ${result.message}');
      }
    }

    if (expected.last is _AnyMatcher || expected.length == got.length) {
      return MatchStatus.matched;
    }

    return MatchStatus.fail(
        'expected exactly ${expected.length} elements got ${got.length}');
  }

  @override
  String toString() => '[${expected.join(',')}]';
}

/// A matcher which matches a block of the specified [kind] and contents.
///
/// Contents are specified as a sequence of matchers ([body]). For each of
/// those matchers a matching block is expected to contain at least one
/// instruction that matches it. Matching is done in order: first we scan
/// the block until we find the match for the first matcher in body, then
/// we continue scanning until we find the match for the second and so on.
class _BlockMatcher implements Matcher {
  final String kind;
  final List<Matcher> body;

  _BlockMatcher(this.kind, [this.body = const []]);

  @override
  MatchStatus match(Env e, covariant Map<String, dynamic> block) {
    if (block['o'] != '${kind}Entry') {
      return MatchStatus.fail(
          'Expected block of kind ${kind} got ${block['o']} '
          'when matching B${block['b']}');
    }

    final gotBody = [...?block['d'], ...?block['is']];

    var matcherIndex = 0;
    for (int i = 0; i < gotBody.length && matcherIndex < body.length; i++) {
      if (body[matcherIndex].match(e, gotBody[i]).isMatch) {
        matcherIndex++;
      }
    }
    if (matcherIndex != body.length) {
      return MatchStatus.fail('Unmatched instruction: ${body[matcherIndex]} '
          'in block B${block['b']}');
    }
    return MatchStatus.matched;
  }
}

/// A matcher for instruction's named attributes.
///
/// Attributes are resolved to their indices through [Env.descriptors].
class _AttributesMatcher implements Matcher {
  final String op;
  final Map<String, Matcher> matchers;

  _ListMatcher? impl;

  _AttributesMatcher(this.op, this.matchers);

  @override
  MatchStatus match(Env e, dynamic v) {
    impl ??= _ListMatcher(e.descriptors[op]!.attributes
        .map((name) => matchers[name] ?? const _AnyMatcher())
        .toList());
    return impl!.match(e, v);
  }

  @override
  String toString() {
    return matchers.toString();
  }
}

/// Matcher which matches an instruction with opcode [op] and properties
/// specified in [matchers] map.
class InstructionMatcher implements Matcher {
  final String op;
  final Map<String, Matcher> matchers;

  InstructionMatcher(
      {required String op, List<Matcher>? data, List<Matcher>? inputs})
      : this._(op: op, matchers: {
          if (data != null) 'd': _ListMatcher(data),
          if (inputs != null) 'i': _ListMatcher(inputs),
        });

  InstructionMatcher._({
    required this.op,
    required this.matchers,
  });

  @override
  MatchStatus match(Env e, covariant Map<String, dynamic> instr) {
    if (instr['o'] != op) {
      return MatchStatus.fail('expected instruction ${op} got ${instr['o']}');
    }

    for (var entry in matchers.entries) {
      final result = entry.value.match(e, instr[entry.key]);
      if (result.isFail) {
        return result;
      }
    }

    return MatchStatus.matched;
  }

  @override
  String toString() {
    return '$op($matchers)';
  }
}

/// This class uses `noSuchMethod` to allow writing code like
///
/// ```
/// match.Op(in0, ..., inN, attr0: a0, ..., attrK: aK)
/// ```
///
/// This will produce an instruction matcher which matches opcode `Op` and
/// expects `in0, ..., inN` to match instructions inputs, while `a0, ...`
/// matchers are expected to match attributes with names `attr0, ...`.
class Matchers {
  _BlockMatcher block(String kind, [List<dynamic> body = const []]) {
    return _BlockMatcher(kind, List<Matcher>.from(body));
  }

  final _AnyMatcher any = const _AnyMatcher();

  InstructionMatcher Goto(String dest) =>
      InstructionMatcher._(op: 'Goto', matchers: {
        's': _ListMatcher([_blockRef(dest)])
      });

  InstructionMatcher Branch(InstructionMatcher compare,
          {String? ifTrue, String? ifFalse}) =>
      InstructionMatcher._(op: 'Branch', matchers: {
        'cc': compare,
        's': _ListMatcher([
          ifTrue != null ? _blockRef(ifTrue) : any,
          ifFalse != null ? _blockRef(ifFalse) : any,
        ]),
      });

  @override
  Object? noSuchMethod(Invocation invocation) {
    final data = {
      for (var e in invocation.namedArguments.entries)
        getName(e.key): Matchers._toAttributeMatcher(e.value),
    };
    final inputs =
        invocation.positionalArguments.map(Matchers._toInputMatcher).toList();
    final op = getName(invocation.memberName);
    return InstructionMatcher._(op: op, matchers: {
      if (data.isNotEmpty) 'd': _AttributesMatcher(op, data),
      if (inputs.isNotEmpty) 'i': _ListMatcher(inputs),
    });
  }

  static Matcher _blockRef(String name) => _RefMatcher(name, binding: true);

  static Matcher _toAttributeMatcher(dynamic v) {
    if (v is Matcher) {
      return v;
    } else {
      return _EqualsMatcher(v);
    }
  }

  static Matcher _toInputMatcher(dynamic v) {
    if (v is Matcher) {
      return v;
    } else if (v is String) {
      return _RefMatcher(v);
    } else {
      throw ArgumentError.value(
          v, 'v', 'Expected either a Matcher or a String (binding name)');
    }
  }
}

/// Extension which enables `'name' << matcher` syntax for creating bound
/// matchers.
extension BindingExtension on String {
  Matcher operator <<(Matcher matcher) {
    return _BoundMatcher(this, matcher);
  }
}

final dynamic match = Matchers();

/// This file should not depend on dart:mirrors because it is imported into
/// tests, which are compiled in AOT mode. So instead we let compare_il driver
/// set this field.
late String Function(Symbol) getName;