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

Commit06351f5

Browse files
Try forcing top-down pairwise comparison
1 parent4825774 commit06351f5

File tree

1 file changed

+63
-75
lines changed

1 file changed

+63
-75
lines changed

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

Lines changed: 63 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -224,7 +224,7 @@ signature predicate interestedInEquality(Type a, Type b);
224224
* Note that `equalTypes(a, b)` only holds if `interestedIn(a, b)` holds. A type is always
225225
* considered to be equal to itself, and this module does not support configurations that declare
226226
* otherwise.
227-
*
227+
*
228228
* Further, `interestedInEquality(a, a)` is treated differently from `interestedInEquality(a, b)`,
229229
* assuming that `a` and `b` are not identical. This is so that we can construct a set of types
230230
* that are not identical, but still may be equivalent by the specified configuration. We also must
@@ -233,45 +233,75 @@ signature predicate interestedInEquality(Type a, Type b);
233233
* only a few are not.
234234
*/
235235
module TypeEquivalence<TypeEquivalenceSig Config,interestedInEquality/2 interestedIn>{
236+
236237
/**
237-
* 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.
238+
* Performance related predicate to force top down rather than bottom up evaluation of type
239+
* equivalence.
241240
*/
242-
predicateequalTypes(Typet1,Typet2){
243-
interestedInUnordered(t1,t2)and
244-
(
245-
// If the types are identical, they are trivially equal.
246-
t1=t2
241+
predicatecompares(Typet1,Typet2){
242+
interestedIn(t1,t2)
243+
or
244+
exists(DerivedTypet1Derived,DerivedTypet2Derived|
245+
nott1DerivedinstanceofSpecifiedTypeand
246+
nott2DerivedinstanceofSpecifiedTypeand
247+
compares(pragma[only_bind_into](t1Derived),pragma[only_bind_into](t2Derived))and
248+
t1=t1Derived.getBaseType()and
249+
t2=t2Derived.getBaseType()
250+
)
251+
or
252+
exists(SpecifiedTypet1Spec,SpecifiedTypet2Spec|
253+
compares(pragma[only_bind_into](t1Spec),pragma[only_bind_into](t2Spec))and
254+
(
255+
t1=unspecify(t1Spec)and
256+
t2=unspecify(t2Spec)
257+
)
258+
)
259+
or
260+
exists(FunctionTypet1Func,FunctionTypet2Func|
261+
compares(pragma[only_bind_into](t1Func),pragma[only_bind_into](t2Func))and
262+
(
263+
t1=t1Func.getReturnType()and
264+
t2=t2Func.getReturnType()
265+
or
266+
exists(inti|
267+
t1=t1Func.getParameterType(pragma[only_bind_out](i))and
268+
t2=t2Func.getParameterType(i)
269+
)
270+
)
271+
)
272+
or
273+
Config::resolveTypedefs()and
274+
exists(TypedefTypetdtype|
275+
tdtype.getBaseType()=t1and
276+
compares(pragma[only_bind_into](tdtype),t2)
247277
or
248-
nott1=t2and
249-
equalTypesImpl(t1,t2)
278+
tdtype.getBaseType()=t2and
279+
compares(t1,pragma[only_bind_into](tdtype))
250280
)
251281
}
252282

253283
/**
254-
* This implementation handles only the slow and complex cases of type equivalence, where the
255-
* types are not identical.
284+
* Check whether two types are equivalent, as defined by the `TypeEquivalenceSig` module.
256285
*
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.
286+
*This only holds if the specified predicate `interestedIn` holds for the types, and always
287+
*holds if `t1` and `t2` are identical.
259288
*/
260-
privatepredicateequalTypesImpl(RelevantTypet1,RelevantTypet2){
289+
privatepredicateequalTypes(Typet1,Typet2){
290+
compares(pragma[only_bind_into](t1),pragma[only_bind_into](t2))and
261291
if Config::overrideTypeComparison(t1,t2, _)
262292
then Config::overrideTypeComparison(t1,t2,true)
263293
else
264294
ift1instanceofTypedefTypeand Config::resolveTypedefs()
265-
thenequalTypesImpl(t1.(TypedefType).getBaseType(),t2)
295+
thenequalTypes(t1.(TypedefType).getBaseType(),t2)
266296
else
267297
ift2instanceofTypedefTypeand Config::resolveTypedefs()
268-
thenequalTypesImpl(t1,t2.(TypedefType).getBaseType())
298+
thenequalTypes(t1,t2.(TypedefType).getBaseType())
269299
else(
270300
nott1instanceofDerivedTypeand
271301
nott2instanceofDerivedTypeand
272302
nott1instanceofTypedefTypeand
273303
nott2instanceofTypedefTypeand
274-
LeafEquiv::getEquivalenceClass(t1)= LeafEquiv::getEquivalenceClass(t2)
304+
equalLeafRelation(t1,t2)
275305
or
276306
equalDerivedTypes(t1,t2)
277307
or
@@ -284,56 +314,14 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
284314
/** Whether two types will be compared, regardless of order (a, b) or (b, a). */
285315
privatepredicateinterestedInUnordered(Typet1,Typet2){
286316
interestedIn(t1,t2)or
287-
interestedIn(t2,t1)}
288-
289-
finalprivateclassFinalType=Type;
290-
291-
/**
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.
294-
*/
295-
privateclassInterestingTypeextendsFinalType{
296-
InterestingType(){
297-
exists(TypeinexactCompare|
298-
interestedInUnordered(this, _)and
299-
notinexactCompare=this
300-
)
301-
}
302-
}
303-
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))}
317+
interestedIn(t2,t1)
314318
}
315319

316-
privateclassRelevantDerivedTypeextendsRelevantTypeinstanceofDerivedType{
317-
RelevantTypegetBaseType(){result=this.(DerivedType).getBaseType()}
318-
}
319-
320-
privateclassRelevantFunctionTypeextendsRelevantTypeinstanceofFunctionType{
321-
RelevantTypegetReturnType(){result=this.(FunctionType).getReturnType()}
322-
323-
RelevantTypegetParameterType(inti){result=this.(FunctionType).getParameterType(i)}
324-
}
325-
326-
privateclassRelevantTypedefTypeextendsRelevantTypeinstanceofTypedefType{
327-
RelevantTypegetBaseType(){result=this.(TypedefType).getBaseType()}
328-
}
329-
330-
privatemodule LeafEquiv= QlBuiltins::EquivalenceRelation<RelevantType,equalLeafRelation/2>;
331-
332-
privatepredicateequalLeafRelation(RelevantTypet1,RelevantTypet2){
333-
Config::equalLeafTypes(t1,t2)
334-
}
320+
bindingset[t1, t2]
321+
privatepredicateequalLeafRelation(Typet1,Typet2){ Config::equalLeafTypes(t1,t2)}
335322

336-
privateRelevantTypeunspecify(SpecifiedTypet){
323+
bindingset[t]
324+
privateTypeunspecify(SpecifiedTypet){
337325
// This subtly and importantly handles the complicated cases of typedefs. Under most scenarios,
338326
// if we see a typedef in `equalTypes()` we can simply get the base type and continue. However,
339327
// there is an exception if we have a specified type that points to a typedef that points to
@@ -347,9 +335,9 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
347335
}
348336

349337
bindingset[t1, t2]
350-
privatepredicateequalDerivedTypes(RelevantDerivedTypet1,RelevantDerivedTypet2){
338+
privatepredicateequalDerivedTypes(DerivedTypet1,DerivedTypet2){
351339
exists(BooleanbaseTypesEqual|
352-
(baseTypesEqual=trueimpliesequalTypesImpl(t1.getBaseType(),t2.getBaseType()))and
340+
(baseTypesEqual=trueimpliesequalTypes(t1.getBaseType(),t2.getBaseType()))and
353341
(
354342
Config::equalPointerTypes(t1,t2,baseTypesEqual)
355343
or
@@ -363,20 +351,20 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
363351
// Note that this case is different from the above, in that we don't merely get the base
364352
// type (as that could be a TypedefType that points to another SpecifiedType). We need to
365353
// unspecify the type to see if the base types are equal.
366-
(unspecifiedTypesEqual=trueimpliesequalTypesImpl(unspecify(t1),unspecify(t2)))and
354+
(unspecifiedTypesEqual=trueimpliesequalTypes(unspecify(t1),unspecify(t2)))and
367355
Config::equalSpecifiedTypes(t1,t2,unspecifiedTypesEqual)
368356
)
369357
}
370358

371359
bindingset[t1, t2]
372-
privatepredicateequalFunctionTypes(RelevantFunctionTypet1,RelevantFunctionTypet2){
360+
privatepredicateequalFunctionTypes(FunctionTypet1,FunctionTypet2){
373361
exists(BooleanreturnTypeEqual,BooleanparameterTypesEqual|
374-
(returnTypeEqual=trueimpliesequalTypesImpl(t1.getReturnType(),t2.getReturnType()))and
362+
(returnTypeEqual=trueimpliesequalTypes(t1.getReturnType(),t2.getReturnType()))and
375363
(
376364
parameterTypesEqual=true
377365
implies
378366
forall(inti|exists([t1,t2].getParameterType(i))|
379-
equalTypesImpl(t1.getParameterType(i),t2.getParameterType(i))
367+
equalTypes(t1.getParameterType(i),t2.getParameterType(i))
380368
)
381369
)and
382370
(
@@ -388,9 +376,9 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
388376
}
389377

390378
bindingset[t1, t2]
391-
privatepredicateequalTypedefTypes(RelevantTypedefTypet1,RelevantTypedefTypet2){
379+
privatepredicateequalTypedefTypes(TypedefTypet1,TypedefTypet2){
392380
exists(BooleanbaseTypesEqual|
393-
(baseTypesEqual=trueimpliesequalTypesImpl(t1.getBaseType(),t2.getBaseType()))and
381+
(baseTypesEqual=trueimpliesequalTypes(t1.getBaseType(),t2.getBaseType()))and
394382
Config::equalTypedefTypes(t1,t2,baseTypesEqual)
395383
)
396384
}

0 commit comments

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