compilers/tge/TGE/Tree.pir

   1 # Copyright (C) 2005-2008, Parrot Foundation.
   2 # $Id$
   3
   4 =head1 NAME
   5
   6 TGE::Tree - The top-level node of every tree.
   7
   8 =head1 DESCRIPTION
   9
  10 A TGE::Tree is the core object at the center of every tree transformation. You
  11 can think of it as something like a PGE::Match object. The first step of
  12 applying every tree grammar is to create a TGE::Tree object and wrap it around
  13 the tree being transformed. The TGE::Tree object handles result caching for
  14 particular transform rules on particular nodes, maintains connections between
  15 particular nodes and the transforms that can apply to those nodes, and will
  16 eventually handle indexing for faster tree searches.
  17
  18 =cut
  19
  20 .namespace [ 'TGE'; 'Tree' ]
  21
  22 .sub "__onload" :load
  23     # define the class
  24     .local pmc base
  25     newclass base, ['TGE';'Tree']
  26     addattribute base, "cell"    # a hash for storing values of tree nodes
  27     addattribute base, "visit"   # arrays of rules that apply to each node type
  28     addattribute base, "data"    # the original unmodified tree
  29     addattribute base, "grammar" # the current grammar object
  30     addattribute base, "agid"    # a hash of node address => node id
  31     .return ()
  32 .end
  33
  34 =head2 new
  35
  36 Returns a simple initialized TGE::Tree object. Doesn't accept any
  37 constructor parameters.
  38
  39 =cut
  40
  41 .sub init :vtable :method
  42     $P0 = new 'Hash'
  43     $P1 = new 'Hash'
  44     $P2 = new 'Undef'
  45     setattribute self, "cell", $P0
  46     setattribute self, "visit", $P1
  47     setattribute self, "data", $P2
  48     $P3 = new 'AddrRegistry'
  49     setattribute self, "agid", $P3
  50 .end
  51
  52 # Call all visitors for a given node
  53 .sub _scan_node :method
  54     .param pmc node
  55     .param pmc name     :optional
  56     .param int got_name :opt_flag
  57     .local string type
  58
  59     # If the user passed in a special name, look up visit actions for that one,
  60     # otherwise look them up for the type name of the node.
  61     if got_name goto name_from_arg
  62     type = typeof node
  63     goto name_set
  64 name_from_arg:
  65     type = name
  66 name_set:
  67
  68     # Iterate over the elements of the visit hash for the given type
  69     .local pmc actions
  70     .local int index
  71     .local pmc currule
  72     $P2 = getattribute self, 'visit'
  73     $I2 = exists $P2[type]
  74     unless $I2 goto end_loop
  75     actions = $P2[type]
  76     index = actions
  77 loop:
  78     dec index
  79     if index < 0 goto end_loop
  80     currule = actions[index]
  81     self.'_install_action'(node, currule)
  82     goto loop
  83 end_loop:
  84     .return()
  85 .end
  86
  87 =head2 get
  88
  89   value = Tree.get('attrname')
  90
  91 Fetches the value of a particular attribute from the root node of the
  92 grammar.
  93
  94   value = Tree.get('attrname', node)
  95   value = Tree.get('attrname', node, 'type')
  96
  97 Fetches the value of a particular attribute from the node passed in.
  98 When working with a tree where the nodes don't know their type (PGE
  99 match objects, for example), you must also tell C<get> the type of the
 100 node.
 101
 102 =cut
 103
 104 .sub get :method
 105     .param pmc name
 106     .param pmc node     :optional
 107     .param int got_node :opt_flag
 108     .param pmc type     :optional
 109     .param int got_type :opt_flag
 110
 111     # If no node was passed in, use top level node.
 112     if got_node goto node_exists
 113     node = getattribute self, 'data'
 114 node_exists:
 115
 116     .local pmc id
 117     id = self.'_lookup_id'(node)
 118
 119     .local pmc cell
 120     $P1 = getattribute self, "cell"
 121     # First check to see if cell exists
 122     $P2 = $P1[name]
 123     $I1 = exists $P1[name]
 124     if $I1 goto name_hash_exists
 125     $P2 = new 'Hash'
 126     $P1[name] = $P2
 127     goto scan_name
 128 name_hash_exists:
 129     $I0 = exists $P2[id]
 130     cell = $P2[id]
 131     if $I0 goto eval_cell
 132 scan_name:
 133     if got_type goto scan_with_type
 134     self.'_scan_node'(node)
 135     goto done_scan
 136 scan_with_type:
 137     self.'_scan_node'(node,type)
 138 done_scan:
 139     # Second check to see if _scan_node defined the cell
 140     cell = $P2[id]
 141     $I0 = exists $P2[id]
 142     if $I0 goto eval_cell
 143     # Cell still not defined, grammar is unresolvable.
 144     print "Cannot find the attribute '"
 145     print name
 146     print "' ("
 147     unless got_type goto class_is_type
 148     print type
 149     print " on node "
 150   class_is_type:
 151     $S1 = typeof node
 152     print $S1
 153     print ") that you asked for.\n"
 154     .return ()
 155 eval_cell:
 156     $P3 = self.'_eval_cell'(cell,node)
 157     .return($P3)
 158 .end
 159
 160 # Evaluate a thunk.
 161 .sub _eval_cell :method
 162     .param pmc cell
 163     .param pmc node
 164     .local pmc value
 165     $I0 = cell['thunk']
 166     if $I0 goto run_thunk_action
 167     goto return_value
 168 run_thunk_action:
 169     .local pmc grammar
 170     grammar = getattribute self, 'grammar'
 171     # the stored node (parent for inherited attributes, self for
 172     # synthesized attributes)
 173     $P1 = cell['node']
 174     $S0 = cell['action']
 175     # the action is a method on the grammar object
 176     value = grammar.$S0(self, $P1)
 177     cell['value'] = value
 178     cell['thunk'] = 0
 179
 180 return_value:
 181     value = cell['value']
 182     .return (value)
 183 .end
 184
 185 # Install a thunk in a particular attribute slot of a particular object.
 186 .sub _install_action :method
 187     .param pmc node
 188     .param pmc rule
 189
 190     # Grab the 'cell' hash from the grammar object.
 191     .local pmc cell_hash
 192     cell_hash = getattribute self, 'cell'
 193
 194     # Retrieve the hash within 'cell' keyed by the name of the attribute.
 195     # If the hash doesn't exist, create it.
 196     .local pmc name
 197     .local pmc cellattr
 198     name = getattribute rule, "name"
 199     cellattr = cell_hash[name]
 200     $I1 = exists cell_hash[name]
 201     if $I1 goto name_hash_exists
 202     cellattr = new 'Hash'
 203     cell_hash[name] = cellattr
 204 name_hash_exists:
 205
 206     # Decide which node to operate on. If 'parent' was '.', then operate on
 207     # the node passed in, otherwise, operate on a child node named in
 208     # 'parent'.
 209     .local pmc id
 210     .local pmc parent
 211     parent = getattribute rule, 'parent'
 212     if parent == '.' goto use_parent_id
 213     .local pmc child_node
 214     child_node = self.'_lookup_child'(node, parent)
 215     id = self.'_lookup_id'(child_node)
 216     goto use_child_id
 217 use_parent_id:
 218     id = self.'_lookup_id'(node)
 219 use_child_id:
 220
 221     # Check that the entry (by attribute name and id) in the "cell" hash
 222     # doesn't already exist (the grammar should only create one entry
 223     # for each unique node id).
 224     $P3 = cellattr[id]
 225     $I2 = exists cellattr[id]
 226     if $I2 goto error_defined
 227
 228     # Create the entry in the "cell" tree that stores the action to
 229     # calculate the value of a given attribute in a given node. Also
 230     # store an empty space for the value after it has been calculated,
 231     # and a flag ("thunk") noting whether the action has been run.
 232     .local pmc thunk
 233     thunk = new 'Hash'
 234     thunk['thunk'] = 1
 235     $P4 = getattribute rule, "action"
 236     thunk['action'] = $P4
 237     $P5 = new 'Undef'
 238     thunk['value'] = $P5
 239     thunk['node'] = node
 240     cellattr[id] = thunk
 241
 242     .return()
 243 error_defined:
 244     print "Nonlinear attribute: you have two or more ways to "
 245     print "assign a value to the attribute '"
 246     print name
 247     print "' on node type '"
 248     $S1 = typeof node
 249     print $S1
 250     print "' with rule name '"
 251     $P4 = getattribute rule, "action"
 252     print $P4
 253     print "' near grammar line "
 254     $P7 = getattribute rule, "line"
 255     print $P7
 256     print "\n"
 257     end
 258 .end
 259
 260 # This determines the semantics of .attr.
 261 .sub _lookup_child :method
 262     .param pmc node
 263     .param pmc name
 264     $S0 = name
 265     $P1 = getattribute node, $S0
 266     .return($P1)
 267 .end
 268
 269 .sub _lookup_id :method
 270     .param pmc node
 271
 272     .local pmc id_hash
 273     .local int id
 274     # Get the id of the node, or if it doesn't exist, generate one.
 275     id_hash = getattribute self, 'agid'
 276     id = id_hash[node]
 277     if id goto got_id          # 0 means, doesn't exist
 278     id = elements id_hash
 279     inc id
 280     id_hash[node] = id
 281 got_id:
 282     .return (id)
 283 .end
 284
 285 # Local Variables:
 286 #   mode: pir
 287 #   fill-column: 100
 288 # End:
 289 # vim: expandtab shiftwidth=4 ft=pir: