Page Menu
Home
WickedGov Phorge
Search
Configure Global Search
Log In
Files
F4052706
DOMDiff.php
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Size
15 KB
Referenced Files
None
Subscribers
None
DOMDiff.php
View Options
<?php
declare
(
strict_types
=
1
);
namespace
Wikimedia\Parsoid\Html2Wt
;
use
Wikimedia\Assert\Assert
;
use
Wikimedia\Assert\UnreachableException
;
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\DiffDOMUtils
;
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
;
public
bool
$skipEncapsulatedContent
=
true
;
private
function
nextAnalyzableSibling
(
Node
$node
):
?
Node
{
if
(
WTUtils
::
isEncapsulationWrapper
(
$node
)
&&
$this
->
skipEncapsulatedContent
)
{
return
WTUtils
::
skipOverEncapsulatedContent
(
$node
);
}
return
$node
->
nextSibling
;
}
/**
* @param mixed ...$args
*/
private
function
debug
(
...
$args
):
void
{
$this
->
env
->
log
(
'trace/domdiff'
,
...
$args
);
}
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
)
.
"
\n
NEW :
\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
;
}
throw
new
UnreachableException
(
'we shouldn
\'
t get here'
);
}
/**
* 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
(
DiffDOMUtils
::
isContentNode
(
$baseNode
)
)
{
$this
->
debug
(
'--lookahead in new dom--'
);
$lookaheadNode
=
$newNode
->
nextSibling
;
while
(
$lookaheadNode
)
{
$this
->
debugOut
(
$baseNode
,
$lookaheadNode
,
'new'
);
if
(
DiffDOMUtils
::
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
,
DiffMarkers
::
INSERTED
);
$markNode
=
$markNode
->
nextSibling
;
}
$foundDiff
=
true
;
$newNode
=
$lookaheadNode
;
break
;
}
$lookaheadNode
=
self
::
nextAnalyzableSibling
(
$lookaheadNode
);
}
}
// look-ahead in *base* DOM to detect deletions
if
(
!
$foundDiff
&&
DiffDOMUtils
::
isContentNode
(
$newNode
)
)
{
$isBlockNode
=
WTUtils
::
isBlockNodeWithVisibleWT
(
$baseNode
);
$this
->
debug
(
'--lookahead in old dom--'
);
$lookaheadNode
=
$baseNode
->
nextSibling
;
while
(
$lookaheadNode
)
{
$this
->
debugOut
(
$lookaheadNode
,
$newNode
,
'old'
);
if
(
DiffDOMUtils
::
isContentNode
(
$lookaheadNode
)
&&
$this
->
treeEquals
(
$lookaheadNode
,
$newNode
,
true
)
)
{
$this
->
debug
(
'--found diff: deleted--'
);
// mark skipped-over nodes as deleted
$this
->
markNode
(
$newNode
,
DiffMarkers
::
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
::
nextAnalyzableSibling
(
$lookaheadNode
);
}
}
if
(
!
$foundDiff
)
{
if
(
!(
$savedNewNode
instanceof
Element
)
)
{
$this
->
debug
(
'--found diff: modified text/comment--'
);
$this
->
markNode
(
$savedNewNode
,
DiffMarkers
::
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
,
DiffMarkers
::
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
,
DiffMarkers
::
DELETED
,
WTUtils
::
isBlockNodeWithVisibleWT
(
$baseNode
)
);
}
}
// Record the fact that direct children changed in the parent node
$this
->
debug
(
'--found diff: children-changed--'
);
$this
->
markNode
(
$newParentNode
,
DiffMarkers
::
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
::
nextAnalyzableSibling
(
$baseNode
);
if
(
!
$dontAdvanceNewNode
)
{
$newNode
=
self
::
nextAnalyzableSibling
(
$newNode
);
}
}
}
// mark extra new nodes as inserted
while
(
$newNode
)
{
$this
->
debug
(
'--found trailing new node: inserted--'
);
$this
->
markNode
(
$newNode
,
DiffMarkers
::
INSERTED
);
$foundDiffOverall
=
true
;
$newNode
=
self
::
nextAnalyzableSibling
(
$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
,
DiffMarkers
::
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
$ext
=
null
;
$baseExtTagName
=
WTUtils
::
getExtTagName
(
$baseNode
);
if
(
$baseExtTagName
)
{
$ext
=
$this
->
env
->
getSiteConfig
()->
getExtTagImpl
(
$baseExtTagName
);
}
if
(
$ext
&&
(
$baseExtTagName
===
WTUtils
::
getExtTagName
(
$newNode
)
)
)
{
$this
->
debug
(
'--diffing extension content--'
);
$subtreeDiffers
=
$ext
->
diffHandler
(
$this
->
extApi
,
[
$this
,
'doDOMDiff'
],
$baseNode
,
$newNode
);
}
elseif
(
$this
->
skipEncapsulatedContent
)
{
// Otherwise, for encapsulated content, we don't know about the subtree.
$subtreeDiffers
=
false
;
}
else
{
$this
->
debug
(
'--shallow equal (encapsulated): recursing--'
);
// Recursively diff subtrees if not template-like content
$subtreeDiffers
=
$this
->
doDOMDiff
(
$baseNode
,
$newNode
);
}
}
else
{
// FIXME: Maybe $editNode should be marked as inserted to avoid
// losing any edits, at the cost of more normalization.
// $state->inInsertedContent 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
,
DiffMarkers
::
SUBTREE_CHANGED
);
}
return
$subtreeDiffers
;
}
private
function
markNode
(
Node
$node
,
string
$mark
,
bool
$blockNodeDeleted
=
false
):
void
{
$meta
=
DiffUtils
::
addDiffMark
(
$node
,
$this
->
env
,
$mark
);
if
(
$meta
&&
$blockNodeDeleted
)
{
$meta
->
setAttribute
(
'data-is-block'
,
'true'
);
}
if
(
$mark
===
DiffMarkers
::
DELETED
||
$mark
===
DiffMarkers
::
INSERTED
)
{
$this
->
markNode
(
$node
->
parentNode
,
DiffMarkers
::
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
;
}
}
private
function
debugOut
(
Node
$nodeA
,
Node
$nodeB
,
string
$laPrefix
=
''
):
void
{
$prefix
=
'trace/domdiff'
;
$this
->
env
->
log
(
$prefix
,
static
fn
()
=>
'--> A'
.
$laPrefix
.
':'
.
(
$nodeA
instanceof
Element
?
DOMCompat
::
getOuterHTML
(
$nodeA
)
:
PHPUtils
::
jsonEncode
(
$nodeA
->
nodeValue
)
)
);
$this
->
env
->
log
(
$prefix
,
static
fn
()
=>
'--> B'
.
$laPrefix
.
':'
.
(
$nodeB
instanceof
Element
?
DOMCompat
::
getOuterHTML
(
$nodeB
)
:
PHPUtils
::
jsonEncode
(
$nodeB
->
nodeValue
)
)
);
}
}
File Metadata
Details
Attached
Mime Type
text/x-php
Expires
Aug 15 2026, 19:45 (13 w, 3 d ago)
Storage Engine
local-disk
Storage Format
Raw Data
Storage Handle
1b/36/ab1a86c0d6bd2d0a90aeac606dc4
Default Alt Text
DOMDiff.php (15 KB)
Attached To
Mode
rMWPROD MediaWiki Production
Attached
Detach File
Event Timeline
Log In to Comment