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 ##########################################################################/
41 def match(self, value, mo):
42 raise NotImplementedError
44 def _matchSequence(self, refValues, srcValues, mo):
45 if not isinstance(srcValues, (list, tuple)):
48 if len(refValues) != len(srcValues):
51 for refValue, srcValue in zip(refValues, srcValues):
52 if not refValue.match(srcValue, mo):
57 raise NotImplementerError
63 class WildcardMatcher(Matcher):
65 def __init__(self, name = ''):
68 def match(self, value, mo):
71 refValue = mo.params[self.name]
73 mo.params[self.name] = value
75 return refValue == value
79 return '<' + self.name + '>'
82 class LiteralMatcher(Matcher):
84 def __init__(self, refValue):
85 self.refValue = refValue
87 def match(self, value, mo):
88 return self.refValue == value
91 return repr(self.refValue)
94 class ApproxMatcher(Matcher):
96 def __init__(self, refValue, tolerance = 2**-23):
97 self.refValue = refValue
98 self.tolerance = tolerance
100 def match(self, value, mo):
101 if not isinstance(value, float):
104 error = abs(self.refValue - value)
106 error = error / self.refValue
107 return error <= self.tolerance
110 return repr(self.refValue)
113 class BitmaskMatcher(Matcher):
115 def __init__(self, refElements):
116 self.refElements = refElements
118 def match(self, value, mo):
119 return self._matchSequence(self.refElements, value, mo)
122 return ' | '.join(map(str, self.refElements))
125 class ArrayMatcher(Matcher):
127 def __init__(self, refElements):
128 self.refElements = refElements
130 def match(self, value, mo):
131 return self._matchSequence(self.refElements, value, mo)
134 return '{' + ', '.join(map(str, self.refElements)) + '}'
137 class StructMatcher(Matcher):
139 def __init__(self, refMembers):
140 self.refMembers = refMembers
142 def match(self, value, mo):
143 if not isinstance(value, dict):
146 if len(value) != len(self.refMembers):
149 for name, refMember in self.refMembers.iteritems():
155 if not refMember.match(member, mo):
161 return '{' + ', '.join(['%s = %s' % refMember for refMember in self.refMembers.iteritems()]) + '}'
164 class CallMatcher(Matcher):
166 def __init__(self, callNo, functionName, args, ret):
168 self.functionName = functionName
172 def match(self, call, mo):
173 callNo, srcFunctionName, srcArgs, srcRet = call
175 if self.functionName != srcFunctionName:
178 refArgs = [value for name, value in self.args]
179 srcArgs = [value for name, value in srcArgs]
181 if not self._matchSequence(refArgs, srcArgs, mo):
185 if srcRet is not None:
188 if not self.ret.match(srcRet, mo):
191 if self.callNo is not None:
192 if not self.callNo.match(callNo, mo):
198 s = self.functionName
199 s += '(' + ', '.join(['%s = %s' % refArg for refArg in self.args]) + ')'
200 if self.ret is not None:
201 s += ' = ' + str(self.ret)
205 class TraceMismatch(Exception):
212 def __init__(self, calls):
215 def match(self, trace):
217 srcCalls = iter(trace.calls)
218 for refCall in self.calls:
222 srcCall = srcCalls.next()
223 except StopIteration:
225 raise TraceMismatch('missing call `%s` (found `%s`)' % (refCall, skippedSrcCalls[0]))
227 raise TraceMismatch('missing call %s' % refCall)
228 if refCall.match(srcCall, mo):
231 skippedSrcCalls.append(srcCall)
235 return ''.join(['%s\n' % call for call in self.calls])
238 #######################################################################
244 class ParseError(Exception):
246 def __init__(self, msg=None, filename=None, line=None, col=None):
248 self.filename = filename
253 return ':'.join([str(part) for part in (self.filename, self.line, self.col, self.msg) if part != None])
257 """Stateless scanner."""
259 # should be overriden by derived classes
268 flags |= re.IGNORECASE
269 self.tokens_re = re.compile(
270 '|'.join(['(' + regexp + ')' for type, regexp, test_lit in self.tokens]),
274 def next(self, buf, pos):
277 mo = self.tokens_re.match(buf, pos)
280 type, regexp, test_lit = self.tokens[mo.lastindex - 1]
283 type = self.literals.get(text, type)
284 return type, text, pos
287 return self.symbols.get(c, None), c, pos + 1
292 def __init__(self, type, text, line, col):
301 # should be overriden by derived classes
305 newline_re = re.compile(r'\r\n?|\n')
307 def __init__(self, buf = None, pos = 0, filename = None, fp = None):
311 length = os.path.getsize(fp.name)
314 # read whole file into memory
318 # map the whole file into memory
320 # length must not be zero
321 buf = mmap.mmap(fileno, length, access = mmap.ACCESS_READ)
322 pos = os.lseek(fileno, 0, 1)
330 except AttributeError:
337 self.filename = filename
346 type, text, endpos = self.scanner.next(self.buf, pos)
347 assert pos + len(text) == endpos
349 type, text = self.filter(type, text)
355 msg = 'unexpected char '
356 if text >= ' ' and text <= '~':
359 msg += "0x%X" % ord(text)
360 raise ParseError(msg, self.filename, line, col)
363 return Token(type = type, text = text, line = line, col = col)
365 def consume(self, text):
368 for mo in self.newline_re.finditer(text, pos):
373 # update column number
375 tabpos = text.find('\t', pos)
378 self.col += tabpos - pos
379 self.col = ((self.col - 1)//self.tabsize + 1)*self.tabsize + 1
381 self.col += len(text) - pos
386 def __init__(self, lexer):
388 self.lookahead = self.lexer.next()
390 def match(self, type):
391 return self.lookahead.type == type
393 def skip(self, type):
394 while not self.match(type):
399 msg = 'unexpected token %r' % self.lookahead.text,
400 filename = self.lexer.filename,
401 line = self.lookahead.line,
402 col = self.lookahead.col)
404 def consume(self, type = None):
405 if type is not None and not self.match(type):
407 token = self.lookahead
408 self.lookahead = self.lexer.next()
412 #######################################################################
414 ID, NUMBER, HEXNUM, STRING, WILDCARD, PRAGMA, LPAREN, RPAREN, LCURLY, RCURLY, COMMA, AMP, EQUAL, VERT, BLOB = xrange(15)
417 class CallScanner(Scanner):
419 # token regular expression table
422 (SKIP, r'[ \t\f\r\n\v]+', False),
425 (ID, r'[a-zA-Z_][a-zA-Z0-9_]*(?:::[a-zA-Z_][a-zA-Z0-9_]*)?', True),
428 (HEXNUM, r'-?0x[0-9a-fA-F]+', False),
431 (NUMBER, r'-?(?:\.[0-9]+|[0-9]+(?:\.[0-9]*)?)(?:[eE][-+][0-9]+)?', False),
434 (STRING, r'"[^"\\]*(?:\\.[^"\\]*)*"', False),
437 (WILDCARD, r'<[^>]*>', False),
440 (PRAGMA, r'#[^\r\n]*', False),
461 class CallLexer(Lexer):
463 scanner = CallScanner()
465 def filter(self, type, text):
470 text = text.replace('\\\r\n', '')
471 text = text.replace('\\\r', '')
472 text = text.replace('\\\n', '')
475 text = text.replace('\\"', '"')
482 class TraceParser(Parser):
484 def __init__(self, stream):
485 lexer = CallLexer(fp = stream)
486 Parser.__init__(self, lexer)
489 return self.match(EOF)
492 while not self.eof():
494 return TraceMatcher(self.calls)
496 def parse_element(self):
497 if self.lookahead.type == PRAGMA:
498 token = self.consume()
499 self.handlePragma(token.text)
503 def parse_call(self):
504 if self.lookahead.type == NUMBER:
505 token = self.consume()
506 callNo = self.handleInt(int(token.text))
507 elif self.lookahead.type == WILDCARD:
508 token = self.consume()
509 callNo = self.handleWildcard((token.text[1:-1]))
513 functionName = self.consume(ID).text
515 args = self.parse_sequence(LPAREN, RPAREN, self.parse_pair)
517 if self.match(EQUAL):
519 ret = self.parse_value()
523 self.handleCall(callNo, functionName, args, ret)
525 def parse_pair(self):
526 '''Parse a `name = value` pair.'''
527 name = self.consume(ID).text
529 value = self.parse_value()
532 def parse_opt_pair(self):
533 '''Parse an optional `name = value` pair.'''
535 name = self.consume(ID).text
536 if self.match(EQUAL):
538 value = self.parse_value()
544 value = self.parse_value()
550 def parse_value(self):
551 value = self._parse_value()
554 while self.match(VERT):
556 value = self._parse_value()
558 return self.handleBitmask(flags)
562 def _parse_value(self):
565 value = [self.parse_value()]
566 return self.handleArray(value)
568 token = self.consume()
570 return self.handleID(value)
571 elif self.match(STRING):
572 token = self.consume()
574 return self.handleString(value)
575 elif self.match(NUMBER):
576 token = self.consume()
577 value = float(token.text)
578 return self.handleFloat(value)
579 elif self.match(HEXNUM):
580 token = self.consume()
581 value = int(token.text, 16)
582 return self.handleInt(value)
583 elif self.match(LCURLY):
584 value = self.parse_sequence(LCURLY, RCURLY, self.parse_opt_pair)
585 if len(value) and isinstance(value[0], tuple):
587 return self.handleStruct(value)
589 return self.handleArray(value)
590 elif self.match(BLOB):
591 token = self.consume()
593 token = self.consume()
594 length = int(token.text)
596 return self.handleBlob(length)
597 elif self.match(WILDCARD):
598 token = self.consume()
599 return self.handleWildcard(token.text[1:-1])
603 def parse_sequence(self, ltype, rtype, elementParser):
604 '''Parse a comma separated list'''
610 while not self.match(rtype):
615 element = elementParser()
616 elements.append(element)
621 def handleID(self, value):
622 raise NotImplementedError
624 def handleInt(self, value):
625 raise NotImplementedError
627 def handleFloat(self, value):
628 raise NotImplementedError
630 def handleString(self, value):
631 raise NotImplementedError
633 def handleBitmask(self, value):
634 raise NotImplementedError
636 def handleArray(self, value):
637 raise NotImplementedError
639 def handleStruct(self, value):
640 raise NotImplementedError
642 def handleBlob(self, length):
643 return self.handleID('blob(%u)' % length)
645 def handleWildcard(self, name):
646 raise NotImplementedError
648 def handleCall(self, callNo, functionName, args, ret):
649 raise NotImplementedError
651 def handlePragma(self, line):
652 raise NotImplementedError
655 class RefTraceParser(TraceParser):
657 def __init__(self, stream):
658 TraceParser.__init__(self, stream)
662 TraceParser.parse(self)
663 return TraceMatcher(self.calls)
665 def handleID(self, value):
666 return LiteralMatcher(value)
668 def handleInt(self, value):
669 return LiteralMatcher(value)
671 def handleFloat(self, value):
672 return ApproxMatcher(value)
674 def handleString(self, value):
675 return LiteralMatcher(value)
677 def handleBitmask(self, value):
678 return BitmaskMatcher(value)
680 def handleArray(self, value):
681 return ArrayMatcher(value)
683 def handleStruct(self, value):
684 return StructMatcher(value)
686 def handleWildcard(self, name):
687 return WildcardMatcher(name)
689 def handleCall(self, callNo, functionName, args, ret):
690 call = CallMatcher(callNo, functionName, args, ret)
691 self.calls.append(call)
693 def handlePragma(self, line):
697 class SrcTraceParser(TraceParser):
699 def __init__(self, stream):
700 TraceParser.__init__(self, stream)
704 TraceParser.parse(self)
705 return TraceMatcher(self.calls)
707 def handleID(self, value):
710 def handleInt(self, value):
713 def handleFloat(self, value):
716 def handleString(self, value):
719 def handleBitmask(self, value):
722 def handleArray(self, elements):
723 return list(elements)
725 def handleStruct(self, members):
728 def handleCall(self, callNo, functionName, args, ret):
729 call = (callNo, functionName, args, ret)
730 self.calls.append(call)
734 # Parse command line options
735 optparser = optparse.OptionParser(
736 usage='\n\t%prog [OPTIONS] REF_TRACE SRC_TRACE',
738 optparser.add_option(
741 dest="verbose", default=False,
742 help="verbose output")
743 (options, args) = optparser.parse_args(sys.argv[1:])
746 optparser.error('wrong number of arguments')
748 refParser = RefTraceParser(open(args[0], 'rt'))
749 refTrace = refParser.parse()
750 sys.stdout.write(str(refTrace))
751 srcParser = SrcTraceParser(open(args[1], 'rt'))
752 srcTrace = srcParser.parse()
753 mo = refTrace.match(srcTrace)
755 paramNames = mo.params.keys()
757 for paramName in paramNames:
758 print '%s = %r' % (paramName, mo.params[paramName])
761 if __name__ == '__main__':