Tcl Library Source Code

Artifact [b928c19728]
Login

Artifact b928c19728f35469971b641bde1e579aaf7b43b3baf97ceaaf13a78c82b22d4a:

Attachment "graphops-tarjan-fix-with-test.diff" to ticket [0f65bfa2d3] added by anonymous 2026-08-08 16:23:01. (unpublished)
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}}
+
 # ---------------------------------------------------