DOMPatchSupport.cpp [plain text]
#include "config.h"
#include "DOMPatchSupport.h"
#include "Attribute.h"
#include "DOMEditor.h"
#include "Document.h"
#include "DocumentFragment.h"
#include "HTMLDocument.h"
#include "HTMLDocumentParser.h"
#include "HTMLElement.h"
#include "HTMLHeadElement.h"
#include "HTMLNames.h"
#include "InspectorHistory.h"
#include "Node.h"
#include "XMLDocument.h"
#include "XMLDocumentParser.h"
#include <wtf/Deque.h>
#include <wtf/HashTraits.h>
#include <wtf/RefPtr.h>
#include <wtf/SHA1.h>
#include <wtf/text/Base64.h>
#include <wtf/text/CString.h>
namespace WebCore {
using HTMLNames::bodyTag;
using HTMLNames::headTag;
using HTMLNames::htmlTag;
struct DOMPatchSupport::Digest {
String sha1;
String attrsSHA1;
Node* node;
Vector<std::unique_ptr<Digest>> children;
};
DOMPatchSupport::DOMPatchSupport(DOMEditor& domEditor, Document& document)
: m_domEditor(domEditor)
, m_document(document)
{
}
void DOMPatchSupport::patchDocument(const String& markup)
{
RefPtr<Document> newDocument;
if (m_document.isHTMLDocument())
newDocument = HTMLDocument::create(nullptr, URL());
else if (m_document.isXHTMLDocument())
newDocument = XMLDocument::createXHTML(nullptr, URL());
else if (m_document.isSVGDocument())
newDocument = XMLDocument::create(nullptr, URL());
ASSERT(newDocument);
RefPtr<DocumentParser> parser;
if (newDocument->isHTMLDocument())
parser = HTMLDocumentParser::create(static_cast<HTMLDocument&>(*newDocument));
else
parser = XMLDocumentParser::create(*newDocument, nullptr);
parser->insert(markup); parser->finish();
parser->detach();
if (!m_document.documentElement())
return;
if (!newDocument->documentElement())
return;
std::unique_ptr<Digest> oldInfo = createDigest(*m_document.documentElement(), nullptr);
std::unique_ptr<Digest> newInfo = createDigest(*newDocument->documentElement(), &m_unusedNodesMap);
if (innerPatchNode(*oldInfo, *newInfo).hasException()) {
m_document.write(nullptr, markup);
m_document.close();
}
}
ExceptionOr<Node*> DOMPatchSupport::patchNode(Node& node, const String& markup)
{
if (node.isDocumentNode() || (node.parentNode() && node.parentNode()->isDocumentNode())) {
patchDocument(markup);
return nullptr;
}
Node* previousSibling = node.previousSibling();
RefPtr<DocumentFragment> fragment = DocumentFragment::create(m_document);
if (m_document.isHTMLDocument())
fragment->parseHTML(markup, node.parentElement() ? node.parentElement() : m_document.documentElement());
else
fragment->parseXML(markup, node.parentElement() ? node.parentElement() : m_document.documentElement());
auto* parentNode = node.parentNode();
Vector<std::unique_ptr<Digest>> oldList;
for (Node* child = parentNode->firstChild(); child; child = child->nextSibling())
oldList.append(createDigest(*child, nullptr));
Vector<std::unique_ptr<Digest>> newList;
for (Node* child = parentNode->firstChild(); child != &node; child = child->nextSibling())
newList.append(createDigest(*child, nullptr));
for (Node* child = fragment->firstChild(); child; child = child->nextSibling()) {
if (child->hasTagName(headTag) && !child->firstChild() && !markup.containsIgnoringASCIICase("</head>"))
continue; if (child->hasTagName(bodyTag) && !child->firstChild() && !markup.containsIgnoringASCIICase("</body>"))
continue; newList.append(createDigest(*child, &m_unusedNodesMap));
}
for (Node* child = node.nextSibling(); child; child = child->nextSibling())
newList.append(createDigest(*child, nullptr));
if (innerPatchChildren(*parentNode, oldList, newList).hasException()) {
auto result = m_domEditor.replaceChild(*parentNode, *fragment, node);
if (result.hasException())
return result.releaseException();
}
return previousSibling ? previousSibling->nextSibling() : parentNode->firstChild();
}
ExceptionOr<void> DOMPatchSupport::innerPatchNode(Digest& oldDigest, Digest& newDigest)
{
if (oldDigest.sha1 == newDigest.sha1)
return { };
auto& oldNode = *oldDigest.node;
auto& newNode = *newDigest.node;
if (newNode.nodeType() != oldNode.nodeType() || newNode.nodeName() != oldNode.nodeName())
return m_domEditor.replaceChild(*oldNode.parentNode(), newNode, oldNode);
if (oldNode.nodeValue() != newNode.nodeValue()) {
auto result = m_domEditor.setNodeValue(oldNode, newNode.nodeValue());
if (result.hasException())
return result.releaseException();
}
if (!is<Element>(oldNode))
return { };
auto& oldElement = downcast<Element>(oldNode);
auto& newElement = downcast<Element>(newNode);
if (oldDigest.attrsSHA1 != newDigest.attrsSHA1) {
if (oldElement.hasAttributesWithoutUpdate()) {
while (oldElement.attributeCount()) {
auto result = m_domEditor.removeAttribute(oldElement, oldElement.attributeAt(0).localName());
if (result.hasException())
return result.releaseException();
}
}
if (newElement.hasAttributesWithoutUpdate()) {
for (auto& attribute : newElement.attributesIterator()) {
auto result = m_domEditor.setAttribute(oldElement, attribute.name().localName(), attribute.value());
if (result.hasException())
return result.releaseException();
}
}
}
auto result = innerPatchChildren(oldElement, oldDigest.children, newDigest.children);
m_unusedNodesMap.remove(newDigest.sha1);
return result;
}
std::pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap>
DOMPatchSupport::diff(const Vector<std::unique_ptr<Digest>>& oldList, const Vector<std::unique_ptr<Digest>>& newList)
{
ResultMap newMap(newList.size());
ResultMap oldMap(oldList.size());
for (auto& result : oldMap) {
result.first = nullptr;
result.second = 0;
}
for (auto& result : newMap) {
result.first = nullptr;
result.second = 0;
}
for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[i]->sha1 == newList[i]->sha1; ++i) {
oldMap[i].first = oldList[i].get();
oldMap[i].second = i;
newMap[i].first = newList[i].get();
newMap[i].second = i;
}
for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[oldList.size() - i - 1]->sha1 == newList[newList.size() - i - 1]->sha1; ++i) {
size_t oldIndex = oldList.size() - i - 1;
size_t newIndex = newList.size() - i - 1;
oldMap[oldIndex].first = oldList[oldIndex].get();
oldMap[oldIndex].second = newIndex;
newMap[newIndex].first = newList[newIndex].get();
newMap[newIndex].second = oldIndex;
}
typedef HashMap<String, Vector<size_t>> DiffTable;
DiffTable newTable;
DiffTable oldTable;
for (size_t i = 0; i < newList.size(); ++i)
newTable.add(newList[i]->sha1, Vector<size_t>()).iterator->value.append(i);
for (size_t i = 0; i < oldList.size(); ++i)
oldTable.add(oldList[i]->sha1, Vector<size_t>()).iterator->value.append(i);
for (auto& newEntry : newTable) {
if (newEntry.value.size() != 1)
continue;
auto oldIt = oldTable.find(newEntry.key);
if (oldIt == oldTable.end() || oldIt->value.size() != 1)
continue;
newMap[newEntry.value[0]] = std::make_pair(newList[newEntry.value[0]].get(), oldIt->value[0]);
oldMap[oldIt->value[0]] = std::make_pair(oldList[oldIt->value[0]].get(), newEntry.value[0]);
}
for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
if (!newMap[i].first || newMap[i + 1].first)
continue;
size_t j = newMap[i].second + 1;
if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->sha1 == oldList[j]->sha1) {
newMap[i + 1] = std::make_pair(newList[i + 1].get(), j);
oldMap[j] = std::make_pair(oldList[j].get(), i + 1);
}
}
for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
continue;
size_t j = newMap[i].second - 1;
if (!oldMap[j].first && newList[i - 1]->sha1 == oldList[j]->sha1) {
newMap[i - 1] = std::make_pair(newList[i - 1].get(), j);
oldMap[j] = std::make_pair(oldList[j].get(), i - 1);
}
}
#ifdef DEBUG_DOM_PATCH_SUPPORT
dumpMap(oldMap, "OLD");
dumpMap(newMap, "NEW");
#endif
return std::make_pair(oldMap, newMap);
}
ExceptionOr<void> DOMPatchSupport::innerPatchChildren(ContainerNode& parentNode, const Vector<std::unique_ptr<Digest>>& oldList, const Vector<std::unique_ptr<Digest>>& newList)
{
auto resultMaps = diff(oldList, newList);
ResultMap& oldMap = resultMaps.first;
ResultMap& newMap = resultMaps.second;
Digest* oldHead = nullptr;
Digest* oldBody = nullptr;
HashMap<Digest*, Digest*> merges;
HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t>> usedNewOrdinals;
for (size_t i = 0; i < oldList.size(); ++i) {
if (oldMap[i].first) {
if (!usedNewOrdinals.contains(oldMap[i].second)) {
usedNewOrdinals.add(oldMap[i].second);
continue;
}
oldMap[i].first = nullptr;
oldMap[i].second = 0;
}
if (oldList[i]->node->hasTagName(headTag)) {
oldHead = oldList[i].get();
continue;
}
if (oldList[i]->node->hasTagName(bodyTag)) {
oldBody = oldList[i].get();
continue;
}
if (!m_unusedNodesMap.contains(oldList[i]->sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
size_t anchorAfter = i == oldMap.size() - 1 ? anchorCandidate + 1 : oldMap[i + 1].second;
if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList.size())
merges.set(newList[anchorCandidate].get(), oldList[i].get());
else {
auto result = removeChildAndMoveToNew(*oldList[i]);
if (result.hasException())
return result.releaseException();
}
} else {
auto result = removeChildAndMoveToNew(*oldList[i]);
if (result.hasException())
return result.releaseException();
}
}
HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t>> usedOldOrdinals;
for (size_t i = 0; i < newList.size(); ++i) {
if (!newMap[i].first)
continue;
size_t oldOrdinal = newMap[i].second;
if (usedOldOrdinals.contains(oldOrdinal)) {
newMap[i].first = nullptr;
newMap[i].second = 0;
continue;
}
usedOldOrdinals.add(oldOrdinal);
markNodeAsUsed(*newMap[i].first);
}
if (oldHead || oldBody) {
for (size_t i = 0; i < newList.size(); ++i) {
if (oldHead && newList[i]->node->hasTagName(headTag))
merges.set(newList[i].get(), oldHead);
if (oldBody && newList[i]->node->hasTagName(bodyTag))
merges.set(newList[i].get(), oldBody);
}
}
for (auto& merge : merges) {
auto result = innerPatchNode(*merge.value, *merge.key);
if (result.hasException())
return result.releaseException();
}
for (size_t i = 0; i < newMap.size(); ++i) {
if (newMap[i].first || merges.contains(newList[i].get()))
continue;
auto result = insertBeforeAndMarkAsUsed(parentNode, *newList[i], parentNode.traverseToChildAt(i));
if (result.hasException())
return result.releaseException();
}
for (size_t i = 0; i < oldMap.size(); ++i) {
if (!oldMap[i].first)
continue;
RefPtr<Node> node = oldMap[i].first->node;
auto* anchorNode = parentNode.traverseToChildAt(oldMap[i].second);
if (node == anchorNode)
continue;
if (node->hasTagName(bodyTag) || node->hasTagName(headTag))
continue; auto result = m_domEditor.insertBefore(parentNode, node.releaseNonNull(), anchorNode);
if (result.hasException())
return result.releaseException();
}
return { };
}
static void addStringToSHA1(SHA1& sha1, const String& string)
{
CString cString = string.utf8();
sha1.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
}
std::unique_ptr<DOMPatchSupport::Digest> DOMPatchSupport::createDigest(Node& node, UnusedNodesMap* unusedNodesMap)
{
auto digest = std::make_unique<Digest>();
digest->node = &node;
SHA1 sha1;
auto nodeType = node.nodeType();
sha1.addBytes(reinterpret_cast<const uint8_t*>(&nodeType), sizeof(nodeType));
addStringToSHA1(sha1, node.nodeName());
addStringToSHA1(sha1, node.nodeValue());
if (node.nodeType() == Node::ELEMENT_NODE) {
Node* child = node.firstChild();
while (child) {
std::unique_ptr<Digest> childInfo = createDigest(*child, unusedNodesMap);
addStringToSHA1(sha1, childInfo->sha1);
child = child->nextSibling();
digest->children.append(WTFMove(childInfo));
}
auto& element = downcast<Element>(node);
if (element.hasAttributesWithoutUpdate()) {
SHA1 attrsSHA1;
for (auto& attribute : element.attributesIterator()) {
addStringToSHA1(attrsSHA1, attribute.name().toString());
addStringToSHA1(attrsSHA1, attribute.value());
}
SHA1::Digest attrsHash;
attrsSHA1.computeHash(attrsHash);
digest->attrsSHA1 = base64Encode(attrsHash.data(), 10);
addStringToSHA1(sha1, digest->attrsSHA1);
}
}
SHA1::Digest hash;
sha1.computeHash(hash);
digest->sha1 = base64Encode(hash.data(), 10);
if (unusedNodesMap)
unusedNodesMap->add(digest->sha1, digest.get());
return digest;
}
ExceptionOr<void> DOMPatchSupport::insertBeforeAndMarkAsUsed(ContainerNode& parentNode, Digest& digest, Node* anchor)
{
ASSERT(digest.node);
auto result = m_domEditor.insertBefore(parentNode, *digest.node, anchor);
markNodeAsUsed(digest);
return result;
}
ExceptionOr<void> DOMPatchSupport::removeChildAndMoveToNew(Digest& oldDigest)
{
Ref<Node> oldNode = *oldDigest.node;
ASSERT(oldNode->parentNode());
auto result = m_domEditor.removeChild(*oldNode->parentNode(), oldNode);
if (result.hasException())
return result.releaseException();
auto it = m_unusedNodesMap.find(oldDigest.sha1);
if (it != m_unusedNodesMap.end()) {
auto& newDigest = *it->value;
auto& newNode = *newDigest.node;
auto result = m_domEditor.replaceChild(*newNode.parentNode(), oldNode.get(), newNode);
if (result.hasException())
return result.releaseException();
newDigest.node = oldNode.ptr();
markNodeAsUsed(newDigest);
return { };
}
for (auto& child : oldDigest.children) {
auto result = removeChildAndMoveToNew(*child);
if (result.hasException())
return result.releaseException();
}
return { };
}
void DOMPatchSupport::markNodeAsUsed(Digest& digest)
{
Deque<Digest*> queue;
queue.append(&digest);
while (!queue.isEmpty()) {
auto& first = *queue.takeFirst();
m_unusedNodesMap.remove(first.sha1);
for (auto& child : first.children)
queue.append(child.get());
}
}
#ifdef DEBUG_DOM_PATCH_SUPPORT
static String nodeName(Node* node)
{
if (node->document().isXHTMLDocument())
return node->nodeName();
return node->nodeName().convertToASCIILowercase();
}
void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name)
{
fprintf(stderr, "\n\n");
for (size_t i = 0; i < map.size(); ++i)
fprintf(stderr, "%s[%lu]: %s (%p) - [%lu]\n", name.utf8().data(), i, map[i].first ? nodeName(map[i].first->m_node).utf8().data() : "", map[i].first, map[i].second);
}
#endif
}