HTML search: represent indices using JavaScript Map instead of object literals #13097

jayaddison · 2024-11-02T02:21:50Z

Feature or Bugfix

Bugfix

Purpose

Prevent queries for the JavaScript class prototype reference propery name from causing errors in the HTML search JavaScript code provided in the basic theme.

Detail

~~Ensure that the user input query term is found as a named property of the relevant index objects before accessing them, using Object.hasOwnProperty.~~
Represent the HTML search indices as JavaScript Map instances instead of Object literals.

Relates

Resolves HTML search: bug with JS-prototype-property query #13096.
~~May resolve # 13098 (conditional on inclusion of JSON.parse reviver / Object.freeze logic)~~

Edit: update description to reflect JavaScript Map-based approach.

…fore accessing them

[skip ci]

wlach

I can see how this would be a problem but I'm a little unclear on how the solution actually works? See comments

wlach · 2024-11-05T16:14:33Z

sphinx/themes/basic/static/searchtools.js

@@ -514,8 +514,8 @@ const Search = {
    searchTerms.forEach((word) => {
      const files = [];
      const arr = [
-        { files: terms[word], score: Scorer.term },
-        { files: titleTerms[word], score: Scorer.title },
+        { files: terms.hasOwnProperty(word) ? terms[word] : [], score: Scorer.term },


I'm actually a little confused by how this might work, as it doesn't appear that JavaScript supports setting the __proto__ property in an object. Am I missing something? Should we be using a map to store these terms instead?

When parsing JSON, an object key named "__proto__" is accepted, and converted to the JavaScript object key ["__proto__"] -- distinct from the __proto__ property (a reference to a class prototype).

During read-access, introducing hasOwnProperty allows us to filter out the latter, so that we don't mistakenly retrieve the prototype class reference from terms.

I'm not certain whether the below example will help to clarify, but I find experimentation helpful to understand some of the behaviours:

> x = JSON.parse('{}') {} > y = JSON.parse('{"__proto__": "testing"}') { ['__proto__']: 'testing' } > '__proto__' in x true > x.hasOwnProperty('__proto__') false > '__proto__' in y true > y.hasOwnProperty('__proto__') true

I forgot to respond to your Map question: that is certainly possible, although I feel that doing so might add some runtime overhead (since we'd need to load the native JS object contents from the index into respective Map objects).

As I understand it, Map objects are also more difficult to make immutable in JavaScript than Object and Array instances. Freezing a Map object doesn't prevent its private contents from being updated:

> x = {'foo': 'bar'} { foo: 'bar' } > Object.freeze(x) { foo: 'bar' } > x['foo'] = 'baz' 'baz' > x['foo'] 'bar' > y = new Map([['foo', 'bar']]) Map(1) { 'foo' => 'bar' } > Object.freeze(y) Map(1) { 'foo' => 'bar' } > y.set('foo', 'baz') Map(1) { 'foo' => 'baz' } > y.get('foo') 'baz'

So another factor is that, to the extent that I'd like to see the search index contents become immutable at load-time in future (#13098), I'd prefer not to migrate to the Map type unless there is a compelling reason to (maybe avoiding prototype pollution is that reason -- but I don't think we're exposed to that currently).

Ok got it, this makes sense to me re: the property. TIL!

I'm a little bit less sure about whether the index should be immutable, but happy to defer that discussion to another day.

Actually, one extra piece of optional feedback: since this is kind of counter-intuitive, you might want to add a comment on this line explaining what you're doing.

Yep, OK - I'll try to add some phrasing to explain this succinctly. Thanks for the code review!

tests/js/roots/ecmascript/index.rst

The JS prototype property should _not_ be found in unrelated documents

wlach · 2024-11-11T13:53:00Z

sphinx/themes/basic/static/searchtools.js

@@ -514,8 +514,8 @@ const Search = {
    searchTerms.forEach((word) => {
      const files = [];
      const arr = [
-        { files: terms[word], score: Scorer.term },
-        { files: titleTerms[word], score: Scorer.title },
+        { files: terms.hasOwnProperty(word) ? terms[word] : [], score: Scorer.term },


Ok got it, this makes sense to me re: the property. TIL!

I'm a little bit less sure about whether the index should be immutable, but happy to defer that discussion to another day.

sphinx/themes/basic/static/searchtools.js

AA-Turner · 2024-11-13T22:03:42Z

Would this work as an alternative?

    // in Search.setIndex()
    const frozen_index = JSON.parse(index, (key, value) => {
      typeof value === "object" && value !== null
        ? Object.freeze(value)
        : value;
    });

If we change Search.setIndex() to taking a JSON string, it seems we could use the 'reviver' function to freeze arrays and objects?

A

jayaddison · 2024-11-14T01:08:49Z

@AA-Turner although I'd recommend some performance testing, that could be useul for #13098, yep.

jayaddison · 2024-11-14T11:53:40Z

In fact, no, my mistake: JSON.parse may in fact be necessary to solve this robustly. The test appears only to be passing due to the fact that __proto__ is found in the objects part of the searchindex.js file. The terms entry for __proto__ is not being handled correctly.

… index contents Co-authored-by: Adam Turner <[email protected]>

jayaddison · 2024-11-14T12:04:31Z

I've pushed the change to use JSON.parse and reviver -- a note of caution, though: when I was testing that against a JSON-ized version of the Python documentation searchindex.js file yesterday, I was encountering ~200ms duration within the setIndex function in my browser.

wlach · 2024-11-14T12:13:56Z

Personally, I'd be inclined to merge the previous version of this and address that (if at all) in a followup. Trying to "freeze" the index here feels like scope creep to me and it would be nice to get this fix in.

jayaddison · 2024-11-14T12:19:35Z

That's reasonable, yep, and I've no strong opinions on whether we include or omit the Object.freeze aspect. However, without 462c859, I don't believe this branch would genuinely fix the reported bug.

The `JSON.dumps` call escapes single-quotes within strings; all JSON strings are enclosed by double-quotes

jayaddison · 2024-11-14T12:28:08Z

Without the reviver function, I recall the setIndex + JSON.parse performance overhead being in the order of ~60ms on my local machine. I'll confirm those stats in some more detail within the next day or so. I get the feeling that some of this will be coupled to the browser+implementation (Firefox) details, so I may try to compare to Chrom[e|ium] also.

wlach · 2024-11-14T12:33:02Z

In fact, no, my mistake: JSON.parse may in fact be necessary to solve this robustly. The test appears only to be passing due to the fact that __proto__ is found in the objects part of the searchindex.js file. The terms entry for __proto__ is not being handled correctly.

Sorry, I missed this part. Do you know why this is the case? The solution looked correct to me?

jayaddison · 2024-11-14T12:42:52Z

In fact, no, my mistake: JSON.parse may in fact be necessary to solve this robustly. The test appears only to be passing due to the fact that __proto__ is found in the objects part of the searchindex.js file. The terms entry for __proto__ is not being handled correctly.

Sorry, I missed this part. Do you know why this is the case? The solution looked correct to me?

The test case in 0fff170 was inaccurate -- it demonstrated that an object Object.__proto__ could be found based on a user query for __proto__.

However, there was still a bug: a document text term __proto__ -- represented by the "terms":{"__proto__":0 fragment of the searchindex.js -- was not searchable as intended.

AA-Turner · 2024-11-14T16:11:23Z

sphinx/themes/basic/static/searchtools.js

+    const reviver = (k, v) => (typeof v === "object" && v !== null) ? Object.freeze(v) : v;
+    Search._index = JSON.parse(index, reviver);


I think @wlach is right that immutability is orthoganal here. I think 'simply' using JSON.parse rather than an object literal would solve the __proto__ case. Would we then need to keep the hasOwnProperty checks?

An alternative would be to use a reviver function that constructs Map objects/serialise the index with Map literals, and use .get(), but that may also be expensive.

Suggested change

const reviver = (k, v) => (typeof v === "object" && v !== null) ? Object.freeze(v) : v;

Search._index = JSON.parse(index, reviver);

Search._index = JSON.parse(index);

I think @wlach is right that immutability is orthoganal here. I think 'simply' using JSON.parse rather than an object literal would solve the __proto__ case.

Ok, yep - I can revert 443fd21 to remove the use of Object.freeze / the reviver function.

Would we then need to keep the hasOwnProperty checks?

We should keep those, I think. Without them, queries for __proto__ may continue to inadvertently retrieve object prototypes instead of getting an undefined result.

An alternative would be to use a reviver function that constructs Map objects/serialise the index with Map literals, and use .get(), but that may also be expensive.

What do you think about constructing those Map objects directly in the searchindex.js file format, instead of using JSON.parse and a reviver?

What do you think about constructing those Map objects directly in the searchindex.js file format, instead of using JSON.parse and a reviver?

IMO this is definitely worth a shot, I suspect it'll be quite fast.

I'm giving it a try - it doesn't seem too tricky; the Python serialization of the search index becomes a little more complex. One challenge that I have yet to work out is how the Python unit tests should parse/load the resulting index (ref:

sphinx/tests/test_search.py

Line 70 in 15b46dc

return json.loads(searchindex[16:-1])

).

…e search index contents" This reverts commit 443fd21.

[skip ci]

Relates-to commit d4bba1e. [skip ci]

jayaddison · 2024-11-16T11:47:32Z

tests/test_search.py

+    indices = ast.literal_eval(
+        searchindex[16:-1]
+        .replace('new Map', '')
+        .replace('null', 'None')
+        .replace('false', 'False')
+    )


This is fragile and inelegant; it's a compromise to avoid introducing the complexity of a Python-implemented JavaScript parser dependency given the use of new Map(...) within searchindex.js files.

[skip ci]

jayaddison · 2024-11-16T17:45:57Z

Without the reviver function, I recall the setIndex + JSON.parse performance overhead being in the order of ~60ms on my local machine. I'll confirm those stats in some more detail within the next day or so. I get the feeling that some of this will be coupled to the browser+implementation (Firefox) details, so I may try to compare to Chrom[e|ium] also.

I haven't gotten around to this comprehensive performance testing yet, but want to share some notes:

Initial results

Initially the native Map approach (up to fae81a0) seems similar in runtime performance to the existing/baseline approach (object literals), based on my testing using Sphinx's self-built documentation.

The page-load searchindex-evaluation time on my machine for a query for phin (~700 results) is ~30ms in Firefox, compared to a ~20ms baseline. Those are both relatively small compared to a ~0.5s duration for display/rendering of the search results, but arguably that is a pessimal query (a more-precise match would reduce the display duration).

There is a small amount of index size bloat -- not so much from the new Map( and ) text overhead, but more from the additional Array literals (e.g. square brackets) used to format their entries instead of object literals. This is approximately 5% overhead on the test dataset; 541857 bytes compared to 516691 baseline.

Observations so far

There seem to be multiple factors to balance: Python complexity, JavaScript complexity, code safety (both datastructure immutability, and also prototype access), runtime performance and index filesize.

I'm not sure how much to explore and how to present my thoughts/findings. Generally my feeling is that the Map approach here (again, up to fae81a0) seems good on most criteria except for Python complexity (particularly the unit tests, but also the application serialization code is more complex than it was) and immutability (that it does not address, in my opinion). The tc39 Records-and-Tuples proposal, I think, would be near-optimal on all factors -- but we could be years away from that reaching widespread adoption.

jayaddison added 3 commits November 2, 2024 02:09

search: check that query terms exist as properties in term indices be…

47f6547

…fore accessing them

Tests: fixtures: add document title for ECMAScript testroot

713d6bb

Tests: add JavaScript test coverage for prototype-property-name query

0fff170

jayaddison added html search javascript Pull requests that update Javascript code labels Nov 2, 2024

Add CHANGES.rst entry

64d6e09

[skip ci]

jayaddison mentioned this pull request Nov 3, 2024

HTML search: sanitise 'searchindex.js' contents #13099

Closed

jayaddison requested a review from wlach November 4, 2024 21:02

wlach reviewed Nov 5, 2024

View reviewed changes

Tests: add negative-test case

9bab17c

The JS prototype property should _not_ be found in unrelated documents

wlach approved these changes Nov 11, 2024

View reviewed changes

jayaddison commented Nov 11, 2024

View reviewed changes

sphinx/themes/basic/static/searchtools.js Outdated Show resolved Hide resolved

jayaddison and others added 4 commits November 11, 2024 17:27

search: add explanatory comment for document title/text term lookup

9b1edac

search: retain undefined result instead of [] for non-matching terms

52b9de3

search: add explanatory comment regarding hasOwnProperty usage

bcb02fe

Merge branch 'master' into issue-13096/html-search-handle-proto-query

7267990

jayaddison added the DO NOT MERGE label Nov 14, 2024

jayaddison and others added 3 commits November 14, 2024 12:01

HTML search: encapsulate the search index content within a JSON string

462c859

HTML search: use the JSON.parse reviver argument to freeze search…

443fd21

… index contents Co-authored-by: Adam Turner <[email protected]>

Merge branch 'master' into issue-13096/html-search-handle-proto-query

295d230

jayaddison added the type:performance label Nov 14, 2024

Tests: fixup: accommodate adjusted setIndex prefix/suffix lengths

3498755

HTML search: replace repr with simple embedded single-quotes

f38ce20

The `JSON.dumps` call escapes single-quotes within strings; all JSON strings are enclosed by double-quotes

AA-Turner reviewed Nov 14, 2024

View reviewed changes

jayaddison added 12 commits November 15, 2024 19:00

Revert "HTML search: use the JSON.parse reviver argument to freez…

0d9a26c

…e search index contents" This reverts commit 443fd21.

WIP: HTML search: use JS Maps in serialized index

d4bba1e

[skip ci]

HTML search: fixup for object search

d9dee52

Relates-to commit d4bba1e. [skip ci]

HTML search: ensure array-format index entries are sorted

d056a8a

HTML search: refactor-out redundant code

15a7dfa

HTML search: rectify variable names

6e670ea

HTML search: compress index representation

f2848ed

HTML search: enclose index names in double-quotes

798cb48

Tests: HTML search: use ast.literal_eval to parse index contents

af61293

Tests: HTML search: update test expectation

2bcf7a6

HTML search: cleanup: remove redundant assert statement

381c26f

HTML search: typing/lint fixups for ruff and mypy

ac281dc

jayaddison commented Nov 16, 2024

View reviewed changes

Edit CHANGES.rst entry

fae81a0

[skip ci]

jayaddison changed the title ~~HTML search: check for query terms presence in index term properties~~ HTML search: represent indices using JavaScript Map instead of object literals Nov 16, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

HTML search: represent indices using JavaScript Map instead of object literals #13097

HTML search: represent indices using JavaScript Map instead of object literals #13097

jayaddison commented Nov 2, 2024 •

edited

Loading

wlach left a comment

wlach Nov 5, 2024

jayaddison Nov 5, 2024

jayaddison Nov 6, 2024

wlach Nov 11, 2024

wlach Nov 11, 2024

jayaddison Nov 11, 2024

wlach Nov 11, 2024

AA-Turner commented Nov 13, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

wlach commented Nov 14, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

wlach commented Nov 14, 2024

jayaddison commented Nov 14, 2024

AA-Turner Nov 14, 2024

jayaddison Nov 15, 2024

wlach Nov 15, 2024

jayaddison Nov 15, 2024

jayaddison Nov 16, 2024

jayaddison commented Nov 16, 2024

		const reviver = (k, v) => (typeof v === "object" && v !== null) ? Object.freeze(v) : v;
		Search._index = JSON.parse(index, reviver);

	const reviver = (k, v) => (typeof v === "object" && v !== null) ? Object.freeze(v) : v;
	Search._index = JSON.parse(index, reviver);
	Search._index = JSON.parse(index);

HTML search: represent indices using JavaScript Map instead of object literals #13097

Are you sure you want to change the base?

HTML search: represent indices using JavaScript Map instead of object literals #13097

Conversation

jayaddison commented Nov 2, 2024 • edited Loading

Feature or Bugfix

Purpose

Detail

Relates

wlach left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

AA-Turner commented Nov 13, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

wlach commented Nov 14, 2024

jayaddison commented Nov 14, 2024

jayaddison commented Nov 14, 2024

wlach commented Nov 14, 2024

jayaddison commented Nov 14, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jayaddison commented Nov 16, 2024

Initial results

Observations so far

jayaddison commented Nov 2, 2024 •

edited

Loading