e520ebdafcf5a33ad64be85552f4127b9c7892b2
[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  * Contains diff method based on Javascript Diff Algorithm By John Resig
30  * http://ejohn.org/files/jsdiff.js (released under the MIT license).
31  */
32
33 String.prototype.hasSubstring = function(string, caseInsensitive)
34 {
35     if (!caseInsensitive)
36         return this.indexOf(string) !== -1;
37     return this.match(new RegExp(string.escapeForRegExp(), "i"));
38 }
39
40 String.prototype.findAll = function(string)
41 {
42     var matches = [];
43     var i = this.indexOf(string);
44     while (i !== -1) {
45         matches.push(i);
46         i = this.indexOf(string, i + string.length);
47     }
48     return matches;
49 }
50
51 String.prototype.lineEndings = function()
52 {
53     if (!this._lineEndings) {
54         this._lineEndings = this.findAll("\n");
55         this._lineEndings.push(this.length);
56     }
57     return this._lineEndings;
58 }
59
60 String.prototype.escapeCharacters = function(chars)
61 {
62     var foundChar = false;
63     for (var i = 0; i < chars.length; ++i) {
64         if (this.indexOf(chars.charAt(i)) !== -1) {
65             foundChar = true;
66             break;
67         }
68     }
69
70     if (!foundChar)
71         return this;
72
73     var result = "";
74     for (var i = 0; i < this.length; ++i) {
75         if (chars.indexOf(this.charAt(i)) !== -1)
76             result += "\\";
77         result += this.charAt(i);
78     }
79
80     return result;
81 }
82
83 String.prototype.escapeForRegExp = function()
84 {
85     return this.escapeCharacters("^[]{}()\\.$*+?|");
86 }
87
88 String.prototype.escapeHTML = function()
89 {
90     return this.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;").replace(/"/g, "&quot;"); //" doublequotes just for editor
91 }
92
93 String.prototype.collapseWhitespace = function()
94 {
95     return this.replace(/[\s\xA0]+/g, " ");
96 }
97
98 String.prototype.trimMiddle = function(maxLength)
99 {
100     if (this.length <= maxLength)
101         return this;
102     var leftHalf = maxLength >> 1;
103     var rightHalf = maxLength - leftHalf - 1;
104     return this.substr(0, leftHalf) + "\u2026" + this.substr(this.length - rightHalf, rightHalf);
105 }
106
107 String.prototype.trimEnd = function(maxLength)
108 {
109     if (this.length <= maxLength)
110         return this;
111     return this.substr(0, maxLength - 1) + "\u2026";
112 }
113
114 String.prototype.trimURL = function(baseURLDomain)
115 {
116     var result = this.replace(/^(https|http|file):\/\//i, "");
117     if (baseURLDomain)
118         result = result.replace(new RegExp("^" + baseURLDomain.escapeForRegExp(), "i"), "");
119     return result;
120 }
121
122 String.prototype.removeURLFragment = function()
123 {
124     var fragmentIndex = this.indexOf("#");
125     if (fragmentIndex == -1)
126         fragmentIndex = this.length;
127     return this.substring(0, fragmentIndex);
128 }
129
130 String.prototype.startsWith = function(substring)
131 {
132     return !this.lastIndexOf(substring, 0);
133 }
134
135 String.prototype.endsWith = function(substring)
136 {
137     return this.indexOf(substring, this.length - substring.length) !== -1;
138 }
139
140 Number.constrain = function(num, min, max)
141 {
142     if (num < min)
143         num = min;
144     else if (num > max)
145         num = max;
146     return num;
147 }
148
149 Date.prototype.toISO8601Compact = function()
150 {
151     function leadZero(x)
152     {
153         return x > 9 ? '' + x : '0' + x
154     }
155     return this.getFullYear() +
156            leadZero(this.getMonth() + 1) +
157            leadZero(this.getDate()) + 'T' +
158            leadZero(this.getHours()) +
159            leadZero(this.getMinutes()) +
160            leadZero(this.getSeconds());
161 }
162
163 Object.defineProperty(Array.prototype, "remove",
164 {
165     /**
166      * @this {Array.<*>}
167      */
168     value: function(value, onlyFirst)
169     {
170         if (onlyFirst) {
171             var index = this.indexOf(value);
172             if (index !== -1)
173                 this.splice(index, 1);
174             return;
175         }
176
177         var length = this.length;
178         for (var i = 0; i < length; ++i) {
179             if (this[i] === value)
180                 this.splice(i, 1);
181         }
182     }
183 });
184
185 Object.defineProperty(Array.prototype, "keySet",
186 {
187     /**
188      * @this {Array.<*>}
189      */
190     value: function()
191     {
192         var keys = {};
193         for (var i = 0; i < this.length; ++i)
194             keys[this[i]] = true;
195         return keys;
196     }
197 });
198
199 Object.defineProperty(Array.prototype, "upperBound",
200 {
201     /**
202      * @this {Array.<number>}
203      */
204     value: function(value)
205     {
206         var first = 0;
207         var count = this.length;
208         while (count > 0) {
209           var step = count >> 1;
210           var middle = first + step;
211           if (value >= this[middle]) {
212               first = middle + 1;
213               count -= step + 1;
214           } else
215               count = step;
216         }
217         return first;
218     }
219 });
220
221 Object.defineProperty(Uint32Array.prototype, "sort", {
222    value: Array.prototype.sort
223 });
224
225 (function() {
226 var partition = {
227     /**
228      * @this {Array.<number>}
229      * @param {function(number,number):boolean} comparator
230      * @param {number} left
231      * @param {number} right
232      * @param {number} pivotIndex
233      */
234     value: function(comparator, left, right, pivotIndex)
235     {
236         function swap(array, i1, i2)
237         {
238             var temp = array[i1];
239             array[i1] = array[i2];
240             array[i2] = temp;
241         }
242
243         var pivotValue = this[pivotIndex];
244         swap(this, right, pivotIndex);
245         var storeIndex = left;
246         for (var i = left; i < right; ++i) {
247             if (comparator(this[i], pivotValue) < 0) {
248                 swap(this, storeIndex, i);
249                 ++storeIndex;
250             }
251         }
252         swap(this, right, storeIndex);
253         return storeIndex;
254     }
255 };
256 Object.defineProperty(Array.prototype, "partition", partition);
257 Object.defineProperty(Uint32Array.prototype, "partition", partition);
258
259 var sortRange = {
260     /**
261      * @this {Array.<number>}
262      * @param {function(number,number):boolean} comparator
263      * @param {number} leftBound
264      * @param {number} rightBound
265      * @param {number} k
266      */
267     value: function(comparator, leftBound, rightBound, k)
268     {
269         function quickSortFirstK(array, comparator, left, right, k)
270         {
271             if (right <= left)
272                 return;
273             var pivotIndex = Math.floor(Math.random() * (right - left)) + left;
274             var pivotNewIndex = array.partition(comparator, left, right, pivotIndex);
275             quickSortFirstK(array, comparator, left, pivotNewIndex - 1, k);
276             if (pivotNewIndex < left + k - 1)
277                 quickSortFirstK(array, comparator, pivotNewIndex + 1, right, k);
278         }
279
280         if (leftBound === 0 && rightBound === (this.length - 1) && k === this.length)
281             this.sort(comparator);
282         else
283             quickSortFirstK(this, comparator, leftBound, rightBound, k);
284         return this;
285     }
286 }
287 Object.defineProperty(Array.prototype, "sortRange", sortRange);
288 Object.defineProperty(Uint32Array.prototype, "sortRange", sortRange);
289 })();
290
291 Object.defineProperty(Array.prototype, "qselect",
292 {
293     /**
294      * @this {Array.<number>}
295      * @param {number} k
296      * @param {function(number,number):boolean=} comparator
297      */
298     value: function(k, comparator)
299     {
300         if (k < 0 || k >= this.length)
301             return;
302         if (!comparator)
303             comparator = function(a, b) { return a - b; }
304
305         var low = 0;
306         var high = this.length - 1;
307         for (;;) {
308             var pivotPosition = this.partition(comparator, low, high, Math.floor((high + low) / 2));
309             if (pivotPosition === k)
310                 return this[k];
311             else if (pivotPosition > k)
312                 high = pivotPosition - 1;
313             else
314                 low = pivotPosition + 1;
315         }
316     }
317 });
318
319 /**
320  * @param {*} object
321  * @param {Array.<*>} array
322  * @param {function(*, *):number} comparator
323  */
324 function binarySearch(object, array, comparator)
325 {
326     var first = 0;
327     var last = array.length - 1;
328
329     while (first <= last) {
330         var mid = (first + last) >> 1;
331         var c = comparator(object, array[mid]);
332         if (c > 0)
333             first = mid + 1;
334         else if (c < 0)
335             last = mid - 1;
336         else
337             return mid;
338     }
339
340     // Return the nearest lesser index, "-1" means "0, "-2" means "1", etc.
341     return -(first + 1);
342 }
343
344 Object.defineProperty(Array.prototype, "binaryIndexOf",
345 {
346     /**
347      * @this {Array.<*>}
348      * @param {function(*, *):number} comparator
349      */
350     value: function(value, comparator)
351     {
352         var result = binarySearch(value, this, comparator);
353         return result >= 0 ? result : -1;
354     }
355 });
356
357 /**
358  * @param {*} anObject
359  * @param {Array.<*>} aList
360  * @param {function(*, *)} aFunction
361  */
362 function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunction)
363 {
364     var index = binarySearch(anObject, aList, aFunction);
365     if (index < 0)
366         // See binarySearch implementation.
367         return -index - 1;
368     else {
369         // Return the first occurance of an item in the list.
370         while (index > 0 && aFunction(anObject, aList[index - 1]) === 0)
371             index--;
372         return index;
373     }
374 }
375
376 Array.diff = function(left, right)
377 {
378     var o = left;
379     var n = right;
380
381     var ns = {};
382     var os = {};
383
384     for (var i = 0; i < n.length; i++) {
385         if (ns[n[i]] == null)
386             ns[n[i]] = { rows: [], o: null };
387         ns[n[i]].rows.push(i);
388     }
389
390     for (var i = 0; i < o.length; i++) {
391         if (os[o[i]] == null)
392             os[o[i]] = { rows: [], n: null };
393         os[o[i]].rows.push(i);
394     }
395
396     for (var i in ns) {
397         if (ns[i].rows.length == 1 && typeof(os[i]) != "undefined" && os[i].rows.length == 1) {
398             n[ns[i].rows[0]] = { text: n[ns[i].rows[0]], row: os[i].rows[0] };
399             o[os[i].rows[0]] = { text: o[os[i].rows[0]], row: ns[i].rows[0] };
400         }
401     }
402
403     for (var i = 0; i < n.length - 1; i++) {
404         if (n[i].text != null && n[i + 1].text == null && n[i].row + 1 < o.length && o[n[i].row + 1].text == null && n[i + 1] == o[n[i].row + 1]) {
405             n[i + 1] = { text: n[i + 1], row: n[i].row + 1 };
406             o[n[i].row + 1] = { text: o[n[i].row + 1], row: i + 1 };
407         }
408     }
409
410     for (var i = n.length - 1; i > 0; i--) {
411         if (n[i].text != null && n[i - 1].text == null && n[i].row > 0 && o[n[i].row - 1].text == null &&
412             n[i - 1] == o[n[i].row - 1]) {
413             n[i - 1] = { text: n[i - 1], row: n[i].row - 1 };
414             o[n[i].row - 1] = { text: o[n[i].row - 1], row: i - 1 };
415         }
416     }
417
418     return { left: o, right: n };
419 }
420
421 Array.convert = function(list)
422 {
423     // Cast array-like object to an array.
424     return Array.prototype.slice.call(list);
425 }
426
427 /**
428  * @param {string} format
429  * @param {...*} var_arg
430  */
431 String.sprintf = function(format, var_arg)
432 {
433     return String.vsprintf(format, Array.prototype.slice.call(arguments, 1));
434 }
435
436 String.tokenizeFormatString = function(format, formatters)
437 {
438     var tokens = [];
439     var substitutionIndex = 0;
440
441     function addStringToken(str)
442     {
443         tokens.push({ type: "string", value: str });
444     }
445
446     function addSpecifierToken(specifier, precision, substitutionIndex)
447     {
448         tokens.push({ type: "specifier", specifier: specifier, precision: precision, substitutionIndex: substitutionIndex });
449     }
450
451     function isDigit(c)
452     {
453         return !!/[0-9]/.exec(c);
454     }
455
456     var index = 0;
457     for (var precentIndex = format.indexOf("%", index); precentIndex !== -1; precentIndex = format.indexOf("%", index)) {
458         addStringToken(format.substring(index, precentIndex));
459         index = precentIndex + 1;
460
461         if (isDigit(format[index])) {
462             // The first character is a number, it might be a substitution index.
463             var number = parseInt(format.substring(index), 10);
464             while (isDigit(format[index]))
465                 ++index;
466
467             // If the number is greater than zero and ends with a "$",
468             // then this is a substitution index.
469             if (number > 0 && format[index] === "$") {
470                 substitutionIndex = (number - 1);
471                 ++index;
472             }
473         }
474
475         var precision = -1;
476         if (format[index] === ".") {
477             // This is a precision specifier. If no digit follows the ".",
478             // then the precision should be zero.
479             ++index;
480             precision = parseInt(format.substring(index), 10);
481             if (isNaN(precision))
482                 precision = 0;
483
484             while (isDigit(format[index]))
485                 ++index;
486         }
487
488         if (!(format[index] in formatters)) {
489             addStringToken(format.substring(precentIndex, index + 1));
490             ++index;
491             continue;
492         }
493
494         addSpecifierToken(format[index], precision, substitutionIndex);
495
496         ++substitutionIndex;
497         ++index;
498     }
499
500     addStringToken(format.substring(index));
501
502     return tokens;
503 }
504
505 String.standardFormatters = {
506     d: function(substitution)
507     {
508         return !isNaN(substitution) ? substitution : 0;
509     },
510
511     f: function(substitution, token)
512     {
513         if (substitution && token.precision > -1)
514             substitution = substitution.toFixed(token.precision);
515         return !isNaN(substitution) ? substitution : (token.precision > -1 ? Number(0).toFixed(token.precision) : 0);
516     },
517
518     s: function(substitution)
519     {
520         return substitution;
521     }
522 }
523
524 String.vsprintf = function(format, substitutions)
525 {
526     return String.format(format, substitutions, String.standardFormatters, "", function(a, b) { return a + b; }).formattedResult;
527 }
528
529 String.format = function(format, substitutions, formatters, initialValue, append)
530 {
531     if (!format || !substitutions || !substitutions.length)
532         return { formattedResult: append(initialValue, format), unusedSubstitutions: substitutions };
533
534     function prettyFunctionName()
535     {
536         return "String.format(\"" + format + "\", \"" + substitutions.join("\", \"") + "\")";
537     }
538
539     function warn(msg)
540     {
541         console.warn(prettyFunctionName() + ": " + msg);
542     }
543
544     function error(msg)
545     {
546         console.error(prettyFunctionName() + ": " + msg);
547     }
548
549     var result = initialValue;
550     var tokens = String.tokenizeFormatString(format, formatters);
551     var usedSubstitutionIndexes = {};
552
553     for (var i = 0; i < tokens.length; ++i) {
554         var token = tokens[i];
555
556         if (token.type === "string") {
557             result = append(result, token.value);
558             continue;
559         }
560
561         if (token.type !== "specifier") {
562             error("Unknown token type \"" + token.type + "\" found.");
563             continue;
564         }
565
566         if (token.substitutionIndex >= substitutions.length) {
567             // If there are not enough substitutions for the current substitutionIndex
568             // just output the format specifier literally and move on.
569             error("not enough substitution arguments. Had " + substitutions.length + " but needed " + (token.substitutionIndex + 1) + ", so substitution was skipped.");
570             result = append(result, "%" + (token.precision > -1 ? token.precision : "") + token.specifier);
571             continue;
572         }
573
574         usedSubstitutionIndexes[token.substitutionIndex] = true;
575
576         if (!(token.specifier in formatters)) {
577             // Encountered an unsupported format character, treat as a string.
578             warn("unsupported format character \u201C" + token.specifier + "\u201D. Treating as a string.");
579             result = append(result, substitutions[token.substitutionIndex]);
580             continue;
581         }
582
583         result = append(result, formatters[token.specifier](substitutions[token.substitutionIndex], token));
584     }
585
586     var unusedSubstitutions = [];
587     for (var i = 0; i < substitutions.length; ++i) {
588         if (i in usedSubstitutionIndexes)
589             continue;
590         unusedSubstitutions.push(substitutions[i]);
591     }
592
593     return { formattedResult: result, unusedSubstitutions: unusedSubstitutions };
594 }
595
596 /**
597  * @param {string} query
598  * @param {boolean} caseSensitive
599  * @param {boolean} isRegex
600  * @return {RegExp}
601  */
602 function createSearchRegex(query, caseSensitive, isRegex)
603 {
604     var regexFlags = caseSensitive ? "g" : "gi";
605     var regexObject;
606
607     if (isRegex) {
608         try {
609             regexObject = new RegExp(query, regexFlags);
610         } catch (e) {
611             // Silent catch.
612         }
613     }
614
615     if (!regexObject)
616         regexObject = createPlainTextSearchRegex(query, regexFlags);
617
618     return regexObject;
619 }
620
621 /**
622  * @param {string} query
623  * @param {string=} flags
624  * @return {RegExp}
625  */
626 function createPlainTextSearchRegex(query, flags)
627 {
628     // This should be kept the same as the one in ContentSearchUtils.cpp.
629     var regexSpecialCharacters = "[](){}+-*.,?\\^$|";
630     var regex = "";
631     for (var i = 0; i < query.length; ++i) {
632         var c = query.charAt(i);
633         if (regexSpecialCharacters.indexOf(c) != -1)
634             regex += "\\";
635         regex += c;
636     }
637     return new RegExp(regex, flags || "");
638 }
639
640 /**
641  * @param {RegExp} regex
642  * @param {string} content
643  * @return {number}
644  */
645 function countRegexMatches(regex, content)
646 {
647     var text = content;
648     var result = 0;
649     var match;
650     while (text && (match = regex.exec(text))) {
651         if (match[0].length > 0)
652             ++result;
653         text = text.substring(match.index + 1);
654     }
655     return result;
656 }
657
658 /**
659  * @param {number} value
660  * @param {number} symbolsCount
661  * @return {string}
662  */
663 function numberToStringWithSpacesPadding(value, symbolsCount)
664 {
665     var numberString = value.toString();
666     var paddingLength = Math.max(0, symbolsCount - numberString.length);
667     var paddingString = Array(paddingLength + 1).join("\u00a0");
668     return paddingString + numberString;
669 }
670
671 /**
672  * @constructor
673  */
674 function TextDiff()
675 {
676     this.added = [];
677     this.removed = [];
678     this.changed = [];
679
680
681 /**
682  * @param {string} baseContent
683  * @param {string} newContent
684  * @return {TextDiff}
685  */
686 TextDiff.compute = function(baseContent, newContent)
687 {
688     var oldLines = baseContent.split(/\r?\n/);
689     var newLines = newContent.split(/\r?\n/);
690
691     var diff = Array.diff(oldLines, newLines);
692
693     var diffData = new TextDiff();
694
695     var offset = 0;
696     var right = diff.right;
697     for (var i = 0; i < right.length; ++i) {
698         if (typeof right[i] === "string") {
699             if (right.length > i + 1 && right[i + 1].row === i + 1 - offset)
700                 diffData.changed.push(i);
701             else {
702                 diffData.added.push(i);
703                 offset++;
704             }
705         } else
706             offset = i - right[i].row;
707     }
708     return diffData;
709 }
710
711 /**
712  * @constructor
713  */
714 var Map = function()
715 {
716     this._map = {};
717 }
718
719 Map._lastObjectIdentifier = 0;
720
721 Map.prototype = {
722     /**
723      * @param {Object} key
724      */
725     put: function(key, value)
726     {
727         var objectIdentifier = key.__identifier;
728         if (!objectIdentifier) {
729             objectIdentifier = ++Map._lastObjectIdentifier;
730             key.__identifier = objectIdentifier;
731         }
732         this._map[objectIdentifier] = value;
733     },
734     
735     /**
736      * @param {Object} key
737      * @return {Object} value
738      */
739     remove: function(key)
740     {
741         var result = this._map[key.__identifier];
742         delete this._map[key.__identifier];
743         return result;
744     },
745     
746     values: function()
747     {
748         var result = [];
749         for (var objectIdentifier in this._map)
750             result.push(this._map[objectIdentifier]);
751         return result;
752     },
753     
754     /**
755      * @param {Object} key
756      */
757     get: function(key)
758     {
759         return this._map[key.__identifier];
760     },
761     
762     clear: function()
763     {
764         this._map = {};
765     }
766 }