泛型

如果有一个声明，在该声明中使用尖括号声明了类型形参，那么称这个声明是泛型的。在使用泛型声明时，类型形参可以被代换为其他的类型。通过在函数签名中声明类型形参，可以定义一个泛型函数；通过在 class、interface、struct、enum、typealias 定义中声明类型形参，可以定义泛型类型。

类型形参与类型变元

在仓颉编程语言中，用标识符表示类型形参，并用<>括起。通过在<>内用,分隔多个类型形参名称，可以提供多个类型形参，如<T1, T2, T3>，T1, T2, T3均为类型形参。

一旦声明了类型形参，这些形参就可以被当做类型来使用。

当使用标识符来引用声明的类型形参时，这些标识符被称为类型变元。

类型形参的语法如下：

typeParameters
    : '<' identifier (',' identifier)* '>'
    ;

泛型约束

在仓颉语言中可以用<:来表示一个类型是另一个类型的子类型。通过声明这种关系可以对泛型类型形参声明加以约束，使得它只能被替换为满足特定约束的类型。

泛型约束通过 where 之后的<:运算符来声明，由一个下界与一个上界来组成。其中 <: 左边称为约束的下界，下界只能为类型变元。<: 右边称为约束上界，约束上界可以为类型。当一个约束的上界是类型时，该约束为子类型约束。当上界为类型时，上界可以为任何类型。

一个类型变元可能同时受到多个上界约束，对于同一个类型形参的多个上界必须使用&连接，以此来简化一个类型形参有多个上界约束的情形，它本质上还是多个泛型约束。对不同类型变元的约束需要使用,分隔。

声明约束的语法如下：

upperBounds
    :  type ('&' type)*
    ;

genericConstraints
    : 'where' identifier  '<:' upperBounds (',' identifier  '<:' upperBounds)*
    ;

例如以下示例展示了泛型约束声明的写法：

interface Enumerable<U> where U <: Bounded {...}

interface Comparable<T> {...}

func collectionCompare<T>(a: T, b: T) where T <: Comparable<T> & Seqence {...}

func sort<T, V>(input: T)
    where T <:  Enumerable<V>, V <: Object {...}

类型变元 X 和 Y 的约束相同，指的是所有满足 X 约束的类型都满足 Y 的约束，且所有满足 Y 的约束的类型也都满足 X 的约束；

类型变元 X 比 Y 的约束更严格，指的是所有满足 X 约束的类型都满足 Y 的约束，反之，不一定满足；

如果 X 比 Y 的约束更严格，则Y 比 X的约束更宽松。

两个泛型类型的约束相同，指的是泛型类型的类型变元数量相同，且所有对应的类型变元约束均相同；

一个泛型类型 A 的约束比另一个泛型类型 B 的约束更严格，指的是 A 和 B 的类型变元数量相同，且 A 的所有类型变元的约束均比 B 中对应的类型变元更严格；

一个泛型类型 A 的约束比另一个泛型类型 B 的约束更严格，则 B 的约束比 A 更宽松。

比如下面的两个泛型 C 和 D ，假设有 I1 <: I2，C 的约束比 D 更严格：

class C<X, Y> where X <: I1, Y <: I1 和 class D<X, Y> where X <: I2, Y <: I2

类型型变

在正式介绍泛型函数与泛型类型前，先简单介绍以下类型型变，以此来说明在仓颉编程语言中，泛型类型的子类型关系。

定义

如果 A 和 B 是类型，T 是类型构造器，设其有一个类型参数 X，那么：

  • 如果 T(A) <: T(B) 当且仅当 A <: B，则 T 在 X 处是协变的。
  • 如果 T(A) <: T(B) 当且仅当 B <: A，则 T 在 X 处是逆变的。
  • 如果 T(A) <: T(B) 当且仅当 A = B，则 T 是不型变的。

泛型不型变

在仓颉编程语言中，所有的泛型都是不型变的。这意味着如果A是B的子类型，ClassName<A>和ClassName<B>之间没有子类型关系。我们禁止这样的行为以保证运行时的安全。

函数类型的型变

函数的参数类型是逆变的，函数的返回类型是协变的。假设存在函数f1的类型是S1 -> T1，函数f2的类型是S2 -> T2。如果 S2 <: S1 并且T1 <: T2，则f1的类型是f2的类型的子类型。

元组类型的协变

元组之间是存在子类型关系的，如果一个元组的每一个元素都是另一个元组的对应位元素的子类型，则该元组是另一个元组的子类型。假设有元组 Tuple1 和 Tuple2，它们的类型分别为 (A1, A2.., An)、(B1, B2.., Bn)，如果对于所有 i 都满足 Ai <: Bi，则 Tuple1 <: Tuple2。

型变的限制

现在以下两种情况的型变关系被禁止：

  1. class 以外的类型实现接口，该类型和该接口之间的子类型关系不能作为协变和逆变的依据。
  2. 实现类型通过扩展实现接口，该类型和该接口之间的子类型关系不能作为协变和逆变的依据。

这些限制除了影响型变关系以外，同时也会影响 override 对于子类型的判定。

不满足型变关系的类型，在发生 override 时不能作为子类型的依据。

interface I {
    func f(): Any
}
 
class Foo <: I {
    func f(): Int64 { // error
        ...
    }
}

泛型约束上界中导出的约束

对于一个约束 L <: T<T1..Tn>，其中的上界 T<T1..Tn> 的声明T的类型形参可能还需要满足一些约束，在实参 Ti 的代换后，这些约束需要被隐式地引入到当前声明的上下文中。例如：

interface Eq<T> {
	func eq(other: T): Bool
}

interface Ord<T> where T <: Eq<T> {
	func lt(other: T): Bool
}

func foo<T>(a: T) where T <: Ord<T> {
	a.eq(a)
	a.lt(a)
}

对于 foo 函数，虽然只声明了 T 受到 Ord 的约束，但是由于 Ord 的 T 类型受到了 Eq 的约束，所以在 foo 函数里是可以使用 Eq 中的 eq 函数的。这样，foo 函数的约束实际上是 T <: Eq & Ord。这样在声明一个泛型参数满足一个约束时，这一约束的上界中需要满足的约束也将被引入。

对于其他泛型声明，隐式地引入约束上界的约束这一规则也是有效的。例如：

interface A {}
class B<T> where T <: A {}
class C<U> where U <: B<U> {} // actual constraints are U <: A & B<U>

这里，对于类C，它的泛型形参 U 所受到的约束实际上为 U <: A & B<U>。

注意：虽然当前声明中上界的约束会被隐式地引入，但当前声明仍然可以将这些约束显式地写出。

泛型函数与泛型类型的定义

泛型函数

如果一个函数声明了一个或多个类型形参，则将其称为泛型函数。语法上，类型形参紧跟在函数名后，并用<>括起，如果有多个类型形参，则用,分离。

func f<T>() {...}
func f1<T1, T2, T3, ...>() {...}

泛型函数的语法如下：

functionDefinition
    : functionModifierList? 'func' identifier
    typeParameters functionParameters
    (':' type)? genericConstraints?
    block?
    ;

需要注意的是：

  • <与>在使用时，会优先解析为泛型，如果成功，则直接就是泛型表达式，否则才为比较运算符，例如：
(c <d , e> (f))

这一表达式会被解析为函数调用表达式。

泛型类型

如果一个 class、interface、struct、enum、typealias 的定义中声明了一个或多个类型形参，则它们被称为泛型类型。语法上，类型形参紧跟在类型名（如类名、接口名等）后，并用<>括起，如果有多个类型形参，则用“,”分隔。

class C<T1, T2> {...}	// generic class
interface I<T1> {...}	// generic interface
type BinaryOperator<T> = (T, T) -> T	// generic typealias

对于泛型声明定义的语法可以参考相应的章节。

泛型类型检查

泛型声明的检查

泛型约束的健全性检查

对一个声明的所有类型形参，其每个形参的约束上界可以分为两种情况：

  1. 上界也是类型变元，这个类型变元可能是它本身，也可能是其他的类型变元

  2. 上界为具体类型时，可以分为两种情形：

    • 第一种情形是上界 class 与 interface 类型时，称为类相关类型。

    • 第二种情形是上界为除 class 与 interface 类型以外的类型，这些称为类无关类型

    在仓颉语言中，对于一个类型变元的一个或多个具体类型上界需要满足如下规则：

    1. 所有的约束上界只能属于同一种情形，即要么上界都是类相关类型，要么是类无关类型。例如：T <: Object & Int32不合法。

    2. 当上界是类相关类型时，如果存在多个类的上界，那么这些类需要在同一个继承链上，对于接口没有此限制。一个类型变元的多个泛型上界中不允许包含冲突的成员定义，具体来说，冲突指同名函数或相同操作符之间不构成重载，并且返回类型之间不具有子类关系。

    3. 当上界是类无关类型的情形时，只能包含一种类无关的具体类型。不能同时为两个不同的具体类型。例如：T <: Int32 & Bool 不合法。

    4. 类型变元上界为类无关类型的情形时不能存在递归约束。递归泛型约束是上界类型实参直接或间接依赖于下界类型变元自身的约束。例如：T <: Option<T>，由于Option是通过enum关键字声明的，所以此种递归泛型约束不合法。T <: U, U <: (Int32) -> T 也不合法，因为函数是值类型，T类型间接地通过U依赖了自身。

类型兼容性检查

对于泛型声明的类型的检查主要是检查泛型类型与其所在的类型上下文中是否兼容，对于成员函数、变量的访问是否合法，例如：

open class C {
    func coo() {...}
}

class D <: C {...}

interface Tr {
    func bar(): Int64
}

func foo<T>(a: T) {
    var b: C = a // error, T is not a subclass of C
    a.coo() // error, T has no member function coo
    a.bar() // error, T did not implement Tr
}

在上述示例代码的foo的函数体中共有 3 处报错，原因分别如下：

  1. 由于foo函数中声明的变量b的期望的类型是C，所以这里需要检查T是否是D的子类型，即T <: C，而这一约束不存在于T的上下文中，所以变量声明处编译报错。

  2. 由于泛型类型T在当前上下文与C无关，所以也不能访问C的成员函数coo。

  3. 类似地，由于 T 类型的不存在 Tr 的约束，所以也不能访问 Tr 的成员函数 bar。

如果想要通过类型检查需要在声明体前加入泛型约束：

open class C {
	func coo() {...}
}

interface Tr {
    func bar(): Int64
}

func foo<T>(a: T) where T <: C & Tr {
	var b: C = a // OK, T is a sub type of C now
	a.coo() // OK, T is a sub type of C, so it has coo member function
	a.bar() // OK, T is constrained by Tr
}

特别地，如果一个类型变元 T 的泛型上界包含一个函数类型或重载了函数调用操作符 () 的类型，则类型为 T 的值可以被作为函数调用。当上界为函数类型时，该调用的返回类型为 T 的上界的返回类型，当上界为重载了函数调用操作符 () 的类型时，该调用的返回类型为上界类型中匹配的函数调用操作符的返回类型。

泛型声明使用的检查

对于泛型声明的使用检查主要是将实参代入到泛型声明的形参，然后检查约束是否成立。

如果我们直接用C类型调用上一小节中定义的foo函数：

main(): Int64 {
	foo<C>(C()) // error C does not implement Tr
	return 0
}

那么会得到类型C没有实现 Tr的错误，这是因为在foo函数的约束中有T <: C & Tr，其中的形参T会被代替为C，首先C <: C成立，但是C <: Tr不成立。

如果为C类型加入了实现Tr的声明，那么就可以满足T <: Tr这一约束：

extend C <: Tr {
	func bar(): Int64 {...}
}

特别的是，当 interface 作为泛型约束时，调用时泛型变元实例化的类型必须完全实现所有上界约束中的 interface static 函数。

意味着如果作为泛型约束的 interface 中存在 static 函数，就无法将未实现对应 static 函数的 interface 或抽象类作为泛型变元实例化的类型。

interface I {
    static func f(): Unit
}

func g<T>(): Unit where T <: I {}

main() {
    g<I>() // error
    return 0
}

泛型实例化的深度

为保证泛型实例化不会出现死循环或耗尽内存，在编译过程中会对实例化的层数做出限制。例如：

class A<T>{
    func test(a: A<(A<T>, A<T>)>): Bool {true}
}

main(): Int64 {
    var a : A<Int32> = A<Int32>()
    return 0
}

这段程序会报 infinite instantiation 的错误。

泛型实例化

一个泛型声明在所有类型形参的取值都确定之后形成一个对应的非泛型语言结构的过程称之为泛型声明的实例化。

泛型函数的实例化

func show<T>(a: T) where T <: ToString {
    a.toString()
}

在给定T = Int32的取值之后会形成这样的实例（这里假定show$Int32是编译器实例化后的内部表示，后面也会使用类似的表示）：

func show$Int32(a: Int32) {
    a.toString()
}

实例化泛型函数的限制

在仓颉语言中，以下情形不能声明泛型函数：

  1. 接口与抽象类中的非静态抽象函数
  2. 类与抽象类中被 open 关键字修饰的实例成员函数
  3. 操作符重载函数

例如，以下函数的声明与定义都是不合法的：

abstract class AbsClass {
	public func foo<T>(a: T): Unit // error: abstract generic function in abstract class
	public open func bar<T>(a: T) { // error: open generic function in abstract class
		...
	}
}

interface IF {
	func foo<T>(a: T): Unit // error: abstract generic function in interface
}

open class Foo {
	public open func foo<T>(a: T): Unit { // error: open generic function in class
    	... 
    } 
}

而以下的泛型函数是合法的：

class Foo {
	static func foo<T>(a: T) {...} // generic static function in class
	func bar<T>(a: T) {...} // generic non-open function in class
}

abstract class Bar {
	func bar<T>(a: T) {...} // generic non-open function in abstract class
}

struct R {
	func foo<T>(a: T) {...} // generic function in struct
}

enum E {
    A | B | C
    func e<T>(a: T) {...} // generic function in enum
}

类与接口的实例化

class Foo<T> <: IBar<T>{
    var a: T
    init(a: T) {
        this.a = a
    }
    static func foo(a: T) {...}
    public func bar(a: T, b: Int32): Unit {...}
}

interface IBar<T> {
    func bar(a: T, b: Int32): Unit
}

在给定T=Int32 时会生成以下实例的声明：

class Foo$Int32 <: IBar$Int32 {
    var a: Int32
    static func foo(a: Int32) {...}
    func bar(a: Int32) {...}
}

interface IBar$Int32 {
    func bar(a: Int32, b: Int32)
}

struct 的实例化

结构体的实例化与类的实例化十分类似。

struct Foo<T> {
    func foo(a: T) {...}
}

当给定T=Int32时会生成以下实例的声明：

struct Foo$Int32 {
    func foo(a: Int32) {...}
}

Enum 的实例化

enum Either<T,R> {
      Left(T)
    | Right(R)
}

当Either被给定参数Int32与Bool时，类型在被实例化后得到：

enum Either$Int32$Bool {
	  Left(Int32)
 	| Right(Bool)
}

在使用一个泛型声明时，例如调用泛型函数、构造泛型类型的值等，在编译时实际发生作用的都是确定类型形参后的实例，也就是说只有当所有泛型参数都为具体类型后才会发生实例化。

泛型函数重载

在仓颉编程语言中，支持泛型函数之间的重载，也支持泛型函数与非泛型函数之间的重载，重载的定义详见[函数重载]。

函数调用时，重载的处理过程如下：

第一步：构建函数调用的候选集，最终进入候选集的函数均为通过类型检查可以被调用的函数，详见[重载函数候选集]，在构建候选集时，对于泛型函数有额外的规则，下面会详细介绍；

第二步：根据作用域优先级规则（详见 [作用域优先级]）和最匹配规则（详见 [最匹配规则]）选择最匹配的函数，如果无法确定唯一的最匹配函数，则报无法决议的错误；

第三步：如果实参类型有多个，根据最匹配函数确定实参类型，如果不能确定唯一的实参类型，则报错。

构建函数调用的候选集时，对于泛型函数需要注意以下几点：

1、在函数调用时，对于泛型函数f，进入候选集的可能是部分实例化后的泛型函数或是完全实例化的函数。具体是哪种形式进入候选集，由调用表达式的形式决定：

  • 调用表达式的形式为：C<TA>.f(A)，即f为某个泛型类型的静态成员函数，先对类型进行实例化；再对实例化后类型的静态成员函数进行函数调用的类型检查，如果能通过则进入候选集。假设C的类型形参为X，则进入候选集的函数是将f中X代换成TA之后的f':

    $$ \sigma = [X \mapsto TA] $$ $$ f' = \sigma f $$

    // The context contains the following types: Base, Sub, and Sub <: Base.
class F<X> {
   static func foo<Y>(a: X, b: Y) {}  // foo1
   static func foo<Z>(a: Sub, b: Z) {}  // foo2   
}

/* The functions that enter the candidate set are foo1 and partial instantiated  foo2: foo<Y>(a:Base, b: Y) and foo<Z>(a: Sub, b: Z) */
var f = F<Base>.foo(Sub(), Base())  // foo2

  • 调用表达式的形式为：obj.f(A)，且obj为泛型类型实例化类型的实例，即f为某个泛型类型的非静态成员函数。

    在该表达式中obj的类型需要先确定，再根据obj的类型来获取候选集函数。obj的类型是实例化后的类型，也是将实例化后的类型的非静态成员函数进行函数调用的类型检查，通过类型检查的进入候选集。

    // The context contains the following types: Base, Sub, and Sub <: Base.
class C<T, U>{
    init (a: T, b: U) {}
    func foo(a: T, b: U) {}     // foo1
    func foo(a: Base, b: U) {}   // foo2
}

/* It is inferred that the type of obj is C<Sub, Rune>.
   The functions that enter the candidate set are instantiated foo1, foo2:   
   foo(a:Sub, b:Rune) and foo(a: Base, b: Rune)
 */
main() {
    C(Sub(), 'a').foo(Sub(), 'a')   // choose foo1
    return 0
}

2、如果函数调用时未提供类型实参，也就是函数调用的形式为：f(a), 则要求进入候选集的泛型函数f满足以下要求：

  • 如果f是泛型函数，其形式为：f<X_1,...,X_m>(p1: T_1, ..., pn: T_n): R，调用表达式中未提供类型实参，形式为f(a_1, ..., a_n)， f可以根据实参的类型(A1,...,An)能推断出一组类型实参TA_1,...,TA_m，满足f的所有泛型约束，且将f中的X_1,...,X_m分别代换成TA_1,...,TA_m，能通过函数调用的类型检查，检查规则如下：

    • 将推断出的类型实参TA_1,...,TA_m代换到f的函数形参(T1,...,Tn)后，满足在调用表达式所在的上下文中(A1,...,An)是代换后形参类型的子类型：

      $$ \sigma = [X_1 \mapsto TA_1, ..., X_m \mapsto TA_m] $$ $$ \Delta \vdash (A1, ..., An) <: \sigma (T_{1},...,T_{n}) $$

    • 如果调用表达式中提供了返回类型RA，则需要根据返回类型进行类型检查，将f的返回类型R中的X_1,...,X_m分别代换成TA_1,...,TA_m后，满足在调用表达式所在的上下文中代换后的返回类型是RA的子类型。

$$ \sigma = [X_1 \mapsto TA_1, ..., X_m \mapsto TA_m] $$ $$ \Delta \vdash \sigma R <: RA $$

3、如果函数调用时提供了类型实参，也就是函数调用的形式为：f<TA>(a), 则要求进入候选集的f满足以下要求：

  • f的类型形参与TA的数量相同，且类型实参TA满足f的泛型约束，且类型实参代入之后能通过函数调用的类型检查规则