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
38U_NAMESPACE_BEGIN
39
40#ifdef RBBI_DEBUG
41static int gLastSerial = 0;
42#endif
43
44
45//-------------------------------------------------------------------------
46//
47// Constructor. Just set the fields to reasonable default values.
48//
49//-------------------------------------------------------------------------
50RBBINode::RBBINode(NodeType t) : UMemory() {
51#ifdef RBBI_DEBUG
52 fSerialNum = ++gLastSerial;
53#endif
54 fType = t;
55 fParent = nullptr;
56 fLeftChild = nullptr;
57 fRightChild = nullptr;
58 fInputSet = nullptr;
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
80RBBINode::RBBINode(const RBBINode &other) : UMemory(other) {
81#ifdef RBBI_DEBUG
82 fSerialNum = ++gLastSerial;
83#endif
84 fType = other.fType;
85 fParent = nullptr;
86 fLeftChild = nullptr;
87 fRightChild = nullptr;
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//-------------------------------------------------------------------------
113RBBINode::~RBBINode() {
114 // printf("deleting node %8x serial %4d\n", this, this->fSerialNum);
115 delete fInputSet;
116 fInputSet = nullptr;
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 = nullptr;
128 delete fRightChild;
129 fRightChild = nullptr;
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//-------------------------------------------------------------------------
149RBBINode *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 != nullptr) {
162 if (fLeftChild != nullptr) {
163 n->fLeftChild = fLeftChild->cloneTree();
164 n->fLeftChild->fParent = n;
165 }
166 if (fRightChild != nullptr) {
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//-------------------------------------------------------------------------
195RBBINode *RBBINode::flattenVariables() {
196 if (fType == varRef) {
197 RBBINode *retNode = fLeftChild->cloneTree();
198 if (retNode != nullptr) {
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 != nullptr) {
207 fLeftChild = fLeftChild->flattenVariables();
208 fLeftChild->fParent = this;
209 }
210 if (fRightChild != nullptr) {
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//-------------------------------------------------------------------------
226void RBBINode::flattenSets() {
227 U_ASSERT(fType != setRef);
228
229 if (fLeftChild != nullptr) {
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 != nullptr) {
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//-------------------------------------------------------------------------
264void RBBINode::findNodes(UVector *dest, RBBINode::NodeType kind, UErrorCode &status) {
265 /* test for buffer overflows */
266 if (U_FAILURE(status)) {
267 return;
268 }
269 U_ASSERT(!dest->hasDeleter());
270 if (fType == kind) {
271 dest->addElement(this, status);
272 }
273 if (fLeftChild != nullptr) {
274 fLeftChild->findNodes(dest, kind, status);
275 }
276 if (fRightChild != nullptr) {
277 fRightChild->findNodes(dest, kind, status);
278 }
279}
280
281
282//-------------------------------------------------------------------------
283//
284// print. Print out a single node, for debugging.
285//
286//-------------------------------------------------------------------------
287#ifdef RBBI_DEBUG
288
289static int32_t serial(const RBBINode *node) {
290 return (node == nullptr? -1 : node->fSerialNum);
291}
292
293
294void RBBINode::printNode(const RBBINode *node) {
295 static const char * const nodeTypeNames[] = {
296 "setRef",
297 "uset",
298 "varRef",
299 "leafChar",
300 "lookAhead",
301 "tag",
302 "endMark",
303 "opStart",
304 "opCat",
305 "opOr",
306 "opStar",
307 "opPlus",
308 "opQuestion",
309 "opBreak",
310 "opReverse",
311 "opLParen"
312 };
313
314 if (node==nullptr) {
315 RBBIDebugPrintf("%10p", (void *)node);
316 } else {
317 RBBIDebugPrintf("%10p %5d %12s %c%c %5d %5d %5d %6d %d ",
318 (void *)node, node->fSerialNum, nodeTypeNames[node->fType],
319 node->fRuleRoot?'R':' ', node->fChainIn?'C':' ',
320 serial(node->fLeftChild), serial(node->fRightChild), serial(node->fParent),
321 node->fFirstPos, node->fVal);
322 if (node->fType == varRef) {
323 RBBI_DEBUG_printUnicodeString(node->fText);
324 }
325 }
326 RBBIDebugPrintf("\n");
327}
328#endif
329
330
331#ifdef RBBI_DEBUG
332U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth) {
333 RBBIDebugPrintf("%*s", minWidth, CStr(s)());
334}
335#endif
336
337
338//-------------------------------------------------------------------------
339//
340// print. Print out the tree of nodes rooted at "this"
341//
342//-------------------------------------------------------------------------
343#ifdef RBBI_DEBUG
344void RBBINode::printNodeHeader() {
345 RBBIDebugPrintf(" Address serial type LeftChild RightChild Parent position value\n");
346}
347
348void RBBINode::printTree(const RBBINode *node, UBool printHeading) {
349 if (printHeading) {
350 printNodeHeader();
351 }
352 printNode(node);
353 if (node != nullptr) {
354 // Only dump the definition under a variable reference if asked to.
355 // Unconditionally dump children of all other node types.
356 if (node->fType != varRef) {
357 if (node->fLeftChild != nullptr) {
358 printTree(node->fLeftChild, false);
359 }
360
361 if (node->fRightChild != nullptr) {
362 printTree(node->fRightChild, false);
363 }
364 }
365 }
366}
367#endif
368
369
370
371U_NAMESPACE_END
372
373#endif /* #if !UCONFIG_NO_BREAK_ITERATION */
374