wala/wala

T.J. Watson Libraries for Analysis, with frontends for Java, Android, and JavaScript, and may common static program analyses

---

The T. J. Watson Libraries for Analysis (WALA) provide static analysis capabilities for Java bytecode and related languages and for JavaScript. The system is licensed under the Eclipse Public License, which has been approved by the OSI (Open Source Initiative) as a fully certified open source license. The initial WALA infrastructure was independently developed as part of the DOMO research project at the IBM T.J. Watson Research Center. In 2006, IBM donated the software to the community.

For recent updates on WALA, join the mailing list.

Core WALA Features

WALA features include:

• Java type system and class hierarchy analysis
• Source language framework supporting Java and JavaScript
• Interprocedural dataflow analysis (RHS solver)
• Context-sensitive tabulation-based slicer
• Pointer analysis and call graph construction
• SSA-based register-transfer language IR
• General framework for iterative dataflow
• General analysis utilities and data structures
• A bytecode instrumentation library (Shrike)

Getting Started

The fastest way to get started with WALA is to use the packages in Maven Central, as noted here. See the WALA-start repo for a Gradle-based example. We are actively re-organizing the deeper wiki technical documentation. In the meantime, you can check out tutorial slides to get an overview of WALA:

• Core WALA (PDF)
• WALA JavaScript (PDF)

You can also watch screencasts of the WALA JavaScript tutorial here.

Finally, for now, to search the wiki documentation, we recommend a site-specific search on GitHub, e.g., a search for "call graph".

Documentation

We're hosting documentation for WALA on the GitHub wiki. We've chosen a wiki format just so that you can contribute. Don't be shy!

The WALA publications department is populating this wiki with technical documentation on a demand-driven basis, driven by questions posted to the wala-wala mailing list and also Gitter. We recommend this page for searching the mailing list archives.

Currently, we have the JavaDoc documentation for the WALA code being updated continuously. If you think a particular file deserves better javadoc, please open a feature request.

Getting Help

To get help with WALA, please either email the mailing list, ask a question on Gitter, or open an issue.

Required Java Versions

Most components of each official WALA release are built for use with Java 11 or newer. However, components that use Eclipse require at least Java 17.

Building from Source

WALA uses Gradle as its build system. If you intend to modify or build WALA yourself, then see the Gradle-specific README for more instructions and helpful tips.

WALA Tools in JavaScript

Recently, we have been expanding the set of WALA tools implemented in JavaScript. We have released a normalizer and some basic program analyses for JavaScript in the JS_WALA GitHub repository. We have also made available jsdelta and WALA Delta, delta debuggers for JavaScript-processing tools. Please see the linked GitHub repositories for further details on these tools.

WALA-Based Tools

Several groups have built open-source tools that enhance or build on WALA that may be useful to other WALA users. For details, see the Wala-based tools page.

Acknowledgements

We thank YourKit for providing WALA developers with a complimentary license for their excellent Java profiler, which we use to improve and maintain WALA performance.

wala's Issues

Using ControlDependenceOptions.NO_EXCEPTIONAL_EDGES results in java.lang.NullPointerException

Exception in thread "main" java.lang.NullPointerException
at com.ibm.wala.util.graph.dominators.DominanceFrontiers.getDominanceFrontier(DominanceFrontiers.java:50)
at com.ibm.wala.cfg.cdg.ControlDependenceGraph.buildControlDependence(ControlDependenceGraph.java:77)
at com.ibm.wala.cfg.cdg.ControlDependenceGraph.(ControlDependenceGraph.java:231)
at com.ibm.wala.cfg.cdg.ControlDependenceGraph.(ControlDependenceGraph.java:238)
at com.ibm.wala.ipa.slicer.PDG.createControlDependenceEdges(PDG.java:248)
at com.ibm.wala.ipa.slicer.PDG.createScalarEdges(PDG.java:186)
at com.ibm.wala.ipa.slicer.PDG.populate(PDG.java:180)
at com.ibm.wala.ipa.slicer.PDG.getNumber(PDG.java:1240)
at com.ibm.wala.ipa.slicer.SDGSupergraph.getLocalBlockNumber(SDGSupergraph.java:154)
at com.ibm.wala.ipa.slicer.SDGSupergraph.getLocalBlockNumber(SDGSupergraph.java:1)
at com.ibm.wala.dataflow.IFDS.TabulationSolver.processParticularCallee(TabulationSolver.java:646)
at com.ibm.wala.dataflow.IFDS.TabulationSolver.processCall(TabulationSolver.java:554)
at com.ibm.wala.dataflow.IFDS.TabulationSolver.forwardTabulateSLRPs(TabulationSolver.java:279)
at com.ibm.wala.dataflow.IFDS.TabulationSolver.solve(TabulationSolver.java:206)
at com.ibm.wala.ipa.slicer.Slicer.slice(Slicer.java:205)
at com.ibm.wala.ipa.slicer.Slicer.computeSlice(Slicer.java:184)
at com.ibm.wala.ipa.slicer.Slicer.computeForwardSlice(Slicer.java:145)

Stop using Sourceforge

It looks like sketchy stuff is happening on Sourceforge:

https://news.ycombinator.com/item?id=9612152

It will take some work, but I think it should be a medium- to long-term goal to get our site, hosted files, etc. off of Sourceforge.

get wala.core regression tests passing on Java 7

Some tests currently fail due to differences in the standard library, I think.

Some code for autoboxing semantics

I have in my code base the following code for autoboxing support; maybe it can be added to TypeReference or wherever it may be appropriate. It seems like a nice addition when dealing with type signatures.

  /**
   * @brief
   *  Perform unboxing i.e. apply the following mapping
   *  <ul>
   *    <li>java.lang.Boolean -> boolean</li>
   *    <li>java.lang.Byte -> byte</li>
   *    <li>java.lang.Character -> char</li>
   *    <li>java.lang.Double -> double</li>
   *    <li>java.lang.Float -> float</li>
   *    <li>java.lang.Integer -> int</li>
   *    <li>java.lang.Long -> long</li>
   *    <li>java.lang.Short -> short</li>
   *  </ul>
   *  if @a t refers to one of the types on the left-hand side,
   *  otherwise simply return @a t.
   * @param t
   *  The type reference.
   * @return
   *  The type reference to the unboxed type or @a t.
   */
  public static TypeReference unbox(TypeReference t) {
    if (t == TypeReference.JavaLangBoolean) {
      return TypeReference.Boolean;
    } else if (t == TypeReference.JavaLangByte) {
      return TypeReference.Byte;
    } else if (t == TypeReference.JavaLangCharacter) {
      return TypeReference.Char;
    } else if (t == TypeReference.JavaLangDouble) {
      return TypeReference.Double;
    } else if (t == TypeReference.JavaLangFloat) {
      return TypeReference.Float;
    } else if (t == TypeReference.JavaLangInteger) {
      return TypeReference.Int;
    } else if (t == TypeReference.JavaLangLong) {
      return TypeReference.Long;
    } else if (t == TypeReference.JavaLangShort) {
      return TypeReference.Short;
    } else {
      return t;
    }
  }

  /**
   * @brief
   *  Perform boxing i.e. apply the following mapping
   *  <ul>
   *    <li>boolean -> java.lang.Boolean</li>
   *    <li>byte -> java.lang.Byte</li>
   *    <li>char -> java.lang.Character</li>
   *    <li>double -> java.lang.Double</li>
   *    <li>float -> java.lang.Float</li>
   *    <li>int -> java.lang.Integer</li>
   *    <li>long -> java.lang.Long</li>
   *    <li>short -> java.lang.Short</li>
   *  <ul>
   *  if @a t refers to one of the types on the left-hand side,
   *  otherwise simply return @a t.
   * @param t
   *  The type reference.
   * @return
   *  The type reference to the boxed type or @a t.
   */
  public static TypeReference box(TypeReference t) {
    if (t == TypeReference.Boolean) {
      return TypeReference.JavaLangBoolean;
    } else if (t == TypeReference.Byte) {
      return TypeReference.JavaLangByte;
    } else if (t == TypeReference.Char) {
      return TypeReference.JavaLangCharacter;
    } else if (t == TypeReference.Double) {
      return TypeReference.JavaLangDouble;
    } else if (t == TypeReference.Float) {
      return TypeReference.JavaLangFloat;
    } else if (t == TypeReference.Int) {
      return TypeReference.JavaLangInteger;
    } else if (t == TypeReference.Long) {
      return TypeReference.JavaLangLong;
    } else if (t == TypeReference.Short) {
      return TypeReference.JavaLangShort;
    } else {
      return t;
    }
  }

VectorGenFlowFunction not propagating 0 by default

I don't know if this can be considered a bug or not, but it did give be a bit of a headache when I first used VectorGenFlowFunction.

VectorGenFlowFunction.make(SparseIntSet.singleton(7)) makes a flow function:

0 -> { 7 }
7 -> { }
* -> { * }

Should it make a flow function more akin to:

0 -> { 0, 7 }
* -> { * }

I guess 7 -> {} is a performance optimization that assumes 0 on input.
What I don't understand is the reason for killing 0, i.e., 0 -> { 7 } instead of 0 -> {0, 7}.

The function is:

  public IntSet getTargets(int i) {
    return (i == 0) ? gen : gen.contains(i) ? null : SparseIntSet.singleton(i);
  }

better expose NullPointerAnalysis and InterprocNullPointerAnalysis

@mohrm talked about pruning certain imprecise exceptional edges from control-flow graphs based on a null-pointer analysis in the Workshop on WALA. I found the NullPointerAnalysis and InterprocNullPointerAnalysis classes in WALA, but I didn't see any uses of them. Maybe we can provide a standard API for computing pruned CFGs based on these analyses and make it more visible?

proper Maven Central support

We have some unofficial jars for wala.util, wala.shrike, and wala.core in the Sonatype repository, as noted in #68. But, these aren't properly versioned, so updating them is completely hackish right now. We need to put at least these jars in Maven Central. We should do this along with cutting a new WALA release. Doing it properly requires changing version numbers in various XML files; we should probably write a script to do it.

In general, we should try to set things up so that we can do more frequent minor releases, to make it easy to get the latest fixes into Maven Central.

Two classes in com.ibm.wala.analysis.reflection are not public

FactoryBypassInterpreter and GetClassContextSelector in com.ibm.wala.analysis.reflection are not public
and can not be accessed from outside package. The classes should be accessible from outside packages.

make JavaScript slicer code more visible

I thought we didn't support slicing for JavaScript, but then I saw this code:

https://github.com/wala/WALA/blob/master/com.ibm.wala.cast.js.test/harness-src/com/ibm/wala/cast/js/test/TestJavaScriptSlicer.java#L74

We should make this more visible by pulling it out to a JavaScriptSlicer class in the main wala.cast.js project.

Fix CAst Java front-ends with AstTranslator.NEW_LEXICAL enabled

While the JavaScript front-end works with the new scheme for handling lexical scopes, the Java front-ends do not. Fix this.

Fix warnings

There are lots of warnings about redundant casts, redundant checks, .... in Eclipse. I will fix many of them soon and make the code using generics where possible (many old parts are written in pre-generics style). I announce that here, so there is no need for others to do that.

Is there a reason that com.ibm.wala.util.collections.Filter is deprecated?
The deprecation causes warnings all over the place.

Java7CallGraphTest.testOcamlHelloHash() failing

This regression test fails for me when running on JDK 1.7.0_72. I wonder if the JDK update caused the problem? @juliandolby can you reproduce?

Wala crashes on analyzing bobo

When I use Wala to build call graphs for bobo, it crashes.
The source files of bobo can be downloaded from https://github.com/javasoze/bobo

The stack is as follows:
com.ibm.wala.util.debug.UnimplementedError: unexpected instance key [<src-class: Lcom/browseengine/bobo/util/ListMerger$MergedIterator]
at com.ibm.wala.util.debug.Assertions.UNREACHABLE(Assertions.java:55)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor$5.act(AstSSAPropagationCallGraphBuilder.java:681)
at com.ibm.wala.util.intset.SparseIntSet.foreach(SparseIntSet.java:438)
at com.ibm.wala.util.intset.MutableSharedBitVectorIntSet.foreach(MutableSharedBitVectorIntSet.java:269)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor.getLexicalDefiners(AstSSAPropagationCallGraphBuilder.java:670)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor.access$1(AstSSAPropagationCallGraphBuilder.java:643)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor$LexicalOperator.doLexicalPointerKeys(AstSSAPropagationCallGraphBuilder.java:582)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor$LexicalOperator.access$1(AstSSAPropagationCallGraphBuilder.java:573)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor.visitLexical(AstSSAPropagationCallGraphBuilder.java:314)
at com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder$AstConstraintVisitor.visitAstLexicalWrite(AstSSAPropagationCallGraphBuilder.java:355)
at com.ibm.wala.cast.ir.ssa.AstLexicalWrite.visit(AstLexicalWrite.java:95)
at com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder.addBlockInstructionConstraints(SSAPropagationCallGraphBuilder.java:277)
at com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder.addNodeInstructionConstraints(SSAPropagationCallGraphBuilder.java:256)
at com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder.unconditionallyAddConstraintsFromNode(SSAPropagationCallGraphBuilder.java:229)
at com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder.addConstraintsFromNode(SSAPropagationCallGraphBuilder.java:195)
at com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder.addConstraintsFromNewNodes(PropagationCallGraphBuilder.java:338)
at com.ibm.wala.ipa.callgraph.propagation.StandardSolver.solve(StandardSolver.java:58)
at com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder.makeCallGraph(PropagationCallGraphBuilder.java:263)
at com.ibm.wala.client.AbstractAnalysisEngine.buildCallGraph(AbstractAnalysisEngine.java:136)

Flakiness in running tests under Maven

When running mvn clean verify after a fresh checkout, the WALA core tests fail to run, with the following error:

[ERROR] Failed to execute goal org.apache.maven.plugins:maven-surefire-plugin:2.14.1:test (test) on project com.ibm.wala.core.tests: Execution test of goal org.apache.maven.plugins:maven-surefire-plugin:2.14.1:test failed: There was an error in the forked process
[ERROR] java.lang.NoClassDefFoundError: com/ibm/wala/util/graph/NumberedGraph
[ERROR] at java.lang.Class.getDeclaredMethods0(Native Method)
[ERROR] at java.lang.Class.privateGetDeclaredMethods(Class.java:2451)
[ERROR] at java.lang.Class.getMethod0(Class.java:2694)
[ERROR] at java.lang.Class.getMethod(Class.java:1622)
[ERROR] at org.apache.maven.surefire.util.ReflectionUtils.tryGetMethod(ReflectionUtils.java:57)
[ERROR] at org.apache.maven.surefire.common.junit3.JUnit3TestChecker.isSuiteOnly(JUnit3TestChecker.java:64)
[ERROR] at org.apache.maven.surefire.common.junit3.JUnit3TestChecker.isValidJUnit3Test(JUnit3TestChecker.java:59)
[ERROR] at org.apache.maven.surefire.common.junit3.JUnit3TestChecker.accept(JUnit3TestChecker.java:54)
[ERROR] at org.apache.maven.surefire.common.junit4.JUnit4TestChecker.accept(JUnit4TestChecker.java:51)
[ERROR] at org.apache.maven.surefire.util.DefaultScanResult.applyFilter(DefaultScanResult.java:97)
[ERROR] at org.apache.maven.surefire.junit4.JUnit4Provider.scanClassPath(JUnit4Provider.java:206)
[ERROR] at org.apache.maven.surefire.junit4.JUnit4Provider.invoke(JUnit4Provider.java:103)
[ERROR] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
[ERROR] at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
[ERROR] at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
[ERROR] at java.lang.reflect.Method.invoke(Method.java:601)
[ERROR] at org.apache.maven.surefire.util.ReflectionUtils.invokeMethodWithArray2(ReflectionUtils.java:208)

However, if we run mvn clean verify -DskipTests=true, and then run mvn clean verify, the tests run fine and pass. We should probably figure out what's going on here.

crash building JS IR due to dead code

Here's an example that causes a crash:

(function() {
    return;
    try {
      x();
    } catch (e) {
    }
});

Looks like a dead code issue.

another JavaScript try-finally crash

We currently crash for the following test case:

var x = function() {
    try {
        y;
    } catch (e) {
        for (0; this.p.q; ) {}
    } finally {
        return;
    }
};

x();

I added TestSimpleCallGraphShape.testTryFinallyCrash() for the above (it's currently ignored).

support invokedynamic

This will be more important when Java 8 is released, as lambdas my be compiled using invokedynamic:

http://zeroturnaround.com/rebellabs/java-8-the-first-taste-of-lambdas/#!/

Weird generic types in DefaultFixedPointSystem

When fixing another bug, I noticed some strange generic type instantiations in DefaultFixedPointSystem. In particular, all the addStatement methods instantiate generic types with ? or no type parameter instead of using T, e.g.:

https://github.com/wala/WALA/blob/master/com.ibm.wala.util/src/com/ibm/wala/fixedpoint/impl/DefaultFixedPointSystem.java#L107
https://github.com/wala/WALA/blob/master/com.ibm.wala.util/src/com/ibm/wala/fixedpoint/impl/DefaultFixedPointSystem.java#L122

I was going to go through and fix these to refer to T, but then I wondered if there is some good reason for the code to be this way. @juliandolby @sjfink any idea what is going on here?

Update to compile with Eclipse Luna

I'm running Eclipse Kepler SR2 with the patched JDT to handle Java 8, and I get the following compile errors in com.ibm.wala.ide.jdt:

Description Resource    Path    Location    Type
The type FakeExceptionTypeBinding must implement the inherited abstract method ITypeBinding.getTypeAnnotations()    FakeExceptionTypeBinding.java   /com.ibm.wala.ide.jdt/source/com/ibm/wala/cast/java/translator/jdt  line 58 Java Problem
The type FakeExceptionTypeBinding must implement the inherited abstract method ITypeBinding.getFunctionalInterfaceMethod()  FakeExceptionTypeBinding.java   /com.ibm.wala.ide.jdt/source/com/ibm/wala/cast/java/translator/jdt  line 58 Java Problem

I'm guessing these errors will persist under Eclipse Luna. Nothing urgent, just noting for future reference.

Why are SSAPiInstructions inserted at the end of basic blocks?

Is there a reason SSAPiInstructions are inserted at the end of basic blocks?

I think it is not intuitive: Usually basic blocks have a single exit point. In case of a conditional branch, there will be pi instructions for each successor of the branch. Both pi instructions are inserted into the basic block of the branch. As a result this basic block has now two exit points.

add handling of zero-length arrays to refinement-based pointer analysis

Our standard pointer analyses can now reason that arrays of length 0 have no contents, but the refinement-based pointer analysis does not. This is now causing test failures on recent versions of ArrayList in the Java 7 libraries, forcing us to disable some tests (see b057e35). We should enhance the refinement-based analysis to reason precisely about length 0 arrays.

com.ibm.wala.util.warnings.Warnings.toString() may cause java.util.ConcurrentModificationException

com.ibm.wala.util.warnings.Warnings.toString() accesses the collection of warnings when calling T.addAll(warnings). This may cause a java.util.ConcurrentModificationException
if a warning is added to the collection or the collection is cleared while T.addAll(warnings) is being executed.

Duplicate of #43.

Duplicate of #43. (I will re-use this issue asap).

JavaLangClassContextInterpreter and JavaLangClassContextSelector improvement

As far as I can see JavaLangClassContextInterpreter and JavaLangClassContextSelector do not take advantage of the special case when the first argument to getMethod or getDeclaredMethod - i.e. the string of the method name - is a constant (cf. ClassFactoryContextInterpreter and ClassFactoryContextSelector which use a similar mechanism). Taking this into account would increase the precision in that special case.

To implement that behaviour I have created a new context selector and a new context interpreter plus a sub-class of JavaTypeContext to capture that case. Is this approach correct and does anyone of the developers want that code, check it or maybe implement something similar?

Getting Started guide's "Building the code" doesn't work

Building from source following the Getting Started guide unfortunately fails on a mvn clean verify -DskipTests=true -q:

[ERROR] Failed to execute goal org.apache.maven.plugins:maven-antrun-plugin:1.7:run (default) on project com.ibm.wala.cast.java.polyglot: An Ant BuildException has occured: The following error occurred while executing this line:
[ERROR] /Users/sewe/Documents/Workspaces/github/wala/WALA/com.ibm.wala.cast.java.polyglot/build.xml:50: Basedir /Users/sewe/Documents/Workspaces/github/wala/WALA/com.ibm.wala.cast.java.polyglot/temp.folder/polyglot-compiler-read-only/polyglot does not exist
[ERROR] around Ant part ...<ant antfile="/Users/sewe/Documents/Workspaces/github/wala/WALA/com.ibm.wala.cast.java.polyglot/build.xml" target="getJars"/>... @ 5:128 in /Users/sewe/Documents/Workspaces/github/wala/WALA/com.ibm.wala.cast.java.polyglot/target/antrun/build-main.xml

Is there a step missing in the Getting Started guide?

com.ibm.wala.ide.tests depends on CAst projects

This is inconsistent with our Getting Started documention, which doesn't indicate that you need the CAst projects to get ide.tests to compile:

http://wala.sourceforge.net/wiki/index.php/UserGuide:Getting_Started#Getting_the_code

We should either remove the dependence by adding a new project, or update the documentation.

Add appropriate @Override annotations

Now that we're building with Java 1.6, we have tons of warnings due to missing @OverRide annotations. Easy to fix, but we should do it at a point where it won't be too painful in terms of causing conflicts, say right after the next release.

com.ibm.wala.dalvik.test: Compilation failure

[INFO] Building jar: /home/user/WALA/com.ibm.wala.cast.js.test/test.jar
[INFO] Building jar: /home/user/WALA/com.ibm.wala.dalvik/dalvik.jar
[ERROR] Failed to execute goal org.eclipse.tycho:tycho-compiler-plugin:0.21.0:compile (default-compile) on project com.ibm.wala.dalvik.test: Compilation failure: Compilation failure:
[ERROR] /home/user/WALA/com.ibm.wala.dalvik.test/source/com/ibm/wala/dalvik/test/DalvikTestBase.java:[59]
[ERROR] com.android.dx.command.Main.main(new String[]{"--dex", "--output=" + f.getAbsolutePath(), jarFile});
[ERROR] ^^^^^^^^^^^
[ERROR] com.android cannot be resolved
[ERROR] 1 problem (1 error)
[ERROR] -> [Help 1]
[ERROR]

linux machine with java 1.8 and mvn 3.0.5

ohloh.net project entry has outdated source code location

The code location of Wala on ohloh.net is outdated which makes ohloh.net conclude that the project is inactive. Someone with the right permissions should fix that.

support annotations in JDT frontend

We should support getting method and class annotation information for the JDT frontend, like we currently do for bytecode.

Performance improvement when caching the IR and DefUse within CGNode

A getIR() invocation on CGNode now requires going through the cache system, i.e. two HashSet lookups. A getDU() invocation does four lookups, as it includes a getIR() lookup. The HashSet is pretty fast but the extra lookups do take their toll (see below).

A simple solution is to put a the IR and DefUse as WeakReference fields within the ExplicitCallGraph$(new CGNode) implementation. The WeakReference will be automatically cleared whenever the cache is cleared so it will not impact the caching policy. The only worry would be the memory used by the two extra WeakRereference references and objects. Still, the test below suggests it is negligible.

I've run the CallGraphTest test with and without the addition. The test is done with 2G of RAM so that the GC doesn't kick in too early.

Before:

After:

cos/WALA@91e4ee0

move tabulation solver to wala.util

TabulationSolver should live in wala.util, as it's completely language independent.

Expose output file name from DomLessSourceExtractor

We've seen at least one client where knowing this file name can be useful, e.g., for filtering analysis results. The file is created here:

WALA/com.ibm.wala.cast.js/source/com/ibm/wala/cast/js/html/DomLessSourceExtractor.java

Line 261 in 84da2bd

File outputFile = createOutputFile(entrypointUrl, DELETE_UPON_EXIT, USE_TEMP_NAME);

Filter vs Predicate

We should re-write the code using com.ibm.wala.util.collections.Filter to use com.ibm.wala.util.Predicate instead.

DomLessSourceExtractor does not extract source with correct line numbers

In com/ibm/wala/cast/js/html/DomLessSourceExtractor.java, the line numbers of the extracted source does not match the line numbers of the original webpage.

The following steps can reproduce the problem.

1. Test it with the following website.
   http://deutsche-wolke.de

2. Print the positions of the startTag and endTag in handleText(Position p, String text) by this statement:

   scriptRegion.println("currentScriptTag position: " + currentScriptTag.getContentPosition().getFirstLine() + "-" + currentScriptTag.getContentPosition().getLastLine() + text + "\n", currentScriptTag.getContentPosition(), url);

3. Compare the line numbers of the extracted source and the original webpage.

BypassMethodTargetSelector ignores parent if it is a subclass of ClassHierarchyMethodSelector

The getCalleeTargetMethod of BypassMethodTargetSelector is supposed to delegate to its parent method selector if both the ClassHierarchyMethodTarget selector and the summaries fail to get the target of the method, but it fails to do this properly if its parent selector is a subclass of ClassHierarchyMethodTargetSelector. The problem is in the check

if (parent instanceof ClassHierarchyMethodTargetSelector) {
// already checked this case and decided not to bypass
return chaTarget;
}

If parent is a subclass of ClassHierarchyMethodTargetSelector, then its getCalleeTarget method will never be called. This is potentially bad because it may override the getCalleeTarget method of ClassHierarchyMethodTargetSelector. I discovered this issue because I created a subclass of ClassHierarchyMethodTargetSelector and was bitten by this problem.

I think this could be fixed by either:

(a) Making ClassHierarchyMethodTarget final. There are no classes in the WALA codebase that extend this class, so this will not break any WALA code, though it may break clients.

(b) Changing the "parent instanceof ClassHierarchyMethodTargetSelector" check to "parent.getClass() == ClassHierarchyMethodTargetSelector.class", "parent.getClass() == chaMethodTargetSelector.getClass()", or something similar. This is potentially fragile if parent comes from a different classloader.

I'm happy to submit a pull request, but just wanted to discuss the possible fixes in case you prefer one over the other or have a third suggestion.

At least compile all projects in Travis build

Right now, I don't think we try to compile the ide.jsdt.* projects in the Maven scripts. We should at least build them so we detect any compile error type regressions.

Cleanup annotation reading code

We have duplicated code for reading annotations in various places:

WALA/com.ibm.wala.core/src/com/ibm/wala/classLoader/ShrikeClass.java

Line 247 in dc839aa

private AnnotationsReader getAnnotationsReader(boolean runtimeInvisable) throws InvalidClassFileException {

WALA/com.ibm.wala.core/src/com/ibm/wala/classLoader/ShrikeClass.java

Line 247 in dc839aa

private AnnotationsReader getAnnotationsReader(boolean runtimeInvisable) throws InvalidClassFileException {

WALA/com.ibm.wala.core/src/com/ibm/wala/classLoader/ShrikeClass.java

Line 247 in dc839aa

private AnnotationsReader getAnnotationsReader(boolean runtimeInvisable) throws InvalidClassFileException {

This should be de-duplicated into some kind of utility method / class. Volunteers welcome :-)

Monotonic caches

I am facing another problem here though; the caches are monotonic, i.e. they grow but never shrink. I know that compilers and data-flow analysis (and associated tools) are conceptually one-shot tools i.e. they assume to terminate fairly soon. Now this is not an issue of concurrent or parallel execution but rather an issue of that termination assumption: I have a single-threaded program analyzing a program p1. The caches get filled with data from p1. Now without terminating and analyzing more programs p2,p3,... (think of the program as a GUI tool) the caches basically grow with each program p2,p3,...: For instance, I do think this is the case for the Atom cache and any other cache that is used to achieve by-reference comparison. Is there something that could be done about that? I can not re-set private static variables.

Stack overflow in AbstractNestedJarFileModule's Warning.getMsg()

I just encountered the following:

java.lang.StackOverflowError: null
at com.ibm.wala.util.warnings.Warning.toString(Warning.java:80)
at com.ibm.wala.classLoader.AbstractNestedJarFileModule$1.getMsg(AbstractNestedJarFileModule.java:79)
at com.ibm.wala.util.warnings.Warning.toString(Warning.java:82)
at com.ibm.wala.classLoader.AbstractNestedJarFileModule$1.getMsg(AbstractNestedJarFileModule.java:79)
at com.ibm.wala.util.warnings.Warning.toString(Warning.java:82)
at com.ibm.wala.classLoader.AbstractNestedJarFileModule$1.getMsg(AbstractNestedJarFileModule.java:79)
at com.ibm.wala.util.warnings.Warning.toString(Warning.java:82)
at com.ibm.wala.classLoader.AbstractNestedJarFileModule$1.getMsg(AbstractNestedJarFileModule.java:79)
at com.ibm.wala.util.warnings.Warning.toString(Warning.java:82)

Looking at the code, it seems rather obvious what the problem is.

ReferenceCleanser must die

We need to replace the current combination of SoftReferences + ReferenceCleanser with a new caching mechanism with a reasonable default and easy tuning from client code. See #6 for some relevant discussion, along with this older mailing list thread:

https://groups.google.com/forum/#!searchin/wala-sourceforge-net/soft%2420reference/wala-sourceforge-net/QsoG_pF7ehc/R4w4S7ZQB54J

Periodic cache wipe problem

The SSA cache is intended to be implemented with soft references but, in the current implementation, it is wiped clean directly from time to time, bypassing the GC:

  /**
   * For some reason (either a bug in our code that defeats soft references, or a bad policy in the GC), leaving soft reference
   * caches to clear themselves out doesn't work. Help it out.
   * 
   * It's unfortunate that this method exits.
   */
  protected void tendToSoftCaches() {
    wipeCount++;
    if (wipeCount > WIPE_SOFT_CACHE_INTERVAL) {
      wipeCount = 0;
      ReferenceCleanser.clearSoftCaches();
    }
  }

The problem is that wiping caches periodically creates new SSAInstructions and SSA
instructions are compared using reference identity. So, subsequent cgNode.getIR() invocations on the same node may return IRs with SSAInstructions that cannot be compared for equality - which is very confusing.

Here is a test revealing the problem: cos/WALA@0972358

The best thing would be to find out why CG doesn't clear the soft references. Still, in the meantime, it might be good to either:

• document that distinct getIR() may return IRs with non-comparable SSA instructions
• make the SSAInstruction equal based on something else, e.g., IR.instructions index
• set PERIODIC_WIPE_SOFT_CACHES = false; by default ( cos/WALA@9ad9e45 ) and document that turning it on may be problematic.

Compile all WALA projects against Java 6

Some projects like wala.core still compile against a Java 1.5 target. Java 6 has been out since the end of 2006, so I think we're safe to update.

DefaultSourceExtractor inheritance chain broken

In package com.ibm.wala.cast.js.html, DefaultSourceExtractor.java, line 29: the member class HtmlCallBack was set to private.

Because most of DefaultSourceExtractor's job is done by this member class, setting it to private basically made DefaultSourceExtractor unextendable.

Since many methods in HtmlCallBack are in protected scope, it seems the author meant to allow inheritance but mistakenly set the class itself to private.

The similar extendability issue goes for IGeneratorCallback interface in DomLessSourceExtractor class. The HtmlCallBack who implements this interface is correctly set to protected but the interface itself was left in package scope, making extension difficult without rewriting large part of the classes.

It would be more reasonable if both DefaultSourceExtractor.HtmlCallBack and DomLessSourceExtractor.IGeneratorCallback are set to protected.

Fix source file tests when run under Maven

We currently disable 4 tests when running under Maven:

• CallGraphTest.testHello()
• CallGraphTest.testHelloAllEntrypoints()
• com.ibm.wala.core.tests.cha.SourceMapTest.testFromJar()
• com.ibm.wala.core.tests.cha.SourceMapTest.testHello()

The reason is that these tests assume that they are reading files from the filesystem, not a jar. We should fix things so that either (1) they can read the files from the filesystem when running under Maven or (2) they work when reading files from a jar. (1) seems easier.

Inconsistency in published Sonatype artifacts

The util artifact was updated yesterday, but core and shrike have not been updated since November 2014. Tools that rely on both the core and util artifacts fail at runtime with errors like java.lang.NoClassDefFoundError: com/ibm/wala/util/collections/Filter because of the inconsistency between the artifacts.

make NodeDecorator generic

com.ibm.wala.viz.NodeDecorator should be a generic type, parameterized by a node type T.

make maven builds reproducible

Doing a mvn clean should delete all files which have been downloaded or created during other maven builds. This would enable reproducible builds and uncover nasty errors which only occur if these files are not present.

Test failing on Windows 8 box (Test written in platform specific way)

I receive the following errors when running mvn clean verify on a Windows 8 box. It seems as if the test assumes a Linux box as /tmp is usually a valid path there i.e. the test is written in a platform specific way.

Results :

Tests in error:
  DynamicCallGraphTest.testExclusions:155->instrument:64 ╗ FileNotFound \tmp\tes...
  DynamicCallGraphTest.testGraph:147->instrument:64 ╗ FileNotFound \tmp\test.jar...

Tests run: 221, Failures: 0, Errors: 2, Skipped: 3

build.xml scripts failing on OS X with the Oracle JRE (i.e., Java 7)

The culprit is the special tag required for Apple's Java implementation. The fix is to simply remove this tag as the Oracle OS X JRE conforms to the standard one. Still, it will break the build for people that have not switched to the Java 7 JRE yet.

  <!-- This property has been updated to correspond to the paths used by the latest Java update
       on Mac OS X 10.6 (Java version 1.6.0_22).  If you are not using this version of Mac OS X or Java,
       try changing the value of the property to "${java.home}/../../../Classes" -->
  <condition property="dir_bootclasspath" value="${java.home}/../Classes">
    <os family="mac"/>
  </condition>
  <property name="dir_bootclasspath" value="${java.home}/lib"/>