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