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 if(av && AvFILLp(av) >= 0) {
254 SV **svp = AvARRAY(av);
255 I32 items = AvFILLp(av) + 1;
259 SV* const sv = *svp++;
260 HV* const basestash = gv_stashsv(sv, 0);
265 /* if no stash exists for this @ISA member,
266 simply add it to the MRO and move on */
271 /* otherwise, recurse into ourselves for the MRO
272 of this @ISA member, and append their MRO to ours.
273 The recursive call could throw an exception, which
274 has memory management implications here, hence the use of
276 const AV *const subrv
277 = mro_get_linear_isa_dfs(basestash, level + 1);
279 subrv_p = AvARRAY(subrv);
280 subrv_items = AvFILLp(subrv) + 1;
283 while(subrv_items--) {
284 SV *const subsv = *subrv_p++;
285 /* LVALUE fetch will create a new undefined SV if necessary
287 HE *const he = hv_fetch_ent(stored, subsv, 1, 0);
289 if(HeVAL(he) != &PL_sv_undef) {
290 /* It was newly created. Steal it for our new SV, and
291 replace it in the hash with the "real" thing. */
292 SV *const val = HeVAL(he);
293 HEK *const key = HeKEY_hek(he);
295 HeVAL(he) = &PL_sv_undef;
296 /* Save copying by making a shared hash key scalar. We
297 inline this here rather than calling
298 Perl_newSVpvn_share because we already have the
299 scalar, and we already have the hash key. */
300 assert(SvTYPE(val) == SVt_NULL);
301 sv_upgrade(val, SVt_PV);
302 SvPV_set(val, HEK_KEY(share_hek_hek(key)));
303 SvCUR_set(val, HEK_LEN(key));
310 av_push(retval, val);
314 /* We are the first (or only) parent. We can short cut the
315 complexity above, because our @ISA is simply us prepended
316 to our parent's @ISA, and our ->isa cache is simply our
317 parent's, with our name added. */
318 /* newSVsv() is slow. This code is only faster if we can avoid
319 it by ensuring that SVs in the arrays are shared hash key
320 scalar SVs, because we can "copy" them very efficiently.
321 Although to be fair, we can't *ensure* this, as a reference
322 to the internal array is returned by mro::get_linear_isa(),
323 so we'll have to be defensive just in case someone faffed
327 stored = MUTABLE_HV(sv_2mortal((SV*)newHVhv(HvMROMETA(basestash)->isa)));
328 av_extend(retval, subrv_items);
329 AvFILLp(retval) = subrv_items;
330 svp = AvARRAY(retval);
331 while(subrv_items--) {
332 SV *const val = *subrv_p++;
333 *++svp = SvIsCOW_shared_hash(val)
334 ? newSVhek(SvSHARED_HEK_FROM_PV(SvPVX(val)))
338 /* They have no stash. So create ourselves an ->isa cache
339 as if we'd copied it from what theirs should be. */
340 stored = MUTABLE_HV(sv_2mortal(MUTABLE_SV(newHV())));
341 (void) hv_store(stored, "UNIVERSAL", 9, &PL_sv_undef, 0);
343 newSVhek(HeKEY_hek(hv_store_ent(stored, sv,
349 /* We have no parents. */
350 stored = MUTABLE_HV(sv_2mortal(MUTABLE_SV(newHV())));
351 (void) hv_store(stored, "UNIVERSAL", 9, &PL_sv_undef, 0);
354 (void) hv_store_ent(stored, our_name, &PL_sv_undef, 0);
356 SvREFCNT_inc_simple_void_NN(stored);
358 SvREADONLY_on(stored);
362 /* now that we're past the exception dangers, grab our own reference to
363 the AV we're about to use for the result. The reference owned by the
364 mortals' stack will be released soon, so everything will balance. */
365 SvREFCNT_inc_simple_void_NN(retval);
368 /* we don't want anyone modifying the cache entry but us,
369 and we do so by replacing it completely */
370 SvREADONLY_on(retval);
372 return MUTABLE_AV(Perl_mro_set_private_data(aTHX_ meta, &dfs_alg,
373 MUTABLE_SV(retval)));
377 =for apidoc mro_get_linear_isa
379 Returns either C<mro_get_linear_isa_c3> or
380 C<mro_get_linear_isa_dfs> for the given stash,
381 dependant upon which MRO is in effect
382 for that stash. The return value is a
385 You are responsible for C<SvREFCNT_inc()> on the
386 return value if you plan to store it anywhere
387 semi-permanently (otherwise it might be deleted
388 out from under you the next time the cache is
394 Perl_mro_get_linear_isa(pTHX_ HV *stash)
396 struct mro_meta* meta;
398 PERL_ARGS_ASSERT_MRO_GET_LINEAR_ISA;
400 Perl_croak(aTHX_ "Can't linearize anonymous symbol table");
402 meta = HvMROMETA(stash);
403 if (!meta->mro_which)
404 Perl_croak(aTHX_ "panic: invalid MRO!");
405 return meta->mro_which->resolve(aTHX_ stash, 0);
409 =for apidoc mro_isa_changed_in
411 Takes the necessary steps (cache invalidations, mostly)
412 when the @ISA of the given package has changed. Invoked
413 by the C<setisa> magic, should not need to invoke directly.
418 Perl_mro_isa_changed_in(pTHX_ HV* stash)
427 struct mro_meta * meta;
429 const char * const stashname = HvNAME_get(stash);
430 const STRLEN stashname_len = HvNAMELEN_get(stash);
432 PERL_ARGS_ASSERT_MRO_ISA_CHANGED_IN;
435 Perl_croak(aTHX_ "Can't call mro_isa_changed_in() on anonymous symbol table");
437 /* wipe out the cached linearizations for this stash */
438 meta = HvMROMETA(stash);
439 if (meta->mro_linear_all) {
440 SvREFCNT_dec(MUTABLE_SV(meta->mro_linear_all));
441 meta->mro_linear_all = NULL;
442 /* This is just acting as a shortcut pointer. */
443 meta->mro_linear_current = NULL;
444 } else if (meta->mro_linear_current) {
445 /* Only the current MRO is stored, so this owns the data. */
446 SvREFCNT_dec(meta->mro_linear_current);
447 meta->mro_linear_current = NULL;
450 SvREFCNT_dec(meta->isa);
454 /* Inc the package generation, since our @ISA changed */
457 /* Wipe the global method cache if this package
458 is UNIVERSAL or one of its parents */
460 svp = hv_fetch(PL_isarev, stashname, stashname_len, 0);
461 isarev = svp ? MUTABLE_HV(*svp) : NULL;
463 if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
464 || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
468 else { /* Wipe the local method cache otherwise */
470 is_universal = FALSE;
473 /* wipe next::method cache too */
474 if(meta->mro_nextmethod) hv_clear(meta->mro_nextmethod);
476 /* Iterate the isarev (classes that are our children),
477 wiping out their linearization, method and isa caches */
480 while((iter = hv_iternext(isarev))) {
482 const char* const revkey = hv_iterkey(iter, &len);
483 HV* revstash = gv_stashpvn(revkey, len, 0);
484 struct mro_meta* revmeta;
486 if(!revstash) continue;
487 revmeta = HvMROMETA(revstash);
488 if (revmeta->mro_linear_all) {
489 SvREFCNT_dec(MUTABLE_SV(revmeta->mro_linear_all));
490 revmeta->mro_linear_all = NULL;
491 /* This is just acting as a shortcut pointer. */
492 revmeta->mro_linear_current = NULL;
493 } else if (revmeta->mro_linear_current) {
494 /* Only the current MRO is stored, so this owns the data. */
495 SvREFCNT_dec(revmeta->mro_linear_current);
496 revmeta->mro_linear_current = NULL;
499 revmeta->cache_gen++;
500 if(revmeta->mro_nextmethod)
501 hv_clear(revmeta->mro_nextmethod);
503 SvREFCNT_dec(revmeta->isa);
509 /* Now iterate our MRO (parents), and do a few things:
510 1) instantiate with the "fake" flag if they don't exist
511 2) flag them as universal if we are universal
512 3) Add everything from our isarev to their isarev
515 /* We're starting at the 2nd element, skipping ourselves here */
516 linear_mro = mro_get_linear_isa(stash);
517 svp = AvARRAY(linear_mro) + 1;
518 items = AvFILLp(linear_mro);
521 SV* const sv = *svp++;
524 HE *he = hv_fetch_ent(PL_isarev, sv, TRUE, 0);
526 /* That fetch should not fail. But if it had to create a new SV for
527 us, then will need to upgrade it to an HV (which sv_upgrade() can
530 mroisarev = MUTABLE_HV(HeVAL(he));
532 SvUPGRADE(MUTABLE_SV(mroisarev), SVt_PVHV);
534 /* This hash only ever contains PL_sv_yes. Storing it over itself is
535 almost as cheap as calling hv_exists, so on aggregate we expect to
536 save time by not making two calls to the common HV code for the
537 case where it doesn't exist. */
539 (void)hv_store(mroisarev, stashname, stashname_len, &PL_sv_yes, 0);
543 while((iter = hv_iternext(isarev))) {
545 char* const revkey = hv_iterkey(iter, &revkeylen);
546 (void)hv_store(mroisarev, revkey, revkeylen, &PL_sv_yes, 0);
553 =for apidoc mro_method_changed_in
555 Invalidates method caching on any child classes
556 of the given stash, so that they might notice
557 the changes in this one.
559 Ideally, all instances of C<PL_sub_generation++> in
560 perl source outside of C<mro.c> should be
561 replaced by calls to this.
563 Perl automatically handles most of the common
564 ways a method might be redefined. However, there
565 are a few ways you could change a method in a stash
566 without the cache code noticing, in which case you
567 need to call this method afterwards:
569 1) Directly manipulating the stash HV entries from
572 2) Assigning a reference to a readonly scalar
573 constant into a stash entry in order to create
574 a constant subroutine (like constant.pm
577 This same method is available from pure perl
578 via, C<mro::method_changed_in(classname)>.
583 Perl_mro_method_changed_in(pTHX_ HV *stash)
585 const char * const stashname = HvNAME_get(stash);
586 const STRLEN stashname_len = HvNAMELEN_get(stash);
588 SV ** const svp = hv_fetch(PL_isarev, stashname, stashname_len, 0);
589 HV * const isarev = svp ? MUTABLE_HV(*svp) : NULL;
591 PERL_ARGS_ASSERT_MRO_METHOD_CHANGED_IN;
594 Perl_croak(aTHX_ "Can't call mro_method_changed_in() on anonymous symbol table");
596 /* Inc the package generation, since a local method changed */
597 HvMROMETA(stash)->pkg_gen++;
599 /* If stash is UNIVERSAL, or one of UNIVERSAL's parents,
600 invalidate all method caches globally */
601 if((stashname_len == 9 && strEQ(stashname, "UNIVERSAL"))
602 || (isarev && hv_exists(isarev, "UNIVERSAL", 9))) {
607 /* else, invalidate the method caches of all child classes,
613 while((iter = hv_iternext(isarev))) {
615 const char* const revkey = hv_iterkey(iter, &len);
616 HV* const revstash = gv_stashpvn(revkey, len, 0);
617 struct mro_meta* mrometa;
619 if(!revstash) continue;
620 mrometa = HvMROMETA(revstash);
621 mrometa->cache_gen++;
622 if(mrometa->mro_nextmethod)
623 hv_clear(mrometa->mro_nextmethod);
629 Perl_mro_set_mro(pTHX_ struct mro_meta *const meta, SV *const name)
631 const struct mro_alg *const which = Perl_mro_get_from_name(aTHX_ name);
633 PERL_ARGS_ASSERT_MRO_SET_MRO;
636 Perl_croak(aTHX_ "Invalid mro name: '%"SVf"'", name);
638 if(meta->mro_which != which) {
639 if (meta->mro_linear_current && !meta->mro_linear_all) {
640 /* If we were storing something directly, put it in the hash before
642 Perl_mro_set_private_data(aTHX_ meta, meta->mro_which,
643 MUTABLE_SV(meta->mro_linear_current));
645 meta->mro_which = which;
646 /* Scrub our cached pointer to the private data. */
647 meta->mro_linear_current = NULL;
648 /* Only affects local method cache, not
649 even child classes */
651 if(meta->mro_nextmethod)
652 hv_clear(meta->mro_nextmethod);
658 XS(XS_mro_method_changed_in);
661 Perl_boot_core_mro(pTHX)
664 static const char file[] = __FILE__;
666 Perl_mro_register(aTHX_ &dfs_alg);
668 newXSproto("mro::method_changed_in", XS_mro_method_changed_in, file, "$");
671 XS(XS_mro_method_changed_in)
679 croak_xs_usage(cv, "classname");
683 class_stash = gv_stashsv(classname, 0);
684 if(!class_stash) Perl_croak(aTHX_ "No such class: '%"SVf"'!", SVfARG(classname));
686 mro_method_changed_in(class_stash);
693 * c-indentation-style: bsd
695 * indent-tabs-mode: t
698 * ex: set ts=8 sts=4 sw=4 noet: