f215ce15709279968a54bbd6cbc9f58133736743
[WebKit-https.git] / Source / WebCore / inspector / front-end / utilities.js
1 /*
2  * Copyright (C) 2007 Apple Inc.  All rights reserved.
3  * Copyright (C) 2012 Google Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer.
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution.
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 Object.isEmpty = function(obj)
31 {
32     for (var i in obj)
33         return false;
34     return true;
35 }
36
37 Object.values = function(obj)
38 {
39     var keys = Object.keys(obj);
40     var result = [];
41
42     for (var i = 0; i < keys.length; ++i)
43         result.push(obj[keys[i]]);
44     return result;
45 }
46
47 String.prototype.hasSubstring = function(string, caseInsensitive)
48 {
49     if (!caseInsensitive)
50         return this.indexOf(string) !== -1;
51     return this.match(new RegExp(string.escapeForRegExp(), "i"));
52 }
53
54 String.prototype.findAll = function(string)
55 {
56     var matches = [];
57     var i = this.indexOf(string);
58     while (i !== -1) {
59         matches.push(i);
60         i = this.indexOf(string, i + string.length);
61     }
62     return matches;
63 }
64
65 String.prototype.lineEndings = function()
66 {
67     if (!this._lineEndings) {
68         this._lineEndings = this.findAll("\n");
69         this._lineEndings.push(this.length);
70     }
71     return this._lineEndings;
72 }
73
74 String.prototype.escapeCharacters = function(chars)
75 {
76     var foundChar = false;
77     for (var i = 0; i < chars.length; ++i) {
78         if (this.indexOf(chars.charAt(i)) !== -1) {
79             foundChar = true;
80             break;
81         }
82     }
83
84     if (!foundChar)
85         return this;
86
87     var result = "";
88     for (var i = 0; i < this.length; ++i) {
89         if (chars.indexOf(this.charAt(i)) !== -1)
90             result += "\\";
91         result += this.charAt(i);
92     }
93
94     return result;
95 }
96
97 String.prototype.escapeForRegExp = function()
98 {
99     return this.escapeCharacters("^[]{}()\\.$*+?|");
100 }
101
102 String.prototype.escapeHTML = function()
103 {
104     return this.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;").replace(/"/g, "&quot;"); //" doublequotes just for editor
105 }
106
107 String.prototype.collapseWhitespace = function()
108 {
109     return this.replace(/[\s\xA0]+/g, " ");
110 }
111
112 String.prototype.trimMiddle = function(maxLength)
113 {
114     if (this.length <= maxLength)
115         return this;
116     var leftHalf = maxLength >> 1;
117     var rightHalf = maxLength - leftHalf - 1;
118     return this.substr(0, leftHalf) + "\u2026" + this.substr(this.length - rightHalf, rightHalf);
119 }
120
121 String.prototype.trimEnd = function(maxLength)
122 {
123     if (this.length <= maxLength)
124         return this;
125     return this.substr(0, maxLength - 1) + "\u2026";
126 }
127
128 String.prototype.trimURL = function(baseURLDomain)
129 {
130     var result = this.replace(/^(https|http|file):\/\//i, "");
131     if (baseURLDomain)
132         result = result.replace(new RegExp("^" + baseURLDomain.escapeForRegExp(), "i"), "");
133     return result;
134 }
135
136 String.prototype.removeURLFragment = function()
137 {
138     var fragmentIndex = this.indexOf("#");
139     if (fragmentIndex == -1)
140         fragmentIndex = this.length;
141     return this.substring(0, fragmentIndex);
142 }
143
144 String.prototype.startsWith = function(substring)
145 {
146     return !this.lastIndexOf(substring, 0);
147 }
148
149 String.prototype.endsWith = function(substring)
150 {
151     return this.indexOf(substring, this.length - substring.length) !== -1;
152 }
153
154 Number.constrain = function(num, min, max)
155 {
156     if (num < min)
157         num = min;
158     else if (num > max)
159         num = max;
160     return num;
161 }
162
163 Date.prototype.toISO8601Compact = function()
164 {
165     function leadZero(x)
166     {
167         return x > 9 ? '' + x : '0' + x
168     }
169     return this.getFullYear() +
170            leadZero(this.getMonth() + 1) +
171            leadZero(this.getDate()) + 'T' +
172            leadZero(this.getHours()) +
173            leadZero(this.getMinutes()) +
174            leadZero(this.getSeconds());
175 }
176
177 Object.defineProperty(Array.prototype, "remove",
178 {
179     /**
180      * @this {Array.<*>}
181      */
182     value: function(value, onlyFirst)
183     {
184         if (onlyFirst) {
185             var index = this.indexOf(value);
186             if (index !== -1)
187                 this.splice(index, 1);
188             return;
189         }
190
191         var length = this.length;
192         for (var i = 0; i < length; ++i) {
193             if (this[i] === value)
194                 this.splice(i, 1);
195         }
196     }
197 });
198
199 Object.defineProperty(Array.prototype, "keySet",
200 {
201     /**
202      * @this {Array.<*>}
203      */
204     value: function()
205     {
206         var keys = {};
207         for (var i = 0; i < this.length; ++i)
208             keys[this[i]] = true;
209         return keys;
210     }
211 });
212
213 Object.defineProperty(Array.prototype, "upperBound",
214 {
215     /**
216      * @this {Array.<number>}
217      */
218     value: function(value)
219     {
220         var first = 0;
221         var count = this.length;
222         while (count > 0) {
223           var step = count >> 1;
224           var middle = first + step;
225           if (value >= this[middle]) {
226               first = middle + 1;
227               count -= step + 1;
228           } else
229               count = step;
230         }
231         return first;
232     }
233 });
234
235 Object.defineProperty(Array.prototype, "rotate",
236 {
237     /**
238      * @this {Array.<*>}
239      * @param {number} index
240      * @return {Array.<*>}
241      */
242     value: function(index)
243     {
244         var result = [];
245         for (var i = index; i < index + this.length; ++i)
246             result.push(this[i % this.length]);
247         return result;
248     }
249 });
250
251 Object.defineProperty(Uint32Array.prototype, "sort", {
252    value: Array.prototype.sort
253 });
254
255 (function() {
256 var partition = {
257     /**
258      * @this {Array.<number>}
259      * @param {function(number,number):boolean} comparator
260      * @param {number} left
261      * @param {number} right
262      * @param {number} pivotIndex
263      */
264     value: function(comparator, left, right, pivotIndex)
265     {
266         function swap(array, i1, i2)
267         {
268             var temp = array[i1];
269             array[i1] = array[i2];
270             array[i2] = temp;
271         }
272
273         var pivotValue = this[pivotIndex];
274         swap(this, right, pivotIndex);
275         var storeIndex = left;
276         for (var i = left; i < right; ++i) {
277             if (comparator(this[i], pivotValue) < 0) {
278                 swap(this, storeIndex, i);
279                 ++storeIndex;
280             }
281         }
282         swap(this, right, storeIndex);
283         return storeIndex;
284     }
285 };
286 Object.defineProperty(Array.prototype, "partition", partition);
287 Object.defineProperty(Uint32Array.prototype, "partition", partition);
288
289 var sortRange = {
290     /**
291      * @this {Array.<number>}
292      * @param {function(number,number):boolean} comparator
293      * @param {number} leftBound
294      * @param {number} rightBound
295      * @param {number} k
296      */
297     value: function(comparator, leftBound, rightBound, k)
298     {
299         function quickSortFirstK(array, comparator, left, right, k)
300         {
301             if (right <= left)
302                 return;
303             var pivotIndex = Math.floor(Math.random() * (right - left)) + left;
304             var pivotNewIndex = array.partition(comparator, left, right, pivotIndex);
305             quickSortFirstK(array, comparator, left, pivotNewIndex - 1, k);
306             if (pivotNewIndex < left + k - 1)
307                 quickSortFirstK(array, comparator, pivotNewIndex + 1, right, k);
308         }
309
310         if (leftBound === 0 && rightBound === (this.length - 1) && k === this.length)
311             this.sort(comparator);
312         else
313             quickSortFirstK(this, comparator, leftBound, rightBound, k);
314         return this;
315     }
316 }
317 Object.defineProperty(Array.prototype, "sortRange", sortRange);
318 Object.defineProperty(Uint32Array.prototype, "sortRange", sortRange);
319 })();
320
321 Object.defineProperty(Array.prototype, "qselect",
322 {
323     /**
324      * @this {Array.<number>}
325      * @param {number} k
326      * @param {function(number,number):boolean=} comparator
327      */
328     value: function(k, comparator)
329     {
330         if (k < 0 || k >= this.length)
331             return;
332         if (!comparator)
333             comparator = function(a, b) { return a - b; }
334
335         var low = 0;
336         var high = this.length - 1;
337         for (;;) {
338             var pivotPosition = this.partition(comparator, low, high, Math.floor((high + low) / 2));
339             if (pivotPosition === k)
340                 return this[k];
341             else if (pivotPosition > k)
342                 high = pivotPosition - 1;
343             else
344                 low = pivotPosition + 1;
345         }
346     }
347 });
348
349 /**
350  * @param {*} object
351  * @param {Array.<*>} array
352  * @param {function(*, *):number} comparator
353  */
354 function binarySearch(object, array, comparator)
355 {
356     var first = 0;
357     var last = array.length - 1;
358
359     while (first <= last) {
360         var mid = (first + last) >> 1;
361         var c = comparator(object, array[mid]);
362         if (c > 0)
363             first = mid + 1;
364         else if (c < 0)
365             last = mid - 1;
366         else
367             return mid;
368     }
369
370     // Return the nearest lesser index, "-1" means "0, "-2" means "1", etc.
371     return -(first + 1);
372 }
373
374 Object.defineProperty(Array.prototype, "binaryIndexOf",
375 {
376     /**
377      * @this {Array.<*>}
378      * @param {function(*, *):number} comparator
379      */
380     value: function(value, comparator)
381     {
382         var result = binarySearch(value, this, comparator);
383         return result >= 0 ? result : -1;
384     }
385 });
386
387 Object.defineProperty(Array.prototype, "select",
388 {
389     /**
390      * @this {Array.<*>}
391      * @param {string} field
392      * @return {Array.<*>}
393      */
394     value: function(field)
395     {
396         var result = new Array(this.length);
397         for (var i = 0; i < this.length; ++i)
398             result[i] = this[i][field];
399         return result;
400     }
401 });
402
403 /**
404  * @param {*} anObject
405  * @param {Array.<*>} aList
406  * @param {function(*, *)} aFunction
407  */
408 function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction)
409 {
410     var index = binarySearch(anObject, aList, aFunction);
411     if (index < 0)
412         // See binarySearch implementation.
413         return -index - 1;
414     else {
415         // Return the first occurance of an item in the list.
416         while (index > 0 && aFunction(anObject, aList[index - 1]) === 0)
417             index--;
418         return index;
419     }
420 }
421
422 Array.convert = function(list)
423 {
424     // Cast array-like object to an array.
425     return Array.prototype.slice.call(list);
426 }
427
428 /**
429  * @param {string} format
430  * @param {...*} var_arg
431  */
432 String.sprintf = function(format, var_arg)
433 {
434     return String.vsprintf(format, Array.prototype.slice.call(arguments, 1));
435 }
436
437 String.tokenizeFormatString = function(format, formatters)
438 {
439     var tokens = [];
440     var substitutionIndex = 0;
441
442     function addStringToken(str)
443     {
444         tokens.push({ type: "string", value: str });
445     }
446
447     function addSpecifierToken(specifier, precision, substitutionIndex)
448     {
449         tokens.push({ type: "specifier", specifier: specifier, precision: precision, substitutionIndex: substitutionIndex });
450     }
451
452     function isDigit(c)
453     {
454         return !!/[0-9]/.exec(c);
455     }
456
457     var index = 0;
458     for (var precentIndex = format.indexOf("%", index); precentIndex !== -1; precentIndex = format.indexOf("%", index)) {
459         addStringToken(format.substring(index, precentIndex));
460         index = precentIndex + 1;
461
462         if (isDigit(format[index])) {
463             // The first character is a number, it might be a substitution index.
464             var number = parseInt(format.substring(index), 10);
465             while (isDigit(format[index]))
466                 ++index;
467
468             // If the number is greater than zero and ends with a "$",
469             // then this is a substitution index.
470             if (number > 0 && format[index] === "$") {
471                 substitutionIndex = (number - 1);
472                 ++index;
473             }
474         }
475
476         var precision = -1;
477         if (format[index] === ".") {
478             // This is a precision specifier. If no digit follows the ".",
479             // then the precision should be zero.
480             ++index;
481             precision = parseInt(format.substring(index), 10);
482             if (isNaN(precision))
483                 precision = 0;
484
485             while (isDigit(format[index]))
486                 ++index;
487         }
488
489         if (!(format[index] in formatters)) {
490             addStringToken(format.substring(precentIndex, index + 1));
491             ++index;
492             continue;
493         }
494
495         addSpecifierToken(format[index], precision, substitutionIndex);
496
497         ++substitutionIndex;
498         ++index;
499     }
500
501     addStringToken(format.substring(index));
502
503     return tokens;
504 }
505
506 String.standardFormatters = {
507     d: function(substitution)
508     {
509         return !isNaN(substitution) ? substitution : 0;
510     },
511
512     f: function(substitution, token)
513     {
514         if (substitution && token.precision > -1)
515             substitution = substitution.toFixed(token.precision);
516         return !isNaN(substitution) ? substitution : (token.precision > -1 ? Number(0).toFixed(token.precision) : 0);
517     },
518
519     s: function(substitution)
520     {
521         return substitution;
522     }
523 }
524
525 String.vsprintf = function(format, substitutions)
526 {
527     return String.format(format, substitutions, String.standardFormatters, "", function(a, b) { return a + b; }).formattedResult;
528 }
529
530 String.format = function(format, substitutions, formatters, initialValue, append)
531 {
532     if (!format || !substitutions || !substitutions.length)
533         return { formattedResult: append(initialValue, format), unusedSubstitutions: substitutions };
534
535     function prettyFunctionName()
536     {
537         return "String.format(\"" + format + "\", \"" + substitutions.join("\", \"") + "\")";
538     }
539
540     function warn(msg)
541     {
542         console.warn(prettyFunctionName() + ": " + msg);
543     }
544
545     function error(msg)
546     {
547         console.error(prettyFunctionName() + ": " + msg);
548     }
549
550     var result = initialValue;
551     var tokens = String.tokenizeFormatString(format, formatters);
552     var usedSubstitutionIndexes = {};
553
554     for (var i = 0; i < tokens.length; ++i) {
555         var token = tokens[i];
556
557         if (token.type === "string") {
558             result = append(result, token.value);
559             continue;
560         }
561
562         if (token.type !== "specifier") {
563             error("Unknown token type \"" + token.type + "\" found.");
564             continue;
565         }
566
567         if (token.substitutionIndex >= substitutions.length) {
568             // If there are not enough substitutions for the current substitutionIndex
569             // just output the format specifier literally and move on.
570             error("not enough substitution arguments. Had " + substitutions.length + " but needed " + (token.substitutionIndex + 1) + ", so substitution was skipped.");
571             result = append(result, "%" + (token.precision > -1 ? token.precision : "") + token.specifier);
572             continue;
573         }
574
575         usedSubstitutionIndexes[token.substitutionIndex] = true;
576
577         if (!(token.specifier in formatters)) {
578             // Encountered an unsupported format character, treat as a string.
579             warn("unsupported format character \u201C" + token.specifier + "\u201D. Treating as a string.");
580             result = append(result, substitutions[token.substitutionIndex]);
581             continue;
582         }
583
584         result = append(result, formatters[token.specifier](substitutions[token.substitutionIndex], token));
585     }
586
587     var unusedSubstitutions = [];
588     for (var i = 0; i < substitutions.length; ++i) {
589         if (i in usedSubstitutionIndexes)
590             continue;
591         unusedSubstitutions.push(substitutions[i]);
592     }
593
594     return { formattedResult: result, unusedSubstitutions: unusedSubstitutions };
595 }
596
597 /**
598  * @param {string} query
599  * @param {boolean} caseSensitive
600  * @param {boolean} isRegex
601  * @return {RegExp}
602  */
603 function createSearchRegex(query, caseSensitive, isRegex)
604 {
605     var regexFlags = caseSensitive ? "g" : "gi";
606     var regexObject;
607
608     if (isRegex) {
609         try {
610             regexObject = new RegExp(query, regexFlags);
611         } catch (e) {
612             // Silent catch.
613         }
614     }
615
616     if (!regexObject)
617         regexObject = createPlainTextSearchRegex(query, regexFlags);
618
619     return regexObject;
620 }
621
622 /**
623  * @param {string} query
624  * @param {string=} flags
625  * @return {RegExp}
626  */
627 function createPlainTextSearchRegex(query, flags)
628 {
629     // This should be kept the same as the one in ContentSearchUtils.cpp.
630     var regexSpecialCharacters = "[](){}+-*.,?\\^$|";
631     var regex = "";
632     for (var i = 0; i < query.length; ++i) {
633         var c = query.charAt(i);
634         if (regexSpecialCharacters.indexOf(c) != -1)
635             regex += "\\";
636         regex += c;
637     }
638     return new RegExp(regex, flags || "");
639 }
640
641 /**
642  * @param {RegExp} regex
643  * @param {string} content
644  * @return {number}
645  */
646 function countRegexMatches(regex, content)
647 {
648     var text = content;
649     var result = 0;
650     var match;
651     while (text && (match = regex.exec(text))) {
652         if (match[0].length > 0)
653             ++result;
654         text = text.substring(match.index + 1);
655     }
656     return result;
657 }
658
659 /**
660  * @param {number} value
661  * @param {number} symbolsCount
662  * @return {string}
663  */
664 function numberToStringWithSpacesPadding(value, symbolsCount)
665 {
666     var numberString = value.toString();
667     var paddingLength = Math.max(0, symbolsCount - numberString.length);
668     var paddingString = Array(paddingLength + 1).join("\u00a0");
669     return paddingString + numberString;
670 }
671
672 /**
673  * @constructor
674  */
675 var Map = function()
676 {
677     this._map = {};
678 }
679
680 Map._lastObjectIdentifier = 0;
681
682 Map.prototype = {
683     /**
684      * @param {Object} key
685      */
686     put: function(key, value)
687     {
688         var objectIdentifier = key.__identifier;
689         if (!objectIdentifier) {
690             objectIdentifier = ++Map._lastObjectIdentifier;
691             key.__identifier = objectIdentifier;
692         }
693         this._map[objectIdentifier] = value;
694     },
695     
696     /**
697      * @param {Object} key
698      * @return {Object} value
699      */
700     remove: function(key)
701     {
702         var result = this._map[key.__identifier];
703         delete this._map[key.__identifier];
704         return result;
705     },
706     
707     values: function()
708     {
709         var result = [];
710         for (var objectIdentifier in this._map)
711             result.push(this._map[objectIdentifier]);
712         return result;
713     },
714     
715     /**
716      * @param {Object} key
717      */
718     get: function(key)
719     {
720         return this._map[key.__identifier];
721     },
722     
723     clear: function()
724     {
725         this._map = {};
726     }
727 };
728
729
730 /**
731  * @constructor
732  */
733 function StringPool()
734 {
735     this.reset();
736 }
737
738 StringPool.prototype = {
739     /**
740      * @param {string} string
741      * @return {string}
742      */
743     intern: function(string)
744     {
745         // Do not mess with setting __proto__ to anything but null, just handle it explicitly.
746         if (string === "__proto__")
747             return "__proto__";
748         var result = this._strings[string];
749         if (result === undefined) {
750             this._strings[string] = string;
751             result = string;
752         }
753         return result;
754     },
755
756     reset: function()
757     {
758         this._strings = Object.create(null);
759     },
760
761     /**
762      * @param {Object} obj
763      * @param {number=} depthLimit
764      */
765     internObjectStrings: function(obj, depthLimit)
766     {
767         if (typeof depthLimit !== "number")
768             depthLimit = 100;
769         else if (--depthLimit < 0)
770             throw "recursion depth limit reached in StringPool.deepIntern(), perhaps attempting to traverse cyclical references?";
771
772         for (var field in obj) {
773             switch (typeof obj[field]) {
774             case "string":
775                 obj[field] = this.intern(obj[field]);
776                 break;
777             case "object":
778                 this.internObjectStrings(obj[field], depthLimit);
779                 break;
780             }
781         }
782     }
783 }
784
785 var _importedScripts = {};
786
787 /**
788  * @param {string} scriptName
789  */
790 function importScript(scriptName)
791 {
792     if (_importedScripts[scriptName])
793         return;
794     _importedScripts[scriptName] = true;
795     var xhr = new XMLHttpRequest();
796     xhr.open("GET", scriptName, false);
797     xhr.send(null);
798     window.eval(xhr.responseText + "\n//@ sourceURL=" + scriptName);
799 }