Code Coverage
 
Classes and Traits
Functions and Methods
Lines
Total
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 9
CRAP
32.18% covered (danger)
32.18%
65 / 202
DOMDiff
0.00% covered (danger)
0.00%
0 / 1
0.00% covered (danger)
0.00%
0 / 9
2127.81
32.18% covered (danger)
32.18%
65 / 202
 nextNonTemplateSibling
0.00% covered (danger)
0.00%
0 / 1
12
0.00% covered (danger)
0.00%
0 / 3
 debug
0.00% covered (danger)
0.00%
0 / 1
2
0.00% covered (danger)
0.00%
0 / 2
 __construct
0.00% covered (danger)
0.00%
0 / 1
20
0.00% covered (danger)
0.00%
0 / 16
 diff
0.00% covered (danger)
0.00%
0 / 1
2
0.00% covered (danger)
0.00%
0 / 9
 treeEquals
0.00% covered (danger)
0.00%
0 / 1
380
0.00% covered (danger)
0.00%
0 / 37
 doDOMDiff
0.00% covered (danger)
0.00%
0 / 1
34.04
80.25% covered (warning)
80.25%
65 / 81
 subtreeDiffers
0.00% covered (danger)
0.00%
0 / 1
90
0.00% covered (danger)
0.00%
0 / 21
 markNode
0.00% covered (danger)
0.00%
0 / 1
182
0.00% covered (danger)
0.00%
0 / 20
 debugOut
0.00% covered (danger)
0.00%
0 / 1
12
0.00% covered (danger)
0.00%
0 / 13
<?php
declare( strict_types = 1 );
namespace Wikimedia\Parsoid\Html2Wt;
use Wikimedia\Assert\Assert;
use Wikimedia\Parsoid\Config\Env;
use Wikimedia\Parsoid\DOM\Comment;
use Wikimedia\Parsoid\DOM\DocumentFragment;
use Wikimedia\Parsoid\DOM\Element;
use Wikimedia\Parsoid\DOM\Node;
use Wikimedia\Parsoid\DOM\Text;
use Wikimedia\Parsoid\Ext\ParsoidExtensionAPI;
use Wikimedia\Parsoid\Utils\DOMCompat;
use Wikimedia\Parsoid\Utils\DOMDataUtils;
use Wikimedia\Parsoid\Utils\DOMUtils;
use Wikimedia\Parsoid\Utils\PHPUtils;
use Wikimedia\Parsoid\Utils\WTUtils;
/**
 * A DOM diff helper class.
 *
 * Compares two DOMs and annotates a copy of the passed-in DOM with change
 * information for the selective serializer.
 */
class DOMDiff {
    // These attributes are ignored for equality purposes if they are added to a node.
    private const IGNORE_ATTRIBUTES = [
        // Note that we are explicitly not ignoring data-parsoid even though clients
        // would never modify data-parsoid because SelectiveSerializer is wrapping text
        // nodes in spans and speculatively computes DSR offsets for these span tags
        // which are accurate for original DOM and may be inaccurate for the edited DOM.
        // By diffing data-parsoid which diffs the DSR as well, we ensure we mark such
        // nodes as modified and prevent use of those speculatively computed incorrect
        // DSR values.
        'data-parsoid-diff',
        'about',
        DOMDataUtils::DATA_OBJECT_ATTR_NAME,
    ];
    /**
     * @var Env
     */
    public $env;
    /** @var ParsoidExtensionAPI */
    public $extApi;
    /**
     * @var array
     */
    public $specializedAttribHandlers;
    /**
     * @param Node $node
     * @return Node|null
     */
    private function nextNonTemplateSibling( Node $node ): ?Node {
        if ( WTUtils::isEncapsulationWrapper( $node ) ) {
            return WTUtils::skipOverEncapsulatedContent( $node );
        }
        return $node->nextSibling;
    }
    /**
     * @param mixed ...$args
     */
    private function debug( ...$args ): void {
        $this->env->log( 'trace/domdiff', ...$args );
    }
    /**
     * @param Env $env
     */
    public function __construct( Env $env ) {
        $this->env = $env;
        $this->extApi = new ParsoidExtensionAPI( $env );
        $this->specializedAttribHandlers = [
            'data-mw' => static function ( $nodeA, $dmwA, $nodeB, $dmwB ) {
                return $dmwA == $dmwB;
            },
            'data-parsoid' => static function ( $nodeA, $dpA, $nodeB, $dpB ) {
                return $dpA == $dpB;
            },
            // TODO(T254502): This is added temporarily for backwards
            // compatibility and can be removed when versions up to 2.1.0
            // are no longer stored
            'typeof' => static function ( $nodeA, $valA, $nodeB, $valB ) {
                if ( $valA === $valB ) {
                    return true;
                } elseif ( $valA === 'mw:DisplaySpace' ) {
                    return $valB === 'mw:DisplaySpace mw:Placeholder';
                } elseif ( $valB === 'mw:DisplaySpace' ) {
                    return $valA === 'mw:DisplaySpace mw:Placeholder';
                } else {
                    return false;
                }
            }
        ];
    }
    /**
     * Diff two HTML documents, and add / update data-parsoid-diff attributes with
     * change information.
     *
     * @param Element $nodeA
     * @param Element $nodeB
     * @return array
     */
    public function diff( Element $nodeA, Element $nodeB ): array {
        Assert::invariant(
            $nodeA->ownerDocument !== $nodeB->ownerDocument,
            'Expected to be diff\'ing different documents.'
        );
        $this->debug( static function () use( $nodeA, $nodeB ) {
            return "ORIG:\n" .
                DOMCompat::getOuterHTML( $nodeA ) .
                "\nNEW :\n" .
                DOMCompat::getOuterHTML( $nodeB );
        } );
        // The root nodes are equal, call recursive differ
        $foundChange = $this->doDOMDiff( $nodeA, $nodeB );
        return [ 'isEmpty' => !$foundChange ];
    }
    /**
     * Test if two DOM nodes are equal.
     *
     * @param Node $nodeA
     * @param Node $nodeB
     * @param bool $deep
     * @return bool
     */
    public function treeEquals( Node $nodeA, Node $nodeB, bool $deep ): bool {
        if ( $nodeA->nodeType !== $nodeB->nodeType ) {
            return false;
        } elseif ( $nodeA instanceof Text ) {
            // In the past we've had bugs where we let non-primitive strings
            // leak into our DOM.  Safety first:
            Assert::invariant( $nodeA->nodeValue === (string)$nodeA->nodeValue, '' );
            Assert::invariant( $nodeB->nodeValue === (string)$nodeB->nodeValue, '' );
            // ok, now do the comparison.
            return $nodeA->nodeValue === $nodeB->nodeValue;
        } elseif ( $nodeA instanceof Comment ) {
            return WTUtils::decodeComment( $nodeA->nodeValue ) ===
                WTUtils::decodeComment( $nodeB->nodeValue );
        } elseif ( $nodeA instanceof Element || $nodeA instanceof DocumentFragment ) {
            if ( $nodeA instanceof DocumentFragment ) {
                if ( !( $nodeB instanceof DocumentFragment ) ) {
                    return false;
                }
            } else {  // $nodeA instanceof Element
                // Compare node name and attribute length
                if (
                    !( $nodeB instanceof Element ) ||
                    DOMCompat::nodeName( $nodeA ) !== DOMCompat::nodeName( $nodeB ) ||
                    !DiffUtils::attribsEquals(
                        $nodeA,
                        $nodeB,
                        self::IGNORE_ATTRIBUTES,
                        $this->specializedAttribHandlers
                    )
                ) {
                    return false;
                }
            }
            // Passed all tests, node itself is equal.
            if ( $deep ) {
                $childA = null;
                $childB = null;
                // Compare # of children, since that's fast.
                // (Avoid de-optimizing DOM by using node#childNodes)
                for ( $childA = $nodeA->firstChild, $childB = $nodeB->firstChild;
                    $childA && $childB;
                    $childA = $childA->nextSibling, $childB = $childB->nextSibling
                ) {
                    /* don't look inside children yet, just look at # of children */
                }
                if ( $childA || $childB ) {
                    return false; /* nodes have different # of children */
                }
                // Now actually compare the child subtrees
                for ( $childA = $nodeA->firstChild, $childB = $nodeB->firstChild;
                    $childA && $childB;
                    $childA = $childA->nextSibling, $childB = $childB->nextSibling
                ) {
                    if ( !$this->treeEquals( $childA, $childB, $deep ) ) {
                        return false;
                    }
                }
            }
            // Did not find a diff yet, so the trees must be equal.
            return true;
        }
        PHPUtils::unreachable( 'we shouldn\'t get here' );
        return false;
    }
    /**
     * Diff two DOM trees by comparing them node-by-node.
     *
     * TODO: Implement something more intelligent like
     * http://gregory.cobena.free.fr/www/Publications/%5BICDE2002%5D%20XyDiff%20-%20published%20version.pdf,
     * which uses hash signatures of subtrees to efficiently detect moves /
     * wrapping.
     *
     * Adds / updates a data-parsoid-diff structure with change information.
     *
     * Returns true if subtree is changed, false otherwise.
     *
     * TODO:
     * Assume typical CSS white-space, so ignore ws diffs in non-pre content.
     *
     * @param Node $baseParentNode
     * @param Node $newParentNode
     * @return bool
     */
    public function doDOMDiff( Node $baseParentNode, Node $newParentNode ): bool {
        // Perform a relaxed version of the recursive treeEquals algorithm that
        // allows for some minor differences and tries to produce a sensible diff
        // marking using heuristics like look-ahead on siblings.
        $baseNode = $baseParentNode->firstChild;
        $newNode = $newParentNode->firstChild;
        $lookaheadNode = null;
        $foundDiffOverall = false;
        while ( $baseNode && $newNode ) {
            $dontAdvanceNewNode = false;
            $this->debugOut( $baseNode, $newNode );
            // shallow check first
            if ( !$this->treeEquals( $baseNode, $newNode, false ) ) {
                $this->debug( '-- not equal --' );
                $savedNewNode = $newNode;
                $foundDiff = false;
                // Some simplistic look-ahead, currently limited to a single level
                // in the DOM.
                // look-ahead in *new* DOM to detect insertions
                if ( DOMUtils::isContentNode( $baseNode ) ) {
                    $this->debug( '--lookahead in new dom--' );
                    $lookaheadNode = $newNode->nextSibling;
                    while ( $lookaheadNode ) {
                        $this->debugOut( $baseNode, $lookaheadNode, 'new' );
                        if ( DOMUtils::isContentNode( $lookaheadNode ) &&
                            $this->treeEquals( $baseNode, $lookaheadNode, true )
                        ) {
                            // mark skipped-over nodes as inserted
                            $markNode = $newNode;
                            while ( $markNode !== $lookaheadNode ) {
                                $this->debug( '--found diff: inserted--' );
                                $this->markNode( $markNode, 'inserted' );
                                $markNode = $markNode->nextSibling;
                            }
                            $foundDiff = true;
                            $newNode = $lookaheadNode;
                            break;
                        }
                        $lookaheadNode = self::nextNonTemplateSibling( $lookaheadNode );
                    }
                }
                // look-ahead in *base* DOM to detect deletions
                if ( !$foundDiff && DOMUtils::isContentNode( $newNode ) ) {
                    $isBlockNode = WTUtils::isBlockNodeWithVisibleWT( $baseNode );
                    $this->debug( '--lookahead in old dom--' );
                    $lookaheadNode = $baseNode->nextSibling;
                    while ( $lookaheadNode ) {
                        $this->debugOut( $lookaheadNode, $newNode, 'old' );
                        if ( DOMUtils::isContentNode( $lookaheadNode ) &&
                            $this->treeEquals( $lookaheadNode, $newNode, true )
                        ) {
                            $this->debug( '--found diff: deleted--' );
                            // mark skipped-over nodes as deleted
                            $this->markNode( $newNode, 'deleted', $isBlockNode );
                            $baseNode = $lookaheadNode;
                            $foundDiff = true;
                            break;
                        } elseif ( !WTUtils::emitsSolTransparentSingleLineWT( $lookaheadNode ) ) {
                            // We only care about the deleted node prior to the one that
                            // gets a tree match (but, ignore nodes that show up in wikitext
                            // but don't affect sol-state or HTML rendering -- note that
                            // whitespace is being ignored, but that whitespace occurs
                            // between block nodes).
                            $isBlockNode = WTUtils::isBlockNodeWithVisibleWT( $lookaheadNode );
                        }
                        $lookaheadNode = self::nextNonTemplateSibling( $lookaheadNode );
                    }
                }
                if ( !$foundDiff ) {
                    if ( !( $savedNewNode instanceof Element ) ) {
                        $this->debug( '--found diff: modified text/comment--' );
                        $this->markNode( $savedNewNode, 'deleted', WTUtils::isBlockNodeWithVisibleWT( $baseNode ) );
                    } elseif ( $baseNode instanceof Element &&
                        DOMCompat::nodeName( $savedNewNode ) === DOMCompat::nodeName( $baseNode ) &&
                        ( DOMDataUtils::getDataParsoid( $savedNewNode )->stx ?? null ) ===
                        ( DOMDataUtils::getDataParsoid( $baseNode )->stx ?? null )
                    ) {
                        // Identical wrapper-type, but modified.
                        // Mark modified-wrapper, and recurse.
                        $this->debug( '--found diff: modified-wrapper--' );
                        $this->markNode( $savedNewNode, 'modified-wrapper' );
                        $this->subtreeDiffers( $baseNode, $savedNewNode );
                    } else {
                        // We now want to compare current newNode with the next baseNode.
                        $dontAdvanceNewNode = true;
                        // Since we are advancing in an old DOM without advancing
                        // in the new DOM, there were deletions. Add a deletion marker
                        // since this is important for accurate separator handling in selser.
                        $this->markNode( $savedNewNode, 'deleted', WTUtils::isBlockNodeWithVisibleWT( $baseNode ) );
                    }
                }
                // Record the fact that direct children changed in the parent node
                $this->debug( '--found diff: children-changed--' );
                $this->markNode( $newParentNode, 'children-changed' );
                $foundDiffOverall = true;
            } elseif ( $this->subtreeDiffers( $baseNode, $newNode ) ) {
                $foundDiffOverall = true;
            }
            // And move on to the next pair (skipping over template HTML)
            if ( $baseNode && $newNode ) {
                $baseNode = self::nextNonTemplateSibling( $baseNode );
                if ( !$dontAdvanceNewNode ) {
                    $newNode = self::nextNonTemplateSibling( $newNode );
                }
            }
        }
        // mark extra new nodes as inserted
        while ( $newNode ) {
            $this->debug( '--found trailing new node: inserted--' );
            $this->markNode( $newNode, 'inserted' );
            $foundDiffOverall = true;
            $newNode = self::nextNonTemplateSibling( $newNode );
        }
        // If there are extra base nodes, something was deleted. Mark the parent as
        // having lost children for now.
        if ( $baseNode ) {
            $this->debug( '--found trailing base nodes: deleted--' );
            $this->markNode( $newParentNode, 'children-changed' );
            // SSS FIXME: WTS checks for zero children in a few places
            // That code would have to be upgraded if we emit mw:DiffMarker
            // in this scenario. So, bailing out in this one case for now.
            if ( $newParentNode->hasChildNodes() ) {
                $meta = $newParentNode->ownerDocument->createElement( 'meta' );
                DOMUtils::addTypeOf( $meta, 'mw:DiffMarker/deleted' );
                if ( WTUtils::isBlockNodeWithVisibleWT( $baseNode ) ) {
                    $meta->setAttribute( 'data-is-block', 'true' );
                }
                $newParentNode->appendChild( $meta );
            }
            $foundDiffOverall = true;
        }
        return $foundDiffOverall;
    }
    /* ***************************************************
     * Helpers
     * ***************************************************/
    /**
     * @param Node $baseNode
     * @param Node $newNode
     * @return bool
     */
    private function subtreeDiffers( Node $baseNode, Node $newNode ): bool {
        $baseEncapsulated = WTUtils::isEncapsulationWrapper( $baseNode );
        $newEncapsulated = WTUtils::isEncapsulationWrapper( $newNode );
        if ( !$baseEncapsulated && !$newEncapsulated ) {
            $this->debug( '--shallow equal: recursing--' );
            // Recursively diff subtrees if not template-like content
            $subtreeDiffers = $this->doDOMDiff( $baseNode, $newNode );
        } elseif ( $baseEncapsulated && $newEncapsulated ) {
            '@phan-var Element $baseNode';  // @var Element $baseNode
            '@phan-var Element $newNode';  // @var Element $newNode
            $extType = DOMUtils::matchTypeOf( $baseNode, '!^mw:Extension/!' );
            $ext = null;
            if ( $extType ) {
                $dataMw = DOMDataUtils::getDataMw( $baseNode );
                // FIXME: The EncapsulatedContentHandler tries to get the name from
                // the typeOf if it isn't in dataMw ...
                $ext = $this->env->getSiteConfig()->getExtTagImpl( $dataMw->name ?? '' );
            }
            if (
                $ext && ( DOMUtils::matchTypeOf( $newNode, '!^mw:Extension/!' ) === $extType )
            ) {
                $this->debug( '--diffing extension content--' );
                $subtreeDiffers = $ext->diffHandler(
                    $this->extApi, [ $this, 'doDOMDiff' ], $baseNode, $newNode
                );
            } else {
                // Otherwise, for encapsulated content, we don't know about the subtree.
                $subtreeDiffers = false;
            }
        } else {
            // FIXME: Maybe $editNode should be marked as inserted to avoid
            // losing any edits, at the cost of more normalization.
            // $state->inModifiedContent is only set when we're in inserted
            // content, so not sure this is currently doing all that much.
            $subtreeDiffers = true;
        }
        if ( $subtreeDiffers ) {
            $this->debug( '--found diff: subtree-changed--' );
            $this->markNode( $newNode, 'subtree-changed' );
        }
        return $subtreeDiffers;
    }
    /**
     * @param Node $node
     * @param string $mark
     * @param bool $blockNodeDeleted
     */
    private function markNode( Node $node, string $mark, bool $blockNodeDeleted = false ): void {
        static $ignoreableNodeTypes = [ XML_DOCUMENT_NODE, XML_DOCUMENT_TYPE_NODE, XML_DOCUMENT_FRAG_NODE ];
        $meta = null;
        if ( $mark === 'deleted' ) {
            // insert a meta tag marking the place where content used to be
            $meta = DiffUtils::prependTypedMeta( $node, 'mw:DiffMarker/' . $mark );
        } else {
            if ( $node instanceof Element ) {
                DiffUtils::setDiffMark( $node, $this->env, $mark );
            } elseif ( $node instanceof Text || $node instanceof Comment ) {
                if ( $mark !== 'inserted' ) {
                    $this->env->log( 'error/domdiff',
                        'BUG! CHANGE-marker for ' . $node->nodeType . ' node is: ' . $mark
                    );
                }
                $meta = DiffUtils::prependTypedMeta( $node, 'mw:DiffMarker/' . $mark );
            } elseif ( !in_array( $node->nodeType, $ignoreableNodeTypes, true ) ) {
                $this->env->log( 'error/domdiff', 'Unhandled node type', $node->nodeType, 'in markNode!' );
            }
        }
        if ( $meta && $blockNodeDeleted ) {
            $meta->setAttribute( 'data-is-block', 'true' );
        }
        if ( $mark === 'deleted' || $mark === 'inserted' ) {
            $this->markNode( $node->parentNode, 'children-changed' );
        }
        // Clear out speculatively computed DSR values for data-mw-selser-wrapper nodes
        // since they may be incorrect. This eliminates any inadvertent use of
        // these incorrect values.
        if ( $node instanceof Element && $node->hasAttribute( 'data-mw-selser-wrapper' ) ) {
            DOMDataUtils::getDataParsoid( $node )->dsr = null;
        }
    }
    /**
     * @param Node $nodeA
     * @param Node $nodeB
     * @param string $laPrefix
     */
    private function debugOut( Node $nodeA, Node $nodeB, string $laPrefix = '' ): void {
        $this->env->log(
            'trace/domdiff',
            '--> A' . $laPrefix . ':' .
                ( $nodeA instanceof Element
                    ? DOMCompat::getOuterHTML( $nodeA )
                    : PHPUtils::jsonEncode( $nodeA->nodeValue ) )
        );
        $this->env->log(
            'trace/domdiff',
            '--> B' . $laPrefix . ':' .
                ( $nodeB instanceof Element
                    ? DOMCompat::getOuterHTML( $nodeB )
                    : PHPUtils::jsonEncode( $nodeB->nodeValue ) )
        );
    }
}