Accept header sort is not stable leading to unstable negotiation result

[Tpt]

The following test passes:

#[test]
fn negotiate_tie() -> crate::Result<()> {
        let mut accept = Accept::new();
        accept.push(MediaTypeProposal::new(mime::HTML, Some(0.4))?);
        accept.push(MediaTypeProposal::new(mime::XML, Some(0.4))?);

        assert_eq!(accept.negotiate(&[mime::HTML, mime::XML])?, mime::XML);
        assert_eq!(accept.negotiate(&[mime::XML, mime::HTML])?, mime::HTML);
        Ok(())
}

XML (or HTML?) should be picked the two times.

[yoshuawuyts]

What to do on equal media type priority and specificity

XML (or HTML?) should be picked the two times.

Now that I've looked closer at the spec, it indeed seems that our content negotiation isn't implemented the way it should be. On what to do when two media types are equal, the spec has the following to say:

    Accept: text/plain; q=0.5, text/html,
        text/x-dvi; q=0.8, text/x-c

Verbally, this would be interpreted as "text/html and text/x-c are the equally preferred media types, but if they do not exist, then send the text/x-dvi representation, and if that does not exist, send the text/plain representation".

This sounds like our negotiate method may assign equal precedence to media types. The solution seems to not assign a constant ordering, but instead return multiple types. Meaning the example should probably behave as follows:

#[test]
fn negotiate_tie() -> crate::Result<()> {
    let mut accept = Accept::new();
    accept.push(MediaTypeProposal::new(mime::HTML, Some(0.4))?);
    accept.push(MediaTypeProposal::new(mime::XML, Some(0.4))?);

    assert_eq!(accept.negotiate(&[mime::HTML, mime::XML])?, &[mime::HTML, mime::XML]);
    assert_eq!(accept.negotiate(&[mime::XML, mime::HTML])?, &[mime::XML, mime::HTML]);
    Ok(())
}

Instead of returning a slice (ordered), we may want to return a set instead (unordered). There's a question of what the return type should be, but we can probably figure something out.

Other issues with content negotiation

I don't believe we're currently accurately negotiating media type precedence. The spec gives the following example:

Media ranges can be overridden by more specific media ranges or specific media types. If more than one media range applies to a given type, the most specific reference has precedence. For example,

Accept: text/*, text/plain, text/plain;format=flowed, */*

have the following precedence:

1. text/plain;format=flowed
2. text/plain
3. text/*
4. */*

We should author tests for this, validate the output, and fix any issues we find.

Next steps

https://github.com/http-rs/http-types/pull/390 is currently open, but while it does make the ordering more reliable, it doesn't implement it according to spec either. What we should do is:

1. Open a PR to validate the sort order to account for specificity, and fix any issues we find with that.
2. Make the result of accept::negotiate be capable of returning a Map of media types, to account for the case where multiple headers are exactly equal. This will require some design work to figure out how to make it ergonomic.