Discussion:
bug#31472: tsort reporting false loop in input. unix2dos fixes the problem.
(too old to reply)
Ivan Ivanov
2018-05-16 09:23:12 UTC
Permalink
Hi all,

tsort is reporting loop in my input file, but the loop doesn't exist
really.

I have checked this manually, examining the contents of the file,
related to the reported loop.

Further more, if I run the input file trhough unix2dos – it works, so I
suspect some strange problem with the unix newlines.

The input file is generated with python script on the Ubuntu 16.04.3 so
all newlines should be the same.

Test environments (acting the same way):
---------------------------------------

Ubuntu 16.04.3 LTS
tsort (coreutils) 8.25

and

Debian GNU/Linux 9 (stretch)
tsort (coreutils) 8.26


Reproduction steps:
---------------------------------------
$ unxz for-tsort-bug-example.txt.xz
$ tsort for-tsort-bug-example.txt > /dev/null

the above command should produce:
tsort: for-tsort-bug-example.txt: input contains a loop:
tsort: 15731101
tsort: 15731102

$ cat for-tsort-bug-example.txt | unix2dos | tsort > /dev/null

should exit properly.

You may choose to first convert the file and than call tsort and it
will exit properly again:
$ unix2dos for-tsort-bug-example.txt
$ tsort for-tsort-bug-example.txt > /dev/null

If you have further questions to investigate the issue, feel free to
write back!

Best wishes,

Ivan Ivanov
Ivan Ivanov (by way of Ivan Ivanov )
2018-05-16 11:15:02 UTC
Permalink
Hi again,

I've digged more into this, and I found that unix2dos doesn't fix
the problem, but just masks the tsort behaviour.

If you point the tsort result into a file, you will notice, that tsort
breaks some of the newline chars. The input file seems to be ok.

I am still looking into this, but I am now a little bit suspicious if
this is really a tsort bug.

If I find something useful, I will share it.

Ivan Ivanov

На Wed, 16 May 2018 12:23:12 +0300
Post by Ivan Ivanov
Hi all,
tsort is reporting loop in my input file, but the loop doesn't exist
really.
I have checked this manually, examining the contents of the file,
related to the reported loop.
Further more, if I run the input file trhough unix2dos – it works, so
I suspect some strange problem with the unix newlines.
The input file is generated with python script on the Ubuntu 16.04.3
so all newlines should be the same.
---------------------------------------
Ubuntu 16.04.3 LTS
tsort (coreutils) 8.25
and
Debian GNU/Linux 9 (stretch)
tsort (coreutils) 8.26
---------------------------------------
$ unxz for-tsort-bug-example.txt.xz
$ tsort for-tsort-bug-example.txt > /dev/null
tsort: 15731101
tsort: 15731102
$ cat for-tsort-bug-example.txt | unix2dos | tsort > /dev/null
should exit properly.
You may choose to first convert the file and than call tsort and it
$ unix2dos for-tsort-bug-example.txt
$ tsort for-tsort-bug-example.txt > /dev/null
If you have further questions to investigate the issue, feel free to
write ba
Bernhard Voelker
2018-05-16 16:16:26 UTC
Permalink
Post by Ivan Ivanov
Hi all,
tsort is reporting loop in my input file, but the loop doesn't exist
really.
I have checked this manually, examining the contents of the file,
related to the reported loop.
Further more, if I run the input file trhough unix2dos – it works, so I
suspect some strange problem with the unix newlines.
The input file is generated with python script on the Ubuntu 16.04.3 so
all newlines should be the same.
---------------------------------------
Ubuntu 16.04.3 LTS
tsort (coreutils) 8.25
and
Debian GNU/Linux 9 (stretch)
tsort (coreutils) 8.26
---------------------------------------
$ unxz for-tsort-bug-example.txt.xz
$ tsort for-tsort-bug-example.txt > /dev/null
tsort: 15731101
tsort: 15731102
The problematic lines are:

$ grep -E '15731101|15731102' for-tsort-bug-example.txt
15731102 16019755
15731102 15731104
15731102 15731101
15731102 15731105
15731102 15731103
15731101
15731102

Therefore your example reduces to:

$ grep -E '15731101|15731102|16019755|15731104|15731105|15731103' for-tsort-bug-example.txt
15731102 16019755
15731102 15731104
15731102 15731101
15731102 15731105
15731102 15731103
15731101
15731102
Post by Ivan Ivanov
$ cat for-tsort-bug-example.txt | unix2dos | tsort > /dev/null
This replaces "\n" by "\r\n", and of course changes the way tsort works.
If your suspicion was that the file has Windows-style line-endings, then
you would have had to use 'dos2unix'.

Have a nice day,
Berny
Assaf Gordon
2018-10-30 03:25:29 UTC
Permalink
tags 31472 notabug
close 31472
stop

Hello,
Post by Bernhard Voelker
This replaces "\n" by "\r\n", and of course changes the way tsort
works. If your suspicion was that the file has Windows-style
line-endings, then you would have had to use 'dos2unix'.
Beyond the CRLF problem, I found that the result, returned by tsort on
the file with dos line endings had duplicates. So it is totally
incorrect.
The conclusion of the thread is that dos/windows/mac line endings
will affect "tsort" (as expected - since tsort treats them as normal
characters which change the sorted string).

As such, I'm closing this bug.
Discussion can continue by replying to this thread.

-assaf

Continue reading on narkive:
Loading...