Skip to content

Commit c85ccb2

Browse files
RasmusWLRasmusWL
committed
Python: Add call-graph compare meta-queries
Also changed the definition of a relevant call-target, so it's only what is in the actual source code, which is what we want in the future! (so what we're designing type-tracking to handle) I also changed terminology from `callee` to `target`. It felt more natural this way in my opinion.
1 parent a98554b commit c85ccb2

File tree

7 files changed

+211
-28
lines changed

7 files changed

+211
-28
lines changed

‎python/ql/src/meta/analysis-quality/CallGraphQuality.qll‎

Lines changed: 104 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,72 @@
11
/**
22
* Provides predicates for measuring the quality of the call graph, that is,
3-
* the number of calls that could be resolved to a callee.
3+
* the number of calls that could be resolved to a target.
44
*/
55

66
import python
77
import meta.MetaMetrics
88

9+
newtype TTarget =
10+
TFunction(Function func) or
11+
TClass(Class cls)
12+
13+
class Target extends TTarget {
14+
/** Gets a textual representation of this element. */
15+
abstract string toString();
16+
17+
/** Gets the location of this dataflow call. */
18+
abstract Location getLocation();
19+
20+
/** Whether this target is relevant. */
21+
predicate isRelevant() { exists(this.getLocation().getFile().getRelativePath()) }
22+
}
23+
24+
class TargetFunction extends Target, TFunction {
25+
Function func;
26+
27+
TargetFunction() { this = TFunction(func) }
28+
29+
override string toString() { result = func.toString() }
30+
31+
override Location getLocation() { result = func.getLocation() }
32+
33+
Function getFunction() { result = func }
34+
}
35+
36+
class TargetClass extends Target, TClass {
37+
Class cls;
38+
39+
TargetClass() { this = TClass(cls) }
40+
41+
override string toString() { result = cls.toString() }
42+
43+
override Location getLocation() { result = cls.getLocation() }
44+
45+
Class getClass() { result = cls }
46+
}
47+
948
/**
1049
* A call that is (possibly) relevant for analysis quality.
1150
* See `IgnoredFile` for details on what is excluded.
1251
*/
13-
class RelevantCall extends Call {
52+
class RelevantCall extends CallNode {
1453
RelevantCall() { not this.getLocation().getFile() instanceof IgnoredFile }
1554
}
1655

1756
/** Provides classes for call-graph resolution by using points-to. */
1857
module PointsToBasedCallGraph {
1958
/** A call that can be resolved by points-to. */
2059
class ResolvableCall extends RelevantCall {
21-
Value callee;
60+
Value targetValue;
2261

23-
ResolvableCall() { callee.getACall() = this.getAFlowNode() }
62+
ResolvableCall() { targetValue.getACall() = this }
2463

25-
/** Gets a resolved callee of this call. */
26-
Value getCallee() { result = callee }
64+
/** Gets a resolved target of this call. */
65+
Target getTarget() {
66+
result.(TargetFunction).getFunction() = targetValue.(CallableValue).getScope()
67+
or
68+
result.(TargetClass).getClass() = targetValue.(ClassValue).getScope()
69+
}
2770
}
2871

2972
/** A call that cannot be resolved by points-to. */
@@ -32,34 +75,68 @@ module PointsToBasedCallGraph {
3275
}
3376

3477
/**
35-
* A call that can be resolved by points-to, where the resolved callee is relevant.
36-
* Relevant callees include:
37-
* - builtins
38-
* - standard library
78+
* A call that can be resolved by points-to, where the resolved target is relevant.
79+
* Relevant targets include:
3980
* - source code of the project
4081
*/
41-
class ResolvableCallRelevantCallee extends ResolvableCall {
42-
ResolvableCallRelevantCallee() {
43-
callee.isBuiltin()
44-
or
45-
exists(File file |
46-
file = callee.(CallableValue).getScope().getLocation().getFile()
47-
or
48-
file = callee.(ClassValue).getScope().getLocation().getFile()
49-
|
50-
file.inStdlib()
51-
or
52-
// part of the source code of the project
53-
exists(file.getRelativePath())
82+
class ResolvableCallRelevantTarget extends ResolvableCall {
83+
ResolvableCallRelevantTarget() {
84+
exists(Target target | target = getTarget() |
85+
exists(target.getLocation().getFile().getRelativePath())
86+
)
87+
}
88+
}
89+
90+
/**
91+
* A call that can be resolved by points-to, where the resolved target is not considered relevant.
92+
* See `ResolvableCallRelevantTarget` for the definition of relevance.
93+
*/
94+
class ResolvableCallIrrelevantTarget extends ResolvableCall {
95+
ResolvableCallIrrelevantTarget() { not this instanceof ResolvableCallRelevantTarget }
96+
}
97+
}
98+
99+
/** Provides classes for call-graph resolution by using type-tracking. */
100+
module TypeTrackingBasedCallGraph {
101+
private import semmle.python.dataflow.new.internal.DataFlowDispatch as TT
102+
103+
/** A call that can be resolved by type-tracking. */
104+
class ResolvableCall extends RelevantCall {
105+
TT::DataFlowCallable dataflowTarget;
106+
107+
ResolvableCall() { dataflowTarget = TT::viableCallable(TT::TNormalCall(this)) }
108+
109+
/** Gets a resolved target of this call. */
110+
Target getTarget() {
111+
result.(TargetFunction).getFunction() = dataflowTarget.(TT::DataFlowFunction).getScope()
112+
// TODO: class calls
113+
// result.(TargetClass).getClass()
114+
}
115+
}
116+
117+
/** A call that cannot be resolved by type-tracking. */
118+
class UnresolvableCall extends RelevantCall {
119+
UnresolvableCall() { not this instanceof ResolvableCall }
120+
}
121+
122+
/**
123+
* A call that can be resolved by type-tracking, where the resolved callee is relevant.
124+
* Relevant targets include:
125+
* - source code of the project
126+
*/
127+
class ResolvableCallRelevantTarget extends ResolvableCall {
128+
ResolvableCallRelevantTarget() {
129+
exists(Target target | target = getTarget() |
130+
exists(target.getLocation().getFile().getRelativePath())
54131
)
55132
}
56133
}
57134

58135
/**
59-
* A call that can be resolved by points-to, where the resolved callee is not considered relevant.
60-
* See `ResolvableCallRelevantCallee` for the definition of relevance.
136+
* A call that can be resolved by type-tracking, where the resolved target is not considered relevant.
137+
* See `ResolvableCallRelevantTarget` for the definition of relevance.
61138
*/
62-
class ResolvableCallIrrelevantCallee extends ResolvableCall {
63-
ResolvableCallIrrelevantCallee() { not this instanceof ResolvableCallRelevantCallee }
139+
class ResolvableCallIrrelevantTarget extends ResolvableCall {
140+
ResolvableCallIrrelevantTarget() { not this instanceof ResolvableCallRelevantTarget }
64141
}
65142
}

‎python/ql/src/meta/analysis-quality/PointsToResolvableCallsRelevantTarget.ql‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,4 @@
1111
import python
1212
import CallGraphQuality
1313

14-
select projectRoot(), count(PointsToBasedCallGraph::ResolvableCallRelevantCallee call)
14+
select projectRoot(), count(PointsToBasedCallGraph::ResolvableCallRelevantTarget call)

‎python/ql/src/meta/analysis-quality/TTCallGraph.ql‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
/**
2+
* @name New call graph edge from using type-tracking instead of points-to
3+
* @kind problem
4+
* @problem.severity recommendation
5+
* @id py/meta/call-graph-new
6+
* @tags meta
7+
* @precision very-low
8+
*/
9+
10+
import python
11+
import CallGraphQuality
12+
13+
from CallNode call, Target target
14+
where
15+
target.isRelevant() and
16+
call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
17+
select call, "$@ to $@", call, "Call", target, target.toString()

‎python/ql/src/meta/analysis-quality/TTCallGraphMissing.ql‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* @name Missing call graph edge from using type-tracking instead of points-to
3+
* @kind problem
4+
* @problem.severity recommendation
5+
* @id py/meta/call-graph-missing
6+
* @tags meta
7+
* @precision very-low
8+
*/
9+
10+
import python
11+
import CallGraphQuality
12+
13+
from CallNode call, Target target
14+
where
15+
target.isRelevant() and
16+
call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
17+
not call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
18+
select call, "MISSING: $@ to $@", call, "Call", target, target.toString()

‎python/ql/src/meta/analysis-quality/TTCallGraphNew.ql‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* @name New call graph edge from using type-tracking instead of points-to
3+
* @kind problem
4+
* @problem.severity recommendation
5+
* @id py/meta/call-graph-new
6+
* @tags meta
7+
* @precision very-low
8+
*/
9+
10+
import python
11+
import CallGraphQuality
12+
13+
from CallNode call, Target target
14+
where
15+
target.isRelevant() and
16+
not call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
17+
call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
18+
select call, "NEW: $@ to $@", call, "Call", target, target.toString()

‎python/ql/src/meta/analysis-quality/TTCallGraphOverview.ql‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/**
2+
* @name Call graph edge overview from using type-tracking instead of points-to
3+
* @id py/meta/call-graph-overview
4+
* @precision very-low
5+
*/
6+
7+
import python
8+
import CallGraphQuality
9+
10+
from string tag, int c
11+
where
12+
tag = "SHARED" and
13+
c =
14+
count(CallNode call, Target target |
15+
target.isRelevant() and
16+
call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
17+
call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
18+
)
19+
or
20+
tag = "NEW" and
21+
c =
22+
count(CallNode call, Target target |
23+
target.isRelevant() and
24+
not call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
25+
call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
26+
)
27+
or
28+
tag = "MISSING" and
29+
c =
30+
count(CallNode call, Target target |
31+
target.isRelevant() and
32+
call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
33+
not call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
34+
)
35+
select tag, c

‎python/ql/src/meta/analysis-quality/TTCallGraphShared.ql‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* @name Shared call graph edge from using type-tracking instead of points-to
3+
* @kind problem
4+
* @problem.severity recommendation
5+
* @id py/meta/call-graph-shared
6+
* @tags meta
7+
* @precision very-low
8+
*/
9+
10+
import python
11+
import CallGraphQuality
12+
13+
from CallNode call, Target target
14+
where
15+
target.isRelevant() and
16+
call.(PointsToBasedCallGraph::ResolvableCall).getTarget() = target and
17+
call.(TypeTrackingBasedCallGraph::ResolvableCall).getTarget() = target
18+
select call, "SHARED: $@ to $@", call, "Call", target, target.toString()

0 commit comments

Comments
 (0)