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 //-------------------------------------------------------------------------
RBBINode(NodeType t)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
RBBINode(const RBBINode & other)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 //-------------------------------------------------------------------------
~RBBINode()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 //-------------------------------------------------------------------------
cloneTree()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 //-------------------------------------------------------------------------
flattenVariables()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 //-------------------------------------------------------------------------
flattenSets()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 //-------------------------------------------------------------------------
findNodes(UVector * dest,RBBINode::NodeType kind,UErrorCode & status)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
serial(const RBBINode * node)288 static int32_t serial(const RBBINode *node) {
289 return (node == NULL? -1 : node->fSerialNum);
290 }
291
292
printNode(const RBBINode * node)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
RBBI_DEBUG_printUnicodeString(const UnicodeString & s,int minWidth)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
printNodeHeader()343 void RBBINode::printNodeHeader() {
344 RBBIDebugPrintf(" Address serial type LeftChild RightChild Parent position value\n");
345 }
346
printTree(const RBBINode * node,UBool printHeading)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