Java 类soot.jimple.spark.sets.PointsToSetInternal 实例源码

public static PointsToSetInternal constructIntersection(final PointsToSetInternal set1, final PointsToSetInternal set2, PAG pag) {
  HybridPointsToSet hybridSet1 = null, hybridSet2 = null;
  hybridSet1 = convertToHybrid(set1);
  hybridSet2 = convertToHybrid(set2);
  HybridPointsToSet intersection = HybridPointsToSet.intersection(hybridSet1, hybridSet2, pag);
  // checkSetsEqual(intersection, set1, set2, pag);
  return intersection;

}

private static HybridPointsToSet convertToHybrid(final PointsToSetInternal set) {
  HybridPointsToSet ret = null;
  if (set instanceof HybridPointsToSet) {
    ret = (HybridPointsToSet) set;
  } else if (set instanceof DoublePointsToSet) {
    assert ((DoublePointsToSet) set).getNewSet().isEmpty();
    ret = (HybridPointsToSet) ((DoublePointsToSet) set).getOldSet();
  }
  return ret;
}

public PointsToSet reachingObjects(Local l) {
    if(lazy)
        /*
         * create a lazy points-to set; this will not actually compute context information until we ask whether this points-to set
         * has a non-empty intersection with another points-to set and this intersection appears to be non-empty; when this is the case
         * then the points-to set will call doReachingObjects(..) to refine itself
         */         
        return new LazyContextSensitivePointsToSet(l,new WrappedPointsToSet((PointsToSetInternal) pag.reachingObjects(l)),this);
    else
        return doReachingObjects(l);
}

protected PointsToSetInternal checkContextsForAllocsCache(
        VarAndContext varAndContext, AllocAndContextSet ret,
        PointsToSetInternal locs) {
    PointsToSetInternal retSet = null;
    if (contextsForAllocsCache.containsKey(varAndContext)) {
        for (AllocAndContext allocAndContext : contextsForAllocsCache.get(
                varAndContext).getO2()) {
            if (locs.contains(allocAndContext.alloc)) {
                ret.add(allocAndContext);
            }
        }
        final PointsToSetInternal oldLocs = contextsForAllocsCache.get(
                varAndContext).getO1();
        final PointsToSetInternal tmpSet = new HybridPointsToSet(locs
                .getType(), pag);
        locs.forall(new P2SetVisitor() {

            @Override
            public void visit(Node n) {
                if (!oldLocs.contains(n)) {
                    tmpSet.add(n);
                }
            }
        });
        retSet = tmpSet;
        oldLocs.addAll(tmpSet, null);
    } else {
        PointsToSetInternal storedSet = new HybridPointsToSet(locs
                .getType(), pag);
        storedSet.addAll(locs, null);
        contextsForAllocsCache.put(varAndContext,
                new Pair<PointsToSetInternal, AllocAndContextSet>(
                        storedSet, new AllocAndContextSet()));
        retSet = locs;
    }
    return retSet;
}

@SuppressWarnings("unchecked")
protected Set<SootMethod> getCallTargets(PointsToSetInternal p2Set,
        NumberedString methodStr, Type receiverType,
        Set<SootMethod> possibleTargets) {
    List<Object> args = Arrays.asList(p2Set, methodStr, receiverType,
            possibleTargets);
    if (callTargetsArgCache.containsKey(args)) {
        return callTargetsArgCache.get(args);
    }
    Set<Type> types = p2Set.possibleTypes();
    Set<SootMethod> ret = new HashSet<SootMethod>();
    for (Type type : types) {
        ret.addAll(getCallTargetsForType(type, methodStr, receiverType,
                possibleTargets));
    }
    callTargetsArgCache.put(args, ret);
    return ret;
}

@SuppressWarnings("unused")
protected Set<VarNode> nodesPropagatedThrough(final VarNode source,
        final PointsToSetInternal allocs) {
    final Set<VarNode> marked = new HashSet<VarNode>();
    final Stack<VarNode> worklist = new Stack<VarNode>();
    Propagator<VarNode> p = new Propagator<VarNode>(marked, worklist);
    p.prop(source);
    while (!worklist.isEmpty()) {
        VarNode curNode = worklist.pop();
        Node[] assignSources = pag.simpleInvLookup(curNode);
        for (int i = 0; i < assignSources.length; i++) {
            VarNode assignSrc = (VarNode) assignSources[i];
            if (assignSrc.getP2Set().hasNonEmptyIntersection(allocs)) {
                p.prop(assignSrc);
            }
        }
        Set<VarNode> matchSources = vMatches.vMatchInvLookup(curNode);
        for (VarNode matchSrc : matchSources) {
            if (matchSrc.getP2Set().hasNonEmptyIntersection(allocs)) {
                p.prop(matchSrc);
            }
        }
    }
    return marked;
}

protected boolean refineAlias(VarNode v1, VarNode v2,
        PointsToSetInternal intersection, HeuristicType heuristic) {
    if (refineAliasInternal(v1, v2, intersection, heuristic))
        return true;
    if (refineAliasInternal(v2, v1, intersection, heuristic))
        return true;
    return false;
}

protected boolean refineP2Set(VarNode v, PointsToSetInternal badLocs,
        HeuristicType heuristic) {
    // G.v().out.println(badLocs);
    this.doPointsTo = false;
    this.fieldCheckHeuristic = HeuristicType.getHeuristic(heuristic, pag
            .getTypeManager(), getMaxPasses());
    try {
        numPasses = 0;
        while (true) {
            numPasses++;
            if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
                return false;
            }
            if (numPasses > maxPasses) {
                return false;
            }
            if (DEBUG) {
                G.v().out.println("PASS " + numPasses);
                G.v().out.println(fieldCheckHeuristic);
            }
            clearState();
            boolean success = false;
            try {
                success = refineP2Set(
                        new VarAndContext(v, EMPTY_CALLSTACK), badLocs);
            } catch (TerminateEarlyException e) {
                success = false;
            }
            if (success) {

                return true;
            } else {
                if (!fieldCheckHeuristic.runNewPass()) {
                    return false;
                }
            }
        }
    } finally {
    }
}

public boolean hasNonEmptyIntersection(PointsToSet other) {
  if (other instanceof AllocAndContextSet) {
    return nonEmptyHelper((AllocAndContextSet) other);
  } else if (other instanceof WrappedPointsToSet) {
    return hasNonEmptyIntersection(((WrappedPointsToSet) other).getWrapped());
  } else if (other instanceof PointsToSetInternal) {
    return ((PointsToSetInternal) other).forall(new P2SetVisitor() {

      @Override
      public void visit(Node n) {
        if (!returnValue) {
          for (AllocAndContext allocAndContext : AllocAndContextSet.this) {
            if (n.equals(allocAndContext.alloc)) {
              returnValue = true;
              break;
            }
          }
        }
      }

    });
  }
  throw new UnsupportedOperationException("can't check intersection with set of type " + other.getClass());
}

/**
 * For many applications, they only need the context insensitive points-to result.
 * We provide a way to transfer our result back to SPARK.
 * After the transformation, we discard the context sensitive points-to information.
 * Therefore, if context sensitive queries are needed in future, please call ddSolve() for queried pointers first. 
 */
public void transformToCIResult()
{   
    for ( IVarAbstraction pn : pointers ) {
        if ( pn.getRepresentative() != pn ) continue;

        Node node = pn.getWrappedNode();
        node.discardP2Set();
        PointsToSetInternal ptSet = node.makeP2Set();
        for ( AllocNode obj : pn.get_all_points_to_objects() ) {
            ptSet.add( obj );
        }

        pn.deleteAll();
    }

    hasTransformed = true;
}

private List<AllocNode> getMayAliasList(PointsToSetInternal pts)
{
    List<AllocNode> list = new ArrayList<AllocNode>();
    final HashSet<AllocNode> ret = new HashSet<AllocNode>();
    pts.forall( new P2SetVisitor() {
        public void visit( Node n ) {

            ret.add( (AllocNode)n );
        }
    } );
    Iterator<AllocNode> it = ret.iterator();
    while (it.hasNext()){
        list.add( it.next() );
    }
    return list;
}

private boolean isArrayAccessShared(Local local)
{
PointsToSetInternal pts = (PointsToSetInternal) pag.reachingObjects(local);
return pts.forall(new P2SetVisitor() {

    boolean isShared ;
         @Override
         public void visit(Node n) {
           if(!isShared)
           {
            int id = n.getNumber();
            XNode xn = indexNodeMap.get(id);
            if(xn!=null)
                isShared = xn.isArrayShared();
           }
         }
         @Override
         public boolean getReturnValue()
         {
          return isShared;
         }
     }); 
}

private void accessArray(Local local, final boolean isWrite)
{
PointsToSetInternal pts = (PointsToSetInternal) pag.reachingObjects(local);
pts.forall(new P2SetVisitor() {
        @Override
        public void visit(Node n) {

            int id = n.getNumber();
            XNode xn = indexNodeMap.get(id);
            if(xn==null)
            {
                xn = new XNode();
                indexNodeMap.put(id,xn);
            }
            xn.accessArray(currentThreadID,isWrite);
            if(currentThread.runsMany)
            {
                xn.accessArray((byte) (currentThreadID+1),isWrite);
            }

        }
    }); 
}

private void accessField(Local local, final SootField sf, final boolean isWrite)
{
 PointsToSetInternal pts = (PointsToSetInternal) pag.reachingObjects(local);
pts.forall(new P2SetVisitor() {
        @Override
        public void visit(Node n) {

            int id = n.getNumber();
            XNode xn = indexNodeMap.get(id);
            if(xn==null)
            {
                xn = new XNode();
                indexNodeMap.put(id,xn);
            }

        accessField(id,sf,isWrite);

        }
    });                 
}

private List<AllocNode> getMayAliasList(PointsToSetInternal pts)
{
    List<AllocNode> list = new ArrayList<AllocNode>();
    final HashSet<AllocNode> ret = new HashSet<AllocNode>();
    pts.forall( new P2SetVisitor() {
        public void visit( Node n ) {

            ret.add( (AllocNode)n );
        }
    } );
    Iterator<AllocNode> it = ret.iterator();
    while (it.hasNext()){
        list.add( it.next() );
    }
    return list;
}

/** Returns the points-to set for this node. */
public PointsToSetInternal getP2Set() {
    if( p2set != null ) {
        if( replacement != this ) throw new RuntimeException(
                "Node "+this+" has replacement "+replacement+" but has p2set" );
        return p2set;
    }
    Node rep = getReplacement();
    if( rep == this ) {
        return EmptyPointsToSet.v();
    }
    return rep.getP2Set();
}

/** Returns the points-to set for this node, makes it if necessary. */
public PointsToSetInternal makeP2Set() {
    if( p2set != null ) {
        if( replacement != this ) throw new RuntimeException(
                "Node "+this+" has replacement "+replacement+" but has p2set" );
        return p2set;
    }
    Node rep = getReplacement();
    if( rep == this ) {
        p2set = pag.getSetFactory().newSet( type, pag );
    }
    return rep.makeP2Set();
}

protected void checkAll( final Node container, PointsToSetInternal nodes,
        final Node upstream ) {
    nodes.forall( new P2SetVisitor() {
    public final void visit( Node n ) {
            checkNode( container, n, upstream );
        }
    } );
}

protected void checkNode( Node container, Node n, Node upstream ) {
    if( container.getReplacement() != container )
        throw new RuntimeException( "container "+container+" is illegal" );
    if( upstream.getReplacement() != upstream )
        throw new RuntimeException( "upstream "+upstream+" is illegal" );
    PointsToSetInternal p2set = container.getP2Set();
    FastHierarchy fh = pag.getTypeManager().getFastHierarchy();
    if( !p2set.contains( n ) 
            && ( fh == null || container.getType() == null ||
            fh.canStoreType( n.getType(), container.getType() ) ) ) {
        G.v().out.println( "Check failure: "+container+" does not have "+n
                +"; upstream is "+upstream );
    }
}

protected void handleSimples( VarNode src ) {
PointsToSetInternal srcSet = src.getP2Set();
if( srcSet.isEmpty() ) return;
final Node[] simpleTargets = pag.simpleLookup( src );
for (Node element : simpleTargets) {
           checkAll( element, srcSet, src );
}
   }

protected void handleStores( final VarNode src ) {
final PointsToSetInternal srcSet = src.getP2Set();
if( srcSet.isEmpty() ) return;
Node[] storeTargets = pag.storeLookup( src );
for (Node element : storeTargets) {
           final FieldRefNode fr = (FieldRefNode) element;
           checkAll( fr, srcSet, src );
}
   }

protected void handleLoads( final FieldRefNode src ) {
final Node[] loadTargets = pag.loadLookup( src );
       PointsToSetInternal set = src.getP2Set();
       if( set.isEmpty() ) return;
       for (Node element : loadTargets) {
           VarNode target = (VarNode) element;
           checkAll( target, set, src );
       }
   }

final protected void dfsVisit( VarNode v, VarNode rootOfSCC ) {
    if( visited.contains( v ) ) return;
    visited.add( v );
    Node[] succs = pag.simpleInvLookup( v );
    for (Node element : succs) {
        if( ignoreTypes
        || typeManager.castNeverFails( element.getType(), v.getType() ) ) {
            dfsVisit( (VarNode) element, rootOfSCC );
        }
    }
    if( v != rootOfSCC ) {
        if( !ignoreTypes ) {
            if( typeManager.castNeverFails(
                        v.getType(), rootOfSCC.getType() )
             && typeManager.castNeverFails(
                        rootOfSCC.getType(), v.getType() ) ) {
                rootOfSCC.mergeWith( v );
                numCollapsed++;
            }
        } else /* ignoreTypes */ {
            if( typeManager.castNeverFails(
                        v.getType(), rootOfSCC.getType() ) ) {
                rootOfSCC.mergeWith( v );
            } else if( typeManager.castNeverFails(
                        rootOfSCC.getType(), v.getType() ) ) {
                v.mergeWith( rootOfSCC );
            } else {
                rootOfSCC.getReplacement().setType( null );
                PointsToSetInternal set = rootOfSCC.getP2Set();
                if( set != null ) {
                    set.setType( null );
                }
                rootOfSCC.mergeWith( v );
            }
            numCollapsed++;
        }
    }
}

/**
 * Transform the result to SPARK style context insensitive points-to set.
 * The transformed result is stored in the points-to set of the querying pointer.
 * @param vn: the querying pointer
 * @return
 */
public PointsToSet toSparkCompatiableResult(VarNode vn)
{
    if ( !readyToUse) finish();

    PointsToSetInternal ptset = vn.makeP2Set();

    for ( VarType cv : outList ) {
        ptset.add(cv.var);
    }

    return ptset;
}

private PointsToSetInternal field_p2set( PointsToSet s, final SparkField f )
{
    if ( !(s instanceof PointsToSetInternal) )
        throw new RuntimeException( "Base pointers must be stored in *PointsToSetInternal*." );

    PointsToSetInternal bases = (PointsToSetInternal) s;
    final PointsToSetInternal ret = getSetFactory().newSet(f.getType(), this);

    bases.forall(new P2SetVisitor() {
        public final void visit(Node n) {
            Node nDotF = ((AllocNode) n).dot(f);
            if (nDotF != null) {
                //nDotF.getP2Set() has been discarded in solve()
                IVarAbstraction pn = consG.get(nDotF);
                if (pn == null
                        || hasTransformed 
                        || nDotF.getP2Set() != EmptyPointsToSet.v()) {
                    ret.addAll(nDotF.getP2Set(), null);
                    return;
                }

                pn = pn.getRepresentative();
                //PointsToSetInternal ptSet = nDotF.makeP2Set();
                for ( AllocNode obj : pn.get_all_points_to_objects() ) {
                    ret.add( obj );
                    //ptSet.add(obj);
                }
            }
        }
    });

    return ret;
}

@Override
public PointsToSet reachingObjects(Local l) 
{
    if ( !hasExecuted ) return super.reachingObjects(l);

    LocalVarNode vn = findLocalVarNode(l);
    if ( vn == null ) 
        return EmptyPointsToSet.v();

    IVarAbstraction pn = consG.get(vn);

    // In case this pointer has no geomPTA result
    // This is perhaps a bug
    if ( pn == null ) 
        return vn.getP2Set();

    // Return the cached result
    if ( hasTransformed ||
            vn.getP2Set() != EmptyPointsToSet.v() ) return vn.getP2Set();

    // Compute and cache the result
    pn = pn.getRepresentative();
    PointsToSetInternal ptSet = vn.makeP2Set();
    for ( AllocNode obj : pn.get_all_points_to_objects() ) {
        ptSet.add( obj );
    }

    return ptSet;
}

@Override
public PointsToSet reachingObjects(SootField f) 
{
    if ( !hasExecuted ) return super.reachingObjects(f);

    if( !f.isStatic() )
           throw new RuntimeException( "The parameter f must be a *static* field." );

       VarNode vn = findGlobalVarNode( f );
       if ( vn == null ) 
        return EmptyPointsToSet.v();

       IVarAbstraction pn = consG.get(vn);
       if( pn == null ) 
        return vn.getP2Set();

       // Lookup the cache
       if ( hasTransformed ||
        vn.getP2Set() != EmptyPointsToSet.v() ) return vn.getP2Set();   

       // We transform and cache the result for the next query
    pn = pn.getRepresentative();
    PointsToSetInternal ptSet = vn.makeP2Set();
    for ( AllocNode obj : pn.getRepresentative().get_all_points_to_objects() ) {
        ptSet.add( obj );
    }

    return ptSet;
}

public PointsToSet reachingObjects(AllocNode an, SootField f)
{
    AllocDotField adf = an.dot(f);
    IVarAbstraction pn = consG.get(adf);

    // No such pointer seen by SPARK
    if ( adf == null )
        return EmptyPointsToSet.v();

    // Not seen by geomPTA
    if ( pn == null )
        return adf.getP2Set();

    if ( hasTransformed ||
            adf.getP2Set() != EmptyPointsToSet.v() ) return adf.getP2Set(); 

        // We transform and cache the result for the next query
        pn = pn.getRepresentative();
        PointsToSetInternal ptSet = adf.makeP2Set();
        for ( AllocNode obj : pn.getRepresentative().get_all_points_to_objects() ) {
            ptSet.add( obj );
    }

    return ptSet;
}

/**
 * Builds an abstraction for the contents of an array. It is called on registered arrays.
 * @param nt
 * @param node
 */
public void resolveArray(NodeTable nt, AllocNode node) {
    if (pag == null) return;
    int id = node.getNumber();
    // Even if type stratification was defeated, we will not loop on an array containing itself.
    if (seen.contains(id)) return;
    seen.add(id);
    P2SetFactory ptsf = pag.getSetFactory();
    PointsToSetInternal pts = ptsf.newSet(node.getType(), pag);
    pts.add(node);
    PointsToSet contents = pag.reachingObjectsOfArrayElement(pts);
    AbsValue av = P2SAux.p2sContents(nt, contents);
    repositoryOtherArrays.put(id, av);
}

/**
 * Check if a points to set is non empty.
 * @param ptsRaw
 * @param m
 * @param obj
 */
public static void check (PointsToSet ptsRaw, SootMethod m, Unit st) {
    if (!(ptsRaw instanceof PointsToSetInternal)) return;
    PointsToSetInternal pts = (PointsToSetInternal) ptsRaw;
    if ((pts.size() != 0 && pts.getType() != null)) return;
    /*
    CallGraph cg = Scene.v().getCallGraph();
    System.out.println("**********" + st + "***************");
    showAncestor(cg,st, m,1 );
    */
}

public PointsToSetInternal getWrapped() {
  return wrapped;
}

public WrappedPointsToSet(final PointsToSetInternal wrapped) {
  super();
  this.wrapped = wrapped;
}

public PointsToSetInternal getP2set() {
  return p2set;
}

public void setP2set(PointsToSetInternal p2set) {
  this.p2set = p2set;
}

public abstract void handleMatchSrc(VarNode matchSrc,
PointsToSetInternal intersection, VarNode loadBase,
VarNode storeBase, VarAndContext origVarAndContext,
SparkField field, boolean refine);

protected boolean refineAliasInternal(VarNode v1, VarNode v2,
        PointsToSetInternal intersection, HeuristicType heuristic) {
    this.fieldCheckHeuristic = HeuristicType.getHeuristic(heuristic, pag
            .getTypeManager(), getMaxPasses());
    numPasses = 0;
    while (true) {
        numPasses++;
        if (DEBUG_PASS != -1 && numPasses > DEBUG_PASS) {
            return false;
        }
        if (numPasses > maxPasses) {
            return false;
        }
        if (DEBUG) {
            G.v().out.println("PASS " + numPasses);
            G.v().out.println(fieldCheckHeuristic);
        }
        clearState();
        boolean success = false;
        try {
            AllocAndContextSet allocAndContexts = findContextsForAllocs(
                    new VarAndContext(v1, EMPTY_CALLSTACK), intersection);
            boolean emptyIntersection = true;
            for (AllocAndContext allocAndContext : allocAndContexts) {
                CallingContextSet upContexts = findUpContextsForVar(
                        allocAndContext, new VarContextAndUp(v2,
                                EMPTY_CALLSTACK, EMPTY_CALLSTACK));
                if (!upContexts.isEmpty()) {
                    emptyIntersection = false;
                    break;
                }
            }
            success = emptyIntersection;
        } catch (TerminateEarlyException e) {
            success = false;
        }
        if (success) {
            G.v().out.println("took " + numPasses + " passes");
            return true;
        } else {
            if (!fieldCheckHeuristic.runNewPass()) {
                return false;
            }
        }
    }
}

/** Use the specified points-to set to replace current one */
public void setP2Set( PointsToSetInternal ptsInternal )
{
    p2set = ptsInternal;
}

@Override
public PointsToSet reachingObjects(Context c, Local l) 
{
    if ( !hasExecuted ) return super.reachingObjects(c, l);

    if ( hasTransformed ||
            !(c instanceof Unit) )
        return reachingObjects(l);

    LocalVarNode vn = findLocalVarNode(l);
    if ( vn == null ) 
        return EmptyPointsToSet.v();

    // Lookup the context sensitive points-to information for this pointer
    IVarAbstraction pn = consG.get(vn);
    if ( pn == null ) 
        return vn.getP2Set();

    pn = pn.getRepresentative();

    // Obtain the context sensitive points-to result
    SootMethod callee = vn.getMethod();
    Edge e = Scene.v().getCallGraph().findEdge((Unit) c, callee);
    if (e == null)
        return vn.getP2Set();

    // Compute the contexts interval
    CgEdge myEdge = getInternalEdgeFromSootEdge(e);
    if (myEdge == null)
        return vn.getP2Set();

    long low = myEdge.map_offset;
    long high = low + max_context_size_block[myEdge.s];

    // Lookup the cache
    ContextVarNode cvn = vn.context(c);
    if ( cvn != null ) {
        PointsToSetInternal ans = cvn.getP2Set();
        if ( ans != EmptyPointsToSet.v() ) return ans;
    }
    else {
        // Create a new context sensitive variable
        // The points-to vector is set to empty at start
        cvn = makeContextVarNode(vn, c);
    }

    // Fill
    PointsToSetInternal ptset = cvn.makeP2Set();
    for ( AllocNode an : pn.get_all_points_to_objects() ) {
        if ( pn.pointer_interval_points_to(low, high, an) )
            ptset.add(an);
    }

    return ptset;
}