OLD | NEW |
(Empty) | |
| 1 # Copyright 2016 The Chromium Authors. All rights reserved. |
| 2 # Use of this source code is govered by a BSD-style |
| 3 # license that can be found in the LICENSE file or at |
| 4 # https://developers.google.com/open-source/licenses/bsd |
| 5 |
| 6 """Helper functions for sorting lists of project artifacts. |
| 7 |
| 8 This module exports the SortArtifacts function that does sorting of |
| 9 Monorail business objects (e.g., an issue). The sorting is done by |
| 10 extracting relevant values from the PB using a dictionary of |
| 11 accessor functions. |
| 12 |
| 13 The desired sorting directives are specified in part of the user's |
| 14 HTTP request. This sort spec consists of the names of the columns |
| 15 with optional minus signs to indicate descending sort order. |
| 16 |
| 17 The tool configuration object also affects sorting. When sorting by |
| 18 key-value labels, the well-known labels are considered to come |
| 19 before any non-well-known labels, and those well-known labels sort in |
| 20 the order in which they are defined in the tool config PB. |
| 21 """ |
| 22 |
| 23 import logging |
| 24 |
| 25 import settings |
| 26 from framework import framework_constants |
| 27 from proto import tracker_pb2 |
| 28 from tracker import tracker_bizobj |
| 29 |
| 30 |
| 31 class DescendingValue(object): |
| 32 """A wrapper which reverses the sort order of values.""" |
| 33 |
| 34 @classmethod |
| 35 def MakeDescendingValue(cls, obj): |
| 36 """Make a value that sorts in the reverse order as obj.""" |
| 37 if isinstance(obj, int): |
| 38 return -obj |
| 39 if obj == MAX_STRING: |
| 40 return MIN_STRING |
| 41 if obj == MIN_STRING: |
| 42 return MAX_STRING |
| 43 if isinstance(obj, list): |
| 44 return [cls.MakeDescendingValue(item) for item in reversed(obj)] |
| 45 return DescendingValue(obj) |
| 46 |
| 47 def __init__(self, val): |
| 48 self.val = val |
| 49 |
| 50 def __cmp__(self, other): |
| 51 """Return -1, 0, or 1 base on the reverse of the normal sort order.""" |
| 52 if isinstance(other, DescendingValue): |
| 53 return cmp(other.val, self.val) |
| 54 else: |
| 55 return cmp(other, self.val) |
| 56 |
| 57 def __repr__(self): |
| 58 return 'DescendingValue(%r)' % self.val |
| 59 |
| 60 |
| 61 # A string that sorts after every other string, and one that sorts before them. |
| 62 MAX_STRING = '~~~' |
| 63 MIN_STRING = DescendingValue(MAX_STRING) |
| 64 |
| 65 |
| 66 # RAMCache {issue_id: {column_name: sort_key, ...}, ...} |
| 67 art_values_cache = None |
| 68 |
| 69 |
| 70 def InitializeArtValues(services): |
| 71 global art_values_cache |
| 72 art_values_cache = services.cache_manager.MakeCache( |
| 73 'issue', max_size=settings.issue_cache_max_size) |
| 74 |
| 75 |
| 76 def SortArtifacts( |
| 77 mr, artifacts, config, accessors, username_cols=None, users_by_id=None): |
| 78 """Return a list of artifacts sorted by the user's sort specification. |
| 79 |
| 80 In the following, an "accessor" is a function(art) -> [field_value, ...]. |
| 81 |
| 82 Args: |
| 83 mr: commonly used info parsed from the request, including query. |
| 84 artifacts: an unsorted list of project artifact PBs. |
| 85 config: Project config PB instance that defines the sort order for |
| 86 labels and statuses in this project. |
| 87 accessors: dictionary of (column_name -> accessor) to get values |
| 88 from the artifacts. |
| 89 username_cols: optional list of lowercase column names that will show |
| 90 user names. |
| 91 users_by_id: optional dictionary {user_id: user_view,...} for all users |
| 92 who participate in the list of artifacts. |
| 93 |
| 94 Returns: |
| 95 A sorted list of artifacts. |
| 96 |
| 97 Note: if username_cols is supplied, then users_by_id should be too. |
| 98 |
| 99 The approach to sorting is to construct a comprehensive sort key for |
| 100 each artifact. To create the sort key, we (a) build lists with a |
| 101 variable number of fields to sort on, and (b) allow individual |
| 102 fields to be sorted in descending order. Even with the time taken |
| 103 to build the sort keys, calling sorted() with the key seems to be |
| 104 faster overall than doing multiple stable-sorts or doing one sort |
| 105 using a multi-field comparison function. |
| 106 """ |
| 107 sort_directives = ComputeSortDirectives(mr, config) |
| 108 |
| 109 # Build a list of accessors that will extract sort keys from the issues. |
| 110 accessor_pairs = [ |
| 111 (sd, _MakeCombinedSortKeyAccessor( |
| 112 sd, config, accessors, username_cols, users_by_id)) |
| 113 for sd in sort_directives] |
| 114 |
| 115 def SortKey(art): |
| 116 """Make a sort_key for the given artifact, used by sorted() below.""" |
| 117 if art_values_cache.HasItem(art.issue_id): |
| 118 art_values = art_values_cache.GetItem(art.issue_id) |
| 119 else: |
| 120 art_values = {} |
| 121 |
| 122 sort_key = [] |
| 123 for sd, accessor in accessor_pairs: |
| 124 if sd not in art_values: |
| 125 art_values[sd] = accessor(art) |
| 126 sort_key.append(art_values[sd]) |
| 127 |
| 128 art_values_cache.CacheItem(art.issue_id, art_values) |
| 129 return sort_key |
| 130 |
| 131 return sorted(artifacts, key=SortKey) |
| 132 |
| 133 |
| 134 def ComputeSortDirectives(mr, config, tie_breaker='id'): |
| 135 """Return a list with sort directives to be used in sorting. |
| 136 |
| 137 Args: |
| 138 mr: commonly used info parsed from the request, including query. |
| 139 config: Project config PB instance that defines the sort order for |
| 140 labels and statuses in this project. |
| 141 tie_breaker: column name to add to the end of the sort spec if it is |
| 142 not already somewhere in the sort spec. |
| 143 |
| 144 Returns: |
| 145 A list of lower-case column names, each one may have a leading |
| 146 minus-sign. |
| 147 """ |
| 148 # Prepend the end-user's sort spec to any project default sort spec. |
| 149 sort_spec = '%s %s %s' % ( |
| 150 mr.group_by_spec, mr.sort_spec, config.default_sort_spec) |
| 151 # Sort specs can have interfering sort orders, so remove any duplicates. |
| 152 field_names = set() |
| 153 sort_directives = [] |
| 154 for sort_directive in sort_spec.lower().split(): |
| 155 field_name = sort_directive.lstrip('-') |
| 156 if field_name not in field_names: |
| 157 sort_directives.append(sort_directive) |
| 158 field_names.add(field_name) |
| 159 |
| 160 # Add in the project name so that the overall ordering is completely |
| 161 # defined in cross-project search. Otherwise, issues jump up and |
| 162 # down on each reload of the same query, and prev/next links get |
| 163 # messed up. It's a no-op in single projects. |
| 164 if 'project' not in sort_directives: |
| 165 sort_directives.append('project') |
| 166 |
| 167 if tie_breaker not in sort_directives: |
| 168 sort_directives.append(tie_breaker) |
| 169 |
| 170 return sort_directives |
| 171 |
| 172 |
| 173 def _MakeCombinedSortKeyAccessor( |
| 174 sort_directive, config, accessors, username_cols, users_by_id): |
| 175 """Return an accessor that extracts a sort key for a UI table column. |
| 176 |
| 177 Args: |
| 178 sort_directive: string with column name and optional leading minus sign, |
| 179 for combined columns, it may have slashes, e.g., "-priority/pri". |
| 180 config: ProjectIssueConfig instance that defines the sort order for |
| 181 labels and statuses in this project. |
| 182 accessors: dictionary of (column_name -> accessor) to get values |
| 183 from the artifacts. |
| 184 username_cols: list of lowercase names of columns that contain user names. |
| 185 users_by_id: dictionary {user_id: user_view,...} for all users |
| 186 who participate in the list of artifacts (e.g., owners, reporters, cc). |
| 187 |
| 188 Returns: |
| 189 A list of accessor functions that can be applied to an issue to extract |
| 190 the relevant sort key value. |
| 191 |
| 192 The strings for status and labels are converted to lower case in |
| 193 this method so that they sort like case-insensitive enumerations. |
| 194 Any component-specific field of the artifact is sorted according to the |
| 195 value returned by the accessors defined in that component. Those |
| 196 accessor functions should lower case string values for fields where |
| 197 case-insensitive sorting is desired. |
| 198 """ |
| 199 if sort_directive.startswith('-'): |
| 200 combined_col_name = sort_directive[1:] |
| 201 descending = True |
| 202 else: |
| 203 combined_col_name = sort_directive |
| 204 descending = False |
| 205 |
| 206 wk_labels = [wkl.label for wkl in config.well_known_labels] |
| 207 accessors = [ |
| 208 _MakeSingleSortKeyAccessor( |
| 209 col_name, config, accessors, username_cols, users_by_id, wk_labels) |
| 210 for col_name in combined_col_name.split('/')] |
| 211 |
| 212 # The most common case is that we sort on a single column, like "priority". |
| 213 if len(accessors) == 1: |
| 214 return _MaybeMakeDescending(accessors[0], descending) |
| 215 |
| 216 # Less commonly, we are sorting on a combined column like "priority/pri". |
| 217 def CombinedAccessor(art): |
| 218 """Flatten and sort the values for each column in a combined column.""" |
| 219 key_part = [] |
| 220 for single_accessor in accessors: |
| 221 value = single_accessor(art) |
| 222 if isinstance(value, list): |
| 223 key_part.extend(value) |
| 224 else: |
| 225 key_part.append(value) |
| 226 return sorted(key_part) |
| 227 |
| 228 return _MaybeMakeDescending(CombinedAccessor, descending) |
| 229 |
| 230 |
| 231 def _MaybeMakeDescending(accessor, descending): |
| 232 """If descending is True, return a new function that reverses accessor.""" |
| 233 if not descending: |
| 234 return accessor |
| 235 |
| 236 def DescendingAccessor(art): |
| 237 asc_value = accessor(art) |
| 238 return DescendingValue.MakeDescendingValue(asc_value) |
| 239 |
| 240 return DescendingAccessor |
| 241 |
| 242 |
| 243 def _MakeSingleSortKeyAccessor( |
| 244 col_name, config, accessors, username_cols, users_by_id, wk_labels): |
| 245 """Return an accessor function for a single simple UI column.""" |
| 246 # Case 1. Handle built-in fields: status, component. |
| 247 if col_name == 'status': |
| 248 wk_statuses = [wks.status for wks in config.well_known_statuses] |
| 249 return _IndexOrLexical(wk_statuses, accessors[col_name]) |
| 250 |
| 251 if col_name == 'component': |
| 252 comp_defs = sorted(config.component_defs, key=lambda cd: cd.path.lower()) |
| 253 comp_ids = [cd.component_id for cd in comp_defs] |
| 254 return _IndexListAccessor(comp_ids, accessors[col_name]) |
| 255 |
| 256 # Case 2. Any other defined accessor functions. |
| 257 if col_name in accessors: |
| 258 if username_cols and col_name in username_cols: |
| 259 # sort users by email address rather than user ids. |
| 260 return _UserEditNameAccessor(users_by_id, accessors[col_name]) |
| 261 else: |
| 262 return accessors[col_name] |
| 263 |
| 264 # Case 3. Anything else is assumed to be a label prefix or custom field. |
| 265 # TODO(jrobbins): user-valued custom fields. Find them at top of loop. |
| 266 fd_list = [ |
| 267 fd for fd in config.field_defs |
| 268 if (fd.field_name.lower() == col_name and |
| 269 fd.field_type != tracker_pb2.FieldTypes.ENUM_TYPE)] |
| 270 return _IndexOrLexicalList( |
| 271 wk_labels, fd_list, col_name, users_by_id) |
| 272 |
| 273 |
| 274 IGNORABLE_INDICATOR = -1 |
| 275 |
| 276 |
| 277 def _PrecomputeSortIndexes(values, col_name): |
| 278 """Precompute indexes of strings in the values list for fast lookup later.""" |
| 279 # Make a dictionary that immediately gives us the index of any value |
| 280 # in the list, and also add the same values in all-lower letters. In |
| 281 # the case where two values differ only by case, the later value wins, |
| 282 # which is fine. |
| 283 indexes = {} |
| 284 if col_name: |
| 285 prefix = col_name + '-' |
| 286 else: |
| 287 prefix = '' |
| 288 for idx, val in enumerate(values): |
| 289 if val.lower().startswith(prefix): |
| 290 indexes[val] = idx |
| 291 indexes[val.lower()] = idx |
| 292 else: |
| 293 indexes[val] = IGNORABLE_INDICATOR |
| 294 indexes[val.lower()] = IGNORABLE_INDICATOR |
| 295 |
| 296 return indexes |
| 297 |
| 298 |
| 299 def _UserEditNameAccessor(users_by_id, base_accessor): |
| 300 """Make an accessor that returns a list of user edit names for sorting. |
| 301 |
| 302 Args: |
| 303 users_by_id: dictionary {user_id: user_view, ...} for all participants |
| 304 in the entire list of artifacts. |
| 305 base_accessor: an accessor function f(artifact) -> user_id. |
| 306 |
| 307 Returns: |
| 308 An accessor f(artifact) -> value that can be used in sorting |
| 309 the decorated list. |
| 310 """ |
| 311 |
| 312 def Accessor(art): |
| 313 """Return a user edit name for the given artifact's base_accessor.""" |
| 314 id_or_id_list = base_accessor(art) |
| 315 if isinstance(id_or_id_list, list): |
| 316 emails = [users_by_id[user_id].email |
| 317 for user_id in id_or_id_list] |
| 318 else: |
| 319 emails = [users_by_id[id_or_id_list].email] |
| 320 |
| 321 return sorted(emails) or MAX_STRING |
| 322 |
| 323 return Accessor |
| 324 |
| 325 |
| 326 def _MakeColumnAccessor(col_name): |
| 327 """Make an accessor for an issue's labels that have col_name as a prefix. |
| 328 |
| 329 Args: |
| 330 col_name: string column name. |
| 331 |
| 332 Returns: |
| 333 An accessor that can be applied to an artifact to return a list of |
| 334 labels that have col_name as a prefix. |
| 335 |
| 336 For example, _MakeColumnAccessor('priority')(issue) could result in |
| 337 [], or ['priority-high'], or a longer list for multi-valued labels. |
| 338 """ |
| 339 prefix = col_name + '-' |
| 340 |
| 341 def Accessor(art): |
| 342 """Return a list of label values on the given artifact.""" |
| 343 result = [label.lower() for label in tracker_bizobj.GetLabels(art) |
| 344 if label.lower().startswith(prefix)] |
| 345 return result |
| 346 |
| 347 return Accessor |
| 348 |
| 349 |
| 350 def _IndexOrLexical(wk_values, base_accessor): |
| 351 """Return an accessor to score an artifact based on a user-defined ordering. |
| 352 |
| 353 Args: |
| 354 wk_values: a list of well-known status values from the config. |
| 355 base_accessor: function that gets a field from a given issue. |
| 356 |
| 357 Returns: |
| 358 An accessor that can be applied to an issue to return a suitable |
| 359 sort key. |
| 360 |
| 361 For example, when used to sort issue statuses, these accessors return an |
| 362 integer for well-known statuses, a string for odd-ball statuses, and an |
| 363 extreme value key for issues with no status. That causes issues to appear |
| 364 in the expected order with odd-ball issues sorted lexicographically after |
| 365 the ones with well-known status values, and issues with no defined status at |
| 366 the very end. |
| 367 """ |
| 368 well_known_value_indexes = _PrecomputeSortIndexes(wk_values, '') |
| 369 |
| 370 def Accessor(art): |
| 371 """Custom-made function to return a specific value of any issue.""" |
| 372 value = base_accessor(art) |
| 373 if not value: |
| 374 # Undefined values sort last. |
| 375 return MAX_STRING |
| 376 |
| 377 try: |
| 378 # Well-known values sort by index. Ascending sorting has positive ints |
| 379 # in well_known_value_indexes. |
| 380 return well_known_value_indexes[value] |
| 381 except KeyError: |
| 382 # Odd-ball values after well-known and lexicographically. |
| 383 return value.lower() |
| 384 |
| 385 return Accessor |
| 386 |
| 387 |
| 388 def _IndexListAccessor(wk_values, base_accessor): |
| 389 """Return an accessor to score an artifact based on a user-defined ordering. |
| 390 |
| 391 Args: |
| 392 wk_values: a list of well-known values from the config. |
| 393 base_accessor: function that gets a field from a given issue. |
| 394 |
| 395 Returns: |
| 396 An accessor that can be applied to an issue to return a suitable |
| 397 sort key. |
| 398 """ |
| 399 well_known_value_indexes = { |
| 400 val: idx for idx, val in enumerate(wk_values)} |
| 401 |
| 402 def Accessor(art): |
| 403 """Custom-made function to return a specific value of any issue.""" |
| 404 values = base_accessor(art) |
| 405 if not values: |
| 406 # Undefined values sort last. |
| 407 return MAX_STRING |
| 408 |
| 409 indexes = [well_known_value_indexes.get(val, MAX_STRING) for val in values] |
| 410 return sorted(indexes) |
| 411 |
| 412 return Accessor |
| 413 |
| 414 |
| 415 def _IndexOrLexicalList(wk_values, fd_list, col_name, users_by_id): |
| 416 """Return an accessor to score an artifact based on a user-defined ordering. |
| 417 |
| 418 Args: |
| 419 wk_values: A list of well-known labels from the config. |
| 420 fd_list: list of FieldDef PBs that match the column name. These might not |
| 421 all have the same field_type. Enum-type field are not included. |
| 422 col_name: lowercase string name of the column that will be sorted on. |
| 423 users_by_id: A dictionary {user_id: user_view}. |
| 424 |
| 425 Returns: |
| 426 An accessor that can be applied to an issue to return a suitable |
| 427 sort key. |
| 428 """ |
| 429 well_known_value_indexes = _PrecomputeSortIndexes(wk_values, col_name) |
| 430 |
| 431 def Accessor(art): |
| 432 """Custom-made function to return a sort value for any issue.""" |
| 433 idx_or_lex_list = ( |
| 434 _SortableFieldValues(art, fd_list, users_by_id) + |
| 435 _SortableLabelValues(art, col_name, well_known_value_indexes)) |
| 436 if not idx_or_lex_list: |
| 437 return MAX_STRING # issues with no value sort to the end of the list. |
| 438 return sorted(idx_or_lex_list) |
| 439 |
| 440 return Accessor |
| 441 |
| 442 |
| 443 def _SortableFieldValues(art, fd_list, users_by_id): |
| 444 """Return a list of field values relevant to one UI table column.""" |
| 445 sortable_value_list = [] |
| 446 for fd in fd_list: |
| 447 for fv in art.field_values: |
| 448 if fv.field_id == fd.field_id: |
| 449 sortable_value_list.append( |
| 450 tracker_bizobj.GetFieldValue(fv, users_by_id)) |
| 451 |
| 452 return sortable_value_list |
| 453 |
| 454 |
| 455 def _SortableLabelValues(art, col_name, well_known_value_indexes): |
| 456 """Return a list of ints and strings for labels relevant to one UI column.""" |
| 457 sortable_value_list = [] |
| 458 for label in tracker_bizobj.GetLabels(art): |
| 459 idx_or_lex = well_known_value_indexes.get(label) |
| 460 if idx_or_lex == IGNORABLE_INDICATOR: |
| 461 continue # Label is known to not have the desired prefix. |
| 462 if idx_or_lex is None: |
| 463 if '-' not in label: |
| 464 # Skip an irrelevant OneWord label and remember to ignore it later. |
| 465 well_known_value_indexes[label] = IGNORABLE_INDICATOR |
| 466 continue |
| 467 key, value = label.lower().split('-', 1) |
| 468 if key == col_name: |
| 469 # Label is a key-value label with an odd-ball value, remember it |
| 470 idx_or_lex = value |
| 471 well_known_value_indexes[label] = value |
| 472 else: |
| 473 # Label was a key-value label that is not relevant to this column. |
| 474 # Remember to ignore it later. |
| 475 well_known_value_indexes[label] = IGNORABLE_INDICATOR |
| 476 continue |
| 477 |
| 478 sortable_value_list.append(idx_or_lex) |
| 479 |
| 480 return sortable_value_list |
OLD | NEW |