NfaState


1   /*
2    * Copyright © 2002 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
3    * California 95054, U.S.A. All rights reserved.  Sun Microsystems, Inc. has
4    * intellectual property rights relating to technology embodied in the product
5    * that is described in this document. In particular, and without limitation,
6    * these intellectual property rights may include one or more of the U.S.
7    * patents listed at http://www.sun.com/patents and one or more additional
8    * patents or pending patent applications in the U.S. and in other countries.
9    * U.S. Government Rights - Commercial software. Government users are subject
10   * to the Sun Microsystems, Inc. standard license agreement and applicable
11   * provisions of the FAR and its supplements.  Use is subject to license terms.
12   * Sun,  Sun Microsystems,  the Sun logo and  Java are trademarks or registered
13   * trademarks of Sun Microsystems, Inc. in the U.S. and other countries.  This
14   * product is covered and controlled by U.S. Export Control laws and may be
15   * subject to the export or import laws in other countries.  Nuclear, missile,
16   * chemical biological weapons or nuclear maritime end uses or end users,
17   * whether direct or indirect, are strictly prohibited.  Export or reexport
18   * to countries subject to U.S. embargo or to entities identified on U.S.
19   * export exclusion lists, including, but not limited to, the denied persons
20   * and specially designated nationals lists is strictly prohibited.
21   */
22  
23  package org.javacc.parser;
24  
25  import java.util.*;
26  
27  public class NfaState
28  {
29     public static boolean unicodeWarningGiven = false;
30     public static int generatedStates = 0;
31     static int idCnt = 0;
32     static int lohiByteCnt;
33     static int dummyStateIndex = -1;
34     static boolean done;
35     static boolean mark[];
36     static boolean stateDone[];
37     static boolean nonAsciiIntersections[][] = new boolean[20][20];
38  
39     static Vector allStates = new Vector();
40     static Vector indexedAllStates = new Vector();
41     static Vector nonAsciiTableForMethod = new Vector();
42     static Hashtable equivStatesTable = new Hashtable();
43     static Hashtable allNextStates = new Hashtable();
44     static Hashtable lohiByteTab = new Hashtable();
45     static Hashtable stateNameForComposite = new Hashtable();
46     static Hashtable compositeStateTable = new Hashtable();
47     static Hashtable stateBlockTable = new Hashtable();
48     static Hashtable stateSetsToFix = new Hashtable();
49  
50     public static void ReInit()
51     {
52        generatedStates = 0;
53        idCnt = 0;
54        dummyStateIndex = -1;
55        done = false;
56        mark = null;
57        stateDone = null;
58  
59        allStates.removeAllElements();
60        indexedAllStates.removeAllElements();
61        equivStatesTable.clear();
62        allNextStates.clear();
63        compositeStateTable.clear();
64        stateBlockTable.clear();
65        stateNameForComposite.clear();
66        stateSetsToFix.clear();
67     }
68  
69     long[] asciiMoves = new long[2];
70     char[] charMoves = null;
71     char[] rangeMoves = null;
72     NfaState next = null;
73     NfaState stateForCase;
74     Vector epsilonMoves = new Vector();
75     String   epsilonMovesString;
76     NfaState[] epsilonMoveArray;
77  
78     int id;
79     int stateName = -1;
80     int kind = Integer.MAX_VALUE;
81     int lookingFor;
82     int usefulEpsilonMoves = 0;
83     int inNextOf;
84     private int lexState;
85     int nonAsciiMethod = -1;
86     int kindToPrint = Integer.MAX_VALUE;
87     boolean dummy = false;
88     boolean isComposite = false;
89     int[] compositeStates = null;
90     boolean isFinal = false;
91     public Vector loByteVec;
92     public int[] nonAsciiMoveIndices;
93     int round = 0;
94     int onlyChar = 0;
95     char matchSingleChar;
96  
97     NfaState()
98     {
99        id = idCnt++;
100       allStates.addElement(this);
101       lexState = LexGen.lexStateIndex;
102       lookingFor = LexGen.curKind;
103    }
104 
105    NfaState CreateClone()
106    {
107       NfaState retVal = new NfaState();
108 
109       retVal.isFinal = isFinal;
110       retVal.kind = kind;
111       retVal.lookingFor = lookingFor;
112       retVal.lexState = lexState;
113       retVal.inNextOf = inNextOf;
114 
115       retVal.MergeMoves(this);
116 
117       return retVal;
118    }
119 
120    static void InsertInOrder(Vector v, NfaState s)
121    {
122       int j;
123 
124       for (j = 0; j < v.size(); j++)
125          if (((NfaState)v.elementAt(j)).id > s.id)
126             break;
127          else if (((NfaState)v.elementAt(j)).id  == s.id)
128             return;
129 
130       v.insertElementAt(s, j);
131    }
132 
133    private static char[] ExpandCharArr(char[] oldArr, int incr)
134    {
135       char[] ret = new char[oldArr.length + incr];
136       System.arraycopy(oldArr, 0, ret, 0, oldArr.length);
137       return ret;
138    }
139 
140    void AddMove(NfaState newState)
141    {
142       if (!epsilonMoves.contains(newState))
143          InsertInOrder(epsilonMoves, newState);
144    }
145 
146    private final void AddASCIIMove(char c)
147    {
148       asciiMoves[c / 64] |= (1L << (c % 64));
149    }
150 
151    void AddChar(char c)
152    {
153       onlyChar++;
154       matchSingleChar = c;
155       int i;
156       char temp;
157       char temp1;
158 
159       if ((int)c < 128) // ASCII char
160       {
161          AddASCIIMove(c);
162          return;
163       }
164 
165       if (charMoves == null)
166          charMoves = new char[10];
167 
168       int len = charMoves.length;
169 
170       if (charMoves[len - 1] != 0)
171       {
172          charMoves = ExpandCharArr(charMoves, 10);
173          len += 10;
174       }
175 
176       for (i = 0; i < len; i++)
177          if (charMoves[i] == 0 || charMoves[i] > c)
178             break;
179 
180       if (!unicodeWarningGiven && c > 0xff &&
181           !Options.getJavaUnicodeEscape() &&
182           !Options.getUserCharStream())
183       {
184          unicodeWarningGiven = true;
185          JavaCCErrors.warning(LexGen.curRE, "Non-ASCII characters used in regular expression.\n" +
186               "Please make sure you use the correct Reader when you create the parser that can handle your character set.");
187       }
188 
189       temp = charMoves[i];
190       charMoves[i] = c;
191 
192       for (i++; i < len; i++)
193       {
194          if (temp == 0)
195             break;
196 
197          temp1 = charMoves[i];
198          charMoves[i] = temp;
199          temp = temp1;
200       }
201    }
202 
203    void AddRange(char left, char right)
204    {
205       onlyChar = 2;
206       int i;
207       char tempLeft1, tempLeft2, tempRight1, tempRight2;
208 
209       if (left < 128)
210       {
211          if (right < 128)
212          {
213             for (; left <= right; left++)
214                AddASCIIMove(left);
215 
216             return;
217          }
218 
219          for (; left < 128; left++)
220             AddASCIIMove(left);
221       }
222 
223       if (!unicodeWarningGiven && (left > 0xff || right > 0xff) &&
224           !Options.getJavaUnicodeEscape() &&
225           !Options.getUserCharStream())
226       {
227          unicodeWarningGiven = true;
228          JavaCCErrors.warning(LexGen.curRE, "Non-ASCII characters used in regular expression.\n" +
229               "Please make sure you use the correct Reader when you create the parser that can handle your character set.");
230       }
231 
232       if (rangeMoves == null)
233          rangeMoves = new char[20];
234 
235       int len = rangeMoves.length;
236 
237       if (rangeMoves[len - 1] != 0)
238       {
239          rangeMoves = ExpandCharArr(rangeMoves, 20);
240          len += 20;
241       }
242 
243       for (i = 0; i < len; i += 2)
244          if (rangeMoves[i] == 0 ||
245              (rangeMoves[i] > left) ||
246              ((rangeMoves[i] == left) && (rangeMoves[i + 1] > right)))
247             break;
248 
249       tempLeft1 = rangeMoves[i];
250       tempRight1 = rangeMoves[i + 1];
251       rangeMoves[i] = left;
252       rangeMoves[i + 1] = right;
253 
254       for (i += 2; i < len; i += 2)
255       {
256          if (tempLeft1 == 0)
257             break;
258 
259          tempLeft2 = rangeMoves[i];
260          tempRight2 = rangeMoves[i + 1];
261          rangeMoves[i] = tempLeft1;
262          rangeMoves[i + 1] = tempRight1;
263          tempLeft1 = tempLeft2;
264          tempRight1 = tempRight2;
265       }
266    }
267 
268    // From hereon down all the functions are used for code generation
269 
270    private static boolean EqualCharArr(char[] arr1, char[] arr2)
271    {
272       if (arr1 == arr2)
273          return true;
274 
275       if (arr1 != null &&
276           arr2 != null &&
277           arr1.length == arr2.length)
278       {
279          for (int i = arr1.length; i-- > 0;)
280             if (arr1[i] != arr2[i])
281                return false;
282 
283          return true;
284       }
285 
286       return false;
287    }
288 
289    private boolean closureDone = false;
290 
291    /** This function computes the closure and also updates the kind so that
292      * any time there is a move to this state, it can go on epsilon to a
293      * new state in the epsilon moves that might have a lower kind of token
294      * number for the same length.
295    */
296 
297    private void EpsilonClosure()
298    {
299       int i = 0;
300 
301       if (closureDone || mark[id])
302          return;
303 
304       mark[id] = true;
305 
306       // Recursively do closure
307       for (i = 0; i < epsilonMoves.size(); i++)
308          ((NfaState)epsilonMoves.elementAt(i)).EpsilonClosure();
309 
310       Enumeration e = epsilonMoves.elements();
311 
312       while (e.hasMoreElements())
313       {
314          NfaState tmp = (NfaState)e.nextElement();
315 
316          for (i = 0; i < tmp.epsilonMoves.size(); i++)
317          {
318             NfaState tmp1 = (NfaState)tmp.epsilonMoves.elementAt(i);
319             if (tmp1.UsefulState() && !epsilonMoves.contains(tmp1))
320             {
321                InsertInOrder(epsilonMoves, tmp1);
322                done = false;
323             }
324          }
325 
326          if (kind > tmp.kind)
327             kind = tmp.kind;
328       }
329 
330       if (HasTransitions() && !epsilonMoves.contains(this))
331          InsertInOrder(epsilonMoves, this);
332    }
333 
334    private boolean UsefulState()
335    {
336       return isFinal || HasTransitions();
337    }
338 
339    public boolean HasTransitions()
340    {
341       return (asciiMoves[0] != 0L || asciiMoves[1] != 0L ||
342               (charMoves != null && charMoves[0] != 0) ||
343               (rangeMoves != null && rangeMoves[0] != 0));
344    }
345 
346    void MergeMoves(NfaState other)
347    {
348       // Warning : This function does not merge epsilon moves
349       if (asciiMoves == other.asciiMoves)
350       {
351          JavaCCErrors.semantic_error("Bug in JavaCC : Please send " +
352                    "a report along with the input that caused this. Thank you.");
353          throw new Error  ();
354       }
355 
356       asciiMoves[0] = asciiMoves[0] | other.asciiMoves[0];
357       asciiMoves[1] = asciiMoves[1] | other.asciiMoves[1];
358 
359       if (other.charMoves != null)
360       {
361          if (charMoves == null)
362             charMoves = other.charMoves;
363          else
364          {
365             char[] tmpCharMoves = new char[charMoves.length +
366                                               other.charMoves.length];
367             System.arraycopy(charMoves, 0, tmpCharMoves, 0, charMoves.length);
368             charMoves = tmpCharMoves;
369 
370             for (int i = 0; i < other.charMoves.length; i++)
371                AddChar(other.charMoves[i]);
372          }
373       }
374 
375       if (other.rangeMoves != null)
376       {
377          if (rangeMoves == null)
378             rangeMoves = other.rangeMoves;
379          else
380          {
381             char[] tmpRangeMoves = new char[rangeMoves.length +
382                                                      other.rangeMoves.length];
383             System.arraycopy(rangeMoves, 0, tmpRangeMoves,
384                                                         0, rangeMoves.length);
385             rangeMoves = tmpRangeMoves;
386             for (int i = 0; i < other.rangeMoves.length; i += 2)
387                AddRange(other.rangeMoves[i], other.rangeMoves[i + 1]);
388          }
389       }
390 
391       if (other.kind < kind)
392          kind = other.kind;
393 
394       if (other.kindToPrint < kindToPrint)
395          kindToPrint = other.kindToPrint;
396 
397       isFinal |= other.isFinal;
398    }
399 
400    NfaState CreateEquivState(Vector states)
401    {
402       NfaState newState = ((NfaState)states.elementAt(0)).CreateClone();
403 
404       newState.next = new NfaState();
405 
406       InsertInOrder(newState.next.epsilonMoves,
407                            ((NfaState)states.elementAt(0)).next);
408 
409       for (int i = 1; i < states.size(); i++)
410       {
411          NfaState tmp2 = ((NfaState)states.elementAt(i));
412 
413          if (tmp2.kind < newState.kind)
414             newState.kind = tmp2.kind;
415 
416          newState.isFinal |= tmp2.isFinal;
417 
418          InsertInOrder(newState.next.epsilonMoves, tmp2.next);
419       }
420 
421       return newState;
422    }
423 
424    private NfaState GetEquivalentRunTimeState()
425    {
426       Outer :
427       for (int i = allStates.size(); i-- > 0;)
428       {
429          NfaState other = (NfaState)allStates.elementAt(i);
430 
431          if (this != other && other.stateName != -1 &&
432              kindToPrint == other.kindToPrint &&
433              asciiMoves[0] == other.asciiMoves[0] &&
434              asciiMoves[1] == other.asciiMoves[1] &&
435              EqualCharArr(charMoves, other.charMoves) &&
436              EqualCharArr(rangeMoves, other.rangeMoves))
437          {
438             if (next == other.next)
439                return other;
440             else if (next != null && other.next != null)
441             {
442                if (next.epsilonMoves.size() == other.next.epsilonMoves.size())
443                {
444                   for (int j = 0; j < next.epsilonMoves.size(); j++)
445                      if (next.epsilonMoves.elementAt(j) !=
446                            other.next.epsilonMoves.elementAt(j))
447                         continue Outer;
448 
449                   return other;
450                }
451             }
452          }
453       }
454 
455       return null;
456    }
457 
458    // generates code (without outputting it) and returns the name used.
459    void GenerateCode()
460    {
461       if (stateName != -1)
462          return;
463 
464       if (next != null)
465       {
466          next.GenerateCode();
467          if (next.kind != Integer.MAX_VALUE)
468             kindToPrint = next.kind;
469       }
470 
471       if (stateName == -1 && HasTransitions())
472       {
473          NfaState tmp = GetEquivalentRunTimeState();
474 
475          if (tmp != null)
476          {
477             stateName = tmp.stateName;
478 //????
479             //tmp.inNextOf += inNextOf;
480 //????
481             dummy = true;
482             return;
483          }
484 
485          stateName = generatedStates++;
486          indexedAllStates.addElement(this);
487          GenerateNextStatesCode();
488       }
489    }
490 
491    public static void ComputeClosures()
492    {
493       for (int i = allStates.size(); i-- > 0; )
494       {
495          NfaState tmp = (NfaState)allStates.elementAt(i);
496 
497          if (!tmp.closureDone)
498             tmp.OptimizeEpsilonMoves(true);
499       }
500 
501       for (int i = 0; i < allStates.size(); i++)
502       {
503          NfaState tmp = (NfaState)allStates.elementAt(i);
504 
505          if (!tmp.closureDone)
506             tmp.OptimizeEpsilonMoves(false);
507       }
508 
509       for (int i = 0; i < allStates.size(); i++)
510       {
511          NfaState tmp = (NfaState)allStates.elementAt(i);
512          tmp.epsilonMoveArray = new NfaState[tmp.epsilonMoves.size()];
513          tmp.epsilonMoves.copyInto(tmp.epsilonMoveArray);
514       }
515    }
516 
517    void OptimizeEpsilonMoves(boolean optReqd)
518    {
519       int i;
520 
521       // First do epsilon closure
522       done = false;
523       while (!done)
524       {
525          if (mark == null || mark.length < allStates.size())
526             mark = new boolean[allStates.size()];
527 
528          for (i = allStates.size(); i-- > 0;)
529             mark[i] = false;
530 
531          done = true;
532          EpsilonClosure();
533       }
534 
535       for (i = allStates.size(); i-- > 0;)
536          ((NfaState)allStates.elementAt(i)).closureDone =
537                                   mark[((NfaState)allStates.elementAt(i)).id];
538 
539       // Warning : The following piece of code is just an optimization.
540       // in case of trouble, just remove this piece.
541 
542       boolean sometingOptimized = true;
543 
544       NfaState newState = null;
545       NfaState tmp1, tmp2;
546       int j;
547       Vector equivStates = null;
548 
549       while (sometingOptimized)
550       {
551          sometingOptimized = false;
552          for (i = 0; optReqd && i < epsilonMoves.size(); i++)
553          {
554             if ((tmp1 = (NfaState)epsilonMoves.elementAt(i)).HasTransitions())
555             {
556                for (j = i + 1; j < epsilonMoves.size(); j++)
557                {
558                   if ((tmp2 = (NfaState)epsilonMoves.elementAt(j)).
559                                                            HasTransitions() &&
560                       (tmp1.asciiMoves[0] == tmp2.asciiMoves[0] &&
561                        tmp1.asciiMoves[1] == tmp2.asciiMoves[1] &&
562                        EqualCharArr(tmp1.charMoves, tmp2.charMoves) &&
563                        EqualCharArr(tmp1.rangeMoves, tmp2.rangeMoves)))
564                   {
565                      if (equivStates == null)
566                      {
567                         equivStates = new Vector();
568                         equivStates.addElement(tmp1);
569                      }
570 
571                      InsertInOrder(equivStates, tmp2);
572                      epsilonMoves.removeElementAt(j--);
573                   }
574                }
575             }
576 
577             if (equivStates != null)
578             {
579                sometingOptimized = true;
580                String   tmp = "";
581                for (int l = 0; l < equivStates.size(); l++)
582                   tmp += String.valueOf(
583                             ((NfaState)equivStates.elementAt(l)).id) + ", ";
584 
585                if ((newState = (NfaState)equivStatesTable.get(tmp)) == null)
586                {
587                   newState = CreateEquivState(equivStates);
588                   equivStatesTable.put(tmp, newState);
589                }
590 
591                epsilonMoves.removeElementAt(i--);
592                epsilonMoves.addElement(newState);
593                equivStates = null;
594                newState = null;
595             }
596          }
597 
598          for (i = 0; i < epsilonMoves.size(); i++)
599          {
600             //if ((tmp1 = (NfaState)epsilonMoves.elementAt(i)).next == null)
601                //continue;
602             tmp1 = (NfaState)epsilonMoves.elementAt(i);
603 
604             for (j = i + 1; j < epsilonMoves.size(); j++)
605             {
606                tmp2 = (NfaState)epsilonMoves.elementAt(j);
607 
608                if (tmp1.next == tmp2.next)
609                {
610                   if (newState == null)
611                   {
612                      newState = tmp1.CreateClone();
613                      newState.next = tmp1.next;
614                      sometingOptimized = true;
615                   }
616 
617                   newState.MergeMoves(tmp2);
618                   epsilonMoves.removeElementAt(j--);
619                }
620             }
621 
622             if (newState != null)
623             {
624                epsilonMoves.removeElementAt(i--);
625                epsilonMoves.addElement(newState);
626                newState = null;
627             }
628          }
629       }
630 
631       // End Warning
632 
633       // Generate an array of states for epsilon moves (not vector)
634       if (epsilonMoves.size() > 0)
635       {
636          for (i = 0; i < epsilonMoves.size(); i++)
637             // Since we are doing a closure, just epsilon moves are unncessary
638             if (((NfaState)epsilonMoves.elementAt(i)).HasTransitions())
639                usefulEpsilonMoves++;
640             else
641                epsilonMoves.removeElementAt(i--);
642       }
643    }
644 
645    void GenerateNextStatesCode()
646    {
647       if (next.usefulEpsilonMoves > 0)
648          next.GetEpsilonMovesString();
649    }
650 
651    String   GetEpsilonMovesString()
652    {
653       int[] stateNames = new int[usefulEpsilonMoves];
654       int cnt = 0;
655 
656       if (epsilonMovesString != null)
657          return epsilonMovesString;
658 
659       if (usefulEpsilonMoves > 0)
660       {
661          NfaState tempState;
662          epsilonMovesString = "{ ";
663          for (int i = 0; i < epsilonMoves.size(); i++)
664          {
665             if ((tempState = (NfaState)epsilonMoves.elementAt(i)).
666                                                      HasTransitions())
667             {
668                if (tempState.stateName == -1)
669                   tempState.GenerateCode();
670 
671                ((NfaState)indexedAllStates.elementAt(tempState.stateName)).inNextOf++;
672                stateNames[cnt] = tempState.stateName;
673                epsilonMovesString += tempState.stateName + ", ";
674                if (cnt++ > 0 && cnt % 16 == 0)
675                   epsilonMovesString += "\n";
676             }
677          }
678 
679          epsilonMovesString += "};";
680       }
681 
682       usefulEpsilonMoves = cnt;
683       if (epsilonMovesString != null &&
684           allNextStates.get(epsilonMovesString) == null)
685       {
686          int[] statesToPut = new int[usefulEpsilonMoves];
687 
688          System.arraycopy(stateNames, 0, statesToPut, 0, cnt);
689          allNextStates.put(epsilonMovesString, statesToPut);
690       }
691 
692       return epsilonMovesString;
693    }
694 
695    public static boolean CanStartNfaUsingAscii(char c)
696    {
697       if (c >= 128)
698          throw new Error  ("JavaCC Bug: Please send mail to sankar@cs.stanford.edu");
699 
700       String   s = LexGen.initialState.GetEpsilonMovesString();
701 
702       if (s == null || s.equals("null;"))
703          return false;
704 
705       int[] states = (int[])allNextStates.get(s);
706 
707       for (int i = 0; i < states.length; i++)
708       {
709          NfaState tmp = (NfaState)indexedAllStates.elementAt(states[i]);
710 
711          if ((tmp.asciiMoves[c / 64 ] & (1L << c % 64)) != 0L)
712             return true;
713       }
714 
715       return false;
716    }
717 
718    final boolean CanMoveUsingChar(char c)
719    {
720       int i;
721 
722       if (onlyChar == 1)
723          return c == matchSingleChar;
724 
725       if (c < 128)
726          return ((asciiMoves[c / 64 ] & (1L << c % 64)) != 0L);
727 
728       // Just check directly if there is a move for this char
729       if (charMoves != null && charMoves[0] != 0)
730       {
731          for (i = 0; i < charMoves.length; i++)
732          {
733             if (c == charMoves[i])
734                return true;
735             else if (c < charMoves[i] || charMoves[i] == 0)
736                break;
737          }
738       }
739 
740 
741       // For ranges, iterate thru the table to see if the current char
742       // is in some range
743       if (rangeMoves != null && rangeMoves[0] != 0)
744          for (i = 0; i < rangeMoves.length; i += 2)
745             if (c >= rangeMoves[i] && c <= rangeMoves[i + 1])
746                return true;
747             else if (c < rangeMoves[i] || rangeMoves[i] == 0)
748                break;
749 
750       //return (nextForNegatedList != null);
751       return false;
752    }
753 
754    public int getFirstValidPos(String   s, int i, int len)
755    {
756       if (onlyChar == 1)
757       {
758          char c = matchSingleChar;
759          while (c != s.charAt(i) && ++i < len);
760          return i;
761       }
762 
763       do
764       {
765          if (CanMoveUsingChar(s.charAt(i)))
766             return i;
767       } while (++i < len);
768 
769       return i;
770    }
771 
772    public int MoveFrom(char c, Vector newStates)
773    {
774       if (CanMoveUsingChar(c))
775       {
776          for (int i = next.epsilonMoves.size(); i-- > 0;)
777             InsertInOrder(newStates, (NfaState)next.epsilonMoves.elementAt(i));
778 
779          return kindToPrint;
780       }
781 
782       return Integer.MAX_VALUE;
783    }
784 
785    public static int MoveFromSet(char c, Vector states, Vector newStates)
786    {
787       int tmp;
788       int retVal = Integer.MAX_VALUE;
789 
790       for (int i = states.size(); i-- > 0;)
791          if (retVal >
792              (tmp = ((NfaState)states.elementAt(i)).MoveFrom(c, newStates)))
793             retVal = tmp;
794 
795       return retVal;
796    }
797 
798    public static int moveFromSetForRegEx(char c, NfaState[] states, NfaState[] newStates, int round)
799    {
800       int start = 0;
801       int sz = states.length;
802 
803       for (int i = 0; i < sz; i++)
804       {
805          NfaState tmp1, tmp2;
806 
807          if ((tmp1 = states[i]) == null)
808             break;
809 
810          if (tmp1.CanMoveUsingChar(c))
811          {
812             if (tmp1.kindToPrint != Integer.MAX_VALUE)
813             {
814                newStates[start] = null;
815                return 1;
816             }
817 
818             NfaState[] v = tmp1.next.epsilonMoveArray;
819             for (int j = v.length; j-- > 0;)
820             {
821                if ((tmp2 = v[j]).round != round)
822                {
823                   tmp2.round = round;
824                   newStates[start++] = tmp2;
825                }
826             }
827          }
828       }
829 
830       newStates[start] = null;
831       return Integer.MAX_VALUE;
832    }
833 
834    static Vector allBitVectors = new Vector();
835 
836    /* This function generates the bit vectors of low and hi bytes for common
837       bit vectors and retunrs those that are not common with anything (in
838       loBytes) and returns an array of indices that can be used to generate
839       the function names for char matching using the common bit vectors.
840       It also generates code to match a char with the common bit vectors.
841       (Need a better comment). */
842 
843    static int[] tmpIndices = new int[512]; // 2 * 256
844    void GenerateNonAsciiMoves(java.io.PrintWriter   ostr)
845    {
846       int i = 0, j = 0;
847       char hiByte;
848       int cnt = 0;
849       long[][] loBytes = new long[256][4];
850 
851       if ((charMoves == null || charMoves[0] == 0) &&
852           (rangeMoves == null || rangeMoves[0] == 0))
853          return;
854 
855       if (charMoves != null)
856       {
857          for (i = 0; i < charMoves.length; i++)
858          {
859             if (charMoves[i] == 0)
860                break;
861 
862             hiByte = (char)(charMoves[i] >> 8);
863             loBytes[hiByte][(charMoves[i] & 0xff) / 64] |=
864                               (1L << ((charMoves[i] & 0xff) % 64));
865          }
866       }
867 
868       if (rangeMoves != null)
869       {
870          for (i = 0; i < rangeMoves.length; i += 2)
871          {
872             if (rangeMoves[i] == 0)
873                break;
874 
875             char c, r;
876 
877             r = (char)(rangeMoves[i + 1] & 0xff);
878             hiByte = (char)(rangeMoves[i] >> 8);
879 
880             if (hiByte == (char)(rangeMoves[i + 1] >> 8))
881             {
882                for (c = (char)(rangeMoves[i] & 0xff); c <= r; c++)
883                   loBytes[hiByte][c / 64] |= (1L << (c % 64));
884 
885                continue;
886             }
887 
888             for (c = (char)(rangeMoves[i] & 0xff); c <= 0xff; c++)
889                loBytes[hiByte][c / 64] |= (1L << (c % 64));
890 
891             while (++hiByte < (char)(rangeMoves[i + 1] >> 8))
892             {
893                loBytes[hiByte][0] |= 0xffffffffffffffffL;
894                loBytes[hiByte][1] |= 0xffffffffffffffffL;
895                loBytes[hiByte][2] |= 0xffffffffffffffffL;
896                loBytes[hiByte][3] |= 0xffffffffffffffffL;
897             }
898 
899             for (c = 0; c <= r; c++)
900                loBytes[hiByte][c / 64] |= (1L << (c % 64));
901          }
902       }
903 
904       long[] common = null;
905       boolean[] done = new boolean[256];
906 
907       for (i = 0; i <= 255; i++)
908       {
909          if (done[i] ||
910              (done[i] =
911               loBytes[i][0] == 0 &&
912               loBytes[i][1] == 0 &&
913               loBytes[i][2] == 0 &&
914               loBytes[i][3] == 0))
915             continue;
916 
917          for (j = i + 1; j < 256; j++)
918          {
919             if (done[j])
920                continue;
921 
922             if (loBytes[i][0] == loBytes[j][0] &&
923                 loBytes[i][1] == loBytes[j][1] &&
924                 loBytes[i][2] == loBytes[j][2] &&
925                 loBytes[i][3] == loBytes[j][3])
926             {
927                done[j] = true;
928                if (common == null)