4113b3d81d2ff4bf6875ae13a2acb873b932d78a
[WebKit-https.git] / Source / WebCore / inspector / DOMPatchSupport.cpp
1 /*
2  * Copyright (C) 2012 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are
6  * met:
7  *
8  *     * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *     * Redistributions in binary form must reproduce the above
11  * copyright notice, this list of conditions and the following disclaimer
12  * in the documentation and/or other materials provided with the
13  * distribution.
14  *     * Neither the name of Google Inc. nor the names of its
15  * contributors may be used to endorse or promote products derived from
16  * this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31 #include "config.h"
32 #include "DOMPatchSupport.h"
33
34 #if ENABLE(INSPECTOR)
35
36 #include "Attribute.h"
37 #include "Base64.h"
38 #include "Document.h"
39 #include "DocumentFragment.h"
40 #include "HTMLDocument.h"
41 #include "HTMLDocumentParser.h"
42 #include "HTMLElement.h"
43 #include "HTMLHeadElement.h"
44 #include "HTMLNames.h"
45 #include "Node.h"
46
47 #include <wtf/Deque.h>
48 #include <wtf/HashTraits.h>
49 #include <wtf/RefPtr.h>
50 #include <wtf/SHA1.h>
51 #include <wtf/text/CString.h>
52
53 using namespace std;
54
55 namespace WebCore {
56
57 using HTMLNames::bodyTag;
58 using HTMLNames::headTag;
59 using HTMLNames::htmlTag;
60
61 struct DOMPatchSupport::Digest {
62     explicit Digest(Node* node) : m_node(node) { }
63
64     String m_sha1;
65     String m_attrsSHA1;
66     Node* m_node;
67     Vector<OwnPtr<Digest> > m_children;
68 };
69
70 DOMPatchSupport::DOMPatchSupport(Document* document) : m_document(document) { }
71
72 DOMPatchSupport::~DOMPatchSupport() { }
73
74 void DOMPatchSupport::patchDocument(const String& markup)
75 {
76     RefPtr<HTMLDocument> newDocument = HTMLDocument::create(0, KURL());
77     RefPtr<DocumentParser> parser = HTMLDocumentParser::create(newDocument.get(), false);
78     parser->insert(markup); // Use insert() so that the parser will not yield.
79     parser->finish();
80     parser->detach();
81
82     ExceptionCode ec = 0;
83     OwnPtr<Digest> oldInfo = createDigest(m_document->documentElement(), 0);
84     OwnPtr<Digest> newInfo = createDigest(newDocument->documentElement(), &m_unusedNodesMap);
85     innerPatchNode(oldInfo.get(), newInfo.get(), ec);
86
87     if (ec) {
88         // Fall back to rewrite.
89         m_document->write(markup);
90         m_document->close();
91     }
92 }
93
94 Node* DOMPatchSupport::patchNode(Node* node, const String& markup, ExceptionCode& ec)
95 {
96     // Don't parse <html> as a fragment.
97     if (node->isDocumentNode() || (node->parentNode() && node->parentNode()->isDocumentNode())) {
98         patchDocument(markup);
99         return 0;
100     }
101
102     Node* previousSibling = node->previousSibling();
103     RefPtr<DocumentFragment> fragment = DocumentFragment::create(m_document);
104     fragment->parseHTML(markup, node->parentElement() ? node->parentElement() : m_document->documentElement());
105
106     // Compose the old list.
107     ContainerNode* parentNode = node->parentNode();
108     Vector<OwnPtr<Digest> > oldList;
109     for (Node* child = parentNode->firstChild(); child; child = child->nextSibling())
110         oldList.append(createDigest(child, 0));
111
112     // Compose the new list.
113     String markupCopy = markup;
114     markupCopy.makeLower();
115     Vector<OwnPtr<Digest> > newList;
116     for (Node* child = parentNode->firstChild(); child != node; child = child->nextSibling())
117         newList.append(createDigest(child, 0));
118     for (Node* child = fragment->firstChild(); child; child = child->nextSibling()) {
119         if (child->hasTagName(headTag) && !child->firstChild() && markupCopy.find("</head>") == notFound)
120             continue; // HTML5 parser inserts empty <head> tag whenever it parses <body>
121         if (child->hasTagName(bodyTag) && !child->firstChild() && markupCopy.find("</body>") == notFound)
122             continue; // HTML5 parser inserts empty <body> tag whenever it parses </head>
123         newList.append(createDigest(child, &m_unusedNodesMap));
124     }
125     for (Node* child = node->nextSibling(); child; child = child->nextSibling())
126         newList.append(createDigest(child, 0));
127
128     innerPatchChildren(parentNode, oldList, newList, ec);
129     if (ec) {
130         // Fall back to total replace.
131         ec = 0;
132         parentNode->replaceChild(fragment.release(), node, ec);
133         if (ec)
134             return 0;
135     }
136     return previousSibling ? previousSibling->nextSibling() : parentNode->firstChild();
137 }
138
139 void DOMPatchSupport::innerPatchNode(Digest* oldDigest, Digest* newDigest, ExceptionCode& ec)
140 {
141     if (oldDigest->m_sha1 == newDigest->m_sha1)
142         return;
143
144     Node* oldNode = oldDigest->m_node;
145     Node* newNode = newDigest->m_node;
146
147     if (newNode->nodeType() != oldNode->nodeType() || newNode->nodeName() != oldNode->nodeName()) {
148         oldNode->parentNode()->replaceChild(newNode, oldNode, ec);
149         return;
150     }
151
152     if (oldNode->nodeValue() != newNode->nodeValue())
153         oldNode->setNodeValue(newNode->nodeValue(), ec);
154     if (ec)
155         return;
156
157     if (oldNode->nodeType() != Node::ELEMENT_NODE)
158         return;
159
160     // Patch attributes
161     Element* oldElement = static_cast<Element*>(oldNode);
162     Element* newElement = static_cast<Element*>(newNode);
163     if (oldDigest->m_attrsSHA1 != newDigest->m_attrsSHA1) {
164         // FIXME: Create a function in Element for removing all properties. Take in account whether did/willModifyAttribute are important.
165         if (oldElement->hasAttributesWithoutUpdate()) {
166             while (oldElement->attributeCount())
167                 oldElement->removeAttribute(0);
168         }
169
170         // FIXME: Create a function in Element for copying properties. setAttributesFromElement() is close but not enough for this case.
171         if (newElement->hasAttributesWithoutUpdate()) {
172             size_t numAttrs = newElement->attributeCount();
173             for (size_t i = 0; i < numAttrs; ++i) {
174                 const Attribute* attribute = newElement->attributeItem(i);
175                 oldElement->setAttribute(attribute->name(), attribute->value());
176             }
177         }
178     }
179
180     innerPatchChildren(oldElement, oldDigest->m_children, newDigest->m_children, ec);
181     m_unusedNodesMap.remove(newDigest->m_sha1);
182 }
183
184 pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap>
185 DOMPatchSupport::diff(const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList)
186 {
187     ResultMap newMap(newList.size());
188     ResultMap oldMap(oldList.size());
189
190     for (size_t i = 0; i < oldMap.size(); ++i) {
191         oldMap[i].first = 0;
192         oldMap[i].second = 0;
193     }
194
195     for (size_t i = 0; i < newMap.size(); ++i) {
196         newMap[i].first = 0;
197         newMap[i].second = 0;
198     }
199
200     // Trim head and tail.
201     for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[i]->m_sha1 == newList[i]->m_sha1; ++i) {
202         oldMap[i].first = oldList[i].get();
203         oldMap[i].second = i;
204         newMap[i].first = newList[i].get();
205         newMap[i].second = i;
206     }
207     for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[oldList.size() - i - 1]->m_sha1 == newList[newList.size() - i - 1]->m_sha1; ++i) {
208         size_t oldIndex = oldList.size() - i - 1;
209         size_t newIndex = newList.size() - i - 1;
210         oldMap[oldIndex].first = oldList[oldIndex].get();
211         oldMap[oldIndex].second = newIndex;
212         newMap[newIndex].first = newList[newIndex].get();
213         newMap[newIndex].second = oldIndex;
214     }
215
216     typedef HashMap<String, Vector<size_t> > DiffTable;
217     DiffTable newTable;
218     DiffTable oldTable;
219
220     for (size_t i = 0; i < newList.size(); ++i) {
221         DiffTable::iterator it = newTable.add(newList[i]->m_sha1, Vector<size_t>()).first;
222         it->second.append(i);
223     }
224
225     for (size_t i = 0; i < oldList.size(); ++i) {
226         DiffTable::iterator it = oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).first;
227         it->second.append(i);
228     }
229
230     for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) {
231         if (newIt->second.size() != 1)
232             continue;
233
234         DiffTable::iterator oldIt = oldTable.find(newIt->first);
235         if (oldIt == oldTable.end() || oldIt->second.size() != 1)
236             continue;
237
238         newMap[newIt->second[0]] = make_pair(newList[newIt->second[0]].get(), oldIt->second[0]);
239         oldMap[oldIt->second[0]] = make_pair(oldList[oldIt->second[0]].get(), newIt->second[0]);
240     }
241
242     for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
243         if (!newMap[i].first || newMap[i + 1].first)
244             continue;
245
246         size_t j = newMap[i].second + 1;
247         if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == oldList[j]->m_sha1) {
248             newMap[i + 1] = make_pair(newList[i + 1].get(), j);
249             oldMap[j] = make_pair(oldList[j].get(), i + 1);
250         }
251     }
252
253     for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
254         if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
255             continue;
256
257         size_t j = newMap[i].second - 1;
258         if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) {
259             newMap[i - 1] = make_pair(newList[i - 1].get(), j);
260             oldMap[j] = make_pair(oldList[j].get(), i - 1);
261         }
262     }
263
264 #ifdef DEBUG_DOM_PATCH_SUPPORT
265     dumpMap(oldMap, "OLD");
266     dumpMap(newMap, "NEW");
267 #endif
268
269     return make_pair(oldMap, newMap);
270 }
271
272 void DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList, ExceptionCode& ec)
273 {
274     pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList);
275     ResultMap& oldMap = resultMaps.first;
276     ResultMap& newMap = resultMaps.second;
277
278     Digest* oldHead = 0;
279     Digest* oldBody = 0;
280
281     // 1. First strip everything except for the nodes that retain. Collect pending merges.
282     HashMap<Digest*, Digest*> merges;
283     HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t> > usedNewOrdinals;
284     for (size_t i = 0; i < oldList.size(); ++i) {
285         if (oldMap[i].first) {
286             if (!usedNewOrdinals.contains(oldMap[i].second)) {
287                 usedNewOrdinals.add(oldMap[i].second);
288                 continue;
289             }
290             oldMap[i].first = 0;
291             oldMap[i].second = 0;
292         }
293
294         // Always match <head> and <body> tags with each other - we can't remove them from the DOM
295         // upon patching.
296         if (oldList[i]->m_node->hasTagName(headTag)) {
297             oldHead = oldList[i].get();
298             continue;
299         }
300         if (oldList[i]->m_node->hasTagName(bodyTag)) {
301             oldBody = oldList[i].get();
302             continue;
303         }
304
305         // Check if this change is between stable nodes. If it is, consider it as "modified".
306         if (!m_unusedNodesMap.contains(oldList[i]->m_sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
307             size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
308             size_t anchorAfter = i == oldMap.size() - 1 ? anchorCandidate + 1 : oldMap[i + 1].second;
309             if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList.size())
310                 merges.set(newList[anchorCandidate].get(), oldList[i].get());
311             else {
312                 removeChild(oldList[i].get(), ec);
313                 if (ec)
314                     return;
315             }
316         } else {
317             removeChild(oldList[i].get(), ec);
318             if (ec)
319                 return;
320         }
321     }
322
323     // Mark retained nodes as used, do not reuse node more than once.
324     HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t> >  usedOldOrdinals;
325     for (size_t i = 0; i < newList.size(); ++i) {
326         if (!newMap[i].first)
327             continue;
328         size_t oldOrdinal = newMap[i].second;
329         if (usedOldOrdinals.contains(oldOrdinal)) {
330             // Do not map node more than once
331             newMap[i].first = 0;
332             newMap[i].second = 0;
333             continue;
334         }
335         usedOldOrdinals.add(oldOrdinal);
336         markNodeAsUsed(newMap[i].first);
337     }
338
339     // Mark <head> and <body> nodes for merge.
340     if (oldHead || oldBody) {
341         for (size_t i = 0; i < newList.size(); ++i) {
342             if (oldHead && newList[i]->m_node->hasTagName(headTag))
343                 merges.set(newList[i].get(), oldHead);
344             if (oldBody && newList[i]->m_node->hasTagName(bodyTag))
345                 merges.set(newList[i].get(), oldBody);
346         }
347     }
348
349     // 2. Patch nodes marked for merge.
350     for (HashMap<Digest*, Digest*>::iterator it = merges.begin(); it != merges.end(); ++it) {
351         innerPatchNode(it->second, it->first, ec);
352         if (ec)
353             return;
354     }
355
356     // 3. Insert missing nodes.
357     for (size_t i = 0; i < newMap.size(); ++i) {
358         if (newMap[i].first || merges.contains(newList[i].get()))
359             continue;
360
361         ExceptionCode ec = 0;
362         insertBefore(parentNode, newList[i].get(), parentNode->childNode(i), ec);
363         if (ec)
364             return;
365     }
366
367     // 4. Then put all nodes that retained into their slots (sort by new index).
368     for (size_t i = 0; i < oldMap.size(); ++i) {
369         if (!oldMap[i].first)
370             continue;
371         RefPtr<Node> node = oldMap[i].first->m_node;
372         Node* anchorNode = parentNode->childNode(oldMap[i].second);
373         if (node.get() == anchorNode)
374             continue;
375         if (node->hasTagName(bodyTag) || node->hasTagName(headTag))
376             continue; // Never move head or body, move the rest of the nodes around them.
377
378         parentNode->insertBefore(node, anchorNode, ec);
379         if (ec)
380             return;
381     }
382 }
383
384 static void addStringToSHA1(SHA1& sha1, const String& string)
385 {
386     CString cString = string.utf8();
387     sha1.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
388 }
389
390 PassOwnPtr<DOMPatchSupport::Digest> DOMPatchSupport::createDigest(Node* node, UnusedNodesMap* unusedNodesMap)
391 {
392     Digest* digest = new Digest(node);
393
394     SHA1 sha1;
395
396     Node::NodeType nodeType = node->nodeType();
397     sha1.addBytes(reinterpret_cast<const uint8_t*>(&nodeType), sizeof(nodeType));
398     addStringToSHA1(sha1, node->nodeName());
399     addStringToSHA1(sha1, node->nodeValue());
400
401     if (node->nodeType() == Node::ELEMENT_NODE) {
402         Node* child = node->firstChild();
403         while (child) {
404             OwnPtr<Digest> childInfo = createDigest(child, unusedNodesMap);
405             addStringToSHA1(sha1, childInfo->m_sha1);
406             child = child->nextSibling();
407             digest->m_children.append(childInfo.release());
408         }
409         Element* element = static_cast<Element*>(node);
410
411         if (element->hasAttributesWithoutUpdate()) {
412             size_t numAttrs = element->attributeCount();
413             SHA1 attrsSHA1;
414             for (size_t i = 0; i < numAttrs; ++i) {
415                 const Attribute* attribute = element->attributeItem(i);
416                 addStringToSHA1(attrsSHA1, attribute->name().toString());
417                 addStringToSHA1(attrsSHA1, attribute->value());
418             }
419             Vector<uint8_t, 20> attrsHash;
420             attrsSHA1.computeHash(attrsHash);
421             digest->m_attrsSHA1 = base64Encode(reinterpret_cast<const char*>(attrsHash.data()), 10);
422             addStringToSHA1(sha1, digest->m_attrsSHA1);
423         }
424     }
425
426     Vector<uint8_t, 20> hash;
427     sha1.computeHash(hash);
428     digest->m_sha1 = base64Encode(reinterpret_cast<const char*>(hash.data()), 10);
429     if (unusedNodesMap)
430         unusedNodesMap->add(digest->m_sha1, digest);
431     return adoptPtr(digest);
432 }
433
434 void DOMPatchSupport::insertBefore(ContainerNode* parentNode, Digest* digest, Node* anchor, ExceptionCode& ec)
435 {
436     parentNode->insertBefore(digest->m_node, anchor, ec);
437     markNodeAsUsed(digest);
438 }
439
440 void DOMPatchSupport::removeChild(Digest* oldDigest, ExceptionCode& ec)
441 {
442     RefPtr<Node> oldNode = oldDigest->m_node;
443     oldNode->parentNode()->removeChild(oldNode.get(), ec);
444
445     // Diff works within levels. In order not to lose the node identity when user
446     // prepends his HTML with "<div>" (i.e. all nodes are shifted to the next nested level),
447     // prior to dropping the original node on the floor, check whether new DOM has a digest
448     // with matching sha1. If it does, replace it with the original DOM chunk. Chances are
449     // high that it will get merged back into the original DOM during the further patching.
450
451     UnusedNodesMap::iterator it = m_unusedNodesMap.find(oldDigest->m_sha1);
452     if (it != m_unusedNodesMap.end()) {
453         Digest* newDigest = it->second;
454         Node* newNode = newDigest->m_node;
455         newNode->parentNode()->replaceChild(oldNode, newNode, ec);
456         newDigest->m_node = oldNode.get();
457         markNodeAsUsed(newDigest);
458         return;
459     }
460
461     for (size_t i = 0; i < oldDigest->m_children.size(); ++i)
462         removeChild(oldDigest->m_children[i].get(), ec);
463 }
464
465 void DOMPatchSupport::markNodeAsUsed(Digest* digest)
466 {
467     Deque<Digest*> queue;
468     queue.append(digest);
469     while (!queue.isEmpty()) {
470         Digest* first = queue.takeFirst();
471         m_unusedNodesMap.remove(first->m_sha1);
472         for (size_t i = 0; i < first->m_children.size(); ++i)
473             queue.append(first->m_children[i].get());
474     }
475 }
476
477 #ifdef DEBUG_DOM_PATCH_SUPPORT
478 static String nodeName(Node* node)
479 {
480     if (node->document()->isXHTMLDocument())
481          return node->nodeName();
482     return node->nodeName().lower();
483 }
484
485 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name)
486 {
487     fprintf(stderr, "\n\n");
488     for (size_t i = 0; i < map.size(); ++i)
489         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);
490 }
491 #endif
492
493 } // namespace WebCore
494
495 #endif // ENABLE(INSPECTOR)