1# Copyright 2013 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5from telemetry.value import failure
6from telemetry.value import skip
7
8
9# TODO(eakuefner): Get rid of this as part of crbug.com/525688
10def DefaultKeyFunc(value):
11  """Keys values in a standard way for grouping in merging and summary.
12
13  Merging and summarization can be parameterized by a function that groups
14  values into equivalence classes. Any function that returns a comparable
15  object can be used as a key_func, but merge_values and summary both use this
16  function by default, to allow the default grouping to change as Telemtry does.
17
18  Args:
19    value: A Telemetry Value instance
20
21  Returns:
22    A comparable object used to group values.
23  """
24  # We use the name and tir_label because even in the TBMv2 case, right now
25  # metrics are responsible for mangling grouping keys into the name, and
26  # PageTestResults is responsible for mangling story grouping keys into the
27  # tir_label.
28  return value.name, value.tir_label
29
30
31def MergeLikeValuesFromSamePage(all_values, key_func=DefaultKeyFunc):
32  """Merges values that measure the same thing on the same page.
33
34  A page may end up being measured multiple times, meaning that we may end up
35  with something like this:
36       ScalarValue(page1, 'x', 1, 'foo')
37       ScalarValue(page2, 'x', 4, 'bar')
38       ScalarValue(page1, 'x', 2, 'foo')
39       ScalarValue(page2, 'x', 5, 'baz')
40
41  This function will produce:
42       ListOfScalarValues(page1, 'x', [1, 2], 'foo')
43       ListOfScalarValues(page2, 'x', [4], 'bar')
44       ListOfScalarValues(page2, 'x', [5], 'baz')
45
46  The workhorse of this code is Value.MergeLikeValuesFromSamePage.
47
48  This requires (but assumes) that the values passed in with the same grouping
49  key pass the Value.IsMergableWith test. If this is not obeyed, the
50  results will be undefined.
51  """
52  return _MergeLikeValuesCommon(
53      all_values,
54      lambda x: (x.page, key_func(x)),
55      lambda v0, merge_group: v0.MergeLikeValuesFromSamePage(merge_group))
56
57
58def MergeLikeValuesFromDifferentPages(all_values, key_func=DefaultKeyFunc):
59  """Merges values that measure the same thing on different pages.
60
61  After using MergeLikeValuesFromSamePage, one still ends up with values from
62  different pages:
63       ScalarValue(page1, 'x', 1, 'foo')
64       ScalarValue(page1, 'y', 30, 'bar')
65       ScalarValue(page2, 'x', 2, 'foo')
66       ScalarValue(page2, 'y', 40, 'baz')
67
68  This function will group values with the same name and tir_label together:
69       ListOfScalarValues(None, 'x', [1, 2], 'foo')
70       ListOfScalarValues(None, 'y', [30], 'bar')
71       ListOfScalarValues(None, 'y', [40], 'baz')
72
73  The workhorse of this code is Value.MergeLikeValuesFromDifferentPages.
74
75  Not all values that go into this function will come out: not every value can
76  be merged across pages. Values whose MergeLikeValuesFromDifferentPages returns
77  None will be omitted from the results.
78
79  This requires (but assumes) that the values passed in with the same name pass
80  the Value.IsMergableWith test. If this is not obeyed, the results
81  will be undefined.
82  """
83  return _MergeLikeValuesCommon(
84      all_values,
85      key_func,
86      lambda v0, merge_group: v0.MergeLikeValuesFromDifferentPages(merge_group))
87
88
89def _MergeLikeValuesCommon(all_values, key_func, merge_func):
90  """Groups all_values by key_func then applies merge_func to the groups.
91
92  This takes the all_values list and groups each item in that using the key
93  provided by key_func. This produces groups of values with like keys. Thes are
94  then handed to the merge_func to produce a new key. If merge_func produces a
95  non-None return, it is added to the list of returned values.
96  """
97  # When merging, we want to merge values in a consistent order, e.g. so that
98  # Scalar(1), Scalar(2) predictably produces ListOfScalarValues([1,2]) rather
99  # than 2,1.
100  #
101  # To do this, the values are sorted by key up front. Then, grouping is
102  # performed using a dictionary, but as new groups are found, the order in
103  # which they were found is also noted.
104  #
105  # Merging is then performed on groups in group-creation-order. This ensures
106  # that the returned array is in a stable order, group by group.
107  #
108  # Within a group, the order is stable because of the original sort.
109  all_values = list(all_values)
110  merge_groups = GroupStably(all_values, key_func)
111
112  res = []
113  for merge_group in merge_groups:
114    v0 = merge_group[0]
115    vM = merge_func(v0, merge_group)
116    if vM:
117      res.append(vM)
118  return res
119
120def GroupStably(all_values, key_func):
121  """Groups an array by key_func, with the groups returned in a stable order.
122
123  Returns a list of groups.
124  """
125  all_values = list(all_values)
126
127  merge_groups = {}
128  merge_groups_in_creation_order = []
129  for value in all_values:
130    # TODO(chrishenry): This is temporary. When we figure out the
131    # right summarization strategy for page runs with failures/skips, we
132    # should use that instead.
133    should_skip_value = (isinstance(value, failure.FailureValue) or
134                         isinstance(value, skip.SkipValue))
135
136    if should_skip_value:
137      continue
138
139    key = key_func(value)
140    if key not in merge_groups:
141      merge_groups[key] = []
142      merge_groups_in_creation_order.append(merge_groups[key])
143    merge_groups[key].append(value)
144  return merge_groups_in_creation_order
145