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]> 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]
> *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;
>