1   /*
2    *  FSM.java
3    *
4    *  Copyright (c) 1998-2005, The University of Sheffield.
5    *
6    *  This file is part of GATE (see http://gate.ac.uk/), and is free
7    *  software, licenced under the GNU Library General Public License,
8    *  Version 2, June 1991 (in the distribution as file licence.html,
9    *  and also available at http://gate.ac.uk/gate/licence.html).
10   *
11   *  Valentin Tablan, 29/Mar/2000
12   *
13   *  $Id: FSM.java,v 1.26 2005/01/11 13:51:34 ian Exp $
14   */
15  
16  package gate.fsm;
17  
18  import java.util.*;
19  
20  import gate.jape.*;
21  
22  /**
23    * This class implements a standard Finite State Machine.
24    * It is used for both deterministic and non-deterministic machines.
25    */
26  public class FSM implements JapeConstants {
27  
28    /** Debug flag */
29    private static final boolean DEBUG = false;
30  
31    /**
32      * Builds a standalone FSM starting from a single phase transducer.
33      * @param spt the single phase transducer to be used for building this FSM.
34      */
35    public FSM(SinglePhaseTransducer spt){
36      initialState = new State();
37      transducerName = spt.getName();
38      Iterator rulesEnum = spt.getRules().iterator();
39      Rule currentRule;
40  
41      while(rulesEnum.hasNext()){
42        currentRule = (Rule) rulesEnum.next();
43        FSM ruleFSM = new FSM(currentRule);
44  
45        //added by Karter start
46        if(gate.Gate.isEnableJapeDebug()) {
47          ruleHash.putAll(ruleFSM.ruleHash);
48        }
49        //added by Karter end
50  
51        initialState.addTransition(new Transition(null,
52                                                  ruleFSM.getInitialState()));
53      }
54  
55      eliminateVoidTransitions();
56  //Out.prln("Transducer " + spt.getName() + " converted to " + allStates.size() + " states");
57  
58    }
59  
60    /**
61      * Builds a FSM starting from a rule. This FSM is actually a part of a larger
62      * one (usually the one that is built based on the single phase transducer
63      * that contains the rule).
64      * built by this constructor.
65      * @param rule the rule to be used for the building process.
66      */
67    public FSM(Rule rule) {
68  
69      initialState = new State();
70      LeftHandSide lhs = rule.getLHS();
71  
72      //added by Karter start
73      LinkedList ll = new LinkedList();
74      if(gate.Gate.isEnableJapeDebug()) {
75        String label = currentLHSBinding(lhs);
76        ll.add(label);
77        ruleHash.put(rule.getName(), label);
78      }
79      //added by Karter end
80  
81  
82      PatternElement[][] constraints =
83                         lhs.getConstraintGroup().getPatternElementDisjunction();
84      // the rectangular array constraints is a disjunction of sequences of
85      // constraints = [[PE]:[PE]...[PE] ||
86      //                [PE]:[PE]...[PE] ||
87      //                ...
88      //                [PE]:[PE]...[PE] ]
89  
90      //The current and the next state for the current ROW.
91      State currentRowState, nextRowState;
92      State finalState = new State();
93      PatternElement currentPattern;
94  
95      for(int i = 0; i < constraints.length; i++){
96        // for each row we have to create a sequence of states that will accept
97        // the sequence of annotations described by the restrictions on that row.
98        // The final state of such a sequence will always be a final state which
99        // will have associated the right hand side of the rule used for this
100       // constructor.
101 
102       // For each row we will start from the initial state.
103       currentRowState = initialState;
104       for(int j=0; j < constraints[i].length; j++) {
105 
106         // parse the sequence of constraints:
107         // For each basic pattern element add a new state and link it to the
108         // currentRowState.
109         // The case of kleene operators has to be considered!
110         currentPattern = constraints[i][j];
111         State insulator = new State();
112         currentRowState.addTransition(new Transition(null,insulator));
113         currentRowState = insulator;
114         if(currentPattern instanceof BasicPatternElement) {
115           //the easy case
116           nextRowState = new State();
117 
118           //added by Karter start
119           LinkedList sll = new LinkedList();
120           if(gate.Gate.isEnableJapeDebug()) {
121             sll.add(currentBasicBinding( (BasicPatternElement) currentPattern));
122             currentRowState.addTransition(
123                 new Transition( (BasicPatternElement) currentPattern,
124                                nextRowState
125                                /*added by Karter*/, sll));
126           } else {
127             currentRowState.addTransition(
128               new Transition((BasicPatternElement)currentPattern, nextRowState));
129           }
130           //added by Karter end
131 
132           currentRowState = nextRowState;
133         } else if(currentPattern instanceof ComplexPatternElement) {
134 
135           // the current pattern is a complex pattern element
136           // ..it will probaly be converted into a sequence of states itself.
137 
138           // Angel debugger cut
139           if(gate.Gate.isEnableJapeDebug()) {
140             currentRowState = convertComplexPE(
141                 currentRowState,
142                 (ComplexPatternElement) currentPattern,
143                 /*changed by Karter "new LinkedList()"*/ll);
144           } else {
145             currentRowState =  convertComplexPE(
146                                 currentRowState,
147                                 (ComplexPatternElement)currentPattern,
148                                 new LinkedList());
149 
150           }
151           // Angel debugger cut
152 
153         } else {
154           // we got an unknown kind of pattern
155           throw new RuntimeException("Strange looking pattern: " +
156                                      currentPattern);
157         }
158 
159       } // for j
160 
161       //link the end of the current row to the final state using
162       //an empty transition.
163       currentRowState.addTransition(new Transition(null,finalState));
164       finalState.setAction(rule.getRHS());
165       finalState.setFileIndex(rule.getPosition());
166       finalState.setPriority(rule.getPriority());
167     } // for i
168   }
169 
170   /**
171     * Gets the initial state of this FSM
172     * @return an object of type gate.fsm.State representing the initial state.
173     */
174   public State getInitialState() {
175     return initialState;
176   } // getInitialState
177 
178   /**
179     * Receives a state to start from and a complex pattern element.
180     * Parses the complex pattern element and creates all the necessary states
181     * and transitions for accepting annotations described by the given PE.
182     * @param startState the state to start from
183     * @param cpe the pattern to be recognized
184     * @param labels the bindings name for all the annotation accepted along
185     * the way. This is actually a list of Strings. It is necessary to use
186     * a list because of the recursive definition of ComplexPatternElement.
187     * @return the final state reached after accepting a sequence of annotations
188     * as described in the pattern
189     */
190   private State convertComplexPE(State startState,
191                                 ComplexPatternElement cpe, LinkedList labels){
192     //create a copy
193     LinkedList newBindings = (LinkedList)labels.clone();
194     String localLabel = cpe.getBindingName ();
195 
196     if(localLabel != null)newBindings.add(localLabel);
197 
198     PatternElement[][] constraints =
199                        cpe.getConstraintGroup().getPatternElementDisjunction();
200 
201     // the rectangular array constraints is a disjunction of sequences of
202     // constraints = [[PE]:[PE]...[PE] ||
203     //                [PE]:[PE]...[PE] ||
204     //                ...
205     //                [PE]:[PE]...[PE] ]
206 
207     //The current and the next state for the current ROW.
208     State currentRowState, nextRowState, endState = new State();
209     PatternElement currentPattern;
210 
211     for(int i = 0; i < constraints.length; i++) {
212       // for each row we have to create a sequence of states that will accept
213       // the sequence of annotations described by the restrictions on that row.
214       // The final state of such a sequence will always be a finale state which
215       // will have associated the right hand side of the rule used for this
216       // constructor.
217 
218       //For each row we will start from the initial state.
219       currentRowState = startState;
220       for(int j=0; j < (constraints[i]).length; j++) {
221 
222         //parse the sequence of constraints:
223         //For each basic pattern element add a new state and link it to the
224         //currentRowState.
225         //The case of kleene operators has to be considered!
226         State insulator = new State();
227         currentRowState.addTransition(new Transition(null,insulator));
228         currentRowState = insulator;
229         currentPattern = constraints[i][j];
230         if(currentPattern instanceof BasicPatternElement) {
231 
232           //the easy case
233           nextRowState = new State();
234 
235           //added by Karter start
236           if(gate.Gate.isEnableJapeDebug()) {
237             newBindings.add(currentBasicBinding( (BasicPatternElement)
238                                                 currentPattern));
239           }
240           //added by Karter end
241 
242 
243           currentRowState.addTransition(
244             new Transition((BasicPatternElement)currentPattern,
245                             nextRowState,newBindings));
246           currentRowState = nextRowState;
247         } else if(currentPattern instanceof ComplexPatternElement) {
248 
249           // the current pattern is a complex pattern element
250           // ..it will probaly be converted into a sequence of states itself.
251           currentRowState =  convertComplexPE(
252                               currentRowState,
253                               (ComplexPatternElement)currentPattern,
254                               newBindings);
255         } else {
256 
257           //we got an unknown kind of pattern
258           throw new RuntimeException("Strange looking pattern:"+currentPattern);
259         }
260 
261       } // for j
262         // link the end of the current row to the general end state using
263         // an empty transition.
264         currentRowState.addTransition(new Transition(null,endState));
265     } // for i
266 
267     // let's take care of the kleene operator
268     int kleeneOp = cpe.getKleeneOp();
269     switch (kleeneOp){
270       case NO_KLEENE_OP:{
271         break;
272       }
273       case KLEENE_QUERY:{
274         //allow to skip everything via a null transition
275         startState.addTransition(new Transition(null,endState));
276         break;
277       }
278       case KLEENE_PLUS:{
279 
280         // allow to return to startState
281         endState.addTransition(new Transition(null,startState));
282         break;
283       }
284       case KLEENE_STAR:{
285 
286         // allow to skip everything via a null transition
287         startState.addTransition(new Transition(null,endState));
288 
289         // allow to return to startState
290         endState.addTransition(new Transition(null,startState));
291         break;
292       }
293       default:{
294         throw new RuntimeException("Unknown Kleene operator"+kleeneOp);
295       }
296     } // switch (cpe.getKleeneOp())
297     return endState;
298   } // convertComplexPE
299 
300   /**
301     * Converts this FSM from a non-deterministic to a deterministic one by
302     * eliminating all the unrestricted transitions.
303     */
304   public void eliminateVoidTransitions() {
305 
306     dStates.clear(); //kalina: replaced from new HashSet()
307     LinkedList unmarkedDStates = new LinkedList();
308     AbstractSet currentDState = new HashSet();
309     //kalina: prefer clear coz faster than init()
310     newStates.clear();
311 
312     currentDState.add(initialState);
313     currentDState = lambdaClosure(currentDState);
314     dStates.add(currentDState);
315     unmarkedDStates.add(currentDState);
316 
317     // create a new state that will take the place the set of states
318     // in currentDState
319     initialState = new State();
320     newStates.put(currentDState, initialState);
321 
322     // find out if the new state is a final one
323     Iterator innerStatesIter = currentDState.iterator();
324     RightHandSide action = null;
325 
326     while(innerStatesIter.hasNext()){
327       State currentInnerState = (State)innerStatesIter.next();
328       if(currentInnerState.isFinal()){
329         action = (RightHandSide)currentInnerState.getAction();
330         initialState.setAction(action);
331         initialState.setFileIndex(currentInnerState.getFileIndex());
332         initialState.setPriority(currentInnerState.getPriority());
333         break;
334       }
335     }
336 
337     while(!unmarkedDStates.isEmpty()) {
338       currentDState = (AbstractSet)unmarkedDStates.removeFirst();
339       Iterator insideStatesIter = currentDState.iterator();
340 
341       while(insideStatesIter.hasNext()) {
342         State innerState = (State)insideStatesIter.next();
343         Iterator transIter = innerState.getTransitions().iterator();
344 
345         while(transIter.hasNext()) {
346           Transition currentTrans = (Transition)transIter.next();
347 
348           if(currentTrans.getConstraints() !=null) {
349             State target = currentTrans.getTarget();
350             AbstractSet newDState = new HashSet();
351             newDState.add(target);
352             newDState = lambdaClosure(newDState);
353 
354             if(!dStates.contains(newDState)) {
355               dStates.add(newDState);
356               unmarkedDStates.add(newDState);
357               State newState = new State();
358               newStates.put(newDState, newState);
359 
360               //find out if the new state is a final one
361               innerStatesIter = newDState.iterator();
362               while(innerStatesIter.hasNext()) {
363                 State currentInnerState = (State)innerStatesIter.next();
364 
365                 if(currentInnerState.isFinal()) {
366                   newState.setAction(
367                           (RightHandSide)currentInnerState.getAction());
368                   newState.setFileIndex(currentInnerState.getFileIndex());
369                   newState.setPriority(currentInnerState.getPriority());
370                   break;
371                 }
372               }
373             }// if(!dStates.contains(newDState))
374 
375             State currentState = (State)newStates.get(currentDState);
376             State newState = (State)newStates.get(newDState);
377             currentState.addTransition(new Transition(
378                                         currentTrans.getConstraints(),
379                                         newState,
380                                         currentTrans.getBindings()));
381           }// if(currentTrans.getConstraints() !=null)
382 
383         }// while(transIter.hasNext())
384 
385       }// while(insideStatesIter.hasNext())
386 
387     }// while(!unmarkedDstates.isEmpty())
388 
389     /*
390     //find final states
391     Iterator allDStatesIter = dStates.iterator();
392     while(allDStatesIter.hasNext()){
393       currentDState = (AbstractSet) allDStatesIter.next();
394       Iterator innerStatesIter = currentDState.iterator();
395       while(innerStatesIter.hasNext()){
396         State currentInnerState = (State) innerStatesIter.next();
397         if(currentInnerState.isFinal()){
398           State newState = (State)newStates.get(currentDState);
399 
400           newState.setAction(currentInnerState.getAction());
401           break;
402         }
403       }
404 
405     }
406     */
407     allStates = newStates.values();
408   }//eliminateVoidTransitions
409 
410   /*
411     * Computes the lambda-closure (aka epsilon closure) of the given set of
412     * states, that is the set of states that are accessible from any of the
413     * states in the given set using only unrestricted transitions.
414     * @return a set containing all the states accessible from this state via
415     * transitions that bear no restrictions.
416     */
417   private AbstractSet lambdaClosure(AbstractSet s) {
418     // the stack/queue used by the algorithm
419     LinkedList list = new LinkedList(s);
420 
421     // the set to be returned
422     AbstractSet lambdaClosure = new HashSet(s);
423     State top;
424     Iterator transIter;
425     Transition currentTransition;
426     State currentState;
427     while(!list.isEmpty()){
428       top = (State)list.removeFirst();
429       transIter = top.getTransitions().iterator();
430 
431       while(transIter.hasNext()){
432         currentTransition = (Transition)transIter.next();
433 
434         if(currentTransition.getConstraints() == null){
435           currentState = currentTransition.getTarget();
436           if(!lambdaClosure.contains(currentState)){
437             lambdaClosure.add(currentState);
438             list.addFirst(currentState);
439           }// if(!lambdaClosure.contains(currentState))
440 
441         }// if(currentTransition.getConstraints() == null)
442 
443       }
444     }
445     return lambdaClosure;
446   } // lambdaClosure
447 
448   /**
449     * Returns a GML (Graph Modelling Language) representation of the transition
450     * graph of this FSM.
451     */
452   public String getGML() {
453 
454     String res = "graph[ \ndirected 1\n";
455 ///    String nodes = "", edges = "";
456     StringBuffer nodes = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE),
457                  edges = new StringBuffer(gate.Gate.STRINGBUFFER_SIZE);
458 
459     Iterator stateIter = allStates.iterator();
460     while (stateIter.hasNext()){
461       State currentState = (State)stateIter.next();
462       int stateIndex = currentState.getIndex();
463 /*      nodes += "node[ id " + stateIndex +
464                " label \"" + stateIndex;
465 */
466         nodes.append("node[ id ");
467         nodes.append(stateIndex);
468         nodes.append(" label \"");
469         nodes.append(stateIndex);
470 
471              if(currentState.isFinal()){
472 /*              nodes += ",F";
473               nodes += "\\n" + currentState.getAction().shortDesc();
474 */
475               nodes.append(",F\\n" + currentState.getAction().shortDesc());
476              }
477 ///             nodes +=  "\"  ]\n";
478              nodes.append("\"  ]\n");
479 ///      edges += currentState.getEdgesGML();
480       edges.append(currentState.getEdgesGML());
481     }
482     res += nodes.toString() + edges.toString() + "]\n";
483     return res;
484   } // getGML
485 
486   /**
487     * Returns a textual description of this FSM.
488     */
489   public String toString(){
490     String res = "Starting from:" + initialState.getIndex() + "\n";
491     Iterator stateIter = allStates.iterator();
492     while (stateIter.hasNext()){
493       res += "\n\n" + stateIter.next();
494     }
495     return res;
496   } // toString
497 
498   /**
499     * The initial state of this FSM.
500     */
501   private State initialState;
502 
503   /**
504     * The set of states for this FSM
505     */
506   private transient Collection allStates =  new HashSet();
507 
508   //kalina: added this member here to minimise HashMap allocation
509   private transient Map newStates = new HashMap();
510   private transient Set dStates = new HashSet();
511 
512   private String transducerName;
513 
514   //added by Karter start
515   private String currentBinding(ComplexPatternElement cpe, int indent) {
516     if (indent == 0)
517       bpeId = 0;
518     String ind = "";
519     for (int i = 0; i < indent; i++) {
520       ind += "   ";
521     }
522     String binds = ind + "(\n";
523     PatternElement[][] pe = cpe.getConstraintGroup().
524         getPatternElementDisjunction();
525     for (int i = 0; i < pe.length; i++) {
526       PatternElement[] patternElements = pe[i];
527       for (int j = 0; j < patternElements.length; j++) {
528         PatternElement patternElement = patternElements[j];
529         if (patternElement instanceof ComplexPatternElement) {
530           ComplexPatternElement complexPatternElement = (ComplexPatternElement)
531               patternElement;
532           binds += currentBinding(complexPatternElement, indent + 1);
533 
534         }
535         else {
536           binds += ind + "   {";
537           BasicPatternElement basicPatternElement = (BasicPatternElement)
538               patternElement;
539           Constraint[] cons = basicPatternElement.getConstraints();
540           for (int k = 0; k < cons.length; k++) {
541             Constraint con = cons[k];
542             String annType = con.getAnnotType();
543             gate.FeatureMap fm = con.getAttributeSeq();
544             Iterator iter = fm.keySet().iterator();
545             if (!iter.hasNext())
546               binds += annType + ",";
547             while (iter.hasNext()) {
548               String key = (String) iter.next();
549               binds += annType + "." + key + "==\"" + fm.get(key) + "\",";
550 
551             }
552           }
553           binds = binds.substring(0, binds.length() - 1);
554           binds += "}" + " *" + bpeId++ +"*" + "\n";
555         }
556       }
557       binds += ind + "   |\n";
558     }
559     String kleene = "";
560     int klInt = cpe.getKleeneOp();
561     if (klInt == KLEENE_PLUS)
562       kleene = "+";
563     if (klInt == KLEENE_QUERY)
564       kleene = "?";
565     if (klInt == KLEENE_STAR)
566       kleene = "*";
567     binds = binds.substring(0, binds.length() - 5);
568     binds += ")" + kleene + "\n";
569     if (indent == 0)
570       bpeId = 0;
571     return binds;
572   }
573 
574   private String currentBasicBinding(BasicPatternElement bpe) {
575     String bind = "";
576     bind += "{";
577     Constraint[] cons = bpe.getConstraints();
578     for (int k = 0; k < cons.length; k++) {
579       Constraint con = cons[k];
580       String annType = con.getAnnotType();
581       gate.FeatureMap fm = con.getAttributeSeq();
582       Iterator iter = fm.keySet().iterator();
583       if (!iter.hasNext())
584         bind += annType + ",";
585       while (iter.hasNext()) {
586         String key = (String) iter.next();
587         bind += annType + "." + key + "==\"" + fm.get(key) + "\",";
588 
589       }
590     }
591     bind = bind.substring(0, bind.length() - 1);
592     bind += "}" + " *" + bpeId++ +"*";
593     return bind;
594   }
595 
596   private String currentLHSBinding(LeftHandSide lhs) {
597     String binds = "(\n";
598     PatternElement[][] pe = lhs.getConstraintGroup().
599         getPatternElementDisjunction();
600     for (int i = 0; i < pe.length; i++) {
601       PatternElement[] patternElements = pe[i];
602       for (int j = 0; j < patternElements.length; j++) {
603         PatternElement patternElement = patternElements[j];
604         if (patternElement instanceof ComplexPatternElement) {
605           ComplexPatternElement complexPatternElement = (ComplexPatternElement)
606               patternElement;
607           binds += currentBinding(complexPatternElement, 1);
608 
609         }
610         else {
611           binds += "   {";
612           BasicPatternElement basicPatternElement = (BasicPatternElement)
613               patternElement;
614           Constraint[] cons = basicPatternElement.getConstraints();
615           for (int k = 0; k < cons.length; k++) {
616             Constraint con = cons[k];
617             String annType = con.getAnnotType();
618             gate.FeatureMap fm = con.getAttributeSeq();
619             Iterator iter = fm.keySet().iterator();
620             if (!iter.hasNext())
621               binds += annType + ",";
622             while (iter.hasNext()) {
623               String key = (String) iter.next();
624               binds += annType + "." + key + "==\"" + fm.get(key) + "\",";
625 
626             }
627           }
628           binds = binds.substring(0, binds.length() - 1);
629           binds += "}" + " *" + bpeId++ +"*" + "\n";
630         }
631       }
632       binds += "   |\n";
633     }
634     binds = binds.substring(0, binds.length() - 5);
635     binds += ")\n";
636     bpeId = 0;
637     return binds;
638   }
639 
640   int bpeId = 0;
641   public HashMap ruleHash = new HashMap();
642   //added by Karter end
643 } // FSM
644