Sort bug / strangeness

[Steven Schveighoffer]

On 10/1/21 12:44 PM, Danny Arends wrote:
> Hey all,
> 
> Using a modified 3D A* tile searching algorithm, full code see:
> 
> https://github.com/DannyArends/CalderaD/blob/master/src/math/search.d
> 
> I get the following AssertError, 'sometimes' but not always on running 
> the code:
> 
> mutation.d(2816): Swap: rhs points to lhs.
> 
> the first time I hit Phobos is because I call the 
> std.algorithm.sorting.sort function to sort my open list (just an array 
> of search node objects);
> 
> ```
> search.openlist.sort!("a.f < b.f")();
> ```
> 
> sneakily f here is a @property function of the object, which just 
> computes and returns a float:
> 
> ```
> // sum of cumulative cost of this node + predecessors + heuristic
> struct Node {
>    float g; // cost of this node + it's predecessors
>    float h; // heuristic estimate of distance to goal
>    @nogc @property float f() nothrow const { return(this.g + this.h); }
> }
> ```

I think your struct is different than this, because this only happens if 
aliasing is inside the struct being sorted (i.e. it has pointers). Your 
presented struct doesn't have pointers, and the code you linked to is 
completely parameterized on the struct type.

If it does have pointers, you are not allowed to swap the values if 
either points to each other (or themselves).

-Steve