1#!/usr/bin/env python
2#
3# Copyright 2014, NICTA
4#
5# This software may be distributed and modified according to the terms of
6# the BSD 2-Clause license. Note that NO WARRANTY is provided.
7# See "LICENSE_BSD2.txt" for details.
8#
9# @TAG(NICTA_BSD)
10#
11
12import os
13import heapq
14import argparse
15import sys
16
17from lxml import etree
18
19REGRESSION_DIR = os.path.dirname(os.path.realpath(__file__))
20REGRESSION_DTD = os.path.join(REGRESSION_DIR, "regression.dtd")
21
22class TestSpecParseException(Exception):
23    pass
24
25class TestEnv(object):
26
27    def __init__(self, base_dir):
28        self.base_dir = os.path.normpath(base_dir)
29        self.cwd = self.base_dir
30        self.timeout = 0
31        self.cpu_timeout = 0
32        self.depends = frozenset()
33
34    _update = {
35        'cwd': lambda self, cwd: os.path.normpath(os.path.join(self.base_dir, cwd)),
36        'timeout': lambda self, timeout: timeout,
37        'cpu_timeout': lambda self, cpu_timeout: cpu_timeout,
38        'depends': lambda self, depends: self.depends | frozenset(depends)
39    }
40
41    __slots__ = 'base_dir', 'cwd', 'timeout', 'cpu_timeout', 'depends'
42
43    def update(self, updates):
44        new_env = TestEnv.__new__(TestEnv)
45        new_env.base_dir = self.base_dir
46        for name, upd in TestEnv._update.items():
47            new = upd(self, updates[name]) if name in updates else getattr(self, name)
48            setattr(new_env, name, new)
49        return new_env
50
51def parse_attributes(tag, env):
52    """Parse attributes such as "timeout" in the given XML tag,
53    returning an updated env to reflect them."""
54
55    updates = {}
56
57    def parse_attr(name, xml_name, cast):
58        value = tag.get(xml_name)
59        if value is not None: updates[name] = cast(value)
60
61    parse_attr("cwd", "cwd", str)
62    parse_attr("timeout", "timeout", int)
63    parse_attr("cpu_timeout", "cpu-timeout", float)
64    parse_attr("depends", "depends", lambda s: s.split())
65
66    return env.update(updates) if updates else env
67
68class Test(object):
69
70    __slots__ = (
71        'name', 'command', 'cwd', 'timeout', 'cpu_timeout',
72        'depends', 'depends_trans', 'depends_rtrans',
73        'reverse', 'reverse_trans', 'reverse_rtrans'
74    )
75
76    def __init__(self, name, command, env):
77        self.name = name
78        self.command = command
79        self.cwd = env.cwd
80        self.timeout = env.timeout
81        self.cpu_timeout = env.cpu_timeout
82        self.depends = env.depends
83
84def parse_test(doc, env):
85    test = Test(doc.get("name"), doc.text.strip(), env)
86    return [test]
87
88def tests_names(tests):
89    return [t.name for t in tests]
90
91def parse_sequence(doc, env):
92    tests = []
93
94    for child in doc:
95        new_tests = parse_tag(child, env)
96        tests += new_tests
97        env = env.update({"depends": tests_names(new_tests)})
98
99    return tests
100
101def parse_set(doc, env):
102    tests = []
103
104    for child in doc:
105        tests += parse_tag(child, env)
106
107    return tests
108
109parsers = {
110    'testsuite': parse_set,
111    'set': parse_set,
112    'sequence': parse_sequence,
113    'test': parse_test
114}
115
116def parse_tag(doc, env):
117    try:
118        parser = parsers[doc.tag]
119    except KeyError:
120        raise TestSpecParseException("Unknown tag '%s'" % doc.tag)
121    return parser(doc, parse_attributes(doc, env))
122
123def validate_xml(doc, filename):
124    """Ensure the XML matches the regression DTD."""
125
126    # Read in the DTD
127    with open(REGRESSION_DTD) as dtd_file:
128        dtd = etree.DTD(dtd_file)
129
130    # Parse the file, and validate against the DTD.
131    if not dtd.validate(doc):
132        raise Exception(
133                "%s does not validate against DTD:\n\n" % filename
134                + str(dtd.error_log))
135
136def parse_testsuite_xml(filename):
137    # Parse the file.
138    parser = etree.XMLParser(remove_comments=True, recover=False)
139    doc = etree.parse(filename, parser=parser)
140
141    # Validate the XML.
142    validate_xml(doc, filename)
143
144    # Setup an empty environment
145    env = TestEnv(os.path.dirname(filename))
146
147    # Parse this tag as a set of tests.
148    # Returns a list of all tests found in this file.
149    return parse_tag(doc.getroot(), env)
150
151def parse_test_files(xml_files):
152    tests = []
153    for x in xml_files:
154        try:
155            tests += parse_testsuite_xml(x)
156        except:
157            sys.stderr.write("Exception while parsing file: %s.\n" % x)
158            raise
159    return tests
160
161def show_names(names):
162    return ' '.join(sorted(names))
163
164def check_tests(tests):
165    # Check that test names are unique.
166    names, dups = set(), set()
167    for n in tests_names(tests):
168        if n in names: dups.add(n)
169        else: names.add(n)
170    if dups:
171        raise TestSpecParseException(
172            "Duplicate test names: %s" % show_names(dups))
173
174    # Check that dependencies exist.
175    bad_depends = {dep for t in tests for dep in t.depends} - names
176    if bad_depends:
177        raise TestSpecParseException(
178            "Invalid dependencies: %s" % show_names(bad_depends))
179
180def step_rel(rel):
181    # From a one-step relation represented as a dictionary,
182    # generate the corresponding one-or-two-step relation.
183    return dict((s, rel[s].union(*(rel[t] for t in rel[s]))) for s in rel)
184
185def trans_depends(rel):
186    # Repeatedly add dependencies of dependencies until convergence.
187    rel_t = step_rel(rel)
188    while rel_t != rel:
189        rel, rel_t = rel_t, step_rel(rel_t)
190    return rel_t
191
192def refl_depends(rel):
193    rel_r = {}
194    for t in rel: rel_r[t] = rel[t] | {t}
195    return rel_r
196
197class Depends(object):
198    __slots__ = 'step', 'trans', 'rtrans'
199    def __init__(self, step):
200        trans = trans_depends(step)
201        rtrans = refl_depends(trans)
202
203        # Provide access to dictionary contents,
204        # without exposing dictionaries to mutation.
205        def lookup(rel):
206            # Allow the user to customise handling of missing keys,
207            # but by default, raise the appropriate KeyError.
208            def result(x, fail=lambda x: rel[x]):
209                if x in rel: return rel[x]
210                else: return fail(x)
211            return result
212
213        self.step = lookup(step)
214        self.trans = lookup(trans)
215        self.rtrans = lookup(rtrans)
216
217def collect_dependencies(tests):
218    forward, reverse = {}, {}
219    for t in tests:
220        forward[t.name] = frozenset(t.depends)
221        reverse[t.name] = frozenset(r.name for r in tests if t.name in r.depends)
222    return Depends(forward), Depends(reverse)
223
224def toposort(keys, forward_depends, reverse_depends):
225    """Topological sort.
226
227    Perform a toposort of keys, retaining the existing ordering as closely
228    as possible, without breaking dependencies.
229    """
230
231    # Count number of forward dependencies.
232    fwd_deps = dict((k, len(forward_depends(k))) for k in keys)
233
234    # Enumerate keys so we can retain ordering as much as possible.
235    enum_of_key = dict((k, i) for (i, k) in enumerate(keys))
236
237    if len(enum_of_key) != len(keys):
238        raise Exception("toposort: non-unique keys")
239
240    #
241    # Generate heap of tests without a parent, and keep popping off
242    # the heap and processing the tests.
243    #
244    result = []
245    candidates = [(p, k) for (p, k) in enumerate(keys) if fwd_deps[k] == 0]
246
247    while len(candidates) > 0:
248        (p, k) = heapq.heappop(candidates)
249        result.append(k)
250        for j in reverse_depends(k):
251            fwd_deps[j] -= 1
252            if fwd_deps[j] == 0:
253                heapq.heappush(candidates, (enum_of_key[j], j))
254
255    if len(result) != len(keys) or set(result) != set(keys):
256        raise Exception("toposort: panic")
257
258    return result
259
260class TestInfo(object):
261    __slots__ = 'tests', 'tests_by_name', 'forward_deps', 'reverse_deps'
262    def __init__(self, tests, tests_by_name, forward_deps, reverse_deps):
263        self.tests = tests
264        self.tests_by_name = tests_by_name
265        self.forward_deps = forward_deps
266        self.reverse_deps = reverse_deps
267
268def process_tests(tests):
269    """Given a list of tests (possibly from multiple XML file), check for
270    errors and return a list of tests in dependency-satisfying order."""
271
272    # Check test names are unique and dependencies exist.
273    check_tests(tests)
274
275    # Collect dependencies.
276    forward_deps, reverse_deps = collect_dependencies(tests)
277
278    # Annotate tests with richer dependencies.
279    for t in tests:
280        t.reverse = reverse_deps.step(t.name)
281        t.depends_trans = forward_deps.trans(t.name)
282        t.reverse_trans = reverse_deps.trans(t.name)
283        t.depends_rtrans = forward_deps.rtrans(t.name)
284        t.reverse_rtrans = reverse_deps.rtrans(t.name)
285
286    tests_by_name = dict((t.name, t) for t in tests)
287
288    # Check for cyclic dependencies.
289    cyclic = [t.name for t in tests if t.name in t.depends_trans]
290    if cyclic:
291        raise TestSpecParseException("Tests with cyclic dependencies: %s" % show_names(cyclic))
292
293    # Sort tests in dependency order.
294    ordered_names = toposort(tests_names(tests), forward_deps.step, reverse_deps.step)
295    tests = [tests_by_name[t] for t in ordered_names]
296
297    return TestInfo(tests, tests_by_name, forward_deps, reverse_deps)
298
299def process_test_files(xml_files):
300    return process_tests(parse_test_files(xml_files))
301
302def main():
303    # Parse arguments
304    parser = argparse.ArgumentParser(description="Regression Framework Testspec Parser")
305    parser.add_argument("file", metavar="FILE", type=str, nargs="*",
306            help="a regression XML file to parse")
307    args = parser.parse_args()
308
309    # Ensure we have at least one file.
310    if len(args.file) == 0:
311        parser.error("Please provide at least one XML file.")
312
313    # Fetch XML tests.
314    test_info = process_test_files(args.file)
315
316    # Print results
317    for test in test_info.tests:
318        print("\"%s\" [timeout=%d, cpu-timeout=%g, parents=%s, cwd=%s]" % (
319            test.command, test.timeout, test.cpu_timeout, ",".join(test.depends), test.cwd))
320
321if __name__ == "__main__":
322    main()
323