Skip to content
graphviz-pure

pack: C's fillEdge reads past a one-point spline, so polyomino packing of components depends on garbage memory

Kind
Upstream C behaviour
Severity
medium
Engine
all
Category
layout
Cases
2
Seeds
20914, 21147
Tracking
GitHub issuewon't fix
Labels
fidelityfuzzengine:sfdpengine:neatoupstream-cwontfix

When nodes overlap, clipping can leave an edge with a one-point Bézier (here the multi-edge n1 -- n9, routed by the straight-line fallback because nodes touch: pos="549,163.11"). The packer (pack=, or sfdp/neato/fdp packing disconnected components with doSplines) rasterises each edge into polyomino cells with fillEdge, which reads bz.list[1] without checking the size. In C that reads past the end of the list, and whatever is there becomes a cell — here extra cells near the origin of component 0 (-v3 shows 114 cells with splines=polyline and 106 with splines=spline, same layout). The extra cells move the singleton component n14 from (247,106) to (379,414). The port uses the point itself.

Reproducer

graph "fuzz 21147" {
layout=sfdp;
splines="polyline";
"n0" [];
"n1" [height="1.64"];
"n8" [];
"n10" [];
"n14" [];
"n15";
"n16" [];
"n17" [];
"n18" [];
"n0" -- subgraph "s3" {"n20" "n9" "n5"};
"n0" -- "n11" [];
"n0" -- "n13" [];
"n1" -- "n8";
"n1" -- "n9" [];
"n1" -- subgraph "s18" {"n17" "n15" "n12"};
"n1" -- subgraph "s20" {"n11" "n10" "n16"};
"n6":"sw" -- "n7" [];
"n6" -- subgraph "s53" {"n9" "n6" "n10"};
{"n20" "n8" "n16"} -- "n10";
"n7" -- "n11";
{"n20"} -- "n9";
"n8" -- "n13";
"n9" -- subgraph "s70" {"n17" "n1"};
{"n3" "n18"} -- "n13";
"n11":"ne" -- "n12";
"n12" -- "n13":"ne" [];
}

GVBINDIR=<pango-free plugins> dot -Ksfdp -Tsvg repro.gv   # C Graphviz 16.1.0
graphviz-pure -Ksfdp -Tsvg repro.gv                              # port

C output vs port

--- c.svg
+++ rust.svg
@@ -167,2 +167,2 @@
-<ellipse fill="none" stroke="black" cx="379" cy="-414" rx="27" ry="18"/>
-<text xml:space="preserve" text-anchor="middle" x="379" y="-409.8" font-family="Times,serif" font-size="14.00">n14</text>
+<ellipse fill="none" stroke="black" cx="247" cy="-106" rx="27" ry="18"/>
+<text xml:space="preserve" text-anchor="middle" x="247" y="-101.8" font-family="Times,serif" font-size="14.00">n14</text>

stderr:

--- c.stderr
+++ rust.stderr
@@ -1 +0,0 @@
-Warning: some nodes with margin (3.20,3.20) touch - falling back to straight line edges

Root cause

C, lib/pack/pack.c:170-200 (fillEdge): pt = bz.list[0]; hpt = bz.list[1]; k = 2; with no size check; the result depends on what follows the one-element allocation. The one-point spline itself comes from clip_and_install (lib/common/splines.c:234) on overlapping nodes; port and C produce the same spline.

Port, crates/graphviz-pure-layout/src/pack/mod.rs:499-504: a one-point spline uses bz.list[0] for the missing second point (documented as C undefined behaviour).

Why the port cannot match: the value C reads is out-of-bounds heap memory (it changes with splines=polyline vs splines=spline, which only changes how the 1-point list was allocated). The port's choice (a degenerate segment at the point) is the defined behaviour C presumably intends. Suggest wontfix; report upstream (fillEdge should check bz.size).

A neato reproducer, repro-neato.gv, gets its one-point spline from a different source: the self-loop of a zero-size shape=plain, fixedsize=true node, which C writes as a single point. Removing that node makes C and the port agree.

digraph "G" {
layout=neato;
"v35" [shape="plain", fixedsize="true"];
"v22" -> "v22";
"v24" -> "v35";
"v35" -> "v22" [dir="back", fontsize="10.8"];
"v11":"n" -> "v4";
"v7" -> subgraph "s14" {"v24" "v16" "v8"};
"v31" -> "v4";
"v35" -> "v35" [headlabel="end\r中文标签\re=mc²\ry1", penwidth="4.86"];
"v15" -> "v15" [headlabel="…"];
}

Cases

2 fuzz cases, seeds 20914, 21147 (sfdp 21147, neato 20914). Regenerate a case with python3 -I scripts/fuzz-gen.py --seed N (byte for byte for these seeds).

Files

tests/fuzz-open/028-pack-filledge-one-point-spline (repro.gv, c.svg, rust.svg, cmd.txt, cases.txt)

C and the port

Comparing…
C Graphviz 16.1.0 output, cyan plategraphviz-pure output, magenta plate

C onlyport onlyboth: in register

c.stderr
Warning: some nodes with margin (3.20,3.20) touch - falling back to straight line edges
rust.stderr
(empty)

Reproduce

repro.gv
graph "fuzz 21147" {
layout=sfdp;
splines="polyline";
"n0" [];
"n1" [height="1.64"];
"n8" [];
"n10" [];
"n14" [];
"n15";
"n16" [];
"n17" [];
"n18" [];
"n0" -- subgraph "s3" {"n20" "n9" "n5"};
"n0" -- "n11" [];
"n0" -- "n13" [];
"n1" -- "n8";
"n1" -- "n9" [];
"n1" -- subgraph "s18" {"n17" "n15" "n12"};
"n1" -- subgraph "s20" {"n11" "n10" "n16"};
"n6":"sw" -- "n7" [];
"n6" -- subgraph "s53" {"n9" "n6" "n10"};
{"n20" "n8" "n16"} -- "n10";
"n7" -- "n11";
{"n20"} -- "n9";
"n8" -- "n13";
"n9" -- subgraph "s70" {"n17" "n1"};
{"n3" "n18"} -- "n13";
"n11":"ne" -- "n12";
"n12" -- "n13":"ne" [];
}
cmd.txt
C:    GVBINDIR=<pango-free plugins> dot -Ksfdp -Tsvg repro.gv
port: graphviz-pure -Ksfdp -Tsvg repro.gv


neato variant (repro-neato.gv):
C:    GVBINDIR=<pango-free plugins> dot -Kneato -Tsvg repro.gv
port: graphviz-pure -Kneato -Tsvg repro.gv
cases.txt
r3/diff/s20914.gv seed=20914
r3/diff/s21147.gv seed=21147  # its earlier minimised form was the star obstacle issue (issue #17, fixed); the full case still differs from this cause

Files: c-neato.svg, c.stderr, c.svg, cases.txt, cmd.txt, repro-neato.gv, repro.gv, rust-neato.svg, rust.stderr, rust.svg. Source: tests/fuzz-open/028-pack-filledge-one-point-spline.

All open issues