View Javadoc
1   /*
2    * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  package build.tools.generatebreakiteratordata;
27  
28  import java.io.*;
29  import java.util.Enumeration;
30  import java.util.Hashtable;
31  import java.util.Stack;
32  import java.util.Vector;
33  import java.util.zip.CRC32;
34  import sun.text.CompactByteArray;
35  
36  /**
37   * This class has the job of constructing a RuleBasedBreakIterator from a
38   * textual description. A Builder is constructed by GenerateBreakIteratorData,
39   * which uses it to construct the iterator itself and then throws it away.
40   * <p>The construction logic is separated out into its own class for two primary
41   * reasons:
42   * <ul>
43   * <li>The construction logic is quite sophisticated and large. Separating
44   * it out into its own class means the code must only be loaded into memory
45   * while a RuleBasedBreakIterator is being constructed, and can be purged after
46   * that.
47   * <li>There is a fair amount of state that must be maintained throughout the
48   * construction process that is not needed by the iterator after construction.
49   * Separating this state out into another class prevents all of the functions
50   * that construct the iterator from having to have really long parameter lists,
51   * (hopefully) contributing to readability and maintainability.
52   * </ul>
53   * <p>
54   * It'd be really nice if this could be an independent class rather than an
55   * inner class, because that would shorten the source file considerably, but
56   * making Builder an inner class of RuleBasedBreakIterator allows it direct
57   * access to RuleBasedBreakIterator's private members, which saves us from
58   * having to provide some kind of "back door" to the Builder class that could
59   * then also be used by other classes.
60   */
61  class RuleBasedBreakIteratorBuilder {
62  
63      /**
64       * A token used as a character-category value to identify ignore characters
65       */
66      protected static final byte IGNORE = -1;
67  
68      /**
69       * Tables that indexes from character values to character category numbers
70       */
71      private CompactByteArray charCategoryTable = null;
72      private SupplementaryCharacterData supplementaryCharCategoryTable = null;
73  
74      /**
75       * The table of state transitions used for forward iteration
76       */
77      private short[] stateTable = null;
78  
79      /**
80       * The table of state transitions used to sync up the iterator with the
81       * text in backwards and random-access iteration
82       */
83      private short[] backwardsStateTable = null;
84  
85      /**
86       * A list of flags indicating which states in the state table are accepting
87       * ("end") states
88       */
89      private boolean[] endStates = null;
90  
91      /**
92       * A list of flags indicating which states in the state table are
93       * lookahead states (states which turn lookahead on and off)
94       */
95      private boolean[] lookaheadStates = null;
96  
97      /**
98       * A table for additional data. May be used by a subclass of
99       * RuleBasedBreakIterator.
100      */
101     private byte[] additionalData = null;
102 
103     /**
104      * The number of character categories (and, thus, the number of columns in
105      * the state tables)
106      */
107     private int numCategories;
108 
109     /**
110      * A temporary holding place used for calculating the character categories.
111      * This object contains CharSet objects.
112      */
113     protected Vector<CharSet> categories = null;
114 
115     /**
116      * A table used to map parts of regexp text to lists of character
117      * categories, rather than having to figure them out from scratch each time
118      */
119     protected Hashtable<String, Object> expressions = null;
120 
121     /**
122      * A temporary holding place for the list of ignore characters
123      */
124     protected CharSet ignoreChars = null;
125 
126     /**
127      * A temporary holding place where the forward state table is built
128      */
129     protected Vector<short[]> tempStateTable = null;
130 
131     /**
132      * A list of all the states that have to be filled in with transitions to
133      * the next state that is created.  Used when building the state table from
134      * the regular expressions.
135      */
136     protected Vector<Integer> decisionPointList = null;
137 
138     /**
139      * A stack for holding decision point lists.  This is used to handle nested
140      * parentheses and braces in regexps.
141      */
142     protected Stack<Vector<Integer>> decisionPointStack = null;
143 
144     /**
145      * A list of states that loop back on themselves.  Used to handle .*?
146      */
147     protected Vector<Integer> loopingStates = null;
148 
149     /**
150      * Looping states actually have to be backfilled later in the process
151      * than everything else.  This is where a the list of states to backfill
152      * is accumulated.  This is also used to handle .*?
153      */
154     protected Vector<Integer> statesToBackfill = null;
155 
156     /**
157      * A list mapping pairs of state numbers for states that are to be combined
158      * to the state number of the state representing their combination.  Used
159      * in the process of making the state table deterministic to prevent
160      * infinite recursion.
161      */
162     protected Vector<int[]> mergeList = null;
163 
164     /**
165      * A flag that is used to indicate when the list of looping states can
166      * be reset.
167      */
168     protected boolean clearLoopingStates = false;
169 
170     /**
171      * A bit mask used to indicate a bit in the table's flags column that marks
172      * a state as an accepting state.
173      */
174     protected static final int END_STATE_FLAG = 0x8000;
175 
176     /**
177      * A bit mask used to indicate a bit in the table's flags column that marks
178      * a state as one the builder shouldn't loop to any looping states
179      */
180     protected static final int DONT_LOOP_FLAG = 0x4000;
181 
182     /**
183      * A bit mask used to indicate a bit in the table's flags column that marks
184      * a state as a lookahead state.
185      */
186     protected static final int LOOKAHEAD_STATE_FLAG = 0x2000;
187 
188     /**
189      * A bit mask representing the union of the mask values listed above.
190      * Used for clearing or masking off the flag bits.
191      */
192     protected static final int ALL_FLAGS = END_STATE_FLAG
193                                          | LOOKAHEAD_STATE_FLAG
194                                          | DONT_LOOP_FLAG;
195 
196     /**
197      * This is the main function for setting up the BreakIterator's tables. It
198      * just vectors different parts of the job off to other functions.
199      */
200     public RuleBasedBreakIteratorBuilder(String description) {
201         Vector<String> tempRuleList = buildRuleList(description);
202         buildCharCategories(tempRuleList);
203         buildStateTable(tempRuleList);
204         buildBackwardsStateTable(tempRuleList);
205     }
206 
207     /**
208      * Thus function has three main purposes:
209      * <ul><li>Perform general syntax checking on the description, so the rest
210      * of the build code can assume that it's parsing a legal description.
211      * <li>Split the description into separate rules
212      * <li>Perform variable-name substitutions (so that no one else sees
213      * variable names)
214      * </ul>
215      */
216     private Vector<String> buildRuleList(String description) {
217         // invariants:
218         // - parentheses must be balanced: ()[]{}<>
219         // - nothing can be nested inside <>
220         // - nothing can be nested inside [] except more []s
221         // - pairs of ()[]{}<> must not be empty
222         // - ; can only occur at the outer level
223         // - | can only appear inside ()
224         // - only one = or / can occur in a single rule
225         // - = and / cannot both occur in the same rule
226         // - <> can only occur on the left side of a = expression
227         //   (because we'll perform substitutions to eliminate them other places)
228         // - the left-hand side of a = expression can only be a single character
229         //   (possibly with \) or text inside <>
230         // - the right-hand side of a = expression must be enclosed in [] or ()
231         // - * may not occur at the beginning of a rule, nor may it follow
232         //   =, /, (, (, |, }, ;, or *
233         // - ? may only follow *
234         // - the rule list must contain at least one / rule
235         // - no rule may be empty
236         // - all printing characters in the ASCII range except letters and digits
237         //   are reserved and must be preceded by \
238         // - ! may only occur at the beginning of a rule
239 
240         // set up a vector to contain the broken-up description (each entry in the
241         // vector is a separate rule) and a stack for keeping track of opening
242         // punctuation
243         Vector<String> tempRuleList = new Vector<>();
244         Stack<Character> parenStack = new Stack<>();
245 
246         int p = 0;
247         int ruleStart = 0;
248         int c = '\u0000';
249         int lastC = '\u0000';
250         int lastOpen = '\u0000';
251         boolean haveEquals = false;
252         boolean havePipe = false;
253         boolean sawVarName = false;
254         final String charsThatCantPrecedeAsterisk = "=/{(|}*;\u0000";
255 
256         // if the description doesn't end with a semicolon, tack a semicolon onto the end
257         if (description.length() != 0 &&
258             description.codePointAt(description.length() - 1) != ';') {
259             description = description + ";";
260         }
261 
262         // for each character, do...
263         while (p < description.length()) {
264             c = description.codePointAt(p);
265 
266             switch (c) {
267                 // if the character is a backslash, skip the character that follows it
268                 // (it'll get treated as a literal character)
269                 case '\\':
270                     ++p;
271                     break;
272 
273                 // if the character is opening punctuation, verify that no nesting
274                 // rules are broken, and push the character onto the stack
275                 case '{':
276                 case '<':
277                 case '[':
278                 case '(':
279                     if (lastOpen == '<') {
280                         error("Can't nest brackets inside <>", p, description);
281                     }
282                     if (lastOpen == '[' && c != '[') {
283                         error("Can't nest anything in [] but []", p, description);
284                     }
285 
286                     // if we see < anywhere except on the left-hand side of =,
287                     // we must be seeing a variable name that was never defined
288                     if (c == '<' && (haveEquals || havePipe)) {
289                         error("Unknown variable name", p, description);
290                     }
291 
292                     lastOpen = c;
293                     parenStack.push(new Character((char)c));
294                     if (c == '<') {
295                         sawVarName = true;
296                     }
297                     break;
298 
299                 // if the character is closing punctuation, verify that it matches the
300                 // last opening punctuation we saw, and that the brackets contain
301                 // something, then pop the stack
302                 case '}':
303                 case '>':
304                 case ']':
305                 case ')':
306                     char expectedClose = '\u0000';
307                     switch (lastOpen) {
308                         case '{':
309                             expectedClose = '}';
310                             break;
311                         case '[':
312                             expectedClose = ']';
313                             break;
314                         case '(':
315                             expectedClose = ')';
316                             break;
317                         case '<':
318                             expectedClose = '>';
319                             break;
320                     }
321                     if (c != expectedClose) {
322                         error("Unbalanced parentheses", p, description);
323                     }
324                     if (lastC == lastOpen) {
325                         error("Parens don't contain anything", p, description);
326                     }
327                     parenStack.pop();
328                     if (!parenStack.empty()) {
329                         lastOpen = parenStack.peek().charValue();
330                     }
331                     else {
332                         lastOpen = '\u0000';
333                     }
334 
335                     break;
336 
337                 // if the character is an asterisk, make sure it occurs in a place
338                 // where an asterisk can legally go
339                 case '*':
340                     if (charsThatCantPrecedeAsterisk.indexOf(lastC) != -1) {
341                         error("Misplaced asterisk", p, description);
342                     }
343                     break;
344 
345                 // if the character is a question mark, make sure it follows an asterisk
346                 case '?':
347                     if (lastC != '*') {
348                         error("Misplaced ?", p, description);
349                     }
350                     break;
351 
352                 // if the character is an equals sign, make sure we haven't seen another
353                 // equals sign or a slash yet
354                 case '=':
355                     if (haveEquals || havePipe) {
356                         error("More than one = or / in rule", p, description);
357                     }
358                     haveEquals = true;
359                     break;
360 
361                 // if the character is a slash, make sure we haven't seen another slash
362                 // or an equals sign yet
363                 case '/':
364                     if (haveEquals || havePipe) {
365                         error("More than one = or / in rule", p, description);
366                     }
367                     if (sawVarName) {
368                         error("Unknown variable name", p, description);
369                     }
370                     havePipe = true;
371                     break;
372 
373                 // if the character is an exclamation point, make sure it occurs only
374                 // at the beginning of a rule
375                 case '!':
376                     if (lastC != ';' && lastC != '\u0000') {
377                         error("! can only occur at the beginning of a rule", p, description);
378                     }
379                     break;
380 
381                 // we don't have to do anything special on a period
382                 case '.':
383                     break;
384 
385                 // if the character is a syntax character that can only occur
386                 // inside [], make sure that it does in fact only occur inside [].
387                 case '^':
388                 case '-':
389                 case ':':
390                     if (lastOpen != '[' && lastOpen != '<') {
391                         error("Illegal character", p, description);
392                     }
393                     break;
394 
395                 // if the character is a semicolon, do the following...
396                 case ';':
397                     // make sure the rule contains something and that there are no
398                     // unbalanced parentheses or brackets
399                     if (lastC == ';' || lastC == '\u0000') {
400                         error("Empty rule", p, description);
401                     }
402                     if (!parenStack.empty()) {
403                         error("Unbalanced parenheses", p, description);
404                     }
405 
406                     if (parenStack.empty()) {
407                         // if the rule contained an = sign, call processSubstitution()
408                         // to replace the substitution name with the substitution text
409                         // wherever it appears in the description
410                         if (haveEquals) {
411                             description = processSubstitution(description.substring(ruleStart,
412                                             p), description, p + 1);
413                         }
414                         else {
415                             // otherwise, check to make sure the rule doesn't reference
416                             // any undefined substitutions
417                             if (sawVarName) {
418                                 error("Unknown variable name", p, description);
419                             }
420 
421                             // then add it to tempRuleList
422                             tempRuleList.addElement(description.substring(ruleStart, p));
423                         }
424 
425                         // and reset everything to process the next rule
426                         ruleStart = p + 1;
427                         haveEquals = havePipe = sawVarName = false;
428                     }
429                     break;
430 
431                 // if the character is a vertical bar, check to make sure that it
432                 // occurs inside a () expression and that the character that precedes
433                 // it isn't also a vertical bar
434                 case '|':
435                     if (lastC == '|') {
436                         error("Empty alternative", p, description);
437                     }
438                     if (parenStack.empty() || lastOpen != '(') {
439                         error("Misplaced |", p, description);
440                     }
441                     break;
442 
443                 // if the character is anything else (escaped characters are
444                 // skipped and don't make it here), it's an error
445                 default:
446                     if (c >= ' ' && c < '\u007f' && !Character.isLetter((char)c)
447                         && !Character.isDigit((char)c)) {
448                         error("Illegal character", p, description);
449                     }
450                     if (c >= Character.MIN_SUPPLEMENTARY_CODE_POINT) {
451                         ++p;
452                     }
453                     break;
454             }
455             lastC = c;
456             ++p;
457         }
458         if (tempRuleList.size() == 0) {
459             error("No valid rules in description", p, description);
460         }
461         return tempRuleList;
462     }
463 
464     /**
465      * This function performs variable-name substitutions.  First it does syntax
466      * checking on the variable-name definition.  If it's syntactically valid, it
467      * then goes through the remainder of the description and does a simple
468      * find-and-replace of the variable name with its text.  (The variable text
469      * must be enclosed in either [] or () for this to work.)
470      */
471     protected String processSubstitution(String substitutionRule, String description,
472                     int startPos) {
473         // isolate out the text on either side of the equals sign
474         String replace;
475         String replaceWith;
476         int equalPos = substitutionRule.indexOf('=');
477         replace = substitutionRule.substring(0, equalPos);
478         replaceWith = substitutionRule.substring(equalPos + 1);
479 
480         // check to see whether the substitution name is something we've declared
481         // to be "special".  For RuleBasedBreakIterator itself, this is "<ignore>".
482         // This function takes care of any extra processing that has to be done
483         // with "special" substitution names.
484         handleSpecialSubstitution(replace, replaceWith, startPos, description);
485 
486         // perform various other syntax checks on the rule
487         if (replaceWith.length() == 0) {
488             error("Nothing on right-hand side of =", startPos, description);
489         }
490         if (replace.length() == 0) {
491             error("Nothing on left-hand side of =", startPos, description);
492         }
493         if (replace.length() == 2 && replace.charAt(0) != '\\') {
494             error("Illegal left-hand side for =", startPos, description);
495         }
496         if (replace.length() >= 3 && replace.charAt(0) != '<' &&
497             replace.codePointBefore(equalPos) != '>') {
498             error("Illegal left-hand side for =", startPos, description);
499         }
500         if (!(replaceWith.charAt(0) == '[' &&
501               replaceWith.charAt(replaceWith.length() - 1) == ']') &&
502             !(replaceWith.charAt(0) == '(' &&
503               replaceWith.charAt(replaceWith.length() - 1) == ')')) {
504             error("Illegal right-hand side for =", startPos, description);
505         }
506 
507         // now go through the rest of the description (which hasn't been broken up
508         // into separate rules yet) and replace every occurrence of the
509         // substitution name with the substitution body
510         StringBuffer result = new StringBuffer();
511         result.append(description.substring(0, startPos));
512         int lastPos = startPos;
513         int pos = description.indexOf(replace, startPos);
514         while (pos != -1) {
515             result.append(description.substring(lastPos, pos));
516             result.append(replaceWith);
517             lastPos = pos + replace.length();
518             pos = description.indexOf(replace, lastPos);
519         }
520         result.append(description.substring(lastPos));
521         return result.toString();
522     }
523 
524     /**
525      * This function defines a protocol for handling substitution names that
526      * are "special," i.e., that have some property beyond just being
527      * substitutions.  At the RuleBasedBreakIterator level, we have one
528      * special substitution name, "<ignore>".  Subclasses can override this
529      * function to add more.  Any special processing that has to go on beyond
530      * that which is done by the normal substitution-processing code is done
531      * here.
532      */
533     protected void handleSpecialSubstitution(String replace, String replaceWith,
534                 int startPos, String description) {
535         // if we get a definition for a substitution called "ignore", it defines
536         // the ignore characters for the iterator.  Check to make sure the expression
537         // is a [] expression, and if it is, parse it and store the characters off
538         // to the side.
539         if (replace.equals("<ignore>")) {
540             if (replaceWith.charAt(0) == '(') {
541                 error("Ignore group can't be enclosed in (", startPos, description);
542             }
543             ignoreChars = CharSet.parseString(replaceWith);
544         }
545     }
546 
547     /**
548      * This function builds the character category table.  On entry,
549      * tempRuleList is a vector of break rules that has had variable names substituted.
550      * On exit, the charCategoryTable data member has been initialized to hold the
551      * character category table, and tempRuleList's rules have been munged to contain
552      * character category numbers everywhere a literal character or a [] expression
553      * originally occurred.
554      */
555     @SuppressWarnings("fallthrough")
556     protected void buildCharCategories(Vector<String> tempRuleList) {
557         int bracketLevel = 0;
558         int p = 0;
559         int lineNum = 0;
560 
561         // build hash table of every literal character or [] expression in the rule list
562         // and use CharSet.parseString() to derive a CharSet object representing the
563         // characters each refers to
564         expressions = new Hashtable<>();
565         while (lineNum < tempRuleList.size()) {
566             String line = tempRuleList.elementAt(lineNum);
567             p = 0;
568             while (p < line.length()) {
569                 int c = line.codePointAt(p);
570                 switch (c) {
571                     // skip over all syntax characters except [
572                     case '{': case '}': case '(': case ')': case '*': case '.':
573                     case '/': case '|': case ';': case '?': case '!':
574                         break;
575 
576                     // for [, find the matching ] (taking nested [] pairs into account)
577                     // and add the whole expression to the expression list
578                     case '[':
579                         int q = p + 1;
580                         ++bracketLevel;
581                         while (q < line.length() && bracketLevel != 0) {
582                             c = line.codePointAt(q);
583                             switch (c) {
584                             case '\\':
585                                 q++;
586                                 break;
587                             case '[':
588                                 ++bracketLevel;
589                                 break;
590                             case ']':
591                                 --bracketLevel;
592                                 break;
593                             }
594                             q = q + Character.charCount(c);
595                         }
596                         if (expressions.get(line.substring(p, q)) == null) {
597                             expressions.put(line.substring(p, q), CharSet.parseString(line.substring(p, q)));
598                         }
599                         p = q - 1;
600                         break;
601 
602                     // for \ sequences, just move to the next character and treat
603                     // it as a single character
604                     case '\\':
605                         ++p;
606                         c = line.codePointAt(p);
607                         // DON'T break; fall through into "default" clause
608 
609                     // for an isolated single character, add it to the expression list
610                     default:
611                         expressions.put(line.substring(p, p + 1), CharSet.parseString(line.substring(p, p + 1)));
612                         break;
613                 }
614                 p += Character.charCount(line.codePointAt(p));
615             }
616             ++lineNum;
617         }
618         // dump CharSet's internal expression cache
619         CharSet.releaseExpressionCache();
620 
621         // create the temporary category table (which is a vector of CharSet objects)
622         categories = new Vector<>();
623         if (ignoreChars != null) {
624             categories.addElement(ignoreChars);
625         }
626         else {
627             categories.addElement(new CharSet());
628         }
629         ignoreChars = null;
630 
631         // this is a hook to allow subclasses to add categories on their own
632         mungeExpressionList(expressions);
633 
634         // Derive the character categories.  Go through the existing character categories
635         // looking for overlap.  Any time there's overlap, we create a new character
636         // category for the characters that overlapped and remove them from their original
637         // category.  At the end, any characters that are left in the expression haven't
638         // been mentioned in any category, so another new category is created for them.
639         // For example, if the first expression is [abc], then a, b, and c will be placed
640         // into a single character category.  If the next expression is [bcd], we will first
641         // remove b and c from their existing category (leaving a behind), create a new
642         // category for b and c, and then create another new category for d (which hadn't
643         // been mentioned in the previous expression).
644         // At no time should a character ever occur in more than one character category.
645 
646         // for each expression in the expressions list, do...
647         for (Enumeration<Object> iter = expressions.elements(); iter.hasMoreElements(); ) {
648             // initialize the working char set to the chars in the current expression
649             CharSet e = (CharSet)iter.nextElement();
650 
651             // for each category in the category list, do...
652             for (int j = categories.size() - 1; !e.empty() && j > 0; j--) {
653 
654                 // if there's overlap between the current working set of chars
655                 // and the current category...
656                 CharSet that = categories.elementAt(j);
657                 if (!that.intersection(e).empty()) {
658 
659                     // add a new category for the characters that were in the
660                     // current category but not in the working char set
661                     CharSet temp = that.difference(e);
662                     if (!temp.empty()) {
663                         categories.addElement(temp);
664                     }
665 
666                     // remove those characters from the working char set and replace
667                     // the current category with the characters that it did
668                     // have in common with the current working char set
669                     temp = e.intersection(that);
670                     e = e.difference(that);
671                     if (!temp.equals(that)) {
672                         categories.setElementAt(temp, j);
673                     }
674                 }
675             }
676 
677             // if there are still characters left in the working char set,
678             // add a new category containing them
679             if (!e.empty()) {
680                 categories.addElement(e);
681             }
682         }
683 
684         // we have the ignore characters stored in position 0.  Make an extra pass through
685         // the character category list and remove anything from the ignore list that shows
686         // up in some other category
687         CharSet allChars = new CharSet();
688         for (int i = 1; i < categories.size(); i++) {
689             allChars = allChars.union(categories.elementAt(i));
690         }
691         CharSet ignoreChars = categories.elementAt(0);
692         ignoreChars = ignoreChars.difference(allChars);
693         categories.setElementAt(ignoreChars, 0);
694 
695         // now that we've derived the character categories, go back through the expression
696         // list and replace each CharSet object with a String that represents the
697         // character categories that expression refers to.  The String is encoded: each
698         // character is a character category number (plus 0x100 to avoid confusing them
699         // with syntax characters in the rule grammar)
700 
701         for (Enumeration<String> iter = expressions.keys(); iter.hasMoreElements(); ) {
702             String key = iter.nextElement();
703             CharSet cs = (CharSet)expressions.get(key);
704             StringBuffer cats = new StringBuffer();
705 
706             // for each category...
707             for (int j = 0; j < categories.size(); j++) {
708 
709                 // if the current expression contains characters in that category...
710                 CharSet temp = cs.intersection(categories.elementAt(j));
711                 if (!temp.empty()) {
712 
713                     // then add the encoded category number to the String for this
714                     // expression
715                     cats.append((char)(0x100 + j));
716                     if (temp.equals(cs)) {
717                         break;
718                     }
719                 }
720             }
721 
722             // once we've finished building the encoded String for this expression,
723             // replace the CharSet object with it
724             expressions.put(key, cats.toString());
725         }
726 
727         // and finally, we turn the temporary category table into a permanent category
728         // table, which is a CompactByteArray. (we skip category 0, which by definition
729         // refers to all characters not mentioned specifically in the rules)
730         charCategoryTable = new CompactByteArray((byte)0);
731         supplementaryCharCategoryTable = new SupplementaryCharacterData((byte)0);
732 
733         // for each category...
734         for (int i = 0; i < categories.size(); i++) {
735             CharSet chars = categories.elementAt(i);
736 
737             // go through the character ranges in the category one by one...
738             Enumeration<int[]> enum_ = chars.getChars();
739             while (enum_.hasMoreElements()) {
740                 int[] range = enum_.nextElement();
741 
742                 // and set the corresponding elements in the CompactArray accordingly
743                 if (i != 0) {
744                     if (range[0] < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
745                         if (range[1] < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
746                             charCategoryTable.setElementAt((char)range[0], (char)range[1], (byte)i);
747                         } else {
748                             charCategoryTable.setElementAt((char)range[0], (char)0xFFFF, (byte)i);
749                             supplementaryCharCategoryTable.appendElement(Character.MIN_SUPPLEMENTARY_CODE_POINT, range[1], (byte)i);
750                         }
751                     } else {
752                         supplementaryCharCategoryTable.appendElement(range[0], range[1], (byte)i);
753                     }
754                 }
755 
756                 // (category 0 is special-- it's the hiding place for the ignore
757                 // characters, whose real category number in the CompactArray is
758                 // -1 [this is because category 0 contains all characters not
759                 // specifically mentioned anywhere in the rules] )
760                 else {
761                     if (range[0] < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
762                         if (range[1] < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
763                             charCategoryTable.setElementAt((char)range[0], (char)range[1], IGNORE);
764                         } else {
765                             charCategoryTable.setElementAt((char)range[0], (char)0xFFFF, IGNORE);
766                             supplementaryCharCategoryTable.appendElement(Character.MIN_SUPPLEMENTARY_CODE_POINT, range[1], IGNORE);
767                         }
768                     } else {
769                         supplementaryCharCategoryTable.appendElement(range[0], range[1], IGNORE);
770                     }
771                 }
772             }
773         }
774 
775         // once we've populated the CompactArray, compact it
776         charCategoryTable.compact();
777 
778         // And, complete the category table for supplementary characters
779         supplementaryCharCategoryTable.complete();
780 
781         // initialize numCategories
782         numCategories = categories.size();
783     }
784 
785     protected void mungeExpressionList(Hashtable<String, Object> expressions) {
786         // empty in the parent class.  This function provides a hook for subclasses
787         // to mess with the character category table.
788     }
789 
790     /**
791      * This is the function that builds the forward state table.  Most of the real
792      * work is done in parseRule(), which is called once for each rule in the
793      * description.
794      */
795     private void buildStateTable(Vector<String> tempRuleList) {
796         // initialize our temporary state table, and fill it with two states:
797         // state 0 is a dummy state that allows state 1 to be the starting state
798         // and 0 to represent "stop".  State 1 is added here to seed things
799         // before we start parsing
800         tempStateTable = new Vector<>();
801         tempStateTable.addElement(new short[numCategories + 1]);
802         tempStateTable.addElement(new short[numCategories + 1]);
803 
804         // call parseRule() for every rule in the rule list (except those which
805         // start with !, which are actually backwards-iteration rules)
806         for (int i = 0; i < tempRuleList.size(); i++) {
807             String rule = tempRuleList.elementAt(i);
808             if (rule.charAt(0) != '!') {
809                 parseRule(rule, true);
810             }
811         }
812 
813         // finally, use finishBuildingStateTable() to minimize the number of
814         // states in the table and perform some other cleanup work
815         finishBuildingStateTable(true);
816     }
817 
818     /**
819      * This is where most of the work really happens.  This routine parses a single
820      * rule in the rule description, adding and modifying states in the state
821      * table according to the new expression.  The state table is kept deterministic
822      * throughout the whole operation, although some ugly postprocessing is needed
823      * to handle the *? token.
824      */
825     private void parseRule(String rule, boolean forward) {
826         // algorithm notes:
827         //   - The basic idea here is to read successive character-category groups
828         //   from the input string.  For each group, you create a state and point
829         //   the appropriate entries in the previous state to it.  This produces a
830         //   straight line from the start state to the end state.  The {}, *, and (|)
831         //   idioms produce branches in this straight line.  These branches (states
832         //   that can transition to more than one other state) are called "decision
833         //   points."  A list of decision points is kept.  This contains a list of
834         //   all states that can transition to the next state to be created.  For a
835         //   straight line progression, the only thing in the decision-point list is
836         //   the current state.  But if there's a branch, the decision-point list
837         //   will contain all of the beginning points of the branch when the next
838         //   state to be created represents the end point of the branch.  A stack is
839         //   used to save decision point lists in the presence of nested parentheses
840         //   and the like.  For example, when a { is encountered, the current decision
841         //   point list is saved on the stack and restored when the corresponding }
842         //   is encountered.  This way, after the } is read, the decision point list
843         //   will contain both the state right before the } _and_ the state before
844         //   the whole {} expression.  Both of these states can transition to the next
845         //   state after the {} expression.
846         //   - one complication arises when we have to stamp a transition value into
847         //   an array cell that already contains one.  The updateStateTable() and
848         //   mergeStates() functions handle this case.  Their basic approach is to
849         //   create a new state that combines the two states that conflict and point
850         //   at it when necessary.  This happens recursively, so if the merged states
851         //   also conflict, they're resolved in the same way, and so on.  There are
852         //   a number of tests aimed at preventing infinite recursion.
853         //   - another complication arises with repeating characters.  It's somewhat
854         //   ambiguous whether the user wants a greedy or non-greedy match in these cases.
855         //   (e.g., whether "[a-z]*abc" means the SHORTEST sequence of letters ending in
856         //   "abc" or the LONGEST sequence of letters ending in "abc".  We've adopted
857         //   the *? to mean "shortest" and * by itself to mean "longest".  (You get the
858         //   same result with both if there's no overlap between the repeating character
859         //   group and the group immediately following it.)  Handling the *? token is
860         //   rather complicated and involves keeping track of whether a state needs to
861         //   be merged (as described above) or merely overwritten when you update one of
862         //   its cells, and copying the contents of a state that loops with a *? token
863         //   into some of the states that follow it after the rest of the table-building
864         //   process is complete ("backfilling").
865         // implementation notes:
866         //   - This function assumes syntax checking has been performed on the input string
867         //   prior to its being passed in here.  It assumes that parentheses are
868         //   balanced, all literal characters are enclosed in [] and turned into category
869         //   numbers, that there are no illegal characters or character sequences, and so
870         //   on.  Violation of these invariants will lead to undefined behavior.
871         //   - It'd probably be better to use linked lists rather than Vector and Stack
872         //   to maintain the decision point list and stack.  I went for simplicity in
873         //   this initial implementation.  If performance is critical enough, we can go
874         //   back and fix this later.
875         //   -There are a number of important limitations on the *? token.  It does not work
876         //   right when followed by a repeating character sequence (e.g., ".*?(abc)*")
877         //   (although it does work right when followed by a single repeating character).
878         //   It will not always work right when nested in parentheses or braces (although
879         //   sometimes it will).  It also will not work right if the group of repeating
880         //   characters and the group of characters that follows overlap partially
881         //   (e.g., "[a-g]*?[e-j]").  None of these capabilites was deemed necessary for
882         //   describing breaking rules we know about, so we left them out for
883         //   expeditiousness.
884         //   - Rules such as "[a-z]*?abc;" will be treated the same as "[a-z]*?aa*bc;"--
885         //   that is, if the string ends in "aaaabc", the break will go before the first
886         //   "a" rather than the last one.  Both of these are limitations in the design
887         //   of RuleBasedBreakIterator and not limitations of the rule parser.
888 
889         int p = 0;
890         int currentState = 1;   // don't use state number 0; 0 means "stop"
891         int lastState = currentState;
892         String pendingChars = "";
893 
894         decisionPointStack = new Stack<>();
895         decisionPointList = new Vector<>();
896         loopingStates = new Vector<>();
897         statesToBackfill = new Vector<>();
898 
899         short[] state;
900         boolean sawEarlyBreak = false;
901 
902         // if we're adding rules to the backward state table, mark the initial state
903         // as a looping state
904         if (!forward) {
905             loopingStates.addElement(new Integer(1));
906         }
907 
908         // put the current state on the decision point list before we start
909         decisionPointList.addElement(new Integer(currentState)); // we want currentState to
910                                                                  // be 1 here...
911         currentState = tempStateTable.size() - 1;   // but after that, we want it to be
912                                                     // 1 less than the state number of the next state
913         while (p < rule.length()) {
914             int c = rule.codePointAt(p);
915             clearLoopingStates = false;
916 
917             // this section handles literal characters, escaped characters (which are
918             // effectively literal characters too), the . token, and [] expressions
919             if (c == '['
920                 || c == '\\'
921                 || Character.isLetter(c)
922                 || Character.isDigit(c)
923                 || c < ' '
924                 || c == '.'
925                 || c >= '\u007f') {
926 
927                 // if we're not on a period, isolate the expression and look up
928                 // the corresponding category list
929                 if (c != '.') {
930                     int q = p;
931 
932                     // if we're on a backslash, the expression is the character
933                     // after the backslash
934                     if (c == '\\') {
935                         q = p + 2;
936                         ++p;
937                     }
938 
939                     // if we're on an opening bracket, scan to the closing bracket
940                     // to isolate the expression
941                     else if (c == '[') {
942                         int bracketLevel = 1;
943 
944                         q += Character.charCount(rule.codePointAt(q));
945                         while (bracketLevel > 0) {
946                             c = rule.codePointAt(q);
947                             if (c == '[') {
948                                 ++bracketLevel;
949                             }
950                             else if (c == ']') {
951                                 --bracketLevel;
952                             }
953                             else if (c == '\\') {
954                                 c = rule.codePointAt(++q);
955                             }
956                             q += Character.charCount(c);
957                         }
958                     }
959 
960                     // otherwise, the expression is just the character itself
961                     else {
962                         q = p + Character.charCount(c);
963                     }
964 
965                     // look up the category list for the expression and store it
966                     // in pendingChars
967                     pendingChars = (String)expressions.get(rule.substring(p, q));
968 
969                     // advance the current position past the expression
970                     p = q - Character.charCount(rule.codePointBefore(q));
971                 }
972 
973                 // if the character we're on is a period, we end up down here
974                 else {
975                     int rowNum = decisionPointList.lastElement().intValue();
976                     state = tempStateTable.elementAt(rowNum);
977 
978                     // if the period is followed by an asterisk, then just set the current
979                     // state to loop back on itself
980                     if (p + 1 < rule.length() && rule.charAt(p + 1) == '*' && state[0] != 0) {
981                         decisionPointList.addElement(new Integer(state[0]));
982                         pendingChars = "";
983                         ++p;
984                     }
985 
986                     // otherwise, fabricate a category list ("pendingChars") with
987                     // every category in it
988                     else {
989                         StringBuffer temp = new StringBuffer();
990                         for (int i = 0; i < numCategories; i++)
991                             temp.append((char)(i + 0x100));
992                         pendingChars = temp.toString();
993                     }
994                 }
995 
996                 // we'll end up in here for all expressions except for .*, which is
997                 // special-cased above
998                 if (pendingChars.length() != 0) {
999 
1000                     // if the expression is followed by an asterisk, then push a copy
1001                     // of the current desicion point list onto the stack (this is
1002                     // the same thing we do on an opening brace)
1003                     if (p + 1 < rule.length() && rule.charAt(p + 1) == '*') {
1004                         @SuppressWarnings("unchecked")
1005                         Vector<Integer> clone = (Vector<Integer>)decisionPointList.clone();
1006                         decisionPointStack.push(clone);
1007                     }
1008 
1009                     // create a new state, add it to the list of states to backfill
1010                     // if we have looping states to worry about, set its "don't make
1011                     // me an accepting state" flag if we've seen a slash, and add
1012                     // it to the end of the state table
1013                     int newState = tempStateTable.size();
1014                     if (loopingStates.size() != 0) {
1015                         statesToBackfill.addElement(new Integer(newState));
1016                     }
1017                     state = new short[numCategories + 1];
1018                     if (sawEarlyBreak) {
1019                         state[numCategories] = DONT_LOOP_FLAG;
1020                     }
1021                     tempStateTable.addElement(state);
1022 
1023                     // update everybody in the decision point list to point to
1024                     // the new state (this also performs all the reconciliation
1025                     // needed to make the table deterministic), then clear the
1026                     // decision point list
1027                     updateStateTable(decisionPointList, pendingChars, (short)newState);
1028                     decisionPointList.removeAllElements();
1029 
1030                     // add all states created since the last literal character we've
1031                     // seen to the decision point list
1032                     lastState = currentState;
1033                     do {
1034                         ++currentState;
1035                         decisionPointList.addElement(new Integer(currentState));
1036                     } while (currentState + 1 < tempStateTable.size());
1037                 }
1038             }
1039 
1040             // a { marks the beginning of an optional run of characters.  Push a
1041             // copy of the current decision point list onto the stack.  This saves
1042             // it, preventing it from being affected by whatever's inside the parentheses.
1043             // This decision point list is restored when a } is encountered.
1044             else if (c == '{') {
1045                 @SuppressWarnings("unchecked")
1046                 Vector<Integer> clone = (Vector<Integer>)decisionPointList.clone();
1047                 decisionPointStack.push(clone);
1048             }
1049 
1050             // a } marks the end of an optional run of characters.  Pop the last decision
1051             // point list off the stack and merge it with the current decision point list.
1052             // a * denotes a repeating character or group (* after () is handled separately
1053             // below).  In addition to restoring the decision point list, modify the
1054             // current state to point to itself on the appropriate character categories.
1055             else if (c == '}' || c == '*') {
1056                 // when there's a *, update the current state to loop back on itself
1057                 // on the character categories that caused us to enter this state
1058                 if (c == '*') {
1059                     for (int i = lastState + 1; i < tempStateTable.size(); i++) {
1060                         Vector<Integer> temp = new Vector<>();
1061                         temp.addElement(new Integer(i));
1062                         updateStateTable(temp, pendingChars, (short)(lastState + 1));
1063                     }
1064                 }
1065 
1066                 // pop the top element off the decision point stack and merge
1067                 // it with the current decision point list (this causes the divergent
1068                 // paths through the state table to come together again on the next
1069                 // new state)
1070                 Vector<Integer> temp = decisionPointStack.pop();
1071                 for (int i = 0; i < decisionPointList.size(); i++)
1072                     temp.addElement(decisionPointList.elementAt(i));
1073                 decisionPointList = temp;
1074             }
1075 
1076             // a ? after a * modifies the behavior of * in cases where there is overlap
1077             // between the set of characters that repeat and the characters which follow.
1078             // Without the ?, all states following the repeating state, up to a state which
1079             // is reached by a character that doesn't overlap, will loop back into the
1080             // repeating state.  With the ?, the mark states following the *? DON'T loop
1081             // back into the repeating state.  Thus, "[a-z]*xyz" will match the longest
1082             // sequence of letters that ends in "xyz," while "[a-z]*? will match the
1083             // _shortest_ sequence of letters that ends in "xyz".
1084             // We use extra bookkeeping to achieve this effect, since everything else works
1085             // according to the "longest possible match" principle.  The basic principle
1086             // is that transitions out of a looping state are written in over the looping
1087             // value instead of being reconciled, and that we copy the contents of the
1088             // looping state into empty cells of all non-terminal states that follow the
1089             // looping state.
1090             else if (c == '?') {
1091                 setLoopingStates(decisionPointList, decisionPointList);
1092             }
1093 
1094             // a ( marks the beginning of a sequence of characters.  Parentheses can either
1095             // contain several alternative character sequences (i.e., "(ab|cd|ef)"), or
1096             // they can contain a sequence of characters that can repeat (i.e., "(abc)*").  Thus,
1097             // A () group can have multiple entry and exit points.  To keep track of this,
1098             // we reserve TWO spots on the decision-point stack.  The top of the stack is
1099             // the list of exit points, which becomes the current decision point list when
1100             // the ) is reached.  The next entry down is the decision point list at the
1101             // beginning of the (), which becomes the current decision point list at every
1102             // entry point.
1103             // In addition to keeping track of the exit points and the active decision
1104             // points before the ( (i.e., the places from which the () can be entered),
1105             // we need to keep track of the entry points in case the expression loops
1106             // (i.e., is followed by *).  We do that by creating a dummy state in the
1107             // state table and adding it to the decision point list (BEFORE it's duplicated
1108             // on the stack).  Nobody points to this state, so it'll get optimized out
1109             // at the end.  It exists only to hold the entry points in case the ()
1110             // expression loops.
1111             else if (c == '(') {
1112 
1113                 // add a new state to the state table to hold the entry points into
1114                 // the () expression
1115                 tempStateTable.addElement(new short[numCategories + 1]);
1116 
1117                 // we have to adjust lastState and currentState to account for the
1118                 // new dummy state
1119                 lastState = currentState;
1120                 ++currentState;
1121 
1122                 // add the current state to the decision point list (add it at the
1123                 // BEGINNING so we can find it later)
1124                 decisionPointList.insertElementAt(new Integer(currentState), 0);
1125 
1126                 // finally, push a copy of the current decision point list onto the
1127                 // stack (this keeps track of the active decision point list before
1128                 // the () expression), followed by an empty decision point list
1129                 // (this will hold the exit points)
1130                 @SuppressWarnings("unchecked")
1131                 Vector<Integer> clone = (Vector<Integer>)decisionPointList.clone();
1132                 decisionPointStack.push(clone);
1133                 decisionPointStack.push(new Vector<Integer>());
1134             }
1135 
1136             // a | separates alternative character sequences in a () expression.  When
1137             // a | is encountered, we add the current decision point list to the exit-point
1138             // list, and restore the decision point list to its state prior to the (.
1139             else if (c == '|') {
1140 
1141                 // pick out the top two decision point lists on the stack
1142                 Vector<Integer> oneDown = decisionPointStack.pop();
1143                 Vector<Integer> twoDown = decisionPointStack.peek();
1144                 decisionPointStack.push(oneDown);
1145 
1146                 // append the current decision point list to the list below it
1147                 // on the stack (the list of exit points), and restore the
1148                 // current decision point list to its state before the () expression
1149                 for (int i = 0; i < decisionPointList.size(); i++)
1150                     oneDown.addElement(decisionPointList.elementAt(i));
1151                 @SuppressWarnings("unchecked")
1152                 Vector<Integer> clone = (Vector<Integer>)twoDown.clone();
1153                 decisionPointList = clone;
1154             }
1155 
1156             // a ) marks the end of a sequence of characters.  We do one of two things
1157             // depending on whether the sequence repeats (i.e., whether the ) is followed
1158             // by *):  If the sequence doesn't repeat, then the exit-point list is merged
1159             // with the current decision point list and the decision point list from before
1160             // the () is thrown away.  If the sequence does repeat, then we fish out the
1161             // state we were in before the ( and copy all of its forward transitions
1162             // (i.e., every transition added by the () expression) into every state in the
1163             // exit-point list and the current decision point list.  The current decision
1164             // point list is then merged with both the exit-point list AND the saved version
1165             // of the decision point list from before the ().  Then we throw out the *.
1166             else if (c == ')') {
1167 
1168                 // pull the exit point list off the stack, merge it with the current
1169                 // decision point list, and make the merged version the current
1170                 // decision point list
1171                 Vector<Integer> exitPoints = decisionPointStack.pop();
1172                 for (int i = 0; i < decisionPointList.size(); i++)
1173                     exitPoints.addElement(decisionPointList.elementAt(i));
1174                 decisionPointList = exitPoints;
1175 
1176                 // if the ) isn't followed by a *, then all we have to do is throw
1177                 // away the other list on the decision point stack, and we're done
1178                 if (p + 1 >= rule.length() || rule.charAt(p + 1) != '*') {
1179                     decisionPointStack.pop();
1180                 }
1181 
1182                 // but if the sequence repeats, we have a lot more work to do...
1183                 else {
1184 
1185                     // now exitPoints and decisionPointList have to point to equivalent
1186                     // vectors, but not the SAME vector
1187                     @SuppressWarnings("unchecked")
1188                     Vector<Integer> clone = (Vector<Integer>)decisionPointList.clone();
1189                     exitPoints = clone;
1190 
1191                     // pop the original decision point list off the stack
1192                     Vector<Integer> temp = decisionPointStack.pop();
1193 
1194                     // we squirreled away the row number of our entry point list
1195                     // at the beginning of the original decision point list.  Fish
1196                     // that state number out and retrieve the entry point list
1197                     int tempStateNum = temp.firstElement().intValue();
1198                     short[] tempState = tempStateTable.elementAt(tempStateNum);
1199 
1200                     // merge the original decision point list with the current
1201                     // decision point list
1202                     for (int i = 0; i < decisionPointList.size(); i++)
1203                         temp.addElement(decisionPointList.elementAt(i));
1204                     decisionPointList = temp;
1205 
1206                     // finally, copy every forward reference from the entry point
1207                     // list into every state in the new decision point list
1208                     for (int i = 0; i < tempState.length; i++) {
1209                         if (tempState[i] > tempStateNum) {
1210                             updateStateTable(exitPoints,
1211                                              new Character((char)(i + 0x100)).toString(),
1212                                              tempState[i]);
1213                         }
1214                     }
1215 
1216                     // update lastState and currentState, and throw away the *
1217                     lastState = currentState;
1218                     currentState = tempStateTable.size() - 1;
1219                     ++p;
1220                 }
1221             }
1222 
1223             // a / marks the position where the break is to go if the character sequence
1224             // matches this rule.  We update the flag word of every state on the decision
1225             // point list to mark them as ending states, and take note of the fact that
1226             // we've seen the slash
1227             else if (c == '/') {
1228                 sawEarlyBreak = true;
1229                 for (int i = 0; i < decisionPointList.size(); i++) {
1230                     state = tempStateTable.elementAt(decisionPointList.
1231                                     elementAt(i).intValue());
1232                     state[numCategories] |= LOOKAHEAD_STATE_FLAG;
1233                 }
1234             }
1235 
1236             // if we get here without executing any of the above clauses, we have a
1237             // syntax error.  However, for now we just ignore the offending character
1238             // and move on
1239 
1240             // clearLoopingStates is a signal back from updateStateTable() that we've
1241             // transitioned to a state that won't loop back to the current looping
1242             // state.  (In other words, we've gotten to a point where we can no longer
1243             // go back into a *? we saw earlier.)  Clear out the list of looping states
1244             // and backfill any states that need to be backfilled.
1245             if (clearLoopingStates) {
1246                 setLoopingStates(null, decisionPointList);
1247             }
1248 
1249             // advance to the next character, now that we've processed the current
1250             // character
1251             p += Character.charCount(c);
1252         }
1253 
1254         // this takes care of backfilling any states that still need to be backfilled
1255         setLoopingStates(null, decisionPointList);
1256 
1257         // when we reach the end of the string, we do a postprocessing step to mark the
1258         // end states.  The decision point list contains every state that can transition
1259         // to the end state-- that is, every state that is the last state in a sequence
1260         // that matches the rule.  All of these states are considered "mark states"
1261         // or "accepting states"-- that is, states that cause the position returned from
1262         // next() to be updated.  A mark state represents a possible break position.
1263         // This allows us to look ahead and remember how far the rule matched
1264         // before following the new branch (see next() for more information).
1265         // The temporary state table has an extra "flag column" at the end where this
1266         // information is stored.  We mark the end states by setting a flag in their
1267         // flag column.
1268         // Now if we saw the / in the rule, then everything after it is lookahead
1269         // material and the break really goes where the slash is.  In this case,
1270         // we mark these states as BOTH accepting states and lookahead states.  This
1271         // signals that these states cause the break position to be updated to the
1272         // position of the slash rather than the current break position.
1273         for (int i = 0; i < decisionPointList.size(); i++) {
1274             int rowNum = decisionPointList.elementAt(i).intValue();
1275             state = tempStateTable.elementAt(rowNum);
1276             state[numCategories] |= END_STATE_FLAG;
1277             if (sawEarlyBreak) {
1278                 state[numCategories] |= LOOKAHEAD_STATE_FLAG;
1279             }
1280         }
1281     }
1282 
1283 
1284     /**
1285      * Update entries in the state table, and merge states when necessary to keep
1286      * the table deterministic.
1287      * @param rows The list of rows that need updating (the decision point list)
1288      * @param pendingChars A character category list, encoded in a String.  This is the
1289      * list of the columns that need updating.
1290      * @param newValue Update the cells specfied above to contain this value
1291      */
1292     private void updateStateTable(Vector<Integer> rows,
1293                                   String pendingChars,
1294                                   short newValue) {
1295         // create a dummy state that has the specified row number (newValue) in
1296         // the cells that need to be updated (those specified by pendingChars)
1297         // and 0 in the other cells
1298         short[] newValues = new short[numCategories + 1];
1299         for (int i = 0; i < pendingChars.length(); i++)
1300             newValues[(int)(pendingChars.charAt(i)) - 0x100] = newValue;
1301 
1302         // go through the list of rows to update, and update them by calling
1303         // mergeStates() to merge them the the dummy state we created
1304         for (int i = 0; i < rows.size(); i++) {
1305             mergeStates(rows.elementAt(i).intValue(), newValues, rows);
1306         }
1307     }
1308 
1309     /**
1310      * The real work of making the state table deterministic happens here.  This function
1311      * merges a state in the state table (specified by rowNum) with a state that is
1312      * passed in (newValues).  The basic process is to copy the nonzero cells in newStates
1313      * into the state in the state table (we'll call that oldValues).  If there's a
1314      * collision (i.e., if the same cell has a nonzero value in both states, and it's
1315      * not the SAME value), then we have to reconcile the collision.  We do this by
1316      * creating a new state, adding it to the end of the state table, and using this
1317      * function recursively to merge the original two states into a single, combined
1318      * state.  This process may happen recursively (i.e., each successive level may
1319      * involve collisions).  To prevent infinite recursion, we keep a log of merge
1320      * operations.  Any time we're merging two states we've merged before, we can just
1321      * supply the row number for the result of that merge operation rather than creating
1322      * a new state just like it.
1323      * @param rowNum The row number in the state table of the state to be updated
1324      * @param newValues The state to merge it with.
1325      * @param rowsBeingUpdated A copy of the list of rows passed to updateStateTable()
1326      * (itself a copy of the decision point list from parseRule()).  Newly-created
1327      * states get added to the decision point list if their "parents" were on it.
1328      */
1329     private void mergeStates(int rowNum,
1330                              short[] newValues,
1331                              Vector<Integer> rowsBeingUpdated) {
1332         short[] oldValues = tempStateTable.elementAt(rowNum);
1333         boolean isLoopingState = loopingStates.contains(new Integer(rowNum));
1334 
1335         // for each of the cells in the rows we're reconciling, do...
1336         for (int i = 0; i < oldValues.length; i++) {
1337 
1338             // if they contain the same value, we don't have to do anything
1339             if (oldValues[i] == newValues[i]) {
1340                 continue;
1341             }
1342 
1343             // if oldValues is a looping state and the state the current cell points to
1344             // is too, then we can just stomp over the current value of that cell (and
1345             // set the clear-looping-states flag if necessary)
1346             else if (isLoopingState && loopingStates.contains(new Integer(oldValues[i]))) {
1347                 if (newValues[i] != 0) {
1348                     if (oldValues[i] == 0) {
1349                         clearLoopingStates = true;
1350                     }
1351                     oldValues[i] = newValues[i];
1352                 }
1353             }
1354 
1355             // if the current cell in oldValues is 0, copy in the corresponding value
1356             // from newValues
1357             else if (oldValues[i] == 0) {
1358                 oldValues[i] = newValues[i];
1359             }
1360 
1361             // the last column of each row is the flag column.  Take care to merge the
1362             // flag words correctly
1363             else if (i == numCategories) {
1364                 oldValues[i] = (short)((newValues[i] & ALL_FLAGS) | oldValues[i]);
1365             }
1366 
1367             // if both newValues and oldValues have a nonzero value in the current
1368             // cell, and it isn't the same value both places...
1369             else if (oldValues[i] != 0 && newValues[i] != 0) {
1370 
1371                 // look up this pair of cell values in the merge list.  If it's
1372                 // found, update the cell in oldValues to point to the merged state
1373                 int combinedRowNum = searchMergeList(oldValues[i], newValues[i]);
1374                 if (combinedRowNum != 0) {
1375                     oldValues[i] = (short)combinedRowNum;
1376                 }
1377 
1378                 // otherwise, we have to reconcile them...
1379                 else {
1380                     // copy our row numbers into variables to make things easier
1381                     int oldRowNum = oldValues[i];
1382                     int newRowNum = newValues[i];
1383                     combinedRowNum = tempStateTable.size();
1384 
1385                     // add this pair of row numbers to the merge list (create it first
1386                     // if we haven't created the merge list yet)
1387                     if (mergeList == null) {
1388                         mergeList = new Vector<>();
1389                     }
1390                     mergeList.addElement(new int[] { oldRowNum, newRowNum, combinedRowNum });
1391 
1392                     // create a new row to represent the merged state, and copy the
1393                     // contents of oldRow into it, then add it to the end of the
1394                     // state table and update the original row (oldValues) to point
1395                     // to the new, merged, state
1396                     short[] newRow = new short[numCategories + 1];
1397                     short[] oldRow = tempStateTable.elementAt(oldRowNum);
1398                     System.arraycopy(oldRow, 0, newRow, 0, numCategories + 1);
1399                     tempStateTable.addElement(newRow);
1400                     oldValues[i] = (short)combinedRowNum;
1401 
1402                     // if the decision point list contains either of the parent rows,
1403                     // update it to include the new row as well
1404                     if ((decisionPointList.contains(new Integer(oldRowNum))
1405                             || decisionPointList.contains(new Integer(newRowNum)))
1406                         && !decisionPointList.contains(new Integer(combinedRowNum))
1407                     ) {
1408                         decisionPointList.addElement(new Integer(combinedRowNum));
1409                     }
1410 
1411                     // do the same thing with the list of rows being updated
1412                     if ((rowsBeingUpdated.contains(new Integer(oldRowNum))
1413                             || rowsBeingUpdated.contains(new Integer(newRowNum)))
1414                         && !rowsBeingUpdated.contains(new Integer(combinedRowNum))
1415                     ) {
1416                         decisionPointList.addElement(new Integer(combinedRowNum));
1417                     }
1418                     // now (groan) do the same thing for all the entries on the
1419                     // decision point stack
1420                     for (int k = 0; k < decisionPointStack.size(); k++) {
1421                         Vector<Integer> dpl = decisionPointStack.elementAt(k);
1422                         if ((dpl.contains(new Integer(oldRowNum))
1423                                 || dpl.contains(new Integer(newRowNum)))
1424                             && !dpl.contains(new Integer(combinedRowNum))
1425                         ) {
1426                             dpl.addElement(new Integer(combinedRowNum));
1427                         }
1428                     }
1429 
1430                     // FINALLY (puff puff puff), call mergeStates() recursively to copy
1431                     // the row referred to by newValues into the new row and resolve any
1432                     // conflicts that come up at that level
1433                     mergeStates(combinedRowNum, tempStateTable.elementAt(
1434                                     newValues[i]), rowsBeingUpdated);
1435                 }
1436             }
1437         }
1438         return;
1439     }
1440 
1441     /**
1442      * The merge list is a list of pairs of rows that have been merged somewhere in
1443      * the process of building this state table, along with the row number of the
1444      * row containing the merged state.  This function looks up a pair of row numbers
1445      * and returns the row number of the row they combine into.  (It returns 0 if
1446      * this pair of rows isn't in the merge list.)
1447      */
1448     private int searchMergeList(int a, int b) {
1449         // if there is no merge list, there obviously isn't anything in it
1450         if (mergeList == null) {
1451             return 0;
1452         }
1453 
1454         // otherwise, for each element in the merge list...
1455         else {
1456             int[] entry;
1457             for (int i = 0; i < mergeList.size(); i++) {
1458                 entry = mergeList.elementAt(i);
1459 
1460                 // we have a hit if the two row numbers match the two row numbers
1461                 // in the beginning of the entry (the two that combine), in either
1462                 // order
1463                 if ((entry[0] == a && entry[1] == b) || (entry[0] == b && entry[1] == a)) {
1464                     return entry[2];
1465                 }
1466 
1467                 // we also have a hit if one of the two row numbers matches the marged
1468                 // row number and the other one matches one of the original row numbers
1469                 if ((entry[2] == a && (entry[0] == b || entry[1] == b))) {
1470                     return entry[2];
1471                 }
1472                 if ((entry[2] == b && (entry[0] == a || entry[1] == a))) {
1473                     return entry[2];
1474                 }
1475             }
1476             return 0;
1477         }
1478     }
1479 
1480     /**
1481      * This function is used to update the list of current loooping states (i.e.,
1482      * states that are controlled by a *? construct).  It backfills values from
1483      * the looping states into unpopulated cells of the states that are currently
1484      * marked for backfilling, and then updates the list of looping states to be
1485      * the new list
1486      * @param newLoopingStates The list of new looping states
1487      * @param endStates The list of states to treat as end states (states that
1488      * can exit the loop).
1489      */
1490     private void setLoopingStates(Vector<Integer> newLoopingStates,
1491                                   Vector<Integer> endStates) {
1492 
1493         // if the current list of looping states isn't empty, we have to backfill
1494         // values from the looping states into the states that are waiting to be
1495         // backfilled
1496         if (!loopingStates.isEmpty()) {
1497             int loopingState = loopingStates.lastElement().intValue();
1498             int rowNum;
1499 
1500             // don't backfill into an end state OR any state reachable from an end state
1501             // (since the search for reachable states is recursive, it's split out into
1502             // a separate function, eliminateBackfillStates(), below)
1503             for (int i = 0; i < endStates.size(); i++) {
1504                 eliminateBackfillStates(endStates.elementAt(i).intValue());
1505             }
1506 
1507             // we DON'T actually backfill the states that need to be backfilled here.
1508             // Instead, we MARK them for backfilling.  The reason for this is that if
1509             // there are multiple rules in the state-table description, the looping
1510             // states may have some of their values changed by a succeeding rule, and
1511             // this wouldn't be reflected in the backfilled states.  We mark a state
1512             // for backfilling by putting the row number of the state to copy from
1513             // into the flag cell at the end of the row
1514             for (int i = 0; i < statesToBackfill.size(); i++) {
1515                 rowNum = statesToBackfill.elementAt(i).intValue();
1516                 short[] state = tempStateTable.elementAt(rowNum);
1517                 state[numCategories] =
1518                     (short)((state[numCategories] & ALL_FLAGS) | loopingState);
1519             }
1520             statesToBackfill.removeAllElements();
1521             loopingStates.removeAllElements();
1522         }
1523 
1524         if (newLoopingStates != null) {
1525             @SuppressWarnings("unchecked")
1526             Vector<Integer> clone = (Vector<Integer>)newLoopingStates.clone();
1527             loopingStates = clone;
1528         }
1529     }
1530 
1531     /**
1532      * This removes "ending states" and states reachable from them from the
1533      * list of states to backfill.
1534      * @param The row number of the state to remove from the backfill list
1535      */
1536     private void eliminateBackfillStates(int baseState) {
1537 
1538         // don't do anything unless this state is actually in the backfill list...
1539         if (statesToBackfill.contains(new Integer(baseState))) {
1540 
1541             // if it is, take it out
1542             statesToBackfill.removeElement(new Integer(baseState));
1543 
1544             // then go through and recursively call this function for every
1545             // state that the base state points to
1546             short[] state = tempStateTable.elementAt(baseState);
1547             for (int i = 0; i < numCategories; i++) {
1548                 if (state[i] != 0) {
1549                     eliminateBackfillStates(state[i]);
1550                 }
1551             }
1552         }
1553     }
1554 
1555     /**
1556      * This function completes the backfilling process by actually doing the
1557      * backfilling on the states that are marked for it
1558      */
1559     private void backfillLoopingStates() {
1560         short[] state;
1561         short[] loopingState = null;
1562         int loopingStateRowNum = 0;
1563         int fromState;
1564 
1565         // for each state in the state table...
1566         for (int i = 0; i < tempStateTable.size(); i++) {
1567             state = tempStateTable.elementAt(i);
1568 
1569             // check the state's flag word to see if it's marked for backfilling
1570             // (it's marked for backfilling if any bits other than the two high-order
1571             // bits are set-- if they are, then the flag word, minus the two high bits,
1572             // is the row number to copy from)
1573             fromState = state[numCategories] & ~ALL_FLAGS;
1574             if (fromState > 0) {
1575 
1576                 // load up the state to copy from (if we haven't already)
1577                 if (fromState != loopingStateRowNum) {
1578                     loopingStateRowNum = fromState;
1579                     loopingState = tempStateTable.elementAt(loopingStateRowNum);
1580                 }
1581 
1582                 // clear out the backfill part of the flag word
1583                 state[numCategories] &= ALL_FLAGS;
1584 
1585                 // then fill all zero cells in the current state with values
1586                 // from the corresponding cells of the fromState
1587                 for (int j = 0; j < state.length; j++) {
1588                     if (state[j] == 0) {
1589                         state[j] = loopingState[j];
1590                     }
1591                     else if (state[j] == DONT_LOOP_FLAG) {
1592                         state[j] = 0;
1593                     }
1594                 }
1595             }
1596         }
1597     }
1598 
1599     /**
1600      * This function completes the state-table-building process by doing several
1601      * postprocessing steps and copying everything into its final resting place
1602      * in the iterator itself
1603      * @param forward True if we're working on the forward state table
1604      */
1605     private void finishBuildingStateTable(boolean forward) {
1606         // start by backfilling the looping states
1607         backfillLoopingStates();
1608 
1609         int[] rowNumMap = new int[tempStateTable.size()];
1610         Stack<Integer> rowsToFollow = new Stack<>();
1611         rowsToFollow.push(new Integer(1));
1612         rowNumMap[1] = 1;
1613 
1614         // determine which states are no longer reachable from the start state
1615         // (the reachable states will have their row numbers in the row number
1616         // map, and the nonreachable states will have zero in the row number map)
1617         while (rowsToFollow.size() != 0) {
1618             int rowNum = rowsToFollow.pop().intValue();
1619             short[] row = tempStateTable.elementAt(rowNum);
1620 
1621             for (int i = 0; i < numCategories; i++) {
1622                 if (row[i] != 0) {
1623                     if (rowNumMap[row[i]] == 0) {
1624                         rowNumMap[row[i]] = row[i];
1625                         rowsToFollow.push(new Integer(row[i]));
1626                     }
1627                 }
1628             }
1629         }
1630 
1631         boolean madeChange;
1632         int newRowNum;
1633 
1634         // algorithm for minimizing the number of states in the table adapted from
1635         // Aho & Ullman, "Principles of Compiler Design"
1636         // The basic idea here is to organize the states into classes.  When we're done,
1637         // all states in the same class can be considered identical and all but one eliminated.
1638 
1639         // initially assign states to classes based on the number of populated cells they
1640         // contain (the class number is the number of populated cells)
1641         int[] stateClasses = new int[tempStateTable.size()];
1642         int nextClass = numCategories + 1;
1643         short[] state1, state2;
1644         for (int i = 1; i < stateClasses.length; i++) {
1645             if (rowNumMap[i] == 0) {
1646                 continue;
1647             }
1648             state1 = tempStateTable.elementAt(i);
1649             for (int j = 0; j < numCategories; j++) {
1650                 if (state1[j] != 0) {
1651                     ++stateClasses[i];
1652                 }
1653             }
1654             if (stateClasses[i] == 0) {
1655                 stateClasses[i] = nextClass;
1656             }
1657         }
1658         ++nextClass;
1659 
1660         // then, for each class, elect the first member of that class as that class's
1661         // "representative".  For each member of the class, compare it to the "representative."
1662         // If there's a column position where the state being tested transitions to a
1663         // state in a DIFFERENT class from the class where the "representative" transitions,
1664         // then move the state into a new class.  Repeat this process until no new classes
1665         // are created.
1666         int currentClass;
1667         int lastClass;
1668         boolean split;
1669 
1670         do {
1671             currentClass = 1;
1672             lastClass = nextClass;
1673             while (currentClass < nextClass) {
1674                 split = false;
1675                 state1 = state2 = null;
1676                 for (int i = 0; i < stateClasses.length; i++) {
1677                     if (stateClasses[i] == currentClass) {
1678                         if (state1 == null) {
1679                             state1 = tempStateTable.elementAt(i);
1680                         }
1681                         else {
1682                             state2 = tempStateTable.elementAt(i);
1683                             for (int j = 0; j < state2.length; j++) {
1684                                 if ((j == numCategories && state1[j] != state2[j] && forward)
1685                                         || (j != numCategories && stateClasses[state1[j]]
1686                                         != stateClasses[state2[j]])) {
1687                                     stateClasses[i] = nextClass;
1688                                     split = true;
1689                                     break;
1690                                 }
1691                             }
1692                         }
1693                     }
1694                 }
1695                 if (split) {
1696                     ++nextClass;
1697                 }
1698                 ++currentClass;
1699             }
1700         } while (lastClass != nextClass);
1701 
1702         // at this point, all of the states in a class except the first one (the
1703         //"representative") can be eliminated, so update the row-number map accordingly
1704         int[] representatives = new int[nextClass];
1705         for (int i = 1; i < stateClasses.length; i++)
1706             if (representatives[stateClasses[i]] == 0) {
1707                 representatives[stateClasses[i]] = i;
1708             }
1709             else {
1710                 rowNumMap[i] = representatives[stateClasses[i]];
1711             }
1712 
1713         // renumber all remaining rows...
1714         // first drop all that are either unreferenced or not a class representative
1715         for (int i = 1; i < rowNumMap.length; i++) {
1716             if (rowNumMap[i] != i) {
1717                 tempStateTable.setElementAt(null, i);
1718             }
1719         }
1720 
1721         // then calculate everybody's new row number and update the row
1722         // number map appropriately (the first pass updates the row numbers
1723         // of all the class representatives [the rows we're keeping], and the
1724         // second pass updates the cross references for all the rows that
1725         // are being deleted)
1726         newRowNum = 1;
1727         for (int i = 1; i < rowNumMap.length; i++) {
1728             if (tempStateTable.elementAt(i) != null) {
1729                 rowNumMap[i] = newRowNum++;
1730             }
1731         }
1732         for (int i = 1; i < rowNumMap.length; i++) {
1733             if (tempStateTable.elementAt(i) == null) {
1734                 rowNumMap[i] = rowNumMap[rowNumMap[i]];
1735             }
1736         }
1737 
1738         // allocate the permanent state table, and copy the remaining rows into it
1739         // (adjusting all the cell values, of course)
1740 
1741         // this section does that for the forward state table
1742         if (forward) {
1743             endStates = new boolean[newRowNum];
1744             lookaheadStates = new boolean[newRowNum];
1745             stateTable = new short[newRowNum * numCategories];
1746             int p = 0;
1747             int p2 = 0;
1748             for (int i = 0; i < tempStateTable.size(); i++) {
1749                 short[] row = tempStateTable.elementAt(i);
1750                 if (row == null) {
1751                     continue;
1752                 }
1753                 for (int j = 0; j < numCategories; j++) {
1754                     stateTable[p] = (short)(rowNumMap[row[j]]);
1755                     ++p;
1756                 }
1757                 endStates[p2] = ((row[numCategories] & END_STATE_FLAG) != 0);
1758                 lookaheadStates[p2] = ((row[numCategories] & LOOKAHEAD_STATE_FLAG) != 0);
1759                 ++p2;
1760             }
1761         }
1762 
1763         // and this section does it for the backward state table
1764         else {
1765             backwardsStateTable = new short[newRowNum * numCategories];
1766             int p = 0;
1767             for (int i = 0; i < tempStateTable.size(); i++) {
1768                 short[] row = tempStateTable.elementAt(i);
1769                 if (row == null) {
1770                     continue;
1771                 }
1772                 for (int j = 0; j < numCategories; j++) {
1773                     backwardsStateTable[p] = (short)(rowNumMap[row[j]]);
1774                     ++p;
1775                 }
1776             }
1777         }
1778     }
1779 
1780     /**
1781      * This function builds the backward state table from the forward state
1782      * table and any additional rules (identified by the ! on the front)
1783      * supplied in the description
1784      */
1785     private void buildBackwardsStateTable(Vector<String> tempRuleList) {
1786 
1787         // create the temporary state table and seed it with two rows (row 0
1788         // isn't used for anything, and we have to create row 1 (the initial
1789         // state) before we can do anything else
1790         tempStateTable = new Vector<>();
1791         tempStateTable.addElement(new short[numCategories + 1]);
1792         tempStateTable.addElement(new short[numCategories + 1]);
1793 
1794         // although the backwards state table is built automatically from the forward
1795         // state table, there are some situations (the default sentence-break rules,
1796         // for example) where this doesn't yield enough stop states, causing a dramatic
1797         // drop in performance.  To help with these cases, the user may supply
1798         // supplemental rules that are added to the backward state table.  These have
1799         // the same syntax as the normal break rules, but begin with '!' to distinguish
1800         // them from normal break rules
1801         for (int i = 0; i < tempRuleList.size(); i++) {
1802             String rule = tempRuleList.elementAt(i);
1803             if (rule.charAt(0) == '!') {
1804                 parseRule(rule.substring(1), false);
1805             }
1806         }
1807         backfillLoopingStates();
1808 
1809         // Backwards iteration is qualitatively different from forwards iteration.
1810         // This is because backwards iteration has to be made to operate from no context
1811         // at all-- the user should be able to ask BreakIterator for the break position
1812         // immediately on either side of some arbitrary offset in the text.  The
1813         // forward iteration table doesn't let us do that-- it assumes complete
1814         // information on the context, which means starting from the beginning of the
1815         // document.
1816         // The way we do backward and random-access iteration is to back up from the
1817         // current (or user-specified) position until we see something we're sure is
1818         // a break position (it may not be the last break position immediately
1819         // preceding our starting point, however).  Then we roll forward from there to
1820         // locate the actual break position we're after.
1821         // This means that the backwards state table doesn't have to identify every
1822         // break position, allowing the building algorithm to be much simpler.  Here,
1823         // we use a "pairs" approach, scanning the forward-iteration state table for
1824         // pairs of character categories we ALWAYS break between, and building a state
1825         // table from that information.  No context is required-- all this state table
1826         // looks at is a pair of adjacent characters.
1827 
1828         // It's possible that the user has supplied supplementary rules (see above).
1829         // This has to be done first to keep parseRule() and friends from becoming
1830         // EVEN MORE complicated.  The automatically-generated states are appended
1831         // onto the end of the state table, and then the two sets of rules are
1832         // stitched together at the end.  Take note of the row number of the
1833         // first row of the auromatically-generated part.
1834         int backTableOffset = tempStateTable.size();
1835         if (backTableOffset > 2) {
1836             ++backTableOffset;
1837         }
1838 
1839         // the automatically-generated part of the table models a two-dimensional
1840         // array where the two dimensions represent the two characters we're currently
1841         // looking at.  To model this as a state table, we actually need one additional
1842         // row to represent the initial state.  It gets populated with the row numbers
1843         // of the other rows (in order).
1844         for (int i = 0; i < numCategories + 1; i++)
1845             tempStateTable.addElement(new short[numCategories + 1]);
1846 
1847         short[] state = tempStateTable.elementAt(backTableOffset - 1);
1848         for (int i = 0; i < numCategories; i++)
1849             state[i] = (short)(i + backTableOffset);
1850 
1851         // scavenge the forward state table for pairs of character categories
1852         // that always have a break between them.  The algorithm is as follows:
1853         // Look down each column in the state table.  For each nonzero cell in
1854         // that column, look up the row it points to.  For each nonzero cell in
1855         // that row, populate a cell in the backwards state table: the row number
1856         // of that cell is the number of the column we were scanning (plus the
1857         // offset that locates this sub-table), and the column number of that cell
1858         // is the column number of the nonzero cell we just found.  This cell is
1859         // populated with its own column number (adjusted according to the actual
1860         // location of the sub-table).  This process will produce a state table
1861         // whose behavior is the same as looking up successive pairs of characters
1862         // in an array of Booleans to determine whether there is a break.
1863         int numRows = stateTable.length / numCategories;
1864         for (int column = 0; column < numCategories; column++) {
1865             for (int row = 0; row < numRows; row++) {
1866                 int nextRow = lookupState(row, column);
1867                 if (nextRow != 0) {
1868                     for (int nextColumn = 0; nextColumn < numCategories; nextColumn++) {
1869                         int cellValue = lookupState(nextRow, nextColumn);
1870                         if (cellValue != 0) {
1871                             state = tempStateTable.elementAt(nextColumn +
1872                                             backTableOffset);
1873                             state[column] = (short)(column + backTableOffset);
1874                         }
1875                     }
1876                 }
1877             }
1878         }
1879 
1880         // if the user specified some backward-iteration rules with the ! token,
1881         // we have to merge the resulting state table with the auto-generated one
1882         // above.  First copy the populated cells from row 1 over the populated
1883         // cells in the auto-generated table.  Then copy values from row 1 of the
1884         // auto-generated table into all of the the unpopulated cells of the
1885         // rule-based table.
1886         if (backTableOffset > 1) {
1887 
1888             // for every row in the auto-generated sub-table, if a cell is
1889             // populated that is also populated in row 1 of the rule-based
1890             // sub-table, copy the value from row 1 over the value in the
1891             // auto-generated sub-table
1892             state = tempStateTable.elementAt(1);
1893             for (int i = backTableOffset - 1; i < tempStateTable.size(); i++) {
1894                 short[] state2 = tempStateTable.elementAt(i);
1895                 for (int j = 0; j < numCategories; j++) {
1896                     if (state[j] != 0 && state2[j] != 0) {
1897                         state2[j] = state[j];
1898                     }
1899                 }
1900             }
1901 
1902             // now, for every row in the rule-based sub-table that is not
1903             // an end state, fill in all unpopulated cells with the values
1904             // of the corresponding cells in the first row of the auto-
1905             // generated sub-table.
1906             state = tempStateTable.elementAt(backTableOffset - 1);
1907             for (int i = 1; i < backTableOffset - 1; i++) {
1908                 short[] state2 = tempStateTable.elementAt(i);
1909                 if ((state2[numCategories] & END_STATE_FLAG) == 0) {
1910                     for (int j = 0; j < numCategories; j++) {
1911                         if (state2[j] == 0) {
1912                             state2[j] = state[j];
1913                         }
1914                     }
1915                 }
1916             }
1917         }
1918 
1919         // finally, clean everything up and copy it into the actual BreakIterator
1920         // by calling finishBuildingStateTable()
1921         finishBuildingStateTable(false);
1922     }
1923 
1924     /**
1925      * Given a current state and a character category, looks up the
1926      * next state to transition to in the state table.
1927      */
1928     protected int lookupState(int state, int category) {
1929         return stateTable[state * numCategories + category];
1930     }
1931 
1932     /**
1933      * Throws an IllegalArgumentException representing a syntax error in the rule
1934      * description.  The exception's message contains some debugging information.
1935      * @param message A message describing the problem
1936      * @param position The position in the description where the problem was
1937      * discovered
1938      * @param context The string containing the error
1939      */
1940     protected void error(String message, int position, String context) {
1941         throw new IllegalArgumentException("Parse error at position (" + position + "): " + message + "\n" +
1942                 context.substring(0, position) + " -here- " + context.substring(position));
1943     }
1944 
1945     void makeFile(String filename) {
1946         writeTables(filename);
1947     }
1948 
1949     /**
1950      * Magic number for the BreakIterator data file format.
1951      */
1952     private static final byte[] LABEL = {
1953         (byte)'B', (byte)'I', (byte)'d', (byte)'a', (byte)'t', (byte)'a',
1954         (byte)'\0'
1955     };
1956 
1957     /**
1958      * Version number of the dictionary that was read in.
1959      */
1960     private static final byte[] supportedVersion = { (byte)1 };
1961 
1962     /**
1963      * Header size in byte count
1964      */
1965      private static final int HEADER_LENGTH = 36;
1966 
1967     /**
1968      * Array length of indices for BMP characters
1969      */
1970      private static final int BMP_INDICES_LENGTH = 512;
1971 
1972     /**
1973      * Read datafile. The datafile's format is as follows:
1974      * <pre>
1975      *   BreakIteratorData {
1976      *       u1           magic[7];
1977      *       u1           version;
1978      *       u4           totalDataSize;
1979      *       header_info  header;
1980      *       body         value;
1981      *   }
1982      * </pre>
1983      * <code>totalDataSize</code> is the summation of the size of
1984      * <code>header_info</code> and <code>body</code> in byte count.
1985      * <p>
1986      * In <code>header</code>, each field except for checksum implies the
1987      * length of each field. Since <code>BMPdataLength</code> is a fixed-length
1988      *  data(512 entries), its length isn't included in <code>header</code>.
1989      * <code>checksum</code> is a CRC32 value of all in <code>body</code>.
1990      * <pre>
1991      *   header_info {
1992      *       u4           stateTableLength;
1993      *       u4           backwardsStateTableLength;
1994      *       u4           endStatesLength;
1995      *       u4           lookaheadStatesLength;
1996      *       u4           BMPdataLength;
1997      *       u4           nonBMPdataLength;
1998      *       u4           additionalDataLength;
1999      *       u8           checksum;
2000      *   }
2001      * </pre>
2002      * <p>
2003      *
2004      * Finally, <code>BMPindices</code> and <code>BMPdata</code> are set to
2005      * <code>charCategoryTable</code>. <code>nonBMPdata</code> is set to
2006      * <code>supplementaryCharCategoryTable</code>.
2007      * <pre>
2008      *   body {
2009      *       u2           stateTable[stateTableLength];
2010      *       u2           backwardsStateTable[backwardsStateTableLength];
2011      *       u1           endStates[endStatesLength];
2012      *       u1           lookaheadStates[lookaheadStatesLength];
2013      *       u2           BMPindices[512];
2014      *       u1           BMPdata[BMPdataLength];
2015      *       u4           nonBMPdata[numNonBMPdataLength];
2016      *       u1           additionalData[additionalDataLength];
2017      *   }
2018      * </pre>
2019      */
2020     protected void writeTables(String datafile) {
2021         final String filename;
2022         final String outputDir;
2023         String tmpbuf = GenerateBreakIteratorData.getOutputDirectory();
2024 
2025         if (tmpbuf.equals("")) {
2026             filename = datafile;
2027             outputDir = "";
2028         } else {
2029             char sep = File.separatorChar;
2030             if (sep == '/') {
2031                 outputDir = tmpbuf;
2032             } else if (sep == '\\') {
2033                 outputDir = tmpbuf.replaceAll("/", "\\\\");
2034             } else {
2035                 outputDir = tmpbuf.replaceAll("/", String.valueOf(sep));
2036             }
2037 
2038             filename = outputDir + sep + datafile;
2039         }
2040 
2041         try {
2042             if (!outputDir.equals("")) {
2043                 new File(outputDir).mkdirs();
2044             }
2045             BufferedOutputStream out = new BufferedOutputStream(new FileOutputStream(filename));
2046 
2047             byte[] BMPdata = charCategoryTable.getStringArray();
2048             short[] BMPindices = charCategoryTable.getIndexArray();
2049             int[] nonBMPdata = supplementaryCharCategoryTable.getArray();
2050 
2051             if (BMPdata.length <= 0) {
2052                 throw new InternalError("Wrong BMP data length(" + BMPdata.length + ")");
2053             }
2054             if (BMPindices.length != BMP_INDICES_LENGTH) {
2055                 throw new InternalError("Wrong BMP indices length(" + BMPindices.length + ")");
2056             }
2057             if (nonBMPdata.length <= 0) {
2058                 throw new InternalError("Wrong non-BMP data length(" + nonBMPdata.length + ")");
2059             }
2060 
2061             int len;
2062 
2063             /* Compute checksum */
2064             CRC32 crc32 = new CRC32();
2065             len = stateTable.length;
2066             for (int i = 0; i < len; i++) {
2067                 crc32.update(stateTable[i]);
2068             }
2069             len = backwardsStateTable.length;
2070             for (int i = 0; i < len; i++) {
2071                 crc32.update(backwardsStateTable[i]);
2072             }
2073             crc32.update(toByteArray(endStates));
2074             crc32.update(toByteArray(lookaheadStates));
2075             for (int i = 0; i < BMP_INDICES_LENGTH; i++) {
2076                 crc32.update(BMPindices[i]);
2077             }
2078             crc32.update(BMPdata);
2079             len = nonBMPdata.length;
2080             for (int i = 0; i < len; i++) {
2081                 crc32.update(nonBMPdata[i]);
2082             }
2083             if (additionalData != null) {
2084                 len = additionalData.length;
2085                 for (int i = 0; i < len; i++) {
2086                     crc32.update(additionalData[i]);
2087                 }
2088             }
2089 
2090             /* First, write magic, version, and totalDataSize. */
2091             len = HEADER_LENGTH +
2092                   (stateTable.length + backwardsStateTable.length) * 2 +
2093                   endStates.length + lookaheadStates.length + 1024 +
2094                   BMPdata.length + nonBMPdata.length * 4 +
2095                   ((additionalData == null) ? 0 : additionalData.length);
2096             out.write(LABEL);
2097             out.write(supportedVersion);
2098             out.write(toByteArray(len));
2099 
2100             /* Write header_info. */
2101             out.write(toByteArray(stateTable.length));
2102             out.write(toByteArray(backwardsStateTable.length));
2103             out.write(toByteArray(endStates.length));
2104             out.write(toByteArray(lookaheadStates.length));
2105             out.write(toByteArray(BMPdata.length));
2106             out.write(toByteArray(nonBMPdata.length));
2107             if (additionalData == null) {
2108                 out.write(toByteArray(0));
2109             } else {
2110                 out.write(toByteArray(additionalData.length));
2111             }
2112             out.write(toByteArray(crc32.getValue()));
2113 
2114             /* Write stateTable[numCategories * numRows] */
2115             len = stateTable.length;
2116             for (int i = 0; i < len; i++) {
2117                 out.write(toByteArray(stateTable[i]));
2118             }
2119 
2120             /* Write backwardsStateTable[numCategories * numRows] */
2121             len = backwardsStateTable.length;
2122             for (int i = 0; i < len; i++) {
2123                 out.write(toByteArray(backwardsStateTable[i]));
2124             }
2125 
2126             /* Write endStates[numRows] */
2127             out.write(toByteArray(endStates));
2128 
2129             /* Write lookaheadStates[numRows] */
2130             out.write(toByteArray(lookaheadStates));
2131 
2132             for (int i = 0; i < BMP_INDICES_LENGTH; i++) {
2133                 out.write(toByteArray(BMPindices[i]));
2134             }
2135             BMPindices = null;
2136             out.write(BMPdata);
2137             BMPdata = null;
2138 
2139             /* Write a category table for non-BMP characters. */
2140             len = nonBMPdata.length;
2141             for (int i = 0; i < len; i++) {
2142                 out.write(toByteArray(nonBMPdata[i]));
2143             }
2144             nonBMPdata = null;
2145 
2146             /* Write additional data */
2147             if (additionalData != null) {
2148                 out.write(additionalData);
2149             }
2150 
2151             out.close();
2152         }
2153         catch (Exception e) {
2154             throw new InternalError(e.toString());
2155         }
2156     }
2157 
2158     byte[] toByteArray(short val) {
2159         byte[] buf = new byte[2];
2160         buf[0] = (byte)((val>>>8) & 0xFF);
2161         buf[1] = (byte)(val & 0xFF);
2162         return buf;
2163     }
2164 
2165     byte[] toByteArray(int val) {
2166         byte[] buf = new byte[4];
2167         buf[0] = (byte)((val>>>24) & 0xFF);
2168         buf[1] = (byte)((val>>>16) & 0xFF);
2169         buf[2] = (byte)((val>>>8) & 0xFF);
2170         buf[3] = (byte)(val & 0xFF);
2171         return buf;
2172     }
2173 
2174     byte[] toByteArray(long val) {
2175         byte[] buf = new byte[8];
2176         buf[0] = (byte)((val>>>56) & 0xff);
2177         buf[1] = (byte)((val>>>48) & 0xff);
2178         buf[2] = (byte)((val>>>40) & 0xff);
2179         buf[3] = (byte)((val>>>32) & 0xff);
2180         buf[4] = (byte)((val>>>24) & 0xff);
2181         buf[5] = (byte)((val>>>16) & 0xff);
2182         buf[6] = (byte)((val>>>8) & 0xff);
2183         buf[7] = (byte)(val & 0xff);
2184         return buf;
2185     }
2186 
2187     byte[] toByteArray(boolean[] data) {
2188         byte[] buf = new byte[data.length];
2189         for (int i = 0; i < data.length; i++) {
2190             buf[i] = data[i] ? (byte)1 : (byte)0;
2191         }
2192         return buf;
2193     }
2194 
2195     void setAdditionalData(byte[] data) {
2196         additionalData = data;
2197     }
2198 }