Rust: Type inference for tuples #20041

paldepind · 2025-07-14T14:38:28Z

Implements type inference for tuples. More specifically tuple expressions (e.g., (1,2)), tuple indexing (e.g., tuple.1), and pattern matching on tuples.

Pattern matches with .. in them are not supported.

DCA shows a 1.12% point increase in resolved method calls, type inference inconsistencies is down, and performance seem unaffected.

Type parameters are required to belong to a single type only. Since we store the arity for tuple types, we need to store the arity in tuple type parameters as well such that we can associate them to the tuple type of the same arity.

Copilot

Pull Request Overview

This PR implements type inference for tuples in Rust, extending the type system to handle tuple expressions, tuple indexing, and pattern matching on tuples. The changes enable the type inference engine to correctly track type information through tuple creation, field access, and destructuring patterns.

Adds support for tuple types and tuple type parameters in the type system
Implements type inference for tuple expressions, indexing, and pattern matching
Updates type mentions to handle tuple type representations

Reviewed Changes

Copilot reviewed 9 out of 9 changed files in this pull request and generated no comments.

Show a summary per file

File	Description
rust/ql/lib/codeql/rust/internal/Type.qll	Defines tuple types and tuple type parameters
rust/ql/lib/codeql/rust/internal/TypeInference.qll	Implements tuple type inference logic
rust/ql/lib/codeql/rust/internal/TypeMention.qll	Adds tuple type representation mentions
rust/ql/test/library-tests/type-inference/type-inference.expected	Test file with .expected extension
rust/ql/test/library-tests/type-inference/pattern_matching.rs	Updates test expectations for tuple patterns
rust/ql/test/library-tests/type-inference/main.rs	Updates test expectations for tuple expressions
rust/ql/test/library-tests/dataflow/local/DataFlowStep.expected	Test file with .expected extension
rust/ql/test/library-tests/dataflow/local/CONSISTENCY/PathResolutionConsistency.expected	Test file with .expected extension
rust/ql/src/change-notes/2025-07-15-type-inference-tuples.md	Changelog entry

aibaars

Looks good to me overall. I have some questions and suggestions. Also could you add a test case like the following where the type information has to flow from a pattern match to other uses and the definition:

        let pair = 1.into();
        match pair {
            (0,0) => print!("unexpected");
        }
        let x = pair.0;

aibaars · 2025-07-15T14:14:46Z

rust/ql/lib/codeql/rust/internal/Type.qll

  TEnum(Enum e) or
  TTrait(Trait t) or
  TArrayType() or // todo: add size?
  TRefType() or // todo: add mut?
  TImplTraitType(ImplTraitTypeRepr impl) or
  TSliceType() or
+  TTupleTypeParameter(int arity, int i) { exists(TTuple(arity)) and i in [0 .. arity - 1] } or


This way of defining arity would make TType's definition recursive, right? Not sure if that is a problem, but we might want to avoid it.

Good question. No recursion markers show up in VScode, so I think what's happening is that TTuple is materialized first and then TTupleTypeParameter is materialized. So TTupleTypeParameter depends on TTuple but there is no recursion. I'm just guessing though so maybe I'm wrong.

It's fine with me, @hvitved once commented on a case where I defined a recursive type where it wasn't necessary. Not sure if it is a problem here though. In any case if it's easy to rewrite if it turns out to be a problem.

Agree. Let's keep it and change it if it's actually suboptimal.

aibaars · 2025-07-15T14:17:05Z

rust/ql/lib/codeql/rust/internal/Type.qll

+class TupleType extends Type, TTuple {
+  private int arity;
+
+  TupleType() { this = TTuple(arity) and arity > 0 }


Why the restriction that arity must be non-zero? Isn't () just a 0-arity tuple? See also: https://doc.rust-lang.org/reference/types/tuple.html

Suggested change

TupleType() { this = TTuple(arity) and arity > 0 }

TupleType() { this = TTuple(arity) }

Yes, lets do that! I wanted to have a class UnitType since I think it's useful to have that concept named, but making it a subclass of tuple still accomplices that and is nicer 👍

aibaars · 2025-07-15T14:17:32Z

rust/ql/lib/codeql/rust/internal/Type.qll

@@ -56,8 +60,8 @@ abstract class Type extends TType {
 }

 /** The unit type `()`. */
-class UnitType extends Type, TUnit {
-  UnitType() { this = TUnit() }
+class UnitType extends Type, TTuple {


Suggested change

class UnitType extends Type, TTuple {

class UnitType extends TupleType, TTuple {

aibaars · 2025-07-15T14:31:25Z

rust/ql/lib/codeql/rust/internal/Type.qll

+  /** Gets the arity of this tuple type parameter. */
+  int getArity() { result = arity }


TypeParameters don't really have an arity, right? Do we need this method for anything? Perhaps it should be replaced by

TypeType getTupleType() { result = TTuple (arity) }

aibaars · 2025-07-15T14:35:19Z

rust/ql/lib/codeql/rust/internal/Type.qll

+  TTuple(int arity) {
+    arity = any(TupleTypeRepr t).getNumberOfFields() and
+    Stages::TypeInferenceStage::ref()
+  } or


Shouldn't we also include tuple patterns and tuple expression in addition to tuple type reprs?

Suggested change

TTuple(int arity) {

arity = any(TupleTypeRepr t).getNumberOfFields() and

Stages::TypeInferenceStage::ref()

} or

TTuple(int arity) {

(

arity = any(TupleTypeRepr t).getNumberOfFields() or

arity = any(TupleExpr e).getNumberOfFields() or

arity = any(TuplePat p).getNumberOfFields()

) and

Stages::TypeInferenceStage::ref()

} or

aibaars · 2025-07-15T14:41:45Z

rust/ql/lib/codeql/rust/internal/Type.qll

+ *  their positional index.
+ */
+class TupleTypeParameter extends TypeParameter, TTupleTypeParameter {
+  private int arity;


Is it really necessary to have arity as a field? Is it important to distinguish the first element of a pair from the first element of a triple?

Unintuitively the answer is yes. Before 7c04c9f arity was not in TupleTypeParameter. But the type inference library relies on the assumption that every type parameter corresponds to exactly one type, so not having the arity caused problems.

I've noted this in the QLdoc for TupleTypeParameter now.

Thanks, I was wondering this as well.

aibaars · 2025-07-15T14:49:37Z

rust/ql/lib/codeql/rust/internal/TypeInference.qll

+
+/** Infers the type of `t` in `t.n` when `t` is a tuple. */
+private Type inferTupleContainerExprType(Expr e, TypePath path) {
+  // NOTE: For a field expression `t.n` where `n` is a number `t` might both be


I don't really understand this comment. I think the following is perfectly fine in rust

struct Pair (i32, u64) ; let x = (Pair (1,2)).1;

Yes, that is the problem :) In let i: i64 = foo.1 we cannot say from looking at this syntactically that foo has i64 as it's second tuple element, exactly because it could also be a tuple struct. But if foo is a tuple then we want to make that conclusion.

I've expanded on the comment. Let me know if it is still not clear enough.

rust/ql/lib/codeql/rust/internal/TypeInference.qll

aibaars · 2025-07-15T14:58:37Z

rust/ql/lib/codeql/rust/internal/TypeInference.qll

@@ -1055,6 +1079,31 @@ private Type inferFieldExprType(AstNode n, TypePath path) {
  )
 }

+pragma[nomagic]
+private Type inferTupleIndexExprType(FieldExpr fe, TypePath path) {


This looks fine to me, although I had expected something more similar to inferFieldExprType (or even integrated into that predicate). Or do things really work differently for named fields compared to numeric fields?

I looked into that, but inferFieldExprType uses the Matching module which is about propagating type info from declarations. Tuple types need not correspond to any declaration, so they're different enough that I don't see a clear way to handle them in inferFieldExprType.

rust/ql/test/library-tests/type-inference/pattern_matching.rs

paldepind · 2025-07-16T07:48:58Z

Thanks for the review. I think I've addressed the suggestions and questions.

Also could you add a test case like the following where the type information has to flow from a pattern match to other uses and the definition:

Done. This also uncovered a gap in the implementation. We never inferred the root tuple type itself from a tuple pattern, only the type of the elements.

geoffw0

Looks great, I'll have a look at the DCA results as well when that's done...

rust/ql/test/library-tests/type-inference/main.rs

rust/ql/test/library-tests/type-inference/pattern_matching.rs

geoffw0 · 2025-07-16T08:28:28Z

rust/ql/lib/codeql/rust/internal/Type.qll

+ *  their positional index.
+ */
+class TupleTypeParameter extends TypeParameter, TTupleTypeParameter {
+  private int arity;


Thanks, I was wondering this as well.

rust/ql/test/library-tests/type-inference/main.rs

Co-authored-by: Arthur Baars <aibaars@github.com>

paldepind · 2025-07-18T06:43:20Z

The status of this PR is that it's currently blocked as it causes analysis on databend to explode. I'm investigating the performance issue which is either caused or exposed by this PR.

paldepind added 2 commits July 14, 2025 16:24

Rust: Expand on type inference test for tuples

21c030f

Rust: Add type inference for tuples

03a9a16

github-actions bot added the Rust Pull requests that update Rust code label Jul 14, 2025

paldepind added 3 commits July 15, 2025 09:50

Rust: Store arity in tuple type parameters

7c04c9f

Type parameters are required to belong to a single type only. Since we store the arity for tuple types, we need to store the arity in tuple type parameters as well such that we can associate them to the tuple type of the same arity.

Rust: Accept test changes

97e7794

Rust: Add a change note

8858f21

github-actions bot added the documentation label Jul 15, 2025

paldepind marked this pull request as ready for review July 15, 2025 09:11

Copilot AI review requested due to automatic review settings July 15, 2025 09:11

paldepind requested a review from a team as a code owner July 15, 2025 09:11

Copilot AI reviewed Jul 15, 2025

View reviewed changes

aibaars reviewed Jul 15, 2025

View reviewed changes

Rust: Improvements to tuple type inference based on PR feedback

a508089

geoffw0 reviewed Jul 16, 2025

View reviewed changes

Rust: Add inline expectation

bbd7ed5

aibaars reviewed Jul 16, 2025

View reviewed changes

rust/ql/test/library-tests/type-inference/main.rs Outdated Show resolved Hide resolved

Rust: Add additional inline expectation

7f8829a

Co-authored-by: Arthur Baars <aibaars@github.com>

	TupleType() { this = TTuple(arity) and arity > 0 }
	TupleType() { this = TTuple(arity) }

	class UnitType extends Type, TTuple {
	class UnitType extends TupleType, TTuple {

		/** Gets the arity of this tuple type parameter. */
		int getArity() { result = arity }

Rust: Type inference for tuples #20041

Are you sure you want to change the base?

Rust: Type inference for tuples #20041

Conversation

paldepind commented Jul 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull Request Overview

Reviewed Changes

Uh oh!

aibaars left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

paldepind commented Jul 16, 2025

Uh oh!

geoffw0 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

paldepind commented Jul 18, 2025

Uh oh!

Uh oh!

paldepind commented Jul 14, 2025 •

edited

Loading