Not reviewed: 32bit build fix.
[WebKit-https.git] / Source / WebCore / inspector / DOMEditor.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 "DOMEditor.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 "Node.h"
45
46 #include <wtf/Deque.h>
47 #include <wtf/RefPtr.h>
48 #include <wtf/SHA1.h>
49 #include <wtf/text/CString.h>
50
51 using namespace std;
52
53 namespace WebCore {
54
55 struct DOMEditor::Digest {
56     explicit Digest(Node* node) : m_node(node) { }
57
58     String m_sha1;
59     String m_attrsSHA1;
60     Node* m_node;
61     Vector<OwnPtr<Digest> > m_children;
62 };
63
64 DOMEditor::DOMEditor(Document* document) : m_document(document) { }
65
66 DOMEditor::~DOMEditor() { }
67
68 void DOMEditor::patchDocument(const String& markup)
69 {
70     RefPtr<HTMLDocument> newDocument = HTMLDocument::create(0, KURL());
71     RefPtr<DocumentParser> parser = HTMLDocumentParser::create(newDocument.get(), false);
72     parser->insert(markup); // Use insert() so that the parser will not yield.
73     parser->finish();
74     parser->detach();
75
76     ExceptionCode ec = 0;
77     innerPatchHTMLElement(m_document->head(), newDocument->head(), ec);
78     if (!ec)
79         innerPatchHTMLElement(m_document->body(), newDocument->body(), ec);
80
81     if (ec) {
82         // Fall back to rewrite.
83         m_document->write(markup);
84         m_document->close();
85     }
86 }
87
88 Node* DOMEditor::patchNode(Node* node, const String& markup, ExceptionCode& ec)
89 {
90     Element* parentElement = node->parentElement();
91     Node* previousSibling = node->previousSibling();
92     RefPtr<DocumentFragment> fragment = DocumentFragment::create(m_document);
93     fragment->parseHTML(markup, parentElement);
94
95     // Compose the old list.
96     Vector<OwnPtr<Digest> > oldList;
97     for (Node* child = parentElement->firstChild(); child; child = child->nextSibling())
98         oldList.append(createDigest(child, 0));
99
100     // Compose the new list.
101     Vector<OwnPtr<Digest> > newList;
102     for (Node* child = parentElement->firstChild(); child != node; child = child->nextSibling())
103         newList.append(createDigest(child, 0));
104     for (Node* child = fragment->firstChild(); child; child = child->nextSibling())
105         newList.append(createDigest(child, &m_unusedNodesMap));
106     for (Node* child = node->nextSibling(); child; child = child->nextSibling())
107         newList.append(createDigest(child, 0));
108
109     innerPatchChildren(parentElement, oldList, newList, ec);
110     if (ec) {
111         // Fall back to total replace.
112         ec = 0;
113         parentElement->replaceChild(fragment.release(), node, ec);
114         if (ec)
115             return 0;
116     }
117     return previousSibling ? previousSibling->nextSibling() : parentElement->firstChild();
118 }
119
120 void DOMEditor::innerPatchHTMLElement(HTMLElement* oldElement, HTMLElement* newElement, ExceptionCode& ec)
121 {
122     if (oldElement)  {
123         if (newElement) {
124             OwnPtr<Digest> oldInfo = createDigest(oldElement, 0);
125             OwnPtr<Digest> newInfo = createDigest(newElement, &m_unusedNodesMap);
126             innerPatchNode(oldInfo.get(), newInfo.get(), ec);
127             if (ec)
128                 return;
129         }
130         oldElement->removeAllChildren();
131         return;
132     }
133     if (newElement)
134         m_document->documentElement()->appendChild(newElement, ec);
135 }
136
137 void DOMEditor::innerPatchNode(Digest* oldDigest, Digest* newDigest, ExceptionCode& ec)
138 {
139     if (oldDigest->m_sha1 == newDigest->m_sha1)
140         return;
141
142     Node* oldNode = oldDigest->m_node;
143     Node* newNode = newDigest->m_node;
144
145     if (newNode->nodeType() != oldNode->nodeType() || newNode->nodeName() != oldNode->nodeName()) {
146         oldNode->parentNode()->replaceChild(newNode, oldNode, ec);
147         return;
148     }
149
150     if (oldNode->nodeValue() != newNode->nodeValue())
151         oldNode->setNodeValue(newNode->nodeValue(), ec);
152     if (ec)
153         return;
154
155     if (oldNode->nodeType() != Node::ELEMENT_NODE)
156         return;
157
158     // Patch attributes
159     Element* oldElement = static_cast<Element*>(oldNode);
160     Element* newElement = static_cast<Element*>(newNode);
161     if (oldDigest->m_attrsSHA1 != newDigest->m_attrsSHA1) {
162         NamedNodeMap* oldAttributeMap = oldElement->attributeMap();
163
164         while (oldAttributeMap && oldAttributeMap->length())
165             oldAttributeMap->removeAttribute(0);
166
167         NamedNodeMap* newAttributeMap = newElement->attributeMap();
168         if (newAttributeMap) {
169             size_t numAttrs = newAttributeMap->length();
170             for (size_t i = 0; i < numAttrs; ++i) {
171                 const Attribute* attribute = newAttributeMap->attributeItem(i);
172                 oldElement->setAttribute(attribute->name(), attribute->value());
173             }
174         }
175     }
176
177     innerPatchChildren(oldElement, oldDigest->m_children, newDigest->m_children, ec);
178     m_unusedNodesMap.remove(newDigest->m_sha1);
179 }
180
181 pair<DOMEditor::ResultMap, DOMEditor::ResultMap>
182 DOMEditor::diff(const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList)
183 {
184     ResultMap newMap(newList.size());
185     ResultMap oldMap(oldList.size());
186
187     for (size_t i = 0; i < oldMap.size(); ++i) {
188         oldMap[i].first = 0;
189         oldMap[i].second = -1;
190     }
191
192     for (size_t i = 0; i < newMap.size(); ++i) {
193         newMap[i].first = 0;
194         newMap[i].second = -1;
195     }
196
197     // Trim head and tail.
198     for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[i]->m_sha1 == newList[i]->m_sha1; ++i) {
199         oldMap[i].first = oldList[i].get();
200         oldMap[i].second = i;
201         newMap[i].first = newList[i].get();
202         newMap[i].second = i;
203     }
204     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) {
205         size_t oldIndex = oldList.size() - i - 1;
206         size_t newIndex = newList.size() - i - 1;
207         oldMap[oldIndex].first = oldList[oldIndex].get();
208         oldMap[oldIndex].second = newIndex;
209         newMap[newIndex].first = newList[newIndex].get();
210         newMap[newIndex].second = oldIndex;
211     }
212
213     typedef HashMap<String, Vector<size_t> > DiffTable;
214     DiffTable newTable;
215     DiffTable oldTable;
216
217     for (size_t i = 0; i < newList.size(); ++i) {
218         DiffTable::iterator it = newTable.add(newList[i]->m_sha1, Vector<size_t>()).first;
219         it->second.append(i);
220     }
221
222     for (size_t i = 0; i < oldList.size(); ++i) {
223         DiffTable::iterator it = oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).first;
224         it->second.append(i);
225     }
226
227     for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) {
228         if (newIt->second.size() != 1)
229             continue;
230
231         DiffTable::iterator oldIt = oldTable.find(newIt->first);
232         if (oldIt == oldTable.end() || oldIt->second.size() != 1)
233             continue;
234
235         newMap[newIt->second[0]] = make_pair(newList[newIt->second[0]].get(), oldIt->second[0]);
236         oldMap[oldIt->second[0]] = make_pair(oldList[oldIt->second[0]].get(), newIt->second[0]);
237     }
238
239     for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
240         if (!newMap[i].first || newMap[i + 1].first)
241             continue;
242
243         size_t j = newMap[i].second + 1;
244         if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == oldList[j]->m_sha1) {
245             newMap[i + 1] = make_pair(newList[i + 1].get(), j);
246             oldMap[j] = make_pair(oldList[j].get(), i + 1);
247         }
248     }
249
250     for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
251         if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
252             continue;
253
254         size_t j = newMap[i].second - 1;
255         if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) {
256             newMap[i - 1] = make_pair(newList[i - 1].get(), j);
257             oldMap[j] = make_pair(oldList[j].get(), i - 1);
258         }
259     }
260
261     return make_pair(oldMap, newMap);
262 }
263
264 void DOMEditor::innerPatchChildren(Element* element, const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList, ExceptionCode& ec)
265 {
266     pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList);
267     ResultMap& oldMap = resultMaps.first;
268     ResultMap& newMap = resultMaps.second;
269
270     // 1. First strip everything except for the nodes that retain. Collect pending merges.
271     HashMap<Digest*, Digest*> merges;
272     for (size_t i = 0; i < oldList.size(); ++i) {
273         if (oldMap[i].first)
274             continue;
275
276         // Check if this change is between stable nodes. If it is, consider it as "modified".
277         if (!m_unusedNodesMap.contains(oldList[i]->m_sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
278             size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
279             size_t anchorAfter = i == oldMap.size() - 1 ? anchorCandidate + 1 : oldMap[i + 1].second;
280             if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList.size())
281                 merges.set(newList[anchorCandidate].get(), oldList[i].get());
282             else {
283                 removeChild(oldList[i].get(), ec);
284                 if (ec)
285                     return;
286             }
287         } else {
288             removeChild(oldList[i].get(), ec);
289             if (ec)
290                 return;
291         }
292     }
293
294     // Mark retained nodes as used.
295     for (size_t i = 0; i < newList.size(); ++i) {
296         if (newMap[i].first)
297             markNodeAsUsed(newMap[i].first);
298     }
299
300     // 2. Patch nodes marked for merge.
301     for (HashMap<Digest*, Digest*>::iterator it = merges.begin(); it != merges.end(); ++it) {
302         innerPatchNode(it->second, it->first, ec);
303         if (ec)
304             return;
305     }
306
307     // 3. Insert missing nodes.
308     for (size_t i = 0; i < newMap.size(); ++i) {
309         if (newMap[i].first || merges.contains(newList[i].get()))
310             continue;
311
312         ExceptionCode ec = 0;
313         insertBefore(element, newList[i].get(), element->childNode(i), ec);
314         if (ec)
315             return;
316     }
317
318     // 4. Then put all nodes that retained into their slots (sort by new index).
319     for (size_t i = 0; i < oldMap.size(); ++i) {
320         if (!oldMap[i].first)
321             continue;
322         RefPtr<Node> node = oldMap[i].first->m_node;
323         Node* anchorNode = element->childNode(oldMap[i].second);
324         if (node.get() == anchorNode)
325             continue;
326
327         element->insertBefore(node, anchorNode, ec);
328         if (ec)
329             return;
330     }
331 }
332
333 static void addStringToSHA1(SHA1& sha1, const String& string)
334 {
335     CString cString = string.utf8();
336     sha1.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
337 }
338
339 PassOwnPtr<DOMEditor::Digest> DOMEditor::createDigest(Node* node, UnusedNodesMap* unusedNodesMap)
340 {
341     Digest* digest = new Digest(node);
342
343     SHA1 sha1;
344
345     Node::NodeType nodeType = node->nodeType();
346     sha1.addBytes(reinterpret_cast<const uint8_t*>(&nodeType), sizeof(nodeType));
347     addStringToSHA1(sha1, node->nodeName());
348     addStringToSHA1(sha1, node->nodeValue());
349
350     if (node->nodeType() == Node::ELEMENT_NODE) {
351         Node* child = node->firstChild();
352         while (child) {
353             OwnPtr<Digest> childInfo = createDigest(child, unusedNodesMap);
354             addStringToSHA1(sha1, childInfo->m_sha1);
355             child = child->nextSibling();
356             digest->m_children.append(childInfo.release());
357         }
358         Element* element = static_cast<Element*>(node);
359
360         NamedNodeMap* attrMap = element->attributeMap();
361         if (attrMap && attrMap->length()) {
362             size_t numAttrs = attrMap->length();
363             SHA1 attrsSHA1;
364             for (size_t i = 0; i < numAttrs; ++i) {
365                 const Attribute* attribute = attrMap->attributeItem(i);
366                 addStringToSHA1(attrsSHA1, attribute->name().toString());
367                 addStringToSHA1(attrsSHA1, attribute->value());
368             }
369             Vector<uint8_t, 20> attrsHash;
370             attrsSHA1.computeHash(attrsHash);
371             digest->m_attrsSHA1 = base64Encode(reinterpret_cast<const char*>(attrsHash.data()), 10);
372             addStringToSHA1(sha1, digest->m_attrsSHA1);
373         }
374     }
375
376     Vector<uint8_t, 20> hash;
377     sha1.computeHash(hash);
378     digest->m_sha1 = base64Encode(reinterpret_cast<const char*>(hash.data()), 10);
379     if (unusedNodesMap)
380         unusedNodesMap->add(digest->m_sha1, digest);
381     return adoptPtr(digest);
382 }
383
384 void DOMEditor::insertBefore(Element* parentElement, Digest* digest, Node* anchor, ExceptionCode& ec)
385 {
386     parentElement->insertBefore(digest->m_node, anchor, ec);
387     markNodeAsUsed(digest);
388 }
389
390 void DOMEditor::removeChild(Digest* oldDigest, ExceptionCode& ec)
391 {
392     RefPtr<Node> oldNode = oldDigest->m_node;
393     oldNode->parentNode()->removeChild(oldNode.get(), ec);
394
395     // Diff works within levels. In order not to lose the node identity when user
396     // prepends his HTML with "<div>" (i.e. all nodes are shifted to the next nested level),
397     // prior to dropping the original node on the floor, check whether new DOM has a digest
398     // with matching sha1. If it does, replace it with the original DOM chunk. Chances are
399     // high that it will get merged back into the original DOM during the further patching.
400
401     UnusedNodesMap::iterator it = m_unusedNodesMap.find(oldDigest->m_sha1);
402     if (it != m_unusedNodesMap.end()) {
403         Digest* newDigest = it->second;
404         Node* newNode = newDigest->m_node;
405         newNode->parentNode()->replaceChild(oldNode, newNode, ec);
406         newDigest->m_node = oldNode.get();
407         markNodeAsUsed(newDigest);
408         return;
409     }
410
411     for (size_t i = 0; i < oldDigest->m_children.size(); ++i)
412         removeChild(oldDigest->m_children[i].get(), ec);
413 }
414
415 void DOMEditor::markNodeAsUsed(Digest* digest)
416 {
417     Deque<Digest*> queue;
418     queue.append(digest);
419     while (!queue.isEmpty()) {
420         Digest* first = queue.takeFirst();
421         m_unusedNodesMap.remove(first->m_sha1);
422         for (size_t i = 0; i < first->m_children.size(); ++i)
423             queue.append(first->m_children[i].get());
424     }
425 }
426
427 } // namespace WebCore
428
429 #endif // ENABLE(INSPECTOR)