77502 2012-01-31 19:45:33 -0800 Optimize owner form lookup 2012-03-30 01:36:59 -0700 1 1 1 Unclassified WebKit Forms 528+ (Nightly build) Unspecified Unspecified RESOLVED WONTFIX http://www.haun.org/kent/html5/find-form-perf.html P2 Normal --- 58837 1 tkent tkent ap darin dglazkov jonlee morrita yosin oldest_to_newest 546750 0 tkent 2012-01-31 19:45:33 -0800 We use HTMLElement::findFormAncestor() to find an owner <form> when we insert a form control to a tree. findFormAncestor() iterates over ancestor nodes until it finds a <form>. So, if the tree doesn't contain no <form> elements, inserting a form control is O(depth). 546751 1 tkent 2012-01-31 19:49:11 -0800 The page of the URL field shows "106 ms" on my machine. I confirmed an incoming patch improved it to "8 ms". 546866 2 124897 tkent 2012-02-01 00:48:38 -0800 Created attachment 124897 Patch 547194 3 124897 ap 2012-02-01 10:39:47 -0800 Comment on attachment 124897 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=124897&action=review Does this affect any real web pages? It's too easy to introduce security and correctness bugs by such caching, the benefit should be very material to attempt it. There is obvious memory impact - we already cache form pointer in every HTMLFormControlElement upon creation, and now we will have a separate map too. I, for one, cannot vouch that ContainerNode::insertedIntoDocument and removedFromDocument cover all cases (are they called recursively? what's the difference with willRemove()?). Having another catch-all callback pair inside Document will be confusing (how will we decide what goes there, and what goes in ContainerNode counterpart?). We have fairly weak test coverage in this area, especially for form controls that are outside their <form> trees in DOM. > Source/WebCore/dom/Document.h:521 > + void didInsertContainerNode(const ContainerNode*); > + void didRemoveContainerNode(const ContainerNode*); > + HTMLFormElement* nearestAncestorForm(const HTMLElement*); We don't use const with nodes. 547200 4 124897 darin 2012-02-01 10:48:52 -0800 Comment on attachment 124897 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=124897&action=review This makes adding form controls faster by spending a lot of memory and by hurting performance for adding elements that are not inside a form. I’m not sure this is the way to do it. Instead, I think we should look at the possibility of memoizing the information about what form something is in and computing it only when asked. > Source/WebCore/dom/ContainerNode.cpp:803 > + document()->didInsertContainerNode(this); What’s the performance impact of adding this additional work for every container node? Even doing it for every HTML element seems like it would cause a measurable performance slowdown. Also, since we need this map only for HTML elements, why are we doing this for all other container nodes? > Source/WebCore/dom/Document.cpp:4625 > + if (!parent) > + return; How did you test this code path? When is this 0? > Source/WebCore/dom/Document.cpp:4631 > + m_ancestorFormMap.set(node, form); This seems like a vast amount of extra memory use. An entry in as hash table for every single element inside a form! 547604 5 tkent 2012-02-01 20:46:16 -0800 Thank you for comments. I think the performance of HTMLElement::findFormAncestor() is not important for now. If we have a deep DOM tree and a lot of form controls, we must have other performance bottlenecks. I haven't seen real bugs caused by HTMLElement::findFormAncestor() performance. However, we need to add ancestor lookup for <fieldset> and <datalist> in addition to <form>. * https://bugs.webkit.org/show_bug.cgi?id=58837 * http://www.whatwg.org/specs/web-apps/current-work/multipage/the-button-element.html#the-datalist-element (See Constraint Validation paragraph) When we implement these features, the ancestor lookup performance can be a show-stopper. Actually Bug 58837 was blocked by this issue. I'd like to propose a way to resolve such ancestor lookup performance issue in this bug. 558484 6 124897 eric 2012-02-16 13:41:14 -0800 Comment on attachment 124897 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=124897&action=review >> Source/WebCore/dom/Document.h:521 >> + HTMLFormElement* nearestAncestorForm(const HTMLElement*); > > We don't use const with nodes. .... because they're RefCounted (and thus passing them around as const means they can't be put into a RefPtr). 566995 7 124897 ap 2012-02-28 12:56:43 -0800 Comment on attachment 124897 Patch My and Darin's comments sound like r-. 567343 8 yosin 2012-02-28 20:39:11 -0800 Just dumb thought, can we calculation of owner form and HTMLFormElement:m_associatedElements on demand? Something like: class FormAssociatedElement ... { ... enum { Ready, NotReady } m_formState; HTMLFormElement* m_form; }; class HTMLFormElement ... { enum { Dirty, NotReady, Ready } m_associateElementsState; ... }; = PROS = * No slowness for this test. :-) * Don't need to compute unused m_form and m_associatedElements, e.g. I usually ignore survey form. = CONS = * Changes spread into 11 files. * Total calculation time isn't changed if no dynamic form associated element insertion/deletion. * Dynamic form associated element addition/deletion requires another calculation of m_associatedElements. 567404 9 tkent 2012-02-28 23:04:11 -0800 (In reply to comment #8) > Just dumb thought, can we calculation of owner form and HTMLFormElement:m_associatedElements on demand? I don't think it will have performance benefit because updating m_associatedElements requires DOM traversal, but it might simplify the code. FormAssociatedElement.cpp will be smaller, and the HTML parser won't need to track a parent <form>. 567409 10 yosin 2012-02-28 23:12:33 -0800 I suspected slowness of Vector::append when adding 4000 form associate elements. But, it isn't. It seems Vector::append isn't slow. There are 25 times of Vector::expandCapcity and copy of elements(= 19,423 x 4 = 77,692 byte on 32bit platform). Here is result: 1: grow to 16 2: grow to 22 3: grow to 29 4: grow to 38 5: grow to 49 6: grow to 63 7: grow to 81 8: grow to 103 9: grow to 131 10: grow to 166 11: grow to 209 12: grow to 263 13: grow to 331 14: grow to 416 15: grow to 522 16: grow to 654 17: grow to 819 18: grow to 1026 19: grow to 1284 20: grow to 1607 21: grow to 2011 22: grow to 2516 23: grow to 3147 24: grow to 3936 25: grow to 4922 591950 11 tkent 2012-03-30 01:36:59 -0700 I'll withdraw this bug because the idea in Bug 58837 (searching ancestors for <fieldset> and <legend> in single traversal) looks enough. Comment #8 - #10 is another issue. We should discuss it in another bug. 124897 2012-02-01 00:48:38 -0800 2012-02-28 12:56:43 -0800 Patch bug-77502-20120201174836.patch text/plain 9343 tkent U3VidmVyc2lvbiBSZXZpc2lvbjogMTA2MzUxCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNTBiMjAyN2IwNTRlZGZk ODA2Mzk3ZGJlNGY5NTg0ODAxN2M3NDU5Ni4uNWU5MTU1ZTJmNTEyODA4NGRiMzVmZDc0N2JjNzBk NmE4MDdmMTc0NiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDQyIEBACisyMDEyLTAyLTAxICBLZW50 IFRhbXVyYSAgPHRrZW50QGNocm9taXVtLm9yZz4KKworICAgICAgICBPcHRpbWl6ZSBvd25lciBm b3JtIGxvb2t1cAorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/ aWQ9Nzc1MDIKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAg ICBXZSB1c2UgSFRNTEVsZW1lbnQ6OmZpbmRGb3JtQW5jZXN0b3IoKSB0byBmaW5kIGFuIG93bmVy IDxmb3JtPgorICAgICAgICB3aGVuIHdlIGluc2VydCBhIGZvcm0gY29udHJvbCB0byBhIHRyZWUu IGZpbmRGb3JtQW5jZXN0b3IoKQorICAgICAgICBpdGVyYXRlcyBvdmVyIGFuY2VzdG9yIG5vZGVz IHVudGlsIGl0IGZpbmRzIGEgPGZvcm0+LiBTbywgaWYgdGhlcmUKKyAgICAgICAgYXJlIG5vIDxm b3JtPiBlbGVtZW50cyBpbiBhbmNlc3RvcnMgb2YgdGhlIGluc2VydGVkIGZvcm0gY29udHJvbCwK KyAgICAgICAgdGhlIGluc2VydGlvbiBjb3N0IGlzIE8oZGVwdGgpLgorCisgICAgICAgIFRvIGlt cHJvdmUgdGhlIHBlcmZvcm1hbmNlLCB3ZSBpbnRyb2R1Y2UgYSBtYXAgZnJvbSBlbGVtZW50cyB0 bworICAgICAgICB0aGVpciBuZWFyZXN0IGFuY2VzdG9yIDxmb3JtPiBlbGVlbW50cyBpbiBhIERv Y3VtZW50LiBXZSBjYW4KKyAgICAgICAgb2J0YWluIGEgPGZvcm0+IGluIE8oMSkgaWYgYSBmb3Jt IGNvbnRyb2wgaXMgaW5zZXJ0ZWQgaW50byBhCisgICAgICAgIGRvY3VtZW50IHRyZWUuIElmIGFu IGVsZW1lbnQgaGFzIG5vIDxmb3JtPiBhbmNlc3Rvciwgd2UgZG9uJ3QgbWFrZQorICAgICAgICBh IG1hcCBlbnRyeSBmb3IgaXQuCisgICAgICAgIAorICAgICAgICBUZXN0OiBwZXJmL2ZpbmQtZm9y bS1jb250cm9sLW93bmVyLmh0bWwKKworICAgICAgICAqIGRvbS9Db250YWluZXJOb2RlLmNwcDoK KyAgICAgICAgKFdlYkNvcmU6OkNvbnRhaW5lck5vZGU6Omluc2VydGVkSW50b0RvY3VtZW50KTog Q2FsbHMgRG9jdW1lbnQ6OmRpZEluc2VydENvbnRhaW5lck5vZGUoKS4KKyAgICAgICAgKFdlYkNv cmU6OkNvbnRhaW5lck5vZGU6OnJlbW92ZWRGcm9tRG9jdW1lbnQpOiBDYWxscyBEb2N1bWVudDo6 ZGlkUmVtb3ZlQ29udGFpbmVyTm9kZSgpLgorICAgICAgICAqIGRvbS9Eb2N1bWVudC5jcHA6Cisg ICAgICAgIChXZWJDb3JlOjpEb2N1bWVudDo6ZGlkSW5zZXJ0Q29udGFpbmVyTm9kZSk6CisgICAg ICAgIFJlZ2lzdGVyIHRoZSBzcGVjaWZpZWQgbm9kZSB0byBtX2FuY2VzdG9yRm9ybU1hcCBpZiBp dCBoYXMgYW4gYW5jZXN0b3IgPGZvcm0+LgorICAgICAgICAoV2ViQ29yZTo6RG9jdW1lbnQ6OmRp ZFJlbW92ZUNvbnRhaW5lck5vZGUpOgorICAgICAgICBVbnJlZ2lzdGVyIHRoZSBzcGVjaWZpZWQg bm9kZSBmcm9tIG1fYW5jZXN0b3JGb3JtTWFwLgorICAgICAgICAoV2ViQ29yZTo6RG9jdW1lbnQ6 Om5lYXJlc3RBbmNlc3RvckZvcm0pOgorICAgICAgICBSZXR1cm5zIHRoZSBjb3JyZXNwb25kaW5n IDxmb3JtPiBmb3IgdGhlIHNwZWNpZmllZCBub2RlLgorICAgICAgICAqIGRvbS9Eb2N1bWVudC5o OgorICAgICAgICAoRG9jdW1lbnQpOiBBZGQgZGVjbGFyYXRpb25zIG9mIGRpZEluc2VydENvbnRh aW5lck5vZGUsCisgICAgICAgIGRpZFJlbW92ZUNvbnRhaW5lck5vZGUsIG5lYXJlc3RBbmNlc3Rv ckZvcm0sIGFuZCBtX2FuY2VzdG9yRm9ybU1hcC4KKyAgICAgICAgKiBodG1sL0hUTUxFbGVtZW50 LmNwcDoKKyAgICAgICAgKFdlYkNvcmU6OmZpbmROZWFyZXN0QW5jZXN0b3JGb3JtKTogUmVuYW1l ZCBmcm9tIGZpbmRGb3JtQW5jZXN0b3IoKS4KKyAgICAgICAgKFdlYkNvcmU6OkhUTUxFbGVtZW50 OjpmaW5kRm9ybUFuY2VzdG9yKToKKyAgICAgICAgSWYgdGhpcyBlbGVtZW50IGlzIGluIGRvY3Vt ZW50LCB1c2UgRG9jdW1lbnQ6Om5lYXJlc3RBbmNlc3RvckZvcm0oKS4KKwogMjAxMi0wMS0zMSAg Um9sYW5kIFN0ZWluZXIgIDxyb2xhbmRzdGVpbmVyQGNocm9taXVtLm9yZz4KIAogICAgICAgICA8 c3R5bGUgc2NvcGVkPjogSW1wcm92ZSBzaG9ydGN1dCBjb2RlIGZvciBjYXNlcyB3aGVyZSA8c3R5 bGUgc2NvcGVkPiBpc24ndCB1c2VkCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vQ29u dGFpbmVyTm9kZS5jcHAgYi9Tb3VyY2UvV2ViQ29yZS9kb20vQ29udGFpbmVyTm9kZS5jcHAKaW5k ZXggZDVjZDA5YjlmZGFmOTk3ZjQ3ODBmMjNmMTY1Y2JlN2JjYTQ3MDhmNi4uMDBmOTQxM2M4Yzg2 YWExNTJjNTVhNTFmZWMwODFiOTk5YjM2YjI0NiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUv ZG9tL0NvbnRhaW5lck5vZGUuY3BwCisrKyBiL1NvdXJjZS9XZWJDb3JlL2RvbS9Db250YWluZXJO b2RlLmNwcApAQCAtODAwLDYgKzgwMCw3IEBAIHZvaWQgQ29udGFpbmVyTm9kZTo6aW5zZXJ0ZWRJ bnRvRG9jdW1lbnQoKQogICAgIFJlZlB0cjxOb2RlPiBwcm90ZWN0KHRoaXMpOwogCiAgICAgTm9k ZTo6aW5zZXJ0ZWRJbnRvRG9jdW1lbnQoKTsKKyAgICBkb2N1bWVudCgpLT5kaWRJbnNlcnRDb250 YWluZXJOb2RlKHRoaXMpOwogICAgIGluc2VydGVkSW50b1RyZWUoZmFsc2UpOwogCiAgICAgZm9y IChSZWZQdHI8Tm9kZT4gY2hpbGQgPSBtX2ZpcnN0Q2hpbGQ7IGNoaWxkOyBjaGlsZCA9IGNoaWxk LT5uZXh0U2libGluZygpKSB7CkBAIC04MTUsNiArODE2LDcgQEAgdm9pZCBDb250YWluZXJOb2Rl OjppbnNlcnRlZEludG9Eb2N1bWVudCgpCiB2b2lkIENvbnRhaW5lck5vZGU6OnJlbW92ZWRGcm9t RG9jdW1lbnQoKQogewogICAgIE5vZGU6OnJlbW92ZWRGcm9tRG9jdW1lbnQoKTsKKyAgICBkb2N1 bWVudCgpLT5kaWRSZW1vdmVDb250YWluZXJOb2RlKHRoaXMpOwogICAgIGlmIChkb2N1bWVudCgp LT5jc3NUYXJnZXQoKSA9PSB0aGlzKSAKICAgICAgICAgZG9jdW1lbnQoKS0+c2V0Q1NTVGFyZ2V0 KDApOyAKICAgICBjbGVhckluRG9jdW1lbnQoKTsKZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3Jl L2RvbS9Eb2N1bWVudC5jcHAgYi9Tb3VyY2UvV2ViQ29yZS9kb20vRG9jdW1lbnQuY3BwCmluZGV4 IDNhYmIzYWRhOWJjYjUxZjAxZjAyNDc1YTgxOTE2NzNiZGVhOGExYTEuLjQ3ZTYyNzk1YjdlMjBm MjYyODYzNmYwZTUzZDBmYmZjNjE0YWJlMjIgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL2Rv bS9Eb2N1bWVudC5jcHAKKysrIGIvU291cmNlL1dlYkNvcmUvZG9tL0RvY3VtZW50LmNwcApAQCAt ODUsNiArODUsNyBAQAogI2luY2x1ZGUgIkhUTUxDb2xsZWN0aW9uLmgiCiAjaW5jbHVkZSAiSFRN TERvY3VtZW50LmgiCiAjaW5jbHVkZSAiSFRNTEVsZW1lbnRGYWN0b3J5LmgiCisjaW5jbHVkZSAi SFRNTEZvcm1FbGVtZW50LmgiCiAjaW5jbHVkZSAiSFRNTEZyYW1lT3duZXJFbGVtZW50LmgiCiAj aW5jbHVkZSAiSFRNTEhlYWRFbGVtZW50LmgiCiAjaW5jbHVkZSAiSFRNTElGcmFtZUVsZW1lbnQu aCIKQEAgLTQ2MTcsNiArNDYxOCwzMCBAQCB2b2lkIERvY3VtZW50OjpyZXNldEZvcm1FbGVtZW50 c093bmVyKCkKICAgICAgICAgKCppdCktPnJlc2V0Rm9ybU93bmVyKCk7CiB9CiAKK3ZvaWQgRG9j dW1lbnQ6OmRpZEluc2VydENvbnRhaW5lck5vZGUoY29uc3QgQ29udGFpbmVyTm9kZSogbm9kZSkK K3sKKyAgICBDb250YWluZXJOb2RlKiBwYXJlbnQgPSBub2RlLT5wYXJlbnROb2RlKCk7CisgICAg aWYgKCFwYXJlbnQpCisgICAgICAgIHJldHVybjsKKyAgICBpZiAocGFyZW50LT5oYXNUYWdOYW1l KGZvcm1UYWcpKSB7CisgICAgICAgIG1fYW5jZXN0b3JGb3JtTWFwLnNldChub2RlLCBzdGF0aWNf Y2FzdDxIVE1MRm9ybUVsZW1lbnQqPihwYXJlbnQpKTsKKyAgICAgICAgcmV0dXJuOworICAgIH0K KyAgICBpZiAoSFRNTEZvcm1FbGVtZW50KiBmb3JtID0gbV9hbmNlc3RvckZvcm1NYXAuZ2V0KHBh cmVudCkpCisgICAgICAgIG1fYW5jZXN0b3JGb3JtTWFwLnNldChub2RlLCBmb3JtKTsKK30KKwor dm9pZCBEb2N1bWVudDo6ZGlkUmVtb3ZlQ29udGFpbmVyTm9kZShjb25zdCBDb250YWluZXJOb2Rl KiBub2RlKQoreworICAgIG1fYW5jZXN0b3JGb3JtTWFwLnJlbW92ZShub2RlKTsKK30KKworSFRN TEZvcm1FbGVtZW50KiBEb2N1bWVudDo6bmVhcmVzdEFuY2VzdG9yRm9ybShjb25zdCBIVE1MRWxl bWVudCogZWxlbWVudCkKK3sKKyAgICBBU1NFUlQoZWxlbWVudC0+aW5Eb2N1bWVudCgpKTsKKyAg ICByZXR1cm4gbV9hbmNlc3RvckZvcm1NYXAuZ2V0KGVsZW1lbnQpOworfQorCiB2b2lkIERvY3Vt ZW50OjpzZXRVc2VTZWN1cmVLZXlib2FyZEVudHJ5V2hlbkFjdGl2ZShib29sIHVzZXNTZWN1cmVL ZXlib2FyZCkKIHsKICAgICBpZiAobV91c2VTZWN1cmVLZXlib2FyZEVudHJ5V2hlbkFjdGl2ZSA9 PSB1c2VzU2VjdXJlS2V5Ym9hcmQpCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9kb20vRG9j dW1lbnQuaCBiL1NvdXJjZS9XZWJDb3JlL2RvbS9Eb2N1bWVudC5oCmluZGV4IGZkYjM5ODg3NWY1 MTRkZmZjNGM3MDM5NzIxYjFhNzU3NDdjYmI5N2IuLmRkNTljYzQ5NWNiN2IzNThiMjdlMmI3NGM2 NWFkN2Y5NTg1M2Q2ZWQgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL2RvbS9Eb2N1bWVudC5o CisrKyBiL1NvdXJjZS9XZWJDb3JlL2RvbS9Eb2N1bWVudC5oCkBAIC01MTYsNiArNTE2LDkgQEAg cHVibGljOgogICAgIHZvaWQgcmVnaXN0ZXJGb3JtRWxlbWVudFdpdGhGb3JtQXR0cmlidXRlKEZv cm1Bc3NvY2lhdGVkRWxlbWVudCopOwogICAgIHZvaWQgdW5yZWdpc3RlckZvcm1FbGVtZW50V2l0 aEZvcm1BdHRyaWJ1dGUoRm9ybUFzc29jaWF0ZWRFbGVtZW50Kik7CiAgICAgdm9pZCByZXNldEZv cm1FbGVtZW50c093bmVyKCk7CisgICAgdm9pZCBkaWRJbnNlcnRDb250YWluZXJOb2RlKGNvbnN0 IENvbnRhaW5lck5vZGUqKTsKKyAgICB2b2lkIGRpZFJlbW92ZUNvbnRhaW5lck5vZGUoY29uc3Qg Q29udGFpbmVyTm9kZSopOworICAgIEhUTUxGb3JtRWxlbWVudCogbmVhcmVzdEFuY2VzdG9yRm9y bShjb25zdCBIVE1MRWxlbWVudCopOwogCiAgICAgRnJhbWVWaWV3KiB2aWV3KCkgY29uc3Q7IC8v IGNhbiBiZSBOVUxMCiAgICAgRnJhbWUqIGZyYW1lKCkgY29uc3QgeyByZXR1cm4gbV9mcmFtZTsg fSAvLyBjYW4gYmUgTlVMTApAQCAtMTI4MSw2ICsxMjg0LDggQEAgcHJpdmF0ZToKIAogICAgIHR5 cGVkZWYgSGFzaE1hcDxGb3JtRWxlbWVudEtleSwgVmVjdG9yPFN0cmluZz4sIEZvcm1FbGVtZW50 S2V5SGFzaCwgRm9ybUVsZW1lbnRLZXlIYXNoVHJhaXRzPiBGb3JtRWxlbWVudFN0YXRlTWFwOwog ICAgIEZvcm1FbGVtZW50U3RhdGVNYXAgbV9zdGF0ZUZvck5ld0Zvcm1FbGVtZW50czsKKyAgICB0 eXBlZGVmIEhhc2hNYXA8Y29uc3QgQ29udGFpbmVyTm9kZSosIEhUTUxGb3JtRWxlbWVudCo+IEFu Y2VzdG9yRm9ybU1hcDsKKyAgICBBbmNlc3RvckZvcm1NYXAgbV9hbmNlc3RvckZvcm1NYXA7CiAg ICAgCiAgICAgQ29sb3IgbV9saW5rQ29sb3I7CiAgICAgQ29sb3IgbV92aXNpdGVkTGlua0NvbG9y OwpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUvaHRtbC9IVE1MRWxlbWVudC5jcHAgYi9Tb3Vy Y2UvV2ViQ29yZS9odG1sL0hUTUxFbGVtZW50LmNwcAppbmRleCA2ODBjMjNiNWRmOWI1MmYzMjA0 ZmEzMzg4ODY3NWI1NDg2MWNjZDIyLi40MGY4YmRkZjM3YTZmNDE4ZTlhZGNiYzYyZTc0N2EwNGMx NTQ0Njk3IDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9odG1sL0hUTUxFbGVtZW50LmNwcAor KysgYi9Tb3VyY2UvV2ViQ29yZS9odG1sL0hUTUxFbGVtZW50LmNwcApAQCAtODUzLDE1ICs4NTMs MjUgQEAgUmVuZGVyT2JqZWN0KiBIVE1MRWxlbWVudDo6Y3JlYXRlUmVuZGVyZXIoUmVuZGVyQXJl bmEqIGFyZW5hLCBSZW5kZXJTdHlsZSogc3R5bGUKICAgICByZXR1cm4gUmVuZGVyT2JqZWN0Ojpj cmVhdGVPYmplY3QodGhpcywgc3R5bGUpOwogfQogCi1IVE1MRm9ybUVsZW1lbnQqIEhUTUxFbGVt ZW50OjpmaW5kRm9ybUFuY2VzdG9yKCkgY29uc3QKK3N0YXRpYyBpbmxpbmUgSFRNTEZvcm1FbGVt ZW50KiBmaW5kTmVhcmVzdEFuY2VzdG9yRm9ybShjb25zdCBIVE1MRWxlbWVudCogZWxlbWVudCkK IHsKLSAgICBmb3IgKENvbnRhaW5lck5vZGUqIGFuY2VzdG9yID0gcGFyZW50Tm9kZSgpOyBhbmNl c3RvcjsgYW5jZXN0b3IgPSBhbmNlc3Rvci0+cGFyZW50Tm9kZSgpKSB7CisgICAgZm9yIChDb250 YWluZXJOb2RlKiBhbmNlc3RvciA9IGVsZW1lbnQtPnBhcmVudE5vZGUoKTsgYW5jZXN0b3I7IGFu Y2VzdG9yID0gYW5jZXN0b3ItPnBhcmVudE5vZGUoKSkgewogICAgICAgICBpZiAoYW5jZXN0b3It Pmhhc1RhZ05hbWUoZm9ybVRhZykpCiAgICAgICAgICAgICByZXR1cm4gc3RhdGljX2Nhc3Q8SFRN TEZvcm1FbGVtZW50Kj4oYW5jZXN0b3IpOwogICAgIH0KICAgICByZXR1cm4gMDsKIH0KIAorSFRN TEZvcm1FbGVtZW50KiBIVE1MRWxlbWVudDo6ZmluZEZvcm1BbmNlc3RvcigpIGNvbnN0Cit7Cisg ICAgaWYgKGluRG9jdW1lbnQoKSkgeworICAgICAgICBIVE1MRm9ybUVsZW1lbnQqIGZvcm0gPSBk b2N1bWVudCgpLT5uZWFyZXN0QW5jZXN0b3JGb3JtKHRoaXMpOworICAgICAgICBBU1NFUlQoZm9y bSA9PSBmaW5kTmVhcmVzdEFuY2VzdG9yRm9ybSh0aGlzKSk7CisgICAgICAgIHJldHVybiBmb3Jt OworICAgIH0KKyAgICByZXR1cm4gZmluZE5lYXJlc3RBbmNlc3RvckZvcm0odGhpcyk7Cit9CisK IEhUTUxGb3JtRWxlbWVudCogSFRNTEVsZW1lbnQ6OnZpcnR1YWxGb3JtKCkgY29uc3QKIHsKICAg ICByZXR1cm4gZmluZEZvcm1BbmNlc3RvcigpOwpkaWZmIC0tZ2l0IGEvTGF5b3V0VGVzdHMvQ2hh bmdlTG9nIGIvTGF5b3V0VGVzdHMvQ2hhbmdlTG9nCmluZGV4IDJkMjM3NzBhMzNkMDA0ZTcwZDFh YTlhNmY1ZDIzZjZjYWJmM2I3MzUuLjE3NDQwNTE2NDNkNjQ3MjVlYzE1ZjY3NDExMmJlYzNkODI1 NzFjZWUgMTAwNjQ0Ci0tLSBhL0xheW91dFRlc3RzL0NoYW5nZUxvZworKysgYi9MYXlvdXRUZXN0 cy9DaGFuZ2VMb2cKQEAgLTEsMyArMSwxMyBAQAorMjAxMi0wMi0wMSAgS2VudCBUYW11cmEgIDx0 a2VudEBjaHJvbWl1bS5vcmc+CisKKyAgICAgICAgT3B0aW1pemUgb3duZXIgZm9ybSBsb29rdXAK KyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTc3NTAyCisK KyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisKKyAgICAgICAgKiBwZXJmL2Zp bmQtZm9ybS1jb250cm9sLW93bmVyLWV4cGVjdGVkLnR4dDogQWRkZWQuCisgICAgICAgICogcGVy Zi9maW5kLWZvcm0tY29udHJvbC1vd25lci5odG1sOiBBZGRlZC4KKwogMjAxMi0wMS0zMSAgWXV6 byBGdWppc2hpbWEgIDx5dXpvQGdvb2dsZS5jb20+CiAKICAgICAgICAgW0Nocm9taXVtXSBVbnJl dmlld2VkIHRlc3QgZXhwZWN0YXRpb24gY2hhbmdlLgpkaWZmIC0tZ2l0IGEvTGF5b3V0VGVzdHMv cGVyZi9maW5kLWZvcm0tY29udHJvbC1vd25lci1leHBlY3RlZC50eHQgYi9MYXlvdXRUZXN0cy9w ZXJmL2ZpbmQtZm9ybS1jb250cm9sLW93bmVyLWV4cGVjdGVkLnR4dApuZXcgZmlsZSBtb2RlIDEw MDY0NAppbmRleCAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwLi40Mjcz MTQ1N2YxNjI0ODM5MDBlNTY5YTQ1MTQ2YmZmODY3NDFkMzQ5Ci0tLSAvZGV2L251bGwKKysrIGIv TGF5b3V0VGVzdHMvcGVyZi9maW5kLWZvcm0tY29udHJvbC1vd25lci1leHBlY3RlZC50eHQKQEAg LTAsMCArMSwzIEBACitUZXN0cyB0aGF0IGFkZGluZyBhIGZvcm0gY29udHJvbCB0byBhbiBlbGVt ZW50IGlzIGNvbnN0YW50IGluIHRoZSBlbGVtZW50IGRlcHRoIGluIHRoZSB0cmVlLgorUEFTUwor CmRpZmYgLS1naXQgYS9MYXlvdXRUZXN0cy9wZXJmL2ZpbmQtZm9ybS1jb250cm9sLW93bmVyLmh0 bWwgYi9MYXlvdXRUZXN0cy9wZXJmL2ZpbmQtZm9ybS1jb250cm9sLW93bmVyLmh0bWwKbmV3IGZp bGUgbW9kZSAxMDA2NDQKaW5kZXggMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAw MDAwMC4uZTVmNmJhOTMxZjExMDcyMTNlNjY1MThhNDA4MzM1MDJlMzcwZDFkMQotLS0gL2Rldi9u dWxsCisrKyBiL0xheW91dFRlc3RzL3BlcmYvZmluZC1mb3JtLWNvbnRyb2wtb3duZXIuaHRtbApA QCAtMCwwICsxLDM0IEBACis8IURPQ1RZUEUgaHRtbD4KKzxodG1sPgorPGJvZHk+Cis8c2NyaXB0 IHNyYz0iLi4vcmVzb3VyY2VzL21hZ25pdHVkZS1wZXJmLmpzIj48L3NjcmlwdD4KKzxzY3JpcHQ+ Cit2YXIgdGVzdFJvb3QgPSBudWxsOwordmFyIHRlc3RQYXJlbnQ7CisKK2Z1bmN0aW9uIHNldHVw KG1hZ25pdHVkZSkgeworICAgIGlmICh0ZXN0Um9vdCkKKyAgICAgICAgZG9jdW1lbnQuYm9keS5y ZW1vdmVDaGlsZCh0ZXN0Um9vdCk7CisgICAgdGVzdFJvb3QgPSBkb2N1bWVudC5jcmVhdGVFbGVt ZW50KCdkaXYnKTsKKyAgICBkb2N1bWVudC5ib2R5LmFwcGVuZENoaWxkKHRlc3RSb290KTsKKyAg ICB0ZXN0UGFyZW50ID0gdGVzdFJvb3Q7CisgICAgZm9yICh2YXIgaSA9IDA7IGkgPCAxMDAgKyBt YWduaXR1ZGUgKiAxMDsgKytpKSB7CisgICAgICAgIHZhciBuZXdQYXJlbnQgPSBkb2N1bWVudC5j cmVhdGVFbGVtZW50KCdkaXYnKTsKKyAgICAgICAgdGVzdFBhcmVudC5hcHBlbmRDaGlsZChuZXdQ YXJlbnQpOworICAgICAgICB0ZXN0UGFyZW50ID0gbmV3UGFyZW50OworICAgIH0KK30KKworZnVu Y3Rpb24gdGVzdChtYWduaXR1ZGUpIHsKKyAgICBmb3IgKHZhciBpID0gMDsgaSA8IDEwOyArK2kp IHsKKyAgICAgICAgdmFyIGlucHV0ID0gZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgnaW5wdXQnKTsK KyAgICAgICAgaW5wdXQuaGlkZGVuID0gdHJ1ZTsKKyAgICAgICAgdGVzdFBhcmVudC5hcHBlbmRD aGlsZChpbnB1dCk7CisgICAgfQorfQorCitNYWduaXR1ZGUuZGVzY3JpcHRpb24oIlRlc3RzIHRo YXQgYWRkaW5nIGEgZm9ybSBjb250cm9sIHRvIGFuIGVsZW1lbnQgaXMgY29uc3RhbnQgaW4gdGhl IGVsZW1lbnQgZGVwdGggaW4gdGhlIHRyZWUuIik7CitNYWduaXR1ZGUucnVuKHNldHVwLCB0ZXN0 LCBNYWduaXR1ZGUuQ09OU1RBTlQpOworPC9zY3JpcHQ+Cis8L2JvZHk+Cis8L2h0bWw+Cg==