我是如何用java实现一个LeetCode的

前言

作为一个算法小垃圾，有一次我做完了一个LeetCode题目，我想的不是如何在提升一下自己的算法，而是想到了其他的一些东西。比如，我提交了一段Java代码到后台，后台是运行Java代码并且返回结果和这段代码执行的时间、占用内存等信息。我工作中接触的东西并不能考诉我这个过程中到底发生了什么，但是我还是抱着一探究竟的心，想去深入了解一个这个过程每一步的原理。

其实说来疑问就那么几点：

LeetCode提交的Java代码到底如何执行？
代码的运行时间和占用内存怎么得到？

对于这两个问题，我有初步的判断：

我们知道java不像Python可以直接执行，Java得编译之后在可以执行。我能想到的最简单的办法是把代码保存下载，然后开一个javac进程编译，执行并返回结果。这样可以实现，但是这样也太low了，毕竟io占用消耗就很大。解决方案肯定是动态的去编译Java代码。
获取代码运行时间非常容易，用切面就可以实现，但是获取这一段Java程序占用的内存还是有一定的困难。

当时想到这里我还是比较兴奋的，感觉这里还是有很多挑战，是我喜欢的类型。所以索性就自己实现了一下，当天晚上我就查找了一下相关的资料，发现Java的动态编译【】可以满足我的需求。并且实现了一个小demo完成了Java代码的编译执行。

后面我在这个小demo的基础上，继续的整合搭建，没想到最后也从一个小小的想法做成了一个完整的项目。最终我用到了SpringBoot Mybatis Redis Nacos Dubbo Gateway等等组件，也把这个项目做的有模有样。不过这个过程也是非常有趣的，一个是他完成了我的一个想法的落地，第二个是我又借这个机会重新复习了一下SpringCloud的一些知识。现在我把这个项目从头到尾用到的一些知识整理一下，分享出来。

【架构图占位】

动态编译-原理篇

1. 什么是动态编译？

动态编译，简单来说就是在Java程序运行时编译源代码。

从JDK1.6开始，引入了Java代码重写过的编译器接口，使得我们可以在运行时编译Java源代码，然后再通过类加载器将编译好的类加载进JVM,这种在运行时编译代码的操作就叫做动态编译。JDK提供了对应的JavaComplier接口来实现动态编译。

网上可以很轻松的就找到动态编译的例子，但是我在使用的过程中还是发现了很多的问题，后面我再展开介绍，最后我在arthas里找到了现成的内存编译，最终还是使用了arthas写好的库，比我自己写的优秀多了。

如果想要研究一下动态编译的原理的话，推荐几篇写的非常好的文章。前两篇文章都是从源代码讲起，看了很多篇文章，这几篇文章还是非常有深度的。

动态编译-实践篇

编译得到字节码

拿LeetCode第一题，两数之和来举例。试想一段这样的代码提交之后LeetCode是如何执行并且返回结果的呢？上面已经说过了，猜测使用的是动态编译。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numsHashmap = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (numsHashmap.containsKey(target - nums[i])) {
                return new int[]{i, numsHashmap.get(target - nums[i])};
            }
            numsHashmap.put(nums[i], i);
        }
        return new int[]{0, 0};
    }
}

动态编译的工具类写好之后，可以做到输入Java代码的字符串，输出Java class的字节码。然后就可以加载到虚拟机中来运行了。大致的逻辑如下：

public Map<String, Class<?>> build() {

    errors.clear();
    warnings.clear();

    JavaFileManager fileManager = new DynamicJavaFileManager(standardFileManager, dynamicClassLoader);

    DiagnosticCollector<JavaFileObject> collector = new DiagnosticCollector<JavaFileObject>();
    JavaCompiler.CompilationTask task = javaCompiler.getTask(null, fileManager, collector, options, null,
            compilationUnits);
    try {
        if (!compilationUnits.isEmpty()) {
            boolean result = task.call();
            // 异常判断
        }
        return dynamicClassLoader.getClasses();
    } catch (Throwable e) {
        throw new DynamicCompilerException(e, errors);
    } finally {
        compilationUnits.clear();
    }
}

但是首先一个问题就是，JVM里一个类加载器只能加载一个同名的类，而且，我们的系统肯定是多线程的，所以说a线程编译的类不能被b线程编译好的覆盖掉。所以说最好的方式还是每一个线程编译的类都新建一个类加载器来加载。

自定义类加载器

public class DynamicClassLoader extends ClassLoader {
    // 存储编译好的字节码，最终这些字节码在getClasses被加载
    private final Map<String, MemoryByteCode> byteCodes = new HashMap<String, MemoryByteCode>();
    public DynamicClassLoader(ClassLoader classLoader) {
        super(classLoader);
    }

    // getJavaFileForOutput，注册到类加载器中输出编译好的字节码
    public void registerCompiledSource(MemoryByteCode byteCode) {
        byteCodes.put(byteCode.getClassName(), byteCode);
    }

    @Override
    protected Class<?> findClass(String name) throws ClassNotFoundException {
        MemoryByteCode byteCode = byteCodes.get(name);
        if (byteCode == null) {
            return super.findClass(name);
        }
        // 使用asm来修改字节码
        byte[] modifyCodes = ByteCodeModifier.modify(name, byteCode.getByteCode(), byteCodes.keySet());
        return defineClass(name, modifyCodes, 0, modifyCodes.length);
    }

    public Map<String, Class<?>> getClasses() throws ClassNotFoundException {
        Map<String, Class<?>> classes = new HashMap<String, Class<?>>();
        for (MemoryByteCode byteCode : byteCodes.values()) {
            // 这里是真正加载字节码的地方
            classes.put(byteCode.getClassName(), findClass(byteCode.getClassName()));
        }
        return classes;
    }

    public Map<String, byte[]> getByteCodes() {
        Map<String, byte[]> result = new HashMap<>(byteCodes.size());
        for (Entry<String, MemoryByteCode> entry : byteCodes.entrySet()) {
            result.put(entry.getKey(), entry.getValue().getByteCode());
        }
        return result;
    }
}

最后多次调用的结果如下，可以发现有多个DynamicClassLoader，其父类加载器是AppClassLoader，GC之后就会被回收掉。

ASM

解决了编译和加载的问题之后，下面的问题就是如何正确运行并返回结果。这一步我也遇到了很多的麻烦，首先是我完全模仿LeetCode，类是没有加public的，但是不加public是不能运行的。同样的问题在import那里也是，LeetCode是不用用户区import包的，但是我在程序里没有想到解决的方案，手动拼上import java.util.*，是不行的，因为有的程序需要用的util包下的子包，这种编译也不通过，所以我这里其实是默认需要带上import语句的。如果谁知道怎么做的话欢迎告诉我。

说回public的问题，我们知道Java的类方法字段等都是需要修饰符的，可见性如下所示：

如下表所示,Y表示能访问(可见性），N表示不能访问，例如第一行的第3个Y，表示类的变量/方法如果是用public修饰，它的子类能访问这个变量/方法

修饰符类内部同个包（package）子类其他范围
public Y Y Y Y
protected Y Y Y N
无修饰符 Y Y Y或者N(见说明) N
private Y N N N

说明：

需要特别说明“无修饰符”这个情况，子类能否访问父类中无修饰符的变量/方法，取决于子类的位置。如果子类和父类在同一个包中，那么子类可以访问父类中的无修饰符的变量/方法，否则不行。

编译的类的包和调用的包不是一个包，那么就会抛异常。其实和import一样也可以手动去加上，但是一直这样干也太丑了，强迫症犯了的我确定使用另外的方法。那就是对字节码下手，修改类的修饰符。上文中我们提到了动态编译的返回结果是字节码，然后我们用自定义的类加载器去加载，这样我们在加载这个类之前就可以去修改这个类的修饰符，使他变为public的。用ASM就可以解决这个问题，

public class ByteCodeModifier {
    public static byte[] modify(String name, byte[] byteCode, Set<String> customClass) {

        // asm修改类的修饰符
        // 1. 创建 ClassReader 读入 .class 文件到内存中
        ClassReader reader = new ClassReader(byteCode);
        // 2. 创建 ClassWriter 对象，将操作之后的字节码的字节数组回写
        ClassWriter writer = new ClassWriter(reader, ClassWriter.COMPUTE_MAXS);
        if (name.equals("Solution")) {
            ClassVisitor change = new ChangeAccessVisitor(writer);
            reader.accept(change, ClassReader.EXPAND_FRAMES);
            return writer.toByteArray();
        } else if (customClass.contains(name)) {
            ClassVisitor change = new ChangePackageVisitor(writer);
            reader.accept(change, ClassReader.EXPAND_FRAMES);
            return writer.toByteArray();
        }
        return byteCode;
    }
}



public class ChangeAccessVisitor extends ClassVisitor {

    public ChangeAccessVisitor(ClassVisitor classVisitor) {
        super(Opcodes.ASM5, classVisitor);
    }

    @Override
    public void visit(int version, int access, String name, String signature, String superName,
            String[] interfaces) {
        super.visit(version, AccessFlag.setPublic(access), name, signature, superName, interfaces);
    }

    @Override
    public MethodVisitor visitMethod(int access, String name, String desc, String signature, String[] exceptions) {
        if (name.equals("<init>")) {
            access = AccessFlag.PUBLIC;
        }
        return super.visitMethod(access, name, desc, signature, exceptions);
    }
}

如何实现一个可拓展的应用？设计模式堆上去！

其实到这里最核心的部分已经完成了，后面就是如何吧整个的服务框架搭建起来，这一步也必须针对特定的业务场景来思考如何将程序写的更加优雅一些。

首先根据我们接收到代码的流程，我们可以分为几个步骤：首先是检查代码规范性，比如类是否完整等；第二步是编译；第三步是编译返回结果。这三步，每一步每一道题都有自己的实现，这种情况下我们使用模版方法比较适合。

模板方法

我们首先定义一个接口和抽象类，在抽象类中有几个方法，需要子类去实现，最终在compute方法中调用并返回结果。

public interface Compute {
    BaseResponse<?> compute(Code code);

    String getName();

}

public abstract class AbstractComputer implements Compute {
    protected abstract boolean verify();

    protected Class<?> compileCode(String sourceCode) throws Exception {
        try {
            DynamicCompiler dynamicCompiler = new DynamicCompiler(ClassLoader.getSystemClassLoader());
            dynamicCompiler.addSource("Solution", sourceCode);
            Map<String, Class<?>> build = dynamicCompiler.build();
            return build.get("Solution");
        } catch (Exception e) {
            e.printStackTrace();
            throw e;
        }
    }

    // 应该有一个run，运行单个，有一个submit，运行多个并提交
    protected abstract Object run(Class<?> clazz) throws Exception;

    @Override
    public BaseResponse<?> compute(Code code) {
        if (verify()) {
            try {
                Class<?> clazz = compileCode(code.getCodeStr());
                Object res = run(clazz);
                return BaseResponse.ok(res);
            } catch (Exception e) {
                e.printStackTrace();
                return BaseResponse.fail(ResponseEnum.INTERNAL_SERVER_ERROR);
            }
        }
        return BaseResponse.fail(ResponseEnum.INTERNAL_SERVER_ERROR);
    }
}

我们来随便看一个实现类，就拿LeetCode第一个题两数之和来举例子：

@Service
public class TwoSumComputer extends AbstractComputer {
    @Override
    public boolean verify() {
        return true; // 就随便这样写了
    }

    @Override
    public String getName() {
        return "1_twoSum"; // 这个方法后面再解释
    }

    @Override
    public Object run(Class<?> clazz) throws Exception {
        Object solution = clazz.newInstance();
        Method twoSum = clazz.getDeclaredMethod("twoSum", int[].class, int.class);
        int[] invoke = (int[]) twoSum.invoke(solution, new int[] {2, 7, 11, 15}, 9);
        return Arrays.stream(invoke).toArray();
    }
}

策略模式

每一道题都会有一个实现类，每一个请求都得分配一个类来去计算，这种情况下肯定不能用多个if来判断，使用策略模式会更好的解决这个问题。

利用Spring的构造器注入的方式，可以很好地吧Compute接口的实现类都注入到一个类里，然后保存起来，使用题目的名字来获取服务类。computeMap来保存所有Compute实现类的bean，key使用getName()方法来获得，每一个类都实现了这个方法，返回index_name，这样前端请求带上这两个参数，拼起来之后就能获得实现类了。

@Service
public class ComputerServiceDispatcher {
    private Map<String, Compute> computeMap = new HashMap<>();

    public ComputerServiceDispatcher(List<Compute> computes) {
        for (Compute compute : computes) {
            computeMap.put(compute.getName(), compute);
        }

    }

    public Compute getCompute(Code code) {
        return computeMap.get(code.getDescription());

    }
}

controller的实现：

@RestController
public class ComputeController {
    @Autowired
    private ComputerServiceDispatcher computerServiceDispatcher;

    @PostMapping("/test/compute")
    public BaseResponse<?> compute(@RequestBody Code code) {
        Compute compute = computerServiceDispatcher.getCompute(code);
        if (compute == null) {
            return BaseResponse.fail("没有该题目对应的computer");
        }
        return compute.compute(code);
    }

}

接口测试：

微服务-实践篇

后面，我又使用来springcloud和dubbo等工具搭建了一个简单的微服务框架，整体上这个项目就像点样子了。这部分大致上没什么特别的，都是那些组件最基本的用法，不过一个一个的组件搭起来，结合自己写的服务，看着一个个模块运行起来，还是挺有意思的。我个人也是喜欢这种创造的乐趣。至于前端，我做了一半又半途而废了，实在不想做前端，看看后续如果有人感兴趣的话，文档我再完善一下，再看看前端需不需要再做起来。