Sort algorithm: Magento checkout totals sorted wrongly causing wrong shipping tax calculation

Thanks for persisting @Alex, here is a better answer with a better explanation :) My first answer was wrong.

PHP implements the quicksort for all array sorting functions (reference zend_qsort.c).
If two records in the array are identical, their place will be swapped.

The problem is the giftwrap total record, which, according to _compareTotals(), is larger then subtotal and nominal but equal to all other totals.

Depending on the original order of the $confArray input array and on the placement of the pivot element it is legal to swap giftwrap with e.g. discount, because both are equal, even though discount is larger then shipping.

This might make the problem clearer from the sorting algorithms point of view:

• shipping < tax_shipping
• giftwrapping == shipping
• giftwrapping == tax_shipping

There are several possible solutions, even though the original problem is the choice of quicksort to build a directed acyclic dependency graph

• One (bad, shortterm) solution would be to add more dependencies to the giftwrapping total, even though there might still be more problems with other totals that simply didn't surface so far.
• The real solution would be to implement a topological sorting algorithm for the problem.

Interestingly there are not many PHP packages floating around. There is an orphaned PEAR package Structures_Graph. Using that would probably be the quick solution, but it would mean transforming the $confArray into a Structures_Graph structure (so maybe not that quick).

Wikipedia does a good job of explaining the problem, so rolling your own solution might be a fun challenge. The German Wikipedia topological sorting page breaks down the problem into logical steps and also has a great example algorithm in PERL.

So finally, here is my patch for this issue.

It implements topological sorting as suggested by Vinai.

1. Copy app/code/core/Mage/Sales/Model/Config/Ordered.php to app/code/local/Mage/Sales/Model/Config/Ordered.php
2. Save the contents of the patch to a file total-sorting.patch and call patch -p0 app/code/local/Mage/Sales/Model/Config/Ordered.php

In case of upgrades make sure to re-apply these steps.

The patch is tested to work with Magento 1.7.0.2

--- app/code/core/Mage/Sales/Model/Config/Ordered.php   2012-08-14 14:19:50.306504947 +0200+++ app/code/local/Mage/Sales/Model/Config/Ordered.php  2012-08-15 10:00:47.027003404 +0200@@ -121,6 +121,78 @@         return $totalConfig;     }+// [PATCHED CODE BEGIN]++    /**+     * Topological sort+     *+     * Copyright: http://www.calcatraz.com/blog/php-topological-sort-function-384+     * And fix see comment on http://stackoverflow.com/questions/11953021/topological-sorting-in-php+     *+     * @param $nodeids Node Ids+     * @param $edges Array of Edges. Each edge is specified as an array with two elements: The source and destination node of the edge+     * @return array|null+     */+    function topological_sort($nodeids, $edges) {+        $L = $S = $nodes = array();+        foreach($nodeids as $id) {+            $nodes[$id] = array('in'=>array(), 'out'=>array());+            foreach($edges as $e) {+                if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }+                if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }+            }+        }+        foreach ($nodes as $id=>$n) { if (empty($n['in'])) $S[]=$id; }+        while ($id = array_shift($S)) {+            if (!in_array($id, $L)) {+                $L[] = $id;+                foreach($nodes[$id]['out'] as $m) {+                    $nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));+                    if (empty($nodes[$m]['in'])) { $S[] = $m; }+                }+                $nodes[$id]['out'] = array();+            }+        }+        foreach($nodes as $n) {+            if (!empty($n['in']) or !empty($n['out'])) {+                return null; // not sortable as graph is cyclic+            }+        }+        return $L;+    }++    /**+     * Sort config array+     *+     * public to be easily accessable by test+     *+     * @param $configArray+     * @return array+     */+    public function _topSortConfigArray($configArray)+    {+        $nodes = array_keys($configArray);+        $edges = array();++        foreach ($configArray as $code => $data) {+            $_code = $data['_code'];+            if (!isset($configArray[$_code])) continue;+            foreach ($data['before'] as $beforeCode) {+                if (!isset($configArray[$beforeCode])) continue;+                $edges[] = array($_code, $beforeCode);+            }++            foreach ($data['after'] as $afterCode) {+                if (!isset($configArray[$afterCode])) continue;+                $edges[] = array($afterCode, $_code);+            }+        }+        return $this->topological_sort($nodes, $edges);+    }++// [PATCHED CODE END]++     /**      * Aggregate before/after information from all items and sort totals based on this data      *@@ -138,38 +210,16 @@         // invoke simple sorting if the first element contains the "sort_order" key         reset($configArray);         $element = current($configArray);+        // [PATCHED CODE BEGIN]         if (isset($element['sort_order'])) {             uasort($configArray, array($this, '_compareSortOrder'));+            $sortedCollectors = array_keys($configArray);+         } else {-            foreach ($configArray as $code => $data) {-                foreach ($data['before'] as $beforeCode) {-                    if (!isset($configArray[$beforeCode])) {-                        continue;-                    }-                    $configArray[$code]['before'] = array_unique(array_merge(-                        $configArray[$code]['before'], $configArray[$beforeCode]['before']-                    ));-                    $configArray[$beforeCode]['after'] = array_merge(-                        $configArray[$beforeCode]['after'], array($code), $data['after']-                    );-                    $configArray[$beforeCode]['after'] = array_unique($configArray[$beforeCode]['after']);-                }-                foreach ($data['after'] as $afterCode) {-                    if (!isset($configArray[$afterCode])) {-                        continue;-                    }-                    $configArray[$code]['after'] = array_unique(array_merge(-                        $configArray[$code]['after'], $configArray[$afterCode]['after']-                    ));-                    $configArray[$afterCode]['before'] = array_merge(-                        $configArray[$afterCode]['before'], array($code), $data['before']-                    );-                    $configArray[$afterCode]['before'] = array_unique($configArray[$afterCode]['before']);-                }-            }-            uasort($configArray, array($this, '_compareTotals'));+            $sortedCollectors = $this->_topSortConfigArray($configArray);         }-        $sortedCollectors = array_keys($configArray);+        // [PATCHED CODE END]+         if (Mage::app()->useCache('config')) {             Mage::app()->saveCache(serialize($sortedCollectors), $this->_collectorsCacheKey, array(                     Mage_Core_Model_Config::CACHE_TAG@@ -196,27 +246,6 @@     }     /**-     * Callback that uses after/before for comparison-     *-     * @param   array $a-     * @param   array $b-     * @return  int-     */-    protected function _compareTotals($a, $b)-    {-        $aCode = $a['_code'];-        $bCode = $b['_code'];-        if (in_array($aCode, $b['after']) || in_array($bCode, $a['before'])) {-            $res = -1;-        } elseif (in_array($bCode, $a['after']) || in_array($aCode, $b['before'])) {-            $res = 1;-        } else {-            $res = 0;-        }-        return $res;-    }--    /**      * Callback that uses sort_order for comparison      *      * @param array $a

EDIT: There is also another suggested change (for Magento 2): https://github.com/magento/magento2/pull/49

EDIT: This answer is wrong. See the discussion in the comments.

As Vinai noted, the problem is that the order function returns 0 even if the parameters are not equal. I modified the function to fall back on the string order of the keys as follows:

protected function _compareTotals($a, $b){    $aCode = $a['_code'];    $bCode = $b['_code'];    if (in_array($aCode, $b['after']) || in_array($bCode, $a['before'])) {        $res = -1;    } elseif (in_array($bCode, $a['after']) || in_array($aCode, $b['before'])) {        $res = 1;    } else {        $res = strcmp($aCode, $bCode); // was $res = 0 before    }    return $res;}