- Notifications
You must be signed in to change notification settings - Fork1.7k
Rust: Type inference for tuples#20041
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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;
| 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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This way of definingarity would makeTType's definition recursive, right? Not sure if that is a problem, but we might want to avoid it.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Good question. No recursion markers show up in VScode, so Ithink what's happening is thatTTuple is materialized first and thenTTupleTypeParameter is materialized. SoTTupleTypeParameter depends onTTuple but there is no recursion. I'm just guessing though so maybe I'm wrong.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Agree. Let's keep it and change it if it's actually suboptimal.
| class TupleType extends Type, TTuple { | ||
| private int arity; | ||
| TupleType() { this = TTuple(arity) and arity > 0 } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
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
| TupleType(){this=TTuple(arity)andarity>0} | |
| TupleType(){this=TTuple(arity)} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Yes, lets do that! I wanted to have a classUnitType since I think it's useful to have that concept named, but making it a subclass of tuple still accomplices that and is nicer 👍
| @@ -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 { | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| classUnitTypeextendsType,TTuple{ | |
| classUnitTypeextendsTupleType,TTuple{ |
| /** Gets the arity of this tuple type parameter. */ | ||
| int getArity() { result = arity } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
TypeParameters don't really have an arity, right? Do we need this method for anything? Perhaps it should be replaced by
TypeTypegetTupleType(){result=TTuple(arity)}
| TTuple(int arity) { | ||
| arity = any(TupleTypeRepr t).getNumberOfFields() and | ||
| Stages::TypeInferenceStage::ref() | ||
| } or |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Shouldn't we also include tuple patterns and tuple expression in addition to tuple type reprs?
| TTuple(intarity){ | |
| arity=any(TupleTypeReprt).getNumberOfFields() and | |
| Stages::TypeInferenceStage::ref() | |
| }or | |
| TTuple(intarity){ | |
| ( | |
| arity=any(TupleTypeReprt).getNumberOfFields() or | |
| arity=any(TupleExpre).getNumberOfFields() or | |
| arity=any(TuplePatp).getNumberOfFields() | |
| )and | |
| Stages::TypeInferenceStage::ref() | |
| }or |
| * their positional index. | ||
| */ | ||
| class TupleTypeParameter extends TypeParameter, TTupleTypeParameter { | ||
| private int arity; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Is it really necessary to havearity as a field? Is it important to distinguish the first element of a pair from the first element of a triple?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Unintuitively the answer is yes. Before7c04c9f arity was not inTupleTypeParameter. 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 forTupleTypeParameter now.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks, I was wondering this as well.
| /** 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 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I don't really understand this comment. I think the following is perfectly fine in rust
structPair(i32,u64);let x =(Pair(1,2)).1;
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Yes, that is the problem :) Inlet i: i64 = foo.1 we cannot say from looking at this syntactically thatfoo hasi64 as it's second tuple element, exactly because it could also be a tuple struct. But iffoois 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.
Uh oh!
There was an error while loading.Please reload this page.
| @@ -1055,6 +1079,31 @@ private Type inferFieldExprType(AstNode n, TypePath path) { | |||
| ) | |||
| } | |||
| pragma[nomagic] | |||
| private Type inferTupleIndexExprType(FieldExpr fe, TypePath path) { | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
This looks fine to me, although I had expected something more similar toinferFieldExprType (or even integrated into that predicate). Or do things really work differently for named fields compared to numeric fields?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I looked into that, butinferFieldExprType uses theMatching 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 ininferFieldExprType.
Uh oh!
There was an error while loading.Please reload this page.
Thanks for the review. I think I've addressed the suggestions and questions.
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. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Looks great, I'll have a look at the DCA results as well when that's done...
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
| * their positional index. | ||
| */ | ||
| class TupleTypeParameter extends TypeParameter, TTupleTypeParameter { | ||
| private int arity; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thanks, I was wondering this as well.
Uh oh!
There was an error while loading.Please reload this page.
Co-authored-by: Arthur Baars <aibaars@github.com>
The status of this PR is that it's currently blocked as it causes analysis on |
Uh oh!
There was an error while loading.Please reload this page.
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.