Resolution of links to extensions in KDoc

[whyoleg]

This is an issue to discuss Resolution of links to extensions in KDoc. The full text of the proposal is here.

During the migration of Dokka analysis to K2, several questions arose around KDoc links resolution.
In particular, it was unclear how a link to an extension should be resolved in the presence of type parameters.
Link resolution in KDoc is not fully specified, and for this reason some cases are currently implemented
differently in K1 and K2 analysis.

The goal of the proposal is to try to describe consistent rules on how KDoc links to extensions should be resolved.

[CLOVIS-AI]

I'm not sure this is on-topic for this KEEP, but I'd very much like to see a way to disambiguate links of different things that have the same name. For example, when a class and a top-level function exist, it is not currently possible to create a link that refers to one of them specifically. Unlike regular function overloads, which are all listed on the same page, so the disambiguation isn't particularly needed, homonyms on different pages hinder the documentation quality at the moment.

[whyoleg]

Hey @CLOVIS-AI, this is known and tracked in https://youtrack.jetbrains.com/issue/KT-19765/KDoc-Provide-ability-disambiguate-links-to-classes-vs-links-to-functions
Feel free to add a use-case there.

[marcopennekamp]

If Type has type parameters, e.g interface Container<T, C: Iterable<T>>, then the link should be resolved if it's possibly to substitute them with some concrete types in callable reference

We should describe the substitution more precisely. The definition here is quite mathematical (as opposed to algorithmic), which has the problem that the search space might be very large. When the compiler compiles a callable reference in code, the reference already has its type arguments set. Hence, it's quite easy to check them against the expected type parameters. On the other hand, a type reference in KDoc does not have its type arguments set. So there needs to be another mechanism to match the type reference against the extension function's extension receiver.

To make sure that there can be a proper and well performing implementation, I think the KEEP should describe the algorithm which matches the type references against the declared extension receiver.

(Maybe I got a bit carried away, but what follows is my attempt at such an algorithm.)

Naive instantiation

Let's say we have an extension function KDoc reference Type.extension with Type<A_0, A_1, ..., A_N>.

For covariant type parameters out A_x : U_x, it would be tempting to take the upper bound U_x as the type argument's instantiation, but this is not correct:

interface Animal
class Cat : Animal

class Type<out A : Animal>

fun Type<Cat>.extension() { }

/** [Type.extension] */
fun documented() { }

If we instantiate Type<Animal> for Type in Type.extension, the reference will be unresolved because Type<Animal> is not a subtype of Type<Cat> (and in general, the extension receiver has to be a subtype of the declared extension receiver).

The crucial point, as the proposal notes, is that the type parameter can be substituted with some concrete type to make the receiver type fit. So there is some instantiation of A which allows Type<A> to be a subtype of Type<Cat>.

Possible approach

I wonder if the following approach suffices. First, let's assume we have the following code:

interface T<A_0, A_1, ..., A_TN>

class S<B_0, B_1, ..., B_SN> : T<...> // Not pictured: Indirect inheritance.

fun T<E_0, E_1, ..., E_I>.extension() { }

/** [S.extension] */
fun documented() { }

We check that S.extension is a valid reference with the following algorithm:

• From S<B_0, B_1, ..., B_M>, derive the supertype instantiation T<Z_0, Z_1, ..., Z_K> according to the inheritance relationship.
  • Any Z_x will either be a type parameter type from S<B_0, B_1, ..., B_M>, or a concrete type from a regular type argument along the way to the supertype.
• Compare T<Z_0, Z_1, ..., Z_K> against T<E_0, E_1, ..., E_I>, finding whether each type argument E_x matches with the type Z_x:
  • If both Z_x and E_x are concrete types, check that Z_x is a subtype of E_x according to the variance of the type parameter at the position. Invariant type arguments must be equal.
  • If only E_x is a concrete type, check that E_x fits into the bounds of Z_x. If E_x does not fit the bounds of Z_x, we cannot find an instantiation of Z_x which satisfies E_x.
  • If only Z_x is a concrete type, check that Z_x fits into the bounds of E_x. If Z_x does not fit the bounds of E_x, the extension receiver type T<E_0, E_1, ..., E_I> has a type parameter which is too specific to accept the subtype's type argument at the same position. Hence, S cannot subtype T<E_0, E_1, ..., E_I> specifically.
    • Note that such a type parameter comes not from T but rather from the extension function or its containing class. So it is possible to restrict the bounds of E_x so much that a subtype S of T would instantiate a type for the type parameter which is too broad.
  • Otherwise, if both types are type parameter types, check that the bounds of Z_x and E_x overlap. That is, there must be at least one type which can be an instantiation of both Z_x and E_x.
  • In general, the important idea is that the bounds of Z_x and E_x overlap. Only when this is the case can we find an instantiation of Z_x which can also be an instantiation of E_x. Conceptually, we can view a concrete (non-type parameter) type t as a type parameter with a lower and upper bound of t, so this idea applies even in the cases where we have one or two concrete types on either side.
  • Unless we are dealing with concrete types on both sides, covariance and contravariance do not need to be taken into account. Variance is concerned with subtyping of two types when their type arguments have concrete instantiations (e.g. Type<Cat> <: Type<Animal>), but here we are concerned with finding a common instantiation of two type parameters (e.g. Type<X> and Type<Y>). As long as the bounds overlap, we can instantiate both type parameters to the same type argument, making the variance unimportant (all type parameters could be invariant).
• If all Z_x match with their respective E_x, the types are compatible.
• If S inherits from T through multiple paths, we may have to derive multiple instantiations of T which need to be checked against the KDoc reference type.
  • Essentially, S will be a subtype of the intersection of multiple instantiations of T.

The description might not be complete, but it may be a direction to go in. Or maybe there are other similar approaches somewhere in the compiler or language specification.

Example

interface Animal
class Cat : Animal

interface Shape
class Ball : Shape

interface Container<out A, X, Y>
class AnimalContainer<out AC_A : Animal, out AC_X : String> : Container<AC_A, AC_X, String>
class ShapeContainer<out SC_A : Shape, out SC_X : Int> : Container<SC_A, SC_X, Int>

fun <FUN_X : String> Container<Cat, FUN_X, String>.extension() { }

For the KDoc reference AnimalContainer.extension:

• On the KDoc reference side, derive Container<AC_A, AC_X, String> from AnimalContainer<AC_A, AC_X>.
• On the extension receiver side, we have Container<Cat, FUN_X, String>.
• Check each type argument for compatibility (Container<AC_A, AC_X, String> against Container<Cat, FUN_X, String>):
  • AC_A can be instantiated with Cat.
  • AC_X can be instantiated with the same type as FUN_X since their bounds overlap.
  • String is equal to String (and should be because the type parameter in this position is invariant).
• So AnimalContainer.extension is a valid reference.

For the KDoc reference ShapeContainer.extension:

• On the KDoc reference side, derive Container<SC_A, SC_X, Int> from ShapeContainer<SC_A, SC_X>.
• On the extension receiver side, we have Container<Cat, FUN_X, String>.
• Check each type argument for compatibility (Container<SC_A, SC_X, Int> against Container<Cat, FUN_X, String>):
  • SC_A CANNOT be instantiated with Cat.
  • SC_X CANNOT be instantiated with the same type as FUN_X since their bounds DO NOT overlap (Int vs. String).
  • Int is not equal to String (but it should be because the type parameter in this position is invariant).
• So ShapeContainer.extension is not a valid reference.