Open Source Monorail

appengine/monorail/framework/sorting.py

Index: appengine/monorail/framework/sorting.py
diff --git a/appengine/monorail/framework/sorting.py b/appengine/monorail/framework/sorting.py
new file mode 100644
index 0000000000000000000000000000000000000000..282935c9ba69df50c1c6d35b01354070bde337c9
--- /dev/null
+++ b/appengine/monorail/framework/sorting.py
@@ -0,0 +1,480 @@
+# Copyright 2016 The Chromium Authors. All rights reserved.
+# Use of this source code is govered by a BSD-style
+# license that can be found in the LICENSE file or at
+# https://developers.google.com/open-source/licenses/bsd
+
+"""Helper functions for sorting lists of project artifacts.
+
+This module exports the SortArtifacts function that does sorting of
+Monorail business objects (e.g., an issue).  The sorting is done by
+extracting relevant values from the PB using a dictionary of
+accessor functions.
+
+The desired sorting directives are specified in part of the user's
+HTTP request.  This sort spec consists of the names of the columns
+with optional minus signs to indicate descending sort order.
+
+The tool configuration object also affects sorting.  When sorting by
+key-value labels, the well-known labels are considered to come
+before any non-well-known labels, and those well-known labels sort in
+the order in which they are defined in the tool config PB.
+"""
+
+import logging
+
+import settings
+from framework import framework_constants
+from proto import tracker_pb2
+from tracker import tracker_bizobj
+
+
+class DescendingValue(object):
+  """A wrapper which reverses the sort order of values."""
+
+  @classmethod
+  def MakeDescendingValue(cls, obj):
+    """Make a value that sorts in the reverse order as obj."""
+    if isinstance(obj, int):
+      return -obj
+    if obj == MAX_STRING:
+      return MIN_STRING
+    if obj == MIN_STRING:
+      return MAX_STRING
+    if isinstance(obj, list):
+      return [cls.MakeDescendingValue(item) for item in reversed(obj)]
+    return DescendingValue(obj)
+
+  def __init__(self, val):
+    self.val = val
+
+  def __cmp__(self, other):
+    """Return -1, 0, or 1 base on the reverse of the normal sort order."""
+    if isinstance(other, DescendingValue):
+      return cmp(other.val, self.val)
+    else:
+      return cmp(other, self.val)
+
+  def __repr__(self):
+    return 'DescendingValue(%r)' % self.val
+
+
+# A string that sorts after every other string, and one that sorts before them.
+MAX_STRING = '~~~'
+MIN_STRING = DescendingValue(MAX_STRING)
+
+
+# RAMCache {issue_id: {column_name: sort_key, ...}, ...}
+art_values_cache = None
+
+
+def InitializeArtValues(services):
+  global art_values_cache
+  art_values_cache = services.cache_manager.MakeCache(
+      'issue', max_size=settings.issue_cache_max_size)
+
+
+def SortArtifacts(
+    mr, artifacts, config, accessors, username_cols=None, users_by_id=None):
+  """Return a list of artifacts sorted by the user's sort specification.
+
+  In the following, an "accessor" is a function(art) -> [field_value, ...].
+
+  Args:
+    mr: commonly used info parsed from the request, including query.
+    artifacts: an unsorted list of project artifact PBs.
+    config: Project config PB instance that defines the sort order for
+        labels and statuses in this project.
+    accessors: dictionary of (column_name -> accessor) to get values
+        from the artifacts.
+    username_cols: optional list of lowercase column names that will show
+        user names.
+    users_by_id: optional dictionary {user_id: user_view,...} for all users
+        who participate in the list of artifacts.
+
+  Returns:
+    A sorted list of artifacts.
+
+  Note: if username_cols is supplied, then users_by_id should be too.
+
+  The approach to sorting is to construct a comprehensive sort key for
+  each artifact. To create the sort key, we (a) build lists with a
+  variable number of fields to sort on, and (b) allow individual
+  fields to be sorted in descending order.  Even with the time taken
+  to build the sort keys, calling sorted() with the key seems to be
+  faster overall than doing multiple stable-sorts or doing one sort
+  using a multi-field comparison function.
+  """
+  sort_directives = ComputeSortDirectives(mr, config)
+
+  # Build a list of accessors that will extract sort keys from the issues.
+  accessor_pairs = [
+      (sd, _MakeCombinedSortKeyAccessor(
+          sd, config, accessors, username_cols, users_by_id))
+      for sd in sort_directives]
+
+  def SortKey(art):
+    """Make a sort_key for the given artifact, used by sorted() below."""
+    if art_values_cache.HasItem(art.issue_id):
+      art_values = art_values_cache.GetItem(art.issue_id)
+    else:
+      art_values = {}
+
+    sort_key = []
+    for sd, accessor in accessor_pairs:
+      if sd not in art_values:
+        art_values[sd] = accessor(art)
+      sort_key.append(art_values[sd])
+
+    art_values_cache.CacheItem(art.issue_id, art_values)
+    return sort_key
+
+  return sorted(artifacts, key=SortKey)
+
+
+def ComputeSortDirectives(mr, config, tie_breaker='id'):
+  """Return a list with sort directives to be used in sorting.
+
+  Args:
+    mr: commonly used info parsed from the request, including query.
+    config: Project config PB instance that defines the sort order for
+        labels and statuses in this project.
+    tie_breaker: column name to add to the end of the sort spec if it is
+        not already somewhere in the sort spec.
+
+  Returns:
+    A list of lower-case column names, each one may have a leading
+    minus-sign.
+  """
+  # Prepend the end-user's sort spec to any project default sort spec.
+  sort_spec = '%s %s %s' % (
+      mr.group_by_spec, mr.sort_spec, config.default_sort_spec)
+  # Sort specs can have interfering sort orders, so remove any duplicates.
+  field_names = set()
+  sort_directives = []
+  for sort_directive in sort_spec.lower().split():
+    field_name = sort_directive.lstrip('-')
+    if field_name not in field_names:
+      sort_directives.append(sort_directive)
+      field_names.add(field_name)
+
+  # Add in the project name so that the overall ordering is completely
+  # defined in cross-project search. Otherwise, issues jump up and
+  # down on each reload of the same query, and prev/next links get
+  # messed up.  It's a no-op in single projects.
+  if 'project' not in sort_directives:
+    sort_directives.append('project')
+
+  if tie_breaker not in sort_directives:
+    sort_directives.append(tie_breaker)
+
+  return sort_directives
+
+
+def _MakeCombinedSortKeyAccessor(
+    sort_directive, config, accessors, username_cols, users_by_id):
+  """Return an accessor that extracts a sort key for a UI table column.
+
+  Args:
+    sort_directive: string with column name and optional leading minus sign,
+        for combined columns, it may have slashes, e.g., "-priority/pri".
+    config: ProjectIssueConfig instance that defines the sort order for
+        labels and statuses in this project.
+    accessors: dictionary of (column_name -> accessor) to get values
+        from the artifacts.
+    username_cols: list of lowercase names of columns that contain user names.
+    users_by_id: dictionary {user_id: user_view,...} for all users
+        who participate in the list of artifacts (e.g., owners, reporters, cc).
+
+  Returns:
+    A list of accessor functions that can be applied to an issue to extract
+    the relevant sort key value.
+
+  The strings for status and labels are converted to lower case in
+  this method so that they sort like case-insensitive enumerations.
+  Any component-specific field of the artifact is sorted according to the
+  value returned by the accessors defined in that component.  Those
+  accessor functions should lower case string values for fields where
+  case-insensitive sorting is desired.
+  """
+  if sort_directive.startswith('-'):
+    combined_col_name = sort_directive[1:]
+    descending = True
+  else:
+    combined_col_name = sort_directive
+    descending = False
+
+  wk_labels = [wkl.label for wkl in config.well_known_labels]
+  accessors = [
+      _MakeSingleSortKeyAccessor(
+          col_name, config, accessors, username_cols, users_by_id, wk_labels)
+      for col_name in combined_col_name.split('/')]
+
+  # The most common case is that we sort on a single column, like "priority".
+  if len(accessors) == 1:
+    return _MaybeMakeDescending(accessors[0], descending)
+
+  # Less commonly, we are sorting on a combined column like "priority/pri".
+  def CombinedAccessor(art):
+    """Flatten and sort the values for each column in a combined column."""
+    key_part = []
+    for single_accessor in accessors:
+      value = single_accessor(art)
+      if isinstance(value, list):
+        key_part.extend(value)
+      else:
+        key_part.append(value)
+    return sorted(key_part)
+
+  return _MaybeMakeDescending(CombinedAccessor, descending)
+
+
+def _MaybeMakeDescending(accessor, descending):
+  """If descending is True, return a new function that reverses accessor."""
+  if not descending:
+    return accessor
+
+  def DescendingAccessor(art):
+    asc_value = accessor(art)
+    return DescendingValue.MakeDescendingValue(asc_value)
+
+  return DescendingAccessor
+
+
+def _MakeSingleSortKeyAccessor(
+    col_name, config, accessors, username_cols, users_by_id, wk_labels):
+  """Return an accessor function for a single simple UI column."""
+  # Case 1. Handle built-in fields: status, component.
+  if col_name == 'status':
+    wk_statuses = [wks.status for wks in config.well_known_statuses]
+    return _IndexOrLexical(wk_statuses, accessors[col_name])
+
+  if col_name == 'component':
+    comp_defs = sorted(config.component_defs, key=lambda cd: cd.path.lower())
+    comp_ids = [cd.component_id for cd in comp_defs]
+    return _IndexListAccessor(comp_ids, accessors[col_name])
+
+  # Case 2. Any other defined accessor functions.
+  if col_name in accessors:
+    if username_cols and col_name in username_cols:
+      # sort users by email address rather than user ids.
+      return _UserEditNameAccessor(users_by_id, accessors[col_name])
+    else:
+      return accessors[col_name]
+
+  # Case 3. Anything else is assumed to be a label prefix or custom field.
+  # TODO(jrobbins): user-valued custom fields.  Find them at top of loop.
+  fd_list = [
+      fd for fd in config.field_defs
+      if (fd.field_name.lower() == col_name and
+          fd.field_type != tracker_pb2.FieldTypes.ENUM_TYPE)]
+  return _IndexOrLexicalList(
+      wk_labels, fd_list, col_name, users_by_id)
+
+
+IGNORABLE_INDICATOR = -1
+
+
+def _PrecomputeSortIndexes(values, col_name):
+  """Precompute indexes of strings in the values list for fast lookup later."""
+  # Make a dictionary that immediately gives us the index of any value
+  # in the list, and also add the same values in all-lower letters.  In
+  # the case where two values differ only by case, the later value wins,
+  # which is fine.
+  indexes = {}
+  if col_name:
+    prefix = col_name + '-'
+  else:
+    prefix = ''
+  for idx, val in enumerate(values):
+    if val.lower().startswith(prefix):
+      indexes[val] = idx
+      indexes[val.lower()] = idx
+    else:
+      indexes[val] = IGNORABLE_INDICATOR
+      indexes[val.lower()] = IGNORABLE_INDICATOR
+
+  return indexes
+
+
+def _UserEditNameAccessor(users_by_id, base_accessor):
+  """Make an accessor that returns a list of user edit names for sorting.
+
+  Args:
+    users_by_id: dictionary {user_id: user_view, ...} for all participants
+        in the entire list of artifacts.
+    base_accessor: an accessor function f(artifact) -> user_id.
+
+  Returns:
+    An accessor f(artifact) -> value that can be used in sorting
+    the decorated list.
+  """
+
+  def Accessor(art):
+    """Return a user edit name for the given artifact's base_accessor."""
+    id_or_id_list = base_accessor(art)
+    if isinstance(id_or_id_list, list):
+      emails = [users_by_id[user_id].email
+                for user_id in id_or_id_list]
+    else:
+      emails = [users_by_id[id_or_id_list].email]
+
+    return sorted(emails) or MAX_STRING
+
+  return Accessor
+
+
+def _MakeColumnAccessor(col_name):
+  """Make an accessor for an issue's labels that have col_name as a prefix.
+
+  Args:
+    col_name: string column name.
+
+  Returns:
+    An accessor that can be applied to an artifact to return a list of
+    labels that have col_name as a prefix.
+
+  For example, _MakeColumnAccessor('priority')(issue) could result in
+  [], or ['priority-high'], or a longer list for multi-valued labels.
+  """
+  prefix = col_name + '-'
+
+  def Accessor(art):
+    """Return a list of label values on the given artifact."""
+    result = [label.lower() for label in tracker_bizobj.GetLabels(art)
+              if label.lower().startswith(prefix)]
+    return result
+
+  return Accessor
+
+
+def _IndexOrLexical(wk_values, base_accessor):
+  """Return an accessor to score an artifact based on a user-defined ordering.
+
+  Args:
+    wk_values: a list of well-known status values from the config.
+    base_accessor: function that gets a field from a given issue.
+
+  Returns:
+    An accessor that can be applied to an issue to return a suitable
+    sort key.
+
+  For example, when used to sort issue statuses, these accessors return an
+  integer for well-known statuses, a string for odd-ball statuses, and an
+  extreme value key for issues with no status.  That causes issues to appear
+  in the expected order with odd-ball issues sorted lexicographically after
+  the ones with well-known status values, and issues with no defined status at
+  the very end.
+  """
+  well_known_value_indexes = _PrecomputeSortIndexes(wk_values, '')
+
+  def Accessor(art):
+    """Custom-made function to return a specific value of any issue."""
+    value = base_accessor(art)
+    if not value:
+      # Undefined values sort last.
+      return MAX_STRING
+
+    try:
+      # Well-known values sort by index.  Ascending sorting has positive ints
+      # in well_known_value_indexes.
+      return well_known_value_indexes[value]
+    except KeyError:
+      # Odd-ball values after well-known and lexicographically.
+      return value.lower()
+
+  return Accessor
+
+
+def _IndexListAccessor(wk_values, base_accessor):
+  """Return an accessor to score an artifact based on a user-defined ordering.
+
+  Args:
+    wk_values: a list of well-known values from the config.
+    base_accessor: function that gets a field from a given issue.
+
+  Returns:
+    An accessor that can be applied to an issue to return a suitable
+    sort key.
+  """
+  well_known_value_indexes = {
+    val: idx for idx, val in enumerate(wk_values)}
+
+  def Accessor(art):
+    """Custom-made function to return a specific value of any issue."""
+    values = base_accessor(art)
+    if not values:
+      # Undefined values sort last.
+      return MAX_STRING
+
+    indexes = [well_known_value_indexes.get(val, MAX_STRING) for val in values]
+    return sorted(indexes)
+
+  return Accessor
+
+
+def _IndexOrLexicalList(wk_values, fd_list, col_name, users_by_id):
+  """Return an accessor to score an artifact based on a user-defined ordering.
+
+  Args:
+    wk_values: A list of well-known labels from the config.
+    fd_list: list of FieldDef PBs that match the column name.  These might not
+        all have the same field_type.  Enum-type field are not included.
+    col_name: lowercase string name of the column that will be sorted on.
+    users_by_id: A dictionary {user_id: user_view}.
+
+  Returns:
+    An accessor that can be applied to an issue to return a suitable
+    sort key.
+  """
+  well_known_value_indexes = _PrecomputeSortIndexes(wk_values, col_name)
+
+  def Accessor(art):
+    """Custom-made function to return a sort value for any issue."""
+    idx_or_lex_list = (
+        _SortableFieldValues(art, fd_list, users_by_id) +
+        _SortableLabelValues(art, col_name, well_known_value_indexes))
+    if not idx_or_lex_list:
+      return MAX_STRING  # issues with no value sort to the end of the list.
+    return sorted(idx_or_lex_list)
+
+  return Accessor
+
+
+def _SortableFieldValues(art, fd_list, users_by_id):
+  """Return a list of field values relevant to one UI table column."""
+  sortable_value_list = []
+  for fd in fd_list:
+    for fv in art.field_values:
+      if fv.field_id == fd.field_id:
+        sortable_value_list.append(
+            tracker_bizobj.GetFieldValue(fv, users_by_id))
+
+  return sortable_value_list
+
+
+def _SortableLabelValues(art, col_name, well_known_value_indexes):
+  """Return a list of ints and strings for labels relevant to one UI column."""
+  sortable_value_list = []
+  for label in tracker_bizobj.GetLabels(art):
+    idx_or_lex = well_known_value_indexes.get(label)
+    if idx_or_lex == IGNORABLE_INDICATOR:
+      continue  # Label is known to not have the desired prefix.
+    if idx_or_lex is None:
+      if '-' not in label:
+        # Skip an irrelevant OneWord label and remember to ignore it later.
+        well_known_value_indexes[label] = IGNORABLE_INDICATOR
+        continue
+      key, value = label.lower().split('-', 1)
+      if key == col_name:
+        # Label is a key-value label with an odd-ball value, remember it
+        idx_or_lex = value
+        well_known_value_indexes[label] = value
+      else:
+        # Label was a key-value label that is not relevant to this column.
+        # Remember to ignore it later.
+        well_known_value_indexes[label] = IGNORABLE_INDICATOR
+        continue
+
+    sortable_value_list.append(idx_or_lex)
+
+  return sortable_value_list