lib/voodoo/validator.rb

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