[stringtemplate-interest] Bug in rest function when applied recursively

[John Snyders]

I was thinking about how templates can be called recursively. Just for fun I
decided to try the classic recursive definition of reverse.
    group Reverse;
    reverse(L) ::= <<
    $if(L)$
    $reverse(rest(L))$$first(L)$
    $endif$
    >>

>From another template I called $reverse(list)$ where list is an attribute
created as:
    String myList[] = { "a", "b", "c", "d", "e" };
    st.setAttribute("list", myList);

The expected result is “edcba”. It is probably not a good idea for a
template to have this kind of logic in it but I wanted to play with
recursion.

This didn’t work. All it printed was “a”. I tried adding “test $L$,
$first(L)$, $rest(L)$” as the first line of reverse to try to debug. I found
that after the first call first and rest were not working – they returned
nothing. I set a breakpoint in ASTExpr.rest. The rest method will return an
iterator over the collection (I’m using the term collection generally here)
positioned at the second element. It is this iterator and not a collection
that is passed to the template. Now rest is called with the input L being an
iterator. The trouble is that this iterator is already at the end by the
time rest is called again. I’m not exactly sure why that happened but it may
be that the $if(L)$ must evaluate L by iterating. When I added the debugging
that would definitely cause the iterator to stick at the end. The trouble
with an iterator being passed to a template rather than a collection is that
once it is used it can’t be used again! Even $first(L)$ when L is an
iterator will cause problems because it leaves the iterator one position
farther along.

I changed rest to return a new collection (ArrayList) that contains the rest
of the original collection. After making this change the reverse template
worked perfectly.

The trouble is that creating a new collection is wasteful. Perhaps there is
a way to determine if a copy of rest is needed rather than just an iterator.
For example just at the point where the iterator is going to be passed to a
template it is copied to a new collection. Are there any other cases where
an iterator should be turned to a collection?

If Java iterators supported cloning (clone would create a new iterator over
the same colection positioned at the point where the original iterator was
cloned) it may be enough to always return a cloned iterator from rest. But
Java iterators don’t allow cloning.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org:8080/pipermail/stringtemplate-interest/attachments/20060928/ecf765e2/attachment.html