Generate subgroup StyleSurroundData in ComputedStyle.

third_party/WebKit/Source/build/scripts/make_computed_style_base.py

 #!/usr/bin/env python
 # Copyright 2016 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.
 
 import math
 import sys
 
 import json5_generator
 import template_expander
 import make_style_builder
 
 from name_utilities import (
     enum_for_css_keyword, enum_type_name, enum_value_name, class_member_name, method_name,
-    join_name
+    class_name, join_name
 )
-from collections import OrderedDict
+from collections import defaultdict, OrderedDict
+from itertools import chain
 
 
 # Temporary hard-coded list of fields that are not CSS properties.
 # TODO(shend): Put this into its own JSON5 file.
 NONPROPERTIES = [
     {'name': 'IsLink', 'field_template': 'monotonic_flag',
      'inherited': False, 'independent': False, 'default_value': False},
     {'name': 'OriginalDisplay', 'field_template': 'keyword', 'default_value': 'inline',
      'type_name': 'EDisplay', 'inherited': False, 'independent': False,
      'keywords': [
@@ skipping 34 matching lines @@
     {'name': 'HasSimpleUnderline', 'field_template': 'storage_only', 'field_size': 1, 'default_value': 'false',
      'type_name': 'bool', 'inherited': True, 'independent': False},
     # TODO(shend): vertical align is actually a CSS property, but since we don't support union fields
     # which can be either a keyword or Length, this is generated as a nonproperty for now. Remove this
     # once we can support union fields and groups.
     {'name': 'VerticalAlign', 'field_template': 'storage_only', 'field_size': 4, 'default_value': 'EVerticalAlign::kBaseline',
      'type_name': 'EVerticalAlign', 'inherited': False, 'independent': False},
 ]
 
 
+def _flatten_list(x):
+    """Flattens a list of lists into a single list."""
+    return list(chain.from_iterable(x))
+
+
+def _num_bit_field_buckets(bit_fields):

[meade_UTC10, 2017/04/06 03:29:57]

would this be better as something like

_num_32_bit_words_for_bit_fields

?

[shend, 2017/04/06 04:39:39]

Done.

+    """Gets the number of 32 bit unsigned integers needed store a list of bit fields."""
+    num_buckets, cur_bucket = 0, 0
+    for field in bit_fields:
+        if field.size + cur_bucket > 32:
+            num_buckets += 1
+            cur_bucket = 0
+        cur_bucket += field.size
+    return num_buckets + (cur_bucket > 0)
+
+
+class Group(object):
+    def __init__(self, name, subgroups, fields):
+        """Represents a group of fields, which may contain subgroups that are dynamically allocated."""

[meade_UTC10, 2017/04/06 03:29:57]

Could you please document the types of the parameters? This will get more and
more important as the Python code gets bigger. 

Perhaps a followup CL could improve the documentation in this file (including
the parameter types, and things like below in field.__init__ the doc is "creates
a new field", which is completely useless).

[shend, 2017/04/06 04:39:39]

Agreed, the documentation in this file could be significantly improved.

+        self.name = name
+        self.subgroups = subgroups
+        self.fields = fields
+        self.type_name = class_name(join_name('style', name, ' data'))
+        self.member_name = class_member_name(name)
+        self.num_bit_field_buckets = _num_bit_field_buckets(field for field in fields if field.is_bit_field)
+
+        # Recursively get all the fields in the subgroups as well
+        self.all_fields = _flatten_list(subgroup.all_fields for subgroup in subgroups) + fields
+
+
 class Field(object):
     """
     The generated ComputedStyle object is made up of a series of Fields.
     Each Field has a name, size, type, etc, and a bunch of attributes to
     determine which methods it will be used in.
 
     A Field also has enough information to use any storage type in C++, such as
     regular member variables, or more complex storage like vectors or hashmaps.
     Almost all properties will have at least one Field, often more than one.
 
@@ skipping 10 matching lines @@
             Should be in upper camel case.
         property_name: Name of the property that the field is part of.
         type_name: Name of the C++ type exposed by the generated interface (e.g. EClear, int).
         field_template: Determines the interface generated for the field. Can be one of:
            keyword, flag, or monotonic_flag.
         size: Number of bits needed for storage.
         default_value: Default value for this field when it is first initialized.
     """
 
     def __init__(self, field_role, name_for_methods, property_name, type_name,
-                 field_template, size, default_value, **kwargs):
+                 field_template, field_group, size, default_value, **kwargs):
         """Creates a new field."""
         self.name = class_member_name(name_for_methods)
         self.property_name = property_name
         self.type_name = type_name
         self.field_template = field_template
+        self.field_group = field_group
         self.size = size
         self.default_value = default_value
 
         # Field role: one of these must be true
         self.is_property = field_role == 'property'
         self.is_inherited_flag = field_role == 'inherited_flag'
         self.is_nonproperty = field_role == 'nonproperty'
         assert (self.is_property, self.is_inherited_flag, self.is_nonproperty).count(True) == 1, \
             'Field role has to be exactly one of: property, inherited_flag, nonproperty'
 
@@ skipping 21 matching lines @@
     """
     Get a list of paths that need to be included for ComputedStyleBase.
     """
     include_paths = set()
     for property_ in properties:
         if property_['field_type_path'] is not None:
             include_paths.add(property_['field_type_path'] + '.h')
     return list(sorted(include_paths))
 
 
+def _group_fields(fields):
+    """Groups a list of fields by their field_group and returns the root group."""
+    groups = defaultdict(list)
+    for field in fields:
+        groups[field.field_group].append(field)
+
+    no_group = groups.pop(None)
+    subgroups = [Group(field_group, [], _reorder_fields(fields)) for field_group, fields in groups.items()]
+    return Group('', subgroups=subgroups, fields=_reorder_fields(no_group))
+
+
 def _create_enums(properties):
     """
     Returns an OrderedDict of enums to be generated, enum name -> [list of enum values]
     """
     enums = {}
     for property_ in properties:
         # Only generate enums for keyword properties that use the default field_type_path.
         if property_['field_template'] == 'keyword' and property_['field_type_path'] is None:
             enum_name = property_['type_name']
             enum_values = [enum_value_name(k) for k in property_['keywords']]
@@ skipping 43 matching lines @@
         size = 1
 
     return Field(
         field_role,
         name_for_methods,
         property_name=property_['name'],
         inherited=property_['inherited'],
         independent=property_['independent'],
         type_name=type_name,
         field_template=property_['field_template'],
+        field_group=property_['field_group'],
         size=size,
         default_value=default_value,
     )
 
 
 def _create_inherited_flag_field(property_):
     """
     Create the field used for an inheritance fast path from an independent CSS property,
     and return the Field object.
     """
     return Field(
         'inherited_flag',
         join_name(property_['name_for_methods'], 'is inherited'),
         property_name=property_['name'],
         type_name='bool',
         field_template='flag',
+        field_group=property_['field_group'],
         size=1,
         default_value='true',
     )
 
 
 def _create_fields(field_role, properties):
     """
     Create ComputedStyle fields from properties or nonproperties and return a list of Field objects.
     """
     fields = []
     for property_ in properties:
         # Only generate properties that have a field template
         if property_['field_template'] is not None:
             # If the property is independent, add the single-bit sized isInherited flag
             # to the list of Fields as well.
             if property_['independent']:
                 fields.append(_create_inherited_flag_field(property_))
 
             fields.append(_create_field(field_role, property_))
 
     return fields
 
 
-def _pack_fields(fields):
+def _reorder_fields(fields):

[meade_UTC10, 2017/04/06 03:29:57]

You're still doing packing though? I don't think this is a helpful renaming...

maybe something like _reorder_and_pack_members?

[shend, 2017/04/06 04:39:39]

For me, packing means the compiler "packing" the struct. What we're doing is
"reordering" so that the compiler can "pack" the struct.

     """
-    Group a list of fields into buckets to minimise padding.
-    Returns a list of buckets, where each bucket is a list of Field objects.
+    Returns a list of fields ordered to minimise padding.
     """
+    # Separate out bit fields from normal fields
+    bit_fields = [field for field in fields if field.is_bit_field]
+    normal_fields = [field for field in fields if not field.is_bit_field]
+
     # Since fields cannot cross word boundaries, in order to minimize
     # padding, group fields into buckets so that as many buckets as possible
     # are exactly 32 bits. Although this greedy approach may not always
     # produce the optimal solution, we add a static_assert to the code to
     # ensure ComputedStyleBase results in the expected size. If that
     # static_assert fails, this code is falling into the small number of
     # cases that are suboptimal, and may need to be rethought.
     # For more details on packing bit fields to reduce padding, see:
     # http://www.catb.org/esr/structure-packing/#_bitfields
     field_buckets = []
     # Consider fields in descending order of size to reduce fragmentation
     # when they are selected. Ties broken in alphabetical order by name.
-    for field in sorted(fields, key=lambda f: (-f.size, f.name)):
+    for field in sorted(bit_fields, key=lambda f: (-f.size, f.name)):
         added_to_bucket = False
         # Go through each bucket and add this field if it will not increase
         # the bucket's size to larger than 32 bits. Otherwise, make a new
         # bucket containing only this field.
         for bucket in field_buckets:
             if sum(f.size for f in bucket) + field.size <= 32:
                 bucket.append(field)
                 added_to_bucket = True
                 break
         if not added_to_bucket:
             field_buckets.append([field])
 
-    return field_buckets
+    # Normal fields go first, then the bit fields.
+    return list(normal_fields) + _flatten_list(field_buckets)
 
 
 class ComputedStyleBaseWriter(make_style_builder.StyleBuilderWriter):
     def __init__(self, json5_file_path):
         super(ComputedStyleBaseWriter, self).__init__(json5_file_path)
         self._outputs = {
             'ComputedStyleBase.h': self.generate_base_computed_style_h,
             'ComputedStyleBase.cpp': self.generate_base_computed_style_cpp,
             'ComputedStyleBaseConstants.h': self.generate_base_computed_style_constants,
             'CSSValueIDMappingsGenerated.h': self.generate_css_value_mappings,
         }
 
         # TODO(shend): Remove this once we move NONPROPERTIES to its own JSON file,
         # since the JSON5 reader will handle missing fields and defaults.
         for property_ in NONPROPERTIES:
             property_['name_for_methods'] = property_['name']
             if 'field_type_path' not in property_:
                 property_['field_type_path'] = None
             if 'type_name' not in property_:
                 property_['type_name'] = 'E' + enum_type_name(property_['name_for_methods'])
+            if 'field_group' not in property_:
+                property_['field_group'] = None
 
         property_values = self._properties.values()
 
         # Override the type name when field_type_path is specified
         for property_ in property_values:
             if property_['field_type_path']:
                 property_['type_name'] = property_['field_type_path'].split('/')[-1]
 
         self._generated_enums = _create_enums(property_values + NONPROPERTIES)
 
-        all_fields = (_create_fields('property', property_values) +
-                      _create_fields('nonproperty', NONPROPERTIES))
+        fields = (_create_fields('property', property_values) +
+                  _create_fields('nonproperty', NONPROPERTIES))
 
-        # Separate the normal fields from the bit fields
-        bit_fields = [field for field in all_fields if field.is_bit_field]
-        normal_fields = [field for field in all_fields if not field.is_bit_field]
+        # Separate fields into groups
+        self._base_group = _group_fields(fields)
 
-        # Pack bit fields into buckets
-        field_buckets = _pack_fields(bit_fields)
-
-        # The expected size of ComputedStyleBase is equivalent to as many words
-        # as the total number of buckets.
-        self._expected_bit_field_bytes = len(field_buckets)
-
-        # The most optimal size of ComputedStyleBase is the total sum of all the
-        # field sizes, rounded up to the nearest word. If this produces the
-        # incorrect value, either the packing algorithm is not optimal or there
-        # is no way to pack the fields such that excess padding space is not
-        # added.
-        # If this fails, increase extra_padding_bytes by 1, but be aware that
-        # this also increases ComputedStyleBase by 1 word.
-        # We should be able to bring extra_padding_bytes back to 0 from time to
-        # time.
-        extra_padding_bytes = 0
-        optimal_bit_field_bytes = int(math.ceil(sum(f.size for f in bit_fields) / 32.0))
-        real_bit_field_bytes = optimal_bit_field_bytes + extra_padding_bytes
-        assert self._expected_bit_field_bytes == real_bit_field_bytes, \
-            ('The field packing algorithm produced %s bytes, optimal is %s bytes' %
-             (self._expected_bit_field_bytes, real_bit_field_bytes))
-
-        # Normal fields go first, then the bit fields.
-        self._fields = list(normal_fields)
-
-        # Order the fields so fields in each bucket are adjacent.
-        for bucket in field_buckets:
-            for field in bucket:
-                self._fields.append(field)
-
-        self._include_paths = _get_include_paths(property_values + NONPROPERTIES)
-
+        # Get include paths

[meade_UTC10, 2017/04/06 03:29:57]

Is this really a helpful comment? :p

[shend, 2017/04/06 04:39:40]

lol, removed.

+        self._include_paths = _get_include_paths(property_values)
 
     @template_expander.use_jinja('ComputedStyleBase.h.tmpl')
     def generate_base_computed_style_h(self):
         return {
             'properties': self._properties,
             'enums': self._generated_enums,
             'include_paths': self._include_paths,
-            'fields': self._fields,
+            'computed_style': self._base_group,
         }
 
     @template_expander.use_jinja('ComputedStyleBase.cpp.tmpl')
     def generate_base_computed_style_cpp(self):
         return {
             'properties': self._properties,
             'enums': self._generated_enums,
-            'fields': self._fields,
-            'expected_bit_field_bytes': self._expected_bit_field_bytes,
+            'computed_style': self._base_group,
         }
 
     @template_expander.use_jinja('ComputedStyleBaseConstants.h.tmpl')
     def generate_base_computed_style_constants(self):
         return {
             'properties': self._properties,
             'enums': self._generated_enums,
-            'fields': self._fields,
         }
 
     @template_expander.use_jinja('CSSValueIDMappingsGenerated.h.tmpl')
     def generate_css_value_mappings(self):
         mappings = {}
 
         for property_ in self._properties.values():
             if property_['field_template'] == 'keyword':
                 mappings[property_['type_name']] = {
                     'default_value': enum_value_name(property_['default_value']),
                     'mapping': [(enum_value_name(k), enum_for_css_keyword(k)) for k in property_['keywords']],
                 }
 
         return {
             'include_paths': self._include_paths,
             'mappings': mappings,
         }
 
 if __name__ == '__main__':
     json5_generator.Maker(ComputedStyleBaseWriter).main()