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