Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7f6b32d

Browse files
Try new approach to reduce search set in type equivalence, some new join orders.
More pragmas added to encourage the join ordering pipeline to make functioncomparisons more efficient.New approach in type equivalence assumes that all types are trivially equivalentto themselves. Therefore, only type comparisons between non-identical types needto be considered as interesting roots. The types that are reachable in the typegraph from these roots are the ones considered by the recursive type equivalencepredicate.
1 parent472c93a commit7f6b32d

File tree

8 files changed

+199
-80
lines changed

8 files changed

+199
-80
lines changed

‎c/misra/src/rules/RULE-23-5/DangerousDefaultSelectionForPointerInGeneric.ql‎

Lines changed: 8 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -20,18 +20,14 @@ import codingstandards.cpp.types.LvalueConversion
2020
import codingstandards.cpp.types.SimpleAssignment
2121

2222
predicatetypesCompatible(Typet1,Typet2){
23-
TypeEquivalence<TypesCompatibleConfig,TypeFromGeneric>::equalTypes(t1,t2)
23+
TypeEquivalence<TypesCompatibleConfig,relevantTypes/2>::equalTypes(t1,t2)
2424
}
2525

26-
classTypeFromGenericextendsType{
27-
TypeFromGeneric(){
28-
exists(C11GenericExprg|
29-
(
30-
this=g.getAssociationType(_)or
31-
this=g.getControllingExpr().getFullyConverted().getType()
32-
)
33-
)
34-
}
26+
predicaterelevantTypes(Typea,Typeb){
27+
exists(C11GenericExprg|
28+
a=g.getAnAssociationType()and
29+
b=getLvalueConverted(g.getControllingExpr().getFullyConverted().getType())
30+
)
3531
}
3632

3733
predicatemissesOnPointerConversion(Typeprovided,Typeexpected){
@@ -40,11 +36,11 @@ predicate missesOnPointerConversion(Type provided, Type expected) {
4036
// But 6.5.16.1 simple assignment constraints would have been satisfied:
4137
(
4238
// Check as if the controlling expr is assigned to the expected type:
43-
SimpleAssignment<TypeFromGeneric>::satisfiesSimplePointerAssignment(expected,provided)
39+
SimpleAssignment<relevantTypes/2>::satisfiesSimplePointerAssignment(expected,provided)
4440
or
4541
// Since developers typically rely on the compiler to catch const/non-const assignment
4642
// errors, don't assume a const-to-non-const generic selection miss was intentional.
47-
SimpleAssignment<TypeFromGeneric>::satisfiesSimplePointerAssignment(provided,expected)
43+
SimpleAssignment<relevantTypes/2>::satisfiesSimplePointerAssignment(provided,expected)
4844
)
4945
}
5046

‎c/misra/src/rules/RULE-8-3/DeclarationsOfAFunctionSameNameAndType.ql‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,12 @@ import cpp
1616
import codingstandards.c.misra
1717
import codingstandards.cpp.types.Compatible
1818

19+
predicateinterestedInFunctions(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2){
20+
f1.getDeclaration()=f2.getDeclaration()and
21+
notf1=f2and
22+
f1.getDeclaration()=f2.getDeclaration()
23+
}
24+
1925
fromFunctionDeclarationEntryf1,FunctionDeclarationEntryf2,stringcase,stringpluralDo
2026
where
2127
notisExcluded(f1, Declarations4Package::declarationsOfAFunctionSameNameAndTypeQuery())and
@@ -24,12 +30,12 @@ where
2430
f1.getDeclaration()=f2.getDeclaration()and
2531
//return type check
2632
(
27-
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig>::equalReturnTypes(f1,f2)and
33+
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig,interestedInFunctions/2>::equalReturnTypes(f1,f2)and
2834
case="return type"and
2935
pluralDo="does"
3036
or
3137
//parameter type check
32-
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig>::equalParameterTypes(f1,f2)and
38+
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig,interestedInFunctions/2>::equalParameterTypes(f1,f2)and
3339
case="parameter types"and
3440
pluralDo="do"
3541
or

‎c/misra/src/rules/RULE-8-3/DeclarationsOfAnObjectSameNameAndType.ql‎

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -16,15 +16,6 @@ import cpp
1616
import codingstandards.c.misra
1717
import codingstandards.cpp.types.Compatible
1818

19-
classRelevantTypeextendsType{
20-
RelevantType(){
21-
exists(VariableDeclarationEntrydecl|
22-
(relevantPair(decl, _)orrelevantPair(_,decl))and
23-
decl.getType()=this
24-
)
25-
}
26-
}
27-
2819
predicaterelevantPair(VariableDeclarationEntrydecl1,VariableDeclarationEntrydecl2){
2920
notdecl1=decl2and
3021
notdecl1.getVariable().getDeclaringType().isAnonymous()and
@@ -43,12 +34,20 @@ predicate relevantPair(VariableDeclarationEntry decl1, VariableDeclarationEntry
4334
)
4435
}
4536

37+
predicaterelevantTypes(Typea,Typeb){
38+
exists(VariableDeclarationEntryvarA,VariableDeclarationEntryvarB|
39+
a=varA.getType()and
40+
b=varB.getType()and
41+
relevantPair(varA,varB)
42+
)
43+
}
44+
4645
fromVariableDeclarationEntrydecl1,VariableDeclarationEntrydecl2
4746
where
4847
notisExcluded(decl1, Declarations4Package::declarationsOfAnObjectSameNameAndTypeQuery())and
4948
notisExcluded(decl2, Declarations4Package::declarationsOfAnObjectSameNameAndTypeQuery())and
5049
relevantPair(decl1,decl2)and
51-
not TypeEquivalence<TypeNamesMatchConfig,RelevantType>::equalTypes(decl1.getType(),
50+
not TypeEquivalence<TypeNamesMatchConfig,relevantTypes/2>::equalTypes(decl1.getType(),
5251
decl2.getType())
5352
selectdecl1,
5453
"The object $@ of type "+decl1.getType().toString()+

‎c/misra/src/rules/RULE-8-4/CompatibleDeclarationFunctionDefined.ql‎

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,16 @@ import codingstandards.c.misra
1919
import codingstandards.cpp.Identifiers
2020
import codingstandards.cpp.types.Compatible
2121

22+
predicateinterestedInFunctions(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2){
23+
f1.getDeclaration()instanceofExternalIdentifiersand
24+
f1.isDefinition()and
25+
f1.getName()=f2.getName()and
26+
f1.getDeclaration()=f2.getDeclaration()and
27+
notf2.isDefinition()and
28+
notf1.isFromTemplateInstantiation(_)and
29+
notf2.isFromTemplateInstantiation(_)
30+
}
31+
2232
fromFunctionDeclarationEntryf1
2333
where
2434
notisExcluded(f1, Declarations4Package::compatibleDeclarationFunctionDefinedQuery())and
@@ -38,10 +48,12 @@ where
3848
f2.getDeclaration()=f1.getDeclaration()and
3949
(
4050
//return types differ
41-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalReturnTypes(f1,f2)
51+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig,interestedInFunctions/2>::equalReturnTypes(f1,
52+
f2)
4253
or
4354
//parameter types differ
44-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalParameterTypes(f1,f2)
55+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig,interestedInFunctions/2>::equalParameterTypes(f1,
56+
f2)
4557
or
4658
//parameter names differ
4759
parameterNamesUnmatched(f1,f2)

‎c/misra/src/rules/RULE-8-4/CompatibleDeclarationObjectDefined.ql‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,13 @@ import codingstandards.c.misra
1919
import codingstandards.cpp.Identifiers
2020
import codingstandards.cpp.types.Compatible
2121

22-
classRelevantTypeextendsType{
23-
RelevantType(){
24-
exists(VariableDeclarationEntrydecl|
25-
count(VariableDeclarationEntryothers|others.getDeclaration()=decl.getDeclaration())>1and
26-
decl.getType()=this
27-
)
28-
}
22+
predicaterelevantTypes(Typea,Typeb){
23+
exists(VariableDeclarationEntryvarA,VariableDeclarationEntryvarB|
24+
notvarA=varBand
25+
varA.getDeclaration()=varB.getDeclaration()and
26+
a=varA.getType()and
27+
b=varB.getType()
28+
)
2929
}
3030

3131
fromVariableDeclarationEntrydecl1
@@ -37,7 +37,7 @@ where
3737
notexists(VariableDeclarationEntrydecl2|
3838
notdecl2.isDefinition()and
3939
decl1.getDeclaration()=decl2.getDeclaration()and
40-
TypeEquivalence<TypesCompatibleConfig,RelevantType>::equalTypes(decl1.getType(),
40+
TypeEquivalence<TypesCompatibleConfig,relevantTypes/2>::equalTypes(decl1.getType(),
4141
decl2.getType())
4242
)
4343
selectdecl1,"No separate compatible declaration found for this definition."
Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
-`RULE-8-3`,`RULE-8-4`,`DCL40-C`,`RULE-23-5`:`DeclarationsOfAFunctionSameNameAndType.ql`,`DeclarationsOfAnObjectSameNameAndType.ql`,`CompatibleDeclarationOfFunctionDefined.ql`,`CompatibleDeclarationObjectDefined.ql`,`IncompatibleFunctionDeclarations.ql`,`DangerousDefaultSelectionForPointerInGeneric.ql`:
2+
- Added pragmas to alter join order on function parameter equivalence (names and types).
3+
- Refactored expression which the optimizer was confused by, and compiled into a cartesian product.
4+
- Altered the module`Compatible.qll` to only perform expensive equality checks on types that are compared to a non identical other type, and those reachable from those types in the type graph. Types that are identical will trivially be considered equivalent.
5+
-`RULE-23-5`:`DangerousDefaultSelectionForPointerInGeneric.ql`:
6+
- Altered the module`SimpleAssignment.qll` in accordance with the changes to`Compatible.qll`.

‎cpp/common/src/codingstandards/cpp/types/Compatible.qll‎

Lines changed: 101 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ class VariableType extends Type {
2525
}
2626

2727
predicateparameterNamesUnmatched(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2){
28-
f1.getDeclaration()=f2.getDeclaration()and
28+
pragma[only_bind_into](f1).getDeclaration()=pragma[only_bind_into](f2).getDeclaration()and
2929
exists(stringp1Name,stringp2Name,inti|
3030
p1Name=f1.getParameterDeclarationEntry(i).getName()and
3131
p2Name=f2.getParameterDeclarationEntry(i).getName()
@@ -208,34 +208,64 @@ signature module TypeEquivalenceSig {
208208
module DefaultEquivalenceimplementsTypeEquivalenceSig{}
209209

210210
/**
211-
* A signatureclass used to restrict the set of types considered by `TypeEquivalence`, for
211+
* A signaturepredicate used to restrict the set of types considered by `TypeEquivalence`, for
212212
* performance reasons.
213213
*/
214-
signatureclassTypeSubsetextendsType;
214+
signaturepredicateinterestedInEquality(Typea,Typeb);
215215

216216
/**
217217
* A module to check the equivalence of two types, as defined by the provided `TypeEquivalenceSig`.
218218
*
219-
* For performance reasons, this module is designed to be used with a `TypeSubset` that restricts
220-
* the set of considered types. All types reachable (in the type graph) from a type in the subset
221-
* will be considered. (See `RelevantType`.)
219+
* For performance reasons, this module is designed to be used with a predicate
220+
* `interestedInEquality` that restricts the set of considered types.
222221
*
223222
* To use this module, define a `TypeEquivalenceSig` module and implement a subset of `Type` that
224223
* selects the relevant root types to be considered. Then use the predicate `equalTypes(a, b)`.
224+
* Note that `equalTypes(a, b)` only holds if `interestedIn(a, b)` holds. A type is always
225+
* considered to be equal to itself, and this module does not support configurations that declare
226+
* otherwise.
227+
*
228+
* Further, `interestedInEquality(a, a)` is treated differently from `interestedInEquality(a, b)`,
229+
* assuming that `a` and `b` are not identical. This is so that we can construct a set of types
230+
* that are not identical, but still may be equivalent by the specified configuration. We also must
231+
* consider all types that are reachable from these types, as the equivalence relation is
232+
* recursive. Therefore, this module is more performant when most comparisons are identical, and
233+
* only a few are not.
225234
*/
226-
module TypeEquivalence<TypeEquivalenceSig Config,TypeSubset T>{
235+
module TypeEquivalence<TypeEquivalenceSig Config,interestedInEquality/2 interestedIn>{
227236
/**
228237
* Check whether two types are equivalent, as defined by the `TypeEquivalenceSig` module.
238+
*
239+
* This only holds if the specified predicate `interestedIn` holds for the types, and always
240+
* holds if `t1` and `t2` are identical.
229241
*/
230-
predicateequalTypes(RelevantTypet1,RelevantTypet2){
242+
predicateequalTypes(Typet1,Typet2){
243+
interestedInUnordered(t1,t2)and
244+
(
245+
// If the types are identical, they are trivially equal.
246+
t1=t2
247+
or
248+
nott1=t2and
249+
equalTypesImpl(t1,t2)
250+
)
251+
}
252+
253+
/**
254+
* This implementation handles only the slow and complex cases of type equivalence, where the
255+
* types are not identical.
256+
*
257+
* Assuming that types a, b must be compared where `a` and `b` are not identical, we wish to
258+
* search only the smallest set of possible relevant types. See `RelevantType` for more.
259+
*/
260+
privatepredicateequalTypesImpl(RelevantTypet1,RelevantTypet2){
231261
if Config::overrideTypeComparison(t1,t2, _)
232262
then Config::overrideTypeComparison(t1,t2,true)
233263
else
234264
ift1instanceofTypedefTypeand Config::resolveTypedefs()
235-
thenequalTypes(t1.(TypedefType).getBaseType(),t2)
265+
thenequalTypesImpl(t1.(TypedefType).getBaseType(),t2)
236266
else
237267
ift2instanceofTypedefTypeand Config::resolveTypedefs()
238-
thenequalTypes(t1,t2.(TypedefType).getBaseType())
268+
thenequalTypesImpl(t1,t2.(TypedefType).getBaseType())
239269
else(
240270
nott1instanceofDerivedTypeand
241271
nott2instanceofDerivedTypeand
@@ -251,13 +281,36 @@ module TypeEquivalence<TypeEquivalenceSig Config, TypeSubset T> {
251281
)
252282
}
253283

284+
/** Whether two types will be compared, regardless of order (a, b) or (b, a). */
285+
privatepredicateinterestedInUnordered(Typet1,Typet2){
286+
interestedIn(t1,t2)or
287+
interestedIn(t2,t1)}
288+
289+
finalprivateclassFinalType=Type;
290+
254291
/**
255-
* A type that is either part of the type subset, or that is reachable from a type in the subset.
292+
* A type that is compared to another type that is not identical. This is the set of types that
293+
* form the roots of our more expensive type equivalence analysis.
256294
*/
257-
privateclassRelevantTypeinstanceofType{
258-
RelevantType(){exists(Tt|typeGraph*(t,this))}
295+
privateclassInterestingTypeextendsFinalType{
296+
InterestingType(){
297+
exists(TypeinexactCompare|
298+
interestedInUnordered(this, _)and
299+
notinexactCompare=this
300+
)
301+
}
302+
}
259303

260-
stringtoString(){result=this.(Type).toString()}
304+
/**
305+
* A type that is reachable from an `InterestingType` (a type that is compared to a non-identical
306+
* type).
307+
*
308+
* Since type equivalence is recursive, CodeQL will consider the equality of these types in a
309+
* bottom-up evaluation, with leaf nodes first. Therefore, this set must be as small as possible
310+
* in order to be efficient.
311+
*/
312+
privateclassRelevantTypeextendsFinalType{
313+
RelevantType(){exists(InterestingTypet|typeGraph*(t,this))}
261314
}
262315

263316
privateclassRelevantDerivedTypeextendsRelevantTypeinstanceofDerivedType{
@@ -296,7 +349,7 @@ module TypeEquivalence<TypeEquivalenceSig Config, TypeSubset T> {
296349
bindingset[t1, t2]
297350
privatepredicateequalDerivedTypes(RelevantDerivedTypet1,RelevantDerivedTypet2){
298351
exists(BooleanbaseTypesEqual|
299-
(baseTypesEqual=trueimpliesequalTypes(t1.getBaseType(),t2.getBaseType()))and
352+
(baseTypesEqual=trueimpliesequalTypesImpl(t1.getBaseType(),t2.getBaseType()))and
300353
(
301354
Config::equalPointerTypes(t1,t2,baseTypesEqual)
302355
or
@@ -310,20 +363,20 @@ module TypeEquivalence<TypeEquivalenceSig Config, TypeSubset T> {
310363
// Note that this case is different from the above, in that we don't merely get the base
311364
// type (as that could be a TypedefType that points to another SpecifiedType). We need to
312365
// unspecify the type to see if the base types are equal.
313-
(unspecifiedTypesEqual=trueimpliesequalTypes(unspecify(t1),unspecify(t2)))and
366+
(unspecifiedTypesEqual=trueimpliesequalTypesImpl(unspecify(t1),unspecify(t2)))and
314367
Config::equalSpecifiedTypes(t1,t2,unspecifiedTypesEqual)
315368
)
316369
}
317370

318371
bindingset[t1, t2]
319372
privatepredicateequalFunctionTypes(RelevantFunctionTypet1,RelevantFunctionTypet2){
320373
exists(BooleanreturnTypeEqual,BooleanparameterTypesEqual|
321-
(returnTypeEqual=trueimpliesequalTypes(t1.getReturnType(),t2.getReturnType()))and
374+
(returnTypeEqual=trueimpliesequalTypesImpl(t1.getReturnType(),t2.getReturnType()))and
322375
(
323376
parameterTypesEqual=true
324377
implies
325378
forall(inti|exists([t1,t2].getParameterType(i))|
326-
equalTypes(t1.getParameterType(i),t2.getParameterType(i))
379+
equalTypesImpl(t1.getParameterType(i),t2.getParameterType(i))
327380
)
328381
)and
329382
(
@@ -337,30 +390,52 @@ module TypeEquivalence<TypeEquivalenceSig Config, TypeSubset T> {
337390
bindingset[t1, t2]
338391
privatepredicateequalTypedefTypes(RelevantTypedefTypet1,RelevantTypedefTypet2){
339392
exists(BooleanbaseTypesEqual|
340-
(baseTypesEqual=trueimpliesequalTypes(t1.getBaseType(),t2.getBaseType()))and
393+
(baseTypesEqual=trueimpliesequalTypesImpl(t1.getBaseType(),t2.getBaseType()))and
341394
Config::equalTypedefTypes(t1,t2,baseTypesEqual)
342395
)
343396
}
344397
}
345398

346-
module FunctionDeclarationTypeEquivalence<TypeEquivalenceSig Config>{
399+
signaturepredicateinterestedInFunctionDeclarations(
400+
FunctionDeclarationEntryf1,FunctionDeclarationEntryf2
401+
);
402+
403+
module FunctionDeclarationTypeEquivalence<
404+
TypeEquivalenceSig Config,interestedInFunctionDeclarations/2 interestedInFunctions>
405+
{
406+
privatepredicateinterestedInReturnTypes(Typea,Typeb){
407+
exists(FunctionDeclarationEntryaFun,FunctionDeclarationEntrybFun|
408+
interestedInFunctions(aFun,bFun)and
409+
a=aFun.getType()and
410+
b=bFun.getType()
411+
)
412+
}
413+
414+
privatepredicateinterestedInParameterTypes(Typea,Typeb){
415+
exists(FunctionDeclarationEntryaFun,FunctionDeclarationEntrybFun,inti|
416+
interestedInFunctions(pragma[only_bind_into](aFun),pragma[only_bind_into](bFun))and
417+
a=aFun.getParameterDeclarationEntry(i).getType()and
418+
b=bFun.getParameterDeclarationEntry(i).getType()
419+
)
420+
}
421+
347422
predicateequalReturnTypes(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2){
348-
TypeEquivalence<Config,FunctionSignatureType>::equalTypes(f1.getType(),f2.getType())
423+
TypeEquivalence<Config,interestedInReturnTypes/2>::equalTypes(f1.getType(),f2.getType())
349424
}
350425

351426
predicateequalParameterTypes(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2){
427+
interestedInFunctions(f1,f2)and
352428
f1.getDeclaration()=f2.getDeclaration()and
353429
forall(inti|exists([f1,f2].getParameterDeclarationEntry(i))|
354430
equalParameterTypesAt(f1,f2,pragma[only_bind_into](i))
355431
)
356432
}
357433

358434
predicateequalParameterTypesAt(FunctionDeclarationEntryf1,FunctionDeclarationEntryf2,inti){
359-
pragma[only_bind_out](f1.getDeclaration())=pragma[only_bind_out](f2.getDeclaration())and
360-
TypeEquivalence<Config,FunctionSignatureType>::equalTypes(
361-
f1.getParameterDeclarationEntry(i).getType(),
362-
f2.getParameterDeclarationEntry(i).getType()
363-
)
435+
interestedInFunctions(f1,f2)and
436+
f1.getDeclaration()=f2.getDeclaration()and
437+
TypeEquivalence<Config,interestedInParameterTypes/2>::equalTypes(f1.getParameterDeclarationEntry(pragma[only_bind_into](i))
438+
.getType(),f2.getParameterDeclarationEntry(pragma[only_bind_into](i)).getType())
364439
}
365440
}
366441

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp