import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private boolean meetIsectAndObjType(IntersectionType isectType,
        ObjectType objType) {
    ObjectType lhsObj = isectType.findObjectType();
    List<Type> isectTypes = isectType.getTypes();
    if (lhsObj != null) {
        Pair<ObjectType, Boolean> res = meetObjectTypes(lhsObj, objType);
        if (res.snd) {
            // need to replace object type in intersection
            for (int i = 0; i < isectTypes.size(); i++) {
                if (isectTypes.get(i).equals(lhsObj)) {
                    isectTypes.set(i, res.fst);
                    break;
                }
            }
            return true;
        }
        return false;
        // UGH.  need to write test for when something is used both as an object and a function.  sigh.
    } else {
        // add object type as a case
        isectTypes.add(objType);
        // we changed the type, so return true
        return true;
    }
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
 * collect the putstatic instructions in the call graph as {@link PathEdge} seeds for the analysis
 */
private Collection<PathEdge<BasicBlockInContext<IExplodedBasicBlock>>> collectInitialSeeds() {
  Collection<PathEdge<BasicBlockInContext<IExplodedBasicBlock>>> result = HashSetFactory.make();
  for (BasicBlockInContext<IExplodedBasicBlock> bb : supergraph) {
    IExplodedBasicBlock ebb = bb.getDelegate();
    SSAInstruction instruction = ebb.getInstruction();
    if (instruction instanceof SSAPutInstruction) {
      SSAPutInstruction putInstr = (SSAPutInstruction) instruction;
      if (putInstr.isStatic()) {
        final CGNode cgNode = bb.getNode();
        Pair<CGNode, Integer> fact = Pair.make(cgNode, ebb.getFirstInstructionIndex());
        int factNum = domain.add(fact);
        BasicBlockInContext<IExplodedBasicBlock> fakeEntry = getFakeEntry(cgNode);
        // note that the fact number used for the source of this path edge doesn't really matter
        result.add(PathEdge.createPathEdge(fakeEntry, factNum, bb, factNum));

      }
    }
  }
  return result;
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private Map<Pair<CGNode, Integer>, HashSet<String>> tagInvokeInsts() {
    Map<Pair<CGNode, Integer>, HashSet<String>> invokeInstTags = new HashMap<>();

    for (CGNode node : icfg.getCallGraph()) {
        String m = node.getMethod().getDeclaringClass().getName().toString();
        if (m.startsWith("Lprologue.js") || m.startsWith("Lpreamble.js"))
            continue;

        IR ir = node.getIR();
        if (ir == null) continue;

        SSAInstruction[] instructions = ir.getInstructions();
        for (int i = 0; i < instructions.length; i++) {
            SSAInstruction instruction = instructions[i];
            if (instruction instanceof JavaScriptInvoke) {
                JavaScriptInvoke invokeInst = (JavaScriptInvoke) instruction;
                Pair<CGNode, Integer> invokeInstItem = Pair.make(node, i);
                HashSet<String> tags = this.getReachingTags(node, invokeInst);
                invokeInstTags.put(invokeInstItem, tags);
            }
        }
    }

    return invokeInstTags;
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
protected SourceModule convertHTMLToJS(URL url) {
  SourceModule ret = null;
  try {
    Pair<Set<MappedSourceModule>,File> parsed = WebUtil.extractScriptFromHTML(url, true);
    File jsfile = parsed.snd; 
    //Dbg.dbg("JSFILE: " + jsfile.getAbsolutePath());
    Set<MappedSourceModule> sms = parsed.fst;
    if (sms.size() < 1) {
      Dbg.err("Nothing returned from WebUtil.extractScriptFromHTML");
    } else if (sms.size() > 1) {
      Dbg.err("Unexpected result from WebUtil.extractScriptFromHTML: " + sms);
    } else {
      ret = (MappedSourceModule)sms.toArray()[0];
    }
  } catch (Error ex) {
    Dbg.warn("Error converting HTML to script: " + ex.getMessage());
  }
  return ret;
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private Map makeValueNumbers(IR ir) {
   Map vns = new LinkedHashMap();
   for(Iterator is = iterateInstructions(ir); is.hasNext(); ) {
     SSAInstruction inst = (SSAInstruction)is.next();
     if (inst == null) continue;

     PointerKey[] uses = fieldAccesses.getUses(inst);
     int[] useValueNumbers = new int[ uses.length ];
     for(int j = 0; j < uses.length; j++) {
useValueNumbers[j] = getInitialFieldNumber( uses[j] );
     }
     vns.put(Pair.make(inst, USES), useValueNumbers);
     
     PointerKey[] defs = fieldAccesses.getDefs(inst);
     int[] defValueNumbers = new int[ defs.length ];
     for(int j = 0; j < defs.length; j++) {
defValueNumbers[j] = getInitialFieldNumber( defs[j] );
     }
     vns.put(Pair.make(inst, DEFS), defValueNumbers);
   }
   
   return vns;
 }
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private void handleFunctionReturnTerm(
        Consumer<IConstraint> constraintAdder,
        Set<Pair<ITypeTerm, Integer>> constrainedFunctionTerms,
        ITypeConstraint constraint) {
    FunctionReturnTerm returnTerm = (FunctionReturnTerm)(constraint.getLeft() instanceof FunctionReturnTerm ? constraint.getLeft() : constraint.getRight());
    ITypeTerm otherTerm = constraint.getLeft() instanceof FunctionReturnTerm ? constraint.getRight() : constraint.getLeft();
    ITypeTerm functionTerm = returnTerm.getFunctionTerm();
    int nrParams = returnTerm.getNrParams();
    // TODO make sure we handle constructors with parameters
    boolean isConstructorCall = otherTerm instanceof FunctionCallTerm &&
            ((FunctionCallTerm)otherTerm).getFunctionCall() instanceof NewExpression;
    doConstraintsForFunctionTerm(constraintAdder, constrainedFunctionTerms, functionTerm, nrParams, isConstructorCall);
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private void handleFunctionParamTerm(
        Consumer<IConstraint> constraintAdder,
        Set<Pair<ITypeTerm, Integer>> constrainedFunctionTerms,
        ITypeConstraint constraint) {
    FunctionParamTerm paramTerm = (FunctionParamTerm)(constraint.getLeft() instanceof FunctionParamTerm ? constraint.getLeft() : constraint.getRight());
    // create type variables for return type and parameters
    ITypeTerm functionTerm = paramTerm.getFunctionTerm();
    int nrParams = paramTerm.getNrParams();
    doConstraintsForFunctionTerm(constraintAdder,
            constrainedFunctionTerms, functionTerm, nrParams, false);
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
 * meet two object types.
 * @param lTy
 * @param rTy
 * @return <O,b> where O is the meeted type, and b is true if this type differs from lTy.  If b is false, O is null.
 */
private Pair<ObjectType,Boolean> meetObjectTypes(ObjectType lTy, ObjectType rTy) {
    boolean changed = false;
    List<Property> props = new ArrayList<Property>();
    for (Property p : rTy.properties()) {
        String propName = p.getName();
        if (lTy.hasProperty(propName)) {

            logger.debug("Common property: {}", propName);

            Property lProp = lTy.getProperty(propName);
            Property rProp = rTy.getProperty(propName);
            typeEquator.accept(lProp.getType(), rProp.getType());
            if (lProp.isRO() && rProp.isRW()) {
                props.add(new Property(lProp.getName(), lProp.getType(), false, rProp.getSourceLoc()));
                changed = true;
            } else {
                props.add(lProp);
            }

        } else {
            logger.debug("Adding property: {}", propName);
            props.add(p);
            changed = true;
        }
    }
    if (changed) {
        // create a fresh ObjectType for the meet result
        // first we need to add the lTy properties that are not on rTy
        List<Property> lTyPropsToKeep = lTy.properties().stream()
                .filter((p) -> {
                    return !rTy.hasProperty(p.getName());
                }).collect(Collectors.toList());
        props.addAll(lTyPropsToKeep);
        ObjectType meetResult = new ObjectType(props);
        return Pair.make(meetResult,changed);
    }
    return Pair.make(null,changed);

}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
 * generate a numbering of the putstatic instructions
 */
@SuppressWarnings("unchecked")
private OrdinalSetMapping<Pair<CGNode, Integer>> numberPutStatics() {
  ArrayList<Pair<CGNode, Integer>> putInstrs = new ArrayList<Pair<CGNode, Integer>>();
  for (CGNode node : icfg.getCallGraph()) {
    IR ir = node.getIR();
    if (ir == null) {
      continue;
    }
    SSAInstruction[] instructions = ir.getInstructions();
    for (int i = 0; i < instructions.length; i++) {
      SSAInstruction instruction = instructions[i];
      if (instruction instanceof SSAPutInstruction && ((SSAPutInstruction) instruction).isStatic()) {
        SSAPutInstruction putInstr = (SSAPutInstruction) instruction;
        // instrNum is the number that will be assigned to this putstatic
        int instrNum = putInstrs.size();
        putInstrs.add(Pair.make(node, i));
        // also update the mapping of static fields to def'ing statements
        IField field = cha.resolveField(putInstr.getDeclaredField());
        assert field != null;
        BitVector bv = staticField2DefStatements.get(field);
        if (bv == null) {
          bv = new BitVector();
          staticField2DefStatements.put(field, bv);
        }
        bv.set(instrNum);
      }
    }
  }
  return new ObjectArrayMapping<Pair<CGNode, Integer>>(putInstrs.toArray(new Pair[putInstrs.size()]));
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
 * perform the tabulation analysis and return the {@link TabulationResult}
 */
public TabulationResult<BasicBlockInContext<IExplodedBasicBlock>, CGNode, Pair<CGNode, Integer>> analyze() {
  PartiallyBalancedTabulationSolver<BasicBlockInContext<IExplodedBasicBlock>, CGNode, Pair<CGNode, Integer>> solver = PartiallyBalancedTabulationSolver
      .createPartiallyBalancedTabulationSolver(new ReachingDefsProblem(), null);
  TabulationResult<BasicBlockInContext<IExplodedBasicBlock>, CGNode, Pair<CGNode, Integer>> result = null;
  try {
    result = solver.solve();
  } catch (CancelException e) {
    // this shouldn't happen 
    assert false;
  }
  return result;

}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
protected int getNumberOfDefs(SSAInstruction inst) {
  if (fieldPhiSet.contains(inst)) {
    return inst.getNumberOfDefs();
  } else {
  	int[] defs = (int[])valueNumbers.get(Pair.make(inst, DEFS));
  	if ( defs == null) {
  		return 0;
  	} else { 
  		return defs.length;
  	}
  }
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
protected int getDef(SSAInstruction inst, int index) {
  if (fieldPhiSet.contains(inst)) {
    return inst.getDef(index);
  } else {
    return ((int[])valueNumbers.get(Pair.make(inst, DEFS)))[index];
  }
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
protected int getNumberOfUses(SSAInstruction inst) {
  if (fieldPhiSet.contains(inst)) {
    return inst.getNumberOfUses();
  } else {
    return ((int[])valueNumbers.get(Pair.make(inst, USES))).length;
  }
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
protected int getUse(SSAInstruction inst, int index) {
  if (fieldPhiSet.contains(inst)) {
    return inst.getUse(index);
  } else {
    return ((int[])valueNumbers.get(Pair.make(inst, USES)))[index];
  }
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
public UnaryOperator getNodeTransferFunction(Object node) {
if (node instanceof Pair) {
  return identityTransferFunction;
} else {
  return new NodeTransferFunction((CGNode)node);
}
     }
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private BiMap<Pair<TypeLabel, Integer>, Integer> createOriginal2Optimized(Set<TypeLabel> labels, Set<Integer> keySet, int maxLocals) {
	BiMap<Pair<TypeLabel, Integer>, Integer> map = HashBiMap.create(keySet.size());
	
	int optLocal = maxLocals + 1;
	
	for (TypeLabel label : labels) {
		
		for (Integer originalLocal : keySet) {
			map.put(Pair.make(label, originalLocal), optLocal);
			optLocal++;
		}
	}
	return map;
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
public int getLocalForLabel(TypeLabel from, TypeLabel to, int local) {
	
	if (from == null) {
		return locals.get(Pair.make(to, local));
	} else {
		int orgLocal = locals.inverse().get(local).snd;
		
		if (to != null) {
			return locals.get(Pair.make(to, orgLocal));
		} else {
			return orgLocal;
		}
	}
}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
private void handleIndexedTerm(Consumer<IConstraint> constraintAdder,
            Set<ITypeTerm> constrainedIndexTerms,
            Set<Pair<ITypeTerm, Integer>> constrainedFunctionTerms,
            ITypeConstraint constraint) {
        IndexedTerm indexedTerm = (IndexedTerm)(constraint.getLeft() instanceof IndexedTerm ? constraint.getLeft() : constraint.getRight());
        ITypeTerm base = indexedTerm.getBase();
        // TODO temporary hack until we handle function types; remove this condition!
//                if (base instanceof FunctionReturnTerm) continue;
        if (!constrainedIndexTerms.contains(base)) {
            ITypeTerm other = constraint.getLeft() instanceof IndexedTerm ? constraint.getRight() : constraint.getLeft();
            TypeVar elemTypeVar = makeFreshTypeVar();
            TypeVariableTerm elemTypeVarTerm = factory.findOrCreateTypeVariableTerm(elemTypeVar);
            if (base instanceof ArrayLiteralTerm) {
                // mutate the array type to use our elements type variable
                ArrayType arrType = (ArrayType)((ArrayLiteralTerm)base).getType();
                arrType.setElemType(elemTypeVar);
            } else if (base instanceof MapLiteralTerm) {
                // mutate to use our elements type variable
                MapType mapType = (MapType)((MapLiteralTerm)base).getType();
                mapType.setElemType(elemTypeVar);
            } else if (other.toString().startsWith("TP(")) { // TODO HACK!
                // we know we're talking about an array in this case, so
                // don't introduce a type variable for the key
                ArrayType arrayType = new ArrayType(elemTypeVar);
                constraintAdder.accept(new SubTypeConstraint(base, factory.getTermForType(arrayType)));
                // hack!  make sure return type of "push" is an int
                PropertyAccessTerm pushTerm = factory.findOrCreatePropertyAccessTerm(base, "push", null);
                FunctionReturnTerm pushRetTerm = factory.findOrCreateFunctionReturnTerm(pushTerm, 1);
                constraintAdder.accept(new TypeEqualityConstraint(
                        pushRetTerm, factory.getTermForType(IntegerType
                                .make())));
                // another hack!  need this to handle Array function
                if (base instanceof FunctionReturnTerm
                        && base.toString().equals("ret(|Array|)")) {
                    doConstraintsForFunctionTerm(constraintAdder,
                            constrainedFunctionTerms,
                            ((FunctionReturnTerm) base)
                                    .getFunctionTerm(),
                            ((FunctionReturnTerm) base).getNrParams(), false);
                }
            } else {
                TypeVar keyTypeVar = makeFreshTypeVar();
                TypeVariableTerm keyTypeVarTerm = factory.findOrCreateTypeVariableTerm(keyTypeVar);
                UnknownIndexableType mapOrArrayType = new UnknownIndexableType(keyTypeVar, elemTypeVar);
                constraintAdder.accept(new SubTypeConstraint(base, factory.getTermForType(mapOrArrayType)));
                constraintAdder.accept(new TypeEqualityConstraint(keyTypeVarTerm, factory.findOrCreateKeyTerm(base)));
            }
            // always constrain the element type
            constraintAdder.accept(new TypeEqualityConstraint(elemTypeVarTerm, indexedTerm));
            constrainedIndexTerms.add(base);
        }
    }
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
	   * Usage: CSReachingDefsDriver -scopeFile file_path -mainClass class_name
	   * 
	   * Uses main() method of class_name as entrypoint.
	   * 
	   * @throws IOException
	   * @throws ClassHierarchyException
	   * @throws CallGraphBuilderCancelException
	   * @throws IllegalArgumentException
	   */
	  public static void main(String[] args) throws IOException, ClassHierarchyException, IllegalArgumentException, CallGraphBuilderCancelException {
	    long start = System.currentTimeMillis();		
	    Properties p = CommandLine.parse(args);
	    String scopeFile = p.getProperty("scopeFile");
	    if (scopeFile == null) {
	    	throw new IllegalArgumentException("must specify scope file");
	    }
	    String mainClass = p.getProperty("mainClass");
	    if (mainClass == null) {
	      throw new IllegalArgumentException("must specify main class");
	    }
	    AnalysisScope scope = AnalysisScopeReader.readJavaScope(scopeFile, null, CSReachingDefsDriver.class.getClassLoader());
	    ExampleUtil.addDefaultExclusions(scope);
	    IClassHierarchy cha = ClassHierarchyFactory.make(scope);
	    System.out.println(cha.getNumberOfClasses() + " classes");
	    System.out.println(Warnings.asString());
	    Warnings.clear();
	    AnalysisOptions options = new AnalysisOptions();
	    Iterable<Entrypoint> entrypoints = Util.makeMainEntrypoints(scope, cha, mainClass);
	    options.setEntrypoints(entrypoints);
	    // you can dial down reflection handling if you like
	    options.setReflectionOptions(ReflectionOptions.NONE);
	    AnalysisCache cache = new AnalysisCacheImpl();
	    // other builders can be constructed with different Util methods
	    CallGraphBuilder builder = Util.makeZeroOneContainerCFABuilder(options, cache, cha, scope);
//	    CallGraphBuilder builder = Util.makeNCFABuilder(2, options, cache, cha, scope);
//	    CallGraphBuilder builder = Util.makeVanillaNCFABuilder(2, options, cache, cha, scope);
	    System.out.println("building call graph...");
	    CallGraph cg = builder.makeCallGraph(options, null);
//	    System.out.println(cg);
	    long end = System.currentTimeMillis();
	    System.out.println("done");
	    System.out.println("took " + (end-start) + "ms");
	    System.out.println(CallGraphStats.getStats(cg));
	    
	    ContextSensitiveReachingDefs reachingDefs = new ContextSensitiveReachingDefs(cg, cache);
	    TabulationResult<BasicBlockInContext<IExplodedBasicBlock>, CGNode, Pair<CGNode, Integer>> result = reachingDefs.analyze();
	    ISupergraph<BasicBlockInContext<IExplodedBasicBlock>, CGNode> supergraph = reachingDefs.getSupergraph();

	    // TODO print out some analysis results
	}
 

import com.ibm.wala.util.collections.Pair; //导入依赖的package包/类
/**
 * gets putstatic instruction corresponding to some fact number from a bitvector in the analysis result
 */
public Pair<CGNode, Integer> getNodeAndInstrForNumber(int num) {
  return putInstrNumbering.getMappedObject(num);
}