maphash: improve docstring

maphash: improve docstring

[Paul Pogonyshev]

Docstring for `maphash' doesn't give any answer to the following
question: is the callback FUNCTION allowed to access the hash
table in read mode (I guess yes) and write mode?  About the
latter I have no idea without studying internal implementation.

E.g., is the following code going to work as a way to filter a
hash table?

    (maphash (lambda (key value)
               (unless (i-like-it value)
                 (remhash key hash-table)))
             hash-table)

Paul

Re: maphash: improve docstring

[Stefan Monnier]

> Docstring for `maphash' doesn't give any answer to the following
> question: is the callback FUNCTION allowed to access the hash
> table in read mode (I guess yes) and write mode?  About the
> latter I have no idea without studying internal implementation.

> E.g., is the following code going to work as a way to filter a
> hash table?

Yes, you are allowed to modify the table while iterating over it and the
resulting behavior should be sane.

And it should have the usual desired properties: The set of elements
passed to the function is a superset of all the elements that aren't
removed during the iteration, and a subset of all the elements that were
present at the beginning or added during the loop.  IOW if an entry is
untouched during the loop, then it will be passed (exactly once) to the
function.  If an entry is added or removed during the loop, then maybe
it will be passed to the function, but maybe not.  And if an entry is
modified during the loop, then it will be passed to the function
(exactly once) and the value passed will be the one that happens to be
current when the function is called.


        Stefan

Re: maphash: improve docstring

[Stefan Monnier]

> it will be passed to the function, but maybe not.  And if an entry is
> modified during the loop, then it will be passed to the function
> (exactly once) and the value passed will be the one that happens to be
> current when the function is called.

More specifically, you're guaranteed when entering the function that the
key you've received does currently exist in the table and is currently
associated with the value you just received.


        Stefan

Re: maphash: improve docstring

[Paul Pogonyshev]

[I didn't receive the answer because I wasn't subscribed to the list,
 so the thread will be broken]

> > Docstring for `maphash' doesn't give any answer to the following
> > question: is the callback FUNCTION allowed to access the hash
> > table in read mode (I guess yes) and write mode?  About the
> > latter I have no idea without studying internal implementation.
>
> > E.g., is the following code going to work as a way to filter a
> > hash table?
>
> Yes, you are allowed to modify the table while iterating over it and the
> resulting behavior should be sane.
>
> And it should have the usual desired properties: The set of elements
> passed to the function is a superset of all the elements that aren't
> removed during the iteration, and a subset of all the elements that were
> present at the beginning or added during the loop.  IOW if an entry is
> untouched during the loop, then it will be passed (exactly once) to the
> function.  If an entry is added or removed during the loop, then maybe
> it will be passed to the function, but maybe not.  And if an entry is
> modified during the loop, then it will be passed to the function
> (exactly once) and the value passed will be the one that happens to be
> current when the function is called.
>
> More specifically, you're guaranteed when entering the function that the
> key you've received does currently exist in the table and is currently
> associated with the value you just received.

Could one expand documentation of `maphash' like this?  I'm not
sure it follows from what you wrote, but I understood it like
this:

    Call FUNCTION for all entries in hash table TABLE.
    FUNCTION is called with two arguments, KEY and VALUE.
    `maphash' always returns nil.

    FUNCTION will usually just inspect its arguments, but may also
    alter TABLE and this will not cause `maphash' to malfunction.
    However, some effects are not fully defined, see below.

    If FUNCTION adds an entry to TABLE, it may or may not be called
    with the added key/value pair.

    If FUNCTION changes value already associated with a key and it
    has not been called with that key yet, it will be called with key
    and the new value during the iteration later.  Otherwise it will
    not be called for that key again.

    If FUNCTION removes a key and it has not been called with it yet,
    it will not be called for the removed key in the future either.

    Note that if FUNCTION removes or changes value only for KEY it is
    called with, the behavior is completely defined.

Another option is to add this (probably with more explanation) to
the manual and add just a sentence to the tune of "see manual for
details" to the docstring.

Paul

Re: maphash: improve docstring

[Stefan Monnier]

> Could one expand documentation of `maphash' like this?  I'm not sure
> it follows from what you wrote, but I understood it like this:

That looks right.

>     Call FUNCTION for all entries in hash table TABLE.
>     FUNCTION is called with two arguments, KEY and VALUE.
>     `maphash' always returns nil.
>     FUNCTION will usually just inspect its arguments, but may also
>     alter TABLE and this will not cause `maphash' to malfunction.
>     However, some effects are not fully defined, see below.
>     If FUNCTION adds an entry to TABLE, it may or may not be called
>     with the added key/value pair.
>     If FUNCTION changes value already associated with a key and it
>     has not been called with that key yet, it will be called with key
>     and the new value during the iteration later.  Otherwise it will
>     not be called for that key again.
>     If FUNCTION removes a key and it has not been called with it yet,
>     it will not be called for the removed key in the future either.
>     Note that if FUNCTION removes or changes value only for KEY it is
>     called with, the behavior is completely defined.

Yes.  I think we can come up with something more concise (by splitting
the description of which keys will be called, from the description of
which value is passed), but haven't been very successful at it either.

> Another option is to add this (probably with more explanation) to
> the manual and add just a sentence to the tune of "see manual for
> details" to the docstring.

Sure,


        Stefan

Re: maphash: improve docstring

[Paul Pogonyshev]

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

How about the following patch?

Paul



* src/fns.c (Fmaphash): Add reference to the corresponding Info
  node to the docstring.

* doc/lispref/hash.texi (Hash Access): Expand documentation of
  'maphash' with detailed description of what happens if
  'function' modifies the 'table'.

On 30 March 2016 at 00:44, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> Could one expand documentation of `maphash' like this?  I'm not sure
>> it follows from what you wrote, but I understood it like this:
>
> That looks right.
>
>>     Call FUNCTION for all entries in hash table TABLE.
>>     FUNCTION is called with two arguments, KEY and VALUE.
>>     `maphash' always returns nil.
>>     FUNCTION will usually just inspect its arguments, but may also
>>     alter TABLE and this will not cause `maphash' to malfunction.
>>     However, some effects are not fully defined, see below.
>>     If FUNCTION adds an entry to TABLE, it may or may not be called
>>     with the added key/value pair.
>>     If FUNCTION changes value already associated with a key and it
>>     has not been called with that key yet, it will be called with key
>>     and the new value during the iteration later.  Otherwise it will
>>     not be called for that key again.
>>     If FUNCTION removes a key and it has not been called with it yet,
>>     it will not be called for the removed key in the future either.
>>     Note that if FUNCTION removes or changes value only for KEY it is
>>     called with, the behavior is completely defined.
>
> Yes.  I think we can come up with something more concise (by splitting
> the description of which keys will be called, from the description of
> which value is passed), but haven't been very successful at it either.
>
>> Another option is to add this (probably with more explanation) to
>> the manual and add just a sentence to the tune of "see manual for
>> details" to the docstring.
>
> Sure,
>
>
>         Stefan

[-- Attachment #2: maphash-doc.diff --]
[-- Type: text/plain, Size: 2112 bytes --]

diff --git a/doc/lispref/hash.texi b/doc/lispref/hash.texi
index a197399..611225c 100644
--- a/doc/lispref/hash.texi
+++ b/doc/lispref/hash.texi
@@ -225,6 +225,27 @@ This function calls @var{function} once for each of the associations in
 @var{table}.  The function @var{function} should accept two
 arguments---a @var{key} listed in @var{table}, and its associated
 @var{value}.  @code{maphash} returns @code{nil}.
+
+Typically, @var{function} will just inspect its arguments.  However,
+it is also allowed to read and/or modify @var{table}, even for
+unrelated keys.  This will not cause @code{maphash} to malfunction,
+but some effects are not fully defined, as described below.
+
+If @var{function} adds a new entry to the @var{table}, it @emph{may or
+may not} be called during this iteration with the new key/value pair.
+
+If @var{function} changes the value already associated with a key
+@var{K} and it has not been called with @var{K} yet, it will be called
+with the @var{K} and the @emph{new} value during the iteration later.
+Otherwise it will not be called for @var{K} again, even though it has
+been called with the old value before.
+
+If @var{function} removes a key and it has not been called with it
+yet, it will not be called for the removed key in the future either.
+
+In particular, it follows that if @var{function} removes or changes
+value only for the @var{key} it is called with, the behavior is
+completely defined.
 @end defun
 
 @node Defining Hash
diff --git a/src/fns.c b/src/fns.c
index 825e443..65d46f7 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4715,7 +4715,10 @@ DEFUN ("remhash", Fremhash, Sremhash, 2, 2, 0,
 DEFUN ("maphash", Fmaphash, Smaphash, 2, 2, 0,
        doc: /* Call FUNCTION for all entries in hash table TABLE.
 FUNCTION is called with two arguments, KEY and VALUE.
-`maphash' always returns nil.  */)
+`maphash' always returns nil.
+
+FUNCTION may modify the TABLE even as iteration is in progress.
+See Info node `(elisp)Hash Access' for details.  */)
   (Lisp_Object function, Lisp_Object table)
 {
   struct Lisp_Hash_Table *h = check_hash_table (table);

Re: maphash: improve docstring

[Stefan Monnier]

> How about the following patch?

Looks OK,


        Stefan