icuSources/common/rbbinode.cpp

   1 /*
   2 ***************************************************************************
   3 *   Copyright (C) 2002-2008 International Business Machines Corporation   *
   4 *   and others. All rights reserved.                                      *
   5 ***************************************************************************
   6 */
   7
   8 //
   9 //  File:  rbbinode.cpp
  10 //
  11 //         Implementation of class RBBINode, which represents a node in the
  12 //         tree generated when parsing the Rules Based Break Iterator rules.
  13 //
  14 //         This "Class" is actually closer to a struct.
  15 //         Code using it is expected to directly access fields much of the time.
  16 //
  17
  18 #include "unicode/utypes.h"
  19
  20 #if !UCONFIG_NO_BREAK_ITERATION
  21
  22 #include "unicode/unistr.h"
  23 #include "unicode/uniset.h"
  24 #include "unicode/uchar.h"
  25 #include "unicode/parsepos.h"
  26 #include "uvector.h"
  27
  28 #include "rbbirb.h"
  29 #include "rbbinode.h"
  30
  31 #include "uassert.h"
  32
  33
  34 U_NAMESPACE_BEGIN
  35
  36 #ifdef RBBI_DEBUG
  37 static int  gLastSerial = 0;
  38 #endif
  39
  40
  41 //-------------------------------------------------------------------------
  42 //
  43 //    Constructor.   Just set the fields to reasonable default values.
  44 //
  45 //-------------------------------------------------------------------------
  46 RBBINode::RBBINode(NodeType t) : UMemory() {
  47 #ifdef RBBI_DEBUG
  48     fSerialNum    = ++gLastSerial;
  49 #endif
  50     fType         = t;
  51     fParent       = NULL;
  52     fLeftChild    = NULL;
  53     fRightChild   = NULL;
  54     fInputSet     = NULL;
  55     fFirstPos     = 0;
  56     fLastPos      = 0;
  57     fNullable     = FALSE;
  58     fLookAheadEnd = FALSE;
  59     fVal          = 0;
  60     fPrecedence   = precZero;
  61
  62     UErrorCode     status = U_ZERO_ERROR;
  63     fFirstPosSet  = new UVector(status);  // TODO - get a real status from somewhere
  64     fLastPosSet   = new UVector(status);
  65     fFollowPos    = new UVector(status);
  66     if      (t==opCat)    {fPrecedence = precOpCat;}
  67     else if (t==opOr)     {fPrecedence = precOpOr;}
  68     else if (t==opStart)  {fPrecedence = precStart;}
  69     else if (t==opLParen) {fPrecedence = precLParen;}
  70
  71 }
  72
  73
  74 RBBINode::RBBINode(const RBBINode &other) : UMemory(other) {
  75 #ifdef RBBI_DEBUG
  76     fSerialNum   = ++gLastSerial;
  77 #endif
  78     fType        = other.fType;
  79     fParent      = NULL;
  80     fLeftChild   = NULL;
  81     fRightChild  = NULL;
  82     fInputSet    = other.fInputSet;
  83     fPrecedence  = other.fPrecedence;
  84     fText        = other.fText;
  85     fFirstPos    = other.fFirstPos;
  86     fLastPos     = other.fLastPos;
  87     fNullable    = other.fNullable;
  88     fVal         = other.fVal;
  89     UErrorCode     status = U_ZERO_ERROR;
  90     fFirstPosSet = new UVector(status);   // TODO - get a real status from somewhere
  91     fLastPosSet  = new UVector(status);
  92     fFollowPos   = new UVector(status);
  93 }
  94
  95
  96 //-------------------------------------------------------------------------
  97 //
  98 //    Destructor.   Deletes both this node AND any child nodes,
  99 //                  except in the case of variable reference nodes.  For
 100 //                  these, the l. child points back to the definition, which
 101 //                  is common for all references to the variable, meaning
 102 //                  it can't be deleted here.
 103 //
 104 //-------------------------------------------------------------------------
 105 RBBINode::~RBBINode() {
 106     // printf("deleting node %8x   serial %4d\n", this, this->fSerialNum);
 107     delete fInputSet;
 108     fInputSet = NULL;
 109
 110     switch (this->fType) {
 111     case varRef:
 112     case setRef:
 113         // for these node types, multiple instances point to the same "children"
 114         // Storage ownership of children handled elsewhere.  Don't delete here.
 115         break;
 116
 117     default:
 118         delete        fLeftChild;
 119         fLeftChild =   NULL;
 120         delete        fRightChild;
 121         fRightChild = NULL;
 122     }
 123
 124
 125     delete fFirstPosSet;
 126     delete fLastPosSet;
 127     delete fFollowPos;
 128
 129 }
 130
 131
 132 //-------------------------------------------------------------------------
 133 //
 134 //    cloneTree     Make a copy of the subtree rooted at this node.
 135 //                  Discard any variable references encountered along the way,
 136 //                  and replace with copies of the variable's definitions.
 137 //                  Used to replicate the expression underneath variable
 138 //                  references in preparation for generating the DFA tables.
 139 //
 140 //-------------------------------------------------------------------------
 141 RBBINode *RBBINode::cloneTree() {
 142     RBBINode    *n;
 143
 144     if (fType == RBBINode::varRef) {
 145         // If the current node is a variable reference, skip over it
 146         //   and clone the definition of the variable instead.
 147         n = fLeftChild->cloneTree();
 148     } else if (fType == RBBINode::uset) {
 149         n = this;
 150     } else {
 151         n = new RBBINode(*this);
 152         // Check for null pointer.
 153         if (n != NULL) {
 154             if (fLeftChild != NULL) {
 155                 n->fLeftChild          = fLeftChild->cloneTree();
 156                 n->fLeftChild->fParent = n;
 157             }
 158             if (fRightChild != NULL) {
 159                 n->fRightChild          = fRightChild->cloneTree();
 160                 n->fRightChild->fParent = n;
 161             }
 162         }
 163     }
 164     return n;
 165 }
 166
 167
 168
 169 //-------------------------------------------------------------------------
 170 //
 171 //   flattenVariables   Walk a parse tree, replacing any variable
 172 //                      references with a copy of the variable's definition.
 173 //                      Aside from variables, the tree is not changed.
 174 //
 175 //                      Return the root of the tree.  If the root was not a variable
 176 //                      reference, it remains unchanged - the root we started with
 177 //                      is the root we return.  If, however, the root was a variable
 178 //                      reference, the root of the newly cloned replacement tree will
 179 //                      be returned, and the original tree deleted.
 180 //
 181 //                      This function works by recursively walking the tree
 182 //                      without doing anything until a variable reference is
 183 //                      found, then calling cloneTree() at that point.  Any
 184 //                      nested references are handled by cloneTree(), not here.
 185 //
 186 //-------------------------------------------------------------------------
 187 RBBINode *RBBINode::flattenVariables() {
 188     if (fType == varRef) {
 189         RBBINode *retNode = fLeftChild->cloneTree();
 190         delete this;
 191         return retNode;
 192     }
 193
 194     if (fLeftChild != NULL) {
 195         fLeftChild = fLeftChild->flattenVariables();
 196         fLeftChild->fParent  = this;
 197     }
 198     if (fRightChild != NULL) {
 199         fRightChild = fRightChild->flattenVariables();
 200         fRightChild->fParent = this;
 201     }
 202     return this;
 203 }
 204
 205
 206 //-------------------------------------------------------------------------
 207 //
 208 //  flattenSets    Walk the parse tree, replacing any nodes of type setRef
 209 //                 with a copy of the expression tree for the set.  A set's
 210 //                 equivalent expression tree is precomputed and saved as
 211 //                 the left child of the uset node.
 212 //
 213 //-------------------------------------------------------------------------
 214 void RBBINode::flattenSets() {
 215     U_ASSERT(fType != setRef);
 216
 217     if (fLeftChild != NULL) {
 218         if (fLeftChild->fType==setRef) {
 219             RBBINode *setRefNode = fLeftChild;
 220             RBBINode *usetNode   = setRefNode->fLeftChild;
 221             RBBINode *replTree   = usetNode->fLeftChild;
 222             fLeftChild           = replTree->cloneTree();
 223             fLeftChild->fParent  = this;
 224             delete setRefNode;
 225         } else {
 226             fLeftChild->flattenSets();
 227         }
 228     }
 229
 230     if (fRightChild != NULL) {
 231         if (fRightChild->fType==setRef) {
 232             RBBINode *setRefNode = fRightChild;
 233             RBBINode *usetNode   = setRefNode->fLeftChild;
 234             RBBINode *replTree   = usetNode->fLeftChild;
 235             fRightChild           = replTree->cloneTree();
 236             fRightChild->fParent  = this;
 237             delete setRefNode;
 238         } else {
 239             fRightChild->flattenSets();
 240         }
 241     }
 242 }
 243
 244
 245
 246 //-------------------------------------------------------------------------
 247 //
 248 //   findNodes()     Locate all the nodes of the specified type, starting
 249 //                   at the specified root.
 250 //
 251 //-------------------------------------------------------------------------
 252 void   RBBINode::findNodes(UVector *dest, RBBINode::NodeType kind, UErrorCode &status) {
 253     /* test for buffer overflows */
 254     if (U_FAILURE(status)) {
 255         return;
 256     }
 257     if (fType == kind) {
 258         dest->addElement(this, status);
 259     }
 260     if (fLeftChild != NULL) {
 261         fLeftChild->findNodes(dest, kind, status);
 262     }
 263     if (fRightChild != NULL) {
 264         fRightChild->findNodes(dest, kind, status);
 265     }
 266 }
 267
 268
 269 //-------------------------------------------------------------------------
 270 //
 271 //    print.         Print out a single node, for debugging.
 272 //
 273 //-------------------------------------------------------------------------
 274 #ifdef RBBI_DEBUG
 275 void RBBINode::printNode() {
 276     static const char * const nodeTypeNames[] = {
 277                 "setRef",
 278                 "uset",
 279                 "varRef",
 280                 "leafChar",
 281                 "lookAhead",
 282                 "tag",
 283                 "endMark",
 284                 "opStart",
 285                 "opCat",
 286                 "opOr",
 287                 "opStar",
 288                 "opPlus",
 289                 "opQuestion",
 290                 "opBreak",
 291                 "opReverse",
 292                 "opLParen"
 293     };
 294
 295     if (this==NULL) {
 296         RBBIDebugPrintf("%10p", (void *)this);
 297     } else {
 298         RBBIDebugPrintf("%10p  %12s  %10p  %10p  %10p      %4d     %6d   %d ",
 299             (void *)this, nodeTypeNames[fType], (void *)fParent, (void *)fLeftChild, (void *)fRightChild,
 300             fSerialNum, fFirstPos, fVal);
 301         if (fType == varRef) {
 302             RBBI_DEBUG_printUnicodeString(fText);
 303         }
 304     }
 305     RBBIDebugPrintf("\n");
 306 }
 307 #endif
 308
 309
 310 #ifdef RBBI_DEBUG
 311 U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth)
 312 {
 313     int i;
 314     for (i=0; i<s.length(); i++) {
 315         RBBIDebugPrintf("%c", s.charAt(i));
 316         // putc(s.charAt(i), stdout);
 317     }
 318     for (i=s.length(); i<minWidth; i++) {
 319         RBBIDebugPrintf(" ");
 320     }
 321 }
 322 #endif
 323
 324
 325 //-------------------------------------------------------------------------
 326 //
 327 //    print.         Print out the tree of nodes rooted at "this"
 328 //
 329 //-------------------------------------------------------------------------
 330 #ifdef RBBI_DEBUG
 331 void RBBINode::printTree(UBool printHeading) {
 332     if (printHeading) {
 333         RBBIDebugPrintf( "-------------------------------------------------------------------\n"
 334                          "    Address       type         Parent   LeftChild  RightChild    serial  position value\n"
 335               );
 336     }
 337     this->printNode();
 338     if (this != NULL) {
 339         // Only dump the definition under a variable reference if asked to.
 340         // Unconditinally dump children of all other node types.
 341         if (fType != varRef) {
 342             if (fLeftChild != NULL) {
 343                 fLeftChild->printTree(FALSE);
 344             }
 345
 346             if (fRightChild != NULL) {
 347                 fRightChild->printTree(FALSE);
 348             }
 349         }
 350     }
 351 }
 352 #endif
 353
 354
 355
 356 U_NAMESPACE_END
 357
 358 #endif /* #if !UCONFIG_NO_BREAK_ITERATION */