Implementation of the XML normalization algorithm for SMEV 3?

Question

PHP

According to the guidelines for working with SMEV, when signing XML fragments with an electronic signature in the form of XMLDSig, it is mandatory to use urn://smev-gov-ru/xmldsig/transform normalization.
In the normalization algorithm, I absolutely do not understand the points related to namespaces, namely:

1. Remove namespace prefixes that are declared but not used at the current level.
   
2. Check that the current element's namespace is declared either up the tree or in the current element. If not declared, declare in the current element.
   
3. Namespace prefix of elements and attributes should be replaced with auto-generated ones. The generated prefix consists of the literal "ns", and the sequence number of the generated prefix within the XML fragment being processed, starting from one. When generating prefixes, their duplication should be eliminated.
   

At the same time, there is an example of the correct xml obtained after normalization.
Source XML * :

<ns:SenderProvidedRequestData Id="SIGNED_BY_CONSUMER" xmlns="urn://x-artefacts-smev-gov-ru/services/message-exchange/types/1.1" xmlns:ns="urn://x-artefacts-smev-gov-ru/services/message-exchange/types/1.1" xmlns:ns2="urn://x-artefacts-smev-gov-ru/services/message-exchange/types/basic/1.1">
  <ns:MessageID>db0486d0-3c08-11e5-95e2-d4c9eff07b77</ns:MessageID>
  <ns2:MessagePrimaryContent>
    <ns1:BreachRequest xmlns:ns1="urn://x-artefacts-gibdd-gov-ru/breach/root/1.0"  xmlns:ns2="urn://x-artefacts-gibdd-gov-ru/breach/commons/1.0"  xmlns:ns3="urn://x-artefacts-smev-gov-ru/supplementary/commons/1.0.1" Id="PERSONAL_SIGNATURE">
      <ns1:RequestedInformation>
        <ns2:RegPointNum>Т785ЕС57</ns2:RegPointNum>
      </ns1:RequestedInformation>
      <ns1:Governance>
        <ns2:Name>ГИБДД РФ</ns2:Name>
        <ns2:Code>GIBDD</ns2:Code>
        <ns2:OfficialPerson>
          <ns3:FamilyName>Загурский</ns3:FamilyName>
          <ns3:FirstName>Андрей</ns3:FirstName>
          <ns3:Patronymic>Петрович</ns3:Patronymic>
        </ns2:OfficialPerson>
      </ns1:Governance>
    </ns1:BreachRequest>
  </ns2:MessagePrimaryContent>
  <ns:TestMessage/>
</ns:SenderProvidedRequestData>

After normalization * :

<ns1:SenderProvidedRequestData xmlns:ns1="urn://x-artefacts-smev-gov-ru/services/message-exchange/types/1.1" Id="SIGNED_BY_CONSUMER">
  <ns1:MessageID>db0486d0-3c08-11e5-95e2-d4c9eff07b77</ns1:MessageID>
  <ns2:MessagePrimaryContent xmlns:ns2="urn://x-artefacts-smev-gov-ru/services/message-exchange/types/basic/1.1">
    <ns3:BreachRequest xmlns:ns3="urn://x-artefacts-gibdd-gov-ru/breach/root/1.0" Id="PERSONAL_SIGNATURE">
      <ns3:RequestedInformation>
        <ns4:RegPointNum xmlns:ns4="urn://x-artefacts-gibdd-gov-ru/breach/commons/1.0">Т785ЕС57</ns4:RegPointNum>
      </ns3:RequestedInformation>
      <ns3:Governance>
        <ns5:Name xmlns:ns5="urn://x-artefacts-gibdd-gov-ru/breach/commons/1.0">ГИБДД РФ</ns5:Name>
        <ns6:Code xmlns:ns6="urn://x-artefacts-gibdd-gov-ru/breach/commons/1.0">GIBDD</ns6:Code>
        <ns7:OfficialPerson xmlns:ns7="urn://x-artefacts-gibdd-gov-ru/breach/commons/1.0">
          <ns8:FamilyName xmlns:ns8="urn://x-artefacts-smev-gov-ru/supplementary/commons/1.0.1">Загурский</ns8:FamilyName>
          <ns9:FirstName xmlns:ns9="urn://x-artefacts-smev-gov-ru/supplementary/commons/1.0.1">Андрей</ns9:FirstName>
          <ns10:Patronymic xmlns:ns10="urn://x-artefacts-smev-gov-ru/supplementary/commons/1.0.1">Петрович</ns10:Patronymic>
        </ns7:OfficialPerson>
      </ns3:Governance>
    </ns3:BreachRequest>
  </ns2:MessagePrimaryContent>
  <ns1:TestMessage/>
</ns1:SenderProvidedRequestData>

* Line breaks and indentation added for easy viewing.
An exemplary implementation (whether it is an exemplary one is unknown) of the algorithm is presented in the methodical recommendations in Java for Apache Santuario.
Has anyone implemented this transformation algorithm in PHP?
Or at least able to understand the rules according to which the transformation should take place? Not in the language of GOST documentation, but in human language?

Answer 1

For future seekers: I got such a monster (PHP 7.1). It passes all the checks from MP 3.5, but, perhaps, does not take into account some of the nuances.

<?php
$in = new DOMDocument();
$in->load($argv[1]);

$out = new XMLWriter();
$out->openMemory();

$index = 0;
$stack = [null, [$in->documentElement, []]];
while (count($stack)) {
  $item = array_pop($stack);
  if ($item === null) {
    $out->text('');
    $out->endElement();
    continue;
  }
  [$node, $nsList] = $item;
  if ($node->nodeType == XML_ELEMENT_NODE) {
    // Let the magic begin! ;)
    // The element itself.
    if ($node->namespaceURI !== null) {
      $thisLevel = false;
      if (($nsList[$node->namespaceURI] ?? null) === null) {
        $thisLevel = true;
        $nsList[$node->namespaceURI] = 'ns' . ++$index;
      }
      $out->startElement("{$nsList[$node->namespaceURI]}:{$node->localName}");
      if ($thisLevel) {
        $out->writeAttribute("xmlns:{$nsList[$node->namespaceURI]}", $node->namespaceURI);
      }
    }
    else {
      $out->startElement($node->localName);
    }
    // Attributes.
    $attrs = iterator_to_array($node->attributes);
    usort($attrs, function($a, $b) {
      if ($a->namespaceURI !== null && $b->namespaceURI === null) return -1;
      else if ($a->namespaceURI === null && $b->namespaceURI !== null) return 1;
      else return strcmp($a->namespaceURI, $b->namespaceURI) ?: strcmp($a->localName, $b->localName);
    });
    foreach ($attrs as $attr) {
      if ($attr->namespaceURI !== null && ($nsList[$attr->namespaceURI] ?? null) === null) {
        $nsList[$attr->namespaceURI] = 'ns' . ++$index;
        $out->writeAttribute("xmlns:{$nsList[$attr->namespaceURI]}", $attr->namespaceURI);
      }
    }
    foreach ($attrs as $attr) {
      if ($attr->namespaceURI !== null) {
        $out->writeAttribute("{$nsList[$attr->namespaceURI]}:{$attr->localName}", $attr->nodeValue);
      }
      else {
        $out->writeAttribute($attr->localName, $attr->nodeValue);
      }
    }
  }
  else if ($node->nodeType == XML_TEXT_NODE && strlen(trim($node->nodeValue))) {
    $out->text($node->nodeValue);
  }

  if ($node->lastChild !== null) {
    $stack[] = null;
    for ($node = $node->lastChild; $node !== null; $node = $node->previousSibling) {
      $stack[] = [$node, $nsList];
    }
  }
}

echo $out->outputMemory(), "\n";

?>