[Findit] Initial code of findit for crash. Add scorers to apply heuristic rules.

appengine/findit/crash/findit_for_crash.py

+# Copyright 2016 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.
+
+from collections import defaultdict
+
+from common import chromium_deps
+from common.change_log import ChangeLog
+from common.git_repository import GitRepository
+from common.http_client_appengine import HttpClientAppengine
+from crash import crash_util
+from crash.results import MatchResult, MatchResults
+from crash.scorers.aggregator import Aggregator
+from crash.scorers.top_frame_index import TopFrameIndex
+from crash.scorers.min_distance import MinDistance
+
+
+def GetDepsInCrashStack(crash_stack, crash_deps):
+  """Gets Dependencies in crash stack."""
+  if not crash_stack:

[stgao, 2016/04/15 18:35:19]

It seems this is just one callstack, while a crash stack might include multiple
callstacks. We'd better use the terms consistently to avoid confusion. Maybe I'm
wrong with the terms too?

[Sharu, 2016/04/15 22:59:46]

crash_stack is one callstack, the one that has the highest priority and cause
the crash.

+    return {}
+
+  deps = set()
+  for frame in crash_stack:
+    deps.add(frame.dep_path)
+
+  stack_deps = {}
+  for dep in deps:

[stgao, 2016/04/15 18:35:19]

Can we merge these two for loop?

[Sharu, 2016/04/15 22:59:46]

Done.

+    stack_deps[dep] = crash_deps[dep]
+
+  return stack_deps
+
+
+def GetDepFileToChangeLogsAndIgnoreCls(regression_deps_rolls, stack_deps):
+  """For those deps we concern, gets a dict containing all the files touched by
+  changelogs in regressoin range and a set of revisions that should be ignored.
+
+  Args:
+    regression_deps_rolls (dict): Maps dep_path to DependencyRoll in
+      regression range.
+    stack_deps (dict): Represents all the dependencies show in
+      the crash stack.
+
+  Returns:
+    A tuple (dep_file_to_changelogs, ignore_cls).
+
+    dep_file_to_changelogs (dict): Maps dep_path to a dict mapping file path
+      to ChangeLogs that touched this file.
+
+    For example:
+    {
+        'src/': {
+            'a.cc': [
+                ChangeLog.FromDict({
+                    'author_name': 'test@chromium.org',
+                    'message': 'dummy',
+                    'committer_email': 'example@chromium.org',
+                    'commit_position': 175976,
+                    'author_email': 'example@chromium.org',
+                    'touched_files': [
+                        {
+                            'change_type': 'add',
+                            'new_path': 'a.cc',
+                            'old_path': 'b/a.cc'
+                        },
+                        ...
+                    ],
+                    'author_time': 'Thu Mar 31 21:24:43 2016',
+                    'committer_time': 'Thu Mar 31 21:28:39 2016',
+                    'commit_url':
+                        'https://repo.test/+/bcfd',
+                    'code_review_url': 'https://codereview.chromium.org/3281',
+                    'committer_name': 'example@chromium.org',
+                    'revision': 'bcfd',
+                    'reverted_revision': None
+                }),
+            ]
+        }
+    }
+
+    ignore_cls (set): A set of reverted revisions.
+  """
+  dep_file_to_changelogs = defaultdict(lambda: defaultdict(list))
+

[Martin Barbella, 2016/04/15 06:05:24]

Nit: Remove this whitespace and the one on 88.

[Sharu, 2016/04/15 22:59:46]

Done.

+  ignore_cls = set()
+
+  for dep in stack_deps:
+
+    dep_roll = regression_deps_rolls[dep]
+
+    git_parser = GitRepository(dep_roll['repo_url'], HttpClientAppengine())
+    changelogs = git_parser.GetChangeLogs(dep_roll['old_revision'],
+                                          dep_roll['new_revision'])
+
+    for changelog in changelogs:
+      for touched_file in changelog.touched_files:
+        # If a dependency is deleted or is a .h file, skip this changelog.

[Martin Barbella, 2016/04/15 06:05:24]

s/skip this changelog/skip this file/ right?

[Sharu, 2016/04/15 22:59:46]

Right, done.

+        if not touched_file.new_path or touched_file.new_path.endswith('.h'):

[stgao, 2016/04/15 18:35:18]

Can we use the change_type instead?

https://chromium.googlesource.com/infra/infra/+/master/appengine/findit/commo...

[Sharu, 2016/04/15 22:59:46]

Done.

+          continue
+
+        if changelog.reverted_revision:

[stgao, 2016/04/15 18:35:19]

Should this be in this inner for loop?

[Sharu, 2016/04/15 22:59:47]

Ouch, done.

+          # Add reverted revisions to ignore_cls to filter those reverted
+          # revisions later while matching cls.
+          ignore_cls.add(changelog.reverted_revision)

[stgao, 2016/04/15 18:35:19]

Should we including the reverting cl too?

[Sharu, 2016/04/15 22:59:46]

I didn't add the reverting cls in dep_file_to_changelogs, so I didn't add it.

[stgao, 2016/04/20 17:41:25]

What if the reverting CLs showing up in the regression range?

[Sharu Jiang, 2016/04/20 18:54:23]

All the changelogs in the regression range we are interested in are stored in
dep_to_file_to_changelogs. If I didn't include those reverting cls in
dep_to_file_to_changelogs, it won't show anywhere afterward, I think it won't be
a problem.

+          continue
+
+        dep_file_to_changelogs[dep][touched_file.new_path].append(changelog)
+
+  return dep_file_to_changelogs, ignore_cls
+
+
+def GetDepFileToStackInfos(stacktrace):
+  """Gets a dict containing all the stack information of files in stacktrace.
+
+  Args:
+    stacktrace (Stacktrace): Parsed stacktrace object.
+
+  Returns:
+    A dict, maps dep path to a dict mapping file path to a list of stack
+    inforamtion of this file. A file may occur in several frames, one stack info
+    consist of a StackFrame and the callstack priority of it.
+
+    For example:
+    {
+        'src/': {
+            'a.cc': [
+                (StackFrame(0, 'src/', '', 'func', 'a.cc', [1]), 0),
+                (StackFrame(2, 'src/', '', 'func', 'a.cc', [33]), 0),
+            ]
+        }
+    }
+  """
+  dep_file_to_stack_infos = defaultdict(lambda: defaultdict(list))
+
+  for callstack in stacktrace:
+    for frame in callstack:
+      if frame.file_path.endswith('.h'):
+        continue
+
+      dep_file_to_stack_infos[frame.dep_path][frame.file_path].append((
+          frame, callstack.priority))
+
+  return dep_file_to_stack_infos
+
+
+def GetDepFileToBlame(stacktrace, stack_deps):

[stgao, 2016/04/15 18:35:19]

What does "DepFile" mean here? The DEPS file?

[Sharu, 2016/04/15 22:59:47]

I wanted to mean a dict[dep_path][file_path] = Blame ... Cannot think of a
better name without being too long, any suggestion?

+  """Gets Blames for files in stacktrace.
+
+  Args:
+    stacktrace (Stacktrace): Parsed stacktrace object.
+    stack_deps (dict of Dependencys): Represents all the dependencies shown in
+      the crash stack.
+
+  Returns:
+    A dict, maps dep_path to a dict mapping file path to its Blame.
+
+    For example:
+    {
+        'src/': {
+            'a.cc': Blame(revision, 'a.cc')
+            'b.cc': Blame(revision, 'b.cc')
+        }
+    }
+  """
+  dep_file_to_blame = defaultdict(dict)
+  for callstack in stacktrace:
+    for frame in callstack:
+      # We only care about those dependencies in crash stack.
+      if frame.dep_path not in stack_deps:
+        continue
+
+      git_parser = GitRepository(stack_deps[frame.dep_path].repo_url,

[stgao, 2016/04/15 18:35:19]

naming nit: it's not just a parser.

[Sharu, 2016/04/15 22:59:47]

Done.

+                                 HttpClientAppengine())
+      dep_file_to_blame[frame.dep_path][frame.file_path] = (
+          git_parser.GetBlame(
+              frame.file_path, stack_deps[frame.dep_path].revision))
+  return dep_file_to_blame
+
+
+def FindMatchResults(dep_file_to_changelogs,
+                     dep_file_to_stack_infos,
+                     dep_file_to_blame,
+                     ignore_cls=None):
+  """Finds culprit results by matching stacktrace and changelogs in regression
+  range. This method only applies to those crashes with regression range.
+
+  Args:
+    dep_file_to_changelogs (dict): Maps dep_path to a dict mapping file path
+      to ChangeLogs that touched this file.
+
+    dep_file_to_stack_infos (dict): Maps dep path to a dict mapping file path
+      to a list of stack inforamtion of this file. A file may occur in several
+      frames, one stack info consist of a StackFrame and the callstack priority
+      of it.
+
+    dep_file_to_blame (dict): Maps dep_path to a dict mapping file path to
+    its Blame.
+
+    ignore_cls (set): Set of reverted revisions.
+
+  Returns:
+    A list of MatchResult instances with confidence and reason unset.
+  """
+  match_results = MatchResults(ignore_cls)
+
+  for dep, file_to_stack_infos in dep_file_to_stack_infos.iteritems():
+    for crashed_file_path, stack_infos in file_to_stack_infos.iteritems():
+
+      file_to_changelogs = dep_file_to_changelogs[dep]
+      for touched_file_path, changelogs in file_to_changelogs.iteritems():
+        if not crash_util.IsSameFilePath(crashed_file_path, touched_file_path):

[stgao, 2016/04/15 18:35:18]

Note: syzyasan has lower case file path in ClusterFuzz.

[Sharu, 2016/04/15 22:59:47]

Modified this inside IsSameFilePath function

+          continue
+
+        match_results.GenerateMatchResults(
+            crashed_file_path, dep, stack_infos, changelogs,
+            dep_file_to_blame[dep][crashed_file_path])
+
+  return match_results.values()
+
+
+def FindItForCrash(stacktrace, regression_range, crash_revision):
+  """Finds culprit results for crash.
+
+  Args:
+    stacktrace (Stactrace): Parsed Stactrace object.
+    regression_range (tuple or None): A tuple of githash strs -
+      (start_revision, end_revision), None if no regression range provided.
+    crash_revision (str): The crashed revision githash str.
+
+  Returns:
+    List of dicts of culprit results, sorted by confidence from highest to
+    lowest.
+  """
+
+  if not regression_range:
+    return []
+
+  start_revision, end_revision = regression_range

[stgao, 2016/04/15 18:35:19]

good_revision, bad_revision?

[Sharu, 2016/04/15 22:59:46]

Done.

+
+  # Get regression deps and crash deps.
+  # Right now we only care about those deps for all platforms.
+  regression_deps_rolls = chromium_deps.GetDEPSRollsDict(
+      start_revision, end_revision, 'all')

[stgao, 2016/04/15 18:35:19]

Why 'all' instead of the specific os platform?

[Sharu, 2016/04/15 22:59:46]

I was supposed to set it to None :( 

Changed it.

[stgao, 2016/04/20 17:41:25]

Why set it to None?

[Sharu Jiang, 2016/04/20 18:54:24]

It's a mistake :(

+  crash_deps = chromium_deps.GetChromeDependency(crash_revision, 'all')
+
+  crash_stack = stacktrace.GetCrashStack()
+  stack_deps = GetDepsInCrashStack(crash_stack, crash_deps)
+
+  # Get dep and file to changelogs, stack_info and blame dicts.
+  dep_file_to_changelogs, ignore_cls = GetDepFileToChangeLogsAndIgnoreCls(
+      regression_deps_rolls, stack_deps)
+  dep_file_to_stack_infos = GetDepFileToStackInfos(stacktrace)
+  dep_file_to_blame = GetDepFileToBlame(stacktrace, stack_deps)
+
+  results = FindMatchResults(dep_file_to_changelogs,
+                             dep_file_to_stack_infos,
+                             dep_file_to_blame,
+                             ignore_cls)
+
+  if not results:
+    return []
+
+  aggregator = Aggregator([TopFrameIndex(), MinDistance()])
+
+  map(aggregator.ScoreAndReason, results)
+
+  return sorted([result.ToDict() for result in results],
+                key=lambda r: -r['confidence'])