| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
The descriptions are, on almost all crates[^1], the majority
of the size of the search index, even though they aren't really
used for searching. This makes it relatively easy to separate
them into their own files.
This commit also bumps us to ES8. Out of the browsers we support,
all of them support async functions according to caniuse.
https://caniuse.com/async-functions
[^1]:
<https://microsoft.github.io/windows-docs-rs/>, a crate with
44MiB of pure names and no descriptions for them, is an outlier
and should not be counted.
|
|
|
|
r=GuillaumeGomez
rustdoc-search: depth limit `T<U>` -> `U` unboxing
Profiler output:
https://notriddle.com/rustdoc-html-demo-9/search-unbox-limit/ (the only significant change is that one of the `rust` tests went from 378416ms to 16ms).
This is a performance enhancement aimed at a problem I found while using type-driven search on the Rust compiler. It is caused by [`Interner`], a trait with 41 associated types, many of which recurse back to `Self` again.
This caused search.js to struggle. It eventually terminates, after about 10 minutes of turning my PC into a space header, but it's doing `41!` unifications and that's too slow.
[`Interner`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.Interner.html
|
|
This is implemented, in addition to the ML-style one,
because Rust does it. If we don't, we'll never hear the end of it.
This commit also refactors some duplicate parts of the parser
into a dedicated function.
|
|
Initialize them before the search index is loaded.
|
|
It's going to be a no-op on the empty list anyway
(we have plenty of test cases that return nothing)
so why send extra code?
|
|
Option::map, for example, looks like this:
option<t>, (t -> u) -> option<u>
This syntax searches all of the HOFs in Rust: traits Fn, FnOnce,
and FnMut, and bare fn primitives.
|
|
Profiler output:
https://notriddle.com/rustdoc-html-demo-9/search-unbox-limit/
This is a performance enhancement aimed at a problem I found while
using type-driven search on the Rust compiler. It is caused by
[`Interner`], a trait with 41 associated types, many of which
recurse back to `Self` again.
This caused search.js to struggle. It eventually terminates,
after about 10 minutes of turning my PC into a space header, but it's
doing `41!` unifications and that's too slow.
[`Interner`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.Interner.html
|
|
|
|
rustdoc: Correctly handle long crate names on mobile
Fixes https://github.com/rust-lang/rust/issues/120471.
It now renders like this:
r? `@notriddle`
|
|
|
|
|
|
rustdoc: hide modals when resizing the sidebar
Follow-up for
https://github.com/rust-lang/rust/pull/119477#discussion_r1439085011
CC `@lukas-code`
|
|
This takes advantage of more reuse opportunities.
Along with the empty object commit, they
bringing memory usage down about 20% over the original.
|
|
Map is implemented as a pointer to a mutable object.
Rustdoc never mutates function signatures after constructing them,
but the JS engine doesn't know that.
To save a bunch of memory, use a single immutable map
for every decoded type object with no bindings or generics.
|
|
Follow-up for
https://github.com/rust-lang/rust/pull/119477#discussion_r1439085011
|
|
rustdoc: search for tuples and unit by type with `()`
This feature extends rustdoc to support the syntax that most users will naturally attempt to use to search for tuples. Part of https://github.com/rust-lang/rust/issues/60485
Function signature searches already support tuples and unit. The explicit name `primitive:tuple` and `primitive:unit` can be used to match a tuple or unit, while `()` will match either one. It also follows the direction set by the actual language for parens as a group, so `(u8,)` will only match a tuple, while `(u8)` will match a plain, unwrapped byte—thanks to loose search semantics, it will also match the tuple.
## Preview
* [`option<t>, option<u> -> (t, u)`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=option%3Ct%3E%2C option%3Cu%3E -%3E (t%2C u)>)
* [`[t] -> (t,)`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=[t] -%3E (t%2C)>)
* [`(ipaddr,) -> socketaddr`](<https://notriddle.com/rustdoc-html-demo-5/tuple-unit/std/index.html?search=(ipaddr%2C) -%3E socketaddr>)
## Motivation
When type-based search was first landed, it was directly [described as incomplete][a comment].
[a comment]: https://github.com/rust-lang/rust/pull/23289#issuecomment-79437386
Filling out the missing functionality is going to mean adding support for more of Rust's [type expression] syntax, such as tuples (in this PR), references, raw pointers, function pointers, and closures.
[type expression]: https://doc.rust-lang.org/reference/types.html#type-expressions
There does seem to be demand for this sort of thing, such as [this Discord message](https://discord.com/channels/442252698964721669/443150878111694848/1042145740065099796) expressing regret at rustdoc not supporting tuples in search queries.
## Reference description (from the Rustdoc book)
<table>
<thead>
<tr>
<th>Shorthand</th>
<th>Explicit names</th>
</tr>
</thead>
<tbody>
<tr><td colspan="2">Before this PR</td></tr>
<tr>
<td><code>[]</code></td>
<td><code>primitive:slice</code> and/or <code>primitive:array</code></td>
</tr>
<tr>
<td><code>[T]</code></td>
<td><code>primitive:slice<T></code> and/or <code>primitive:array<T></code></td>
</tr>
<tr>
<td><code>!</code></td>
<td><code>primitive:never</code></td>
</tr>
<tr><td colspan="2">After this PR</td></tr>
<tr>
<td><code>()</code></td>
<td><code>primitive:unit</code> and/or <code>primitive:tuple</code></td>
</tr>
<tr>
<td><code>(T)</code></td>
<td><code>T</code></td>
</tr>
<tr>
<td><code>(T,)</code></td>
<td><code>primitive:tuple<T></code></td>
</tr>
</tbody>
</table>
A single type expression wrapped in parens is the same as that type expression, since parens act as the grouping operator. If they're empty, though, they will match both `unit` and `tuple`, and if there's more than one type (or a trailing or leading comma) it is the same as `primitive:tuple<...>`.
However, since items can be left out of the query, `(T)` will still return results for types that match tuples, even though it also matches the type on its own. That is, `(u32)` matches `(u32,)` for the exact same reason that it also matches `Result<u32, Error>`.
## Future direction
The [type expression grammar](https://doc.rust-lang.org/reference/types.html#type-expressions) from the Reference is given below:
<pre><code>Syntax
Type :
TypeNoBounds
| <a href="https://doc.rust-lang.org/reference/types/impl-trait.html">ImplTraitType</a>
| <a href="https://doc.rust-lang.org/reference/types/trait-object.html">TraitObjectType</a>
<br>
TypeNoBounds :
<a href="https://doc.rust-lang.org/reference/types.html#parenthesized-types">ParenthesizedType</a>
| <a href="https://doc.rust-lang.org/reference/types/impl-trait.html">ImplTraitTypeOneBound</a>
| <a href="https://doc.rust-lang.org/reference/types/trait-object.html">TraitObjectTypeOneBound</a>
| <a href="https://doc.rust-lang.org/reference/paths.html#paths-in-types">TypePath</a>
| <a href="https://doc.rust-lang.org/reference/types/tuple.html#tuple-types">TupleType</a>
| <a href="https://doc.rust-lang.org/reference/types/never.html">NeverType</a>
| <a href="https://doc.rust-lang.org/reference/types/pointer.html#raw-pointers-const-and-mut">RawPointerType</a>
| <a href="https://doc.rust-lang.org/reference/types/pointer.html#shared-references-">ReferenceType</a>
| <a href="https://doc.rust-lang.org/reference/types/array.html">ArrayType</a>
| <a href="https://doc.rust-lang.org/reference/types/slice.html">SliceType</a>
| <a href="https://doc.rust-lang.org/reference/types/inferred.html">InferredType</a>
| <a href="https://doc.rust-lang.org/reference/paths.html#qualified-paths">QualifiedPathInType</a>
| <a href="https://doc.rust-lang.org/reference/types/function-pointer.html">BareFunctionType</a>
| <a href="https://doc.rust-lang.org/reference/macros.html#macro-invocation">MacroInvocation</a>
</code></pre>
ImplTraitType and TraitObjectType (and ImplTraitTypeOneBound and TraitObjectTypeOneBound) are not yet implemented. They would mostly desugar to `trait:`, similarly to how `!` desugars to `primitive:never`.
ParenthesizedType and TuplePath are added in this PR.
TypePath is already implemented (except const generics, which is not planned, and function-like trait syntax, which is planned as part of closure support).
NeverType is already implemented.
RawPointerType and ReferenceType require parsing and fixes to the search index to store this information, but otherwise their behavior seems simple enough. Just like tuples and slices, `&T` would be equivalent to `primitive:reference<T>`, `&mut T` would be equivalent to `primitive:reference<keyword:mut, T>`, `*T` would be equivalent to `primitive:pointer<T>`, `*mut T` would be equivalent to `primitive:pointer<keyword:mut, T>`, and `*const T` would be equivalent to `primitive:pointer<keyword:const, T>`. Lifetime generics support is not planned, because lifetime subtyping seems too complicated.
ArrayType is subsumed by SliceType right now. Implementing const generics is not planned, because it seems like it would require a lot of implementation complexity for not much gain.
InferredType isn't really covered right now. Its semantics in a search context are not obvious.
QualifiedPathInType is not implemented, and it is not planned. I would need a use case to justify it, and act as a guide for what the exact semantics should be.
BareFunctionType is not implemented. Along with function-like trait syntax, which is formally considered a TypePath, it's the biggest missing feature to be able to do structured searches over generic APIs like `Option`.
MacroInvocation is not parsed (macro names are, but they don't mean the same thing here at all). Those are gone by the time Rustdoc sees the source code.
|
|
rustdoc-search: tighter encoding for f index
Depends on https://github.com/rust-lang/rust/pull/119457
Two optimizations for the function signature search:
* Instead of using JSON arrays, like `[1,20]`, it uses VLQ
hex with no commas, like `[aAd]`.
* This also adds backrefs: if you have more than one function
with exactly the same signature, it'll not only store it once,
it'll *decode* it once, and store in the typeIdMap only once.
Based partially on discussions on zulip:
https://rust-lang.zulipchat.com/#narrow/stream/266220-t-rustdoc/topic/search.20index.20size
Performance
-----------
https://notriddle.com/rustdoc-html-demo-8/compression-perf-v2/index.html
### memory/time profiler output (for more details, consult the above link)
<table>
<thead><tr><th>benchmark<th>before<th>after</tr></thead>
<tbody>
<tr><th>arti<td>
```
user: 002.789 s
sys: 000.390 s
wall: 002.096 s
child_RSS_high: 440796 KiB
group_mem_high: 414924 KiB
```
</td><td>
```
user: 002.295 s
sys: 000.278 s
wall: 001.738 s
child_RSS_high: 314588 KiB
group_mem_high: 285220 KiB
```
</td></tr><tr><th>cortex-m<td>
```
user: 000.127 s
sys: 000.030 s
wall: 000.134 s
child_RSS_high: 60264 KiB
group_mem_high: 23824 KiB
```
</td><td>
```
user: 000.136 s
sys: 000.038 s
wall: 000.137 s
child_RSS_high: 59204 KiB
group_mem_high: 22712 KiB
```
</td></tr><tr><th>sqlx<td>
```
user: 000.887 s
sys: 000.118 s
wall: 000.592 s
child_RSS_high: 190408 KiB
group_mem_high: 157804 KiB
```
</td><td>
```
user: 000.798 s
sys: 000.101 s
wall: 000.525 s
child_RSS_high: 159292 KiB
group_mem_high: 126292 KiB
```
</td></tr><tr><th>stm32f4<td>
```
user: 013.884 s
sys: 005.399 s
wall: 013.149 s
child_RSS_high: 1942244 KiB
group_mem_high: 1954916 KiB
```
</td><td>
```
user: 006.128 s
sys: 003.297 s
wall: 007.994 s
child_RSS_high: 1038108 KiB
group_mem_high: 1023900 KiB
```
</td></tr><tr><th>ripgrep<td>
```
user: 000.441 s
sys: 000.063 s
wall: 000.264 s
child_RSS_high: 109180 KiB
group_mem_high: 74272 KiB
```
</td><td>
```
user: 000.408 s
sys: 000.044 s
wall: 000.238 s
child_RSS_high: 101488 KiB
group_mem_high: 66000 KiB
```
</td></tr></tbody></table>
Size change
-----------
standard library without gzip:
```console
$ du -bs search-index-old.js search-index-new.js
4976370 search-index-old.js
4404391 search-index-new.js
```
((4976370-4404391)/4404391)*100% = 12.9%
with gzip:
```console
$ du -hs search-index-old.js.gz search-index-new.js.gz
520K search-index-old.js.gz
504K search-index-new.js.gz
$ du -bs search-index-old.js.gz search-index-new.js.gz
522092 search-index-old.js.gz
507654 search-index-new.js.gz
```
((522092-507654)/507654)*100% = 2.8%
Benchmarks are similarly shrunk.
Without gzip:
```console
$ du -hs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.js
10555067 tmp/arti/toolchain_old/doc/search-index.js
8921236 tmp/arti/toolchain_new/doc/search-index.js
77018 tmp/cortex-m/toolchain_old/doc/search-index.js
66676 tmp/cortex-m/toolchain_new/doc/search-index.js
2876330 tmp/sqlx/toolchain_old/doc/search-index.js
2436812 tmp/sqlx/toolchain_new/doc/search-index.js
63632890 tmp/stm32f4/toolchain_old/doc/search-index.js
52337438 tmp/stm32f4/toolchain_new/doc/search-index.js
631150 tmp/ripgrep/toolchain_old/doc/search-index.js
541646 tmp/ripgrep/toolchain_new/doc/search-index.js
```
With gzip:
```console
$ du -bs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.js.gz
1618852 tmp/arti/toolchain_old/doc/search-index.js.gz
1582007 tmp/arti/toolchain_new/doc/search-index.js.gz
16109 tmp/cortex-m/toolchain_old/doc/search-index.js.gz
15831 tmp/cortex-m/toolchain_new/doc/search-index.js.gz
422257 tmp/sqlx/toolchain_old/doc/search-index.js.gz
411507 tmp/sqlx/toolchain_new/doc/search-index.js.gz
4454761 tmp/stm32f4/toolchain_old/doc/search-index.js.gz
4334924 tmp/stm32f4/toolchain_new/doc/search-index.js.gz
98312 tmp/ripgrep/toolchain_old/doc/search-index.js.gz
96864 tmp/ripgrep/toolchain_new/doc/search-index.js.gz
$ du -hs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.j
s.gz
1.6M tmp/arti/toolchain_old/doc/search-index.js.gz
1.6M tmp/arti/toolchain_new/doc/search-index.js.gz
24K tmp/cortex-m/toolchain_old/doc/search-index.js.gz
24K tmp/cortex-m/toolchain_new/doc/search-index.js.gz
424K tmp/sqlx/toolchain_old/doc/search-index.js.gz
412K tmp/sqlx/toolchain_new/doc/search-index.js.gz
4.3M tmp/stm32f4/toolchain_old/doc/search-index.js.gz
4.2M tmp/stm32f4/toolchain_new/doc/search-index.js.gz
108K tmp/ripgrep/toolchain_old/doc/search-index.js.gz
104K tmp/ripgrep/toolchain_new/doc/search-index.js.gz
```
|
|
|
|
r=GuillaumeGomez
rustdoc: clean up source sidebar hide button
This is a redesign of the feature, with parts pulled from https://github.com/rust-lang/rust/pull/119049 but with a button that looks more like a button and matches the one used on other sidebar pages.
Preview:
* http://notriddle.com/rustdoc-html-demo-8/source-sidebar-resize/src/std/lib.rs.html
* http://notriddle.com/rustdoc-html-demo-8/source-sidebar-resize/std/index.html
| | Before | After |
|--|--|--|
| Closed |  | 
| Open |  | 
| Mobile Closed |  | 
| Mobile Open |  | 
|
|
Two optimizations for the function signature search:
* Instead of using JSON arrays, like `[1,20]`, it uses VLQ
hex with no commas, like `[aAd]`.
* This also adds backrefs: if you have more than one function
with exactly the same signature, it'll not only store it once,
it'll *decode* it once, and store in the typeIdMap only once.
Size change
-----------
standard library
```console
$ du -bs search-index-old.js search-index-new.js
4976370 search-index-old.js
4404391 search-index-new.js
```
((4976370-4404391)/4404391)*100% = 12.9%
Benchmarks are similarly shrunk:
```console
$ du -hs tmp/{arti,cortex-m,sqlx,stm32f4,ripgrep}/toolchain_{old,new}/doc/search-index.js
10555067 tmp/arti/toolchain_old/doc/search-index.js
8921236 tmp/arti/toolchain_new/doc/search-index.js
77018 tmp/cortex-m/toolchain_old/doc/search-index.js
66676 tmp/cortex-m/toolchain_new/doc/search-index.js
2876330 tmp/sqlx/toolchain_old/doc/search-index.js
2436812 tmp/sqlx/toolchain_new/doc/search-index.js
63632890 tmp/stm32f4/toolchain_old/doc/search-index.js
52337438 tmp/stm32f4/toolchain_new/doc/search-index.js
631150 tmp/ripgrep/toolchain_old/doc/search-index.js
541646 tmp/ripgrep/toolchain_new/doc/search-index.js
```
|
|
|
|
r=GuillaumeGomez
rustdoc-search: count path edits with separate edit limit
Avoids strange-looking results like this one, where the path component seems to be ignored:
Since the two are counted separately elsewhere, they should get their own limits, too. The biggest problem with combining them is that paths are loosely checked by not requiring every component to match, which means that if they are short and matched loosely, they can easily find "drunk typist" matches that make no sense, like this old result:
std::collections::btree_map::itermut matching slice::itermut
maxEditDistance = ("slice::itermut".length) / 3 = 14 / 3 = 4
editDistance("std", "slice") = 4
editDistance("itermut", "itermut") = 0
4 + 0 <= 4 PASS
Of course, `slice::itermut` should not match stuff from btreemap. `slice` should not match `std`.
The new result counts them separately:
maxPathEditDistance = "slice".length / 3 = 5 / 3 = 1
maxEditDistance = "itermut".length / 3 = 7 / 3 = 2
editDistance("std", "slice") = 4
4 <= 1 FAIL
Effectively, this makes path queries less "typo-resistant". It's not zero, but it means `vec` won't match the `v1` prelude.
This commit also adds substring matching to paths. It's stricter than the substring matching in the main part, but loose enough that what I expect to match does.
Queries without parent paths are unchanged.
|
|
Since the two are counted separately elsewhere, they should get
their own limits, too. The biggest problem with combining them
is that paths are loosely checked by not requiring every component
to match, which means that if they are short and matched loosely,
they can easily find "drunk typist" matches that make no sense,
like this old result:
std::collections::btree_map::itermut matching slice::itermut
maxEditDistance = ("slice::itermut".length) / 3 = 14 / 3 = 4
editDistance("std", "slice") = 4
editDistance("itermut", "itermut") = 0
4 + 0 <= 4 PASS
Of course, `slice::itermut` should not match stuff from btreemap.
`slice` should not match `std`.
The new result counts them separately:
maxPathEditDistance = "slice".length / 3 = 5 / 3 = 1
maxEditDistance = "itermut".length / 3 = 7 / 3 = 2
editDistance("std", "slice") = 4
4 <= 1 FAIL
Effectively, this makes path queries less "typo-resistant".
It's not zero, but it means `vec` won't match the `v1` prelude.
Queries without parent paths are unchanged.
|
|
Fixes #119219
|
|
|
|
|
|
|
|
This is a redesign of the feature, with parts pulled from
https://github.com/rust-lang/rust/pull/119049
but with a button that looks more like a button and matches the
one used on other sidebar pages.
|
|
rustdoc-search: remove parallel searchWords array
This might have made sense if the algorithm could use `searchWords` to skip having to look at `searchIndex`, but since it always does a substring check on both the stock word and the normalizedName, it doesn't seem to help performance anyway.
Profile: http://notriddle.com/rustdoc-html-demo-8/searchwords/index.html
|
|
This might have made sense if the algorithm could use `searchWords`
to skip having to look at `searchIndex`, but since it always
does a substring check on both the stock word and the normalizedName,
it doesn't seem to help performance anyway.
|
|
Simplify `src-script.js` code
Instead of keeping this value in the global scope and still use it in the function in case it wasn't used outside, let's just use it inside the function.
r? ``@notriddle``
|
|
|
|
rustdoc: allow resizing the sidebar / hiding the top bar
Fixes #97306
Preview: http://notriddle.com/rustdoc-html-demo-4/sidebar-resize/std/index.html
## Summary
This feature adds:
1. A checkbox to the Settings popover to hide the persistent navigation bar (the sidebar on large viewports and the top bar on small ones).
2. On large viewports, it adds a resize handle to the persistent sidebar. Resizing it into nothing is equivalent to turning off the persistent navigation bar checkbox in Settings.
3. If the navigation bar is hidden, a toolbar button to the left of the search appears. Clicking it brings the navigation bar back.
## Motivation
While "mobile mode" is definitely a good default, it's not the only reason people have wanted to hide the sidebar:
* Some people use tiling window managers, and don't like rustdoc's current breakpoints. Changing the breakpoints might help with that, but there's no perfect solution, because there's a gap between "huge screen" and "smartphone" where reasonable people can disagree about whether it makes sense for the sidebar to be on-screen. https://github.com/rust-lang/rust/issues/97306
* Some people ask for ways to reduce on-screen clutter because it makes it easier to focus. There's not a media query for that (and if there was, privacy-conscious users would turn it off). https://github.com/rust-lang/rust/issues/59829
This feature is designed to avoid these problems. Resizing the sidebar especially helps, because it provides a way to hide the sidebar without adding a new top-level button (which would add clutter), and it provides a way to make rustdoc play nicer in complex, custom screen layouts.
## Guide and Reference-level explanation
On a desktop or laptop with a mouse, resize the sidebar by dragging its right edge.
On any browser, including mobile phones, the sticky top bar or side bar can be hidden from the Settings area (the button with the cog wheel, next to the search bar). When it's hidden, a convenient button will appear on the search bar's left.
## Drawbacks
This adds more JavaScript code to the render blocking area.
## Rationale and alternatives
The most obvious way to allow people to hide the sidebar would have been to let them "manually enter mobile mode." The upside is that it's a feature we already have. The downside is that it's actually really hard to come up with a terse description. Is it:
* A Setting that forces desktop viewers to always have the mobile-style top bar? If so, how do we label it? Should it be visible on mobile, and, if so, does it just not do anything?
* A persistent hide/show sidebar button, present on desktop, just like on mobile? That's clutter that I'd like to avoid.
## Prior art
* The new file browser in GitHub uses a similar divider with a mouse-over indicator
* mdBook and macOS Finder both allow you to resize the sidebar to nothing as a gesture to hide it
* https://www.nngroup.com/articles/drag-drop/
## Future possibilities
https://rust-lang.zulipchat.com/#narrow/stream/266220-rustdoc/topic/Table.20of.20contents proposes a new, second sidebar (a table of contents). How should it fit in with this feature? Should it be resizeable? Hideable? Can it be accessed on mobile?
|
|
|
|
|
|
The hash changes are based on some tests with `arti` and various
specific queries, aimed at reducing the false positive rate.
Sorting the query elements so that generics always come first is
instead aimed at reducing the number of Map operations on mgens,
assuming if the bloom filter does find a false positive, it'll
be able to reject the row without having to track a mapping.
- https://hur.st/bloomfilter/?n=3&p=&m=96&k=6
Different functions have different amounts of inputs, and
unification isn't very slow anyway, so figuring out a single
ideal number of hash functions is nasty, but 6 keeps things
low even up to 10 inputs.
- https://web.archive.org/web/20210927123933/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.2442&rep=rep1&type=pdf
This is the `h1` and `h2`, both derived from `h0`.
|
|
This commit adds ranking and quick filtering to type-based search,
improving performance and having it order results based on their
type signatures.
Motivation
----------
If I write a query like `str -> String`, a lot of functions come up.
That's to be expected, but `String::from_str` should come up on top, and
it doesn't right now. This is because the sorting algorithm is based
on the functions name, and doesn't consider the type signature at all.
`slice::join` even comes up above it!
To fix this, the sorting should take into account the function's
signature, and the closer match should come up on top.
Guide-level description
-----------------------
When searching by type signature, types with a "closer" match will
show up above types that match less precisely.
Reference-level explanation
---------------------------
Functions signature search works in three major phases:
* A compact "fingerprint," based on the [bloom filter] technique, is used to
check for matches and to estimate the distance. It sometimes has false
positive matches, but it also operates on 128 bit contiguous memory and
requires no backtracking, so it performs a lot better than real
unification.
The fingerprint represents the set of items in the type signature, but it
does not represent nesting, and it ignores when the same item appears more
than once.
The result is rejected if any query bits are absent in the function, or
if the distance is higher than the current maximum and 200
results have already been found.
* The second step performs unification. This is where nesting and true bag
semantics are taken into account, and it has no false positives. It uses a
recursive, backtracking algorithm.
The result is rejected if any query elements are absent in the function.
[bloom filter]: https://en.wikipedia.org/wiki/Bloom_filter
Drawbacks
---------
This makes the code bigger.
More than that, this design is a subtle trade-off. It makes the cases I've
tested against measurably faster, but it's not clear how well this extends
to other crates with potentially more functions and fewer types.
The more complex things get, the more important it is to gather a good set
of data to test with (this is arguably more important than the actual
benchmarking ifrastructure right now).
Rationale and alternatives
--------------------------
Throwing a bloom filter in front makes it faster.
More than that, it tries to take a tactic where the system can not only check
for potential matches, but also gets an accurate distance function without
needing to do unification. That way it can skip unification even on items
that have the needed elems, as long as they have more items than the
currently found maximum.
If I didn't want to be able to cheaply do set operations on the fingerprint,
a [cuckoo filter] is supposed to have better performance.
But the nice bit-banging set intersection doesn't work AFAIK.
I also looked into [minhashing], but since it's actually an unbiased
estimate of the similarity coefficient, I'm not sure how it could be used
to skip unification (I wouldn't know if the estimate was too low or
too high).
This function actually uses the number of distinct items as its
"distance function."
This should give the same results that it would have gotten from a Jaccard
Distance $1-\frac{|F\cap{}Q|}{|F\cup{}Q|}$, while being cheaper to compute.
This is because:
* The function $F$ must be a superset of the query $Q$, so their union is
just $F$ and the intersection is $Q$ and it can be reduced to
$1-\frac{|Q|}{|F|}.
* There are no magic thresholds. These values are only being used to
compare against each other while sorting (and, if 200 results are found,
to compare with the maximum match). This means we only care if one value
is bigger than the other, not what it's actual value is, and since $Q$ is
the same for everything, it can be safely left out, reducing the formula
to $1-\frac{1}{|F|} = \frac{|F|}{|F|}-\frac{1}{|F|} = |F|-1$. And, since
the values are only being compared with each other, $|F|$ is fine.
Prior art
---------
This is significantly different from how Hoogle does it.
It doesn't account for order, and it has no special account for nesting,
though `Box<t>` is still two items, while `t` is only one.
This should give the same results that it would have gotten from a Jaccard
Distance $1-\frac{|A\cap{}B|}{|A\cup{}B|}$, while being cheaper to compute.
Unresolved questions
--------------------
`[]` and `()`, the slice/array and tuple/union operators, are ignored while
building the signature for the query. This is because they match more than
one thing, making them ambiguous. Unfortunately, this also makes them
a performance cliff. Is this likely to be a problem?
Right now, the system just stashes the type distance into the
same field that levenshtein distance normally goes in. This means exact
query matches show up on top (for example, if you have a function like
`fn nothing(a: Nothing, b: i32)`, then searching for `nothing` will show it
on top even if there's another function with `fn bar(x: Nothing)` that's
technically a closer match in type signature.
Future possibilities
--------------------
It should be possible to adopt more sorting criteria to act as a tie breaker,
which could be determined during unification.
[cuckoo filter]: https://en.wikipedia.org/wiki/Cuckoo_filter
[minhashing]: https://en.wikipedia.org/wiki/MinHash
|
|
This function dates back to 9a45c9d7c6928743f9e7a7161bf564a65bfc0577 and
seems to have been made obsolete when `addIntoResult` grew the ability to
check the levenshtein distance matching with commit
ba824ec52beb0e49b64e86837c1402a0c2d0c971.
|
|
Clean up variables in `search.js`
While reviewing https://github.com/rust-lang/rust/pull/118402, I saw a few small clean ups that were needed, mostly about variables creation.
r? ```@notriddle```
|
|
|
|
The `c === "="` was redundant when `isSeparatorCharacter` already
checks that.
The function `isStopCharacter` and `isEndCharacter` functions
did exactly the same thing and have synonymous names.
There doesn't seem much point in having both.
|
|
|
|
Before: http://notriddle.com/rustdoc-html-demo-6/tor-before/tor_config/
After: http://notriddle.com/rustdoc-html-demo-6/tor-after/tor_config/
Profile: http://notriddle.com/rustdoc-html-demo-6/tor-profile/
As a bit of background information: in type-based queries, a type
name that does not exist gets treated as a generic type variable.
This causes a counterintuitive behavior in the `tor_config` crate,
which has a trait with an associated type variable called `T`.
This isn't a searchable concrete type, but its name still gets stored
in the typeNameIdMap, as a convenient way to intern its name.
|
|
This feature was added in edec5807ac5ba90cbc0c61a5ec7b80f29e1eea33
to support JavaScript-based toggles that were later replaced with
HTML `<details>`.
|
|
This way, most of the parsing code doesn't need to be designed to handle
it, since they should always be treated exactly the same anyhow.
|
|
This is already covered by the normal unexpected char path.
|
|
This restriction made sense back when spaces separated function
parameters, but now that they separate path components, there's
no real ambiguity any more.
Additionally, the Rust language allows it.
|
|
Fix Rustdoc search docs link
This link has been outdated since #112725 moved the search docs to their own page
|
