Home | History | Annotate | Download | only in antlr3
      1 #!/usr/bin/ruby
      2 # encoding: utf-8
      3 
      4 =begin LICENSE
      5 
      6 [The "BSD licence"]
      7 Copyright (c) 2009-2010 Kyle Yetter
      8 All rights reserved.
      9 
     10 Redistribution and use in source and binary forms, with or without
     11 modification, are permitted provided that the following conditions
     12 are met:
     13 
     14  1. Redistributions of source code must retain the above copyright
     15     notice, this list of conditions and the following disclaimer.
     16  2. Redistributions in binary form must reproduce the above copyright
     17     notice, this list of conditions and the following disclaimer in the
     18     documentation and/or other materials provided with the distribution.
     19  3. The name of the author may not be used to endorse or promote products
     20     derived from this software without specific prior written permission.
     21 
     22 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     23 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     24 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     25 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     27 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     28 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     29 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     30 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     31 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     32 
     33 =end
     34 
     35 require 'antlr3'
     36 
     37 module ANTLR3
     38   
     39 =begin rdoc ANTLR3::AST
     40 
     41 Name space containing all of the entities pertaining to tree construction and
     42 tree parsing.
     43 
     44 =end
     45 
     46 module AST
     47 
     48 autoload :Wizard, 'antlr3/tree/wizard'
     49 autoload :Visitor, 'antlr3/tree/visitor'
     50 
     51 ####################################################################################################
     52 ############################################ Tree Parser ###########################################
     53 ####################################################################################################
     54 
     55 =begin rdoc ANTLR3::AST::TreeParser
     56 
     57 = TreeParser
     58 
     59 TreeParser is the default base class of ANTLR-generated tree parsers. The class
     60 tailors the functionality provided by Recognizer to the task of tree-pattern
     61 recognition.
     62 
     63 == About Tree Parsers
     64 
     65 ANTLR generates three basic types of recognizers:
     66 * lexers
     67 * parsers
     68 * tree parsers
     69 
     70 Furthermore, it is capable of generating several different flavors of parser,
     71 including parsers that take token input and use it to build Abstract Syntax
     72 Trees (ASTs), tree structures that reflect the high-level syntactic and semantic
     73 structures defined by the language.
     74 
     75 You can take the information encapsulated by the AST and process it directly in
     76 a program. However, ANTLR also provides a means to create a recognizer which is
     77 capable of walking through the AST, verifying its structure and performing
     78 custom actions along the way -- tree parsers.
     79 
     80 Tree parsers are created from tree grammars. ANTLR-generated tree parsers
     81 closely mirror the general structure of regular parsers and lexers.
     82 
     83 For more in-depth coverage of the topic, check out the ANTLR documentation
     84 (http://www.antlr.org).
     85 
     86 == The Tree Parser API
     87 
     88 Like Parser, the class does not stray too far from the Recognizer API.
     89 Mainly, it customizes a few methods specifically to deal with tree nodes
     90 (instead of basic tokens), and adds some helper methods for working with trees.
     91 
     92 Like all ANTLR recognizers, tree parsers contained a shared state structure and
     93 an input stream, which should be a TreeNodeStream. ANTLR intends to keep its
     94 tree features flexible and customizable, and thus it does not make any
     95 assumptions about the class of the actual nodes it processes. One consequence of
     96 this flexibility is that tree parsers also require an extra tree adaptor object,
     97 the purpose of which is to provide a homogeneous interface for handling tree
     98 construction and analysis of your tree nodes.
     99 
    100 See Tree and TreeAdaptor for more information.
    101 
    102 =end
    103 
    104 class TreeParser < Recognizer
    105   def self.main( argv = ARGV, options = {} )
    106     if ::Hash === argv then argv, options = ARGV, argv end
    107     main = ANTLR3::Main::WalkerMain.new( self, options )
    108     block_given? ? yield( main ) : main.execute( argv )
    109   end
    110   
    111   def initialize( input, options = {} )
    112     super( options )
    113     @input = input
    114   end
    115   
    116   alias tree_node_stream input
    117   alias tree_node_stream= input=
    118   
    119   def source_name
    120     @input.source_name
    121   end
    122   
    123   def missing_symbol( error, expected_token_type, follow )
    124     name = token_name( expected_token_type ).to_s
    125     text = "<missing " << name << '>'
    126     tk = create_token do |t|
    127       t.text = text
    128       t.type = expected_token_type
    129     end
    130     return( CommonTree.new( tk ) )
    131   end
    132   
    133   def match_any( ignore = nil )
    134     @state.error_recovery = false
    135     
    136     look, adaptor = @input.look, @input.tree_adaptor
    137     if adaptor.child_count( look ) == 0
    138       @input.consume
    139       return
    140     end
    141     
    142     level = 0
    143     while type = @input.peek and type != EOF
    144       #token_type == EOF or ( token_type == UP && level == 0 )
    145       @input.consume
    146       case type
    147       when DOWN then level += 1
    148       when UP
    149         level -= 1
    150         level.zero? and break
    151       end
    152     end
    153   end
    154   
    155   def mismatch( input, type, follow = nil )
    156     raise MismatchedTreeNode.new( type, input )
    157   end
    158   
    159   def error_header( e )
    160     <<-END.strip!
    161     #{ grammar_file_name }: node from #{ 
    162       e.approximate_line_info? ? 'after ' : ''
    163     } line #{ e.line }:#{ e.column }
    164     END
    165   end
    166   
    167   def error_message( e )
    168     adaptor = e.input.adaptor
    169     e.token = adaptor.token( e.node )
    170     e.token ||= create_token do | tok |
    171       tok.type = adaptor.type_of( e.node )
    172       tok.text = adaptor.text_of( e.node )
    173     end
    174     return super( e )
    175   end
    176   
    177   def trace_in( rule_name, rule_index )
    178     super( rule_name, rule_index, @input.look )
    179   end
    180   
    181   def trace_out( rule_name, rule_index )
    182     super( rule_name, rule_index, @input.look )
    183   end
    184 end
    185 
    186 ####################################################################################################
    187 ############################################ Tree Nodes ############################################
    188 ####################################################################################################
    189 
    190 =begin rdoc ANTLR3::AST::Tree
    191 
    192 = ANTLR Abstract Syntax Trees
    193 
    194 As ANTLR is concerned, an Abstract Syntax Tree (AST) node is an object that
    195 wraps a token, a list of child trees, and some information about the collective
    196 source text embodied within the tree and its children.
    197 
    198 The Tree module, like the Token and Stream modules, emulates an abstract base
    199 class for AST classes; it specifies the attributes that are expected of basic
    200 tree nodes as well as the methods trees need to implement.
    201 
    202 == Terminology
    203 
    204 While much of this terminology is probably familiar to most developers, the
    205 following brief glossary is intended to clarify terminology used in code
    206 throughout the AST library:
    207 
    208 [payload] either a token value contained within a node or +nil+
    209 [flat list (nil tree)] a tree node without a token payload, but with more 
    210                        than one children -- functions like an array of 
    211                        tree nodes
    212 [root] a top-level tree node, i.e. a node that does not have a parent
    213 [leaf] a node that does not have any children
    214 [siblings] all other nodes sharing the same parent as some node
    215 [ancestors] the list of successive parents from a tree node to the root node
    216 [error node] a special node used to represent an erroneous series of tokens
    217              from an input stream
    218 
    219 =end
    220 
    221 module Tree
    222   
    223   #attr_accessor :parent
    224   attr_accessor :start_index
    225   attr_accessor :stop_index
    226   attr_accessor :child_index
    227   attr_reader :type
    228   attr_reader :text
    229   attr_reader :line
    230   attr_reader :column
    231   #attr_reader :children
    232   attr_reader :token
    233   
    234   
    235   def root?
    236     parent.nil?
    237   end
    238   alias detached? root?
    239   
    240   def root
    241     cursor = self
    242     until cursor.root?
    243       yield( parent_node = cursor.parent )
    244       cursor = parent_node
    245     end
    246     return( cursor )
    247   end
    248   
    249   #
    250   def leaf?
    251     children.nil? or children.empty?
    252   end
    253   
    254   def has_child?( node )
    255     children and children.include?( node )
    256   end
    257   
    258   def depth
    259     root? ? 0 : parent.depth + 1
    260   end
    261   
    262   def siblings
    263     root? and return []
    264     parent.children.reject { | c | c.equal?( self ) }
    265   end
    266   
    267   def each_ancestor
    268     block_given? or return( enum_for( :each_ancestor ) )
    269     cursor = self
    270     until cursor.root?
    271       yield( parent_node = cursor.parent )
    272       cursor = parent_node
    273     end
    274     return( self )
    275   end
    276   
    277   def ancestors
    278     each_ancestor.to_a
    279   end
    280   
    281   def walk
    282     block_given? or return( enum_for( :walk ) )
    283     stack = []
    284     cursor = self
    285     while true
    286       begin
    287         yield( cursor )
    288         stack.push( cursor.children.dup ) unless cursor.empty?
    289       rescue StopIteration
    290         # skips adding children to prune the node
    291       ensure
    292         break if stack.empty?
    293         cursor = stack.last.shift
    294         stack.pop if stack.last.empty?
    295       end
    296     end
    297     return self
    298   end
    299   
    300 end
    301 
    302 
    303 =begin rdoc ANTLR3::AST::BaseTree
    304 
    305 A base implementation of an Abstract Syntax Tree Node. It mainly defines the
    306 methods and attributes required to implement the parent-node-children
    307 relationship that characterize a tree; it does not provide any logic concerning
    308 a node's token <i>payload</i>.
    309 
    310 =end
    311 
    312 class BaseTree < ::Array
    313   attr_accessor :parent
    314   extend ClassMacros
    315   include Tree
    316   
    317   def initialize( node = nil )
    318     super()
    319     @parent = nil
    320     @child_index = 0
    321   end
    322   
    323   def children() self end
    324   
    325   alias child at
    326   alias child_count length
    327   
    328   def first_with_type( tree_type )
    329     find { | child | child.type == tree_type }
    330   end
    331   
    332   def add_child( child_tree )
    333     child_tree.nil? and return
    334     if child_tree.flat_list?
    335       self.equal?( child_tree.children ) and
    336         raise ArgumentError, "attempt to add child list to itself"
    337       child_tree.each_with_index do | child, index |
    338         child.parent = self
    339         child.child_index = length + index
    340       end
    341       concat( child_tree )
    342     else
    343       child_tree.child_index = length
    344       child_tree.parent = self
    345       self << child_tree
    346     end
    347     return( self )
    348   end
    349   
    350   def detach
    351     @parent = nil
    352     @child_index = -1
    353     return( self )
    354   end
    355   
    356   alias add_children concat
    357   alias each_child each
    358   
    359   def set_child( index, tree )
    360     return if tree.nil?
    361     tree.flat_list? and raise ArgumentError, "Can't set single child to a list"
    362     tree.parent = self
    363     tree.child_index = index
    364     self[ index ] = tree
    365   end
    366   
    367   def delete_child( index )
    368     killed = delete_at( index ) and freshen( index )
    369     return killed
    370   end
    371 
    372   def replace_children( start, stop, new_tree )
    373     start >= length or stop >= length and
    374       raise IndexError, ( <<-END ).gsub!( /^\s+\| /,'' )
    375       | indices span beyond the number of children:
    376       |  children.length = #{ length }
    377       |  start = #{ start_index.inspect }
    378       |  stop  = #{ stop_index.inspect }
    379       END
    380     new_children = new_tree.flat_list? ? new_tree : [ new_tree ]
    381     self[ start .. stop ] = new_children
    382     freshen( start_index )
    383     return self
    384   end
    385   
    386   def flat_list?
    387     false
    388   end
    389   
    390   def freshen( offset = 0 )
    391     for i in offset ... length
    392       node = self[ i ]
    393       node.child_index = i
    394       node.parent = self
    395     end
    396   end
    397   
    398   def sanity_check( parent = nil, i = -1 )
    399     parent == @parent or
    400       raise TreeInconsistency.failed_parent_check!( parent, @parent )
    401     i == @child_index or
    402       raise TreeInconsistency.failed_index_check!( i, @child_index )
    403     each_with_index do | child, index |
    404       child.sanity_check( self, index )
    405     end
    406   end
    407   
    408   def inspect
    409     empty? and return to_s
    410     buffer = ''
    411     buffer << '(' << to_s << ' ' unless flat_list?
    412     buffer << map { | c | c.inspect }.join( ' ' )
    413     buffer << ')' unless flat_list?
    414     return( buffer )
    415   end
    416   
    417   def walk
    418     block_given? or return( enum_for( :walk ) )
    419     stack = []
    420     cursor = self
    421     while true
    422       begin
    423         yield( cursor )
    424         stack.push( Array[ *cursor ] ) unless cursor.empty?
    425       rescue StopIteration
    426         # skips adding children to prune the node
    427       ensure
    428         break if stack.empty?
    429         cursor = stack.last.shift
    430         stack.pop if stack.last.empty?
    431       end
    432     end
    433     return self
    434   end
    435   
    436   def prune
    437     raise StopIteration
    438   end
    439   
    440   abstract :to_s
    441   #protected :sanity_check, :freshen
    442   
    443   def root?() @parent.nil? end
    444   alias leaf? empty?
    445 end
    446 
    447 
    448 =begin rdoc ANTLR3::AST::CommonTree
    449 
    450 The default Tree class implementation used by ANTLR tree-related code.
    451 
    452 A CommonTree object is a tree node that wraps a token <i>payload</i> (or a +nil+
    453 value) and contains zero or more child tree nodes. Additionally, it tracks
    454 information about the range of data collectively spanned by the tree node: 
    455 
    456 * the token stream start and stop indexes of tokens contained throughout 
    457   the tree 
    458 * that start and stop positions of the character input stream from which 
    459   the tokens were defined
    460 
    461 Tracking this information simplifies tasks like extracting a block of code or
    462 rewriting the input stream. However, depending on the purpose of the
    463 application, building trees with all of this extra information may be
    464 unnecessary. In such a case, a more bare-bones tree class could be written
    465 (optionally using the BaseTree class or the Token module). Define a customized
    466 TreeAdaptor class to handle tree construction and manipulation for the
    467 customized node class, and recognizers will be able to build, rewrite, and parse
    468 the customized lighter-weight trees.
    469 
    470 =end
    471 
    472 class CommonTree < BaseTree
    473   def initialize( payload = nil )
    474     super()
    475     @start_index = -1
    476     @stop_index = -1
    477     @child_index = -1
    478     case payload
    479     when CommonTree then   # copy-constructor style init
    480       @token       = payload.token
    481       @start_index = payload.start_index
    482       @stop_index  = payload.stop_index
    483     when nil, Token then @token = payload
    484     else raise ArgumentError,
    485       "Invalid argument type: %s (%p)" % [ payload.class, payload ]
    486     end
    487   end
    488   
    489   def initialize_copy( orig )
    490     super
    491     clear
    492     @parent = nil
    493   end
    494   
    495   def copy_node
    496     return self.class.new( @token )
    497   end
    498   
    499   def flat_list?
    500     @token.nil?
    501   end
    502   
    503   def type
    504     @token ? @token.type : 0
    505   end
    506   
    507   def text
    508     @token.text rescue nil
    509   end
    510   
    511   def line
    512     if @token.nil? or @token.line == 0
    513       return ( empty? ? 0 : first.line )
    514     end
    515     return @token.line
    516   end
    517   
    518   def column
    519     if @token.nil? or @token.column == -1
    520       return( empty? ? 0 : first.column )
    521     end
    522     return @token.column
    523   end
    524   
    525   def start_index
    526     @start_index == -1 and @token and return @token.index
    527     return @start_index
    528   end
    529   
    530   def stop_index
    531     @stop_index == -1 and @token and return @token.index
    532     return @stop_index
    533   end
    534   
    535   alias token_start_index= start_index=
    536   alias token_stop_index= stop_index=
    537   alias token_start_index start_index
    538   alias token_stop_index stop_index
    539   
    540   def name
    541     @token.name rescue 'INVALID'
    542   end
    543   
    544   def token_range
    545     unknown_boundaries? and infer_boundaries
    546     @start_index .. @stop_index
    547   end
    548   
    549   def source_range
    550     unknown_boundaries? and infer_boundaries
    551     tokens = map do | node |
    552       tk = node.token and tk.index >= 0 ? tk : nil
    553     end
    554     tokens.compact!
    555     first, last = tokens.minmax_by { |t| t.index }
    556     first.start .. last.stop
    557   end
    558   
    559   def infer_boundaries
    560     if empty? and @start_index < 0 || @stop_index < 0
    561       @start_index = @stop_index = @token.index rescue -1
    562       return
    563     end
    564     for child in self do child.infer_boundaries end
    565     return if @start_index >= 0 and @stop_index >= 0
    566     
    567     @start_index = first.start_index
    568     @stop_index  = last.stop_index
    569     return nil
    570   end
    571   
    572   def unknown_boundaries?
    573     @start_index < 0 or @stop_index < 0
    574   end
    575   
    576   def to_s
    577     flat_list? ? 'nil' : @token.text.to_s
    578   end
    579   
    580   def pretty_print( printer )
    581     text = @token ? @token.text : 'nil'
    582     text =~ /\s+/ and
    583       text = text.dump
    584     
    585     if empty?
    586       printer.text( text )
    587     else
    588       endpoints = @token ? [ "(#{ text }", ')' ] : [ '', '' ]
    589       printer.group( 1, *endpoints ) do
    590         for child in self
    591           printer.breakable
    592           printer.pp( child )
    593         end
    594       end
    595     end
    596   end
    597   
    598 end
    599 
    600 =begin rdoc ANTLR3::AST::CommonErrorNode
    601 
    602 Represents a series of erroneous tokens from a token stream input
    603 
    604 =end
    605 
    606 class CommonErrorNode < CommonTree
    607   include ANTLR3::Error
    608   include ANTLR3::Constants
    609   
    610   attr_accessor :input, :start, :stop, :error
    611   
    612   def initialize( input, start, stop, error )
    613     super( nil )
    614     stop = start if stop.nil? or
    615       ( stop.token_index < start.token_index and stop.type != EOF )
    616     @input = input
    617     @start = start
    618     @stop = stop
    619     @error = error
    620   end
    621   
    622   def flat_list?
    623     return false
    624   end
    625   
    626   def type
    627     INVALID_TOKEN_TYPE
    628   end
    629   
    630   def text
    631     case @start
    632     when Token
    633       i = @start.token_index
    634       j = ( @stop.type == EOF ) ? @input.size : @stop.token_index
    635       @input.to_s( i, j )            # <- the bad text
    636     when Tree
    637       @input.to_s( @start, @stop )   # <- the bad text
    638     else
    639       "<unknown>"
    640     end
    641   end
    642   
    643   def to_s
    644     case @error
    645     when MissingToken
    646       "<missing type: #{ @error.missing_type }>"
    647     when UnwantedToken
    648       "<extraneous: #{ @error.token.inspect }, resync = #{ text }>"
    649     when MismatchedToken
    650       "<mismatched token: #{ @error.token.inspect }, resync = #{ text }>"
    651     when NoViableAlternative
    652       "<unexpected: #{ @error.token.inspect }, resync = #{ text }>"
    653     else "<error: #{ text }>"
    654     end
    655   end
    656   
    657 end
    658 
    659 Constants::INVALID_NODE = CommonTree.new( ANTLR3::INVALID_TOKEN )
    660 
    661 ####################################################################################################
    662 ########################################### Tree Adaptors ##########################################
    663 ####################################################################################################
    664 
    665 =begin rdoc ANTLR3::AST::TreeAdaptor
    666 
    667 Since a tree can be represented by a multitude of formats, ANTLR's tree-related
    668 code mandates the use of Tree Adaptor objects to build and manipulate any actual
    669 trees. Using an adaptor object permits a single recognizer to work with any
    670 number of different tree structures without adding rigid interface requirements
    671 on customized tree structures. For example, if you want to represent trees using
    672 simple arrays of arrays, you just need to design an appropriate tree adaptor and
    673 provide it to the parser.
    674 
    675 Tree adaptors are tasked with:
    676 
    677 * copying and creating tree nodes and tokens
    678 * defining parent-child relationships between nodes
    679 * cleaning up / normalizing a full tree structure after construction
    680 * reading and writing the attributes ANTLR expects of tree nodes
    681 * providing node access and iteration
    682 
    683 =end
    684 
    685 module TreeAdaptor
    686   include TokenFactory
    687   include Constants
    688   include Error
    689   
    690   def add_child( tree, child )
    691     tree.add_child( child ) if tree and child
    692   end
    693   
    694   def child_count( tree )
    695     tree.child_count
    696   end
    697   
    698   def child_index( tree )
    699     tree.child_index rescue 0
    700   end
    701   
    702   def child_of( tree, index )
    703     tree.nil? ? nil : tree.child( index )
    704   end
    705   
    706   def copy_node( tree_node )
    707     tree_node and tree_node.dup
    708   end
    709 
    710   def copy_tree( tree, parent = nil )
    711     tree or return nil
    712     new_tree = copy_node( tree )
    713     set_child_index( new_tree, child_index( tree ) )
    714     set_parent( new_tree, parent )
    715     each_child( tree ) do | child |
    716       new_sub_tree = copy_tree( child, new_tree )
    717       add_child( new_tree, new_sub_tree )
    718     end
    719     return new_tree
    720   end
    721   
    722   def delete_child( tree, index )
    723     tree.delete_child( index )
    724   end
    725   
    726   
    727   def each_child( tree )
    728     block_given? or return enum_for( :each_child, tree )
    729     for i in 0 ... child_count( tree )
    730       yield( child_of( tree, i ) )
    731     end
    732     return tree
    733   end
    734   
    735   def each_ancestor( tree, include_tree = true )
    736     block_given? or return enum_for( :each_ancestor, tree, include_tree )
    737     if include_tree
    738       begin yield( tree ) end while tree = parent_of( tree )
    739     else
    740       while tree = parent_of( tree ) do yield( tree ) end
    741     end
    742   end
    743   
    744   def flat_list?( tree )
    745     tree.flat_list?
    746   end
    747   
    748   def empty?( tree )
    749     child_count( tree ).zero?
    750   end
    751   
    752   def parent( tree )
    753     tree.parent
    754   end
    755   
    756   def replace_children( parent, start, stop, replacement )
    757     parent and parent.replace_children( start, stop, replacement )
    758   end
    759 
    760   def rule_post_processing( root )
    761     if root and root.flat_list?
    762       case root.child_count
    763       when 0 then root = nil
    764       when 1
    765         root = root.child( 0 ).detach
    766       end
    767     end
    768     return root
    769   end
    770   
    771   def set_child_index( tree, index )
    772     tree.child_index = index
    773   end
    774 
    775   def set_parent( tree, parent )
    776     tree.parent = parent
    777   end
    778   
    779   def set_token_boundaries( tree, start_token = nil, stop_token = nil )
    780     return unless tree
    781     start = stop = 0
    782     start_token and start = start_token.index
    783     stop_token  and stop  = stop_token.index
    784     tree.start_index = start
    785     tree.stop_index = stop
    786     return tree
    787   end
    788 
    789   def text_of( tree )
    790     tree.text rescue nil
    791   end
    792 
    793   def token( tree )
    794     CommonTree === tree ? tree.token : nil
    795   end
    796 
    797   def token_start_index( tree )
    798     tree ? tree.token_start_index : -1
    799   end
    800   
    801   def token_stop_index( tree )
    802     tree ? tree.token_stop_index : -1
    803   end
    804   
    805   def type_name( tree )
    806     tree.name rescue 'INVALID'
    807   end
    808   
    809   def type_of( tree )
    810     tree.type rescue INVALID_TOKEN_TYPE
    811   end
    812   
    813   def unique_id( node )
    814     node.hash
    815   end
    816   
    817 end
    818 
    819 =begin rdoc ANTLR3::AST::CommonTreeAdaptor
    820 
    821 The default tree adaptor used by ANTLR-generated tree code. It, of course,
    822 builds and manipulates CommonTree nodes.
    823 
    824 =end
    825 
    826 class CommonTreeAdaptor
    827   extend ClassMacros
    828   include TreeAdaptor
    829   include ANTLR3::Constants
    830   
    831   def initialize( token_class = ANTLR3::CommonToken )
    832     @token_class = token_class
    833   end
    834   
    835   def create_flat_list
    836     return create_with_payload( nil )
    837   end
    838   alias create_flat_list! create_flat_list
    839   
    840   def become_root( new_root, old_root )
    841     new_root = create( new_root ) if new_root.is_a?( Token )
    842     old_root or return( new_root )
    843     
    844     new_root = create_with_payload( new_root ) unless CommonTree === new_root
    845     if new_root.flat_list?
    846       count = new_root.child_count
    847       if count == 1
    848         new_root = new_root.child( 0 )
    849       elsif count > 1
    850         raise TreeInconsistency.multiple_roots!
    851       end
    852     end
    853     
    854     new_root.add_child( old_root )
    855     return new_root
    856   end
    857   
    858   def create_from_token( token_type, from_token, text = nil )
    859     from_token = from_token.dup
    860     from_token.type = token_type
    861     from_token.text = text.to_s if text
    862     tree = create_with_payload( from_token )
    863     return tree
    864   end
    865   
    866   def create_from_type( token_type, text )
    867     from_token = create_token( token_type, DEFAULT_CHANNEL, text )
    868     create_with_payload( from_token )
    869   end
    870   
    871   def create_error_node( input, start, stop, exc )
    872     CommonErrorNode.new( input, start, stop, exc )
    873   end
    874   
    875   def create_with_payload( payload )
    876     return CommonTree.new( payload )
    877   end
    878 
    879   def create( *args )
    880     n = args.length
    881     if n == 1 and args.first.is_a?( Token ) then create_with_payload( args[ 0 ] )
    882     elsif n == 2 and Integer === args.first and String === args[ 1 ]
    883       create_from_type( *args )
    884     elsif n >= 2 and Integer === args.first
    885       create_from_token( *args )
    886     else
    887       sig = args.map { |f| f.class }.join( ', ' )
    888       raise TypeError, "No create method with this signature found: (#{ sig })"
    889     end
    890   end
    891   
    892   creation_methods = %w(
    893     create_from_token create_from_type
    894     create_error_node create_with_payload
    895     create
    896   )
    897   
    898   for method_name in creation_methods
    899     bang_method = method_name + '!'
    900     alias_method( bang_method, method_name )
    901     deprecate( bang_method, "use method ##{ method_name } instead" )
    902   end
    903   
    904   def rule_post_processing( root )
    905     if root and root.flat_list?
    906       if root.empty? then root = nil
    907       elsif root.child_count == 1 then root = root.first.detach
    908       end
    909     end
    910     return root
    911   end
    912   
    913   def empty?( tree )
    914     tree.empty?
    915   end
    916   
    917   def each_child( tree )
    918     block_given? or return enum_for( :each_child, tree )
    919     tree.each do | child |
    920       yield( child )
    921     end
    922   end
    923   
    924 end
    925 
    926 
    927 ####################################################################################################
    928 ########################################### Tree Streams ###########################################
    929 ####################################################################################################
    930 
    931 =begin rdoc ANTLR3::AST::TreeNodeStream
    932 
    933 TreeNodeStreams flatten two-dimensional tree structures into one-dimensional
    934 sequences. They preserve the two-dimensional structure of the tree by inserting
    935 special +UP+ and +DOWN+ nodes.
    936 
    937 Consider a hypothetical tree:
    938 
    939   [A]
    940    +--[B]
    941    |   +--[C]
    942    |   `--[D]
    943    `--[E]
    944        `--[F]
    945 
    946 A tree node stream would serialize the tree into the following sequence:
    947 
    948   A DOWN B DOWN C D UP E DOWN F UP UP EOF
    949 
    950 Other than serializing a tree into a sequence of nodes, a tree node stream
    951 operates similarly to other streams. They are commonly used by tree parsers as
    952 the main form of input. #peek, like token streams, returns the type of the token
    953 of the next node. #look returns the next full tree node.
    954 
    955 =end
    956 
    957 module TreeNodeStream
    958   extend ClassMacros
    959   include Stream
    960   include Constants
    961   
    962   abstract :at
    963   abstract :look
    964   abstract :tree_source
    965   abstract :token_stream
    966   abstract :tree_adaptor
    967   abstract :unique_navigation_nodes=
    968   abstract :to_s
    969   abstract :replace_children
    970 end
    971 
    972 =begin rdoc ANTLR3::AST::CommonTreeNodeStream
    973 
    974 An implementation of TreeNodeStream tailed for streams based on CommonTree
    975 objects. CommonTreeNodeStreams are the default input streams for tree parsers.
    976 
    977 =end
    978 
    979 class CommonTreeNodeStream
    980   include TreeNodeStream
    981   
    982   attr_accessor :token_stream
    983   attr_reader :adaptor, :position
    984   
    985   def initialize( *args )
    986     options = args.last.is_a?( ::Hash ) ? args.pop : {}
    987     case n = args.length
    988     when 1
    989       @root = args.first
    990       @token_stream = @adaptor = @nodes = @down = @up = @eof = nil
    991     when 2
    992       @adaptor, @root = args
    993       @token_stream = @nodes = @down = @up = @eof = nil
    994     when 3
    995       parent, start, stop = *args
    996       @adaptor = parent.adaptor
    997       @root = parent.root
    998       @nodes = parent.nodes[ start ... stop ]
    999       @down = parent.down
   1000       @up = parent.up
   1001       @eof = parent.eof
   1002       @token_stream = parent.token_stream
   1003     when 0
   1004       raise ArgumentError, "wrong number of arguments (0 for 1)"
   1005     else raise ArgumentError, "wrong number of arguments (#{ n } for 3)"
   1006     end
   1007     @adaptor ||= options.fetch( :adaptor ) { CommonTreeAdaptor.new }
   1008     @token_stream ||= options[ :token_stream ]
   1009     @down  ||= options.fetch( :down ) { @adaptor.create_from_type( DOWN, 'DOWN' ) }
   1010     @up    ||= options.fetch( :up )   { @adaptor.create_from_type( UP, 'UP' ) }
   1011     @eof   ||= options.fetch( :eof )  { @adaptor.create_from_type( EOF, 'EOF' ) }
   1012     @nodes ||= []
   1013     
   1014     @unique_navigation_nodes = options.fetch( :unique_navigation_nodes, false )
   1015     @position = -1
   1016     @last_marker = nil
   1017     @calls = []
   1018   end
   1019   
   1020   def fill_buffer( tree = @root )
   1021     @nodes << tree unless nil_tree = @adaptor.flat_list?( tree )
   1022     unless @adaptor.empty?( tree )
   1023       add_navigation_node( DOWN ) unless nil_tree
   1024       @adaptor.each_child( tree ) { | c | fill_buffer( c ) }
   1025       add_navigation_node( UP ) unless nil_tree
   1026     end
   1027     @position = 0 if tree == @root
   1028     return( self )
   1029   end
   1030   
   1031   def node_index( node )
   1032     @position == -1 and fill_buffer
   1033     return @nodes.index( node )
   1034   end
   1035   
   1036   def add_navigation_node( type )
   1037     navigation_node =
   1038       case type
   1039       when DOWN
   1040         has_unique_navigation_nodes? ? @adaptor.create_from_type( DOWN, 'DOWN' ) : @down
   1041       else
   1042         has_unique_navigation_nodes? ? @adaptor.create_from_type( UP, 'UP' ) : @up
   1043       end
   1044     @nodes << navigation_node
   1045   end
   1046   
   1047   def at( index )
   1048     @position == -1 and fill_buffer
   1049     @nodes.at( index )
   1050   end
   1051   
   1052   def look( k = 1 )
   1053     @position == -1 and fill_buffer
   1054     k == 0 and return nil
   1055     k < 0 and return self.look_behind( -k )
   1056     
   1057     absolute = @position + k - 1
   1058     @nodes.fetch( absolute, @eof )
   1059   end
   1060   
   1061   def current_symbol
   1062     look
   1063   end
   1064   
   1065   def look_behind( k = 1 )
   1066     k == 0 and return nil
   1067     absolute = @position - k
   1068     return( absolute < 0 ? nil : @nodes.fetch( absolute, @eof ) )
   1069   end
   1070   
   1071   def tree_source
   1072     @root
   1073   end
   1074   
   1075   def source_name
   1076     self.token_stream.source_name
   1077   end
   1078   
   1079   def tree_adaptor
   1080     @adaptor
   1081   end
   1082   
   1083   def has_unique_navigation_nodes?
   1084     return @unique_navigation_nodes
   1085   end
   1086   attr_writer :unique_navigation_nodes
   1087   
   1088   def consume
   1089     @position == -1 and fill_buffer
   1090     node = @nodes.fetch( @position, @eof )
   1091     @position += 1
   1092     return( node )
   1093   end
   1094   
   1095   def peek( i = 1 )
   1096     @adaptor.type_of look( i )
   1097   end
   1098   
   1099   alias >> peek
   1100   def <<( k )
   1101     self >> -k
   1102   end
   1103   
   1104   def mark
   1105     @position == -1 and fill_buffer
   1106     @last_marker = @position
   1107     return @last_marker
   1108   end
   1109   
   1110   def release( marker = nil )
   1111     # do nothing?
   1112   end
   1113   
   1114   alias index position
   1115   
   1116   def rewind( marker = @last_marker, release = true )
   1117     seek( marker )
   1118   end
   1119 
   1120   def seek( index )
   1121     @position == -1 and fill_buffer
   1122     @position = index
   1123   end
   1124   
   1125   def push( index )
   1126     @calls << @position
   1127     seek( index )
   1128   end
   1129   
   1130   def pop
   1131     pos = @calls.pop and seek( pos )
   1132     return pos
   1133   end
   1134   
   1135   def reset
   1136     @position = 0
   1137     @last_marker = 0
   1138     @calls = []
   1139   end
   1140   
   1141   def replace_children( parent, start, stop, replacement )
   1142     parent and @adaptor.replace_children( parent, start, stop, replacement )
   1143   end
   1144   
   1145   def size
   1146     @position == -1 and fill_buffer
   1147     return @nodes.length
   1148   end
   1149   
   1150   def inspect
   1151     @position == -1 and fill_buffer
   1152     @nodes.map { |nd| @adaptor.type_name( nd ) }.join( ' ' )
   1153   end
   1154   
   1155   def extract_text( start = nil, stop = nil )
   1156     start.nil? || stop.nil? and return nil
   1157     @position == -1 and fill_buffer
   1158     
   1159     if @token_stream
   1160       from = @adaptor.token_start_index( start )
   1161       to = 
   1162         case @adaptor.type_of( stop )
   1163         when UP then @adaptor.token_stop_index( start )
   1164         when EOF then to = @nodes.length - 2
   1165         else @adaptor.token_stop_index( stop )
   1166         end
   1167       return @token_stream.extract_text( from, to )
   1168     end
   1169     
   1170     buffer = ''
   1171     for node in @nodes
   1172       if node == start ... node == stop  # <-- hey look, it's the flip flop operator
   1173         buffer << @adaptor.text_of( node ) #|| ' ' << @adaptor.type_of( node ).to_s )
   1174       end
   1175     end
   1176     return( buffer )
   1177   end
   1178   
   1179   def each
   1180     @position == -1 and fill_buffer
   1181     block_given? or return enum_for( :each )
   1182     for node in @nodes do yield( node ) end
   1183     self
   1184   end
   1185   
   1186   include Enumerable
   1187   
   1188   def to_a
   1189     return @nodes.dup
   1190   end
   1191   
   1192   def extract_text( start = nil, stop = nil )
   1193     @position == -1 and fill_buffer
   1194     start ||= @nodes.first
   1195     stop  ||= @nodes.last
   1196     
   1197     if @token_stream
   1198       case @adaptor.type_of( stop )
   1199       when UP
   1200         stop_index = @adaptor.token_stop_index( start )
   1201       when EOF
   1202         return extract_text( start, @nodes[ - 2 ] )
   1203       else
   1204         stop_index = @adaptor.token_stop_index( stop )
   1205       end
   1206       
   1207       start_index = @adaptor.token_start_index( start )
   1208       return @token_stream.extract_text( start_index, stop_index )
   1209     else
   1210       start_index = @nodes.index( start ) || @nodes.length
   1211       stop_index  = @nodes.index( stop )  || @nodes.length
   1212       return( 
   1213         @nodes[ start_index .. stop_index ].map do | n |
   1214           @adaptor.text_of( n ) or " " + @adaptor.type_of( n ).to_s
   1215         end.join( '' )
   1216       )
   1217     end
   1218   end
   1219   
   1220   alias to_s extract_text
   1221   
   1222 #private
   1223 #  
   1224 #  def linear_node_index( node )
   1225 #    @position == -1 and fill_buffer
   1226 #    @nodes.each_with_index do |n, i|
   1227 #      node == n and return(i)
   1228 #    end
   1229 #    return -1
   1230 #  end
   1231 end
   1232 
   1233 =begin rdoc ANTLR3::AST::RewriteRuleElementStream
   1234 
   1235 Special type of stream that is used internally by tree-building and tree-
   1236 rewriting parsers.
   1237 
   1238 =end
   1239 
   1240 class RewriteRuleElementStream # < Array
   1241   extend ClassMacros
   1242   include Error
   1243   
   1244   def initialize( adaptor, element_description, elements = nil )
   1245     @cursor = 0
   1246     @single_element = nil
   1247     @elements = nil
   1248     @dirty = false
   1249     @element_description = element_description
   1250     @adaptor = adaptor
   1251     if elements.instance_of?( Array )
   1252       @elements = elements
   1253     else
   1254       add( elements )
   1255     end
   1256   end
   1257   
   1258   def reset
   1259     @cursor = 0
   1260     @dirty = true
   1261   end
   1262   
   1263   def add( el )
   1264     return( nil ) unless el
   1265     case
   1266     when ! el then return( nil )
   1267     when @elements then @elements << el
   1268     when @single_element.nil? then @single_element = el
   1269     else
   1270       @elements = [ @single_element, el ]
   1271       @single_element = nil
   1272       return( @elements )
   1273     end
   1274   end
   1275   
   1276   def next_tree
   1277     if @dirty or @cursor >= length && length == 1
   1278       return dup( __next__ )
   1279     end
   1280     __next__
   1281   end
   1282   
   1283   abstract :dup
   1284   
   1285   def to_tree( el )
   1286     return el
   1287   end
   1288   
   1289   def has_next?
   1290     return( @single_element && @cursor < 1 or
   1291            @elements && @cursor < @elements.length )
   1292   end
   1293   
   1294   def size
   1295     @single_element and return 1
   1296     @elements and return @elements.length
   1297     return 0
   1298   end
   1299   
   1300   alias length size
   1301   
   1302 private
   1303   
   1304   def __next__
   1305     l = length
   1306     case
   1307     when l.zero?
   1308       raise Error::RewriteEmptyStream.new( @element_description )
   1309     when @cursor >= l
   1310       l == 1 and return to_tree( @single_element )
   1311       raise RewriteCardinalityError.new( @element_description )
   1312     when @single_element
   1313       @cursor += 1
   1314       return( to_tree( @single_element ) )
   1315     else
   1316       out = to_tree( @elements.at( @cursor ) )
   1317       @cursor += 1
   1318       return( out )
   1319     end
   1320   end
   1321 end
   1322 
   1323 
   1324 =begin rdoc ANTLR3::AST::RewriteRuleTokenStream
   1325 
   1326 Special type of stream that is used internally by tree-building and tree-
   1327 rewriting parsers.
   1328 
   1329 =end
   1330 class RewriteRuleTokenStream < RewriteRuleElementStream
   1331   def next_node
   1332     return @adaptor.create_with_payload( __next__ )
   1333   end
   1334   
   1335   alias :next :__next__
   1336   public :next
   1337   
   1338   def dup( el )
   1339     raise TypeError, "dup can't be called for a token stream"
   1340   end
   1341 end
   1342 
   1343 =begin rdoc ANTLR3::AST::RewriteRuleSubtreeStream
   1344 
   1345 Special type of stream that is used internally by tree-building and tree-
   1346 rewriting parsers.
   1347 
   1348 =end
   1349 
   1350 class RewriteRuleSubtreeStream < RewriteRuleElementStream
   1351   def next_node
   1352     if @dirty or @cursor >= length && length == 1
   1353       return @adaptor.copy_node( __next__ )
   1354     end
   1355     return __next__
   1356   end
   1357   
   1358   def dup( el )
   1359     @adaptor.copy_tree( el )
   1360   end
   1361 end
   1362 
   1363 =begin rdoc ANTLR3::AST::RewriteRuleNodeStream
   1364 
   1365 Special type of stream that is used internally by tree-building and tree-
   1366 rewriting parsers.
   1367 
   1368 =end
   1369 
   1370 class RewriteRuleNodeStream < RewriteRuleElementStream
   1371   alias next_node __next__
   1372   public :next_node
   1373   def to_tree( el )
   1374     @adaptor.copy_node( el )
   1375   end
   1376   
   1377   def dup( el )
   1378     raise TypeError, "dup can't be called for a node stream"
   1379   end
   1380 end
   1381 end
   1382 
   1383 include AST
   1384 end
   1385