src/third_party/WebKit/Source/devtools/front_end/utilities.js

   1 /*
   2  * Copyright (C) 2007 Apple Inc.  All rights reserved.
   3  * Copyright (C) 2012 Google Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1.  Redistributions of source code must retain the above copyright
  10  *     notice, this list of conditions and the following disclaimer.
  11  * 2.  Redistributions in binary form must reproduce the above copyright
  12  *     notice, this list of conditions and the following disclaimer in the
  13  *     documentation and/or other materials provided with the distribution.
  14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  15  *     its contributors may be used to endorse or promote products derived
  16  *     from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /**
  31  * @param {!Object} obj
  32  * @return {boolean}
  33  */
  34 Object.isEmpty = function(obj)
  35 {
  36     for (var i in obj)
  37         return false;
  38     return true;
  39 }
  40
  41 /**
  42  * @param {!Object.<string,!T>} obj
  43  * @return {!Array.<!T>}
  44  * @template T
  45  */
  46 Object.values = function(obj)
  47 {
  48     var result = Object.keys(obj);
  49     var length = result.length;
  50     for (var i = 0; i < length; ++i)
  51         result[i] = obj[result[i]];
  52     return result;
  53 }
  54
  55 /**
  56  * @param {string} string
  57  * @return {!Array.<number>}
  58  */
  59 String.prototype.findAll = function(string)
  60 {
  61     var matches = [];
  62     var i = this.indexOf(string);
  63     while (i !== -1) {
  64         matches.push(i);
  65         i = this.indexOf(string, i + string.length);
  66     }
  67     return matches;
  68 }
  69
  70 /**
  71  * @return {!Array.<number>}
  72  */
  73 String.prototype.lineEndings = function()
  74 {
  75     if (!this._lineEndings) {
  76         this._lineEndings = this.findAll("\n");
  77         this._lineEndings.push(this.length);
  78     }
  79     return this._lineEndings;
  80 }
  81
  82 /**
  83  * @return {number}
  84  */
  85 String.prototype.lineCount = function()
  86 {
  87     var lineEndings = this.lineEndings();
  88     return lineEndings.length;
  89 }
  90
  91 /**
  92  * @return {string}
  93  */
  94 String.prototype.lineAt = function(lineNumber)
  95 {
  96     var lineEndings = this.lineEndings();
  97     var lineStart = lineNumber > 0 ? lineEndings[lineNumber - 1] + 1 : 0;
  98     var lineEnd = lineEndings[lineNumber];
  99     var lineContent = this.substring(lineStart, lineEnd);
 100     if (lineContent.length > 0 && lineContent.charAt(lineContent.length - 1) === "\r")
 101         lineContent = lineContent.substring(0, lineContent.length - 1);
 102     return lineContent;
 103 }
 104
 105 /**
 106  * @param {string} chars
 107  * @return {string}
 108  */
 109 String.prototype.escapeCharacters = function(chars)
 110 {
 111     var foundChar = false;
 112     for (var i = 0; i < chars.length; ++i) {
 113         if (this.indexOf(chars.charAt(i)) !== -1) {
 114             foundChar = true;
 115             break;
 116         }
 117     }
 118
 119     if (!foundChar)
 120         return String(this);
 121
 122     var result = "";
 123     for (var i = 0; i < this.length; ++i) {
 124         if (chars.indexOf(this.charAt(i)) !== -1)
 125             result += "\\";
 126         result += this.charAt(i);
 127     }
 128
 129     return result;
 130 }
 131
 132 /**
 133  * @return {string}
 134  */
 135 String.regexSpecialCharacters = function()
 136 {
 137     return "^[]{}()\\.^$*+?|-,";
 138 }
 139
 140 /**
 141  * @return {string}
 142  */
 143 String.prototype.escapeForRegExp = function()
 144 {
 145     return this.escapeCharacters(String.regexSpecialCharacters());
 146 }
 147
 148 /**
 149  * @return {string}
 150  */
 151 String.prototype.escapeHTML = function()
 152 {
 153     return this.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;").replace(/"/g, "&quot;"); //" doublequotes just for editor
 154 }
 155
 156 /**
 157  * @return {string}
 158  */
 159 String.prototype.collapseWhitespace = function()
 160 {
 161     return this.replace(/[\s\xA0]+/g, " ");
 162 }
 163
 164 /**
 165  * @param {number} maxLength
 166  * @return {string}
 167  */
 168 String.prototype.trimMiddle = function(maxLength)
 169 {
 170     if (this.length <= maxLength)
 171         return String(this);
 172     var leftHalf = maxLength >> 1;
 173     var rightHalf = maxLength - leftHalf - 1;
 174     return this.substr(0, leftHalf) + "\u2026" + this.substr(this.length - rightHalf, rightHalf);
 175 }
 176
 177 /**
 178  * @param {number} maxLength
 179  * @return {string}
 180  */
 181 String.prototype.trimEnd = function(maxLength)
 182 {
 183     if (this.length <= maxLength)
 184         return String(this);
 185     return this.substr(0, maxLength - 1) + "\u2026";
 186 }
 187
 188 /**
 189  * @param {?string=} baseURLDomain
 190  * @return {string}
 191  */
 192 String.prototype.trimURL = function(baseURLDomain)
 193 {
 194     var result = this.replace(/^(https|http|file):\/\//i, "");
 195     if (baseURLDomain)
 196         result = result.replace(new RegExp("^" + baseURLDomain.escapeForRegExp(), "i"), "");
 197     return result;
 198 }
 199
 200 /**
 201  * @return {string}
 202  */
 203 String.prototype.toTitleCase = function()
 204 {
 205     return this.substring(0, 1).toUpperCase() + this.substring(1);
 206 }
 207
 208 /**
 209  * @param {string} other
 210  * @return {number}
 211  */
 212 String.prototype.compareTo = function(other)
 213 {
 214     if (this > other)
 215         return 1;
 216     if (this < other)
 217         return -1;
 218     return 0;
 219 }
 220
 221 /**
 222  * @param {string} href
 223  * @return {?string}
 224  */
 225 function sanitizeHref(href)
 226 {
 227     return href && href.trim().toLowerCase().startsWith("javascript:") ? null : href;
 228 }
 229
 230 /**
 231  * @return {string}
 232  */
 233 String.prototype.removeURLFragment = function()
 234 {
 235     var fragmentIndex = this.indexOf("#");
 236     if (fragmentIndex == -1)
 237         fragmentIndex = this.length;
 238     return this.substring(0, fragmentIndex);
 239 }
 240
 241 /**
 242  * @return {boolean}
 243  */
 244 String.prototype.startsWith = function(substring)
 245 {
 246     return !this.lastIndexOf(substring, 0);
 247 }
 248
 249 /**
 250  * @return {boolean}
 251  */
 252 String.prototype.endsWith = function(substring)
 253 {
 254     return this.indexOf(substring, this.length - substring.length) !== -1;
 255 }
 256
 257 /**
 258  * @return {number}
 259  */
 260 String.prototype.hashCode = function()
 261 {
 262     var result = 0;
 263     for (var i = 0; i < this.length; ++i)
 264         result = result * 3 + this.charCodeAt(i);
 265     return result;
 266 }
 267
 268 /**
 269  * @param {string} a
 270  * @param {string} b
 271  * @return {number}
 272  */
 273 String.naturalOrderComparator = function(a, b)
 274 {
 275     var chunk = /^\d+|^\D+/;
 276     var chunka, chunkb, anum, bnum;
 277     while (1) {
 278         if (a) {
 279             if (!b)
 280                 return 1;
 281         } else {
 282             if (b)
 283                 return -1;
 284             else
 285                 return 0;
 286         }
 287         chunka = a.match(chunk)[0];
 288         chunkb = b.match(chunk)[0];
 289         anum = !isNaN(chunka);
 290         bnum = !isNaN(chunkb);
 291         if (anum && !bnum)
 292             return -1;
 293         if (bnum && !anum)
 294             return 1;
 295         if (anum && bnum) {
 296             var diff = chunka - chunkb;
 297             if (diff)
 298                 return diff;
 299             if (chunka.length !== chunkb.length) {
 300                 if (!+chunka && !+chunkb) // chunks are strings of all 0s (special case)
 301                     return chunka.length - chunkb.length;
 302                 else
 303                     return chunkb.length - chunka.length;
 304             }
 305         } else if (chunka !== chunkb)
 306             return (chunka < chunkb) ? -1 : 1;
 307         a = a.substring(chunka.length);
 308         b = b.substring(chunkb.length);
 309     }
 310 }
 311
 312 /**
 313  * @param {number} num
 314  * @param {number} min
 315  * @param {number} max
 316  * @return {number}
 317  */
 318 Number.constrain = function(num, min, max)
 319 {
 320     if (num < min)
 321         num = min;
 322     else if (num > max)
 323         num = max;
 324     return num;
 325 }
 326
 327 /**
 328  * @param {number} a
 329  * @param {number} b
 330  * @return {number}
 331  */
 332 Number.gcd = function(a, b)
 333 {
 334     if (b === 0)
 335         return a;
 336     else
 337         return Number.gcd(b, a % b);
 338 }
 339
 340 /**
 341  * @param {string} value
 342  * @return {string}
 343  */
 344 Number.toFixedIfFloating = function(value)
 345 {
 346     if (!value || isNaN(value))
 347         return value;
 348     var number = Number(value);
 349     return number % 1 ? number.toFixed(3) : String(number);
 350 }
 351
 352 /**
 353  * @return {string}
 354  */
 355 Date.prototype.toISO8601Compact = function()
 356 {
 357     /**
 358      * @param {number} x
 359      * @return {string}
 360      */
 361     function leadZero(x)
 362     {
 363         return (x > 9 ? "" : "0") + x;
 364     }
 365     return this.getFullYear() +
 366            leadZero(this.getMonth() + 1) +
 367            leadZero(this.getDate()) + "T" +
 368            leadZero(this.getHours()) +
 369            leadZero(this.getMinutes()) +
 370            leadZero(this.getSeconds());
 371 }
 372
 373 /**
 374  * @return {string}
 375  */
 376  Date.prototype.toConsoleTime = function()
 377 {
 378     /**
 379      * @param {number} x
 380      * @return {string}
 381      */
 382     function leadZero2(x)
 383     {
 384         return (x > 9 ? "" : "0") + x;
 385     }
 386
 387     /**
 388      * @param {number} x
 389      * @return {string}
 390      */
 391     function leadZero3(x)
 392     {
 393         return (Array(4 - x.toString().length)).join('0') + x;
 394     }
 395
 396     return this.getFullYear() + "-" +
 397            leadZero2(this.getMonth() + 1) + "-" +
 398            leadZero2(this.getDate()) + " " +
 399            leadZero2(this.getHours()) + ":" +
 400            leadZero2(this.getMinutes()) + ":" +
 401            leadZero2(this.getSeconds()) + "." +
 402            leadZero3(this.getMilliseconds());
 403 }
 404
 405 Object.defineProperty(Array.prototype, "remove",
 406 {
 407     /**
 408      * @param {!T} value
 409      * @param {boolean=} firstOnly
 410      * @this {Array.<!T>}
 411      * @template T
 412      */
 413     value: function(value, firstOnly)
 414     {
 415         var index = this.indexOf(value);
 416         if (index === -1)
 417             return;
 418         if (firstOnly) {
 419             this.splice(index, 1);
 420             return;
 421         }
 422         for (var i = index + 1, n = this.length; i < n; ++i) {
 423             if (this[i] !== value)
 424                 this[index++] = this[i];
 425         }
 426         this.length = index;
 427     }
 428 });
 429
 430 Object.defineProperty(Array.prototype, "keySet",
 431 {
 432     /**
 433      * @return {!Object.<string, boolean>}
 434      * @this {Array.<*>}
 435      */
 436     value: function()
 437     {
 438         var keys = {};
 439         for (var i = 0; i < this.length; ++i)
 440             keys[this[i]] = true;
 441         return keys;
 442     }
 443 });
 444
 445 Object.defineProperty(Array.prototype, "rotate",
 446 {
 447     /**
 448      * @param {number} index
 449      * @return {!Array.<!T>}
 450      * @this {Array.<!T>}
 451      * @template T
 452      */
 453     value: function(index)
 454     {
 455         var result = [];
 456         for (var i = index; i < index + this.length; ++i)
 457             result.push(this[i % this.length]);
 458         return result;
 459     }
 460 });
 461
 462 Object.defineProperty(Uint32Array.prototype, "sort", {
 463    value: Array.prototype.sort
 464 });
 465
 466 (function() {
 467 var partition = {
 468     /**
 469      * @this {Array.<number>}
 470      * @param {function(number, number): number} comparator
 471      * @param {number} left
 472      * @param {number} right
 473      * @param {number} pivotIndex
 474      */
 475     value: function(comparator, left, right, pivotIndex)
 476     {
 477         function swap(array, i1, i2)
 478         {
 479             var temp = array[i1];
 480             array[i1] = array[i2];
 481             array[i2] = temp;
 482         }
 483
 484         var pivotValue = this[pivotIndex];
 485         swap(this, right, pivotIndex);
 486         var storeIndex = left;
 487         for (var i = left; i < right; ++i) {
 488             if (comparator(this[i], pivotValue) < 0) {
 489                 swap(this, storeIndex, i);
 490                 ++storeIndex;
 491             }
 492         }
 493         swap(this, right, storeIndex);
 494         return storeIndex;
 495     }
 496 };
 497 Object.defineProperty(Array.prototype, "partition", partition);
 498 Object.defineProperty(Uint32Array.prototype, "partition", partition);
 499
 500 var sortRange = {
 501     /**
 502      * @param {function(number, number): number} comparator
 503      * @param {number} leftBound
 504      * @param {number} rightBound
 505      * @param {number} sortWindowLeft
 506      * @param {number} sortWindowRight
 507      * @return {!Array.<number>}
 508      * @this {Array.<number>}
 509      */
 510     value: function(comparator, leftBound, rightBound, sortWindowLeft, sortWindowRight)
 511     {
 512         function quickSortRange(array, comparator, left, right, sortWindowLeft, sortWindowRight)
 513         {
 514             if (right <= left)
 515                 return;
 516             var pivotIndex = Math.floor(Math.random() * (right - left)) + left;
 517             var pivotNewIndex = array.partition(comparator, left, right, pivotIndex);
 518             if (sortWindowLeft < pivotNewIndex)
 519                 quickSortRange(array, comparator, left, pivotNewIndex - 1, sortWindowLeft, sortWindowRight);
 520             if (pivotNewIndex < sortWindowRight)
 521                 quickSortRange(array, comparator, pivotNewIndex + 1, right, sortWindowLeft, sortWindowRight);
 522         }
 523         if (leftBound === 0 && rightBound === (this.length - 1) && sortWindowLeft === 0 && sortWindowRight >= rightBound)
 524             this.sort(comparator);
 525         else
 526             quickSortRange(this, comparator, leftBound, rightBound, sortWindowLeft, sortWindowRight);
 527         return this;
 528     }
 529 }
 530 Object.defineProperty(Array.prototype, "sortRange", sortRange);
 531 Object.defineProperty(Uint32Array.prototype, "sortRange", sortRange);
 532 })();
 533
 534 Object.defineProperty(Array.prototype, "stableSort",
 535 {
 536     /**
 537      * @param {function(?T, ?T): number=} comparator
 538      * @return {!Array.<?T>}
 539      * @this {Array.<?T>}
 540      * @template T
 541      */
 542     value: function(comparator)
 543     {
 544         function defaultComparator(a, b)
 545         {
 546             return a < b ? -1 : (a > b ? 1 : 0);
 547         }
 548         comparator = comparator || defaultComparator;
 549
 550         var indices = new Array(this.length);
 551         for (var i = 0; i < this.length; ++i)
 552             indices[i] = i;
 553         var self = this;
 554         /**
 555          * @param {number} a
 556          * @param {number} b
 557          * @return {number}
 558          */
 559         function indexComparator(a, b)
 560         {
 561             var result = comparator(self[a], self[b]);
 562             return result ? result : a - b;
 563         }
 564         indices.sort(indexComparator);
 565
 566         for (var i = 0; i < this.length; ++i) {
 567             if (indices[i] < 0 || i === indices[i])
 568                 continue;
 569             var cyclical = i;
 570             var saved = this[i];
 571             while (true) {
 572                 var next = indices[cyclical];
 573                 indices[cyclical] = -1;
 574                 if (next === i) {
 575                     this[cyclical] = saved;
 576                     break;
 577                 } else {
 578                     this[cyclical] = this[next];
 579                     cyclical = next;
 580                 }
 581             }
 582         }
 583         return this;
 584     }
 585 });
 586
 587 Object.defineProperty(Array.prototype, "qselect",
 588 {
 589     /**
 590      * @param {number} k
 591      * @param {function(number, number): number=} comparator
 592      * @return {number|undefined}
 593      * @this {Array.<number>}
 594      */
 595     value: function(k, comparator)
 596     {
 597         if (k < 0 || k >= this.length)
 598             return;
 599         if (!comparator)
 600             comparator = function(a, b) { return a - b; }
 601
 602         var low = 0;
 603         var high = this.length - 1;
 604         for (;;) {
 605             var pivotPosition = this.partition(comparator, low, high, Math.floor((high + low) / 2));
 606             if (pivotPosition === k)
 607                 return this[k];
 608             else if (pivotPosition > k)
 609                 high = pivotPosition - 1;
 610             else
 611                 low = pivotPosition + 1;
 612         }
 613     }
 614 });
 615
 616 Object.defineProperty(Array.prototype, "lowerBound",
 617 {
 618     /**
 619      * Return index of the leftmost element that is equal or greater
 620      * than the specimen object. If there's no such element (i.e. all
 621      * elements are smaller than the specimen) returns right bound.
 622      * The function works for sorted array.
 623      * When specified, |left| (inclusive) and |right| (exclusive) indices
 624      * define the search window.
 625      *
 626      * @param {!T} object
 627      * @param {function(!T,!S):number=} comparator
 628      * @param {number=} left
 629      * @param {number=} right
 630      * @return {number}
 631      * @this {Array.<!S>}
 632      * @template T,S
 633      */
 634     value: function(object, comparator, left, right)
 635     {
 636         function defaultComparator(a, b)
 637         {
 638             return a < b ? -1 : (a > b ? 1 : 0);
 639         }
 640         comparator = comparator || defaultComparator;
 641         var l = left || 0;
 642         var r = right !== undefined ? right : this.length;
 643         while (l < r) {
 644             var m = (l + r) >> 1;
 645             if (comparator(object, this[m]) > 0)
 646                 l = m + 1;
 647             else
 648                 r = m;
 649         }
 650         return r;
 651     }
 652 });
 653
 654 Object.defineProperty(Array.prototype, "upperBound",
 655 {
 656     /**
 657      * Return index of the leftmost element that is greater
 658      * than the specimen object. If there's no such element (i.e. all
 659      * elements are smaller or equal to the specimen) returns right bound.
 660      * The function works for sorted array.
 661      * When specified, |left| (inclusive) and |right| (exclusive) indices
 662      * define the search window.
 663      *
 664      * @param {!T} object
 665      * @param {function(!T,!S):number=} comparator
 666      * @param {number=} left
 667      * @param {number=} right
 668      * @return {number}
 669      * @this {Array.<!S>}
 670      * @template T,S
 671      */
 672     value: function(object, comparator, left, right)
 673     {
 674         function defaultComparator(a, b)
 675         {
 676             return a < b ? -1 : (a > b ? 1 : 0);
 677         }
 678         comparator = comparator || defaultComparator;
 679         var l = left || 0;
 680         var r = right !== undefined ? right : this.length;
 681         while (l < r) {
 682             var m = (l + r) >> 1;
 683             if (comparator(object, this[m]) >= 0)
 684                 l = m + 1;
 685             else
 686                 r = m;
 687         }
 688         return r;
 689     }
 690 });
 691
 692 Object.defineProperty(Array.prototype, "binaryIndexOf",
 693 {
 694     /**
 695      * @param {!T} value
 696      * @param {function(!T,!S):number} comparator
 697      * @return {number}
 698      * @this {Array.<!S>}
 699      * @template T,S
 700      */
 701     value: function(value, comparator)
 702     {
 703         var index = this.lowerBound(value, comparator);
 704         return index < this.length && comparator(value, this[index]) === 0 ? index : -1;
 705     }
 706 });
 707
 708 Object.defineProperty(Array.prototype, "select",
 709 {
 710     /**
 711      * @param {string} field
 712      * @return {!Array.<!T>}
 713      * @this {Array.<!Object.<string,!T>>}
 714      * @template T
 715      */
 716     value: function(field)
 717     {
 718         var result = new Array(this.length);
 719         for (var i = 0; i < this.length; ++i)
 720             result[i] = this[i][field];
 721         return result;
 722     }
 723 });
 724
 725 Object.defineProperty(Array.prototype, "peekLast",
 726 {
 727     /**
 728      * @return {!T|undefined}
 729      * @this {Array.<!T>}
 730      * @template T
 731      */
 732     value: function()
 733     {
 734         return this[this.length - 1];
 735     }
 736 });
 737
 738 (function(){
 739
 740 /**
 741  * @param {!Array.<T>} array1
 742  * @param {!Array.<T>} array2
 743  * @param {function(T,T):number} comparator
 744  * @return {!Array.<T>}
 745  * @template T
 746  */
 747 function mergeOrIntersect(array1, array2, comparator, mergeNotIntersect)
 748 {
 749     var result = [];
 750     var i = 0;
 751     var j = 0;
 752     while (i < array1.length && j < array2.length) {
 753         var compareValue = comparator(array1[i], array2[j]);
 754         if (mergeNotIntersect || !compareValue)
 755             result.push(compareValue <= 0 ? array1[i] : array2[j]);
 756         if (compareValue <= 0)
 757             i++;
 758         if (compareValue >= 0)
 759             j++;
 760     }
 761     if (mergeNotIntersect) {
 762         while (i < array1.length)
 763             result.push(array1[i++]);
 764         while (j < array2.length)
 765             result.push(array2[j++]);
 766     }
 767     return result;
 768 }
 769
 770 Object.defineProperty(Array.prototype, "intersectOrdered",
 771 {
 772     /**
 773      * @param {!Array.<T>} array
 774      * @param {function(T,T):number} comparator
 775      * @return {!Array.<T>}
 776      * @this {!Array.<T>}
 777      * @template T
 778      */
 779     value: function(array, comparator)
 780     {
 781         return mergeOrIntersect(this, array, comparator, false);
 782     }
 783 });
 784
 785 Object.defineProperty(Array.prototype, "mergeOrdered",
 786 {
 787     /**
 788      * @param {!Array.<T>} array
 789      * @param {function(T,T):number} comparator
 790      * @return {!Array.<T>}
 791      * @this {!Array.<T>}
 792      * @template T
 793      */
 794     value: function(array, comparator)
 795     {
 796         return mergeOrIntersect(this, array, comparator, true);
 797     }
 798 });
 799
 800 }());
 801
 802
 803 /**
 804  * @param {!T} object
 805  * @param {!Array.<!S>} list
 806  * @param {function(!T,!S):number=} comparator
 807  * @param {boolean=} insertionIndexAfter
 808  * @return {number}
 809  * @template T,S
 810  */
 811 function insertionIndexForObjectInListSortedByFunction(object, list, comparator, insertionIndexAfter)
 812 {
 813     if (insertionIndexAfter)
 814         return list.upperBound(object, comparator);
 815     else
 816         return list.lowerBound(object, comparator);
 817 }
 818
 819 /**
 820  * @param {string} format
 821  * @param {...*} var_arg
 822  * @return {string}
 823  */
 824 String.sprintf = function(format, var_arg)
 825 {
 826     return String.vsprintf(format, Array.prototype.slice.call(arguments, 1));
 827 }
 828
 829 String.tokenizeFormatString = function(format, formatters)
 830 {
 831     var tokens = [];
 832     var substitutionIndex = 0;
 833
 834     function addStringToken(str)
 835     {
 836         tokens.push({ type: "string", value: str });
 837     }
 838
 839     function addSpecifierToken(specifier, precision, substitutionIndex)
 840     {
 841         tokens.push({ type: "specifier", specifier: specifier, precision: precision, substitutionIndex: substitutionIndex });
 842     }
 843
 844     function isDigit(c)
 845     {
 846         return !!/[0-9]/.exec(c);
 847     }
 848
 849     var index = 0;
 850     for (var precentIndex = format.indexOf("%", index); precentIndex !== -1; precentIndex = format.indexOf("%", index)) {
 851         addStringToken(format.substring(index, precentIndex));
 852         index = precentIndex + 1;
 853
 854         if (isDigit(format[index])) {
 855             // The first character is a number, it might be a substitution index.
 856             var number = parseInt(format.substring(index), 10);
 857             while (isDigit(format[index]))
 858                 ++index;
 859
 860             // If the number is greater than zero and ends with a "$",
 861             // then this is a substitution index.
 862             if (number > 0 && format[index] === "$") {
 863                 substitutionIndex = (number - 1);
 864                 ++index;
 865             }
 866         }
 867
 868         var precision = -1;
 869         if (format[index] === ".") {
 870             // This is a precision specifier. If no digit follows the ".",
 871             // then the precision should be zero.
 872             ++index;
 873             precision = parseInt(format.substring(index), 10);
 874             if (isNaN(precision))
 875                 precision = 0;
 876
 877             while (isDigit(format[index]))
 878                 ++index;
 879         }
 880
 881         if (!(format[index] in formatters)) {
 882             addStringToken(format.substring(precentIndex, index + 1));
 883             ++index;
 884             continue;
 885         }
 886
 887         addSpecifierToken(format[index], precision, substitutionIndex);
 888
 889         ++substitutionIndex;
 890         ++index;
 891     }
 892
 893     addStringToken(format.substring(index));
 894
 895     return tokens;
 896 }
 897
 898 String.standardFormatters = {
 899     /**
 900      * @return {number}
 901      */
 902     d: function(substitution)
 903     {
 904         return !isNaN(substitution) ? substitution : 0;
 905     },
 906
 907     /**
 908      * @return {number}
 909      */
 910     f: function(substitution, token)
 911     {
 912         if (substitution && token.precision > -1)
 913             substitution = substitution.toFixed(token.precision);
 914         return !isNaN(substitution) ? substitution : (token.precision > -1 ? Number(0).toFixed(token.precision) : 0);
 915     },
 916
 917     /**
 918      * @return {string}
 919      */
 920     s: function(substitution)
 921     {
 922         return substitution;
 923     }
 924 }
 925
 926 /**
 927  * @param {string} format
 928  * @param {!Array.<*>} substitutions
 929  * @return {string}
 930  */
 931 String.vsprintf = function(format, substitutions)
 932 {
 933     return String.format(format, substitutions, String.standardFormatters, "", function(a, b) { return a + b; }).formattedResult;
 934 }
 935
 936 String.format = function(format, substitutions, formatters, initialValue, append)
 937 {
 938     if (!format || !substitutions || !substitutions.length)
 939         return { formattedResult: append(initialValue, format), unusedSubstitutions: substitutions };
 940
 941     function prettyFunctionName()
 942     {
 943         return "String.format(\"" + format + "\", \"" + substitutions.join("\", \"") + "\")";
 944     }
 945
 946     function warn(msg)
 947     {
 948         console.warn(prettyFunctionName() + ": " + msg);
 949     }
 950
 951     function error(msg)
 952     {
 953         console.error(prettyFunctionName() + ": " + msg);
 954     }
 955
 956     var result = initialValue;
 957     var tokens = String.tokenizeFormatString(format, formatters);
 958     var usedSubstitutionIndexes = {};
 959
 960     for (var i = 0; i < tokens.length; ++i) {
 961         var token = tokens[i];
 962
 963         if (token.type === "string") {
 964             result = append(result, token.value);
 965             continue;
 966         }
 967
 968         if (token.type !== "specifier") {
 969             error("Unknown token type \"" + token.type + "\" found.");
 970             continue;
 971         }
 972
 973         if (token.substitutionIndex >= substitutions.length) {
 974             // If there are not enough substitutions for the current substitutionIndex
 975             // just output the format specifier literally and move on.
 976             error("not enough substitution arguments. Had " + substitutions.length + " but needed " + (token.substitutionIndex + 1) + ", so substitution was skipped.");
 977             result = append(result, "%" + (token.precision > -1 ? token.precision : "") + token.specifier);
 978             continue;
 979         }
 980
 981         usedSubstitutionIndexes[token.substitutionIndex] = true;
 982
 983         if (!(token.specifier in formatters)) {
 984             // Encountered an unsupported format character, treat as a string.
 985             warn("unsupported format character \u201C" + token.specifier + "\u201D. Treating as a string.");
 986             result = append(result, substitutions[token.substitutionIndex]);
 987             continue;
 988         }
 989
 990         result = append(result, formatters[token.specifier](substitutions[token.substitutionIndex], token));
 991     }
 992
 993     var unusedSubstitutions = [];
 994     for (var i = 0; i < substitutions.length; ++i) {
 995         if (i in usedSubstitutionIndexes)
 996             continue;
 997         unusedSubstitutions.push(substitutions[i]);
 998     }
 999
1000     return { formattedResult: result, unusedSubstitutions: unusedSubstitutions };
1001 }
1002
1003 /**
1004  * @param {string} query
1005  * @param {boolean} caseSensitive
1006  * @param {boolean} isRegex
1007  * @return {!RegExp}
1008  */
1009 function createSearchRegex(query, caseSensitive, isRegex)
1010 {
1011     var regexFlags = caseSensitive ? "g" : "gi";
1012     var regexObject;
1013
1014     if (isRegex) {
1015         try {
1016             regexObject = new RegExp(query, regexFlags);
1017         } catch (e) {
1018             // Silent catch.
1019         }
1020     }
1021
1022     if (!regexObject)
1023         regexObject = createPlainTextSearchRegex(query, regexFlags);
1024
1025     return regexObject;
1026 }
1027
1028 /**
1029  * @param {string} query
1030  * @param {string=} flags
1031  * @return {!RegExp}
1032  */
1033 function createPlainTextSearchRegex(query, flags)
1034 {
1035     // This should be kept the same as the one in ContentSearchUtils.cpp.
1036     var regexSpecialCharacters = String.regexSpecialCharacters();
1037     var regex = "";
1038     for (var i = 0; i < query.length; ++i) {
1039         var c = query.charAt(i);
1040         if (regexSpecialCharacters.indexOf(c) != -1)
1041             regex += "\\";
1042         regex += c;
1043     }
1044     return new RegExp(regex, flags || "");
1045 }
1046
1047 /**
1048  * @param {!RegExp} regex
1049  * @param {string} content
1050  * @return {number}
1051  */
1052 function countRegexMatches(regex, content)
1053 {
1054     var text = content;
1055     var result = 0;
1056     var match;
1057     while (text && (match = regex.exec(text))) {
1058         if (match[0].length > 0)
1059             ++result;
1060         text = text.substring(match.index + 1);
1061     }
1062     return result;
1063 }
1064
1065 /**
1066  * @param {number} value
1067  * @param {number} symbolsCount
1068  * @return {string}
1069  */
1070 function numberToStringWithSpacesPadding(value, symbolsCount)
1071 {
1072     var numberString = value.toString();
1073     var paddingLength = Math.max(0, symbolsCount - numberString.length);
1074     var paddingString = Array(paddingLength + 1).join("\u00a0");
1075     return paddingString + numberString;
1076 }
1077
1078 /**
1079  * @return {string}
1080  */
1081 var createObjectIdentifier = function()
1082 {
1083     // It has to be string for better performance.
1084     return "_" + ++createObjectIdentifier._last;
1085 }
1086
1087 createObjectIdentifier._last = 0;
1088
1089 /**
1090  * @constructor
1091  * @template T
1092  */
1093 var Set = function()
1094 {
1095     /** @type {!Object.<string, !T>} */
1096     this._set = {};
1097     this._size = 0;
1098 }
1099
1100 Set.prototype = {
1101     /**
1102      * @param {!T} item
1103      */
1104     add: function(item)
1105     {
1106         var objectIdentifier = item.__identifier;
1107         if (!objectIdentifier) {
1108             objectIdentifier = createObjectIdentifier();
1109             item.__identifier = objectIdentifier;
1110         }
1111         if (!this._set[objectIdentifier])
1112             ++this._size;
1113         this._set[objectIdentifier] = item;
1114     },
1115
1116     /**
1117      * @param {!T} item
1118      * @return {boolean}
1119      */
1120     remove: function(item)
1121     {
1122         if (this._set[item.__identifier]) {
1123             --this._size;
1124             delete this._set[item.__identifier];
1125             return true;
1126         }
1127         return false;
1128     },
1129
1130     /**
1131      * @return {!Array.<!T>}
1132      */
1133     items: function()
1134     {
1135         var result = new Array(this._size);
1136         var i = 0;
1137         for (var objectIdentifier in this._set)
1138             result[i++] = this._set[objectIdentifier];
1139         return result;
1140     },
1141
1142     /**
1143      * @param {!T} item
1144      * @return {boolean}
1145      */
1146     hasItem: function(item)
1147     {
1148         return !!this._set[item.__identifier];
1149     },
1150
1151     /**
1152      * @return {number}
1153      */
1154     size: function()
1155     {
1156         return this._size;
1157     },
1158
1159     clear: function()
1160     {
1161         this._set = {};
1162         this._size = 0;
1163     }
1164 }
1165
1166 /**
1167  * @constructor
1168  * @template K,V
1169  */
1170 var Map = function()
1171 {
1172     /** @type {!Object.<string, !Array.<K|V>>} */
1173     this._map = {};
1174     this._size = 0;
1175 }
1176
1177 Map.prototype = {
1178     /**
1179      * @param {K} key
1180      * @param {V} value
1181      */
1182     put: function(key, value)
1183     {
1184         var objectIdentifier = key.__identifier;
1185         if (!objectIdentifier) {
1186             objectIdentifier = createObjectIdentifier();
1187             key.__identifier = objectIdentifier;
1188         }
1189         if (!this._map[objectIdentifier])
1190             ++this._size;
1191         this._map[objectIdentifier] = [key, value];
1192     },
1193
1194     /**
1195      * @param {K} key
1196      * @return {V}
1197      */
1198     remove: function(key)
1199     {
1200         var result = this._map[key.__identifier];
1201         if (!result)
1202             return undefined;
1203         --this._size;
1204         delete this._map[key.__identifier];
1205         return result[1];
1206     },
1207
1208     /**
1209      * @return {!Array.<K>}
1210      */
1211     keys: function()
1212     {
1213         return this._list(0);
1214     },
1215
1216     /**
1217      * @return {!Array.<V>}
1218      */
1219     values: function()
1220     {
1221         return this._list(1);
1222     },
1223
1224     /**
1225      * @param {number} index
1226      * @return {!Array.<K|V>}
1227      */
1228     _list: function(index)
1229     {
1230         var result = new Array(this._size);
1231         var i = 0;
1232         for (var objectIdentifier in this._map)
1233             result[i++] = this._map[objectIdentifier][index];
1234         return result;
1235     },
1236
1237     /**
1238      * @param {K} key
1239      * @return {V|undefined}
1240      */
1241     get: function(key)
1242     {
1243         var entry = this._map[key.__identifier];
1244         return entry ? entry[1] : undefined;
1245     },
1246
1247     /**
1248      * @param {K} key
1249      * @return {boolean}
1250      */
1251     contains: function(key)
1252     {
1253         var entry = this._map[key.__identifier];
1254         return !!entry;
1255     },
1256
1257     /**
1258      * @return {number}
1259      */
1260     size: function()
1261     {
1262         return this._size;
1263     },
1264
1265     clear: function()
1266     {
1267         this._map = {};
1268         this._size = 0;
1269     }
1270 }
1271
1272 /**
1273  * @constructor
1274  * @template T
1275  */
1276 var StringMap = function()
1277 {
1278     /** @type {!Object.<string, T>} */
1279     this._map = {};
1280     this._size = 0;
1281 }
1282
1283 StringMap.prototype = {
1284     /**
1285      * @param {string} key
1286      * @param {T} value
1287      */
1288     put: function(key, value)
1289     {
1290         if (key === "__proto__") {
1291             if (!this._hasProtoKey) {
1292                 ++this._size;
1293                 this._hasProtoKey = true;
1294             }
1295             /** @type {T} */
1296             this._protoValue = value;
1297             return;
1298         }
1299         if (!Object.prototype.hasOwnProperty.call(this._map, key))
1300             ++this._size;
1301         this._map[key] = value;
1302     },
1303
1304     /**
1305      * @param {string} key
1306      * @return {T|undefined}
1307      */
1308     remove: function(key)
1309     {
1310         var result;
1311         if (key === "__proto__") {
1312             if (!this._hasProtoKey)
1313                 return undefined;
1314             --this._size;
1315             delete this._hasProtoKey;
1316             result = this._protoValue;
1317             delete this._protoValue;
1318             return result;
1319         }
1320         if (!Object.prototype.hasOwnProperty.call(this._map, key))
1321             return undefined;
1322         --this._size;
1323         result = this._map[key];
1324         delete this._map[key];
1325         return result;
1326     },
1327
1328     /**
1329      * @return {!Array.<string>}
1330      */
1331     keys: function()
1332     {
1333         var result = Object.keys(this._map) || [];
1334         if (this._hasProtoKey)
1335             result.push("__proto__");
1336         return result;
1337     },
1338
1339     /**
1340      * @return {!Array.<T>}
1341      */
1342     values: function()
1343     {
1344         var result = Object.values(this._map);
1345         if (this._hasProtoKey)
1346             result.push(this._protoValue);
1347         return result;
1348     },
1349
1350     /**
1351      * @param {string} key
1352      * @return {T|undefined}
1353      */
1354     get: function(key)
1355     {
1356         if (key === "__proto__")
1357             return this._protoValue;
1358         if (!Object.prototype.hasOwnProperty.call(this._map, key))
1359             return undefined;
1360         return this._map[key];
1361     },
1362
1363     /**
1364      * @param {string} key
1365      * @return {boolean}
1366      */
1367     contains: function(key)
1368     {
1369         var result;
1370         if (key === "__proto__")
1371             return this._hasProtoKey;
1372         return Object.prototype.hasOwnProperty.call(this._map, key);
1373     },
1374
1375     /**
1376      * @return {number}
1377      */
1378     size: function()
1379     {
1380         return this._size;
1381     },
1382
1383     clear: function()
1384     {
1385         this._map = {};
1386         this._size = 0;
1387         delete this._hasProtoKey;
1388         delete this._protoValue;
1389     }
1390 }
1391
1392 /**
1393  * @constructor
1394  */
1395 var StringSet = function()
1396 {
1397     /** @type {!StringMap.<boolean>} */
1398     this._map = new StringMap();
1399 }
1400
1401 StringSet.prototype = {
1402     /**
1403      * @param {string} value
1404      */
1405     put: function(value)
1406     {
1407         this._map.put(value, true);
1408     },
1409
1410     /**
1411      * @param {string} value
1412      * @return {boolean}
1413      */
1414     remove: function(value)
1415     {
1416         return !!this._map.remove(value);
1417     },
1418
1419     /**
1420      * @return {!Array.<string>}
1421      */
1422     values: function()
1423     {
1424         return this._map.keys();
1425     },
1426
1427     /**
1428      * @param {string} value
1429      * @return {boolean}
1430      */
1431     contains: function(value)
1432     {
1433         return this._map.contains(value);
1434     },
1435
1436     /**
1437      * @return {number}
1438      */
1439     size: function()
1440     {
1441         return this._map.size();
1442     },
1443
1444     clear: function()
1445     {
1446         this._map.clear();
1447     }
1448 }
1449
1450 /**
1451  * @param {string} url
1452  * @param {boolean=} async
1453  * @param {function(?string)=} callback
1454  * @return {?string}
1455  */
1456 function loadXHR(url, async, callback)
1457 {
1458     function onReadyStateChanged()
1459     {
1460         if (xhr.readyState !== XMLHttpRequest.DONE)
1461             return;
1462
1463         if (xhr.status === 200) {
1464             callback(xhr.responseText);
1465             return;
1466         }
1467
1468         callback(null);
1469    }
1470
1471     var xhr = new XMLHttpRequest();
1472     xhr.open("GET", url, async);
1473     if (async)
1474         xhr.onreadystatechange = onReadyStateChanged;
1475     xhr.send(null);
1476
1477     if (!async) {
1478         if (xhr.status === 200)
1479             return xhr.responseText;
1480         return null;
1481     }
1482     return null;
1483 }
1484
1485 var _importedScripts = {};
1486
1487 /**
1488  * This function behavior depends on the "debug_devtools" flag value.
1489  * - In debug mode it loads scripts synchronously via xhr request.
1490  * - In release mode every occurrence of "importScript" in the js files
1491  *   that have been white listed in the build system gets replaced with
1492  *   the script source code on the compilation phase.
1493  *   The build system will throw an exception if it found importScript call
1494  *   in other files.
1495  *
1496  * To load scripts lazily in release mode call "loadScript" function.
1497  * @param {string} scriptName
1498  */
1499 function importScript(scriptName)
1500 {
1501     if (_importedScripts[scriptName])
1502         return;
1503     var xhr = new XMLHttpRequest();
1504     _importedScripts[scriptName] = true;
1505     xhr.open("GET", scriptName, false);
1506     xhr.send(null);
1507     if (!xhr.responseText)
1508         throw "empty response arrived for script '" + scriptName + "'";
1509     var baseUrl = location.origin + location.pathname;
1510     baseUrl = baseUrl.substring(0, baseUrl.lastIndexOf("/"));
1511     var sourceURL = baseUrl + "/" + scriptName;
1512     self.eval(xhr.responseText + "\n//# sourceURL=" + sourceURL);
1513 }
1514
1515 var loadScript = importScript;
1516
1517 /**
1518  * @constructor
1519  */
1520 function CallbackBarrier()
1521 {
1522     this._pendingIncomingCallbacksCount = 0;
1523 }
1524
1525 CallbackBarrier.prototype = {
1526     /**
1527      * @param {function(!T)=} userCallback
1528      * @return {function(!T=)}
1529      * @template T
1530      */
1531     createCallback: function(userCallback)
1532     {
1533         console.assert(!this._outgoingCallback, "CallbackBarrier.createCallback() is called after CallbackBarrier.callWhenDone()");
1534         ++this._pendingIncomingCallbacksCount;
1535         return this._incomingCallback.bind(this, userCallback);
1536     },
1537
1538     /**
1539      * @param {function()} callback
1540      */
1541     callWhenDone: function(callback)
1542     {
1543         console.assert(!this._outgoingCallback, "CallbackBarrier.callWhenDone() is called multiple times");
1544         this._outgoingCallback = callback;
1545         if (!this._pendingIncomingCallbacksCount)
1546             this._outgoingCallback();
1547     },
1548
1549     /**
1550      * @param {function(...)=} userCallback
1551      */
1552     _incomingCallback: function(userCallback)
1553     {
1554         console.assert(this._pendingIncomingCallbacksCount > 0);
1555         if (userCallback) {
1556             var args = Array.prototype.slice.call(arguments, 1);
1557             userCallback.apply(null, args);
1558         }
1559         if (!--this._pendingIncomingCallbacksCount && this._outgoingCallback)
1560             this._outgoingCallback();
1561     }
1562 }
1563
1564 /**
1565  * @param {*} value
1566  */
1567 function suppressUnused(value)
1568 {
1569 }