Opened 9 months ago

Last modified 8 months ago

#6688 new change

Optimise matching algorithm, add matchesAll function

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 (2)

comment:1 Changed 9 months ago by kzar

  • Description modified (diff)

comment:2 Changed 8 months ago by arthur

  • Cc arthur added
Note: See TracTickets for help on using tickets.