Day 16 – Revision gating in Rakudo core

The motivation

One of the Rakudo features I worked on this year was to resolve an annoyance related to the Array.splice method. As reported in a GitHub issue called Array.splice insists on flattening itself:

my @map = [[11, 12], [31,32]];
my @newrow = [21, 22];
@map.splice(1, 0, @newrow);
​
# Expected
[
    [11, 12],
    [21, 22],
    [31, 32]
]
​
# Actual
[
    [11, 12],
    21,
    22,
    [31, 32]
]

The author of the ticket tried all sorts of mechanisms to inform splice that the @newrow array should be inserted as a single element.

@map.splice(1, 0, [[[[@newrow]]]]);
@map.splice(1, 0, $@newrow);

But unfortunately these efforts were to no avail.

The “real” way to achieve the semantics the user wanted would be:

@map.splice(1, 0, [$@newrow,])

I’m not sure if hanging-commas-to-declare-single-element-lists ever genuinely did anything worthy to earn the exact volume of my distaste for them. Nevertheless I viscerally react when I see this syntax.

Not only this, but in the recent history prior to my reading this issue on Github, I had been personally annoyed by this exact issue in splice .

Clearly it was time to take this thing head-on.

This hubristic impulse led me down a rabbit hole from which it took three pull requests and a handful of months in order to extract myself.

A solution to the splice problem

I’m going to avoid wading too far into the depths of the solution — the is item trait — I crafted to resolve the above issue, as that would be a lengthy post all on its own.

However, it is worth showing a bit of how it works:

multi combine (@a, $b) { 
    [|@a,  [@a[0][0],$b]] 
}
​
multi combine (@a is item, $b) {
    # the non-itemized array returned here will match
    # the "regular" @a signature
    [@a, [@a[0], $b]]
}
​
​
multi combine ($a, $b) { 
    # The itemized array returned here will match
    # the signature containing `@a is item`
    $[$a, $b]
}
​
(reduce &combine, 1..5).raku.say;
# [[1, 2], [1, 3], [1, 4], [1, 5]]

Or, more directly using Array.splice:

use v6.e.PREVIEW; # THIS PART IS CRUCIAL!
​
my @presents = [<
  pear-tree-partridge turtle-dove french-hen calling-bird 
  golden-rings eggy-goose swimmy-swan milky-maid dancey-lady 
  leapy-lord pipey-piper drummy-drummer
>];
​
multi sub present-supplier(Int $day) {
  [ @presents[$day] xx $day+1 ]
}
​
my @christmas-presents-flat;
for ^12 -> $nth-day {
# if $nth-day == 0 {
#   @christmas-presents-flat[$nth-day] = present-supplier($nth-day)[0];
#  } 
#  else {
    @christmas-presents-flat.splice: *, 0, present-supplier($nth-day);
#  }
}
​
use PrettyDump;
pd @christmas-presents-flat;
# Array=[
#   "turtle-dove",
#   "french-hen",
#   "french-hen",
#   ...
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer",
#   "drummy-drummer"
# ]
​
multi sub present-supplier(Int $day, :$itemize!) {
  $[ @presents[$day] xx $day+1 ]
}
​
my @christmas-presents-segmented;
for ^12 -> $nth-day {
  @christmas-presents-segmented.splice: *, 0, present-supplier($nth-day, :itemize);
}
​
pd @christmas-presents-segmented;
# Array=[
#   Array=[
#       "pear-tree-partridge"
#   ],
#   Array=[
#       "turtle-dove",
#       "turtle-dove"
#   ],
#   Array=[
#       "french-hen",
#       "french-hen",
#       "french-hen"
#   ],
#   ...
# ]

This new functionality was made possible by adding candidates to Array.splice which utilized the is item trait to dispatch a nested form of the array to the primary Array.splice candidate. (There are a lot of Array.splice candidates, but they all eventually funnel into an optimized candidate.)

Here is an example candidate, and in fact the one we are using in our examples:

multi method splice(Array:D:
  Callable:D $offset, Int:D $size, @new is item
--> Array:D) is revision-gated("6.e") {
    self.splice($offset(self.elems),$size,[$@new])
}

So here we are passing along the @new array as the single itemized element in a wrapper array. When this gets to Array.splice‘s handler candidate, it will flatten the wrapper array and receive @new as a single item to be spliced in.

However, in doing so I had now changed the base behavior of Array.splice. Any code that was working as expected with itemized array arguments would break.

So, how could we introduce these new semantics into Rakudo without breaking existing code?

Therein, my friends, lay the rabbit hole at the bottom of the rabbit hole.

Enter revision gating

After some consultation on #raku-dev, I started hacking on a mechanism to mark multi candidates as “gated” to a specific revision baseline. For the @new is item candidates in Array.splice , these would be gated to language revisions 6.e and above.

This is done through a combination of features that run pretty deeply into Rakudo’s CORE.setting:

1. A new is trait needed to be created.
2. The Routine class needed to know how to become revision gated.
   1. These changes to Routine need to be supported by additions to BOOTSTRAP.nqp
3. The dispatcher needed to be made aware of revision gating and capable of handling it.

Adding the is revision-gated trait declaration

In my opinion traits are deeply cool. I often miss them when I’m programming in other languages. It’s a way to sugar over what would otherwise be some gnarly-ish metaprogramming code. Underneath, it remains said gnarly-ish metaprogramming — but it doesn’t clutter up your declaration locations. In some sense, traits are sort of a way to make metaprogramming look as safe as it actually is.

Here’s the declaration I used for is revision-gated:

multi sub trait_mod:<is>(Routine:D $r, Str :$revision-gated!) {
    my $chars := nqp::chars($revision-gated);
    my $internal-revision :=
      1 + nqp::ord($revision-gated, $chars - 1) - nqp::ord("c");
    $r.set-revision-gated;
    $r.^mixin(role is-revision-gated[$revision] {
        method REQUIRED-REVISION(--> Int) { $revision }
    }.^parameterize($internal-revision));
}

I don’t think anyone would want to look at this very often, so having it in a trait is perfect. Many traits make use of ^mixin to include a role, which can be anonymous or named (as we have here, to be able to parameterize it).

Due to the earliness where it should be possible to use this trait in the Rakudo setting, we have to do the parameterization of the role via ^parameterize rather than passing it in as a simple lexical (thanks to nine++ for devising the final incantation).

The ultimate impact of the trait is two-fold:

1. It flips a bit field in the routine object to mark it as having revision gating ($r.set-revision-gated).
2. It installs a REQUIRED-REVISION method that returns the minimum required revision as an Int.

Bootstrap concerns

Since the call to set-revision-gated is happening very early on in the setup of the Routine object, that method needs to be defined and made available through our bootstrap.c/BOOTSTRAP.nqp module, rather than as a method defined in Routine.rakumod.

Routine.HOW.add_method(Routine, 'set-revision-gated',
  nqp::getstaticcode(sub ($self) {
      $self.set_flag(0x08);
  })
);

We also need a method for checking this flag:

Routine.HOW.add_method(Routine, 'revision-gated',
  nqp::getstaticcode(sub ($self) {
     $self.get_flag(0x08);
  })
);

Also, we want to include the required revision for the candidate in the hash of “candidate info” that is stored in a field of the Routine object and which the dispatcher will eventually be using in favor of having to call methods on candidate objects (a much more costly affair):

Routine.HOW.add_method(Routine, '!create_dispatch_info',
  nqp::getstaticcode(sub ($self) {
      $self := nqp::decont($self);
      ...
      if $self.revision-gated {
          nqp::bindkey(%info, 'required_revision', $self.REQUIRED-REVISION);
      }
      ...
      nqp::bindattr($self, Routine, '$!dispatch_info', %info)
  })
);

With that we are mostly through with fiddling with the bootstrap, except in the case of the JVM, which also installs a private method onto Routine called !filter-revision-gated-candidates that will be used by the “old” dispatcher code. We will see the contents of this routine next, but in the context of MoarVM’s dispatcher, and otherwise won’t be talking about the JVM implementation here beyond mentioning that it is at feature parity with MoarVM.

Dispatching to specific revisions

The dispatcher code was recently revised and optimized. I had gotten somewhat familiar with it while adding is item, so I knew a bit of how to poke at it.

From a bird’s eye view, when a multi is called, the dispatcher receives the proto candidate and an argument capture. The dispatcher asks the proto for a list of %dispatcher_info hashes that are then whittled down to the subset of hashes that are suitable for the provided argument capture.

So then, “all” I needed to do was filter out any candidates not meeting the language revision criteria (if any) from the list of candidate hashes before that list is sent to the whittling function.

Here’s the logic that checks if the proto mentions any revision gating:

my @candidates := nqp::bitand_i(
  nqp::getattr_i($target, Routine, '$!flags'), 0x08
) ?? (my $caller-revision := nqp::getlexcaller('$?LANGUAGE-REVISION') // 1) 
       && $target.REQUIRED-REVISION <= $caller-revision
    ?? multi-filter-revision-gated-candidates($target, $caller-revision)
    !! []
  !! $target.dispatch_order;

So, if there’s no bit flipped in $!flag to indicate revision gating, we simply return $target.dispatch_order.

Otherwise, we pull $?LANGUAGE-REVISION from the lexpad (it gets installed at the top-level of every compunit) and we compare it against $target.REQUIRED-REVISION (where $target is the proto). If $target has a higher revision requirement than the $caller-revision than none of its multis will likewise have their requirements met. So in this case we set @candidates an empty list, which bubbles up to a dispatch error almost immediately.

In the more common case where the proto‘s revision requirement is met, we call multi-filter-revision-gated-candidates:

sub multi-filter-revision-gated-candidates($proto, $caller-revision) {
    my @candidates := $proto.dispatch_order;
​
    my int $idx := 0;
    my int $allowed-idx := 0;
    my @allowed-candidates;
    my %gated-candidates;
    while $idx < nqp::elems(@candidates) {
        my $candidate := nqp::atpos(@candidates, $idx++);
​
        unless nqp::isconcrete($candidate) {
            nqp::push(@allowed-candidates, $candidate);
            $allowed-idx++;
            next;
        }
​
        my $required-revision := nqp::atkey($candidate, 'required_revision');
        my $is-revision-specified := nqp::isconcrete($required-revision);
        if !$is-revision-specified || $required-revision <= $caller-revision  {
            if (nqp::existskey($candidate, 'signature')) && $is-revision-specified {
                my $signature := nqp::atkey($candidate, 'signature').raku;
                if nqp::existskey(%gated-candidates, $signature) {
                    # this is what was set as the $allowed-idx in a previous run
                    my $candidate-idx := nqp::atkey(%gated-candidates, $signature);
                    my $last-seen-revision := nqp::atkey(
                        nqp::atpos(@allowed-candidates, $candidate-idx),
                        'required_revision'
                    );
​
                    if $last-seen-revision < $required-revision {
                        nqp::bindkey(%gated-candidates, $signature, $candidate-idx);
                        nqp::bindpos(@allowed-candidates, $candidate-idx, $candidate);
                        # Do *not* bump $allowed-idx here
                    }
                } else {
                    nqp::push(@allowed-candidates, $candidate);
                    nqp::bindkey(%gated-candidates, $signature, $allowed-idx++);
                }
            } else {
                nqp::push(@allowed-candidates, $candidate);
                $allowed-idx++;
            }
        }
    }
​
    @allowed-candidates
}

A primary consideration here is that $proto.dispatch_order returns an organized list of candidate info hashes. This means we need to preserve the ordering while kicking out any inadequate candidates.

Initially routine covered fewer edge cases, and thus was slightly simpler. But since revision gating should also be able to replace multis that have the same signature but where a change of functionality is desired, I introduced the %gated-candidates hash to track minimum revision gated versions for candidates of the same signature.

This has the functional effect of allowing for the introduction of ceilings and floors for otherwise-matching candidates. This is probably best shown in an example:

How to use is revision-gated

(Please note: this evolution did not land in time for the 2024.12, so you will need to wait for 2025.01 or build Rakudo from source to use revision gating of candidates with equivalent signatures.)

my $to-eval = q:to/END/;
​
proto sub gated(|) is revision-gated("6.c") {*}
multi sub gated(Int $x) is revision-gated("6.c") { print "6.c ($x)" }
multi sub gated(Int $x) is revision-gated("6.d") { print "6.d ({$x+1})" }
multi sub gated(Int $x) is revision-gated("6.e") { print "6.e ({$x+2})" }
​
gated(6);
​
END
​
is-run 'use v6.c;' ~ $to-eval,
  :out("6.c (6)"),
  q|is revision-gated("6.c") candidate called for 'use v6.c;'|;

is-run 'use v6.d;' ~ $to-eval,
  :out("6.d (7)"),
  q|is revision-gated("6.d") candidate called for 'use v6.d;'|;

is-run 'use v6.e.PREVIEW;' ~ $to-eval,
  :out("6.e (8)"),
  q|is revision-gated("6.e") candidate called for 'use v6.e;'|;

(Note: is-run is provided by Test::Helpers which is not currently provided outside of Rakudo’s test suite.)

Here each candidate has a clear floor and ceiling: each can only run on a single language revision.

However, if we removed the 6.d candidate, the “floor” of the 6.c candidate would be 6.c and the “ceiling” would be 6.d, as a replacement is then provided in 6.e. These “floor”/”ceiling” values are implicit and contextual.

Required ingredients

Revision gating requires the following to be in place in order to work:

• The proto must specify the minimum revision for all of it’s candidates.
  • proto sub gated(|) is revision-gated("6.c") {*}
• The new candidate must specify the revision of it’s introduction.
  • multi sub gated(Int $x) is revision-gated("6.e")

However, as mentioned above, it is important to follow this additional rule:

• If the new candidate replaces an existing candidate of the same signature, the multi candidate to be replaced must set it’s own minimum revision.
  • multi sub gated(Int $x) is revision-gated("6.c")

Eventually the requirement of specifying a minimum revision for the proto may be removed but at the moment there were bootstrapping/circularity issues in play that prevented a minimum revision to be automatically installed.

Gate it and upgrade it!

I hope this helps in shedding some light on the revision-gated trait and unlocks some opportunities for code in both Rakudo core and in user space to evolve their semantics safely and effectively.

Post Scriptum

While implementing this feature, I was mostly oblivious to some long-running discussions about how to achieve the evolution of semantics across language revisions. Later I found this problem-solving ticket, which almost certainly represents only the very tip of the iceberg.

But I only found that ticket because, after merging the initial version, nine informed me of the following:

nine ab5tract: you do realize that you have finally implemented something we have only talked about for 6 or 7 years? Thanks a lot!

To which I replied:

ab5tract kind of reminds me of my trainer at the gym.. he takes care not to tell me how much weight I’m lifting until after I’m done lifting it 🙂

It’s been a great year with some heavy lifting in core and so I want to say a mega-large thank you to all the folks in #raku and #raku-dev who have managed to put up with my ups-and-downs this year. It means a lot to to me, being in the presence of such a diversely talented crowd.