FSM.java
001 /*
002  *  FSM.java
003  *
004  *  Copyright (c) 1995-2012, The University of Sheffield. See the file
005  *  COPYRIGHT.txt in the software or at http://gate.ac.uk/gate/COPYRIGHT.txt
006  *
007  *  This file is part of GATE (see http://gate.ac.uk/), and is free
008  *  software, licenced under the GNU Library General Public License,
009  *  Version 2, June 1991 (in the distribution as file licence.html,
010  *  and also available at http://gate.ac.uk/gate/licence.html).
011  *
012  *  Valentin Tablan, 29/Mar/2000
013  *
014  *  $Id: FSM.java 17595 2014-03-08 13:05:32Z markagreenwood $
015  */
016 
017 package gate.fsm;
018 
019 import java.util.*;
020 
021 import gate.jape.*;
022 import gate.util.Benchmark;
023 import gate.util.SimpleArraySet;
024 import static gate.jape.KleeneOperator.Type.*;
025 
026 /**
027   * This class implements a standard Finite State Machine.
028   * It is used for both deterministic and non-deterministic machines.
029   */
030 public class FSM implements JapeConstants {
031   
032   private static final long serialVersionUID = -7088856970776558801L;
033   
034   private List<RuleTime> ruleTimes = new ArrayList<RuleTime>();
035   
036   public List<RuleTime> getRuleTimes() {
037     return ruleTimes;
038   }
039 
040   private void decorateStates() {
041     HashMap<String,Integer>  temporaryRuleNameToIndexMap = new HashMap<String,Integer>();
042     ruleTimes.add(new RuleTime(0,State.INITIAL_RULE));
043     ruleTimes.add(new RuleTime(0,State.UNKNOWN_RULE));
044     ruleTimes.add(new RuleTime(0,State.UNVISITED_RULE));
045     int ruleIndex = State.INITIAL_INDEX;
046     for (Transition t : this.getInitialState().getTransitions()) {
047       ruleIndex = t.getTarget().getRuleForState(temporaryRuleNameToIndexMap, ruleTimes);
048       assert (ruleIndex != State.UNVISITED_INDEX&& (ruleIndex != State.UNKNOWN_INDEX);
049     }
050     this.getInitialState().setIndexInRuleList(State.INITIAL_INDEX);
051   }
052 
053 
054   /** Debug flag */
055   private static final boolean DEBUG = false;
056 
057   /**
058    * The constructor that all the other constructors should call.
059    */
060   protected FSM() {
061     initialState = new State();
062   }
063 
064   /**
065     * Builds a standalone FSM starting from a single phase transducer.
066     @param spt the single phase transducer to be used for building this FSM.
067     */
068   public FSM(SinglePhaseTransducer spt){
069     this();
070     addRules(spt.getRules());
071     if (Benchmark.isBenchmarkingEnabled()) {
072       this.decorateStates();
073     }
074   }
075 
076   /**
077    * Do the work involved in creating an FSM from a PrioritisedRuleList.
078    */
079   protected void addRules(PrioritisedRuleList rules) {
080     Iterator<Rule> rulesEnum = rules.iterator();
081 
082     while(rulesEnum.hasNext()){
083       FSM ruleFSM = spawn(rulesEnum.next());
084 
085       //added by Karter start -> JapeDebugger
086       ruleHash.putAll(ruleFSM.ruleHash);
087       //added by Karter end
088 
089       initialState.addTransition(new Transition(null,
090                                                 ruleFSM.getInitialState()));
091     }
092 
093     eliminateVoidTransitions();
094   }
095 
096   /**
097     * Builds a FSM starting from a rule. This FSM is actually a part of a larger
098     * one (usually the one that is built based on the single phase transducer
099     * that contains the rule).
100     * built by this constructor.
101     @param rule the rule to be used for the building process.
102     */
103   public FSM(Rule rule) {
104     this();
105     setRule(rule);
106   }
107 
108 
109   /**
110    * Do the work involved in creating an FSM from a Rule.
111    */
112   protected void setRule(Rule rule) {
113 
114     LeftHandSide lhs = rule.getLHS();
115 
116     //added by Karter start -> JapeDebugger
117     LinkedList<String> ll = new LinkedList<String>();
118     String label = currentLHSBinding(lhs);
119     ll.add(label);
120     ruleHash.put(rule.getName(), label);
121     //added by Karter end
122 
123 
124     PatternElement[][] constraints =
125                        lhs.getConstraintGroup().getPatternElementDisjunction();
126     // the rectangular array constraints is a disjunction of sequences of
127     // constraints = [[PE]:[PE]...[PE] ||
128     //                [PE]:[PE]...[PE] ||
129     //                ...
130     //                [PE]:[PE]...[PE] ]
131 
132     //The current and the next state for the current ROW.
133     State currentRowState, nextRowState;
134     State finalState = new State();
135     PatternElement currentPattern;
136 
137     for(int i = 0; i < constraints.length; i++){
138       // for each row we have to create a sequence of states that will accept
139       // the sequence of annotations described by the restrictions on that row.
140       // The final state of such a sequence will always be a final state which
141       // will have associated the right hand side of the rule used for this
142       // constructor.
143 
144       // For each row we will start from the initial state.
145       currentRowState = initialState;
146       for(int j=0; j < constraints[i].length; j++) {
147 
148         // parse the sequence of constraints:
149         // For each basic pattern element add a new state and link it to the
150         // currentRowState.
151         // The case of kleene operators has to be considered!
152         currentPattern = constraints[i][j];
153         State insulator = new State();
154         currentRowState.addTransition(new Transition(null,insulator));
155         currentRowState = insulator;
156         if(currentPattern instanceof BasicPatternElement) {
157           //the easy case
158           nextRowState = new State();
159 
160           //added by Karter start -> JapeDebugger
161           LinkedList<String> sll = new LinkedList<String>();
162           sll.add(currentBasicBinding( (BasicPatternElementcurrentPattern));
163           currentRowState.addTransition(
164               new Transition( (BasicPatternElementcurrentPattern,
165                              nextRowState
166                              /*added by Karter*/, sll));
167           //added by Karter end
168 
169           currentRowState = nextRowState;
170         else if(currentPattern instanceof ComplexPatternElement) {
171 
172           // the current pattern is a complex pattern element
173           // ..it will probaly be converted into a sequence of states itself.
174 
175           //  -> JapeDebugger
176           currentRowState = convertComplexPE(
177               currentRowState,
178               (ComplexPatternElementcurrentPattern,
179               /*changed by Karter "new LinkedList()"*/ll);
180 
181         else {
182           // we got an unknown kind of pattern
183           throw new RuntimeException("Strange looking pattern: " +
184                                      currentPattern);
185         }
186 
187       // for j
188 
189       //link the end of the current row to the final state using
190       //an empty transition.
191       currentRowState.addTransition(new Transition(null,finalState));
192       finalState.setAction(rule.getRHS());
193       finalState.setFileIndex(rule.getPosition());
194       finalState.setPriority(rule.getPriority());
195     // for i
196   }
197 
198   /**
199    * Builds a FSM starting from a ComplexPatternElement. This FSM is usually
200    * part of a larger FSM based on the Rule that contains the
201    * ComplexPatternElement.
202    *
203    @param cpe
204    *            the ComplexPatternElement to be used for the building process.
205    */
206   protected FSM(ComplexPatternElement cpe) {
207       this();
208       finalState = convertComplexPE(initialState, cpe, new LinkedList<String>());
209       finalState.isFinal = true;
210   }
211 
212   /**
213    * A factory method for new FSMs like this one, given a Rule object.
214    */
215   protected FSM spawn(Rule r) {
216     return new FSM(r);
217   }
218 
219   /**
220    * A factory method for new FSMs like this one, given a ComplexPatternElement
221    * object.
222    */
223   protected FSM spawn(ComplexPatternElement currentPattern) {
224       return new FSM(currentPattern);
225   }
226 
227   /**
228     * Gets the initial state of this FSM
229     @return an object of type gate.fsm.State representing the initial state.
230     */
231   public State getInitialState() {
232     return initialState;
233   // getInitialState
234 
235   /**
236     * Receives a state to start from and a complex pattern element.
237     * Parses the complex pattern element and creates all the necessary states
238     * and transitions for accepting annotations described by the given PE.
239     @param startState the state to start from
240     @param cpe the pattern to be recognized
241     @param labels the bindings name for all the annotation accepted along
242     * the way. This is actually a list of Strings. It is necessary to use
243     * a list because of the recursive definition of ComplexPatternElement.
244     @return the final state reached after accepting a sequence of annotations
245     * as described in the pattern
246     */
247   private State convertComplexPE(State startState,
248           ComplexPatternElement cpe, LinkedList<String> labels){
249 
250     State endState = generateStates(startState, cpe, labels);
251 
252     // now take care of the kleene operator
253     KleeneOperator kleeneOp = cpe.getKleeneOp();
254     KleeneOperator.Type type = kleeneOp.getType();
255     if (type == OPTIONAL) {
256       //allow to skip everything via a null transition
257       startState.addTransition(new Transition(null,endState));
258     }
259     else if (type == PLUS) {
260       // allow to return to startState
261       endState.addTransition(new Transition(null,startState));
262     }
263     else if (type == STAR) {
264       // allow to skip everything via a null transition
265       startState.addTransition(new Transition(null,endState));
266 
267       // allow to return to startState
268       endState.addTransition(new Transition(null,startState));
269     }
270     else if (type == RANGE) {
271       Integer min = kleeneOp.getMin();
272       Integer max = kleeneOp.getMax();
273 
274       // keep a list of the start states for each possible optional sets so can make
275       // direct transitions from them to the final end state
276       List<State> startStateList = new ArrayList<State>();
277 
278       if (min == null || min == 0) {
279         //if min is empty or 0, allow to skip everything via a null transition
280         startStateList.add(startState);
281       }
282       else if (min > 1) {
283         // add min-1 copies of the set of states for the CPE.  It's -1 because
284         // one set was already added by the first generateStates call
285         int numCopies = min - 1;
286         for(int i = 1; i <= numCopies; i++) {
287           // the end state of the previous set always moves up to be the
288           // start state of the next set.
289           startState = endState;
290           endState = generateStates(startState, cpe, labels);
291         }
292       }
293 
294       if (max == null) {
295         // if there is no defined max, allow to return to startState any
296         // number of times.  Start state may be the original start or, if
297         // min > 1, then it's the start of the last set of states added.
298         // Example: A range with min 3 and max = unbounded will look like
299         // this:
300         //                                  v------|
301         // start1...end1->start2...end2->start3...end3->...
302         //
303         endState.addTransition(new Transition(null,startState));
304       }
305       else if (max > min) {
306         // there are some optional state sets.  Make a copy of the state
307         // set for each.
308         int numCopies = max-min;
309 
310         //if min == 0 then reduce numCopies by one since we already added
311         //one set of states that are optional
312         if (min == 0)
313           numCopies--;
314 
315         for(int i = 1; i <= numCopies; i++) {
316           startState = endState;
317           startStateList.add(startState);
318           endState = generateStates(startState, cpe, labels);
319         }
320       }
321 
322       //each of the optional stages can transition directly to the final end
323       for(State state : startStateList) {
324         state.addTransition(new Transition(null,endState));
325       }
326 
327     //end if type == RANGE
328 
329     return endState;
330   // convertComplexPE
331 
332   /**
333    * Receives a state to start from and a complex pattern element.
334    * Parses the complex pattern element and creates all the necessary states
335    * and transitions for traversing the annotations described by the given PE
336    * exactly once.  Does not add any transitions for kleene operators.
337    @param startState the state to start from
338    @param cpe the pattern to be recognized
339    @param labels the bindings name for all the annotation accepted along
340    * the way. This is actually a list of Strings. It is necessary to use
341    * a list because of the recursive definition of ComplexPatternElement.
342    @return the final state reached after accepting a sequence of annotations
343    * as described in the pattern
344    */
345   private State generateStates(State startState, ComplexPatternElement cpe,
346           LinkedList<String> labels) {
347     //create a copy
348     @SuppressWarnings("unchecked")
349     LinkedList<String> newBindings = (LinkedList<String>)labels.clone();
350     String localLabel = cpe.getBindingName ();
351 
352     if(localLabel != null)newBindings.add(localLabel);
353 
354     ConstraintGroup constraintGroup = cpe.getConstraintGroup();
355     PatternElement[][] constraints =
356                        constraintGroup.getPatternElementDisjunction();
357 
358     // the rectangular array constraints is a disjunction of sequences of
359     // constraints = [[PE]:[PE]...[PE] ||
360     //                [PE]:[PE]...[PE] ||
361     //                ...
362     //                [PE]:[PE]...[PE] ]
363 
364     //The current and the next state for the current ROW.
365     State currentRowState, nextRowState, endState = new State();
366     PatternElement currentPattern;
367 
368     for(int i = 0; i < constraints.length; i++) {
369       // for each row we have to create a sequence of states that will accept
370       // the sequence of annotations described by the restrictions on that row.
371       // The final state of such a sequence will always be a finale state which
372       // will have associated the right hand side of the rule used for this
373       // constructor.
374 
375       //For each row we will start from the initial state.
376       currentRowState = startState;
377       for(int j=0; j < (constraints[i]).length; j++) {
378 
379         //parse the sequence of constraints:
380         //For each basic pattern element add a new state and link it to the
381         //currentRowState.
382         //The case of kleene operators has to be considered!
383         State insulator = new State();
384         currentRowState.addTransition(new Transition(null,insulator));
385         currentRowState = insulator;
386         currentPattern = constraints[i][j];
387         if(currentPattern instanceof BasicPatternElement) {
388 
389           //the easy case
390           nextRowState = new State();
391 
392           //added by Karter start -> JapeDebugger
393           newBindings.add(currentBasicBinding( (BasicPatternElement)
394                                               currentPattern));
395           //added by Karter end
396 
397 
398           currentRowState.addTransition(
399             new Transition((BasicPatternElement)currentPattern,
400                             nextRowState,newBindings));
401           currentRowState = nextRowState;
402         else if(currentPattern instanceof ComplexPatternElement) {
403 
404           // the current pattern is a complex pattern element
405           // ..it will probaly be converted into a sequence of states itself.
406           currentRowState =  convertComplexPE(
407                               currentRowState,
408                               (ComplexPatternElement)currentPattern,
409                               newBindings);
410         else {
411 
412           //we got an unknown kind of pattern
413           throw new RuntimeException("Strange looking pattern:"+currentPattern);
414         }
415 
416       // for j
417         // link the end of the current row to the general end state using
418         // an empty transition.
419         currentRowState.addTransition(new Transition(null,endState));
420     // for i
421     return endState;
422   }
423 
424   /**
425     * Converts this FSM from a non-deterministic to a deterministic one by
426     * eliminating all the unrestricted transitions.
427     */
428   public void eliminateVoidTransitions() {
429 
430     dStates.clear()//kalina: replaced from new HashSet()
431     LinkedList<Set<State>> unmarkedDStates = new LinkedList<Set<State>>();
432     Set<State> currentDState = new HashSet<State>();
433     //kalina: prefer clear coz faster than init()
434     newStates.clear();
435 
436     currentDState.add(initialState);
437     currentDState = lambdaClosure(currentDState);
438     dStates.add(currentDState);
439     unmarkedDStates.add(currentDState);
440 
441     // create a new state that will take the place the set of states
442     // in currentDState
443     initialState = new State();
444     newStates.put(currentDState, initialState);
445 
446     // find out if the new state is a final one
447     Iterator<State> innerStatesIter = currentDState.iterator();
448     RightHandSide action = null;
449 
450     while(innerStatesIter.hasNext()){
451       State currentInnerState = innerStatesIter.next();
452       if(currentInnerState.isFinal()){
453         action = currentInnerState.getAction();
454         initialState.setAction(action);
455         initialState.setFileIndex(currentInnerState.getFileIndex());
456         initialState.setPriority(currentInnerState.getPriority());
457         break;
458       }
459     }
460 
461     while(!unmarkedDStates.isEmpty()) {
462       currentDState = unmarkedDStates.removeFirst();
463       Iterator<State> insideStatesIter = currentDState.iterator();
464 
465       while(insideStatesIter.hasNext()) {
466         State innerState = insideStatesIter.next();
467         Iterator<Transition> transIter = innerState.getTransitions().iterator();
468 
469         while(transIter.hasNext()) {
470           Transition currentTrans = transIter.next();
471 
472           if(currentTrans.getConstraints() !=null) {
473             State target = currentTrans.getTarget();
474             Set<State> newDState = new HashSet<State>();
475             newDState.add(target);
476             newDState = lambdaClosure(newDState);
477 
478             if(!dStates.contains(newDState)) {
479               dStates.add(newDState);
480               unmarkedDStates.add(newDState);
481               State newState = new State();
482               newStates.put(newDState, newState);
483 
484               //find out if the new state is a final one
485               innerStatesIter = newDState.iterator();
486               while(innerStatesIter.hasNext()) {
487                 State currentInnerState = innerStatesIter.next();
488 
489                 if(currentInnerState.isFinal()) {
490                   newState.setAction(
491                           currentInnerState.getAction());
492                   newState.setFileIndex(currentInnerState.getFileIndex());
493                   newState.setPriority(currentInnerState.getPriority());
494                   break;
495                 }
496               }
497             }// if(!dStates.contains(newDState))
498 
499             State currentState = newStates.get(currentDState);
500             State newState = newStates.get(newDState);
501             currentState.addTransition(new Transition(
502                                         currentTrans.getConstraints(),
503                                         newState,
504                                         currentTrans.getBindings()));
505           }// if(currentTrans.getConstraints() !=null)
506 
507         }// while(transIter.hasNext())
508 
509       }// while(insideStatesIter.hasNext())
510 
511     }// while(!unmarkedDstates.isEmpty())
512 
513     /*
514     //find final states
515     Iterator allDStatesIter = dStates.iterator();
516     while(allDStatesIter.hasNext()){
517       currentDState = (AbstractSet) allDStatesIter.next();
518       Iterator innerStatesIter = currentDState.iterator();
519       while(innerStatesIter.hasNext()){
520         State currentInnerState = (State) innerStatesIter.next();
521         if(currentInnerState.isFinal()){
522           State newState = (State)newStates.get(currentDState);
523 
524           newState.setAction(currentInnerState.getAction());
525           break;
526         }
527       }
528 
529     }
530     */
531     allStates = newStates.values();
532   }//eliminateVoidTransitions
533 
534   /*
535     * Computes the lambda-closure (aka epsilon closure) of the given set of
536     * states, that is the set of states that are accessible from any of the
537     * states in the given set using only unrestricted transitions.
538     * @return a set containing all the states accessible from this state via
539     * transitions that bear no restrictions.
540     */
541   private Set<State> lambdaClosure(Set<State> s) {
542     // the stack/queue used by the algorithm
543     LinkedList<State> list = new LinkedList<State>(s);
544 
545     // the set to be returned
546     Set<State> lambdaClosure = new HashSet<State>(s);
547     State top;
548     Iterator<Transition> transIter;
549     Transition currentTransition;
550     State currentState;
551     while(!list.isEmpty()){
552       top = list.removeFirst();
553       transIter = top.getTransitions().iterator();
554 
555       while(transIter.hasNext()){
556         currentTransition = transIter.next();
557 
558         if(currentTransition.getConstraints() == null){
559           currentState = currentTransition.getTarget();
560           if(!lambdaClosure.contains(currentState)){
561             lambdaClosure.add(currentState);
562             list.addFirst(currentState);
563           }// if(!lambdaClosure.contains(currentState))
564 
565         }// if(currentTransition.getConstraints() == null)
566 
567       }
568     }
569     return lambdaClosure;
570   // lambdaClosure
571 
572 
573   /**
574    * Two members used by forEachState().
575    */
576   protected State currentState;
577   protected Transition currentTransition;
578 
579   /**
580    * Iterates over all the states in this FSM, setting currentState and
581    * currentTransition, then calling the given Runnable callback.
582    */
583   protected void forEachState (java.lang.Runnable r) {
584     Set<State> stackToProcess = new HashSet<State>();
585     Set<State> processed = new HashSet<State>();
586 
587     stackToProcess.add(initialState);
588     while (!stackToProcess.isEmpty()) {
589       currentState = stackToProcess.iterator().next();
590       stackToProcess.remove(currentState);
591       processed.add(currentState);
592 
593       for(Transition t : currentState.getTransitions()) {
594         currentTransition = t;
595         State target = currentTransition.getTarget();
596         if (processed.contains(target|| stackToProcess.contains(target)) continue;
597         stackToProcess.add(target);
598 
599         r.run();
600       }
601     }
602   }
603 
604   /**
605    @return a Map whose keys contain the states of this FSM, and whose values
606    *         contain their corresponding transitions. This method actually walks
607    *         the FSM, so it may be called before the FSM is finalized with
608    *         compactTransitions().
609    */
610   public Map<State,SimpleArraySet<Transition>> getAllStates() {
611     /*
612      * This method can't use the allStates data member, since it's sometimes
613      * called before allStates is populated.
614      */
615 
616     Map<State,SimpleArraySet<Transition>> statesToReturn = new HashMap<State,SimpleArraySet<Transition>>();
617     Set<State> stackToProcess = new HashSet<State>();
618     Set<State> processed = new HashSet<State>();
619 
620     stackToProcess.add(initialState);
621     while (!stackToProcess.isEmpty()) {
622       currentState = stackToProcess.iterator().next();
623       stackToProcess.remove(currentState);
624       processed.add(currentState);
625 
626 
627       SimpleArraySet<Transition> transitions = currentState.getTransitions();
628       statesToReturn.put(currentState, transitions);
629       for (Iterator<Transition> iter = transitions.iterator(); iter.hasNext();) {
630         currentTransition = iter.next();
631         State target = currentTransition.getTarget();
632         if (processed.contains(target|| stackToProcess.contains(target)) continue;
633         stackToProcess.add(target);
634       }
635     }
636 
637     return statesToReturn;
638   }
639 
640   /**
641    * Returns a representation of this FSM in the GraphViz graph-visualization
642    * language. We use the "digraph" (directed graph) format. Nodes are labeled
643    * by their numerical indexes. A node's shape is a diamond if it's the initial
644    * state, and round otherwise. A node is green if it's an initial state, red
645    * if it's a final state, and black otherwise. Final states are also marked
646    * with a double-line outline.
647    
648    @see <a href="http://www.graphviz.org">GraphViz for visulization</a>
649    @param includeConstraints
650    *          whether to include a stringified representation of each transition
651    *          object as part of its label. The default is false.
652    */
653   public String asGraphViz(boolean includeConstraints) {
654     StringBuffer result = new StringBuffer();
655 
656     result.append("digraph G {\n");
657 
658     for(State currentState : getAllStates().keySet()) {
659       int stateIndex = currentState.getIndex();
660       Map<String,String> opts = new HashMap<String,String>();
661       opts.put("shape", currentState == initialState ? "diamond" "circle");
662       opts.put("color", currentState == initialState ? "green" : currentState.isFinal() "red" "black");
663       if (currentState.isFinal()) {
664         opts.put("peripheries""2");
665         if (DEBUG) {
666           opts.put("shape""rectangle");
667           opts.put("label""" + stateIndex + "-" + currentState.getAction());
668         }
669       }
670 
671       result.append("  " + stateIndex + " [" + encodeForGraphViz(opts"]" ";\n");
672 
673       for(Transition t : currentState.getTransitions()) {
674         String extraText = includeConstraints
675         " [label=\"" + t.toString(false"\"]"
676                 "";
677         result.append("  " + stateIndex + " -> " + t.getTarget().getIndex()
678                 + extraText + ";\n");
679       }
680     }
681 
682     result.append("}\n");
683 
684     return result.toString();
685   }
686 
687   /**
688    * Given a Map, encodes its keys and values as strings suitable for use as a
689    * GraphViz label. Embedded "\r\n" sequences are replaced by "\\l" to create
690    * line feeds, and embedded backslashes are escaped. The returned String takes
691    * the form "key1=value1, key2=value2, ...".
692    */
693   String encodeForGraphViz (Map<String,String> m) {
694     ArrayList<String> temp = new ArrayList<String>(m.size());
695     for(String k : m.keySet()) {
696       String v = m.get(k);
697       v = v.replaceAll("\r\n""\\\\l");
698       v = v.replaceAll("\"""\\\\\"");
699       temp.add(k + "=\"" + v + "\"");
700     }
701 
702     StringBuffer toReturn = new StringBuffer();
703     for (int i = 0; i < temp.size(); i++)
704     {
705       if (i != 0toReturn.append(",");
706       toReturn.append(temp.get(i));
707     }
708     return toReturn.toString();
709   }
710 
711 
712   /**
713     * Returns a GML (Graph Modelling Language) representation of the transition
714     * graph of this FSM.
715     */
716   public String getGML() {
717 
718     String res = "graph[ \ndirected 1\n";
719 
720     StringBuffer nodes = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE),
721                  edges = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE);
722 
723     Iterator<State> stateIter = allStates.iterator();
724     while (stateIter.hasNext()){
725       State currentState = stateIter.next();
726       int stateIndex = currentState.getIndex();
727         nodes.append("node[ id ");
728         nodes.append(stateIndex);
729         nodes.append(" label \"");
730         nodes.append(stateIndex);
731 
732              if(currentState.isFinal()){
733               nodes.append(",F\\n" + currentState.getAction().shortDesc());
734              }
735              nodes.append("\"  ]\n");
736       edges.append(currentState.getEdgesGML());
737     }
738     res += nodes.toString() + edges.toString() "]\n";
739     return res;
740   // getGML
741 
742   /**
743     * Returns a textual description of this FSM.
744     */
745   @Override
746   public String toString(){
747     String res = "Starting from:" + initialState.getIndex() "\n";
748     Iterator<State> stateIter = allStates.iterator();
749     while (stateIter.hasNext()){
750       res += "\n\n" + stateIter.next();
751     }
752     return res;
753   // toString
754 
755   /**
756     * The initial state of this FSM.
757     */
758   private State initialState;
759 
760  /**
761    * The final state of this FSM (usually only valid during construction).
762    */
763   protected State finalState;
764 
765   /**
766     * The set of states for this FSM
767     */
768   private transient Collection<State> allStates =  new HashSet<State>();
769 
770   //kalina: added this member here to minimise HashMap allocation
771   private transient Map<Set<State>,State> newStates = new HashMap<Set<State>,State>();
772   private transient Set<Set<State>> dStates = new HashSet<Set<State>>();
773 
774 
775   //added by Karter start
776   private String currentBinding(ComplexPatternElement cpe, int indent) {
777     if (indent == 0)
778       bpeId = 0;
779     String ind = "";
780     for (int i = 0; i < indent; i++) {
781       ind += "   ";
782     }
783     String binds = ind + "(\n";
784     PatternElement[][] pe = cpe.getConstraintGroup().
785         getPatternElementDisjunction();
786     for (int i = 0; i < pe.length; i++) {
787       PatternElement[] patternElements = pe[i];
788       for (int j = 0; j < patternElements.length; j++) {
789         PatternElement patternElement = patternElements[j];
790         if (patternElement instanceof ComplexPatternElement) {
791           ComplexPatternElement complexPatternElement = (ComplexPatternElement)
792               patternElement;
793           binds += currentBinding(complexPatternElement, indent + 1);
794 
795         }
796         else {
797           binds += ind + "   ";
798           binds += currentBasicBinding((BasicPatternElementpatternElement);
799           binds += "\n";
800         }
801       }
802       binds += ind + "   |\n";
803     }
804     binds = binds.substring(0, binds.length() 5);
805     binds += ")" + cpe.getKleeneOp().toString() "\n";
806     if (indent == 0)
807       bpeId = 0;
808     return binds;
809   }
810 
811   private String currentBasicBinding(BasicPatternElement bpe) {
812     StringBuilder sb = new StringBuilder("{");
813     Constraint[] cons = bpe.getConstraints();
814     for (int k = 0; k < cons.length; k++) {
815       sb.append(cons[k].getDisplayString(""));
816       if (k < cons.length - 1)
817         sb.append(",");
818     }
819     sb.append("}").append(" *").append(bpeId++).append("*");
820     return sb.toString();
821   }
822 
823   private String currentLHSBinding(LeftHandSide lhs) {
824     String binds = "(\n";
825     PatternElement[][] pe = lhs.getConstraintGroup().
826         getPatternElementDisjunction();
827     for (int i = 0; i < pe.length; i++) {
828       PatternElement[] patternElements = pe[i];
829       for (int j = 0; j < patternElements.length; j++) {
830         PatternElement patternElement = patternElements[j];
831         if (patternElement instanceof ComplexPatternElement) {
832           ComplexPatternElement complexPatternElement = (ComplexPatternElement)
833               patternElement;
834           binds += currentBinding(complexPatternElement, 1);
835 
836         }
837         else {
838           binds += "   ";
839           binds += currentBasicBinding((BasicPatternElementpatternElement);
840           binds += "\n";
841         }
842       }
843       binds += "   |\n";
844     }
845     binds = binds.substring(0, binds.length() 5);
846     binds += ")\n";
847     bpeId = 0;
848     return binds;
849   }
850 
851   int bpeId = 0;
852   public HashMap<String,String> ruleHash = new HashMap<String,String>();
853   //added by Karter end
854 // FSM