GDScriptDepSort broken.

[SaracenOne]

Operating system or device, Godot version, GPU Model and driver (if graphics related):

Issue description:
GDScriptDepSort operator does not work as expected. Does not correctly sort scripts by inheritance. Breakpoint often caught in the if (A == B) conditional, which the comment states should not be happening.

Steps to reproduce:
Call the reload_all_scripts() method on GDScriptLanguage singleton in a project with a variety of interlinking script dependencies. Since this is not currently used by any currently existing engine functionality, it must be called manually in C++.

Link to minimal example project:

[ghost]

I just had scan of the code and I think the issue here is that transitivity does not hold for GDScriptDepSort which I believe is necessary for sorting.

Consider 3 scripts (A, B, C) where A is a base of B. GDScriptDepSort(A,B) returns true, so A<B. GDScriptDepSort(A,C) and GDScriptDepSort(C,A) return false, so A == C. If transitivity holds C<B, but GDScriptDepSort(B,C) and GDScriptDepSort(C,B) return false so B == C too.

Presumably this means that when picking a pivot something is going wrong and a base script may get shuffled to the wrong side of the pivot? I can't immediately come up with a case for this though. A potential solution might be to instead count how many ancestors a script has (I->get_base()) and sort on this count, all base scripts should be sorted before the child scripts in the list.

[SaracenOne]

Hmm...sounds like you're one the right track. I've honestly not gone super deep into the nitty gritty details myself since the whole sorting system is quite tricky to get head around.

[Calinou]

@SaracenOne Can you still reproduce this in Godot 3.2.1 or the master branch?

[akien-mga]

No answer, so closing. Please comment if you can still reproduce the issue in Godot 3.3 or later.