前两天在看Twitter的Effective Scala的时候，看到了一些关于类型协变性的讨论。
之前虽然断断续续的看过一些讲协变性的文章，不过感觉果然还是没搞清楚呢……
于是花了一个晚上和半个早上的时间整理了一篇学习笔记，也算是了解了怎么回事。
// Type system is indeed interesting :-)
Update 2016.11.3：在学完Kotlin以后添加了关于Type Projection的小节。
What’s Variance
首先，变性（Variance）是什么？简单的来说，它是用来处理复合类型的类型转换的一些规则。
常见的复合类型有数组和泛型类。当我们在讨论类似这样的问题：
List<EntityPlayer>是否能被转型成List<Entity>？- 一个
Object[]的引用是否能接受一个String[]类型的引用？
的时候，我们就在讨论复合类型的变性。
通常来说，变性分类为以下三种（假设 ASub 是 A 的子类）：
- 协变性 (Covariance)：
List<ASub>是一个List<A>，反之不成立。 - 逆变性 (Contravariance):
List<A>是一个List<ASub>，反之不成立。 - 不变性 (Invariance)：
List<ASub>不是一个List<A>，List<A>也不是一个List<ASub>。
这里的” A 是 B “的意思是：一个 B 类型的引用可以接受一个 A 类型的引用。可以通俗的理解为A 是 B 的子类。简单的来说，协变保持了类型参数的继承关系；逆变则逆转了类型参数的继承关系。
数组的协变性
在java中，数组是协变的：
String[] strList = new String[] { "233", "2333", "233333" };
Object[] objList = strList;
你可以把一个 String[] 转型为一个 Object[] 而不得到任何编译期错误，你也可以正常的通过这个
引用访问原数组的元素。
然而，当你尝试往objList里加入一些奇怪的东西的时候：
objList[0] = new Punk();
> Exception in thread "main" java.lang.ArrayStoreException
抛出了一个异常，因为你无法向一个存放String的数组里存放一个其他类型的元素。
数组的协变是类型不安全的。实际上，这是当初java语言设计上的失误。由于一开始的java没有泛型，
然而又想引入一些方法来对数组进行通用的操作，怎么办呢？只好全部把它们upcast成 Object[]。
即便在有了泛型之后，为了保持代码的向前兼容，数组还是可以协变。
协变和逆变
由上面数组协变的例子，我们可以看到，如果一个复合类型是协变的，并且你尝试对里面的状态进行更改，
就会出现类型不安全的问题。把协变的规则搬到另外一个场景看一下：
interface IContainer<T> {
void add(T element);
}
假如IContainer的参数类型T是协变的，我们就可以写出
IContainer<String> c1 = ...;
IContainer<Object> c2 = c1;
c2.add(new Punk());
和数组时候的情况一模一样。
这里的问题在于，实际上 IContainer<String>.add 方法接受的是一个String类型的参数。通过协变，我们
绕开了该方法对于类型的限定，从而导致了类型不安全。对于数组，我们可以想象有一个 set(int index, T value)
方法处于同样的困境中。
因此，我们可以得出如下结论：如果一个类型参数出现在方法的参数中，那么这个类型参数必须不能是协变的。
再看接下来的另外一种情况：
interface Iterator<T> {
bool hasNext();
T next();
}
这个接口容许协变。将一个 Iterator<EntityPlayer> 转型为一个 Iterator<Entity> ，我们通过next() 方法得到的是一个Entity对象，这的确合乎常理。
从 Iterator 接口和的观察我们可以得出：对值的观察(observation) 或将值作为函数的返回值返回的
情况下，类型参数的协变是安全的。
对协变的情况讨论完了，接下来我们讨论一下逆变 (Contravariance) 。逆变本身其实是比较反直觉的。假如一个类型参数是逆变的，那么 SomeType<String> 就可以接受 SomeType<ObjecT>。在面向对象的世界，
这意味着 SomeType<Object> 可以被看作是 SomeType<String>的子类！
不过，如果把 IContainer 和 Iterator 的例子在支持逆变的情况下再讨论一次，就会发现逆变有它的存在价值，来试试吧：
首先，对于 IContainer<T>，可以逆变意味着可以让 IContainer<String> 接受IContainer<Object>。当你调用 add 方法时，你往里面加入的是一个 String 对象，
而这对 IContainer<Object> 是完全安全的！
接下来，对于 Iterator<T>，可以逆变意味着可以让 Iterator<EntityPlayer> 接受Iterator<Entity>。当你调用 next 方法时，你总是期望得到一个 EntityPlayer 类型的参数，但是现在却有可能得到一个在继承层次上一级的 Entity 对象。这是类型不安全的。
可以看到，协变和逆变在各个情况下的类型安全问题恰好相反。可以列表归纳如下：
类型 | 作为函数参数 | 作为函数返回值
协变 | 不安全 | 安全
逆变 | 安全 – | 不安全
不变 | 安全 – | 安全
常见的强类型带泛型的语言（e.g. C#, Java, Scala）通常允许程序作者指定类型参数的变性，
并且通过检查变性的限制条件来保证代码的（编译时）类型安全。我们在下面就讨论一下这些语言指定变性的方法。
Use-site variance 和 Declaration-site variance
指定类型参数变性的方法有两种：在类声明时指定 (Declaration-site) 或在创建实例，
即使用类时指定 (Use-site)。在 C# 和 Scala 中用的是第一种方法，而 Java 中用的是第二种方法。
类声明时的变性
下面这段Scala代码示范了声明时变性的用法：
trait Box[-A] {
def insert(element: A)
}
val boxOfObject: Box[AnyRef] = ...
val boxOfString: Box[String] = ...
// 因为A是逆变参数，Box[String]是Box[AnyRef]的子类，转型可以发生
val boxOfString2: Box[String] = boxOfObject
在 Scala 中，通过在类型参数前加上 + 来代表协变参数， - 代表逆变参数。在 C# 中，对应的关键字
则是 out 和 in （这非常有意思，正好对应了我们之前对读写操作和类型安全性的讨论）。
Use-site variance
特立独行的Java使用的是 Use-site variance，即让类的使用者决定一个类实例的变性。变性的指定通过
泛型通配符 (Wildcard) 进行。例如：
List<? extends Entity>代表一个类型参数为Entity的协变列表。List<? super EntityPlayer>代表一个类型参数为EntityPlayer的逆变列表。List<?>是List<? extends Object>的简写。
为了保证类型安全，相应的有如下限制：
- 使用
? extends通配符的协变类型，不允许调用任何以本类型参数作为参数的方法。 (e.g. add) - 使用
? super通配符的协变类型，不允许调用任何以本类型参数作为返回值的方法。(e.g. getValue)
类型通配符实际很容易和类型边界(Type bounds)搞混，但是它们实际上是完全不同的概念：
void <T extends Action> applyAction(Entity target, T action);
这里说的是这个泛型参数T只接受可以任何Action类的子类型作为实际参数。在知道这一点的前提下，
我们可以对T类型的引用调用Action类里定义的所有公有方法。
Sidenote: C++里的协变
C++里面，通常来说不存在类型的逆变和协变。例如，std::vector<Entity> 和 std::vector<EntityPlayer>
之间是完全无法相互转换的（在引用的意义上）。毕竟在C++里面，“泛型”的概念并不存在，取而代之的是模板和模板实例化。
在模板支持特例化和重载，并且在实例化时验证代码的情况下，实际上并不需要这样的转换。逆变和协变的概念通常在使用真泛型、比较强调引用概念的强类型语言中比较有用。
不过，C++支持返回类型的协变。
struct A {
virtual void test() {
std::cout << "A::test" << std::endl;
}
}
struct ASub : public A {
void test() override {
std::cout << "ASub::test" << std::endl;
}
}
struct B {
virtual A& getA() { return A(); }
}
struct BSub : public B {
ASub& getA() override { return ASub(); }
}
不过，这种协变应该仅限于指针和引用类型。对于复合类型的协变（e.g. std::unique_ptr<A>）就无能为力了。
Sidenote 2: Kotlin的Type projection
保证协变和逆变安全的规则可以简单概括为：读协变，写逆变，同时读写只能不变。这样就引来了一个问题：如果在特定的上下文里，我只想对一个泛型类进行读/写，不能够对其进行泛型的处理。
例如，我有一个List<Object>和一个List<String>，我想同时往它们里放入String：
fun putStrings(target: List<String>) {
target.add("233")
target.add("466")
}
val list1 = ArrayList<Object>()
val list2 = ArrayList<String>()
putStrings(list2) // success
putStrings(list1) // fail!
某种程度上，也是由于这个严重的问题，java才不得不对数组进行协变，从而导致了类型不安全。
Kotlin使用了叫做Type projection的trick来解决这个问题，其规则很简单：在函数参数的泛型参数类型前加上in或out标记。如果加上in标记，则方法内部只允许调用该对象关于泛型参数的写方法；如果加上out标记，则方法内部只允许调用相关的读方法。这样，就可以对本来不变的类型进行协变或者逆变了。
对于上面的例子，编译成功的代码为：
fun putStrings(target: List<in String>) { // Type projection rocks!
target.add("233")
target.add("466")
}
val list1 = ArrayList<Object>()
val list2 = ArrayList<String>()
putStrings(list2) // success
putStrings(list1) // success!
顺便一说，Kotlin的docs对泛型的解释是我看到的所有教程里最清楚的，有时间可以专门看看哈哈哈
小结
变性是复合类型处理类型转换的一套规则。总的来说，变性的各种规则都是为了保证在使用泛型对象时的类型安全。具体的来说，也就是对函数传入参数和返回值的类型安全。
为了保证类型安全，在不需要修改对象的时候，泛型参数可以协变；在不需要观察对象的时候，泛型参数可以逆变。在观察和修改两种操作同时存在的情况下，泛型参数必须是不变的。
参考
Wikipedia - Covariance and contravariance (computer science)