167154 2017-01-18 00:06:49 -0800 Implement URLSearchParams's sort() 2017-01-18 23:46:59 -0800 1 1 1 Unclassified WebKit DOM Safari Technology Preview Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 annevk achristensen achristensen cdumez commit-queue esprehn+autocc gyuyoung.kim kondapallykalyan oldest_to_newest 1267683 0 annevk 2017-01-18 00:06:49 -0800 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. 1267968 1 299208 achristensen 2017-01-18 18:19:25 -0800 Created attachment 299208 Patch 1267974 2 achristensen 2017-01-18 18:30:04 -0800 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"]] }, 1267980 3 299208 sam 2017-01-18 18:41:48 -0800 Comment on attachment 299208 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. 1268051 4 annevk 2017-01-18 23:27:47 -0800 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? 1268054 5 achristensen 2017-01-18 23:39:30 -0800 (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. 1268055 6 achristensen 2017-01-18 23:46:59 -0800 http://trac.webkit.org/r210915 299208 2017-01-18 18:19:25 -0800 2017-01-18 18:41:48 -0800 Patch bug-167154-20170118181735.patch text/plain 5389 achristensen SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDIxMDkwMykKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDE3IEBACisyMDE3LTAxLTE4ICBBbGV4IENo cmlzdGVuc2VuICA8YWNocmlzdGVuc2VuQHdlYmtpdC5vcmc+CisKKyAgICAgICAgSW1wbGVtZW50 IFVSTFNlYXJjaFBhcmFtcydzIHNvcnQoKQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9y Zy9zaG93X2J1Zy5jZ2k/aWQ9MTY3MTU0CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChP T1BTISkuCisKKyAgICAgICAgVGVzdDogaW1wb3J0ZWQvdzNjL3dlYi1wbGF0Zm9ybS10ZXN0cy91 cmwvdXJsc2VhcmNocGFyYW1zLXNvcnQuaHRtbAorCisgICAgICAgICogaHRtbC9VUkxTZWFyY2hQ YXJhbXMuY3BwOgorICAgICAgICAoV2ViQ29yZTo6VVJMU2VhcmNoUGFyYW1zOjpzb3J0KToKKyAg ICAgICAgKiBodG1sL1VSTFNlYXJjaFBhcmFtcy5oOgorICAgICAgICAqIGh0bWwvVVJMU2VhcmNo UGFyYW1zLmlkbDoKKwogMjAxNy0wMS0xOCAgUnlhbiBIYWRkYWQgIDxyeWFuaGFkZGFkQGFwcGxl LmNvbT4KIAogICAgICAgICBVbnJldmlld2VkLCByb2xsaW5nIG91dCByMjEwODQ4LgpJbmRleDog U291cmNlL1dlYkNvcmUvaHRtbC9VUkxTZWFyY2hQYXJhbXMuY3BwCj09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNv dXJjZS9XZWJDb3JlL2h0bWwvVVJMU2VhcmNoUGFyYW1zLmNwcAkocmV2aXNpb24gMjEwODg5KQor KysgU291cmNlL1dlYkNvcmUvaHRtbC9VUkxTZWFyY2hQYXJhbXMuY3BwCSh3b3JraW5nIGNvcHkp CkBAIC01OSw2ICs1OSwxNCBAQCBib29sIFVSTFNlYXJjaFBhcmFtczo6aGFzKGNvbnN0IFN0cmlu ZyYgCiAgICAgcmV0dXJuIGZhbHNlOwogfQogCit2b2lkIFVSTFNlYXJjaFBhcmFtczo6c29ydCgp Cit7CisgICAgc3RkOjpzdGFibGVfc29ydChtX3BhaXJzLmJlZ2luKCksIG1fcGFpcnMuZW5kKCks IFtdIChhdXRvIGEsIGF1dG8gYikgeworICAgICAgICByZXR1cm4gV1RGOjpjb2RlUG9pbnRDb21w YXJlTGVzc1RoYW4oYS5maXJzdCwgYi5maXJzdCk7CisgICAgfSk7CisgICAgdXBkYXRlVVJMKCk7 Cit9CisKIHZvaWQgVVJMU2VhcmNoUGFyYW1zOjpzZXQoY29uc3QgU3RyaW5nJiBuYW1lLCBjb25z dCBTdHJpbmcmIHZhbHVlKQogewogICAgIGZvciAoYXV0byYgcGFpciA6IG1fcGFpcnMpIHsKSW5k ZXg6IFNvdXJjZS9XZWJDb3JlL2h0bWwvVVJMU2VhcmNoUGFyYW1zLmgKPT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0g U291cmNlL1dlYkNvcmUvaHRtbC9VUkxTZWFyY2hQYXJhbXMuaAkocmV2aXNpb24gMjEwODg5KQor KysgU291cmNlL1dlYkNvcmUvaHRtbC9VUkxTZWFyY2hQYXJhbXMuaAkod29ya2luZyBjb3B5KQpA QCAtNDcsNiArNDcsNyBAQCBwdWJsaWM6CiAgICAgY29uc3QgVmVjdG9yPHN0ZDo6cGFpcjxTdHJp bmcsIFN0cmluZz4+JiBwYWlycygpIGNvbnN0IHsgcmV0dXJuIG1fcGFpcnM7IH0KICAgICBvcGVy YXRvciBjb25zdCBWZWN0b3I8c3RkOjpwYWlyPFN0cmluZywgU3RyaW5nPj4mKCkgeyByZXR1cm4g bV9wYWlyczsgfQogICAgIHZvaWQgdXBkYXRlRnJvbUFzc29jaWF0ZWRVUkwoKTsKKyAgICB2b2lk IHNvcnQoKTsKIAogICAgIGNsYXNzIEl0ZXJhdG9yIHsKICAgICBwdWJsaWM6CkluZGV4OiBTb3Vy Y2UvV2ViQ29yZS9odG1sL1VSTFNlYXJjaFBhcmFtcy5pZGwKPT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNl L1dlYkNvcmUvaHRtbC9VUkxTZWFyY2hQYXJhbXMuaWRsCShyZXZpc2lvbiAyMTA4ODkpCisrKyBT b3VyY2UvV2ViQ29yZS9odG1sL1VSTFNlYXJjaFBhcmFtcy5pZGwJKHdvcmtpbmcgY29weSkKQEAg LTM0LDYgKzM0LDkgQEAKICAgICBzZXF1ZW5jZTxVU1ZTdHJpbmc+IGdldEFsbChVU1ZTdHJpbmcg bmFtZSk7CiAgICAgYm9vbGVhbiBoYXMoVVNWU3RyaW5nIG5hbWUpOwogICAgIHZvaWQgc2V0KFVT VlN0cmluZyBuYW1lLCBVU1ZTdHJpbmcgdmFsdWUpOworCisgICAgdm9pZCBzb3J0KCk7CisKICAg ICBpdGVyYWJsZTxVU1ZTdHJpbmcsIFVTVlN0cmluZz47CiAKICAgICAvLyBGSVhNRTogVGhpcyBz aG91bGQganVzdCBiZSBzdHJpbmdpZmllciBvbmNlIHRoYXQgaXMgc3VwcG9ydGVkIGluIHRoZSBi aW5kaW5ncyBnZW5lcmF0b3IKSW5kZXg6IExheW91dFRlc3RzL2ltcG9ydGVkL3czYy9DaGFuZ2VM b2cKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PQotLS0gTGF5b3V0VGVzdHMvaW1wb3J0ZWQvdzNjL0NoYW5nZUxvZwkocmV2 aXNpb24gMjEwOTAzKQorKysgTGF5b3V0VGVzdHMvaW1wb3J0ZWQvdzNjL0NoYW5nZUxvZwkod29y a2luZyBjb3B5KQpAQCAtMSwzICsxLDEzIEBACisyMDE3LTAxLTE4ICBBbGV4IENocmlzdGVuc2Vu ICA8YWNocmlzdGVuc2VuQHdlYmtpdC5vcmc+CisKKyAgICAgICAgSW1wbGVtZW50IFVSTFNlYXJj aFBhcmFtcydzIHNvcnQoKQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1 Zy5jZ2k/aWQ9MTY3MTU0CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisK KyAgICAgICAgKiB3ZWItcGxhdGZvcm0tdGVzdHMvdXJsL3VybHNlYXJjaHBhcmFtcy1zb3J0LWV4 cGVjdGVkLnR4dDogQWRkZWQuCisgICAgICAgICogd2ViLXBsYXRmb3JtLXRlc3RzL3VybC91cmxz ZWFyY2hwYXJhbXMtc29ydC5odG1sOiBBZGRlZC4KKwogMjAxNy0wMS0xOCAgWW91ZW5uIEZhYmxl dCAgPHlvdWVubkBhcHBsZS5jb20+CiAKICAgICAgICAgUmVqZWN0IGZldGNoIHByb21pc2UgaW4g Y2FzZSBvZiBSZWFkYWJsZVN0cmVhbSB1cGxvYWQKSW5kZXg6IExheW91dFRlc3RzL2ltcG9ydGVk L3czYy93ZWItcGxhdGZvcm0tdGVzdHMvdXJsL3VybHNlYXJjaHBhcmFtcy1zb3J0LWV4cGVjdGVk LnR4dAo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09Ci0tLSBMYXlvdXRUZXN0cy9pbXBvcnRlZC93M2Mvd2ViLXBsYXRmb3Jt LXRlc3RzL3VybC91cmxzZWFyY2hwYXJhbXMtc29ydC1leHBlY3RlZC50eHQJKG5vbmV4aXN0ZW50 KQorKysgTGF5b3V0VGVzdHMvaW1wb3J0ZWQvdzNjL3dlYi1wbGF0Zm9ybS10ZXN0cy91cmwvdXJs c2VhcmNocGFyYW1zLXNvcnQtZXhwZWN0ZWQudHh0CSh3b3JraW5nIGNvcHkpCkBAIC0wLDAgKzEs MTAgQEAKKworUEFTUyBQYXJzZSBhbmQgc29ydDogej1iJmE9YiZ6PWEmYT1hIAorUEFTUyBVUkwg cGFyc2UgYW5kIHNvcnQ6IHo9YiZhPWImej1hJmE9YSAKK1BBU1MgUGFyc2UgYW5kIHNvcnQ6IO+/ vT14Ju+/vCbvv709YSAKK1BBU1MgVVJMIHBhcnNlIGFuZCBzb3J0OiDvv709eCbvv7wm77+9PWEg CitQQVNTIFBhcnNlIGFuZCBzb3J0OiDvrIMm8J+MiCAKK1BBU1MgVVJMIHBhcnNlIGFuZCBzb3J0 OiDvrIMm8J+MiCAKK1BBU1MgUGFyc2UgYW5kIHNvcnQ6IMOpJmXvv70mZcyBIAorUEFTUyBVUkwg cGFyc2UgYW5kIHNvcnQ6IMOpJmXvv70mZcyBIAorCkluZGV4OiBMYXlvdXRUZXN0cy9pbXBvcnRl ZC93M2Mvd2ViLXBsYXRmb3JtLXRlc3RzL3VybC91cmxzZWFyY2hwYXJhbXMtc29ydC5odG1sCj09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT0KLS0tIExheW91dFRlc3RzL2ltcG9ydGVkL3czYy93ZWItcGxhdGZvcm0tdGVzdHMv dXJsL3VybHNlYXJjaHBhcmFtcy1zb3J0Lmh0bWwJKG5vbmV4aXN0ZW50KQorKysgTGF5b3V0VGVz dHMvaW1wb3J0ZWQvdzNjL3dlYi1wbGF0Zm9ybS10ZXN0cy91cmwvdXJsc2VhcmNocGFyYW1zLXNv cnQuaHRtbAkod29ya2luZyBjb3B5KQpAQCAtMCwwICsxLDQ2IEBACis8IWRvY3R5cGUgaHRtbD4K KzxtZXRhIGNoYXJzZXQ9InV0ZjgiPgorPHNjcmlwdCBzcmM9Ii9yZXNvdXJjZXMvdGVzdGhhcm5l c3MuanMiPjwvc2NyaXB0PgorPHNjcmlwdCBzcmM9Ii9yZXNvdXJjZXMvdGVzdGhhcm5lc3NyZXBv cnQuanMiPjwvc2NyaXB0PgorPGRpdiBpZD1sb2c+PC9kaXY+Cis8c2NyaXB0PgorWworICB7Cisg ICAgImlucHV0IjogIno9YiZhPWImej1hJmE9YSIsCisgICAgIm91dHB1dCI6IFtbImEiLCAiYiJd LCBbImEiLCAiYSJdLCBbInoiLCAiYiJdLCBbInoiLCAiYSJdXQorICB9LAorICB7CisgICAgImlu cHV0IjogIlx1RkZGRD14Jlx1RkZGQyZcdUZGRkQ9YSIsCisgICAgIm91dHB1dCI6IFtbIlx1RkZG QyIsICIiXSwgWyJcdUZGRkQiLCAieCJdLCBbIlx1RkZGRCIsICJhIl1dCisgIH0sCisgIHsKKyAg ICAiaW5wdXQiOiAi76yDJvCfjIgiLCAvLyDwn4yIID4gY29kZSBwb2ludCwgYnV0IDwgY29kZSB1 bml0IGJlY2F1c2UgdHdvIGNvZGUgdW5pdHMKKyAgICAib3V0cHV0IjogW1si8J+MiCIsICIiXSwg WyLvrIMiLCAiIl1dCisgIH0sCisgIHsKKyAgICAiaW5wdXQiOiAiw6kmZVx1RkZGRCZlXHUwMzAx IiwKKyAgICAib3V0cHV0IjogW1siZVx1MDMwMSIsICIiXSwgWyJlXHVGRkZEIiwgIiJdLCBbIsOp IiwgIiJdXQorICB9CitdLmZvckVhY2goKHZhbCkgPT4geworICB0ZXN0KCgpID0+IHsKKyAgICBs ZXQgcGFyYW1zID0gbmV3IFVSTFNlYXJjaFBhcmFtcyh2YWwuaW5wdXQpLAorICAgICAgICBpID0g MAorICAgIHBhcmFtcy5zb3J0KCkKKyAgICBmb3IobGV0IHBhcmFtIG9mIHBhcmFtcykgeworICAg ICAgYXNzZXJ0X2FycmF5X2VxdWFscyhwYXJhbSwgdmFsLm91dHB1dFtpXSkKKyAgICAgIGkrKwor ICAgIH0KKyAgfSwgIlBhcnNlIGFuZCBzb3J0OiAiICsgdmFsLmlucHV0KQorCisgIHRlc3QoKCkg PT4geworICAgIGxldCB1cmwgPSBuZXcgVVJMKCI/IiArIHZhbC5pbnB1dCwgImh0dHBzOi8vZXhh bXBsZS8iKQorICAgIHVybC5zZWFyY2hQYXJhbXMuc29ydCgpCisgICAgbGV0IHBhcmFtcyA9IG5l dyBVUkxTZWFyY2hQYXJhbXModXJsLnNlYXJjaCksCisgICAgICAgIGkgPSAwCisgICAgZm9yKGxl dCBwYXJhbSBvZiBwYXJhbXMpIHsKKyAgICAgIGFzc2VydF9hcnJheV9lcXVhbHMocGFyYW0sIHZh bC5vdXRwdXRbaV0pCisgICAgICBpKysKKyAgICB9CisgIH0sICJVUkwgcGFyc2UgYW5kIHNvcnQ6 ICIgKyB2YWwuaW5wdXQpCit9KQorPC9zY3JpcHQ+Cg==