ConfigEntity based lists with items containing non-ascii characters are not sorted correctly

This could use a test case to start with.

I think there are a lot more lists not sorted correctly when translated. In core strnatcasecmp, usort, uasort, natcasesort is used a lot.

Sorts all ConfigEntityBundleBase based lists with transliteration

Sorts all ConfigEntityBundleBase based lists with transliteration:

• BlockContentType
• CommentType
• ContactForm
• MediaType
• NodeType
• ShortcutSet
• Vocabulary

Sorts all ConfigEntityBase based lists with transliteration

Sorts all ConfigEntityBase based lists with weight or transliterated label with test in ConfigEntityBaseUnitTest:
DateFormat, EntityFormDisplay, EntityViewDisplay, EntityFormMode, EntityViewMode, FieldConfig, Block, Editor, FilterFormat, ImageStyle, ConfigurableLanguage, ContentLanguageSettings, ResponsiveImageStyle, SearchPage, Action, Menu, Tour, Role, View, Workflow, BlockContentType, CommentType, ContactForm, MediaType, NodeType, ShortcutSet, Vocabulary

Verified and tested patch #24 on 10.1.x-dev. Patch applied successfully.

Test Steps:
1. Enable the following modules - Configuration Translation, Content Translation, Interface Translation, Language
2. Add a language (French in the example)
3. Add a two content types (Show and Zone)
4. Translate the Show content type to Émission
5. Switch languages (fr/admin/structure/types)
6. Verify content types are ordered alphabetically
7. Verify this for other bundle types - CommentType, ContactForm, MediaType, NodeType, ShortcutSet, Vocabulary, etc.

Test Results: Bundles with non-ascii character are ordered alphabetically.

Before Patch:

After Patch:

Tested on 10.1.x and following is my observation

1. The issue summary is clear and explains the overall problem
2. Testing steps have been provided and was able to reproduce the issue
3. Patch #24 applies cleanly and the non-ASCII config entity sort correctly
4. Tests have been included and passes for #24
5. Did code review and no issues were identified

Marking this as RTBC, not including additional screenshots. Already provided in #27

+++ b/core/lib/Drupal/Core/Config/Entity/ConfigEntityBase.php
@@ -226,14 +226,22 @@ public function createDuplicate() {
+      $language_id = \Drupal::service('language_manager')
...
+      $a_label = \Drupal::service('transliteration')->transliterate(
...
+      $b_label = \Drupal::service('transliteration')->transliterate(

A bit concerned about calling all these services inside the sort callback, because it feels like this is not going to be very performant in a case when there are hundreds of items or more to sort.

We could at least extract the transliteration service to a variable, and also skip transliterating the empty string if it is falsy? Is there a way of injecting at least the language ID, given that it never changes, or the transliteration service itself?

Also, do we have the same concerns about sorting in different languages as was raised in #3262017-90: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish)? Is transliterating the right thing to do in all cases?

@longwave : I remove transliteration and added the Collator like in #3262017: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish).

To prevent MethodArgumentValueNotImplemented exception in Collator, language_id en is used if intl extension is not installed.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

patch #34 doesn't apply to drupal core and throws this error:

error: while searching for:
   * {@inheritdoc}
   */
  protected function setUp(): void {
    $this->query = $this->createMock('Drupal\Core\Entity\Query\QueryInterface');

    $this->storage = $this->createMock('Drupal\Core\Config\Entity\ConfigEntityStorageInterface');

error: patch failed: core/modules/search/tests/src/Unit/SearchPageRepositoryTest.php:50
error: core/modules/search/tests/src/Unit/SearchPageRepositoryTest.php: patch does not apply

adding a new patch with reroll diff

The new polyfill and intl extension have the same considerations as #3262017: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish) so this will need to wait for the decision over there first.

Reroll

Postponing on #3262017: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish).

Also posted to the #needs-review-queue-initative slack channel so hopefully a framework manager can take a look at that one.

Unpostpone it. #3262017: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish) is postponed because nobody wants to break the API.

Converted to MR

Can the issue summary be updated to use the standard template please.

Hiding all patches for clarity as fix is in MR now.

Will need framework manager review for the package being added.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Took a look at the MR before pinging a framework manager and seems we are updating several packages that seem unrelated to this. Can those be reverted please.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Rerolled again

I can't make the call about the new package but the MR does fix the problem described in the issue summary. Moving to RTBC to put in front of the framework managers.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Rerolled again

It's fine to add a new Symfony polyfill, (more a release management decision than a framework one) but there should really be a dependency evaluation in the issue summary here per https://www.drupal.org/about/core/policies/core-dependency-policies/depe... - can be very short because we know the answers in this case.

Dependency evaluation added to issue summary

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Remarking as dependency eval has been added to summary.

I read the IS, comments and the MR. The only possible thing to consider is @longwave's point in #31 about calling services inside the sort callback "is not going to be very performant in a case when there are hundreds of items or more to sort". The transliteration service was removed from an earlier iteration of the MR but is still is getting the LanguageManager.

Leaving at RTBC.

#31 still to be addressed.
MR no longer applies in the meantime.

The service is moved to a new function
public static function sortEntities(array &$entities): bool
which calls a new compare function
public static function compare(ConfigEntityInterface $a, ConfigEntityInterface $b, \Collator $collator): int.

The sort functionpublic static function sort(ConfigEntityInterface $a, ConfigEntityInterface $b) is now deprecated in all child classes.

appears to have merge conflict but the tag no-needs-review-bot kept the bot from getting it.

Rerolled

Left a review on the MR
Would it be simpler (less re-rolls etc) to get the new dependency in first in a separate issue?

@larowlan all references to 11.1 are replaced by 11.2

Feedback appears to be addressed.

Do we need to deprecate sort()? Can we add the Collator as an optional argument to the existing method, and trigger a deprecation if it's not passed in?

Also there is a merge conflict, some out of scope changes in composer.json/lock.

@longwave you pointed in #31 about calling services inside the sort callback "is not going to be very performant in a case when there are hundreds of items or more to sort". The solution is to place the service outside the compare function sort().

Furthermore the function name sort() does not reflect its function. It is just comparing the two values, it is not sorting anything.

The merge conflict is resolved.

@longwave going to go on a limb and say this is good. The lock file seems to only show the new dependency I believe.

Rerolled

Rerolled

Unfortunately this needs another rebase, the MR looks good to me.

Rebased. What else needs to be done before the merge?

I don't think there's anything left to do here, RTBC queue has been very busy (hard to keep under 100 issues even with over 100 commits/month and many more reviews).

Committed/pushed to 11.x, thanks!

This blows up sites that don't have the intl extension

adam@8fa2a3a71304:data $ drush cr
PHP Fatal error:  Uncaught Error: Class "Collator" not found in /data/app/core/lib/Drupal/Core/Config/Entity/ConfigEntityBase.php:239

I think the intention of this code was to check the extension was loaded before initialising the $collator but I can't quite follow:

$collator = \Collator::create((!extension_loaded('intl')) ? ('en') : (\Drupal::service('language_manager')->getCurrentLanguage()->getId()));

::compare requires a Collator to be passed to it as well so we'll need to allow that the handle it being NULL?

I'm guessing this passed CI because that environment has the extension installed, but it's not listed as a requirement in core's composer.json...

I missed the symfony polyfill in the MR though which does look like it works

Just seen #3516545: Symfony\Polyfill\Intl\Icu\Collator::compare() is not implemented let's revert this and recommit with that fixed.

Reverted the commit and marked #3516545: Symfony\Polyfill\Intl\Icu\Collator::compare() is not implemented as duplicate. Let's fix that here and re-commit.

I think we should also open an upstream bug report against Symfony to implement the method, then we wouldn't need the checks added by that MR and could go back to the original code committed here.

Fixed the problem in MR11697 and tested it here in tugboat. Please review.

@acbramley : Test manually or automatically? Manually: "View live preview" via Tugboat next to the MR on the top of this issue page. In the tugboat PHP intl extension is not installed, at the moment. Same in Simplytest.me

Test manually or automatically

I meant in automated tests, i.e to catch the bug that caused this to be reverted

NW per the test. Also not sure why changing the API is necessary here.

Any idea how to test the fallback to symfony/polyfill-intl-icu ?

The PHP intl extension is compiled into PHP in the docker image. If the PHP intl extension should be optional, the base docker image has to be changed to install intl with pecl.

I compared the composer.json ext-* requirements and the extensions installed in the gitlab docker image. There are many PHP extensions installed that are not listed as required by core and its dependencies. Doesn't this lead to potential post-installation problems on systems that don't have the usual large number of PHP extensions installed (e.g simplytest.me)? If the PHP extensions are only suggested,, they should be disableable for testing.

symfony/polyfill-intl-icu:^1,34 now implements Collator::compare

sorry this one needs a rebase now.

Rebased, needs review

Believe this one is ready again. Would least be good to get into 12

The solution of adding Symfony's intl polyfill here feels really odd because we don't actually use it - we only use it to create a collator class that is then never used - because if the intl extension is not installed we fallback to strnatcasecmp. Why are we not comparing using Symfony's collator?

Another thing about the current solution is arguably you're going to get better sorting on english sites without intl installed.

$arr = ['Format 10x10', 'Format 20x20', 'Format 100x100'];
print "strnatcasecmp:\n";
usort($arr, 'strnatcasecmp');
var_dump($arr);

print "\n\nstrcasecmp:\n";
usort($arr, 'strcasecmp');
var_dump($arr);

print "\n\nCollator:\n";
$collator = new Collator('en');
// 2. Use usort with the collator's compare method
usort($arr, [$collator, 'compare']);
var_dump($arr);

The output;

strnatcasecmp:
array(3) {
  [0]=>
  string(12) "Format 10x10"
  [1]=>
  string(12) "Format 20x20"
  [2]=>
  string(14) "Format 100x100"
}


strcasecmp:
array(3) {
  [0]=>
  string(14) "Format 100x100"
  [1]=>
  string(12) "Format 10x10"
  [2]=>
  string(12) "Format 20x20"
}


Collator:
array(3) {
  [0]=>
  string(14) "Format 100x100"
  [1]=>
  string(12) "Format 10x10"
  [2]=>
  string(12) "Format 20x20"
}

Link to code: https://3v4l.org/ZbOPJ#v8.4.16

So there's a fix for this - we need to do $collator->setAttribute(Collator::NUMERIC_COLLATION, Collator::ON); See https://3v4l.org/rdO0q#v8.4.16

Obviously symfony's collator doesn't support this so I think that's yet another argument for not using it.

Here's what I think we should do.

1. Remove the symfony polyfill
2. If the intl extension is isntalled create a collator and set the Numeric Collation attribute.
3. Allow the usort callback to accept a collator or NULL - if null fallback to strnatcasecmp otherwise use the collator.

• Removed the symfony polyfill
• If the intl extension is installed, a collator is created and set the Numeric Collation attribute.
• Allow the usort callback to accept a collator or NULL - if null fallback to strnatcasecmp otherwise use the collator.
• A new deprecation test for Block::sort in BlockRenderOrderTest

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

• Removed meaningless comment
• Changed unit test with relevant label

Since I can't close threads I left check marks on them but from what I can tell feedback was addressed

My only comment was the location of the deprecation test but since it'll go away in 13 I'm going to assume none issue

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. The merge request has merge conflicts and cannot be merged. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

I've removed the dependency evaluation as it is no longer relevant but we also need to update the issue summary to reflect what is changing here. Can be set back to RTBC once that is done.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Saving @sleitner another rebase/conflict resolution in the baseline. Will chase some committers to see if we can get this in finally.

The Needs Review Queue Bot tested this issue. The merge request has merge conflicts and cannot be merged. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

@sleitner you rock for keeping up with all the rebases

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

One thing I keep pondering with this issue is does the string comparison stuff belong in the config system or somewhere more generic - like this is probably an issue when sorting other things using strnatcasecmp... for example:

• \Drupal\Component\Utility\SortArray::sortByKeyString
• \Drupal\Core\Plugin\CategorizingPluginManagerTrait::getSortedDefinitions
• \Drupal\Core\Plugin\DefaultLazyPluginCollection::sortHelper
• \Drupal\config\Form\ConfigSingleExportForm::buildForm
• \Drupal\config\Form\ConfigSingleImportForm::buildForm
• \Drupal\field_ui\Controller\EntityViewDisplayOverviewController::overview (interesting because it is based on config entities and will end up sorting them wrong :) )
• \Drupal\filter\FilterPluginCollection::sortHelper
• \Drupal\help\Plugin\HelpSection\HelpTopicSection::getPlugins
• \Drupal\workspaces\WorkspaceRepository::loadTree

All of these proably should be using a locale aware version of strnatcasecmp() where possible.

@alexpott I think a helper \Drupal\Component\Utility\SortArray would be a good idea to make it more generic.
For example like this:

public static function sortByString(string $a, string $b, ?\Collator $collator): int {
      if (isset($collator)) {
        return $collator->compare($a, $b);
      }
      return strnatcasecmp($a, $b);
}

I think there are more array sorts which use non-optimal compare helpers. But this is a follow-up.

@alexpott Should the other things using strnatcasecmp be handled in a follow-up?
I added SortArray::sortByString and SortArray::createSortCollator

@sleitner nice work! And yes fixing the other places is all follow-up material.

@alexpott \Drupal::service() is moved back to the entity and documentation is improved

The Needs Review Queue Bot tested this issue. The merge request has merge conflicts and cannot be merged. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

I've reviewed all the changes from @alexpott's review and they're looking good. I think this should be good to go now

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Just a few comment nits added to the MR - most with suggestions...

I've been reviewing this code for quite a while and @sleitner has done an amazing job of keeping up with all my reviews. Thanks for your patience and persistence.

While reviewing the code I've always had two nagging doubts at the back of my mind:

1. The disruption to existing config entity sorting is hard and real - if a custom or contrib module has a config entity with an override of ::sort and call to ::sort then there are situations where no deprecations is issued. And code that sorts multiple types of config entities will have unexpected results until the whole ecosystem has updated - it won't have a way to call sort or sortEntities depending on what type of config entities it is sorting...
2. It's not just config entities - all usage of strnatcasecmp() is problematic on a non-english site - how can we minimise disruption but provide a good fix for everywhere.

Soooo.... I'm proposing we go for a different solution. In this issue we add a new utility class that provides a container and language aware alternative to strnatcasecmp() and we convert config entities to use it. And then in a follow-up we introduce a PHPCS rule or PHPStan rule to detect strnatcasecmp() and tell people to use the drop in replacement. See the new MR https://git.drupalcode.org/project/drupal/-/merge_requests/16947

For example, I think the new MR will make solving #3262017: Country list is not correctly sorted when it's localized with accents (e.g. German, Turkish) quite easy - we either swap to the new method supplied here - or we add a natcasesort to the new utility class for even more win.

As the collators are stored in a static class we need to look at the memory usage. A collator takes up 64 bytes and it is highly unlikely the language will be swapping around a lot so I don't think this is an issue.

The new solution sounds good. Will there be performance issues if the languageManager is called every time a comparison is made in large lists? (#31)

I readded the new NaturalSort::strnatcasecmp() to Language and Block .

A new NaturalSort::natcasesort() could call the languageManager outside of the comparison only once.

@sleitner - thanks for fixing up Block - nice catch.

I'm not concerned about performance the current langcode is cached in both language managers provided by core.

Added NaturalSort::natcasesort() with tests

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

I removed NaturalSort::natcasesort for now

This looks great now. Definitely file a follow-up to add it back and test it and replace natcasesort usage everywhere.

I'm updating / deleting the CRs where appropriate.

I'm working through testing this, I'll share my notes in a bit, but for now I created the follow up mentioned in 163.

I added a note to the CR about the natural sort numbers.

Took a bit of effort to test, I was not seeing the expected results, I think there might be something going on separately there so I wouldn't read too much into it.
I did this on a fresh install and it worked both on the english only version and a fresh install that had both english and spanish enabled.

I created several content types one with Émission then when I added the spanish translation I translated it to an ñ.

I've attached 4 screenshots:

Main in English

Main in Spanish

This branch in English

This branch in Spanish

I really wish we could test this with and without the intl extension in CI, but I think it's fair to leave out here.
This is a great improvement even for just single language sites!

I read through the MR a couple of times and didn't see anything that hadn't already been addressed in the numerous revisions.

The Needs Review Queue Bot tested this issue. It no longer applies to Drupal core. Therefore, this issue status is now "Needs work".

This does not mean that the patch necessarily needs to be re-rolled or the MR rebased. Read the Issue Summary, the issue tags and the latest discussion here to determine what needs to be done.

Consult the Drupal Contributor Guide to find step-by-step guides for working with issues.

Committed and pushed 8cd44d484e3 to main. Thanks!

Given we're in beta freeze for both 11.5.0 and 12.0.0 - I've not backported this. This would be safe to backport as there is no API change here only addition so we might consider doing that once the freeze is over to allow contrib to adopt the fix earlier.

Let's consider backporting this while we are in beta for 11.5 and 12.0.