Opened on 05/22/2018 at 10:52:34 AM
Closed on 03/16/2019 at 04:00:12 PM
Last modified on 03/18/2019 at 10:13:13 AM
#6688 closed change (duplicate)
Optimise matching algorithm, add matchesAll function
| Reported by: | kzar | Assignee: | |
|---|---|---|---|
| Priority: | P2 | Milestone: | |
| Module: | Core | Keywords: | |
| Cc: | sebastian, mjethani, sergz, arthur | Blocked By: | |
| Blocking: | Platform: | Unknown / Cross platform | |
| Ready: | yes | Confidential: | no |
| Tester: | Unknown | Verified working: | no |
| Review URL(s): | |||
Description (last modified by mjethani)
Background
So far Matcher in lib/matcher.js provides matchesAny which given a URL and some other details for a request returns the first filter (if any) that matches.
It would be nice to add a matchesAll function as well, which returns all filters that match. For example that would allow us to find all $csp filters which apply to a document and inject all the given Content Security Policy headers. So far we just find the first $csp filter that matches and discard the others.
Unfortunately at the moment finding all filters that match would we use a be quite slow, and since this is a hotspot we have to be careful not to slow things down. Sebastian has suggested that using a binary search tree (BST) might help the performance and has provided some example code.
What to change
- Take Sebastian's example code and put it into lib/matcher.js. Test the performance of matchesAny before and after this change to see if it has made things slower or faster.
- Implement matchesAll as described above.
- Add unit tests.
Notes
- See the discussion in #6465.
Resolution
We made a number of improvements to the matching algorithm that went into ABP 3.5 for Chrome/Firefox (see #6994, #7003, #7052, #7089, #7208, #7209, #7232, #7245, #7250, and #7265); we also added a function to return all matching filters (see #7179).
