[Dot] Sporadic rashes during edge spline creation

[GadgetSteve]

Ported Issue from Mantis
Original ID: 1814
Reported By: Devin Pitcher

SEVERITY: MAJOR
Submitted: 2010-02-09 23:41:13

OS: X86-OSX-10.5.8

VERSION: 2.24.0

DESCRIPTION

Hello, I've been using Graphviz to graph dependencies in software modules and have been quite happy with the results but I've recently been hitting an abort() within shortest.c - triangulate() when I layout the graph. The problem seems to occur when I have multiple nested clusters in the graph. Here is the relevant part of a backtrace:

#0  0x93edfe42 in __kill ()
#1  0x93edfe34 in kill$UNIX2003 ()
#2  0x93f5223a in raise ()
#3  0x93f5e679 in abort ()
#4  0x006e68c7 in triangulate (pnlps=0x22e951e0, pnln=5) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/pathplan/shortest.c:343
#5  0x006e6082 in Pshortestpath (polyp=0xbfffd874, eps=0xbfffd844, output=0xbfffd86c) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/pathplan/shortest.c:194
#6  0x0066d7d6 in _routesplines (pp=0x22e7f940, npoints=0xbfffdec8, polyline=0) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/common/routespl.c:421
#7  0x0066e027 in routesplines (pp=0x22e7f940, npoints=0xbfffdec8) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/common/routespl.c:533
#8  0x00690d31 in make_flat_edge (sp=0xbfffe050, P=0x22e7f940, edges=0x4136600, ind=0, cnt=1, et=8) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/dotgen/dotsplines.c:1249
#9  0x0068ce8e in _dot_splines (g=0x22e16910, normalize=1) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/dotgen/dotsplines.c:388
#10 0x0068d0d3 in dot_splines (g=0x22e16910) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/dotgen/dotsplines.c:452
#11 0x0068bd1a in dot_layout (g=0x22e16910) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/dotgen/dotinit.c:273
#12 0x006b49e2 in gvLayoutJobs (gvc=0x22b98060, g=0x22e16910) at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/gvc/gvlayout.c:88
#13 0x006b0c15 in gvLayout (gvc=0x22b98060, g=0x22e16910, engine=0x15775c3 "dot") at /Users/devin/sti-qt4.6/src/graphviz/graphviz-2.24.0/lib/gvc/gvc.c:79

As I've been trying to debug this myself (based on my very limited understanding of the code) I've noticed that I get a lot of sets of colinear vertices within the polygon used for calculating the spline. I tried tweaking the code to massage the polygon data by removing the "extra" vertex when three adjacent colinear vertices existed before passing the polygon to triangulation. Eventually that lead to an abort() further down the road when it was unable to find a triangle containing one of the edge endpoints. In my case the endpoint was on the border of a triangle.

Alas, I'm spinning my wheels not getting anywhere at this point. I'm including some sample input that caused the crash above. Sorry for the length of the sample. This is the smallest sample I've been able to replicate the crash with.

Thanks in advance.

Regards,
Devin Pitcher

ADDITIONAL INFORMATION

I'd prefer that my input be kept private.

[GadgetSteve]

Resolved in 2.26.3