Package org.antlr.v4.runtime.atn

Class ATNConfigSet

java.lang.Object
org.antlr.v4.runtime.atn.ATNConfigSet
All Implemented Interfaces:
Iterable<ATNConfig>, Collection<ATNConfig>, Set<ATNConfig>
Direct Known Subclasses:
OrderedATNConfigSet
public class ATNConfigSet extends Object implements Set<ATNConfig>
Represents a set of ATN configurations (see ATNConfig). As configurations are added to the set, they are merged with other ATNConfig instances already in the set when possible using the graph-structured stack.

An instance of this class represents the complete set of positions (with context) in an ATN which would be associated with a single DFA state. Its internal representation is more complex than traditional state used for NFA to DFA conversion due to performance requirements (both improving speed and reducing memory overhead) as well as supporting features such as semantic predicates and non-greedy operators in a form to support ANTLR's prediction algorithm.

Writable sets use a primitive long-keyed map for the (state, alt) merge index so hot add/merge paths avoid Long boxing on every lookup.

  • Field Details

    • MIN_MERGED_CONFIG_CAPACITY

      private static final int MIN_MERGED_CONFIG_CAPACITY
      Minimum expected-element hint passed to the primitive long-keyed merge map when a positive capacity is requested. Matches the previous HashMap default capacity floor so small hints still expand reasonably during closure fan-out.
      See Also:

    • SCRATCH_CAPACITY_FLOOR

      static final int SCRATCH_CAPACITY_FLOOR
      Capacity floor shared by hot-path scratch sets (lexer reach, parser reach/intermediate, epsilon-closure BFS buffers).
      See Also:

    • SPARSE_CLEAR_CAPACITY_FACTOR

      static final int SPARSE_CLEAR_CAPACITY_FACTOR
      When the number of configs is less than table-length / this factor, clear() removes known merge keys one-by-one (O(n)) instead of bulk-filling the open-addressed table (O(capacity)). Retained scratch sets often keep a large table after a wide fan-out edge while later edges hold only a handful of configs.
      See Also:

    • mergedConfigs

      private final ClearableLongObjectHashMap<ATNConfig> mergedConfigs
      This maps (state, alt) -> merged ATNConfig. The key does not account for the ATNConfig.getSemanticContext() of the value, which is only a problem if a single ATNConfigSet contains two configs with the same state and alternative but different semantic contexts. When this case arises, the first config added to this map stays, and the remaining configs are placed in unmerged.

      This map is only used for optimizing the process of adding configs to the set, and is null for read-only sets stored in the DFA.

      Implemented as a private primitive long-keyed open-addressed map (package-private storage; not part of any public or protected API) so getKey(org.antlr.v4.runtime.atn.ATNConfig) values are stored and looked up without Long boxing on the prediction hot path. Hot add(org.antlr.v4.runtime.atn.ATNConfig) / contains(java.lang.Object) hash each key once per operation. clear() uses an empty-fast path and may sparse-remove known keys when occupancy is low relative to table capacity (see SPARSE_CLEAR_CAPACITY_FACTOR). External callers interact only with the Set<ATNConfig> surface of this class.

    • unmerged

      private final ArrayList<ATNConfig> unmerged
      This is an "overflow" list holding configs which cannot be merged with one of the configs in mergedConfigs but have a colliding key. This occurs when two configs in the set have the same state and alternative but different semantic contexts.

      This list is only used for optimizing the process of adding configs to the set, and is null for read-only sets stored in the DFA.

    • configs

      private final ArrayList<ATNConfig> configs
      This is a list of all configs in this set.

    • uniqueAlt

      private int uniqueAlt

    • conflictInfo

      private ConflictInfo conflictInfo

    • hasSemanticContext

      private boolean hasSemanticContext

    • dipsIntoOuterContext

      private boolean dipsIntoOuterContext

    • outermostConfigSet

      private boolean outermostConfigSet
      When true, this config set represents configurations where the entire outer context has been consumed by the ATN interpreter. This prevents the ParserATNSimulator.closure(org.antlr.v4.runtime.atn.ATNConfigSet, org.antlr.v4.runtime.atn.ATNConfigSet, boolean, boolean, org.antlr.v4.runtime.atn.PredictionContextCache, boolean) from pursuing the global FOLLOW when a rule stop state is reached with an empty prediction context.

      Note: outermostConfigSet and dipsIntoOuterContext should never be true at the same time.

    • cachedHashCode

      private int cachedHashCode
      Cached hashCode() for both writable scratch sets and readonly DFA sets. 0 means uncomputed (zero is reserved; a raw hash of zero is stored as 1). Invalidated on every mutating operation that participates in hashCode().

  • Constructor Details

    • ATNConfigSet

      public ATNConfigSet()

    • ATNConfigSet

      public ATNConfigSet(int expectedSize)
      Constructs an empty, writable config set with the given capacity hint for the primary configuration storage. Larger hints reduce rehashing when the approximate number of configurations is known in advance (for example when seeding a set from another configuration set during closure or reach operations).

      The hint is treated as an expected element count for both the configuration list and the primitive (state, alt) merge map. The merge-map expected size is floored at MIN_MERGED_CONFIG_CAPACITY so that small expected sizes which later expand during closure do not rehash more aggressively than an unhinted set.

      Parameters:
      expectedSize - expected number of configurations, or <= 0 for the default map/list capacities

    • ATNConfigSet

      protected ATNConfigSet(ATNConfigSet set, boolean readonly)

  • Method Details