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