There is a bug in Class::Std, in the way parent classes
are ordered for the BUILD and DEMOLISH methods.
The attached file contains a bunch of .pm files and a .pl file which
triggers a bug in Class::Std. Two of the .pm files print trace
messages when building and demolishing an object. They are linked by a
direct isa relationship. The other .pm files are silent. When you run
the .pl file, you obtain trace messages which show that the derived
class builds the object before the basic one and demolishes it after
the basic class.
Here is another example which illustrates better the problem. Imagine
we enrich the Shimmer example with a second inheritance level:
package Wax::Floor;
use base qw{Stuff::Shiny};
package Dessert::Topping;
use base qw{Food};
you have
Wax::Floor compares as equal to Food
Food more basic than Dessert::Topping
Dessert::Topping compares as equal to Stuff::Shiny
therefore
Wax::Floor more basic than Stuff::Shiny WHAT??!!
The problem is that "compares as equal to" really means "cannot be
compared to, therefore assumed as equal to".
In math terms, you have a partial order which the module attempts to
reinterpret as a complete preorder. Except that it does not work, it
is not transitive.
In computer science terms, the module tries to use a regular sort
algorithm with an inconsistent comparison function.
The optimum O(n.log n) comparison sort algorithms and some
less-than-optimum O(n^2) comparison sort algorithms do not
compare all pairs of elements, they deduce some comparisons
by combining others. If you know that:
x <= y
and y <= z
you do not need to compare x and z, you know that
x <= z
In math terms, the relation is transitive. In computer science terms,
the comparison function is consistent (this is not quite the same
thing, but close enough).
So, forget Hoare, Shell, Schwartz, Guttman, Rosler and Knuth (TAOCP
vol 3). Their advices are good, but irrelevant for the present
problem. You should rather follow the path trodden by Euler in
Koenigsberg, or the path trodden by Hamilton elsewhere, you should
hunt the wumpus or explore twisty passages all alike, you should read
Dijkstra and Knuth (the Stanford Graphbase).
Your task here is to take the inheritance DAG (directed acyclic
graph), prune it and traverse the resulting tree.
I have attached a patch to fix Class::Std . When demolishing objects,
the parent classes are traversed with a standard tree traversal with a
user-managed stack, plus a prune function to convert on-the-fly the
DAG into a tree. The pruning process is not based on the usual
%node_visited_already boolean hash, but on a node_visited_later()
boolean function.
But the idea of solving a graph-traversal problem with a sort was an
interesting and maybe even an amusing one, right in tune with Perl's
spirit. So I have attached another patch to fix Class::Std. This time,
I use a topological sort. Anyhow, please notice that, in the "Wolf
book" (Algorithms in Perl), topological sorts appear in the chapter
about graphs, not the chapter about sorting. The fix is based on Kurt
Stephens' distribution Data-Match-0.06. I have not used Jarkko's
fully-featured Graph module, because Jarkko might some day implement
graphs with Class-Std and you would have a problem with the
prerequisites' DNLAG (directed no longer acyclic graph).
A third patch is included, but it does *not* work. Or rather, it does
not work yet. To make it work, you should ask to the P5P to add a new
value for the "use sort" pragma:
use sort 'topological';
With this pragma, the sort algorithm would react quite differently
when the comparison function returns 0 or undef.
Config info : any perl with merge sort (in my case, 5.8.5)
and Class::Std v0.0.8
The full config info is in an attached file.
