一句话：提出基于合一的类型推断框架，恢复 C 程序中缺失的 struct、union、enum 与 typedef 声明，用于重建部分程序。
类型推断在函数式语言以及 C#、C++ 等语言中已有广泛应用，但在 C 语言领域仍属空白，主要困难在于解析 C 不仅需要语法信息还需要语义信息，且 C 的类型系统错综复杂。本文提出一个基于合一（unification）的框架，能够推断程序中缺失的 struct、union、enum 和 typedef 声明，并以此作为应用场景研究部分程序的重建：不完整源码在软件设计、演化、测试与分析中普遍存在，重建出良类型的程序后可（i）在组件缺失时启用静态分析工具，（ii）提升“零配置”静态分析工具的精度，（iii）对代码片段应用桩生成器、符号执行器与测试工具，（iv）为工程师提供可编译的基准用于性能与正确性验证。作者在来自多个 C 库的代码上评估该技术，包括 GNU Coreutils，以及 CPython、FreeBSD 和 Git 等流行项目的代码片段。
Type inference is a feature that is common to a variety of programming languages. While, in the past, it has been prominently present in functional ones (e.g., ML and Haskell), today, many object-oriented/multi-paradigm languages such as C# and C++ offer, to a certain extent, such a feature. Nevertheless, type inference still is an unexplored subject in the realm of C. In particular, it remains open whether it is possible to devise a technique that encompasses the idiosyncrasies of this language. The first difficulty encountered when tackling this problem is that parsing C requires, not only syntactic, but also semantic information. Yet, greater challenges emerge due to C’s intricate type system. In this work, we present a unification-based framework that lets us infer the missing struct, union, enum, and typedef declarations in a program. As an application of our technique, we investigate the reconstruction of partial programs. Incomplete source code naturally appears in software development: during design and while evolving, testing, and analyzing programs; therefore, understanding it is a valuable asset. With a reconstructed well-typed program, one can: (i) enable static analysis tools in scenarios where components are absent; (ii) improve precision of “zero setup” static analysis tools; (iii) apply stub generators, symbolic executors, and testing tools on code snippets; and (iv) provide engineers with an assortment of compilable benchmarks for performance and correctness validation. We evaluate our technique on code from a variety of C libraries, including GNU’s Coreutils and on snippets from popular projects such as CPython, FreeBSD, and Git.
@article{MeloRGP20,
title = {Type Inference for C},
author = {Leandro T. C. Melo and Rodrigo G. Ribeiro and Breno C. F. Guimarães and Fernando Magno Quintão Pereira},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {42},
number = {3},
year = {2020},
doi = {10.1145/3421472}
}