Pansymbolic: Mapping all Emacs Lisp symbols

There are more than 1400 native Emacs functions written in C, so a "package" 'EMACS-PRIMITIVES needs to be added with its corresponding symbols.

These symbols could be extracted:

• directly from the C sources (somehow); or
  
• by loading the latest minor version of Emacs and running something like this:
  

(let (prims)
  (mapatoms
   (lambda (symbol)
     (and (functionp symbol)
          (subr-primitive-p (symbol-function symbol))
          (push symbol prims))))
  (sort prims #'string<))

One way to store collected symbols is to put them in a map where each package is a key and each value is a list of symbols defined by that package in one namespace. Let's call this pack→syms. It's a one-dimensional map.

Another way is sym→packs. It can be produced either directly or by converting pack→syms.

Here, each symbol is a key, and the value is a list of packages that define that symbol. For almost all symbols, that list will have only one package. When not, an unintended symbol collision might be going on. We can see that pack→syms is also a one-dimensional map.

In order to query the symbols, it's cumbersome to have them be inside the lists in the values (pack→syms). We'd have to walk all the lists in all the values for every search. That's expensive.

Some alternatives to choose from are:

1. Make pack→syms; convert to sym→packs, then to tree:sym→packs; query that.
   
2. Make pack→syms; convert to sym→packs; query that.
   
3. Make sym→packs; convert to tree:sym→packs; query that.
   
4. Make sym→packs; query that.
   
5. Make pack→syms; convert directly to tree:sym→packs; query that.
   

What is tree:sym→packs? That's a tree in which the symbols have been properly tokenized and the list of packages that define each symbol is to be found at the leaves. It can provide visualization, navigation, and extremely fast "prefix" queries.

Given the huge size of the results (easily a few hundred thousand symbols for the functions' namespace), it seems important to horizontally partition sym→packs and/or tree:sym→packs.

Partitioning can be alphabetic, and perhaps first letter is enough, with an extra bucket (say, %) to put anything starting with [^a-zA-Z0-9]. So:

• A search for "foo-this" or "f-ext" would open and read file f.
  
• A search for "", "<", ="/", "+", or "-each" would read file %.
  

Hash tables — that's my suggestion.

In this case:

• SymTable can convert from pack→syms to sym→packs.
  
• SymTree can convert from either of these two to tree:sym→packs.
  

Note that tree:sym→packs here isn't a "regular tree" (nested lists), but a nested hash table.

For more information, see the respective packages.

One question is whether it'd be better to have only sym→packs hash table(s) (without also the corresponding tree:sym→packs). The most critical factor would be querying speed.

If data formats other than elisp are fine, then flat TSV is a good choice.

Both pack→syms and sym→packs could be put into a two-column TSV each.

Since sym→packs could have hundreds of thousands of lines, it might still be a good idea to partition it alphabetically into several files.

Querying sym→packs could then be done by grepping lines by regex and then uniq-ifying the values. Naturally, this could also be coded in elisp and done from inside emacs in a platform-independent fashion.

Below is a simple solution to that, using a new function candidate for my SymTable package. Note: a KVL, which means "key–value lines", is just a headerless two-column TSV that is flexible about field separators.

;; Example of a possible new function for non-elisp data format
(defun symtable/query-pre-in-kvl (korkf prefix &optional kvl-sep)
  "Return packages that have PREFIX.
KORKF is either a KVL file or a KVL.
For the meaning of KVL, see ‘h<-kvl’.
For the meaning of PREFIX, see ‘symtable-query-pre’.
Optional argument KVL-SEP is the separator used in the KVL. If nil,
use ‘h-kvl-sep-re’, whose value is \" *= *\". Pass \\t for tabs."
  (let* ((case-fold-search nil)
         (h-kvl-sep-re (if kvl-sep kvl-sep h-kvl-sep-re))
         (kvl (if (file-exists-p korkf) (h-read-kvl korkf) korkf))
         (rx  (symtable--query-make-pre-rx prefix))
         (htb))
    (with-temp-buffer
      (save-excursion (insert kvl))
      (keep-lines rx)
      (setq htb (h<-kvl (buffer-string))))
    (h--hmap! key (s-split " " value 'no-nulls) htb)
    (symtable-query-rx htb rx)))

So that:

(let ((kvl "
foo-this          =  foo
foo--this-thing   =  foo foo-plus
global-foo-mode   =  foo
bar--that         =  bar
global-bar-mode   =  bar
baz-global-doing  =  baz
globalize-things  =  globalize
qux/mode          =  qux
global-qux/mode   =  qux-lite qux
qux/something     =  qux"))

  (symtable/query-pre-in-kvl kvl "global"))
=> '("bar" "foo" "qux" "qux-lite")

This means these four packages define at least one function that has global as one of its prefixes. Note that globalize isn't a match, because it's not a "prefix for packaging purposes".

(The above isn't the most efficient way of doing that, but it's simple enough. It could be optimized later, if needed, after exact formats have been chosen.)