nuggreat
commented
2 years ago Mostly just forwarding what we discussed on the kOS discord as well as some other thoughts I have on the subject.
The root cause of the issue from what I could determine likley stems from the chosen compare function as said function was computing the distance along the SHIP:FACING vector for parts. As this is physics linked data should a physics tick fall between getting the data for the two passed in parts it is possible for the same part to have two difference distances. This is a problem for the sort function as written because it assumes that the things being sorted are not volatile and thus when comparing two parts there will be no difference. But should there be a difference and that difference is positive or negative depending that can cause the i and j values in the internal pt function to go out of range.
Once this was determined I was able to construct a reproducible test case with the error by injecting noise into the comparison function. From what I was then able to determine the proposed solution only works in some cases not all. Instead the solution I was able to come up with that worked in all cases reasonable cases I was able to create. The only thing I dislike about the solution is that it comes with an increase in sort time that seams to impact longer lists more. Thus as the issue was narrowed down to being caused by sorting a volatile list I am debating if it should be patched.
I'm not sure what conditions lead to the i and j indices walking off the ends, but they do sometimes, seemingly randomly but probably not really. I altered my local copy at line 102 in the sort fn from:
if lo<hi{local p is pt(A, lo, hi). qs(A, lo, p). qs(A, p + 1, hi).}}to:if (lo>0 AND hi<A:LENGTH-1) AND lo<hi{local p is pt(A, lo, hi). qs(A, lo, p). qs(A, p + 1, hi).}}and the issue went away for me. But there is probably a more robust solution