Radical changes of across elements pipeline.

[angezid]

The performance test results in Firefox: markRegExp method, regex /\b(?:lorem|ipsum)\b/gi

	size 100kb, marked words 1400:	size 200kb, marked words 1400:	size 500kb, marked words 3000:
existing lib	~230 ms.	~460 ms.	~2000 ms.
PR	~30 ms.	~35 ms.	~50 ms.

the same without acrossElements option

	size 100kb, marked words 1400:	size 200kb, marked words 1400:	size 500kb, marked words 3000:
existing lib	~50 ms.	~70 ms.	~120 ms.
PR	~30 ms.	~45 ms.	~60 ms.

markRanges method - generated number of ranges equal marked word number

	size 100kb, marked words 1400:	size 200kb, marked words 1400:	size 500kb, marked words 3000:
existing lib	~80 ms.	~140 ms.	~620 ms.
PR	~30 ms.	~35 ms.	~70 ms.

Also see below how to boost performance in mark() method.

The 8MB file containing 177000 text nodes, marked words 5000: in Firefox ~470 ms. in Chrome ~1300 ms. The big difference in the performance of Firefox vs. Chrome on my computer is probably related to the processor cache. For 3.2MB file containing 69200 text nodes and 2400 marked words is only 180 ms. vs 200 ms.

Before modification in the 'iterateThroughNodes' method performance was: in Firefox ~1150 ms. in Chrome ~3600 ms.

The markRegExp method, with the separateGroups option, now has the ability to mark separate groups.
With wrapAllRanges option can mark nesting and overlapping ranges and match groups.

To the callbacks each and filter in the markRegExp and mark methods i added the additional parameters - matchInfo and filterInfo objects containing match information. The additional parameters allow to use of simple code to correctly count words and/or phrases, pinpoint the start of matches, which are located across elements, abort execution, match.input property exposes internal string ...

They will not break backward-compatibility but can help to solve many problems without 'happy hacking'.

filterInfo object in the code examples:

/**
* @property {array} match - The result of RegExp exec() method
* @property {boolean} matchStart - indicate the start of match
* @property {number} groupIndex - The group index, is only available with 'separateGroups' options
* @property {object} execution - The helper object for early abort. Contains boolean 'abort' property.
* @property {number} offset - The absolute start index of a text node.
* Can be used to translate the local node indexes to the absolute ones
*/

info or matchInfo object in the code examples:

/**
* @property {array} match - The result of RegExp exec() method
* @property {boolean} matchStart - indicate the start of match
* @property {number} count - The current number of matches
* @property {number} groupIndex - The index of match group, is only available with 'separateGroups' options
* @property {boolean} groupStart - indicate the start of group, is only
* available with both 'acrossElements' and 'separateGroups' options
*/

To the done callbacks in the mark, markRegExp, and markRanges methods I added the exact total match counter, and termStats object in the mark method. The done callback in the code examples:

/**
* @param {number} totalMarks - The total number of marked elements
* @param {number} totalMatches - The exact number of total matches
* @param {object} termStats - An object containing an individual term's matches count for `mark` method
*/

Available properties of the filterInfo object on the filter callback depending on options mark - filter : function(textNode, foundTerm, totalMarks, counter, filterInfo) {} markRegExp - filter : function(textNode, foundTerm, totalMarks, filterInfo) {}

method	options	match	matchStart	groupIndex	execution	offset
mark	acrossElements	+	+	-	+	+
mark		+	-	-	+	+
markRegExp	acrossElements	+	+	-	+	+
markRegExp	acrossElements, separateGroups	+	+	+	+	-
markRegExp	separateGroups	+	+	+	+	+
markRegExp		+	-	-	+	-

Available properties of the matchInfo object on the each callback depending on options mark, markRegExp - each : function(node, matchInfo) {}

method	options	match	matchStart	groupIndex	groupStart	count
mark	acrossElements	+	+	-	-	+
mark		+	-	-	-	+
						+
markRegExp	acrossElements	+	+	-	-	+
markRegExp	acrossElements, separateGroups	+	+	+	+	+
markRegExp	separateGroups	+	+	+	-	+
markRegExp		+	-	-	-	+

The start mark elements in the code examples are only useful with 'acrossElements' option in cases such as with next/previous buttons to highlight match no matter how many mark elements it contains. The data-markjs attribute can be used for this purpose instead.

The markRegExp() method code example with acrossElements option

let matchCount = 0;

context.markRegExp(/AB\s+BC\s+EF/gi, {
    'acrossElements' : true,
    'each' : function(elem, info) {
        // for external counter 
        matchCount = info.count;
        
        // for internal use
        if(info.count ..) {}
        
        // if start of the match
        if(info.matchStart) {
            elem.className = 'start-1';
            // also possible
            // matchCount++;
        }
        
        // info.count as a match identifier
        // elem.setAttribute('data-markjs', info.count);
    },
    'done' : function(totalMarks, totalMatches) {
        console.log('Total matches = ' + totalMatches);
    }
});

The mark() method code example with acrossElements option

let matchCount = 0;

context.mark(['AB CD', 'EF'], {
    'separateWordSearch' : true,
    'acrossElements' : true,
    'each' : function(elem, info) {
       // the counter usage is the same as in markRegExp() method above
        
    },
    'done' : function(totalMarks, totalMatches, termStats) {
        console.log('Total matches = ' + totalMatches);
        
        for(var term in termStats) {
            console.log(term + ' = ' + termStats[term]);
        }
    }
});

The mark() method code example without acrossElements option

let matchCount = 0;

context.mark('AB CD EF', {
    'separateWordSearch' : true,
    'each' : function(elem, info) {
        // for external counter
        matchCount = info.count; // also possible matchCount++;
        
        // for internal use
        if(info.count ..) {}
    },
    'done' : function(totalMarks, totalMatches, termStats) {
        // Note: although without 'acrossElements' option 'totalMarks' and 'totalMatches' are equal,
        // the latter should be preferred
        console.log('Total matches = ' + totalMatches);
        
        for(var term in termStats) {
            console.log(term + ' = ' + termStats[term]);
        }
    }
});

The markRanges() method code example

let ranges = [{ start: 15, length: 50 }, {..}, {..}];

context.markRanges(ranges, {
    'done' : function(totalMarks, totalMatches) {
        console.log('Total range matches = ' + totalMatches);
    }
});

Filter matches

Filter matches in the markRegExp() method

let count = 0, reg = /\bAB\b.+?\bCD\b/gi;

// if you have access to the RegExp object with 'acrossElements' option, you can also
// set 'lastIndex' to 'Infinity' to break the execution
context.markRegExp(reg, {
    filter : function(node, matchStr, totalMarks, filterInfo) {
        // to mark only the first match
        filterInfo.execution.abort = true; return  true;
        // reg.lastIndex = Infinity; return  true; // only with 'acrossElements' option

        // filter callback requires its own match counter
        if(filterInfo.matchStart) {
            count++;
        }
        // mark the first 10 matches.
        if(count > 10) {
            filterInfo.execution.abort = true;
            // reg.lastIndex = Infinity; // only with 'acrossElements' option
            return  false;
        }

        // skip between
        if(count > 10 && count < 20) { return  false; }

        // mark between
        if(count <= 10) { return  false; }
        else if(count > 20) {
            filterInfo.execution.abort = true;
            // reg.lastIndex = Infinity; // only with 'acrossElements' option
            return  false;
        }

        return  true;
    },
});

Mark the first desired number of matches on each callback with acrossElements option. It's much limited than the filter callback.

let reg = /\b(A\s+B\s+C)\b/gi;

context.markRegExp(reg, {
    'acrossElements' : true,
    'each' : function(elem, info) {
        // to mark only the first match
        reg.lastIndex = Infinity;

        // first 10 matches
        if(info.count >= 10) {
            reg.lastIndex = Infinity;
        }
    }
});

Filter matches in the mark method with acrossElements option

let count = 0;

context.mark('AB', {
    'acrossElements' : true,
    filter : function(node, term, totalMarks, currentMarks, filterInfo) {
         // to mark only the first match
        filterInfo.execution.abort = true; return  true;

        // filter callback requires its own match counter
        if(filterInfo.matchStart) {
            count++;
        }
        // mark the first 10 matches.
        if(count > 10) { filterInfo.execution.abort = true; return  false; }

        // skip between
        if(count > 10 && count < 20) { return  false; }

        // mark between
        if(count <= 10) { return  false; }
        else if(count > 20) { filterInfo.execution.abort = true; return  false; }

        return  true;
    }
});

Filter matches in the mark method without acrossElements option

let count = 0;

context.mark('AB', {
    filter : function(node, term, totalMarks, currentMarks, filterInfo) {
        // the only difference is counter implementation
        count++;
    }
});

Mark separate groups

Important: in this implementation two branches of code process separate groups, which one, depending on the existence of d flag.

1. Primitive, base on indexOf(), only reliable with contiguous groups - unwanted group(s) can be easily filtered out.
2. Exact, but not all browsers currently supported group indices.

They both have identical logic for nested groups - if the parent group has been marked, there is no way to mark nested groups. This means you can use nested group(s) as auxiliary and don't care about filtering them.
Note: the new wrapAllRanges option allows change this behavior.

But they have different parent groups logic:

• The exact one does allow to use parent group as auxiliary - you need to filter out it in order to mark the nested group(s).
• The primitive one does not allow this - if the parent group has filtered out the nested group(s) won't be marked.

Note: Code which will use the primitive implementation will be compatible with the exact if the unwanted group(s) don't contain nested group(s) (in the exact implementation, if parent group is filtered out, the nested group(s) will be marked). To test the primitive one just add d flag.

Although, there is no strict requirement for the contiguity of capture groups. compare: in string - 'AAB xxx BCD xx BC', to mark groups AB and BC. in /(AB)\b.+?\b(BC)/g the indexOf('BC', start) find first 'BC', which is correct, but in /(AB)\b(.+?)\b(BC)(?!D)/g the indexOf('BC', start) also find first 'BC', which is wrong, because of condition '(?!D)', so group 2 is required.

Warning: related using RegExp without d flag:

• Do not add the capture group(s) to lookbehind assertion (?<=), there is no code which handle such cases.
• With acrossElements option, currently not possible to highlight the capture group(s) inside the lookahead assertion (?=).

Example to mark separate groups with acrossElements option

let groupCount = 0, group1Count = 0, group2Count = 0;

context.markRegExp(/\b(AB)\b.+?\b(CD)\b/gi, {
    'acrossElements' : true,
    'separateGroups' : true,
    'each' : function(elem, info) {
        // if start of match group
        if(info.groupStart) {
            // all group count
            groupCount++;
            
            // info.groupIndex is index of the current match group
            if(info.groupIndex === 1) {
                elem.className = 'group1-1';
                // individual group count
                group1Count++;

            } else if(info.groupIndex === 2) {
                elem.className = 'group2-1';
                group2Count++;
            }
        }
    }
});

Example to mark separate groups without acrossElements option

let groupCount = 0, group1Count = 0, group2Count = 0;

context.markRegExp(/\b(AB)\b.+?\b(CD)\b/gi, {
    'separateGroups' : true,
    'each' : function(elem, info) {
        // all group count
        groupCount++;
        
        // info.groupIndex is index of the current match group
        if(info.groupIndex === 1) {
            // individual group count
            group1Count++;

        } else if(info.groupIndex === 2) {
            group2Count++;
        }
    }
});

Filter capture groups - if filter return false, the group will be ignored

context.markRegExp(/(AB)\b(.+)\b(CD)(...)(?<gr5>EF)?\b/gi, {
    // with and without `acrossElements` option
    'acrossElements' : true,
    'separateGroups' : true,
    filter : function(node, group, totalMarks, filterInfo) {
        // by group index
        // filterInfo.groupIndex - current group index. Note: if group lays across several elements,
        // the index will be the same while the current group is wrapping
        if(filterInfo.groupIndex === 2 || filterInfo.groupIndex === 4) return  false;

        // by group content
       // if(filterInfo.group === 'AB') return  false;

        // to filter the whole match. Note: it will iterate through all groups and only then return
        if(filterInfo.match[5]) return true/false;

        // Note: named capture groups can be use only to filter whole match
        if(filterInfo.match.groups.gr5) return  true/false;

        return  true;
    },
});

Elements boundaries

With the acrossElements option, text nodes are aggregated into a single string, taking into account Html elements. If the block element divides text nodes, and the first text node doesn't end by white space, the space is added to the string to separate them.

With the additional blockElementsBoundary option, if the text node doesn't end by white space - ' \u001 ', otherwise - '\u001 ' string is added between them. It's become something 'across inline elements' option.

The blockElementsBoundary option only make sense when highlighting phrases or RegExp separate groups. It will keep the matches from crossing the boundary of block elements or only custom elements.

context.markRegExp(/\bAB\s+BC\s+CD\b/gi, {
    'acrossElements' : true,
    // option divide text nodes by ' \u001 ' instead of space
    // 'blockElementsBoundary' : {}, or with options
    'blockElementsBoundary' : {
        // custom block elements - only this custom elements will have boundaries
        'tagNames' : ['div', 'p', 'h1', 'h2'],    //optional
        // custom boundary char, default is '\u001'
        'char' : '.'        //optional
    }
});

Mark nesting and overlapping ranges and match groups

The markRanges() method with wrapAllRanges option, can mark nesting/overlapping ranges.

The markRegExp() method with RegExp having the d flag, with separateGroups and wrapAllRanges options can mark: nesting groups, capturing groups inside positive lookaround assertions. It's practically removes all restrictions.

The lookaround examples below demonstrate cases when wrapAllRanges option should be used, otherwise it won't be correctly highlighted:

• RegExp with lookaround assertions can create overlapping matches.
  e.g. regex /(?<=(gr1)\s+\w+\b).+?(gr2)/dg, string 'gr1 match1 gr1 gr2 match2 gr2'.
  The gr1 from the second match won't be wrap because the gr2 from the first match is already wrapped.

• Another case: regex /(?=\d*(1))(?=\d*(2))(?=\d*(3))/dg, matches '123, 132, 213, 231, 312, 321'.
  This is not an overlapping case, but groups are wrapped in any order. If group 1 is wrapped first, the 2 and 3 will be ignored in '231, 321' ...

• Groups overlapping case: regex /\w+(?=.*?(gr1 \w+))(?=.*?(\w+ gr2))/dg , string 'word gr1 overlap gr2' - the gr1 will be wrapped, the gr2 will be ignored.

Note: the wrapAllRanges option can cause performance degradation if the context contains a very large number of text nodes and a large number of mark elements. This is because with each wrapping, two more objects are inserted into the array, which require a lot of copying, memory allocation ...

The 8MB file containing 177000 text nodes:

tested	marked groups 2500	marked groups 29000
with wrapAllRanges option	0.7 sec.	2.9 sec.
without	0.65 sec.	0.7 sec.

The 1MB file containing 20800 text nodes:

tested	marked groups 2500	marked groups 29000
with wrapAllRanges option	120 ms.	710 ms.
without	70 ms.	310 ms.

Note: wrapAllRanges option with d flag will wrap all capturing groups regardless of nested level.
Without this option - if the group has been wrapped, all nested groups will be ignored.

With acrossElements option the code is simple:

context.markRegExp(/.../dg, {
    'acrossElements' : true,
    'separateGroups' : true,
    'wrapAllRanges' : true,
});

To mark nesting groups with the acrossElements option and with RegExp not having the d flag,
it treats the whole match as a group 0, and all child groups, in this case 'group1, group2', as nested groups:

let regex = /...\b(group1)\b.+?\b(group2)\b.../gi;

context.markRegExp(regex, {
    'acrossElements' : true,
    'separateGroups' : true,
    'wrapAllRanges' : true,
    'each' : function(elem, info) {
        // if(info.groupIndex === 0) elem.className = 'main-group';
        if(info.groupIndex > 0) {
            elem.className = 'nested-group';
        }
    }
});

To mark nesting/overlapping groups without acrossElements option and with RegExp having the d flag, is only possible through this hack:

let regex = /.../dg;
let ranges = buildRanges(context, regex);

context.markRanges(ranges, {
  'wrapAllRanges' : true,
  'each' : function(node, range) {
    // handle the additional properties
    // node.setAttribute('data-markjs', range.id);
  }
});

function buildRanges(context, regex) {
  let ranges = [];
  // it should only build ranges - an attempt to mark any group can break regex normal workflow
  context.markRegExp(regex, {
    'separateGroups' : true,
    'filter' : function(node, group, totalMatch, info) {
      if(info.matchStart) {
        // 'i = 1' - skips match[0] group
        for(let i = 1; i < info.match.length; i++)  {
          if(info.match[i]) {
            let indices = info.match.indices[i];
            // info.offset is added to translate the local group index to the absolute one
            let range = {
              start : info.offset + indices[0],
              length : indices[1] - indices[0]
            };
            // some additional properties e.g. class/color to highlight nested group,
            // match identifer to highlight all match groups with next/previous buttons ...
            // can be added here to the range object
            ranges.push(range);
          }
        }
      }
      return false;
    }
  });
  return  ranges;
}

Simple example with next/previous buttons. It's uses numbers as unique match identifiers in continuous ascending order.

let currentIndex = 0,
    matchCount,
    marks,
    // highlight 3 words in sentences in any order
    regex = /(?=[^.]*?(word1))(?=[^.]*?(word2))(?=[^.]*?(word3))/dgi;
    
context.markRegExp(regex, {
    'acrossElements' : true,
    'separateGroups' : true,
    'wrapAllRanges' : true,
    'each' : function(elem, info) {
        // info.count as a match identifier
        elem.setAttribute('data-markjs', info.count);
    },
    'done' : function(totalMarks, totalMatches) {
        marks = $('mark');
        matchCount = totalMatches;
    }
});

prevButton.click(function() {
    if(--currentIndex <= 0) currentIndex = 0;
    highlightMatchGroups();
});

nextButton.click(function() {
    if(++currentIndex > matchCount) currentIndex = matchCount;
    highlightMatchGroups();
});

function highlightMatchGroups() {
    marks.removeClass('current');
    marks.filter((i, elem) => elem.getAttribute('data-markjs') == currentIndex).addClass('current');
}

Ways to boost performance, when mark a (especially)large array of strings or string with the `separateWordSearch` option.

There are two options which do so :

• combinePatterns : combines given numbers of strings into RegExp patterns, e.g. an array of 50 strings, combinePatterns : 10 - will create 5 combine patterns, so instead of 50 passes there will be only 5 passes. The number bigger than the array length will create a single combined pattern. Note : with diacritics option, a single pattern can be monstrous and more slowly, it's better to create 5-7 patterns. Also, this option will change the behavior of marking strings, e.g. ['word1 word2 word3', 'word2'], without this option, 'word2' will be marked, with - don't.

• cacheTextNodes : collecting context text nodes information on every pass is expensive. Caching this information will improve performance with a large array.   With acrossElements option, it requires the wrapAllRanges option.   Note : this option does not change behavior as the combinePatterns option does.

In Firefox marking an array of 500 words on a 1 MB page, without diacritics and ~7600 highlighted words :

• with combinePatterns: 1001 - 0.15 second. (single pattern)
• with cacheTextNodes option - 4.1 sec.
• with cacheTextNodes, acrossElements and wrapAllRanges options - 0.6 sec.
• without above options - 27 sec.

let array = [ 'str1', 'str2', .. ];

context.mark(array, {
  'combinePatterns' : number  // or true (default number is 10)
});

context.mark(array, {
  'cacheTextNodes' : true,
  // 'acrossElements' : true,
  // 'wrapAllRanges' : true,
});

Other

Simple example with next/previous buttons. Unusable with markRegExp() method having wrapAllRanges option.

var currentIndex = 0,
    marks = $('mark'),
    startElements = marks.filter((i, elem) => $(elem).hasClass('start-1'));
    //startElements = marks.filter((i, elem) => $(elem).data('markjs') === 'start-1');

prevButton.on('click', function() {
    if(--currentIndex <= 0) currentIndex = 0;

    var elem = startElements.eq(currentIndex);
    if(elem.length) highlightMatch(elem[0]);
});

nextButton.on('click', function() {
    if(++currentIndex >= startElements.length) currentIndex = startElements.length - 1;

    var elem = startElements.eq(currentIndex);
    if(elem.length) highlightMatch(elem[0]);
});

// it adds class 'current' to all mark elements of the found match if it located across elements
// or to the first mark element
function highlightMatch(elem) {
    var found = false;
    marks.each(function(i, el) {
        if( !found) {
            if(el === elem[0]) found = true;

        // start of the next 'start element' means the end of the current match
        } else if($(this).hasClass('start-1')) return  false;
        //} else if($(this).data('markjs') === 'start-1') return  false;

        if(found) $(this).addClass('current');
    });
}

[dabrahams]

There is a backward-compatibility issue I noticed when I dropped this change into my project: it now insists on g or y flags for the regex in a regex search.

[dabrahams]

I think this patch needs some documentation for matchNodeIndex (and anything else added). I don't know what it means and all the examples merely test it against zero, so it's hard to guess.

[angezid]

There is a backward-compatibility issue I noticed when I dropped this change into my project: it now insists on g or y flags for the regex

The first idea was to silently recompile RegExp with the g flag, but how to control this new RegExp? Without g or y flags there will be an infinite loop. In the existing library an infinite loop is control by complex manipulations with input string and nodes indexes.

[dabrahams]

Can't you just recompile it with g if and only if the object has neither .global == true nor .sticky == true?

[angezid]

In my previous versions there was code which do this:

if (this.opt.acrossElements && !regexp.global && !regexp.sticky) {
  let flags = 'g' + (regexp.flags ? regexp.flags : '');
  regexp = new RegExp(regexp.source, flags);
}

but what if user forget to set g flag and later try regexp.lastIndex = Number.MAX_VALUE;?

[dabrahams]

@julmot what do you think about this PR? Does it need more work? Is it heading in the wrong direction completely?

[angezid]

@julmot, I implement what I want, even more than. But how to test wrapMatchGroupsD and separateGroupsD methods? With PhantomJS it's not possible to test even RegExp pattern parser? Currently, I left the manual test. Also, some doubts about correct naming, comments ...

[dabrahams]

@angezid looking at @julmot's GitHub activity I am not holding out much hope for future development in this repo. I'm thinking of using your fork.

[angezid]

I also have doubts this PR will revive this repo.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[drzraf]

I'm trying to anticipate mark.js future and that led me to wonder about maintainer's vision (@julmot) regarding this (remarkable) PR (and the overall project).

[drzraf]

To the callbacks each and filter in the markRegExp and mark methods i added the additional parameters - matchInfo and filterInfo objects containing match information.

This is great. When using markRegExp with a regexp containing named groups, these would be available inside matchInfo.groups. Very useful.

[rbhalla]

@angezid, I was looking at contributing the following enhancement to the existing repo: https://github.com/julmot/mark.js/issues/473

Then I found this incredible PR. Would you open to contributions to this branch? It seems well updated, and could easily form the basis of a fork.

Not sure what you think of the issue, but it feels like acrossElements: true and separateWordSearch: false is a useful combination to support.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[drzraf]

Just wanted to mention that I had a project (a web-extension) which couldn't rely upon mark.js because of the low performance, but using this branch saved my day and made it just work like a breeze. Big thanks to @angezid !

[stevemckenzie]

Great job on this PR! You fixed a bug that I was experiencing when using the exactly accuracy 😀

[stevemckenzie]

@angezid you should reach out to @julmot 🙃 - https://github.com/julmot/mark.js/issues/463#issuecomment-1048890093

[angezid]

He is probably very busy. Version 9.0.0 still not released https://github.com/julmot/mark.js/issues/457.

[stevemckenzie]

@angezid I reached out to him via email. He is definitely too busy to maintain this so maybe you can help to get version 9 out the door? He said he was waiting for you to respond.

[peace2000]

If this is going through changes, would it be possible to add support for texts under shadow root https://github.com/julmot/mark.js/issues/458 at the same time? Thanks!

[chris-allen]

:+1:

[stevemckenzie]

@angezid did you connect with @julmot yet?

[julkue]

@stevemckenzie No, I've also sent a reminder comment here.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.