Checkout totals sort order broken with 1.9.3 & PHP7

[bubach]

As described in these Stackoverflow posts, the sorting algorithm for the totals collector classes is broken - and it seems to only be a problem in combination with PHP7. The consequences of this is devastating for anything relating to a quote or order totals sum, especially when using third party modules for giftcard and or storecredit calculations on top of the core.

http://stackoverflow.com/questions/9194281/sort-algorithm-magento-checkout-totals-sorted-wrongly-causing-wrong-shipping-ta
http://magento.stackexchange.com/questions/92783/magento-grand-total-without-taxes-in-1-9-with-php7

There is a couple of suggested fixes in both threads, but what finally solved it for me was this patch to class "Mage_Core_Config_Base", http://stackoverflow.com/a/11954867/653721

--- 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

[durzel]

There is already a totals fix in this module, are you saying that 1.9.3.0 somehow undoes it?

[bubach]

I wouldn't call that a fix, it only solves the immediate symptom - not the underlying cause. This patch actually fixes the problem - and was the only solution that worked for my specific set of third-party modules that added sorting of their own.

The Stackoverflow posts linked will go into more detail about how this is happening, but it has to do with the sorting used and some highly technical details I'm not so familiar with...

@ http://stackoverflow.com/a/9258826/653721

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.

[icurdinj]

@bubach , @durzel - first of all, big thanks for all your work on fixing totals sort.

Following the information you provided, I added topological sort to 1.9.2.4 branch of this extension. (It will probably be needed in the master branch, too. I plan to add it there later.) The version I added is the very nice implementation that @IvanChepurnyi made for Magento 2 (https://github.com/magento/magento2/pull/49/files). It adds topological sorting right into _getSortedCollectorCodes() method.

Following that, I removed the XML order fix, as it shouldn't be needed any more.

My first tests seem to show everything works fine, but I would like to hear your experience with it, if you've got the time to try and test it on projects where you had problems.

[durzel]

Will do. I'm on 1.9.3.1 so I would be on the 2.x branch, so I would need to wait for the master branch to be updated in order to be able to give you some constructive feedback. 👍

[icurdinj]

@durzel , master branch updated.

[durzel]

Thanks @icurdinj, you're a star. Will update my dev site later, run some tests and give some feedback as soon as I can.

[icurdinj]

I believe that 2.0.1 release fixes this problem.

[stollr]

The patch is reverted in master branch by commit 6b2fa1c.

See #152