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
|
"""Utilities for handling privileges."""
from typing import Union, Sequence, Iterator, TypeAlias
Operator: TypeAlias = str # Valid operators: "AND", "OR"
Privilege: TypeAlias = str
PrivilegesList: TypeAlias = Sequence[Privilege]
ParseTree = tuple[Operator,
# Leaves (`PrivilegesList` objects) on the left,
# trees (`ParseTree` objects) on the right
Union[PrivilegesList, tuple[PrivilegesList, 'ParseTree']]]
class SpecificationValueError(ValueError):
"""Raised when there is an error in the specification string."""
_OPERATORS_ = ("OR", "AND")
_EMPTY_SPEC_ERROR_ = SpecificationValueError(
"Empty specification. I do not know what to do.")
def __add_leaves__(
index: int,
tree: tuple[Operator],
leaves: dict
) -> Union[tuple[Operator], ParseTree]:
"""Add leaves to the tree."""
if leaves.get(index):
return tree + (leaves[index],)
return tree
def __build_tree__(tree_state: dict) -> ParseTree:
"""Given computed state, build the actual tree."""
_built= []
for idx, tree in enumerate(tree_state["trees"]):
_built.append(__add_leaves__(idx, (tree[2],), tree_state["leaves"]))
print(f"Number of built trees: {len(_built)}, {_built}")
_num_trees = len(_built)
for idx in range(0, _num_trees):
_last_tree = _built.pop()
print(f"LAST TREE: {_last_tree}, {len(_last_tree)}")
if len(_last_tree) <= 1:# Has no leaves or subtrees
_last_tree = None# type: ignore[assignment]
continue# more evil
_name = tree_state["trees"][_num_trees - 1 - idx][0]
_parent = tree_state["trees"][
tree_state["trees"][_num_trees - 1 - idx][1]]
_op = tree_state["trees"][_num_trees - 1 - idx][2]
print(f"TREE => name: {_name}, operation: {_op}, parent: {_parent}")
if _name != _parent[0]:# not root tree
print(f"{_op} == {_parent[2]} : {_op == _parent[2]}")
if _op == _parent[2]:
_built[_parent[0]] = (
_built[_parent[0]][0],# Operator
_built[_parent[0]][1] + _last_tree[1]# merge leaves
) + _last_tree[2:]#Add any trees left over
else:
_built[_parent[0]] += (_last_tree,)
if _last_tree is None:
raise _EMPTY_SPEC_ERROR_
return _last_tree
def __parse_tree__(tokens: Iterator[str]) -> ParseTree:
"""Parse the tokens into a tree."""
_state = {
"tokens": [],
"trees": [],#(name, parent, operator, start, end)
"open-parens": 0,
"current-tree": 0,
"leaves": {}#[parent-tree, [index, index, ...]]
}
for _idx, _token in enumerate(tokens):
_state["tokens"].append(_token)
if _idx==0:
if _token[1:].upper() not in _OPERATORS_:
print(f"'{_token[1:].upper()}' == {_OPERATORS_}")
raise SpecificationValueError(f"Invalid operator: {_token[1:]}")
_state["open-parens"] += 1
_state["trees"].append((0, 0, _token[1:].upper(), _idx))
_state["current-tree"] = 0
continue# this is bad!
if _token == ")":# end a tree
print(f"ENDING A TREE: {_state}")
_state["open-parens"] -= 1
_state["trees"][_state["current-tree"]] = (
_state["trees"][_state["current-tree"]] + (_idx,))
# We go back to the parent below.
_state["current-tree"] = _state["trees"][_state["current-tree"]][1]
continue# still really bad!
if _token[1:].upper() in _OPERATORS_:# new child tree
_state["open-parens"] += 1
_state["trees"].append((len(_state["trees"]),
_state["current-tree"],
_token[1:].upper(),
_idx))
_state["current-tree"] = len(_state["trees"]) - 1
continue# more evil still
print(f"state: {_state}")
# leaves
_state["leaves"][_state["current-tree"]] = _state["leaves"].get(
_state["current-tree"], tuple()) + (_token,)
# Build parse-tree from state
if _state["open-parens"] != 0:
raise SpecificationValueError("Unbalanced parentheses.")
return __build_tree__(_state)
def __tokenise__(spec: str) -> Iterator[str]:
"""Clean up and tokenise the string."""
return (token.strip()
for token in spec.replace(
"(", " ("
).replace(
")", " ) "
).replace(
"( ", "("
).split())
def parse(spec: str) -> ParseTree:
"""Parse a string specification for privileges and return a tree of data
objects of the form (<operator> (<check>))"""
if spec.strip() == "":
raise _EMPTY_SPEC_ERROR_
return __parse_tree__(__tokenise__(spec))
def check(spec: str, privileges: tuple[str, ...]) -> bool:
"""Check that the sequence of `privileges` satisfies `spec`."""
_spec = spec
_privs = privileges
return False
|
