2 ##########################################################################
4 # Copyright 2008-2012 Jose Fonseca
7 # Permission is hereby granted, free of charge, to any person obtaining a copy
8 # of this software and associated documentation files (the "Software"), to deal
9 # in the Software without restriction, including without limitation the rights
10 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 # copies of the Software, and to permit persons to whom the Software is
12 # furnished to do so, subject to the following conditions:
14 # The above copyright notice and this permission notice shall be included in
15 # all copies or substantial portions of the Software.
17 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 ##########################################################################/
35 def match(self, value):
36 raise NotImplementedError
38 def _matchSequence(self, refValues, srcValues):
39 if not isinstance(srcValues, (list, tuple)):
42 if len(refValues) != len(srcValues):
45 for refValue, srcValue in zip(refValues, srcValues):
46 if not refValue.match(srcValue):
51 raise NotImplementerError
57 class WildcardMatcher(Matcher):
59 def match(self, value):
66 class LiteralMatcher(Matcher):
68 def __init__(self, refValue):
69 self.refValue = refValue
71 def match(self, value):
72 return self.refValue == value
75 return repr(self.refValue)
78 class ApproxMatcher(Matcher):
80 def __init__(self, refValue, tolerance = 2**-23):
81 self.refValue = refValue
82 self.tolerance = tolerance
84 def match(self, value):
85 if not isinstance(value, float):
88 error = abs(self.refValue - value)
90 error = error / self.refValue
91 return error <= self.tolerance
94 return repr(self.refValue)
97 class BitmaskMatcher(Matcher):
99 def __init__(self, refElements):
100 self.refElements = refElements
102 def match(self, value):
103 return self._matchSequence(self.refElements, value)
106 return ' | '.join(map(str, self.refElements))
109 class ArrayMatcher(Matcher):
111 def __init__(self, refElements):
112 self.refElements = refElements
114 def match(self, value):
115 return self._matchSequence(self.refElements, value)
118 return '{' + ', '.join(map(str, self.refElements)) + '}'
121 class StructMatcher(Matcher):
123 def __init__(self, refMembers):
124 self.refMembers = refMembers
126 def match(self, value):
127 if not isinstance(value, dict):
130 if len(value) != len(self.refMembers):
133 for name, refMember in self.refMembers.iteritems():
139 if not refMember.match(member):
145 print self.refMembers
146 return '{' + ', '.join(['%s = %s' % refMember for refMember in self.refMembers.iteritems()]) + '}'
149 class CallMatcher(Matcher):
151 def __init__(self, functionName, args, ret = None):
152 self.functionName = functionName
156 def match(self, call):
157 srcFunctionName, srcArgs, srcRet = call
159 if self.functionName != srcFunctionName:
162 refArgs = [value for name, value in self.args]
163 srcArgs = [value for name, value in srcArgs]
165 if not self._matchSequence(refArgs, srcArgs):
169 if srcRet is not None:
172 if not self.ret.match(srcRet):
178 s = self.functionName
179 s += '(' + ', '.join(['%s = %s' % refArg for refArg in self.args]) + ')'
180 if self.ret is not None:
181 s += ' = ' + str(self.ret)
187 def __init__(self, calls):
190 def match(self, trace):
192 srcCalls = iter(trace.calls)
193 for refCall in self.calls:
197 srcCall = srcCalls.next()
198 except StopIteration:
200 raise Exception('missing call `%s` (found `%s`)' % (refCall, skippedSrcCalls[0]))
202 raise Exception('missing call %s' % refCall)
203 if refCall.match(srcCall):
206 skippedSrcCalls.append(srcCall)
210 return ''.join(['%s\n' % call for call in self.calls])
213 #######################################################################
219 class ParseError(Exception):
221 def __init__(self, msg=None, filename=None, line=None, col=None):
223 self.filename = filename
228 return ':'.join([str(part) for part in (self.filename, self.line, self.col, self.msg) if part != None])
232 """Stateless scanner."""
234 # should be overriden by derived classes
243 flags |= re.IGNORECASE
244 self.tokens_re = re.compile(
245 '|'.join(['(' + regexp + ')' for type, regexp, test_lit in self.tokens]),
249 def next(self, buf, pos):
252 mo = self.tokens_re.match(buf, pos)
255 type, regexp, test_lit = self.tokens[mo.lastindex - 1]
258 type = self.literals.get(text, type)
259 return type, text, pos
262 return self.symbols.get(c, None), c, pos + 1
267 def __init__(self, type, text, line, col):
276 # should be overriden by derived classes
280 newline_re = re.compile(r'\r\n?|\n')
282 def __init__(self, buf = None, pos = 0, filename = None, fp = None):
286 length = os.path.getsize(fp.name)
289 # read whole file into memory
293 # map the whole file into memory
295 # length must not be zero
296 buf = mmap.mmap(fileno, length, access = mmap.ACCESS_READ)
297 pos = os.lseek(fileno, 0, 1)
305 except AttributeError:
312 self.filename = filename
321 type, text, endpos = self.scanner.next(self.buf, pos)
322 assert pos + len(text) == endpos
324 type, text = self.filter(type, text)
330 msg = 'unexpected char '
331 if text >= ' ' and text <= '~':
334 msg += "0x%X" % ord(text)
335 raise ParseError(msg, self.filename, line, col)
338 return Token(type = type, text = text, line = line, col = col)
340 def consume(self, text):
343 for mo in self.newline_re.finditer(text, pos):
348 # update column number
350 tabpos = text.find('\t', pos)
353 self.col += tabpos - pos
354 self.col = ((self.col - 1)//self.tabsize + 1)*self.tabsize + 1
356 self.col += len(text) - pos
361 def __init__(self, lexer):
363 self.lookahead = self.lexer.next()
365 def match(self, type):
366 return self.lookahead.type == type
368 def skip(self, type):
369 while not self.match(type):
374 msg = 'unexpected token %r' % self.lookahead.text,
375 filename = self.lexer.filename,
376 line = self.lookahead.line,
377 col = self.lookahead.col)
379 def consume(self, type = None):
380 if type is not None and not self.match(type):
382 token = self.lookahead
383 self.lookahead = self.lexer.next()
387 #######################################################################
389 ID, NUMBER, HEXNUM, STRING, PRAGMA, LPAREN, RPAREN, LCURLY, RCURLY, COMMA, AMP, EQUAL, VERT, BLOB = xrange(14)
392 class CallScanner(Scanner):
394 # token regular expression table
397 (SKIP, r'[ \t\f\r\n\v]+', False),
400 (ID, r'[a-zA-Z_][a-zA-Z0-9_]*(?:::[a-zA-Z_][a-zA-Z0-9_]*)?', True),
403 (HEXNUM, r'-?0x[0-9a-fA-F]+', False),
406 (NUMBER, r'-?(?:\.[0-9]+|[0-9]+(?:\.[0-9]*)?)(?:[eE][-+][0-9]+)?', False),
409 (STRING, r'"[^"\\]*(?:\\.[^"\\]*)*"', False),
412 (PRAGMA, r'#[^\r\n]*', False),
433 class CallLexer(Lexer):
435 scanner = CallScanner()
437 def filter(self, type, text):
442 text = text.replace('\\\r\n', '')
443 text = text.replace('\\\r', '')
444 text = text.replace('\\\n', '')
447 text = text.replace('\\"', '"')
454 class TraceParser(Parser):
456 def __init__(self, stream):
457 lexer = CallLexer(fp = stream)
458 Parser.__init__(self, lexer)
461 return self.match(EOF)
464 while not self.eof():
466 return TraceMatcher(self.calls)
468 def parse_element(self):
469 if self.lookahead.type == PRAGMA:
471 token = self.consume()
472 self.handlePragma(token.text)
476 def parse_call(self):
477 while self.lookahead.type == PRAGMA:
479 token = self.consume()
482 if self.lookahead.type == NUMBER:
483 token = self.consume()
484 callNo = int(token.text)
488 functionName = self.consume(ID).text
490 args = self.parse_sequence(LPAREN, RPAREN, self.parse_pair)
492 if self.match(EQUAL):
494 ret = self.parse_value()
498 self.handleCall(functionName, args, ret)
500 def parse_pair(self):
501 '''Parse a `name = value` pair.'''
502 name = self.consume(ID).text
504 value = self.parse_value()
507 def parse_opt_pair(self):
508 '''Parse an optional `name = value` pair.'''
510 name = self.consume(ID).text
511 if self.match(EQUAL):
513 value = self.parse_value()
519 value = self.parse_value()
525 def parse_value(self):
526 value = self._parse_value()
529 while self.match(VERT):
531 value = self._parse_value()
533 return self.handleBitmask(flags)
537 def _parse_value(self):
540 value = [self.parse_value()]
541 return self.handleArray(value)
543 token = self.consume()
545 return self.handleID(value)
546 elif self.match(STRING):
547 token = self.consume()
549 return self.handleString(value)
550 elif self.match(NUMBER):
551 token = self.consume()
552 value = float(token.text)
553 return self.handleFloat(value)
554 elif self.match(HEXNUM):
555 token = self.consume()
556 value = int(token.text, 16)
557 return self.handleInt(value)
558 elif self.match(LCURLY):
559 value = self.parse_sequence(LCURLY, RCURLY, self.parse_opt_pair)
560 if len(value) and isinstance(value[0], tuple):
562 return self.handleStruct(value)
564 return self.handleArray(value)
565 elif self.match(BLOB):
566 token = self.consume()
568 length = self.consume()
570 return self.handleBlob(length)
574 def parse_sequence(self, ltype, rtype, elementParser):
575 '''Parse a comma separated list'''
581 while not self.match(rtype):
586 element = elementParser()
587 elements.append(element)
592 def handleID(self, value):
593 raise NotImplementedError
595 def handleInt(self, value):
596 raise NotImplementedError
598 def handleFloat(self, value):
599 raise NotImplementedError
601 def handleString(self, value):
602 raise NotImplementedError
604 def handleBitmask(self, value):
605 raise NotImplementedError
607 def handleArray(self, value):
608 raise NotImplementedError
610 def handleStruct(self, value):
611 raise NotImplementedError
613 def handleBlob(self, length):
614 raise NotImplementedError
616 return WildcardMatcher()
618 def handleCall(self, functionName, args, ret):
619 raise NotImplementedError
621 def handlePragma(self, line):
625 class RefTraceParser(TraceParser):
627 def __init__(self, stream):
628 TraceParser.__init__(self, stream)
632 TraceParser.parse(self)
633 return TraceMatcher(self.calls)
635 def handleID(self, value):
636 return LiteralMatcher(value)
638 def handleInt(self, value):
639 return LiteralMatcher(value)
641 def handleFloat(self, value):
642 return ApproxMatcher(value)
644 def handleString(self, value):
645 return LiteralMatcher(value)
647 def handleBitmask(self, value):
648 return BitmaskMatcher(value)
650 def handleArray(self, value):
651 return ArrayMatcher(value)
653 def handleStruct(self, value):
654 return StructMatcher(value)
656 def handleBlob(self, length):
658 return WildcardMatcher()
660 def handleCall(self, functionName, args, ret):
661 call = CallMatcher(functionName, args, ret)
662 self.calls.append(call)
665 class SrcTraceParser(TraceParser):
667 def __init__(self, stream):
668 TraceParser.__init__(self, stream)
672 TraceParser.parse(self)
673 return TraceMatcher(self.calls)
675 def handleID(self, value):
678 def handleInt(self, value):
681 def handleFloat(self, value):
684 def handleString(self, value):
687 def handleBitmask(self, value):
690 def handleArray(self, elements):
691 return list(elements)
693 def handleStruct(self, members):
696 def handleBlob(self, length):
700 def handleCall(self, functionName, args, ret):
701 call = (functionName, args, ret)
702 self.calls.append(call)
706 # Parse command line options
707 optparser = optparse.OptionParser(
708 usage='\n\t%prog [OPTIONS] REF_TRACE SRC_TRACE',
710 optparser.add_option(
713 dest="verbose", default=False,
714 help="verbose output")
715 (options, args) = optparser.parse_args(sys.argv[1:])
718 optparser.error('wrong number of arguments')
720 refParser = RefTraceParser(open(args[0], 'rt'))
721 refTrace = refParser.parse()
722 sys.stdout.write(str(refTrace))
723 srcParser = SrcTraceParser(open(args[1], 'rt'))
724 srcTrace = srcParser.parse()
725 refTrace.match(srcTrace)
728 if __name__ == '__main__':