Add a bisect button to automatically schedule bisecting A/B tasks.
authordewei_zhu@apple.com <dewei_zhu@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Apr 2018 22:16:23 +0000 (22:16 +0000)
committerdewei_zhu@apple.com <dewei_zhu@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Apr 2018 22:16:23 +0000 (22:16 +0000)
https://bugs.webkit.org/show_bug.cgi?id=183888

Reviewed by Ryosuke Niwa.

Extended AnalysisTask's ability to figure out bisecting A/B tasks based on existing data points and test groups.
Updated analysis page UI to show bisect button which will only appear when the middle commit set of the range in
test group can be found.

Finding middle commit set algorithm is described as follows:
1. Find all commits from multiple repositories among the ranges specified by two commit sets in test group. In
the meanwhile, merge all commits that have commit time into a single list. For commits only have commit order,
put those commits into separate lists.
2. Filter all the available commit sets in current analysis task by keeping the ones have exact repositories
as the two commit sets in specified test group, and every commit of a commit set is in side the commit range.
After filtering the commit sets, sort the remaining ones and only keep one commit set if multiple commit sets
are equal to each other.
3. Among commits processed by step 2, find the commit sets that have the commit which is closest to the middle of
all commits that have commit time created from step 1.
4. Among commits processed by step 3, find the commit sets that have the commit which is closest to the middle of
commits that only have commit order and categorized by repository. We have to iterate through repository as commit
order is not granted to be comparable between different repositories.
5. If more than one commit sets are found, choose the middle commit set.

* public/v3/commit-set-range-bisector.js: Added.
(CommitSetRangeBisector.async.commitSetClosestToMiddleOfAllCommits): Instead of naively returning the middle of
existing commit set array, this function selects a bisect bisection points that is closest to actually middle of
the revision range based on all revisions reported to performance dashboard.
(CommitSetRangeBisector._findCommitSetsWithinRange): Helper function to find commit sets those are in specified range.
(CommitSetRangeBisector._orderCommitSetsByTimeAndOrderThenDeduplicate): Helper function to sort and deduplicate commit sets.
(CommitSetRangeBisector._closestCommitSetsToBisectingCommitByTime): Helper function to find the commit sets those
are closest to the middle of among all the commits in the range that have commit time.
(CommitSetRangeBisector._findCommitSetsClosestToMiddleOfCommitsWithOrder): Helper function which goes through all
repositories the commit of which has commit order, and find the commit sets those are closest to the middle of
commits for each repository.
(CommitSetRangeBisector._buildCommitToCommitSetMap): Helper function to builder mapping from a commit to commit
sets those contain this commit.
(CommitSetRangeBisector._findCommitClosestToMiddleIndex): Helper function to find closest commit to the middle of index.
(CommitSetRangeBisector):
* public/v3/index.html: Imports 'public/v3/commit-set-range-bisector.js'.
* public/v3/models/analysis-task.js:
(AnalysisTask.prototype.async.commitSetsFromTestGroupsAndMeasurementSet): Aggregates all existing commit sets in
test groups of current analysis tasks.
* public/v3/models/commit-log.js:
(CommitLog.prototype.hasCommitTime): A helper function determine whether a commit has a commit time. For commit
that does not have time, server will return commit time as zero. As it is unrealistic for a commit has commit time
0, it would be safe to assume a valid commit time is greater than 0.
(CommitLog.prototype.hasCommitOrder): Returns whether a commit has a commit oder.
(CommitLog.hasOrdering): Determine whether we can order two commits by commit time or commit order.
(CommitLog.orderTwoCommits): Order two commits incrementally.
* public/v3/models/commit-set.js:
(CommitSet.prototype.hasSameRepositories): A helper function to determine whether a commit set has same repositories
as current repository.
(CommitSet.containsRootOrPatchOrOwnedCommit): A helper function to determine whether current commit set has root,
patch or owned commit.
(CommitSet.commitForRepository): This function defined twice identically, remove one of them.
* public/v3/models/test-group.js: Make '_computeRequestedCommitSets' a static function as it does not use any
instance variables.
* public/v3/pages/analysis-task-page.js: Added bisect button.
(AnalysisTaskTestGroupPane):
(AnalysisTaskTestGroupPane.prototype.didConstructShadowTree):
(AnalysisTaskTestGroupPane.prototype.setTestGroups): Update 'setTestGroups' to update _bisectingCommitSetByTestGroup
when the test groups changes.
(AnalysisTaskTestGroupPane.prototype._renderCurrentTestGroup): Added code to conditionally show bisect button.
Bisect button will only show when there is a middle commit set for that test group.
(AnalysisTaskTestGroupPane.htmlTemplate):
(AnalysisTaskTestGroupPane.cssTemplate):
(AnalysisTaskPage.prototype.didConstructShadowTree):
(AnalysisTaskPage.prototype._retryCurrentTestGroup):
(AnalysisTaskPage.prototype.async._bisectCurrentTestGroup): A callback when bisect button is clicked.
* tools/js/v3-models.js:
* unit-tests/commit-log-tests.js: Added unit tests for 'CommitLog.hasCommitTime', 'CommitLog.hasCommitOrder',
'CommitLog.orderTwoCommits', 'CommitLog.hasOrdering'.
* unit-tests/commit-set-range-bisector-tests.js: Unit tests for 'CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits'.
* unit-tests/commit-set-tests.js: Added unit tests for 'CommitSet.hasSameRepositories' and 'CommitSet.containsRootOrPatchOrOwnedCommit'.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@230821 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
Websites/perf.webkit.org/ChangeLog
Websites/perf.webkit.org/public/v3/commit-set-range-bisector.js [new file with mode: 0644]
Websites/perf.webkit.org/public/v3/index.html
Websites/perf.webkit.org/public/v3/models/analysis-task.js
Websites/perf.webkit.org/public/v3/models/commit-log.js
Websites/perf.webkit.org/public/v3/models/commit-set.js
Websites/perf.webkit.org/public/v3/models/test-group.js
Websites/perf.webkit.org/public/v3/pages/analysis-task-page.js
Websites/perf.webkit.org/tools/js/v3-models.js
Websites/perf.webkit.org/unit-tests/commit-log-tests.js
Websites/perf.webkit.org/unit-tests/commit-set-range-bisector-tests.js [new file with mode: 0644]
Websites/perf.webkit.org/unit-tests/commit-set-tests.js

index de2bb9b..f3edcfb 100644 (file)
@@ -1,3 +1,81 @@
+2018-04-19  Dewei Zhu  <dewei_zhu@apple.com>
+
+        Add a bisect button to automatically schedule bisecting A/B tasks.
+        https://bugs.webkit.org/show_bug.cgi?id=183888
+
+        Reviewed by Ryosuke Niwa.
+
+        Extended AnalysisTask's ability to figure out bisecting A/B tasks based on existing data points and test groups.
+        Updated analysis page UI to show bisect button which will only appear when the middle commit set of the range in
+        test group can be found.
+
+        Finding middle commit set algorithm is described as follows:
+        1. Find all commits from multiple repositories among the ranges specified by two commit sets in test group. In
+        the meanwhile, merge all commits that have commit time into a single list. For commits only have commit order,
+        put those commits into separate lists.
+        2. Filter all the available commit sets in current analysis task by keeping the ones have exact repositories
+        as the two commit sets in specified test group, and every commit of a commit set is in side the commit range.
+        After filtering the commit sets, sort the remaining ones and only keep one commit set if multiple commit sets
+        are equal to each other.
+        3. Among commits processed by step 2, find the commit sets that have the commit which is closest to the middle of
+        all commits that have commit time created from step 1.
+        4. Among commits processed by step 3, find the commit sets that have the commit which is closest to the middle of
+        commits that only have commit order and categorized by repository. We have to iterate through repository as commit
+        order is not granted to be comparable between different repositories.
+        5. If more than one commit sets are found, choose the middle commit set.
+
+        * public/v3/commit-set-range-bisector.js: Added.
+        (CommitSetRangeBisector.async.commitSetClosestToMiddleOfAllCommits): Instead of naively returning the middle of
+        existing commit set array, this function selects a bisect bisection points that is closest to actually middle of
+        the revision range based on all revisions reported to performance dashboard.
+        (CommitSetRangeBisector._findCommitSetsWithinRange): Helper function to find commit sets those are in specified range.
+        (CommitSetRangeBisector._orderCommitSetsByTimeAndOrderThenDeduplicate): Helper function to sort and deduplicate commit sets.
+        (CommitSetRangeBisector._closestCommitSetsToBisectingCommitByTime): Helper function to find the commit sets those
+        are closest to the middle of among all the commits in the range that have commit time.
+        (CommitSetRangeBisector._findCommitSetsClosestToMiddleOfCommitsWithOrder): Helper function which goes through all
+        repositories the commit of which has commit order, and find the commit sets those are closest to the middle of
+        commits for each repository.
+        (CommitSetRangeBisector._buildCommitToCommitSetMap): Helper function to builder mapping from a commit to commit
+        sets those contain this commit.
+        (CommitSetRangeBisector._findCommitClosestToMiddleIndex): Helper function to find closest commit to the middle of index.
+        (CommitSetRangeBisector):
+        * public/v3/index.html: Imports 'public/v3/commit-set-range-bisector.js'.
+        * public/v3/models/analysis-task.js:
+        (AnalysisTask.prototype.async.commitSetsFromTestGroupsAndMeasurementSet): Aggregates all existing commit sets in
+        test groups of current analysis tasks.
+        * public/v3/models/commit-log.js:
+        (CommitLog.prototype.hasCommitTime): A helper function determine whether a commit has a commit time. For commit
+        that does not have time, server will return commit time as zero. As it is unrealistic for a commit has commit time
+        0, it would be safe to assume a valid commit time is greater than 0.
+        (CommitLog.prototype.hasCommitOrder): Returns whether a commit has a commit oder.
+        (CommitLog.hasOrdering): Determine whether we can order two commits by commit time or commit order.
+        (CommitLog.orderTwoCommits): Order two commits incrementally.
+        * public/v3/models/commit-set.js:
+        (CommitSet.prototype.hasSameRepositories): A helper function to determine whether a commit set has same repositories
+        as current repository.
+        (CommitSet.containsRootOrPatchOrOwnedCommit): A helper function to determine whether current commit set has root,
+        patch or owned commit.
+        (CommitSet.commitForRepository): This function defined twice identically, remove one of them.
+        * public/v3/models/test-group.js: Make '_computeRequestedCommitSets' a static function as it does not use any
+        instance variables.
+        * public/v3/pages/analysis-task-page.js: Added bisect button.
+        (AnalysisTaskTestGroupPane):
+        (AnalysisTaskTestGroupPane.prototype.didConstructShadowTree):
+        (AnalysisTaskTestGroupPane.prototype.setTestGroups): Update 'setTestGroups' to update _bisectingCommitSetByTestGroup
+        when the test groups changes.
+        (AnalysisTaskTestGroupPane.prototype._renderCurrentTestGroup): Added code to conditionally show bisect button.
+        Bisect button will only show when there is a middle commit set for that test group.
+        (AnalysisTaskTestGroupPane.htmlTemplate):
+        (AnalysisTaskTestGroupPane.cssTemplate):
+        (AnalysisTaskPage.prototype.didConstructShadowTree):
+        (AnalysisTaskPage.prototype._retryCurrentTestGroup):
+        (AnalysisTaskPage.prototype.async._bisectCurrentTestGroup): A callback when bisect button is clicked.
+        * tools/js/v3-models.js:
+        * unit-tests/commit-log-tests.js: Added unit tests for 'CommitLog.hasCommitTime', 'CommitLog.hasCommitOrder',
+        'CommitLog.orderTwoCommits', 'CommitLog.hasOrdering'.
+        * unit-tests/commit-set-range-bisector-tests.js: Unit tests for 'CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits'.
+        * unit-tests/commit-set-tests.js: Added unit tests for 'CommitSet.hasSameRepositories' and 'CommitSet.containsRootOrPatchOrOwnedCommit'.
+
 2018-04-16  Dewei Zhu  <dewei_zhu@apple.com>
 
         Commit order should always be returned by api.
diff --git a/Websites/perf.webkit.org/public/v3/commit-set-range-bisector.js b/Websites/perf.webkit.org/public/v3/commit-set-range-bisector.js
new file mode 100644 (file)
index 0000000..e478474
--- /dev/null
@@ -0,0 +1,166 @@
+'use strict';
+
+
+class CommitSetRangeBisector {
+    static async commitSetClosestToMiddleOfAllCommits(commitSetsToSplit, availableCommitSets)
+    {
+        console.assert(commitSetsToSplit.length === 2);
+        const [firstCommitSet, secondCommitSet] = commitSetsToSplit;
+        if (firstCommitSet.containsRootOrPatchOrOwnedCommit() || secondCommitSet.containsRootOrPatchOrOwnedCommit())
+            return null;
+
+        if (!firstCommitSet.hasSameRepositories(secondCommitSet))
+            return null;
+
+        const repositoriesWithCommitTime = new Set;
+        const commitRangeByRepository = new Map;
+        const indexForAllTimelessCommitsWithOrderByRepository = new Map;
+        const allCommitsWithCommitTime = [];
+        const topLevelRepositoriesWithCommitChange = firstCommitSet.topLevelRepositories()
+            .filter((repository) => {
+                const firstCommit = firstCommitSet.commitForRepository(repository);
+                const secondCommit = secondCommitSet.commitForRepository(repository);
+                return firstCommit !== secondCommit && CommitLog.hasOrdering(firstCommit, secondCommit);
+            });
+
+        await Promise.all(topLevelRepositoriesWithCommitChange.map(async (repository) => {
+            const firstCommit = firstCommitSet.commitForRepository(repository);
+            const secondCommit = secondCommitSet.commitForRepository(repository);
+            const [startCommit, endCommit] = CommitLog.orderTwoCommits(firstCommit, secondCommit);
+            const commits = await CommitLog.fetchBetweenRevisions(repository, startCommit.revision(), endCommit.revision());
+            if (startCommit.hasCommitTime()) {
+                allCommitsWithCommitTime.push(startCommit, ...commits);
+                commitRangeByRepository.set(repository, (commit) =>
+                    commit.hasCommitTime() && startCommit.time() <= commit.time() && commit.time() <= endCommit.time());
+                repositoriesWithCommitTime.add(repository);
+            } else {
+                const indexByCommit = new Map;
+                indexByCommit.set(startCommit, 0);
+                commits.forEach((commit, index) => indexByCommit.set(commit, index + 1));
+                indexForAllTimelessCommitsWithOrderByRepository.set(repository, indexByCommit);
+                commitRangeByRepository.set(repository, (commit) =>
+                    commit.hasCommitOrder() && startCommit.order() <= commit.order() && commit.order() <= endCommit.order());
+            }
+        }));
+
+        if (!repositoriesWithCommitTime.size && !indexForAllTimelessCommitsWithOrderByRepository.size)
+            return null;
+
+        const commitSetsInRange = this._findCommitSetsWithinRange(firstCommitSet, secondCommitSet, availableCommitSets, commitRangeByRepository);
+        let sortedCommitSets = this._orderCommitSetsByTimeAndOrderThenDeduplicate(commitSetsInRange, repositoriesWithCommitTime, [...indexForAllTimelessCommitsWithOrderByRepository.keys()]);
+        if (!sortedCommitSets.length)
+            return null;
+
+        let remainingCommitSets = this._closestCommitSetsToBisectingCommitByTime(sortedCommitSets, repositoriesWithCommitTime, allCommitsWithCommitTime);
+        remainingCommitSets = this._findCommitSetsClosestToMiddleOfCommitsWithOrder(remainingCommitSets, indexForAllTimelessCommitsWithOrderByRepository);
+
+        if (!remainingCommitSets.length)
+            return null;
+        return remainingCommitSets[Math.floor(remainingCommitSets.length / 2)];
+    }
+
+    static _findCommitSetsWithinRange(firstCommitSetSpecifiedInRange, secondCommitSetSpecifiedInRange, availableCommitSets, commitRangeByRepository)
+    {
+        return availableCommitSets.filter((commitSet) => {
+            if (!commitSet.hasSameRepositories(firstCommitSetSpecifiedInRange)
+                || commitSet.equals(firstCommitSetSpecifiedInRange) || commitSet.equals(secondCommitSetSpecifiedInRange))
+                return false;
+            for (const [repository, isCommitInRange] of commitRangeByRepository) {
+                const commit = commitSet.commitForRepository(repository);
+                if (!isCommitInRange(commit))
+                    return false;
+            }
+            return true;
+        });
+    }
+
+    static _orderCommitSetsByTimeAndOrderThenDeduplicate(commitSets, repositoriesWithCommitTime, repositoriesWithCommitOrderOnly)
+    {
+        const sortedCommitSets = commitSets.sort((firstCommitSet, secondCommitSet) => {
+            for (const repository of repositoriesWithCommitTime) {
+                const firstCommit = firstCommitSet.commitForRepository(repository);
+                const secondCommit = secondCommitSet.commitForRepository(repository);
+                const diff = firstCommit.time() - secondCommit.time();
+                if (!diff)
+                    continue;
+                return diff;
+            }
+            for (const repository of repositoriesWithCommitOrderOnly) {
+                const firstCommit = firstCommitSet.commitForRepository(repository);
+                const secondCommit = secondCommitSet.commitForRepository(repository);
+                const diff = firstCommit.order() - secondCommit.order();
+                if (!diff)
+                    continue;
+                return diff;
+            }
+            return 0;
+        });
+
+        return sortedCommitSets.filter((currentSet, i) => !i || !currentSet.equals(sortedCommitSets[i - 1]));
+    }
+
+    static _closestCommitSetsToBisectingCommitByTime(sortedCommitSets, repositoriesWithCommitTime, allCommitsWithCommitTime)
+    {
+        if (!repositoriesWithCommitTime.size)
+            return sortedCommitSets;
+
+        const indexByCommitWithTime = new Map;
+        allCommitsWithCommitTime.sort((firstCommit, secondCommit) => firstCommit.time() - secondCommit.time())
+            .forEach((commit, index) => indexByCommitWithTime.set(commit, index));
+
+        const commitToCommitSetMap = this._buildCommitToCommitSetMap(repositoriesWithCommitTime, sortedCommitSets);
+        const closestCommit = this._findCommitClosestToMiddleIndex(indexByCommitWithTime, commitToCommitSetMap.keys());
+        return Array.from(commitToCommitSetMap.get(closestCommit));
+    }
+
+    static _findCommitSetsClosestToMiddleOfCommitsWithOrder(remainingCommitSets, indexForAllTimelessCommitsWithOrderByRepository)
+    {
+        if (!indexForAllTimelessCommitsWithOrderByRepository.size)
+            return remainingCommitSets;
+
+        const commitWithOrderToCommitSets = this._buildCommitToCommitSetMap(indexForAllTimelessCommitsWithOrderByRepository.keys(), remainingCommitSets);
+
+        for (const [repository, indexByCommit] of indexForAllTimelessCommitsWithOrderByRepository) {
+            const commitsInRemainingSetsForCurrentRepository = remainingCommitSets.map((commitSet) => commitSet.commitForRepository(repository));
+            const closestCommit = this._findCommitClosestToMiddleIndex(indexByCommit, commitsInRemainingSetsForCurrentRepository);
+            const commitSetsContainingClosestCommit = commitWithOrderToCommitSets.get(closestCommit);
+            remainingCommitSets = remainingCommitSets.filter((commitSet) => commitSetsContainingClosestCommit.has(commitSet));
+            if (!remainingCommitSets.length)
+                return remainingCommitSets;
+        }
+        return remainingCommitSets;
+    }
+
+    static _buildCommitToCommitSetMap(repositories, commitSets)
+    {
+        const commitToCommitSetMap = new Map;
+        for (const repository of repositories) {
+            for (const commitSet of commitSets) {
+                const commit = commitSet.commitForRepository(repository);
+                if (!commitToCommitSetMap.has(commit))
+                    commitToCommitSetMap.set(commit, new Set);
+                commitToCommitSetMap.get(commit).add(commitSet);
+            }
+        }
+        return commitToCommitSetMap;
+    }
+
+    static _findCommitClosestToMiddleIndex(indexByCommit, commits)
+    {
+        const desiredCommitIndex = indexByCommit.size / 2;
+        let minCommitDistance = indexByCommit.size;
+        let closestCommit = null;
+        for (const commit of commits) {
+            const index = indexByCommit.get(commit);
+            const distanceForCommit = Math.abs(index - desiredCommitIndex);
+            if (distanceForCommit < minCommitDistance) {
+                minCommitDistance = distanceForCommit;
+                closestCommit = commit;
+            }
+        }
+        return closestCommit;
+    }
+}
+
+if (typeof module != 'undefined')
+    module.exports.CommitSetRangeBisector = CommitSetRangeBisector;
\ No newline at end of file
index 0233f96..9c0876a 100644 (file)
@@ -45,6 +45,7 @@ Run tools/bundle-v3-scripts to speed up the load time for production.`);
         <script src="privileged-api.js"></script>
         <script src="async-task.js"></script>
         <script src="lazily-evaluated-function.js"></script>
+        <script src="commit-set-range-bisector.js"></script>
 
         <script src="models/time-series.js"></script>
         <script src="models/measurement-adaptor.js"></script>
index 6e22285..0179be1 100644 (file)
@@ -167,6 +167,32 @@ class AnalysisTask extends LabeledObject {
         return category;
     }
 
+    async commitSetsFromTestGroupsAndMeasurementSet()
+    {
+
+        const platform = this.platform();
+        const metric = this.metric();
+        if (!platform || !metric)
+            return [];
+
+        const lastModified = platform.lastModified(metric);
+        const measurementSet = MeasurementSet.findSet(platform.id(), metric.id(), lastModified);
+        const fetchingMeasurementSetPromise = measurementSet.fetchBetween(this.startTime(), this.endTime());
+
+        const allTestGroupsInTask = await TestGroup.fetchForTask(this.id());
+        const allCommitSetsInTask = new Set;
+        for (const group of allTestGroupsInTask)
+            group.requestedCommitSets().forEach((commitSet) => allCommitSetsInTask.add(commitSet));
+
+        await fetchingMeasurementSetPromise;
+
+        const series = measurementSet.fetchedTimeSeries('current', false, false);
+        const startPoint = series.findById(this.startMeasurementId());
+        const endPoint = series.findById(this.endMeasurementId());
+
+        return Array.from(series.viewBetweenPoints(startPoint, endPoint)).map((point) => point.commitSet());
+    }
+
     static categories()
     {
         return [
index 39b3260..c2db63b 100644 (file)
@@ -35,6 +35,7 @@ class CommitLog extends DataModelObject {
 
     repository() { return this._repository; }
     time() { return new Date(this._rawData['time']); }
+    hasCommitTime() { return this._rawData['time'] > 0 && this._rawData['time'] != null; }
     author() { return this._rawData['authorName']; }
     revision() { return this._rawData['revision']; }
     message() { return this._rawData['message']; }
@@ -43,6 +44,7 @@ class CommitLog extends DataModelObject {
     ownedCommits() { return this._ownedCommits; }
     ownerCommit() { return this._ownerCommit; }
     order() { return this._rawData['order']; }
+    hasCommitOrder() { return this._rawData['order'] != null; }
     setOwnerCommits(ownerCommit) { this._ownerCommit = ownerCommit; }
 
     label()
@@ -92,6 +94,20 @@ class CommitLog extends DataModelObject {
         });
     }
 
+    static hasOrdering(firstCommit, secondCommit)
+    {
+        return (firstCommit.hasCommitTime() && secondCommit.hasCommitTime()) ||
+            (firstCommit.hasCommitOrder() && secondCommit.hasCommitOrder());
+    }
+
+    static orderTwoCommits(firstCommit, secondCommit)
+    {
+        console.assert(CommitLog.hasOrdering(firstCommit, secondCommit));
+        const firstCommitSmaller = firstCommit.hasCommitTime() && secondCommit.hasCommitTime() ?
+            firstCommit.time() < secondCommit.time() : firstCommit.order() < secondCommit.order();
+        return firstCommitSmaller ? [firstCommit, secondCommit] : [secondCommit, firstCommit];
+    }
+
     ownedCommitForOwnedRepository(ownedRepository) { return this._ownedCommitByOwnedRepository.get(ownedRepository); }
 
     fetchOwnedCommits()
index f179511..8112d56 100644 (file)
@@ -71,7 +71,6 @@ class CommitSet extends DataModelObject {
     ownerCommitForRepository(repository) { return this._repositoryToCommitOwnerMap.get(repository); }
     topLevelRepositories() { return Repository.sortByNamePreferringOnesWithURL(this._repositories.filter((repository) => !this.ownerRevisionForRepository(repository))); }
     ownedRepositoriesForOwnerRepository(repository) { return this._ownerRepositoryToOwnedRepositoriesMap.get(repository); }
-    commitForRepository(repository) { return this._repositoryToCommitMap.get(repository); }
 
     revisionForRepository(repository)
     {
@@ -120,6 +119,12 @@ class CommitSet extends DataModelObject {
         return CommitSet.areCustomRootsEqual(this._customRoots, other._customRoots);
     }
 
+    hasSameRepositories(commitSet)
+    {
+        return commitSet.repositories().length === this._repositoryToCommitMap.size
+            && commitSet.repositories().every((repository) => this._repositoryToCommitMap.has(repository));
+    }
+
     static areCustomRootsEqual(customRoots1, customRoots2)
     {
         if (customRoots1.length != customRoots2.length)
@@ -146,6 +151,22 @@ class CommitSet extends DataModelObject {
         return false;
     }
 
+    containsRootOrPatchOrOwnedCommit()
+    {
+        if (this.allRootFiles().length)
+            return true;
+
+        for (const repository of this.repositories()) {
+            if (this.ownerCommitForRepository(repository))
+                return true;
+            if (this.ownedRepositoriesForOwnerRepository(repository))
+                return true;
+            if (this.patchForRepository(repository))
+                return true;
+        }
+        return false;
+    }
+
     static createNameWithoutCollision(name, existingNameSet)
     {
         console.assert(existingNameSet instanceof Set);
index 2da6220..e821670 100644 (file)
@@ -14,7 +14,7 @@ class TestGroup extends LabeledObject {
             return buildRequests.sort((a, b) => a.order() - b.order());
         });
         this._repositories = null;
-        this._computeRequestedCommitSetsLazily = new LazilyEvaluatedFunction(this._computeRequestedCommitSets.bind(this));
+        this._computeRequestedCommitSetsLazily = new LazilyEvaluatedFunction(TestGroup._computeRequestedCommitSets);
         this._requestedCommitSets = null;
         this._commitSetToLabel = new Map;
         console.assert(!object.platform || object.platform instanceof Platform);
@@ -80,7 +80,7 @@ class TestGroup extends LabeledObject {
         return this._computeRequestedCommitSetsLazily.evaluate(...this._orderedBuildRequests());
     }
 
-    _computeRequestedCommitSets(...orderedBuildRequests)
+    static _computeRequestedCommitSets(...orderedBuildRequests)
     {
         const requestedCommitSets = [];
         const commitSetLabelMap = new Map;
index 02cfaa0..5aaf068 100644 (file)
@@ -258,8 +258,10 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
         this._renderCurrentTestGroupLazily = new LazilyEvaluatedFunction(this._renderCurrentTestGroup.bind(this));
         this._testGroupMap = new Map;
         this._testGroups = [];
+        this._bisectingCommitSetByTestGroup = null;
         this._currentTestGroup = null;
         this._showHiddenGroups = false;
+        this._allTestGroupIdSetForCurrentTask = null;
     }
 
     didConstructShadowTree()
@@ -268,6 +270,12 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
         this.part('retry-form').listenToAction('startTesting', (repetitionCount) => {
             this.dispatchAction('retryTestGroup', this._currentTestGroup, repetitionCount);
         });
+        this.part('bisect-form').listenToAction('startTesting', (repetitionCount) => {
+            const bisectingCommitSet = this._bisectingCommitSetByTestGroup.get(this._currentTestGroup);
+            const [oneCommitSet, anotherCommitSet] = this._currentTestGroup.requestedCommitSets();
+            const commitSets = [oneCommitSet, bisectingCommitSet, anotherCommitSet];
+            this.dispatchAction('bisectTestGroup', this._currentTestGroup, commitSets, repetitionCount);
+        });
     }
 
     setTestGroups(testGroups, currentTestGroup, showHiddenGroups)
@@ -277,7 +285,30 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
         this._showHiddenGroups = showHiddenGroups;
         this.part('revision-table').setTestGroup(currentTestGroup);
         this.part('results-viewer').setTestGroup(currentTestGroup);
-        this.enqueueToRender();
+
+        const analysisTask = currentTestGroup.task();
+        const allTestGroupIdsForCurrentTask = TestGroup.findAllByTask(analysisTask.id()).map((testGroup) => testGroup.id());
+        const testGroupChanged = !this._allTestGroupIdSetForCurrentTask
+            || this._allTestGroupIdSetForCurrentTask.size !== allTestGroupIdsForCurrentTask.length
+            || !allTestGroupIdsForCurrentTask.every((testGroupId) => this._allTestGroupIdSetForCurrentTask.has(testGroupId));
+
+        const computedForCurrentTestGroup = this._bisectingCommitSetByTestGroup && this._bisectingCommitSetByTestGroup.has(currentTestGroup);
+
+        if (!testGroupChanged && computedForCurrentTestGroup) {
+            this.enqueueToRender();
+            return;
+        }
+
+        if (testGroupChanged) {
+            this._bisectingCommitSetByTestGroup = new Map;
+            this._allTestGroupIdSetForCurrentTask = new Set(allTestGroupIdsForCurrentTask);
+        }
+
+        analysisTask.commitSetsFromTestGroupsAndMeasurementSet().then(async (availableCommitSets) => {
+            const commitSetClosestToMiddle = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits(currentTestGroup.requestedCommitSets(), availableCommitSets);
+            this._bisectingCommitSetByTestGroup.set(currentTestGroup, commitSetClosestToMiddle);
+            this.enqueueToRender();
+        });
     }
 
     setAnalysisResults(analysisResults, metric)
@@ -337,9 +368,12 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
         if (currentGroup)
             this._testGroupMap.get(currentGroup).listItem.classList.add('selected');
 
-        if (currentGroup)
+        if (currentGroup) {
             this.part('retry-form').setRepetitionCount(currentGroup.repetitionCount());
+            this.part('bisect-form').setRepetitionCount(currentGroup.repetitionCount());
+        }
         this.content('retry-form').style.display = currentGroup ? null : 'none';
+        this.content('bisect-form').style.display = currentGroup && this._bisectingCommitSetByTestGroup.get(currentGroup) ? null : 'none';
 
         const hideButton = this.content('hide-button');
         hideButton.textContent = currentGroup && currentGroup.isHidden() ? 'Unhide' : 'Hide';
@@ -356,6 +390,7 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
                 <test-group-results-viewer id="results-viewer"></test-group-results-viewer>
                 <test-group-revision-table id="revision-table"></test-group-revision-table>
                 <test-group-form id="retry-form">Retry</test-group-form>
+                <test-group-form id="bisect-form">Bisect</test-group-form>
                 <button id="hide-button">Hide</button>
                 <span id="pending-request-cancel-warning">(cancels pending requests)</span>
             </div>`;
@@ -423,7 +458,7 @@ class AnalysisTaskTestGroupPane extends ComponentBase {
                 margin: 0;
             }
 
-            #retry-form {
+            #retry-form, #bisect-form {
                 display: block;
                 margin: 0.5rem;
             }
@@ -509,6 +544,7 @@ class AnalysisTaskPage extends PageWithHeading {
         groupPane.listenToAction('renameTestGroup', (testGroup, newName) => this._updateTestGroupName(testGroup, newName));
         groupPane.listenToAction('toggleTestGroupVisibility', (testGroup) => this._hideCurrentTestGroup(testGroup));
         groupPane.listenToAction('retryTestGroup', (testGroup, repetitionCount) => this._retryCurrentTestGroup(testGroup, repetitionCount));
+        groupPane.listenToAction('bisectTestGroup', (testGroup, commitSets, repetitionCount) => this._bisectCurrentTestGroup(testGroup, commitSets, repetitionCount));
 
         this.part('cause-list').listenToAction('addItem', (repository, revision) => {
             this._associateCommit('cause', repository, revision);
@@ -793,7 +829,25 @@ class AnalysisTaskPage extends PageWithHeading {
             .then(this._didFetchTestGroups.bind(this), function (error) {
             alert('Failed to create a new test group: ' + error);
         });
-        return this._createTestGroupAfterVerifyingCommitSetList(newName, repetitionCount, commitSetMap);
+    }
+
+    async _bisectCurrentTestGroup(testGroup, commitSets, repetitionCount)
+    {
+        console.assert(testGroup.task());
+        const existingTestGroupNames = new Set((this._testGroups || []).map((testGroup) => testGroup.name()));
+
+        for (let i = 1; i < commitSets.length; i++) {
+            const previousCommitSet = commitSets[i - 1];
+            const currentCommitSet = commitSets[i];
+            const testGroupName = CommitSet.createNameWithoutCollision(CommitSet.diff(previousCommitSet, currentCommitSet), existingTestGroupNames);
+            try {
+                const testGroups = await TestGroup.createAndRefetchTestGroups(testGroup.task(), testGroupName, repetitionCount, [previousCommitSet, currentCommitSet]);
+                await this._didFetchTestGroups(testGroups);
+            } catch(error) {
+                alert('Failed to create a new test group: ' + error);
+                break;
+            }
+        }
     }
 
     _createTestGroupAfterVerifyingCommitSetList(testGroupName, repetitionCount, commitSetMap)
index d0efe7c..01d23e2 100644 (file)
@@ -37,5 +37,6 @@ importFromV3('models/uploaded-file.js', 'UploadedFile');
 importFromV3('privileged-api.js', 'PrivilegedAPI');
 importFromV3('instrumentation.js', 'Instrumentation');
 importFromV3('lazily-evaluated-function.js', 'LazilyEvaluatedFunction');
+importFromV3('commit-set-range-bisector.js', 'CommitSetRangeBisector');
 
-global.Statistics = require('../../public/shared/statistics.js');
+global.Statistics = require('../../public/shared/statistics.js');
\ No newline at end of file
index 849b036..cc2dbbf 100644 (file)
@@ -95,6 +95,26 @@ function otherOwnerCommit()
     });
 }
 
+function ownedCommit()
+{
+    return new CommitLog(11, {
+        repository: MockModels.ownedRepository,
+        revision: 'owned-commit-0',
+        ownsCommits: true,
+        time: null
+    });
+}
+
+function anotherOwnedCommit()
+{
+    return new CommitLog(11, {
+        repository: MockModels.ownedRepository,
+        revision: 'owned-commit-1',
+        ownsCommits: true,
+        time: null
+    });
+}
+
 describe('CommitLog', function () {
     MockModels.inject();
 
@@ -181,6 +201,60 @@ describe('CommitLog', function () {
         });
     });
 
+    describe('hasOrdering', () => {
+        it('should return "true" when both commits have commit orders', () => {
+            assert.ok(CommitLog.hasOrdering(osxCommit(), oldOSXCommit()));
+        });
+
+        it('should return "true" when both commits have commit time', () => {
+            assert.ok(CommitLog.hasOrdering(webkitCommit(), oldWebKitCommit()));
+        });
+
+        it('should return "false" when neither commit time nor commit order exists', () => {
+            assert.ok(!CommitLog.hasOrdering(ownedCommit(), anotherOwnedCommit()));
+        });
+
+        it('should return "false" when one commit only has commit time and another only has commit order', () => {
+            assert.ok(!CommitLog.hasOrdering(webkitCommit(), osxCommit()));
+        });
+    });
+
+    describe('hasCommitOrder', () => {
+        it('should return "true" when a commit has commit order', () => {
+            assert.ok(osxCommit().hasCommitOrder());
+        });
+
+        it('should return "false" when a commit only has commit time', () => {
+            assert.ok(!webkitCommit().hasCommitOrder());
+        });
+    });
+
+    describe('hasCommitTime', () => {
+        it('should return "true" when a commit has commit order', () => {
+            assert.ok(!osxCommit().hasCommitTime());
+        });
+
+        it('should return "false" when a commit only has commit time', () => {
+            assert.ok(webkitCommit().hasCommitTime());
+        });
+    });
+
+    describe('orderTowCommits', () => {
+        it('should order by time when both commits have time', () => {
+            const startCommit = oldWebKitCommit();
+            const endCommit = webkitCommit();
+            assert.deepEqual(CommitLog.orderTwoCommits(endCommit, startCommit), [startCommit, endCommit]);
+            assert.deepEqual(CommitLog.orderTwoCommits(startCommit, endCommit), [startCommit, endCommit]);
+        });
+
+        it('should order by commit order when both commits only have commit order', () => {
+            const startCommit = oldOSXCommit();
+            const endCommit = osxCommit();
+            assert.deepEqual(CommitLog.orderTwoCommits(endCommit, startCommit), [startCommit, endCommit]);
+            assert.deepEqual(CommitLog.orderTwoCommits(startCommit, endCommit), [startCommit, endCommit]);
+        });
+    });
+
     describe('fetchOwnedCommits', () => {
         beforeEach(() => {
             MockRemoteAPI.inject();
diff --git a/Websites/perf.webkit.org/unit-tests/commit-set-range-bisector-tests.js b/Websites/perf.webkit.org/unit-tests/commit-set-range-bisector-tests.js
new file mode 100644 (file)
index 0000000..f10cc1c
--- /dev/null
@@ -0,0 +1,780 @@
+'use strict';
+
+const assert = require('assert');
+
+require('../tools/js/v3-models.js');
+const MockModels = require('./resources/mock-v3-models.js').MockModels;
+const MockRemoteAPI = require('./resources/mock-remote-api.js').MockRemoteAPI;
+
+describe('CommitSetRangeBisector', () => {
+
+    function makeCommit(id, repository, revision, time, order)
+    {
+        return CommitLog.ensureSingleton(id, {
+            repository,
+            revision,
+            ownsCommits: false,
+            time,
+            order
+        });
+    }
+
+    function sortedCommitSets()
+    {
+        return [
+            CommitSet.ensureSingleton(1, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(2, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(3, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(4, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(5, {
+                revisionItems: [
+                    { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false }
+                ],
+                customRoots: []}),
+        ];
+    }
+
+    function sortedCommitSetsWithoutTimeOrOrder()
+    {
+        return [
+            CommitSet.ensureSingleton(6, {
+                revisionItems: [
+                    { commit: makeCommit(101, MockModels.webkit, 'webkit-commit-101', 0), requiresBuild: false },
+                    { commit: makeCommit(111, MockModels.osx, 'osx-commit-111', 0), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(7, {
+                revisionItems: [
+                    { commit: makeCommit(101, MockModels.webkit, 'webkit-commit-101', 0), requiresBuild: false },
+                    { commit: makeCommit(112, MockModels.osx, 'osx-commit-112', 0), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(8, {
+                revisionItems: [
+                    { commit: makeCommit(102, MockModels.webkit, 'webkit-commit-102', 0), requiresBuild: false },
+                    { commit: makeCommit(112, MockModels.osx, 'osx-commit-112', 0), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(9, {
+                revisionItems: [
+                    { commit: makeCommit(103, MockModels.webkit, 'webkit-commit-103', 0), requiresBuild: false },
+                    { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(10, {
+                revisionItems: [
+                    { commit: makeCommit(106, MockModels.webkit, 'webkit-commit-106', 0), requiresBuild: false },
+                    { commit: makeCommit(113, MockModels.osx, 'osx-commit-113', 0), requiresBuild: false }
+                ],
+                customRoots: []}),
+        ];
+    }
+
+    function commitSetsWithSomeCommitsOnlyHaveOrder()
+    {
+        return [
+            CommitSet.ensureSingleton(11, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false },
+                    { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(12, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(13, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(14, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(15, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(16, {
+                revisionItems: [
+                    { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
+                ],
+                customRoots: []}),
+        ];
+    }
+
+    function commitSetsWithSomeHaveOwnedCommits()
+    {
+        return [
+            CommitSet.ensureSingleton(11, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false },
+                    { commit: makeCommit(201, MockModels.ownerRepository, 'owner-commit-1', 0, 1), requiresBuild: false },
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(12, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(13, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 21), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(14, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(202, MockModels.ownerRepository, 'owner-commit-2', 0, 2), requiresBuild: false },
+                    { commit: makeCommit(302, MockModels.ownedRepository, 'owned-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(15, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(16, {
+                revisionItems: [
+                    { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 31), requiresBuild: false },
+                    { commit: makeCommit(203, MockModels.ownerRepository, 'owner-commit-3', 0, 3), requiresBuild: false }
+                ],
+                customRoots: []}),
+        ];
+    }
+
+    function commitSetsWithSomeCommitsNotMonotonicallyIncrease()
+    {
+        return [
+            CommitSet.ensureSingleton(17, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(18, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 10), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(19, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(20, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-2', 20), requiresBuild: false },
+                    { commit: makeCommit(12, MockModels.osx, 'osx-commit-2', 0, 2), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(21, {
+                revisionItems: [
+                    { commit: makeCommit(3, MockModels.webkit, 'webkit-commit-3', 30), requiresBuild: false },
+                    { commit: makeCommit(13, MockModels.osx, 'osx-commit-3', 0, 3), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(22, {
+                revisionItems: [
+                    { commit: makeCommit(6, MockModels.webkit, 'webkit-commit-6', 60), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 0, 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+        ];
+    }
+
+    function createRoot()
+    {
+        return UploadedFile.ensureSingleton(456, {'createdAt': new Date('2017-05-01T21:03:27Z'), 'filename': 'root.dat', 'extension': '.dat', 'author': 'some user',
+            size: 16452234, sha256: '03eed7a8494ab8794c44b7d4308e55448fc56f4d6c175809ba968f78f656d58d'});
+    }
+
+    function commitSetWithRoot()
+    {
+        return CommitSet.ensureSingleton(15, {
+            revisionItems: [{ commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false }],
+            customRoots: [createRoot()]
+        });
+    }
+
+    function commitSet()
+    {
+        return CommitSet.ensureSingleton(16, {
+            revisionItems: [{ commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false }],
+            customRoots: []
+        });
+    }
+
+    function commitSetsWithNoCommonRepository() {
+        return [
+            CommitSet.ensureSingleton(1, {
+                revisionItems: [
+                    { commit: makeCommit(1, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false },
+                    { commit: makeCommit(11, MockModels.osx, 'osx-commit-1', 1), requiresBuild: false }
+                ],
+                customRoots: []}),
+            CommitSet.ensureSingleton(2, {
+                revisionItems: [
+                    { commit: makeCommit(2, MockModels.webkit, 'webkit-commit-1', 1), requiresBuild: false },
+                    { commit: makeCommit(31, MockModels.ios, 'ios-commit-1', 1), requiresBuild: false },
+                ],
+                customRoots: []})
+        ];
+    }
+
+    describe('commitSetClosestToMiddleOfAllCommits', () => {
+        MockModels.inject();
+        const requests = MockRemoteAPI.inject();
+
+        it('should return "null" if no common repository found', async () => {
+            const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits(commitSetsWithNoCommonRepository().splice(0, 2));
+            assert.equal(middleCommitSet, null);
+        });
+
+        it('should return "null" to bisect commit set with root', async () => {
+            const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([commitSet(), commitSetWithRoot()], [commitSet(), commitSetWithRoot()]);
+            assert.equal(middleCommitSet, null);
+        });
+
+        it('should return "null" if no repository with time or order is found', async () => {
+            const allCommitSets = sortedCommitSetsWithoutTimeOrOrder();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const middleCommitSet = await CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            assert.equal(middleCommitSet, null);
+        });
+
+        it('should throw exception when failed to fetch commit log', async () => {
+            const allCommitSets = sortedCommitSets();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            const rejectReason = '404';
+            requests[0].reject(rejectReason);
+            let exceptionRaised = false;
+            try {
+                await promise;
+            } catch (error) {
+                exceptionRaised = true;
+                assert.equal(error, rejectReason);
+            }
+            assert.ok(exceptionRaised);
+        });
+
+        it('should return "null" if no commit set is found other than the commit sets that define the range', async () => {
+            const allCommitSets = sortedCommitSets();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], [startCommitSet, endCommitSet]);
+            assert.equal(requests.length, 2);
+            assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
+            assert.equal(requests[1].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
+            requests[0].resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 21
+                    },
+                    {
+                        repository: osxId,
+                        id: 13,
+                        revision: 'osx-commit-3',
+                        ownsCommits: false,
+                        time: 31
+                    }
+                ]
+            });
+            requests[1].resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+
+            assert.equal(await promise, null);
+        });
+
+        it('should return bisecting commit set point closest to the middle of revision range', async () => {
+            const allCommitSets = sortedCommitSets();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            assert.equal(requests.length, 2);
+            const osxFetchRequest = requests.find((fetch_request) => fetch_request.url === '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
+            const webkitFetchRequest = requests.find((fetch_request) => fetch_request.url === '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+            webkitFetchRequest.resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+            osxFetchRequest.resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 21
+                    },
+                    {
+                        repository: osxId,
+                        id: 13,
+                        revision: 'osx-commit-3',
+                        ownsCommits: false,
+                        time: 31
+                    }
+                ]
+            });
+
+            assert.equal(await promise, allCommitSets[3]);
+        });
+
+        it('should return same bisection point even when two commit sets from original commit set have reverse order', async () => {
+            const allCommitSets = sortedCommitSets();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([endCommitSet, startCommitSet], allCommitSets);
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+            requests[0].resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+            requests[1].resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 21
+                    },
+                    {
+                        repository: osxId,
+                        id: 13,
+                        revision: 'osx-commit-3',
+                        ownsCommits: false,
+                        time: 31
+                    }
+                ]
+            });
+
+            assert.equal(await promise, allCommitSets[3]);
+        });
+
+        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 () => {
+            const allCommitSets = commitSetsWithSomeCommitsOnlyHaveOrder();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+            const ownerRepositoryId = MockModels.ownerRepository.id();
+
+            assert.equal(requests.length, 3);
+            assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
+            assert.equal(requests[1].url, '/api/commits/111/?precedingRevision=owner-commit-1&lastRevision=owner-commit-3');
+            assert.equal(requests[2].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
+
+            requests[0].resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 21
+                    },
+                    {
+                        repository: osxId,
+                        id: 13,
+                        revision: 'osx-commit-3',
+                        ownsCommits: false,
+                        time: 31
+                    }
+                ]
+            });
+
+            requests[1].resolve({
+                'commits': [
+                    {
+                        repository: ownerRepositoryId,
+                        id: 202,
+                        revision: 'owner-commit-2',
+                        ownsCommits: false,
+                        time: 0,
+                        order: 2
+                    },
+                    {
+                        repository: ownerRepositoryId,
+                        id: 203,
+                        revision: 'owner-commit-3',
+                        ownsCommits: false,
+                        time: 0,
+                        order: 3
+                    }
+                ]
+            });
+
+            requests[2].resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+            assert.equal(await promise, allCommitSets[3]);
+        });
+
+        it('should filter out commit set with owned commit', async () => {
+            const allCommitSets = commitSetsWithSomeHaveOwnedCommits();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+            const ownerRepositoryId = MockModels.ownerRepository.id();
+
+            assert.equal(requests.length, 3);
+            assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-3');
+            assert.equal(requests[1].url, '/api/commits/111/?precedingRevision=owner-commit-1&lastRevision=owner-commit-3');
+            assert.equal(requests[2].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
+
+            requests[0].resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 21
+                    },
+                    {
+                        repository: osxId,
+                        id: 13,
+                        revision: 'osx-commit-3',
+                        ownsCommits: false,
+                        time: 31
+                    }
+                ]
+            });
+
+            requests[1].resolve({
+                'commits': [
+                    {
+                        repository: ownerRepositoryId,
+                        id: 202,
+                        revision: 'owner-commit-2',
+                        ownsCommits: true,
+                        time: 0,
+                        order: 2
+                    },
+                    {
+                        repository: ownerRepositoryId,
+                        id: 203,
+                        revision: 'owner-commit-3',
+                        ownsCommits: true,
+                        time: 0,
+                        order: 3
+                    }
+                ]
+            });
+
+            requests[2].resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+            assert.equal(await promise, allCommitSets[4]);
+        });
+
+        it('should still work even some commits do not monotonically increasing', async () => {
+            const allCommitSets = commitSetsWithSomeCommitsNotMonotonicallyIncrease();
+            const startCommitSet = allCommitSets[0];
+            const endCommitSet = allCommitSets[allCommitSets.length - 1];
+            const promise = CommitSetRangeBisector.commitSetClosestToMiddleOfAllCommits([startCommitSet, endCommitSet], allCommitSets);
+            const webkitId = MockModels.webkit.id();
+            const osxId = MockModels.osx.id();
+
+            assert.equal(requests.length, 2);
+            assert.equal(requests[0].url, '/api/commits/9/?precedingRevision=osx-commit-1&lastRevision=osx-commit-2');
+            assert.equal(requests[1].url, '/api/commits/11/?precedingRevision=webkit-commit-1&lastRevision=webkit-commit-6');
+
+            requests[0].resolve({
+                'commits': [
+                    {
+                        repository: osxId,
+                        id: 12,
+                        revision: 'osx-commit-2',
+                        ownsCommits: false,
+                        time: 0,
+                        order: 2
+                    }
+                ]
+            });
+            requests[1].resolve({
+                'commits': [
+                    {
+                        repository: webkitId,
+                        id: 2,
+                        revision: 'webkit-commit-2',
+                        ownsCommits: false,
+                        time: 20
+                    },
+                    {
+                        repository: webkitId,
+                        id: 3,
+                        revision: 'webkit-commit-3',
+                        ownsCommits: false,
+                        time: 30
+                    },
+                    {
+                        repository: webkitId,
+                        id: 4,
+                        revision: 'webkit-commit-4',
+                        ownsCommits: false,
+                        time: 40
+                    },
+                    {
+                        repository: webkitId,
+                        id: 5,
+                        revision: 'webkit-commit-5',
+                        ownsCommits: false,
+                        time: 50
+                    },
+                    {
+                        repository: webkitId,
+                        id: 6,
+                        revision: 'webkit-commit-6',
+                        ownsCommits: false,
+                        time: 60
+                    },
+                ]
+            });
+
+            assert.equal(await promise, allCommitSets[3]);
+        });
+    });
+});
\ No newline at end of file
index 3af3579..646deed 100644 (file)
@@ -328,6 +328,43 @@ describe('CommitSet', () => {
         });
     });
 
+    describe('containsRootOrPatchOrOwnedCommit', () => {
+        it('should return false if commit does not contain root, patch or owned commit', () => {
+            assert.ok(!oneCommitSet().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!anotherCommitSet().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!commitSetWithAnotherWebKitCommit().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!commitSetWithSVNCommit().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!anotherCommitSetWithSVNCommit().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!commitSetWithGitCommit().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!anotherCommitSetWithGitCommit().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!commitSetWithTwoCommits().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!anotherCommitSetWithTwoCommits().containsRootOrPatchOrOwnedCommit());
+            assert.ok(!oneMeasurementCommitSet().containsRootOrPatchOrOwnedCommit());
+        });
+
+        it('should return true if commit contains root, patch or owned commit', () => {
+            assert.ok(commitSetWithPatch().containsRootOrPatchOrOwnedCommit());
+            assert.ok(commitSetWithAnotherPatch().containsRootOrPatchOrOwnedCommit());
+            assert.ok(commitSetWithRoot().containsRootOrPatchOrOwnedCommit());
+            assert.ok(anotherCommitSetWithRoot().containsRootOrPatchOrOwnedCommit());
+            assert.ok(commitSetWithTwoRoots().containsRootOrPatchOrOwnedCommit());
+            assert.ok(commitSetWithAnotherCommitPatchAndRoot().containsRootOrPatchOrOwnedCommit());
+        });
+    });
+
+    describe('hasSameRepositories', () => {
+        it('should return true if two commit sets have same repositories', () => {
+            assert.ok(oneCommitSet().hasSameRepositories(anotherCommitSet()));
+            assert.ok(commitSetWithGitCommit().hasSameRepositories(anotherCommitSetWithGitCommit()));
+            assert.ok(oneCommitSet().hasSameRepositories(oneCommitSet()));
+        });
+
+        it('should return false if two commit sets have differen repositories', () => {
+            assert.ok(!commitSetWithGitCommit().hasSameRepositories(commitSetWithSVNCommit()));
+            assert.ok(!commitSetWithTwoCommits().hasSameRepositories(commitSetWithGitCommit()));
+        });
+    });
+
     describe('diff',  () => {
         it('should describe patch difference', () => {
             assert.equal(CommitSet.diff(commitSetWithPatch(), commitSetWithAnotherPatch()), 'WebKit: patch.dat - patch.dat (2)');