Skip to content

Rust: Rework type inference for method calls #20282

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

Draft
wants to merge 8 commits into
base: main
Choose a base branch
from
+4,094 −3,065
Draft

Rust: Rework type inference for method calls #20282

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
642bfbd
Shared: Make some generalizations in type inference library
hvitved Sep 3, 2025
fc9ce33
Rust: Add type inference tests
hvitved Aug 18, 2025
195a708
wip
hvitved Aug 18, 2025
d11b22b
wip2
hvitved Sep 4, 2025
7662edf
update expected
hvitved Sep 4, 2025
77fa7b4
wip
hvitved Sep 4, 2025
adfced0
perf
hvitved Sep 4, 2025
5183918
wip
hvitved Sep 4, 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
3 changes: 3 additions & 0 deletions rust/ql/lib/codeql/rust/elements/internal/FunctionImpl.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -69,5 +69,8 @@
this.getLocation().getStartLine() <= result.getLocation().getStartLine() and
result.getLocation().getStartLine() <= this.getName().getLocation().getStartLine()
}

pragma[nomagic]

Check warning on line 73 in rust/ql/lib/codeql/rust/elements/internal/FunctionImpl.qll

View workflow job for this annotation

GitHub Actions / qldoc 

Missing QLdoc for member-predicate FunctionImpl::Impl::Function::hasSelfParam/0
predicate hasSelfParam() { this.getParamList().hasSelfParam() }
}
}
2 changes: 1 addition & 1 deletion rust/ql/lib/codeql/rust/elements/internal/OperationImpl.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,7 +12,7 @@ private import codeql.rust.elements.internal.ExprImpl::Impl as ExprImpl
* the canonical path `path` and the method name `method`, and if it borrows its
* first `borrows` arguments.
*/
private predicate isOverloaded(string op, int arity, string path, string method, int borrows) {
predicate isOverloaded(string op, int arity, string path, string method, int borrows) {
arity = 1 and
(
// Negation
Expand Down
7 changes: 7 additions & 0 deletions rust/ql/lib/codeql/rust/elements/internal/UnionImpl.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,6 +21,13 @@ module Impl {
* ```
*/
class Union extends Generated::Union {
/** Gets the record field named `name`, if any. */
pragma[nomagic]
StructField getStructField(string name) {
result = this.getStructFieldList().getAField() and
result.getName().getText() = name
}

override string toStringImpl() { result = "union " + this.getName().getText() }
}
}
40 changes: 40 additions & 0 deletions rust/ql/lib/codeql/rust/frameworks/stdlib/Stdlib.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -213,3 +213,43 @@ class StringStruct extends Struct {
pragma[nomagic]
StringStruct() { this.getCanonicalPath() = "alloc::string::String" }
}

/**
* The [`Deref` trait][1].
*
* [1]: https://doc.rust-lang.org/core/ops/trait.Deref.html
*/
class DerefTrait extends Trait {
pragma[nomagic]
DerefTrait() { this.getCanonicalPath() = "core::ops::deref::Deref" }

/** Gets the `deref` function. */
Function getDerefFunction() { result = this.(TraitItemNode).getAssocItem("deref") }

/** Gets the `Target` associated type. */
pragma[nomagic]
TypeAlias getTargetType() {
result = this.getAssocItemList().getAnAssocItem() and
result.getName().getText() = "Target"
}
}

/**
* The [`Index` trait][1].
*
* [1]: https://doc.rust-lang.org/std/ops/trait.Index.html
*/
class IndexTrait extends Trait {
pragma[nomagic]
IndexTrait() { this.getCanonicalPath() = "core::ops::index::Index" }

/** Gets the `index` function. */
Function getIndexFunction() { result = this.(TraitItemNode).getAssocItem("index") }

/** Gets the `Output` associated type. */
pragma[nomagic]
TypeAlias getOutputType() {
result = this.getAssocItemList().getAnAssocItem() and
result.getName().getText() = "Output"
}
}
47 changes: 34 additions & 13 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 @@ -636,6 +636,8 @@ final class ImplItemNode extends ImplOrTraitItemNode instanceof Impl {

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

predicate isBlanket() { this.resolveSelfTy() instanceof TypeParam }

override AssocItemNode getAnAssocItem() { result = this.getADescendant() }

override string getName() { result = "(impl)" }
Expand Down Expand Up @@ -721,7 +723,7 @@ final class ImplItemNode extends ImplOrTraitItemNode instanceof Impl {
}
}

final private class ImplTraitTypeReprItemNode extends TypeItemNode instanceof ImplTraitTypeRepr {
final class ImplTraitTypeReprItemNode extends TypeItemNode instanceof ImplTraitTypeRepr {
pragma[nomagic]
Path getABoundPath() {
result = super.getTypeBoundList().getABound().getTypeRepr().(PathTypeRepr).getPath()
Expand Down Expand Up @@ -1425,24 +1427,43 @@ signature predicate relevantTraitVisibleSig(Element element, Trait trait);
* at a given element.
*/
module TraitIsVisible<relevantTraitVisibleSig/2 relevantTraitVisible> {
/** Holds if the trait might be looked up in `encl`. */
private predicate traitLookup(ItemNode encl, Element element, Trait trait) {
// lookup in immediately enclosing item
relevantTraitVisible(element, trait) and
encl.getADescendant() = element
private newtype TNode =
TTrait(Trait t) or
TItemNode(ItemNode i) or
TElement(Element e) { relevantTraitVisible(e, _) }

private predicate isTrait(TNode n) { n instanceof TTrait }

private predicate step(TNode n1, TNode n2) {
exists(Trait t1, ItemNode i2 |
n1 = TTrait(t1) and
n2 = TItemNode(i2) and
t1 = i2.getASuccessor(_, _)
)
or
// lookup in an outer scope, but only if the trait is not declared in inner scope
exists(ItemNode mid |
traitLookup(mid, element, trait) and
not trait = mid.getASuccessor(_, _) and
encl = getOuterScope(mid)
exists(ItemNode i1, ItemNode i2 |
n1 = TItemNode(i1) and
n2 = TItemNode(i2) and
i1 = getOuterScope(i2)
)
or
exists(ItemNode i1, Element e2 |
n1 = TItemNode(i1) and
n2 = TElement(e2) and
i1.getADescendant() = e2
)
}

private predicate isElement(TNode n) { n instanceof TElement }

private predicate traitIsVisibleTC(TNode trait, TNode element) =
doublyBoundedFastTC(step/2, isTrait/1, isElement/1)(trait, element)
Comment on lines +1459 to +1460
Copy link
Preview

Copilot AI Sep 4, 2025

Choose a reason for hiding this comment

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

The replacement of the recursive traitLookup predicate with transitive closure using doublyBoundedFastTC is a good optimization. However, ensure that the performance characteristics are tested with large codebases, as transitive closure can be expensive for deeply nested scopes.

Suggested change
private predicate traitIsVisibleTC(TNode trait, TNode element) =
doublyBoundedFastTC(step/2, isTrait/1, isElement/1)(trait, element)
/**
* Holds if there is a path from `trait` to `element` via `step`, bounded by `isTrait` and `isElement`.
* To avoid performance issues in large or deeply nested codebases, we limit the maximum path length.
* If you encounter performance problems, consider tightening the bounds or using the original recursive predicate.
*/
private predicate traitIsVisibleTC(TNode trait, TNode element) {
exists(int depth |
depth < 20 and
doublyBoundedFastTC(step/2, isTrait/1, isElement/1, depth)(trait, element)
)
}

Copilot uses AI. Check for mistakes.


/** Holds if the trait `trait` is visible at `element`. */
pragma[nomagic]
predicate traitIsVisible(Element element, Trait trait) {
exists(ItemNode encl | traitLookup(encl, element, trait) and trait = encl.getASuccessor(_, _))
traitIsVisibleTC(TTrait(trait), TElement(element)) and
relevantTraitVisible(element, trait)
}
}

Expand Down Expand Up @@ -1740,7 +1761,7 @@ private module Debug {
exists(string filepath, int startline, int startcolumn, int endline, int endcolumn |
result.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn) and
filepath.matches("%/main.rs") and
startline = 52
startline = 167
Comment on lines 1763 to +1764
Copy link
Preview

Copilot AI Sep 3, 2025

Choose a reason for hiding this comment

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

This hardcoded line number (167) in the debug module appears to be a leftover from development/testing. Consider removing this specific line constraint or making it configurable to avoid issues when the test file structure changes.

See below for a potential fix:

      filepath.matches("%/main.rs")

Copilot uses AI. Check for mistakes.

Copy link
Preview

Copilot AI Sep 3, 2025

Choose a reason for hiding this comment

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

[nitpick] This hardcoded line number in the debug module should be removed or made configurable. Having hardcoded debug coordinates in production code can cause confusion and makes the code less maintainable.

See below for a potential fix:

  /**
   * Returns a relevant locatable for debugging, configurable by line number.
   */
  private Locatable getRelevantLocatable(int startline) {
    exists(string filepath, int sline, int startcolumn, int endline, int endcolumn |
      result.getLocation().hasLocationInfo(filepath, sline, startcolumn, endline, endcolumn) and
      filepath.matches("%/main.rs") and
      sline = startline
    )
  }

  /** Convenience: default line number for debugging. */
  private int defaultDebugStartLine() { result = 167 }

  /** Overload for backward compatibility: uses default line number. */
  private Locatable getRelevantLocatable() { result = getRelevantLocatable(defaultDebugStartLine()) }

  predicate debugUnqualifiedPathLookup(
    RelevantPath p, string name, Namespace ns, ItemNode encl, string path
  ) {
    p = getRelevantLocatable(defaultDebugStartLine()) and
    unqualifiedPathLookup(encl, name, ns, p) and
    path = p.toStringDebug()
  }

  ItemNode debugResolvePath(RelevantPath path) {
    path = getRelevantLocatable(defaultDebugStartLine()) and
    result = resolvePath(path)
  }

  predicate debugUseImportEdge(Use use, string name, ItemNode item, SuccessorKind kind) {
    use = getRelevantLocatable(defaultDebugStartLine()) and
    useImportEdge(use, name, item, kind)
  }

  ItemNode debugGetASuccessor(ItemNode i, string name, SuccessorKind kind) {
    i = getRelevantLocatable(defaultDebugStartLine()) and
    result = i.getASuccessor(name, kind)
  }

  predicate debugFileImportEdge(Module mod, string name, ItemNode item, SuccessorKind kind) {
    mod = getRelevantLocatable(defaultDebugStartLine()) and
    fileImportEdge(mod, name, item, kind)
  }

  predicate debugFileImport(Module m, SourceFile f) {
    m = getRelevantLocatable(defaultDebugStartLine()) and
    fileImport(m, f)
  }

  predicate debugPreludeEdge(SourceFile f, string name, ItemNode i) {
    preludeEdge(f, name, i) and
    f = getRelevantLocatable(defaultDebugStartLine())
  }

  string debugGetCanonicalPath(ItemNode i, Crate c) {
    result = i.getCanonicalPath(c) and
    i = getRelevantLocatable(defaultDebugStartLine())

Copilot uses AI. Check for mistakes.

)
}

Expand Down
64 changes: 63 additions & 1 deletion 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 @@ -42,11 +42,14 @@ newtype TType =
TStruct(Struct s) or
TEnum(Enum e) or
TTrait(Trait t) or
TUnion(Union u) or
TArrayType() or // todo: add size?
TRefType() or // todo: add mut?
TImplTraitType(ImplTraitTypeRepr impl) or
TDynTraitType(Trait t) { t = any(DynTraitTypeRepr dt).getTrait() } or
TSliceType() or
TNeverType() or
TPtrType() or
TTupleTypeParameter(int arity, int i) { exists(TTuple(arity)) and i in [0 .. arity - 1] } or
TTypeParamTypeParameter(TypeParam t) or
TAssociatedTypeTypeParameter(TypeAlias t) { any(TraitItemNode trait).getAnAssocItem() = t } or
Expand All @@ -57,7 +60,8 @@ newtype TType =
} or
TRefTypeParameter() or
TSelfTypeParameter(Trait t) or
TSliceTypeParameter()
TSliceTypeParameter() or
TPtrTypeParameter()

private predicate implTraitTypeParam(ImplTraitTypeRepr implTrait, int i, TypeParam tp) {
implTrait.isInReturnPos() and
Expand Down Expand Up @@ -224,6 +228,31 @@ class TraitType extends Type, TTrait {
override Location getLocation() { result = trait.getLocation() }
}

/** A union type. */
class UnionType extends StructOrEnumType, TUnion {
private Union union;

UnionType() { this = TUnion(union) }

override ItemNode asItemNode() { result = union }

override StructField getStructField(string name) { result = union.getStructField(name) }

override TupleField getTupleField(int i) { none() }

override TypeParameter getPositionalTypeParameter(int i) {
result = TTypeParamTypeParameter(union.getGenericParamList().getTypeParam(i))
}

override TypeMention getTypeParameterDefault(int i) {
result = union.getGenericParamList().getTypeParam(i).getDefaultType()
}

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

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

/**
* An array type.
*
Expand Down Expand Up @@ -374,6 +403,33 @@ class SliceType extends Type, TSliceType {
override Location getLocation() { result instanceof EmptyLocation }
}

class NeverType extends Type, TNeverType {
override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }

override TypeParameter getPositionalTypeParameter(int i) { none() }

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

override Location getLocation() { result instanceof EmptyLocation }
}

class PtrType extends Type, TPtrType {
override StructField getStructField(string name) { none() }

override TupleField getTupleField(int i) { none() }

override TypeParameter getPositionalTypeParameter(int i) {
i = 0 and
result = TPtrTypeParameter()
}

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

override Location getLocation() { result instanceof EmptyLocation }
}

/** A type parameter. */
abstract class TypeParameter extends Type {
override StructField getStructField(string name) { none() }
Expand Down Expand Up @@ -529,6 +585,12 @@ class SliceTypeParameter extends TypeParameter, TSliceTypeParameter {
override Location getLocation() { result instanceof EmptyLocation }
}

class PtrTypeParameter extends TypeParameter, TPtrTypeParameter {
override string toString() { result = "*T" }

override Location getLocation() { result instanceof EmptyLocation }
}

/**
* The implicit `Self` type parameter of a trait, that refers to the
* implementing type of the trait.
Expand Down
Loading
Loading