Rust: Improve performance of type inference #19534
Conversation
There was a problem hiding this comment.
Pull Request Overview
This PR optimizes type inference by eliminating certain aggregates and runtime checks, replacing them with compile-time computations, and introduces inverse-append helpers to skip redundant path‐length validations.
- Introduce
length2()to compute type-path segment counts withoutstrictcount - Replace
appendwith bounds-checked logic and addappendInversefor deconstructing paths - Update all call sites to use
appendInversewhere appropriate
Reviewed Changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated 3 comments.
| File | Description |
|---|---|
| shared/typeinference/codeql/typeinference/internal/TypeInference.qll | Replaced strictcount use with length2(), refactored length(), introduced appendInverse and updated call sites |
| rust/ql/lib/codeql/rust/internal/TypeInference.qll | Added typeEqualityLeft/Right predicates, switched to consInverse in inference and replaced old prefix-based logic |
Comments suppressed due to low confidence (2)
shared/typeinference/codeql/typeinference/internal/TypeInference.qll:187
- [nitpick] The name
length2is not descriptive of its purpose (counting path segments). Consider renaming it to something likesegmentCountordotCountPlusOnefor clarity.
private int length2() {
shared/typeinference/codeql/typeinference/internal/TypeInference.qll:191
- Using
regexpReplaceAllfor every path may be costly on very long strings. After fixing the bug above, consider benchmarking or using a direct dot-counting approach if QL provides one to ensure this remains faster thanstrictcount.
result = this.regexpReplaceAll("[0-9]+", "").length() + 1
| * Gets the path obtained by appending `suffix` onto this path. | ||
| * | ||
| * Unlike `append`, this predicate has `result` in the binding set, | ||
| * so there is no need to check the length of `result`. |
There was a problem hiding this comment.
The documentation for appendInverse is copied from append but this predicate actually deconstructs a full path into this and suffix. Please update the comment to describe the inverse operation.
| * Gets the path obtained by appending `suffix` onto this path. | |
| * | |
| * Unlike `append`, this predicate has `result` in the binding set, | |
| * so there is no need to check the length of `result`. | |
| * Deconstructs a full path `result` into `this` and `suffix`. | |
| * | |
| * This predicate performs the inverse operation of `append`. It holds if | |
| * `result` is a path that can be split into `this` as the prefix and | |
| * `suffix` as the remainder. For example, if `result` is "a.b.c" and | |
| * `this` is "a.b", then `suffix` would be "c". |
Copilot uses AI. Check for mistakes.
| * onto `suffix`. | ||
| */ | ||
| bindingset[result] | ||
| TypePath consInverse(TypeParameter tp, TypePath suffix) { |
There was a problem hiding this comment.
consInverse is equivalent to isCons but with a different parameter order.
I find isCons easer to read as it's the result that is the output and since the name is easier to understand. Looking at the places where consInverse is used there's only one spot where it's not trivial to use isCons instead. Given that, I think it would make sense to remove consInverse and use isCons instead.
| * so there is no need to check the length of `result`. | ||
| */ | ||
| bindingset[this, result] | ||
| TypePath appendInverse(TypePath suffix) { |
There was a problem hiding this comment.
A variant of this where the result is the output could be:
bindingset[this, prefix]
TypePath stripPrefix(TypePath prefix) { this = prefix.appendInverse(result) }Similar to my comment for consInverse I find that more natural. However, unlike for isCons this variant is less convenient in all the places where appendInverse is used. But perhaps we could introduce stripPrefix, define appendInverse in terms of stripPrefix, and use stripPrefix in the (few if any) cases where it's not inconvenient?
| this.isEmpty() and result = 0 | ||
| or | ||
| result = strictcount(this.indexOf(".")) + 1 | ||
| if this.isEmpty() |
There was a problem hiding this comment.
Perhaps depth would actually be a better name than length?
There was a problem hiding this comment.
Doesn't depth lead to the misconception that it is a tree instead of a list?
There was a problem hiding this comment.
Maybe? To me it feel natural to say that the depth of foo/bar/baz is 3, but let's just keep it as-if if you feel it's not as clear.
| /** Gets the length of this path, assuming the length is at least 2. */ | ||
| bindingset[this] | ||
| pragma[inline_late] | ||
| private int length2() { |
39423fd to
856021c
Compare
856021c to
13861b8
Compare
This PR speeds up type inference by
strictcountaggregate,DCA shows an impressive 65 % analysis time speedup on
rust-lang/rust.