-
Notifications
You must be signed in to change notification settings - Fork 22.7k
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
base: main
Are you sure you want to change the base?
Conversation
And manipulate the array directly.
Preview URLs (comment last updated: 2025-05-28 20:30:26) |
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. |
There was a problem hiding this 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.
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; | ||
}; |
There was a problem hiding this comment.
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.
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; | ||
}, | ||
}); |
There was a problem hiding this comment.
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.
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; | |
} |
There was a problem hiding this comment.
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.
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(); | ||
}; |
There was a problem hiding this comment.
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) { |
There was a problem hiding this comment.
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: |
There was a problem hiding this comment.
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?
files/en-us/mozilla/add-ons/webextensions/api/webrequest/streamfilter/ondata/index.md
Outdated
Show resolved
Hide resolved
Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
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