You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by su...@apache.org on 2021/08/14 14:59:47 UTC
[groovy] branch master updated: Rewrite Groovy source code in core
to Java(tailrec) (closes #1612)
This is an automated email from the ASF dual-hosted git repository.
sunlan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/groovy.git
The following commit(s) were added to refs/heads/master by this push:
new b4b2134 Rewrite Groovy source code in core to Java(tailrec) (closes #1612)
b4b2134 is described below
commit b4b2134953cd79ef359e51dc5d784d097d971f6f
Author: Daniel Sun <su...@apache.org>
AuthorDate: Sat Aug 14 14:00:57 2021 +0800
Rewrite Groovy source code in core to Java(tailrec) (closes #1612)
---
.../groovy/transform/tailrec/AstHelper.groovy | 75 -----
.../transform/tailrec/CollectRecursiveCalls.groovy | 60 ----
.../transform/tailrec/HasRecursiveCalls.groovy | 61 ----
.../transform/tailrec/InWhileLoopWrapper.groovy | 83 ------
.../transform/tailrec/RecursivenessTester.groovy | 101 -------
.../ReturnStatementToIterationConverter.groovy | 147 ----------
.../transform/tailrec/StatementReplacer.groovy | 106 -------
.../tailrec/TailRecursiveASTTransformation.groovy | 263 -----------------
.../tailrec/VariableAccessReplacer.groovy | 69 -----
.../tailrec/VariableExpressionReplacer.groovy | 163 -----------
.../tailrec/VariableExpressionTransformer.groovy | 46 ---
.../groovy/transform/TailRecursive.java} | 26 +-
.../groovy/transform/tailrec/AstHelper.java | 78 +++++
.../transform/tailrec/CollectRecursiveCalls.java | 64 +++++
.../transform/tailrec/GotoRecurHereException.java | 26 ++
.../transform/tailrec/HasRecursiveCalls.java | 63 +++++
.../transform/tailrec/InWhileLoopWrapper.java | 60 ++++
.../transform/tailrec/RecursivenessTester.java | 121 ++++++++
.../transform/tailrec/ReturnAdderForClosures.java} | 31 +-
.../ReturnStatementToIterationConverter.java | 170 +++++++++++
.../transform/tailrec/StatementReplacer.java | 174 ++++++++++++
.../tailrec/TailRecursiveASTTransformation.java | 313 +++++++++++++++++++++
.../tailrec/TernaryToIfStatementConverter.java} | 28 +-
.../transform/tailrec/UsedVariableTracker.java | 38 +++
.../transform/tailrec/VariableAccessReplacer.java | 66 +++++
.../tailrec/VariableExpressionReplacer.java | 219 ++++++++++++++
.../tailrec/VariableExpressionTransformer.java | 66 +++++
.../tailrec/VariableReplacedListener.java | 29 ++
.../transform/tailrec/StatementReplacerTest.groovy | 22 +-
.../tailrec/VariableExpressionReplacerTest.groovy | 2 +-
30 files changed, 1544 insertions(+), 1226 deletions(-)
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/AstHelper.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/AstHelper.groovy
deleted file mode 100644
index 35cf13f..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/AstHelper.groovy
+++ /dev/null
@@ -1,75 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ClassNode
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.VariableExpression
-import org.codehaus.groovy.ast.stmt.ContinueStatement
-import org.codehaus.groovy.ast.stmt.ExpressionStatement
-import org.codehaus.groovy.ast.stmt.Statement
-
-import java.lang.reflect.Modifier
-
-import static org.codehaus.groovy.ast.tools.GeneralUtils.classX
-import static org.codehaus.groovy.ast.tools.GeneralUtils.declS
-import static org.codehaus.groovy.ast.tools.GeneralUtils.localVarX
-import static org.codehaus.groovy.ast.tools.GeneralUtils.propX
-import static org.codehaus.groovy.ast.tools.GeneralUtils.throwS
-import static org.codehaus.groovy.ast.tools.GeneralUtils.varX
-
-/**
- * Helping to create a few standard AST constructs
- */
-@CompileStatic
-class AstHelper {
- static ExpressionStatement createVariableDefinition(String variableName, ClassNode variableType, Expression value, boolean variableShouldBeFinal = false) {
- def newVariable = localVarX(variableName, variableType)
- if (variableShouldBeFinal)
- newVariable.modifiers = Modifier.FINAL
- (ExpressionStatement) declS(newVariable, value)
- }
-
- static ExpressionStatement createVariableAlias(String aliasName, ClassNode variableType, String variableName) {
- createVariableDefinition(aliasName, variableType, varX(variableName, variableType))
- }
-
- static VariableExpression createVariableReference(Map variableSpec) {
- varX((String) variableSpec.name, (ClassNode) variableSpec.type)
- }
-
- /**
- * This statement should make the code jump to surrounding while loop's start label
- * Does not work from within Closures
- */
- static Statement recurStatement() {
- //continue _RECUR_HERE_
- new ContinueStatement(InWhileLoopWrapper.LOOP_LABEL)
- }
-
- /**
- * This statement will throw exception which will be caught and redirected to jump to surrounding while loop's start label
- * Also works from within Closures but is a tiny bit slower
- */
- static Statement recurByThrowStatement() {
- // throw InWhileLoopWrapper.LOOP_EXCEPTION
- throwS(propX(classX(InWhileLoopWrapper), 'LOOP_EXCEPTION'))
- }
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.groovy
deleted file mode 100644
index 3f586d8..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.groovy
+++ /dev/null
@@ -1,60 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.CodeVisitorSupport
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.MethodCallExpression
-import org.codehaus.groovy.ast.expr.StaticMethodCallExpression
-
-/**
- * Collect all recursive calls within method
- */
-@CompileStatic
-class CollectRecursiveCalls extends CodeVisitorSupport {
- MethodNode method
- List<Expression> recursiveCalls = []
-
- void visitMethodCallExpression(MethodCallExpression call) {
- if (isRecursive(call)) {
- recursiveCalls << call
- }
- super.visitMethodCallExpression(call)
- }
-
- void visitStaticMethodCallExpression(StaticMethodCallExpression call) {
- if (isRecursive(call)) {
- recursiveCalls << call
- }
- super.visitStaticMethodCallExpression(call)
- }
-
- private boolean isRecursive(call) {
- new RecursivenessTester().isRecursive(method: method, call: call)
- }
-
- synchronized List<Expression> collect(MethodNode method) {
- recursiveCalls.clear()
- this.method = method
- this.method.code.visit(this)
- recursiveCalls
- }
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.groovy
deleted file mode 100644
index e8799c3..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.groovy
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.CodeVisitorSupport
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.expr.MethodCallExpression
-import org.codehaus.groovy.ast.expr.StaticMethodCallExpression
-
-/**
- * Check if there are any recursive calls in a method
- */
-@CompileStatic
-class HasRecursiveCalls extends CodeVisitorSupport {
- MethodNode method
- boolean hasRecursiveCalls = false
-
- void visitMethodCallExpression(MethodCallExpression call) {
- if (isRecursive(call)) {
- hasRecursiveCalls = true
- } else {
- super.visitMethodCallExpression(call)
- }
- }
-
- void visitStaticMethodCallExpression(StaticMethodCallExpression call) {
- if (isRecursive(call)) {
- hasRecursiveCalls = true
- } else {
- super.visitStaticMethodCallExpression(call)
- }
- }
-
- private boolean isRecursive(call) {
- new RecursivenessTester().isRecursive(method: method, call: call)
- }
-
- synchronized boolean test(MethodNode method) {
- hasRecursiveCalls = false
- this.method = method
- this.method.code.visit(this)
- hasRecursiveCalls
- }
-}
\ No newline at end of file
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.groovy
deleted file mode 100644
index d622dc5..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.groovy
+++ /dev/null
@@ -1,83 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ClassHelper
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.VariableScope
-import org.codehaus.groovy.ast.stmt.BlockStatement
-import org.codehaus.groovy.ast.stmt.ContinueStatement
-import org.codehaus.groovy.ast.stmt.EmptyStatement
-import org.codehaus.groovy.ast.stmt.Statement
-import org.codehaus.groovy.ast.stmt.TryCatchStatement
-import org.codehaus.groovy.ast.stmt.WhileStatement
-
-import static org.codehaus.groovy.ast.tools.GeneralUtils.block
-import static org.codehaus.groovy.ast.tools.GeneralUtils.boolX
-import static org.codehaus.groovy.ast.tools.GeneralUtils.catchS
-import static org.codehaus.groovy.ast.tools.GeneralUtils.constX
-import static org.codehaus.groovy.ast.tools.GeneralUtils.param
-import static org.codehaus.groovy.ast.tools.GeneralUtils.tryCatchS
-
-/**
- * Wrap the body of a method in a while loop, nested in a try-catch.
- * This is the first step in making a tail recursive method iterative.
- *
- * There are two ways to invoke the next iteration step:
- * <ol>
- * <li>"continue _RECUR_HERE_" is used by recursive calls outside of closures</li>
- * <li>"throw LOOP_EXCEPTION" is used by recursive calls within closures b/c you cannot invoke "continue" from there</li>
- * </ol>
- */
-@CompileStatic
-class InWhileLoopWrapper {
- static final String LOOP_LABEL = '_RECUR_HERE_'
- static final GotoRecurHereException LOOP_EXCEPTION = new GotoRecurHereException()
-
- void wrap(MethodNode method) {
- BlockStatement oldBody = method.code as BlockStatement
- TryCatchStatement tryCatchStatement = tryCatchS(
- oldBody,
- EmptyStatement.INSTANCE,
- catchS(
- param(ClassHelper.make(GotoRecurHereException), 'ignore'),
- new ContinueStatement(InWhileLoopWrapper.LOOP_LABEL)
- ))
-
- WhileStatement whileLoop = new WhileStatement(
- boolX(constX(true)),
- block(new VariableScope(method.variableScope), tryCatchStatement)
- )
- List<Statement> whileLoopStatements = ((BlockStatement) whileLoop.loopBlock).statements
- if (whileLoopStatements.size() > 0)
- whileLoopStatements[0].statementLabel = LOOP_LABEL
- BlockStatement newBody = block(new VariableScope(method.variableScope))
- newBody.addStatement(whileLoop)
- method.code = newBody
- }
-}
-
-/**
- * Exception will be thrown by recursive calls in closures and caught in while loop to continue to LOOP_LABEL
- */
-@CompileStatic
-class GotoRecurHereException extends Exception {
- private static final long serialVersionUID = -193137033604506378L
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/RecursivenessTester.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/RecursivenessTester.groovy
deleted file mode 100644
index 15e24e4..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/RecursivenessTester.groovy
+++ /dev/null
@@ -1,101 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import org.codehaus.groovy.ast.ClassHelper
-import org.codehaus.groovy.ast.ClassNode
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.expr.ConstantExpression
-import org.codehaus.groovy.ast.expr.MethodCallExpression
-import org.codehaus.groovy.ast.expr.StaticMethodCallExpression
-import org.codehaus.groovy.ast.expr.VariableExpression
-
-/**
- * Test if a method call is recursive if called within a given method node.
- * Handles static calls as well.
- *
- * Currently known simplifications:
- * <ul>
- * <li>Does not check for method overloading or overridden methods</li>
- * <li>Does not check for matching return types; even void and any object type are considered to be compatible</li>
- * <li>Argument type matching could be more specific in case of static compilation</li>
- * <li>Method names via a GString are never considered to be recursive</li>
- * </ul>
- */
-class RecursivenessTester {
- boolean isRecursive(params) {
- assert params.method.class == MethodNode
- assert params.call.class == MethodCallExpression || StaticMethodCallExpression
-
- isRecursive(params.method, params.call)
- }
-
- @SuppressWarnings('Instanceof')
- boolean isRecursive(MethodNode method, MethodCallExpression call) {
- if (!isCallToThis(call))
- return false
- // Could be a GStringExpression
- if (! (call.method instanceof ConstantExpression))
- return false
- if (call.method.value != method.name)
- return false
- methodParamsMatchCallArgs(method, call)
- }
-
- boolean isRecursive(MethodNode method, StaticMethodCallExpression call) {
- if (!method.isStatic())
- return false
- if (method.declaringClass != call.ownerType)
- return false
- if (call.method != method.name)
- return false
- methodParamsMatchCallArgs(method, call)
- }
-
- @SuppressWarnings('Instanceof')
- private boolean isCallToThis(MethodCallExpression call) {
- if (call.objectExpression == null)
- return call.isImplicitThis()
- if (! (call.objectExpression instanceof VariableExpression)) {
- return false
- }
- call.objectExpression.isThisExpression()
- }
-
- private boolean methodParamsMatchCallArgs(method, call) {
- if (method.parameters.size() != call.arguments.expressions.size())
- return false
- def classNodePairs = [method.parameters*.type, call.arguments*.type].transpose()
- classNodePairs.every { ClassNode paramType, ClassNode argType ->
- areTypesCallCompatible(argType, paramType)
- }
- }
-
- /**
- * Parameter type and calling argument type can both be derived from the other since typing information is
- * optional in Groovy.
- * Since int is not derived from Integer (nor the other way around) we compare the boxed types
- */
- private areTypesCallCompatible(ClassNode argType, ClassNode paramType) {
- ClassNode boxedArg = ClassHelper.getWrapper(argType)
- ClassNode boxedParam = ClassHelper.getWrapper(paramType)
- boxedArg.isDerivedFrom(boxedParam) || boxedParam.isDerivedFrom(boxedArg)
- }
-
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.groovy
deleted file mode 100644
index 5ebac87..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.groovy
+++ /dev/null
@@ -1,147 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ClassNode
-import org.codehaus.groovy.ast.expr.BinaryExpression
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.MethodCallExpression
-import org.codehaus.groovy.ast.expr.StaticMethodCallExpression
-import org.codehaus.groovy.ast.expr.TupleExpression
-import org.codehaus.groovy.ast.expr.VariableExpression
-import org.codehaus.groovy.ast.stmt.BlockStatement
-import org.codehaus.groovy.ast.stmt.ExpressionStatement
-import org.codehaus.groovy.ast.stmt.ReturnStatement
-import org.codehaus.groovy.ast.stmt.Statement
-
-import static org.codehaus.groovy.ast.tools.GeneralUtils.assignS
-import static org.codehaus.groovy.ast.tools.GeneralUtils.varX
-
-/**
- * Translates all return statements into an invocation of the next iteration. This can be either
- * - "continue LOOP_LABEL": Outside closures
- * - "throw LOOP_EXCEPTION": Inside closures
- *
- * Moreover, before adding the recur statement the iteration parameters (originally the method args)
- * are set to their new value. To prevent variable aliasing parameters will be copied into temp vars
- * before they are changes so that their current iteration value can be used when setting other params.
- *
- * There's probably place for optimizing the amount of variable copying being done, e.g.
- * parameters that are only handed through must not be copied at all.
- */
-@CompileStatic
-class ReturnStatementToIterationConverter {
-
- Statement recurStatement = AstHelper.recurStatement()
-
- Statement convert(ReturnStatement statement, Map<Integer, Map> positionMapping) {
- Expression recursiveCall = statement.expression
- if (!isAMethodCalls(recursiveCall))
- return statement
-
- Map<String, Map> tempMapping = [:]
- Map tempDeclarations = [:]
- List<ExpressionStatement> argAssignments = []
-
- BlockStatement result = new BlockStatement()
- result.copyStatementLabels(statement)
-
- /* Create temp declarations for all method arguments.
- * Add the declarations and var mapping to tempMapping and tempDeclarations for further reference.
- */
- getArguments(recursiveCall).eachWithIndex { Expression expression, int index ->
- ExpressionStatement tempDeclaration = createTempDeclaration(index, positionMapping, tempMapping, tempDeclarations)
- result.addStatement(tempDeclaration)
- }
-
- /*
- * Assign the iteration variables their new value before recuring
- */
- getArguments(recursiveCall).eachWithIndex { Expression expression, int index ->
- ExpressionStatement argAssignment = createAssignmentToIterationVariable(expression, index, positionMapping)
- argAssignments.add(argAssignment)
- result.addStatement(argAssignment)
- }
-
- Set<String> unusedTemps = replaceAllArgUsages(argAssignments, tempMapping)
- for (String temp : unusedTemps) {
- result.statements.remove(tempDeclarations[temp])
- }
- result.addStatement(recurStatement)
-
- result
- }
-
- private ExpressionStatement createAssignmentToIterationVariable(Expression expression, int index, Map<Integer, Map> positionMapping) {
- String argName = positionMapping[index]['name']
- ClassNode argAndTempType = positionMapping[index]['type'] as ClassNode
- ExpressionStatement argAssignment = (ExpressionStatement) assignS(varX(argName, argAndTempType), expression)
- argAssignment
- }
-
- private ExpressionStatement createTempDeclaration(int index, Map<Integer, Map> positionMapping, Map<String, Map> tempMapping, Map tempDeclarations) {
- String argName = positionMapping[index]['name']
- String tempName = "_${argName}_"
- ClassNode argAndTempType = positionMapping[index]['type'] as ClassNode
- ExpressionStatement tempDeclaration = AstHelper.createVariableAlias(tempName, argAndTempType, argName)
- tempMapping[argName] = [name: tempName, type: argAndTempType]
- tempDeclarations[tempName] = tempDeclaration
- tempDeclaration
- }
-
- @SuppressWarnings('Instanceof')
- private List<Expression> getArguments(Expression recursiveCall) {
- if (recursiveCall instanceof MethodCallExpression)
- return ((TupleExpression) ((MethodCallExpression) recursiveCall).arguments).expressions
- if (recursiveCall instanceof StaticMethodCallExpression)
- return ((TupleExpression) ((StaticMethodCallExpression) recursiveCall).arguments).expressions
- }
-
- private boolean isAMethodCalls(Expression expression) {
- expression.class in [MethodCallExpression, StaticMethodCallExpression]
- }
-
- private Set<String> replaceAllArgUsages(List<ExpressionStatement> iterationVariablesAssignmentNodes, Map<String, Map> tempMapping) {
- Set<String> unusedTempNames = tempMapping.values().collect { Map nameAndType -> (String) nameAndType['name'] } as Set<String>
- VariableReplacedListener tracker = new UsedVariableTracker()
- for (ExpressionStatement statement : iterationVariablesAssignmentNodes) {
- replaceArgUsageByTempUsage((BinaryExpression) statement.expression, tempMapping, tracker)
- }
- unusedTempNames = unusedTempNames - tracker.usedVariableNames
- unusedTempNames
- }
-
- private void replaceArgUsageByTempUsage(BinaryExpression binary, Map tempMapping, UsedVariableTracker tracker) {
- VariableAccessReplacer replacer = new VariableAccessReplacer(nameAndTypeMapping: tempMapping, listener: tracker)
- // Replacement must only happen in binary.rightExpression. It's a hack in VariableExpressionReplacer which takes care of that.
- replacer.replaceIn(binary)
- }
-}
-
-@CompileStatic
-class UsedVariableTracker implements VariableReplacedListener {
-
- final Set<String> usedVariableNames = [] as Set
-
- @Override
- void variableReplaced(VariableExpression oldVar, VariableExpression newVar) {
- usedVariableNames.add(newVar.name)
- }
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/StatementReplacer.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/StatementReplacer.groovy
deleted file mode 100644
index 8c7a55a..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/StatementReplacer.groovy
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ASTNode
-import org.codehaus.groovy.ast.CodeVisitorSupport
-import org.codehaus.groovy.ast.expr.ClosureExpression
-import org.codehaus.groovy.ast.stmt.BlockStatement
-import org.codehaus.groovy.ast.stmt.DoWhileStatement
-import org.codehaus.groovy.ast.stmt.ForStatement
-import org.codehaus.groovy.ast.stmt.IfStatement
-import org.codehaus.groovy.ast.stmt.Statement
-import org.codehaus.groovy.ast.stmt.WhileStatement
-
-/**
- * Tool for replacing Statement objects in an AST by other Statement instances.
- *
- * Within @TailRecursive it is used to swap ReturnStatements with looping back to RECUR label
- */
-@CompileStatic
-class StatementReplacer extends CodeVisitorSupport {
-
- Closure<Boolean> when = { Statement node -> false }
- Closure<Statement> replaceWith = { Statement statement -> statement }
- int closureLevel = 0
-
- void replaceIn(ASTNode root) {
- root.visit(this)
- }
-
- void visitClosureExpression(ClosureExpression expression) {
- closureLevel++
- try {
- super.visitClosureExpression(expression)
- } finally {
- closureLevel--
- }
- }
-
- void visitBlockStatement(BlockStatement block) {
- List<Statement> copyOfStatements = new ArrayList<Statement>(block.statements)
- copyOfStatements.eachWithIndex { Statement statement, int index ->
- replaceIfNecessary(statement) { Statement node -> block.statements[index] = node }
- }
- super.visitBlockStatement(block)
- }
-
- void visitIfElse(IfStatement ifElse) {
- replaceIfNecessary(ifElse.ifBlock) { Statement s -> ifElse.ifBlock = s }
- replaceIfNecessary(ifElse.elseBlock) { Statement s -> ifElse.elseBlock = s }
- super.visitIfElse(ifElse)
- }
-
- void visitForLoop(ForStatement forLoop) {
- replaceIfNecessary(forLoop.loopBlock) { Statement s -> forLoop.loopBlock = s }
- super.visitForLoop(forLoop)
- }
-
- void visitWhileLoop(WhileStatement loop) {
- replaceIfNecessary(loop.loopBlock) { Statement s -> loop.loopBlock = s }
- super.visitWhileLoop(loop)
- }
-
- void visitDoWhileLoop(DoWhileStatement loop) {
- replaceIfNecessary(loop.loopBlock) { Statement s -> loop.loopBlock = s }
- super.visitDoWhileLoop(loop)
- }
-
-
- private void replaceIfNecessary(Statement nodeToCheck, Closure replacementCode) {
- if (conditionFulfilled(nodeToCheck)) {
- ASTNode replacement = replaceWith(nodeToCheck)
- replacement.sourcePosition = nodeToCheck
- replacement.copyNodeMetaData(nodeToCheck)
- replacementCode(replacement)
- }
- }
-
- private boolean conditionFulfilled(ASTNode nodeToCheck) {
- if (when.maximumNumberOfParameters < 2)
- return when(nodeToCheck)
- when(nodeToCheck, isInClosure())
- }
-
- private boolean isInClosure() {
- closureLevel > 0
- }
-
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.groovy
deleted file mode 100644
index 0b71062..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.groovy
+++ /dev/null
@@ -1,263 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import groovy.transform.Memoized
-import groovy.transform.TailRecursive
-import org.codehaus.groovy.ast.ASTNode
-import org.codehaus.groovy.ast.AnnotationNode
-import org.codehaus.groovy.ast.ClassHelper
-import org.codehaus.groovy.ast.ClassNode
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.Parameter
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.MethodCallExpression
-import org.codehaus.groovy.ast.expr.StaticMethodCallExpression
-import org.codehaus.groovy.ast.expr.TernaryExpression
-import org.codehaus.groovy.ast.expr.VariableExpression
-import org.codehaus.groovy.ast.stmt.BlockStatement
-import org.codehaus.groovy.ast.stmt.ReturnStatement
-import org.codehaus.groovy.ast.stmt.Statement
-import org.codehaus.groovy.classgen.ReturnAdder
-import org.codehaus.groovy.classgen.VariableScopeVisitor
-import org.codehaus.groovy.control.CompilePhase
-import org.codehaus.groovy.control.SourceUnit
-import org.codehaus.groovy.transform.AbstractASTTransformation
-import org.codehaus.groovy.transform.GroovyASTTransformation
-
-/**
- * Handles generation of code for the @TailRecursive annotation.
- *
- * It's doing its work in the earliest possible compile phase
- */
-@CompileStatic
-@GroovyASTTransformation(phase = CompilePhase.SEMANTIC_ANALYSIS)
-class TailRecursiveASTTransformation extends AbstractASTTransformation {
-
- private static final Class MY_CLASS = TailRecursive
- private static final ClassNode MY_TYPE = new ClassNode(MY_CLASS)
- static final String MY_TYPE_NAME = '@' + MY_TYPE.nameWithoutPackage
- private final HasRecursiveCalls hasRecursiveCalls = new HasRecursiveCalls()
- private final TernaryToIfStatementConverter ternaryToIfStatement = new TernaryToIfStatementConverter()
-
-
- @Override
- void visit(ASTNode[] nodes, SourceUnit source) {
- init(nodes, source)
-
- MethodNode method = nodes[1] as MethodNode
-
- if (method.isAbstract()) {
- addError("Annotation $MY_TYPE_NAME cannot be used for abstract methods.", method)
- return
- }
-
- if (hasAnnotation(method, ClassHelper.make(Memoized))) {
- ClassNode memoizedClassNode = ClassHelper.make(Memoized)
- for (AnnotationNode annotationNode in method.annotations) {
- if (annotationNode.classNode == MY_TYPE)
- break
- if (annotationNode.classNode == memoizedClassNode) {
- addError("Annotation $MY_TYPE_NAME must be placed before annotation @Memoized.", annotationNode)
- return
- }
- }
- }
-
- if (!hasRecursiveMethodCalls(method)) {
- AnnotationNode annotationNode = method.getAnnotations(ClassHelper.make(TailRecursive))[0]
- addError("No recursive calls detected. You must remove annotation ${MY_TYPE_NAME}.", annotationNode)
- return
- }
-
- transformToIteration(method, source)
- ensureAllRecursiveCallsHaveBeenTransformed(method)
- }
-
- private boolean hasAnnotation(MethodNode methodNode, ClassNode annotation) {
- List annots = methodNode.getAnnotations(annotation)
- annots != null && annots.size() > 0
- }
-
-
- private void transformToIteration(MethodNode method, SourceUnit source) {
- if (method.isVoidMethod()) {
- transformVoidMethodToIteration(method)
- } else {
- transformNonVoidMethodToIteration(method, source)
- }
- }
-
- private void transformVoidMethodToIteration(MethodNode method) {
- addError('Void methods are not supported by @TailRecursive yet.', method)
- }
-
- private void transformNonVoidMethodToIteration(MethodNode method, SourceUnit source) {
- addMissingDefaultReturnStatement(method)
- replaceReturnsWithTernariesToIfStatements(method)
- wrapMethodBodyWithWhileLoop(method)
-
- Map<String, Map> nameAndTypeMapping = name2VariableMappingFor(method)
- replaceAllAccessToParams(method, nameAndTypeMapping)
- addLocalVariablesForAllParameters(method, nameAndTypeMapping) //must happen after replacing access to params
-
- Map<Integer, Map> positionMapping = position2VariableMappingFor(method)
- replaceAllRecursiveReturnsWithIteration(method, positionMapping)
- repairVariableScopes(source, method)
- }
-
- private void repairVariableScopes(SourceUnit source, MethodNode method) {
- new VariableScopeVisitor(source).visitClass(method.declaringClass)
- }
-
- @SuppressWarnings('Instanceof')
- private void replaceReturnsWithTernariesToIfStatements(MethodNode method) {
- Closure<Boolean> whenReturnWithTernary = { ASTNode node ->
- if (!(node instanceof ReturnStatement)) {
- return false
- }
- ((ReturnStatement) node).expression instanceof TernaryExpression
- }
- Closure<Statement> replaceWithIfStatement = { ReturnStatement statement ->
- ternaryToIfStatement.convert(statement)
- }
- StatementReplacer replacer = new StatementReplacer(when: whenReturnWithTernary, replaceWith: replaceWithIfStatement)
- replacer.replaceIn(method.code)
-
- }
-
- private void addLocalVariablesForAllParameters(MethodNode method, Map<String, Map> nameAndTypeMapping) {
- BlockStatement code = method.code as BlockStatement
- nameAndTypeMapping.each { String paramName, Map localNameAndType ->
- code.statements.add(0, AstHelper.createVariableDefinition(
- (String) localNameAndType['name'],
- (ClassNode) localNameAndType['type'],
- new VariableExpression(paramName, (ClassNode) localNameAndType['type'])
- ))
- }
- }
-
- private void replaceAllAccessToParams(MethodNode method, Map<String, Map> nameAndTypeMapping) {
- new VariableAccessReplacer(nameAndTypeMapping: nameAndTypeMapping).replaceIn(method.code)
- }
-
- // Public b/c there are tests for this method
- Map<String, Map> name2VariableMappingFor(MethodNode method) {
- Map<String, Map> nameAndTypeMapping = [:]
- method.parameters.each { Parameter param ->
- String paramName = param.name
- ClassNode paramType = param.type as ClassNode
- String iterationVariableName = iterationVariableName(paramName)
- nameAndTypeMapping[paramName] = [name: iterationVariableName, type: paramType]
- }
- nameAndTypeMapping
- }
-
- // Public b/c there are tests for this method
- Map<Integer, Map> position2VariableMappingFor(MethodNode method) {
- Map<Integer, Map> positionMapping = [:]
- method.parameters.eachWithIndex { Parameter param, int index ->
- String paramName = param.name
- ClassNode paramType = param.type as ClassNode
- String iterationVariableName = this.iterationVariableName(paramName)
- positionMapping[index] = [name: iterationVariableName, type: paramType]
- }
- positionMapping
- }
-
- private String iterationVariableName(String paramName) {
- '_' + paramName + '_'
- }
-
- private void replaceAllRecursiveReturnsWithIteration(MethodNode method, Map positionMapping) {
- replaceRecursiveReturnsOutsideClosures(method, positionMapping)
- replaceRecursiveReturnsInsideClosures(method, positionMapping)
- }
-
- @SuppressWarnings('Instanceof')
- private void replaceRecursiveReturnsOutsideClosures(MethodNode method, Map<Integer, Map> positionMapping) {
- Closure<Boolean> whenRecursiveReturn = { Statement statement, boolean inClosure ->
- if (inClosure)
- return false
- if (!(statement instanceof ReturnStatement)) {
- return false
- }
- Expression inner = ((ReturnStatement) statement).expression
- if (!(inner instanceof MethodCallExpression) && !(inner instanceof StaticMethodCallExpression)) {
- return false
- }
- isRecursiveIn(inner, method)
- }
- Closure<Statement> replaceWithContinueBlock = { ReturnStatement statement ->
- new ReturnStatementToIterationConverter().convert(statement, positionMapping)
- }
- def replacer = new StatementReplacer(when: whenRecursiveReturn, replaceWith: replaceWithContinueBlock)
- replacer.replaceIn(method.code)
- }
-
- @SuppressWarnings('Instanceof')
- private void replaceRecursiveReturnsInsideClosures(MethodNode method, Map<Integer, Map> positionMapping) {
- Closure<Boolean> whenRecursiveReturn = { Statement statement, boolean inClosure ->
- if (!inClosure)
- return false
- if (!(statement instanceof ReturnStatement)) {
- return false
- }
- Expression inner = ((ReturnStatement) statement).expression
- if (!(inner instanceof MethodCallExpression) && !(inner instanceof StaticMethodCallExpression)) {
- return false
- }
- isRecursiveIn(inner, method)
- }
- Closure<Statement> replaceWithThrowLoopException = { ReturnStatement statement ->
- new ReturnStatementToIterationConverter(recurStatement: AstHelper.recurByThrowStatement()).convert(statement, positionMapping)
- }
- StatementReplacer replacer = new StatementReplacer(when: whenRecursiveReturn, replaceWith: replaceWithThrowLoopException)
- replacer.replaceIn(method.code)
- }
-
- private void wrapMethodBodyWithWhileLoop(MethodNode method) {
- new InWhileLoopWrapper().wrap(method)
- }
-
- private void addMissingDefaultReturnStatement(MethodNode method) {
- new ReturnAdder().visitMethod(method)
- new ReturnAdderForClosures().visitMethod(method)
- }
-
- private void ensureAllRecursiveCallsHaveBeenTransformed(MethodNode method) {
- List<Expression> remainingRecursiveCalls = new CollectRecursiveCalls().collect(method)
- for (Expression expression : remainingRecursiveCalls) {
- addError("Recursive call could not be transformed by @TailRecursive. Maybe it's not a tail call.", expression)
- }
- }
-
- private boolean hasRecursiveMethodCalls(MethodNode method) {
- hasRecursiveCalls.test(method)
- }
-
- @SuppressWarnings('Instanceof')
- private boolean isRecursiveIn(Expression methodCall, MethodNode method) {
- if (methodCall instanceof MethodCallExpression)
- return new RecursivenessTester().isRecursive(method, (MethodCallExpression) methodCall)
- if (methodCall instanceof StaticMethodCallExpression)
- return new RecursivenessTester().isRecursive(method, (StaticMethodCallExpression) methodCall)
- }
-}
\ No newline at end of file
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.groovy
deleted file mode 100644
index b53b5bd..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.groovy
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ASTNode
-import org.codehaus.groovy.ast.expr.VariableExpression
-
-/**
- * Replace all access to variables and args by new variables.
- * The variable names to replace as well as their replacement name and type have to be configured
- * in nameAndTypeMapping before calling replaceIn().
- *
- * The VariableReplacedListener can be set if clients want to react to variable replacement.
- */
-@CompileStatic
-class VariableAccessReplacer {
-
- /**
- * Nested map of variable accesses to replace
- * e.g.: [
- * 'varToReplace': [name: 'newVar', type: TypeOfVar],
- * 'varToReplace2': [name: 'newVar2', type: TypeOfVar2],
- * ]
- */
- Map<String, Map> nameAndTypeMapping = [:]
-
- VariableReplacedListener listener = VariableReplacedListener.NULL
-
- void replaceIn(ASTNode root) {
- Closure<Boolean> whenParam = { VariableExpression expr ->
- return nameAndTypeMapping.containsKey(expr.name)
- }
- Closure<VariableExpression> replaceWithLocalVariable = { VariableExpression expr ->
- def newVar = AstHelper.createVariableReference(nameAndTypeMapping[expr.name])
- listener.variableReplaced(expr, newVar)
- return newVar
- }
- new VariableExpressionReplacer(when: whenParam, replaceWith: replaceWithLocalVariable).replaceIn(root)
- }
-}
-
-@CompileStatic
-interface VariableReplacedListener {
- void variableReplaced(VariableExpression oldVar, VariableExpression newVar)
-
- public static VariableReplacedListener NULL = new VariableReplacedListener() {
- @Override
- void variableReplaced(VariableExpression oldVar, VariableExpression newVar) {
- //do nothing
- }
- }
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.groovy
deleted file mode 100644
index 9dbb801..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.groovy
+++ /dev/null
@@ -1,163 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.AutoFinal
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.ASTNode
-import org.codehaus.groovy.ast.CodeVisitorSupport
-import org.codehaus.groovy.ast.expr.BinaryExpression
-import org.codehaus.groovy.ast.expr.BooleanExpression
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.ExpressionTransformer
-import org.codehaus.groovy.ast.expr.VariableExpression
-import org.codehaus.groovy.ast.stmt.AssertStatement
-import org.codehaus.groovy.ast.stmt.CaseStatement
-import org.codehaus.groovy.ast.stmt.DoWhileStatement
-import org.codehaus.groovy.ast.stmt.ExpressionStatement
-import org.codehaus.groovy.ast.stmt.ForStatement
-import org.codehaus.groovy.ast.stmt.IfStatement
-import org.codehaus.groovy.ast.stmt.ReturnStatement
-import org.codehaus.groovy.ast.stmt.SwitchStatement
-import org.codehaus.groovy.ast.stmt.SynchronizedStatement
-import org.codehaus.groovy.ast.stmt.ThrowStatement
-import org.codehaus.groovy.ast.stmt.WhileStatement
-import org.codehaus.groovy.ast.tools.GeneralUtils
-
-import java.lang.reflect.Method
-
-/**
- * Tool for replacing VariableExpression instances in an AST by other VariableExpression instances.
- * Regardless of a real change taking place in nested expressions, all considered expression (trees) will be replaced.
- * This could be optimized to accelerate compilation.
- *
- * Within @TailRecursive it is used
- * - to swap the access of method args with the access to iteration variables
- * - to swap the access of iteration variables with the access of temp vars
- */
-@AutoFinal @CompileStatic
-class VariableExpressionReplacer extends CodeVisitorSupport {
-
- Closure<Boolean> when = { VariableExpression node -> false }
- Closure<VariableExpression> replaceWith = { VariableExpression variableExpression -> variableExpression }
-
- private ExpressionTransformer transformer
-
- synchronized void replaceIn(ASTNode root) {
- transformer = new VariableExpressionTransformer(when: when, replaceWith: replaceWith)
- root.visit(this)
- }
-
- void visitReturnStatement(ReturnStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitReturnStatement(statement)
- }
-
- void visitIfElse(IfStatement ifElse) {
- replaceExpressionPropertyWhenNecessary(ifElse, 'booleanExpression', BooleanExpression)
- super.visitIfElse(ifElse)
- }
-
- void visitForLoop(ForStatement forLoop) {
- replaceExpressionPropertyWhenNecessary(forLoop, 'collectionExpression')
- super.visitForLoop(forLoop)
- }
-
- /**
- * It's the only Expression type in which replacing is considered.
- * That's an abuse of the class, but I couldn't think of a better way.
- */
- void visitBinaryExpression(BinaryExpression expression) {
- //A hack: Only replace right expression b/c ReturnStatementToIterationConverter needs it that way :-/
- replaceExpressionPropertyWhenNecessary(expression, 'rightExpression')
- expression.rightExpression.visit(this)
- super.visitBinaryExpression(expression)
- }
-
- void visitWhileLoop(WhileStatement loop) {
- replaceExpressionPropertyWhenNecessary(loop, 'booleanExpression', BooleanExpression)
- super.visitWhileLoop(loop)
- }
-
- void visitDoWhileLoop(DoWhileStatement loop) {
- replaceExpressionPropertyWhenNecessary(loop, 'booleanExpression', BooleanExpression)
- super.visitDoWhileLoop(loop)
- }
-
- void visitSwitch(SwitchStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitSwitch(statement)
- }
-
- void visitCaseStatement(CaseStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitCaseStatement(statement)
- }
-
- void visitExpressionStatement(ExpressionStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitExpressionStatement(statement)
- }
-
- void visitThrowStatement(ThrowStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitThrowStatement(statement)
- }
-
- void visitAssertStatement(AssertStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement, 'booleanExpression', BooleanExpression)
- replaceExpressionPropertyWhenNecessary(statement, 'messageExpression')
- super.visitAssertStatement(statement)
- }
-
- void visitSynchronizedStatement(SynchronizedStatement statement) {
- replaceExpressionPropertyWhenNecessary(statement)
- super.visitSynchronizedStatement(statement)
- }
-
- private void replaceExpressionPropertyWhenNecessary(ASTNode node, String propName = 'expression', Class propClass = Expression) {
- Expression expr = getExpression(node, propName)
-
- if (expr instanceof VariableExpression) {
- if (when(expr)) {
- VariableExpression newExpr = replaceWith(expr)
- replaceExpression(node, propName, propClass, expr, newExpr)
- }
- } else {
- Expression newExpr = transformer.transform(expr)
- replaceExpression(node, propName, propClass, expr, newExpr)
- }
- }
-
- private void replaceExpression(ASTNode node, String propName, Class propClass, Expression oldExpr, Expression newExpr) {
- //Use reflection to enable CompileStatic
- String setterName = GeneralUtils.getSetterName(propName)
- Method setExpressionMethod = node.class.getMethod(setterName, propClass)
- newExpr.copyNodeMetaData(oldExpr)
- newExpr.setSourcePosition(oldExpr)
- setExpressionMethod.invoke(node, newExpr)
- }
-
- private Expression getExpression(ASTNode node, String propName) {
- //Use reflection to enable CompileStatic
- String getterName = GeneralUtils.getGetterName(propName)
- Method getExpressionMethod = node.class.getMethod(getterName)
- getExpressionMethod.invoke(node) as Expression
- }
-}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.groovy b/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.groovy
deleted file mode 100644
index 9683bc9..0000000
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.groovy
+++ /dev/null
@@ -1,46 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.codehaus.groovy.transform.tailrec
-
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.expr.Expression
-import org.codehaus.groovy.ast.expr.ExpressionTransformer
-import org.codehaus.groovy.ast.expr.VariableExpression
-
-/**
- * An expression transformer used in the process of replacing the access to variables
- */
-@CompileStatic
-class VariableExpressionTransformer implements ExpressionTransformer {
-
- Closure<Boolean> when
- Closure<VariableExpression> replaceWith
-
- @Override
- @SuppressWarnings('Instanceof')
- Expression transform(Expression expr) {
- if ((expr instanceof VariableExpression) && when(expr)) {
- VariableExpression newExpr = replaceWith(expr)
- newExpr.sourcePosition = expr
- newExpr.copyNodeMetaData(expr)
- return newExpr
- }
- expr.transformExpression(this)
- }
-}
diff --git a/src/main/groovy/groovy/transform/TailRecursive.groovy b/src/main/java/groovy/transform/TailRecursive.java
similarity index 87%
rename from src/main/groovy/groovy/transform/TailRecursive.groovy
rename to src/main/java/groovy/transform/TailRecursive.java
index 066a6a8..e283991 100644
--- a/src/main/groovy/groovy/transform/TailRecursive.groovy
+++ b/src/main/java/groovy/transform/TailRecursive.java
@@ -16,14 +16,14 @@
* specific language governing permissions and limitations
* under the License.
*/
-package groovy.transform
+package groovy.transform;
-import org.codehaus.groovy.transform.GroovyASTTransformationClass
+import org.codehaus.groovy.transform.GroovyASTTransformationClass;
-import java.lang.annotation.ElementType
-import java.lang.annotation.Retention
-import java.lang.annotation.RetentionPolicy
-import java.lang.annotation.Target
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
/**
* Method annotation used to transform methods with tail recursive calls into iterative methods automagically
@@ -44,9 +44,9 @@ import java.lang.annotation.Target
* assert target.sumUp(100) == 5050
* assert target.sumUp(1000000) == 500000500000 //will blow the stack on most machines when used without {@code @TailRecursive}
* </pre>
- *
+ * <p>
* {@code @TailRecursive} is supposed to work in combination with {@code @CompileStatic}
- *
+ * <p>
* Known shortcomings:
* <ul>
* <li>Only non-void methods are currently being handled. Void methods will fail compilation.
@@ -58,7 +58,7 @@ import java.lang.annotation.Target
* <li>Non trivial continuation passing style examples do not work.
* <li>Probably many unrecognized edge cases.
* </ul>
- *
+ *
* <p>More examples:</p>
* <pre class="groovyTestCase">
* import groovy.transform.TailRecursive
@@ -68,7 +68,7 @@ import java.lang.annotation.Target
* if (list.size() == 0) {
* counter
* } else {
- * sizeOfList(list.tail(), counter + 1)
+ * sizeOfList(list.tail(), counter + 1)
* }
* }
*
@@ -80,7 +80,7 @@ import java.lang.annotation.Target
* @since 2.3
*/
@Retention(RetentionPolicy.SOURCE)
-@Target([ElementType.METHOD])
-@GroovyASTTransformationClass(['org.codehaus.groovy.transform.tailrec.TailRecursiveASTTransformation'])
-@interface TailRecursive {
+@Target({ElementType.METHOD})
+@GroovyASTTransformationClass({"org.codehaus.groovy.transform.tailrec.TailRecursiveASTTransformation"})
+public @interface TailRecursive {
}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/AstHelper.java b/src/main/java/org/codehaus/groovy/transform/tailrec/AstHelper.java
new file mode 100644
index 0000000..fc09f6c
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/AstHelper.java
@@ -0,0 +1,78 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.codehaus.groovy.ast.ClassNode;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+import org.codehaus.groovy.ast.stmt.ContinueStatement;
+import org.codehaus.groovy.ast.stmt.ExpressionStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
+
+import java.lang.reflect.Modifier;
+import java.util.Map;
+
+import static org.codehaus.groovy.ast.tools.GeneralUtils.classX;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.declS;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.localVarX;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.propX;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.throwS;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.varX;
+
+/**
+ * Helping to create a few standard AST constructs
+ */
+class AstHelper {
+ public static ExpressionStatement createVariableDefinition(String variableName, ClassNode variableType, Expression value) {
+ return createVariableDefinition(variableName, variableType, value, false);
+ }
+
+ public static ExpressionStatement createVariableDefinition(String variableName, ClassNode variableType, Expression value, boolean variableShouldBeFinal) {
+ VariableExpression newVariable = localVarX(variableName, variableType);
+ if (variableShouldBeFinal)
+ newVariable.setModifiers(Modifier.FINAL);
+ return (ExpressionStatement) declS(newVariable, value);
+ }
+
+ public static ExpressionStatement createVariableAlias(String aliasName, ClassNode variableType, String variableName) {
+ return createVariableDefinition(aliasName, variableType, varX(variableName, variableType));
+ }
+
+ public static VariableExpression createVariableReference(Map<String, ?> variableSpec) {
+ return varX((String) variableSpec.get("name"), (ClassNode) variableSpec.get("type"));
+ }
+
+ /**
+ * This statement should make the code jump to surrounding while loop's start label
+ * Does not work from within Closures
+ */
+ public static Statement recurStatement() {
+ //continue _RECUR_HERE_
+ return new ContinueStatement(InWhileLoopWrapper.LOOP_LABEL);
+ }
+
+ /**
+ * This statement will throw exception which will be caught and redirected to jump to surrounding while loop's start label
+ * Also works from within Closures but is a tiny bit slower
+ */
+ public static Statement recurByThrowStatement() {
+ // throw InWhileLoopWrapper.LOOP_EXCEPTION
+ return throwS(propX(classX(InWhileLoopWrapper.class), "LOOP_EXCEPTION"));
+ }
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.java b/src/main/java/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.java
new file mode 100644
index 0000000..e996a86
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/CollectRecursiveCalls.java
@@ -0,0 +1,64 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.apache.groovy.util.Maps;
+import org.codehaus.groovy.ast.CodeVisitorSupport;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.MethodCallExpression;
+import org.codehaus.groovy.ast.expr.StaticMethodCallExpression;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Collect all recursive calls within method
+ */
+class CollectRecursiveCalls extends CodeVisitorSupport {
+ private final List<Expression> recursiveCalls = new ArrayList<>();
+ private MethodNode method;
+
+ @Override
+ public void visitMethodCallExpression(MethodCallExpression call) {
+ if (isRecursive(call)) {
+ recursiveCalls.add(call);
+ }
+ super.visitMethodCallExpression(call);
+ }
+
+ @Override
+ public void visitStaticMethodCallExpression(StaticMethodCallExpression call) {
+ if (isRecursive(call)) {
+ recursiveCalls.add(call);
+ }
+ super.visitStaticMethodCallExpression(call);
+ }
+
+ public synchronized List<Expression> collect(MethodNode method) {
+ recursiveCalls.clear();
+ this.method = method;
+ this.method.getCode().visit(this);
+ return recursiveCalls;
+ }
+
+ private boolean isRecursive(Expression call) {
+ return new RecursivenessTester().isRecursive(Maps.of("method", method, "call", call));
+ }
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/GotoRecurHereException.java b/src/main/java/org/codehaus/groovy/transform/tailrec/GotoRecurHereException.java
new file mode 100644
index 0000000..54375ca
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/GotoRecurHereException.java
@@ -0,0 +1,26 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+/**
+ * Exception will be thrown by recursive calls in closures and caught in while loop to continue to LOOP_LABEL
+ */
+public class GotoRecurHereException extends Exception {
+ private static final long serialVersionUID = -193137033604506378L;
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.java b/src/main/java/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.java
new file mode 100644
index 0000000..9042ed2
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/HasRecursiveCalls.java
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.apache.groovy.util.Maps;
+import org.codehaus.groovy.ast.CodeVisitorSupport;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.MethodCallExpression;
+import org.codehaus.groovy.ast.expr.StaticMethodCallExpression;
+
+/**
+ * Check if there are any recursive calls in a method
+ */
+class HasRecursiveCalls extends CodeVisitorSupport {
+ private MethodNode method;
+ private boolean hasRecursiveCalls = false;
+
+ @Override
+ public void visitMethodCallExpression(MethodCallExpression call) {
+ if (isRecursive(call)) {
+ hasRecursiveCalls = true;
+ } else {
+ super.visitMethodCallExpression(call);
+ }
+ }
+
+ @Override
+ public void visitStaticMethodCallExpression(StaticMethodCallExpression call) {
+ if (isRecursive(call)) {
+ hasRecursiveCalls = true;
+ } else {
+ super.visitStaticMethodCallExpression(call);
+ }
+ }
+
+ public synchronized boolean test(MethodNode method) {
+ hasRecursiveCalls = false;
+ this.method = method;
+ this.method.getCode().visit(this);
+ return hasRecursiveCalls;
+ }
+
+ private boolean isRecursive(Expression call) {
+ return new RecursivenessTester().isRecursive(Maps.of("method", method, "call", call));
+ }
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.java b/src/main/java/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.java
new file mode 100644
index 0000000..a4d8f09
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/InWhileLoopWrapper.java
@@ -0,0 +1,60 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.codehaus.groovy.ast.ClassHelper;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.VariableScope;
+import org.codehaus.groovy.ast.stmt.BlockStatement;
+import org.codehaus.groovy.ast.stmt.ContinueStatement;
+import org.codehaus.groovy.ast.stmt.EmptyStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
+import org.codehaus.groovy.ast.stmt.TryCatchStatement;
+import org.codehaus.groovy.ast.stmt.WhileStatement;
+import org.codehaus.groovy.ast.tools.GeneralUtils;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.util.List;
+
+/**
+ * Wrap the body of a method in a while loop, nested in a try-catch.
+ * This is the first step in making a tail recursive method iterative.
+ * <p>
+ * There are two ways to invoke the next iteration step:
+ * <ol>
+ * <li>"continue _RECUR_HERE_" is used by recursive calls outside of closures</li>
+ * <li>"throw LOOP_EXCEPTION" is used by recursive calls within closures b/c you cannot invoke "continue" from there</li>
+ * </ol>
+ */
+class InWhileLoopWrapper {
+ public void wrap(MethodNode method) {
+ BlockStatement oldBody = DefaultGroovyMethods.asType(method.getCode(), BlockStatement.class);
+ TryCatchStatement tryCatchStatement = GeneralUtils.tryCatchS(oldBody, EmptyStatement.INSTANCE, GeneralUtils.catchS(GeneralUtils.param(ClassHelper.make(GotoRecurHereException.class), "ignore"), new ContinueStatement(InWhileLoopWrapper.LOOP_LABEL)));
+
+ WhileStatement whileLoop = new WhileStatement(GeneralUtils.boolX(GeneralUtils.constX(true)), GeneralUtils.block(new VariableScope(method.getVariableScope()), tryCatchStatement));
+ List<Statement> whileLoopStatements = ((BlockStatement) whileLoop.getLoopBlock()).getStatements();
+ if (whileLoopStatements.size() > 0) whileLoopStatements.get(0).setStatementLabel(LOOP_LABEL);
+ BlockStatement newBody = GeneralUtils.block(new VariableScope(method.getVariableScope()));
+ newBody.addStatement(whileLoop);
+ method.setCode(newBody);
+ }
+
+ public static final String LOOP_LABEL = "_RECUR_HERE_";
+ public static final GotoRecurHereException LOOP_EXCEPTION = new GotoRecurHereException();
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/RecursivenessTester.java b/src/main/java/org/codehaus/groovy/transform/tailrec/RecursivenessTester.java
new file mode 100644
index 0000000..d88d88e
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/RecursivenessTester.java
@@ -0,0 +1,121 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.codehaus.groovy.ast.ASTNode;
+import org.codehaus.groovy.ast.ClassHelper;
+import org.codehaus.groovy.ast.ClassNode;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.Parameter;
+import org.codehaus.groovy.ast.expr.ConstantExpression;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.MethodCallExpression;
+import org.codehaus.groovy.ast.expr.StaticMethodCallExpression;
+import org.codehaus.groovy.ast.expr.TupleExpression;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
+
+import static org.codehaus.groovy.runtime.DefaultGroovyMethods.transpose;
+
+/**
+ * Test if a method call is recursive if called within a given method node.
+ * Handles static calls as well.
+ * <p>
+ * Currently known simplifications:
+ * <ul>
+ * <li>Does not check for method overloading or overridden methods</li>
+ * <li>Does not check for matching return types; even void and any object type are considered to be compatible</li>
+ * <li>Argument type matching could be more specific in case of static compilation</li>
+ * <li>Method names via a GString are never considered to be recursive</li>
+ * </ul>
+ */
+class RecursivenessTester {
+ public boolean isRecursive(Map<String, ASTNode> params) {
+ ASTNode method = params.get("method");
+ assert MethodNode.class.equals(method.getClass());
+ ASTNode call = params.get("call");
+ Class<? extends ASTNode> callClass = call.getClass();
+ assert MethodCallExpression.class.equals(callClass) || StaticMethodCallExpression.class.equals(callClass);
+
+ if (callClass == MethodCallExpression.class) {
+ return isRecursive((MethodNode) method, (MethodCallExpression) call);
+ }
+ return isRecursive((MethodNode) method, (StaticMethodCallExpression) call);
+ }
+
+ @SuppressWarnings("Instanceof")
+ public boolean isRecursive(MethodNode method, MethodCallExpression call) {
+ if (!isCallToThis(call)) return false;
+ // Could be a GStringExpression
+ if (!(call.getMethod() instanceof ConstantExpression)) return false;
+ if (!((ConstantExpression) call.getMethod()).getValue().equals(method.getName())) return false;
+ return methodParamsMatchCallArgs(method, call);
+ }
+
+ public boolean isRecursive(MethodNode method, StaticMethodCallExpression call) {
+ if (!method.isStatic()) return false;
+ if (!method.getDeclaringClass().equals(call.getOwnerType())) return false;
+ if (!call.getMethod().equals(method.getName())) return false;
+ return methodParamsMatchCallArgs(method, call);
+ }
+
+ @SuppressWarnings("Instanceof")
+ private boolean isCallToThis(MethodCallExpression call) {
+ if (call.getObjectExpression() == null) return call.isImplicitThis();
+ if (!(call.getObjectExpression() instanceof VariableExpression)) {
+ return false;
+ }
+
+ return ((boolean) (DefaultGroovyMethods.invokeMethod(call.getObjectExpression(), "isThisExpression", new Object[0])));
+ }
+
+ private boolean methodParamsMatchCallArgs(MethodNode method, Expression call) {
+ TupleExpression arguments;
+ if (call instanceof MethodCallExpression) {
+ arguments = ((TupleExpression) ((MethodCallExpression) call).getArguments());
+ } else {
+ arguments = ((TupleExpression) ((StaticMethodCallExpression) call).getArguments());
+ }
+
+ if (method.getParameters().length != arguments.getExpressions().size())
+ return false;
+
+ List<List<ClassNode>> classNodePairs =
+ transpose(Arrays.asList(
+ Arrays.stream(method.getParameters()).map(Parameter::getType).collect(Collectors.toList()),
+ arguments.getExpressions().stream().map(Expression::getType).collect(Collectors.toList())));
+ return classNodePairs.stream().allMatch(t -> areTypesCallCompatible(t.get(0), t.get(1)));
+ }
+
+ /**
+ * Parameter type and calling argument type can both be derived from the other since typing information is
+ * optional in Groovy.
+ * Since int is not derived from Integer (nor the other way around) we compare the boxed types
+ */
+ private Boolean areTypesCallCompatible(ClassNode argType, ClassNode paramType) {
+ ClassNode boxedArg = ClassHelper.getWrapper(argType);
+ ClassNode boxedParam = ClassHelper.getWrapper(paramType);
+ return boxedArg.isDerivedFrom(boxedParam) || boxedParam.isDerivedFrom(boxedArg);
+ }
+}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.groovy b/src/main/java/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.java
similarity index 63%
rename from src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.groovy
rename to src/main/java/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.java
index 62c4aa9..2dc6196 100644
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.groovy
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/ReturnAdderForClosures.java
@@ -16,31 +16,30 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.codehaus.groovy.transform.tailrec
+package org.codehaus.groovy.transform.tailrec;
-import org.codehaus.groovy.ast.ClassHelper
-import org.codehaus.groovy.ast.ClassNode
-import org.codehaus.groovy.ast.CodeVisitorSupport
-import org.codehaus.groovy.ast.MethodNode
-import org.codehaus.groovy.ast.Parameter
-import org.codehaus.groovy.ast.expr.ClosureExpression
-import org.codehaus.groovy.classgen.ReturnAdder
+import org.codehaus.groovy.ast.ClassHelper;
+import org.codehaus.groovy.ast.ClassNode;
+import org.codehaus.groovy.ast.CodeVisitorSupport;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.Parameter;
+import org.codehaus.groovy.ast.expr.ClosureExpression;
+import org.codehaus.groovy.classgen.ReturnAdder;
/**
* Adds explicit return statements to implicit return points in a closure. This is necessary since
* tail-recursion is detected by having the recursive call within the return statement.
*/
class ReturnAdderForClosures extends CodeVisitorSupport {
-
- synchronized void visitMethod(MethodNode method) {
- method.code.visit(this)
+ public synchronized void visitMethod(MethodNode method) {
+ method.getCode().visit(this);
}
- void visitClosureExpression(ClosureExpression expression) {
+ @Override
+ public void visitClosureExpression(ClosureExpression expression) {
//Create a dummy method with the closure's code as the method's code. Then user ReturnAdder, which only works for methods.
- MethodNode node = new MethodNode('dummy', 0, ClassHelper.OBJECT_TYPE, Parameter.EMPTY_ARRAY, ClassNode.EMPTY_ARRAY, expression.code)
- new ReturnAdder().visitMethod(node)
- super.visitClosureExpression(expression)
+ MethodNode node = new MethodNode("dummy", 0, ClassHelper.OBJECT_TYPE, Parameter.EMPTY_ARRAY, ClassNode.EMPTY_ARRAY, expression.getCode());
+ new ReturnAdder().visitMethod(node);
+ super.visitClosureExpression(expression);
}
-
}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.java b/src/main/java/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.java
new file mode 100644
index 0000000..3440a1f
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/ReturnStatementToIterationConverter.java
@@ -0,0 +1,170 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import org.codehaus.groovy.ast.ClassNode;
+import org.codehaus.groovy.ast.expr.BinaryExpression;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.MethodCallExpression;
+import org.codehaus.groovy.ast.expr.StaticMethodCallExpression;
+import org.codehaus.groovy.ast.expr.TupleExpression;
+import org.codehaus.groovy.ast.stmt.BlockStatement;
+import org.codehaus.groovy.ast.stmt.ExpressionStatement;
+import org.codehaus.groovy.ast.stmt.ReturnStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
+import org.codehaus.groovy.ast.tools.GeneralUtils;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Translates all return statements into an invocation of the next iteration. This can be either
+ * - "continue LOOP_LABEL": Outside closures
+ * - "throw LOOP_EXCEPTION": Inside closures
+ * <p>
+ * Moreover, before adding the recur statement the iteration parameters (originally the method args)
+ * are set to their new value. To prevent variable aliasing parameters will be copied into temp vars
+ * before they are changes so that their current iteration value can be used when setting other params.
+ * <p>
+ * There's probably place for optimizing the amount of variable copying being done, e.g.
+ * parameters that are only handed through must not be copied at all.
+ */
+class ReturnStatementToIterationConverter {
+ public ReturnStatementToIterationConverter() {}
+
+ public ReturnStatementToIterationConverter(Statement recurStatement) {
+ this.recurStatement = recurStatement;
+ }
+
+ public Statement convert(ReturnStatement statement, final Map<Integer, Map> positionMapping) {
+ Expression recursiveCall = statement.getExpression();
+ if (!isAMethodCalls(recursiveCall)) return statement;
+
+ final Map<String, Map> tempMapping = new LinkedHashMap<String, Map>();
+ final Map<String, ExpressionStatement> tempDeclarations = new LinkedHashMap<>();
+ final List<ExpressionStatement> argAssignments = new ArrayList<ExpressionStatement>();
+
+ final BlockStatement result = new BlockStatement();
+ result.copyStatementLabels(statement);
+
+ /* Create temp declarations for all method arguments.
+ * Add the declarations and var mapping to tempMapping and tempDeclarations for further reference.
+ */
+ DefaultGroovyMethods.eachWithIndex(getArguments(recursiveCall), new Closure<Void>(this, this) {
+ public void doCall(Expression expression, int index) {
+ ExpressionStatement tempDeclaration = createTempDeclaration(index, positionMapping, tempMapping, tempDeclarations);
+ result.addStatement(tempDeclaration);
+ }
+
+ });
+
+ /*
+ * Assign the iteration variables their new value before recuring
+ */
+ DefaultGroovyMethods.eachWithIndex(getArguments(recursiveCall), new Closure<Void>(this, this) {
+ public void doCall(Expression expression, int index) {
+ ExpressionStatement argAssignment = createAssignmentToIterationVariable(expression, index, positionMapping);
+ argAssignments.add(argAssignment);
+ result.addStatement(argAssignment);
+ }
+
+ });
+
+ Set<String> unusedTemps = replaceAllArgUsages(argAssignments, tempMapping);
+ for (String temp : unusedTemps) {
+ result.getStatements().remove(tempDeclarations.get(temp));
+ }
+
+ result.addStatement(recurStatement);
+
+ return result;
+ }
+
+ private ExpressionStatement createAssignmentToIterationVariable(Expression expression, int index, Map<Integer, Map> positionMapping) {
+ String argName = (String) positionMapping.get(index).get("name");
+ ClassNode argAndTempType = DefaultGroovyMethods.asType(positionMapping.get(index).get("type"), ClassNode.class);
+ ExpressionStatement argAssignment = (ExpressionStatement) GeneralUtils.assignS(GeneralUtils.varX(argName, argAndTempType), expression);
+ return argAssignment;
+ }
+
+ private ExpressionStatement createTempDeclaration(int index, Map<Integer, Map> positionMapping, Map<String, Map> tempMapping, Map<String, ExpressionStatement> tempDeclarations) {
+ final String argName = (String) positionMapping.get(index).get("name");
+ String tempName = "_" + argName + "_";
+ ClassNode argAndTempType = DefaultGroovyMethods.asType(positionMapping.get(index).get("type"), ClassNode.class);
+ ExpressionStatement tempDeclaration = AstHelper.createVariableAlias(tempName, argAndTempType, argName);
+ Map<String, Object> map = new LinkedHashMap<String, Object>(2);
+ map.put("name", tempName);
+ map.put("type", argAndTempType);
+ tempMapping.put(argName, map);
+ tempDeclarations.put(tempName, tempDeclaration);
+ return tempDeclaration;
+ }
+
+ @SuppressWarnings("Instanceof")
+ private List<Expression> getArguments(Expression recursiveCall) {
+ if (recursiveCall instanceof MethodCallExpression)
+ return ((TupleExpression) ((MethodCallExpression) recursiveCall).getArguments()).getExpressions();
+ if (recursiveCall instanceof StaticMethodCallExpression)
+ return ((TupleExpression) ((StaticMethodCallExpression) recursiveCall).getArguments()).getExpressions();
+ return null;
+ }
+
+ private boolean isAMethodCalls(Expression expression) {
+ Class<?> clazz = expression.getClass();
+ return MethodCallExpression.class == clazz || StaticMethodCallExpression.class == clazz;
+ }
+
+ private Set<String> replaceAllArgUsages(List<ExpressionStatement> iterationVariablesAssignmentNodes, Map<String, Map> tempMapping) {
+ Set<String> unusedTempNames = DefaultGroovyMethods.asType(DefaultGroovyMethods.collect(tempMapping.values(), new Closure<String>(this, this) {
+ public String doCall(Map nameAndType) {
+ return (String) nameAndType.get("name");
+ }
+
+ }), Set.class);
+ VariableReplacedListener tracker = new UsedVariableTracker();
+ for (ExpressionStatement statement : iterationVariablesAssignmentNodes) {
+ replaceArgUsageByTempUsage((BinaryExpression) statement.getExpression(), tempMapping, (UsedVariableTracker) tracker);
+ }
+
+ unusedTempNames = DefaultGroovyMethods.minus(unusedTempNames, ((UsedVariableTracker) tracker).getUsedVariableNames());
+ return unusedTempNames;
+ }
+
+ private void replaceArgUsageByTempUsage(BinaryExpression binary, Map tempMapping, UsedVariableTracker tracker) {
+ VariableAccessReplacer replacer = new VariableAccessReplacer(tempMapping, tracker);
+ // Replacement must only happen in binary.rightExpression. It's a hack in VariableExpressionReplacer which takes care of that.
+ replacer.replaceIn(binary);
+ }
+
+ public Statement getRecurStatement() {
+ return recurStatement;
+ }
+
+ public void setRecurStatement(Statement recurStatement) {
+ this.recurStatement = recurStatement;
+ }
+
+ private Statement recurStatement = AstHelper.recurStatement();
+}
+
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/StatementReplacer.java b/src/main/java/org/codehaus/groovy/transform/tailrec/StatementReplacer.java
new file mode 100644
index 0000000..942baff
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/StatementReplacer.java
@@ -0,0 +1,174 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import org.codehaus.groovy.ast.ASTNode;
+import org.codehaus.groovy.ast.CodeVisitorSupport;
+import org.codehaus.groovy.ast.expr.ClosureExpression;
+import org.codehaus.groovy.ast.stmt.BlockStatement;
+import org.codehaus.groovy.ast.stmt.DoWhileStatement;
+import org.codehaus.groovy.ast.stmt.ForStatement;
+import org.codehaus.groovy.ast.stmt.IfStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
+import org.codehaus.groovy.ast.stmt.WhileStatement;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Tool for replacing Statement objects in an AST by other Statement instances.
+ * <p>
+ * Within @TailRecursive it is used to swap ReturnStatements with looping back to RECUR label
+ */
+class StatementReplacer extends CodeVisitorSupport {
+ public StatementReplacer(Closure<Boolean> when, Closure<Statement> replaceWith) {
+ this.when = when;
+ this.replaceWith = replaceWith;
+ }
+
+ public void replaceIn(ASTNode root) {
+ root.visit(this);
+ }
+
+ public void visitClosureExpression(ClosureExpression expression) {
+ closureLevel++;
+ try {
+ super.visitClosureExpression(expression);
+ } finally {
+ closureLevel--;
+ }
+ }
+
+ public void visitBlockStatement(final BlockStatement block) {
+ List<Statement> copyOfStatements = new ArrayList<Statement>(block.getStatements());
+ DefaultGroovyMethods.eachWithIndex(copyOfStatements, new Closure<Void>(this, this) {
+ public void doCall(Statement statement, final int index) {
+ replaceIfNecessary(statement, new Closure<Statement>(StatementReplacer.this, StatementReplacer.this) {
+ public Statement doCall(Statement node) {
+ block.getStatements().set(index, node);
+ return node;
+ }
+ });
+ }
+ });
+ super.visitBlockStatement(block);
+ }
+
+ public void visitIfElse(final IfStatement ifElse) {
+ replaceIfNecessary(ifElse.getIfBlock(), new Closure<Statement>(this, this) {
+ public Statement doCall(Statement s) {
+ ifElse.setIfBlock(s);
+ return s;
+ }
+ });
+ replaceIfNecessary(ifElse.getElseBlock(), new Closure<Statement>(this, this) {
+ public Statement doCall(Statement s) {
+ ifElse.setElseBlock(s);
+ return s;
+ }
+ });
+ super.visitIfElse(ifElse);
+ }
+
+ public void visitForLoop(final ForStatement forLoop) {
+ replaceIfNecessary(forLoop.getLoopBlock(), new Closure<Statement>(this, this) {
+ public Statement doCall(Statement s) {
+ forLoop.setLoopBlock(s);
+ return s;
+ }
+ });
+ super.visitForLoop(forLoop);
+ }
+
+ public void visitWhileLoop(final WhileStatement loop) {
+ replaceIfNecessary(loop.getLoopBlock(), new Closure<Statement>(this, this) {
+ public Statement doCall(Statement s) {
+ loop.setLoopBlock(s);
+ return s;
+ }
+ });
+ super.visitWhileLoop(loop);
+ }
+
+ public void visitDoWhileLoop(final DoWhileStatement loop) {
+ replaceIfNecessary(loop.getLoopBlock(), new Closure<Statement>(this, this) {
+ public Statement doCall(Statement s) {
+ loop.setLoopBlock(s);
+ return s;
+ }
+ });
+ super.visitDoWhileLoop(loop);
+ }
+
+ private void replaceIfNecessary(Statement nodeToCheck, Closure replacementCode) {
+ if (conditionFulfilled(nodeToCheck)) {
+ Statement replacement = replaceWith.call(nodeToCheck);
+ replacement.setSourcePosition(nodeToCheck);
+ replacement.copyNodeMetaData(nodeToCheck);
+ replacementCode.call(replacement);
+ }
+ }
+
+ private boolean conditionFulfilled(ASTNode nodeToCheck) {
+ if (when.getMaximumNumberOfParameters() < 2) return when.call(nodeToCheck);
+ return when.call(nodeToCheck, isInClosure());
+ }
+
+ private boolean isInClosure() {
+ return closureLevel > 0;
+ }
+
+ public Closure<Boolean> getWhen() {
+ return when;
+ }
+
+ public void setWhen(Closure<Boolean> when) {
+ this.when = when;
+ }
+
+ public Closure<Statement> getReplaceWith() {
+ return replaceWith;
+ }
+
+ public void setReplaceWith(Closure<Statement> replaceWith) {
+ this.replaceWith = replaceWith;
+ }
+
+ public int getClosureLevel() {
+ return closureLevel;
+ }
+
+ public void setClosureLevel(int closureLevel) {
+ this.closureLevel = closureLevel;
+ }
+
+ private Closure<Boolean> when = new Closure<Boolean>(this, this) {
+ public Boolean doCall(Statement node) {
+ return false;
+ }
+ };
+ private Closure<Statement> replaceWith = new Closure<Statement>(this, this) {
+ public Statement doCall(Statement statement) {
+ return statement;
+ }
+ };
+ private int closureLevel = 0;
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.java b/src/main/java/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.java
new file mode 100644
index 0000000..d406f39
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/TailRecursiveASTTransformation.java
@@ -0,0 +1,313 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import groovy.transform.Memoized;
+import groovy.transform.TailRecursive;
+import org.codehaus.groovy.ast.ASTNode;
+import org.codehaus.groovy.ast.AnnotationNode;
+import org.codehaus.groovy.ast.ClassHelper;
+import org.codehaus.groovy.ast.ClassNode;
+import org.codehaus.groovy.ast.MethodNode;
+import org.codehaus.groovy.ast.Parameter;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.MethodCallExpression;
+import org.codehaus.groovy.ast.expr.StaticMethodCallExpression;
+import org.codehaus.groovy.ast.expr.TernaryExpression;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+import org.codehaus.groovy.ast.stmt.BlockStatement;
+import org.codehaus.groovy.ast.stmt.ReturnStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
+import org.codehaus.groovy.classgen.ReturnAdder;
+import org.codehaus.groovy.classgen.VariableScopeVisitor;
+import org.codehaus.groovy.control.CompilePhase;
+import org.codehaus.groovy.control.SourceUnit;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+import org.codehaus.groovy.transform.AbstractASTTransformation;
+import org.codehaus.groovy.transform.GroovyASTTransformation;
+
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Handles generation of code for the @TailRecursive annotation.
+ * <p>
+ * It's doing its work in the earliest possible compile phase
+ */
+@GroovyASTTransformation(phase = CompilePhase.SEMANTIC_ANALYSIS)
+public class TailRecursiveASTTransformation extends AbstractASTTransformation {
+ @Override
+ public void visit(ASTNode[] nodes, SourceUnit source) {
+ init(nodes, source);
+
+ MethodNode method = DefaultGroovyMethods.asType(nodes[1], MethodNode.class);
+
+ if (method.isAbstract()) {
+ addError("Annotation " + TailRecursiveASTTransformation.getMY_TYPE_NAME() + " cannot be used for abstract methods.", method);
+ return;
+
+ }
+
+
+ if (hasAnnotation(method, ClassHelper.make(Memoized.class))) {
+ ClassNode memoizedClassNode = ClassHelper.make(Memoized.class);
+ for (AnnotationNode annotationNode : method.getAnnotations()) {
+ if (annotationNode.getClassNode().equals(MY_TYPE)) break;
+ if (annotationNode.getClassNode().equals(memoizedClassNode)) {
+ addError("Annotation " + TailRecursiveASTTransformation.getMY_TYPE_NAME() + " must be placed before annotation @Memoized.", annotationNode);
+ return;
+
+ }
+
+ }
+
+ }
+
+
+ if (!hasRecursiveMethodCalls(method)) {
+ AnnotationNode annotationNode = method.getAnnotations(ClassHelper.make(TailRecursive.class)).get(0);
+ addError("No recursive calls detected. You must remove annotation " + TailRecursiveASTTransformation.getMY_TYPE_NAME() + ".", annotationNode);
+ return;
+
+ }
+
+
+ transformToIteration(method, source);
+ ensureAllRecursiveCallsHaveBeenTransformed(method);
+ }
+
+ private boolean hasAnnotation(MethodNode methodNode, ClassNode annotation) {
+ List annots = methodNode.getAnnotations(annotation);
+ return annots != null && annots.size() > 0;
+ }
+
+ private void transformToIteration(MethodNode method, SourceUnit source) {
+ if (method.isVoidMethod()) {
+ transformVoidMethodToIteration(method);
+ } else {
+ transformNonVoidMethodToIteration(method, source);
+ }
+
+ }
+
+ private void transformVoidMethodToIteration(MethodNode method) {
+ addError("Void methods are not supported by @TailRecursive yet.", method);
+ }
+
+ private void transformNonVoidMethodToIteration(MethodNode method, SourceUnit source) {
+ addMissingDefaultReturnStatement(method);
+ replaceReturnsWithTernariesToIfStatements(method);
+ wrapMethodBodyWithWhileLoop(method);
+
+ Map<String, Map> nameAndTypeMapping = name2VariableMappingFor(method);
+ replaceAllAccessToParams(method, nameAndTypeMapping);
+ addLocalVariablesForAllParameters(method, nameAndTypeMapping);//must happen after replacing access to params
+
+ Map<Integer, Map> positionMapping = position2VariableMappingFor(method);
+ replaceAllRecursiveReturnsWithIteration(method, positionMapping);
+ repairVariableScopes(source, method);
+ }
+
+ private void repairVariableScopes(SourceUnit source, MethodNode method) {
+ new VariableScopeVisitor(source).visitClass(method.getDeclaringClass());
+ }
+
+ @SuppressWarnings("Instanceof")
+ private void replaceReturnsWithTernariesToIfStatements(MethodNode method) {
+ Closure<Boolean> whenReturnWithTernary = new Closure<Boolean>(this, this) {
+ public Boolean doCall(ASTNode node) {
+ if (!(node instanceof ReturnStatement)) {
+ return false;
+ }
+
+ return ((ReturnStatement) node).getExpression() instanceof TernaryExpression;
+ }
+
+ };
+ Closure<Statement> replaceWithIfStatement = new Closure<Statement>(this, this) {
+ public Statement doCall(ReturnStatement statement) {
+ return ternaryToIfStatement.convert(statement);
+ }
+
+ };
+ StatementReplacer replacer = new StatementReplacer(whenReturnWithTernary, replaceWithIfStatement);
+ replacer.replaceIn(method.getCode());
+
+ }
+
+ private void addLocalVariablesForAllParameters(MethodNode method, Map<String, Map> nameAndTypeMapping) {
+ final BlockStatement code = DefaultGroovyMethods.asType(method.getCode(), BlockStatement.class);
+ DefaultGroovyMethods.each(nameAndTypeMapping, new Closure<Void>(this, this) {
+ public void doCall(String paramName, Map localNameAndType) {
+ code.getStatements().add(0, AstHelper.createVariableDefinition((String) localNameAndType.get("name"), (ClassNode) localNameAndType.get("type"), new VariableExpression(paramName, (ClassNode) localNameAndType.get("type"))));
+ }
+
+ });
+ }
+
+ private void replaceAllAccessToParams(MethodNode method, Map<String, Map> nameAndTypeMapping) {
+ new VariableAccessReplacer(nameAndTypeMapping).replaceIn(method.getCode());
+ }
+
+ public Map<String, Map> name2VariableMappingFor(MethodNode method) {
+ final Map<String, Map> nameAndTypeMapping = new LinkedHashMap<String, Map>();
+ DefaultGroovyMethods.each(method.getParameters(), new Closure<LinkedHashMap<String, Object>>(this, this) {
+ public LinkedHashMap<String, Object> doCall(Parameter param) {
+ String paramName = param.getName();
+ ClassNode paramType = DefaultGroovyMethods.asType(param.getType(), ClassNode.class);
+ String iterationVariableName = iterationVariableName(paramName);
+ LinkedHashMap<String, Object> map = new LinkedHashMap<String, Object>(2);
+ map.put("name", iterationVariableName);
+ map.put("type", paramType);
+ return putAt0(nameAndTypeMapping, paramName, map);
+ }
+
+ });
+ return nameAndTypeMapping;
+ }
+
+ public Map<Integer, Map> position2VariableMappingFor(MethodNode method) {
+ final Map<Integer, Map> positionMapping = new LinkedHashMap<Integer, Map>();
+ DefaultGroovyMethods.eachWithIndex(method.getParameters(), new Closure<LinkedHashMap<String, Object>>(this, this) {
+ public LinkedHashMap<String, Object> doCall(Parameter param, int index) {
+ String paramName = param.getName();
+ ClassNode paramType = DefaultGroovyMethods.asType(param.getType(), ClassNode.class);
+ String iterationVariableName = TailRecursiveASTTransformation.this.iterationVariableName(paramName);
+ LinkedHashMap<String, Object> map = new LinkedHashMap<String, Object>(2);
+ map.put("name", iterationVariableName);
+ map.put("type", paramType);
+ return putAt0(positionMapping, index, map);
+ }
+
+ });
+ return positionMapping;
+ }
+
+ private String iterationVariableName(String paramName) {
+ return "_" + paramName + "_";
+ }
+
+ private void replaceAllRecursiveReturnsWithIteration(MethodNode method, Map positionMapping) {
+ replaceRecursiveReturnsOutsideClosures(method, positionMapping);
+ replaceRecursiveReturnsInsideClosures(method, positionMapping);
+ }
+
+ @SuppressWarnings("Instanceof")
+ private void replaceRecursiveReturnsOutsideClosures(final MethodNode method, final Map<Integer, Map> positionMapping) {
+ Closure<Boolean> whenRecursiveReturn = new Closure<Boolean>(this, this) {
+ public Boolean doCall(Statement statement, boolean inClosure) {
+ if (inClosure) return false;
+ if (!(statement instanceof ReturnStatement)) {
+ return false;
+ }
+
+ Expression inner = ((ReturnStatement) statement).getExpression();
+ if (!(inner instanceof MethodCallExpression) && !(inner instanceof StaticMethodCallExpression)) {
+ return false;
+ }
+
+ return isRecursiveIn(inner, method);
+ }
+
+ };
+ Closure<Statement> replaceWithContinueBlock = new Closure<Statement>(this, this) {
+ public Statement doCall(ReturnStatement statement) {
+ return new ReturnStatementToIterationConverter().convert(statement, positionMapping);
+ }
+
+ };
+ StatementReplacer replacer = new StatementReplacer(whenRecursiveReturn, replaceWithContinueBlock);
+ replacer.replaceIn(method.getCode());
+ }
+
+ @SuppressWarnings("Instanceof")
+ private void replaceRecursiveReturnsInsideClosures(final MethodNode method, final Map<Integer, Map> positionMapping) {
+ Closure<Boolean> whenRecursiveReturn = new Closure<Boolean>(this, this) {
+ public Boolean doCall(Statement statement, boolean inClosure) {
+ if (!inClosure) return false;
+ if (!(statement instanceof ReturnStatement)) {
+ return false;
+ }
+
+ Expression inner = ((ReturnStatement) statement).getExpression();
+ if (!(inner instanceof MethodCallExpression) && !(inner instanceof StaticMethodCallExpression)) {
+ return false;
+ }
+
+ return isRecursiveIn(inner, method);
+ }
+
+ };
+ Closure<Statement> replaceWithThrowLoopException = new Closure<Statement>(this, this) {
+ public Statement doCall(ReturnStatement statement) {
+ return new ReturnStatementToIterationConverter(AstHelper.recurByThrowStatement()).convert(statement, positionMapping);
+ }
+
+ };
+ StatementReplacer replacer = new StatementReplacer(whenRecursiveReturn, replaceWithThrowLoopException);
+ replacer.replaceIn(method.getCode());
+ }
+
+ private void wrapMethodBodyWithWhileLoop(MethodNode method) {
+ new InWhileLoopWrapper().wrap(method);
+ }
+
+ private void addMissingDefaultReturnStatement(MethodNode method) {
+ new ReturnAdder().visitMethod(method);
+ new ReturnAdderForClosures().visitMethod(method);
+ }
+
+ private void ensureAllRecursiveCallsHaveBeenTransformed(MethodNode method) {
+ List<Expression> remainingRecursiveCalls = new CollectRecursiveCalls().collect(method);
+ for (Expression expression : remainingRecursiveCalls) {
+ addError("Recursive call could not be transformed by @TailRecursive. Maybe it's not a tail call.", expression);
+ }
+
+ }
+
+ private boolean hasRecursiveMethodCalls(MethodNode method) {
+ return hasRecursiveCalls.test(method);
+ }
+
+ @SuppressWarnings("Instanceof")
+ private boolean isRecursiveIn(Expression methodCall, MethodNode method) {
+ if (methodCall instanceof MethodCallExpression)
+ return new RecursivenessTester().isRecursive(method, (MethodCallExpression) methodCall);
+ if (methodCall instanceof StaticMethodCallExpression)
+ return new RecursivenessTester().isRecursive(method, (StaticMethodCallExpression) methodCall);
+ return false;
+ }
+
+ public static String getMY_TYPE_NAME() {
+ return MY_TYPE_NAME;
+ }
+
+ private static final Class MY_CLASS = TailRecursive.class;
+ private static final ClassNode MY_TYPE = new ClassNode(MY_CLASS);
+ private static final String MY_TYPE_NAME = "@" + MY_TYPE.getNameWithoutPackage();
+ private final HasRecursiveCalls hasRecursiveCalls = new HasRecursiveCalls();
+ private final TernaryToIfStatementConverter ternaryToIfStatement = new TernaryToIfStatementConverter();
+
+ private static <K, V, Value extends V> Value putAt0(Map<K, V> propOwner, K key, Value value) {
+ propOwner.put(key, value);
+ return value;
+ }
+}
diff --git a/src/main/groovy/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.groovy b/src/main/java/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.java
similarity index 60%
rename from src/main/groovy/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.groovy
rename to src/main/java/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.java
index 165650f..4016c5c 100644
--- a/src/main/groovy/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.groovy
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/TernaryToIfStatementConverter.java
@@ -16,28 +16,26 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.codehaus.groovy.transform.tailrec
+package org.codehaus.groovy.transform.tailrec;
-import groovy.transform.CompileStatic
-import org.codehaus.groovy.ast.expr.TernaryExpression
-import org.codehaus.groovy.ast.stmt.ReturnStatement
-import org.codehaus.groovy.ast.stmt.Statement
+import org.codehaus.groovy.ast.expr.TernaryExpression;
+import org.codehaus.groovy.ast.stmt.ReturnStatement;
+import org.codehaus.groovy.ast.stmt.Statement;
-import static org.codehaus.groovy.ast.tools.GeneralUtils.ifElseS
-import static org.codehaus.groovy.ast.tools.GeneralUtils.returnS
+import static org.codehaus.groovy.ast.tools.GeneralUtils.ifElseS;
+import static org.codehaus.groovy.ast.tools.GeneralUtils.returnS;
+import static org.codehaus.groovy.runtime.DefaultGroovyMethods.asType;
/**
* Since a ternary statement has more than one exit point tail-recursiveness testing cannot be easily done.
* Therefore this class translates a ternary statement (or Elvis operator) into the equivalent if-else statement.
*/
-@CompileStatic
class TernaryToIfStatementConverter {
-
- @SuppressWarnings('Instanceof')
- Statement convert(ReturnStatement statementWithInnerTernaryExpression) {
- if (!(statementWithInnerTernaryExpression.expression instanceof TernaryExpression))
- return statementWithInnerTernaryExpression
- TernaryExpression ternary = statementWithInnerTernaryExpression.expression as TernaryExpression
- ifElseS(ternary.booleanExpression, returnS(ternary.trueExpression), returnS(ternary.falseExpression))
+ @SuppressWarnings("Instanceof")
+ public Statement convert(ReturnStatement statementWithInnerTernaryExpression) {
+ if (!(statementWithInnerTernaryExpression.getExpression() instanceof TernaryExpression))
+ return statementWithInnerTernaryExpression;
+ TernaryExpression ternary = asType(statementWithInnerTernaryExpression.getExpression(), TernaryExpression.class);
+ return ifElseS(ternary.getBooleanExpression(), returnS(ternary.getTrueExpression()), returnS(ternary.getFalseExpression()));
}
}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/UsedVariableTracker.java b/src/main/java/org/codehaus/groovy/transform/tailrec/UsedVariableTracker.java
new file mode 100644
index 0000000..6f08f96
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/UsedVariableTracker.java
@@ -0,0 +1,38 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.codehaus.groovy.ast.expr.VariableExpression;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.util.ArrayList;
+import java.util.Set;
+
+class UsedVariableTracker implements VariableReplacedListener {
+ @Override
+ public void variableReplaced(VariableExpression oldVar, VariableExpression newVar) {
+ usedVariableNames.add(newVar.getName());
+ }
+
+ public Set<String> getUsedVariableNames() {
+ return usedVariableNames;
+ }
+
+ private final Set<String> usedVariableNames = DefaultGroovyMethods.asType(new ArrayList(), Set.class);
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.java b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.java
new file mode 100644
index 0000000..8225aa4
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableAccessReplacer.java
@@ -0,0 +1,66 @@
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import org.codehaus.groovy.ast.ASTNode;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+/**
+ * Replace all access to variables and args by new variables.
+ * The variable names to replace as well as their replacement name and type have to be configured
+ * in nameAndTypeMapping before calling replaceIn().
+ * <p>
+ * The VariableReplacedListener can be set if clients want to react to variable replacement.
+ */
+class VariableAccessReplacer {
+ public VariableAccessReplacer(Map<String, Map> nameAndTypeMapping) {
+ this.nameAndTypeMapping = nameAndTypeMapping;
+ }
+
+ public VariableAccessReplacer(Map<String, Map> nameAndTypeMapping, VariableReplacedListener listener) {
+ this.nameAndTypeMapping = nameAndTypeMapping;
+ this.listener = listener;
+ }
+
+ public void replaceIn(ASTNode root) {
+ Closure<Boolean> whenParam = new Closure<Boolean>(this, this) {
+ public Boolean doCall(VariableExpression expr) {
+ return nameAndTypeMapping.containsKey(expr.getName());
+ }
+
+ };
+ Closure<VariableExpression> replaceWithLocalVariable = new Closure<VariableExpression>(this, this) {
+ public VariableExpression doCall(VariableExpression expr) {
+ VariableExpression newVar = AstHelper.createVariableReference(nameAndTypeMapping.get(expr.getName()));
+ getListener().variableReplaced(expr, newVar);
+ return newVar;
+ }
+
+ };
+ new VariableExpressionReplacer(whenParam, replaceWithLocalVariable).replaceIn(root);
+ }
+
+ public void setNameAndTypeMapping(Map<String, Map> nameAndTypeMapping) {
+ this.nameAndTypeMapping = nameAndTypeMapping;
+ }
+
+ public VariableReplacedListener getListener() {
+ return listener;
+ }
+
+ public void setListener(VariableReplacedListener listener) {
+ this.listener = listener;
+ }
+
+ /**
+ * Nested map of variable accesses to replace
+ * e.g.: [
+ * 'varToReplace': [name: 'newVar', type: TypeOfVar],
+ * 'varToReplace2': [name: 'newVar2', type: TypeOfVar2],
+ * ]
+ */
+ private Map<String, Map> nameAndTypeMapping = new LinkedHashMap<>();
+ private VariableReplacedListener listener = VariableReplacedListener.NULL;
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.java b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.java
new file mode 100644
index 0000000..14aa777
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacer.java
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import org.apache.groovy.internal.util.UncheckedThrow;
+import org.codehaus.groovy.ast.ASTNode;
+import org.codehaus.groovy.ast.CodeVisitorSupport;
+import org.codehaus.groovy.ast.expr.BinaryExpression;
+import org.codehaus.groovy.ast.expr.BooleanExpression;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.ExpressionTransformer;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+import org.codehaus.groovy.ast.stmt.AssertStatement;
+import org.codehaus.groovy.ast.stmt.CaseStatement;
+import org.codehaus.groovy.ast.stmt.DoWhileStatement;
+import org.codehaus.groovy.ast.stmt.ExpressionStatement;
+import org.codehaus.groovy.ast.stmt.ForStatement;
+import org.codehaus.groovy.ast.stmt.IfStatement;
+import org.codehaus.groovy.ast.stmt.ReturnStatement;
+import org.codehaus.groovy.ast.stmt.SwitchStatement;
+import org.codehaus.groovy.ast.stmt.SynchronizedStatement;
+import org.codehaus.groovy.ast.stmt.ThrowStatement;
+import org.codehaus.groovy.ast.stmt.WhileStatement;
+import org.codehaus.groovy.ast.tools.GeneralUtils;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
+
+import java.lang.reflect.Method;
+
+/**
+ * Tool for replacing VariableExpression instances in an AST by other VariableExpression instances.
+ * Regardless of a real change taking place in nested expressions, all considered expression (trees) will be replaced.
+ * This could be optimized to accelerate compilation.
+ * <p>
+ * Within @TailRecursive it is used
+ * - to swap the access of method args with the access to iteration variables
+ * - to swap the access of iteration variables with the access of temp vars
+ */
+class VariableExpressionReplacer extends CodeVisitorSupport {
+ VariableExpressionReplacer(Closure<Boolean> when, Closure<VariableExpression> replaceWith) {
+ this.when = when;
+ this.replaceWith = replaceWith;
+ }
+
+ @Override
+ public void visitReturnStatement(final ReturnStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitReturnStatement(statement);
+ }
+
+ @Override
+ public void visitIfElse(final IfStatement ifElse) {
+ replaceExpressionPropertyWhenNecessary(ifElse, "booleanExpression", BooleanExpression.class);
+ super.visitIfElse(ifElse);
+ }
+
+ @Override
+ public void visitForLoop(final ForStatement forLoop) {
+ replaceExpressionPropertyWhenNecessary(forLoop, "collectionExpression");
+ super.visitForLoop(forLoop);
+ }
+
+ /**
+ * It's the only Expression type in which replacing is considered.
+ * That's an abuse of the class, but I couldn't think of a better way.
+ */
+ @Override
+ public void visitBinaryExpression(final BinaryExpression expression) {
+ //A hack: Only replace right expression b/c ReturnStatementToIterationConverter needs it that way :-/
+ replaceExpressionPropertyWhenNecessary(expression, "rightExpression");
+ expression.getRightExpression().visit(this);
+ super.visitBinaryExpression(expression);
+ }
+
+ @Override
+ public void visitWhileLoop(final WhileStatement loop) {
+ replaceExpressionPropertyWhenNecessary(loop, "booleanExpression", BooleanExpression.class);
+ super.visitWhileLoop(loop);
+ }
+
+ @Override
+ public void visitDoWhileLoop(final DoWhileStatement loop) {
+ replaceExpressionPropertyWhenNecessary(loop, "booleanExpression", BooleanExpression.class);
+ super.visitDoWhileLoop(loop);
+ }
+
+ @Override
+ public void visitSwitch(final SwitchStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitSwitch(statement);
+ }
+
+ @Override
+ public void visitCaseStatement(final CaseStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitCaseStatement(statement);
+ }
+
+ @Override
+ public void visitExpressionStatement(final ExpressionStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitExpressionStatement(statement);
+ }
+
+ @Override
+ public void visitThrowStatement(final ThrowStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitThrowStatement(statement);
+ }
+
+ @Override
+ public void visitAssertStatement(final AssertStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement, "booleanExpression", BooleanExpression.class);
+ replaceExpressionPropertyWhenNecessary(statement, "messageExpression");
+ super.visitAssertStatement(statement);
+ }
+
+ @Override
+ public void visitSynchronizedStatement(final SynchronizedStatement statement) {
+ replaceExpressionPropertyWhenNecessary(statement);
+ super.visitSynchronizedStatement(statement);
+ }
+
+ public synchronized void replaceIn(final ASTNode root) {
+ transformer = new VariableExpressionTransformer(when, replaceWith);
+ root.visit(this);
+ }
+
+ private void replaceExpressionPropertyWhenNecessary(final ASTNode node, final String propName, final Class propClass) {
+ Expression expr = getExpression(node, propName);
+
+ if (expr instanceof VariableExpression) {
+ if (when.call(expr)) {
+ VariableExpression newExpr = replaceWith.call(expr);
+ replaceExpression(node, propName, propClass, expr, newExpr);
+ }
+ } else {
+ Expression newExpr = transformer.transform(expr);
+ replaceExpression(node, propName, propClass, expr, newExpr);
+ }
+ }
+
+ private void replaceExpressionPropertyWhenNecessary(final ASTNode node, final String propName) {
+ replaceExpressionPropertyWhenNecessary(node, propName, Expression.class);
+ }
+
+ private void replaceExpressionPropertyWhenNecessary(final ASTNode node) {
+ replaceExpressionPropertyWhenNecessary(node, "expression", Expression.class);
+ }
+
+ private void replaceExpression(final ASTNode node, final String propName, final Class propClass, final Expression oldExpr, final Expression newExpr) {
+ try {
+ //Use reflection to enable CompileStatic
+ String setterName = GeneralUtils.getSetterName(propName);
+ Method setExpressionMethod = node.getClass().getMethod(setterName, propClass);
+ newExpr.copyNodeMetaData(oldExpr);
+ newExpr.setSourcePosition(oldExpr);
+ setExpressionMethod.invoke(node, newExpr);
+ } catch (Throwable t) {
+ UncheckedThrow.rethrow(t);
+ }
+ }
+
+ private Expression getExpression(final ASTNode node, final String propName) {
+ try {
+ //Use reflection to enable CompileStatic
+ String getterName = GeneralUtils.getGetterName(propName);
+ Method getExpressionMethod = node.getClass().getMethod(getterName);
+ return DefaultGroovyMethods.asType(getExpressionMethod.invoke(node), Expression.class);
+ } catch (Throwable t) {
+ UncheckedThrow.rethrow(t);
+ return null;
+ }
+ }
+
+ public Closure<Boolean> getWhen() {
+ return when;
+ }
+
+ public void setWhen(Closure<Boolean> when) {
+ this.when = when;
+ }
+
+ public Closure<VariableExpression> getReplaceWith() {
+ return replaceWith;
+ }
+
+ public void setReplaceWith(Closure<VariableExpression> replaceWith) {
+ this.replaceWith = replaceWith;
+ }
+
+ private Closure<Boolean> when = new Closure<Boolean>(this, this) {
+ public Boolean doCall(final VariableExpression node) {
+ return false;
+ }
+ };
+ private Closure<VariableExpression> replaceWith = new Closure<VariableExpression>(this, this) {
+ public VariableExpression doCall(final VariableExpression variableExpression) {
+ return variableExpression;
+ }
+ };
+ private ExpressionTransformer transformer;
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.java b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.java
new file mode 100644
index 0000000..78a8360
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableExpressionTransformer.java
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import groovy.lang.Closure;
+import org.codehaus.groovy.ast.expr.Expression;
+import org.codehaus.groovy.ast.expr.ExpressionTransformer;
+import org.codehaus.groovy.ast.expr.VariableExpression;
+
+/**
+ * An expression transformer used in the process of replacing the access to variables
+ */
+class VariableExpressionTransformer implements ExpressionTransformer {
+ public VariableExpressionTransformer(Closure<Boolean> when, Closure<VariableExpression> replaceWith) {
+ this.when = when;
+ this.replaceWith = replaceWith;
+ }
+
+ @Override
+ @SuppressWarnings("Instanceof")
+ public Expression transform(Expression expr) {
+ if ((expr instanceof VariableExpression) && when.call(expr)) {
+ VariableExpression newExpr = replaceWith.call(expr);
+ newExpr.setSourcePosition(expr);
+ newExpr.copyNodeMetaData(expr);
+ return newExpr;
+ }
+
+ return expr.transformExpression(this);
+ }
+
+ public Closure<Boolean> getWhen() {
+ return when;
+ }
+
+ public void setWhen(Closure<Boolean> when) {
+ this.when = when;
+ }
+
+ public Closure<VariableExpression> getReplaceWith() {
+ return replaceWith;
+ }
+
+ public void setReplaceWith(Closure<VariableExpression> replaceWith) {
+ this.replaceWith = replaceWith;
+ }
+
+ private Closure<Boolean> when;
+ private Closure<VariableExpression> replaceWith;
+}
diff --git a/src/main/java/org/codehaus/groovy/transform/tailrec/VariableReplacedListener.java b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableReplacedListener.java
new file mode 100644
index 0000000..37da93b
--- /dev/null
+++ b/src/main/java/org/codehaus/groovy/transform/tailrec/VariableReplacedListener.java
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.codehaus.groovy.transform.tailrec;
+
+import org.codehaus.groovy.ast.expr.VariableExpression;
+
+interface VariableReplacedListener {
+ VariableReplacedListener NULL = (oldVar, newVar) -> {
+ //do nothing
+ };
+
+ void variableReplaced(VariableExpression oldVar, VariableExpression newVar);
+}
diff --git a/src/test/org/codehaus/groovy/transform/tailrec/StatementReplacerTest.groovy b/src/test/org/codehaus/groovy/transform/tailrec/StatementReplacerTest.groovy
index 786fed3..a6f77f7 100644
--- a/src/test/org/codehaus/groovy/transform/tailrec/StatementReplacerTest.groovy
+++ b/src/test/org/codehaus/groovy/transform/tailrec/StatementReplacerTest.groovy
@@ -25,7 +25,15 @@ import org.codehaus.groovy.ast.builder.AstBuilder
import org.codehaus.groovy.ast.expr.BooleanExpression
import org.codehaus.groovy.ast.expr.ClosureExpression
import org.codehaus.groovy.ast.expr.ConstantExpression
-import org.codehaus.groovy.ast.stmt.*
+import org.codehaus.groovy.ast.stmt.BlockStatement
+import org.codehaus.groovy.ast.stmt.DoWhileStatement
+import org.codehaus.groovy.ast.stmt.EmptyStatement
+import org.codehaus.groovy.ast.stmt.ExpressionStatement
+import org.codehaus.groovy.ast.stmt.ForStatement
+import org.codehaus.groovy.ast.stmt.IfStatement
+import org.codehaus.groovy.ast.stmt.ReturnStatement
+import org.codehaus.groovy.ast.stmt.Statement
+import org.codehaus.groovy.ast.stmt.WhileStatement
import org.junit.Before
import org.junit.Test
@@ -38,7 +46,7 @@ class StatementReplacerTest {
@Before
void init() {
- replacer = new StatementReplacer(when: when, replaceWith: replaceWith)
+ replacer = new StatementReplacer(when, replaceWith)
}
@Test
@@ -81,7 +89,7 @@ class StatementReplacerTest {
block.addStatement(toReplace)
block.addStatement(aReturnStatement("after"))
- replacer = new StatementReplacer(when: { it == toReplace }, replaceWith: {
+ replacer = new StatementReplacer({ it == toReplace }, {
assert it == toReplace
replacement
})
@@ -187,8 +195,8 @@ class StatementReplacerTest {
}[0]
def replacer = new StatementReplacer(
- when: { node, inClosure -> inClosure && node instanceof ExpressionStatement },
- replaceWith: { new ExpressionStatement(aConstant('new')) }
+ { node, inClosure -> inClosure && node instanceof ExpressionStatement },
+ { new ExpressionStatement(aConstant('new')) }
)
replacer.replaceIn(closure)
@@ -206,8 +214,8 @@ class StatementReplacerTest {
}[0]
def replacer = new StatementReplacer(
- when: { node, inClosure -> inClosure && node instanceof ExpressionStatement },
- replaceWith: { assert false, 'Must not get here' }
+ { node, inClosure -> inClosure && node instanceof ExpressionStatement },
+ { assert false, 'Must not get here' }
)
replacer.replaceIn(block)
}
diff --git a/src/test/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacerTest.groovy b/src/test/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacerTest.groovy
index cca4408..9ae4559 100644
--- a/src/test/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacerTest.groovy
+++ b/src/test/org/codehaus/groovy/transform/tailrec/VariableExpressionReplacerTest.groovy
@@ -53,7 +53,7 @@ class VariableExpressionReplacerTest {
@Before
void init() {
- replacer = new VariableExpressionReplacer(when: when, replaceWith: replaceWith)
+ replacer = new VariableExpressionReplacer(when, replaceWith)
}
@Test