First, very basic implementation to pass all of the (current) tests.

1 files changed, 118 insertions, 6 deletions

diff --git a/gn_libs/privileges.py b/gn_libs/privileges.py
index a515970..ea523a0 100644
--- a/gn_libs/privileges.py
+++ b/gn_libs/privileges.py
@@ -1,5 +1,5 @@
 """Utilities for handling privileges."""
-from typing import Union, Sequence, TypeAlias
+from typing import Union, Sequence, Iterator, TypeAlias
 
 Operator: TypeAlias = str # Valid operators: "AND", "OR"
 Privilege: TypeAlias = str
@@ -12,19 +12,131 @@ ParseTree = tuple[Operator,
 
 class SpecificationValueError(ValueError):
     """Raised when there is an error in the specification string."""
-    pass
+
+
+_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 SpecificationValueError(
-    #         "You passed an empty specification. I do not know what to do.")
+    if spec.strip() == "":
+        raise _EMPTY_SPEC_ERROR_
 
-    return tuple()
+    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