1import os
2from urllib.parse import urljoin, urlsplit
3from collections import namedtuple, defaultdict, deque
4from math import ceil
5from typing import Any, Callable, ClassVar, Dict, List
6
7from .wptmanifest import serialize
8from .wptmanifest.node import (DataNode, ConditionalNode, BinaryExpressionNode,
9                              BinaryOperatorNode, NumberNode, StringNode, VariableNode,
10                              ValueNode, UnaryExpressionNode, UnaryOperatorNode,
11                              ListNode)
12from .wptmanifest.backends import conditional
13from .wptmanifest.backends.conditional import ManifestItem
14
15from . import expected
16from . import expectedtree
17
18"""Manifest structure used to update the expected results of a test
19
20Each manifest file is represented by an ExpectedManifest that has one
21or more TestNode children, one per test in the manifest.  Each
22TestNode has zero or more SubtestNode children, one for each known
23subtest of the test.
24
25In these representations, conditionals expressions in the manifest are
26not evaluated upfront but stored as python functions to be evaluated
27at runtime.
28
29When a result for a test is to be updated set_result on the
30[Sub]TestNode is called to store the new result, alongside the
31existing conditional that result's run info matched, if any. Once all
32new results are known, update is called to compute the new
33set of results and conditionals. The AST of the underlying parsed manifest
34is updated with the changes, and the result is serialised to a file.
35"""
36
37
38class ConditionError(Exception):
39    def __init__(self, cond=None):
40        self.cond = cond
41
42
43class UpdateError(Exception):
44    pass
45
46
47Value = namedtuple("Value", ["run_info", "value"])
48
49
50def data_cls_getter(output_node, visited_node):
51    # visited_node is intentionally unused
52    if output_node is None:
53        return ExpectedManifest
54    elif isinstance(output_node, ExpectedManifest):
55        return TestNode
56    elif isinstance(output_node, TestNode):
57        return SubtestNode
58    else:
59        raise ValueError
60
61
62class UpdateProperties(object):
63    def __init__(self, manifest, **kwargs):
64        self._manifest = manifest
65        self._classes = kwargs
66
67    def __getattr__(self, name):
68        if name in self._classes:
69            rv = self._classes[name](self._manifest)
70            setattr(self, name, rv)
71            return rv
72        raise AttributeError
73
74    def __contains__(self, name):
75        return name in self._classes
76
77    def __iter__(self):
78        for name in self._classes.keys():
79            yield getattr(self, name)
80
81
82class ExpectedManifest(ManifestItem):
83    def __init__(self, node, test_path, url_base, run_info_properties,
84                 update_intermittent=False, remove_intermittent=False):
85        """Object representing all the tests in a particular manifest
86
87        :param node: AST Node associated with this object. If this is None,
88                     a new AST is created to associate with this manifest.
89        :param test_path: Path of the test file associated with this manifest.
90        :param url_base: Base url for serving the tests in this manifest.
91        :param run_info_properties: Tuple of ([property name],
92                                              {property_name: [dependent property]})
93                                    The first part lists run_info properties
94                                    that are always used in the update, the second
95                                    maps property names to additional properties that
96                                    can be considered if we already have a condition on
97                                    the key property e.g. {"foo": ["bar"]} means that
98                                    we consider making conditions on bar only after we
99                                    already made one on foo.
100        :param update_intermittent: When True, intermittent statuses will be recorded
101                                    as `expected` in the test metadata.
102        :param: remove_intermittent: When True, old intermittent statuses will be removed
103                                    if no longer intermittent. This is only relevant if
104                                    `update_intermittent` is also True, because if False,
105                                    the metadata will simply update one `expected`status.
106        """
107        if node is None:
108            node = DataNode(None)
109        ManifestItem.__init__(self, node)
110        self.child_map = {}
111        self.test_path = test_path
112        self.url_base = url_base
113        assert self.url_base is not None
114        self._modified = False
115        self.run_info_properties = run_info_properties
116        self.update_intermittent = update_intermittent
117        self.remove_intermittent = remove_intermittent
118        self.update_properties = UpdateProperties(self, **{
119            "lsan": LsanUpdate,
120            "leak_object": LeakObjectUpdate,
121            "leak_threshold": LeakThresholdUpdate,
122        })
123
124    @property
125    def modified(self):
126        if self._modified:
127            return True
128        return any(item.modified for item in self.children)
129
130    @modified.setter
131    def modified(self, value):
132        self._modified = value
133
134    def append(self, child):
135        ManifestItem.append(self, child)
136        if child.id in self.child_map:
137            print("Warning: Duplicate heading %s" % child.id)
138        self.child_map[child.id] = child
139
140    def _remove_child(self, child):
141        del self.child_map[child.id]
142        ManifestItem._remove_child(self, child)
143
144    def get_test(self, test_id):
145        """Return a TestNode by test id, or None if no test matches
146
147        :param test_id: The id of the test to look up"""
148
149        return self.child_map.get(test_id)
150
151    def has_test(self, test_id):
152        """Boolean indicating whether the current test has a known child test
153        with id test id
154
155        :param test_id: The id of the test to look up"""
156
157        return test_id in self.child_map
158
159    @property
160    def url(self):
161        return urljoin(self.url_base,
162                       "/".join(self.test_path.split(os.path.sep)))
163
164    def set_lsan(self, run_info, result):
165        """Set the result of the test in a particular run
166
167        :param run_info: Dictionary of run_info parameters corresponding
168                         to this run
169        :param result: Lsan violations detected"""
170        self.update_properties.lsan.set(run_info, result)
171
172    def set_leak_object(self, run_info, result):
173        """Set the result of the test in a particular run
174
175        :param run_info: Dictionary of run_info parameters corresponding
176                         to this run
177        :param result: Leaked objects deletec"""
178        self.update_properties.leak_object.set(run_info, result)
179
180    def set_leak_threshold(self, run_info, result):
181        """Set the result of the test in a particular run
182
183        :param run_info: Dictionary of run_info parameters corresponding
184                         to this run
185        :param result: Total number of bytes leaked"""
186        self.update_properties.leak_threshold.set(run_info, result)
187
188    def update(self, full_update, disable_intermittent):
189        for prop_update in self.update_properties:
190            prop_update.update(full_update,
191                               disable_intermittent)
192
193
194class TestNode(ManifestItem):
195    def __init__(self, node):
196        """Tree node associated with a particular test in a manifest
197
198        :param node: AST node associated with the test"""
199
200        ManifestItem.__init__(self, node)
201        self.subtests = {}
202        self._from_file = True
203        self.new_disabled = False
204        self.has_result = False
205        self.modified = False
206        self.update_properties = UpdateProperties(
207            self,
208            expected=ExpectedUpdate,
209            max_asserts=MaxAssertsUpdate,
210            min_asserts=MinAssertsUpdate
211        )
212
213    @classmethod
214    def create(cls, test_id):
215        """Create a TestNode corresponding to a given test
216
217        :param test_type: The type of the test
218        :param test_id: The id of the test"""
219        name = test_id[len(urlsplit(test_id).path.rsplit("/", 1)[0]) + 1:]
220        node = DataNode(name)
221        self = cls(node)
222
223        self._from_file = False
224        return self
225
226    @property
227    def is_empty(self):
228        ignore_keys = {"type"}
229        if set(self._data.keys()) - ignore_keys:
230            return False
231        return all(child.is_empty for child in self.children)
232
233    @property
234    def test_type(self):
235        """The type of the test represented by this TestNode"""
236        return self.get("type", None)
237
238    @property
239    def id(self):
240        """The id of the test represented by this TestNode"""
241        return urljoin(self.parent.url, self.name)
242
243    def disabled(self, run_info):
244        """Boolean indicating whether this test is disabled when run in an
245        environment with the given run_info
246
247        :param run_info: Dictionary of run_info parameters"""
248
249        return self.get("disabled", run_info) is not None
250
251    def set_result(self, run_info, result):
252        """Set the result of the test in a particular run
253
254        :param run_info: Dictionary of run_info parameters corresponding
255                         to this run
256        :param result: Status of the test in this run"""
257        self.update_properties.expected.set(run_info, result)
258
259    def set_asserts(self, run_info, count):
260        """Set the assert count of a test
261
262        """
263        self.update_properties.min_asserts.set(run_info, count)
264        self.update_properties.max_asserts.set(run_info, count)
265
266    def append(self, node):
267        child = ManifestItem.append(self, node)
268        self.subtests[child.name] = child
269
270    def get_subtest(self, name):
271        """Return a SubtestNode corresponding to a particular subtest of
272        the current test, creating a new one if no subtest with that name
273        already exists.
274
275        :param name: Name of the subtest"""
276
277        if name in self.subtests:
278            return self.subtests[name]
279        else:
280            subtest = SubtestNode.create(name)
281            self.append(subtest)
282            return subtest
283
284    def update(self, full_update, disable_intermittent):
285        for prop_update in self.update_properties:
286            prop_update.update(full_update,
287                               disable_intermittent)
288
289
290class SubtestNode(TestNode):
291    def __init__(self, node):
292        assert isinstance(node, DataNode)
293        TestNode.__init__(self, node)
294
295    @classmethod
296    def create(cls, name):
297        node = DataNode(name)
298        self = cls(node)
299        return self
300
301    @property
302    def is_empty(self):
303        if self._data:
304            return False
305        return True
306
307
308def build_conditional_tree(_, run_info_properties, results):
309    properties, dependent_props = run_info_properties
310    return expectedtree.build_tree(properties, dependent_props, results)
311
312
313def build_unconditional_tree(_, run_info_properties, results):
314    root = expectedtree.Node(None, None)
315    for run_info, values in results.items():
316        for value, count in values.items():
317            root.result_values[value] += count
318        root.run_info.add(run_info)
319    return root
320
321
322class PropertyUpdate(object):
323    property_name = None  # type: ClassVar[str]
324    cls_default_value = None  # type: ClassVar[Any]
325    value_type = None  # type: ClassVar[type]
326    # property_builder is a class variable set to either build_conditional_tree
327    # or build_unconditional_tree. TODO: Make this type stricter when those
328    # methods are annotated.
329    property_builder = None  # type: ClassVar[Callable[..., Any]]
330
331    def __init__(self, node):
332        self.node = node
333        self.default_value = self.cls_default_value
334        self.has_result = False
335        self.results = defaultdict(lambda: defaultdict(int))
336        self.update_intermittent = self.node.root.update_intermittent
337        self.remove_intermittent = self.node.root.remove_intermittent
338
339    def run_info_by_condition(self, run_info_index, conditions):
340        run_info_by_condition = defaultdict(list)
341        # A condition might match 0 or more run_info values
342        run_infos = run_info_index.keys()
343        for cond in conditions:
344            for run_info in run_infos:
345                if cond(run_info):
346                    run_info_by_condition[cond].append(run_info)
347
348        return run_info_by_condition
349
350    def set(self, run_info, value):
351        self.has_result = True
352        self.node.has_result = True
353        self.check_default(value)
354        value = self.from_result_value(value)
355        self.results[run_info][value] += 1
356
357    def check_default(self, result):
358        return
359
360    def from_result_value(self, value):
361        """Convert a value from a test result into the internal format"""
362        return value
363
364    def from_ini_value(self, value):
365        """Convert a value from an ini file into the internal format"""
366        if self.value_type:
367            return self.value_type(value)
368        return value
369
370    def to_ini_value(self, value):
371        """Convert a value from the internal format to the ini file format"""
372        return str(value)
373
374    def updated_value(self, current, new):
375        """Given a single current value and a set of observed new values,
376        compute an updated value for the property"""
377        return new
378
379    @property
380    def unconditional_value(self):
381        try:
382            unconditional_value = self.from_ini_value(
383                self.node.get(self.property_name))
384        except KeyError:
385            unconditional_value = self.default_value
386        return unconditional_value
387
388    def update(self,
389               full_update=False,
390               disable_intermittent=None):
391        """Update the underlying manifest AST for this test based on all the
392        added results.
393
394        This will update existing conditionals if they got the same result in
395        all matching runs in the updated results, will delete existing conditionals
396        that get more than one different result in the updated run, and add new
397        conditionals for anything that doesn't match an existing conditional.
398
399        Conditionals not matched by any added result are not changed.
400
401        When `disable_intermittent` is not None, disable any test that shows multiple
402        unexpected results for the same set of parameters.
403        """
404        if not self.has_result:
405            return
406
407        property_tree = self.property_builder(self.node.root.run_info_properties,
408                                              self.results)
409
410        conditions, errors = self.update_conditions(property_tree,
411                                                    full_update)
412
413        for e in errors:
414            if disable_intermittent:
415                condition = e.cond.children[0] if e.cond else None
416                msg = disable_intermittent if isinstance(disable_intermittent, str) else "unstable"
417                self.node.set("disabled", msg, condition)
418                self.node.new_disabled = True
419            else:
420                msg = "Conflicting metadata values for %s" % (
421                    self.node.root.test_path)
422                if e.cond:
423                    msg += ": %s" % serialize(e.cond).strip()
424                print(msg)
425
426        # If all the values match remove all conditionals
427        # This handles the case where we update a number of existing conditions and they
428        # all end up looking like the post-update default.
429        new_default = self.default_value
430        if conditions and conditions[-1][0] is None:
431            new_default = conditions[-1][1]
432        if all(condition[1] == new_default for condition in conditions):
433            conditions = [(None, new_default)]
434
435        # Don't set the default to the class default
436        if (conditions and
437            conditions[-1][0] is None and
438            conditions[-1][1] == self.default_value):
439            self.node.modified = True
440            conditions = conditions[:-1]
441
442        if self.node.modified:
443            self.node.clear(self.property_name)
444
445            for condition, value in conditions:
446                self.node.set(self.property_name,
447                              self.to_ini_value(value),
448                              condition)
449
450    def update_conditions(self,
451                          property_tree,
452                          full_update):
453        # This is complicated because the expected behaviour is complex
454        # The complexity arises from the fact that there are two ways of running
455        # the tool, with a full set of runs (full_update=True) or with partial metadata
456        # (full_update=False). In the case of a full update things are relatively simple:
457        # * All existing conditionals are ignored, with the exception of conditionals that
458        #   depend on variables not used by the updater, which are retained as-is
459        # * All created conditionals are independent of each other (i.e. order isn't
460        #   important in the created conditionals)
461        # In the case where we don't have a full set of runs, the expected behaviour
462        # is much less clear. This is of course the common case for when a developer
463        # runs the test on their own machine. In this case the assumptions above are untrue
464        # * The existing conditions may be required to handle other platforms
465        # * The order of the conditions may be important, since we don't know if they overlap
466        #   e.g. `if os == linux and version == 18.04` overlaps with `if (os != win)`.
467        # So in the case we have a full set of runs, the process is pretty simple:
468        # * Generate the conditionals for the property_tree
469        # * Pick the most common value as the default and add only those conditions
470        #   not matching the default
471        # In the case where we have a partial set of runs, things are more complex
472        # and more best-effort
473        # * For each existing conditional, see if it matches any of the run info we
474        #   have. In cases where it does match, record the new results
475        # * Where all the new results match, update the right hand side of that
476        #   conditional, otherwise remove it
477        # * If this leaves nothing existing, then proceed as with the full update
478        # * Otherwise add conditionals for the run_info that doesn't match any
479        #   remaining conditions
480        prev_default = None
481
482        current_conditions = self.node.get_conditions(self.property_name)
483
484        # Ignore the current default value
485        if current_conditions and current_conditions[-1].condition_node is None:
486            self.node.modified = True
487            prev_default = current_conditions[-1].value
488            current_conditions = current_conditions[:-1]
489
490        # If there aren't any current conditions, or there is just a default
491        # value for all run_info, proceed as for a full update
492        if not current_conditions:
493            return self._update_conditions_full(property_tree,
494                                                prev_default=prev_default)
495
496        conditions = []
497        errors = []
498
499        run_info_index = {run_info: node
500                          for node in property_tree
501                          for run_info in node.run_info}
502
503        node_by_run_info = {run_info: node
504                            for (run_info, node) in run_info_index.items()
505                            if node.result_values}
506
507        run_info_by_condition = self.run_info_by_condition(run_info_index,
508                                                           current_conditions)
509
510        run_info_with_condition = set()
511
512        if full_update:
513            # Even for a full update we need to keep hand-written conditions not
514            # using the properties we've specified and not matching any run_info
515            top_level_props, dependent_props = self.node.root.run_info_properties
516            update_properties = set(top_level_props)
517            for item in dependent_props.values():
518                update_properties |= set(item)
519            for condition in current_conditions:
520                if ((not condition.variables.issubset(update_properties) and
521                     not run_info_by_condition[condition])):
522                    conditions.append((condition.condition_node,
523                                       self.from_ini_value(condition.value)))
524
525            new_conditions, errors = self._update_conditions_full(property_tree,
526                                                                  prev_default=prev_default)
527            conditions.extend(new_conditions)
528            return conditions, errors
529
530        # Retain existing conditions if they match the updated values
531        for condition in current_conditions:
532            # All run_info that isn't handled by some previous condition
533            all_run_infos_condition = run_info_by_condition[condition]
534            run_infos = {item for item in all_run_infos_condition
535                         if item not in run_info_with_condition}
536
537            if not run_infos:
538                # Retain existing conditions that don't match anything in the update
539                conditions.append((condition.condition_node,
540                                   self.from_ini_value(condition.value)))
541                continue
542
543            # Set of nodes in the updated tree that match the same run_info values as the
544            # current existing node
545            nodes = [node_by_run_info[run_info] for run_info in run_infos
546                     if run_info in node_by_run_info]
547            # If all the values are the same, update the value
548            if nodes and all(set(node.result_values.keys()) == set(nodes[0].result_values.keys()) for node in nodes):
549                current_value = self.from_ini_value(condition.value)
550                try:
551                    new_value = self.updated_value(current_value,
552                                                   nodes[0].result_values)
553                except ConditionError as e:
554                    errors.append(e)
555                    continue
556                if new_value != current_value:
557                    self.node.modified = True
558                conditions.append((condition.condition_node, new_value))
559                run_info_with_condition |= set(run_infos)
560            else:
561                # Don't append this condition
562                self.node.modified = True
563
564        new_conditions, new_errors = self.build_tree_conditions(property_tree,
565                                                                run_info_with_condition,
566                                                                prev_default)
567        if new_conditions:
568            self.node.modified = True
569
570        conditions.extend(new_conditions)
571        errors.extend(new_errors)
572
573        return conditions, errors
574
575    def _update_conditions_full(self,
576                                property_tree,
577                                prev_default=None):
578        self.node.modified = True
579        conditions, errors = self.build_tree_conditions(property_tree,
580                                                        set(),
581                                                        prev_default)
582
583        return conditions, errors
584
585    def build_tree_conditions(self,
586                              property_tree,
587                              run_info_with_condition,
588                              prev_default=None):
589        conditions = []
590        errors = []
591
592        value_count = defaultdict(int)
593
594        def to_count_value(v):
595            if v is None:
596                return v
597            # Need to count the values in a hashable type
598            count_value = self.to_ini_value(v)
599            if isinstance(count_value, list):
600                count_value = tuple(count_value)
601            return count_value
602
603
604        queue = deque([(property_tree, [])])
605        while queue:
606            node, parents = queue.popleft()
607            parents_and_self = parents + [node]
608            if node.result_values and any(run_info not in run_info_with_condition
609                                          for run_info in node.run_info):
610                prop_set = [(item.prop, item.value) for item in parents_and_self if item.prop]
611                value = node.result_values
612                error = None
613                if parents:
614                    try:
615                        value = self.updated_value(None, value)
616                    except ConditionError:
617                        expr = make_expr(prop_set, value)
618                        error = ConditionError(expr)
619                    else:
620                        expr = make_expr(prop_set, value)
621                else:
622                    # The root node needs special handling
623                    expr = None
624                    try:
625                        value = self.updated_value(self.unconditional_value,
626                                                   value)
627                    except ConditionError:
628                        error = ConditionError(expr)
629                        # If we got an error for the root node, re-add the previous
630                        # default value
631                        if prev_default:
632                            conditions.append((None, prev_default))
633                if error is None:
634                    count_value = to_count_value(value)
635                    value_count[count_value] += len(node.run_info)
636
637                if error is None:
638                    conditions.append((expr, value))
639                else:
640                    errors.append(error)
641
642            for child in node.children:
643                queue.append((child, parents_and_self))
644
645        conditions = conditions[::-1]
646
647        # If we haven't set a default condition, add one and remove all the conditions
648        # with the same value
649        if value_count and (not conditions or conditions[-1][0] is not None):
650            # Sort in order of occurence, prioritising values that match the class default
651            # or the previous default
652            cls_default = to_count_value(self.default_value)
653            prev_default = to_count_value(prev_default)
654            commonest_value = max(value_count, key=lambda x:(value_count.get(x),
655                                                             x == cls_default,
656                                                             x == prev_default))
657            if isinstance(commonest_value, tuple):
658                commonest_value = list(commonest_value)
659            commonest_value = self.from_ini_value(commonest_value)
660            conditions = [item for item in conditions if item[1] != commonest_value]
661            conditions.append((None, commonest_value))
662
663        return conditions, errors
664
665
666class ExpectedUpdate(PropertyUpdate):
667    property_name = "expected"
668    property_builder = build_conditional_tree
669
670    def check_default(self, result):
671        if self.default_value is not None:
672            assert self.default_value == result.default_expected
673        else:
674            self.default_value = result.default_expected
675
676    def from_result_value(self, result):
677        # When we are updating intermittents, we need to keep a record of any existing
678        # intermittents to pass on when building the property tree and matching statuses and
679        # intermittents to the correct run info -  this is so we can add them back into the
680        # metadata aligned with the right conditions, unless specified not to with
681        # self.remove_intermittent.
682        # The (status, known_intermittent) tuple is counted when the property tree is built, but
683        # the count value only applies to the first item in the tuple, the status from that run,
684        # when passed to `updated_value`.
685        if (not self.update_intermittent or
686            self.remove_intermittent or
687            not result.known_intermittent):
688            return result.status
689        return result.status + result.known_intermittent
690
691    def to_ini_value(self, value):
692        if isinstance(value, (list, tuple)):
693            return [str(item) for item in value]
694        return str(value)
695
696    def updated_value(self, current, new):
697        if len(new) > 1 and not self.update_intermittent and not isinstance(current, list):
698            raise ConditionError
699
700        counts = {}
701        for status, count in new.items():
702            if isinstance(status, tuple):
703                counts[status[0]] = count
704                counts.update({intermittent: 0 for intermittent in status[1:] if intermittent not in counts})
705            else:
706                counts[status] = count
707
708        if not (self.update_intermittent or isinstance(current, list)):
709            return list(counts)[0]
710
711        # Reorder statuses first based on counts, then based on status priority if there are ties.
712        # Counts with 0 are considered intermittent.
713        statuses = ["OK", "PASS", "FAIL", "ERROR", "TIMEOUT", "CRASH"]
714        status_priority = {value: i for i, value in enumerate(statuses)}
715        sorted_new = sorted(counts.items(), key=lambda x:(-1 * x[1],
716                                                        status_priority.get(x[0],
717                                                        len(status_priority))))
718        expected = []
719        for status, count in sorted_new:
720            # If we are not removing existing recorded intermittents, with a count of 0,
721            # add them in to expected.
722            if count > 0 or not self.remove_intermittent:
723                expected.append(status)
724
725        # If the new intermittent is a subset of the existing one, just use the existing one
726        # This prevents frequent flip-flopping of results between e.g. [OK, TIMEOUT] and
727        # [TIMEOUT, OK]
728        if current and set(expected).issubset(set(current)):
729            return current
730
731        if self.update_intermittent:
732            if len(expected) == 1:
733                return expected[0]
734            return expected
735
736        # If we are not updating intermittents, return the status with the highest occurence.
737        return expected[0]
738
739
740class MaxAssertsUpdate(PropertyUpdate):
741    """For asserts we always update the default value and never add new conditionals.
742    The value we set as the default is the maximum the current default or one more than the
743    number of asserts we saw in any configuration."""
744
745    property_name = "max-asserts"
746    cls_default_value = 0
747    value_type = int
748    property_builder = build_unconditional_tree
749
750    def updated_value(self, current, new):
751        if any(item > current for item in new):
752            return max(new) + 1
753        return current
754
755
756class MinAssertsUpdate(PropertyUpdate):
757    property_name = "min-asserts"
758    cls_default_value = 0
759    value_type = int
760    property_builder = build_unconditional_tree
761
762    def updated_value(self, current, new):
763        if any(item < current for item in new):
764            rv = min(new) - 1
765        else:
766            rv = current
767        return max(rv, 0)
768
769
770class AppendOnlyListUpdate(PropertyUpdate):
771    cls_default_value = []  # type: ClassVar[List[str]]
772    property_builder = build_unconditional_tree
773
774    def updated_value(self, current, new):
775        if current is None:
776            rv = set()
777        else:
778            rv = set(current)
779
780        for item in new:
781            if item is None:
782                continue
783            elif isinstance(item, str):
784                rv.add(item)
785            else:
786                rv |= item
787
788        return sorted(rv)
789
790
791class LsanUpdate(AppendOnlyListUpdate):
792    property_name = "lsan-allowed"
793    property_builder = build_unconditional_tree
794
795    def from_result_value(self, result):
796        # If we have an allowed_match that matched, return None
797        # This value is ignored later (because it matches the default)
798        # We do that because then if we allow a failure in foo/__dir__.ini
799        # we don't want to update foo/bar/__dir__.ini with the same rule
800        if result[1]:
801            return None
802        # Otherwise return the topmost stack frame
803        # TODO: there is probably some improvement to be made by looking for a "better" stack frame
804        return result[0][0]
805
806    def to_ini_value(self, value):
807        return value
808
809
810class LeakObjectUpdate(AppendOnlyListUpdate):
811    property_name = "leak-allowed"
812    property_builder = build_unconditional_tree
813
814    def from_result_value(self, result):
815        # If we have an allowed_match that matched, return None
816        if result[1]:
817            return None
818        # Otherwise return the process/object name
819        return result[0]
820
821
822class LeakThresholdUpdate(PropertyUpdate):
823    property_name = "leak-threshold"
824    cls_default_value = {}  # type: ClassVar[Dict[str, int]]
825    property_builder = build_unconditional_tree
826
827    def from_result_value(self, result):
828        return result
829
830    def to_ini_value(self, data):
831        return ["%s:%s" % item for item in sorted(data.items())]
832
833    def from_ini_value(self, data):
834        rv = {}
835        for item in data:
836            key, value = item.split(":", 1)
837            rv[key] = int(float(value))
838        return rv
839
840    def updated_value(self, current, new):
841        if current:
842            rv = current.copy()
843        else:
844            rv = {}
845        for process, leaked_bytes, threshold in new:
846            # If the value is less than the threshold but there isn't
847            # an old value we must have inherited the threshold from
848            # a parent ini file so don't any anything to this one
849            if process not in rv and leaked_bytes < threshold:
850                continue
851            if leaked_bytes > rv.get(process, 0):
852                # Round up to nearest 50 kb
853                boundary = 50 * 1024
854                rv[process] = int(boundary * ceil(float(leaked_bytes) / boundary))
855        return rv
856
857
858def make_expr(prop_set, rhs):
859    """Create an AST that returns the value ``status`` given all the
860    properties in prop_set match.
861
862    :param prop_set: tuple of (property name, value) pairs for each
863                     property in this expression and the value it must match
864    :param status: Status on RHS when all the given properties match
865    """
866    root = ConditionalNode()
867
868    assert len(prop_set) > 0
869
870    expressions = []
871    for prop, value in prop_set:
872        if value not in (True, False):
873            expressions.append(
874                BinaryExpressionNode(
875                    BinaryOperatorNode("=="),
876                    VariableNode(prop),
877                    make_node(value)))
878        else:
879            if value:
880                expressions.append(VariableNode(prop))
881            else:
882                expressions.append(
883                    UnaryExpressionNode(
884                        UnaryOperatorNode("not"),
885                        VariableNode(prop)
886                    ))
887    if len(expressions) > 1:
888        prev = expressions[-1]
889        for curr in reversed(expressions[:-1]):
890            node = BinaryExpressionNode(
891                BinaryOperatorNode("and"),
892                curr,
893                prev)
894            prev = node
895    else:
896        node = expressions[0]
897
898    root.append(node)
899    rhs_node = make_value_node(rhs)
900    root.append(rhs_node)
901
902    return root
903
904
905def make_node(value):
906    if isinstance(value, (int, float,)):
907        node = NumberNode(value)
908    elif isinstance(value, str):
909        node = StringNode(str(value))
910    elif hasattr(value, "__iter__"):
911        node = ListNode()
912        for item in value:
913            node.append(make_node(item))
914    return node
915
916
917def make_value_node(value):
918    if isinstance(value, (int, float,)):
919        node = ValueNode(value)
920    elif isinstance(value, str):
921        node = ValueNode(str(value))
922    elif hasattr(value, "__iter__"):
923        node = ListNode()
924        for item in value:
925            node.append(make_value_node(item))
926    else:
927        raise ValueError("Don't know how to convert %s into node" % type(value))
928    return node
929
930
931def get_manifest(metadata_root, test_path, url_base, run_info_properties, update_intermittent, remove_intermittent):
932    """Get the ExpectedManifest for a particular test path, or None if there is no
933    metadata stored for that test path.
934
935    :param metadata_root: Absolute path to the root of the metadata directory
936    :param test_path: Path to the test(s) relative to the test root
937    :param url_base: Base url for serving the tests in this manifest"""
938    manifest_path = expected.expected_path(metadata_root, test_path)
939    try:
940        with open(manifest_path, "rb") as f:
941            rv = compile(f, test_path, url_base,
942                         run_info_properties, update_intermittent, remove_intermittent)
943    except IOError:
944        return None
945    return rv
946
947
948def compile(manifest_file, test_path, url_base, run_info_properties, update_intermittent, remove_intermittent):
949    return conditional.compile(manifest_file,
950                               data_cls_getter=data_cls_getter,
951                               test_path=test_path,
952                               url_base=url_base,
953                               run_info_properties=run_info_properties,
954                               update_intermittent=update_intermittent,
955                               remove_intermittent=remove_intermittent)
956