<file_sep>package org.opensource.analysis.byclass;

import org.objectweb.asm.ClassReader;
import org.objectweb.asm.ClassVisitor;

import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
import java.net.URLClassLoader;
import java.nio.file.Paths;
import java.util.List;

public class ClassCallGraph {

    public static void main(String[] args) throws IOException {
        URL url = Paths.get("/Users/lvtu/workspace/java-callgraph/target/classes").toUri().toURL();
        ClassLoader cl = new URLClassLoader(new URL[]{url});
        InputStream ins = cl.getResourceAsStream("org/opensource/analysis/bysource/SourceCallGraph.class");

        ClassReader cr = new ClassReader(ins);

        ClassVisitor cw = new ClassCallVisitor();
        cr.accept(cw, ClassReader.EXPAND_FRAMES);
    }

}
<file_sep>package org.opensource.analysis.parse;

public interface ICallGraph {

    void callGraph(String className, String method);

    void search(String className, String method);

}
<file_sep>package org.opensource.analysis.parse.graph;

public interface MethodEdge {
}
<file_sep>package org.opensource.analysis.byclass;

import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class MethodCallVisitor extends MethodVisitor {

    private final static Logger logger = LoggerFactory.getLogger(MethodCallVisitor.class);

    public MethodCallVisitor() {
        super(Opcodes.ASM7);
    }

    @Override
    public void visitMethodInsn(int opcode, String owner, String name, String descriptor, boolean isInterface) {
        if (name.equals("<init>") || owner.startsWith("java")) {
            super.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
            return;
        }
        logger.info("-> {}.{}", owner, name);
    }

    @Override
    public void visitCode() {
        super.visitCode();
    }

    @Override
    public void visitMaxs(int maxStack, int maxLocals) {
        super.visitMaxs(maxStack, maxLocals);
    }
}
<file_sep>package org.opensource.analysis.parse.structure;

import org.objectweb.asm.Opcodes;

public class MethodrefInfo {

    private int opcode;
    private String owner;
    private String name;
    private String descriptor;
    private boolean isInterface;
    private boolean resolvedResult;

    public MethodrefInfo(int opcode, String owner, String name, String descriptor, boolean isInterface) {
        this.opcode = opcode;
        this.owner = owner;
        this.name = name;
        this.descriptor = descriptor;
        this.isInterface = isInterface;
    }

    public boolean isInvokeVirtual() {
        return opcode == Opcodes.INVOKEVIRTUAL;
    }

    public boolean isInvokeInterface() {
        return opcode == Opcodes.INVOKEINTERFACE;
    }

    public boolean isInvokeSpecial() {
        return opcode == Opcodes.INVOKESPECIAL;
    }

    public boolean isInvokeStatic() {
        return opcode == Opcodes.INVOKESTATIC;
    }

    public boolean isInvokeDynamic() {
        return opcode == Opcodes.INVOKEDYNAMIC;
    }

    public int getOpcode() {
        return opcode;
    }

    public String getOwner() {
        return owner;
    }

    public String getName() {
        return name;
    }

    public String getDescriptor() {
        return descriptor;
    }

    public boolean isResolvedResult() {
        return resolvedResult;
    }

    public void setResolvedResult(boolean resolvedResult) {
        this.resolvedResult = resolvedResult;
    }
}
<file_sep>package org.opensource.analysis.parse;

import org.apache.commons.lang3.StringUtils;
import org.opensource.analysis.parse.structure.ClassInfo;
import org.opensource.analysis.parse.structure.MethodInfo;
import org.opensource.analysis.parse.structure.MethodrefInfo;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

public class ClassMethodGraph implements ICallGraph {

    private final static Logger logger = LoggerFactory.getLogger(ClassMethodGraph.class);

    private GraphClassResolver graphClassResolver;

    public ClassMethodGraph(GraphClassResolver graphClassResolver) {
        this.graphClassResolver = graphClassResolver;
    }

    public static final ThreadLocal<List> stack = ThreadLocal.withInitial(ArrayList::new);

    @Override
    public void callGraph(String className, String method) {
        Map<String, ClassInfo> resolvedClassesMap = graphClassResolver.getResolvedTable().getResolvedClassesMap();
        ClassInfo classInfo = resolvedClassesMap.get(StringUtils.replace(className, ".", "/"));

        if (Objects.isNull(classInfo)) {
            //可能没有解析成功，再解析一遍
            if (!graphClassResolver.resolveClass(className)) {
                //仍然没有解析成功
                return;
            }
        }

        classInfo = resolvedClassesMap.get(StringUtils.replace(className, ".", "/"));

        //调用栈并且递归解析
        Optional<MethodInfo> methodInfoOptional = classInfo.getMethods()
                .stream()
                .filter(methodInfo -> methodInfo.getName().equals(method))
                .findFirst();
        List<MethodrefInfo> methodrefInfos = methodInfoOptional.get().getMethodrefInfos();
        for (int i = 0; i < methodrefInfos.size(); i++) {
            MethodrefInfo methodrefInfo = methodrefInfos.get(i);
            logger.info("called class:{},method:{}", methodrefInfo.getOwner(), methodrefInfo.getName());
            callGraph(methodrefInfo.getOwner(), methodrefInfo.getName());
        }
    }

    @Override
    public void search(String className, String method) {

    }
}
<file_sep>package org.opensource.analysis.algorithms;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.LongAdder;

/**
 * 原子命令性能评估
 * 1亿累加：
 * atom：620ms
 * 普通（带寄存器优化）：7ms，差距88倍
 */
public class CasPerformance {


    public static void main(String[] args) throws InterruptedException {
//        test();
//        long start = System.currentTimeMillis();
//        AtomicInteger atom = new AtomicInteger();
//        for (int i = 0; i < 10000 * 10000; i++) {
//            atom.incrementAndGet();
//        }
//        long end = System.currentTimeMillis();
//        System.out.println(end - start + "ms");
//        test();
        test2();
//        test3();
        test4();
    }

    public static void test() {
        long start = System.currentTimeMillis();
        long local = 0;
        for (int i = 0; i < 10000 * 10000; i++) {
            ++local;
        }
        long end = System.currentTimeMillis();
        System.out.println(local);
        System.out.println(end - start + "ms");
    }

    /**
     *
     */
    public static void test2() throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(64);
        LongAdder base = new LongAdder();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 2000 * 10000; i++) {
            executorService.submit(base::increment);
        }
        executorService.shutdown();
        executorService.awaitTermination(1, TimeUnit.HOURS);
        long end = System.currentTimeMillis();
        System.out.println("LongAdder ：" + (end - start));
    }

    public static void test3() throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(500);
        AtomicInteger base = new AtomicInteger();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 2000 * 10000; i++) {
            executorService.submit(base::incrementAndGet);
        }
        executorService.shutdown();
        executorService.awaitTermination(1, TimeUnit.HOURS);
        long end = System.currentTimeMillis();
        System.out.println("AtomicInteger ：" + (end - start));
    }

    public static void test4() throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(64);
        AtomicLong base = new AtomicLong();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 2000 * 10000; i++) {
            executorService.submit(base::incrementAndGet);
        }
        executorService.shutdown();
        executorService.awaitTermination(1, TimeUnit.HOURS);
        long end = System.currentTimeMillis();
        System.out.println("AtomicLong ：" + (end - start));
    }
}
<file_sep>```text
1.sp callgraph -cp [classpath] package.class.method
package.class.method
	->package.class.method
		->package.class.method
		->package.class.method
	->package.class.method
		->package.class.method
			package.class.method
	->package.class.method
		->package.class.method


2.sp search -cp [classpath] package.class.method
package.class.method
	<-package.class.method
		<-package.class.method
		<-package.class.method
	<-package.class.method
		<-package.class.method
			<-package.class.method
	<-package.class.method
		<-package.class.method

callgraph实现方法：
例如package.classA.methodB
1.find class:package.classA
2.find All methods of A
2-1.save all call instructions
3.find specified methodB from step2
4.for each insn in methodB
    repeat step-1
5.end until some call terminal methods

analysis:
ClassResolver.resolveClass(class)
    ClassVisitor
MethodResolver.resolveMethod(method) => ClassResolver.resolveClass(class) => MethodResolver.resolveMethod(method)
    MethodVisitor
ClassLoader
ResolvedClassTable
ResolvedMethodTable
CallGraph:method --ref--> method
怎样表达两个方法的引用关系，或者说用怎样的数据结构描绘这个graph？
methodA
    ref call-ref
            ref methodB

public <T,K> T void(K parameter);

```

```text
analyzer
    1.class-resolver:读取class文件,解析类和方法----创建MethodNode
    2.method-resolver:读取method code，解析被调用方法的类和方法----先解析类和方法，再根据语言特性继续解析可能的父类和接口类
        step-1和step-2把文件读取到内存中，把文件中的结构在内存中再组织一遍：
            文件中的结构：调用关系隐式存在；
            内存中的结构：调用关系，类和方法的组织关系，类的属性，方法的属性等等，在内存中显式存储，并可以对外暴露接口使用。
    3.graph:利用前面步骤的接口，建立graph接口，可供搜索遍历
实际的顺序可能会被调整，即可能graph3 -> class1 -> method2 -> class1 ->method2 这个互相插入的的顺序
说明：
这几个步骤的目的都是为了使结构structure使用起来更加方便，因为需要不同，组织结构的方式也不同，接口提供的功能也不相同。
基本元素是相同，客观存在的关系是相同的，但是对于不同的要求层次，组织和使用的方式却是不同的，为了让使用起来更加方便，抽象了以上概念。
即使元素只有0和1，但是也能组合成不同的形式，也就需要层次抽象来帮助管理。
```

```text
resolve ref伪代码：
function callgraph(ref)
	resolveMethod(ref)=>class+method+ref_list
	for each ref in ref_list
		callgraph(ref)

为了简单化，处理如下：
1.如果遇到接口interface，不再继续resolve，后续支持；
2.接口调用可能会形成死循环，这时要break死循环；

难点：
1.接口没有body，需要找到实现impl;  (findDirectImplClasses,findAllImplClasses)
2.类有子类，使用哪一个实现; (findDirectSubClasses,findAllSubClasses)
3.怎样避免cycle调用;
4.怎样清楚优雅地显示;
5.多态节点的展示方法和数据结构

interface:
findDirectSubInterfaces(parameter:interface)
findSubInterfaces(parameter:interface)
findDirectImplClasses(parameter:interface)
findAllImplClasses(parameter:interface)
impl class:
findDirectSubClasses(parameter:impl class)
findAllSubClasses(parameter:impl class)

invokeinterface:findDirectImplClasses,findAllImplClasses
invokevirtual:findDirectSubClasses,findAllSubClasses
invokestatic:
invokespecial:
invokedynamic:略


类的关系
resolve和classloader是一对一的关系
不同的classloader会单独加载class，但是resolve的逻辑是一样的

需要补充的算法知识：
1.环路检测：利用stack追踪调用链，检测环路
2.图的表达：数据结构
3.图的展示
4.图的遍历
```<file_sep>package org.opensource.analysis.parse.graph;

import java.util.List;

public interface MethodNode {

    /**
     * 根据method ref发现真实的方法节点，如果不能发现，那么就创造一个虚拟节点
     *
     * @return
     */
    List<MethodNode> findRefNodes();

    List<MethodNode> possibleMethodNodes();

    boolean existsMultiImpl();
}
<file_sep>package org.opensource.analysis.parse.structure;

import java.util.ArrayList;
import java.util.List;

public class MethodInfo {

    private ClassInfo ownerClassInfo;
    private int access;
    private String name;
    private String descriptor;
    private String signature;
    private String[] exceptions;

    public MethodInfo(int access, String name, String descriptor, String signature, String[] exceptions) {
        this.access = access;
        this.name = name;
        this.descriptor = descriptor;
        this.signature = signature;
        this.exceptions = exceptions;
    }

    private List<MethodrefInfo> methodrefInfos = new ArrayList<>();

    public void addMethodRef(MethodrefInfo methodref) {
        methodrefInfos.add(methodref);
    }

    public ClassInfo getOwnerClassInfo() {
        return ownerClassInfo;
    }

    public void setOwnerClassInfo(ClassInfo ownerClassInfo) {
        this.ownerClassInfo = ownerClassInfo;
    }

    public int getAccess() {
        return access;
    }

    public String getName() {
        return name;
    }

    public String getDescriptor() {
        return descriptor;
    }

    public String getSignature() {
        return signature;
    }

    public String[] getExceptions() {
        return exceptions;
    }

    public List<MethodrefInfo> getMethodrefInfos() {
        return methodrefInfos;
    }
}
<file_sep>package org.opensource.analysis.bysource;

import org.antlr4.java.JavaBaseVisitor;
import org.antlr4.java.JavaParser;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class MethodVisitor extends JavaBaseVisitor {

    private final static Logger logger = LoggerFactory.getLogger(MethodVisitor.class);

    @Override
    public Object visitMethodDeclaration(JavaParser.MethodDeclarationContext ctx) {
        logger.info("visitMethodDeclaration:{}", ctx.getText());
        return super.visitMethodDeclaration(ctx);
    }

    @Override
    public Object visitMethodModifier(JavaParser.MethodModifierContext ctx) {
        return super.visitMethodModifier(ctx);
    }

    @Override
    public Object visitMethodHeader(JavaParser.MethodHeaderContext ctx) {
        logger.info("visitMethodHeader:{}", ctx.getText());
        return super.visitMethodHeader(ctx);
    }

    @Override
    public Object visitMethodName(JavaParser.MethodNameContext ctx) {
        return super.visitMethodName(ctx);
    }

    @Override
    public Object visitMethodDeclarator(JavaParser.MethodDeclaratorContext ctx) {
        return super.visitMethodDeclarator(ctx);
    }

    @Override
    public Object visitMethodBody(JavaParser.MethodBodyContext ctx) {
        logger.info("visitMethodBody:{}", ctx.getText());
        return super.visitMethodBody(ctx);
    }

    @Override
    public Object visitMethodInvocation(JavaParser.MethodInvocationContext ctx) {
        logger.info("visitMethodInvocation:{}", ctx.getText());
        return super.visitMethodInvocation(ctx);
    }

    @Override
    public Object visitInterfaceMethodDeclaration(JavaParser.InterfaceMethodDeclarationContext ctx) {
        return super.visitInterfaceMethodDeclaration(ctx);
    }

    @Override
    public Object visitInterfaceMethodModifier(JavaParser.InterfaceMethodModifierContext ctx) {
        return super.visitInterfaceMethodModifier(ctx);
    }

    @Override
    public Object visitMethodReference(JavaParser.MethodReferenceContext ctx) {
        logger.info("visitMethodReference:{}", ctx.getText());
        return super.visitMethodReference(ctx);
    }

    @Override
    public Object visitMethodReference_lf_primary(JavaParser.MethodReference_lf_primaryContext ctx) {
        return super.visitMethodReference_lf_primary(ctx);
    }

    @Override
    public Object visitMethodReference_lfno_primary(JavaParser.MethodReference_lfno_primaryContext ctx) {
        return super.visitMethodReference_lfno_primary(ctx);
    }

    @Override
    public Object visitMethodInvocation_lf_primary(JavaParser.MethodInvocation_lf_primaryContext ctx) {
        return super.visitMethodInvocation_lf_primary(ctx);
    }

    @Override
    public Object visitMethodInvocation_lfno_primary(JavaParser.MethodInvocation_lfno_primaryContext ctx) {
        return super.visitMethodInvocation_lfno_primary(ctx);
    }


}
<file_sep>package org.opensource.analysis.parse;

import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import org.opensource.analysis.parse.structure.ClassInfo;
import org.opensource.analysis.parse.structure.MethodInfo;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class GraphClassVisitor extends org.objectweb.asm.ClassVisitor {

    private final static Logger logger = LoggerFactory.getLogger(GraphClassVisitor.class);

    private ClassInfo classInfo;

    private GraphClassResolver classResolver;

    public GraphClassVisitor(GraphClassResolver classResolver) {
        super(Opcodes.ASM7);
        this.classResolver = classResolver;
    }

    @Override
    public void visit(int version, int access, String name, String signature, String superName, String[] interfaces) {
        classInfo = new ClassInfo(access, name, signature, superName, interfaces);
        super.visit(version, access, name, signature, superName, interfaces);
    }

    @Override
    public MethodVisitor visitMethod(int access, String name, String descriptor, String signature, String[] exceptions) {
        MethodInfo methodInfo = new MethodInfo(access, name, descriptor, signature, exceptions);
        classInfo.addMethod(methodInfo);
        return new GraphMethodVisitor(methodInfo);
    }

    @Override
    public void visitEnd() {
        super.visitEnd();
        classResolver.getResolvedTable().addClass(classInfo);
    }
}
<file_sep>package org.opensource.analysis.parse.graph;

import java.util.List;

public abstract class AbstractMethodNode implements MethodNode{

    @Override
    public List<MethodNode> findRefNodes() {
        return null;
    }

    @Override
    public List<MethodNode> possibleMethodNodes() {
        return null;
    }

    @Override
    public boolean existsMultiImpl() {
        return false;
    }
}
<file_sep>package org.opensource.analysis.parse;

import org.opensource.analysis.parse.structure.MethodrefInfo;

public class GraphMethodResolver {

    private GraphClassResolver classResolver;

    public GraphMethodResolver(GraphClassResolver classResolver) {
        this.classResolver = classResolver;
    }

    public void resolveMethodref(MethodrefInfo methodrefInfo) {
        boolean resolvedResult = classResolver.resolveClass(methodrefInfo.getOwner());
        methodrefInfo.setResolvedResult(resolvedResult);
        if (methodrefInfo.isInvokeInterface()) {
            //寻找实现
        } else if (methodrefInfo.isInvokeSpecial()) {
            //寻找所有实现类及子类
        } else if (methodrefInfo.isInvokeVirtual()) {
            //寻找所有实现类及子类
        } else if (methodrefInfo.isInvokeStatic()) {
            //寻找所有实现类及子类
        } else if (methodrefInfo.isInvokeDynamic()) {

        }

    }


}
<file_sep>package org.opensource.analysis.parse.graph;

import java.util.List;

/**
 * 多态节点,因为面向对象：封装，继承，多态的特性，可以理解为所有的节点都是多态节点
 */
public class PolymorphismNode extends AbstractMethodNode {

    private List<MethodNode> possibleNodes;

    @Override
    public List<MethodNode> findRefNodes() {
        return super.findRefNodes();
    }

    @Override
    public List<MethodNode> possibleMethodNodes() {
        return possibleNodes;
    }

    @Override
    public boolean existsMultiImpl() {
        return true;
    }
}
<file_sep>package org.opensource.analysis.bysource;

import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr4.java.JavaLexer;
import org.antlr4.java.JavaParser;

import java.io.IOException;
import java.nio.charset.Charset;

public class SourceCallGraph {

    public static void main(String[] args) throws IOException {
        String sFile = "/Users/lvtu/workspace/java-callgraph/src/main/java/org/opensource/analysis/CallGraph.java";
        CharStream cs = CharStreams.fromFileName(sFile, Charset.forName("utf-8"));
        JavaLexer lexer = new JavaLexer(cs);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        JavaParser parser = new JavaParser(tokens);
        JavaParser.CompilationUnitContext tree = parser.compilationUnit(); // parse a compilationUnit
        int hashCode = cs.hashCode();
        System.out.println(hashCode);
        MethodVisitor methodVisitor = new MethodVisitor();
        tree.accept(methodVisitor);

        selfCall();
    }

    private static void selfCall() {
    }

}
