intl/icu/source/common/rbbinode.cpp@129ffea94266
intl/icu/source/common/rbbinode.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
1 /*
2 ***************************************************************************
3 * Copyright (C) 2002-2008 International Business Machines Corporation *
4 * and others. All rights reserved. *
5 ***************************************************************************
6 */
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 //
18 #include "unicode/utypes.h"
20 #if !UCONFIG_NO_BREAK_ITERATION
22 #include "unicode/unistr.h"
23 #include "unicode/uniset.h"
24 #include "unicode/uchar.h"
25 #include "unicode/parsepos.h"
26 #include "uvector.h"
28 #include "rbbirb.h"
29 #include "rbbinode.h"
31 #include "uassert.h"
34 U_NAMESPACE_BEGIN
36 #ifdef RBBI_DEBUG
37 static int gLastSerial = 0;
38 #endif
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;
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;}
71 }
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 }
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;
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;
117 default:
118 delete fLeftChild;
119 fLeftChild = NULL;
120 delete fRightChild;
121 fRightChild = NULL;
122 }
125 delete fFirstPosSet;
126 delete fLastPosSet;
127 delete fFollowPos;
129 }
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;
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 }
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 }
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 }
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);
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 }
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 }
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 }
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 };
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
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
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 }
346 if (fRightChild != NULL) {
347 fRightChild->printTree(FALSE);
348 }
349 }
350 }
351 }
352 #endif
356 U_NAMESPACE_END
358 #endif /* #if !UCONFIG_NO_BREAK_ITERATION */
