modulepackage
0.0.0-20241107054834-eb74745331d0
Repository: https://github.com/inngest/expr.git
Documentation: pkg.go.dev
# README
Aggregate expression engines
This repo contains Inngest's aggregate expression engine service, turning O(n^2) expression matching into O(n).
It does this by:
- Parsing each expression whilst lifting literals out of expressions
- Breaking expressions down into subgroups (matching && comparators)
- Storing each group's comparator in a matching engine for fast lookups
When an event is received, instead of matching the event against every expression, we instead inspect each matching engine to filter out invalid expressions. This leaves us with a subset of expressions that are almost always matching for the event, simplifying the number of expressions to match against.
Copyright Inngest 2024.
# Functions
EnvCompiler turns a *cel.Env into a CELParser.
No description provided by the author
NewCachingCompiler returns a CELCompiler which lifts quoted literals out of the expression as variables and uses caching to cache expression parsing, resulting in improved performance when parsing expressions.
NewTreeParser returns a new tree parser for a given *cel.Env.
# Constants
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
VarPrefix is the lifted variable name used when extracting idents from an expression.
# Variables
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
# Structs
ExpressionPart represents a predicate group which is part of an expression.
Leaf represents the leaf within a tree.
PredicateGroup represents a group of predicates that must all pass in order to execute the given expression.
ParsedExpression represents a parsed CEL expression into our higher-level AST.
Predicate represents a predicate that must evaluate to true in order for an expression to be considered as viable when checking an event.
StoredExpressionPart is a lightweight expression part which only stores a hash of the predicate to reduce memory usage.
# Interfaces
AggregateEvaluator represents a group of expressions that must be evaluated for a single event received.
CELCompiler represents a CEL compiler which takes an expression string and returns a CEL AST, any issues during parsing, and any lifted and replaced from the expression.
Evaluable represents an evaluable expression with a unique identifier.
LiftedArgs represents a set of variables that have been lifted from expressions and replaced with identifiers, eg `id == "foo"` becomes `id == vars.a`, with "foo" lifted as "vars.a".
MatchingEngine represents an engine (such as a b-tree, radix trie, or simple hash map) which matches a predicate over many expressions.
TreeParser parses an expression into a tree, with a root node and branches for each subsequent OR or AND expression.
# Type aliases
No description provided by the author
EvaluableLoader returns one or more evaluable items given IDs.
ExpressionEvaluator is a function which evalues an expression given input data, returning a boolean and error.
No description provided by the author
StringExpression is a string type that implements Evaluable, useful for basic ephemeral expressions that have no lifetime.