3 * Copyright (c) 2007 Brandon L Black
4 * Copyright (c) 2007, 2008 Larry Wall and others
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.
12 * 'Which order shall we go in?' said Frodo. 'Eldest first, or quickest first?
13 * You'll be last either way, Master Peregrin.'
15 * [p.101 of _The Lord of the Rings_, I/iii: "A Conspiracy Unmasked"]
21 These functions are related to the method resolution order of perl classes
30 static const struct mro_alg dfs_alg =
31 {S_mro_get_linear_isa_dfs, "dfs", 3, 0, 0};
34 Perl_mro_get_private_data(pTHX_ struct mro_meta *const smeta,
35 const struct mro_alg *const which)
38 PERL_ARGS_ASSERT_MRO_GET_PRIVATE_DATA;
40 data = (SV **)Perl_hv_common(aTHX_ smeta->mro_linear_all, NULL,
41 which->name, which->length, which->kflags,
42 HV_FETCH_JUST_SV, NULL, which->hash);
46 /* If we've been asked to look up the private data for the current MRO, then
48 if (smeta->mro_which == which)
49 smeta->mro_linear_current = *data;
55 Perl_mro_set_private_data(pTHX_ struct mro_meta *const smeta,
56 const struct mro_alg *const which, SV *const data)
58 PERL_ARGS_ASSERT_MRO_SET_PRIVATE_DATA;
60 if (!smeta->mro_linear_all) {
61 if (smeta->mro_which == which) {
62 /* If all we need to store is the current MRO's data, then don't use
63 memory on a hash with 1 element - store it direct, and signal
64 this by leaving the would-be-hash NULL. */
65 smeta->mro_linear_current = data;
68 HV *const hv = newHV();
69 /* Start with 2 buckets. It's unlikely we'll need more. */
71 smeta->mro_linear_all = hv;
73 if (smeta->mro_linear_current) {
74 /* If we were storing something directly, put it in the hash
76 Perl_mro_set_private_data(aTHX_ smeta, smeta->mro_which,
77 smeta->mro_linear_current);
82 /* We get here if we're storing more than one linearisation for this stash,
83 or the linearisation we are storing is not that if its current MRO. */
85 if (smeta->mro_which == which) {
86 /* If we've been asked to store the private data for the current MRO,
88 smeta->mro_linear_current = data;
91 if (!Perl_hv_common(aTHX_ smeta->mro_linear_all, NULL,
92 which->name, which->length, which->kflags,
93 HV_FETCH_ISSTORE, data, which->hash)) {
94 Perl_croak(aTHX_ "panic: hv_store() failed in set_mro_private_data() "
95 "for '%.*s' %d", (int) which->length, which->name,
102 const struct mro_alg *
103 Perl_mro_get_from_name(pTHX_ SV *name) {
106 PERL_ARGS_ASSERT_MRO_GET_FROM_NAME;
108 data = (SV **)Perl_hv_common(aTHX_ PL_registered_mros, name, NULL, 0, 0,
109 HV_FETCH_JUST_SV, NULL, 0);
112 assert(SvTYPE(*data) == SVt_IV);
113 assert(SvIOK(*data));
114 return INT2PTR(const struct mro_alg *, SvUVX(*data));
118 Perl_mro_register(pTHX_ const struct mro_alg *mro) {
119 SV *wrapper = newSVuv(PTR2UV(mro));
121 PERL_ARGS_ASSERT_MRO_REGISTER;
124 if (!Perl_hv_common(aTHX_ PL_registered_mros, NULL,
125 mro->name, mro->length, mro->kflags,
126 HV_FETCH_ISSTORE, wrapper, mro->hash)) {
127 SvREFCNT_dec(wrapper);
128 Perl_croak(aTHX_ "panic: hv_store() failed in mro_register() "
129 "for '%.*s' %d", (int) mro->length, mro->name, mro->kflags);
134 Perl_mro_meta_init(pTHX_ HV* stash)
136 struct mro_meta* newmeta;
138 PERL_ARGS_ASSERT_MRO_META_INIT;
139 assert(HvAUX(stash));
140 assert(!(HvAUX(stash)->xhv_mro_meta));
141 Newxz(newmeta, 1, struct mro_meta);
142 HvAUX(stash)->xhv_mro_meta = newmeta;
143 newmeta->cache_gen = 1;
144 newmeta->pkg_gen = 1;
145 newmeta->mro_which = &dfs_alg;
150 #if defined(USE_ITHREADS)
152 /* for sv_dup on new threads */
154 Perl_mro_meta_dup(pTHX_ struct mro_meta* smeta, CLONE_PARAMS* param)
156 struct mro_meta* newmeta;
158 PERL_ARGS_ASSERT_MRO_META_DUP;
160 Newx(newmeta, 1, struct mro_meta);
161 Copy(smeta, newmeta, 1, struct mro_meta);
163 if (newmeta->mro_linear_all) {
164 newmeta->mro_linear_all
165 = MUTABLE_HV(SvREFCNT_inc(sv_dup((const SV *)newmeta->mro_linear_all, param)));
166 /* This is just acting as a shortcut pointer, and will be automatically
167 updated on the first get. */
168 newmeta->mro_linear_current = NULL;
169 } else if (newmeta->mro_linear_current) {
170 /* Only the current MRO is stored, so this owns the data. */
171 newmeta->mro_linear_current
172 = SvREFCNT_inc(sv_dup((const SV *)newmeta->mro_linear_current,
176 if (newmeta->mro_nextmethod)
177 newmeta->mro_nextmethod
178 = MUTABLE_HV(SvREFCNT_inc(sv_dup((const SV *)newmeta->mro_nextmethod, param)));
181 = MUTABLE_HV(SvREFCNT_inc(sv_dup((const SV *)newmeta->isa, param)));
186 #endif /* USE_ITHREADS */
189 =for apidoc mro_get_linear_isa_dfs
191 Returns the Depth-First Search linearization of @ISA
192 the given stash. The return value is a read-only AV*.
193 C<level> should be 0 (it is used internally in this
194 function's recursion).
196 You are responsible for C<SvREFCNT_inc()> on the
197 return value if you plan to store it anywhere
198 semi-permanently (otherwise it might be deleted
199 out from under you the next time the cache is
205 S_mro_get_linear_isa_dfs(pTHX_ HV *stash, U32 level)
212 struct mro_meta* meta;
216 PERL_ARGS_ASSERT_MRO_GET_LINEAR_ISA_DFS;
217 assert(HvAUX(stash));
219 stashhek = HvNAME_HEK(stash);
221 Perl_croak(aTHX_ "Can't linearize anonymous symbol table");
224 Perl_croak(aTHX_ "Recursive inheritance detected in package '%s'",
227 meta = HvMROMETA(stash);
229 /* return cache if valid */
230 if((retval = MUTABLE_AV(MRO_GET_PRIVATE_DATA(meta, &dfs_alg)))) {
234 /* not in cache, make a new one */
236 retval = MUTABLE_AV(sv_2mortal(MUTABLE_SV(newAV())));
237 /* We use this later in this function, but don't need a reference to it
238 beyond the end of this function, so reference count is fine. */
239 our_name = newSVhek(stashhek);
240 av_push(retval, our_name); /* add ourselves at the top */
243 gvp = (GV**)hv_fetchs(stash, "ISA", FALSE);
244 av = (gvp && (gv = *gvp) && isGV_with_GP(gv)) ? GvAV(gv) : NULL;
246 /* "stored" is used to keep track of all of the classnames we have added to
247 the MRO so far, so we can do a quick exists check and avoid adding
248 duplicate classnames to the MRO as we go.
249 It's then retained to be re-used as a fast lookup for ->isa(), by adding
250 our own name and "UNIVERSAL" to it. */
252 stored = MUTABLE_HV(sv_2mortal(MUTABLE_SV(newHV())));
254 if(av && AvFILLp(av) >= 0) {
256 SV **svp = AvARRAY(av);
257 I32 items = AvFILLp(av) + 1;
261 SV* const sv = *svp++;
262 HV* const basestash = gv_stashsv(sv, 0);
267 /* if no stash exists for this @ISA member,
268 simply add it to the MRO and move on */
273 /* otherwise, recurse into ourselves for the MRO
274 of this @ISA member, and append their MRO to ours.
275 The recursive call could throw an exception, which
276 has memory management implications here, hence the use of
278 const AV *const subrv
279 = mro_get_linear_isa_dfs(basestash, level + 1);
281 subrv_p = AvARRAY(subrv);
282 subrv_items = AvFILLp(subrv) + 1;
284 while(subrv_items--) {
285 SV *const subsv = *subrv_p++;
286 /* LVALUE fetch will create a new undefined SV if necessary
288 HE *const he = hv_fetch_ent(stored, subsv, 1, 0);
290 if(HeVAL(he) != &PL_sv_undef) {
291 /* It was newly created. Steal it for our new SV, and
292 replace it in the hash with the "real" thing. */
293 SV *const val = HeVAL(he);
294 HEK *const key = HeKEY_hek(he);
296 HeVAL(he) = &PL_sv_undef;
297 /* Save copying by making a shared hash key scalar. We
298 inline this here rather than calling Perl_newSVpvn_share
299 because we already have the scalar, and we already have
301 assert(SvTYPE(val) == SVt_NULL);
302 sv_upgrade(val, SVt_PV);
303 SvPV_set(val, HEK_KEY(share_hek_hek(key)));
304 SvCUR_set(val, HEK_LEN(key));
311 av_push(retval, val);
317 (void) hv_store_ent(stored, our_name, &PL_sv_undef, 0);
318 (void) hv_store(stored, "UNIVERSAL", 9, &PL_sv_undef, 0);
320 SvREFCNT_inc_simple_void_NN(stored);
322 SvREADONLY_on(stored);
326 /* now that we're past the exception dangers, grab our own reference to
327 the AV we're about to use for the result. The reference owned by the
328 mortals' stack will be released soon, so everything will balance. */
329 SvREFCNT_inc_simple_void_NN(retval);
332 /* we don't want anyone modifying the cache entry but us,
333 and we do so by replacing it completely */
334 SvREADONLY_on(retval);
336 return MUTABLE_AV(Perl_mro_set_private_data(aTHX_ meta, &dfs_alg,
337 MUTABLE_SV(retval)));
341 =for apidoc mro_get_linear_isa
343 Returns either C<mro_get_linear_isa_c3> or
344 C<mro_get_linear_isa_dfs> for the given stash,
345 dependant upon which MRO is in effect
346 for that stash. The return value is a
349 You are responsible for C<SvREFCNT_inc()> on the
350 return value if you plan to store it anywhere
351 semi-permanently (otherwise it might be deleted
352 out from under you the next time the cache is
358 Perl_mro_get_linear_isa(pTHX_ HV *stash)
360 struct mro_meta* meta;
362 PERL_ARGS_ASSERT_MRO_GET_LINEAR_ISA;
364 Perl_croak(aTHX_ "Can't linearize anonymous symbol table");
366 meta = HvMROMETA(stash);
367 if (!meta->mro_which)
368 Perl_croak(aTHX_ "panic: invalid MRO!");
369 return meta->mro_which->resolve(aTHX_ stash, 0);
373 =for apidoc mro_isa_changed_in
375 Takes the necessary steps (cache invalidations, mostly)
376 when the @ISA of the given package has changed. Invoked
377 by the C<setisa> magic, should not need to invoke directly.
382 Perl_mro_isa_changed_in(pTHX_ HV* stash)
391 struct mro_meta * meta;
393 const char * const stashname = HvNAME_get(stash);
394 const STRLEN stashname_len = HvNAMELEN_get(stash);
396 PERL_ARGS_ASSERT_MRO_ISA_CHANGED_IN;
399 Perl_croak(aTHX_ "Can't call mro_isa_changed_in() on anonymous symbol table");
401 /* wipe out the cached linearizations for this stash */
402 meta = HvMROMETA(stash);
403 if (meta->mro_linear_all) {
404 SvREFCNT_dec(MUTABLE_SV(meta->mro_linear_all));
405 meta->mro_linear_all = NULL;
406 /* This is just acting as a shortcut pointer. */
407 meta->mro_linear_current = NULL;
408 } else if (meta->mro_linear_current) {
409 /* Only the current MRO is stored, so this owns the data. */
410 SvREFCNT_dec(meta->mro_linear_current);
411 meta->mro_linear_current = NULL;
414 SvREFCNT_dec(meta->isa);
418 /* Inc the package generation, since our @ISA changed */
421 /* Wipe the global method cache if this package
422 is UNIVERSAL or one of its parents */
424 svp = hv_fetch(PL_isarev, stashname, stashname_len, 0);
425 isarev = svp ? MUTABLE_HV(*svp) : NULL;
427 if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
428 || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
432 else { /* Wipe the local method cache otherwise */
434 is_universal = FALSE;
437 /* wipe next::method cache too */
438 if(meta->mro_nextmethod) hv_clear(meta->mro_nextmethod);
440 /* Iterate the isarev (classes that are our children),
441 wiping out their linearization, method and isa caches */
444 while((iter = hv_iternext(isarev))) {
446 const char* const revkey = hv_iterkey(iter, &len);
447 HV* revstash = gv_stashpvn(revkey, len, 0);
448 struct mro_meta* revmeta;
450 if(!revstash) continue;
451 revmeta = HvMROMETA(revstash);
452 if (revmeta->mro_linear_all) {
453 SvREFCNT_dec(MUTABLE_SV(revmeta->mro_linear_all));
454 revmeta->mro_linear_all = NULL;
455 /* This is just acting as a shortcut pointer. */
456 revmeta->mro_linear_current = NULL;
457 } else if (revmeta->mro_linear_current) {
458 /* Only the current MRO is stored, so this owns the data. */
459 SvREFCNT_dec(revmeta->mro_linear_current);
460 revmeta->mro_linear_current = NULL;
463 revmeta->cache_gen++;
464 if(revmeta->mro_nextmethod)
465 hv_clear(revmeta->mro_nextmethod);
467 SvREFCNT_dec(revmeta->isa);
473 /* Now iterate our MRO (parents), and do a few things:
474 1) instantiate with the "fake" flag if they don't exist
475 2) flag them as universal if we are universal
476 3) Add everything from our isarev to their isarev
479 /* We're starting at the 2nd element, skipping ourselves here */
480 linear_mro = mro_get_linear_isa(stash);
481 svp = AvARRAY(linear_mro) + 1;
482 items = AvFILLp(linear_mro);
485 SV* const sv = *svp++;
488 HE *he = hv_fetch_ent(PL_isarev, sv, TRUE, 0);
490 /* That fetch should not fail. But if it had to create a new SV for
491 us, then will need to upgrade it to an HV (which sv_upgrade() can
494 mroisarev = MUTABLE_HV(HeVAL(he));
496 SvUPGRADE(MUTABLE_SV(mroisarev), SVt_PVHV);
498 /* This hash only ever contains PL_sv_yes. Storing it over itself is
499 almost as cheap as calling hv_exists, so on aggregate we expect to
500 save time by not making two calls to the common HV code for the
501 case where it doesn't exist. */
503 (void)hv_store(mroisarev, stashname, stashname_len, &PL_sv_yes, 0);
507 while((iter = hv_iternext(isarev))) {
509 char* const revkey = hv_iterkey(iter, &revkeylen);
510 (void)hv_store(mroisarev, revkey, revkeylen, &PL_sv_yes, 0);
517 =for apidoc mro_method_changed_in
519 Invalidates method caching on any child classes
520 of the given stash, so that they might notice
521 the changes in this one.
523 Ideally, all instances of C<PL_sub_generation++> in
524 perl source outside of C<mro.c> should be
525 replaced by calls to this.
527 Perl automatically handles most of the common
528 ways a method might be redefined. However, there
529 are a few ways you could change a method in a stash
530 without the cache code noticing, in which case you
531 need to call this method afterwards:
533 1) Directly manipulating the stash HV entries from
536 2) Assigning a reference to a readonly scalar
537 constant into a stash entry in order to create
538 a constant subroutine (like constant.pm
541 This same method is available from pure perl
542 via, C<mro::method_changed_in(classname)>.
547 Perl_mro_method_changed_in(pTHX_ HV *stash)
549 const char * const stashname = HvNAME_get(stash);
550 const STRLEN stashname_len = HvNAMELEN_get(stash);
552 SV ** const svp = hv_fetch(PL_isarev, stashname, stashname_len, 0);
553 HV * const isarev = svp ? MUTABLE_HV(*svp) : NULL;
555 PERL_ARGS_ASSERT_MRO_METHOD_CHANGED_IN;
558 Perl_croak(aTHX_ "Can't call mro_method_changed_in() on anonymous symbol table");
560 /* Inc the package generation, since a local method changed */
561 HvMROMETA(stash)->pkg_gen++;
563 /* If stash is UNIVERSAL, or one of UNIVERSAL's parents,
564 invalidate all method caches globally */
565 if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
566 || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
571 /* else, invalidate the method caches of all child classes,
577 while((iter = hv_iternext(isarev))) {
579 const char* const revkey = hv_iterkey(iter, &len);
580 HV* const revstash = gv_stashpvn(revkey, len, 0);
581 struct mro_meta* mrometa;
583 if(!revstash) continue;
584 mrometa = HvMROMETA(revstash);
585 mrometa->cache_gen++;
586 if(mrometa->mro_nextmethod)
587 hv_clear(mrometa->mro_nextmethod);
593 Perl_mro_set_mro(pTHX_ struct mro_meta *const meta, SV *const name)
595 const struct mro_alg *const which = Perl_mro_get_from_name(aTHX_ name);
597 PERL_ARGS_ASSERT_MRO_SET_MRO;
600 Perl_croak(aTHX_ "Invalid mro name: '%"SVf"'", name);
602 if(meta->mro_which != which) {
603 if (meta->mro_linear_current && !meta->mro_linear_all) {
604 /* If we were storing something directly, put it in the hash before
606 Perl_mro_set_private_data(aTHX_ meta, meta->mro_which,
607 MUTABLE_SV(meta->mro_linear_current));
609 meta->mro_which = which;
610 /* Scrub our cached pointer to the private data. */
611 meta->mro_linear_current = NULL;
612 /* Only affects local method cache, not
613 even child classes */
615 if(meta->mro_nextmethod)
616 hv_clear(meta->mro_nextmethod);
622 XS(XS_mro_method_changed_in);
625 Perl_boot_core_mro(pTHX)
628 static const char file[] = __FILE__;
630 Perl_mro_register(aTHX_ &dfs_alg);
632 newXSproto("mro::method_changed_in", XS_mro_method_changed_in, file, "$");
635 XS(XS_mro_method_changed_in)
643 croak_xs_usage(cv, "classname");
647 class_stash = gv_stashsv(classname, 0);
648 if(!class_stash) Perl_croak(aTHX_ "No such class: '%"SVf"'!", SVfARG(classname));
650 mro_method_changed_in(class_stash);
657 * c-indentation-style: bsd
659 * indent-tabs-mode: t
662 * ex: set ts=8 sts=4 sw=4 noet: