1168345 - nsTArray::Sort shouldn't need Equals in the comparator

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Gian-Carlo Pascutto [:gcp]]

https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1790

The Equals function is being called here. This mostly looks like legacy cruft from NS_QuickSort() requiring 0 for equality. Even so it could/should be emulated via LessThan alone, which matches STL better. I think requiring an equals operator for a sort() is very unidiomatic C++.

The Equals being used actually violates the documented API: https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1793

The extra operator makes some other bugs more ugly such as Bug 1135022.

Comment 1

[Benjamin Smedberg]

Will this change the stable sort behavior? IIRC we spent some effort to make sort stable.

Comment 2

[Gian-Carlo Pascutto [:gcp]]

>Will this change the stable sort behavior? IIRC we spent some effort to make sort stable.

That's rather strange given that QuickSort isn't a stable sort, generally speaking. Are you sure?

See also bug 1082580.

In any case, Equals can be emulated by checking not(x < y) and not(y < x) so you really only need LessThan (cfr. STL and std::stable_sort)

Comment 3

[Jens Stutte [:jstutte]]

(In reply to Gian-Carlo Pascutto [:gcp] from comment #0)

https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1790

The Equals function is being called here.

I assume this translates today here.

This mostly looks like legacy
cruft from NS_QuickSort() requiring 0 for equality. Even so it could/should
be emulated via LessThan alone, which matches STL better. I think requiring
an equals operator for a sort() is very unidiomatic C++.

After bug 1839051 landed, Sort and StableSort indeed just rely on LessThan, however we have a comparator wrapper for legacy comparators that hopefully is inlined and mostly optimized away by the compiler.

The Equals being used actually violates the documented API:
https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1793

I am not sure what this relates to, there is this comment that might be related?

In any case it seems to me that in the meantime we did some improvements, always maintaining the possibility to use both legacy tri-state and STL like LessThan comparators.

(In reply to Gian-Carlo Pascutto [:gcp] from comment #2)

Will this change the stable sort behavior? IIRC we spent some effort to make sort stable.

That's rather strange given that QuickSort isn't a stable sort, generally
speaking. Are you sure?

Since bug 1147091 landed we have a std::stable_sort based nsTArray<>::StableSort. We used to have some "special" comparators that check the pointer values arithmetically when the items where otherwise equal. This was far from optimal in terms of execution times vs. std::stable_sort (as was quick sort as such compared to std::sort). And those comparators would crash with std::sort as it moves some elements temporarily to different locations, so definitely not recommended at all.

To summarize the current state:

• To use APIs like nsTArray::IndexOf with comparator, just Equals is needed like here.
• To use nsTArray::Sort or nsTArray::StableSort, a comparator can either be legacy tri-state or just have a LessThan. Equals is ignored but does not hurt.
• The default comparator however expects both Equals and LessThan to be defined on the value_type class. That makes it usable both for IndexOf-ish and Sort-ish usages.

Not sure if I missed some other API, but it looks more or less coherent to me these days?

Comment 4

[Gian-Carlo Pascutto [:gcp]]

I had to look back a bit. The code I was referring to 9 years ago is here: https://hg.mozilla.org/mozilla-central/file/a5f31bacc839708a0d0c8f9408b00f9b4767c601/xpcom/glue/nsTArray.h#l1790

Which required both LessThan and Equal, and doesn't match the comment on the next function that says "It uses the LessThan method defined on the given Comparator object to collate elements."

From your comments this has been resolved, as verified in the code too: https://searchfox.org/mozilla-central/rev/c09764753ea40725eb50decad2c51edecbd33308/xpcom/ds/nsTArray.h#2384