*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
* or see http://www.gnu.org/
*/
/**
* Any element in the DOM tree of an HTML document.
*/
class Node {
public $parent;
protected $parentTree;
public $whiteBefore = false;
public $whiteAfter = false;
function __construct($parent) {
$this->parent = $parent;
}
public function getParentTree() {
if (!isset($this->parentTree)) {
if (!is_null($this->parent)) {
$this->parentTree = $this->parent->getParentTree();
$this->parentTree[] = $this->parent;
} else {
$this->parentTree = array();
}
}
return $this->parentTree;
}
public function getLastCommonParent(Node $other) {
$result = new LastCommonParentResult();
$myParents = $this->getParentTree();
$otherParents = $other->getParentTree();
$i = 1;
$isSame = true;
$nbMyParents = count($myParents);
$nbOtherParents = count($otherParents);
while ($isSame && $i < $nbMyParents && $i < $nbOtherParents) {
if (!$myParents[$i]->openingTag === $otherParents[$i]->openingTag) {
$isSame = false;
} else {
// After a while, the index i-1 must be the last common parent
$i++;
}
}
$result->lastCommonParentDepth = $i - 1;
$result->parent = $myParents[$i - 1];
if (!$isSame || $nbMyParents > $nbOtherParents) {
// Not all tags matched, or all tags matched but
// there are tags left in this tree
$result->indexInLastCommonParent = $myParents[$i - 1]->getIndexOf($myParents[$i]);
$result->splittingNeeded = true;
} else if ($nbMyParents <= $nbOtherParents) {
$result->indexInLastCommonParent = $myParents[$i - 1]->getIndexOf($this);
}
return $result;
}
public function setParent($parent) {
$this->parent = $parent;
unset($this->parentTree);
}
public function inPre() {
$tree = $this->getParentTree();
foreach ($tree as &$ancestor) {
if ($ancestor->isPre()) {
return true;
}
}
return false;
}
}
/**
* Node that can contain other nodes. Represents an HTML tag.
*/
class TagNode extends Node {
public $children = array();
public $qName;
public $attributes = array();
public $openingTag;
function __construct($parent, $qName, /*array*/ $attributes) {
parent::__construct($parent);
$this->qName = strtolower($qName);
foreach($attributes as $key => &$value){
$this->attributes[strtolower($key)] = $value;
}
return $this->openingTag = Xml::openElement($this->qName, $this->attributes);
}
public function addChildAbsolute(Node $node, $index) {
array_splice($this->children, $index, 0, array($node));
}
public function getIndexOf(Node $child) {
// don't trust array_search with objects
foreach ($this->children as $key => &$value){
if ($value === $child) {
return $key;
}
}
return null;
}
public function getNbChildren() {
return count($this->children);
}
public function getMinimalDeletedSet($id, &$allDeleted, &$somethingDeleted) {
$nodes = array();
$allDeleted = false;
$somethingDeleted = false;
$hasNonDeletedDescendant = false;
if (empty($this->children)) {
return $nodes;
}
foreach ($this->children as &$child) {
$allDeleted_local = false;
$somethingDeleted_local = false;
$childrenChildren = $child->getMinimalDeletedSet($id, $allDeleted_local, $somethingDeleted_local);
if ($somethingDeleted_local) {
$nodes = array_merge($nodes, $childrenChildren);
$somethingDeleted = true;
}
if (!$allDeleted_local) {
$hasNonDeletedDescendant = true;
}
}
if (!$hasNonDeletedDescendant) {
$nodes = array($this);
$allDeleted = true;
}
return $nodes;
}
public function splitUntil(TagNode $parent, Node $split, $includeLeft) {
$splitOccured = false;
if ($parent !== $this) {
$part1 = new TagNode(null, $this->qName, $this->attributes);
$part2 = new TagNode(null, $this->qName, $this->attributes);
$part1->setParent($this->parent);
$part2->setParent($this->parent);
$onSplit = false;
$pastSplit = false;
foreach ($this->children as &$child)
{
if ($child === $split) {
$onSplit = true;
}
if(!$pastSplit || ($onSplit && $includeLeft)) {
$child->setParent($part1);
$part1->children[] = $child;
} else {
$child->setParent($part2);
$part2->children[] = $child;
}
if ($onSplit) {
$onSplit = false;
$pastSplit = true;
}
}
$myindexinparent = $this->parent->getIndexOf($this);
if (!empty($part1->children)) {
$this->parent->addChildAbsolute($part1, $myindexinparent);
}
if (!empty($part2->children)) {
$this->parent->addChildAbsolute($part2, $myindexinparent);
}
if (!empty($part1->children) && !empty($part2->children)) {
$splitOccured = true;
}
$this->parent->removeChild($myindexinparent);
if ($includeLeft) {
$this->parent->splitUntil($parent, $part1, $includeLeft);
} else {
$this->parent->splitUntil($parent, $part2, $includeLeft);
}
}
return $splitOccured;
}
private function removeChild($index) {
unset($this->children[$index]);
$this->children = array_values($this->children);
}
public static $blocks = array('html', 'body','p','blockquote', 'h1',
'h2', 'h3', 'h4', 'h5', 'pre', 'div', 'ul', 'ol', 'li', 'table',
'tbody', 'tr', 'td', 'th', 'br');
public function copyTree() {
$newThis = new TagNode(null, $this->qName, $this->attributes);
$newThis->whiteBefore = $this->whiteBefore;
$newThis->whiteAfter = $this->whiteAfter;
foreach ($this->children as &$child) {
$newChild = $child->copyTree();
$newChild->setParent($newThis);
$newThis->children[] = $newChild;
}
return $newThis;
}
public function getMatchRatio(TagNode $other) {
$txtComp = new TextOnlyComparator($other);
return $txtComp->getMatchRatio(new TextOnlyComparator($this));
}
public function expandWhiteSpace() {
$shift = 0;
$spaceAdded = false;
$nbOriginalChildren = $this->getNbChildren();
for ($i = 0; $i < $nbOriginalChildren; ++$i) {
$child = $this->children[$i + $shift];
if ($child instanceof TagNode) {
if (!$child->isPre()) {
$child->expandWhiteSpace();
}
}
if (!$spaceAdded && $child->whiteBefore) {
$ws = new WhiteSpaceNode(null, ' ', $child->getLeftMostChild());
$ws->setParent($this);
$this->addChildAbsolute($ws,$i + ($shift++));
}
if ($child->whiteAfter) {
$ws = new WhiteSpaceNode(null, ' ', $child->getRightMostChild());
$ws->setParent($this);
$this->addChildAbsolute($ws,$i + 1 + ($shift++));
$spaceAdded = true;
} else {
$spaceAdded = false;
}
}
}
public function getLeftMostChild() {
if (empty($this->children)) {
return $this;
}
return $this->children[0]->getLeftMostChild();
}
public function getRightMostChild() {
if (empty($this->children)) {
return $this;
}
return $this->children[$this->getNbChildren() - 1]->getRightMostChild();
}
public function isPre() {
return 0 == strcasecmp($this->qName,'pre');
}
public static function toDiffLine(TagNode $node) {
return $node->openingTag;
}
}
/**
* Represents a piece of text in the HTML file.
*/
class TextNode extends Node {
public $text;
public $modification;
function __construct($parent, $text) {
parent::__construct($parent);
$this->modification = new Modification(Modification::NONE);
$this->text = $text;
}
public function copyTree() {
$clone = clone $this;
$clone->setParent(null);
return $clone;
}
public function getLeftMostChild() {
return $this;
}
public function getRightMostChild() {
return $this;
}
public function getMinimalDeletedSet($id, &$allDeleted, &$somethingDeleted) {
if ($this->modification->type == Modification::REMOVED
&& $this->modification->id == $id){
$somethingDeleted = true;
$allDeleted = true;
return array($this);
}
return array();
}
public function isSameText($other) {
if (is_null($other) || ! $other instanceof TextNode) {
return false;
}
return str_replace('\n', ' ',$this->text) === str_replace('\n', ' ',$other->text);
}
public static function toDiffLine(TextNode $node) {
return str_replace('\n', ' ',$node->text);
}
}
class WhiteSpaceNode extends TextNode {
function __construct($parent, $s, Node $like = null) {
parent::__construct($parent, $s);
if(!is_null($like) && $like instanceof TextNode) {
$newModification = clone $like->modification;
$newModification->firstOfID = false;
$this->modification = $newModification;
}
}
}
/**
* Represents the root of a HTML document.
*/
class BodyNode extends TagNode {
function __construct() {
parent::__construct(null, 'body', array());
}
public function copyTree() {
$newThis = new BodyNode();
foreach ($this->children as &$child) {
$newChild = $child->copyTree();
$newChild->setParent($newThis);
$newThis->children[] = $newChild;
}
return $newThis;
}
public function getMinimalDeletedSet($id, &$allDeleted, &$somethingDeleted) {
$nodes = array();
foreach ($this->children as &$child) {
$childrenChildren = $child->getMinimalDeletedSet($id,
$allDeleted, $somethingDeleted);
$nodes = array_merge($nodes, $childrenChildren);
}
return $nodes;
}
}
/**
* Represents an image in HTML. Even though images do not contain any text they
* are independent visible objects on the page. They are logically a TextNode.
*/
class ImageNode extends TextNode {
public $attributes;
function __construct(TagNode $parent, /*array*/ $attrs) {
if(!array_key_exists('src', $attrs)) {
//wfDebug('Image without a source:');
//foreach ($attrs as $key => &$value) {
//wfDebug("$key = $value");
//}
parent::__construct($parent, '');
}else{
parent::__construct($parent, '
' . strtolower($attrs['src']) . '');
}
$this->attributes = $attrs;
}
public function isSameText($other) {
if (is_null($other) || ! $other instanceof ImageNode) {
return false;
}
return $this->text === $other->text;
}
}
class DummyNode extends Node {
function __construct() {
// no op
}
}
/**
* When detecting the last common parent of two nodes, all results are stored as
* a LastCommonParentResult.
*/
class LastCommonParentResult {
// Parent
public $parent;
// Splitting
public $splittingNeeded = false;
// Depth
public $lastCommonParentDepth = -1;
// Index
public $indexInLastCommonParent = -1;
}
class Modification{
const NONE = 1;
const REMOVED = 2;
const ADDED = 4;
const CHANGED = 8;
public $type;
public $id = -1;
public $firstOfID = false;
public $changes;
function __construct($type) {
$this->type = $type;
}
public static function typeToString($type) {
switch($type) {
case self::NONE: return 'none';
case self::REMOVED: return 'removed';
case self::ADDED: return 'added';
case self::CHANGED: return 'changed';
}
}
}
class DomTreeBuilder {
public $textNodes = array();
public $bodyNode;
private $currentParent;
private $newWord = '';
protected $bodyStarted = false;
protected $bodyEnded = false;
private $whiteSpaceBeforeThis = false;
private $lastSibling;
private $notInPre = true;
function __construct() {
$this->bodyNode = $this->currentParent = new BodyNode();
$this->lastSibling = new DummyNode();
}
/**
* Must be called manually
*/
public function endDocument() {
$this->endWord();
//wfDebug(count($this->textNodes) . ' text nodes in document.');
}
public function startElement($parser, $name, /*array*/ $attributes) {
if (strcasecmp($name, 'body') != 0) {
//wfDebug("Starting $name node.");
$this->endWord();
$newNode = new TagNode($this->currentParent, $name, $attributes);
$this->currentParent->children[] = $newNode;
$this->currentParent = $newNode;
$this->lastSibling = new DummyNode();
if ($this->whiteSpaceBeforeThis && !in_array(strtolower($this->currentParent->qName),TagNode::$blocks)) {
$this->currentParent->whiteBefore = true;
}
$this->whiteSpaceBeforeThis = false;
if(strcasecmp($name, 'pre') == 0) {
$this->notInPre = false;
}
}
}
public function endElement($parser, $name) {
if(strcasecmp($name, 'body') != 0) {
//wfDebug("Ending $name node.");
if (0 == strcasecmp($name,'img')) {
// Insert a dummy leaf for the image
$img = new ImageNode($this->currentParent, $this->currentParent->attributes);
$this->currentParent->children[] = $img;
$img->whiteBefore = $this->whiteSpaceBeforeThis;
$this->lastSibling = $img;
$this->textNodes[] = $img;
}
$this->endWord();
if (!in_array(strtolower($this->currentParent->qName),TagNode::$blocks)) {
$this->lastSibling = $this->currentParent;
} else {
$this->lastSibling = new DummyNode();
}
$this->currentParent = $this->currentParent->parent;
$this->whiteSpaceBeforeThis = false;
if (!$this->notInPre && strcasecmp($name, 'pre') == 0) {
$this->notInPre = true;
}
} else {
$this->endDocument();
}
}
const regex = '/([\s\.\,\"\\\'\(\)\?\:\;\!\{\}\-\+\*\=\_\[\]\&\|\$]{1})/';
const whitespace = '/^[\s]{1}$/';
const delimiter = '/^[\s\.\,\"\\\'\(\)\?\:\;\!\{\}\-\+\*\=\_\[\]\&\|\$]{1}$/';
public function characters($parser, $data) {
$matches = preg_split(self::regex, $data, -1, PREG_SPLIT_DELIM_CAPTURE);
foreach($matches as &$word) {
if (preg_match(self::whitespace, $word) && $this->notInPre) {
$this->endWord();
$this->lastSibling->whiteAfter = true;
$this->whiteSpaceBeforeThis = true;
} else if (preg_match(self::delimiter, $word)) {
$this->endWord();
$textNode = new TextNode($this->currentParent, $word);
$this->currentParent->children[] = $textNode;
$textNode->whiteBefore = $this->whiteSpaceBeforeThis;
$this->whiteSpaceBeforeThis = false;
$this->lastSibling = $textNode;
$this->textNodes[] = $textNode;
} else {
$this->newWord .= $word;
}
}
}
private function endWord() {
if ($this->newWord !== '') {
$node = new TextNode($this->currentParent, $this->newWord);
$this->currentParent->children[] = $node;
$node->whiteBefore = $this->whiteSpaceBeforeThis;
$this->whiteSpaceBeforeThis = false;
$this->lastSibling = $node;
$this->textNodes[] = $node;
$this->newWord = "";
}
}
public function getDiffLines() {
return array_map(array('TextNode','toDiffLine'), $this->textNodes);
}
}
class TextNodeDiffer {
private $textNodes;
public $bodyNode;
private $oldTextNodes;
private $oldBodyNode;
private $newID = 0;
private $changedID = 0;
private $changedIDUsed = false;
// used to remove the whitespace between a red and green block
private $whiteAfterLastChangedPart = false;
private $deletedID = 0;
function __construct(DomTreeBuilder $tree, DomTreeBuilder $oldTree) {
$this->textNodes = $tree->textNodes;
$this->bodyNode = $tree->bodyNode;
$this->oldTextNodes = $oldTree->textNodes;
$this->oldBodyNode = $oldTree->bodyNode;
}
public function markAsNew($start, $end) {
if ($end <= $start) {
return;
}
if ($this->whiteAfterLastChangedPart) {
$this->textNodes[$start]->whiteBefore = false;
}
for ($i = $start; $i < $end; ++$i) {
$mod = new Modification(Modification::ADDED);
$mod->id = $this->newID;
$this->textNodes[$i]->modification = $mod;
}
if ($start < $end) {
$this->textNodes[$start]->modification->firstOfID = true;
}
++$this->newID;
}
public function handlePossibleChangedPart($leftstart, $leftend, $rightstart, $rightend) {
$i = $rightstart;
$j = $leftstart;
if ($this->changedIDUsed) {
++$this->changedID;
$this->changedIDUsed = false;
}
$changes;
while ($i < $rightend) {
$acthis = new AncestorComparator($this->textNodes[$i]->getParentTree());
$acother = new AncestorComparator($this->oldTextNodes[$j]->getParentTree());
$result = $acthis->getResult($acother);
unset($acthis, $acother);
if ($result->changed) {
$mod = new Modification(Modification::CHANGED);
if (!$this->changedIDUsed) {
$mod->firstOfID = true;
} else if (!is_null($result->changes) && $result->changes !== $this->changes) {
++$this->changedID;
$mod->firstOfID = true;
}
$mod->changes = $result->changes;
$mod->id = $this->changedID;
$this->textNodes[$i]->modification = $mod;
$this->changes = $result->changes;
$this->changedIDUsed = true;
} else if ($this->changedIDUsed) {
++$this->changedID;
$this->changedIDUsed = false;
}
++$i;
++$j;
}
}
public function markAsDeleted($start, $end, $before) {
if ($end <= $start) {
return;
}
if ($before > 0 && $this->textNodes[$before - 1]->whiteAfter) {
$this->whiteAfterLastChangedPart = true;
} else {
$this->whiteAfterLastChangedPart = false;
}
for ($i = $start; $i < $end; ++$i) {
$mod = new Modification(Modification::REMOVED);
$mod->id = $this->deletedID;
// oldTextNodes is used here because we're going to move its deleted
// elements to this tree!
$this->oldTextNodes[$i]->modification = $mod;
}
$this->oldTextNodes[$start]->modification->firstOfID = true;
$root = $this->oldTextNodes[$start]->getLastCommonParent($this->oldTextNodes[$end-1])->parent;
$junk1 = $junk2 = null;
$deletedNodes = $root->getMinimalDeletedSet($this->deletedID, $junk1, $junk2);
//wfDebug("Minimal set of deleted nodes of size " . count($deletedNodes));
// Set prevLeaf to the leaf after which the old HTML needs to be
// inserted
if ($before > 0) {
$prevLeaf = $this->textNodes[$before - 1];
}
// Set nextLeaf to the leaf before which the old HTML needs to be
// inserted
if ($before < count($this->textNodes)) {
$nextLeaf = $this->textNodes[$before];
}
while (count($deletedNodes) > 0) {
if (isset($prevLeaf)) {
$prevResult = $prevLeaf->getLastCommonParent($deletedNodes[0]);
} else {
$prevResult = new LastCommonParentResult();
$prevResult->parent = $this->bodyNode;
$prevResult->indexInLastCommonParent = 0;
}
if (isset($nextleaf)) {
$nextResult = $nextLeaf->getLastCommonParent($deletedNodes[count($deletedNodes) - 1]);
} else {
$nextResult = new LastCommonParentResult();
$nextResult->parent = $this->bodyNode;
$nextResult->indexInLastCommonParent = $this->bodyNode->getNbChildren();
}
if ($prevResult->lastCommonParentDepth == $nextResult->lastCommonParentDepth) {
// We need some metric to choose which way to add-...
if ($deletedNodes[0]->parent === $deletedNodes[count($deletedNodes) - 1]->parent
&& $prevResult->parent === $nextResult->parent) {
// The difference is not in the parent
$prevResult->lastCommonParentDepth = $prevResult->lastCommonParentDepth + 1;
} else {
// The difference is in the parent, so compare them
// now THIS is tricky
$distancePrev = $deletedNodes[0]->parent->getMatchRatio($prevResult->parent);
$distanceNext = $deletedNodes[count($deletedNodes) - 1]->parent->getMatchRatio($nextResult->parent);
if ($distancePrev <= $distanceNext) {
$prevResult->lastCommonParentDepth = $prevResult->lastCommonParentDepth + 1;
} else {
$nextResult->lastCommonParentDepth = $nextResult->lastCommonParentDepth + 1;
}
}
}
if ($prevResult->lastCommonParentDepth > $nextResult->lastCommonParentDepth) {
// Inserting at the front
if ($prevResult->splittingNeeded) {
$prevLeaf->parent->splitUntil($prevResult->parent, $prevLeaf, true);
}
$prevLeaf = $deletedNodes[0]->copyTree();
unset($deletedNodes[0]);
$deletedNodes = array_values($deletedNodes);
$prevLeaf->setParent($prevResult->parent);
$prevResult->parent->addChildAbsolute($prevLeaf,$prevResult->indexInLastCommonParent + 1);
} else if ($prevResult->lastCommonParentDepth < $nextResult->lastCommonParentDepth) {
// Inserting at the back
if ($nextResult->splittingNeeded) {
$splitOccured = $nextLeaf->parent->splitUntil($nextResult->parent, $nextLeaf, false);
if ($splitOccured) {
// The place where to insert is shifted one place to the
// right
$nextResult->indexInLastCommonParent = $nextResult->indexInLastCommonParent + 1;
}
}
$nextLeaf = $deletedNodes[count(deletedNodes) - 1]->copyTree();
unset($deletedNodes[count(deletedNodes) - 1]);
$deletedNodes = array_values($deletedNodes);
$nextLeaf->setParent($nextResult->parent);
$nextResult->parent->addChildAbsolute($nextLeaf,$nextResult->indexInLastCommonParent);
} else {
throw new Exception("Uh?");
}
}
++$this->deletedID;
}
public function expandWhiteSpace() {
$this->bodyNode->expandWhiteSpace();
}
public function lengthNew(){
return count($this->textNodes);
}
public function lengthOld(){
return count($this->oldTextNodes);
}
}
class HTMLDiffer {
private $output;
function __construct($output) {
$this->output = $output;
}
function htmlDiff($from, $to) {
wfProfileIn( __METHOD__ );
// Create an XML parser
$xml_parser = xml_parser_create('');
$domfrom = new DomTreeBuilder();
// Set the functions to handle opening and closing tags
xml_set_element_handler($xml_parser, array($domfrom, "startElement"), array($domfrom, "endElement"));
// Set the function to handle blocks of character data
xml_set_character_data_handler($xml_parser, array($domfrom, "characters"));
//wfDebug('Parsing '.strlen($from)." characters worth of HTML\n");
if (!xml_parse($xml_parser, ''.Sanitizer::hackDocType().'