From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Tobias Zawada Newsgroups: gmane.emacs.bugs Subject: bug#26629: 25.1.50; Feature-request: Structure-preserving copying of sequences Date: Mon, 24 Apr 2017 00:02:25 +0200 Message-ID: <874lxepytq.fsf@smtp.1und1.de> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1492987032 30992 195.159.176.226 (23 Apr 2017 22:37:12 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 23 Apr 2017 22:37:12 +0000 (UTC) To: 26629@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Apr 24 00:37:07 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1d2Q7u-0007yJ-5Y for geb-bug-gnu-emacs@m.gmane.org; Mon, 24 Apr 2017 00:37:06 +0200 Original-Received: from localhost ([::1]:40818 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d2Q80-0007uY-38 for geb-bug-gnu-emacs@m.gmane.org; Sun, 23 Apr 2017 18:37:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:53916) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d2Q7t-0007uF-A2 for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:37:06 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d2Q7q-0006n3-61 for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:37:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:38684) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1d2Q7q-0006mz-2D for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:37:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1d2Q7p-0000CA-Q5 for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:37:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Tobias Zawada Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 23 Apr 2017 22:37:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 26629 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.1492986985664 (code B ref -1); Sun, 23 Apr 2017 22:37:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 23 Apr 2017 22:36:25 +0000 Original-Received: from localhost ([127.0.0.1]:36883 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d2Q7F-0000Ac-0u for submit@debbugs.gnu.org; Sun, 23 Apr 2017 18:36:25 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:57511) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d2Pav-0007DF-GN for submit@debbugs.gnu.org; Sun, 23 Apr 2017 18:03:02 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d2Pap-0006EQ-1n for submit@debbugs.gnu.org; Sun, 23 Apr 2017 18:02:56 -0400 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:33468) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1d2Pao-0006EH-Up for submit@debbugs.gnu.org; Sun, 23 Apr 2017 18:02:54 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48471) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d2Pan-0003Os-Fe for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:02:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d2Pai-0006DO-Hh for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:02:53 -0400 Original-Received: from mout.kundenserver.de ([217.72.192.75]:56561) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1d2Pai-0006Cw-6i for bug-gnu-emacs@gnu.org; Sun, 23 Apr 2017 18:02:48 -0400 Original-Received: from elmo ([178.5.191.199]) by mrelayeu.kundenserver.de (mreue101 [212.227.15.183]) with ESMTPSA (Nemesis) id 0M4qlR-1c3rxO1akn-00z0Cl for ; Mon, 24 Apr 2017 00:02:44 +0200 X-Provags-ID: V03:K0:QxQVOKE53m0lYwyswgdd0VimB8KAmqkvyL8fuCu9qh0eO1vZ3mK 19M762NOd4hT5GqJZfPoixezFA8JwJzM/XEo+TzGQ+PIpnRMGlDKn4RcIpD1Qy7S038wUNF bjZ+UZv3Q75HSDTP+7IS1gfE7jevO6cYzI6+dDJ/Zq6lMLHe6ZRW/9cSF+FLk7ZidabhhNC MltdDSgYnNCJWEnSXuhEw== X-UI-Out-Filterresults: notjunk:1;V01:K0:Lh2M1vfD0hY=:fV1TRTJ2zulhvyFox81nzj VS7G7RKoZvayeN9/ZdqdY7grUSSQlQiCd2L2q9Vcuk2QQY2NR1qHwBN80W1A4jpAzLvJOPzKL a04DV3jJshsrN6Q+3zygsVlxi5/ImhdVmefgEnE2/sijPFb7Z9M6LUtv8sCywz4p/nzZyQFHF JF5F2jzwTq82o9lup3V7Mj+JoMNgMIEWKnhoJ6CMYKQNhNK2U8W3CSAefoYPnHOtJamAJtVtP +l3vEf9G2pzfJaZX579MX6QuANj8VcTzGXLtKJ/uVDXPr8uHxkCb4Mune4LbDnHCJj0ooJe3E ykbMisYIHrQ8pqDNvgpgu3bTYxyBC+Tpz7SRB89uH/sGDs7P68OXhkP6n0Wc5TlpV0DEGvGvb zN9OEtVJdS1o8qCADd5vCvGj7ph00CJAS17QuffNKEiVSiRgoPnSNCWCHchgLzk9bu3IS5WCZ P9nU/lMfODNwUB7fDrVMz69FXxNgYzk0p/yD0RcdrEsybJV7vDn0eZReT8yMK82uWE+/9b7RO 7gyWh/me0qtXcOD367AAnjRH2sEove3ZlrOESVSAyBeqWOCEnGuVfcA6nuht18jcunQxyuhul PayAYNx725hJayhzzPFZTWaqOs8O4Wj0XbyG5F3iKSUHywpeDYiqCDiUa1REbpe2YJt0ivlds HAxvpKEtst0EIK6MfM+rLnF/KEg847FGpaisgAYegXjAb1F2jv039U/8MWWKLmM8+c1lRovl5 SmBMqjQjsBorwTVN X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Mailman-Approved-At: Sun, 23 Apr 2017 18:36:23 -0400 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:131919 Archived-At: Dear emacs maintainers, I propose to implement a structure-preserving version of copy-tree in emacs. It could be part of one of the elisp libraries (e.g., seq.el or subr.el) or it could be an internal function. An example implementation is cited at the end of this mail. The function copy-tree copies recursively but not structure preserving. If two cars or cdrs link to the same sub-list in the original data they point to two separate sub-lists in the copy. As mentioned in the Common Lisp Hyper Spec (http://clhs.lisp.se/Body/f_cp_tre.htm) this is the intended behavior of copy-tree. I needed a structure-preserving copy of a graph for the solution of the request https://emacs.stackexchange.com/questions/32194/undo-tree-history-file-without-text-properties So I wrote my own version of copy-tree* and asked at https://emacs.stackexchange.com/questions/32316/structure-preserving-copying-of-sequences whether anyone knows some built-in version for that purpose. Drew responded that he does not know about any such function and recommended to write this feature request. For making this request self-contained I cite in the following my version of copy-tree*. Feel free to use it or parts of it for emacs if you like. There are no license-restrictions on the code. About the code: Traversing of the original graph and construction of the new graph are stack-based as it is standard. There is an additional hash-map that maps the already traversed old nodes to the newly created ones. If some old node is already in the hash-map we do not create a new one in the copied graph but use the mapped one from the hash map. I chose the name `copy-tree*' because of the similarity of the function to `copy-tree'. Considering the functionality maybe the name `copy-graph' would be more appropriate. (cl-defstruct (copy-tree* (:constructor copy-tree*-mem (&optional stack stack-new (hash (make-hash-table))))) stack stack-new hash) (defmacro copy-tree*--push (el el-new mem &optional hash) "Put EL onto the stack and EL-NEW onto stack-new in the `copy-tree*' structure MEM. Add a key-value pair mapping EL to EL-NEW in the hash map of mem." (let ((my-el (make-symbol "my-el")) (my-el-new (make-symbol "my-el-new"))) ; makes sure `el' is only evaluated once (append `(let ((,my-el ,el) (,my-el-new ,el-new)) (push ,my-el (copy-tree*-stack ,mem)) (push ,my-el-new (copy-tree*-stack-new ,mem))) (and hash `((puthash ,my-el ,my-el-new (copy-tree*-hash ,mem)))) (list my-el-new)))) (defmacro copy-tree*--pop (el el-new mem) `(setq ,el (pop (copy-tree*-stack ,mem)) ,el-new (pop (copy-tree*-stack-new mem)))) (defun copy-tree*--copy-node (node mem vecp) "If NODE is not a `cons' just return it. Create a new copy of NODE if NODE is a `cons' not already contained in the hash map of mem (a `copy-tree*' structure). Register NODE and its copy as key-value pair in the hash table. If NODE is already a key of the hash map return its copy. With non-nil VECP vectors are treated analogously to conses." (if (or (consp node) (and vecp (vectorp node))) (let ((existing-node (gethash node (copy-tree*-hash mem)))) (if existing-node existing-node (copy-tree*--push node (if (consp node) (cons nil nil) (make-vector (length node) nil)) mem t))) node)) (defun copy-tree* (tree &optional vecp) "Structure preserving version of `cl-copy-tree'." (if (or (consp tree) (and vecp (vectorp tree))) (let* ((tree-new (if (consp tree) (cons nil nil) (make-vector (length tree) nil))) (mem (copy-tree*-mem)) next next-new) (copy-tree*--push tree tree-new mem t) (while (copy-tree*--pop next next-new mem) (cond ((consp next) (setcar next-new (copy-tree*--copy-node (car next) mem vecp)) (setcdr next-new (copy-tree*--copy-node (cdr next) mem vecp))) ((and vecp (vectorp next)) (cl-loop for i from 0 below (length next) do (aset next-new i (copy-tree*--copy-node (aref next i) mem vecp)))))) tree-new) tree)) Best regards, Tobias Zawada