Add controls for tuning the evaluation cost of the runtime:
Memory
Most operations are have no additional allocation costs beyond the memory required to represent the value within the runtime. There are a couple of exceptions to this rule:

Type conversion functions can result in fixed-size allocations, e.g. string to timestamp.
The re2-based matches performs its own allocations when compiling the input regex pattern.
RE2 provides its own internal control for the limits of the regex.
The + operator supports string / list concat where the memory cost is variable with the size of the input.
CPU
The majority of CEL functions and macros are O(1) or O(n), with a couple of exceptions.

The re2-based matches is linear, but with a high-constant factor.
The in operator can be super-linear when testing for a string value in a non-literal list.
The comprehension macros all, exists, filter, map support bounded iteration and nesting.

Tuning
In many cases, the matches function is eschewed in favor of the simpler startsWith, endsWith, and contains functions.

The in operator can be linted to ensure that a list or map literal appears on the right-hand side of the expression, as this special case is treated as a set membership test rather than as a per-element comparison of the list elements.

Some environments disable the + operator due to its inclusion of string and list overloads. I think that CEL might need to deprecate the concatenation overloads in the near-term in favor of a concat function which can be expressly removed from the environment.

Most of the performance critical use cases for CEL disable macros entirely, though there are a couple of linear-time macros currently supported in Istio.

With the above recommendations, you'll have fixed allocation size operations that run in linear or sub-linear time. If you want to support in and +, I would recommend lint checks on the AST to ensure that they are used in a performance manner (in) or with limited frequency (+).

Example: x.y with {x.y: true} activation
Returns: No value with name \"x\" found in Activation
Expected: true

See #61 for example.
@TristonianJones can you grant me admin access so I can poke around the settings? Or if you have time, can you see why CI integrations is no longer posting notifications.

I hesistate to ask, but can you give me a minimal example of how to evaluate an expression with a set of input values? Build instructions would also be great. Thanks in advance!

I have a use case where the names of the variables in the expression prior to evaluation.

Downstream projects would like to be able to export CEL values to a protobuf serialized form.
This should be a generic function provided by the runtime.

The ast_visitor.h is not pure virtual, but should be.

Example: null == null
Returns: No matching overloads found
Expected: true

Example: 15.75 / 0.0

Returns: <double_value:inf >

Expected: an error

The current activation bindings support proto-based types, but don't support dynamic types such as JSON values well. These tools should be improved to make it easier to construct the input to provide to the CEL evaluation.

Cause: abseil/abseil-cpp#73

Construction string_view from nullptr without length is an undefined behavior in C++ standard while absl accepts it, when building with C++17 absl::string_view is a type alias to std::string_view, then this is no longer true. @kyessenov

stacktrace:

==17==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x7f2d886cd746 bp 0x7ffd45971ff0 sp 0x7ffd459717a8 T0)
==17==The signal is caused by a READ memory access.
==17==Hint: address points to the zero page.
    #0 0x7f2d886cd745 in strlen (/lib/x86_64-linux-gnu/libc.so.6+0x8b745)
    #1 0x6830d18 in strlen /local/mnt/workspace/bcain_clang_bcain-ubuntu_23113/llvm/utils/release/final/llvm.src/projects/compiler-rt/lib/asan/../sanitizer_common/sanitizer_common_interceptors.inc
    #2 0x68f708c in std::__1::char_traits<char>::length(char const*) /opt/llvm/bin/../include/c++/v1/__string:217:53
    #3 0x6ae49c3 in std::__1::basic_string_view<char, std::__1::char_traits<char> >::basic_string_view(char const*) /opt/llvm/bin/../include/c++/v1/string_view:238:31
    #4 0x7200838 in google::api::expr::runtime::CelValue::StringHolderBase<0>::StringHolderBase() /proc/self/cwd/external/com_google_cel_cpp/eval/public/cel_value.h:49:26
    #5 0x754de06 in cel_base::Status google::api::expr::runtime::FunctionAdapter<google::api::expr::runtime::CelValue, google::api::expr::runtime::CelValue::StringHolderBase<0>, google::api::expr::runtime::CelValue::StringHolderBase<0> >::RunWrap<google::api::expr::runtime::CelValue::StringHolderBase<0>, google::api::expr::runtime::CelValue::StringHolderBase<0> >(std::__1::function<google::api::expr::runtime::CelValue (google::api::expr::runtime::CelValue::StringHolderBase<0>, google::api::expr::runtime::CelValue::StringHolderBase<0>)>, absl::Span<google::api::expr::runtime::CelValue const>, google::protobuf::Arena*, google::api::expr::runtime::CelValue*, int) const /proc/self/cwd/external/com_google_cel_cpp/eval/public/cel_function_adapter.h:155:9
    #6 0x754d6d2 in google::api::expr::runtime::FunctionAdapter<google::api::expr::runtime::CelValue, google::api::expr::runtime::CelValue::StringHolderBase<0>, google::api::expr::runtime::CelValue::StringHolderBase<0> >::Evaluate(absl::Span<google::api::expr::runtime::CelValue const>, google::api::expr::runtime::CelValue*, google::protobuf::Arena*) const /proc/self/cwd/external/com_google_cel_cpp/eval/public/cel_function_adapter.h:189:12
    #7 0x78b9e0a in google::api::expr::runtime::(anonymous namespace)::FunctionStep::Evaluate(google::api::expr::runtime::ExecutionFrame*) const /proc/self/cwd/external/com_google_cel_cpp/eval/eval/function_step.cc:61:27
    #8 0x78e4530 in google::api::expr::runtime::CelExpressionFlatImpl::Trace(google::api::expr::runtime::Activation const&, google::protobuf::Arena*, std::__1::function<cel_base::Status (long, google::api::expr::runtime::CelValue const&, google::protobuf::Arena*)>) const /proc/self/cwd/external/com_google_cel_cpp/eval/eval/evaluator_core.cc:34:25
    #9 0x78e3cf8 in google::api::expr::runtime::CelExpressionFlatImpl::Evaluate(google::api::expr::runtime::Activation const&, google::protobuf::Arena*) const /proc/self/cwd/external/com_google_cel_cpp/eval/eval/evaluator_core.cc:22:10
    #10 0x6b0b724 in Envoy::Extensions::Filters::Common::Expr::evaluate(google::api::expr::runtime::CelExpression const&, google::protobuf::Arena*, Envoy::StreamInfo::StreamInfo const&, Envoy::Http::HeaderMap const*, Envoy::Http::HeaderMap const*, Envoy::Http::HeaderMap const*) /proc/self/cwd/source/extensions/filters/common/expr/evaluator.cc:74:27
    #11 0x6b0bc93 in Envoy::Extensions::Filters::Common::Expr::matches(google::api::expr::runtime::CelExpression const&, Envoy::StreamInfo::StreamInfo const&, Envoy::Http::HeaderMap const&) /proc/self/cwd/source/extensions/filters/common/expr/evaluator.cc:85:22
    #12 0x6a8c651 in Envoy::Extensions::Filters::Common::RBAC::PolicyMatcher::matches(Envoy::Network::Connection const&, Envoy::Http::HeaderMap const&, Envoy::StreamInfo::StreamInfo const&) const /proc/self/cwd/source/extensions/filters/common/rbac/matchers.cc:171:37
    #13 0x6a6e7c1 in Envoy::Extensions::Filters::Common::RBAC::RoleBasedAccessControlEngineImpl::allowed(Envoy::Network::Connection const&, Envoy::Http::HeaderMap const&, Envoy::StreamInfo::StreamInfo const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*) const /proc/self/cwd/source/extensions/filters/common/rbac/engine_impl.cc:35:24
    #14 0x68c7840 in Envoy::Extensions::Filters::Common::RBAC::(anonymous namespace)::checkEngine(Envoy::Extensions::Filters::Common::RBAC::RoleBasedAccessControlEngineImpl const&, bool, Envoy::Network::Connection const&, Envoy::Http::HeaderMap const&, envoy::api::v2::core::Metadata const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*) /proc/self/cwd/test/extensions/filters/common/rbac/engine_impl_test.cc:32:3
    #15 0x68d83c0 in Envoy::Extensions::Filters::Common::RBAC::(anonymous namespace)::RoleBasedAccessControlEngineImpl_HeaderCondition_Test::TestBody() /proc/self/cwd/test/extensions/filters/common/rbac/engine_impl_test.cc:285:3
    #16 0xee06eed in void testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2447:10
    #17 0xedb3355 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2483:14
    #18 0xed5cf86 in testing::Test::Run() /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2522:5
    #19 0xed5fc8f in testing::TestInfo::Run() /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2698:11
    #20 0xed62280 in testing::TestSuite::Run() /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2828:28
    #21 0xed92a11 in testing::internal::UnitTestImpl::RunAllTests() /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:5285:44
    #22 0xee1ab8b in bool testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2447:10
    #23 0xedbe975 in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:2483:14
    #24 0xed90837 in testing::UnitTest::Run() /proc/self/cwd/external/com_google_googletest/googletest/src/gtest.cc:4873:10
    #25 0xa8bb27f in RUN_ALL_TESTS() /proc/self/cwd/external/com_google_googletest/googletest/include/gtest/gtest.h:2453:46
    #26 0xa8b8342 in Envoy::TestRunner::RunTests(int, char**) /proc/self/cwd/test/test_runner.cc:121:10
    #27 0xa8b1855 in main /proc/self/cwd/test/main.cc:46:10
    #28 0x7f2d8866282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #29 0x681e028 in _start (/b/f/w/bazel-out/k8-dbg/bin/test/extensions/filters/common/rbac/engine_impl_test.runfiles/envoy/test/extensions/filters/common/rbac/engine_impl_test+0x681e028)

The cel-spec lists a number of type conversion methods. A fraction of them are supported in cel-cpp, but the full set should be added.

When the expression is syntactically incorrect, we get a helpful error message:

ERROR: <input>:1:33: Syntax error: token recognition error at: '"'
 | unmatched_quotation_mark_follows"
 | ................................^

When there is a semantic error, we get a message but no character position:

"foo" + 5

No matching overloads found

Is there some way to get this information from semantic errors? Thanks!

Examples:

• [] == []
• [1,2,3] == [1,2,3]
• [[]] != [[]]
• [] != [1]

Returns: No matching overloads found

Expected: a boolean

Examples:

• {} == {}
• {'k':'v'} == {'k':'v1'}
• {'k':'v','k1':'v1'} == {'k':'v'}

Returns: No matching overloads found

Expected: a boolean

The cel-go evaluator and cel-cpp evaluator should use the same error codes and messages for the same error conditions.

Cross-referenced in google/cel-go#25.

Activation doesn't support customization of its implementation which is useful and needed when there are large number of attributes but only a small part of them are used in the evaluation.
In this case we may want to avoid copying all the unused attributes before evaluation. If customization is supported, a user could have their own Activation implementation and then dispatch the attribute look-up dynamically. This also opens more flexibility on the usage of the Activation.

The easiest way might be just to add the virtual keyword to the following functions.

  // Provide value that is bound to the name, if found.
  // arena parameter is provided to support the case when we want to pass the
  // ownership of returned object ( Message/List/Map ) to Evaluator.
  absl::optional<CelValue> FindValue(absl::string_view name,
                                     google::protobuf::Arena* arena) const;

  // Insert value into Activation.
  void InsertValue(absl::string_view name, const CelValue& value);

  // Insert ValueProducer into Activation.
  void InsertValueProducer(absl::string_view name,
                           std::unique_ptr<CelValueProducer> value_producer);

  // Removes value or producer, returns true if entry with the name was found
  bool RemoveValueEntry(absl::string_view name);

Similar to the Activation interface in golang:
https://github.com/google/cel-go/blob/ebbdb2886430bee8aa24a7f83a4ecb99db312478/interpreter/activation.go#L28

@kyessenov @TristonianJones Any thoughts on this? I'm still learning the CEL library so please let me know if I missed anything important or if this is already supported in cpp. Thank you.

There seems to be something wrong with Travis ATM. See #45, for example.

When performing arithmetic operations, the operators should return errors on loss of precision.

The comprehension expression flattening step is overly complicated and difficult to maintain and could benefit from refactoring.

The presence of a BUILD file here:
https://github.com/googleapis/googleapis/blob/master/google/api/BUILD.bazel
and not any where in the expr dir, makes it so you can't inject a build file and use the protos.

@TristonianJones @JimLarson

@kyessenov @asraa
When creating an expression with && or || function, providing with no args field proves to be fatal.
This is an example of the minimal failing testcase. Attached is a local run of such a test case in cel-cpp.
R"(
call_expr: <
function: "&&"
>
)";

Screenshot 2020-07-24 at 12 21 15 PM

This issue is found by a Envoy fuzzer run, which is also linked here https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=21777&can=2&q=envoy

StackTrace of the envoy fuzz test

TestRandomGenerator running with seed -549535368
  | external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:110:19: runtime error: member call on null pointer of type 'google::api::expr::runtime::JumpStepBase'
  | #0 0x9d64fc in google::api::expr::runtime::(anonymous namespace)::FlatExprVisitor::Jump::set_target(int) /proc/self/cwd/external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:110:19
  | #1 0x9d4cf3 in google::api::expr::runtime::(anonymous namespace)::FlatExprVisitor::BinaryCondVisitor::PostVisit(google::api::expr::v1alpha1::Expr const*) /proc/self/cwd/external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:501:14
  | #2 0x9bcca3 in google::api::expr::runtime::(anonymous namespace)::FlatExprVisitor::PostVisitCall(google::api::expr::v1alpha1::Expr_Call const*, google::api::expr::v1alpha1::Expr const*, google::api::expr::runtime::SourcePosition const*) /proc/self/cwd/external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:266:21
  | #3 0xa92fa4 in google::api::expr::runtime::(anonymous namespace)::PostVisit(google::api::expr::runtime::(anonymous namespace)::StackRecord const&, google::api::expr::runtime::AstVisitor*) /proc/self/cwd/external/com_google_cel_cpp/eval/public/ast_traverse.cc:101:16
  | #4 0xa91db1 in google::api::expr::runtime::AstTraverse(google::api::expr::v1alpha1::Expr const*, google::api::expr::v1alpha1::SourceInfo const*, google::api::expr::runtime::AstVisitor*) /proc/self/cwd/external/com_google_cel_cpp/eval/public/ast_traverse.cc:227:7
  | #5 0x9b73a2 in google::api::expr::runtime::FlatExprBuilder::CreateExpression(google::api::expr::v1alpha1::Expr const*, google::api::expr::v1alpha1::SourceInfo const*, std::__1::vector<absl::Status, std::__1::allocatorabsl::Status >) const /proc/self/cwd/external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:693:3
  | #6 0x9b9002 in google::api::expr::runtime::FlatExprBuilder::CreateExpression(google::api::expr::v1alpha1::Expr const, google::api::expr::v1alpha1::SourceInfo const*) const /proc/self/cwd/external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:714:10
  | #7 0x5becb4 in Envoy::Extensions::Filters::Common::Expr::createExpression(google::api::expr::runtime::CelExpressionBuilder&, google::api::expr::v1alpha1::Expr const&) /proc/self/cwd/source/extensions/filters/common/expr/evaluator.cc:60:40
  | #8 0x461358 in Envoy::Extensions::Filters::Common::Expr::(anonymous namespace)::TestOneProtoInput(test::extensions::filters::common::expr::EvaluatorTestCase const&) /proc/self/cwd/test/extensions/filters/common/expr/evaluator_fuzz_test.cc:43:32
  | #9 0x460f42 in LLVMFuzzerTestOneInput /proc/self/cwd/test/extensions/filters/common/expr/evaluator_fuzz_test.cc:21:1
  | #10 0x56db546 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /src/libfuzzer/FuzzerLoop.cpp:558:15
  | #11 0x56c7041 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /src/libfuzzer/FuzzerDriver.cpp:296:6
  | #12 0x56ca48a in fuzzer::FuzzerDriver(int*, char***, int ()(unsigned char const, unsigned long)) /src/libfuzzer/FuzzerDriver.cpp:796:9
  | #13 0x56c6d7a in main /src/libfuzzer/FuzzerMain.cpp:19:10
  | #14 0x7fad2936a82f in __libc_start_main /build/glibc-LK5gWL/glibc-2.23/csu/../csu/libc-start.c:291
  | #15 0x440538 in _start (/mnt/scratch0/clusterfuzz/bot/builds/clusterfuzz-builds_envoy_13526b3cec4fe4a2eb6540004a639d98790ed27f/revisions/evaluator_fuzz_test+0x440538)
  |  
  | SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior external/com_google_cel_cpp/eval/compiler/flat_expr_builder.cc:110:19 in

CEL supports the concept of a qualified container name, e.g. a.b.c and when Enum values are referenced relative to a container or when the container is non-empty, the evaluator can't resolve the reference.

Including the core Value type and associated classes.