Author: jonathan
Date: Sun Mar 25 17:14:29 2007
New Revision: 17747
Modified:
trunk/include/parrot/objects.h
trunk/src/objects.c
trunk/src/pmc/class.pmc
trunk/t/oo/mro-c3.t
trunk/t/pmc/class.t
Log:
[PDD15]: Initial work at implementing C3 MRO for the new class/object model.
Not optimized in any way, but clear and hopefully correct. Wrote a few tests.
Currently can't test it due to Parrot_PCCINVOKE breakage, so all C3 tests and a
few others that broke as a result of this change are TODO'd.
Modified: trunk/include/parrot/objects.h
==============================================================================
--- trunk/include/parrot/objects.h (original)
+++ trunk/include/parrot/objects.h Sun Mar 25 17:14:29 2007
@@ -99,6 +99,13 @@
# define GET_CLASS(arr, obj) \
obj->vtable->class
+
+/* ************************************************************************ */
+/* ********* BELOW HERE IS NEW PPD15 IMPLEMENTATION RELATED STUFF ********* */
+/* ************************************************************************ */
+
+PARROT_API PMC* Parrot_ComputeMRO_C3(Interp *interp, PMC *class);
+
#endif /* PARROT_OBJECTS_H_GUARD */
/*
Modified: trunk/src/objects.c
==============================================================================
--- trunk/src/objects.c (original)
+++ trunk/src/objects.c Sun Mar 25 17:14:29 2007
@@ -1695,6 +1695,142 @@
{
}
+
+/* ************************************************************************ */
+/* ********* BELOW HERE IS NEW PPD15 IMPLEMENTATION RELATED STUFF ********* */
+/* ************************************************************************ */
+
+/*
+
+=item C<PMC* Parrot_ComputeMRO_C3(Interp *interp, PMC *class)>
+
+Computes the C3 linearization for the given class.
+
+=cut
+
+*/
+
+static PMC* C3_merge(Interp *interp, PMC *merge_list)
+{
+ PMC *result = pmc_new(interp, enum_class_ResizablePMCArray);
+ int list_count = VTABLE_elements(interp, merge_list);
+ int cand_count = 0;
+ int i;
+ PMC *accepted = PMCNULL;
+
+ /* Try and find something appropriate to add to the MRO - basically, the
+ * first list head that is not in the tail of all the other lists. */
+ for (i = 0; i < list_count; i++) {
+ PMC *cand_list = VTABLE_get_pmc_keyed_int(interp, merge_list, i);
+ PMC *cand_class;
+ int reject = 0;
+ int j;
+ if (VTABLE_elements(interp, cand_list) == 0)
+ continue;
+ cand_class = VTABLE_get_pmc_keyed_int(interp, cand_list, 0);
+ cand_count++;
+ for (j = 0; j < list_count; j++) {
+ /* Skip the current list. */
+ if (j != i) {
+ /* Is it in the tail? If so, reject. */
+ PMC *check_list = VTABLE_get_pmc_keyed_int(interp, merge_list,
j);
+ int check_length = VTABLE_elements(interp, check_list);
+ int k;
+
+ for (k = 1; k < check_length; k++) {
+ if (VTABLE_get_pmc_keyed_int(interp, check_list, k) ==
cand_class) {
+ reject = 1;
+ break;
+ }
+ }
+ }
+ }
+
+ /* If we didn't reject it, this candidate will do. */
+ if (!reject) {
+ accepted = cand_class;
+ break;
+ }
+ }
+
+ /* If we never found any candidates, return an empty list. */
+ if (cand_count == 0)
+ return pmc_new(interp, enum_class_ResizablePMCArray);
+
+ /* If we didn't find anything to accept, error. */
+ if (PMC_IS_NULL(accepted)) {
+ real_exception(interp, NULL, ILL_INHERIT,
+ "Could not build C3 linearization: ambiguous hierarchy");
+ return PMCNULL;
+ }
+
+ /* Otherwise, remove what was accepted from the merge lists. */
+ for (i = 0; i < list_count; i++) {
+ PMC *list = VTABLE_get_pmc_keyed_int(interp, merge_list, i);
+ int list_count = VTABLE_elements(interp, list);
+ int j;
+ for (j = 0; j < list_count; j++) {
+ if (VTABLE_get_pmc_keyed_int(interp, list, j) == accepted) {
+ VTABLE_delete_keyed_int(interp, list, j);
+ break;
+ }
+ }
+ }
+
+ /* Need to merge what remains of the list, then put what was accepted on
+ * the start of the list, and we're done. */
+ result = C3_merge(interp, merge_list);
+ VTABLE_unshift_pmc(interp, result, accepted);
+ return result;
+}
+
+PMC* Parrot_ComputeMRO_C3(Interp *interp, PMC *class)
+{
+ PMC *result;
+ PMC *merge_list = pmc_new(interp, enum_class_ResizablePMCArray);
+ PMC *immediate_parents;
+ int i, parent_count;
+
+ /* Now get immediate parents list. */
+ Parrot_PCCINVOKE(interp, class, string_from_const_cstring(interp,
"parents", 0),
+ "->P", &immediate_parents);
+ if (immediate_parents == NULL) {
+ real_exception(interp, NULL, METH_NOT_FOUND,
+ "Failed to get parents list from class!");
+ return PMCNULL;
+ }
+ parent_count = VTABLE_elements(interp, immediate_parents);
+ if (parent_count == 0)
+ {
+ /* No parents - MRO just contains this class. */
+ result = pmc_new(interp, enum_class_ResizablePMCArray);
+ VTABLE_push_pmc(interp, result, class);
+ return result;
+ }
+
+ /* Otherwise, need to do merge. For that, need linearizations of all of
+ * our parents added to the merge list. */
+ for (i = 0; i < parent_count; i++) {
+ PMC *lin = Parrot_ComputeMRO_C3(interp,
+ VTABLE_get_pmc_keyed_int(interp, immediate_parents, i));
+ if (PMC_IS_NULL(lin))
+ return PMCNULL;
+ VTABLE_push_pmc(interp, merge_list, lin);
+ }
+
+ /* Finally, need list of direct parents on the end of the merge list, then
+ * we can merge. */
+ VTABLE_push_pmc(interp, merge_list, immediate_parents);
+ result = C3_merge(interp, merge_list);
+ if (PMC_IS_NULL(result))
+ return PMCNULL;
+
+ /* Merged result needs this class on the start, and then we're done. */
+ VTABLE_unshift_pmc(interp, result, class);
+ return result;
+}
+
+
/*
=back
Modified: trunk/src/pmc/class.pmc
==============================================================================
--- trunk/src/pmc/class.pmc (original)
+++ trunk/src/pmc/class.pmc Sun Mar 25 17:14:29 2007
@@ -351,14 +351,8 @@
/* If we've not been instantiated before... */
if (!class->instantiated) {
/* Build full parents list.
- * XXX While waiting a decision on the MRO stuff, we just put
- * ourself and our immediate parents in the list... */
- int i;
- class->all_parents = pmc_new(interp, enum_class_ResizablePMCArray);
- VTABLE_push_pmc(interp, class->all_parents, SELF);
- for (i = 0; i < VTABLE_elements(interp, class->parents); i++)
- VTABLE_push_pmc(interp, class->all_parents,
- VTABLE_get_pmc_keyed_int(interp, class->parents, i));
+ * XXX Need pluggable MRO, for now always do C3. */
+ class->all_parents = Parrot_ComputeMRO_C3(interp, class);
/* Build attributes index. */
Parrot_Class_build_attrib_index(interp, SELF);
Modified: trunk/t/oo/mro-c3.t
==============================================================================
--- trunk/t/oo/mro-c3.t (original)
+++ trunk/t/oo/mro-c3.t Sun Mar 25 17:14:29 2007
@@ -6,7 +6,7 @@
use warnings;
use lib qw( . lib ../lib ../../lib );
use Test::More;
-use Parrot::Test tests => 1;
+use Parrot::Test tests => 3;
=head1 NAME
@@ -22,15 +22,132 @@
=cut
-# L<PDD15>
-# TODO update smartlink
-# TODO write real tests :)
-pir_output_is( <<'CODE', <<'OUT', 'stup' );
+pir_output_is( <<'CODE', <<'OUT', 'single parent', todo => 'Parrot_PCCINVOKE
broken' );
.sub 'test' :main
- say 'ok 1 - just a stub'
+ .local pmc A, B
+
+ A = new .Class
+ $P0 = find_global 'testA'
+ A.'add_method'("foo", $P0)
+ A.'add_method'("bar", $P0)
+
+ B = new .Class
+ B.'add_parent'(A)
+ $P0 = find_global 'testB'
+ B.'add_method'("foo", $P0)
+
+ $P0 = B.'new'()
+ $P0.foo()
+ $P0.bar()
+.end
+
+.sub testA :method
+ print "Method from A called\n"
+.end
+.sub testB :method
+ print "Method from B called\n"
+.end
+CODE
+Method from B called
+Method from A called
+OUT
+
+pir_output_is( <<'CODE', <<'OUT', 'grandparent', todo => 'Parrot_PCCINVOKE
broken' );
+.sub 'test' :main
+ .local pmc A, B, C
+
+ A = new .Class
+ $P0 = find_global 'testA'
+ A.'add_method'("foo", $P0)
+ A.'add_method'("bar", $P0)
+ A.'add_method'("baz", $P0)
+
+ B = new .Class
+ B.'add_parent'(A)
+ $P0 = find_global 'testB'
+ B.'add_method'("foo", $P0)
+ B.'add_method'("bar", $P0)
+
+ C = new .Class
+ C.'add_parent'(B)
+ $P0 = find_global 'testC'
+ C.'add_method'("foo", $P0)
+
+ $P0 = C.'new'()
+ $P0.foo()
+ $P0.bar()
+ $P0.baz()
+.end
+
+.sub testA :method
+ print "Method from A called\n"
+.end
+.sub testB :method
+ print "Method from B called\n"
+.end
+.sub testC :method
+ print "Method from C called\n"
+.end
+CODE
+Method from C called
+Method from B called
+Method from A called
+OUT
+
+pir_output_is( <<'CODE', <<'OUT', 'diamond inheritance', todo =>
'Parrot_PCCINVOKE broken' );
+.sub 'test' :main
+ .local pmc A, B, C, D
+
+ A = new .Class
+ $P0 = find_global 'testA'
+ A.'add_method'("foo", $P0)
+ A.'add_method'("bar", $P0)
+ A.'add_method'("baz", $P0)
+ A.'add_method'("wag", $P0)
+
+ B = new .Class
+ B.'add_parent'(A)
+ $P0 = find_global 'testB'
+ B.'add_method'("foo", $P0)
+ B.'add_method'("bar", $P0)
+
+ C = new .Class
+ C.'add_parent'(A)
+ $P0 = find_global 'testC'
+ C.'add_method'("foo", $P0)
+ C.'add_method'("bar", $P0)
+ B.'add_method'("baz", $P0)
+
+ D = new .Class
+ D.'add_parent'(B)
+ D.'add_parent'(C)
+ $P0 = find_global 'testD'
+ D.'add_method'("foo", $P0)
+
+ $P0 = D.'new'()
+ $P0.foo()
+ $P0.bar()
+ $P0.baz()
+ $P0.wag()
+.end
+
+.sub testA :method
+ print "Method from A called\n"
+.end
+.sub testB :method
+ print "Method from B called\n"
+.end
+.sub testC :method
+ print "Method from C called\n"
+.end
+.sub testD :method
+ print "Method from D called\n"
.end
CODE
-ok 1 - just a stub
+Method from D called
+Method from C called
+Method from B called
+Method from A called
OUT
# Local Variables:
Modified: trunk/t/pmc/class.t
==============================================================================
--- trunk/t/pmc/class.t (original)
+++ trunk/t/pmc/class.t Sun Mar 25 17:14:29 2007
@@ -91,7 +91,7 @@
OUT
# L<PDD15/Class PMC API/=item new>
-pir_output_is( <<'CODE', <<'OUT', 'new' );
+pir_output_is( <<'CODE', <<'OUT', 'new', todo => 'Parrot_PCCINVOKE broken' );
.sub 'test' :main
new $P0, .Class
$P1 = $P0.'new'()
@@ -195,7 +195,7 @@
## NOTE i think this belongs in the Object PMC tests
# L<PDD15/Class PMC API>
-pir_output_is( <<'CODE', <<'OUT', 'set_attr/get_attr VTABLE methods' );
+pir_output_is( <<'CODE', <<'OUT', 'set_attr/get_attr VTABLE methods', todo =>
'Parrot_PCCINVOKE broken' );
.sub 'test' :main
new $P0, .Class
$P0.'name'("Test")
