[critical/blocking] stack overflow: infinite exceptions when opening Conflict editor on a relation

[verdy_p]

java.lang.StackOverflowError
	at sun.java2d.pipe.AlphaColorPipe.drawParallelogram(Unknown Source)
	at sun.java2d.pipe.PixelToParallelogramConverter.drawRectangle(Unknown Source)
	at sun.java2d.pipe.PixelToParallelogramConverter.drawRect(Unknown Source)
	at sun.java2d.SunGraphics2D.drawRect(Unknown Source)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:188)
	at org.openstreetmap.josm.data.osm.Node.visit(Node.java:184)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
	at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
	at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
... (infinitely reported... the initial exception cause is not logged, even in the Java console, due to the stack overflow)

Then JOSM freezes and no longer refreshes its window (and even the Java console freezes)

Certainly a synchronization/serialization issue with the GUI thread.

JOSM development version 5406.

[anonymous]

May be also related to Ticket #7936 (also in Conflit editor).

[verdy_p]

Visibly this is caused by a way with zero nodes in the conflict editor. I don't why this occured, because the way 105079938 (in Madrid, Spain) was absolutely not within my edit area and is completely unrelated to the conflict to solve (in the French region of Franche-Comté). It seems that references to objects get mixed up of objects with zero nodes (deleted objects) are considered as one and then shared spuriously by many other relations, and the conflict editor gets confused when visiting them (e.g. if there are two references to what were distinct objects, both deleted, from the same relation object being edited).

Note: this also affects the current release version :

Repository Root: ​http://josm.openstreetmap.de/svn
Build-Date: 2012-07-23 01:31:06
Last Changed Author: Don-vip
Revision: 5356
Repository UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
URL: ​http://josm.openstreetmap.de/svn/trunk
Last Changed Date: 2012-07-22 22:36:44 +0200 (Sun, 22 Jul 2012)
Last Changed Rev: 5356

Identification: JOSM/1.5 (5356 fr)
Memory Usage: 1486 MB / 2714 MB (859 MB allocated, but free)
Java version: 1.7.0_05, Oracle Corporation, Java HotSpot(TM) 64-Bit Server VM
Operating system: Windows 7

Dataset consistency test:
[WARN - ZERO NODES] Way {Way id=105079938 version=2 VT nodes=[]} has zero nodes

Plugin: cadastre-fr (28412)
Plugin: epci-fr (26960)
Plugin: licensechange (28412)
Plugin: mapdust (28412)
Plugin: merge-overlap (28412)
Plugin: multipoly-convert (28412)
Plugin: openstreetbugs (28412)
Plugin: osmarender (28412)
Plugin: reltoolbox (28412)
Plugin: reverter (28535)
Plugin: undelete (28501)
Plugin: waydownloader (28412)

java.lang.StackOverflowError

at sun.java2d.pipe.AlphaColorPipe.drawParallelogram(Unknown Source)
at sun.java2d.pipe.PixelToParallelogramConverter.drawRectangle(Unknown Source)
at sun.java2d.pipe.PixelToParallelogramConverter.drawRect(Unknown Source)
at sun.java2d.SunGraphics2D.drawRect(Unknown Source)
at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:188)
at org.openstreetmap.josm.data.osm.Node.visit(Node.java:184)
at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)
at org.openstreetmap.josm.gui.dialogs.ConflictDialog$4.visit(ConflictDialog.java:208)
at org.openstreetmap.josm.data.osm.Relation.visit(Relation.java:165)

[...the rest is sniped as these two last lines is repeated many times infinitely up to the max log size...]

[verdy_p]

I saved My .osm file and it looks like the way affected above was in fact not completely loaded from the server. It has the correct version 2, and the correct timestamp, but it contains only a few tags of that version, but NO <nd ref='...'> member for that version.

In fact a lot of nodes are missing each time : the server seems to NOT send all members when loading a way or a relation. IF a few nodes or members are missing, then we'll have conflicts detected when uploading modified data. But if there remains NO member node at all in a way that was apparetly successfully loaded, this causes an infinite loop of exceptions in JOSM when it tried to visit it.

The consistency checker (run from the bug report alert) correctly detects that, but the conflict editor does not check that there are effectively some nodes in a way and fails when trying to select it on the map, and the map renderer also fails and turns into an infinite loop too.

Unfortunately, I can't find any way to synchronize the OSM file: as soon as I try to select it in order to reload it from the server, JOSM hangs in an infinite loop. If I load that .osm file but do not select anything and then use "load object" to load that missing object by reference, JOSM will detect a conflict and will fail to edit that conflict because the server object and the local object use the SAME version & timestamp.

Ideally:

• the conflict editor should work work with ways whose ALL nodes are missing for any kind of reasons.
• the server should generate a data signature to all objects, or at least should indicate, in an XML atttribute of the <way> element the number of member nodes it is supposed to contain (this will allow consistency check on the client side). It should do the same thing for the number of members in relation objects, to make sure that the data loaded from the server was complete and not unexpectedly interrupted before end on the server side.

Objects may have been loaded also at one time where some members were still hidden by the redaction bot, but they have been "resurrected" later by making them visible. Some inconsistant data see to be reported by the server about those resurrected/inhidden objects.

[verdy_p]

Hmmmm... After thought the infinite loop comes from the fact that relation 8642 contains a member with role "defaults" that references the relation ref='957702', in which the relation 8642 is also a member (with role "apply_to").

The conflicts resolver attempts to visit the complete tree of all children and subchildren of a relation, without detecting the possible loop of parent relations already visited in the stack !

  <relation id='8642' action='modify' timestamp='2012-06-26T12:49:28Z' uid='13442' user='Damouns' visible='true' version='360' changeset='12022212'>
    <!--(snip)-->
    <member type='relation' ref='957702' role='defaults' /> <!-- !!!!!!! BUG HERE !!!!! -->
    <!--(snip)-->
    <tag k='admin_level' v='4' />
    <tag k='boundary' v='administrative' />
    <tag k='name' v='Franche-Comté' />
    <!--(snip)-->
  </relation>

  <relation id='957702' timestamp='2011-02-01T08:15:07Z' uid='178186' user='mdk' visible='true' version='3' changeset='7152372'>
    <!--(snip)-->
    <member type='relation' ref='8642' role='apply_to' />
    <tag k='name:fr' v='France, vacances scolaires, zone A' />
    <tag k='type' v='defaults' />
    <!--(snip)-->
  </relation>

Note that the relation 8642 v36 was edited by me and someone else that saved his changes in v361 before me, so this raised a version conflict. The conflict resolver however does not support the resolution of such circular references of relations.

What is the validity of such backward reference from a subarea to his parent area ?

[verdy_p]

I confirm the infinite loop is caused effectively in these lines:

205                 public void visit(Relation e) {
207	                for (RelationMember em : e.getMembers()) {
208	                    em.getMember().visit(this);
209	                }
210	            }

This method does not check that the em.getMember() will not return an item that is already in the stack normally maintained by this. But there's no trace in this to record such stack, for example you could add "HashedSet<OsmPrimitive> visited;" member in the new anonymous AbstractVisitor subclass created on line 185 of ConflictDialog.java:

Before visiting each member that you get from "OsmPrimitive m = em.getMember();", first check if it's in the "visited" collection, if yes, do nothing; else add "m" into "visited", then you can "m.visit(this)" and finally remove "m" from "visited".

205                 public void visit(Relation e) {
207	                for (RelationMember em : e.getMembers()) {
208                         OsmPrimitive m = em.getMember();
+                           if (m instanceof Node || m instanceof Way) {
+                               m.visit(this);
+                           } else if (!visited.contains(m)) {
+                               visited.add(m);
+                               try {
+                                   m.visit(this);
+                               } finally {
+                                   visited.remove(m);
+                               }
209	                }
210	            }

The caveat is that the generic Visitor model is slow here, especially when there's a conflict on a very large relation containing lots of levels of children relations. Do you need to recurse here ?

• Only the members of OsmPrimitive types Way and Node may need to be visited here to draw them in conflict for the conflict editor dialog.
• Other types could be simply ignored: remove the else-if clause in this patch above, then you don't need to manage the hashed set containing the already visited primitives.

[stoecker]

Please supply a patch. You actually have currently much deeper insight into this particular part of code than anybody else.

[Don-vip]

Could you please also upload your (bzipped) .osm file to allow us to reproduce this problem ? Thanks.

[anonymous]

You have the small extract above. My .osm file is much too big for you.

I have completely isolated the problem above in the XML sample cited. It can easily be reproduced. by creating an edit conflict in a relation referencing a relation that includes the reverse member reference to the 1st relation.

I gave a small patch above too (a summary of the actual code in fact).

[verdy_p]

Note: I have deleted in my .osm file the member with role "defaults" that was part of relation 8642, so now the modifications in the OSM file could be uploaded completely after correctly resolving that roblematic conflict with JOSM.

[verdy_p]

The steps to reproduce this bug:

• 1st create a relation A referencing relation B as a member, and a relation B referencing relation A as a member. Submit it to the server.
• Use JOSM to download relation A (version 1) in two separate instances of JOSM:
• Modify relation A v1 in the 2nd separate instance of any editor and submit it. Now server has v2.
• Modify relation A v1 in the 1st instance of JOSM, and try uploading it : the version conflict generates the infinite recursion loop in line 208 of ConflictDialog.java

[Don-vip]

Replying to verdy_p@…:

The steps to reproduce this bug:

OK I got it, thanks.

[Don-vip]

Problem reproduced, patch OK, fix on the way.

[Don-vip]

In 5413/josm:

fix #7938 - fix StackOverflowError when painting conflicts of a cyclic relation (patch by verdy_p) + improve javadoc

[verdy_p]

OK your code is similar to what I described above:

221	            public void visit(Relation e) {
222	                for (RelationMember em : e.getMembers()) {
223	                    OsmPrimitive m = em.getMember();
224	                    if (m instanceof Node || m instanceof Way) {
225	                        m.visit(this);
226	                    } else if (m instanceof Relation && !visited.contains(m)) {
227	                        visited.add((Relation) m);
228	                        try {
229	                            m.visit(this);
230	                        } finally {
231	                            visited.remove(m);
232	                        }
233	                    }
234	                }
235	            }

However I note that nodes and ways that are members in the first visited relation will be visited twice, even if relations that are members of that first relation will be visted only once.

A simpler more generic code could be simply (and more generally without using type inference and manual typecasts) :

221                public void visit(Relation e) {
+                      if (!visited.contains(e)) {
+                          visited.add(e);
+                          try {
222                            for (RelationMember em : e.getMembers()) {
223                                em.getMember().visit(this);
230                            }
+                          } finally {
231                            visited.remove(e);
233                        }
234                    }
235                }

This leaves the genericity of the code to handle possible future OSM primitives for collections of members that are not relations (e.g. if a PolyLineString/Polyways primitive is introduced, or an Area primitive, or a Ring primitive, containing only members of type way, leaving relations only to create polymorphic collections).

Note that even if the OSM database is not changed, JOSM could handle and infer such upper-level OpenGIS primitives internally, to simplify the edition, optimize the speed of rendering or selection, or to allow imports from other GIS schemas, before generating a OSM compliant schema, as such upper primitive infered once from the OSM schema would avoid lots of tests, notably for how to render surfaces, or for comparing versions ignoring the orientation of ways which is not always significant, or the starting node of a closed polyline string.

For handling these upper-level geometric constructions (including the future introduction of Beziers ways defined with intermediate off-curve control nodes between on-curve nodes, and the internal generation of computed on-curve nodes from the Bezier definition of on-curve nodes and off-curve control nodes). To help the mutual compatibility, JOSM could reserve (and document) some additional meta-data properties, with geometry helpers like detection of intersections and angles/corners with infinite curvatures but with a defined angle.

So the alternate code above which remains generic, will have the strict minimum needed for the AbstractVisitor model. Only the Relation primitive requires this test of recursions (other upper-level constructions built on top of relations won't need this recursion test, so this would also speed up the rendering).

I made a sample test of this alternate more generic code on a giant OSM file (about 2MB) and it is a bit faster as it avoids many test branches by the type inference and many runtime validation of the typecasts.

[anonymous]

Correction: my giant OSM file was 2GB (containing almost all boundary and coast relations/ways/nodes in Western Europe and dependencies of European countries in the world, with all the other information tags), not just 2 MB.

[Don-vip]

Replying to verdy_p@…:

I made a sample test of this alternate more generic code on a giant OSM file (about 2GB) and it is a bit faster as it avoids many test branches by the type inference and many runtime validation of the typecasts.

OK I'll update it, so.

[Don-vip]

In 5416/josm:

see #7938 - code optimization (patch by verdy_p)