Rust: Support non-universal impl blocks
#19372
Open
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
c66a71a to
a9afbb3
Compare
76baa34 to
02115f6
Compare
…rait implementation
439b202 to
68860b1
Compare
68860b1 to
a545361
Compare
geoffw0
reviewed
May 1, 2025
| result = this.getStaticTargetFrom(true) | ||
| or | ||
| not exists(this.getStaticTargetFrom(true)) and | ||
| result = this.getStaticTargetFrom(false) |
There was a problem hiding this comment.
Why do we prioritize results with fromSource above everything else?
| override Location getLocation() { result = trait.getLocation() } | ||
| } | ||
|
|
||
| /** A type abstraction. */ |
There was a problem hiding this comment.
I'd appreciate a bit more QLDoc here. What is a "type abstraction" in this context? (assuming it's not a Rust term)
| result = tp.(SelfTypeParameter).getTrait() | ||
| } | ||
|
|
||
| predicate conditionSatisfiesConstraint( |
There was a problem hiding this comment.
This could also do with QLDoc, in particular explaining the condition and constraint parameters.
hvitved
reviewed
May 1, 2025
| @@ -212,6 +237,17 @@ module Make1<LocationSig Location, InputSig1<Location> Input1> { | |||
| TypePath cons(TypeParameter tp, TypePath suffix) { result = singleton(tp).append(suffix) } | |||
| } | |||
|
|
|||
| /** A class that represents a type tree. */ | |||
| signature class TypeTreeSig { | |||
| @@ -265,8 +357,239 @@ module Make1<LocationSig Location, InputSig1<Location> Input1> { | |||
| result = tm.resolveTypeAt(TypePath::nil()) | |||
| } | |||
|
|
|||
| signature module IsInstantiationOfSig<TypeTreeSig App> { | |||
There was a problem hiding this comment.
I would call it IsInstantiationOfInputSig
| predicate potentialInstantiationOf(App app, TypeAbstraction abs, TypeMention tm); | ||
| } | ||
|
|
||
| module IsInstantiationOf<TypeTreeSig App, IsInstantiationOfSig<App> Input> { |
Comment on lines
+330
to
+344
| * Note that the type parameters in `abs` significantly change the meaning | ||
| * of type parameters that occur in `condition`. For instance, in the Rust | ||
| * example | ||
| * ```rust | ||
| * fn foo<T: Trait>() { } | ||
| * ``` | ||
| * we have that the type parameter `T` satisfies the constraint `Trait`. But, | ||
| * only that specific `T` satisfy the constraint. Hence we would not have | ||
| * `T` in `abs`. On the other hand, in the Rust example | ||
| * ```rust | ||
| * impl<T> Trait for T { } | ||
| * ``` | ||
| * the constraint `Trait` is in fact satisfied for all types, and we would | ||
| * have `T` in `abs` to make it free in the condition. | ||
| */ |
There was a problem hiding this comment.
This bit is hard to follow.
Comment on lines
+362
to
+364
| * Holds if `abs` is a type abstraction under which `tm` occurs and if | ||
| * `app` is potentially the result of applying the abstraction to type | ||
| * some type argument. |
There was a problem hiding this comment.
Can you elaborate what under which `tm` occurs means?
| ) | ||
| } | ||
|
|
||
| private predicate satisfiesConcreteTypesFromIndex( |
There was a problem hiding this comment.
For a predicate like this I would always defensively add pragma[nomagic]
| if i = 0 then any() else satisfiesConcreteTypesFromIndex(app, abs, tm, i - 1) | ||
| } | ||
|
|
||
| pragma[inline] |
There was a problem hiding this comment.
I would assume pragma[nomagic] instead.
| * - `Pair<int, string>` is _not_ an instantiation of `Pair<string, string>` | ||
| */ | ||
| predicate isInstantiationOf(App app, TypeAbstraction abs, TypeMention tm) { | ||
| potentialInstantiationOf(app, abs, tm) and |
There was a problem hiding this comment.
This is implied from satisfiesConcreteTypes, no?
| private import Input | ||
|
|
||
| /** Gets the `i`th path in `tm` per some arbitrary order. */ | ||
| private TypePath getNthPath(TypeMention tm, int i) { |
There was a problem hiding this comment.
I noticed that this rank can take a bit of time
[2025-05-01 19:42:45] Evaluated non-recursive predicate TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthPath/2#f4fd7036@294f69ka in 5811ms (size: 8841689).
Evaluated relational algebra for predicate TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthPath/2#f4fd7036@294f69ka with tuple counts:
8841689 ~6% {3} r1 = AGGREGATE `project#TypeMention::TypeMention.resolveTypeAt/1#dispred#a125c821`, `project#TypeMention::TypeMention.resolveTypeAt/1#dispred#a125c821_011#rank_term` ON In.2 WITH RANK<0 ASC> OUTPUT In.0, Agg.0, Agg.1
8841689 ~2% {4} | SCAN OUTPUT In.0, _, In.1, In.2
8841689 ~0% {3} | REWRITE WITH Tmp.1 := 1, Out.1 := (In.3 - Tmp.1) KEEPING 3
return r1
We can, however, improve it, by restricting it to relevant type mentions. The following seems to work for me locally
diff --git a/shared/typeinference/codeql/typeinference/internal/TypeInference.qll b/shared/typeinference/codeql/typeinfe
rence/internal/TypeInference.qll
index 7e89671da54..19444398c04 100644
--- a/shared/typeinference/codeql/typeinference/internal/TypeInference.qll
+++ b/shared/typeinference/codeql/typeinference/internal/TypeInference.qll
@@ -364,14 +364,25 @@ module Make1<LocationSig Location, InputSig1<Location> Input1> {
* some type argument.
*/
predicate potentialInstantiationOf(App app, TypeAbstraction abs, TypeMention tm);
+
+ default predicate potentialInstantiationOfProj(TypeMention tm) {
+ potentialInstantiationOf(_, _, tm)
+ }
}
module IsInstantiationOf<TypeTreeSig App, IsInstantiationOfSig<App> Input> {
private import Input
/** Gets the `i`th path in `tm` per some arbitrary order. */
+ pragma[nomagic]
private TypePath getNthPath(TypeMention tm, int i) {
- result = rank[i + 1](TypePath path | exists(tm.resolveTypeAt(path)) | path)
+ result =
+ rank[i + 1](TypePath path |
+ exists(tm.resolveTypeAt(path)) and
+ potentialInstantiationOfProj(tm)
+ |
+ path
+ )
}
/**
@@ -416,10 +427,18 @@ module Make1<LocationSig Location, InputSig1<Location> Input1> {
* Gets the path to the `i`th occurrence of `tp` within `tm` per some
* arbitrary order, if any.
*/
+ pragma[nomagic]
private TypePath getNthTypeParameterPath(TypeMention tm, TypeParameter tp, int i) {
- result = rank[i + 1](TypePath path | tp = tm.resolveTypeAt(path) | path)
+ result =
+ rank[i + 1](TypePath path |
+ tp = tm.resolveTypeAt(path) and
+ potentialInstantiationOfProj(tm)
+ |
+ path
+ )
}
+ pragma[nomagic]
private predicate typeParametersEqualFromIndex(
App app, TypeAbstraction abs, TypeMention tm, TypeParameter tp, int i
) {
@@ -965,6 +984,10 @@ module Make1<LocationSig Location, InputSig1<Location> Input1> {
countConstraintImplementations(type, constraint) > 1
)
}
+
+ predicate potentialInstantiationOfProj(TypeMention constraint) {
+ rootTypesSatisfaction(_, _, _, constraint, _)
+ }
}
/**
diff --git a/rust/ql/lib/codeql/rust/internal/TypeInference.qll b/rust/ql/lib/codeql/rust/internal/TypeInference.qll
index 595a038884d..8395f94bb16 100644
--- a/rust/ql/lib/codeql/rust/internal/TypeInference.qll
+++ b/rust/ql/lib/codeql/rust/internal/TypeInference.qll
@@ -996,6 +996,13 @@ private module Cached {
receiver.getNumberOfArgs(), impl) and
sub = impl.(ImplTypeAbstraction).getSelfTy()
}
+
+ predicate potentialInstantiationOfProj(TypeMention sub) {
+ exists(TypeAbstraction impl |
+ methodCandidate(_, _, _, impl) and
+ sub = impl.(ImplTypeAbstraction).getSelfTy()
+ )
+ }
}The reason why we need the extra potentialInstantiationOfProj predicate is to avoid non-monotonic recursion.
| result = rank[i + 1](TypePath path | tp = tm.resolveTypeAt(path) | path) | ||
| } | ||
|
|
||
| private predicate typeParametersEqualFromIndex( |
There was a problem hiding this comment.
This predicate has bad joins
Pipeline standard for TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf@043e99wh was evaluated in 195 iterations totaling 6014ms (delta sizes total: 0).
0 ~0% {5} r1 = SCAN `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf#prev_delta` OUTPUT In.3, In.0, In.1, In.2, In.4
0 ~0% {5} | JOIN WITH `project#TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameter/2#5ff60e08#bff#3` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.3, Lhs.0, Lhs.4
0 ~0% {7} | JOIN WITH `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev` ON FIRST 3 OUTPUT Lhs.3, Lhs.0, Lhs.1, Lhs.2, _, Lhs.4, _
{5} | REWRITE WITH Tmp.4 := 1, Out.4 := (Tmp.4 + In.5), Tmp.6 := 1, TEST Out.4 != Tmp.6 KEEPING 5
0 ~0% {6} | SCAN OUTPUT In.3, In.0, In.4, In.1, In.2, _
0 ~0% {6} | REWRITE WITH Tmp.5 := 1, Out.5 := (InOut.2 - Tmp.5)
0 ~0% {7} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 3 OUTPUT Lhs.3, Rhs.3, Lhs.1, Lhs.4, Lhs.0, Lhs.2, Lhs.5
0 ~0% {7} | JOIN WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 2 OUTPUT Lhs.4, Lhs.2, Lhs.6, Lhs.0, Lhs.3, Lhs.5, Rhs.2
0 ~0% {7} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 3 OUTPUT Lhs.3, Rhs.3, Lhs.6, Lhs.1, Lhs.4, Lhs.0, Lhs.5
0 ~0% {5} | JOIN WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 3 OUTPUT Lhs.0, Lhs.4, Lhs.5, Lhs.3, Lhs.6
64790 ~1% {3} r2 = SCAN `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev_delta` OUTPUT In.2, In.0, In.1
4 ~0% {6} r3 = JOIN r2 WITH `_TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::Relevan__#join_rhs#3` ON FIRST 1 OUTPUT Lhs.0, Rhs.1, _, Rhs.3, Lhs.1, Lhs.2
4 ~0% {6} | REWRITE WITH Out.2 := 1
4 ~0% {6} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 4 OUTPUT Lhs.4, Lhs.3, Lhs.1, Lhs.0, _, Lhs.5
4 ~0% {6} | REWRITE WITH Out.4 := 1
37827 ~2% {6} r4 = JOIN r2 WITH `_TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::Relevan__#join_rhs#4` ON FIRST 1 OUTPUT Lhs.1, Lhs.2, Lhs.0, Rhs.1, Rhs.2, Rhs.3
0 ~0% {8} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf#prev` ON FIRST 4 OUTPUT Lhs.3, Lhs.2, Lhs.4, Lhs.5, Lhs.0, Lhs.1, Rhs.4, _
{8} | REWRITE WITH Tmp.7 := 1, Out.7 := (InOut.2 - Tmp.7), TEST Out.7 = InOut.6
0 ~0% {6} | SCAN OUTPUT In.4, In.3, In.0, In.1, In.2, In.5
4 ~0% {6} r5 = r3 UNION r4
4 ~0% {7} | JOIN WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 2 OUTPUT Lhs.3, Lhs.2, _, Lhs.4, Lhs.0, Lhs.5, Rhs.2
4 ~0% {7} | REWRITE WITH Tmp.2 := 1, Out.2 := (InOut.3 - Tmp.2)
4 ~0% {7} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 3 OUTPUT Lhs.4, Rhs.3, Lhs.6, Lhs.1, Lhs.0, Lhs.3, Lhs.5
0 ~0% {5} | JOIN WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 3 OUTPUT Lhs.0, Lhs.6, Lhs.4, Lhs.3, Lhs.5
1236652 ~0% {5} r6 = JOIN `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev_delta` WITH `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev` ON FIRST 1 OUTPUT Lhs.0, Lhs.2, Lhs.1, Rhs.1, Rhs.2
742186130 ~20% {5} r7 = JOIN r6 WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#reorder_0_2_1#prev` ON FIRST 2 OUTPUT Lhs.4, Lhs.2, Lhs.0, Lhs.3, Rhs.2
6704 ~0% {8} r8 = JOIN r7 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.1, Lhs.3, Lhs.0, Lhs.4, Rhs.2, Rhs.3, _
{7} | REWRITE WITH Tmp.7 := 1, TEST InOut.6 = Tmp.7 KEEPING 7
1 ~0% {7} | SCAN OUTPUT In.3, In.5, _, In.1, In.0, In.2, In.4
1 ~0% {7} | REWRITE WITH Out.2 := 1
1 ~0% {6} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 4 OUTPUT Lhs.1, Lhs.4, Lhs.5, Lhs.0, Lhs.6, _
1 ~0% {6} | REWRITE WITH Out.5 := 1
6704 ~0% {7} r9 = JOIN r7 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.0, Lhs.4, Rhs.2, Rhs.3, _
{6} | REWRITE WITH Tmp.6 := 1, TEST InOut.5 != Tmp.6 KEEPING 6
6703 ~0% {6} | SCAN OUTPUT In.0, In.1, In.2, In.4, In.3, In.5
0 ~0% {8} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf#prev` ON FIRST 4 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.4, Lhs.3, Lhs.5, Rhs.4, _
{8} | REWRITE WITH Tmp.7 := 1, Out.7 := (InOut.5 - Tmp.7), TEST Out.7 = InOut.6
0 ~0% {6} | SCAN OUTPUT In.4, In.0, In.1, In.2, In.3, In.5
1 ~0% {6} r10 = r8 UNION r9
1 ~0% {7} | JOIN WITH `project#TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameter/2#5ff60e08#bff#3` ON FIRST 1 OUTPUT Lhs.3, Lhs.0, _, Lhs.4, Lhs.1, Lhs.2, Lhs.5
1 ~0% {7} | REWRITE WITH Tmp.2 := 1, Out.2 := (InOut.6 - Tmp.2)
0 ~0% {5} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 4 OUTPUT Lhs.4, Lhs.5, Lhs.0, Lhs.1, Lhs.6
742186130 ~19% {5} r11 = JOIN r6 WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#reorder_0_2_1#prev` ON FIRST 2 OUTPUT Lhs.4, Rhs.2, Lhs.0, Lhs.2, Lhs.3
1230891 ~23% {8} r12 = JOIN r11 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Lhs.0, Lhs.1, Rhs.2, Rhs.3, _
{7} | REWRITE WITH Tmp.7 := 1, TEST InOut.6 = Tmp.7 KEEPING 7
1 ~0% {7} | SCAN OUTPUT In.3, In.5, _, In.4, In.0, In.1, In.2
1 ~0% {7} | REWRITE WITH Out.2 := 1
1 ~0% {6} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 4 OUTPUT Lhs.1, Lhs.4, Lhs.5, Lhs.6, Lhs.0, _
1 ~0% {6} | REWRITE WITH Out.5 := 1
1230891 ~22% {7} r13 = JOIN r11 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Lhs.0, Rhs.2, Rhs.3, _
{6} | REWRITE WITH Tmp.6 := 1, TEST InOut.5 != Tmp.6 KEEPING 6
1230890 ~22% {6} | SCAN OUTPUT In.0, In.2, In.3, In.4, In.1, In.5
0 ~0% {8} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf#prev` ON FIRST 4 OUTPUT Lhs.0, Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.5, Rhs.4, _
{8} | REWRITE WITH Tmp.7 := 1, Out.7 := (InOut.5 - Tmp.7), TEST Out.7 = InOut.6
0 ~0% {6} | SCAN OUTPUT In.4, In.0, In.1, In.2, In.3, In.5
1 ~0% {6} r14 = r12 UNION r13
1 ~0% {7} | JOIN WITH `project#TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameter/2#5ff60e08#bff#3` ON FIRST 1 OUTPUT Lhs.4, Lhs.0, _, Lhs.2, Lhs.1, Lhs.3, Lhs.5
1 ~0% {7} | REWRITE WITH Tmp.2 := 1, Out.2 := (InOut.6 - Tmp.2)
0 ~0% {5} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::CallExprBaseMatching::AccessConstraint::RelevantAccess,TypeInference::CallExprBaseMatching::AccessConstraint::IsInstantiationOfInput>::getNthTypeParameterPath/3#52820dda#bbff` ON FIRST 4 OUTPUT Lhs.4, Lhs.5, Lhs.0, Lhs.1, Lhs.6
0 ~0% {5} r15 = r1 UNION r5 UNION r10 UNION r14
0 ~0% {5} | AND NOT `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/5#a7658501#fffbf#prev`(FIRST 5)
return r15
If you add pragma[nomagic] to IsInstantiationOfInput::potentialInstantiationOf inside ql/lib/codeql/rust/internal/TypeInference.qll and change this predicate to
pragma[nomagic]
private predicate typeParametersEqualFromIndex(
App app, TypeAbstraction abs, TypeMention tm, TypeParameter tp, int i, Type t
) {
potentialInstantiationOf(app, abs, tm) and
exists(TypePath path |
path = getNthTypeParameterPath(tm, tp, i) and
t = app.resolveTypeAt(path) and
if i = 0 then any() else typeParametersEqualFromIndex(app, abs, tm, tp, i - 1, t)
)
}it becomes much better
Pipeline standard for TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/6#b6c58530#reorder_0_1_2_3_5_4@6cb3c5w4 was evaluated in 197 iterations totaling 24ms (delta sizes total: 23565).
1236652 ~1% {5} r1 = JOIN `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev_delta` WITH `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev` ON FIRST 1 OUTPUT Rhs.2, Lhs.1, Lhs.0, Lhs.2, Rhs.1
5001 ~0% {8} r2 = JOIN r1 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.1, Lhs.3, Lhs.4, Lhs.0, Rhs.2, Rhs.3, _
{7} | REWRITE WITH Tmp.7 := 0, TEST InOut.6 = Tmp.7 KEEPING 7
5000 ~1% {7} | SCAN OUTPUT In.4, In.5, _, In.1, In.0, In.2, In.3
5000 ~0% {7} | REWRITE WITH Out.2 := 0
5000 ~1% {6} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371` ON FIRST 4 OUTPUT Lhs.4, Lhs.6, Lhs.0, Lhs.1, Lhs.5, _
5000 ~1% {6} | REWRITE WITH Out.5 := 0
93885 ~0% {5} r3 = JOIN `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev_delta` WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 1 OUTPUT Lhs.2, Rhs.1, Lhs.0, Lhs.1, Rhs.2
18569 ~1% {8} r4 = JOIN r3 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.0, Lhs.1, Lhs.4, Rhs.2, Rhs.3, _
{7} | REWRITE WITH Tmp.7 := 0, TEST InOut.6 = Tmp.7 KEEPING 7
18565 ~1% {7} | SCAN OUTPUT In.2, In.5, _, In.3, In.0, In.1, In.4
18565 ~1% {7} | REWRITE WITH Out.2 := 0
18565 ~1% {6} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371` ON FIRST 4 OUTPUT Lhs.4, Lhs.5, Lhs.0, Lhs.1, Lhs.6, _
18565 ~1% {6} | REWRITE WITH Out.5 := 0
21873 ~0% {6} r5 = SCAN `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/6#b6c58530#reorder_0_1_2_3_5_4#prev_delta` OUTPUT In.0, In.1, In.2, In.3, In.5, In.4
21873 ~0% {8} | JOIN WITH `TypeInference::IsInstantiationOfInput::potentialInstantiationOf/3#d3ebae4e#prev` ON FIRST 3 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.3, Lhs.5, _, Lhs.4, _
{6} | REWRITE WITH Tmp.5 := 1, Out.5 := (Tmp.5 + In.6), Tmp.7 := 0, TEST Out.5 != Tmp.7 KEEPING 6
21873 ~0% {6} | SCAN OUTPUT In.2, In.3, In.5, In.0, In.1, In.4
0 ~0% {7} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371` ON FIRST 3 OUTPUT Lhs.3, Rhs.3, Lhs.5, Lhs.4, Lhs.0, Lhs.1, Lhs.2
0 ~0% {6} | JOIN WITH `TypeInference::ReceiverExpr.resolveTypeAt/1#dispred#ffbfacd4#prev` ON FIRST 3 OUTPUT Lhs.0, Lhs.3, Lhs.4, Lhs.5, Lhs.2, Lhs.6
5001 ~0% {7} r6 = JOIN r1 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Lhs.0, Rhs.2, Rhs.3, _
{6} | REWRITE WITH Tmp.6 := 0, TEST InOut.5 != Tmp.6 KEEPING 6
1 ~0% {6} | SCAN OUTPUT In.0, In.2, In.3, In.4, In.1, In.5
0 ~0% {8} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/6#b6c58530#reorder_0_1_2_3_5_4#prev` ON FIRST 5 OUTPUT Lhs.0, Lhs.4, Lhs.1, Lhs.2, Lhs.3, Lhs.5, Rhs.5, _
{8} | REWRITE WITH Tmp.7 := 1, Out.7 := (InOut.5 - Tmp.7), TEST Out.7 = InOut.6
0 ~0% {6} | SCAN OUTPUT In.0, In.2, In.3, In.4, In.1, In.5
18569 ~0% {7} r7 = JOIN r3 WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::getNthTypeParameterPath/3#40c83371_0312#join_rhs` ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.0, Lhs.4, Rhs.2, Rhs.3, _
{6} | REWRITE WITH Tmp.6 := 0, TEST InOut.5 != Tmp.6 KEEPING 6
4 ~0% {6} | SCAN OUTPUT In.0, In.1, In.2, In.4, In.3, In.5
0 ~0% {8} | JOIN WITH `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/6#b6c58530#reorder_0_1_2_3_5_4#prev` ON FIRST 5 OUTPUT Lhs.0, Lhs.1, Lhs.2, Lhs.4, Lhs.3, Lhs.5, Rhs.5, _
{8} | REWRITE WITH Tmp.7 := 1, Out.7 := (InOut.5 - Tmp.7), TEST Out.7 = InOut.6
0 ~0% {6} | SCAN OUTPUT In.0, In.1, In.2, In.4, In.3, In.5
23565 ~9% {6} r8 = r2 UNION r4 UNION r5 UNION r6 UNION r7
23565 ~9% {6} | AND NOT `TypeInference::M2::IsInstantiationOf<TypeInference::ReceiverExpr,TypeInference::IsInstantiationOfInput>::typeParametersEqualFromIndex/6#b6c58530#reorder_0_1_2_3_5_4#prev`(FIRST 6)
return r8
There was a problem hiding this comment.
The rewrite actually has a small semantic difference, which I think is good: The original version required that adjacent type parameter paths agreed on some type, while the new version requires that all type parameter paths agree on some type, which is not necessarily the same, unless the types are unique.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Adds type inference support for non-universal
implblocks. By "non-universal" we meanimplblocks that target generic types but which are not valid for all instantiations of the generic type.For instance
where the
flattenmethod is only valid for someOptioninstantiations.Non-universal
implblock affect both method resolution and trait implementations as the method/trait implementation can be valid only for some instantiations of a type. AFoo<i64>might have a different set of methods/traits than aFoo<String>. Finding the right method/trait implementation is the crux of the matter. The tests have examples of this.I've tried to document the new additions in this PR with QLdoc, but here are some additional high-level comments on the changes:
As mentioned above, with non-universal
implblocks it is no longer enough to know the root of a type to determine which traits it implements and which methods it supports. This affects a bunch of things.getMethodandgetABaseTypeMentionmember predicate onTypeis removed, as aTypeis now not enough to determine these things.conditionSatisfiesConstrainttakes aTypeMentionas its second parameter as aTypeis not enough.In this PR I've split subtype handling (inferring type parameters through supertypes) from constraint handling (inferring type parameters from type parameter interface constraints (in C#)/trait bounds (in Rust). The former is now the sole job of the
AccessBaseTypesub-module and the later is done in the newAccessConstraintsub-module. There's also a predicate for each in the module signature:getABaseTypeMentionandconditionSatisfiesConstraint.This has both pros and cons:
getABaseTypeMentionasnone()and avoid any computation related to subtyping.All in all I'm not sure which approach is best, but when I made this change performance improved quite a bit (but that was before making some other optimizations) so that's why I ended up with this. Another approach (in follow up work) could be to 1/ merge the two things back again, 2/ add a
getVariancepredicate for access positions than can becovariantorinvariant, 3/ only do subtyping for covariant positions, 4/ make all positions invariant for Rust. That should give equal performance for Rust, cut down on the duplicated code and hopefully the optimization withcountConstraintImplementationswould mean that subtyping for languages like C# wouldn't regress in performance (but we'd have no way to measure that).