Skip to content

Latest commit

 

History

History
63 lines (39 loc) · 2.86 KB

ii.9.2-generics-and-recursive-inheritance-graphs.md

File metadata and controls

63 lines (39 loc) · 2.86 KB

II.9.2 Generics and recursive inheritance graphs

[Rationale: Although inheritance graphs cannot be directly cyclic, instantiations given in parent classes or interfaces may introduce either direct or indirect cyclic dependencies, some of which are allowed (e.g., C : IComparable<C>), and some of which are disallowed (e.g., class A<T> : B<A<A<T>>> given class B<U>). end rationale]

Each type definition shall generate a finite instantiation closure. An instantiation closure is defined as follows:

  1. Create a set containing a single generic type definition.

  2. Form the closure of this set by adding all generic types referenced in the type signatures of base classes and implemented interfaces of all types in the set. Include nested instantiations in this set, so a referenced type Stack<List<T>> actually counts as both List<T> and Stack<List<T>>.

  3. Construct a graph:

    • Whose nodes are the formal type parameters of types in the set. Use alpha-renaming as needed to avoid name clashes.

    • If T appears as the actual type argument to be substituted for U in some referenced type D<…, U, …> add a non-expanding (→) edge from T to U.

    • If T appears somewhere inside (but not as) the actual type argument to be substituted for U in referenced type D<…, U, …> add an expanding (⇒) edge from T to U.

An expanding-cycle is a cycle in the instantiation closure that contains at least one expanding-edge (⇒). The instantiation-closure of the system is finite if and only if the graph as constructed above contains no expanding-cycles.

[Example:

class B<U>
class A<T> : B<A<A<T>>>

generates the edges (using ⇒ for expanding-edges and → for non-expanding-edges)

  • T → T (generated by referenced type A<T>)
  • T ⇒ T (generated by referenced type A<A<T>>)
  • T ⇒ U (generated by referenced type B<A<A<T>>>)

This graph does contain an expanding-cycle, so the instantiation closure is infinite. end example]

[Example:

class B<U>
class A<T> : B<A<T>>

generates the edges

  • T → T (generated by referenced type A<T>)
  • T ⇒ U (generated by referenced type B<A<T>>)

This graph does not contain an expanding-cycle, so the instantiation closure is finite. end example]

[Example:

class P<T>
class C<U,V> : P<D<V,U>>
class D<W,X> : P<C<W,X>>

generates the edges

  • U → X, V → W, U ⇒ T, V ⇒ T (generated by referenced type D<V,U> and P<D<V,U>>)
  • W → U, X → V, W ⇒ T, X => T (generated by referenced type C<W,X> and P<C<W,X>>)

This graph contains non-expanding-cycles (e.g. U → X → V → W → U), but no expanding-cycle, so the instantiation closure is finite. end example]