These validation files for REXML need to be included in the main branch.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@6596 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

3 files changed, 720 insertions, 0 deletions

diff --git a/lib/rexml/validation/relaxng.rb b/lib/rexml/validation/relaxng.rb
new file mode 100644
index 0000000000..969f51bc95
--- /dev/null
+++ b/lib/rexml/validation/relaxng.rb
@@ -0,0 +1,559 @@
+require "rexml/validation/validation"
+require "rexml/parsers/baseparser"
+
+module REXML
+  module Validation
+    # Implemented:
+    # * empty
+    # * element
+    # * attribute
+    # * text
+    # * optional
+    # * choice
+    # * oneOrMore
+    # * zeroOrMore
+    # * group
+    # * value
+    # * interleave
+    # * mixed
+    # * ref
+    # * grammar
+    # * start
+    # * define
+    #
+    # Not implemented:
+    # * data
+    # * param
+    # * include
+    # * externalRef
+    # * notAllowed
+    # * anyName
+    # * nsName
+    # * except
+    # * name
+    class RelaxNG
+      include Validator
+
+      INFINITY = 1.0 / 0.0
+      EMPTY = Event.new( nil )
+      TEXT = [:start_element, "text"]
+      attr_accessor :current
+      attr_accessor :count
+      attr_reader :references
+
+      # FIXME: Namespaces
+      def initialize source
+        parser = REXML::Parsers::BaseParser.new( source )
+
+        @count = 0
+        @references = {}
+        @root = @current = Sequence.new(self)
+        @root.previous = true
+        states = [ @current ]
+        begin
+          event = parser.pull
+          case event[0]
+          when :start_element
+            case event[1]
+            when "empty"
+            when "element", "attribute", "text", "value"
+              states[-1] << event
+            when "optional"
+              states << Optional.new( self )
+              states[-2] << states[-1]
+            when "choice"
+              states << Choice.new( self )
+              states[-2] << states[-1]
+            when "oneOrMore"
+              states << OneOrMore.new( self )
+              states[-2] << states[-1]
+            when "zeroOrMore"
+              states << ZeroOrMore.new( self )
+              states[-2] << states[-1]
+            when "group"
+              states << Sequence.new( self )
+              states[-2] << states[-1]
+            when "interleave"
+              states << Interleave.new( self )
+              states[-2] << states[-1]
+            when "mixed"
+              states << Interleave.new( self )
+              states[-2] << states[-1]
+              states[-1] << TEXT 
+            when "define"
+              states << [ event[2]["name"] ]
+            when "ref"
+              states[-1] << Ref.new( event[2]["name"] )
+            when "anyName"
+              states << AnyName.new( self )
+              states[-2] << states[-1]
+            when "nsName"
+            when "except"
+            when "name"
+            when "data"
+            when "param"
+            when "include"
+            when "grammar"
+            when "start"
+            when "externalRef"
+            when "notAllowed"
+            end
+          when :end_element
+            case event[1]
+            when "element", "attribute"
+              states[-1] << event
+            when "zeroOrMore", "oneOrMore", "choice", "optional", 
+              "interleave", "group", "mixed"
+              states.pop
+            when "define"
+              ref = states.pop
+              @references[ ref.shift ] = ref
+            #when "empty"
+            end
+          when :end_document
+            states[-1] << event
+          when :text
+            states[-1] << event
+          end
+        end while event[0] != :end_document
+      end
+
+      def receive event
+        validate( event )
+      end
+    end
+
+    class State
+      def initialize( context )
+        @previous = []
+        @events = []
+        @current = 0
+        @count = context.count += 1
+        @references = context.references
+        @value = false
+      end
+
+      def reset
+        return if @current == 0
+        @current = 0
+        @events.each {|s| s.reset if s.kind_of? State }
+      end
+
+      def previous=( previous ) 
+        @previous << previous
+      end
+
+      def next( event )
+        #print "In next with #{event.inspect}.  "
+        #puts "Next (#@current) is #{@events[@current]}"
+        #p @previous
+        return @previous.pop.next( event ) if @events[@current].nil?
+        expand_ref_in( @events, @current ) if @events[@current].class == Ref
+        if ( @events[@current].kind_of? State )
+          @current += 1
+          @events[@current-1].previous = self
+          return @events[@current-1].next( event )
+        end
+        #puts "Current isn't a state"
+        if ( @events[@current].matches?(event) )
+          @current += 1
+          if @events[@current].nil?
+            #puts "#{inspect[0,5]} 1RETURNING #{@previous.inspect[0,5]}"
+            return @previous.pop
+          elsif @events[@current].kind_of? State
+            @current += 1
+            #puts "#{inspect[0,5]} 2RETURNING (#{@current-1}) #{@events[@current-1].inspect[0,5]}; on return, next is #{@events[@current]}"
+            @events[@current-1].previous = self
+            return @events[@current-1]
+          else
+            #puts "#{inspect[0,5]} RETURNING self w/ next(#@current) = #{@events[@current]}"
+            return self
+          end
+        else
+          return nil
+        end
+      end
+
+      def to_s
+        # Abbreviated:
+        self.class.name =~ /(?:::)(\w)\w+$/
+        # Full:
+        #self.class.name =~ /(?:::)(\w+)$/
+        "#$1.#@count"
+      end
+
+      def inspect
+        "< #{to_s} #{@events.collect{|e| 
+          pre = e == @events[@current] ? '#' : ''
+          pre + e.inspect unless self == e
+        }.join(', ')} >"
+      end
+
+      def expected
+        return [@events[@current]]
+      end
+
+      def <<( event )
+        add_event_to_arry( @events, event )
+      end
+
+
+      protected
+      def expand_ref_in( arry, ind )
+        new_events = []
+        @references[ arry[ind].to_s ].each{ |evt| 
+          add_event_to_arry(new_events,evt)
+        }
+        arry[ind,1] = new_events
+      end
+
+      def add_event_to_arry( arry, evt ) 
+        evt = generate_event( evt )
+        if evt.kind_of? String 
+          arry[-1].event_arg = evt if arry[-1].kind_of? Event and @value
+          @value = false
+        else
+          arry << evt
+        end
+      end
+
+      def generate_event( event )
+        return event if event.kind_of? State or event.class == Ref
+        evt = nil
+        arg = nil
+        case event[0]
+        when :start_element
+          case event[1]
+          when "element"
+            evt = :start_element
+            arg = event[2]["name"]
+          when "attribute"
+            evt = :start_attribute
+            arg = event[2]["name"]
+          when "text"
+            evt = :text
+          when "value"
+            evt = :text
+            @value = true
+          end
+        when :text
+          return event[1]
+        when :end_document
+          return Event.new( event[0] )
+        else # then :end_element
+          case event[1]
+          when "element"
+            evt = :end_element
+          when "attribute"
+            evt = :end_attribute
+          end
+        end
+        return Event.new( evt, arg )
+      end
+    end
+
+
+    class Sequence < State
+      def matches?(event)
+        @events[@current].matches?( event )
+      end
+    end
+
+
+    class Optional < State
+      def next( event )
+        if @current == 0
+          rv = super
+          return rv if rv
+          @prior = @previous.pop
+          return @prior.next( event )
+        end
+        super
+      end
+
+      def matches?(event)
+        @events[@current].matches?(event) || 
+        (@current == 0 and @previous[-1].matches?(event))
+      end
+
+      def expected
+        return [ @prior.expected, @events[0] ].flatten if @current == 0
+        return [@events[@current]]
+      end
+    end
+
+
+    class ZeroOrMore < Optional
+      def next( event )
+        expand_ref_in( @events, @current ) if @events[@current].class == Ref
+        if ( @events[@current].matches?(event) )
+          @current += 1
+          if @events[@current].nil?
+            @current = 0
+            return self
+          elsif @events[@current].kind_of? State
+            @current += 1
+            @events[@current-1].previous = self
+            return @events[@current-1]
+          else
+            return self
+          end
+        else
+          @prior = @previous.pop
+          return @prior.next( event ) if @current == 0
+          return nil
+        end
+      end
+
+      def expected
+        return [ @prior.expected, @events[0] ].flatten if @current == 0
+        return [@events[@current]]
+      end
+    end
+
+
+    class OneOrMore < State
+      def initialize context
+        super
+        @ord = 0
+      end
+
+      def reset
+        super 
+        @ord = 0
+      end
+
+      def next( event )
+        expand_ref_in( @events, @current ) if @events[@current].class == Ref
+        if ( @events[@current].matches?(event) )
+          @current += 1
+          @ord += 1
+          if @events[@current].nil?
+            @current = 0
+            return self
+          elsif @events[@current].kind_of? State
+            @current += 1
+            @events[@current-1].previous = self
+            return @events[@current-1]
+          else
+            return self
+          end
+        else
+          return @previous.pop.next( event ) if @current == 0 and @ord > 0
+          return nil
+        end
+      end
+
+      def matches?( event )
+        @events[@current].matches?(event) || 
+        (@current == 0 and @ord > 0 and @previous[-1].matches?(event))
+      end
+
+      def expected
+        if @current == 0 and @ord > 0
+          return [@previous[-1].expected, @events[0]].flatten
+        else
+          return [@events[@current]]
+        end
+      end
+    end
+
+
+    class Choice < State
+      def initialize context
+        super
+        @choices = []
+      end
+
+      def reset
+        super
+        @events = []
+        @choices.each { |c| c.each { |s| s.reset if s.kind_of? State } }
+      end
+
+      def <<( event )
+        add_event_to_arry( @choices, event )
+      end
+
+      def next( event )
+        # Make the choice if we haven't
+        if @events.size == 0
+          c = 0 ; max = @choices.size
+          while c < max
+            if @choices[c][0].class == Ref
+              expand_ref_in( @choices[c], 0 )
+              @choices += @choices[c]
+              @choices.delete( @choices[c] )
+              max -= 1
+            else
+              c += 1
+            end
+          end
+          @events = @choices.find { |evt| evt[0].matches? event }
+          # Remove the references
+          # Find the events
+        end
+        #puts "In next with #{event.inspect}."
+        #puts "events is #{@events.inspect}"
+        unless @events
+          @events = []
+          return nil
+        end
+        #puts "current = #@current"
+        super
+      end
+
+      def matches?( event )
+        return @events[@current].matches?( event ) if @events.size > 0
+        !@choices.find{|evt| evt[0].matches?(event)}.nil?
+      end
+
+      def expected
+        #puts "IN CHOICE EXPECTED"
+        #puts "EVENTS = #{@events.inspect}"
+        return [@events[@current]] if @events.size > 0
+        return @choices.collect do |x| 
+          if x[0].kind_of? State
+            x[0].expected
+          else
+            x[0]
+          end
+        end.flatten
+      end
+
+      def inspect
+        "< #{to_s} #{@choices.collect{|e| e.collect{|f|f.to_s}.join(', ')}.join(' or ')} >"
+      end
+
+      protected
+      def add_event_to_arry( arry, evt ) 
+        if evt.kind_of? State or evt.class == Ref
+          arry << [evt]
+        elsif evt[0] == :text 
+         if arry[-1] and
+            arry[-1][-1].kind_of?( Event ) and 
+            arry[-1][-1].event_type == :text and @value
+
+            arry[-1][-1].event_arg = evt[1]
+            @value = false
+          end
+        else
+          arry << [] if evt[0] == :start_element
+          arry[-1] << generate_event( evt )
+        end
+      end
+    end
+
+
+    class Interleave < Choice
+      def initialize context
+        super
+        @choice = 0
+      end
+
+      def reset
+        @choice = 0
+      end
+
+      def next_current( event )
+        # Expand references
+        c = 0 ; max = @choices.size
+        while c < max
+          if @choices[c][0].class == Ref
+            expand_ref_in( @choices[c], 0 )
+            @choices += @choices[c]
+            @choices.delete( @choices[c] )
+            max -= 1
+          else
+            c += 1
+          end
+        end
+        @events = @choices[@choice..-1].find { |evt| evt[0].matches? event }
+        @current = 0
+        if @events
+          # reorder the choices
+          old = @choices[@choice]
+          idx = @choices.index( @events )
+          @choices[@choice] = @events
+          @choices[idx] = old
+          @choice += 1
+        end
+        
+       #puts "In next with #{event.inspect}."
+       #puts "events is #{@events.inspect}"
+        @events = [] unless @events
+      end
+
+
+      def next( event )
+        # Find the next series
+        next_current(event) unless @events[@current]
+        return nil unless @events[@current]
+
+        expand_ref_in( @events, @current ) if @events[@current].class == Ref 
+       #puts "In next with #{event.inspect}."
+       #puts "Next (#@current) is #{@events[@current]}"
+        if ( @events[@current].kind_of? State )
+          @current += 1
+          @events[@current-1].previous = self
+          return @events[@current-1].next( event )
+        end
+       #puts "Current isn't a state"
+        return @previous.pop.next( event ) if @events[@current].nil?
+        if ( @events[@current].matches?(event) )
+          @current += 1
+          if @events[@current].nil?
+           #puts "#{inspect[0,5]} 1RETURNING self" unless @choices[@choice].nil?
+            return self unless @choices[@choice].nil?
+           #puts "#{inspect[0,5]} 1RETURNING #{@previous[-1].inspect[0,5]}"
+            return @previous.pop
+          elsif @events[@current].kind_of? State
+            @current += 1
+           #puts "#{inspect[0,5]} 2RETURNING (#{@current-1}) #{@events[@current-1].inspect[0,5]}; on return, next is #{@events[@current]}"
+            @events[@current-1].previous = self
+            return @events[@current-1]
+          else
+           #puts "#{inspect[0,5]} RETURNING self w/ next(#@current) = #{@events[@current]}"
+            return self
+          end
+        else
+          return nil
+        end
+      end
+
+      def matches?( event )
+        return @events[@current].matches?( event ) if @events[@current]
+        !@choices[@choice..-1].find{|evt| evt[0].matches?(event)}.nil?
+      end
+
+      def expected
+        #puts "IN CHOICE EXPECTED"
+        #puts "EVENTS = #{@events.inspect}"
+        return [@events[@current]] if @events[@current]
+        return @choices[@choice..-1].collect do |x| 
+          if x[0].kind_of? State
+            x[0].expected
+          else
+            x[0]
+          end
+        end.flatten
+      end
+
+      def inspect
+        "< #{to_s} #{@choices.collect{|e| e.collect{|f|f.to_s}.join(', ')}.join(' and ')} >"
+      end
+    end
+
+    class Ref
+      def initialize value
+        @value = value
+      end
+      def to_s
+        @value
+      end
+      def inspect
+        "{#{to_s}}"
+      end
+    end
+  end
+end
diff --git a/lib/rexml/validation/validation.rb b/lib/rexml/validation/validation.rb
new file mode 100644
index 0000000000..fbee315f0b
--- /dev/null
+++ b/lib/rexml/validation/validation.rb
@@ -0,0 +1,152 @@
+require 'rexml/validation/validationexception'
+
+module REXML
+  module Validation
+    module Validator
+      NILEVENT = [ nil ]
+      def reset
+        @current = @root
+        @root.reset
+        @root.previous = true
+        @attr_stack = []
+        self
+      end
+      def dump
+        puts @root.inspect
+      end
+      def validate( event ) 
+        #puts "Current: #@current"
+        #puts "Event: #{event.inspect}"
+        @attr_stack = [] unless defined? @attr_stack
+        match = @current.next(event)
+        raise ValidationException.new( "Validation error.  Expected: "+
+          @current.expected.join( " or " )+" from #{@current.inspect} "+
+          " but got #{Event.new( event[0], event[1] ).inspect}" ) unless match
+        @current = match
+
+        # Check for attributes
+        case event[0]
+        when :start_element
+          #puts "Checking attributes"
+          @attr_stack << event[2]
+          begin
+            sattr = [:start_attribute, nil]
+            eattr = [:end_attribute]
+            text = [:text, nil]
+            k,v = event[2].find { |k,v| 
+              sattr[1] = k
+              #puts "Looking for #{sattr.inspect}"
+              m = @current.next( sattr )
+              #puts "Got #{m.inspect}"
+              if m 
+                # If the state has text children...
+                #puts "Looking for #{eattr.inspect}"
+                #puts "Expect #{m.expected}"
+                if m.matches?( eattr )
+                  #puts "Got end"
+                  @current = m
+                else
+                  #puts "Didn't get end"
+                  text[1] = v
+                  #puts "Looking for #{text.inspect}"
+                  m = m.next( text )
+                  #puts "Got #{m.inspect}"
+                  text[1] = nil
+                  return false unless m
+                  @current = m if m
+                end
+                m = @current.next( eattr )
+                if m
+                  @current = m
+                  true
+                else
+                  false
+                end
+              else
+                false
+              end
+            }
+            event[2].delete(k) if k
+          end while k
+        when :end_element
+          attrs = @attr_stack.pop
+          raise ValidationException.new( "Validation error.  Illegal "+
+            " attributes: #{attrs.inspect}") if attrs.length > 0
+        end
+      end
+    end
+
+    class Event
+      def initialize(event_type, event_arg=nil )
+        @event_type = event_type
+        @event_arg = event_arg
+      end
+
+      attr_reader :done?
+      attr_reader :event_type
+      attr_accessor :event_arg
+
+      def single?
+        return (@event_type != :start_element and @event_type != :start_attribute)
+      end
+
+      def matches?( event )
+        #puts "#@event_type =? #{event[0]} && #@event_arg =? #{event[1]} "
+        return false unless event[0] == @event_type
+        case event[0]
+        when nil
+          return true
+        when :start_element
+          return true if event[1] == @event_arg
+        when :end_element
+          return true
+        when :start_attribute
+          return true if event[1] == @event_arg
+        when :end_attribute
+          return true
+        when :end_document
+          return true
+        when :text
+          return (@event_arg.nil? or @event_arg == event[1])
+=begin
+        when :processing_instruction
+          false
+        when :xmldecl
+          false
+        when :start_doctype
+          false
+        when :end_doctype
+          false
+        when :externalentity
+          false
+        when :elementdecl
+          false
+        when :entity
+          false
+        when :attlistdecl
+          false
+        when :notationdecl
+          false
+        when :end_doctype
+          false
+=end
+        else
+          false
+        end
+      end
+
+      def ==( other )
+        return false unless other.kind_of? Event
+        @event_type == other.event_type and @event_arg == other.event_arg
+      end
+
+      def to_s
+        inspect
+      end
+
+      def inspect
+        "#{@event_type.inspect}( #@event_arg )"
+      end
+    end
+  end
+end
diff --git a/lib/rexml/validation/validationexception.rb b/lib/rexml/validation/validationexception.rb
new file mode 100644
index 0000000000..4723d9e4d3
--- /dev/null
+++ b/lib/rexml/validation/validationexception.rb
@@ -0,0 +1,9 @@
+module REXML
+  module Validation
+    class ValidationException < RuntimeError
+      def initialize msg
+        super
+      end
+    end
+  end
+end