There's more than one way to do it...

In the process of paying the taxes, I've come across one of the important classes in Kakapo that needs "updating."

In this case, "updating" means "complete rewrite," since I've got the new class system working. So I thought I'd show a before/after version of the code.


Here's the before version:

module DependencyQueue;
# A queue that orders its entries according to their prerequisites.

_pre_initload();

method added(*@value)        { self._ATTR_HASH('added', @value); }
method already_done(*@value)    { self._ATTR_HASH('already_done', @value); }
method cycle(*@value)        { self._ATTR_HASH('cycle', @value); }
method cycle_keys(*@value)    { self._ATTR_ARRAY('cycle_keys', @value); }
method open(*@value)        { self._ATTR_HASH('open', @value); }
method pending(*@value)        { self._ATTR_HASH('pending', @value); }
method queue(*@value)        { self._ATTR_ARRAY('queue', @value); }
   
method add_entry($name, $value, :@requires?) {
    unless @requires { @requires := Array::new(); }
   
    my @entry := Array::new($name, $value, @requires);
    self.pending{$name} := @entry;
}

method already_added($name) {
    return self.already_done{$name} || self.added{$name};
}

method init(@args, %opts) {
    for @args {
        self.mark_as_done(~ $_);
    }
   
    self.open(1);
}

method is_empty() {
    if self.open {
        return self.pending.elements == 0;
    }
   
    return self.queue.elements == 0;
}

method mark_as_done($label) {
    self.already_done{$label} := 1;
}

method marked_done($label) {
    return self.already_done{$label};
}

method next() {
    if self.open {
        self.tsort_queue();
    }

    if self.queue.elements {
        my $node := self.queue.shift;
        self.mark_as_done($node[0]);
        return $node[1];
    }
   
    return my $undef;
}

sub _pre_initload() {
    if our $_Pre_initload_done { return 0; }
    $_Pre_initload_done := 1;
   
    use('Dumper');
   
    Class::SUBCLASS('DependencyQueue',
        'Class::HashBased');
}

method reset() {
    self.open(1);
    self.pending(Hash::empty());
}

method tsort_queue() {
    self.open(0);
    self.cycle_keys(Array::empty());
    self.cycle(Hash::empty());
    self.added(Hash::empty());

    self.tsort_add_keys(self.pending.keys);
}

method tsort_add_keys(@list) {
# Visits a list of keys, adding the attached calls to the queue in topological order.

    for @list {
        my $key := $_;       
       
        unless self.already_added($key) {
            ## First, check for cycles in the graph.
            my $cycle_elts := self.cycle_keys.elements;
            self.cycle_keys.push($key);
           
            if self.cycle.exists($key) {
                my @slice := self.cycle_keys.slice(:from(self.cycle{$key}));

                Opcode::die("Cycle detected in dependencies: ",
                    @slice.join(', '),
                );
            }
           
            self.cycle{$key} := $cycle_elts;
           
            ## Put everything $key depends on ahead of $key
            my $node := self.pending{$key};
           
            my @prerequisites := $node[2];
            self.tsort_add_keys(@prerequisites);
           
            ## Finally, it's my turn.
            self.added{$key} := 1;
            self.queue.push($node);
        }
    }
}

 The first few lines are the 'module' declaration and the call to _pre_initload. The call is a waste, since Kakapo.nqp calls this one in the "super-duper-early" section, since the dep-q is used to implement the ordering for all the other modules.

Looking at the _pre_initload sub, the class is declared as a direct subclass of HashBased, which was my old root behavior. I can rewrite this class header using the 'class' keyword and no call to _pre_initload. I should put my copyright block in:

# Copyright (C) 2009-2010, Austin Hastings. See accompanying LICENSE file, or
# http://www.opensource.org/licenses/artistic-license-2.0.php for license.

class DependencyQueue;
# A queue that orders its entries according to their prerequisites.

The next block is a bunch of attribute-methods. Those are automatically generated using the P6metaclass 'has' sub:

INIT {
    use(    'P6metaclass' );
   
    has(    '%!added',
        '%!already_done',
        '%!cycle',
        '@!cycle_keys',
        '%!open',
        '%!pending',
        '@!queue'
    );
}

The next bunch of methods is generally not going to change. The automatically generated methods should have the same names, and the same behaviors, as the hand-coded ones they replaced. The 'init' method is different, though. That method has been replaced by a series of methods, one of which fills the bill here:

method _init_positional_(@pos) {
    for @pos {
        self.mark_as_done(~ $_);
    }
   
    self.open(1);
}

Plus, of course, the _pre_initload sub goes away entirely, since the class creation has moved to the class header. If this were not such an important class, I would probably add a call to the INIT header to tell the system that there is no further initload processing to be done. But dep-q runs before the Program:: module does, which is where that information is tracked. (Program:: creates a DependencyQueue to do the tracking.)

Anyway, here's the rewritten code:

# Copyright (C) 2009-2010, Austin Hastings. See accompanying LICENSE file, or
# http://www.opensource.org/licenses/artistic-license-2.0.php for license.

class DependencyQueue;
# A queue that orders its entries according to their prerequisites.

INIT {
    use(    'P6metaclass' );
   
    has(    '%!added',
        '%!already_done',
        '%!cycle',
        '@!cycle_keys',
        '%!open',
        '%!pending',
        '@!queue'
    );
}
       
method add_entry($name, $value, :@requires?) {
    unless @requires { @requires := Array::new(); }
   
    my @entry := Array::new($name, $value, @requires);
    self.pending{$name} := @entry;
}

method already_added($name) {
    return self.already_done{$name} || self.added{$name};
}

method _init_positional_(@pos) {
    for @pos {
        self.mark_as_done(~ $_);
    }
   
    self.open(1);
}

method is_empty() {
    if self.open {
        return self.pending.elements == 0;
    }
   
    return self.queue.elements == 0;
}

method mark_as_done($label) {
    self.already_done{$label} := 1;
}

method marked_done($label) {
    return self.already_done{$label};
}

method next() {
    if self.open {
        self.tsort_queue();
    }

    if self.queue.elements {
        my $node := self.queue.shift;
        self.mark_as_done($node[0]);
        return $node[1];
    }
   
    return my $undef;
}

method reset() {
    self.open(1);
    self.pending(Hash::empty());
}

method tsort_queue() {
    self.open(0);
    self.cycle_keys(Array::empty());
    self.cycle(Hash::empty());
    self.added(Hash::empty());

    self.tsort_add_keys(self.pending.keys);
}

method tsort_add_keys(@list) {
# Visits a list of keys, adding the attached calls to the queue in topological order.

    for @list {
        my $key := $_;       
       
        unless self.already_added($key) {
            ## First, check for cycles in the graph.
            my $cycle_elts := self.cycle_keys.elements;
            self.cycle_keys.push($key);
           
            if self.cycle.exists($key) {
                my @slice := self.cycle_keys.slice(:from(self.cycle{$key}));

                Opcode::die("Cycle detected in dependencies: ",
                    @slice.join(', '),
                );
            }
           
            self.cycle{$key} := $cycle_elts;
           
            ## Put everything $key depends on ahead of $key
            my $node := self.pending{$key};
           
            my @prerequisites := $node[2];
            self.tsort_add_keys(@prerequisites);
           
            ## Finally, it's my turn.
            self.added{$key} := 1;
            self.queue.push($node);
        }
    }
}