• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
4def MergeLikeValuesFromSamePage(all_values):
5  """Merges values that measure the same thing on the same page.
6
7  A page may end up being measured multiple times, meaning that we may end up
8  with something like this:
9       ScalarValue(page1, 'x', 1)
10       ScalarValue(page2, 'x', 4)
11       ScalarValue(page1, 'x', 2)
12       ScalarValue(page2, 'x', 5)
13
14  This function will produce:
15       ListOfScalarValues(page1, 'x', [1, 2])
16       ListOfScalarValues(page2, 'x', [4, 5])
17
18  The workhorse of this code is Value.MergeLikeValuesFromSamePage.
19
20  This requires (but assumes) that the values passed in with the same grouping
21  key pass the Value.IsMergableWith test. If this is not obeyed, the
22  results will be undefined.
23  """
24  return _MergeLikeValuesCommon(
25      all_values,
26      lambda x: (x.page, x.name),
27      lambda v0, merge_group: v0.MergeLikeValuesFromSamePage(merge_group))
28
29
30def MergeLikeValuesFromDifferentPages(all_values, group_by_name_suffix=False):
31  """Merges values that measure the same thing on different pages.
32
33  After using MergeLikeValuesFromSamePage, one still ends up with values from
34  different pages:
35       ScalarValue(page1, 'x', 1)
36       ScalarValue(page1, 'y', 30)
37       ScalarValue(page2, 'x', 2)
38       ScalarValue(page2, 'y', 40)
39
40  This function will group the values of the same value_name together:
41       ListOfScalarValues(None, 'x', [1, 2])
42       ListOfScalarValues(None, 'y', [30, 40])
43
44  If group_by_name_suffix is True, then x.z and y.z are considered to be the
45  same value and are grouped together. If false, then x.z and y.z are
46  considered different.
47
48  The workhorse of this code is Value.MergeLikeValuesFromDifferentPages.
49
50  Not all values that go into this function will come out: not every value can
51  be merged across pages. Values whose MergeLikeValuesFromDifferentPages returns
52  None will be omitted from the results.
53
54  This requires (but assumes) that the values passed in with the same name pass
55  the Value.IsMergableWith test. If this is not obeyed, the results
56  will be undefined.
57  """
58  if group_by_name_suffix:
59    def key(value):
60      return value.name_suffix
61  else:
62    key = lambda x: x.name
63  return _MergeLikeValuesCommon(
64      all_values,
65      key,
66      lambda v0, merge_group: v0.MergeLikeValuesFromDifferentPages(
67          merge_group, group_by_name_suffix=group_by_name_suffix))
68
69
70def _MergeLikeValuesCommon(all_values, key_func, merge_func):
71  """Groups all_values by key_func then applies merge_func to the groups.
72
73  This takes the all_values list and groups each item in that using the key
74  provided by key_func. This produces groups of values with like keys. Thes are
75  then handed to the merge_func to produce a new key. If merge_func produces a
76  non-None return, it is added to the list of returned values.
77  """
78  # When merging, we want to merge values in a consistent order, e.g. so that
79  # Scalar(1), Scalar(2) predictably produces ListOfScalarValues([1,2]) rather
80  # than 2,1.
81  #
82  # To do this, the values are sorted by key up front. Then, grouping is
83  # performed using a dictionary, but as new groups are found, the order in
84  # which they were found is also noted.
85  #
86  # Merging is then performed on groups in group-creation-order. This ensures
87  # that the returned array is in a stable order, group by group.
88  #
89  # Within a group, the order is stable because of the original sort.
90  all_values = list(all_values)
91  merge_groups = GroupStably(all_values, key_func)
92
93  res = []
94  for merge_group in merge_groups:
95    v0 = merge_group[0]
96    vM = merge_func(v0, merge_group)
97    if vM:
98      res.append(vM)
99  return res
100
101def GroupStably(all_values, key_func):
102  """Groups an array by key_func, with the groups returned in a stable order.
103
104  Returns a list of groups.
105  """
106  all_values = list(all_values)
107
108  merge_groups = {}
109  merge_groups_in_creation_order = []
110  for value in all_values:
111    key = key_func(value)
112    if key not in merge_groups:
113      merge_groups[key] = []
114      merge_groups_in_creation_order.append(merge_groups[key])
115    merge_groups[key].append(value)
116  return merge_groups_in_creation_order
117