mirror of
https://github.com/gaasedelen/lighthouse
synced 2026-06-08 14:19:10 +00:00
gaasedelen
454 lines
13 KiB
Python
454 lines
13 KiB
Python
import re
|
|
import string
|
|
import operator
|
|
|
|
#------------------------------------------------------------------------------
|
|
# Text Tokens
|
|
#------------------------------------------------------------------------------
|
|
|
|
class TextToken(object):
|
|
"""
|
|
A single tokenized text element.
|
|
|
|
TextTokens are effectively wrappers for individual regex matches found
|
|
when tokenizing a text string (eg, a composition string). They provide
|
|
location and type information for the token as it exists in the string.
|
|
|
|
Besides being used to normalize and guide the parsing of a given
|
|
string, TextTokens can be used for things like syntax highlighting.
|
|
"""
|
|
|
|
def __init__(self, match):
|
|
self.type = match.lastgroup
|
|
self.value = (str(match.group())).upper()
|
|
self.span = match.span()
|
|
|
|
@property
|
|
def index(self):
|
|
return self.span[0]
|
|
|
|
#
|
|
# COVERAGE_TOKEN:
|
|
# 'A' | 'B' | 'C' | ... | 'Z'
|
|
#
|
|
|
|
# NOTE: this is now dynamically computed in parse(...)
|
|
#COVERAGE_TOKEN = r'(?P<COVERAGE_TOKEN>[A-Za-z])'
|
|
AGGREGATE_TOKEN = '*'
|
|
|
|
#
|
|
# LOGIC_TOKEN:
|
|
# '|' | '^' | '&' | '-'
|
|
#
|
|
|
|
OR = r'(?P<OR>\|)'
|
|
XOR = r'(?P<XOR>\^)'
|
|
AND = r'(?P<AND>\&)'
|
|
MINUS = r'(?P<MINUS>-)'
|
|
|
|
#
|
|
# Misc Tokens
|
|
#
|
|
|
|
LPAREN = r'(?P<LPAREN>\()'
|
|
RPAREN = r'(?P<RPAREN>\))'
|
|
COMMA = r'(?P<COMMA>\,)'
|
|
WS = r'(?P<WS>\s+)'
|
|
UNKNOWN = r'(?P<UNKNOWN>.)'
|
|
|
|
TOKEN_DEFINITIONS = [OR, XOR, AND, MINUS, LPAREN, RPAREN, COMMA, WS, UNKNOWN]
|
|
|
|
#------------------------------------------------------------------------------
|
|
# AST Tokens
|
|
#------------------------------------------------------------------------------
|
|
|
|
class AstToken(object):
|
|
"""
|
|
Base class for Abstract Syntax Tree (AST) Tokens.
|
|
|
|
The Tokens subclassed from AstToken are used to build an abstract
|
|
syntax tree representing a composition equation.
|
|
|
|
Once generated, an AST can be logically evaluated by Lighthouse's
|
|
director to compose a new coverage set described by the tree.
|
|
"""
|
|
|
|
def __init__(self):
|
|
self.nodes = []
|
|
self.text_tokens = []
|
|
|
|
class TokenNull(AstToken):
|
|
"""
|
|
AST Token indicating a NULL / empty composition.
|
|
"""
|
|
|
|
def __init__(self):
|
|
super(TokenNull, self).__init__()
|
|
|
|
class TokenLogicOperator(AstToken):
|
|
"""
|
|
AST Token for a logical operator.
|
|
|
|
eg: '|'
|
|
"""
|
|
|
|
def __init__(self, logic_op, op1, op2=None):
|
|
super(TokenLogicOperator, self).__init__()
|
|
self.text_tokens = [logic_op]
|
|
|
|
# logic operator
|
|
self.operator = self.str2op(logic_op.value)
|
|
|
|
# referenced operands
|
|
self.op1 = op1
|
|
self.op2 = op2
|
|
|
|
# save the operand expressions as children
|
|
self.nodes = [op1, op2]
|
|
|
|
@staticmethod
|
|
def str2op(op_char):
|
|
if op_char == '|':
|
|
return operator.or_
|
|
if op_char == '&':
|
|
return operator.and_
|
|
if op_char == '^':
|
|
return operator.xor
|
|
if op_char == '-':
|
|
return operator.sub
|
|
raise ValueError("Unknown Operator")
|
|
|
|
class TokenCoverageSingle(AstToken):
|
|
"""
|
|
AST Token for a single coverage reference.
|
|
|
|
eg: 'A'
|
|
"""
|
|
|
|
def __init__(self, coverage_single):
|
|
super(TokenCoverageSingle, self).__init__()
|
|
self.text_tokens = [coverage_single]
|
|
|
|
# referenced coverage set
|
|
self.symbol = coverage_single.value
|
|
|
|
#------------------------------------------------------------------------------
|
|
# AST Operations
|
|
#------------------------------------------------------------------------------
|
|
|
|
def ast_equal(first, second):
|
|
"""
|
|
A fail-safe equality of the structure and contents of two AST.
|
|
|
|
This is not a true (logical) equality check. Two AST's may evaluate to
|
|
the same logical result, but have a slightly different structure which
|
|
will trigger this check to return False.
|
|
|
|
This is primarily used to check if a user specified AST has changed, and
|
|
if we should probably re-evaluate the tree (composition).
|
|
"""
|
|
|
|
# both trees are 'NULL' / empty AST
|
|
if isinstance(first, TokenNull) and isinstance(second, TokenNull):
|
|
return True
|
|
|
|
# recursively evaluate the AST's
|
|
return _ast_equal_recursive(first, second)
|
|
|
|
def _ast_equal_recursive(first, second):
|
|
"""
|
|
The internal (recursive) AST evaluation routine.
|
|
"""
|
|
|
|
#
|
|
# if the left and right types are not identical at every step, the tree
|
|
# is obviously different somehow
|
|
#
|
|
|
|
if type(first) != type(second):
|
|
return False
|
|
|
|
#
|
|
# if both tokens are terminating / None, they are a match
|
|
#
|
|
|
|
if first == second == None:
|
|
return True
|
|
|
|
#
|
|
# if the current node is a logic operator, we need to evaluate the
|
|
# expressions that make up its input.
|
|
#
|
|
|
|
elif isinstance(first, TokenLogicOperator):
|
|
if not _ast_equal_recursive(first.op1, second.op1):
|
|
return False
|
|
if not _ast_equal_recursive(first.op2, second.op2):
|
|
return False
|
|
return first.operator == second.operator
|
|
|
|
#
|
|
# if the current node is a coverage token, we need simply need
|
|
# to compare its symbol.
|
|
#
|
|
|
|
elif isinstance(first, TokenCoverageSingle):
|
|
return first.symbol == second.symbol
|
|
|
|
#
|
|
# unknown token? (this should never happen)
|
|
#
|
|
|
|
raise ValueError("Unknown token types, cannot compare them...")
|
|
|
|
#------------------------------------------------------------------------------
|
|
# Parsing
|
|
#------------------------------------------------------------------------------
|
|
|
|
class ParseError(SyntaxError):
|
|
"""
|
|
Exception raised when composition parsing fails.
|
|
|
|
A ParseError will provide some contextual information to how and why
|
|
the parser failed. Information gleaned through the exception can still
|
|
be consumed for user hints, syntax highlighting, or other uses.
|
|
"""
|
|
|
|
def __init__(self, message, expected, error_token, parsed_tokens):
|
|
super(ParseError, self).__init__(message)
|
|
self.expected = expected
|
|
self.error_token = error_token
|
|
self.parsed_tokens = parsed_tokens
|
|
|
|
if error_token == self.parsed_tokens[-1]:
|
|
fail = self.parsed_tokens.pop()
|
|
self.error_index = fail.span[0]
|
|
else:
|
|
self.error_index = self.parsed_tokens[-1].span[1]
|
|
|
|
def __str__(self):
|
|
return "%s: at %s, %s" % (self.__class__.__name__, self.error_token.span, self.msg)
|
|
|
|
#------------------------------------------------------------------------------
|
|
# Composition Parser
|
|
#------------------------------------------------------------------------------
|
|
|
|
class CompositionParser(object):
|
|
"""
|
|
A simple recursive descent parser for Compositions.
|
|
|
|
Heavily modified from:
|
|
https://rockie-yang.gitbooks.io/python-cookbook/content/ch2/simple_parser.html
|
|
|
|
#----------------------------------------------------------------------
|
|
|
|
Below is the spec for the LL(1) 'Composition Grammar' that was designed
|
|
to generically parse coverage composition equations form raw text.
|
|
|
|
#----------------------------------------------------------------------
|
|
|
|
COMPOSITION:
|
|
EXPRESSION COMPOSITION_TAIL
|
|
|
|
COMPOSITION_TAIL:
|
|
LOGIC_TOKEN COMPOSITION | None
|
|
|
|
EXPRESSION:
|
|
'(' EXPRESSION ')' COMPOSITION_TAIL | COVERAGE COMPOSITION_TAIL
|
|
|
|
COVERAGE_TOKEN:
|
|
'A' | 'B' | 'C' | ... | 'Z' | AGGREGATE_TOKEN
|
|
|
|
LOGIC_TOKEN:
|
|
'&' | '|' | '^' | '-' | None
|
|
|
|
"""
|
|
|
|
def parse(self, text, coverage_tokens):
|
|
"""
|
|
Parse a string using the Composition Grammar.
|
|
|
|
Returns an Abstract Syntax Tree (AST) of the parsed input.
|
|
|
|
Raises ParseError on parse failure.
|
|
"""
|
|
|
|
# if the string is *only* whitespace, return an empty, but valid parse
|
|
if not text.strip():
|
|
return ([], TokenNull())
|
|
|
|
#
|
|
# we used to parse [A-Za-z] as the COVERAGE_TOKEN, but that means we
|
|
# would technically tokenize and construct trees with COVERAGE_TOKEN's
|
|
# that have no matching (eg invalid) loaded coverage data.
|
|
#
|
|
# now we construct the COVERAGE_TOKEN regex just before parsing.
|
|
# this enables us to tokenize/parse only the shorthand names that
|
|
# reflect the state of loaded coverage
|
|
#
|
|
|
|
COVERAGE_TOKEN = r'(?P<COVERAGE_TOKEN>[%s])' % ''.join(coverage_tokens + [AGGREGATE_TOKEN])
|
|
|
|
#
|
|
# if there were any coverage tokens defined, then we definitely need
|
|
# the constructed COVERAGE_TOKEN regex in our grammar list.
|
|
#
|
|
|
|
if coverage_tokens:
|
|
TOKEN_REGEXES = [COVERAGE_TOKEN] + TOKEN_DEFINITIONS
|
|
else:
|
|
TOKEN_REGEXES = TOKEN_DEFINITIONS
|
|
|
|
# build our master tokenizer regex pattern to parse the text stream
|
|
master_pattern = re.compile('|'.join(TOKEN_REGEXES))
|
|
|
|
# reset the parser's runtime variables
|
|
self._parsed_tokens = []
|
|
self.current_token = None
|
|
self.next_token = None
|
|
|
|
# tokenize the raw text stream
|
|
self.tokens = self._generate_tokens(master_pattern, text)
|
|
|
|
# initialize the parser state by bumping the parser onto the first token
|
|
self._advance()
|
|
|
|
# parse the token stream using the grammar defined by this class
|
|
ast = self._COMPOSITION()
|
|
|
|
# if there are any tokens remaining in the stream, the text is invalid
|
|
if self.next_token:
|
|
self._parse_error("Expected $$", TokenNull)
|
|
|
|
# return the parsed tokens and generated AST
|
|
return (self._parsed_tokens, ast)
|
|
|
|
#--------------------------------------------------------------------------
|
|
# Token Stream Operations
|
|
#--------------------------------------------------------------------------
|
|
|
|
def _advance(self):
|
|
"""
|
|
Advance one token in the token stream.
|
|
"""
|
|
self.current_token, self.next_token = self.next_token, next(self.tokens, None)
|
|
|
|
def _accept(self, token_type):
|
|
"""
|
|
Match and accept the lookahead token.
|
|
"""
|
|
if self.next_token and self.next_token.type == token_type:
|
|
self._advance()
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def _generate_tokens(self, regex_pattern, text):
|
|
"""
|
|
Generate a TextToken stream using a given regex token pattern and text.
|
|
"""
|
|
scanner = regex_pattern.scanner(text)
|
|
for m in iter(scanner.match, None):
|
|
token = TextToken(m)
|
|
self._parsed_tokens.append(token)
|
|
if token.type != 'WS': # ignore whitespace tokens
|
|
yield token
|
|
|
|
def _parse_error(self, message, expected):
|
|
"""
|
|
Raises a ParseError, capturing elements of the parser state.
|
|
"""
|
|
raise ParseError(message, expected, self.next_token, self._parsed_tokens)
|
|
|
|
#--------------------------------------------------------------------------
|
|
# Grammar Rules
|
|
#--------------------------------------------------------------------------
|
|
|
|
def _COMPOSITION(self):
|
|
"""
|
|
COMPOSITION:
|
|
EXPRESSION COMPOSITION_TAIL
|
|
"""
|
|
expression = self._EXPRESSION()
|
|
return self._COMPOSITION_TAIL(expression)
|
|
|
|
def _COMPOSITION_TAIL(self, head):
|
|
"""
|
|
COMPOSITION_TAIL:
|
|
LOGIC_TOKEN COMPOSITION | None
|
|
"""
|
|
|
|
#
|
|
# LOGIC_TOKEN COMPOSITION
|
|
#
|
|
|
|
logic_op = self._LOGIC_TOKEN()
|
|
if logic_op:
|
|
composition = self._COMPOSITION()
|
|
return TokenLogicOperator(logic_op, head, composition)
|
|
|
|
#
|
|
# None
|
|
#
|
|
|
|
# no COMPOSITION_TAIL to parse, simply return the leading expression
|
|
return head
|
|
|
|
def _EXPRESSION(self):
|
|
"""
|
|
EXPRESSION:
|
|
'(' EXPRESSION ')' COMPOSITION_TAIL | COVERAGE_TOKEN COMPOSITION_TAIL
|
|
"""
|
|
|
|
#
|
|
# ['(' EXPRESSION ')'] COMPOSITION_TAIL
|
|
#
|
|
|
|
if self._accept('LPAREN'):
|
|
|
|
# parse left paren
|
|
left_paren = self.current_token
|
|
|
|
# parse the expression
|
|
expression = self._EXPRESSION() # THESE ARE CHILDREN
|
|
|
|
# parse the right paren
|
|
if not self._accept('RPAREN'):
|
|
self._parse_error("Expected RPAREN", TextToken)
|
|
right_paren = self.current_token
|
|
|
|
# inject parenthesis TextTokens into the expression
|
|
expression.text_tokens.append(left_paren)
|
|
expression.text_tokens.append(right_paren)
|
|
|
|
#
|
|
# [COVERAGE] COMPOSITION_TAIL
|
|
#
|
|
|
|
else:
|
|
expression = self._COVERAGE_TOKEN()
|
|
|
|
# ... [COMPOSITION_TAIL]
|
|
return self._COMPOSITION_TAIL(expression)
|
|
|
|
def _COVERAGE_TOKEN(self):
|
|
"""
|
|
COVERAGE_TOKEN:
|
|
'A' | 'B' | 'C' | ... | 'Z' | AGGREGATE_TOKEN
|
|
"""
|
|
if self._accept("COVERAGE_TOKEN"):
|
|
return TokenCoverageSingle(self.current_token)
|
|
self._parse_error("Expected COVERAGE_TOKEN", TokenCoverageSingle)
|
|
|
|
def _LOGIC_TOKEN(self):
|
|
"""
|
|
LOGIC_TOKEN:
|
|
'&' | '|' | '^' | '-' | None
|
|
"""
|
|
if self._accept("OR") or \
|
|
self._accept("XOR") or \
|
|
self._accept("AND") or \
|
|
self._accept("MINUS"):
|
|
return self.current_token
|
|
return None
|