Add a bisect button to automatically schedule bisecting A/B tasks.
[WebKit-https.git] / Websites / perf.webkit.org / public / v3 / commit-set-range-bisector.js
1 'use strict';
2
3
4 class CommitSetRangeBisector {
5     static async commitSetClosestToMiddleOfAllCommits(commitSetsToSplit, availableCommitSets)
6     {
7         console.assert(commitSetsToSplit.length === 2);
8         const [firstCommitSet, secondCommitSet] = commitSetsToSplit;
9         if (firstCommitSet.containsRootOrPatchOrOwnedCommit() || secondCommitSet.containsRootOrPatchOrOwnedCommit())
10             return null;
11
12         if (!firstCommitSet.hasSameRepositories(secondCommitSet))
13             return null;
14
15         const repositoriesWithCommitTime = new Set;
16         const commitRangeByRepository = new Map;
17         const indexForAllTimelessCommitsWithOrderByRepository = new Map;
18         const allCommitsWithCommitTime = [];
19         const topLevelRepositoriesWithCommitChange = firstCommitSet.topLevelRepositories()
20             .filter((repository) => {
21                 const firstCommit = firstCommitSet.commitForRepository(repository);
22                 const secondCommit = secondCommitSet.commitForRepository(repository);
23                 return firstCommit !== secondCommit && CommitLog.hasOrdering(firstCommit, secondCommit);
24             });
25
26         await Promise.all(topLevelRepositoriesWithCommitChange.map(async (repository) => {
27             const firstCommit = firstCommitSet.commitForRepository(repository);
28             const secondCommit = secondCommitSet.commitForRepository(repository);
29             const [startCommit, endCommit] = CommitLog.orderTwoCommits(firstCommit, secondCommit);
30             const commits = await CommitLog.fetchBetweenRevisions(repository, startCommit.revision(), endCommit.revision());
31             if (startCommit.hasCommitTime()) {
32                 allCommitsWithCommitTime.push(startCommit, ...commits);
33                 commitRangeByRepository.set(repository, (commit) =>
34                     commit.hasCommitTime() && startCommit.time() <= commit.time() && commit.time() <= endCommit.time());
35                 repositoriesWithCommitTime.add(repository);
36             } else {
37                 const indexByCommit = new Map;
38                 indexByCommit.set(startCommit, 0);
39                 commits.forEach((commit, index) => indexByCommit.set(commit, index + 1));
40                 indexForAllTimelessCommitsWithOrderByRepository.set(repository, indexByCommit);
41                 commitRangeByRepository.set(repository, (commit) =>
42                     commit.hasCommitOrder() && startCommit.order() <= commit.order() && commit.order() <= endCommit.order());
43             }
44         }));
45
46         if (!repositoriesWithCommitTime.size && !indexForAllTimelessCommitsWithOrderByRepository.size)
47             return null;
48
49         const commitSetsInRange = this._findCommitSetsWithinRange(firstCommitSet, secondCommitSet, availableCommitSets, commitRangeByRepository);
50         let sortedCommitSets = this._orderCommitSetsByTimeAndOrderThenDeduplicate(commitSetsInRange, repositoriesWithCommitTime, [...indexForAllTimelessCommitsWithOrderByRepository.keys()]);
51         if (!sortedCommitSets.length)
52             return null;
53
54         let remainingCommitSets = this._closestCommitSetsToBisectingCommitByTime(sortedCommitSets, repositoriesWithCommitTime, allCommitsWithCommitTime);
55         remainingCommitSets = this._findCommitSetsClosestToMiddleOfCommitsWithOrder(remainingCommitSets, indexForAllTimelessCommitsWithOrderByRepository);
56
57         if (!remainingCommitSets.length)
58             return null;
59         return remainingCommitSets[Math.floor(remainingCommitSets.length / 2)];
60     }
61
62     static _findCommitSetsWithinRange(firstCommitSetSpecifiedInRange, secondCommitSetSpecifiedInRange, availableCommitSets, commitRangeByRepository)
63     {
64         return availableCommitSets.filter((commitSet) => {
65             if (!commitSet.hasSameRepositories(firstCommitSetSpecifiedInRange)
66                 || commitSet.equals(firstCommitSetSpecifiedInRange) || commitSet.equals(secondCommitSetSpecifiedInRange))
67                 return false;
68             for (const [repository, isCommitInRange] of commitRangeByRepository) {
69                 const commit = commitSet.commitForRepository(repository);
70                 if (!isCommitInRange(commit))
71                     return false;
72             }
73             return true;
74         });
75     }
76
77     static _orderCommitSetsByTimeAndOrderThenDeduplicate(commitSets, repositoriesWithCommitTime, repositoriesWithCommitOrderOnly)
78     {
79         const sortedCommitSets = commitSets.sort((firstCommitSet, secondCommitSet) => {
80             for (const repository of repositoriesWithCommitTime) {
81                 const firstCommit = firstCommitSet.commitForRepository(repository);
82                 const secondCommit = secondCommitSet.commitForRepository(repository);
83                 const diff = firstCommit.time() - secondCommit.time();
84                 if (!diff)
85                     continue;
86                 return diff;
87             }
88             for (const repository of repositoriesWithCommitOrderOnly) {
89                 const firstCommit = firstCommitSet.commitForRepository(repository);
90                 const secondCommit = secondCommitSet.commitForRepository(repository);
91                 const diff = firstCommit.order() - secondCommit.order();
92                 if (!diff)
93                     continue;
94                 return diff;
95             }
96             return 0;
97         });
98
99         return sortedCommitSets.filter((currentSet, i) => !i || !currentSet.equals(sortedCommitSets[i - 1]));
100     }
101
102     static _closestCommitSetsToBisectingCommitByTime(sortedCommitSets, repositoriesWithCommitTime, allCommitsWithCommitTime)
103     {
104         if (!repositoriesWithCommitTime.size)
105             return sortedCommitSets;
106
107         const indexByCommitWithTime = new Map;
108         allCommitsWithCommitTime.sort((firstCommit, secondCommit) => firstCommit.time() - secondCommit.time())
109             .forEach((commit, index) => indexByCommitWithTime.set(commit, index));
110
111         const commitToCommitSetMap = this._buildCommitToCommitSetMap(repositoriesWithCommitTime, sortedCommitSets);
112         const closestCommit = this._findCommitClosestToMiddleIndex(indexByCommitWithTime, commitToCommitSetMap.keys());
113         return Array.from(commitToCommitSetMap.get(closestCommit));
114     }
115
116     static _findCommitSetsClosestToMiddleOfCommitsWithOrder(remainingCommitSets, indexForAllTimelessCommitsWithOrderByRepository)
117     {
118         if (!indexForAllTimelessCommitsWithOrderByRepository.size)
119             return remainingCommitSets;
120
121         const commitWithOrderToCommitSets = this._buildCommitToCommitSetMap(indexForAllTimelessCommitsWithOrderByRepository.keys(), remainingCommitSets);
122
123         for (const [repository, indexByCommit] of indexForAllTimelessCommitsWithOrderByRepository) {
124             const commitsInRemainingSetsForCurrentRepository = remainingCommitSets.map((commitSet) => commitSet.commitForRepository(repository));
125             const closestCommit = this._findCommitClosestToMiddleIndex(indexByCommit, commitsInRemainingSetsForCurrentRepository);
126             const commitSetsContainingClosestCommit = commitWithOrderToCommitSets.get(closestCommit);
127             remainingCommitSets = remainingCommitSets.filter((commitSet) => commitSetsContainingClosestCommit.has(commitSet));
128             if (!remainingCommitSets.length)
129                 return remainingCommitSets;
130         }
131         return remainingCommitSets;
132     }
133
134     static _buildCommitToCommitSetMap(repositories, commitSets)
135     {
136         const commitToCommitSetMap = new Map;
137         for (const repository of repositories) {
138             for (const commitSet of commitSets) {
139                 const commit = commitSet.commitForRepository(repository);
140                 if (!commitToCommitSetMap.has(commit))
141                     commitToCommitSetMap.set(commit, new Set);
142                 commitToCommitSetMap.get(commit).add(commitSet);
143             }
144         }
145         return commitToCommitSetMap;
146     }
147
148     static _findCommitClosestToMiddleIndex(indexByCommit, commits)
149     {
150         const desiredCommitIndex = indexByCommit.size / 2;
151         let minCommitDistance = indexByCommit.size;
152         let closestCommit = null;
153         for (const commit of commits) {
154             const index = indexByCommit.get(commit);
155             const distanceForCommit = Math.abs(index - desiredCommitIndex);
156             if (distanceForCommit < minCommitDistance) {
157                 minCommitDistance = distanceForCommit;
158                 closestCommit = commit;
159             }
160         }
161         return closestCommit;
162     }
163 }
164
165 if (typeof module != 'undefined')
166     module.exports.CommitSetRangeBisector = CommitSetRangeBisector;