<?php

/** Copyright (C) 2008 Guy Van den Broeck <guy@guyvdb.eu>
 *
 * 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/
 * 
 * @ingroup DifferenceEngine
 */

/*
  @internal revision by TestLink Dev Team
  20110108 - franciscom - endElement() $img seems to be useless
*/

/**
 * When detecting the last common parent of two nodes, all results are stored as
 * a LastCommonParentResult.
 */

include_once 'Diff.php'; 
include_once 'Nodes.php';
include_once 'Sanitizer.php';
include_once 'Xml.php';

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();
        HTMLDiffer::diffDebug( count($this->textNodes) . " text nodes in document.\n" );
    }

    public function startElement($parser, $name, /*array*/ $attributes) {
        if (strcasecmp($name, 'body') != 0) {
            HTMLDiffer::diffDebug( "Starting $name node.\n" );
            $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) {
            HTMLDiffer::diffDebug( "Ending $name node.\n");
            if (0 == strcasecmp($name,'img') ||
                0 == strcasecmp($name,'br') ||
                0 == strcasecmp($name,'hr')) {
                // Insert a dummy leaf for the element
                $tag = new VisibleTagNode($this->currentParent, $name, $this->currentParent->attributes);
                $this->currentParent->children[] = $tag;
                // 20110108 - franciscom - this generates warning on event viewer,
                // and seems that $img is never used 
                // $img->whiteBefore = $this->whiteSpaceBeforeThis;
                $this->lastSibling = $tag;
                $this->textNodes[] = $tag;
            }
            $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, htmlentities($data,ENT_NOQUOTES,'UTF-8'), -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 ) {
                $mod = new Modification(Modification::CHANGED);

                if (!$this->changedIDUsed) {
                    $mod->firstOfID = true;
                } else if (!is_null( $result ) && $result !== $this->changes) {
                    ++$this->changedID;
                    $mod->firstOfID = true;
                }

                $mod->changes = $result;
                $mod->id = $this->changedID;

                $this->textNodes[$i]->modification = $mod;
                $this->changes = $result;
                $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);

        HTMLDiffer::diffDebug( "Minimal set of deleted nodes of size " . count($deletedNodes) . "\n" );

        // 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 = -1;
            }
            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);
            }
        }
        ++$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 static $debug = '';
    private $output;

    function htmlDiff($from, $to) {

        // 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"));

        HTMLDiffer::diffDebug( "Parsing " . strlen($from) . " characters worth of HTML\n" );
        if (!xml_parse($xml_parser, '<?xml version="1.0" encoding="UTF-8"?>'.Sanitizer::hackDocType().'<body>', false)
                    || !xml_parse($xml_parser, $from, false)
                    || !xml_parse($xml_parser, '</body>', true)){
            $error = xml_error_string(xml_get_error_code($xml_parser));
            $line = xml_get_current_line_number($xml_parser);
            $col = xml_get_current_column_number($xml_parser);
            HTMLDiffer::diffDebug( "XML error: $error at line $line and column $col\n" );
        }
        xml_parser_free($xml_parser);
        unset($from);

        $xml_parser = xml_parser_create('');

        $domto = new DomTreeBuilder();

        // Set the functions to handle opening and closing tags
        xml_set_element_handler($xml_parser, array($domto, "startElement"), array($domto, "endElement"));

        // Set the function to handle blocks of character data
        xml_set_character_data_handler($xml_parser, array($domto, "characters"));

        HTMLDiffer::diffDebug( "Parsing " . strlen($to) . " characters worth of HTML\n" );
        if (!xml_parse($xml_parser, '<?xml version="1.0" encoding="UTF-8"?>'.Sanitizer::hackDocType().'<body>', false)
        || !xml_parse($xml_parser, $to, false)
        || !xml_parse($xml_parser, '</body>', true)){
            $error = xml_error_string(xml_get_error_code($xml_parser));
            $line = xml_get_current_line_number($xml_parser);
            $col = xml_get_current_column_number($xml_parser);
            HTMLDiffer::diffDebug( "XML error: $error at line $line and column $col\n" );
        }
        xml_parser_free($xml_parser);
        unset($to);

        $diffengine = new WikiDiff3();
        $differences = $this->preProcess($diffengine->diff_range($domfrom->getDiffLines(), $domto->getDiffLines()));
        
        unset($xml_parser, $diffengine);

        $textNodeDiffer = new TextNodeDiffer($domto, $domfrom);

        $currentIndexLeft = 0;
        $currentIndexRight = 0;
        foreach ($differences as &$d) {
            if ($d->leftstart > $currentIndexLeft) {
                $textNodeDiffer->handlePossibleChangedPart($currentIndexLeft, $d->leftstart,
                    $currentIndexRight, $d->rightstart);
            }
            if ($d->leftlength > 0) {
                $textNodeDiffer->markAsDeleted($d->leftstart, $d->leftend, $d->rightstart);
            }
            $textNodeDiffer->markAsNew($d->rightstart, $d->rightend);

            $currentIndexLeft = $d->leftend;
            $currentIndexRight = $d->rightend;
        }
        $oldLength = $textNodeDiffer->lengthOld();
        if ($currentIndexLeft < $oldLength) {
            $textNodeDiffer->handlePossibleChangedPart($currentIndexLeft, $oldLength, $currentIndexRight, $textNodeDiffer->lengthNew());
        }
        $textNodeDiffer->expandWhiteSpace();
        
        $output = new HTMLOutput('htmldiff');

        //return $output->parse($textNodeDiffer->bodyNode);
        return array($output->parse($textNodeDiffer->bodyNode), count($differences));
    }

    private function preProcess(/*array*/ $differences) {
        $newRanges = array();

        $nbDifferences = count($differences);
        for ($i = 0; $i < $nbDifferences; ++$i) {
            $leftStart = $differences[$i]->leftstart;
            $leftEnd = $differences[$i]->leftend;
            $rightStart = $differences[$i]->rightstart;
            $rightEnd = $differences[$i]->rightend;

            $leftLength = $leftEnd - $leftStart;
            $rightLength = $rightEnd - $rightStart;

            while ($i + 1 < $nbDifferences && self::score($leftLength,
                        $differences[$i + 1]->leftlength,
                        $rightLength,
                        $differences[$i + 1]->rightlength)
                    > ($differences[$i + 1]->leftstart - $leftEnd)) {
                $leftEnd = $differences[$i + 1]->leftend;
                $rightEnd = $differences[$i + 1]->rightend;
                $leftLength = $leftEnd - $leftStart;
                $rightLength = $rightEnd - $rightStart;
                ++$i;
            }
            $newRanges[] = new RangeDifference($leftStart, $leftEnd, $rightStart, $rightEnd);
        }
        return $newRanges;
    }

    /**
     * Heuristic to merge differences for readability.
     */
    public static function score($ll, $nll, $rl, $nrl) {
        if (($ll == 0 && $nll == 0)
                || ($rl == 0 && $nrl == 0)) {
            return 0;
        }
        $numbers = array($ll, $nll, $rl, $nrl);
        $d = 0;
        foreach ($numbers as &$number) {
            while ($number > 3) {
                $d += 3;
                $number -= 3;
                $number *= 0.5;
            }
            $d += $number;

        }
        return $d / (1.5 * count($numbers));
    }

    /**
     * Add to debug output
     * @param string $str Debug output
     */
    public static function diffDebug( $str ) {
        self :: $debug .= $str;
    }
    
    /**
     * Get debug output
     * @return string
     */
    public static function getDebugOutput() {
        return self :: $debug;
    }

}

class TextOnlyComparator {

    public $leafs = array();

    function __construct(TagNode $tree) {
        $this->addRecursive($tree);
        $this->leafs = array_map(array('TextNode','toDiffLine'), $this->leafs);
    }

    private function addRecursive(TagNode $tree) {
        foreach ($tree->children as &$child) {
            if ($child instanceof TagNode) {
                $this->addRecursive($child);
            } else if ($child instanceof TextNode) {
                $this->leafs[] = $child;
            }
        }
    }

    public function getMatchRatio(TextOnlyComparator $other) {
        $nbOthers = count($other->leafs);
        $nbThis = count($this->leafs);
        if($nbOthers == 0 || $nbThis == 0){
            return -log(0);
        }

        $diffengine = new WikiDiff3(25000, 1.35);
        $diffengine->diff($this->leafs, $other->leafs);

        $lcsLength = $diffengine->getLcsLength();

        $distanceThis = $nbThis-$lcsLength;

        return (2.0 - $lcsLength/$nbOthers - $lcsLength/$nbThis) / 2.0;
    }
}

/**
 * A comparator used when calculating the difference in ancestry of two Nodes.
 */
class AncestorComparator {

    public $ancestors;
    public $ancestorsText;

    function __construct(/*array*/ $ancestors) {
        $this->ancestors = $ancestors;
        $this->ancestorsText = array_map(array('TagNode','toDiffLine'), $ancestors);
    }

    public $compareTxt = "";

    public function getResult(AncestorComparator $other) {

        $diffengine = new WikiDiff3(10000, 1.35);
        $differences = $diffengine->diff_range($other->ancestorsText,$this->ancestorsText);

        if (count($differences) == 0){
            return null;
        }
        $changeTxt = new ChangeTextGenerator($this, $other);

        return $changeTxt->getChanged($differences)->toString();;
    }
}

class ChangeTextGenerator {

    private $ancestorComparator;
    private $other;

    private $factory;

    function __construct(AncestorComparator $ancestorComparator, AncestorComparator $other) {
        $this->ancestorComparator = $ancestorComparator;
        $this->other = $other;
        $this->factory = new TagToStringFactory();
    }

    public function getChanged(/*array*/ $differences) {
        $txt = new ChangeText;
        $rootlistopened = false;
        if (count($differences) > 1) {
            $txt->addHtml('<ul class="changelist">');
            $rootlistopened = true;
        }
        $nbDifferences = count($differences);
        for ($j = 0; $j < $nbDifferences; ++$j) {
            $d = $differences[$j];
            $lvl1listopened = false;
            if ($rootlistopened) {
                $txt->addHtml('<li>');
            }
            if ($d->leftlength + $d->rightlength > 1) {
                $txt->addHtml('<ul class="changelist">');
                $lvl1listopened = true;
            }
            // left are the old ones
            for ($i = $d->leftstart; $i < $d->leftend; ++$i) {
                if ($lvl1listopened){
                    $txt->addHtml('<li>');
                }
                // add a bullet for a old tag
                $this->addTagOld($txt, $this->other->ancestors[$i]);
                if ($lvl1listopened){
                    $txt->addHtml('</li>');
                }
            }
            // right are the new ones
            for ($i = $d->rightstart; $i < $d->rightend; ++$i) {
                if ($lvl1listopened){
                    $txt->addHtml('<li>');
                }
                // add a bullet for a new tag
                $this->addTagNew($txt, $this->ancestorComparator->ancestors[$i]);

                if ($lvl1listopened){
                    $txt->addHtml('</li>');
                }
            }
            if ($lvl1listopened) {
                $txt->addHtml('</ul>');
            }
            if ($rootlistopened) {
                $txt->addHtml('</li>');
            }
        }
        if ($rootlistopened) {
            $txt->addHtml('</ul>');
        }
        return $txt;
    }

    private function addTagOld(ChangeText $txt, TagNode $ancestor) {
        $this->factory->create($ancestor)->getRemovedDescription($txt);
    }

    private function addTagNew(ChangeText $txt, TagNode $ancestor) {
        $this->factory->create($ancestor)->getAddedDescription($txt);
    }
}

class ChangeText {

    private $txt = "";

    public function addHtml($s) {
        $this->txt .= $s;
    }

    public function toString() {
        return $this->txt;
    }
}

class TagToStringFactory {

    private static $containerTags = array('html', 'body', 'p', 'blockquote',
        'h1', 'h2', 'h3', 'h4', 'h5', 'pre', 'div', 'ul', 'ol', 'li',
        'table', 'tbody', 'tr', 'td', 'th', 'br', 'hr', 'code', 'dl',
        'dt', 'dd', 'input', 'form', 'img', 'span', 'a');

    private static $styleTags = array('i', 'b', 'strong', 'em', 'font',
        'big', 'del', 'tt', 'sub', 'sup', 'strike');

    const MOVED = 1;
    const STYLE = 2;
    const UNKNOWN = 4;

    public function create(TagNode $node) {
        $sem = $this->getChangeSemantic($node->qName);
        if (strcasecmp($node->qName,'a') == 0) {
            return new AnchorToString($node, $sem);
        }
        if (strcasecmp($node->qName,'img') == 0 ||
            strcasecmp($node->qName,'br') == 0 ||
            strcasecmp($node->qName,'hr') == 0) {
            return new NoContentTagToString($node, $sem);
        }
        return new TagToString($node, $sem);
    }

    protected function getChangeSemantic($qname) {
        if (in_array(strtolower($qname),self::$containerTags)) {
            return self::MOVED;
        }
        if (in_array(strtolower($qname),self::$styleTags)) {
            return self::STYLE;
        }
        return self::UNKNOWN;
    }
}

class TagToString {

    protected $node;

    protected $sem;

    function __construct(TagNode $node, $sem) {
        $this->node = $node;
        $this->sem = $sem;
    }

    public function getRemovedDescription(ChangeText $txt) {
        $tagDescription = "&lt;" . $this->node->qName . "&gt;";
        if ($this->sem == TagToStringFactory::MOVED) {
            $txt->addHtml( 'Moved out of: ' . $tagDescription);
        } else if ($this->sem == TagToStringFactory::STYLE) {
            $txt->addHtml( 'Style removed: <' . $this->node->qName . '>' . $tagDescription . '</' . $this->node->qName . '>');
        } else {
            $txt->addHtml( 'Removed: ' . $tagDescription);
        }
        $this->addAttributes($txt, $this->node->attributes);
        $txt->addHtml('.');
    }

    public function getAddedDescription(ChangeText $txt) {
        $tagDescription = "&lt;" . $this->node->qName . "&gt;";
        if ($this->sem == TagToStringFactory::MOVED) {
            $txt->addHtml( 'Moved into: ' . $tagDescription);
        } else if ($this->sem == TagToStringFactory::STYLE) {
            $txt->addHtml( 'Style added: <' . $this->node->qName . '>' . $tagDescription . '</' . $this->node->qName . '>');
        } else {
            $txt->addHtml( 'Added: ' . $tagDescription);
        }
        $this->addAttributes($txt, $this->node->attributes);
        $txt->addHtml('.');
    }

    protected function addAttributes(ChangeText $txt, array $attributes) {
        if (count($attributes) < 1) {
            return;
        }

        $keys = array_keys($attributes);
        $txt->addHtml(Sanitizer::normalizeCharReferences( ' with "' . $keys[0] . '" attribute as "' . $attributes[$keys[0]] . '"'));

        $nbAttributes_min_1 = count($attributes)-1;
        for ($i=1;$i<$nbAttributes_min_1;$i++) {
            $key = $keys[$i];
            $attr = $attributes[$key];
            $txt->addHtml(Sanitizer::normalizeCharReferences( ', with "' . $key . '" attribute as "' . $attr . '"'));
        }

        if ($nbAttributes_min_1 > 1) {
            $txt->addHtml(Sanitizer::normalizeCharReferences( ' and with "' . $keys[$nbAttributes_min_1] . '" attribute as "' . $attributes[$keys[$nbAttributes_min_1]] . '"'));
        }
    }

}

class NoContentTagToString extends TagToString {

    function __construct(TagNode $node, $sem) {
        parent::__construct($node, $sem);
    }

    public function getAddedDescription(ChangeText $txt) {
        $tagDescription = "&lt;" . $this->node->qName . "&gt;";
        $txt->addHtml( 'Changed to ' . $tagDescription );
        $this->addAttributes($txt, $this->node->attributes);
        $txt->addHtml('.');
    }

    public function getRemovedDescription(ChangeText $txt) {
        $tagDescription = "&lt;" . $this->node->qName . "&gt;";
        $txt->addHtml( 'Changed from ' . $tagDescription );
        $this->addAttributes($txt, $this->node->attributes);
        $txt->addHtml('.');
    }
}

class AnchorToString extends TagToString {

    function __construct(TagNode $node, $sem) {
        parent::__construct($node, $sem);
    }

    protected function addAttributes(ChangeText $txt, array $attributes) {
        if (array_key_exists('href', $attributes)) {
            $txt->addHtml(' with destination ' . htmlspecialchars($attributes['href']));
            unset($attributes['href']);
        }
        parent::addAttributes($txt, $attributes);
    }
}

/**
 * Takes a branch root and creates an HTML file for it.
 */
class HTMLOutput{

    private $prefix;
    private $handler;

    function __construct($prefix) {
        $this->prefix = $prefix;
        $this->handler = new ContentHandler();
    }

    public function parse(TagNode $node) {
        $handler = $this->handler;

        if (strcasecmp($node->qName, 'img') != 0 &&
            strcasecmp($node->qName, 'br') != 0 &&
            strcasecmp($node->qName, 'hr') != 0 &&
            strcasecmp($node->qName, 'body') != 0) {
            $handler->startElement($node->qName, $node->attributes);
        }

        $newStarted = false;
        $remStarted = false;
        $changeStarted = false;
        $changeTXT = '';

        foreach ($node->children as &$child) {
            if ($child instanceof TagNode) {
                if ($newStarted) {
                    $handler->endElement('span');
                    $newStarted = false;
                } else if ($changeStarted) {
                    $handler->endElement('span');
                    $changeStarted = false;
                } else if ($remStarted) {
                    $handler->endElement('span');
                    $remStarted = false;
                }
                $this->parse($child);
            } else if ($child instanceof TextNode) {
                $mod = $child->modification;

                if ($newStarted && ($mod->type != Modification::ADDED || $mod->firstOfID)) {
                    $handler->endElement('span');
                    $newStarted = false;
                } else if ($changeStarted && ($mod->type != Modification::CHANGED
                        || $mod->changes != $changeTXT || $mod->firstOfID)) {
                    $handler->endElement('span');
                    $changeStarted = false;
                } else if ($remStarted && ($mod->type != Modification::REMOVED || $mod ->firstOfID)) {
                    $handler->endElement('span');
                    $remStarted = false;
                }

                // no else because a removed part can just be closed and a new
                // part can start
                if (!$newStarted && $mod->type == Modification::ADDED) {
                    $attrs = array('class' => 'diff-html-added');
                    if ($mod->firstOfID) {
                        $attrs['id'] = "added-{$this->prefix}-{$mod->id}";
                    }
                    $handler->startElement('span', $attrs);
                    $newStarted = true;
                } else if (!$changeStarted && $mod->type == Modification::CHANGED) {
                    $attrs = array('class' => 'diff-html-changed');
                    if ($mod->firstOfID) {
                        $attrs['id'] = "changed-{$this->prefix}-{$mod->id}";
                    }
                    $handler->startElement('span', $attrs);

                    //tooltip
                    $handler->startElement('span', array('class' => 'tip'));
                    $handler->html($mod->changes);
                    $handler->endElement('span');

                    $changeStarted = true;
                    $changeTXT = $mod->changes;
                } else if (!$remStarted && $mod->type == Modification::REMOVED) {
                    $attrs = array('class'=>'diff-html-removed');
                    if ($mod->firstOfID) {
                        $attrs['id'] = "removed-{$this->prefix}-{$mod->id}";
                    }
                    $handler->startElement('span', $attrs);
                    $remStarted = true;
                }

                $chars = $child->text;

                if ($child instanceof VisibleTagNode) {
                    if (strcasecmp($child->qName, 'br') == 0 && ($newStarted || $changeStarted || $remStarted)) {
                        $handler->characters('&nbsp;');
                    }
                    $this->handler->element($child->qName, $child->attributes);
                } else {
                    $handler->characters($chars);
                }
            }
        }

        if ($newStarted) {
            $handler->endElement('span');
            $newStarted = false;
        } else if ($changeStarted) {
            $handler->endElement('span');
            $changeStarted = false;
        } else if ($remStarted) {
            $handler->endElement('span');
            $remStarted = false;
        }

        if (strcasecmp($node->qName, 'img') != 0 &&
            strcasecmp($node->qName, 'br') != 0 &&
            strcasecmp($node->qName, 'hr') != 0 &&
            strcasecmp($node->qName, 'body') != 0) {
            $handler->endElement($node->qName);
        }
        
        return $handler->getContent();
    }

}

class ContentHandler {

    private $string;

    function __construct() {
        $this->string = '';
    }

    function startElement($qname, /*array*/ $arguments) {
        $this->string .= Xml::openElement($qname, $arguments);
    }

    function endElement($qname){
        $this->string .= Xml::closeElement($qname);
    }

    function element($qname, /*array*/ $arguments) {
        $this->string .= Xml::element($qname, $arguments);
    }    
    
    function characters($chars){
        $this->string .= $chars;
    }

    function html($html){
        $this->string .= $html;
    }
    
    function getContent() {
        return $this->string;
    }

}