Abstract

摘要：当将一组新类型引入大型软件系统时，改造该系统以利用这些类型的任务通常成本高昂。 现有的自动类型迁移系统假定旧类型和新类型之间是一对一的对应关系，这使得它们无法对更复杂的类型集进行部分迁移。 通过使用基于编译器的迁移工具和代数建模的类型集，可以使用少量手动播种的类型信息通过大型单片 C++ 代码库自动传播新类型。 我们通过在包含数百万行 C++ 的大型工业代码库中自动生成 20k 多个单独的更改来演示此技术。
索引词——类型推断、重构、软件维护

I. INTRODUCTION

强类型通过限制格式良好的程序可以执行的操作来帮助软件工程师 [1]。 当引入新的类型集时，工程师可以使用它们来编写更明确指定的程序，避免在编译时出现错误，而不是依赖于测试或运行时发现 [2]。 现有的遗留系统不会立即受益于新类型的改进约束。 例如，现有软件可能使用整数类型来表示位置和速度，但是一组新的类型可以将这两个概念表示为单独的类型，它们之间有一组受约束的操作，以提高程序的正确性。

将现有系统迁移到新类型是一个称为类型迁移的过程。 存在许多允许跨有限代码集的自动单一类型迁移的工具。 这种类型迁移模型假设新类型可以直接映射到旧类型，即它们之间的关系是一对一的。 对于更复杂的类型集，该假设不再成立。 在上面的示例中，位置和速度将被建模为两种不同的类型，并且任何类型迁移都需要推断给定整数在语义上有意义的上下文，如速度或距离，或两者都不是。 该工具还需要考虑其他数字类型的输入，例如浮点值。

最近，Google 采用类型来更正确地对我们的 C++ 代码库中的时间瞬间和间隔的概念进行建模。 这些类型基于时间瞬间作为一维仿射空间中的点以及时间间隔作为该空间中的向量的数学模型。 使用这种时间类型的代数模型，我们实现了可以从现有程序语法推断类型语义的自动化工具。这种技术帮助工程师正确使用类型新代码，还允许我们在整个 250M 行 C++ 中更新现有的遗留代码。

在本文中，我们介绍了我们在从数字类型到新引入的时间类型集进行这种迭代的大规模类型迁移的经验的案例研究，使用不同变量之间的关系来推断和传播类型信息。 从少量手动放置的初始信息（称为种子）中，我们展示了类型信息如何传播到其他变量，而不仅仅是通过函数调用层次结构从调用者线性传播到被调用者。 虽然这种技术依赖于现有代码在语义上正确的假设，但它也拓宽了传统类型迁移的范围，并扩展到大型代码库。

我们使用 clang 项目的 LibTooling 基础设施 [3] 之上的 clang-tidy 分析和迁移框架将我们的方法实现为一组开源工具。 使用这些工具，我们成功地对 Google 的 2.5 亿行生产 C++ 代码的语料库应用了超过 2 万次单独的更改，并在此过程中发现了数十个潜在的错误。

开始这项工作时，我们的目标是探索将部分类型迁移应用到我们的大型 C++ 代码库的可行性，并证明迭代渐进类型推断在静态类型语言中是合理的。 具体来说，我们还希望在使用与时间相关的结构时使现有的 C++ 代码库更安全，发现代码库中的现有缺陷并通过使代码更易于编写来防止未来的缺陷。 我们希望分享我们在工业环境中大规模进行这些转型的经验，包括我们遇到的限制，具有广泛的用途。

MOTIVATING EXAMPLE

image.png

III. TIME TYPE SET

type set 只是相关类型的集合。 尽管任何类型的集合都满足这个广泛的定义，但为了对迁移有用，类型集应该体现一个特定的数学模型，该模型定义了集合中类型之间的有效操作。 一个简单的例子是 C++ 指针和整数。 C++ 标准定义了指针类型和整数之间的算术运算，以底层数字运算为模型，但某些运算（例如两个指针相加）是未定义的。

A. Abseil Time Library

Abseil Time Library 将时间瞬间和间隔的类型集分别定义为 absl::Time 和 absl::Duration。 该库还定义了以类型安全的方式实现已定义操作的运算符，并省略了那些未由底层代数定义的操作。 这种类型安全性提高的结果是一种自然的方式来计算时间间隔和瞬间，并且由于编译时强制执行而减少了运行时错误。 Abseil Time Library 的完整描述可以在其公共存储库中找到 [5]。

为了帮助从现有代码库迁移，并提供与遗留系统的互操作性，Abseil Time 还提供了与 absl::Time 和 absl::Duration 类型之间的转换功能。 表 I 列出了这些函数的选择。这些函数允许系统逐步迁移到新类型，这在对大型系统进行非原子重构时很重要 [6]。
image.png

这些函数在六种不同的固定长度尺度上运行：小时、分钟、秒、毫秒、微秒和纳秒。 为简洁起见，我们将在大多数示例中省略小时、微秒和纳秒，但它们的迁移技术类似于其他尺度。

B. Time Algebra

在本文中，我们讨论了两种类型，它们代表两个不同但相关的概念：时间瞬间 time instant 和时间间隔 time interval。 在数学上，这些是一维仿射空间的一部分，时间瞬间作为该空间中的点，时间间隔作为该空间中的向量。 Abseil Time 库定义了在该类型集之间和之间以及在该类型集内有效的各种操作，总结在表 II 中。 正是这些代数关系，我们稍后将其用于进行类型推断，作为我们类型迁移的一部分。
image.png

这种数学关系意味着除了加法和减法之外的运算。 例如，标量的乘法和除法是为 absl::Duration 定义的，但为 absl::Time 未定义。 因为时间间隔和时刻是有序的，所以也定义了相似类型之间的关系比较。 absl::Duration 工厂函数也分布在数学运算和其他 C++ 语言结构中。 一些附加操作的例子总结在表 III 中。
image.png

有了足够的现有类型信息，我们可以使用这种类型代数推导出有关周围代码的附加类型信息。 例如，如果我们知道一个结果加法表达式是一个absl::Time，并且它的第一个操作数也是一个absl::Time，我们可以推断出第二个操作数在语义上是一个时间间隔，而不管它声明的类型。 我们将在第四节探讨这些扣除的含义。

C. Compiler-Based Transformations

我们的工具使用基于编译器的技术来可扩展地匹配程序抽象语法树 (AST) 中的模式并生成建议的更改。 这个过程可以有效地并行化以在多台机器上大规模运行，从而实现对数百万行代码的全系统分析。 对于 C++，我们使用了一系列基于 clang-tidy 静态分析基础架构的工具，这些工具可以使用 ClangMR 架构进行并行化 [7]。

使用 Clang 的 AST 匹配器库，我们可以有效地匹配 AST 中节点的特定模式。 匹配节点后，我们使用有关该节点及其周围环境的语义信息来转换其文本。 这种技术在进行类型转换时变得很强大，因为我们可以查找特定的表达式，然后检查它们的上下文以确定适当的转换应该是什么。 例如，如果一个变量的类型正在改变，它的引用也必须改变，但如何做到这一点取决于它是用作左值还是右值——在基于 AST 的工具中可用的信息，但不是 在基于文本的。

这些工具在审查时显示这些修复有助于防止旧模式的新用法重新进入我们的代码库，并确保继续应用良好的模式。 我们对 Abseil Time 库的 clang-tidy 检查集是开源的，可作为大型 clang-tidy 工具套件的一部分 [9]。

IV. TRANSFORMATION PROCESS

我们现在描述将数值类型（例如 int 和 double）转换为 Abseil Time 类型 absl::Time 和 absl::Duration 的过程。 因为这不是一对一的映射，所以我们使用第 III-B 节中描述的代数从现有语法中推断语义并执行部分类型迁移。 随着这些工具的迭代应用，它们将有关时间类型集的初始少量信息传播到数百万行代码中。

A. Symbol Names

首先，我们注意到一个用于推断时间类型信息的诱人但徒劳的途径：符号名称 Symbol Names 。 许多函数和变量通过它们的名称暗示它们的时间类型语义。函数名称（ DeadlineSeconds 和 GetSecondsSinceYesterday），以及变量名称（deadline_sec） 似乎表明这些对象可以无条件地转换为 absl::Duration ，不用关心上下文。

我们发现，这种转换是不可取的，因为函数或变量名称不足以明确确定所讨论的值是时间间隔还是时间瞬间。 进行错误的转换通常比不进行转换更糟糕，因为转换过程的迭代性质意味着这样的错误会传播到整个软件系统。 在这些情况下，我们会等到更多上下文可用以确定正确的转换。

B. Transformation Categories

第 III-B 节中的 time algebra 允许我们列举仅使用部分类型信息可以执行的不同可能转换。 我们展示了为什么它们等同于使用整数的表达式，然后展示了这些转换的局限性。 表 IV 列出了各种转换及其用途，本节的其余部分将详细描述每一种转换。
image.png

1. Expression-based Transformations

我们将第一类转换函数称为基于表达式的转换，因为它们使用单个可用的信息传播类型信息的表达式。 由于表达式通常包含对多个变量的引用，因此这些转换有助于推导表达式中相关变量的信息，提供一种将类型信息传播到最初使用强类型声明的变量之外的机制。

a. Comparison : 当一个时间间隔与某个其他值进行比较时，我们推断该值也必须是一个时间间隔，然后从所使用的转换函数的比例推导出间隔的比例。 我们将此转换称为 DurationComparison，并将其应用于任何布尔上下文。 清单 2 中显示了一个示例。
image.png

在 absl::Duration 域中执行比较在语义上更正确，因为它更精确——定义了溢出和饱和的行为——并且更好地匹配了代码的语义意图。 稍后我们可以使用清单 2 中的结果来推断有关 deadline_seconds 变量的信息，这是我们在第 IV-B2 节中使用的事实。

虽然我们在此示例中使用 absl::Duration，但同样的原则适用于对 absl::Time 比较的自动转换，我们称之为 TimeComparison。 虽然我们在示例中使用秒刻度，但此示例和其他示例的工具适用于 Abseil Time 支持的所有时间刻度。

b. Subtraction and Addition : 从表 II 中，我们注意到为 absl::Duration 和 absl::Time 类型的几种组合定义了减法。 使用减法表达式中可用的部分类型信息，我们推断出有关表达式其他成员的信息。 例如，清单 3a 中的减法表达式有一个 absl::Duration 结果，第一个操作数是从 absl::Time 转换而来的。 使用来自表 II 的类型信息，我们推断第二个操作数也必须表示一个时间瞬间。 从这个推论中，我们应用了一个转换，它使用原生的 Abseil Time 类型执行减法运算，并避免了整个表达式的最终转换。 我们将此转换称为减法，结果如清单 3b 所示。
image.png

需要注意的是，仅知道上例中第一个操作数的类型不足以进行正确的转换：我们不能在不知道结果的情况下从表 II 推断出第二个操作数的类型（或在不知道结果的类型的情况下） 第二个操作数的）。 但是，在我们知道第二个操作数是 absl::Time 的情况下，我们有足够的信息来推断第一个操作数和结果的类型，因为从 absl::Duration 中减去 absl::Time 是未定义的。

加法转换以与减法转换类似的方式推断信息。 与 DurationComparison 和 TimeComparison 非常相似，这些转换允许在单独的变量或子表达式之间传播类型信息，这对于通过软件系统进行广泛类型传播的总体目标至关重要。

c. Local Canonicalizations: 最后一组基于表达式的转换执行本地规范化。 虽然这些在传播类型信息方面没有直接作用，但它们简化了现有的 absl::Time 和 absl::Duration 表达式，以使基于 AST 的模式匹配器更简单并匹配更全面的候选集。 清单 4 中显示的每个表达式都可以简化，因此我们不是在每个转换工具中处理所有这些情况，而是使用单独的工具将代码库同质化为最简单的表达式。
image.png

2. Local Variable Transformations

在应用上述基于表达式的转换之后，我们可以扩展我们的范围以查看在同一函数中跨越表达式的更改。 这些转换属于单一类别：局部变量类型更改。

考虑清单 5a 中的函数——它可能是先前应用 DurationComparison 的结果。 我们从第 3 行中对 absl::Seconds 的使用推断出变量 x 被解释为秒数。 使用此信息，我们更改 x 的类型，并使用适当的转换函数更新其所有引用以维护函数的现有语义，如清单 5b 所示。

image.png

我们将此转换称为 DurationLocalVariable，在 absl::Time 域中具有 TimeDurationVariable 的模拟。 一般来说，我们通过两种方式识别候选变量。

首先，我们查找通过调用 absl::Duration 转换函数（例如 absl::ToDoubleSeconds）初始化或分配的变量。 其次，我们寻找用作 absl::Duration 工厂函数的参数的变量，如清单 5a 中的 x 情况。 最后，我们通过消除获取地址的变量来修剪候选列表，因为工具还不够强大，无法处理指针的转换，只有值。

这种识别方法是保守的，因为它只找到当前在 Abseil Time 上下文中使用的变量。 我们更喜欢这种保守的方法，因为它避免了错误的推断，并可能在程序中进一步传播错误的时间信息。

DurationLocalVariable 是基于 AST 的工具如何使类型集迁移成为可能的一个示例。 AST 中的上下文提供了有关如何转换对变量的每个引用的信息。 例如，作为赋值结果的变量引用应该将转换函数应用于它们被分配到的表达式，而用作右值的引用本身应该包含在转换函数中。 语言的某些部分，例如 lambda 捕获列表，保持不变

我们在试点过程的早期发现，人工审阅者更喜欢某些变量名称的更改以及类型的更改。 因此，如果 DurationLocalVariable 工具可以推断出名称被用于表示某个比例，则它会更新变量名称。 因此，deadline_seconds 变成了最后期限，但 sleep_interval 保持不变。 结果是对人类读者来说看起来更自然的代码。

3. Interfunction Transformations

基于表达式的转换和局部变量转换的组合可以将类型信息推送到函数的边界：作为参数的输入和作为返回值的输出。 从这里，我们可以通过识别和更改函数参数来继续通过我们的系统推送类型信息类型和返回类型，以及相关的调用者，使用传统的数据流和类型推断技术。

a) Function Parameters

我们可以像识别局部变量一样识别转换的函数参数候选者：查找通过调用函数中的 absl::Duration 转换函数初始化或分配的参数，或查找用作参数的参数 absl::Duration 工厂函数。 也可以使用函数外部的信息来识别参数迁移候选者：如果使用本身是从 absl::Duration 转换的参数调用函数，我们知道参数可以迁移。 清单 6 中给出了一个示例
image.png

这种类型的转换对于 absl::Duration 和 absl::Time 类型都是可能的，我们将各自的转换称为 DurationParameter 和 TimeParameter。 更改函数参数的类型会将类型信息传播到函数边界，更重要的是传播到同一函数的其他调用者，这些调用者可能处于完全不相关的上下文中。

我们的代码库的大小禁止以原子方式将所有调用者更改为所有函数。 如果我们无法证明所有调用者都可以在更新函数的同时更改，我们在一次更改中添加适当的重载，然后应用单独的转换 DurationOverload（或用于 absl::Time 参数的 TimeOverload）到 更新调用者以在后续更改中使用新的重载。

添加单独的转换以仅将调用者迁移到新的重载有一个额外的优势：我们可以通过手动添加新的重载来播种 highcaller 函数，然后运行标准转换来迁移它们的调用者。 在我们的案例研究中，我们只植入了 10 个函数，这些函数总共有数以万计的调用者，然后让这些信息通知其余的转换。

b) Return Types

与函数参数一样，我们可以从函数的内部和外部使用信息识别返回类型迁移候选者。 如果函数的返回值是从函数的 return 语句内的 absl::Duration 转换的，或者如果从函数返回的值在调用点转换为 absl::Duration，则该函数是 DurationReturn 的合理候选者 转换（或 TimeReturn 如果值从或转换为 absl::Time 值）。 与 DurationParameter 一样，必须同时更改函数及其调用者。 清单 7 显示了 TimeReturn 转换的示例。

image.png
c) Class Variables

最后一类支持的函数内转换涉及类变量。 我们将这些转换（DurationClassVariable 和 TimeClassVariable）限制为私有变量，以便我们可以在单个翻译单元中查看它们的所有引用。

与其他函数内转换一样，更改私有变量的类型允许对这些变量的其他引用来推断有关其封闭表达式的类型特征的更多信息，如清单 8 所示。

C. Iteration

关于转换减法部分中提出的转换的最后一点说明：我们观察到，由于它们的建设性，它们最好在我们的代码库中迭代运行。 例如，DurationComparison 可能会找到一个 LocalDurationVariable 然后可以迁移的变量，然后它可能会生成一个 Subtraction 可以更改的表达式。 使用定期运行的静态分析框架可以在代码审查期间标记基于表达式的更改，并允许工程师将多个转换组合成一个提交的更改。

结果是一套工具可以在我们的大型 C++ 代码库中持续运行，并且随着时间的推移，使用 Abseil Time 类型使该代码库收敛到更安全的状态。 这种迭代类型的变换导致给定变换集的定点迭代。

V. CASE STUDY

Google 的代码库是代表许多不同类型的开发模式和用法的大量代码集合 [10]。 我们的代码库广泛使用时间概念来表达截止日期和超时。 在本节中，我们将介绍在这个包含 2.5 亿行 C++ 代码的语料库中部署我们的工具的实践经验。 我们还探索了通过此部署过程发现的技术的局限性。

A. Methodology

使用第 III-C 节中提到的分布式分析基础架构，我们在整个 C++ 代码语料库中运行第 IV-B 节中描述的每个转换。 这个过程为跨越整个语料库的每个转换生成了一大组更改。 然后，为了测试和代码审查的目的，这个巨大的变化被沿着单独的项目边界分割。 这些边界通常对应于整体语料库中的各个目录。 然后像对进入我们生产系统的任何其他代码更改一样，对这些子更改中的每一个进行测试和审查。

出于我们评估中的实际原因，我们将自己限制为 50 个未决的同时未决更改。 我们还将精力集中在特定的转换上，而不是尝试同时在代码库上运行所有这些转换。 在几个月的过程中，这个过程产生了数千个单独的更改，这些更改已提交到我们的生产 C++ 代码库。 表 V 显示了每个转换的已提交更改数量的摘要。

image.png

因为我们在将相同转换的更改发送给各个团队时将它们分组在一起，所以表 V 中的结果是我们的工具产生的离散编辑数量的下限。 由于我们的源代码控制系统中的跟踪缺陷，这些数字还忽略了作为预审测试或自动静态分析的一部分所做的更改。

DurationOverload 更改的数量在总结果中占主导地位，主要是因为它是第一个启动运行的更改。回想一下，要启动该过程，我们手动将重载添加到高调用函数，然后使用 DurationOverload 将初始类型信息传播到整个代码库。 虽然仍然是一个非常粗略的估计，但剩余的变化比 DurationOverload 的变化多 2:1。

1) Correctness

我们使用三种方法来评估我们工具的正确性：编译器、现有单元测试和人工检查。 作为审查过程的一部分，每个生成的更改都通过编译器运行，以确保转换工具产生语法上有效的输出。 当我们发现它没有的案例时，我们以该案例为例来改进我们的工具。

编译后，更改通过我们的单元测试系统运行，该系统不仅运行受给定更改直接影响的测试，还运行受更改传递影响的所有测试 [11]。 结果是产生的变化是语义保留的有力保证。

最后，作为 Google 标准代码审查流程的一部分，每个更改都由人工审查员检查。 超过 97% 的更改得到了审稿人的批准，没有发表评论。 在剩余的更改中，大多数评论者建议在手头的转换启发下进行额外的改进，有些只是对正在进行的更改进行补充。 在少数情况下，审阅者担心提议的更改，但这几乎总是源于对 Abseil Time 库本身的不熟悉，而不是潜在更改的正确性。

2) Performance

因为我们的转换工具在 AST 上运行，并且来自不同翻译单元的 AST 是独立的，所以我们可以跨翻译单元并行分析。 使用诸如 MapReduce [12] 之类的分析系统，并将我们的分析分片到数千台机器上，可以在不到一个小时的时间内分析我们的 250M 行 C++ 语料库。 将每个独立更改提交到代码库的主要因素不是分析步骤，而是测试和人工审查所花费的时间。

我们继续在我们的代码库中运行自动化工具，以捕获新添加的转换候选实例。 有趣的是，自动更改的接收者在围绕自动转换的区域进行进一步的手动改进而不是等待未来的转换进行这些更改的情况并不少见。 这些改进通常先于一个转换的输出为后续转换生成输入模式的情况，所以这些都没有计入表 V。我们希望当转换达到一个固定点时工作就完成了。

B. Defects Found

这项工作的目的之一是发现并修复因使用数字类型保存时间值而导致的软件缺陷。 我们发现了一些这样的缺陷，尽管发生率低于我们的预期，但确诊病例约为 20 例，缺陷率仅为 0.13%。 我们预计，由于强大的测试文化，语义不匹配错误往往会很快得到解决，并且不会停留在这种类型的分析中。 现有缺陷的数量少并不会降低执行这些更改的价值：Google 的工程师报告说，更明确的类型集使未来的开发更不容易出错，尽管我们没有测量已预防的错误的数量。 在这里，我们重点介绍我们发现的两种常见缺陷模式，以及哪些改进的类型有助于防止：不正确的比例和不正确的类型。

1) Incorrect Scale

从这项工作中出现的一个错误模式是将具有不正确比例的值作为参数传递给函数（参见清单 9）。 函数 func 接受一个将其解释为秒数的数值，但调用函数传递一个以毫秒为单位的值。 这意味着提供给 func 的值比工程师可能预期的值大一千倍。

image.png

在执行 DurationArgument 转换后，func 的参数被包装在一个 absl::Duration 工厂中以进行显式缩放。 这并不能修复错误，因为转换旨在保留行为，但它确实使错误更加明显，使得审阅者很可能会在后续更改中修复错误。

2) Incorrect Type

我们遇到的另一种缺陷是用时间间隔代替时间瞬间，反之亦然。 例如，清单 10 中的代码错误地将一个表示自 Unix 纪元以来的秒数的整数作为时间间隔传递。 调用者无意中提供了大约多年的时间间隔，而不是预期的几秒钟。

经过几次转换后，代码的读者会更加明显地发现错误，然后他们可以独立修复这个。维护语义等价性而不是在发现这些错误时对其进行修复的原因来自于这样的认识，即像这些看似微小的“修复”通常会导致更广泛的系统中出现意想不到的影响，并且这些影响应该与转换本身分开。

C. Limitations

尽管我们现有的转换库很强大，但在某些情况下，我们不能或不能自动转换变量或表达式以进一步传播类型信息，我们将在下面概述。