Output a list of suggested OWNERS reviewers when needed.

owners.py

 # Copyright (c) 2012 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """A database of OWNERS files."""
 
 import collections
 import re
 
 
@@ skipping 147 matching lines @@
             'unknown option: "%s"' % line[4:].strip())
       if self.email_regexp.match(line) or line == EVERYONE:
         self.owned_by.setdefault(line, set()).add(dirpath)
         self.owners_for.setdefault(dirpath, set()).add(line)
         continue
       raise SyntaxErrorInOwnersFile(owners_path, lineno,
             ('line is not a comment, a "set" directive, '
              'or an email address: "%s"' % line))
 
   def _covering_set_of_owners_for(self, files):
-    # TODO(dpranke): implement the greedy algorithm for covering sets, and
-    # consider returning multiple options in case there are several equally
-    # short combinations of owners.
-    every_owner = set()
+    # Get the set of directories from the files.
+    dirs = set()
     for f in files:
-      dirname = self.os_path.dirname(f)
+      dirs.add(self.os_path.dirname(f))
+
+    owned_dirs = {}
+    dir_owners = {}
+
+    for current_dir in dirs:
+      # Get the list of owners for each directory.
+      current_owners = set()
+      dirname = current_dir
       while dirname in self.owners_for:
-        every_owner |= self.owners_for[dirname]
+        for owner in self.owners_for[dirname]:
+          current_owners.add(owner)

[Dirk Pranke, 2012/04/27 00:00:13]

nit: this can just be current_owners |= self.owners_for[dir_name]

[Zachary Kuznia, 2012/05/02 08:57:58]

Done.

         if self._stop_looking(dirname):
           break
         dirname = self.os_path.dirname(dirname)
-    return every_owner
+
+      # Map each directory to a list of its owners.
+      dir_owners[current_dir] = current_owners
+
+      # Add the directory to the list of each owner.
+      for owner in current_owners:
+        if not owner in owned_dirs:
+          owned_dirs[owner] = set()
+        owned_dirs[owner].add(current_dir)

[Dirk Pranke, 2012/04/27 00:00:13]

nit: lines 192-194 would be a little more idiomatic as:

  owned_dirs.get(owner, set()).add(current_dir)

[Zachary Kuznia, 2012/05/02 08:57:58]

Done.

+
+    final_owners = set()
+    while dirs:
+      # Find the owner that has the most directories.
+      max_count = 0
+      max_owner = None
+      owner_count = {}
+      for dirname in dirs:
+        for owner in dir_owners[dirname]:
+          count = owner_count.get(owner, 0) + 1
+          owner_count[owner] = count
+          if count >= max_count:
+            max_owner = owner

[Dirk Pranke, 2012/04/27 00:00:13]

I think if you have cases where the same set of directories is covered by the
same set of owners you will always pick the same person and the other owners
will get "starved". I wonder if we want to randomize this choice ...

[Zachary Kuznia, 2012/05/02 08:57:58]

Next week, I'm going to look at adding prioritization for the deepest nested
owners.  Do you think that would be sufficient?

On 2012/04/27 00:00:13, Dirk Pranke wrote:

[Dirk Pranke, 2012/05/02 21:43:32]

Dunno. Possibly. I suggest launch early and iterate often :) We'll see who
complains.

+
+      # If no more directories have OWNERS, we're done.
+      if not max_owner:
+        break
+
+      final_owners.add(max_owner)
+
+      # Remove all directories owned by the current owner from the remaining
+      # list.
+      for dirname in owned_dirs[max_owner]:
+        dirs.remove(dirname)
+
+    return final_owners