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