Follow-up / Split-off from
🐛
uasort() does NOT preserve sort order, but core assumes so (Element::children, css sort, ...)
Needs work
Use cases
- (most common *) An array of arrays, where each item may have a weight in
$item[$weight_key].
- (less common) An array of arrays, where each item may have multiple weights in
$item[$weight_key_0], $item[$weight_key_1], etc.
- (less common) An array of objects, where each object may have a weight method e.g.
$weight = $item->getWeight().
- (less common) An array of items of whichever type, with a callback to determine a weight for each item. E.g.
$weight = $weight_callback($item);
(*) The most common example for the first case is render arrays with $item['#weight']. However, these should not be dealt with here, because there are special peculiarities we don't want to worry about. Esp the distinction of element children vs element properties.
#2522712-26: Simplify Element::children() stable sort. →
Existing implementations, previous attempts
Currently there are different sort implementations for different instances of these use cases, often with uasort() and a comparison function.
One problem with this is that uasort() is not stable.
The other problem is that comparison functions are slow. Really slow. Compared to other solutions.
Benchmark results can be found in
#2466097-91: uasort() does NOT preserve sort order, but core assumes so (Element::children, css sort, ...) →
ff.
Scope of this issue: Dedicated sort-by-weight
The goal of this issue is to provide dedicated reusable functions (static methods) for stable sorting based on item weights.
These should be simple, fast, and generic.
Example implementations can be found in https://github.com/donquixote/stable/tree/drupal-org-2466097-95-sort-keys
This issue is only about introducing the new functions + unit tests.
Actually using them should happen in another issue.
This way we keep the git history clean, and the issue readable, avoiding distractions.
This can happen in 8.1.x, because it will not BC-break anything.
DX questions
How do we want to distinguish asort() vs sort() ? (Preserve keys or not)
Distinct methods? Or an additional parameter?
How can the caller enable or disable (relatively expensive) checks such as is_array(), or possibly method_exists() etc? Currently in the proposed methods, the caller can use e.g. sortMixedByWeightKey() to force an is_array() check, or sortArraysByWeightKey() to omit such a check. But this brings a clutter of different methods.
Do we want to return a sorted array, or modify the first parameter by-reference, like the native PHP sort functions?
Do we want an options to make the sort non-stable? Just to get rid of comparison callbacks..
Do we want a fluid API?
This would make some of the API design questions above easier. But it would result in a bigger library than what we are ready to put in core.
Fluid API? Injectable sorts?
If we want a fluid API (which is not decided yet), there are two options:
// First option:
$items_sorted = StableSort::begin()
->byKey('weight', SORT_NUMERIC)
->sort($items_unsorted);
// Second option:
$items_sorted = StableSort::begin($items_unsorted)
->byKey('weight', SORT_NUMERIC)
->sort();
Only the first option leads us to reusable, injectable sorts. E.g.
$sort = StableSort::begin()
->byKey('weight', SORT_NUMERIC);
foreach ($items_all as $k => $items) {
$items_all[$k] = $sort->sort($items);
}
Why a new issue?
From #2466097-97:
This way, newcomers or people who want to understand the git history don't have to read 80 comments about an approach that was already discarded.