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
 
+# TODO(shend): Improve documentation and add docstrings.
 
 # Temporary hard-coded list of extra fields.
 # TODO(shend): Put this into its own JSON5 file.
 EXTRA_FIELDS = [
     {'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': [
          "inline", "block", "list-item", "inline-block", "table", "inline-table", "table-row-group", "table-header-group",
@@ skipping 38 matching lines @@
     {'name': 'PseudoBits', 'field_template': 'storage_only', 'field_size': 8, 'default_value': 'kPseudoIdNone',
      'type_name': 'PseudoId', 'inherited': False, 'independent': False},
     # True if 'underline solid' is the only text decoration on this element.
     {'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},
+    # Fields that are shared by multiple properties.
+    # TODO(shend): Try to split these up to one field per property.
+    {'name': 'margin', 'field_template': 'storage_only', 'field_size': None, 'field_type_path': 'platform/LengthBox',
+     'type_name': 'LengthBox', 'field_group': 'surround', 'default_value': 'LengthBox(kFixed)', 'inherited': False,
+     'independent': False, 'has_custom_compare_and_copy': False},
+    {'name': 'padding', 'field_template': 'storage_only', 'field_size': None, 'field_type_path': 'platform/LengthBox',
+     'type_name': 'LengthBox', 'field_group': 'surround', 'default_value': 'LengthBox(kFixed)', 'inherited': False,
+     'independent': False, 'has_custom_compare_and_copy': False},
+    {'name': 'border', 'field_template': 'storage_only', 'field_size': None, 'field_type_path': 'core/style/BorderData',
+     'type_name': 'BorderData', 'field_group': 'surround', 'default_value': 'BorderData()', 'inherited': False,
+     'independent': False, 'has_custom_compare_and_copy': False},
 ]
 
 
+def _flatten_list(x):
+    """Flattens a list of lists into a single list."""
+    return list(chain.from_iterable(x))
+
+
+def _num_32_bit_words_for_bit_fields(bit_fields):
+    """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):
+    """Represents a group of fields stored together in a class.
+
+    Attributes:
+        name: The name of the group as a string.
+        subgroups: List of Group instances that are stored as subgroups under this group.
+        fields: List of Field instances stored directly under this group.
+    """
+    def __init__(self, name, subgroups, fields):
+        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_32_bit_words_for_bit_fields = _num_32_bit_words_for_bit_fields(
+            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.
 
     Most attributes in this class correspond to parameters in CSSProperties.json5.
     See that file for a more detailed explanation of each attribute.
 
     Attributes:
         field_role: The semantic role of the field. Can be:
             - 'property': for fields that store CSS properties
             - 'inherited_flag': for single-bit flags that store whether a property is
                                 inherited by this style or set explicitly
             - 'nonproperty': for fields that are not CSS properties
         name_for_methods: String used to form the names of getters and setters.
             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.
+        group_member_name: The class member name representing the group.

[meade_UTC10, 2017/04/20 03:08:40]

This is the first time you mention groups in this class doc - is it the group
the field is inside, or is it a group contained within the field?

[shend, 2017/04/20 03:22:34]

Clarified the comment.

         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, getter_method_name, setter_method_name,
-                 initial_method_name, **kwargs):
+                 field_template, field_group, size, default_value,
+                 getter_method_name, setter_method_name, initial_method_name, **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.group_member_name = class_member_name(field_group) if field_group else None
         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 20 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 group_member_name and returns the root group."""
+    groups = defaultdict(list)
+    for field in fields:
+        groups[field.group_member_name].append(field)
+
+    no_group = groups.pop(None)
+    subgroups = [Group(group_member_name, [], _reorder_fields(fields)) for group_member_name, 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 47 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,
         getter_method_name=property_['getter'],
         setter_method_name=property_['setter'],
         initial_method_name=property_['initial'],
     )
 
 
 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.
     """
     name_for_methods = join_name(property_['name_for_methods'], 'is inherited')
     return Field(
         'inherited_flag',
         name_for_methods,
         property_name=property_['name'],
         type_name='bool',
         field_template='primitive',
+        field_group=property_['field_group'],
         size=1,
         default_value='true',
         getter_method_name=method_name(name_for_methods),
         setter_method_name=method_name(join_name('set', name_for_methods)),
         initial_method_name=method_name(join_name('initial', name_for_methods)),
     )
 
 
 def _create_fields(properties):
     """
@@ skipping 10 matching lines @@
 
             # TODO(shend): Get rid of the property/nonproperty field roles.
             # If the field has_custom_compare_and_copy, then it does not appear in
             # ComputedStyle::operator== and ComputedStyle::CopyNonInheritedFromCached.
             field_role = 'nonproperty' if property_['has_custom_compare_and_copy'] else 'property'
             fields.append(_create_field(field_role, property_))
 
     return fields
 
 
-def _pack_fields(fields):
+def _reorder_fields(fields):
     """
-    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]

[meade_UTC10, 2017/04/20 03:08:40]

normal -> fields that are some type other than a bit field? bit_fields vs
non_bit_fields maybe?

[shend, 2017/04/20 03:22:34]

Changed to non_bit_fields.

+
     # 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)
 
         # Ignore shorthand properties
         for property_ in self._properties.values():
             if property_['field_template'] is not None:
                 assert not property_['longhands'], \
                     "Shorthand '{}' cannot have a field_template.".format(property_['name'])
 
         css_properties = [value for value in self._properties.values() if not value['longhands']]
 
         for property_ in css_properties:
             # All CSS properties that are generated do not have custom comparison and copy logic.
             property_['has_custom_compare_and_copy'] = False
             # CSS properties are not allowed to explicitly specify their field_size.
             property_['field_size'] = None
 
         # TODO(shend): Remove this once we move EXTRA_FIELDS to its own JSON file,
         # since the JSON5 reader will handle missing fields and defaults.
-        # 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 EXTRA_FIELDS:
             for parameter in self.json5_file.parameters:
                 if parameter not in property_:
                     property_[parameter] = None
 
         for property_ in EXTRA_FIELDS:
             # TODO(shend): Remove the line below once we move EXTRA_FIELDS to its
             # own file which would enforce defaults.
-            property_['has_custom_compare_and_copy'] = True
+            if 'has_custom_compare_and_copy' not in property_:
+                property_['has_custom_compare_and_copy'] = True
             make_style_builder.apply_property_naming_defaults(property_)
 
         all_properties = css_properties + EXTRA_FIELDS
 
         # Override the type name when field_type_path is specified
         for property_ in all_properties:
             if property_['field_type_path']:
                 property_['type_name'] = property_['field_type_path'].split('/')[-1]
 
         self._generated_enums = _create_enums(all_properties)
 
         all_fields = _create_fields(all_properties)
 
-        # 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]
-
-        # 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)
+        # Organise fields into a tree structure where the root group
+        # is ComputedStyleBase.
+        self._root_group = _group_fields(all_fields)
 
         self._include_paths = _get_include_paths(all_properties)
         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,
         }
 
     @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._root_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._root_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,
         }
 
 if __name__ == '__main__':
     json5_generator.Maker(ComputedStyleBaseWriter).main()