Opened 2 years ago

Last modified 17 months ago

#6688 closed change

Optimise matching algorithm, add matchesAll function — at Initial Version

Reported by: kzar Assignee: kzar
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

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, injecting all the Content Security Policy headers, instead of just the header specified in the first filter that we find.

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 (attached).

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.

Change History (0)

Note: See TracTickets for help on using tickets.