mirror of
https://github.com/NationalSecurityAgency/PACE-python.git
synced 2026-11-09 03:59:33 -10:00
370 lines
13 KiB
Python
370 lines
13 KiB
Python
## **************
|
|
## Copyright 2015 MIT Lincoln Laboratory
|
|
## Project: PACE
|
|
## Authors: ATLH
|
|
## Description: Visiblity nodes
|
|
## Modifications:
|
|
## Date Name Modification
|
|
## ---- ---- ------------
|
|
## 17 Feb 2015 ATLH Original file - based on
|
|
## ColumnVisibility.java in Accumulo
|
|
## code base
|
|
## **************
|
|
|
|
import os
|
|
import sys
|
|
this_dir = os.path.dirname(os.path.dirname(__file__))
|
|
base_dir = os.path.join(this_dir, '../..')
|
|
sys.path.append(base_dir)
|
|
|
|
from enum import IntEnum
|
|
import StringIO
|
|
|
|
class VisibilityFormatException(Exception):
|
|
""" Exception raised when unable to process a vis label
|
|
|
|
Attributes:
|
|
msg - error message for situation
|
|
"""
|
|
def __init__(self, msg):
|
|
self.msg = msg
|
|
|
|
def __str__(self):
|
|
return self.msg
|
|
|
|
class NodeType(IntEnum):
|
|
"""
|
|
Represents the four types of nodes.
|
|
|
|
EMPTY: exactly what it says on the tin, an empty node
|
|
|
|
TERM: This is a visibility label term, found at the leaves
|
|
of the tree. For example in 'alice&bob', both 'alice' and
|
|
'bob' would be the terms.
|
|
|
|
OR: Node for an or clause, children are either other OR/AND
|
|
nodes or terminal TERM nodes.
|
|
|
|
AND: Node for an and clause, children are either other OR/AND
|
|
nodes or terminal TERM nodes.
|
|
"""
|
|
EMPTY = 0
|
|
TERM = 1
|
|
OR = 2
|
|
AND = 3
|
|
|
|
VALID_CHAR = ['_','-',':','.','/']
|
|
|
|
class VisNode(object):
|
|
"""
|
|
Basic building block to form visibility trees. Stores the
|
|
type of the node and the start and the end locations of
|
|
the term in the expression, does not actually store the
|
|
term itself. Can have multiple children if OR/AND node:
|
|
for example a&b&c would have three children.
|
|
"""
|
|
def __init__(self, start, end=None, type=NodeType.TERM):
|
|
'''
|
|
Arguments:
|
|
start: integer representing the start of the term,
|
|
in the case of OR/AND nodes, this is just the
|
|
location of the '&'/'|'
|
|
end: integer representing the end of the term,
|
|
in the case of OR/AND nodes, this is just the
|
|
location of the '&'/|'. If not specified, is assumed
|
|
to be one more than the start.
|
|
type: The type of the node as specified in NodeType.
|
|
Defaults to TERM.
|
|
'''
|
|
self.type = type
|
|
self.start = start
|
|
self.children = []
|
|
if end:
|
|
self.end = end
|
|
else:
|
|
self.end = start + 1
|
|
|
|
def copy_node(self, node):
|
|
'''
|
|
Returns a copy of the node of the same type with
|
|
the exception of its children.
|
|
'''
|
|
|
|
return VisNode(start=node.start,
|
|
end=node.end,
|
|
type=node.type)
|
|
|
|
def add(self, child):
|
|
"""
|
|
Adds the child to the end of list of children
|
|
"""
|
|
self.children.append(child)
|
|
|
|
def getTerm(self, expression):
|
|
'''
|
|
When passed the original expression for the node
|
|
returns the associated term (without quotes if they exist).
|
|
Throws an assertion if the node is not a term node.
|
|
'''
|
|
assert self.type == NodeType.TERM
|
|
|
|
if expression[self.start] == '"':
|
|
return expression[(self.start+1):(self.end-1)]
|
|
else:
|
|
return expression[self.start:self.end]
|
|
|
|
class VisTree(object):
|
|
"""
|
|
Represents a container for a root VisNode and the
|
|
corresponding expression
|
|
"""
|
|
def __init__(self, root, expression):
|
|
self.root = root
|
|
self.expression = expression
|
|
|
|
def __str__(self):
|
|
"""
|
|
Overloading str function, does not simply
|
|
return self.expression because it is used
|
|
primarily for testing, and it is useful to
|
|
see the structure of the tree.
|
|
"""
|
|
s = StringIO.StringIO()
|
|
self._stringify(self.root,self.expression, s)
|
|
s_string = s.getvalue()
|
|
s.close()
|
|
return s_string
|
|
|
|
def _stringify(self, root, expression, out_put):
|
|
"""
|
|
Arguments:
|
|
root: VisNode to turn into a string representation
|
|
exression: the corresponding expression for the
|
|
root node passed in
|
|
out_put: StringIO object in which the string
|
|
description is placed.
|
|
|
|
Side Effects: Returns nothing, but string representation
|
|
is placed in the out_put object.
|
|
"""
|
|
#case of empty root
|
|
if root is None:
|
|
out_put.write('')
|
|
return
|
|
|
|
if root.type == NodeType.TERM:
|
|
out_put.write(expression[root.start:root.end])
|
|
else:
|
|
sep = ''
|
|
for c in root.children:
|
|
out_put.write(sep)
|
|
parens = (c.type != NodeType.TERM) and (root.type != c.type)
|
|
if parens:
|
|
out_put.write("(")
|
|
self._stringify(c, expression, out_put)
|
|
if parens:
|
|
out_put.write(")")
|
|
if root.type == NodeType.AND:
|
|
sep = '&'
|
|
else:
|
|
sep = "|"
|
|
|
|
|
|
|
|
class VisParser(object):
|
|
"""
|
|
Contains the logic for parsing visibility labels and turning into
|
|
VisTree
|
|
"""
|
|
|
|
def _getTreeType(self, node, expression):
|
|
return VisTree(node, expression)
|
|
|
|
def parse(self, expression):
|
|
"""
|
|
Arguments:
|
|
expression - the expression to parse
|
|
|
|
Returns: VisTree containing the root node of
|
|
the parsed Visibility Tree and the original expression.
|
|
Raises VisibilityFormatException if the visibility
|
|
is ill-formed.
|
|
"""
|
|
self._index = 0 #current parse location
|
|
self._parens = 0 #number of parenthesis encountered
|
|
|
|
if len(expression) == 0:
|
|
return None
|
|
|
|
node = self._parse(expression)
|
|
|
|
if node is None:
|
|
raise VisibilityFormatException("operator or missing parens: %s" % (expression))
|
|
|
|
if self._parens != 0:
|
|
raise VisibilityFormatException("parenthesis mis-match: %s" % (expression))
|
|
|
|
return self._getTreeType(node, expression)
|
|
|
|
def _isValidAuthChar(self, c):
|
|
"""
|
|
Determines if the character c is an authorized character for the
|
|
visibility field
|
|
"""
|
|
return any([c >= 'a', c <= 'z',
|
|
c >= 'A', c <= 'Z',
|
|
c >= '0', c <= '9',
|
|
c in VALID_CHAR])
|
|
|
|
def _processTerm(self, start, end, node_expr, expression):
|
|
"""
|
|
Arguments:
|
|
start - start of the term
|
|
end - end of the term
|
|
node_expr - Existing term node or None
|
|
expression - the overall expression
|
|
|
|
Returns: Processed term node; if expr existed, it returns
|
|
the existing node, otherwise creates a new VisNode for
|
|
the term
|
|
"""
|
|
if start != end:
|
|
if node_expr is not None:
|
|
raise VisibilityFormatException("expression %s needs to be | or &" % (expression))
|
|
return VisNode(start = start, end = end)
|
|
|
|
if node_expr is None:
|
|
raise VisibilityFormatException("empty term %s" % (expression))
|
|
return node_expr
|
|
|
|
def _create_node(self, start, type):
|
|
return VisNode(start = start, type = type)
|
|
|
|
def _parse(self, expression):
|
|
"""
|
|
Arguments:
|
|
expression - the expression to parse
|
|
|
|
Returns: Root node to the newly parsed visibility tree
|
|
"""
|
|
result = None #current top-level node
|
|
expr = None #child node being parsed
|
|
wholeTermStart = self._index #start of the top-level term
|
|
subtermStart = self._index #start of sub-level term
|
|
subtermComplete = False #has the subterm been completed
|
|
|
|
#loop through all characters and parse them individually
|
|
while self._index < len(expression):
|
|
e = expression[self._index]
|
|
self._index += 1
|
|
if e == '&': #case of whole term being being AND
|
|
expr = self._processTerm(subtermStart, self._index - 1, expr, expression)
|
|
if result != None:
|
|
if result.type != NodeType.AND:
|
|
raise VisibilityFormatException("cannot mix & and |")
|
|
else:
|
|
result = self._create_node(wholeTermStart, NodeType.AND )
|
|
result.add(expr)
|
|
expr = None
|
|
subtermStart = self._index
|
|
subtermComplete = False
|
|
continue
|
|
|
|
elif e == '|': #case of whole term being OR
|
|
expr = self._processTerm(subtermStart, self._index - 1, expr, expression)
|
|
if result != None:
|
|
if result.type != NodeType.OR:
|
|
raise VisibilityFormatException("cannot mix & and |")
|
|
else:
|
|
result = self._create_node(wholeTermStart, NodeType.OR )
|
|
result.add(expr)
|
|
expr = None
|
|
subtermStart = self._index
|
|
subtermComplete = False
|
|
continue
|
|
|
|
elif e == '(': #case of start of a parenthetical term
|
|
self._parens += 1
|
|
if (subtermStart != self._index - 1) or (expr is not None):
|
|
raise VisibilityFormatException("expression needs & or |")
|
|
#parse the subterm expression
|
|
expr = self._parse(expression)
|
|
subtermStart = self._index
|
|
subtermComplete = False
|
|
continue
|
|
|
|
elif e == ')': #case of end of a parenthetical term
|
|
self._parens -= 1
|
|
#process the subterm and make sure it is wellformed
|
|
child = self._processTerm(subtermStart, self._index - 1, expr, expression)
|
|
if child is None and result is None:
|
|
raise VisibilityFormatException("empty expression not allowed")
|
|
if result is None:
|
|
return child
|
|
#if the child is the same type as parent (result), promote the child's children
|
|
if result.type == child.type:
|
|
for c in child.children:
|
|
result.add(c)
|
|
else:
|
|
result.add(child)
|
|
result.end = self._index - 1
|
|
return result
|
|
|
|
elif e == '"': #case of a quoted expression
|
|
if subtermStart != (self._index - 1):
|
|
raise VisibilityFormatException("expression needs & or |")
|
|
|
|
#check to make nothing is invalid escaped in the quotes
|
|
while (self._index < len(expression) and \
|
|
expression[self._index] != '"'):
|
|
if expression[self._index] == '\\':
|
|
self._index += 1
|
|
if (expression[self._index] != '\\' and \
|
|
expression[self._index] != '"'):
|
|
raise VisibilityFormatException('invalid escaping within quotes')
|
|
self._index += 1
|
|
|
|
#case without a closing quote
|
|
if self._index == len(expression):
|
|
raise VisibilityFormatException("unclosed quote")
|
|
|
|
if subtermStart + 1 == self._index:
|
|
raise VisibilityFormatException("empty term")
|
|
|
|
self._index += 1
|
|
subtermComplete = True
|
|
continue
|
|
|
|
else: #all other cases, should be valid characters part of a term
|
|
if subtermComplete:
|
|
raise VisibilityFormatException("expression needs & or |")
|
|
|
|
#check to see the character is valid
|
|
c = expression[self._index - 1]
|
|
if not self._isValidAuthChar(c):
|
|
raise VisibilityFormatException('bad character (%c)' % (c))
|
|
|
|
continue
|
|
|
|
child = self._processTerm(subtermStart, self._index, expr, expression)
|
|
if result is not None:
|
|
result.add(child)
|
|
result.end = self._index
|
|
else:
|
|
result = child
|
|
|
|
if result.type != NodeType.TERM:
|
|
if len(result.children) < 2:
|
|
raise VisibilityFormatException("missing term")
|
|
|
|
return result
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|