Class: Heist::Runtime::Macro::Tree

Inherits:
Object
  • Object
show all
Defined in:
lib/runtime/callable/macro/tree.rb

Overview

Trees are used by instances of Matches to store expressions matched by macro patterns. Patterns may contain patterns that repeat (indicated by following the pattern with an ellipsis), and these repetitions may be nested. Tree instances store expressions in a set of nested arrays that match the repetition structure of the macro pattern being matched. See Matches for a fuller explanation.

Every Tree contains an array called @data that stores the expressions matched by a pattern variable, a variable @depth that stores the maximum repetition depth of the tree (a non-repeated pattern has depth zero), and an array @indexes which is used to maintain a list of array indexes that point to the current read position in the tree while a macro is being expanded. For example, taking the pattern from the Matches example:

(do ([variable init step ...] ...)
    (test expression ...)
    command ...)

Say we had the following expression (not entirely valid (do) syntax, but compatible with the above pattern):

(do ([x 6 (- x 1) (- acc 1)]
     [y 5]
     [acc 1 (* x acc)])
    ((zero? x) acc)
  (display x) (newline)
  (set! acc (* acc x)))

The resulting Matches object would contain the following data for the variable step:

"step" => [ [ (- x 1),
              (- acc 1)
            ],

            [],

            [ (* x acc)
            ]
          ]

That is, the outermost repetition [variable init step ...] occurs three times; the first appearance includes two matches for step ..., the second no matches and the third one match. With this data, an @indexes state of [0,0] would read (- x 1), a state of [0,1] would read (- acc 1), and [2,0] would read (* x acc); the latter instructing the Tree to get the third element of the root array, then the first element of that array to find the right value.

In practise, all Tree objects have an extra array around the data as presented above, to make the no-repetition case consistent with the representation for arbitrarily nested repetitions. That is, the methods in this class expect to read from an array in general, so the representation of a non-repeating pattern is just a single-element array to simplify the implementation of these methods in the general case. The first item in the @indexes array is always zero. We could remove this extra container and add a type check on @data when reading, but the current implementation seems more elegant for the moment.

Instance Method Summary collapse

Constructor Details

#initialize(name) ⇒ Tree

A Tree is initialized using the name of the pattern variable it is associated with (for debugging purposes).



70
71
72
73
74
 
# File 'lib/runtime/callable/macro/tree.rb', line 70

def initialize(name)
  @name  = name
  @data  = []
  @depth = 0
end

Instance Method Details

#<<(value) ⇒ Object

Pushes an expression onto the end of the final branch of the tree. All expressions should exist at the same depth (the tree’s maximum depth), seeing as the pattern should be followed by the same number of ellipses every time it is encountered.



90
91
92
93
 
# File 'lib/runtime/callable/macro/tree.rb', line 90

def <<(value)
  return if Cons::NULL == value
  tail(@depth) << value
end

#descend!(depth) ⇒ Object

Tells the receiving Tree that its pattern variable has been visited at a repetition depth of depth during pattern matching. This allocates a new empty array at an appropriate place in the tree to store matches (or groups of matches) if any are encountered. Calls to this method are also used to determine the tree’s maximum depth.



81
82
83
84
 
# File 'lib/runtime/callable/macro/tree.rb', line 81

def descend!(depth)
  tail(depth-1) << []
  @depth = depth if depth > @depth
end

#read ⇒ Object

Returns the expression at the current read position as instructed by the @indexes list.



97
98
99
 
# File 'lib/runtime/callable/macro/tree.rb', line 97

def read
  current(@depth)[indexes[@depth]]
end

#shift!(depth) ⇒ Object

Shifts the read position at the given depth along by one, by adding 1 to one of the values in @indexes. The macro expander calls this while walking a template to iterate over repetition branches.



104
105
106
107
 
# File 'lib/runtime/callable/macro/tree.rb', line 104

def shift!(depth)
  indexes[depth] += 1
  indexes[depth] = 0 if indexes[depth] >= current(depth).size
end

#size(depth) ⇒ Object

Returns the number of matches (or groups of matches) on the current read branch at the given depth. Returns zero if no branch exists at the given indexes.



112
113
114
 
# File 'lib/runtime/callable/macro/tree.rb', line 112

def size(depth)
  current(depth).size rescue 0
end