Strange behavior of breadthfirst strategy in Rewriter trait

[GoogleCodeExporter]

The breadthfirst strategy of the Rewriter trait behaves strangely (compared to 
other strategies like topdown or bottomup) when traversing trees consisting of 
just one root node using Kiama 1.4.0.

See attached example to reproduce this behavior.

Original issue reported on code.google.com by djzupr...@googlemail.com on 6 May 2013 at 8:54

Attachments:

• BreadthFirst.scala

[GoogleCodeExporter]

Thanks for your report. Kiama inherited most of its library strategies from the 
Stratego library and the definition of breadthfirst is one of them.

The issue in your example is caused because breadthfirst does not apply its 
strategy argument to the root of the subject term. I think the main reason for 
this is that the obvious recursive definition:

    breadthfirst (s) =
        all (s) <* all (breadthfirst (s))

should not apply s directly since that would cause it to be applied to each 
non-root node twice.

You can remedy this situation by using 

    mybreadthfirst (s) =
        s <* breadthfirst (s)

Note that mybreadthfirst is equivalent in behaviour to topdown, so it is really 
only useful if you are doing side-effects so that the order of traversal 
matters.

Also, arguably these combinators are not really doing a breadthfirst traversal 
since the descendants of the first child of a term are all visited before any 
of the descendants of the second child of that term are visited.

I've added some clarifying notes to the breadthfirst ScalaDoc.

Original comment by inkytonik on 7 May 2013 at 3:42

• Changed state: Resolved
• Added labels: Milestone-Release1.5