Bug 1469893 - Make the metadata update generate more compact conditionals, r=maja_zf
authorJames Graham <james@hoppipolla.co.uk>
Mon, 24 Jun 2019 08:54:11 +0000
changeset 479923 1fc3a0502508a5043886f9b7de020d82fec674d9
parent 479922 0e43d60936b7d215438d38567b9a76fa84943e4c
child 479924 3bce3ca779f0084be8cba237f00502b1201daa95
push id113504
push userncsoregi@mozilla.com
push dateMon, 24 Jun 2019 15:34:16 +0000
treeherdermozilla-inbound@d30796cfdeb9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmaja_zf
bugs1469893
milestone69.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1469893 - Make the metadata update generate more compact conditionals, r=maja_zf Previously the wpt metadata update code generated rather conservative conditionals, simply inclusing every possible condition unless all the tests had the same outcome or similar. This isn't very nice to read and makes the metadata rather fragile to changes in the configuration. A better approach is to build a decision tree from the metadata, choosing the properties to split on using a simple greedy algorithm, as follows: * Given a set of test results, associated run_info_properties and properties that we want to use, partition the test results by each property we are using in turn. * For each partition, generate a score for how uniform the results are in each subset after partition. The score should be good if the partition results in small numbers of groups with mostly uniform test results and bad if it results in a large number of groups or groups with a mix of test results. For this we adopt a metric based on the Shannon entropy. * Chose the partition resulting in the best score, and use that as a condition in the tree. * Recursively reapply the algorithm to each group that's been created. Differential Revision: https://phabricator.services.mozilla.com/D34734
testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/firefox.py
testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servo.py
testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servodriver.py
testing/web-platform/tests/tools/wptrunner/wptrunner/expectedtree.py
testing/web-platform/tests/tools/wptrunner/wptrunner/manifestupdate.py
testing/web-platform/tests/tools/wptrunner/wptrunner/metadata.py
testing/web-platform/tests/tools/wptrunner/wptrunner/products.py
testing/web-platform/tests/tools/wptrunner/wptrunner/tests/test_expectedtree.py
testing/web-platform/tests/tools/wptrunner/wptrunner/tests/test_update.py
testing/web-platform/tests/tools/wptrunner/wptrunner/update/metadata.py
testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/backends/conditional.py
testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/node.py
testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/parser.py
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/firefox.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/firefox.py
@@ -173,18 +173,18 @@ def run_info_browser_version(binary):
         version_info = None
     if version_info:
         return {"browser_build_id": version_info.get("application_buildid", None),
                 "browser_changeset": version_info.get("application_changeset", None)}
     return {}
 
 
 def update_properties():
-    return (["debug", "webrender", "e10s", "os", "version", "processor", "bits"],
-            {"debug", "e10s", "webrender"})
+    return (["os", "debug", "webrender", "e10s", "sw-e10s", "processor"],
+            {"os": ["version"], "processor": ["bits"]})
 
 
 class FirefoxBrowser(Browser):
     init_timeout = 70
     shutdown_timeout = 70
 
     def __init__(self, logger, binary, prefs_root, test_type, extra_prefs=None, debug_info=None,
                  symbols_path=None, stackwalk_binary=None, certutil_binary=None,
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servo.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servo.py
@@ -56,17 +56,17 @@ def env_extras(**kwargs):
 def env_options():
     return {"server_host": "127.0.0.1",
             "bind_address": False,
             "testharnessreport": "testharnessreport-servo.js",
             "supports_debugger": True}
 
 
 def update_properties():
-    return ["debug", "os", "version", "processor", "bits"], None
+    return ["debug", "os", "processor"], {"os": ["version"], "processor": ["bits"]}
 
 
 class ServoBrowser(NullBrowser):
     def __init__(self, logger, binary, debug_info=None, binary_args=None,
                  user_stylesheets=None, ca_certificate_path=None):
         NullBrowser.__init__(self, logger)
         self.binary = binary
         self.debug_info = debug_info
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servodriver.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/browsers/servodriver.py
@@ -58,17 +58,17 @@ def env_extras(**kwargs):
 
 def env_options():
     return {"server_host": "127.0.0.1",
             "testharnessreport": "testharnessreport-servodriver.js",
             "supports_debugger": True}
 
 
 def update_properties():
-    return ["debug", "os", "version", "processor", "bits"], None
+    return {["debug", "os", "processor"], {"os": ["version"], "processor": ["bits"]}
 
 
 def write_hosts_file(config):
     hosts_fd, hosts_path = tempfile.mkstemp()
     with os.fdopen(hosts_fd, "w") as f:
         f.write(make_hosts_file(config, "127.0.0.1"))
     return hosts_path
 
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/expectedtree.py
@@ -0,0 +1,128 @@
+from math import log
+from collections import defaultdict
+
+class Node(object):
+    def __init__(self, prop, value):
+        self.prop = prop
+        self.value = value
+        self.parent = None
+
+        self.children = set()
+
+        # Populated for leaf nodes
+        self.run_info = set()
+        self.result_values = set()
+
+    def add(self, node):
+        self.children.add(node)
+        node.parent = self
+
+    def __iter__(self):
+        yield self
+        for node in self.children:
+            for item in node:
+                yield item
+
+    def __len__(self):
+        return 1 + sum(len(item) for item in self.children)
+
+
+def entropy(results):
+    """This is basically a measure of the uniformity of the values in results
+    based on the shannon entropy"""
+
+    result_counts = defaultdict(int)
+    total = float(len(results))
+    for values in results.itervalues():
+        # Not sure this is right, possibly want to treat multiple values as
+        # distinct from multiple of the same value?
+        for value in values:
+            result_counts[value] += 1
+
+    entropy_sum = 0
+
+    for count in result_counts.itervalues():
+        prop = float(count) / total
+        entropy_sum -= prop * log(prop, 2)
+
+    return entropy_sum
+
+
+def split_results(prop, results):
+    """Split a dictionary of results into a dictionary of dictionaries where
+    each sub-dictionary has a specific value of the given property"""
+    by_prop = defaultdict(dict)
+    for run_info, value in results.iteritems():
+        by_prop[run_info[prop]][run_info] = value
+
+    return by_prop
+
+
+def build_tree(properties, dependent_props, results, tree=None):
+    """Build a decision tree mapping properties to results
+
+    :param properties: - A list of run_info properties to consider
+                         in the tree
+    :param dependent_props: - A dictionary mapping property name
+                              to properties that should only be considered
+                              after the properties in the key. For example
+                              {"os": ["version"]} means that "version" won't
+                              be used until after os.
+    :param results: Dictionary mapping run_info to set of results
+    :tree: A Node object to use as the root of the (sub)tree"""
+
+    if tree is None:
+        tree = Node(None, None)
+
+    prop_index = {prop: i for i, prop in enumerate(properties)}
+
+    all_results = set()
+    for result_values in results.itervalues():
+        all_results |= result_values
+
+    # If there is only one result we are done
+    if not properties or len(all_results) == 1:
+        tree.result_values |= all_results
+        tree.run_info |= set(results.keys())
+        return tree
+
+    results_partitions = []
+    remove_properties = set()
+    for prop in properties:
+        result_sets = split_results(prop, results)
+        if len(result_sets) == 1:
+            # If this property doesn't partition the space then just remove it
+            # from the set to consider
+            remove_properties.add(prop)
+            continue
+        new_entropy = 0.
+        results_sets_entropy = []
+        for prop_value, result_set in result_sets.iteritems():
+            results_sets_entropy.append((entropy(result_set), prop_value, result_set))
+            new_entropy += (float(len(result_set)) / len(results)) * results_sets_entropy[-1][0]
+
+        results_partitions.append((new_entropy,
+                                   prop,
+                                   results_sets_entropy))
+
+    # In the case that no properties partition the space
+    if not results_partitions:
+        tree.result_values |= all_results
+        tree.run_info |= set(results.keys())
+        return tree
+
+    # split by the property with the highest entropy
+    results_partitions.sort(key=lambda x: (x[0], prop_index[x[1]]))
+    _, best_prop, sub_results = results_partitions[0]
+
+    # Create a new set of properties that can be used
+    new_props = properties[:prop_index[best_prop]] + properties[prop_index[best_prop] + 1:]
+    new_props.extend(dependent_props.get(best_prop, []))
+    if remove_properties:
+        new_props = [item for item in new_props if item not in remove_properties]
+
+    for _, prop_value, results_sets in sub_results:
+        node = Node(best_prop, prop_value)
+        tree.add(node)
+        build_tree(new_props, dependent_props, results_sets, node)
+    return tree
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/manifestupdate.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/manifestupdate.py
@@ -1,22 +1,25 @@
 from __future__ import print_function
 import itertools
 import os
 from six.moves.urllib.parse import urljoin
-from collections import namedtuple, defaultdict
+from collections import namedtuple, defaultdict, deque
 from math import ceil
 
+from wptmanifest import serialize
 from wptmanifest.node import (DataNode, ConditionalNode, BinaryExpressionNode,
-                              BinaryOperatorNode, VariableNode, StringNode, NumberNode,
-                              UnaryExpressionNode, UnaryOperatorNode, KeyValueNode)
+                              BinaryOperatorNode, NumberNode, StringNode, VariableNode,
+                              ValueNode, UnaryExpressionNode, UnaryOperatorNode, KeyValueNode,
+                              ListNode)
 from wptmanifest.backends import conditional
 from wptmanifest.backends.conditional import ManifestItem
 
 import expected
+import expectedtree
 
 """Manifest structure used to update the expected results of a test
 
 Each manifest file is represented by an ExpectedManifest that has one
 or more TestNode children, one per test in the manifest.  Each
 TestNode has zero or more SubtestNode children, one for each known
 subtest of the test.
 
@@ -52,45 +55,79 @@ def data_cls_getter(output_node, visited
     elif isinstance(output_node, ExpectedManifest):
         return TestNode
     elif isinstance(output_node, TestNode):
         return SubtestNode
     else:
         raise ValueError
 
 
+class UpdateProperties(object):
+    def __init__(self, manifest, **kwargs):
+        self._manifest = manifest
+        self._classes = kwargs
+
+    def __getattr__(self, name):
+        if name in self._classes:
+            rv = self._classes[name](self._manifest)
+            setattr(self, name, rv)
+            return rv
+        raise AttributeError
+
+    def __contains__(self, name):
+        return name in self._classes
+
+    def __iter__(self):
+        for name in self._classes.iterkeys():
+            yield getattr(self, name)
+
+
 class ExpectedManifest(ManifestItem):
-    def __init__(self, node, test_path=None, url_base=None, property_order=None,
-                 boolean_properties=None):
+    def __init__(self, node, test_path, url_base, run_info_properties):
         """Object representing all the tests in a particular manifest
 
         :param node: AST Node associated with this object. If this is None,
                      a new AST is created to associate with this manifest.
         :param test_path: Path of the test file associated with this manifest.
         :param url_base: Base url for serving the tests in this manifest.
-        :param property_order: List of properties to use in expectation metadata
-                               from most to least significant.
-        :param boolean_properties: Set of properties in property_order that should
-                                   be treated as boolean.
+        :param run_info_properties: Tuple of ([property name],
+                                              {property_name: [dependent property]})
+                                    The first part lists run_info properties
+                                    that are always used in the update, the second
+                                    maps property names to additional properties that
+                                    can be considered if we already have a condition on
+                                    the key property e.g. {"foo": ["bar"]} means that
+                                    we consider making conditions on bar only after we
+                                    already made one on foo.
         """
         if node is None:
             node = DataNode(None)
         ManifestItem.__init__(self, node)
         self.child_map = {}
         self.test_path = test_path
         self.url_base = url_base
         assert self.url_base is not None
-        self.modified = False
-        self.boolean_properties = boolean_properties
-        self.property_order = property_order
-        self.update_properties = {
-            "lsan": LsanUpdate(self),
-            "leak-object": LeakObjectUpdate(self),
-            "leak-threshold": LeakThresholdUpdate(self),
-        }
+        self._modified = False
+        self.run_info_properties = run_info_properties
+
+        self.update_properties = UpdateProperties(self, **{
+            "lsan": LsanUpdate,
+            "leak_object": LeakObjectUpdate,
+            "leak_threshold": LeakThresholdUpdate,
+        })
+
+    @property
+    def modified(self):
+        if self._modified:
+            return True
+        return any(item.modified for item in self.children)
+
+    @modified.setter
+    def modified(self, value):
+        self._modified = value
 
     def append(self, child):
         ManifestItem.append(self, child)
         if child.id in self.child_map:
             print("Warning: Duplicate heading %s" % child.id)
         self.child_map[child.id] = child
 
     def _remove_child(self, child):
@@ -118,57 +155,57 @@ class ExpectedManifest(ManifestItem):
                        "/".join(self.test_path.split(os.path.sep)))
 
     def set_lsan(self, run_info, result):
         """Set the result of the test in a particular run
 
         :param run_info: Dictionary of run_info parameters corresponding
                          to this run
         :param result: Lsan violations detected"""
-
-        self.update_properties["lsan"].set(run_info, result)
+        self.update_properties.lsan.set(run_info, result)
 
     def set_leak_object(self, run_info, result):
         """Set the result of the test in a particular run
 
         :param run_info: Dictionary of run_info parameters corresponding
                          to this run
         :param result: Leaked objects deletec"""
-
-        self.update_properties["leak-object"].set(run_info, result)
+        self.update_properties.leak_object.set(run_info, result)
 
     def set_leak_threshold(self, run_info, result):
         """Set the result of the test in a particular run
 
         :param run_info: Dictionary of run_info parameters corresponding
                          to this run
         :param result: Total number of bytes leaked"""
-
-        self.update_properties["leak-threshold"].set(run_info, result)
+        self.update_properties.leak_threshold.set(run_info, result)
 
-    def coalesce_properties(self, stability):
-        for prop_update in self.update_properties.itervalues():
-            prop_update.coalesce(stability)
+    def update(self, stability):
+        for prop_update in self.update_properties:
+            prop_update.update(stability)
 
 
 class TestNode(ManifestItem):
     def __init__(self, node):
         """Tree node associated with a particular test in a manifest
 
         :param node: AST node associated with the test"""
 
         ManifestItem.__init__(self, node)
         self.subtests = {}
         self._from_file = True
         self.new_disabled = False
-        self.update_properties = {
-            "expected": ExpectedUpdate(self),
-            "max-asserts": MaxAssertsUpdate(self),
-            "min-asserts": MinAssertsUpdate(self)
-        }
+        self.has_result = False
+        self.modified = False
+        self.update_properties = UpdateProperties(
+            self,
+            expected=ExpectedUpdate,
+            max_asserts=MaxAssertsUpdate,
+            min_asserts=MinAssertsUpdate
+        )
 
     @classmethod
     def create(cls, test_id):
         """Create a TestNode corresponding to a given test
 
         :param test_type: The type of the test
         :param test_id: The id of the test"""
 
@@ -207,47 +244,24 @@ class TestNode(ManifestItem):
 
     def set_result(self, run_info, result):
         """Set the result of the test in a particular run
 
         :param run_info: Dictionary of run_info parameters corresponding
                          to this run
         :param result: Status of the test in this run"""
 
-        self.update_properties["expected"].set(run_info, result)
+        self.update_properties.expected.set(run_info, result)
 
     def set_asserts(self, run_info, count):
         """Set the assert count of a test
 
         """
-        self.update_properties["min-asserts"].set(run_info, count)
-        self.update_properties["max-asserts"].set(run_info, count)
-
-    def _add_key_value(self, node, values):
-        ManifestItem._add_key_value(self, node, values)
-        if node.data in self.update_properties:
-            new_updated = []
-            self.update_properties[node.data].updated = new_updated
-            for value in values:
-                new_updated.append((value, []))
-
-    def clear(self, key):
-        """Clear all the expected data for this test and all of its subtests"""
-
-        self.updated = []
-        if key in self._data:
-            for child in self.node.children:
-                if (isinstance(child, KeyValueNode) and
-                    child.data == key):
-                    child.remove()
-                    del self._data[key]
-                    break
-
-        for subtest in self.subtests.itervalues():
-            subtest.clear(key)
+        self.update_properties.min_asserts.set(run_info, count)
+        self.update_properties.max_asserts.set(run_info, count)
 
     def append(self, node):
         child = ManifestItem.append(self, node)
         self.subtests[child.name] = child
 
     def get_subtest(self, name):
         """Return a SubtestNode corresponding to a particular subtest of
         the current test, creating a new one if no subtest with that name
@@ -257,19 +271,19 @@ class TestNode(ManifestItem):
 
         if name in self.subtests:
             return self.subtests[name]
         else:
             subtest = SubtestNode.create(name)
             self.append(subtest)
             return subtest
 
-    def coalesce_properties(self, stability):
-        for prop_update in self.update_properties.itervalues():
-            prop_update.coalesce(stability)
+    def update(self, stability):
+        for prop_update in self.update_properties:
+            prop_update.update(stability)
 
 
 class SubtestNode(TestNode):
     def __init__(self, node):
         assert isinstance(node, DataNode)
         TestNode.__init__(self, node)
 
     @classmethod
@@ -280,457 +294,431 @@ class SubtestNode(TestNode):
 
     @property
     def is_empty(self):
         if self._data:
             return False
         return True
 
 
+def build_conditional_tree(_, run_info_properties, results):
+    properties, dependent_props = run_info_properties
+    return expectedtree.build_tree(properties, dependent_props, results)
+
+
+def build_unconditional_tree(_, run_info_properties, results):
+    root = expectedtree.Node(None, None)
+    for run_info, value in results.iteritems():
+        root.result_values |= value
+        root.run_info.add(run_info)
+    return root
+
+
 class PropertyUpdate(object):
     property_name = None
     cls_default_value = None
     value_type = None
+    property_builder = None
 
     def __init__(self, node):
         self.node = node
-        self.updated = []
-        self.new = []
         self.default_value = self.cls_default_value
-
-    def set(self, run_info, in_value):
-        self.check_default(in_value)
-        value = self.get_value(in_value)
+        self.has_result = False
+        self.results = defaultdict(set)
 
-        # Add this result to the list of results satisfying
-        # any condition in the list of updated results it matches
-        for (cond, values) in self.updated:
-            if cond(run_info):
-                values.append(Value(run_info, value))
-                if value != cond.value_as(self.value_type):
-                    self.node.root.modified = True
-                break
-        else:
-            # We didn't find a previous value for this
-            self.new.append(Value(run_info, value))
-            self.node.root.modified = True
+    def run_info_by_condition(self, run_info_index, conditions):
+        run_info_by_condition = defaultdict(list)
+        # A condition might match 0 or more run_info values
+        run_infos = run_info_index.keys()
+        for cond in conditions:
+            for run_info in run_infos:
+                if cond(run_info):
+                    run_info_by_condition[cond].append(run_info)
+
+        return run_info_by_condition
+
+    def set(self, run_info, value):
+        self.has_result = True
+        self.node.has_result = True
+        self.check_default(value)
+        value = self.from_result_value(value)
+        self.results[run_info].add(value)
 
     def check_default(self, result):
         return
 
-    def get_value(self, in_value):
-        return in_value
+    def from_result_value(self, value):
+        """Convert a value from a test result into the internal format"""
+        return value
+
+    def from_ini_value(self, value):
+        """Convert a value from an ini file into the internal format"""
+        if self.value_type:
+            return self.value_type(value)
+        return value
+
+    def to_ini_value(self, value):
+        """Convert a value from the internal format to the ini file format"""
+        return str(value)
 
-    def coalesce(self, stability=None):
+    def updated_value(self, current, new):
+        """Given a single current value and a set of observed new values,
+        compute an updated value for the property"""
+        return new
+
+    @property
+    def unconditional_value(self):
+        try:
+            unconditional_value = self.from_ini_value(
+                self.node.get(self.property_name))
+        except KeyError:
+            unconditional_value = self.default_value
+        return unconditional_value
+
+    def update(self, stability=None, full_update=False):
         """Update the underlying manifest AST for this test based on all the
         added results.
 
         This will update existing conditionals if they got the same result in
         all matching runs in the updated results, will delete existing conditionals
         that get more than one different result in the updated run, and add new
         conditionals for anything that doesn't match an existing conditional.
 
         Conditionals not matched by any added result are not changed.
 
         When `stability` is not None, disable any test that shows multiple
         unexpected results for the same set of parameters.
         """
+        if not self.has_result:
+            return
 
-        try:
-            unconditional_value = self.node.get(self.property_name)
-            if self.value_type:
-                unconditional_value = self.value_type(unconditional_value)
-        except KeyError:
-            unconditional_value = self.default_value
+        property_tree = self.property_builder(self.node.root.run_info_properties,
+                                              self.results)
+
+        conditions, errors = self.update_conditions(property_tree, full_update)
 
-        for conditional_value, results in self.updated:
-            if not results:
-                # The conditional didn't match anything in these runs so leave it alone
-                pass
-            elif all(results[0].value == result.value for result in results):
-                # All the new values for this conditional matched, so update the node
-                result = results[0]
-                if (result.value == unconditional_value and
-                    conditional_value.condition_node is not None):
-                    if self.property_name in self.node:
-                        self.node.remove_value(self.property_name, conditional_value)
-                else:
-                    conditional_value.value = self.update_value(conditional_value.value_as(self.value_type),
-                                                                result.value)
-            elif conditional_value.condition_node is not None:
-                # Blow away the existing condition and rebuild from scratch
-                # This isn't sure to work if we have a conditional later that matches
-                # these values too, but we can hope, verify that we get the results
-                # we expect, and if not let a human sort it out
-                self.node.remove_value(self.property_name, conditional_value)
-                self.new.extend(results)
-            elif conditional_value.condition_node is None:
-                self.new.extend(result for result in results
-                                if result.value != unconditional_value)
+        for e in errors:
+            if stability and e.cond:
+                self.node.set("disabled", stability or "unstable",
+                              e.cond.children[0])
+                self.node.new_disabled = True
+            else:
+                msg = "Conflicting metadata values for %s" % (
+                    self.node.root.test_path)
+                if e.cond:
+                    msg += ": %s" % serialize(e.cond).strip()
+                print(msg)
 
-        # It is an invariant that nothing in new matches an existing
-        # condition except for the default condition
-        if self.new:
-            update_default, new_default_value = self.update_default()
-            if update_default:
-                if new_default_value != self.default_value:
+        if self.node.modified:
+            self.node.clear(self.property_name)
+
+            for condition, value in conditions:
+                if condition is None or value != self.unconditional_value:
                     self.node.set(self.property_name,
-                                  self.update_value(unconditional_value, new_default_value),
-                                  condition=None)
-            else:
+                                  self.to_ini_value(value),
+                                  condition
+                                  if condition is not None else None)
+
+    def update_conditions(self, property_tree, full_update):
+        current_conditions = self.node.get_conditions(self.property_name)
+        conditions = []
+        errors = []
+
+        run_info_index = {run_info: node
+                          for node in property_tree
+                          for run_info in node.run_info}
+
+        node_by_run_info = {run_info: node
+                            for (run_info, node) in run_info_index.iteritems()
+                            if node.result_values}
+
+        run_info_by_condition = self.run_info_by_condition(run_info_index,
+                                                           current_conditions)
+
+        run_info_with_condition = set()
+
+        # Retain existing conditions if they match the updated values
+        for condition in current_conditions:
+            # All run_info that isn't handled by some previous condition
+            all_run_infos_condition = run_info_by_condition[condition]
+            run_infos = {item for item in all_run_infos_condition
+                         if item not in run_info_with_condition}
+
+            if not run_infos:
+                # Retain existing conditions that don't match anything in the update
+                if not full_update:
+                    conditions.append((condition.condition_node,
+                                       self.from_ini_value(condition.value)))
+                continue
+
+            # Set of nodes in the updated tree that match the same run_info values as the
+            # current existing node
+            nodes = [node_by_run_info[run_info] for run_info in run_infos
+                     if run_info in node_by_run_info]
+            # If all the values are the same, update the value
+            if nodes and all(node.result_values == nodes[0].result_values for node in nodes):
+                current_value = self.from_ini_value(condition.value)
                 try:
-                    self.add_new(unconditional_value, stability)
-                except UpdateError as e:
-                    print("%s for %s, cannot update %s" % (e, self.node.root.test_path,
-                                                           self.property_name))
+                    new_value = self.updated_value(current_value,
+                                                   nodes[0].result_values)
+                except ConditionError as e:
+                    errors.append(e)
+                    continue
+                if new_value != current_value:
+                    self.node.modified = True
+                conditions.append((condition.condition_node, new_value))
+                run_info_with_condition |= set(run_infos)
+            else:
+                # Don't append this condition
+                self.node.modified = True
 
-        # Remove cases where the value matches the default
-        if (self.property_name in self.node._data and
-            len(self.node._data[self.property_name]) > 0 and
-            self.node._data[self.property_name][-1].condition_node is None and
-            self.node._data[self.property_name][-1].value_as(self.value_type) == self.default_value):
+        new_conditions, new_errors = self.build_tree_conditions(property_tree,
+                                                                run_info_with_condition)
+        conditions.extend(new_conditions)
+        errors.extend(new_errors)
 
-            self.node.remove_value(self.property_name, self.node._data[self.property_name][-1])
+        # Re-add the default if there isn't one
+        if (current_conditions and
+            current_conditions[-1].condition_node is None and
+            conditions[-1][0] is not None):
+            conditions.append((current_conditions[-1].condition_node,
+                               self.from_ini_value(current_conditions[-1].value)))
 
-        # Remove empty properties
-        if (self.property_name in self.node._data and len(self.node._data[self.property_name]) == 0):
-            for child in self.node.children:
-                if (isinstance(child, KeyValueNode) and child.data == self.property_name):
-                    child.remove()
-                    break
+        # Don't add a condition to set the default whatever the class default is
+        if (conditions and
+            conditions[-1][0] is None and
+            conditions[-1][1] == self.default_value):
+            conditions = conditions[:-1]
 
-    def update_default(self):
-        """Get the updated default value for the property (i.e. the one chosen when no conditions match).
+        if full_update:
+            # Check if any new conditions match what's going to become the
+            # unconditional value
+            new_unconditional_value = (conditions[-1][1]
+                                       if conditions[-1][0] is None
+                                       else self.unconditional_value)
+
+            if any(item[1] == new_unconditional_value for item in conditions
+                   if item[0] is not None):
+                self.remove_default(run_info_index, conditions, new_unconditional_value)
+        return conditions, errors
+
+    def build_tree_conditions(self, property_tree, run_info_with_condition):
+        conditions = []
+        errors = []
 
-        :returns: (update, new_default_value) where updated is a bool indicating whether the property
-                  should be updated, and new_default_value is the value to set if it should."""
-        raise NotImplementedError
-
-    def add_new(self, unconditional_value, stability):
-        """Add new conditional values for the property.
+        queue = deque([(property_tree, [])])
+        while queue:
+            node, parents = queue.popleft()
+            parents_and_self = parents + [node]
+            if node.result_values and any(run_info not in run_info_with_condition
+                                          for run_info in node.run_info):
+                prop_set = [(item.prop, item.value) for item in parents_and_self if item.prop]
+                value = node.result_values
+                error = None
+                if parents:
+                    try:
+                        value = self.updated_value(None, value)
+                    except ConditionError:
+                        expr = make_expr(prop_set, value)
+                        error = ConditionError(expr)
+                    expr = make_expr(prop_set, value)
+                else:
+                    # The root node needs special handling
+                    expr = None
+                    value = self.updated_value(self.unconditional_value,
+                                               value)
+                if error is None:
+                    conditions.append((expr, value))
+                else:
+                    errors.append(error)
 
-        Subclasses need not implement this if they only ever update the default value."""
-        raise NotImplementedError
+            for child in node.children:
+                queue.append((child, parents_and_self))
+
+        if conditions:
+            self.node.modified = True
+        return conditions[::-1], errors
 
-    def update_value(self, old_value, new_value):
-        """Get a value to set on the property, given its previous value and the new value from logs.
-
-        By default this just returns the new value, but overriding is useful in cases
-        where we want the new value to be some function of both old and new e.g. max(old_value, new_value)"""
-        return new_value
+    def remove_default(self, run_info_index, conditions, new_unconditional_value):
+        # Remove any conditions that match the default value and won't
+        # be overridden by a later conditional
+        conditions = []
+        matched_run_info = set()
+        run_infos = self.run_info_index.keys()
+        for idx, (cond, value) in enumerate(reversed(conditions)):
+            if not cond:
+                continue
+            run_info_for_cond = set(run_info for run_info in run_infos if cond(run_info))
+            if (value == new_unconditional_value and
+                not run_info_for_cond & matched_run_info):
+                pass
+            else:
+                conditions.append((cond, value))
+            matched_run_info |= run_info_for_cond
+        return conditions[::-1]
 
 
 class ExpectedUpdate(PropertyUpdate):
     property_name = "expected"
+    property_builder = build_conditional_tree
 
     def check_default(self, result):
         if self.default_value is not None:
             assert self.default_value == result.default_expected
         else:
             self.default_value = result.default_expected
 
-    def get_value(self, in_value):
-        return in_value.status
-
-    def update_default(self):
-        update_default = all(self.new[0].value == result.value
-                             for result in self.new) and not self.updated
-        new_value = self.new[0].value
-        return update_default, new_value
+    def from_result_value(self, result):
+        return result.status
 
-    def add_new(self, unconditional_value, stability):
-        try:
-            conditionals = group_conditionals(
-                self.new,
-                property_order=self.node.root.property_order,
-                boolean_properties=self.node.root.boolean_properties)
-        except ConditionError as e:
-            if stability is not None:
-                self.node.set("disabled", stability or "unstable", e.cond.children[0])
-                self.node.new_disabled = True
-            else:
-                raise UpdateError("Conflicting metadata values")
-        for conditional_node, value in conditionals:
-            if value != unconditional_value:
-                self.node.set(self.property_name, value, condition=conditional_node.children[0])
+    def updated_value(self, current, new):
+        if len(new) > 1:
+            raise ConditionError
+        return list(new)[0]
 
 
 class MaxAssertsUpdate(PropertyUpdate):
     """For asserts we always update the default value and never add new conditionals.
     The value we set as the default is the maximum the current default or one more than the
     number of asserts we saw in any configuration."""
 
     property_name = "max-asserts"
     cls_default_value = 0
     value_type = int
-
-    def update_value(self, old_value, new_value):
-        new_value = self.value_type(new_value)
-        if old_value is not None:
-            old_value = self.value_type(old_value)
-        if old_value is not None and old_value < new_value:
-            return new_value + 1
-        if old_value is None:
-            return new_value + 1
-        return old_value
+    property_builder = build_unconditional_tree
 
-    def update_default(self):
-        # Current values
-        values = []
-        current_default = None
-        if self.property_name in self.node._data:
-            current_default = [item for item in
-                               self.node._data[self.property_name]
-                               if item.condition_node is None]
-            if current_default:
-                values.append(int(current_default[0].value))
-        values.extend(item.value for item in self.new)
-        values.extend(item.value for item in
-                      itertools.chain.from_iterable(results for _, results in self.updated))
-        new_value = max(values)
-        return True, new_value
+    def updated_value(self, current, new):
+        if any(item > current for item in new):
+            return max(new) + 1
+        return current
 
 
 class MinAssertsUpdate(PropertyUpdate):
     property_name = "min-asserts"
     cls_default_value = 0
     value_type = int
-
-    def update_value(self, old_value, new_value):
-        new_value = self.value_type(new_value)
-        if old_value is not None:
-            old_value = self.value_type(old_value)
-        if old_value is not None and new_value < old_value:
-            return 0
-        if old_value is None:
-            # If we are getting some asserts for the first time, set the minimum to 0
-            return new_value
-        return old_value
+    property_builder = build_unconditional_tree
 
-    def update_default(self):
-        """For asserts we always update the default value and never add new conditionals.
-        This is either set to the current value or one less than the number of asserts
-        we saw, whichever is lower."""
-        values = []
-        current_default = None
-        if self.property_name in self.node._data:
-            current_default = [item for item in
-                               self.node._data[self.property_name]
-                               if item.condition_node is None]
-        if current_default:
-            values.append(current_default[0].value_as(self.value_type))
-        values.extend(max(0, item.value) for item in self.new)
-        values.extend(max(0, item.value) for item in
-                      itertools.chain.from_iterable(results for _, results in self.updated))
-        new_value = min(values)
-        return True, new_value
+    def updated_value(self, current, new):
+        if any(item < current for item in new):
+            rv = min(new) - 1
+        else:
+            rv = current
+        return max(rv, 0)
 
 
 class AppendOnlyListUpdate(PropertyUpdate):
-    cls_default_value = None
+    cls_default_value = []
+    property_builder = build_unconditional_tree
 
-    def get_value(self, result):
-        raise NotImplementedError
-
-    def update_value(self, old_value, new_value):
-        if isinstance(new_value, (str, unicode)):
-            new_value = {new_value}
+    def updated_value(self, current, new):
+        if current is None:
+            rv = set()
         else:
-            new_value = set(new_value)
-        if old_value is None:
-            old_value = set()
-        old_value = set(old_value)
-        return sorted((old_value | new_value) - {None})
+            rv = set(current)
 
-    def update_default(self):
-        current_default = None
-        if self.property_name in self.node._data:
-            current_default = [item for item in
-                               self.node._data[self.property_name]
-                               if item.condition_node is None]
-        if current_default:
-            current_default = current_default[0].value
-        new_values = [item.value for item in self.new]
-        new_value = self.update_value(current_default, new_values)
-        return True, new_value if new_value else None
+        for item in new:
+            if item is None:
+                continue
+            elif isinstance(item, (str, unicode)):
+                rv.add(item)
+            else:
+                rv |= item
+
+        return sorted(rv)
 
 
 class LsanUpdate(AppendOnlyListUpdate):
     property_name = "lsan-allowed"
+    property_builder = build_unconditional_tree
 
-    def get_value(self, result):
+    def from_result_value(self, result):
         # If we have an allowed_match that matched, return None
         # This value is ignored later (because it matches the default)
         # We do that because then if we allow a failure in foo/__dir__.ini
         # we don't want to update foo/bar/__dir__.ini with the same rule
         if result[1]:
             return None
         # Otherwise return the topmost stack frame
         # TODO: there is probably some improvement to be made by looking for a "better" stack frame
         return result[0][0]
 
+    def to_ini_value(self, value):
+        return value
+
 
 class LeakObjectUpdate(AppendOnlyListUpdate):
     property_name = "leak-allowed"
+    property_builder = build_unconditional_tree
 
-    def get_value(self, result):
+    def from_result_value(self, result):
         # If we have an allowed_match that matched, return None
         if result[1]:
             return None
         # Otherwise return the process/object name
         return result[0]
 
 
 class LeakThresholdUpdate(PropertyUpdate):
     property_name = "leak-threshold"
-    cls_default_value = []
-
-    def __init__(self, node):
-        PropertyUpdate.__init__(self, node)
-        self.thresholds = {}
+    cls_default_value = {}
+    property_builder = build_unconditional_tree
 
-    def get_value(self, value):
-        threshold = value[2]
-        key = value[0]
-        self.thresholds[key] = threshold
-        return value[:2]
+    def from_result_value(self, result):
+        return result
+
+    def to_ini_value(self, data):
+        return ["%s:%s" % item for item in sorted(data.iteritems())]
 
-    def value_type(self, data):
-        if all(isinstance(item, tuple) for item in data):
-            return data
-        values = [item.rsplit(":", 1) for item in data]
-        return [(key, int(float(value))) for key, value in values]
+    def from_ini_value(self, data):
+        rv = {}
+        for item in data:
+            key, value = item.split(":", 1)
+            rv[key] = int(float(value))
+        return rv
 
-    def update_value(self, old_value, new_value, allow_buffer=True):
-        rv = []
-        old_value = dict(old_value)
-        new_value = dict(self.value_type(new_value))
-        for key in set(new_value.keys()) | set(old_value.keys()):
-            old = old_value.get(key, 0)
-            new = new_value.get(key, 0)
-            threshold = self.thresholds.get(key, 0)
+    def updated_value(self, current, new):
+        if current:
+            rv = current.copy()
+        else:
+            rv = {}
+        for process, leaked_bytes, threshold in new:
             # If the value is less than the threshold but there isn't
             # an old value we must have inherited the threshold from
             # a parent ini file so don't any anything to this one
-            if not old and new < threshold:
+            if process not in rv and leaked_bytes < threshold:
                 continue
-            if old >= new:
-                updated = old
-            else:
-                if allow_buffer:
-                    # Round up to nearest 50 kb
-                    boundary = 50 * 1024
-                    updated = int(boundary * ceil(float(new) / boundary))
-                else:
-                    updated = new
-            rv.append((key, updated))
-        return ["%s:%s" % item for item in sorted(rv)]
-
-    def update_default(self):
-        # Current values
-        current_default = []
-        if self.property_name in self.node._data:
-            current_default = [item for item in
-                               self.node._data[self.property_name]
-                               if item.condition_node is None]
-            current_default = current_default[0].value_as(self.value_type)
-        max_new = {}
-        for item in self.new:
-            key, value = item.value
-            if value > max_new.get(key, 0):
-                max_new[key] = value
-        new_value = self.update_value(current_default,
-                                      max_new.items(),
-                                      allow_buffer=False)
-        return True, new_value
+            if leaked_bytes > rv.get(process, 0):
+                # Round up to nearest 50 kb
+                boundary = 50 * 1024
+                rv[process] = int(boundary * ceil(float(leaked_bytes) / boundary))
+        return rv
 
 
-def group_conditionals(values, property_order=None, boolean_properties=None):
-    """Given a list of Value objects, return a list of
-    (conditional_node, status) pairs representing the conditional
-    expressions that are required to match each status
-
-    :param values: List of Values
-    :param property_order: List of properties to use in expectation metadata
-                           from most to least significant.
-    :param boolean_properties: Set of properties in property_order that should
-                               be treated as boolean."""
-
-    by_property = defaultdict(set)
-    for run_info, value in values:
-        for prop_name, prop_value in run_info.iteritems():
-            by_property[(prop_name, prop_value)].add(value)
-
-    if property_order is None:
-        property_order = ["debug", "os", "version", "processor", "bits"]
-
-    if boolean_properties is None:
-        boolean_properties = {"debug"}
-    else:
-        boolean_properties = set(boolean_properties)
-
-    # If we have more than one value, remove any properties that are common
-    # for all the values
-    if len(values) > 1:
-        for key, statuses in by_property.copy().iteritems():
-            if len(statuses) == len(values):
-                del by_property[key]
-        if not by_property:
-            raise ConditionError
-
-    properties = {item[0] for item in by_property.iterkeys()}
-    include_props = []
-
-    for prop in property_order:
-        if prop in properties:
-            include_props.append(prop)
-
-    conditions = {}
-
-    for run_info, value in values:
-        prop_set = tuple((prop, run_info[prop]) for prop in include_props)
-        if prop_set in conditions:
-            if conditions[prop_set][1] != value:
-                # A prop_set contains contradictory results
-                raise ConditionError(make_expr(prop_set, value, boolean_properties))
-            continue
-
-        expr = make_expr(prop_set, value, boolean_properties=boolean_properties)
-        conditions[prop_set] = (expr, value)
-
-    return conditions.values()
-
-
-def make_expr(prop_set, rhs, boolean_properties=None):
+def make_expr(prop_set, rhs):
     """Create an AST that returns the value ``status`` given all the
     properties in prop_set match.
 
     :param prop_set: tuple of (property name, value) pairs for each
                      property in this expression and the value it must match
     :param status: Status on RHS when all the given properties match
-    :param boolean_properties: Set of properties in property_order that should
-                               be treated as boolean.
     """
     root = ConditionalNode()
 
     assert len(prop_set) > 0
 
     expressions = []
     for prop, value in prop_set:
-        number_types = (int, float, long)
-        value_cls = (NumberNode
-                     if type(value) in number_types
-                     else StringNode)
-        if prop not in boolean_properties:
+        if value not in (True, False):
             expressions.append(
                 BinaryExpressionNode(
                     BinaryOperatorNode("=="),
                     VariableNode(prop),
-                    value_cls(unicode(value))
-                ))
+                    make_node(value))
+                )
         else:
             if value:
                 expressions.append(VariableNode(prop))
             else:
                 expressions.append(
                     UnaryExpressionNode(
                         UnaryOperatorNode("not"),
                         VariableNode(prop)
@@ -742,46 +730,61 @@ def make_expr(prop_set, rhs, boolean_pro
                 BinaryOperatorNode("and"),
                 curr,
                 prev)
             prev = node
     else:
         node = expressions[0]
 
     root.append(node)
-    if type(rhs) in number_types:
-        rhs_node = NumberNode(rhs)
-    else:
-        rhs_node = StringNode(rhs)
+    rhs_node = make_value_node(rhs)
     root.append(rhs_node)
 
     return root
 
 
-def get_manifest(metadata_root, test_path, url_base, property_order=None,
-                 boolean_properties=None):
+def make_node(value):
+    if type(value) in (int, float, long):
+        node = NumberNode(value)
+    elif type(value) in (str, unicode):
+        node = StringNode(unicode(value))
+    elif hasattr(value, "__iter__"):
+        node = ListNode()
+        for item in value:
+            node.append(make_node(item))
+    return node
+
+
+def make_value_node(value):
+    if type(value) in (int, float, long):
+        node = ValueNode(value)
+    elif type(value) in (str, unicode):
+        node = ValueNode(unicode(value))
+    elif hasattr(value, "__iter__"):
+        node = ListNode()
+        for item in value:
+            node.append(make_node(item))
+    return node
+
+
+def get_manifest(metadata_root, test_path, url_base, run_info_properties):
     """Get the ExpectedManifest for a particular test path, or None if there is no
     metadata stored for that test path.
 
     :param metadata_root: Absolute path to the root of the metadata directory
     :param test_path: Path to the test(s) relative to the test root
-    :param url_base: Base url for serving the tests in this manifest
-    :param property_order: List of properties to use in expectation metadata
-                           from most to least significant.
-    :param boolean_properties: Set of properties in property_order that should
-                               be treated as boolean."""
+    :param url_base: Base url for serving the tests in this manifest"""
     manifest_path = expected.expected_path(metadata_root, test_path)
     try:
         with open(manifest_path) as f:
-            return compile(f, test_path, url_base, property_order=property_order,
-                           boolean_properties=boolean_properties)
+            rv = compile(f, test_path, url_base,
+                         run_info_properties)
     except IOError:
         return None
+    return rv
 
 
-def compile(manifest_file, test_path, url_base, property_order=None,
-            boolean_properties=None):
+def compile(manifest_file, test_path, url_base, run_info_properties):
     return conditional.compile(manifest_file,
                                data_cls_getter=data_cls_getter,
                                test_path=test_path,
                                url_base=url_base,
-                               property_order=property_order,
-                               boolean_properties=boolean_properties)
+                               run_info_properties=run_info_properties)
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/metadata.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/metadata.py
@@ -20,35 +20,60 @@ manifestitem = None
 logger = structuredlog.StructuredLogger("web-platform-tests")
 
 try:
     import ujson as json
 except ImportError:
     import json
 
 
+class RunInfo(object):
+    """A wrapper around RunInfo dicts so that they can be hashed by identity"""
+
+    def __init__(self, dict_value):
+        self.data = dict_value
+        self.canonical_repr = tuple(tuple(item) for item in sorted(dict_value.items()))
+
+    def __getitem__(self, key):
+        return self.data[key]
+
+    def __setitem__(self, key, value):
+        raise TypeError
+
+    def __hash__(self):
+        return hash(self.canonical_repr)
+
+    def __eq__(self, other):
+        return self.canonical_repr == other.canonical_repr
+
+    def iteritems(self):
+        for key, value in self.data.iteritems():
+            yield key, value
+
+    def items(self):
+        return list(self.iteritems())
+
+
 def update_expected(test_paths, serve_root, log_file_names,
-                    rev_old=None, rev_new="HEAD", ignore_existing=False,
-                    sync_root=None, property_order=None, boolean_properties=None,
-                    stability=None):
+                    update_properties, rev_old=None, rev_new="HEAD",
+                    ignore_existing=False, sync_root=None, stability=None):
     """Update the metadata files for web-platform-tests based on
     the results obtained in a previous run or runs
 
     If stability is not None, assume log_file_names refers to logs from repeated
     test jobs, disable tests that don't behave as expected on all runs"""
     do_delayed_imports(serve_root)
 
     id_test_map = load_test_data(test_paths)
 
     for metadata_path, updated_ini in update_from_logs(id_test_map,
-                                                       *log_file_names,
-                                                       ignore_existing=ignore_existing,
-                                                       property_order=property_order,
-                                                       boolean_properties=boolean_properties,
-                                                       stability=stability):
+                                                       update_properties,
+                                                       ignore_existing,
+                                                       stability,
+                                                       *log_file_names):
 
         write_new_expected(metadata_path, updated_ini)
         if stability:
             for test in updated_ini.iterchildren():
                 for subtest in test.iterchildren():
                     if subtest.new_disabled:
                         print("disabled: %s" % os.path.dirname(subtest.root.test_path) + "/" + subtest.name)
                     if test.new_disabled:
@@ -134,16 +159,19 @@ class InternedData(object):
     type_conv = None
     rev_type_conv = None
 
     def __init__(self, max_bits=8):
         self.max_idx = 2**max_bits - 2
         # Reserve 0 as a sentinal
         self._data = [None], {}
 
+    def clear(self):
+        self.__init__()
+
     def store(self, obj):
         if self.type_conv is not None:
             obj = self.type_conv(obj)
 
         objs, obj_to_idx = self._data
         if obj not in obj_to_idx:
             value = len(objs)
             objs.append(obj)
@@ -155,110 +183,85 @@ class InternedData(object):
         return value
 
     def get(self, idx):
         obj = self._data[0][idx]
         if self.rev_type_conv is not None:
             obj = self.rev_type_conv(obj)
         return obj
 
+    def __iter__(self):
+        for i in xrange(1, len(self._data[0])):
+            yield self.get(i)
+
 
 class RunInfoInterned(InternedData):
     def type_conv(self, value):
         return tuple(value.items())
 
     def rev_type_conv(self, value):
         return dict(value)
 
 
 prop_intern = InternedData(4)
-run_info_intern = RunInfoInterned()
+run_info_intern = InternedData(8)
 status_intern = InternedData(4)
 
 
 def load_test_data(test_paths):
     manifest_loader = testloader.ManifestLoader(test_paths, False)
     manifests = manifest_loader.load()
 
     id_test_map = {}
     for test_manifest, paths in manifests.iteritems():
         id_test_map.update(create_test_tree(paths["metadata_path"],
                                             test_manifest))
     return id_test_map
 
 
-def update_from_logs(id_test_map, *log_filenames, **kwargs):
-    ignore_existing = kwargs.get("ignore_existing", False)
-    property_order = kwargs.get("property_order")
-    boolean_properties = kwargs.get("boolean_properties")
-    stability = kwargs.get("stability")
+def update_from_logs(id_test_map, update_properties, ignore_existing, stability,
+                     *log_filenames):
 
     updater = ExpectedUpdater(id_test_map,
                               ignore_existing=ignore_existing)
 
     for i, log_filename in enumerate(log_filenames):
         print("Processing log %d/%d" % (i + 1, len(log_filenames)))
         with open(log_filename) as f:
             updater.update_from_log(f)
 
-    for item in update_results(id_test_map, property_order, boolean_properties, stability):
+    for item in update_results(id_test_map, update_properties, stability):
         yield item
 
 
-def update_results(id_test_map, property_order, boolean_properties, stability):
+def update_results(id_test_map, update_properties, stability):
     test_file_items = set(id_test_map.itervalues())
 
     default_expected_by_type = {}
     for test_type, test_cls in wpttest.manifest_test_cls.iteritems():
         if test_cls.result_cls:
             default_expected_by_type[(test_type, False)] = test_cls.result_cls.default_expected
         if test_cls.subtest_result_cls:
             default_expected_by_type[(test_type, True)] = test_cls.subtest_result_cls.default_expected
 
     for test_file in test_file_items:
-        updated_expected = test_file.update(property_order, boolean_properties, stability,
-                                            default_expected_by_type)
+        updated_expected = test_file.update(stability, default_expected_by_type, update_properties)
         if updated_expected is not None and updated_expected.modified:
             yield test_file.metadata_path, updated_expected
 
 
 def directory_manifests(metadata_path):
     rv = []
     for dirpath, dirname, filenames in os.walk(metadata_path):
         if "__dir__.ini" in filenames:
             rel_path = os.path.relpath(dirpath, metadata_path)
             rv.append(os.path.join(rel_path, "__dir__.ini"))
     return rv
 
 
-def write_changes(metadata_path, expected):
-    # First write the new manifest files to a temporary directory
-    temp_path = tempfile.mkdtemp(dir=os.path.split(metadata_path)[0])
-    write_new_expected(temp_path, expected)
-
-    # Copy all files in the root to the temporary location since
-    # these cannot be ini files
-    keep_files = [item for item in os.listdir(metadata_path) if
-                  not os.path.isdir(os.path.join(metadata_path, item))]
-
-    for item in keep_files:
-        dest_dir = os.path.dirname(os.path.join(temp_path, item))
-        if not os.path.exists(dest_dir):
-            os.makedirs(dest_dir)
-        shutil.copyfile(os.path.join(metadata_path, item),
-                        os.path.join(temp_path, item))
-
-    # Then move the old manifest files to a new location
-    temp_path_2 = metadata_path + str(uuid.uuid4())
-    os.rename(metadata_path, temp_path_2)
-    # Move the new files to the destination location and remove the old files
-    os.rename(temp_path, metadata_path)
-    shutil.rmtree(temp_path_2)
-
-
 def write_new_expected(metadata_path, expected):
     # Serialize the data back to a file
     path = expected_path(metadata_path, expected.test_path)
     if not expected.is_empty:
         manifest_str = wptmanifest.serialize(expected.node, skip_empty_data=True)
         assert manifest_str != ""
         dir = os.path.split(path)[0]
         if not os.path.exists(dir):
@@ -348,17 +351,17 @@ class ExpectedUpdater(object):
             for key, action in [("objects", "mozleak_object"),
                                 ("total", "mozleak_total")]:
                 for item in scope_data.get(key, []):
                     item_data = {"scope": scope}
                     item_data.update(item)
                     action_map[action](item_data)
 
     def suite_start(self, data):
-        self.run_info = run_info_intern.store(data["run_info"])
+        self.run_info = run_info_intern.store(RunInfo(data["run_info"]))
 
     def test_start(self, data):
         test_id = intern(data["test"].encode("utf8"))
         try:
             test_data = self.id_test_map[test_id]
         except KeyError:
             print("Test not found %s, skipping" % test_id)
             return
@@ -523,66 +526,61 @@ class PackedResultList(object):
 
     def __iter__(self):
         for i, item in enumerate(self.data):
             yield self.unpack(i, item)
 
 
 class TestFileData(object):
     __slots__ = ("url_base", "item_type", "test_path", "metadata_path", "tests",
-                 "_requires_update", "clear", "data")
+                 "_requires_update", "data")
     def __init__(self, url_base, item_type, metadata_path, test_path, tests):
         self.url_base = url_base
         self.item_type = item_type
         self.test_path = test_path
         self.metadata_path = metadata_path
         self.tests = {intern(item.id.encode("utf8")) for item in tests}
         self._requires_update = False
-        self.clear = set()
         self.data = defaultdict(lambda: defaultdict(PackedResultList))
 
     def set_requires_update(self):
         self._requires_update = True
 
     def set(self, test_id, subtest_id, prop, run_info, value):
         self.data[test_id][subtest_id].append(prop_intern.store(prop),
                                               run_info,
                                               value)
 
-    def expected(self, property_order, boolean_properties):
+    def expected(self, update_properties):
         expected_data = load_expected(self.url_base,
                                       self.metadata_path,
                                       self.test_path,
                                       self.tests,
-                                      property_order,
-                                      boolean_properties)
+                                      update_properties)
         if expected_data is None:
             expected_data = create_expected(self.url_base,
                                             self.test_path,
-                                            property_order,
-                                            boolean_properties)
+                                            update_properties)
         return expected_data
 
-    def update(self, property_order, boolean_properties, stability,
-               default_expected_by_type):
+    def update(self, stability, default_expected_by_type, update_properties):
         if not self._requires_update:
             return
 
-        expected = self.expected(property_order, boolean_properties)
+        expected = self.expected(update_properties)
         expected_by_test = {}
 
         for test_id in self.tests:
             if not expected.has_test(test_id):
                 expected.append(manifestupdate.TestNode.create(test_id))
             test_expected = expected.get_test(test_id)
             expected_by_test[test_id] = test_expected
-            for prop in self.clear:
-                test_expected.clear(prop)
 
         for test_id, test_data in self.data.iteritems():
+            test_id = test_id.decode("utf8")
             for subtest_id, results_list in test_data.iteritems():
                 for prop, run_info, value in results_list:
                     # Special case directory metadata
                     if subtest_id is None and test_id.endswith("__dir__"):
                         if prop == "lsan":
                             expected.set_lsan(run_info, value)
                         elif prop == "leak-object":
                             expected.set_leak_object(run_info, value)
@@ -593,52 +591,42 @@ class TestFileData(object):
                     if prop == "status":
                         value = Result(value, default_expected_by_type[self.item_type,
                                                                        subtest_id is not None])
 
                     test_expected = expected_by_test[test_id]
                     if subtest_id is None:
                         item_expected = test_expected
                     else:
+                        if isinstance(subtest_id, str):
+                            subtest_id = subtest_id.decode("utf8")
                         item_expected = test_expected.get_subtest(subtest_id)
                     if prop == "status":
                         item_expected.set_result(run_info, value)
                     elif prop == "asserts":
                         item_expected.set_asserts(run_info, value)
 
-        expected.coalesce_properties(stability=stability)
+        expected.update(stability=stability)
         for test in expected.iterchildren():
             for subtest in test.iterchildren():
-                subtest.coalesce_properties(stability=stability)
-            test.coalesce_properties(stability=stability)
+                subtest.update(stability=stability)
+            test.update(stability=stability)
 
         return expected
 
 
 Result = namedtuple("Result", ["status", "default_expected"])
 
 
-def create_expected(url_base, test_path, property_order=None,
-                    boolean_properties=None):
+def create_expected(url_base, test_path,  run_info_properties):
     expected = manifestupdate.ExpectedManifest(None,
                                                test_path,
                                                url_base,
-                                               property_order=property_order,
-                                               boolean_properties=boolean_properties)
+                                               run_info_properties)
     return expected
 
 
-def load_expected(url_base, metadata_path, test_path, tests, property_order=None,
-                  boolean_properties=None):
+def load_expected(url_base, metadata_path, test_path, tests, run_info_properties):
     expected_manifest = manifestupdate.get_manifest(metadata_path,
                                                     test_path,
                                                     url_base,
-                                                    property_order=property_order,
-                                                    boolean_properties=boolean_properties)
-    if expected_manifest is None:
-        return
-
-    # Remove expected data for tests that no longer exist
-    for test in expected_manifest.iterchildren():
-        if test.id not in tests:
-            test.remove()
-
+                                                    run_info_properties)
     return expected_manifest
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/products.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/products.py
@@ -68,11 +68,11 @@ def load_product_update(config, product)
     run_info properties to use when constructing the expectation data for
     this product. None for either key indicates that the default keys
     appropriate for distinguishing based on platform will be used."""
 
     module = product_module(config, product)
     data = module.__wptrunner__
 
     update_properties = (getattr(module, data["update_properties"])()
-                         if "update_properties" in data else (None, None))
+                         if "update_properties" in data else {})
 
     return update_properties
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/tests/test_expectedtree.py
@@ -0,0 +1,109 @@
+import sys
+
+import pytest
+
+from .. import expectedtree, metadata
+
+def dump_tree(tree):
+    rv = []
+
+    def dump_node(node, indent=0):
+        prefix = " " * indent
+        if not node.prop:
+            data = "root"
+        else:
+            data = "%s:%s" % (node.prop, node.value)
+        if node.result_values:
+            data += " result_values:%s" % (",".join(sorted(node.result_values)))
+        rv.append("%s<%s>" % (prefix, data))
+        for child in sorted(node.children, key=lambda x:x.value):
+            dump_node(child, indent + 2)
+
+    dump_node(tree)
+    return "\n".join(rv)
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_build_tree_0():
+    # Pass iff debug
+    results = [({"os": "linux", "version": "18.04", "debug": True}, "FAIL"),
+               ({"os": "linux", "version": "18.04", "debug": False}, "PASS"),
+               ({"os": "linux", "version": "16.04", "debug": False}, "PASS"),
+               ({"os": "mac", "version": "10.12", "debug": True}, "FAIL"),
+               ({"os": "mac", "version": "10.12", "debug": False}, "PASS"),
+               ({"os": "win", "version": "7", "debug": False}, "PASS"),
+               ({"os": "win", "version": "10", "debug": False}, "PASS")]
+    results = {metadata.RunInfo(run_info): set([status]) for run_info, status in results}
+    tree = expectedtree.build_tree(["os", "version", "debug"], {}, results)
+
+    expected = """<root>
+  <debug:False result_values:PASS>
+  <debug:True result_values:FAIL>"""
+
+    assert dump_tree(tree) == expected
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_build_tree_1():
+    # Pass if linux or windows 10
+    results = [({"os": "linux", "version": "18.04", "debug": True}, "PASS"),
+               ({"os": "linux", "version": "18.04", "debug": False}, "PASS"),
+               ({"os": "linux", "version": "16.04", "debug": False}, "PASS"),
+               ({"os": "mac", "version": "10.12", "debug": True}, "FAIL"),
+               ({"os": "mac", "version": "10.12", "debug": False}, "FAIL"),
+               ({"os": "win", "version": "7", "debug": False}, "FAIL"),
+               ({"os": "win", "version": "10", "debug": False}, "PASS")]
+    results = {metadata.RunInfo(run_info): set([status]) for run_info, status in results}
+    tree = expectedtree.build_tree(["os", "debug"], {"os": ["version"]}, results)
+
+    expected = """<root>
+  <os:linux result_values:PASS>
+  <os:mac result_values:FAIL>
+  <os:win>
+    <version:10 result_values:PASS>
+    <version:7 result_values:FAIL>"""
+
+    assert dump_tree(tree) == expected
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_build_tree_2():
+    # Fails in a specific configuration
+    results = [({"os": "linux", "version": "18.04", "debug": True}, "PASS"),
+               ({"os": "linux", "version": "18.04", "debug": False}, "FAIL"),
+               ({"os": "linux", "version": "16.04", "debug": False}, "PASS"),
+               ({"os": "linux", "version": "16.04", "debug": True}, "PASS"),
+               ({"os": "mac", "version": "10.12", "debug": True}, "PASS"),
+               ({"os": "mac", "version": "10.12", "debug": False}, "PASS"),
+               ({"os": "win", "version": "7", "debug": False}, "PASS"),
+               ({"os": "win", "version": "10", "debug": False}, "PASS")]
+    results = {metadata.RunInfo(run_info): set([status]) for run_info, status in results}
+    tree = expectedtree.build_tree(["os", "debug"], {"os": ["version"]}, results)
+
+    expected = """<root>
+  <os:linux>
+    <debug:False>
+      <version:16.04 result_values:PASS>
+      <version:18.04 result_values:FAIL>
+    <debug:True result_values:PASS>
+  <os:mac result_values:PASS>
+  <os:win result_values:PASS>"""
+
+    assert dump_tree(tree) == expected
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_build_tree_3():
+
+    results = [({"os": "linux", "version": "18.04", "debug": True, "unused": False}, "PASS"),
+               ({"os": "linux", "version": "18.04", "debug": True, "unused": True}, "FAIL")]
+    results = {metadata.RunInfo(run_info): set([status]) for run_info, status in results}
+    tree = expectedtree.build_tree(["os", "debug"], {"os": ["version"]}, results)
+
+    expected = """<root result_values:FAIL,PASS>"""
+
+    assert dump_tree(tree) == expected
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/tests/test_update.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/tests/test_update.py
@@ -1,21 +1,22 @@
 import json
 import mock
 import os
 import pytest
 import sys
 from io import BytesIO
 
 from .. import metadata, manifestupdate
-from ..update import WPTUpdate
+from ..update.update import WPTUpdate
 from ..update.base import StepRunner, Step
 from mozlog import structuredlog, handlers, formatters
 
-sys.path.insert(0, os.path.join(os.path.dirname(__file__), os.pardir, os.pardir, os.pardir))
+here = os.path.dirname(__file__)
+sys.path.insert(0, os.path.join(here, os.pardir, os.pardir, os.pardir))
 from manifest import manifest, item as manifest_item
 
 
 def rel_path_to_test_url(rel_path):
     assert not os.path.isabs(rel_path)
     return rel_path.replace(os.sep, "/")
 
 
@@ -32,41 +33,61 @@ item_classes = {"testharness": manifest_
                 "manual": manifest_item.ManualTest,
                 "stub": manifest_item.Stub,
                 "wdspec": manifest_item.WebDriverSpecTest,
                 "conformancechecker": manifest_item.ConformanceCheckerTest,
                 "visual": manifest_item.VisualTest,
                 "support": manifest_item.SupportFile}
 
 
+default_run_info = {"debug": False, "os": "linux", "version": "18.04", "processor": "x86_64", "bits": 64}
+
+
+def reset_globals():
+    metadata.prop_intern.clear()
+    metadata.run_info_intern.clear()
+    metadata.status_intern.clear()
+
+
+def get_run_info(overrides):
+    run_info = default_run_info.copy()
+    run_info.update(overrides)
+    return run_info
+
+
 def update(tests, *logs):
     id_test_map, updater = create_updater(tests)
+
     for log in logs:
         log = create_log(log)
         updater.update_from_log(log)
 
+    update_properties = (["debug", "os", "version", "processor"],
+                         {"os": ["version"], "processor": "bits"})
+
+    expected_data = {}
+    metadata.load_expected = lambda _, __, test_path, *args: expected_data[test_path]
+    for test_path, test_ids, test_type, manifest_str in tests:
+        expected_data[test_path] = manifestupdate.compile(BytesIO(manifest_str),
+                                                          test_path,
+                                                          "/",
+                                                          update_properties)
+
     return list(metadata.update_results(id_test_map,
-                                        ["debug", "os", "version", "processor", "bits"],
-                                        ["debug"],
+                                        update_properties,
                                         False))
 
 
 def create_updater(tests, url_base="/", **kwargs):
     id_test_map = {}
     m = create_test_manifest(tests, url_base)
-    expected_data = {}
-    metadata.load_expected = lambda _, __, test_path, *args: expected_data[test_path]
 
+    reset_globals()
     id_test_map = metadata.create_test_tree(None, m)
 
-    for test_path, test_ids, test_type, manifest_str in tests:
-        expected_data[test_path] = manifestupdate.compile(BytesIO(manifest_str),
-                                                          test_path,
-                                                          url_base)
-
     return id_test_map, metadata.ExpectedUpdater(id_test_map, **kwargs)
 
 
 def create_log(entries):
     data = BytesIO()
     if isinstance(entries, list):
         logger = structuredlog.StructuredLogger("expected_test")
         handler = handlers.StreamHandler(data, formatters.JSONFormatter())
@@ -78,17 +99,20 @@ def create_log(entries):
         logger.remove_handler(handler)
     else:
         json.dump(entries, data)
     data.seek(0)
     return data
 
 
 def suite_log(entries, run_info=None):
-    return ([("suite_start", {"tests": [], "run_info": run_info or {}})] +
+    _run_info = default_run_info.copy()
+    if run_info:
+        _run_info.update(run_info)
+    return ([("suite_start", {"tests": [], "run_info": _run_info})] +
             entries +
             [("suite_end", {})])
 
 
 def create_test_manifest(tests, url_base="/"):
     source_files = []
     for i, (test, _, test_type, _) in enumerate(tests):
         if test_type:
@@ -136,17 +160,17 @@ def test_update_1():
                                       "expected": "ERROR"}),
                      ("test_end", {"test": test_id,
                                    "status": "OK"})])
 
     updated = update(tests, log)
 
     new_manifest = updated[0][1]
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).children[0].get("expected") == "FAIL"
+    assert new_manifest.get_test(test_id).children[0].get("expected", default_run_info) == "FAIL"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_skip_0():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness",
               """[test.htm]
@@ -182,18 +206,18 @@ def test_new_subtest():
                                       "subtest": "test2",
                                       "status": "FAIL",
                                       "expected": "PASS"}),
                      ("test_end", {"test": test_id,
                                    "status": "OK"})])
     updated = update(tests, log)
     new_manifest = updated[0][1]
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).children[0].get("expected") == "FAIL"
-    assert new_manifest.get_test(test_id).children[1].get("expected") == "FAIL"
+    assert new_manifest.get_test(test_id).children[0].get("expected", default_run_info) == "FAIL"
+    assert new_manifest.get_test(test_id).children[1].get("expected", default_run_info) == "FAIL"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_multiple_0():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   [test1]
@@ -216,18 +240,22 @@ def test_update_multiple_0():
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"debug": False, "os": "linux"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"debug": False, "os": "osx"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"debug": False, "os": "linux"})
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "osx"}) == "FAIL"
+        "expected", run_info_1) == "FAIL"
     assert new_manifest.get_test(test_id).children[0].get(
         "expected", {"debug": False, "os": "linux"}) == "TIMEOUT"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_multiple_1():
     test_id = "/path/to/test.htm"
@@ -252,22 +280,28 @@ def test_update_multiple_1():
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"debug": False, "os": "linux"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "osx"}) == "FAIL"
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"debug": False, "os": "osx"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"debug": False, "os": "linux"})
+    run_info_3 = default_run_info.copy()
+    run_info_3.update({"debug": False, "os": "win"})
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "linux"}) == "TIMEOUT"
+        "expected", run_info_1) == "FAIL"
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "windows"}) == "FAIL"
+        "expected", run_info_2) == "TIMEOUT"
+    assert new_manifest.get_test(test_id).children[0].get(
+        "expected", run_info_3) == "FAIL"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_multiple_2():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   [test1]
@@ -289,21 +323,26 @@ def test_update_multiple_2():
                                         "expected": "FAIL"}),
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"debug": True, "os": "osx"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"debug": False, "os": "osx"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"debug": True, "os": "osx"})
+
     assert not new_manifest.is_empty
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "osx"}) == "FAIL"
+        "expected", run_info_1) == "FAIL"
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": True, "os": "osx"}) == "TIMEOUT"
+        "expected", run_info_2) == "TIMEOUT"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_multiple_3():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   [test1]
@@ -327,21 +366,26 @@ def test_update_multiple_3():
                                         "expected": "FAIL"}),
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"debug": True, "os": "osx"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"debug": False, "os": "osx"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"debug": True, "os": "osx"})
+
     assert not new_manifest.is_empty
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "osx"}) == "FAIL"
+        "expected", run_info_1) == "FAIL"
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": True, "os": "osx"}) == "TIMEOUT"
+        "expected", run_info_2) == "TIMEOUT"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_ignore_existing():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   [test1]
@@ -365,21 +409,126 @@ def test_update_ignore_existing():
                                         "expected": "PASS"}),
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"debug": True, "os": "windows"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"debug": False, "os": "linux"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"debug": False, "os": "osx"})
+
     assert not new_manifest.is_empty
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": True, "os": "osx"}) == "FAIL"
+        "expected", run_info_1) == "FAIL"
     assert new_manifest.get_test(test_id).children[0].get(
-        "expected", {"debug": False, "os": "osx"}) == "NOTRUN"
+        "expected", run_info_2) == "NOTRUN"
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_update_default():
+    test_id = "/path/to/test.htm"
+    tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
+  [test1]
+    expected:
+      if os == "mac": FAIL
+      ERROR""")]
+
+    log_0 = suite_log([("test_start", {"test": test_id}),
+                       ("test_status", {"test": test_id,
+                                        "subtest": "test1",
+                                        "status": "PASS",
+                                        "expected": "FAIL"}),
+                       ("test_end", {"test": test_id,
+                                     "status": "OK"})],
+                      run_info={"os": "mac"})
+
+    log_1 = suite_log([("test_start", {"test": test_id}),
+                       ("test_status", {"test": test_id,
+                                        "subtest": "test1",
+                                        "status": "PASS",
+                                        "expected": "ERROR"}),
+                       ("test_end", {"test": test_id,
+                                     "status": "OK"})],
+                      run_info={"os": "linux"})
+
+    updated = update(tests, log_0, log_1)
+    new_manifest = updated[0][1]
+
+    assert new_manifest.is_empty
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_update_default_1():
+    test_id = "/path/to/test.htm"
+    tests = [("path/to/test.htm", [test_id], "testharness", """
+[test.htm]
+  expected:
+    if os == "mac": TIMEOUT
+    ERROR""")]
+
+    log_0 = suite_log([("test_start", {"test": test_id}),
+                       ("test_end", {"test": test_id,
+                                     "expected": "ERROR",
+                                     "status": "FAIL"})],
+                      run_info={"os": "linux"})
+
+    updated = update(tests, log_0)
+    new_manifest = updated[0][1]
+
+    assert not new_manifest.is_empty
+
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"os": "mac"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"os": "win"})
+
+    assert not new_manifest.is_empty
+    assert new_manifest.get_test(test_id).get(
+        "expected", run_info_1) == "TIMEOUT"
+    assert new_manifest.get_test(test_id).get(
+        "expected", run_info_2) == "FAIL"
+
+
+@pytest.mark.xfail(sys.version[0] == "3",
+                   reason="metadata doesn't support py3")
+def test_update_default_2():
+    test_id = "/path/to/test.htm"
+    tests = [("path/to/test.htm", [test_id], "testharness", """
+[test.htm]
+  expected:
+    if os == "mac": TIMEOUT
+    ERROR""")]
+
+    log_0 = suite_log([("test_start", {"test": test_id}),
+                       ("test_end", {"test": test_id,
+                                     "expected": "ERROR",
+                                     "status": "TIMEOUT"})],
+                      run_info={"os": "linux"})
+
+    updated = update(tests, log_0)
+    new_manifest = updated[0][1]
+
+    assert not new_manifest.is_empty
+
+    run_info_1 = default_run_info.copy()
+    run_info_1.update({"os": "mac"})
+    run_info_2 = default_run_info.copy()
+    run_info_2.update({"os": "win"})
+
+    assert not new_manifest.is_empty
+    assert new_manifest.get_test(test_id).get(
+        "expected", run_info_1) == "TIMEOUT"
+    assert new_manifest.get_test(test_id).get(
+        "expected", run_info_2) == "TIMEOUT"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_assertion_count_0():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   max-asserts: 4
@@ -393,18 +542,18 @@ def test_update_assertion_count_0():
                                             "max_expected": 4}),
                        ("test_end", {"test": test_id,
                                      "status": "OK"})])
 
     updated = update(tests, log_0)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).get("max-asserts") == 7
-    assert new_manifest.get_test(test_id).get("min-asserts") == 2
+    assert new_manifest.get_test(test_id).get("max-asserts") == "7"
+    assert new_manifest.get_test(test_id).get("min-asserts") == "2"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_assertion_count_1():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
   max-asserts: 4
@@ -418,17 +567,17 @@ def test_update_assertion_count_1():
                                             "max_expected": 4}),
                        ("test_end", {"test": test_id,
                                      "status": "OK"})])
 
     updated = update(tests, log_0)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).get("max-asserts") == 4
+    assert new_manifest.get_test(test_id).get("max-asserts") == "4"
     assert new_manifest.get_test(test_id).has_key("min-asserts") is False
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_assertion_count_2():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]
@@ -474,18 +623,18 @@ def test_update_assertion_count_3():
                        ("test_end", {"test": test_id,
                                      "status": "OK"})],
                       run_info={"os": "linux"})
 
     updated = update(tests, log_0, log_1)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
-    assert new_manifest.get_test(test_id).get("max-asserts") == 8
-    assert new_manifest.get_test(test_id).get("min-asserts") == 2
+    assert new_manifest.get_test(test_id).get("max-asserts") == "8"
+    assert new_manifest.get_test(test_id).get("min-asserts") == "2"
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_assertion_count_4():
     test_id = "/path/to/test.htm"
     tests = [("path/to/test.htm", [test_id], "testharness", """[test.htm]""")]
 
@@ -607,17 +756,17 @@ def test_update_lsan_3():
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_wptreport_0():
     tests = [("path/to/test.htm", ["/path/to/test.htm"], "testharness",
               """[test.htm]
   [test1]
     expected: FAIL""")]
 
-    log = {"run_info": {},
+    log = {"run_info": default_run_info.copy(),
            "results": [
                {"test": "/path/to/test.htm",
                 "subtests": [{"name": "test1",
                               "status": "PASS",
                               "expected": "FAIL"}],
                 "status": "OK"}
            ]}
 
@@ -628,17 +777,17 @@ def test_update_wptreport_0():
 
 
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="metadata doesn't support py3")
 def test_update_wptreport_1():
     tests = [("path/to/test.htm", ["/path/to/test.htm"], "testharness", ""),
              ("path/to/__dir__", ["path/to/__dir__"], None, "")]
 
-    log = {"run_info": {},
+    log = {"run_info": default_run_info.copy(),
            "results": [],
            "lsan_leaks": [{"scope": "path/to/",
                            "frames": ["baz", "foobar"]}]}
 
     updated = update(tests, log)
 
     assert len(updated) == 1
     assert updated[0][1].get("lsan-allowed") == ["baz"]
@@ -744,32 +893,164 @@ leak-total: 110""")]
 
     updated = update(tests, log_0)
     new_manifest = updated[0][1]
 
     assert not new_manifest.is_empty
     assert new_manifest.has_key("leak-threshold") is False
 
 
+def dump_tree(tree):
+    rv = []
+
+    def dump_node(node, indent=0):
+        prefix = " " * indent
+        if not node.prop:
+            data = "root"
+        else:
+            data = "%s:%s" % (node.prop, node.value)
+        if node.update_values:
+            data += " update_values:%s" % (",".join(sorted(node.update_values)))
+        rv.append("%s<%s>" % (prefix, data))
+        for child in sorted(node.children, key=lambda x:x.value):
+            dump_node(child, indent + 2)
+
+    dump_node(tree)
+    return "\n".join(rv)
+
+
+# @pytest.mark.xfail(sys.version[0] == "3",
+#                    reason="metadata doesn't support py3")
+# def test_property_tree():
+#     run_info_values = [{"os": "linux", "version": "18.04", "debug": False},
+#                        {"os": "linux", "version": "18.04", "debug": True},
+#                        {"os": "linux", "version": "16.04", "debug": False},
+#                        {"os": "mac", "version": "10.12", "debug": True},
+#                        {"os": "mac", "version": "10.12", "debug": False},
+#                        {"os": "win", "version": "7", "debug": False},
+#                        {"os": "win", "version": "10", "debug": False}]
+#     run_info_values = [metadata.RunInfo(item) for item in run_info_values]
+#     tree = metadata.build_property_tree(["os", "version", "debug"],
+#                                         run_info_values)
+
+#     expected = """<root>
+#   <os:linux>
+#     <version:16.04>
+#     <version:18.04>
+#       <debug:False>
+#       <debug:True>
+#   <os:mac>
+#     <debug:False>
+#     <debug:True>
+#   <os:win>
+#     <version:10>
+#     <version:7>"""
+
+#     assert dump_tree(tree) == expected
+
+
+# @pytest.mark.xfail(sys.version[0] == "3",
+#                    reason="metadata doesn't support py3")
+# def test_propogate_up():
+#     update_values = [({"os": "linux", "version": "18.04", "debug": False}, "FAIL"),
+#                      ({"os": "linux", "version": "18.04", "debug": True}, "FAIL"),
+#                      ({"os": "linux", "version": "16.04", "debug": False}, "FAIL"),
+#                      ({"os": "mac", "version": "10.12", "debug": True}, "PASS"),
+#                      ({"os": "mac", "version": "10.12", "debug": False}, "PASS"),
+#                      ({"os": "win", "version": "7", "debug": False}, "PASS"),
+#                      ({"os": "win", "version": "10", "debug": False}, "FAIL")]
+#     update_values = {metadata.RunInfo(item[0]): item[1] for item in update_values}
+#     tree = metadata.build_property_tree(["os", "version", "debug"],
+#                                         update_values.keys())
+#     for node in tree:
+#         for run_info in node.run_info:
+#             node.update_values.add(update_values[run_info])
+
+#     optimiser = manifestupdate.OptimiseConditionalTree()
+#     optimiser.propogate_up(tree)
+
+#     expected = """<root>
+#   <os:linux update_values:FAIL>
+#   <os:mac update_values:PASS>
+#   <os:win>
+#     <version:10 update_values:FAIL>
+#     <version:7 update_values:PASS>"""
+
+#     assert dump_tree(tree) == expected
+
+
+# @pytest.mark.xfail(sys.version[0] == "3",
+#                    reason="metadata doesn't support py3")
+# def test_common_properties():
+#     update_values = [({"os": "linux", "version": "18.04", "debug": False}, "PASS"),
+#                      ({"os": "linux", "version": "18.04", "debug": True}, "FAIL"),
+#                      ({"os": "linux", "version": "16.04", "debug": False}, "PASS"),
+#                      ({"os": "mac", "version": "10.12", "debug": True}, "FAIL"),
+#                      ({"os": "mac", "version": "10.12", "debug": False}, "PASS"),
+#                      ({"os": "win", "version": "7", "debug": False}, "PASS"),
+#                      ({"os": "win", "version": "10", "debug": False}, "PASS")]
+#     update_values = {metadata.RunInfo(item[0]): item[1] for item in update_values}
+#     tree = metadata.build_property_tree(["os", "version", "debug"],
+#                                         update_values.keys())
+#     for node in tree:
+#         for run_info in node.run_info:
+#             node.update_values.add(update_values[run_info])
+
+#     optimiser = manifestupdate.OptimiseConditionalTree()
+#     optimiser.propogate_up(tree)
+
+#     expected = """<root>
+#   <os:linux>
+#     <version:16.04 update_values:PASS>
+#     <version:18.04>
+#       <debug:False update_values:PASS>
+#       <debug:True update_values:FAIL>
+#   <os:mac>
+#     <debug:False update_values:PASS>
+#     <debug:True update_values:FAIL>
+#   <os:win update_values:PASS>"""
+
+#     assert dump_tree(tree) == expected
+
+
+#     optimiser.common_properties(tree)
+
+#     expected = """<root>
+#   <os:linux>
+#     <debug:False update_values:PASS>
+#     <debug:True update_values:FAIL>
+#   <os:mac update_values:PASS>
+#     <debug:False update_values:PASS>
+#     <debug:True update_values:FAIL>
+#   <os:win update_values: PASS>"""
+#     assert dump_tree(tree) == expected
+
+
 class TestStep(Step):
     def create(self, state):
         test_id = "/path/to/test.htm"
         tests = [("path/to/test.htm", [test_id], "testharness", "")]
         state.foo = create_test_manifest(tests)
 
+
 class UpdateRunner(StepRunner):
     steps = [TestStep]
 
+
 @pytest.mark.xfail(sys.version[0] == "3",
                    reason="update.state doesn't support py3")
 def test_update_pickle():
     logger = structuredlog.StructuredLogger("expected_test")
     args = {
         "test_paths": {
-            "/": {"tests_path": ""},
+            "/": {"tests_path": os.path.abspath(os.path.join(here,
+                                                             os.pardir,
+                                                             os.pardir,
+                                                             os.pardir,
+                                                             os.pardir))},
         },
         "abort": False,
         "continue": False,
         "sync": False,
     }
     args2 = args.copy()
     args2["abort"] = True
     wptupdate = WPTUpdate(logger, **args2)
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/update/metadata.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/update/metadata.py
@@ -1,23 +1,20 @@
 import os
 
 from .. import metadata, products
 
 from .base import Step, StepRunner
 
 
 class GetUpdatePropertyList(Step):
-    provides = ["property_order", "boolean_properties"]
+    provides = ["update_properties"]
 
     def create(self, state):
-        property_order, boolean_properties = products.load_product_update(
-            state.config, state.product)
-        state.property_order = (property_order or []) + state.extra_properties
-        state.boolean_properties = boolean_properties
+        state.update_properties = products.load_product_update(state.config, state.product)
 
 
 class UpdateExpected(Step):
     """Do the metadata update on the local checkout"""
 
     def create(self, state):
         if state.sync_tree is not None:
             sync_root = state.sync_tree.root
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/backends/conditional.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/backends/conditional.py
@@ -1,21 +1,23 @@
 import operator
 
-from ..node import NodeVisitor, DataNode, ConditionalNode, KeyValueNode, ListNode, ValueNode
+from ..node import NodeVisitor, DataNode, ConditionalNode, KeyValueNode, ListNode, ValueNode, BinaryExpressionNode
 from ..parser import parse
 
 
 class ConditionalValue(object):
     def __init__(self, node, condition_func):
         self.node = node
+        assert callable(condition_func)
         self.condition_func = condition_func
         if isinstance(node, ConditionalNode):
             assert len(node.children) == 2
             self.condition_node = self.node.children[0]
+            assert isinstance(node.children[1], (ValueNode, ListNode))
             self.value_node = self.node.children[1]
         else:
             assert isinstance(node, (ValueNode, ListNode))
             self.condition_node = None
             self.value_node = self.node
 
     @property
     def value(self):
@@ -186,16 +188,17 @@ class Compiler(NodeVisitor):
         assert operand_1 is not None
 
         return lambda x: operator(operand_0(x), operand_1(x))
 
     def visit_UnaryOperatorNode(self, node):
         return {"not": operator.not_}[node.data]
 
     def visit_BinaryOperatorNode(self, node):
+        assert isinstance(node.parent, BinaryExpressionNode)
         return {"and": operator.and_,
                 "or": operator.or_,
                 "==": operator.eq,
                 "!=": operator.ne}[node.data]
 
 
 class ManifestItem(object):
     def __init__(self, node=None, **kwargs):
@@ -211,16 +214,22 @@ class ManifestItem(object):
         rv = [repr(self)]
         for item in self.children:
             rv.extend("  %s" % line for line in str(item).split("\n"))
         return "\n".join(rv)
 
     def __contains__(self, key):
         return key in self._data
 
+    def __iter__(self):
+        yield self
+        for child in self.children:
+            for node in child:
+                yield node
+
     @property
     def is_empty(self):
         if self._data:
             return False
         return all(child.is_empty for child in self.children)
 
     @property
     def root(self):
@@ -277,34 +286,52 @@ class ManifestItem(object):
 
         if isinstance(value, list):
             value_node = ListNode()
             for item in value:
                 value_node.append(ValueNode(unicode(item)))
         else:
             value_node = ValueNode(unicode(value))
         if condition is not None:
-            conditional_node = ConditionalNode()
-            conditional_node.append(condition)
-            conditional_node.append(value_node)
+            if not isinstance(condition, ConditionalNode):
+                conditional_node = ConditionalNode()
+                conditional_node.append(condition)
+                conditional_node.append(value_node)
+            else:
+                conditional_node = condition
             node.append(conditional_node)
             cond_value = Compiler().compile_condition(conditional_node)
         else:
             node.append(value_node)
             cond_value = ConditionalValue(value_node, lambda x: True)
 
         # Update the cache of child values. This is pretty annoying and maybe
         # it should just work directly on the tree
         if key not in self._data:
             self._data[key] = []
         if self._data[key] and self._data[key][-1].condition_node is None:
             self._data[key].insert(len(self._data[key]) - 1, cond_value)
         else:
             self._data[key].append(cond_value)
 
+    def clear(self, key):
+        """Clear all the expected data for this node"""
+        if key in self._data:
+            for child in self.node.children:
+                if (isinstance(child, KeyValueNode) and
+                    child.data == key):
+                    child.remove()
+                    del self._data[key]
+                    break
+
+    def get_conditions(self, property_name):
+        if property_name in self._data:
+            return self._data[property_name]
+        return []
+
     def _add_key_value(self, node, values):
         """Called during construction to set a key-value node"""
         self._data[node.data] = values
 
     def append(self, child):
         self.children.append(child)
         child.parent = self
         if child.node.parent != self.node:
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/node.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/node.py
@@ -62,19 +62,21 @@ class DataNode(Node):
             self.children.insert(index, other)
 
 
 class KeyValueNode(Node):
     def append(self, other):
         # Append that retains the invariant that conditional nodes
         # come before unconditional nodes
         other.parent = self
-        if isinstance(other, ValueNode):
+        if not isinstance(other, (ListNode, ValueNode, ConditionalNode)):
+            raise TypeError
+        if isinstance(other, (ListNode, ValueNode)):
             if self.children:
-                assert not isinstance(self.children[-1], ValueNode)
+                assert not isinstance(self.children[-1], (ListNode, ValueNode))
             self.children.append(other)
         else:
             if self.children and isinstance(self.children[-1], ValueNode):
                 self.children.insert(len(self.children) - 1, other)
             else:
                 self.children.append(other)
 
 
@@ -89,17 +91,27 @@ class ValueNode(Node):
         raise TypeError
 
 
 class AtomNode(ValueNode):
     pass
 
 
 class ConditionalNode(Node):
-    pass
+    def append(self, other):
+        if not len(self.children):
+            if not isinstance(other, (BinaryExpressionNode, UnaryExpressionNode, VariableNode)):
+                raise TypeError
+        else:
+            if len(self.children) > 1:
+                raise ValueError
+            if not isinstance(other, (ListNode, ValueNode)):
+                raise TypeError
+        other.parent = self
+        self.children.append(other)
 
 
 class UnaryExpressionNode(Node):
     def __init__(self, operator, operand):
         Node.__init__(self)
         self.append(operator)
         self.append(operand)
 
--- a/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/parser.py
+++ b/testing/web-platform/tests/tools/wptrunner/wptrunner/wptmanifest/parser.py
@@ -11,17 +11,17 @@
 #
 
 # TODO: keep comments in the tree
 
 from __future__ import unicode_literals
 
 from six import binary_type, text_type, BytesIO
 
-from .node import (AtomNode, BinaryExpressionNode, BinaryOperatorNode,
+from .node import (Node, AtomNode, BinaryExpressionNode, BinaryOperatorNode,
                    ConditionalNode, DataNode, IndexNode, KeyValueNode, ListNode,
                    NumberNode, StringNode, UnaryExpressionNode,
                    UnaryOperatorNode, ValueNode, VariableNode)
 
 
 class ParseError(Exception):
     def __init__(self, filename, line, detail):
         self.line = line
@@ -693,23 +693,26 @@ class Parser(object):
 
 
 class Treebuilder(object):
     def __init__(self, root):
         self.root = root
         self.node = root
 
     def append(self, node):
+        assert isinstance(node, Node)
         self.node.append(node)
         self.node = node
+        assert self.node is not None
         return node
 
     def pop(self):
         node = self.node
         self.node = self.node.parent
+        assert self.node is not None
         return node
 
 
 class ExpressionBuilder(object):
     def __init__(self, tokenizer):
         self.operands = []
         self.operators = [None]
         self.tokenizer = tokenizer