tsort: segfault on large cycles #8695
Description
Hi!
I've used the following script to generate loop of 100000 items
And tried to run tsort on it:
#!/usr/bin/env python3
# cycle_10000.py
# Prints edges of a single cycle with 10000 nodes in the format: "NodeFrom NodeTo"
import sys
def print_cycle(n: int = 100000, start_label: int = 1):
end_label = start_label + n - 1
out = sys.stdout.write
for i in range(start_label, end_label):
out(f"{i} {i+1}\n")
# last node -> first node
out(f"{end_label} {start_label}\n")
if __name__ == "__main__":
print_cycle()
Gnu tsort:
dmis@dmis-asus-N7600PC:~/WORKSPACE/coreutils$ tsort cycle.txt
tsort: cycle.txt: input contains a loop:
and hangs (probably on printing)
dmis@dmis-asus-N7600PC:~/WORKSPACE/coreutils$ target/release/coreutils tsort cycle.txt
Segmentation fault (core dumped)
I've found that the cycle detection:
- Uses recursive dfs -- that may explain segfault (stack overflow)
- It uses linear search (contains on vector) for checking node in the cycle. That may degrade on large cycles as well -- https://github.com/uutils/coreutils/blob/main/src/uu/tsort/src/tsort.rs#L258