Don’t Write, but Return: Replacing Output Parameters with Algebraic Data Types in C-to-Rust Translation
Open Access
- 20 June 2024
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (PLDI) , 716-740
Abstract
Translating legacy system programs from C to Rust is a promising way to enhance their reliability. To alleviate the burden of manual translation, automatic C-to-Rust translation is desirable. However, existing translators fail to generate Rust code fully utilizing Rust’s language features, including algebraic data types. In this work, we focus on tuples and Option/Result types, an important subset of algebraic data types. They are used as functions’ return types to represent those returning multiple values and those that may fail. Due to the absence of these types, C programs use output parameters , i.e., pointer-type parameters for producing outputs, to implement such functions. As output parameters make code less readable and more error-prone, their use is discouraged in Rust. To address this problem, this paper presents a technique for removing output parameters during C-to-Rust translation. This involves three steps: (1) syntactically translating C code to Rust using an existing translator; (2) analyzing the Rust code to extract information related to output parameters; and (3) transforming the Rust code using the analysis result. The second step poses several challenges, including the identification and classification of output parameters. To overcome these challenges, we propose a static analysis based on abstract interpretation, complemented by the notion of abstract read/write sets , which approximate the sets of read/written pointers, and two sensitivities: write set sensitivity and nullity sensitivity . Our evaluation shows that the proposed technique is (1) scalable, with the analysis and transformation of 190k LOC within 213 seconds, (2) useful, with the detection of 1,670 output parameters across 55 real-world C programs, and (3) mostly correct, with 25 out of 26 programs passing their test suites after the transformation.Keywords
Funding Information
- National Research Foundation of Korea (2022R1A2C200366011,2021R1A5A1021944)
- Institute for Information and Communications Technology Promotion (2022-0-00460,2023-2020-0-01819)
- Samsung Electronics Co., Ltd (G01210570)
This publication has 29 references indexed in Scilit:
- Ownership Guided C to Rust Translation2023
- Concrat: An Automatic C-to-Rust Lock API Translator for Concurrent Programs2023
- RustyHermit: A Scalable, Rust-Based Virtual Execution Environment2020
- Control-flow analysis of functional programsACM Computing Surveys, 2012
- Pick your contexts well2011
- Resolving and exploiting the k -CFA paradox2010
- Semi-sparse flow-sensitive pointer analysis2009
- The trace partitioning abstract domainACM Transactions on Programming Languages and Systems, 2007
- Trace Partitioning in Abstract Interpretation Based Static Analyzers2005
- Parameterized object sensitivity for points-to analysis for JavaACM Transactions on Software Engineering and Methodology, 2005