detect each() after insert and produce warnings when we do
authorYves Orton <demerphq@gmail.com>
Sun, 17 Mar 2013 23:28:03 +0000 (00:28 +0100)
committerYves Orton <demerphq@gmail.com>
Mon, 18 Mar 2013 23:23:12 +0000 (00:23 +0100)
Inserting into a hash that is being traversed with each()
has always produced undefined behavior. With hash traversal
randomization this is more pronounced, and at the same
time relatively easy to spot. At the cost of an extra U32
in the xpvhv_aux structure we can detect that the xhv_rand
has changed and then produce a warning if it has.

It was suggested on IRC that this should produce a fatal
error, but I couldn't see a clean way to manage that with
"strict", it was much easier to create a "severe" (internal)
warning, which is enabled by default but suppressible with
C<no warnings "internal";> if people /really/ wanted.

hv.c
hv.h
pod/perldiag.pod
t/op/each.t

index 5fc0296..0821841 100644 (file)
--- a/hv.c
+++ b/hv.c
@@ -1611,6 +1611,7 @@ Perl_hfree_next_entry(pTHX_ HV *hv, STRLEN *indexp)
        }
        iter->xhv_riter = -1;   /* HvRITER(hv) = -1 */
        iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */
+        iter->xhv_last_rand = iter->xhv_rand;
     }
 
     if (!((XPVHV*)SvANY(hv))->xhv_keys)
@@ -1848,12 +1849,15 @@ S_hv_auxinit(pTHX_ HV *hv) {
         SvOOK_on(hv);
         PL_hash_rand_bits += ptr_hash((PTRV)array);
         PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1);
+        iter = HvAUX(hv);
+        iter->xhv_rand = (U32)PL_hash_rand_bits;
+    } else {
+        iter = HvAUX(hv);
     }
-    iter = HvAUX(hv);
 
     iter->xhv_riter = -1;      /* HvRITER(hv) = -1 */
     iter->xhv_eiter = NULL;    /* HvEITER(hv) = NULL */
-    iter->xhv_rand = (U32)PL_hash_rand_bits;
+    iter->xhv_last_rand = iter->xhv_rand;
     iter->xhv_name_u.xhvnameu_name = 0;
     iter->xhv_name_count = 0;
     iter->xhv_backreferences = 0;
@@ -1896,6 +1900,7 @@ Perl_hv_iterinit(pTHX_ HV *hv)
        }
        iter->xhv_riter = -1;   /* HvRITER(hv) = -1 */
        iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */
+        iter->xhv_last_rand = iter->xhv_rand;
     } else {
        hv_auxinit(hv);
     }
@@ -2355,6 +2360,15 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
             }
        }
     }
+    if (iter->xhv_last_rand != iter->xhv_rand) {
+        if (iter->xhv_riter != -1) {
+            Perl_ck_warner_d(aTHX_ packWARN(WARN_INTERNAL),
+                             "Use of each() on hash after insertion without resetting hash iterator results in undefined behavior"
+                             pTHX__FORMAT
+                             pTHX__VALUE);
+        }
+        iter->xhv_last_rand = iter->xhv_rand;
+    }
 
     /* Skip the entire loop if the hash is empty.   */
     if ((flags & HV_ITERNEXT_WANTPLACEHOLDERS)
@@ -2366,6 +2380,7 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
            if (iter->xhv_riter > (I32)xhv->xhv_max /* HvRITER(hv) > HvMAX(hv) */) {
                /* There is no next one.  End of the hash.  */
                iter->xhv_riter = -1; /* HvRITER(hv) = -1 */
+                iter->xhv_last_rand = iter->xhv_rand;
                break;
            }
             entry = (HvARRAY(hv))[(iter->xhv_riter ^ iter->xhv_rand) & xhv->xhv_max];
@@ -2381,7 +2396,10 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
               or if we run through it and find only placeholders.  */
        }
     }
-    else iter->xhv_riter = -1;
+    else {
+        iter->xhv_riter = -1;
+        iter->xhv_last_rand = iter->xhv_rand;
+    }
 
     if (oldentry && HvLAZYDEL(hv)) {           /* was deleted earlier? */
        HvLAZYDEL_off(hv);
diff --git a/hv.h b/hv.h
index f2dd8e1..e6b9bb8 100644 (file)
--- a/hv.h
+++ b/hv.h
@@ -93,6 +93,8 @@ struct xpvhv_aux {
     struct mro_meta *xhv_mro_meta;
     HV *       xhv_super;      /* SUPER method cache */
     U32         xhv_rand;       /* random value for hash traversal */
+    U32         xhv_last_rand;  /* last random value for hash traversal,
+                                   used to detect each() after insert for warnings */
 };
 
 /* hash structure: */
index 8d29e2d..d9ebe57 100644 (file)
@@ -5667,6 +5667,12 @@ or if you meant this
 
 You need to add either braces or blanks to disambiguate.
 
+=item Use of each() on hash after insertion without resetting hash iterator results in undefined behavior
+
+(S internal) The behavior of C<each()> after insertion is undefined, it may
+skip items, or visit items more than once. Consider using C<keys()> instead
+of C<each()>.
+
 =item Useless assignment to a temporary
 
 (W misc) You assigned to an lvalue subroutine, but what
index d12d678..be8aa48 100644 (file)
@@ -6,7 +6,7 @@ BEGIN {
     require './test.pl';
 }
 
-plan tests => 57;
+plan tests => 59;
 
 $h{'abc'} = 'ABC';
 $h{'def'} = 'DEF';
@@ -269,3 +269,22 @@ for my $k (qw(each keys values)) {
     is join ("-", each %h), '1-2',
        'each on apparently empty hash does not leave RITER set';
 }
+{
+    my $warned= 0;
+    local $SIG{__WARN__}= sub {
+        /\QUse of each() on hash after insertion without resetting hash iterator results in undefined behavior\E/
+            and $warned++ for @_;
+    };
+    my %h= map { $_ => $_ } "A".."F";
+    while (my ($k, $v)= each %h) {
+        $h{"$k$k"}= $v;
+    }
+    ok($warned,"each() after insert produces warnings");
+    no warnings 'internal';
+    $warned= 0;
+    %h= map { $_ => $_ } "A".."F";
+    while (my ($k, $v)= each %h) {
+        $h{"$k$k"}= $v;
+    }
+    ok(!$warned, "no warnings 'internal' silences each() after insert warnings");
+}