CommitSet range bisector should use commits occur in commit sets which specify the...
[WebKit-https.git] / Websites / perf.webkit.org / unit-tests / commit-set-range-bisector-tests.js
1 'use strict';
2
3 const assert = require('assert');
4
5 require('../tools/js/v3-models.js');
6 const BrowserPrivilegedAPI = require('../public/v3/privileged-api.js').PrivilegedAPI;
7 const MockModels = require('./resources/mock-v3-models.js').MockModels;
8 const MockRemoteAPI = require('./resources/mock-remote-api.js').MockRemoteAPI;
9
10 describe('CommitSetRangeBisector', () => {
11
12     function makeCommit(id, repository, revision, time, order)
13     {
14         return CommitLog.ensureSingleton(id, {
15             repository,
16             revision,
17             ownsCommits: false,
18             time,
19             order
20         });
21     }
22
23     function sortedCommitSets()
24     {
25         return [
26             CommitSet.ensureSingleton(1, {
27                 revisionItems: [
28                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
29                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false }
30                 ],
31                 customRoots: []}),
32             CommitSet.ensureSingleton(2, {
33                 revisionItems: [
34                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
35                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false }
36                 ],
37                 customRoots: []}),
38             CommitSet.ensureSingleton(3, {
39                 revisionItems: [
40                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
41                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false }
42                 ],
43                 customRoots: []}),
44             CommitSet.ensureSingleton(4, {
45                 revisionItems: [
46                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
47                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false }
48                 ],
49                 customRoots: []}),
50             CommitSet.ensureSingleton(5, {
51                 revisionItems: [
52                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
53                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false }
54                 ],
55                 customRoots: []}),
56         ];
57     }
58
59     function sortedCommitSetsWithoutTimeOrOrder()
60     {
61         return [
62             CommitSet.ensureSingleton(6, {
63                 revisionItems: [
64                     { commit: makeCommit(101, MockModels.webkit, 'webkit-commit-101', 0), requiresBuild: false },
65                     { commit: makeCommit(111, MockModels.osx, 'osx-commit-111', 0), requiresBuild: false }
66                 ],
67                 customRoots: []}),
68             CommitSet.ensureSingleton(7, {
69                 revisionItems: [
70                     { commit: makeCommit(101, MockModels.webkit, 'webkit-commit-101', 0), requiresBuild: false },
71                     { commit: makeCommit(112, MockModels.osx, 'osx-commit-112', 0), requiresBuild: false }
72                 ],
73                 customRoots: []}),
74             CommitSet.ensureSingleton(8, {
75                 revisionItems: [
76                     { commit: makeCommit(102, MockModels.webkit, 'webkit-commit-102', 0), requiresBuild: false },
77                     { commit: makeCommit(112, MockModels.osx, 'osx-commit-112', 0), requiresBuild: false }
78                 ],
79                 customRoots: []}),
80             CommitSet.ensureSingleton(9, {
81                 revisionItems: [
82                     { commit: makeCommit(103, MockModels.webkit, 'webkit-commit-103', 0), requiresBuild: false },
83                     { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
84                 ],
85                 customRoots: []}),
86             CommitSet.ensureSingleton(10, {
87                 revisionItems: [
88                     { commit: makeCommit(106, MockModels.webkit, 'webkit-commit-106', 0), requiresBuild: false },
89                     { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
90                 ],
91                 customRoots: []}),
92         ];
93     }
94
95     function commitSetsWithSomeCommitsOnlyHaveOrder()
96     {
97         return [
98             CommitSet.ensureSingleton(11, {
99                 revisionItems: [
100                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
101                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false },
102                     { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false }
103                 ],
104                 customRoots: []}),
105             CommitSet.ensureSingleton(12, {
106                 revisionItems: [
107                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
108                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
109                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
110                 ],
111                 customRoots: []}),
112             CommitSet.ensureSingleton(13, {
113                 revisionItems: [
114                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
115                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
116                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
117                 ],
118                 customRoots: []}),
119             CommitSet.ensureSingleton(14, {
120                 revisionItems: [
121                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
122                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
123                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
124                 ],
125                 customRoots: []}),
126             CommitSet.ensureSingleton(15, {
127                 revisionItems: [
128                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
129                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
130                     { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
131                 ],
132                 customRoots: []}),
133             CommitSet.ensureSingleton(16, {
134                 revisionItems: [
135                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
136                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
137                     { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
138                 ],
139                 customRoots: []}),
140         ];
141     }
142
143     function commitSetsWitCommitRollback()
144     {
145         return [
146             CommitSet.ensureSingleton(11, {
147                 revisionItems: [
148                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
149                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false },
150                     { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false }
151                 ],
152                 customRoots: []}),
153             CommitSet.ensureSingleton(12, {
154                 revisionItems: [
155                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
156                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
157                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
158                 ],
159                 customRoots: []}),
160             CommitSet.ensureSingleton(13, {
161                 revisionItems: [
162                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
163                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
164                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
165                 ],
166                 customRoots: []}),
167             CommitSet.ensureSingleton(14, {
168                 revisionItems: [
169                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
170                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
171                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
172                 ],
173                 customRoots: []}),
174             CommitSet.ensureSingleton(15, {
175                 revisionItems: [
176                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
177                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
178                     { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
179                 ],
180                 customRoots: []}),
181             CommitSet.ensureSingleton(17, {
182                 revisionItems: [
183                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
184                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
185                     { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false }
186                 ],
187                 customRoots: []}),
188         ];
189     }
190
191     function commitSetsWithSomeHaveOwnedCommits()
192     {
193         return [
194             CommitSet.ensureSingleton(11, {
195                 revisionItems: [
196                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
197                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false },
198                     { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false },
199                 ],
200                 customRoots: []}),
201             CommitSet.ensureSingleton(12, {
202                 revisionItems: [
203                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
204                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
205                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
206                 ],
207                 customRoots: []}),
208             CommitSet.ensureSingleton(13, {
209                 revisionItems: [
210                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
211                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
212                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
213                 ],
214                 customRoots: []}),
215             CommitSet.ensureSingleton(14, {
216                 revisionItems: [
217                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
218                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
219                     { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false },
220                     { commit: makeCommit(302, MockModels.ownedRepository, 'owned-commit-2', 0, 2), requiresBuild: false }
221                 ],
222                 customRoots: []}),
223             CommitSet.ensureSingleton(15, {
224                 revisionItems: [
225                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
226                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
227                     { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
228                 ],
229                 customRoots: []}),
230             CommitSet.ensureSingleton(16, {
231                 revisionItems: [
232                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
233                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
234                     { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
235                 ],
236                 customRoots: []}),
237         ];
238     }
239
240     function commitSetsWithSomeCommitsNotMonotonicallyIncrease()
241     {
242         return [
243             CommitSet.ensureSingleton(17, {
244                 revisionItems: [
245                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
246                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 0, 2), requiresBuild: false }
247                 ],
248                 customRoots: []}),
249             CommitSet.ensureSingleton(18, {
250                 revisionItems: [
251                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
252                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
253                 ],
254                 customRoots: []}),
255             CommitSet.ensureSingleton(19, {
256                 revisionItems: [
257                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
258                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
259                 ],
260                 customRoots: []}),
261             CommitSet.ensureSingleton(20, {
262                 revisionItems: [
263                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
264                     { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 0, 2), requiresBuild: false }
265                 ],
266                 customRoots: []}),
267             CommitSet.ensureSingleton(21, {
268                 revisionItems: [
269                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
270                     { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 0, 3), requiresBuild: false }
271                 ],
272                 customRoots: []}),
273             CommitSet.ensureSingleton(22, {
274                 revisionItems: [
275                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
276                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
277                 ],
278                 customRoots: []}),
279         ];
280     }
281
282     function commitSetWithOnlySomeCommitsHaveOrdering()
283     {
284         return [
285             CommitSet.ensureSingleton(23, {
286                 revisionItems: [
287                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
288                     { commit: makeCommit(111, MockModels.osx, 'osx-commit-111', 0), requiresBuild: false }
289                 ],
290                 customRoots: []}),
291             CommitSet.ensureSingleton(24, {
292                 revisionItems: [
293                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
294                     { commit: makeCommit(112, MockModels.osx, 'osx-commit-112', 0), requiresBuild: false }
295                 ],
296                 customRoots: []}),
297             CommitSet.ensureSingleton(25, {
298                 revisionItems: [
299                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
300                     { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
301                 ],
302                 customRoots: []}),
303             CommitSet.ensureSingleton(26, {
304                 revisionItems: [
305                     { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
306                     { commit: makeCommit(114, MockModels.osx, 'osx-commit-114', 0), requiresBuild: false }
307                 ],
308                 customRoots: []}),
309             CommitSet.ensureSingleton(27, {
310                 revisionItems: [
311                     { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
312                     { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
313                 ],
314                 customRoots: []}),
315         ];
316     }
317
318     function createRoot()
319     {
320         return UploadedFile.ensureSingleton(456, {'createdAt': new Date('2017-05-01T21:03:27Z'), 'filename': 'root.dat', 'extension': '.dat', 'author': 'some user',
321             size: 16452234, sha256: '03eed7a8494ab8794c44b7d4308e55448fc56f4d6c175809ba968f78f656d58d'});
322     }
323
324     function commitSetWithRoot()
325     {
326         return CommitSet.ensureSingleton(15, {
327             revisionItems: [{ commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false }],
328             customRoots: [createRoot()]
329         });
330     }
331
332     function commitSet()
333     {
334         return CommitSet.ensureSingleton(16, {
335             revisionItems: [{ commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false }],
336             customRoots: []
337         });
338     }
339
340     function commitSetsWithNoCommonRepository() {
341         return [
342             CommitSet.ensureSingleton(1, {
343                 revisionItems: [
344                     { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false },
345                     { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false }
346                 ],
347                 customRoots: []}),
348             CommitSet.ensureSingleton(2, {
349                 revisionItems: [
350                     { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false },
351                     { commit: makeCommit(31, MockModels.ios, 'ios-commit-1', 1), requiresBuild: false },
352                 ],
353                 customRoots: []})
354         ];
355     }
356
357     describe('commitSetClosestToMiddleOfAllCommits', () => {
358         MockModels.inject();
359         const requests = MockRemoteAPI.inject(null, BrowserPrivilegedAPI);
360
361         it('should return "null" if no common repository found', async () => {
362             const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits(commitSetsWithNoCommonRepository().splice(0, 2));
363             assert.equal(middleCommitSet, null);
364         });
365
366         it('should return "null" to bisect commit set with root', async () => {
367             const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([commitSet(), commitSetWithRoot()], [commitSet(), commitSetWithRoot()]);
368             assert.equal(middleCommitSet, null);
369         });
370
371         it('should return "null" if no repository with time or order is found', async () => {
372             const allCommitSets = sortedCommitSetsWithoutTimeOrOrder();
373             const startCommitSet = allCommitSets[0];
374             const endCommitSet = allCommitSets[allCommitSets.length - 1];
375             const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
376             assert.equal(middleCommitSet, null);
377         });
378
379         it('should throw exception when failed to fetch commit log', async () => {
380             const allCommitSets = sortedCommitSets();
381             const startCommitSet = allCommitSets[0];
382             const endCommitSet = allCommitSets[allCommitSets.length - 1];
383             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
384             const rejectReason = '404';
385             requests[0].reject(rejectReason);
386             let exceptionRaised = false;
387             try {
388                 await promise;
389             } catch (error) {
390                 exceptionRaised = true;
391                 assert.equal(error, rejectReason);
392             }
393             assert.ok(exceptionRaised);
394         });
395
396         it('should return "null" if no commit set is found other than the commit sets that define the range', async () => {
397             const allCommitSets = sortedCommitSets();
398             const startCommitSet = allCommitSets[0];
399             const endCommitSet = allCommitSets[allCommitSets.length - 1];
400             const webkitId = MockModels.webkit.id();
401             const osxId = MockModels.osx.id();
402             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], [startCommitSet, endCommitSet]);
403             assert.equal(requests.length, 2);
404             assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
405             assert.equal(requests[1].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
406             requests[0].resolve({
407                 'commits': [
408                     {
409                         repository: osxId,
410                         id: 12,
411                         revision: 'osx-commit-2',
412                         ownsCommits: false,
413                         time: 21
414                     },
415                     {
416                         repository: osxId,
417                         id: 13,
418                         revision: 'osx-commit-3',
419                         ownsCommits: false,
420                         time: 31
421                     }
422                 ]
423             });
424             requests[1].resolve({
425                 'commits': [
426                     {
427                         repository: webkitId,
428                         id: 2,
429                         revision: 'webkit-commit-2',
430                         ownsCommits: false,
431                         time: 20
432                     },
433                     {
434                         repository: webkitId,
435                         id: 3,
436                         revision: 'webkit-commit-3',
437                         ownsCommits: false,
438                         time: 30
439                     },
440                     {
441                         repository: webkitId,
442                         id: 4,
443                         revision: 'webkit-commit-4',
444                         ownsCommits: false,
445                         time: 40
446                     },
447                     {
448                         repository: webkitId,
449                         id: 5,
450                         revision: 'webkit-commit-5',
451                         ownsCommits: false,
452                         time: 50
453                     },
454                     {
455                         repository: webkitId,
456                         id: 6,
457                         revision: 'webkit-commit-6',
458                         ownsCommits: false,
459                         time: 60
460                     },
461                 ]
462             });
463
464             assert.equal(await promise, null);
465         });
466
467         it('should return bisecting commit set point closest to the middle of revision range', async () => {
468             const allCommitSets = sortedCommitSets();
469             const startCommitSet = allCommitSets[0];
470             const endCommitSet = allCommitSets[allCommitSets.length - 1];
471             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
472             assert.equal(requests.length, 2);
473             const osxFetchRequest = requests.find((fetch_request) => fetch_request.url === '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
474             const webkitFetchRequest = requests.find((fetch_request) => fetch_request.url === '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
475             const webkitId = MockModels.webkit.id();
476             const osxId = MockModels.osx.id();
477             webkitFetchRequest.resolve({
478                 'commits': [
479                     {
480                         repository: webkitId,
481                         id: 2,
482                         revision: 'webkit-commit-2',
483                         ownsCommits: false,
484                         time: 20
485                     },
486                     {
487                         repository: webkitId,
488                         id: 3,
489                         revision: 'webkit-commit-3',
490                         ownsCommits: false,
491                         time: 30
492                     },
493                     {
494                         repository: webkitId,
495                         id: 4,
496                         revision: 'webkit-commit-4',
497                         ownsCommits: false,
498                         time: 40
499                     },
500                     {
501                         repository: webkitId,
502                         id: 5,
503                         revision: 'webkit-commit-5',
504                         ownsCommits: false,
505                         time: 50
506                     },
507                     {
508                         repository: webkitId,
509                         id: 6,
510                         revision: 'webkit-commit-6',
511                         ownsCommits: false,
512                         time: 60
513                     },
514                 ]
515             });
516             osxFetchRequest.resolve({
517                 'commits': [
518                     {
519                         repository: osxId,
520                         id: 12,
521                         revision: 'osx-commit-2',
522                         ownsCommits: false,
523                         time: 21
524                     },
525                     {
526                         repository: osxId,
527                         id: 13,
528                         revision: 'osx-commit-3',
529                         ownsCommits: false,
530                         time: 31
531                     }
532                 ]
533             });
534
535             assert.equal(await promise, allCommitSets[3]);
536         });
537
538         it('should return same bisection point even when two commit sets from original commit set have reverse order', async () => {
539             const allCommitSets = sortedCommitSets();
540             const startCommitSet = allCommitSets[0];
541             const endCommitSet = allCommitSets[allCommitSets.length - 1];
542             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([endCommitSet, startCommitSet], allCommitSets);
543             const webkitId = MockModels.webkit.id();
544             const osxId = MockModels.osx.id();
545             requests[0].resolve({
546                 'commits': [
547                     {
548                         repository: webkitId,
549                         id: 2,
550                         revision: 'webkit-commit-2',
551                         ownsCommits: false,
552                         time: 20
553                     },
554                     {
555                         repository: webkitId,
556                         id: 3,
557                         revision: 'webkit-commit-3',
558                         ownsCommits: false,
559                         time: 30
560                     },
561                     {
562                         repository: webkitId,
563                         id: 4,
564                         revision: 'webkit-commit-4',
565                         ownsCommits: false,
566                         time: 40
567                     },
568                     {
569                         repository: webkitId,
570                         id: 5,
571                         revision: 'webkit-commit-5',
572                         ownsCommits: false,
573                         time: 50
574                     },
575                     {
576                         repository: webkitId,
577                         id: 6,
578                         revision: 'webkit-commit-6',
579                         ownsCommits: false,
580                         time: 60
581                     },
582                 ]
583             });
584             requests[1].resolve({
585                 'commits': [
586                     {
587                         repository: osxId,
588                         id: 12,
589                         revision: 'osx-commit-2',
590                         ownsCommits: false,
591                         time: 21
592                     },
593                     {
594                         repository: osxId,
595                         id: 13,
596                         revision: 'osx-commit-3',
597                         ownsCommits: false,
598                         time: 31
599                     }
600                 ]
601             });
602
603             assert.equal(await promise, allCommitSets[3]);
604         });
605
606         it('should use commits with order as fallback when multiple commit sets found for the commit that is closest to the middle of commits with time', async () => {
607             const allCommitSets = commitSetsWithSomeCommitsOnlyHaveOrder();
608             const startCommitSet = allCommitSets[0];
609             const endCommitSet = allCommitSets[allCommitSets.length - 1];
610             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
611             const webkitId = MockModels.webkit.id();
612             const osxId = MockModels.osx.id();
613             const ownerRepositoryId = MockModels.ownerRepository.id();
614
615             assert.equal(requests.length, 3);
616             assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
617             assert.equal(requests[1].url, '/api/commits/111/?precedingRevision=owner-commit-1&lastRevision=owner-commit-3');
618             assert.equal(requests[2].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
619
620             requests[0].resolve({
621                 'commits': [
622                     {
623                         repository: osxId,
624                         id: 12,
625                         revision: 'osx-commit-2',
626                         ownsCommits: false,
627                         time: 21
628                     },
629                     {
630                         repository: osxId,
631                         id: 13,
632                         revision: 'osx-commit-3',
633                         ownsCommits: false,
634                         time: 31
635                     }
636                 ]
637             });
638
639             requests[1].resolve({
640                 'commits': [
641                     {
642                         repository: ownerRepositoryId,
643                         id: 202,
644                         revision: 'owner-commit-2',
645                         ownsCommits: false,
646                         time: 0,
647                         order: 2
648                     },
649                     {
650                         repository: ownerRepositoryId,
651                         id: 203,
652                         revision: 'owner-commit-3',
653                         ownsCommits: false,
654                         time: 0,
655                         order: 3
656                     }
657                 ]
658             });
659
660             requests[2].resolve({
661                 'commits': [
662                     {
663                         repository: webkitId,
664                         id: 2,
665                         revision: 'webkit-commit-2',
666                         ownsCommits: false,
667                         time: 20
668                     },
669                     {
670                         repository: webkitId,
671                         id: 3,
672                         revision: 'webkit-commit-3',
673                         ownsCommits: false,
674                         time: 30
675                     },
676                     {
677                         repository: webkitId,
678                         id: 4,
679                         revision: 'webkit-commit-4',
680                         ownsCommits: false,
681                         time: 40
682                     },
683                     {
684                         repository: webkitId,
685                         id: 5,
686                         revision: 'webkit-commit-5',
687                         ownsCommits: false,
688                         time: 50
689                     },
690                     {
691                         repository: webkitId,
692                         id: 6,
693                         revision: 'webkit-commit-6',
694                         ownsCommits: false,
695                         time: 60
696                     },
697                 ]
698             });
699             assert.equal(await promise, allCommitSets[3]);
700         });
701
702         it('should still check the repository revision even the repository has no change in the range', async () => {
703             const allCommitSets = commitSetsWitCommitRollback();
704             const startCommitSet = allCommitSets[0];
705             const endCommitSet = allCommitSets[allCommitSets.length - 1];
706             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
707             const webkitId = MockModels.webkit.id();
708             const osxId = MockModels.osx.id();
709
710             assert.equal(requests.length, 2);
711             assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
712             assert.equal(requests[1].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
713
714             requests[0].resolve({
715                 'commits': [
716                     {
717                         repository: osxId,
718                         id: 12,
719                         revision: 'osx-commit-2',
720                         ownsCommits: false,
721                         time: 21
722                     },
723                     {
724                         repository: osxId,
725                         id: 13,
726                         revision: 'osx-commit-3',
727                         ownsCommits: false,
728                         time: 31
729                     }
730                 ]
731             });
732
733             requests[1].resolve({
734                 'commits': [
735                     {
736                         repository: webkitId,
737                         id: 2,
738                         revision: 'webkit-commit-2',
739                         ownsCommits: false,
740                         time: 20
741                     },
742                     {
743                         repository: webkitId,
744                         id: 3,
745                         revision: 'webkit-commit-3',
746                         ownsCommits: false,
747                         time: 30
748                     },
749                     {
750                         repository: webkitId,
751                         id: 4,
752                         revision: 'webkit-commit-4',
753                         ownsCommits: false,
754                         time: 40
755                     },
756                     {
757                         repository: webkitId,
758                         id: 5,
759                         revision: 'webkit-commit-5',
760                         ownsCommits: false,
761                         time: 50
762                     },
763                     {
764                         repository: webkitId,
765                         id: 6,
766                         revision: 'webkit-commit-6',
767                         ownsCommits: false,
768                         time: 60
769                     },
770                 ]
771             });
772             assert.equal(await promise, null);
773         });
774
775         it('should filter out commit set with owned commit', async () => {
776             const allCommitSets = commitSetsWithSomeHaveOwnedCommits();
777             const startCommitSet = allCommitSets[0];
778             const endCommitSet = allCommitSets[allCommitSets.length - 1];
779             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
780             const webkitId = MockModels.webkit.id();
781             const osxId = MockModels.osx.id();
782             const ownerRepositoryId = MockModels.ownerRepository.id();
783
784             assert.equal(requests.length, 3);
785             assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
786             assert.equal(requests[1].url, '/api/commits/111/?precedingRevision=owner-commit-1&lastRevision=owner-commit-3');
787             assert.equal(requests[2].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
788
789             requests[0].resolve({
790                 'commits': [
791                     {
792                         repository: osxId,
793                         id: 12,
794                         revision: 'osx-commit-2',
795                         ownsCommits: false,
796                         time: 21
797                     },
798                     {
799                         repository: osxId,
800                         id: 13,
801                         revision: 'osx-commit-3',
802                         ownsCommits: false,
803                         time: 31
804                     }
805                 ]
806             });
807
808             requests[1].resolve({
809                 'commits': [
810                     {
811                         repository: ownerRepositoryId,
812                         id: 202,
813                         revision: 'owner-commit-2',
814                         ownsCommits: true,
815                         time: 0,
816                         order: 2
817                     },
818                     {
819                         repository: ownerRepositoryId,
820                         id: 203,
821                         revision: 'owner-commit-3',
822                         ownsCommits: true,
823                         time: 0,
824                         order: 3
825                     }
826                 ]
827             });
828
829             requests[2].resolve({
830                 'commits': [
831                     {
832                         repository: webkitId,
833                         id: 2,
834                         revision: 'webkit-commit-2',
835                         ownsCommits: false,
836                         time: 20
837                     },
838                     {
839                         repository: webkitId,
840                         id: 3,
841                         revision: 'webkit-commit-3',
842                         ownsCommits: false,
843                         time: 30
844                     },
845                     {
846                         repository: webkitId,
847                         id: 4,
848                         revision: 'webkit-commit-4',
849                         ownsCommits: false,
850                         time: 40
851                     },
852                     {
853                         repository: webkitId,
854                         id: 5,
855                         revision: 'webkit-commit-5',
856                         ownsCommits: false,
857                         time: 50
858                     },
859                     {
860                         repository: webkitId,
861                         id: 6,
862                         revision: 'webkit-commit-6',
863                         ownsCommits: false,
864                         time: 60
865                     },
866                 ]
867             });
868             assert.equal(await promise, allCommitSets[4]);
869         });
870
871         it('should filter out commits those are not in any commit sets for commit without ordering', async () => {
872             const allCommitSets = commitSetWithOnlySomeCommitsHaveOrdering();
873             const startCommitSet = allCommitSets[0];
874             const endCommitSet = allCommitSets[allCommitSets.length - 1];
875             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
876             const webkitId = MockModels.webkit.id();
877             const osxId = MockModels.osx.id();
878
879             assert.equal(requests.length, 1);
880             assert.equal(requests[0].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
881
882             requests[0].resolve({
883                 'commits': [
884                     {
885                         repository: webkitId,
886                         id: 2,
887                         revision: 'webkit-commit-2',
888                         ownsCommits: false,
889                         time: 20
890                     },
891                     {
892                         repository: webkitId,
893                         id: 3,
894                         revision: 'webkit-commit-3',
895                         ownsCommits: false,
896                         time: 30
897                     },
898                     {
899                         repository: webkitId,
900                         id: 4,
901                         revision: 'webkit-commit-4',
902                         ownsCommits: false,
903                         time: 40
904                     },
905                     {
906                         repository: webkitId,
907                         id: 5,
908                         revision: 'webkit-commit-5',
909                         ownsCommits: false,
910                         time: 50
911                     },
912                     {
913                         repository: webkitId,
914                         id: 6,
915                         revision: 'webkit-commit-6',
916                         ownsCommits: false,
917                         time: 60
918                     },
919                 ]
920             });
921             assert.equal(await promise, allCommitSets[2]);
922         });
923
924         it('should still work even some commits do not monotonically increasing', async () => {
925             const allCommitSets = commitSetsWithSomeCommitsNotMonotonicallyIncrease();
926             const startCommitSet = allCommitSets[0];
927             const endCommitSet = allCommitSets[allCommitSets.length - 1];
928             const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
929             const webkitId = MockModels.webkit.id();
930             const osxId = MockModels.osx.id();
931
932             assert.equal(requests.length, 2);
933             assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-2');
934             assert.equal(requests[1].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
935
936             requests[0].resolve({
937                 'commits': [
938                     {
939                         repository: osxId,
940                         id: 12,
941                         revision: 'osx-commit-2',
942                         ownsCommits: false,
943                         time: 0,
944                         order: 2
945                     }
946                 ]
947             });
948             requests[1].resolve({
949                 'commits': [
950                     {
951                         repository: webkitId,
952                         id: 2,
953                         revision: 'webkit-commit-2',
954                         ownsCommits: false,
955                         time: 20
956                     },
957                     {
958                         repository: webkitId,
959                         id: 3,
960                         revision: 'webkit-commit-3',
961                         ownsCommits: false,
962                         time: 30
963                     },
964                     {
965                         repository: webkitId,
966                         id: 4,
967                         revision: 'webkit-commit-4',
968                         ownsCommits: false,
969                         time: 40
970                     },
971                     {
972                         repository: webkitId,
973                         id: 5,
974                         revision: 'webkit-commit-5',
975                         ownsCommits: false,
976                         time: 50
977                     },
978                     {
979                         repository: webkitId,
980                         id: 6,
981                         revision: 'webkit-commit-6',
982                         ownsCommits: false,
983                         time: 60
984                     },
985                 ]
986             });
987
988             assert.equal(await promise, allCommitSets[3]);
989         });
990     });
991
992     describe('_orderCommitSetsByTimeAndOrderThenDeduplicate', () => {
993         it('should sort by alphabetically for commits without ordering', () => {
994             const oneCommitSet = CommitSet.ensureSingleton(100, {
995                 revisionItems: [
996                     { commit: makeCommit(1001, MockModels.webkit, 'webkit-commit-1001'), requiresBuild: false}
997                 ],
998                 customRoots: []
999             });
1000
1001             const anotherCommitSet = CommitSet.ensureSingleton(101, {
1002                 revisionItems: [
1003                     { commit: makeCommit(1002, MockModels.webkit, 'webkit-commit-1002'), requiresBuild: false}
1004                 ],
1005                 customRoots: []
1006             });
1007
1008             const [commitSet0, commitSet1] = CommitSetRangeBisector._orderCommitSetsByTimeAndOrderThenDeduplicate([anotherCommitSet, oneCommitSet], [], [], [MockModels.webkit]);
1009             assert.equal(oneCommitSet, commitSet0);
1010             assert.equal(anotherCommitSet, commitSet1);
1011         })
1012     })
1013 });