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