ValidatorSchema::get_actions_in_set materializes a Vec of all RHS action descendants that type_of_action_in_actions then scans linearly, instead of O(1) HashSet lookups, on every action in [...] type… #2586

Before opening, please confirm:

• I have searched for duplicate or closed issues.
• I have read the guide for submitting bug reports.
• I have done my best to include a minimal, self-contained set of instructions for consistently reproducing the issue.

Describe the bug

Location: cedar-policy-core/src/validator/schema.rs:1096-1112 at dddbdff0 (on main)

Description

ValidatorSchema::get_actions_in_set collects, for each RHS action EUID, an iterator over its full transitive descendants set (a HashSet<EntityUID>) chained with the action itself, and flattens everything into a freshly allocated Vec<&EntityUID>. Its only caller, SingleEnvTypechecker::type_of_action_in_actions (cedar-policy-core/src/validator/typecheck.rs, if let Some(rhs_descendants) = self.schema.get_actions_in_set(rhs) followed by rhs_descendants.into_iter().any(|e| e == lhs)), then does a linear scan of that Vec comparing EntityUIDs to find the LHS action. This runs for every action in Action::"group" / action in [...] expression — which appears in the condition of nearly every policy that constrains the action scope — and typecheck_policy re-typechecks the condition once per request environment (the full P×R×action cross product derived from the schema). The membership question is answerable in O(1) per RHS action because ValidatorActionId::descendants is already a HashSet<EntityUID>.

Impact

For a schema with A actions where action groups have D transitive member actions, each action in node costs one Vec allocation of ~D references plus up to D EntityUID equality comparisons, repeated for every request environment (commonly hundreds to thousands of envs for realistic schemas) and every policy. Validating P policies against E envs performs O(P × E × D) EntityUID comparisons and O(P × E) heap allocations where O(P × E × |rhs|) hash lookups (no allocation) would suffice. A profiler running Validator::validate on a schema with large action groups will show this in get_actions_in_set/type_of_action_in_actions.

Suggestion

Replace the materialize-then-scan pattern with direct hash-set membership: in type_of_action_in_actions, for each RHS EUID do self.schema.get_action_id(rhs_euid).map(|a| a.name == *lhs || a.descendants.contains(lhs)), short-circuiting on the first true and preserving the existing None-propagation (fail/partial-mode behavior) when any RHS action is not defined. get_actions_in_set can then be removed or reduced to a boolean is_action_in_set(lhs, rhs) helper on ValidatorSchema that never allocates.

Reproduction steps

// Put your code below this line.