| // Copyright 2021 The Tint Authors. | |
| // | |
| // Licensed under the Apache License, Version 2.0 (the "License"); | |
| // you may not use this file except in compliance with the License. | |
| // You may obtain a copy of the License at | |
| // | |
| // http://www.apache.org/licenses/LICENSE-2.0 | |
| // | |
| // Unless required by applicable law or agreed to in writing, software | |
| // distributed under the License is distributed on an "AS IS" BASIS, | |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| // See the License for the specific language governing permissions and | |
| // limitations under the License. | |
| package resolver | |
| import ( | |
| "fmt" | |
| "sort" | |
| "dawn.googlesource.com/dawn/tools/src/cmd/builtin-gen/ast" | |
| "dawn.googlesource.com/dawn/tools/src/cmd/builtin-gen/sem" | |
| "dawn.googlesource.com/dawn/tools/src/cmd/builtin-gen/tok" | |
| ) | |
| type resolver struct { | |
| a *ast.AST | |
| s *sem.Sem | |
| globals scope | |
| functions map[string]*sem.Function | |
| enumEntryMatchers map[*sem.EnumEntry]*sem.EnumMatcher | |
| } | |
| // Resolve processes the AST | |
| func Resolve(a *ast.AST) (*sem.Sem, error) { | |
| r := resolver{ | |
| a: a, | |
| s: sem.New(), | |
| globals: newScope(nil), | |
| functions: map[string]*sem.Function{}, | |
| enumEntryMatchers: map[*sem.EnumEntry]*sem.EnumMatcher{}, | |
| } | |
| // Declare and resolve all the enumerators | |
| for _, e := range a.Enums { | |
| if err := r.enum(e); err != nil { | |
| return nil, err | |
| } | |
| } | |
| // Declare and resolve all the ty types | |
| for _, p := range a.Types { | |
| if err := r.ty(p); err != nil { | |
| return nil, err | |
| } | |
| } | |
| // Declare and resolve the type matchers | |
| for _, m := range a.Matchers { | |
| if err := r.matcher(m); err != nil { | |
| return nil, err | |
| } | |
| } | |
| // Declare and resolve the functions | |
| for _, f := range a.Functions { | |
| if err := r.function(f); err != nil { | |
| return nil, err | |
| } | |
| } | |
| // Calculate the unique parameter names | |
| r.s.UniqueParameterNames = r.calculateUniqueParameterNames() | |
| return r.s, nil | |
| } | |
| // enum() resolves an enum declaration. | |
| // The resulting sem.Enum is appended to Sem.Enums, and the enum and all its | |
| // entries are registered with the global scope. | |
| func (r *resolver) enum(e ast.EnumDecl) error { | |
| s := &sem.Enum{ | |
| Decl: e, | |
| Name: e.Name, | |
| } | |
| // Register the enum | |
| r.s.Enums = append(r.s.Enums, s) | |
| if err := r.globals.declare(s, e.Source); err != nil { | |
| return err | |
| } | |
| // Register each of the enum entries | |
| for _, ast := range e.Entries { | |
| entry := &sem.EnumEntry{ | |
| Name: ast.Name, | |
| Enum: s, | |
| } | |
| if internal := ast.Decorations.Take("internal"); internal != nil { | |
| entry.IsInternal = true | |
| if len(internal.Values) != 0 { | |
| return fmt.Errorf("%v unexpected value for internal decoration", ast.Source) | |
| } | |
| } | |
| if len(ast.Decorations) != 0 { | |
| return fmt.Errorf("%v unknown decoration", ast.Decorations[0].Source) | |
| } | |
| if err := r.globals.declare(entry, e.Source); err != nil { | |
| return err | |
| } | |
| s.Entries = append(s.Entries, entry) | |
| } | |
| return nil | |
| } | |
| // ty() resolves a type declaration. | |
| // The resulting sem.Type is appended to Sem.Types, and the type is registered | |
| // with the global scope. | |
| func (r *resolver) ty(a ast.TypeDecl) error { | |
| t := &sem.Type{ | |
| Decl: a, | |
| Name: a.Name, | |
| } | |
| // Register the type | |
| r.s.Types = append(r.s.Types, t) | |
| if err := r.globals.declare(t, a.Source); err != nil { | |
| return err | |
| } | |
| // Create a new scope for resolving template parameters | |
| s := newScope(&r.globals) | |
| // Resolve the type template parameters | |
| templateParams, err := r.templateParams(&s, a.TemplateParams) | |
| if err != nil { | |
| return err | |
| } | |
| t.TemplateParams = templateParams | |
| // Scan for decorations | |
| if d := a.Decorations.Take("display"); d != nil { | |
| if len(d.Values) != 1 { | |
| return fmt.Errorf("%v expected a single value for 'display' decoration", d.Source) | |
| } | |
| t.DisplayName = d.Values[0] | |
| } | |
| if len(a.Decorations) != 0 { | |
| return fmt.Errorf("%v unknown decoration", a.Decorations[0].Source) | |
| } | |
| return nil | |
| } | |
| // matcher() resolves a match declaration to either a sem.TypeMatcher or | |
| // sem.EnumMatcher. | |
| // The resulting matcher is appended to either Sem.TypeMatchers or | |
| // Sem.EnumMatchers, and is registered with the global scope. | |
| func (r *resolver) matcher(a ast.MatcherDecl) error { | |
| // Determine whether this is a type matcher or enum matcher by resolving the | |
| // first option | |
| firstOption, err := r.lookupNamed(&r.globals, a.Options[0]) | |
| if err != nil { | |
| return err | |
| } | |
| // Resolve to a sem.TypeMatcher or a sem.EnumMatcher | |
| switch firstOption := firstOption.(type) { | |
| case *sem.Type: | |
| options := map[sem.Named]tok.Source{} | |
| m := &sem.TypeMatcher{ | |
| Decl: a, | |
| Name: a.Name, | |
| } | |
| // Register the matcher | |
| r.s.TypeMatchers = append(r.s.TypeMatchers, m) | |
| if err := r.globals.declare(m, a.Source); err != nil { | |
| return err | |
| } | |
| // Resolve each of the types in the options list | |
| for _, ast := range m.Decl.Options { | |
| ty, err := r.lookupType(&r.globals, ast) | |
| if err != nil { | |
| return err | |
| } | |
| m.Types = append(m.Types, ty) | |
| if s, dup := options[ty]; dup { | |
| return fmt.Errorf("%v duplicate option '%v' in matcher\nFirst declared here: %v", ast.Source, ast.Name, s) | |
| } | |
| options[ty] = ast.Source | |
| } | |
| return nil | |
| case *sem.EnumEntry: | |
| enum := firstOption.Enum | |
| m := &sem.EnumMatcher{ | |
| Decl: a, | |
| Name: a.Name, | |
| Enum: enum, | |
| } | |
| // Register the matcher | |
| r.s.EnumMatchers = append(r.s.EnumMatchers, m) | |
| if err := r.globals.declare(m, a.Source); err != nil { | |
| return err | |
| } | |
| // Resolve each of the enums in the options list | |
| for _, ast := range m.Decl.Options { | |
| entry := enum.FindEntry(ast.Name) | |
| if entry == nil { | |
| return fmt.Errorf("%v enum '%v' does not contain '%v'", ast.Source, enum.Name, ast.Name) | |
| } | |
| m.Options = append(m.Options, entry) | |
| } | |
| return nil | |
| } | |
| return fmt.Errorf("'%v' cannot be used for matcher", a.Name) | |
| } | |
| // function() resolves a function overload declaration. | |
| // The the first overload for the function creates and appends the sem.Function | |
| // to Sem.Functions. Subsequent overloads append their resolved overload to the | |
| // sem.Function.Overloads list. | |
| func (r *resolver) function(a ast.FunctionDecl) error { | |
| // If this is the first overload of the function, create and register the | |
| // semantic function. | |
| f := r.functions[a.Name] | |
| if f == nil { | |
| f = &sem.Function{Name: a.Name} | |
| r.functions[a.Name] = f | |
| r.s.Functions = append(r.s.Functions, f) | |
| } | |
| // Create a new scope for resolving template parameters | |
| s := newScope(&r.globals) | |
| // Resolve the declared template parameters | |
| templateParams, err := r.templateParams(&s, a.TemplateParams) | |
| if err != nil { | |
| return err | |
| } | |
| // Construct the semantic overload | |
| overload := &sem.Overload{ | |
| Decl: a, | |
| Function: f, | |
| Parameters: make([]sem.Parameter, len(a.Parameters)), | |
| TemplateParams: templateParams, | |
| } | |
| // Process overload decorations | |
| if stageDeco := a.Decorations.Take("stage"); stageDeco != nil { | |
| for stageDeco != nil { | |
| for _, stage := range stageDeco.Values { | |
| switch stage { | |
| case "vertex": | |
| overload.CanBeUsedInStage.Vertex = true | |
| case "fragment": | |
| overload.CanBeUsedInStage.Fragment = true | |
| case "compute": | |
| overload.CanBeUsedInStage.Compute = true | |
| default: | |
| return fmt.Errorf("%v unknown stage '%v'", stageDeco.Source, stage) | |
| } | |
| } | |
| stageDeco = a.Decorations.Take("stage") | |
| } | |
| } else { | |
| overload.CanBeUsedInStage = sem.StageUses{ | |
| Vertex: true, | |
| Fragment: true, | |
| Compute: true, | |
| } | |
| } | |
| if deprecated := a.Decorations.Take("deprecated"); deprecated != nil { | |
| overload.IsDeprecated = true | |
| if len(deprecated.Values) != 0 { | |
| return fmt.Errorf("%v unexpected value for deprecated decoration", deprecated.Source) | |
| } | |
| } | |
| if len(a.Decorations) != 0 { | |
| return fmt.Errorf("%v unknown decoration", a.Decorations[0].Source) | |
| } | |
| // Append the overload to the function | |
| f.Overloads = append(f.Overloads, overload) | |
| // Sort the template parameters by resolved type. Append these to | |
| // sem.Overload.OpenTypes or sem.Overload.OpenNumbers based on their kind. | |
| for _, param := range templateParams { | |
| switch param := param.(type) { | |
| case *sem.TemplateTypeParam: | |
| overload.OpenTypes = append(overload.OpenTypes, param) | |
| case *sem.TemplateEnumParam, *sem.TemplateNumberParam: | |
| overload.OpenNumbers = append(overload.OpenNumbers, param) | |
| } | |
| } | |
| // Update high-water marks of open types / numbers | |
| if r.s.MaxOpenTypes < len(overload.OpenTypes) { | |
| r.s.MaxOpenTypes = len(overload.OpenTypes) | |
| } | |
| if r.s.MaxOpenNumbers < len(overload.OpenNumbers) { | |
| r.s.MaxOpenNumbers = len(overload.OpenNumbers) | |
| } | |
| // Resolve the parameters | |
| for i, p := range a.Parameters { | |
| usage, err := r.fullyQualifiedName(&s, p.Type) | |
| if err != nil { | |
| return err | |
| } | |
| overload.Parameters[i] = sem.Parameter{ | |
| Name: p.Name, | |
| Type: usage, | |
| } | |
| } | |
| // Resolve the return type | |
| if a.ReturnType != nil { | |
| usage, err := r.fullyQualifiedName(&s, *a.ReturnType) | |
| if err != nil { | |
| return err | |
| } | |
| switch usage.Target.(type) { | |
| case *sem.Type, *sem.TemplateTypeParam: | |
| overload.ReturnType = &usage | |
| default: | |
| return fmt.Errorf("%v cannot use '%v' as return type. Must be a type or template type", a.ReturnType.Source, a.ReturnType.Name) | |
| } | |
| } | |
| return nil | |
| } | |
| // fullyQualifiedName() resolves the ast.TemplatedName to a sem.FullyQualifiedName. | |
| func (r *resolver) fullyQualifiedName(s *scope, arg ast.TemplatedName) (sem.FullyQualifiedName, error) { | |
| target, err := r.lookupNamed(s, arg) | |
| if err != nil { | |
| return sem.FullyQualifiedName{}, err | |
| } | |
| if entry, ok := target.(*sem.EnumEntry); ok { | |
| // The target resolved to an enum entry. | |
| // Automagically transform this into a synthetic matcher with a single | |
| // option. i.e. | |
| // This: | |
| // enum E{ a b c } | |
| // fn F(b) | |
| // Becomes: | |
| // enum E{ a b c } | |
| // matcher b | |
| // fn F(b) | |
| // We don't really care right now that we have a symbol collision | |
| // between E.b and b, as the generators return different names for | |
| // these. | |
| matcher, ok := r.enumEntryMatchers[entry] | |
| if !ok { | |
| matcher = &sem.EnumMatcher{ | |
| Name: entry.Name, | |
| Enum: entry.Enum, | |
| Options: []*sem.EnumEntry{entry}, | |
| } | |
| r.enumEntryMatchers[entry] = matcher | |
| r.s.EnumMatchers = append(r.s.EnumMatchers, matcher) | |
| } | |
| target = matcher | |
| } | |
| fqn := sem.FullyQualifiedName{ | |
| Target: target, | |
| TemplateArguments: make([]interface{}, len(arg.TemplateArgs)), | |
| } | |
| for i, a := range arg.TemplateArgs { | |
| arg, err := r.fullyQualifiedName(s, a) | |
| if err != nil { | |
| return sem.FullyQualifiedName{}, err | |
| } | |
| fqn.TemplateArguments[i] = arg | |
| } | |
| return fqn, nil | |
| } | |
| // templateParams() resolves the ast.TemplateParams into list of sem.TemplateParam. | |
| // Each sem.TemplateParam is registered with the scope s. | |
| func (r *resolver) templateParams(s *scope, l ast.TemplateParams) ([]sem.TemplateParam, error) { | |
| out := []sem.TemplateParam{} | |
| for _, ast := range l { | |
| param, err := r.templateParam(ast) | |
| if err != nil { | |
| return nil, err | |
| } | |
| s.declare(param, ast.Source) | |
| out = append(out, param) | |
| } | |
| return out, nil | |
| } | |
| // templateParams() resolves the ast.TemplateParam into sem.TemplateParam, which | |
| // is either a sem.TemplateEnumParam or a sem.TemplateTypeParam. | |
| func (r *resolver) templateParam(a ast.TemplateParam) (sem.TemplateParam, error) { | |
| if a.Type.Name == "num" { | |
| return &sem.TemplateNumberParam{Name: a.Name}, nil | |
| } | |
| if a.Type.Name != "" { | |
| resolved, err := r.lookupNamed(&r.globals, a.Type) | |
| if err != nil { | |
| return nil, err | |
| } | |
| switch r := resolved.(type) { | |
| case *sem.Enum: | |
| return &sem.TemplateEnumParam{Name: a.Name, Enum: r}, nil | |
| case *sem.EnumMatcher: | |
| return &sem.TemplateEnumParam{Name: a.Name, Enum: r.Enum, Matcher: r}, nil | |
| case *sem.TypeMatcher: | |
| return &sem.TemplateTypeParam{Name: a.Name, Type: r}, nil | |
| default: | |
| return nil, fmt.Errorf("%v invalid template parameter type '%v'", a.Source, a.Type.Name) | |
| } | |
| } | |
| return &sem.TemplateTypeParam{Name: a.Name}, nil | |
| } | |
| // lookupType() searches the scope `s` and its ancestors for the sem.Type with | |
| // the given name. | |
| func (r *resolver) lookupType(s *scope, a ast.TemplatedName) (*sem.Type, error) { | |
| resolved, err := r.lookupNamed(s, a) | |
| if err != nil { | |
| return nil, err | |
| } | |
| // Something with the given name was found... | |
| if ty, ok := resolved.(*sem.Type); ok { | |
| return ty, nil | |
| } | |
| // ... but that something was not a sem.Type | |
| return nil, fmt.Errorf("%v '%v' resolves to %v but type is expected", a.Source, a.Name, describe(resolved)) | |
| } | |
| // lookupNamed() searches `s` and its ancestors for the sem.Named object with | |
| // the given name. If there are template arguments for the name `a`, then | |
| // lookupNamed() performs basic validation that those arguments can be passed | |
| // to the named object. | |
| func (r *resolver) lookupNamed(s *scope, a ast.TemplatedName) (sem.Named, error) { | |
| target := s.lookup(a.Name) | |
| if target == nil { | |
| return nil, fmt.Errorf("%v cannot resolve '%v'", a.Source, a.Name) | |
| } | |
| // Something with the given name was found... | |
| var params []sem.TemplateParam | |
| var ty sem.ResolvableType | |
| switch target := target.object.(type) { | |
| case *sem.Type: | |
| ty = target | |
| params = target.TemplateParams | |
| case *sem.TypeMatcher: | |
| ty = target | |
| params = target.TemplateParams | |
| case sem.TemplateParam: | |
| if len(a.TemplateArgs) != 0 { | |
| return nil, fmt.Errorf("%v '%v' template parameters do not accept template arguments", a.Source, a.Name) | |
| } | |
| return target.(sem.Named), nil | |
| case sem.Named: | |
| return target, nil | |
| default: | |
| panic(fmt.Errorf("Unknown resolved type %T", target)) | |
| } | |
| // ... and that something takes template parameters | |
| // Check the number of templated name template arguments match the number of | |
| // templated parameters for the target. | |
| args := a.TemplateArgs | |
| if len(params) != len(args) { | |
| return nil, fmt.Errorf("%v '%v' requires %d template arguments, but %d were provided", a.Source, a.Name, len(params), len(args)) | |
| } | |
| // Check templated name template argument kinds match the parameter kinds | |
| for i, ast := range args { | |
| param := params[i] | |
| arg, err := r.lookupNamed(s, args[i]) | |
| if err != nil { | |
| return nil, err | |
| } | |
| if err := checkCompatible(arg, param); err != nil { | |
| return nil, fmt.Errorf("%v %w", ast.Source, err) | |
| } | |
| } | |
| return ty, nil | |
| } | |
| // calculateUniqueParameterNames() iterates over all the parameters of all | |
| // overloads, calculating the list of unique parameter names | |
| func (r *resolver) calculateUniqueParameterNames() []string { | |
| set := map[string]struct{}{"": {}} | |
| names := []string{} | |
| for _, f := range r.s.Functions { | |
| for _, o := range f.Overloads { | |
| for _, p := range o.Parameters { | |
| if _, dup := set[p.Name]; !dup { | |
| set[p.Name] = struct{}{} | |
| names = append(names, p.Name) | |
| } | |
| } | |
| } | |
| } | |
| sort.Strings(names) | |
| return names | |
| } | |
| // describe() returns a string describing a sem.Named | |
| func describe(n sem.Named) string { | |
| switch n := n.(type) { | |
| case *sem.Type: | |
| return "type '" + n.Name + "'" | |
| case *sem.TypeMatcher: | |
| return "type matcher '" + n.Name + "'" | |
| case *sem.Enum: | |
| return "enum '" + n.Name + "'" | |
| case *sem.EnumMatcher: | |
| return "enum matcher '" + n.Name + "'" | |
| case *sem.TemplateTypeParam: | |
| return "template type" | |
| case *sem.TemplateEnumParam: | |
| return "template enum '" + n.Enum.Name + "'" | |
| case *sem.EnumEntry: | |
| return "enum entry '" + n.Enum.Name + "." + n.Name + "'" | |
| case *sem.TemplateNumberParam: | |
| return "template number" | |
| default: | |
| panic(fmt.Errorf("unhandled type %T", n)) | |
| } | |
| } | |
| // checkCompatible() returns an error if `arg` cannot be used as an argument for | |
| // a parameter of `param`. | |
| func checkCompatible(arg, param sem.Named) error { | |
| // asEnum() returns the underlying sem.Enum if n is a enum matcher, | |
| // templated enum parameter or an enum entry, otherwise nil | |
| asEnum := func(n sem.Named) *sem.Enum { | |
| switch n := n.(type) { | |
| case *sem.EnumMatcher: | |
| return n.Enum | |
| case *sem.TemplateEnumParam: | |
| return n.Enum | |
| case *sem.EnumEntry: | |
| return n.Enum | |
| default: | |
| return nil | |
| } | |
| } | |
| if arg := asEnum(arg); arg != nil { | |
| param := asEnum(param) | |
| if arg == param { | |
| return nil | |
| } | |
| } | |
| anyNumber := "any number" | |
| // asNumber() returns anyNumber if n is a TemplateNumberParam. | |
| // TODO(bclayton): Once we support number ranges [e.g.: fn F<N: 1..4>()], we | |
| // should check number ranges are compatible | |
| asNumber := func(n sem.Named) interface{} { | |
| switch n.(type) { | |
| case *sem.TemplateNumberParam: | |
| return anyNumber | |
| default: | |
| return nil | |
| } | |
| } | |
| if arg := asNumber(arg); arg != nil { | |
| param := asNumber(param) | |
| if arg == param { | |
| return nil | |
| } | |
| } | |
| anyType := &sem.Type{} | |
| // asNumber() returns the sem.Type, sem.TypeMatcher if the named object | |
| // resolves to one of these, or anyType if n is a unconstrained template | |
| // type parameter. | |
| asResolvableType := func(n sem.Named) sem.ResolvableType { | |
| switch n := n.(type) { | |
| case *sem.TemplateTypeParam: | |
| if n.Type != nil { | |
| return n.Type | |
| } | |
| return anyType | |
| case *sem.Type: | |
| return n | |
| case *sem.TypeMatcher: | |
| return n | |
| default: | |
| return nil | |
| } | |
| } | |
| if arg := asResolvableType(arg); arg != nil { | |
| param := asResolvableType(param) | |
| if arg == param || param == anyType { | |
| return nil | |
| } | |
| } | |
| return fmt.Errorf("cannot use %v as %v", describe(arg), describe(param)) | |
| } | |
| // scope is a basic hierarchical name to object table | |
| type scope struct { | |
| objects map[string]objectAndSource | |
| parent *scope | |
| } | |
| // objectAndSource is a sem.Named object with a source | |
| type objectAndSource struct { | |
| object sem.Named | |
| source tok.Source | |
| } | |
| // newScope returns a newly initalized scope | |
| func newScope(parent *scope) scope { | |
| return scope{objects: map[string]objectAndSource{}, parent: parent} | |
| } | |
| // lookup() searches the scope and then its parents for the symbol with the | |
| // given name. | |
| func (s *scope) lookup(name string) *objectAndSource { | |
| if o, found := s.objects[name]; found { | |
| return &o | |
| } | |
| if s.parent == nil { | |
| return nil | |
| } | |
| return s.parent.lookup(name) | |
| } | |
| // declare() declares the symbol with the given name, erroring on symbol | |
| // collision. | |
| func (s *scope) declare(object sem.Named, source tok.Source) error { | |
| name := object.GetName() | |
| if existing := s.lookup(name); existing != nil { | |
| return fmt.Errorf("%v '%v' already declared\nFirst declared here: %v", source, name, existing.source) | |
| } | |
| s.objects[name] = objectAndSource{object, source} | |
| return nil | |
| } |