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