1/*
2***************************************************************************
3*   Copyright (C) 2002-2008 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
34U_NAMESPACE_BEGIN
35
36#ifdef RBBI_DEBUG
37static int  gLastSerial = 0;
38#endif
39
40
41//-------------------------------------------------------------------------
42//
43//    Constructor.   Just set the fields to reasonable default values.
44//
45//-------------------------------------------------------------------------
46RBBINode::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;
61
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;}
70
71}
72
73
74RBBINode::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}
94
95
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//-------------------------------------------------------------------------
105RBBINode::~RBBINode() {
106    // printf("deleting node %8x   serial %4d\n", this, this->fSerialNum);
107    delete fInputSet;
108    fInputSet = NULL;
109
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;
116
117    default:
118        delete        fLeftChild;
119        fLeftChild =   NULL;
120        delete        fRightChild;
121        fRightChild = NULL;
122    }
123
124
125    delete fFirstPosSet;
126    delete fLastPosSet;
127    delete fFollowPos;
128
129}
130
131
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//-------------------------------------------------------------------------
141RBBINode *RBBINode::cloneTree() {
142    RBBINode    *n;
143
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}
166
167
168
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//-------------------------------------------------------------------------
187RBBINode *RBBINode::flattenVariables() {
188    if (fType == varRef) {
189        RBBINode *retNode = fLeftChild->cloneTree();
190        delete this;
191        return retNode;
192    }
193
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}
204
205
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//-------------------------------------------------------------------------
214void RBBINode::flattenSets() {
215    U_ASSERT(fType != setRef);
216
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    }
229
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}
243
244
245
246//-------------------------------------------------------------------------
247//
248//   findNodes()     Locate all the nodes of the specified type, starting
249//                   at the specified root.
250//
251//-------------------------------------------------------------------------
252void   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}
267
268
269//-------------------------------------------------------------------------
270//
271//    print.         Print out a single node, for debugging.
272//
273//-------------------------------------------------------------------------
274#ifdef RBBI_DEBUG
275void 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    };
294
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
308
309
310#ifdef RBBI_DEBUG
311U_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
323
324
325//-------------------------------------------------------------------------
326//
327//    print.         Print out the tree of nodes rooted at "this"
328//
329//-------------------------------------------------------------------------
330#ifdef RBBI_DEBUG
331void 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            }
345
346            if (fRightChild != NULL) {
347                fRightChild->printTree(FALSE);
348            }
349        }
350    }
351}
352#endif
353
354
355
356U_NAMESPACE_END
357
358#endif /* #if !UCONFIG_NO_BREAK_ITERATION */
359