Sort bug / strangeness

Danny Arends Danny.Arends at
Fri Oct 1 16:44:08 UTC 2021

Hey all,

Using a modified 3D A* tile searching algorithm, full code see:

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); }

For the life of me I cannot fathom, how 2 function calls would 
end up pointing to the same memory location ?

To mention (might be relevant or not, I'm lost badly), the search 
struct around the map is parameterized. because I want to give 
objects the ability to have their own map walker definition (eg. 
ground, ground+air, ground+shallow water ). I am using the 
following wrapper struct:

struct Search(M, N) {
   N[] openlist; // Astar open list
   N[] closedlist; // Astar closed list

Anyone got some idea what I'm doing wrong, or explain me why I am 
messing up my Dijkstra here ?



Full stack trace/ dump below:

core.exception.AssertError at C:\D\dmd2\windows\bin\..\..\src\phobos\std\algorithm\mutation.d(2816): Swap: rhs points to lhs.
0x000000014008A2E3 in d_assert_msg
0x0000000140056F35 in 
std.algorithm.mutation.swap!(searchnode.Node).swap at 
0x0000000140057A07 in 
std.algorithm.mutation.swapAt!(searchnode.Node[]).swapAt at 
0x00000001400582BE in std.algorithm.sorting.medianOf!(binaryFun,, searchnode.Node[], ulong, ulong, ulong).medianOf at 
0x0000000140057DF4 in std.algorithm.sorting.getPivot!(binaryFun, 
searchnode.Node[]).getPivot at 
0x0000000140057112 in 
searchnode.Node[]).quickSortImpl at 
0x0000000140056FB5 in std.algorithm.sorting.sort!("a.f < b.f", 
SwapStrategy.unstable, searchnode.Node[]).sort at 
0x0000000140050C1F in search.step!(search.Search!(Map, Node), 
searchnode.Node).step at C:\Github\CalderaD\src\math\search.d(119)
0x000000014005012E in search.performSearch!(map.Map, 
searchnode.Node).performSearch at 
0x000000014004723B in map.testGenMap at 
0x000000014004CD9E in at 
0x000000014004CD3E in D main at C:\Github\CalderaD\src\main.d(25)

More information about the Digitalmars-d-learn mailing list