blob: c7ff26949767b8fae3f53b3e0a49db413846deb2 [file] [log] [blame]
pam@chromium.orgf46aed92012-03-08 09:18:17 +00001# Copyright (c) 2012 The Chromium Authors. All rights reserved.
dpranke@chromium.org2a009622011-03-01 02:43:31 +00002# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
dpranke@chromium.org17cc2442012-10-17 21:12:09 +00005"""A database of OWNERS files.
6
7OWNERS files indicate who is allowed to approve changes in a specific directory
8(or who is allowed to make changes without needing approval of another OWNER).
9Note that all changes must still be reviewed by someone familiar with the code,
10so you may need approval from both an OWNER and a reviewer in many cases.
11
12The syntax of the OWNERS file is, roughly:
13
14lines := (\s* line? \s* "\n")*
15
16line := directive
dpranke@chromium.orgd16e48b2012-12-03 21:53:49 +000017 | "per-file" \s+ glob \s* "=" \s* directive
dpranke@chromium.org17cc2442012-10-17 21:12:09 +000018 | comment
19
20directive := "set noparent"
peter@chromium.org2ce13132015-04-16 16:42:08 +000021 | "file:" glob
dpranke@chromium.org17cc2442012-10-17 21:12:09 +000022 | email_address
23 | "*"
24
25glob := [a-zA-Z0-9_-*?]+
26
27comment := "#" [^"\n"]*
28
29Email addresses must follow the foo@bar.com short form (exact syntax given
30in BASIC_EMAIL_REGEXP, below). Filename globs follow the simple unix
31shell conventions, and relative and absolute paths are not allowed (i.e.,
32globs only refer to the files in the current directory).
33
34If a user's email is one of the email_addresses in the file, the user is
35considered an "OWNER" for all files in the directory.
36
37If the "per-file" directive is used, the line only applies to files in that
38directory that match the filename glob specified.
39
40If the "set noparent" directive used, then only entries in this OWNERS file
41apply to files in this directory; if the "set noparent" directive is not
42used, then entries in OWNERS files in enclosing (upper) directories also
43apply (up until a "set noparent is encountered").
44
45If "per-file glob=set noparent" is used, then global directives are ignored
46for the glob, and only the "per-file" owners are used for files matching that
47glob.
48
peter@chromium.org2ce13132015-04-16 16:42:08 +000049If the "file:" directive is used, the referred to OWNERS file will be parsed and
50considered when determining the valid set of OWNERS. If the filename starts with
51"//" it is relative to the root of the repository, otherwise it is relative to
52the current file
53
dpranke@chromium.org17cc2442012-10-17 21:12:09 +000054Examples for all of these combinations can be found in tests/owners_unittest.py.
55"""
dpranke@chromium.org2a009622011-03-01 02:43:31 +000056
dpranke@chromium.orgfdecfb72011-03-16 23:27:23 +000057import collections
dtu944b6052016-07-14 14:48:21 -070058import fnmatch
dpranke@chromium.orgc591a702012-12-20 20:14:58 +000059import random
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +000060import re
61
62
63# If this is present by itself on a line, this means that everyone can review.
64EVERYONE = '*'
65
66
67# Recognizes 'X@Y' email addresses. Very simplistic.
68BASIC_EMAIL_REGEXP = r'^[\w\-\+\%\.]+\@[\w\-\+\%\.]+$'
dpranke@chromium.org2a009622011-03-01 02:43:31 +000069
dpranke@chromium.org2a009622011-03-01 02:43:31 +000070
Jochen Eisinger72606f82017-04-04 10:44:18 +020071# Key for global comments per email address. Should be unlikely to be a
72# pathname.
73GLOBAL_STATUS = '*'
74
75
dpranke@chromium.org923950f2011-03-17 23:40:00 +000076def _assert_is_collection(obj):
dpranke@chromium.orge6a4ab32011-03-31 01:23:08 +000077 assert not isinstance(obj, basestring)
maruel@chromium.org725f1c32011-04-01 20:24:54 +000078 # Module 'collections' has no 'Iterable' member
Quinten Yearsleyb2cc4a92016-12-15 13:53:26 -080079 # pylint: disable=no-member
dpranke@chromium.orge6a4ab32011-03-31 01:23:08 +000080 if hasattr(collections, 'Iterable') and hasattr(collections, 'Sized'):
81 assert (isinstance(obj, collections.Iterable) and
82 isinstance(obj, collections.Sized))
dpranke@chromium.org923950f2011-03-17 23:40:00 +000083
84
dpranke@chromium.org898a10e2011-03-04 21:54:43 +000085class SyntaxErrorInOwnersFile(Exception):
dpranke@chromium.org86bbf192011-03-09 21:37:06 +000086 def __init__(self, path, lineno, msg):
87 super(SyntaxErrorInOwnersFile, self).__init__((path, lineno, msg))
dpranke@chromium.org898a10e2011-03-04 21:54:43 +000088 self.path = path
dpranke@chromium.org86bbf192011-03-09 21:37:06 +000089 self.lineno = lineno
dpranke@chromium.org898a10e2011-03-04 21:54:43 +000090 self.msg = msg
91
92 def __str__(self):
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +000093 return '%s:%d syntax error: %s' % (self.path, self.lineno, self.msg)
dpranke@chromium.org898a10e2011-03-04 21:54:43 +000094
95
dpranke@chromium.org898a10e2011-03-04 21:54:43 +000096class Database(object):
97 """A database of OWNERS files for a repository.
98
99 This class allows you to find a suggested set of reviewers for a list
100 of changed files, and see if a list of changed files is covered by a
101 list of reviewers."""
102
Jochen Eisingereb744762017-04-05 11:00:05 +0200103 def __init__(self, root, fopen, os_path):
dpranke@chromium.org898a10e2011-03-04 21:54:43 +0000104 """Args:
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000105 root: the path to the root of the Repository
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000106 open: function callback to open a text file for reading
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000107 os_path: module/object callback with fields for 'abspath', 'dirname',
mbjorgef2d73522016-07-14 13:28:59 -0700108 'exists', 'join', and 'relpath'
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000109 """
110 self.root = root
111 self.fopen = fopen
112 self.os_path = os_path
113
dpranke@chromium.org627ea672011-03-11 23:29:03 +0000114 # Pick a default email regexp to use; callers can override as desired.
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000115 self.email_regexp = re.compile(BASIC_EMAIL_REGEXP)
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000116
dtu944b6052016-07-14 14:48:21 -0700117 # Mapping of owners to the paths or globs they own.
118 self._owners_to_paths = {EVERYONE: set()}
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000119
120 # Mapping of paths to authorized owners.
dtu944b6052016-07-14 14:48:21 -0700121 self._paths_to_owners = {}
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000122
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000123 # Mapping reviewers to the preceding comment per file in the OWNERS files.
124 self.comments = {}
125
nick7e16cf32016-09-16 16:05:05 -0700126 # Cache of compiled regexes for _fnmatch()
127 self._fnmatch_cache = {}
128
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000129 # Set of paths that stop us from looking above them for owners.
130 # (This is implicitly true for the root directory).
dtu944b6052016-07-14 14:48:21 -0700131 self._stop_looking = set([''])
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000132
peter@chromium.org2ce13132015-04-16 16:42:08 +0000133 # Set of files which have already been read.
134 self.read_files = set()
135
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800136 # Set of files which were included from other files. Files are processed
137 # differently depending on whether they are regular owners files or
138 # being included from another file.
139 self._included_files = {}
140
Jochen Eisingereb744762017-04-05 11:00:05 +0200141 # File with global status lines for owners.
142 self._status_file = None
143
dpranke@chromium.orgdbf8b4e2013-02-28 19:24:16 +0000144 def reviewers_for(self, files, author):
dpranke@chromium.orgfdecfb72011-03-16 23:27:23 +0000145 """Returns a suggested set of reviewers that will cover the files.
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000146
dpranke@chromium.orgdbf8b4e2013-02-28 19:24:16 +0000147 files is a sequence of paths relative to (and under) self.root.
148 If author is nonempty, we ensure it is not included in the set returned
149 in order avoid suggesting the author as a reviewer for their own changes."""
dpranke@chromium.org7eea2592011-03-09 21:35:46 +0000150 self._check_paths(files)
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000151 self.load_data_needed_for(files)
dtu944b6052016-07-14 14:48:21 -0700152
dpranke@chromium.orgdbf8b4e2013-02-28 19:24:16 +0000153 suggested_owners = self._covering_set_of_owners_for(files, author)
dpranke@chromium.org9d66f482013-01-18 02:57:11 +0000154 if EVERYONE in suggested_owners:
155 if len(suggested_owners) > 1:
156 suggested_owners.remove(EVERYONE)
157 else:
158 suggested_owners = set(['<anyone>'])
159 return suggested_owners
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000160
dpranke@chromium.org6b1e3ee2013-02-23 00:06:38 +0000161 def files_not_covered_by(self, files, reviewers):
162 """Returns the files not owned by one of the reviewers.
dpranke@chromium.orgfdecfb72011-03-16 23:27:23 +0000163
164 Args:
165 files is a sequence of paths relative to (and under) self.root.
pam@chromium.orgf46aed92012-03-08 09:18:17 +0000166 reviewers is a sequence of strings matching self.email_regexp.
167 """
dpranke@chromium.org7eea2592011-03-09 21:35:46 +0000168 self._check_paths(files)
169 self._check_reviewers(reviewers)
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000170 self.load_data_needed_for(files)
pam@chromium.orgf46aed92012-03-08 09:18:17 +0000171
dtu944b6052016-07-14 14:48:21 -0700172 return set(f for f in files if not self._is_obj_covered_by(f, reviewers))
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000173
dpranke@chromium.org7eea2592011-03-09 21:35:46 +0000174 def _check_paths(self, files):
175 def _is_under(f, pfx):
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000176 return self.os_path.abspath(self.os_path.join(pfx, f)).startswith(pfx)
dpranke@chromium.org923950f2011-03-17 23:40:00 +0000177 _assert_is_collection(files)
dpranke@chromium.orgb54a78e2012-12-13 23:37:23 +0000178 assert all(not self.os_path.isabs(f) and
179 _is_under(f, self.os_path.abspath(self.root)) for f in files)
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000180
dpranke@chromium.org7eea2592011-03-09 21:35:46 +0000181 def _check_reviewers(self, reviewers):
dpranke@chromium.org923950f2011-03-17 23:40:00 +0000182 _assert_is_collection(reviewers)
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000183 assert all(self.email_regexp.match(r) for r in reviewers)
184
dtu944b6052016-07-14 14:48:21 -0700185 def _is_obj_covered_by(self, objname, reviewers):
186 reviewers = list(reviewers) + [EVERYONE]
187 while True:
188 for reviewer in reviewers:
189 for owned_pattern in self._owners_to_paths.get(reviewer, set()):
190 if fnmatch.fnmatch(objname, owned_pattern):
191 return True
192 if self._should_stop_looking(objname):
193 break
dpranke@chromium.org6b1e3ee2013-02-23 00:06:38 +0000194 objname = self.os_path.dirname(objname)
dtu944b6052016-07-14 14:48:21 -0700195 return False
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000196
dpranke@chromium.org6b1e3ee2013-02-23 00:06:38 +0000197 def _enclosing_dir_with_owners(self, objname):
pam@chromium.orgf46aed92012-03-08 09:18:17 +0000198 """Returns the innermost enclosing directory that has an OWNERS file."""
dpranke@chromium.org6b1e3ee2013-02-23 00:06:38 +0000199 dirpath = objname
dtu944b6052016-07-14 14:48:21 -0700200 while not self._owners_for(dirpath):
201 if self._should_stop_looking(dirpath):
pam@chromium.orgf46aed92012-03-08 09:18:17 +0000202 break
203 dirpath = self.os_path.dirname(dirpath)
204 return dirpath
205
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000206 def load_data_needed_for(self, files):
Jochen Eisinger72606f82017-04-04 10:44:18 +0200207 self._read_global_comments()
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000208 for f in files:
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000209 dirpath = self.os_path.dirname(f)
dtu944b6052016-07-14 14:48:21 -0700210 while not self._owners_for(dirpath):
peter@chromium.org2ce13132015-04-16 16:42:08 +0000211 self._read_owners(self.os_path.join(dirpath, 'OWNERS'))
dtu944b6052016-07-14 14:48:21 -0700212 if self._should_stop_looking(dirpath):
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000213 break
214 dirpath = self.os_path.dirname(dirpath)
dpranke@chromium.org2a009622011-03-01 02:43:31 +0000215
dtu944b6052016-07-14 14:48:21 -0700216 def _should_stop_looking(self, objname):
nick7e16cf32016-09-16 16:05:05 -0700217 return any(self._fnmatch(objname, stop_looking)
dtu944b6052016-07-14 14:48:21 -0700218 for stop_looking in self._stop_looking)
219
220 def _owners_for(self, objname):
221 obj_owners = set()
222 for owned_path, path_owners in self._paths_to_owners.iteritems():
nick7e16cf32016-09-16 16:05:05 -0700223 if self._fnmatch(objname, owned_path):
dtu944b6052016-07-14 14:48:21 -0700224 obj_owners |= path_owners
225 return obj_owners
226
peter@chromium.org2ce13132015-04-16 16:42:08 +0000227 def _read_owners(self, path):
228 owners_path = self.os_path.join(self.root, path)
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000229 if not self.os_path.exists(owners_path):
230 return
peter@chromium.org2ce13132015-04-16 16:42:08 +0000231
232 if owners_path in self.read_files:
233 return
234
235 self.read_files.add(owners_path)
236
Jochen Eisingereb744762017-04-05 11:00:05 +0200237 is_toplevel = path == 'OWNERS'
238
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000239 comment = []
peter@chromium.org2ce13132015-04-16 16:42:08 +0000240 dirpath = self.os_path.dirname(path)
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000241 in_comment = False
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000242 lineno = 0
243 for line in self.fopen(owners_path):
244 lineno += 1
245 line = line.strip()
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000246 if line.startswith('#'):
Jochen Eisingereb744762017-04-05 11:00:05 +0200247 if is_toplevel:
248 m = re.match('#\s*OWNERS_STATUS\s+=\s+(.+)$', line)
249 if m:
250 self._status_file = m.group(1).strip()
251 continue
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000252 if not in_comment:
253 comment = []
254 comment.append(line[1:].strip())
255 in_comment = True
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000256 continue
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000257 if line == '':
258 continue
259 in_comment = False
260
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000261 if line == 'set noparent':
dtu944b6052016-07-14 14:48:21 -0700262 self._stop_looking.add(dirpath)
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000263 continue
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000264
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000265 m = re.match('per-file (.+)=(.+)', line)
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000266 if m:
dpranke@chromium.orgd16e48b2012-12-03 21:53:49 +0000267 glob_string = m.group(1).strip()
268 directive = m.group(2).strip()
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000269 full_glob_string = self.os_path.join(self.root, dirpath, glob_string)
dpranke@chromium.org9e227d52012-10-20 23:47:42 +0000270 if '/' in glob_string or '\\' in glob_string:
dpranke@chromium.orge3b1c3d2012-10-20 22:28:14 +0000271 raise SyntaxErrorInOwnersFile(owners_path, lineno,
dpranke@chromium.org9e227d52012-10-20 23:47:42 +0000272 'per-file globs cannot span directories or use escapes: "%s"' %
273 line)
dtu944b6052016-07-14 14:48:21 -0700274 relative_glob_string = self.os_path.relpath(full_glob_string, self.root)
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800275 self._add_entry(relative_glob_string, directive, owners_path,
276 lineno, '\n'.join(comment))
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000277 continue
278
dpranke@chromium.org86bbf192011-03-09 21:37:06 +0000279 if line.startswith('set '):
280 raise SyntaxErrorInOwnersFile(owners_path, lineno,
281 'unknown option: "%s"' % line[4:].strip())
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000282
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800283 self._add_entry(dirpath, line, owners_path, lineno,
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000284 ' '.join(comment))
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000285
Jochen Eisinger72606f82017-04-04 10:44:18 +0200286 def _read_global_comments(self):
Jochen Eisingereb744762017-04-05 11:00:05 +0200287 if not self._status_file:
288 if not 'OWNERS' in self.read_files:
289 self._read_owners('OWNERS')
290 if not self._status_file:
291 return
Jochen Eisinger72606f82017-04-04 10:44:18 +0200292
Jochen Eisingereb744762017-04-05 11:00:05 +0200293 owners_status_path = self.os_path.join(self.root, self._status_file)
Jochen Eisinger72606f82017-04-04 10:44:18 +0200294 if not self.os_path.exists(owners_status_path):
Jochen Eisingereb744762017-04-05 11:00:05 +0200295 raise IOError('Could not find global status file "%s"' %
Jochen Eisinger72606f82017-04-04 10:44:18 +0200296 owners_status_path)
297
298 if owners_status_path in self.read_files:
299 return
300
301 self.read_files.add(owners_status_path)
302
303 lineno = 0
304 for line in self.fopen(owners_status_path):
305 lineno += 1
306 line = line.strip()
307 if line.startswith('#'):
308 continue
309 if line == '':
310 continue
311
312 m = re.match('(.+?):(.+)', line)
313 if m:
314 owner = m.group(1).strip()
315 comment = m.group(2).strip()
316 if not self.email_regexp.match(owner):
317 raise SyntaxErrorInOwnersFile(owners_status_path, lineno,
318 'invalid email address: "%s"' % owner)
319
320 self.comments.setdefault(owner, {})
321 self.comments[owner][GLOBAL_STATUS] = comment
322 continue
323
324 raise SyntaxErrorInOwnersFile(owners_status_path, lineno,
325 'cannot parse status entry: "%s"' % line.strip())
326
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800327 def _add_entry(self, owned_paths, directive, owners_path, lineno, comment):
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000328 if directive == 'set noparent':
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800329 self._stop_looking.add(owned_paths)
peter@chromium.org2ce13132015-04-16 16:42:08 +0000330 elif directive.startswith('file:'):
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800331 include_file = self._resolve_include(directive[5:], owners_path)
332 if not include_file:
peter@chromium.org2ce13132015-04-16 16:42:08 +0000333 raise SyntaxErrorInOwnersFile(owners_path, lineno,
334 ('%s does not refer to an existing file.' % directive[5:]))
335
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800336 included_owners = self._read_just_the_owners(include_file)
337 for owner in included_owners:
338 self._owners_to_paths.setdefault(owner, set()).add(owned_paths)
339 self._paths_to_owners.setdefault(owned_paths, set()).add(owner)
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000340 elif self.email_regexp.match(directive) or directive == EVERYONE:
Jochen Eisinger72606f82017-04-04 10:44:18 +0200341 if comment:
342 self.comments.setdefault(directive, {})
343 self.comments[directive][owned_paths] = comment
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800344 self._owners_to_paths.setdefault(directive, set()).add(owned_paths)
345 self._paths_to_owners.setdefault(owned_paths, set()).add(directive)
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000346 else:
dpranke@chromium.org86bbf192011-03-09 21:37:06 +0000347 raise SyntaxErrorInOwnersFile(owners_path, lineno,
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800348 ('"%s" is not a "set noparent", file include, "*", '
349 'or an email address.' % (directive,)))
dpranke@chromium.org17cc2442012-10-17 21:12:09 +0000350
peter@chromium.org2ce13132015-04-16 16:42:08 +0000351 def _resolve_include(self, path, start):
352 if path.startswith('//'):
353 include_path = path[2:]
354 else:
355 assert start.startswith(self.root)
mbjorgef2d73522016-07-14 13:28:59 -0700356 start = self.os_path.dirname(self.os_path.relpath(start, self.root))
peter@chromium.org2ce13132015-04-16 16:42:08 +0000357 include_path = self.os_path.join(start, path)
358
359 owners_path = self.os_path.join(self.root, include_path)
360 if not self.os_path.exists(owners_path):
361 return None
362
363 return include_path
364
Dirk Pranke4dc849f2017-02-28 15:31:19 -0800365 def _read_just_the_owners(self, include_file):
366 if include_file in self._included_files:
367 return self._included_files[include_file]
368
369 owners = set()
370 self._included_files[include_file] = owners
371 lineno = 0
372 for line in self.fopen(self.os_path.join(self.root, include_file)):
373 lineno += 1
374 line = line.strip()
375 if (line.startswith('#') or line == '' or
376 line.startswith('set noparent') or
377 line.startswith('per-file')):
378 continue
379
380 if self.email_regexp.match(line) or line == EVERYONE:
381 owners.add(line)
382 continue
383 if line.startswith('file:'):
384 sub_include_file = self._resolve_include(line[5:], include_file)
385 sub_owners = self._read_just_the_owners(sub_include_file)
386 owners.update(sub_owners)
387 continue
388
389 raise SyntaxErrorInOwnersFile(include_file, lineno,
390 ('"%s" is not a "set noparent", file include, "*", '
391 'or an email address.' % (line,)))
392 return owners
393
dpranke@chromium.orgdbf8b4e2013-02-28 19:24:16 +0000394 def _covering_set_of_owners_for(self, files, author):
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000395 dirs_remaining = set(self._enclosing_dir_with_owners(f) for f in files)
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000396 all_possible_owners = self.all_possible_owners(dirs_remaining, author)
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000397 suggested_owners = set()
398 while dirs_remaining:
399 owner = self.lowest_cost_owner(all_possible_owners, dirs_remaining)
400 suggested_owners.add(owner)
401 dirs_to_remove = set(el[0] for el in all_possible_owners[owner])
402 dirs_remaining -= dirs_to_remove
403 return suggested_owners
dpranke@chromium.org5e5d37b2012-12-19 21:04:58 +0000404
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000405 def all_possible_owners(self, dirs, author):
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000406 """Returns a list of (potential owner, distance-from-dir) tuples; a
407 distance of 1 is the lowest/closest possible distance (which makes the
408 subsequent math easier)."""
409 all_possible_owners = {}
zork@chromium.org046e1752012-05-07 05:56:12 +0000410 for current_dir in dirs:
zork@chromium.org046e1752012-05-07 05:56:12 +0000411 dirname = current_dir
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000412 distance = 1
413 while True:
dtu944b6052016-07-14 14:48:21 -0700414 for owner in self._owners_for(dirname):
dpranke@chromium.orgdbf8b4e2013-02-28 19:24:16 +0000415 if author and owner == author:
416 continue
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000417 all_possible_owners.setdefault(owner, [])
418 # If the same person is in multiple OWNERS files above a given
419 # directory, only count the closest one.
420 if not any(current_dir == el[0] for el in all_possible_owners[owner]):
421 all_possible_owners[owner].append((current_dir, distance))
dtu944b6052016-07-14 14:48:21 -0700422 if self._should_stop_looking(dirname):
dpranke@chromium.org6dada4e2011-03-08 22:32:40 +0000423 break
424 dirname = self.os_path.dirname(dirname)
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000425 distance += 1
426 return all_possible_owners
zork@chromium.org046e1752012-05-07 05:56:12 +0000427
nick7e16cf32016-09-16 16:05:05 -0700428 def _fnmatch(self, filename, pattern):
429 """Same as fnmatch.fnmatch(), but interally caches the compiled regexes."""
430 matcher = self._fnmatch_cache.get(pattern)
431 if matcher is None:
432 matcher = re.compile(fnmatch.translate(pattern)).match
433 self._fnmatch_cache[pattern] = matcher
434 return matcher(filename)
435
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000436 @staticmethod
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000437 def total_costs_by_owner(all_possible_owners, dirs):
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000438 # We want to minimize both the number of reviewers and the distance
439 # from the files/dirs needing reviews. The "pow(X, 1.75)" below is
440 # an arbitrarily-selected scaling factor that seems to work well - it
441 # will select one reviewer in the parent directory over three reviewers
442 # in subdirs, but not one reviewer over just two.
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000443 result = {}
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000444 for owner in all_possible_owners:
445 total_distance = 0
446 num_directories_owned = 0
447 for dirname, distance in all_possible_owners[owner]:
448 if dirname in dirs:
449 total_distance += distance
450 num_directories_owned += 1
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000451 if num_directories_owned:
452 result[owner] = (total_distance /
453 pow(num_directories_owned, 1.75))
454 return result
zork@chromium.org046e1752012-05-07 05:56:12 +0000455
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000456 @staticmethod
457 def lowest_cost_owner(all_possible_owners, dirs):
458 total_costs_by_owner = Database.total_costs_by_owner(all_possible_owners,
459 dirs)
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000460 # Return the lowest cost owner. In the case of a tie, pick one randomly.
461 lowest_cost = min(total_costs_by_owner.itervalues())
462 lowest_cost_owners = filter(
ikarienator@chromium.orgfaf3fdf2013-09-20 02:11:48 +0000463 lambda owner: total_costs_by_owner[owner] == lowest_cost,
464 total_costs_by_owner)
dpranke@chromium.orgc591a702012-12-20 20:14:58 +0000465 return random.Random().choice(lowest_cost_owners)