1 /*
   2  * Copyright (c) 1999, 2005, 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 /*
  27  * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
  28  * (C) Copyright IBM Corp. 1996-1998 - All Rights Reserved
  29  *
  30  *   The original version of this source code and documentation is copyrighted
  31  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  32  * materials are provided under terms of a License Agreement between Taligent
  33  * and Sun. This technology is protected by multiple US and International
  34  * patents. This notice and attribution to Taligent may not be removed.
  35  *   Taligent is a registered trademark of Taligent, Inc.
  36  *
  37  */
  38 
  39 package java.text;
  40 
  41 import java.util.Vector;
  42 import sun.text.UCompactIntArray;
  43 import sun.text.IntHashtable;
  44 import sun.text.ComposedCharIter;
  45 import sun.text.CollatorUtilities;
  46 import sun.text.normalizer.NormalizerImpl;
  47 
  48 /**
  49  * This class contains all the code to parse a RuleBasedCollator pattern
  50  * and build a RBCollationTables object from it.  A particular instance
  51  * of tis class exists only during the actual build process-- once an
  52  * RBCollationTables object has been built, the RBTableBuilder object
  53  * goes away.  This object carries all of the state which is only needed
  54  * during the build process, plus a "shadow" copy of all of the state
  55  * that will go into the tables object itself.  This object communicates
  56  * with RBCollationTables through a separate class, RBCollationTables.BuildAPI,
  57  * this is an inner class of RBCollationTables and provides a separate
  58  * private API for communication with RBTableBuilder.
  59  * This class isn't just an inner class of RBCollationTables itself because
  60  * of its large size.  For source-code readability, it seemed better for the
  61  * builder to have its own source file.
  62  */
  63 final class RBTableBuilder {
  64 
  65     public RBTableBuilder(RBCollationTables.BuildAPI tables) {
  66         this.tables = tables;
  67     }
  68 
  69     /**
  70      * Create a table-based collation object with the given rules.
  71      * This is the main function that actually builds the tables and
  72      * stores them back in the RBCollationTables object.  It is called
  73      * ONLY by the RBCollationTables constructor.
  74      * @see RuleBasedCollator#RuleBasedCollator
  75      * @exception ParseException If the rules format is incorrect.
  76      */
  77 
  78     public void build(String pattern, int decmp) throws ParseException
  79     {
  80         boolean isSource = true;
  81         int i = 0;
  82         String expChars;
  83         String groupChars;
  84         if (pattern.length() == 0)
  85             throw new ParseException("Build rules empty.", 0);
  86 
  87         // This array maps Unicode characters to their collation ordering
  88         mapping = new UCompactIntArray(RBCollationTables.UNMAPPED);
  89         // Normalize the build rules.  Find occurances of all decomposed characters
  90         // and normalize the rules before feeding into the builder.  By "normalize",
  91         // we mean that all precomposed Unicode characters must be converted into
  92         // a base character and one or more combining characters (such as accents).
  93         // When there are multiple combining characters attached to a base character,
  94         // the combining characters must be in their canonical order
  95         //
  96         // sherman/Note:
  97         //(1)decmp will be NO_DECOMPOSITION only in ko locale to prevent decompose
  98         //hangual syllables to jamos, so we can actually just call decompose with
  99         //normalizer's IGNORE_HANGUL option turned on
 100         //
 101         //(2)just call the "special version" in NormalizerImpl directly
 102         //pattern = Normalizer.decompose(pattern, false, Normalizer.IGNORE_HANGUL, true);
 103         //
 104         //Normalizer.Mode mode = CollatorUtilities.toNormalizerMode(decmp);
 105         //pattern = Normalizer.normalize(pattern, mode, 0, true);
 106 
 107         pattern = NormalizerImpl.canonicalDecomposeWithSingleQuotation(pattern);
 108 
 109         // Build the merged collation entries
 110         // Since rules can be specified in any order in the string
 111         // (e.g. "c , C < d , D < e , E .... C < CH")
 112         // this splits all of the rules in the string out into separate
 113         // objects and then sorts them.  In the above example, it merges the
 114         // "C < CH" rule in just before the "C < D" rule.
 115         //
 116 
 117         mPattern = new MergeCollation(pattern);
 118 
 119         int order = 0;
 120 
 121         // Now walk though each entry and add it to my own tables
 122         for (i = 0; i < mPattern.getCount(); ++i)
 123         {
 124             PatternEntry entry = mPattern.getItemAt(i);
 125             if (entry != null) {
 126                 groupChars = entry.getChars();
 127                 if (groupChars.length() > 1) {
 128                     switch(groupChars.charAt(groupChars.length()-1)) {
 129                     case '@':
 130                         frenchSec = true;
 131                         groupChars = groupChars.substring(0, groupChars.length()-1);
 132                         break;
 133                     case '!':
 134                         seAsianSwapping = true;
 135                         groupChars = groupChars.substring(0, groupChars.length()-1);
 136                         break;
 137                     }
 138                 }
 139 
 140                 order = increment(entry.getStrength(), order);
 141                 expChars = entry.getExtension();
 142 
 143                 if (expChars.length() != 0) {
 144                     addExpandOrder(groupChars, expChars, order);
 145                 } else if (groupChars.length() > 1) {
 146                     char ch = groupChars.charAt(0);
 147                     if (Character.isHighSurrogate(ch) && groupChars.length() == 2) {
 148                         addOrder(Character.toCodePoint(ch, groupChars.charAt(1)), order);
 149                     } else {
 150                         addContractOrder(groupChars, order);
 151                     }
 152                 } else {
 153                     char ch = groupChars.charAt(0);
 154                     addOrder(ch, order);
 155                 }
 156             }
 157         }
 158         addComposedChars();
 159 
 160         commit();
 161         mapping.compact();
 162         /*
 163         System.out.println("mappingSize=" + mapping.getKSize());
 164         for (int j = 0; j < 0xffff; j++) {
 165             int value = mapping.elementAt(j);
 166             if (value != RBCollationTables.UNMAPPED)
 167                 System.out.println("index=" + Integer.toString(j, 16)
 168                            + ", value=" + Integer.toString(value, 16));
 169         }
 170         */
 171         tables.fillInTables(frenchSec, seAsianSwapping, mapping, contractTable, expandTable,
 172                     contractFlags, maxSecOrder, maxTerOrder);
 173     }
 174 
 175     /** Add expanding entries for pre-composed unicode characters so that this
 176      * collator can be used reasonably well with decomposition turned off.
 177      */
 178     private void addComposedChars() throws ParseException {
 179         // Iterate through all of the pre-composed characters in Unicode
 180         ComposedCharIter iter = new ComposedCharIter();
 181         int c;
 182         while ((c = iter.next()) != ComposedCharIter.DONE) {
 183             if (getCharOrder(c) == RBCollationTables.UNMAPPED) {
 184                 //
 185                 // We don't already have an ordering for this pre-composed character.
 186                 //
 187                 // First, see if the decomposed string is already in our
 188                 // tables as a single contracting-string ordering.
 189                 // If so, just map the precomposed character to that order.
 190                 //
 191                 // TODO: What we should really be doing here is trying to find the
 192                 // longest initial substring of the decomposition that is present
 193                 // in the tables as a contracting character sequence, and find its
 194                 // ordering.  Then do this recursively with the remaining chars
 195                 // so that we build a list of orderings, and add that list to
 196                 // the expansion table.
 197                 // That would be more correct but also significantly slower, so
 198                 // I'm not totally sure it's worth doing.
 199                 //
 200                 String s = iter.decomposition();
 201 
 202                 //sherman/Note: if this is 1 character decomposed string, the
 203                 //only thing need to do is to check if this decomposed character
 204                 //has an entry in our order table, this order is not necessary
 205                 //to be a contraction order, if it does have one, add an entry
 206                 //for the precomposed character by using the same order, the
 207                 //previous impl unnecessarily adds a single character expansion
 208                 //entry.
 209                 if (s.length() == 1) {
 210                     int order = getCharOrder(s.charAt(0));
 211                     if (order != RBCollationTables.UNMAPPED) {
 212                         addOrder(c, order);
 213                     }
 214                     continue;
 215                 } else if (s.length() == 2) {
 216                     char ch0 = s.charAt(0);
 217                     if (Character.isHighSurrogate(ch0)) {
 218                         int order = getCharOrder(s.codePointAt(0));
 219                         if (order != RBCollationTables.UNMAPPED) {
 220                             addOrder(c, order);
 221                         }
 222                         continue;
 223                     }
 224                 }
 225                 int contractOrder = getContractOrder(s);
 226                 if (contractOrder != RBCollationTables.UNMAPPED) {
 227                     addOrder(c, contractOrder);
 228                 } else {
 229                     //
 230                     // We don't have a contracting ordering for the entire string
 231                     // that results from the decomposition, but if we have orders
 232                     // for each individual character, we can add an expanding
 233                     // table entry for the pre-composed character
 234                     //
 235                     boolean allThere = true;
 236                     for (int i = 0; i < s.length(); i++) {
 237                         if (getCharOrder(s.charAt(i)) == RBCollationTables.UNMAPPED) {
 238                             allThere = false;
 239                             break;
 240                         }
 241                     }
 242                     if (allThere) {
 243                         addExpandOrder(c, s, RBCollationTables.UNMAPPED);
 244                     }
 245                 }
 246             }
 247         }
 248     }
 249 
 250     /**
 251      * Look up for unmapped values in the expanded character table.
 252      *
 253      * When the expanding character tables are built by addExpandOrder,
 254      * it doesn't know what the final ordering of each character
 255      * in the expansion will be.  Instead, it just puts the raw character
 256      * code into the table, adding CHARINDEX as a flag.  Now that we've
 257      * finished building the mapping table, we can go back and look up
 258      * that character to see what its real collation order is and
 259      * stick that into the expansion table.  That lets us avoid doing
 260      * a two-stage lookup later.
 261      */
 262     private final void commit()
 263     {
 264         if (expandTable != null) {
 265             for (int i = 0; i < expandTable.size(); i++) {
 266                 int[] valueList = expandTable.elementAt(i);
 267                 for (int j = 0; j < valueList.length; j++) {
 268                     int order = valueList[j];
 269                     if (order < RBCollationTables.EXPANDCHARINDEX && order > CHARINDEX) {
 270                         // found a expanding character that isn't filled in yet
 271                         int ch = order - CHARINDEX;
 272 
 273                         // Get the real values for the non-filled entry
 274                         int realValue = getCharOrder(ch);
 275 
 276                         if (realValue == RBCollationTables.UNMAPPED) {
 277                             // The real value is still unmapped, maybe it's ignorable
 278                             valueList[j] = IGNORABLEMASK & ch;
 279                         } else {
 280                             // just fill in the value
 281                             valueList[j] = realValue;
 282                         }
 283                     }
 284                 }
 285             }
 286         }
 287     }
 288     /**
 289      *  Increment of the last order based on the comparison level.
 290      */
 291     private final int increment(int aStrength, int lastValue)
 292     {
 293         switch(aStrength)
 294         {
 295         case Collator.PRIMARY:
 296             // increment priamry order  and mask off secondary and tertiary difference
 297             lastValue += PRIMARYORDERINCREMENT;
 298             lastValue &= RBCollationTables.PRIMARYORDERMASK;
 299             isOverIgnore = true;
 300             break;
 301         case Collator.SECONDARY:
 302             // increment secondary order and mask off tertiary difference
 303             lastValue += SECONDARYORDERINCREMENT;
 304             lastValue &= RBCollationTables.SECONDARYDIFFERENCEONLY;
 305             // record max # of ignorable chars with secondary difference
 306             if (!isOverIgnore)
 307                 maxSecOrder++;
 308             break;
 309         case Collator.TERTIARY:
 310             // increment tertiary order
 311             lastValue += TERTIARYORDERINCREMENT;
 312             // record max # of ignorable chars with tertiary difference
 313             if (!isOverIgnore)
 314                 maxTerOrder++;
 315             break;
 316         }
 317         return lastValue;
 318     }
 319 
 320     /**
 321      *  Adds a character and its designated order into the collation table.
 322      */
 323     private final void addOrder(int ch, int anOrder)
 324     {
 325         // See if the char already has an order in the mapping table
 326         int order = mapping.elementAt(ch);
 327 
 328         if (order >= RBCollationTables.CONTRACTCHARINDEX) {
 329             // There's already an entry for this character that points to a contracting
 330             // character table.  Instead of adding the character directly to the mapping
 331             // table, we must add it to the contract table instead.
 332             int length = 1;
 333             if (Character.isSupplementaryCodePoint(ch)) {
 334                 length = Character.toChars(ch, keyBuf, 0);
 335             } else {
 336                 keyBuf[0] = (char)ch;
 337             }
 338             addContractOrder(new String(keyBuf, 0, length), anOrder);
 339         } else {
 340             // add the entry to the mapping table,
 341             // the same later entry replaces the previous one
 342             mapping.setElementAt(ch, anOrder);
 343         }
 344     }
 345 
 346     private final void addContractOrder(String groupChars, int anOrder) {
 347         addContractOrder(groupChars, anOrder, true);
 348     }
 349 
 350     /**
 351      *  Adds the contracting string into the collation table.
 352      */
 353     private final void addContractOrder(String groupChars, int anOrder,
 354                                           boolean fwd)
 355     {
 356         if (contractTable == null) {
 357             contractTable = new Vector<>(INITIALTABLESIZE);
 358         }
 359 
 360         //initial character
 361         int ch = groupChars.codePointAt(0);
 362         /*
 363         char ch0 = groupChars.charAt(0);
 364         int ch = Character.isHighSurrogate(ch0)?
 365           Character.toCodePoint(ch0, groupChars.charAt(1)):ch0;
 366           */
 367         // See if the initial character of the string already has a contract table.
 368         int entry = mapping.elementAt(ch);
 369         Vector<EntryPair> entryTable = getContractValuesImpl(entry - RBCollationTables.CONTRACTCHARINDEX);
 370 
 371         if (entryTable == null) {
 372             // We need to create a new table of contract entries for this base char
 373             int tableIndex = RBCollationTables.CONTRACTCHARINDEX + contractTable.size();
 374             entryTable = new Vector<>(INITIALTABLESIZE);
 375             contractTable.addElement(entryTable);
 376 
 377             // Add the initial character's current ordering first. then
 378             // update its mapping to point to this contract table
 379             entryTable.addElement(new EntryPair(groupChars.substring(0,Character.charCount(ch)), entry));
 380             mapping.setElementAt(ch, tableIndex);
 381         }
 382 
 383         // Now add (or replace) this string in the table
 384         int index = RBCollationTables.getEntry(entryTable, groupChars, fwd);
 385         if (index != RBCollationTables.UNMAPPED) {
 386             EntryPair pair = entryTable.elementAt(index);
 387             pair.value = anOrder;
 388         } else {
 389             EntryPair pair = entryTable.lastElement();
 390 
 391             // NOTE:  This little bit of logic is here to speed CollationElementIterator
 392             // .nextContractChar().  This code ensures that the longest sequence in
 393             // this list is always the _last_ one in the list.  This keeps
 394             // nextContractChar() from having to search the entire list for the longest
 395             // sequence.
 396             if (groupChars.length() > pair.entryName.length()) {
 397                 entryTable.addElement(new EntryPair(groupChars, anOrder, fwd));
 398             } else {
 399                 entryTable.insertElementAt(new EntryPair(groupChars, anOrder,
 400                         fwd), entryTable.size() - 1);
 401             }
 402         }
 403 
 404         // If this was a forward mapping for a contracting string, also add a
 405         // reverse mapping for it, so that CollationElementIterator.previous
 406         // can work right
 407         if (fwd && groupChars.length() > 1) {
 408             addContractFlags(groupChars);
 409             addContractOrder(new StringBuffer(groupChars).reverse().toString(),
 410                              anOrder, false);
 411         }
 412     }
 413 
 414     /**
 415      * If the given string has been specified as a contracting string
 416      * in this collation table, return its ordering.
 417      * Otherwise return UNMAPPED.
 418      */
 419     private int getContractOrder(String groupChars)
 420     {
 421         int result = RBCollationTables.UNMAPPED;
 422         if (contractTable != null) {
 423             int ch = groupChars.codePointAt(0);
 424             /*
 425             char ch0 = groupChars.charAt(0);
 426             int ch = Character.isHighSurrogate(ch0)?
 427               Character.toCodePoint(ch0, groupChars.charAt(1)):ch0;
 428               */
 429             Vector<EntryPair> entryTable = getContractValues(ch);
 430             if (entryTable != null) {
 431                 int index = RBCollationTables.getEntry(entryTable, groupChars, true);
 432                 if (index != RBCollationTables.UNMAPPED) {
 433                     EntryPair pair = entryTable.elementAt(index);
 434                     result = pair.value;
 435                 }
 436             }
 437         }
 438         return result;
 439     }
 440 
 441     private final int getCharOrder(int ch) {
 442         int order = mapping.elementAt(ch);
 443 
 444         if (order >= RBCollationTables.CONTRACTCHARINDEX) {
 445             Vector<EntryPair> groupList = getContractValuesImpl(order - RBCollationTables.CONTRACTCHARINDEX);
 446             EntryPair pair = groupList.firstElement();
 447             order = pair.value;
 448         }
 449         return order;
 450     }
 451 
 452     /**
 453      *  Get the entry of hash table of the contracting string in the collation
 454      *  table.
 455      *  @param ch the starting character of the contracting string
 456      */
 457     private Vector<EntryPair> getContractValues(int ch)
 458     {
 459         int index = mapping.elementAt(ch);
 460         return getContractValuesImpl(index - RBCollationTables.CONTRACTCHARINDEX);
 461     }
 462 
 463     private Vector<EntryPair> getContractValuesImpl(int index)
 464     {
 465         if (index >= 0)
 466         {
 467             return contractTable.elementAt(index);
 468         }
 469         else // not found
 470         {
 471             return null;
 472         }
 473     }
 474 
 475     /**
 476      *  Adds the expanding string into the collation table.
 477      */
 478     private final void addExpandOrder(String contractChars,
 479                                 String expandChars,
 480                                 int anOrder) throws ParseException
 481     {
 482         // Create an expansion table entry
 483         int tableIndex = addExpansion(anOrder, expandChars);
 484 
 485         // And add its index into the main mapping table
 486         if (contractChars.length() > 1) {
 487             char ch = contractChars.charAt(0);
 488             if (Character.isHighSurrogate(ch) && contractChars.length() == 2) {
 489                 char ch2 = contractChars.charAt(1);
 490                 if (Character.isLowSurrogate(ch2)) {
 491                     //only add into table when it is a legal surrogate
 492                     addOrder(Character.toCodePoint(ch, ch2), tableIndex);
 493                 }
 494             } else {
 495                 addContractOrder(contractChars, tableIndex);
 496             }
 497         } else {
 498             addOrder(contractChars.charAt(0), tableIndex);
 499         }
 500     }
 501 
 502     private final void addExpandOrder(int ch, String expandChars, int anOrder)
 503       throws ParseException
 504     {
 505         int tableIndex = addExpansion(anOrder, expandChars);
 506         addOrder(ch, tableIndex);
 507     }
 508 
 509     /**
 510      * Create a new entry in the expansion table that contains the orderings
 511      * for the given characers.  If anOrder is valid, it is added to the
 512      * beginning of the expanded list of orders.
 513      */
 514     private int addExpansion(int anOrder, String expandChars) {
 515         if (expandTable == null) {
 516             expandTable = new Vector<>(INITIALTABLESIZE);
 517         }
 518 
 519         // If anOrder is valid, we want to add it at the beginning of the list
 520         int offset = (anOrder == RBCollationTables.UNMAPPED) ? 0 : 1;
 521 
 522         int[] valueList = new int[expandChars.length() + offset];
 523         if (offset == 1) {
 524             valueList[0] = anOrder;
 525         }
 526 
 527         int j = offset;
 528         for (int i = 0; i < expandChars.length(); i++) {
 529             char ch0 = expandChars.charAt(i);
 530             char ch1;
 531             int ch;
 532             if (Character.isHighSurrogate(ch0)) {
 533                 if (++i == expandChars.length() ||
 534                     !Character.isLowSurrogate(ch1=expandChars.charAt(i))) {
 535                     //ether we are missing the low surrogate or the next char
 536                     //is not a legal low surrogate, so stop loop
 537                     break;
 538                 }
 539                 ch = Character.toCodePoint(ch0, ch1);
 540 
 541             } else {
 542                 ch = ch0;
 543             }
 544 
 545             int mapValue = getCharOrder(ch);
 546 
 547             if (mapValue != RBCollationTables.UNMAPPED) {
 548                 valueList[j++] = mapValue;
 549             } else {
 550                 // can't find it in the table, will be filled in by commit().
 551                 valueList[j++] = CHARINDEX + ch;
 552             }
 553         }
 554         if (j < valueList.length) {
 555             //we had at least one supplementary character, the size of valueList
 556             //is bigger than it really needs...
 557             int[] tmpBuf = new int[j];
 558             while (--j >= 0) {
 559                 tmpBuf[j] = valueList[j];
 560             }
 561             valueList = tmpBuf;
 562         }
 563         // Add the expanding char list into the expansion table.
 564         int tableIndex = RBCollationTables.EXPANDCHARINDEX + expandTable.size();
 565         expandTable.addElement(valueList);
 566 
 567         return tableIndex;
 568     }
 569 
 570     private void addContractFlags(String chars) {
 571         char c0;
 572         int c;
 573         int len = chars.length();
 574         for (int i = 0; i < len; i++) {
 575             c0 = chars.charAt(i);
 576             c = Character.isHighSurrogate(c0)
 577                           ?Character.toCodePoint(c0, chars.charAt(++i))
 578                           :c0;
 579             contractFlags.put(c, 1);
 580         }
 581     }
 582 
 583     // ==============================================================
 584     // constants
 585     // ==============================================================
 586     final static int CHARINDEX = 0x70000000;  // need look up in .commit()
 587 
 588     private final static int IGNORABLEMASK = 0x0000ffff;
 589     private final static int PRIMARYORDERINCREMENT = 0x00010000;
 590     private final static int SECONDARYORDERINCREMENT = 0x00000100;
 591     private final static int TERTIARYORDERINCREMENT = 0x00000001;
 592     private final static int INITIALTABLESIZE = 20;
 593     private final static int MAXKEYSIZE = 5;
 594 
 595     // ==============================================================
 596     // instance variables
 597     // ==============================================================
 598 
 599     // variables used by the build process
 600     private RBCollationTables.BuildAPI tables = null;
 601     private MergeCollation mPattern = null;
 602     private boolean isOverIgnore = false;
 603     private char[] keyBuf = new char[MAXKEYSIZE];
 604     private IntHashtable contractFlags = new IntHashtable(100);
 605 
 606     // "shadow" copies of the instance variables in RBCollationTables
 607     // (the values in these variables are copied back into RBCollationTables
 608     // at the end of the build process)
 609     private boolean frenchSec = false;
 610     private boolean seAsianSwapping = false;
 611 
 612     private UCompactIntArray mapping = null;
 613     private Vector<Vector<EntryPair>>   contractTable = null;
 614     private Vector<int[]>   expandTable = null;
 615 
 616     private short maxSecOrder = 0;
 617     private short maxTerOrder = 0;
 618 }