Making CallStack immutable, so it can be hashable

appengine/findit/crash/stacktrace.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 namedtuple
+import copy
 import logging
 import re
 
 from crash import parse_util
 from crash.type_enums import CallStackFormatType
 from crash.type_enums import CallStackLanguageType
 
 # Used to parse a line into StackFrame of a Callstack.
 CALLSTACK_FORMAT_TO_PATTERN = {
     CallStackFormatType.JAVA: re.compile(
         r'at ([A-Za-z0-9$._<>]+)\(\w+(\.java)?:(\d+)\)'),
     CallStackFormatType.SYZYASAN: re.compile(
         r'(CF: )?(.*?)( \(FPO: .*\) )?( \(CONV: .*\) )?\[(.*) @ (\d+)\]'),
     CallStackFormatType.DEFAULT: re.compile(
         r'(.*?):(\d+)(:\d+)?$')
 }
 
 FRAME_INDEX_PATTERN = re.compile(r'\s*#(\d+)\s.*')
 
+_DEFAULT_FORMAT_TYPE = CallStackFormatType.DEFAULT
+_DEFAULT_LANGUAGE_TYPE = CallStackLanguageType.CPP
+
 
 class StackFrame(namedtuple('StackFrame',
     ['index', 'dep_path', 'function', 'file_path', 'raw_file_path',
     'crashed_line_numbers', 'repo_url'])):
   """Represents a frame in a stacktrace.
 
   Attributes:
     index (int): Index shown in the stacktrace if a stackframe line looks like
       this - '#0 ...', else use the index in the callstack list.
     dep_path (str): Path of the dep this frame represents, for example,
       'src/', 'src/v8', 'src/skia'...etc.
     function (str): Function that caused the crash.
     file_path (str): Normalized path of the crashed file, with parts dep_path
       and parts before it stripped, for example, api.cc.
     raw_file_path (str): Normalized original path of the crashed file,
       for example, /b/build/slave/mac64/build/src/v8/src/heap/
       incremental-marking-job.cc.
     crashed_line_numbers (list): Line numbers of the file that caused the crash.
     repo_url (str): Repo url of this frame.
   """
   __slots__ = ()
 
   def __new__(cls, index, dep_path, function, file_path, raw_file_path,
               crashed_line_numbers, repo_url=None):
+    assert index is not None, TypeError("The index must be an int")

[Martin Barbella, 2016/12/08 22:30:55]

Nit: single quotes for consistency with other strings.

[wrengr, 2016/12/08 23:42:37]

Done.

     return super(cls, StackFrame).__new__(cls,
         index, dep_path, function, file_path, raw_file_path,
         crashed_line_numbers, repo_url)
 
   def ToString(self):
     frame_str = '#%d in %s @ %s' % (self.index, self.function, self.file_path)
     if self.crashed_line_numbers:
       frame_str += ':%d' % self.crashed_line_numbers[0]
 
     # For example, if crashed_line_numbers is [61], returns '... f.cc:61',
@@ skipping 10 matching lines @@
     blame_url = '%s/+blame/%s/%s' % (self.repo_url, revision, self.file_path)
     if self.crashed_line_numbers:
       blame_url += '#%d' % self.crashed_line_numbers[0]
 
     return blame_url
 
   def __str__(self):
     return self.ToString()
 
 
-class CallStack(list):
-  """Represents a call stack within a stacktrace. A list of StackFrame objects.
+# TODO(wrengr): this should be a method on ``format_type``, or a class
+# method on ``StackFrame``.

[Sharu Jiang, 2016/12/08 22:23:44]

I think in ``StackFrame`` and change the name to Parse should be the way to go.

[Martin Barbella, 2016/12/08 22:30:55]

Is there any reason not to just do this (my usual comment for new TODOs)?

[stgao, 2016/12/08 23:42:17]

Let's make this a method into the class in this CL instead of a TODO.
If it is a question to discuss during code-review, it is better to add as a
comment before publishing the CL.

[wrengr, 2016/12/08 23:42:37]

Mainly just that I ran into issues getting it to work when I first tried it.
(Also not sure if people had preferences on where to put it.) Done now.

+def ParseStackFrame(language_type, format_type, line, deps,
+    default_stack_frame_index=None):
+  """Parse line into a StackFrame instance, if possible.
+
+  Args:
+    language_type (CallStackLanguageType): the language the line is in.
+    format_type (CallStackFormatType): the format the line is in.
+    line (str): The line to be parsed.
+    deps (dict): Map dependency path to its corresponding Dependency.
+
+  Returns:
+    A ``StackFrame`` or ``None``.
+  """
+  # TODO(wrengr): how can we avoid duplicating this logic from ``CallStack``?
+  if format_type is None: # pragma: no cover
+    format_type = _DEFAULT_FORMAT_TYPE
+
+  if language_type is None:
+    language_type = _DEFAULT_LANGUAGE_TYPE
+
+  if format_type == CallStackFormatType.JAVA:
+    language_type = CallStackLanguageType.JAVA
+
+  line = line.strip()
+  line_pattern = CALLSTACK_FORMAT_TO_PATTERN[format_type]
+
+  if format_type == CallStackFormatType.JAVA:
+    match = line_pattern.match(line)
+    if not match:
+      return None
+
+    function = match.group(1)
+    raw_file_path = parse_util.GetFullPathForJavaFrame(function)
+    crashed_line_numbers = [int(match.group(3))]
+
+  elif format_type == CallStackFormatType.SYZYASAN:
+    match = line_pattern.match(line)
+    if not match:
+      return None
+
+    function = match.group(2).strip()
+    raw_file_path = match.group(5)
+    crashed_line_numbers = [int(match.group(6))]
+
+  else:
+    line_parts = line.split()
+    if not line_parts or not line_parts[0].startswith('#'):
+      return None
+
+    match = line_pattern.match(line_parts[-1])
+    if not match: # pragma: no cover
+      return None
+
+    function = ' '.join(line_parts[3:-1])
+
+    raw_file_path = match.group(1)
+    # Fracas java stack has default format type.
+    if language_type == CallStackLanguageType.JAVA:
+      raw_file_path = parse_util.GetFullPathForJavaFrame(function)
+
+    crashed_line_numbers = parse_util.GetCrashedLineRange(
+        match.group(2) + (match.group(3) if match.group(3) else ''))
+  # Normalize the file path so that it can be compared to repository path.
+  dep_path, file_path, repo_url = parse_util.GetDepPathAndNormalizedFilePath(
+      raw_file_path, deps, language_type == CallStackLanguageType.JAVA)
+
+  # If we have the common stack frame index pattern, then use it
+  # since it is more reliable.
+  index_match = FRAME_INDEX_PATTERN.match(line)
+  if index_match:
+    stack_frame_index = int(index_match.group(1))
+  else:
+    stack_frame_index = int(default_stack_frame_index or 0)
+
+  return StackFrame(stack_frame_index, dep_path, function, file_path,
+                    raw_file_path, crashed_line_numbers, repo_url)
+
+
+# N.B., because ``list`` is mutable it isn't hashable, thus cannot be
+# used as a key in a dict. Because we want to usecallstacks as keys (for
+# memoization) we has-a tuple rather than is-a list.

[Sharu Jiang, 2016/12/08 22:23:44]

I think it's not necessary to make every parameter to memorized function
immutable. If you use the cache decorator in
https://cs.chromium.org/chromium/infra/appengine/findit/libs/cache_decorator.py,
we have something like _DefaultKeyGenerator(You can define yours to serve your
purpose) to generate key.
 
Another concern is that we do a lot manipulation to CallStack and StackTrace,
e.g. a lot filtering. Making it immutable will slow down the efficiency.

[stgao, 2016/12/08 23:42:17]

With the current implementation of MemoizedFunction, I agree that an in-memory
cache + a customized key generator (the default one might work as well) could do
the same, as I commented in the CL which added MemoizedFunction. We could add a
new API to clear the cache.

But I'd like to see the usage of MemoizedFunction to understand better.
wrengr@, do you have some code snippet on where and how MemoizedFunction will be
used?
This is a problem we need to discuss as it is impacted by this CL. This might
cause test breakage as is?

Overall, read-only namedtuple could help avoid the surprise of unexpected
modification.
But as we currently modify the stack trace in-place when we filter out some
frames, we need to think on the overhead of deepcopy for modification.

wrengr@, what do you think of such overhead?

katesonia@, is it doable to do filtering before creating CallStack instance?

[wrengr, 2016/12/08 23:42:37]

Even though the old code did do a lot of mutation, it actually doesn't need to.
There are two places where we call SliceFrames: (1) when computing the
crash_stack for a Stacktrace, which is done only once per construction of a
StackTrace, (2) in the CL classifier for limiting what all the scorers/features
look at, which isn't really necessary since the scorers/features can be
redesigned to only look at the top few frames.

If we actually do run into performance issues then we can optimize the
SliceFrames method. Since things are mutable all the way down, we shouldn't
actually have to allocate a new tuple and copy the pointers to StackFrames over.
We can do a lightweight slicing by just storing a pointer to the original tuple
plus information about the starting and stopping indices. It's trivial enough to
do; but I'd wait to see if we actually have performance issues before bothering.

[Sharu Jiang, 2016/12/09 00:13:58]

We can do, that's one alternative, but this will need some redesign on the
stacktrace Parser.

[Sharu Jiang, 2016/12/09 00:13:58]

For those frames we don't even look into, we shouldn't waste memory to keep
them. Or an alternative should be to redesign the stacktrace to only parse
frames after the signature frame. 
One thing is, do you really want to force every parameter of MemerizedFunction
to be immutable? Especially the ``Callstack`` and ``Stacktrace`` are not small,
using them as key may not be very efficient. IMHO, it'd be better to reuse the
cache_decorator and cache, or you can add key generator to MemorizedFunctions.

[Sharu Jiang, 2016/12/09 00:29:20]

*Only parse top_n frames after the signature frame.
Ignore "using them as key may not be very efficient" comment, the namedtuple
hash should have solved this... 
I saw your comments in https://codereview.chromium.org/2557423003/, if
optimization can solve the performance issue, but a question, for general
purpose, is forcing the parameter x of MemorizedFunction immutable good?

[Sharu Jiang, 2016/12/09 00:57:15]

Follow up on "redesign the stacktrace to only parse
top_n frames after the signature frame.", this would make parsing stacktrace
depend on ``top_n`` in config, this may mess our core_algorithm/gae stuff
seperation... 

[wrengr, 2016/12/09 18:58:38]

All tests pass with 100% coverage. The only modifications were to remove the
unnecessary mutation. (A lot of tests would allocate an empty stack and then
push a whole bunch of frames onto it; now they allocate the complete stack in
one go, which they should've done in the first place.)
Yes, I agree. Semantically callstacks/stacktraces aren't things that change;
they're just information given to us to look at.
Because things are immutable all the way down, there's no need for deep copy.
The only thing SliceFrames needs to do is (1) allocate the new namedtuple, (2)
allocate a tuple for the frames we want to keep, (3) copy pointers. The first
and third are unavoidable; but as I mentioned elsewhere, the second is an
avoidable artifact of the current implementation.

That is, rather than allocating a new tuple for the frames and copying over all
the pointers to those frames, we can instead have a namedtuple which does a
"soft copy". That is, the soft copy stores three things: a pointer to the
original tuple, start index, stop index; and provides the same API as if we did
the hard copy. This reduces the cost of slicing down to be constant time. This
is a standard trick used extensively in other languages (and maybe that's what
Python's "slice objects" do?). But since it adds complexity, I'd rather wait and
see whether we actually need to bother doing it (given as we only call
SliceFrames in two places, so it's not like we're doing this all that often).

[wrengr, 2016/12/09 18:58:38]

The code using MemoizedFunction is:

https://codereview.chromium.org/2517383005/
https://codereview.chromium.org/2544493004/

The code necessitating this CL is:

https://codereview.chromium.org/2560723005/

+class CallStack(namedtuple('CallStack',
+    ['priority', 'frames', 'format_type', 'language_type'])):
+  """A stack (sequence of ``StackFrame`` objects)  in a ``Stacktrace``.
 
   Attributes:
     priority (int): The smaller the number, the higher the priority beginning
       with 0.
+    frames (tuple of StackFrame): the frames in order from bottom to top.
     format_type (CallStackFormatType): Represents the type of line format
       within a callstack. For example:
 
       CallStackFormatType.JAVA -
       'at com.android.commands.am.Am.onRun(Am.java:353)'
 
       CallStackFormatType.SYZYASAN -
       'chrome_child!v8::internal::ApplyTransition+0x93 [v8/src/lookup.cc @ 340]'
 
       CallStackFormatType.DEFAULT -
       '#0 0x32b5982 in get third_party/WebKit/Source/wtf/RefPtr.h:61:43'
     language_type (CallStackLanguageType): Either CPP or JAVA language.
   """
-  def __init__(self, priority, format_type=CallStackFormatType.DEFAULT,
-               language_type=CallStackLanguageType.CPP,
-               frame_list=None):
-    super(CallStack, self).__init__(frame_list or [])
+  __slots__ = ()
 
-    self.priority = priority
-    self.format_type = format_type
-    self.language_type = (
-        CallStackLanguageType.JAVA if format_type == CallStackFormatType.JAVA
-        else language_type)
+  def __new__(cls, priority, format_type=None, language_type=None,
+              frame_list=None):
+    """Construct a new ``CallStack``.
 
-  def ParseLine(self, line, deps):
-    """Parse line into StackFrame instance and append it if successfully
-    parsed."""
-    line = line.strip()
-    line_pattern = CALLSTACK_FORMAT_TO_PATTERN[self.format_type]
+    N.B., we use ``None`` as the default value of the optional arguments
+    so that if callers need to explicitly provide those arguments but
+    don't have an explicit value, they can pass ``None`` to get at the
+    default without needing to be kept in sync with this constructor. For
+    example, the ``ChromeCrashParser.Parse`` constructs a stack and they
+    need to keep track of all the arguments to be passed to this function.
 
-    if self.format_type == CallStackFormatType.JAVA:
-      match = line_pattern.match(line)
-      if not match:
-        return
+    Args:
+      priority (int): The priority of this stack in its ``Stacktrace``.
+      format_type (CallStackFormatType): Optional. The stack's format.
+      language_type (CallStackLanguageType): Optional. The stack's language.
+      frame_list (iterable of StackFrame): Optional. The frames in the stack.
+    """
+    if format_type is None:
+      format_type = _DEFAULT_FORMAT_TYPE
 
-      function = match.group(1)
-      raw_file_path = parse_util.GetFullPathForJavaFrame(function)
-      crashed_line_numbers = [int(match.group(3))]
+    if language_type is None:
+      language_type = _DEFAULT_LANGUAGE_TYPE
 
-    elif self.format_type == CallStackFormatType.SYZYASAN:
-      match = line_pattern.match(line)
-      if not match:
-        return
+    if format_type == CallStackFormatType.JAVA: # pragma: no cover

[Martin Barbella, 2016/12/08 22:30:55]

Not too important, but do we really need no cover here? Seems like an easy
enough case to hit, but there might not be much value in it.

[wrengr, 2016/12/08 23:42:37]

We don't *need* the pragma; rather, the old version of the code wasn't actually
covering this case, but that was hidden from the code coverage checker.

Added a new test.

+      language_type = CallStackLanguageType.JAVA
 
-      function = match.group(2).strip()
-      raw_file_path = match.group(5)
-      crashed_line_numbers = [int(match.group(6))]
+    if frame_list is None:
+      frame_list = []
 
-    else:
-      line_parts = line.split()
-      if not line_parts or not line_parts[0].startswith('#'):
-        return
+    return super(cls, CallStack).__new__(cls,
+        priority, tuple(frame_list), format_type, language_type)
 
-      match = line_pattern.match(line_parts[-1])
-      if not match:
-        return
+  def __len__(self):
+    """Returns the number of frames in this stack."""
+    return len(self.frames)
 
-      function = ' '.join(line_parts[3:-1])
+  # TODO: we do actually have unittests for this, but for some reason

[Martin Barbella, 2016/12/08 22:30:55]

Strange. Is there a bug opened for this? might be nice to be able to point folks
more familiar with how we gather the coverage information at this.

Also, could you reference the bug or yourself in the TODO?

[wrengr, 2016/12/08 23:42:37]

Done. crbug.com/672641

+  # coverage isn't seeing them.
+  def __bool__(self): # pragma: no cover
+    """Returns whether this stack is empty."""
+    return bool(self.frames)
 
-      raw_file_path = match.group(1)
-      # Fracas java stack has default format type.
-      if self.language_type == CallStackLanguageType.JAVA:
-        raw_file_path = parse_util.GetFullPathForJavaFrame(function)
+  def __iter__(self):
+    """Iterator over the frames in this stack."""
+    return iter(self.frames)
 
-      crashed_line_numbers = parse_util.GetCrashedLineRange(
-          match.group(2) + (match.group(3) if match.group(3) else ''))
-    # Normalize the file path so that it can be compared to repository path.
-    dep_path, file_path, repo_url = parse_util.GetDepPathAndNormalizedFilePath(
-        raw_file_path, deps, self.language_type == CallStackLanguageType.JAVA)
+  def SliceFrames(self, low_index, high_index):
+    """Returns a new ``CallStack`` keeping only the specified frames.
 
-    # If we have the common stack frame index pattern, then use it
-    # since it is more reliable.
-    index_match = FRAME_INDEX_PATTERN.match(line)
-    if index_match:
-      stack_frame_index = int(index_match.group(1))
-    else:
-      stack_frame_index = len(self)
+    Args:
+      low_index (int or None): the lowest index to keep. If ``None``
+        then defaults to 0.
+      high_index (int or None): the index after the highest one to
+        keep. If ``None`` then defaults to one after the highest index.
 
-    self.append(StackFrame(stack_frame_index, dep_path, function, file_path,
-                           raw_file_path, crashed_line_numbers, repo_url))
+    Returns:
+      A new ``CallStack`` instance. If both arguments are ``None`` then
+      we return the original stack object, because they are equal and
+      due to immutability there's no reason to clone the instance.
+    """
+    if low_index is None and high_index is None:
+      return self
+
+    # TODO(wrengr): can we use ``_replace`` without running into TypeErrors?

[Sharu Jiang, 2016/12/08 22:23:44]

what TypeErrors you encountered?

[wrengr, 2016/12/08 23:42:37]

The TypeError complains about _make not being called with the right number of
arguments (_make is called by _replace). It's something really weird about the
guts of namedtuples and not easily googleable. I'm guessing it has something to
do with the fact that the frames attribute is a tuple rather than a simple
scalar, and that we're changing its length. If I can trigger it again I'll file
a bug with the stack trace.

Copying all the other attributes over one by one works well enough; it just
introduces maintenance costs should we ever change the arguments to the
constructor

+    return CallStack(self.priority,
+        format_type=self.format_type,
+        language_type=self.language_type,
+        frame_list=self.frames[low_index:high_index])
 
 
+# N.B., because ``list`` is mutable it isn't hashable, thus cannot be
+# used as a key in a dict. Because we want to usecallstacks as keys (for
+# memoization) we has-a tuple rather than is-a list.
 # TODO(http://crbug.com/644476): this class needs a better name.
-class Stacktrace(list):
+class Stacktrace(object):
   """A collection of callstacks which together provide a trace of what happened.
 
   For instance, when doing memory debugging we will have callstacks for
   (1) when the crash occurred, (2) when the object causing the crash
   was allocated, (3) when the object causing the crash was freed (for
   use-after-free crashes), etc. What callstacks are included in the
   trace is unspecified, since this differs for different tools."""
   def __init__(self, stack_list=None, signature=None):
-    super(Stacktrace, self).__init__(stack_list or [])
-
+    self.stacks = stack_list or []
     self._crash_stack = None
     self._signature_parts = None
     if signature:
       # Filter out the types of signature, for example [Out of Memory].
       signature = re.sub('[[][^]]*[]]\s*', '', signature)
       # For clusterfuzz crash, the signature is crash state. It is
       # usually the top 3 important stack frames separated by '\n'.
       self._signature_parts = signature.split('\n')
 
+  def __getitem__(self, i): # pragma: no cover
+    return self.stacks[i]
+
+  def __len__(self):
+    return len(self.stacks)
+
+  def __bool__(self): # pragma: no cover
+    return bool(self.stacks)
+
+  def __iter__(self):
+    return iter(self.stacks)
 
   @property
   def crash_stack(self):
     """Get the callstack with the highest priority (i.e., whose priority
     field is numerically the smallest) in the stacktrace."""
-    if not self:
+    if not self.stacks:
       logging.warning('Cannot get crash stack for empty stacktrace: %s', self)
       return None
 
     if self._crash_stack is None and self._signature_parts:
       def _IsSignatureCallstack(callstack):
         for index, frame in enumerate(callstack):
           for signature_part in self._signature_parts:
             if signature_part in frame.function:
               return True, index
 
         return False, 0
 
       # Set the crash stack using signature callstack.
-      for callstack in self:
+      for callstack in self.stacks:
         is_signature_callstack, index = _IsSignatureCallstack(callstack)
         if is_signature_callstack:
           # Filter all the stack frames before signature.
-          callstack[:] = callstack[index:]
-          self._crash_stack = callstack
+          self._crash_stack = callstack.SliceFrames(index, None)
           break
 
     # If there is no signature callstack, fall back to set crash stack using
     # the first least priority callstack.
     if self._crash_stack is None:
-      self._crash_stack = sorted(self, key=lambda stack: stack.priority)[0]
+      self._crash_stack = sorted(self.stacks,
+          key=lambda stack: stack.priority)[0]
 
     return self._crash_stack