breadthfirst(s) doesn’t do a breadth first traversal of the tree, instead it does topdown(all(s)) (i.e., a depth first traversal where instead of the node itself, its children are rewritten at each step.)

Here is some test code; I expected it to output the constructors in numeric order.

!One(Two(Five(Nine(), Ten()), Six()), Three(), Four(Seven(Eleven(), Twelve()), Eight()));
breadthfirst(debug)

This is the actual output:

Two(Five(Nine,Ten),Six)
Three
Four(Seven(Eleven,Twelve),Eight)
Five(Nine,Ten)
Six
Nine
Ten
Seven(Eleven,Twelve)
Eight
Eleven
Twelve

(Maybe breadthfirst in this case refers to some other meaning of breadthfirst yet unknown to me?)

Additionally it doesn’t visit the root of the tree, though that might be intentional.

Submitted by Tobi Vollebregt on 27 October 2011 at 16:01

Here is a working (though slightly ugly) breadthfirst:

Requires at-depth' from https://yellowgrass.org/issue/StrategoXT/864.

term-depth =
crush(!0, max, term-depth); inc

override breadthfirst(s) =
!(0, );
repeat-until( (d, ) -> ( d, <at-depth’(s)>)
, where({d: (?d, term-depth; ?d)}) );
?(, )

I think the intention of breadthfirst was to do a simple “breadthfirst-like” traversal. So if you fix it, it should probably get a different name… :o

I mostly put this here as documentation for others who stumble upon the same issue later on.

Fixing indeed breaks backward compatibility so it can’t be done (even if I put it under a different name). Maybe at some point if someone makes a libstratego v2 fixes like this can be put in :-)