icuSources/i18n/rbt_set.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4  **********************************************************************
   5  *   Copyright (C) 1999-2011, International Business Machines
   6  *   Corporation and others.  All Rights Reserved.
   7  **********************************************************************
   8  *   Date        Name        Description
   9  *   11/17/99    aliu        Creation.
  10  **********************************************************************
  11  */
  12
  13 #include "unicode/utypes.h"
  14
  15 #if !UCONFIG_NO_TRANSLITERATION
  16
  17 #include "unicode/unistr.h"
  18 #include "unicode/uniset.h"
  19 #include "unicode/utf16.h"
  20 #include "rbt_set.h"
  21 #include "rbt_rule.h"
  22 #include "cmemory.h"
  23 #include "putilimp.h"
  24
  25 U_CDECL_BEGIN
  26 static void U_CALLCONV _deleteRule(void *rule) {
  27     delete (icu::TransliterationRule *)rule;
  28 }
  29 U_CDECL_END
  30
  31 //----------------------------------------------------------------------
  32 // BEGIN Debugging support
  33 //----------------------------------------------------------------------
  34
  35 // #define DEBUG_RBT
  36
  37 #ifdef DEBUG_RBT
  38 #include <stdio.h>
  39 #include "charstr.h"
  40
  41 /**
  42  * @param appendTo result is appended to this param.
  43  * @param input the string being transliterated
  44  * @param pos the index struct
  45  */
  46 static UnicodeString& _formatInput(UnicodeString &appendTo,
  47                                    const UnicodeString& input,
  48                                    const UTransPosition& pos) {
  49     // Output a string of the form aaa{bbb|ccc|ddd}eee, where
  50     // the {} indicate the context start and limit, and the ||
  51     // indicate the start and limit.
  52     if (0 <= pos.contextStart &&
  53         pos.contextStart <= pos.start &&
  54         pos.start <= pos.limit &&
  55         pos.limit <= pos.contextLimit &&
  56         pos.contextLimit <= input.length()) {
  57
  58         UnicodeString a, b, c, d, e;
  59         input.extractBetween(0, pos.contextStart, a);
  60         input.extractBetween(pos.contextStart, pos.start, b);
  61         input.extractBetween(pos.start, pos.limit, c);
  62         input.extractBetween(pos.limit, pos.contextLimit, d);
  63         input.extractBetween(pos.contextLimit, input.length(), e);
  64         appendTo.append(a).append((UChar)123/*{*/).append(b).
  65             append((UChar)124/*|*/).append(c).append((UChar)124/*|*/).append(d).
  66             append((UChar)125/*}*/).append(e);
  67     } else {
  68         appendTo.append("INVALID UTransPosition");
  69         //appendTo.append((UnicodeString)"INVALID UTransPosition {cs=" +
  70         //                pos.contextStart + ", s=" + pos.start + ", l=" +
  71         //                pos.limit + ", cl=" + pos.contextLimit + "} on " +
  72         //                input);
  73     }
  74     return appendTo;
  75 }
  76
  77 // Append a hex string to the target
  78 UnicodeString& _appendHex(uint32_t number,
  79                           int32_t digits,
  80                           UnicodeString& target) {
  81     static const UChar digitString[] = {
  82         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39,
  83         0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0
  84     };
  85     while (digits--) {
  86         target += digitString[(number >> (digits*4)) & 0xF];
  87     }
  88     return target;
  89 }
  90
  91 // Replace nonprintable characters with unicode escapes
  92 UnicodeString& _escape(const UnicodeString &source,
  93                        UnicodeString &target) {
  94     for (int32_t i = 0; i < source.length(); ) {
  95         UChar32 ch = source.char32At(i);
  96         i += U16_LENGTH(ch);
  97         if (ch < 0x09 || (ch > 0x0A && ch < 0x20)|| ch > 0x7E) {
  98             if (ch <= 0xFFFF) {
  99                 target += "\\u";
 100                 _appendHex(ch, 4, target);
 101             } else {
 102                 target += "\\U";
 103                 _appendHex(ch, 8, target);
 104             }
 105         } else {
 106             target += ch;
 107         }
 108     }
 109     return target;
 110 }
 111
 112 inline void _debugOut(const char* msg, TransliterationRule* rule,
 113                       const Replaceable& theText, UTransPosition& pos) {
 114     UnicodeString buf(msg, "");
 115     if (rule) {
 116         UnicodeString r;
 117         rule->toRule(r, TRUE);
 118         buf.append((UChar)32).append(r);
 119     }
 120     buf.append(UnicodeString(" => ", ""));
 121     UnicodeString* text = (UnicodeString*)&theText;
 122     _formatInput(buf, *text, pos);
 123     UnicodeString esc;
 124     _escape(buf, esc);
 125     CharString cbuf(esc);
 126     printf("%s\n", (const char*) cbuf);
 127 }
 128
 129 #else
 130 #define _debugOut(msg, rule, theText, pos)
 131 #endif
 132
 133 //----------------------------------------------------------------------
 134 // END Debugging support
 135 //----------------------------------------------------------------------
 136
 137 // Fill the precontext and postcontext with the patterns of the rules
 138 // that are masking one another.
 139 static void maskingError(const icu::TransliterationRule& rule1,
 140                          const icu::TransliterationRule& rule2,
 141                          UParseError& parseError) {
 142     icu::UnicodeString r;
 143     int32_t len;
 144
 145     parseError.line = parseError.offset = -1;
 146
 147     // for pre-context
 148     rule1.toRule(r, FALSE);
 149     len = uprv_min(r.length(), U_PARSE_CONTEXT_LEN-1);
 150     r.extract(0, len, parseError.preContext);
 151     parseError.preContext[len] = 0;
 152
 153     //for post-context
 154     r.truncate(0);
 155     rule2.toRule(r, FALSE);
 156     len = uprv_min(r.length(), U_PARSE_CONTEXT_LEN-1);
 157     r.extract(0, len, parseError.postContext);
 158     parseError.postContext[len] = 0;
 159 }
 160
 161 U_NAMESPACE_BEGIN
 162
 163 /**
 164  * Construct a new empty rule set.
 165  */
 166 TransliterationRuleSet::TransliterationRuleSet(UErrorCode& status) : UMemory() {
 167     ruleVector = new UVector(&_deleteRule, NULL, status);
 168     if (U_FAILURE(status)) {
 169         return;
 170     }
 171     if (ruleVector == NULL) {
 172         status = U_MEMORY_ALLOCATION_ERROR;
 173     }
 174     rules = NULL;
 175     maxContextLength = 0;
 176 }
 177
 178 /**
 179  * Copy constructor.
 180  */
 181 TransliterationRuleSet::TransliterationRuleSet(const TransliterationRuleSet& other) :
 182     UMemory(other),
 183     ruleVector(0),
 184     rules(0),
 185     maxContextLength(other.maxContextLength) {
 186
 187     int32_t i, len;
 188     uprv_memcpy(index, other.index, sizeof(index));
 189     UErrorCode status = U_ZERO_ERROR;
 190     ruleVector = new UVector(&_deleteRule, NULL, status);
 191     if (other.ruleVector != 0 && ruleVector != 0 && U_SUCCESS(status)) {
 192         len = other.ruleVector->size();
 193         for (i=0; i<len && U_SUCCESS(status); ++i) {
 194             TransliterationRule *tempTranslitRule = new TransliterationRule(*(TransliterationRule*)other.ruleVector->elementAt(i));
 195             // Null pointer test
 196             if (tempTranslitRule == NULL) {
 197                 status = U_MEMORY_ALLOCATION_ERROR;
 198                 break;
 199             }
 200             ruleVector->addElement(tempTranslitRule, status);
 201             if (U_FAILURE(status)) {
 202                 break;
 203             }
 204         }
 205     }
 206     if (other.rules != 0 && U_SUCCESS(status)) {
 207         UParseError p;
 208         freeze(p, status);
 209     }
 210 }
 211
 212 /**
 213  * Destructor.
 214  */
 215 TransliterationRuleSet::~TransliterationRuleSet() {
 216     delete ruleVector; // This deletes the contained rules
 217     uprv_free(rules);
 218 }
 219
 220 void TransliterationRuleSet::setData(const TransliterationRuleData* d) {
 221     /**
 222      * We assume that the ruleset has already been frozen.
 223      */
 224     int32_t len = index[256]; // see freeze()
 225     for (int32_t i=0; i<len; ++i) {
 226         rules[i]->setData(d);
 227     }
 228 }
 229
 230 /**
 231  * Return the maximum context length.
 232  * @return the length of the longest preceding context.
 233  */
 234 int32_t TransliterationRuleSet::getMaximumContextLength(void) const {
 235     return maxContextLength;
 236 }
 237
 238 /**
 239  * Add a rule to this set.  Rules are added in order, and order is
 240  * significant.  The last call to this method must be followed by
 241  * a call to <code>freeze()</code> before the rule set is used.
 242  *
 243  * <p>If freeze() has already been called, calling addRule()
 244  * unfreezes the rules, and freeze() must be called again.
 245  *
 246  * @param adoptedRule the rule to add
 247  */
 248 void TransliterationRuleSet::addRule(TransliterationRule* adoptedRule,
 249                                      UErrorCode& status) {
 250     if (U_FAILURE(status)) {
 251         delete adoptedRule;
 252         return;
 253     }
 254     ruleVector->addElement(adoptedRule, status);
 255
 256     int32_t len;
 257     if ((len = adoptedRule->getContextLength()) > maxContextLength) {
 258         maxContextLength = len;
 259     }
 260
 261     uprv_free(rules);
 262     rules = 0;
 263 }
 264
 265 /**
 266  * Check this for masked rules and index it to optimize performance.
 267  * The sequence of operations is: (1) add rules to a set using
 268  * <code>addRule()</code>; (2) freeze the set using
 269  * <code>freeze()</code>; (3) use the rule set.  If
 270  * <code>addRule()</code> is called after calling this method, it
 271  * invalidates this object, and this method must be called again.
 272  * That is, <code>freeze()</code> may be called multiple times,
 273  * although for optimal performance it shouldn't be.
 274  */
 275 void TransliterationRuleSet::freeze(UParseError& parseError,UErrorCode& status) {
 276     /* Construct the rule array and index table.  We reorder the
 277      * rules by sorting them into 256 bins.  Each bin contains all
 278      * rules matching the index value for that bin.  A rule
 279      * matches an index value if string whose first key character
 280      * has a low byte equal to the index value can match the rule.
 281      *
 282      * Each bin contains zero or more rules, in the same order
 283      * they were found originally.  However, the total rules in
 284      * the bins may exceed the number in the original vector,
 285      * since rules that have a variable as their first key
 286      * character will generally fall into more than one bin.
 287      *
 288      * That is, each bin contains all rules that either have that
 289      * first index value as their first key character, or have
 290      * a set containing the index value as their first character.
 291      */
 292     int32_t n = ruleVector->size();
 293     int32_t j;
 294     int16_t x;
 295     UVector v(2*n, status); // heuristic; adjust as needed
 296
 297     if (U_FAILURE(status)) {
 298         return;
 299     }
 300
 301     /* Precompute the index values.  This saves a LOT of time.
 302      * Be careful not to call malloc(0).
 303      */
 304     int16_t* indexValue = (int16_t*) uprv_malloc( sizeof(int16_t) * (n > 0 ? n : 1) );
 305     /* test for NULL */
 306     if (indexValue == 0) {
 307         status = U_MEMORY_ALLOCATION_ERROR;
 308         return;
 309     }
 310     for (j=0; j<n; ++j) {
 311         TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
 312         indexValue[j] = r->getIndexValue();
 313     }
 314     for (x=0; x<256; ++x) {
 315         index[x] = v.size();
 316         for (j=0; j<n; ++j) {
 317             if (indexValue[j] >= 0) {
 318                 if (indexValue[j] == x) {
 319                     v.addElement(ruleVector->elementAt(j), status);
 320                 }
 321             } else {
 322                 // If the indexValue is < 0, then the first key character is
 323                 // a set, and we must use the more time-consuming
 324                 // matchesIndexValue check.  In practice this happens
 325                 // rarely, so we seldom tread this code path.
 326                 TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
 327                 if (r->matchesIndexValue((uint8_t)x)) {
 328                     v.addElement(r, status);
 329                 }
 330             }
 331         }
 332     }
 333     uprv_free(indexValue);
 334     index[256] = v.size();
 335
 336     /* Freeze things into an array.
 337      */
 338     uprv_free(rules); // Contains alias pointers
 339
 340     /* You can't do malloc(0)! */
 341     if (v.size() == 0) {
 342         rules = NULL;
 343         return;
 344     }
 345     rules = (TransliterationRule **)uprv_malloc(v.size() * sizeof(TransliterationRule *));
 346     /* test for NULL */
 347     if (rules == 0) {
 348         status = U_MEMORY_ALLOCATION_ERROR;
 349         return;
 350     }
 351     for (j=0; j<v.size(); ++j) {
 352         rules[j] = (TransliterationRule*) v.elementAt(j);
 353     }
 354
 355     // TODO Add error reporting that indicates the rules that
 356     //      are being masked.
 357     //UnicodeString errors;
 358
 359     /* Check for masking.  This is MUCH faster than our old check,
 360      * which was each rule against each following rule, since we
 361      * only have to check for masking within each bin now.  It's
 362      * 256*O(n2^2) instead of O(n1^2), where n1 is the total rule
 363      * count, and n2 is the per-bin rule count.  But n2<<n1, so
 364      * it's a big win.
 365      */
 366     for (x=0; x<256; ++x) {
 367         for (j=index[x]; j<index[x+1]-1; ++j) {
 368             TransliterationRule* r1 = rules[j];
 369             for (int32_t k=j+1; k<index[x+1]; ++k) {
 370                 TransliterationRule* r2 = rules[k];
 371                 if (r1->masks(*r2)) {
 372 //|                 if (errors == null) {
 373 //|                     errors = new StringBuffer();
 374 //|                 } else {
 375 //|                     errors.append("\n");
 376 //|                 }
 377 //|                 errors.append("Rule " + r1 + " masks " + r2);
 378                     status = U_RULE_MASK_ERROR;
 379                     maskingError(*r1, *r2, parseError);
 380                     return;
 381                 }
 382             }
 383         }
 384     }
 385
 386     //if (errors != null) {
 387     //    throw new IllegalArgumentException(errors.toString());
 388     //}
 389 }
 390
 391 /**
 392  * Transliterate the given text with the given UTransPosition
 393  * indices.  Return TRUE if the transliteration should continue
 394  * or FALSE if it should halt (because of a U_PARTIAL_MATCH match).
 395  * Note that FALSE is only ever returned if isIncremental is TRUE.
 396  * @param text the text to be transliterated
 397  * @param pos the position indices, which will be updated
 398  * @param incremental if TRUE, assume new text may be inserted
 399  * at index.limit, and return FALSE if thre is a partial match.
 400  * @return TRUE unless a U_PARTIAL_MATCH has been obtained,
 401  * indicating that transliteration should stop until more text
 402  * arrives.
 403  */
 404 UBool TransliterationRuleSet::transliterate(Replaceable& text,
 405                                             UTransPosition& pos,
 406                                             UBool incremental) {
 407     int16_t indexByte = (int16_t) (text.char32At(pos.start) & 0xFF);
 408     for (int32_t i=index[indexByte]; i<index[indexByte+1]; ++i) {
 409         UMatchDegree m = rules[i]->matchAndReplace(text, pos, incremental);
 410         switch (m) {
 411         case U_MATCH:
 412             _debugOut("match", rules[i], text, pos);
 413             return TRUE;
 414         case U_PARTIAL_MATCH:
 415             _debugOut("partial match", rules[i], text, pos);
 416             return FALSE;
 417         default: /* Ram: added default to make GCC happy */
 418             break;
 419         }
 420     }
 421     // No match or partial match from any rule
 422     pos.start += U16_LENGTH(text.char32At(pos.start));
 423     _debugOut("no match", NULL, text, pos);
 424     return TRUE;
 425 }
 426
 427 /**
 428  * Create rule strings that represents this rule set.
 429  */
 430 UnicodeString& TransliterationRuleSet::toRules(UnicodeString& ruleSource,
 431                                                UBool escapeUnprintable) const {
 432     int32_t i;
 433     int32_t count = ruleVector->size();
 434     ruleSource.truncate(0);
 435     for (i=0; i<count; ++i) {
 436         if (i != 0) {
 437             ruleSource.append((UChar) 0x000A /*\n*/);
 438         }
 439         TransliterationRule *r =
 440             (TransliterationRule*) ruleVector->elementAt(i);
 441         r->toRule(ruleSource, escapeUnprintable);
 442     }
 443     return ruleSource;
 444 }
 445
 446 /**
 447  * Return the set of all characters that may be modified
 448  * (getTarget=false) or emitted (getTarget=true) by this set.
 449  */
 450 UnicodeSet& TransliterationRuleSet::getSourceTargetSet(UnicodeSet& result,
 451                                UBool getTarget) const
 452 {
 453     result.clear();
 454     int32_t count = ruleVector->size();
 455     for (int32_t i=0; i<count; ++i) {
 456         TransliterationRule* r =
 457             (TransliterationRule*) ruleVector->elementAt(i);
 458         if (getTarget) {
 459             r->addTargetSetTo(result);
 460         } else {
 461             r->addSourceSetTo(result);
 462         }
 463     }
 464     return result;
 465 }
 466
 467 U_NAMESPACE_END
 468
 469 #endif /* #if !UCONFIG_NO_TRANSLITERATION */