Opened 2 years ago

Closed 19 months ago

Last modified 19 months ago

#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)


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.


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

Change History (4)

comment:1 Changed 2 years ago by kzar

  • Description modified (diff)

comment:2 Changed 2 years ago by arthur

  • Cc arthur added

comment:3 Changed 19 months ago by mjethani

  • Description modified (diff)
  • Resolution set to duplicate
  • Status changed from new to closed

comment:4 Changed 19 months ago by kzar

  • Owner kzar deleted
Note: See TracTickets for help on using tickets.