mirror of
https://github.com/microsoft/regorus.git
synced 2026-08-05 02:16:11 +00:00
49bd3c22f3
* 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>
285 lines
7.7 KiB
YAML
285 lines
7.7 KiB
YAML
# Copyright (c) Microsoft Corporation.
|
|
# Licensed under the MIT License.
|
|
|
|
# Set Operations Test Suite
|
|
# Tests set creation, deduplication, and membership testing
|
|
# Covers complex value deduplication, nested sets, and undefined handling
|
|
|
|
cases:
|
|
- note: set_deduplication_simple
|
|
description: Set automatically deduplicates simple values
|
|
example_rego: "{1, 2, 1, 3, 2}"
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }" # 1
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }" # 2
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "SetAdd { set: 0, value: 1 }" # 1 again (duplicate)
|
|
- "Load { dest: 3, literal_idx: 2 }" # 3
|
|
- "SetAdd { set: 0, value: 3 }"
|
|
- "SetAdd { set: 0, value: 2 }" # 2 again (duplicate)
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
|
|
- note: set_deduplication_objects
|
|
description: Set deduplicates identical objects
|
|
example_rego: "{{\"a\": 1}, {\"b\": 2}, {\"a\": 1}}"
|
|
literals:
|
|
- {"a": 1}
|
|
- {"b": 2}
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }" # {"a": 1}
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }" # {"b": 2}
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "SetAdd { set: 0, value: 1 }" # {"a": 1} again (duplicate)
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- {"a": 1}
|
|
- {"b": 2}
|
|
|
|
- note: set_deduplication_arrays
|
|
description: Set deduplicates identical arrays
|
|
example_rego: "{[1, 2], [3, 4], [1, 2]}"
|
|
literals:
|
|
- [1, 2]
|
|
- [3, 4]
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }" # [1, 2]
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }" # [3, 4]
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "SetAdd { set: 0, value: 1 }" # [1, 2] again (duplicate)
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- [1, 2]
|
|
- [3, 4]
|
|
|
|
- note: set_with_mixed_types
|
|
description: Set can contain different types
|
|
example_rego: "{1, \"text\", true, null, [1, 2], {\"a\": 1}}"
|
|
literals:
|
|
- 1
|
|
- "text"
|
|
- [1, 2]
|
|
- {"a": 1}
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }" # 1
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }" # "text"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "LoadTrue { dest: 3 }"
|
|
- "SetAdd { set: 0, value: 3 }"
|
|
- "LoadNull { dest: 4 }"
|
|
- "SetAdd { set: 0, value: 4 }"
|
|
- "Load { dest: 5, literal_idx: 2 }" # [1, 2]
|
|
- "SetAdd { set: 0, value: 5 }"
|
|
- "Load { dest: 6, literal_idx: 3 }" # {"a": 1}
|
|
- "SetAdd { set: 0, value: 6 }"
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- 1
|
|
- "text"
|
|
- true
|
|
- null
|
|
- [1, 2]
|
|
- {"a": 1}
|
|
|
|
- note: set_contains_simple
|
|
description: Contains check on set with simple values
|
|
example_rego: "2 in {1, 2, 3}"
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "Load { dest: 3, literal_idx: 2 }"
|
|
- "SetAdd { set: 0, value: 3 }"
|
|
- "Contains { dest: 4, collection: 0, value: 2 }"
|
|
- "Return { value: 4 }"
|
|
want_result: true
|
|
|
|
- note: set_contains_object
|
|
description: Contains check with object value
|
|
example_rego: "{\"a\": 1} in {{\"a\": 1}, {\"b\": 2}}"
|
|
literals:
|
|
- {"a": 1}
|
|
- {"b": 2}
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "Contains { dest: 3, collection: 0, value: 1 }"
|
|
- "Return { value: 3 }"
|
|
want_result: true
|
|
|
|
- note: set_contains_not_found
|
|
description: Contains returns false when value not in set
|
|
example_rego: "5 in {1, 2, 3}"
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
- 5
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "Load { dest: 3, literal_idx: 2 }"
|
|
- "SetAdd { set: 0, value: 3 }"
|
|
- "Load { dest: 4, literal_idx: 3 }"
|
|
- "Contains { dest: 5, collection: 0, value: 4 }"
|
|
- "Return { value: 5 }"
|
|
want_result: false
|
|
|
|
- note: set_create_from_registers
|
|
description: SetCreate instruction creates set from multiple registers
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
instruction_params:
|
|
set_create_params:
|
|
- dest: 0
|
|
elements: [1, 2, 3, 1] # Duplicate 1
|
|
instructions:
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "Load { dest: 3, literal_idx: 2 }"
|
|
- "SetCreate { params_index: 0 }"
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
|
|
- note: set_create_with_undefined_element
|
|
description: SetCreate with undefined element returns undefined (short-circuit)
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- "#undefined"
|
|
instruction_params:
|
|
set_create_params:
|
|
- dest: 0
|
|
elements: [1, 2, 3] # r3 is undefined
|
|
instructions:
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "Load { dest: 3, literal_idx: 2 }" # r3 is explicitly undefined
|
|
- "SetCreate { params_index: 0 }"
|
|
- "Return { value: 0 }"
|
|
want_result: "#undefined"
|
|
|
|
- note: set_large_collection
|
|
description: Set with many elements (stress test)
|
|
literals:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
- 4
|
|
- 5
|
|
- 6
|
|
- 7
|
|
- 8
|
|
- 9
|
|
- 10
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "Load { dest: 3, literal_idx: 2 }"
|
|
- "SetAdd { set: 0, value: 3 }"
|
|
- "Load { dest: 4, literal_idx: 3 }"
|
|
- "SetAdd { set: 0, value: 4 }"
|
|
- "Load { dest: 5, literal_idx: 4 }"
|
|
- "SetAdd { set: 0, value: 5 }"
|
|
- "Load { dest: 6, literal_idx: 5 }"
|
|
- "SetAdd { set: 0, value: 6 }"
|
|
- "Load { dest: 7, literal_idx: 6 }"
|
|
- "SetAdd { set: 0, value: 7 }"
|
|
- "Load { dest: 8, literal_idx: 7 }"
|
|
- "SetAdd { set: 0, value: 8 }"
|
|
- "Load { dest: 9, literal_idx: 8 }"
|
|
- "SetAdd { set: 0, value: 9 }"
|
|
- "Load { dest: 10, literal_idx: 9 }"
|
|
- "SetAdd { set: 0, value: 10 }"
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
- 1
|
|
- 2
|
|
- 3
|
|
- 4
|
|
- 5
|
|
- 6
|
|
- 7
|
|
- 8
|
|
- 9
|
|
- 10
|
|
|
|
- note: set_empty
|
|
description: Empty set creation
|
|
example_rego: "set()"
|
|
literals: []
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!: []
|
|
|
|
- note: set_nested_in_set
|
|
description: Set containing other sets
|
|
example_rego: "{{1, 2}, {3, 4}}"
|
|
literals:
|
|
- set!:
|
|
- 1
|
|
- 2
|
|
- set!:
|
|
- 3
|
|
- 4
|
|
instructions:
|
|
- "SetNew { dest: 0 }"
|
|
- "Load { dest: 1, literal_idx: 0 }"
|
|
- "SetAdd { set: 0, value: 1 }"
|
|
- "Load { dest: 2, literal_idx: 1 }"
|
|
- "SetAdd { set: 0, value: 2 }"
|
|
- "Return { value: 0 }"
|
|
want_result:
|
|
set!:
|
|
-
|
|
set!:
|
|
- 1
|
|
- 2
|
|
-
|
|
set!:
|
|
- 3
|
|
- 4
|