Rust for Rustaceans: Idomatic Programming for Experienced Developers Chap.2 Types-摩杜云开发者社区

翻译的内容如果有不理解的地方或者是其他的差错，欢迎后台回复讨论。

类型在内存中的表示

Rust中的每一个值都有自己的类型(Type)。在这一章中，我们将会看到Rust中的类型服务于许多不同的目的，但其中最基本的一个目的是告诉你如何翻译并理解内存中的比特。举例来说，比特串0b10111101(十六进制下为0xBD)本身并不能携带任何信息，只有当你赋予它一个特定的类型时它才有了含义：如果我们以u8为类型来翻译这一串比特，那么它代表着数字189；如果以i8为类型来翻译，那么它的含义变为了数字-67。当你定义自己的类型时，编译器将负责决定如何在内存中表示该类型的各个部分。你所定义的结构体(Struct)中的各个字段(field)将会分别出现在比特串中的哪些部分？你的枚举类型中的各个判别值(discriminant)存储在什么地方？想要开始编写进阶的Rust代码，我们非常有必要先理解这些过程是如何工作的，因为这些过程的细节同时影响着你的代码的正确性和性能。

对齐(Alignment)

在我们讨论如何决定类型在内存中的表示形式之前，我门首先需要来讨论对齐(alignment)的概念，这一概念决定了代表某一类型的字节可以被存储的位置。一旦决定了一个类型的表示方法，你也许觉得你可以把它保存在内存中的任意位置，并在随后将该位置的字节按照事先决定的方式翻译为具体的类型。从理论层面来讲，这样的做法是对的，但是从实践的层面来看，硬件也在限制某一类型在内存中可以被放置的位置。为了说明这一点，一个最显而易见的例子是我们的指针通常指向字节，而不是比特。如果你把一个类型T放置在内存中的第四个比特的位置，你将没有办法来引用这一位置；你只能创建一个指向字节0或是字节1的指针。出于这个理由，所有类型的值都必须被放置在一个成倍于8比特的位置。

某些值有着比起按字节对齐(byte-aligned)更为严格的对齐规则。在CPU和内存系统中，内存通常是以块的形式获取的，而每一个块的大小往往超过单个的字节。举例来说，在一个64位的CPU上，大部分的值都是以一个大小为8字节(64比特)的大小的块的形式读取的，同时每一个操作都是起始于一个八字节对齐的地址处。这在CPU中被称为单字大小(word size)。除此之外，CPU会采用一些聪明的技巧来处理一些更小的值和那些跨越了块边界的值。

如果可以的话，你总是希望确保硬件可以以原生的对齐形式来执行各种操作。如果不这样做的话，你可以考虑一种从一个8字节块的中间读取i64类型的情况（也就是说，该指针指向的地址没有按照8字节对齐）。此时该硬件不得不做两次读取，一次读取第一个内存块的后半来获取i64的前半部分，第二次读取第二个内存块的前半来获取i64的后半部分——随后将这两个结果拼接在一起。这种做法的效率不高。同时，考虑到这个加载操作包含了两次内存读取，如果在执行的过程中还有另一个线程并发地写入这一段内存，你有可能会得到一个非常怪异的结果——比如i64的前半部分来自于线程写入前，而后半部分来自于线程写入后。

操作那些没有被对齐的数据通常被称作是一次未对齐的访问(misaligned access)，这种做法会带来糟糕的性能和讨人厌的并发问题。处于这个理由，许多CPU操作要求，或者强烈地倾向于接受经过合适对齐的内存地址作为参数。一种合适的对齐是当某一个值按照它自身的大小为标准进行对齐时。比如，对于一次8字节的加载操作，提供为参数的地址需要按照8字节对齐。

考虑到对齐的内存访问通常更快并且提供了更强的一致性语义，编译器会尽可能地利用这一优势。具体来说，编译器会根据每一个类型所包含的类型来赋予它需要对齐的大小。内建的类型往往都会根据它们自身的大小进行对齐，比如u8是单字节对齐的，u16是双字节对齐的，u32是四字节对齐的，而u64是8字节对齐的。一些更复杂的类型（内部包含了其他类型的类型）通常会被赋予它们所包含的类型中最大的一个子类型的对齐大小。举例来说，一个包含u8，u16，和u32的类型将会是四字节对齐的，因为其中u32具有最大的对齐大小。

布局(Layout)

既然你已经了解了对齐，我们就可以开始探索编译器是如何决定内存中表示的了，也就是一个类型的布局(Layout)。你很快就会看到，在默认设定下，Rust编译器几乎没有给出任何对类型布局的保证，这也使得理解Rust类型布局以及其背后的原理这件事变得无从下手。幸运的是，Rust提供了一种repr属性(attribute)，你可以将这种属性添加在类型定义之前来要求Rust编译器对该类型采取特殊的内存表示。在实际的代码中，你最常见到的一种是repr(c)。顾名思义，Rust编译器会将拥有这种属性的类型按照C/C++编译器的标准进行布局。在借助Rust外部函数接口来和其他语言进行交互时，这一属性可以起到很大的帮助，这一部分的内容会在第十一章中详细描述，此时的Rust会为导出的类型生成与其他语言的编译器所对应的内存布局。同时，由于C型式的布局是在编译前可预测的而且不会被改变，repr(c)属性在unsafe场景下（裸指针，类型强制转换）也可以发挥很大的帮助作用。

Note: 另一个有用的属性是repr(transparent)，这一种属性是能用在仅含有一个单独的字段的类型中，它保证了该类型的布局和内部的类型完全一致。这一种布局方式在 newtype模式下非常有用，此时你可以将newtype完全等同于它内部的类型，struct A 和 struct NewA(A)在内存中的布局是完全一致的。如果没有repr(transparent)，那么Rust编译器将无法保证这种一致性

接下来，让我们看看在repr(c)下，编译器是如何排布一个特定的类型的。想一想，对于Listing 2-1的Foo类型，编译器会以什么样的形式来把它放置在内存中？

// Listing 2-1
#[repr(C)]
struct Foo {
  tiny: bool,
  normal: u32,
  small: u8,
  long: u64,
  short: u16,
}

起初，编译器发现了字段tiny，它的逻辑大小为1比特。然而CPU和内存是以字节为单位执行操作的，tiny表示在内存中将占据一字节的空间。其次，normal是一个四字节大小的类型，所以我们需要对这个字段进行四字节对齐。然而尽管在Foo被正确对齐的情况下，编译器分配给tiny的一字节会导致normal无法满足对齐的要求。为了纠正这一点，编译器会在normal之前的和tiny之后的内存中插入三字节的填充(padding)，这些填充是一些不确定的值，并且在用户的代码将被忽略。

对于下一个字段small而言，对齐的策略十分简单：这只是一个单字节的值，并且目前的字节偏移量为1+3+4=8，已经完成了单字节的对齐，所以small可以立即被插入normal之后。然而遇到long时，我们又遇到了一个问题。现在的字节偏移量为第1+3+4+1=9字节。如果Foo是正确对齐的，那么long就不会被正确地以8字节的形式对齐，所以我们必须在long之前插入另外的7字节来确保它重新对齐。最后我们也可以简单地保证short字段满足双字节对齐的要求。此时，Foo类型所占用的内存空间总计为26字节。所以，为了保证Foo在被放置入类似数组这样的容器时可以保持对齐，编译器最终会在该类型的最后添加6个字节来保证Foo满足8字节对齐。

到了现在，我们是时候抛弃那些C语言标准中定义的规则，转而开始考虑Rust中没有repr(c)的情况了。让我们再重新回顾Listing 2-1，通过之前的分析，我们可以看到C语言定义的表示方法的一个很重要的局限性是它要求编译器将结构体的字段按照其所声明的顺序排布在内存中。默认的Rust表示方法repr(Rust)中去除了这一条限制，同时，Rust还对其他的限制做了一些宽松处理：例如，在C语言中恰好拥有相同字段以及相同字段顺序的两个类型在内存中一定会具有相同的表示形式，而Rust中即使两个类型的字段类型和声明顺序完全一致，编译器也无法向你许诺这两个类型在内存中拥有完全一致的布局！

既然我们现在已经可以对字段进行重排序，我们可以选择让这些字段按照其占用内存空间大小的降序进行排列。这意味着我们无需再对Foo进行额外的填充，这些字段本身就可以实现对齐。现在的Foo仅仅占用了它原本所应当占用的空间：16字节。这也正是Rust在默认的情况下不对类型在内存中的布局做出保证的原因，通过赋予编译器重排布的自由，我们就可以生成更加高效的代码。

事实上我们还有第三种布局方法，那就是告诉编译器不要在字段之间进行任何的填充。一旦这样做了，我们就必须要承受未对齐访问会带来的性能损耗。这种布局方法最常用在对内存占用极度敏感的场景下，例如当你同时拥有该类型的相当多个实例时，当你只有非常有限的内存时，或者当你将该类型在内存中的表示通过一个低带宽的媒介进行传输时（例如网络连接）。要切换到这种布局，你可以在你的类型定义前标注#[repr(packed)]。记住，这样的做法可能会导致代码运行得相当慢，并且，在极限情况下，如果某些操作在你的CPU中只支持对齐后的参数，这会导致你的程序直接崩溃。

有些时候，你希望给某个字段或者类型以一个超过它原本要求的大小的对齐标准。对于这种情况，你可以使用属性#[repr(align(n))]。对于这种情况，一个常见的使用场景是为了保证那些在内存中被连续存储的值（比如数组）最终可以被CPU加载入不同的缓存行(cache line)中，这样一来，你就可以避免那些伪共享(false sharing)，这在并发的程序中会带来巨大的性能损耗。伪共享是指：对于那些在理论上可以并行操作的情况，两个不同地值被错误地加载到了同一段缓存行中，导致两个同时运行的CPU不得不费力地反复更新缓存中的同一个条目。在第十章中，我们会更详细地讨论并发这一主题。

复杂类型(Complex Types)

你也许会好奇编译器是怎么将其他类型表示在内存中的，下面是的信息可以供你快速地参考：

元组(Tuple) 的表示方法和一个与该元组拥有着相同字段的结构体一样。
数组(Array)的表示方法是一串连续的元素紧邻着排布，它们之间不会有额外的填充。
联合体(Union)的布局是根据各个变体(variant)独立地选取的，一个联合体的对齐大小和其所有变体中对齐大小最大的一个保持一致。
枚举(Enumeration)的表示方法和联合体一样，但是枚举类型中还具有一个额外的隐藏共享字段用于存储变体的判别值。该判别值是一个代码，用于区分当前枚举类型所代表的变体。判别值字段占用内存空间的大小取决于变体的数量。

动态尺寸类型和宽指针(Dynamically Sized Types and Wide Pointers)

你可能在各种各样的Rust文档中的古怪角落里，或是返回的错误信息里遇到过“标记特性(marker trait)”Sized。通常而言，它的出现意味着编译器希望你能够提供一个具有Sized 特性的类型，而你显然没有。Rust中绝大部分的类型都自动实现了Sized特性——也就是说，他们的大小在编译阶段是已知的，然而，两个常见的类型却并不满足这样的条件：trait object以及切片(slice)。举例来说，dyn Iteratot和[u8]，这两个类型没有一个确切的大小。他们的大小取决于一些运行时信息，这些信息在编译阶段是不可知的，也正因为此他们才被叫做动态尺寸类型(dynamically sized type, DST)。没有人能够提前知道一个作为函数参数的dyn Iterator是代表着一个200个字节的结构体或者是一个8字节的结构体。这样的情况于是带来了一个问题：通常编译器必须知道一些变量的大小来生成有效的代码，这些信息将用于判断诸如应当为一个(i32, dyn Iterator, [u8], i32)类型的元祖分配多少内存空间或者当你的代码需要获取第四个字段时，应该使用多大的内存偏移量。但是如果这些类型并不是Sized的，那么这些信息都无法获取。

几乎在所有的地方，编译器都要求类型具有Sized特性，比如：结构体字段，函数参数，函数返回值，变量类型以及数组类型，这些都必须具有Sized特性。这种限制过于普遍，以至于你所写的所有type bound都会默认包含T: Sized。只有当你显式地使用T: ?Sized(?意味着“不一定是”)标注type bound时，这种限制才会失效。但是在这些情况下，比如当你希望你的函数接受一个trait object或是slice作为参数时，DST的存在会让你的开发过程变得困难重重。

为了填补动态尺寸类型和固定尺寸类型之间的间隙，我们可以将动态尺寸类型放置在一个宽指针(wide pointer，也叫胖指针, aka fat pointer)之后。一个宽指针就像一个普通的指针一样，但是它包含了一个额外的单字大小的字段，这个字段给出了关于该指针的一些额外的信息以供编译器来生成合理的处理代码。当你对一个DST作取引用操作时，编译器会自动地为你构造出一个宽指针。对于一个slice而言，这个“额外的信息”就是指该slice的长度。而关于trait object的介绍，我们会在稍后给出。此外最重要的是：宽指针是定长的，它具有Sized特性。具体来说，宽指针的大小是usize大小的两倍（usize代表目标平台的单字大小）：一个单字用于存储指针，另一个单字用于存储补全该类型的一些“额外信息”。

Note: Box和Arc同样支持存储宽指针，这也正是为什么他们的声明中都支持T: ?Sized。

特性以及特性界(Trait and Trait Bounds)

Traits 是Rust类型系统中十分关键的一个部分——正是他们使得类型之间可以在互相不知道对方的定义时仍然可以正常地相互操作。《The Rust Programming Languge》一书很好地介绍了如何定义和使用traits，所以我不会再重复这些内容。取而代之的是，我们将会从一个与技术性的视角来观察traits：探讨traits的实现方式，使用限制以及其他那些更高深晦涩的使用技巧。

编译以及指派(Compilation and Dispatch)

到目前为止，你可能已经使用Rust写了相当多与范性相关的代码。你也许已经在类型和方法的定义中使用了范型参数，甚至可能还在一些地方用到了trait bounds。但是你有思考过当你编译具有范型的代码时会发生什么吗？或者说，当你对一个dyn Trait调用方法时，会发生什么呢？

当你写下了一个具有范型参数T的类型或者函数时，你其实是在告诉编译器去为每一个可能的T生成一份该类型或者函数的拷贝。当你构建一个Vec<i32>或者HashMap<String, bool>时，编译器实际上将这个范型以及所有与它相关的实现做了一次复制粘贴，并且将其中出现的所有范型参数替换为了你指定的具体类型。具体来说，编译器创建了一个Vec的完整拷贝，并将每一个T替换为了i32，又生成了HashMap的完整拷贝，并将每一个K和每一个V替换为了String和bool。

Note: 实际上，编译器并不会做完成的拷贝，它只会拷贝那些被你用到的代码，所以如果你的代码中从未对Vec<i32>调用find方法，那么find的代码将不会被拷贝和编译

相同的规则也会被应用到范型函数之上。让我们来看一看Listing 2-2中的代码，其中展现了一个范型方法。

// Listing 2-2: 一个使用静态指派(static dispatch)的范型方法
impl String {
  pub fn contains(&self, p: impl Pattern) -> bool {
    p.is_contained_in(self)
  }
}

编译器会为所有具有Pattern特性的类型生成一份该方法的拷贝（回忆一下，impl Trait是<T: Trait>的简写）。我们需要为每一个impl Pattern类型生成一份不同的拷贝，因为我们必须在编译时确定is_contained_in函数的位置来生成调用它的代码。对于某一个已知的impl Pattern类型，编译器可以确定is_contained_in方法的地址正是在该类型实现Pattern特性的地方。然而并没有一个地址可以用来代表所有的impl Pattern类型的is_contained_in方法，所以我们不得不为每一个这样的类型生成一个contains函数的副本，每一个副本里都有一个不同的用于跳转到is_contained_in方法的地址。这就是我们所说的静态指派(static dispatch)，这意味着对于所有副本方法，我们将要指派的地址可以静态地获取。

Note: 你可能注意到了在当前的上下文中静态(static)这个词的含义有一些冲突。静态通常用来指代所有可以在编译阶段得知的东西，或者其他的一些等价于编译阶段可知的东西。这样一来这些“东西”就可以被写在静态内存中，这和我们在第一章中讨论的一样。

把范型转化为非范型的过程被叫做单态化(monomorphization)，这正是范型Rust在性能表现上通常和非范型Rust一样好的一部分原因。当编译器开始优化你的代码时，所有的范型就像从未存在过一样！所有的实例都会被单独优化，所有的类型都是已知的。所以，我们的代码在效率上就像是直接调用传入的范型参数对应的is_contained_in方法，而没有涉及任何traits一样。编译器拥有关于代码囊括的所有类型的知识，所以如果它愿意的话，甚至可以将is_contained_in方法转变为内联实现。

然而单态化也是有代价的：所有类型对应的实例都必须被分别编译，如果编译器无法将这些代码优化掉的话，这会导致编译时间变长。所有的单态化函数也会带来它们各自的一段机器码，这会导致你的程序本身占用更多的存储空间。同时，由于指令在不同的范型实例方法中无法被共享，CPU的指令缓存也会因为不得不存储多份实际上相同的指令而变得更低效。

非范型的内层函数

通常来说，一个范型方法中的许多代码都是与类型无关的。比如在HashMap::insert中，用于计算key的哈希的代码依赖于当前map的key的类型，然而用于遍历map中的buckets来寻找插入点的代码则不是这样。在这种情况下，在不同的单态化实例间共享这一部分非范型的代码会变得更有效率——我们只需要为范型方法代码中那些不同的部分来生成拷贝就好了。

具体来说，一种好的做法是在该范型方法内部声明一个用于执行共享行为的非范型帮助函数。这会让编译器仅仅为你复制那些和类型相关的代码，同时允许帮助函数在不同的实例间被共享。

将函数声明为一个内部函数同时也带来了另一个好处：你无需担心你的代码会被这个单一用途的函数而被污染。当然你也可以把这样的一个帮助函数声明在方法之外，但是务必小心不要把这个方法生命在一个范型的impl块里，这会导致这段帮助函数最终仍然被编译器单态化。

除了使用静态指派以外，你还可以在你的代码中选择动态指派(dynamic dispatch)。动态指派使得你的代码可以在不知道具体类型的情况下调用该范型所具有的trait方法。我之前提到过，在Listing 2-2中我们需要同一个方法的多份拷贝是因为如果不这样做的话，你的程序就无法确定调用is_contained_in方法时所需要的跳转地址。然而，在动态指派的帮助下，这一信息将由调用者给出。如果你将函数申明中的impl Pattern替换成&dyn Pattern，那么就相当于要求调用者必须给出关于这一参数的两部分信息：pattern本身的地址以及is_contained_in方法的地址。在具体的实现上，调用者是给了我们一个指向虚函数表(virtual method table, vtable)的指针。这个表中的每一个条目保存了其所属类型所实现的所有属于某一trait的方法的地址，其中之一就是is_contained_in。当方法中的代码想要对给出的pattern调用对应的方法时，它会在该类型的vtable中寻找对应的地址来用于后续的跳转。这就使我们可以无视调用者的类型而复用同一段函数代码了。

NOTE:每一个虚函数表中还存储着对应的真实类型的布局(layout)以及对齐标准(alignment)，这些信息在处理某一类型时可以说是必要的。如果你想要亲自看看虚函数表长什么样子，那么可以去参考一下std::task::RawWakerVTable类型

你会发现，当我们使用dyn关键词来切换入动态指派时，我们必须在之前加上一个&。这是因为我们无法在编译时确定调用者传入的那一个具有pattern特性的类型的真实大小，所以我们也无法提前为这个对象预留合适的内存空间。换句话来说，dyn Trait是!Sized的，这里的!意味着非。为了让他成为一个合法的参数，我们需要使它具有Sized，具体的做法就是使用一个指向它的指针（显然一个指针的大小是已知的）。并且由于我们还需要传递一张具有方法的地址的表，所以这个指针就成为了一个宽指针，其中的额外的信息正是虚函数表的地址。你可以使用任何能够储存宽指针的类型来用作动态指派，比如&mut，Box以及Arc。Listing 2-3展示了Listing 2-2使用动态指派实现后的版本。

// Listing 2-3: 一个使用动态指派的方法，它可以被广泛地应用在多个调用点处而不需要被复制
impl String {
  pub fn contains(&self, p: &dyn Pattern) -> bool {
    p.is_contained_in(&*self)
  }
}

一个实现了某一种trait的类型和它的虚函数表的组合就叫做一个trait object。绝大部分的trait都可以被转换为trait object，但还是有例外，比如Clone，它的clone方法会返回Self，这一种trait无法被转换为trait object。如果我们接受dyn Clone作为trait object，然后对该trait object调用clone方法，编译器将无法获知具体的返回类型。或者再举一个例子，让我们来看看标准库中的Extend trait，它的方法extend使用了一个范型来指代调用者提供的迭代器类型（所以这个方法会同时存在多个实例）。如果你调用了一个以dyn Extend作为参数的方法，那就会导致无法确定extend的方法的地址（此时的extend地址不仅取决于传入的dyn Extend的真实类型，也取决于用于调用extend的参数）。这样一来，每一个可能的extend实例都需要在vtable中占据一个条目，而这显然是无法做到的。以上这些就是不具有对象安全(object-safe)属性的trait的例子，这些trait无法被转换为trait objects。为了实现object-safe，trait方法中不可以出现范型，或者使用Self作为类型。进一步来说，这些trait也不能拥有静态方法（即第一个参数不可以被解引用为Self的方法），因为这样会导致我们无法获知要被调用的方法属于哪一个实例。举个例子，对于这一段代码FromIterator::from_iter(&[0])来说，究竟应该调用的是哪个类型的from_iter方法是不得而知的。

当我们查看各种与trait object相关的代码时，你也许看到过一种trait bound叫作Self:Sized。这样的一个trait bound暗示了Self类型不会在trait object中被使用到（不然的话它这种情况就变成了!Sized）。你可以为你的trait附加一条这样的trait bound来保证该类型永远不会采用动态指派。或者，你也可以把这个trait bound放置在某一个方法之前，这样该方法对于trait object而言就是不可见的。被标注为where Self: Sized的方法会在检查object-safe时被排除在外。

由于动态指派不需要编译多份类型和方法的拷贝，它可以帮助缩减编译时间，同时它也可以提高你的CPU指令缓存的效率。然而，动态指派的存在使得编译器无法进一步地为你优化某些特定的类型。Listing 2-2中的例子，在动态指派下，编译器能做的最大努力只是通过虚函数表中记录的信息来生成一次对find的方法调用，除此之外，它无法再进行任何额外的优化，因为在编译时，编译器无法得知虚函数表中存储的究竟是方法的哪一个实例。进一步来说，每一次对trait object进行的方法调用都需要一次额外的查表作为开销，这一点也为函数调用增加了些许的开销。

当你需要在静态指派和动态指派之间做出选择的时候，我们很难给出一个清晰简单的正确答案。总得来说，你可能会更希望在你开发的库(library)中使用静态指派，同时在你开发的二进制文件中使用动态指派。在你开发library的时候，你希望它的使用者来决定适合他们的指派方式，因为你并不清楚你的用户有着什么样的需求。在这种情况下，如果你使用动态指派，那么用户就不得不做同样的事情，然而如果你使用静态指派，用户就可以自己选择需要的指派类型。在二进制文件的场景下，你所写下的就是最终的代码，所以你只需要关注自己写下的代码。动态指派可以让你摆脱范型参数，写出更加整洁的代码，同时也能让你的代码编译得更快，而这一切所带来的性能损耗(通常)是微不足道的。所以写二进制文件时，动态指派往往是一个更好的选择。

范型特性(Generic Traits)

Rust trait可以通过两种方式来实现泛用性：使用范型参数，如trait Foo<T>或者使用关联类型(associated type)，如trait Foo {type Bar; }。这二者之间的区别并不是非常显著，但是幸运的是，在选择使用的场景时，我们可以有一个非常简单的评判标准：对于某一种类型而言，如果你只希望实现一次该trait，那么就使用关联类型；反之，在trait中加入范型会是更好的选择。

这种做法背后的合理性在于，使用关联类型通常来说会比使用范型简单非常多，但它并不允许对应的trait被多次实现。所以，更加简单地来看待先前的评判标准，我的建议是尽可能地去使用关联类型。

对于一个具有范型的trait来说，用户总是需要指明所有的范型参数以及这些范型参数所具有的任何trait bound。这样的要求会导致你的代码很快变得乱糟糟的并且很难维护。一旦你在你的trait中添加了一个新的范型参数，该trait的所有用户都需要更新他们自己的代码来迎合这一改变。并且，由于对于给定类型来说，相同的trait可能被实现了很多次，编译器很难弄清楚你想要的究竟是哪一个实例，为此你必须使用一段看起来很糟糕的代码来消除歧义，比如FromIterator::<u32>::from_iter。但是好处就是，现在你可以为同一个类型实现多次相同的trait。比如，你可以基于多种不同的右值类型来为你的类型实现PartialEq，或者你可以同时实现FromIterator<T>以及FromIterator<&T> where T: Clone，这完全归功于范型trait所提供的灵活性。

从另一方面来讲，对于关联类型，编译器只需要知道实现了这个trait的类型即可，其他所有的关联类型也会随之而确定(因为该trait只会有一种实现)。这意味着所有的限制都只需存在于trait定义的内部，不需要在使用时再重复声明。所以，这同时也允许我们可以在不影响用户代码的情况下来添加新的关联类型。同时，对于某一类型来说，它所实现的trait内部的关联类型是固定的，所以你永远不需要使用之前提到的统一函数调用语法(unified function calling syntax)来消除歧义。然而，这样做后你将无法为多个Target类型来实现不同的Dereftrait，你也不能为不同的Item类型来实现多个Iteratortrait。

一致性和孤儿规则(Coherence and the Orphan Rule)

Rust对于你可以实现的trait以及你可以将这些trait实现在哪些类型上有着严格的规定。这些规定存在的意义是为了保留一致性：对于任何的类型，在对它进行调用方法时，该方法的实现必须是唯一确定的。我们可以通过一个例子来看一看这种规则背后的重要性：试想一下，假如我可以为标准库中的bool类型实现自己的Debugtrait会发生什么？在这种情况下，对于我所写的代码中所有尝试打印bool值的片段，编译器无法确定此处要调用的是我自己写的Debug实现，还是标准库中定义的实现。在这种情况下，没有一个选择会比另一个更好，同时编译器显然不应该随机地做选择。即使是在没有标准库的场景下，这种问题同样会存在，只不过那时我们会拥有两个相互依赖的crate，他们内部各自为一个共享的类型实现了一个相同的trait。一致性的提出就是为了确保编译器永远不会陷入需要做出这种选择的窘境，对于编译器来说，选项只能有一个。

为了实现一致性，一种简单的做法是只允许定义了某个trait的crate来实现该trait；如果其他任何人都不能实现这个trait，那么冲突将永远不会发生。然而，这种做法在实践上做了过多的限制以至于使得trait不再能够发挥它应有的作用：例如，这样会使得我们无法为自己的类型实现std::fmt::Debug和serde::Serialize，除非你将自己的类型转移到定义了这些trait的crate中。另一个反面的极端是你只能为自己的类型实现trait，这解决了之前的问题，但是却引入了另一个问题：定义了某个trait的crate不再能够为标准库或者其他热门库中的类型提供该trait的实现！我们在开发时有两种需求，一是想要下游的crate来为他们自己的类型实现上游的trait；二是上游的crate可以为他们自己的trait添加实现，同时又不会破会下游的代码。在理想的情况下，我们必须找到一种可以很好地平衡这两种需求的规则。

Note: 上游指代的是你的代码所依赖的那些东西，下游则只带那些依赖你的代码的东西。通常来说，这些术语用于直观地描述crate之间的依赖关系，但它们也可以被用来指代一个代码仓库的一份权威的fork——如果你fork了一份Rust编译器的代码，那么官方的Rust编译器就是你的上游

在Rust中，建立这种平衡的正是孤儿规则(orphan rule)。简单来说，孤儿规则是指当你实现一个trait时，你必须确保该trait和实现的目标类型中至少有一个来自于你自己写的crate。所以你才能为自己的类型实现Debug，同时也能为bool实现MyNeatTrait，但你不能为bool实现Debug。一旦你这么做了，你的代码将不会被编译，并且编译器会告诉你存在相互冲突的实现。

这已经带给了你足够的保障和便利性；它允许你为第三方的类型实现你自己定义的trait，同时也可以为自己的类型实现第三方的trait。然而，这种孤儿规则并不是故事的全部。这其中还有许多额外的隐藏含义和例外情况，你必须意识到这些情况的存在。

通用实现(Blanket Implementation)

孤儿规则允许你来为一个范围内的类型来实现trait，比如impl<T> MyTrait for T where T:诸如此类，这叫做通用实现(blanket implementation)，在通用实现中，trait的实现不仅仅局限于某一个特定的类型，实现的对象可以被扩展到一个很大范围的类型。只有定义了trait的crate才可以为该trait进行通用实现，同时，为一个现有的trait添加一个通用实现会被视为一个破坏性变动(breaking change)——如果不这样做的话，下游的代码如果实现了impl MyTrait for Foo就会无法通过编译检查，因为这会导致一个MyTrait得冲突实现，而这一切都是因为你在上游的代码中引入了一个通用实现。

基本类型(Fundamental Types)

有些类型过于重要，以至于我们必须允许任何人为它们实现trait，尽管这样的做法看起来会违背孤儿规则。这些类型会有一个#[fundamental]标记，目前来说，这样的基本类型包括&,&mut以及Box。为了实现孤儿规则，这些基本类型在做孤儿规则的检查时就像不存在一样——他们会在检查前就被移除出检查的对象。现在，我们可以写出如下的代码了：IntoIterator for &MyType。在孤儿规则的限制下，上述的代码并不会通过编译检查，因为它为一个外部的类型实现了一个外部的trait——IntoIterator和&都来自于标准库。需要注意的是，为一个基本类型添加通用实现也会被视作次破坏性的改变。

Covered Implementations

除了之前提到的基本类型以外，在一些其他的有限的情况中，我们也会想要打破孤儿规则来为外部的类型实现外部的trait。最简单的例子就是impl From<MyType> for Vec<i32>。在这里，From是一个外部的trait，Vec同样也是。目前来看，这并没有破坏一致性规则。这是因为，冲突的实现之可能发生在为标准库添加一个通用实现时（不然的话，标准库中不可能会有MyType），而这这种变动必然会是一次破坏性变动。

为了允许这种实现的存在，孤儿规则中引入了一些有限的例外，它允许为外部类型实现外部trait发生在一些非常特殊的情况中。具体来说，对一个实现impl<P1..=Pn> ForeignTrait<T1..=Tn> for T0而言，仅当至少一个Ti是本地类型并且在第一个满足这样条件的Ti之前的T中，没有一个T来自于范型P1..=Pn时，才会被接受。只有被一些中间类型覆盖(covered)时，T0..Ti中才可以出现那些范型参数（即P）。一个T被覆盖意味着它被用作另一个类型的类型参数，比如Vec<T>，而不是它独自出现(只有T)或者出现在一个基本类型后，比如&T。所以，Listing 2-4中所有的实现都是有效的。

// Listing 2-4: 为外部类型实现外部trait的一些有效的例子
impl<T> From<T> for MyType
impl<T> From<T> for MyType<T>
impl<T> From<MyType> for Vec<T>
impl<T> ForeignTrait<MyType, T> for Vec<T>

然而，Listing 2-5中的实现都是无效的。

// Listing 2-5: 为外部类型实现外部trait的一些无效的例子
impl<T> ForeignTrait for T
impl<T> From<T> for T
impl<T> From<Vec<T>> for T
impl<T> From<MyType<T>> for T
impl<T> From<T> for Vec<T>
impl<T> ForeignTrait<T, MyType> for Vec<T>

孤儿规则的这种宽松化处理使得我们更难去判断什么样的情况下，为一个现有的trait添加新的实现会导致破坏性改变。特别是，只有当某一个trait中含有至少一个新的本地类型时，为该trait添加一个新的实现才不会被视为是破坏性改变，并且这个新的本地类型必须满足先前提到的例外情况。添加任何其他的新实现都会被视为破坏性改变。

Note: 需要注意的是impl<T> ForeignTrait<LocalType, T> for ForeignType是有效的，但impl<T> ForeignTrait<LocalType, T> for ForeignType则是无效的！这也许看起来很不符合常理，但是如果没有了这一条规则，就会发生这种情况：你在自己的crate中写下impl<T> ForeignTrait<T, LocalType> for ForeignType，同时另一个crate在他们的代码中写下impl<T> ForeignTrait<TheirType, T> for ForeignType，此时如果两个crate出现在了一起，就会出现冲突。比起完全禁止这种模式，孤儿规则选择了要求你的本地类型出现在类型参数之前，这就打破了这一种死结并且保证了，如果两个crate分别保证了一致性，那么他们被引入同一个项目时，也能继续保持一致性。

Trait Bounds

标准库中存在着许许多多的trait bound，比如HashMap的键值中必须实现Hash + Eq，以及传入thread::spawn中的函数必须实现FnOnce + Send + 'static。当你自己写范型代码时，你几乎一定会用到trait bound，不然的话你的代码可能无法很好地利用它所用到的范型参数。随着你写下越来越多精致巧妙的范型实现，你会发现你还需要更好地来操控trait bound来实现你想要的功能，那么就让我们来看看如何做到这一件事吧。

首先，trait bound并不一定需要以T: Trait的形式出现。我们所界定的可以是任意的类型限制，甚至都可以不包含范型参数，参数的类型，或者本地类型。你可以写下这样的trait bound: where String: Clone，即使String: Clone永远是正确的，而且其中并不包含任何的本的类型。你也可以写下where io::Error: From<MyError<T>>;你的范型参数并不一定要出现在左手边。这不仅让你能够更好地表达那些错综复杂的trait bound，同时也让你节省了反复重复这些trait bound的时间和精力。举个例子，如果你的方法需要构建一个HashMap<K, V, S>，其中键值部分是一个范型参数T而值(value)部分是一个usize，你可以不用写下像where T: Hash+Eq, S: BuildHasher + Default这样的trait bound，只需要where HashMap<T, usize, S>: FromIterator就足够了。这很大程度上节省了你查阅那些准确的trait bound要求的时间，同时也更好地传达了你的代码此处"真正"的需求。正如你所看见的那样，当你想要调用的trait方法非常复杂时，它也可以显著地降低你的trait bound的复杂度。

Derive Trait

虽然#[derive(Trait)]使用起来很方便，但是在使用trait bound的场景下，你应该有意识地注意到#[dereive(Trait)]在实现上的一个细微之处。许多#[derive(Trait)]会被展开为impl Trait for Foo<T> where T: Trait。通常来说，这可以很好地满足你的需求，但是也有例外的情况。比如说，试想一下，如果我们为Foo<T>附加#[derive<Clone>]，而Foo包括了一个Arc<T>时，会发生什么呢？无论T有没有实现Clone，Arc本身都会实现Clone，但是由于derive bound的存在，只有在T实现了Clone时，Foo才可以实现Clone。这并不是一个很严重的问题，但它确实引入了一些不必要的限制。如果我们把这个类型Foo当作Shared，这个问题就会变得清晰一些。想象一下，对于一个用户来说，看见一个不能被clone的Shared<NotClone>会有多奇怪！在写下这本书的时候，这就是目前标准库中#[derive(Clone)]的工作方式，不过在未来可能会发生变化。

有的时候，你希望为关联类型也添加一些限制。比如，让我么来考虑一下迭代器方法flatten，它的参数是一个迭代器的的迭代器，它的输出则是一个对参数中内层元素的迭代器。（举例来说，参数可以是一个二维数组的迭代器，而输出则可以转换为将嵌套的二维数组按次序展开为一位数组后的迭代器）。它返回的类型Flatten含有一个范型参数I，这个I代表了外层迭代器的类型。如果I实现了Iterator且I所产生的类型实现了IntoIterator，那么Flatten也会实现Iterator。为了允许你能够写出这样的trait bound，Rust中可以通过Type::AssocType的方式来指代类型中的关联类型。举例来说，我们可以使用I::Item来指代I的Item类型。如果一个类型含有多个同名的关联类型，比如提供了关联类型的trait本身同时还具有范型参数(这样一来这个trait就可能被实现了很多次)，你可以通过<Type as Trait>::AssocType这样的语法来消除歧义。这样一来，你不进可以为外层的迭代器添加限制，同时也可以为外层的迭代器内部的关联类型Item一并添加限制。

在一些用到了很多范型的代码中，你可能会发现你需要为类型的引用来添加限制。通常来说这没什么问题，因为在大部分情况下你需要添加限制的引用类型会自带有一个范型生命周期参数，你可以在引用类型的限制中使用这个信息。然而，在一些情况下，你会希望这个引用在任何生命周期下都要实现这个trait。这种bound 被称作HRTB(higher-ranked trait bound)，HRTB在Fntrait的场景下十分有用。举个例子，假设你想要设计一个函数类型的范型参数，它接受一个T的引用作为参数，返回一个T的内部成员的引用。如果你使用这样的写法：F: Fn(&T) -> &U，那么你就需要为这些引用类型提供生命周期。但是也许你仅仅希望返回值的生命周期与参数的生命周期相同，而对具体的生命周期不作任何要求。那么在这种情况下，你就可以用到higher-ranked lifetime。只需要写下F: for<'a> Fn(&'a T) -> &'a U'即可表示：对于任何生命周期'a，这条trait bound必须满足。在实践中，Rust编译器在大部分情况下都可以智能地在这种场景下添加for的部分。显式地声明HRTB的情况非常非常罕见，在标准库中，HRTB一共仅仅出现了三次——不过既然它存在，那么就值得我们在此讨论它的使用。

为了更好地理解这里提到过的trait bound，让我们来看一看Listing 2-6中的代码，它可以用来为任何可以迭代的并且迭代的元素为Debug的类型实现Debug。

// Listing 2-6: 一个针对任何可迭代的集合所编写的一个具有极高泛用性的`Debug`实现。
impl Debug for AnyIterable 
	where for<'a> &'a Self: IntoIterator,
				for<'a> <&'a Self as IntoIterator>::Item: Debug {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        f.debug_list().entries(self).finish()
      }
}

你可以将这一段实现复制粘贴为几乎任何集合类型的Debug实现，它都可以“正常地运作”。当然，你需要的可能是一个更加聪明的Debug实现，但是这个例子很好地展示了trait bounds的能力。

Marker Traits

通常来说，我们会用trait来表示一些会被很多类型同时支持的功能；一个具有Hash的类型可以通过调用它的hash方法来得到它的哈希值；一个具有Clone的类型可以通过调用它的clone方法来被复制；一个具有Debug的类型可以通过调用它的fmt方法来打印它的格式化调试信息。但是并不是所有的trait都是通过这种方式来实现它们的功能性的；有一些被叫做marker trait的trait，则是间接地指示了对应类型的某种属性。marker trait没有任何的方法和关联类型，它的存在只是为了告诉你某个类型能够或者不能够被用于某一种用途。举个例子，如果一个类型实现了Send maker trait，那么我们就可以安全地在线程间传递它。如果这个类型没有实现Send，那么我们就不可以安全地传递。这种行为本身并没有任何相关联的方法；这个trait本身只是一个关于某个type的事实。在标准库的std::marker模块下有许多这样的trait，其中包括Send，Sync，Copy，Sized和Unpin。这些中的绝大部分（除了Copy以外的全部）都是自动特性(auto-traits)；除非某个类型中包含了一些没有实现该marker trait的东西，否则编译器会自动地为该类型实现该marker trait。

marker trait在Rust中是为了一个重要的目的而存在的：他们使得你能够通过指明bounds的方式来捕获那些没有直接通过代码来表达的语义要求。在要求Send类型的场景下，我们无法通过在代码中调用send函数来迫使某个类型具有Send。取而代之的是，实际的代码会假定它获得的类型可以被安全地传送到另一个不同的线程。如果没有marker trait，编译器就无法检查这种假定是否正确，从而这种责任就被转移给了开发者——开发者必须记住自己做出的这种假设，并且仔细地检查自己写下的代码，显然，这种做法是非常不可靠的，它会带来数不清的数据竞争，段错误以及其他的运行时问题。

和marker trait对应的另一种相似的机制是marker types。他们是单元类型(unit type)（比如struct MyMarker;），这些类型中没有任何的数据和方法。marker type是用来标记某一个类型当前是否处在一个特殊的状态下的。如果你希望完全避免你的代码的用户误用一个API，你就可以使用这种marker type。举个例子，让我们来看一种SshConnection类型，它可能存在于已认证(authenticated)或未认证(unauthenticated)两种状态下。你可以为SshConnection添加一个范型参数，同时再创建两个marker type：Unauthenticated和Authenticated。在用户尝试发起一次链接的最初，他得到的是SshConnection<Unauthenticated>。在它的impl块中，你只需要提供一个方法：connect。这个connect方法返回一个SshConnection<Authenticated>，同时，只有在这个类型的实现中，你才提供了其他诸如执行指令等的方法。我们会在第三章中再来探讨这种类型。

Existential Traits

在Rust中，你很少需要指明函数中变量的类型，或是指明方法的范型参数的具体类型。这一切都归功于Rust的类型推断（type inference）机制，这一机制使得编译器可以通过求解该类型出现的代码片段所代表的类型来判断此处需要的类型。编译器通常只会推断变量的类型以及闭包的参数（和返回值）的类型；诸如函数，类型，trait以及trait实现部分等顶级定义都需要你显式地给出所有的类型。这背后有着些许的原因，但是最主要的一个原因是：类型推断机制需要至少几个已知的点作为推断的初始条件来使整个推断过程变得更容易。然而，要显式地指出类型，在有些时候并不容易，甚至无法做到！举个例子，如果你从函数中返回了一个闭包，或者从一个trait方法中返回了一个异步块（async block），这些东西并没有一个可以让你写入你的代码中的类型名称。

为了处理这种情况，Rust支持existential type。事实上，你可能已经在实践中见过了existential type。所有被标注为async fn或者返回值为impl Trait的函数都有一个existential type作为返回值：签名中并不会给出返回值的真实类型，而是给出了一个提示来告诉调用者该函数返回了一些类型，这些类型实现了一些trait的集合，调用者可以根据此来获取关于返回值的信息。并且，关键的是，调用者只能依赖于实现了那些特定trait的类型作为返回值，而不能做其他的假设。

Note: 从技术上来说，调用者只能依赖于实现了那些特定trait的类型作为返回值本身并不是严格正确的。编译器同样也会通过返回值位置的impl Trait扩散auto-trait，比如Send和Sync ，我们会在下一章中更多地探讨这种情况。

Existential type这个名称本身就是由这种行为总结而出的：我们断言这个位置存在一些可以匹配签名的具体类型，并且我们把找到这个具体类型的任务留给了编译器。编译器通常会进一步通过对函数体进行类型推断来弄清楚真实的返回值。

并不是所有到的impl Trait实例都用到了existential type。如果你在函数参数中使用impl Trait，那实际上这只是一种未命名的范型参数的简写形式。举个例子，fn foo(s: impl ToString)只是fn foo<S: ToString>(s: S)的一种语法糖形式。

Existential type在你实现那些拥有关联类型的trait时会变得格外好用。举个例子，假如你正在实现IntoIterator。它有一个关联类型IntoIter，这一关联类型中给出了当前类型可以被转化为的迭代器的类型。有了existential type，你不再需要在这个时候为了IntoIter额外地定义一个单独的迭代器类型。取而代之的是，你可以将这个关联类型赋值为impl Iterator<Item = Self::Item>，同时，只需在fn into_iter(self)中写下一个可以被判断为Iterator类型的表达式，比如对一些已有的迭代器类型使用map或者filter方法等。

除了便利之外，existential type还提供了另一种特别功能：零成本类型擦除(type erasure)。在一些情况下，比如使用迭代器或是future类型时，你可以在那些需要的位置使用existential type来隐藏那些不应该被导出其模块的真实类型。这样一来的，你的接口的用户就只能看到相关的类型所实现的trait，真实的类型将被隐藏为一种实现的细节。这种做法不仅仅简化了你的接口，也使你能够在需要的时候以一种对下游代码无害的方式改变类型的实现细节。

总结

本章节提供了一次对Rust类型系统的完整的复盘。我们同时探讨了编译器在内存中表示类型的方式以及编译器推断类型的方式。这些对于编写unsafe代码，编写复杂应用接口以及编写异步代码等后续章节会涉及的内容而言，是非常重要的背景知识。你也会发现，本章节中涉及的类型推断内容会影响到你设计你的Rust接口代码的方式，而这一部分内容我们会在下一章中提及。

By Iris.S & Ryan.X