1#!/usr/bin/ruby
2# encoding: utf-8
3
4=begin LICENSE
5
6[The "BSD licence"]
7Copyright (c) 2009-2010 Kyle Yetter
8All rights reserved.
9
10Redistribution and use in source and binary forms, with or without
11modification, are permitted provided that the following conditions
12are 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
22THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33=end
34
35require 'antlr3'
36
37module ANTLR3
38
39=begin rdoc ANTLR3::AST
40
41Name space containing all of the entities pertaining to tree construction and
42tree parsing.
43
44=end
45
46module AST
47
48autoload :Wizard, 'antlr3/tree/wizard'
49autoload :Visitor, 'antlr3/tree/visitor'
50
51####################################################################################################
52############################################ Tree Parser ###########################################
53####################################################################################################
54
55=begin rdoc ANTLR3::AST::TreeParser
56
57= TreeParser
58
59TreeParser is the default base class of ANTLR-generated tree parsers. The class
60tailors the functionality provided by Recognizer to the task of tree-pattern
61recognition.
62
63== About Tree Parsers
64
65ANTLR generates three basic types of recognizers:
66* lexers
67* parsers
68* tree parsers
69
70Furthermore, it is capable of generating several different flavors of parser,
71including parsers that take token input and use it to build Abstract Syntax
72Trees (ASTs), tree structures that reflect the high-level syntactic and semantic
73structures defined by the language.
74
75You can take the information encapsulated by the AST and process it directly in
76a program. However, ANTLR also provides a means to create a recognizer which is
77capable of walking through the AST, verifying its structure and performing
78custom actions along the way -- tree parsers.
79
80Tree parsers are created from tree grammars. ANTLR-generated tree parsers
81closely mirror the general structure of regular parsers and lexers.
82
83For more in-depth coverage of the topic, check out the ANTLR documentation
84(http://www.antlr.org).
85
86== The Tree Parser API
87
88Like Parser, the class does not stray too far from the Recognizer API.
89Mainly, 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
92Like all ANTLR recognizers, tree parsers contained a shared state structure and
93an input stream, which should be a TreeNodeStream. ANTLR intends to keep its
94tree features flexible and customizable, and thus it does not make any
95assumptions about the class of the actual nodes it processes. One consequence of
96this flexibility is that tree parsers also require an extra tree adaptor object,
97the purpose of which is to provide a homogeneous interface for handling tree
98construction and analysis of your tree nodes.
99
100See Tree and TreeAdaptor for more information.
101
102=end
103
104class 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
184end
185
186####################################################################################################
187############################################ Tree Nodes ############################################
188####################################################################################################
189
190=begin rdoc ANTLR3::AST::Tree
191
192= ANTLR Abstract Syntax Trees
193
194As ANTLR is concerned, an Abstract Syntax Tree (AST) node is an object that
195wraps a token, a list of child trees, and some information about the collective
196source text embodied within the tree and its children.
197
198The Tree module, like the Token and Stream modules, emulates an abstract base
199class for AST classes; it specifies the attributes that are expected of basic
200tree nodes as well as the methods trees need to implement.
201
202== Terminology
203
204While much of this terminology is probably familiar to most developers, the
205following brief glossary is intended to clarify terminology used in code
206throughout 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
221module 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
300end
301
302
303=begin rdoc ANTLR3::AST::BaseTree
304
305A base implementation of an Abstract Syntax Tree Node. It mainly defines the
306methods and attributes required to implement the parent-node-children
307relationship that characterize a tree; it does not provide any logic concerning
308a node's token <i>payload</i>.
309
310=end
311
312class 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?
445end
446
447
448=begin rdoc ANTLR3::AST::CommonTree
449
450The default Tree class implementation used by ANTLR tree-related code.
451
452A CommonTree object is a tree node that wraps a token <i>payload</i> (or a +nil+
453value) and contains zero or more child tree nodes. Additionally, it tracks
454information 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
461Tracking this information simplifies tasks like extracting a block of code or
462rewriting the input stream. However, depending on the purpose of the
463application, building trees with all of this extra information may be
464unnecessary. 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
466TreeAdaptor class to handle tree construction and manipulation for the
467customized node class, and recognizers will be able to build, rewrite, and parse
468the customized lighter-weight trees.
469
470=end
471
472class 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
598end
599
600=begin rdoc ANTLR3::AST::CommonErrorNode
601
602Represents a series of erroneous tokens from a token stream input
603
604=end
605
606class 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
657end
658
659Constants::INVALID_NODE = CommonTree.new( ANTLR3::INVALID_TOKEN )
660
661####################################################################################################
662########################################### Tree Adaptors ##########################################
663####################################################################################################
664
665=begin rdoc ANTLR3::AST::TreeAdaptor
666
667Since a tree can be represented by a multitude of formats, ANTLR's tree-related
668code mandates the use of Tree Adaptor objects to build and manipulate any actual
669trees. Using an adaptor object permits a single recognizer to work with any
670number of different tree structures without adding rigid interface requirements
671on customized tree structures. For example, if you want to represent trees using
672simple arrays of arrays, you just need to design an appropriate tree adaptor and
673provide it to the parser.
674
675Tree 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
685module 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
817end
818
819=begin rdoc ANTLR3::AST::CommonTreeAdaptor
820
821The default tree adaptor used by ANTLR-generated tree code. It, of course,
822builds and manipulates CommonTree nodes.
823
824=end
825
826class 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
924end
925
926
927####################################################################################################
928########################################### Tree Streams ###########################################
929####################################################################################################
930
931=begin rdoc ANTLR3::AST::TreeNodeStream
932
933TreeNodeStreams flatten two-dimensional tree structures into one-dimensional
934sequences. They preserve the two-dimensional structure of the tree by inserting
935special +UP+ and +DOWN+ nodes.
936
937Consider a hypothetical tree:
938
939  [A]
940   +--[B]
941   |   +--[C]
942   |   `--[D]
943   `--[E]
944       `--[F]
945
946A 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
950Other than serializing a tree into a sequence of nodes, a tree node stream
951operates similarly to other streams. They are commonly used by tree parsers as
952the main form of input. #peek, like token streams, returns the type of the token
953of the next node. #look returns the next full tree node.
954
955=end
956
957module 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
970end
971
972=begin rdoc ANTLR3::AST::CommonTreeNodeStream
973
974An implementation of TreeNodeStream tailed for streams based on CommonTree
975objects. CommonTreeNodeStreams are the default input streams for tree parsers.
976
977=end
978
979class 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
1231end
1232
1233=begin rdoc ANTLR3::AST::RewriteRuleElementStream
1234
1235Special type of stream that is used internally by tree-building and tree-
1236rewriting parsers.
1237
1238=end
1239
1240class 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
1302private
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
1321end
1322
1323
1324=begin rdoc ANTLR3::AST::RewriteRuleTokenStream
1325
1326Special type of stream that is used internally by tree-building and tree-
1327rewriting parsers.
1328
1329=end
1330class 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
1341end
1342
1343=begin rdoc ANTLR3::AST::RewriteRuleSubtreeStream
1344
1345Special type of stream that is used internally by tree-building and tree-
1346rewriting parsers.
1347
1348=end
1349
1350class 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
1361end
1362
1363=begin rdoc ANTLR3::AST::RewriteRuleNodeStream
1364
1365Special type of stream that is used internally by tree-building and tree-
1366rewriting parsers.
1367
1368=end
1369
1370class 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
1380end
1381end
1382
1383include AST
1384end
1385