bug#31472: tsort reporting false loop in input. unix2dos fixes the problem.

[Assaf Gordon]

tags 31472 notabug
close 31472
stop

Hello,

On 2018-05-16 10:16 a.m., Bernhard Voelker wrote:

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'.


On 2018-05-17 2:54 a.m., Ivan Ivanov wrote:

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

bug#31472: tsort reporting false loop in input. unix2dos fixes the problem.

[Ivan Ivanov]

Hi again,

one last comment on this:

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.

Than I've tried the followling:

Instead of giving this as an input:
15731102 16019755
15731102 15731104
15731102 15731101
15731102 15731105
15731102 15731103
15731101
15731102

I gave tsort this one:
15731102 16019755
15731102 15731104
15731102 15731101
15731102 15731105
15731102 15731103
15731101 15731101
15731102 15731102

and it works like a charm.

So the problem is only with the format of the single nodes without
dependent ones.

Have a nice day!

Ivan Ivanov

bug#31472: tsort reporting false loop in input. unix2dos fixes the problem.

[Bernhard Voelker]

On 05/16/2018 11:23 AM, Ivan Ivanov wrote:
> 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

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

> $ 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

bug#31472: tsort reporting false loop in input. unix2dos fixes the problem.

[Ivan Ivanov]

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
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.
> 
> 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