title: Sort algorithm: Magento checkout totals sorted wrongly causing wrong shipping tax calculation
body: <p>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.</p>
  
  <p>I added a custom total and if I add the following lines to the config.xml, the sorting is wrong. Wrong means: <code>tax_shipping</code> comes <strong>before</strong> <code>shipping</code>.
  This causes the tax for the shipping cost to be added twice.</p>
  
  <p>But this violates the condition</p>
  
  <pre><code>tax_shipping
  after: shipping
  </code></pre>
  
  <p>My guess: <strong>There must be some contradiction in the full set of rules.</strong> But how can I find it?</p>
  
  <p>This is the only rule I add. Without this rule, <code>tax_shipping</code> is sorted after <code>shipping</code>.</p>
  
  <pre><code>&lt;shippingprotectiontax&gt;
      &lt;class&gt;n98_shippingprotection/quote_address_total_shippingprotectionTax&lt;/class&gt;
      &lt;after&gt;subtotal,discount,shipping,tax&lt;/after&gt;
      &lt;before&gt;grand_total&lt;/before&gt;
  &lt;/shippingprotectiontax&gt;
  </code></pre>
  
  <p>Below I paste the sorted array that is returned by the usort call in <code>Mage_Sales_Model_Quote_Address_Total_Collector::_getSortedCollectorCodes()</code>
  For those who do not have a Magento installation, the code is like this:</p>
  
  <pre><code>/**
   * 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=&gt;$data) {
          $loginfo .= "$code\n";
          $loginfo .= "after: ".implode(',',$data['after'])."\n";
          $loginfo .= "before: ".implode(',',$data['before'])."\n";
          $loginfo .= "\n";
      }
      Mage::log($loginfo);
  
      ...
  </code></pre>
  
  <p>Log output:</p>
  
  <pre><code>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: 
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>After Vinai's answer I added more debug code </p>
  
  <pre><code>$fp = fopen('/tmp/dotfile','w');
  fwrite($fp,"digraph TotalOrder\n");
  fwrite($fp,"{\n");
  foreach($configArray as $code=&gt;$data) {
      $_code = $data['_code'];
      foreach($data['before'] as $beforeCode) {
          fwrite($fp,"$beforeCode -&gt; $_code;\n");
      }
      foreach($data['after'] as $afterCode) {
          fwrite($fp,"$_code -&gt; $afterCode;\n");
      }
  }
  fwrite($fp,"}\n");
  fclose($fp);
  </code></pre>
  
  <p>And visualized it with graphviz: <code>dot -Tpng dotfile &gt; viz.png</code>. That's the result of the first try. Called after the sorting.</p>
  
  <p><img src="https://i.stack.imgur.com/iuSyZ.jpg" alt="Visualization"></p>
  
  <p>EDIT2:</p>
  
  <p>I think this is pretty useless.</p>
  
  <p>So I made a visualization of the array before merging the after/before entries. (right after <code>$configArray = $this-&gt;_modelsConfig;</code>)</p>
  
  <p>This is it without my <code>shippingprotectiontax</code> entry:</p>
  
  <p><img src="https://i.stack.imgur.com/hXHxT.png" alt="enter image description here"></p>
  
  <p>This is it with my <code>shippingprotectiontax</code> entry:</p>
  
  <p><img src="https://i.stack.imgur.com/uiAjb.png" alt="enter image description here"></p>
  
  <p>I do not see any clear contradictions.</p>
  
  <p>EDIT3:</p>
  
  <p>Config array just before uasort:</p>
  
  <pre>
  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',
    ),
  )
  </pre>
  
  <hr>
  
  <p><em>Update:</em> Magento Bug Ticket: <a href="https://jira.magento.com/browse/MCACE-129" rel="noreferrer">https://jira.magento.com/browse/MCACE-129</a></p>