1package hil 2 3import ( 4 "bytes" 5 "errors" 6 "fmt" 7 "sync" 8 9 "github.com/hashicorp/hil/ast" 10) 11 12// EvalConfig is the configuration for evaluating. 13type EvalConfig struct { 14 // GlobalScope is the global scope of execution for evaluation. 15 GlobalScope *ast.BasicScope 16 17 // SemanticChecks is a list of additional semantic checks that will be run 18 // on the tree prior to evaluating it. The type checker, identifier checker, 19 // etc. will be run before these automatically. 20 SemanticChecks []SemanticChecker 21} 22 23// SemanticChecker is the type that must be implemented to do a 24// semantic check on an AST tree. This will be called with the root node. 25type SemanticChecker func(ast.Node) error 26 27// EvaluationResult is a struct returned from the hil.Eval function, 28// representing the result of an interpolation. Results are returned in their 29// "natural" Go structure rather than in terms of the HIL AST. For the types 30// currently implemented, this means that the Value field can be interpreted as 31// the following Go types: 32// TypeInvalid: undefined 33// TypeString: string 34// TypeList: []interface{} 35// TypeMap: map[string]interface{} 36// TypBool: bool 37type EvaluationResult struct { 38 Type EvalType 39 Value interface{} 40} 41 42// InvalidResult is a structure representing the result of a HIL interpolation 43// which has invalid syntax, missing variables, or some other type of error. 44// The error is described out of band in the accompanying error return value. 45var InvalidResult = EvaluationResult{Type: TypeInvalid, Value: nil} 46 47// errExitUnknown is an internal error that when returned means the result 48// is an unknown value. We use this for early exit. 49var errExitUnknown = errors.New("unknown value") 50 51func Eval(root ast.Node, config *EvalConfig) (EvaluationResult, error) { 52 output, outputType, err := internalEval(root, config) 53 if err != nil { 54 return InvalidResult, err 55 } 56 57 // If the result contains any nested unknowns then the result as a whole 58 // is unknown, so that callers only have to deal with "entirely known" 59 // or "entirely unknown" as outcomes. 60 if ast.IsUnknown(ast.Variable{Type: outputType, Value: output}) { 61 outputType = ast.TypeUnknown 62 output = UnknownValue 63 } 64 65 switch outputType { 66 case ast.TypeList: 67 val, err := VariableToInterface(ast.Variable{ 68 Type: ast.TypeList, 69 Value: output, 70 }) 71 return EvaluationResult{ 72 Type: TypeList, 73 Value: val, 74 }, err 75 case ast.TypeMap: 76 val, err := VariableToInterface(ast.Variable{ 77 Type: ast.TypeMap, 78 Value: output, 79 }) 80 return EvaluationResult{ 81 Type: TypeMap, 82 Value: val, 83 }, err 84 case ast.TypeString: 85 return EvaluationResult{ 86 Type: TypeString, 87 Value: output, 88 }, nil 89 case ast.TypeBool: 90 return EvaluationResult{ 91 Type: TypeBool, 92 Value: output, 93 }, nil 94 case ast.TypeUnknown: 95 return EvaluationResult{ 96 Type: TypeUnknown, 97 Value: UnknownValue, 98 }, nil 99 default: 100 return InvalidResult, fmt.Errorf("unknown type %s as interpolation output", outputType) 101 } 102} 103 104// Eval evaluates the given AST tree and returns its output value, the type 105// of the output, and any error that occurred. 106func internalEval(root ast.Node, config *EvalConfig) (interface{}, ast.Type, error) { 107 // Copy the scope so we can add our builtins 108 if config == nil { 109 config = new(EvalConfig) 110 } 111 scope := registerBuiltins(config.GlobalScope) 112 implicitMap := map[ast.Type]map[ast.Type]string{ 113 ast.TypeFloat: { 114 ast.TypeInt: "__builtin_FloatToInt", 115 ast.TypeString: "__builtin_FloatToString", 116 }, 117 ast.TypeInt: { 118 ast.TypeFloat: "__builtin_IntToFloat", 119 ast.TypeString: "__builtin_IntToString", 120 }, 121 ast.TypeString: { 122 ast.TypeInt: "__builtin_StringToInt", 123 ast.TypeFloat: "__builtin_StringToFloat", 124 ast.TypeBool: "__builtin_StringToBool", 125 }, 126 ast.TypeBool: { 127 ast.TypeString: "__builtin_BoolToString", 128 }, 129 } 130 131 // Build our own semantic checks that we always run 132 tv := &TypeCheck{Scope: scope, Implicit: implicitMap} 133 ic := &IdentifierCheck{Scope: scope} 134 135 // Build up the semantic checks for execution 136 checks := make( 137 []SemanticChecker, 138 len(config.SemanticChecks), 139 len(config.SemanticChecks)+2) 140 copy(checks, config.SemanticChecks) 141 checks = append(checks, ic.Visit) 142 checks = append(checks, tv.Visit) 143 144 // Run the semantic checks 145 for _, check := range checks { 146 if err := check(root); err != nil { 147 return nil, ast.TypeInvalid, err 148 } 149 } 150 151 // Execute 152 v := &evalVisitor{Scope: scope} 153 return v.Visit(root) 154} 155 156// EvalNode is the interface that must be implemented by any ast.Node 157// to support evaluation. This will be called in visitor pattern order. 158// The result of each call to Eval is automatically pushed onto the 159// stack as a LiteralNode. Pop elements off the stack to get child 160// values. 161type EvalNode interface { 162 Eval(ast.Scope, *ast.Stack) (interface{}, ast.Type, error) 163} 164 165type evalVisitor struct { 166 Scope ast.Scope 167 Stack ast.Stack 168 169 err error 170 lock sync.Mutex 171} 172 173func (v *evalVisitor) Visit(root ast.Node) (interface{}, ast.Type, error) { 174 // Run the actual visitor pattern 175 root.Accept(v.visit) 176 177 // Get our result and clear out everything else 178 var result *ast.LiteralNode 179 if v.Stack.Len() > 0 { 180 result = v.Stack.Pop().(*ast.LiteralNode) 181 } else { 182 result = new(ast.LiteralNode) 183 } 184 resultErr := v.err 185 if resultErr == errExitUnknown { 186 // This means the return value is unknown and we used the error 187 // as an early exit mechanism. Reset since the value on the stack 188 // should be the unknown value. 189 resultErr = nil 190 } 191 192 // Clear everything else so we aren't just dangling 193 v.Stack.Reset() 194 v.err = nil 195 196 t, err := result.Type(v.Scope) 197 if err != nil { 198 return nil, ast.TypeInvalid, err 199 } 200 201 return result.Value, t, resultErr 202} 203 204func (v *evalVisitor) visit(raw ast.Node) ast.Node { 205 if v.err != nil { 206 return raw 207 } 208 209 en, err := evalNode(raw) 210 if err != nil { 211 v.err = err 212 return raw 213 } 214 215 out, outType, err := en.Eval(v.Scope, &v.Stack) 216 if err != nil { 217 v.err = err 218 return raw 219 } 220 221 v.Stack.Push(&ast.LiteralNode{ 222 Value: out, 223 Typex: outType, 224 }) 225 226 if outType == ast.TypeUnknown { 227 // Halt immediately 228 v.err = errExitUnknown 229 return raw 230 } 231 232 return raw 233} 234 235// evalNode is a private function that returns an EvalNode for built-in 236// types as well as any other EvalNode implementations. 237func evalNode(raw ast.Node) (EvalNode, error) { 238 switch n := raw.(type) { 239 case *ast.Index: 240 return &evalIndex{n}, nil 241 case *ast.Call: 242 return &evalCall{n}, nil 243 case *ast.Conditional: 244 return &evalConditional{n}, nil 245 case *ast.Output: 246 return &evalOutput{n}, nil 247 case *ast.LiteralNode: 248 return &evalLiteralNode{n}, nil 249 case *ast.VariableAccess: 250 return &evalVariableAccess{n}, nil 251 default: 252 en, ok := n.(EvalNode) 253 if !ok { 254 return nil, fmt.Errorf("node doesn't support evaluation: %#v", raw) 255 } 256 257 return en, nil 258 } 259} 260 261type evalCall struct{ *ast.Call } 262 263func (v *evalCall) Eval(s ast.Scope, stack *ast.Stack) (interface{}, ast.Type, error) { 264 // Look up the function in the map 265 function, ok := s.LookupFunc(v.Func) 266 if !ok { 267 return nil, ast.TypeInvalid, fmt.Errorf( 268 "unknown function called: %s", v.Func) 269 } 270 271 // The arguments are on the stack in reverse order, so pop them off. 272 args := make([]interface{}, len(v.Args)) 273 for i, _ := range v.Args { 274 node := stack.Pop().(*ast.LiteralNode) 275 if node.IsUnknown() { 276 // If any arguments are unknown then the result is automatically unknown 277 return UnknownValue, ast.TypeUnknown, nil 278 } 279 args[len(v.Args)-1-i] = node.Value 280 } 281 282 // Call the function 283 result, err := function.Callback(args) 284 if err != nil { 285 return nil, ast.TypeInvalid, fmt.Errorf("%s: %s", v.Func, err) 286 } 287 288 return result, function.ReturnType, nil 289} 290 291type evalConditional struct{ *ast.Conditional } 292 293func (v *evalConditional) Eval(s ast.Scope, stack *ast.Stack) (interface{}, ast.Type, error) { 294 // On the stack we have literal nodes representing the resulting values 295 // of the condition, true and false expressions, but they are in reverse 296 // order. 297 falseLit := stack.Pop().(*ast.LiteralNode) 298 trueLit := stack.Pop().(*ast.LiteralNode) 299 condLit := stack.Pop().(*ast.LiteralNode) 300 301 if condLit.IsUnknown() { 302 // If our conditional is unknown then our result is also unknown 303 return UnknownValue, ast.TypeUnknown, nil 304 } 305 306 if condLit.Value.(bool) { 307 return trueLit.Value, trueLit.Typex, nil 308 } else { 309 return falseLit.Value, trueLit.Typex, nil 310 } 311} 312 313type evalIndex struct{ *ast.Index } 314 315func (v *evalIndex) Eval(scope ast.Scope, stack *ast.Stack) (interface{}, ast.Type, error) { 316 key := stack.Pop().(*ast.LiteralNode) 317 target := stack.Pop().(*ast.LiteralNode) 318 319 variableName := v.Index.Target.(*ast.VariableAccess).Name 320 321 if key.IsUnknown() { 322 // If our key is unknown then our result is also unknown 323 return UnknownValue, ast.TypeUnknown, nil 324 } 325 326 // For target, we'll accept collections containing unknown values but 327 // we still need to catch when the collection itself is unknown, shallowly. 328 if target.Typex == ast.TypeUnknown { 329 return UnknownValue, ast.TypeUnknown, nil 330 } 331 332 switch target.Typex { 333 case ast.TypeList: 334 return v.evalListIndex(variableName, target.Value, key.Value) 335 case ast.TypeMap: 336 return v.evalMapIndex(variableName, target.Value, key.Value) 337 default: 338 return nil, ast.TypeInvalid, fmt.Errorf( 339 "target %q for indexing must be ast.TypeList or ast.TypeMap, is %s", 340 variableName, target.Typex) 341 } 342} 343 344func (v *evalIndex) evalListIndex(variableName string, target interface{}, key interface{}) (interface{}, ast.Type, error) { 345 // We assume type checking was already done and we can assume that target 346 // is a list and key is an int 347 list, ok := target.([]ast.Variable) 348 if !ok { 349 return nil, ast.TypeInvalid, fmt.Errorf( 350 "cannot cast target to []Variable, is: %T", target) 351 } 352 353 keyInt, ok := key.(int) 354 if !ok { 355 return nil, ast.TypeInvalid, fmt.Errorf( 356 "cannot cast key to int, is: %T", key) 357 } 358 359 if len(list) == 0 { 360 return nil, ast.TypeInvalid, fmt.Errorf("list is empty") 361 } 362 363 if keyInt < 0 || len(list) < keyInt+1 { 364 return nil, ast.TypeInvalid, fmt.Errorf( 365 "index %d out of range for list %s (max %d)", 366 keyInt, variableName, len(list)) 367 } 368 369 returnVal := list[keyInt].Value 370 returnType := list[keyInt].Type 371 return returnVal, returnType, nil 372} 373 374func (v *evalIndex) evalMapIndex(variableName string, target interface{}, key interface{}) (interface{}, ast.Type, error) { 375 // We assume type checking was already done and we can assume that target 376 // is a map and key is a string 377 vmap, ok := target.(map[string]ast.Variable) 378 if !ok { 379 return nil, ast.TypeInvalid, fmt.Errorf( 380 "cannot cast target to map[string]Variable, is: %T", target) 381 } 382 383 keyString, ok := key.(string) 384 if !ok { 385 return nil, ast.TypeInvalid, fmt.Errorf( 386 "cannot cast key to string, is: %T", key) 387 } 388 389 if len(vmap) == 0 { 390 return nil, ast.TypeInvalid, fmt.Errorf("map is empty") 391 } 392 393 value, ok := vmap[keyString] 394 if !ok { 395 return nil, ast.TypeInvalid, fmt.Errorf( 396 "key %q does not exist in map %s", keyString, variableName) 397 } 398 399 return value.Value, value.Type, nil 400} 401 402type evalOutput struct{ *ast.Output } 403 404func (v *evalOutput) Eval(s ast.Scope, stack *ast.Stack) (interface{}, ast.Type, error) { 405 // The expressions should all be on the stack in reverse 406 // order. So pop them off, reverse their order, and concatenate. 407 nodes := make([]*ast.LiteralNode, 0, len(v.Exprs)) 408 haveUnknown := false 409 for range v.Exprs { 410 n := stack.Pop().(*ast.LiteralNode) 411 nodes = append(nodes, n) 412 413 // If we have any unknowns then the whole result is unknown 414 // (we must deal with this first, because the type checker can 415 // skip type conversions in the presence of unknowns, and thus 416 // any of our other nodes may be incorrectly typed.) 417 if n.IsUnknown() { 418 haveUnknown = true 419 } 420 } 421 422 if haveUnknown { 423 return UnknownValue, ast.TypeUnknown, nil 424 } 425 426 // Special case the single list and map 427 if len(nodes) == 1 { 428 switch t := nodes[0].Typex; t { 429 case ast.TypeList: 430 fallthrough 431 case ast.TypeMap: 432 fallthrough 433 case ast.TypeUnknown: 434 return nodes[0].Value, t, nil 435 } 436 } 437 438 // Otherwise concatenate the strings 439 var buf bytes.Buffer 440 for i := len(nodes) - 1; i >= 0; i-- { 441 if nodes[i].Typex != ast.TypeString { 442 return nil, ast.TypeInvalid, fmt.Errorf( 443 "invalid output with %s value at index %d: %#v", 444 nodes[i].Typex, 445 i, 446 nodes[i].Value, 447 ) 448 } 449 buf.WriteString(nodes[i].Value.(string)) 450 } 451 452 return buf.String(), ast.TypeString, nil 453} 454 455type evalLiteralNode struct{ *ast.LiteralNode } 456 457func (v *evalLiteralNode) Eval(ast.Scope, *ast.Stack) (interface{}, ast.Type, error) { 458 return v.Value, v.Typex, nil 459} 460 461type evalVariableAccess struct{ *ast.VariableAccess } 462 463func (v *evalVariableAccess) Eval(scope ast.Scope, _ *ast.Stack) (interface{}, ast.Type, error) { 464 // Look up the variable in the map 465 variable, ok := scope.LookupVar(v.Name) 466 if !ok { 467 return nil, ast.TypeInvalid, fmt.Errorf( 468 "unknown variable accessed: %s", v.Name) 469 } 470 471 return variable.Value, variable.Type, nil 472} 473