Late Function Bindings in Go Cel Evaluation

[mswest46]

Currently, function definitions must be provided in the parsing step, so data relevant to their definition must be available at that step. This request is to support binding a function at activation time instead. As a use case example, I'd like to write a function has_tag :: string -> bool whose implementation checks membership in a list tags that is only available at evaluation time and remains hidden from the expression writer.

[JimLarson]

We're discussing a generalization of this - allow functions to access the full Activation, not just the supplied variables. This way you could bind tags as a variable at runtime in the normal way, but it would be hidden from the expression if you omit it from the declarations at type check time. This would require a separate flavor of overload which would accept something like func(interpreter.Activation, ...ref.Val) ref.Val.

[hyp0th3rmi4]

I have stumbled upon a use case for this feature which would be elegantly solved by allowing to override some of the bindings used during program evaluation. By digging down into the source code the function bindings are resolved when the program is created here:

https://github.com/google/cel-go/blob/master/cel/program.go#L180-L203

and become part of the interpreter that is used to create the interpretable. Out of function calls found in the expression, the planner will create one of the following Interpretable implementations (reference: https://github.com/google/cel-go/blob/master/interpreter/planner.go#L211-L285):

• evalZeroArity (impl: functions.FunctionOp)
• evalUnary (impl: functions.FunctionUnaryOp)
• evalBinary (impl: functions.FunctionBinaryOp)
• evalVarArgs (impl: functions.FunctionOp)

because all of them retain a function and overload identifier, their corresponding evaluation method can lookup the activation and eventually replace such binding with the late bound supplied version of the same function signature.

I think we should still be checking during program.Eval(....) that all signatures and bindings that are overridden match so that any calculation that has been done before and validation still remains valid.

Another option would be passing a decorator to the program.Eval, to do this job by scanning the interpretable and perform the replacement.

I don't think that the code changes are massive, they seem rather contained to a couple of files at first site. If this is a viable solution I can prepare a PR that implement one of the two approaches below:

Approach 1: With Activation and Internal CustomDecorator

• Define a new type of activation that contains overridden bindings.
• Define a custom decorator that is injected if the Activation contains binding definitions.
• The decorator can then check the interpretables whose types match the above evalXXX types and perform the replacements as needed.
• Modify program.Eval(...) to validate the overrides have a matching function signature.
• Inject the decorator as part of: https://github.com/google/cel-go/blob/master/cel/program.go#L301

Approach 2: With Custom Decorator Only

• Same approach as above but rather than using a special activation modify the Eval(....) methods to accept new parameters, one of these being an InterpretableDecorator.

Approach 3: Add a ProgramOption

Unfortunately, we cannot achieve this by adding an additional EvalOption which would lead to adding an InterpretableDecorator, because these are collected too early in the cycle and are not supplied at evaluation time but when the environment is created. If we could have evaluation options, late in the cycle this could also be a viable solution, but it seems to me that it will require too many change and lead to a more careful analysis of the impact. EvalOption functions seem to be involved in the construction of the interpretable at program creation time and not at the evaluation time.

Verdict

Personally I think that implementing a custom InterpretableDecorator for this task and defining a new Activation type including bindings might be a better way, simply because we don't have to modify the interface of the types and therefore we can use this behaviour with the existing code. Therefore Approach 1 would be preferred, also because with respect to Approach 2 it does not open up to other behaviours that we don't want to support yet.

Suggested Code Changes

in: https://github.com/google/cel-go/blob/master/interpreter/decorators.go

// LateBindinsDispatcher returns a dispatcher that contains the supplied overloads.
// The function checks that each of the overload is defined in the parent dispatcher
// because they are expected to be overrides and not new dispatchers. If any of the
// dispatchers does not match a corresponding overload in the parent then or it has
// a different arity, it then returns an error.
func lateBindingsDispatcher(bindings []*functions.Overload, parent Dispatcher) (Dispatcher, error) {
      lateDispatcher := &defaultDispatcher{
            overloads: make(map[string]*functions.Overload)
      }
      for _, binding := range bindings {

          // does the current dispatcher have the overload?
          // if not skip and don't include it
          if overload, found := dispatcher.FindOverload(binding.Operator); found {

            // the lightest check we can do is ensuring at least
            // that the number of parameters matches, by checking
            // which operator is defined. We don't have the ability
            // to check that types are compatible because there is
            // not enough information to do this check.
            if (binding.UnaryOp == nil && overload.UnaryOp != nil) || (binding.UnaryOp != nil && binding.UnaryOp == nil) {
                  return nil, fmt.Errorf("overload unary operator mismatch (id: '%s')", binding.Operator)
            }

            if (binding.BinaryOp == nil && binding.BinaryOp != nil) || (binding.BinaryOp != nil && binding.BinaryOp == nil) {
                  return nil, fmt.Errorf("overload binary operator mismtach (id: '%s')", binding.Operator)
            }

            if (binding.FunctionOp == nil && binding.FunctionOp != nil) || (binding.FunctionOp != nil && binding.FunctionOp == nil) {
                  return nil, fmt.Errorf("overload function operator mismtach (id: '%s')", binding.Operator)
            }
            
            lateDispatcher.overloads[binding.Operator] = binding
          } else {
            return nil, fmt.Errorf("overload does not exist: '%s'", binding.Operator)
          }
      }

      return &lateDispatcher, nil
}


// lateBindingDispatcher produces an interpretable decorator that replaces
// function calls with the overloads defined in the dispatcher passed as
// arguments. If the overload is not found, no change is made to the 
// interpretable.
func lateBindingsDecorator(dispatcher Dispatcher) InterpretableDecorator {


      return func(i interpreter.Interpretable) (interpreter.Interpretable, error) {
          call, ok := i.(interpreter.InterpretableCall)
	    if !ok {
		return i, nil
	    }

          switch inst := i.(type) {

            case *evalZeroArity:
                  overload, found := dispatcher.FindOverload(inst.overload)
                  if found {
                        return &evalZeroArity{
                              id: inst.id,
                              function: inst.function,
                              overload: inst.overload,
                              impl: overload.FunctionOp,
                        }, nil
                  }
            case *evalUnary:
                  overload, found := dispatcher.FindOverload(inst.overload)
                  if found {
                        return &evalUnary{
                              id: inst.id,
                              interpretable: inst.interpretable,
                              function: inst.function,
                              overload: inst.overload,
                              trait: inst.trait,
                              nonStrict: inst.nonStrict, 
                              impl: overload.UnaryOp,
                        }, nil
                  }
            case *evalBinary:
                  overload, found := dispatcher.FindOverload(inst.overload)
                  if found {
                        return &evalBinary{
                              id: inst.id,
                              lhs: inst.lhs,
                              rhs: inst.rhs,
                              function: inst.function,
                              overload: inst.overload,
                              trait: inst.trait,
                              nonStrict: inst.nonStrict, 
                              impl: overload.UnaryOp,
                        }, nil
                  }
            case *evalVarArgs:
                  verload, found := dispatcher.FindOverload(inst.overload)
                  if found {
                        return &evalVarArgs{
                              id: inst.id,
                              args: inst.args,
                              function: inst.function,
                              overload: inst.overload,
                              trait: inst.trait,
                              nonStrict: inst.nonStrict, 
                              impl: overload.UnaryOp,
                        }, nil
                  }
            default:
                  return nil, types.NewErr("invalid type: %s", inst)

          }

          return i, nil
      }
}

func ReplaceBindings(
	interpretable intepreter.Interpretable,
	bindings []*function.Overload,
	dispatcher Dispatcher
) (interpreter.Interpretable, error) {

	lateDispatcher, err := interpreter.LateBindingDispatcher(bindings, p.dispatcher)
	if err != nil {
		return nil, err
	}
        lateDecorator = lateBindingsDecorator(lateDispatcher)

        // here is where we need to have the ability to visit the interpretable
        // the decorator I have implemented only performs the replacement
        // if the input is of type InterpretableCall. 

        return visit(interpretable, lateDecorator)
}

in: https://github.com/google/cel-go/blob/master/interpreter/activation.go

// Overloads returns the function overloads that have been added to the
// activation. The function recursively check the activations based on
// the known types.
func Overloads(activation interpreter.Activation) map[string]*functions.Overload {

	overloads := map[string]*functions.Overload{}
	if activation == nil {
		return overloads
	}
	
	switch inst := activation.(type) {
	case *emptyActivation: 
		return []*functions.Overload{},
	case *mapActivation:
		for k, v := range inst.bindings {

			if overload, ok := v.(*functions.Overload), ok {
				overloads[overload.Operator] = overload
			}
		}
	case *hierarchicalActivation:
		overloads = Overloads(inst.parent)
		override  = Overloads(inst.child)

		for k, v := range override {
			overloads[k] = v
		}
	case *partActivation:
		overloads = Overloads(inst.Activation)
	}

	return overloads
}

in: https://github.com/google/cel-go/blob/master/cel/program.go#L301

    overloads := Overloads(vars)
    target := p.interpretable

    if len(overloads) > 0 {
		bindings := make([]*functions.Overload, len(overloads))
		int i := 0
	
		for _, binding := range overloads {
			bindings[i] = binding
		}
		interpretable, err = interpreter.ReplaceBindings(intepretable, bindings, p.dispatcher)
		if err != nil {
			return nil, err
		}
		target = interpretable
     }
    v = target.Eval(vars)

@mswest46 and @JimLarson I know this thread has gone cold, but I would be interested in understanding if a PR with the behaviour described above would be welcomed. If becomes really hard to implement a visitor for the Interpretable perhaps this option isn't really feasible.