Enforce LGTM from owners of depends-on paths in DEPS via presubmit.

This presubmit check has been copied from Chromium's PRESUBMIT.py [1].

Example of the error message:

** Presubmit ERRORS **
You need LGTM from owners of depends-on paths in DEPS that were modified in this CL:
    '+third_party/protobuf/src/google/protobuf',

Suggested missing target path OWNERS:
...

[1] - https://cs.chromium.org/chromium/src/PRESUBMIT.py?l=1475-1550&rcl=57cc805bba436b3f26b86168628a343be8abe2a3

Bug: webrtc:9453
Change-Id: Icc028bcd1d48b83f2f31bb821c708289eebd8623
Reviewed-on: https://webrtc-review.googlesource.com/95885
Commit-Queue: Mirko Bonadei <mbonadei@webrtc.org>
Reviewed-by: Patrik Höglund <phoglund@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#24891}
diff --git a/PRESUBMIT.py b/PRESUBMIT.py
index ae5303d..242e557 100755
--- a/PRESUBMIT.py
+++ b/PRESUBMIT.py
@@ -859,6 +859,7 @@
       input_api, output_api, source_file_filter=non_third_party_sources))
   results.extend(CheckNoStreamUsageIsAdded(
       input_api, output_api, non_third_party_sources))
+  results.extend(CheckAddedDepsHaveTargetApprovals(input_api, output_api))
   return results
 
 
@@ -930,3 +931,151 @@
       if len(lines) > 0 and not lines[-1].endswith('\n'):
         results.append(output_api.PresubmitError(error_msg.format(file_path)))
   return results
+
+
+def _ExtractAddRulesFromParsedDeps(parsed_deps):
+  """Extract the rules that add dependencies from a parsed DEPS file.
+
+  Args:
+    parsed_deps: the locals dictionary from evaluating the DEPS file."""
+  add_rules = set()
+  add_rules.update([
+      rule[1:] for rule in parsed_deps.get('include_rules', [])
+      if rule.startswith('+') or rule.startswith('!')
+  ])
+  for _, rules in parsed_deps.get('specific_include_rules',
+                                              {}).iteritems():
+    add_rules.update([
+        rule[1:] for rule in rules
+        if rule.startswith('+') or rule.startswith('!')
+    ])
+  return add_rules
+
+
+def _ParseDeps(contents):
+  """Simple helper for parsing DEPS files."""
+  # Stubs for handling special syntax in the root DEPS file.
+  class VarImpl(object):
+
+    def __init__(self, local_scope):
+      self._local_scope = local_scope
+
+    def Lookup(self, var_name):
+      """Implements the Var syntax."""
+      try:
+        return self._local_scope['vars'][var_name]
+      except KeyError:
+        raise Exception('Var is not defined: %s' % var_name)
+
+  local_scope = {}
+  global_scope = {
+      'Var': VarImpl(local_scope).Lookup,
+  }
+  exec contents in global_scope, local_scope
+  return local_scope
+
+
+def _CalculateAddedDeps(os_path, old_contents, new_contents):
+  """Helper method for _CheckAddedDepsHaveTargetApprovals. Returns
+  a set of DEPS entries that we should look up.
+
+  For a directory (rather than a specific filename) we fake a path to
+  a specific filename by adding /DEPS. This is chosen as a file that
+  will seldom or never be subject to per-file include_rules.
+  """
+  # We ignore deps entries on auto-generated directories.
+  auto_generated_dirs = ['grit', 'jni']
+
+  old_deps = _ExtractAddRulesFromParsedDeps(_ParseDeps(old_contents))
+  new_deps = _ExtractAddRulesFromParsedDeps(_ParseDeps(new_contents))
+
+  added_deps = new_deps.difference(old_deps)
+
+  results = set()
+  for added_dep in added_deps:
+    if added_dep.split('/')[0] in auto_generated_dirs:
+      continue
+    # Assume that a rule that ends in .h is a rule for a specific file.
+    if added_dep.endswith('.h'):
+      results.add(added_dep)
+    else:
+      results.add(os_path.join(added_dep, 'DEPS'))
+  return results
+
+
+def CheckAddedDepsHaveTargetApprovals(input_api, output_api):
+  """When a dependency prefixed with + is added to a DEPS file, we
+  want to make sure that the change is reviewed by an OWNER of the
+  target file or directory, to avoid layering violations from being
+  introduced. This check verifies that this happens.
+  """
+  virtual_depended_on_files = set()
+
+  file_filter = lambda f: not input_api.re.match(
+      r"^third_party[\\\/](WebKit|blink)[\\\/].*", f.LocalPath())
+  for f in input_api.AffectedFiles(include_deletes=False,
+                                   file_filter=file_filter):
+    filename = input_api.os_path.basename(f.LocalPath())
+    if filename == 'DEPS':
+      virtual_depended_on_files.update(_CalculateAddedDeps(
+          input_api.os_path,
+          '\n'.join(f.OldContents()),
+          '\n'.join(f.NewContents())))
+
+  if not virtual_depended_on_files:
+    return []
+
+  if input_api.is_committing:
+    if input_api.tbr:
+      return [output_api.PresubmitNotifyResult(
+          '--tbr was specified, skipping OWNERS check for DEPS additions')]
+    if input_api.dry_run:
+      return [output_api.PresubmitNotifyResult(
+          'This is a dry run, skipping OWNERS check for DEPS additions')]
+    if not input_api.change.issue:
+      return [output_api.PresubmitError(
+          "DEPS approval by OWNERS check failed: this change has "
+          "no change number, so we can't check it for approvals.")]
+    output = output_api.PresubmitError
+  else:
+    output = output_api.PresubmitNotifyResult
+
+  owners_db = input_api.owners_db
+  owner_email, reviewers = (
+      input_api.canned_checks.GetCodereviewOwnerAndReviewers(
+        input_api,
+        owners_db.email_regexp,
+        approval_needed=input_api.is_committing))
+
+  owner_email = owner_email or input_api.change.author_email
+
+  reviewers_plus_owner = set(reviewers)
+  if owner_email:
+    reviewers_plus_owner.add(owner_email)
+  missing_files = owners_db.files_not_covered_by(virtual_depended_on_files,
+                                                 reviewers_plus_owner)
+
+  # We strip the /DEPS part that was added by
+  # _FilesToCheckForIncomingDeps to fake a path to a file in a
+  # directory.
+  def StripDeps(path):
+    start_deps = path.rfind('/DEPS')
+    if start_deps != -1:
+      return path[:start_deps]
+    else:
+      return path
+  unapproved_dependencies = ["'+%s'," % StripDeps(path)
+                             for path in missing_files]
+
+  if unapproved_dependencies:
+    output_list = [
+      output('You need LGTM from owners of depends-on paths in DEPS that were '
+             'modified in this CL:\n    %s' %
+                 '\n    '.join(sorted(unapproved_dependencies)))]
+    suggested_owners = owners_db.reviewers_for(missing_files, owner_email)
+    output_list.append(output(
+        'Suggested missing target path OWNERS:\n    %s' %
+            '\n    '.join(suggested_owners or [])))
+    return output_list
+
+  return []