icuSources/common/rbbinode.cpp

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