1 2// 3// file: rbbiscan.cpp 4// 5// Copyright (C) 2002-2011, International Business Machines Corporation and others. 6// All Rights Reserved. 7// 8// This file contains the Rule Based Break Iterator Rule Builder functions for 9// scanning the rules and assembling a parse tree. This is the first phase 10// of compiling the rules. 11// 12// The overall of the rules is managed by class RBBIRuleBuilder, which will 13// create and use an instance of this class as part of the process. 14// 15 16#include "unicode/utypes.h" 17 18#if !UCONFIG_NO_BREAK_ITERATION 19 20#include "unicode/unistr.h" 21#include "unicode/uniset.h" 22#include "unicode/uchar.h" 23#include "unicode/uchriter.h" 24#include "unicode/parsepos.h" 25#include "unicode/parseerr.h" 26#include "util.h" 27#include "cmemory.h" 28#include "cstring.h" 29 30#include "rbbirpt.h" // Contains state table for the rbbi rules parser. 31 // generated by a Perl script. 32#include "rbbirb.h" 33#include "rbbinode.h" 34#include "rbbiscan.h" 35#include "rbbitblb.h" 36 37#include "uassert.h" 38 39 40//------------------------------------------------------------------------------ 41// 42// Unicode Set init strings for each of the character classes needed for parsing a rule file. 43// (Initialized with hex values for portability to EBCDIC based machines. 44// Really ugly, but there's no good way to avoid it.) 45// 46// The sets are referred to by name in the rbbirpt.txt, which is the 47// source form of the state transition table for the RBBI rule parser. 48// 49//------------------------------------------------------------------------------ 50static const UChar gRuleSet_rule_char_pattern[] = { 51 // [ ^ [ \ p { Z } \ u 0 0 2 0 52 0x5b, 0x5e, 0x5b, 0x5c, 0x70, 0x7b, 0x5a, 0x7d, 0x5c, 0x75, 0x30, 0x30, 0x32, 0x30, 53 // - \ u 0 0 7 f ] - [ \ p 54 0x2d, 0x5c, 0x75, 0x30, 0x30, 0x37, 0x66, 0x5d, 0x2d, 0x5b, 0x5c, 0x70, 55 // { L } ] - [ \ p { N } ] ] 56 0x7b, 0x4c, 0x7d, 0x5d, 0x2d, 0x5b, 0x5c, 0x70, 0x7b, 0x4e, 0x7d, 0x5d, 0x5d, 0}; 57 58static const UChar gRuleSet_name_char_pattern[] = { 59// [ _ \ p { L } \ p { N } ] 60 0x5b, 0x5f, 0x5c, 0x70, 0x7b, 0x4c, 0x7d, 0x5c, 0x70, 0x7b, 0x4e, 0x7d, 0x5d, 0}; 61 62static const UChar gRuleSet_digit_char_pattern[] = { 63// [ 0 - 9 ] 64 0x5b, 0x30, 0x2d, 0x39, 0x5d, 0}; 65 66static const UChar gRuleSet_name_start_char_pattern[] = { 67// [ _ \ p { L } ] 68 0x5b, 0x5f, 0x5c, 0x70, 0x7b, 0x4c, 0x7d, 0x5d, 0 }; 69 70static const UChar kAny[] = {0x61, 0x6e, 0x79, 0x00}; // "any" 71 72 73U_CDECL_BEGIN 74static void U_CALLCONV RBBISetTable_deleter(void *p) { 75 U_NAMESPACE_QUALIFIER RBBISetTableEl *px = (U_NAMESPACE_QUALIFIER RBBISetTableEl *)p; 76 delete px->key; 77 // Note: px->val is owned by the linked list "fSetsListHead" in scanner. 78 // Don't delete the value nodes here. 79 uprv_free(px); 80} 81U_CDECL_END 82 83U_NAMESPACE_BEGIN 84 85//------------------------------------------------------------------------------ 86// 87// Constructor. 88// 89//------------------------------------------------------------------------------ 90RBBIRuleScanner::RBBIRuleScanner(RBBIRuleBuilder *rb) 91{ 92 fRB = rb; 93 fStackPtr = 0; 94 fStack[fStackPtr] = 0; 95 fNodeStackPtr = 0; 96 fRuleNum = 0; 97 fNodeStack[0] = NULL; 98 99 fSymbolTable = NULL; 100 fSetTable = NULL; 101 102 fScanIndex = 0; 103 fNextIndex = 0; 104 105 fReverseRule = FALSE; 106 fLookAheadRule = FALSE; 107 108 fLineNum = 1; 109 fCharNum = 0; 110 fQuoteMode = FALSE; 111 112 // Do not check status until after all critical fields are sufficiently initialized 113 // that the destructor can run cleanly. 114 if (U_FAILURE(*rb->fStatus)) { 115 return; 116 } 117 118 // 119 // Set up the constant Unicode Sets. 120 // Note: These could be made static, lazily initialized, and shared among 121 // all instances of RBBIRuleScanners. BUT this is quite a bit simpler, 122 // and the time to build these few sets should be small compared to a 123 // full break iterator build. 124 fRuleSets[kRuleSet_rule_char-128] = UnicodeSet(gRuleSet_rule_char_pattern, *rb->fStatus); 125 UnicodeSet *whitespaceSet = uprv_openPatternWhiteSpaceSet(rb->fStatus); 126 if (U_FAILURE(*rb->fStatus)) { 127 return; 128 } 129 fRuleSets[kRuleSet_white_space-128] = *whitespaceSet; 130 delete whitespaceSet; 131 fRuleSets[kRuleSet_name_char-128] = UnicodeSet(gRuleSet_name_char_pattern, *rb->fStatus); 132 fRuleSets[kRuleSet_name_start_char-128] = UnicodeSet(gRuleSet_name_start_char_pattern, *rb->fStatus); 133 fRuleSets[kRuleSet_digit_char-128] = UnicodeSet(gRuleSet_digit_char_pattern, *rb->fStatus); 134 if (*rb->fStatus == U_ILLEGAL_ARGUMENT_ERROR) { 135 // This case happens if ICU's data is missing. UnicodeSet tries to look up property 136 // names from the init string, can't find them, and claims an illegal arguement. 137 // Change the error so that the actual problem will be clearer to users. 138 *rb->fStatus = U_BRK_INIT_ERROR; 139 } 140 if (U_FAILURE(*rb->fStatus)) { 141 return; 142 } 143 144 fSymbolTable = new RBBISymbolTable(this, rb->fRules, *rb->fStatus); 145 if (fSymbolTable == NULL) { 146 *rb->fStatus = U_MEMORY_ALLOCATION_ERROR; 147 return; 148 } 149 fSetTable = uhash_open(uhash_hashUnicodeString, uhash_compareUnicodeString, NULL, rb->fStatus); 150 if (U_FAILURE(*rb->fStatus)) { 151 return; 152 } 153 uhash_setValueDeleter(fSetTable, RBBISetTable_deleter); 154} 155 156 157 158//------------------------------------------------------------------------------ 159// 160// Destructor 161// 162//------------------------------------------------------------------------------ 163RBBIRuleScanner::~RBBIRuleScanner() { 164 delete fSymbolTable; 165 if (fSetTable != NULL) { 166 uhash_close(fSetTable); 167 fSetTable = NULL; 168 169 } 170 171 172 // Node Stack. 173 // Normally has one entry, which is the entire parse tree for the rules. 174 // If errors occured, there may be additional subtrees left on the stack. 175 while (fNodeStackPtr > 0) { 176 delete fNodeStack[fNodeStackPtr]; 177 fNodeStackPtr--; 178 } 179 180} 181 182//------------------------------------------------------------------------------ 183// 184// doParseAction Do some action during rule parsing. 185// Called by the parse state machine. 186// Actions build the parse tree and Unicode Sets, 187// and maintain the parse stack for nested expressions. 188// 189// TODO: unify EParseAction and RBBI_RuleParseAction enum types. 190// They represent exactly the same thing. They're separate 191// only to work around enum forward declaration restrictions 192// in some compilers, while at the same time avoiding multiple 193// definitions problems. I'm sure that there's a better way. 194// 195//------------------------------------------------------------------------------ 196UBool RBBIRuleScanner::doParseActions(int32_t action) 197{ 198 RBBINode *n = NULL; 199 200 UBool returnVal = TRUE; 201 202 switch (action) { 203 204 case doExprStart: 205 pushNewNode(RBBINode::opStart); 206 fRuleNum++; 207 break; 208 209 210 case doExprOrOperator: 211 { 212 fixOpStack(RBBINode::precOpCat); 213 RBBINode *operandNode = fNodeStack[fNodeStackPtr--]; 214 RBBINode *orNode = pushNewNode(RBBINode::opOr); 215 orNode->fLeftChild = operandNode; 216 operandNode->fParent = orNode; 217 } 218 break; 219 220 case doExprCatOperator: 221 // concatenation operator. 222 // For the implicit concatenation of adjacent terms in an expression that are 223 // not separated by any other operator. Action is invoked between the 224 // actions for the two terms. 225 { 226 fixOpStack(RBBINode::precOpCat); 227 RBBINode *operandNode = fNodeStack[fNodeStackPtr--]; 228 RBBINode *catNode = pushNewNode(RBBINode::opCat); 229 catNode->fLeftChild = operandNode; 230 operandNode->fParent = catNode; 231 } 232 break; 233 234 case doLParen: 235 // Open Paren. 236 // The openParen node is a dummy operation type with a low precedence, 237 // which has the affect of ensuring that any real binary op that 238 // follows within the parens binds more tightly to the operands than 239 // stuff outside of the parens. 240 pushNewNode(RBBINode::opLParen); 241 break; 242 243 case doExprRParen: 244 fixOpStack(RBBINode::precLParen); 245 break; 246 247 case doNOP: 248 break; 249 250 case doStartAssign: 251 // We've just scanned "$variable = " 252 // The top of the node stack has the $variable ref node. 253 254 // Save the start position of the RHS text in the StartExpression node 255 // that precedes the $variableReference node on the stack. 256 // This will eventually be used when saving the full $variable replacement 257 // text as a string. 258 n = fNodeStack[fNodeStackPtr-1]; 259 n->fFirstPos = fNextIndex; // move past the '=' 260 261 // Push a new start-of-expression node; needed to keep parse of the 262 // RHS expression happy. 263 pushNewNode(RBBINode::opStart); 264 break; 265 266 267 268 269 case doEndAssign: 270 { 271 // We have reached the end of an assignement statement. 272 // Current scan char is the ';' that terminates the assignment. 273 274 // Terminate expression, leaves expression parse tree rooted in TOS node. 275 fixOpStack(RBBINode::precStart); 276 277 RBBINode *startExprNode = fNodeStack[fNodeStackPtr-2]; 278 RBBINode *varRefNode = fNodeStack[fNodeStackPtr-1]; 279 RBBINode *RHSExprNode = fNodeStack[fNodeStackPtr]; 280 281 // Save original text of right side of assignment, excluding the terminating ';' 282 // in the root of the node for the right-hand-side expression. 283 RHSExprNode->fFirstPos = startExprNode->fFirstPos; 284 RHSExprNode->fLastPos = fScanIndex; 285 fRB->fRules.extractBetween(RHSExprNode->fFirstPos, RHSExprNode->fLastPos, RHSExprNode->fText); 286 287 // Expression parse tree becomes l. child of the $variable reference node. 288 varRefNode->fLeftChild = RHSExprNode; 289 RHSExprNode->fParent = varRefNode; 290 291 // Make a symbol table entry for the $variableRef node. 292 fSymbolTable->addEntry(varRefNode->fText, varRefNode, *fRB->fStatus); 293 if (U_FAILURE(*fRB->fStatus)) { 294 // This is a round-about way to get the parse position set 295 // so that duplicate symbols error messages include a line number. 296 UErrorCode t = *fRB->fStatus; 297 *fRB->fStatus = U_ZERO_ERROR; 298 error(t); 299 } 300 301 // Clean up the stack. 302 delete startExprNode; 303 fNodeStackPtr-=3; 304 break; 305 } 306 307 case doEndOfRule: 308 { 309 fixOpStack(RBBINode::precStart); // Terminate expression, leaves expression 310 if (U_FAILURE(*fRB->fStatus)) { // parse tree rooted in TOS node. 311 break; 312 } 313#ifdef RBBI_DEBUG 314 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "rtree")) {printNodeStack("end of rule");} 315#endif 316 U_ASSERT(fNodeStackPtr == 1); 317 318 // If this rule includes a look-ahead '/', add a endMark node to the 319 // expression tree. 320 if (fLookAheadRule) { 321 RBBINode *thisRule = fNodeStack[fNodeStackPtr]; 322 RBBINode *endNode = pushNewNode(RBBINode::endMark); 323 RBBINode *catNode = pushNewNode(RBBINode::opCat); 324 fNodeStackPtr -= 2; 325 catNode->fLeftChild = thisRule; 326 catNode->fRightChild = endNode; 327 fNodeStack[fNodeStackPtr] = catNode; 328 endNode->fVal = fRuleNum; 329 endNode->fLookAheadEnd = TRUE; 330 } 331 332 // All rule expressions are ORed together. 333 // The ';' that terminates an expression really just functions as a '|' with 334 // a low operator prededence. 335 // 336 // Each of the four sets of rules are collected separately. 337 // (forward, reverse, safe_forward, safe_reverse) 338 // OR this rule into the appropriate group of them. 339 // 340 RBBINode **destRules = (fReverseRule? &fRB->fReverseTree : fRB->fDefaultTree); 341 342 if (*destRules != NULL) { 343 // This is not the first rule encounted. 344 // OR previous stuff (from *destRules) 345 // with the current rule expression (on the Node Stack) 346 // with the resulting OR expression going to *destRules 347 // 348 RBBINode *thisRule = fNodeStack[fNodeStackPtr]; 349 RBBINode *prevRules = *destRules; 350 RBBINode *orNode = pushNewNode(RBBINode::opOr); 351 orNode->fLeftChild = prevRules; 352 prevRules->fParent = orNode; 353 orNode->fRightChild = thisRule; 354 thisRule->fParent = orNode; 355 *destRules = orNode; 356 } 357 else 358 { 359 // This is the first rule encountered (for this direction). 360 // Just move its parse tree from the stack to *destRules. 361 *destRules = fNodeStack[fNodeStackPtr]; 362 } 363 fReverseRule = FALSE; // in preparation for the next rule. 364 fLookAheadRule = FALSE; 365 fNodeStackPtr = 0; 366 } 367 break; 368 369 370 case doRuleError: 371 error(U_BRK_RULE_SYNTAX); 372 returnVal = FALSE; 373 break; 374 375 376 case doVariableNameExpectedErr: 377 error(U_BRK_RULE_SYNTAX); 378 break; 379 380 381 // 382 // Unary operands + ? * 383 // These all appear after the operand to which they apply. 384 // When we hit one, the operand (may be a whole sub expression) 385 // will be on the top of the stack. 386 // Unary Operator becomes TOS, with the old TOS as its one child. 387 case doUnaryOpPlus: 388 { 389 RBBINode *operandNode = fNodeStack[fNodeStackPtr--]; 390 RBBINode *plusNode = pushNewNode(RBBINode::opPlus); 391 plusNode->fLeftChild = operandNode; 392 operandNode->fParent = plusNode; 393 } 394 break; 395 396 case doUnaryOpQuestion: 397 { 398 RBBINode *operandNode = fNodeStack[fNodeStackPtr--]; 399 RBBINode *qNode = pushNewNode(RBBINode::opQuestion); 400 qNode->fLeftChild = operandNode; 401 operandNode->fParent = qNode; 402 } 403 break; 404 405 case doUnaryOpStar: 406 { 407 RBBINode *operandNode = fNodeStack[fNodeStackPtr--]; 408 RBBINode *starNode = pushNewNode(RBBINode::opStar); 409 starNode->fLeftChild = operandNode; 410 operandNode->fParent = starNode; 411 } 412 break; 413 414 case doRuleChar: 415 // A "Rule Character" is any single character that is a literal part 416 // of the regular expression. Like a, b and c in the expression "(abc*) | [:L:]" 417 // These are pretty uncommon in break rules; the terms are more commonly 418 // sets. To keep things uniform, treat these characters like as 419 // sets that just happen to contain only one character. 420 { 421 n = pushNewNode(RBBINode::setRef); 422 findSetFor(fC.fChar, n); 423 n->fFirstPos = fScanIndex; 424 n->fLastPos = fNextIndex; 425 fRB->fRules.extractBetween(n->fFirstPos, n->fLastPos, n->fText); 426 break; 427 } 428 429 case doDotAny: 430 // scanned a ".", meaning match any single character. 431 { 432 n = pushNewNode(RBBINode::setRef); 433 findSetFor(kAny, n); 434 n->fFirstPos = fScanIndex; 435 n->fLastPos = fNextIndex; 436 fRB->fRules.extractBetween(n->fFirstPos, n->fLastPos, n->fText); 437 break; 438 } 439 440 case doSlash: 441 // Scanned a '/', which identifies a look-ahead break position in a rule. 442 n = pushNewNode(RBBINode::lookAhead); 443 n->fVal = fRuleNum; 444 n->fFirstPos = fScanIndex; 445 n->fLastPos = fNextIndex; 446 fRB->fRules.extractBetween(n->fFirstPos, n->fLastPos, n->fText); 447 fLookAheadRule = TRUE; 448 break; 449 450 451 case doStartTagValue: 452 // Scanned a '{', the opening delimiter for a tag value within a rule. 453 n = pushNewNode(RBBINode::tag); 454 n->fVal = 0; 455 n->fFirstPos = fScanIndex; 456 n->fLastPos = fNextIndex; 457 break; 458 459 case doTagDigit: 460 // Just scanned a decimal digit that's part of a tag value 461 { 462 n = fNodeStack[fNodeStackPtr]; 463 uint32_t v = u_charDigitValue(fC.fChar); 464 U_ASSERT(v < 10); 465 n->fVal = n->fVal*10 + v; 466 break; 467 } 468 469 case doTagValue: 470 n = fNodeStack[fNodeStackPtr]; 471 n->fLastPos = fNextIndex; 472 fRB->fRules.extractBetween(n->fFirstPos, n->fLastPos, n->fText); 473 break; 474 475 case doTagExpectedError: 476 error(U_BRK_MALFORMED_RULE_TAG); 477 returnVal = FALSE; 478 break; 479 480 case doOptionStart: 481 // Scanning a !!option. At the start of string. 482 fOptionStart = fScanIndex; 483 break; 484 485 case doOptionEnd: 486 { 487 UnicodeString opt(fRB->fRules, fOptionStart, fScanIndex-fOptionStart); 488 if (opt == UNICODE_STRING("chain", 5)) { 489 fRB->fChainRules = TRUE; 490 } else if (opt == UNICODE_STRING("LBCMNoChain", 11)) { 491 fRB->fLBCMNoChain = TRUE; 492 } else if (opt == UNICODE_STRING("forward", 7)) { 493 fRB->fDefaultTree = &fRB->fForwardTree; 494 } else if (opt == UNICODE_STRING("reverse", 7)) { 495 fRB->fDefaultTree = &fRB->fReverseTree; 496 } else if (opt == UNICODE_STRING("safe_forward", 12)) { 497 fRB->fDefaultTree = &fRB->fSafeFwdTree; 498 } else if (opt == UNICODE_STRING("safe_reverse", 12)) { 499 fRB->fDefaultTree = &fRB->fSafeRevTree; 500 } else if (opt == UNICODE_STRING("lookAheadHardBreak", 18)) { 501 fRB->fLookAheadHardBreak = TRUE; 502 } else { 503 error(U_BRK_UNRECOGNIZED_OPTION); 504 } 505 } 506 break; 507 508 case doReverseDir: 509 fReverseRule = TRUE; 510 break; 511 512 case doStartVariableName: 513 n = pushNewNode(RBBINode::varRef); 514 if (U_FAILURE(*fRB->fStatus)) { 515 break; 516 } 517 n->fFirstPos = fScanIndex; 518 break; 519 520 case doEndVariableName: 521 n = fNodeStack[fNodeStackPtr]; 522 if (n==NULL || n->fType != RBBINode::varRef) { 523 error(U_BRK_INTERNAL_ERROR); 524 break; 525 } 526 n->fLastPos = fScanIndex; 527 fRB->fRules.extractBetween(n->fFirstPos+1, n->fLastPos, n->fText); 528 // Look the newly scanned name up in the symbol table 529 // If there's an entry, set the l. child of the var ref to the replacement expression. 530 // (We also pass through here when scanning assignments, but no harm is done, other 531 // than a slight wasted effort that seems hard to avoid. Lookup will be null) 532 n->fLeftChild = fSymbolTable->lookupNode(n->fText); 533 break; 534 535 case doCheckVarDef: 536 n = fNodeStack[fNodeStackPtr]; 537 if (n->fLeftChild == NULL) { 538 error(U_BRK_UNDEFINED_VARIABLE); 539 returnVal = FALSE; 540 } 541 break; 542 543 case doExprFinished: 544 break; 545 546 case doRuleErrorAssignExpr: 547 error(U_BRK_ASSIGN_ERROR); 548 returnVal = FALSE; 549 break; 550 551 case doExit: 552 returnVal = FALSE; 553 break; 554 555 case doScanUnicodeSet: 556 scanSet(); 557 break; 558 559 default: 560 error(U_BRK_INTERNAL_ERROR); 561 returnVal = FALSE; 562 break; 563 } 564 return returnVal; 565} 566 567 568 569 570//------------------------------------------------------------------------------ 571// 572// Error Report a rule parse error. 573// Only report it if no previous error has been recorded. 574// 575//------------------------------------------------------------------------------ 576void RBBIRuleScanner::error(UErrorCode e) { 577 if (U_SUCCESS(*fRB->fStatus)) { 578 *fRB->fStatus = e; 579 if (fRB->fParseError) { 580 fRB->fParseError->line = fLineNum; 581 fRB->fParseError->offset = fCharNum; 582 fRB->fParseError->preContext[0] = 0; 583 fRB->fParseError->preContext[0] = 0; 584 } 585 } 586} 587 588 589 590 591//------------------------------------------------------------------------------ 592// 593// fixOpStack The parse stack holds partially assembled chunks of the parse tree. 594// An entry on the stack may be as small as a single setRef node, 595// or as large as the parse tree 596// for an entire expression (this will be the one item left on the stack 597// when the parsing of an RBBI rule completes. 598// 599// This function is called when a binary operator is encountered. 600// It looks back up the stack for operators that are not yet associated 601// with a right operand, and if the precedence of the stacked operator >= 602// the precedence of the current operator, binds the operand left, 603// to the previously encountered operator. 604// 605//------------------------------------------------------------------------------ 606void RBBIRuleScanner::fixOpStack(RBBINode::OpPrecedence p) { 607 RBBINode *n; 608 // printNodeStack("entering fixOpStack()"); 609 for (;;) { 610 n = fNodeStack[fNodeStackPtr-1]; // an operator node 611 if (n->fPrecedence == 0) { 612 RBBIDebugPuts("RBBIRuleScanner::fixOpStack, bad operator node"); 613 error(U_BRK_INTERNAL_ERROR); 614 return; 615 } 616 617 if (n->fPrecedence < p || n->fPrecedence <= RBBINode::precLParen) { 618 // The most recent operand goes with the current operator, 619 // not with the previously stacked one. 620 break; 621 } 622 // Stack operator is a binary op ( '|' or concatenation) 623 // TOS operand becomes right child of this operator. 624 // Resulting subexpression becomes the TOS operand. 625 n->fRightChild = fNodeStack[fNodeStackPtr]; 626 fNodeStack[fNodeStackPtr]->fParent = n; 627 fNodeStackPtr--; 628 // printNodeStack("looping in fixOpStack() "); 629 } 630 631 if (p <= RBBINode::precLParen) { 632 // Scan is at a right paren or end of expression. 633 // The scanned item must match the stack, or else there was an error. 634 // Discard the left paren (or start expr) node from the stack, 635 // leaving the completed (sub)expression as TOS. 636 if (n->fPrecedence != p) { 637 // Right paren encountered matched start of expression node, or 638 // end of expression matched with a left paren node. 639 error(U_BRK_MISMATCHED_PAREN); 640 } 641 fNodeStack[fNodeStackPtr-1] = fNodeStack[fNodeStackPtr]; 642 fNodeStackPtr--; 643 // Delete the now-discarded LParen or Start node. 644 delete n; 645 } 646 // printNodeStack("leaving fixOpStack()"); 647} 648 649 650 651 652//------------------------------------------------------------------------------ 653// 654// findSetFor given a UnicodeString, 655// - find the corresponding Unicode Set (uset node) 656// (create one if necessary) 657// - Set fLeftChild of the caller's node (should be a setRef node) 658// to the uset node 659// Maintain a hash table of uset nodes, so the same one is always used 660// for the same string. 661// If a "to adopt" set is provided and we haven't seen this key before, 662// add the provided set to the hash table. 663// If the string is one (32 bit) char in length, the set contains 664// just one element which is the char in question. 665// If the string is "any", return a set containing all chars. 666// 667//------------------------------------------------------------------------------ 668void RBBIRuleScanner::findSetFor(const UnicodeString &s, RBBINode *node, UnicodeSet *setToAdopt) { 669 670 RBBISetTableEl *el; 671 672 // First check whether we've already cached a set for this string. 673 // If so, just use the cached set in the new node. 674 // delete any set provided by the caller, since we own it. 675 el = (RBBISetTableEl *)uhash_get(fSetTable, &s); 676 if (el != NULL) { 677 delete setToAdopt; 678 node->fLeftChild = el->val; 679 U_ASSERT(node->fLeftChild->fType == RBBINode::uset); 680 return; 681 } 682 683 // Haven't seen this set before. 684 // If the caller didn't provide us with a prebuilt set, 685 // create a new UnicodeSet now. 686 if (setToAdopt == NULL) { 687 if (s.compare(kAny, -1) == 0) { 688 setToAdopt = new UnicodeSet(0x000000, 0x10ffff); 689 } else { 690 UChar32 c; 691 c = s.char32At(0); 692 setToAdopt = new UnicodeSet(c, c); 693 } 694 } 695 696 // 697 // Make a new uset node to refer to this UnicodeSet 698 // This new uset node becomes the child of the caller's setReference node. 699 // 700 RBBINode *usetNode = new RBBINode(RBBINode::uset); 701 if (usetNode == NULL) { 702 error(U_MEMORY_ALLOCATION_ERROR); 703 return; 704 } 705 usetNode->fInputSet = setToAdopt; 706 usetNode->fParent = node; 707 node->fLeftChild = usetNode; 708 usetNode->fText = s; 709 710 711 // 712 // Add the new uset node to the list of all uset nodes. 713 // 714 fRB->fUSetNodes->addElement(usetNode, *fRB->fStatus); 715 716 717 // 718 // Add the new set to the set hash table. 719 // 720 el = (RBBISetTableEl *)uprv_malloc(sizeof(RBBISetTableEl)); 721 UnicodeString *tkey = new UnicodeString(s); 722 if (tkey == NULL || el == NULL || setToAdopt == NULL) { 723 // Delete to avoid memory leak 724 delete tkey; 725 tkey = NULL; 726 uprv_free(el); 727 el = NULL; 728 delete setToAdopt; 729 setToAdopt = NULL; 730 731 error(U_MEMORY_ALLOCATION_ERROR); 732 return; 733 } 734 el->key = tkey; 735 el->val = usetNode; 736 uhash_put(fSetTable, el->key, el, fRB->fStatus); 737 738 return; 739} 740 741 742 743// 744// Assorted Unicode character constants. 745// Numeric because there is no portable way to enter them as literals. 746// (Think EBCDIC). 747// 748static const UChar chCR = 0x0d; // New lines, for terminating comments. 749static const UChar chLF = 0x0a; 750static const UChar chNEL = 0x85; // NEL newline variant 751static const UChar chLS = 0x2028; // Unicode Line Separator 752static const UChar chApos = 0x27; // single quote, for quoted chars. 753static const UChar chPound = 0x23; // '#', introduces a comment. 754static const UChar chBackSlash = 0x5c; // '\' introduces a char escape 755static const UChar chLParen = 0x28; 756static const UChar chRParen = 0x29; 757 758 759//------------------------------------------------------------------------------ 760// 761// stripRules Return a rules string without unnecessary 762// characters. 763// 764//------------------------------------------------------------------------------ 765UnicodeString RBBIRuleScanner::stripRules(const UnicodeString &rules) { 766 UnicodeString strippedRules; 767 int rulesLength = rules.length(); 768 for (int idx = 0; idx < rulesLength; ) { 769 UChar ch = rules[idx++]; 770 if (ch == chPound) { 771 while (idx < rulesLength 772 && ch != chCR && ch != chLF && ch != chNEL) 773 { 774 ch = rules[idx++]; 775 } 776 } 777 if (!u_isISOControl(ch)) { 778 strippedRules.append(ch); 779 } 780 } 781 // strippedRules = strippedRules.unescape(); 782 return strippedRules; 783} 784 785 786//------------------------------------------------------------------------------ 787// 788// nextCharLL Low Level Next Char from rule input source. 789// Get a char from the input character iterator, 790// keep track of input position for error reporting. 791// 792//------------------------------------------------------------------------------ 793UChar32 RBBIRuleScanner::nextCharLL() { 794 UChar32 ch; 795 796 if (fNextIndex >= fRB->fRules.length()) { 797 return (UChar32)-1; 798 } 799 ch = fRB->fRules.char32At(fNextIndex); 800 fNextIndex = fRB->fRules.moveIndex32(fNextIndex, 1); 801 802 if (ch == chCR || 803 ch == chNEL || 804 ch == chLS || 805 (ch == chLF && fLastChar != chCR)) { 806 // Character is starting a new line. Bump up the line number, and 807 // reset the column to 0. 808 fLineNum++; 809 fCharNum=0; 810 if (fQuoteMode) { 811 error(U_BRK_NEW_LINE_IN_QUOTED_STRING); 812 fQuoteMode = FALSE; 813 } 814 } 815 else { 816 // Character is not starting a new line. Except in the case of a 817 // LF following a CR, increment the column position. 818 if (ch != chLF) { 819 fCharNum++; 820 } 821 } 822 fLastChar = ch; 823 return ch; 824} 825 826 827//------------------------------------------------------------------------------ 828// 829// nextChar for rules scanning. At this level, we handle stripping 830// out comments and processing backslash character escapes. 831// The rest of the rules grammar is handled at the next level up. 832// 833//------------------------------------------------------------------------------ 834void RBBIRuleScanner::nextChar(RBBIRuleChar &c) { 835 836 // Unicode Character constants needed for the processing done by nextChar(), 837 // in hex because literals wont work on EBCDIC machines. 838 839 fScanIndex = fNextIndex; 840 c.fChar = nextCharLL(); 841 c.fEscaped = FALSE; 842 843 // 844 // check for '' sequence. 845 // These are recognized in all contexts, whether in quoted text or not. 846 // 847 if (c.fChar == chApos) { 848 if (fRB->fRules.char32At(fNextIndex) == chApos) { 849 c.fChar = nextCharLL(); // get nextChar officially so character counts 850 c.fEscaped = TRUE; // stay correct. 851 } 852 else 853 { 854 // Single quote, by itself. 855 // Toggle quoting mode. 856 // Return either '(' or ')', because quotes cause a grouping of the quoted text. 857 fQuoteMode = !fQuoteMode; 858 if (fQuoteMode == TRUE) { 859 c.fChar = chLParen; 860 } else { 861 c.fChar = chRParen; 862 } 863 c.fEscaped = FALSE; // The paren that we return is not escaped. 864 return; 865 } 866 } 867 868 if (fQuoteMode) { 869 c.fEscaped = TRUE; 870 } 871 else 872 { 873 // We are not in a 'quoted region' of the source. 874 // 875 if (c.fChar == chPound) { 876 // Start of a comment. Consume the rest of it. 877 // The new-line char that terminates the comment is always returned. 878 // It will be treated as white-space, and serves to break up anything 879 // that might otherwise incorrectly clump together with a comment in 880 // the middle (a variable name, for example.) 881 for (;;) { 882 c.fChar = nextCharLL(); 883 if (c.fChar == (UChar32)-1 || // EOF 884 c.fChar == chCR || 885 c.fChar == chLF || 886 c.fChar == chNEL || 887 c.fChar == chLS) {break;} 888 } 889 } 890 if (c.fChar == (UChar32)-1) { 891 return; 892 } 893 894 // 895 // check for backslash escaped characters. 896 // Use UnicodeString::unescapeAt() to handle them. 897 // 898 if (c.fChar == chBackSlash) { 899 c.fEscaped = TRUE; 900 int32_t startX = fNextIndex; 901 c.fChar = fRB->fRules.unescapeAt(fNextIndex); 902 if (fNextIndex == startX) { 903 error(U_BRK_HEX_DIGITS_EXPECTED); 904 } 905 fCharNum += fNextIndex-startX; 906 } 907 } 908 // putc(c.fChar, stdout); 909} 910 911//------------------------------------------------------------------------------ 912// 913// Parse RBBI rules. The state machine for rules parsing is here. 914// The state tables are hand-written in the file rbbirpt.txt, 915// and converted to the form used here by a perl 916// script rbbicst.pl 917// 918//------------------------------------------------------------------------------ 919void RBBIRuleScanner::parse() { 920 uint16_t state; 921 const RBBIRuleTableEl *tableEl; 922 923 if (U_FAILURE(*fRB->fStatus)) { 924 return; 925 } 926 927 state = 1; 928 nextChar(fC); 929 // 930 // Main loop for the rule parsing state machine. 931 // Runs once per state transition. 932 // Each time through optionally performs, depending on the state table, 933 // - an advance to the the next input char 934 // - an action to be performed. 935 // - pushing or popping a state to/from the local state return stack. 936 // 937 for (;;) { 938 // Bail out if anything has gone wrong. 939 // RBBI rule file parsing stops on the first error encountered. 940 if (U_FAILURE(*fRB->fStatus)) { 941 break; 942 } 943 944 // Quit if state == 0. This is the normal way to exit the state machine. 945 // 946 if (state == 0) { 947 break; 948 } 949 950 // Find the state table element that matches the input char from the rule, or the 951 // class of the input character. Start with the first table row for this 952 // state, then linearly scan forward until we find a row that matches the 953 // character. The last row for each state always matches all characters, so 954 // the search will stop there, if not before. 955 // 956 tableEl = &gRuleParseStateTable[state]; 957 #ifdef RBBI_DEBUG 958 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "scan")) { 959 RBBIDebugPrintf("char, line, col = (\'%c\', %d, %d) state=%s ", 960 fC.fChar, fLineNum, fCharNum, RBBIRuleStateNames[state]); 961 } 962 #endif 963 964 for (;;) { 965 #ifdef RBBI_DEBUG 966 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "scan")) { RBBIDebugPrintf(".");} 967 #endif 968 if (tableEl->fCharClass < 127 && fC.fEscaped == FALSE && tableEl->fCharClass == fC.fChar) { 969 // Table row specified an individual character, not a set, and 970 // the input character is not escaped, and 971 // the input character matched it. 972 break; 973 } 974 if (tableEl->fCharClass == 255) { 975 // Table row specified default, match anything character class. 976 break; 977 } 978 if (tableEl->fCharClass == 254 && fC.fEscaped) { 979 // Table row specified "escaped" and the char was escaped. 980 break; 981 } 982 if (tableEl->fCharClass == 253 && fC.fEscaped && 983 (fC.fChar == 0x50 || fC.fChar == 0x70 )) { 984 // Table row specified "escaped P" and the char is either 'p' or 'P'. 985 break; 986 } 987 if (tableEl->fCharClass == 252 && fC.fChar == (UChar32)-1) { 988 // Table row specified eof and we hit eof on the input. 989 break; 990 } 991 992 if (tableEl->fCharClass >= 128 && tableEl->fCharClass < 240 && // Table specs a char class && 993 fC.fEscaped == FALSE && // char is not escaped && 994 fC.fChar != (UChar32)-1) { // char is not EOF 995 if (fRuleSets[tableEl->fCharClass-128].contains(fC.fChar)) { 996 // Table row specified a character class, or set of characters, 997 // and the current char matches it. 998 break; 999 } 1000 } 1001 1002 // No match on this row, advance to the next row for this state, 1003 tableEl++; 1004 } 1005 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "scan")) { RBBIDebugPuts("");} 1006 1007 // 1008 // We've found the row of the state table that matches the current input 1009 // character from the rules string. 1010 // Perform any action specified by this row in the state table. 1011 if (doParseActions((int32_t)tableEl->fAction) == FALSE) { 1012 // Break out of the state machine loop if the 1013 // the action signalled some kind of error, or 1014 // the action was to exit, occurs on normal end-of-rules-input. 1015 break; 1016 } 1017 1018 if (tableEl->fPushState != 0) { 1019 fStackPtr++; 1020 if (fStackPtr >= kStackSize) { 1021 error(U_BRK_INTERNAL_ERROR); 1022 RBBIDebugPuts("RBBIRuleScanner::parse() - state stack overflow."); 1023 fStackPtr--; 1024 } 1025 fStack[fStackPtr] = tableEl->fPushState; 1026 } 1027 1028 if (tableEl->fNextChar) { 1029 nextChar(fC); 1030 } 1031 1032 // Get the next state from the table entry, or from the 1033 // state stack if the next state was specified as "pop". 1034 if (tableEl->fNextState != 255) { 1035 state = tableEl->fNextState; 1036 } else { 1037 state = fStack[fStackPtr]; 1038 fStackPtr--; 1039 if (fStackPtr < 0) { 1040 error(U_BRK_INTERNAL_ERROR); 1041 RBBIDebugPuts("RBBIRuleScanner::parse() - state stack underflow."); 1042 fStackPtr++; 1043 } 1044 } 1045 1046 } 1047 1048 // 1049 // If there were NO user specified reverse rules, set up the equivalent of ".*;" 1050 // 1051 if (fRB->fReverseTree == NULL) { 1052 fRB->fReverseTree = pushNewNode(RBBINode::opStar); 1053 RBBINode *operand = pushNewNode(RBBINode::setRef); 1054 findSetFor(kAny, operand); 1055 fRB->fReverseTree->fLeftChild = operand; 1056 operand->fParent = fRB->fReverseTree; 1057 fNodeStackPtr -= 2; 1058 } 1059 1060 1061 // 1062 // Parsing of the input RBBI rules is complete. 1063 // We now have a parse tree for the rule expressions 1064 // and a list of all UnicodeSets that are referenced. 1065 // 1066#ifdef RBBI_DEBUG 1067 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "symbols")) {fSymbolTable->rbbiSymtablePrint();} 1068 if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "ptree")) 1069 { 1070 RBBIDebugPrintf("Completed Forward Rules Parse Tree...\n"); 1071 fRB->fForwardTree->printTree(TRUE); 1072 RBBIDebugPrintf("\nCompleted Reverse Rules Parse Tree...\n"); 1073 fRB->fReverseTree->printTree(TRUE); 1074 RBBIDebugPrintf("\nCompleted Safe Point Forward Rules Parse Tree...\n"); 1075 fRB->fSafeFwdTree->printTree(TRUE); 1076 RBBIDebugPrintf("\nCompleted Safe Point Reverse Rules Parse Tree...\n"); 1077 fRB->fSafeRevTree->printTree(TRUE); 1078 } 1079#endif 1080} 1081 1082 1083//------------------------------------------------------------------------------ 1084// 1085// printNodeStack for debugging... 1086// 1087//------------------------------------------------------------------------------ 1088#ifdef RBBI_DEBUG 1089void RBBIRuleScanner::printNodeStack(const char *title) { 1090 int i; 1091 RBBIDebugPrintf("%s. Dumping node stack...\n", title); 1092 for (i=fNodeStackPtr; i>0; i--) {fNodeStack[i]->printTree(TRUE);} 1093} 1094#endif 1095 1096 1097 1098 1099//------------------------------------------------------------------------------ 1100// 1101// pushNewNode create a new RBBINode of the specified type and push it 1102// onto the stack of nodes. 1103// 1104//------------------------------------------------------------------------------ 1105RBBINode *RBBIRuleScanner::pushNewNode(RBBINode::NodeType t) { 1106 fNodeStackPtr++; 1107 if (fNodeStackPtr >= kStackSize) { 1108 error(U_BRK_INTERNAL_ERROR); 1109 RBBIDebugPuts("RBBIRuleScanner::pushNewNode - stack overflow."); 1110 *fRB->fStatus = U_BRK_INTERNAL_ERROR; 1111 return NULL; 1112 } 1113 fNodeStack[fNodeStackPtr] = new RBBINode(t); 1114 if (fNodeStack[fNodeStackPtr] == NULL) { 1115 *fRB->fStatus = U_MEMORY_ALLOCATION_ERROR; 1116 } 1117 return fNodeStack[fNodeStackPtr]; 1118} 1119 1120 1121 1122//------------------------------------------------------------------------------ 1123// 1124// scanSet Construct a UnicodeSet from the text at the current scan 1125// position. Advance the scan position to the first character 1126// after the set. 1127// 1128// A new RBBI setref node referring to the set is pushed onto the node 1129// stack. 1130// 1131// The scan position is normally under the control of the state machine 1132// that controls rule parsing. UnicodeSets, however, are parsed by 1133// the UnicodeSet constructor, not by the RBBI rule parser. 1134// 1135//------------------------------------------------------------------------------ 1136void RBBIRuleScanner::scanSet() { 1137 UnicodeSet *uset; 1138 ParsePosition pos; 1139 int startPos; 1140 int i; 1141 1142 if (U_FAILURE(*fRB->fStatus)) { 1143 return; 1144 } 1145 1146 pos.setIndex(fScanIndex); 1147 startPos = fScanIndex; 1148 UErrorCode localStatus = U_ZERO_ERROR; 1149 uset = new UnicodeSet(fRB->fRules, pos, USET_IGNORE_SPACE, 1150 fSymbolTable, 1151 localStatus); 1152 if (uset == NULL) { 1153 localStatus = U_MEMORY_ALLOCATION_ERROR; 1154 } 1155 if (U_FAILURE(localStatus)) { 1156 // TODO: Get more accurate position of the error from UnicodeSet's return info. 1157 // UnicodeSet appears to not be reporting correctly at this time. 1158 #ifdef RBBI_DEBUG 1159 RBBIDebugPrintf("UnicodeSet parse postion.ErrorIndex = %d\n", pos.getIndex()); 1160 #endif 1161 error(localStatus); 1162 delete uset; 1163 return; 1164 } 1165 1166 // Verify that the set contains at least one code point. 1167 // 1168 if (uset->isEmpty()) { 1169 // This set is empty. 1170 // Make it an error, because it almost certainly is not what the user wanted. 1171 // Also, avoids having to think about corner cases in the tree manipulation code 1172 // that occurs later on. 1173 error(U_BRK_RULE_EMPTY_SET); 1174 delete uset; 1175 return; 1176 } 1177 1178 1179 // Advance the RBBI parse postion over the UnicodeSet pattern. 1180 // Don't just set fScanIndex because the line/char positions maintained 1181 // for error reporting would be thrown off. 1182 i = pos.getIndex(); 1183 for (;;) { 1184 if (fNextIndex >= i) { 1185 break; 1186 } 1187 nextCharLL(); 1188 } 1189 1190 if (U_SUCCESS(*fRB->fStatus)) { 1191 RBBINode *n; 1192 1193 n = pushNewNode(RBBINode::setRef); 1194 n->fFirstPos = startPos; 1195 n->fLastPos = fNextIndex; 1196 fRB->fRules.extractBetween(n->fFirstPos, n->fLastPos, n->fText); 1197 // findSetFor() serves several purposes here: 1198 // - Adopts storage for the UnicodeSet, will be responsible for deleting. 1199 // - Mantains collection of all sets in use, needed later for establishing 1200 // character categories for run time engine. 1201 // - Eliminates mulitiple instances of the same set. 1202 // - Creates a new uset node if necessary (if this isn't a duplicate.) 1203 findSetFor(n->fText, n, uset); 1204 } 1205 1206} 1207 1208U_NAMESPACE_END 1209 1210#endif /* #if !UCONFIG_NO_BREAK_ITERATION */ 1211