tools/src/tint/intrinsic/gen/permutate.go

// Copyright 2021 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
//    contributors may be used to endorse or promote products derived from
//    this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

package gen

import (
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"strings"

	"dawn.googlesource.com/dawn/tools/src/fileutils"
	"dawn.googlesource.com/dawn/tools/src/tint/intrinsic/sem"
)

// Permuter generates permutations of intrinsic overloads
type Permuter struct {
	sem      *sem.Sem
	allTypes []sem.FullyQualifiedName
}

// NewPermuter returns a new initialized Permuter
func NewPermuter(s *sem.Sem) (*Permuter, error) {
	// allTypes are the list of FQNs that are used for unconstrained types
	allTypes := []sem.FullyQualifiedName{}
	for _, ty := range s.Types {
		if len(ty.TemplateParams) > 0 {
			// Ignore aggregate types for now.
			// TODO(bclayton): Support a limited set of aggregate types
			continue
		}
		allTypes = append(allTypes, sem.FullyQualifiedName{Target: ty})
	}
	return &Permuter{
		sem:      s,
		allTypes: allTypes,
	}, nil
}

// Permutation describes a single permutation of an overload
type Permutation struct {
	sem.Overload        // The permutated overload signature
	Desc         string // Description of the overload
	Hash         string // Hash of the overload
}

// Permute generates a set of permutations for the given intrinsic overload
func (p *Permuter) Permute(overload *sem.Overload) ([]Permutation, error) {
	state := permutationState{
		Permuter:        p,
		templateTypes:   map[sem.TemplateParam]sem.FullyQualifiedName{},
		templateNumbers: map[sem.TemplateParam]any{},
		parameters:      map[int]sem.FullyQualifiedName{},
	}

	out := []Permutation{}

	// Map of hash to permutation description. Used to detect collisions.
	hashes := map[string]string{}

	// permutate appends a permutation to out.
	// permutate may be chained to generate N-dimensional permutations.
	permutate := func() error {
		o := sem.Overload{
			Decl:             overload.Decl,
			Intrinsic:        overload.Intrinsic,
			CanBeUsedInStage: overload.CanBeUsedInStage,
		}
		for i, p := range overload.Parameters {
			ty := state.parameters[i]
			if !validate(ty, &o.CanBeUsedInStage) {
				return nil
			}
			o.Parameters = append(o.Parameters, sem.Parameter{
				Name:      p.Name,
				Type:      ty,
				IsConst:   p.IsConst,
				TestValue: p.TestValue,
			})
		}
		if overload.ReturnType != nil {
			retTys, err := state.permutateFQN(*overload.ReturnType)
			if err != nil {
				return fmt.Errorf("while permutating return type: %w", err)
			}
			if len(retTys) != 1 {
				return fmt.Errorf("result type not pinned")
			}
			o.ReturnType = &retTys[0]
		}
		desc := fmt.Sprint(o)
		hash := sha256.Sum256([]byte(desc))
		const hashLength = 6
		shortHash := hex.EncodeToString(hash[:])[:hashLength]
		out = append(out, Permutation{
			Overload: o,
			Desc:     desc,
			Hash:     shortHash,
		})

		// Check for hash collisions
		if existing, collision := hashes[shortHash]; collision {
			return fmt.Errorf(`hash '%v' collision between
  %v
and
  %v
Increase hashLength in %v`,
				shortHash, existing, desc, fileutils.ThisLine())
		}
		hashes[shortHash] = desc
		return nil
	}
	for i, param := range overload.Parameters {
		i, param := i, param // Capture iterator values for anonymous function
		next := permutate    // Permutation chaining
		permutate = func() error {
			permutations, err := state.permutateFQN(param.Type)
			if err != nil {
				return fmt.Errorf("while processing parameter %v: %w", i, err)
			}
			if len(permutations) == 0 {
				return fmt.Errorf("parameter %v has no permutations", i)
			}
			for _, fqn := range permutations {
				state.parameters[i] = fqn
				if err := next(); err != nil {
					return err
				}
			}
			return nil
		}
	}
	for _, t := range overload.TemplateParams {
		next := permutate // Permutation chaining
		switch t := t.(type) {
		case *sem.TemplateTypeParam:
			types := p.allTypes
			if t.Type != nil {
				var err error
				types, err = state.permutateFQN(sem.FullyQualifiedName{Target: t.Type})
				if err != nil {
					return nil, fmt.Errorf("while permutating template types: %w", err)
				}
			}
			if len(types) == 0 {
				return nil, fmt.Errorf("template type %v has no permutations", t.Name)
			}
			permutate = func() error {
				for _, ty := range types {
					state.templateTypes[t] = ty
					if err := next(); err != nil {
						return err
					}
				}
				return nil
			}
		case *sem.TemplateEnumParam:
			var permutations []sem.FullyQualifiedName
			var err error
			if t.Matcher != nil {
				permutations, err = state.permutateFQN(sem.FullyQualifiedName{Target: t.Matcher})
			} else {
				permutations, err = state.permutateFQN(sem.FullyQualifiedName{Target: t.Enum})
			}
			if err != nil {
				return nil, fmt.Errorf("while permutating template numbers: %w", err)
			}
			if len(permutations) == 0 {
				return nil, fmt.Errorf("template type %v has no permutations", t.Name)
			}
			permutate = func() error {
				for _, n := range permutations {
					state.templateNumbers[t] = n
					if err := next(); err != nil {
						return err
					}
				}
				return nil
			}
		case *sem.TemplateNumberParam:
			// Currently all open numbers are used for vector / matrices
			permutations := []int{2, 3, 4}
			permutate = func() error {
				for _, n := range permutations {
					state.templateNumbers[t] = n
					if err := next(); err != nil {
						return err
					}
				}
				return nil
			}
		}
	}

	if err := permutate(); err != nil {
		return nil, fmt.Errorf("%v %v %w\nState: %v", overload.Decl.Source, overload.Decl, err, state)
	}

	return out, nil
}

type permutationState struct {
	*Permuter
	templateTypes   map[sem.TemplateParam]sem.FullyQualifiedName
	templateNumbers map[sem.TemplateParam]any
	parameters      map[int]sem.FullyQualifiedName
}

func (s permutationState) String() string {
	sb := &strings.Builder{}
	sb.WriteString("Template types:\n")
	for ct, ty := range s.templateTypes {
		fmt.Fprintf(sb, "  %v: %v\n", ct.GetName(), ty)
	}
	sb.WriteString("Template numbers:\n")
	for cn, v := range s.templateNumbers {
		fmt.Fprintf(sb, "  %v: %v\n", cn.GetName(), v)
	}
	return sb.String()
}

func (s *permutationState) permutateFQN(in sem.FullyQualifiedName) ([]sem.FullyQualifiedName, error) {
	args := append([]any{}, in.TemplateArguments...)
	out := []sem.FullyQualifiedName{}

	// permutate appends a permutation to out.
	// permutate may be chained to generate N-dimensional permutations.
	var permutate func() error

	switch target := in.Target.(type) {
	case *sem.Type:
		permutate = func() error {
			// Inner-most permutate lambda.
			// Append a the current permutation to out
			out = append(out, sem.FullyQualifiedName{Target: in.Target, TemplateArguments: args})
			// Clone the argument list, for the next permutation to use.
			args = append([]any{}, args...)
			return nil
		}
	case sem.TemplateParam:
		if ty, ok := s.templateTypes[target]; ok {
			permutate = func() error {
				out = append(out, ty)
				return nil
			}
		} else {
			return nil, fmt.Errorf("'%v' was not found in templateTypes", target.GetName())
		}
	case *sem.TypeMatcher:
		permutate = func() error {
			for _, ty := range target.Types {
				out = append(out, sem.FullyQualifiedName{Target: ty})
			}
			return nil
		}
	case *sem.EnumMatcher:
		permutate = func() error {
			for _, o := range target.Options {
				if !o.IsInternal {
					out = append(out, sem.FullyQualifiedName{Target: o})
				}
			}
			return nil
		}
	case *sem.Enum:
		permutate = func() error {
			for _, e := range target.Entries {
				if !e.IsInternal {
					out = append(out, sem.FullyQualifiedName{Target: e})
				}
			}
			return nil
		}
	default:
		return nil, fmt.Errorf("unhandled target type: %T", in.Target)
	}

	for i, arg := range in.TemplateArguments {
		i := i            // Capture iterator value for anonymous functions
		next := permutate // Permutation chaining
		switch arg := arg.(type) {
		case sem.FullyQualifiedName:
			switch target := arg.Target.(type) {
			case sem.TemplateParam:
				if ty, ok := s.templateTypes[target]; ok {
					args[i] = ty
				} else if num, ok := s.templateNumbers[target]; ok {
					args[i] = num
				} else {
					return nil, fmt.Errorf("'%v' was not found in templateTypes or templateNumbers", target.GetName())
				}
			default:
				perms, err := s.permutateFQN(arg)
				if err != nil {
					return nil, fmt.Errorf("while processing template argument %v: %v", i, err)
				}
				if len(perms) == 0 {
					return nil, fmt.Errorf("template argument %v has no permutations", i)
				}
				permutate = func() error {
					for _, f := range perms {
						args[i] = f
						if err := next(); err != nil {
							return err
						}
					}
					return nil
				}
			}
		default:
			return nil, fmt.Errorf("permutateFQN() unhandled template argument type: %T", arg)
		}
	}

	if err := permutate(); err != nil {
		return nil, fmt.Errorf("while processing fully qualified name '%v': %w", in.Target.GetName(), err)
	}

	return out, nil
}

func validate(fqn sem.FullyQualifiedName, uses *sem.StageUses) bool {
	if strings.HasPrefix(fqn.Target.GetName(), "_") {
		return false // Builtin, untypeable return type
	}

	isStorable := func(elTy sem.FullyQualifiedName) bool {
		elTyName := elTy.Target.GetName()
		switch {
		case elTyName == "bool",
			strings.Contains(elTyName, "sampler"),
			strings.Contains(elTyName, "texture"),
			IsAbstract(DeepestElementType(elTy)):
			return false
		}
		return true
	}

	switch fqn.Target.GetName() {
	case "array":
		if !isStorable(fqn.TemplateArguments[0].(sem.FullyQualifiedName)) {
			return false
		}
	case "ptr":
		// https://gpuweb.github.io/gpuweb/wgsl/#address-space
		access := fqn.TemplateArguments[2].(sem.FullyQualifiedName).Target.(*sem.EnumEntry).Name
		addressSpace := fqn.TemplateArguments[0].(sem.FullyQualifiedName).Target.(*sem.EnumEntry).Name
		switch addressSpace {
		case "function", "private":
			if access != "read_write" {
				return false
			}
		case "workgroup":
			uses.Vertex = false
			uses.Fragment = false
			if access != "read_write" {
				return false
			}
			if !isStorable(fqn.TemplateArguments[1].(sem.FullyQualifiedName)) {
				return false
			}
		case "uniform":
			if access != "read" {
				return false
			}
		case "storage":
			if access != "read_write" && access != "read" {
				return false
			}
		case "handle":
			if access != "read" {
				return false
			}
		default:
			return false
		}
	}

	for _, arg := range fqn.TemplateArguments {
		if argFQN, ok := arg.(sem.FullyQualifiedName); ok {
			if !validate(argFQN, uses) {
				return false
			}
		}
	}

	return true
}