lib/voodoo/validator.rb

   1 module Voodoo
   2   # Functionality for validating Voodoo code.
   3   module Validator
   4
   5     # Expressions that take two arguments
   6     BINOPS = [:add, :and, :asr, :bsr, :div, :mod, :mul, :or,
   7               :rol, :ror, :shl, :shr, :sub, :xor]
   8     # Expressions that take zero or more parameters
   9     VARARG_EXPRS = [:call, :'tail-call']
  10     # Symbols that may occur as the first word of an expression
  11     EXPRS = BINOPS + VARARG_EXPRS + [:not]
  12
  13     # Symbols that are a valid start of a statement
  14     STATEMENTS = [:block, :call,
  15                   :'get-byte', :'get-word', :goto,
  16                   :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne,
  17                   :label, :let, :return, :set,
  18                   :'set-byte', :'set-word', :'tail-call']
  19
  20     # Symbols that are valid at top-level
  21     TOP_LEVELS = [:align, :byte, :export, :function, :import,
  22                   :section, :string, :word] + STATEMENTS
  23
  24     module_function
  25
  26     # Validates an expression.
  27     # Returns true if the expression is valid.
  28     # Raises ValidationError if the expression is not valid.
  29     def validate_expression code
  30       if atomic_value? code
  31         true
  32       elsif code.respond_to? :[]
  33         if BINOPS.member? code[0]
  34           # binop must have 2 parameters, both of them atomic values
  35           if code.length == 3
  36             if atomic_value? code[1]
  37               if atomic_value? code[2]
  38                 true
  39               else
  40                 raise ValidationError.new("#{code[2].inspect} should be" +
  41                                           "a Symbol or an Integer", code)
  42               end
  43             else
  44               raise ValidationError.new("#{code[1].inspect} should be" +
  45                                         "a Symbol or an Integer", code)
  46             end
  47           else
  48             raise ValidationError.new("#{code[0]} should get exactly 2" +
  49                                       " parameters", code)
  50           end
  51         else
  52           # code[0] is not a binop
  53           case code[0]
  54           when :call, :'tail-call'
  55             # call must have at least 1 parameter
  56             # and all parameters must be atomic values
  57             if code.length < 2
  58               raise ValidationError.new("#{code[0]} requires at least" +
  59                                         " one parameter", code)
  60             else
  61               code[1..-1].each do |x|
  62                 unless atomic_value? x
  63                   raise ValidationError.new("All parameters to #{code[0]}" +
  64                                             " should be atomic values" +
  65                                             " (symbols or integers)",
  66                                             code)
  67                 end
  68               end
  69             end
  70             true
  71
  72           when :'get-byte', :'get-word'
  73             # Must have exactly 2 parameters.
  74             # First parameter must be a symbol.
  75             # Second parameter must be an atomic value.
  76             if code.length != 3
  77               raise ValidationError.new("#{code[0]} should have exactly" +
  78                                         " two parameters", code)
  79             elsif !code[1].kind_of?(::Symbol)
  80               raise ValidationError.new("First parameter to #{code[0]} must" +
  81                                         " be a symbol", code)
  82             elsif !atomic_value?(code[2])
  83               raise ValidationError.new("Second parameter to #{code[0]} must" +
  84                                         " be a symbol or an integer", code)
  85             else
  86               true
  87             end
  88
  89           when :not
  90               # must have a single, atomic parameter
  91               if code.length != 2
  92                 raise ValidationError.new("not takes exactly one parameter",
  93                                           code)
  94               elsif atomic_value? code[1]
  95                 true
  96               else
  97                 raise ValidationError.new("Parameter to not must be a" +
  98                                           " symbol or integer", code)
  99               end
 100
 101           else
 102             raise ValidationError.new("#{code[0].inspect}" +
 103                                       " cannot start an expression",
 104                                       code)
 105           end
 106         end
 107       else
 108         # code is not an atomic value and does not respond to :[]
 109         raise ValidationError.new("#{code.inspect} is not a valid expression",
 110                                   code)
 111       end
 112     end
 113
 114     # Validates a statement.
 115     # Returns true if the statement is valid.
 116     # Raises ValidationError if the statement is not valid.
 117     def validate_statement code
 118       begin
 119         case code[0]
 120         when :block
 121           code[1..-1].each {|stmt| validate_statement stmt}
 122           true
 123
 124         when :call, :'tail-call'
 125           validate_expression code
 126
 127         when :goto
 128           # must have exactly 1 parameter, which must be atomic
 129           if code.length != 2
 130             raise ValidationError.new("goto should have exactly" +
 131                                       " one parameter", code)
 132           elsif atomic_value? code[1]
 133             true
 134           else
 135             raise ValidationError.new("parameter to goto must be a" +
 136                                       " label or an integer", code)
 137           end
 138
 139         when :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
 140           # Must have 2 or 3 parameters.
 141           # First parameter must be an array (or similar) containing
 142           # two elements, both atomic.
 143           # Second parameter must consist of one or more statements.
 144           # Third parameter, if present, must consist of zero or more
 145           # statements.
 146           # let is not allowed as a statement in either parameter, though
 147           # it can be embedded in a block in either.
 148           if code.length < 3 || code.length > 4
 149             raise ValidationError.new("#{code[0]} takes 2 or 3 parameters",
 150                                       code)
 151           elsif code[1].length != 2
 152             raise ValidationError.new("#{code[0]} requires two values to" +
 153                                       " compare in its first parameter",
 154                                       code)
 155           elsif !code[1].all? {|x| atomic_value? x}
 156             raise ValidationError.new("Values to compare must be atomic" +
 157                                       " (symbols or integers)", code)
 158           else
 159             code[2].each do |stmt|
 160               validate_statement stmt
 161               if stmt[0] == :let
 162                 raise ValidationError.new("let is not allowed inside " +
 163                                           code[0].to_s, code)
 164               end
 165             end
 166
 167             if code.length > 3
 168               code[3].each do |stmt|
 169                 validate_statement stmt
 170                 if stmt[0] == :let
 171                   raise ValidationError.new("let is not allowed inside " +
 172                                             code[0].to_s, code)
 173                 end
 174               end
 175             end
 176
 177             true
 178           end
 179
 180         when :label
 181           # must have 1 parameter which must be a symbol
 182           if code.length != 2 || !code[1].kind_of?(::Symbol)
 183             raise ValidationError.new("label requires a single symbol" +
 184                                       "as its parameter", code)
 185           else
 186             true
 187           end
 188
 189         when :let, :set
 190           # must have exactly 2 parameters
 191           if code.length != 3
 192             raise ValidationError.new("#{code[0]} requires exactly" +
 193                                       " two parameters", code)
 194           elsif code[1].kind_of? ::Symbol
 195             # Second parameter must be an expression
 196             validate_expression code[2]
 197           else
 198             raise ValidationError.new("First parameter to #{code[0]} must be" +
 199                                         " a symbol", code)
 200           end
 201
 202         when :return
 203           case code.length
 204           when 1
 205             true
 206           when 2
 207             validate_expression code[1]
 208           else
 209             raise ValidationError.new("return only takes a single parameter",
 210                                       code)
 211           end
 212
 213         when :'set-byte', :'set-word'
 214           # Must have exactly 3 parameters.
 215           # First parameter must be a symbol.
 216           # Second parameter must be an atomic value.
 217           # Third parameter must be an expression.
 218           if code.length != 4
 219             raise ValidationError.new("#{code[0]} should have exactly" +
 220                                       " three parameters", code)
 221           elsif !code[1].kind_of?(::Symbol)
 222             raise ValidationError.new("First parameter to #{code[0]} must" +
 223                                       " be a symbol", code)
 224           elsif !atomic_value?(code[2])
 225             raise ValidationError.new("Second parameter to #{code[0]} must" +
 226                                       " be a symbol or an integer", code)
 227           else
 228             validate_expression code[3]
 229           end
 230
 231         else
 232           raise ValidationError.new("Not a valid statement: #{code.inspect}",
 233                                     code)
 234         end
 235
 236       rescue ValidationError
 237         # Pass it on
 238         raise
 239
 240       rescue Exception => e
 241         if code.respond_to? :[]
 242           # Pass on the execption
 243           raise
 244         else
 245           raise ValidationError.new("#{code.inspect} does not respond to" +
 246                                     ":[]", code)
 247         end
 248
 249       end
 250     end
 251
 252     # Validates a top-level directive.
 253     # Returns true if the directive is valid.
 254     # Raises ValidationError if the directive is not valid.
 255     def validate_toplevel code
 256       begin
 257         case code[0]
 258         when :align
 259           # Must either have no parameter or a single integer parameter
 260           if code.length == 1 || (code.length == 2 &&
 261                                   code[1].kind_of?(::Integer))
 262             true
 263           else
 264             raise ValidationError.new("align requires either a single" +
 265                                       " integer parameter, or no parameters",
 266                                       code)
 267           end
 268
 269         when :byte, :word
 270           # Must have a single integer or symbol parameter
 271           if code.length != 2 || !atomic_value?(code[1])
 272             raise ValidationError.new("#{code[0]} requires a single" +
 273                                       " parameter that is either an " +
 274                                       " integer or a symbol", code)
 275           else
 276             true
 277           end
 278
 279         when :export, :import
 280           # Must have at least 1 parameter, and all parameters must
 281           # be symbols.
 282           if code.length < 2
 283             raise ValidationError.new("#{code[0]} requires at least " +
 284                                       " one parameter", code)
 285           elsif code[1..-1].all? {|x| x.kind_of? ::Symbol}
 286             true
 287           else
 288             raise ValidationError.new("All parameters to #{code[0]}" +
 289                                       " should be symbols", code)
 290           end
 291
 292         when :function
 293
 294           # Check that formal parameters have been specified
 295           if code.length < 2
 296             raise ValidationError.new("Formal parameters should be" +
 297                                       " specified for function",
 298                                       code)
 299           end
 300
 301           # Check that all formal parameters are symbols
 302           code[1].each do |formal|
 303             unless formal.kind_of? ::Symbol
 304               raise ValidationError.new("Formal parameter #{formal.inspect}" +
 305                                         " should be a symbol",
 306                                         formal)
 307             end
 308           end
 309
 310           # Verify statements
 311           code[2..-1].each {|stmt| validate_statement stmt}
 312
 313         when :section
 314
 315           # Check that we have a string or a symbol
 316           case code.length
 317           when 1
 318             raise ValidationError.new("Section name should be specified",
 319                                       code)
 320           when 2
 321             unless code[1].kind_of?(::String) || code[1].kind_of?(::Symbol)
 322               raise ValidationError.new("Section name should be a String" +
 323                                         " or a symbol",
 324                                         code)
 325             end
 326
 327           else
 328             raise ValidationError.new("section directive should have only" +
 329                                       " a single parameter",
 330                                       code);
 331           end
 332
 333         when :string
 334           # Must have a single string parameter
 335           if code.length != 2 || !code[1].kind_of?(::String)
 336             raise ValidationError.new("string requires a single string" +
 337                                       " as a parameter", code)
 338           else
 339             true
 340           end
 341
 342         else
 343           if STATEMENTS.member? code[0]
 344             validate_statement code
 345           else
 346             raise ValidationError.new("Directive #{code[0].inspect}" +
 347                                       " not valid at top-level;" +
 348                                       " valid directives are: " +
 349                                       TOP_LEVELS.join(', '),
 350                                       code)
 351           end
 352         end
 353
 354       rescue ValidationError
 355         # Pass it on
 356         raise
 357
 358       rescue Exception => e
 359         if code.respond_to? :[]
 360           # Pass on the exception
 361           raise
 362         else
 363           raise ValidationError.new("#{code.inspect} does not respond to" +
 364                                     ":[]", code)
 365         end
 366       end
 367
 368       # If we got here, all is well
 369       true
 370     end
 371
 372     # Base class for errors signalled by the Validator.
 373     class ValidationError < StandardError
 374       def initialize message, code = nil
 375         super message
 376         @code = code
 377       end
 378       attr_reader :code
 379     end
 380
 381     def atomic_value? code
 382       code.kind_of?(::Symbol) || code.kind_of?(::Integer)
 383     end
 384
 385   end
 386 end