framework/sorting.py

# Copyright 2016 The Chromium Authors
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""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.
"""
from __future__ import print_function
from __future__ import division
from __future__ import absolute_import

import functools

import settings
from mrproto import tracker_pb2
from services import caches
from tracker import tracker_bizobj
from tracker import tracker_constants


@functools.total_ordering
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 __eq__(self, other):
    if isinstance(other, DescendingValue):
      return self.val == other.val
    return self.val == other

  def __ne__(self, other):
    if isinstance(other, DescendingValue):
      return self.val != other.val
    return self.val != other

  def __lt__(self, other):
    if isinstance(other, DescendingValue):
      return other.val < self.val
    return 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 = caches.RamCache(
      services.cache_manager, 'issue', max_size=settings.issue_cache_max_size)


def InvalidateArtValuesKeys(cnxn, keys):
  art_values_cache.InvalidateKeys(cnxn, keys)


def SortArtifacts(
    artifacts, config, accessors, postprocessors, group_by_spec, sort_spec,
    users_by_id=None, tie_breakers=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:
    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: dict {column_name: accessor} to get values from the artifacts.
    postprocessors: dict {column_name: postprocessor} to get user emails
        and timestamps.
    group_by_spec: string that lists the grouping order
    sort_spec: string that lists the sort order
    users_by_id: optional dictionary {user_id: user_view,...} for all users
        who participate in the list of artifacts.
    tie_breakers: list of column names to add to the end of the sort
        spec if they are not already somewhere in the sort spec.

  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(
      config, group_by_spec, sort_spec, tie_breakers=tie_breakers)

  # Build a list of accessors that will extract sort keys from the issues.
  accessor_pairs = [
      (sd, _MakeCombinedSortKeyAccessor(
          sd, config, accessors, postprocessors, 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=lambda x: Python2Key(SortKey(x)))


def ComputeSortDirectives(config, group_by_spec, sort_spec, tie_breakers=None):
  """Return a list with sort directives to be used in sorting.

  Args:
    config: Project config PB instance that defines the sort order for
        labels and statuses in this project.
    group_by_spec: string that lists the grouping order
    sort_spec: string that lists the sort order
    tie_breakers: list of column names to add to the end of the sort
        spec if they are 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.
  if tie_breakers is None:
    tie_breakers = ['id']
  sort_spec = '%s %s %s' % (
      group_by_spec, 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')

  for tie_breaker in tie_breakers:
    if tie_breaker not in sort_directives:
      sort_directives.append(tie_breaker)

  return sort_directives


def _MakeCombinedSortKeyAccessor(
    sort_directive, config, accessors, postprocessors, 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.
    postprocessors: dict {column_name: postprocessor} to get user emails
        and timestamps.
    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, postprocessors, 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, key=Python2Key)

  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, postprocessors, 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 postprocessors and col_name in postprocessors:
      # sort users by email address or timestamp rather than user ids.
      return _MakeAccessorWithPostProcessor(
          users_by_id, accessors[col_name], postprocessors[col_name])
    else:
      return accessors[col_name]

  # Case 3. Anything else is assumed to be a label prefix or custom field.
  return _IndexOrLexicalList(
      wk_labels, config.field_defs, 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 _MakeAccessorWithPostProcessor(users_by_id, base_accessor, postprocessor):
  """Make an accessor that returns a list of user_view properties 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.
    postprocessor: function f(user_view) -> single sortable value.

  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):
      values = [postprocessor(users_by_id[user_id])
                for user_id in id_or_id_list]
    else:
      values = [postprocessor(users_by_id[id_or_id_list])]

    return sorted(values) 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, key=Python2Key)

  return Accessor


def _IndexOrLexicalList(wk_values, full_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.
    full_fd_list: list of FieldDef PBs that belong to the config.
    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)

  if col_name.endswith(tracker_constants.APPROVER_COL_SUFFIX):
    # Custom field names cannot end with the APPROVER_COL_SUFFIX. So the only
    # possible relevant values are approvers for an APPROVAL_TYPE named
    # field_name and any values from labels with the key 'field_name-approvers'.
    field_name = col_name[:-len(tracker_constants.APPROVER_COL_SUFFIX)]
    approval_fds = [fd for fd in full_fd_list
                    if (fd.field_name.lower() == field_name and
                        fd.field_type == tracker_pb2.FieldTypes.APPROVAL_TYPE)]

    def ApproverAccessor(art):
      """Custom-made function to return a sort value or an issue's approvers."""
      idx_or_lex_list = (
          _SortableApprovalApproverValues(art, approval_fds, 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, key=Python2Key)

    return ApproverAccessor

  # Column name does not end with APPROVER_COL_SUFFIX, so relevant values
  # are Approval statuses or Field Values for fields named col_name and
  # values from labels with the key equal to col_name.
  field_name = col_name
  phase_name = None
  if '.' in col_name:
    phase_name, field_name = col_name.split('.', 1)

  fd_list = [fd for fd in full_fd_list
             if (fd.field_name.lower() == field_name and
                 fd.field_type != tracker_pb2.FieldTypes.ENUM_TYPE and
                 bool(phase_name) == fd.is_phase_field)]
  approval_fds = []
  if not phase_name:
    approval_fds = [fd for fd in fd_list if
                    fd.field_type == tracker_pb2.FieldTypes.APPROVAL_TYPE]

  def Accessor(art):
    """Custom-made function to return a sort value for any issue."""
    idx_or_lex_list = (
        _SortableApprovalStatusValues(art, approval_fds) +
        _SortableFieldValues(art, fd_list, users_by_id, phase_name) +
        _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, key=Python2Key)

  return Accessor


def _SortableApprovalStatusValues(art, fd_list):
  """Return a list of approval statuses relevant to one UI table column."""
  sortable_value_list = []
  for fd in fd_list:
    for av in art.approval_values:
      if av.approval_id == fd.field_id:
        # Order approval statuses by life cycle.
        # NOT_SET == 8 but should be before all other statuses.
        sortable_value_list.append(
            0 if av.status.number == 8 else av.status.number)

  return sortable_value_list


def _SortableApprovalApproverValues(art, fd_list, users_by_id):
  """Return a list of approval approvers relevant to one UI table column."""
  sortable_value_list = []
  for fd in fd_list:
    for av in art.approval_values:
      if av.approval_id == fd.field_id:
        sortable_value_list.extend(
          [users_by_id.get(approver_id).email
           for approver_id in av.approver_ids
           if users_by_id.get(approver_id)])

  return sortable_value_list


def _SortableFieldValues(art, fd_list, users_by_id, phase_name):
  """Return a list of field values relevant to one UI table column."""
  phase_id = None
  if phase_name:
    phase_id = next((
        phase.phase_id for phase in art.phases
        if phase.name.lower() == phase_name), None)
  sortable_value_list = []
  for fd in fd_list:
    for fv in art.field_values:
      if fv.field_id == fd.field_id and fv.phase_id == phase_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."""
  col_name_dash = col_name + '-'
  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
      label_lower = label.lower()
      if label_lower.startswith(col_name_dash):
        # Label is a key-value label with an odd-ball value, remember it
        value = label_lower[len(col_name_dash):]
        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


def _Python2Cmp(a, b):
  """Compares two objects in the Python 2 way.

  In Python 3, comparing two objects of different types raises a TypeError.
  In Python 2, when you compare two objects of different types, they are
  generally ordered by their type names, with a few special cases carved
  out for int/float and str/unicode.

  This comparison function also looks through lists and compares them pairwise.
  It doesn't do the same for other iterables.
  """
  try:
    # First try comparing the objects directly.
    # https://docs.python.org/3.0/whatsnew/3.0.html#ordering-comparisons
    return (a > b) - (a < b)
  except TypeError:
    s1, s2 = type(a).__name__, type(b).__name__
    if not (s1 == 'list' and s2 == 'list'):
      # If they are different types, compare their type names.
      return (s1 > s2) - (s1 < s2)

    # If they are both lists, compare their elements pairwise.
    for x, y in zip(a, b):
      element_cmp = _Python2Cmp(x, y)
      if element_cmp != 0:
        return element_cmp

    # If the lists start with the same elements, compare their lengths.
    return (len(a) > len(b)) - (len(a) < len(b))


Python2Key = functools.cmp_to_key(_Python2Cmp)