As a reminder, PRs marked as draft will not be automatically assigned reviewers,
or be handled by maintainer-oncall triage.

Please mark your PR as ready when you want it to be reviewed!

CC @envoyproxy/api-shepherds: Your approval is needed for changes made to (api/envoy/|docs/root/api-docs/).
envoyproxy/api-shepherds assignee is @markdroth
CC @envoyproxy/api-watchers: FYI only for changes made to (api/envoy/|docs/root/api-docs/).
CC @envoyproxy/dependency-shepherds: Your approval is needed for changes made to (bazel/.*repos.*\.bzl)|(bazel/dependency_imports\.bzl)|(api/bazel/.*\.bzl)|(.*/requirements\.txt)|(.*\.patch).
envoyproxy/dependency-shepherds assignee is @moderation

/retest
(looks like just flakes)

/retest

/coverage

Coverage for this Pull Request will be rendered here:

https://storage.googleapis.com/envoy-pr/38986/coverage/index.html

The coverage results are (re-)rendered each time the CI envoy-presubmit (check linux_x64 coverage) job completes.

Thanks for bringing this up! I agree that the current behavior seems strange.

It seems like the behavior we really want here is that if a subtree does not find a match and does not have an on_no_match, then we consider the match in the parent to have not actually matched -- i.e., the parent should react as if it had not found that match in the first place and had never recursed into the sub-tree. However, if the sub-tree does have an on_no_match, then I think we should choose that, and at that point, the parent should consider the sub-tree to have produced a match.

I agree that for the prefix map matcher specifically, it makes sense that if a sub-tree is considered to not have matched, that we should look for other, less-specific prefix matches before defaulting to on_no_match. However, I think that's just a special case, because the general problem can show up with any type of matcher. For example, if we have a list matcher that selects a sub-tree, and that sub-tree does not find a match and does not have an on_no_match, then the parent list matcher should ideally execute its own on_no_match. So I think we need a more general solution here; simply providing a new variant of the prefix map matcher doesn't seem to fully solve the problem.

If we agree that this general principle is correct, then we have to figure out how to get to that behavior from where we are today. I see two main options:

1. We could simply declare the current behavior to be a bug and fix it, possibly adding a runtime option as a migration tool for those that may be depending on the current behavior. This would not require any API changes, but it might make the migration harder for users. It's not clear to me how many existing users would be affected.
2. If we don't want to break any existing behavior, then we need to add an API knob to select the new behavior. However, as I mentioned above, I think we need to solve it for all matcher types, not just adding a new variant of the prefix map matcher. Maybe we can just add a new bool field in the top-level Matcher proto that controls how this works?

I'd like input from @snowp, who initially wrote the matcher code.

Also, I am wondering if this has any overlap with #38726 from @bsurber.

This retry feature does look similar to what I had in mind when considering how to do re-entry for prefix map matchers. The largest difference is that a reentrant object would go back to the match caller, which is also capable of continuing "retries" (in this PR's parlance) from where the last match call ended.

Implementation wise, I was considering doing the re-entry/retry by tracking each matching path along the way down the trie in a separate vector of pointers (optional parameter). Then the reentrant would just have to step backwards through that vector to find the next-longest match, instead of starting at the top of the trie all over again: O(n) vs O(n^2) execution at the cost of O(n) memory & enabling further re-entry at a specified index.

This retry feature does look similar to what I had in mind when considering how to do re-entry for prefix map matchers. The largest difference is that a reentrant object would go back to the match caller, which is also capable of continuing "retries" (in this PR's parlance) from where the last match call ended.

I'm happy for it to be done that way - I was aiming for "minimal disruption" in my implementation, but I agree it would be nicer if it was made more generally "this is how it's supposed to work."

Implementation wise, I was considering doing the re-entry/retry by tracking each matching path along the way down the trie in a separate vector of pointers. Then the reentrant would just have to step backwards through that vector to find the next-longest match, instead of starting at the top of the trie all over again: O(n) vs O(n^2) execution at the cost of O(n) memory.

I also considered that. O(n) memory being the cost is a bit simplistic though - a vector is also another allocation, or potentially several, and O(n^2) is while technically accurate not really a sensible way to look at it when the real world case is going to be O(2n), maybe O(3n). A prefix config that's like /banana, /banan, /bana, /ban, /ba, /b, / isn't really going to happen.
If preferring a vector I would suggest using absl::InlinedVector<T, 4> to avoid extra allocations in the common cases. (3 is realistic, but it's a short-lived thing so the memory impact is negligible, 4 or even 8 would be fine.)

Happy to defer to #38726 for implementation; I can contribute a vector-returning trie lookup if that would help. (Edit: #39011)

Setting aside the question of implementation overlap with @bsurber's work, I think we still need to decide the overall API question here. The keep_matching knob that @bsurber is adding is for a use-case where we want individual rules to decide whether they will be considered a match, but I think the question being asked in this PR is more about whether we want a match that goes to a sub-tree to be considered a match if nothing in the sub-tree matches. I don't think that's something that can be configured via keep_matching, because it will apply in cases where there is no matching OnMatch field in which to look at the value of keep_matching.

because it will apply in cases where there is no matching OnMatch field in which to look at the value of keep_matching.

I think bsurber's implementation could do what we want. It would be quite a bit more verbose in the config than my model, but I'm assuming it would work to have a config like (pseudo-config):

prefix_match_tree:
  "/foo/bar":
    match_list:
       has_some_header: whatever
       on_no_match: keep_matching [null or do-nothing action]
  "/foo":
    match_list:
       has_some_other_header: whatever
       on_no_match: keep_matching [null or do-nothing action]
  on_no_match: some_default_action

I also considered that. O(n) memory being the cost is a bit simplistic though - a vector is also another allocation, or potentially several, and O(n^2) is while technically accurate not really a sensible way to look at it when the real world case is going to be O(2n), maybe O(3n). A prefix config that's like /banana, /banan, /bana, /ban, /ba, /b, / isn't really going to happen. If preferring a vector I would suggest using absl::InlinedVector<T, 4> to avoid extra allocations in the common cases. (3 is realistic, but it's a short-lived thing so the memory impact is negligible, 4 or even 8 would be fine.)

We could also avoid the vector output by adding optional parent references to the trie nodes. The reentrant would just need to track the current node & iterate up through the parents. It'd touch more code but could be preferable (requires touching the actual trie lib, not just the matchers).

For the trie-based matcher, we actually do perform the traversal (see https://github.com/cncf/xds/blob/main/xds/type/matcher/v3/domain.proto#L39), so maybe we need to define a new kind of prefix matcher as a custom matcher?

For the trie-based matcher, we actually do perform the traversal (see https://github.com/cncf/xds/blob/main/xds/type/matcher/v3/domain.proto#L39), so maybe we need to define a new kind of prefix matcher as a custom matcher?

"The trie-based matcher" is a confusing thing to say, because prefix_map_matcher is also trie-based. Also confusing to link to that xds proto which doesn't seem to be used at all in envoy except in a fuzz test. I eventually figured out you meant trie_matcher.h does a multimatch.

Anyway, it certainly would be possible to implement this as just a custom matcher, if that's the preferred way. Bit weird since the API would be an exact duplicate of the existing API but it would have to either duplicate or wrap the existing message because custom extensions must use unique types. And mostly duplicate the code. And every time there's a custom extension point it makes the documentation painful to navigate. But if that's what it takes to get something useable I'm happy to go that way.

For the trie-based matcher, we actually do perform the traversal (see https://github.com/cncf/xds/blob/main/xds/type/matcher/v3/domain.proto#L39), so maybe we need to define a new kind of prefix matcher as a custom matcher?

"The trie-based matcher" is a confusing thing to say, because prefix_map_matcher is also trie-based. Also confusing to link to that xds proto which doesn't seem to be used at all in envoy except in a fuzz test. I eventually figured out you meant trie_matcher.h does a multimatch.

Anyway, it certainly would be possible to implement this as just a custom matcher, if that's the preferred way. Bit weird since the API would be an exact duplicate of the existing API but it would have to either duplicate or wrap the existing message because custom extensions must use unique types. And mostly duplicate the code. And every time there's a custom extension point it makes the documentation painful to navigate. But if that's what it takes to get something useable I'm happy to go that way.

Absolutely right about documentation. I don't think proto docs even cut it for the matching configuration, we need examples for specific use cases. I brought this up because we had a similar discussion when I introduced this custom matcher. The problem with the prefix matcher is that it's generic for strings, it is also used to match various authentication attributes (e.g. JWT attributes, TLS fields, etc) where it's not appropriate to have this "keep-matching" logic since Ali and Alice principals should never be confused. Trie-matching only makes sense for URIs and even then extra-care needs to be done to make sure things like /foo, /fo%23, /fÖo, /foob, /foo#, /foo?, and /foo/ are not ambiguous.

Absolutely right about documentation. I don't think proto docs even cut it for the matching configuration, we need examples for specific use cases. I brought this up because we had a similar discussion when I introduced this custom matcher. The problem with the prefix matcher is that it's generic for strings, it is also used to match various authentication attributes (e.g. JWT attributes, TLS fields, etc) where it's not appropriate to have this "keep-matching" logic since Ali and Alice principals should never be confused. Trie-matching only makes sense for URIs and even then extra-care needs to be done to make sure things like /foo, /fo%23, /fÖo, /foob, /foo#, /foo?, and /foo/ are not ambiguous.

Ah, thanks, I didn't realize it was used for other things, so yeah, that makes sense of it (though this implementation did control whether it does "keep matching" with a new flag in the config so it's not like it would be forcing unwanted behavior).

Question: are you saying that looking back up in the case of a specific match being tagged with the "keep_matching" property (as in #38726) shouldn't cause prefix_map_matcher to "look up"? (If yes then I should implement a custom extension, but if no then I should just pay attention to bsurber's solution. Or if you're saying bsurber's solution is going to encounter a lot of pushback then that too means I should do it as a custom extension.)

/wait-any

for further consideration

LGTM from an API perspective (even though this doesn't actually require API approval).

/wait

/retest

/retest