blob: fbd9c9d6847eaceefd37d1cf6d36de982736a1da [file] [log] [blame]
// 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/tint/tools/src/cmd/builtin-gen/ast"
"dawn.googlesource.com/tint/tools/src/cmd/builtin-gen/sem"
"dawn.googlesource.com/tint/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
}