Highlight declaration differences in overloaded symbol groups

[QuietMisdreavus]

Bug/issue #, if applicable: rdar://116409531

Summary

This PR introduces a new field to declaration tokens in Render JSON: highlight. This field indicates that the token is distinct among a set of overloads and should be indicated with a highlight or other style. It also performs a difference comparison of overloaded symbols' declarations so that the fields are populated for Swift-DocC-Render.

When combined with the related Swift-DocC-Render PR (linked below), the rendered page appears like this:

Because the differencing works directly on the declaration fragments received from the symbol graph, this PR also takes some care to break up .text tokens to prevent false-positive differences and create a cleaner output. For example, the below overloads correctly only highlight the <S> in the second overload, even though it originally contains a text token of >(. Also visible in this example is some proactive whitespace-trimming from highlighted sections; there is a unique text token containing a single space before the where clause in the second overload, but it's not highlighted to reduce clutter:

Performance

This PR uses the standard library's CollectionDifference API to generate the Longest Common Subsequence of the overload declarations. The diff algorithm can have a heavy time complexity, especially when run repeatedly like here. The standard library's implementation is well-optimized, but there is still a necessary performance hit to calculate the diffs. This following is a benchmark run on a large framework with many overloaded symbols:

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ Metric                                   │ Change          │ main                 │ current              │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Duration for 'bundle-registration'       │ +1.913%¹,²      │ 10.351 sec           │ 10.549 sec           │
│ Duration for 'convert-total-time'        │ +3.857%³,⁴      │ 15.477 sec           │ 16.074 sec           │
│ Duration for 'documentation-processing'  │ +7.959%⁵,⁶      │ 5.003 sec            │ 5.401 sec            │
│ Duration for 'finalize-navigation-index' │ no change⁷      │ 0.046 sec            │ 0.046 sec            │
│ Peak memory footprint                    │ no change⁸      │ 811 MB               │ 835.4 MB             │
│ Data subdirectory size                   │ +2.028%⁹        │ 127.4 MB             │ 130 MB               │
│ Index subdirectory size                  │ -0.02829%¹⁰     │ 1.1 MB               │ 1.1 MB               │
│ Total DocC archive size                  │ +1.092%¹¹       │ 236.6 MB             │ 239.2 MB             │
│ Topic Anchor Checksum                    │ no change       │ 53074b40863239b7a00d │ 53074b40863239b7a00d │
│ Topic Graph Checksum                     │ change          │ 5bdfe323b77baec3d5cd │ f4af046ddef9eab49ba8 │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────┘

Dependencies

https://github.com/apple/swift-docc-render/pull/847 is required to render the tokens with a highlight.

Testing

Steps:

1. Build the Swift-DocC-Render PR and link the resulting dist directory into the DOCC_HTML_DIR environment variable.
2. `swift run docc preview --enable-experimental-overloaded-symbol-presentation 'Tests/SwiftDocCTests/Test Bundles/OverloadedSymbols.docc'
3. Navigate to the OverloadedEnum/firstTestMemberName(_:) overload group and expand the declaration list.
4. Ensure that the declarations correctly highlight the parameter type in each overloaded declaration.

Checklist

Make sure you check off the following items. If they cannot be completed, provide a reason.

• [x] Added tests
• [x] Ran the ./bin/test script and it succeeded
• [ n/a ] Updated documentation if necessary

[QuietMisdreavus]

@swift-ci Please test

[mportiz08]

I'm also concerned about the possibility of other renderers that consume DocC Render JSON that might not anticipate the concept of recursive tokens.

FWIW, other renderers would already have to deal with recursion for basic existing things like formatting inline text (you can have any combination of bold/emphasis/codeVoice or nested lists, etc) with our existing tree-like concept of block/inline content which carries over from the markdown. I wouldn't actually anticipate that there would be any other renderer that would handle experimental features under feature flags like this in any case though.

[d-ronnqvist]

I'm also concerned about the possibility of other renderers that consume DocC Render JSON that might not anticipate the concept of recursive tokens.

FWIW, other renderers would already have to deal with recursion for basic existing things like formatting inline text (you can have any combination of bold/emphasis/codeVoice or nested lists, etc) with our existing tree-like concept of block/inline content which carries over from the markdown. I wouldn't actually anticipate that there would be any other renderer that would handle experimental features under feature flags like this in any case though.

That is different because "Text" in the RenderNode spec isn't recursive, it's a simple object with "text" and "type" properties (very similar to "DeclarationToken"):

"Text": {
    "type": "object",
    "required": [
        "type",
        "text"
    ],
    "properties": {
        "type": {
            "type": "string",
            "enum": ["text"]
        },
        "text": {
            "type": "string"
        }
    }
},

Just like "DeclarationToken", I would be opposed to making "Text" in the RenderNode spec recursive.

Instead, the way that we have modeled emphasis, strong, codeVoice, etc. in the RenderNode spec is by defining many dedicated types—some of which are recursive and some of which are not—and wrapping them all in a "RenderInlineContent" type:

"RenderInlineContent": {
    "oneOf": [
        {
            "$ref": "#/components/schemas/Text"
        },
        {
            "$ref": "#/components/schemas/Emphasis"
        },
        {
            "$ref": "#/components/schemas/Strong"
        },
        {
            "$ref": "#/components/schemas/CodeVoice"
        },
        ...
        }
    ]
}

We could introduce this type of structure for declarations as well—like what @Vera suggested with enum RenderToken {} (which I feel would be better named "DeclarationInlineContent" for consistency and to distance it from the "token" concept)—but to use that structure we would need to make breaking changes to the various "tokens" properties in the RenderNode spec:

 "tokens": {
    "type": "array",
    "items": {
-       "$ref": "#/components/schemas/DeclarationToken"
+       "$ref": "#/components/schemas/DeclarationInlineContent"
    }
}

As far as I know, we don't have a process yet for how to handle breaking change to the RenderNode spec.

If the Swift code won't mirror the Render Node spec, I don't feel like this structure makes sense for the Swift code.

[mportiz08]

I've created a draft renderer PR for both proposed Render JSON schemas that have been discussed in this PR:

• new token kind: https://github.com/apple/swift-docc-render/pull/841
• new flag for all tokens: https://github.com/apple/swift-docc-render/pull/847

Please let me know which approach ends up being decided for this PR, and I'll close the corresponding renderer PR that isn't needed and remove draft status from the other.

[QuietMisdreavus]

@swift-ci Please test

[QuietMisdreavus]

@swift-ci Please test

[QuietMisdreavus]

@d-ronnqvist @patshaughnessy I've updated the PR to remove the recursive token type and refactor the code to clean it up a bit. I've also added some tests, so i've removed the draft status from the PR.

[QuietMisdreavus]

@swift-ci Please test

[QuietMisdreavus]

@swift-ci Please test

[QuietMisdreavus]

@swift-ci Please test

[QuietMisdreavus]

@swift-ci Please test