OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2012 Google Inc. All rights reserved. | 2 * Copyright (C) 2012 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions are | 5 * modification, are permitted provided that the following conditions are |
6 * met: | 6 * met: |
7 * | 7 * |
8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
56 #include "wtf/text/CString.h" | 56 #include "wtf/text/CString.h" |
57 | 57 |
58 namespace blink { | 58 namespace blink { |
59 | 59 |
60 struct DOMPatchSupport::Digest { | 60 struct DOMPatchSupport::Digest { |
61 explicit Digest(Node* node) : m_node(node) { } | 61 explicit Digest(Node* node) : m_node(node) { } |
62 | 62 |
63 String m_sha1; | 63 String m_sha1; |
64 String m_attrsSHA1; | 64 String m_attrsSHA1; |
65 Node* m_node; | 65 Node* m_node; |
66 Vector<OwnPtr<Digest> > m_children; | 66 Vector<OwnPtr<Digest>> m_children; |
67 }; | 67 }; |
68 | 68 |
69 void DOMPatchSupport::patchDocument(Document& document, const String& markup) | 69 void DOMPatchSupport::patchDocument(Document& document, const String& markup) |
70 { | 70 { |
71 InspectorHistory history; | 71 InspectorHistory history; |
72 DOMEditor domEditor(&history); | 72 DOMEditor domEditor(&history); |
73 DOMPatchSupport patchSupport(&domEditor, document); | 73 DOMPatchSupport patchSupport(&domEditor, document); |
74 patchSupport.patchDocument(markup); | 74 patchSupport.patchDocument(markup); |
75 } | 75 } |
76 | 76 |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
134 Element* targetElement = toElement(targetNode); | 134 Element* targetElement = toElement(targetNode); |
135 | 135 |
136 // FIXME: This code should use one of createFragment* in markup.h | 136 // FIXME: This code should use one of createFragment* in markup.h |
137 if (document().isHTMLDocument()) | 137 if (document().isHTMLDocument()) |
138 fragment->parseHTML(markup, targetElement); | 138 fragment->parseHTML(markup, targetElement); |
139 else | 139 else |
140 fragment->parseXML(markup, targetElement); | 140 fragment->parseXML(markup, targetElement); |
141 | 141 |
142 // Compose the old list. | 142 // Compose the old list. |
143 ContainerNode* parentNode = node->parentNode(); | 143 ContainerNode* parentNode = node->parentNode(); |
144 Vector<OwnPtr<Digest> > oldList; | 144 Vector<OwnPtr<Digest>> oldList; |
145 for (Node* child = parentNode->firstChild(); child; child = child->nextSibli
ng()) | 145 for (Node* child = parentNode->firstChild(); child; child = child->nextSibli
ng()) |
146 oldList.append(createDigest(child, 0)); | 146 oldList.append(createDigest(child, 0)); |
147 | 147 |
148 // Compose the new list. | 148 // Compose the new list. |
149 String markupCopy = markup.lower(); | 149 String markupCopy = markup.lower(); |
150 Vector<OwnPtr<Digest> > newList; | 150 Vector<OwnPtr<Digest>> newList; |
151 for (Node* child = parentNode->firstChild(); child != node; child = child->n
extSibling()) | 151 for (Node* child = parentNode->firstChild(); child != node; child = child->n
extSibling()) |
152 newList.append(createDigest(child, 0)); | 152 newList.append(createDigest(child, 0)); |
153 for (Node* child = fragment->firstChild(); child; child = child->nextSibling
()) { | 153 for (Node* child = fragment->firstChild(); child; child = child->nextSibling
()) { |
154 if (isHTMLHeadElement(*child) && !child->hasChildren() && markupCopy.fin
d("</head>") == kNotFound) | 154 if (isHTMLHeadElement(*child) && !child->hasChildren() && markupCopy.fin
d("</head>") == kNotFound) |
155 continue; // HTML5 parser inserts empty <head> tag whenever it parse
s <body> | 155 continue; // HTML5 parser inserts empty <head> tag whenever it parse
s <body> |
156 if (isHTMLBodyElement(*child) && !child->hasChildren() && markupCopy.fin
d("</body>") == kNotFound) | 156 if (isHTMLBodyElement(*child) && !child->hasChildren() && markupCopy.fin
d("</body>") == kNotFound) |
157 continue; // HTML5 parser inserts empty <body> tag whenever it parse
s </head> | 157 continue; // HTML5 parser inserts empty <body> tag whenever it parse
s </head> |
158 newList.append(createDigest(child, &m_unusedNodesMap)); | 158 newList.append(createDigest(child, &m_unusedNodesMap)); |
159 } | 159 } |
160 for (Node* child = node->nextSibling(); child; child = child->nextSibling()) | 160 for (Node* child = node->nextSibling(); child; child = child->nextSibling()) |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
204 return false; | 204 return false; |
205 } | 205 } |
206 } | 206 } |
207 | 207 |
208 bool result = innerPatchChildren(oldElement, oldDigest->m_children, newDiges
t->m_children, exceptionState); | 208 bool result = innerPatchChildren(oldElement, oldDigest->m_children, newDiges
t->m_children, exceptionState); |
209 m_unusedNodesMap.remove(newDigest->m_sha1); | 209 m_unusedNodesMap.remove(newDigest->m_sha1); |
210 return result; | 210 return result; |
211 } | 211 } |
212 | 212 |
213 pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap> | 213 pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap> |
214 DOMPatchSupport::diff(const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPt
r<Digest> >& newList) | 214 DOMPatchSupport::diff(const Vector<OwnPtr<Digest>>& oldList, const Vector<OwnPtr
<Digest>>& newList) |
215 { | 215 { |
216 ResultMap newMap(newList.size()); | 216 ResultMap newMap(newList.size()); |
217 ResultMap oldMap(oldList.size()); | 217 ResultMap oldMap(oldList.size()); |
218 | 218 |
219 for (size_t i = 0; i < oldMap.size(); ++i) { | 219 for (size_t i = 0; i < oldMap.size(); ++i) { |
220 oldMap[i].first = 0; | 220 oldMap[i].first = 0; |
221 oldMap[i].second = 0; | 221 oldMap[i].second = 0; |
222 } | 222 } |
223 | 223 |
224 for (size_t i = 0; i < newMap.size(); ++i) { | 224 for (size_t i = 0; i < newMap.size(); ++i) { |
(...skipping 10 matching lines...) Expand all Loading... |
235 } | 235 } |
236 for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[oldLi
st.size() - i - 1]->m_sha1 == newList[newList.size() - i - 1]->m_sha1; ++i) { | 236 for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[oldLi
st.size() - i - 1]->m_sha1 == newList[newList.size() - i - 1]->m_sha1; ++i) { |
237 size_t oldIndex = oldList.size() - i - 1; | 237 size_t oldIndex = oldList.size() - i - 1; |
238 size_t newIndex = newList.size() - i - 1; | 238 size_t newIndex = newList.size() - i - 1; |
239 oldMap[oldIndex].first = oldList[oldIndex].get(); | 239 oldMap[oldIndex].first = oldList[oldIndex].get(); |
240 oldMap[oldIndex].second = newIndex; | 240 oldMap[oldIndex].second = newIndex; |
241 newMap[newIndex].first = newList[newIndex].get(); | 241 newMap[newIndex].first = newList[newIndex].get(); |
242 newMap[newIndex].second = oldIndex; | 242 newMap[newIndex].second = oldIndex; |
243 } | 243 } |
244 | 244 |
245 typedef HashMap<String, Vector<size_t> > DiffTable; | 245 typedef HashMap<String, Vector<size_t>> DiffTable; |
246 DiffTable newTable; | 246 DiffTable newTable; |
247 DiffTable oldTable; | 247 DiffTable oldTable; |
248 | 248 |
249 for (size_t i = 0; i < newList.size(); ++i) { | 249 for (size_t i = 0; i < newList.size(); ++i) { |
250 newTable.add(newList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap
pend(i); | 250 newTable.add(newList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap
pend(i); |
251 } | 251 } |
252 | 252 |
253 for (size_t i = 0; i < oldList.size(); ++i) { | 253 for (size_t i = 0; i < oldList.size(); ++i) { |
254 oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap
pend(i); | 254 oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap
pend(i); |
255 } | 255 } |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
289 } | 289 } |
290 | 290 |
291 #ifdef DEBUG_DOM_PATCH_SUPPORT | 291 #ifdef DEBUG_DOM_PATCH_SUPPORT |
292 dumpMap(oldMap, "OLD"); | 292 dumpMap(oldMap, "OLD"); |
293 dumpMap(newMap, "NEW"); | 293 dumpMap(newMap, "NEW"); |
294 #endif | 294 #endif |
295 | 295 |
296 return std::make_pair(oldMap, newMap); | 296 return std::make_pair(oldMap, newMap); |
297 } | 297 } |
298 | 298 |
299 bool DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector
<OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList, ExceptionSta
te& exceptionState) | 299 bool DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector
<OwnPtr<Digest>>& oldList, const Vector<OwnPtr<Digest>>& newList, ExceptionState
& exceptionState) |
300 { | 300 { |
301 pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList); | 301 pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList); |
302 ResultMap& oldMap = resultMaps.first; | 302 ResultMap& oldMap = resultMaps.first; |
303 ResultMap& newMap = resultMaps.second; | 303 ResultMap& newMap = resultMaps.second; |
304 | 304 |
305 Digest* oldHead = nullptr; | 305 Digest* oldHead = nullptr; |
306 Digest* oldBody = nullptr; | 306 Digest* oldBody = nullptr; |
307 | 307 |
308 // 1. First strip everything except for the nodes that retain. Collect pendi
ng merges. | 308 // 1. First strip everything except for the nodes that retain. Collect pendi
ng merges. |
309 HashMap<Digest*, Digest*> merges; | 309 HashMap<Digest*, Digest*> merges; |
310 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz
e_t> > usedNewOrdinals; | 310 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz
e_t>> usedNewOrdinals; |
311 for (size_t i = 0; i < oldList.size(); ++i) { | 311 for (size_t i = 0; i < oldList.size(); ++i) { |
312 if (oldMap[i].first) { | 312 if (oldMap[i].first) { |
313 if (usedNewOrdinals.add(oldMap[i].second).isNewEntry) | 313 if (usedNewOrdinals.add(oldMap[i].second).isNewEntry) |
314 continue; | 314 continue; |
315 oldMap[i].first = 0; | 315 oldMap[i].first = 0; |
316 oldMap[i].second = 0; | 316 oldMap[i].second = 0; |
317 } | 317 } |
318 | 318 |
319 // Always match <head> and <body> tags with each other - we can't remove
them from the DOM | 319 // Always match <head> and <body> tags with each other - we can't remove
them from the DOM |
320 // upon patching. | 320 // upon patching. |
(...skipping 16 matching lines...) Expand all Loading... |
337 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) | 337 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) |
338 return false; | 338 return false; |
339 } | 339 } |
340 } else { | 340 } else { |
341 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) | 341 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) |
342 return false; | 342 return false; |
343 } | 343 } |
344 } | 344 } |
345 | 345 |
346 // Mark retained nodes as used, do not reuse node more than once. | 346 // Mark retained nodes as used, do not reuse node more than once. |
347 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz
e_t> > usedOldOrdinals; | 347 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz
e_t>> usedOldOrdinals; |
348 for (size_t i = 0; i < newList.size(); ++i) { | 348 for (size_t i = 0; i < newList.size(); ++i) { |
349 if (!newMap[i].first) | 349 if (!newMap[i].first) |
350 continue; | 350 continue; |
351 size_t oldOrdinal = newMap[i].second; | 351 size_t oldOrdinal = newMap[i].second; |
352 if (usedOldOrdinals.contains(oldOrdinal)) { | 352 if (usedOldOrdinals.contains(oldOrdinal)) { |
353 // Do not map node more than once | 353 // Do not map node more than once |
354 newMap[i].first = 0; | 354 newMap[i].first = 0; |
355 newMap[i].second = 0; | 355 newMap[i].second = 0; |
356 continue; | 356 continue; |
357 } | 357 } |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
507 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name) | 507 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name) |
508 { | 508 { |
509 fprintf(stderr, "\n\n"); | 509 fprintf(stderr, "\n\n"); |
510 for (size_t i = 0; i < map.size(); ++i) | 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); | 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 } | 512 } |
513 #endif | 513 #endif |
514 | 514 |
515 } // namespace blink | 515 } // namespace blink |
516 | 516 |
OLD | NEW |