tsort: GNU test cases fail even though our output is still valid

Open Beginner friendly
#7,094 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
1/5
Estimated time
Under an hour
Newbie friendliness
88/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
perl, rust
Domain
cli, testing-qa

Research direction

Start with the tree-1 and tree-2 cases in tests/misc/tsort.pl and inspect how build-gnu.sh regenerates or updates GNU test cases. Run the relevant tsort test to confirm the current outputs differ while remaining valid topological orderings. Done means the cases accept the implementation's valid output without masking other failures.

Written by the indexing model from the issue text.

Description

U - tsort

For the test cases named tree-1 and tree-2 in the GNU test file tests/misc/tsort.pl, our implementation of tsort produces an output different from GNU tsort but still valid. (In general, there may be more than one valid topological ordering for a given directed acyclic graph.) The test cases will fail due to this difference.

One option is to use our build-gnu.sh script to modify the GNU test cases as follows:

diff --git a/tests/misc/tsort.pl b/tests/misc/tsort.pl
index f1ca28a08..1fb256139 100755
--- a/tests/misc/tsort.pl
+++ b/tests/misc/tsort.pl
@@ -41,9 +41,9 @@ my @Tests =
     {OUT => "a\nb\nc\nd\ne\nf\ng\n"}],
 
    ['tree-1', {IN => "a b b c c d d e e f f g\nc x x y y z\n"},
-    {OUT => "a\nb\nc\nx\nd\ny\ne\nz\nf\ng\n"}],
+    {OUT => "a\nb\nc\nd\nx\ne\ny\nf\nz\ng\n"}],
    ['tree-2', {IN => "a b b c c d d e e f f g\nc x x y y z\nf r r s s t\n"},
-    {OUT => "a\nb\nc\nx\nd\ny\ne\nz\nf\nr\ng\ns\nt\n"}],
+    {OUT => "a\nb\nc\nd\nx\ne\ny\nf\nz\ng\nr\ns\nt\n"}],
 
    # Before coreutils-5.0.1, given an odd number of input tokens,
    # tsort would accept that and treat the input as if an additional

Maybe there are other solutions as well.

Dominant language
Rust
Stars
24.1k
Forks
2k
Avg merge
1d 4h
Merged PRs (30d)
371

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from uutils/coreutils

All issues in uutils/coreutils

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.