forked from typetools/checker-framework
-
Notifications
You must be signed in to change notification settings - Fork 2
/
MustCallConsistencyAnalyzer.java
2229 lines (2086 loc) · 102 KB
/
MustCallConsistencyAnalyzer.java
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
package org.checkerframework.checker.resourceleak;
import com.google.common.base.Preconditions;
import com.google.common.collect.FluentIterable;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.sun.source.tree.MethodInvocationTree;
import com.sun.source.tree.MethodTree;
import com.sun.source.tree.NewClassTree;
import com.sun.source.tree.Tree;
import com.sun.source.tree.VariableTree;
import com.sun.source.util.TreePath;
import com.sun.tools.javac.code.Type;
import java.io.UnsupportedEncodingException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import javax.lang.model.element.AnnotationMirror;
import javax.lang.model.element.Element;
import javax.lang.model.element.ElementKind;
import javax.lang.model.element.ExecutableElement;
import javax.lang.model.element.Name;
import javax.lang.model.element.TypeElement;
import javax.lang.model.element.VariableElement;
import javax.lang.model.type.TypeKind;
import javax.lang.model.type.TypeMirror;
import org.checkerframework.checker.calledmethods.qual.CalledMethods;
import org.checkerframework.checker.mustcall.CreatesMustCallForToJavaExpression;
import org.checkerframework.checker.mustcall.MustCallAnnotatedTypeFactory;
import org.checkerframework.checker.mustcall.MustCallChecker;
import org.checkerframework.checker.mustcall.qual.MustCall;
import org.checkerframework.checker.mustcall.qual.MustCallAlias;
import org.checkerframework.checker.mustcall.qual.NotOwning;
import org.checkerframework.checker.mustcall.qual.Owning;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.checkerframework.checker.signature.qual.FullyQualifiedName;
import org.checkerframework.dataflow.cfg.ControlFlowGraph;
import org.checkerframework.dataflow.cfg.UnderlyingAST;
import org.checkerframework.dataflow.cfg.UnderlyingAST.Kind;
import org.checkerframework.dataflow.cfg.block.Block;
import org.checkerframework.dataflow.cfg.block.Block.BlockType;
import org.checkerframework.dataflow.cfg.block.ExceptionBlock;
import org.checkerframework.dataflow.cfg.block.SingleSuccessorBlock;
import org.checkerframework.dataflow.cfg.node.AssignmentNode;
import org.checkerframework.dataflow.cfg.node.ClassNameNode;
import org.checkerframework.dataflow.cfg.node.FieldAccessNode;
import org.checkerframework.dataflow.cfg.node.LocalVariableNode;
import org.checkerframework.dataflow.cfg.node.MethodInvocationNode;
import org.checkerframework.dataflow.cfg.node.Node;
import org.checkerframework.dataflow.cfg.node.NullLiteralNode;
import org.checkerframework.dataflow.cfg.node.ObjectCreationNode;
import org.checkerframework.dataflow.cfg.node.ReturnNode;
import org.checkerframework.dataflow.cfg.node.SuperNode;
import org.checkerframework.dataflow.cfg.node.ThisNode;
import org.checkerframework.dataflow.cfg.node.TypeCastNode;
import org.checkerframework.dataflow.expression.FieldAccess;
import org.checkerframework.dataflow.expression.JavaExpression;
import org.checkerframework.dataflow.expression.LocalVariable;
import org.checkerframework.dataflow.expression.ThisReference;
import org.checkerframework.dataflow.util.NodeUtils;
import org.checkerframework.framework.flow.CFAnalysis;
import org.checkerframework.framework.flow.CFStore;
import org.checkerframework.framework.flow.CFValue;
import org.checkerframework.framework.type.AnnotatedTypeMirror;
import org.checkerframework.framework.util.JavaExpressionParseUtil.JavaExpressionParseException;
import org.checkerframework.framework.util.StringToJavaExpression;
import org.checkerframework.javacutil.AnnotationUtils;
import org.checkerframework.javacutil.ElementUtils;
import org.checkerframework.javacutil.Pair;
import org.checkerframework.javacutil.TreePathUtil;
import org.checkerframework.javacutil.TreeUtils;
import org.checkerframework.javacutil.TypeSystemError;
import org.checkerframework.javacutil.TypesUtils;
import org.plumelib.util.StringsPlume;
/**
* An analyzer that checks consistency of {@link MustCall} and {@link CalledMethods} types, thereby
* detecting resource leaks. For any expression <em>e</em> the analyzer ensures that when <em>e</em>
* goes out of scope, there exists a resource alias <em>r</em> of <em>e</em> (which might be
* <em>e</em> itself) such that the must-call methods of <em>r</em> (i.e. the values of <em>r</em>'s
* MustCall type) are contained in the value of <em>r</em>'s CalledMethods type. For any <em>e</em>
* for which this property does not hold, the analyzer reports a {@code
* "required.method.not.called"} error, indicating a possible resource leak.
*
* <p>Mechanically, the analysis does two tasks.
*
* <ul>
* <li>Tracks must-aliases, implemented via a dataflow analysis. Each dataflow fact is a set of
* resource-aliases that refer to the same resource. Furthermore, that resource is owned. No
* dataflow facts are maintained for a non-owned resource.
* <li>When the last resource alias in a resource-alias set goes out-of-scope, it checks their
* must-call and called-methods types. The analysis does not track must-call or called-methods
* types, but queries other checkers to obtain them.
* </ul>
*
* <p>Class {@link Obligation} represents a single such dataflow fact. Abstractly, each dataflow
* fact is a pair: a set of resource aliases to some resource, and the must-call obligations of that
* resource (i.e the list of must-call methods that need to be called on one of the resource
* aliases). Concretely, the Must Call Checker is responsible for tracking the latter - an
* expression's must-call type indicates which methods must be called - so this dataflow analysis
* only actually tracks the sets of resource aliases.
*
* <p>The dataflow algorithm adds, modifies, or removes dataflow facts when certain code patterns
* are encountered, to account for ownership transfer. Here are non-exhaustive examples:
*
* <ul>
* <li>A new fact is added to the tracked set when a constructor or a method with an owning return
* is invoked.
* <li>A fact is modified when an expression with a tracked Obligation is the RHS of a
* (pseudo-)assignment. The LHS is added to the existing resource alias set.
* <li>A fact can be removed when a member of a resource-alias set is assigned to an owning field
* or passed to a method in a parameter location that is annotated as {@code @Owning}.
* </ul>
*
* <p>The dataflow analysis for these Obligations is conservative in that it guarantees that for
* every resource which actually does have a must-call obligation, at least one Obligation will
* exist. However, it does not guarantee the opposite: Obligations may also exist for resources
* without a must-call obligation (or for non-resources) as a result of analysis imprecision. That
* is, the set of Obligations tracked by the analysis over-approximates the actual set of resources
* in the analyzed program with must-call obligations.
*
* <p>Throughout, this class uses the temporary-variable facilities provided by the Must Call and
* Resource Leak type factories both to emulate a three-address-form IR (simplifying some analysis
* logic) and to permit expressions to have their types refined in their respective checkers'
* stores. These temporary variables can be members of resource-alias sets. Without temporary
* variables, the checker wouldn't be able to verify code such as {@code new Socket(host,
* port).close()}, which would cause false positives. Temporaries are created for {@code new}
* expressions, method calls (for the return value), and ternary expressions. Other types of
* expressions may also be supported in the future.
*/
/* package-private */
class MustCallConsistencyAnalyzer {
/** True if errors related to static owning fields should be suppressed. */
private boolean permitStaticOwning;
/** True if errors related to field initialization should be suppressed. */
private boolean permitInitializationLeak;
/**
* Aliases about which the checker has already reported about a resource leak, to avoid duplicate
* reports.
*/
private final Set<ResourceAlias> reportedErrorAliases = new HashSet<>();
/**
* The type factory for the Resource Leak Checker, which is used to get called methods types and
* to access the Must Call Checker.
*/
private final ResourceLeakAnnotatedTypeFactory typeFactory;
/**
* A cache for the result of calling {@code ResourceLeakAnnotatedTypeFactory.getStoreAfter()} on a
* node. The cache prevents repeatedly computing least upper bounds on stores
*/
private IdentityHashMap<Node, CFStore> cmStoreAfter = new IdentityHashMap<>();
/**
* A cache for the result of calling {@code MustCallAnnotatedTypeFactory.getStoreAfter()} on a
* node. The cache prevents repeatedly computing least upper bounds on stores
*/
private IdentityHashMap<Node, CFStore> mcStoreAfter = new IdentityHashMap<>();
/** The Resource Leak Checker, used to issue errors. */
private final ResourceLeakChecker checker;
/** The analysis from the Resource Leak Checker, used to get input stores based on CFG blocks. */
private final CFAnalysis analysis;
/**
* An Obligation is a dataflow fact: a set of resource aliases. Abstractly, each Obligation
* represents a resource that the analyzed program which might have a must-call obligation. Each
* Obligation is a pair of a set of resource aliases and their must-call obligation. Must-call
* obligations are tracked by the {@link MustCallChecker} and are accessed by looking up the
* type(s) in its type system of the resource aliases contained in each {@code Obligation} using
* {@link #getMustCallMethods(ResourceLeakAnnotatedTypeFactory, CFStore)}.
*
* <p>There is no guarantee that a given Obligation represents a resource with a real must-call
* obligation. When the analysis can conclude that a given Obligation certainly does not represent
* a real resource with a real must-call obligation (such as if the only resource alias is
* certainly a null pointer, or if the must-call obligation is the empty set), the analysis can
* discard the Obligation.
*/
/* package-private */ static class Obligation {
/**
* The set of resource aliases through which a must-call obligation can be satisfied. Calling
* the required method(s) in the must-call obligation through any of them satisfies the
* must-call obligation: that is, if the called-methods type of any alias contains the required
* method(s), then the must-call obligation is satisfied. See {@link #getMustCallMethods}.
*
* <p>{@code Obligation} is deeply immutable. If some code were to accidentally mutate a {@code
* resourceAliases} set it could be really nasty to debug, so this set is always immutable.
*/
public final ImmutableSet<ResourceAlias> resourceAliases;
/**
* Create an Obligation from a set of resource aliases.
*
* @param resourceAliases a set of resource aliases
*/
public Obligation(Set<ResourceAlias> resourceAliases) {
this.resourceAliases = ImmutableSet.copyOf(resourceAliases);
}
/**
* Returns the resource alias in this Obligation's resource alias set corresponding to {@code
* localVariableNode} if one is present. Otherwise, returns null.
*
* @param localVariableNode a local variable
* @return the resource alias corresponding to {@code localVariableNode} if one is present;
* otherwise, null
*/
private @Nullable ResourceAlias getResourceAlias(LocalVariableNode localVariableNode) {
Element element = localVariableNode.getElement();
for (ResourceAlias alias : resourceAliases) {
if (alias.reference.getElement().equals(element)) {
return alias;
}
}
return null;
}
/**
* Returns the resource alias in this Obligation's resource alias set corresponding to {@code
* expression} if one is present. Otherwise, returns null.
*
* @param expression a Java expression
* @return the resource alias corresponding to {@code expression} if one is present; otherwise,
* null
*/
private @Nullable ResourceAlias getResourceAlias(JavaExpression expression) {
for (ResourceAlias alias : resourceAliases) {
if (alias.reference.equals(expression)) {
return alias;
}
}
return null;
}
/**
* Returns true if this contains a resource alias corresponding to {@code localVariableNode},
* meaning that calling the required methods on {@code localVariableNode} is sufficient to
* satisfy the must-call obligation this object represents.
*
* @param localVariableNode a local variable node
* @return true if a resource alias corresponding to {@code localVariableNode} is present
*/
private boolean canBeSatisfiedThrough(LocalVariableNode localVariableNode) {
return getResourceAlias(localVariableNode) != null;
}
/**
* Does this Obligation contain any resource aliases that were derived from {@link
* MustCallAlias} parameters?
*
* @return the logical or of the {@link ResourceAlias#derivedFromMustCallAliasParam} fields of
* this Obligation's resource aliases
*/
public boolean derivedFromMustCallAlias() {
for (ResourceAlias ra : resourceAliases) {
if (ra.derivedFromMustCallAliasParam) {
return true;
}
}
return false;
}
/**
* Gets the must-call methods (i.e. the list of methods that must be called to satisfy the
* must-call obligation) of the resource represented by this Obligation.
*
* @param rlAtf a Resource Leak Annotated Type Factory
* @param mcStore a CFStore produced by the MustCall checker's dataflow analysis. If this is
* null, then the default MustCall type of each variable's class will be used.
* @return the list of must-call method names, or null if the resource's must-call obligations
* are unsatisfiable (i.e. its value in the Must Call store is MustCallUnknown)
*/
public @Nullable List<String> getMustCallMethods(
ResourceLeakAnnotatedTypeFactory rlAtf, @Nullable CFStore mcStore) {
MustCallAnnotatedTypeFactory mustCallAnnotatedTypeFactory =
rlAtf.getTypeFactoryOfSubchecker(MustCallChecker.class);
// Need to get the LUB (ie, union) of the MC values, because if a CreatesMustCallFor method
// was called on just one of the aliases then they all need to be treated as if they need to
// call the relevant methods.
AnnotationMirror mcLub = mustCallAnnotatedTypeFactory.BOTTOM;
for (ResourceAlias alias : this.resourceAliases) {
AnnotationMirror mcAnno = getMustCallValue(alias, mcStore, mustCallAnnotatedTypeFactory);
mcLub = mustCallAnnotatedTypeFactory.getQualifierHierarchy().leastUpperBound(mcLub, mcAnno);
}
if (AnnotationUtils.areSameByName(
mcLub, "org.checkerframework.checker.mustcall.qual.MustCall")) {
return rlAtf.getMustCallValues(mcLub);
} else {
return null;
}
}
/**
* Gets the must-call type associated with the given resource alias, falling on back on the
* declared type if there is no refined type for the alias in the store.
*
* @param alias a resource alias
* @param mcStore the must-call checker's store
* @param mcAtf the must-call checker's annotated type factory
* @return the annotation from the must-call type hierarchy associated with {@code alias}
*/
private static AnnotationMirror getMustCallValue(
ResourceAlias alias, @Nullable CFStore mcStore, MustCallAnnotatedTypeFactory mcAtf) {
LocalVariable reference = alias.reference;
CFValue value = mcStore == null ? null : mcStore.getValue(reference);
if (value != null) {
AnnotationMirror result =
AnnotationUtils.getAnnotationByClass(value.getAnnotations(), MustCall.class);
if (result != null) {
return result;
}
}
// There wasn't an @MustCall annotation for it in the store, so fall back to the default
// must-call type for the class.
// TODO: we currently end up in this case when checking a call to the return type
// of a returns-receiver method on something with a MustCall type; for example,
// see tests/socket/ZookeeperReport6.java. We should instead use a poly type if we can.
TypeElement typeElt = TypesUtils.getTypeElement(reference.getType());
if (typeElt == null) {
// typeElt is null if reference.getType() was not a class, interface, annotation type,
// or enum -- that is, was not an annotatable type.
// That happens rarely, such as when it is a wildcard type. In these cases, fall back
// on a safe default: top.
return mcAtf.TOP;
}
if (typeElt.asType().getKind() == TypeKind.VOID) {
// Void types can't have methods called on them, so returning bottom is safe.
return mcAtf.BOTTOM;
}
return mcAtf.getAnnotatedType(typeElt).getAnnotationInHierarchy(mcAtf.TOP);
}
@Override
public String toString() {
return "Obligation: resourceAliases=" + Iterables.toString(resourceAliases);
}
@Override
public boolean equals(@Nullable Object obj) {
if (this == obj) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Obligation that = (Obligation) obj;
return this.resourceAliases.equals(that.resourceAliases);
}
@Override
public int hashCode() {
return Objects.hash(resourceAliases);
}
}
// Is there a different Obligation on every line of the program, or is Obligation mutable?
// (Or maybe Obligation is abstractly mutable when you consider the @MustCall types that are not
// recorded in Obligation's representation.) Could you clarify? I found the first paragraph
// confusing, including "correspond to".
/**
* A resource alias is a reference through which a must-call obligation can be satisfied. Any
* must-call obligation might be satisfiable through one or more resource aliases. An {@link
* Obligation} tracks one set of resource aliases that correspond to one must-call obligation in
* the program.
*
* <p>A resource alias is always owning; non-owning aliases are, by definition, not tracked.
*
* <p>Internally, a resource alias is represented by a pair of a local or temporary variable (the
* "reference" through which the must-call obligations for the alias set to which it belongs can
* be satisfied) and a tree that "assigns" the reference.
*/
/* package-private */ static class ResourceAlias {
/** A local variable defined in the source code or a temporary variable for an expression. */
public final LocalVariable reference;
/** The tree at which {@code reference} was assigned, for the purpose of error reporting */
public final Tree tree;
/**
* Was this ResourceAlias derived from a parameter to a method that was annotated as {@link
* MustCallAlias}? If so, the obligation containing this resource alias must be discharged only
* in one of the following ways:
*
* <ul>
* <li>it is passed to another method or constructor in an @MustCallAlias position, and then
* the containing method returns that method’s result, or the call is a super()
* constructor call annotated with {@link MustCallAlias}, or
* <li>it is stored in an owning field of the class under analysis
* </ul>
*/
public final boolean derivedFromMustCallAliasParam;
/**
* Create a new resource alias. This constructor should only be used if the resource alias was
* not derived from a method parameter annotated as {@link MustCallAlias}.
*
* @param reference the local variable
* @param tree the tree
*/
public ResourceAlias(LocalVariable reference, Tree tree) {
this(reference, tree, false);
}
/**
* Create a new resource alias.
*
* @param reference the local variable
* @param tree the tree
* @param derivedFromMustCallAliasParam true iff this resource alias was created because of an
* {@link MustCallAlias} parameter
*/
public ResourceAlias(
LocalVariable reference, Tree tree, boolean derivedFromMustCallAliasParam) {
this.reference = reference;
this.tree = tree;
this.derivedFromMustCallAliasParam = derivedFromMustCallAliasParam;
}
@Override
public String toString() {
return "(ResourceAlias: reference: " + reference + " |||| tree: " + tree + ")";
}
@Override
public boolean equals(@Nullable Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
ResourceAlias that = (ResourceAlias) o;
return reference.equals(that.reference) && tree.equals(that.tree);
}
@Override
public int hashCode() {
return Objects.hash(reference, tree);
}
}
/**
* Creates a consistency analyzer. Typically, the type factory's postAnalyze method would
* instantiate a new consistency analyzer using this constructor and then call {@link
* #analyze(ControlFlowGraph)}.
*
* @param typeFactory the type factory
* @param analysis the analysis from the type factory. Usually this would have protected access,
* so this constructor cannot get it directly.
*/
/* package-private */
MustCallConsistencyAnalyzer(ResourceLeakAnnotatedTypeFactory typeFactory, CFAnalysis analysis) {
this.typeFactory = typeFactory;
this.checker = (ResourceLeakChecker) typeFactory.getChecker();
this.analysis = analysis;
this.permitStaticOwning = checker.hasOption("permitStaticOwning");
this.permitInitializationLeak = checker.hasOption("permitInitializationLeak");
}
/**
* The main function of the consistency dataflow analysis. The analysis tracks dataflow facts
* ("Obligations") of type {@link Obligation}, each representing a set of owning resource aliases
* for some value with a non-empty {@code @MustCall} obligation. The set of tracked Obligations is
* guaranteed to include at least one Obligation for each actual resource in the program, but
* might include other, spurious Obligations, too (that is, it is a conservative
* over-approximation of the true Obligation set).
*
* <p>The analysis improves its precision by removing Obligations from tracking when it can prove
* that they do not represent real resources. For example, it is not necessary to track
* expressions with empty {@code @MustCall} obligations, because they are trivially fulfilled. Nor
* is tracking non-owning aliases necessary, because by definition they cannot be used to fulfill
* must-call obligations.
*
* @param cfg the control flow graph of the method to check
*/
// TODO: This analysis is currently implemented directly using a worklist; in the future, it
// should be rewritten to use the dataflow framework of the Checker Framework.
/* package-private */
void analyze(ControlFlowGraph cfg) {
// The `visited` set contains everything that has been added to the worklist, even if it has not
// yet been removed and analyzed.
Set<BlockWithObligations> visited = new HashSet<>();
Deque<BlockWithObligations> worklist = new ArrayDeque<>();
// Add any owning parameters to the initial set of variables to track.
BlockWithObligations entry =
new BlockWithObligations(cfg.getEntryBlock(), computeOwningParameters(cfg));
worklist.add(entry);
visited.add(entry);
while (!worklist.isEmpty()) {
BlockWithObligations current = worklist.remove();
// A *mutable* set that eventually holds the set of dataflow facts to be propagated to
// successor blocks. The set is initialized to the current dataflow facts and updated by the
// methods invoked in the for loop below.
Set<Obligation> obligations = new LinkedHashSet<>(current.obligations);
for (Node node : current.block.getNodes()) {
if (node instanceof AssignmentNode) {
updateObligationsForAssignment(obligations, (AssignmentNode) node);
} else if (node instanceof ReturnNode) {
updateObligationsForOwningReturn(obligations, cfg, (ReturnNode) node);
} else if (node instanceof MethodInvocationNode || node instanceof ObjectCreationNode) {
updateObligationsForInvocation(obligations, node);
}
// All other types of nodes are ignored. This is safe, because other kinds of
// nodes cannot create or modify the resource-alias sets that the algorithm is tracking.
}
propagateObligationsToSuccessorBlocks(obligations, current.block, visited, worklist);
}
}
/**
* Update a set of Obligations to account for a method or constructor invocation.
*
* @param obligations the Obligations to update
* @param node the method or constructor invocation
*/
private void updateObligationsForInvocation(Set<Obligation> obligations, Node node) {
removeObligationsAtOwnershipTransferToParameters(obligations, node);
if (node instanceof MethodInvocationNode
&& typeFactory.canCreateObligations()
&& typeFactory.hasCreatesMustCallFor((MethodInvocationNode) node)) {
checkCreatesMustCallForInvocation(obligations, (MethodInvocationNode) node);
// Count calls to @CreatesMustCallFor methods as creating new resources. Doing so could
// result in slightly over-counting, because @CreatesMustCallFor doesn't guarantee that a
// new resource is created: it just means that a new resource might have been created.
incrementNumMustCall(node);
}
if (!shouldTrackInvocationResult(obligations, node)) {
return;
}
if (typeFactory.declaredTypeHasMustCall(node.getTree())) {
// The incrementNumMustCall call above increments the count for the target of the
// @CreatesMustCallFor annotation. By contrast, this call increments the count for the return
// value of the method (which can't be the target of the annotation, because our syntax
// doesn't support that).
incrementNumMustCall(node);
}
updateObligationsWithInvocationResult(obligations, node);
}
/**
* Checks that an invocation of a CreatesMustCallFor method is valid.
*
* <p>Such an invocation is valid if any of the conditions in {@link
* #isValidCreatesMustCallForExpression(Set, JavaExpression, TreePath)} is true for each
* expression in the argument to the CreatesMustCallFor annotation. As a special case, the
* invocation of a CreatesMustCallFor method with "this" as its expression is permitted in the
* constructor of the relevant class (invoking a constructor already creates an obligation). If
* none of these conditions are true for any of the expressions, this method issues a
* reset.not.owning error.
*
* <p>For soundness, this method also guarantees that if any of the expressions in the
* CreatesMustCallFor annotation has a tracked Obligation, any tracked resource aliases of it will
* be removed (lest the analysis conclude that it is already closed because one of these aliases
* was closed before the method was invoked). Aliases created after the CreatesMustCallFor method
* is invoked are still permitted.
*
* @param obligations the currently-tracked Obligations; this value is side-effected if there is
* an Obligation in it which tracks any expression from the CreatesMustCallFor annotation as
* one of its resource aliases
* @param node a method invocation node, invoking a method with a CreatesMustCallFor annotation
*/
private void checkCreatesMustCallForInvocation(
Set<Obligation> obligations, MethodInvocationNode node) {
TreePath currentPath = typeFactory.getPath(node.getTree());
List<JavaExpression> cmcfExpressions =
CreatesMustCallForToJavaExpression.getCreatesMustCallForExpressionsAtInvocation(
node, typeFactory, typeFactory);
List<JavaExpression> missing = new ArrayList<>(0);
for (JavaExpression expression : cmcfExpressions) {
if (!isValidCreatesMustCallForExpression(obligations, expression, currentPath)) {
missing.add(expression);
}
}
if (missing.isEmpty()) {
// All expressions matched one of the rules, so the invocation is valid.
return;
}
// Special case for invocations of CreatesMustCallFor("this") methods in the constructor.
if (missing.size() == 1) {
JavaExpression expression = missing.get(0);
if (expression instanceof ThisReference && TreePathUtil.inConstructor(currentPath)) {
return;
}
}
String missingStrs = StringsPlume.join(", ", missing);
checker.reportError(
node.getTree(),
"reset.not.owning",
node.getTarget().getMethod().getSimpleName().toString(),
missingStrs);
}
/**
* Checks the validity of the given expression from an invoked method's {@link
* org.checkerframework.checker.mustcall.qual.CreatesMustCallFor} annotation. Helper method for
* {@link #checkCreatesMustCallForInvocation(Set, MethodInvocationNode)}.
*
* <p>An expression is valid if one of the following conditions is true: 1) the expression is an
* owning pointer, 2) the expression already has a tracked Obligation (i.e. there is already a
* resource alias in some Obligation's resource alias set that refers to the expression), or 3)
* the method in which the invocation occurs also has an @CreatesMustCallFor annotation, with the
* same expression.
*
* @param obligations the currently-tracked Obligations; this value is side-effected if there is
* an Obligation in it which tracks {@code expression} as one of its resource aliases
* @param expression an element of a method's @CreatesMustCallFor annotation
* @param path the path to the invocation of the method from whose @CreateMustCallFor annotation
* {@code expression} came
* @return true iff the expression is valid, as defined above
*/
private boolean isValidCreatesMustCallForExpression(
Set<Obligation> obligations, JavaExpression expression, TreePath path) {
if (expression instanceof FieldAccess) {
Element elt = ((FieldAccess) expression).getField();
if (!checker.hasOption(MustCallChecker.NO_LIGHTWEIGHT_OWNERSHIP)
&& typeFactory.getDeclAnnotation(elt, Owning.class) != null) {
// The expression is an Owning field. This satisfies case 1.
return true;
}
} else if (expression instanceof LocalVariable) {
Element elt = ((LocalVariable) expression).getElement();
if (!checker.hasOption(MustCallChecker.NO_LIGHTWEIGHT_OWNERSHIP)
&& typeFactory.getDeclAnnotation(elt, Owning.class) != null) {
// The expression is an Owning formal parameter. Note that this cannot actually
// be a local variable (despite expressions's type being LocalVariable) because
// the @Owning annotation can only be written on methods, parameters, and fields;
// formal parameters are also represented by LocalVariable in the bodies of methods.
// This satisfies case 1.
return true;
} else {
Obligation toRemove = null;
Obligation toAdd = null;
for (Obligation obligation : obligations) {
ResourceAlias alias = obligation.getResourceAlias(expression);
if (alias != null) {
// This satisfies case 2 above. Remove all its aliases, then return below.
if (toRemove != null) {
throw new TypeSystemError(
"tried to remove multiple sets containing a reset expression at once");
}
toRemove = obligation;
toAdd = new Obligation(ImmutableSet.of(alias));
}
}
if (toRemove != null) {
obligations.remove(toRemove);
obligations.add(toAdd);
// This satisfies case 2.
return true;
}
}
}
// TODO: Getting this every time is inefficient if a method has many @CreatesMustCallFor
// annotations, but that should be rare.
MethodTree enclosingMethodTree = TreePathUtil.enclosingMethod(path);
if (enclosingMethodTree == null) {
return false;
}
ExecutableElement enclosingMethodElt = TreeUtils.elementFromDeclaration(enclosingMethodTree);
MustCallAnnotatedTypeFactory mcAtf =
typeFactory.getTypeFactoryOfSubchecker(MustCallChecker.class);
List<String> enclosingCmcfValues =
ResourceLeakVisitor.getCreatesMustCallForValues(enclosingMethodElt, mcAtf, typeFactory);
if (enclosingCmcfValues.isEmpty()) {
return false;
}
for (String enclosingCmcfValue : enclosingCmcfValues) {
JavaExpression enclosingTarget;
try {
enclosingTarget =
StringToJavaExpression.atMethodBody(enclosingCmcfValue, enclosingMethodTree, checker);
} catch (JavaExpressionParseException e) {
// Do not issue an error here, because it would be a duplicate.
// The error will be issued by the Transfer class of the checker,
// via the CreatesMustCallForElementSupplier interface.
enclosingTarget = null;
}
if (areSame(expression, enclosingTarget)) {
// This satisfies case 3.
return true;
}
}
return false;
}
/**
* Checks whether the two JavaExpressions are the same. This is identical to calling equals() on
* one of them, with two exceptions: the second expression can be null, and "this" references are
* compared using their underlying type. (ThisReference#equals always returns true, which is
* probably a bug and isn't accurate in the case of nested classes.)
*
* @param target a JavaExpression
* @param enclosingTarget another, possibly null, JavaExpression
* @return true iff they represent the same program element
*/
private boolean areSame(JavaExpression target, @Nullable JavaExpression enclosingTarget) {
if (enclosingTarget == null) {
return false;
}
if (enclosingTarget instanceof ThisReference && target instanceof ThisReference) {
return enclosingTarget.getType().toString().equals(target.getType().toString());
} else {
return enclosingTarget.equals(target);
}
}
/**
* Given a node representing a method or constructor call, updates the set of Obligations to
* account for the result, which is treated as a new resource alias. Adds the new resource alias
* to the set of an Obligation in {@code obligations}: either an existing Obligation if the result
* is definitely resource-aliased with it, or a new Obligation if not.
*
* @param obligations the currently-tracked Obligations. This is always side-effected: either a
* new resource alias is added to the resource alias set of an existing Obligation, or a new
* Obligation with a single-element resource alias set is created and added.
* @param node the invocation node whose result is to be tracked; must be {@link
* MethodInvocationNode} or {@link ObjectCreationNode}
*/
private void updateObligationsWithInvocationResult(Set<Obligation> obligations, Node node) {
Tree tree = node.getTree();
// Only track the result of the call if there is a temporary variable for the call node
// (because if there is no temporary, then the invocation must produce an untrackable value,
// such as a primitive type).
LocalVariableNode tmpVar = typeFactory.getTempVarForNode(node);
if (tmpVar == null) {
return;
}
// `mustCallAliases` is a (possibly-empty) list of arguments passed in a MustCallAlias position.
List<Node> mustCallAliases = getMustCallAliasArgumentNodes(node);
// If call returns @This, add the receiver to mustCallAliases.
if (node instanceof MethodInvocationNode
&& typeFactory.returnsThis((MethodInvocationTree) tree)) {
mustCallAliases.add(
removeCastsAndGetTmpVarIfPresent(
((MethodInvocationNode) node).getTarget().getReceiver()));
}
if (mustCallAliases.isEmpty()) {
// If mustCallAliases is an empty List, add tmpVarAsResourceAlias to a new set.
ResourceAlias tmpVarAsResourceAlias = new ResourceAlias(new LocalVariable(tmpVar), tree);
obligations.add(new Obligation(ImmutableSet.of(tmpVarAsResourceAlias)));
} else {
for (Node mustCallAlias : mustCallAliases) {
if (mustCallAlias instanceof FieldAccessNode) {
// Do not track the call result if the MustCallAlias argument is a field. Handling of
// @Owning fields is a completely separate check, and there is never a need to track an
// alias of a non-@Owning field, as by definition such a field does not have must-call
// obligations!
} else if (mustCallAlias instanceof LocalVariableNode) {
// If mustCallAlias is a local variable already being tracked, add tmpVarAsResourceAlias
// to the set containing mustCallAlias.
Obligation obligationContainingMustCallAlias =
getObligationForVar(obligations, (LocalVariableNode) mustCallAlias);
if (obligationContainingMustCallAlias != null) {
ResourceAlias tmpVarAsResourceAlias =
new ResourceAlias(
new LocalVariable(tmpVar),
tree,
obligationContainingMustCallAlias.derivedFromMustCallAlias());
Set<ResourceAlias> newResourceAliasSet =
FluentIterable.from(obligationContainingMustCallAlias.resourceAliases)
.append(tmpVarAsResourceAlias)
.toSet();
obligations.remove(obligationContainingMustCallAlias);
obligations.add(new Obligation(newResourceAliasSet));
// It is not an error if there is no Obligation containing the must-call alias. In that
// case, what has usually happened is that no Obligation was created in the first place.
// For example, when checking the invocation of a "wrapper stream" constructor, if the
// argument in the must-call alias position is some stream with no must-call obligations
// like a ByteArrayInputStream, then no Obligation object will have been created for it
// and therefore obligationContainingMustCallAlias will be null.
}
}
}
}
}
/**
* Determines if the result of the given method or constructor invocation node should be tracked
* in {@code obligations}. In some cases, there is no need to track the result because the
* must-call obligations are already satisfied in some other way or there cannot possibly be
* must-call obligations because of the structure of the code.
*
* <p>Specifically, an invocation result does NOT need to be tracked if any of the following is
* true:
*
* <ul>
* <li>The invocation is a call to a {@code this()} or {@code super()} constructor.
* <li>The method's return type is annotated with MustCallAlias and the argument passed in this
* invocation in the corresponding position is an owning field.
* <li>The method's return type is non-owning, which can either be because the method has no
* return type or because the return type is annotated with {@link NotOwning}.
* </ul>
*
* <p>This method can also side-effect {@code obligations}, if node is a super or this constructor
* call with MustCallAlias annotations, by removing that Obligation.
*
* @param obligations the current set of Obligations, which may be side-effected
* @param node the invocation node to check; must be {@link MethodInvocationNode} or {@link
* ObjectCreationNode}
* @return true iff the result of {@code node} should be tracked in {@code obligations}
*/
private boolean shouldTrackInvocationResult(Set<Obligation> obligations, Node node) {
Tree callTree = node.getTree();
if (callTree.getKind() == Tree.Kind.NEW_CLASS) {
// Constructor results from new expressions are tracked as long as the declared type has a
// non-empty @MustCall annotation.
NewClassTree newClassTree = (NewClassTree) callTree;
ExecutableElement executableElement = TreeUtils.elementFromUse(newClassTree);
TypeElement typeElt = TypesUtils.getTypeElement(ElementUtils.getType(executableElement));
return typeElt == null
|| !typeFactory.getMustCallValue(typeElt).isEmpty()
|| !typeFactory.getMustCallValue(newClassTree).isEmpty();
}
// Now callTree.getKind() == Tree.Kind.METHOD_INVOCATION.
MethodInvocationTree methodInvokeTree = (MethodInvocationTree) callTree;
if (TreeUtils.isSuperConstructorCall(methodInvokeTree)
|| TreeUtils.isThisConstructorCall(methodInvokeTree)) {
List<Node> mustCallAliasArguments = getMustCallAliasArgumentNodes(node);
// If there is a MustCallAlias argument that is also in the set of Obligations, then remove
// it; its must-call obligation has been fulfilled by being passed on to the MustCallAlias
// constructor (because a this/super constructor call can only occur in the body of another
// constructor).
for (Node mustCallAliasArgument : mustCallAliasArguments) {
if (mustCallAliasArgument instanceof LocalVariableNode) {
removeObligationsContainingVar(obligations, (LocalVariableNode) mustCallAliasArgument);
}
}
return false;
}
return !returnTypeIsMustCallAliasWithUntrackable((MethodInvocationNode) node)
&& shouldTrackReturnType((MethodInvocationNode) node);
}
/**
* Returns true if this node represents a method invocation of a must-call-alias method, where the
* argument in the must-call-alias position is untrackable: an owning field or a pointer that is
* guaranteed to be non-owning, such as {@code "this"} or a non-owning field. Owning fields are
* handled by the rest of the checker, not by this algorithm, so they are "untrackable".
* Non-owning fields and this nodes are guaranteed to be non-owning, and are therefore also
* "untrackable". Because both owning and non-owning fields are untrackable (and there are no
* other kinds of fields), this method returns true for all field accesses.
*
* @param node a method invocation node
* @return true if this is the invocation of a method whose return type is MCA with an owning
* field or a definitely non-owning pointer
*/
private boolean returnTypeIsMustCallAliasWithUntrackable(MethodInvocationNode node) {
List<Node> mustCallAliasArguments = getMustCallAliasArgumentNodes(node);
for (Node mustCallAliasArg : mustCallAliasArguments) {
if (!(mustCallAliasArg instanceof FieldAccessNode || mustCallAliasArg instanceof ThisNode)) {
return false;
}
}
return !mustCallAliasArguments.isEmpty();
}
/**
* Checks if {@code node} is either directly enclosed by a {@link TypeCastNode}, by looking at the
* successor block in the CFG. In this case the enclosing operator is a "no-op" that evaluates to
* the same value as {@code node}. This method is only used within {@link
* #propagateObligationsToSuccessorBlocks(Set, Block, Set, Deque)} to ensure Obligations are
* propagated to cast nodes properly. It relies on the assumption that a {@link TypeCastNode} will
* only appear in a CFG as the first node in a block.
*
* @param node the CFG node
* @return {@code true} if {@code node} is in a {@link SingleSuccessorBlock} {@code b}, the first
* {@link Node} in {@code b}'s successor block is a {@link TypeCastNode}, and {@code node} is
* an operand of the successor node; {@code false} otherwise
*/
private boolean inCast(Node node) {
if (!(node.getBlock() instanceof SingleSuccessorBlock)) {
return false;
}
Block successorBlock = ((SingleSuccessorBlock) node.getBlock()).getSuccessor();
if (successorBlock != null) {
List<Node> succNodes = successorBlock.getNodes();
if (succNodes.size() > 0) {
Node succNode = succNodes.get(0);
if (succNode instanceof TypeCastNode) {
return ((TypeCastNode) succNode).getOperand().equals(node);
}
}
}
return false;
}
/**
* Transfer ownership of any locals passed as arguments to {@code @Owning} parameters at a method
* or constructor call by removing the Obligations corresponding to those locals.
*
* @param obligations the current set of Obligations, which is side-effected to remove Obligations
* for locals that are passed as owning parameters to the method or constructor
* @param node a method or constructor invocation node
*/
private void removeObligationsAtOwnershipTransferToParameters(
Set<Obligation> obligations, Node node) {
if (checker.hasOption(MustCallChecker.NO_LIGHTWEIGHT_OWNERSHIP)) {
// Never transfer ownership to parameters, matching the default in the analysis built into
// Eclipse.
return;
}
List<Node> arguments = getArgumentsOfInvocation(node);
List<? extends VariableElement> parameters = getParametersOfInvocation(node);
if (arguments.size() != parameters.size()) {
// This could happen, e.g., with varargs, or with strange cases like generated Enum
// constructors. In the varargs case (i.e. if the varargs parameter is owning),
// only the first of the varargs arguments will actually get transferred: the second
// and later varargs arguments will continue to be tracked at the call-site.
// For now, just skip this case - the worst that will happen is a false positive in
// cases like the varargs one described above.
// TODO allow for ownership transfer here if needed in future
return;
}
for (int i = 0; i < arguments.size(); i++) {
Node n = removeCastsAndGetTmpVarIfPresent(arguments.get(i));
if (n instanceof LocalVariableNode) {
LocalVariableNode local = (LocalVariableNode) n;
if (varTrackedInObligations(obligations, local)) {
// check if parameter has an @Owning annotation
VariableElement parameter = parameters.get(i);
Set<AnnotationMirror> annotationMirrors = typeFactory.getDeclAnnotations(parameter);
for (AnnotationMirror anno : annotationMirrors) {
if (AnnotationUtils.areSameByName(
anno, "org.checkerframework.checker.mustcall.qual.Owning")) {
Obligation localObligation = getObligationForVar(obligations, local);
// Passing to an owning parameter is not sufficient to resolve the
// obligation created from a MustCallAlias parameter, because the containing
// method must actually return the value.
if (!localObligation.derivedFromMustCallAlias()) {
// Transfer ownership!
obligations.remove(localObligation);
break;
}
}
}
}
}
}
}
/**
* If the return type of the enclosing method is {@code @Owning}, treat the must-call obligations
* of the return expression as satisfied by removing all references to them from {@code
* obligations}.
*
* @param obligations the current set of tracked Obligations. If ownership is transferred, it is
* side-effected to remove any Obligations that are resource-aliased to the return node.
* @param cfg the CFG of the enclosing method
* @param node a return node
*/
private void updateObligationsForOwningReturn(
Set<Obligation> obligations, ControlFlowGraph cfg, ReturnNode node) {
if (isTransferOwnershipAtReturn(cfg)) {
Node returnExpr = node.getResult();
returnExpr = getTempVarOrNode(returnExpr);
if (returnExpr instanceof LocalVariableNode) {
removeObligationsContainingVar(obligations, (LocalVariableNode) returnExpr);
}
}
}
/**