Repository navigation
Optimize policy validation when there are many errors in a large policy set #2598
Description
Due to how errors are de-duplicated, policy validation can be excessively slow for large policy sets containing many errors. While this case isn't particularly important (validation is required prior to TPE or symbolic compilation, so we'd like it to be fast, but we can assume these policies are almost always valid), I think we can improve it.
Errors are de-duplicated by inserting into a HashSet, but errors have a source location which holds an Arc<str>, so hashing it potentially expensive for a large policy document.
For example, this policy found in fuzzing.
forbid(
principal,
action,
resource
) when {
(((((true && (if (if (if ([].contains([[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[], [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[context, context, context, context], [context, context, context, context], [context, context, context, context], [context, context, context, context]], [[context, context, {}, {}], [{}], [{}], [{}]], [[{}]], [[{}]]], [[[{}]]], [[[{}]]], [[[{}]]]], [[[[{}]]]], [[[[{}]]]], [[[[{}, {}, {}, {}, {}, {}]]]]], [[[[[], [], [], [], [{}, {}, {}, context, {}, {}, {}], [{}]], [], [[{}]], [[]], [[{}]], [[{}]]], [[[{}, {}, {}, {}, {}, {}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}, context, context, {}], [{}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, context]], [[{}, {}, {}, context, context], [], [], [{}, {}, {}, context, {}, {}, context], [{}, {}, {}, {}, {}, {}, {}], [{}, {}], [{}, {}, {}, {}, {}, {}, {}]]], [[[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [context, {}, {}, {}, {}, {}, {}], [{}, context]], [[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}], [{}, {}, {}], [{}, context, context], [], [context, context, context], []], [[{}, context, context, context, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, context, context, context, context, context], []], [], [], [], []], [], [[[], [{}, {}, {}, {}, {}], [{}, {}]], [[context, context], []], [], [], []], []], [], [], [], [], []], [], []], [], [], []], [[[[[[[{}, {}, {}, {}, {}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]]]], [[[[], [[{}, {}, {}, {}, {}, {}]], [], []], [], []], [], []], [], [], [], [[[[[{}, {}], [{}, {}]], [[], []]], []], []], []], [], [], [], [], [[[[[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]]], [[[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}]], [[{}]]]]], []], []], [], []], [], [], []], [], [], []], [], [], []]]]]]]]]]], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [[[[[[]]]]]], [], [], [], [], []], [], [], [], [], [], []], [[[[[[[[[[[[[[[[[[[[[[[[], [], [], [], [], []], [], [[[[[[], [[{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}]], [[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [context, {}, {}, {}, {}, {}, {}], [{}, context]], [[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}], [{}, {}, {}], [{}, context, context], [], [context, context, context], []], [[{}, context, context, context, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}], [{}, context, context, context, context, context], []], [], []], [], [], [], [[[], [{}, {}, {}, {}, {}], [{}, {}]], [[context, context], []], [], [], []], [], []], [], [], [], []], [], [], [], [], [], [[[[[{}, {}, {}, {}, {}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}, {}, context, context, {}]], [[{}, {}], [{}, {}], [], [], [], []]], [], []], [], [], [], [[[[{}, {}], [{}, {}]], [[context, context], []]], []], [], []]], [], [], []], [[[[[[[{}, {}], [{}, {}, {}, {}, {}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}, {}, {}, {}]]]], [[[[{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}]], [[{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}]], [[{}, {}, {}, {}, {}], [{}, {}, {}, {}, {}], [{}, {}, {}, {}, context], [{}, {}, {}, {}, {}, {}, {}], []], [[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}], [{}], [{}]], [[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, context], [], [], [], [], []]], [], [], [[[{}]]], [[[{}]]]]], [[[[[{}, {}, {}, {}, {}]]]]]], [[[[[[{}]]]]]]], [[[[], []], [], [[[[[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, context, {}, {}, {}]], [[{}, {}, {}, {}, {}, {}, {}], [{}], [{}], [{}], [context], [context, context, context, context], [context, context, context, context]], [[context, context, context, context], [context, context, context, context], [context, context, context, context], [context, context, context, context]], [[{}, {}, {}, {}], [{}], [{}], [{}]], [[{}]], [[{}]], [[{}]]], [[[{}]]], [[[{}]]], [[[{}]]], [[[{}]]], [[[{}]]], [[[{}, {}, {}, {}, {}, {}], [{}, context, context, context, context, {}], [{}, {}, context, {}, {}, {}, {}], [context, {}, {}, {}, {}, context], [{}], [{}]], [[{}, {}, {}, {}, {}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]]], [[[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}, context, context, {}]]], [[[{}, {}], [{}, {}, {}, {}, {}]], [[{}, context, {}, {}, {}, {}], [context, context, context, {}], [{}, {}], [{}, {}, context, {}], [{}, {}, {}, {}, {}, {}, {}]], [[{}, {}], [{}, {}, {}, {}, {}, context], [context, context, context, context, {}, {}, {}], [context, {}, {}, context, {}, context, {}], [{}, {}, {}, context, {}, {}, {}], [{}, {}, context, context, context, context, context], [context, context, context, context]], [[context, context, context, context], [{}, {}, context, context, context], [context, context, context, context], [context, context, context, context]], [[context, context, context, context], [context, context, context, context], [context, context, context, context], [context, {}, {}, {}]], [[{}, {}, context, {}, context, context], [{}, {}], [{}, {}, context, context, context, context], [], [], []]]], [[[[{}, {}, {}, {}, {}, {}], [context], [context, context, context, context], [context, context, context, context], [context, context, context, context], [{}, {}, context, context, context]], [[context, context, context, context], [context, context, context, context], [context, context, context, context], [context, context, context, context]], [[context, context, context, context], [context, context, context, context], [context, context, context, context], [context, context, context, context]], [[context, context, {}, {}], [{}, {}], [{}, {}, {}, {}, {}, {}], []], [], []], [[[context, {}, context, {}], []], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], [[], [[[[[{}, {}], [{}, {}]], [[{}, context, context], [{}], [{}, {}], [{}, {}], []], [], []], []], []], [], [], [], []], [[[[[[{}, {}], [{}, {}]], []], []], []], []], []], [], []], [], [], [[[[[[[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]]], [[[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]], [[[{}, {}], [{}, {}]], [[{}, {}], [{}, {}]]]]], [[[[[context]]]]]], []], []], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], []], [], [], [], [[[[[[[[[[[[[], [[], [], [[[[], [[{}]], [[{}]], [[{}]], [[{}]], [[{}, {}, {}, {}, {}, {}], [{}], [{}], [{}], [{}], [{}]]]]], [[[[[{}, {}, {}, context, {}, {}, {}], [{}, {}, {}, {}, {}, {}, {}], [{}, {}, context, {}, {}, {}, {}], [{}, {}, context, {}, {}, context, context]]]]], [[]]]], [[[[[[[{}]]]]], [[[[[{}]]]]]], [[[[[[{}, {}, {}, {}, {}, {}, {}], [{}, {}, {}, {}, {}, context, context], [], [], [], [], []]], [], [], [], [], [], []]]], [], [], [], []], [], [], []], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], []]]]]]]], [], [], [], []], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], []], [], []], [], [], [], [], []], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []], [], [], [], [], [], []])) then false else false) then false else false) then false else false)) && false) && false) && false) && false) && false
};
Reacted by Lucas Käldström
Activity
Hash only the span of a `Loc`
Hash only the span of a Loc (fixes cedar-policy#2598)
Vedthakar commentedon Oct 21, 2026
I opened #2636 for this:
Locnow hashes only its span, so de-duplicating validation errors is no longer quadratic in the size of the policy set.— Ved Thakar
Precompute the hash of a Loc's source text (fixes cedar-policy#2598)