Compile policy into an optimized state machine

[DemiMarie]

How to file a helpful issue

The problem you're addressing (if any)

qrexec policy evaluation uses a slow linear search in Python.

The solution you'd like

Compile the policy into an optimized state machine that can evaluate policy in O(log N) time or better, where N is the number of rules in the policy. Then use this optimized state machine to respond to queries.

Qrexec policy evaluation is a simpler version of ML pattern matching, for which highly efficient algorithms are known.

The value to a user, and who that user might be

All users will benefit from faster qrexec calls.

Completion criteria checklist

(This section is for developer use only. Please do not modify it.)

[marmarek]

Duplicate of #6266

[github-actions]

This issue has been closed as a "duplicate." This means that another issue exists that is very similar to or subsumes this one. If any useful information on this issue is not already present on the other issue, please add it in a comment on the other issue. Here are some common cases of duplicate issues:

• The other issue is closed. The other issue being closed does not prevent this issue from duplicating it. We will examine the closed issue and, if appropriate, reopen it.
• The other issue is for a different Qubes release. We usually maintain only one issue for all affected Qubes releases.
• The other issue is very old. The mere age of an issue is not, by itself, a relevant factor when determining duplicates.

By default, the newer issue will be closed in favor of the older issue. However, we make exceptions when we determine that it would be significantly more useful to keep the newer issue open instead of the older one.

We respect the time and effort you have taken to file this issue, and we understand that this outcome may be unsatisfying. Please accept our sincere apologies and know that we greatly value your participation and membership in the Qubes community.

If anyone reading this believes that this issue was closed in error or that the resolution of "duplicate" is not accurate, please leave a comment below saying so, and we will review this issue again. For more information, see How issues get closed.