vendor/github.com/hashicorp/hil/check_types.go

   1 package hil
   2
   3 import (
   4         "fmt"
   5         "sync"
   6
   7         "github.com/hashicorp/hil/ast"
   8 )
   9
  10 // TypeCheck implements ast.Visitor for type checking an AST tree.
  11 // It requires some configuration to look up the type of nodes.
  12 //
  13 // It also optionally will not type error and will insert an implicit
  14 // type conversions for specific types if specified by the Implicit
  15 // field. Note that this is kind of organizationally weird to put into
  16 // this structure but we'd rather do that than duplicate the type checking
  17 // logic multiple times.
  18 type TypeCheck struct {
  19         Scope ast.Scope
  20
  21         // Implicit is a map of implicit type conversions that we can do,
  22         // and that shouldn't error. The key of the first map is the from type,
  23         // the key of the second map is the to type, and the final string
  24         // value is the function to call (which must be registered in the Scope).
  25         Implicit map[ast.Type]map[ast.Type]string
  26
  27         // Stack of types. This shouldn't be used directly except by implementations
  28         // of TypeCheckNode.
  29         Stack []ast.Type
  30
  31         err  error
  32         lock sync.Mutex
  33 }
  34
  35 // TypeCheckNode is the interface that must be implemented by any
  36 // ast.Node that wants to support type-checking. If the type checker
  37 // encounters a node that doesn't implement this, it will error.
  38 type TypeCheckNode interface {
  39         TypeCheck(*TypeCheck) (ast.Node, error)
  40 }
  41
  42 func (v *TypeCheck) Visit(root ast.Node) error {
  43         v.lock.Lock()
  44         defer v.lock.Unlock()
  45         defer v.reset()
  46         root.Accept(v.visit)
  47
  48         // If the resulting type is unknown, then just let the whole thing go.
  49         if v.err == errExitUnknown {
  50                 v.err = nil
  51         }
  52
  53         return v.err
  54 }
  55
  56 func (v *TypeCheck) visit(raw ast.Node) ast.Node {
  57         if v.err != nil {
  58                 return raw
  59         }
  60
  61         var result ast.Node
  62         var err error
  63         switch n := raw.(type) {
  64         case *ast.Arithmetic:
  65                 tc := &typeCheckArithmetic{n}
  66                 result, err = tc.TypeCheck(v)
  67         case *ast.Call:
  68                 tc := &typeCheckCall{n}
  69                 result, err = tc.TypeCheck(v)
  70         case *ast.Conditional:
  71                 tc := &typeCheckConditional{n}
  72                 result, err = tc.TypeCheck(v)
  73         case *ast.Index:
  74                 tc := &typeCheckIndex{n}
  75                 result, err = tc.TypeCheck(v)
  76         case *ast.Output:
  77                 tc := &typeCheckOutput{n}
  78                 result, err = tc.TypeCheck(v)
  79         case *ast.LiteralNode:
  80                 tc := &typeCheckLiteral{n}
  81                 result, err = tc.TypeCheck(v)
  82         case *ast.VariableAccess:
  83                 tc := &typeCheckVariableAccess{n}
  84                 result, err = tc.TypeCheck(v)
  85         default:
  86                 tc, ok := raw.(TypeCheckNode)
  87                 if !ok {
  88                         err = fmt.Errorf("unknown node for type check: %#v", raw)
  89                         break
  90                 }
  91
  92                 result, err = tc.TypeCheck(v)
  93         }
  94
  95         if err != nil {
  96                 pos := raw.Pos()
  97                 v.err = fmt.Errorf("At column %d, line %d: %s",
  98                         pos.Column, pos.Line, err)
  99         }
 100
 101         return result
 102 }
 103
 104 type typeCheckArithmetic struct {
 105         n *ast.Arithmetic
 106 }
 107
 108 func (tc *typeCheckArithmetic) TypeCheck(v *TypeCheck) (ast.Node, error) {
 109         // The arguments are on the stack in reverse order, so pop them off.
 110         exprs := make([]ast.Type, len(tc.n.Exprs))
 111         for i, _ := range tc.n.Exprs {
 112                 exprs[len(tc.n.Exprs)-1-i] = v.StackPop()
 113         }
 114
 115         // If any operand is unknown then our result is automatically unknown
 116         for _, ty := range exprs {
 117                 if ty == ast.TypeUnknown {
 118                         v.StackPush(ast.TypeUnknown)
 119                         return tc.n, nil
 120                 }
 121         }
 122
 123         switch tc.n.Op {
 124         case ast.ArithmeticOpLogicalAnd, ast.ArithmeticOpLogicalOr:
 125                 return tc.checkLogical(v, exprs)
 126         case ast.ArithmeticOpEqual, ast.ArithmeticOpNotEqual,
 127                 ast.ArithmeticOpLessThan, ast.ArithmeticOpGreaterThan,
 128                 ast.ArithmeticOpGreaterThanOrEqual, ast.ArithmeticOpLessThanOrEqual:
 129                 return tc.checkComparison(v, exprs)
 130         default:
 131                 return tc.checkNumeric(v, exprs)
 132         }
 133
 134 }
 135
 136 func (tc *typeCheckArithmetic) checkNumeric(v *TypeCheck, exprs []ast.Type) (ast.Node, error) {
 137         // Determine the resulting type we want. We do this by going over
 138         // every expression until we find one with a type we recognize.
 139         // We do this because the first expr might be a string ("var.foo")
 140         // and we need to know what to implicit to.
 141         mathFunc := "__builtin_IntMath"
 142         mathType := ast.TypeInt
 143         for _, v := range exprs {
 144                 // We assume int math but if we find ANY float, the entire
 145                 // expression turns into floating point math.
 146                 if v == ast.TypeFloat {
 147                         mathFunc = "__builtin_FloatMath"
 148                         mathType = v
 149                         break
 150                 }
 151         }
 152
 153         // Verify the args
 154         for i, arg := range exprs {
 155                 if arg != mathType {
 156                         cn := v.ImplicitConversion(exprs[i], mathType, tc.n.Exprs[i])
 157                         if cn != nil {
 158                                 tc.n.Exprs[i] = cn
 159                                 continue
 160                         }
 161
 162                         return nil, fmt.Errorf(
 163                                 "operand %d should be %s, got %s",
 164                                 i+1, mathType, arg)
 165                 }
 166         }
 167
 168         // Modulo doesn't work for floats
 169         if mathType == ast.TypeFloat && tc.n.Op == ast.ArithmeticOpMod {
 170                 return nil, fmt.Errorf("modulo cannot be used with floats")
 171         }
 172
 173         // Return type
 174         v.StackPush(mathType)
 175
 176         // Replace our node with a call to the proper function. This isn't
 177         // type checked but we already verified types.
 178         args := make([]ast.Node, len(tc.n.Exprs)+1)
 179         args[0] = &ast.LiteralNode{
 180                 Value: tc.n.Op,
 181                 Typex: ast.TypeInt,
 182                 Posx:  tc.n.Pos(),
 183         }
 184         copy(args[1:], tc.n.Exprs)
 185         return &ast.Call{
 186                 Func: mathFunc,
 187                 Args: args,
 188                 Posx: tc.n.Pos(),
 189         }, nil
 190 }
 191
 192 func (tc *typeCheckArithmetic) checkComparison(v *TypeCheck, exprs []ast.Type) (ast.Node, error) {
 193         if len(exprs) != 2 {
 194                 // This should never happen, because the parser never produces
 195                 // nodes that violate this.
 196                 return nil, fmt.Errorf(
 197                         "comparison operators must have exactly two operands",
 198                 )
 199         }
 200
 201         // The first operand always dictates the type for a comparison.
 202         compareFunc := ""
 203         compareType := exprs[0]
 204         switch compareType {
 205         case ast.TypeBool:
 206                 compareFunc = "__builtin_BoolCompare"
 207         case ast.TypeFloat:
 208                 compareFunc = "__builtin_FloatCompare"
 209         case ast.TypeInt:
 210                 compareFunc = "__builtin_IntCompare"
 211         case ast.TypeString:
 212                 compareFunc = "__builtin_StringCompare"
 213         default:
 214                 return nil, fmt.Errorf(
 215                         "comparison operators apply only to bool, float, int, and string",
 216                 )
 217         }
 218
 219         // For non-equality comparisons, we will do implicit conversions to
 220         // integer types if possible. In this case, we need to go through and
 221         // determine the type of comparison we're doing to enable the implicit
 222         // conversion.
 223         if tc.n.Op != ast.ArithmeticOpEqual && tc.n.Op != ast.ArithmeticOpNotEqual {
 224                 compareFunc = "__builtin_IntCompare"
 225                 compareType = ast.TypeInt
 226                 for _, expr := range exprs {
 227                         if expr == ast.TypeFloat {
 228                                 compareFunc = "__builtin_FloatCompare"
 229                                 compareType = ast.TypeFloat
 230                                 break
 231                         }
 232                 }
 233         }
 234
 235         // Verify (and possibly, convert) the args
 236         for i, arg := range exprs {
 237                 if arg != compareType {
 238                         cn := v.ImplicitConversion(exprs[i], compareType, tc.n.Exprs[i])
 239                         if cn != nil {
 240                                 tc.n.Exprs[i] = cn
 241                                 continue
 242                         }
 243
 244                         return nil, fmt.Errorf(
 245                                 "operand %d should be %s, got %s",
 246                                 i+1, compareType, arg,
 247                         )
 248                 }
 249         }
 250
 251         // Only ints and floats can have the <, >, <= and >= operators applied
 252         switch tc.n.Op {
 253         case ast.ArithmeticOpEqual, ast.ArithmeticOpNotEqual:
 254                 // anything goes
 255         default:
 256                 switch compareType {
 257                 case ast.TypeFloat, ast.TypeInt:
 258                         // fine
 259                 default:
 260                         return nil, fmt.Errorf(
 261                                 "<, >, <= and >= may apply only to int and float values",
 262                         )
 263                 }
 264         }
 265
 266         // Comparison operators always return bool
 267         v.StackPush(ast.TypeBool)
 268
 269         // Replace our node with a call to the proper function. This isn't
 270         // type checked but we already verified types.
 271         args := make([]ast.Node, len(tc.n.Exprs)+1)
 272         args[0] = &ast.LiteralNode{
 273                 Value: tc.n.Op,
 274                 Typex: ast.TypeInt,
 275                 Posx:  tc.n.Pos(),
 276         }
 277         copy(args[1:], tc.n.Exprs)
 278         return &ast.Call{
 279                 Func: compareFunc,
 280                 Args: args,
 281                 Posx: tc.n.Pos(),
 282         }, nil
 283 }
 284
 285 func (tc *typeCheckArithmetic) checkLogical(v *TypeCheck, exprs []ast.Type) (ast.Node, error) {
 286         for i, t := range exprs {
 287                 if t != ast.TypeBool {
 288                         cn := v.ImplicitConversion(t, ast.TypeBool, tc.n.Exprs[i])
 289                         if cn == nil {
 290                                 return nil, fmt.Errorf(
 291                                         "logical operators require boolean operands, not %s",
 292                                         t,
 293                                 )
 294                         }
 295                         tc.n.Exprs[i] = cn
 296                 }
 297         }
 298
 299         // Return type is always boolean
 300         v.StackPush(ast.TypeBool)
 301
 302         // Arithmetic nodes are replaced with a call to a built-in function
 303         args := make([]ast.Node, len(tc.n.Exprs)+1)
 304         args[0] = &ast.LiteralNode{
 305                 Value: tc.n.Op,
 306                 Typex: ast.TypeInt,
 307                 Posx:  tc.n.Pos(),
 308         }
 309         copy(args[1:], tc.n.Exprs)
 310         return &ast.Call{
 311                 Func: "__builtin_Logical",
 312                 Args: args,
 313                 Posx: tc.n.Pos(),
 314         }, nil
 315 }
 316
 317 type typeCheckCall struct {
 318         n *ast.Call
 319 }
 320
 321 func (tc *typeCheckCall) TypeCheck(v *TypeCheck) (ast.Node, error) {
 322         // Look up the function in the map
 323         function, ok := v.Scope.LookupFunc(tc.n.Func)
 324         if !ok {
 325                 return nil, fmt.Errorf("unknown function called: %s", tc.n.Func)
 326         }
 327
 328         // The arguments are on the stack in reverse order, so pop them off.
 329         args := make([]ast.Type, len(tc.n.Args))
 330         for i, _ := range tc.n.Args {
 331                 args[len(tc.n.Args)-1-i] = v.StackPop()
 332         }
 333
 334         // Verify the args
 335         for i, expected := range function.ArgTypes {
 336                 if expected == ast.TypeAny {
 337                         continue
 338                 }
 339
 340                 if args[i] == ast.TypeUnknown {
 341                         v.StackPush(ast.TypeUnknown)
 342                         return tc.n, nil
 343                 }
 344
 345                 if args[i] != expected {
 346                         cn := v.ImplicitConversion(args[i], expected, tc.n.Args[i])
 347                         if cn != nil {
 348                                 tc.n.Args[i] = cn
 349                                 continue
 350                         }
 351
 352                         return nil, fmt.Errorf(
 353                                 "%s: argument %d should be %s, got %s",
 354                                 tc.n.Func, i+1, expected.Printable(), args[i].Printable())
 355                 }
 356         }
 357
 358         // If we're variadic, then verify the types there
 359         if function.Variadic && function.VariadicType != ast.TypeAny {
 360                 args = args[len(function.ArgTypes):]
 361                 for i, t := range args {
 362                         if t == ast.TypeUnknown {
 363                                 v.StackPush(ast.TypeUnknown)
 364                                 return tc.n, nil
 365                         }
 366
 367                         if t != function.VariadicType {
 368                                 realI := i + len(function.ArgTypes)
 369                                 cn := v.ImplicitConversion(
 370                                         t, function.VariadicType, tc.n.Args[realI])
 371                                 if cn != nil {
 372                                         tc.n.Args[realI] = cn
 373                                         continue
 374                                 }
 375
 376                                 return nil, fmt.Errorf(
 377                                         "%s: argument %d should be %s, got %s",
 378                                         tc.n.Func, realI,
 379                                         function.VariadicType.Printable(), t.Printable())
 380                         }
 381                 }
 382         }
 383
 384         // Return type
 385         v.StackPush(function.ReturnType)
 386
 387         return tc.n, nil
 388 }
 389
 390 type typeCheckConditional struct {
 391         n *ast.Conditional
 392 }
 393
 394 func (tc *typeCheckConditional) TypeCheck(v *TypeCheck) (ast.Node, error) {
 395         // On the stack we have the types of the condition, true and false
 396         // expressions, but they are in reverse order.
 397         falseType := v.StackPop()
 398         trueType := v.StackPop()
 399         condType := v.StackPop()
 400
 401         if condType == ast.TypeUnknown {
 402                 v.StackPush(ast.TypeUnknown)
 403                 return tc.n, nil
 404         }
 405
 406         if condType != ast.TypeBool {
 407                 cn := v.ImplicitConversion(condType, ast.TypeBool, tc.n.CondExpr)
 408                 if cn == nil {
 409                         return nil, fmt.Errorf(
 410                                 "condition must be type bool, not %s", condType.Printable(),
 411                         )
 412                 }
 413                 tc.n.CondExpr = cn
 414         }
 415
 416         // The types of the true and false expression must match
 417         if trueType != falseType && trueType != ast.TypeUnknown && falseType != ast.TypeUnknown {
 418
 419                 // Since passing around stringified versions of other types is
 420                 // common, we pragmatically allow the false expression to dictate
 421                 // the result type when the true expression is a string.
 422                 if trueType == ast.TypeString {
 423                         cn := v.ImplicitConversion(trueType, falseType, tc.n.TrueExpr)
 424                         if cn == nil {
 425                                 return nil, fmt.Errorf(
 426                                         "true and false expression types must match; have %s and %s",
 427                                         trueType.Printable(), falseType.Printable(),
 428                                 )
 429                         }
 430                         tc.n.TrueExpr = cn
 431                         trueType = falseType
 432                 } else {
 433                         cn := v.ImplicitConversion(falseType, trueType, tc.n.FalseExpr)
 434                         if cn == nil {
 435                                 return nil, fmt.Errorf(
 436                                         "true and false expression types must match; have %s and %s",
 437                                         trueType.Printable(), falseType.Printable(),
 438                                 )
 439                         }
 440                         tc.n.FalseExpr = cn
 441                         falseType = trueType
 442                 }
 443         }
 444
 445         // Currently list and map types cannot be used, because we cannot
 446         // generally assert that their element types are consistent.
 447         // Such support might be added later, either by improving the type
 448         // system or restricting usage to only variable and literal expressions,
 449         // but for now this is simply prohibited because it doesn't seem to
 450         // be a common enough case to be worth the complexity.
 451         switch trueType {
 452         case ast.TypeList:
 453                 return nil, fmt.Errorf(
 454                         "conditional operator cannot be used with list values",
 455                 )
 456         case ast.TypeMap:
 457                 return nil, fmt.Errorf(
 458                         "conditional operator cannot be used with map values",
 459                 )
 460         }
 461
 462         // Result type (guaranteed to also match falseType due to the above)
 463         if trueType == ast.TypeUnknown {
 464                 // falseType may also be unknown, but that's okay because two
 465                 // unknowns means our result is unknown anyway.
 466                 v.StackPush(falseType)
 467         } else {
 468                 v.StackPush(trueType)
 469         }
 470
 471         return tc.n, nil
 472 }
 473
 474 type typeCheckOutput struct {
 475         n *ast.Output
 476 }
 477
 478 func (tc *typeCheckOutput) TypeCheck(v *TypeCheck) (ast.Node, error) {
 479         n := tc.n
 480         types := make([]ast.Type, len(n.Exprs))
 481         for i, _ := range n.Exprs {
 482                 types[len(n.Exprs)-1-i] = v.StackPop()
 483         }
 484
 485         for _, ty := range types {
 486                 if ty == ast.TypeUnknown {
 487                         v.StackPush(ast.TypeUnknown)
 488                         return tc.n, nil
 489                 }
 490         }
 491
 492         // If there is only one argument and it is a list, we evaluate to a list
 493         if len(types) == 1 {
 494                 switch t := types[0]; t {
 495                 case ast.TypeList:
 496                         fallthrough
 497                 case ast.TypeMap:
 498                         v.StackPush(t)
 499                         return n, nil
 500                 }
 501         }
 502
 503         // Otherwise, all concat args must be strings, so validate that
 504         resultType := ast.TypeString
 505         for i, t := range types {
 506
 507                 if t == ast.TypeUnknown {
 508                         resultType = ast.TypeUnknown
 509                         continue
 510                 }
 511
 512                 if t != ast.TypeString {
 513                         cn := v.ImplicitConversion(t, ast.TypeString, n.Exprs[i])
 514                         if cn != nil {
 515                                 n.Exprs[i] = cn
 516                                 continue
 517                         }
 518
 519                         return nil, fmt.Errorf(
 520                                 "output of an HIL expression must be a string, or a single list (argument %d is %s)", i+1, t)
 521                 }
 522         }
 523
 524         // This always results in type string, unless there are unknowns
 525         v.StackPush(resultType)
 526
 527         return n, nil
 528 }
 529
 530 type typeCheckLiteral struct {
 531         n *ast.LiteralNode
 532 }
 533
 534 func (tc *typeCheckLiteral) TypeCheck(v *TypeCheck) (ast.Node, error) {
 535         v.StackPush(tc.n.Typex)
 536         return tc.n, nil
 537 }
 538
 539 type typeCheckVariableAccess struct {
 540         n *ast.VariableAccess
 541 }
 542
 543 func (tc *typeCheckVariableAccess) TypeCheck(v *TypeCheck) (ast.Node, error) {
 544         // Look up the variable in the map
 545         variable, ok := v.Scope.LookupVar(tc.n.Name)
 546         if !ok {
 547                 return nil, fmt.Errorf(
 548                         "unknown variable accessed: %s", tc.n.Name)
 549         }
 550
 551         // Add the type to the stack
 552         v.StackPush(variable.Type)
 553
 554         return tc.n, nil
 555 }
 556
 557 type typeCheckIndex struct {
 558         n *ast.Index
 559 }
 560
 561 func (tc *typeCheckIndex) TypeCheck(v *TypeCheck) (ast.Node, error) {
 562         keyType := v.StackPop()
 563         targetType := v.StackPop()
 564
 565         if keyType == ast.TypeUnknown || targetType == ast.TypeUnknown {
 566                 v.StackPush(ast.TypeUnknown)
 567                 return tc.n, nil
 568         }
 569
 570         // Ensure we have a VariableAccess as the target
 571         varAccessNode, ok := tc.n.Target.(*ast.VariableAccess)
 572         if !ok {
 573                 return nil, fmt.Errorf(
 574                         "target of an index must be a VariableAccess node, was %T", tc.n.Target)
 575         }
 576
 577         // Get the variable
 578         variable, ok := v.Scope.LookupVar(varAccessNode.Name)
 579         if !ok {
 580                 return nil, fmt.Errorf(
 581                         "unknown variable accessed: %s", varAccessNode.Name)
 582         }
 583
 584         switch targetType {
 585         case ast.TypeList:
 586                 if keyType != ast.TypeInt {
 587                         tc.n.Key = v.ImplicitConversion(keyType, ast.TypeInt, tc.n.Key)
 588                         if tc.n.Key == nil {
 589                                 return nil, fmt.Errorf(
 590                                         "key of an index must be an int, was %s", keyType)
 591                         }
 592                 }
 593
 594                 valType, err := ast.VariableListElementTypesAreHomogenous(
 595                         varAccessNode.Name, variable.Value.([]ast.Variable))
 596                 if err != nil {
 597                         return tc.n, err
 598                 }
 599
 600                 v.StackPush(valType)
 601                 return tc.n, nil
 602         case ast.TypeMap:
 603                 if keyType != ast.TypeString {
 604                         tc.n.Key = v.ImplicitConversion(keyType, ast.TypeString, tc.n.Key)
 605                         if tc.n.Key == nil {
 606                                 return nil, fmt.Errorf(
 607                                         "key of an index must be a string, was %s", keyType)
 608                         }
 609                 }
 610
 611                 valType, err := ast.VariableMapValueTypesAreHomogenous(
 612                         varAccessNode.Name, variable.Value.(map[string]ast.Variable))
 613                 if err != nil {
 614                         return tc.n, err
 615                 }
 616
 617                 v.StackPush(valType)
 618                 return tc.n, nil
 619         default:
 620                 return nil, fmt.Errorf("invalid index operation into non-indexable type: %s", variable.Type)
 621         }
 622 }
 623
 624 func (v *TypeCheck) ImplicitConversion(
 625         actual ast.Type, expected ast.Type, n ast.Node) ast.Node {
 626         if v.Implicit == nil {
 627                 return nil
 628         }
 629
 630         fromMap, ok := v.Implicit[actual]
 631         if !ok {
 632                 return nil
 633         }
 634
 635         toFunc, ok := fromMap[expected]
 636         if !ok {
 637                 return nil
 638         }
 639
 640         return &ast.Call{
 641                 Func: toFunc,
 642                 Args: []ast.Node{n},
 643                 Posx: n.Pos(),
 644         }
 645 }
 646
 647 func (v *TypeCheck) reset() {
 648         v.Stack = nil
 649         v.err = nil
 650 }
 651
 652 func (v *TypeCheck) StackPush(t ast.Type) {
 653         v.Stack = append(v.Stack, t)
 654 }
 655
 656 func (v *TypeCheck) StackPop() ast.Type {
 657         var x ast.Type
 658         x, v.Stack = v.Stack[len(v.Stack)-1], v.Stack[:len(v.Stack)-1]
 659         return x
 660 }
 661
 662 func (v *TypeCheck) StackPeek() ast.Type {
 663         if len(v.Stack) == 0 {
 664                 return ast.TypeInvalid
 665         }
 666
 667         return v.Stack[len(v.Stack)-1]
 668 }