时间戳

首页 > 技术文章 > OO第三次博客作业

OO第三次博客作业

Potassium 2020-05-20 00:04 原文

一、JML 基础

梳理JML语言的理论基础、应用工具链情况。

语言介绍

JML (Java Modeling Language) 是用于对 Java 程序进行规格化设计的一种表示语言，是一种行为接口规格语言。

通过 JML 及其支持工具，不仅可以基于规格自动构造测试用例，并整合了 SMT Solver 等工具以静态方式来检查代码实现对规格的满足情况。

一般而言， JML 有两种主要的用法：

  • 开展规格化设计。这样交给代码实现人员的将不是可能带有内在模糊性的自然语言描述，而是逻辑严格的规格。
  • 针对已有的代码实现，书写其对应的规格，从而提高代码的可维护性。这在遗留代码的维护方面具有特别重要的意义。

语言用途

JML 是为契约性编程而生的，从它的原生语法来看，非常符合契约设计的理念：requires 描述先验条件，ensures 描述后验条件，old 描述副作用，exceptional_behavior 描述异常。

所以从理论上来说，通过 JML 这种语言，可以规范化编程，将编程变为一种可以形式化验证、消除歧义并进行自动的分析和推导的过程，让 bug 不复存在。

应用工具链

  • JML 工具链主要有 JMLUnit，JMLUnitNG，OpenJML 等，这些将在下文一一介绍。
  • 这些工具链大都非常陈旧，且无人维护，而且并没有形成一个真正的理论体系。

二、 SMT Solver 杀马特解决器

部署SMT Solver，至少选择3个主要方法来尝试进行验证，报告结果 有可能要补充JML规格

OpenJML

花了千辛万苦配好，打开使用之后发现，这个工具有好多地方没有 bug ，有很多支持的 JML 语法，有很多支持的 java 版本，这么好用的工具我不配使用，告辞。

我使用以下代码进行测试：

public class Main {
    
    /* @ public normal_behavior
     * @ ensures \result == (l != r);
     */
    public static boolean neq(int l, int r) {
        return l!=r;
    }
    
    public static void main(String[] args) {
        neq(0, 1);
    }
}

报错信息如下：

warning: An internal JML error occurred, possibly recoverable.  Please report the bug with as much information as you can.
  Reason: Last resort loading of extensions
warning: An internal JML error occurred, possibly recoverable.  Please report the bug with as much information as you can.
  Reason: Last resort loading of extensions
Internal JML bug - please report.  BuildOpenJML-0.8.44-20200413
java.lang.NullPointerException
	at com.sun.tools.javac.parser.JmlParser.parseTypeSpecs(JmlParser.java:2082)
	at com.sun.tools.javac.parser.JmlParser.classOrInterfaceBodyDeclaration(JmlParser.java:1216)
	at com.sun.tools.javac.parser.JavacParser.classOrInterfaceBody(JavacParser.java:3563)
	at com.sun.tools.javac.parser.JmlParser.classOrInterfaceBody(JmlParser.java:420)
	at com.sun.tools.javac.parser.JavacParser.classDeclaration(JavacParser.java:3412)
	at com.sun.tools.javac.parser.JmlParser.classDeclaration(JmlParser.java:431)
	at com.sun.tools.javac.parser.JavacParser.classOrInterfaceOrEnumDeclaration(JavacParser.java:3353)
	at com.sun.tools.javac.parser.JmlParser.classOrInterfaceOrEnumDeclaration(JmlParser.java:285)
	at com.sun.tools.javac.parser.JavacParser.typeDeclaration(JavacParser.java:3342)
	at com.sun.tools.javac.parser.JavacParser.parseCompilationUnit(JavacParser.java:3282)
	at com.sun.tools.javac.parser.JmlParser.parseCompilationUnit(JmlParser.java:170)
	at com.sun.tools.javac.main.JavaCompiler.parse(JavaCompiler.java:633)
	at com.sun.tools.javac.main.JmlCompiler.parse(JmlCompiler.java:143)
	at com.sun.tools.javac.main.JavaCompiler.parse(JavaCompiler.java:670)
	at com.sun.tools.javac.main.JmlCompiler.parseSingleFile(JmlCompiler.java:251)
	at com.sun.tools.javac.main.JmlCompiler.parseSpecs(JmlCompiler.java:223)
	at com.sun.tools.javac.main.JmlCompiler.completeBinaryEnterTodo(JmlCompiler.java:359)
	at com.sun.tools.javac.main.JmlCompiler.loadSpecsForBinary(JmlCompiler.java:337)
	at com.sun.tools.javac.comp.JmlResolve.loadClass(JmlResolve.java:172)
	at com.sun.tools.javac.comp.Resolve.findGlobalType(Resolve.java:2015)
	at com.sun.tools.javac.comp.Resolve.findType(Resolve.java:2101)
	at com.sun.tools.javac.comp.Resolve.findIdent(Resolve.java:2126)
	at com.sun.tools.javac.comp.Resolve.resolveIdent(Resolve.java:2400)
	at com.sun.tools.javac.comp.Attr.visitIdent(Attr.java:3182)
	at com.sun.tools.javac.comp.JmlAttr.visitIdent(JmlAttr.java:4631)
	at com.sun.tools.javac.tree.JCTree$JCIdent.accept(JCTree.java:2011)
	at com.sun.tools.javac.comp.Attr.attribTree(Attr.java:577)
	at com.sun.tools.javac.comp.Attr.attribType(Attr.java:639)
	at com.sun.tools.javac.comp.Attr.attribType(Attr.java:632)
	at com.sun.tools.javac.comp.JmlAttr.attribType(JmlAttr.java:2514)
	at com.sun.tools.javac.comp.Attr.visitTypeArray(Attr.java:3912)
	at com.sun.tools.javac.tree.JCTree$JCArrayTypeTree.accept(JCTree.java:2111)
	at com.sun.tools.javac.comp.Attr.attribTree(Attr.java:577)
	at com.sun.tools.javac.comp.Attr.attribType(Attr.java:639)
	at com.sun.tools.javac.comp.Attr.attribType(Attr.java:632)
	at com.sun.tools.javac.comp.JmlAttr.attribType(JmlAttr.java:2514)
	at com.sun.tools.javac.comp.MemberEnter.visitVarDef(MemberEnter.java:686)
	at com.sun.tools.javac.comp.JmlMemberEnter.visitVarDef(JmlMemberEnter.java:1953)
	at com.sun.tools.javac.tree.JCTree$JCVariableDecl.accept(JCTree.java:852)
	at org.jmlspecs.openjml.JmlTree$JmlVariableDecl.accept(JmlTree.java:1396)
	at com.sun.tools.javac.comp.MemberEnter.memberEnter(MemberEnter.java:438)
	at com.sun.tools.javac.comp.JmlMemberEnter.memberEnter(JmlMemberEnter.java:175)
	at com.sun.tools.javac.comp.MemberEnter.signature(MemberEnter.java:386)
	at com.sun.tools.javac.comp.MemberEnter.visitMethodDef(MemberEnter.java:592)
	at com.sun.tools.javac.comp.JmlMemberEnter.visitMethodDef(JmlMemberEnter.java:1717)
	at com.sun.tools.javac.tree.JCTree$JCMethodDecl.accept(JCTree.java:778)
	at org.jmlspecs.openjml.JmlTree$JmlMethodDecl.accept(JmlTree.java:1264)
	at com.sun.tools.javac.comp.MemberEnter.memberEnter(MemberEnter.java:438)
	at com.sun.tools.javac.comp.JmlMemberEnter.memberEnter(JmlMemberEnter.java:175)
	at com.sun.tools.javac.comp.MemberEnter.memberEnter(MemberEnter.java:450)
	at com.sun.tools.javac.comp.JmlMemberEnter.memberEnter(JmlMemberEnter.java:167)
	at com.sun.tools.javac.comp.MemberEnter.finishClass(MemberEnter.java:460)
	at com.sun.tools.javac.comp.JmlMemberEnter.finishClass(JmlMemberEnter.java:276)
	at com.sun.tools.javac.comp.MemberEnter.finish(MemberEnter.java:1446)
	at com.sun.tools.javac.comp.MemberEnter.complete(MemberEnter.java:1241)
	at com.sun.tools.javac.comp.JmlMemberEnter.complete(JmlMemberEnter.java:1865)
	at com.sun.tools.javac.code.Symbol.complete(Symbol.java:574)
	at com.sun.tools.javac.code.Symbol$ClassSymbol.complete(Symbol.java:1037)
	at com.sun.tools.javac.comp.Enter.complete(Enter.java:493)
	at com.sun.tools.javac.comp.Enter.main(Enter.java:471)
	at com.sun.tools.javac.comp.JmlEnter.main(JmlEnter.java:824)
	at com.sun.tools.javac.main.JavaCompiler.enterTrees(JavaCompiler.java:992)
	at com.sun.tools.javac.main.JavaCompiler.compile(JavaCompiler.java:864)
	at com.sun.tools.javac.main.Main.compile(Main.java:553)
	at com.sun.tools.javac.main.Main.compile(Main.java:410)
	at org.jmlspecs.openjml.Main.compile(Main.java:581)
	at com.sun.tools.javac.main.Main.compile(Main.java:399)
	at com.sun.tools.javac.main.Main.compile(Main.java:390)
	at org.jmlspecs.openjml.Main.execute(Main.java:417)
	at org.jmlspecs.openjml.Main.execute(Main.java:375)
	at org.jmlspecs.openjml.Main.execute(Main.java:362)
	at org.jmlspecs.openjml.Main.main(Main.java:334)
Press any key to continue . . .

可以看到，这一款工具的 bug 反馈机制做的相当不错。

三、JMLUnit

部署JMLUnitNG/JMLUnit，针对Group接口的实现自动生成测试用例，并结合规格对生成的测试用例和数据进行简要分析

JMLUnitNG

很强的一个测试工具。只要没有同名变量，没有不支持的语法结构，就可以进行测试了！那么他测试的是什么呢？！以这段代码为例跑一下试试：

public class Main {
    
    /* @ public normal_behavior
     * @ ensures \result == (l != r);
     */
    public static boolean neq(int l, int r) {
        return l!=r;
    }
    
    public static void main(String[] args) {
        neq(0, 1);
    }
}

输出结果：

[TestNG] Running:
  Command line suite

Failed: racEnabled()
Passed: constructor Main()
Passed: static main(null)
Passed: static main({})
Passed: static neq(-2147483648, -2147483648)
Passed: static neq(0, -2147483648)
Passed: static neq(2147483647, -2147483648)
Passed: static neq(-2147483648, 0)
Passed: static neq(0, 0)
Passed: static neq(2147483647, 0)
Passed: static neq(-2147483648, 2147483647)
Passed: static neq(0, 2147483647)
Passed: static neq(2147483647, 2147483647)

===============================================
Command line suite
Total tests run: 13, Failures: 1, Skips: 0
===============================================

===============================================

看！虽然不能帮你验证结果的正确性，但能帮你看出来极端数据下你的程序会不会抛异常呀！哦，我的老天爷！您一定得瞧瞧这一个工具，我的老伙计。这简直是太方便了，就像去吃隔壁玛丽婶婶做的馅饼一样！

在传入数据类型为 int 的情况下，会自动生成 INT_MAX ，0 ， INT_MIN 分别进行输入；而在传入为一个对象的时候，会直接传入 null 。通过这个思想进行组合输入，能够很方便的帮我们找出在极端数据下各个方法是否会抛出异常。是真没什么作用

所以要求中的对 Group 进行测试，完全没有意义，通过上述 demo 已经证明了这一点，而且他支持的版本和写法太狭窄，故略去。

四、架构设计

按照作业梳理自己的架构设计，特别分析自己的模型构建策略

第九次作业

绝大多数的内容直接照搬规格即可。

需要讨论的有几个点：

  1. MyPerson 中，acquaintance value 两个数组分别使用什么容器
  2. MyNetwork 中，使用什么容器存储 people
  3. 如何快速实现 MyNetwork 中的 isCircle 方法

第一个问题，由于每一个 person 对应一个 value，且没有重复 Person ，故可以合并成使用 HashMap<Person, Integer> 一个容器进行储存。

第二个问题，由于需要根据唯一确定的 id 找人，故使用 HashMap<Integer, Person> 存储 people。

第三个问题，很明显因为只有 addRelation 没有 delRelation，故可以使用路径压缩的并查集（均摊 \(\mathcal{O}(1)\)）。当然如果有 delRelation 的话，需要改成搜索 \(\mathcal{O}(n)\)，或者要保证性能较高的话，使用 ETT 维护一个分层图，复杂度可以保证在 \(\mathcal{O}(\log^2n)\)。好在接下来的几次作业中助教并没有这么魔鬼，于是使用路径压缩并查集。

第十次作业

添加了 Group 接口，实现一些关于查询组内信息的方法。

对于 conflictSum 、 ageMean 和 ageVar ，直接在加入人的时候更新即可；对于 relationSum 和 valueSum ，还需要在改变 network 中人之间关系的同时进行修改。这些方法都是 \(\mathcal{O}(n)\) 维护， \(\mathcal{O}(1)\) 回答询问。

其中，要求 ageMean 和 ageVar 计算都是整数除法，故需要维护一个年龄总和以及其平方，推一下式子即可 \(\mathcal{O}(n)\) 维护， \(\mathcal{O}(1)\) 回答询问。

一些 corner case ：首先 ageVar 计算结果不会爆 int ，故不会出现问题（下文中做分析）；计算 ageMean 和 ageVar 的时候，需要特判除零的情况。

第十一次作业

添加了“从 Group 里删除”的操作，这个只需要和加入人一样反向更新一下几个和值即可。

添加了借钱操作，这个只要加一个人 id 对应钱数的 HashMap 查询、更新一下即可。

添加了查询连通块个数操作，这个只需要 addPerson 的时候增加，addRelation 且不同集合的时候减少即可，并查集维护， \(\mathcal{O}(1)\) 回答询问。

添加了询问一个区间年龄中人数的操作，这个我选择了 \(\mathcal{O}(n)\) 遍历，因为数据范围太小。当数据范围加大时，可以使用树状数组维护某年龄人个数的前缀和进行 \(\mathcal{O}(\log n)\) 维护， \(\mathcal{O}(\log n)\) 查询。

添加了“查询两点间最短路”的操作，于是新建了 Graph 类，在 addPerson 和 addRelation 的时候对图进行更新，在每次询问的时候跑一遍堆优化 dijkstra 即可， \(\mathcal{O}(1)\) 维护， \(\mathcal{O}(n\log n)\) 回答询问。

添加了“查询两点是否在同一点双”操作，同样在 Graph 类里进行操作。由于 JML 里的要求其实并不是严格的点双，它认为 K2 并不是一个点双，因此需要特判。这里有两种实现方式：

  1. Tarjan 算法。直接预处理出所有 v-DCC ，枚举进行判断即可。关于 Tarjan 算法对于三种图论中的连通分量的不同实现和分析，在此不多赘述，提供参考链接。
  2. 暴力做法。枚举每一点，判断不经过这一点的情况下是否能够联通。

两种做法都写了，但由于暴力复杂度不会超时，为了保险提交了第二种做法。

第二种做法中，特判的情况需要判断两点联通时删掉该边后能否连通，这里并没有使用删掉边的简单 dfs 思路，而是想了一种神秘的做法，参考如下：

  • 对点 \(id_1\) 的连出边进行标号（\(0,1..deg[id_1]-1\)）；

  • 从 \(id_1\) 出发，按照升序枚举初次走的边，进行 dfs 染色，将所有起始边为 \(i\) 能达到的、没有被 \(0..i-1\) 条边遍历到的点 \(p\) 全部染成 \(i\) 色（\(col[p][0]=i\)）；

  • 再按照降序染色（\(col[p][1]=i\)）。

  • 结束两轮染色后，比较 \(col[id_2][0]\) 和 \(col[id_2][1]\) 是否相等。如果相等，那么 false ；否则 true 。

这种做法的思路题目来源，只供一哂。

关于为什么不会爆 int

众所周知，\(2000\cdot 2000\cdot 800 > 2147483647\) ，那么为什么用公式法求解的时候不会爆 int 呢？

实际上，加减乘运算均是通过二进制加法运算得到的。也就是说，计算中，只要结果不爆 int ，那么中间可以任意爆 int 而不会出错（本质都是 &0xffffffff ）。（如果有错欢迎指正）

五、bug 情况

按照作业分析代码实现的bug和修复情况

仔细阅读 JML ，将其中所有的约束条件通过 JUnit 进行单元测试，使用测试驱动开发的思想，先构造数据集进行测试（变红），再分析如何实现，编写代码使得测试变绿；同时保证在迭代开发的过程中不会出现新的 bug。

通过随机生成合法数据进行多人对拍运动，进一步保证了随机数据和带有一定特征（只测某几个有关联指令）的数据下，自己不存在问题。

自己的bug

三次作业的弱中强测、互测没有被测出 bug 。

他人的bug

第十次作业互测中，发现了一个同学的 qgvs 使用暴力做法，故构造数据卡掉；发现另一个同学 qci 的做法过于暴力，亦构造长链数据卡掉。同屋还有一个同学的 bug 没被我发现，是因为没有研读代码，直接采用对拍，忽略掉了一些较为基础的错误点。

吸取了上次的教训，第十一次作业的互测中，采用对拍+阅读代码构造数据的方式进行测试，成功发现屋中所有 3 个 bug 。它们分别是对于 ageMean 的边界条件判断问题，对于 qsl 的中间判断问题，以及 qsl 在边界条件情况下的 TLE 问题。

六、心得体会

阐述对规格撰写和理解上的心得体会

JML 是为契约性编程而生的，从它的原生语法来看，非常符合契约设计的理念：requires 描述先验条件，ensures 描述后验条件，old 描述副作用，exceptional_behavior 描述异常。

所以从理论上来说，通过 JML 这种语言，可以规范化编程，将编程变为一种可以形式化验证、消除歧义并进行自动的分析和推导的过程，让 bug 不复存在。

在规格撰写的过程中，我们需要注意所有的可变、不变类型，并进行对应处理。在规格的理解中，切不可偏解，要完整、正确地理解规格，否则就会产生一些边角数据（ corner case ）下的问题。

在这一章中，通过对 JML 这门崭新的语言的学习，我对于契约式编程的理解更加深刻了，对于规格和代码之间的转化和对应关系也有了新的认识。感谢各位助教的辛勤付出，感谢和我一同讨论问题、进行对拍、分析的同学们，希望能在下一个单元重新遇见更好的 OO 。

七、杂念

这篇博客作业到此为止写完了，下面的部分不属于作业。还恳请辛苦批阅的助教 / 老师跳过。

说实话，这单元的内容没什么意思，也没有学到什么有价值的东西，比前两个单元差远了，很失望，如果明年 cut 掉也没有什么，并且希望如此。

据说本单元的本意在考查对规格的理解和实现，但其实做出来最后考的是算法的实现。一个 OO ，考什么算法呢？算法不应该是 ds 就打下的良好基础吗？但实际上，ds 就没学什么东西，至少我们在大二下了，还有无数的同学不会堆优化 dij ，不会并查集，而这些东西本身就是数据结构要学的内容。这样看来，六系的这一套体系似乎有一些瑕疵，现下的 OO 通过第三单元的三次算法小练习似乎在拆东补西，尝试弥补这一个缺陷。

代码规格不能说没用，他很有用，如果一个项目分配给很多人写每个部分，当然如果有一个规格去统一是非常方便、且能高效率、低出错率地完成的。但如果以为用 JML 就很方便，无论是从对于 JML 的书写还是对于它的阅读，哪一个方面都不容易。 JML 可以把一个很简单的方法说的极其复杂，导致阅读效率大幅降低；而且通过这三次作业助教修 JML 锅的次数来看，这个东西也很难保证写的正确。实际上，如果遇到更加复杂的问题，如果有更多的元素、更多的方法参与其中，那么 JML 的内容会更加复杂，无论是编写者还是阅读者都极难保证自己的理解不出问题，分支、边界条件不遗漏。另外，目前对于 JML 的正确性验证、对于基于 JML 实现的验证都极其不完备，我认为这个比较适合作为研究生项目等进行研究，而不是把这一个很不完备的体系拿过来用在来我们的 OO 课程。

第一单元帮我们构建了整一个 OO 体系的思想，让我们深刻地理解到将一个大任务分割成一些对象，并通过继承、接口等方式构建共同点、分而治之的巧妙思想；第二单元搭建起了整一个多线程程序的框架，让我们理解并发执行多个线程的思想和实现过程，并让我们切身实际体验多线程中锁的重要性以及死锁的预防方式。可是本单元呢？如果说本单元的目的在于让我们拥有一个规格的思想，那其实一次实验足矣；如果说这是对于去年 ds 的亡羊补牢练习，这最多练习了一下 dijkstra ，并查集，有兴趣的同学学习了一下 tarjan 算法，似乎也并没有涉及很多东西。

本单元体验无论是从作业内容，还是实验内容来看，都不太行。不太行并不是说老师助教们做的不好，老师助教们的辛勤付出我们都看在眼里，而是整个体系出现的问题，没有回答好一个“本单元究竟是什么目的”的问题。这一切都是笔者当下的看法，也可能是由于我目光短浅造成的。希望下一单元能够带来更加有趣、实用的东西。

推荐阅读