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