pd.if.org Git - pccts/blob - h/ASTBase.cpp

   1 /* Abstract syntax tree manipulation functions
   2  *
   3  * SOFTWARE RIGHTS
   4  *
   5  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
   6  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
   7  * company may do whatever they wish with source code distributed with
   8  * PCCTS or the code generated by PCCTS, including the incorporation of
   9  * PCCTS, or its output, into commerical software.
  10  *
  11  * We encourage users to develop software with PCCTS.  However, we do ask
  12  * that credit is given to us for developing PCCTS.  By "credit",
  13  * we mean that if you incorporate our source code into one of your
  14  * programs (commercial product, research project, or otherwise) that you
  15  * acknowledge this fact somewhere in the documentation, research report,
  16  * etc...  If you like PCCTS and have developed a nice tool with the
  17  * output, please mention that you developed it using PCCTS.  In
  18  * addition, we ask that this header remain intact in our source code.
  19  * As long as these guidelines are kept, we expect to continue enhancing
  20  * this system and expect to make other tools available as they are
  21  * completed.
  22  *
  23  * ANTLR 1.33
  24  * Terence Parr
  25  * Parr Research Corporation
  26  * with Purdue University and AHPCRC, University of Minnesota
  27  * 1989-1995
  28  */
  29 #include <stdio.h>
  30 #include <stdarg.h>
  31
  32 #define ANTLR_SUPPORT_CODE
  33
  34 #include "ASTBase.h"
  35
  36 /* ensure that tree manipulation variables are current after a rule
  37  * reference
  38  */
  39 void
  40 ASTBase::link(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  41 {
  42         if ( *_sibling == NULL ) return;
  43         if ( *_root == NULL ) *_root = *_sibling;
  44         else if ( *_root != *_sibling ) (*_root)->_down = *_sibling;
  45         if ( *_tail==NULL ) *_tail = *_sibling;
  46         while ( (*_tail)->_right != NULL ) *_tail = (*_tail)->_right;
  47 }
  48
  49 /* add a child node to the current sibling list */
  50 void
  51 ASTBase::subchild(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  52 {
  53         if ( *_tail != NULL ) (*_tail)->_right = this;
  54         else {
  55                 *_sibling = this;
  56                 if ( *_root != NULL ) (*_root)->_down = *_sibling;
  57         }
  58         *_tail = this;
  59         if ( *_root == NULL ) *_root = *_sibling;
  60 }
  61
  62 /* make a new AST node.  Make the newly-created
  63  * node the root for the current sibling list.  If a root node already
  64  * exists, make the newly-created node the root of the current root.
  65  */
  66 void
  67 ASTBase::subroot(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  68 {
  69         if ( *_root != NULL )
  70                 if ( (*_root)->_down == *_sibling ) *_sibling = *_tail = *_root;
  71         *_root = this;
  72         (*_root)->_down = *_sibling;
  73 }
  74
  75 /* Apply preorder_action(), etc.. to root then each sibling */
  76 void
  77 ASTBase::preorder()
  78 {
  79         ASTBase *tree = this;
  80
  81         while ( tree!= NULL )
  82         {
  83                 if ( tree->_down != NULL ) preorder_before_action();
  84                 tree->preorder_action();
  85                 if ( tree->_down!=NULL )
  86                 {
  87                         tree->_down->preorder();
  88                         preorder_after_action();
  89                 }
  90                 tree = tree->_right;
  91         }
  92 }
  93
  94 /* free all AST nodes in tree; apply func to each before freeing */
  95 void
  96 ASTBase::destroy()
  97 {
  98    ASTBase* tree = this;
  99    while (tree) {
 100       if (tree->_down) tree->_down->destroy();
 101
 102       ASTBase* cur = tree;
 103       tree = tree->_right;
 104       delete cur;
 105    }
 106 }
 107
 108 /* build a tree (root child1 child2 ... NULL)
 109  * If root is NULL, simply make the children siblings and return ptr
 110  * to 1st sibling (child1).  If root is not single node, return NULL.
 111  *
 112  * Siblings that are actually siblins lists themselves are handled
 113  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
 114  * in the tree ( NULL A B C D ).
 115  *
 116  * Requires at least two parameters with the last one being NULL.  If
 117  * both are NULL, return NULL.
 118  */
 119 ASTBase *
 120 ASTBase::tmake(ASTBase *root, ...)
 121 {
 122         va_list ap;
 123         register ASTBase *child, *sibling=NULL, *tail, *w;
 124
 125         va_start(ap, root);
 126
 127         if ( root != NULL )
 128                 if ( root->_down != NULL ) return NULL;
 129         child = va_arg(ap, ASTBase *);
 130         while ( child != NULL )
 131         {
 132                 for (w=child; w->_right!=NULL; w=w->_right) {;} /* find end of child */
 133                 if ( sibling == NULL ) {sibling = child; tail = w;}
 134                 else {tail->_right = child; tail = w;}
 135                 child = va_arg(ap, ASTBase *);
 136         }
 137         if ( root==NULL ) root = sibling;
 138         else root->_down = sibling;
 139         va_end(ap);
 140         return root;
 141 }
 142
 143 /* tree duplicate */
 144 // forgot to check for NULL this (TJP July 23,1995)
 145 ASTBase *
 146 ASTBase::dup()
 147 {
 148         ASTBase *u, *t=this;
 149
 150         if ( t == NULL ) return NULL;
 151 /*
 152         u = new ASTBase;
 153         *u = *t;
 154 */
 155         u = (ASTBase *)this->shallowCopy();
 156         if ( t->_right!=NULL ) u->_right = t->_right->dup();
 157         else u->_right = NULL;
 158         if ( t->_down!=NULL ) u->_down = t->_down->dup();
 159         else u->_down = NULL;
 160         return u;
 161 }
 162
 163 /* tree duplicate */
 164 ASTBase *
 165 ASTDoublyLinkedBase::dup()
 166 {
 167         ASTDoublyLinkedBase *u, *t=this;
 168
 169         if ( t == NULL ) return NULL;
 170 /*
 171         u = new ASTDoublyLinkedBase;
 172         *u = *t;
 173 */
 174         u = (ASTDoublyLinkedBase *)this->shallowCopy();
 175         u->_up = NULL;          /* set by calling invocation */
 176         u->_left = NULL;
 177         u->_right = t->_right->dup();
 178         u->_down = t->_down->dup();
 179         if ( u->_right!=NULL ) ((ASTDoublyLinkedBase *)u->_right)->_left = u;
 180         if ( u->_down!=NULL ) ((ASTDoublyLinkedBase *)u->_down)->_up = u;
 181         return u;
 182 }
 183
 184 /*
 185  * Set the 'up', and 'left' pointers of all nodes in 't'.
 186  * Initial call is double_link(your_tree, NULL, NULL).
 187  */
 188 void
 189 ASTDoublyLinkedBase::double_link(ASTBase *left, ASTBase *up)
 190 {
 191     ASTDoublyLinkedBase *t = this;
 192
 193     t->_left = (ASTDoublyLinkedBase *) left;
 194     t->_up = (ASTDoublyLinkedBase *) up;
 195     if (t->_down != NULL)
 196                 ((ASTDoublyLinkedBase *)t->_down)->double_link(NULL, t);
 197     if (t->_right != NULL)
 198                 ((ASTDoublyLinkedBase *)t->_right)->double_link(t, up);
 199 }
 200