Quantcast

Bizarre issue with TopologicalOrderIterator

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Bizarre issue with TopologicalOrderIterator

org.jgrapht
Hi.

I've been using jgrapht for over a year now to handle various tasks in
the implementation of a compiler. Today, I've started having an issue that's
causing me to question my own sanity.

I use jgrapht to handle the graph of dependencies between terms, types,
and modules in a shading language I've developed:

  http://mvn.io7m.com/io7m-jparasol

When attempting to run the test suite today (despite the code not having
been changed since the last commit on 2014-11-15), I suddenly find that
there's a test failing.

Specifically, I use jgrapht to handle module dependencies. The language
allows the programmer to define modules/terms/types in any order, but
the target language (GLSL) requires things to be declared in the order
of their dependencies (like C/C++). So, using a directed acyclic graph
to detect circular imports, I then sort modules topologically in
preparation for emitting GLSL declarations. I actually use the reverse
of the topological order for declarations, but that makes no difference
here.

So, for example:

--8<--

module N is
  import x.y.M;
end;

module M is

end;

module Q is
  import x.y.P;
end;

module P is
  import x.y.M;
end;

--8<--

The expected topological order for the above is something like:

  [Q, N, P, M]

  M has no dependencies, so it should probably be declared first.
  Because Q depends on P, it must be declared after P.
  Because P depends on M, it must be declared after M.
  Because N depends on M, it must be declared after M.
  P and N could be declared in either order, obviously.

Reversing this gives me the order that I'd need to use for declarations
in the target language.

However, I'm suddenly getting the order [N, Q, P, M] from the
test suite, which doesn't really make sense whatever way I try to look
at it. The code that handles imports is pretty simple, and I've
extracted it (and the test case) to this easy example:

--8<--
package com.io7m.graphtbug;

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

import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
import org.jgrapht.traverse.TopologicalOrderIterator;
import org.junit.Assert;
import org.junit.Test;

public final class JGraphTBugTest
{
  static final class Import
  {
    private final ModulePath importer;
    private final ModulePath target;

    public Import(
      final ModulePath in_importer,
      final ModulePath in_target)
    {
      this.importer = in_importer;
      this.target = in_target;
    }

    @Override public int hashCode()
    {
      final int prime = 31;
      int result = 1;
      result = (prime * result) + this.importer.hashCode();
      result = (prime * result) + this.target.hashCode();
      return result;
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final Import other = (Import) obj;
      if (!this.importer.equals(other.importer)) {
        return false;
      }
      if (!this.target.equals(other.target)) {
        return false;
      }
      return true;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[Import ");
      builder.append(this.importer);
      builder.append(" → ");
      builder.append(this.target);
      builder.append("]");
      return builder.toString();
    }

  }

  static final class ModulePath
  {
    private final String name;

    ModulePath(
      final String in_name)
    {
      this.name = in_name;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[");
      builder.append(this.name);
      builder.append("]");
      return builder.toString();
    }

    @Override public int hashCode()
    {
      return this.name.hashCode();
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final ModulePath other = (ModulePath) obj;
      return this.name.equals(other.name);
    }
  }

  @Test public void testTopology()
    throws CycleFoundException
  {
    final DirectedAcyclicGraph<ModulePath, Import> g =
      new DirectedAcyclicGraph<ModulePath, Import>(Import.class);

    final ModulePath mm = new ModulePath("x.y.M");
    final ModulePath mn = new ModulePath("x.y.N");
    final ModulePath mp = new ModulePath("x.y.P");
    final ModulePath mq = new ModulePath("x.y.Q");

    g.addVertex(mn);
    g.addVertex(mm);
    g.addVertex(mp);
    g.addVertex(mq);

    g.addDagEdge(mn, mm, new Import(mn, mm));
    g.addDagEdge(mp, mm, new Import(mp, mm));
    g.addDagEdge(mq, mp, new Import(mq, mp));

    final TopologicalOrderIterator<ModulePath, Import> iter =
      new TopologicalOrderIterator<ModulePath, Import>(g);

    final List<ModulePath> ordered = new ArrayList<ModulePath>();

    while (iter.hasNext()) {
      final ModulePath p = iter.next();
      ordered.add(p);
    }

    System.out.println(ordered);
    Assert.assertEquals(mq, ordered.get(0));
    Assert.assertEquals(mn, ordered.get(1));
    Assert.assertEquals(mp, ordered.get(2));
    Assert.assertEquals(mm, ordered.get(3));
  }
}
--8<--

The output is:

  [[x.y.N], [x.y.Q], [x.y.P], [x.y.M]]
 
Followed by an assertion error (expected Q but got N).

What's utterly bizarre about this whole situation is that nothing has
changed in the environment from two weeks ago. Same Java version, no significant OS
updates, same jgrapht version, no changes to the code. I even have log
files showing the test output from unit tests executed on 2014-11-15
that show the output as:

  [[ModulePathFlat x.y.Q], [ModulePathFlat x.y.N], [ModulePathFlat x.y.P], [ModulePathFlat x.y.M]]

I'm using Java 8, but have tested on Java 7 too. I'm using jgrapht-core 0.9.0 from Maven Central.

Any ideas would be appreciated.

M

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bizarre issue with TopologicalOrderIterator

John Sichi
Administrator

I don't see any dependency between Q and N in your code, so why do you think their relative order would be deterministic?

On Dec 3, 2014 2:10 PM, <[hidden email]> wrote:
Hi.

I've been using jgrapht for over a year now to handle various tasks in
the implementation of a compiler. Today, I've started having an issue that's
causing me to question my own sanity.

I use jgrapht to handle the graph of dependencies between terms, types,
and modules in a shading language I've developed:

  http://mvn.io7m.com/io7m-jparasol

When attempting to run the test suite today (despite the code not having
been changed since the last commit on 2014-11-15), I suddenly find that
there's a test failing.

Specifically, I use jgrapht to handle module dependencies. The language
allows the programmer to define modules/terms/types in any order, but
the target language (GLSL) requires things to be declared in the order
of their dependencies (like C/C++). So, using a directed acyclic graph
to detect circular imports, I then sort modules topologically in
preparation for emitting GLSL declarations. I actually use the reverse
of the topological order for declarations, but that makes no difference
here.

So, for example:

--8<--

module N is
  import x.y.M;
end;

module M is

end;

module Q is
  import x.y.P;
end;

module P is
  import x.y.M;
end;

--8<--

The expected topological order for the above is something like:

  [Q, N, P, M]

  M has no dependencies, so it should probably be declared first.
  Because Q depends on P, it must be declared after P.
  Because P depends on M, it must be declared after M.
  Because N depends on M, it must be declared after M.
  P and N could be declared in either order, obviously.

Reversing this gives me the order that I'd need to use for declarations
in the target language.

However, I'm suddenly getting the order [N, Q, P, M] from the
test suite, which doesn't really make sense whatever way I try to look
at it. The code that handles imports is pretty simple, and I've
extracted it (and the test case) to this easy example:

--8<--
package com.io7m.graphtbug;

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

import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph.CycleFoundException;
import org.jgrapht.traverse.TopologicalOrderIterator;
import org.junit.Assert;
import org.junit.Test;

public final class JGraphTBugTest
{
  static final class Import
  {
    private final ModulePath importer;
    private final ModulePath target;

    public Import(
      final ModulePath in_importer,
      final ModulePath in_target)
    {
      this.importer = in_importer;
      this.target = in_target;
    }

    @Override public int hashCode()
    {
      final int prime = 31;
      int result = 1;
      result = (prime * result) + this.importer.hashCode();
      result = (prime * result) + this.target.hashCode();
      return result;
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final Import other = (Import) obj;
      if (!this.importer.equals(other.importer)) {
        return false;
      }
      if (!this.target.equals(other.target)) {
        return false;
      }
      return true;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[Import ");
      builder.append(this.importer);
      builder.append(" → ");
      builder.append(this.target);
      builder.append("]");
      return builder.toString();
    }

  }

  static final class ModulePath
  {
    private final String name;

    ModulePath(
      final String in_name)
    {
      this.name = in_name;
    }

    @Override public String toString()
    {
      final StringBuilder builder = new StringBuilder();
      builder.append("[");
      builder.append(this.name);
      builder.append("]");
      return builder.toString();
    }

    @Override public int hashCode()
    {
      return this.name.hashCode();
    }

    @Override public boolean equals(
      final Object obj)
    {
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (this.getClass() != obj.getClass()) {
        return false;
      }
      final ModulePath other = (ModulePath) obj;
      return this.name.equals(other.name);
    }
  }

  @Test public void testTopology()
    throws CycleFoundException
  {
    final DirectedAcyclicGraph<ModulePath, Import> g =
      new DirectedAcyclicGraph<ModulePath, Import>(Import.class);

    final ModulePath mm = new ModulePath("x.y.M");
    final ModulePath mn = new ModulePath("x.y.N");
    final ModulePath mp = new ModulePath("x.y.P");
    final ModulePath mq = new ModulePath("x.y.Q");

    g.addVertex(mn);
    g.addVertex(mm);
    g.addVertex(mp);
    g.addVertex(mq);

    g.addDagEdge(mn, mm, new Import(mn, mm));
    g.addDagEdge(mp, mm, new Import(mp, mm));
    g.addDagEdge(mq, mp, new Import(mq, mp));

    final TopologicalOrderIterator<ModulePath, Import> iter =
      new TopologicalOrderIterator<ModulePath, Import>(g);

    final List<ModulePath> ordered = new ArrayList<ModulePath>();

    while (iter.hasNext()) {
      final ModulePath p = iter.next();
      ordered.add(p);
    }

    System.out.println(ordered);
    Assert.assertEquals(mq, ordered.get(0));
    Assert.assertEquals(mn, ordered.get(1));
    Assert.assertEquals(mp, ordered.get(2));
    Assert.assertEquals(mm, ordered.get(3));
  }
}
--8<--

The output is:

  [[x.y.N], [x.y.Q], [x.y.P], [x.y.M]]

Followed by an assertion error (expected Q but got N).

What's utterly bizarre about this whole situation is that nothing has
changed in the environment from two weeks ago. Same Java version, no significant OS
updates, same jgrapht version, no changes to the code. I even have log
files showing the test output from unit tests executed on 2014-11-15
that show the output as:

  [[ModulePathFlat x.y.Q], [ModulePathFlat x.y.N], [ModulePathFlat x.y.P], [ModulePathFlat x.y.M]]

I'm using Java 8, but have tested on Java 7 too. I'm using jgrapht-core 0.9.0 from Maven Central.

Any ideas would be appreciated.

M

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bizarre issue with TopologicalOrderIterator

org.jgrapht
On 2014-12-03T22:18:50 -0800
John Sichi <[hidden email]> wrote:

> I don't see any dependency between Q and N in your code, so why do you
> think their relative order would be deterministic?

Hah, I guess that'd be the "question my own sanity" part - I had no idea
the algorithm even could be nondeterministic. Out of idle curiousity,
how does this happen? I didn't notice any concurrency or anything along
those lines.

I see that the lack of dependency between Q and N does allow that
returned order to make sense! I'll fix the test.

M

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bizarre issue with TopologicalOrderIterator

Alexander Herz
That is java for you,
data structures using hashes often use the value of references to
compute the hash. Since the pointer values may change every run, the
order things are iterated over may change every run (there is no
guarantee that the n-th call to malloc in an application always yields
the same address).
In order to make your application deterministic and debugable you want
to use LinkedHash.. data structures. These guarantee deterministic
behaviour (in single threaded execution).

Alex

On 04.12.2014 13:50, [hidden email] wrote:

> On 2014-12-03T22:18:50 -0800
> John Sichi <[hidden email]> wrote:
>
>> I don't see any dependency between Q and N in your code, so why do you
>> think their relative order would be deterministic?
> Hah, I guess that'd be the "question my own sanity" part - I had no idea
> the algorithm even could be nondeterministic. Out of idle curiousity,
> how does this happen? I didn't notice any concurrency or anything along
> those lines.
>
> I see that the lack of dependency between Q and N does allow that
> returned order to make sense! I'll fix the test.
>
> M
>
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
> _______________________________________________
> jgrapht-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bizarre issue with TopologicalOrderIterator

org.jgrapht
> On 2014-12-04T14:02:52 +0100
> Alexander Herz <[hidden email]> wrote:
>
> That is java for you,
> data structures using hashes often use the value of references to
> compute the hash. Since the pointer values may change every run, the
> order things are iterated over may change every run (there is no
> guarantee that the n-th call to malloc in an application always yields
> the same address).
> In order to make your application deterministic and debugable you want
> to use LinkedHash.. data structures. These guarantee deterministic
> behaviour (in single threaded execution).
 
Is this the case with the TopologicalOrderIterator (or the
DirectAcyclicGraph)?
 
I only use structural equality and hashes derived from values, as
opposed to reference equality or Object.hashCode() in my own code.
 
M

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bizarre issue with TopologicalOrderIterator

Alexander Herz
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

The DAG internally uses HashSets/Maps to store vertices and edges,
these cause the non determinism when iterating, so it is nothing you
do :) Basically anything you compute by iterating over items in the
set (or the key in the map) is non deterministic.
The TopolOrderIterator uses these operations to compute the order, so
it is non deterministic.

Alex

On 12/04/2014 03:43 PM, [hidden email] wrote:

>> On 2014-12-04T14:02:52 +0100 Alexander Herz
>> <[hidden email]> wrote:
>>
>> That is java for you, data structures using hashes often use the
>> value of references to compute the hash. Since the pointer values
>> may change every run, the order things are iterated over may
>> change every run (there is no guarantee that the n-th call to
>> malloc in an application always yields the same address). In
>> order to make your application deterministic and debugable you
>> want to use LinkedHash.. data structures. These guarantee
>> deterministic behaviour (in single threaded execution).
>
> Is this the case with the TopologicalOrderIterator (or the
> DirectAcyclicGraph)?
>
> I only use structural equality and hashes derived from values, as
> opposed to reference equality or Object.hashCode() in my own code.
>
> M
>
> ------------------------------------------------------------------------------
>
>
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and
> Dashboards with Interactivity, Sharing, Native Excel Exports, App
> Integration & more Get technology previously reserved for
> billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
>
>
_______________________________________________
> jgrapht-users mailing list [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBAgAGBQJUgIFvAAoJEGSriSINjxXwGh4IAKYZK+/r/MNh7oQrzxQx1a33
jaQSO7TruSUV76T8BUBI4XvpNNSN1i4MFuZwovSBa+uT434uMc9qLPEAnbrxJmEh
bFpeFJaH9T7SkP5YUqG/9sSkvti6nD7uD/PiYSL7jl4xLZB113hP8nTO/X1YO1Hh
IOhWZe49YMQE3HnNvlxq+UsQKxw9g88guNbpb6dFsZY7DXFcVRjAnmV10NwhiphX
EbHB54RvyeDYij5rOTOrz0CKawGcZUcsQKWOK9mWrJjgITivzXNd5pTfVHTLUN+A
sNdHTnW22cCVsFApJ2iBPNM5kdSN9zNctsBn4mm+omi/VRAmhKKI9G7qWLam/pk=
=xlh5
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...