Skip to content

Add an example to search for multi-byte pattern in an array #39479

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 18 commits into
base: main
Choose a base branch
from

Conversation

def00111
Copy link
Contributor

And manipulate the array directly.

Description

Motivation

There was no example for manipulating the array directly without converting the whole array to a string first.

Additional details

Related issues and pull requests

@def00111 def00111 requested a review from a team as a code owner May 11, 2025 18:31
@def00111 def00111 requested review from willdurand and removed request for a team May 11, 2025 18:31
@github-actions github-actions bot added Content:WebExt WebExtensions docs size/m [PR only] 51-500 LoC changed labels May 11, 2025
Copy link
Contributor

github-actions bot commented May 11, 2025

Preview URLs

(comment last updated: 2025-05-28 20:30:26)

@dotproto dotproto self-requested a review May 12, 2025 06:50
@dotproto
Copy link
Collaborator

After giving this some thought, I'm not sure this page is the right place for this example. I understand the desire to have a concrete example of working with multi-byte sequences, but our in-page code samples tend to be relatively short and easy to parse. I think mdn/webextensions-examples may be a better home for this. While we don't currently have a "cookbook" section, I feel like this might be a good candidate for that type of content.

Tagging @rebloor for a second opinion.

@dotproto dotproto requested a review from rebloor May 20, 2025 00:12
Copy link
Collaborator

@dotproto dotproto left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@rebloor and I discussed this offline. One of the things he pointed out is that the length of this example isn't as atypical as I originally thought. My view now is that we can probably land this with a few tweaks.

Comment on lines 321 to 336
Array.prototype.indexOfMulti = function (searchElements, fromIndex) {
let i = this.indexOf(searchElements[0], fromIndex);
if (searchElements.length === 1 || i === -1) {
// Not found or no other elements to check
return i;
}

const initial = i;
for (let j = 1; j < searchElements.length && i < this.length; j++) {
if (this[++i] !== searchElements[j]) {
return this.indexOfMulti(searchElements, initial + 1);
}
}

return i === initial + searchElements.length - 1 ? initial : -1;
};
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Modifying built-in prototypes is generally considered an anti-pattern. There's no clear benefit to this approach over using a standalone function.

Comment on lines 321 to 341
Object.defineProperty(Array.prototype, "indexOfMulti", {
value: function (searchElements, fromIndex) {
let i = this.indexOf(searchElements[0], fromIndex);
if (searchElements.length === 1 || i === -1) {
// Not found or no other elements to check
return i;
}

if (i + searchElements.length > this.length) {
return -1;
}

const initial = i;
for (let j = 1, l = searchElements.length; j < l; j++) {
if (this[++i] !== searchElements[j]) {
return this.indexOfMulti(searchElements, initial + 1);
}
}
return initial;
},
});
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Modifying built-in prototypes like this is generally considered an anti-pattern. It would be better to refactor this so indexOfMulti is a standalone function.

Suggested change
Object.defineProperty(Array.prototype, "indexOfMulti", {
value: function (searchElements, fromIndex) {
let i = this.indexOf(searchElements[0], fromIndex);
if (searchElements.length === 1 || i === -1) {
// Not found or no other elements to check
return i;
}
if (i + searchElements.length > this.length) {
return -1;
}
const initial = i;
for (let j = 1, l = searchElements.length; j < l; j++) {
if (this[++i] !== searchElements[j]) {
return this.indexOfMulti(searchElements, initial + 1);
}
}
return initial;
},
});
function indexOfMulti(arr, searchElements, fromIndex) {
let i = arr.indexOf(searchElements[0], fromIndex);
if (searchElements.length === 1 || i === -1) {
// Not found or no other elements to check
return i;
}
if (i + searchElements.length > arr.length) {
return -1;
}
const initial = i;
for (let j = 1, l = searchElements.length; j < l; j++) {
if (arr[++i] !== searchElements[j]) {
return indexOfMulti(arr, searchElements, initial + 1);
}
}
return initial;
}

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If you'd like to improve this example, I'd suggest revising this function to use the KMP algorithm as this will reduce time spent on partial matches. That change isn't required for this PR, but if you don't want to make that change we should create a tracking issue to improve this in the future.

Comment on lines 351 to 370
filter.ondata = (event) => {
const buffer = new Uint8Array(event.data);
for (let i = 0, l = buffer.length; i < l; i++) {
data.push(buffer[i]);
}
};

filter.onstop = (event) => {
for (
let i = data.indexOfMulti(bytes), m = elements.length, n = bytes.length;
i >= 0;
i = data.indexOfMulti(bytes, i + m + n)
) {
// Insert "WebExtension " at the given index
data.splice(i, 0, ...elements);
}

filter.write(new Uint8Array(data));
filter.close();
};
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Another suggestion that's out of scope for this PR: progressively apply the transform in ondata callbacks rather than buffering the entire file in memory and serially applying the transform at the end. This would improve scenarios where content can progressively render while streaming, such as with HTML responses.

// JavaScript program to search the pattern in given array
// using KMP Algorithm

function constructLps(pat, lps) {
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@@ -315,6 +315,143 @@ browser.webRequest.onBeforeRequest.addListener(
);
```

This example demonstrates, how to search for multi-byte pattern in an array:
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This example is very large now. Should it be on https://github.com/mdn/webextensions-examples?

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Content:WebExt WebExtensions docs size/m [PR only] 51-500 LoC changed
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants