mro.c

   1 /*    mro.c
   2  *
   3  *    Copyright (c) 2007 Brandon L Black
   4  *    Copyright (c) 2007, 2008, 2009, 2010, 2011 Larry Wall and others
   5  *
   6  *    You may distribute under the terms of either the GNU General Public
   7  *    License or the Artistic License, as specified in the README file.
   8  *
   9  */
  10
  11 /*
  12  * 'Which order shall we go in?' said Frodo.  'Eldest first, or quickest first?
  13  *  You'll be last either way, Master Peregrin.'
  14  *
  15  *     [p.101 of _The Lord of the Rings_, I/iii: "A Conspiracy Unmasked"]
  16  */
  17
  18 /*
  19 =head1 MRO Functions
  20 These functions are related to the method resolution order of perl classes
  21
  22 =cut
  23 */
  24
  25 #include "EXTERN.h"
  26 #define PERL_IN_MRO_C
  27 #include "perl.h"
  28
  29 static const struct mro_alg dfs_alg =
  30     {S_mro_get_linear_isa_dfs, "dfs", 3, 0, 0};
  31
  32 SV *
  33 Perl_mro_get_private_data(pTHX_ struct mro_meta *const smeta,
  34                           const struct mro_alg *const which)
  35 {
  36     SV **data;
  37     PERL_ARGS_ASSERT_MRO_GET_PRIVATE_DATA;
  38
  39     data = (SV **)Perl_hv_common(aTHX_ smeta->mro_linear_all, NULL,
  40                                  which->name, which->length, which->kflags,
  41                                  HV_FETCH_JUST_SV, NULL, which->hash);
  42     if (!data)
  43         return NULL;
  44
  45     /* If we've been asked to look up the private data for the current MRO, then
  46        cache it.  */
  47     if (smeta->mro_which == which)
  48         smeta->mro_linear_current = *data;
  49
  50     return *data;
  51 }
  52
  53 SV *
  54 Perl_mro_set_private_data(pTHX_ struct mro_meta *const smeta,
  55                           const struct mro_alg *const which, SV *const data)
  56 {
  57     PERL_ARGS_ASSERT_MRO_SET_PRIVATE_DATA;
  58
  59     if (!smeta->mro_linear_all) {
  60         if (smeta->mro_which == which) {
  61             /* If all we need to store is the current MRO's data, then don't use
  62                memory on a hash with 1 element - store it direct, and signal
  63                this by leaving the would-be-hash NULL.  */
  64             smeta->mro_linear_current = data;
  65             return data;
  66         } else {
  67             HV *const hv = newHV();
  68             /* Start with 2 buckets. It's unlikely we'll need more. */
  69             HvMAX(hv) = 1;
  70             smeta->mro_linear_all = hv;
  71
  72             if (smeta->mro_linear_current) {
  73                 /* If we were storing something directly, put it in the hash
  74                    before we lose it. */
  75                 Perl_mro_set_private_data(aTHX_ smeta, smeta->mro_which,
  76                                           smeta->mro_linear_current);
  77             }
  78         }
  79     }
  80
  81     /* We get here if we're storing more than one linearisation for this stash,
  82        or the linearisation we are storing is not that if its current MRO.  */
  83
  84     if (smeta->mro_which == which) {
  85         /* If we've been asked to store the private data for the current MRO,
  86            then cache it.  */
  87         smeta->mro_linear_current = data;
  88     }
  89
  90     if (!Perl_hv_common(aTHX_ smeta->mro_linear_all, NULL,
  91                         which->name, which->length, which->kflags,
  92                         HV_FETCH_ISSTORE, data, which->hash)) {
  93         Perl_croak(aTHX_ "panic: hv_store() failed in set_mro_private_data() "
  94                    "for '%.*s' %d", (int) which->length, which->name,
  95                    which->kflags);
  96     }
  97
  98     return data;
  99 }
 100
 101 const struct mro_alg *
 102 Perl_mro_get_from_name(pTHX_ SV *name) {
 103     SV **data;
 104
 105     PERL_ARGS_ASSERT_MRO_GET_FROM_NAME;
 106
 107     data = (SV **)Perl_hv_common(aTHX_ PL_registered_mros, name, NULL, 0, 0,
 108                                  HV_FETCH_JUST_SV, NULL, 0);
 109     if (!data)
 110         return NULL;
 111     assert(SvTYPE(*data) == SVt_IV);
 112     assert(SvIOK(*data));
 113     return INT2PTR(const struct mro_alg *, SvUVX(*data));
 114 }
 115
 116 /*
 117 =for apidoc mro_register
 118 Registers a custom mro plugin.  See L<perlmroapi> for details.
 119
 120 =cut
 121 */
 122
 123 void
 124 Perl_mro_register(pTHX_ const struct mro_alg *mro) {
 125     SV *wrapper = newSVuv(PTR2UV(mro));
 126
 127     PERL_ARGS_ASSERT_MRO_REGISTER;
 128
 129
 130     if (!Perl_hv_common(aTHX_ PL_registered_mros, NULL,
 131                         mro->name, mro->length, mro->kflags,
 132                         HV_FETCH_ISSTORE, wrapper, mro->hash)) {
 133         SvREFCNT_dec_NN(wrapper);
 134         Perl_croak(aTHX_ "panic: hv_store() failed in mro_register() "
 135                    "for '%.*s' %d", (int) mro->length, mro->name, mro->kflags);
 136     }
 137 }
 138
 139 struct mro_meta*
 140 Perl_mro_meta_init(pTHX_ HV* stash)
 141 {
 142     struct mro_meta* newmeta;
 143
 144     PERL_ARGS_ASSERT_MRO_META_INIT;
 145     assert(HvAUX(stash));
 146     assert(!(HvAUX(stash)->xhv_mro_meta));
 147     Newxz(newmeta, 1, struct mro_meta);
 148     HvAUX(stash)->xhv_mro_meta = newmeta;
 149     newmeta->cache_gen = 1;
 150     newmeta->pkg_gen = 1;
 151     newmeta->mro_which = &dfs_alg;
 152
 153     return newmeta;
 154 }
 155
 156 #if defined(USE_ITHREADS)
 157
 158 /* for sv_dup on new threads */
 159 struct mro_meta*
 160 Perl_mro_meta_dup(pTHX_ struct mro_meta* smeta, CLONE_PARAMS* param)
 161 {
 162     struct mro_meta* newmeta;
 163
 164     PERL_ARGS_ASSERT_MRO_META_DUP;
 165
 166     Newx(newmeta, 1, struct mro_meta);
 167     Copy(smeta, newmeta, 1, struct mro_meta);
 168
 169     if (newmeta->mro_linear_all) {
 170         newmeta->mro_linear_all
 171             = MUTABLE_HV(sv_dup_inc((const SV *)newmeta->mro_linear_all, param));
 172         /* This is just acting as a shortcut pointer, and will be automatically
 173            updated on the first get.  */
 174         newmeta->mro_linear_current = NULL;
 175     } else if (newmeta->mro_linear_current) {
 176         /* Only the current MRO is stored, so this owns the data.  */
 177         newmeta->mro_linear_current
 178             = sv_dup_inc((const SV *)newmeta->mro_linear_current, param);
 179     }
 180
 181     if (newmeta->mro_nextmethod)
 182         newmeta->mro_nextmethod
 183             = MUTABLE_HV(sv_dup_inc((const SV *)newmeta->mro_nextmethod, param));
 184     if (newmeta->isa)
 185         newmeta->isa
 186             = MUTABLE_HV(sv_dup_inc((const SV *)newmeta->isa, param));
 187
 188     newmeta->super = NULL;
 189
 190     return newmeta;
 191 }
 192
 193 #endif /* USE_ITHREADS */
 194
 195 /*
 196 =for apidoc mro_get_linear_isa_dfs
 197
 198 Returns the Depth-First Search linearization of @ISA
 199 the given stash.  The return value is a read-only AV*.
 200 C<level> should be 0 (it is used internally in this
 201 function's recursion).
 202
 203 You are responsible for C<SvREFCNT_inc()> on the
 204 return value if you plan to store it anywhere
 205 semi-permanently (otherwise it might be deleted
 206 out from under you the next time the cache is
 207 invalidated).
 208
 209 =cut
 210 */
 211 static AV*
 212 S_mro_get_linear_isa_dfs(pTHX_ HV *stash, U32 level)
 213 {
 214     AV* retval;
 215     GV** gvp;
 216     GV* gv;
 217     AV* av;
 218     const HEK* stashhek;
 219     struct mro_meta* meta;
 220     SV *our_name;
 221     HV *stored = NULL;
 222
 223     PERL_ARGS_ASSERT_MRO_GET_LINEAR_ISA_DFS;
 224     assert(HvAUX(stash));
 225
 226     stashhek
 227      = HvAUX(stash)->xhv_name_u.xhvnameu_name && HvENAME_HEK_NN(stash)
 228         ? HvENAME_HEK_NN(stash)
 229         : HvNAME_HEK(stash);
 230
 231     if (!stashhek)
 232       Perl_croak(aTHX_ "Can't linearize anonymous symbol table");
 233
 234     if (level > 100)
 235         Perl_croak(aTHX_
 236                   "Recursive inheritance detected in package '%"HEKf"'",
 237                    HEKfARG(stashhek));
 238
 239     meta = HvMROMETA(stash);
 240
 241     /* return cache if valid */
 242     if((retval = MUTABLE_AV(MRO_GET_PRIVATE_DATA(meta, &dfs_alg)))) {
 243         return retval;
 244     }
 245
 246     /* not in cache, make a new one */
 247
 248     retval = MUTABLE_AV(sv_2mortal(MUTABLE_SV(newAV())));
 249     /* We use this later in this function, but don't need a reference to it
 250        beyond the end of this function, so reference count is fine.  */
 251     our_name = newSVhek(stashhek);
 252     av_push(retval, our_name); /* add ourselves at the top */
 253
 254     /* fetch our @ISA */
 255     gvp = (GV**)hv_fetchs(stash, "ISA", FALSE);
 256     av = (gvp && (gv = *gvp) && isGV_with_GP(gv)) ? GvAV(gv) : NULL;
 257
 258     /* "stored" is used to keep track of all of the classnames we have added to
 259        the MRO so far, so we can do a quick exists check and avoid adding
 260        duplicate classnames to the MRO as we go.
 261        It's then retained to be re-used as a fast lookup for ->isa(), by adding
 262        our own name and "UNIVERSAL" to it.  */
 263
 264     if(av && AvFILLp(av) >= 0) {
 265
 266         SV **svp = AvARRAY(av);
 267         I32 items = AvFILLp(av) + 1;
 268
 269         /* foreach(@ISA) */
 270         while (items--) {
 271             SV* const sv = *svp ? *svp : &PL_sv_undef;
 272             HV* const basestash = gv_stashsv(sv, 0);
 273             SV *const *subrv_p;
 274             I32 subrv_items;
 275             svp++;
 276
 277             if (!basestash) {
 278                 /* if no stash exists for this @ISA member,
 279                    simply add it to the MRO and move on */
 280                 subrv_p = &sv;
 281                 subrv_items = 1;
 282             }
 283             else {
 284                 /* otherwise, recurse into ourselves for the MRO
 285                    of this @ISA member, and append their MRO to ours.
 286                    The recursive call could throw an exception, which
 287                    has memory management implications here, hence the use of
 288                    the mortal.  */
 289                 const AV *const subrv
 290                     = mro_get_linear_isa_dfs(basestash, level + 1);
 291
 292                 subrv_p = AvARRAY(subrv);
 293                 subrv_items = AvFILLp(subrv) + 1;
 294             }
 295             if (stored) {
 296                 while(subrv_items--) {
 297                     SV *const subsv = *subrv_p++;
 298                     /* LVALUE fetch will create a new undefined SV if necessary
 299                      */
 300                     HE *const he = hv_fetch_ent(stored, subsv, 1, 0);
 301                     assert(he);
 302                     if(HeVAL(he) != &PL_sv_undef) {
 303                         /* It was newly created.  Steal it for our new SV, and
 304                            replace it in the hash with the "real" thing.  */
 305                         SV *const val = HeVAL(he);
 306                         HEK *const key = HeKEY_hek(he);
 307
 308                         HeVAL(he) = &PL_sv_undef;
 309                         /* Save copying by making a shared hash key scalar. We
 310                            inline this here rather than calling
 311                            Perl_newSVpvn_share because we already have the
 312                            scalar, and we already have the hash key.  */
 313                         assert(SvTYPE(val) == SVt_NULL);
 314                         sv_upgrade(val, SVt_PV);
 315                         SvPV_set(val, HEK_KEY(share_hek_hek(key)));
 316                         SvCUR_set(val, HEK_LEN(key));
 317                         SvIsCOW_on(val);
 318                         SvPOK_on(val);
 319                         if (HEK_UTF8(key))
 320                             SvUTF8_on(val);
 321
 322                         av_push(retval, val);
 323                     }
 324                 }
 325             } else {
 326                 /* We are the first (or only) parent. We can short cut the
 327                    complexity above, because our @ISA is simply us prepended
 328                    to our parent's @ISA, and our ->isa cache is simply our
 329                    parent's, with our name added.  */
 330                 /* newSVsv() is slow. This code is only faster if we can avoid
 331                    it by ensuring that SVs in the arrays are shared hash key
 332                    scalar SVs, because we can "copy" them very efficiently.
 333                    Although to be fair, we can't *ensure* this, as a reference
 334                    to the internal array is returned by mro::get_linear_isa(),
 335                    so we'll have to be defensive just in case someone faffed
 336                    with it.  */
 337                 if (basestash) {
 338                     SV **svp;
 339                     stored = MUTABLE_HV(sv_2mortal((SV*)newHVhv(HvMROMETA(basestash)->isa)));
 340                     av_extend(retval, subrv_items);
 341                     AvFILLp(retval) = subrv_items;
 342                     svp = AvARRAY(retval);
 343                     while(subrv_items--) {
 344                         SV *const val = *subrv_p++;
 345                         *++svp = SvIsCOW_shared_hash(val)
 346                             ? newSVhek(SvSHARED_HEK_FROM_PV(SvPVX(val)))
 347                             : newSVsv(val);
 348                     }
 349                 } else {
 350                     /* They have no stash.  So create ourselves an ->isa cache
 351                        as if we'd copied it from what theirs should be.  */
 352                     stored = MUTABLE_HV(sv_2mortal(MUTABLE_SV(newHV())));
 353                     (void) hv_store(stored, "UNIVERSAL", 9, &PL_sv_undef, 0);
 354                     av_push(retval,
 355                             newSVhek(HeKEY_hek(hv_store_ent(stored, sv,
 356                                                             &PL_sv_undef, 0))));
 357                 }
 358             }
 359         }
 360     } else {
 361         /* We have no parents.  */
 362         stored = MUTABLE_HV(sv_2mortal(MUTABLE_SV(newHV())));
 363         (void) hv_store(stored, "UNIVERSAL", 9, &PL_sv_undef, 0);
 364     }
 365
 366     (void) hv_store_ent(stored, our_name, &PL_sv_undef, 0);
 367
 368     SvREFCNT_inc_simple_void_NN(stored);
 369     SvTEMP_off(stored);
 370     SvREADONLY_on(stored);
 371
 372     meta->isa = stored;
 373
 374     /* now that we're past the exception dangers, grab our own reference to
 375        the AV we're about to use for the result. The reference owned by the
 376        mortals' stack will be released soon, so everything will balance.  */
 377     SvREFCNT_inc_simple_void_NN(retval);
 378     SvTEMP_off(retval);
 379
 380     /* we don't want anyone modifying the cache entry but us,
 381        and we do so by replacing it completely */
 382     SvREADONLY_on(retval);
 383
 384     return MUTABLE_AV(Perl_mro_set_private_data(aTHX_ meta, &dfs_alg,
 385                                                 MUTABLE_SV(retval)));
 386 }
 387
 388 /*
 389 =for apidoc mro_get_linear_isa
 390
 391 Returns the mro linearisation for the given stash.  By default, this
 392 will be whatever C<mro_get_linear_isa_dfs> returns unless some
 393 other MRO is in effect for the stash.  The return value is a
 394 read-only AV*.
 395
 396 You are responsible for C<SvREFCNT_inc()> on the
 397 return value if you plan to store it anywhere
 398 semi-permanently (otherwise it might be deleted
 399 out from under you the next time the cache is
 400 invalidated).
 401
 402 =cut
 403 */
 404 AV*
 405 Perl_mro_get_linear_isa(pTHX_ HV *stash)
 406 {
 407     struct mro_meta* meta;
 408     AV *isa;
 409
 410     PERL_ARGS_ASSERT_MRO_GET_LINEAR_ISA;
 411     if(!SvOOK(stash))
 412         Perl_croak(aTHX_ "Can't linearize anonymous symbol table");
 413
 414     meta = HvMROMETA(stash);
 415     if (!meta->mro_which)
 416         Perl_croak(aTHX_ "panic: invalid MRO!");
 417     isa = meta->mro_which->resolve(aTHX_ stash, 0);
 418
 419     if (meta->mro_which != &dfs_alg) { /* skip for dfs, for speed */
 420         SV * const namesv =
 421             (HvENAME(stash)||HvNAME(stash))
 422               ? newSVhek(HvENAME_HEK(stash)
 423                           ? HvENAME_HEK(stash)
 424                           : HvNAME_HEK(stash))
 425               : NULL;
 426
 427         if(namesv && (AvFILLp(isa) == -1 || !sv_eq(*AvARRAY(isa), namesv)))
 428         {
 429             AV * const old = isa;
 430             SV **svp;
 431             SV **ovp = AvARRAY(old);
 432             SV * const * const oend = ovp + AvFILLp(old) + 1;
 433             isa = (AV *)sv_2mortal((SV *)newAV());
 434             av_extend(isa, AvFILLp(isa) = AvFILLp(old)+1);
 435             *AvARRAY(isa) = namesv;
 436             svp = AvARRAY(isa)+1;
 437             while (ovp < oend) *svp++ = SvREFCNT_inc(*ovp++);
 438         }
 439         else SvREFCNT_dec(namesv);
 440     }
 441
 442     if (!meta->isa) {
 443             HV *const isa_hash = newHV();
 444             /* Linearisation didn't build it for us, so do it here.  */
 445             SV *const *svp = AvARRAY(isa);
 446             SV *const *const svp_end = svp + AvFILLp(isa) + 1;
 447             const HEK *canon_name = HvENAME_HEK(stash);
 448             if (!canon_name) canon_name = HvNAME_HEK(stash);
 449
 450             while (svp < svp_end) {
 451                 (void) hv_store_ent(isa_hash, *svp++, &PL_sv_undef, 0);
 452             }
 453
 454             (void) hv_common(isa_hash, NULL, HEK_KEY(canon_name),
 455                              HEK_LEN(canon_name), HEK_FLAGS(canon_name),
 456                              HV_FETCH_ISSTORE, &PL_sv_undef,
 457                              HEK_HASH(canon_name));
 458             (void) hv_store(isa_hash, "UNIVERSAL", 9, &PL_sv_undef, 0);
 459
 460             SvREADONLY_on(isa_hash);
 461
 462             meta->isa = isa_hash;
 463     }
 464
 465     return isa;
 466 }
 467
 468 /*
 469 =for apidoc mro_isa_changed_in
 470
 471 Takes the necessary steps (cache invalidations, mostly)
 472 when the @ISA of the given package has changed.  Invoked
 473 by the C<setisa> magic, should not need to invoke directly.
 474
 475 =cut
 476 */
 477
 478 /* Macro to avoid repeating the code five times. */
 479 #define CLEAR_LINEAR(mEta)                                     \
 480     if (mEta->mro_linear_all) {                                 \
 481         SvREFCNT_dec(MUTABLE_SV(mEta->mro_linear_all));          \
 482         mEta->mro_linear_all = NULL;                              \
 483         /* This is just acting as a shortcut pointer.  */          \
 484         mEta->mro_linear_current = NULL;                            \
 485     } else if (mEta->mro_linear_current) {                           \
 486         /* Only the current MRO is stored, so this owns the data.  */ \
 487         SvREFCNT_dec(mEta->mro_linear_current);                        \
 488         mEta->mro_linear_current = NULL;                                \
 489     }
 490
 491 void
 492 Perl_mro_isa_changed_in(pTHX_ HV* stash)
 493 {
 494     dVAR;
 495     HV* isarev;
 496     AV* linear_mro;
 497     HE* iter;
 498     SV** svp;
 499     I32 items;
 500     bool is_universal;
 501     struct mro_meta * meta;
 502     HV *isa = NULL;
 503
 504     const HEK * const stashhek = HvENAME_HEK(stash);
 505     const char * const stashname = HvENAME_get(stash);
 506     const STRLEN stashname_len = HvENAMELEN_get(stash);
 507
 508     PERL_ARGS_ASSERT_MRO_ISA_CHANGED_IN;
 509
 510     if(!stashname)
 511         Perl_croak(aTHX_ "Can't call mro_isa_changed_in() on anonymous symbol table");
 512
 513
 514     /* wipe out the cached linearizations for this stash */
 515     meta = HvMROMETA(stash);
 516     CLEAR_LINEAR(meta);
 517     if (meta->isa) {
 518         /* Steal it for our own purposes. */
 519         isa = (HV *)sv_2mortal((SV *)meta->isa);
 520         meta->isa = NULL;
 521     }
 522
 523     /* Inc the package generation, since our @ISA changed */
 524     meta->pkg_gen++;
 525
 526     /* Wipe the global method cache if this package
 527        is UNIVERSAL or one of its parents */
 528
 529     svp = hv_fetchhek(PL_isarev, stashhek, 0);
 530     isarev = svp ? MUTABLE_HV(*svp) : NULL;
 531
 532     if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
 533         || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
 534         PL_sub_generation++;
 535         is_universal = TRUE;
 536     }
 537     else { /* Wipe the local method cache otherwise */
 538         meta->cache_gen++;
 539         is_universal = FALSE;
 540     }
 541
 542     /* wipe next::method cache too */
 543     if(meta->mro_nextmethod) hv_clear(meta->mro_nextmethod);
 544
 545     /* Changes to @ISA might turn overloading on */
 546     HvAMAGIC_on(stash);
 547     /* pessimise derefs for now. Will get recalculated by Gv_AMupdate() */
 548     HvAUX(stash)->xhv_aux_flags &= ~HvAUXf_NO_DEREF;
 549
 550     /* DESTROY can be cached in SvSTASH. */
 551     if (!SvOBJECT(stash)) SvSTASH(stash) = NULL;
 552
 553     /* Iterate the isarev (classes that are our children),
 554        wiping out their linearization, method and isa caches
 555        and upating PL_isarev. */
 556     if(isarev) {
 557         HV *isa_hashes = NULL;
 558
 559        /* We have to iterate through isarev twice to avoid a chicken and
 560         * egg problem: if A inherits from B and both are in isarev, A might
 561         * be processed before B and use B's previous linearisation.
 562         */
 563
 564        /* First iteration: Wipe everything, but stash away the isa hashes
 565         * since we still need them for updating PL_isarev.
 566         */
 567
 568         if(hv_iterinit(isarev)) {
 569             /* Only create the hash if we need it; i.e., if isarev has
 570                any elements. */
 571             isa_hashes = (HV *)sv_2mortal((SV *)newHV());
 572         }
 573         while((iter = hv_iternext(isarev))) {
 574             HV* revstash = gv_stashsv(hv_iterkeysv(iter), 0);
 575             struct mro_meta* revmeta;
 576
 577             if(!revstash) continue;
 578             revmeta = HvMROMETA(revstash);
 579             CLEAR_LINEAR(revmeta);
 580             if(!is_universal)
 581                 revmeta->cache_gen++;
 582             if(revmeta->mro_nextmethod)
 583                 hv_clear(revmeta->mro_nextmethod);
 584             if (!SvOBJECT(revstash)) SvSTASH(revstash) = NULL;
 585
 586             (void)
 587               hv_store(
 588                isa_hashes, (const char*)&revstash, sizeof(HV *),
 589                revmeta->isa ? (SV *)revmeta->isa : &PL_sv_undef, 0
 590               );
 591             revmeta->isa = NULL;
 592         }
 593
 594        /* Second pass: Update PL_isarev. We can just use isa_hashes to
 595         * avoid another round of stash lookups. */
 596
 597        /* isarev might be deleted from PL_isarev during this loop, so hang
 598         * on to it. */
 599         SvREFCNT_inc_simple_void_NN(sv_2mortal((SV *)isarev));
 600
 601         if(isa_hashes) {
 602             hv_iterinit(isa_hashes);
 603             while((iter = hv_iternext(isa_hashes))) {
 604                 HV* const revstash = *(HV **)HEK_KEY(HeKEY_hek(iter));
 605                 HV * const isa = (HV *)HeVAL(iter);
 606                 const HEK *namehek;
 607
 608                 /* We're starting at the 2nd element, skipping revstash */
 609                 linear_mro = mro_get_linear_isa(revstash);
 610                 svp = AvARRAY(linear_mro) + 1;
 611                 items = AvFILLp(linear_mro);
 612
 613                 namehek = HvENAME_HEK(revstash);
 614                 if (!namehek) namehek = HvNAME_HEK(revstash);
 615
 616                 while (items--) {
 617                     SV* const sv = *svp++;
 618                     HV* mroisarev;
 619
 620                     HE *he = hv_fetch_ent(PL_isarev, sv, TRUE, 0);
 621
 622                     /* That fetch should not fail.  But if it had to create
 623                        a new SV for us, then will need to upgrade it to an
 624                        HV (which sv_upgrade() can now do for us). */
 625
 626                     mroisarev = MUTABLE_HV(HeVAL(he));
 627
 628                     SvUPGRADE(MUTABLE_SV(mroisarev), SVt_PVHV);
 629
 630                     /* This hash only ever contains PL_sv_yes. Storing it
 631                        over itself is almost as cheap as calling hv_exists,
 632                        so on aggregate we expect to save time by not making
 633                        two calls to the common HV code for the case where
 634                        it doesn't exist.  */
 635
 636                     (void)
 637                       hv_storehek(mroisarev, namehek, &PL_sv_yes);
 638                 }
 639
 640                 if ((SV *)isa != &PL_sv_undef) {
 641                     assert(namehek);
 642                     mro_clean_isarev(
 643                      isa, HEK_KEY(namehek), HEK_LEN(namehek),
 644                      HvMROMETA(revstash)->isa, HEK_HASH(namehek),
 645                      HEK_UTF8(namehek)
 646                     );
 647                 }
 648             }
 649         }
 650     }
 651
 652     /* Now iterate our MRO (parents), adding ourselves and everything from
 653        our isarev to their isarev.
 654     */
 655
 656     /* We're starting at the 2nd element, skipping ourselves here */
 657     linear_mro = mro_get_linear_isa(stash);
 658     svp = AvARRAY(linear_mro) + 1;
 659     items = AvFILLp(linear_mro);
 660
 661     while (items--) {
 662         SV* const sv = *svp++;
 663         HV* mroisarev;
 664
 665         HE *he = hv_fetch_ent(PL_isarev, sv, TRUE, 0);
 666
 667         /* That fetch should not fail.  But if it had to create a new SV for
 668            us, then will need to upgrade it to an HV (which sv_upgrade() can
 669            now do for us. */
 670
 671         mroisarev = MUTABLE_HV(HeVAL(he));
 672
 673         SvUPGRADE(MUTABLE_SV(mroisarev), SVt_PVHV);
 674
 675         /* This hash only ever contains PL_sv_yes. Storing it over itself is
 676            almost as cheap as calling hv_exists, so on aggregate we expect to
 677            save time by not making two calls to the common HV code for the
 678            case where it doesn't exist.  */
 679
 680         (void)hv_storehek(mroisarev, stashhek, &PL_sv_yes);
 681     }
 682
 683     /* Delete our name from our former parents' isarevs. */
 684     if(isa && HvARRAY(isa))
 685         mro_clean_isarev(isa, stashname, stashname_len, meta->isa,
 686                          HEK_HASH(stashhek), HEK_UTF8(stashhek));
 687 }
 688
 689 /* Deletes name from all the isarev entries listed in isa */
 690 STATIC void
 691 S_mro_clean_isarev(pTHX_ HV * const isa, const char * const name,
 692                          const STRLEN len, HV * const exceptions, U32 hash,
 693                          U32 flags)
 694 {
 695     HE* iter;
 696
 697     PERL_ARGS_ASSERT_MRO_CLEAN_ISAREV;
 698
 699     /* Delete our name from our former parents' isarevs. */
 700     if(isa && HvARRAY(isa) && hv_iterinit(isa)) {
 701         SV **svp;
 702         while((iter = hv_iternext(isa))) {
 703             I32 klen;
 704             const char * const key = hv_iterkey(iter, &klen);
 705             if(exceptions && hv_exists(exceptions, key, HeKUTF8(iter) ? -klen : klen))
 706                 continue;
 707             svp = hv_fetch(PL_isarev, key, HeKUTF8(iter) ? -klen : klen, 0);
 708             if(svp) {
 709                 HV * const isarev = (HV *)*svp;
 710                 (void)hv_common(isarev, NULL, name, len, flags,
 711                                 G_DISCARD|HV_DELETE, NULL, hash);
 712                 if(!HvARRAY(isarev) || !HvUSEDKEYS(isarev))
 713                     (void)hv_delete(PL_isarev, key,
 714                                         HeKUTF8(iter) ? -klen : klen, G_DISCARD);
 715             }
 716         }
 717     }
 718 }
 719
 720 /*
 721 =for apidoc mro_package_moved
 722
 723 Call this function to signal to a stash that it has been assigned to
 724 another spot in the stash hierarchy.  C<stash> is the stash that has been
 725 assigned.  C<oldstash> is the stash it replaces, if any.  C<gv> is the glob
 726 that is actually being assigned to.
 727
 728 This can also be called with a null first argument to
 729 indicate that C<oldstash> has been deleted.
 730
 731 This function invalidates isa caches on the old stash, on all subpackages
 732 nested inside it, and on the subclasses of all those, including
 733 non-existent packages that have corresponding entries in C<stash>.
 734
 735 It also sets the effective names (C<HvENAME>) on all the stashes as
 736 appropriate.
 737
 738 If the C<gv> is present and is not in the symbol table, then this function
 739 simply returns.  This checked will be skipped if C<flags & 1>.
 740
 741 =cut
 742 */
 743 void
 744 Perl_mro_package_moved(pTHX_ HV * const stash, HV * const oldstash,
 745                        const GV * const gv, U32 flags)
 746 {
 747     SV *namesv;
 748     HEK **namep;
 749     I32 name_count;
 750     HV *stashes;
 751     HE* iter;
 752
 753     PERL_ARGS_ASSERT_MRO_PACKAGE_MOVED;
 754     assert(stash || oldstash);
 755
 756     /* Determine the name(s) of the location that stash was assigned to
 757      * or from which oldstash was removed.
 758      *
 759      * We cannot reliably use the name in oldstash, because it may have
 760      * been deleted from the location in the symbol table that its name
 761      * suggests, as in this case:
 762      *
 763      *   $globref = \*foo::bar::;
 764      *   Symbol::delete_package("foo");
 765      *   *$globref = \%baz::;
 766      *   *$globref = *frelp::;
 767      *      # calls mro_package_moved(%frelp::, %baz::, *$globref, NULL, 0)
 768      *
 769      * So we get it from the gv. But, since the gv may no longer be in the
 770      * symbol table, we check that first. The only reliable way to tell is
 771      * to see whether its stash has an effective name and whether the gv
 772      * resides in that stash under its name. That effective name may be
 773      * different from what gv_fullname4 would use.
 774      * If flags & 1, the caller has asked us to skip the check.
 775      */
 776     if(!(flags & 1)) {
 777         SV **svp;
 778         if(
 779          !GvSTASH(gv) || !HvENAME(GvSTASH(gv)) ||
 780          !(svp = hv_fetchhek(GvSTASH(gv), GvNAME_HEK(gv), 0)) ||
 781          *svp != (SV *)gv
 782         ) return;
 783     }
 784     assert(SvOOK(GvSTASH(gv)));
 785     assert(GvNAMELEN(gv));
 786     assert(GvNAME(gv)[GvNAMELEN(gv) - 1] == ':');
 787     assert(GvNAMELEN(gv) == 1 || GvNAME(gv)[GvNAMELEN(gv) - 2] == ':');
 788     name_count = HvAUX(GvSTASH(gv))->xhv_name_count;
 789     if (!name_count) {
 790         name_count = 1;
 791         namep = &HvAUX(GvSTASH(gv))->xhv_name_u.xhvnameu_name;
 792     }
 793     else {
 794         namep = HvAUX(GvSTASH(gv))->xhv_name_u.xhvnameu_names;
 795         if (name_count < 0) ++namep, name_count = -name_count - 1;
 796     }
 797     if (name_count == 1) {
 798         if (HEK_LEN(*namep) == 4 && strnEQ(HEK_KEY(*namep), "main", 4)) {
 799             namesv = GvNAMELEN(gv) == 1
 800                 ? newSVpvs_flags(":", SVs_TEMP)
 801                 : newSVpvs_flags("",  SVs_TEMP);
 802         }
 803         else {
 804             namesv = sv_2mortal(newSVhek(*namep));
 805             if (GvNAMELEN(gv) == 1) sv_catpvs(namesv, ":");
 806             else                    sv_catpvs(namesv, "::");
 807         }
 808         if (GvNAMELEN(gv) != 1) {
 809             sv_catpvn_flags(
 810                 namesv, GvNAME(gv), GvNAMELEN(gv) - 2,
 811                                           /* skip trailing :: */
 812                 GvNAMEUTF8(gv) ? SV_CATUTF8 : SV_CATBYTES
 813             );
 814         }
 815     }
 816     else {
 817         SV *aname;
 818         namesv = sv_2mortal((SV *)newAV());
 819         while (name_count--) {
 820             if(HEK_LEN(*namep) == 4 && strnEQ(HEK_KEY(*namep), "main", 4)){
 821                 aname = GvNAMELEN(gv) == 1
 822                          ? newSVpvs(":")
 823                          : newSVpvs("");
 824                 namep++;
 825             }
 826             else {
 827                 aname = newSVhek(*namep++);
 828                 if (GvNAMELEN(gv) == 1) sv_catpvs(aname, ":");
 829                 else                    sv_catpvs(aname, "::");
 830             }
 831             if (GvNAMELEN(gv) != 1) {
 832                 sv_catpvn_flags(
 833                     aname, GvNAME(gv), GvNAMELEN(gv) - 2,
 834                                           /* skip trailing :: */
 835                     GvNAMEUTF8(gv) ? SV_CATUTF8 : SV_CATBYTES
 836                 );
 837             }
 838             av_push((AV *)namesv, aname);
 839         }
 840     }
 841
 842     /* Get a list of all the affected classes. */
 843     /* We cannot simply pass them all to mro_isa_changed_in to avoid
 844        the list, as that function assumes that only one package has
 845        changed. It does not work with:
 846
 847           @foo::ISA = qw( B B::B );
 848           *B:: = delete $::{"A::"};
 849
 850        as neither B nor B::B can be updated before the other, since they
 851        will reset caches on foo, which will see either B or B::B with the
 852        wrong name. The names must be set on *all* affected stashes before
 853        we do anything else. (And linearisations must be cleared, too.)
 854      */
 855     stashes = (HV *) sv_2mortal((SV *)newHV());
 856     mro_gather_and_rename(
 857      stashes, (HV *) sv_2mortal((SV *)newHV()),
 858      stash, oldstash, namesv
 859     );
 860
 861     /* Once the caches have been wiped on all the classes, call
 862        mro_isa_changed_in on each. */
 863     hv_iterinit(stashes);
 864     while((iter = hv_iternext(stashes))) {
 865         HV * const stash = *(HV **)HEK_KEY(HeKEY_hek(iter));
 866         if(HvENAME(stash)) {
 867             /* We have to restore the original meta->isa (that
 868                mro_gather_and_rename set aside for us) this way, in case
 869                one class in this list is a superclass of a another class
 870                that we have already encountered. In such a case, meta->isa
 871                will have been overwritten without old entries being deleted
 872                from PL_isarev. */
 873             struct mro_meta * const meta = HvMROMETA(stash);
 874             if(meta->isa != (HV *)HeVAL(iter)){
 875                 SvREFCNT_dec(meta->isa);
 876                 meta->isa
 877                  = HeVAL(iter) == &PL_sv_yes
 878                     ? NULL
 879                     : (HV *)HeVAL(iter);
 880                 HeVAL(iter) = NULL; /* We donated our reference count. */
 881             }
 882             mro_isa_changed_in(stash);
 883         }
 884     }
 885 }
 886
 887 STATIC void
 888 S_mro_gather_and_rename(pTHX_ HV * const stashes, HV * const seen_stashes,
 889                               HV *stash, HV *oldstash, SV *namesv)
 890 {
 891     XPVHV* xhv;
 892     HE *entry;
 893     I32 riter = -1;
 894     I32 items = 0;
 895     const bool stash_had_name = stash && HvENAME(stash);
 896     bool fetched_isarev = FALSE;
 897     HV *seen = NULL;
 898     HV *isarev = NULL;
 899     SV **svp = NULL;
 900
 901     PERL_ARGS_ASSERT_MRO_GATHER_AND_RENAME;
 902
 903     /* We use the seen_stashes hash to keep track of which packages have
 904        been encountered so far. This must be separate from the main list of
 905        stashes, as we need to distinguish between stashes being assigned
 906        and stashes being replaced/deleted. (A nested stash can be on both
 907        sides of an assignment. We cannot simply skip iterating through a
 908        stash on the right if we have seen it on the left, as it will not
 909        get its ename assigned to it.)
 910
 911        To avoid allocating extra SVs, instead of a bitfield we can make
 912        bizarre use of immortals:
 913
 914         &PL_sv_undef:  seen on the left  (oldstash)
 915         &PL_sv_no   :  seen on the right (stash)
 916         &PL_sv_yes  :  seen on both sides
 917
 918      */
 919
 920     if(oldstash) {
 921         /* Add to the big list. */
 922         struct mro_meta * meta;
 923         HE * const entry
 924          = (HE *)
 925              hv_common(
 926               seen_stashes, NULL, (const char *)&oldstash, sizeof(HV *), 0,
 927               HV_FETCH_LVALUE|HV_FETCH_EMPTY_HE, NULL, 0
 928              );
 929         if(HeVAL(entry) == &PL_sv_undef || HeVAL(entry) == &PL_sv_yes) {
 930             oldstash = NULL;
 931             goto check_stash;
 932         }
 933         HeVAL(entry)
 934          = HeVAL(entry) == &PL_sv_no ? &PL_sv_yes : &PL_sv_undef;
 935         meta = HvMROMETA(oldstash);
 936         (void)
 937           hv_store(
 938            stashes, (const char *)&oldstash, sizeof(HV *),
 939            meta->isa
 940             ? SvREFCNT_inc_simple_NN((SV *)meta->isa)
 941             : &PL_sv_yes,
 942            0
 943           );
 944         CLEAR_LINEAR(meta);
 945
 946         /* Update the effective name. */
 947         if(HvENAME_get(oldstash)) {
 948             const HEK * const enamehek = HvENAME_HEK(oldstash);
 949             if(SvTYPE(namesv) == SVt_PVAV) {
 950                 items = AvFILLp((AV *)namesv) + 1;
 951                 svp = AvARRAY((AV *)namesv);
 952             }
 953             else {
 954                 items = 1;
 955                 svp = &namesv;
 956             }
 957             while (items--) {
 958                 const U32 name_utf8 = SvUTF8(*svp);
 959                 STRLEN len;
 960                 const char *name = SvPVx_const(*svp, len);
 961                 if(PL_stashcache) {
 962                     DEBUG_o(Perl_deb(aTHX_ "mro_gather_and_rename clearing PL_stashcache for '%"SVf"'\n",
 963                                      *svp));
 964                    (void)hv_delete(PL_stashcache, name, name_utf8 ? -(I32)len : (I32)len, G_DISCARD);
 965                 }
 966                 ++svp;
 967                 hv_ename_delete(oldstash, name, len, name_utf8);
 968
 969                 if (!fetched_isarev) {
 970                     /* If the name deletion caused a name change, then we
 971                      * are not going to call mro_isa_changed_in with this
 972                      * name (and not at all if it has become anonymous) so
 973                      * we need to delete old isarev entries here, both
 974                      * those in the superclasses and this class's own list
 975                      * of subclasses. We simply delete the latter from
 976                      * PL_isarev, since we still need it. hv_delete morti-
 977                      * fies it for us, so sv_2mortal is not necessary. */
 978                     if(HvENAME_HEK(oldstash) != enamehek) {
 979                         if(meta->isa && HvARRAY(meta->isa))
 980                             mro_clean_isarev(meta->isa, name, len, 0, 0,
 981                                              name_utf8 ? HVhek_UTF8 : 0);
 982                         isarev = (HV *)hv_delete(PL_isarev, name,
 983                                                     name_utf8 ? -(I32)len : (I32)len, 0);
 984                         fetched_isarev=TRUE;
 985                     }
 986                 }
 987             }
 988         }
 989     }
 990    check_stash:
 991     if(stash) {
 992         if(SvTYPE(namesv) == SVt_PVAV) {
 993             items = AvFILLp((AV *)namesv) + 1;
 994             svp = AvARRAY((AV *)namesv);
 995         }
 996         else {
 997             items = 1;
 998             svp = &namesv;
 999         }
1000         while (items--) {
1001             const U32 name_utf8 = SvUTF8(*svp);
1002             STRLEN len;
1003             const char *name = SvPVx_const(*svp++, len);
1004             hv_ename_add(stash, name, len, name_utf8);
1005         }
1006
1007        /* Add it to the big list if it needs
1008         * mro_isa_changed_in called on it. That happens if it was
1009         * detached from the symbol table (so it had no HvENAME) before
1010         * being assigned to the spot named by the 'name' variable, because
1011         * its cached isa linearisation is now stale (the effective name
1012         * having changed), and subclasses will then use that cache when
1013         * mro_package_moved calls mro_isa_changed_in. (See
1014         * [perl #77358].)
1015         *
1016         * If it did have a name, then its previous name is still
1017         * used in isa caches, and there is no need for
1018         * mro_package_moved to call mro_isa_changed_in.
1019         */
1020
1021         entry
1022          = (HE *)
1023              hv_common(
1024               seen_stashes, NULL, (const char *)&stash, sizeof(HV *), 0,
1025               HV_FETCH_LVALUE|HV_FETCH_EMPTY_HE, NULL, 0
1026              );
1027         if(HeVAL(entry) == &PL_sv_yes || HeVAL(entry) == &PL_sv_no)
1028             stash = NULL;
1029         else {
1030             HeVAL(entry)
1031              = HeVAL(entry) == &PL_sv_undef ? &PL_sv_yes : &PL_sv_no;
1032             if(!stash_had_name)
1033             {
1034                 struct mro_meta * const meta = HvMROMETA(stash);
1035                 (void)
1036                   hv_store(
1037                    stashes, (const char *)&stash, sizeof(HV *),
1038                    meta->isa
1039                     ? SvREFCNT_inc_simple_NN((SV *)meta->isa)
1040                     : &PL_sv_yes,
1041                    0
1042                   );
1043                 CLEAR_LINEAR(meta);
1044             }
1045         }
1046     }
1047
1048     if(!stash && !oldstash)
1049         /* Both stashes have been encountered already. */
1050         return;
1051
1052     /* Add all the subclasses to the big list. */
1053     if(!fetched_isarev) {
1054         /* If oldstash is not null, then we can use its HvENAME to look up
1055            the isarev hash, since all its subclasses will be listed there.
1056            It will always have an HvENAME. It the HvENAME was removed
1057            above, then fetch_isarev will be true, and this code will not be
1058            reached.
1059
1060            If oldstash is null, then this is an empty spot with no stash in
1061            it, so subclasses could be listed in isarev hashes belonging to
1062            any of the names, so we have to check all of them.
1063          */
1064         assert(!oldstash || HvENAME(oldstash));
1065         if (oldstash) {
1066             /* Extra variable to avoid a compiler warning */
1067             const HEK * const hvename = HvENAME_HEK(oldstash);
1068             fetched_isarev = TRUE;
1069             svp = hv_fetchhek(PL_isarev, hvename, 0);
1070             if (svp) isarev = MUTABLE_HV(*svp);
1071         }
1072         else if(SvTYPE(namesv) == SVt_PVAV) {
1073             items = AvFILLp((AV *)namesv) + 1;
1074             svp = AvARRAY((AV *)namesv);
1075         }
1076         else {
1077             items = 1;
1078             svp = &namesv;
1079         }
1080     }
1081     if(
1082         isarev || !fetched_isarev
1083     ) {
1084       while (fetched_isarev || items--) {
1085         HE *iter;
1086
1087         if (!fetched_isarev) {
1088             HE * const he = hv_fetch_ent(PL_isarev, *svp++, 0, 0);
1089             if (!he || !(isarev = MUTABLE_HV(HeVAL(he)))) continue;
1090         }
1091
1092         hv_iterinit(isarev);
1093         while((iter = hv_iternext(isarev))) {
1094             HV* revstash = gv_stashsv(hv_iterkeysv(iter), 0);
1095             struct mro_meta * meta;
1096
1097             if(!revstash) continue;
1098             meta = HvMROMETA(revstash);
1099             (void)
1100               hv_store(
1101                stashes, (const char *)&revstash, sizeof(HV *),
1102                meta->isa
1103                 ? SvREFCNT_inc_simple_NN((SV *)meta->isa)
1104                 : &PL_sv_yes,
1105                0
1106               );
1107             CLEAR_LINEAR(meta);
1108         }
1109
1110         if (fetched_isarev) break;
1111       }
1112     }
1113
1114     /* This is partly based on code in hv_iternext_flags. We are not call-
1115        ing that here, as we want to avoid resetting the hash iterator. */
1116
1117     /* Skip the entire loop if the hash is empty.   */
1118     if(oldstash && HvUSEDKEYS(oldstash)) {
1119         xhv = (XPVHV*)SvANY(oldstash);
1120         seen = (HV *) sv_2mortal((SV *)newHV());
1121
1122         /* Iterate through entries in the oldstash, adding them to the
1123            list, meanwhile doing the equivalent of $seen{$key} = 1.
1124          */
1125
1126         while (++riter <= (I32)xhv->xhv_max) {
1127             entry = (HvARRAY(oldstash))[riter];
1128
1129             /* Iterate through the entries in this list */
1130             for(; entry; entry = HeNEXT(entry)) {
1131                 const char* key;
1132                 I32 len;
1133
1134                 /* If this entry is not a glob, ignore it.
1135                    Try the next.  */
1136                 if (!isGV(HeVAL(entry))) continue;
1137
1138                 key = hv_iterkey(entry, &len);
1139                 if ((len > 1 && key[len-2] == ':' && key[len-1] == ':')
1140                  || (len == 1 && key[0] == ':')) {
1141                     HV * const oldsubstash = GvHV(HeVAL(entry));
1142                     SV ** const stashentry
1143                      = stash ? hv_fetch(stash, key, HeUTF8(entry) ? -(I32)len : (I32)len, 0) : NULL;
1144                     HV *substash = NULL;
1145
1146                     /* Avoid main::main::main::... */
1147                     if(oldsubstash == oldstash) continue;
1148
1149                     if(
1150                         (
1151                             stashentry && *stashentry && isGV(*stashentry)
1152                          && (substash = GvHV(*stashentry))
1153                         )
1154                      || (oldsubstash && HvENAME_get(oldsubstash))
1155                     )
1156                     {
1157                         /* Add :: and the key (minus the trailing ::)
1158                            to each name. */
1159                         SV *subname;
1160                         if(SvTYPE(namesv) == SVt_PVAV) {
1161                             SV *aname;
1162                             items = AvFILLp((AV *)namesv) + 1;
1163                             svp = AvARRAY((AV *)namesv);
1164                             subname = sv_2mortal((SV *)newAV());
1165                             while (items--) {
1166                                 aname = newSVsv(*svp++);
1167                                 if (len == 1)
1168                                     sv_catpvs(aname, ":");
1169                                 else {
1170                                     sv_catpvs(aname, "::");
1171                                     sv_catpvn_flags(
1172                                         aname, key, len-2,
1173                                         HeUTF8(entry)
1174                                            ? SV_CATUTF8 : SV_CATBYTES
1175                                     );
1176                                 }
1177                                 av_push((AV *)subname, aname);
1178                             }
1179                         }
1180                         else {
1181                             subname = sv_2mortal(newSVsv(namesv));
1182                             if (len == 1) sv_catpvs(subname, ":");
1183                             else {
1184                                 sv_catpvs(subname, "::");
1185                                 sv_catpvn_flags(
1186                                    subname, key, len-2,
1187                                    HeUTF8(entry) ? SV_CATUTF8 : SV_CATBYTES
1188                                 );
1189                             }
1190                         }
1191                         mro_gather_and_rename(
1192                              stashes, seen_stashes,
1193                              substash, oldsubstash, subname
1194                         );
1195                     }
1196
1197                     (void)hv_store(seen, key, HeUTF8(entry) ? -(I32)len : (I32)len, &PL_sv_yes, 0);
1198                 }
1199             }
1200         }
1201     }
1202
1203     /* Skip the entire loop if the hash is empty.   */
1204     if (stash && HvUSEDKEYS(stash)) {
1205         xhv = (XPVHV*)SvANY(stash);
1206         riter = -1;
1207
1208         /* Iterate through the new stash, skipping $seen{$key} items,
1209            calling mro_gather_and_rename(stashes,seen,entry,NULL, ...). */
1210         while (++riter <= (I32)xhv->xhv_max) {
1211             entry = (HvARRAY(stash))[riter];
1212
1213             /* Iterate through the entries in this list */
1214             for(; entry; entry = HeNEXT(entry)) {
1215                 const char* key;
1216                 I32 len;
1217
1218                 /* If this entry is not a glob, ignore it.
1219                    Try the next.  */
1220                 if (!isGV(HeVAL(entry))) continue;
1221
1222                 key = hv_iterkey(entry, &len);
1223                 if ((len > 1 && key[len-2] == ':' && key[len-1] == ':')
1224                  || (len == 1 && key[0] == ':')) {
1225                     HV *substash;
1226
1227                     /* If this entry was seen when we iterated through the
1228                        oldstash, skip it. */
1229                     if(seen && hv_exists(seen, key, HeUTF8(entry) ? -(I32)len : (I32)len)) continue;
1230
1231                     /* We get here only if this stash has no corresponding
1232                        entry in the stash being replaced. */
1233
1234                     substash = GvHV(HeVAL(entry));
1235                     if(substash) {
1236                         SV *subname;
1237
1238                         /* Avoid checking main::main::main::... */
1239                         if(substash == stash) continue;
1240
1241                         /* Add :: and the key (minus the trailing ::)
1242                            to each name. */
1243                         if(SvTYPE(namesv) == SVt_PVAV) {
1244                             SV *aname;
1245                             items = AvFILLp((AV *)namesv) + 1;
1246                             svp = AvARRAY((AV *)namesv);
1247                             subname = sv_2mortal((SV *)newAV());
1248                             while (items--) {
1249                                 aname = newSVsv(*svp++);
1250                                 if (len == 1)
1251                                     sv_catpvs(aname, ":");
1252                                 else {
1253                                     sv_catpvs(aname, "::");
1254                                     sv_catpvn_flags(
1255                                         aname, key, len-2,
1256                                         HeUTF8(entry)
1257                                            ? SV_CATUTF8 : SV_CATBYTES
1258                                     );
1259                                 }
1260                                 av_push((AV *)subname, aname);
1261                             }
1262                         }
1263                         else {
1264                             subname = sv_2mortal(newSVsv(namesv));
1265                             if (len == 1) sv_catpvs(subname, ":");
1266                             else {
1267                                 sv_catpvs(subname, "::");
1268                                 sv_catpvn_flags(
1269                                    subname, key, len-2,
1270                                    HeUTF8(entry) ? SV_CATUTF8 : SV_CATBYTES
1271                                 );
1272                             }
1273                         }
1274                         mro_gather_and_rename(
1275                           stashes, seen_stashes,
1276                           substash, NULL, subname
1277                         );
1278                     }
1279                 }
1280             }
1281         }
1282     }
1283 }
1284
1285 /*
1286 =for apidoc mro_method_changed_in
1287
1288 Invalidates method caching on any child classes
1289 of the given stash, so that they might notice
1290 the changes in this one.
1291
1292 Ideally, all instances of C<PL_sub_generation++> in
1293 perl source outside of F<mro.c> should be
1294 replaced by calls to this.
1295
1296 Perl automatically handles most of the common
1297 ways a method might be redefined.  However, there
1298 are a few ways you could change a method in a stash
1299 without the cache code noticing, in which case you
1300 need to call this method afterwards:
1301
1302 1) Directly manipulating the stash HV entries from
1303 XS code.
1304
1305 2) Assigning a reference to a readonly scalar
1306 constant into a stash entry in order to create
1307 a constant subroutine (like constant.pm
1308 does).
1309
1310 This same method is available from pure perl
1311 via, C<mro::method_changed_in(classname)>.
1312
1313 =cut
1314 */
1315 void
1316 Perl_mro_method_changed_in(pTHX_ HV *stash)
1317 {
1318     const char * const stashname = HvENAME_get(stash);
1319     const STRLEN stashname_len = HvENAMELEN_get(stash);
1320
1321     SV ** const svp = hv_fetchhek(PL_isarev, HvENAME_HEK(stash), 0);
1322     HV * const isarev = svp ? MUTABLE_HV(*svp) : NULL;
1323
1324     PERL_ARGS_ASSERT_MRO_METHOD_CHANGED_IN;
1325
1326     if(!stashname)
1327         Perl_croak(aTHX_ "Can't call mro_method_changed_in() on anonymous symbol table");
1328
1329     /* Inc the package generation, since a local method changed */
1330     HvMROMETA(stash)->pkg_gen++;
1331
1332     /* DESTROY can be cached in SvSTASH. */
1333     if (!SvOBJECT(stash)) SvSTASH(stash) = NULL;
1334
1335     /* If stash is UNIVERSAL, or one of UNIVERSAL's parents,
1336        invalidate all method caches globally */
1337     if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
1338         || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
1339         PL_sub_generation++;
1340         return;
1341     }
1342
1343     /* else, invalidate the method caches of all child classes,
1344        but not itself */
1345     if(isarev) {
1346         HE* iter;
1347
1348         hv_iterinit(isarev);
1349         while((iter = hv_iternext(isarev))) {
1350             HV* const revstash = gv_stashsv(hv_iterkeysv(iter), 0);
1351             struct mro_meta* mrometa;
1352
1353             if(!revstash) continue;
1354             mrometa = HvMROMETA(revstash);
1355             mrometa->cache_gen++;
1356             if(mrometa->mro_nextmethod)
1357                 hv_clear(mrometa->mro_nextmethod);
1358             if (!SvOBJECT(revstash)) SvSTASH(revstash) = NULL;
1359         }
1360     }
1361
1362     /* The method change may be due to *{$package . "::()"} = \&nil; in
1363        overload.pm. */
1364     HvAMAGIC_on(stash);
1365     /* pessimise derefs for now. Will get recalculated by Gv_AMupdate() */
1366     HvAUX(stash)->xhv_aux_flags &= ~HvAUXf_NO_DEREF;
1367 }
1368
1369 void
1370 Perl_mro_set_mro(pTHX_ struct mro_meta *const meta, SV *const name)
1371 {
1372     const struct mro_alg *const which = Perl_mro_get_from_name(aTHX_ name);
1373
1374     PERL_ARGS_ASSERT_MRO_SET_MRO;
1375
1376     if (!which)
1377         Perl_croak(aTHX_ "Invalid mro name: '%"SVf"'", name);
1378
1379     if(meta->mro_which != which) {
1380         if (meta->mro_linear_current && !meta->mro_linear_all) {
1381             /* If we were storing something directly, put it in the hash before
1382                we lose it. */
1383             Perl_mro_set_private_data(aTHX_ meta, meta->mro_which,
1384                                       MUTABLE_SV(meta->mro_linear_current));
1385         }
1386         meta->mro_which = which;
1387         /* Scrub our cached pointer to the private data.  */
1388         meta->mro_linear_current = NULL;
1389         /* Only affects local method cache, not
1390            even child classes */
1391         meta->cache_gen++;
1392         if(meta->mro_nextmethod)
1393             hv_clear(meta->mro_nextmethod);
1394     }
1395 }
1396
1397 #include "XSUB.h"
1398
1399 XS(XS_mro_method_changed_in);
1400
1401 void
1402 Perl_boot_core_mro(pTHX)
1403 {
1404     dVAR;
1405     static const char file[] = __FILE__;
1406
1407     Perl_mro_register(aTHX_ &dfs_alg);
1408
1409     newXSproto("mro::method_changed_in", XS_mro_method_changed_in, file, "$");
1410 }
1411
1412 XS(XS_mro_method_changed_in)
1413 {
1414     dVAR;
1415     dXSARGS;
1416     SV* classname;
1417     HV* class_stash;
1418
1419     if(items != 1)
1420         croak_xs_usage(cv, "classname");
1421
1422     classname = ST(0);
1423
1424     class_stash = gv_stashsv(classname, 0);
1425     if(!class_stash) Perl_croak(aTHX_ "No such class: '%"SVf"'!", SVfARG(classname));
1426
1427     mro_method_changed_in(class_stash);
1428
1429     XSRETURN_EMPTY;
1430 }
1431
1432 /*
1433  * Local variables:
1434  * c-indentation-style: bsd
1435  * c-basic-offset: 4
1436  * indent-tabs-mode: nil
1437  * End:
1438  *
1439  * ex: set ts=8 sts=4 sw=4 et:
1440  */