Web Inspector: make setOuterHTML use new DOMEditor, cover it with tests.
[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 "ExceptionCode.h"
41 #include "HTMLDocument.h"
42 #include "HTMLDocumentParser.h"
43 #include "HTMLElement.h"
44 #include "HTMLHeadElement.h"
45 #include "Node.h"
46
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 static String exceptionDescription(ExceptionCode& ec)
56 {
57     ExceptionCodeDescription description(ec);
58     return description.name;
59 }
60
61 struct DOMEditor::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 DOMEditor::DOMEditor(Document* document) : m_document(document) { }
71
72 DOMEditor::~DOMEditor() { }
73
74 void DOMEditor::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     ErrorString errorString;
83     innerPatchHTMLElement(&errorString, m_document->head(), newDocument->head());
84     if (errorString.isEmpty())
85         innerPatchHTMLElement(&errorString, m_document->body(), newDocument->body());
86
87     if (errorString.isEmpty())
88         return;
89
90     // Fall back to rewrite.
91     m_document->write(markup);
92     m_document->close();
93 }
94
95 Node* DOMEditor::patchNode(ErrorString* errorString, Node* node, const String& markup)
96 {
97     Element* parentElement = node->parentElement();
98     if (!parentElement) {
99         *errorString = "Can only set outer HTML to nodes within Element";
100         return 0;
101     }
102
103     Node* previousSibling = node->previousSibling();
104     RefPtr<DocumentFragment> fragment = DocumentFragment::create(m_document);
105     fragment->parseHTML(markup, parentElement);
106
107     // Compose the old list.
108     Vector<OwnPtr<Digest> > oldList;
109     for (Node* child = parentElement->firstChild(); child; child = child->nextSibling())
110         oldList.append(createDigest(child));
111
112     // Compose the new list.
113     Vector<OwnPtr<Digest> > newList;
114     for (Node* child = parentElement->firstChild(); child != node; child = child->nextSibling())
115         newList.append(createDigest(child));
116     for (Node* child = fragment->firstChild(); child; child = child->nextSibling())
117         newList.append(createDigest(child));
118     for (Node* child = node->nextSibling(); child; child = child->nextSibling())
119         newList.append(createDigest(child));
120
121     innerPatchChildren(errorString, parentElement, oldList, newList);
122     if (!errorString->isEmpty()) {
123         // Fall back to total replace.
124         ExceptionCode ec = 0;
125         parentElement->replaceChild(fragment.release(), node, ec);
126         if (ec) {
127             *errorString = exceptionDescription(ec);
128             return 0;
129         }
130     }
131     return previousSibling ? previousSibling->nextSibling() : parentElement->firstChild();
132 }
133
134 void DOMEditor::innerPatchHTMLElement(ErrorString* errorString, HTMLElement* oldElement, HTMLElement* newElement)
135 {
136     if (oldElement)  {
137         if (newElement) {
138             OwnPtr<Digest> oldInfo = createDigest(oldElement);
139             OwnPtr<Digest> newInfo = createDigest(newElement);
140             innerPatchNode(errorString, oldInfo.get(), newInfo.get());
141             if (!errorString->isEmpty())
142                 return;
143         }
144         oldElement->removeAllChildren();
145         return;
146     }
147     if (newElement) {
148         ExceptionCode ec = 0;
149         m_document->documentElement()->appendChild(newElement, ec);
150         if (ec)
151             *errorString = exceptionDescription(ec);
152     }
153 }
154
155 void DOMEditor::innerPatchNode(ErrorString* errorString, Digest* oldDigest, Digest* newDigest)
156 {
157     if (oldDigest->m_sha1 == newDigest->m_sha1)
158         return;
159
160     Node* oldNode = oldDigest->m_node;
161     Node* newNode = newDigest->m_node;
162
163     if (newNode->nodeType() != oldNode->nodeType() || newNode->nodeName() != oldNode->nodeName()) {
164         ExceptionCode ec = 0;
165         oldNode->parentNode()->replaceChild(newNode, oldNode, ec);
166         if (ec)
167             *errorString = exceptionDescription(ec);
168         return;
169     }
170
171     ExceptionCode ec = 0;
172     if (oldNode->nodeValue() != newNode->nodeValue())
173         oldNode->setNodeValue(newNode->nodeValue(), ec);
174     if (ec) {
175         *errorString = exceptionDescription(ec);
176         return;
177     }
178
179     if (oldNode->nodeType() != Node::ELEMENT_NODE)
180         return;
181
182     // Patch attributes
183     Element* oldElement = static_cast<Element*>(oldNode);
184     Element* newElement = static_cast<Element*>(newNode);
185     if (oldDigest->m_attrsSHA1 != newDigest->m_attrsSHA1) {
186         NamedNodeMap* oldAttributeMap = oldElement->attributeMap();
187
188         while (oldAttributeMap && oldAttributeMap->length())
189             oldAttributeMap->removeAttribute(0);
190
191         NamedNodeMap* newAttributeMap = newElement->attributeMap();
192         if (newAttributeMap) {
193             size_t numAttrs = newAttributeMap->length();
194             for (size_t i = 0; i < numAttrs; ++i) {
195                 const Attribute* attribute = newAttributeMap->attributeItem(i);
196                 oldElement->setAttribute(attribute->name(), attribute->value());
197             }
198         }
199     }
200
201     innerPatchChildren(errorString, oldElement, oldDigest->m_children, newDigest->m_children);
202 }
203
204 pair<DOMEditor::ResultMap, DOMEditor::ResultMap>
205 DOMEditor::diff(Vector<OwnPtr<Digest> >& oldList, Vector<OwnPtr<Digest> >& newList)
206 {
207     ResultMap newMap(newList.size());
208     ResultMap oldMap(oldList.size());
209
210     for (size_t i = 0; i < oldMap.size(); ++i)
211         oldMap[i].first = 0;
212     for (size_t i = 0; i < newMap.size(); ++i)
213         newMap[i].first = 0;
214
215     typedef HashMap<String, Vector<size_t> > DiffTable;
216     DiffTable newTable;
217     DiffTable oldTable;
218
219     for (size_t i = 0; i < newList.size(); ++i) {
220         DiffTable::iterator it = newTable.add(newList[i]->m_sha1, Vector<size_t>()).first;
221         it->second.append(i);
222     }
223
224     for (size_t i = 0; i < oldList.size(); ++i) {
225         DiffTable::iterator it = oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).first;
226         it->second.append(i);
227     }
228
229     for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) {
230         if (newIt->second.size() != 1)
231             continue;
232
233         DiffTable::iterator oldIt = oldTable.find(newIt->first);
234         if (oldIt == oldTable.end() || oldIt->second.size() != 1)
235             continue;
236         make_pair(newList[newIt->second[0]].get(), oldIt->second[0]);
237         newMap[newIt->second[0]] = make_pair(newList[newIt->second[0]].get(), oldIt->second[0]);
238         oldMap[oldIt->second[0]] = make_pair(oldList[oldIt->second[0]].get(), newIt->second[0]);
239     }
240
241     for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
242         if (!newMap[i].first || newMap[i + 1].first)
243             continue;
244
245         size_t j = newMap[i].second + 1;
246         if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == oldList[j]->m_sha1) {
247             newMap[i + 1] = make_pair(newList[i + 1].get(), j);
248             oldMap[j] = make_pair(oldList[j].get(), i + 1);
249         }
250     }
251
252     for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
253         if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
254             continue;
255
256         size_t j = newMap[i].second - 1;
257         if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) {
258             newMap[i - 1] = make_pair(newList[i - 1].get(), j);
259             oldMap[j] = make_pair(oldList[j].get(), i - 1);
260         }
261     }
262     return make_pair(oldMap, newMap);
263 }
264
265 void DOMEditor::innerPatchChildren(ErrorString* errorString, Element* element, Vector<OwnPtr<Digest> >& oldList, Vector<OwnPtr<Digest> >& newList)
266 {
267     // Trim tail.
268     size_t offset = 0;
269     for (; offset < oldList.size() && offset < newList.size() && oldList[oldList.size() - offset - 1]->m_sha1 == newList[newList.size() - offset - 1]->m_sha1; ++offset) { }
270     if (offset > 0) {
271         oldList.resize(oldList.size() - offset);
272         newList.resize(newList.size() - offset);
273     }
274
275     // Trim head.
276     for (offset = 0; offset < oldList.size() && offset < newList.size() && oldList[offset]->m_sha1 == newList[offset]->m_sha1; ++offset) { }
277     if (offset > 0) {
278         oldList.remove(0, offset);
279         newList.remove(0, offset);
280     }
281
282     pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList);
283     ResultMap& oldMap = resultMaps.first;
284     ResultMap& newMap = resultMaps.second;
285
286     HashSet<Digest*> merges;
287     for (size_t i = 0; i < oldList.size(); ++i) {
288         if (oldMap[i].first)
289             continue;
290
291         // Check if this change is between stable nodes. If it is, consider it as "modified".
292         if ((!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
293             size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
294             size_t anchorAfter = i == oldMap.size() - 1 ? anchorCandidate + 1 : oldMap[i + 1].second;
295             if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList.size()) {
296                 innerPatchNode(errorString, oldList[i].get(), newList[anchorCandidate].get());
297                 if (!errorString->isEmpty())
298                     return;
299
300                 merges.add(newList[anchorCandidate].get());
301             } else
302                 element->removeChild(oldList[i]->m_node);
303         } else
304             element->removeChild(oldList[i]->m_node);
305     }
306
307     for (size_t i = 0; i < newMap.size(); ++i) {
308         if (newMap[i].first || merges.contains(newList[i].get()))
309             continue;
310
311         ExceptionCode ec = 0;
312         element->insertBefore(newList[i]->m_node, element->childNode(i + offset), ec);
313         if (ec) {
314             *errorString = exceptionDescription(ec);
315             return;
316         }
317     }
318 }
319
320 static void addStringToSHA1(SHA1& sha1, const String& string)
321 {
322     CString cString = string.utf8();
323     sha1.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
324 }
325
326 PassOwnPtr<DOMEditor::Digest> DOMEditor::createDigest(Node* node)
327 {
328     Digest* digest = new Digest(node);
329
330     SHA1 sha1;
331
332     Node::NodeType nodeType = node->nodeType();
333     sha1.addBytes(reinterpret_cast<const uint8_t*>(&nodeType), sizeof(nodeType));
334     addStringToSHA1(sha1, node->nodeName());
335     addStringToSHA1(sha1, node->nodeValue());
336
337     if (node->nodeType() == Node::ELEMENT_NODE) {
338         Node* child = node->firstChild();
339         while (child) {
340             OwnPtr<Digest> childInfo = createDigest(child);
341             addStringToSHA1(sha1, childInfo->m_sha1);
342             child = child->nextSibling();
343             digest->m_children.append(childInfo.release());
344         }
345         Element* element = static_cast<Element*>(node);
346
347         NamedNodeMap* attrMap = element->attributeMap();
348         if (attrMap && attrMap->length()) {
349             size_t numAttrs = attrMap->length();
350             SHA1 attrsSHA1;
351             for (size_t i = 0; i < numAttrs; ++i) {
352                 const Attribute* attribute = attrMap->attributeItem(i);
353                 addStringToSHA1(attrsSHA1, attribute->name().toString());
354                 addStringToSHA1(attrsSHA1, attribute->value());
355             }
356             Vector<uint8_t, 20> attrsHash;
357             attrsSHA1.computeHash(attrsHash);
358             digest->m_attrsSHA1 = base64Encode(reinterpret_cast<const char*>(attrsHash.data()), 10);
359             addStringToSHA1(sha1, digest->m_attrsSHA1);
360         }
361     }
362
363     Vector<uint8_t, 20> hash;
364     sha1.computeHash(hash);
365     digest->m_sha1 = base64Encode(reinterpret_cast<const char*>(hash.data()), 10);
366     return adoptPtr(digest);
367 }
368
369 } // namespace WebCore
370
371 #endif // ENABLE(INSPECTOR)