Kotlin - How to generify recursive functions that can't be reified?

Question

I want to generify the following function:

fun ViewGroup.allRadioButtons(f: (RadioButton) -> Unit){
    this.afterMeasured {
        for(i in 0 until childCount){
            val child = getChildAt(i)
            if(child is RadioButton){
                f(child)
            }
            if(child is ViewGroup){
                child.allRadioButtons(f)
            }
        }
    }
}

So instead of hardcoding RadioButton, I would like to use a generic T, like this:

inline fun <reified T> ViewGroup.allViewsOfTypeT(f: (T) -> Unit){
    this.afterMeasured {
        for(i in 0 until childCount){
            val child = getChildAt(i)
            if(child is T){
                f(child)
            }
            if(child is ViewGroup){
                child.allRadioButtons(f)
            }
        }
    }
}

I can't do the above because reified types are not allowed in recursive functions.

How can I generify that function in Kotlin?

Salem · Accepted Answer · 2020-04-19T15:18:48.970

You can make the recursive function non-inline and take a KClass representing the desired type, and make an additional wrapper function:

fun <T : View> ViewGroup.allViewsOfTypeT(type: KClass<T>, f: (T) -> Unit) {
    afterMeasured {
        for (i in 0 until childCount) {
            val child = getChildAt(i)
            if (type.isInstance(child)) f(child)
            if (child is ViewGroup) child.allViewsOfTypeT(type, f)
        }
    }
}

inline fun <reified T : View> ViewGroup.allViewsOfTypeT(f: (T) -> Unit)
    = allViewsOfTypeT(T::class, f)

You can't inline a recursive function, unless you can unroll it into a loop, because inlining a function means that after compilation it isn't a function anymore - it is instead copied directly into the call site. No function, no call stack, no recursion. In these cases, you have to pass a KClass instead of making the generic parameter reified, which is basically exactly what you'd do in Java if you needed an instanceof check with a generic parameter.

However, you can roll your own stack (Way to go from recursion to iteration):

inline fun <reified T : View> ViewGroup.allViewsOfTypeT(action: (T) -> Unit) {
    val views = Stack<View>()

    afterMeasured {
        views.addAll((0 until childCount).map(this::getChildAt))
    }

    while (!views.isEmpty()) {
        views.pop().let {
            if (it is T) action(it)
            if (it is ViewGroup) {
                afterMeasured {
                    views.addAll((0 until childCount).map(this::getChildAt))
                }
            }
        }
    }
}

I haven't tested this, but the general idea should work.

Hi, it tried implementing this and the `addViews` method spits an error that says `local functions are not yet supported in inline functions`. Any workarounds for this? — Dale Julian, Oct 04 '18 at 09:58
@DaleJulian Oops. The only reason I used a function was to make things more readable, you can just replace the function call by its contents (or extract it and make it `private`) — Salem, Oct 04 '18 at 10:23
thanks! But just to clarify, the `afterMeasured` method that you used here is the same as the one found here: https://antonioleiva.com/kotlin-ongloballayoutlistener/ ? — Dale Julian, Oct 12 '18 at 02:01
@DaleJulian I'm not sure, I just used that function since the OP used it (the `afterMeasured {}` part _is_ the recurring part of the function, you can replace it with anything). It doesn't have anything to do with recursive `inline` functions. — Salem, Oct 12 '18 at 07:38

SOFe · Answer 2 · 2019-02-14T14:24:17.213

You may define a function within an inline function.

inline fun <reified T> execute64(crossinline run: (Class<*>, Int) -> Unit) {
    var cnt = 0
    val x = object : Consumer<Int> {
        override fun accept(i: Int) {
            if(i > 1) {
                repeat(2) { accept(i shr 1) }
                return
            }
            run(T::class.java, cnt++)
        }
    }
    x.accept(64)
}

See this working test

Note that it does not require tail recursion, i.e. it will work even with NP-hard recursive algorithms.

Why it works:

In each call to execute64, a new anonymous class is created inline.
The anonymous class allows us to define a function inside a function.
We have an actual compiled function (not just an inline function). So we can call this function recursively without worrying about inline, because the inlined scope is outside the scope of this function.

Note:

This would result in defining a new anonymous class every time you call execute64(). So if you have 100 places in your code that call this function directly, 100 anonymous classes will be created. Your code may suffer from slow classloading. (citation needed, I am not an expert in classloading)
This method still involves calling a method recursively, and instantiates one instance every time the inline function execute64 is called (but no new instance is created during recursion). I am not sure if this inline function still enjoys the performance boost from inlining lambdas, but it certainly fixes the issue with reified.

Kotlin - How to generify recursive functions that can't be reified?

2 Answers2