Hint about where to insert integer histogram enum values.

tools/metrics/histograms/extract_histograms.py

 # Copyright 2013 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Extract histogram names from the description XML file.
 
 For more information on the format of the XML file, which is self-documenting,
 see histograms.xml; however, here is a simple example to get you started. The
 XML below will generate the following five histograms:
 
@@ skipping 182 matching lines @@
       logging.error('Enums %s and %s are not in alphabetical order',
                     last_name, name)
       have_errors = True
     last_name = name
 
     if name in enums:
       logging.error('Duplicate enum %s', name)
       have_errors = True
       continue
 
-    last_int_value = None
     enum_dict = {}
     enum_dict['name'] = name
     enum_dict['values'] = {}
 
     for int_tag in enum.getElementsByTagName('int'):
       value_dict = {}
       int_value = int(int_tag.getAttribute('value'))
-      if last_int_value is not None and int_value < last_int_value:
-        logging.error('Enum %s int values %d and %d are not in numerical order',
-                      name, last_int_value, int_value)
-        have_errors = True
-      last_int_value = int_value
       if int_value in enum_dict['values']:
         logging.error('Duplicate enum value %d for enum %s', int_value, name)
         have_errors = True
         continue
       value_dict['label'] = int_tag.getAttribute('label')
       value_dict['summary'] = _JoinChildNodes(int_tag)
       enum_dict['values'][int_value] = value_dict
 
+    enum_items = sorted(enum_dict['values'].iteritems(), key=lambda i: i[0])
+    def _FindLeftEnumItemIndex(int_value):
+      """ Copy of bisect.bisect_left() modified to work with |enum_items|. """
+      lo = 0
+      hi = len(enum_items)
+      while lo < hi:
+          mid = (lo + hi) / 2
+          if enum_items[mid][0] < int_value: lo = mid + 1
+          else: hi = mid
+      return lo

[Ilya Sherman, 2017/04/11 21:34:25]

Rather than copying bisect.bisect_left(), could you instead create a list that
just has the integer values, and call bisect on it directly?

[DmitrySkiba, 2017/04/12 16:24:13]

Done.

+
+    last_int_value = None
+    for int_tag in enum.getElementsByTagName('int'):
+      int_value = int(int_tag.getAttribute('value'))
+      if last_int_value is not None and int_value < last_int_value:
+        logging.error('Enum %s int values %d and %d are not in numerical order',
+                      name, last_int_value, int_value)
+        have_errors = True
+        left_item_index = _FindLeftEnumItemIndex(int_value)
+        if left_item_index == 0:
+          logging.warning('Insert value %d at the beginning of enum %s',
+                          int_value, name)
+        else:
+          left_item_index -= 1
+          left_int_value, left_value_dict = enum_items[left_item_index]

[Ilya Sherman, 2017/04/11 21:34:25]

nit: It looks like the -1 calculation could be moved into this line.

[DmitrySkiba, 2017/04/12 16:24:13]

Done.

+          logging.warning('Insert value %d after %d ("%s")',
+                          int_value, left_int_value, left_value_dict['label'])
+      else:
+        last_int_value = int_value
+
     summary_nodes = enum.getElementsByTagName('summary')
     if summary_nodes:
       enum_dict['summary'] = _NormalizeString(_JoinChildNodes(summary_nodes[0]))
 
     enums[name] = enum_dict
 
   return enums, have_errors
 
 
 def _ExtractOwners(xml_node):
@@ skipping 275 matching lines @@
   with open(filename, 'r') as f:
     histograms, had_errors = ExtractHistogramsFromFile(f)
     if had_errors:
       logging.error('Error parsing %s', filename)
       raise Error()
     return histograms
 
 
 def ExtractNames(histograms):
   return sorted(histograms.keys())