[PATCH] It is always safe to delete the most recent key

[p5pRT]

Migrated from rt.perl.org#121404 (status was 'resolved')

Searchable as RT121404$

[p5pRT]

From @pjcj

Created by @pjcj

In the perlfunc section on "each" we state​:

  Any insertion
  into the hash may change the order, as will any deletion, with the exception
  that the most recent key returned by C<each> or C<keys> may be deleted
  without changing the order.

  If you add or delete a hash's
  elements while iterating over it, entries may be skipped or duplicated--so
  don't do that. Exception​: In the current implementation, it is always safe
  to delete the item most recently returned by C<each()>, so the following
  code works properly​:

  while (($key, $value) = each %hash) {
  print $key, "\n";
  delete $hash{$key}; # This is safe
  }

My beef here is with the phrase "In the current implementation". This was
added by Tom Christiansen in bade7fb (perl #89758) as part of a series of
changes to remind "users to put version guards on their neologisms". I'm all
for not promising more than we need to in the documentation, but I think this
particular change might be a step too far.

We promise unconditionally that deleting the most recent key will not change
the iteration order, then we weaken that promise. But are we really thinking
that the above code may one day be illegal? We had promised it would always
be safe since 2000 (74fc8b5).

In addition, the documentation for both "keys" and "values" states​:

  Any insertion
  into the hash may change the order, as will any deletion, with the exception
  that the most recent key returned by C<each> or C<keys> may be deleted
  without changing the order.

So perhaps the attached patch is appropriate. Or have I misunderstood
something?

Perl Info

Flags:
    category=docs
    severity=low
    Type=Patch
    PatchStatus=HasPatch

Site configuration information for perl 5.19.10:

Configured by pjcj at Sun Mar  9 14:33:56 CET 2014.

Summary of my perl5 (revision 5 version 19 subversion 10) configuration:
  Commit id: d6f4d13d11a6a780ab6f0fc8156ec350a7da07b2
  Platform:
    osname=linux, osvers=3.2.0-59-generic, archname=x86_64-linux
    uname='linux posub64 3.2.0-59-generic #90-ubuntu smp tue jan 7 22:43:51 utc 2014 x86_64 x86_64 x86_64 gnulinux '
    config_args='-des -Dprefix=/usr/local/pkg/bleadperl -Dusedevel'
    hint=previous, useposix=true, d_sigaction=define
    useithreads=undef, usemultiplicity=undef
    use64bitint=define, use64bitall=define, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
    optimize='-O2',
    cppflags='-fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include -fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64'
    ccversion='', gccversion='4.6.3', gccosandvers=''
    intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
    ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='cc', ldflags =' -fstack-protector -L/usr/local/lib'
    libpth=/usr/local/lib /usr/lib/gcc/x86_64-linux-gnu/4.6/include-fixed /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib /usr/local/lib /usr/lib/gcc/x86_64-linux-gnu/4.6/include-fixed /usr/include/x86_64-linux-gnu /usr/lib
    libs=-lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
    perllibs=-lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.15.so, so=so, useshrplib=false, libperl=libperl.a
    gnulibc_version='2.15'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
    cccdlflags='-fPIC', lddlflags='-shared -O2 -L/usr/local/lib -fstack-protector'



@INC for perl 5.19.10:
    lib
    /usr/local/lib/perl5/site_perl/5.19.10/x86_64-linux
    /usr/local/lib/perl5/site_perl/5.19.10
    /usr/local/lib/perl5/5.19.10/x86_64-linux
    /usr/local/lib/perl5/5.19.10
    .


Environment for perl 5.19.10:
    HOME=/home/pjcj
    LANG=en_GB.UTF-8
    LANGUAGE (unset)
    LC_CTYPE=en_GB.UTF-8
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/home/pjcj/.rvm/gems/ruby-1.9.3-p448/bin:/home/pjcj/.rvm/gems/ruby-1.9.3-p448@global/bin:/home/pjcj/.rvm/rubies/ruby-1.9.3-p448/bin:/home/pjcj/.rvm/bin:/home/pjcj/perl5/perlbrew/bin:/home/pjcj/perl5/perlbrew/perls/perl-5.18.0/bin:/home/pjcj/bin:/home/pjcj/utils:/home/pjcj/utils/perl:/home/pjcj/g/sw/bin:/usr/local/bin:/usr/bin:/bin:/usr/local/sbin:/usr/sbin:/sbin:/usr/bin/X11:/usr/games:/home/pjcj/g/sw/powerline-daemon:/home/pjcj/g/base/powerline/scripts
    PERLBREW=command perlbrew
    PERLBREW_BASHRC_VERSION=0.63
    PERLBREW_HOME=/home/pjcj/.perlbrew
    PERLBREW_MANPATH=/home/pjcj/perl5/perlbrew/perls/perl-5.18.0/man
    PERLBREW_PATH=/home/pjcj/perl5/perlbrew/bin:/home/pjcj/perl5/perlbrew/perls/perl-5.18.0/bin
    PERLBREW_PERL=perl-5.18.0
    PERLBREW_ROOT=/home/pjcj/perl5/perlbrew
    PERLBREW_VERSION=0.63
    PERL_BADLANG (unset)
    SHELL=/usr/bin/zsh

--------------1.40.perlbug
Content-Type: text/x-patch; name="0001-It-is-always-safe-to-delete-the-most-recent-key.patch"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment; filename="0001-It-is-always-safe-to-delete-the-most-recent-key.patch"

From e928c36230fdb3137ada5f9c50b66a21712663f0 Mon Sep 17 00:00:00 2001
From: Paul Johnson <paul@pjcj.net>
Date: Sun, 9 Mar 2014 15:07:54 +0100
Subject: [PATCH] It is always safe to delete the most recent key.


 pod/perlfunc.pod |    5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/pod/perlfunc.pod b/pod/perlfunc.pod
index 14c5171..4a3893a 100644
--- a/pod/perlfunc.pod
+++ b/pod/perlfunc.pod
@@ -1670,9 +1670,8 @@ reached the end as just described; it can be explicitly reset by calling
 C<keys> or C<values> on the hash or array.  If you add or delete a hash's
 elements while iterating over it, the effect on the iterator is
 unspecified; for example, entries may be skipped or duplicated--so don't
-do that.  Exception: In the current implementation, it is always safe to
-delete the item most recently returned by C<each()>, so the following code
-works properly:
+do that.  Exception: It is always safe to delete the item most recently
+returned by C<each()>, so the following code works properly:
 
         while (($key, $value) = each %hash) {
           print $key, "\n";
-- 
1.7.9.5


--------------1.40.perlbug--

[p5pRT]

From @demerphq

On 9 March 2014 15​:26, Paul Johnson <perlbug-followup@​perl.org> wrote​:

# New Ticket Created by "Paul Johnson"
# Please include the string​: [perl #121404]
# in the subject line of all future correspondence about this issue.
# <URL​: https://rt-archive.perl.org/perl5/Ticket/Display.html?id=121404 >

This is a multi-part message in MIME format.
--------------1.40.perlbug
Content-Type​: text/plain; charset=UTF-8; format=fixed
Content-Transfer-Encoding​: 8bit

This is a bug report for perl from paul@​pjcj.net,
generated with the help of perlbug 1.40 running under perl 5.19.10.

-----------------------------------------------------------------
[Please describe your issue here]

In the perlfunc section on "each" we state​:

                                                              Any insertion
into the hash may change the order\, as will any deletion\, with the exception
that the most recent key returned by C\<each> or C\<keys> may be deleted
without changing the order\.

                                            If you add or delete a hash's
elements while iterating over it\, entries may be skipped or duplicated\-\-so
don't do that\.  Exception&#8203;: In the current implementation\, it is always safe
to delete the item most recently returned by C\<each\(\)>\, so the following
code works properly&#8203;:

        while \(\($key\, $value\) = each %hash\) \{
            print $key\, "\\n";
            delete $hash\{$key\};   \# This is safe
        \}

My beef here is with the phrase "In the current implementation". This was
added by Tom Christiansen in bade7fb (perl #89758) as part of a series of
changes to remind "users to put version guards on their neologisms". I'm all
for not promising more than we need to in the documentation, but I think this
particular change might be a step too far.

We promise unconditionally that deleting the most recent key will not change
the iteration order, then we weaken that promise. But are we really thinking
that the above code may one day be illegal? We had promised it would always
be safe since 2000 (74fc8b5).

In addition, the documentation for both "keys" and "values" states​:

                                                              Any insertion
into the hash may change the order\, as will any deletion\, with the exception
that the most recent key returned by C\<each> or C\<keys> may be deleted
without changing the order\.

So perhaps the attached patch is appropriate. Or have I misunderstood
something?

No, your understanding is correct, the documentation is not. It is an
outright guarantee. Whatever we do to the internals of the hash
function we cannot break this.

From e928c36230fdb3137ada5f9c50b66a21712663f0 Mon Sep 17 00​:00​:00 2001
From​: Paul Johnson <paul@​pjcj.net>
Date​: Sun, 9 Mar 2014 15​:07​:54 +0100
Subject​: [PATCH] It is always safe to delete the most recent key.

---
pod/perlfunc.pod | 5 ++---
1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/pod/perlfunc.pod b/pod/perlfunc.pod
index 14c5171..4a3893a 100644
--- a/pod/perlfunc.pod
+++ b/pod/perlfunc.pod
@​@​ -1670,9 +1670,8 @​@​ reached the end as just described; it can be explicitly reset by calling
C<keys> or C<values> on the hash or array. If you add or delete a hash's
elements while iterating over it, the effect on the iterator is
unspecified; for example, entries may be skipped or duplicated--so don't
-do that. Exception​: In the current implementation, it is always safe to
-delete the item most recently returned by C<each()>, so the following code
-works properly​:
+do that. Exception​: It is always safe to delete the item most recently
+returned by C<each()>, so the following code works properly​:

     while \(\($key\, $value\) = each %hash\) \{
       print $key\, "\\n";

--

You can apply this yourself right?

Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

[p5pRT]

The RT System itself - Status changed from 'new' to 'open'

[p5pRT]

From @demerphq

On 10 March 2014 08​:19, Paul Johnson <paul@​pjcj.net> wrote​:

On Mon, Mar 10, 2014 at 08​:13​:12AM +0100, demerphq wrote​:

On 9 March 2014 15​:26, Paul Johnson <perlbug-followup@​perl.org> wrote​:

So perhaps the attached patch is appropriate. Or have I misunderstood
something?

No, your understanding is correct, the documentation is not. It is an
outright guarantee. Whatever we do to the internals of the hash
function we cannot break this.

Thanks for the confirmation.

You can apply this yourself right?

No, I don't have a core commit bit.

Applied as​:

commit d802114
Author​: Paul Johnson <paul@​pjcj.net>
Date​: Mon Mar 10 08​:31​:32 2014 +0100

  It is and always will be safe to delete the most recent key
returned from each.

--
perl -Mre=debug -e "/just|another|perl|hacker/"

[p5pRT]

From @pjcj

On Mon, Mar 10, 2014 at 08​:13​:12AM +0100, demerphq wrote​:

On 9 March 2014 15​:26, Paul Johnson <perlbug-followup@​perl.org> wrote​:

So perhaps the attached patch is appropriate. Or have I misunderstood
something?

No, your understanding is correct, the documentation is not. It is an
outright guarantee. Whatever we do to the internals of the hash
function we cannot break this.

Thanks for the confirmation.

You can apply this yourself right?

No, I don't have a core commit bit.

--
Paul Johnson - paul@​pjcj.net
http​://www.pjcj.net

[p5pRT]

From @rjbs

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org> [2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will not change
the iteration order, then we weaken that promise. But are we really thinking
that the above code may one day be illegal? We had promised it would always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

--
rjbs

[p5pRT]

From @Leont

On Fri, Mar 21, 2014 at 1​:45 AM, Ricardo Signes
<perl.p5p@​rjbs.manxome.org>wrote​:

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org>
[2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will not
change
the iteration order, then we weaken that promise. But are we really
thinking
that the above code may one day be illegal? We had promised it would
always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

I'm somewhat worried about ties, but I guess it's not unreasonable to force
them to support this too.

Leon

[p5pRT]

From @nwc10

On Fri, Mar 21, 2014 at 10​:33​:02AM +0100, Leon Timmermans wrote​:

On Fri, Mar 21, 2014 at 1​:45 AM, Ricardo Signes
<perl.p5p@​rjbs.manxome.org>wrote​:

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org>
[2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will not
change
the iteration order, then we weaken that promise. But are we really
thinking
that the above code may one day be illegal? We had promised it would
always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

I'm somewhat worried about ties, but I guess it's not unreasonable to force
them to support this too.

I think that it's actually impossible to force ties to support this.
For starters, we'd need to "fix" all the *DB*_File modules we ship to
conform. Right now, I think that none do.

I think that we need to

a) clarify that this is Perl's hash implementation.
b) be more careful generally to consider (and describe) tie as a way to map
  foreign things to be accessible with the syntax of Perl builtin types.
  Not strictly and unconditionally to make foreign things behave exactly
  as builtin types, with all the quirks and funky features.

Nicholas Clark

[p5pRT]

From @demerphq

On 21 March 2014 01​:45, Ricardo Signes <perl.p5p@​rjbs.manxome.org> wrote​:

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org> [2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will not change
the iteration order, then we weaken that promise. But are we really thinking
that the above code may one day be illegal? We had promised it would always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

I think that it is truly binding on all normal perl hashes.

Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

[p5pRT]

From @tonycoz

On Fri Mar 21 02​:33​:42 2014, LeonT wrote​:

On Fri, Mar 21, 2014 at 1​:45 AM, Ricardo Signes
<perl.p5p@​rjbs.manxome.org>wrote​:

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org>
[2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will
not
change
the iteration order, then we weaken that promise. But are we
really
thinking
that the above code may one day be illegal? We had promised it
would
always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree
with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

I'm somewhat worried about ties, but I guess it's not unreasonable to
force
them to support this too.

How about the attached?

Tony

[p5pRT]

From @tonycoz

0001-perl-121404-tied-hashes-are-different.patch

From f680130422cd2d8902ffb5569f7c8e10746f47d1 Mon Sep 17 00:00:00 2001
From: Tony Cook <tony@develop-help.com>
Date: Thu, 24 Jul 2014 17:08:17 +1000
Subject: [PATCH] [perl #121404] tied hashes are different

---
 pod/perlfunc.pod |   11 +++++++++--
 pod/perlsec.pod  |    3 +++
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/pod/perlfunc.pod b/pod/perlfunc.pod
index 173615b..ed6f7a8 100644
--- a/pod/perlfunc.pod
+++ b/pod/perlfunc.pod
@@ -1683,6 +1683,9 @@ returned by C<each()>, so the following code works properly:
           delete $hash{$key};   # This is safe
         }
 
+Tied hashes may have a different ordering behaviour to perl's hash
+implmentation.
+
 This prints out your environment like the printenv(1) program,
 but in a different order:
 
@@ -3155,7 +3158,9 @@ rely on C<keys>, C<values> and C<each> to repeatedly return the same order
 as each other.  See L<perlsec/"Algorithmic Complexity Attacks"> for
 details on why hash order is randomized.  Aside from the guarantees
 provided here the exact details of Perl's hash algorithm and the hash
-traversal order are subject to change in any release of Perl.
+traversal order are subject to change in any release of Perl.  Tied hashes
+may behave differently to Perl's hashes with respect to changes in order on
+insertion and deletion of items.
 
 As a side effect, calling keys() resets the internal iterator of the HASH or
 ARRAY (see L</each>).  In particular, calling keys() in void context resets
@@ -8747,7 +8752,9 @@ rely on C<keys>, C<values> and C<each> to repeatedly return the same order
 as each other.  See L<perlsec/"Algorithmic Complexity Attacks"> for
 details on why hash order is randomized.  Aside from the guarantees
 provided here the exact details of Perl's hash algorithm and the hash
-traversal order are subject to change in any release of Perl.
+traversal order are subject to change in any release of Perl.  Tied hashes
+may behave differently to Perl's hashes with respect to changes in order on
+insertion and deletion of items.
 
 As a side effect, calling values() resets the HASH or ARRAY's internal
 iterator, see L</each>.  (In particular, calling values() in void context
diff --git a/pod/perlsec.pod b/pod/perlsec.pod
index 703bd46..b6474e6 100644
--- a/pod/perlsec.pod
+++ b/pod/perlsec.pod
@@ -534,6 +534,9 @@ or the CPAN module C<Algorithm::Numerical::Shuffle>), or for generating
 permutations (use e.g. the CPAN modules C<Algorithm::Permute> or
 C<Algorithm::FastPermute>), or for any cryptographic applications.
 
+Tied hashes may have their own ordering and algorithmic complexity
+attacks.
+
 =item *
 
 Regular expressions - Perl's regular expression engine is so called NFA
-- 
1.7.10.4

[p5pRT]

From @demerphq

Besides the typo on "implmentation" it looks fine to me.

On 24 July 2014 09​:11, Tony Cook via RT <perlbug-followup@​perl.org> wrote​:

On Fri Mar 21 02​:33​:42 2014, LeonT wrote​:

On Fri, Mar 21, 2014 at 1​:45 AM, Ricardo Signes
<perl.p5p@​rjbs.manxome.org>wrote​:

* "Paul Johnson" (via RT) <perlbug-followup@​perl.org>
[2014-03-09T10​:26​:43]

We promise unconditionally that deleting the most recent key will
not
change
the iteration order, then we weaken that promise. But are we
really
thinking
that the above code may one day be illegal? We had promised it
would
always
be safe since 2000 (74fc8b5).

I think that while most of bade7fb seems like great stuff, I agree
with you
here. This promise seems like one we want to consider truly binding.

Anyone else?

I'm somewhat worried about ties, but I guess it's not unreasonable to
force
them to support this too.

How about the attached?

Tony

---
via perlbug​: queue​: perl5 status​: open
https://rt-archive.perl.org/perl5/Ticket/Display.html?id=121404

From f680130422cd2d8902ffb5569f7c8e10746f47d1 Mon Sep 17 00​:00​:00 2001
From​: Tony Cook <tony@​develop-help.com>
Date​: Thu, 24 Jul 2014 17​:08​:17 +1000
Subject​: [PATCH] [perl #121404] tied hashes are different

---
pod/perlfunc.pod | 11 +++++++++--
pod/perlsec.pod | 3 +++
2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/pod/perlfunc.pod b/pod/perlfunc.pod
index 173615b..ed6f7a8 100644
--- a/pod/perlfunc.pod
+++ b/pod/perlfunc.pod
@​@​ -1683,6 +1683,9 @​@​ returned by C<each()>, so the following code works
properly​:
delete $hash{$key}; # This is safe
}

+Tied hashes may have a different ordering behaviour to perl's hash
+implmentation.
+
This prints out your environment like the printenv(1) program,
but in a different order​:

@​@​ -3155,7 +3158,9 @​@​ rely on C<keys>, C<values> and C<each> to repeatedly
return the same order
as each other. See L<perlsec/"Algorithmic Complexity Attacks"> for
details on why hash order is randomized. Aside from the guarantees
provided here the exact details of Perl's hash algorithm and the hash
-traversal order are subject to change in any release of Perl.
+traversal order are subject to change in any release of Perl. Tied hashes
+may behave differently to Perl's hashes with respect to changes in order
on
+insertion and deletion of items.

As a side effect, calling keys() resets the internal iterator of the HASH
or
ARRAY (see L</each>). In particular, calling keys() in void context
resets
@​@​ -8747,7 +8752,9 @​@​ rely on C<keys>, C<values> and C<each> to repeatedly
return the same order
as each other. See L<perlsec/"Algorithmic Complexity Attacks"> for
details on why hash order is randomized. Aside from the guarantees
provided here the exact details of Perl's hash algorithm and the hash
-traversal order are subject to change in any release of Perl.
+traversal order are subject to change in any release of Perl. Tied hashes
+may behave differently to Perl's hashes with respect to changes in order
on
+insertion and deletion of items.

As a side effect, calling values() resets the HASH or ARRAY's internal
iterator, see L</each>. (In particular, calling values() in void context
diff --git a/pod/perlsec.pod b/pod/perlsec.pod
index 703bd46..b6474e6 100644
--- a/pod/perlsec.pod
+++ b/pod/perlsec.pod
@​@​ -534,6 +534,9 @​@​ or the CPAN module C<Algorithm​::Numerical​::Shuffle>),
or for generating
permutations (use e.g. the CPAN modules C<Algorithm​::Permute> or
C<Algorithm​::FastPermute>), or for any cryptographic applications.

+Tied hashes may have their own ordering and algorithmic complexity
+attacks.
+
=item *

Regular expressions - Perl's regular expression engine is so called NFA
--
1.7.10.4

--
perl -Mre=debug -e "/just|another|perl|hacker/"

[p5pRT]

From @tonycoz

On Thu Jul 24 00​:20​:20 2014, demerphq wrote​:

Besides the typo on "implmentation" it looks fine to me.

Thanks for pointing that out.

Applied witha fix to "implmentation" as 883f220.

Tony

[p5pRT]

@tonycoz - Status changed from 'open' to 'resolved'