[Findit] findit algorithms and a cluster-fuzz implementation.

tools/findit/findit_for_crash.py

Index: tools/findit/findit_for_crash.py
diff --git a/tools/findit/findit_for_crash.py b/tools/findit/findit_for_crash.py
new file mode 100644
index 0000000000000000000000000000000000000000..7c3f3453ec96583ef8fe6c5e1ccd888f87a27ea7
--- /dev/null
+++ b/tools/findit/findit_for_crash.py
@@ -0,0 +1,645 @@
+# Copyright (c) 2014 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.
+
+import os
+from threading import Lock, Thread
+
+import blame
+from common import utils
+import component_dictionary
+import crash_utils
+import git_repository_parser
+import match_set
+import svn_repository_parser
+
+
+LINE_CHANGE_PRIORITY = 1
+FILE_CHANGE_PRIORITY = 2
+_THIS_DIR = os.path.abspath(os.path.dirname(__file__))
+CONFIG = crash_utils.ParseURLsFromConfig(os.path.join(_THIS_DIR,
+                                                      'config.ini'))
+
+
+def GenerateMatchEntry(
+    matches, revision_info, revision_number, file_path, function,
+    component_path, component_name, crashed_line_numbers, stack_frame_indices,
+    file_change_type, repository_parser):
+  """Generates a match object and adds it to the match set.
+
+  Args:
+    matches: A matchset object, a map from CL to a match object.
+    revision_info: The revision information, a map from fields (message,
+                   changed files, etc) to its values.
+    revision_number: The SVN revision number or git hash.
+    file_path: The path of the file.
+    function: The function that caused an crash.
+    component_path: The path of the component this file is from.
+    component_name: The name of the component the file is from.
+    crashed_line_numbers: The list of the lines in the file that caused
+                          the crash.
+    stack_frame_indices: The list of positions of this file within a stack.
+    file_change_type: Whether file is modified, added or deleted.
+    repository_parser: The parser object to parse line diff.
+  """
+  # Check if this CL should be ignored.
+  with matches.matches_lock:
+    if revision_number in matches.cls_to_ignore:
+      return
+
+    # If this CL is not already identified as suspected, create a new entry.
+    if revision_number not in matches.matches:
+      match = match_set.Match(revision_info, component_name)
+      message = revision_info['message']
+      # TODO(jeun): Don't hold lock while issuing http request.
+      match.ParseMessage(message, matches.codereview_api_url)
+
+      # If this match is a revert, add to the set of CLs to be ignored.
+      if match.is_reverted:

[Martin Barbella, 2014/08/19 16:11:33]

s/is_reverted/is_revert/

[jeun, 2014/08/19 18:30:06]

Done.

+        matches.cls_to_ignore.add(revision_number)
+
+        # If this match has info on what CL it is reverted from, add that CL.
+        if match.revert_of:
+          matches.cls_to_ignore.add(match.revert_of)
+
+        # Return because we do not need to look at this CL anymore.
+        return
+
+      # Add this CL to the set of matches.
+      matches.matches[revision_number] = match
+
+    # Else, bring in the existing result.
+    else:
+      match = matches.matches[revision_number]
+
+  # Parse line diff information for this file.
+  (diff_url, changed_line_numbers, changed_line_contents) = (
+      repository_parser.ParseLineDiff(
+          file_path, component_path, file_change_type, revision_number))
+
+  # Ignore this match if the component is not supported for svn.

[Martin Barbella, 2014/08/19 16:11:33]

Is this correct? If so, is there more work that needs to be done here?

[jeun, 2014/08/19 18:30:06]

Yes this is correct, for SVN we need to write a parser for googlecode (v8 and
others). But assuming that they will show git hash eventually, I don't think it
is too much of a problem?

+  if not diff_url:
+    return
+
+  # Find the intersection between the lines that this file crashed on and
+  # the changed lines.
+  (line_number_intersection, stack_frame_index_intersection) = (
+      crash_utils.Intersection(
+          crashed_line_numbers, stack_frame_indices, changed_line_numbers))
+
+  # Find the minimum distance between the changed lines and crashed lines.
+  min_distance = crash_utils.FindMinLineDistance(crashed_line_numbers,
+                                                 changed_line_numbers)
+
+  # Check whether this CL changes the crashed lines or not.
+  if line_number_intersection:
+    priority = LINE_CHANGE_PRIORITY
+  else:
+    priority = FILE_CHANGE_PRIORITY
+
+  # Add the parsed information to the object.
+  with matches.matches_lock:
+    match.crashed_line_numbers.append(line_number_intersection)
+
+    file_name = os.path.basename(file_path)

[Martin Barbella, 2014/08/19 16:11:33]

Could you confirm that this works on Windows? The stacks will still contain
forward slashes.

[jeun, 2014/08/19 18:30:06]

Changed all occurrences to file_path.split('/')[-1]. All path should be in linux
path when this is called elsewhere, so this should work everywhere.

+    match.changed_files.append(file_name)
+
+    # Update the min distance only if it is less than the current one.
+    if min_distance < match.min_distance:
+      match.min_distance = min_distance
+
+    # If this CL does not change the crashed line, all occurrence of this
+    # file in the stack has the same priority.
+    if not stack_frame_index_intersection:
+      stack_frame_index_intersection = stack_frame_indices
+    match.stack_frame_indices.append(stack_frame_index_intersection)
+    match.changed_file_urls.append(diff_url)
+    match.priorities.append(priority)
+    match.function_list.append(function)
+
+
+def FindMatch(revisions_info_map, file_to_revision_info, file_to_crash_info,
+              component_path, component_name, repository_parser,
+              codereview_api_url):
+  """Finds a CL that modifies file in the stacktrace.
+
+  Args:
+    revisions_info_map: A dictionary mapping revision number to the CL
+                        information.
+    file_to_revision_info: A dictionary mapping file to the revision that
+                           modifies it.
+    file_to_crash_info: A dictionary mapping file to its occurrence in
+                       stacktrace.
+    component_path: The path of the component to search for.
+    component_name: The name of the component to search for.
+    repository_parser: The parser object to parse the line diff.
+    codereview_api_url: A code review url to retrieve data from.
+
+  Returns:
+    Matches, a set of match objects.
+  """
+  matches = match_set.MatchSet(codereview_api_url)
+  threads = []
+
+  # For all files in stacktrace, if it is not header file, check against
+  # all CLs to see if any CL changes this file. If so, add to the set of
+  # suspected CLs.
+  for crashed_file_path in file_to_crash_info:
+    # Ignore header file.
+    if crashed_file_path.endswith('.h'):
+      continue
+
+    # If the file in the stacktrace is not changed in any commits, continue.
+    for changed_file_path in file_to_revision_info:
+      changed_file_name = os.path.basename(changed_file_path)
+      crashed_file_name = os.path.basename(crashed_file_path)
+
+      # If the two file path does not have the same file name, continue.
+      if changed_file_name != crashed_file_name:
+        continue
+
+      # If the path of the two files are not same, continue.
+      if not crash_utils.GuessIfSameSubPath(
+          changed_file_path, crashed_file_path):
+        continue
+
+      crashed_line_numbers = file_to_crash_info.GetCrashedLineNumbers(
+          crashed_file_path)
+      stack_frame_nums = file_to_crash_info.GetCrashStackFrameIndices(
+          crashed_file_path)
+      functions = file_to_crash_info.GetCrashFunctions(crashed_file_path)
+
+      # Iterate through the CLs that this file path is changed.
+      for (cl, file_change_type) in file_to_revision_info[changed_file_path]:
+        # If the file change is delete, ignore this CL.
+        if file_change_type == 'D':

[Martin Barbella, 2014/08/19 16:11:32]

Should this be startswith('D'), or are other parts of the status ignored before
we get to this point? I'm not sure how often this would come up either way.

[jeun, 2014/08/19 18:30:06]

Yes the other parts are ignored when the check happens. In blame, it returns
'delete', so I make it into 'D'.

+          continue
+
+        revision = revisions_info_map[cl]
+
+        match_thread = Thread(
+            target=GenerateMatchEntry,
+            args=[matches, revision, cl, changed_file_path, functions,
+                  component_path, component_name, crashed_line_numbers,
+                  stack_frame_nums, file_change_type,
+                  repository_parser])
+        threads.append(match_thread)
+        match_thread.start()
+
+  # Make sure all threads finish before returning.
+  for match_thread in threads:
+    match_thread.join()
+
+  # Remove CLs that are revert.
+  matches.RemoveRevertedCLs()
+
+  return matches
+
+
+def FindMatchForComponent(component_path, file_to_crash_info, changelog,
+                          callstack_priority, results, results_lock):
+  """Parses changelog and finds suspected CLs for a given component.
+
+  Args:
+    component_path: The path of component to look for the culprit CL.
+    file_to_crash_info: A dictionary mapping file to its occurrence in
+                        stackframe.
+    changelog: The parsed changelog for this component.
+    callstack_priority: The priority of this call stack, 0 if from crash stack,
+                        1 if from freed, 2 if from previously allocated.
+    results: A dictionary to store the result.
+    results_lock: A lock that guards results.
+  """
+  (repository_parser, component_name, revisions, file_to_revision_map) = \
+      changelog
+
+  # Find match for this component.
+  codereview_api_url = CONFIG['codereview']['review_url']
+  component_result = FindMatch(
+      revisions, file_to_revision_map, file_to_crash_info, component_path,
+      component_name, repository_parser, codereview_api_url)
+  matches = component_result.matches
+
+  # For all the match results in a dictionary, add to the list so that it
+  # can be sorted.
+  with results_lock:
+    for cl in matches:
+      match = matches[cl]
+      results.append((callstack_priority, cl, match))
+
+
+def FindMatchForCallstack(
+    callstack, components, component_to_changelog_map, results,
+    results_lock):
+  """Finds culprit cl for a stack within a stacktrace.
+
+  For each components to look for, create new thread that computes the matches
+  and join the results at the end.
+
+  Args:
+    callstack: A callstack in a stacktrace to find the result for.
+    components: A set of components to look for.
+    component_to_changelog_map: A map from component to its parsed changelog.
+    results: A list to aggregrate results from all stacktraces.
+    results_lock: A lock that guards results.
+  """
+  # Create component dictionary from the component and call stack.
+  component_dict = component_dictionary.ComponentDictionary(callstack,
+                                                            components)
+  callstack_priority = callstack.priority
+
+  # Iterate through all components and create new thread for each component.
+  threads = []
+  for component_path in component_dict:
+    # If the component to consider in this callstack is not in the parsed list
+    # of components, ignore this one.
+    if component_path not in component_to_changelog_map:
+      continue
+
+    changelog = component_to_changelog_map[component_path]
+    file_to_crash_info = component_dict.GetFileDict(component_path)
+    t = Thread(
+        target=FindMatchForComponent,
+        args=[component_path, file_to_crash_info, changelog,
+              callstack_priority, results, results_lock])
+    threads.append(t)
+    t.start()
+
+  # Join the threads before returning.
+  for t in threads:
+    t.join()
+
+
+def FindMatchForStacktrace(stacktrace, components,
+                           component_to_regression_dict):
+  """Finds the culprit CL for stacktrace.
+
+  The passed stacktrace is either from release build stacktrace
+  or debug build stacktrace.
+
+  Args:
+    stacktrace: A list of parsed stacks within a stacktrace.
+    components: A set of components to look for.
+    component_to_regression_dict: A dictionary mapping component path to
+                                  its regression.
+
+  Returns:
+    A list of match results from all stacks.
+  """
+  # A list to aggregate results from all the callstacks in the stacktrace.
+  results = []
+  results_lock = Lock()
+
+  # Parse changelog for each of the components and store it.
+  svn_parser = svn_repository_parser.SVNParser(CONFIG['svn'])
+  git_parser = git_repository_parser.GitParser(component_to_regression_dict,
+                                               CONFIG['git'])
+
+  component_to_changelog_map = {}
+  for component_path in components:
+    component_object = component_to_regression_dict[component_path]
+    range_start = component_object['old_revision']
+    range_end = component_object['new_revision']
+
+    # If range start is 0, it means regression is not reliable, so ignore.

[Martin Barbella, 2014/08/19 16:11:32]

Again, 0 isn't about reliability. It just means that the crash was introduced
before the archived builds. It makes sense to continue in this case since the
range is so large, but please update the comment.

[jeun, 2014/08/19 18:30:06]

Done.

+    if range_start == '0':
+      continue
+
+    component_name = component_to_regression_dict[component_path]['name']
+
+    # Check if the regression is git hash or a revision number, and create
+    # appropriate parser object.
+    is_git = utils.IsGitHash(range_start)
+    if is_git:
+      repository_parser = git_parser
+    else:
+      repository_parser = svn_parser
+
+    # Parse revisions and changed files in regression.
+    (revisions, file_to_revision_map) = repository_parser.ParseChangelog(
+        component_path, range_start, range_end)
+
+    # If the returned map from ParseChangeLog is empty, we don't need to look
+    # further because either the parsing failed or the changelog is empty.
+    if not (revisions and file_to_revision_map):
+      continue
+
+    component_to_changelog_map[component_path] = (repository_parser,
+                                                  component_name,
+                                                  revisions,
+                                                  file_to_revision_map)
+
+  # Create separate threads for each of the call stack in the stacktrace.
+  threads = []
+  for callstack in stacktrace.stack_list:
+    t = Thread(
+        target=FindMatchForCallstack,
+        args=[callstack, components, component_to_changelog_map,
+              results, results_lock])
+    threads.append(t)
+    t.start()
+
+  # Join the threads before returning.
+  for t in threads:
+    t.join()
+
+  return results
+
+
+def SortAndFilterMatches(matches, num_important_frames=5):
+  """Filters the list of potential culprit CLs to remove noise.
+
+  Args:
+    matches: A list containing match results.
+    num_important_frames: A number of frames on the top of the frame to Check
+                          for when filtering the results. A match with a file
+                          that is in top num_important_frames of the stacktrace
+                          is regarded more probable then others.
+
+  Returns:
+    Filtered match results.
+  """
+  new_matches = []
+  line_changed = False
+  is_important_frame = False
+  highest_priority_stack = crash_utils.INFINITY
+
+  # Sort the matches in specific order. It is sorted by
+  # 1) The highest priority file change in the CL (changing crashed line is
+  # higher priority than just changing the file)
+  # 2) The callstack this match is computed (crash stack, freed, allocation)

[Martin Barbella, 2014/08/19 16:11:33]

Was this updated so that free/allocation stacks have the same priority? If so,
using the name stack_index below might not make sense. Maybe stack_priority?

[jeun, 2014/08/19 18:30:06]

Yes it has been updated. I changed the name to stack_priority.

+  # 3) The minimum stack frame number of the changed file in the match
+  # 4) The number of files this CL changes (higher the better)
+  # 5) The minimum distance between the lines that the CL changes and crashed
+  # lines
+  matches.sort(key=lambda (stack_index, cl, match):

[Martin Barbella, 2014/08/19 16:11:33]

Using a lambda here is pretty ugly. Please just define a function for this and
move the comment explaining the sort priority to there.

[jeun, 2014/08/19 18:30:06]

Done.

+               (min(match.priorities), stack_index,
+                crash_utils.FindMinStackFrameNumber(match.stack_frame_indices,
+                                                    match.priorities),
+                -len(match.changed_files), match.min_distance))
+
+  # Iterate through the matches to find out what results are significant.
+  for stack_index, cl, match in matches:
+    # Check if the current match changes crashed line.
+    is_line_change = (min(match.priorities) == LINE_CHANGE_PRIORITY)
+
+    # Check which stack this match is from, and finds the highest priority
+    # callstack up to this point.
+    current_stack = stack_index
+    if current_stack < highest_priority_stack:
+      highest_priority_stack = current_stack
+
+    # Check if current match changes a file that occurs in crash state.
+    flattened_stack_frame_indices = [frame for frame_indices in
+                                     match.stack_frame_indices
+                                     for frame in frame_indices]
+    current_is_important = (
+        min(flattened_stack_frame_indices) < num_important_frames)
+
+    # This match and anything lower than this should be ignored if:
+    # - Current match does not change crashed lines but there are matches
+    # that do so.
+    # - Current match is not in crash state but there are matches in it.
+    # - There are other matches that came from higher priority stack.
+    if (line_changed and not is_line_change) or (
+        is_important_frame and not current_is_important) or (
+            current_stack > highest_priority_stack):
+      break
+
+    # Update the variables.
+    if is_line_change:
+      line_changed = True
+    if current_is_important:
+      is_important_frame = True
+
+    # Add current match to the filtered result.
+    new_matches.append((stack_index, cl, match))
+
+  return new_matches
+
+
+def GenerateReasonForMatches(matches):
+  """Generates a reason that a match (CL) is a culprit cl.
+
+  Args:
+    matches: A list of match objects.
+  """
+  # Iterate through the matches in the list.
+  for i, _, match in matches:
+    reason = []
+
+    # Zip the files in the match by the reason they are suspected
+    # (how the file is modified).
+    match_by_priority = zip(
+        match.priorities, match.crashed_line_numbers, match.changed_files,
+        match.changed_file_urls)
+
+    # Sort the zipped changed files in the match by their priority so that the
+    # changed lines comes first in the reason.
+    match_by_priority.sort(
+        key=lambda (priority, crashed_line_number, file_name, url): priority)
+
+    # Iterate through the sorted match.
+    for i in range(len(match_by_priority)):
+      (priority, crashed_line_number, file_name, file_url) = \
+          match_by_priority[i]
+
+      # If the file in the match is a line change, append a explanation.
+      if priority == LINE_CHANGE_PRIORITY:
+        reason.append(
+            'Line %s of file %s      which caused the crash according '

[Martin Barbella, 2014/08/19 16:11:33]

I'm not sure about saying "caused the crash" here. It sounds certain. Maybe
"potentially caused the crash".

[jeun, 2014/08/19 18:30:06]

Done.

+            'to the stacktrace, is changed in this cl.\n' %
+            (crash_utils.PrettifyList(crashed_line_number),
+             crash_utils.PrettifyFiles([(file_name, file_url)])))
+
+      else:
+        # Get all the files that are not line change.
+        rest_of_the_files = match_by_priority[i:]
+
+        # Take care of single/multiple files in string.
+        if len(rest_of_the_files) == 1:
+          file_string = 'File %s      is changed in this cl.\n'
+        else:
+          file_string = 'Files %s      are changed in this cl.\n'
+
+        # Create a list of file name and its url, and prettify the list.
+        file_name_with_url = [(file_name, file_url)
+                              for (_, _, file_name, file_url)
+                              in rest_of_the_files]
+        pretty_file_name_url = crash_utils.PrettifyFiles(file_name_with_url)
+
+        # Add the reason, break because we took care of the rest of the files.
+        reason.append(file_string % pretty_file_name_url)
+        break
+
+    # Set the reason as string.
+    match.reason = ''.join(reason)
+
+
+def CombineMatches(matches):
+  """Combine possible duplicates in matches.
+
+  Args:
+    matches: A list of matches object, along with its callstack priority and
+             CL it is from.
+  Returns:
+    A combined list of matches.
+  """
+  combined_matches = []
+
+  for stack_index, cl, match in matches:
+    found_match = None
+
+    # Iterate through the list of combined matches.
+    for _, cl_combined, match_combined in combined_matches:
+      # Check for if current match is already higher up in the result.
+      if cl == cl_combined:
+        found_match = match_combined
+        break
+
+    # If current match is not already in, add it to the list of matches.

[Martin Barbella, 2014/08/19 16:11:33]

In general, I think this file had a lot of unnecessary comments. This is one
example.

[jeun, 2014/08/19 18:30:06]

I removed a lot of self-explanatory comments.

+    if not found_match:
+      combined_matches.append((stack_index, cl, match))
+      continue
+
+    # Combine the reason if the current match is already in there.
+    found_match.reason += match.reason
+
+  return combined_matches
+
+
+def FilterAndGenerateReasonForMatches(result):
+  """A wrapper function.
+
+  It generates reasons for the matches and returns string representation
+  of filtered results.
+
+  Args:
+    result: A list of match objects.
+
+  Returns:
+    A string representation of filtered results.
+  """
+  new_result = SortAndFilterMatches(result)
+  GenerateReasonForMatches(new_result)
+  combined_matches = CombineMatches(new_result)
+  return crash_utils.MatchListToResultList(combined_matches)
+
+
+def ParseCrashComponents(main_stack, top_n_frames=3):
+  """Parses the crashing component.
+
+  Crashing components is a component that top_n_frames of the stacktrace is
+  from.
+
+  Args:
+    main_stack: Main stack from the stacktrace.
+    top_n_frames: A number of frames to regard as crashing frame.
+
+  Returns:
+    A set of components.
+  """
+  frame_list = main_stack.GetTopNFrames(top_n_frames)
+  components = set()
+
+  for frame in frame_list:
+    components.add(frame.component_path)
+
+  return components
+
+
+def GenerateAndFilterBlameList(callstack, component_to_crash_revision_dict,
+                               component_to_regression_dict):
+  """A wrapper function.
+
+  Finds blame information for stack and returns string representation.
+
+  Args:
+    callstack: A callstack to find the blame information.
+    component_to_crash_revision_dict: A dictionary mapping component to its
+                                      crash revision.
+    component_to_regression_dict: A dictionary mapping component to its
+                                  regression.
+
+  Returns:
+    A list of blame results.
+  """
+  # Setup parser objects to use for parsing blame information.
+  svn_parser = svn_repository_parser.SVNParser(CONFIG['svn'])
+  git_parser = git_repository_parser.GitParser(component_to_regression_dict,
+                                               CONFIG['git'])
+  parsers = {}
+  parsers['svn'] = svn_parser
+  parsers['git'] = git_parser
+
+  # Create and generate the blame objects from the callstack.
+  blame_list = blame.BlameList()
+  blame_list.FindBlame(callstack, component_to_crash_revision_dict,
+                       component_to_regression_dict,
+                       parsers)
+
+  blame_list.FilterAndSortBlameList()
+  return crash_utils.BlameListToResultList(blame_list)
+
+
+def FindItForCrash(stacktrace_list,
+                   callstack,
+                   component_to_regression_dict,
+                   component_to_crash_revision_dict):
+  """Finds the culprit CL from the list of stacktrace.
+
+  Args:
+    stacktrace_list: A list of stacktraces to look for, in the order of
+                     decreasing significance.
+    callstack: A callstack object to show blame information for, if there are
+               no results for all stacktraces in the stacktrace_list.
+    component_to_regression_dict: A parsed regression information as a
+                                  result of parsing DEPS file.
+    component_to_crash_revision_dict: A parsed crash revision information.
+
+  Returns:
+    A list of result objects, with the message how the result is created.
+  """
+  # If regression information is not available, return blame information.
+  if not component_to_regression_dict:
+    return_message = (
+        'Regression information is not available. The result is '
+        'the blame information.')
+    result = GenerateAndFilterBlameList(callstack,
+                                        component_to_crash_revision_dict,
+                                        component_to_regression_dict)
+    return (return_message, result)
+
+  for stacktrace in stacktrace_list:
+    # Check the next stacktrace if current one is empty.
+    if not stacktrace.stack_list:
+      continue
+
+    # Get the crash stack for this stacktrace, and extract crashing components
+    # from it.
+    main_stack = stacktrace.GetCrashStack()
+    components = ParseCrashComponents(main_stack)
+
+    result_for_stacktrace = FindMatchForStacktrace(
+        stacktrace, components, component_to_regression_dict)
+
+    # If the result is empty, check the next stacktrace. Else, return the
+    # filtered result.
+    if not result_for_stacktrace:
+      continue
+
+    return_message = (
+        'The result is a list of CLs that change the crashed files.')
+    result = FilterAndGenerateReasonForMatches(result_for_stacktrace)
+    return (return_message, result)
+
+  # If no match is found, return the blame information for the input
+  # callstack.
+  return_message = (
+      'There are no CLs that change the crashed files. The result is the '
+      'blame information.')
+  result = GenerateAndFilterBlameList(
+      callstack, component_to_crash_revision_dict,
+      component_to_regression_dict)
+  return (return_message, result)
+