Opened 2 years ago

Last modified 17 months ago

#6688 closed change

Optimise matching algorithm, add matchesAll function — at Version 1

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 (last modified by kzar)


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.


  • See the discussion in #6465.

Change History (1)

comment:1 Changed 2 years ago by kzar

  • Description modified (diff)
Note: See TracTickets for help on using tickets.