DevTools: introduce WI.SourceMap.Entry structure and cleanup WI.SourceMap API.

Source/devtools/front_end/sdk/SourceMap.js

Index: Source/devtools/front_end/sdk/SourceMap.js
diff --git a/Source/devtools/front_end/sdk/SourceMap.js b/Source/devtools/front_end/sdk/SourceMap.js
index b185b49f77fc01d75de3d9fc900b0032ab0a6151..736e0cc9e6bfe6be638e927839ef4fd58b941014 100644
--- a/Source/devtools/front_end/sdk/SourceMap.js
+++ b/Source/devtools/front_end/sdk/SourceMap.js
@@ -76,7 +76,7 @@ WebInspector.SourceMap = function(sourceMappingURL, payload)
     }
 
     this._sourceMappingURL = sourceMappingURL;
-    this._reverseMappingsBySourceURL = {};
+    this._reverseMappingsBySourceURL = new Map();
     this._mappings = [];
     this._sources = {};
     this._sourceContentByURL = {};
@@ -191,7 +191,7 @@ WebInspector.SourceMap.prototype = {
     /**
      * @param {number} lineNumber in compiled resource
      * @param {number} columnNumber in compiled resource
-     * @return {?Array.<number|string>}
+     * @return {?WebInspector.SourceMap.Entry}
      */
     findEntry: function(lineNumber, columnNumber)
     {
@@ -201,7 +201,7 @@ WebInspector.SourceMap.prototype = {
           var step = count >> 1;
           var middle = first + step;
           var mapping = this._mappings[middle];
-          if (lineNumber < mapping[0] || (lineNumber === mapping[0] && columnNumber < mapping[1]))
+          if (lineNumber < mapping.lineNumber || (lineNumber === mapping.lineNumber && columnNumber < mapping.columnNumber))
               count = step;
           else {
               first = middle;
@@ -209,29 +209,66 @@ WebInspector.SourceMap.prototype = {
           }
         }
         var entry = this._mappings[first];
-        if (!first && entry && (lineNumber < entry[0] || (lineNumber === entry[0] && columnNumber < entry[1])))
+        if (!first && entry && (lineNumber < entry.lineNumber || (lineNumber === entry.lineNumber && columnNumber < entry.columnNumber)))
             return null;
         return entry;
     },
 
     /**
-     * @param {string} sourceURL of the originating resource
-     * @param {number} lineNumber in the originating resource
-     * @param {number=} span
-     * @return {?Array.<*>}
+     * @param {string} sourceURL
+     * @param {number} lineNumber
+     * @return {?WebInspector.SourceMap.Entry}
      */
-    findEntryReversed: function(sourceURL, lineNumber, span)
+    firstSourceLineMapping: function(sourceURL, lineNumber)
     {
-        var mappings = this._reverseMappingsBySourceURL[sourceURL];
-        if (!mappings)
+        var mappings = this._reversedMappings(sourceURL);
+        var index = mappings.lowerBound(lineNumber, lineComparator);
+        if (index >= mappings.length || mappings[index].sourceLineNumber !== lineNumber)
             return null;
-        var maxLineNumber = typeof span === "number" ? Math.min(lineNumber + span + 1, mappings.length) : mappings.length;
-        for ( ; lineNumber < maxLineNumber; ++lineNumber) {
-            var mapping = mappings[lineNumber];
-            if (mapping)
-                return mapping;
+        var minColumn = mappings[index];
+        for (var i = index + 1; i < mappings.length && mappings[i].sourceLineNumber === lineNumber; ++i) {
+            if (minColumn.sourceColumnNumber > mappings[i].sourceColumnNumber)
+                minColumn = mappings[i];
+        }
+        return minColumn;
+
+        /**
+         * @param {number} lineNumber
+         * @param {!WebInspector.SourceMap.Entry} mapping
+         * @return {number}
+         */
+        function lineComparator(lineNumber, mapping)
+        {
+            return lineNumber - mapping.sourceLineNumber;
+        }
+    },
+
+    /**
+     * @param {string} sourceURL
+     * @return {!Array.<!WebInspector.SourceMap.Entry>}
+     */
+    _reversedMappings: function(sourceURL)
+    {
+        var mappings = this._reverseMappingsBySourceURL.get(sourceURL);
+        if (!mappings)
+            return [];
+        if (!mappings._sorted) {
+            mappings.sort(sourceMappingComparator);
+            mappings._sorted = true;
+        }
+        return mappings;
+
+        /**
+         * @param {!WebInspector.SourceMap.Entry} a
+         * @param {!WebInspector.SourceMap.Entry} b
+         * @return {number}
+         */
+        function sourceMappingComparator(a, b)
+        {
+            if (a.sourceLineNumber !== b.sourceLineNumber)
+                return a.sourceLineNumber - b.sourceLineNumber;
+            return a.sourceColumnNumber - b.sourceColumnNumber;
         }
-        return null;
     },
 
     /**
@@ -281,7 +318,7 @@ WebInspector.SourceMap.prototype = {
 
             columnNumber += this._decodeVLQ(stringCharIterator);
             if (!stringCharIterator.hasNext() || this._isSeparator(stringCharIterator.peek())) {
-                this._mappings.push([lineNumber, columnNumber]);
+                this._mappings.push(new WebInspector.SourceMap.Entry(lineNumber, columnNumber));
                 continue;
             }
 
@@ -295,20 +332,18 @@ WebInspector.SourceMap.prototype = {
             if (!this._isSeparator(stringCharIterator.peek()))
                 nameIndex += this._decodeVLQ(stringCharIterator);
 
-            this._mappings.push([lineNumber, columnNumber, sourceURL, sourceLineNumber, sourceColumnNumber]);
+            this._mappings.push(new WebInspector.SourceMap.Entry(lineNumber, columnNumber, sourceURL, sourceLineNumber, sourceColumnNumber));
         }
 
         for (var i = 0; i < this._mappings.length; ++i) {
             var mapping = this._mappings[i];
-            var url = mapping[2];
+            var url = mapping.sourceURL;
             if (!url)
                 continue;
-            if (!this._reverseMappingsBySourceURL[url])
-                this._reverseMappingsBySourceURL[url] = [];
-            var reverseMappings = this._reverseMappingsBySourceURL[url];
-            var sourceLine = mapping[3];
-            if (!reverseMappings[sourceLine])
-                reverseMappings[sourceLine] = [mapping[0], mapping[1]];
+            if (!this._reverseMappingsBySourceURL.has(url))
+                this._reverseMappingsBySourceURL.set(url, []);
+            var reverseMappings = this._reverseMappingsBySourceURL.get(url);
+            reverseMappings.push(mapping);

[pfeldman, 2015/09/04 01:38:36]

reverseMapping.get(mapping.lineNumber).push(mapping);

[lushnikov, 2015/09/04 17:46:45]

This will render findEntriesReversed implementation work for linear time.

         }
     },
 
@@ -382,3 +417,20 @@ WebInspector.SourceMap.StringCharIterator.prototype = {
         return this._position < this._string.length;
     }
 }
+
+/**
+ * @constructor
+ * @param {number} lineNumber
+ * @param {number} columnNumber
+ * @param {string=} sourceURL
+ * @param {number=} sourceLineNumber
+ * @param {number=} sourceColumnNumber
+ */
+WebInspector.SourceMap.Entry = function(lineNumber, columnNumber, sourceURL, sourceLineNumber, sourceColumnNumber)
+{
+    this.lineNumber = lineNumber;
+    this.columnNumber = columnNumber;
+    this.sourceURL = sourceURL;
+    this.sourceLineNumber = sourceLineNumber;
+    this.sourceColumnNumber = sourceColumnNumber;
+}