Sort algorithm: Magento checkout totals sorted wro

问题:

In Magento there is a functionality where you can define the order of total calculation by specifing before and after which totals a total should be run.

I added a custom total and if I add the following lines to the config.xml, the sorting is wrong. Wrong means: tax_shipping comes before shipping. This causes the tax for the shipping cost to be added twice.

But this violates the condition

tax_shipping
after: shipping

My guess: There must be some contradiction in the full set of rules. But how can I find it?

This is the only rule I add. Without this rule, tax_shipping is sorted after shipping.

<shippingprotectiontax>
    <class>n98_shippingprotection/quote_address_total_shippingprotectionTax</class>
    <after>subtotal,discount,shipping,tax</after>
    <before>grand_total</before>
</shippingprotectiontax>

Below I paste the sorted array that is returned by the usort call in Mage_Sales_Model_Quote_Address_Total_Collector::_getSortedCollectorCodes() For those who do not have a Magento installation, the code is like this:

/**
 * uasort callback function
 *
 * @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;
}

protected function _getSortedCollectorCodes()
{

    ...

    uasort($configArray, array($this, '_compareTotals'));
    Mage::log('Sorted:');

    // this produces the output below
    $loginfo = "";
    foreach($configArray as $code=>$data) {
        $loginfo .= "$code\n";
        $loginfo .= "after: ".implode(',',$data['after'])."\n";
        $loginfo .= "before: ".implode(',',$data['before'])."\n";
        $loginfo .= "\n";
    }
    Mage::log($loginfo);

    ...

Log output:

nominal
after: 
before: subtotal,grand_total

subtotal
after: nominal
before: grand_total,shipping,freeshipping,tax_subtotal,discount,tax,weee,giftwrapping,cashondelivery,cashondelivery_tax,shippingprotection,shippingprotectiontax

freeshipping
after: subtotal,nominal
before: tax_subtotal,shipping,grand_total,tax,discount

tax_shipping
after: shipping,subtotal,freeshipping,tax_subtotal,nominal
before: tax,discount,grand_total,grand_total

giftwrapping
after: subtotal,nominal
before: 

tax_subtotal
after: freeshipping,subtotal,subtotal,nominal
before: tax,discount,shipping,grand_total,weee,customerbalance,giftcardaccount,reward

weee
after: subtotal,tax_subtotal,nominal,freeshipping,subtotal,subtotal,nominal
before: tax,discount,grand_total,grand_total,tax

shipping
after: subtotal,freeshipping,tax_subtotal,nominal
before: grand_total,discount,tax_shipping,tax,cashondelivery,cashondelivery_tax,shippingprotection,shippingprotectiontax

discount
after: subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee
before: grand_total,tax,customerbalance,giftcardaccount,reward,cashondelivery,cashondelivery_tax,shippingprotection,shippingprotectiontax

cashondelivery
after: subtotal,discount,shipping,nominal,subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee,subtotal,freeshipping,tax_subtotal,nominal
before: tax,grand_total,grand_total,customerbalance,giftcardaccount,tax_giftwrapping,reward,customerbalance,giftcardaccount,reward

shippingprotection
after: subtotal,discount,shipping,nominal,subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee,subtotal,freeshipping,tax_subtotal,nominal
before: tax,grand_total,grand_total,customerbalance,giftcardaccount,tax_giftwrapping,reward,cashondelivery_tax,customerbalance,giftcardaccount,reward

tax
after: subtotal,shipping,discount,tax_subtotal,freeshipping,tax_shipping,nominal,weee,cashondelivery,shippingprotection
before: grand_total,customerbalance,giftcardaccount,tax_giftwrapping,reward,cashondelivery_tax,shippingprotectiontax

shippingprotectiontax
after: subtotal,discount,shipping,tax,nominal,subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee,subtotal,freeshipping,tax_subtotal,nominal,subtotal,shipping,discount,tax_subtotal,freeshipping,tax_shipping,nominal,weee,cashondelivery,shippingprotection
before: grand_total,customerbalance,giftcardaccount,reward

cashondelivery_tax
after: subtotal,discount,shipping,tax,nominal,subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee,subtotal,freeshipping,tax_subtotal,nominal,subtotal,shipping,discount,tax_subtotal,freeshipping,tax_shipping,nominal,weee,cashondelivery
before: grand_total,customerbalance,giftcardaccount,reward

tax_giftwrapping
after: tax,subtotal,shipping,discount,tax_subtotal,freeshipping,tax_shipping,nominal,weee
before: grand_total,customerbalance,giftcardaccount

grand_total
after: subtotal,nominal,shipping,freeshipping,tax_subtotal,discount,tax,tax_giftwrapping,cashondelivery,cashondelivery_tax,shippingprotection,shippingprotectiontax
before: customerbalance,giftcardaccount,reward

reward
after: wee,discount,tax,tax_subtotal,grand_total,subtotal,shipping,nominal,freeshipping,tax_subtotal,tax_shipping,weee,subtotal,shipping,discount,tax_subtotal,freeshipping,tax_shipping,nominal,weee,freeshipping,subtotal,subtotal,nominal,subtotal,nominal,shipping,freeshipping,tax_subtotal,discount,tax,tax_giftwrapping
before: giftcardaccount,customerbalance,customerbalance

giftcardaccount
after: wee,discount,tax,tax_subtotal,grand_total,reward,subtotal,shipping,nominal,freeshipping,tax_shipping,weee
before: customerbalance

customerbalance
after: wee,discount,tax,tax_subtotal,grand_total,reward,giftcardaccount,subtotal,shipping,nominal,freeshipping,tax_shipping,weee
before: 

EDIT:

After Vinai's answer I added more debug code

$fp = fopen('/tmp/dotfile','w');
fwrite($fp,"digraph TotalOrder\n");
fwrite($fp,"{\n");
foreach($configArray as $code=>$data) {
    $_code = $data['_code'];
    foreach($data['before'] as $beforeCode) {
        fwrite($fp,"$beforeCode -> $_code;\n");
    }
    foreach($data['after'] as $afterCode) {
        fwrite($fp,"$_code -> $afterCode;\n");
    }
}
fwrite($fp,"}\n");
fclose($fp);

And visualized it with graphviz: dot -Tpng dotfile > viz.png. That's the result of the first try. Called after the sorting.

EDIT2:

I think this is pretty useless.

So I made a visualization of the array before merging the after/before entries. (right after $configArray = $this->_modelsConfig;)

This is it without my shippingprotectiontax entry:

This is it with my shippingprotectiontax entry:

I do not see any clear contradictions.

EDIT3:

Config array just before uasort:

array (
  'nominal' => 
  array (
    'class' => 'sales/quote_address_total_nominal',
    'before' => 
    array (
      0 => 'subtotal',
      1 => 'grand_total',
    ),
    'renderer' => 'checkout/total_nominal',
    'after' => 
    array (
    ),
    '_code' => 'nominal',
  ),
  'subtotal' => 
  array (
    'class' => 'sales/quote_address_total_subtotal',
    'after' => 
    array (
      0 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'shipping',
      2 => 'freeshipping',
      3 => 'tax_subtotal',
      4 => 'discount',
      5 => 'tax',
      6 => 'weee',
      7 => 'giftwrapping',
      8 => 'cashondelivery',
      9 => 'cashondelivery_tax',
      10 => 'shippingprotection',
      11 => 'shippingprotectiontax',
    ),
    'renderer' => 'tax/checkout_subtotal',
    'admin_renderer' => 'adminhtml/sales_order_create_totals_subtotal',
    '_code' => 'subtotal',
  ),
  'shipping' => 
  array (
    'class' => 'sales/quote_address_total_shipping',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'freeshipping',
      2 => 'tax_subtotal',
      3 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'discount',
      2 => 'tax_shipping',
      3 => 'tax',
      4 => 'cashondelivery',
      5 => 'cashondelivery_tax',
      6 => 'shippingprotection',
      7 => 'shippingprotectiontax',
    ),
    'renderer' => 'tax/checkout_shipping',
    'admin_renderer' => 'adminhtml/sales_order_create_totals_shipping',
    '_code' => 'shipping',
  ),
  'grand_total' => 
  array (
    'class' => 'sales/quote_address_total_grand',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'nominal',
      2 => 'shipping',
      3 => 'freeshipping',
      4 => 'tax_subtotal',
      5 => 'discount',
      6 => 'tax',
      7 => 'tax_giftwrapping',
      8 => 'cashondelivery',
      9 => 'cashondelivery_tax',
      10 => 'shippingprotection',
      11 => 'shippingprotectiontax',
    ),
    'renderer' => 'tax/checkout_grandtotal',
    'admin_renderer' => 'adminhtml/sales_order_create_totals_grandtotal',
    'before' => 
    array (
      0 => 'customerbalance',
      1 => 'giftcardaccount',
      2 => 'reward',
    ),
    '_code' => 'grand_total',
  ),
  'freeshipping' => 
  array (
    'class' => 'salesrule/quote_freeshipping',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax_subtotal',
      1 => 'shipping',
      2 => 'grand_total',
      3 => 'tax',
      4 => 'discount',
    ),
    '_code' => 'freeshipping',
  ),
  'discount' => 
  array (
    'class' => 'salesrule/quote_discount',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'shipping',
      2 => 'nominal',
      3 => 'freeshipping',
      4 => 'tax_subtotal',
      5 => 'tax_shipping',
      6 => 'weee',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'tax',
      2 => 'customerbalance',
      3 => 'giftcardaccount',
      4 => 'reward',
      5 => 'cashondelivery',
      6 => 'cashondelivery_tax',
      7 => 'shippingprotection',
      8 => 'shippingprotectiontax',
    ),
    'renderer' => 'tax/checkout_discount',
    'admin_renderer' => 'adminhtml/sales_order_create_totals_discount',
    '_code' => 'discount',
  ),
  'tax_subtotal' => 
  array (
    'class' => 'tax/sales_total_quote_subtotal',
    'after' => 
    array (
      0 => 'freeshipping',
      1 => 'subtotal',
      2 => 'subtotal',
      3 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax',
      1 => 'discount',
      2 => 'shipping',
      3 => 'grand_total',
      4 => 'weee',
      5 => 'customerbalance',
      6 => 'giftcardaccount',
      7 => 'reward',
    ),
    '_code' => 'tax_subtotal',
  ),
  'tax_shipping' => 
  array (
    'class' => 'tax/sales_total_quote_shipping',
    'after' => 
    array (
      0 => 'shipping',
      1 => 'subtotal',
      2 => 'freeshipping',
      3 => 'tax_subtotal',
      4 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax',
      1 => 'discount',
      2 => 'grand_total',
      3 => 'grand_total',
    ),
    '_code' => 'tax_shipping',
  ),
  'tax' => 
  array (
    'class' => 'tax/sales_total_quote_tax',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'shipping',
      2 => 'discount',
      3 => 'tax_subtotal',
      4 => 'freeshipping',
      5 => 'tax_shipping',
      6 => 'nominal',
      7 => 'weee',
      8 => 'cashondelivery',
      9 => 'shippingprotection',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'customerbalance',
      2 => 'giftcardaccount',
      3 => 'tax_giftwrapping',
      4 => 'reward',
      5 => 'cashondelivery_tax',
      6 => 'shippingprotectiontax',
    ),
    'renderer' => 'tax/checkout_tax',
    'admin_renderer' => 'adminhtml/sales_order_create_totals_tax',
    '_code' => 'tax',
  ),
  'weee' => 
  array (
    'class' => 'weee/total_quote_weee',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'tax_subtotal',
      2 => 'nominal',
      3 => 'freeshipping',
      4 => 'subtotal',
      5 => 'subtotal',
      6 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax',
      1 => 'discount',
      2 => 'grand_total',
      3 => 'grand_total',
      4 => 'tax',
    ),
    '_code' => 'weee',
  ),
  'customerbalance' => 
  array (
    'class' => 'enterprise_customerbalance/total_quote_customerbalance',
    'after' => 
    array (
      0 => 'wee',
      1 => 'discount',
      2 => 'tax',
      3 => 'tax_subtotal',
      4 => 'grand_total',
      5 => 'reward',
      6 => 'giftcardaccount',
      7 => 'subtotal',
      8 => 'shipping',
      9 => 'nominal',
      10 => 'freeshipping',
      11 => 'tax_shipping',
      12 => 'weee',
    ),
    'renderer' => 'enterprise_customerbalance/checkout_total',
    'before' => 
    array (
    ),
    '_code' => 'customerbalance',
  ),
  'giftcardaccount' => 
  array (
    'class' => 'enterprise_giftcardaccount/total_quote_giftcardaccount',
    'after' => 
    array (
      0 => 'wee',
      1 => 'discount',
      2 => 'tax',
      3 => 'tax_subtotal',
      4 => 'grand_total',
      5 => 'reward',
      6 => 'subtotal',
      7 => 'shipping',
      8 => 'nominal',
      9 => 'freeshipping',
      11 => 'tax_shipping',
      12 => 'weee',
    ),
    'before' => 
    array (
      0 => 'customerbalance',
    ),
    'renderer' => 'enterprise_giftcardaccount/checkout_cart_total',
    '_code' => 'giftcardaccount',
  ),
  'giftwrapping' => 
  array (
    'class' => 'enterprise_giftwrapping/total_quote_giftwrapping',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'nominal',
    ),
    'renderer' => 'enterprise_giftwrapping/checkout_totals',
    'before' => 
    array (
    ),
    '_code' => 'giftwrapping',
  ),
  'tax_giftwrapping' => 
  array (
    'class' => 'enterprise_giftwrapping/total_quote_tax_giftwrapping',
    'after' => 
    array (
      0 => 'tax',
      1 => 'subtotal',
      2 => 'shipping',
      3 => 'discount',
      4 => 'tax_subtotal',
      5 => 'freeshipping',
      6 => 'tax_shipping',
      7 => 'nominal',
      8 => 'weee',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'customerbalance',
      2 => 'giftcardaccount',
    ),
    '_code' => 'tax_giftwrapping',
  ),
  'reward' => 
  array (
    'class' => 'enterprise_reward/total_quote_reward',
    'after' => 
    array (
      0 => 'wee',
      1 => 'discount',
      2 => 'tax',
      3 => 'tax_subtotal',
      4 => 'grand_total',
      5 => 'subtotal',
      6 => 'shipping',
      7 => 'nominal',
      8 => 'freeshipping',
      9 => 'tax_subtotal',
      10 => 'tax_shipping',
      11 => 'weee',
      12 => 'subtotal',
      13 => 'shipping',
      14 => 'discount',
      15 => 'tax_subtotal',
      16 => 'freeshipping',
      17 => 'tax_shipping',
      18 => 'nominal',
      19 => 'weee',
      20 => 'freeshipping',
      21 => 'subtotal',
      22 => 'subtotal',
      23 => 'nominal',
      24 => 'subtotal',
      25 => 'nominal',
      26 => 'shipping',
      27 => 'freeshipping',
      28 => 'tax_subtotal',
      29 => 'discount',
      30 => 'tax',
      31 => 'tax_giftwrapping',
    ),
    'before' => 
    array (
      0 => 'giftcardaccount',
      1 => 'customerbalance',
      2 => 'customerbalance',
    ),
    'renderer' => 'enterprise_reward/checkout_total',
    '_code' => 'reward',
  ),
  'cashondelivery' => 
  array (
    'class' => 'cashondelivery/quote_total',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'discount',
      2 => 'shipping',
      3 => 'nominal',
      4 => 'subtotal',
      5 => 'shipping',
      6 => 'nominal',
      7 => 'freeshipping',
      8 => 'tax_subtotal',
      9 => 'tax_shipping',
      10 => 'weee',
      11 => 'subtotal',
      12 => 'freeshipping',
      13 => 'tax_subtotal',
      14 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax',
      1 => 'grand_total',
      2 => 'grand_total',
      3 => 'customerbalance',
      4 => 'giftcardaccount',
      5 => 'tax_giftwrapping',
      6 => 'reward',
      7 => 'customerbalance',
      8 => 'giftcardaccount',
      9 => 'reward',
    ),
    'renderer' => 'cashondelivery/checkout_cod',
    'admin_renderer' => 'cashondelivery/adminhtml_sales_order_create_totals_cod',
    '_code' => 'cashondelivery',
  ),
  'cashondelivery_tax' => 
  array (
    'class' => 'cashondelivery/quote_taxTotal',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'discount',
      2 => 'shipping',
      3 => 'tax',
      4 => 'nominal',
      5 => 'subtotal',
      6 => 'shipping',
      7 => 'nominal',
      8 => 'freeshipping',
      9 => 'tax_subtotal',
      10 => 'tax_shipping',
      11 => 'weee',
      12 => 'subtotal',
      13 => 'freeshipping',
      14 => 'tax_subtotal',
      15 => 'nominal',
      16 => 'subtotal',
      17 => 'shipping',
      18 => 'discount',
      19 => 'tax_subtotal',
      20 => 'freeshipping',
      21 => 'tax_shipping',
      22 => 'nominal',
      23 => 'weee',
      24 => 'cashondelivery',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'customerbalance',
      2 => 'giftcardaccount',
      3 => 'reward',
    ),
    '_code' => 'cashondelivery_tax',
  ),
  'shippingprotection' => 
  array (
    'class' => 'n98_shippingprotection/quote_address_total_shippingprotection',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'discount',
      2 => 'shipping',
      3 => 'nominal',
      4 => 'subtotal',
      5 => 'shipping',
      6 => 'nominal',
      7 => 'freeshipping',
      8 => 'tax_subtotal',
      9 => 'tax_shipping',
      10 => 'weee',
      11 => 'subtotal',
      12 => 'freeshipping',
      13 => 'tax_subtotal',
      14 => 'nominal',
    ),
    'before' => 
    array (
      0 => 'tax',
      1 => 'grand_total',
      2 => 'grand_total',
      3 => 'customerbalance',
      4 => 'giftcardaccount',
      5 => 'tax_giftwrapping',
      6 => 'reward',
      7 => 'cashondelivery_tax',
      8 => 'customerbalance',
      9 => 'giftcardaccount',
      10 => 'reward',
    ),
    '_code' => 'shippingprotection',
  ),
  'shippingprotectiontax' => 
  array (
    'class' => 'n98_shippingprotection/quote_address_total_shippingprotectionTax',
    'after' => 
    array (
      0 => 'subtotal',
      1 => 'discount',
      2 => 'shipping',
      3 => 'tax',
      4 => 'nominal',
      5 => 'subtotal',
      6 => 'shipping',
      7 => 'nominal',
      8 => 'freeshipping',
      9 => 'tax_subtotal',
      10 => 'tax_shipping',
      11 => 'weee',
      12 => 'subtotal',
      13 => 'freeshipping',
      14 => 'tax_subtotal',
      15 => 'nominal',
      16 => 'subtotal',
      17 => 'shipping',
      18 => 'discount',
      19 => 'tax_subtotal',
      20 => 'freeshipping',
      21 => 'tax_shipping',
      22 => 'nominal',
      23 => 'weee',
      24 => 'cashondelivery',
      25 => 'shippingprotection',
    ),
    'before' => 
    array (
      0 => 'grand_total',
      1 => 'customerbalance',
      2 => 'giftcardaccount',
      3 => 'reward',
    ),
    '_code' => 'shippingprotectiontax',
  ),
)

---

Update: Magento Bug Ticket: https://jira.magento.com/browse/MCACE-129

回答1:

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.

回答2:

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

回答3:

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

回答4:

Well was stucked at this for years!!!+

Now i know why some projects of the past were so difficult to adjust regarding wee and tax combinations a nightmare i could say, never got to understand why, yesterday i found why, later i found this article, a real shame.. but most of the time i need to know the response to be capable of search the question..

And the obvius solution at least for linux heads without fear, is the code below, basically i make use of the ancient linux command tsort that especifically does a topolocical order in the way we need here..

For the entomological and archeologist souls among us some pointers http://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html,I am using authentic 80's technology... yummmm

    /**
 * Aggregate before/after information from all items and sort totals based on this data
 *
 * @return array
 */
protected function _getSortedCollectorCodes() {
    if (Mage::app()->useCache('config')) {
        $cachedData = Mage::app()->loadCache($this->_collectorsCacheKey);
        if ($cachedData) {
            return unserialize($cachedData);
        }
    }
    $configArray = $this->_modelsConfig;
    // invoke simple sorting if the first element contains the "sort_order" key
    reset($configArray);
    $element = current($configArray);
    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_merge(
                        $configArray[$code]['before'],
                        $configArray[$beforeCode]['before']);
                $configArray[$code]['before'] = array_unique(
                        $configArray[$code]['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_merge(
                        $configArray[$code]['after'],
                        $configArray[$afterCode]['after']);
                $configArray[$code]['after'] = array_unique(
                        $configArray[$code]['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'));
        $res = "";
        foreach ($configArray as $code => $data) {
            foreach ($data['before'] as $beforeCode) {
                if (!isset($configArray[$beforeCode])) {
                    continue;
                }
                $res = $res . "$code $beforeCode\n";
            }
            foreach ($data['after'] as $afterCode) {
                if (!isset($configArray[$afterCode])) {
                    continue;
                }
                $res = $res . "$afterCode $code\n";
            }
        }
        file_put_contents(Mage::getBaseDir('tmp')."/graph.txt", $res);
        $sortedCollectors=explode("\n",shell_exec('tsort '.Mage::getBaseDir('tmp')."/graph.txt"),-1);           
    }
    if (Mage::app()->useCache('config')) {
        Mage::app()
                ->saveCache(serialize($sortedCollectors),
                        $this->_collectorsCacheKey,
                        array(Mage_Core_Model_Config::CACHE_TAG));
    }
    return $sortedCollectors;
}

I've posted the complete funcion for the sake of completeness, and of course is working like a charm for me at least...

回答5:

I decided to go with Plan B, overloading the getSortedCollectors... its straight forward and gives me absolut control, if course if I would introduce new modules I would have to check if I need to add them here

<?php
class YourModule_Sales_Model_Total_Quote_Collector extends Mage_Sales_Model_Quote_Address_Total_Collector {

    protected function _getSortedCollectorCodes() {
        return array(
            'nominal',
            'subtotal',
            'msrp',
            'freeshipping',
            'tax_subtotal',
            'weee',
            'shipping',
            'tax_shipping',
            'floorfee',
            'bottlediscount',
            'discount',
            'tax',
            'grand_total',
        );
    }

}

回答6:

The discussion above clearly indicate the problem. Usual sort doesn't work on the set of data without order function to be defied between any two element of the set. If only some of relational is defined like a "partial dependency" then topological sort must be used to obey declared "before" and "after" statement. In my test these declaration was broken in the resulted set depending of that and there I add additional modules. The scare part, it was not only affecting additional module but could change entire sorting result in unpredictable way. So, I implement standard topological sort which does solve the problem:

/**
 * The source data of the nodes and their dependencies, they are not required to be symmetrical node cold list other
 * node in 'after' but not present in its 'before' list:
 * @param $configArray
 *  $configArray = [
 *    <nodeCode>     => ["_code"=> <nodeCode>, "after"=> [<dependsOnNodeCode>, ...], "before"=> [<dependedByCode>, ...] ],
 *     ...
 * ]
 * The procedure updates adjacency list , to have every edge to be listed in the both nodes (in one 'after' and other 'before')
 */
function normalizeDependencies(&$configArray) {
    //For each node in the source data
    foreach ($configArray as $code => $data) {
            //Look up all nodes listed 'before' and update their 'after' for consistency
        foreach ($data['before'] as $beforeCode) {
            if (!isset($configArray[$beforeCode])) {
                continue;
            }
            $configArray[$beforeCode]['after'] = array_unique(array_merge(
                $configArray[$beforeCode]['after'], array($code)
            ));
        }
            //Look up all nodes listed 'after' and update their 'before' for consistency
        foreach ($data['after'] as $afterCode) {
            if (!isset($configArray[$afterCode])) {
                continue;
            }
            $configArray[$afterCode]['before'] = array_unique(array_merge(
                $configArray[$afterCode]['before'], array($code)
            ));
        }
    }
}

/**
 *  http://en.wikipedia.org/wiki/Topological_sorting
 *  Implements Kahn (1962) algorithms
 */
function topoSort(&$array) {
    normalizeDependencies($array);
    $result = array(); // Empty list that will contain the sorted elements
    $front = array(); // Set of all nodeCodes with no incoming edges
    //Push all items with no predecessors in S;
    foreach ($array as $code => $data) {
        if ( empty ($data['after']) ) {
            $front[] = $code;
        }
    }
    // While 'front' is not empty
    while (! empty ($front)) {
        //Deque 'frontier' from 'front'
        $frontierCode = array_shift($front);
        //Push it in 'result'
        $result[$frontierCode]= $array[$frontierCode];
        // Remove all outgoing edges from 'frontier';
        while (! empty ($array[$frontierCode]['before'])) {
            $afterCode = array_shift($array[$frontierCode]['before']);
            // remove corresponding edge e from the graph
            $array[$afterCode]['after'] = array_remove($array[$afterCode]['after'], $frontierCode);
            //* if, no more decencies put node into processing queue:
            // if m has no other incoming edges then
            if ( empty ($array[$afterCode]['after']) ) {
                // insert m into 'front'
                array_push($front, $afterCode);
            }
        }
    }
    if(count($result) != count($array)){
        saveGraph($array, 'mage-dependencies.dot');
        throw new Exception("Acyclic dependencies in data, see graphviz diagram: mage-dependencies.dot for details.");
    }
    return $result;
}
 /**
 * Could not find better way to remove value from array
 *
 * @param $array
 * @param $value
 * @return array
 */
protected function array_remove($array, $value){
    $cp = array();
    foreach($array as $b) {
        if($b != $value){
            $cp[]=$b;
        }
    }
    return $cp;
}

/**
 *  Saves graph in the graphviz format for visualisation:
 *    >dot -Tpng /tmp/dotfile.dot > viz-graph.png
 */
function saveGraph($configArray, $fileName){
    $fp = fopen($fileName,'w');
    fwrite($fp,"digraph TotalOrder\n");
    fwrite($fp,"{\n");
    foreach($configArray as $code=>$data) {
        fwrite($fp,"$code;\n");
        foreach($data['before'] as $beforeCode) {
            fwrite($fp,"$beforeCode -> $code;\n");
        }
        foreach($data['after'] as $afterCode) {
            fwrite($fp,"$code -> $afterCode;\n");
        }
    }
    fwrite($fp,"}\n");
    fclose($fp);
}

The question, how hard would be to get it (or other topo sort) into Magento release/hot fix?