compile.sh0000775000176100017620000000016413120354112011233 0ustar yueyueif [ ! -d "build" ]; then mkdir build fi javac $(find src -name "*.java") -d build jar -cvf mahjong.jar -C build . doop-mahjong.patch0000664000176100017620000007737213120354033012670 0ustar yueyuediff -urN doop-r160113-bin/logic/3-object-sensitive+2-heap/analysis.logic doop-mahjong/logic/3-object-sensitive+2-heap/analysis.logic --- doop-r160113-bin/logic/3-object-sensitive+2-heap/analysis.logic 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/logic/3-object-sensitive+2-heap/analysis.logic 2017-06-15 10:41:11.273935834 +1000 @@ -0,0 +1,105 @@ +/** + * @author Tian Tan + * @author Yue Li + */ + +#include "macros.logic" +#include "../context-sensitive.logic" +#include "../library.logic" + +// In this analysis, both the real context and the real heap context +// are triplets of HeapAllocationRefs. Keeping mapping +// functions is the way to handle analyses where HContext = Context +// (since the language considers them different types). +ContextFromRealContext[?heap1, ?heap2, ?heap3] = ?ctx -> + Context(?ctx), HeapAllocationRef(?heap1), HeapAllocationRef(?heap2), HeapAllocationRef(?heap3). +lang:skolem(`ContextFromRealContext). +RealContext1FromContext[?ctx] = ?heap -> + Context(?ctx), HeapAllocationRef(?heap). +RealContext2FromContext[?ctx] = ?heap -> + Context(?ctx), HeapAllocationRef(?heap). +RealContext3FromContext[?ctx] = ?heap -> + Context(?ctx), HeapAllocationRef(?heap). + +RealContext1FromContext[?ctx] = ?heap1, +RealContext2FromContext[?ctx] = ?heap2, +RealContext3FromContext[?ctx] = ?heap3 <- + ContextFromRealContext[?heap1, ?heap2, ?heap3] = ?ctx. + +HContextFromRealHContext[?heap1, ?heap2] = ?hctx -> + HContext(?hctx), HeapAllocationRef(?heap1), HeapAllocationRef(?heap2). +lang:skolem(`HContextFromRealHContext). + +RealHContext1FromHContext[?hctx] = ?heap -> + HContext(?hctx), HeapAllocationRef(?heap). +RealHContext2FromHContext[?hctx] = ?heap -> + HContext(?hctx), HeapAllocationRef(?heap). + +RealHContext1FromHContext[?hctx] = ?heap1, +RealHContext2FromHContext[?hctx] = ?heap2<- + HContextFromRealHContext[?heap1, ?heap2] = ?hctx. + +// Creating special immutable heap allocation constant +ImmutableHeapValue[] = ?immHeap <- + HeapAllocationValue(?immHeap, "<>"). + + +// Create initial objects with their heapcontexts. +HContextFromRealHContext[?heap1, ?heap2] = ?hctx, +HContext(?hctx), +SystemThreadGroup(?hctx, ?alloc) <- + MySystemThreadGroup(?heap1, ?heap2, ?alloc). + +HContextFromRealHContext[?heap1, ?heap2] = ?hctx, +HContext(?hctx), +MainThreadGroup(?hctx, ?alloc) <- + MyMainThreadGroup(?heap1, ?heap2, ?alloc). + +HContextFromRealHContext[?heap1, ?heap2] = ?hctx, +HContext(?hctx), +MainThread(?hctx, ?alloc) <- + MyMainThread(?heap1, ?heap2, ?alloc). + +/** + * Merge optimization hack + */ + +// For this analysis, we only need two of the parameters that may +// influence the new context object. +MyMergeBasis(?hctx, ?heap) <- + MergeBasis(_, _, ?hctx, ?heap). + +// We create new context objects sparingly, because of the high cost. +// We also cache them, so they can be looked up without a join. +Context(?calleeCtx), +ContextFromRealContext[RealHContext1FromHContext[?hctx], + RealHContext2FromHContext[?hctx], + ?heap] = ?calleeCtx, +OptimizeMerge[?hctx, ?heap] = ?calleeCtx <- + MyMergeBasis(?hctx, ?heap). + + +/** + * Reachable + */ +ReachableContext(?ctx, ?method), +ContextFromRealContext[?initheap, ?initheap, ?initheap] = ?ctx, +Context(?ctx) + <- + MainMethodDeclaration(?method), + HeapAllocationValue(?initheap, "<>"). + +ReachableContext(?ctx, ?method), +ContextFromRealContext[?startupheap, ?startupheap, ?startupheap] = ?ctx, +Context(?ctx) + <- + ImplicitReachable(?method), + HeapAllocationValue(?startupheap, "<>"). + +ReachableContext(?ctx, ?clinit), +ContextFromRealContext[?clinitheap, ?clinitheap, ?clinitheap] = ?ctx, +Context(?ctx) + <- + InitializedClass(?class), + ClassInitializer[?class] = ?clinit, + HeapAllocationValue(?clinitheap, "<>"). diff -urN doop-r160113-bin/logic/3-object-sensitive+2-heap/declarations.logic doop-mahjong/logic/3-object-sensitive+2-heap/declarations.logic --- doop-r160113-bin/logic/3-object-sensitive+2-heap/declarations.logic 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/logic/3-object-sensitive+2-heap/declarations.logic 2017-06-15 10:41:11.357936251 +1000 @@ -0,0 +1,16 @@ +#include "macros.logic" +#include "../context-sensitive-declarations.logic" + +// For this analysis, contexts are triplets of heap objects, so this is +// what the initial system objects should have. +MySystemThreadGroup(?heap1, ?heap2, ?alloc) -> + HeapAllocationRef(?heap1), HeapAllocationRef(?heap2), + HeapAllocationRef(?alloc). + +MyMainThreadGroup(?heap1, ?heap2, ?alloc) -> + HeapAllocationRef(?heap1), HeapAllocationRef(?heap2), + HeapAllocationRef(?alloc). + +MyMainThread(?heap1, ?heap2, ?alloc) -> + HeapAllocationRef(?heap1), HeapAllocationRef(?heap2), + HeapAllocationRef(?alloc). diff -urN doop-r160113-bin/logic/3-object-sensitive+2-heap/delta.logic doop-mahjong/logic/3-object-sensitive+2-heap/delta.logic --- doop-r160113-bin/logic/3-object-sensitive+2-heap/delta.logic 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/logic/3-object-sensitive+2-heap/delta.logic 2017-06-15 10:41:11.421936568 +1000 @@ -0,0 +1,29 @@ +#include "macros.logic" +#include "../library/common-delta.logic" + +/** + * Special calling contexts + * + * Note: the type is necessary (java.lang.String), but never used. It + * could be anything. It also needs to be an existing type, otherwise + * the sanity checks will barf. + */ +PlusHeapAllocationRef(?heap, "<>", "java.lang.String"). +PlusHeapAllocationRef(?heap, "<>", "java.lang.String"). +PlusHeapAllocationRef(?heap, "<>", "java.lang.String"). +PlusHeapAllocationRef(?heap, "<>", "java.lang.String"). + +/** + * Special objects + */ ++MySystemThreadGroup(?heap, ?heap, ?alloc), + PlusHeapAllocationRef(?heap, "<>", "java.lang.String"), + PlusHeapAllocationRef(?alloc, "<>", "java.lang.ThreadGroup"). + ++MyMainThreadGroup(?heap, ?heap, ?alloc), + PlusHeapAllocationRef(?heap, "<>", "java.lang.String"), + PlusHeapAllocationRef(?alloc, "<>", "java.lang.ThreadGroup"). + ++MyMainThread(?heap, ?heap, ?alloc), + PlusHeapAllocationRef(?heap, "<>", "java.lang.String"), + PlusHeapAllocationRef(?alloc, "<>", "java.lang.Thread"). diff -urN doop-r160113-bin/logic/3-object-sensitive+2-heap/macros.logic doop-mahjong/logic/3-object-sensitive+2-heap/macros.logic --- doop-r160113-bin/logic/3-object-sensitive+2-heap/macros.logic 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/logic/3-object-sensitive+2-heap/macros.logic 2017-06-15 10:41:11.525937084 +1000 @@ -0,0 +1,69 @@ +#include "../library/fact-macros.logic" + +// For this analysis, every heap context recorded on allocation +// corresponds to the calling context of the allocator method. +// Subtle point: this may need to be created because even though it +// exists as a Context it may not exist as an HContext. +#define RecordMacro(ctx, heap, hctx) \ + HContext(hctx), \ + HContextFromRealHContext[RealContext2FromContext[ctx], \ + RealContext3FromContext[ctx]] = hctx + +#define RecordImmutableMacro(ctx, heap, immCtx) \ + HContext(immCtx), \ + HContextFromRealHContext[ImmutableHeapValue[], ImmutableHeapValue[]] = immCtx + + +// For this analysis the context of a method call corresponds to the +// identity of the receiver object, that of the receiver object of +// the caller and so on. Again, this may trigger creation of +// a new object. +#define MergeMacro(callerCtx, invocation, hctx, heap, calleeCtx) \ + Context(calleeCtx), \ + ContextFromRealContext[RealHContext1FromHContext[hctx], \ + RealHContext2FromHContext[hctx], \ + heap] = calleeCtx + +#define MergeBasisMacro(callerCtx, invocation, hctx, heap) \ + MergeBasis(callerCtx, invocation, hctx, heap) + +#define OptimizeMergeMacro(callerCtx, invocation, hctx, heap, calleeCtx) \ + OptimizeMerge[hctx, heap] = calleeCtx + +// For this analysis, static calls just keep the same context as the +// caller. *Not* creating a new one, but pretending to, nonetheless, +// so the engine doesn't barf. +#define MergeStaticMacro(callerCtx, invocation, calleeCtx) \ + Context(calleeCtx), \ + ContextFromRealContext[RealContext1FromContext[callerCtx], \ + RealContext2FromContext[callerCtx], \ + RealContext3FromContext[callerCtx]] = calleeCtx + +// MergeThreadStart, MergeStartup, and MergeFinalizerRegisterContext +// have the same logic as plain Merge for this analysis. +#define MergeThreadStartMacro(hctx, heap, callerCtx, newCtx) \ + Context(newCtx), \ + ContextFromRealContext[RealHContext1FromHContext[hctx], \ + RealHContext2FromHContext[hctx], \ + heap] = newCtx + +#define MergeStartupMacro(hctx, heap, calleeCtx) \ + Context(calleeCtx), \ + ContextFromRealContext[RealHContext1FromHContext[hctx], \ + RealHContext2FromHContext[hctx], \ + heap] = calleeCtx + +// This is exactly equivalent to the regular merge logic, but written +// differently. At finalization, we create a new hctx, based on the +// callerCtx, and then use this new hctx as we would in regular Merge. +// The macro below does this, without referring to the new hctx (i.e., +// using knowledge of how it is created). This is necessary because since +// the new hctx is created in the same rule, it will not yet have values +// for its inverse functions (RealHContextFromHContext), so the rule will never +// fire if done naively. The signature of the macro (which does not accept a +// hctx) is a hint for avoiding this problem. +#define MergeFinalizerRegisterContextMacro(callerCtx, inmethod, heap, newCtx) \ + Context(newCtx), \ + ContextFromRealContext[RealContext2FromContext[callerCtx], \ + RealContext3FromContext[callerCtx], \ + heap] = newCtx diff -urN doop-r160113-bin/logic/library/fact-declarations.logic doop-mahjong/logic/library/fact-declarations.logic --- doop-r160113-bin/logic/library/fact-declarations.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library/fact-declarations.logic 2017-06-15 10:41:15.545957018 +1000 @@ -489,3 +489,33 @@ MethodInvocationRef(?invocation), VarRef(?to), VarRef(?field). + + +MahjongHeapAbstraction[?heap] = ?mergedHeap -> + HeapAllocationRef(?heap), + HeapAllocationRef(?mergedHeap). + + +ClassForName:Log(?invocation, ?type) -> + MethodInvocationRef(?invocation), + Type(?type). + +ClassNewInstance:Log(?invocation, ?type) -> + MethodInvocationRef(?invocation), + Type(?type). + +ConstructorNewInstance:Log(?invocation, ?constructor) -> + MethodInvocationRef(?invocation), + MethodSignatureRef(?constructor). + +MethodInvoke:Log(?invocation, ?method) -> + MethodInvocationRef(?invocation), + MethodSignatureRef(?method). + +FieldGet:Log(?invocation, ?field) -> + MethodInvocationRef(?invocation), + FieldSignatureRef(?field). + +FieldSet:Log(?invocation, ?field) -> + MethodInvocationRef(?invocation), + FieldSignatureRef(?field). diff -urN doop-r160113-bin/logic/library/mahjong.logic doop-mahjong/logic/library/mahjong.logic --- doop-r160113-bin/logic/library/mahjong.logic 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/logic/library/mahjong.logic 2017-06-15 10:41:15.937958962 +1000 @@ -0,0 +1,17 @@ +/** + * Mahjong heap abstraction. + * + * @author Tian Tan + * @author Yue Li + */ + +HeapAllocation:Merge[?heap] = ?mergedHeap <- + ObjectToBeMerged(?heap), + MahjongHeapAbstraction[?heap] = ?mergedHeap. + +ObjectToBeMerged(?heap) <- + MahjongHeapAbstraction[?heap] = ?mergedHeap, + NumberOfObjectsMergedTo[?mergedHeap] > 1. + +NumberOfObjectsMergedTo[?mergedHeap] = n <- + agg<> MahjongHeapAbstraction[_] = ?mergedHeap. diff -urN doop-r160113-bin/logic/library/reflection.logic doop-mahjong/logic/library/reflection.logic --- doop-r160113-bin/logic/library/reflection.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library/reflection.logic 2017-06-15 10:41:16.781963147 +1000 @@ -112,6 +112,7 @@ ReachableContext(?ctx, ?inmethod), Config:DynamicClass(?type, ?invocation). +#ifndef ENABLE_REFLECTION_LOG /** * Class.forName invocations with string constant parameters */ @@ -124,6 +125,8 @@ java:lang:Class:forName:ActualParam[?invocation] = ?param, VarPointsTo(_, ?constant, ?ctx, ?param), // recursive ClassNameStringConstant:Type[?constant] = ?type. +#endif // #ifndef ENABLE_REFLECTION_LOG + java:lang:Class:forName:ActualParam[?invocation] = ?param -> MethodInvocationRef(?invocation), @@ -161,6 +164,8 @@ AssignReturnValue[?invocation] = ?to, VirtualMethodInvocation:Base[?invocation] = ?from. + +#ifndef ENABLE_REFLECTION_LOG /** * evaluate */ @@ -184,6 +189,8 @@ ReifiedMethod[?signature] = ?heap, ObjectShouldBeRefined(?heap). #endif +#endif // #ifndef ENABLE_REFLECTION_LOG + /************************************************************* * Class.getConstructors @@ -221,6 +228,7 @@ AssignReturnValue[?invocation] = ?to, VirtualMethodInvocation:Base[?invocation] = ?from. +#ifndef ENABLE_REFLECTION_LOG /** * evaluate */ @@ -265,6 +273,8 @@ ReifiedConstructor[?signature] = ?heap, ObjectShouldBeRefined(?heap). #endif +#endif // #ifndef ENABLE_REFLECTION_LOG + /************************************************************* * Method.invoke @@ -293,10 +303,18 @@ VirtualMethodInvocation:Signature[?invocation] = ?invoke, VirtualMethodInvocation:Base[?invocation] = ?base. +#ifdef ENABLE_REFLECTION_LOG +ReflectiveMethodInvocation(?ctx, ?instruction, ?signature) <- + java:lang:reflect:Method:invoke(?instruction, _), + MethodInvoke:Log(?instruction, ?signature), + VirtualMethodInvocation:In(?instruction, ?inmethod), + ReachableContext(?ctx, ?inmethod). +#else ReflectiveMethodInvocation(?ctx, ?instruction, ?signature) <- java:lang:reflect:Method:invoke(?instruction, ?from), VarPointsTo(_, ?method, ?ctx, ?from), // recursive ReifiedMethod[?signature] = ?method. +#endif ReflectiveBaseVar[?invocation] = ?base <- java:lang:reflect:Method:invoke(?invocation, _), @@ -340,12 +358,22 @@ * *************************************************************/ +#ifdef ENABLE_REFLECTION_LOG +ReflectiveAssignHeapAllocation(?invocation, ?type, ?ctx, ?to), +ReflectiveSpecialMethodInvocation(?ctx, ?invocation, ?signature) <- + java:lang:reflect:Constructor:newInstance(?invocation, ?to, _), + ConstructorNewInstance:Log(?invocation, ?signature), + VirtualMethodInvocation:In(?invocation, ?inmethod), + ReachableContext(?ctx, ?inmethod), + MethodSignature:Type[?signature] = ?type. +#else ReflectiveAssignHeapAllocation(?invocation, ?type, ?ctx, ?to), ReflectiveSpecialMethodInvocation(?ctx, ?invocation, ?signature) <- java:lang:reflect:Constructor:newInstance(?invocation, ?to, ?base), VarPointsTo(_, ?constructor, ?ctx, ?base), // recursive ReifiedConstructor[?signature] = ?constructor, MethodSignature:Type[?signature] = ?type. +#endif ReflectiveBaseVar[?invocation] = ?to <- java:lang:reflect:Constructor:newInstance(?invocation, ?to, _). @@ -403,13 +431,25 @@ MethodDescriptorRef:Value(?descriptor:"void()"), SimpleNameRef:Value(?simplename:""). +#ifdef ENABLE_REFLECTION_LOG +ReflectiveAssignHeapAllocation(?invocation, ?type, ?ctx, ?to), +ReflectiveSpecialMethodInvocation(?ctx, ?invocation, ?constructor) + <- + java:lang:Class:newInstance(?invocation, ?to, _), + ClassNewInstance:Log(?invocation, ?type), + ReifiedClass[?type] = ?class, + VirtualMethodInvocation:In(?invocation, ?inmethod), + ReachableContext(?ctx, ?inmethod), + OptClassToConstructor(?constructor, ?class). +#else ReflectiveAssignHeapAllocation(?invocation, ?type, ?ctx, ?to), ReflectiveSpecialMethodInvocation(?ctx, ?invocation, ?constructor) <- java:lang:Class:newInstance(?invocation, ?to, ?var), VarPointsTo(_, ?class, ?ctx, ?var), - OptClassToConstructor(?constructor, ?class), - MethodSignature:Type[?constructor] = ?type. + MethodSignature:Type[?constructor] = ?type, + OptClassToConstructor(?constructor, ?class). +#endif ReflectiveBaseVar[?invocation] = ?to <- java:lang:Class:newInstance(?invocation, ?to, _). @@ -450,6 +490,7 @@ AssignReturnValue[?invocation] = ?to, VirtualMethodInvocation:Base[?invocation] = ?from. +#ifndef ENABLE_REFLECTION_LOG /** * evaluate */ @@ -472,6 +513,8 @@ ReifiedField[?signature] = ?heap, ObjectShouldBeRefined(?heap). #endif +#endif // #ifndef ENABLE_REFLECTION_LOG + /************************************************************* * Field.get @@ -514,10 +557,18 @@ FieldSignatureRef(?signature), Context(?ctx), VarRef(?to). +#ifdef ENABLE_REFLECTION_LOG +ReflectiveLoadField(?invocation, ?ctx, ?to, ?signature) <- + java:lang:reflect:Field:get(?invocation, ?to, ?field), + FieldGet:Log(?invocation, ?signature), + VarPointsTo(_, _, ?ctx, ?field). +#else ReflectiveLoadField(?invocation, ?ctx, ?to, ?signature) <- java:lang:reflect:Field:get(?invocation, ?to, ?field), VarPointsTo(_, ?fieldHeap, ?ctx, ?field), ReifiedField[?signature] = ?fieldHeap. +#endif + /** * Load of static field. @@ -596,11 +647,19 @@ FieldSignatureRef(?signature), Context(?ctx), VarRef(?var). +#ifdef ENABLE_REFLECTION_LOG +ReflectiveStoreField(?invocation, ?signature, ?ctx, ?from) <- + java:lang:reflect:Field:set(?invocation, ?fieldVar), + FieldSet:Log(?invocation, ?signature), + VarPointsTo(_, _, ?ctx, ?fieldVar), + java:lang:reflect:Field:set:from[?invocation] = ?from. +#else ReflectiveStoreField(?invocation, ?signature, ?ctx, ?from) <- java:lang:reflect:Field:set(?invocation, ?fieldVar), VarPointsTo(_, ?fieldHeap, ?ctx, ?fieldVar), ReifiedField[?signature] = ?fieldHeap, java:lang:reflect:Field:set:from[?invocation] = ?from. +#endif /** * Store of static field. diff -urN doop-r160113-bin/logic/library/reflective.logic doop-mahjong/logic/library/reflective.logic --- doop-r160113-bin/logic/library/reflective.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library/reflective.logic 2017-06-15 10:41:17.021964337 +1000 @@ -241,7 +241,11 @@ * to initialize classes separate from the VarPointsTo rule. */ InitializedClass(?type) <- +#ifdef ENABLE_REFLECTION_LOG + ClassForName:Log(_, ?type). +#else ReflectiveAssignClassConstant(_, _, ?type). +#endif /** * TODO This doesn't make any sense without a 'to' variable. @@ -263,12 +267,28 @@ Context(?callerCtx), VarRef(?base). /** - * TODO it's unfortunate this code is so similar to normal LoadArrayIndex. + * Original predicate name LoadHeapArrayIndex is replaced by ReflectiveLoadHeapArrayIndex. + * The original implementation causes many argument passing of reflective calls fail. */ -LoadHeapArrayIndex(?calleeCtx, ?to, ?basehctx, ?baseheap) <- +ReflectiveLoadHeapArrayIndex(?calleeCtx, ?to, ?basehctx, ?baseheap) -> + Context(?calleeCtx), + VarRef(?to), + HContext(?basehctx), + HeapAllocationRef(?baseheap). + +ReflectiveLoadHeapArrayIndex(?calleeCtx, ?to, ?basehctx, ?baseheap) <- ReflectiveLoadArrayIndex(?calleeCtx, ?to, ?callerCtx, ?base), VarPointsTo(?basehctx, ?baseheap, ?callerCtx, ?base). +// Use types of objects to filter reflective interprocedural assignments. +// Fix the reflective argument passing bug. +VarPointsTo(?hctx, ?heap, ?ctx, ?to) <- + ReflectiveLoadHeapArrayIndex(?ctx, ?to, ?basehctx, ?baseheap), + ArrayIndexPointsTo(?hctx, ?heap, ?basehctx, ?baseheap), + Var:Type[?to] = ?type, + HeapAllocation:Type[?heap] = ?heaptype, + AssignCompatible(?type, ?heaptype). + /************************************************************* * diff -urN doop-r160113-bin/logic/library/statistics-simple.logic doop-mahjong/logic/library/statistics-simple.logic --- doop-r160113-bin/logic/library/statistics-simple.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library/statistics-simple.logic 2017-06-15 10:41:17.245965448 +1000 @@ -58,6 +58,25 @@ Stats:Simple:ReachableVirtualMethodInvocation(?from), Stats:Simple:InsensCallGraphEdge(?from, ?to). +Stats:Simple:InsensAllCallGraphEdge(?from, ?to) -> + CallGraphEdgeSourceRef(?from), MethodSignatureRef(?to). +Stats:Simple:InsensAllCallGraphEdge(?from, ?to) <- + Stats:Simple:InsensCallGraphEdge(?from, ?to). +Stats:Simple:InsensAllCallGraphEdge(?from, ?to) <- + InsensReflectiveCallGraphEdge(?from, ?to). + +InsensReflectiveCallGraphEdge(?caller, ?callee) <- + ReflectiveCallGraphEdge(_, ?caller, _, ?callee). + +Stats:Simple:AllCallGraphEdge(?callerctx, ?caller, ?calleectx,?callee) -> + Context(?callerctx), CallGraphEdgeSourceRef(?caller), + Context(?calleectx), MethodSignatureRef(?callee). + +Stats:Simple:AllCallGraphEdge(?callerctx, ?caller, ?calleectx,?callee) <- + CallGraphEdge(?callerctx, ?caller, ?calleectx,?callee). +Stats:Simple:AllCallGraphEdge(?callerctx, ?caller, ?calleectx,?callee) <- + ReflectiveCallGraphEdge(?callerctx, ?caller, ?calleectx,?callee). + /*************************************************** * Application methods ***************************************************/ diff -urN doop-r160113-bin/logic/library/string-constants.logic doop-mahjong/logic/library/string-constants.logic --- doop-r160113-bin/logic/library/string-constants.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library/string-constants.logic 2017-06-15 10:41:17.789968146 +1000 @@ -46,9 +46,16 @@ AssignHeapAllocation(?heap, ?var, ?inmethod), HeapAllocation:Merge[?heap] = ?mergeHeap. +#ifdef ENABLE_MAHJONG AssignContextInsensitiveHeapAllocation(?heap, ?var, ?inmethod) <- AssignHeapAllocation(?heap, ?var, ?inmethod), + ! ObjectToBeMerged(?heap), HeapAllocation:ContextInsensitive(?heap). +#else +AssignContextInsensitiveHeapAllocation(?heap, ?var, ?inmethod) <- + AssignHeapAllocation(?heap, ?var, ?inmethod), + HeapAllocation:ContextInsensitive(?heap). +#endif /************************************************************* * String constants diff -urN doop-r160113-bin/logic/library.logic doop-mahjong/logic/library.logic --- doop-r160113-bin/logic/library.logic 2013-01-16 07:31:46.000000000 +1100 +++ doop-mahjong/logic/library.logic 2017-06-15 10:41:18.193970149 +1000 @@ -45,6 +45,10 @@ #include "client/client-extensions-catalogue.logic" #endif +#ifdef ENABLE_MAHJONG +#include "library/mahjong.logic" +#endif + /** * Declaring class */ diff -urN doop-r160113-bin/mahjong.py doop-mahjong/mahjong.py --- doop-r160113-bin/mahjong.py 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/mahjong.py 2017-06-15 10:41:23.933998612 +1000 @@ -0,0 +1,42 @@ +#!/usr/bin/python + +__author__ = "Tian Tan and Yue Li" + +import os, sys + +MAHJONG_CP = 'mahjong.jar' +MAHJONG_OPT = '-mahjong' +MAHJONG_OUTPUT = 'MahjongHeapAbstraction.facts' + +def splitArgs(args): + analysis = args[0] + outDir = args[1] + ptaArgs = args[2:] + i = ptaArgs.index(analysis) + opts = [opt for opt in ptaArgs[:i] if opt != MAHJONG_OPT] + jars = ptaArgs[i+1:] + argMap = { 'outDir':outDir, 'opts':opts, 'jars':jars } + return argMap + +def runCIPTA(argMap): + print + print 'Running pre-analysis (context-insensitive analysis) ...' + cmd = './run %s context-insensitive %s' % (' '.join(argMap['opts']), ' '.join(argMap['jars'])) + os.system(cmd) + +def runMahjong(argMap): + print + print 'Running Mahjong ...' + cmd = 'java -cp %s mahjong.main.DoopMain ' % MAHJONG_CP +\ + '-db last-analysis -out %s' % argMap['outDir'] + os.system(cmd) + +def run(args): + argMap = splitArgs(args) + mahjongOutput = os.path.join(argMap['outDir'], MAHJONG_OUTPUT) + if not os.path.isfile(mahjongOutput): + runCIPTA(argMap) + runMahjong(argMap) + +if __name__ == '__main__': + run(sys.argv[1:]) diff -urN doop-r160113-bin/reflection.py doop-mahjong/reflection.py --- doop-r160113-bin/reflection.py 1970-01-01 10:00:00.000000000 +1000 +++ doop-mahjong/reflection.py 2017-06-15 10:41:24.181999842 +1000 @@ -0,0 +1,80 @@ +#!/usr/bin/python + +__author__ = "Tian Tan and Yue Li" + +import os, sys +import re + +INVOCATIONREF = 'MethodInvocationRef.facts' +PATTERN = re.compile('<(?P[^:]+): \S+ (?P[^(]+).*') +REFCALL = { + 'Class.forName':'java.lang.Class.forName', + 'Class.newInstance':'java.lang.Class.newInstance', + 'Constructor.newInstance':'java.lang.reflect.Constructor.newInstance', + 'Field.get*':'java.lang.reflect.Field.get', + 'Field.set*':'java.lang.reflect.Field.set', + 'Method.invoke':'java.lang.reflect.Method.invoke', +} + +def convertToDotFormat(caller): + if caller.startswith('<'): + match = PATTERN.match(caller) + d = match.groupdict() + return '%s.%s' % (d['clsName'], d['methName']) + else: + return caller + +def isPotentialCall(call, caller, invo): + invoCaller, invoCallee, _ = invo.split('/') + return caller == convertToDotFormat(invoCaller) and \ + REFCALL[call] == invoCallee + +def findInvocations(call, caller, invos): + return [invo for invo in invos if isPotentialCall(call, caller, invo)] + +def filterReflectiveInvocation(invos): + refInvos = set() + for invo in invos: + for _, call in REFCALL.items(): + if call in invo and \ + 'java.lang.Class.newInstance0' not in invo: # skip wrapper call + refInvos.add(invo.strip()) + return refInvos + +def convertReflectionLog(refLog, factsDir, outDir): + flog = open(refLog) + + finvo = open(os.path.join(factsDir, INVOCATIONREF)) + refInvos = filterReflectiveInvocation(finvo.readlines()) + finvo.close() + + outputDict = { + 'Class.forName':open(os.path.join(outDir, 'ClassForName.log'), 'w'), + 'Class.newInstance':open(os.path.join(outDir, 'ClassNewInstance.log'), 'w'), + 'Constructor.newInstance':open(os.path.join(outDir, 'ConstructorNewInstance.log'), 'w'), + 'Field.get*':open(os.path.join(outDir, 'FieldGet.log'), 'w'), + 'Field.set*':open(os.path.join(outDir, 'FieldSet.log'), 'w'), + 'Method.invoke':open(os.path.join(outDir, 'MethodInvoke.log'), 'w'), + } + for line in flog: + call, target, caller, _, _, _ = line.split(';') + # skip generated accessors + if 'GeneratedConstructorAccessor' in target or \ + 'GeneratedMethodAccessor' in target: + continue + # skip non side-effect calls + if call not in outputDict.keys(): + continue + output = outputDict[call] + for invo in findInvocations(call, caller, refInvos): + output.write('%s\t%s\n' % (invo, target)) + flog.close() + for _, output in outputDict.items(): + output.close() + +def run(args): + [refLog, factsDir, outDir] = args + convertReflectionLog(refLog, factsDir, outDir) + +if __name__ == '__main__': + run(sys.argv[1:]) diff -urN doop-r160113-bin/run doop-mahjong/run --- doop-r160113-bin/run 2013-01-16 07:38:09.000000000 +1100 +++ doop-mahjong/run 2017-06-15 10:41:24.562001726 +1000 @@ -147,6 +147,7 @@ CPPFLAGS_FIELD_BASED_STATIC="" CPPFLAGS_FIELD_BASED_DYNAMIC="" CPPFLAGS_EXCEPTIONS_EXPERIMENTAL="" +CPPFLAGS_MAHJONG="" cache="false" logMemStats="false" sanity="false" @@ -166,6 +167,8 @@ singleRun="false" noColour="false" # skolemGraph="false" +mahjong="" +refllog="" originalCommandLine="$*" @@ -334,6 +337,17 @@ phantom="true" shift 1 ;; + "-refl-log") + shift 1 + refllog="${refllog} $1" + shift 1 + CPPFLAGS_REFLECTION="-DENABLE_REFLECTION_LOG" + ;; + "-mahjong") + mahjong="true" + CPPFLAGS_MAHJONG="-DENABLE_MAHJONG" + shift 1 + ;; *) echo "invalid option: $1" usage @@ -382,7 +396,7 @@ ;; esac -CPPFLAGS="${CPPFLAGS_EXCEPTIONS} ${CPPFLAGS_EXCEPTIONS_EXPERIMENTAL} ${CPPFLAGS_PADDLE_COMPAT} ${CPPFLAGS_CLIENT_ANALYSES} ${CPPFLAGS_JRE} ${CPPFLAGS_OS} ${CPPFLAGS_STRING_CONSTANTS} ${CPPFLAGS_STRING_BUFFERS} ${CPPFLAGS_CONTEXT} ${CPPFLAGS_REFLECTION} ${CPPFLAGS_FIELD_BASED_STATIC} ${CPPFLAGS_FIELD_BASED_DYNAMIC}" +CPPFLAGS="${CPPFLAGS_EXCEPTIONS} ${CPPFLAGS_EXCEPTIONS_EXPERIMENTAL} ${CPPFLAGS_PADDLE_COMPAT} ${CPPFLAGS_CLIENT_ANALYSES} ${CPPFLAGS_JRE} ${CPPFLAGS_OS} ${CPPFLAGS_STRING_CONSTANTS} ${CPPFLAGS_STRING_BUFFERS} ${CPPFLAGS_CONTEXT} ${CPPFLAGS_REFLECTION} ${CPPFLAGS_FIELD_BASED_STATIC} ${CPPFLAGS_FIELD_BASED_DYNAMIC} ${CPPFLAGS_MAHJONG}" # Requires DOOP_HOME environment variable to be set if [ ! "x$clientcode" = "x" ]; then @@ -668,6 +682,87 @@ # timing $bloxbatch -db $database -addBlock -file tmp/spanning.logic # fi + # Read Mahjong heap abstraction + #if [ ! "x$mahjong" = "x" ]; then + if test "$mahjong" = "true"; then + #printf "loading ${C_YELLOW}Mahjong heap abstraction${C_RESET} from %s ...\n" $mahjong + echo "loading Mahjong heap abstraction ... " + cat > tmp/mahjong.import < tmp/classforname.import < tmp/classnewinstance.import < tmp/constructornewinstance.import < tmp/fieldget.import < tmp/fieldset.import < tmp/methodinvoke.import <^.f.vnvF6̼;Ff 0FTF~̼TܤԢĤWp~iQr[&㖙X _PeddCLƢt0!P?dd|V @ , $94'PK bPKXJmahjong/pta/Type.class;o>^.f.vnvF6̼;Ff 0FTF~̼TܤԢĤWp~iQr[&RYX _Pdd dCŢt0!P;dd|V @ , $94'PK3"%PKXJmahjong/pta/Obj.classMOn@B("nҁ BPp2gs|BD;3] GNj7ӹ6hp^ t:W*TQJƏYʌYo4^$SpmJӇau5dF!XUSڎkNiE 7P1iŞQs l7j@ qb›;vM鮶khPK'PKXJmahjong/pta/PTAProvider.classN @-ԂN yK7#"AAl,ס裢Ưw\ofl U+wZ֩k4Җ IZOBo!WCP&: ?PKւPKXJmahjong/pta/doop/Options.classuTSg- ͺ(  C( Z6m"j& ntLcq)3Rgz9gDCs;s&Ty̆!c<,n\%= |ɗ ; X/+Xa.5Xߗ.お+,6U`+P7 UJP>";=UBj͵ 0%!sۢe UqwpER m 4ܛ^B©aJ)+{zHpAaߤqHO55;9]Ca!qPɲ|\u޹ͺ)}TO09˺T|ˇDoXd(z*oYr5,ӡ :\=^mf|+Rgbpy)!hGx<=Ѓ MB ]"&!%$\f@AM7H+^ yNQ  kvY>6C6CG B7CHNC7C_"\5CI^5C_&$Yt^4җ3 0&1U8Y< oC5kPFW"'GRV3vuNVaT%v}Tq]]H*b8it&[Y/l }YTwk䅷\H^B}ANSoV191 *Œj`Kp.6!I@T;[<6`2wg9ޙ;w_l# Ű!MCؒW2^+x ,{I;2>0YЬt۶f33GY1-wPk&)w0 q8q,ݨ$Ӧa;pNy ӹsjD4ֈgnF1fngV+;;\GSYtC8/jVk6[Oa,7)tW 4,= /*:({:ED6H1@S7O8FDq{DTʵT6P9h\YxKWV\BoD8AIz0(4I͐w HL.U*Y[~, &L^S;y׼AD,YI&h+P P$TxLv >Z ?%HPK\DPKXJ!mahjong/pta/doop/ObjManager.classUSW<@NS1Mc!/"mZiEIQbMI$x).WL1NN u>}* Ux>TbI)|4U- `_{ RYSucPiw_Hئ aв!L7}[a1(+5[Hfێ%Ϟ7*mF%ݫY%;Z,W ʦHǑ.bd_ ^eZsH|,d!zQXX#ZEu^g{/"(j^,!~,1LDJӛmwکpuSc}]iQp9KS·4|YMެUjw>-]|`Oc ~$c["+Mɤ\~pw$쩆g $0_f1jtި{}K%]ش C:z:md c{r4,T ae0nQuHeLݡ;އ}*6:VnvvvNFҢT̜TFǀ̔"IJDF~׼̼tԒv.FČtD>}4* A<91.\FLcһ6~'c^L*Mh(l*I&\`0 @(e'lٌ&g笐Ly9(3SWnku[qƿ1G;/Pll2Za[;9瞙wO#qO @, U 5 uGbň!y8 |6|ܠn87ܜS`XNelG?[? bDC>WSH`X WI/*}t.IS e@zV9PB@*Q&C dVRQOvw֦EЮ hXbIY8K&G)rשFT][ٷTU^ϥ-Tt4ErXٞwE>PKf $PKXJ mahjong/pta/doop/DoopField.classmPMO@} RJ୭=MEB҄xp/K%r%_:_MFs v9G]02Qxpj]7S>\/ixVH 84Pf; &)y6Bw-F8'gVюGg(}+H SҦ0M78krηucQu_!?mll36JöTzޒvroPK+PKXJ2mahjong/pta/doop/DoopPTAProvider$ObjIterator.classTYSA&lXP1` \95 jb ?TɥUʳ?ʲ'D n7_tϯ~[詠!*ŀJGX*q:,W# F%0&c DŽ &UzL)V0`A1W7⎰|GV" d-0Z2va/N^p#M:nc3xu2'6I-GLs+:CenkB3tKCoʦ5X \ _ЎE04rBm0tJ:q-ⶠlVP1+O Ֆ t%g!7Cś/~Sӹ6v>/F M8y}\͠0z\S.=.4|i]N=iHd9ه+|w8r2PNyh+ٖqz‘CB,Ns!orF(E:|^>PK^o!PKXJ#mahjong/pta/doop/FieldManager.classQ]KA=WW42|*?} zP|IQmEwe]PGEwELh`9;3N3cCG@&BȘmֱCVQ5BPl3/ ɨ+k2c|)l(9"q/pm|ǵ+H <&JX+o;=BخP{*U_]ҬU̖7{ FN8 Bvi:,v^ 1 ?ڟU F%DzUj2KޣQl##Xa<%21R9!rHZ0\zl1P\V9q<ǷB福މD_Osrf&N'mlwa^ߵapV8bn0i퇍aDIB3pAb}DwS_a>31L8i93|։;q[)9 UPˡ[UDѧ*?3ٺU\~QWM`:(-V]?.Uǘ**N GHE ܤLzD_!sjZ3+";}sW|deYۦ U\WMU@9LCp4aZ]h,!U 'rPU1q5U1^HLP U1QL6%(QC2Τ'F_ ND0d85$$mBPVdQ)Ҫ^'01 v3nfG ^:Z"ܾ]2U WS|T%8ήY,RS3ٶ=$Z-ūeeq~).ڌZ`G"F܈i6vqZǬ"Aէ٪#JUQ&rr\;CUGBZ|@u'V^_fnk;ѐ^F-I .&xֽY`]._p+WҵhC(k \Lcײcn,>P+_ifytnnogwh -hkHL2&Ji ׌HlטxiVP"odn,y9/V ~\rwO^Të gKnbr{ylrAc?qI*a QIE>s԰=a 59kJ+5TQCZ4mS ?—r=~,7)M^4/by'-.gb!@=>qœBLN/%4yP]0IB!LhK`2QPۤʪAL{)Űq\ZPDh i55 \> f}'GPL ,,N!2 |[I1og3czR\̴:!t[5i-(\礒KafUʌjwkZe\Cg756oIZBe|c߽m~ăcX)ˑ_ҰI*, 5KV b%$0!h /&tϷC ØG,'`']2hWwu(K㘬k\h;})v>ڷ^SW$s^A #m$=cUfiy$OPrrsڥt6'6'\[GT*CK7 ]e= .^,2MbX"2M^K?$ϏcPKu  PK XJ mahjong/fpg/PKXJ$mahjong/fpg/FieldPointstoGraph.classVkSg~6 PD/ LkTD&޵$v򹿡L-tOtՐdA07׿Op?щ ^øc皩7]#!m.ኌ2u1nɸF+hĻa]geĜj9 [򖹤5KB䢚7XQc3hHISB伺 My%9Cu &![~:\9=;?k5S0ѭIK-K 'nW$fZ1v8YIu6GIÜQ;һA>THǖeU)CBYpܨ錄*j/UKp֍0>f'^?Ƭj3E27~f9ԐքXd{&3I '635; RɩiwI9 '̂u1Zj>{HdRARV'T;b؋}2tX4f ”dʹX\eM8D^=lxPhiKPp1eZ*XR0*އx #!sUT+ 秙\:G uSBL-HFDzib{Xvcraˇ Kt/||TJ-,LH9iawc˘5-| >"3y9 %.h˼fN=~AU2 :`KM 鴄FvFB#tQ;խ|5 ʖuc\bnOԌbdbi'Gn4 lahV<ڶzxŎPtNkp,zjEV\.;ڐ$to*z|:çx!w~+=81BZcHѧ\_A1BeM1jV!K>`uPvQ$rqBhQ+vvuc+Y\uv?H04L* =^]ѮEؑ a_؏7= 2ޢrn_[rb=J&MZ0H]6gy)pʳ/nRYŶ z^ה?rIQ#XYcE)]<1B}+h.N-kpқz/m g'ˢ =-\>E+yn/tXŎ@5k;ھ̪Jg\[ %P3 IH6 !˗#p#p=)ϰ")eew {ؼNye2D7Roy~޵ u&1(HPKk PKXJ$mahjong/HeapAbstraction$DFAMap.classT[OA ]l *7^RAA[AE0}rXv) _hb|G,B[̜ssw.~` Π_1:nH #eII"AC6ňs긩cTǘ[ W|W5U锳3Ė˪/&[ u+يǥWI;;70Q}# 1WK-U:r'z4- EqţzIOxLV_H25S2ė$_SQ n" #9J= ̃@ i{ ㍫n'6X-EfX 9tnT8CM< eWC a”eNꇰ%D/~lhζJCЙ, O`jh95݉S5ݧimV U2SCZH U } ;DЮ FZ=H} yrH:әh]4.;з@#Ao[z&$wg=D $h_|ЪȌ'[!/8{?C j%*j?[/9(tfCvQ*?X/mĒzHC jPudX-PKB6tgPK XJ mahjong/main/PKXJmahjong/main/DoopMain.classX{X:|c`0D VjJ@\qNѝHLtt4i nҽt=ɖ, ƒn9KZ휂~7m*X?l9h>3e&)a9 /m83NYߢ5\쑩eO)8!81f/$LggCi]==3= !v#Pټ?hYLOX=+4Β[o<E$y߲#F6p;f({ o$Ʀ.Tz%Y9bf4fʧXrm7cZNLp=pLAw|Eh cZy!(ϥLzpkK:ѧS:>,>cT|^Eϙ̃35l̘ZuuuT|IǗ񴎯[1&:଎cX~qETMnC- :+H77-zy\5V oøV\4c0|LaxVA[\%A+t'!EăS{J9wD+sQpMb>Iwധx^ U,XWu,኎/%?Ry?:~,a:ܚA佘̚1öݔ!XU "̟̟*V%k=u}ˎև/K¯u/-zUwR$6/\ib2(QrNz*ZױBe9U٠%61qßemҫ>9f ެn 0LOe d(;JQlHs9Xmyg鬂=Wk"ߔr3l՝tò[+]nٴ5~vC_x6rZV3]@ZJK!5Ʀ!8Vd%M2$fx^b.P+r#>)AvRJ~1e*m]Mt6HՆgߜ?S"Gd F?+h2l—rNHϒw^>s:5zwU`(e:W"ޑQ#xO>s*ϖsٽd&!;77>Sک7vKy~q\mxiIۦ xW*ysחm>7)xC_XG |61(x]澧lQxΡ(sး'G1aݵº5%V@3h:(8",iM ?EF^@QGdѾ%h 5wIPKh PKXJmahjong/HeapAbstraction$1.class;o>nvvvNFҢT̜TFǤ⒢<IJDF~׼̼tԒv.FČt}4=* ̛7oxG%؀1 G |KNwf^r˯,j]Ap o,Žx7b"Zw#>Q\χ.)R)x~@N?C-> E >(g>>1P>ZD㤂OH?Y" JpFYCR9|އ|Ji}F]PYSy0dS\KwK6-!Pԓگ3z~7xf̰RyCRKE|=Zay-mYJ~=),(@:6u#;YՌ6=٫w X54+V]]?#A]"Ʃͦ5#H 'v֥-1CoOwɝZW3UQ?TG-h *%[U`RnS+*E.Ve|E p;72G$S><ܦHaT|B5_~LKhӭ>;U7xoAo T|W}?PCI5&*~*~is/U VV{yUIWW|SF >]/*G fbFj~x)USfWKdqlW/R!>6`iغ#۝ݡJZ,uRܛh} yS:9vewK2giܖh,T9LYHH -Sgm׆I-&6 kpn AZ0c)BYX< 1W =O1cܯ׷}#gwki"ƴ4W\̶>4;j2.^Gh-fTN6eLe<%x3M,؀ܨ-GյKv *o3-{~ \iý'|{r')$pU ܸ%X<, W-i wmuLEBu;r/e|*(;iS(K#fgQy3Pj_2C*p<Dž,#>s *Tc5c-MZuXu$2B#;]C`;J>u>$|s׹ɗ O؛o##Bi Oط8؏rJ;Aitja.#5C' aQ, ,\j jA5'm곸v%o(Cԍr2}&FF3Ġ&nۅp_v*-4\O$rbooUfHZCsX"Cԅpn~QT|B ]@(זdQr]AR ҹ-,dd 's 9D=& ( Յm&dC~-Bh g*fOHZfMn4Da7`@ຣT#]Pl_(Ԅ aZ3}+'_HW3zfi#F܊M$a3 wv֒#4k ์jqLgT`p / **XzBh Z1+'z "WthXܴ7q%F}1K\%f#Wٹƫ5x-^gF>N?PK(PO PK XJ mahjong/util/PKXJmahjong/util/UnionFindSet.classWSW$(*⻈I(À22qpdjJ{ԌevF(̋@:S]yG;ėI,Lj 1"~\i~C̫sLw!ν+,Lq"9-58ZbHX>R`9*,WQ*hؿ*DWT"-{WqMkWp]xÇ-=Q'8Si_p{ !fMn}mN^K|%ϧhTOpYgzWdtjeksz^y&MZ>-:-p_ԂsRL{J啰RVMT@nM[+3oF9AD}|3@їNn8$dVԋSֵ9f}rFq^!oxjD|q2ݟ@'ل[Iyٖk_!4ˊNT,e,mf:45V&JU-WmbÊSgCi;oH*Ï*pZE< 5 :6GmR3seͦc43S|$ipt>?de񵁵a-N~~8xXp[l v|x_FYp<D>\ p߅1x%J]E.nSY vT@5#$l诐Ij$HSWl!4[Sfka|Ųm>>swAUa:+z3"37Q1. wz!27|e~|.QO1<PK`%U PKXJmahjong/util/Numberable.class]OMK@l&U' ś""*m$m^xQGoӂ]x>f~|~8DBĖm;8`ڷq6WgꪘFRXKZej^tI[D>^*Izq~Ծ#4?\ǵ;uᯖIW=X=v2JflVq#"GG=Fb:7N қ8kXxHzh]|zx0'`N__PKV-PKXJmahjong/util/Triple.classS[OQNwm"Pn \JEPai)kY,-o~/h6]j::DVLꔋ0} KPA U4_'OV֎D*}P*s%5zzv\-t>6\!vc>Տ>##Ak8)"  QCzC~?&!$O"_RXrJsKҘQ S%R\;#̧Ad =R$dZBDrKqYf՘241P~aQCjER,`˟:CnvvvNFҢT̜TFм<̼IJDF~׼̼tԒv.FČtҒ}d]* >L(QŒYTǡ!aǻxO} x!mw<ƾ.5ftgߩyK 1˭7mvjuJJǩ"ym^agIkn8Ӡʀ{p^M;ޚ/.c)FVK2m$#N+0 Hͽ`LD(U)J9?E,BzO%4m$bD 2 kuŨw(ft#"BFMxL@f!oK-suIo0 8LcP69C DI"S巐DYDiJ:lM +쇐Ao+hEp. 9bLTYzO Mp_CBv̟&;⎹$9PKȚo!PKXJ%mahjong/util/UnionFindSet$Entry.class_oAvZ*V ЊO6MLm m5T}rv+,fYLN>D?x"4u#a9wgv~@ td *X*dU%cEM6dS Y9?ۅk'?W#;l3d{"ۮ}0ʮ+n˶rihF=J?[Aњ j~ev + uMbfVW߲V}TWu5ص3 "aM"Ac*[]-׬5M!hi8YWOm4&:vƘPrQ6{QWfp@ WaH⺁^x"-`^G97'GjKC6\,1Y>$LSA33Öosc㼕"b!jYVa+܅vʗ$aCqp 4}EBwpZeQpXߡ}XD{ɗ.^_bⲲY[85MS_rI(>H8<C N/Jo[actm!PK _3tPK XJmahjong/automata/PKXJ.mahjong/automata/DFAEquivalenceChecker$1.class; ADuuu@E c <GL i~`Gm+٦ZvUiZU"", QR&# LdWrOxN|( jN0@h૦CmmuS;oPKR1ƫPKXJmahjong/automata/DFAState.classVkSf~A.VmxC(YRdu7 쌠ؙԙNSϛֽ@웜sssNGx ?%Ѓ$qI#UZ@=O Rb2kVjq@3I;.nxW׌&Y1gv-$VDsM+3!-9sW2~z6[K)"3=4tM=Wgn \[(VǦ.TkLm:Apn\qQ^q_y"N0۳mLՔ^#-k0kfĬEx꿙y 6dĂsَT!mh8a'lًVϔ]6]ӱL?7ꞡTkbnaH[wK! s(-{:9d 6m-;-Q͋ $}u 7pV1sW3LOFǥck8~ {OC/ rNY80 GpZGlɉA< ^ѰSA%qnI wɗۚԎe^vPPM %*\xV13 lϲTpYO)cR]ZG3 ՠ*E`_TZ> 6zܥ_(bѺ x޳仑 o-Ⲽ,Lj[9%ȳ:DzS9mD¦\sDj;ˆ\ռw}b+yM4|5pob`+βogU yO*Eq=MضQDllkLQ_0o鈰G9=Sn(xR)>!Qٔ5sgǐ4(>=>>i4Q܋&=abd^%wX`?%E&G&L<iu]N<.鰌VhZ%5E~GRk# NQ#MR#%rݺk- VcH=%V'*q25Q(=ApX݁?xc$5h5 zЍspF;FЍQ?J 0atmGhѡ!:ױ3ZCw] L0e6|{dM'"O|vs/dd bϽ͌n/٩L= E|wKߐi7h&B_PK7Ǔ8\ PKXJmahjong/automata/NFA.classVWW&&$DRE T\,*V]dLL&Vk}7jmU=K]7H [w}h~܏r4G d.sUw$9*a3.]3,ݴӶ՝Rc.M)-4 NM$tZqM?RGaQvXI3{R=F3nD5+16ާ&}ifVڙ :f1)RΊB}M M.NCAtM'HZz`D":nRGƂ[xZ] $_rlRI&j7"Hn5Q4,JFV e3ʤbZ.ߵg@Q4bXâa1 *QpO*8T(`V)xZ <Z/PfYtU *𢂗𲂕VlW7 FwЮ]`8Gئ#|,3|U)|AL'_ЦJtcbL'31 k#ӝ|YOO$!TI+) /fu{5Φ%C_KXXLK2F~fӝ6fd̘[f2ә)RWU[1e\ðWigӺ9jhe.Wk0ť&)T2h.8x45!am?+er. =D ~Jiq=VD'p@&d(:G^[Cd|~T ^9wyעNdQGԘmxN%kYBij)xo埼T=7׳yjK}.CcMv1dᥛ_xDfD۴-ԬoX'#CZOo6%ΥLecی2W7,(ʑoR$su82 &2^3?vrZT 1@-v0J-so.VJ<"/B./3`Y^Rxy>.ŝuC QQi>ed|P,gWև{v-9B2R,">,G\,ZmbE>x`}I$L̽\{E\k}xeA)Հ*n#nowz%^J KXݓRGFp+] -?'FwgH꜡ZP3y#lkj䳚Qh/XjѶ”7];%xM˹vKrʝ5c\ٞH' k |XSk@"SZ_Lr;4!98ϱfG4Q;O$;IS*(,TsRU䨣㌨i{VY^ 鯄k%pQZ1p(x>[X;㞠p9¨"/}Q*:PV?$xY|77-:5Ϫi}BOKq0XH ܢ&I55W@4mX/!TZv挬Z揀gˋjhZ2"a_T@Z~^bkjMWK~! a*=qE|6u%Dx3+R " >> (&քS[͍]d!QІvhqZxVz5cDxЏ32V0 &1`PY(>hIh!cRQǧ(,>|ޏ=xԏ/("$ d|Uu7YDs.|Kz]?'DO~Q9 çIXk;i0r 9SR5.*t$EMjrpR3~]kY nΉ#+ΞX)Jn|Di5`)B~_a'@uWlj,e9ft.ҲҳAVd&ҹ}ډ2\{'ە'̃Z򎩨dԚωZ²`Nssn{΍RgRѻ oN+o$\^*%fOd£f2IuS&( Pf*%v)(yK׳cQAU`+q:ҚysYh&o-!.sJXi^Q^9q$ ._y(쇢~/ aZMFT?o v3wq݈+8&e8qNZkyoၬ͜9H܂=~<ϲUZQ𣳓k볎n5Oj&KpvY< -evd4a~8TyEy!+>Ƣ䶫̇5,wAH_[Mz^ kt+|UsP \$Nsi|OvRQUjtb-U]zYx&uaȽӨLTAϴKDK[QjĿi&P{n ɺ3DV i5h:xkpt<|Qf!F*XEhemYSM^92 ]xNNc@XE}HmsOc9-_Å I\8jIMbD齂D~o>ĥBoHHZq4N`69 Q3ŀZ o:PoF60uz35v0v1lѿ[)yzp'kP$2'GF>'zރi8 f*l%FBd`bɅ|WD3٧!$詥*SV c=E8z:b"@zT[E"#&pslbIE:UR7Q,g?Ͳpv)Gl -+W.leJęUͶr=^b_k!#-h-֯;Ш'-bw!VѢלb]l9,"q/e>wfevp= OXAf♑(A*Vy=}fMBGp 5C&'wSyp¦N&J 7Ew soPKV&wPKXJmahjong/automata/DFA.classVkWW3 LHA|⃪ C-CA)Vd$ kC@l+귮RW}'CBk%w}9;_wp7؎5؆~1rsxBN+Q `P5y*x҃00F-yp#B?%\N1D.q 1)PTP55SJ MjZ gn%Ԅ㱔f2RmG(MLX@˙FR3@O_WX@ W-v +8c~JX8.2-Dq[~3|%aG1n<5mL遐jltm\F=ɢ T;JMb_?2Z*г;%fa3Ołr.RCVmYҸu_?÷Ee;~ClpB$$cdzow*u>9RQ/C@MI^̏-\mC(%zp N1)9 ylbE"\U9\۷Nw,̯C<`\2F|P58 H.NT v@кU2BZPsh5ʸOǺ;BYy \8DhM1GЁ1t<|tYIpG[f~r]4Q-l[Htm$r~|ؖvC-M8 Y]B*ȞN$wfN>[}9log9J6ʸUbI垵MΰDgF4b\{ c㬓\\8˳h7H'hUP -n l{PfF귺VY()A({Mﱾx,77sz}b%s|/ЈQ _Eܪ!Rfss ZMC7a̕6dmi] uZYRfvJan o%9Sո@/"flVMMRGrvH-U"Vr;Vfi^g~3uw0gnpWu9oe{Qb*b*w*1b *{D25fnq NLbڳL#vPw|L{ az0G'?Og;T!nj 覛p0qgPK PKXJ,mahjong/automata/DFAEquivalenceChecker.classXUnNhaZ}nҐXI)IZٴ4dwL;V jo+(bE+RM("_mvCgj{s={'+nh~wQ! + # `P0F$lISp-U'&7{po#W1hBj S`idXI.'0}T_6RTaQQ ezӺ@Όu z!j #̸Ӥ< h eiۚl]ֳBϼ`Id *~3\p%#F1ret MGk{tHmq}OsTЕS]FMnbz]{`4xJonsN3j27guYC+nJ!pg!`V +|CM olNu'|.i 2ZsTvu'T \LnU|'U|S8+[tTIJ!Y"XŪUڝ]@$_qaΓ#V$YRDŸ`9 ә4a$o}*vçtmb]l/2Gg4Keg2H5;#5`y [:z6> ,a3jS@I&ZwJ[6_0 $amY&|ƴdy+q +iQ|b5(Ba;]U1A[ĕ Qe" h5,LKkZ &| SVc>hhH+]HC'0*?*Яb/z6´3FwEHГL&L$SzRW֬!۞˳`ORii^,?iMvU=5.orqKg{t:ҥoWKFu>l`VB~B|-m6-g9횭|@|m9mb#mstu͢3Z@}MuZPSwiD,H(S8(U ՝a9jH5VM\aBu58}E-X-mZ,34smװn4ބ-a6r~ьal!RVA'#Og s_Rݪ :p(MeU['YmkFNu07^:Zs g7հY/P]F9I5 6vքV~kϜp:P:ҳ>|ڇA~G߁{0ϫPO( nD2{<9lL|i)B^sVIEzej9  ?+ZHSGS xǧb]Be-Wc J For example, let us analyze luindex again. This time, we let DOOP use the reflection analysis results created by TamiFlex (suppose they are in the file "$DOOP_HOME/refl.log"): $ ./run -jre1.6 -mahjong -refl-log refl.log 3-object-sensitive+2-heap jars/dacapo/luindex.jar ----------------------------------------------- | Reproducibility of the Results in Our Paper | ----------------------------------------------- Generally, using this release version to analyze the programs in our paper ("Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata", PLDI'17) will generate the client results with smaller numbers than those in the paper. This is due to some dynamically loaded classes missed by DOOP. DOOP builds closed-world without considering dynamic class loading, so some classes that are dynamically loaded during runtime will be missed by DOOP during analysis. In the evaluation of our paper, to build a more sound closed-world, we manually adds these classes (discovered by TamiFlex but missed by DOOP) to DOOP’s closed-world. But we do not do this in the release version. As a result, DOOP in the evaluation of the paper reaches more code and genetates client results with larger numbers than this release version. To reproduce the results in our paper, please download the artifact from MAHJONG website. ----------- | Licence | ----------- GPL v3 Please feel free to contact the authors if you have any concerns. src/0000775000176100017620000000000013120354112010032 5ustar yueyuesrc/mahjong/0000775000176100017620000000000013120354112011455 5ustar yueyuesrc/mahjong/pta/0000775000176100017620000000000013120354112012241 5ustar yueyuesrc/mahjong/pta/Obj.java0000664000176100017620000000062613120354112013622 0ustar yueyuepackage mahjong.pta; import mahjong.util.Numberable; /** * A class used to represent abstract objects in points-to analysis. * To avoid the name collision between this class and java.lang.Object, * it is named "Obj". * * @author Tian Tan * @author Yue Li */ public abstract class Obj extends Numberable { public abstract String getName(); public abstract Type getType(); } src/mahjong/pta/PTAProvider.java0000664000176100017620000000074213120354112015246 0ustar yueyuepackage mahjong.pta; import java.util.Iterator; import mahjong.util.Triple; /** * @author Tian Tan * @author Yue Li */ public interface PTAProvider { /** * * @return an iterator for each object in the points-to set */ public Iterator objIterator(); /** * * @return an iterator for every field points-to relation, * including instance field and array objects */ public Iterator> fptIterator(); } src/mahjong/pta/Field.java0000664000176100017620000000024013120354112014123 0ustar yueyuepackage mahjong.pta; import mahjong.util.Numberable; /** * @author Tian Tan * @author Yue Li */ public abstract class Field extends Numberable {} src/mahjong/pta/Type.java0000664000176100017620000000023713120354112014027 0ustar yueyuepackage mahjong.pta; import mahjong.util.Numberable; /** * @author Tian Tan * @author Yue Li */ public abstract class Type extends Numberable {} src/mahjong/pta/doop/0000775000176100017620000000000013120354112013202 5ustar yueyuesrc/mahjong/pta/doop/DoopType.java0000664000176100017620000000065013120354112015611 0ustar yueyuepackage mahjong.pta.doop; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class DoopType extends Type { private final String typeName; private final int id; DoopType(String typeName, int id) { this.typeName = typeName; this.id = id; } @Override public int getID() { return id; } @Override public String toString() { return typeName; } } src/mahjong/pta/doop/DoopItemManager.java0000664000176100017620000000107213120354112017060 0ustar yueyuepackage mahjong.pta.doop; import java.util.Collection; import java.util.HashMap; import java.util.Map; /** * @author Tian Tan * @author Yue Li */ abstract class DoopItemManager { private Map name2item = new HashMap<>(); protected int count = 0; T get(String name) { T item = name2item.get(name); if (item == null) { item = createItem(name); name2item.put(name, item); } return item; } protected abstract T createItem(String name); Collection getAllItems() { return name2item.values(); } } src/mahjong/pta/doop/FieldManager.java0000664000176100017620000000041513120354112016363 0ustar yueyuepackage mahjong.pta.doop; import mahjong.pta.Field; /** * @author Tian Tan * @author Yue Li */ class FieldManager extends DoopItemManager { @Override protected Field createItem(String name) { return new DoopField(name, ++count); } } src/mahjong/pta/doop/Options.java0000664000176100017620000000341613120354112015504 0ustar yueyuepackage mahjong.pta.doop; /** * @author Tian Tan * @author Yue Li */ public class Options { private String dbPath; private String cachePath; private String app; private String outPath; private boolean isDebug = false; public String getDbPath() { return dbPath; } public void setDbPath(String dbPath) { this.dbPath = dbPath; } public String getCachePath() { return cachePath; } public void setCachePath(String cachePath) { this.cachePath = cachePath; } public String getApp() { return app; } public void setApp(String app) { this.app = app; } public String getOutPath() { return outPath; } public void setOutPath(String outPath) { this.outPath = outPath; } public boolean isDebug() { return this.isDebug; } public void setIsDebug(boolean isDebug) { this.isDebug = isDebug; } public static Options parse(String[] args) { Options opt = new Options(); for (int i = 0; i < args.length; ++i) { if (args[i].equals("-db")) { i = shift(args, i); opt.setDbPath(args[i]); } else if (args[i].equals("-cache")) { i = shift(args, i); opt.setCachePath(args[i]); } else if (args[i].equals("-app")) { i = shift(args, i); opt.setApp(args[i]); } else if (args[i].equals("-out")) { i = shift(args, i); opt.setOutPath(args[i]); } else if (args[i].equals("-debug")) { opt.setIsDebug(true); } else { throw new RuntimeException("Unexpected options: " + args[i]); } } return opt; } private static int shift(String[] args, int index) { if (args.length == index + 1) { System.err.println("error: option " + args[index] + " requires an argument"); System.exit(1); } return index + 1; } } src/mahjong/pta/doop/DoopField.java0000664000176100017620000000062313120354112015713 0ustar yueyuepackage mahjong.pta.doop; import mahjong.pta.Field; /** * @author Tian Tan * @author Yue Li */ public class DoopField extends Field { private final String sig; private final int id; DoopField(String sig, int id) { this.sig = sig; this.id = id; } @Override public int getID() { return id; } @Override public String toString() { return sig; } } src/mahjong/pta/doop/DoopPTAProvider.java0000664000176100017620000000452613120354112017035 0ustar yueyuepackage mahjong.pta.doop; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; import mahjong.pta.Field; import mahjong.pta.Obj; import mahjong.pta.PTAProvider; import mahjong.util.Triple; /** * @author Tian Tan * @author Yue Li */ public class DoopPTAProvider implements PTAProvider { private static final String ARR_FIELD = "@ARRAY"; private final DataBase db; private final ObjManager objManager; private final FieldManager fieldManager; public DoopPTAProvider(DataBase db) { this.db = db; this.objManager = new ObjManager(db); this.fieldManager = new FieldManager(); } @Override public Iterator objIterator() { return new ObjIterator(); } @Override public Iterator> fptIterator() { return new FPTIterator(); } private class ObjIterator implements Iterator { private Iterator> objIter; private ObjIterator() { objIter = db.query("OBJ").iterator(); } @Override public boolean hasNext() { return objIter.hasNext(); } @Override public Obj next() { if (hasNext()) { List obj = objIter.next(); return objManager.get(obj.get(0)); } else { throw new NoSuchElementException(); } } } private class FPTIterator implements Iterator> { private Iterator> fptIter; private Iterator> aptIter; private FPTIterator() { fptIter = db.query("IFPT").iterator(); aptIter = db.query("APT").iterator(); } @Override public boolean hasNext() { return fptIter.hasNext() || aptIter.hasNext(); } @Override public Triple next() { if (fptIter.hasNext()) { List fpt = fptIter.next(); Obj baseObj = objManager.get(fpt.get(0)); Field field = fieldManager.get(fpt.get(1)); Obj obj = objManager.get(fpt.get(2)); return new Triple(baseObj, field, obj); } else if (aptIter.hasNext()) { List apt = aptIter.next(); Obj array = objManager.get(apt.get(0)); Field field = fieldManager.get(ARR_FIELD); Obj obj = objManager.get(apt.get(1)); return new Triple(array, field, obj); } else { throw new NoSuchElementException(); } } } } src/mahjong/pta/doop/DataBase.java0000664000176100017620000001206013120354112015510 0ustar yueyuepackage mahjong.pta.doop; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; /** * The class representing database of Doop. * * @author Tian Tan * @author Yue Li */ public class DataBase { public static final Map QUERY = new HashMap<>(); private static final String CMD = "bloxbatch -db %s -query %s"; private static final String SEP = ", "; private Map>> queryResults = new HashMap<>(); private final File dbDir; private final File cacheDir; private final String program; static { QUERY.put("OBJ", "_(obj)<-Stats:Simple:InsensVarPointsTo(obj,_)."); QUERY.put("OBJ_TYPE", "_[obj]=type<-" + "HeapAllocation:Type[obj]=type," + "Stats:Simple:InsensVarPointsTo(obj,_)."); QUERY.put("IFPT", "_(baseheap,field,heap)<-" + "InstanceFieldPointsTo(_,heap,field,_,baseheap)."); QUERY.put("APT", "_(array,heap)<-ArrayIndexPointsTo(_,heap,_,array)."); } public DataBase(File dbDir) { this.dbDir = null; this.cacheDir = null; this.program = null; init(dbDir); } public DataBase(File dbDir, File cacheDir, String program) { this.dbDir = dbDir; this.cacheDir = cacheDir; this.program = program; } /** Return the results of the give query. */ List> query(String query) { if (this.cacheDir == null) { return queryResults.get(query); } else { return queryDoopWithCache(query); } } /** * Query Doop database and store the query results to queryResults. * @param dbDir the directory of Doop database. */ private void init(File dbDir) { System.out.println("Querying Doop database ..."); for (String query: QUERY.keySet()) { queryDoop(dbDir, query); } } private void queryDoop(File dbDir, String query) { List> results = new LinkedList<>(); try { Process proc = null; String cmd = String.format(CMD, dbDir.getAbsolutePath(), QUERY.get(query)); Runtime rt = Runtime.getRuntime(); proc = rt.exec(cmd); BufferedReader reader = new BufferedReader(new InputStreamReader( proc.getInputStream())); String line = null; while ((line = reader.readLine()) != null) { results.add(line2list(line)); } if (proc != null) { proc.waitFor(); } reader.close(); queryResults.put(query, results); } catch (InterruptedException e) { throw new RuntimeException("Exception during query: " + QUERY.get(query)); } catch (IOException e) { throw new RuntimeException("Query " + query + " fails, " + "caused by " + e.getMessage()); } } /** Query Doop and cache the results for later uses. */ private List> queryDoopWithCache(String query) { BufferedReader reader = getCacheReader(query); List> result = new LinkedList<>(); try { Process proc = null; if (reader == null) { String cmd = String.format(CMD, dbDir.getAbsolutePath(), QUERY.get(query)); Runtime rt = Runtime.getRuntime(); proc = rt.exec(cmd); reader = new BufferedReader(new InputStreamReader( proc.getInputStream())); } String line = null; while ((line = reader.readLine()) != null) { result.add(line2list(line)); } if (proc != null) { proc.waitFor(); // bloxbatch is invoked which means that the cache file // does not exist. So we are going to create the cache. createCache(query, result); } reader.close(); } catch (InterruptedException e) { throw new RuntimeException("Exception during query: " + QUERY.get(query)); } catch (IOException e) { throw new RuntimeException("Query " + query + " fails, " + "caused by " + e.getMessage()); } return result; } private BufferedReader getCacheReader(String query) { BufferedReader reader = null; File path = getCacheFile(query); if (path.exists()) { try { reader = new BufferedReader(new FileReader(path)); } catch (IOException e) { throw new RuntimeException("Read cache file fails: " + path); } } return reader; } private File getCacheFile(String query) { File cacheFile = null; if (cacheDir != null) { String fileName = String.format("%s.%s", program, query); String filePath = String.format("%s%s%s", cacheDir.getAbsolutePath(), File.separator, fileName); cacheFile = new File(filePath); } return cacheFile; } private void createCache(String query, List> content) throws IOException { File path = getCacheFile(query); PrintWriter writer = new PrintWriter(new FileWriter(path)); content.forEach(list -> { writer.println(String.join(SEP, list)); }); writer.close(); } private List line2list(String line) { return Arrays.asList(line.trim().split(SEP)); } } src/mahjong/pta/doop/ObjManager.java0000664000176100017620000000161013120354112016050 0ustar yueyuepackage mahjong.pta.doop; import java.util.HashMap; import java.util.Map; import mahjong.pta.Obj; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ class ObjManager extends DoopItemManager { private final Map typeMap; private final TypeManager typeManager = new TypeManager(); ObjManager(DataBase db) { typeMap = new HashMap<>(); db.query("OBJ_TYPE").forEach(list -> { String objName = list.get(0); String typeName = list.get(1); typeMap.put(objName, typeName); }); } @Override protected Obj createItem(String name) { String typeName = typeMap.get(name); return new DoopObj(name, typeManager.get(typeName), ++count); } private class TypeManager extends DoopItemManager { @Override protected Type createItem(String name) { return new DoopType(name, ++count); } } } src/mahjong/pta/doop/DoopObj.java0000664000176100017620000000132513120354112015402 0ustar yueyuepackage mahjong.pta.doop; import mahjong.pta.Obj; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class DoopObj extends Obj { private final String objName; private final Type type; private final int id; private final String rep; DoopObj(String objName, Type type, int id) { this.objName = objName; this.type = type; this.id = id; this.rep = String.format("%s(%d)", objName, id); //this.rep = objName; } @Override public int getID() { return id; } @Override public String getName() { return objName; } @Override public Type getType() { return type; } @Override public String toString() { return rep; } } src/mahjong/HeapAbstraction.java0000664000176100017620000000774613120354112015405 0ustar yueyuepackage mahjong; import java.util.Collection; import java.util.HashMap; import java.util.Map; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; import java.util.stream.Collectors; import mahjong.automata.DFA; import mahjong.automata.DFAEquivalenceChecker; import mahjong.automata.DFAFactory; import mahjong.automata.DFAState; import mahjong.fpg.FieldPointstoGraph; import mahjong.pta.Obj; import mahjong.pta.Type; import mahjong.util.UnionFindSet; /** * @author Tian Tan * @author Yue Li */ public class HeapAbstraction { private final FieldPointstoGraph fpg; private final DFAFactory dfaFactory; private final DFAEquivalenceChecker dfaEqChecker; /** This map would be manipulated by multiple threads * thus it should be concurrent hashmap. */ private Map canMerged; public HeapAbstraction(FieldPointstoGraph fpg) { this.fpg = fpg; this.dfaFactory = new DFAFactory(fpg); this.dfaEqChecker = new DFAEquivalenceChecker(); } public Map computeMergedObjectMap() { UnionFindSet uf = modelHeap(); Map mom = convertToMap(uf.getDisjointSets()); return mom; } /** * Modeling the heap by checking the equivalence of automata. */ private UnionFindSet modelHeap() { canMerged = new ConcurrentHashMap<>(); Set allObjs = fpg.getAllObjs(); UnionFindSet uf = new UnionFindSet<>(allObjs); // group the objects by their types Map> groupedObjs = allObjs .stream() .collect(Collectors.groupingBy( obj -> obj.getType(), Collectors.toSet())); groupedObjs.entrySet() .parallelStream() .forEach(entry -> { Set objs = entry.getValue(); DFAMap dfaMap = new DFAMap(); for (Obj o1 : objs) { if (canBeMerged(o1, dfaMap)) { for (Obj o2 : objs) { if (canBeMerged(o2, dfaMap)) { if (o1.getID() <= o2.getID() && !uf.isConnected(o1, o2)) { if (canBeMerged(o1, o2, dfaMap)) { uf.union(o1, o2); } } } } } } }); return uf; } /** * * @param o1 * @param o2 * @return whether o1 and o2 can be merged. */ private boolean canBeMerged(Obj o1, Obj o2, DFAMap dfaMap) { if (o1 == o2) { return true; } DFA dfa1 = dfaMap.retrieveDFA(o1); DFA dfa2 = dfaMap.retrieveDFA(o2); return dfaEqChecker.isEquivalent(dfa1, dfa2); } /** * * @param o * @return whether o can be merged with other objects. */ private boolean canBeMerged(Obj o, DFAMap dfaMap) { if (!canMerged.containsKey(o)) { boolean result = true; // Check whether the types of objects pointed (directly/indirectly) // by o are unique. DFA dfa = dfaMap.retrieveDFA(o); for (DFAState s : dfa.getStates()) { if (dfa.outputOf(s).size() > 1) { // Types pointed (directly/indirectly) by o are not unique. result = false; break; } } canMerged.put(o, result); } return canMerged.get(o); } private static Map convertToMap(Collection> objModel) { Map map = new HashMap<>(); objModel.forEach(objs -> { Obj rep = selectRepresentative(objs); objs.forEach(obj -> map.put(obj, rep)); }); return map; } private static Obj selectRepresentative(Set objs) { return objs.stream().findFirst().get(); } /** * During equivalence check, each thread holds a DFAMap which contains * the DFA of the objects of the type. After comparison, the DFAMap * and its containing DFA will be released to save memory space. * */ private class DFAMap { private final Map dfaMap = new HashMap<>(); private DFA retrieveDFA(Obj o) { if (!dfaMap.containsKey(o)) { DFA dfa = dfaFactory.getDFA(o); dfaMap.put(o, dfa); } return dfaMap.get(o); } } } src/mahjong/fpg/0000775000176100017620000000000013120354112012231 5ustar yueyuesrc/mahjong/fpg/FieldPointstoGraph.java0000664000176100017620000000465113120354112016647 0ustar yueyuepackage mahjong.fpg; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; import mahjong.pta.Field; import mahjong.pta.Obj; import mahjong.pta.PTAProvider; /** * @author Tian Tan * @author Yue Li */ public class FieldPointstoGraph { private PTAProvider provider; private Map>> pointsTo = new HashMap<>(); private Map>> pointedBy = new HashMap<>(); public FieldPointstoGraph(PTAProvider provider) { this.provider = provider; provider.objIterator().forEachRemaining(this::insertObj); provider.fptIterator().forEachRemaining(triple -> { Obj baseObj = triple.getFirst(); Field field = triple.getSecond(); Obj obj = triple.getThird(); insertFPT(baseObj, field, obj); }); } public PTAProvider getPTAProvider() { return provider; } public Set getAllObjs() { return pointsTo.keySet(); } public Set outFieldsOf(Obj baseObj) { return pointsTo.get(baseObj).keySet(); } public Set inFieldsOf(Obj obj) { return pointedBy.get(obj).keySet(); } public Set pointsTo(Obj baseObj, Field field) { return pointsTo.get(baseObj).get(field); } public Set pointedBy(Obj obj, Field field) { return pointedBy.get(obj).get(field); } public boolean hasFieldPointer(Obj obj, Field field) { return pointsTo.get(obj).containsKey(field); } private void insertObj(Obj obj) { if (!pointsTo.containsKey(obj)) { pointsTo.put(obj, new HashMap<>()); } if (!pointedBy.containsKey(obj)) { pointedBy.put(obj, new HashMap<>()); } } /** * Insert field points-to relation. * @param baseObj the base object * @param field a field of `baseObj' * @param obj the object pointed by `field' */ private void insertFPT(Obj baseObj, Field field, Obj obj) { insertPointsTo(baseObj, field, obj); insertPointedBy(baseObj, field, obj); } private void insertPointsTo(Obj baseObj, Field field, Obj obj) { Map> fpt = pointsTo.get(baseObj); if (!fpt.containsKey(field)) { fpt.put(field, new HashSet<>()); } fpt.get(field).add(obj); } private void insertPointedBy(Obj baseObj, Field field, Obj obj) { Map> fpb = pointedBy.get(obj); if (!fpb.containsKey(field)) { fpb.put(field, new HashSet<>()); } fpb.get(field).add(baseObj); } } src/mahjong/main/0000775000176100017620000000000013120354112012401 5ustar yueyuesrc/mahjong/main/DoopMain.java0000664000176100017620000000650113120354112014754 0ustar yueyuepackage mahjong.main; import java.io.File; import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.Map; import mahjong.HeapAbstraction; import mahjong.fpg.FieldPointstoGraph; import mahjong.pta.Obj; import mahjong.pta.doop.DataBase; import mahjong.pta.doop.DoopPTAProvider; import mahjong.pta.doop.Options; /** * @author Tian Tan * @author Yue Li */ public class DoopMain { private static final char SEP = '\t'; private static final char EOL = '\n'; public static void main(String[] args) throws FileNotFoundException { run(args); } public static void run(String[] args) throws FileNotFoundException { Options opt = Options.parse(args); FieldPointstoGraph fpg = buildFPG(opt.getDbPath()); System.out.print("Creating heap abstraction ... "); long start = System.currentTimeMillis(); HeapAbstraction heapAbs = new HeapAbstraction(fpg); Map mom = heapAbs.computeMergedObjectMap(); long end = System.currentTimeMillis(); DoopMain.outputElapsedTime(start, end); outputStatistics(mom); System.out.printf("Writing Mahjong heap abstraction to %s ...\n", opt.getOutPath()); File outputFile = new File(opt.getOutPath(), "MahjongHeapAbstraction.facts"); writeMergedObjectMap(mom, outputFile); } public static FieldPointstoGraph buildFPG(String dbPath) { File dbDir = new File(dbPath); DataBase db = new DataBase(dbDir); System.out.print("Building FPG (Field Points-to Graph) ... "); long start = System.currentTimeMillis(); DoopPTAProvider fptProvider = new DoopPTAProvider(db); FieldPointstoGraph fpg = new FieldPointstoGraph(fptProvider); long end = System.currentTimeMillis(); outputElapsedTime(start, end); return fpg; } public static FieldPointstoGraph buildFPG(String dbPath, String cachePath, String app) { File dbDir = new File(dbPath); File cacheDir = new File(cachePath); DataBase db = new DataBase(dbDir, cacheDir, app); System.out.print("Building FPG (Field Points-to Graph) ... "); long start = System.currentTimeMillis(); DoopPTAProvider fptProvider = new DoopPTAProvider(db); FieldPointstoGraph fpg = new FieldPointstoGraph(fptProvider); long end = System.currentTimeMillis(); outputElapsedTime(start, end); return fpg; } public static void outputElapsedTime(long start, long end) { System.out.printf("elapsed time: %.2fs\n", (end - start) / 1000F); } public static void outputStatistics(Map mom) { int nObj = (int) mom.keySet().stream().distinct().count(); int nObjMahjong = (int) mom.values().stream().distinct().count(); System.out.println("-----------------------------------------------------------"); System.out.printf("%d objects in the allocation-site heap abstraction.\n", nObj); System.out.printf("%d objects in the Mahjong heap abstraction.\n", nObjMahjong); System.out.println("-----------------------------------------------------------"); } private static void writeMergedObjectMap(Map mom, File outputFile) throws FileNotFoundException { PrintWriter writer = new PrintWriter(outputFile); mom.forEach((heap, mergedHeap) -> { writer.write(heap.getName()); writer.write(SEP); writer.write(mergedHeap.getName()); writer.write(EOL); }); writer.close(); } } src/mahjong/util/0000775000176100017620000000000013120354112012432 5ustar yueyuesrc/mahjong/util/Triple.java0000664000176100017620000000206713120354112014541 0ustar yueyuepackage mahjong.util; import java.util.Objects; /** * @author Tian Tan * @author Yue Li */ public class Triple { private final T1 first; private final T2 second; private final T3 third; public Triple(T1 first, T2 second, T3 third) { this.first = first; this.second = second; this.third = third; } public T1 getFirst() { return first; } public T2 getSecond() { return second; } public T3 getThird() { return third; } @Override public int hashCode() { return Objects.hash(first, second, third); } @Override public boolean equals(Object o) { if (o instanceof Triple) { Triple anoTriple = (Triple) o; return Objects.equals(first, anoTriple.first) && Objects.equals(second, anoTriple.second) && Objects.equals(third, anoTriple.third); } return false; } @Override public String toString() { return "<" + Objects.toString(first) + ", " + Objects.toString(second) + ", " + Objects.toString(third) + ">"; } } src/mahjong/util/UnionFindSet.java0000664000176100017620000000340513120354112015644 0ustar yueyuepackage mahjong.util; import java.util.Collection; import java.util.HashMap; import java.util.Map; import java.util.Set; import java.util.stream.Collectors; /** * @author Tian Tan * @author Yue Li */ public class UnionFindSet { private Map entries = new HashMap<>(); private int nrsets; // number of disjoint sets public UnionFindSet(Collection elems) { elems.forEach(elem -> entries.put(elem, new Entry(elem))); nrsets = entries.size(); } public boolean union(E e1, E e2) { Entry root1 = findRoot(entries.get(e1)); Entry root2 = findRoot(entries.get(e2)); if (root1 == root2) { return false; } else { // union by rank if (root1.rank < root2.rank) { root1.parent = root2; } else if (root1.rank > root2.rank) { root2.parent = root1; } else { root2.parent = root1; ++root2.rank; } --nrsets; return true; } } public boolean isConnected(E e1, E e2) { Entry root1 = findRoot(entries.get(e1)); Entry root2 = findRoot(entries.get(e2)); return root1 == root2; } public E find(E e) { Entry ent = findRoot(entries.get(e)); return ent.elem; } public int numberOfSets() { return nrsets; } public Collection> getDisjointSets() { return entries.keySet() .stream() .collect(Collectors.groupingBy(this::find, Collectors.toSet())) .values(); } private Entry findRoot(Entry ent) { if (ent.parent != ent) { // path compression ent.parent = findRoot(ent.parent); } return ent.parent; } private class Entry { private final E elem; private Entry parent; private int rank; private Entry(E elem) { this.elem = elem; this.parent = this; this.rank = 0; } } } src/mahjong/util/Pair.java0000664000176100017620000000152313120354112014171 0ustar yueyuepackage mahjong.util; import java.util.Objects; /** * @author Tian Tan * @author Yue Li */ public class Pair { private final T1 first; private final T2 second; public Pair(T1 first, T2 second) { this.first = first; this.second = second; } public T1 getFirst() { return first; } public T2 getSecond() { return second; } @Override public int hashCode() { return Objects.hash(first, second); } @Override public boolean equals(Object o) { if (o instanceof Pair) { Pair anoPair = (Pair) o; return Objects.equals(first, anoPair.first) && Objects.equals(second, anoPair.second); } return false; } @Override public String toString() { return "<" + Objects.toString(first) + ", " + Objects.toString(second) + ">"; } } src/mahjong/util/Numberable.java0000664000176100017620000000056213120354112015354 0ustar yueyuepackage mahjong.util; /** * Every instance of this class has an unique ID number. * * @author Tian Tan * @author Yue Li */ public abstract class Numberable { public abstract int getID(); @Override public final int hashCode() { return getID(); } @Override public final boolean equals(Object obj) { return this == obj; } } src/mahjong/automata/0000775000176100017620000000000013120354112013270 5ustar yueyuesrc/mahjong/automata/DFAEquivalenceChecker.java0000664000176100017620000000573313120354112020204 0ustar yueyuepackage mahjong.automata; import java.util.Collection; import java.util.Set; import java.util.Stack; import java.util.stream.Collectors; import java.util.stream.Stream; import mahjong.pta.Field; import mahjong.pta.Type; import mahjong.util.Pair; import mahjong.util.UnionFindSet; /** * @author Tian Tan * @author Yue Li */ public class DFAEquivalenceChecker { /** * Check the equivalence of input automata by Hopcroft-Karp algorithm * with minor modifications. * @param dfa1 * @param dfa2 * @return whether dfa1 and dfa2 are equivalent */ public boolean isEquivalent(DFA dfa1, DFA dfa2) { CombinedDFA dfa = new CombinedDFA(dfa1, dfa2); Set combinedStates = dfa.getStates(); UnionFindSet uf = new UnionFindSet<>(combinedStates); Stack> stack = new Stack<>(); DFAState s1 = dfa1.getStartState(); DFAState s2 = dfa2.getStartState(); uf.union(s1, s2); stack.push(new Pair<>(s1, s2)); while (!stack.isEmpty()) { Pair pair = stack.pop(); DFAState q1 = pair.getFirst(); DFAState q2 = pair.getSecond(); Stream.concat(dfa.outEdgesOf(q1).stream(), dfa.outEdgesOf(q2).stream()) .forEach(field -> { DFAState r1 = uf.find(dfa.nextState(q1, field)); DFAState r2 = uf.find(dfa.nextState(q2, field)); if (r1 != r2) { uf.union(r1, r2); stack.push(new Pair<>(r1, r2)); } }); } Collection> mergedStateSets = uf.getDisjointSets(); return validate(dfa, mergedStateSets); } /** * * @param dfa * @param mergedStateSets * @return true if every state set contains no different output * (i.e., types) */ private boolean validate(CombinedDFA dfa, Collection> mergedStateSets) { for (Set set : mergedStateSets) { int minSize = set.stream() .mapToInt(s -> dfa.outputOf(s).size()) .min() .getAsInt(); long unionSize = set.stream() .flatMap(s -> dfa.outputOf(s).stream()) .distinct() .count(); if (unionSize > minSize) { return false; } } return true; } private class CombinedDFA { DFA dfa1, dfa2; private CombinedDFA(DFA dfa1, DFA dfa2) { this.dfa1 = dfa1; this.dfa2 = dfa2; } private Set getStates() { return Stream .concat(dfa1.getAllStates().stream(), dfa2.getAllStates().stream()) .collect(Collectors.toSet()); } private DFAState nextState(DFAState s, Field f) { return dfa1.containsState(s) ? dfa1.nextState(s, f) : dfa2.nextState(s, f); } private Set outEdgesOf(DFAState s) { return dfa1.containsState(s) ? dfa1.outEdgesOf(s) : dfa2.outEdgesOf(s); } private Set outputOf(DFAState s) { return dfa1.containsState(s) ? dfa1.outputOf(s) : dfa2.outputOf(s); } } } src/mahjong/automata/NFA.java0000664000176100017620000000333713120354112014545 0ustar yueyuepackage mahjong.automata; import java.util.Collections; import java.util.HashSet; import java.util.Set; import java.util.Stack; import mahjong.fpg.FieldPointstoGraph; import mahjong.pta.Field; import mahjong.pta.Obj; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class NFA { private static final Obj deadState = null; private Obj q0; private FieldPointstoGraph fpg; public NFA(Obj q0, FieldPointstoGraph fpg) { this.q0 = q0; this.fpg = fpg; } /** * This method on-the-fly computes set of states. * @return Set of states. Does not contains dead state. */ public Set getStates() { Set states = new HashSet<>(); Stack stack = new Stack<>(); stack.push(q0); while (!stack.isEmpty()) { Obj s = stack.pop(); if (!states.contains(s)) { states.add(s); outEdgesOf(s).forEach(field -> { nextStates(s, field).stream() .filter(obj -> !states.contains(obj)) .forEach(stack::push); }); } } return states; } public Obj getStartState() { return q0; } public Obj getDeadState() { return deadState; } public Set nextStates(Obj obj, Field f) { if (isDeadState(obj) || !fpg.hasFieldPointer(obj, f)) { return Collections.singleton(deadState); } else { return fpg.pointsTo(obj, f); } } public boolean isDeadState(Obj obj) { return obj == deadState; } public Set outEdgesOf(Obj obj) { if (isDeadState(obj)) { return Collections.emptySet(); } else { return fpg.outFieldsOf(obj); } } public Type outputOf(Obj obj) { if (isDeadState(obj)) { return null; } else { return obj.getType(); } } } src/mahjong/automata/DFA.java0000664000176100017620000000401713120354112014527 0ustar yueyuepackage mahjong.automata; import java.util.Collections; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Set; import mahjong.pta.Field; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class DFA { private Set states, allStates; private DFAState q0; private static final DFAState deadState = new DFAState(Collections.emptySet(), Collections.emptySet()); public DFA(DFAState q0) { this.q0 = q0; } /** * * @return Set of states. Does not contains dead state. */ public Set getStates() { if (states == null) { computeStates(); } return states; } /** * * @return Set of all states including dead state. */ public Set getAllStates() { if (allStates == null) { computeStates(); } return allStates; } private void computeStates() { Queue queue = new LinkedList<>(); queue.add(q0); states = new HashSet<>(); while (!queue.isEmpty()) { DFAState s = queue.poll(); if (!states.contains(s)) { states.add(s); s.getNextMap().values().forEach(queue::add); } } allStates = new HashSet<>(states); allStates.add(deadState); } public DFAState getStartState() { return q0; } public DFAState getDeadState() { return deadState; } public boolean isDeadState(DFAState s) { return deadState == s; } public DFAState nextState(DFAState s, Field f) { if (isDeadState(s)) { return getDeadState(); } Map nextMap = s.getNextMap(); if (nextMap.containsKey(f)) { return nextMap.get(f); } return getDeadState(); } public Set outputOf(DFAState s) { return s.getOutput(); } public Set outEdgesOf(DFAState s) { Map nextMap = s.getNextMap(); return nextMap.keySet(); } public boolean containsState(DFAState s) { return getAllStates().contains(s); } } src/mahjong/automata/DFAFactory.java0000664000176100017620000000552213120354112016061 0ustar yueyuepackage mahjong.automata; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Set; import java.util.stream.Collectors; import mahjong.fpg.FieldPointstoGraph; import mahjong.pta.Field; import mahjong.pta.Obj; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class DFAFactory { private final FieldPointstoGraph fpg; private Map, DFAState> stateMap; private Set states, visited; public DFAFactory(FieldPointstoGraph fpg) { this.fpg = fpg; buildAllDFA(); } public DFA getDFA(Obj obj) { DFAState q0 = stateMap.get(Collections.singleton(obj)); return new DFA(q0); } private void buildAllDFA() { stateMap = new HashMap<>(); states = new HashSet<>(); visited = new HashSet<>(); fpg.getAllObjs().forEach(this::buildDFA); } /** * Perform subset construction algorithm to convert an NFA * to a DFA. If a set of NFA states are merged to an existing * DFA state, then reused the existing DFA state instead of creating * an equivalent new one. * @param obj the start state (object) of the DFA */ private void buildDFA(Obj obj) { Set q0Set = Collections.singleton(obj); if (!stateMap.containsKey(q0Set)) { NFA nfa = new NFA(obj, fpg); DFAState startState = getDFAState(q0Set, nfa); Queue worklist = new LinkedList<>(); states.add(startState); worklist.add(startState); while (!worklist.isEmpty()) { DFAState s = worklist.poll(); if (!visited.contains(s)) { visited.add(s); Set fields = fields(nfa, s.getObjects()); fields.forEach(f -> { Set nextNFAStates = move(nfa, s.getObjects(), f); DFAState nextState = getDFAState(nextNFAStates, nfa); if (!states.contains(nextState)) { states.add(nextState); worklist.add(nextState); } addTransition(s, f, nextState); }); } } } } private DFAState getDFAState(Set objs, NFA nfa) { if (!stateMap.containsKey(objs)) { Set output = objs.stream() .map(nfa::outputOf) .collect(Collectors.toSet()); stateMap.put(objs, new DFAState(objs, output)); } return stateMap.get(objs); } private Set move(NFA nfa, Set objs, Field f) { return objs.stream() .map(obj -> nfa.nextStates(obj, f)) .flatMap(nextStates -> nextStates.stream()) .collect(Collectors.toSet()); } private Set fields(NFA nfa, Set objs) { return objs.stream() .map(nfa::outEdgesOf) .flatMap(fields -> fields.stream()) .collect(Collectors.toSet()); } private void addTransition(DFAState s, Field f, DFAState nextState) { s.addTransition(f, nextState); } } src/mahjong/automata/DFAState.java0000664000176100017620000000302413120354112015525 0ustar yueyuepackage mahjong.automata; import java.util.HashMap; import java.util.Map; import java.util.Set; import java.util.stream.Collectors; import mahjong.pta.Field; import mahjong.pta.Obj; import mahjong.pta.Type; /** * @author Tian Tan * @author Yue Li */ public class DFAState { private final Set objs; private final Set output; private final Map nextMap; private boolean hasHashCode = false; private int hashCode; public DFAState(Set objs, Set output) { this.objs = objs; this.output = output; this.nextMap = new HashMap<>(); } public Set getObjects() { return objs; } public Set getOutput() { return output; } void addTransition(Field f, DFAState nextState) { nextMap.put(f, nextState); } Map getNextMap() { return nextMap; } /** * Cache hash code. */ @Override public int hashCode() { if (!hasHashCode) { hashCode = objs.hashCode(); hasHashCode = true; } return hashCode; } @Override public boolean equals(Object other) { if (this == other) { return true; } if (! (other instanceof DFAState)) { return false; } DFAState anoDFAState = (DFAState) other; return getObjects().equals(anoDFAState.getObjects()); } @Override public String toString() { return getObjects().stream() .map(obj -> obj == null ? "null" :String.valueOf(obj.getID())) .sorted() .collect(Collectors.toSet()) .toString(); } }