This only happens in very particular cases. It is hard to explain exactly when without knowledge of the source code, so I'm going to assume the reader knows where to find it. I used Gradle 2.0 for debugging, but was also able to reproduce the issue on Gradle 1.12.

The following code reproduces the problem:

task a
task b
task c
task d

d.dependsOn a, b, c

// populate walkedShouldRunAfterEdges with a->b
a.shouldRunAfter b

// cause circular dependency logic to activate.
c.dependsOn d

Small piece of the stacktrace when running task d:

java.util.EmptyStackException
at org.gradle.execution.taskgraph.DefaultTaskExecutionPlan.restorePath(DefaultTaskExecutionPlan.java:280)
at org.gradle.execution.taskgraph.DefaultTaskExecutionPlan.determineExecutionPlan(DefaultTaskExecutionPlan.java:226)
at org.gradle.execution.taskgraph.DefaultTaskGraphExecuter.ensurePopulated(DefaultTaskGraphExecuter.java:148)
at org.gradle.execution.taskgraph.DefaultTaskGraphExecuter.execute(DefaultTaskGraphExecuter.java:82)
at org.gradle.execution.SelectedTaskExecutionAction.execute(SelectedTaskExecutionAction.java:29)
at org.gradle.execution.DefaultBuildExecuter.execute(DefaultBuildExecuter.java:61)
at org.gradle.execution.DefaultBuildExecuter.access$200(DefaultBuildExecuter.java:23)
at org.gradle.execution.DefaultBuildExecuter$2.proceed(DefaultBuildExecuter.java:67)
at org.gradle.execution.DryRunBuildExecutionAction.execute(DryRunBuildExecutionAction.java:32)
at org.gradle.execution.DefaultBuildExecuter.execute(DefaultBuildExecuter.java:61)
at org.gradle.execution.DefaultBuildExecuter.execute(DefaultBuildExecuter.java:54)

In the example above the problem is that you want a clear error message rather than an EmptyStackException. I'm not sure if it is possible to create an example which should run but also triggers this issue. My real case is rather big so I do not know if there is a circular dependency.

My analysis of the issue:

The DefaultTaskExecutionPlan goes depth-first into the graph of dependencies. 'path' keeps a list of all encountered nodes. If there are no unresolved dependencies (dependsOn, shouldRunAfter, mustRunAfter), a node is added to the executionPlan and removed from path. That node is then skipped in all later cases. If a node is encountered twice before reaching a 'leaf' (no unresolved dependencies), then there is a circular dependency and a nice error message is shown.

So far so good. However, if 'shouldRunAfter' causes a circular dependency, we want to ignore it. I do not completely understand the code that does this, but it seems it keeps a record of what dependencies are introduced through 'shouldRunAfter' (in walkedShouldRunAfterEdges) and uses this to restore a snapshot when 'shouldRunAfter' causes a circular dependency. This restoring of the snapshot is what goes wrong when walkedShouldRunAfterEdges is populated with a dependency from a node that is no longer present in path.