php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #55062 comparison function is not anticommutative for arrays claimed to be comparable
Submitted: 2011-06-29 05:39 UTC Modified: 2020-11-05 12:17 UTC
Votes:1
Avg. Score:1.0 ± 0.0
Reproduced:1 of 1 (100.0%)
Same Version:1 (100.0%)
Same OS:1 (100.0%)
From: cataphract@php.net Assigned:
Status: Suspended Package: Scripting Engine problem
PHP Version: trunk-SVN-2011-06-29 (SVN) OS: Irrelevant
Private report: No CVE-ID: None
 [2011-06-29 05:39 UTC] cataphract@php.net
Description:
------------
This discussion is limited to the subsets of the array domain with elements that the manual claims are comparable between each other:
«Array with fewer members is smaller, if key from operand 1 is not found in operand 2 then arrays are uncomparable, otherwise - compare value by value»
http://docs.php.net/manual/en/language.operators.comparison.php
Whether the relations should be total (or partial) orders in the entire array domain is beyond the scope of this bug report.

The comparison function used to compare arrays with the operators, <, <=, >, >= is not anticommutative, i.e., swapping the arguments doesn't change the sign. It should be the case that

cmp(a, b) = - cmp(b, a)

The reason for this is that the relations <, <=, >, >=  should be antisymmetric, i.e., R(a, b) and R(b, a) cannot both be true unless maybe a == b (in which case the relation is reflexive, as is the case of <= and >=).

The relationship between the comparison function and the relations easily follows by how the relations are defined:
a < b  === cmp(a,b) == -1
a <= b === cmp(a,b) <= 0
a > b  === cmp(b,a) == -1
a >= b === cmp(b,a) <= 0

It is important that the relations are antisymmetric because it's a requirement for relation to be a total (or even partial!) order. Without that property, it's impossible to, for instance, reliably sort or do a binary search in an array of arrays.

The problem is the comparison function is sensitive to the order of the arguments. It starts by comparing the value of the first element of the first operand with the corresponding (i.e., with the same key) element in the second operand. One can see that, for any two arrays with the same length and keys, if reset($a) < $b[key($a)] && reset($b) < $x[key($a)], then $a < $b and $b < $a.

References:
http://en.wikipedia.org/wiki/Anticommutativity
http://en.wikipedia.org/wiki/Antisymmetric_relation
http://en.wikipedia.org/wiki/Reflexive_relation
http://en.wikipedia.org/wiki/Total_order
http://stackoverflow.com/questions/6480365/comparing-arrays-in-php-interesting-behaviour/6481181#6481181

Test script:
---------------
<?php
$b = array("a" => 1, "b" => 2);
$a = array("b" => 1, "a" => 2);
var_dump($a < $b);
var_dump($b < $a);
var_dump($b > $a);
var_dump($a > $b);


Expected result:
----------------
bool(true)   //or false
bool(false)  //or true
bool(true)   //or false
bool(false)  //or true

Actual result:
--------------
bool(true)
bool(true)
bool(true)
bool(true)


Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2020-11-05 12:17 UTC] cmb@php.net
-Status: Open +Status: Suspended -Type: Bug +Type: Feature/Change Request
 [2020-11-05 12:17 UTC] cmb@php.net
I agree that there is room for improvement, but given that this
behavior is there since at least PHP 4.3.0[1], and that it is well
documented[2], it is certainly not an implementation bug.  It
might be regarded as design issue, but changing the behavior would
constitute a BC break, and as such needs to be discussed on the
internals mailing list[3] (and likely requires an RFC).  If you,
or anybody else, is (still) interested in changing the behavior,
please forward the request to the mailing list.  For the time
being, I'm suspending this ticket.

[1] <https://3v4l.org/7PYiI>
[2] <http://docs.php.net/manual/en/language.operators.comparison.php#example-102>
[3] <https://www.php.net/mailing-lists.php#internals>
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Oct 31 23:01:28 2024 UTC