GNU bug report logs - #31472
tsort reporting false loop in input. unix2dos fixes the problem.

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 31472 in the body.
You can then email your comments to 31472 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Ivan Ivanov <wankata <at> ivanovi.net>
To: bug-coreutils <at> gnu.org
Subject: tsort reporting false loop in input. unix2dos fixes the problem.
Date: Wed, 16 May 2018 12:23:12 +0300

[Message part 1 (text/plain, inline)]

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

[for-tsort-bug-example.txt.xz (application/x-xz, attachment)]

Message #8 received at 31472 <at> debbugs.gnu.org (full text, mbox):

From: Ivan Ivanov <wankata <at> ivanovi.net> (by way of Ivan Ivanov
 <wankata <at> ivanovi.net>)
To: bug-coreutils <at> gnu.org
Subject: Re: tsort reporting false loop in input. unix2dos fixes the problem.
Date: Wed, 16 May 2018 14:15:02 +0300

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 <wankata <at> ivanovi.net> написа:

> 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

Message #11 received at 31472 <at> debbugs.gnu.org (full text, mbox):

From: Bernhard Voelker <mail <at> bernhard-voelker.de>
To: Ivan Ivanov <wankata <at> ivanovi.net>, 31472 <at> debbugs.gnu.org
Subject: Re: bug#31472: tsort reporting false loop in input. unix2dos fixes
 the problem.
Date: Wed, 16 May 2018 18:16:26 +0200

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

Message #14 received at 31472 <at> debbugs.gnu.org (full text, mbox):

From: Ivan Ivanov <wankata <at> ivanovi.net>
To: 31472 <at> debbugs.gnu.org
Subject: Re: bug#31472: tsort reporting false loop in input. unix2dos fixes
Date: Thu, 17 May 2018 10:09:49 +0300

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

OK, I've worked on this. The input file is OK and the line breaks are
correct too. 

What I've have seen previously is, that tsort is adding LF in the
result file and is preserving the CRLF, so the file ends up with non
consistent line endings.

So we have two problems here:
1. tsort falsely reports loop 
2. When working on input with CRLF it creats a mess with the line
endings in the result file.

I am still curious why tsort doesn't report those loops when I change
the line endings to CRLF.

Hope this helps!

Ivan Ivanov

Message #17 received at 31472 <at> debbugs.gnu.org (full text, mbox):

From: Ivan Ivanov <wankata <at> ivanovi.net>
To: 31472 <at> debbugs.gnu.org
Subject: Re: bug#31472: tsort reporting false loop in input. unix2dos fixes
 the problem.
Date: Thu, 17 May 2018 11:54:05 +0300

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

Message #20 received at 31472 <at> debbugs.gnu.org (full text, mbox):

From: Assaf Gordon <assafgordon <at> gmail.com>
To: 31472 <at> debbugs.gnu.org
Subject: Re: bug#31472: tsort reporting false loop in input. unix2dos fixes
 the problem.
Date: Mon, 29 Oct 2018 21:25:29 -0600

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.