For simplicity I won't implement this in bug 1654862, but it would be useful, because currently the suggestions controller respects the maxHistoricalSearchSuggestions pref, and that's fine if the user opted out (set to 0), but otherwise we may only show 2 suggestions, even if we have no remote suggestions at all.
This likely requires to change the logic in the suggestions controller to fetch more local suggestions and then adjust the list depending on how many remote suggestions there are. Though we should also not break the normal suggestions usage.

This rewrites the muxer. I'll explain why.

The obvious way to fix this bug is to modify UrlbarProviderSearchSuggestions so
it adds maxHistoricalSearchSuggestions form history results first, followed by
as many remote suggestions as there are, followed by any remaining form history
results. And in fact that's what this patch does. But the muxer isn't capable of
handling that very well, with regard to deuping SERPs and form history.

The muxer does a first pass through all results, and it builds a set of form
history suggestions. Then, as it's adding URL results in the second pass, it
excludes SERPs whose search terms are in the set. The problem is that the set
can include search terms from form history results that do not end up in the
final list of results. And that's because UrlbarProviderSearchSuggestions now
returns many form history results -- as many as context.maxResults + 1 so that
there are enough of them to fill the view when appropriate.

This is a problem with the muxer in general. It collects a bunch of state from
all results in its first pass, even though not all of those results may end up
in the final list. Worst case, we may end up excluding results we should not
exclude. The fundamental problem is that the muxer doesn't know which results
will end up being included until it starts including results.

The key thing about this rewrite is that the muxer builds up state as it goes
along filling its buckets. If a result is excluded, then it doesn't contribute
to the state used to determine whether subsequent results should be included.
There are a couple of exceptions though where it still does build state using
all results. (1) It still determines the heuristic this way, but that's OK since
there's only one heuristic. (2) It still builds strippedUrlToTopPrefixAndTitle
this way. I couldn't think of a nice way around that, because AFAICT there's no
guarantee that UnifiedComplete will put the higher-ranking URL result before the
lower one. If the lower one comes first, we'd end up including it too since
strippedUrlToTopPrefixAndTitle would not contain the higher-ranking one at
that point.

There's one drawback of building up the state in this new way. It's the flip
side of solving the problem above. If a result depends in some way on a
subsequent result, then the state at that first result won't be accurate and the
muxer will make a bad decision about that result. There's an example of this in
test_search_suggestions.js, near the bottom of the formHistory task. In that
test, matchBuckets is defined so that general results (e.g., history) appear
before search suggestions. That means the SERP in history can't be deduped in
favor of the form history result that appears later, so both results appear. I
think that's better than the alternative of possibly deduping too aggressively.

One important thing to note is that this patch isn't restricted to search
mode. It will always include more form history results to fill out the final
list if some other higher-ranked result group doesn't fill it out
sooner. Currently matchBuckets is heuristic,1,extension,5,suggestion,4,general,Infinity,suggestion,Infinity,general,Infinity.
Since general,Infinity comes before suggestion,Infinity, this means that if
there aren't enough general results to fill out the list, then suggestions will
fill it out as much as possible. Within suggestions, remote suggestions will
fill it out first and then form history, since that's the order that
UrlbarProviderSearchSuggestions adds them in after the initial
maxHistoricalSearchSuggestions form history results. I think that's what we
want regardless of search mode.

Finally, this patch also breaks up sort into more, smaller methods. The patch
started out as a much larger version that also redesigned matchBuckets. That's
the main reason I split it up, but it's nice by itself I think. (I'd like to
come back to that matchBuckets redesign, which could now build on top of
this. The original patch is in D87830.)

https://treeherder.mozilla.org/#/jobs?repo=try&revision=fa9199cd825ba05c4351801509276b16bdc404c1

https://hg.mozilla.org/mozilla-central/rev/c4a5371dcac9

I verified this issue using 82.0a1 (2020-09-14) on macOS 10.13 and Windows 10 x64.
Adrian could you help me with Ubuntu verification?

Verified as fixed using latest Nightly 83.0a1 under Ubuntu 18.04 64-bit.