computeReachSet method

ATNConfigSet? computeReachSet(ATNConfigSet config, int t, bool fullCtx)

Implementation

ATNConfigSet? computeReachSet(ATNConfigSet config, int t, bool fullCtx) {
  if (debug) log('in computeReachSet, starting closure: $config');

  mergeCache ??= {};

  final intermediate = ATNConfigSet(fullCtx);

  /* Configurations already in a rule stop state indicate reaching the end
		 * of the decision rule (local context) or end of the start rule (full
		 * context). Once reached, these configurations are never updated by a
		 * closure operation, so they are handled separately for the performance
		 * advantage of having a smaller intermediate set when calling closure.
		 *
		 * For full-context reach operations, separate handling is required to
		 * ensure that the alternative matching the longest overall sequence is
		 * chosen when multiple such configurations can match the input.
		 */
  List<ATNConfig>? skippedStopStates;

  // First figure out where we can reach on input t
  for (var c in config) {
    if (debug) log('testing ' + getTokenName(t) + ' at ' + c.toString());

    if (c.state is RuleStopState) {
      assert(c.context!.isEmpty);
      if (fullCtx || t == IntStream.EOF) {
        skippedStopStates ??= [];

        skippedStopStates.add(c);
      }

      continue;
    }

    final n = c.state.numberOfTransitions;
    for (var ti = 0; ti < n; ti++) {
      // for each transition
      final trans = c.state.transition(ti);
      final target = getReachableTarget(trans, t);
      if (target != null) {
        intermediate.add(ATNConfig.dup(c, state: target), mergeCache);
      }
    }
  }

  // Now figure out where the reach operation can take us...

  ATNConfigSet? reach;

  /* This block optimizes the reach operation for intermediate sets which
		 * trivially indicate a termination state for the overall
		 * adaptivePredict operation.
		 *
		 * The conditions assume that intermediate
		 * contains all configurations relevant to the reach set, but this
		 * condition is not true when one or more configurations have been
		 * withheld in skippedStopStates, or when the current symbol is EOF.
		 */
  if (skippedStopStates == null && t != Token.EOF) {
    if (intermediate.length == 1) {
      // Don't pursue the closure if there is just one state.
      // It can only have one alternative; just add to result
      // Also don't pursue the closure if there is unique alternative
      // among the configurations.
      reach = intermediate;
    } else if (getUniqueAlt(intermediate) != ATN.INVALID_ALT_NUMBER) {
      // Also don't pursue the closure if there is unique alternative
      // among the configurations.
      reach = intermediate;
    }
  }

  /* If the reach set could not be trivially determined, perform a closure
		 * operation on the intermediate set to compute its initial value.
		 */
  if (reach == null) {
    reach = ATNConfigSet(fullCtx);
    final closureBusy = <ATNConfig>{};
    final treatEofAsEpsilon = t == Token.EOF;
    for (var c in intermediate) {
      closure(c, reach, closureBusy, false, fullCtx, treatEofAsEpsilon);
    }
  }

  if (t == IntStream.EOF) {
    /* After consuming EOF no additional input is possible, so we are
			 * only interested in configurations which reached the end of the
			 * decision rule (local context) or end of the start rule (full
			 * context). Update reach to contain only these configurations. This
			 * handles both explicit EOF transitions in the grammar and implicit
			 * EOF transitions following the end of the decision or start rule.
			 *
			 * When reach==intermediate, no closure operation was performed. In
			 * this case, removeAllConfigsNotInRuleStopState needs to check for
			 * reachable rule stop states as well as configurations already in
			 * a rule stop state.
			 *
			 * This is handled before the configurations in skippedStopStates,
			 * because any configurations potentially added from that list are
			 * already guaranteed to meet this condition whether or not it's
			 * required.
			 */
    reach = removeAllConfigsNotInRuleStopState(reach, reach == intermediate);
  }

  /* If skippedStopStates is not null, then it contains at least one
		 * configuration. For full-context reach operations, these
		 * configurations reached the end of the start rule, in which case we
		 * only add them back to reach if no configuration during the current
		 * closure operation reached such a state. This ensures adaptivePredict
		 * chooses an alternative matching the longest overall sequence when
		 * multiple alternatives are viable.
		 */
  if (skippedStopStates != null &&
      (!fullCtx ||
          !PredictionModeExtension.hasConfigInRuleStopState(reach))) {
    assert(skippedStopStates.isNotEmpty);
    for (var c in skippedStopStates) {
      reach.add(c, mergeCache);
    }
  }

  if (reach.isEmpty) return null;
  return reach;
}