bug#28753: 25.3; Functions to get alist from hash table and vice versa

[Drew Adams <drew.adams@oracle.com>]

> > (when (or use-last-p  (not (gethash key ht)))
>
> This doesn't work if the value is nil. 

I guess you mean that it doesn't DTRT if the cdr of an alist
entry is `nil' - e.g. (foo) aka (foo . nil).

> You need to use an uninterned symbol or some other unique object, e.g.
> (eq (gethash key ht #1='#:void) #1#)

OK.  Dunno which is clearer or whether there is some
performance difference, but I would probably just bind
a var to a unique cons, e.g. (cons 1 1), outside the
`dolist'.  E.g.:

(let ((ht (make-hash-table :test test :weakness weakness
                           :size size :rehash-size rehash-size
                           :rehash-threshold rehash-threshold))
      (uniq-cons (cons 1 1))
      key val)
  (dolist (key.val  alist)
    (setq key  (car key.val)
          val  (cdr key.val))
    (when (or use-last-p  (not (eq (gethash key ht uniq-cons))))
      (puthash key val ht)))
  ht))

(With your approach of using an uninterned symbol, wouldn't
you want to do the same thing: bind a var to it outside the
`dolist', or would that make no real difference?)
 
> I'd personally make use-last-p another keyword argument, though.

I don't have a strong objection, but why?

> > (defun hash-table-to-alist (hash-table)
> >  "Create and return an alist created from HASH-TABLE.
> > The order of alist entries is the same as the order of hash-table
> > entries (which normally is the order in which the entries were added
> > to the table)."
> >  (let ((al  ()))
> >    (maphash (lambda (key val) (push (cons key val) al)) hash-table)
> >    (nreverse al)))
>
> Hmm, is the order guaranteed? I haven't found anything in the
> Emacs Lisp manual about this, so maybe just leave out the
> parenthetical remark or say that the order is unspecified?

Good question!  But it's not just the parenthetical part.
If we couldn't say anything about the traversal order of
`maphash' then the whole sentence would need to go.

FWIW, I think it's pretty important.  Order is quite
important for alists, generally.

Is there some reason we should not be able to count on
this `maphash' behavior?

That's the behavior I saw, AFAICT, but I didn't test much.

I don't know whether it is guaranteed, but this use case
involving conversion to alist looks like a good argument for
some guarantee wrt order.

I see that in Common Lisp nothing is said about the traversal
by `maphash' over the hash table.  This is all that is said:

 "For each entry in hash-table, maphash calls function on two
  arguments: the key of the entry and the value of the entry;
  maphash then returns nil. If entries are added to or deleted
  from the hash table while a maphash is in progress, the results
  are unpredictable, with one exception: if the function calls
  remhash to remove the entry currently being processed by the
  function, or performs a setf of gethash on that entry to change
  the associated value, then those operations will have the
  intended effect."

  - https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node155.html

(Emacs doc should also probably say at least something about
what happens when entries are added/removed during a `maphash'
application.)

If Emacs decides not to guarantee the order seen now, which I
think is the order I described in the doc string above, then we
would need to remove that sentence.  That would be too bad for
users of function `hash-table-to-alist', but at least they
would, at least so far (and AFAICT), get that behavior, which
is likely to be expected by them even if it is not documented.

Another possibility (?): Allow _optional_ creation of a hash
table that does preserve such ordering (even if just by
recording order of entry and making that available to `maphash').
E.g., add a keyword arg for `make-hash-table' that does just that.

Even if it turned out that this consistently or occasionally
detracted from performance, it could be a useful option.
Conversion to an alist would be a case in point.