third_party/WebKit/LayoutTests/inspector/utilities.html

   1 <html>
   2 <head>
   3 <script src="../http/tests/inspector/inspector-test.js"></script>
   4 <script>
   5
   6 function test()
   7 {
   8     InspectorTest.runTestSuite([
   9         function remove(next)
  10         {
  11             var testArrays = [
  12                 [], [], [],
  13                 [1], [1], [1],
  14                 [1, 2, 3, 4, 5, 4, 3, 2, 1], [1, 3, 4, 5, 4, 3, 2, 1], [1, 3, 4, 5, 4, 3, 1],
  15                 [2, 2, 2, 2, 2], [2, 2, 2, 2], [],
  16                 [2, 2, 2, 1, 2, 2, 3, 2], [2, 2, 1, 2, 2, 3, 2], [1, 3]
  17             ];
  18             for (var i = 0; i < testArrays.length; i += 3) {
  19                 var actual = testArrays[i].slice(0);
  20                 var expected = testArrays[i + 1];
  21                 actual.remove(2, true);
  22                 InspectorTest.assertEquals(JSON.stringify(expected), JSON.stringify(actual), "remove(2, true) passed");
  23                 actual = testArrays[i].slice(0);
  24                 expected = testArrays[i + 2];
  25                 actual.remove(2, false);
  26                 InspectorTest.assertEquals(JSON.stringify(expected), JSON.stringify(actual), "remove(2, false) passed");
  27             }
  28             next();
  29         },
  30
  31         function orderedMergeIntersect(next)
  32         {
  33             function comparator(a, b)
  34             {
  35                 return a - b;
  36             }
  37             function count(a, x)
  38             {
  39                 return a.upperBound(x) - a.lowerBound(x);
  40             }
  41             function testAll(a, b)
  42             {
  43                 testOperation(a, b, a.mergeOrdered(b, comparator), Math.max, "U");
  44                 testOperation(a, b, a.intersectOrdered(b, comparator), Math.min, "x");
  45             }
  46             function testOperation(a, b, actual, checkOperation, opName)
  47             {
  48                 var allValues = a.concat(b).concat(actual);
  49                 for (var i = 0; i < allValues.length; ++i) {
  50                     var value = allValues[i];
  51                     expectedCount = checkOperation(count(a, value), count(b, value));
  52                     actualCount = count(actual, value);
  53                     InspectorTest.assertEquals(expectedCount, actualCount,
  54                         "Incorrect result for value: " + value + " at [" + a + "] " + opName + " [" + b + "] -> [" + actual + "]");
  55                 }
  56                 InspectorTest.assertEquals(JSON.stringify(actual.sort()), JSON.stringify(actual), "result array is ordered");
  57             }
  58             var testArrays = [
  59                 [], [],
  60                 [1], [],
  61                 [1, 2, 2, 2, 3], [],
  62                 [4, 5, 5, 8, 8], [1, 1, 1, 2, 6],
  63                 [1, 2, 2, 2, 2, 3, 3, 4], [2, 2, 2, 3, 3, 3, 3],
  64                 [1, 2, 3, 4, 5], [1, 2, 3]
  65             ];
  66             for (var i = 0; i < testArrays.length; i += 2) {
  67                 testAll(testArrays[i], testArrays[i + 1]);
  68                 testAll(testArrays[i + 1], testArrays[i]);
  69             }
  70             next();
  71         },
  72
  73         function binaryIndexOfTest(next)
  74         {
  75             var testArrays = [
  76                 [],
  77                 [1],
  78                 [1, 10],
  79                 [1, 10, 11, 12, 13, 14, 100],
  80                 [-100, -50, 0, 50, 100],
  81                 [-100, -14, -13, -12, -11, -10, -1]
  82             ];
  83
  84             function testArray(array)
  85             {
  86                 function comparator(a, b)
  87                 {
  88                     return a < b ? -1 : (a > b ? 1 : 0);
  89                 }
  90
  91                 for (var i = -100; i <= 100; ++i) {
  92                     var reference = array.indexOf(i);
  93                     var actual = array.binaryIndexOf(i, comparator);
  94                     InspectorTest.assertEquals(reference, actual, "binaryIndexOf");
  95                 }
  96                 return true;
  97             }
  98
  99             for (var i = 0, l = testArrays.length; i < l; ++i)
 100                 testArray(testArrays[i]);
 101             next();
 102         },
 103
 104         function lowerBoundTest(next)
 105         {
 106             var testArrays = [
 107                 [],
 108                 [1],
 109                 [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
 110             ];
 111
 112             function testArray(array, useComparator)
 113             {
 114                 function comparator(a, b)
 115                 {
 116                     return a < b ? -1 : (a > b ? 1 : 0);
 117                 }
 118
 119                 for (var value = -2; value <= 12; ++value) {
 120                     var index = useComparator ? array.lowerBound(value, comparator) : array.lowerBound(value);
 121                     InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
 122                     InspectorTest.assertTrue(index === 0 || array[index - 1] < value, "array[index - 1] < value");
 123                     InspectorTest.assertTrue(index === array.length || array[index] >= value, "array[index] >= value");
 124                 }
 125             }
 126
 127             for (var i = 0, l = testArrays.length; i < l; ++i) {
 128                 testArray(testArrays[i], false);
 129                 testArray(testArrays[i], true);
 130             }
 131             next();
 132         },
 133
 134         function upperBoundTest(next)
 135         {
 136             var testArrays = [
 137                 [],
 138                 [1],
 139                 [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]
 140             ];
 141
 142             function testArray(array, useComparator)
 143             {
 144                 function comparator(a, b)
 145                 {
 146                     return a < b ? -1 : (a > b ? 1 : 0);
 147                 }
 148
 149                 for (var value = -2; value <= 12; ++value) {
 150                     var index = useComparator ? array.upperBound(value, comparator) : array.upperBound(value);
 151                     InspectorTest.assertTrue(0 <= index && index <= array.length, "index is within bounds");
 152                     InspectorTest.assertTrue(index === 0 || array[index - 1] <= value, "array[index - 1] <= value");
 153                     InspectorTest.assertTrue(index === array.length || array[index] > value, "array[index] > value");
 154                 }
 155             }
 156
 157             for (var i = 0, l = testArrays.length; i < l; ++i) {
 158                 testArray(testArrays[i], false);
 159                 testArray(testArrays[i], true);
 160             }
 161             next();
 162         },
 163
 164         function qselectTest(next)
 165         {
 166             var testArrays = [
 167                 [],
 168                 [0],
 169                 [0, 0, 0, 0, 0, 0, 0, 0],
 170                 [4, 3, 2, 1],
 171                 [1, 2, 3, 4, 5],
 172                 [-1, 3, 2, 7, 7, 7, 10, 12, 3, 4, -1, 2]
 173             ];
 174
 175             function testArray(array)
 176             {
 177                 function compare(a, b)
 178                 {
 179                     return a - b;
 180                 }
 181                 var sorted = array.slice(0).sort(compare);
 182
 183                 var reference = {
 184                     min: sorted[0],
 185                     median: sorted[Math.floor(sorted.length / 2)],
 186                     max: sorted[sorted.length - 1]
 187                 }
 188
 189                 var actual = {
 190                     min: array.slice(0).qselect(0),
 191                     median: array.slice(0).qselect(Math.floor(array.length / 2)),
 192                     max: array.slice(0).qselect(array.length - 1)
 193                 }
 194                 InspectorTest.addResult("Array: " + JSON.stringify(array));
 195                 InspectorTest.addResult("Reference: " + JSON.stringify(reference));
 196                 InspectorTest.addResult("Actual:    " + JSON.stringify(actual));
 197             }
 198             for (var i = 0, l = testArrays.length; i < l; ++i)
 199                 testArray(testArrays[i]);
 200             next();
 201         },
 202
 203         function sortRangeTest(next)
 204         {
 205             var testArrays = [
 206                 [],
 207                 [1],
 208                 [2, 1],
 209                 [6, 4, 2, 7, 10, 15, 1],
 210                 [10, 44, 3, 6, 56, 66, 10, 55, 32, 56, 2, 5]
 211             ];
 212
 213             function testArray(array)
 214             {
 215                 function comparator(a, b)
 216                 {
 217                     return a < b ? -1 : (a > b ? 1 : 0);
 218                 }
 219
 220                 function compareArrays(a, b, message)
 221                 {
 222                     InspectorTest.assertEquals(JSON.stringify(a), JSON.stringify(b), message);
 223                 }
 224
 225                 for (var left = 0, l = array.length - 1; left < l; ++left) {
 226                     for (var right = left, r = array.length; right < r; ++right) {
 227                         for (var first = left; first <= right; ++first) {
 228                             for (var count = 1, k = right - first + 1; count <= k; ++count) {
 229                                 var actual = array.slice(0);
 230                                 actual.sortRange(comparator, left, right, first, first + count - 1);
 231                                 compareArrays(array.slice(0, left), actual.slice(0, left), "left " + left + " " + right + " " + count);
 232                                 compareArrays(array.slice(right + 1), actual.slice(right + 1), "right " + left + " " + right + " " + count);
 233                                 var middle = array.slice(left, right + 1);
 234                                 middle.sort(comparator);
 235                                 compareArrays(middle.slice(first - left, first - left + count), actual.slice(first, first + count), "sorted " + left + " " + right + " " + first + " " + count);
 236                                 actualRest = actual.slice(first + count, right + 1);
 237                                 actualRest.sort(comparator);
 238                                 compareArrays(middle.slice(first - left + count), actualRest, "unsorted " + left + " " + right + " " + first + " " + count);
 239                             }
 240                         }
 241                     }
 242                 }
 243             }
 244
 245             for (var i = 0, len = testArrays.length; i < len; ++i)
 246                 testArray(testArrays[i]);
 247             next();
 248         },
 249
 250         function naturalOrderComparatorTest(next)
 251         {
 252             var testArray = [
 253                 "dup",
 254                 "a1",
 255                 "a4222",
 256                 "a91",
 257                 "a07",
 258                 "dup",
 259                 "a7",
 260                 "a007",
 261                 "abc00",
 262                 "abc0",
 263                 "abc",
 264                 "abcd",
 265                 "abc000",
 266                 "x10y20z30",
 267                 "x9y19z29",
 268                 "dup",
 269                 "x09y19z29",
 270                 "x10y22z23",
 271                 "x10y19z43",
 272                 "1",
 273                 "10",
 274                 "11",
 275                 "dup",
 276                 "2", "2", "2",
 277                 "555555",
 278                 "5",
 279                 "5555",
 280                 "dup",
 281             ];
 282
 283             for (var i = 0, n = testArray.length; i < n; ++i)
 284                 InspectorTest.assertEquals(0, String.naturalOrderComparator(testArray[i], testArray[i]), "comparing equal strings");
 285
 286             testArray.sort(String.naturalOrderComparator);
 287             InspectorTest.addResult("Sorted in natural order: [" + testArray.join(", ") + "]");
 288
 289             // Check comparator's transitivity.
 290             for (var i = 0, n = testArray.length; i < n; ++i) {
 291                 for (var j = 0; j < n; ++j) {
 292                     var a = testArray[i];
 293                     var b = testArray[j];
 294                     var diff = String.naturalOrderComparator(a, b);
 295                     if (diff === 0)
 296                         InspectorTest.assertEquals(a, b, "zero diff");
 297                     else if (diff < 0)
 298                         InspectorTest.assertTrue(i < j);
 299                     else
 300                         InspectorTest.assertTrue(i > j);
 301                 }
 302             }
 303             next();
 304         },
 305
 306         function stableSortPrimitiveTest(next)
 307         {
 308             InspectorTest.assertEquals("", [].stableSort().join(","));
 309             InspectorTest.assertEquals("1", [1].stableSort().join(","));
 310             InspectorTest.assertEquals("1,2", [2,1].stableSort().join(","));
 311             InspectorTest.assertEquals("1,1,1", [1,1,1].stableSort().join(","));
 312             InspectorTest.assertEquals("1,2,3,4", [1,2,3,4].stableSort().join(","));
 313
 314             function defaultComparator(a, b)
 315             {
 316                 return a < b ? -1 : (a > b ? 1 : 0);
 317             }
 318
 319             function strictNumberCmp(a, b)
 320             {
 321                 if (a !== b)
 322                     return false;
 323                 if (a)
 324                     return true;
 325                 return 1/a === 1/b; // Neg zero comparison.
 326             }
 327
 328             // The following fails with standard Array.sort()
 329             var original = [0,-0,0,-0,-0,-0,0,0,0,-0,0,-0,-0,-0,0,0];
 330             var sorted = original.slice(0).stableSort(defaultComparator);
 331             for (var i = 0; i < original.length; ++i)
 332                 InspectorTest.assertTrue(strictNumberCmp(original[i], sorted[i]), "Sorting negative zeros");
 333
 334             // Test sorted and backward-sorted arrays.
 335             var identity = [];
 336             var reverse = [];
 337             for (var i = 0; i < 100; ++i) {
 338                 identity[i] = i;
 339                 reverse[i] = -i;
 340             }
 341             identity.stableSort(defaultComparator);
 342             reverse.stableSort(defaultComparator);
 343             for (var i = 1; i < identity.length; ++i) {
 344                 InspectorTest.assertTrue(identity[i - 1] < identity[i], "identity");
 345                 InspectorTest.assertTrue(reverse[i - 1] < reverse[i], "reverse");
 346             }
 347
 348             next();
 349         },
 350
 351         function stableSortTest(next)
 352         {
 353             function Pair(key1, key2)
 354             {
 355                 this.key1 = key1;
 356                 this.key2 = key2;
 357             }
 358             Pair.prototype.toString = function() {
 359                 return "Pair(" + this.key1 + ", " + this.key2 + ")";
 360             }
 361
 362             var testArray = [
 363                 new Pair(1, 1),
 364                 new Pair(3, 31),
 365                 new Pair(3, 30),
 366                 new Pair(5, 55),
 367                 new Pair(5, 54),
 368                 new Pair(5, 57),
 369                 new Pair(4, 47),
 370                 new Pair(4, 46),
 371                 new Pair(4, 45),
 372                 new Pair(5, 52),
 373                 new Pair(5, 59),
 374                 new Pair(3, 37),
 375                 new Pair(3, 38),
 376                 new Pair(5, -58),
 377                 new Pair(5, 58),
 378                 new Pair(4, 41),
 379                 new Pair(4, 42),
 380                 new Pair(4, 43),
 381                 new Pair(3, 33),
 382                 new Pair(3, 32),
 383                 new Pair(9, 9),
 384             ];
 385
 386             var testArrayKey2Values = [];
 387             for (var i = 0, n = testArray.length; i < n; ++i) {
 388                 var value = testArray[i].key2;
 389                 InspectorTest.assertTrue(testArrayKey2Values.indexOf(value) === -1, "FAIL: key2 values should be unique");
 390                 testArrayKey2Values.push(value);
 391             }
 392
 393             function comparator(a, b)
 394             {
 395                 return a.key1 - b.key1;
 396             }
 397             testArray.stableSort(comparator);
 398             InspectorTest.addResult("Stable sort result:\n" + testArray.join("\n"));
 399
 400             function assertHelper(condition, message, i, a, b)
 401             {
 402                 InspectorTest.assertTrue(condition, "FAIL: " + message + " at index " + i + ": " + a + " < " + b);
 403             }
 404
 405             for (var i = 1, n = testArray.length; i < n; ++i) {
 406                 var a = testArray[i - 1];
 407                 var b = testArray[i];
 408                 assertHelper(a.key1 <= b.key1, "primary key order", i, a, b);
 409                 if (a.key1 !== b.key1)
 410                     continue;
 411                 var key2IndexA = testArrayKey2Values.indexOf(a.key2);
 412                 InspectorTest.assertTrue(key2IndexA !== -1);
 413                 var key2IndexB = testArrayKey2Values.indexOf(b.key2);
 414                 InspectorTest.assertTrue(key2IndexB !== -1);
 415                 assertHelper(key2IndexA < key2IndexB, "stable order", i, a, b);
 416             }
 417             next();
 418         },
 419
 420         function stringHashTest(next)
 421         {
 422             var stringA = " ".repeat(10000);
 423             var stringB = stringA + " ";
 424             var hashA = String.hashCode(stringA);
 425             InspectorTest.assertTrue(hashA !== String.hashCode(stringB));
 426             InspectorTest.assertTrue(isFinite(hashA));
 427             InspectorTest.assertTrue(hashA + 1 !== hashA);
 428             next();
 429         },
 430
 431         function stringTrimURLTest(next)
 432         {
 433             var baseURLDomain = "www.chromium.org";
 434             var testArray = [
 435                 "http://www.chromium.org/foo/bar", "/foo/bar",
 436                 "https://www.CHromium.ORG/BAZ/zoo", "/BAZ/zoo",
 437                 "https://example.com/foo[]", "example.com/foo[]",
 438             ];
 439             for (var i = 0; i < testArray.length; i += 2) {
 440                 var url = testArray[i];
 441                 var expected = testArray[i + 1];
 442                 InspectorTest.assertEquals(expected, url.trimURL(baseURLDomain), url);
 443             }
 444             next();
 445         },
 446
 447         function stringToBase64Test(next)
 448         {
 449             var testArray = [
 450                 "", "",
 451                 "a", "YQ==",
 452                 "bc", "YmM=",
 453                 "def", "ZGVm",
 454                 "ghij", "Z2hpag==",
 455                 "klmno", "a2xtbm8=",
 456                 "pqrstu", "cHFyc3R1",
 457                 String.fromCharCode(0x444, 0x5555, 0x66666, 0x777777), "0YTllZXmmabnnbc="
 458             ];
 459             for (var i = 0; i < testArray.length; i += 2) {
 460                 var string = testArray[i];
 461                 var encodedString = testArray[i + 1];
 462                 InspectorTest.assertEquals(encodedString, string.toBase64());
 463             }
 464             next();
 465         }
 466     ]);
 467 }
 468
 469 </script>
 470 </head>
 471
 472 <body onload="runTest()">
 473 <p>
 474 This test checks Web Inspector utilities.
 475 </p>
 476
 477 </body>
 478 </html>