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)


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

Attachments (0)

Change History (4)

comment:1 Changed on 05/22/2018 at 10:56:28 AM by kzar

  • Description modified (diff)

comment:2 Changed on 06/11/2018 at 10:23:23 AM by arthur

  • Cc arthur added

comment:3 Changed on 03/16/2019 at 04:00:12 PM by mjethani

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

comment:4 Changed on 03/18/2019 at 10:13:13 AM by kzar

  • Owner kzar deleted

Add Comment

Modify Ticket

Change Properties
as closed .
The resolution will be deleted. Next status will be 'reopened'.
to The owner will be changed from (none).
Note: See TracTickets for help on using tickets.