Austin Group Defect Tracker

Aardvark Mark IV


Viewing Issue Simple Details Jump to Notes ] Issue History ] Print ]
ID Category Severity Type Date Submitted Last Update
0001617 [Issue 8 drafts] Shell and Utilities Objection Clarification Requested 2022-11-11 01:20 2024-06-11 09:12
Reporter illiliti View Status public  
Assigned To
Priority normal Resolution Accepted As Marked  
Status Closed   Product Version Draft 2.1
Name Mark Lundblad
Organization
User Reference
Section tsort
Page Number 3237
Line Number 109959
Final Accepted Text See Note: 0006098
Summary 0001617: what tsort should do with cycles?
Description The current standard is unclear what should happen when tsort encounters a cycle. Existing practice shows that some implementations might only print a warning and some might even exit with a non-zero status code. Essentially, that renders tsort unusable for portable applications due to the lack of a way to explicitly tell tsort how cycles should be handled.

Here is more detailed analysis what implementations do with cycles:

- GNU, sbase print a warning and continue traversing the graph, then exit with a non-zero status code.
- NetBSD, FreeBSD, Illumos print a warning and continue traversing the graph, then exit with a zero status code.
- OpenBSD has -w option to record the number of cycles in exit status code(zero cycles = zero status code).
Desired Action Decide what to do. Either add an option to force specific behavior or clarify that tsort shall not be relied upon to detect cycles(but then what's the point of it nowadays?)
Tags issue8
Attached Files

- Relationships
related to 0001629Closed 1003.1(2016/18)/Issue7+TC2 Shell vs. read(2) errors on the script 

-  Notes
(0006051)
Don Cragun (manager)
2022-11-14 16:52
edited on: 2022-11-14 19:06

Add a new paragraph to the DESCRIPTION of tsort after D2.1 P3237, L109968:
If a cycle is found in the input, diagnostic messages shall be written to STDERR reporting that there is a cycle and indicating which nodes are in the cycle(s).


(0006052)
illiliti (reporter)
2022-11-14 17:15

Hmm, but what about exit status code? Should cycle cause an error or not? If not, how to detect cycle using tsort in a portable shell script? That's the most important things to clarify; sorry if I didn't make it clear initially.
(0006053)
Don Cragun (manager)
2022-11-14 19:01

Re Note: 0006052:
By definition, diagnostic messages report errors that must result in an unsuccessful exit status. All that we require is that a non-zero exit status be returned in this case; we do not require that the number of cycles be reported in the exit status. (Note that there is always the theoretical possibility that counting cycles could result in a zero exit status due to overflow. This description does not allow that behavior; if the count wraps to zero, tsort must detect this condition and return a non-zero value.)
(0006054)
illiliti (reporter)
2022-11-14 19:56

Thanks for the clarification. Still, I think proposed text should be adjusted to *explicitly* mention that cycle is an error and should result in non-zero status code. It's mainly needed to reduce confusion because some implementations don't exit with a non-zero exit status despite that they print diagnostic message to stderr.
(0006057)
Don Cragun (manager)
2022-11-17 16:48
edited on: 2023-01-05 07:38

Make the following changes:
Add a new paragraph to the DESCRIPTION of tsort after D2.1 P3237, L109968:
If a cycle is found in the input, diagnostic or warning messages shall be written to standard error reporting that there is a cycle and indicating which nodes are in the cycle(s). If a diagnostic message is written, the final exit status shall be non-zero.


Change the STDERR in tsort on P3238, L100001 from:
The standard error shall be used only for diagnostic messages.
to:
The standard error shall be used only for diagnostic and warning messages.


(0006059)
illiliti (reporter)
2022-11-17 20:31

As a portable shell script writer, how do I know whether particular tsort implementation prints a warning or diagnostic message? How to know that there's a cycle if it's still unclear what exit status tsort returns? Sorry, the proposed text does not fix the problem with cycles and exit status but only aggravates it.
(0006060)
kre (reporter)
2022-11-17 21:01

Re Note: 0006059

You don't know, just as you don't now. You can test, by creating
input with a cycle, running tsort, and seeing what happens.

What the standard is supposed to do is make it clear to applications
what they can expect, and what they cannot. As long as implementations
differ (by other than agreed bugs), there is no standard to state
beyond that applications cannot depend upon anything in particular
in this area.
(0006061)
illiliti (reporter)
2022-11-17 22:24

Here's how I think this should be fixed(by adding -w option from OpenBSD):

On page 3237 line 109962, change:

tsort [file]

to:

tsort [-w] [file]



On page 3237 line 109968, add a new paragraph:

If a cycle is found in the input, diagnostic messages shall be written to standard error reporting that there is a cycle and indicating which nodes are in the cycle(s). It is unspecified whether the final exit status shall be zero or non-zero value.



On page 3237 line 109970, change:

None

to:

The tsort utility shall conform to XBD Section 12.2 (on page 199).

The following option shall be supported:

-w

Exit with the number of cycles after traversing the graph. If there are more cycles than maximum representation of the exit status code can hold, the application shall exit with a non-zero status code instead. If there are no cycles, the application shall exit with zero status code.
(0006098)
geoffclare (manager)
2023-01-05 16:58

On page 3237 line 109962, change:
tsort [file]
to:
tsort [-w] [file]


Add a new paragraph to the DESCRIPTION of tsort after D2.1 P3237, L109968:
If a cycle is found in the input, diagnostic or warning messages shall be written to standard error reporting that there is a cycle and indicating which nodes are in the cycle(s). If the -w option is specified, these messages shall be diagnostic messages. If a diagnostic message is written, the final exit status shall be non-zero.

    
On page 3237 line 109970, change OPTIONS from:
None

to:
The tsort utility shall conform to [xref to XBD Section 12.2].

    The following option shall be supported:

    -w
Set the exit status to the number of cycles found in the input, or to an implementation defined maximum if there are more cycles than that maximum. If no cycles are found, the exit status shall be zero unless another error occurs.


Change the STDERR in tsort on P3238, L100001 from:
The standard error shall be used only for diagnostic messages.
to:
The standard error shall be used only for diagnostic and warning messages.


On page 3238 line 110009 change:
>0 An error occurred.
to:
>0 An error occurred. If the -w option is specified and one or more cycles were found in the input, the exit status shall be the number of cycles found, or an implementation defined maximum if more cycles than that maximum were found.


Change RATIONALE at page 3238 line 110033 from "None" to:
At the time that the -w option was added to this standard, the only known implementation reported a maximum of 255 cycles via the exit status. This has the drawback that applications cannot distinguish, from the exit status, errors caused by cycles from other errors or (when tsort() is executed from a shell) termination by a signal. Implementations are urged to set the implementation-defined maximum number of cycles reported via the exit status to at most 125, leaving 128 for other errors, and leaving 126, 127, and values greater than 128 to have the special meanings that the shell assigns to them. (An implemenation that wants to distinguish other types of errors would need to set the maximum to less than 125 so that 128 is not the only code available for those errors).


Change FUTURE DIRECTIONS at line 110035 from "None" to:
A future version of this standard may require that when the -w option is specified, the maximum number of cycles reported through the exit status of tsort is at most 125 and that exit status values 126, 127, and greater than 128 are not used by tsort.

- Issue History
Date Modified Username Field Change
2022-11-11 01:20 illiliti New Issue
2022-11-11 01:20 illiliti Name => Mark Lundblad
2022-11-11 01:20 illiliti Section => tsort
2022-11-11 01:20 illiliti Page Number => 3237
2022-11-11 01:20 illiliti Line Number => 109959
2022-11-14 16:52 Don Cragun Note Added: 0006051
2022-11-14 16:52 Don Cragun Status New => Resolved
2022-11-14 16:52 Don Cragun Resolution Open => Accepted As Marked
2022-11-14 16:53 Don Cragun Final Accepted Text => See Note: 0006051.
2022-11-14 16:53 Don Cragun Tag Attached: issue8
2022-11-14 17:15 illiliti Note Added: 0006052
2022-11-14 18:53 Don Cragun Note Edited: 0006051
2022-11-14 19:01 Don Cragun Note Added: 0006053
2022-11-14 19:06 Don Cragun Note Edited: 0006051
2022-11-14 19:56 illiliti Note Added: 0006054
2022-11-14 20:05 Don Cragun Status Resolved => Under Review
2022-11-14 20:05 Don Cragun Resolution Accepted As Marked => Reopened
2022-11-17 16:48 Don Cragun Note Added: 0006057
2022-11-17 16:48 Don Cragun Final Accepted Text See Note: 0006051. => See Note: 0006057.
2022-11-17 16:48 Don Cragun Status Under Review => Resolved
2022-11-17 16:48 Don Cragun Resolution Reopened => Accepted As Marked
2022-11-17 20:31 illiliti Note Added: 0006059
2022-11-17 21:01 kre Note Added: 0006060
2022-11-17 22:24 illiliti Note Added: 0006061
2023-01-05 07:38 Don Cragun Note Edited: 0006057
2023-01-05 16:58 geoffclare Note Added: 0006098
2023-01-05 16:58 geoffclare Final Accepted Text See Note: 0006057. => See Note: 0006098
2023-01-17 11:31 geoffclare Status Resolved => Applied
2023-03-20 16:28 eblake Relationship added related to 0001629
2024-06-11 09:12 agadmin Status Applied => Closed


Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker