php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #40616 uasort implementation is not robust
Submitted: 2007-02-23 23:13 UTC Modified: 2007-02-26 22:17 UTC
From: phpbugs at jessemccarthy dot net Assigned:
Status: Not a bug Package: Arrays related
PHP Version: 5.2.1 OS: Linux
Private report: No CVE-ID: None
 [2007-02-23 23:13 UTC] phpbugs at jessemccarthy dot net
Description:
------------
I spent hours investigating why my script using uasort() was not producing the expected results before finally discovering that the problem is due to a bug / limitation in the uasort() implementation.

I don't know what's actually happening in the source code, but my theory about the problem is that uasort() (or whatever underlying code) cuts corners or tries to use a shortcut based on members that compare as equal.

I *know* that "If two members compare as equal, their order in the sorted array is undefined."  *However*, once uasort() has found certain members to be equal, it seems to jump to conclusions based on that and doesn't go on to compare other members to each other that need to be.

Say for example you have an array with 3 members, call them A, B, and C, where the callback for uasort() would return
 0 for A compared to B
 0 for B compared to C
-1 for A compared to C

It seems that if uasort() compares A to B, and B to C and sees that they are "equal", it never compares A to C, which are not equal.

I consider it a bug, and a major flaw, but I don't know for sure that people familiar with the code don't intend for it to work that way.  Since uasort() / usort() are billed as the solution for sorting by non-trivial criteria, I really think that it should work more robustly and perform more thorough processing in those situations.  If there is some reason it can't be made to work that way, there should be a very noticeable warning in the documentation about how limited its functionality is.

I encountered this issue in the course of real world development, trying to tailor the order of output of form elements in Drupal based on its weighting system.  The uasort() callback in my reproduce code is the Drupal core code modified to sort members alphabetically if the assigned weight values are equal.  Printing the values of the arguments in the callback reveals that "A" and "C" (field_favorite_movies and field_favorite_music) are never compared.

Reproduce code:
---------------
Source:
http://www.jessemccarthy.net/public/uasort_bug/reproduce_source.php

In action (with PHP 4.4.4., but the same behavior occurs on another server with 5.2, where I originally encountered it):
http://www.jessemccarthy.net/public/uasort_bug/reproduce.php

Expected result:
----------------
I expect 'field_favorite_movies' to occur prior to 'field_favorite_music' in the sorted array.  I expect 'monkey_wrench' to appear anywhere.

Actual result:
--------------
'field_favorite_music' occurs prior to 'field_favorite_movies'.  If 'monkey_wrench' is excluded from the original array, the order is correct after sorting.

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2007-02-23 23:19 UTC] tony2001@php.net
Please provide a SHORT but complete reproduce code, so we won't have to debug it.
 [2007-02-23 23:20 UTC] tony2001@php.net
And don't forget actual and expected output.
 [2007-02-23 23:30 UTC] phpbugs at jessemccarthy dot net
Thanks for your quick response.  The reproduce code is too long?  The descriptions of actual and expected output are not sufficient?
 [2007-02-23 23:36 UTC] tony2001@php.net
>The reproduce code is too long?  
Yes, please remove everything not related to your problem.

>The descriptions of actual and expected output are not >sufficient?

Descriptions? No, descriptions are not enough, we need the results, not their descriptions.
 [2007-02-24 01:03 UTC] phpbugs at jessemccarthy dot net
Well I apologize.  Thanks for your feedback.

Short reproduce code:
http://www.jessemccarthy.net/public/uasort_bug/short_reproduce_source.php

Expected result:
array(3) {
  ["field_favorite_movies"]=>
  array(1) {
    ["title"]=>
    string(15) "Favorite movies"
  }
  ["monkey_wrench"]=>
  string(0) ""
  ["field_favorite_music"]=>
  array(1) {
    ["title"]=>
    string(14) "Favorite music"
  }
}


Actual result:
array(3) {
  ["field_favorite_music"]=>
  array(1) {
    ["title"]=>
    string(14) "Favorite music"
  }
  ["monkey_wrench"]=>
  string(0) ""
  ["field_favorite_movies"]=>
  array(1) {
    ["title"]=>
    string(15) "Favorite movies"
  }
}

I would think that an English description of expected / actual results would be helpful rather than just raw output, but whatever works for you.  I also can't help but feel that the original reproduce code made more sense, but this is the most minimal version I can create that still demonstrates anything.

Thanks for your attention.
 [2007-02-24 01:08 UTC] phpbugs at jessemccarthy dot net
This software broke the line with the URL to the short reproduce code.

http://www.jessemccarthy.net/public/uasort_bug/s_reproduce_source.php
 [2007-02-26 08:00 UTC] tony2001@php.net
Thank you for taking the time to write to us, but this is not
a bug. Please double-check the documentation available at
http://www.php.net/manual/ and the instructions on how to report
a bug at http://bugs.php.net/how-to-report.php

Your expectations are wrong.
 [2007-02-26 17:16 UTC] phpbugs at jessemccarthy dot net
> Please double-check the documentation...
> Your expectations are wrong.

Sorry, that's a little too vague to be meaningful.  I've read the documentation.  I just re-read it.  It's counterintuitive, and not documented, that uasort does not compare certain elements to each other because it has compared each of them to a different element and jumped to a conclusion based on that.

That's not quite what I expect from a function advertised as implementing my "non-trivial" sort criteria.

Even if your position is that the behavior of the function is fine, it's working as it's intended to, why would you not want to clearly explain to users what it does -- and can't -- do?  As far as I can tell, based on the documentation, it is a bug because there is nothing in the documentation that explains that behavior or prepares me for it.  If that's the intended behavior of the function, then the documentation is inadequate.
 [2007-02-26 19:03 UTC] dmytton@php.net
Feel free to submit your suggestions for rewording the documentation if you believe it could be clearer. Submitting a patch with any changes you might suggest would be even more helpful.
 [2007-02-26 22:13 UTC] phpbugs at jessemccarthy dot net
> Submitting a patch with any changes you
> might suggest would be even more helpful.

I appreciate that, but unfortunately for that idea, I'm not a C programmer.  If I was, I'd want to know the patch would have a chance of being considered before I invested the time.  Given tony2001's response, I'd be afraid it would just be trashcanned with no consideration.  I completely appreciate what you're saying, but as a practical matter it's unrealistic to expect people reporting PHP bugs to have the capability of fixing them themselves.  I hope you don't want to discourage people from reporting bugs because they can't personally fix them.


> Feel free to submit your suggestions for
> rewording the documentation if you believe
> it could be clearer.

Well, I think it would be vastly superior for uasort to perform more robustly and not have the behavior I described, but if it does behave that way, I think something like the following would be necessary to explain it.

I don't think it's a good idea to refer to the documentation for usort / uksort for an explanation of the callback function and code examples for uasort, but if that's how it's going to be then I guess I'd put the note in the usort documentation.  I'd put the code example in the uasort documentation.


Documentation changes:
********************

Note:  Two members (call them "A" and "C") that would each compare as equal to a third member (call it "B") will possibly never be compared to each other, even if your callback would compare them as unequal.

Example:
<?php

/*

Sort $favorites first by the 'weight' parameter of each element.  If the 'weight' parameter of two elements is equal and both have a 'title', sort alphabetically by 'title'.

*/

function sort_favorites( $array_element_1, $array_element_2 ) {

  $comparison_result = 0;

  // The array elements have equal 'weight' values

  if ( $array_element_1[ 'weight' ] == $array_element_2[ 'weight' ] ) {

    // Both elements have 'title' set

    if ( isset( $array_element_1[ 'title' ] ) && isset( $array_element_2[ 'title' ] ) ) {

      // Since 'weight' is equal, compare the elements alphabetically by 'title'
      $comparison_result = strnatcasecmp( $array_element_1[ 'title' ], $array_element_2[ 'title' ] );

    }
    // end if

  }
  // end if


  // The array elements have unequal 'weight' values

  else {

    // Compare the elements solely by 'weight'
    $comparison_result = ( ( $array_element_1 > $array_element_2 ) ? 1 : -1 );

  }
  // end else


  return $comparison_result;

}
// end sort_favorites


$favorites = array(

  'A' => array( 'weight' => 10, 'title' => "Favorite movies" ),

  'B' => array( 'weight' => 10 ),

  'C' => array( 'weight' => 10, 'title' => "Favorite music" )

);


uasort( $favorites, 'sort_favorites' );

/*

sort_favorites( $favorites[ 'A' ], $favorites[ 'B' ] ) would return 0

sort_favorites( $favorites[ 'B' ], $favorites[ 'C' ] ) would return 0

sort_favorites( $favorites[ 'A' ], $favorites[ 'C' ] ) will never be executed

$favorites will not be correctly sorted alphabetically by 'title'

*/

?>

********************


The difficulty of explaining the current behavior just goes to show how undesirable and counterintuitive it is.

I appreciate the constructive nature of your response, dmytton.
 [2007-02-26 22:17 UTC] phpbugs at jessemccarthy dot net
Sorry, I should have just posted a link to the code example:
http://www.jessemccarthy.net/public/uasort_bug/doc_code_src.php
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Apr 25 09:01:29 2024 UTC