Java 类org.antlr.v4.runtime.dfa.DFAState 实例源码

protected void predicateDFAState(DFAState dfaState, DecisionState decisionState) {
    // We need to test all predicates, even in DFA states that
    // uniquely predict alternative.
    int nalts = decisionState.getNumberOfTransitions();
    // Update DFA so reach becomes accept state with (predicate,alt)
    // pairs if preds found for conflicting alts
    BitSet altsToCollectPredsFrom = getConflictingAltsOrUniqueAlt(dfaState.configs);
    SemanticContext[] altToPred = getPredsForAmbigAlts(altsToCollectPredsFrom, dfaState.configs, nalts);
    if ( altToPred!=null ) {
        dfaState.predicates = getPredicatePredictions(altsToCollectPredsFrom, altToPred);
        dfaState.prediction = ATN.INVALID_ALT_NUMBER; // make sure we use preds
    }
    else {
        // There are preds in configs but they might go away
        // when OR'd together like {p}? || NONE == NONE. If neither
        // alt has preds, resolve to min alt
        dfaState.prediction = altsToCollectPredsFrom.nextSetBit(0);
    }
}

protected DFAState.PredPrediction[] getPredicatePredictions(BitSet ambigAlts,
                                                             SemanticContext[] altToPred)
    {
        List<DFAState.PredPrediction> pairs = new ArrayList<DFAState.PredPrediction>();
        boolean containsPredicate = false;
        for (int i = 1; i < altToPred.length; i++) {
            SemanticContext pred = altToPred[i];

            // unpredicated is indicated by SemanticContext.NONE
            assert pred != null;

            if (ambigAlts!=null && ambigAlts.get(i)) {
                pairs.add(new DFAState.PredPrediction(pred, i));
            }
            if ( pred!=SemanticContext.NONE ) containsPredicate = true;
        }

        if ( !containsPredicate ) {
            return null;
        }

//      System.out.println(Arrays.toString(altToPred)+"->"+pairs);
        return pairs.toArray(new DFAState.PredPrediction[pairs.size()]);
    }

/**
 * Add state {@code D} to the DFA if it is not already present, and return
 * the actual instance stored in the DFA. If a state equivalent to {@code D}
 * is already in the DFA, the existing state is returned. Otherwise this
 * method returns {@code D} after adding it to the DFA.
 *
 * <p>If {@code D} is {@link #ERROR}, this method returns {@link #ERROR} and
 * does not change the DFA.</p>
 *
 * @param dfa The dfa
 * @param D The DFA state to add
 * @return The state stored in the DFA. This will be either the existing
 * state if {@code D} is already in the DFA, or {@code D} itself if the
 * state was not already present.
 */
@NotNull
protected DFAState addDFAState(@NotNull DFA dfa, @NotNull DFAState D) {
    if (D == ERROR) {
        return D;
    }

    synchronized (dfa.states) {
        DFAState existing = dfa.states.get(D);
        if ( existing!=null ) return existing;

        D.stateNumber = dfa.states.size();
        if (!D.configs.isReadonly()) {
            D.configs.optimizeConfigs(this);
            D.configs.setReadonly(true);
        }
        dfa.states.put(D, D);
        if ( debug ) System.out.println("adding new DFA state: "+D);
        return D;
    }
}

@Override
protected DFAState getExistingTargetState(DFAState previousD, int t) {
    // this method is called after each time the input position advances
    // during SLL prediction
    _sllStopIndex = _input.index();

    DFAState existingTargetState = super.getExistingTargetState(previousD, t);
    if ( existingTargetState!=null ) {
        decisions[currentDecision].SLL_DFATransitions++; // count only if we transition over a DFA state
        if ( existingTargetState==ERROR ) {
            decisions[currentDecision].errors.add(
                    new ErrorInfo(currentDecision, previousD.configs, _input, _startIndex, _sllStopIndex, false)
            );
        }
    }

    currentState = existingTargetState;
    return existingTargetState;
}

@Override
protected void reportAmbiguity(@NotNull DFA dfa, DFAState D, int startIndex, int stopIndex, boolean exact,
                               @Nullable BitSet ambigAlts, @NotNull ATNConfigSet configs)
{
    int prediction;
    if ( ambigAlts!=null ) {
        prediction = ambigAlts.nextSetBit(0);
    }
    else {
        prediction = configs.getAlts().nextSetBit(0);
    }
    if ( configs.fullCtx && prediction != conflictingAltResolvedBySLL ) {
        // Even though this is an ambiguity we are reporting, we can
        // still detect some context sensitivities.  Both SLL and LL
        // are showing a conflict, hence an ambiguity, but if they resolve
        // to different minimum alternatives we have also identified a
        // context sensitivity.
        decisions[currentDecision].contextSensitivities.add(
                new ContextSensitivityInfo(currentDecision, configs, _input, startIndex, stopIndex)
        );
    }
    decisions[currentDecision].ambiguities.add(
        new AmbiguityInfo(currentDecision, configs, _input, startIndex, stopIndex, configs.fullCtx)
    );
    super.reportAmbiguity(dfa, D, startIndex, stopIndex, exact, ambigAlts, configs);
}

protected int matchATN(@NotNull CharStream input) {
    ATNState startState = atn.modeToStartState.get(mode);

    if ( debug ) {
        System.out.format(Locale.getDefault(), "matchATN mode %d start: %s\n", mode, startState);
    }

    int old_mode = mode;

    ATNConfigSet s0_closure = computeStartState(input, startState);
    boolean suppressEdge = s0_closure.hasSemanticContext;
    s0_closure.hasSemanticContext = false;

    DFAState next = addDFAState(s0_closure);
    if (!suppressEdge) {
        decisionToDFA[mode].s0 = next;
    }

    int predict = execATN(input, next);

    if ( debug ) {
        System.out.format(Locale.getDefault(), "DFA after matchATN: %s\n", decisionToDFA[old_mode].toLexerString());
    }

    return predict;
}

/**
 * Compute a target state for an edge in the DFA, and attempt to add the
 * computed state and corresponding edge to the DFA.
 *
 * @param input The input stream
 * @param s The current DFA state
 * @param t The next input symbol
 *
 * @return The computed target DFA state for the given input symbol
 * {@code t}. If {@code t} does not lead to a valid DFA state, this method
 * returns {@link #ERROR}.
 */
@NotNull
protected DFAState computeTargetState(@NotNull CharStream input, @NotNull DFAState s, int t) {
    ATNConfigSet reach = new OrderedATNConfigSet();

    // if we don't find an existing DFA state
    // Fill reach starting from closure, following t transitions
    getReachableConfigSet(input, s.configs, reach, t);

    if ( reach.isEmpty() ) { // we got nowhere on t from s
        if (!reach.hasSemanticContext) {
            // we got nowhere on t, don't throw out this knowledge; it'd
            // cause a failover from DFA later.
            addDFAEdge(s, t, ERROR);
        }

        // stop when we can't match any more char
        return ERROR;
    }

    // Add an edge from s to target DFA found/created for reach
    return addDFAEdge(s, t, reach);
}

protected void addDFAEdge(@NotNull DFAState p, int t, @NotNull DFAState q) {
    if (t < MIN_DFA_EDGE || t > MAX_DFA_EDGE) {
        // Only track edges within the DFA bounds
        return;
    }

    if ( debug ) {
        System.out.println("EDGE "+p+" -> "+q+" upon "+((char)t));
    }

    synchronized (p) {
        if ( p.edges==null ) {
            //  make room for tokens 1..n and -1 masquerading as index 0
            p.edges = new DFAState[MAX_DFA_EDGE-MIN_DFA_EDGE+1];
        }
        p.edges[t - MIN_DFA_EDGE] = q; // connect
    }
}

@Override
protected DFAState getExistingTargetState(DFAState s, int t) {
    DFAState target = super.getExistingTargetState(s, t);
    if (target != null) {
        _listener.transition(false);
    }

    return target;
}

@Override
protected void addDFAEdge(DFAState p, int t, DFAState q) {
    if (!getSuppressedSet(startIndex).isNil()) {
        return;
    }

    super.addDFAEdge(p, t, q);
}

@Override
protected DFAState addDFAEdge(DFA dfa, DFAState fromState, int t, IntegerList contextTransitions, ATNConfigSet toConfigs, PredictionContextCache contextCache) {
    if (!getSuppressedSet(startIndex).isNil()) {
        DFAState to = addDFAState(dfa, toConfigs, contextCache);
        return to;
    }

    return super.addDFAEdge(dfa, fromState, t, contextTransitions, toConfigs, contextCache);
}

@Override
protected DFAState createDFAState(DFA dfa, ATNConfigSet configs) {
    int t = _input.LA(1);
    if (t == CaretToken.CARET_TOKEN_TYPE && !_computingStartState) {
        caretToken = (CaretToken)_input.LT(1);
        throw noViableAlt(_input, _outerContext, configs, _startIndex);
    }

    return super.createDFAState(dfa, configs);
}

/** Look through a list of predicate/alt pairs, returning alts for the
 *  pairs that win. A {@code NONE} predicate indicates an alt containing an
 *  unpredicated config which behaves as "always true." If !complete
 *  then we stop at the first predicate that evaluates to true. This
 *  includes pairs with null predicates.
 */
protected BitSet evalSemanticContext(@NotNull DFAState.PredPrediction[] predPredictions,
                                  ParserRuleContext outerContext,
                                  boolean complete)
{
    BitSet predictions = new BitSet();
    for (DFAState.PredPrediction pair : predPredictions) {
        if ( pair.pred==SemanticContext.NONE ) {
            predictions.set(pair.alt);
            if (!complete) {
                break;
            }
            continue;
        }

        boolean fullCtx = false; // in dfa
        boolean predicateEvaluationResult = evalSemanticContext(pair.pred, outerContext, pair.alt, fullCtx);
        if ( debug || dfa_debug ) {
            System.out.println("eval pred "+pair+"="+predicateEvaluationResult);
        }

        if ( predicateEvaluationResult ) {
            if ( debug || dfa_debug ) System.out.println("PREDICT "+pair.alt);
            predictions.set(pair.alt);
            if (!complete) {
                break;
            }
        }
    }

    return predictions;
}

/**
 * Add an edge to the DFA, if possible. This method calls
 * {@link #addDFAState} to ensure the {@code to} state is present in the
 * DFA. If {@code from} is {@code null}, or if {@code t} is outside the
 * range of edges that can be represented in the DFA tables, this method
 * returns without adding the edge to the DFA.
 *
 * <p>If {@code to} is {@code null}, this method returns {@code null}.
 * Otherwise, this method returns the {@link DFAState} returned by calling
 * {@link #addDFAState} for the {@code to} state.</p>
 *
 * @param dfa The DFA
 * @param from The source state for the edge
 * @param t The input symbol
 * @param to The target state for the edge
 *
 * @return If {@code to} is {@code null}, this method returns {@code null};
 * otherwise this method returns the result of calling {@link #addDFAState}
 * on {@code to}
 */
protected DFAState addDFAEdge(@NotNull DFA dfa,
                              @Nullable DFAState from,
                              int t,
                              @Nullable DFAState to)
{
    if ( debug ) {
        System.out.println("EDGE "+from+" -> "+to+" upon "+getTokenName(t));
    }

    if (to == null) {
        return null;
    }

    to = addDFAState(dfa, to); // used existing if possible not incoming
    if (from == null || t < -1 || t > atn.maxTokenType) {
        return to;
    }

    synchronized (from) {
        if ( from.edges==null ) {
            from.edges = new DFAState[atn.maxTokenType+1+1];
        }

        from.edges[t+1] = to; // connect
    }

    if ( debug ) {
        System.out.println("DFA=\n"+dfa.toString(parser!=null?parser.getTokenNames():null));
    }

    return to;
}

/** If context sensitive parsing, we know it's ambiguity not conflict */
   protected void reportAmbiguity(@NotNull DFA dfa, DFAState D, int startIndex, int stopIndex,
                               boolean exact,
                               @Nullable BitSet ambigAlts,
                               @NotNull ATNConfigSet configs)
{
    if ( debug || retry_debug ) {
        Interval interval = Interval.of(startIndex, stopIndex);
        System.out.println("reportAmbiguity "+
                           ambigAlts+":"+configs+
                              ", input="+parser.getTokenStream().getText(interval));
       }
       if ( parser!=null ) parser.getErrorListenerDispatch().reportAmbiguity(parser, dfa, startIndex, stopIndex,
                                                                          exact, ambigAlts, configs);
   }

/**
 * Get an existing target state for an edge in the DFA. If the target state
 * for the edge has not yet been computed or is otherwise not available,
 * this method returns {@code null}.
 *
 * @param s The current DFA state
 * @param t The next input symbol
 * @return The existing target DFA state for the given input symbol
 * {@code t}, or {@code null} if the target state for this edge is not
 * already cached
 */
@Nullable
protected DFAState getExistingTargetState(@NotNull DFAState s, int t) {
    if (s.edges == null || t < MIN_DFA_EDGE || t > MAX_DFA_EDGE) {
        return null;
    }

    DFAState target = s.edges[t - MIN_DFA_EDGE];
    if (debug && target != null) {
        System.out.println("reuse state "+s.stateNumber+
                           " edge to "+target.stateNumber);
    }

    return target;
}

protected void captureSimState(@NotNull SimState settings,
                               @NotNull CharStream input,
                               @NotNull DFAState dfaState)
{
    settings.index = input.index();
    settings.line = line;
    settings.charPos = charPositionInLine;
    settings.dfaState = dfaState;
}

@NotNull
protected DFAState addDFAEdge(@NotNull DFAState from,
                              int t,
                              @NotNull ATNConfigSet q)
{
    /* leading to this call, ATNConfigSet.hasSemanticContext is used as a
     * marker indicating dynamic predicate evaluation makes this edge
     * dependent on the specific input sequence, so the static edge in the
     * DFA should be omitted. The target DFAState is still created since
     * execATN has the ability to resynchronize with the DFA state cache
     * following the predicate evaluation step.
     *
     * TJP notes: next time through the DFA, we see a pred again and eval.
     * If that gets us to a previously created (but dangling) DFA
     * state, we can continue in pure DFA mode from there.
     */
    boolean suppressEdge = q.hasSemanticContext;
    q.hasSemanticContext = false;

    @NotNull
    DFAState to = addDFAState(q);

    if (suppressEdge) {
        return to;
    }

    addDFAEdge(from, t, to);
    return to;
}

/** Add a new DFA state if there isn't one with this set of
    configurations already. This method also detects the first
    configuration containing an ATN rule stop state. Later, when
    traversing the DFA, we will know which rule to accept.
 */
@NotNull
protected DFAState addDFAState(@NotNull ATNConfigSet configs) {
    /* the lexer evaluates predicates on-the-fly; by this point configs
     * should not contain any configurations with unevaluated predicates.
     */
    assert !configs.hasSemanticContext;

    DFAState proposed = new DFAState(configs);
    ATNConfig firstConfigWithRuleStopState = null;
    for (ATNConfig c : configs) {
        if ( c.state instanceof RuleStopState ) {
            firstConfigWithRuleStopState = c;
            break;
        }
    }

    if ( firstConfigWithRuleStopState!=null ) {
        proposed.isAcceptState = true;
        proposed.lexerActionExecutor = ((LexerATNConfig)firstConfigWithRuleStopState).getLexerActionExecutor();
        proposed.prediction = atn.ruleToTokenType[firstConfigWithRuleStopState.state.ruleIndex];
    }

    DFA dfa = decisionToDFA[mode];
    synchronized (dfa.states) {
        DFAState existing = dfa.states.get(proposed);
        if ( existing!=null ) return existing;

        DFAState newState = proposed;

        newState.stateNumber = dfa.states.size();
        configs.setReadonly(true);
        newState.configs = configs;
        dfa.states.put(newState, newState);
        return newState;
    }
}

@Override
protected Tuple2<DFAState, ParserRuleContext> computeTargetState(DFA dfa, DFAState s, ParserRuleContext remainingGlobalContext, int t, boolean useContext, PredictionContextCache contextCache) {
    computedTransitions[decision]++;

    long startTime = System.nanoTime();
    try {
        return super.computeTargetState(dfa, s, remainingGlobalContext, t, useContext, contextCache);
    } finally {
        long totalTime = System.nanoTime() - startTime;
        decisionCost[dfa.decision] += totalTime;
        if (useContext) {
            decisionLlCost[dfa.decision] += totalTime;
        }
    }
}

@Override
protected DFAState getExistingTargetState(DFAState s, int t) {
    DFAState target = super.getExistingTargetState(s, t);
    if (target != null) {
        _listener.transition(false);
    }

    return target;
}

@Override
protected DFAState createDFAState(DFA dfa, ATNConfigSet configs) {
    int t = _input.LA(1);
    if (t == CaretToken.CARET_TOKEN_TYPE && !_computingStartState) {
        caretToken = (CaretToken)_input.LT(1);
        throw noViableAlt(_input, _outerContext, configs, _startIndex);
    }

    return super.createDFAState(dfa, configs);
}

@Override
protected DFAState getExistingTargetState(DFAState s, int t) {
    totalTransitions++;
    return super.getExistingTargetState(s, t);
}

@Override
protected DFAState computeTargetState(CharStream input, DFAState s, int t) {
    computedTransitions++;
    return super.computeTargetState(input, s, t);
}

@Override
protected DFAState getExistingTargetState(DFAState previousD, int t) {
    totalTransitions[decision]++;
    return super.getExistingTargetState(previousD, t);
}

@Override
protected Tuple2<DFAState, ParserRuleContext> computeTargetState(DFA dfa, DFAState s, ParserRuleContext remainingGlobalContext, int t, boolean useContext, PredictionContextCache contextCache) {
    computedTransitions[decision]++;
    return super.computeTargetState(dfa, s, remainingGlobalContext, t, useContext, contextCache);
}

@Override
protected DFAState computeTargetState(CharStream input, DFAState s, int t) {
    _listener.transition(true);
    return super.computeTargetState(input, s, t);
}

@Override
protected void captureSimState(SimState settings, CharStream input, DFAState dfaState) {
    _listener.acceptState(dfaState.getPrediction());
    super.captureSimState(settings, input, dfaState);
}

/**
 * Compute a target state for an edge in the DFA, and attempt to add the
 * computed state and corresponding edge to the DFA.
 *
 * @param dfa The DFA
 * @param previousD The current DFA state
 * @param t The next input symbol
 *
 * @return The computed target DFA state for the given input symbol
 * {@code t}. If {@code t} does not lead to a valid DFA state, this method
 * returns {@link #ERROR}.
 */
@NotNull
protected DFAState computeTargetState(@NotNull DFA dfa, @NotNull DFAState previousD, int t) {
    ATNConfigSet reach = computeReachSet(previousD.configs, t, false);
    if ( reach==null ) {
        addDFAEdge(dfa, previousD, t, ERROR);
        return ERROR;
    }

    // create new target state; we'll add to DFA after it's complete
    DFAState D = new DFAState(reach);

    int predictedAlt = getUniqueAlt(reach);

    if ( debug ) {
        Collection<BitSet> altSubSets = PredictionMode.getConflictingAltSubsets(reach);
        System.out.println("SLL altSubSets="+altSubSets+
                           ", configs="+reach+
                           ", predict="+predictedAlt+", allSubsetsConflict="+
                               PredictionMode.allSubsetsConflict(altSubSets)+", conflictingAlts="+
                           getConflictingAlts(reach));
    }

    if ( predictedAlt!=ATN.INVALID_ALT_NUMBER ) {
        // NO CONFLICT, UNIQUELY PREDICTED ALT
        D.isAcceptState = true;
        D.configs.uniqueAlt = predictedAlt;
        D.prediction = predictedAlt;
    }
    else if ( PredictionMode.hasSLLConflictTerminatingPrediction(mode, reach) ) {
        // MORE THAN ONE VIABLE ALTERNATIVE
        D.configs.conflictingAlts = getConflictingAlts(reach);
        D.requiresFullContext = true;
        // in SLL-only mode, we will stop at this state and return the minimum alt
        D.isAcceptState = true;
        D.prediction = D.configs.conflictingAlts.nextSetBit(0);
    }

    if ( D.isAcceptState && D.configs.hasSemanticContext ) {
        predicateDFAState(D, atn.getDecisionState(dfa.decision));
        if (D.predicates != null) {
            D.prediction = ATN.INVALID_ALT_NUMBER;
        }
    }

    // all adds to dfa are done after we've created full D state
    D = addDFAEdge(dfa, previousD, t, D);
    return D;
}

@Override
protected DFAState computeTargetState(DFA dfa, DFAState previousD, int t) {
    DFAState state = super.computeTargetState(dfa, previousD, t);
    currentState = state;
    return state;
}

protected int execATN(@NotNull CharStream input, @NotNull DFAState ds0) {
    //System.out.println("enter exec index "+input.index()+" from "+ds0.configs);
    if ( debug ) {
        System.out.format(Locale.getDefault(), "start state closure=%s\n", ds0.configs);
    }

    int t = input.LA(1);
    @NotNull
    DFAState s = ds0; // s is current/from DFA state

    while ( true ) { // while more work
        if ( debug ) {
            System.out.format(Locale.getDefault(), "execATN loop starting closure: %s\n", s.configs);
        }

        // As we move src->trg, src->trg, we keep track of the previous trg to
        // avoid looking up the DFA state again, which is expensive.
        // If the previous target was already part of the DFA, we might
        // be able to avoid doing a reach operation upon t. If s!=null,
        // it means that semantic predicates didn't prevent us from
        // creating a DFA state. Once we know s!=null, we check to see if
        // the DFA state has an edge already for t. If so, we can just reuse
        // it's configuration set; there's no point in re-computing it.
        // This is kind of like doing DFA simulation within the ATN
        // simulation because DFA simulation is really just a way to avoid
        // computing reach/closure sets. Technically, once we know that
        // we have a previously added DFA state, we could jump over to
        // the DFA simulator. But, that would mean popping back and forth
        // a lot and making things more complicated algorithmically.
        // This optimization makes a lot of sense for loops within DFA.
        // A character will take us back to an existing DFA state
        // that already has lots of edges out of it. e.g., .* in comments.
        DFAState target = getExistingTargetState(s, t);
        if (target == null) {
            target = computeTargetState(input, s, t);
        }

        if (target == ERROR) {
            break;
        }

        if (target.isAcceptState) {
            captureSimState(prevAccept, input, target);
            if (t == IntStream.EOF) {
                break;
            }
        }

        if (t != IntStream.EOF) {
            consume(input);
            t = input.LA(1);
        }

        s = target; // flip; current DFA target becomes new src/from state
    }

    return failOrAccept(prevAccept, input, s.configs, t);
}

@Override
protected DFAState getExistingTargetState(DFAState s, int t) {
    totalTransitions++;
    return super.getExistingTargetState(s, t);
}

@Override
protected DFAState computeTargetState(CharStream input, DFAState s, int t) {
    computedTransitions++;
    return super.computeTargetState(input, s, t);
}

@Override
protected DFAState getExistingTargetState(DFAState previousD, int t) {
    totalTransitions[decision]++;
    return super.getExistingTargetState(previousD, t);
}

@Override
protected DFAState computeTargetState(CharStream input, DFAState s, int t) {
    _listener.transition(true);
    return super.computeTargetState(input, s, t);
}

@Override
protected void captureSimState(SimState settings, CharStream input, DFAState dfaState) {
    _listener.acceptState(dfaState.getPrediction());
    super.captureSimState(settings, input, dfaState);
}

/**
 * Get an existing target state for an edge in the DFA. If the target state
 * for the edge has not yet been computed or is otherwise not available,
 * this method returns {@code null}.
 *
 * @param previousD The current DFA state
 * @param t The next input symbol
 * @return The existing target DFA state for the given input symbol
 * {@code t}, or {@code null} if the target state for this edge is not
 * already cached
 */
@Nullable
protected DFAState getExistingTargetState(@NotNull DFAState previousD, int t) {
    DFAState[] edges = previousD.edges;
    if (edges == null || t + 1 < 0 || t + 1 >= edges.length) {
        return null;
    }

    return edges[t + 1];
}