icuSources/common/rbbiscan.cpp

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