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 */ 470