[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Unexpected behaviour of tsort

Hi textutils developers, 

I am writing to you because we (Debian) got a release critical bug
against our textutils package. It seems that tsort does not behave as
most people would expect. 

Note: I am not the maintainer of that package but a member of the
Quality Assurance team. 

As the behaviour of tsort conforms to the documentation this is not
really a bug. Problem is that the other unices I tried this on report 
the error but nonetheless they try to generate senseful output on

This is from the manpage of tsort on SuSE Linux:

     If the graph contains a cycle (and therefore cannot be properly
     sorted), one of the arcs in the cycle is ignored and the sort
     continues.  Cycles are reported on standard error.

SuSE seems to use the BSD version of tsort. On Solaris there is no
reference to this problem in the manpage but output is generated anyway. 

As Debian tries to stay compatible with other Linux versions we are
thinking of replacing tsort with the BSD version but as we ship
GNU/Linux we would like a new GNU version which fixes this better.

So please consider changing the behaviour of tsort. If you lack the
manpower I could help with the patch but I am out of reach starting this
Friday for a week.

Here is the original bugreport:

> Date: Fri, 27 Aug 1999 12:53:44 +0200
> From: "J.H.M. Dassen (Ray)" <jdassen@wi.LeidenUniv.nl>
> To: submit@bugs.debian.org
> Subject: textutils: tsort behaves unexpectedly
> Package: textutils
> Version: 2.0-2
> Severity: important
> [Severity motiviation: this breaks behaviour expected by some source builds,
> e.g. of netkit-telnet-ssl.]
> Consider the following data:
>         auth.o auth.o
>         misc.o misc.o
>         ssl.o ssl.o
>         sslapp.o sslapp.o
>         ssl.o misc.o
>         ssl.o auth.o
>         auth.o misc.o
>         ssl.o auth.o
>         misc.o auth.o
>         auth.o ssl.o
>         sslapp.o ssl.o
>         auth.o misc.o
>         ssl.o sslapp.o
> Running tsort on this results in these errors on stderr
> [this is correct: a true topological sort does not exists when there are
> cycles]
>         tsort: -: input contains a loop:
>         tsort: auth.o
>         tsort: misc.o
> and no output no stdout.
> In 2.1, tsort was built from bsd sources rather than the GNU textutils. That
> version also gives warnings on stderr
>         tsort: cycle in data
>         tsort: ssl.o
>         tsort: sslapp.o
>         tsort: cycle in data
>         tsort: misc.o
>         tsort: auth.o
>         tsort: ssl.o
>         tsort: cycle in data
>         tsort: auth.o
>         tsort: misc.o
> but does produce output on stdout
> [namely a fewest-cycles sort of the input]
>         sslapp.o
>         ssl.o
>         misc.o
>         auth.o
> This behaviour is expected by a number of source builds, which contain an
> optimisation in library generation:
>         ar [some flags] `lorder *.o | tsort`
> Please make GNU's tsort behave like the BSD one, or coordinate with the
> bsdmainutils maintainer to switch back to the BSD version.
> -- System Information
> Debian Release: potato
> Kernel Version: Linux jcn206a 2.2.12-int2.2.11.2 #3 Fri Aug 27
> 10:02:05 CEST 19 99 i586 unknown
> Versions of the packages textutils depends on:
> ii  libc6     2.1.2-0pre11   GNU C Library: Shared libraries and timezone

Torsten Landschoff for the Debian QA Group

Attachment: pgpgaapQtmszw.pgp
Description: PGP signature

Reply to: