Replace WTF::move with WTFMove
[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 #include "Attribute.h"
35 #include "DOMEditor.h"
36 #include "Document.h"
37 #include "DocumentFragment.h"
38 #include "HTMLDocument.h"
39 #include "HTMLDocumentParser.h"
40 #include "HTMLElement.h"
41 #include "HTMLHeadElement.h"
42 #include "HTMLNames.h"
43 #include "InspectorHistory.h"
44 #include "Node.h"
45 #include "XMLDocumentParser.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/Base64.h>
52 #include <wtf/text/CString.h>
53
54 namespace WebCore {
55
56 using HTMLNames::bodyTag;
57 using HTMLNames::headTag;
58 using HTMLNames::htmlTag;
59
60 struct DOMPatchSupport::Digest {
61     explicit Digest(Node* node) : m_node(node) { }
62
63     String m_sha1;
64     String m_attrsSHA1;
65     Node* m_node;
66     Vector<std::unique_ptr<Digest>> m_children;
67 };
68
69 void DOMPatchSupport::patchDocument(Document* document, const String& markup)
70 {
71     InspectorHistory history;
72     DOMEditor domEditor(&history);
73     DOMPatchSupport patchSupport(&domEditor, document);
74     patchSupport.patchDocument(markup);
75 }
76
77 DOMPatchSupport::DOMPatchSupport(DOMEditor* domEditor, Document* document)
78     : m_domEditor(domEditor)
79     , m_document(document)
80 {
81 }
82
83 DOMPatchSupport::~DOMPatchSupport() { }
84
85 void DOMPatchSupport::patchDocument(const String& markup)
86 {
87     RefPtr<Document> newDocument;
88     if (m_document->isHTMLDocument())
89         newDocument = HTMLDocument::create(nullptr, URL());
90     else if (m_document->isXHTMLDocument())
91         newDocument = HTMLDocument::createXHTML(nullptr, URL());
92     else if (m_document->isSVGDocument())
93         newDocument = Document::create(nullptr, URL());
94
95     ASSERT(newDocument);
96     RefPtr<DocumentParser> parser;
97     if (newDocument->isHTMLDocument())
98         parser = HTMLDocumentParser::create(static_cast<HTMLDocument&>(*newDocument));
99     else
100         parser = XMLDocumentParser::create(*newDocument, nullptr);
101     parser->insert(markup); // Use insert() so that the parser will not yield.
102     parser->finish();
103     parser->detach();
104
105     std::unique_ptr<Digest> oldInfo = createDigest(m_document->documentElement(), nullptr);
106     std::unique_ptr<Digest> newInfo = createDigest(newDocument->documentElement(), &m_unusedNodesMap);
107
108     if (!innerPatchNode(oldInfo.get(), newInfo.get(), IGNORE_EXCEPTION)) {
109         // Fall back to rewrite.
110         m_document->write(markup);
111         m_document->close();
112     }
113 }
114
115 Node* DOMPatchSupport::patchNode(Node& node, const String& markup, ExceptionCode& ec)
116 {
117     // Don't parse <html> as a fragment.
118     if (node.isDocumentNode() || (node.parentNode() && node.parentNode()->isDocumentNode())) {
119         patchDocument(markup);
120         return nullptr;
121     }
122
123     Node* previousSibling = node.previousSibling();
124     // FIXME: This code should use one of createFragment* in markup.h
125     RefPtr<DocumentFragment> fragment = DocumentFragment::create(*m_document);
126     if (m_document->isHTMLDocument())
127         fragment->parseHTML(markup, node.parentElement() ? node.parentElement() : m_document->documentElement());
128     else
129         fragment->parseXML(markup, node.parentElement() ? node.parentElement() : m_document->documentElement());
130
131     // Compose the old list.
132     ContainerNode* parentNode = node.parentNode();
133     Vector<std::unique_ptr<Digest>> oldList;
134     for (Node* child = parentNode->firstChild(); child; child = child->nextSibling())
135         oldList.append(createDigest(child, nullptr));
136
137     // Compose the new list.
138     String markupCopy = markup.lower();
139     Vector<std::unique_ptr<Digest>> newList;
140     for (Node* child = parentNode->firstChild(); child != &node; child = child->nextSibling())
141         newList.append(createDigest(child, nullptr));
142     for (Node* child = fragment->firstChild(); child; child = child->nextSibling()) {
143         if (child->hasTagName(headTag) && !child->firstChild() && markupCopy.find("</head>") == notFound)
144             continue; // HTML5 parser inserts empty <head> tag whenever it parses <body>
145         if (child->hasTagName(bodyTag) && !child->firstChild() && markupCopy.find("</body>") == notFound)
146             continue; // HTML5 parser inserts empty <body> tag whenever it parses </head>
147         newList.append(createDigest(child, &m_unusedNodesMap));
148     }
149     for (Node* child = node.nextSibling(); child; child = child->nextSibling())
150         newList.append(createDigest(child, nullptr));
151
152     if (!innerPatchChildren(parentNode, oldList, newList, ec)) {
153         // Fall back to total replace.
154         ec = 0;
155         if (!m_domEditor->replaceChild(parentNode, fragment.release(), &node, ec))
156             return nullptr;
157     }
158     return previousSibling ? previousSibling->nextSibling() : parentNode->firstChild();
159 }
160
161 bool DOMPatchSupport::innerPatchNode(Digest* oldDigest, Digest* newDigest, ExceptionCode& ec)
162 {
163     if (oldDigest->m_sha1 == newDigest->m_sha1)
164         return true;
165
166     Node* oldNode = oldDigest->m_node;
167     Node* newNode = newDigest->m_node;
168
169     if (newNode->nodeType() != oldNode->nodeType() || newNode->nodeName() != oldNode->nodeName())
170         return m_domEditor->replaceChild(oldNode->parentNode(), newNode, oldNode, ec);
171
172     if (oldNode->nodeValue() != newNode->nodeValue()) {
173         if (!m_domEditor->setNodeValue(oldNode, newNode->nodeValue(), ec))
174             return false;
175     }
176
177     if (oldNode->nodeType() != Node::ELEMENT_NODE)
178         return true;
179
180     // Patch attributes
181     Element* oldElement = downcast<Element>(oldNode);
182     Element* newElement = downcast<Element>(newNode);
183     if (oldDigest->m_attrsSHA1 != newDigest->m_attrsSHA1) {
184         // FIXME: Create a function in Element for removing all properties. Take in account whether did/willModifyAttribute are important.
185         if (oldElement->hasAttributesWithoutUpdate()) {
186             while (oldElement->attributeCount()) {
187                 const Attribute& attribute = oldElement->attributeAt(0);
188                 if (!m_domEditor->removeAttribute(oldElement, attribute.localName(), ec))
189                     return false;
190             }
191         }
192
193         // FIXME: Create a function in Element for copying properties. cloneDataFromElement() is close but not enough for this case.
194         if (newElement->hasAttributesWithoutUpdate()) {
195             for (const Attribute& attribute : newElement->attributesIterator()) {
196                 if (!m_domEditor->setAttribute(oldElement, attribute.name().localName(), attribute.value(), ec))
197                     return false;
198             }
199         }
200     }
201
202     bool result = innerPatchChildren(oldElement, oldDigest->m_children, newDigest->m_children, ec);
203     m_unusedNodesMap.remove(newDigest->m_sha1);
204     return result;
205 }
206
207 std::pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap>
208 DOMPatchSupport::diff(const Vector<std::unique_ptr<Digest>>& oldList, const Vector<std::unique_ptr<Digest>>& newList)
209 {
210     ResultMap newMap(newList.size());
211     ResultMap oldMap(oldList.size());
212
213     for (auto& result : oldMap) {
214         result.first = nullptr;
215         result.second = 0;
216     }
217
218     for (auto& result : newMap) {
219         result.first = nullptr;
220         result.second = 0;
221     }
222
223     // Trim head and tail.
224     for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[i]->m_sha1 == newList[i]->m_sha1; ++i) {
225         oldMap[i].first = oldList[i].get();
226         oldMap[i].second = i;
227         newMap[i].first = newList[i].get();
228         newMap[i].second = i;
229     }
230     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) {
231         size_t oldIndex = oldList.size() - i - 1;
232         size_t newIndex = newList.size() - i - 1;
233         oldMap[oldIndex].first = oldList[oldIndex].get();
234         oldMap[oldIndex].second = newIndex;
235         newMap[newIndex].first = newList[newIndex].get();
236         newMap[newIndex].second = oldIndex;
237     }
238
239     typedef HashMap<String, Vector<size_t>> DiffTable;
240     DiffTable newTable;
241     DiffTable oldTable;
242
243     for (size_t i = 0; i < newList.size(); ++i) {
244         DiffTable::iterator it = newTable.add(newList[i]->m_sha1, Vector<size_t>()).iterator;
245         it->value.append(i);
246     }
247
248     for (size_t i = 0; i < oldList.size(); ++i) {
249         DiffTable::iterator it = oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).iterator;
250         it->value.append(i);
251     }
252
253     for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) {
254         if (newIt->value.size() != 1)
255             continue;
256
257         DiffTable::iterator oldIt = oldTable.find(newIt->key);
258         if (oldIt == oldTable.end() || oldIt->value.size() != 1)
259             continue;
260
261         newMap[newIt->value[0]] = std::make_pair(newList[newIt->value[0]].get(), oldIt->value[0]);
262         oldMap[oldIt->value[0]] = std::make_pair(oldList[oldIt->value[0]].get(), newIt->value[0]);
263     }
264
265     for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
266         if (!newMap[i].first || newMap[i + 1].first)
267             continue;
268
269         size_t j = newMap[i].second + 1;
270         if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == oldList[j]->m_sha1) {
271             newMap[i + 1] = std::make_pair(newList[i + 1].get(), j);
272             oldMap[j] = std::make_pair(oldList[j].get(), i + 1);
273         }
274     }
275
276     for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
277         if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
278             continue;
279
280         size_t j = newMap[i].second - 1;
281         if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) {
282             newMap[i - 1] = std::make_pair(newList[i - 1].get(), j);
283             oldMap[j] = std::make_pair(oldList[j].get(), i - 1);
284         }
285     }
286
287 #ifdef DEBUG_DOM_PATCH_SUPPORT
288     dumpMap(oldMap, "OLD");
289     dumpMap(newMap, "NEW");
290 #endif
291
292     return std::make_pair(oldMap, newMap);
293 }
294
295 bool DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector<std::unique_ptr<Digest>>& oldList, const Vector<std::unique_ptr<Digest>>& newList, ExceptionCode& ec)
296 {
297     std::pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList);
298     ResultMap& oldMap = resultMaps.first;
299     ResultMap& newMap = resultMaps.second;
300
301     Digest* oldHead = nullptr;
302     Digest* oldBody = nullptr;
303
304     // 1. First strip everything except for the nodes that retain. Collect pending merges.
305     HashMap<Digest*, Digest*> merges;
306     HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t>> usedNewOrdinals;
307     for (size_t i = 0; i < oldList.size(); ++i) {
308         if (oldMap[i].first) {
309             if (!usedNewOrdinals.contains(oldMap[i].second)) {
310                 usedNewOrdinals.add(oldMap[i].second);
311                 continue;
312             }
313             oldMap[i].first = nullptr;
314             oldMap[i].second = 0;
315         }
316
317         // Always match <head> and <body> tags with each other - we can't remove them from the DOM
318         // upon patching.
319         if (oldList[i]->m_node->hasTagName(headTag)) {
320             oldHead = oldList[i].get();
321             continue;
322         }
323         if (oldList[i]->m_node->hasTagName(bodyTag)) {
324             oldBody = oldList[i].get();
325             continue;
326         }
327
328         // Check if this change is between stable nodes. If it is, consider it as "modified".
329         if (!m_unusedNodesMap.contains(oldList[i]->m_sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
330             size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
331             size_t anchorAfter = i == oldMap.size() - 1 ? anchorCandidate + 1 : oldMap[i + 1].second;
332             if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList.size())
333                 merges.set(newList[anchorCandidate].get(), oldList[i].get());
334             else {
335                 if (!removeChildAndMoveToNew(oldList[i].get(), ec))
336                     return false;
337             }
338         } else {
339             if (!removeChildAndMoveToNew(oldList[i].get(), ec))
340                 return false;
341         }
342     }
343
344     // Mark retained nodes as used, do not reuse node more than once.
345     HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<size_t>> usedOldOrdinals;
346     for (size_t i = 0; i < newList.size(); ++i) {
347         if (!newMap[i].first)
348             continue;
349         size_t oldOrdinal = newMap[i].second;
350         if (usedOldOrdinals.contains(oldOrdinal)) {
351             // Do not map node more than once
352             newMap[i].first = nullptr;
353             newMap[i].second = 0;
354             continue;
355         }
356         usedOldOrdinals.add(oldOrdinal);
357         markNodeAsUsed(newMap[i].first);
358     }
359
360     // Mark <head> and <body> nodes for merge.
361     if (oldHead || oldBody) {
362         for (size_t i = 0; i < newList.size(); ++i) {
363             if (oldHead && newList[i]->m_node->hasTagName(headTag))
364                 merges.set(newList[i].get(), oldHead);
365             if (oldBody && newList[i]->m_node->hasTagName(bodyTag))
366                 merges.set(newList[i].get(), oldBody);
367         }
368     }
369
370     // 2. Patch nodes marked for merge.
371     for (auto& merge : merges) {
372         if (!innerPatchNode(merge.value, merge.key, ec))
373             return false;
374     }
375
376     // 3. Insert missing nodes.
377     for (size_t i = 0; i < newMap.size(); ++i) {
378         if (newMap[i].first || merges.contains(newList[i].get()))
379             continue;
380         if (!insertBeforeAndMarkAsUsed(parentNode, newList[i].get(), parentNode->traverseToChildAt(i), ec))
381             return false;
382     }
383
384     // 4. Then put all nodes that retained into their slots (sort by new index).
385     for (size_t i = 0; i < oldMap.size(); ++i) {
386         if (!oldMap[i].first)
387             continue;
388         RefPtr<Node> node = oldMap[i].first->m_node;
389         Node* anchorNode = parentNode->traverseToChildAt(oldMap[i].second);
390         if (node.get() == anchorNode)
391             continue;
392         if (node->hasTagName(bodyTag) || node->hasTagName(headTag))
393             continue; // Never move head or body, move the rest of the nodes around them.
394
395         if (!m_domEditor->insertBefore(parentNode, node.release(), anchorNode, ec))
396             return false;
397     }
398     return true;
399 }
400
401 static void addStringToSHA1(SHA1& sha1, const String& string)
402 {
403     CString cString = string.utf8();
404     sha1.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
405 }
406
407 std::unique_ptr<DOMPatchSupport::Digest> DOMPatchSupport::createDigest(Node* node, UnusedNodesMap* unusedNodesMap)
408 {
409     auto digest = std::make_unique<Digest>(node);
410     SHA1 sha1;
411
412     Node::NodeType nodeType = node->nodeType();
413     sha1.addBytes(reinterpret_cast<const uint8_t*>(&nodeType), sizeof(nodeType));
414     addStringToSHA1(sha1, node->nodeName());
415     addStringToSHA1(sha1, node->nodeValue());
416
417     if (node->nodeType() == Node::ELEMENT_NODE) {
418         Node* child = node->firstChild();
419         while (child) {
420             std::unique_ptr<Digest> childInfo = createDigest(child, unusedNodesMap);
421             addStringToSHA1(sha1, childInfo->m_sha1);
422             child = child->nextSibling();
423             digest->m_children.append(WTFMove(childInfo));
424         }
425         Element* element = downcast<Element>(node);
426
427         if (element->hasAttributesWithoutUpdate()) {
428             SHA1 attrsSHA1;
429             for (const Attribute& attribute : element->attributesIterator()) {
430                 addStringToSHA1(attrsSHA1, attribute.name().toString());
431                 addStringToSHA1(attrsSHA1, attribute.value());
432             }
433             SHA1::Digest attrsHash;
434             attrsSHA1.computeHash(attrsHash);
435             digest->m_attrsSHA1 = base64Encode(attrsHash.data(), 10);
436             addStringToSHA1(sha1, digest->m_attrsSHA1);
437         }
438     }
439
440     SHA1::Digest hash;
441     sha1.computeHash(hash);
442     digest->m_sha1 = base64Encode(hash.data(), 10);
443     if (unusedNodesMap)
444         unusedNodesMap->add(digest->m_sha1, digest.get());
445
446     return digest;
447 }
448
449 bool DOMPatchSupport::insertBeforeAndMarkAsUsed(ContainerNode* parentNode, Digest* digest, Node* anchor, ExceptionCode& ec)
450 {
451     bool result = m_domEditor->insertBefore(parentNode, digest->m_node, anchor, ec);
452     markNodeAsUsed(digest);
453     return result;
454 }
455
456 bool DOMPatchSupport::removeChildAndMoveToNew(Digest* oldDigest, ExceptionCode& ec)
457 {
458     RefPtr<Node> oldNode = oldDigest->m_node;
459     if (!m_domEditor->removeChild(oldNode->parentNode(), oldNode.get(), ec))
460         return false;
461
462     // Diff works within levels. In order not to lose the node identity when user
463     // prepends his HTML with "<div>" (i.e. all nodes are shifted to the next nested level),
464     // prior to dropping the original node on the floor, check whether new DOM has a digest
465     // with matching sha1. If it does, replace it with the original DOM chunk. Chances are
466     // high that it will get merged back into the original DOM during the further patching.
467     UnusedNodesMap::iterator it = m_unusedNodesMap.find(oldDigest->m_sha1);
468     if (it != m_unusedNodesMap.end()) {
469         Digest* newDigest = it->value;
470         Node* newNode = newDigest->m_node;
471         if (!m_domEditor->replaceChild(newNode->parentNode(), WTFMove(oldNode), newNode, ec))
472             return false;
473         newDigest->m_node = oldNode.get();
474         markNodeAsUsed(newDigest);
475         return true;
476     }
477
478     for (auto& child : oldDigest->m_children) {
479         if (!removeChildAndMoveToNew(child.get(), ec))
480             return false;
481     }
482     return true;
483 }
484
485 void DOMPatchSupport::markNodeAsUsed(Digest* digest)
486 {
487     Deque<Digest*> queue;
488     queue.append(digest);
489     while (!queue.isEmpty()) {
490         Digest* first = queue.takeFirst();
491         m_unusedNodesMap.remove(first->m_sha1);
492         for (auto& child : first->m_children)
493             queue.append(child.get());
494     }
495 }
496
497 #ifdef DEBUG_DOM_PATCH_SUPPORT
498 static String nodeName(Node* node)
499 {
500     if (node->document().isXHTMLDocument())
501          return node->nodeName();
502     return node->nodeName().lower();
503 }
504
505 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name)
506 {
507     fprintf(stderr, "\n\n");
508     for (size_t i = 0; i < map.size(); ++i)
509         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);
510 }
511 #endif
512
513 } // namespace WebCore