Very interesting problem. I would do this in two passes: first, nest the elements according to their hierarchy. Then output the elements, sorted by the count of their ancestors.
XSLT 1.0 (+ EXSLT node-set() function):
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:exsl="http://exslt.org/common"
extension-element-prefixes="exsl">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:key name="product-by-code" match="product" use="@code" />
<!-- first pass -->
<xsl:variable name="nested">
<xsl:apply-templates select="/order/line/product[not(key('product-by-code', @parent))]" mode="nest"/>
</xsl:variable>
<xsl:template match="product" mode="nest">
<xsl:copy>
<xsl:copy-of select="@*"/>
<xsl:apply-templates select="../../line/product[@parent=current()/@code]" mode="nest"/>
</xsl:copy>
</xsl:template>
<!-- output -->
<xsl:template match="/order">
<xsl:copy>
<xsl:for-each select="exsl:node-set($nested)//product">
<xsl:sort select="count(ancestor::*)" data-type="number" order="ascending"/>
<line><product><xsl:copy-of select="@*"/></product></line>
</xsl:for-each>
</xsl:copy>
</xsl:template>
</xsl:stylesheet>
When applied to your input, the result is:
<?xml version="1.0" encoding="UTF-8"?>
<order>
<line>
<product code="6" parent="X"/>
</line>
<line>
<product code="1"/>
</line>
<line>
<product code="3" parent="1"/>
</line>
<line>
<product code="2" parent="1"/>
</line>
<line>
<product code="4" parent="2"/>
</line>
</order>
This still leaves the issue of the existing/missing parent X - I will try to address that later.