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