t/moe/conf.py

   1 """
   2 conf.py
   3 -------
   4
   5 Lazy conditional string evaluation module for Moe configuration variables.
   6
   7
   8 * Each variable has ordered list of operations (definitions), each defining operation either
   9 assigns (SET) or appends (APPEND) value of an expression to the variable. Each operation may be guarded by condition(s).
  10
  11 NOTE: If no 'SET' applies, a variable is still undefined even if some 'APPEND' applies. This might change.
  12
  13 * Each condition is a formula (tree consisting of 'AND', 'OR', 'NOT' and '==', '!=' between two expressions.
  14
  15 * Expression is a list of strings and variables to be expanded.
  16
  17 NOTE: All expanded data should be (or is converted to) unicode
  18
  19
  20 TODO: Fixing value of variables.
  21 TODO: Cleanup of unused undefined variables.
  22 TODO: Better variable name checking (no name '.'-structural prefix of another)
  23 TODO: Implemet "subtree" listing.
  24 TODO: Test conditions and unicode
  25 """
  26
  27 import types, itertools, re, bisect
  28 import logging as log
  29
  30 "Allowed depth of recursion - includes ALL recursive calls, so should quite high."
  31 c_maxdepth = 256
  32
  33 "Maximum attained depth of recursion - for debug/testing"
  34 debug_maxdepth = 0
  35
  36 "Variable name regexp, dots (separators) must be separated from edges and each other."
  37 re_VARNAME = re.compile(r'\A([A-Za-z0-9_-]+\.)*[A-Za-z0-9_-]+\Z')
  38
  39 def check_depth(depth):
  40   "Helper to check for recursion depth."
  41   global debug_maxdepth
  42   if depth > c_maxdepth:
  43     raise CyclicConfigError('Too deep recursion in config evaluation (cyclic substitution?)')
  44   if depth > debug_maxdepth:
  45     debug_maxdepth = depth
  46
  47
  48 class ConfigError(Exception):
  49   pass
  50
  51 class UndefinedError(ConfigError):
  52   pass
  53
  54 class VariableNameError(ConfigError):
  55   pass
  56
  57 class CyclicConfigError(ConfigError):
  58   pass
  59
  60
  61 class ConfigTree(object):
  62   """
  63   Configuration tree containing all the variables.
  64
  65   The variables in `self.variables` are referenced directly by the full name.
  66   """
  67   def __init__(self):
  68     self.variables = {}
  69   def lookup(self, key, create = True):
  70     """
  71     Lookup and return a variable.
  72     If not found and `create` set, check the name and transparently create a new one.
  73     """
  74     if key not in self.variables:
  75       if not re_VARNAME.match(key):
  76         raise VariableNameError('Invalid variable identifier %r in config', key)
  77       if not create:
  78         raise UndefinedError('Config variable %r undefined.', key)
  79       self.variables[key] = ConfigVar(key)
  80     return self.variables[key]
  81   def dump(self, prefix=''):
  82     """
  83     Pretty printing of the tree.
  84     Returns an iterator of lines (strings).
  85     """
  86     return itertools.chain(*[
  87       self.variables[k].dump(prefix) for k in sorted(self.variables.keys())
  88       ])
  89
  90 class ConfigElem(object):
  91   """
  92   Base class for cahed config elements - variables and conditions
  93   """
  94   def __init__(self, name):
  95     # Full name with separators, definition for conditions
  96     self.name = name
  97     # Vars and conditions depending on value of this one
  98     self.dependants = set([])
  99     # Cached value (may be None in case of evaluation error)
 100     self.cached = False
 101     self.cached_val = None
 102   def invalidate(self, depth=0):
 103     """
 104     Invalidate cached data and invalidate all dependants.
 105     Does nothing if not cached.
 106     """
 107     check_depth(depth)
 108     if self.cached:
 109       log.debug('invalidating %s', self)
 110       self.cached = False
 111       for d in self.dependants:
 112         d.invalidate(depth + 1)
 113   def value(self, depth=0):
 114     "Caching helper calling self.evaluate(), returns a value or throws an exception."
 115     check_depth(depth)
 116     if not self.cached:
 117       self.cached_val = self.evaluate(depth=depth+1)
 118       self.cached = True
 119     if self.cached_val == None:
 120       raise UndefinedError("Unable to evaluate %r."%(self.name,))
 121     return self.cached_val
 122   def __str__(self):
 123     return self.name
 124
 125 class ConfigCondition(ConfigElem):
 126   """
 127   Condition using equality and logic operators.
 128   Clause is a tuple-tree in the following recursive form:
 129   ('AND', c1, c1), ('OR', c1, c2), ('NOT', c1),
 130   ('==', e1, e2), ('!=', e1, e2) where e1, e2 are `ConfigExpression`s.
 131   """
 132   def __init__(self, formula, text=None, parent=None):
 133     """
 134     Condition defined by `text` (informative), `formula` as in class definition,
 135     `parent` is the parent condition (if any).
 136     """
 137     if not text:
 138       text = self.formula_string(formula)
 139     super(ConfigCondition, self).__init__(text)
 140     self.formula = formula
 141     self.parent = parent
 142     # Setup dependencies on used variables (not on the parent condition)
 143     for v in self.variables():
 144       v.dependants.add(self)
 145     if self.parent:
 146       self.parent.dependants.add(self)
 147   def variables(self, cl=None):
 148     "Return an iterator of variables used in formula `cl`"
 149     if not cl:
 150       cl = self.formula
 151     if cl[0] in ['==','!=']:
 152       return itertools.chain(cl[1].variables(), cl[2].variables())
 153     if cl[0] in ['AND','OR']:
 154       return itertools.chain(self.variables(cl[1]), self.variables(cl[2]))
 155     return self.variables(cl[1]) # only 'NOT' left
 156   def remove_dependencies(self):
 157     "Remove self as a dependant from all used variables"
 158     for v in self.variables():
 159       v.dependants.discard(self)
 160     if self.parent:
 161       self.parent.dependants.discard(self)
 162   def evaluate(self, cl=None, depth=0):
 163     """Evaluate formula `cl` (or the entire condition).
 164     Partial evaluation for AND and OR. Tests the parent condition first."""
 165     check_depth(depth)
 166     if not cl:
 167       cl = self.formula
 168     if self.parent and not self.parent.value():
 169       return False
 170     if cl[0] in ['==','!=']:
 171       v = cl[1].evaluate(depth=depth+1) == cl[2].evaluate(depth=depth+1)
 172       if cl[0] == '!=': v = not v
 173       return v
 174     v1 = self.evaluate(cl=cl[1], depth=depth+1)
 175     if cl[0] == 'NOT':
 176       return not v1
 177     if cl[0] == 'OR' and v1: return True
 178     if cl[0] == 'AND' and not v1: return False
 179     return self.evaluate(cl=cl[2], depth=depth+1)
 180   def formula_string(self, formula):
 181     "Create a string representation of a formula."
 182     if formula[0] == 'AND':
 183       return itertools.chain(['('], self.formula_string(formula[1]), [' and '], self.formula_string(formula[2]),[')'])
 184     elif formula[0] == 'OR':
 185       return itertools.chain(['('], self.formula_string(formula[1]), [' or '], self.formula_string(formula[2]),[')'])
 186     elif formula[0] == 'NOT':
 187       return itertools.chain(['(not '], self.formula_string(formula[1]),[')'])
 188     elif formula[0] in ['==', '!=']:
 189       return itertools.chain(formula[1], formula[0], formula[2])
 190     return iter(['<invalid formula>'])
 191   def str(self, parents=False):
 192     "Retur the defining expression, if `parents` set, then prefixed with parent conditions."
 193     if parents and self.parent:
 194       return self.parent.str(parents=True) + u' && ' + self.name
 195     return self.name
 196   def __str__(self):
 197     return self.str(parents=False)
 198
 199 class Operation(object):
 200   "Helper class for operation data. Must not be present in more variables or present multiple times."
 201   def __init__(self, operation, condition, expression, level=0, source='?'):
 202     # operation is currently 'SET' and 'APPEND'
 203     self.operation = operation
 204     self.condition = condition
 205     self.expression = expression
 206     self.level = level
 207     self.source = source
 208   def __str__(self):
 209     return "%s <%d, %s> [%s] %r" % ( {'SET':'=', 'APPEND':'+'}[self.operation], self.level, self.source,
 210       (self.condition and self.condition.str(parents=True)) or '', unicode(self.expression))
 211
 212 class ConfigVar(ConfigElem):
 213   def __init__(self, name):
 214     super(ConfigVar, self).__init__(name)
 215     # Ordered list of `Operations` (ascending by `level`)
 216     self.operations = []
 217     # Fixed to value (may be None)
 218     # TODO: fixing
 219     self.fixed = False
 220     self.fixed_val = None
 221   def variables(self):
 222     "Return a set of variables used in the expressions"
 223     return set(sum([ list(op.expression.variables()) for op in self.operations ], []))
 224   def add_operation(self, operation):
 225     """
 226     Inserts an operation. The operations are sorted by `level` (ascending), new operation goes last among
 227     these with the same level.
 228     Adds the variable as a dependant of the conditions and variables used in the expressions.
 229     """
 230     # Invalidate cached value
 231     self.invalidate()
 232     # Add the operation
 233     pos = bisect.bisect_right([o.level for o in self.operations], operation.level)
 234     self.operations.insert(pos, operation)
 235     # Create dependencies
 236     for v in operation.expression.variables():
 237       v.dependants.add(self)
 238     if operation.condition:
 239       operation.condition.dependants.add(self)
 240   def remove_operation(self, operation):
 241     """
 242     Remove the Operation.
 243     Also removes the variable as dependant from all conditions and variables used in this
 244     operation that are no longer used.
 245     """
 246     # Invalidate cached value
 247     self.invalidate()
 248     # Remove the operation
 249     self.operations.remove(operation)
 250     # Remove dependencies on variables unused in other operations
 251     vs = self.variables()
 252     for v in operation.expression.variables():
 253       if v not in vs:
 254         v.dependants.remove(self)
 255     # Remove the dependency on the conditions (if not used in another operation)
 256     if operation.condition and operation.condition not in [op.condition for op in self.operations]:
 257       condition.dependants.remove(self)
 258   def evaluate(self, depth=0):
 259     """
 260     Find the last 'SET' operation that applies and return the result of concatenating with all
 261     subsequent applicable 'APPEND' operations. The result is the same as performing the operations
 262     first-to-last.
 263     NOTE: undefined if some 'APPEND' apply but no 'SET' applies.
 264     """
 265     check_depth(depth)
 266     log.debug('evaluating var %r', self.name)
 267     # List of strings to be concatenated
 268     val = []
 269     # Scan for last applicable expression - try each starting from the end, concatenate extensions
 270     for i in range(len(self.operations)-1, -1, -1):
 271       op = self.operations[i]
 272       # Check the guarding condition
 273       if (not op.condition) or op.condition.value(depth+1):
 274         val.insert(0, op.expression.evaluate(depth=depth+1))
 275         if op.operation == 'SET':
 276           return u''.join(val)
 277     return None
 278   def dump(self, prefix=''):
 279     """
 280     Pretty printing of the variable. Includes all operations.
 281     Returns iterator of lines (unicode strings).
 282     """
 283     # Try to evaluate the variable, but avoid undefined exceptions
 284     v = None
 285     try:
 286       v = self.value(depth=0)
 287     except ConfigError:
 288       pass
 289     yield prefix+u'%s = %r' % (self.name, v)
 290     for op in self.operations:
 291       #yield prefix+u'  %s [%s] %s' % (op.operation, op.condition and op.condition.str(parents=True), op.expression)
 292       yield prefix + u'  ' + unicode(op)
 293
 294 class ConfigExpression(object):
 295   """
 296   String expression with some unexpanded config variables. Used in variable operations and conditions.
 297   Expression is given as a list of unicode strings and ConfigVar variables to be expanded.
 298   """
 299   def __init__(self, exprlist, original = u'<unknown>'):
 300     self.exprlist = exprlist
 301     # Original defining string
 302     self.original = original
 303     # Replace strings with unicode
 304     for i in range(len(self.exprlist)):
 305       e = self.exprlist[i]
 306       if isinstance(e, types.StringTypes):
 307         if not isinstance(e, unicode):
 308           self.exprlist[i] = unicode(e, 'ascii')
 309   def variables(self):
 310     "Return an iterator of variables user in the expression"
 311     return itertools.ifilter(lambda e: isinstance(e, ConfigVar), self.exprlist)
 312   def __str__(self):
 313     return self.original
 314   def evaluate(self, depth):
 315     check_depth(depth)
 316     "Return unicode result of expansion of the variables."
 317     s = []
 318     for e in self.exprlist:
 319       if isinstance(e, ConfigVar):
 320         s.append(e.value(depth+1))
 321       elif isinstance(e, unicode):
 322         s.append(e)
 323       else:
 324         raise ConfigError('Invalid type %s in expression \'%s\'.'%(type(e), self))
 325     return u''.join(s)
 326
 327