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