petitparser/lib/src/reflection/analyzer.dart

import '../core/parser.dart';
import '../parser/misc/epsilon.dart';
import '../shared/types.dart';
import 'internal/cycle_set.dart';
import 'internal/first_set.dart';
import 'internal/follow_set.dart';
import 'internal/path.dart';
import 'iterable.dart';

/// Helper to reflect on properties of a grammar.
class Analyzer {
  /// Constructs an analyzer on the parser graph starting at [root].
  Analyzer(this.root);

  /// The start parser of analysis.
  final Parser root;

  /// Returns a set of all parsers reachable from [root].
  Iterable<Parser> get parsers => _parsers;

  late final Set<Parser> _parsers = allParser(root).toSet();

  /// Returns a set of all deep children reachable from [parser].
  ///
  /// The returned set does only include the [parser] itself, if it is
  /// recursively calling itself.
  Set<Parser> allChildren(Parser parser) {
    assert(parsers.contains(parser), 'parser is not part of the analyzer');
    return _allChildren.putIfAbsent(
        parser,
        () => parser.children.fold(
            <Parser>{}, (result, child) => result..addAll(allParser(child))));
  }

  late final Map<Parser, Set<Parser>> _allChildren = {};

  /// Returns the shortest path from [source] that satisfies the given
  /// [predicate], if any.
  ParserPath? findPath(Parser source, Predicate<ParserPath> predicate) {
    ParserPath? path;
    for (final current in findAllPaths(source, predicate)) {
      if (path == null || current.length < path.length) {
        path = current;
      }
    }
    return path;
  }

  /// Returns the shortest path from [source] to [target], if any.
  ParserPath? findPathTo(Parser source, Parser target) {
    assert(parsers.contains(target), 'target is not part of the analyzer');
    return findPath(source, (path) => path.target == target);
  }

  /// Returns all paths starting at [source] that satisfy the given [predicate].
  Iterable<ParserPath> findAllPaths(
      Parser source, Predicate<ParserPath> predicate) {
    assert(parsers.contains(source), 'source is not part of the analyzer');
    return depthFirstSearch(ParserPath([source], []), predicate);
  }

  /// Returns all paths starting at [source] that end in [target].
  Iterable<ParserPath> findAllPathsTo(Parser source, Parser target) {
    assert(parsers.contains(target), 'target is not part of the analyzer');
    return findAllPaths(source, (path) => path.target == target);
  }

  /// Returns `true` if [parser] is transitively nullable, that is it can
  /// successfully parse nothing.
  bool isNullable(Parser parser) => _firstSets[parser]!.contains(sentinel);

  /// Returns the first-set of [parser].
  ///
  /// The first-set of a parser is the set of terminal parsers which can appear
  /// as the first element of any chain of parsers derivable from [parser].
  /// Includes [sentinel], if the set is nullable.
  Iterable<Parser> firstSet(Parser parser) => _firstSets[parser]!;

  late final Map<Parser, Set<Parser>> _firstSets =
      computeFirstSets(parsers: _parsers, sentinel: sentinel);

  /// Returns the follow-set of a [parser].
  ///
  /// The follow-set of a parser is the list of terminal parsers that can
  /// appear immediately after [parser]. Includes [sentinel], if the parse can
  /// complete when starting at [root].
  Iterable<Parser> followSet(Parser parser) => _followSet[parser]!;

  late final Map<Parser, Set<Parser>> _followSet = computeFollowSets(
      root: root, parsers: _parsers, firstSets: _firstSets, sentinel: sentinel);

  /// Returns the cycle-set of a [parser].
  Iterable<Parser> cycleSet(Parser parser) => _cycleSet[parser]!;

  late final Map<Parser, List<Parser>> _cycleSet =
      computeCycleSets(parsers: _parsers, firstSets: _firstSets);

  /// Helper to do a global replace of [source] with [target].
  void replaceAll(Parser source, Parser target) {
    for (final parent in _parsers) {
      parent.replace(source, target);
    }
  }

  /// A unique parser used as a marker in [firstSet] and [followSet]
  /// computations.
  static final sentinel = EpsilonParser<void>(null);
}