Last active
September 2, 2020 14:19
-
-
Save elizarov/d715c9564288c2635bb55687e7341717 to your computer and use it in GitHub Desktop.
Using coroutines to avoid StackOverflowException on recursive calls
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import kotlin.coroutines.experimental.* | |
import kotlin.coroutines.experimental.intrinsics.COROUTINE_SUSPENDED | |
import kotlin.coroutines.experimental.intrinsics.suspendCoroutineOrReturn | |
@RestrictsSuspension | |
abstract class StackComputation { | |
abstract suspend fun <T> push(block: suspend StackComputation.() -> T): T | |
} | |
fun <T> compute(block: suspend StackComputation.() -> T): T = | |
StackComputationImpl(block).run { | |
process() | |
result as T | |
} | |
private class StackComputationImpl<T>(block: suspend StackComputation.() -> T) : StackComputation() { | |
private val stack = mutableListOf<() -> Unit>() | |
var result: T? = null | |
init { | |
stack.add { | |
block.startCoroutine(this, object : Continuation<T> { | |
override val context: CoroutineContext get() = EmptyCoroutineContext | |
override fun resume(value: T) { result = value } | |
override fun resumeWithException(exception: Throwable) { throw exception } | |
}) | |
} | |
} | |
fun process() { | |
while (!stack.isEmpty()) stack.removeAt(stack.lastIndex)() | |
} | |
override suspend fun <T> push(block: suspend StackComputation.() -> T): T = suspendCoroutineOrReturn { cont -> | |
stack.add { | |
block.startCoroutine(this, object : Continuation<T> { | |
override val context: CoroutineContext get() = EmptyCoroutineContext | |
override fun resume(value: T) { stack.add { cont.resume(value) } } | |
override fun resumeWithException(exception: Throwable) { throw exception } | |
}) | |
} | |
COROUTINE_SUSPENDED | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
sealed class Tree | |
class Leaf(val i: Int) : Tree() | |
class Node(val a: Tree, val b: Tree) : Tree() | |
suspend fun StackComputation.recSum(t: Tree): Int = push { | |
when(t) { | |
is Leaf -> t.i | |
is Node -> recSum(t.a) + recSum(t.b) | |
} | |
} | |
fun main(args: Array<String>) { | |
// build long-tree | |
var cur: Tree = Leaf(1) | |
repeat(100000) { | |
cur = Node(Leaf(1), cur) | |
} | |
// compute w/o stack overflow | |
println(compute { recSum(cur) }) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment