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 int_or_symbol_or_at? 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 int_or_symbol_or_at? code[1]
  37               if int_or_symbol_or_at? 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 int_or_symbol_or_at? 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 !int_or_symbol_or_at?(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 int_or_symbol_or_at? 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 int_or_symbol_or_at? 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| int_or_symbol_or_at? 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 at least 2 parameters
 191           if code.length < 3
 192             raise ValidationError.new("#{code[0]} requires a symbol" +
 193                                       " and an expression", code)
 194           elsif code[1].kind_of? ::Symbol
 195             # After the symbol, there must be an expression
 196             expr = code[2..-1]
 197             if expr.length == 1
 198               validate_expression expr[0]
 199             else
 200               validate_expression expr
 201             end
 202           else
 203             raise ValidationError.new("First parameter to #{code[0]} must be" +
 204                                         " a symbol", code)
 205           end
 206
 207         when :return
 208           # Must either have no parameters, or a single expression as
 209           # a parameter.
 210           case code.length
 211           when 1
 212             true
 213           when 2
 214             validate_expression code[1]
 215           else
 216             validate_expression code[1..-1]
 217           end
 218
 219         when :'set-byte', :'set-word'
 220           # Must have exactly 3 parameters.
 221           # First parameter must be a symbol.
 222           # Second and third parameters must be atomic values.
 223           if code.length != 4
 224             raise ValidationError.new("#{code[0]} should have exactly" +
 225                                       " three parameters", code)
 226           elsif !code[1].kind_of?(::Symbol)
 227             raise ValidationError.new("First parameter to #{code[0]} must" +
 228                                       " be a symbol", code)
 229           elsif !int_or_symbol_or_at?(code[2])
 230             raise ValidationError.new("Second parameter to #{code[0]} must" +
 231                                       " be a symbol or an integer", code)
 232           elsif !int_or_symbol_or_at?(code[3])
 233             raise ValidationError.new("Third parameter to #{code[0]} must" +
 234                                       " be a symbol or an integer", code)
 235           else
 236             true
 237           end
 238
 239         else
 240           raise ValidationError.new("Not a valid statement: #{code.inspect}",
 241                                     code)
 242         end
 243
 244       rescue ValidationError
 245         # Pass it on
 246         raise
 247
 248       rescue Exception => e
 249         if code.respond_to? :[]
 250           # Pass on the execption
 251           raise
 252         else
 253           raise ValidationError.new("#{code.inspect} does not respond to" +
 254                                     ":[]", code)
 255         end
 256
 257       end
 258     end
 259
 260     # Validates a top-level directive.
 261     # Returns true if the directive is valid.
 262     # Raises ValidationError if the directive is not valid.
 263     def validate_top_level code
 264       begin
 265         case code[0]
 266         when :align
 267           # Must either have no parameter or a single integer parameter
 268           if code.length == 1 || (code.length == 2 &&
 269                                   code[1].kind_of?(::Integer))
 270             true
 271           else
 272             raise ValidationError.new("align requires either a single" +
 273                                       " integer parameter, or no parameters",
 274                                       code)
 275           end
 276
 277         when :byte, :word
 278           # Must have a single integer or symbol parameter
 279           if code.length != 2 || !int_or_symbol_or_at?(code[1])
 280             raise ValidationError.new("#{code[0]} requires a single" +
 281                                       " parameter that is either an " +
 282                                       " integer or a symbol", code)
 283           else
 284             true
 285           end
 286
 287         when :export, :import
 288           # Must have at least 1 parameter, and all parameters must
 289           # be symbols.
 290           if code.length < 2
 291             raise ValidationError.new("#{code[0]} requires at least " +
 292                                       " one parameter", code)
 293           elsif code[1..-1].all? {|x| x.kind_of? ::Symbol}
 294             true
 295           else
 296             raise ValidationError.new("All parameters to #{code[0]}" +
 297                                       " should be symbols", code)
 298           end
 299
 300         when :function
 301
 302           # Check that formal parameters have been specified
 303           if code.length < 2
 304             raise ValidationError.new("Formal parameters should be" +
 305                                       " specified for function",
 306                                       code)
 307           end
 308
 309           # Check that all formal parameters are symbols
 310           code[1].each do |formal|
 311             unless formal.kind_of? ::Symbol
 312               raise ValidationError.new("Formal parameter #{formal.inspect}" +
 313                                         " should be a symbol",
 314                                         formal)
 315             end
 316           end
 317
 318           # Verify statements
 319           code[2..-1].each do |stmt|
 320             if stmt.respond_to?(:[]) && stmt[0] == :function
 321               raise ValidationError.new("Function definitions are only " +
 322                                         "valid at top-level", stmt)
 323             else
 324               validate_statement stmt
 325             end
 326           end
 327
 328         when :section
 329
 330           # Check that we have a string or a symbol
 331           case code.length
 332           when 1
 333             raise ValidationError.new("Section name should be specified",
 334                                       code)
 335           when 2
 336             unless code[1].kind_of?(::String) || code[1].kind_of?(::Symbol)
 337               raise ValidationError.new("Section name should be a string" +
 338                                         " or a symbol",
 339                                         code)
 340             end
 341
 342           else
 343             raise ValidationError.new("section directive should have only" +
 344                                       " a single parameter",
 345                                       code);
 346           end
 347
 348         when :string
 349           # Must have a single string parameter
 350           if code.length != 2 || !code[1].kind_of?(::String)
 351             raise ValidationError.new("string requires a single string" +
 352                                       " as a parameter", code)
 353           else
 354             true
 355           end
 356
 357         else
 358           if STATEMENTS.member? code[0]
 359             validate_statement code
 360           else
 361             raise ValidationError.new("Directive #{code[0]}" +
 362                                       " not valid at top-level",
 363                                       code)
 364           end
 365         end
 366
 367       rescue ValidationError
 368         # Pass it on
 369         raise
 370
 371       rescue Exception => e
 372         if code.respond_to? :[]
 373           # Pass on the exception
 374           raise
 375         else
 376           raise ValidationError.new("#{code.inspect} does not respond to" +
 377                                     ":[]", code)
 378         end
 379       end
 380
 381       # If we got here, all is well
 382       true
 383     end
 384
 385     # Base class for errors signalled by the Validator.
 386     class ValidationError < StandardError
 387       def initialize message, code = nil
 388         super message
 389         @code = code
 390       end
 391       attr_reader :code
 392     end
 393
 394     def int_or_symbol? x
 395       x.kind_of?(::Symbol) || x.kind_of?(::Integer)
 396     end
 397
 398     def int_or_symbol_or_at? x
 399       int_or_symbol?(x) ||
 400         (x.respond_to?(:length) && x.length == 2 && x[0] == :'@' &&
 401          int_or_symbol?(x[1]))
 402     end
 403
 404   end
 405 end