maphash

maphash

[Helmut Eller]

The documentation states that puthash and remhash are only "allowed" to
use the current key while a maphash is in progress.  (Interestingly, it
says nothing about gethash.)

However, the code in comp.el uses puthash with other keys.  E.g
comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
and while the iteration is in progress, it calls
comp--add-cond-cstrs-target-block which puts new basic blocks into the
hashtable.

(With the current implementation, inserting may rehash the table which
can cause maphash to "skip" some entries or visit some entries twice.)

Should the hashtable implementation detect such situations and perhaps
signal an error or a warning?

Re: maphash

[Mattias Engdegård]

10 sep. 2024 kl. 17.52 skrev Helmut Eller <eller.helmut@gmail.com>:

> The documentation states that puthash and remhash are only "allowed" to
> use the current key while a maphash is in progress.  (Interestingly, it
> says nothing about gethash.)

That is correct. The purpose of these rules is to avoid us being shackled to a specific behaviour if a user breaks them; we don't want any more implementation restrictions than necessary.

We still protect Lisp abstractions so the user shouldn't fear segfaults, but there are no promises when it comes to the iteration order, whether iteration will encounter added elements, the same element twice or some none at all, etc.

> However, the code in comp.el uses puthash with other keys.  E.g
> comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
> and while the iteration is in progress, it calls
> comp--add-cond-cstrs-target-block which puts new basic blocks into the
> hashtable.

This sounds like a bug in nativecomp then, even if it happens not to have any bad consequences right now.

> Should the hashtable implementation detect such situations and perhaps
> signal an error or a warning?

Not unless it can be done at basically no cost. This is not a very common mistake and letting all correct code pay for it wouldn't be a good trade-off.

Re: maphash

[Andrea Corallo]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 10 sep. 2024 kl. 17.52 skrev Helmut Eller <eller.helmut@gmail.com>:
>
>> The documentation states that puthash and remhash are only "allowed" to
>> use the current key while a maphash is in progress.  (Interestingly, it
>> says nothing about gethash.)
>
> That is correct. The purpose of these rules is to avoid us being shackled to a specific behaviour if a user breaks them; we don't want any more implementation restrictions than necessary.
>
> We still protect Lisp abstractions so the user shouldn't fear
> segfaults, but there are no promises when it comes to the iteration
> order, whether iteration will encounter added elements, the same
> element twice or some none at all, etc.
>
>> However, the code in comp.el uses puthash with other keys.  E.g
>> comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
>> and while the iteration is in progress, it calls
>> comp--add-cond-cstrs-target-block which puts new basic blocks into the
>> hashtable.
>
> This sounds like a bug in nativecomp then, even if it happens not to have any bad consequences right now.

Ops! Will look at thanks

  Andrea

Re: maphash

[Richard Stallman]

    I have discovered by experimentation that maphash actually does what 
    I hoped it would, which is to pass key/value pairs to the mapping 
    function in the same order in which they were added to the table. 

An small anount of experimentation doesn't show you it will always to
do that.  It would be necessary to study the code and construct a
proof, before we could promise this to the users.

Do you want to study the code?

Re: maphash

[Stephen J. Turnbull]

>>>>> "rms" == Richard Stallman <rms@gnu.org> writes:

    I have discovered by experimentation that maphash actually does what 
    I hoped it would, which is to pass key/value pairs to the mapping 
    function in the same order in which they were added to the table. 

    rms> An small anount of experimentation doesn't show you it will
    rms> always to do that.  It would be necessary to study the code
    rms> and construct a proof, before we could promise this to the
    rms> users.

If I understand the OP's description correctly, I can already promise
you that code depending on such a feature won't be portable to XEmacs:

(let ((my-hash (make-hash-table))
      result)
  (puthash "key1" "val1" my-hash)
  (puthash "key2" "val2" my-hash)
  (puthash "key3" "val3" my-hash)
  (maphash (lambda (k v) (setq result (cons k result))) my-hash)
  (reverse result))

=> ("key2" "key3" "key1")


-- 
Institute of Policy and Planning Sciences     http://turnbull.sk.tsukuba.ac.jp
University of Tsukuba                    Tennodai 1-1-1 Tsukuba 305-8573 JAPAN
               Ask not how you can "do" free software business;
              ask what your business can "do for" free software.

Re: maphash

[Greg Hill]

At 4:46 PM +0900 4/24/03, Stephen J. Turnbull wrote:
>  >>>>> "rms" == Richard Stallman <rms@gnu.org> writes:
>
>     I have discovered by experimentation that maphash actually does what
>     I hoped it would, which is to pass key/value pairs to the mapping
>     function in the same order in which they were added to the table.
>
>     rms> An small anount of experimentation doesn't show you it will
>     rms> always to do that.  It would be necessary to study the code
>     rms> and construct a proof, before we could promise this to the
>     rms> users.
>
>If I understand the OP's description correctly, I can already promise
>you that code depending on such a feature won't be portable to XEmacs:
>
>(let ((my-hash (make-hash-table))
>       result)
>   (puthash "key1" "val1" my-hash)
>   (puthash "key2" "val2" my-hash)
>   (puthash "key3" "val3" my-hash)
>   (maphash (lambda (k v) (setq result (cons k result))) my-hash)
>   (reverse result))
>
>=> ("key2" "key3" "key1")

Fortunately for me, in GNU Emacs Stephen's example--and several 
variations thereof--do work the way I described, and not the way they 
work in XEmacs.  Also, fortunately for me, my code does not have to 
be portable.


At 9:51 PM -0400 4/23/03, Richard Stallman wrote:
>Do you want to study the code?

After taking a quick look at the C source code, the simple answer to 
Richard's question is "No, thank you."  I do write code in C, when I 
absolutely have to, but I don't really care for the language.  And in 
general, I don't enjoy the challenge of figuring out how OP's code 
works, especially when it is written in C _and_ chock full of MACROs.

So, I'll just say: That's ok, I understand that you cannot, in good 
faith, make any promises either that this "feature" works relieably 
now, or even that if it happens to now, it always will.  It _is_ 
working for me reliably now, and I'll keep using it as long as it 
does; and I promise I won't complain if my decision to do so comes 
back to haunt me later on.

--Greg

Re: maphash

[Richard Stallman]

    Fortunately for me, in GNU Emacs Stephen's example--and several 
    variations thereof--do work the way I described,
    ...

    After taking a quick look at the C source code, the simple answer to 
    Richard's question is "No, thank you."

We can't document this feature unless we know it can be relied on.  I
took a quick look at the code of maphash and it led me to doubt that
this is generally true, but while I have the know-how to study it
carefully, I do not have the time.