computeReachSet method
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;
}