usort函数无法正常工作？求排查PHP依赖排序测试失败的原因

我在使用usort处理依赖排序时遇到了问题，找不到代码里的错误，有没有人能帮忙分析下？

use DependencyResolver;
use PHPUnit\Framework\TestCase;

class DependencyResolverTest extends TestCase
{
    public function testComplex(){
        $resolver = new DependencyResolver();
        $graph = array(
            'A' => array('C'),
            'B' => array(),
            'C' => array()
        );
        $graph2 = array(
            'C' => array(),
            'B' => array(),
            'A' => array('C')
        );
        $output = $resolver->resolveDependencyGraph($graph);
        $output2 = $resolver->resolveDependencyGraph($graph2);
        unset($output[array_search('B', $output)]);
        unset($output2[array_search('B', $output2)]);
        $this->assertEquals($output, $output2);
    }
}

use Exception;

class DependencyResolver {

    protected $graph;
    protected $nestedKeys;

    public function resolveDependencyGraph(array $graph):array {
        $this->graph = $graph;
        $this->nestedKeys = array();
        $keys = array_keys($this->graph);
        $success = usort($keys, array($this, 'sortByDependency'));
        if (!$success)
            throw new Exception('Something went wrong.');
        unset($this->graph);
        unset($this->nestedKeys);
        return $keys;
    }

    protected function sortByDependency(string $left, string $right):int {
        if ($this->isDependentFrom($left, $right))
            $result = 1;
        elseif ($this->isDependentFrom($right, $left))
            $result = -1;
        else
            $result = 0;
        return $result;
    }

    protected function isDependentFrom(string $key, string $possibleDependency):bool {
        $isDependent = false;
        if (in_array($possibleDependency, $this->graph[$key]))
            $isDependent = true;
        else {
            $this->nestedKeys[] = $key;
            foreach ($this->graph[$key] as $dependencyOfKey){
                if (in_array($dependencyOfKey, $this->nestedKeys))
                    throw new Exception('Circular dependency.');
                if ($this->isDependentFrom($dependencyOfKey, $possibleDependency)){
                    $isDependent = true;
                    break;
                }
            }
            array_pop($this->nestedKeys);
        }
        return $isDependent;
    }

}

问题分析 #

你的usort失效主要有两个核心原因：

1. 实例属性$nestedKeys被跨调用污染
   usort在排序过程中会多次调用sortByDependency方法，而$nestedKeys是类的实例属性，每次比较都会修改它的状态。比如第一次比较A和B时往数组里加了A，第二次比较B和C时，这个数组里还残留着之前的元素，导致递归判断依赖时出现错误的循环检测或依赖判断。

2. 比较函数返回0导致排序不稳定
   当两个元素互相不依赖时（比如B和C），你的比较函数返回0，这会让usort认为这两个元素是等价的，排序顺序完全不确定。PHP的usort在处理等价元素时，不保证保留原数组的顺序，这就导致不同输入顺序的数组排序结果不一致，直接触发测试用例的断言失败。

修复方案 #

1. 把$nestedKeys改为递归方法的局部变量

避免跨比较调用的状态污染，修改isDependentFrom方法：

protected function isDependentFrom(string $key, string $possibleDependency, array $nestedKeys = []):bool {
    $isDependent = false;
    if (in_array($possibleDependency, $this->graph[$key])) {
        $isDependent = true;
    } else {
        // 每次递归创建独立的嵌套数组，不共享实例属性
        $currentNested = array_merge($nestedKeys, [$key]);
        foreach ($this->graph[$key] as $dependencyOfKey){
            if (in_array($dependencyOfKey, $currentNested)) {
                throw new Exception('Circular dependency.');
            }
            if ($this->isDependentFrom($dependencyOfKey, $possibleDependency, $currentNested)){
                $isDependent = true;
                break;
            }
        }
    }
    return $isDependent;
}

2. 给不相关元素添加固定排序规则

修改sortByDependency方法，用字符串比较替代返回0，保证排序结果稳定：

protected function sortByDependency(string $left, string $right):int {
    if ($this->isDependentFrom($left, $right)) {
        return 1;
    } elseif ($this->isDependentFrom($right, $left)) {
        return -1;
    } else {
        // 对无依赖关系的元素按字符串字典序排序，确保结果一致
        return strcmp($left, $right);
    }
}

3. 移除无用的实例属性

修改后$nestedKeys不再作为实例属性使用，可以从DependencyResolver类中移除：

class DependencyResolver {
    protected $graph;
    // 移除protected $nestedKeys;

    public function resolveDependencyGraph(array $graph):array {
        $this->graph = $graph;
        $keys = array_keys($this->graph);
        $success = usort($keys, array($this, 'sortByDependency'));
        if (!$success)
            throw new Exception('Something went wrong.');
        unset($this->graph);
        return $keys;
    }

    // ... 其他方法不变
}

这样修改后，不管输入的数组顺序如何，排序结果都会保持一致，测试用例就能通过，同时也解决了usort的不稳定问题。

内容的提问来源于stack exchange，提问作者inf3rno