132546 2014-05-04 10:57:47 -0700 CSS JIT: reduce cost of computing backtracking height 2014-05-11 21:23:46 -0700 1 1 1 Unclassified WebKit CSS 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 ysuzuki webkit-unassigned benjamin commit-queue darin kling rniwa oldest_to_newest 1006487 0 ysuzuki 2014-05-04 10:57:47 -0700 Because compiler previously compute backtracking height for previous child fragment, by leveraging this, we can limit the `maxPrefixSize` for `computeBacktrackingHeightFromDescendant`. For example, consider selector "A>B>C>D>E>F G"'s descendant chain, "A>B>C>D>E>F". In the case of <B>, we calculate the backtracking height such as, pattern: [B, C, D, E, F] candidate0: [C, D, E, F] => not matched candidate1: [D, E, F] => not matched candidate2: [E, F] => matched At this time, first candidate (0)'s pattern size is `pattern.size() - 1`. And get backtracking height from descendant 3 `pattern.size() - candidate.size()`. And next, in the case of <A>, we re-calcucate the backtracking height such as, pattern: [A, B, C, D, E, F] candidate0: [B, C, D, E, F] => not matched candidate1: [C, D, E, F] => not matched candidate2: [D, E, F] => not matched candidate3: [E, F] => matched But we should known that candidate0 ~ candidate1 always fail because part of these patterns are already calculated in <B>'s case and we know that doesn't match. So in the case of <A>, we should start this computation from candidate2, such as, pattern: [A, B, C, D, E, F] candidate2: [D, E, F] => not matched candidate3: [E, F] => matched We can start computation with candidate size = `currentPattern.size() - previousChildFragmentBacktrackingHeightFromDescendant`. In this example, `currentPattern.size()` is 6 and `previousChildFragmentBacktrackingHeightFromDescendant` is 3, so candidate size is `3`. 1006488 1 230789 ysuzuki 2014-05-04 11:02:50 -0700 Created attachment 230789 Patch 1006887 2 230789 benjamin 2014-05-06 00:24:12 -0700 Comment on attachment 230789 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=230789&action=review Sorry, I only had a quick look, I had two crazy days. I see what you are going for here, but I am a little puzzled by the change log. Can you explain from the comment bellow? One little thing that would be nice in the changelog is explaining that your reasoning also applies for tagNameNotMatchedBacktrackingStartHeightFromDescendant because the subset before the "not matched" must have matched. > Source/WebCore/ChangeLog:13 > + For example, consider selector "A>B>C>D>E>F G"'s descendant chain, > + "A>B>C>D>E>F". I am somewhat confused by the example... > Source/WebCore/ChangeLog:17 > + pattern: [B, C, D, E, F] Shouldn't the pattern be [F, E, D, C, B, A]? > Source/WebCore/ChangeLog:20 > + candidate2: [E, F] => matched You lost me here, why is [E, F] a matching "prefix"? > Source/WebCore/cssjit/SelectorCompiler.cpp:719 > + for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) { Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators). It really does not matter here, this is just for info. > Source/WebCore/cssjit/SelectorCompiler.cpp:757 > + RELEASE_ASSERT(tagNames.size() >= previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant); Ensuring there is no overflow here is a great use of RELEASE_ASSERT :) 1006951 3 230789 ysuzuki 2014-05-06 07:23:19 -0700 Comment on attachment 230789 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=230789&action=review >> Source/WebCore/ChangeLog:17 >> + pattern: [B, C, D, E, F] > > Shouldn't the pattern be [F, E, D, C, B, A]? Since we now considers about <B>'s backtracking. <A> is not included in tagNames pattern vector. In the implementation detail, this vector is [F, E, D, C, B], but to follow the fragment's order in the selector, we describe it as [B, C, D, E, F] now. >> Source/WebCore/ChangeLog:20 >> + candidate2: [E, F] => matched > > You lost me here, why is [E, F] a matching "prefix"? In this example, "A" doesn't represent actual tag "A". "A" is an identifier for this fragment. Actually, "A" may be "div". In this time, we assume that prefix [E, F] matches to the [B, C] in this example to show the subsequent matching example. >> Source/WebCore/cssjit/SelectorCompiler.cpp:719 >> + for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) { > > Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators). > > It really does not matter here, this is just for info. Thank you! I also prefer the prefix inc/dec because of C++ iterators, I don't know WebKit also prefer it! I'll change it. 1007119 4 ysuzuki 2014-05-06 16:02:37 -0700 /I don't know/I didn't know/s Oops, mistyped. Sorry for my poor English. 1007954 5 231146 ysuzuki 2014-05-09 05:43:21 -0700 Created attachment 231146 Patch 1008266 6 darin 2014-05-10 10:58:38 -0700 Can we produce a performance test for this that shows the benefit? 1008475 7 231146 benjamin 2014-05-11 20:53:18 -0700 Comment on attachment 231146 Patch Looks good to me. 1008476 8 231146 commit-queue 2014-05-11 21:23:42 -0700 Comment on attachment 231146 Patch Clearing flags on attachment: 231146 Committed r168606: <http://trac.webkit.org/changeset/168606> 1008477 9 commit-queue 2014-05-11 21:23:46 -0700 All reviewed patches have been landed. Closing bug. 230789 2014-05-04 11:02:50 -0700 2014-05-09 05:43:14 -0700 Patch bug-132546-20140505030231.patch text/plain 5581 ysuzuki U3VidmVyc2lvbiBSZXZpc2lvbjogMTY4MjQxCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNWNkZWM0YTlmNzI1YTky ZTdlYmU2NWQ4MDJkZDExMDgyNTliYWU3OS4uMDQ4ZDU5NzNmNmM5Y2UwMGU5Y2FiNTVmZTM2YWQ3 MDIzOWM3ZTAxNyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDU4IEBACisyMDE0LTA1LTA0ICBZdXN1 a2UgU3V6dWtpICA8dXRhdGFuZS50ZWFAZ21haWwuY29tPgorCisgICAgICAgIENTUyBKSVQ6IHJl ZHVjZSBjb3N0IG9mIGNvbXB1dGluZyBiYWNrdHJhY2tpbmcgaGVpZ2h0CisgICAgICAgIGh0dHBz Oi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMzI1NDYKKworICAgICAgICBSZXZp ZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBCZWNhdXNlIGNvbXBpbGVyIHByZXZp b3VzbHkgY29tcHV0ZSBiYWNrdHJhY2tpbmcgaGVpZ2h0IGZvcgorICAgICAgICBwcmV2aW91cyBj aGlsZCBmcmFnbWVudCwgYnkgbGV2ZXJhZ2luZyB0aGlzLCB3ZSBjYW4gbGltaXQgdGhlCisgICAg ICAgIGBtYXhQcmVmaXhTaXplYCBmb3IgYGNvbXB1dGVCYWNrdHJhY2tpbmdIZWlnaHRGcm9tRGVz Y2VuZGFudGAuCisKKyAgICAgICAgRm9yIGV4YW1wbGUsIGNvbnNpZGVyIHNlbGVjdG9yICJBPkI+ Qz5EPkU+RiBHIidzIGRlc2NlbmRhbnQgY2hhaW4sCisgICAgICAgICJBPkI+Qz5EPkU+RiIuCisK KyAgICAgICAgSW4gdGhlIGNhc2Ugb2YgPEI+LCB3ZSBjYWxjdWxhdGUgdGhlIGJhY2t0cmFja2lu ZyBoZWlnaHQgc3VjaCBhcywKKworICAgICAgICBwYXR0ZXJuOiAgICBbQiwgQywgRCwgRSwgRl0K KyAgICAgICAgY2FuZGlkYXRlMDogW0MsIEQsIEUsIEZdICAgICAgPT4gbm90IG1hdGNoZWQKKyAg ICAgICAgY2FuZGlkYXRlMTogW0QsIEUsIEZdICAgICAgICAgPT4gbm90IG1hdGNoZWQKKyAgICAg ICAgY2FuZGlkYXRlMjogW0UsIEZdICAgICAgICAgICAgPT4gbWF0Y2hlZAorCisgICAgICAgIEF0 IHRoaXMgdGltZSwgZmlyc3QgY2FuZGlkYXRlMCdzIHBhdHRlcm4gc2l6ZSBpcyBgcGF0dGVybi5z aXplKCkgLSAxYC4KKyAgICAgICAgQW5kIGdldCBiYWNrdHJhY2tpbmcgaGVpZ2h0IGZyb20gZGVz Y2VuZGFudCAzLCB0aGF0IGlzCisgICAgICAgIGBwYXR0ZXJuLnNpemUoKSAtIGNhbmRpZGF0ZS5z aXplKClgLgorCisgICAgICAgIEFuZCBuZXh0LCBpbiB0aGUgY2FzZSBvZiA8QT4sIHdlIHJlLWNh bGN1Y2F0ZSB0aGUgYmFja3RyYWNraW5nCisgICAgICAgIGhlaWdodCBzdWNoIGFzLAorCisgICAg ICAgIHBhdHRlcm46ICAgIFtBLCBCLCBDLCBELCBFLCBGXQorICAgICAgICBjYW5kaWRhdGUwOiBb QiwgQywgRCwgRSwgRl0gICAgICA9PiBub3QgbWF0Y2hlZAorICAgICAgICBjYW5kaWRhdGUxOiBb QywgRCwgRSwgRl0gICAgICAgICA9PiBub3QgbWF0Y2hlZAorICAgICAgICBjYW5kaWRhdGUyOiBb RCwgRSwgRl0gICAgICAgICAgICA9PiBub3QgbWF0Y2hlZAorICAgICAgICBjYW5kaWRhdGUzOiBb RSwgRl0gICAgICAgICAgICAgICA9PiBtYXRjaGVkCisKKyAgICAgICAgQnV0IHdlIHNob3VsZCBr bm93biB0aGF0IGNhbmRpZGF0ZTAgLSBjYW5kaWRhdGUxIGFsd2F5cyBmYWlsIGJlY2F1c2UKKyAg ICAgICAgcGFydCBvZiB0aGVzZSBwYXR0ZXJucyBhcmUgYWxyZWFkeSBjYWxjdWxhdGVkIGluIDxC PidzIGNhc2UgYW5kCisgICAgICAgIHdlIGtub3cgdGhhdCBkb2Vzbid0IG1hdGNoLgorCisgICAg ICAgIFNvIGluIHRoZSBjYXNlIG9mIDxBPiwgd2Ugc2hvdWxkIHN0YXJ0IHRoaXMgY29tcHV0YXRp b24KKyAgICAgICAgZnJvbSBjYW5kaWRhdGUyLCBzdWNoIGFzLAorCisgICAgICAgIHBhdHRlcm46 ICAgIFtBLCBCLCBDLCBELCBFLCBGXQorICAgICAgICBjYW5kaWRhdGUyOiBbRCwgRSwgRl0gICAg ICAgICAgICA9PiBub3QgbWF0Y2hlZAorICAgICAgICBjYW5kaWRhdGUzOiBbRSwgRl0gICAgICAg ICAgICAgICA9PiBtYXRjaGVkCisKKyAgICAgICAgV2UgY2FuIHN0YXJ0IGNvbXB1dGF0aW9uIHdp dGggY2FuZGlkYXRlIHNpemUgPQorICAgICAgICBgY3VycmVudFBhdHRlcm4uc2l6ZSgpIC0gcHJl dmlvdXNDaGlsZEZyYWdtZW50QmFja3RyYWNraW5nSGVpZ2h0YC4KKyAgICAgICAgSW4gdGhpcyBl eGFtcGxlLCBgY3VycmVudFBhdHRlcm4uc2l6ZSgpYCBpcyA2IGFuZAorICAgICAgICBgcHJldmlv dXNDaGlsZEZyYWdtZW50QmFja3RyYWNraW5nSGVpZ2h0YCBpcyAzLAorICAgICAgICBzbyBjYW5k aWRhdGUgc2l6ZSBpcyBgM2AuCisKKyAgICAgICAgKiBjc3NqaXQvU2VsZWN0b3JDb21waWxlci5j cHA6CisgICAgICAgIChXZWJDb3JlOjpTZWxlY3RvckNvbXBpbGVyOjpjb21wdXRlQmFja3RyYWNr aW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCk6CisgICAgICAgIChXZWJDb3JlOjpTZWxlY3Rv ckNvbXBpbGVyOjpjb21wdXRlQmFja3RyYWNraW5nSGVpZ2h0RnJvbURlc2NlbmRhbnQpOgorCiAy MDE0LTA1LTAzICBDb21taXQgUXVldWUgIDxjb21taXQtcXVldWVAd2Via2l0Lm9yZz4KIAogICAg ICAgICBVbnJldmlld2VkLCByb2xsaW5nIG91dCByMTY4MjMyLgpkaWZmIC0tZ2l0IGEvU291cmNl L1dlYkNvcmUvY3Nzaml0L1NlbGVjdG9yQ29tcGlsZXIuY3BwIGIvU291cmNlL1dlYkNvcmUvY3Nz aml0L1NlbGVjdG9yQ29tcGlsZXIuY3BwCmluZGV4IDRjMTVkMmQyZmJmYWFlNmM1YjM4MGVhNzUx YjEzMjEwZWFiNTYzMDYuLjk3MThiYjM3ODQ5Y2UzY2NjNzg5ZTkxYWZlMGZjYjhlMjFiMzdiNDkg MTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL2Nzc2ppdC9TZWxlY3RvckNvbXBpbGVyLmNwcAor KysgYi9Tb3VyY2UvV2ViQ29yZS9jc3NqaXQvU2VsZWN0b3JDb21waWxlci5jcHAKQEAgLTcxMSwx MiArNzExLDEyIEBAIHN0YXRpYyBpbmxpbmUgYm9vbCBlcXVhbFRhZ05hbWVQYXR0ZXJucyhjb25z dCBUYWdOYW1lUGF0dGVybiYgbGhzLCBjb25zdCBRdWFsaWZpCiAKIC8vIEZpbmQgdGhlIGxhcmdl c3QgbWF0Y2hpbmcgcHJlZml4IGZyb20gYWxyZWFkeSBrbm93biB0YWdOYW1lcy4KIC8vIEFuZCBi eSB1c2luZyB0aGlzLCBjb21wdXRlIGFuIGFwcHJvcHJpYXRlIGhlaWdodCBvZiBiYWNrdHJhY2tp bmcgc3RhcnQgZWxlbWVudCBmcm9tIHRoZSBjbG9zZXN0IGRlc2NlbmRhbnQuCi1zdGF0aWMgaW5s aW5lIHVuc2lnbmVkIGNvbXB1dGVCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50 KGNvbnN0IFRhZ05hbWVMaXN0JiB0YWdOYW1lcykKK3N0YXRpYyBpbmxpbmUgdW5zaWduZWQgY29t cHV0ZUJhY2t0cmFja2luZ1N0YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQoY29uc3QgVGFnTmFtZUxp c3QmIHRhZ05hbWVzLCB1bnNpZ25lZCBtYXhQcmVmaXhTaXplKQogewogICAgIFJFTEVBU0VfQVNT RVJUKCF0YWdOYW1lcy5pc0VtcHR5KCkpOworICAgIFJFTEVBU0VfQVNTRVJUKG1heFByZWZpeFNp emUgPCB0YWdOYW1lcy5zaXplKCkpOwogCi0gICAgdW5zaWduZWQgbGFyZ2VzdFByZWZpeFNpemUg PSB0YWdOYW1lcy5zaXplKCk7Ci0gICAgd2hpbGUgKC0tbGFyZ2VzdFByZWZpeFNpemUpIHsKKyAg ICBmb3IgKHVuc2lnbmVkIGxhcmdlc3RQcmVmaXhTaXplID0gbWF4UHJlZml4U2l6ZTsgbGFyZ2Vz dFByZWZpeFNpemUgPiAwOyBsYXJnZXN0UHJlZml4U2l6ZS0tKSB7CiAgICAgICAgIHVuc2lnbmVk IG9mZnNldFRvTGFyZ2VzdFByZWZpeCA9IHRhZ05hbWVzLnNpemUoKSAtIGxhcmdlc3RQcmVmaXhT aXplOwogICAgICAgICBib29sIG1hdGNoZWQgPSB0cnVlOwogICAgICAgICAvLyBTaW5jZSBUYWdO YW1lUGF0dGVybnMgYXJlIHB1c2hlZCB0byBhIHRhZ05hbWVzLCBjaGVjayB0YWdOYW1lcyB3aXRo IHJldmVyc2Ugb3JkZXIuCkBAIC03NTIsMTUgKzc1MiwyMSBAQCBzdGF0aWMgaW5saW5lIHZvaWQg Y29tcHV0ZUJhY2t0cmFja2luZ0hlaWdodEZyb21EZXNjZW5kYW50KFNlbGVjdG9yRnJhZ21lbnQm IGZyYQogICAgICAgICBwYXR0ZXJuLnRhZ05hbWUgPSBmcmFnbWVudC50YWdOYW1lOwogICAgICAg ICB0YWdOYW1lcy5hcHBlbmQocGF0dGVybik7CiAKKyAgICAgICAgdW5zaWduZWQgbWF4UHJlZml4 U2l6ZSA9IHRhZ05hbWVzLnNpemUoKSAtIDE7CisgICAgICAgIGlmIChwcmV2aW91c0NoaWxkRnJh Z21lbnRJbkRlc2NlbmRhbnRCYWNrdHJhY2tpbmdDaGFpbikgeworICAgICAgICAgICAgUkVMRUFT RV9BU1NFUlQodGFnTmFtZXMuc2l6ZSgpID49IHByZXZpb3VzQ2hpbGRGcmFnbWVudEluRGVzY2Vu ZGFudEJhY2t0cmFja2luZ0NoYWluLT50YWdOYW1lTWF0Y2hlZEJhY2t0cmFja2luZ1N0YXJ0SGVp Z2h0RnJvbURlc2NlbmRhbnQpOworICAgICAgICAgICAgbWF4UHJlZml4U2l6ZSA9IHRhZ05hbWVz LnNpemUoKSAtIHByZXZpb3VzQ2hpbGRGcmFnbWVudEluRGVzY2VuZGFudEJhY2t0cmFja2luZ0No YWluLT50YWdOYW1lTWF0Y2hlZEJhY2t0cmFja2luZ1N0YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQ7 CisgICAgICAgIH0KKwogICAgICAgICBpZiAocGF0dGVybi50YWdOYW1lKSB7CiAgICAgICAgICAg ICAvLyBDb21wdXRlIGhlaWdodCBmcm9tIGRlc2NlbmRhbnQgaW4gdGhlIGNhc2UgdGhhdCB0YWdO YW1lIGlzIG5vdCBtYXRjaGVkLgogICAgICAgICAgICAgdGFnTmFtZXMubGFzdCgpLmludmVydGVk ID0gdHJ1ZTsKLSAgICAgICAgICAgIGZyYWdtZW50LnRhZ05hbWVOb3RNYXRjaGVkQmFja3RyYWNr aW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCA9IGNvbXB1dGVCYWNrdHJhY2tpbmdTdGFydEhl aWdodEZyb21EZXNjZW5kYW50KHRhZ05hbWVzKTsKKyAgICAgICAgICAgIGZyYWdtZW50LnRhZ05h bWVOb3RNYXRjaGVkQmFja3RyYWNraW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCA9IGNvbXB1 dGVCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50KHRhZ05hbWVzLCBtYXhQcmVm aXhTaXplKTsKICAgICAgICAgfQogCiAgICAgICAgIC8vIENvbXB1dGUgaGVpZ2h0IGZyb20gZGVz Y2VuZGFudCBpbiB0aGUgY2FzZSB0aGF0IHRhZ05hbWUgaXMgbWF0Y2hlZC4KICAgICAgICAgdGFn TmFtZXMubGFzdCgpLmludmVydGVkID0gZmFsc2U7Ci0gICAgICAgIGZyYWdtZW50LnRhZ05hbWVN YXRjaGVkQmFja3RyYWNraW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCA9IGNvbXB1dGVCYWNr dHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50KHRhZ05hbWVzKTsKKyAgICAgICAgZnJh Z21lbnQudGFnTmFtZU1hdGNoZWRCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50 ID0gY29tcHV0ZUJhY2t0cmFja2luZ1N0YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQodGFnTmFtZXMs IG1heFByZWZpeFNpemUpOwogICAgICAgICBmcmFnbWVudC5oZWlnaHRGcm9tRGVzY2VuZGFudCA9 IHRhZ05hbWVzLnNpemUoKSAtIDE7CiAgICAgICAgIHByZXZpb3VzQ2hpbGRGcmFnbWVudEluRGVz Y2VuZGFudEJhY2t0cmFja2luZ0NoYWluID0gJmZyYWdtZW50OwogICAgIH0gZWxzZSB7Cg== 231146 2014-05-09 05:43:21 -0700 2014-05-11 21:23:41 -0700 Patch bug-132546-20140509214321.patch text/plain 6089 ysuzuki U3VidmVyc2lvbiBSZXZpc2lvbjogMTY4MzU3CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggMzMxZTRiYzNhMTFkZjVk ZWVkZTg5N2NhYTBlZTJkZTcyMWQ4ODBiNy4uZjI3NmUwOTc2MGUzMjFjZTNmMTBlOGQwYjQ3NGVi ZDkxM2NiZDhhOCAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDY0IEBACisyMDE0LTA1LTA5ICBZdXN1 a2UgU3V6dWtpICA8dXRhdGFuZS50ZWFAZ21haWwuY29tPgorCisgICAgICAgIENTUyBKSVQ6IHJl ZHVjZSBjb3N0IG9mIGNvbXB1dGluZyBiYWNrdHJhY2tpbmcgaGVpZ2h0CisgICAgICAgIGh0dHBz Oi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMzI1NDYKKworICAgICAgICBSZXZp ZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBCZWNhdXNlIGNvbXBpbGVyIHByZXZp b3VzbHkgY29tcHV0ZSBiYWNrdHJhY2tpbmcgaGVpZ2h0IGZvcgorICAgICAgICBwcmV2aW91cyBj aGlsZCBmcmFnbWVudCwgYnkgbGV2ZXJhZ2luZyB0aGlzLCB3ZSBjYW4gbGltaXQgdGhlCisgICAg ICAgIGBtYXhQcmVmaXhTaXplYCBmb3IgYGNvbXB1dGVCYWNrdHJhY2tpbmdIZWlnaHRGcm9tRGVz Y2VuZGFudGAuCisKKyAgICAgICAgRm9yIGV4YW1wbGUsIGNvbnNpZGVyIHNlbGVjdG9yICJjPmE+ Yj5kPmE+YiBlIidzIGRlc2NlbmRhbnQgY2hhaW4sCisgICAgICAgICJjPmE+Yj5kPmE+YiIuCisK KyAgICAgICAgQXQgdGhlIDxhPiBwb3NpdGlvbiwgd2UgaGF2ZSBtYXRjaGluZyBwYXR0ZXJuIFti LCBhLCBkLCBiLCBhXSBhbmQKKyAgICAgICAgY2FsY3VsYXRlIHRoZSBiYWNrdHJhY2tpbmcgaGVp Z2h0IGJ5IGZvbGxvd2luZyBtZXRob2QuCisKKyAgICAgICAgcGF0dGVybjogICAgW2IsIGEsIGQs IGIsIGFdCisgICAgICAgIGNhbmRpZGF0ZTA6ICAgIFtiLCBhLCBkLCBiXSAgPT4gTm90IG1hdGNo ZWQuCisgICAgICAgIGNhbmRpZGF0ZTE6ICAgICAgIFtiLCBhLCBkXSAgPT4gTm90IG1hdGNoZWQu CisgICAgICAgIGNhbmRpZGF0ZTI6ICAgICAgICAgIFtiLCBhXSAgPT4gTWF0Y2hlZCBhZ2FpbnN0 IHRoZSBwYXR0ZXJuLgorCisgICAgICAgIEF0IHRoaXMgdGltZSwgZmlyc3QgY2FuZGlkYXRlMCdz IHBhdHRlcm4gc2l6ZSBpcyBgcGF0dGVybi5zaXplKCkgLSAxYC4KKyAgICAgICAgQW5kIGdldCBi YWNrdHJhY2tpbmcgaGVpZ2h0IGZyb20gZGVzY2VuZGFudCAzLCB0aGF0IGlzCisgICAgICAgIGBw YXR0ZXJuLnNpemUoKSAtIGNhbmRpZGF0ZS5zaXplKClgLCBgNSAtIDJgLgorCisgICAgICAgIEFu ZCBuZXh0LCBhdCB0aGUgPGM+IHBvc2l0aW9uLCB3ZSBjYWxjdWNhdGUgdGhlIGJhY2t0cmFja2lu ZyBoZWlnaHQKKyAgICAgICAgZm9yIHRoaXMgcGF0dGVybi4KKworICAgICAgICBwYXR0ZXJuOiAg ICBbYiwgYSwgZCwgYiwgYSwgY10KKyAgICAgICAgY2FuZGlkYXRlMDogICAgW2IsIGEsIGQsIGIs IGFdICA9PiBOb3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlMTogICAgICAgW2IsIGEsIGQs IGJdICA9PiBOb3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlMjogICAgICAgICAgW2IsIGEs IGRdICA9PiBOb3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlMzogICAgICAgICAgICAgW2Is IGFdICA9PiBOb3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlNDogICAgICAgICAgICAgICAg W2JdICA9PiBOb3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlNTogICAgICAgICAgICAgICAg IFtdICA9PiBNYXRjaGVkIGFnYWluc3QgdGhlIHBhdHRlcm4uCisKKyAgICAgICAgVGhlbiwgd2Ug Z2V0IHRoZSBiYWNrdHJhY2tpbmcgaGVpZ2h0LCB3aGljaCBpcyA2ICg2IC0gMCkuCisgICAgICAg IEhvd2V2ZXIsIGluIHRoZSBhYm92ZSBjYXNlLCB3ZSBhbHJlYWR5IGtub3cgdGhhdCBhdHRlbXB0 cyBmcm9tIGNhbmRpZGF0ZTAKKyAgICAgICAgdG8gY2FuZGlkYXRlMSBhbHdheXMgZmFpbCwgc2lu Y2UgcGFydHMgb2YgdGhlc2UgYXJlIGFscmVhZHkgdGVzdGVkIGF0CisgICAgICAgIHRoZSA8Yj4g cG9zaXRpb24gdHJpYWwgYW5kIHdlIGtub3cgdGhleSBkb24ndCBtYXRjaC4KKworICAgICAgICBT byBpbiB0aGlzIGNhc2UsIHdlIHNob3VsZCBzdGFydCB0aGlzIGNvbXB1dGF0aW9uIGZyb20gY2Fu ZGlkYXRlMiwKKyAgICAgICAgc3VjaCBhcywKKworICAgICAgICBwYXR0ZXJuOiAgICBbYiwgYSwg ZCwgYiwgYSwgY10KKyAgICAgICAgY2FuZGlkYXRlMjogICAgICAgICAgW2IsIGEsIGRdICA9PiBO b3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlMzogICAgICAgICAgICAgW2IsIGFdICA9PiBO b3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlNDogICAgICAgICAgICAgICAgW2JdICA9PiBO b3QgbWF0Y2hlZC4KKyAgICAgICAgY2FuZGlkYXRlNTogICAgICAgICAgICAgICAgIFtdICA9PiBN YXRjaGVkIGFnYWluc3QgdGhlIHBhdHRlcm4uCisKKyAgICAgICAgV2UgY2FuIHN0YXJ0IGNvbXB1 dGF0aW9uIHdpdGggY2FuZGlkYXRlIHNpemUKKyAgICAgICAgYHBhdHRlcm4uc2l6ZSgpIC0gcHJl dmlvdXNDaGlsZEZyYWdtZW50QmFja3RyYWNraW5nSGVpZ2h0YC4KKyAgICAgICAgSW4gdGhpcyBl eGFtcGxlLCBgcGF0dGVybi5zaXplKClgIGlzIDYgYW5kCisgICAgICAgIGBwcmV2aW91c0NoaWxk RnJhZ21lbnRCYWNrdHJhY2tpbmdIZWlnaHRgIGlzIDMsIHNvIGNhbmRpZGF0ZSBzaXplIGlzCisg ICAgICAgIDMsIHRoYXQgaXMgY2FuZGlkYXRlMi4KKworICAgICAgICAqIGNzc2ppdC9TZWxlY3Rv ckNvbXBpbGVyLmNwcDoKKyAgICAgICAgKFdlYkNvcmU6OlNlbGVjdG9yQ29tcGlsZXI6OmNvbXB1 dGVCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50KToKKyAgICAgICAgKFdlYkNv cmU6OlNlbGVjdG9yQ29tcGlsZXI6OmNvbXB1dGVCYWNrdHJhY2tpbmdIZWlnaHRGcm9tRGVzY2Vu ZGFudCk6CisKIDIwMTQtMDUtMDUgIFphbiBEb2JlcnNlayAgPHpkb2JlcnNla0BpZ2FsaWEuY29t PgogCiAgICAgICAgIFtTb3VwXSBVc2Ugc3RkOjp1bmlxdWVfcHRyPGNoYXJbXT4gZm9yIHRoZSBy ZWFkIGJ1ZmZlciBpbiBTb2NrZXRTdHJlYW1IYW5kbGUKZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJD b3JlL2Nzc2ppdC9TZWxlY3RvckNvbXBpbGVyLmNwcCBiL1NvdXJjZS9XZWJDb3JlL2Nzc2ppdC9T ZWxlY3RvckNvbXBpbGVyLmNwcAppbmRleCA0YzE1ZDJkMmZiZmFhZTZjNWIzODBlYTc1MWIxMzIx MGVhYjU2MzA2Li5jMGMxYmQ2MzU4MDk1YjhhMzcyYTcwYTViOTMwOGZiMjc1ZTI2MmJkIDEwMDY0 NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9jc3NqaXQvU2VsZWN0b3JDb21waWxlci5jcHAKKysrIGIv U291cmNlL1dlYkNvcmUvY3Nzaml0L1NlbGVjdG9yQ29tcGlsZXIuY3BwCkBAIC03MTEsMTIgKzcx MSwxMiBAQCBzdGF0aWMgaW5saW5lIGJvb2wgZXF1YWxUYWdOYW1lUGF0dGVybnMoY29uc3QgVGFn TmFtZVBhdHRlcm4mIGxocywgY29uc3QgUXVhbGlmaQogCiAvLyBGaW5kIHRoZSBsYXJnZXN0IG1h dGNoaW5nIHByZWZpeCBmcm9tIGFscmVhZHkga25vd24gdGFnTmFtZXMuCiAvLyBBbmQgYnkgdXNp bmcgdGhpcywgY29tcHV0ZSBhbiBhcHByb3ByaWF0ZSBoZWlnaHQgb2YgYmFja3RyYWNraW5nIHN0 YXJ0IGVsZW1lbnQgZnJvbSB0aGUgY2xvc2VzdCBkZXNjZW5kYW50Lgotc3RhdGljIGlubGluZSB1 bnNpZ25lZCBjb21wdXRlQmFja3RyYWNraW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudChjb25z dCBUYWdOYW1lTGlzdCYgdGFnTmFtZXMpCitzdGF0aWMgaW5saW5lIHVuc2lnbmVkIGNvbXB1dGVC YWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50KGNvbnN0IFRhZ05hbWVMaXN0JiB0 YWdOYW1lcywgdW5zaWduZWQgbWF4UHJlZml4U2l6ZSkKIHsKICAgICBSRUxFQVNFX0FTU0VSVCgh dGFnTmFtZXMuaXNFbXB0eSgpKTsKKyAgICBSRUxFQVNFX0FTU0VSVChtYXhQcmVmaXhTaXplIDwg dGFnTmFtZXMuc2l6ZSgpKTsKIAotICAgIHVuc2lnbmVkIGxhcmdlc3RQcmVmaXhTaXplID0gdGFn TmFtZXMuc2l6ZSgpOwotICAgIHdoaWxlICgtLWxhcmdlc3RQcmVmaXhTaXplKSB7CisgICAgZm9y ICh1bnNpZ25lZCBsYXJnZXN0UHJlZml4U2l6ZSA9IG1heFByZWZpeFNpemU7IGxhcmdlc3RQcmVm aXhTaXplID4gMDsgLS1sYXJnZXN0UHJlZml4U2l6ZSkgewogICAgICAgICB1bnNpZ25lZCBvZmZz ZXRUb0xhcmdlc3RQcmVmaXggPSB0YWdOYW1lcy5zaXplKCkgLSBsYXJnZXN0UHJlZml4U2l6ZTsK ICAgICAgICAgYm9vbCBtYXRjaGVkID0gdHJ1ZTsKICAgICAgICAgLy8gU2luY2UgVGFnTmFtZVBh dHRlcm5zIGFyZSBwdXNoZWQgdG8gYSB0YWdOYW1lcywgY2hlY2sgdGFnTmFtZXMgd2l0aCByZXZl cnNlIG9yZGVyLgpAQCAtNzUyLDE1ICs3NTIsMjEgQEAgc3RhdGljIGlubGluZSB2b2lkIGNvbXB1 dGVCYWNrdHJhY2tpbmdIZWlnaHRGcm9tRGVzY2VuZGFudChTZWxlY3RvckZyYWdtZW50JiBmcmEK ICAgICAgICAgcGF0dGVybi50YWdOYW1lID0gZnJhZ21lbnQudGFnTmFtZTsKICAgICAgICAgdGFn TmFtZXMuYXBwZW5kKHBhdHRlcm4pOwogCisgICAgICAgIHVuc2lnbmVkIG1heFByZWZpeFNpemUg PSB0YWdOYW1lcy5zaXplKCkgLSAxOworICAgICAgICBpZiAocHJldmlvdXNDaGlsZEZyYWdtZW50 SW5EZXNjZW5kYW50QmFja3RyYWNraW5nQ2hhaW4pIHsKKyAgICAgICAgICAgIFJFTEVBU0VfQVNT RVJUKHRhZ05hbWVzLnNpemUoKSA+PSBwcmV2aW91c0NoaWxkRnJhZ21lbnRJbkRlc2NlbmRhbnRC YWNrdHJhY2tpbmdDaGFpbi0+dGFnTmFtZU1hdGNoZWRCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZy b21EZXNjZW5kYW50KTsKKyAgICAgICAgICAgIG1heFByZWZpeFNpemUgPSB0YWdOYW1lcy5zaXpl KCkgLSBwcmV2aW91c0NoaWxkRnJhZ21lbnRJbkRlc2NlbmRhbnRCYWNrdHJhY2tpbmdDaGFpbi0+ dGFnTmFtZU1hdGNoZWRCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50OworICAg ICAgICB9CisKICAgICAgICAgaWYgKHBhdHRlcm4udGFnTmFtZSkgewogICAgICAgICAgICAgLy8g Q29tcHV0ZSBoZWlnaHQgZnJvbSBkZXNjZW5kYW50IGluIHRoZSBjYXNlIHRoYXQgdGFnTmFtZSBp cyBub3QgbWF0Y2hlZC4KICAgICAgICAgICAgIHRhZ05hbWVzLmxhc3QoKS5pbnZlcnRlZCA9IHRy dWU7Ci0gICAgICAgICAgICBmcmFnbWVudC50YWdOYW1lTm90TWF0Y2hlZEJhY2t0cmFja2luZ1N0 YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQgPSBjb21wdXRlQmFja3RyYWNraW5nU3RhcnRIZWlnaHRG cm9tRGVzY2VuZGFudCh0YWdOYW1lcyk7CisgICAgICAgICAgICBmcmFnbWVudC50YWdOYW1lTm90 TWF0Y2hlZEJhY2t0cmFja2luZ1N0YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQgPSBjb21wdXRlQmFj a3RyYWNraW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCh0YWdOYW1lcywgbWF4UHJlZml4U2l6 ZSk7CiAgICAgICAgIH0KIAogICAgICAgICAvLyBDb21wdXRlIGhlaWdodCBmcm9tIGRlc2NlbmRh bnQgaW4gdGhlIGNhc2UgdGhhdCB0YWdOYW1lIGlzIG1hdGNoZWQuCiAgICAgICAgIHRhZ05hbWVz Lmxhc3QoKS5pbnZlcnRlZCA9IGZhbHNlOwotICAgICAgICBmcmFnbWVudC50YWdOYW1lTWF0Y2hl ZEJhY2t0cmFja2luZ1N0YXJ0SGVpZ2h0RnJvbURlc2NlbmRhbnQgPSBjb21wdXRlQmFja3RyYWNr aW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCh0YWdOYW1lcyk7CisgICAgICAgIGZyYWdtZW50 LnRhZ05hbWVNYXRjaGVkQmFja3RyYWNraW5nU3RhcnRIZWlnaHRGcm9tRGVzY2VuZGFudCA9IGNv bXB1dGVCYWNrdHJhY2tpbmdTdGFydEhlaWdodEZyb21EZXNjZW5kYW50KHRhZ05hbWVzLCBtYXhQ cmVmaXhTaXplKTsKICAgICAgICAgZnJhZ21lbnQuaGVpZ2h0RnJvbURlc2NlbmRhbnQgPSB0YWdO YW1lcy5zaXplKCkgLSAxOwogICAgICAgICBwcmV2aW91c0NoaWxkRnJhZ21lbnRJbkRlc2NlbmRh bnRCYWNrdHJhY2tpbmdDaGFpbiA9ICZmcmFnbWVudDsKICAgICB9IGVsc2Ugewo=