diff --git a/rbtools/api/resource.py b/rbtools/api/resource.py index 6a89d6fb25cd09f4c469c53351f4ad6e7e14ec7c..0d23cfed699aff96e7bdc53c05afcfb298940d6c 100644 --- a/rbtools/api/resource.py +++ b/rbtools/api/resource.py @@ -1,6 +1,7 @@ from __future__ import unicode_literals import re +from collections import defaultdict, deque import six from pkg_resources import parse_version @@ -10,6 +11,7 @@ from six.moves.urllib.parse import urljoin from rbtools.api.cache import MINIMUM_VERSION from rbtools.api.decorators import request_method_decorator from rbtools.api.request import HttpRequest +from rbtools.utils.graphs import path_exists RESOURCE_MAP = {} @@ -246,8 +248,8 @@ class ResourceLinkField(ResourceDictField): self._transport = resource._transport @request_method_decorator - def get(self): - return HttpRequest(self._fields['href']) + def get(self, **query_args): + return HttpRequest(self._fields['href'], query_args=query_args) class ResourceListField(list): @@ -716,6 +718,70 @@ class ReviewRequestResource(ItemResource): return request + def build_dependency_graph(self): + """Build the dependency graph for the review request. + + Only review requests in the same repository as this one will be in the + graph. + + A ValueError is raised if the graph would contain cycles. + """ + def get_url(resource): + """Get the URL of the resource.""" + if hasattr(resource, 'href'): + return resource.href + else: + return resource.absolute_url + + # Even with the API cache, we don't want to be making more requests + # than necessary. The review request resource will be cached by an + # ETag, so there will still be a round trip if we don't cache them + # here. + review_requests_by_url = {} + review_requests_by_url[self.absolute_url] = self + + def get_review_request_resource(resource): + url = get_url(resource) + + if url not in review_requests_by_url: + review_requests_by_url[url] = resource.get(expand='repository') + + return review_requests_by_url[url] + + repository = self.get_repository() + + graph = defaultdict(set) + + visited = set() + + unvisited = deque() + unvisited.append(self) + + while unvisited: + head = unvisited.popleft() + + if head in visited: + continue + + visited.add(get_url(head)) + + for tail in head.depends_on: + tail = get_review_request_resource(tail) + + if path_exists(graph, tail.id, head.id): + raise ValueError('Circular dependencies.') + + # We don't want to include review requests for other + # repositories, so we'll stop if we reach one. We also don't + # want to re-land submitted review requests. + if (repository.id == tail.repository.id and + tail.status != 'submitted'): + graph[head].add(tail) + unvisited.append(tail) + + graph.default_factory = None + return graph + @resource_mimetype('application/vnd.reviewboard.org.diff-validation') class ValidateDiffResource(DiffUploaderMixin, ItemResource): diff --git a/rbtools/commands/land.py b/rbtools/commands/land.py index 5e552c8b69cad37d1499e02b4a37df840aed343a..76a5ffb3627dcc310aed4efce336b73317fb08e6 100644 --- a/rbtools/commands/land.py +++ b/rbtools/commands/land.py @@ -8,6 +8,7 @@ from rbtools.utils.commands import (build_rbtools_cmd_argv, extract_commit_message, get_review_request) from rbtools.utils.console import confirm +from rbtools.utils.graphs import toposort from rbtools.utils.process import execute from rbtools.utils.review_request import (get_draft_or_current_value, get_revisions, @@ -101,6 +102,15 @@ class Land(Command): default=False, help='Simulates the landing of a change, without actually ' 'making any changes to the tree.'), + Option('--recursive', + dest='recursive', + action='store_true', + default=False, + help='Recursively fetch patches for review requests that the ' + 'specified review request depends on. This is equivalent ' + 'to calling "rbt patch" for each of those review ' + 'requests.', + added_in='0.8.0'), Command.server_options, Command.repository_options, ] @@ -123,9 +133,16 @@ class Land(Command): raise CommandError('Failed to execute "rbt patch":\n%s' % output) - def land(self, destination_branch, review_request, source_branch=None, - squash=False, edit=False, delete_branch=True, dry_run=False): - """Land an individual review request.""" + def can_land(self, review_request): + """Determine if the review request is land-able. + + A review request can be landed if it is approved or, if the Review + Board server does not keep track of approval, if the review request + has a ship-it count. + + This function returns the error with landing the review request or None + if it can be landed. + """ try: is_rr_approved = review_request.approved approval_failure = review_request.approval_failure @@ -134,23 +151,28 @@ class Land(Command): # doesn't support the `approved` field. Determining it manually. if review_request.ship_it_count == 0: is_rr_approved = False - approval_failure = ('The review request has not been marked ' + approval_failure = ('review request has not been marked ' '"Ship It!"') else: is_rr_approved = True finally: if not is_rr_approved: - raise CommandError(approval_failure) + return approval_failure + + return None + def land(self, destination_branch, review_request, source_branch=None, + squash=False, edit=False, delete_branch=True, dry_run=False): + """Land an individual review request.""" if source_branch: review_commit_message = extract_commit_message(review_request) author = review_request.get_submitter() if squash: - print('Squashing branch "%s" into "%s"' + print('Squashing branch "%s" into "%s".' % (source_branch, destination_branch)) else: - print('Merging branch "%s" into "%s"' + print('Merging branch "%s" into "%s".' % (source_branch, destination_branch)) if not dry_run: @@ -165,12 +187,12 @@ class Land(Command): raise CommandError(six.text_type(e)) if delete_branch: - print('Deleting merged branch "%s"' % source_branch) + print('Deleting merged branch "%s".' % source_branch) if not dry_run: self.tool.delete_branch(source_branch, merged_only=False) else: - print('Applying patch from review request %s' % review_request.id) + print('Applying patch from review request %s.' % review_request.id) if not dry_run: self.patch(review_request.id) @@ -244,6 +266,44 @@ class Land(Command): else: branch_name = None + land_error = self.can_land(review_request) + + if land_error is not None: + raise CommandError('Cannot land review request %s: %s' + % (review_request_id, land_error)) + + if self.options.recursive: + # The dependency graph shows us which review requests depend on + # which other ones. What we are actually after is the order to land + # them in, which is the topological sorting order of the converse + # graph. It just so happens that if we reverse the topological sort + # of a graph, it is a valid topological sorting of the converse + # graph, so we don't have to compute the converse graph. + dependency_graph = review_request.build_dependency_graph() + dependencies = toposort(dependency_graph)[1:] + + if dependencies: + print('Recursively landing dependencies of review request %s.' + % review_request_id) + + for dependency in dependencies: + land_error = self.can_land(dependency) + + if land_error is not None: + raise CommandError( + 'Aborting recursive land of review request %s.\n' + 'Review request %s cannot be landed: %s' + % (review_request_id, dependency.id, land_error)) + + for dependency in reversed(dependencies): + self.land(self.options.destination_branch, + dependency, + None, + self.options.squash, + self.options.edit, + self.options.delete_branch, + self.options.dry_run) + self.land(self.options.destination_branch, review_request, branch_name, diff --git a/rbtools/utils/graphs.py b/rbtools/utils/graphs.py new file mode 100644 index 0000000000000000000000000000000000000000..944a7d13865b0b795dee879261562481d790f593 --- /dev/null +++ b/rbtools/utils/graphs.py @@ -0,0 +1,79 @@ +from __future__ import unicode_literals + +from collections import defaultdict, deque + +import six + + +def visit_depth_first(graph, start): + """Yield vertices in the graph starting at the start vertex. + + The vertices are yielded in a depth first order and only those vertices + that can be reached from the start vertex will be yielded. + """ + unvisited = deque() + visited = set() + + unvisited.append(start) + + while unvisited: + vertex = unvisited.popleft() + + if vertex in visited: + continue + + visited.add(vertex) + + yield vertex + + if vertex in graph: + for adjacent in graph[vertex]: + unvisited.append(adjacent) + + +def path_exists(graph, start, end): + """Determine if a directed path exists between start and end in graph.""" + for vertex in visit_depth_first(graph, start): + if vertex == end: + return True + + return False + + +def toposort(graph): + """Return a topological sorting of the vertices in the directed graph. + + If the graph contains cycles, ValueError is raised. + """ + result = [] + + indegrees = defaultdict(int) # The in-degree of each vertex in the graph. + + for head in six.iterkeys(graph): + indegrees[head] = 0 + + for tails in six.itervalues(graph): + for tail in tails: + indegrees[tail] += 1 + + heads = set( + vertex + for vertex, indegree in six.iteritems(indegrees) + if indegree == 0 + ) + + while len(heads): + head = heads.pop() + result.append(head) + + if head in graph: + for tail in graph[head]: + indegrees[tail] -= 1 + + if indegrees[tail] == 0: + heads.add(tail) + + if any(six.itervalues(indegrees)): + raise ValueError('Graph contains cycles.') + + return result