rustdoc: use JS to inline target type impl docs into alias

This is an attempt to balance three problems, each of which would
be violated by a simpler implementation:

- A type alias should show all the `impl` blocks for the target
  type, and vice versa, if they're applicable. If nothing was
  done, and rustdoc continues to match them up in HIR, this
  would not work.

- Copying the target type's docs into its aliases' HTML pages
  directly causes far too much redundant HTML text to be generated
  when a crate has large numbers of methods and large numbers
  of type aliases.

- Using JavaScript exclusively for type alias impl docs would
  be a functional regression, and could make some docs very hard
  to find for non-JS readers.

- Making sure that only applicable docs are show in the
  resulting page requires a type checkers. Do not reimplement
  the type checker in JavaScript.

So, to make it work, rustdoc stashes these type-alias-inlined docs
in a JSONP "database-lite". The file is generated in `write_shared.rs`,
included in a `<script>` tag added in `print_item.rs`, and `main.js`
takes care of patching the additional docs into the DOM.

The format of `trait.impl` and `type.impl` JS files are superficially
similar. Each line, except the JSONP wrapper itself, belongs to a crate,
and they are otherwise separate (rustdoc should be idempotent). The
"meat" of the file is HTML strings, so the frontend code is very simple.
Links are relative to the doc root, though, so the frontend needs to fix
that up, and inlined docs can reuse these files.

However, there are a few differences, caused by the sophisticated
features that type aliases have. Consider this crate graph:

```text
 ---------------------------------
 | crate A: struct Foo<T>        |
 |          type Bar = Foo<i32>  |
 |          impl X for Foo<i8>   |
 |          impl Y for Foo<i32>  |
 ---------------------------------
     |
 ----------------------------------
 | crate B: type Baz = A::Foo<i8> |
 |          type Xyy = A::Foo<i8> |
 |          impl Z for Xyy        |
 ----------------------------------
```

The type.impl/A/struct.Foo.js JS file has a structure kinda like this:

```js
JSONP({
"A": [["impl Y for Foo<i32>", "Y", "A::Bar"]],
"B": [["impl X for Foo<i8>", "X", "B::Baz", "B::Xyy"], ["impl Z for Xyy", "Z", "B::Baz"]],
});
```

When the type.impl file is loaded, only the current crate's docs are
actually used. The main reason to bundle them together is that there's
enough duplication in them for DEFLATE to remove the redundancy.

The contents of a crate are a list of impl blocks, themselves
represented as lists. The first item in the sublist is the HTML block,
the second item is the name of the trait (which goes in the sidebar),
and all others are the names of type aliases that successfully match.

This way:

- There's no need to generate these files for types that have no aliases
  in the current crate. If a dependent crate makes a type alias, it'll
  take care of generating its own docs.
- There's no need to reimplement parts of the type checker in
  JavaScript. The Rust backend does the checking, and includes its
  results in the file.
- Docs defined directly on the type alias are dropped directly in the
  HTML by `render_assoc_items`, and are accessible without JavaScript.
  The JSONP file will not list impl items that are known to be part
  of the main HTML file already.

[JSONP]: https://en.wikipedia.org/wiki/JSONP

1 files changed, 173 insertions, 1 deletions

diff --git a/src/librustdoc/html/static/js/main.js b/src/librustdoc/html/static/js/main.js
index 2e9897ef82b..6cd57c8c598 100644
--- a/src/librustdoc/html/static/js/main.js
+++ b/src/librustdoc/html/static/js/main.js
@@ -549,6 +549,7 @@ function preLoadCss(cssUrl) {
         }
     }
 
+    // <https://github.com/search?q=repo%3Arust-lang%2Frust+[RUSTDOCIMPL]+trait.impl&type=code>
     window.register_implementors = imp => {
         const implementors = document.getElementById("implementors-list");
         const synthetic_implementors = document.getElementById("synthetic-implementors-list");
@@ -615,7 +616,7 @@ function preLoadCss(cssUrl) {
                 onEachLazy(code.getElementsByTagName("a"), elem => {
                     const href = elem.getAttribute("href");
 
-                    if (href && !/^(?:[a-z+]+:)?\/\//.test(href)) {
+                    if (href && !href.startsWith("#") && !/^(?:[a-z+]+:)?\/\//.test(href)) {
                         elem.setAttribute("href", window.rootPath + href);
                     }
                 });
@@ -639,6 +640,177 @@ function preLoadCss(cssUrl) {
         window.register_implementors(window.pending_implementors);
     }
 
+    // <https://github.com/search?q=repo%3Arust-lang%2Frust+[RUSTDOCIMPL]+type.impl&type=code>
+    window.register_type_impls = imp => {
+        if (!imp || !imp[window.currentCrate]) {
+            return;
+        }
+        window.pending_type_impls = null;
+        const idMap = new Map();
+
+        let implementations = document.getElementById("implementations-list");
+        let trait_implementations = document.getElementById("trait-implementations-list");
+
+        // We want to include the current type alias's impls, and no others.
+        const script = document.querySelector("script[data-self-path]");
+        const selfPath = script ? script.getAttribute("data-self-path") : null;
+
+        // These sidebar blocks need filled in, too.
+        const sidebarSection = document.querySelector(".sidebar section");
+        let methods = document.querySelector(".sidebar .block.method");
+        let associatedTypes = document.querySelector(".sidebar .block.associatedtype");
+        let associatedConstants = document.querySelector(".sidebar .block.associatedconstant");
+        let sidebarTraitList = document.querySelector(".sidebar .block.trait-implementation");
+
+        for (const impList of imp[window.currentCrate]) {
+            const types = impList.slice(2);
+            const text = impList[0];
+            const isTrait = impList[1] !== 0;
+            const traitName = impList[1];
+            if (types.indexOf(selfPath) === -1) {
+                continue;
+            }
+            let outputList = isTrait ? trait_implementations : implementations;
+            if (outputList === null) {
+                const outputListName = isTrait ? "Trait Implementations" : "Implementations";
+                const outputListId = isTrait ?
+                    "trait-implementations-list" :
+                    "implementations-list";
+                const outputListHeaderId = isTrait ? "trait-implementations" : "implementations";
+                const outputListH = document.createElement("h2");
+                outputListH.id = outputListHeaderId;
+                outputListH.innerText = outputListName;
+                outputList = document.createElement("div");
+                outputList.id = outputListId;
+                if (isTrait) {
+                    const link = document.createElement("a");
+                    link.href = `#${outputListHeaderId}`;
+                    link.innerText = "Trait Implementations";
+                    const h = document.createElement("h3");
+                    h.appendChild(link);
+                    trait_implementations = outputList;
+                    sidebarSection.appendChild(h);
+                    sidebarTraitList = document.createElement("ul");
+                    sidebarTraitList.className = "block trait-implementation";
+                    sidebarSection.appendChild(sidebarTraitList);
+                    const mainContent = document.querySelector("#main-content");
+                    mainContent.appendChild(outputListH);
+                    mainContent.appendChild(outputList);
+                } else {
+                    implementations = outputList;
+                    if (trait_implementations) {
+                        document.insertBefore(outputListH, trait_implementations);
+                        document.insertBefore(outputList, trait_implementations);
+                    } else {
+                        const mainContent = document.querySelector("#main-content");
+                        mainContent.appendChild(outputListH);
+                        mainContent.appendChild(outputList);
+                    }
+                }
+            }
+            const template = document.createElement("template");
+            template.innerHTML = text;
+
+            onEachLazy(template.content.querySelectorAll("a"), elem => {
+                const href = elem.getAttribute("href");
+
+                if (href && !href.startsWith("#") && !/^(?:[a-z+]+:)?\/\//.test(href)) {
+                    elem.setAttribute("href", window.rootPath + href);
+                }
+            });
+            onEachLazy(template.content.querySelectorAll("[id]"), el => {
+                let i = 0;
+                if (idMap.has(el.id)) {
+                    i = idMap.get(el.id);
+                } else if (document.getElementById(el.id)) {
+                    i = 1;
+                    while (document.getElementById(`${el.id}-${2 * i}`)) {
+                        i = 2 * i;
+                    }
+                    while (document.getElementById(`${el.id}-${i}`)) {
+                        i += 1;
+                    }
+                }
+                if (i !== 0) {
+                    el.id = `${el.id}-${i}`;
+                }
+                idMap.set(el.id, i + 1);
+            });
+            const templateAssocItems = template.content.querySelectorAll("section.tymethod, " +
+                "section.method, section.associatedtype, section.associatedconstant");
+            if (isTrait) {
+                const li = document.createElement("li");
+                const a = document.createElement("a");
+                a.href = `#${template.content.querySelector(".impl").id}`;
+                a.textContent = traitName;
+                li.appendChild(a);
+                sidebarTraitList.append(li);
+            } else {
+                onEachLazy(templateAssocItems, item => {
+                    let block = hasClass(item, "associatedtype") ? associatedTypes : (
+                        hasClass(item, "associatedconstant") ? associatedConstants : (
+                        methods));
+                    if (!block) {
+                        const blockTitle = hasClass(item, "associatedtype") ? "Associated Types" : (
+                            hasClass(item, "associatedconstant") ? "Associated Constants" : (
+                            "Methods"));
+                        const blockClass = hasClass(item, "associatedtype") ? "associatedtype" : (
+                            hasClass(item, "associatedconstant") ? "associatedconstant" : (
+                            "method"));
+                        const blockH = document.createElement("h3");
+                        const blockA = document.createElement("a");
+                        blockA.href = "#implementations";
+                        blockA.innerText = blockTitle;
+                        blockH.appendChild(blockA);
+                        block = document.createElement("ul");
+                        block.className = `block ${blockClass}`;
+                        const insertionReference = methods || sidebarTraitList;
+                        if (insertionReference) {
+                            const insertionReferenceH = insertionReference.previousElementSibling;
+                            sidebarSection.insertBefore(blockH, insertionReferenceH);
+                            sidebarSection.insertBefore(block, insertionReferenceH);
+                        } else {
+                            sidebarSection.appendChild(blockH);
+                            sidebarSection.appendChild(block);
+                        }
+                        if (hasClass(item, "associatedtype")) {
+                            associatedTypes = block;
+                        } else if (hasClass(item, "associatedconstant")) {
+                            associatedConstants = block;
+                        } else {
+                            methods = block;
+                        }
+                    }
+                    const li = document.createElement("li");
+                    const a = document.createElement("a");
+                    a.innerText = item.id.split("-")[0].split(".")[1];
+                    a.href = `#${item.id}`;
+                    li.appendChild(a);
+                    block.appendChild(li);
+                });
+            }
+            outputList.appendChild(template.content);
+        }
+
+        for (const list of [methods, associatedTypes, associatedConstants, sidebarTraitList]) {
+            if (!list) {
+                continue;
+            }
+            const newChildren = Array.prototype.slice.call(list.children);
+            newChildren.sort((a, b) => {
+                const aI = a.innerText;
+                const bI = b.innerText;
+                return aI < bI ? -1 :
+                    aI > bI ? 1 :
+                    0;
+            });
+            list.replaceChildren(...newChildren);
+        }
+    };
+    if (window.pending_type_impls) {
+        window.register_type_impls(window.pending_type_impls);
+    }
+
     function addSidebarCrates() {
         if (!window.ALL_CRATES) {
             return;