From dca970e2144c3f5d5bf3118fbd11b54a62b548e9 Mon Sep 17 00:00:00 2001 From: "yurys@chromium.org" Date: Fri, 13 Apr 2012 13:50:43 +0000 Subject: [PATCH] Web Inspector: exception in heap profiler when expanding a class in summary view https://bugs.webkit.org/show_bug.cgi?id=83883 Moved all DOM-specific inspector utilities into DOMExtension.js Merged BinarySearch.js and PartialQuickSort.js into utilities.js, HeapSnapshotWorker.js now imports utilities.js which contains all required routines. Reviewed by Pavel Feldman. * WebCore.gypi: * WebCore.vcproj/WebCore.vcproj: * inspector/compile-front-end.py: * inspector/front-end/BinarySearch.js: Removed. * inspector/front-end/DOMExtension.js: Copied from Source/WebCore/inspector/front-end/utilities.js. (Node.prototype.rangeOfWord): (Node.prototype.traverseNextTextNode): (Node.prototype.rangeBoundaryForOffset): (Element.prototype.removeStyleClass): (Element.prototype.removeMatchingStyleClasses): (Element.prototype.addStyleClass): (Element.prototype.hasStyleClass): (Element.prototype.positionAt): (Element.prototype.pruneEmptyTextNodes): (Element.prototype.isScrolledToBottom): (Node.prototype.enclosingNodeOrSelfWithNodeNameInArray): (Node.prototype.enclosingNodeOrSelfWithNodeName): (Node.prototype.enclosingNodeOrSelfWithClass): (Node.prototype.enclosingNodeWithClass): (Element.prototype.query): (Element.prototype.removeChildren): (Element.prototype.isInsertionCaretInside): (Element.prototype.createChild): (Element.prototype.totalOffsetLeft): (Element.prototype.totalOffsetTop): (Element.prototype.totalOffset): (Element.prototype.scrollOffset): (AnchorBox): (Element.prototype.offsetRelativeToWindow): (Element.prototype.boxInWindow): (Element.prototype.setTextAndTitle): (Event.prototype.consume): (Text.prototype.select): (Element.prototype.selectionLeftOffset): (Node.prototype.isAncestor): (Node.prototype.isDescendant): (Node.prototype.isSelfOrAncestor): (Node.prototype.isSelfOrDescendant): (Node.prototype.traverseNextNode): (Node.prototype.traversePreviousNode): (HTMLTextAreaElement.prototype.moveCursorToEnd): (isEnterKey): (consumeEvent): (highlightSearchResult): (highlightSearchResults): (highlightRangesWithStyleClass): (applyDomChanges): (revertDomChanges): * inspector/front-end/HeapSnapshot.js: Fixed a couple of js compiler warnings by describing structure of heap snapshot header in the protocol. (WebInspector.HeapSnapshotLoader.prototype.pushJSONChunk): * inspector/front-end/HeapSnapshotWorker.js: * inspector/front-end/PartialQuickSort.js: Removed. * inspector/front-end/WebKit.qrc: * inspector/front-end/inspector.html: * inspector/front-end/utilities.js: (.): git-svn-id: http://svn.webkit.org/repository/webkit/trunk@114126 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- .../inspector/utilities-highlight-results.html | 6 +- Source/WebCore/ChangeLog | 70 ++ Source/WebCore/WebCore.gypi | 5 +- Source/WebCore/WebCore.vcproj/WebCore.vcproj | 12 +- Source/WebCore/inspector/compile-front-end.py | 3 +- .../front-end/AdvancedSearchController.js | 4 +- Source/WebCore/inspector/front-end/BinarySearch.js | 86 --- .../WebCore/inspector/front-end/ConsoleMessage.js | 2 +- Source/WebCore/inspector/front-end/ConsoleView.js | 2 +- Source/WebCore/inspector/front-end/DOMExtension.js | 507 +++++++++++++++ .../inspector/front-end/ElementsTreeOutline.js | 2 +- .../front-end/FilteredItemSelectionDialog.js | 4 +- Source/WebCore/inspector/front-end/HeapSnapshot.js | 15 +- .../inspector/front-end/HeapSnapshotWorker.js | 3 +- .../inspector/front-end/JavaScriptSourceFrame.js | 2 +- Source/WebCore/inspector/front-end/NetworkPanel.js | 4 +- .../inspector/front-end/PartialQuickSort.js | 51 -- Source/WebCore/inspector/front-end/TextViewer.js | 2 +- Source/WebCore/inspector/front-end/UIUtils.js | 138 ++++ Source/WebCore/inspector/front-end/WebKit.qrc | 3 +- Source/WebCore/inspector/front-end/inspector.html | 3 +- Source/WebCore/inspector/front-end/utilities.js | 703 +++------------------ 22 files changed, 841 insertions(+), 786 deletions(-) delete mode 100644 Source/WebCore/inspector/front-end/BinarySearch.js create mode 100644 Source/WebCore/inspector/front-end/DOMExtension.js delete mode 100644 Source/WebCore/inspector/front-end/PartialQuickSort.js diff --git a/LayoutTests/inspector/utilities-highlight-results.html b/LayoutTests/inspector/utilities-highlight-results.html index 21b2353..c3539a1 100644 --- a/LayoutTests/inspector/utilities-highlight-results.html +++ b/LayoutTests/inspector/utilities-highlight-results.html @@ -40,11 +40,11 @@ function test() { var changes = []; InspectorTest.addResult("--------- Running test: ----------"); - highlightRangesWithStyleClass(element, ranges, "highlighted", changes); + WebInspector.highlightRangesWithStyleClass(element, ranges, "highlighted", changes); InspectorTest.addResult("After highlight: " + dumpTextNodesAsString(element)); - revertDomChanges(changes); + WebInspector.revertDomChanges(changes); InspectorTest.addResult("After revert: " + dumpTextNodesAsString(element)); - applyDomChanges(changes); + WebInspector.applyDomChanges(changes); InspectorTest.addResult("After apply: " + dumpTextNodesAsString(element)); } diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog index bea8ba1..49c721a 100644 --- a/Source/WebCore/ChangeLog +++ b/Source/WebCore/ChangeLog @@ -1,3 +1,73 @@ +2012-04-13 Yury Semikhatsky + + Web Inspector: exception in heap profiler when expanding a class in summary view + https://bugs.webkit.org/show_bug.cgi?id=83883 + + Moved all DOM-specific inspector utilities into DOMExtension.js + + Merged BinarySearch.js and PartialQuickSort.js into utilities.js, HeapSnapshotWorker.js now + imports utilities.js which contains all required routines. + + Reviewed by Pavel Feldman. + + * WebCore.gypi: + * WebCore.vcproj/WebCore.vcproj: + * inspector/compile-front-end.py: + * inspector/front-end/BinarySearch.js: Removed. + * inspector/front-end/DOMExtension.js: Copied from Source/WebCore/inspector/front-end/utilities.js. + (Node.prototype.rangeOfWord): + (Node.prototype.traverseNextTextNode): + (Node.prototype.rangeBoundaryForOffset): + (Element.prototype.removeStyleClass): + (Element.prototype.removeMatchingStyleClasses): + (Element.prototype.addStyleClass): + (Element.prototype.hasStyleClass): + (Element.prototype.positionAt): + (Element.prototype.pruneEmptyTextNodes): + (Element.prototype.isScrolledToBottom): + (Node.prototype.enclosingNodeOrSelfWithNodeNameInArray): + (Node.prototype.enclosingNodeOrSelfWithNodeName): + (Node.prototype.enclosingNodeOrSelfWithClass): + (Node.prototype.enclosingNodeWithClass): + (Element.prototype.query): + (Element.prototype.removeChildren): + (Element.prototype.isInsertionCaretInside): + (Element.prototype.createChild): + (Element.prototype.totalOffsetLeft): + (Element.prototype.totalOffsetTop): + (Element.prototype.totalOffset): + (Element.prototype.scrollOffset): + (AnchorBox): + (Element.prototype.offsetRelativeToWindow): + (Element.prototype.boxInWindow): + (Element.prototype.setTextAndTitle): + (Event.prototype.consume): + (Text.prototype.select): + (Element.prototype.selectionLeftOffset): + (Node.prototype.isAncestor): + (Node.prototype.isDescendant): + (Node.prototype.isSelfOrAncestor): + (Node.prototype.isSelfOrDescendant): + (Node.prototype.traverseNextNode): + (Node.prototype.traversePreviousNode): + (HTMLTextAreaElement.prototype.moveCursorToEnd): + (isEnterKey): + (consumeEvent): + (highlightSearchResult): + (highlightSearchResults): + (highlightRangesWithStyleClass): + (applyDomChanges): + (revertDomChanges): + * inspector/front-end/HeapSnapshot.js: Fixed a couple of js compiler warnings + by describing structure of heap snapshot header in the protocol. + (WebInspector.HeapSnapshotLoader.prototype.pushJSONChunk): + * inspector/front-end/HeapSnapshotWorker.js: + * inspector/front-end/PartialQuickSort.js: Removed. + * inspector/front-end/WebKit.qrc: + * inspector/front-end/inspector.html: + * inspector/front-end/utilities.js: + (.): + 2012-04-13 Sheriff Bot Unreviewed, rolling out r114103. diff --git a/Source/WebCore/WebCore.gypi b/Source/WebCore/WebCore.gypi index 2f544f3..45a0e61 100644 --- a/Source/WebCore/WebCore.gypi +++ b/Source/WebCore/WebCore.gypi @@ -6274,7 +6274,6 @@ 'inspector/front-end/AuditResultView.js', 'inspector/front-end/AuditRules.js', 'inspector/front-end/AuditsPanel.js', - 'inspector/front-end/BinarySearch.js', 'inspector/front-end/BottomUpProfileDataGridTree.js', 'inspector/front-end/BreakpointManager.js', 'inspector/front-end/BreakpointsSidebarPane.js', @@ -6286,7 +6285,6 @@ 'inspector/front-end/ConsoleModel.js', 'inspector/front-end/ConsolePanel.js', 'inspector/front-end/ConsoleView.js', - 'inspector/front-end/JavaScriptContextManager.js', 'inspector/front-end/ContentProviders.js', 'inspector/front-end/ContextMenu.js', 'inspector/front-end/CookieItemsView.js', @@ -6307,6 +6305,7 @@ 'inspector/front-end/Dialog.js', 'inspector/front-end/DOMAgent.js', 'inspector/front-end/DOMBreakpointsSidebarPane.js', + 'inspector/front-end/DOMExtension.js', 'inspector/front-end/DOMPresentationUtils.js', 'inspector/front-end/DOMStorage.js', 'inspector/front-end/DOMStorageItemsView.js', @@ -6340,6 +6339,7 @@ 'inspector/front-end/InspectorView.js', 'inspector/front-end/InjectedFakeWorker.js', 'inspector/front-end/inspector.js', + 'inspector/front-end/JavaScriptContextManager.js', 'inspector/front-end/JavaScriptFormatter.js', 'inspector/front-end/JavaScriptSourceFrame.js', 'inspector/front-end/KeyboardShortcut.js', @@ -6355,7 +6355,6 @@ 'inspector/front-end/ObjectPropertiesSection.js', 'inspector/front-end/Panel.js', 'inspector/front-end/PanelEnablerView.js', - 'inspector/front-end/PartialQuickSort.js', 'inspector/front-end/Placard.js', 'inspector/front-end/Popover.js', 'inspector/front-end/ProfileDataGridTree.js', diff --git a/Source/WebCore/WebCore.vcproj/WebCore.vcproj b/Source/WebCore/WebCore.vcproj/WebCore.vcproj index b0abe7e..d993032 100755 --- a/Source/WebCore/WebCore.vcproj/WebCore.vcproj +++ b/Source/WebCore/WebCore.vcproj/WebCore.vcproj @@ -73649,10 +73649,6 @@ > - - @@ -73785,6 +73781,10 @@ > + + @@ -74033,10 +74033,6 @@ > - - diff --git a/Source/WebCore/inspector/compile-front-end.py b/Source/WebCore/inspector/compile-front-end.py index 54939a6..5ce21e9 100755 --- a/Source/WebCore/inspector/compile-front-end.py +++ b/Source/WebCore/inspector/compile-front-end.py @@ -37,6 +37,7 @@ modules = [ "target_name": "util", "dependencies": [], "sources": [ + "DOMExtension.js", "utilities.js", "treeoutline.js", ] @@ -45,9 +46,7 @@ modules = [ "target_name": "common", "dependencies": ["util"], "sources": [ - "BinarySearch.js", "Object.js", - "PartialQuickSort.js", "Settings.js", "UserMetrics.js", "HandlerRegistry.js", diff --git a/Source/WebCore/inspector/front-end/AdvancedSearchController.js b/Source/WebCore/inspector/front-end/AdvancedSearchController.js index 9a8ab59..d846413 100644 --- a/Source/WebCore/inspector/front-end/AdvancedSearchController.js +++ b/Source/WebCore/inspector/front-end/AdvancedSearchController.js @@ -681,7 +681,7 @@ WebInspector.FileBasedSearchResultsPane.prototype = { var contentSpan = document.createElement("span"); contentSpan.className = "search-match-content"; contentSpan.textContent = lineContent; - highlightRangesWithStyleClass(contentSpan, matchRanges, "highlighted-match"); + WebInspector.highlightRangesWithStyleClass(contentSpan, matchRanges, "highlighted-match"); return contentSpan; } } @@ -701,4 +701,4 @@ WebInspector.FileBasedSearchResultsPane.SearchResult = function(file, searchMatc /** * @type {WebInspector.AdvancedSearchController} */ -WebInspector.advancedSearchController = null; \ No newline at end of file +WebInspector.advancedSearchController = null; diff --git a/Source/WebCore/inspector/front-end/BinarySearch.js b/Source/WebCore/inspector/front-end/BinarySearch.js deleted file mode 100644 index 8d03ca4..0000000 --- a/Source/WebCore/inspector/front-end/BinarySearch.js +++ /dev/null @@ -1,86 +0,0 @@ -/* - * Copyright (C) 2011 Google Inc. All rights reserved. - * Copyright (C) 2007 Apple Inc. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Google Inc. nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -/** - * @param {*} object - * @param {Array.<*>} array - * @param {function(*, *)} comparator - */ -function binarySearch(object, array, comparator) -{ - var first = 0; - var last = array.length - 1; - - while (first <= last) { - var mid = (first + last) >> 1; - var c = comparator(object, array[mid]); - if (c > 0) - first = mid + 1; - else if (c < 0) - last = mid - 1; - else - return mid; - } - - // Return the nearest lesser index, "-1" means "0, "-2" means "1", etc. - return -(first + 1); -} - -Object.defineProperty(Array.prototype, "binaryIndexOf", -{ - /** - * @this {Array.<*>} - */ - value: function(value, comparator) - { - var result = binarySearch(value, this, comparator); - return result >= 0 ? result : -1; - } -}); - -/** - * @param {*} anObject - * @param {Array.<*>} aList - * @param {function(*, *)} aFunction - */ -function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction) -{ - var index = binarySearch(anObject, aList, aFunction); - if (index < 0) - // See binarySearch implementation. - return -index - 1; - else { - // Return the first occurance of an item in the list. - while (index > 0 && aFunction(anObject, aList[index - 1]) === 0) - index--; - return index; - } -} diff --git a/Source/WebCore/inspector/front-end/ConsoleMessage.js b/Source/WebCore/inspector/front-end/ConsoleMessage.js index dbbe406..c15ec12 100644 --- a/Source/WebCore/inspector/front-end/ConsoleMessage.js +++ b/Source/WebCore/inspector/front-end/ConsoleMessage.js @@ -436,7 +436,7 @@ WebInspector.ConsoleMessageImpl.prototype = { matchRanges.push({ offset: match.index, length: match[0].length }); match = regexObject.exec(text); } - highlightSearchResults(element, matchRanges); + WebInspector.highlightSearchResults(element, matchRanges); }, matchesRegex: function(regexObject) diff --git a/Source/WebCore/inspector/front-end/ConsoleView.js b/Source/WebCore/inspector/front-end/ConsoleView.js index c4c6fc0..7626c3e 100644 --- a/Source/WebCore/inspector/front-end/ConsoleView.js +++ b/Source/WebCore/inspector/front-end/ConsoleView.js @@ -743,7 +743,7 @@ WebInspector.ConsoleCommand.prototype = { matchRanges.push({ offset: match.index, length: match[0].length }); match = regexObject.exec(text); } - highlightSearchResults(this._formattedCommand, matchRanges); + WebInspector.highlightSearchResults(this._formattedCommand, matchRanges); this._element.scrollIntoViewIfNeeded(); }, diff --git a/Source/WebCore/inspector/front-end/DOMExtension.js b/Source/WebCore/inspector/front-end/DOMExtension.js new file mode 100644 index 0000000..bec1470 --- /dev/null +++ b/Source/WebCore/inspector/front-end/DOMExtension.js @@ -0,0 +1,507 @@ +/* + * Copyright (C) 2007 Apple Inc. All rights reserved. + * Copyright (C) 2012 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of + * its contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Contains diff method based on Javascript Diff Algorithm By John Resig + * http://ejohn.org/files/jsdiff.js (released under the MIT license). + */ + +/** + * @param {string=} direction + */ +Node.prototype.rangeOfWord = function(offset, stopCharacters, stayWithinNode, direction) +{ + var startNode; + var startOffset = 0; + var endNode; + var endOffset = 0; + + if (!stayWithinNode) + stayWithinNode = this; + + if (!direction || direction === "backward" || direction === "both") { + var node = this; + while (node) { + if (node === stayWithinNode) { + if (!startNode) + startNode = stayWithinNode; + break; + } + + if (node.nodeType === Node.TEXT_NODE) { + var start = (node === this ? (offset - 1) : (node.nodeValue.length - 1)); + for (var i = start; i >= 0; --i) { + if (stopCharacters.indexOf(node.nodeValue[i]) !== -1) { + startNode = node; + startOffset = i + 1; + break; + } + } + } + + if (startNode) + break; + + node = node.traversePreviousNode(stayWithinNode); + } + + if (!startNode) { + startNode = stayWithinNode; + startOffset = 0; + } + } else { + startNode = this; + startOffset = offset; + } + + if (!direction || direction === "forward" || direction === "both") { + node = this; + while (node) { + if (node === stayWithinNode) { + if (!endNode) + endNode = stayWithinNode; + break; + } + + if (node.nodeType === Node.TEXT_NODE) { + var start = (node === this ? offset : 0); + for (var i = start; i < node.nodeValue.length; ++i) { + if (stopCharacters.indexOf(node.nodeValue[i]) !== -1) { + endNode = node; + endOffset = i; + break; + } + } + } + + if (endNode) + break; + + node = node.traverseNextNode(stayWithinNode); + } + + if (!endNode) { + endNode = stayWithinNode; + endOffset = stayWithinNode.nodeType === Node.TEXT_NODE ? stayWithinNode.nodeValue.length : stayWithinNode.childNodes.length; + } + } else { + endNode = this; + endOffset = offset; + } + + var result = this.ownerDocument.createRange(); + result.setStart(startNode, startOffset); + result.setEnd(endNode, endOffset); + + return result; +} + +Node.prototype.traverseNextTextNode = function(stayWithin) +{ + var node = this.traverseNextNode(stayWithin); + if (!node) + return; + + while (node && node.nodeType !== Node.TEXT_NODE) + node = node.traverseNextNode(stayWithin); + + return node; +} + +Node.prototype.rangeBoundaryForOffset = function(offset) +{ + var node = this.traverseNextTextNode(this); + while (node && offset > node.nodeValue.length) { + offset -= node.nodeValue.length; + node = node.traverseNextTextNode(this); + } + if (!node) + return { container: this, offset: 0 }; + return { container: node, offset: offset }; +} + +Element.prototype.removeStyleClass = function(className) +{ + this.classList.remove(className); +} + +Element.prototype.removeMatchingStyleClasses = function(classNameRegex) +{ + var regex = new RegExp("(^|\\s+)" + classNameRegex + "($|\\s+)"); + if (regex.test(this.className)) + this.className = this.className.replace(regex, " "); +} + +Element.prototype.addStyleClass = function(className) +{ + this.classList.add(className); +} + +Element.prototype.hasStyleClass = function(className) +{ + return this.classList.contains(className); +} + +Element.prototype.positionAt = function(x, y) +{ + this.style.left = x + "px"; + this.style.top = y + "px"; +} + +Element.prototype.pruneEmptyTextNodes = function() +{ + var sibling = this.firstChild; + while (sibling) { + var nextSibling = sibling.nextSibling; + if (sibling.nodeType === this.TEXT_NODE && sibling.nodeValue === "") + this.removeChild(sibling); + sibling = nextSibling; + } +} + +Element.prototype.isScrolledToBottom = function() +{ + // This code works only for 0-width border + return this.scrollTop + this.clientHeight === this.scrollHeight; +} + +Node.prototype.enclosingNodeOrSelfWithNodeNameInArray = function(nameArray) +{ + for (var node = this; node && node !== this.ownerDocument; node = node.parentNode) + for (var i = 0; i < nameArray.length; ++i) + if (node.nodeName.toLowerCase() === nameArray[i].toLowerCase()) + return node; + return null; +} + +Node.prototype.enclosingNodeOrSelfWithNodeName = function(nodeName) +{ + return this.enclosingNodeOrSelfWithNodeNameInArray([nodeName]); +} + +Node.prototype.enclosingNodeOrSelfWithClass = function(className) +{ + for (var node = this; node && node !== this.ownerDocument; node = node.parentNode) + if (node.nodeType === Node.ELEMENT_NODE && node.hasStyleClass(className)) + return node; + return null; +} + +Node.prototype.enclosingNodeWithClass = function(className) +{ + if (!this.parentNode) + return null; + return this.parentNode.enclosingNodeOrSelfWithClass(className); +} + +Element.prototype.query = function(query) +{ + return this.ownerDocument.evaluate(query, this, null, XPathResult.FIRST_ORDERED_NODE_TYPE, null).singleNodeValue; +} + +Element.prototype.removeChildren = function() +{ + if (this.firstChild) + this.textContent = ""; +} + +Element.prototype.isInsertionCaretInside = function() +{ + var selection = window.getSelection(); + if (!selection.rangeCount || !selection.isCollapsed) + return false; + var selectionRange = selection.getRangeAt(0); + return selectionRange.startContainer.isSelfOrDescendant(this); +} + +/** + * @param {string=} className + */ +Element.prototype.createChild = function(elementName, className) +{ + var element = this.ownerDocument.createElement(elementName); + if (className) + element.className = className; + this.appendChild(element); + return element; +} + +DocumentFragment.prototype.createChild = Element.prototype.createChild; + +/** + * @return {number} + */ +Element.prototype.totalOffsetLeft = function() +{ + return this.totalOffset().left; +} + +/** + * @return {number} + */ +Element.prototype.totalOffsetTop = function() +{ + return this.totalOffset().top; + +} + +Element.prototype.totalOffset = function() +{ + var totalLeft = 0; + var totalTop = 0; + + for (var element = this; element; element = element.offsetParent) { + totalLeft += element.offsetLeft; + totalTop += element.offsetTop; + if (this !== element) { + totalLeft += element.clientLeft - element.scrollLeft; + totalTop += element.clientTop - element.scrollTop; + } + } + + return { left: totalLeft, top: totalTop }; +} + +Element.prototype.scrollOffset = function() +{ + var curLeft = 0; + var curTop = 0; + for (var element = this; element; element = element.scrollParent) { + curLeft += element.scrollLeft; + curTop += element.scrollTop; + } + return { left: curLeft, top: curTop }; +} + +/** + * @constructor + * @param {number=} x + * @param {number=} y + * @param {number=} width + * @param {number=} height + */ +function AnchorBox(x, y, width, height) +{ + this.x = x || 0; + this.y = y || 0; + this.width = width || 0; + this.height = height || 0; +} + +/** + * @param {Window} targetWindow + * @return {AnchorBox} + */ +Element.prototype.offsetRelativeToWindow = function(targetWindow) +{ + var elementOffset = new AnchorBox(); + var curElement = this; + var curWindow = this.ownerDocument.defaultView; + while (curWindow && curElement) { + elementOffset.x += curElement.totalOffsetLeft(); + elementOffset.y += curElement.totalOffsetTop(); + if (curWindow === targetWindow) + break; + + curElement = curWindow.frameElement; + curWindow = curWindow.parent; + } + + return elementOffset; +} + +/** + * @param {Window} targetWindow + * @return {AnchorBox} + */ +Element.prototype.boxInWindow = function(targetWindow) +{ + targetWindow = targetWindow || this.ownerDocument.defaultView; + + var anchorBox = this.offsetRelativeToWindow(window); + anchorBox.width = Math.min(this.offsetWidth, window.innerWidth - anchorBox.x); + anchorBox.height = Math.min(this.offsetHeight, window.innerHeight - anchorBox.y); + + return anchorBox; +} + +/** + * @param {string} text + */ +Element.prototype.setTextAndTitle = function(text) +{ + this.textContent = text; + this.title = text; +} + +KeyboardEvent.prototype.__defineGetter__("data", function() +{ + // Emulate "data" attribute from DOM 3 TextInput event. + // See http://www.w3.org/TR/DOM-Level-3-Events/#events-Events-TextEvent-data + switch (this.type) { + case "keypress": + if (!this.ctrlKey && !this.metaKey) + return String.fromCharCode(this.charCode); + else + return ""; + case "keydown": + case "keyup": + if (!this.ctrlKey && !this.metaKey && !this.altKey) + return String.fromCharCode(this.which); + else + return ""; + } +}); + +/** + * @param {boolean=} preventDefault + */ +Event.prototype.consume = function(preventDefault) +{ + this.stopImmediatePropagation(); + if (preventDefault) + this.preventDefault(); + this.handled = true; +} + +Text.prototype.select = function(start, end) +{ + start = start || 0; + end = end || this.textContent.length; + + if (start < 0) + start = end + start; + + var selection = this.ownerDocument.defaultView.getSelection(); + selection.removeAllRanges(); + var range = this.ownerDocument.createRange(); + range.setStart(this, start); + range.setEnd(this, end); + selection.addRange(range); + return this; +} + +Element.prototype.selectionLeftOffset = function() +{ + // Calculate selection offset relative to the current element. + + var selection = window.getSelection(); + if (!selection.containsNode(this, true)) + return null; + + var leftOffset = selection.anchorOffset; + var node = selection.anchorNode; + + while (node !== this) { + while (node.previousSibling) { + node = node.previousSibling; + leftOffset += node.textContent.length; + } + node = node.parentNode; + } + + return leftOffset; +} + +Node.prototype.isAncestor = function(node) +{ + if (!node) + return false; + + var currentNode = node.parentNode; + while (currentNode) { + if (this === currentNode) + return true; + currentNode = currentNode.parentNode; + } + return false; +} + +Node.prototype.isDescendant = function(descendant) +{ + return !!descendant && descendant.isAncestor(this); +} + +Node.prototype.isSelfOrAncestor = function(node) +{ + return !!node && (node === this || this.isAncestor(node)); +} + +Node.prototype.isSelfOrDescendant = function(node) +{ + return !!node && (node === this || this.isDescendant(node)); +} + +Node.prototype.traverseNextNode = function(stayWithin) +{ + var node = this.firstChild; + if (node) + return node; + + if (stayWithin && this === stayWithin) + return null; + + node = this.nextSibling; + if (node) + return node; + + node = this; + while (node && !node.nextSibling && (!stayWithin || !node.parentNode || node.parentNode !== stayWithin)) + node = node.parentNode; + if (!node) + return null; + + return node.nextSibling; +} + +Node.prototype.traversePreviousNode = function(stayWithin) +{ + if (stayWithin && this === stayWithin) + return null; + var node = this.previousSibling; + while (node && node.lastChild) + node = node.lastChild; + if (node) + return node; + return this.parentNode; +} + +HTMLTextAreaElement.prototype.moveCursorToEnd = function() +{ + var length = this.value.length; + this.setSelectionRange(length, length); +} + +function isEnterKey(event) { + // Check if in IME. + return event.keyCode !== 229 && event.keyIdentifier === "Enter"; +} + +function consumeEvent(e) +{ + e.consume(); +} diff --git a/Source/WebCore/inspector/front-end/ElementsTreeOutline.js b/Source/WebCore/inspector/front-end/ElementsTreeOutline.js index c661269..20d978b 100644 --- a/Source/WebCore/inspector/front-end/ElementsTreeOutline.js +++ b/Source/WebCore/inspector/front-end/ElementsTreeOutline.js @@ -1757,7 +1757,7 @@ WebInspector.ElementsTreeElement.prototype = { matchRanges.push({ offset: 0, length: text.length }); this._highlightResult = []; - highlightSearchResults(this.listItemElement, matchRanges, this._highlightResult); + WebInspector.highlightSearchResults(this.listItemElement, matchRanges, this._highlightResult); } } diff --git a/Source/WebCore/inspector/front-end/FilteredItemSelectionDialog.js b/Source/WebCore/inspector/front-end/FilteredItemSelectionDialog.js index 0006c46..1b41468 100644 --- a/Source/WebCore/inspector/front-end/FilteredItemSelectionDialog.js +++ b/Source/WebCore/inspector/front-end/FilteredItemSelectionDialog.js @@ -379,7 +379,7 @@ WebInspector.FilteredItemSelectionDialog.prototype = { { var changes = this._elementHighlightChanges.get(itemElement) if (changes) { - revertDomChanges(changes); + WebInspector.revertDomChanges(changes); this._elementHighlightChanges.remove(itemElement); } }, @@ -401,7 +401,7 @@ WebInspector.FilteredItemSelectionDialog.prototype = { } var changes = []; - highlightRangesWithStyleClass(itemElement, ranges, "highlight", changes); + WebInspector.highlightRangesWithStyleClass(itemElement, ranges, "highlight", changes); if (changes.length) this._elementHighlightChanges.put(itemElement, changes); diff --git a/Source/WebCore/inspector/front-end/HeapSnapshot.js b/Source/WebCore/inspector/front-end/HeapSnapshot.js index 94d8bf5..7dd11ea 100644 --- a/Source/WebCore/inspector/front-end/HeapSnapshot.js +++ b/Source/WebCore/inspector/front-end/HeapSnapshot.js @@ -161,7 +161,7 @@ WebInspector.HeapSnapshotLoader.prototype = { var closingBracketIndex = this._findBalancedCurlyBrackets(); if (closingBracketIndex === -1) return; - this._snapshot.snapshot = JSON.parse(this._json.slice(0, closingBracketIndex)); + this._snapshot.snapshot = /** @type {HeapSnapshotHeader} */JSON.parse(this._json.slice(0, closingBracketIndex)); this._json = this._json.slice(closingBracketIndex); this._state = "find-nodes"; this.pushJSONChunk(""); @@ -854,6 +854,19 @@ function HeapSnapshotMetainfo() this.types = []; } +/** + * @constructor + */ +function HeapSnapshotHeader() +{ + // New format. + this.title = ""; + this.uid = 0; + this.meta = new HeapSnapshotMetainfo(); + this.node_count = 0; + this.edge_count = 0; +} + WebInspector.HeapSnapshot.prototype = { _init: function() { diff --git a/Source/WebCore/inspector/front-end/HeapSnapshotWorker.js b/Source/WebCore/inspector/front-end/HeapSnapshotWorker.js index 3a9a2ca..7c05cbd 100644 --- a/Source/WebCore/inspector/front-end/HeapSnapshotWorker.js +++ b/Source/WebCore/inspector/front-end/HeapSnapshotWorker.js @@ -31,10 +31,9 @@ WebInspector = {}; WebInspector.UIString = function(s) { return s; }; -importScripts("BinarySearch.js"); importScripts("HeapSnapshot.js"); importScripts("HeapSnapshotWorkerDispatcher.js"); -importScripts("PartialQuickSort.js"); +importScripts("utilities.js"); function postMessageWrapper(message) { diff --git a/Source/WebCore/inspector/front-end/JavaScriptSourceFrame.js b/Source/WebCore/inspector/front-end/JavaScriptSourceFrame.js index bd6f767..b75b75c 100644 --- a/Source/WebCore/inspector/front-end/JavaScriptSourceFrame.js +++ b/Source/WebCore/inspector/front-end/JavaScriptSourceFrame.js @@ -239,7 +239,7 @@ WebInspector.JavaScriptSourceFrame.prototype = { // 2. 'highlight' them with artificial style to detect word boundaries var changes = []; - highlightRangesWithStyleClass(lineElement, ranges, "source-frame-token", changes); + WebInspector.highlightRangesWithStyleClass(lineElement, ranges, "source-frame-token", changes); var lineOffsetLeft = lineElement.totalOffsetLeft(); for (var child = lineElement.firstChild; child; child = child.nextSibling) { if (child.nodeType !== Node.ELEMENT_NODE || !child.hasStyleClass("source-frame-token")) diff --git a/Source/WebCore/inspector/front-end/NetworkPanel.js b/Source/WebCore/inspector/front-end/NetworkPanel.js index 9fb2c32..e2a8c7c 100644 --- a/Source/WebCore/inspector/front-end/NetworkPanel.js +++ b/Source/WebCore/inspector/front-end/NetworkPanel.js @@ -1112,7 +1112,7 @@ WebInspector.NetworkLogView.prototype = { _highlightNthMatchedRequest: function(matchedRequestIndex, reveal) { if (this._highlightedSubstringChanges) { - revertDomChanges(this._highlightedSubstringChanges); + WebInspector.revertDomChanges(this._highlightedSubstringChanges); this._highlightedSubstringChanges = null; } @@ -1733,7 +1733,7 @@ WebInspector.NetworkDataGridNode.prototype = { { var domChanges = []; var matchInfo = this._nameCell.textContent.match(regexp); - highlightSearchResult(this._nameCell, matchInfo.index, matchInfo[0].length, domChanges); + WebInspector.highlightSearchResult(this._nameCell, matchInfo.index, matchInfo[0].length, domChanges); return domChanges; }, diff --git a/Source/WebCore/inspector/front-end/PartialQuickSort.js b/Source/WebCore/inspector/front-end/PartialQuickSort.js deleted file mode 100644 index f71a721..0000000 --- a/Source/WebCore/inspector/front-end/PartialQuickSort.js +++ /dev/null @@ -1,51 +0,0 @@ -/* - * Copyright (C) 2011 Google Inc. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Google Inc. nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -Object.defineProperty(Array.prototype, "sortRange", { value: -/** @this {Array} */ -function(comparator, leftBound, rightBound, k) -{ - function quickSortFirstK(array, comparator, left, right, k) - { - if (right <= left) - return; - var pivotIndex = Math.floor(Math.random() * (right - left)) + left; - var pivotNewIndex = array.partition(comparator, left, right, pivotIndex); - quickSortFirstK(array, comparator, left, pivotNewIndex - 1, k); - if (pivotNewIndex < left + k - 1) - quickSortFirstK(array, comparator, pivotNewIndex + 1, right, k); - } - - if (leftBound === 0 && rightBound === (this.length - 1) && k === this.length) - this.sort(comparator); - else - quickSortFirstK(this, comparator, leftBound, rightBound, k); - return this; -}}); diff --git a/Source/WebCore/inspector/front-end/TextViewer.js b/Source/WebCore/inspector/front-end/TextViewer.js index 0f404e1..0e6c504 100644 --- a/Source/WebCore/inspector/front-end/TextViewer.js +++ b/Source/WebCore/inspector/front-end/TextViewer.js @@ -1512,7 +1512,7 @@ WebInspector.TextEditorMainPanel.prototype = { lineRow.appendChild(lineRow.decorationsElement); } finally { if (this._rangeToMark && this._rangeToMark.startLine === lineNumber) - this._markedRangeElement = highlightSearchResult(lineRow, this._rangeToMark.startColumn, this._rangeToMark.endColumn - this._rangeToMark.startColumn); + this._markedRangeElement = WebInspector.highlightSearchResult(lineRow, this._rangeToMark.startColumn, this._rangeToMark.endColumn - this._rangeToMark.startColumn); this.endDomUpdates(); } }, diff --git a/Source/WebCore/inspector/front-end/UIUtils.js b/Source/WebCore/inspector/front-end/UIUtils.js index 49d5767..3b9221f 100644 --- a/Source/WebCore/inspector/front-end/UIUtils.js +++ b/Source/WebCore/inspector/front-end/UIUtils.js @@ -671,6 +671,144 @@ WebInspector.resetToolbarColors = function() } /** + * @param {Element} element + * @param {number} offset + * @param {number} length + * @param {Array.=} domChanges + */ +WebInspector.highlightSearchResult = function(element, offset, length, domChanges) +{ + var result = WebInspector.highlightSearchResults(element, [{offset: offset, length: length }], domChanges); + return result.length ? result[0] : null; +} + +/** + * @param {Element} element + * @param {Array.} resultRanges + * @param {Array.=} changes + */ +WebInspector.highlightSearchResults = function(element, resultRanges, changes) +{ + return WebInspector.highlightRangesWithStyleClass(element, resultRanges, "webkit-search-result", changes); +} + +/** + * @param {Element} element + * @param {Array.} resultRanges + * @param {string} styleClass + * @param {Array.=} changes + */ +WebInspector.highlightRangesWithStyleClass = function(element, resultRanges, styleClass, changes) +{ + changes = changes || []; + var highlightNodes = []; + var lineText = element.textContent; + var ownerDocument = element.ownerDocument; + var textNodeSnapshot = ownerDocument.evaluate(".//text()", element, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null); + + var snapshotLength = textNodeSnapshot.snapshotLength; + if (snapshotLength === 0) + return highlightNodes; + + var nodeRanges = []; + var rangeEndOffset = 0; + for (var i = 0; i < snapshotLength; ++i) { + var range = {}; + range.offset = rangeEndOffset; + range.length = textNodeSnapshot.snapshotItem(i).textContent.length; + rangeEndOffset = range.offset + range.length; + nodeRanges.push(range); + } + + var startIndex = 0; + for (var i = 0; i < resultRanges.length; ++i) { + var startOffset = resultRanges[i].offset; + var endOffset = startOffset + resultRanges[i].length; + + while (startIndex < snapshotLength && nodeRanges[startIndex].offset + nodeRanges[startIndex].length <= startOffset) + startIndex++; + var endIndex = startIndex; + while (endIndex < snapshotLength && nodeRanges[endIndex].offset + nodeRanges[endIndex].length < endOffset) + endIndex++; + if (endIndex === snapshotLength) + break; + + var highlightNode = ownerDocument.createElement("span"); + highlightNode.className = styleClass; + highlightNode.textContent = lineText.substring(startOffset, endOffset); + + var lastTextNode = textNodeSnapshot.snapshotItem(endIndex); + var lastText = lastTextNode.textContent; + lastTextNode.textContent = lastText.substring(endOffset - nodeRanges[endIndex].offset); + changes.push({ node: lastTextNode, type: "changed", oldText: lastText, newText: lastTextNode.textContent }); + + if (startIndex === endIndex) { + lastTextNode.parentElement.insertBefore(highlightNode, lastTextNode); + changes.push({ node: highlightNode, type: "added", nextSibling: lastTextNode, parent: lastTextNode.parentElement }); + highlightNodes.push(highlightNode); + + var prefixNode = ownerDocument.createTextNode(lastText.substring(0, startOffset - nodeRanges[startIndex].offset)); + lastTextNode.parentElement.insertBefore(prefixNode, highlightNode); + changes.push({ node: prefixNode, type: "added", nextSibling: highlightNode, parent: lastTextNode.parentElement }); + } else { + var firstTextNode = textNodeSnapshot.snapshotItem(startIndex); + var firstText = firstTextNode.textContent; + var anchorElement = firstTextNode.nextSibling; + + firstTextNode.parentElement.insertBefore(highlightNode, anchorElement); + changes.push({ node: highlightNode, type: "added", nextSibling: anchorElement, parent: firstTextNode.parentElement }); + highlightNodes.push(highlightNode); + + firstTextNode.textContent = firstText.substring(0, startOffset - nodeRanges[startIndex].offset); + changes.push({ node: firstTextNode, type: "changed", oldText: firstText, newText: firstTextNode.textContent }); + + for (var j = startIndex + 1; j < endIndex; j++) { + var textNode = textNodeSnapshot.snapshotItem(j); + var text = textNode.textContent; + textNode.textContent = ""; + changes.push({ node: textNode, type: "changed", oldText: text, newText: textNode.textContent }); + } + } + startIndex = endIndex; + nodeRanges[startIndex].offset = endOffset; + nodeRanges[startIndex].length = lastTextNode.textContent.length; + + } + return highlightNodes; +} + +WebInspector.applyDomChanges = function(domChanges) +{ + for (var i = 0, size = domChanges.length; i < size; ++i) { + var entry = domChanges[i]; + switch (entry.type) { + case "added": + entry.parent.insertBefore(entry.node, entry.nextSibling); + break; + case "changed": + entry.node.textContent = entry.newText; + break; + } + } +} + +WebInspector.revertDomChanges = function(domChanges) +{ + for (var i = domChanges.length - 1; i >= 0; --i) { + var entry = domChanges[i]; + switch (entry.type) { + case "added": + if (entry.node.parentElement) + entry.node.parentElement.removeChild(entry.node); + break; + case "changed": + entry.node.textContent = entry.oldText; + break; + } + } +} + +/** * @param {WebInspector.ContextMenu} contextMenu * @param {Node} contextNode * @param {Event} event diff --git a/Source/WebCore/inspector/front-end/WebKit.qrc b/Source/WebCore/inspector/front-end/WebKit.qrc index e4b50ed..a61ecb8 100644 --- a/Source/WebCore/inspector/front-end/WebKit.qrc +++ b/Source/WebCore/inspector/front-end/WebKit.qrc @@ -10,7 +10,6 @@ AuditResultView.js AuditRules.js AuditsPanel.js - BinarySearch.js BottomUpProfileDataGridTree.js BreakpointManager.js BreakpointsSidebarPane.js @@ -42,6 +41,7 @@ Dialog.js DOMAgent.js DOMBreakpointsSidebarPane.js + DOMExtension.js DOMPresentationUtils.js DOMStorage.js DOMStorageItemsView.js @@ -91,7 +91,6 @@ ObjectPropertiesSection.js Panel.js PanelEnablerView.js - PartialQuickSort.js Placard.js Popover.js ProfileDataGridTree.js diff --git a/Source/WebCore/inspector/front-end/inspector.html b/Source/WebCore/inspector/front-end/inspector.html index 04c6405..32e2856 100644 --- a/Source/WebCore/inspector/front-end/inspector.html +++ b/Source/WebCore/inspector/front-end/inspector.html @@ -36,7 +36,7 @@ THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + @@ -164,7 +164,6 @@ THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - diff --git a/Source/WebCore/inspector/front-end/utilities.js b/Source/WebCore/inspector/front-end/utilities.js index 6541e74..741d439 100644 --- a/Source/WebCore/inspector/front-end/utilities.js +++ b/Source/WebCore/inspector/front-end/utilities.js @@ -1,5 +1,6 @@ /* * Copyright (C) 2007 Apple Inc. All rights reserved. + * Copyright (C) 2012 Google Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -29,403 +30,6 @@ * http://ejohn.org/files/jsdiff.js (released under the MIT license). */ -/** - * @param {string=} direction - */ -Node.prototype.rangeOfWord = function(offset, stopCharacters, stayWithinNode, direction) -{ - var startNode; - var startOffset = 0; - var endNode; - var endOffset = 0; - - if (!stayWithinNode) - stayWithinNode = this; - - if (!direction || direction === "backward" || direction === "both") { - var node = this; - while (node) { - if (node === stayWithinNode) { - if (!startNode) - startNode = stayWithinNode; - break; - } - - if (node.nodeType === Node.TEXT_NODE) { - var start = (node === this ? (offset - 1) : (node.nodeValue.length - 1)); - for (var i = start; i >= 0; --i) { - if (stopCharacters.indexOf(node.nodeValue[i]) !== -1) { - startNode = node; - startOffset = i + 1; - break; - } - } - } - - if (startNode) - break; - - node = node.traversePreviousNode(stayWithinNode); - } - - if (!startNode) { - startNode = stayWithinNode; - startOffset = 0; - } - } else { - startNode = this; - startOffset = offset; - } - - if (!direction || direction === "forward" || direction === "both") { - node = this; - while (node) { - if (node === stayWithinNode) { - if (!endNode) - endNode = stayWithinNode; - break; - } - - if (node.nodeType === Node.TEXT_NODE) { - var start = (node === this ? offset : 0); - for (var i = start; i < node.nodeValue.length; ++i) { - if (stopCharacters.indexOf(node.nodeValue[i]) !== -1) { - endNode = node; - endOffset = i; - break; - } - } - } - - if (endNode) - break; - - node = node.traverseNextNode(stayWithinNode); - } - - if (!endNode) { - endNode = stayWithinNode; - endOffset = stayWithinNode.nodeType === Node.TEXT_NODE ? stayWithinNode.nodeValue.length : stayWithinNode.childNodes.length; - } - } else { - endNode = this; - endOffset = offset; - } - - var result = this.ownerDocument.createRange(); - result.setStart(startNode, startOffset); - result.setEnd(endNode, endOffset); - - return result; -} - -Node.prototype.traverseNextTextNode = function(stayWithin) -{ - var node = this.traverseNextNode(stayWithin); - if (!node) - return; - - while (node && node.nodeType !== Node.TEXT_NODE) - node = node.traverseNextNode(stayWithin); - - return node; -} - -Node.prototype.rangeBoundaryForOffset = function(offset) -{ - var node = this.traverseNextTextNode(this); - while (node && offset > node.nodeValue.length) { - offset -= node.nodeValue.length; - node = node.traverseNextTextNode(this); - } - if (!node) - return { container: this, offset: 0 }; - return { container: node, offset: offset }; -} - -Element.prototype.removeStyleClass = function(className) -{ - this.classList.remove(className); -} - -Element.prototype.removeMatchingStyleClasses = function(classNameRegex) -{ - var regex = new RegExp("(^|\\s+)" + classNameRegex + "($|\\s+)"); - if (regex.test(this.className)) - this.className = this.className.replace(regex, " "); -} - -Element.prototype.addStyleClass = function(className) -{ - this.classList.add(className); -} - -Element.prototype.hasStyleClass = function(className) -{ - return this.classList.contains(className); -} - -Element.prototype.positionAt = function(x, y) -{ - this.style.left = x + "px"; - this.style.top = y + "px"; -} - -Element.prototype.pruneEmptyTextNodes = function() -{ - var sibling = this.firstChild; - while (sibling) { - var nextSibling = sibling.nextSibling; - if (sibling.nodeType === this.TEXT_NODE && sibling.nodeValue === "") - this.removeChild(sibling); - sibling = nextSibling; - } -} - -Element.prototype.isScrolledToBottom = function() -{ - // This code works only for 0-width border - return this.scrollTop + this.clientHeight === this.scrollHeight; -} - -Node.prototype.enclosingNodeOrSelfWithNodeNameInArray = function(nameArray) -{ - for (var node = this; node && node !== this.ownerDocument; node = node.parentNode) - for (var i = 0; i < nameArray.length; ++i) - if (node.nodeName.toLowerCase() === nameArray[i].toLowerCase()) - return node; - return null; -} - -Node.prototype.enclosingNodeOrSelfWithNodeName = function(nodeName) -{ - return this.enclosingNodeOrSelfWithNodeNameInArray([nodeName]); -} - -Node.prototype.enclosingNodeOrSelfWithClass = function(className) -{ - for (var node = this; node && node !== this.ownerDocument; node = node.parentNode) - if (node.nodeType === Node.ELEMENT_NODE && node.hasStyleClass(className)) - return node; - return null; -} - -Node.prototype.enclosingNodeWithClass = function(className) -{ - if (!this.parentNode) - return null; - return this.parentNode.enclosingNodeOrSelfWithClass(className); -} - -Element.prototype.query = function(query) -{ - return this.ownerDocument.evaluate(query, this, null, XPathResult.FIRST_ORDERED_NODE_TYPE, null).singleNodeValue; -} - -Element.prototype.removeChildren = function() -{ - if (this.firstChild) - this.textContent = ""; -} - -Element.prototype.isInsertionCaretInside = function() -{ - var selection = window.getSelection(); - if (!selection.rangeCount || !selection.isCollapsed) - return false; - var selectionRange = selection.getRangeAt(0); - return selectionRange.startContainer.isSelfOrDescendant(this); -} - -/** - * @param {string=} className - */ -Element.prototype.createChild = function(elementName, className) -{ - var element = this.ownerDocument.createElement(elementName); - if (className) - element.className = className; - this.appendChild(element); - return element; -} - -DocumentFragment.prototype.createChild = Element.prototype.createChild; - -/** - * @return {number} - */ -Element.prototype.totalOffsetLeft = function() -{ - return this.totalOffset().left; -} - -/** - * @return {number} - */ -Element.prototype.totalOffsetTop = function() -{ - return this.totalOffset().top; - -} - -Element.prototype.totalOffset = function() -{ - var totalLeft = 0; - var totalTop = 0; - - for (var element = this; element; element = element.offsetParent) { - totalLeft += element.offsetLeft; - totalTop += element.offsetTop; - if (this !== element) { - totalLeft += element.clientLeft - element.scrollLeft; - totalTop += element.clientTop - element.scrollTop; - } - } - - return { left: totalLeft, top: totalTop }; -} - -Element.prototype.scrollOffset = function() -{ - var curLeft = 0; - var curTop = 0; - for (var element = this; element; element = element.scrollParent) { - curLeft += element.scrollLeft; - curTop += element.scrollTop; - } - return { left: curLeft, top: curTop }; -} - -/** - * @constructor - * @param {number=} x - * @param {number=} y - * @param {number=} width - * @param {number=} height - */ -function AnchorBox(x, y, width, height) -{ - this.x = x || 0; - this.y = y || 0; - this.width = width || 0; - this.height = height || 0; -} - -/** - * @param {Window} targetWindow - * @return {AnchorBox} - */ -Element.prototype.offsetRelativeToWindow = function(targetWindow) -{ - var elementOffset = new AnchorBox(); - var curElement = this; - var curWindow = this.ownerDocument.defaultView; - while (curWindow && curElement) { - elementOffset.x += curElement.totalOffsetLeft(); - elementOffset.y += curElement.totalOffsetTop(); - if (curWindow === targetWindow) - break; - - curElement = curWindow.frameElement; - curWindow = curWindow.parent; - } - - return elementOffset; -} - -/** - * @param {Window} targetWindow - * @return {AnchorBox} - */ -Element.prototype.boxInWindow = function(targetWindow) -{ - targetWindow = targetWindow || this.ownerDocument.defaultView; - - var anchorBox = this.offsetRelativeToWindow(window); - anchorBox.width = Math.min(this.offsetWidth, window.innerWidth - anchorBox.x); - anchorBox.height = Math.min(this.offsetHeight, window.innerHeight - anchorBox.y); - - return anchorBox; -} - -/** - * @param {string} text - */ -Element.prototype.setTextAndTitle = function(text) -{ - this.textContent = text; - this.title = text; -} - -KeyboardEvent.prototype.__defineGetter__("data", function() -{ - // Emulate "data" attribute from DOM 3 TextInput event. - // See http://www.w3.org/TR/DOM-Level-3-Events/#events-Events-TextEvent-data - switch (this.type) { - case "keypress": - if (!this.ctrlKey && !this.metaKey) - return String.fromCharCode(this.charCode); - else - return ""; - case "keydown": - case "keyup": - if (!this.ctrlKey && !this.metaKey && !this.altKey) - return String.fromCharCode(this.which); - else - return ""; - } -}); - -/** - * @param {boolean=} preventDefault - */ -Event.prototype.consume = function(preventDefault) -{ - this.stopImmediatePropagation(); - if (preventDefault) - this.preventDefault(); - this.handled = true; -} - -Text.prototype.select = function(start, end) -{ - start = start || 0; - end = end || this.textContent.length; - - if (start < 0) - start = end + start; - - var selection = this.ownerDocument.defaultView.getSelection(); - selection.removeAllRanges(); - var range = this.ownerDocument.createRange(); - range.setStart(this, start); - range.setEnd(this, end); - selection.addRange(range); - return this; -} - -Element.prototype.selectionLeftOffset = function() -{ - // Calculate selection offset relative to the current element. - - var selection = window.getSelection(); - if (!selection.containsNode(this, true)) - return null; - - var leftOffset = selection.anchorOffset; - var node = selection.anchorNode; - - while (node !== this) { - while (node.previousSibling) { - node = node.previousSibling; - leftOffset += node.textContent.length; - } - node = node.parentNode; - } - - return leftOffset; -} - String.prototype.hasSubstring = function(string, caseInsensitive) { if (!caseInsensitive) @@ -523,69 +127,6 @@ String.prototype.removeURLFragment = function() return this.substring(0, fragmentIndex); } -Node.prototype.isAncestor = function(node) -{ - if (!node) - return false; - - var currentNode = node.parentNode; - while (currentNode) { - if (this === currentNode) - return true; - currentNode = currentNode.parentNode; - } - return false; -} - -Node.prototype.isDescendant = function(descendant) -{ - return !!descendant && descendant.isAncestor(this); -} - -Node.prototype.isSelfOrAncestor = function(node) -{ - return !!node && (node === this || this.isAncestor(node)); -} - -Node.prototype.isSelfOrDescendant = function(node) -{ - return !!node && (node === this || this.isDescendant(node)); -} - -Node.prototype.traverseNextNode = function(stayWithin) -{ - var node = this.firstChild; - if (node) - return node; - - if (stayWithin && this === stayWithin) - return null; - - node = this.nextSibling; - if (node) - return node; - - node = this; - while (node && !node.nextSibling && (!stayWithin || !node.parentNode || node.parentNode !== stayWithin)) - node = node.parentNode; - if (!node) - return null; - - return node.nextSibling; -} - -Node.prototype.traversePreviousNode = function(stayWithin) -{ - if (stayWithin && this === stayWithin) - return null; - var node = this.previousSibling; - while (node && node.lastChild) - node = node.lastChild; - if (node) - return node; - return this.parentNode; -} - Number.constrain = function(num, min, max) { if (num < min) @@ -609,12 +150,6 @@ Date.prototype.toISO8601Compact = function() leadZero(this.getSeconds()); } -HTMLTextAreaElement.prototype.moveCursorToEnd = function() -{ - var length = this.value.length; - this.setSelectionRange(length, length); -} - Object.defineProperty(Array.prototype, "remove", { /** @@ -705,6 +240,36 @@ Object.defineProperty(Array.prototype, "partition", } }); +Object.defineProperty(Array.prototype, "sortRange", +{ + /** + * @this {Array.} + * @param {function(number,number):boolean} comparator + * @param {number} leftBound + * @param {number} rightBound + * @param {number} k + */ + value: function(comparator, leftBound, rightBound, k) + { + function quickSortFirstK(array, comparator, left, right, k) + { + if (right <= left) + return; + var pivotIndex = Math.floor(Math.random() * (right - left)) + left; + var pivotNewIndex = array.partition(comparator, left, right, pivotIndex); + quickSortFirstK(array, comparator, left, pivotNewIndex - 1, k); + if (pivotNewIndex < left + k - 1) + quickSortFirstK(array, comparator, pivotNewIndex + 1, right, k); + } + + if (leftBound === 0 && rightBound === (this.length - 1) && k === this.length) + this.sort(comparator); + else + quickSortFirstK(this, comparator, leftBound, rightBound, k); + return this; + } +}); + Object.defineProperty(Array.prototype, "qselect", { /** @@ -733,6 +298,63 @@ Object.defineProperty(Array.prototype, "qselect", } }); +/** + * @param {*} object + * @param {Array.<*>} array + * @param {function(*, *):number} comparator + */ +function binarySearch(object, array, comparator) +{ + var first = 0; + var last = array.length - 1; + + while (first <= last) { + var mid = (first + last) >> 1; + var c = comparator(object, array[mid]); + if (c > 0) + first = mid + 1; + else if (c < 0) + last = mid - 1; + else + return mid; + } + + // Return the nearest lesser index, "-1" means "0, "-2" means "1", etc. + return -(first + 1); +} + +Object.defineProperty(Array.prototype, "binaryIndexOf", +{ + /** + * @this {Array.<*>} + * @param {function(*, *):number} comparator + */ + value: function(value, comparator) + { + var result = binarySearch(value, this, comparator); + return result >= 0 ? result : -1; + } +}); + +/** + * @param {*} anObject + * @param {Array.<*>} aList + * @param {function(*, *)} aFunction + */ +function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction) +{ + var index = binarySearch(anObject, aList, aFunction); + if (index < 0) + // See binarySearch implementation. + return -index - 1; + else { + // Return the first occurance of an item in the list. + while (index > 0 && aFunction(anObject, aList[index - 1]) === 0) + index--; + return index; + } +} + Array.diff = function(left, right) { var o = left; @@ -953,155 +575,6 @@ String.format = function(format, substitutions, formatters, initialValue, append return { formattedResult: result, unusedSubstitutions: unusedSubstitutions }; } -function isEnterKey(event) { - // Check if in IME. - return event.keyCode !== 229 && event.keyIdentifier === "Enter"; -} - -function consumeEvent(e) -{ - e.consume(); -} - -/** - * @param {Element} element - * @param {number} offset - * @param {number} length - * @param {Array.=} domChanges - */ -function highlightSearchResult(element, offset, length, domChanges) -{ - var result = highlightSearchResults(element, [{offset: offset, length: length }], domChanges); - return result.length ? result[0] : null; -} - -/** - * @param {Element} element - * @param {Array.} resultRanges - * @param {Array.=} changes - */ -function highlightSearchResults(element, resultRanges, changes) -{ - return highlightRangesWithStyleClass(element, resultRanges, "webkit-search-result", changes); - -} - -/** - * @param {Element} element - * @param {Array.} resultRanges - * @param {string} styleClass - * @param {Array.=} changes - */ -function highlightRangesWithStyleClass(element, resultRanges, styleClass, changes) -{ - changes = changes || []; - var highlightNodes = []; - var lineText = element.textContent; - var ownerDocument = element.ownerDocument; - var textNodeSnapshot = ownerDocument.evaluate(".//text()", element, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null); - - var snapshotLength = textNodeSnapshot.snapshotLength; - if (snapshotLength === 0) - return highlightNodes; - - var nodeRanges = []; - var rangeEndOffset = 0; - for (var i = 0; i < snapshotLength; ++i) { - var range = {}; - range.offset = rangeEndOffset; - range.length = textNodeSnapshot.snapshotItem(i).textContent.length; - rangeEndOffset = range.offset + range.length; - nodeRanges.push(range); - } - - var startIndex = 0; - for (var i = 0; i < resultRanges.length; ++i) { - var startOffset = resultRanges[i].offset; - var endOffset = startOffset + resultRanges[i].length; - - while (startIndex < snapshotLength && nodeRanges[startIndex].offset + nodeRanges[startIndex].length <= startOffset) - startIndex++; - var endIndex = startIndex; - while (endIndex < snapshotLength && nodeRanges[endIndex].offset + nodeRanges[endIndex].length < endOffset) - endIndex++; - if (endIndex === snapshotLength) - break; - - var highlightNode = ownerDocument.createElement("span"); - highlightNode.className = styleClass; - highlightNode.textContent = lineText.substring(startOffset, endOffset); - - var lastTextNode = textNodeSnapshot.snapshotItem(endIndex); - var lastText = lastTextNode.textContent; - lastTextNode.textContent = lastText.substring(endOffset - nodeRanges[endIndex].offset); - changes.push({ node: lastTextNode, type: "changed", oldText: lastText, newText: lastTextNode.textContent }); - - if (startIndex === endIndex) { - lastTextNode.parentElement.insertBefore(highlightNode, lastTextNode); - changes.push({ node: highlightNode, type: "added", nextSibling: lastTextNode, parent: lastTextNode.parentElement }); - highlightNodes.push(highlightNode); - - var prefixNode = ownerDocument.createTextNode(lastText.substring(0, startOffset - nodeRanges[startIndex].offset)); - lastTextNode.parentElement.insertBefore(prefixNode, highlightNode); - changes.push({ node: prefixNode, type: "added", nextSibling: highlightNode, parent: lastTextNode.parentElement }); - } else { - var firstTextNode = textNodeSnapshot.snapshotItem(startIndex); - var firstText = firstTextNode.textContent; - var anchorElement = firstTextNode.nextSibling; - - firstTextNode.parentElement.insertBefore(highlightNode, anchorElement); - changes.push({ node: highlightNode, type: "added", nextSibling: anchorElement, parent: firstTextNode.parentElement }); - highlightNodes.push(highlightNode); - - firstTextNode.textContent = firstText.substring(0, startOffset - nodeRanges[startIndex].offset); - changes.push({ node: firstTextNode, type: "changed", oldText: firstText, newText: firstTextNode.textContent }); - - for (var j = startIndex + 1; j < endIndex; j++) { - var textNode = textNodeSnapshot.snapshotItem(j); - var text = textNode.textContent; - textNode.textContent = ""; - changes.push({ node: textNode, type: "changed", oldText: text, newText: textNode.textContent }); - } - } - startIndex = endIndex; - nodeRanges[startIndex].offset = endOffset; - nodeRanges[startIndex].length = lastTextNode.textContent.length; - - } - return highlightNodes; -} - -function applyDomChanges(domChanges) -{ - for (var i = 0, size = domChanges.length; i < size; ++i) { - var entry = domChanges[i]; - switch (entry.type) { - case "added": - entry.parent.insertBefore(entry.node, entry.nextSibling); - break; - case "changed": - entry.node.textContent = entry.newText; - break; - } - } -} - -function revertDomChanges(domChanges) -{ - for (var i = domChanges.length - 1; i >= 0; --i) { - var entry = domChanges[i]; - switch (entry.type) { - case "added": - if (entry.node.parentElement) - entry.node.parentElement.removeChild(entry.node); - break; - case "changed": - entry.node.textContent = entry.oldText; - break; - } - } -} - /** * @param {string} query * @param {boolean} caseSensitive -- 2.7.4