Skip to content

Navigation Menu

Sign in

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
Appearance settings

Commit 4b8cdd3

Browse filesBrowse files
MichaelRFairhurstMichaelRFairhurst
committed
Address next round of feedback
1 parent bc6a234 commit 4b8cdd3
Copy full SHA for 4b8cdd3

File tree

2 files changed

+67
-47
lines changed
Filter options

2 files changed

+67
-47
lines changed

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

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-8-4/CompatibleDeclarationFunctionDefined.ql
+4-1Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,8 +22,9 @@ import codingstandards.cpp.types.Compatible
2222
predicate interestedInFunctions(FunctionDeclarationEntry f1, FunctionDeclarationEntry f2) {
2323
f1.getDeclaration() instanceof ExternalIdentifiers and
2424
f1.isDefinition() and
25-
f1.getName() = f2.getName() and
2625
f1.getDeclaration() = f2.getDeclaration() and
26+
// This condition should always hold, but removing it affects join order performance.
27+
f1.getName() = f2.getName() and
2728
not f2.isDefinition() and
2829
not f1.isFromTemplateInstantiation(_) and
2930
not f2.isFromTemplateInstantiation(_)
@@ -51,10 +52,12 @@ where
5152
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalReturnTypes(f1,
5253
f2)
5354
or
55+
//not compatibleReturns(f1, f2)
5456
//parameter types differ
5557
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalParameterTypes(f1,
5658
f2)
5759
or
60+
//not compatibleParams(f1, f2)
5861
//parameter names differ
5962
parameterNamesUnmatched(f1, f2)
6063
)

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

Copy file name to clipboardExpand all lines: cpp/common/src/codingstandards/cpp/types/Compatible.qll
+63-46Lines changed: 63 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -231,38 +231,46 @@ signature predicate interestedInEquality(Type a, Type b);
231231
* compared. However, if `Config::equalPointerTypes(a, b, false)` holds, then `a` and `b` will be
232232
* compared, but their pointed-to types will not. Similarly, inner types will not be compared if
233233
* `Config::overrideTypeComparison(a, b, _)` holds. For detail, see the module predicates
234-
* `recurses` and `compares`.
234+
* `shouldRecurseOn` and `interestedInNestedTypes`.
235235
*/
236236
module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interestedIn> {
237237
/**
238-
* Performance related predicate to force top down rather than bottom up evaluation of type
239-
* equivalence.
238+
* Performance-related predicate that holds for a pair of types `(a, b)` such that
239+
* `interestedIn(a, b)` holds, or there exists a pair of types `(c, d)` such that
240+
* `interestedIn(c, d)` holds, and computing `equalTypes(a, b)` requires computing
241+
* `equalTypes(c, d)`.
242+
*
243+
* The goal of this predicate is to force top down rather than bottom up evaluation of type
244+
* equivalence. That is to say, if we compare array types `int[]` and `int[]`, we to compare that
245+
* both types are arrays first, and then compare that their base types are equal. Naively, CodeQL
246+
* is liable to compute this kind of recursive equality in a bottom up fashion, where the cross
247+
* product of all types is considered in computing `equalTypes(a, b)`.
240248
*
241-
* This interoperates with the predicate `recurses` to find types that will be compared, along
242-
* with the inner types of those types that will be compared. See `recurses` for cases where this
243-
* algorithm will or will not recurse. We still need to know which types are compared, even if
244-
* we do not recurse on them, in order to properly constrain `equalTypes(x, y)` to hold for types
245-
* such as leaf types, where we do not recurse during comparison.
249+
* This interoperates with the predicate `shouldRecurseOn` to find types that will be compared,
250+
* along with the inner types of those types that will be compared. See `shouldRecurseOn` for
251+
* cases where this algorithm will or will not recurse. We still need to know which types are
252+
* compared, even if we do not recurse on them, in order to properly constrain `equalTypes(x, y)`
253+
* to hold for types such as leaf types, where we do not recurse during comparison.
246254
*
247255
* At each stage of recursion, we specify `pragma[only_bind_into]` to ensure that the
248-
* prior `recurses` results are considered first in the pipeline.
256+
* prior `shouldRecurseOn` results are considered first in the pipeline.
249257
*/
250-
predicate compares(Type t1, Type t2) {
258+
private predicate interestedInNestedTypes(Type t1, Type t2) {
251259
// Base case: config specifies that these root types will be compared.
252260
interestedInUnordered(t1, t2)
253261
or
254262
// If derived types are compared, their base types must be compared.
255263
exists(DerivedType t1Derived, DerivedType t2Derived |
256264
not t1Derived instanceof SpecifiedType and
257265
not t2Derived instanceof SpecifiedType and
258-
recurses(pragma[only_bind_into](t1Derived), pragma[only_bind_into](t2Derived)) and
266+
shouldRecurseOn(pragma[only_bind_into](t1Derived), pragma[only_bind_into](t2Derived)) and
259267
t1 = t1Derived.getBaseType() and
260268
t2 = t2Derived.getBaseType()
261269
)
262270
or
263271
// If specified types are compared, their unspecified types must be compared.
264272
exists(SpecifiedType t1Spec, SpecifiedType t2Spec |
265-
recurses(pragma[only_bind_into](t1Spec), pragma[only_bind_into](t2Spec)) and
273+
shouldRecurseOn(pragma[only_bind_into](t1Spec), pragma[only_bind_into](t2Spec)) and
266274
(
267275
t1 = unspecify(t1Spec) and
268276
t2 = unspecify(t2Spec)
@@ -271,7 +279,7 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
271279
or
272280
// If function types are compared, their return types and parameter types must be compared.
273281
exists(FunctionType t1Func, FunctionType t2Func |
274-
recurses(pragma[only_bind_into](t1Func), pragma[only_bind_into](t2Func)) and
282+
shouldRecurseOn(pragma[only_bind_into](t1Func), pragma[only_bind_into](t2Func)) and
275283
(
276284
t1 = t1Func.getReturnType() and
277285
t2 = t2Func.getReturnType()
@@ -288,15 +296,15 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
288296
Config::resolveTypedefs() and
289297
exists(TypedefType tdtype |
290298
tdtype.getBaseType() = t1 and
291-
recurses(pragma[only_bind_into](tdtype), t2)
299+
shouldRecurseOn(pragma[only_bind_into](tdtype), t2)
292300
or
293301
tdtype.getBaseType() = t2 and
294-
recurses(t1, pragma[only_bind_into](tdtype))
302+
shouldRecurseOn(t1, pragma[only_bind_into](tdtype))
295303
)
296304
or
297305
// If two typedef types are compared, then their base types must be compared.
298306
exists(TypedefType t1Typedef, TypedefType t2Typedef |
299-
recurses(pragma[only_bind_into](t1Typedef), pragma[only_bind_into](t2Typedef)) and
307+
shouldRecurseOn(pragma[only_bind_into](t1Typedef), pragma[only_bind_into](t2Typedef)) and
300308
(
301309
t1 = t1Typedef.getBaseType() and
302310
t2 = t2Typedef.getBaseType()
@@ -309,7 +317,8 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
309317
* equivalence.
310318
*
311319
* This predicate is used to determine whether we should recurse on a type. It is used in
312-
* conjunction with the `compares` predicate to only recurse on types that are being compared.
320+
* conjunction with the `interestedInNestedTypes` predicate to only recurse on types that are
321+
* being compared.
313322
*
314323
* We don't recurse on identical types, as they are already equal. We also don't recurse on
315324
* types that are overriden by `Config::overrideTypeComparison`, as that predicate determines
@@ -322,9 +331,9 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
322331
*
323332
* We do not recurse on leaf types.
324333
*/
325-
private predicate recurses(Type t1, Type t2) {
334+
private predicate shouldRecurseOn(Type t1, Type t2) {
326335
// We only recurse on types we are comparing.
327-
compares(pragma[only_bind_into](t1), pragma[only_bind_into](t2)) and
336+
interestedInNestedTypes(pragma[only_bind_into](t1), pragma[only_bind_into](t2)) and
328337
// We don't recurse on identical types, as they are already equal.
329338
not t1 = t2 and
330339
// We don't recurse on overriden comparisons
@@ -353,45 +362,45 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
353362
or
354363
// We resolve typedefs, and one of these types is a typedef type: recurse.
355364
Config::resolveTypedefs() and
356-
t1 instanceof TypedefType
357-
or
358-
t2 instanceof TypedefType
365+
(
366+
t1 instanceof TypedefType
367+
or
368+
t2 instanceof TypedefType
369+
)
359370
)
360371
}
361372

362373
/**
363374
* Check whether two types are equivalent, as defined by the `TypeEquivalenceSig` module.
364375
*
365-
* This only holds if the specified predicate `interestedIn` holds for the types, and always
366-
* holds if `t1` and `t2` are identical.
376+
* This only holds if the specified predicate `interestedIn` holds for the types, or
377+
* `interestedInNestedTypes` holds for the types, and holds if `t1` and `t2` are identical,
378+
* regardless of how `TypeEquivalenceSig` is defined.
367379
*/
368380
predicate equalTypes(Type t1, Type t2) {
369-
compares(pragma[only_bind_into](t1), pragma[only_bind_into](t2)) and
381+
interestedInNestedTypes(pragma[only_bind_into](t1), pragma[only_bind_into](t2)) and
370382
(
371383
t1 = t2
372384
or
373385
not t1 = t2 and
374386
if Config::overrideTypeComparison(t1, t2, _)
375387
then Config::overrideTypeComparison(t1, t2, true)
376-
else
377-
if t1 instanceof TypedefType and Config::resolveTypedefs()
378-
then equalTypes(t1.(TypedefType).getBaseType(), t2)
379-
else
380-
if t2 instanceof TypedefType and Config::resolveTypedefs()
381-
then equalTypes(t1, t2.(TypedefType).getBaseType())
382-
else (
383-
not t1 instanceof DerivedType and
384-
not t2 instanceof DerivedType and
385-
not t1 instanceof TypedefType and
386-
not t2 instanceof TypedefType and
387-
equalLeafRelation(t1, t2)
388-
or
389-
equalDerivedTypes(t1, t2)
390-
or
391-
equalTypedefTypes(t1, t2)
392-
or
393-
equalFunctionTypes(t1, t2)
394-
)
388+
else (
389+
equalLeafRelation(t1, t2)
390+
or
391+
equalDerivedTypes(t1, t2)
392+
or
393+
equalTypedefTypes(t1, t2)
394+
or
395+
equalFunctionTypes(t1, t2)
396+
or
397+
Config::resolveTypedefs() and
398+
(
399+
equalTypes(t1.(TypedefType).getBaseType(), t2)
400+
or
401+
equalTypes(t1, t2.(TypedefType).getBaseType())
402+
)
403+
)
395404
)
396405
}
397406

@@ -402,7 +411,7 @@ module TypeEquivalence<TypeEquivalenceSig Config, interestedInEquality/2 interes
402411
}
403412

404413
bindingset[t1, t2]
405-
private predicate equalLeafRelation(Type t1, Type t2) { Config::equalLeafTypes(t1, t2) }
414+
private predicate equalLeafRelation(LeafType t1, LeafType t2) { Config::equalLeafTypes(t1, t2) }
406415

407416
bindingset[t]
408417
private Type unspecify(SpecifiedType t) {
@@ -477,7 +486,7 @@ module FunctionDeclarationTypeEquivalence<
477486
{
478487
private predicate interestedInReturnTypes(Type a, Type b) {
479488
exists(FunctionDeclarationEntry aFun, FunctionDeclarationEntry bFun |
480-
interestedInFunctions(aFun, bFun) and
489+
interestedInFunctions(pragma[only_bind_into](aFun), pragma[only_bind_into](bFun)) and
481490
a = aFun.getType() and
482491
b = bFun.getType()
483492
)
@@ -529,3 +538,11 @@ private class FunctionType extends Type {
529538
result = this.(FunctionPointerIshType).getParameterType(i)
530539
}
531540
}
541+
542+
private class LeafType extends Type {
543+
LeafType() {
544+
not this instanceof DerivedType and
545+
not this instanceof FunctionType and
546+
not this instanceof FunctionType
547+
}
548+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.