From 66e443ffc4b01a494dec805454f1ef35e9055cf3 Mon Sep 17 00:00:00 2001 From: Tomas Gavenciak Date: Sat, 8 May 2010 20:31:51 -0400 Subject: [PATCH] Imporoved and shortened conf.py code Removed subtrees, now only one namespace Transparent variable creation upon lookup Implemented general condition clauses (AND, OR, NOT, ==, !=) Conditions now have 'parent' condition (containing condition block) Variables refer to only one condition (and indirectly its parents) Renamed get_value -> evaluate and evaluate -> value Improved max-depth checking Updated the test/example (still no conditions) pprint replaced with dump (for consistency, but still returns an iterator) Some dovumentation (with TODO's) --- t/moe/conf.py | 327 ++++++++++++++++++++++++++------------------- t/moe/conf.test.py | 48 +++---- 2 files changed, 206 insertions(+), 169 deletions(-) diff --git a/t/moe/conf.py b/t/moe/conf.py index 3f77e48..6d61b33 100644 --- a/t/moe/conf.py +++ b/t/moe/conf.py @@ -1,232 +1,276 @@ -import types, itertools +import types, itertools, re import logging as log -# ALL in unicode +""" +Lazy conditional string evaluation module for configuration variables. + + +* Each variable has ordered list of operations (definitions), each SETs or APPENDs an expression +to the value. Each operation may be guarded by condition. + +NOTE: Variable is undefined even if some 'APPEND' apply but no 'SET' applies. This might change. + +* Each condition is a formula (tree consisting of 'AND', 'OR', 'NOT' and '==', '!=' between +two expressions. + +* Expression is a list of strings and variables to be expanded. + +NOTE: All expanded data should be (or is converted to) unicode + +TODO: Cleanup of unused undefined variables. +TODO: Better variable name checking (no name '.'-structural prefix of another) +TODO: Implemet "subtree" listing. +TODO: Test conditions and unicode +""" c_tree_sep = u'.' -c_comment = u'\n' +c_comment = u'#' c_open = u'{' c_close = u'}' c_if = u'if' -c_maxdepth = 42 -c_pprint_indent = 2 + +"Variable name regexp, dots (separators) must be separated from edges and each other." +re_key = re.compile(r'\A([A-Za-z0-9_-]+\.)*[A-Za-z0-9_-]+\Z') + +"Allowed depth of recursion -- includes ALL recursive calls, so should quite high." +c_maxdepth = 256 + +"Maximum attained depth of recursion" +debug_maxdepth = 0 + +def check_depth(depth): + "Helper to check for recursion depth." + global debug_maxdepth + if depth > c_maxdepth: + raise ConfigError('Too deep recursion in config evaluation (cyclic substitution?)') + if depth > debug_maxdepth: + debug_maxdepth = depth + class ConfigError(Exception): pass -# WARNING: Currently, only appending to a variable results in undefined class ConfigTree(object): """ - Configuration subtree (namespace). Contains subtrees and variables. + Configuration tree containing all the variables. + + The variables in `self.variables` are referenced directly by the full name. """ - def __init__(self, name, tree): - """ - Create configuration subtree `name` under `tree`. - Use `name=None` and `tree=None` for the root tree. - """ - # Name of the tree - self.name = name - # Parent tree - self.tree = tree - # Elements of this tree (variables and subtrees) - self.elements = {} - # Full name with separators (None for root tree) - if self.tree and self.tree.fullname: - self.fullname = self.tree.fullname + c_tree_sep + self.name - else: - self.fullname = self.name - if self.tree: - self.tree.add(self.name, self) - def add(self, name, element): - "Add an element (subtree or a variable)." - if self.elements.has_key(name): - raise ConfigError('Element %s already present in tree %s'%(name, self.fullname)) - self.elements[name] = element - def remove(self, name): - "Remove an element (subtree or a variable)." - self.elements.pop(name) - def pprint(self, indent=0): + def __init__(self): + self.variables = {} + def lookup(self, key, create = True): + """ + Lookup and return a variable. + If not found and `create` set, check the name and transparently create a new one. + """ + if not key in self.variables: + if not create: + raise ConfigError('Config variable %r undefined.', key) + if not re_key.match(key): + raise ConfigError('Invalid variable identifier %r in config', key) + self.variables[key] = ConfigVar(key) + return self.variables[key] + def dump(self, prefix=''): """ Pretty printing of the tree. - Returns list of lines (strings). + Returns an iterator of lines (strings). """ - if self.name: - s = [u'%*sSubtree %s'%(indent, u'', self.name)] - else: - s = [u'%*sRoot tree'%(indent, u'')] - for e in sorted(self.elements.values()): - s.extend(e.pprint(indent + c_pprint_indent)) - return s + return itertools.chain(*[ + self.variables[k].dump(prefix) for k in sorted(self.variables.keys()) + ]) class ConfigElem(object): """ Base class for cahed config elements - variables and conditions """ - def __init__(self, name, tree): - # Name in the subtree, for conditions the defining text - self.name = name - # Parent tree - self.tree = tree - # Full name with separators (only informative for conditions) - if self.tree.fullname: - self.fullname = self.tree.fullname + c_tree_sep + self.name - else: - self.fullname = self.name + def __init__(self, name): + # Full name with separators, definition for conditions + self.name = name # Vars and conditions depending on value of this one self.dependants = set([]) # Cached value (may be None in case of evaluation error) self.cached = False self.cached_val = None - def depth_check(self, depth): - """ - Helper to check for recursion depth. - """ - if depth > c_maxdepth: - raise ConfigError('Too deep recursion in config evaluation (cyclic substitution?)') def invalidate(self, depth=0): """ Invalidate cached data and invalidate all dependants. Does nothing if not cached. """ - self.depth_check(depth) + check_depth(depth) if self.cached: - log.debug('invalidating %r', self.fullname) + log.debug('invalidating %r', self.name) self.cached = False for d in self.dependants: d.invalidate(depth + 1) - def evaluate(self, depth=0): - """ - Cached interface for get_value(), returns a value or throws an exception. - """ - self.depth_check(depth) + def value(self, depth=0): + "Caching helper calling self.evaluate(), returns a value or throws an exception." + check_depth(depth) if not self.cached: - self.cached_val = self.get_value(depth+1) + self.cached_val = self.evaluate(depth+1) self.cached = True if self.cached_val == None: - raise ConfigError("Unable to evaluate %r."%(self.fullname,)) + raise ConfigError("Unable to evaluate %r."%(self.name,)) return self.cached_val - def get_value(self, depth=0): - raise ConfigError('get_value() not implemented') - -class ConfigEqCondition(ConfigElem): - "Simple (in)equality condition" - def __init__(self, name, tree, parent_cond, ex1, ex2, equality=True): - super(ConfigVar, self).__init__(name, tree) - # Tuple of two compared expressions - self.expressions = (ex1, ex2) - # If true, test for equality, otherwise inequality - self.equality = equality - # Parent condition in the configuration tree (or None) - self.parent_cond = parent_cond + def __str__(self): + return self.name + +class ConfigCondition(ConfigElem): + """ + Condition using equality and logic operators. + Clause is a tuple-tree in the following recursive form: + ('AND', c1, c1), ('OR', c1, c2), ('NOT', c1), + ('==', e1, e2), ('!=', e1, e2) where e1, e2 are `ConfigExpression`s. + """ + def __init__(self, text, clause, parent=None): + """ + Condition defined by `text` (informative), `clause` as in class definition, + `parent` is the parent condition (if any). + """ + super(ConfigVar, self).__init__(text) + self.clause = clause + self.parent = parent # Setup dependencies on used variables (not on the parent condition) - for e in self.expressions: - for v in e.variables(): - v.dependants.add(self) + for v in self.variables(): + v.dependants.add(self) + if self.parent: + self.parent.dependants.add(self) + def variables(self, cl=None): + "Return an iterator of variables used in clause `cl`" + if not cl: + cl = self.clause + if cl[0] in ['==','!=']: + return itertools.chain(cl[1].variables(), cl[2].variables()) + if cl[0] in ['AND','OR']: + return itertools.chain(self.variables(cl[1]), self.variables(cl[2])) + return self.variables(cl[1]) # only 'NOT' left def remove_dependencies(self): - "Remove self as dependant from all dependencies" - for e in self.expressions: - for v in e.variables(): - v.dependants.remove(self) - def get_value(self, depth=0): - "Evaluate the condition (not cached)" - v = (ex1.evaluate(depth+1) == ex2.evaluate(depth+1)) - if self.equality: + "Remove self as a dependant from all used variables" + for v in self.variables(): + v.dependants.discard(self) + if self.parent: + self.parent.dependants.discard(self) + def evaluate(self, cl=None, depth=0): + """Evaluate clause `cl` (or the entire condition). + Partial evaluation for AND and OR. Tests the parent condition first.""" + check_depth(depth) + if not cl: + cl = self.clause + if self.parent and not self.parent.value(): + return False + if cl[0] in ['==','!=']: + v = cl[1].evaluate(depth+1) == cl[2].evaluate(depth+1) + if cl[0] == '!=': v = not v return v - return not v - def __str__(self): + v1 = self.evaluate(cl[1], depth+1) + if cl[0] == 'NOT': + return not v1 + if cl[0] == 'OR' and v1: return True + if cl[0] == 'AND' and not v1: return False + return self.evaluate(cl[2], depth+1) + def str(self, parents=False): + "Retur the defining expression, if `parents` set, then prefixed with parent conditions." + if parents and self.parent: + return self.parent.str(parents=True) + u' && ' + self.name return self.name + def __str__(self): + return self.str(parents=False) class ConfigVar(ConfigElem): - def __init__(self, name, tree): - super(ConfigVar, self).__init__(name, tree) + def __init__(self, name): + super(ConfigVar, self).__init__(name) # Ordered list of operations - # (operation, [condition], expression ) - # operation is currently restricted to 'SET' and 'APPEND' - self.expressions = [] - # Fixed to value (may bi None) + # (operation, condition, expression) + # operation is currently 'SET' and 'APPEND' + self.operations = [] + # Fixed to value (may be None) # TODO self.fixed = False self.fixed_val = None - # Register in a subtree - if self.tree: - self.tree.add(name, self) def variables(self): "Return a set of variables used in the expressions" - return set(sum([ list(e[2].variables()) for e in self.expressions ], [])) - def conditions(self): - "Return a set of conditions used in the expressions" - return set(sum([ e[1] for e in self.expressions ], [])) - def add_operation(self, operation, conditions, expression, index=None): + return set(sum([ list(e[2].variables()) for e in self.operations ], [])) + def add_operation(self, operation, condition, expression, index=None): """ - Adds a new operation to the given index (None for appending). - Adds the variable as a dependant to the conditions and variables in the expressions. + Inserts a new operation to position `index` (`None` appends). + Adds the variable as a dependant of the conditions and variables used in the expressions. """ - # First invalidate cached value + # Invalidate cached value self.invalidate() # Add the operation - expr = (operation, conditions, expression) + expr = (operation, condition, expression) if index: - self.expressions.insert(index, expr) + self.operations.insert(index, expr) else: - self.expressions.append(expr) + self.operations.append(expr) # Create dependencies for v in expression.variables(): v.dependants.add(self) - for c in conditions: - c.dependants.add(self) + if condition: + condition.dependants.add(self) def remove_operation(self, index): """ Remove the operation at given index. Also removes the variable as dependant from all conditions and variables used in this - operation that are no longer used. NOTE: this may be slow. + operation that are no longer used. """ - # First invalidate cached value + # Invalidate cached value self.invalidate() # Remove the operation - operation, conditions, expression = self.expressions[index] - self.expressions.pop(index) - # Remove obsolete dependencies on variables + operation, condition, expression = self.operations[index] + self.operations.pop(index) + # Remove dependencies on variables unused in other operations vs = self.variables() for v in expression.variables(): - if not v in vs: + if v not in vs: v.dependants.remove(self) - # Remove obsolete dependencies on variables - cs = self.conditions() - for c in conditions: - if not c in cs(): - c.dependants.remove(self) - def get_value(self, depth=0): - log.debug('evaluating var %r', self.fullname) + # Remove the dependency on the conditions (if not used in another operation) + if condition and condition not in [e[1] for e in self.operations]: + condition.dependants.remove(self) + def evaluate(self, depth=0): + """ + Find the last 'SET' operation that applies and return the result of concatenating with all + subsequent applicable 'APPEND' operations. The result is the same as performing the operations + first-to-last. + NOTE: undefined if some 'APPEND' apply but no 'SET' applies. + """ + check_depth(depth) + log.debug('evaluating var %r', self.name) # List of strings to be concatenated val = [] # Scan for last applicable expression - try each starting from the end, concatenate extensions - for i in range(len(self.expressions)-1, -1, -1): - operation, conditions, expr = self.expressions[i] - # Check all conditions guarding an expression - if all([c.evaluate(depth+1) for c in conditions]): + for i in range(len(self.operations)-1, -1, -1): + operation, condition, expr = self.operations[i] + # Check the guarding condition + if (not condition) or condition.value(depth+1): val.insert(0, expr.evaluate(depth+1)) if operation == 'SET': return u''.join(val) return None - def pprint(self, indent=0): + def dump(self, prefix=''): """ Pretty printing of the variable. Includes all operations. Returns iterator of lines (unicode strings). """ - yield u'%*s%s = \'%s\'' % (indent, u'', self.name, self.evaluate(0)) - for operation, conditions, expr in self.expressions: - yield u'%*s%s %s %s' % (indent + c_pprint_indent, '', operation, conditions, expr) + # Try to evaluate the variable, but avoid undefined exceptions + v = None + try: + v = self.value(depth=0) + except ConfigError: + pass + yield prefix+u'%s = %r' % (self.name, v) + for operation, condition, expr in self.operations: + yield prefix+u' %s [%s] %s' % (operation, condition and condition.str(parents=True), expr) class ConfigExpression(object): """ String expression with some unexpanded config variables. Used in variable operations and conditions. Expression is given as a list of unicode strings and ConfigVar variables to be expanded. """ - def __init__(self, exprlist, original = ''): + def __init__(self, exprlist, original = u''): self.exprlist = exprlist # Original defining string self.original = original - # Replace strings with + # Replace strings with unicode for i in range(len(self.exprlist)): e = self.exprlist[i] if isinstance(e, types.StringTypes): @@ -238,15 +282,16 @@ class ConfigExpression(object): def __str__(self): return self.original def evaluate(self, depth): - "Return a unicode result of expansion of the variables." + check_depth(depth) + "Return unicode result of expansion of the variables." s = [] for e in self.exprlist: if isinstance(e, ConfigVar): - s.append(e.evaluate(depth+1)) + s.append(e.value(depth+1)) elif isinstance(e, unicode): s.append(e) else: - raise ConfigError('Unsupported type %s in expression \'%s\'.'%(type(e), self)) + raise ConfigError('Invalid type %s in expression \'%s\'.'%(type(e), self)) return u''.join(s) diff --git a/t/moe/conf.test.py b/t/moe/conf.test.py index d43a129..a630e61 100644 --- a/t/moe/conf.test.py +++ b/t/moe/conf.test.py @@ -7,33 +7,25 @@ vcnt = 3 def cs(s): return conf.ConfigExpression([s], s) -root = conf.ConfigTree(None, None) -t_a = conf.ConfigTree('a', root) -t_a_b = conf.ConfigTree('b', t_a) -t_c = conf.ConfigTree('c', root) +root = conf.ConfigTree() -v_r = conf.ConfigVar('r', root) -v_r.add_operation('SET', [], cs('ROOTVAR')) - -v_a = [] -v_b = [] for i in range(vcnt): - v_a.append(conf.ConfigVar('va%d'%i, t_a)) - v_a[i].add_operation('SET', [], cs('VALUE-A%d'%i)) - - v_b.append(conf.ConfigVar('vb%d'%i, t_a_b)) - v_b[i].add_operation('APPEND', [], cs(' FOO')) - v_b[i].add_operation('SET', [], conf.ConfigExpression([v_a[i]], '{va%d}'%i)) - v_b[i].add_operation('APPEND', [], cs(' BAR')) - if i>0: - v_b[i].add_operation('APPEND', [], conf.ConfigExpression([' ', v_b[i-1]], ' {vb%d}'%(i-1))) -print '\n'.join(root.pprint()) - -v_b[0].remove_operation(1) -v_b[0].add_operation('SET', [], cs('NEW-VALUE')) -v_b[1].add_operation('APPEND', [], cs(' NEW-ADDED')) -v_a[1].add_operation('APPEND', [], cs(' NEW-ADDED-A')) -print '\n'.join(root.pprint()) - -v_a[0].add_operation('SET', [], cs('NEW-VALUE-A0')) -print '\n'.join(root.pprint()) + root.lookup('a.v%d'%i).add_operation('SET', None, cs('A%d'%i)) + b = root.lookup('b.v%d'%i) + b.add_operation('APPEND', None, cs(' ')) + b.add_operation('SET', None, conf.ConfigExpression([root.lookup('a.v%d'%i)], '{a.v%d}'%i)) + b.add_operation('APPEND', None, cs(' ')) + if i')) +root.lookup('a.v1').add_operation('APPEND', None, cs(' ')) +print '\n'.join(root.dump()) + +root.lookup('a.v0').add_operation('SET', [], cs('')) +print '\n'.join(root.dump()) +print 'maxdepth: %d'%conf.debug_maxdepth -- 2.39.2