func flattenFunctionTypes(f *exprpb.Type_FunctionType) []*exprpb.Type {
	argTypes := f.GetArgTypes()
	if len(argTypes) == 0 {
		return []*exprpb.Type{f.GetResultType()}
	}
	flattend := make([]*exprpb.Type, len(argTypes)+1, len(argTypes)+1)
	for i, at := range argTypes {
		flattend[i] = at
	}
	flattend[len(argTypes)] = f.GetResultType()
	return flattend
}
flattenFunctionTypes takes a function with arg types T1, T2, ..., TN and result type TR
and returns a slice containing {T1, T2, ..., TN, TR}.
package checker
import (
	"fmt"
	"strings"
	"github.com/google/cel-go/checker/decls"
	"google.golang.org/protobuf/proto"
	exprpb "google.golang.org/genproto/googleapis/api/expr/v1alpha1"
)
const (
	kindUnknown = iota + 1
	kindError
	kindFunction
	kindDyn
	kindPrimitive
	kindWellKnown
	kindWrapper
	kindNull
	kindAbstract
	kindType
	kindList
	kindMap
	kindObject
	kindTypeParam
)
func FormatCheckedType(t *exprpb.Type) string {
	switch kindOf(t) {
	case kindDyn:
		return "dyn"
	case kindFunction:
		return formatFunction(t.GetFunction().GetResultType(),
			t.GetFunction().GetArgTypes(),
			false)
	case kindList:
		return fmt.Sprintf("list(%s)", FormatCheckedType(t.GetListType().ElemType))
	case kindObject:
		return t.GetMessageType()
	case kindMap:
		return fmt.Sprintf("map(%s, %s)",
			FormatCheckedType(t.GetMapType().KeyType),
			FormatCheckedType(t.GetMapType().ValueType))
	case kindNull:
		return "null"
	case kindPrimitive:
		switch t.GetPrimitive() {
		case exprpb.Type_UINT64:
			return "uint"
		case exprpb.Type_INT64:
			return "int"
		}
		return strings.Trim(strings.ToLower(t.GetPrimitive().String()), " ")
	case kindType:
		if t.GetType() == nil {
			return "type"
		}
		return fmt.Sprintf("type(%s)", FormatCheckedType(t.GetType()))
	case kindWellKnown:
		switch t.GetWellKnown() {
		case exprpb.Type_ANY:
			return "any"
		case exprpb.Type_DURATION:
			return "duration"
		case exprpb.Type_TIMESTAMP:
			return "timestamp"
		}
	case kindWrapper:
		return fmt.Sprintf("wrapper(%s)",
			FormatCheckedType(decls.NewPrimitiveType(t.GetWrapper())))
	case kindError:
		return "!error!"
	}
	return t.String()
}
func isDyn(t *exprpb.Type) bool {
	switch kindOf(t) {
	case kindDyn:
		return true
	case kindWellKnown:
		return t.GetWellKnown() == exprpb.Type_ANY
	default:
		return false
	}
}
func isDynOrError(t *exprpb.Type) bool {
	switch kindOf(t) {
	case kindError:
		return true
	default:
		return isDyn(t)
	}
}
func isEqualOrLessSpecific(t1 *exprpb.Type, t2 *exprpb.Type) bool {
	kind1, kind2 := kindOf(t1), kindOf(t2)
	if isDyn(t1) || kind1 == kindTypeParam {
		return true
	}
	if isDyn(t2) || kind2 == kindTypeParam {
		return false
	}
	if kind1 != kind2 {
		return false
	}
	switch kind1 {
	case kindAbstract:
		a1 := t1.GetAbstractType()
		a2 := t2.GetAbstractType()
		if a1.GetName() != a2.GetName() ||
			len(a1.GetParameterTypes()) != len(a2.GetParameterTypes()) {
			return false
		}
		for i, p1 := range a1.GetParameterTypes() {
			if !isEqualOrLessSpecific(p1, a2.GetParameterTypes()[i]) {
				return false
			}
		}
		return true
	case kindFunction:
		fn1 := t1.GetFunction()
		fn2 := t2.GetFunction()
		if len(fn1.ArgTypes) != len(fn2.ArgTypes) {
			return false
		}
		if !isEqualOrLessSpecific(fn1.ResultType, fn2.ResultType) {
			return false
		}
		for i, a1 := range fn1.ArgTypes {
			if !isEqualOrLessSpecific(a1, fn2.ArgTypes[i]) {
				return false
			}
		}
		return true
	case kindList:
		return isEqualOrLessSpecific(t1.GetListType().ElemType, t2.GetListType().ElemType)
	case kindMap:
		m1 := t1.GetMapType()
		m2 := t2.GetMapType()
		return isEqualOrLessSpecific(m1.KeyType, m2.KeyType) &&
			isEqualOrLessSpecific(m1.ValueType, m2.ValueType)
	case kindType:
		return true
	default:
		return proto.Equal(t1, t2)
	}
}
func internalIsAssignable(m *mapping, t1 *exprpb.Type, t2 *exprpb.Type) bool {
	if proto.Equal(t1, t2) {
		return true
	}
	kind1, kind2 := kindOf(t1), kindOf(t2)
	if kind2 == kindTypeParam {
		if t2Sub, found := m.find(t2); found {
			if !internalIsAssignable(m, t1, t2Sub) {
				return false
			}
			m.add(t2, mostGeneral(t1, t2Sub))
			return true
		}
		if notReferencedIn(m, t2, t1) {
			m.add(t2, t1)
			return true
		}
	}
	if kind1 == kindTypeParam {
		if t1Sub, found := m.find(t1); found {
			if !internalIsAssignable(m, t1Sub, t2) {
				return false
			}
			m.add(t1, mostGeneral(t1Sub, t2))
			return true
		}
		if notReferencedIn(m, t1, t2) {
			m.add(t1, t2)
			return true
		}
	}
	if isDynOrError(t1) || isDynOrError(t2) {
		return true
	}
	switch kind1 {
	case kindNull:
		return internalIsAssignableNull(t2)
	case kindPrimitive:
		return internalIsAssignablePrimitive(t1.GetPrimitive(), t2)
	case kindWrapper:
		return internalIsAssignable(m, decls.NewPrimitiveType(t1.GetWrapper()), t2)
	default:
		if kind1 != kind2 {
			return false
		}
	}
	switch kind1 {
	case kindAbstract:
		return internalIsAssignableAbstractType(m, t1.GetAbstractType(), t2.GetAbstractType())
	case kindFunction:
		return internalIsAssignableFunction(m, t1.GetFunction(), t2.GetFunction())
	case kindList:
		return internalIsAssignable(m, t1.GetListType().GetElemType(), t2.GetListType().GetElemType())
	case kindMap:
		return internalIsAssignableMap(m, t1.GetMapType(), t2.GetMapType())
	case kindObject:
		return t1.GetMessageType() == t2.GetMessageType()
	case kindType:
		return true
	case kindWellKnown:
		return t1.GetWellKnown() == t2.GetWellKnown()
	default:
		return false
	}
}
func internalIsAssignableAbstractType(m *mapping,
	a1 *exprpb.Type_AbstractType,
	a2 *exprpb.Type_AbstractType) bool {
	if a1.GetName() != a2.GetName() {
		return false
	}
	if internalIsAssignableList(m, a1.GetParameterTypes(), a2.GetParameterTypes()) {
		return true
	}
	return false
}
func internalIsAssignableFunction(m *mapping,
	f1 *exprpb.Type_FunctionType,
	f2 *exprpb.Type_FunctionType) bool {
	f1ArgTypes := flattenFunctionTypes(f1)
	f2ArgTypes := flattenFunctionTypes(f2)
	if internalIsAssignableList(m, f1ArgTypes, f2ArgTypes) {
		return true
	}
	return false
}
func internalIsAssignableList(m *mapping, l1 []*exprpb.Type, l2 []*exprpb.Type) bool {
	if len(l1) != len(l2) {
		return false
	}
	for i, t1 := range l1 {
		if !internalIsAssignable(m, t1, l2[i]) {
			return false
		}
	}
	return true
}
func internalIsAssignableMap(m *mapping, m1 *exprpb.Type_MapType, m2 *exprpb.Type_MapType) bool {
	if internalIsAssignableList(m,
		[]*exprpb.Type{m1.GetKeyType(), m1.GetValueType()},
		[]*exprpb.Type{m2.GetKeyType(), m2.GetValueType()}) {
		return true
	}
	return false
}
func internalIsAssignableNull(t *exprpb.Type) bool {
	switch kindOf(t) {
	case kindAbstract, kindObject, kindNull, kindWellKnown, kindWrapper:
		return true
	default:
		return false
	}
}
func internalIsAssignablePrimitive(p exprpb.Type_PrimitiveType, target *exprpb.Type) bool {
	switch kindOf(target) {
	case kindPrimitive:
		return p == target.GetPrimitive()
	case kindWrapper:
		return p == target.GetWrapper()
	default:
		return false
	}
}
func isAssignable(m *mapping, t1 *exprpb.Type, t2 *exprpb.Type) *mapping {
	mCopy := m.copy()
	if internalIsAssignable(mCopy, t1, t2) {
		return mCopy
	}
	return nil
}
func isAssignableList(m *mapping, l1 []*exprpb.Type, l2 []*exprpb.Type) *mapping {
	mCopy := m.copy()
	if internalIsAssignableList(mCopy, l1, l2) {
		return mCopy
	}
	return nil
}
func kindOf(t *exprpb.Type) int {
	if t == nil || t.TypeKind == nil {
		return kindUnknown
	}
	switch t.TypeKind.(type) {
	case *exprpb.Type_Error:
		return kindError
	case *exprpb.Type_Function:
		return kindFunction
	case *exprpb.Type_Dyn:
		return kindDyn
	case *exprpb.Type_Primitive:
		return kindPrimitive
	case *exprpb.Type_WellKnown:
		return kindWellKnown
	case *exprpb.Type_Wrapper:
		return kindWrapper
	case *exprpb.Type_Null:
		return kindNull
	case *exprpb.Type_Type:
		return kindType
	case *exprpb.Type_ListType_:
		return kindList
	case *exprpb.Type_MapType_:
		return kindMap
	case *exprpb.Type_MessageType:
		return kindObject
	case *exprpb.Type_TypeParam:
		return kindTypeParam
	case *exprpb.Type_AbstractType_:
		return kindAbstract
	}
	return kindUnknown
}
func mostGeneral(t1 *exprpb.Type, t2 *exprpb.Type) *exprpb.Type {
	if isEqualOrLessSpecific(t1, t2) {
		return t1
	}
	return t2
}
func notReferencedIn(m *mapping, t *exprpb.Type, withinType *exprpb.Type) bool {
	if proto.Equal(t, withinType) {
		return false
	}
	withinKind := kindOf(withinType)
	switch withinKind {
	case kindTypeParam:
		wtSub, found := m.find(withinType)
		if !found {
			return true
		}
		return notReferencedIn(m, t, wtSub)
	case kindAbstract:
		for _, pt := range withinType.GetAbstractType().GetParameterTypes() {
			if !notReferencedIn(m, t, pt) {
				return false
			}
		}
		return true
	case kindFunction:
		fn := withinType.GetFunction()
		types := flattenFunctionTypes(fn)
		for _, a := range types {
			if !notReferencedIn(m, t, a) {
				return false
			}
		}
		return true
	case kindList:
		return notReferencedIn(m, t, withinType.GetListType().ElemType)
	case kindMap:
		mt := withinType.GetMapType()
		return notReferencedIn(m, t, mt.KeyType) && notReferencedIn(m, t, mt.ValueType)
	case kindWrapper:
		return notReferencedIn(m, t, decls.NewPrimitiveType(withinType.GetWrapper()))
	default:
		return true
	}
}
func substitute(m *mapping, t *exprpb.Type, typeParamToDyn bool) *exprpb.Type {
	if tSub, found := m.find(t); found {
		return substitute(m, tSub, typeParamToDyn)
	}
	kind := kindOf(t)
	if typeParamToDyn && kind == kindTypeParam {
		return decls.Dyn
	}
	switch kind {
	case kindAbstract:
		at := t.GetAbstractType()
		params := make([]*exprpb.Type, len(at.GetParameterTypes()))
		for i, p := range at.GetParameterTypes() {
			params[i] = substitute(m, p, typeParamToDyn)
		}
		return decls.NewAbstractType(at.GetName(), params...)
	case kindFunction:
		fn := t.GetFunction()
		rt := substitute(m, fn.ResultType, typeParamToDyn)
		args := make([]*exprpb.Type, len(fn.ArgTypes))
		for i, a := range fn.ArgTypes {
			args[i] = substitute(m, a, typeParamToDyn)
		}
		return decls.NewFunctionType(rt, args...)
	case kindList:
		return decls.NewListType(substitute(m, t.GetListType().ElemType, typeParamToDyn))
	case kindMap:
		mt := t.GetMapType()
		return decls.NewMapType(substitute(m, mt.KeyType, typeParamToDyn),
			substitute(m, mt.ValueType, typeParamToDyn))
	case kindType:
		if t.GetType() != nil {
			return decls.NewTypeType(substitute(m, t.GetType(), typeParamToDyn))
		}
		return t
	default:
		return t
	}
}
func typeKey(t *exprpb.Type) string {
	return FormatCheckedType(t)
}