1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
"""Methods handling satisfying rule assignments.
"""
# pylint: disable=import-error,no-name-in-module
import runtime.utils as utils
class Assignment:
"""Represents a single satisfying assignment to a /RULE in the Structure.
This class is effectively an intermediary between ProductionRule and
TSDelta.
"""
def __init__(self, rule, assignment):
"""Initialize the Assignment.
"""
self.ts = rule.ts
self.rule = rule
self.assignment = assignment.copy()
self.base_hash = utils.real_hash(assignment)
def apply(self):
"""Applies the rule + assignment to the structure and returns the map.
NOTE: Does *NOT* wrap the delta. The caller should do this if they want
to.
"""
# We will update this dictionary with newly-created nodes as necessary.
running_assignment = self.assignment.copy()
self.add_nodes(running_assignment)
added_facts = self.add_facts(running_assignment)
self.remove(running_assignment, added_facts)
return running_assignment
def add_nodes(self, running_assignment):
"""Adds /INSERT nodes and updates @running_assignment.
"""
for node in self.unassigned_of_type(running_assignment, "/INSERT"):
# NOTE: This also adds the node to the structure.
new_node = self.ts[self.node_name(node) + ":??"].full_name
running_assignment[node] = new_node
for equivalent_node in self.rule.equal[node]:
running_assignment[equivalent_node] = new_node
def add_facts(self, running_assignment):
"""Adds facts to the structure.
The add_facts are rule facts where all rule-nodes are assigned and not
removed (/subtracted?).
"""
translator = utils.Translator(running_assignment)
ignore_nodes = set(self.rule.nodes_by_type["/REMOVE"])
must_include = set(self.rule.nodes_by_type["/INSERT"])
relevant_nodes = set(running_assignment.keys()) - ignore_nodes
new_facts = []
for fact in self.facts_of_nodes(sorted(relevant_nodes)):
args = set(fact)
if ((args & must_include) and
(set(fact) & self.rule.all_nodes) <= relevant_nodes):
new_facts.append(translator.translate_tuple(fact))
self.ts.add_facts(new_facts)
return set(new_facts)
def remove(self, running_assignment, added_facts):
"""Removes the relevant nodes & facts.
We remove nodes that are marked /REMOVE or ones that are marked
/SUBTRACT which have no facts after subtraction.
"""
# (1) First, we just remove the /REMOVE nodes and any facts referencing
# them.
for node in self.assigned_of_type(running_assignment, "/REMOVE"):
node = running_assignment[node]
self.ts[node].remove_with_facts()
# (2) Then we remove /SUBTRACT facts.
# NOTE: Currently, addition takes precedence over removal. So if you
# '/INSERT' a fact that already exists and '/REMOVE' or '/SUBTRACT' it
# at the same time, it will end up *still in the structure*. The
# example for where this semantics is useful is for something like the
# Turing Machine example, where you might want to express keeping the
# same head position as 'remove the current head position then put it
# back in the same spot.'
translator = utils.Translator(running_assignment)
subtract = set(self.assigned_of_type(running_assignment, "/SUBTRACT"))
for fact in self.assigned_rule_facts(running_assignment):
if set(fact) & subtract and fact not in added_facts:
self.ts.remove_fact(translator.translate_tuple(fact))
# (3) Then, we remove /SUBTRACT nodes which have no facts.
for node in self.assigned_of_type(running_assignment, "/SUBTRACT"):
node = running_assignment[node]
if not self.ts.facts_about_node(node, True):
self.ts[node].remove()
def node_name(self, node):
"""Returns the name to use for produced node @node.
Ensures node names are deterministic and reproducible, regardless of
when exactly the match happened.
"""
return "/:" + utils.real_hash("{}{}".format(self.base_hash, node))
def assigned_rule_facts(self, running_assignment):
"""Returns rule facts which do not involve remaining unassigned nodes.
"""
assigned_rule_nodes = set(running_assignment.keys())
for fact in self.rule.facts:
fact_rule_nodes = set(fact) & self.rule.all_nodes
if fact_rule_nodes <= assigned_rule_nodes:
yield fact
def assigned_of_type(self, running_assignment, of_type):
"""Returns nodes already assigned to of a particular type.
"""
for node in self.rule.nodes_by_type[of_type]:
if node in running_assignment:
yield node
def unassigned_of_type(self, running_assignment, of_type):
"""Returns nodes not yet assigned which are @of_type in self.rule.
Eg., you could use this to return all nodes of_type=/INSERT which are
not already constructed (i.e., in running_assignment).
"""
for node in self.rule.nodes_by_type[of_type]:
if node not in running_assignment:
yield node
def facts_of_nodes(self, nodes):
"""Helper method to return facts with one of @nodes in the first slot.
NOTE: This uses the cached copy from @self.rule.indexed_facts, meaning
these are such facts which were in the structure when @rule was
initialized. We do this so we can remove rule-related nodes from the
structure after initialization.
"""
assert set(nodes) <= set(self.rule.all_nodes)
return (fact for node in nodes
for fact in self.rule.indexed_facts[node])
def __str__(self):
return str(self.assignment)
|
