Java 类soot.jimple.AnyNewExpr 实例源码

/**
 * Construct the appropriate NEW expression depending on the given Soot
 * type. It handles RefType and ArrayType types.
 * 
 * @param type
 * @return
 */
public AnyNewExpr getNewExpression(Type type) {
    if (type instanceof RefType) {
        return Jimple.v().newNewExpr((RefType) type);
    } else if (type instanceof ArrayType) {
        ArrayType arrayType = (ArrayType) type;
        if (arrayType.numDimensions <= 1) {
            return Jimple.v().newNewArrayExpr(arrayType.baseType, IntConstant.v(1));
        } else {
            // Create the list of sizes for the array dimensions
            List<Value> sizes = new ArrayList<Value>();
            for (int i = 0; i < arrayType.numDimensions; i++) {
                sizes.add(IntConstant.v(1));
            }

            return Jimple.v().newNewMultiArrayExpr(arrayType, sizes);
        }
    }

    throw new IllegalArgumentException("Type " + type + " cannot be instantiated.");
}

/**
 * Adds an edge between two sites with a given field.
 */
@SuppressWarnings("unused")
private void addEdge(AnyNewExpr n1, SootField field, AnyNewExpr n2) {
    // No edge from null
    assert_tmp (n1 != null && n2 != null && field != null);

    // Ensure nodes exist in the heap
    ensureNode(n1);
    ensureNode(n2);

    // Add the field edge to a copy of the current edges.
    Map<SootField,Set<AnyNewExpr>> oldEdges = heap.get(n1);
    Map<SootField,Set<AnyNewExpr>> newEdges = new HashMap<SootField,Set<AnyNewExpr>>(oldEdges);
    Set<AnyNewExpr> oldTargets = oldEdges.containsKey(field) ? oldEdges.get(field) : new HashSet<AnyNewExpr>();
    Set<AnyNewExpr> newTargets = new HashSet<AnyNewExpr>(oldTargets);
    boolean change = newTargets.add(n2);
    if (change) {
        newEdges.put(field, Collections.unmodifiableSet(newTargets));
        heap.put(n1, Collections.unmodifiableMap(newEdges));
    }
}

/**
 * Adds an edge between a variable and a node.
 */
@SuppressWarnings("unused")
private void addEdge(Local var, AnyNewExpr node) {
    assert_tmp(var != null && node != null);

    // Ensure entry exists for field edges.
    ensureNode(node);

    // Add the root variable edge.
    Set<AnyNewExpr> oldPointees = roots.containsKey(var) ? roots.get(var) : new HashSet<AnyNewExpr>();
    Set<AnyNewExpr> newPointees = new HashSet<AnyNewExpr>(oldPointees);
    boolean change = newPointees.add(node);
    if (change) {
        roots.put(var, Collections.unmodifiableSet(newPointees)); 
    }
}

/**
 * Loads a field of an object into a root variable.
 */
public void getField(Local lhs, Local rhs, SootField field) {
    // Find whatever the RHS->F was pointing to.
    Set<AnyNewExpr> rhsPointees = roots.get(rhs);       
    Set<AnyNewExpr> rhsFieldPointees = new HashSet<AnyNewExpr>();
    for (AnyNewExpr src : rhsPointees) {
        if (src == null) {
            throw new NullPointerException();
        } else if (src == SUMMARY_NODE) { 
            rhsFieldPointees.add(SUMMARY_NODE);
        }else if (heap.get(src).containsKey(field)) {
            Set<AnyNewExpr> targets = heap.get(src).get(field);
            rhsFieldPointees.addAll(targets);
        }
    }

    // Add the indirect pointees to the LHS edges
    roots.put(lhs, Collections.unmodifiableSet(rhsFieldPointees)); 

    // Ensure reachability.
    gc();
}

@Override
public String toString() {
    StringBuffer sb = new StringBuffer();

    for (Local var : roots.keySet()) {
        sb.append(var).append(" -> ");
        for (AnyNewExpr node : roots.get(var)) {
            sb.append(node2String(node)).append(" ");
        }
        sb.append("\n");
    }

    for (AnyNewExpr source : heap.keySet()) {
        for (SootField field : heap.get(source).keySet()) {
            sb.append(node2String(source)).append(".").append(field.isStatic() ? field.toString() : field.getName()).append(" -> ");
            for (AnyNewExpr target : heap.get(source).get(field)) {
                sb.append(node2String(target)).append(" ");
            }
            sb.append("\n");
        }
    }

    return sb.toString();
}

/** 
 * Constructs a copy of the given points-to graph.
 * 
 * @param other the points-to graph to copy
 */
public PointsToGraph(PointsToGraph other) {
    // As the data inside the top-level maps are immutable, just a shallow
    // copy will suffice
    this.roots = new HashMap<Local,Set<AnyNewExpr>>(other.roots);
    this.heap = new HashMap<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>>(other.heap);
}

/**
 * Assigns the sticky local to a parameter.
 */
public void assignSticky(Local sticky, Local parameter) {
    Set<AnyNewExpr> rhsTargets = roots.get(parameter);
    Set<AnyNewExpr> lhsTargets = new HashSet<AnyNewExpr>(roots.get(sticky));
    boolean change = lhsTargets.addAll(rhsTargets);
    if (change) {
        roots.put(sticky, Collections.unmodifiableSet(lhsTargets));
    }
}

/**
 * Assigns a root variable to a new object at a given allocation site.
 */
public void assignNew(Local lhs, AnyNewExpr allocSite) {

    // If creating a new string or class, re-use the constant site
    if (allocSite != SUMMARY_NODE) {
        if (allocSite.getType().equals(STRING_CONST.getType())) {
            allocSite = STRING_SITE;
        } else if (allocSite.getType().equals(CLASS_CONST.getType())) {
            allocSite = CLASS_SITE;
        }
    }

    // We do not handle multi-dimensional arrays in this version
    if (allocSite instanceof NewMultiArrayExpr) {
        allocSite = SUMMARY_NODE;
    }

    // Create this node in the heap, if it doesn't already exist
    newNode(allocSite, false);

    // Assign LHS to the new node
    Set<AnyNewExpr> target = new HashSet<AnyNewExpr>();
    target.add(allocSite);
    roots.put(lhs, Collections.unmodifiableSet(target));

    // Ensure reachability.
    gc();
}

/**
 * Assigns a set of targets to a root variable.
 */
void assignGlobals(Local lhs, Set<AnyNewExpr> targets) {
    // Ensure all nodes exist in the heap
    for (AnyNewExpr allocSite : targets) {
        newNode(allocSite, true);
    }

    // Assign LHS to all these nodes
    roots.put(lhs, Collections.unmodifiableSet(targets));

    // Ensure reachability.
    gc();
}

public void summarizeTargetFields(Local lhs) {
    Set<AnyNewExpr> targets = roots.get(lhs);
    // Summarize nodes
    for (AnyNewExpr allocSite : targets) {
        newNode(allocSite, true);
    }
}

private String node2String(AnyNewExpr node) {
    if (node == SUMMARY_NODE) {
        return "SUMMARY";
    } else if (node == STRING_SITE) {
        return "STRING";
    } else if (node == CLASS_SITE) {
        return "CLASS";
    } else {
        return "[" + node.toString() + " (" + node.hashCode() + ")]";
    }
}

/**
 * Computes the targets of an invoke expression using a given points-to graph.
 * 
 * <p>For static invocations, there is only target. For instance method
 * invocations, the targets depend on the type of receiver objects pointed-to
 * by the instance variable whose method is being invoked.</p>
 * 
 * <p>If the instance variable points to a summary node, then the returned
 * value is <tt>null</tt> signifying a <em>default</em> call-site.</p>
 */
private Set<SootMethod> getTargets(SootMethod callerMethod, Stmt callStmt, InvokeExpr ie, PointsToGraph ptg) {
    Set<SootMethod> targets = new HashSet<SootMethod>();
    SootMethod invokedMethod = ie.getMethod();
    String subsignature = invokedMethod.getSubSignature();

    // Static and special invocations refer to the target method directly
    if (ie instanceof StaticInvokeExpr || ie instanceof SpecialInvokeExpr) {
        targets.add(invokedMethod);
        return targets;
    } else {
        assert (ie instanceof InterfaceInvokeExpr || ie instanceof VirtualInvokeExpr);
        // Get the receiver
        Local receiver = (Local) ((InstanceInvokeExpr) ie).getBase();
        // Get what objects the receiver points-to
        Set<AnyNewExpr> heapNodes = ptg.getTargets(receiver);
        if (heapNodes != null) {
            // For each object, find the invoked method for the declared type
            for (AnyNewExpr heapNode : heapNodes) {
                if (heapNode == PointsToGraph.SUMMARY_NODE) {                       
                    // If even one pointee is a summary node, then this is a default site
                    return null;
                } else if (heapNode instanceof NewArrayExpr) {
                    // Probably getClass() or something like that on an array
                    return null;
                }
                // Find the top-most class that declares a method with the given
                // signature and add it to the resulting targets
                SootClass sootClass = ((RefType) heapNode.getType()).getSootClass();
                do {
                    if (sootClass.declaresMethod(subsignature)) {
                        targets.add(sootClass.getMethod(subsignature));
                        break;
                    } else if (sootClass.hasSuperclass()) {
                        sootClass = sootClass.getSuperclass();
                    } else {
                        sootClass = null;
                    }
                } while (sootClass != null);
            }
        }
        if (targets.isEmpty()) {
            // System.err.println("Warning! Null call at: " + callStmt+ " in " + callerMethod);
        }
        return targets;
    }
}

/**
 * Constructs a new empty points-to graph.
 */
public PointsToGraph() {
    roots = new HashMap<Local,Set<AnyNewExpr>>();
    heap = new HashMap<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>>();
}

/**
 * Assigns a root variable to a root variable.
 */
public void assign(Local lhs, Local rhs) {      
    // Find whatever the RHS was pointing to.
    Set<AnyNewExpr> rhsTargets = roots.get(rhs);

    // We will fill this up with correctly typed targets
    Set<AnyNewExpr> lhsTargets = new HashSet<AnyNewExpr>();
    Type lhsType = lhs.getType();
    if (lhsType instanceof ArrayType) {
        lhsType = ((ArrayType) lhsType).baseType;
    }
    if (rhsTargets != null) {
        // Handle references and arrays separately
        if (lhsType instanceof RefType) {
            SootClass toClass = ((RefType) lhsType).getSootClass();
            for (AnyNewExpr rhsTarget : rhsTargets) {
                // Handle only instance objects
                if (rhsTarget instanceof AnyNewExpr) {
                    // Do not type-check for summary nodes and when the LHS is java.lang.Object
                    if (rhsTarget == SUMMARY_NODE || lhsType.equals(Scene.v().getObjectType())) {
                        // Add by default
                        lhsTargets.add(rhsTarget);
                        continue;
                    }
                    Type rhsTargetType = rhsTarget.getType();
                    if (rhsTargetType instanceof ArrayType) {
                        rhsTargetType = ((ArrayType) rhsTargetType).baseType;
                    }
                    // If the type (or base type) is reftype, then type-check
                    if (rhsTargetType instanceof RefType) {
                        SootClass fromClass = ((RefType) rhsTargetType).getSootClass();
                        if (PointsToGraph.canCast(fromClass, toClass)) {
                            // Yes, add this target
                            lhsTargets.add(rhsTarget);
                        }
                    } else {
                        // For non-ref base types (e.g. char[]), just add
                        lhsTargets.add(rhsTarget);
                    }
                }
            }
        } else if (lhsType instanceof ArrayType) {
            // We are not so fickle about arrays
            lhsTargets.addAll(rhsTargets);
        }
    }

    // Add the targets to the LHS edges.
    roots.put(lhs, Collections.unmodifiableSet(lhsTargets)); 

    // Ensure reachability
    gc();
}

/**
 * Ensures the given node is in the heap.
 */
private void ensureNode(AnyNewExpr node) {
    // WARNING: No fields are added if this is used!
    if (node != null && !heap.containsKey(node))
        heap.put(node, Collections.unmodifiableMap(new HashMap<SootField,Set<AnyNewExpr>>()));
}

/**
 * Removes all unreachable nodes from the edge sets.
 */
public void gc() {
    // Maintain a work-list of (reachable) nodes to process.
    LinkedList<AnyNewExpr> worklist = new LinkedList<AnyNewExpr>();

    // Add all the nodes pointed-to by root variables to the work-list.
    for (Set<AnyNewExpr> nodes : roots.values()) {
        worklist.addAll(nodes);
    }

    // Start with an empty field map (save the old one!)
    Map<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>> oldHeap = this.heap;
    Map<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>> newHeap = new HashMap<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>>();

    // Process work-list.
    while (!worklist.isEmpty()) {
        // Get the next element
        AnyNewExpr node = worklist.remove();
        // Ignore null pointees from the work-list
        if (node == null)
            throw new NullPointerException();
        // If this is already there in the new map, then ignore (duplicate
        // processing)
        if (newHeap.containsKey(node))
            continue;

        // Otherwise, just get the original stuff back
        // No need to do deep copy as (1) it is our own data and (2) target
        // nodes of edges will be reachable
        // (3) Also oldHeap.get(node) should return an unmodifiable map
        newHeap.put(node, oldHeap.get(node)); 

        // Add targets of this node to the work-list.
        for (Set<AnyNewExpr> targets : newHeap.get(node).values()) {
            worklist.addAll(targets);
        }

    }

    // Set this heap to the new minimal heap
    this.heap = newHeap;

}

/**
 * Returns the points-to set of a root variable.
 */
public Set<AnyNewExpr> getTargets(Local local) {
    return roots.get(local);
}

/**
 * Stores values pointed-to by one root variable into a field of objects pointed-to by another root variable.
 */
public void setField(Local lhs, SootField field, Local rhs) {
    // You can't set field of a non-existent variable.
    assert_tmp (roots.containsKey(lhs));

    // Since we are doing weak updates, nothing to do if setting field to null
    if (rhs == null)
        return;

    // Find the objects whose field is being modified.
    Set<AnyNewExpr> lhsPointees = roots.get(lhs);
    // Find the objects to which the fields will now point to.
    Set<AnyNewExpr> rhsPointees = roots.get(rhs);

    // LHS variable should exist
    if (lhsPointees == null)
        throw new NullPointerException();

    // RHS variable should exist
    if (rhsPointees == null)
        throw new NullPointerException();

    // If the RHS variable exists, but points to nothing, then bye-bye
    if(rhsPointees.size() == 0)
        return;

    boolean summarizeRhsTargets = false;

    // For each object that the LHS points to, add to it's field the RHS pointee
    for (AnyNewExpr node : lhsPointees) {
        if (node == null)
            throw new NullPointerException();
        if (node == SUMMARY_NODE) {
            // Don't add any edge to SUMMARY, but note it down so
            // that we can summarize fields of RHS pointees
            summarizeRhsTargets = true;
            continue;
        }
        // Add the new edges (copy-and-modify as edges are immutable)
        Map<SootField,Set<AnyNewExpr>> oldEdges = heap.get(node);
        Map<SootField,Set<AnyNewExpr>> newEdges = new HashMap<SootField,Set<AnyNewExpr>>(oldEdges);
        Set<AnyNewExpr> oldTargets = oldEdges.get(field);
        if (oldTargets == null) {
            if (node == GLOBAL_SITE) {
                // If the node is global, then field must be static
                assert_tmp(field.isStatic());
                // In that case, we allow this condition
                oldTargets = new HashSet<AnyNewExpr>();
            } else {
                // Otherwise not acceptable as we are doing type-checking
                System.err.println(this);
                throw new RuntimeException("Field not found: " + field + " in " + node);
            }
        }
        Set<AnyNewExpr> newTargets = new HashSet<AnyNewExpr>(oldTargets);
        boolean change = newTargets.addAll(rhsPointees);
        if (change) {
            newEdges.put(field, Collections.unmodifiableSet(newTargets));
            heap.put(node, Collections.unmodifiableMap(newEdges));
        }
    }

    // If the LHS local pointed to SUMMARY, then we must summarize all
    // fields of the RHS pointees as we do not know if any such edge
    // could be created (since we are not maintaining edges out of SUMMARY)
    if (summarizeRhsTargets) {
        summarizeTargetFields(rhs);
    }
}

/**
 * Stores a new object into a field of objects pointed-to by a root variable.
 */
public void setFieldNew(Local lhs, SootField field, AnyNewExpr allocSite) {     
    // You can't set field of a non-existent variable.
    assert_tmp (roots.containsKey(lhs));

    // Create this node in the heap, if it doesn't already exist
    newNode(allocSite, false);

    // Find the objects whose field is being modified.
    Set<AnyNewExpr> lhsPointees = roots.get(lhs);
    // Find the objects to which the fields will now point to.
    Set<AnyNewExpr> rhsPointees = new HashSet<AnyNewExpr>();
    rhsPointees.add(allocSite);

    // LHS variable should exist
    if (lhsPointees == null)
        throw new NullPointerException();



    // For each object that the LHS points to, add to it's field the RHS pointee
    for (AnyNewExpr node : lhsPointees) {
        if (node == null)
            throw new NullPointerException();
        if (node == SUMMARY_NODE) // Don't add any edge to SUMMARY
            continue; 
        // Add the new edges (copy-and-modify as edges are immutable)
        Map<SootField,Set<AnyNewExpr>> oldEdges = heap.get(node);
        Map<SootField,Set<AnyNewExpr>> newEdges = new HashMap<SootField,Set<AnyNewExpr>>(oldEdges);
        Set<AnyNewExpr> oldTargets = oldEdges.get(field);
        // Check to see if this node had edges with the given field
        if (oldTargets == null) {
            if (node == GLOBAL_SITE) {
                // If the node is global, then field must be static
                assert_tmp(field.isStatic());
                // In that case, we allow this condition
                oldTargets = new HashSet<AnyNewExpr>();
            } else {
                // Otherwise not acceptable as we are doing type-checking
                throw new RuntimeException("Field not found: " + field + " in " + node);
            }
        }
        Set<AnyNewExpr> newTargets = new HashSet<AnyNewExpr>(oldTargets);
        boolean change = newTargets.addAll(rhsPointees);
        if (change) {
            newEdges.put(field, Collections.unmodifiableSet(newTargets));
            heap.put(node, Collections.unmodifiableMap(newEdges));
        }
    }

}

/**
 * Removes nodes contained in the argument. This is used at 
 * call-edges.
 */
public void subtractHeap(PointsToGraph other) {
    for (AnyNewExpr heapNode : other.heap.keySet()) {
        this.heap.remove(heapNode);
    }
}

/**
 * Returns <tt>true</tt> only if there is an edge
 * from the given root variable to the given heap node.
 */
public boolean containsEdge(Local var, AnyNewExpr node) {
    return roots.get(var).contains(node);
}