1 /* 2 * Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. 3 * Use of this file is governed by the BSD 3-clause license that 4 * can be found in the LICENSE.txt file in the project root. 5 */ 6 7 package org.antlr.v4.runtime.atn; 8 9 import org.antlr.v4.runtime.misc.IntervalSet; 10 11 import java.util.ArrayList; 12 import java.util.Arrays; 13 import java.util.Collections; 14 import java.util.List; 15 import java.util.Locale; 16 17 /** 18 * The following images show the relation of states and 19 * {@link ATNState#transitions} for various grammar constructs. 20 * 21 * <ul> 22 * 23 * <li>Solid edges marked with an ε indicate a required 24 * {@link EpsilonTransition}.</li> 25 * 26 * <li>Dashed edges indicate locations where any transition derived from 27 * {@link Transition} might appear.</li> 28 * 29 * <li>Dashed nodes are place holders for either a sequence of linked 30 * {@link BasicState} states or the inclusion of a block representing a nested 31 * construct in one of the forms below.</li> 32 * 33 * <li>Nodes showing multiple outgoing alternatives with a {@code ...} support 34 * any number of alternatives (one or more). Nodes without the {@code ...} only 35 * support the exact number of alternatives shown in the diagram.</li> 36 * 37 * </ul> 38 * 39 * <h2>Basic Blocks</h2> 40 * 41 * <h3>Rule</h3> 42 * 43 * <embed src="images/Rule.svg" type="image/svg+xml"/> 44 * 45 * <h3>Block of 1 or more alternatives</h3> 46 * 47 * <embed src="images/Block.svg" type="image/svg+xml"/> 48 * 49 * <h2>Greedy Loops</h2> 50 * 51 * <h3>Greedy Closure: {@code (...)*}</h3> 52 * 53 * <embed src="images/ClosureGreedy.svg" type="image/svg+xml"/> 54 * 55 * <h3>Greedy Positive Closure: {@code (...)+}</h3> 56 * 57 * <embed src="images/PositiveClosureGreedy.svg" type="image/svg+xml"/> 58 * 59 * <h3>Greedy Optional: {@code (...)?}</h3> 60 * 61 * <embed src="images/OptionalGreedy.svg" type="image/svg+xml"/> 62 * 63 * <h2>Non-Greedy Loops</h2> 64 * 65 * <h3>Non-Greedy Closure: {@code (...)*?}</h3> 66 * 67 * <embed src="images/ClosureNonGreedy.svg" type="image/svg+xml"/> 68 * 69 * <h3>Non-Greedy Positive Closure: {@code (...)+?}</h3> 70 * 71 * <embed src="images/PositiveClosureNonGreedy.svg" type="image/svg+xml"/> 72 * 73 * <h3>Non-Greedy Optional: {@code (...)??}</h3> 74 * 75 * <embed src="images/OptionalNonGreedy.svg" type="image/svg+xml"/> 76 */ 77 public abstract class ATNState { 78 public static final int INITIAL_NUM_TRANSITIONS = 4; 79 80 // constants for serialization 81 public static final int INVALID_TYPE = 0; 82 public static final int BASIC = 1; 83 public static final int RULE_START = 2; 84 public static final int BLOCK_START = 3; 85 public static final int PLUS_BLOCK_START = 4; 86 public static final int STAR_BLOCK_START = 5; 87 public static final int TOKEN_START = 6; 88 public static final int RULE_STOP = 7; 89 public static final int BLOCK_END = 8; 90 public static final int STAR_LOOP_BACK = 9; 91 public static final int STAR_LOOP_ENTRY = 10; 92 public static final int PLUS_LOOP_BACK = 11; 93 public static final int LOOP_END = 12; 94 95 public static final List<String> serializationNames = 96 Collections.unmodifiableList(Arrays.asList( 97 "INVALID", 98 "BASIC", 99 "RULE_START", 100 "BLOCK_START", 101 "PLUS_BLOCK_START", 102 "STAR_BLOCK_START", 103 "TOKEN_START", 104 "RULE_STOP", 105 "BLOCK_END", 106 "STAR_LOOP_BACK", 107 "STAR_LOOP_ENTRY", 108 "PLUS_LOOP_BACK", 109 "LOOP_END" 110 )); 111 112 public static final int INVALID_STATE_NUMBER = -1; 113 114 /** Which ATN are we in? */ 115 public ATN atn = null; 116 117 public int stateNumber = INVALID_STATE_NUMBER; 118 119 public int ruleIndex; // at runtime, we don't have Rule objects 120 121 public boolean epsilonOnlyTransitions = false; 122 123 /** Track the transitions emanating from this ATN state. */ 124 protected final List<Transition> transitions = 125 new ArrayList<Transition>(INITIAL_NUM_TRANSITIONS); 126 127 /** Used to cache lookahead during parsing, not used during construction */ 128 public IntervalSet nextTokenWithinRule; 129 130 @Override hashCode()131 public int hashCode() { return stateNumber; } 132 133 @Override equals(Object o)134 public boolean equals(Object o) { 135 // are these states same object? 136 if ( o instanceof ATNState ) return stateNumber==((ATNState)o).stateNumber; 137 return false; 138 } 139 isNonGreedyExitState()140 public boolean isNonGreedyExitState() { 141 return false; 142 } 143 144 @Override toString()145 public String toString() { 146 return String.valueOf(stateNumber); 147 } 148 getTransitions()149 public Transition[] getTransitions() { 150 return transitions.toArray(new Transition[transitions.size()]); 151 } 152 getNumberOfTransitions()153 public int getNumberOfTransitions() { 154 return transitions.size(); 155 } 156 addTransition(Transition e)157 public void addTransition(Transition e) { 158 addTransition(transitions.size(), e); 159 } 160 addTransition(int index, Transition e)161 public void addTransition(int index, Transition e) { 162 if (transitions.isEmpty()) { 163 epsilonOnlyTransitions = e.isEpsilon(); 164 } 165 else if (epsilonOnlyTransitions != e.isEpsilon()) { 166 System.err.format(Locale.getDefault(), "ATN state %d has both epsilon and non-epsilon transitions.\n", stateNumber); 167 epsilonOnlyTransitions = false; 168 } 169 170 boolean alreadyPresent = false; 171 for (Transition t : transitions) { 172 if ( t.target.stateNumber == e.target.stateNumber ) { 173 if ( t.label()!=null && e.label()!=null && t.label().equals(e.label()) ) { 174 // System.err.println("Repeated transition upon "+e.label()+" from "+stateNumber+"->"+t.target.stateNumber); 175 alreadyPresent = true; 176 break; 177 } 178 else if ( t.isEpsilon() && e.isEpsilon() ) { 179 // System.err.println("Repeated epsilon transition from "+stateNumber+"->"+t.target.stateNumber); 180 alreadyPresent = true; 181 break; 182 } 183 } 184 } 185 if ( !alreadyPresent ) { 186 transitions.add(index, e); 187 } 188 } 189 transition(int i)190 public Transition transition(int i) { return transitions.get(i); } 191 setTransition(int i, Transition e)192 public void setTransition(int i, Transition e) { 193 transitions.set(i, e); 194 } 195 removeTransition(int index)196 public Transition removeTransition(int index) { 197 return transitions.remove(index); 198 } 199 getStateType()200 public abstract int getStateType(); 201 onlyHasEpsilonTransitions()202 public final boolean onlyHasEpsilonTransitions() { 203 return epsilonOnlyTransitions; 204 } 205 setRuleIndex(int ruleIndex)206 public void setRuleIndex(int ruleIndex) { this.ruleIndex = ruleIndex; } 207 } 208
