Bug 167154 – Implement URLSearchParams's sort()

• Component: DOM
• Status: RESOLVED FIXED

[Anne van Kesteren]

See https://w3c-test.org/url/urlsearchparams-sort.html for a test, https://github.com/whatwg/url/issues/26 for discussion, and https://url.spec.whatwg.org/#dom-urlsearchparams-sort for the standard.

[Alex Christensen]

Created attachment 299208 [details]
Patch

[Alex Christensen]

By the way, Anne, all the existing tests pass if I use std::sort instead of std::stable_sort.  I would suggest adding a longer test like this to the web platform tests to verify the stability of sorting algorithms:

  {
    "input": "z=z&a=a&z=y&a=b&z=x&a=c&z=w&a=d&z=v&a=e&z=u&a=f&z=t&a=g",
    "output": [["a", "a"], ["a", "b"], ["a", "c"], ["a", "d"], ["a", "e"], ["a", "f"], ["a", "g"], ["z", "z"], ["z", "y"], ["z", "x"], ["z", "w"], ["z", "v"], ["z", "u"], ["z", "t"]]
  },

[Sam Weinig]

Comment on attachment 299208 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=299208&action=review

> Source/WebCore/html/URLSearchParams.cpp:64
> +    std::stable_sort(m_pairs.begin(), m_pairs.end(), [] (auto a, auto b) {

Can we add some type of modifier to these autos as I am not sure if this is causing copying / a.k.a. ref-churn for each lambda call.

[Anne van Kesteren]

Alex: https://github.com/w3c/web-platform-tests/pull/4563 (feel free to create them yourself next time).

Also, I'm curious, since I did try to test for stable sort, when does the difference happen? Or does it vary on implementation strategy?

[Alex Christensen]

(In reply to comment #4)
> Alex: https://github.com/w3c/web-platform-tests/pull/4563 (feel free to
> create them yourself next time).
I'm going to get better at this
> 
> Also, I'm curious, since I did try to test for stable sort, when does the
> difference happen? Or does it vary on implementation strategy?
I think it's stl-implementation dependent.  I think our stl implementation is from libc++ and it definitely passed all the existing tests with std::sort but the longer test failed unless it used std::stable_sort.

[Alex Christensen]

http://trac.webkit.org/r210915