caddy/modules/caddyhttp/celmatcher.go

// Copyright 2015 Matthew Holt and The Caddy 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 caddyhttp

import (
	"crypto/x509/pkix"
	"encoding/json"
	"errors"
	"fmt"
	"net"
	"net/http"
	"net/url"
	"reflect"
	"regexp"
	"slices"
	"strings"
	"time"

	"cel.dev/cel-go/cel"
	"cel.dev/cel-go/common"
	"cel.dev/cel-go/common/ast"
	"cel.dev/cel-go/common/operators"
	"cel.dev/cel-go/common/types"
	"cel.dev/cel-go/common/types/ref"
	"cel.dev/cel-go/common/types/traits"
	"cel.dev/cel-go/ext"
	"cel.dev/cel-go/interpreter"
	"cel.dev/cel-go/interpreter/functions"
	"cel.dev/cel-go/parser"
	"go.uber.org/zap"
	"golang.org/x/net/idna"

	"github.com/caddyserver/caddy/v2"
	"github.com/caddyserver/caddy/v2/caddyconfig/caddyfile"
)

func init() {
	caddy.RegisterModule(MatchExpression{})
}

// MatchExpression matches requests by evaluating a
// [CEL](https://github.com/google/cel-spec) expression.
// This enables complex logic to be expressed using a comfortable,
// familiar syntax. Please refer to
// [the standard definitions of CEL functions and operators](https://github.com/google/cel-spec/blob/master/doc/langdef.md#standard-definitions).
//
// This matcher's JSON interface is actually a string, not a struct.
// The generated docs are not correct because this type has custom
// marshaling logic.
//
// COMPATIBILITY NOTE: This module is still experimental and is not
// subject to Caddy's compatibility guarantee.
//
// Runtime arguments to template matchers are literal values, including entire
// concatenations involving runtime data. Static strings retain the matcher's
// placeholder and wildcard syntax. Regexp and URL-pattern matchers retain their
// respective pattern languages.
type MatchExpression struct {
	// The CEL expression to evaluate. Any Caddy placeholders
	// will be expanded and situated into proper CEL function
	// calls before evaluating.
	Expr string `json:"expr,omitempty"`

	// Name is an optional name for this matcher.
	// This is used to populate the name for regexp
	// matchers that appear in the expression.
	Name string `json:"name,omitempty"`

	expandedExpr string
	placeholders []string
	prg          cel.Program
	ta           types.Adapter

	log *zap.Logger
}

// CaddyModule returns the Caddy module information.
func (MatchExpression) CaddyModule() caddy.ModuleInfo {
	return caddy.ModuleInfo{
		ID:  "http.matchers.expression",
		New: func() caddy.Module { return new(MatchExpression) },
	}
}

// MarshalJSON marshals m's expression.
func (m MatchExpression) MarshalJSON() ([]byte, error) {
	// if the name is empty, then we can marshal just the expression string
	if m.Name == "" {
		return json.Marshal(m.Expr)
	}
	// otherwise, we need to marshal the full object, using an
	// anonymous struct to avoid infinite recursion
	return json.Marshal(struct {
		Expr string `json:"expr"`
		Name string `json:"name"`
	}{
		Expr: m.Expr,
		Name: m.Name,
	})
}

// UnmarshalJSON unmarshals m's expression.
func (m *MatchExpression) UnmarshalJSON(data []byte) error {
	// if the data is a string, then it's just the expression
	if data[0] == '"' {
		return json.Unmarshal(data, &m.Expr)
	}
	// otherwise, it's a full object, so unmarshal it,
	// using a temp map to avoid infinite recursion
	var tmpJson map[string]any
	err := json.Unmarshal(data, &tmpJson)
	*m = MatchExpression{
		Expr: tmpJson["expr"].(string),
		Name: tmpJson["name"].(string),
	}
	return err
}

// Provision sets up m.
func (m *MatchExpression) Provision(ctx caddy.Context) error {
	m.log = ctx.Logger()

	// replace placeholders with a function call - this is just some
	// light (and possibly naïve) syntactic sugar
	m.expandedExpr = placeholderRegexp.ReplaceAllString(m.Expr, placeholderExpansion)

	// as a second pass, we'll strip the escape character from an escaped
	// placeholder, so that it can be used as an input to other CEL functions
	m.expandedExpr = escapedPlaceholderRegexp.ReplaceAllString(m.expandedExpr, escapedPlaceholderExpansion)

	// our type adapter expands CEL's standard type support
	m.ta = celTypeAdapter{}

	// initialize the CEL libraries from the Matcher implementations which
	// have been configured to support CEL.
	matcherLibProducers := []CELLibraryProducer{}
	for _, info := range caddy.GetModules("http.matchers") {
		p, ok := info.New().(CELLibraryProducer)
		if ok {
			matcherLibProducers = append(matcherLibProducers, p)
		}
	}

	// add the matcher name to the context so that the matcher name
	// can be used by regexp matchers being provisioned
	ctx = ctx.WithValue(MatcherNameCtxKey, m.Name)

	// Assemble the compilation and program options from the different library
	// producers into a single cel.Library implementation.
	matcherEnvOpts := []cel.EnvOption{}
	matcherProgramOpts := []cel.ProgramOption{}
	for _, producer := range matcherLibProducers {
		l, err := producer.CELLibrary(ctx)
		if err != nil {
			return fmt.Errorf("error initializing CEL library for %T: %v", producer, err)
		}
		matcherEnvOpts = append(matcherEnvOpts, l.CompileOptions()...)
		matcherProgramOpts = append(matcherProgramOpts, l.ProgramOptions()...)
	}
	matcherLib := cel.Lib(NewMatcherCELLibrary(matcherEnvOpts, matcherProgramOpts))

	// create the CEL environment
	env, err := cel.NewEnv(
		cel.Function(CELPlaceholderFuncName, cel.SingletonBinaryBinding(m.caddyPlaceholderFunc), cel.Overload(
			CELPlaceholderFuncName+"_httpRequest_string",
			[]*cel.Type{httpRequestObjectType, cel.StringType},
			cel.AnyType,
		)),
		cel.Variable(CELRequestVarName, httpRequestObjectType),
		cel.CustomTypeAdapter(m.ta),
		ext.Strings(),
		ext.Bindings(),
		ext.Lists(),
		ext.Math(),
		matcherLib,
	)
	if err != nil {
		return fmt.Errorf("setting up CEL environment: %v", err)
	}

	// parse and type-check the expression
	checked, issues := env.Compile(m.expandedExpr)
	if issues.Err() != nil {
		return fmt.Errorf("compiling CEL program: %s", issues.Err())
	}

	// request matching is a boolean operation, so we don't really know
	// what to do if the expression returns a non-boolean type
	if checked.OutputType() != cel.BoolType {
		return fmt.Errorf("CEL request matcher expects return type of bool, not %s", checked.OutputType())
	}

	m.placeholders = celPlaceholderNames(checked.NativeRep().Expr())

	// compile the "program"
	m.prg, err = env.Program(checked, cel.EvalOptions(cel.OptOptimize))
	if err != nil {
		return fmt.Errorf("compiling CEL program: %s", err)
	}
	return nil
}

// Placeholders returns the names of the placeholders the provisioned
// expression reads. A name that is only known at evaluation time is
// returned as an empty string.
func (m MatchExpression) Placeholders() []string {
	return slices.Clone(m.placeholders)
}

// Match returns true if r matches m.
func (m MatchExpression) Match(r *http.Request) bool {
	match, err := m.MatchWithError(r)
	if err != nil {
		SetVar(r.Context(), MatcherErrorVarKey, err)
	}
	return match
}

// MatchWithError returns true if r matches m.
func (m MatchExpression) MatchWithError(r *http.Request) (bool, error) {
	celReq := celHTTPRequest{r}
	out, _, err := m.prg.Eval(celReq)
	if err != nil {
		m.log.Error("evaluating expression", zap.Error(err))
		return false, err
	}
	if outBool, ok := out.Value().(bool); ok {
		return outBool, nil
	}
	return false, nil
}

// UnmarshalCaddyfile implements caddyfile.Unmarshaler.
func (m *MatchExpression) UnmarshalCaddyfile(d *caddyfile.Dispenser) error {
	d.Next() // consume matcher name

	// if there's multiple args, then we need to keep the raw
	// tokens because the user may have used quotes within their
	// CEL expression (e.g. strings) and we should retain that
	if d.CountRemainingArgs() > 1 {
		m.Expr = strings.Join(d.RemainingArgsRaw(), " ")
	} else {
		// there should at least be one arg
		if !d.NextArg() {
			return d.ArgErr()
		}

		// if there's only one token, then we can safely grab the
		// cleaned token (no quotes) and use that as the expression
		// because there's no valid CEL expression that is only a
		// quoted string; commonly quotes are used in Caddyfile to
		// define the expression
		m.Expr = d.Val()

		// use the named matcher's name, to fill regexp
		// matchers names by default
		m.Name = d.GetContextString(caddyfile.MatcherNameCtxKey)
	}

	// a matcher set holds only one expression matcher
	if d.Next() {
		return d.Err("repeated expression matchers are not supported, combine them into one expression with &&")
	}

	return nil
}

// caddyPlaceholderFunc implements the custom CEL function that accesses the
// Replacer on a request and gets values from it.
func (m MatchExpression) caddyPlaceholderFunc(lhs, rhs ref.Val) ref.Val {
	celReq, ok := lhs.(celHTTPRequest)
	if !ok {
		return types.NewErr(
			"invalid request of type '%v' to %s(request, placeholderVarName)",
			lhs.Type(),
			CELPlaceholderFuncName,
		)
	}
	phStr, ok := rhs.(types.String)
	if !ok {
		return types.NewErr(
			"invalid placeholder variable name of type '%v' to %s(request, placeholderVarName)",
			rhs.Type(),
			CELPlaceholderFuncName,
		)
	}

	repl := celReq.Context().Value(caddy.ReplacerCtxKey).(*caddy.Replacer)
	val, _ := repl.Get(string(phStr))

	return m.ta.NativeToValue(val)
}

// httpRequestCELType is the type representation of a native HTTP request.
var httpRequestCELType = cel.ObjectType("http.Request", traits.ReceiverType)

// celHTTPRequest wraps an http.Request with ref.Val interface methods.
//
// This type also implements the interpreter.Activation interface which
// drops allocation costs for CEL expression evaluations by roughly half.
type celHTTPRequest struct{ *http.Request }

func (cr celHTTPRequest) ResolveName(name string) (any, bool) {
	if name == CELRequestVarName {
		return cr, true
	}
	return nil, false
}

func (cr celHTTPRequest) Parent() interpreter.Activation {
	return nil
}

func (cr celHTTPRequest) ConvertToNative(typeDesc reflect.Type) (any, error) {
	return cr.Request, nil
}

func (celHTTPRequest) ConvertToType(typeVal ref.Type) ref.Val {
	panic("not implemented")
}

func (cr celHTTPRequest) Equal(other ref.Val) ref.Val {
	if o, ok := other.Value().(celHTTPRequest); ok {
		return types.Bool(o.Request == cr.Request)
	}
	return types.ValOrErr(other, "%v is not comparable type", other)
}
func (celHTTPRequest) Type() ref.Type { return httpRequestCELType }
func (cr celHTTPRequest) Value() any  { return cr }

var pkixNameCELType = cel.ObjectType("pkix.Name", traits.ReceiverType)

// celPkixName wraps a pkix.Name with
// methods to satisfy the ref.Val interface.
type celPkixName struct{ *pkix.Name }

func (pn celPkixName) ConvertToNative(typeDesc reflect.Type) (any, error) {
	return pn.Name, nil
}

func (pn celPkixName) ConvertToType(typeVal ref.Type) ref.Val {
	if typeVal.TypeName() == "string" {
		return types.String(pn.Name.String())
	}
	panic("not implemented")
}

func (pn celPkixName) Equal(other ref.Val) ref.Val {
	if o, ok := other.Value().(string); ok {
		return types.Bool(pn.Name.String() == o)
	}
	return types.ValOrErr(other, "%v is not comparable type", other)
}
func (celPkixName) Type() ref.Type { return pkixNameCELType }
func (pn celPkixName) Value() any  { return pn }

// celTypeAdapter can adapt our custom types to a CEL value.
type celTypeAdapter struct{}

func (celTypeAdapter) NativeToValue(value any) ref.Val {
	switch v := value.(type) {
	case celHTTPRequest:
		return v
	case pkix.Name:
		return celPkixName{&v}
	case time.Time:
		return types.Timestamp{Time: v}
	case error:
		return types.WrapErr(v)
	}
	return types.DefaultTypeAdapter.NativeToValue(value)
}

// CELLibraryProducer provide CEL libraries that expose a Matcher
// implementation as a first class function within the CEL expression
// matcher.
type CELLibraryProducer interface {
	// CELLibrary creates a cel.Library which makes it possible to use the
	// target object within CEL expression matchers.
	CELLibrary(caddy.Context) (cel.Library, error)
}

// CELMatcherImpl creates a new cel.Library based on the following pieces of
// data:
//
//   - macroName: the function name to be used within CEL. This will be a macro
//     and not a function proper.
//   - funcName: the function overload name generated by the CEL macro used to
//     represent the matcher.
//   - matcherDataTypes: the argument types to the macro.
//   - fac: a matcherFactory implementation which converts from CEL constant
//     values to a Matcher instance.
//
// Note, macro names and function names must not collide with other macros or
// functions exposed within CEL expressions, or an error will be produced
// during the expression matcher plan time.
//
// The existing CELMatcherImpl support methods are configured to support a
// limited set of function signatures. For strong type validation you may need
// to provide a custom macro which does a more detailed analysis of the CEL
// literal provided to the macro as an argument.
func CELMatcherImpl(macroName, funcName string, matcherDataTypes []*cel.Type, fac any) (cel.Library, error) {
	requestType := cel.ObjectType("http.Request")
	var macro parser.Macro
	switch len(matcherDataTypes) {
	case 1:
		matcherDataType := matcherDataTypes[0]
		switch matcherDataType.String() {
		case "list(string)":
			macro = parser.NewGlobalVarArgMacro(macroName, celMatcherStringListMacroExpander(funcName))
		case cel.StringType.String():
			macro = parser.NewGlobalMacro(macroName, 1, celMatcherStringMacroExpander(funcName))
		case CELTypeJSON.String():
			macro = parser.NewGlobalMacro(macroName, 1, celMatcherJSONMacroExpander(funcName))
		default:
			return nil, fmt.Errorf("unsupported matcher data type: %s", matcherDataType)
		}
	case 2:
		if matcherDataTypes[0] == cel.StringType && matcherDataTypes[1] == cel.StringType {
			macro = parser.NewGlobalMacro(macroName, 2, celMatcherStringListMacroExpander(funcName))
			matcherDataTypes = []*cel.Type{cel.ListType(cel.StringType)}
		} else {
			return nil, fmt.Errorf("unsupported matcher data type: %s, %s", matcherDataTypes[0], matcherDataTypes[1])
		}
	case 3:
		// nolint:gosec // false positive, impossible to be out of bounds; see: https://github.com/securego/gosec/issues/1525
		if matcherDataTypes[0] == cel.StringType && matcherDataTypes[1] == cel.StringType && matcherDataTypes[2] == cel.StringType {
			macro = parser.NewGlobalMacro(macroName, 3, celMatcherStringListMacroExpander(funcName))
			matcherDataTypes = []*cel.Type{cel.ListType(cel.StringType)}
		} else {
			// nolint:gosec // false positive, impossible to be out of bounds; see: https://github.com/securego/gosec/issues/1525
			return nil, fmt.Errorf("unsupported matcher data type: %s, %s, %s", matcherDataTypes[0], matcherDataTypes[1], matcherDataTypes[2])
		}
	}
	envOptions := []cel.EnvOption{
		cel.Macros(macro),
		cel.Function(funcName,
			cel.Overload(funcName, append([]*cel.Type{requestType}, matcherDataTypes...), cel.BoolType),
			cel.SingletonBinaryBinding(CELMatcherRuntimeFunction(funcName, fac))),
	}
	programOptions := []cel.ProgramOption{
		cel.CustomDecorator(CELMatcherDecorator(funcName, fac)),
	}
	return NewMatcherCELLibrary(envOptions, programOptions), nil
}

// CELMatcherFactory converts a constant CEL value into a RequestMatcher.
// Deprecated: Use CELMatcherWithErrorFactory instead.
type CELMatcherFactory = func(data ref.Val) (RequestMatcher, error)

// CELMatcherWithErrorFactory converts a constant CEL value into a RequestMatcherWithError.
type CELMatcherWithErrorFactory = func(data ref.Val) (RequestMatcherWithError, error)

// CELMatcherLiteralFactory is a factory that handles literal/template provenance
// itself. Use CELMatcherIsLiteral to inspect strings before native conversion.
// Other factories continue to receive ordinary CEL strings.
type CELMatcherLiteralFactory func(data ref.Val) (RequestMatcherWithError, error)

// celMatcherLiteralString retains the provenance of a runtime matcher argument.
// Its native representation remains a string, including for plugin factories.
type celMatcherLiteralString struct{ types.String }

type celMatcherLiteralLibrary struct{}

func (celMatcherLiteralLibrary) LibraryName() string { return "caddy.http.matcher_literals" }

func (celMatcherLiteralLibrary) CompileOptions() []cel.EnvOption {
	return []cel.EnvOption{
		cel.Function("caddyMatcherLiteral", cel.Overload("caddyMatcherLiteral_string",
			[]*cel.Type{cel.StringType}, cel.StringType,
			cel.UnaryBinding(func(v ref.Val) ref.Val {
				s, ok := v.(types.String)
				if !ok {
					return types.ValOrErr(v, "matcher argument must be a string")
				}
				return celMatcherLiteralString{s}
			}))),
	}
}

func (celMatcherLiteralLibrary) ProgramOptions() []cel.ProgramOption { return nil }

// CELMatcherIsLiteral reports whether a string argument was evaluated at runtime,
// rather than supplied as a trusted template in the expression.
func CELMatcherIsLiteral(v ref.Val) bool {
	_, ok := v.(celMatcherLiteralString)
	return ok
}

// CELMatcherArgument preserves literal/template provenance within matcher input.
// A concatenation involving runtime data is one literal string, not a template.
// Custom matcher macros should apply this to their data argument.
func CELMatcherArgument(eh cel.MacroExprFactory, e ast.Expr) ast.Expr {
	switch e.Kind() {
	case ast.MapKind:
		entries := make([]ast.EntryExpr, 0, len(e.AsMap().Entries()))
		for _, entry := range e.AsMap().Entries() {
			pair := entry.AsMapEntry()
			entries = append(entries, eh.NewMapEntry(
				CELMatcherArgument(eh, pair.Key()), CELMatcherArgument(eh, pair.Value()), pair.IsOptional()))
		}
		return eh.NewMap(entries...)
	case ast.ListKind:
		elems := make([]ast.Expr, 0, len(e.AsList().Elements()))
		for _, elem := range e.AsList().Elements() {
			elems = append(elems, CELMatcherArgument(eh, elem))
		}
		return eh.NewList(elems...)
	case ast.UnspecifiedExprKind, ast.CallKind, ast.ComprehensionKind, ast.IdentKind, ast.LiteralKind, ast.SelectKind, ast.StructKind:
		// String expressions are handled below.
	}
	if celMatcherStaticString(e) {
		return e
	}
	return eh.NewCall("caddyMatcherLiteral", e)
}

func celMatcherStaticString(e ast.Expr) bool {
	if isCELStringLiteral(e) {
		return true
	}
	if e.Kind() != ast.CallKind || e.AsCall().FunctionName() != operators.Add {
		return false
	}
	for _, arg := range e.AsCall().Args() {
		if !celMatcherStaticString(arg) {
			return false
		}
	}
	return true
}

// matcherCELLibrary is a simplistic configurable cel.Library implementation.
type matcherCELLibrary struct {
	envOptions     []cel.EnvOption
	programOptions []cel.ProgramOption
}

// NewMatcherCELLibrary creates a matcherLibrary from option sets.
func NewMatcherCELLibrary(envOptions []cel.EnvOption, programOptions []cel.ProgramOption) cel.Library {
	return &matcherCELLibrary{
		envOptions:     append([]cel.EnvOption{cel.Lib(celMatcherLiteralLibrary{})}, envOptions...),
		programOptions: programOptions,
	}
}

func (lib *matcherCELLibrary) CompileOptions() []cel.EnvOption {
	return lib.envOptions
}

func (lib *matcherCELLibrary) ProgramOptions() []cel.ProgramOption {
	return lib.programOptions
}

// CELMatcherDecorator matches a call overload generated by a CEL macro
// that takes a single argument, and optimizes the implementation to precompile
// the matcher and return a function that references the precompiled and
// provisioned matcher.
func CELMatcherDecorator(funcName string, fac any) interpreter.InterpretableDecorator {
	if factory, ok := fac.(CELMatcherLiteralFactory); ok {
		fac = CELMatcherWithErrorFactory(factory)
	}
	return func(i interpreter.Interpretable) (interpreter.Interpretable, error) {
		call, ok := i.(interpreter.InterpretableCall)
		if !ok {
			return i, nil
		}
		if call.OverloadID() != funcName {
			return i, nil
		}
		callArgs := call.Args()
		reqAttr, ok := callArgs[0].(interpreter.InterpretableAttribute)
		if !ok {
			return nil, errors.New("missing 'req' argument")
		}
		nsAttr, ok := reqAttr.Attr().(interpreter.NamespacedAttribute)
		if !ok {
			return nil, errors.New("missing 'req' argument")
		}
		varNames := nsAttr.CandidateVariableNames()
		if len(varNames) != 1 || len(varNames) == 1 && varNames[0] != CELRequestVarName {
			return nil, errors.New("missing 'req' argument")
		}
		matcherData, ok := callArgs[1].(interpreter.InterpretableConst)
		if !ok {
			// If the matcher arguments are not constant, then this means
			// they contain a Caddy placeholder reference and the evaluation
			// and matcher provisioning should be handled at dynamically.
			return i, nil
		}

		if factory, ok := fac.(CELMatcherWithErrorFactory); ok {
			matcher, err := factory(matcherData.Value())
			if err != nil {
				return nil, err
			}
			return interpreter.NewCall(
				i.ID(), funcName, funcName+"_opt",
				[]interpreter.InterpretableV2{reqAttr},
				func(args ...ref.Val) ref.Val {
					// The request value, guaranteed to be of type celHTTPRequest
					celReq := args[0]
					// If needed this call could be changed to convert the value
					// to a *http.Request using CEL's ConvertToNative method.
					httpReq := celReq.Value().(celHTTPRequest)
					match, err := matcher.MatchWithError(httpReq.Request)
					if err != nil {
						return types.WrapErr(err)
					}
					return types.Bool(match)
				},
			), nil
		}

		if factory, ok := fac.(CELMatcherFactory); ok {
			matcher, err := factory(matcherData.Value())
			if err != nil {
				return nil, err
			}
			return interpreter.NewCall(
				i.ID(), funcName, funcName+"_opt",
				[]interpreter.InterpretableV2{reqAttr},
				func(args ...ref.Val) ref.Val {
					// The request value, guaranteed to be of type celHTTPRequest
					celReq := args[0]
					// If needed this call could be changed to convert the value
					// to a *http.Request using CEL's ConvertToNative method.
					httpReq := celReq.Value().(celHTTPRequest)
					if m, ok := matcher.(RequestMatcherWithError); ok {
						match, err := m.MatchWithError(httpReq.Request)
						if err != nil {
							return types.WrapErr(err)
						}
						return types.Bool(match)
					}
					return types.Bool(matcher.Match(httpReq.Request))
				},
			), nil
		}

		return nil, fmt.Errorf("invalid matcher factory, must be CELMatcherFactory or CELMatcherWithErrorFactory: %T", fac)
	}
}

// CELMatcherRuntimeFunction creates a function binding for when the input to the matcher
// is dynamically resolved rather than a set of static constant values.
func CELMatcherRuntimeFunction(funcName string, fac any) functions.BinaryOp {
	return func(celReq, matcherData ref.Val) ref.Val {
		factoryData := celMatcherUntag(matcherData)
		if types.IsError(factoryData) {
			return factoryData
		}
		factoryFunc := fac
		if factory, ok := fac.(CELMatcherLiteralFactory); ok {
			factoryFunc = CELMatcherWithErrorFactory(factory)
			factoryData = matcherData
		}
		if factory, ok := factoryFunc.(CELMatcherWithErrorFactory); ok {
			matcher, err := factory(factoryData)
			if err != nil {
				return types.WrapErr(err)
			}
			httpReq := celReq.Value().(celHTTPRequest)
			if match, handled, err := celMatchLiteral(matcher, matcherData, httpReq.Request); handled {
				if err != nil {
					return types.WrapErr(err)
				}
				return types.Bool(match)
			}
			match, err := matcher.MatchWithError(httpReq.Request)
			if err != nil {
				return types.WrapErr(err)
			}
			return types.Bool(match)
		}
		if factory, ok := factoryFunc.(CELMatcherFactory); ok {
			matcher, err := factory(factoryData)
			if err != nil {
				return types.WrapErr(err)
			}
			httpReq := celReq.Value().(celHTTPRequest)
			if match, handled, err := celMatchLiteral(matcher, matcherData, httpReq.Request); handled {
				if err != nil {
					return types.WrapErr(err)
				}
				return types.Bool(match)
			}
			if m, ok := matcher.(RequestMatcherWithError); ok {
				match, err := m.MatchWithError(httpReq.Request)
				if err != nil {
					return types.WrapErr(err)
				}
				return types.Bool(match)
			}
			return types.Bool(matcher.Match(httpReq.Request))
		}
		return types.NewErr("CELMatcherRuntimeFunction invalid matcher factory: %T", fac)
	}
}

func celMatcherUntag(v ref.Val) ref.Val {
	switch val := v.(type) {
	case celMatcherLiteralString:
		return val.String
	case traits.Lister:
		var elems []ref.Val
		for i := types.Int(0); i < val.Size().(types.Int); i++ {
			elem := celMatcherUntag(val.Get(i))
			if types.IsError(elem) {
				return elem
			}
			elems = append(elems, elem)
		}
		return types.NewRefValList(types.DefaultTypeAdapter, elems)
	case traits.Mapper:
		entries := make(map[ref.Val]ref.Val)
		for it := val.Iterator(); it.HasNext() == types.True; {
			key := it.Next()
			nativeKey := celMatcherUntag(key)
			if _, exists := entries[nativeKey]; exists {
				return types.NewErr("duplicate matcher map key: %v", nativeKey)
			}
			value := celMatcherUntag(val.Get(key))
			if types.IsError(value) {
				return value
			}
			entries[nativeKey] = value
		}
		return types.NewRefValMap(types.DefaultTypeAdapter, entries)
	}
	return v
}

// celMatchLiteral implements the literal branches of the built-in template
// matchers. Static leaves still go through their normal matcher implementation.
// Other factories receive the same native strings as before.
func celMatchLiteral(matcher any, data ref.Val, r *http.Request) (bool, bool, error) {
	if m, ok := matcher.(MatchVarsRE); ok {
		list, ok := data.(traits.Lister)
		if !ok || list.Size().(types.Int) < 2 {
			return false, false, nil
		}
		key := list.Get(list.Size().(types.Int) - 2)
		if !CELMatcherIsLiteral(key) {
			return false, false, nil
		}
		name := key.Value().(string)
		regexpMatcher, ok := m[name]
		if !ok {
			return false, false, nil
		}
		actual, err := celMatcherVarString(GetVar(r.Context(), name))
		if err != nil {
			return false, true, err
		}
		repl := r.Context().Value(caddy.ReplacerCtxKey).(*caddy.Replacer)
		return regexpMatcher.Match(actual, repl), true, nil
	}
	switch matcher.(type) {
	case MatchPath, MatchHost:
		list, ok := data.(traits.Lister)
		if !ok {
			return false, false, nil
		}
		for i := types.Int(0); i < list.Size().(types.Int); i++ {
			v := list.Get(i)
			s, ok := v.Value().(string)
			if !ok {
				return false, false, nil
			}
			var match bool
			var err error
			switch matcher.(type) {
			case MatchPath:
				if CELMatcherIsLiteral(v) {
					match = CleanPath(normalizeWindowsPath(lowerPath(r.URL.Path)), !strings.Contains(s, "//")) ==
						CleanPath(normalizeWindowsPath(lowerPath(s)), !strings.Contains(s, "//"))
				} else {
					m := MatchPath{s}
					if err = m.Provision(caddy.Context{}); err == nil {
						match, err = m.MatchWithError(r)
					}
				}
			case MatchHost:
				if CELMatcherIsLiteral(v) {
					host, _, splitErr := net.SplitHostPort(r.Host)
					if splitErr != nil {
						host = r.Host
					}
					normalized, convErr := idna.ToASCII(s)
					if convErr != nil {
						return false, true, convErr
					}
					match = strings.EqualFold(strings.Trim(host, "[]"), normalized)
				} else {
					m := MatchHost{s}
					if err = m.Provision(caddy.Context{}); err == nil {
						match, err = m.MatchWithError(r)
					}
				}
			}
			if match || err != nil {
				return match, true, err
			}
		}
		return false, true, nil
	case MatchHeader, MatchQuery, VarsMatcher:
		mapping, ok := data.(traits.Mapper)
		if !ok {
			return false, false, nil
		}
		repl := r.Context().Value(caddy.ReplacerCtxKey).(*caddy.Replacer)
		var query url.Values
		if _, ok := matcher.(MatchQuery); ok {
			var err error
			query, err = url.ParseQuery(r.URL.RawQuery)
			if err != nil {
				return false, true, nil
			}
			if mapping.Size() == types.Int(0) {
				return len(query) == 0, true, nil
			}
		}
		for it := mapping.Iterator(); it.HasNext() == types.True; {
			key := it.Next()
			name := key.Value().(string)
			value := mapping.Get(key)
			values := []ref.Val{value}
			if list, ok := value.(traits.Lister); ok {
				values = nil
				for i := types.Int(0); i < list.Size().(types.Int); i++ {
					values = append(values, list.Get(i))
				}
			}
			var matched bool
			if _, ok := matcher.(MatchHeader); ok && len(values) == 0 {
				var err error
				matched, err = (MatchHeader{name: []string{}}).MatchWithError(r)
				if err != nil {
					return false, true, err
				}
			}
			for _, v := range values {
				s := v.Value().(string)
				var match bool
				var err error
				switch matcher.(type) {
				case MatchHeader:
					if CELMatcherIsLiteral(v) {
						for _, actual := range getHeaderFieldVals(r.Header, name, r.Host, r.TransferEncoding) {
							match = match || actual == s
						}
					} else {
						match, err = (MatchHeader{name: []string{s}}).MatchWithError(r)
					}
				case MatchQuery:
					param := name
					if !CELMatcherIsLiteral(key) {
						param = repl.ReplaceAll(param, "")
					}
					if CELMatcherIsLiteral(v) {
						for _, actual := range query[param] {
							match = match || actual == s
						}
					} else {
						for _, actual := range query[param] {
							expanded := repl.ReplaceAll(s, "")
							match = match || actual == expanded || expanded == "*"
						}
					}
				case VarsMatcher:
					// Runtime keys name variables, never placeholders.
					if CELMatcherIsLiteral(key) && strings.HasPrefix(name, "{") && strings.HasSuffix(name, "}") {
						expected := s
						if !CELMatcherIsLiteral(v) {
							expected = repl.ReplaceAll(s, "")
						}
						actualString, err := celMatcherVarString(GetVar(r.Context(), name))
						if err != nil {
							return false, true, err
						}
						match = actualString == expected
					} else {
						if CELMatcherIsLiteral(v) {
							s = celMatcherEscapeBraces.Replace(s)
						}
						match, err = (VarsMatcher{name: []string{s}}).MatchWithError(r)
					}
				}
				if err != nil {
					return false, true, err
				}
				matched = matched || match
			}
			if _, ok := matcher.(VarsMatcher); ok {
				if matched {
					return true, true, nil
				}
			} else if !matched {
				return false, true, nil
			}
		}
		_, vars := matcher.(VarsMatcher)
		return !vars, true, nil
	}
	return false, false, nil
}

var celMatcherEscapeBraces = strings.NewReplacer("{", `\{`, "}", `\}`)

func celMatcherVarString(value any) (string, error) {
	switch v := value.(type) {
	case nil:
		return "", nil
	case string:
		return v, nil
	case fmt.Stringer:
		return v.String(), nil
	case error:
		if bodyLimit, ok := errors.AsType[RequestBodyLimitError](v); ok {
			return "", HandlerError{Err: bodyLimit, StatusCode: bodyLimit.StatusCode()}
		}
		return v.Error(), nil
	}
	return fmt.Sprint(value), nil
}

// celMatcherStringListMacroExpander validates that the macro is called
// with a variable number of string arguments (at least one).
//
// The arguments are collected into a single list argument the following
// function call returned: <funcName>(request, [args])
func celMatcherStringListMacroExpander(funcName string) cel.MacroFactory {
	return func(eh cel.MacroExprFactory, target ast.Expr, args []ast.Expr) (ast.Expr, *common.Error) {
		matchArgs := []ast.Expr{}
		if len(args) == 0 {
			return nil, eh.NewError(0, "matcher requires at least one argument")
		}
		for _, arg := range args {
			if isCELStringExpr(arg) {
				matchArgs = append(matchArgs, arg)
			} else {
				return nil, eh.NewError(arg.ID(), "matcher arguments must be string constants")
			}
		}
		return eh.NewCall(funcName, eh.NewIdent(CELRequestVarName), CELMatcherArgument(eh, eh.NewList(matchArgs...))), nil
	}
}

// celMatcherStringMacroExpander validates that the macro is called a single
// string argument.
//
// The following function call is returned: <funcName>(request, arg)
func celMatcherStringMacroExpander(funcName string) parser.MacroExpander {
	return func(eh cel.MacroExprFactory, target ast.Expr, args []ast.Expr) (ast.Expr, *common.Error) {
		if len(args) != 1 {
			return nil, eh.NewError(0, "matcher requires one argument")
		}
		if isCELStringExpr(args[0]) {
			return eh.NewCall(funcName, eh.NewIdent(CELRequestVarName), CELMatcherArgument(eh, args[0])), nil
		}
		return nil, eh.NewError(args[0].ID(), "matcher argument must be a string literal")
	}
}

// celMatcherJSONMacroExpander validates that the macro is called a single
// map literal argument.
//
// The following function call is returned: <funcName>(request, arg)
func celMatcherJSONMacroExpander(funcName string) parser.MacroExpander {
	return func(eh cel.MacroExprFactory, target ast.Expr, args []ast.Expr) (ast.Expr, *common.Error) {
		if len(args) != 1 {
			return nil, eh.NewError(0, "matcher requires a map literal argument")
		}
		arg := args[0]

		switch arg.Kind() {
		case ast.StructKind:
			return nil, eh.NewError(arg.ID(),
				fmt.Sprintf("matcher input must be a map literal, not a %s", arg.AsStruct().TypeName()))
		case ast.MapKind:
			mapExpr := arg.AsMap()
			for _, entry := range mapExpr.Entries() {
				isStringPlaceholder := isCELStringExpr(entry.AsMapEntry().Key())
				if !isStringPlaceholder {
					return nil, eh.NewError(entry.ID(), "matcher map keys must be string literals")
				}
				isStringListPlaceholder := isCELStringExpr(entry.AsMapEntry().Value()) ||
					isCELStringListLiteral(entry.AsMapEntry().Value())
				if !isStringListPlaceholder {
					return nil, eh.NewError(entry.AsMapEntry().Value().ID(), "matcher map values must be string or list literals")
				}
			}
			return eh.NewCall(funcName, eh.NewIdent(CELRequestVarName), CELMatcherArgument(eh, arg)), nil
		case ast.UnspecifiedExprKind, ast.CallKind, ast.ComprehensionKind, ast.IdentKind, ast.ListKind, ast.LiteralKind, ast.SelectKind:
			// appeasing the linter :)
		}

		return nil, eh.NewError(arg.ID(), "matcher requires a map literal argument")
	}
}

// CELValueToMapStrList converts a CEL value to a map[string][]string
//
// Earlier validation stages should guarantee that the value has this type
// at compile time, and that the runtime value type is map[string]any.
// The reason for the slight difference in value type is that CEL allows for
// map literals containing heterogeneous values, in this case string and list
// of string.
func CELValueToMapStrList(data ref.Val) (map[string][]string, error) {
	// Prefer map[string]any, but newer cel-go versions may return map[any]any
	mapStrType := reflect.TypeFor[map[string]any]()
	mapStrRaw, err := data.ConvertToNative(mapStrType)
	var mapStrIface map[string]any
	if err != nil {
		// Try map[any]any and convert keys to strings
		mapAnyType := reflect.TypeFor[map[any]any]()
		mapAnyRaw, err2 := data.ConvertToNative(mapAnyType)
		if err2 != nil {
			return nil, err
		}
		mapAnyIface := mapAnyRaw.(map[any]any)
		mapStrIface = make(map[string]any, len(mapAnyIface))
		for k, v := range mapAnyIface {
			ks, ok := k.(string)
			if !ok {
				return nil, fmt.Errorf("unsupported map key type in header match: %T", k)
			}
			mapStrIface[ks] = v
		}
	} else {
		mapStrIface = mapStrRaw.(map[string]any)
	}
	mapStrListStr := make(map[string][]string, len(mapStrIface))
	for k, v := range mapStrIface {
		switch val := v.(type) {
		case string:
			mapStrListStr[k] = []string{val}
		case types.String:
			mapStrListStr[k] = []string{string(val)}
		case []string:
			mapStrListStr[k] = val
		case []ref.Val:
			convVals := make([]string, len(val))
			for i, elem := range val {
				strVal, ok := elem.(types.String)
				if !ok {
					return nil, fmt.Errorf("unsupported value type in matcher input: %T", val)
				}
				convVals[i] = string(strVal)
			}
			mapStrListStr[k] = convVals
		case []any:
			convVals := make([]string, len(val))
			for i, elem := range val {
				switch e := elem.(type) {
				case string:
					convVals[i] = e
				case types.String:
					convVals[i] = string(e)
				default:
					return nil, fmt.Errorf("unsupported element type in matcher input list: %T", elem)
				}
			}
			mapStrListStr[k] = convVals
		default:
			return nil, fmt.Errorf("unsupported value type in matcher input: %T", val)
		}
	}
	return mapStrListStr, nil
}

// celPlaceholderNames returns the name passed to each placeholder call in e,
// or an empty string where the name is not a string literal.
func celPlaceholderNames(e ast.Expr) []string {
	var names []string
	ast.PreOrderVisit(e, ast.NewExprVisitor(func(e ast.Expr) {
		if !isCELCaddyPlaceholderCall(e) {
			return
		}
		name := ""
		if args := e.AsCall().Args(); len(args) == 2 && isCELStringLiteral(args[1]) {
			name = args[1].AsLiteral().Value().(string)
		}
		names = append(names, name)
	}))
	return names
}

// isCELStringExpr indicates whether the expression is a supported string expression
func isCELStringExpr(e ast.Expr) bool {
	return isCELStringLiteral(e) || isCELCaddyPlaceholderCall(e) || isCELConcatCall(e)
}

// isCELStringLiteral returns whether the expression is a CEL string literal.
func isCELStringLiteral(e ast.Expr) bool {
	switch e.Kind() {
	case ast.LiteralKind:
		constant := e.AsLiteral()
		switch constant.Type() {
		case types.StringType:
			return true
		}
	case ast.UnspecifiedExprKind, ast.CallKind, ast.ComprehensionKind, ast.IdentKind, ast.ListKind, ast.MapKind, ast.SelectKind, ast.StructKind:
		// appeasing the linter :)
	}
	return false
}

// isCELCaddyPlaceholderCall returns whether the expression is a caddy placeholder call.
func isCELCaddyPlaceholderCall(e ast.Expr) bool {
	switch e.Kind() {
	case ast.CallKind:
		call := e.AsCall()
		if call.FunctionName() == CELPlaceholderFuncName {
			return true
		}
	case ast.UnspecifiedExprKind, ast.ComprehensionKind, ast.IdentKind, ast.ListKind, ast.LiteralKind, ast.MapKind, ast.SelectKind, ast.StructKind:
		// appeasing the linter :)
	}
	return false
}

// isCELConcatCall tests whether the expression is a concat function (+) with string, placeholder, or
// other concat call arguments.
func isCELConcatCall(e ast.Expr) bool {
	switch e.Kind() {
	case ast.CallKind:
		call := e.AsCall()
		if call.Target().Kind() != ast.UnspecifiedExprKind {
			return false
		}
		if call.FunctionName() != operators.Add {
			return false
		}
		for _, arg := range call.Args() {
			if !isCELStringExpr(arg) {
				return false
			}
		}
		return true
	case ast.UnspecifiedExprKind, ast.ComprehensionKind, ast.IdentKind, ast.ListKind, ast.LiteralKind, ast.MapKind, ast.SelectKind, ast.StructKind:
		// appeasing the linter :)
	}
	return false
}

// isCELStringListLiteral returns whether the expression resolves to a list literal
// containing only string constants or a placeholder call.
func isCELStringListLiteral(e ast.Expr) bool {
	switch e.Kind() {
	case ast.ListKind:
		list := e.AsList()
		for _, elem := range list.Elements() {
			if !isCELStringExpr(elem) {
				return false
			}
		}
		return true
	case ast.UnspecifiedExprKind, ast.CallKind, ast.ComprehensionKind, ast.IdentKind, ast.LiteralKind, ast.MapKind, ast.SelectKind, ast.StructKind:
		// appeasing the linter :)
	}
	return false
}

// Variables used for replacing Caddy placeholders in CEL
// expressions with a proper CEL function call; this is
// just for syntactic sugar.
var (
	// The placeholder may not be preceded by a backslash; the expansion
	// will include the preceding character if it is not a backslash.
	placeholderRegexp    = regexp.MustCompile(`([^\\]|^){([a-zA-Z][\w.-]+)}`)
	placeholderExpansion = `${1}ph(req, "${2}")`

	// As a second pass, we need to strip the escape character in front of
	// the placeholder, if it exists.
	escapedPlaceholderRegexp    = regexp.MustCompile(`\\{([a-zA-Z][\w.-]+)}`)
	escapedPlaceholderExpansion = `{${1}}`

	CELTypeJSON = cel.MapType(cel.StringType, cel.DynType)
)

var httpRequestObjectType = cel.ObjectType("http.Request")

// The name of the CEL function which accesses Replacer values.
const CELPlaceholderFuncName = "ph"

// The name of the CEL request variable.
const CELRequestVarName = "req"

const MatcherNameCtxKey = "matcher_name"

// Interface guards
var (
	_ caddy.Provisioner       = (*MatchExpression)(nil)
	_ RequestMatcherWithError = (*MatchExpression)(nil)
	_ caddyfile.Unmarshaler   = (*MatchExpression)(nil)
	_ json.Marshaler          = (*MatchExpression)(nil)
	_ json.Unmarshaler        = (*MatchExpression)(nil)
)