Zero-allocation* redesign

[clarkmcc]

This issue is meant to be a scratchpad for ideas and feedback on improving how types and values are handled in the interpreter. There have been several different feature requests recently that could be solved by the a fundamental shift in how CEL values are managed.

• https://github.com/clarkmcc/cel-rust/pull/58 - Proposes a way to avoid having to serialize Rust types into CEL Value when only some fields in those types are actually referenced.
• https://github.com/clarkmcc/cel-rust/issues/73 - Requests a way to create actual Rust types in CEL expressions presumably without the intermediate ser/de using a specific format like JSON.
• https://github.com/clarkmcc/cel-rust/pull/68#discussion_r1695592657 - Requests a way to deserialize the result of a CEL expression to a serde_json::Value.

Today any value referenced in a CEL expression is owned by either the Program or the Context. The Program owns values that were created directly in the CEL expression, for example in the expression ("foo" == "bar") == false, there are three values owned by the Program, "foo", "bar", and false. Values that are owned by the Context are values that are dynamically provided at execution time to a Program as variables, like foo == bar, both foo and bar are values owned by the Context.

• I like the idea of fundamentally changing Context so that it does not own any data, meaning that you do not need to clone your types to use them in CEL. Instead I'd like the Context to have references to that data.
• In the case of deeply nested structs, we would provide a derive macro to generate field accessors that the interpreter would call when doing variable resolution. When referencing a property on a struct, CEL would operate on a reference to that data.

Questions:

• Would we even need Arc/Rc's anymore or could we get away with just this since we would assume the caller owned all the data. RIght now, an Arc is required for values owned by Program because a Program can be executed one or more times simultaneously.

  pub enum Value<'a> {
      String(&'a str)
  }
  

• We can easily get references to, and represent primitive types in the interpreter, but what if an expression returned a property whose type was some other user-defined struct? How would we work with that? Perhaps instead of a Value enum, we have a Value trait that exposes every behavior supported in a CEL expression, i.e.:

  pub trait Value {
      fn get_property(&self, key: &str) -> Box<dyn Value>;
  
      fn add(&self, other: &dyn Value) -> Box<dyn Value>;
  
      fn sub(&self, other: &dyn Value) -> Box<dyn Value>;
  }
  

[kyle-mccarthy]

While not zero-allocation, have you considered integrating with the protobuf ecosystem? There is prost-reflect which provides a DynamicMessage trait allowing field access via get_field. Program could then accept a DescriptorPool to help with field and type resolution.

[Caellian]

I like the idea of fundamentally changing Context so that it does not own any data, meaning that you do not need to clone your types to use them in CEL. Instead I'd like the Context to have references to that data.

This only works if you're not passing temporaries into Context, otherwise end-user is forced to keep (moving) them around for as long as the Context is used which is annoying and can be inefficient. I think simply using Cow for values would be simplest and most versatile, while also removing any extra copies/clones.

EDIT 1:

Also, if Value trait is added, and has add function, an additional add_to is required. In math, commutation is proven for numbers via induction and can't be assumed to hold true for every Value.

So the default implementation should be:

/// Called when other [`Value`] is added to this type.
#[inline]
fn add(&self, second: Value) -> ResolveResult {
    Err(ExecutionError::UnsupportedBinaryOperatorExternal(
        "add", std::any::type_name::<Self>(),
    ))
}

/// Called when this type is added to other [`Value`].
/// 
/// Override if addition is non-commutative.
#[inline]
fn add_to(&self, first: Value) -> ResolveResult {
    Self::add(self, first)
}

[Caellian]

Tried doing this at some point, just letting you know you'll need to introduce an additional lifetime to a lot of functions in magic.rs because FunctionContext will require one Value<'the_one>, and that will have to stick around in fully type erased version as well.

I personally don't understand what magic does without spending a day/two examining the code and explanation from the forum, but I'm not invested enough (i.e. too busy) to do so atm.

This is however one of those changes that are better done earlier than later because as more features are tackled on it will be more and more difficult to implement it without breaking/rewriting everything.

[duncanawoods]

I unwisely became obsessed with this in order to support reference external rust types.

1. Lifetimes

I have a working version with lifetimes. The only caveat is that once you introduce lifetimes into the conversion traits, you hit a limitation (bug) in the rust compiler. It's convoluted to explain but essentially (deep breath)... you can't store closures created by a trait that uses other traits with lifetimes without capturing the lifetime which forces them to become invariant statics despite only being used in type signatures and not in any captured reference. It's infuriating because you can write a unit test that works and only discover the issue once you try to return a stored closure.

I've gone in circles trying to solve it with different techniques GAT, Higher-Rank Trait Bounds etc. but it appears to be a hard limitation that they say requires a significant compiler rewrite to fix.

It is however possible to create the closures with normal generic functions but this loses the magic of being able to bind functions of any arity so instead of:

  ctx.add_function("bytes", functions::bytes)
  ctx.add_function("contains", functions::contains)
  ctx.add_function("contains", functions::size)

we have to be explicit about the function arity e.g.

  ctx.add_function_1("bytes", functions::bytes)
  ctx.add_function_2("contains", functions::contains)
  ctx.add_function_1_with_context("size", functions::size);

It's a shame but maybe worth it if references gave a killer benefit.

[duncanawoods]

2. Cow

@Caellia like you, I thought Cow would handle temporaries so I converted every Arc to Cow in the grammar, parser and interpreter. It all worked fine... but it was a time-consuming way to learn that Cow is not a replacement for reference counting.

A Cow supports shallow copy but not shallow clone. When you have a reference to a Cow, you can only shallow clone it if the reference has the same lifetime of the thing it contains and generally that isn't the case i.e.

&'a Cow<'a, str> // can shallow clone
&'b Cow<'a, str> // must deep clone

It meant my implementation was mostly copying Cow::Owned no better than if it was just duplicating String everywhere.

The lesson is that a Cow is only suitable for API boundaries. If you want to share references within a data model then you want reference counting.

(n.b. if the strings are small (which they probably are as keys and such) copying them could well be cheaper than the synchronisation overhead of Arc)

[duncanawoods]

3. Context as an Arena

@clarkmcc it's possible the optimal way to implement a rust interpreter that supports external references is the exact opposite of:

fundamentally changing Context so that it does not own any data

i.e. treat Context as an Arena that owns everything (whether a reference or not) so that Values become ids (indexes) into the Context. It means no reference counting, cloning or lifetime pains when handling values and you tend to see performance gains from collocated data.

It probably requires a mutable context to store new references during expression evaluation and although Values are now very lightweight, they become quite unergonomic where every action requires the Context in order to interpret them e.g.

example_map.get(ctx, "list").iter(ctx).map(x => x.to_string(ctx));

It's a design with debatable appeal but rust often seems to push things in this type of direction.

[duncanawoods]

I personally don't understand what magic does

I think the main puzzle is that most of it is not actually doing anything useful at all!

Here is a simplified version with a single trait:

https://github.com/clarkmcc/cel-rust/pull/133

[clarkmcc]

@duncanawoods

i.e. treat Context as an Arena that owns everything

In your view, how would this impact running the same CEL program concurrently?

Also, the main appeal to borrowing everything is that your CEL environment data has to come from somewhere. If context has to own it, then it needs to be cloned or moved into CEL.

[duncanawoods]

1. In your view, how would this impact running the same CEL program concurrently?

a)

I believe that so long as the type is Send + Sync then an immutable reference can be used across threads. This only causes a problem for types with e.g. raw pointers or Rc. To hold a reference to a type like that, they would need to be wrapped in a mutex.

b)

Although my partial implementation has no issue storing and using references in multithreaded cases, I fear something might crop up in a complete implementation that might uncover a new limitation e.g. the mutability required to store temporary references might be such a thing.

2. If context has to own it, then it needs to be cloned or moved into CEL.

I mean the Context "owns the reference" not that the source object has to be moved/cloned i.e. instead of adding reference support to Value which requires lifetimes on everything that ever touches a Value, the Context has an arena of all borrowed references and the Value only stores a slot-id.

I've gone back and forth on the Arena style. I am currently unsure about how it would handle temporary references so I am currently back to adding foreign type support to a Value with lifetimes.