MRO aux structure

I'm not quite comfortable about the ABI we're about to bake
in with
the MRO meta structure:

typedef enum {
    MRO_DFS, /* 0 */
    MRO_C3   /* 1 */
} mro_alg;

struct mro_meta {
    AV      *mro_linear_dfs; /* cached dfs ISA
linearization */
    AV      *mro_linear_c3;  /* cached c3 ISA
linearization */
    HV      *mro_nextmethod; /* next::method caching */
    U32     cache_gen;       /* Bumping this invalidates our
method cache */
    U32     pkg_gen;         /* Bumps when local
methods/ISA change */
    mro_alg mro_which;       /* which mro alg is in use? */
};



Specifically, as is, we're about to (effectively) impose an
ABI with an
implied central numeric registry of MRO algorithms. Whilst
we don't yet have
an API for adding MRO algorithms, what we have will make it
tricky. I'd
prefer it it we did something like the appended patch, in
time for the
binary freeze implied by 5.10

With this, it would be possible to change mro.c to use a
hash to store MRO
algorithms in, in 5.10.1 or 5.10.2, and add an ABI to add
them.

Nicholas Clark

==== //depot/perl/hv.h#109 - /home/nick/p4perl/perl/hv.h
====
--- /tmp/tmp.14184.1	Mon Sep 10 16:31:26 2007
+++ /home/nick/p4perl/perl/hv.h	Mon Sep 10 14:50:46 2007
 -41,10
+41,9  struct shared_he {
    Use the funcs in mro.c
 */
 
-typedef enum {
-    MRO_DFS, /* 0 */
-    MRO_C3   /* 1 */
-} mro_alg;
+
+/* structure may change, so not public yet */
+struct mro_alg;
 
 struct mro_meta {
     AV      *mro_linear_dfs; /* cached dfs ISA
linearization */
 -52,7
+51,7  struct mro_meta {
     HV      *mro_nextmethod; /* next::method caching */
     U32     cache_gen;       /* Bumping this invalidates
our method cache */
     U32     pkg_gen;         /* Bumps when local
methods/ISA change */
-    mro_alg mro_which;       /* which mro alg is in use?
*/
+    const struct mro_alg *mro_which; /* which mro alg is in
use? */
 };
 
 /* Subject to change.
==== //depot/perl/mro.c#30 - /home/nick/p4perl/perl/mro.c
====
--- /tmp/tmp.14184.2	Mon Sep 10 16:31:26 2007
+++ /home/nick/p4perl/perl/mro.c	Mon Sep 10 14:53:38 2007
 -23,6
+23,31  These functions are related to the metho
 #include "EXTERN.h"
 #include "perl.h"
 
+struct mro_alg {
+    const char *name;
+    AV *(*resolve)(pTHX_ HV* stash, I32 level);
+};
+
+/* First one is the default */
+static struct mro_alg mros[] = {
+    {"dfs", Perl_mro_get_linear_isa_dfs},
+    {"c3", Perl_mro_get_linear_isa_c3}
+};
+
+#define NUMBER_OF_MROS (sizeof(mros)/sizeof(struct
mro_alg))
+
+static const struct mro_alg *
+S_get_mro_from_name(pTHX_ const char *const name) {
+    const struct mro_alg *algo = mros;
+    const struct mro_alg *const end = mros +
NUMBER_OF_MROS;
+    while (algo < end) {
+	if(strEQ(name, algo->name))
+	    return algo;
+	++algo;
+    }
+    return NULL;
+}
+
 struct mro_meta*
 Perl_mro_meta_init(pTHX_ HV* stash)
 {
 -35,6
+60,7  Perl_mro_meta_init(pTHX_ HV* stash)
     HvAUX(stash)->xhv_mro_meta = newmeta;
     newmeta->cache_gen = 1;
     newmeta->pkg_gen = 1;
+    newmeta->mro_which = (void *) mros;
 
     return newmeta;
 }
 -426,14
+452,9  Perl_mro_get_linear_isa(pTHX_ HV *stash)
         Perl_croak(aTHX_ "Can't linearize anonymous
symbol table");
 
     meta = HvMROMETA(stash);
-    if(meta->mro_which == MRO_DFS) {
-        return mro_get_linear_isa_dfs(stash, 0);
-    } else if(meta->mro_which == MRO_C3) {
-        return mro_get_linear_isa_c3(stash, 0);
-    } else {
+    if (!meta->mro_which)
         Perl_croak(aTHX_ "panic: invalid MRO!");
-    }
-    return NULL; /* NOT REACHED */
+    return meta->mro_which->resolve(aTHX_ stash, 0);
 }
 
 /*
 -693,12
+714,10  XS(XS_mro_get_linear_isa) {
     }
     else if(items > 1) {
         const char* const which = SvPV_nolen(ST(1));
-        if(strEQ(which, "dfs"))
-            RETVAL = mro_get_linear_isa_dfs(class_stash,
0);
-        else if(strEQ(which, "c3"))
-            RETVAL = mro_get_linear_isa_c3(class_stash,
0);
-        else
-            Perl_croak(aTHX_ "Invalid mro name:
'%s'", which);
+	const struct mro_alg *const algo =
S_get_mro_from_name(aTHX_ which);
+	if (!algo)
+	    Perl_croak(aTHX_ "Invalid mro name: '%s'",
which);
+	algo->resolve(aTHX_ class_stash, 0);
     }
     else {
         RETVAL = mro_get_linear_isa(class_stash);
 -714,8
+733,8  XS(XS_mro_set_mro)
     dVAR;
     dXSARGS;
     SV* classname;
-    char* whichstr;
-    mro_alg which;
+    const char* whichstr;
+    const struct mro_alg *which;
     HV* class_stash;
     struct mro_meta* meta;
 
 -730,11
+749,8  XS(XS_mro_set_mro)
     if(!class_stash) Perl_croak(aTHX_ "Cannot create
class: '%"SVf"'!", SVfARG(classname));
     meta = HvMROMETA(class_stash);
 
-    if(strEQ(whichstr, "dfs"))
-        which = MRO_DFS;
-    else if(strEQ(whichstr, "c3"))
-        which = MRO_C3;
-    else
+    which = S_get_mro_from_name(aTHX_ whichstr);
+    if (!which)
         Perl_croak(aTHX_ "Invalid mro name:
'%s'", whichstr);
 
     if(meta->mro_which != which) {
 -765,11
+781,9  XS(XS_mro_get_mro)
     classname = ST(0);
     class_stash = gv_stashsv(classname, 0);
 
-    if(!class_stash || HvMROMETA(class_stash)->mro_which
== MRO_DFS)
-        ST(0) = sv_2mortal(newSVpvn("dfs", 3));
-    else
-        ST(0) = sv_2mortal(newSVpvn("c3", 2));
-
+    ST(0) = sv_2mortal(newSVpv(class_stash
+			       ? HvMROMETA(class_stash)->mro_which->name
+			       : "dfs", 0));
     XSRETURN(1);
 }
 

On 9/10/07, Nicholas Clark <nickccl4.org> wrote:
> I'm not quite comfortable about the ABI we're about to
bake in with
> the MRO meta structure:
...
> Specifically, as is, we're about to (effectively)
impose an ABI with an
> implied central numeric registry of MRO algorithms.
Whilst we don't yet have
> an API for adding MRO algorithms, what we have will
make it tricky. I'd
> prefer it it we did something like the appended patch,
in time for the
> binary freeze implied by 5.10
>
> With this, it would be possible to change mro.c to use
a hash to store MRO
> algorithms in, in 5.10.1 or 5.10.2, and add an ABI to
add them.

Seems sortof related to the regexp engine plug in interface.
Maybe its
just a surface similarity (external modification of deep
internals
voodoo) but possibly a unified framework to handle stuff
like this is
worth a little thought.

Yves


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

On 9/10/07, Ben Morrow <benmorrow.me.uk> wrote:
>
> Quoth nickccl4.org (Nicholas Clark):
> > I'm not quite comfortable about the ABI we're
about to bake in with
> > the MRO meta structure:
> >
> > typedef enum {
> >     MRO_DFS, /* 0 */
> >     MRO_C3   /* 1 */
> > } mro_alg;
> >
> > struct mro_meta {
> >     AV      *mro_linear_dfs; /* cached dfs ISA
linearization */
> >     AV      *mro_linear_c3;  /* cached c3 ISA
linearization */
>
> If we're assuming more than two MROs, should these be
here? Should they
> not instead be inside a more general void * or SV * or
struct mro_ctx *
> member?
>

To the thread in general: I haven't reviewed Nicholas' patch
in depth,
but I'm in agreement that this sort of change is a positive
thing and
I trust that he'd do it "right" .  We
discussed such a thing a while
back but no code was produced at the time.

As to the explicit dfs and c3 mro caches and the addition of
more of
them, I'm not sure what the clean solution is really.  I
think the
general concept the current code embodies (which is that
MROs are
algorithms that reduce a tree of ISA inheritance into a
linear list
of classes to search) is sound, so certainly one could make
the
argument that it should be a single "AV * mro_linear;
/* cache of
current ISA linearization */", which caches whatever MRO
is currently
in effect.  It could be wiped on mro algorithm changes in a
given
package.  That would be the easy answer to the above.

At issue is (a) not all inheritance trees are of homogeneous
MRO, (b)
MRO calculations always use the top-level MRO in effect (for
example,
when a C3 class inherits from a dfs class, the dfs class's
parents are
searched in C3 order) and (c) both of the current MROs make
use of
parent linearizations to speed up creating new ones, which
aren't
available unless you're independently caching all of the
different MRO
algorithms.

I suspect this caching logic will be equally applicable to
future MROs
if any ever exist, so it might make the most sense to have
the caches
be a C array of caches using the same indices as this stuff
from
Nicholas' patch:

+/* First one is the default */
+static struct mro_alg mros[] = {
+    {"dfs", Perl_mro_get_linear_isa_dfs},
+    {"c3", Perl_mro_get_linear_isa_c3}
+};
+

-- Brandon

On Mon, Sep 10, 2007 at 09:30:55PM -0700, Brandon Black
wrote:
> On 9/10/07, Ben Morrow <benmorrow.me.uk> wrote:
> >
> > Quoth nickccl4.org (Nicholas Clark):
> > > I'm not quite comfortable about the ABI we're
about to bake in with
> > > the MRO meta structure:
> > >
> > > typedef enum {
> > >     MRO_DFS, /* 0 */
> > >     MRO_C3   /* 1 */
> > > } mro_alg;
> > >
> > > struct mro_meta {
> > >     AV      *mro_linear_dfs; /* cached dfs
ISA
linearization */
> > >     AV      *mro_linear_c3;  /* cached c3
ISA
linearization */
> >
> > If we're assuming more than two MROs, should these
be here? Should they
> > not instead be inside a more general void * or SV
* or struct mro_ctx *
> > member?

> argument that it should be a single "AV *
mro_linear; /* cache of
> current ISA linearization */", which caches
whatever MRO is currently
> in effect.  It could be wiped on mro algorithm changes
in a given
> package.  That would be the easy answer to the above.

I did wonder about trying this yesterday. But then I wasn't
sure if it was
a great idea this late in the day.

> At issue is (a) not all inheritance trees are of
homogeneous MRO, (b)
> MRO calculations always use the top-level MRO in effect
(for example,
> when a C3 class inherits from a dfs class, the dfs
class's parents are
> searched in C3 order) and (c) both of the current MROs
make use of
> parent linearizations to speed up creating new ones,
which aren't
> available unless you're independently caching all of
the different MRO
> algorithms.

Because I inferred that this would be the case, having
looked at the code.
Although what I don't know is how often a C3 class inherits
from a dfs class
in the real world.

> I suspect this caching logic will be equally applicable
to future MROs
> if any ever exist, so it might make the most sense to
have the caches
> be a C array of caches using the same indices as this
stuff from
> Nicholas' patch:
> 
> +/* First one is the default */
> +static struct mro_alg mros[] = {
> +    {"dfs", Perl_mro_get_linear_isa_dfs},
> +    {"c3", Perl_mro_get_linear_isa_c3}
> +};
> +

Aha. Except.

I was assuming that that array was a current implementation
detail.
My assumption was that a "proper" API that let you
register another MRO
algorithm would internally use some sort of hash.

I guess you could use an array, and on registering you get
told "today, you're
number 4 in the array".

But if so, I suspect that we can repurpose the two AV*
member in the structure
without breaking binary compatibility *if* what they point
to is externally
considered an implementation detail.

Nicholas Clark

On 9/11/07, Nicholas Clark <nickccl4.org> wrote:
> On Mon, Sep 10, 2007 at 09:30:55PM -0700, Brandon Black
wrote:
> > I suspect this caching logic will be equally
applicable to future MROs
> > if any ever exist, so it might make the most sense
to have the caches
> > be a C array of caches using the same indices as
this stuff from
> > Nicholas' patch:
> >
> > +/* First one is the default */
> > +static struct mro_alg mros[] = {
> > +    {"dfs",
Perl_mro_get_linear_isa_dfs},
> > +    {"c3", Perl_mro_get_linear_isa_c3}
> > +};
> > +
>
> Aha. Except.
>
> I was assuming that that array was a current
implementation detail.
> My assumption was that a "proper" API that
let you register another MRO
> algorithm would internally use some sort of hash.
>
> I guess you could use an array, and on registering you
get told "today, you're
> number 4 in the array".
>
> But if so, I suspect that we can repurpose the two AV*
member in the structure
> without breaking binary compatibility *if* what they
point to is externally
> considered an implementation detail.
>

I think we can replace the two AV* members with a single
AV** which
grows to NUMBER_OF_MROS.  And yes, we should be able to
reference MRO
algorithms and their caches by number, which would be
returned on
registration in the case of dynamic registration of MRO
algorithms.
The registration function would just take an MRO name and a
function
pointer for linearization, and extend the private
"static struct
mro_alg mros[]", extend the AV** of caches, and extend
NUMBER_OF_MROS,
none of which could be fixed-size things anymore.

-- Brandon

On Mon, Sep 10, 2007 at 04:42:50PM +0100, Nicholas Clark
wrote:

> With this, it would be possible to change mro.c to use
a hash to store MRO
> algorithms in, in 5.10.1 or 5.10.2, and add an ABI to
add them.

After chatting with Brandon on IRC I've applied the patch as
change 31977
(with correction for the two functions that changed to
static linking)

Nicholas Clark

On Mon, Sep 10, 2007 at 07:34:47PM +0200, demerphq wrote:
> On 9/10/07, Nicholas Clark <nickccl4.org> wrote:
> > I'm not quite comfortable about the ABI we're
about to bake in with
> > the MRO meta structure:
> ...
> > Specifically, as is, we're about to (effectively)
impose an ABI with an
> > implied central numeric registry of MRO
algorithms. Whilst we don't yet have
> > an API for adding MRO algorithms, what we have
will make it tricky. I'd
> > prefer it it we did something like the appended
patch, in time for the
> > binary freeze implied by 5.10
> >
> > With this, it would be possible to change mro.c to
use a hash to store MRO
> > algorithms in, in 5.10.1 or 5.10.2, and add an ABI
to add them.
> 
> Seems sortof related to the regexp engine plug in
interface. Maybe its
> just a surface similarity (external modification of
deep internals
> voodoo) but possibly a unified framework to handle
stuff like this is
> worth a little thought.

Yes. I'm not certain if it's just surface similarity.

The big common thing I can think of is both probably work in
the same way -
provide something that is accessed through a dispatch table,
where the
dispatch table is located in a shared library loaded at
runtime, and
pointers to that dispatch table start getting baked into
Perl internal
structures all over the place. Which means that there is a
potentially issue
if the library wants to unload itself. Either it just does
it (and breaks
things), or it's forbidden (which might make runtime
reloading hard, or some
sort of reference tracking is needed.

Nicholas Clark