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