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