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