Skip to content
Navigation Menu
{{ message }}
forked from github/codeql
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathVariableCapture.qll
More file actions
1054 lines (930 loc) · 36.8 KB
/
Copy pathVariableCapture.qll
File metadata and controls
1054 lines (930 loc) · 36.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/**
* Provides a module for synthesizing data-flow nodes and related step relations
* for supporting flow through captured variables.
*/
private import codeql.util.Boolean
private import codeql.util.Unit
private import codeql.util.Location
private import codeql.ssa.Ssa as Ssa
signature module InputSig<LocationSig Location> {
/**
* A basic block, that is, a maximal straight-line sequence of control flow nodes
* without branches or joins.
*/
class BasicBlock {
/** Gets a textual representation of this basic block. */
string toString();
/** Gets the `i`th node in this basic block. */
ControlFlowNode getNode(int i);
/** Gets the length of this basic block. */
int length();
/** Gets the enclosing callable. */
Callable getEnclosingCallable();
/** Gets the location of this basic block. */
Location getLocation();
}
/** A control flow node. */
class ControlFlowNode {
/** Gets a textual representation of this control flow node. */
string toString();
/** Gets the location of this control flow node. */
Location getLocation();
}
/**
* Gets the basic block that immediately dominates basic block `bb`, if any.
*
* That is, all paths reaching `bb` from some entry point basic block must go
* through the result.
*
* Example:
*
* ```csharp
* int M(string s) {
* if (s == null)
* throw new ArgumentNullException(nameof(s));
* return s.Length;
* }
* ```
*
* The basic block starting on line 2 is an immediate dominator of
* the basic block on line 4 (all paths from the entry point of `M`
* to `return s.Length;` must go through the null check.
*/
BasicBlock getImmediateBasicBlockDominator(BasicBlock bb);
/** Gets an immediate successor of basic block `bb`, if any. */
BasicBlock getABasicBlockSuccessor(BasicBlock bb);
/** Holds if `bb` is a control-flow entry point. */
default predicate entryBlock(BasicBlock bb) { not exists(getImmediateBasicBlockDominator(bb)) }
/** A variable that is captured in a closure. */
class CapturedVariable {
/** Gets a textual representation of this variable. */
string toString();
/** Gets the callable that defines this variable. */
Callable getCallable();
/** Gets the location of this variable. */
Location getLocation();
}
/** A parameter that is captured in a closure. */
class CapturedParameter extends CapturedVariable;
/**
* An expression with a value. That is, we expect these expressions to be
* represented in the data flow graph.
*/
class Expr {
/** Gets a textual representation of this expression. */
string toString();
/** Gets the location of this expression. */
Location getLocation();
/** Holds if the `i`th node of basic block `bb` evaluates this expression. */
predicate hasCfgNode(BasicBlock bb, int i);
}
/** A write to a captured variable. */
class VariableWrite {
/** Gets the variable that is the target of this write. */
CapturedVariable getVariable();
/** Gets the location of this write. */
Location getLocation();
/** Holds if the `i`th node of basic block `bb` evaluates this expression. */
predicate hasCfgNode(BasicBlock bb, int i);
}
/** A read of a captured variable. */
class VariableRead extends Expr {
/** Gets the variable that this expression reads. */
CapturedVariable getVariable();
}
/**
* An expression constructing a closure that may capture one or more
* variables. This can for example be a lambda or a constructor call of a
* locally defined object.
*/
class ClosureExpr extends Expr {
/**
* Holds if `body` is the callable body of this closure. A lambda expression
* only has one body, but in general a locally defined object may have
* multiple such methods and constructors.
*/
predicate hasBody(Callable body);
/**
* Holds if `f` is an expression that may hold the value of the closure and
* may occur in a position where the value escapes or where the closure may
* be invoked.
*
* For example, if a lambda is assigned to a variable, then references to
* that variable in return or argument positions should be included.
*/
predicate hasAliasedAccess(Expr f);
}
class Callable {
/** Gets a textual representation of this callable. */
string toString();
/** Gets the location of this callable. */
Location getLocation();
/** Holds if this callable is a constructor. */
predicate isConstructor();
}
}
signature module OutputSig<LocationSig Location, InputSig<Location> I> {
/**
* A data flow node that we need to reference in the step relations for
* captured variables.
*
* Note that only the `SynthesizedCaptureNode` subclass is expected to be
* added as additional nodes in `DataFlow::Node`. The other subclasses are
* expected to already be present and are included here in order to reference
* them in the step relations.
*/
class ClosureNode;
/**
* A synthesized data flow node representing the storage of a captured
* variable.
*/
class SynthesizedCaptureNode extends ClosureNode {
/** Gets a textual representation of this node. */
string toString();
/** Gets the location of this node. */
Location getLocation();
/** Gets the enclosing callable. */
I::Callable getEnclosingCallable();
/** Holds if this node is a synthesized access of `v`. */
predicate isVariableAccess(I::CapturedVariable v);
/** Holds if this node is a synthesized instance access. */
predicate isInstanceAccess();
}
/** A data flow node for an expression. */
class ExprNode extends ClosureNode {
/** Gets the expression corresponding to this node. */
I::Expr getExpr();
}
/** A data flow node for the `PostUpdateNode` of an expression. */
class ExprPostUpdateNode extends ClosureNode {
/** Gets the expression corresponding to this node. */
I::Expr getExpr();
}
/** A data flow node for a parameter. */
class ParameterNode extends ClosureNode {
/** Gets the parameter corresponding to this node. */
I::CapturedParameter getParameter();
}
/** A data flow node for an instance parameter. */
class ThisParameterNode extends ClosureNode {
/** Gets the callable this instance parameter belongs to. */
I::Callable getCallable();
}
/** A data flow node for the instance parameter argument of a constructor call. */
class MallocNode extends ClosureNode {
/** Gets the closure construction that is the post-update of this node. */
I::ClosureExpr getClosureExpr();
}
/**
* A node representing the incoming value about to be written at the given assignment.
*
* The captured-variable library will generate flows out of this node, and assume that other
* parts of the language implementation produce the relevant data flows into this node.
*
* For ordinary assignments, this could be mapped to the right-hand side of the assignment.
*
* For more general cases, where an lvalue has no direct corresponding rvalue, this can be mapped
* to a data-flow node that wraps the lvalue, with language-specific incoming data flows.
*/
class VariableWriteSourceNode extends ClosureNode {
/** Gets the variable write for which this node is the incoming value being written to the variable. */
I::VariableWrite getVariableWrite();
}
/** Holds if `post` is a `PostUpdateNode` for `pre`. */
predicate capturePostUpdateNode(SynthesizedCaptureNode post, SynthesizedCaptureNode pre);
/** Holds if there is a local flow step from `node1` to `node2`. */
predicate localFlowStep(ClosureNode node1, ClosureNode node2);
/** Holds if there is a store step from `node1` to `node2`. */
predicate storeStep(ClosureNode node1, I::CapturedVariable v, ClosureNode node2);
/** Holds if there is a read step from `node1` to `node2`. */
predicate readStep(ClosureNode node1, I::CapturedVariable v, ClosureNode node2);
/** Holds if this-to-this summaries are expected for `c`. */
predicate heuristicAllowInstanceParameterReturnInSelf(I::Callable c);
/** Holds if captured variable `v` is cleared at `node`. */
predicate clearsContent(ClosureNode node, I::CapturedVariable v);
}
/**
* Constructs the type `ClosureNode` and associated step relations, which are
* intended to be included in the data-flow node and step relations.
*/
module Flow<LocationSig Location, InputSig<Location> Input> implements OutputSig<Location, Input> {
private import Input
additional module ConsistencyChecks {
final private class FinalExpr = Expr;
private class RelevantExpr extends FinalExpr {
RelevantExpr() {
this instanceof VariableRead or
this instanceof ClosureExpr or
any(ClosureExpr ce).hasAliasedAccess(this)
}
}
final private class FinalBasicBlock = BasicBlock;
private class RelevantBasicBlock extends FinalBasicBlock {
RelevantBasicBlock() {
exists(RelevantExpr e | e.hasCfgNode(this, _))
or
exists(VariableWrite vw | vw.hasCfgNode(this, _))
}
}
final private class FinalCallable = Callable;
private class RelevantCallable extends FinalCallable {
RelevantCallable() {
exists(RelevantBasicBlock bb | bb.getEnclosingCallable() = this)
or
exists(CapturedVariable v | v.getCallable() = this)
or
exists(ClosureExpr ce | ce.hasBody(this))
}
}
query predicate uniqueToString(string msg, int n) {
exists(string elem |
n = strictcount(RelevantBasicBlock bb | not exists(bb.toString())) and
elem = "BasicBlock"
or
n = strictcount(CapturedVariable v | not exists(v.toString())) and elem = "CapturedVariable"
or
n = strictcount(RelevantExpr e | not exists(e.toString())) and elem = "Expr"
or
n = strictcount(RelevantCallable c | not exists(c.toString())) and
elem = "Callable"
|
msg = n + " " + elem + "(s) are missing toString"
)
or
exists(string elem |
n = strictcount(RelevantBasicBlock bb | 2 <= strictcount(bb.toString())) and
elem = "BasicBlock"
or
n = strictcount(CapturedVariable v | 2 <= strictcount(v.toString())) and
elem = "CapturedVariable"
or
n = strictcount(RelevantExpr e | 2 <= strictcount(e.toString())) and
elem = "Expr"
or
n = strictcount(RelevantCallable c | 2 <= strictcount(c.toString())) and
elem = "Callable"
|
msg = n + " " + elem + "(s) have multiple toStrings"
)
}
query predicate uniqueEnclosingCallable(RelevantBasicBlock bb, string msg) {
msg = "BasicBlock has no enclosing callable" and not exists(bb.getEnclosingCallable())
or
msg = "BasicBlock has multiple enclosing callables" and
2 <= strictcount(bb.getEnclosingCallable())
}
query predicate uniqueDominator(RelevantBasicBlock bb, string msg) {
msg = "BasicBlock has multiple immediate dominators" and
2 <= strictcount(getImmediateBasicBlockDominator(bb))
}
query predicate localDominator(RelevantBasicBlock bb, string msg) {
msg = "BasicBlock has non-local dominator" and
bb.getEnclosingCallable() != getImmediateBasicBlockDominator(bb).getEnclosingCallable()
}
query predicate localSuccessor(RelevantBasicBlock bb, string msg) {
msg = "BasicBlock has non-local successor" and
bb.getEnclosingCallable() != getABasicBlockSuccessor(bb).getEnclosingCallable()
}
query predicate uniqueDefiningScope(CapturedVariable v, string msg) {
msg = "CapturedVariable has no defining callable" and not exists(v.getCallable())
or
msg = "CapturedVariable has multiple defining callables" and 2 <= strictcount(v.getCallable())
}
query predicate variableIsCaptured(CapturedVariable v, string msg) {
msg = "CapturedVariable is not captured" and
not captureAccess(v, _)
}
query predicate uniqueLocation(RelevantExpr e, string msg) {
msg = "Expr has no location" and not exists(e.getLocation())
or
msg = "Expr has multiple locations" and 2 <= strictcount(e.getLocation())
}
query predicate uniqueCfgNode(RelevantExpr e, string msg) {
msg = "Expr has no cfg node" and not e.hasCfgNode(_, _)
or
msg = "Expr has multiple cfg nodes" and
2 <= strictcount(BasicBlock bb, int i | e.hasCfgNode(bb, i))
}
private predicate uniqueWriteTarget(VariableWrite vw, string msg) {
msg = "VariableWrite has no target variable" and not exists(vw.getVariable())
or
msg = "VariableWrite has multiple target variables" and 2 <= strictcount(vw.getVariable())
}
query predicate uniqueWriteTarget(string msg) { uniqueWriteTarget(_, msg) }
private predicate uniqueWriteCfgNode(VariableWrite vw, string msg) {
msg = "VariableWrite has no cfg node" and not vw.hasCfgNode(_, _)
or
msg = "VariableWrite has multiple cfg nodes" and
2 <= strictcount(BasicBlock bb, int i | vw.hasCfgNode(bb, i))
}
query predicate uniqueWriteCfgNode(string msg) { uniqueWriteCfgNode(_, msg) }
query predicate uniqueReadVariable(VariableRead vr, string msg) {
msg = "VariableRead has no source variable" and not exists(vr.getVariable())
or
msg = "VariableRead has multiple source variables" and 2 <= strictcount(vr.getVariable())
}
query predicate closureMustHaveBody(ClosureExpr ce, string msg) {
msg = "ClosureExpr has no body" and not ce.hasBody(_)
}
query predicate closureAliasMustBeInSameScope(ClosureExpr ce, Expr access, string msg) {
exists(BasicBlock bb1, BasicBlock bb2 |
ce.hasAliasedAccess(access) and
ce.hasCfgNode(bb1, _) and
access.hasCfgNode(bb2, _) and
not bb1.getEnclosingCallable() = callableGetEnclosingCallable*(bb2.getEnclosingCallable()) and
msg =
"ClosureExpr has an alias outside the scope of its enclosing callable - these are ignored"
)
}
private predicate astClosureParent(Callable closure, Callable parent) {
exists(ClosureExpr ce, BasicBlock bb |
ce.hasBody(closure) and ce.hasCfgNode(bb, _) and parent = bb.getEnclosingCallable()
)
}
query predicate variableAccessAstNesting(CapturedVariable v, Callable c, string msg) {
exists(BasicBlock bb, Callable parent |
captureRead(v, bb, _, false, _) or captureWrite(v, bb, _, false, _)
|
bb.getEnclosingCallable() = c and
v.getCallable() = parent and
not astClosureParent+(c, parent) and
msg = "CapturedVariable access is not nested in the defining callable"
)
}
query predicate uniqueCallableLocation(RelevantCallable c, string msg) {
msg = "Callable has no location" and not exists(c.getLocation())
or
msg = "Callable has multiple locations" and 2 <= strictcount(c.getLocation())
}
query predicate consistencyOverview(string msg, int n) {
uniqueToString(msg, n) or
n = strictcount(BasicBlock bb | uniqueEnclosingCallable(bb, msg)) or
n = strictcount(BasicBlock bb | uniqueDominator(bb, msg)) or
n = strictcount(BasicBlock bb | localDominator(bb, msg)) or
n = strictcount(BasicBlock bb | localSuccessor(bb, msg)) or
n = strictcount(CapturedVariable v | uniqueDefiningScope(v, msg)) or
n = strictcount(CapturedVariable v | variableIsCaptured(v, msg)) or
n = strictcount(Expr e | uniqueLocation(e, msg)) or
n = strictcount(Expr e | uniqueCfgNode(e, msg)) or
n = strictcount(VariableWrite vw | uniqueWriteTarget(vw, msg)) or
n = strictcount(VariableWrite vw | uniqueWriteCfgNode(vw, msg)) or
n = strictcount(VariableRead vr | uniqueReadVariable(vr, msg)) or
n = strictcount(ClosureExpr ce | closureMustHaveBody(ce, msg)) or
n = strictcount(ClosureExpr ce, Expr access | closureAliasMustBeInSameScope(ce, access, msg)) or
n = strictcount(CapturedVariable v, Callable c | variableAccessAstNesting(v, c, msg)) or
n = strictcount(Callable c | uniqueCallableLocation(c, msg))
}
}
/*
* Flow through captured variables is handled by making each captured variable
* a field on the closures that capture them.
*
* For each closure creation we add a store step from the captured variable to
* the closure, and inside the closures we access the captured variables with
* a `this.` qualifier. This allows capture flow into closures.
*
* It also means that we get several aliased versions of a captured variable
* so proper care must be taken to be able to observe side-effects or flow out
* of closures. E.g. if two closures `l1` and `l2` capture `x` then we'll have
* three names, `x`, `l1.x`, and `l2.x`, plus any potential aliasing of the
* closures.
*
* To handle this, we select a primary name for a captured variable in each of
* its scopes, keep that name updated, and update the other names from the
* primary name.
*
* In the defining scope of a captured variable, we use the local variable
* itself as the primary storage location, and in the capturing scopes we use
* the synthesized field. For each relevant reference to a closure object we
* then update its field from the primary storage location, and we read the
* field back from the post-update of the closure object reference and back
* into the primary storage location.
*
* If we include references to a closure object that may lead to a call as
* relevant, then this means that we'll be able to observe the side-effects of
* such calls in the primary storage location.
*
* Details:
* For a reference to a closure `f` that captures `x` we synthesize a read of
* `x` at the same control-flow node. We then add a store step from `x` to `f`
* and a read step from `postupdate(f)` to `postupdate(x)`.
* ```
* SsaRead(x) --store[x]--> f
* postupdate(f) --read[x]--> postupdate(SsaRead(x))
* ```
* In a closure scope with a nested closure `g` that also captures `x` the
* steps instead look like this:
* ```
* SsaRead(this) --read[x]--> this.x --store[x]--> g
* postupdate(g) --read[x]--> postupdate(this.x)
* ```
* The final store from `postupdate(this.x)` to `postupdate(this)` is
* introduced automatically as a reverse read by the data flow library.
*/
/**
* Holds if `vr` is a read of `v` in the `i`th node of `bb`.
* `topScope` is true if the read is in the defining callable of `v`.
*/
private predicate captureRead(
CapturedVariable v, BasicBlock bb, int i, boolean topScope, VariableRead vr
) {
vr.getVariable() = v and
vr.hasCfgNode(bb, i) and
if v.getCallable() != bb.getEnclosingCallable() then topScope = false else topScope = true
}
/**
* Holds if `vw` is a write of `v` in the `i`th node of `bb`.
* `topScope` is true if the write is in the defining callable of `v`.
*/
private predicate captureWrite(
CapturedVariable v, BasicBlock bb, int i, boolean topScope, VariableWrite vw
) {
vw.getVariable() = v and
vw.hasCfgNode(bb, i) and
if v.getCallable() != bb.getEnclosingCallable() then topScope = false else topScope = true
}
/** Gets the enclosing callable of `ce`. */
private Callable closureExprGetEnclosingCallable(ClosureExpr ce) {
exists(BasicBlock bb | ce.hasCfgNode(bb, _) and result = bb.getEnclosingCallable())
}
/** Gets the enclosing callable of `inner`. */
pragma[nomagic]
private Callable callableGetEnclosingCallable(Callable inner) {
exists(ClosureExpr closure |
closure.hasBody(inner) and
result = closureExprGetEnclosingCallable(closure)
)
}
/**
* Gets a callable that contains `ce`, or a reference to `ce` into which `ce` could be inlined without
* bringing any variables out of scope.
*
* If `ce` was to be inlined into that reference, the resulting callable
* would become the enclosing callable, and thus capture the same variables as `ce`.
* In some sense, we model captured aliases as if this inlining has happened.
*/
private Callable closureExprGetAReferencingCallable(ClosureExpr ce) {
result = closureExprGetEnclosingCallable(ce)
or
exists(Expr expr, BasicBlock bb |
ce.hasAliasedAccess(expr) and
expr.hasCfgNode(bb, _) and
result = bb.getEnclosingCallable() and
// The reference to `ce` is allowed to occur in a more deeply nested context
closureExprGetEnclosingCallable(ce) = callableGetEnclosingCallable*(result)
)
}
/**
* Holds if `v` is available in `c` through capture. This can either be due to
* an explicit variable reference or through the construction of a closure
* that has a nested capture.
*/
private predicate captureAccess(CapturedVariable v, Callable c) {
exists(BasicBlock bb | captureRead(v, bb, _, _, _) or captureWrite(v, bb, _, _, _) |
c = bb.getEnclosingCallable() and
c != v.getCallable()
)
or
exists(ClosureExpr ce |
c = closureExprGetAReferencingCallable(ce) and
closureCaptures(ce, v) and
c != v.getCallable()
)
}
/** Holds if the closure defined by `ce` captures `v`. */
private predicate closureCaptures(ClosureExpr ce, CapturedVariable v) {
exists(Callable c | ce.hasBody(c) and captureAccess(v, c))
}
predicate heuristicAllowInstanceParameterReturnInSelf(Callable c) {
// If multiple variables are captured, then we should allow flow from one to
// another, which entails a this-to-this summary.
2 <= strictcount(CapturedVariable v | captureAccess(v, c))
or
// Constructors that capture a variable may assign it to a field, which also
// entails a this-to-this summary. If there are multiple constructors, then
// they might call each other, so if one constructor captures a variable we
// allow this-to-this summaries for all of them.
exists(ClosureExpr ce | ce.hasBody(c) and c.isConstructor() and hasConstructorCapture(ce, _))
}
/** Holds if a constructor, if any, for the closure defined by `ce` captures `v`. */
private predicate hasConstructorCapture(ClosureExpr ce, CapturedVariable v) {
exists(Callable c | ce.hasBody(c) and c.isConstructor() and captureAccess(v, c))
}
/**
* Holds if `access` is a reference to `ce` evaluated in the `i`th node of `bb`.
* The reference is restricted to be nested within the same callable as `ce` as a
* precaution, even though this is expected to hold for all the given aliased
* accesses.
*/
private predicate localOrNestedClosureAccess(ClosureExpr ce, Expr access, BasicBlock bb, int i) {
ce.hasAliasedAccess(access) and
access.hasCfgNode(bb, i) and
pragma[only_bind_out](bb.getEnclosingCallable()) =
pragma[only_bind_out](closureExprGetAReferencingCallable(ce))
}
/**
* Holds if we need an additional read of `v` in the `i`th node of `bb` in
* order to synchronize the value stored on `closure`.
* `topScope` is true if the read is in the defining callable of `v`.
*
* Side-effects of potentially calling `closure` at this point will be
* observed in a similarly synthesized post-update node for this read of `v`.
*/
private predicate synthRead(
CapturedVariable v, BasicBlock bb, int i, boolean topScope, Expr closure, boolean alias
) {
exists(ClosureExpr ce | closureCaptures(ce, v) |
ce.hasCfgNode(bb, i) and ce = closure and alias = false
or
localOrNestedClosureAccess(ce, closure, bb, i) and alias = true
) and
if v.getCallable() != bb.getEnclosingCallable() then topScope = false else topScope = true
}
private predicate synthRead(
CapturedVariable v, BasicBlock bb, int i, boolean topScope, Expr closure
) {
synthRead(v, bb, i, topScope, closure, _)
}
/**
* Holds if there is an access of a captured variable inside a closure in the
* `i`th node of `bb`, such that we need to synthesize a `this.` qualifier.
*/
private predicate synthThisQualifier(BasicBlock bb, int i) {
synthRead(_, bb, i, false, _) or
captureRead(_, bb, i, false, _) or
captureWrite(_, bb, i, false, _)
}
private newtype TCaptureContainer =
TVariable(CapturedVariable v) or
TThis(Callable c) { captureAccess(_, c) }
/**
* A storage location for a captured variable in a specific callable. This is
* either the variable itself (in its defining scope) or an instance variable
* `this` (in a capturing scope).
*/
private class CaptureContainer extends TCaptureContainer {
string toString() {
exists(CapturedVariable v | this = TVariable(v) and result = v.toString())
or
result = "this" and this = TThis(_)
}
Location getLocation() {
exists(CapturedVariable v | this = TVariable(v) and result = v.getLocation())
or
exists(Callable c | this = TThis(c) and result = c.getLocation())
}
}
/** Holds if `cc` needs a definition at the entry of its callable scope. */
private predicate entryDef(CaptureContainer cc, BasicBlock bb, int i) {
exists(Callable c |
entryBlock(bb) and
pragma[only_bind_out](bb.getEnclosingCallable()) = c and
i =
min(int j |
j = 1 or
captureRead(_, bb, j, _, _) or
captureWrite(_, bb, j, _, _) or
synthRead(_, bb, j, _, _)
) - 1
|
cc = TThis(c)
or
exists(CapturedParameter p | cc = TVariable(p) and p.getCallable() = c)
)
}
private module CaptureSsaInput implements Ssa::InputSig<Location> {
final class BasicBlock = Input::BasicBlock;
final class ControlFlowNode = Input::ControlFlowNode;
BasicBlock getImmediateBasicBlockDominator(BasicBlock bb) {
result = Input::getImmediateBasicBlockDominator(bb)
}
BasicBlock getABasicBlockSuccessor(BasicBlock bb) {
result = Input::getABasicBlockSuccessor(bb)
}
class SourceVariable = CaptureContainer;
predicate variableWrite(BasicBlock bb, int i, SourceVariable cc, boolean certain) {
(
exists(CapturedVariable v | cc = TVariable(v) and captureWrite(v, bb, i, true, _))
or
entryDef(cc, bb, i)
) and
certain = true
}
predicate variableRead(BasicBlock bb, int i, SourceVariable cc, boolean certain) {
(
synthThisQualifier(bb, i) and cc = TThis(bb.getEnclosingCallable())
or
exists(CapturedVariable v | cc = TVariable(v) |
captureRead(v, bb, i, true, _) or synthRead(v, bb, i, true, _)
)
) and
certain = true
}
}
private module CaptureSsa = Ssa::Make<Location, CaptureSsaInput>;
private newtype TClosureNode =
TSynthRead(CapturedVariable v, BasicBlock bb, int i, Boolean isPost) {
synthRead(v, bb, i, _, _)
} or
TSynthThisQualifier(BasicBlock bb, int i, Boolean isPost) { synthThisQualifier(bb, i) } or
TSynthPhi(CaptureSsa::DefinitionExt phi) {
phi instanceof CaptureSsa::PhiNode or phi instanceof CaptureSsa::PhiReadNode
} or
TExprNode(Expr expr, Boolean isPost) {
expr instanceof VariableRead
or
synthRead(_, _, _, _, expr)
} or
TParamNode(CapturedParameter p) or
TThisParamNode(Callable c) { captureAccess(_, c) } or
TMallocNode(ClosureExpr ce) { hasConstructorCapture(ce, _) } or
TVariableWriteSourceNode(VariableWrite write)
class ClosureNode extends TClosureNode {
/** Gets a textual representation of this node. */
string toString() {
exists(CapturedVariable v | this = TSynthRead(v, _, _, _) and result = v.toString())
or
result = "this" and this = TSynthThisQualifier(_, _, _)
or
exists(CaptureSsa::DefinitionExt phi, CaptureContainer cc |
this = TSynthPhi(phi) and
phi.definesAt(cc, _, _, _) and
result = "phi(" + cc.toString() + ")"
)
or
exists(Expr expr, boolean isPost | this = TExprNode(expr, isPost) |
isPost = false and result = expr.toString()
or
isPost = true and result = expr.toString() + " [postupdate]"
)
or
exists(CapturedParameter p | this = TParamNode(p) and result = p.toString())
or
result = "this" and this = TThisParamNode(_)
or
result = "malloc" and this = TMallocNode(_)
or
exists(VariableWrite write |
this = TVariableWriteSourceNode(write) and
result = "Source of write to " + write.getVariable().toString()
)
}
/** Gets the location of this node. */
Location getLocation() {
exists(CapturedVariable v, BasicBlock bb, int i, Expr closure |
this = TSynthRead(v, bb, i, _) and
synthRead(v, bb, i, _, closure) and
result = closure.getLocation()
)
or
exists(BasicBlock bb, int i | this = TSynthThisQualifier(bb, i, _) |
synthRead(_, bb, i, false, any(Expr closure | result = closure.getLocation())) or
captureRead(_, bb, i, false, any(VariableRead vr | result = vr.getLocation())) or
captureWrite(_, bb, i, false, any(VariableWrite vw | result = vw.getLocation()))
)
or
exists(CaptureSsa::DefinitionExt phi, BasicBlock bb |
this = TSynthPhi(phi) and phi.definesAt(_, bb, _, _) and result = bb.getLocation()
)
or
exists(Expr expr | this = TExprNode(expr, _) and result = expr.getLocation())
or
exists(CapturedParameter p | this = TParamNode(p) and result = p.getCallable().getLocation())
or
exists(Callable c | this = TThisParamNode(c) and result = c.getLocation())
or
exists(ClosureExpr ce | this = TMallocNode(ce) and result = ce.getLocation())
or
exists(VariableWrite write |
this = TVariableWriteSourceNode(write) and result = write.getLocation()
)
}
}
private class TSynthesizedCaptureNode = TSynthRead or TSynthThisQualifier or TSynthPhi;
class SynthesizedCaptureNode extends ClosureNode, TSynthesizedCaptureNode {
BasicBlock getBasicBlock() {
this = TSynthRead(_, result, _, _)
or
this = TSynthThisQualifier(result, _, _)
or
exists(CaptureSsa::DefinitionExt phi |
this = TSynthPhi(phi) and phi.definesAt(_, result, _, _)
)
}
Callable getEnclosingCallable() { result = this.getBasicBlock().getEnclosingCallable() }
predicate isVariableAccess(CapturedVariable v) {
this = TSynthRead(v, _, _, _)
or
exists(CaptureSsa::DefinitionExt phi |
this = TSynthPhi(phi) and phi.definesAt(TVariable(v), _, _, _)
)
}
predicate isInstanceAccess() {
this instanceof TSynthThisQualifier
or
exists(CaptureSsa::DefinitionExt phi |
this = TSynthPhi(phi) and phi.definesAt(TThis(_), _, _, _)
)
}
}
class ExprNode extends ClosureNode, TExprNode {
ExprNode() { this = TExprNode(_, false) }
Expr getExpr() { this = TExprNode(result, _) }
}
class ExprPostUpdateNode extends ClosureNode, TExprNode {
ExprPostUpdateNode() { this = TExprNode(_, true) }
Expr getExpr() { this = TExprNode(result, _) }
}
class ParameterNode extends ClosureNode, TParamNode {
CapturedParameter getParameter() { this = TParamNode(result) }
}
class ThisParameterNode extends ClosureNode, TThisParamNode {
Callable getCallable() { this = TThisParamNode(result) }
}
class MallocNode extends ClosureNode, TMallocNode {
ClosureExpr getClosureExpr() { this = TMallocNode(result) }
}
class VariableWriteSourceNode extends ClosureNode, TVariableWriteSourceNode {
VariableWrite getVariableWrite() { this = TVariableWriteSourceNode(result) }
}
predicate capturePostUpdateNode(SynthesizedCaptureNode post, SynthesizedCaptureNode pre) {
exists(CapturedVariable v, BasicBlock bb, int i |
pre = TSynthRead(v, bb, i, false) and post = TSynthRead(v, bb, i, true)
)
or
exists(BasicBlock bb, int i |
pre = TSynthThisQualifier(bb, i, false) and post = TSynthThisQualifier(bb, i, true)
)
}
private predicate step(CaptureContainer cc, BasicBlock bb1, int i1, BasicBlock bb2, int i2) {
CaptureSsa::adjacentDefReadExt(_, cc, bb1, i1, bb2, i2)
}
private predicate stepToPhi(CaptureContainer cc, BasicBlock bb, int i, TSynthPhi phi) {
exists(CaptureSsa::DefinitionExt next |
CaptureSsa::lastRefRedefExt(_, cc, bb, i, next) and
phi = TSynthPhi(next)
)
}
private predicate ssaAccessAt(
ClosureNode n, CaptureContainer cc, boolean isPost, BasicBlock bb, int i
) {
exists(CapturedVariable v |
synthRead(v, bb, i, true, _) and
n = TSynthRead(v, bb, i, isPost) and
cc = TVariable(v)
)
or
n = TSynthThisQualifier(bb, i, isPost) and cc = TThis(bb.getEnclosingCallable())
or
exists(CaptureSsa::DefinitionExt phi |
n = TSynthPhi(phi) and phi.definesAt(cc, bb, i, _) and isPost = false
)
or
exists(VariableRead vr, CapturedVariable v |
captureRead(v, bb, i, true, vr) and
n = TExprNode(vr, isPost) and
cc = TVariable(v)
)
or
exists(VariableWrite vw, CapturedVariable v |
captureWrite(v, bb, i, true, vw) and
n = TVariableWriteSourceNode(vw) and
isPost = false and
cc = TVariable(v)
)
or
exists(CapturedParameter p |
entryDef(cc, bb, i) and
cc = TVariable(p) and
n = TParamNode(p) and
isPost = false
)
or
exists(Callable c |
entryDef(cc, bb, i) and
cc = TThis(c) and
n = TThisParamNode(c) and
isPost = false
)
}
predicate localFlowStep(ClosureNode node1, ClosureNode node2) {
exists(CaptureContainer cc, BasicBlock bb1, int i1, BasicBlock bb2, int i2 |
step(cc, bb1, i1, bb2, i2) and
ssaAccessAt(node1, pragma[only_bind_into](cc), _, bb1, i1) and
ssaAccessAt(node2, pragma[only_bind_into](cc), false, bb2, i2)
)
or
exists(CaptureContainer cc, BasicBlock bb, int i |
stepToPhi(cc, bb, i, node2) and
ssaAccessAt(node1, cc, _, bb, i)
)
}
private predicate storeStepClosure(
ClosureNode node1, CapturedVariable v, ClosureNode node2, boolean alias
) {
exists(BasicBlock bb, int i, Expr closure |
synthRead(v, bb, i, _, closure, alias) and
node1 = TSynthRead(v, bb, i, false)
|
node2 = TExprNode(closure, false)
or
node2 = TMallocNode(closure) and hasConstructorCapture(closure, v)
)
}
predicate storeStep(ClosureNode node1, CapturedVariable v, ClosureNode node2) {
// store v in the closure or in the malloc in case of a relevant constructor call
storeStepClosure(node1, v, node2, _)
or
// write to v inside the closure body
exists(BasicBlock bb, int i, VariableWrite vw |
captureWrite(v, bb, i, false, vw) and
node1 = TVariableWriteSourceNode(vw) and
node2 = TSynthThisQualifier(bb, i, true)
)
}
predicate readStep(ClosureNode node1, CapturedVariable v, ClosureNode node2) {
// read v from the closure post-update to observe side-effects
exists(BasicBlock bb, int i, Expr closure, boolean post |
synthRead(v, bb, i, _, closure) and
node1 = TExprNode(closure, post) and
node2 = TSynthRead(v, bb, i, true)
|
post = true
or
// for a constructor call the regular ExprNode is the post-update for the MallocNode
post = false and hasConstructorCapture(closure, v)
)
or
// read v from the closure inside the closure body
exists(BasicBlock bb, int i | node1 = TSynthThisQualifier(bb, i, false) |
synthRead(v, bb, i, false, _) and
node2 = TSynthRead(v, bb, i, false)
or
exists(VariableRead vr |
captureRead(v, bb, i, false, vr) and
node2 = TExprNode(vr, false)
)
)
}
predicate clearsContent(ClosureNode node, CapturedVariable v) {
/*
* Stores into closure aliases block flow from previous stores, both to
* avoid overlapping data flow paths, but also to avoid false positive
* flow.
*
* Example 1 (overlapping paths):
*
* ```rb
You can’t perform that action at this time.