5

The form (cl-copy-tree TREE t) returns a deep-copy of a sequence TREE. The the Common Lisp Hyper Spec explains that copy-tree does not preserve circularities and sharing of substructures. I.e., even if copy-tree delivers a deep copy it is not structure-preserving.

Is there a structure-preserving version of tree-copy in the elisp library shipped with emacs or even built-in?

The following example demonstrates the structural difference between the argument and the result of copy-tree.

(let* (ret
       (print-circle t)
       (l '((1 2) (3)))
       (c (progn 
            (setcdr (nth 1 l) (car l))
            (cl-copy-tree l))))
  (setq ret (format "l: %S\nc: %S\n" l c))
  (setcar (car l) 4)
  (setcar (car c) 4)
  (setq print-circle nil)
  (concat ret (format "Effect of the structural difference:\nl: %S\nc: %S\n" l c))
  )

Evaluation of this form delivers:

l: (#1=(1 2) (3 . #1#))
c: ((1 2) (3 1 2))
Effect of the structural difference:
l: ((4 2) (3 4 2))
c: ((4 2) (3 1 2))

The following code shows that a library implementation of a structure-preserving version of copy-tree would be possible. I needed it already for an answer related to undo-tree.

(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))

The following example is a modified version of the first example. The only modification is that cl-copy-tree is replaced by copy-tree*.

(let* (ret
       (print-circle t)
       (l '((1 2) (3)))
       (c (progn 
            (setcdr (nth 1 l) (car l))
            (copy-tree* l))))
  (setq ret (format "l: %S\nc: %S\n" l c))
  (setcar (car l) 4)
  (setcar (car c) 4)
  (setq print-circle nil)
  (concat ret (format "Effect of the structural difference:\nl: %S\nc: %S\n" l c))
  )

The output of this form demonstrates that copy-tree* produces a structure-preserving copy of its argument.

l: (#1=(1 2) (3 . #1#))
c: (#1=(1 2) (3 . #1#))
Effect of the structural difference:
l: ((4 2) (3 4 2))
c: ((4 2) (3 4 2))
  • 1
    There is none that I'm aware of. You might consider proposing to add such a function (M-x report-emacs-bug). – Drew Apr 23 '17 at 2:06
  • "I needed it already for an answer related to undo-tree." - For that particular thing, I suggest instead co-operating with undo-tree's author to get some hooks added: github.com/joaotavora/yasnippet/issues/… – npostavs Apr 23 '17 at 22:22
  • @Drew I followed your suggestion and wrote a feature request. Best regards, – Tobias Apr 23 '17 at 22:39
  • Yes, I saw it. I'm sure it will get the attention it deserves. – Drew Apr 23 '17 at 22:47
  • @npostavs copy-tree* above is not so special to undo-tree. It acts very much like copy-tree but is structure-preserving. It has also an maybe important advantage over copy-tree beside that it is structure-preserving. The copy produced by copy-tree* can be smaller than that one produced by copy-tree because copy-tree* reuses common substructures in the same way as the original data does. In some cases this may save algorithmic costs in spite of the fact that a single step of copy-tree* is more expensive. – Tobias Apr 23 '17 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.