Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(116)

Side by Side Diff: Source/core/inspector/DOMPatchSupport.cpp

Issue 329183002: Removing "using" declarations that import names in the C++ Standard library. (Closed) Base URL: https://chromium.googlesource.com/chromium/blink.git@master
Patch Set: Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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 36 matching lines...) Expand 10 before | Expand all | Expand 10 after
47 #include "core/inspector/InspectorHistory.h" 47 #include "core/inspector/InspectorHistory.h"
48 #include "core/xml/parser/XMLDocumentParser.h" 48 #include "core/xml/parser/XMLDocumentParser.h"
49 #include "platform/Crypto.h" 49 #include "platform/Crypto.h"
50 #include "public/platform/Platform.h" 50 #include "public/platform/Platform.h"
51 #include "wtf/Deque.h" 51 #include "wtf/Deque.h"
52 #include "wtf/HashTraits.h" 52 #include "wtf/HashTraits.h"
53 #include "wtf/RefPtr.h" 53 #include "wtf/RefPtr.h"
54 #include "wtf/text/Base64.h" 54 #include "wtf/text/Base64.h"
55 #include "wtf/text/CString.h" 55 #include "wtf/text/CString.h"
56 56
57 using namespace std;
58
59 namespace WebCore { 57 namespace WebCore {
60 58
61 struct DOMPatchSupport::Digest { 59 struct DOMPatchSupport::Digest {
62 explicit Digest(Node* node) : m_node(node) { } 60 explicit Digest(Node* node) : m_node(node) { }
63 61
64 String m_sha1; 62 String m_sha1;
65 String m_attrsSHA1; 63 String m_attrsSHA1;
66 Node* m_node; 64 Node* m_node;
67 Vector<OwnPtr<Digest> > m_children; 65 Vector<OwnPtr<Digest> > m_children;
68 }; 66 };
(...skipping 143 matching lines...) Expand 10 before | Expand all | Expand 10 after
212 m_unusedNodesMap.remove(newDigest->m_sha1); 210 m_unusedNodesMap.remove(newDigest->m_sha1);
213 return result; 211 return result;
214 } 212 }
215 213
216 pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap> 214 pair<DOMPatchSupport::ResultMap, DOMPatchSupport::ResultMap>
217 DOMPatchSupport::diff(const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPt r<Digest> >& newList) 215 DOMPatchSupport::diff(const Vector<OwnPtr<Digest> >& oldList, const Vector<OwnPt r<Digest> >& newList)
218 { 216 {
219 ResultMap newMap(newList.size()); 217 ResultMap newMap(newList.size());
220 ResultMap oldMap(oldList.size()); 218 ResultMap oldMap(oldList.size());
221 219
222 for (size_t i = 0; i < oldMap.size(); ++i) { 220 for (std::size_t i = 0; i < oldMap.size(); ++i) {
223 oldMap[i].first = 0; 221 oldMap[i].first = 0;
224 oldMap[i].second = 0; 222 oldMap[i].second = 0;
225 } 223 }
226 224
227 for (size_t i = 0; i < newMap.size(); ++i) { 225 for (std::size_t i = 0; i < newMap.size(); ++i) {
228 newMap[i].first = 0; 226 newMap[i].first = 0;
229 newMap[i].second = 0; 227 newMap[i].second = 0;
230 } 228 }
231 229
232 // Trim head and tail. 230 // Trim head and tail.
233 for (size_t i = 0; i < oldList.size() && i < newList.size() && oldList[i]->m _sha1 == newList[i]->m_sha1; ++i) { 231 for (std::size_t i = 0; i < oldList.size() && i < newList.size() && oldList[ i]->m_sha1 == newList[i]->m_sha1; ++i) {
234 oldMap[i].first = oldList[i].get(); 232 oldMap[i].first = oldList[i].get();
235 oldMap[i].second = i; 233 oldMap[i].second = i;
236 newMap[i].first = newList[i].get(); 234 newMap[i].first = newList[i].get();
237 newMap[i].second = i; 235 newMap[i].second = i;
238 } 236 }
239 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 for (std::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) {
240 size_t oldIndex = oldList.size() - i - 1; 238 std::size_t oldIndex = oldList.size() - i - 1;
241 size_t newIndex = newList.size() - i - 1; 239 std::size_t newIndex = newList.size() - i - 1;
242 oldMap[oldIndex].first = oldList[oldIndex].get(); 240 oldMap[oldIndex].first = oldList[oldIndex].get();
243 oldMap[oldIndex].second = newIndex; 241 oldMap[oldIndex].second = newIndex;
244 newMap[newIndex].first = newList[newIndex].get(); 242 newMap[newIndex].first = newList[newIndex].get();
245 newMap[newIndex].second = oldIndex; 243 newMap[newIndex].second = oldIndex;
246 } 244 }
247 245
248 typedef HashMap<String, Vector<size_t> > DiffTable; 246 typedef HashMap<String, Vector<std::size_t> > DiffTable;
249 DiffTable newTable; 247 DiffTable newTable;
250 DiffTable oldTable; 248 DiffTable oldTable;
251 249
252 for (size_t i = 0; i < newList.size(); ++i) { 250 for (std::size_t i = 0; i < newList.size(); ++i) {
253 newTable.add(newList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap pend(i); 251 newTable.add(newList[i]->m_sha1, Vector<std::size_t>()).storedValue->val ue.append(i);
254 } 252 }
255 253
256 for (size_t i = 0; i < oldList.size(); ++i) { 254 for (std::size_t i = 0; i < oldList.size(); ++i) {
257 oldTable.add(oldList[i]->m_sha1, Vector<size_t>()).storedValue->value.ap pend(i); 255 oldTable.add(oldList[i]->m_sha1, Vector<std::size_t>()).storedValue->val ue.append(i);
258 } 256 }
259 257
260 for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) { 258 for (DiffTable::iterator newIt = newTable.begin(); newIt != newTable.end(); ++newIt) {
261 if (newIt->value.size() != 1) 259 if (newIt->value.size() != 1)
262 continue; 260 continue;
263 261
264 DiffTable::iterator oldIt = oldTable.find(newIt->key); 262 DiffTable::iterator oldIt = oldTable.find(newIt->key);
265 if (oldIt == oldTable.end() || oldIt->value.size() != 1) 263 if (oldIt == oldTable.end() || oldIt->value.size() != 1)
266 continue; 264 continue;
267 265
268 newMap[newIt->value[0]] = make_pair(newList[newIt->value[0]].get(), oldI t->value[0]); 266 newMap[newIt->value[0]] = std::make_pair(newList[newIt->value[0]].get(), oldIt->value[0]);
269 oldMap[oldIt->value[0]] = make_pair(oldList[oldIt->value[0]].get(), newI t->value[0]); 267 oldMap[oldIt->value[0]] = std::make_pair(oldList[oldIt->value[0]].get(), newIt->value[0]);
270 } 268 }
271 269
272 for (size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) { 270 for (std::size_t i = 0; newList.size() > 0 && i < newList.size() - 1; ++i) {
273 if (!newMap[i].first || newMap[i + 1].first) 271 if (!newMap[i].first || newMap[i + 1].first)
274 continue; 272 continue;
275 273
276 size_t j = newMap[i].second + 1; 274 std::size_t j = newMap[i].second + 1;
277 if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == o ldList[j]->m_sha1) { 275 if (j < oldMap.size() && !oldMap[j].first && newList[i + 1]->m_sha1 == o ldList[j]->m_sha1) {
278 newMap[i + 1] = make_pair(newList[i + 1].get(), j); 276 newMap[i + 1] = std::make_pair(newList[i + 1].get(), j);
279 oldMap[j] = make_pair(oldList[j].get(), i + 1); 277 oldMap[j] = std::make_pair(oldList[j].get(), i + 1);
280 } 278 }
281 } 279 }
282 280
283 for (size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) { 281 for (std::size_t i = newList.size() - 1; newList.size() > 0 && i > 0; --i) {
284 if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0) 282 if (!newMap[i].first || newMap[i - 1].first || newMap[i].second <= 0)
285 continue; 283 continue;
286 284
287 size_t j = newMap[i].second - 1; 285 std::size_t j = newMap[i].second - 1;
288 if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) { 286 if (!oldMap[j].first && newList[i - 1]->m_sha1 == oldList[j]->m_sha1) {
289 newMap[i - 1] = make_pair(newList[i - 1].get(), j); 287 newMap[i - 1] = std::make_pair(newList[i - 1].get(), j);
290 oldMap[j] = make_pair(oldList[j].get(), i - 1); 288 oldMap[j] = std::make_pair(oldList[j].get(), i - 1);
291 } 289 }
292 } 290 }
293 291
294 #ifdef DEBUG_DOM_PATCH_SUPPORT 292 #ifdef DEBUG_DOM_PATCH_SUPPORT
295 dumpMap(oldMap, "OLD"); 293 dumpMap(oldMap, "OLD");
296 dumpMap(newMap, "NEW"); 294 dumpMap(newMap, "NEW");
297 #endif 295 #endif
298 296
299 return make_pair(oldMap, newMap); 297 return std::make_pair(oldMap, newMap);
300 } 298 }
301 299
302 bool DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector <OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList, ExceptionSta te& exceptionState) 300 bool DOMPatchSupport::innerPatchChildren(ContainerNode* parentNode, const Vector <OwnPtr<Digest> >& oldList, const Vector<OwnPtr<Digest> >& newList, ExceptionSta te& exceptionState)
303 { 301 {
304 pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList); 302 pair<ResultMap, ResultMap> resultMaps = diff(oldList, newList);
305 ResultMap& oldMap = resultMaps.first; 303 ResultMap& oldMap = resultMaps.first;
306 ResultMap& newMap = resultMaps.second; 304 ResultMap& newMap = resultMaps.second;
307 305
308 Digest* oldHead = 0; 306 Digest* oldHead = 0;
309 Digest* oldBody = 0; 307 Digest* oldBody = 0;
310 308
311 // 1. First strip everything except for the nodes that retain. Collect pendi ng merges. 309 // 1. First strip everything except for the nodes that retain. Collect pendi ng merges.
312 HashMap<Digest*, Digest*> merges; 310 HashMap<Digest*, Digest*> merges;
313 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz e_t> > usedNewOrdinals; 311 HashSet<std::size_t, WTF::IntHash<std::size_t>, WTF::UnsignedWithZeroKeyHash Traits<std::size_t> > usedNewOrdinals;
314 for (size_t i = 0; i < oldList.size(); ++i) { 312 for (std::size_t i = 0; i < oldList.size(); ++i) {
315 if (oldMap[i].first) { 313 if (oldMap[i].first) {
316 if (usedNewOrdinals.add(oldMap[i].second).isNewEntry) 314 if (usedNewOrdinals.add(oldMap[i].second).isNewEntry)
317 continue; 315 continue;
318 oldMap[i].first = 0; 316 oldMap[i].first = 0;
319 oldMap[i].second = 0; 317 oldMap[i].second = 0;
320 } 318 }
321 319
322 // Always match <head> and <body> tags with each other - we can't remove them from the DOM 320 // Always match <head> and <body> tags with each other - we can't remove them from the DOM
323 // upon patching. 321 // upon patching.
324 if (isHTMLHeadElement(*oldList[i]->m_node)) { 322 if (isHTMLHeadElement(*oldList[i]->m_node)) {
325 oldHead = oldList[i].get(); 323 oldHead = oldList[i].get();
326 continue; 324 continue;
327 } 325 }
328 if (isHTMLBodyElement(*oldList[i]->m_node)) { 326 if (isHTMLBodyElement(*oldList[i]->m_node)) {
329 oldBody = oldList[i].get(); 327 oldBody = oldList[i].get();
330 continue; 328 continue;
331 } 329 }
332 330
333 // Check if this change is between stable nodes. If it is, consider it a s "modified". 331 // Check if this change is between stable nodes. If it is, consider it a s "modified".
334 if (!m_unusedNodesMap.contains(oldList[i]->m_sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) { 332 if (!m_unusedNodesMap.contains(oldList[i]->m_sha1) && (!i || oldMap[i - 1].first) && (i == oldMap.size() - 1 || oldMap[i + 1].first)) {
335 size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0; 333 std::size_t anchorCandidate = i ? oldMap[i - 1].second + 1 : 0;
336 size_t anchorAfter = (i == oldMap.size() - 1) ? anchorCandidate + 1 : oldMap[i + 1].second; 334 std::size_t anchorAfter = (i == oldMap.size() - 1) ? anchorCandidate + 1 : oldMap[i + 1].second;
337 if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList. size()) 335 if (anchorAfter - anchorCandidate == 1 && anchorCandidate < newList. size())
338 merges.set(newList[anchorCandidate].get(), oldList[i].get()); 336 merges.set(newList[anchorCandidate].get(), oldList[i].get());
339 else { 337 else {
340 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) 338 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState))
341 return false; 339 return false;
342 } 340 }
343 } else { 341 } else {
344 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState)) 342 if (!removeChildAndMoveToNew(oldList[i].get(), exceptionState))
345 return false; 343 return false;
346 } 344 }
347 } 345 }
348 346
349 // Mark retained nodes as used, do not reuse node more than once. 347 // Mark retained nodes as used, do not reuse node more than once.
350 HashSet<size_t, WTF::IntHash<size_t>, WTF::UnsignedWithZeroKeyHashTraits<siz e_t> > usedOldOrdinals; 348 HashSet<std::size_t, WTF::IntHash<std::size_t>, WTF::UnsignedWithZeroKeyHash Traits<std::size_t> > usedOldOrdinals;
351 for (size_t i = 0; i < newList.size(); ++i) { 349 for (std::size_t i = 0; i < newList.size(); ++i) {
352 if (!newMap[i].first) 350 if (!newMap[i].first)
353 continue; 351 continue;
354 size_t oldOrdinal = newMap[i].second; 352 std::size_t oldOrdinal = newMap[i].second;
355 if (usedOldOrdinals.contains(oldOrdinal)) { 353 if (usedOldOrdinals.contains(oldOrdinal)) {
356 // Do not map node more than once 354 // Do not map node more than once
357 newMap[i].first = 0; 355 newMap[i].first = 0;
358 newMap[i].second = 0; 356 newMap[i].second = 0;
359 continue; 357 continue;
360 } 358 }
361 usedOldOrdinals.add(oldOrdinal); 359 usedOldOrdinals.add(oldOrdinal);
362 markNodeAsUsed(newMap[i].first); 360 markNodeAsUsed(newMap[i].first);
363 } 361 }
364 362
365 // Mark <head> and <body> nodes for merge. 363 // Mark <head> and <body> nodes for merge.
366 if (oldHead || oldBody) { 364 if (oldHead || oldBody) {
367 for (size_t i = 0; i < newList.size(); ++i) { 365 for (std::size_t i = 0; i < newList.size(); ++i) {
368 if (oldHead && isHTMLHeadElement(*newList[i]->m_node)) 366 if (oldHead && isHTMLHeadElement(*newList[i]->m_node))
369 merges.set(newList[i].get(), oldHead); 367 merges.set(newList[i].get(), oldHead);
370 if (oldBody && isHTMLBodyElement(*newList[i]->m_node)) 368 if (oldBody && isHTMLBodyElement(*newList[i]->m_node))
371 merges.set(newList[i].get(), oldBody); 369 merges.set(newList[i].get(), oldBody);
372 } 370 }
373 } 371 }
374 372
375 // 2. Patch nodes marked for merge. 373 // 2. Patch nodes marked for merge.
376 for (HashMap<Digest*, Digest*>::iterator it = merges.begin(); it != merges.e nd(); ++it) { 374 for (HashMap<Digest*, Digest*>::iterator it = merges.begin(); it != merges.e nd(); ++it) {
377 if (!innerPatchNode(it->value, it->key, exceptionState)) 375 if (!innerPatchNode(it->value, it->key, exceptionState))
378 return false; 376 return false;
379 } 377 }
380 378
381 // 3. Insert missing nodes. 379 // 3. Insert missing nodes.
382 for (size_t i = 0; i < newMap.size(); ++i) { 380 for (std::size_t i = 0; i < newMap.size(); ++i) {
383 if (newMap[i].first || merges.contains(newList[i].get())) 381 if (newMap[i].first || merges.contains(newList[i].get()))
384 continue; 382 continue;
385 if (!insertBeforeAndMarkAsUsed(parentNode, newList[i].get(), parentNode- >traverseToChildAt(i), exceptionState)) 383 if (!insertBeforeAndMarkAsUsed(parentNode, newList[i].get(), parentNode- >traverseToChildAt(i), exceptionState))
386 return false; 384 return false;
387 } 385 }
388 386
389 // 4. Then put all nodes that retained into their slots (sort by new index). 387 // 4. Then put all nodes that retained into their slots (sort by new index).
390 for (size_t i = 0; i < oldMap.size(); ++i) { 388 for (std::size_t i = 0; i < oldMap.size(); ++i) {
391 if (!oldMap[i].first) 389 if (!oldMap[i].first)
392 continue; 390 continue;
393 RefPtrWillBeRawPtr<Node> node = oldMap[i].first->m_node; 391 RefPtrWillBeRawPtr<Node> node = oldMap[i].first->m_node;
394 Node* anchorNode = parentNode->traverseToChildAt(oldMap[i].second); 392 Node* anchorNode = parentNode->traverseToChildAt(oldMap[i].second);
395 if (node == anchorNode) 393 if (node == anchorNode)
396 continue; 394 continue;
397 if (isHTMLBodyElement(*node) || isHTMLHeadElement(*node)) 395 if (isHTMLBodyElement(*node) || isHTMLHeadElement(*node))
398 continue; // Never move head or body, move the rest of the nodes aro und them. 396 continue; // Never move head or body, move the rest of the nodes aro und them.
399 397
400 if (!m_domEditor->insertBefore(parentNode, node.release(), anchorNode, e xceptionState)) 398 if (!m_domEditor->insertBefore(parentNode, node.release(), anchorNode, e xceptionState))
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after
474 if (it != m_unusedNodesMap.end()) { 472 if (it != m_unusedNodesMap.end()) {
475 Digest* newDigest = it->value; 473 Digest* newDigest = it->value;
476 Node* newNode = newDigest->m_node; 474 Node* newNode = newDigest->m_node;
477 if (!m_domEditor->replaceChild(newNode->parentNode(), oldNode, newNode, exceptionState)) 475 if (!m_domEditor->replaceChild(newNode->parentNode(), oldNode, newNode, exceptionState))
478 return false; 476 return false;
479 newDigest->m_node = oldNode.get(); 477 newDigest->m_node = oldNode.get();
480 markNodeAsUsed(newDigest); 478 markNodeAsUsed(newDigest);
481 return true; 479 return true;
482 } 480 }
483 481
484 for (size_t i = 0; i < oldDigest->m_children.size(); ++i) { 482 for (std::size_t i = 0; i < oldDigest->m_children.size(); ++i) {
485 if (!removeChildAndMoveToNew(oldDigest->m_children[i].get(), exceptionSt ate)) 483 if (!removeChildAndMoveToNew(oldDigest->m_children[i].get(), exceptionSt ate))
486 return false; 484 return false;
487 } 485 }
488 return true; 486 return true;
489 } 487 }
490 488
491 void DOMPatchSupport::markNodeAsUsed(Digest* digest) 489 void DOMPatchSupport::markNodeAsUsed(Digest* digest)
492 { 490 {
493 Deque<Digest*> queue; 491 Deque<Digest*> queue;
494 queue.append(digest); 492 queue.append(digest);
495 while (!queue.isEmpty()) { 493 while (!queue.isEmpty()) {
496 Digest* first = queue.takeFirst(); 494 Digest* first = queue.takeFirst();
497 m_unusedNodesMap.remove(first->m_sha1); 495 m_unusedNodesMap.remove(first->m_sha1);
498 for (size_t i = 0; i < first->m_children.size(); ++i) 496 for (std::size_t i = 0; i < first->m_children.size(); ++i)
499 queue.append(first->m_children[i].get()); 497 queue.append(first->m_children[i].get());
500 } 498 }
501 } 499 }
502 500
503 #ifdef DEBUG_DOM_PATCH_SUPPORT 501 #ifdef DEBUG_DOM_PATCH_SUPPORT
504 static String nodeName(Node* node) 502 static String nodeName(Node* node)
505 { 503 {
506 if (node->document().isXHTMLDocument()) 504 if (node->document().isXHTMLDocument())
507 return node->nodeName(); 505 return node->nodeName();
508 return node->nodeName().lower(); 506 return node->nodeName().lower();
509 } 507 }
510 508
511 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name) 509 void DOMPatchSupport::dumpMap(const ResultMap& map, const String& name)
512 { 510 {
513 fprintf(stderr, "\n\n"); 511 fprintf(stderr, "\n\n");
514 for (size_t i = 0; i < map.size(); ++i) 512 for (std::size_t i = 0; i < map.size(); ++i)
515 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); 513 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);
516 } 514 }
517 #endif 515 #endif
518 516
519 } // namespace WebCore 517 } // namespace WebCore
520 518
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698