1 /* 2 * Copyright 2014 Google Inc. All Rights Reserved. 3 * 4 * Modifications copyright (C) 2017 Uber Technologies, Inc. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 package com.uber.nullaway.dataflow; 20 21 import static com.uber.nullaway.NullabilityUtil.findEnclosingMethodOrLambdaOrInitializer; 22 23 import com.google.auto.value.AutoValue; 24 import com.google.common.base.Preconditions; 25 import com.google.common.cache.CacheBuilder; 26 import com.google.common.cache.CacheLoader; 27 import com.google.common.cache.LoadingCache; 28 import com.google.errorprone.util.ASTHelpers; 29 import com.sun.source.tree.BlockTree; 30 import com.sun.source.tree.ClassTree; 31 import com.sun.source.tree.ExpressionTree; 32 import com.sun.source.tree.LambdaExpressionTree; 33 import com.sun.source.tree.MethodTree; 34 import com.sun.source.tree.Tree; 35 import com.sun.source.tree.VariableTree; 36 import com.sun.source.util.TreePath; 37 import com.sun.tools.javac.processing.JavacProcessingEnvironment; 38 import com.sun.tools.javac.util.Context; 39 import com.uber.nullaway.NullabilityUtil; 40 import javax.annotation.Nullable; 41 import javax.annotation.processing.ProcessingEnvironment; 42 import org.checkerframework.nullaway.dataflow.analysis.AbstractValue; 43 import org.checkerframework.nullaway.dataflow.analysis.Analysis; 44 import org.checkerframework.nullaway.dataflow.analysis.AnalysisResult; 45 import org.checkerframework.nullaway.dataflow.analysis.ForwardAnalysisImpl; 46 import org.checkerframework.nullaway.dataflow.analysis.ForwardTransferFunction; 47 import org.checkerframework.nullaway.dataflow.analysis.Store; 48 import org.checkerframework.nullaway.dataflow.analysis.TransferFunction; 49 import org.checkerframework.nullaway.dataflow.cfg.ControlFlowGraph; 50 import org.checkerframework.nullaway.dataflow.cfg.UnderlyingAST; 51 import org.checkerframework.nullaway.dataflow.cfg.builder.CFGBuilder; 52 53 /** 54 * Provides a wrapper around {@link org.checkerframework.nullaway.dataflow.analysis.Analysis}. 55 * 56 * <p>Modified from Error Prone code for more aggressive caching, and to avoid static state. See 57 * {@link com.google.errorprone.dataflow.DataFlow} 58 */ 59 public final class DataFlow { 60 61 /* 62 * We cache both the control flow graph and the analyses that are run on it. 63 * 64 * Unlike in Error Prone's core analyses, sometimes we do not complete all analyses on a CFG 65 * before moving on to the next one. So, here we set a reasonable maximum size to avoid leaks, 66 * and also expose an API method to clear the caches. 67 */ 68 private static final int MAX_CACHE_SIZE = 50; 69 70 private final boolean assertsEnabled; 71 DataFlow(boolean assertsEnabled)72 DataFlow(boolean assertsEnabled) { 73 this.assertsEnabled = assertsEnabled; 74 } 75 76 private final LoadingCache<AnalysisParams, Analysis<?, ?, ?>> analysisCache = 77 CacheBuilder.newBuilder() 78 .maximumSize(MAX_CACHE_SIZE) 79 .build( 80 new CacheLoader<AnalysisParams, Analysis<?, ?, ?>>() { 81 @Override 82 public Analysis<?, ?, ?> load(AnalysisParams key) { 83 final ControlFlowGraph cfg = key.cfg(); 84 final ForwardTransferFunction<?, ?> transfer = key.transferFunction(); 85 86 @SuppressWarnings({"unchecked", "rawtypes"}) 87 final Analysis<?, ?, ?> analysis = new ForwardAnalysisImpl<>(transfer); 88 analysis.performAnalysis(cfg); 89 return analysis; 90 } 91 }); 92 93 private final LoadingCache<CfgParams, ControlFlowGraph> cfgCache = 94 CacheBuilder.newBuilder() 95 .maximumSize(MAX_CACHE_SIZE) 96 .build( 97 new CacheLoader<CfgParams, ControlFlowGraph>() { 98 @Override 99 public ControlFlowGraph load(CfgParams key) { 100 final TreePath codePath = key.codePath(); 101 final TreePath bodyPath; 102 final UnderlyingAST ast; 103 final ProcessingEnvironment env = key.environment(); 104 if (codePath.getLeaf() instanceof LambdaExpressionTree) { 105 LambdaExpressionTree lambdaExpressionTree = 106 (LambdaExpressionTree) codePath.getLeaf(); 107 MethodTree enclMethod = 108 ASTHelpers.findEnclosingNode(codePath, MethodTree.class); 109 ClassTree enclClass = ASTHelpers.findEnclosingNode(codePath, ClassTree.class); 110 ast = new UnderlyingAST.CFGLambda(lambdaExpressionTree, enclClass, enclMethod); 111 bodyPath = new TreePath(codePath, lambdaExpressionTree.getBody()); 112 } else if (codePath.getLeaf() instanceof MethodTree) { 113 MethodTree method = (MethodTree) codePath.getLeaf(); 114 ClassTree enclClass = ASTHelpers.findEnclosingNode(codePath, ClassTree.class); 115 ast = new UnderlyingAST.CFGMethod(method, enclClass); 116 BlockTree body = method.getBody(); 117 if (body == null) { 118 throw new IllegalStateException( 119 "trying to compute CFG for method " + method + ", which has no body"); 120 } 121 bodyPath = new TreePath(codePath, body); 122 } else { 123 // must be an initializer per findEnclosingMethodOrLambdaOrInitializer 124 ast = 125 new UnderlyingAST.CFGStatement( 126 codePath.getLeaf(), (ClassTree) codePath.getParentPath().getLeaf()); 127 bodyPath = codePath; 128 } 129 130 return CFGBuilder.build(bodyPath, ast, assertsEnabled, !assertsEnabled, env); 131 } 132 }); 133 134 /** 135 * Run the {@code transfer} dataflow analysis over the method, lambda or initializer which is the 136 * leaf of the {@code path}. 137 * 138 * <p>For caching, we make the following assumptions: - if two paths to methods are {@code equal}, 139 * their control flow graph is the same. - if two transfer functions are {@code equal}, and are 140 * run over the same control flow graph, the analysis result is the same. - for all contexts, the 141 * analysis result is the same. 142 */ 143 private <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> dataflow(TreePath path, Context context, T transfer)144 Result<A, S, T> dataflow(TreePath path, Context context, T transfer) { 145 final ProcessingEnvironment env = JavacProcessingEnvironment.instance(context); 146 final ControlFlowGraph cfg = cfgCache.getUnchecked(CfgParams.create(path, env)); 147 final AnalysisParams aparams = AnalysisParams.create(transfer, cfg); 148 @SuppressWarnings("unchecked") 149 final Analysis<A, S, T> analysis = (Analysis<A, S, T>) analysisCache.getUnchecked(aparams); 150 151 return new Result<A, S, T>() { 152 @Override 153 public Analysis<A, S, T> getAnalysis() { 154 return analysis; 155 } 156 157 @Override 158 public ControlFlowGraph getControlFlowGraph() { 159 return cfg; 160 } 161 }; 162 } 163 164 /** 165 * Get the control flow graph (GFG) for a given expression. 166 * 167 * @param path expression 168 * @param context Javac context 169 * @param transfer transfer functions 170 * @param <A> values in abstraction 171 * @param <S> store type 172 * @param <T> transfer function type 173 * @return {@link ControlFlowGraph} containing expression 174 */ 175 <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 176 ControlFlowGraph getControlFlowGraph(TreePath path, Context context, T transfer) { 177 return dataflow(findEnclosingMethodOrLambdaOrInitializer(path), context, transfer) 178 .getControlFlowGraph(); 179 } 180 181 /** 182 * Run the {@code transfer} dataflow analysis to compute the abstract value of the expression 183 * which is the leaf of {@code exprPath}. 184 * 185 * @param exprPath expression 186 * @param context Javac context 187 * @param transfer transfer functions 188 * @param <A> values in abstraction 189 * @param <S> store type 190 * @param <T> transfer function type 191 * @return dataflow value for expression 192 */ 193 @Nullable 194 public <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 195 A expressionDataflow(TreePath exprPath, Context context, T transfer) { 196 AnalysisResult<A, S> analysisResult = resultForExpr(exprPath, context, transfer); 197 return analysisResult == null ? null : analysisResult.getValue(exprPath.getLeaf()); 198 } 199 200 /** 201 * Get the dataflow result at exit for a given method (or lambda, or initializer block) 202 * 203 * @param path path to method (or lambda, or initializer block) 204 * @param context Javac context 205 * @param transfer transfer functions 206 * @param <A> values in abstraction 207 * @param <S> store type 208 * @param <T> transfer function type 209 * @return dataflow result at exit of method 210 */ 211 public <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 212 S finalResult(TreePath path, Context context, T transfer) { 213 final Tree leaf = path.getLeaf(); 214 Preconditions.checkArgument( 215 leaf instanceof MethodTree 216 || leaf instanceof LambdaExpressionTree 217 || leaf instanceof BlockTree 218 || leaf instanceof VariableTree, 219 "Leaf of methodPath must be of type MethodTree, LambdaExpressionTree, BlockTree, or VariableTree, but was %s", 220 leaf.getClass().getName()); 221 222 return dataflow(path, context, transfer).getAnalysis().getRegularExitStore(); 223 } 224 225 @Nullable 226 public <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 227 S resultBeforeExpr(TreePath exprPath, Context context, T transfer) { 228 AnalysisResult<A, S> analysisResult = resultForExpr(exprPath, context, transfer); 229 return analysisResult == null ? null : analysisResult.getStoreBefore(exprPath.getLeaf()); 230 } 231 232 /** 233 * like {@link #resultBeforeExpr(TreePath, Context, ForwardTransferFunction)} but for an arbitrary 234 * Tree in a method. A bit riskier to use since we don't check that there is a corresponding CFG 235 * node to the Tree; use with care. 236 */ 237 @Nullable 238 public <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 239 S resultBefore(TreePath exprPath, Context context, T transfer) { 240 AnalysisResult<A, S> analysisResult = resultFor(exprPath, context, transfer); 241 return analysisResult == null ? null : analysisResult.getStoreBefore(exprPath.getLeaf()); 242 } 243 244 @Nullable 245 <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 246 AnalysisResult<A, S> resultForExpr(TreePath exprPath, Context context, T transfer) { 247 final Tree leaf = exprPath.getLeaf(); 248 Preconditions.checkArgument( 249 leaf instanceof ExpressionTree, 250 "Leaf of exprPath must be of type ExpressionTree, but was %s", 251 leaf.getClass().getName()); 252 253 return resultFor(exprPath, context, transfer); 254 } 255 256 private <A extends AbstractValue<A>, S extends Store<S>, T extends ForwardTransferFunction<A, S>> 257 AnalysisResult<A, S> resultFor(TreePath exprPath, Context context, T transfer) { 258 final TreePath enclosingPath = 259 NullabilityUtil.findEnclosingMethodOrLambdaOrInitializer(exprPath); 260 if (enclosingPath == null) { 261 throw new RuntimeException("expression is not inside a method, lambda or initializer block!"); 262 } 263 264 final Tree method = enclosingPath.getLeaf(); 265 if (method instanceof MethodTree && ((MethodTree) method).getBody() == null) { 266 // expressions can occur in abstract methods, for example {@code Map.Entry} in: 267 // 268 // abstract Set<Map.Entry<K, V>> entries(); 269 return null; 270 } 271 // Calling getValue() on the AnalysisResult (as opposed to calling it on the Analysis itself) 272 // ensures we get the result for expr 273 // *before* any unboxing operations (like invoking intValue() on an Integer). This is 274 // important, 275 // e.g., for actually checking that the unboxing operation is legal. 276 return dataflow(enclosingPath, context, transfer).getAnalysis().getResult(); 277 } 278 279 /** clear the CFG and analysis caches */ 280 public void invalidateCaches() { 281 cfgCache.invalidateAll(); 282 analysisCache.invalidateAll(); 283 } 284 285 @AutoValue 286 abstract static class CfgParams { 287 // Should not be used for hashCode or equals 288 private ProcessingEnvironment environment; 289 290 private static CfgParams create(TreePath codePath, ProcessingEnvironment environment) { 291 CfgParams cp = new AutoValue_DataFlow_CfgParams(codePath); 292 cp.environment = environment; 293 return cp; 294 } 295 296 ProcessingEnvironment environment() { 297 return environment; 298 } 299 300 abstract TreePath codePath(); 301 } 302 303 @AutoValue 304 abstract static class AnalysisParams { 305 306 private static AnalysisParams create( 307 ForwardTransferFunction<?, ?> transferFunction, ControlFlowGraph cfg) { 308 AnalysisParams ap = new AutoValue_DataFlow_AnalysisParams(transferFunction, cfg); 309 return ap; 310 } 311 312 abstract ForwardTransferFunction<?, ?> transferFunction(); 313 314 abstract ControlFlowGraph cfg(); 315 } 316 317 /** A pair of Analysis and ControlFlowGraph. */ 318 private interface Result< 319 A extends AbstractValue<A>, S extends Store<S>, T extends TransferFunction<A, S>> { 320 Analysis<A, S, T> getAnalysis(); 321 322 ControlFlowGraph getControlFlowGraph(); 323 } 324 } 325