12359 2007-01-21 20:22:46 -0800 XPathEvaluator may return some nodes more than once in a result set 2007-01-29 10:25:04 -0800 1 1 1 Unclassified WebKit XML 420+ Mac OS X 10.4 RESOLVED FIXED http://andrewdupont.net/test/double-dollar/ P2 Normal --- 1 webkit ap ap webkit oldest_to_newest 33682 0 webkit 2007-01-21 20:22:46 -0800 While working on routing CSS selector queries through XPath for performance, I noticed that WebKit's version of document.evaluate doesn't ensure uniqueness of the result set. At the test URL, you'll notice that some queries -- like "div div" (or in XPath: ".//div//div" -- fail: the length of the result set is far larger than it should be because a DIV with two DIV ancestors would occur twice. This is different from the behavior of Firefox or Opera. Filtering for uniqueness in my own code solves this problem. Discovered using document.evaluate with result set of type ORDERED_NODE_SNAPSHOT_TYPE. 33653 1 ddkilzer 2007-01-21 20:29:31 -0800 Andrew, could you upload a reduced test case? This would be very helpful in resolving this bug. Thanks! 33654 2 12597 webkit 2007-01-21 20:43:54 -0800 Created attachment 12597 Reduced test case Illustrates the example in the above comment. Firefox returns 2 results; WebKit returns 3 (counting the innermost DIV twice). 31459 3 12729 ap 2007-01-28 11:27:12 -0800 Created attachment 12729 proposed fix 31283 4 12729 darin 2007-01-28 18:27:37 -0800 Comment on attachment 12729 proposed fix + if (!outDOMNodesSet.contains(node)) { + outDOMNodes.append(node); + outDOMNodesSet.add(node); + } This can be done more efficiently by taking advantage of the return value from add. Like this: if (outDOMNodesSet.add(node).second) outDOMNodes.append(node); I know it's a little ugly, but I love the fact that it cuts the number of hash table lookups roughly in half, so please consider this idiom. r=me 31017 5 ap 2007-01-29 10:25:04 -0800 Committed revision 19227. (In reply to comment #4) > I know it's a little ugly, but I love the fact that it cuts the number of hash > table lookups roughly in half, so please consider this idiom. Oops - corrected! I should be more critical of idioms used in existing code :) 12597 2007-01-21 20:43:54 -0800 2007-01-21 20:43:54 -0800 Reduced test case xpathtest.html text/html 799 webkit PCFET0NUWVBFIGh0bWwgUFVCTElDICItLy9XM0MvL0RURCBYSFRNTCAxLjAgVHJhbnNpdGlvbmFs Ly9FTiIKICAiaHR0cDovL3d3dy53My5vcmcvVFIveGh0bWwxL0RURC94aHRtbDEtdHJhbnNpdGlv bmFsLmR0ZCI+CjxodG1sPgogIDxoZWFkPgogICAgPHRpdGxlPlhQYXRoRXZhbHVhdG9yIHVuaXF1 ZW5lc3MgdGVzdCBwYWdlPC90aXRsZT4KICAgIAogIDwvaGVhZD4KICA8Ym9keT4KICAgIDxkaXY+ CiAgICAgIDxkaXY+CiAgICAgICAgPGRpdj5UZXN0IERJViB3aXRoaW4gdHdvIGFuY2VzdG9yIERJ VnM8L2Rpdj4KICAgICAgPC9kaXY+CiAgICA8L2Rpdj4KICAgIAogICAgPGlucHV0IHR5cGU9ImJ1 dHRvbiIgaWQ9InJ1bnRlc3QiICB2YWx1ZT0iUnVuIHRlc3QiLz4KICAgIDxkaXYgaWQ9ImxvZyI+ PC9kaXY+CiAgICA8c2NyaXB0IHR5cGU9InRleHQvamF2YXNjcmlwdCI+CiAgICAgIGRvY3VtZW50 LmdldEVsZW1lbnRCeUlkKCdydW50ZXN0Jykub25jbGljayA9IGZ1bmN0aW9uKCkgewogICAgICAg IHZhciByZXN1bHQgPSBkb2N1bWVudC5ldmFsdWF0ZSgiLy9kaXYvL2RpdiIsIGRvY3VtZW50LCBu dWxsLCBYUGF0aFJlc3VsdC5PUkRFUkVEX05PREVfU05BUFNIT1RfVFlQRSwgbnVsbCk7CiAgICAg ICAgaWYgKCFyZXN1bHQpIGFsZXJ0KCJ3dGYiKTsKICAgICAgICBkb2N1bWVudC5nZXRFbGVtZW50 QnlJZCgnbG9nJykuaW5uZXJIVE1MICs9IHJlc3VsdC5zbmFwc2hvdExlbmd0aCArICIgbWF0Y2hl cyAoc2hvdWxkIGJlIDIpIjsKICAgICAgfTsKICAgIDwvc2NyaXB0PgogIDwvYm9keT4KPC9odG1s Pg== 12729 2007-01-28 11:27:12 -0800 2007-01-28 18:27:37 -0800 proposed fix 12359r1_patch.txt text/plain 6133 ap SW5kZXg6IExheW91dFRlc3RzL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBMYXlvdXRUZXN0cy9D aGFuZ2VMb2cJKHJldmlzaW9uIDE5MTk4KQorKysgTGF5b3V0VGVzdHMvQ2hhbmdlTG9nCSh3b3Jr aW5nIGNvcHkpCkBAIC0xLDMgKzEsMTMgQEAKKzIwMDctMDEtMjggIEFsZXhleSBQcm9za3VyeWFr b3YgIDxhcEB3ZWJraXQub3JnPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEp LgorCisgICAgICAgIGh0dHA6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEyMzU5 CisgICAgICAgIFhQYXRoRXZhbHVhdG9yIG1heSByZXR1cm4gc29tZSBub2RlcyBtb3JlIHRoYW4g b25jZSBpbiBhIHJlc3VsdCBzZXQKKworICAgICAgICAqIGZhc3QveHBhdGgvbm9kZXNldC1kdXBs aWNhdGVzLWV4cGVjdGVkLnR4dDogQWRkZWQuCisgICAgICAgICogZmFzdC94cGF0aC9ub2Rlc2V0 LWR1cGxpY2F0ZXMuaHRtbDogQWRkZWQuCisKIDIwMDctMDEtMjcgIERhdmlkIEtpbHplciAgPGRk a2lsemVyQHdlYmtpdC5vcmc+CiAKICAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChtaXNzaW5n IHBpeGVsIHRlc3QgcmVzdWx0cykuCkluZGV4OiBMYXlvdXRUZXN0cy9mYXN0L3hwYXRoL25vZGVz ZXQtZHVwbGljYXRlcy1leHBlY3RlZC50eHQKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gTGF5b3V0VGVzdHMvZmFz dC94cGF0aC9ub2Rlc2V0LWR1cGxpY2F0ZXMtZXhwZWN0ZWQudHh0CShyZXZpc2lvbiAwKQorKysg TGF5b3V0VGVzdHMvZmFzdC94cGF0aC9ub2Rlc2V0LWR1cGxpY2F0ZXMtZXhwZWN0ZWQudHh0CShy ZXZpc2lvbiAwKQpAQCAtMCwwICsxLDMgQEAKK1Rlc3QgZm9yIGJ1ZyAxMjM1OTogWFBhdGhFdmFs dWF0b3IgbWF5IHJldHVybiBzb21lIG5vZGVzIG1vcmUgdGhhbiBvbmNlIGluIGEgcmVzdWx0IHNl dC4KKworU1VDQ0VTUwoKUHJvcGVydHkgY2hhbmdlcyBvbjogTGF5b3V0VGVzdHMvZmFzdC94cGF0 aC9ub2Rlc2V0LWR1cGxpY2F0ZXMtZXhwZWN0ZWQudHh0Cl9fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KTmFtZTogc3ZuOm1p bWUtdHlwZQogICArIHRleHQvcGxhaW4KTmFtZTogc3ZuOmVvbC1zdHlsZQogICArIG5hdGl2ZQoK SW5kZXg6IExheW91dFRlc3RzL2Zhc3QveHBhdGgvbm9kZXNldC1kdXBsaWNhdGVzLmh0bWwKPT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PQotLS0gTGF5b3V0VGVzdHMvZmFzdC94cGF0aC9ub2Rlc2V0LWR1cGxpY2F0ZXMuaHRt bAkocmV2aXNpb24gMCkKKysrIExheW91dFRlc3RzL2Zhc3QveHBhdGgvbm9kZXNldC1kdXBsaWNh dGVzLmh0bWwJKHJldmlzaW9uIDApCkBAIC0wLDAgKzEsMzEgQEAKKzwhRE9DVFlQRSBodG1sIFBV QkxJQyAiLS8vVzNDLy9EVEQgWEhUTUwgMS4wIFRyYW5zaXRpb25hbC8vRU4iCisgICJodHRwOi8v d3d3LnczLm9yZy9UUi94aHRtbDEvRFREL3hodG1sMS10cmFuc2l0aW9uYWwuZHRkIj4KKzxodG1s PgorICA8Ym9keT4KKyAgICA8cD5UZXN0IGZvciA8YSBocmVmPSJodHRwOi8vYnVncy53ZWJraXQu b3JnL3Nob3dfYnVnLmNnaT9pZD0xMjM1OSI+YnVnIDEyMzU5PC9hPjoKKyAgICBYUGF0aEV2YWx1 YXRvciBtYXkgcmV0dXJuIHNvbWUgbm9kZXMgbW9yZSB0aGFuIG9uY2UgaW4gYSByZXN1bHQgc2V0 LjwvcD4KKworICAgIDxkaXY+CisgICAgICA8ZGl2PgorICAgICAgICA8ZGl2PjwvZGl2PgorICAg ICAgPC9kaXY+CisgICAgPC9kaXY+CisKKyAgICA8c2NyaXB0IHR5cGU9InRleHQvamF2YXNjcmlw dCI+CisgICAgICBpZiAod2luZG93LmxheW91dFRlc3RDb250cm9sbGVyKQorICAgICAgICBsYXlv dXRUZXN0Q29udHJvbGxlci5kdW1wQXNUZXh0KCk7CisKKyAgICAgIHRyeSB7CisgICAgICAgIHZh ciByZXN1bHQgPSBkb2N1bWVudC5ldmFsdWF0ZSgiLy9kaXYvL2RpdiB8IC8vZGl2L2RpdiIsIGRv Y3VtZW50LCBudWxsLCBYUGF0aFJlc3VsdC5PUkRFUkVEX05PREVfU05BUFNIT1RfVFlQRSwgbnVs bCk7CisKKyAgICAgICAgaWYgKHJlc3VsdC5zbmFwc2hvdExlbmd0aCA9PSAyKQorICAgICAgICAg IGRvY3VtZW50LndyaXRlKCJTVUNDRVNTIik7CisgICAgICAgIGVsc2UKKyAgICAgICAgICBkb2N1 bWVudC53cml0ZShyZXN1bHQuc25hcHNob3RMZW5ndGggKyAiIG1hdGNoZXMgKHNob3VsZCBiZSAy KSIpOworCisgICAgICB9IGNhdGNoIChleCkgeworICAgICAgICBkb2N1bWVudC53cml0ZSgiRXhj ZXB0aW9uOiAiICsgZXgpOworICAgICAgfQorICAgIDwvc2NyaXB0PgorICA8L2JvZHk+Cis8L2h0 bWw+CgpQcm9wZXJ0eSBjaGFuZ2VzIG9uOiBMYXlvdXRUZXN0cy9mYXN0L3hwYXRoL25vZGVzZXQt ZHVwbGljYXRlcy5odG1sCl9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX18KTmFtZTogc3ZuOm1pbWUtdHlwZQogICArIHRleHQv aHRtbAoKSW5kZXg6IFdlYkNvcmUvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFdlYkNvcmUvQ2hh bmdlTG9nCShyZXZpc2lvbiAxOTE5OCkKKysrIFdlYkNvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNv cHkpCkBAIC0xLDMgKzEsMTggQEAKKzIwMDctMDEtMjggIEFsZXhleSBQcm9za3VyeWFrb3YgIDxh cEB3ZWJraXQub3JnPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisg ICAgICAgIGh0dHA6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEyMzU5CisgICAg ICAgIFhQYXRoRXZhbHVhdG9yIG1heSByZXR1cm4gc29tZSBub2RlcyBtb3JlIHRoYW4gb25jZSBp biBhIHJlc3VsdCBzZXQKKworICAgICAgICAqIHhtbC9YUGF0aFBhdGguY3BwOgorICAgICAgICAo V2ViQ29yZTo6WFBhdGg6OkxvY2F0aW9uUGF0aDo6ZG9FdmFsdWF0ZSk6IEVuc3VyZSB1bmlxdWVu ZXNzIG9mIGVsZW1lbnRzCisgICAgICAgIGluIHRoZSBub2RlLXNldC4KKworICAgICAgICAqIHht bC9YUGF0aFByZWRpY2F0ZS5jcHA6CisgICAgICAgIChXZWJDb3JlOjpYUGF0aDo6VW5pb246OmRv RXZhbHVhdGUpOiBGaXhlZCBhIHVuaXF1ZW5lc3MgYWxnb3JpdGhtIHRoYXQgd2FzCisgICAgICAg IGFscmVhZHkgcHJlc2VudCBoZXJlLiBBZGRlZCBhIEZJWE1FIGFib3V0IGluY29ycmVjdCByZXN1 bHQgb3JkZXJpbmcuCisKIDIwMDctMDEtMjcgIEFkYW0gUm9iZW4gIDxhcm9iZW5AYXBwbGUuY29t PgogCiAgICAgICAgIFJldmlld2VkIGJ5IEFkYS4KSW5kZXg6IFdlYkNvcmUveG1sL1hQYXRoUGF0 aC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PQotLS0gV2ViQ29yZS94bWwvWFBhdGhQYXRoLmNwcAkocmV2aXNpb24g MTkxODQpCisrKyBXZWJDb3JlL3htbC9YUGF0aFBhdGguY3BwCSh3b3JraW5nIGNvcHkpCkBAIC05 NCw3ICs5NCw3IEBAIHZvaWQgTG9jYXRpb25QYXRoOjpvcHRpbWl6ZSgpCiAKIFZhbHVlIExvY2F0 aW9uUGF0aDo6ZG9FdmFsdWF0ZSgpIGNvbnN0CiB7Ci0gICAgTm9kZVZlY3RvciBpbkRvbU5vZGVz LCBvdXREb21Ob2RlczsKKyAgICBOb2RlVmVjdG9yIGluRE9NTm9kZXM7CiAKICAgICAvKiBGb3Ig YWJzb2x1dGUgbG9jYXRpb24gcGF0aHMsIHRoZSBjb250ZXh0IG5vZGUgaXMgaWdub3JlZCAtIHRo ZQogICAgICAqIGRvY3VtZW50J3Mgcm9vdCBub2RlIGlzIHVzZWQgaW5zdGVhZC4KQEAgLTEwMywy MiArMTAzLDI5IEBAIFZhbHVlIExvY2F0aW9uUGF0aDo6ZG9FdmFsdWF0ZSgpIGNvbnN0CiAgICAg aWYgKG1fYWJzb2x1dGUgJiYgY29udGV4dC0+bm9kZVR5cGUoKSAhPSBOb2RlOjpET0NVTUVOVF9O T0RFKSAKICAgICAgICAgY29udGV4dCA9IGNvbnRleHQtPm93bmVyRG9jdW1lbnQoKTsKIAotICAg IGluRG9tTm9kZXMuYXBwZW5kKGNvbnRleHQpOworICAgIGluRE9NTm9kZXMuYXBwZW5kKGNvbnRl eHQpOwogICAgIAogICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBtX3N0ZXBzLnNpemUoKTsg aSsrKSB7CiAgICAgICAgIFN0ZXAqIHN0ZXAgPSBtX3N0ZXBzW2ldOworICAgICAgICBOb2RlVmVj dG9yIG91dERPTU5vZGVzOworICAgICAgICBIYXNoU2V0PE5vZGUqPiBvdXRET01Ob2Rlc1NldDsK IAotICAgICAgICBmb3IgKHVuc2lnbmVkIGogPSAwOyBqIDwgaW5Eb21Ob2Rlcy5zaXplKCk7IGor KykgewotICAgICAgICAgICAgTm9kZVZlY3RvciBtYXRjaGVzID0gc3RlcC0+ZXZhbHVhdGUoaW5E b21Ob2Rlc1tqXS5nZXQoKSk7CisgICAgICAgIGZvciAodW5zaWduZWQgaiA9IDA7IGogPCBpbkRP TU5vZGVzLnNpemUoKTsgaisrKSB7CisgICAgICAgICAgICBOb2RlVmVjdG9yIG1hdGNoZXMgPSBz dGVwLT5ldmFsdWF0ZShpbkRPTU5vZGVzW2pdLmdldCgpKTsKICAgICAgICAgICAgIAotICAgICAg ICAgICAgb3V0RG9tTm9kZXMuYXBwZW5kKG1hdGNoZXMpOworICAgICAgICAgICAgZm9yIChzaXpl X3Qgbm9kZUluZGV4ID0gMDsgbm9kZUluZGV4IDwgbWF0Y2hlcy5zaXplKCk7ICsrbm9kZUluZGV4 KSB7CisgICAgICAgICAgICAgICAgTm9kZSogbm9kZSA9IG1hdGNoZXNbbm9kZUluZGV4XS5nZXQo KTsKKyAgICAgICAgICAgICAgICBpZiAoIW91dERPTU5vZGVzU2V0LmNvbnRhaW5zKG5vZGUpKSB7 CisgICAgICAgICAgICAgICAgICAgIG91dERPTU5vZGVzLmFwcGVuZChub2RlKTsKKyAgICAgICAg ICAgICAgICAgICAgb3V0RE9NTm9kZXNTZXQuYWRkKG5vZGUpOworICAgICAgICAgICAgICAgIH0K KyAgICAgICAgICAgIH0KICAgICAgICAgfQogICAgICAgICAKLSAgICAgICAgaW5Eb21Ob2RlcyA9 IG91dERvbU5vZGVzOwotICAgICAgICBvdXREb21Ob2Rlcy5jbGVhcigpOworICAgICAgICBpbkRP TU5vZGVzID0gb3V0RE9NTm9kZXM7CiAgICAgfQogCi0gICAgcmV0dXJuIGluRG9tTm9kZXM7Cisg ICAgcmV0dXJuIGluRE9NTm9kZXM7CiB9CiAKIFBhdGg6OlBhdGgoRmlsdGVyKiBmaWx0ZXIsIExv Y2F0aW9uUGF0aCogcGF0aCkKSW5kZXg6IFdlYkNvcmUveG1sL1hQYXRoUHJlZGljYXRlLmNwcAo9 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09Ci0tLSBXZWJDb3JlL3htbC9YUGF0aFByZWRpY2F0ZS5jcHAJKHJldmlzaW9uIDE5 MTg0KQorKysgV2ViQ29yZS94bWwvWFBhdGhQcmVkaWNhdGUuY3BwCSh3b3JraW5nIGNvcHkpCkBA IC0xODMsNiArMTgzLDcgQEAgVmFsdWUgTG9naWNhbE9wOjpkb0V2YWx1YXRlKCkgY29uc3QKIAog VmFsdWUgVW5pb246OmRvRXZhbHVhdGUoKSBjb25zdAogeworICAgIC8vIEZJWE1FOiBUaGlzIGFs Z29yaXRobSBkb2Vzbid0IHJldHVybiBub2RlcyBpbiBkb2N1bWVudCBvcmRlciwgYXMgaXQgc2hv dWxkLgogICAgIFZhbHVlIGxocyA9IHN1YkV4cHIoMCktPmV2YWx1YXRlKCk7CiAgICAgVmFsdWUg cmhzID0gc3ViRXhwcigxKS0+ZXZhbHVhdGUoKTsKICAgICBpZiAoIWxocy5pc05vZGVWZWN0b3Io KSB8fCAhcmhzLmlzTm9kZVZlY3RvcigpKQpAQCAtMTkzLDggKzE5NCwxMCBAQCBWYWx1ZSBVbmlv bjo6ZG9FdmFsdWF0ZSgpIGNvbnN0CiAgICAgTm9kZVZlY3RvciByZXN1bHQgPSBsaHNOb2RlczsK ICAgICAKICAgICBIYXNoU2V0PE5vZGUqPiBub2RlczsKKyAgICBmb3IgKHNpemVfdCBpID0gMDsg aSA8IHJlc3VsdC5zaXplKCk7ICsraSkKKyAgICAgICAgbm9kZXMuYWRkKHJlc3VsdFtpXS5nZXQo KSk7CiAgICAgCi0gICAgZm9yICh1bnNpZ25lZCBpID0gMDsgaSA8IHJoc05vZGVzLnNpemUoKTsg aSsrKSB7CisgICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCByaHNOb2Rlcy5zaXplKCk7ICsraSkg ewogICAgICAgICBOb2RlKiBub2RlID0gcmhzTm9kZXNbaV0uZ2V0KCk7CiAgICAgICAgIAogICAg ICAgICBpZiAoIW5vZGVzLmNvbnRhaW5zKG5vZGUpKSB7Cg==