DOTParsers.mealy() not parsing all transitions

[tiferrei]

DOTParsers.mealy() not parsing all transitions

[mtf90]

Dear Thiago,

unfortunately, I cannot reproduce this issue. When I output the .dot code, I receive a graph description similar to the input code (7 states, for each state there are 4 transitions defined, the succesor states match, etc.).

However, I did do things differently compared to your approach. I read the input data via Test.class.getResourceAsStream and output(ted?) it to System.out. This makes me think, there could have gone two different things wrong in your scenario.

• getResourceAsStream always reads the ressource from the JAR/maven module where the class is located. If you simply create a new (input) file with a name "input.dot" (so without absolute path qualifiers) the path is always interpreted relatively to where you start your JVM process. So if you run your JAR (java -jar ...) from different folders it could potentially read a different input file each time. Maybe you have experimented with the serialization before and there were some left-over files laying around?
• The same can happen with your output file. It is just written to the directory, where your JVM process was launched from. So maybe you have checked an outdated output file?

[tiferrei]

Thank you for the fast reply!

That is a good point, just to be sure I modified the code to show us the file contents in the console instead:

package util.learnlib;

import net.automatalib.automata.transducers.impl.compact.CompactMealy;
import net.automatalib.serialization.InputModelData;
import net.automatalib.serialization.InputModelDeserializer;
import net.automatalib.serialization.dot.DOTParsers;
import net.automatalib.serialization.dot.GraphDOT;

import java.io.*;

public class Test {
	private static String DOT_IN = "input.dot";
	private static String DOT_OUT = "output.dot";

	public static CompactMealy<String, String> readFile(String filename) throws IOException {
		File file = new File(filename);

		// Let's print the content just to be sure.
		FileInputStream fis = new FileInputStream(file);
		int oneByte;
		while ((oneByte = fis.read()) != -1) {
			System.out.write(oneByte);
		}
		System.out.flush();

		InputModelDeserializer<String, CompactMealy<String,String>> parser = DOTParsers.mealy();
		InputModelData<String, CompactMealy<String, String>> machine = parser.readModel(file);
		return machine.model;
	}

	private static <I> void saveToFile(String filename, CompactMealy<String, String> model) {
		try (BufferedWriter out = new BufferedWriter(new FileWriter(filename))) {
			GraphDOT.write(model, model.getInputAlphabet(), System.out);
			System.out.flush();
		} catch (IOException exception) {
			exception.printStackTrace();
		}
	}

	public static void main(String[] args) throws IOException {
		CompactMealy<String, String> mealyMachine = readFile(DOT_IN);
		saveToFile(DOT_OUT, mealyMachine);
	}
}

I got the following output:

digraph g {

	s0 [shape="circle" label="0"];
	s1 [shape="circle" label="1"];
	s2 [shape="circle" label="2"];
	s3 [shape="circle" label="3"];
	s4 [shape="circle" label="4"];
	s5 [shape="circle" label="5"];
	s6 [shape="circle" label="6"];
	s0 -> s0 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / EMPTY"];
	s0 -> s0 [label="INITIAL(0xff00001d)[ACK,PING] / INITIAL(0xff00001d)[ACK]"];
	s0 -> s1 [label="INITIAL(0xff00001d)[CRYPTO] / INITIAL(0xff00001d)[ACK,CRYPTO]+HANDSHAKE(0xff00001d)[CRYPTO]+HANDSHAKE(0xff00001d)[CRYPTO]"];
	s0 -> s0 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s1 -> s2 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[HANDSHAKE_DONE,CRYPTO,STREAM]+HANDSHAKE(0xff00001d)[ACK]"];
	s1 -> s1 [label="INITIAL(0xff00001d)[ACK,PING] / INITIAL(0xff00001d)[ACK]"];
	s1 -> s3 [label="INITIAL(0xff00001d)[CRYPTO] / HANDSHAKE(0xff00001d)[CONNECTION_CLOSE]"];
	s1 -> s6 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s2 -> s3 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[CONNECTION_CLOSE]"];
	s2 -> s2 [label="INITIAL(0xff00001d)[ACK,PING] / EMPTY"];
	s2 -> s2 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s2 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK]"];
	s3 -> s3 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / EMPTY"];
	s3 -> s3 [label="INITIAL(0xff00001d)[ACK,PING] / EMPTY"];
	s3 -> s3 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s3 -> s3 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s4 -> s4 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / EMPTY"];
	s4 -> s4 [label="INITIAL(0xff00001d)[ACK,PING] / EMPTY"];
	s4 -> s4 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s4 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK,STREAM]"];
	s5 -> s3 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[CONNECTION_CLOSE]"];
	s5 -> s5 [label="INITIAL(0xff00001d)[ACK,PING] / EMPTY"];
	s5 -> s5 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s5 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK,STREAM]"];
	s6 -> s5 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[HANDSHAKE_DONE,CRYPTO,STREAM]+HANDSHAKE(0xff00001d)[ACK]"];
	s6 -> s6 [label="INITIAL(0xff00001d)[ACK,PING] / INITIAL(0xff00001d)[ACK]"];
	s6 -> s3 [label="INITIAL(0xff00001d)[CRYPTO] / HANDSHAKE(0xff00001d)[CONNECTION_CLOSE]"];
	s6 -> s6 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];

__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;

}
digraph g {

	s0 [shape="circle" label="0"];
	s1 [shape="circle" label="1"];
	s2 [shape="circle" label="2"];
	s3 [shape="circle" label="3"];
	s4 [shape="circle" label="4"];
	s5 [shape="circle" label="5"];
	s6 [shape="circle" label="6"];
	s0 -> s0 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s0 -> s1 [label="INITIAL(0xff00001d)[CRYPTO] / INITIAL(0xff00001d)[ACK,CRYPTO]+HANDSHAKE(0xff00001d)[CRYPTO]+HANDSHAKE(0xff00001d)[CRYPTO]"];
	s1 -> s6 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s1 -> s2 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[HANDSHAKE_DONE,CRYPTO,STREAM]+HANDSHAKE(0xff00001d)[ACK]"];
	s1 -> s1 [label="INITIAL(0xff00001d)[ACK,PING] / INITIAL(0xff00001d)[ACK]"];
	s1 -> s3 [label="INITIAL(0xff00001d)[CRYPTO] / HANDSHAKE(0xff00001d)[CONNECTION_CLOSE]"];
	s2 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK]"];
	s2 -> s3 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[CONNECTION_CLOSE]"];
	s2 -> s2 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s3 -> s3 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s4 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK,STREAM]"];
	s5 -> s4 [label="SHORT(0xff00001d)[ACK,STREAM] / SHORT(0xff00001d)[ACK,STREAM]"];
	s5 -> s3 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[CONNECTION_CLOSE]"];
	s5 -> s5 [label="INITIAL(0xff00001d)[CRYPTO] / EMPTY"];
	s6 -> s6 [label="SHORT(0xff00001d)[ACK,STREAM] / EMPTY"];
	s6 -> s5 [label="HANDSHAKE(0xff00001d)[ACK,CRYPTO] / SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[STREAM]+SHORT(0xff00001d)[HANDSHAKE_DONE,CRYPTO,STREAM]+HANDSHAKE(0xff00001d)[ACK]"];
	s6 -> s3 [label="INITIAL(0xff00001d)[CRYPTO] / HANDSHAKE(0xff00001d)[CONNECTION_CLOSE]"];

__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;

}

I think this tells us that something else is going on. Right now I have 3 potential hypothesis, all to do with the environment. This could be: the Java version, the Library (version or the package itself), the OS (I'm running macOS)

I will try to build this in a Docker container to eliminate the last one. As far as the others go, I'm running OpenJDK-13 and the Library package is learnlib-distribution-0.15.0-dependencies-bundle.jar.

[mtf90]

While environmental differences could always play a role, we try to minimize most of them with our CI pipeline. In fact, we even have a configuration that runs Java 13 on a macOS system and it passes without problems (and yes, we also test that a serialized and then de-serialized model is equivalent to its source 😁). If you'd like, you could try to run a mvn test on the automatalib-0.9.0 tag (which is the version used by LearnLib 0.15.0).

One thing that sticks out to me is the pattern in which transitions go missing. It seems transitions to the same successor state get merged together. You have 3 s0 -> s0 transitions in the input, but only one s0 -> s0 transition in the output. The single s0 -> s1 transition survives. Similarily the two s6 -> s6 transitions get merged as well in the output. It seems some mapping code cannot properly distinguish the state entries. If you're into debugging you could try to find out if this happens during serialization or de-serialization (I'd assume the latter).

I tried to reproduce the error with JDK14 (previously I tried JDK8) but still couldn't replicate the issue. It may after all really be a configuration issue on your end (I believe JDK8/11 are LTS versions and 14 is the latest development release).

[tiferrei]

An update on the environments, as you rightly said the chance of it being env was really low, and running it on a docker container confirmed the same behaviour. I also checked (just to be sure) and my JAR is identical to the one in the distro. I haven't tried out changing the version, but thought I'd run the tests on Java 13 too. It's green lights all the way down, no failures.

I was going to hypothesise that maybe this could be something that didn't trigger in the unit test examples, and only in a more complex example like the one we're dealing with, but you can't reproduce this issue so I find that unlikely.

Regarding the bug, I did isolate it to de-serialisation (I think, it happens on reading and parsing the file into Java memory – I always get the terms confused) upon reading the model from the file the model is already missing the transitions.

EDIT: I seem to get the same issue, as well as test results with 1.8

[mtf90]

What OS/JDK were you using in the docker container? My local tests were on (Arch) Linux with JDK8/11.

Are you using LearnLib as a standalone JAR (i.e. something you invoke with java -cp learnlib-bundled.jar -jar ...) or within a Maven Project? With Maven Project most IDEs supprt a "Download Sources" feature which makes debugging a lot easier. You already pin-pointed out that the issue lies within the de-serialization code (in my case for example the parsed automaton contained no undefined transitions). I suspect it is somewhere buried in the DOTMutableAutomatonParser class. I hope that it is not related to the (auto-generated) parser from JavaCC...

[tiferrei]

I'm using it as a standalone JAR I believe, with an ant build file (old fashioned I know, will update it at some point), and then I'd call the program with java -cp "Learner/dist/MYDIST.jar:Learner/lib/*" util.Test

Regarding the Docker container, it's using openjdk:13-alpine as base although openjdk:8-alpine seems to behave in the same way.

I'll try it out with an Arch Linux JDK8 image just in case. Any particular one I should use?

[mtf90]

I used the JDKs that are available in the default Arch repositories. Judging by their PKGBUILDs they simply cloned the official source repository and built the JDKs themselves. So no middle-man distributor such as AdoptJDK, etc is involved.

Since your setup mostly involves just LearnLib and your Test class, I think the easiest way to debug this issue would be to import the AutomataLib code into a Java IDE (IntelliJ/Eclipse/Netbeans/etc, most of them support Maven projects out-of-the-box), add your test class and step through the crucial steps of the deserialization code to detect where things go missing.

[tiferrei]

I believe I have found the issue. I was doing all this with the latest release, AutomataLib 0.9.0, more precisely commit f74714d. This commit is from 5 February 2020, where AutomataLib is still using the PayPal digraph parser, which merges the edges as you rightly pointed out in issue paypal/digraph-parser#3, and was fixed in commit 230a58f on the 4th of April 2020.

Running the code on develop means that the dot parser uses the automata lib parser instead of PayPal's, and as such resolves the issue.

Do you have an approximate date for the next AutomataLib release to include this fix?

[mtf90]

Oh shoot! I should have noticed this, my bad. I even skimmed over the release notes of version 0.9.0, read something about DOT parsers and assumed it was already the "latest" version.

You are right, the latest release ships with the "broken" PayPal parser. I have re-written the parser because we have some upcoming features in development which ran into the exact same issue that you had.

Usually, we try to stick to yearly releases in which we can break things (i.e. version 0.10.0 is scheduled for some time around Jan/Feb 2021). If you need a quick solution for now, I can refer you to our continuous deployments which are directly uploaded from our CI pipeline. These are used best with some dependency management tools. I think for Ant there is Ivy that allows you to automatically download artifacts or you switch to a tool that combines both techniques such as Maven or Gradle.

If this is a pressing issue for you and you need a stable version (totally understandable), we can also think about chipping in a bugfix release in a week or two. We have already accumulated quite a few fixes for the upcoming release that we hopefully should be able to cherry-pick. By any chance, we can then also include fixes for our latest issues (#41).

[tiferrei]

I think the yearly release cycle makes perfect sense, and I would use a development build, but unfortunately I'm still very much an AutomataLib and LearnLib newbie and rely a lot on the documentation and examples, so I'd prefer to stick with the latest stable, as to not have any surprising new features that could already be in the development build. I would really appreciate a bug fix release if possible, I think it makes sense as there's still roughly 5 months to the next release, however I understand if you'd rather bundle them up for the next release.

[mtf90]

No worries, we can look into an intermediate release. The only thing that worries me is that the DOT parser re-write also includes API changes (the signature for parsing custom elements changed to Function<String, String>) so it would not be a clean drop-in replacement. Maybe we will just release a new "major" version mid-year then.

If you look at the changelogs for the upcoming releases of AutomataLib and LearnLib, you'll see that it mostly affects only niche areas of the libraries -- most "standard" code should not be affected by the changes.

For you to not be blocked by the faulty DOT parser of the latest release, I think it would be best to have a small peek into the development versions. We have not planned anything big for the upcoming weeks, so you should be safe regarding refactorings. In fact, if you happen to stumble upon further issues we can quickly fix them. I have also encountered some oddities in my own projects that I want to investigate so there may be some more bugfix commits pending but that is mostly internal code. I hope to have everything figured out in the next weeks.

Once the next release is published you would then only have to adjust the version of you dependencies.

[mtf90]

Fixed with 7ad78a6. The LearnLib distribution should follow soon (likely tomorrow).

[mtf90]

FYI: The next LearnLib version has been released with LearnLib/learnlib@9e1a34b. The JARs should sync with maven central soon.