From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Tianxiang Xiong Newsgroups: gmane.emacs.devel Subject: Re: Performance issue w/ `cl-loop`s `collect...into` Date: Sun, 8 Apr 2018 18:10:28 -0700 Message-ID: References: <41631665-6cd6-7096-8866-5ab9559a14ef@gmail.com> <1d5b85f5-62cd-f2f3-0b71-9e2a2cf2ef9e@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="94eb2c199dc25bd9980569601260" X-Trace: blaine.gmane.org 1523236118 2490 195.159.176.226 (9 Apr 2018 01:08:38 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 9 Apr 2018 01:08:38 +0000 (UTC) Cc: Emacs developers To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Apr 09 03:08:34 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1f5LIP-0000XB-6x for ged-emacs-devel@m.gmane.org; Mon, 09 Apr 2018 03:08:33 +0200 Original-Received: from localhost ([::1]:44777 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5LKU-00088q-TK for ged-emacs-devel@m.gmane.org; Sun, 08 Apr 2018 21:10:42 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47013) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f5LKL-00087H-9K for emacs-devel@gnu.org; Sun, 08 Apr 2018 21:10:35 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f5LKJ-0001Z1-6H for emacs-devel@gnu.org; Sun, 08 Apr 2018 21:10:33 -0400 Original-Received: from mail-wm0-x229.google.com ([2a00:1450:400c:c09::229]:37919) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1f5LKI-0001Y9-PW for emacs-devel@gnu.org; Sun, 08 Apr 2018 21:10:31 -0400 Original-Received: by mail-wm0-x229.google.com with SMTP id i3so12868212wmf.3 for ; Sun, 08 Apr 2018 18:10:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=aUDGWZtyui0wXQ8W6jOcamzvPmZHMxlrraNAAjLMV5w=; b=YTETJrD7tywLYJzdp22RZG4/FBGT4YimnRltUMi0pY9nJ/ZefHgPgPewNGR9tNSScu oMfNGdFfX3lbQKZFNeQzJf1vFOkhhSSQ5I+el8jakZUvwyLJBQTbNlzHLLo4AngFOR5e mD3KJghgYaYsRec4seN0Hy/eFhfup7V59qqls+OZ4AsYlONW7CK5Ibg2k2TwamI999hV pPkif8bVsMGSOQ2RZXHW039aeHqQMGVd3S5fnQlNaGWdKWIgLtTUNP6/75UrPMU/TWCV +pxjlOUvoZI1ipG4XjFND3RsTp/ySBaRHqhaNtBFH+25kQrfcaExFFSR3bH/Qfytui4a p8Lw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=aUDGWZtyui0wXQ8W6jOcamzvPmZHMxlrraNAAjLMV5w=; b=at9YBQ75jkqMTRZiRQXWvuCJbj5Q/hsXlQ+y/WlZm6IinfxEtDMYjFLNk8P3hKZ3c1 p775YqTXMKhaPdrW9fZr1n5sARYOHs2um16jlrDOdJiddr9vg1DqQ8nzTnsZ5dhL8V0E tBcEnfHVxr1xTv0Xm6iPLGLsrsPz0/X1kVoS4WsJK8waEXZNOt5ODCvRrld/W9NA2oEX +eZcGJ9QsvgYpGYvsH+UQq+i9H52vXM9DUgvJbGVMLFV0ik1qBMV15xBFLZeW8SgQ72x kYhDAA8wehuC6tgnn9W5mD+Xxzt2oUedrX6GhtBh0QQ0+sCOhsqluKizO1KvZAaC9CA1 Ne8A== X-Gm-Message-State: ALQs6tAjJL1P3kU4xlNEplKIRscjC6lmYE5x1Dzu5j8tlLK+mkfHP4iM W1NgWSBE3pJNJmbVe2Z/WsxSftPS6oMaC6CrHUE= X-Google-Smtp-Source: AIpwx4+9qp7lz30oqsgxuZPJV58F/6blALp9yFvBCQ8ANR50PB80Wei+dK3rxXECtLL5/VLmWg386vMdBAtAWa2aaEg= X-Received: by 10.80.149.84 with SMTP id v20mr3580821eda.190.1523236229334; Sun, 08 Apr 2018 18:10:29 -0700 (PDT) Original-Received: by 10.80.203.195 with HTTP; Sun, 8 Apr 2018 18:10:28 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:400c:c09::229 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:224444 Archived-At: --94eb2c199dc25bd9980569601260 Content-Type: multipart/alternative; boundary="94eb2c199dc25bd996056960125e" --94eb2c199dc25bd996056960125e Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Here's a second, cleaner attempt that separates the `cl--loop-handle-accum` function into two functions, one to deal with lists and one to deal w/ non-lists. The tail-tracking optimizing is also applied to `append(ing)` and `nconc(ing)`. On Sun, Apr 8, 2018 at 4:29 PM, Tianxiang Xiong wrote: > One thing I don't understand is the common > > (push `(progn (setq ...) t) cl--loop-body) > > pattern found in the code. I'm not sure why the `(progn ... t)` is > necessary. If anyone could explain that I'd add it as a comment. > > On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier > wrote: > >> > Avoid O(n^2) nconc-ing by keeping track of tail of collection. >> >> I took a quick look at your patch, and it looks pretty good. >> See comments below. >> >> >> Stefan >> >> >> > ((memq word '(collect collecting)) >> > - (let ((what (pop cl--loop-args)) >> > - (var (cl--loop-handle-accum nil 'nreverse))) >> > - (if (eq var cl--loop-accum-var) >> > - (push `(progn (push ,what ,var) t) cl--loop-body) >> > - (push `(progn >> > - (setq ,var (nconc ,var (list ,what))) >> > - t) >> > - cl--loop-body)))) >> > + (let ((what (pop cl--loop-args))) >> > + (cl-multiple-value-bind (var var-tail) >> >> `cl-multiple-value-bind` is the "destructor" corresponding to the >> `cl-values` "constructor". Since your code doesn't use `cl-values` it >> should not use `cl-multiple-value-bind` either (you probably meant to >> use cl-destructuring-bind instead). >> >> > + (cl--loop-handle-accum nil 'nreverse) >> > + (if (eq var cl--loop-accum-var) >> > + (push `(progn (push ,what ,var) t) cl--loop-body) >> > + (push `(progn >> > + (if (null ,var-tail) >> > + (setq ,var (list ,what) ,var-tail (last ,var= )) >> > + (setq ,var-tail (setcdr ,var-tail (list >> ,what)))) >> > + t) >> > + cl--loop-body))))) >> >> The cl-loop macro's code lacks comments. Could you take advantage of >> "being there" to try and add comments? E.g. in the above code I see >> that depending on (eq var cl--loop-accum-var) we end up accumulating in >> the from or in the back. Could you add a comments explaining why and >> mentioning where we correct this discrepancy? >> >> > + (let ((what (pop cl--loop-args))) >> > + (cl-destructuring-bind (var) (cl--loop-handle-accum nil 'nrevers= e) >> > + (push `(progn >> > + (setq ,var >> > + ,(if (eq var cl--loop-accum-var) >> > + `(nconc >> > + (,(if (memq word '(nconc nconcing)) >> > + #'nreverse #'reverse) >> > + ,what) >> > + ,var) >> > + `(,(if (memq word '(nconc nconcing)) >> > + #'nconc #'append) >> > + ,var ,what))) >> > + t) >> > + cl--loop-body)))) >> >> In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could >> also use the `var-tail` to speed up the `nconc`. >> >> Also, to avoid the N=C2=B2 behavior for the `append` case, maybe we >> could/should make it use `copy-sequence`, i.e. >> >> `(nconc ,var-tail (copy-sequence ,what)) >> >> > -(defun cl--loop-handle-accum (def &optional func) ; uses loop-* >> > - (if (eq (car cl--loop-args) 'into) >> > +(defun cl--loop-handle-accum (def &optional func type) ; uses loop-* >> > + (setq type (or type 'list)) >> >> Please add a docstring explaining whatever you managed to understand of >> this code, and describing also what this new arg `type` does. >> >> >> > --94eb2c199dc25bd996056960125e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Here's a second, cleaner attempt that separates the `c= l--loop-handle-accum` function into two functions, one to deal with lists a= nd one to deal w/ non-lists.

The tail-tracking optimizin= g is also applied to `append(ing)` and `nconc(ing)`.

On Sun, Apr 8, 2018 at 4:29= PM, Tianxiang Xiong <tianxiang.xiong@gmail.com> wro= te:
One thing I don'= t understand is the common=C2=A0
(push `(progn (setq= ...) t) cl--loop-body)

pattern found i= n the code. I'm not sure why the `(progn ... t)` is necessary. If anyon= e could explain that I'd add it as a comment.

On Sun, Apr 8, 2018 at 2:13 PM, Stefan Monnier &= lt;monnier@ir= o.umontreal.ca> wrote:
>= Avoid O(n^2) nconc-ing by keeping track of tail of collection.

I took a quick look at your patch, and it looks pretty good.
See comments below.


=C2=A0 =C2=A0 =C2=A0 =C2=A0 Stefan


>=C2=A0 =C2=A0 =C2=A0 =C2=A0((memq word '(collect collecting))
> -=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args))
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(var (cl--loop-handle-accum nil = 9;nreverse)))
> -=C2=A0 =C2=A0 =C2=A0(if (eq var cl--loop-accum-var)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(push `(progn (push ,what ,var) t) = cl--loop-body)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0(push `(progn
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= (setq ,var (nconc ,var (list ,what)))
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= t)
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--loop-body= ))))
> +=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args)))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 (cl-multiple-value-bind (var var-tail)
`cl-multiple-value-bind` is the "destructor" corresponding to the=
`cl-values` "constructor".=C2=A0 =C2=A0Since your code doesn'= t use `cl-values` it
should not use `cl-multiple-value-bind` either (you probably meant to
use cl-destructuring-bind instead).

> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (cl--loop-handle-accum nil = 'nreverse)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (if (eq var cl--loop-accum-var) > +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn (push = ,what ,var) t) cl--loop-body)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0(if (null ,var-tail)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0(setq ,var (list ,what) ,var-tail (last ,var))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0(setq ,var-tail (setcdr ,var-tail (list ,what))))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0t)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--lo= op-body)))))

The cl-loop macro's code lacks comments.=C2=A0 Could you take advantage= of
"being there" to try and add comments?=C2=A0 E.g. in the above co= de I see
that depending on (eq var cl--loop-accum-var) we end up accumulating in
the from or in the back.=C2=A0 Could you add a comments explaining why and<= br> mentioning where we correct this discrepancy?

> +=C2=A0 =C2=A0 =C2=A0 (let ((what (pop cl--loop-args)))
> +=C2=A0 =C2=A0 =C2=A0(cl-destructuring-bind (var) (cl--loop-handle-acc= um nil 'nreverse)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (push `(progn
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= (setq ,var
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0,(if (eq var cl--loop-accum-var)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 `(nconc
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (,(if (memq word '(nconc nco= ncing))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 #'nreve= rse #'reverse)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0,what)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ,var)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 `(,(if (memq word '(nconc nconcing))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0#'nconc #'a= ppend)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ,var ,what)))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= t)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cl--loop-body= ))))

In the `nconc` case (when (eq var cl--loop-accum-var) is nil) we could
also use the `var-tail` to speed up the `nconc`.

Also, to avoid the N=C2=B2 behavior for the `append` case, maybe we
could/should make it use `copy-sequence`, i.e.

=C2=A0 =C2=A0 `(nconc ,var-tail (copy-sequence ,what))

> -(defun cl--loop-handle-accum (def &optional func) ; uses loop-* > -=C2=A0 (if (eq (car cl--loop-args) 'into)
> +(defun cl--loop-handle-accum (def &optional func type) ; uses loo= p-*
> +=C2=A0 (setq type (or type 'list))

Please add a docstring explaining whatever you managed to understand of
this code, and describing also what this new arg `type` does.




--94eb2c199dc25bd996056960125e-- --94eb2c199dc25bd9980569601260 Content-Type: text/x-patch; charset="US-ASCII"; name="0002-Optimize-collect.into.patch" Content-Disposition: attachment; filename="0002-Optimize-collect.into.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_jfrjicxd0 RnJvbSAyZDkxZjdhZTk3NTU5NzYzNjM0NjBlNThkNjQ3ZTc4MjZkYjNlNTQ5IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBUaWFueGlhbmcgWGlvbmcgPHRpYW54aWFuZy54aW9uZ0BnbWFp bC5jb20+CkRhdGU6IFN1biwgOCBBcHIgMjAxOCAxMjozNjo0MSAtMDcwMApTdWJqZWN0OiBbUEFU Q0hdIE9wdGltaXplIGBjb2xsZWN0Li4uaW50b2AKCkF2b2lkIE8obl4yKSBuY29uYy1pbmcgYnkg a2VlcGluZyB0cmFjayBvZiB0YWlsIG9mIGNvbGxlY3Rpb24uCi0tLQogbGlzcC9lbWFjcy1saXNw L2NsLW1hY3MuZWwgfCAxMTUgKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0t LS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgNzcgaW5zZXJ0aW9ucygrKSwgMzggZGVsZXRpb25zKC0p CgpkaWZmIC0tZ2l0IGEvbGlzcC9lbWFjcy1saXNwL2NsLW1hY3MuZWwgYi9saXNwL2VtYWNzLWxp c3AvY2wtbWFjcy5lbAppbmRleCA5NjAwMjMwYzA3Li40N2E1NDEzZjQ5IDEwMDY0NAotLS0gYS9s aXNwL2VtYWNzLWxpc3AvY2wtbWFjcy5lbAorKysgYi9saXNwL2VtYWNzLWxpc3AvY2wtbWFjcy5l bApAQCAtMTUzNywzMSArMTUzNywzNCBAQCBjbC0tcGFyc2UtbG9vcC1jbGF1c2UKIAkocHVzaCBg KD49IChzZXRxICx0ZW1wICgxLSAsdGVtcCkpIDApIGNsLS1sb29wLWJvZHkpKSkKIAogICAgICAo KG1lbXEgd29yZCAnKGNvbGxlY3QgY29sbGVjdGluZykpCi0gICAgICAobGV0ICgod2hhdCAocG9w IGNsLS1sb29wLWFyZ3MpKQotCSAgICAodmFyIChjbC0tbG9vcC1oYW5kbGUtYWNjdW0gbmlsICdu cmV2ZXJzZSkpKQotCShpZiAoZXEgdmFyIGNsLS1sb29wLWFjY3VtLXZhcikKLQkgICAgKHB1c2gg YChwcm9nbiAocHVzaCAsd2hhdCAsdmFyKSB0KSBjbC0tbG9vcC1ib2R5KQotCSAgKHB1c2ggYChw cm9nbgotICAgICAgICAgICAgICAgICAgIChzZXRxICx2YXIgKG5jb25jICx2YXIgKGxpc3QgLHdo YXQpKSkKKyAgICAgIChsZXQgKCh3aGF0IChwb3AgY2wtLWxvb3AtYXJncykpKQorICAgICAgICAo Y2wtZGVzdHJ1Y3R1cmluZy1iaW5kICh2YXIgdmFyLXRhaWwpIChjbC0tbG9vcC1oYW5kbGUtbGlz dC1hY2N1bSBuaWwpCisgICAgICAgICAgKHB1c2ggYChwcm9nbgorICAgICAgICAgICAgICAgICAg IChpZiAobnVsbCAsdmFyLXRhaWwpCisgICAgICAgICAgICAgICAgICAgICAgIChzZXRxICx2YXIg KGxpc3QgLHdoYXQpICx2YXItdGFpbCAobGFzdCAsdmFyKSkKKyAgICAgICAgICAgICAgICAgICAg IChzZXRxICx2YXItdGFpbCAoc2V0Y2RyICx2YXItdGFpbCAobGlzdCAsd2hhdCkpKSkKICAgICAg ICAgICAgICAgICAgICB0KQogICAgICAgICAgICAgICAgIGNsLS1sb29wLWJvZHkpKSkpCiAKLSAg ICAgKChtZW1xIHdvcmQgJyhuY29uYyBuY29uY2luZyBhcHBlbmQgYXBwZW5kaW5nKSkKLSAgICAg IChsZXQgKCh3aGF0IChwb3AgY2wtLWxvb3AtYXJncykpCi0JICAgICh2YXIgKGNsLS1sb29wLWhh bmRsZS1hY2N1bSBuaWwgJ25yZXZlcnNlKSkpCi0JKHB1c2ggYChwcm9nbgotICAgICAgICAgICAg ICAgICAoc2V0cSAsdmFyCi0gICAgICAgICAgICAgICAgICAgICAgICwoaWYgKGVxIHZhciBjbC0t bG9vcC1hY2N1bS12YXIpCi0gICAgICAgICAgICAgICAgICAgICAgICAgICAgYChuY29uYwotICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgKCwoaWYgKG1lbXEgd29yZCAnKG5jb25jIG5jb25j aW5nKSkKLSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMnbnJldmVyc2UgIydy ZXZlcnNlKQotICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICx3aGF0KQotICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgLHZhcikKLSAgICAgICAgICAgICAgICAgICAgICAgICAgYCgs KGlmIChtZW1xIHdvcmQgJyhuY29uYyBuY29uY2luZykpCi0gICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAjJ25jb25jICMnYXBwZW5kKQotICAgICAgICAgICAgICAgICAgICAgICAgICAg ICx2YXIgLHdoYXQpKSkKLSAgICAgICAgICAgICAgICAgdCkKLSAgICAgICAgICAgICAgY2wtLWxv b3AtYm9keSkpKQorICAgICAoKG1lbXEgd29yZCAnKGFwcGVuZCBhcHBlbmRpbmcpKQorICAgICAg KGxldCAoKHdoYXQgKHBvcCBjbC0tbG9vcC1hcmdzKSkpCisgICAgICAgIChjbC1kZXN0cnVjdHVy aW5nLWJpbmQgKHZhciB2YXItdGFpbCkgKGNsLS1sb29wLWhhbmRsZS1saXN0LWFjY3VtIG5pbCkK KyAgICAgICAgICAocHVzaCBgKHByb2duCisgICAgICAgICAgICAgICAgICAgKGlmIChudWxsICx2 YXItdGFpbCkKKyAgICAgICAgICAgICAgICAgICAgICAgKHNldHEgLHZhciAoY29weS1zZXF1ZW5j ZSAsd2hhdCkgLHZhci10YWlsIChsYXN0ICx2YXIpKQorICAgICAgICAgICAgICAgICAgICAgKHNl dHEgLHZhci10YWlsIChzZXRjZHIgLHZhci10YWlsIChjb3B5LXNlcXVlbmNlICx3aGF0KSkpKQor ICAgICAgICAgICAgICAgICAgIHQpCisgICAgICAgICAgICAgICAgY2wtLWxvb3AtYm9keSkpKSkK KworICAgICAoKG1lbXEgd29yZCAnKG5jb25jIG5jb25jaW5nKSkKKyAgICAgIChsZXQgKCh3aGF0 IChwb3AgY2wtLWxvb3AtYXJncykpKQorICAgICAgICAoY2wtZGVzdHJ1Y3R1cmluZy1iaW5kICh2 YXIgdmFyLXRhaWwpIChjbC0tbG9vcC1oYW5kbGUtbGlzdC1hY2N1bSBuaWwpCisgICAgICAgICAg KHB1c2ggYChwcm9nbgorICAgICAgICAgICAgICAgICAgIChpZiAobnVsbCAsdmFyLXRhaWwpCisg ICAgICAgICAgICAgICAgICAgICAgIChzZXRxICx2YXIgLHdoYXQgLHZhci10YWlsIChsYXN0ICx2 YXIpKQorICAgICAgICAgICAgICAgICAgICAgKHNldHEgLHZhci10YWlsIChzZXRjZHIgLHZhci10 YWlsICx3aGF0KSkpCisgICAgICAgICAgICAgICAgICAgdCkKKyAgICAgICAgICAgICAgICBjbC0t bG9vcC1ib2R5KSkpKQogCiAgICAgICgobWVtcSB3b3JkICcoY29uY2F0IGNvbmNhdGluZykpCiAg ICAgICAobGV0ICgod2hhdCAocG9wIGNsLS1sb29wLWFyZ3MpKQpAQCAtMTcyNiwyMiArMTcyOSw1 OCBAQCBjbC0tbG9vcC1sZXQKICAgICAgIGAoLChpZiBwYXIgJ2xldCAnbGV0KikKICAgICAgICAg LChuY29uYyAobnJldmVyc2UgdGVtcHMpIChucmV2ZXJzZSBuZXcpKSAsQGJvZHkpKSkpCiAKLShk ZWZ1biBjbC0tbG9vcC1oYW5kbGUtYWNjdW0gKGRlZiAmb3B0aW9uYWwgZnVuYykgOyB1c2VzIGxv b3AtKgotICAoaWYgKGVxIChjYXIgY2wtLWxvb3AtYXJncykgJ2ludG8pCi0gICAgICAobGV0ICgo dmFyIChjbC0tcG9wMiBjbC0tbG9vcC1hcmdzKSkpCi0JKG9yIChtZW1xIHZhciBjbC0tbG9vcC1h Y2N1bS12YXJzKQotCSAgICAocHJvZ24gKHB1c2ggKGxpc3QgKGxpc3QgdmFyIGRlZikpIGNsLS1s b29wLWJpbmRpbmdzKQotCQkgICAocHVzaCB2YXIgY2wtLWxvb3AtYWNjdW0tdmFycykpKQotCXZh cikKLSAgICAob3IgY2wtLWxvb3AtYWNjdW0tdmFyCi0JKHByb2duCi0JICAocHVzaCAobGlzdCAo bGlzdAotICAgICAgICAgICAgICAgICAgICAgICAoc2V0cSBjbC0tbG9vcC1hY2N1bS12YXIgKG1h a2Utc3ltYm9sICItLWNsLXZhci0tIikpCi0gICAgICAgICAgICAgICAgICAgICAgIGRlZikpCi0g ICAgICAgICAgICAgICAgY2wtLWxvb3AtYmluZGluZ3MpCi0JICAoc2V0cSBjbC0tbG9vcC1yZXN1 bHQgKGlmIGZ1bmMgKGxpc3QgZnVuYyBjbC0tbG9vcC1hY2N1bS12YXIpCi0gICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgY2wtLWxvb3AtYWNjdW0tdmFyKSkKLQkgIGNsLS1sb29wLWFj Y3VtLXZhcikpKSkKKyhkZWZ1biBjbC0tbG9vcC1oYW5kbGUtbGlzdC1hY2N1bSAoZGVmKQorICAi SGFuZGxlIGxpc3QgdmFsdWUgYWNjdW11bGF0aW9uIGNsYXVzZS4KKworREVGIGlzIHRoZSBpbml0 aWFsIHZhbHVlIG9mIHRoZSBhY2N1bXVsYXRpb24gdmFyaWFibGUuCisKK1JldHVybnMgKFZBUiBW QVItVEFJTCksIHdoZXJlIFZBUiBpcyB0aGUgYWNjdW11bGF0aW9uIHZhcmlhYmxlCithbmQgVkFS LVRBSUwgaXMgdGhlIHRhaWwgb2YgdGhlIGFjY3VtdWxhdG9yLiIKKyAgKGNsLWZsZXQgKCh0YWls LXN5bWJvbCAodmFyKQorICAgICAgICAgICAgICAoZ2Vuc3ltIChjb25jYXQgKHN5bWJvbC1uYW1l IHZhcikgIi10YWlsLSIpKSkpCisgICAgKGNvbmQKKyAgICAgICgoZXEgKGNhciBjbC0tbG9vcC1h cmdzKSAnaW50bykKKyAgICAgICAobGV0KiAoKHZhciAoY2wtLXBvcDIgY2wtLWxvb3AtYXJncykp CisgICAgICAgICAgICAgICh2YXItdGFpbCAodGFpbC1zeW1ib2wgdmFyKSkpCisgICAgICAgICAo aWYgKG1lbXEgdmFyIGNsLS1sb29wLWFjY3VtLXZhcnMpCisgICAgICAgICAgICAgKHB1c2ggYCgo LHZhci10YWlsICwobGFzdCBkZWYpKSkgY2wtLWxvb3AtYmluZGluZ3MpCisgICAgICAgICAgIChw dXNoIGAoKCx2YXIgLGRlZikpIGNsLS1sb29wLWJpbmRpbmdzKQorICAgICAgICAgICAocHVzaCBg KCgsdmFyLXRhaWwgLChsYXN0IGRlZikpKSBjbC0tbG9vcC1iaW5kaW5ncykKKyAgICAgICAgICAg KHB1c2ggdmFyIGNsLS1sb29wLWFjY3VtLXZhcnMpKQorICAgICAgICAgKGxpc3QgdmFyIHZhci10 YWlsKSkpCisKKyAgICAgIChjbC0tbG9vcC1hY2N1bS12YXIKKyAgICAgICBgKCxjbC0tbG9vcC1h Y2N1bS12YXIgLCh0YWlsLXN5bWJvbCBjbC0tbG9vcC1hY2N1bS12YXIpKSkKKworICAgICAgKHQg KGxldCogKCh2YXIgKG1ha2Utc3ltYm9sICItLWNsLXZhci0tIikpCisgICAgICAgICAgICAgICAg KHZhci10YWlsICh0YWlsLXN5bWJvbCB2YXIpKSkKKyAgICAgICAgICAgKHB1c2ggYCgoLHZhciAs ZGVmKSkgY2wtLWxvb3AtYmluZGluZ3MpCisgICAgICAgICAgIChwdXNoIGAoKCx2YXItdGFpbCAs KGxhc3QgZGVmKSkpIGNsLS1sb29wLWJpbmRpbmdzKQorICAgICAgICAgICAoc2V0cSBjbC0tbG9v cC1hY2N1bS12YXIgdmFyCisgICAgICAgICAgICAgICAgIGNsLS1sb29wLXJlc3VsdCB2YXIpCisg ICAgICAgICAgIChsaXN0IHZhciB2YXItdGFpbCkpKSkpKQorCisoZGVmdW4gY2wtLWxvb3AtaGFu ZGxlLWFjY3VtIChkZWYpCisgICJIYW5kbGUgbm9uLWxpc3QgdmFsdWUgYWNjdW11bGF0aW9uIGNs YXVzZS4KKworREVGIGlzIHRoZSBpbml0aWFsIHZhbHVlIG9mIHRoZSBhY2N1bXVsYXRpb24gdmFy aWFibGUuCisKK1JldHVybnMgdGhlIGFjY3VtdWxhdGlvbiB2YXJpYWJsZSBWQVIuIgorICAoY29u ZAorICAgICgoZXEgKGNhciBjbC0tbG9vcC1hcmdzKSAnaW50bykKKyAgICAgKGxldCogKCh2YXIg KGNsLS1wb3AyIGNsLS1sb29wLWFyZ3MpKSkKKyAgICAgICAodW5sZXNzIChtZW1xIHZhciBjbC0t bG9vcC1hY2N1bS12YXJzKQorICAgICAgICAgKHB1c2ggYCgoLHZhciAsZGVmKSkgY2wtLWxvb3At YmluZGluZ3MpCisgICAgICAgICAocHVzaCB2YXIgY2wtLWxvb3AtYWNjdW0tdmFycykpCisgICAg ICAgdmFyKSkKKworICAgIChjbC0tbG9vcC1hY2N1bS12YXIgY2wtLWxvb3AtYWNjdW0tdmFyKQor CisgICAgKHQgKGxldCogKCh2YXIgKG1ha2Utc3ltYm9sICItLWNsLXZhci0tIikpKQorICAgICAg ICAgKHB1c2ggYCgoLHZhciAsZGVmKSkgY2wtLWxvb3AtYmluZGluZ3MpCisgICAgICAgICAoc2V0 cSBjbC0tbG9vcC1hY2N1bS12YXIgdmFyCisgICAgICAgICAgICAgICBjbC0tbG9vcC1yZXN1bHQg dmFyKQorICAgICAgICAgdmFyKSkpKQogCiAoZGVmdW4gY2wtLWxvb3AtYnVpbGQtYW5kcyAoY2xh dXNlcykKICAgIlJldHVybiB2YXJpb3VzIHJlcHJlc2VudGF0aW9ucyBvZiAoYW5kIC4gQ0xBVVNF UykuCi0tIAoyLjE0LjMKCg== --94eb2c199dc25bd9980569601260--