webkitpy: Improve performance of merge-results script.

third_party/WebKit/Tools/Scripts/webkitpy/layout_tests/merge_results.py

 # Copyright 2017 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.
 
 """Classes for merging layout tests results directories together.
 
 This is split into three parts:
 
  * Generic code to merge JSON data together.
  * Generic code to merge directories together.
@@ skipping 10 matching lines @@
  * Helper functions can be provided to deal with merging specific file objects.
  * Helper functions are called when a given Match object returns true for the
    filenames.
  * The default helper functions only merge if file contents match or the file
    only exists in one input directory.
 
 The quickest way to understand how the mergers, helper functions and match
 objects work together is to look at the unit tests.
 """
 
+import collections
+import itertools
 import json
 import logging
 import pprint
 import re
 import types
 
 from webkitpy.common.system.filesystem import FileSystem
 
 
 _log = logging.getLogger(__name__)
@@ skipping 46 matching lines @@
     def __init__(self, value):
         self.value = value
 
     def __call__(self, obj, name=None):
         return obj == self.value
 
 
 class MergeFailure(Exception):
     """Base exception for merge failing."""
 
-    def __init__(self, msg, name, obj_a, obj_b):
+    def __init__(self, msg, name, objs):
         emsg = (
             "Failure merging {name}: "
-            " {msg}\nTrying to merge {a} and {b}."
+            " {msg}\nTrying to merge {objs}."
         ).format(
             name=name,
             msg=msg,
-            a=obj_a,
-            b=obj_b,
+            objs=objs,
         )
         Exception.__init__(self, emsg)
 
     @classmethod
-    def assert_type_eq(cls, name, obj_a, obj_b):
-        if type(obj_a) != type(obj_b):
-            raise cls("Types don't match", name, obj_a, obj_b)
+    def assert_type_eq(cls, name, objs):
+        obj_0 = objs[0]
+        for obj_n in objs[1:]:
+            if type(obj_0) != type(obj_n):
+                raise cls("Types don't match", name, (obj_0, obj_n))
 
 
 class Merger(object):
     """Base class for merger objects."""
 
     def __init__(self):
         self.helpers = []
 
     def add_helper(self, match_func, merge_func):
         """Add function which merges values.
@@ skipping 10 matching lines @@
 class JSONMerger(Merger):
     """Merge two JSON-like objects.
 
     For adding helpers;
 
         match_func is a function of form
             def f(obj, name=None) -> bool
         When the function returns true, the merge_func will be called.
 
         merge_func is a function of the form
-            def f(obj_a, obj_b, name=None) -> obj_merged
+            def f(list_of_objs, name=None) -> obj_merged
         Merge functions should *never* modify the input arguments.
     """
 
     def __init__(self):
         Merger.__init__(self)
 
         self.add_helper(
             TypeMatch(types.ListType, types.TupleType), self.merge_listlike)
         self.add_helper(
             TypeMatch(types.DictType), self.merge_dictlike)
 
-    def fallback_matcher(self, obj_a, obj_b, name=None):
+    def fallback_matcher(self, objs, name=None):
         raise MergeFailure(
-            "No merge helper found!", name, obj_a, obj_b)
+            "No merge helper found!", name, objs)
 
-    def merge_equal(self, obj_a, obj_b, name=None):
+    def merge_equal(self, objs, name=None):
         """Merge two equal objects together."""

[alancutter (OOO until 2018), 2017/04/19 07:43:43]

Remove "two".

[mithro, 2017/04/19 08:38:39]

Done.

-        if obj_a != obj_b:
-            raise MergeFailure(
-                "Unable to merge!", name, obj_a, obj_b)
-        return obj_a
+        obj_0 = objs[0]
+        for obj_n in objs[1:]:
+            if obj_0 != obj_n:
+                raise MergeFailure(
+                    "Unable to merge!", name, (obj_0, obj_n))
+        return obj_0
 
-    def merge_listlike(self, list_a, list_b, name=None):  # pylint: disable=unused-argument
+    def merge_listlike(self, lists, name=None):  # pylint: disable=unused-argument
         """Merge two things which are "list like" (tuples, lists, sets)."""

[alancutter (OOO until 2018), 2017/04/19 07:43:43]

Remove "two".

[mithro, 2017/04/19 08:38:39]

Done.

-        assert type(list_a) == type(list_b), (
-            "Types of %r and %r don't match, refusing to merge." % (
-                list_a, list_b))
-        output = list(list_a)
-        output.extend(list_b)
-        return list_a.__class__(output)
+        list_0 = lists[0]
+        for list_n in lists[1:]:
+            assert type(list_0) == type(list_n), (
+                "Types of %r and %r don't match, refusing to merge." % (
+                    list_0, list_n))
+        output = list(list_0)
+        for list_n in lists[1:]:
+            output.extend(list_n)
+        return list_0.__class__(output)
 
-    def merge_dictlike(self, dict_a, dict_b, name=None):
+    def merge_dictlike(self, dicts, name=None):
         """Merge two things which are dictionaries."""

[alancutter (OOO until 2018), 2017/04/19 07:43:43]

Remove "two".

[mithro, 2017/04/19 08:38:39]

Done.

-        assert type(dict_a) == type(dict_b), (
-            "Types of %r and %r don't match, refusing to merge." % (
-                dict_a, dict_b))
-        dict_out = dict_a.__class__({})
-        for key in dict_a.keys() + dict_b.keys():
-            if key in dict_a and key in dict_b:
+        dict_0 = dicts[0]
+        for dict_n in dicts[1:]:
+            assert type(dict_0) == type(dict_n), (
+                "Types of %r and %r don't match, refusing to merge." % (
+                    dict_0, dict_n))

[alancutter (OOO until 2018), 2017/04/19 07:43:43]

I think this is worth pulling out as a helper assert function. One that probably
would live in MergeFailure.

[mithro, 2017/04/19 08:38:39]

Done.

+
+        ordered_keys = collections.OrderedDict.fromkeys(

[mcgreevy, 2017/04/19 06:57:20]

Why do you need an OrderedDict here?  Can't you just use a Set?

[mithro, 2017/04/19 08:38:39]

Set doesn't preserve the order and OrderedSet doesn't exist.

[mcgreevy, 2017/04/20 00:08:25]

Right, but why do you need to preserve the order?  The use of OrderedDict
implies that preserving the order is necessary, but as far as I can tell, it
isn't. This harms readability, as I spend extra time studying the code trying to
figure out why the key order needs to be preserved. If there is indeed a reason
why the key order must be preserved, please add a comment explaining why.  If in
fact the key order is not significant, please use a Set instead.

[mithro, 2017/04/20 02:02:44]

I've added documentation on this.

+            itertools.chain(*(d.iterkeys() for d in dicts)))
+
+        dict_out = dict_0.__class__({})
+        for key in ordered_keys:
+            values_to_merge = []
+            for dobj in dicts:

[mcgreevy, 2017/04/19 06:57:20]

This nested for loop looks up every key in every dictionary.  An alternative
would be to not build up ordered_keys in the first place, but instead build up a
dict of

{key: [values to merge]}

then once you've finished building this, iterate over it, merging the values. 
It would probably be faster at the cost of using more RAM.

[mithro, 2017/04/19 08:38:39]

I tried implementing this and it made no difference to run time (within the
bounds of error).

+                if key in dobj:
+                    values_to_merge.append(dobj[key])
+
+            if len(values_to_merge) == 1:
+                dict_out[key] = values_to_merge[0]
+            elif len(values_to_merge) > 1:
                 dict_out[key] = self.merge(
-                    dict_a[key], dict_b[key],
+                    values_to_merge,
                     name=join_name(name, key))
-            elif key in dict_a:
-                dict_out[key] = dict_a[key]
-            elif key in dict_b:
-                dict_out[key] = dict_b[key]
             else:
-                assert False
+                assert False, "Key %s not found in any inputs!" % (key,)
         return dict_out
 
-    def merge(self, obj_a, obj_b, name=""):
+    def merge(self, objs, name=""):
         """Generic merge function.
 
         name is a string representing the current key value separated by
         semicolons. For example, if file.json had the following;
 
             {'key1': {'key2': 3}}
 
         Then the name of the value 3 is 'file.json:key1:key2'
         """
-        if obj_a is None and obj_b is None:
+        objs = [o for o in objs if o is not None]
+
+        if not objs:
             return None
-        elif obj_b is None:
-            return obj_a
-        elif obj_a is None:
-            return obj_b
 
-        MergeFailure.assert_type_eq(name, obj_a, obj_b)
+        obj_0 = objs[0]
+        for obj_n in objs[1:]:
+            MergeFailure.assert_type_eq(name, (obj_0, obj_n))
 
         # Try the merge helpers.
         for match_func, merge_func in reversed(self.helpers):
-            if match_func(obj_a, name):
-                return merge_func(obj_a, obj_b, name=name)
-            if match_func(obj_b, name):
-                return merge_func(obj_a, obj_b, name=name)
+            for obj in objs:

[alancutter (OOO until 2018), 2017/04/19 07:43:43]

Seems strange that it needs to test against every object, what fails if it only
calls match_func() against the first object?

+                if match_func(obj, name):
+                    return merge_func(objs, name=name)
 
-        return self.fallback_matcher(obj_a, obj_b, name=name)
+        return self.fallback_matcher(objs, name=name)
 
 
 # Classes for recursively merging a directory together.
 # ------------------------------------------------------------------------
 
 
 class FilenameMatch(object):
     """Match based on name matching a regex."""
 
     def __init__(self, regex):
@@ skipping 37 matching lines @@
         for filename in to_merge[1:]:
             other_data = self.filesystem.read_binary_file(filename)
             if data != other_data:
                 nonmatching.append(filename)
 
         if nonmatching:
             raise MergeFailure(
                 '\n'.join(
                     ['File contents don\'t match:'] + nonmatching),
                 out_filename,
-                to_merge[0], to_merge[1:])
+                to_merge)
 
         self.filesystem.write_binary_file(out_filename, data)
 
 
 class MergeFilesLinesSorted(MergeFiles):
     """Merge and sort the files of the given files."""
 
     def __call__(self, out_filename, to_merge):
         lines = []
         for filename in to_merge:
@@ skipping 26 matching lines @@
         output.
     """
 
     def __init__(self, filesystem, json_data_merger=None, json_data_value_overrides=None):
         MergeFiles.__init__(self, filesystem)
         self._json_data_merger = json_data_merger or JSONMerger()
         self._json_data_value_overrides = json_data_value_overrides or {}
 
     def __call__(self, out_filename, to_merge):
         try:
-            before_a, output_data, after_a = self.load_jsonp(
+            before_0, new_json_data_0, after_0 = self.load_jsonp(
                 self.filesystem.open_binary_file_for_reading(to_merge[0]))
         except ValueError as e:
-            raise MergeFailure(e.message, to_merge[0], None, None)
+            raise MergeFailure(e.message, to_merge[0], None)
 
-        for filename in to_merge[1:]:
+        input_data = [new_json_data_0]
+        for filename_n in to_merge[1:]:
             try:
-                before_b, new_json_data, after_b = self.load_jsonp(
-                    self.filesystem.open_binary_file_for_reading(filename))
+                beforen, new_json_data_n, aftern = self.load_jsonp(
+                    self.filesystem.open_binary_file_for_reading(filename_n))
             except ValueError as e:
-                raise MergeFailure(e.message, filename, None, None)
+                raise MergeFailure(e.message, filename_n, None)
 
-            if before_a != before_b:
+            if before_0 != beforen:
                 raise MergeFailure(
-                    "jsonp starting data from %s doesn't match." % filename,
+                    "jsonp starting data from %s doesn't match." % filename_n,
                     out_filename,
-                    before_a, before_b)
+                    [before_0, beforen])
 
-            if after_a != after_b:
+            if after_0 != aftern:
                 raise MergeFailure(
-                    "jsonp ending data from %s doesn't match." % filename,
+                    "jsonp ending data from %s doesn't match." % filename_n,
                     out_filename,
-                    after_a, after_b)
+                    [after_0, aftern])
 
-            output_data = self._json_data_merger.merge(output_data, new_json_data, filename)
+            input_data.append(new_json_data_n)
 
+        output_data = self._json_data_merger.merge(input_data, name=out_filename)
         output_data.update(self._json_data_value_overrides)
 
         self.dump_jsonp(
             self.filesystem.open_binary_file_for_writing(out_filename),
-            before_a, output_data, after_a)
+            before_0, output_data, after_0)
 
     @staticmethod
     def load_jsonp(fd):
         """Load a JSONP file and return the JSON data parsed.
 
         JSONP files have a JSON data structure wrapped in a function call or
         other non-JSON data.
         """
         in_data = fd.read()
 
@@ skipping 92 matching lines @@
                     # rel_file is the path of f relative to the base directory
                     rel_file = self.filesystem.join(dir_path, f)[len(base_dir) + 1:]
                     files.setdefault(rel_file, []).append(base_dir)
 
         # Go through each file and try to merge it.
         # partial_file_path is the file relative to the directories.
         for partial_file_path, in_dirs in sorted(files.iteritems()):
             out_path = self.filesystem.join(output_dir, partial_file_path)
             if self.filesystem.exists(out_path):
                 raise MergeFailure(
-                    'File %s already exist in output.', out_path, None, None)
+                    'File %s already exist in output.', out_path, None)
 
             dirname = self.filesystem.dirname(out_path)
             if not self.filesystem.exists(dirname):
                 self.filesystem.maybe_make_directory(dirname)
 
             to_merge = [self.filesystem.join(d, partial_file_path) for d in in_dirs]
 
             _log.debug("Creating merged %s from %s", out_path, to_merge)
 
             for match_func, merge_func in reversed(self.helpers):
@@ skipping 50 matching lines @@
             ':num_passes$',
             ':num_regressions$',
             ':skipped$',
             ':skips$',
             # All keys inside the num_failures_by_type entry.
             ':num_failures_by_type:',
         ]
         for match_name in addable:
             self.add_helper(
                 NameMatch(match_name),
-                lambda a, b, name=None: a + b)
+                lambda o, name=None: sum(o))
 
         # If any shard is interrupted, mark the whole thing as interrupted.
         self.add_helper(
             NameMatch(':interrupted$'),
-            lambda a, b, name=None: a or b)
+            lambda o, name=None: bool(sum(o)))
 
         # Layout test directory value is randomly created on each shard, so
         # clear it.
         self.add_helper(
             NameMatch(':layout_tests_dir$'),
-            lambda a, b, name=None: None)
+            lambda o, name=None: None)
 
         # seconds_since_epoch is the start time, so we just take the earliest.
         self.add_helper(
             NameMatch(':seconds_since_epoch$'),
-            lambda a, b, name=None: min(a, b))
+            lambda o, name=None: min(*o))
 
-    def fallback_matcher(self, obj_a, obj_b, name=None):
+    def fallback_matcher(self, objs, name=None):
         if self.allow_unknown_if_matching:
-            result = self.merge_equal(obj_a, obj_b, name)
+            result = self.merge_equal(objs, name)
             _log.warning('Unknown value %s, accepting anyway as it matches.', name)
             return result
-        return JSONMerger.fallback_matcher(self, obj_a, obj_b, name)
+        return JSONMerger.fallback_matcher(self, objs, name)
 
 
 class LayoutTestDirMerger(DirMerger):
     """Merge layout test result directory."""
 
     def __init__(self, filesystem=None,
                  results_json_value_overrides=None,
                  results_json_allow_unknown_if_matching=False):
         DirMerger.__init__(self, filesystem)
 
         # JSON merger for non-"result style" JSON files.
         basic_json_data_merger = JSONMerger()
         basic_json_data_merger.fallback_matcher = basic_json_data_merger.merge_equal
         self.add_helper(
-            FilenameMatch('\\.json'),
+            FilenameMatch('\\.json$'),
             MergeFilesJSONP(self.filesystem, basic_json_data_merger))
 
         # access_log and error_log are httpd log files which are sortable.
         self.add_helper(
-            FilenameMatch('access_log\\.txt'),
+            FilenameMatch('access_log\\.txt$'),
             MergeFilesLinesSorted(self.filesystem))
         self.add_helper(
-            FilenameMatch('error_log\\.txt'),
+            FilenameMatch('error_log\\.txt$'),
             MergeFilesLinesSorted(self.filesystem))
 
         # pywebsocket files aren't particularly useful, so just save them.
         self.add_helper(
-            FilenameMatch('pywebsocket\\.ws\\.log-.*-err.txt'),
+            FilenameMatch('pywebsocket\\.ws\\.log-.*-err\\.txt$'),
             MergeFilesKeepFiles(self.filesystem))
 
         # These JSON files have "result style" JSON in them.
         results_json_file_merger = MergeFilesJSONP(
             self.filesystem,
             JSONTestResultsMerger(
                 allow_unknown_if_matching=results_json_allow_unknown_if_matching),
             json_data_value_overrides=results_json_value_overrides or {})
 
         self.add_helper(
-            FilenameMatch('failing_results.json'),
+            FilenameMatch('failing_results\\.json$'),
             results_json_file_merger)
         self.add_helper(
-            FilenameMatch('full_results.json'),
+            FilenameMatch('full_results\\.json$'),
             results_json_file_merger)
         self.add_helper(
-            FilenameMatch('output.json'),
+            FilenameMatch('output\\.json$'),
             results_json_file_merger)