Avoid recursion in base::MatchPattern().
The recursion could lead to exponential run time, which in the previous
implementation was avoided only by restricting the maximum recursion depth.
The idea behind the new implementation is based on
https://research.swtch.com/glob, specifically the fact that once a subpattern
(the sequence of characters between two runs of wildcards) has been matched, the
algorithm never needs to backtrack to before it anymore. The algorithm therefore
searches for each of the subpatterns sequentially in the target string.
One notable difference in the syntax of base::MatchPattern() to "standard" globs
is that the '?' character matches 0 or 1 characters here, whereas the standard
glob '?' matches exactly 1 character. This means that consecutive runs of
wildcards define a maximum distance between exact subpatterns to match (which is
infinite if the run contains at least one '*').
Bug: 52839
Change-Id: I2401ca6e2719ea31b4afbe6e65b6b0d76f7f3da9
Reviewed-on: https://chromium-review.googlesource.com/866503
Commit-Queue: Bernhard Bauer <bauerb@chromium.org>
Reviewed-by: Daniel Cheng <dcheng@chromium.org>
Cr-Commit-Position: refs/heads/master@{#530855}
CrOS-Libchrome-Original-Commit: de432102b73600e23ef0a93ac378db19cb13cab4
3 files changed