blob: d0ee27ae7981e69e1dc6faacd5db1254fe632650 [file] [log] [blame]
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +01001// 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
15package cue
16
17import (
18 "path"
19 "strconv"
20
21 "cuelang.org/go/cue/ast"
22 build "cuelang.org/go/cue/build"
23 "cuelang.org/go/cue/token"
24)
25
26// Build creates one Instance for each build.Instance. A returned Instance
27// may be incomplete, in which case its Err field is set.
28//
29// Example:
30// inst := cue.Build(load.Load(args))
31//
32func Build(instances []*build.Instance) []*Instance {
33 if len(instances) == 0 {
34 panic("cue: list of instances must not be empty")
35 }
36 index := newIndex(instances[0].Context().FileSet())
37
38 loaded := []*Instance{}
39
40 for _, p := range instances {
41 p.Complete()
42
43 loaded = append(loaded, index.loadInstance(p))
44 }
45 // TODO: insert imports
46 return loaded
47}
48
Marcel van Lohuizen57333362019-04-01 14:35:09 +020049// FromExpr creates an instance from an expression.
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010050// Any references must be resolved beforehand.
51func FromExpr(fset *token.FileSet, expr ast.Expr) (*Instance, error) {
52 i := newIndex(fset).NewInstance(nil)
53 err := i.insertFile(&ast.File{
54 Decls: []ast.Decl{&ast.EmitDecl{Expr: expr}},
55 })
56 if err != nil {
57 return nil, err
58 }
59 return i, nil
60}
61
62// index maps conversions from label names to internal codes.
63//
64// All instances belonging to the same package should share this index.
65type index struct {
66 fset *token.FileSet
67
68 labelMap map[string]label
69 labels []string
70
71 loaded map[*build.Instance]*Instance
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +020072
73 offset label
74 parent *index
75 freeze bool
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010076}
77
Marcel van Lohuizen46103912019-04-26 22:23:38 +020078const sharedOffset = 0x40000000
79
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +020080// sharedIndex is used for indexing builtins and any other labels common to
81// all instances.
82var sharedIndex = newSharedIndex(token.NewFileSet())
83
84func newSharedIndex(f *token.FileSet) *index {
Marcel van Lohuizen46103912019-04-26 22:23:38 +020085 // TODO: nasty hack to indicate FileSet of shared index. Remove the whole
86 // FileSet idea from the API. Just take the hit of the extra pointers for
87 // positions in the ast, and then optimize the storage in an abstract
88 // machine implementation for storing graphs.
89 f.AddFile("dummy", sharedOffset, 0)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010090 i := &index{
91 fset: f,
92 labelMap: map[string]label{"": 0},
93 labels: []string{""},
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +010094 }
95 return i
96}
97
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +020098// newIndex creates a new index.
99func newIndex(f *token.FileSet) *index {
100 parent := sharedIndex
101 i := &index{
102 fset: f,
103 labelMap: map[string]label{},
104 loaded: map[*build.Instance]*Instance{},
105 offset: label(len(parent.labels)) + parent.offset,
106 parent: parent,
107 }
108 parent.freeze = true
109 return i
110}
111
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100112func (idx *index) strLabel(str string) label {
113 return idx.label(str, false)
114}
115
116func (idx *index) nodeLabel(n ast.Node) (f label, ok bool) {
117 switch x := n.(type) {
118 case *ast.BasicLit:
119 name, ok := ast.LabelName(x)
120 return idx.label(name, false), ok
121 case *ast.Ident:
122 return idx.label(x.Name, true), true
123 }
124 return 0, false
125}
126
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200127func (idx *index) findLabel(s string) (f label, ok bool) {
128 for x := idx; x != nil; x = x.parent {
129 f, ok = x.labelMap[s]
130 if ok {
131 break
132 }
133 }
134 return f, ok
135}
136
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100137func (idx *index) label(s string, isIdent bool) label {
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200138 f, ok := idx.findLabel(s)
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100139 if !ok {
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200140 if idx.freeze {
141 panic("adding label to frozen index")
142 }
143 f = label(len(idx.labelMap)) + idx.offset
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100144 idx.labelMap[s] = f
145 idx.labels = append(idx.labels, s)
146 }
147 f <<= 1
148 if isIdent && s != "" && s[0] == '_' {
149 f |= 1
150 }
151 return f
152}
153
154func (idx *index) labelStr(l label) string {
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200155 l >>= 1
156 for ; l < idx.offset; idx = idx.parent {
157 }
158 return idx.labels[l-idx.offset]
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100159}
160
161func (idx *index) loadInstance(p *build.Instance) *Instance {
162 if inst := idx.loaded[p]; inst != nil {
163 if !inst.complete {
164 // cycles should be detected by the builder and it should not be
165 // possible to construct a build.Instance that has them.
166 panic("cue: cycle")
167 }
168 return inst
169 }
170 files := p.Files
171 inst := idx.NewInstance(p)
172 if inst.Err == nil {
173 // inst.instance.index.state = s
174 // inst.instance.inst = p
175 inst.Err = resolveFiles(idx, p)
176 for _, f := range files {
177 inst.insertFile(f)
178 }
179 }
180 inst.complete = true
181 return inst
182}
183
184func lineStr(idx *index, n ast.Node) string {
185 return idx.fset.Position(n.Pos()).String()
186}
187
188func resolveFiles(idx *index, p *build.Instance) error {
189 // Link top-level declarations. As top-level entries get unified, an entry
190 // may be linked to any top-level entry of any of the files.
191 allFields := map[string]ast.Node{}
192 for _, file := range p.Files {
193 for _, d := range file.Decls {
194 if f, ok := d.(*ast.Field); ok && f.Value != nil {
195 if ident, ok := f.Label.(*ast.Ident); ok {
196 allFields[ident.Name] = f.Value
197 }
198 }
199 }
200 }
201 for _, f := range p.Files {
202 if err := resolveFile(idx, f, p, allFields); err != nil {
203 return err
204 }
205 }
206 return nil
207}
208
209func resolveFile(idx *index, f *ast.File, p *build.Instance, allFields map[string]ast.Node) error {
210 type importInfo struct {
211 node ast.Node
212 inst *Instance
213 used bool // TODO: use a more general unresolved value technique
214 }
215 index := map[string][]*ast.Ident{}
216 for _, u := range f.Unresolved {
217 index[u.Name] = append(index[u.Name], u)
218 }
219 fields := map[string]ast.Node{}
220 for _, d := range f.Decls {
221 if f, ok := d.(*ast.Field); ok && f.Value != nil {
222 if ident, ok := f.Label.(*ast.Ident); ok {
223 fields[ident.Name] = d
224 }
225 }
226 }
227 var errUnused error
228
229 for _, spec := range f.Imports {
230 id, err := strconv.Unquote(spec.Path.Value)
231 if err != nil {
232 continue // quietly ignore the error
233 }
234 name := path.Base(id)
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200235 if imp := p.LookupImport(id); imp != nil {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100236 name = imp.PkgName
237 if spec.Name != nil {
238 name = spec.Name.Name
239 }
Marcel van Lohuizen8bc02e52019-04-01 13:14:07 +0200240 } else if _, ok := builtins[id]; !ok {
Marcel van Lohuizen17157ea2018-12-11 10:41:10 +0100241 // continue
242 return idx.mkErr(newNode(spec), "package %q not found", id)
243 }
244 if n, ok := fields[name]; ok {
245 return idx.mkErr(newNode(spec),
246 "%s redeclared as imported package name\n"+
247 "\tprevious declaration at %v", name, lineStr(idx, n))
248 }
249 used := false
250 for _, u := range index[name] {
251 used = true
252 u.Node = spec
253 }
254 if !used {
255 if spec.Name == nil {
256 errUnused = idx.mkErr(newNode(spec),
257 "imported and not used: %s", spec.Path.Value)
258 } else {
259 errUnused = idx.mkErr(newNode(spec),
260 "imported and not used: %s as %s", spec.Path.Value, spec.Name)
261 }
262 }
263 }
264 i := 0
265 for _, u := range f.Unresolved {
266 if u.Node != nil {
267 continue
268 }
269 if n, ok := allFields[u.Name]; ok {
270 u.Node = n
271 u.Scope = f
272 continue
273 }
274 f.Unresolved[i] = u
275 i++
276 }
277 f.Unresolved = f.Unresolved[:i]
278 // TODO: also need to resolve types.
279 // if len(f.Unresolved) > 0 {
280 // n := f.Unresolved[0]
281 // return ctx.mkErr(newBase(n), "unresolved reference %s", n.Name)
282 // }
283 if errUnused != nil {
284 return errUnused
285 }
286 return nil
287}