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

Source/devtools/front_end/sdk/SourceMap.js

 /*
  * 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:
  *
  *     * 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
@@ skipping 58 matching lines @@
 WebInspector.SourceMap = function(sourceMappingURL, payload)
 {
     if (!WebInspector.SourceMap.prototype._base64Map) {
         const base64Digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
         WebInspector.SourceMap.prototype._base64Map = {};
         for (var i = 0; i < base64Digits.length; ++i)
             WebInspector.SourceMap.prototype._base64Map[base64Digits.charAt(i)] = i;
     }
 
     this._sourceMappingURL = sourceMappingURL;
-    this._reverseMappingsBySourceURL = {};
+    this._reverseMappingsBySourceURL = new Map();
     this._mappings = [];
     this._sources = {};
     this._sourceContentByURL = {};
     this._parseMappingPayload(payload);
 }
 
 /**
  * @param {string} sourceMapURL
  * @param {string} compiledURL
  * @param {function(?WebInspector.SourceMap)} callback
@@ skipping 94 matching lines @@
     {
         for (var i = 0; i < sections.length; ++i) {
             var section = sections[i];
             this._parseMap(section.map, section.offset.line, section.offset.column);
         }
     },
 
     /**
      * @param {number} lineNumber in compiled resource
      * @param {number} columnNumber in compiled resource
-     * @return {?Array.<number|string>}
+     * @return {?WebInspector.SourceMap.Entry}
      */
     findEntry: function(lineNumber, columnNumber)
     {
         var first = 0;
         var count = this._mappings.length;
         while (count > 1) {
           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;
               count -= step;
           }
         }
         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 null;
+        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;
+        }
+    },
+
+    /**
      * @param {!SourceMapV3} map
      * @param {number} lineNumber
      * @param {number} columnNumber
      */
     _parseMap: function(map, lineNumber, columnNumber)
     {
         var sourceIndex = 0;
         var sourceLineNumber = 0;
         var sourceColumnNumber = 0;
         var nameIndex = 0;
@@ skipping 26 matching lines @@
                     lineNumber += 1;
                     columnNumber = 0;
                     stringCharIterator.next();
                 }
                 if (!stringCharIterator.hasNext())
                     break;
             }
 
             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;
             }
 
             var sourceIndexDelta = this._decodeVLQ(stringCharIterator);
             if (sourceIndexDelta) {
                 sourceIndex += sourceIndexDelta;
                 sourceURL = sources[sourceIndex];
             }
             sourceLineNumber += this._decodeVLQ(stringCharIterator);
             sourceColumnNumber += this._decodeVLQ(stringCharIterator);
             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.

         }
     },
 
     /**
      * @param {string} char
      * @return {boolean}
      */
     _isSeparator: function(char)
     {
         return char === "," || char === ";";
@@ skipping 53 matching lines @@
     },
 
     /**
      * @return {boolean}
      */
     hasNext: function()
     {
         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;
+}