[ELPA] New package: hierarchy

[ELPA] New package: hierarchy

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 1911 bytes --]

Hi,

I would like to add my package 'hierarchy', a library to create and
display hierarchy structures, to ELPA. The hierarchy library has already
been used to implement a json navigator and a Javascript class hierarchy
navigator.

I wrote a blog post describing it on Nicolas' blog:
https://emacs.cafe/emacs/guest-post/2017/06/26/hierarchy.html.

My motivation for proposing this library to ELPA (instead of MELPA where
all my other packages are published) is that some developers might want
to have their hierarchy-dependent package on ELPA. Also, phil-s asked me
to do it: https://github.com/DamienCassou/hierarchy/issues/48.

I propose to put the single-file package hierarchy.el in ELPA and to
keep maintaining the project in a separate repository. I decided to
avoid using subtree or externals because my unit-test file (which is not
included here) depends on buttercup which is not on ELPA.

Longer description:

Creation: After having created a hierarchy with `hierarchy-new',
populate it by calling `hierarchy-add-tree' or `hierarchy-add-trees'.
You can then optionally sort its element with `hierarchy-sort'.

Querying: You can learn more about your hierarchy by using functions
such as `hierarchy-roots', `hierarchy-has-item', `hierarchy-length',
`hierarchy-parent', `hierarchy-descendant-p'.

Navigation: When your hierarchy is ready, you can use `hierarchy-map-item', `hierarchy-map',
and `map-tree' to apply functions to elements of the hierarchy.

Display: You can display a hierarchy as a tabulated list using
`hierarchy-tabulated-display' and as an expandable/foldable tree
using `hierarchy-convert-to-tree-widget'.  The
`hierarchy-labelfn-*' functions will help you display each item of
the hierarchy the way you want it.

Best,


-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

[-- Attachment #2: hierarchy.el --]
[-- Type: text/plain, Size: 22635 bytes --]

;;; hierarchy.el --- Library to create and display hierarchy structures  -*- lexical-binding: t; -*-

;; Copyright (C) 2017 Damien Cassou

;; Author: Damien Cassou <damien@cassou.me>
;; Maintainer: Damien Cassou <damien@cassou.me>
;; Version: 0.7.0
;; Package-Requires: ((emacs "25.1"))
;; GIT: https://github.com/DamienCassou/hierarchy
;; URL: https://github.com/DamienCassou/hierarchy
;;
;; This file is not part of GNU Emacs.

;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

;;; Commentary:

;; Library to create, query, navigate and display hierarchy structures.

;; Creation: After having created a hierarchy with `hierarchy-new', populate it by
;; calling `hierarchy-add-tree' or `hierarchy-add-trees'.  You can then optionally sort its
;; element with `hierarchy-sort'.

;; Querying: You can learn more about your hierarchy by using functions such as
;; `hierarchy-roots', `hierarchy-has-item', `hierarchy-length', `hierarchy-parent', `hierarchy-descendant-p'.

;; Navigation: When your hierarchy is ready, you can use `hierarchy-map-item', `hierarchy-map',
;; and `map-tree' to apply functions to elements of the hierarchy.

;; Display: You can display a hierarchy as a tabulated list using
;; `hierarchy-tabulated-display' and as an expandable/foldable tree
;; using `hierarchy-convert-to-tree-widget'.  The
;; `hierarchy-labelfn-*' functions will help you display each item of
;; the hierarchy the way you want it.

;;; Limitation:

;; Current implementation uses #'equal to find and distinguish elements. Support
;; for user-provided equality definition is desired but not yet implemented.

;;; Code:

(require 'seq)
(require 'map)
(require 'subr-x)

\f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Helpers
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(cl-defstruct (hierarchy
               (:constructor hierarchy--make)
               (:conc-name hierarchy--))
  (roots (list)) ; list of the hierarchy roots (no parent)
  (parents (make-hash-table :test 'equal)) ; map an item to its parent
  (children (make-hash-table :test 'equal)) ; map an item to its childre
  ;; cache containing the set of all items in the hierarchy
  (seen-items (make-hash-table :test 'equal)))  ; map an item to t

(defun hierarchy--seen-items-add (hierarchy item)
  "In HIERARCHY, add ITEM to seen items."
  (map-put (hierarchy--seen-items hierarchy) item t))

(defun hierarchy--compute-roots (hierarchy)
  "Search roots of HIERARCHY and return them."
  (cl-set-difference
   (map-keys (hierarchy--seen-items hierarchy))
   (map-keys (hierarchy--parents hierarchy))
   :test #'equal))

(defun hierarchy--sort-roots (hierarchy sortfn)
  "Compute, sort and store the roots of HIERARCHY.

SORTFN is a function taking two items of the hierarchy as parameter and
returning non-nil if the first parameter is lower than the second."
  (setf (hierarchy--roots hierarchy)
        (sort (hierarchy--compute-roots hierarchy)
              sortfn)))

(defun hierarchy--add-relation (hierarchy item parent acceptfn)
  "In HIERARCHY, add ITEM as child of PARENT.

ACCEPTFN is a function returning non-nil if its parameter (any object)
should be an item of the hierarchy."
  (let* ((existing-parent (hierarchy-parent hierarchy item))
         (has-parent-p (funcall acceptfn existing-parent)))
    (cond
     ((and has-parent-p (not (equal existing-parent parent)))
      (error "An item (%s) can only have one parent: '%s' vs '%s'"
             item existing-parent parent))
     ((not has-parent-p)
      (push item (map-elt (hierarchy--children hierarchy) parent (list)))
      (map-put (hierarchy--parents hierarchy) item parent)))))

(defun hierarchy--set-equal (list1 list2 &rest cl-keys)
  "Return non-nil if LIST1 and LIST2 have same elements.

I.e., if every element of LIST1 also appears in LIST2 and if
every element of LIST2 also appears in LIST1.

CL-KEYS are key-value pairs just like in `cl-subsetp'.  Supported
keys are :key and :test."
  (and (apply 'cl-subsetp list1 list2 cl-keys)
       (apply 'cl-subsetp list2 list1 cl-keys)))

\f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Creation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun hierarchy-new ()
  "Create a hierarchy and return it."
  (hierarchy--make))

(defun hierarchy-add-tree (hierarchy item parentfn &optional childrenfn acceptfn)
  "In HIERARCHY, add ITEM.

PARENTFN is either nil or a function defining the child-to-parent
relationship: this function takes an item as parameter and should return
the parent of this item in the hierarchy.  If the item has no parent in the
hierarchy (i.e., it should be a root), the function should return an object
not accepted by acceptfn (i.e., nil for the default value of acceptfn).

CHILDRENFN is either nil or a function defining the parent-to-children
relationship: this function takes an item as parameter and should return a
list of children of this item in the hierarchy.

If both PARENTFN and CHILDRENFN are non-nil, the results of PARENTFN and
CHILDRENFN are expected to be coherent with each other.

ACCEPTFN is a function returning non-nil if its parameter (any object)
should be an item of the hierarchy.  By default, ACCEPTFN returns non-nil
if its parameter is non-nil."
  (unless (hierarchy-has-item hierarchy item)
    (let ((acceptfn (or acceptfn #'identity)))
      (hierarchy--seen-items-add hierarchy item)
      (let ((parent (and parentfn (funcall parentfn item))))
        (when (funcall acceptfn parent)
          (hierarchy--add-relation hierarchy item parent acceptfn)
          (hierarchy-add-tree hierarchy parent parentfn childrenfn)))
      (let ((children (and childrenfn (funcall childrenfn item))))
        (mapc (lambda (child)
                (when (funcall acceptfn child)
                  (hierarchy--add-relation hierarchy child item acceptfn)
                  (hierarchy-add-tree hierarchy child parentfn childrenfn)))
              children)))))

(defun hierarchy-add-trees (hierarchy items parentfn &optional childrenfn acceptfn)
  "Call `hierarchy-add-tree' on HIERARCHY and each element of ITEMS.

PARENTFN, CHILDRENFN and ACCEPTFN have the same meaning as in `hierarchy-add'."
  (seq-map (lambda (item)
             (hierarchy-add-tree hierarchy item parentfn childrenfn acceptfn))
           items))

(defun hierarchy-add-list (hierarchy list &optional wrap childrenfn)
  "Add to HIERARCHY the sub-lists in LIST.

If WRAP is non-nil, allow duplicate items in LIST by wraping each
item in a cons (id . item).  The root's id is 1.

CHILDRENFN is a function (defaults to `cdr') taking LIST as a
parameter which should return LIST's children (a list).  Each
child is (recursively) passed as a parameter to CHILDRENFN to get
its own children.  Because of this parameter, LIST can be
anything, not necessarily a list."
  (let* ((childrenfn (or childrenfn #'cdr))
         (id 0)
         (wrapfn (lambda (item)
                   (if wrap
                       (cons (setq id (1+ id)) item)
                     item)))
         (unwrapfn (if wrap #'cdr #'identity)))
    (hierarchy-add-tree
     hierarchy (funcall wrapfn list) nil
     (lambda (item)
       (mapcar wrapfn (funcall childrenfn
                               (funcall unwrapfn item)))))
    hierarchy))

(defun hierarchy-from-list (list &optional wrap childrenfn)
  "Create and return a hierarchy built from LIST.

This function passes LIST, WRAP and CHILDRENFN unchanged to
`hierarchy-add-list'."
  (hierarchy-add-list (hierarchy-new) list wrap childrenfn))

(defun hierarchy-sort (hierarchy &optional sortfn)
  "Modify HIERARCHY so that its roots and item's children are sorted.

SORTFN is a function taking two items of the hierarchy as parameter and
returning non-nil if the first parameter is lower than the second.  By
default, SORTFN is `string-lessp'."
  (let ((sortfn (or sortfn #'string-lessp)))
    (hierarchy--sort-roots hierarchy sortfn)
    (mapc (lambda (parent)
            (setf
             (map-elt (hierarchy--children hierarchy) parent)
             (sort (map-elt (hierarchy--children hierarchy) parent) sortfn)))
          (map-keys (hierarchy--children hierarchy)))))

(defun hierarchy-extract-tree (hierarchy item)
  "Return a copy of HIERARCHY with ITEM's descendants and parents."
  (if (not (hierarchy-has-item hierarchy item))
      nil
    (let ((tree (hierarchy-new)))
      (hierarchy-add-tree tree item
                          (lambda (each) (hierarchy-parent hierarchy each))
                          (lambda (each)
                            (when (or (equal each item)
                                      (hierarchy-descendant-p hierarchy each item))
                              (hierarchy-children hierarchy each))))
      tree)))

(defun hierarchy-copy (hierarchy)
  "Return a copy of HIERARCHY.

Items in HIERARCHY are shared, but structure is not."
  (hierarchy-map-hierarchy (lambda (item _) (identity item)) hierarchy))

\f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Querying
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun hierarchy-items (hierarchy)
  "Return a list of all items of HIERARCHY."
  (map-keys (hierarchy--seen-items hierarchy)))

(defun hierarchy-has-item (hierarchy item)
  "Return t if HIERARCHY includes ITEM."
  (map-contains-key (hierarchy--seen-items hierarchy) item))

(defun hierarchy-empty-p (hierarchy)
  "Return t if HIERARCHY is empty."
  (= 0 (hierarchy-length hierarchy)))

(defun hierarchy-length (hierarchy)
  "Return the number of items in HIERARCHY."
  (hash-table-count (hierarchy--seen-items hierarchy)))

(defun hierarchy-has-root (hierarchy item)
  "Return t if one of HIERARCHY's roots is ITEM.

A root is an item with no parent."
  (seq-contains (hierarchy-roots hierarchy) item))

(defun hierarchy-roots (hierarchy)
  "Return all roots of HIERARCHY.

A root is an item with no parent."
  (let ((roots (hierarchy--roots hierarchy)))
    (or roots
        (hierarchy--compute-roots hierarchy))))

(defun hierarchy-leafs (hierarchy &optional node)
  "Return all leafs of HIERARCHY.

A leaf is an item with no child.

If NODE is an item of HIERARCHY, only return leafs under NODE."
  (let ((leafs (cl-set-difference
                (map-keys (hierarchy--seen-items hierarchy))
                (map-keys (hierarchy--children hierarchy)))))
    (if (hierarchy-has-item hierarchy node)
        (seq-filter (lambda (item) (hierarchy-descendant-p hierarchy item node)) leafs)
      leafs)))

(defun hierarchy-parent (hierarchy item)
  "In HIERARCHY, return parent of ITEM."
  (map-elt (hierarchy--parents hierarchy) item))

(defun hierarchy-children (hierarchy parent)
  "In HIERARCHY, return children of PARENT."
  (map-elt (hierarchy--children hierarchy) parent (list)))

(defun hierarchy-child-p (hierarchy item1 item2)
  "In HIERARCHY, return non-nil if and only if ITEM1 is a child of ITEM2."
  (equal (hierarchy-parent hierarchy item1) item2))

(defun hierarchy-descendant-p (hierarchy item1 item2)
  "In HIERARCHY, return non-nil if and only if ITEM1 is a descendant of ITEM2.

ITEM1 is a descendant of ITEM2 if and only if both are items of HIERARCHY
and either:

- ITEM1 is child of ITEM2, or
- ITEM1's parent is a descendant of ITEM2."
  (and
   (hierarchy-has-item hierarchy item1)
   (hierarchy-has-item hierarchy item2)
   (or
    (hierarchy-child-p hierarchy item1 item2)
    (hierarchy-descendant-p hierarchy (hierarchy-parent hierarchy item1) item2))))

(defun hierarchy-equal (hierarchy1 hierarchy2)
  "Return t if HIERARCHY1 and HIERARCHY2 are equal.

Two equal hierarchies share the same items and the same
relationships among them."
  (and (hierarchy-p hierarchy1)
       (hierarchy-p hierarchy2)
       (= (hierarchy-length hierarchy1) (hierarchy-length hierarchy2))
       ;; parents are the same
       (seq-every-p (lambda (child)
                      (equal (hierarchy-parent hierarchy1 child)
                             (hierarchy-parent hierarchy2 child)))
                    (map-keys (hierarchy--parents hierarchy1)))
       ;; children are the same
       (seq-every-p (lambda (parent)
                      (hierarchy--set-equal
                       (hierarchy-children hierarchy1 parent)
                       (hierarchy-children hierarchy2 parent)
                       :test #'equal))
                    (map-keys (hierarchy--children hierarchy1)))))

\f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Navigation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun hierarchy-map-item (func item hierarchy &optional indent)
  "Return the result of applying FUNC to ITEM and its descendants in HIERARCHY.

This function navigates the tree top-down: FUNCTION is first called on item
and then on each of its children.  Results are concatenated in a list.

INDENT is a number (default 0) representing the indentation of ITEM in
HIERARCHY.  FUNC should take 2 argument: the item and its indentation
level."
  (let ((indent (or indent 0)))
    (cons
     (funcall func item indent)
     (seq-mapcat (lambda (child) (hierarchy-map-item func child hierarchy (1+ indent)))
                 (hierarchy-children hierarchy item)))))

(defun hierarchy-map (func hierarchy &optional indent)
  "Return the result of applying FUNC to each element of HIERARCHY.

This function navigates the tree top-down: FUNCTION is first called on each
root.  To do so, it calls `hierarchy-map-item' on each root
sequentially.  Results are concatenated in a list.

FUNC should take 2 arguments: the item and its indentation level.

INDENT is a number (default 0) representing the indentation of HIERARCHY's
roots."
  (let ((indent (or indent 0)))
    (seq-mapcat (lambda (root) (hierarchy-map-item func root hierarchy indent))
                (hierarchy-roots hierarchy))))

(defun hierarchy-map-tree (function hierarchy &optional item indent)
  "Apply FUNCTION on each item of HIERARCHY under ITEM.

This function navigates the tree bottom-up: FUNCTION is first called on
leafs and the result is passed as parameter when calling FUNCTION on
parents.

FUNCTION should take 3 parameters: the current item, its indentation
level (a number), and a list representing the result of applying
`hierarchy-map-tree' to each child of the item.

INDENT is 0 by default and is passed as second parameter to FUNCTION.
INDENT is incremented by 1 at each level of the tree.

This function returns the result of applying FUNCTION to ITEM (the first
root if nil)."
  (let ((item (or item (car (hierarchy-roots hierarchy))))
        (indent (or indent 0)))
    (funcall function item indent
             (mapcar (lambda (child)
                       (hierarchy-map-tree function hierarchy child (1+ indent)))
                     (hierarchy-children hierarchy item)))))

(defun hierarchy-map-hierarchy (function hierarchy)
  "Apply FUNCTION to each item of HIERARCHY in a new hierarchy.

FUNCTION should take 2 parameters, the current item and its
indentation level (a number), and should return an item to be
added to the new hierarchy."
  (let* ((items (make-hash-table :test #'equal))
         (transform (lambda (item) (map-elt items item))))
    ;; Make 'items', a table mapping original items to their
    ;; transformation
    (hierarchy-map (lambda (item indent)
                     (map-put items item (funcall function item indent)))
                   hierarchy)
    (hierarchy--make
     :roots (mapcar transform (hierarchy-roots hierarchy))
     :parents (let ((result (make-hash-table :test #'equal)))
                (map-apply (lambda (child parent)
                             (map-put result
                                      (funcall transform child)
                                      (funcall transform parent)))
                           (hierarchy--parents hierarchy))
                result)
     :children (let ((result (make-hash-table :test #'equal)))
                 (map-apply (lambda (parent children)
                              (map-put result
                                       (funcall transform parent)
                                       (seq-map transform children)))
                            (hierarchy--children hierarchy))
                 result)
     :seen-items (let ((result (make-hash-table :test #'equal)))
                   (map-apply (lambda (item v)
                                (map-put result
                                         (funcall transform item)
                                         v))
                              (hierarchy--seen-items hierarchy))
                   result))))

\f
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Display
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun hierarchy-labelfn-indent (labelfn &optional indent-string)
  "Return a function rendering LABELFN indented with INDENT-STRING.

INDENT-STRING defaults to a 2-space string.  Indentation is
multiplied by the depth of the displayed item."
  (let ((indent-string (or indent-string "  ")))
    (lambda (item indent)
      (dotimes (_ indent) (insert indent-string))
      (funcall labelfn item indent))))

(defun hierarchy-labelfn-button (labelfn actionfn)
  "Return a function rendering LABELFN in a button.

Clicking the button triggers ACTIONFN.  ACTIONFN is a function
taking an item of HIERARCHY and an indentation value (a number)
as input.  This function is called when an item is clicked.  The
return value of ACTIONFN is ignored."
  (lambda (item indent)
    (let ((start (point)))
      (funcall labelfn item indent)
      (make-text-button start (point)
                        'action (lambda (_) (funcall actionfn item indent))))))

(defun hierarchy-labelfn-button-if (labelfn buttonp actionfn)
  "Return a function rendering LABELFN as a button if BUTTONP.

Pass LABELFN and ACTIONFN to `hierarchy-labelfn-button' if
BUTTONP is non-nil.  Otherwise, render LABELFN without making it
a button.

BUTTONP is a function taking an item of HIERARCHY and an
indentation value (a number) as input."
  (lambda (item indent)
    (if (funcall buttonp item indent)
        (funcall (hierarchy-labelfn-button labelfn actionfn) item indent)
      (funcall labelfn item indent))))

(defun hierarchy-labelfn-to-string (labelfn item indent)
  "Execute LABELFN on ITEM and INDENT.  Return result as a string."
  (with-temp-buffer
    (funcall labelfn item indent)
    (buffer-substring (point-min) (point-max))))

(defun hierarchy-print (hierarchy &optional to-string)
  "Insert HIERARCHY in current buffer as plain text.

Use TO-STRING to convert each element to a string.  TO-STRING is
a function taking an item of HIERARCHY as input and returning a
string.  If nil, TO-STRING defaults to a call to `format' with \"%s\"."
  (let ((to-string (or to-string (lambda (item) (format "%s" item)))))
    (hierarchy-map
     (hierarchy-labelfn-indent (lambda (item _) (insert (funcall to-string item) "\n")))
     hierarchy)))

(defun hierarchy-to-string (hierarchy &optional to-string)
  "Return a string representing HIERARCHY.

TO-STRING is passed unchanged to `hierarchy-print'."
  (with-temp-buffer
    (hierarchy-print hierarchy to-string)
    (buffer-substring (point-min) (point-max))))

(defun hierarchy-tabulated-imenu-action (_item-name position)
  "Move to ITEM-NAME at POSITION in current buffer."
  (goto-char position)
  (back-to-indentation))

(define-derived-mode hierarchy-tabulated-mode tabulated-list-mode "Hierarchy tabulated"
  "Major mode to display a hierarchy as a tabulated list."
  (setq-local imenu-generic-expression
              ;; debbugs: 26457 - Cannot pass a function to
              ;; imenu-generic-expression.  Add
              ;; `hierarchy-tabulated-imenu-action' to the end of the
              ;; list when bug is fixed
              '(("Item" "^[[:space:]]+\\(?1:.+\\)$" 1))))

(defun hierarchy-tabulated-display (hierarchy labelfn &optional buffer)
  "Display HIERARCHY as a tabulated list in `hierarchy-tabulated-mode'.

LABELFN is a function taking an item of HIERARCHY and an indentation
level (a number) as input and inserting a string to be displayed in the
table.

The tabulated list is displayed in BUFFER, or a newly created buffer if
nil.  The buffer is returned."
  (let ((buffer (or buffer (generate-new-buffer "hierarchy-tabulated"))))
    (with-current-buffer buffer
      (hierarchy-tabulated-mode)
      (setq tabulated-list-format
            (vector '("Item name" 0 nil)))
      (setq tabulated-list-entries
            (hierarchy-map (lambda (item indent)
                             (list item (vector (hierarchy-labelfn-to-string labelfn item indent))))
                           hierarchy))
      (tabulated-list-init-header)
      (tabulated-list-print))
    buffer))

(declare-function widget-convert "wid-edit")
(defun hierarchy-convert-to-tree-widget (hierarchy labelfn)
  "Return a tree-widget for HIERARCHY.

LABELFN is a function taking an item of HIERARCHY and an indentation
value (a number) as parameter and inserting a string to be displayed as a
node label."
  (require 'wid-edit)
  (require 'tree-widget)
  (hierarchy-map-tree (lambda (item indent children)
                        (widget-convert
                         'tree-widget
                         :tag (hierarchy-labelfn-to-string labelfn item indent)
                         :args children))
                      hierarchy))

(defun hierarchy-tree-display (hierarchy labelfn &optional buffer)
  "Display HIERARCHY as a tree widget in a new buffer.

HIERARCHY and LABELFN are passed unchanged to
`hierarchy-convert-to-tree-widget'.

The tabulated list is displayed in BUFFER, or a newly created buffer if
nil.  The buffer is returned."
  (let ((buffer (or buffer (generate-new-buffer "*hierarchy-tree*")))
        (tree-widget (hierarchy-convert-to-tree-widget hierarchy labelfn)))
    (with-current-buffer buffer
      (setq-local buffer-read-only t)
      (let ((inhibit-read-only t))
        (erase-buffer)
        (widget-create tree-widget)
        (goto-char (point-min))
        (special-mode)))
    buffer))

(provide 'hierarchy)

;;; hierarchy.el ends here

Re: [ELPA] New package: hierarchy

[Stefan Monnier]

Hi,

> I propose to put the single-file package hierarchy.el in ELPA and to
> keep maintaining the project in a separate repository. I decided to
> avoid using subtree or externals because my unit-test file (which is not
> included here) depends on buttercup which is not on ELPA.

I don't understand.  What do you mean exactly by "put ... in ELPA"?
Currently, there are two ways to add a package to GNU ELPA.
One involves a kind of git-subtree and the other involves a separate
branch (somewhat like a git-submodule), but you say "avoid using subtree
or externals" which seems to imply you intend to use neither of them,
hence my question.


        Stefan

Re: [ELPA] New package: hierarchy

[Stefan Monnier]

> I would like to add my package 'hierarchy', a library to create and
> display hierarchy structures, to ELPA. The hierarchy library has already
> been used to implement a json navigator and a Javascript class hierarchy
> navigator.

This looks really nice.  I'd welcome it into GNU ELPA.
If you need any help to install it there, let me know.

Glancing at the code, I wonder how the JSON and Javascript class
navigators work, tho: do they first convert the original tree to
a `hierarchy` struct?  How would it work if you wanted to use it to
navigate your local file-system (where the complete hierarchy might be
extremely and costly to create)?  Is there some way to construct (and
display) it lazily?

Looking at the code I get the impression that it would be nice to split
it into 3 parts:
- the `hierarchy` defstruct with associated manipulation functions.
- the display code.
- an API between the two, which we could call `tree`, a bit like `seq.el`
  defining the tree navigation primitives needed by the display code
  and which could be implemented by all kinds of data types, including
  the `hierarchy` struct.

WDYT?


        Stefan

Re: [ELPA] New package: hierarchy

[John Wiegley]

>>>>> "SM" == Stefan Monnier <monnier@iro.umontreal.ca> writes:

SM> This looks really nice.  I'd welcome it into GNU ELPA.
SM> If you need any help to install it there, let me know.

I've wanted a general library to do this sort of thing for a while, too. In
more than just Emacs Lisp too. I started one for Haskell with exactly the same
name, even. :)

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: [ELPA] New package: hierarchy

[Clément Pit-Claudel]

On 2017-10-20 16:26, Stefan Monnier wrote:
> - the `hierarchy` defstruct with associated manipulation functions.

It'd be nice if some minimal subset of this package was included into core Emacs, so that parts of core Emacs that display hierarchies could be rewritten to use that subset, making it possible to plug in a different rendering engine.

The specific example I have in mind is the tree displayed by profiler-report.

Clément.

Re: [ELPA] New package: hierarchy

[Eli Zaretskii]

> From: Damien Cassou <damien@cassou.me>
> Date: Tue, 17 Oct 2017 20:15:04 +0200
> 
> I would like to add my package 'hierarchy', a library to create and
> display hierarchy structures, to ELPA. The hierarchy library has already
> been used to implement a json navigator and a Javascript class hierarchy
> navigator.
> 
> I wrote a blog post describing it on Nicolas' blog:
> https://emacs.cafe/emacs/guest-post/2017/06/26/hierarchy.html.
> 
> My motivation for proposing this library to ELPA (instead of MELPA where
> all my other packages are published) is that some developers might want
> to have their hierarchy-dependent package on ELPA. Also, phil-s asked me
> to do it: https://github.com/DamienCassou/hierarchy/issues/48.
> 
> I propose to put the single-file package hierarchy.el in ELPA and to
> keep maintaining the project in a separate repository. I decided to
> avoid using subtree or externals because my unit-test file (which is not
> included here) depends on buttercup which is not on ELPA.

How about adding this to Emacs core instead?  I think built-in
capabilities such as these are long overdue, and Emacs should offer
such basics out of the box.

Re: [ELPA] New package: hierarchy

[João Távora]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Looking at the code I get the impression that it would be nice to split
> it into 3 parts:
> - the `hierarchy` defstruct with associated manipulation functions.
> - the display code.
> - an API between the two, which we could call `tree`, a bit like `seq.el`
>   defining the tree navigation primitives needed by the display code
>   and which could be implemented by all kinds of data types, including
>   the `hierarchy` struct.

FWIW there's also:

   https://www.emacswiki.org/emacs/tree-mode.el
   (and maybe some other similar package that I can't find right now).

Anyway, when I implemented a structured "trace" facility for Common
Lisp[1]] these libraries werent' very useful and I had to bake my own.

I had two (extraordinary?) requirements: (1) that it should work
asynchronously (i.e. updates to any arbitrary node in the hierarchy can
come at any time and out of order) and (2) that display is lazy
(i.e. collecting an update to an arbitrary part in the tree doesn't
necessarily display it).

This is why I favour Stefan's separation and I would love to replace my
library with a decent one.

João

[1]
https://github.com/joaotavora/sly/blob/master/contrib/sly-trace-dialog.el

Re: [ELPA] New package: hierarchy

[Damien Cassou]

Eli Zaretskii <eliz@gnu.org> writes:
> How about adding this to Emacs core instead?  I think built-in
> capabilities such as these are long overdue, and Emacs should offer
> such basics out of the box.


If you think Emacs would benefit from having hierarchy included, please
do include it. My philosophy is more in the opposite direction (getting
rid of as much as possible in the core to facilitate release and to let
package maintainers use the tools they want) but you should decide
(maybe including such a library makes sense in the core even in my
philosophy).

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[Eli Zaretskii]

> From: Damien Cassou <damien@cassou.me>
> Cc: emacs-devel@gnu.org
> Date: Sun, 22 Oct 2017 15:20:44 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> > How about adding this to Emacs core instead?  I think built-in
> > capabilities such as these are long overdue, and Emacs should offer
> > such basics out of the box.
> 
> If you think Emacs would benefit from having hierarchy included

I do, see above.

> My philosophy is more in the opposite direction (getting rid of as
> much as possible in the core

As much as possible, but no more than that, I presume?  Then the issue
here is whether this capability should or shouldn't be in core, as
other basics.  I think it should.

Re: [ELPA] New package: hierarchy

[Damien Cassou]

Eli Zaretskii <eliz@gnu.org> writes:
> As much as possible, but no more than that, I presume?  Then the issue
> here is whether this capability should or shouldn't be in core, as
> other basics.  I think it should.

then include it :-).

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[John Wiegley]

>>>>> Damien Cassou <damien@cassou.me> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>> As much as possible, but no more than that, I presume? Then the issue here
>> is whether this capability should or shouldn't be in core, as other basics.
>> I think it should.

> then include it :-).

I think it should be in core as well.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: [ELPA] New package: hierarchy

[Damien Cassou]

John Wiegley <johnw@gnu.org> writes:
> I think it should be in core as well.

I would like the test suite to be included as well then. The latest
version is built with buttercup which is not part of core. There is an
older version based on ert though. Could you please confirm you want me
to propose a patch including hierarchy and its test suite to Emacs core?

Best,

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[Eli Zaretskii]

> From: Damien Cassou <damien@cassou.me>
> Cc: Eli Zaretskii <eliz@gnu.org>, emacs-devel@gnu.org
> Date: Sun, 22 Oct 2017 22:25:37 +0200
> 
> John Wiegley <johnw@gnu.org> writes:
> > I think it should be in core as well.
> 
> I would like the test suite to be included as well then. The latest
> version is built with buttercup which is not part of core. There is an
> older version based on ert though. Could you please confirm you want me
> to propose a patch including hierarchy and its test suite to Emacs core?

Confirmed.

Please also consider suggestions by Stefan and others, perhaps for
future enhancements of the package.

Thanks.

Re: [ELPA] New package: hierarchy

[Damien Cassou]

Hi Stefan,

as I was not on the emacs-devel mailing-list, I didn't see your message
sooner. My answer is below.

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> I propose to put the single-file package hierarchy.el in ELPA and to
>> keep maintaining the project in a separate repository. I decided to
>> avoid using subtree or externals because my unit-test file (which is not
>> included here) depends on buttercup which is not on ELPA.
>
> I don't understand.  What do you mean exactly by "put ... in ELPA"?
> Currently, there are two ways to add a package to GNU ELPA.
> One involves a kind of git-subtree and the other involves a separate
> branch (somewhat like a git-submodule), but you say "avoid using subtree
> or externals" which seems to imply you intend to use neither of them,
> hence my question.

I thought there was a third option: "drop the file in there". I guess it
does not matter anymore as I will try to integrate hierarchy inside the
core.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[Damien Cassou]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> Glancing at the code, I wonder how the JSON and Javascript class
> navigators work, tho: do they first convert the original tree to
> a `hierarchy` struct?

they do. That's fast enough for every day use.

> How would it work if you wanted to use it to navigate your local
> file-system (where the complete hierarchy might be extremely and
> costly to create)?

This is implemented here
https://github.com/DamienCassou/hierarchy/blob/master/examples/hierarchy-examples-fs.el.

But, as you expect, this is not usable for a complete file system
(displaying ~/.emacs.d takes 4 seconds on my fast computer).

> Is there some way to construct (and display) it
> lazily?

could you please share your ideas at
https://github.com/DamienCassou/hierarchy/issues/49?

> Looking at the code I get the impression that it would be nice to split
> it into 3 parts:


by parts, you mean files? The code is currently split into pages. I
don't mind separating into files if that's what people want.


> - the `hierarchy` defstruct with associated manipulation functions.
> - the display code.
> - an API between the two, which we could call `tree`, a bit like `seq.el`
>   defining the tree navigation primitives needed by the display code
>   and which could be implemented by all kinds of data types, including
>   the `hierarchy` struct.

it makes sense even though I need to look deeper into it to have a clue
about what this would mean in practice.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[Damien Cassou]

João Távora <joaotavora@gmail.com> writes:
> I had two (extraordinary?) requirements: (1) that it should work
> asynchronously (i.e. updates to any arbitrary node in the hierarchy can
> come at any time and out of order) and (2) that display is lazy
> (i.e. collecting an update to an arbitrary part in the tree doesn't
> necessarily display it).

lazy computation of children/parents is something I wanted to do:
https://github.com/DamienCassou/hierarchy/issues/49.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

Re: [ELPA] New package: hierarchy

[João Távora]

Damien Cassou <damien@cassou.me> writes:

> João Távora <joaotavora@gmail.com> writes:
>> I had two (extraordinary?) requirements: (1) that it should work
>> asynchronously (i.e. updates to any arbitrary node in the hierarchy can
>> come at any time and out of order) and (2) that display is lazy
>> (i.e. collecting an update to an arbitrary part in the tree doesn't
>> necessarily display it).
>
> lazy computation of children/parents is something I wanted to do:
> https://github.com/DamienCassou/hierarchy/issues/49.

Great. I do hope "wanted" -> "want" :-)

João

Re: [ELPA] New package: hierarchy

[Stefan Monnier]

> I thought there was a third option: "drop the file in there".

Oh, but that's not technically really different from "git subtree".


        Stefan

Re: [ELPA] New package: hierarchy

[Stefan Monnier]

>> How would it work if you wanted to use it to navigate your local
>> file-system (where the complete hierarchy might be extremely and
>> costly to create)?

> This is implemented here
> https://github.com/DamienCassou/hierarchy/blob/master/examples/hierarchy-examples-fs.el.

> But, as you expect, this is not usable for a complete file system
> (displaying ~/.emacs.d takes 4 seconds on my fast computer).

>> Is there some way to construct (and display) it
>> lazily?

> could you please share your ideas at
> https://github.com/DamienCassou/hierarchy/issues/49?

I don't really have any precise idea in this respect.  I'm just thinking
it should be able to display the top-level nodes without looking at the
subtrees if they're not themselves displayed (yet).  Basically, design
it on the assumption that your hierarchy might be your complete
filesystem, yet it should respond "instantaneously".

>> Looking at the code I get the impression that it would be nice to split
>> it into 3 parts:
> by parts, you mean files?

Not necessarily, no: AFAICT your code is currently split into 2 parts,
so my proposal is to add an API based on generic functions between the
two so the display code can be used with other representations of
a tree.


        Stefan