Element::children sort order undefined and slower than it could be - This makes tests fail in PHP7

Going to take a look at this one.

@Fabianx what is the expected output for:

<?php

use Drupal\Core\Render\Element;

$element = [
  'foo:1' => [ '#markup' => 'foo - first' ],
  'bar:2' => [ '#markup' => 'bar - second' ],
  'first:0' => [ '#markup' => 'little things', '#weight' => -1000 ],
];

$children = Element::children($element, TRUE);
?>

Should it return:

Array
(
    [0] => first:0
    [1] => foo:1
    [2] => bar:2
)

There are tests around Element::children at Drupal\Tests\Core\Render\ElementTest

This test only patch should demonstrate that there is a bug

Now we have some adequate test coverage I will try to fix this tomorrow.

I did some debugging and realised that the way that uasort is processing the value comparisons that it will always order things in reverse if they have the same weight. The reason why the following works is because although the sort flag is set when Element::children is called because no child has a weight value it does not get passed to the uasort function because the $sortable variable within the Element::children method only gets set to TRUE if one of the children has a value set for #weight:

<?php
$test = [
  'foo:1' => [ '#markup' => 'foo - first' ],
  'bar:2' => [ '#markup' => 'bar - second' ],
];
$children = Element::children($test, TRUE);
?>

By using array_reverse before uasort is called the expected order is preserved. I have check this works for the latest stable releases of PHP 5.3, 5.4, 5.5 and 5.6.

See https://github.com/nlisgo/uasort_does_not-2448765/pull/1 where I have isolated the example to easily test the solution against different versions of PHP.

Here is the corresponding travis build https://travis-ci.org/nlisgo/uasort_does_not-2448765/builds/54072958.

I'm running a bunch of tests on my github example that I haven't brought over yet. They are all passing with this fix. I am not saying that you're not right.

We should try and come up with a test case that the patch in #10 doesn't work for and then I would happily ditch it.

I will add the test case in #11.

@Fabianx you were right. This patch adds a test case like the one in #11 and the fix put forward fails.

Apologies, I didn't export the interdiff properly.

I propose that we add a method to the SortArray utility class that can be used in place of all calls to the uasort function.

The benefit of this is that we can solve the problem for all calls of the SortArray::uasort in one place.

This is what it would look like:

<?php

namespace Drupal\Component\Utility;

class SortArray {

  // ...

  public static function uasort(array &$a, callable $value_compare_func) {
    $a = array_reverse($a);
    return uasort($a, $value_compare_func);
  }

  // ...

}
?>

And to call it:

<?php

namespace Drupal\Core\Render;

use Drupal\Component\Utility\SortArray;

class Element {

  // ...

  public static function children(array &$elements, $sort = FALSE) {
    
    // ...
    if ($sort && $sortable) {
      SortArray::uasort($children, 'Drupal\Component\Utility\SortArray::sortByWeightProperty');

      // ...

    }

    // ...

  }

  // ...

}

?>

As you can see the patch in #16 causes no more failures than the patch in #14.

I will proceed with this approach (using SortArray::uasort) and await feedback. I want to be moving in a direction that we can roll a solution out for all calls to the uasort function.

Thanks for the pointers @Fabianx. I'm planning out an approach and hope to submit a patch tomorrow.

Please give your feedback on this solution.

Here is the interdiff. Done properly :)

I am addressing the feedback in #24.

Still investigating why the tests are failing.

It should be noted that all tests in Drupal\Tests\Core\Render\ElementTest are passing.

Is it possible that the failures are due to the fact that tests have been written around behaviour that is unexpected. I know this is true for at least one of the cases:

top of menu_test.links.task.yml

menu_test.local_task_test_tasks_view:
  route_name: menu_test.local_task_test_tasks_view
  title: View
  base_route: menu_test.local_task_test_tasks_view
menu_test.local_task_test_tasks_edit:
  route_name: menu_test.local_task_test_tasks_edit
  title: Edit
  base_route: menu_test.local_task_test_tasks_view
menu_test.local_task_test_tasks_settings:
  route_name: menu_test.local_task_test_tasks_settings
  title: Settings
  base_route: menu_test.local_task_test_tasks_view

Yet the current test is checking the order as follows in Drupal\system\Tests\Menu\LocalTasksTest::testPluginLocalTask

<?php
    // Verify that local tasks appear as defined in the router.
    $this->drupalGet(Url::fromRoute('menu_test.local_task_test_tasks_view'));
    $this->assertLocalTasks([
      ['menu_test.local_task_test_tasks_view', []],
      ['menu_test.local_task_test_tasks_settings', []],
      ['menu_test.local_task_test_tasks_edit', []],
    ]);
?>

If the test describes the expected behaviour then we need alter menu_test.links.task.yml

I think you are totally right, the test assumed the odd/bad behaviour of uasort. Feel free to change Drupal\system\Tests\Menu\LocalTasksTest::testPluginLocalTask, is its clearly not what actually is intended.

Addressing feedback in #28 and #29.

Reroll after rebase.

There are 2 test cases that are failing. When I run the tests locally and introduce debugging code around uasortOnArrays and compare the input array with the weights to the altered array after it is passed to the compare function we see that the altered array is in the order that we would expect which is why our next tests for ElementTest are passing.

The effect of the change to the Element class using SortArray::uasortOnArrays rather than uasort is a slight difference in the order of values in the array supplied to the sort function for values in the array that have the same #weight property.

In the case of the Drupal\comment\Tests\CommentPagerTest::testTwoPagers test the result is that the 2 pagers being tested are output in a different order. It is hard for me to know whether it is acceptable to just change the tests for Drupal\comment\Tests\CommentPagerTest::testTwoPagers to reflect the new order or whether it represents a bug that needs to be fixed. The nature of that test is to check that 2 pagers can work on the same page and that can be determined whichever order the pagers are output.

In the case of Drupal\search\Tests\SearchConfigSettingsFormTest::testDefaultSearchPageOrdering the test checks the url's of the first 2 primary tabs. The effect of introducing SortArray::uasortOnArrays is that the order of the primary tabs has gone from:

1. /search/node
2. /search/user
3. /search/dummy_path

to:

1. /search/node
2. /search/dummy_path
3. /search/user

I'm not sure that when this test was written whether the /search/dummy_path primary tab was available. If it had been then can we be sure that this test was not written to reflect the behaviour that was observed instead of the expected behaviour. We will need to investigate the implementation of the search feature to determine whether the primary tabs should really be expected to appear /search/node and then /search/user.

When we roll out the use of SortArray::uasortOnArrays no doubt we will find some other similar cases of tests failing where the tests may have been written to cover the observed behaviour instead of the expected behaviour.

I'm unassigning myself from the task for now to invite someone else to take this on who may see a clearer way forward but I am happy to continue looking into this just don't have much availability at the moment.

I can confirm that the search page primary tabs are being output in the expected order. The existing test Drupal\search\Tests\SearchConfigSettingsFormTest::testDefaultSearchPageOrdering just covers the observed behaviour. The dummy_search_type and user_search have the same weight but dummy_search_type appears before user_search in the source array.

The output below is a var_dump of the SearchLocalTask->getDerivativeDefinitions on the 8.0.x branch.

array (size=3)
  'node_search' => 
    array (size=4)
      'title' => string 'Content' (length=7)
      'route_name' => string 'search.view_node_search' (length=23)
      'base_route' => string 'search.plugins:node_search' (length=26)
      'weight' => int -10
  'dummy_search_type' => 
    array (size=4)
      'title' => string 'Dummy search type' (length=17)
      'route_name' => string 'search.view_dummy_search_type' (length=29)
      'base_route' => string 'search.plugins:node_search' (length=26)
      'weight' => int 0
  'user_search' => 
    array (size=4)
      'title' => string 'Users' (length=5)
      'route_name' => string 'search.view_user_search' (length=23)
      'base_route' => string 'search.plugins:node_search' (length=26)
      'weight' => int 0

OK, well I will change that test and move to investigating why the pagers are appearing in a different order than has been observed without our changes here.

Addressing failing test with Drupal\search\Tests\SearchConfigSettingsFormTest::testDefaultSearchPageOrdering as the test in place was just covering observed behaviour instead of expected. uasort was altering the order of the array in an unexpected way.

See #35 and #36.

There seems to be a bug with the current display of the comment field. Even on the 8.0.x branch if I add a new comment field to the Article content type (field_comment_2) and then go to manage display for the content type. If I give the comment field a weight of 20 and the field_comment_2 field a weight of 30 the comment field still appears last of all the fields on the node page.

I will do some search on the issue queue to see if any one has raised an issue for this, if not I will create one.

In an effort to move forward with this issue I have amended the test for Drupal\comment\Tests\CommentPagerTest::testTwoPagers to target the pager for each comment field by specifying a class selector. That way it doesn't matter what order the fields are output. Since the test is to check that 2 pagers can work on the same page rather than check that the order of the fields is as expected I thought this offered a way forward.

#2455211: Comment field displayed last regardless of assigned weight

While we are at it, we should pick an implementation that doesn't require a mind-boggling number of function calls to do the sorting:

• Instead of calling uasort() which requires something like O(n*log(n)) calls to the comparison function, we prepare a weight array and sort that directly with asort(). We have to scan the array anyway in the current implementation.
• If the weight is not defined, we initialize to ($i / $count), a weight that is between 0 and 1, in order of insertion. (This is the same trick the Form API is using, we can probably remove that other code.)

No interdiff, the test modifications are the same as #40, everything else is new.

Additionally, we should wonder if we shouldn't guarantee order of insertion at the same weight, even if the weight is defined.

The tests actually assume that we keep insertion order at equal weight, whatever the weight.

Damian thanks for your input on this issue.

Whatever approach we take, and you make a really good case for moving away from uasort, it would be great to abstract a sort function for ordering of Element::children as there are many other instances throughout the codebase of using uasort that could share the same solution.

The checkboxes / radios tests fail because they assume that non-integer weights are supported. They are not, and they haven't ever been, at least in the Form API, given this code in FormBuilder::doBuildForm():

      if (!isset($element[$key]['#weight'])) {
        $element[$key]['#weight'] = $count/1000;
      }

The checkboxes / radios ordering only works right now because *all* the weights of the children are set.

Any opinion on the following?

(1) Is everyone OK to explicitly stop support float weights?

(2) Should we trigger a warning on float weights in Element::children(), like we currently do for non-array elements?

(3) About checkboxes / radios: if you add a child element that is not in the #options array, where should it go? Above all the others? Below all the others?

My position on questions in #52.

On point 1, I have no objection. If we stop supporting floats it makes sense to do point 2. Point 3, I don't know enough about it, do we have and instances of that in core currently. Do we need to have an answer for point 3 to progress?

Added test method for invalid render element weights (not integer values).

Added integer value constraint for render element weight. If a weight is not integer value an exception with '"@key" has an invalid weight' message will be raised. I have used the patch from #47.

Attached interdiff.

Did some refactorization on some files that used float weights.

Re-rolled and fixed a few nitpicks and coding standards.

Unfortunately, most of those fixes are wrong, and show that test coverage is extremely spotty around weights outside the render system.

Alternatively, instead of removing support for float weights completely, we could remove support for float weights below a certain precision, for example 0.001. That would keep existing code like:

$element[$key]['#weight'] = $count/1000;

or

$weight += 0.001;

work untouched, but we still keep the performance gains of only sorting float values.

This is an experiment with #47 + supporting up to 0.001 weights.

The test that I had written to improve the targeting of the appropriate next link for the pager was not working as the class used to target it was not connected with the specific field but connected with its' position.

Related PHP7 test fails:

5) Drupal\Tests\Core\Config\Entity\ConfigEntityBaseUnitTest::testSort
Failed asserting that two variables reference the same object.

core/tests/Drupal/Tests/Core/Config/Entity/ConfigEntityBaseUnitTest.php:447
                                           
FAILURES!                                  
Tests: 3079, Assertions: 33482, Failures: 5.

1) Drupal\Tests\block\Unit\BlockRepositoryTest::testGetVisibleBlocksPerRegion with data set #0 (array(array(true, 'top', 0), array(false, 'bottom', 0), array(true, 'bottom', 5), array(true, 'bottom', -5)), array(array('block1'), array(), array('block4', 'block3')))
Failed asserting that Array &0 (
    'top' => Array &1 (
        0 => 'block1'
    )
    'center' => Array &2 ()
    'bottom' => Array &3 (
        0 => 'block4'
        1 => 'block3'
    )
) is identical to Array &0 (
    'top' => Array &1 (
        0 => 'block1'
    )
    'center' => Array &2 ()
    'bottom' => Array &3 (
        0 => 'block3'
        1 => 'block4'
    )
).

core/modules/block/tests/src/Unit/BlockRepositoryTest.php:112

2) Drupal\Tests\user\Unit\PermissionHandlerTest::testBuildPermissionsSortPerModule
Failed asserting that two arrays are equal.
--- Expected
+++ Actual
@@ @@
Array (
-    0 => 'access_module_a1'
-    1 => 'access_module_a2'
+    0 => 'access_module_a2'
+    1 => 'access_module_a1'
)

core/modules/user/tests/src/Unit/PermissionHandlerTest.php:199

+++ b/core/lib/Drupal/Core/Render/Element.php
@@ -93,21 +101,24 @@ public static function children(array &$elements, $sort = FALSE) {
-      uasort($children, 'Drupal\Component\Utility\SortArray::sortByWeightProperty');
+      asort($child_weights);

Its certainly no slow down +1

This patch also fixes 4 PHP7 test fails as mentioned by Berdir in the parent :)
#2454439: [META] Support PHP 7

Patch still applied with git apply -3. Conflicted on String/SafeMarkup context changes.

That Drupal\migrate_drupal\Tests\d6\MigrateFileTest test is known to have random fails. Re-testing.

Failed twice on that, strange. Green again, so RTBC again I guess.

Hopefully that's not a sign of things to come. ;)

Committed and pushed to 8.0.x. Thanks!

We don't need to play with floats for stable sort.
#2522712: Simplify Element::children() stable sort.

I've opened a separate 7.x backport issue for this at #2756297: element_children sort order inconsistent between PHP 5 and PHP 7 [Drupal 7 backport] per (updated in May) backport policy: https://www.drupal.org/core/backport-policy