Go1。18通过字典和Gcshape模板实现泛型

　　本文档描述了在 Go 1.18 中通过字典和 gcshape 模板实现泛型。它提供了比Gcshape 设计文档中描述的更具体和最新的信息
　　泛型的编译器实现（在类型检查之后）主要侧重于创建泛型函数和方法的实例化，这些函数和方法将使用具有具体类型的参数执行。为了避免为具有不同类型参数的泛型函数/方法的每次调用创建不同的函数实例化（这将是纯模板），我们将 字典 与对泛型函数/方法的每次调用一起传递。该字典提供有关类型参数的相关信息，允许单个函数实例化为许多不同的类型参数正确运行。
　　但是，为了实现的简单性（和性能），我们没有针对所有可能的类型参数的通用函数/方法的单一编译。相反，我们在具有相同 gcshape 的类型参数集之间共享通用函数/方法的实例化。 形状
　　gcshape （或 gcshape分组 ）是类型的集合，当指定为类型参数之一时，它们可以在我们的实现中共享通用函数/方法的相同实例化。因此，例如，在具有单个类型参数的泛型函数的情况下，我们只需要对同一gcshape分组中的所有类型参数进行一个函数实例化。类似地，对于具有单个类型参数的泛型类型的方法，我们只需要对同一 gcshape 分组中的所有类型参数（泛型类型）进行一次实例化。gcshape 类型 是我们在实现中使用的特定类型，用于填充 gcshape 分组的所有类型。
　　我们目前正在以相当细粒度的方式实现 gcshapes。当且仅当它们具有相同的底层类型或者它们都是指针类型时，两个具体类型才属于同一个 gcshape 分组。我们有意定义 gcshape，这样我们就不需要在字典中包含任何运算符方法（例如，为指定类型 arg 实现＂+＂运算符）。特别是，根本不同的内置类型，例如int和float64永远不会在同一个 gcshape 中。Even int16andint32有不同的操作（特别是左移和右移），所以我们不会把它们放在同一个 gcshape 中。同样，我们打算让 gcshape 中的所有类型始终实现内置方法（例如make//newlen) 以同样的方式。我们可以在同一个 gcshape 中包含一些非常密切相关的内置类型（例如uintand uintptr），但目前还没有这样做。我们当前的细粒度 gcshape 已经暗示了这一点，但我们也总是希望接口类型与非接口类型处于不同的 gcshape（即使非接口类型与接口具有相同的双字段结构）类型）。在调用方法等方面，接口类型的行为与非接口类型非常不同。
　　我们目前根据types.LinkString其底层类型的唯一字符串表示（如在 中实现）来命名每个 gcshape 类型。我们将所有形状类型放在一个独特的内置包＂ go.shape＂中。出于实现原因（见下一节），我们碰巧在 gcshape 类型的名称中包含了 gcshape 参数在类型参数列表中的索引。因此，具有基础类型＂string＂的类型将对应于名为＂ go.shape.string_0＂或＂ go.shape.string_1＂的 gcshape 类型，具体取决于该类型是否用作泛型函数或类型的第一个或第二个类型参数。所有指针类型都以单个示例类型命名*uint8，因此指针形状的 gcshape 名称为go.shape.*uint8_0,go.shape.*uint8_1等。
　　我们将一组特定形状类型参数的通用函数或方法的实例化称为 形状实例化 。 字典格式
　　每个字典都是在编译时静态定义的。字典对应于程序中的调用站点，其中使用一组特定的具体类型参数调用特定的通用函数/方法。每当调用泛型函数/方法时都需要字典，无论是从非泛型还是泛型函数/方法调用。字典当前以被调用的完全限定的泛型函数/方法名称和具体类型参数的名称命名。两个示例字典名称是main..dict.Map[int,bool]和main..dict.mapCons[int,bool].Apply)。main.Map[int, bool]()这些是调用或引用and所需的字典rcvr.Apply()，其中rcvr有类型main.mapCons[int, bool]. 该字典包含使用这些具体类型参数执行该通用函数/方法的基于 gcshape 的实例化所需的信息。具有相同名称的字典被完全重复数据删除（通过编译器和链接器的某种组合）。
　　我们可以通过分析通用函数/方法的形状实例化来收集有关字典预期格式的信息。我们分析实例化，而不是通用函数/方法本身，因为所需的字典条目可能取决于形状参数 - 特别是形状参数是否是接口类型。重要的是，实例已经＂转换＂到足以使所有隐式接口转换 ( OCONVIFACE) 都被显式化。显式或隐式接口转换（特别是到非空接口的转换）可能需要字典中的额外条目。
　　为了创建字典条目，我们经常需要用与字典关联的真实类型参数替换形状类型参数。因此，形状类型参数必须是完全可区分的，即使几个类型参数碰巧具有相同的形状（例如，它们都是指针类型）。因此，如前所述，我们实际上是在形状类型中加入了类型参数的索引，这样不同的类型参数才能完全正确区分。
　　字典中的条目类型如下： 泛型函数/方法的具体类型参数列表 字典中的类型始终是运行时类型描述符（指向 的指针runtime._type） 所有（或需要的）派生类型的列表 ，它们出现在泛型函数/方法中或以某种方式隐含在泛型函数/方法中，替换为具体类型参数。即具体类型的列表，具体类型从函数/方法的类型参数（例如*T、[]T、map[K, V]等）中派生出来，并以某种方式在通用函数/方法中使用。我们目前在需要表达式的运行时类型的几种情况下使用派生类型。这些情况包括到空接口的显式或隐式转换，以及类型断言和类型切换，其中源值的类型是空接口。调试器在运行时也使用派生类型和类型参数条目来确定参数和局部变量的具体类型。在编译时，有关类型参数和派生类型字典条目的信息与 DWARF 信息一起发出。对于每个具有参数化类型的参数或局部变量，DWARF 信息还指示将包含参数或变量的具体类型的字典条目。 所有子词典的列表 ：泛型函数/方法内部的泛型函数/方法调用需要一个子字典，其中内部调用的类型参数取决于外部函数的类型参数。引用通用函数/方法的函数/方法值和方法表达式同样需要子字典。子字典条目指向正常的顶级字典，该字典使用所需的类型参数执行被调用的函数/方法，使用外部函数字典的类型参数替换。 从类型参数或派生类型 转换为特定非空接口所需的任何特定 itab 。 目前我们使用字典派生的 itabs 主要有四种情况。在所有情况下， itab 都必须来自字典，因为它取决于当前函数的类型参数。OCONVIFACE对于从非接口类型到非空接口的所有显式或隐式调用。itab 用于创建目标接口。对于类型参数的所有方法调用（必须是类型参数绑定中的方法）。这个方法调用被实现为接收者到类型绑定接口的转换，因此与隐式OCONVIFACE调用类似地处理。对于从非空接口到非接口类型的所有类型断言。需要 itab 来实现类型断言。对于涉及从类型参数派生的非接口类型的类型切换情况，其中被切换的值具有非空接口类型。与类型断言一样，需要使用 itab 来实现类型切换。
　　我们已经决定，引用泛型值/类型的泛型函数/方法中的闭包应该使用与其包含的函数/方法相同的字典。因此，实例化函数/方法的字典也应该包括它所包含的所有闭包体所需的所有条目。
　　当前实现可能具有重复的子词典条目和/或重复的 itab 条目。通过在实现中进行更多工作，可以清楚地对条目进行重复数据删除和共享。对于一些不寻常的情况，可能还有一些未使用的字典条目可以被优化掉。 非单态函数
　　我们选择在编译时计算所有字典和子字典确实意味着有些程序我们无法运行。对于具有特定具体类型的通用函数/方法的每个可能的实例化，我们必须有一个字典。因为我们要求在编译时静态创建所有字典，所以必须有一组有限的已知类型用于创建函数/方法实例化。因此，我们无法处理通过泛型函数/方法的递归可以创建无限数量的不同类型（通常通过重复嵌套泛型类型）的程序。一个典型的例子显示在issue #48018中。这些类型的程序通常被称为 非单态的 . 如果我们可以在运行时动态创建字典（和泛型类型的实例化），那么我们可能能够处理其中一些非单态代码的情况。 函数和方法实例化
　　为一组特定的 gcshape 类型参数创建泛型函数或泛型方法的编译时实例化。如上所述，我们有时将这种实例化称为 形状实例化 。我们在编译期间即时确定需要创建哪些形状实例化，如下面的＂通用函数和方法调用的编译器处理＂中所述。给定一组 gcshape 类型参数，我们通过将 shape 类型参数替换整个函数/方法主体和头中的相应类型参数来创建实例化函数或方法。函数体包括函数中包含的任何闭包。
　　在替换过程中，我们还＂转换＂了任何相关节点。旧的类型检查器（typecheck包）不仅确定函数或声明中每个节点的类型，而且还对代码进行了各种转换，通常是对更具体的节点操作，而且还会为任何隐式操作制作显式节点（例如转换）。在知道操作数的确切类型之前，通常无法完成这些转换。因此，我们在节点过程中延迟将这些转换应用于通用函数。相反，我们在进行类型替换时应用转换来创建实例化。其中许多转换包括添加隐式OCONVIFACE节点。重要的是所有OCONVIFACE在确定实例化的字典格式之前明确表示节点。
　　在创建实例化函数/方法时，我们还会自动添加一个字典参数＂.dict＂作为第一个参数，甚至在方法接收器之前。
　　我们有一个在此包编译期间已经创建的形状实例化的哈希表，因此我们不需要重复创建相同的实例化。除了实例化的函数本身，我们还保存了一些额外的信息，这些信息是下面描述的字典传递所需的。这包括与实例化相关的字典格式和其他只能从泛型函数访问的信息（例如类型参数的边界）或难以从实例化主体直接访问的信息。我们计算这些额外信息（字典格式等）作为创建实例化的最后一步。 函数、方法和字典的命名
　　在编译器中，泛型和实例化函数和方法的命名如下： 泛型函数 - 只是名称（没有类型参数），例如 Max 实例化函数 - 带有类型参数的名称，例如Max[int]or Max[go.shape.int_0]。 泛型方法 - 具有方法定义中使用的类型参数和方法名称的接收器类型，例如(*value[T]).Set. （提醒一下，除了接收者类型的类型参数之外，方法不能有任何额外的类型参数。） 实例化方法 - 具有类型参数和方法名称的接收器类型，例如(*value[int]).Setor (*value[go.shape.string_0]).Set。
　　目前，由于编译器仅使用字典（从不使用纯模板），因此通常出现在可执行文件中的唯一函数名称是由形状类型实例化的函数和方法。如果需要必须包含对这些完全实例化方法的引用的 itab，则可能会出现一些由具体类型实例化的方法（请参阅下面的＂Itab 字典包装器＂部分）
　　字典的命名与关联的实例化函数或方法类似，但前缀为＂.dict＂。因此，示例包括：.dict.Max[float64]和.dict.(*value[int]).get。字典总是为一组具体的类型定义的，因此字典名称中永远不会有任何类型参数或形状类型。
　　包含在实例化函数和方法名称中的具体类型名称以及字典名称是完全指定的（包括包名称，如果不是内置包）。因此，实例化函数、实例化方法和字典名称是唯一指定的。因此，它们可以根据需要在任何包中按需生成，并且链接器将自动对同一函数、方法或字典的多个实例进行重复数据删除。 Itab 字典包装器
　　对于泛型函数或泛型方法的直接调用，编译器会在调用适当的形状实例化时自动添加一个额外的初始参数，即所需的字典。该字典可能是对静态字典的引用（如果具体类型是静态已知的），也可能是对包含函数字典的子字典的引用。如果创建了函数值、方法值或方法表达式，则编译器将在调用函数或方法值或方法表达式时自动创建一个闭包，该闭包使用正确的字典调用适当的形状实例化。在生成完全实例化的泛型类型的 itab 的每个条目时，需要一个类似的闭包包装器，因为 itab 条目必须是一个接受适当接收器和其他参数的函数， 对通用函数和方法的调用的编译器处理
　　大多数泛型特定处理发生在编译器的前端。 Types2 类型检查器（新） - types2-typechecker 是一个新的类型检查器，可以对通用程序进行完整的验证和类型检查。它被编写为独立于编译器的其余部分，并将其计算的类型检查信息传递给一组映射中的编译器的其余部分。 节点通道（预先存在，但完全重写以使用 type2 类型检查器信息） - 节点通道创建当前包中所有函数/方法的 ir.Node 表示。我们为通用和非通用函数创建节点表示。我们使用来自 types2-typechecker 的信息来设置每个节点的类型。泛型函数中的各种节点可能具有依赖于类型参数的类型。对于非泛型函数，我们执行与旧类型检查器相关的正常转换，如上所述。我们不对泛型函数进行转换，因为许多转换依赖于具体的类型信息。
　　在 noding 期间，我们记录源代码中已经存在的每个完全实例化的非接口类型。例如，任何函数（泛型或非泛型）都可能碰巧指定了类型为＂ List[int]＂的变量。我们在导入需要的函数体时做同样的事情（或者因为它是一个将被实例化的通用函数，或者因为它是内联所需要的）。
　　可导出的泛型函数的主体总是被导出，因为导出的泛型函数可能会被调用，因此需要在引用它的任何其他包中实例化。类似地，可导出泛型类型的方法体也总是被导出，因为每当泛型类型被实例化时，我们都需要实例化这些方法。如果未导出的泛型函数和类型被可内联函数引用，则可能需要导出它们（请参阅 参考资料crawler.go） Scan pass (new) - 遍历所有非泛型函数和实例化函数，以查找对泛型函数/方法的引用。在任何此类引用中，它都会创建所需的形状实例化（如果在当前编译期间尚未创建）并将引用转换为使用形状实例化并传入适当的字典。扫描过程在所有新创建的实例化函数/方法上重复执行，直到不再创建实例化。 在扫描通道的每次迭代开始时，我们为自扫描通道的最后一次迭代（或节点通道，在扫描通道的第一次迭代）。这确保了在创建运行时类型描述符和 itab 时所需的方法实例化可用，包括字典中所需的 itab。 对于正在扫描的函数中对通用函数/方法的每个引用，我们确定类型参数的 GC 形状。如果我们还没有使用这些形状参数创建所需的实例化，我们通过在通用函数头和主体上进行类型替换来创建实例化。泛型函数可能来自另一个包，在这种情况下我们需要导入它的函数体。一旦我们创建了实例化，我们就可以确定相关字典的格式。我们用所需的字典参数调用所需的实例化（可能在闭包中）替换对通用函数/方法的引用。如果引用位于非泛型函数中，则所需的字典参数将是顶级静态字典。如果引用在形状实例中，那么字典参数将是包含函数字典中的子字典条目。我们使用字典格式信息按需计算顶级字典（及其所有所需的子字典，递归）。 与节点通行证一样，我们记录创建的任何新的完全实例化的非接口类型。在扫描通道的情况下，由于类型替换，将创建此类型。通常，它将用于派生类型的字典条目。如果我们在某些情况下进行纯模版，那么在纯模版函数（没有字典）中创建具体类型时会发生类似的情况。 字典传递（新） - 传递所有实例化函数/方法，这些函数/方法转换需要字典条目的操作。这些操作包括对类型参数绑定的方法的调用、参数化类型到接口的转换以及参数化类型上的类型断言和类型切换。此通道必须是单独的（在扫描通道之后），因为我们必须在进行任何这些转换之前确定实例化的字典格式。字典传递通常转换这些操作以访问字典中的特定条目（它是运行时类型或 itab），然后以特定方式使用该条目。
　　关于内联，有一个有趣的阶段排序问题。目前，我们尝试在 noding 之后立即对泛型进行所有处理，因此对编译器的其余部分的影响很小。我们大部分都成功了——在字典传递之后，实例化的函数被视为正常的类型检查代码，并且可以正常进一步处理和优化。但是，内联传递可以通过新的内联函数引入新代码，并且新代码可以引用具有新实例化类型的变量并调用该变量的方法或将变量存储在接口中。因此，我们可能需要在内联过程中创建新的实例化。
　　但是，如果在导出引用实例化类型 I 的可内联函数的主体时，我们可以避免阶段排序问题，同时也导出与类型 I 相关的任何所需信息。这样，我们将在内联期间获得必要的信息一个没有完全重新创建实例化类型 I 的新包。一种方法是完全导出这种完全实例化的类型 I。但是这种方法过于复杂，并且会以丑陋的方式改变导出格式。最干净的方法（也是我们使用的）是只导出 I 的方法所需的形状实例化和字典。类型 I 和 I 方法的包装器将被重新创建（并删除重复数据） ) 在导入端，但不需要任何额外的实例化过程（创建形状实例化或字典），