Skip to content

Rust: Support non-universal impl blocks #19372

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.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 7 commits into
base: main
Choose a base branch
from
Open

Rust: Support non-universal impl blocks #19372

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
22407ca
Rust: Add type inference test for non-universal impl blocks
paldepind Apr 28, 2025
e45b5c5
Rust: Implement type inference support for non-universal impl blocks
paldepind Apr 28, 2025
4513106
Rust: Add type inference test for inherent implementation shadowing t…
paldepind Apr 29, 2025
3ee8989
Rust: Handle inherent implementations shadowing trait implementations
paldepind Apr 29, 2025
ecead2c
Rust: Workaround for method existing both as source and as dependency
paldepind May 1, 2025
a545361
Rust: Accept test changes
paldepind Apr 29, 2025
06cfa9a
Rust: Address format fixes suggested in review
paldepind May 5, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
38 changes: 29 additions & 9 deletions rust/ql/lib/codeql/rust/elements/internal/MethodCallExprImpl.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,13 @@ private import codeql.rust.internal.TypeInference
* be referenced directly.
*/
module Impl {
private predicate isImplFunction(Function f) { f = any(ImplItemNode impl).getAnAssocItem() }
private predicate isInherentImplFunction(Function f) {
f = any(Impl impl | not impl.hasTrait()).(ImplItemNode).getAnAssocItem()
}

private predicate isTraitImplFunction(Function f) {
f = any(Impl impl | impl.hasTrait()).(ImplItemNode).getAnAssocItem()
}

// the following QLdoc is generated: if you need to edit it, do it in the schema file
/**
Expand All @@ -25,23 +31,37 @@ module Impl {
* ```
*/
class MethodCallExpr extends Generated::MethodCallExpr {
override Function getStaticTarget() {
private Function getStaticTargetFrom(boolean fromSource) {
result = resolveMethodCallExpr(this) and
(if result.fromSource() then fromSource = true else fromSource = false) and
(
// prioritize `impl` methods first
isImplFunction(result)
// prioritize inherent implementation methods first
isInherentImplFunction(result)
or
not isImplFunction(resolveMethodCallExpr(this)) and
not isInherentImplFunction(resolveMethodCallExpr(this)) and
(
// then trait methods with default implementations
result.hasBody()
// then trait implementation methods
isTraitImplFunction(result)
or
// and finally trait methods without default implementations
not resolveMethodCallExpr(this).hasBody()
not isTraitImplFunction(resolveMethodCallExpr(this)) and
(
// then trait methods with default implementations
result.hasBody()
or
// and finally trait methods without default implementations
not resolveMethodCallExpr(this).hasBody()
)
)
)
}

override Function getStaticTarget() {
result = this.getStaticTargetFrom(true)
or
not exists(this.getStaticTargetFrom(true)) and
result = this.getStaticTargetFrom(false)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why do we prioritize results with fromSource above everything else?

}

private string toStringPart(int index) {
index = 0 and
result = this.getReceiver().toAbbreviatedString()
Expand Down
55 changes: 0 additions & 55 deletions rust/ql/lib/codeql/rust/internal/PathResolution.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -448,61 +448,6 @@ class ImplItemNode extends ImplOrTraitItemNode instanceof Impl {

TraitItemNode resolveTraitTy() { result = resolvePath(this.getTraitPath()) }

pragma[nomagic]
private TypeRepr getASelfTyArg() {
result =
this.getSelfPath().getSegment().getGenericArgList().getAGenericArg().(TypeArg).getTypeRepr()
}

/**
* Holds if this `impl` block is not fully parametric. That is, the implementing
* type is generic and the implementation is not parametrically polymorphic in all
* the implementing type's arguments.
*
* Examples:
*
* ```rust
* impl Foo { ... } // fully parametric
*
* impl<T> Foo<T> { ... } // fully parametric
*
* impl Foo<i64> { ... } // not fully parametric
*
* impl<T> Foo<Foo<T>> { ... } // not fully parametric
*
* impl<T: Trait> Foo<T> { ... } // not fully parametric
*
* impl<T> Foo<T> where T: Trait { ... } // not fully parametric
* ```
*/
pragma[nomagic]
predicate isNotFullyParametric() {
exists(TypeRepr arg | arg = this.getASelfTyArg() |
not exists(resolveTypeParamPathTypeRepr(arg))
or
resolveTypeParamPathTypeRepr(arg).hasTraitBound()
)
}

/**
* Holds if this `impl` block is fully parametric. Examples:
*
* ```rust
* impl Foo { ... } // fully parametric
*
* impl<T> Foo<T> { ... } // fully parametric
*
* impl Foo<i64> { ... } // not fully parametric
*
* impl<T> Foo<Foo<T>> { ... } // not fully parametric
*
* impl<T: Trait> Foo<T> { ... } // not fully parametric
*
* impl<T> Foo<T> where T: Trait { ... } // not fully parametric
* ```
*/
predicate isFullyParametric() { not this.isNotFullyParametric() }

override AssocItemNode getAnAssocItem() { result = super.getAssocItemList().getAnAssocItem() }

override string getName() { result = "(impl)" }
Expand Down
112 changes: 26 additions & 86 deletions rust/ql/lib/codeql/rust/internal/Type.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,10 +27,6 @@ newtype TType =
* types, such as traits and implementation blocks.
*/
abstract class Type extends TType {
/** Gets the method `name` belonging to this type, if any. */
pragma[nomagic]
abstract Function getMethod(string name);

/** Gets the struct field `name` belonging to this type, if any. */
pragma[nomagic]
abstract StructField getStructField(string name);
Expand All @@ -45,25 +41,6 @@ abstract class Type extends TType {
/** Gets a type parameter of this type. */
final TypeParameter getATypeParameter() { result = this.getTypeParameter(_) }

/**
* Gets an AST node that mentions a base type of this type, if any.
*
* Although Rust doesn't have traditional OOP-style inheritance, we model trait
* bounds and `impl` blocks as base types. Example:
*
* ```rust
* trait T1 {}
*
* trait T2 {}
*
* trait T3 : T1, T2 {}
* // ^^ `this`
* // ^^ `result`
* // ^^ `result`
* ```
*/
abstract TypeMention getABaseTypeMention();

/** Gets a textual representation of this type. */
abstract string toString();

Expand All @@ -73,21 +50,6 @@ abstract class Type extends TType {

abstract private class StructOrEnumType extends Type {
abstract ItemNode asItemNode();

final override Function getMethod(string name) {
result = this.asItemNode().getASuccessor(name) and
exists(ImplOrTraitItemNode impl | result = impl.getAnAssocItem() |
impl instanceof Trait
or
impl.(ImplItemNode).isFullyParametric()
)
}

/** Gets all of the fully parametric `impl` blocks that target this type. */
final override ImplMention getABaseTypeMention() {
this.asItemNode() = result.resolveSelfTy() and
result.isFullyParametric()
}
}

/** A struct type. */
Expand Down Expand Up @@ -138,8 +100,6 @@ class TraitType extends Type, TTrait {

TraitType() { this = TTrait(trait) }

override Function getMethod(string name) { result = trait.(ItemNode).getASuccessor(name) }

override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }
Expand All @@ -151,14 +111,6 @@ class TraitType extends Type, TTrait {
any(AssociatedTypeTypeParameter param | param.getTrait() = trait and param.getIndex() = i)
}

pragma[nomagic]
private TypeReprMention getABoundMention() {
result = trait.getTypeBoundList().getABound().getTypeRepr()
}

/** Gets any of the trait bounds of this trait. */
override TypeMention getABaseTypeMention() { result = this.getABoundMention() }

override string toString() { result = trait.toString() }

override Location getLocation() { result = trait.getLocation() }
Expand Down Expand Up @@ -220,8 +172,6 @@ class ImplType extends Type, TImpl {

ImplType() { this = TImpl(impl) }

override Function getMethod(string name) { result = impl.(ItemNode).getASuccessor(name) }

override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }
Expand All @@ -230,9 +180,6 @@ class ImplType extends Type, TImpl {
result = TTypeParamTypeParameter(impl.getGenericParamList().getTypeParam(i))
}

/** Get the trait implemented by this `impl` block, if any. */
override TypeMention getABaseTypeMention() { result = impl.getTrait() }

override string toString() { result = impl.toString() }

override Location getLocation() { result = impl.getLocation() }
Expand All @@ -247,8 +194,6 @@ class ImplType extends Type, TImpl {
class ArrayType extends Type, TArrayType {
ArrayType() { this = TArrayType() }

override Function getMethod(string name) { none() }

override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }
Expand All @@ -257,8 +202,6 @@ class ArrayType extends Type, TArrayType {
none() // todo
}

override TypeMention getABaseTypeMention() { none() }

override string toString() { result = "[]" }

override Location getLocation() { result instanceof EmptyLocation }
Expand All @@ -273,8 +216,6 @@ class ArrayType extends Type, TArrayType {
class RefType extends Type, TRefType {
RefType() { this = TRefType() }

override Function getMethod(string name) { none() }

override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }
Expand All @@ -284,17 +225,13 @@ class RefType extends Type, TRefType {
i = 0
}

override TypeMention getABaseTypeMention() { none() }

override string toString() { result = "&" }

override Location getLocation() { result instanceof EmptyLocation }
}

/** A type parameter. */
abstract class TypeParameter extends Type {
override TypeMention getABaseTypeMention() { none() }

override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }
Expand All @@ -318,19 +255,9 @@ class TypeParamTypeParameter extends TypeParameter, TTypeParamTypeParameter {

TypeParam getTypeParam() { result = typeParam }

override Function getMethod(string name) {
// NOTE: If the type parameter has trait bounds, then this finds methods
// on the bounding traits.
result = typeParam.(ItemNode).getASuccessor(name)
}

override string toString() { result = typeParam.toString() }

override Location getLocation() { result = typeParam.getLocation() }

final override TypeMention getABaseTypeMention() {
result = typeParam.getTypeBoundList().getABound().getTypeRepr()
}
}

/**
Expand Down Expand Up @@ -377,19 +304,13 @@ class AssociatedTypeTypeParameter extends TypeParameter, TAssociatedTypeTypePara

int getIndex() { traitAliasIndex(_, result, typeAlias) }

override Function getMethod(string name) { none() }

override string toString() { result = typeAlias.getName().getText() }

override Location getLocation() { result = typeAlias.getLocation() }

override TypeMention getABaseTypeMention() { none() }
}

/** An implicit reference type parameter. */
class RefTypeParameter extends TypeParameter, TRefTypeParameter {
override Function getMethod(string name) { none() }

override string toString() { result = "&T" }

override Location getLocation() { result instanceof EmptyLocation }
Expand All @@ -409,15 +330,34 @@ class SelfTypeParameter extends TypeParameter, TSelfTypeParameter {

Trait getTrait() { result = trait }

override TypeMention getABaseTypeMention() { result = trait }
override string toString() { result = "Self [" + trait.toString() + "]" }

override Location getLocation() { result = trait.getLocation() }
}

/** A type abstraction. */
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'd appreciate a bit more QLDoc here. What is a "type abstraction" in this context? (assuming it's not a Rust term)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

A tried to explain this over in the shared module. Would it make sense to repeat the Rust specific part of that here?

abstract class TypeAbstraction extends AstNode {
abstract TypeParameter getATypeParameter();
}

override Function getMethod(string name) {
// The `Self` type parameter is an implementation of the trait, so it has
// all the trait's methods.
result = trait.(ItemNode).getASuccessor(name)
final class ImplTypeAbstraction extends TypeAbstraction, Impl {
override TypeParamTypeParameter getATypeParameter() {
result.getTypeParam() = this.getGenericParamList().getATypeParam()
}
}

override string toString() { result = "Self [" + trait.toString() + "]" }
final class TraitTypeAbstraction extends TypeAbstraction, Trait {
override TypeParamTypeParameter getATypeParameter() {
result.getTypeParam() = this.getGenericParamList().getATypeParam()
}
}

override Location getLocation() { result = trait.getLocation() }
final class TypeBoundTypeAbstraction extends TypeAbstraction, TypeBound {
override TypeParamTypeParameter getATypeParameter() { none() }
}

final class SelfTypeBoundTypeAbstraction extends TypeAbstraction, Name {
SelfTypeBoundTypeAbstraction() { any(Trait trait).getName() = this }

override TypeParamTypeParameter getATypeParameter() { none() }
}
Loading