Attachment "graphops-tarjan-fix-with-test.diff" to
ticket [0f65bfa2d3]
added by
anonymous
2026-08-08 16:23:01.
Fix regression of SF Tcllib Bug 2815302 in ::struct::graph::op::TarjanSub,
and add a whitespace-canary test to the tarjan testsuite.
TarjanSub removes the visited node from the 'all' set with
'struct::set subtract all $start', passing a single element where
subtract expects a set. For node names containing whitespace the name
is split into multiple bogus elements, the real element is never
removed, 'all' never shrinks, and tarjan's outer
'while {[llength $all]}' loop never terminates.
This is a regression: fixed 2009-07-10 (struct/ChangeLog, SF Bug
2815302) by switching such sites to 'struct::set exclude' (removes a
single element). The exclude calls survive elsewhere in graphops.tcl
(Fleury, isCutVertex?), but TarjanSub reverted to subtract, apparently
during the 0.10/0.11 merge. Applies to tcllib 1.21 through current
trunk (struct::graph::op 0.11.4).
Note: without the code fix the new test case hangs the testsuite
rather than failing cleanly (tcltest has no per-test timeout).
--- a/modules/struct/graphops.tcl
+++ b/modules/struct/graphops.tcl
@@ -3109,7 +3109,7 @@
# Import the tracer state from our caller.
upvar 1 g g index index lowlink lowlink instack instack result result pending pending all all
- struct::set subtract all $start
+ struct::set exclude all $start
set component {}
set index($start) $counter
--- a/modules/struct/graph/tests/ops/tarjan.test
+++ b/modules/struct/graph/tests/ops/tarjan.test
@@ -96,4 +96,17 @@
mygraph destroy
} -result {1b 1w 2b 2w 3b 3w 4b 4w 5b 5w}
+test graphop-t${treeimpl}-g${impl}-s${setimpl}-st${stkimpl}-q${queimpl}-tarjan-3.9 {tarjan, nodes with whitespace in names, regression tcllib SF bug 2815302} -setup {
+ struct::graph mygraph
+ mygraph node insert {beamsect_C C}
+ mygraph node insert {plain}
+ mygraph node insert {loner}
+ mygraph arc insert {beamsect_C C} {plain} a1
+ mygraph arc insert {plain} {beamsect_C C} a2
+} -body {
+ setsetcanon [struct::graph::op::tarjan mygraph]
+} -cleanup {
+ mygraph destroy
+} -result {loner {{beamsect_C C} plain}}
+
# ---------------------------------------------------