Recursion in templates

[dsyer]

I can see that the recursive examples in the spec are commented out of the tests, so we don't yet explicitly support that. Is there a workaround? Would it be easy to implement?

[agentgt]

I don't think it is possible the way JStachio is currently implemented.

JStachio doesn't actually have stack nor can lazily load templates. The terminal state would have to be static and I can't see how that would be possible without logic that happens at compile time.

The best we could do is tail recursion which can be converted to a loop but at the moment I can't remember if most template recursion is tail or augmentative.

An obvious solution one would think is to use actual methods and mimic the recursion in Java but that would require moving the whole frame (the local variables on the top of the current call stack) from one method to another..... let me think about it some more maybe it is possible.

So to summarize. Two problems:

1. Terminal state deduced at compile time or perhaps we do not need it
2. How do we represent a recursion stack. Method calls or use an actual stack?

[agentgt]

In the mean time do you have a specific use case other than fulfilling the spec (this is more of a curiosity)? With the exception of XSLT I always avoided template recursion in the languages that supported it.

[dsyer]

My use case was rendering a tree (e.g. like a file system). Just like the tests in the spec.

[agentgt]

I figured it was probably something like that but just wanted to see.

[agentgt]

Yeah we could probably do it. It would not look pretty or be fast. I'm going to ping @sviperll but we do something like:

void render(...) {
// recursive template call
Object[] stack = new Object[]{ x, y, ...};
someTemplate(stack);
}

void someTemplate(Object[] stack) {
// restore variables like
String y = (String) stack[1];
Integer x = (Integer) stack[0]; // (we know at compile time what each type is)
// resume doing normal jstachio code generation.
}

As a side note I was considering doing something similar to support #140 without combinatoric branch explosion (e.g. use methods instead of giant switch/if statements tree... I will explain this better later).

[sviperll]

I think it's wise to support this to complete full mustache compliens (Note however that for the static-mustache project I had no such problem, because I wasn't aiming to support every mustache feature).

From the project management angle this feature sounds tricky and unknown unknowy, so I wouldn't aim to support it right away. I would probably start with just expanding everything down to some fixed depth and generating code that throws a run-time exception if the actual data goes deeper. Then I would probably try to introduce stand-alone methods for partials, but having different methods for different invocations of the same partial and only then try to actually make it work so that recursive calls actually call the same method.

From technical perspective I think the story can go something like this.

We have a scope that at compile-time is a sequence of types, like [X; Y; ...; Z]. At run time we have variable declarations that correspond to each element from the scope. Having this we may try to generate methods for partials where each scope element is some parameter of the method:

void render() {
    X v1 = v0.property1(); // Entering {{#property1}} section
    ...
    partial1(v1, v0); // render {{>partial1}}
}

The last trick to notice that will make recursive calls work is to notice that if we have [X; X; Y; ...] as a compile-time scope (on the top are two elements of type X), then we can drop the second X, because there is actually no way to address it. Every mustache-placeholder will match some property from the first X or if there is no such property in X, then there is no such property in both first and second X. The result should be something like this:

void recursivePartial1(X v1, Y v0) {
    ...
    X v2 = v1.someProperty();
    ...
    recursivePartial1(v2, v0); // we can drop v1 here
    
}

I'm writing this on my phone, so sorry for typos and errors.

[agentgt]

Yes that was more or less what I was thinking. I only had represented the various variables as an array because I thought Java had much more strict limit on arguments but it appears it is 256. I was going to use the first parameter as an int or something to differentiate different recursive calls and then do conditions but that is just implementation details.

From a PM aspect I think getting expressions set to variables needs to be done first to help finish #4 .

That is currently we repeatedly call the accessors (property like methods). The only exception to that is lambdas.

Unfortunately the above breaks static null analysis as you need to pull the result out to confirm it is not null and then use it (that is not all null analysis have monotonic rules).

Anyway the above in my mind should probably be a prerequisite before attempting recursive partials. e.g. this:

    X v2 = v1.someProperty();

[dsyer]

This (from Javadocs of @JStacheLambda) seems relevant for a workaround:

That being said the lambda can ostensibly return a template (and a model that the template uses) that then references the section body as a partial by using template() and then referencing the section body with the partial named "@section". This allows repeating or wrapping the passed in section body. In some other mustache implementations this accomplished with a render callback but because templates are compiled statically this is a powerful declaritive workaround.

But I don't understand it. Can we have an example (whether or not it is relevant)?

[agentgt]

I'm fairly sure it will not work: calling the same lambda from a lambda template (either passed in section body or annotated returned template).

Right now doing stuff like that is UB and will probably just make the compiler stackoverflow or infinite loop.

However doing the recursion within the Java lambda code is fine of course but then you would have to return the @JStache.Raw string back. In fact JMustache didn't always support recursion and when dealing with that issue I would use my garbage library JATL which I would use to generate raw HTML from a lambda call.

JMustache now for some time has supported recursion by lazy loading the templates at execution time (well not threadsafe which I plan on fixing).

The easy work around is to turn the traversal of whatever tree into a iterable with wrapped nodes via a lambda call or traditional method. Then you can decide if you want DFS (depths first) or BFS (breadth first) and or preorder, in order, or post order.

Then you just do:

{{#tree}}
{{#dfs}}
{{#nodes}}
{{node.depth}} {{! do something with depth like call another lambda }}
{{/nodes}}
{{/dfs}}
{{/tree}}

The above workarounds are how I have avoided recursion.

That being said supporting recursion first with @JStacheLambda might be easier than the general case.

In some very meta irony the biggest pain for developing this is that JStachio does not currently have an AST. We just replay tokens instead and create ad-hoc AST-like trees. In theory it is possible to do it that way but harder to reason. I was hoping to avoid doing the AST till 2.0.

Regardless it should be documented that it is a limitation at the moment and the compiler should not go in an infinite like-loop.

[dsyer]

That's a start. Can it be a complete example with the @JStache model and everything? Also not an example of the thing that I didn't understand, but I will probably open a new issue about that (#275).

[agentgt]

Here is a recursion workaround example. I will see if I can make it a little more generic as just hacked this together quickly:

https://github.com/jstachio/jstachio/tree/main/test/examples/src/main/java/io/jstach/examples/recursion