That all makes sense.

As I understand it, I just need to state the pre-condition. The implementers are given the freedom to decide what to do when the pre-condition isn't met, if anything. The programmer is responsible to make sure it doesn't happen.

My biggest concern has been safety, and you say the NSA has endorsed this.

That makes things smaller. I like that.
Thanks!


________________________________
From: Andrzej Krzemienski
Sent: Monday, May 12, 2025 6:55 PM
To: Phil Ratzloff
Cc: sg19_at_[hidden]
Subject: Re: [isocpp-sg19] Graph algorithms -- feedback on the specification of the algorithms


EXTERNAL

Having spent some time in the Library Evolution and Library groups, as well as in the Contracts study group, I can tell you that this is not how you specify things in the Standard Library.

First, It should be noted that unlike Boost.Graph, or your reference implementation, you are not specifying a single implementation of the library but a *range* of implementations. You have to give different implementers the freedom to implement it the way they want/need/must. You only define the boundaries of this freedom.

This is especially tricky for the preconditions. When you say "this function throws out_of_range when the passed index is too big" it means that:

1. Users are guaranteed that when they pass the too big index, the indicated exception is thrown: in every implementation of a std::graph library on every compiler in the world in every mode (debug, release, test). In fact users can deliberately pass excessive indices only to test if the index fits into the graph, and you are saying that this is a valid use case.

2. Library implementations in debug modes, or when running unit tests cannot freeze the program and launch a debugger on excessive indexes, or provide a core dump of an invalid program, because they have to guarantee to the users that an exception is thrown, because now, an exception upon excessive index is a normal control flow.

One usually doesn't want the above behavior, so what one says is "it is a precondition of this function that the index cannot be too big". This implies that:

1. The library has the freedom to report the buggy input in a way that is most suitable in the current build/deployment (debug, release, test in developer's machine)
2. The programmer is guaranteed nothing: they cannot rely on the behavior of the program: the implementation may choose to call std::abort(). This is still considered "secure" by NSA.

Only the latter is called a "precondition" in the Standard Library.
You could require that every implementation of std::graph in any mode always throws the same exception, but you cannot call it a "precondition" when specifying the Standard Library.

Regards,
&rzej;



pon., 12 maj 2025 o 23:53 Phil Ratzloff <Phil.Ratzloff_at_[hidden]<mailto:Phil.Ratzloff_at_[hidden]>> napisa³(a):
I wasn't aware of the compile-time requirements for Mandates, so that definitely needs to be moved into pre-conditions.

If the pre-conditions aren't valid then an exception must be thrown, so that developers can rely on the behavior.

There has been discussion of whether exceptions should be thrown or not, largely based on whether the library supports Freestanding or not. Because algorithms depend on the queue and stack containers that don't support Freestanding, and because memory allocation is often required that can throw bad_alloc, there's no reason to support Freestanding and exceptions are acceptable.

The reason to throw exceptions is an increased concern of safety in the industry. Most pre-conditions have a O(1) complexity, which is a one-time check when an algorithm is entered and is well work the cost. Considering Dijkstra's Shortest Paths, a check is made for negative weights which requires O(n). This is a question of safety and correctness. As a comparison, boost graph throws an exception on negative weights, so I feel we're in good company to add this check also.

When thinking about the Preconditions and Throws sections, they're directly related to each other and it feels like they're redundant in some cases. Is it reasonable to simply say that an exception is thrown when a precondition isn't met, and remove the matching entry in Throws?

I think adding these items to the algorithms paper makes sense.
Thanks for your input.


________________________________
From: SG19 on behalf of Andrzej Krzemienski via SG19
Sent: Friday, May 09, 2025 4:35 AM
To: sg19_at_[hidden]<mailto:sg19_at_[hidden]>
Cc: Andrzej Krzemienski
Subject: [isocpp-sg19] Graph algorithms -- feedback on the specification of the algorithms


EXTERNAL

Hi All,
I am new to this group, so I do not know how such feedback should be delivered. I didn't have time to report the issue in yesterday's call, so let me do it over email.

I think that it is a design question how the graph algorithms should respond to the "questionable" input values, such as non-existent vertex index, or not properly initialized function output parameters.

Take for instance `dijkstra_shortest_paths` specified in wg21.link/p3128. It specifies:

1 Mandates:
—(1.1) 0 <= source < num_vertices(graph) for the single-source version.
—(1.2) 0 <= source < num_vertices(graph), for each source in sources, for the multi-source version.
—(1.3) The weight function w must return a non-negative value.

2 Preconditions:
—(2.1) distances[i] = shortest_path_infinite_distance() for 0 <= i < num_vertices(g).
—(2.2) predecessors[i] = i for 0 <= i < num_vertices(g).

4 Throws:
—(4.1) An out_of_range exception is thrown in the following cases:
—(4.1.1) size(distances)< size(vertices(g))
—(4.1.2) size(predecessor)< size(vertices(g))
—(4.1.3) source is not in the range 0 <= source < num_vertices(graph).
—(4.1.4) The weight function returns a negative value. This check is not made if the weight value type is an unsigned integral type.

First of all, section "Mandates" only specifies compile-time checkable properties, and puts a hard requirement on the implementations to check the indicated conditions *at compile time*, for instance by using static_assert. The current conditions 1.1, 1.2, 1.3 are clearly not compile-time-checkable, so this is a bug in specification.

But more importantly, regarding the condition `0 <= source < num_vertices(graph)` you have to make the choice:
1. Are the implementations *required* to check the condition and throw an exception when it is not met, so that the programmers can rely on this exception, and can "safely" pass bad indexes and expect predictable behavior?
2. Or are the implementations free to assume that the users always pass the correct values of `source`? This means that they can check the condition, but do not have to. If they check, they can either throw an exception, or launch a debugger, or terminate the program with a core dump. If the programmer passes the bad value of `source` they are guaranteed nothing, and it can even be undefined behavior.

It is important that the paper documents this choice and the rationale for it. It is an important design decision. And then based on this decision, you either list the conditions under section "Preconditions" or you don't.
If you list this under section "Precondition" it means #2 above, and you can no longer say that an exception is thrown in this case.

The following links describe what Mandates and Precoonditions mean in detail:
* https://eel.is/c++draft/description#structure.specifications-3.2<https://protect.checkpoint.com/v2/r01/___https://eel.is/c++draft/description%23structure.specifications-3.2___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjYxZDZlOWY3YjRkNDQ0ODdlNWMxZTMwNzNlYzQ5Mjc6Nzo0MzFiOjdhYzEyZWUxZDg0OTQxNmZmMjkwNDI2MTZkYjAzZWU0MzAzYzdmMzFkMjBiYmM4NWI2YTA5NDBkOTBhYTY5MmI6aDpUOk4>
* https://eel.is/c++draft/description#structure.specifications-3.3<https://protect.checkpoint.com/v2/r01/___https://eel.is/c++draft/description%23structure.specifications-3.3___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjYxZDZlOWY3YjRkNDQ0ODdlNWMxZTMwNzNlYzQ5Mjc6NzphZGJmOjhhYWRlNmY3NDI1ODk5NDgwYjJhNzY5MTVmZmUxNmQwOGMwYThmZjRkNzk3ODdmNDM4YWEzMWI2NDQ3OGUyODY6aDpUOk4>

I recorded this issue in https://github.com/stdgraph/P1709/issues/113

Regards,
&rzej;