Easy traversal of customize groups

Easy traversal of customize groups

[Etienne Prud’homme]

The Emacs customization system allows to group custom options.  We use
something called a group that will contain all its customization members
(including other groups).  Thus this makes a tree structure.

While customize groups are mostly used by “Custom-mode”, I find them
really convenient for splitting my init files.  I use them so often that
I made a small hack library that shows the paths of a group (a group can
have multiple parents).

However, I noticed that figuring out the paths for a group can be quite
hungry.  It may not be noticeable when using “Custom-mode”, but to find
the parents of a group, we actually use `mapatoms' to iterate over all
known symbols.  The symbol has a corresponding plist (list of
properties).

In order to make a group parent of another group, the parent group
symbol property list must include a property in the form of:

([children-group] custom-group)

That’s more or less the same way members of the group are stored.
Storing a reference to group members like that is not a problem when
traversing a tree from the root.  However, it can become really
inefficient when trying to resolve the group’s parent. E.g.

If I’m in group ‘info’, I must map over all known symbols to guess its
parents.

So now, here’s my proposal: adding a property to link parents in the
child group property list.  This would allow efficient traversal of
customization groups and why not printing a tree of the current
customization option.

The drawback would be increased memory usage, but I find it negligible
when we see the performance improvement.

--
Etienne

Re: Easy traversal of customize groups

[Stefan Monnier]

> So now, here’s my proposal: adding a property to link parents in the
> child group property list.

Another option is to perform one mapatoms traversal which builds a cache
of the "reverse links" and then use that.


        Stefan

Re: Easy traversal of customize groups

[Etienne Prud’homme]

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

> Another option is to perform one mapatoms traversal which builds a cache
> of the "reverse links" and then use that.

That’s also a solution.  Were you talking about a tree structure?

It think it might over complicate the current implementation since we
would have to remove an entry from the cache when it is unloaded and we
would have to update each possible paths when a new group is loaded.

Here’s a snippet of what I’m using:

> (require 'seq)
> 
> (defun custom-group-parent-group-p (group parent)
>   "Test that GROUP is a direct child of PARENT."
>   (eq 'custom-group (car (alist-get group (get parent 'custom-group)))))
> 
> (defun custom-group-parent-groups (group)
>   "Return a list of parent groups for GROUP.
> 
> E.g. “wdired” would return “(dired)”.
> 
> Note: This function has much faster implementation of finding
> parents than using `custom-group-parent-group-p'.  Around 10x
> faster than mapping with `custom-group-parent-group-p'."
>   (let ((parents))
>     ;; First find the “group” a-list candidates.
>     (mapatoms (lambda (symbol)
>                 (when (alist-get group (get symbol 'custom-group))
>                   (setq parents (cons symbol parents))))
>               obarray)
>     ;; Than filter “group” a-list candidates to only show `custom-group'
>     ;; symbol properties.
>     (seq-filter (lambda (value)
>               (eq (car (alist-get group (get value 'custom-group))) 'custom-gr> oup))
>             parents)))
> 
> (defun custom-group-get-paths (group)
>   "Get an ordered list on the parent paths for GROUP.
> 
> The path is in the form of:
> \((files dired wdired)
>  (environment dired wdired))
> 
> Where “files” is the topmost parent group of the “wdired”
> group (without counting an orphan or the Emacs group)."
>   (let ((tree (custom-group--get-tree group))
>         (paths)
>         (custom-group-get--paths))
>     (setq custom-group-get--paths
>           (lambda (nodes path)
>             "Private.
> 
> Go through all possible NODES and add the PATH to the `paths' variable."
>             (message (prin1-to-string nodes))
>             (let ((newpath (if (listp path)
>                                path
>                              (list path)))
>                   (newnodes (cadr nodes)))
>               (unless (eq nil (car nodes))
>                 (push (car nodes) newpath))
>               (if newnodes
>                   (dolist (node newnodes)
>                     (funcall custom-group-get--paths node newpath))
>                 (add-to-list 'paths newpath)))))
>     (funcall custom-group-get--paths tree nil)
>     paths))
> 
> (defun custom-group--get-tree (group)
>   "Private.
> 
> Get a tree on the parent paths for GROUP.
> 
> The following tree:
> ╔══════════════════════════════════════╗
> ║ files ─────────┐                     ║
> ║                ├─── dired ─── wdired ║
> ║ environment ───┘                     ║
> ╚══════════════════════════════════════╝
> 
> Would give the expression:
> ╔════════════════════════════════════════════════════════╗
> ║ (wdired ((dired ((environment (nil)) (files (nil)))))) ║
> ╚════════════════════════════════════════════════════════╝
> 
> Where nil either represent no more parent or the Emacs group."
>   (let ((parents (custom-group-parent-groups group))
>         (tree))
>     (unless (or (eq nil group) (eq 'emacs group))
>       (cons group
>             (list
>              (dolist (parent parents tree)
>                (push (custom-group--get-tree parent) tree)))))))
 
As an example, if we get “message-forwarding”: 

> (require 'gnus)
> (require 'message)
> (custom-group-get-paths 'message-forwarding)

It becomes quite a large tree:
> (message-forwarding
>  ((message-interface
>    ((message
>      ((news
>        ((applications (nil))))
>       (mail ((applications (nil))))
>       (gnus-message
>        ((gnus
>          ((news ((applications (nil))))
>           (mail ((applications (nil))))))))))))))

Where “nil” is the Emacs group node.

We could of course map their parents instead of making a tree structure,
but it’s almost the same way my suggestion works.

I’m proposing to change the “custom-declare-group” function to add links
to the parent groups wen defining a new group.

--
Etienne

Re: Easy traversal of customize groups

[Stefan Monnier]

>> Another option is to perform one mapatoms traversal which builds a cache
>> of the "reverse links" and then use that.
> That’s also a solution.  Were you talking about a tree structure?

I was thinking of keeping the "tree" in a hash-table.

> It think it might over complicate the current implementation since we
> would have to remove an entry from the cache when it is unloaded and we
> would have to update each possible paths when a new group is loaded.

I was thinking of throwing the hash-table as soon as you're done with it.
It's pretty cheap to build.  You only need it to avoid O(N) calls to mapatoms.


        Stefan