Add a 100KB cap on compiled regex NFA size via RegexBuilder::size_limit()
to block patterns that blow up in memory or CPU. Regex compilation now
goes through a single helper (compile_regex_for_builtin) so the limit
is enforced consistently across all regex builtins.
While doing this, found and fixed a pre-existing bug: resource-limit
errors (time, memory, instruction count) raised inside builtins were
quietly swallowed to Undefined when strict_builtin_errors was off
(the default). This is a problem because `not regex.match(...)` would
see Undefined and flip to true -- silently wrong. The same issue now
applies to the new regex size limit.
Fixed by teaching the three error-absorption paths (interpreter builtin
call, RVM builtin dispatch, and RVM rule-execution loop) to recognize
LimitError and let it propagate instead of eating it.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Add VM support for Azure Policy's condition operators and allOf/anyOf
short-circuit logic, gated behind cfg(feature = "azure_policy").
Policy conditions (equals, contains, like, match, exists, and their
negations — 21 total) are encoded as a single PolicyCondition
instruction with a PolicyOp sub-opcode rather than bloating the
Instruction enum with 21 variants. The dispatch handles Azure Policy's
quirky comparison semantics: case-insensitive string comparison,
string↔number coercion, null vs undefined distinction, and element-wise
collection membership.
allOf/anyOf blocks use four instructions — LogicalBlockStart,
AllOfNext/AnyOfNext, and LogicalBlockEnd — that wire up a result
register and short-circuit on the first failing (allOf) or passing
(anyOf) child.
Helper functions for case-folded comparison, wildcard/glob matching, and
type coercion live in builtins::azure_policy::helpers.
Two YAML test suites (~2200 lines) exercise the full operator matrix and
the allOf/anyOf control flow.
Default-only rules (e.g., `default deny := true` with no conditional body)
returned Undefined in the RVM instead of the default value.
Compiler:
- compute_rule_type: return Complete when rule exists only in default_rules map
- compile_worklist_rule: emit register slots and data-tree entries for
default-only rules (else branch)
VM:
- execute_call_rule_common + execute_call_rule_suspendable: check
default_literal_index before returning Undefined when definitions is empty
Tests:
- 3 new RVM cases (default_rules.yaml): bool, object, entry-point
- 3 new interpreter cases (default/basic.yaml): matching coverage
Co-authored-by: Mark Birger <markbirger@microsoft.com>
The Rego VM was designed around Rego's semantics, but Azure Policy needs
a few things Rego doesn't: host-supplied context alongside input/data,
undefined-to-null coercion for missing fields, skip-undefined collection
behavior for wildcard aliases, and non-vacuous iteration over non-array
values.
This commit adds five new instructions to bridge those gaps:
LoadContext / LoadMetadata — give programs access to host-supplied
evaluation context and cached program metadata at runtime.
ArrayPushDefined — like ArrayPush but silently drops undefined values,
so wildcard alias collection (field[*].property) excludes absent
nested properties instead of leaking undefined entries into the array.
ReturnUndefinedIfNotTrue — early return with Undefined when a guard
condition isn't satisfied, without tripping a VM assertion failure.
This models "condition doesn't match" cleanly.
CoalesceUndefinedToNull — turns Undefined into Null in-place so that
downstream builtins see null rather than short-circuiting on undefined.
The loop engine also gains an Azure Policy mode: when the source language
is "azure_policy", an Every loop over a non-array value (scalars, null,
objects) iterates once over a virtual Null element instead of being
vacuously true. This matches how field[*] behaves on non-array fields
in Azure Policy — the condition body runs once against Null, which
typically evaluates to false.
On the plumbing side: the VM gets a context field with set_context(),
metadata is cached as a Value on program load, and map_limit_error is
inlined into memory_check since it had only one call site.
Four new YAML test suites (~880 lines) cover the new instructions and
context/metadata loading, along with instruction parser, display, and
assembly listing support for everything added here.
Merge the three separate Assert* instructions (AssertNot, AssertCondition,
AssertNotUndefined) into a single `Guard { register, mode }` instruction
with a GuardMode enum. This cuts duplicated match arms across display,
listing, parser, dispatch, and all compiler emit sites.
Drop the unnecessary `#[repr(C)]` from the Instruction enum. It was never
exposed across FFI, so the C-compatible 4-byte discriminant was pure waste.
Without it Rust picks a 1-byte discriminant, shrinking every instruction
from 8 bytes to 6. A new `instruction_size` unit test locks this at 6.
While touching these files, also clean up several long-standing issues:
- Deduplicate the iteration-state setup in loops.rs by extracting a shared
resolve_iteration_state() helper -- the stack-based and stackless paths
had near-identical 40-line blocks.
- Collapse the ExitWithSuccess / ExitWithFailure match arms into one.
- In rules.rs, stop cloning Arc<Program> just to borrow a RuleInfo -- clone
the small RuleInfo struct directly and extract a get_rule_info() helper.
- Move the memory check into dispatch (runs per instruction) and remove the
now-dead enforce_memory_check() entry-point calls.
- Apply map_or_else style throughout listing.rs for consistency.
* perf!: add LRU caches for compiled regex and glob patterns
Add bounded LRU caches for compiled regex and glob patterns used by
Rego builtins, avoiding repeated recompilation of the same patterns
during policy evaluation.
New `cache` feature (included in `full-opa` and `opa-no-std`) backed by
the `lru` crate (no_std compatible) with `spin::Mutex` for thread safety.
- `src/cache.rs`: generic `LruCache<V>` wrapper, global `REGEX_CACHE`
(default capacity 256) and `GLOB_CACHE` (default capacity 128)
- `src/builtins/regex.rs`: all regex builtins route through the cache
- `src/builtins/glob.rs`: glob.match routes through the cache
- Public API: `regorus::cache::{Config, configure, clear}`
Compilation costs avoided per cache hit:
regex 10-55 µs (simple to complex patterns)
glob 10-12 µs
LRU hit ~10 ns
BREAKING CHANGE: new `cache` Cargo feature added to `full-opa` and
`opa-no-std` feature sets; adds `lru` as a dependency.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* perf(vm): amortize per-instruction memory and time limit checks
Deduplicate per-instruction memory_check calls by hoisting them to the
main dispatch loop, and amortize monotonic_now() syscalls in the
execution timer by checking elapsed time every N instructions instead
of on every tick.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* fix(vm): correct object membership to check values only, not keys
The Contains instruction for objects was checking both keys and values:
object_fields.contains_key(v) || object_fields.values().any(|v| ...)
Per the Rego specification, `x in obj` tests whether x is a VALUE of
the object, not a key. The two-argument form `k, v in obj` is needed
to access keys. The interpreter already implemented this correctly
(values-only scan), but the RVM had the extra contains_key() check
which would incorrectly return true when the search value happened to
match a key name.
Remove the contains_key() branch so the behavior matches the interpreter
and the Rego spec. Add two regression tests:
- object_membership_checks_values_not_keys: "foo" in {"foo": "bar"}
must be false (key, not a value)
- object_membership_finds_value: "bar" in {"foo": "bar"} must be true
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* perf(compiler): hoist all-constant collection literals to the literal table
When an array, set, or object literal consists entirely of compile-time
constant expressions (numbers, strings, bools, null, and nested constant
collections), the compiler now evaluates them at compile time and emits a
single Load instruction from the literal table instead of generating
per-element instructions at runtime.
Previously, a Rego expression like `x in [1, 2, 3]` would emit
ArrayCreate + three Load + three ArrayAppend instructions, allocating a
new Vec and Rc on every evaluation. With this change, the entire array
is built once during compilation and loaded as a single constant.
This optimization applies to all three collection types:
- Array literals: avoids ArrayCreate + N x (Load + ArrayAppend)
- Set literals: avoids SetCreate + N x (Load + SetAdd)
- Object literals: avoids ObjectCreate + N x (Load + Load + ObjectInsert)
The implementation adds a try_eval_const() helper that recursively
evaluates an AST expression as a constant Value, returning None if any
sub-expression is non-constant. Each compile method for collection
literals attempts the all-constant fast path first and falls through to
the existing instruction-by-instruction codegen otherwise.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* perf(compiler): fuse Eq + AssertCondition into AssertEq instruction
Add a new `AssertEq { left, right }` instruction that combines equality
comparison and condition assertion into a single operation. This replaces
the previous two-instruction pattern of `Eq { dest, left, right }` followed
by `AssertCondition { condition: dest }`, saving one instruction and one
register per equality assertion.
The fused instruction checks two registers for equality and directly calls
handle_condition with the result, avoiding the intermediate boolean
register entirely. If either operand is undefined or the values differ,
the condition fails and the rule/loop backtracks.
The optimization applies to four destructuring sites:
- EqualityCheck (assignment re-binding with `x = expr; x = expr`)
- EqualityExpr (destructuring against an expression)
- EqualityValue (destructuring against a literal value)
- assert_array_length (array length validation in destructuring)
In soft_assert_mode the compiler still emits the original Eq instruction
since the boolean result register is needed by callers.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* perf(compiler): fuse Not + AssertCondition into AssertNot instruction
Add a new `AssertNot { operand }` instruction that combines logical
negation and condition assertion into a single operation. This replaces
the previous two-instruction pattern of `Not { dest, operand }` followed
by `AssertCondition { condition: dest }`, saving one instruction and one
register allocation.
The fused instruction checks the operand register and passes the
condition if the value is false or undefined (per Rego semantics where
`not expr` succeeds when the expression has no results or is false),
and fails the condition if the value is true or any non-boolean truthy
value.
This was the only emission site for the Not+AssertCondition pair,
occurring in the compilation of `Literal::NotExpr` statements.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* perf(vm): early exit for same-value multi-definition rules
When a rule has multiple definitions that all produce the same value
(e.g. implicit true, or identical literal), set early_exit_on_first_success
on RuleInfo so the VM can stop after the first successful definition.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* feat!: expose cache configuration API to all language bindings
Add `set_cache_config` and `clear_cache` functions to every binding
so callers can tune or reset the global regex/glob pattern caches
introduced in the cache feature.
Bindings updated:
- FFI (C): `regorus_set_cache_config`, `regorus_clear_cache`
- C++ header: free functions `regorus::set_cache_config`, `regorus::clear_cache`
- Python: module-level `set_cache_config(*, regex, glob)`, `clear_cache()`
- Java: static methods on new `CacheConfig` class
- Go: package-level `SetCacheConfig`, `ClearCache`
- Ruby: module functions `Regorus.set_cache_config`, `Regorus.clear_cache`
- WASM: free functions `setCacheConfig`, `clearCache`
- C#: static methods `Engine.SetCacheConfig`, `Engine.ClearCache`
BREAKING CHANGE: Bump SERIALIZATION_VERSION from 4 to 5 due to new
AssertEq and AssertNot instruction variants added in the instruction
fusion commits. Programs serialized with version 5 cannot be loaded
by older versions of regorus.
* fix: address PR review feedback
Cache subsystem:
- Gate REGEX_CACHE and related imports behind #[cfg(feature = "regex")]
so that building with --features cache without regex compiles correctly.
- Gate LruCache struct behind #[cfg(any(feature = "regex", feature = "glob"))].
- Add Config::MAX_CAPACITY (2^16) hard upper bound; clamp values in
configure() to prevent unbounded cache growth.
- Use parking_lot::Mutex for std builds and spin::Mutex for no_std to
avoid CPU spinning under contention in tight regex/glob eval loops.
- Narrow lock scopes in regex/glob builtins: release the mutex before
compiling a pattern, then re-acquire to insert.
Java JNI binding:
- Fix cache config overflow: negative jlong values now saturate to 0
and positive overflow saturates to usize::MAX (then clamped by
MAX_CAPACITY) instead of silently disabling the cache.
- Gate JNI cache config/clear functions behind #[cfg(feature = "cache")].
Compiler:
- Refactor static_value_of_expr to delegate to try_eval_const,
gaining support for negated numbers and constant collections.
- Make try_eval_const pub(in crate::languages::rego::compiler) and
re-export through expressions.rs.
- Handle Expr::UnaryExpr with numeric literals in try_eval_const so
collections containing negated numbers (e.g. [-1, 2]) are hoisted.
VM correctness:
- Fix Not instruction to follow Rego semantics: not expr yields
true when expr is undefined or false, false for any other defined
value (including non-booleans) -- no longer errors on non-boolean
operands.
- Add enforce_memory_check() call at execute_suspendable_entry to
ensure memory limits are checked before the first instruction.
- Update AssertNot listing comment to "exit if any defined truthy
value" to match actual VM behaviour.
- Add doc comment on Not instruction clarifying Rego negation
semantics.
Bindings:
- Fix C++ header indentation for set_cache_config / clear_cache.
- Propagate Cargo.lock parking_lot addition across ffi, java, python,
and wasm binding lockfiles.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
---------
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
Handle imports that don't use the `as` clause to create a binding.
These imports are bound to the last identifier in the imported path.
Fix both interpreter and compiler.
Add tests.
fixes#541
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- ensure both run-to-completion and suspendable rule execution stop evaluating
bodies once one succeeds so later else branches are skipped
- test cases
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- treat set subtraction in RVM the same as the interpreter by supporting
Value::Set operands in sub_values
- emit internal-only builtin names for set union/intersection and register
handlers so compiled bytecode resolves without exposing new Rego builtins
- add regression coverage for literal set difference/intersection
(x/y from failure.rego) in tests/rvm/rego/cases/sets.yaml
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- emit AssertCondition for equality-only assignment plans (outside soft-assert mode) so rules like `0 = 1` fail under the VM just like the interpreter
- let comprehension bodies consume assertion failures by advancing or exiting their iteration context, both in run-to-completion and suspendable execution
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
Allow compile_chained_ref to fall back to “evaluate root expression → chain access”
so literal arrays, comprehensions, and other computed roots no longer raise NotSimpleReferenceChain.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
Mirror interpreter implementation:
- use builtins::must_cache to determine whether builtin must be cached.
- reuse cached value when applicable
- clear the VM’s builtin cache whenever execution state resets to avoid leaking values across runs
- add a YAML regression for rand.intn set comprehensions and re-enable the rand cases in the OPA test suite
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- Add a scoped soft_assert_mode to the compiler so `not` statements compile their subexpressions without emitting hard AssertCondition/AssertNotUndefined instructions.
- Teach binding-plan application to return an optional result register; equality plans now yield a boolean in soft mode, allowing not abs(-5 , 3) to succeed instead of aborting.
- Update function-call, loop, and rule plumbing to consume the new binding-plan outcome, including copying the produced register when an out-parameter equality is used.
- Trim the OPA TODO list to the remaining troublesome folders.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- Teach the hoister/destructuring planner to respect parent scope when building binding plans for extra arguments, so already-bound vars yield equality checks.
- Update the compiler’s function-call path to drop the trailing out-argument, run its binding plan after the call, and share call-target resolution logic.
- Add regression suites for builtin and user-defined out-parameter scenarios plus align the CLI example output when RVM returns undefined.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
- Supply chain: Use the popular num-bigint crate for handling large integers
- Optimization: Handle f64, i64, u64 directly. These will be the most common instances of a number.
OPA number semantics isn't clear.
https://github.com/open-policy-agent/opa/issues/6281
As part of this change, we update the following failing tests:
- A local test that relies on what 15.3/3 evaluates to.
With our current change, we round in a different direction than what OPA does, but consistent
with Rust. We produce 5.1000000000000005 where as the OPA test expects 5.1.
There is no clear definition in Rego of what the right answer is. Moreover, policies should not
rely on exact floating point value comparison. Therefore this deviations is justified.
The test is patched to pass.
- Another local vm test that exercised 1.1 + 2.2
- Another local vm test that exercises 5.5 - 2.2
- An OPA test that expects that a large integer number say 10e308 is printed in exponent notation.
num-bigint does not print using scientific notation and instead prints all the digits.
The benefit of preserving this compatibility is not clear. We skip this test.
- Doc tests that exercised handling floating point numbers with more than 15 (what f64 supports)
digits of precision. There is no usecase for this scenario. The tests are updated to reflect
the behavior.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* feat!: add Rego Virtual Machine (RVM) implementation
This commit introduces a register-based virtual machine for executing Rego
policies with bytecode-style instructions. Unlike the existing tree-walking
interpreter, the RVM compiles policies into instruction sequences that operate
on virtual registers, offering better performance and optimization potential.
Core Components:
Instruction Set Architecture:
- Define instruction types for data operations, control flow, and builtins
- Implement instruction parameter encoding and display formatting
- Add instruction parser with comprehensive test coverage
Virtual Machine Engine:
- Register-based execution model with program counter management
- Loop execution supporting iterators, comprehensions, and quantifiers
- Function call handling with argument evaluation and context management
- Rule evaluation with default value resolution and virtual data support
- Arithmetic and comparison operation implementations
Program Representation:
- Program listing builder with instruction sequencing
- Rule tree construction for organizing policy rules
- Binary and JSON serialization for compiled programs
- Recompilation support for program modification
Testing Infrastructure:
- Extensive YAML test suites covering all VM features
- Rust unit tests for VM execution and instruction parsing
- Test suites for loops, comprehensions, builtins, and control flow
BREAKING CHANGE: Introduces new VM execution path alongside interpreter
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
* docs: add detailed RVM architecture references
Introduce architecture.md explaining program artifacts, serialization, and runtime subsystems.
Document the full opcode catalog in instruction-set.md, including operands, parameter tables, and outcomes.
Walk through execution flow, stacks, and operational guidance in vm-runtime.md, tying the runtime to the new architecture docs.
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
---------
Signed-off-by: Anand Krishnamoorthi <anakrish@microsoft.com>
