Fix the internal QDir sorting

If two items are equal according to the current sorting criterion,
the sorting predicate uses the address of the items to break the tie.
The problem is that the items themselves are being moved during
the sort; therefore, this will break the Strict Weak Ordering
that std::sort requires.

For instance, suppose to be sorting case-insensitively the following array:

   ("b", "a", "A")

Simulating a swapped-based sorting can lead to:

    Array before      Evaluated predicate      Array after
    ("b", "a", "A")   "a" < "A" (1)            ("b", "a", "A")
           ^    ^

    ("b", "a", "A")   "b" < "A" (2)            ("A", "a", "b")
      ^         ^

    ("A", "a", "b")   "A" < "a" (3)            (XXXXXXXXXXXXX)
      ^    ^

(1) True, because of the array ordering (they're equal otherwise)
(2) False: swap them
(3) True, because of the array ordering (they're equal otherwise)

(1) and (3) say that "a" < "A" and "A" < "a", SWO gets violated,
leading to undefined behavior.

This problem was causing QFileSystemModel autotests failures (cf. [1])
after switching to STL algorithms instead of using qSort.
The array to be ordered in that case is ("a", "c", "C"),
cf. tst_QFileSystemModel::caseSensitivity.

(STL algorithms are much smarter than good ol' quicksort in qSort;
if we're ordering on an array which fits in a cache line, they
turn to the much faster (~1 robe) insertion sort. Violating SWO with
a quick sort usually just gets to a non-sorted container; insertion
sort is implementable in ways that rely on SWO, otherwise they
will overflow the iterator; cf. Cormen/Leiserson/Rivest and the other
literature on the topic.)

This commit reverts commit fa5f3a44 (in Qt 4).

[1] http://testresults.qt-project.org/ci/QtBase_dev_Integration/build_01749/linux-g++_shadow-build_Ubuntu_11.10_x86/log.txt.gz

Change-Id: I5d8ac0d0907675c501717969abee2816b41eca18
Reviewed-by: Friedemann Kleint <Friedemann.Kleint@digia.com>
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>

0 files changed, 0 insertions, 0 deletions