make the BacktrackingSequencer deterministic in ambiguous situations

3 files changed, 52 insertions, 18 deletions

diff --git a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/ISemanticSequencerNfaProvider.java b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/ISemanticSequencerNfaProvider.java
index a9368c1..7885b00 100644
--- a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/ISemanticSequencerNfaProvider.java
+++ b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/ISemanticSequencerNfaProvider.java
@@ -28,13 +28,15 @@ public interface ISemanticSequencerNfaProvider {
 		BitSet getAllFollowerFeatures();
 
 		AbstractElement getAssignedGrammarElement();
-		
+
 		EStructuralFeature getFeature();
 
 		int getFeatureID();
 
 		List<ISemState> getFollowers();
 
+		int getOrderID();
+
 		List<AbstractElement> getToBeValidatedAssignedElements();
 	}
 
diff --git a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/SemanticSequencerNfaProvider.java b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/SemanticSequencerNfaProvider.java
index fa76f7e..d0be1c5 100644
--- a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/SemanticSequencerNfaProvider.java
+++ b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/analysis/SemanticSequencerNfaProvider.java
@@ -22,7 +22,10 @@ import org.eclipse.emf.ecore.util.EcoreUtil;
 import org.eclipse.xtext.AbstractElement;
 import org.eclipse.xtext.Action;
 import org.eclipse.xtext.CrossReference;
+import org.eclipse.xtext.EcoreUtil2;
 import org.eclipse.xtext.GrammarUtil;
+import org.eclipse.xtext.IGrammarAccess;
+import org.eclipse.xtext.ParserRule;
 import org.eclipse.xtext.grammaranalysis.impl.GrammarElementTitleSwitch;
 import org.eclipse.xtext.serializer.analysis.ISyntacticSequencerPDAProvider.ISynAbsorberState;
 import org.eclipse.xtext.serializer.analysis.ISyntacticSequencerPDAProvider.SynAbsorberNfaAdapter;
@@ -74,13 +77,14 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 
 	protected static class SemState implements ISemState {
 
+		protected BitSet allFollowerFeatures;
 		protected AbstractElement assignedGrammarElement;
+		protected List<AbstractElement> contentValidationNeeded;
 		protected EStructuralFeature feature;
 		protected int featureID = -2;
 		protected List<ISemState> followers;
+		protected int orderID = 0;
 		protected EClass type;
-		protected List<AbstractElement> contentValidationNeeded;
-		protected BitSet allFollowerFeatures;
 
 		public SemState(EClass type, AbstractElement assignedGrammarElement) {
 			super();
@@ -114,6 +118,10 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 			return followers == null ? Collections.<ISemState> emptyList() : followers;
 		}
 
+		public int getOrderID() {
+			return orderID;
+		}
+
 		public List<AbstractElement> getToBeValidatedAssignedElements() {
 			return contentValidationNeeded;
 		}
@@ -144,14 +152,40 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 
 	}
 
+	protected Map<AbstractElement, Integer> elementIDCache;
+
+	@Inject
+	protected IGrammarAccess grammar;
+
 	@Inject
 	protected ISyntacticSequencerPDAProvider pdaProvider;
 
-	protected Map<Pair<EObject, EClass>, Nfa<ISemState>> cache = Maps.newHashMap();
+	protected Map<Pair<EObject, EClass>, Nfa<ISemState>> resultCache = Maps.newHashMap();
+
+	protected boolean addAll(BitSet to, BitSet bits) {
+		BitSet cpy = new BitSet();
+		cpy.or(to);
+		cpy.or(bits);
+		if (cpy.equals(to))
+			return false;
+		to.or(bits);
+		return true;
+	}
+
+	protected int getElementID(AbstractElement ele) {
+		if (elementIDCache == null) {
+			elementIDCache = Maps.newHashMap();
+			int counter = 0;
+			for (ParserRule pr : GrammarUtil.allParserRules(grammar.getGrammar()))
+				for (AbstractElement e : EcoreUtil2.getAllContentsOfType(pr, AbstractElement.class))
+					elementIDCache.put(e, counter++);
+		}
+		return elementIDCache.get(ele);
+	}
 
 	public Nfa<ISemState> getNFA(EObject context, EClass type) {
 		Pair<EObject, EClass> key = Tuples.create(context, type);
-		Nfa<ISemState> nfa = cache.get(key);
+		Nfa<ISemState> nfa = resultCache.get(key);
 		if (nfa != null)
 			return nfa;
 		NfaUtil util = new NfaUtil();
@@ -162,8 +196,9 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 		//		util.sortInplace(nfa, distanceMap);
 		initContentValidationNeeded(type, nfa);
 		initRemainingFeatures(nfa.getStop(), util.inverse(nfa), Sets.<ISemState> newHashSet());
+		initOrderIDs(nfa);
 		//		System.out.println(new NfaFormatter().format(nfa));
-		cache.put(key, nfa);
+		resultCache.put(key, nfa);
 		return nfa;
 	}
 
@@ -183,6 +218,12 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 				((SemState) state).contentValidationNeeded = Collections.emptyList();
 	}
 
+	protected void initOrderIDs(Nfa<ISemState> nfa) {
+		for (ISemState state : new NfaUtil().collect(nfa))
+			if (state.getAssignedGrammarElement() != null)
+				((SemState) state).orderID = getElementID(state.getAssignedGrammarElement());
+	}
+
 	protected void initRemainingFeatures(ISemState state, Nfa<ISemState> inverseNfa, Set<ISemState> visited) {
 		BitSet features = state.getAllFollowerFeatures();
 		if (state.getFeature() != null) {
@@ -198,16 +239,6 @@ public class SemanticSequencerNfaProvider implements ISemanticSequencerNfaProvid
 		}
 	}
 
-	protected boolean addAll(BitSet to, BitSet bits) {
-		BitSet cpy = new BitSet();
-		cpy.or(to);
-		cpy.or(bits);
-		if (cpy.equals(to))
-			return false;
-		to.or(bits);
-		return true;
-	}
-
 	protected boolean isContentValidationNeeded(Collection<AbstractElement> ass) {
 		if (ass == null || ass.size() < 2)
 			return false;
diff --git a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/sequencer/BacktrackingSemanticSequencer.java b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/sequencer/BacktrackingSemanticSequencer.java
index 7ac3e4e..b4b661a 100644
--- a/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/sequencer/BacktrackingSemanticSequencer.java
+++ b/plugins/org.eclipse.xtext/src/org/eclipse/xtext/serializer/sequencer/BacktrackingSemanticSequencer.java
@@ -25,7 +25,6 @@ import org.eclipse.xtext.nodemodel.ICompositeNode;
 import org.eclipse.xtext.nodemodel.ILeafNode;
 import org.eclipse.xtext.nodemodel.INode;
 import org.eclipse.xtext.serializer.acceptor.SequenceFeeder;
-import org.eclipse.xtext.serializer.analysis.Context2NameFunction;
 import org.eclipse.xtext.serializer.analysis.ISemanticSequencerNfaProvider;
 import org.eclipse.xtext.serializer.analysis.ISemanticSequencerNfaProvider.ISemState;
 import org.eclipse.xtext.serializer.diagnostic.ISemanticSequencerDiagnosticProvider;
@@ -85,7 +84,9 @@ public class BacktrackingSemanticSequencer extends AbstractSemanticSequencer {
 				return 1;
 			if (o2Cnt == 0 && o1Cnt > 0)
 				return -1;
-			return 0;
+			int o1id = o1.getOrderID();
+			int o2id = o2.getOrderID();
+			return o1id < o2id ? -1 : o1id > o2id ? 1 : 0;
 		}
 
 	}