Алгоритм сортировки: итоговые суммы погашения Magento отсортированы неправильно, что приводит к неправильному исчислению налога на отправку

В Magento есть функциональность, где вы можете определить порядок общего расчета, указав до и после которого итоговое значение должно быть запущено.

Я добавил пользовательскую общую сумму, и если я добавлю следующие строки в файл config.xml, сортировка будет неправильной. Неверное означает: tax_shipping приходит до shipping. Это приводит к тому, что налог за доставку будет добавлен дважды.

Но это нарушает условие

tax_shipping
after: shipping

Мое предположение: Должно быть какое-то противоречие в полном наборе правил. Но как я могу его найти?

Это единственное правило, которое я добавляю. Без этого правила tax_shipping сортируется после shipping.

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

Ниже я вставляю отсортированный массив, который возвращается вызовом usort в Mage_Sales_Model_Quote_Address_Total_Collector::_getSortedCollectorCodes() Для тех, у кого нет установки Magento, код выглядит следующим образом:

/**
 * 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);

    ...

Выход журнала:

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:

После ответа Vinai я добавил еще отладочный код

$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);

И визуализировал его с помощью графика: dot -Tpng dotfile > viz.png. Это результат первой попытки. Вызывается после сортировки.

EDIT2:

Я думаю, что это бесполезно.

Итак, я сделал визуализацию массива перед слиянием записей after/before. (сразу после $configArray = $this->_modelsConfig;)

Это без моей записи shippingprotectiontax:

Это с моей записью shippingprotectiontax:

Я не вижу ясных противоречий.

EDIT3:

Конфигурировать массив непосредственно перед 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',
  ),
)

Обновление: Magento Bug Ticket: https://jira.magento.com/browse/MCACE-129

Ответ 1

Итак, вот мой патч для этой проблемы.

Он реализует топологическую сортировку, предложенную Винаем.

Скопировать app/code/core/Mage/Sales/Model/Config/Ordered.php в app/code/local/Mage/Sales/Model/Config/Ordered.php
Сохраните содержимое патча в файл total-sorting.patch и вызовите patch -p0 app/code/local/Mage/Sales/Model/Config/Ordered.php

В случае обновлений обязательно повторите эти шаги.

Патч протестирован для работы с 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

РЕДАКТИРОВАТЬ: Существует также другое предложенное изменение (для Magento 2): https://github.com/magento/magento2/pull/49

Ответ 2

Спасибо за сохранение @Alex, вот лучший ответ с лучшим объяснением:) Мой первый ответ был неправильным.

PHP реализует quicksort для всех функций сортировки массивов (ссылка zend_qsort.c).
Если две записи в массиве идентичны, их место будет заменено.

Проблема заключается в общей записи giftwrap, которая в соответствии с _compareTotals() больше, чем промежуточная и номинальная, но равна всем остальным итоговым значениям.

В зависимости от исходного порядка входного массива $confArray и размещения элемента сводки законно заменять подарочную упаковку, например. скидка, потому что оба равны, хотя скидка больше, чем доставка.

Это может сделать проблему более ясной с точки зрения алгоритмов сортировки:

доставка < tax_shipping
giftwrapping == shipping
подарочная упаковка == tax_shipping

Существует несколько возможных решений, хотя исходной проблемой является выбор quicksort для построения ориентированного ациклического графика зависимости

Одно (плохое, короткое) решение будет заключаться в том, чтобы добавить больше зависимостей к сумме giftwrapping, даже несмотря на то, что все еще может быть больше проблем с другими суммами, которые до сих пор не отображались.
Реальное решение будет заключаться в реализации алгоритма топологической сортировки для проблемы.

Интересно, что не так много пакетов PHP, плавающих вокруг. Существует сиротный пакет PEAR Structures_Graph. Использование этого, вероятно, было бы быстрым решением, но это означало бы преобразование структуры $confArray в структуру Structures_Graph (возможно, не так быстро).

Википедия хорошо справляется с этой проблемой, поэтому распространение собственного решения может быть интересной задачей. Немецкая версия Википедии топологическая сортировка разбивает проблему на логические шаги, а также имеет отличный примерный алгоритм в PERL.

Ответ 3

EDIT: Этот ответ неверен. См. Обсуждение в комментариях.

Как отметил Винай, проблема в том, что функция порядка возвращает 0, даже если параметры не равный. Я изменил функцию, чтобы вернуться к строковому порядку клавиш следующим образом:

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

Хорошо застрял в этом годами!!! +

Теперь я знаю, почему некоторые проекты прошлого были настолько сложны, чтобы приспосабливаться в отношении комбинаций налогов и налогов, которые я мог бы сказать, никогда не понимал, почему вчера я нашел почему, позже я нашел эту статью, настоящий позор. но большую часть времени мне нужно знать ответ, чтобы он мог искать вопрос.

И решение obvius, по крайней мере, для Linux-голов без страха, - это код ниже, в основном я использую древнюю командную команду linux, которая особенно делает топологический порядок в том виде, в котором мы нуждаемся здесь.

Для энтомологических и археологических душ среди нас есть некоторые указатели http://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html,I с использованием аутентичной технологии 80... 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;
}

Я выложил всю функциональность ради полноты, и, конечно же, для меня как бы прелести, по крайней мере...

Ответ 5

Я решил пойти с Plan B, перегрузив getSortedCollectors... его прямо вперед и дал мне абсолютный контроль, если бы курс, если бы я представил новые модули, мне пришлось бы проверить, нужно ли их добавлять сюда.

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

Вопрос, насколько сложно было бы получить его (или другую сортировку topo) в выпуске Magento/hot fix?