overflow panic in debug estimating cost

[tbillington]

Hey, while running in debug mode I got a panic in the astar implmentation due to overflow.

thread 'Async Compute Task Pool (0)' panicked at /Users/choc/.cargo/registry/src/index.crates.io-6f17d22bba15001f/pathfinding-4.10.0/src/directed/astar.rs:140:33:
attempt to add with overflow

https://github.com/evenfurther/pathfinding/blob/2aa2326ca2b096231c61d0139c7e236d772d755c/src/directed/astar.rs#L140

I probably have some pathological setup, but for correctness the estimated cost should probably saturate instead of wrapping. Thoughts on using new_cost.saturating_add(h) ?

[samueltardieu]

Saturating arithmetic could give incorrect results. The best way would probably be to use checked arithmetic instead in the few places where this might happen (such as adding costs), and document in a "# Panics" section in which case this method might panic.

[tbillington]

If the estimated cost is exceeding the bound of the numeric datatype neither wrapping nor saturating will be "correct", but as a user my preference would be saturating > wrapping > panic.

For a game I prioritise not crashing over total correctness, and accept that if the costs I've fed to astar are this high it's a problem on my end I should fix it. But it's still vastly more preferable that some routes be suboptimal or not resolvable over a straight panic. The majority of the time this code will be run is on end-user systems who cannot/will not be able to report or debug a panic like this.

If checked add is the chosen option, either returning None or changing to a Result type would still be preferable in my use case over a panic.

[samueltardieu]

Thanks Trent for discussing this further.

First of all, I'm not ready to have this crate silently report incorrect results ("suboptimal" is incorrect as far as A* is concerned), but we can try to devise solutions to the problem and the needs you are exposing (those are different).

Right now, I cannot use any other operator than + for cost computation as the C generic type expressing the cost would require adding num_traits::CheckedAdd or num_traits::SaturatingAdd, and that would be a breaking change. The only thing I can do immediately through a patch version is panic so that no incorrect result is returned, and would match the behavior seen in debug mode. I'll open an issue so that all pathfinding algorithms return a Result instead of an Option in a future release. That would let us express various reasons for failure, such as an overflow, and so on. Moreover, it would be extensible.

Concerning the point you raise: you can already get the behavior you want by using a thin wrapper around your cost type which defines addition as a saturating one. This would get you the result you expect, even in the case of panics on overflow since it will never overflow. Could that work for you?

[tbillington]

Oh, I'd forgotten C was a generic, so yes I could indeed do that :) thank you for the suggestion.

First of all, I'm not ready to have this crate silently report incorrect results

Understandable :)