#!/usr/bin/env python3
# SPDX-License-Identifier: GPL-2.0-only
#
# Copyright (C) 2019-2022 Red Hat, Inc. Daniel Bristot de Oliveira <bristot@kernel.org>
#
# Automata class: parse an automaton in dot file digraph format into a python object
#
# For further information, see:
# Documentation/trace/rv/deterministic_automata.rst
import ntpath
import lark
class ParseTree:
# based on https://graphviz.org/doc/info/lang.html
# with the irrelevant stuffs (port and compass) removed
grammar = r'''
start: "strict"? ("graph" | "digraph") ID? "{" stmt_list "}"
stmt_list: (stmt ";"? stmt_list)?
stmt: node_stmt
| edge_stmt
| attr_stmt
| ID "=" ID
| subgraph
attr_stmt: attr_type attr_list
attr_type: "graph" -> graph
| "node" -> node
| "edge" -> edge
attr_list: "[" a_list? "]" attr_list?
a_list: ID "=" ID (";" | ",")? a_list?
edge_stmt: (node_id | subgraph) edgerhs attr_list?
edgerhs: edgeop (node_id | subgraph) edgerhs?
edgeop: "->" | "--"
node_stmt: node_id attr_list?
node_id: ID
subgraph: ("subgraph" ID?)? "{" stmt_list "}"
ID: CNAME
| /-?(\.[0-9]+|[0-9]+(\.[0-9]*))/
| ESCAPED_STRING
%import common.CNAME
%import common.ESCAPED_STRING
%import common.WS
%ignore WS
'''
@staticmethod
def parse_edge(tree: lark.Tree) -> tuple[str, str]:
# only support a simple node-to-node edge
nodes = []
for node in tree.iter_subtrees_topdown():
if node.data == "node_id":
nodes.append(node.children[0].strip('"'))
if len(nodes) != 2:
raise AutomataError("Only state-to-state transition is supported")
return tuple(nodes)
class ParseNodes(lark.visitors.Visitor):
def __init__(self, *args, **kwargs):
self.nodes = set()
super().__init__(*args, **kwargs)
def node_stmt(self, tree):
node_id = tree.children[0]
node = node_id.children[0].strip('"')
self.nodes.add(node)
class ParseEdges(lark.visitors.Visitor):
def __init__(self, *args, **kwargs):
self.edges = set()
super().__init__(*args, **kwargs)
def edge_stmt(self, tree):
edge = ParseTree.parse_edge(tree)
self.edges.add(edge)
class ParseAttributes(lark.visitors.Interpreter):
def __init__(self, *args, **kwargs):
'''
Stacks of default attributes. [0] is the default
attributes for the outermost scope, while [-1] is the
default attributes for the current scope.
'''
self.default_node_attrs = [{}]
self.default_edge_attrs = [{}]
self.node_attrs = {}
self.edge_attrs = {}
super().__init__(*args, **kwargs)
@staticmethod
def __get_attrs(stmt: lark.Tree) -> dict[str, str]:
attrs = {}
for node in stmt.iter_subtrees():
if node.data == "a_list":
attrs[node.children[0]] = node.children[1].strip('"')
return attrs
def subgraph(self, tree):
# We are entering a new scope, inherit the default
# attributes of the outer scope
self.default_node_attrs.append(self.default_node_attrs[-1].copy())
self.default_edge_attrs.append(self.default_edge_attrs[-1].copy())
children = self.visit_children(tree)
# Exiting the scope
del self.default_node_attrs[-1]
del self.default_edge_attrs[-1]
return children
def node_stmt(self, tree):
node_id = tree.children[0]
node = node_id.children[0].strip('"')
attrs = self.default_node_attrs[-1].copy()
attrs |= self.__get_attrs(tree)
if attrs:
if node in self.node_attrs:
self.node_attrs[node] = attrs | self.node_attrs[node]
else:
self.node_attrs[node] = attrs
return self.visit_children(tree)
def edge_stmt(self, tree):
edge = ParseTree.parse_edge(tree)
attrs = self.default_edge_attrs[-1].copy()
attrs |= self.__get_attrs(tree)
if attrs:
if edge in self.edge_attrs:
self.edge_attrs[edge] = attrs | self.edge_attrs[edge]
else:
self.edge_attrs[edge] = attrs
return self.visit_children(tree)
def attr_stmt(self, tree):
attr_type = tree.children[0].data
attrs = self.__get_attrs(tree)
if attr_type == "node":
self.default_node_attrs[-1] |= attrs
elif attr_type == "edge":
self.default_edge_attrs[-1] |= attrs
else:
# graph attributes are irrelevant
pass
self.visit_children(tree)
def __init__(self, dot_file):
parser = lark.Lark(self.grammar, parser='lalr')
node_parser = self.ParseNodes()
edge_parser = self.ParseEdges()
attributes_parser = self.ParseAttributes()
try:
with open(dot_file, "r") as f:
tree = parser.parse(f.read())
attributes_parser.visit(tree)
node_parser.visit(tree)
edge_parser.visit(tree)
except OSError as exc:
raise AutomataError(exc.strerror) from exc
except lark.exceptions.UnexpectedInput as exc:
raise AutomataError(str(exc))
self.nodes = node_parser.nodes
self.edges = edge_parser.edges
self.node_attrs = attributes_parser.node_attrs
self.edge_attrs = attributes_parser.edge_attrs
class ConstraintCondition:
def __init__(self, env: str, op: str, val: str, unit=None):
self.env = env
self.op = op
self.val = val
self.unit = unit
if unit is None:
# try to infer unit from constants or parameters
val_for_unit = val.lower().replace("()", "")
if val_for_unit.endswith("_ns"):
self.unit = "ns"
if val_for_unit.endswith("_jiffies"):
self.unit = "j"
class ConstraintRule:
grammar = r'''
rule: condition (OP condition)*
OP: "&&" | "||"
condition: ENV CMP_OP VAL UNIT?
ENV: CNAME
CMP_OP: "==" | "!=" | "<=" | "<" | ">=" | ">"
VAL: /[0-9]+/
| /[A-Z_]+\(\)/
| /[A-Z_]+/
| /[a-z_]+\(\)/
| /[a-z_]+/
UNIT: "ns" | "us" | "ms" | "s" | "j"
'''
def __init__(self, c: ConstraintCondition):
'''
A list of pairs of
- the condition (e.g. is_constr_dl == 1)
- the logical operator ("||" or "&&") combining this
condition with the next one if it exists, otherwise None
TODO: Perhaps use an abstract syntax tree instead, because
this representation cannot capture precedence
'''
self.rules = [[c, None]]
def chain(self, op: str, c: ConstraintCondition):
self.rules[-1][1] = op
self.rules.append([c, None])
class ConstraintReset:
def __init__(self, env):
self.env = env
class StateLabelParser:
grammar = r'''
label: CNAME ("\\n" condition)?
%import common.CNAME
%import common.WS
%ignore WS
''' + ConstraintRule.grammar
parser = lark.Lark(grammar, parser='lalr', start="label")
def __init__(self, label: str):
try:
tree = self.parser.parse(label)
except lark.exceptions.UnexpectedInput as exc:
raise(AutomataError(f"Unrecognised state \"{label}\"\n{exc}"))
self.state = tree.children[0]
self.constraint = None
if len(tree.children) == 2:
self.constraint = ConstraintCondition(*tree.children[1].children)
if self.constraint.op not in ("<", "<="):
raise AutomataError("State constraints must be clock expirations like"
f" clk<N ({label})")
class EventLabelParser:
grammar = r'''
events: event ("\\n" event)*
event: name (";" guard)?
guard: reset
| rule
| rule ";" reset
| reset ";" rule
name: CNAME
reset: "reset" "(" ENV ")"
%import common.CNAME
%import common.WS
%ignore WS
''' + ConstraintRule.grammar
parser = lark.Lark(grammar, parser='lalr', start="events")
class GetEvents(lark.visitors.Transformer):
def guard(self, args):
reset = None
rule = None
for arg in args:
if arg.data == "reset":
reset = ConstraintReset(arg.children[0])
elif arg.data == "rule":
conditions = arg.children
rule = ConstraintRule(conditions[0])
for i in range(1, len(conditions), 2):
rule.chain(conditions[i], conditions[i + 1])
return reset, rule
def OP(self, args):
return args
def condition(self, args):
return ConstraintCondition(*args)
def event(self, args):
assert(len(args) <= 2)
name = args[0]
rule, reset = None, None
if len(args) == 2:
reset, rule = args[1]
return name, reset, rule
def events(self, args):
return args
def name(self, args):
return args[0]
def __init__(self, label: str):
try:
tree = self.parser.parse(label)
self.events = self.GetEvents().transform(tree)
except lark.exceptions.UnexpectedInput as exc:
raise(AutomataError(f"Unrecognised event \"{label}\"\n{exc}"))
class Transition:
def __init__(self, src: str, dst: str, event: str,
reset: ConstraintReset, rule: ConstraintRule):
self.src = src
self.dst = dst
self.event = event
self.rule = rule
self.reset = reset
class State:
def __init__(self, name: str, inv: ConstraintCondition):
self.name = name
self.inv = inv
class AutomataError(Exception):
"""Exception raised for errors in automata parsing and validation.
Raised when DOT file processing fails due to invalid format, I/O errors,
or malformed automaton definitions.
"""
class Automata:
"""Automata class: Reads a dot file and parses it as an automaton.
It supports both deterministic and hybrid automata.
Attributes:
dot_file: A dot file with an state_automaton definition.
"""
invalid_state_str = "INVALID_STATE"
init_marker = "__init_"
def __init__(self, file_path, model_name=None):
self.__dot_path = file_path
self.name = model_name or self.__get_model_name()
self.__parse_tree = ParseTree(file_path)
self.transitions = self.__parse_transitions()
self.states, self.initial_state, self.final_states = self.__parse_states()
self.env_types = {}
self.env_stored = set()
self.constraint_vars = set()
self.self_loop_reset_events = set()
self.events, self.envs = self.__get_event_variables()
self.function = self.__create_matrix()
self.events_start, self.events_start_run = self.__store_init_events()
self.env_stored = sorted(self.env_stored)
self.constraint_vars = sorted(self.constraint_vars)
self.self_loop_reset_events = sorted(self.self_loop_reset_events)
def __get_model_name(self) -> str:
basename = ntpath.basename(self.__dot_path)
if not basename.endswith(".dot") and not basename.endswith(".gv"):
print("not a dot file")
raise AutomataError(f"not a dot file: {self.__dot_path}")
model_name = ntpath.splitext(basename)[0]
if not model_name:
raise AutomataError(f"not a dot file: {self.__dot_path}")
return model_name
def __parse_transitions(self):
transitions = []
for edge in self.__parse_tree.edges:
attr = self.__parse_tree.edge_attrs.get(edge)
if not attr:
continue
label = attr.get("label")
src, dst = edge
parser = EventLabelParser(label)
for event, reset, rule in parser.events:
transitions.append(Transition(src, dst, event, reset, rule))
transitions.sort(key=lambda t : (t.src, t.event))
return transitions
def __parse_states(self):
initial_state = ""
states = []
final_states = []
for node in self.__parse_tree.nodes:
attr = self.__parse_tree.node_attrs[node]
label = attr.get("label")
if node.startswith(Automata.init_marker):
initial_state = node[len(Automata.init_marker):]
if not label:
continue
parser = StateLabelParser(label)
state = State(parser.state, parser.constraint)
states.append(state)
shape = attr.get("shape")
if shape in ("doublecircle", "ellipse"):
final_states.append(state)
initial_state = next((s for s in states if s.name == initial_state), None)
if not initial_state:
raise AutomataError("The automaton doesn't have an initial state")
if not final_states:
final_states.append(initial_state)
states.remove(initial_state)
states.sort(key=lambda s : s.name)
states.insert(0, initial_state)
return states, initial_state, final_states
def __get_event_variables(self) -> tuple[list[str], list[str]]:
events: list[str] = []
envs: list[str] = []
for transition in self.transitions:
events.append(transition.event)
if transition.reset:
envs.append(transition.reset.env)
self.env_stored.add(transition.reset.env)
if transition.rule:
for c, _ in transition.rule.rules:
envs.append(c.env)
self.__extract_env_var(c)
for state in self.states:
if state.inv:
envs.append(state.inv.env)
self.__extract_env_var(state.inv)
return sorted(set(events)), sorted(set(envs))
def __extract_env_var(self, constraint: ConstraintCondition):
if constraint.unit:
self.env_types[constraint.env] = constraint.unit
if constraint.val[0].isalpha():
self.constraint_vars.add(constraint.val)
def __create_matrix(self) -> list[list[str]]:
# transform the array into a dictionary
events = self.events
states = [s.name for s in self.states]
events_dict = {}
states_dict = {}
nr_event = 0
for event in events:
events_dict[event] = nr_event
nr_event += 1
nr_state = 0
for state in states:
states_dict[state] = nr_state
nr_state += 1
# declare the matrix....
matrix = [[self.invalid_state_str for _ in range(nr_event)] for _ in range(nr_state)]
for transition in self.transitions:
src, dst = transition.src, transition.dst
event = transition.event
if src == dst and transition.reset:
# those events reset also on self loops
self.self_loop_reset_events.add(event)
matrix[states_dict[src]][events_dict[event]] = dst
return matrix
def __store_init_events(self) -> tuple[list[bool], list[bool]]:
events_start = [False] * len(self.events)
events_start_run = [False] * len(self.events)
for i in range(len(self.events)):
curr_event_will_init = 0
curr_event_from_init = False
curr_event_used = 0
for j in range(len(self.states)):
if self.function[j][i] != self.invalid_state_str:
curr_event_used += 1
if self.function[j][i] == self.initial_state.name:
curr_event_will_init += 1
if self.function[0][i] != self.invalid_state_str:
curr_event_from_init = True
# this event always leads to init
if curr_event_will_init and curr_event_used == curr_event_will_init:
events_start[i] = True
# this event is only called from init
if curr_event_from_init and curr_event_used == 1:
events_start_run[i] = True
return events_start, events_start_run
def is_start_event(self, event: str) -> bool:
return self.events_start[self.events.index(event)]
def is_start_run_event(self, event: str) -> bool:
# prefer handle_start_event if there
if any(self.events_start):
return False
return self.events_start_run[self.events.index(event)]
def is_hybrid_automata(self) -> bool:
return bool(self.envs)