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.AbstractEqualityComparator; 10 import org.antlr.v4.runtime.misc.Array2DHashSet; 11 import org.antlr.v4.runtime.misc.DoubleKeyMap; 12 13 import java.util.ArrayList; 14 import java.util.BitSet; 15 import java.util.Collection; 16 import java.util.HashSet; 17 import java.util.Iterator; 18 import java.util.List; 19 import java.util.Set; 20 21 /** 22 * Specialized {@link Set}{@code <}{@link ATNConfig}{@code >} that can track 23 * info about the set, with support for combining similar configurations using a 24 * graph-structured stack. 25 */ 26 public class ATNConfigSet implements Set<ATNConfig> { 27 /** 28 * The reason that we need this is because we don't want the hash map to use 29 * the standard hash code and equals. We need all configurations with the same 30 * {@code (s,i,_,semctx)} to be equal. Unfortunately, this key effectively doubles 31 * the number of objects associated with ATNConfigs. The other solution is to 32 * use a hash table that lets us specify the equals/hashcode operation. 33 */ 34 public static class ConfigHashSet extends AbstractConfigHashSet { ConfigHashSet()35 public ConfigHashSet() { 36 super(ConfigEqualityComparator.INSTANCE); 37 } 38 } 39 40 public static final class ConfigEqualityComparator extends AbstractEqualityComparator<ATNConfig> { 41 public static final ConfigEqualityComparator INSTANCE = new ConfigEqualityComparator(); 42 ConfigEqualityComparator()43 private ConfigEqualityComparator() { 44 } 45 46 @Override hashCode(ATNConfig o)47 public int hashCode(ATNConfig o) { 48 int hashCode = 7; 49 hashCode = 31 * hashCode + o.state.stateNumber; 50 hashCode = 31 * hashCode + o.alt; 51 hashCode = 31 * hashCode + o.semanticContext.hashCode(); 52 return hashCode; 53 } 54 55 @Override equals(ATNConfig a, ATNConfig b)56 public boolean equals(ATNConfig a, ATNConfig b) { 57 if ( a==b ) return true; 58 if ( a==null || b==null ) return false; 59 return a.state.stateNumber==b.state.stateNumber 60 && a.alt==b.alt 61 && a.semanticContext.equals(b.semanticContext); 62 } 63 } 64 65 /** Indicates that the set of configurations is read-only. Do not 66 * allow any code to manipulate the set; DFA states will point at 67 * the sets and they must not change. This does not protect the other 68 * fields; in particular, conflictingAlts is set after 69 * we've made this readonly. 70 */ 71 protected boolean readonly = false; 72 73 /** 74 * All configs but hashed by (s, i, _, pi) not including context. Wiped out 75 * when we go readonly as this set becomes a DFA state. 76 */ 77 public AbstractConfigHashSet configLookup; 78 79 /** Track the elements as they are added to the set; supports get(i) */ 80 public final ArrayList<ATNConfig> configs = new ArrayList<ATNConfig>(7); 81 82 // TODO: these fields make me pretty uncomfortable but nice to pack up info together, saves recomputation 83 // TODO: can we track conflicts as they are added to save scanning configs later? 84 public int uniqueAlt; 85 /** Currently this is only used when we detect SLL conflict; this does 86 * not necessarily represent the ambiguous alternatives. In fact, 87 * I should also point out that this seems to include predicated alternatives 88 * that have predicates that evaluate to false. Computed in computeTargetState(). 89 */ 90 protected BitSet conflictingAlts; 91 92 // Used in parser and lexer. In lexer, it indicates we hit a pred 93 // while computing a closure operation. Don't make a DFA state from this. 94 public boolean hasSemanticContext; 95 public boolean dipsIntoOuterContext; 96 97 /** Indicates that this configuration set is part of a full context 98 * LL prediction. It will be used to determine how to merge $. With SLL 99 * it's a wildcard whereas it is not for LL context merge. 100 */ 101 public final boolean fullCtx; 102 103 private int cachedHashCode = -1; 104 ATNConfigSet(boolean fullCtx)105 public ATNConfigSet(boolean fullCtx) { 106 configLookup = new ConfigHashSet(); 107 this.fullCtx = fullCtx; 108 } ATNConfigSet()109 public ATNConfigSet() { this(true); } 110 ATNConfigSet(ATNConfigSet old)111 public ATNConfigSet(ATNConfigSet old) { 112 this(old.fullCtx); 113 addAll(old); 114 this.uniqueAlt = old.uniqueAlt; 115 this.conflictingAlts = old.conflictingAlts; 116 this.hasSemanticContext = old.hasSemanticContext; 117 this.dipsIntoOuterContext = old.dipsIntoOuterContext; 118 } 119 120 @Override add(ATNConfig config)121 public boolean add(ATNConfig config) { 122 return add(config, null); 123 } 124 125 /** 126 * Adding a new config means merging contexts with existing configs for 127 * {@code (s, i, pi, _)}, where {@code s} is the 128 * {@link ATNConfig#state}, {@code i} is the {@link ATNConfig#alt}, and 129 * {@code pi} is the {@link ATNConfig#semanticContext}. We use 130 * {@code (s,i,pi)} as key. 131 * 132 * <p>This method updates {@link #dipsIntoOuterContext} and 133 * {@link #hasSemanticContext} when necessary.</p> 134 */ add( ATNConfig config, DoubleKeyMap<PredictionContext,PredictionContext,PredictionContext> mergeCache)135 public boolean add( 136 ATNConfig config, 137 DoubleKeyMap<PredictionContext,PredictionContext,PredictionContext> mergeCache) 138 { 139 if ( readonly ) throw new IllegalStateException("This set is readonly"); 140 if ( config.semanticContext!=SemanticContext.NONE ) { 141 hasSemanticContext = true; 142 } 143 if (config.getOuterContextDepth() > 0) { 144 dipsIntoOuterContext = true; 145 } 146 ATNConfig existing = configLookup.getOrAdd(config); 147 if ( existing==config ) { // we added this new one 148 cachedHashCode = -1; 149 configs.add(config); // track order here 150 return true; 151 } 152 // a previous (s,i,pi,_), merge with it and save result 153 boolean rootIsWildcard = !fullCtx; 154 PredictionContext merged = 155 PredictionContext.merge(existing.context, config.context, rootIsWildcard, mergeCache); 156 // no need to check for existing.context, config.context in cache 157 // since only way to create new graphs is "call rule" and here. We 158 // cache at both places. 159 existing.reachesIntoOuterContext = 160 Math.max(existing.reachesIntoOuterContext, config.reachesIntoOuterContext); 161 162 // make sure to preserve the precedence filter suppression during the merge 163 if (config.isPrecedenceFilterSuppressed()) { 164 existing.setPrecedenceFilterSuppressed(true); 165 } 166 167 existing.context = merged; // replace context; no need to alt mapping 168 return true; 169 } 170 171 /** Return a List holding list of configs */ elements()172 public List<ATNConfig> elements() { return configs; } 173 getStates()174 public Set<ATNState> getStates() { 175 Set<ATNState> states = new HashSet<ATNState>(); 176 for (ATNConfig c : configs) { 177 states.add(c.state); 178 } 179 return states; 180 } 181 182 /** 183 * Gets the complete set of represented alternatives for the configuration 184 * set. 185 * 186 * @return the set of represented alternatives in this configuration set 187 * 188 * @since 4.3 189 */ 190 getAlts()191 public BitSet getAlts() { 192 BitSet alts = new BitSet(); 193 for (ATNConfig config : configs) { 194 alts.set(config.alt); 195 } 196 return alts; 197 } 198 getPredicates()199 public List<SemanticContext> getPredicates() { 200 List<SemanticContext> preds = new ArrayList<SemanticContext>(); 201 for (ATNConfig c : configs) { 202 if ( c.semanticContext!=SemanticContext.NONE ) { 203 preds.add(c.semanticContext); 204 } 205 } 206 return preds; 207 } 208 get(int i)209 public ATNConfig get(int i) { return configs.get(i); } 210 optimizeConfigs(ATNSimulator interpreter)211 public void optimizeConfigs(ATNSimulator interpreter) { 212 if ( readonly ) throw new IllegalStateException("This set is readonly"); 213 if ( configLookup.isEmpty() ) return; 214 215 for (ATNConfig config : configs) { 216 // int before = PredictionContext.getAllContextNodes(config.context).size(); 217 config.context = interpreter.getCachedContext(config.context); 218 // int after = PredictionContext.getAllContextNodes(config.context).size(); 219 // System.out.println("configs "+before+"->"+after); 220 } 221 } 222 223 @Override addAll(Collection<? extends ATNConfig> coll)224 public boolean addAll(Collection<? extends ATNConfig> coll) { 225 for (ATNConfig c : coll) add(c); 226 return false; 227 } 228 229 @Override equals(Object o)230 public boolean equals(Object o) { 231 if (o == this) { 232 return true; 233 } 234 else if (!(o instanceof ATNConfigSet)) { 235 return false; 236 } 237 238 // System.out.print("equals " + this + ", " + o+" = "); 239 ATNConfigSet other = (ATNConfigSet)o; 240 boolean same = configs!=null && 241 configs.equals(other.configs) && // includes stack context 242 this.fullCtx == other.fullCtx && 243 this.uniqueAlt == other.uniqueAlt && 244 this.conflictingAlts == other.conflictingAlts && 245 this.hasSemanticContext == other.hasSemanticContext && 246 this.dipsIntoOuterContext == other.dipsIntoOuterContext; 247 248 // System.out.println(same); 249 return same; 250 } 251 252 @Override hashCode()253 public int hashCode() { 254 if (isReadonly()) { 255 if (cachedHashCode == -1) { 256 cachedHashCode = configs.hashCode(); 257 } 258 259 return cachedHashCode; 260 } 261 262 return configs.hashCode(); 263 } 264 265 @Override size()266 public int size() { 267 return configs.size(); 268 } 269 270 @Override isEmpty()271 public boolean isEmpty() { 272 return configs.isEmpty(); 273 } 274 275 @Override contains(Object o)276 public boolean contains(Object o) { 277 if (configLookup == null) { 278 throw new UnsupportedOperationException("This method is not implemented for readonly sets."); 279 } 280 281 return configLookup.contains(o); 282 } 283 containsFast(ATNConfig obj)284 public boolean containsFast(ATNConfig obj) { 285 if (configLookup == null) { 286 throw new UnsupportedOperationException("This method is not implemented for readonly sets."); 287 } 288 289 return configLookup.containsFast(obj); 290 } 291 292 @Override iterator()293 public Iterator<ATNConfig> iterator() { 294 return configs.iterator(); 295 } 296 297 @Override clear()298 public void clear() { 299 if ( readonly ) throw new IllegalStateException("This set is readonly"); 300 configs.clear(); 301 cachedHashCode = -1; 302 configLookup.clear(); 303 } 304 isReadonly()305 public boolean isReadonly() { 306 return readonly; 307 } 308 setReadonly(boolean readonly)309 public void setReadonly(boolean readonly) { 310 this.readonly = readonly; 311 configLookup = null; // can't mod, no need for lookup cache 312 } 313 314 @Override toString()315 public String toString() { 316 StringBuilder buf = new StringBuilder(); 317 buf.append(elements().toString()); 318 if ( hasSemanticContext ) buf.append(",hasSemanticContext=").append(hasSemanticContext); 319 if ( uniqueAlt!=ATN.INVALID_ALT_NUMBER ) buf.append(",uniqueAlt=").append(uniqueAlt); 320 if ( conflictingAlts!=null ) buf.append(",conflictingAlts=").append(conflictingAlts); 321 if ( dipsIntoOuterContext ) buf.append(",dipsIntoOuterContext"); 322 return buf.toString(); 323 } 324 325 // satisfy interface 326 327 @Override toArray()328 public ATNConfig[] toArray() { 329 return configLookup.toArray(); 330 } 331 332 @Override toArray(T[] a)333 public <T> T[] toArray(T[] a) { 334 return configLookup.toArray(a); 335 } 336 337 @Override remove(Object o)338 public boolean remove(Object o) { 339 throw new UnsupportedOperationException(); 340 } 341 342 @Override containsAll(Collection<?> c)343 public boolean containsAll(Collection<?> c) { 344 throw new UnsupportedOperationException(); 345 } 346 347 @Override retainAll(Collection<?> c)348 public boolean retainAll(Collection<?> c) { 349 throw new UnsupportedOperationException(); 350 } 351 352 @Override removeAll(Collection<?> c)353 public boolean removeAll(Collection<?> c) { 354 throw new UnsupportedOperationException(); 355 } 356 357 public static abstract class AbstractConfigHashSet extends Array2DHashSet<ATNConfig> { 358 AbstractConfigHashSet(AbstractEqualityComparator<? super ATNConfig> comparator)359 public AbstractConfigHashSet(AbstractEqualityComparator<? super ATNConfig> comparator) { 360 this(comparator, 16, 2); 361 } 362 AbstractConfigHashSet(AbstractEqualityComparator<? super ATNConfig> comparator, int initialCapacity, int initialBucketCapacity)363 public AbstractConfigHashSet(AbstractEqualityComparator<? super ATNConfig> comparator, int initialCapacity, int initialBucketCapacity) { 364 super(comparator, initialCapacity, initialBucketCapacity); 365 } 366 367 @Override asElementType(Object o)368 protected final ATNConfig asElementType(Object o) { 369 if (!(o instanceof ATNConfig)) { 370 return null; 371 } 372 373 return (ATNConfig)o; 374 } 375 376 @Override createBuckets(int capacity)377 protected final ATNConfig[][] createBuckets(int capacity) { 378 return new ATNConfig[capacity][]; 379 } 380 381 @Override createBucket(int capacity)382 protected final ATNConfig[] createBucket(int capacity) { 383 return new ATNConfig[capacity]; 384 } 385 386 } 387 } 388