1// Copyright 2018 The CUE Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15// This file implements scopes and the objects they contain. 16 17package astutil 18 19import ( 20 "bytes" 21 "fmt" 22 23 "cuelang.org/go/cue/ast" 24 "cuelang.org/go/cue/token" 25) 26 27// An ErrFunc processes errors. 28type ErrFunc func(pos token.Pos, msg string, args ...interface{}) 29 30// TODO: future development 31// 32// Resolution currently assigns values along the table below. This is based on 33// Go's resolver and is not quite convenient for CUE's purposes. For one, CUE 34// allows manually setting resolution and than call astutil.Sanitize to 35// normalize the ast.File. Manually assigning resolutions according to the 36// below table is rather tedious though. 37// 38// Instead of using the Scope and Node fields in identifiers, we suggest the 39// following assignments: 40// 41// Reference Node // an Decl or Clause 42// Ident *Ident // The identifier in References (optional) 43// 44// References always refers to the direct element in the scope in which the 45// identifier occurs, not the final value, so: *Field, *LetClause, *ForClause, 46// etc. In case Ident is defined, it must be the same pointer as the 47// referencing identifier. In case it is not defined, the Name of the 48// referencing identifier can be used to locate the proper identifier in the 49// referenced node. 50// 51// The Scope field in the original design then loses its function. 52// 53// Type of reference Scope Node 54// Let Clause File/Struct LetClause 55// Alias declaration File/Struct Alias (deprecated) 56// Illegal Reference File/Struct 57// Value 58// X in a: X=y Field Alias 59// Fields 60// X in X: y File/Struct Expr (y) 61// X in X=x: y File/Struct Field 62// X in X=(x): y File/Struct Field 63// X in X="\(x)": y File/Struct Field 64// X in [X=x]: y Field Expr (x) 65// X in X=[x]: y Field Field 66// 67// for k, v in ForClause Ident 68// let x = y LetClause Ident 69// 70// Fields inside lambda 71// Label Field Expr 72// Value Field Field 73// Pkg nil ImportSpec 74 75// Resolve resolves all identifiers in a file. Unresolved identifiers are 76// recorded in Unresolved. It will not overwrite already resolved values. 77func Resolve(f *ast.File, errFn ErrFunc) { 78 walk(&scope{errFn: errFn, identFn: resolveIdent}, f) 79} 80 81// Resolve resolves all identifiers in an expression. 82// It will not overwrite already resolved values. 83func ResolveExpr(e ast.Expr, errFn ErrFunc) { 84 f := &ast.File{} 85 walk(&scope{file: f, errFn: errFn, identFn: resolveIdent}, e) 86} 87 88// A Scope maintains the set of named language entities declared 89// in the scope and a link to the immediately surrounding (outer) 90// scope. 91// 92type scope struct { 93 file *ast.File 94 outer *scope 95 node ast.Node 96 index map[string]entry 97 inField bool 98 99 identFn func(s *scope, n *ast.Ident) bool 100 nameFn func(name string) 101 errFn func(p token.Pos, msg string, args ...interface{}) 102} 103 104type entry struct { 105 node ast.Node 106 link ast.Node // Alias, LetClause, or Field 107} 108 109func newScope(f *ast.File, outer *scope, node ast.Node, decls []ast.Decl) *scope { 110 const n = 4 // initial scope capacity 111 s := &scope{ 112 file: f, 113 outer: outer, 114 node: node, 115 index: make(map[string]entry, n), 116 identFn: outer.identFn, 117 nameFn: outer.nameFn, 118 errFn: outer.errFn, 119 } 120 for _, d := range decls { 121 switch x := d.(type) { 122 case *ast.Field: 123 label := x.Label 124 125 if a, ok := x.Label.(*ast.Alias); ok { 126 // TODO(legacy): use name := a.Ident.Name once quoted 127 // identifiers are no longer supported. 128 label, _ = a.Expr.(ast.Label) 129 if name, _, _ := ast.LabelName(a.Ident); name != "" { 130 if _, ok := label.(*ast.ListLit); !ok { 131 s.insert(name, x, a) 132 } 133 } 134 } 135 136 // default: 137 name, isIdent, _ := ast.LabelName(label) 138 if isIdent { 139 v := x.Value 140 // Avoid interpreting value aliases at this point. 141 if a, ok := v.(*ast.Alias); ok { 142 v = a.Expr 143 } 144 s.insert(name, v, x) 145 } 146 case *ast.LetClause: 147 name, isIdent, _ := ast.LabelName(x.Ident) 148 if isIdent { 149 s.insert(name, x, x) 150 } 151 case *ast.Alias: 152 name, isIdent, _ := ast.LabelName(x.Ident) 153 if isIdent { 154 s.insert(name, x, x) 155 } 156 case *ast.ImportDecl: 157 for _, spec := range x.Specs { 158 info, _ := ParseImportSpec(spec) 159 s.insert(info.Ident, spec, spec) 160 } 161 } 162 } 163 return s 164} 165 166func (s *scope) isLet(n ast.Node) bool { 167 if _, ok := s.node.(*ast.Field); ok { 168 return true 169 } 170 switch n.(type) { 171 case *ast.LetClause, *ast.Alias, *ast.Field: 172 return true 173 } 174 return false 175} 176 177func (s *scope) mustBeUnique(n ast.Node) bool { 178 if _, ok := s.node.(*ast.Field); ok { 179 return true 180 } 181 switch n.(type) { 182 // TODO: add *ast.ImportSpec when some implementations are moved over to 183 // Sanitize. 184 case *ast.ImportSpec, *ast.LetClause, *ast.Alias, *ast.Field: 185 return true 186 } 187 return false 188} 189 190func (s *scope) insert(name string, n, link ast.Node) { 191 if name == "" { 192 return 193 } 194 if s.nameFn != nil { 195 s.nameFn(name) 196 } 197 // TODO: record both positions. 198 if outer, _, existing := s.lookup(name); existing.node != nil { 199 if s.isLet(n) != outer.isLet(existing.node) { 200 s.errFn(n.Pos(), "cannot have both alias and field with name %q in same scope", name) 201 return 202 } else if s.mustBeUnique(n) || outer.mustBeUnique(existing.node) { 203 if outer == s { 204 if _, ok := existing.node.(*ast.ImportSpec); ok { 205 return 206 // TODO: 207 s.errFn(n.Pos(), "conflicting declaration %s\n"+ 208 "\tprevious declaration at %s", 209 name, existing.node.Pos()) 210 } else { 211 s.errFn(n.Pos(), "alias %q redeclared in same scope", name) 212 } 213 return 214 } 215 // TODO: Should we disallow shadowing of aliases? 216 // This was the case, but it complicates the transition to 217 // square brackets. The spec says allow it. 218 // s.errFn(n.Pos(), "alias %q already declared in enclosing scope", name) 219 } 220 } 221 s.index[name] = entry{node: n, link: link} 222} 223 224func (s *scope) resolveScope(name string, node ast.Node) (scope ast.Node, e entry, ok bool) { 225 last := s 226 for s != nil { 227 if n, ok := s.index[name]; ok && node == n.node { 228 if last.node == n.node { 229 return nil, n, true 230 } 231 return s.node, n, true 232 } 233 s, last = s.outer, s 234 } 235 return nil, entry{}, false 236} 237 238func (s *scope) lookup(name string) (p *scope, obj ast.Node, node entry) { 239 // TODO(#152): consider returning nil for obj if it is a reference to root. 240 // last := s 241 for s != nil { 242 if n, ok := s.index[name]; ok { 243 if _, ok := n.node.(*ast.ImportSpec); ok { 244 return s, nil, n 245 } 246 return s, s.node, n 247 } 248 // s, last = s.outer, s 249 s = s.outer 250 } 251 return nil, nil, entry{} 252} 253 254func (s *scope) After(n ast.Node) {} 255func (s *scope) Before(n ast.Node) (w visitor) { 256 switch x := n.(type) { 257 case *ast.File: 258 s := newScope(x, s, x, x.Decls) 259 // Support imports. 260 for _, d := range x.Decls { 261 walk(s, d) 262 } 263 return nil 264 265 case *ast.StructLit: 266 return newScope(s.file, s, x, x.Elts) 267 268 case *ast.Comprehension: 269 s = scopeClauses(s, x.Clauses) 270 walk(s, x.Value) 271 return nil 272 273 case *ast.Field: 274 var n ast.Node = x.Label 275 alias, ok := x.Label.(*ast.Alias) 276 if ok { 277 n = alias.Expr 278 } 279 280 switch label := n.(type) { 281 case *ast.ParenExpr: 282 walk(s, label) 283 284 case *ast.Interpolation: 285 walk(s, label) 286 287 case *ast.ListLit: 288 if len(label.Elts) != 1 { 289 break 290 } 291 s = newScope(s.file, s, x, nil) 292 if alias != nil { 293 if name, _, _ := ast.LabelName(alias.Ident); name != "" { 294 s.insert(name, x, alias) 295 } 296 } 297 298 expr := label.Elts[0] 299 300 if a, ok := expr.(*ast.Alias); ok { 301 expr = a.Expr 302 303 // Add to current scope, instead of the value's, and allow 304 // references to bind to these illegally. 305 // We need this kind of administration anyway to detect 306 // illegal name clashes, and it allows giving better error 307 // messages. This puts the burdon on clients of this library 308 // to detect illegal usage, though. 309 name, err := ast.ParseIdent(a.Ident) 310 if err == nil { 311 s.insert(name, a.Expr, a) 312 } 313 } 314 315 ast.Walk(expr, nil, func(n ast.Node) { 316 if x, ok := n.(*ast.Ident); ok { 317 for s := s; s != nil && !s.inField; s = s.outer { 318 if _, ok := s.index[x.Name]; ok { 319 s.errFn(n.Pos(), 320 "reference %q in label expression refers to field against which it would be matched", x.Name) 321 } 322 } 323 } 324 }) 325 walk(s, expr) 326 } 327 328 if n := x.Value; n != nil { 329 if alias, ok := x.Value.(*ast.Alias); ok { 330 // TODO: this should move into Before once decl attributes 331 // have been fully deprecated and embed attributes are introduced. 332 s = newScope(s.file, s, x, nil) 333 s.insert(alias.Ident.Name, alias, x) 334 n = alias.Expr 335 } 336 s.inField = true 337 walk(s, n) 338 s.inField = false 339 } 340 341 return nil 342 343 case *ast.LetClause: 344 // Disallow referring to the current LHS name. 345 name := x.Ident.Name 346 saved := s.index[name] 347 delete(s.index, name) // The same name may still appear in another scope 348 349 if x.Expr != nil { 350 walk(s, x.Expr) 351 } 352 s.index[name] = saved 353 return nil 354 355 case *ast.Alias: 356 // Disallow referring to the current LHS name. 357 name := x.Ident.Name 358 saved := s.index[name] 359 delete(s.index, name) // The same name may still appear in another scope 360 361 if x.Expr != nil { 362 walk(s, x.Expr) 363 } 364 s.index[name] = saved 365 return nil 366 367 case *ast.ImportSpec: 368 return nil 369 370 case *ast.Attribute: 371 // TODO: tokenize attributes, resolve identifiers and store the ones 372 // that resolve in a list. 373 374 case *ast.SelectorExpr: 375 walk(s, x.X) 376 return nil 377 378 case *ast.Ident: 379 if s.identFn(s, x) { 380 return nil 381 } 382 } 383 return s 384} 385 386func resolveIdent(s *scope, x *ast.Ident) bool { 387 name, ok, _ := ast.LabelName(x) 388 if !ok { 389 // TODO: generate error 390 return false 391 } 392 if _, obj, node := s.lookup(name); node.node != nil { 393 switch { 394 case x.Node == nil: 395 x.Node = node.node 396 x.Scope = obj 397 398 case x.Node == node.node: 399 x.Scope = obj 400 401 default: // x.Node != node 402 scope, _, ok := s.resolveScope(name, x.Node) 403 if !ok { 404 s.file.Unresolved = append(s.file.Unresolved, x) 405 } 406 x.Scope = scope 407 } 408 } else { 409 s.file.Unresolved = append(s.file.Unresolved, x) 410 } 411 return true 412} 413 414func scopeClauses(s *scope, clauses []ast.Clause) *scope { 415 for _, c := range clauses { 416 switch x := c.(type) { 417 case *ast.ForClause: 418 walk(s, x.Source) 419 s = newScope(s.file, s, x, nil) 420 if x.Key != nil { 421 name, err := ast.ParseIdent(x.Key) 422 if err == nil { 423 s.insert(name, x.Key, x) 424 } 425 } 426 name, err := ast.ParseIdent(x.Value) 427 if err == nil { 428 s.insert(name, x.Value, x) 429 } 430 431 case *ast.LetClause: 432 walk(s, x.Expr) 433 s = newScope(s.file, s, x, nil) 434 name, err := ast.ParseIdent(x.Ident) 435 if err == nil { 436 s.insert(name, x.Ident, x) 437 } 438 439 default: 440 walk(s, c) 441 } 442 } 443 return s 444} 445 446// Debugging support 447func (s *scope) String() string { 448 var buf bytes.Buffer 449 fmt.Fprintf(&buf, "scope %p {", s) 450 if s != nil && len(s.index) > 0 { 451 fmt.Fprintln(&buf) 452 for name := range s.index { 453 fmt.Fprintf(&buf, "\t%v\n", name) 454 } 455 } 456 fmt.Fprintf(&buf, "}\n") 457 return buf.String() 458} 459