lib/voodoo/validator.rb

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