OLD | NEW |
---|---|
1 # Copyright 2016 The Chromium Authors. All rights reserved. | 1 # Copyright 2016 The Chromium Authors. All rights reserved. |
2 # Use of this source code is governed by a BSD-style license that can be | 2 # Use of this source code is governed by a BSD-style license that can be |
3 # found in the LICENSE file. | 3 # found in the LICENSE file. |
4 | 4 |
5 import collections | 5 import collections |
6 import itertools | 6 import itertools |
7 | 7 |
8 from dashboard.pinpoint.models.change import commit as commit_module | 8 from dashboard.pinpoint.models.change import commit as commit_module |
9 from dashboard.pinpoint.models.change import patch as patch_module | 9 from dashboard.pinpoint.models.change import patch as patch_module |
10 | 10 |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
66 for commit in data['commits']) | 66 for commit in data['commits']) |
67 if 'patch' in data: | 67 if 'patch' in data: |
68 patch = patch_module.Patch.FromDict(data['patch']) | 68 patch = patch_module.Patch.FromDict(data['patch']) |
69 else: | 69 else: |
70 patch = None | 70 patch = None |
71 | 71 |
72 return cls(commits, patch=patch) | 72 return cls(commits, patch=patch) |
73 | 73 |
74 @classmethod | 74 @classmethod |
75 def Midpoint(cls, change_a, change_b): | 75 def Midpoint(cls, change_a, change_b): |
76 """Returns a Change halfway between the two given Changes. | 76 """Returns a Change halfway between the two given Changes. |
perezju
2017/09/20 15:29:41
After thinking through this, I think the important
| |
77 | 77 |
78 This function does two passes over the Changes' Commits: | 78 This function does two passes over the Changes' Commits: |
79 * The first pass attempts to match the lengths of the Commit lists by | 79 * The first pass attempts to match the lengths of the Commit lists by |
80 expanding DEPS to fill in any repositories that are missing from one, | 80 expanding DEPS to fill in any repositories that are missing from one, |
81 but included in the other. | 81 but included in the other. |
82 * The second pass takes the midpoint of every matched pair of Commits, | 82 * The second pass takes the midpoint of every matched pair of Commits, |
83 expanding DEPS rolls as it comes across them. | 83 expanding DEPS rolls as it comes across them. |
84 | 84 |
85 A NonLinearError is raised if there is no valid midpoint. The Changes are | 85 A NonLinearError is raised if there is no valid midpoint. The Changes are |
86 not linear if any of the following is true: | 86 not linear if any of the following is true: |
87 * They have different patches. | 87 * They have different patches. |
88 * Their repositories don't match even after expanding DEPS rolls. | 88 * Their repositories don't match even after expanding DEPS rolls. |
89 * The left Change comes after the right Change. | 89 * The left Change does not come before the right Change. |
90 * They are the same or adjacent. | |
91 See change_test.py for examples of linear and nonlinear Changes. | 90 See change_test.py for examples of linear and nonlinear Changes. |
92 | 91 |
92 If the range has an even number of Changes, the midpoint is the Change just | |
93 before the halfway point. The range includes both change_a and change_b; | |
94 i.e. if change_a and change_b are adjacent or the same, the midpoint is | |
95 change_a. | |
96 | |
93 Args: | 97 Args: |
94 change_a: The first Change in the range. | 98 change_a: The first Change in the range. |
95 change_b: The last Change in the range. | 99 change_b: The last Change in the range. |
96 | 100 |
97 Returns: | 101 Returns: |
98 A new Change representing the midpoint. | 102 A tuple of (Change, (left, right)). left and right are the distances |
perezju
2017/09/19 15:58:05
I think it's cleaner if it returns just (change, l
| |
99 The Change before the midpoint if the range has an even number of commits. | 103 between the midpoint and change_a and change_b, respectively. |
100 | 104 |
101 Raises: | 105 Raises: |
102 NonLinearError: The Changes are not linear. | 106 NonLinearError: The Changes are not linear. |
103 """ | 107 """ |
104 if change_a.patch != change_b.patch: | 108 if change_a.patch != change_b.patch: |
105 raise commit_module.NonLinearError( | 109 raise commit_module.NonLinearError( |
106 'Change A has patch "%s" and Change B has patch "%s".' % | 110 'Change A has patch "%s" and Change B has patch "%s".' % |
107 (change_a.patch, change_b.patch)) | 111 (change_a.patch, change_b.patch)) |
108 | 112 |
109 commits_a = list(change_a.commits) | 113 commits_a = list(change_a.commits) |
110 commits_b = list(change_b.commits) | 114 commits_b = list(change_b.commits) |
111 | 115 |
112 _ExpandDepsToMatchRepositories(commits_a, commits_b) | 116 _ExpandDepsToMatchRepositories(commits_a, commits_b) |
113 commits_midpoint = _FindMidpoints(commits_a, commits_b) | 117 midpoints = _FindMidpoints(commits_a, commits_b) |
118 commits_midpoint, distances = zip(*midpoints) | |
114 | 119 |
115 if commits_a == commits_midpoint: | 120 midpoint = cls(commits_midpoint, change_a.patch) |
116 raise commit_module.NonLinearError('Changes are the same or adjacent.') | 121 distances = tuple(map(max, zip(*distances))) |
117 | 122 return midpoint, distances |
118 return cls(commits_midpoint, change_a.patch) | |
119 | 123 |
120 | 124 |
121 def _ExpandDepsToMatchRepositories(commits_a, commits_b): | 125 def _ExpandDepsToMatchRepositories(commits_a, commits_b): |
122 """Expands DEPS in a Commit list to match the repositories in another. | 126 """Expands DEPS in a Commit list to match the repositories in another. |
123 | 127 |
124 Given two lists of Commits, with one bigger than the other, this function | 128 Given two lists of Commits, with one bigger than the other, this function |
125 looks through the DEPS files for smaller commit list to fill out any missing | 129 looks through the DEPS files for smaller commit list to fill out any missing |
126 Commits that are already in the bigger commit list. | 130 Commits that are already in the bigger commit list. |
127 | 131 |
128 Mutates the lists in-place, and doesn't return anything. The lists will not | 132 Mutates the lists in-place, and doesn't return anything. The lists will not |
(...skipping 23 matching lines...) Expand all Loading... | |
152 # Look through commits_b for any extra slots to fill with the DEPS. | 156 # Look through commits_b for any extra slots to fill with the DEPS. |
153 for commit_b in commits_b[len(commits_a):]: | 157 for commit_b in commits_b[len(commits_a):]: |
154 dep_a = _FindCommitWithRepository(deps_a, commit_b.repository) | 158 dep_a = _FindCommitWithRepository(deps_a, commit_b.repository) |
155 if dep_a: | 159 if dep_a: |
156 commits_a.append(dep_a) | 160 commits_a.append(dep_a) |
157 else: | 161 else: |
158 break | 162 break |
159 | 163 |
160 | 164 |
161 def _FindMidpoints(commits_a, commits_b): | 165 def _FindMidpoints(commits_a, commits_b): |
162 """Returns the midpoint of two Commit lists. | 166 """Returns the midpoints of two Commit lists. |
163 | 167 |
164 Loops through each pair of Commits and takes the midpoint. If the repositories | 168 Loops through each pair of Commits and takes the midpoint. If the repositories |
165 don't match, a NonLinearError is raised. If the Commits are adjacent and | 169 don't match, a NonLinearError is raised. If the Commits are adjacent and |
166 represent a DEPS roll, the differing DEPs are added to the end of the lists. | 170 represent a DEPS roll, the differing DEPs are added to the end of the lists. |
167 | 171 |
168 Args: | 172 Args: |
169 commits_a: A list of Commits. | 173 commits_a: A list of Commits. |
170 commits_b: A list of Commits. | 174 commits_b: A list of Commits. |
171 | 175 |
172 Returns: | 176 Returns: |
173 A list of Commits, each of which is the midpoint of the respective Commit in | 177 A list of tuples. Each tuple is the result of Commit.Midpoint(). |
174 commits_a and commits_b. | |
175 | 178 |
176 Raises: | 179 Raises: |
177 NonLinearError: The lists have a different number of commits even after | 180 NonLinearError: The lists have a different number of commits even after |
178 expanding DEPS rolls, a Commit pair contains differing repositories, or a | 181 expanding DEPS rolls, a Commit pair contains differing repositories, or a |
179 Commit pair is in the wrong order. | 182 Commit pair is in the wrong order. |
180 """ | 183 """ |
181 commits_midpoint = [] | 184 midpoints = [] |
182 | 185 |
183 for commit_a, commit_b in itertools.izip_longest(commits_a, commits_b): | 186 for commit_a, commit_b in itertools.izip_longest(commits_a, commits_b): |
184 if not (commit_a and commit_b): | 187 if not (commit_a and commit_b): |
185 # If the commit lists are not the same length, bail out. That could happen | 188 # If the commit lists are not the same length, bail out. That could happen |
186 # if commits_b has a repository that was not found in the DEPS of | 189 # if commits_b has a repository that was not found in the DEPS of |
187 # commits_a (or vice versa); or a DEPS roll added or removed a DEP. | 190 # commits_a (or vice versa); or a DEPS roll added or removed a DEP. |
188 raise commit_module.NonLinearError( | 191 raise commit_module.NonLinearError( |
189 'Changes have a different number of commits.') | 192 'Changes have a different number of commits.') |
190 | 193 |
191 commit_midpoint = commit_module.Commit.Midpoint(commit_a, commit_b) | 194 midpoint, distances = commit_module.Commit.Midpoint(commit_a, commit_b) |
192 commits_midpoint.append(commit_midpoint) | 195 midpoints.append((midpoint, distances)) |
193 if commit_a == commit_midpoint != commit_b: | 196 |
197 if sum(distances) == 1: | |
194 # Commits are adjacent. | 198 # Commits are adjacent. |
195 # Add any DEPS changes to the commit lists. | 199 # Add any DEPS changes to the commit lists. |
196 deps_a = commit_a.Deps() | 200 deps_a = commit_a.Deps() |
197 deps_b = commit_b.Deps() | 201 deps_b = commit_b.Deps() |
perezju
2017/09/20 15:29:41
The logic would be clearer if we would raise the e
| |
198 commits_a += sorted( | 202 commits_a += sorted( |
199 dep for dep in deps_a.difference(deps_b) | 203 dep for dep in deps_a.difference(deps_b) |
200 if not _FindCommitWithRepository(commits_a, dep.repository)) | 204 if not _FindCommitWithRepository(commits_a, dep.repository)) |
201 commits_b += sorted( | 205 commits_b += sorted( |
202 dep for dep in deps_b.difference(deps_a) | 206 dep for dep in deps_b.difference(deps_a) |
203 if not _FindCommitWithRepository(commits_b, dep.repository)) | 207 if not _FindCommitWithRepository(commits_b, dep.repository)) |
204 | 208 |
205 return commits_midpoint | 209 return midpoints |
206 | 210 |
207 | 211 |
208 def _FindCommitWithRepository(commits, repository): | 212 def _FindCommitWithRepository(commits, repository): |
209 for commit in commits: | 213 for commit in commits: |
210 if commit.repository == repository: | 214 if commit.repository == repository: |
211 return commit | 215 return commit |
212 return None | 216 return None |
OLD | NEW |