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

Question

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

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

Итак, я сделал визуализацию массива перед объединением записей после / до. (сразу после $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: https://jira.magento.com/browse/MCACE-129

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

1. Копирование app/code/core/Mage/Sales/Model/Config/Ordered.php в app/code/local/Mage/Sales/Model/Config/Ordered.php
2. Сохраните содержимое патча в файл 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

EDIT : есть и другое предлагаемое изменение (для Magento 2): https://github.com/magento/magento2/pull/49

Answer 3

РЕДАКТИРОВАТЬ: Этот ответ является неправильным . Смотрите обсуждение в комментариях.

---

Как отметил Винай, проблема в том, что функция заказа возвращает 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;
}

Answer 4

Я решил пойти с Планом 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',
        );
    }

}

Answer 5

Что ж, застрял в этом в течение многих лет !!! +

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

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

Для душ энтомологов и археологов среди нас некоторые указателиhttp://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html,I я использую аутентичную технологию 80-х годов ... нямм

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

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

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

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