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