t/moe/config.py

   1 """
   2 Lazy conditional string evaluation module for Moe configuration variables.
   3
   4 * Each variable has ordered list of operations (definitions), each defining operation either
   5   assigns (SET) or appends (APPEND) value of an expression to the variable. Each operation may be guarded by condition(s).
   6
   7 * Each condition is a formula (tree consisting of 'AND', 'OR', 'NOT' and '==', '!=' between two expressions.
   8
   9 * Expression is a list of strings and variables to be expanded.
  10
  11 .. note:: If no 'SET' applies, a variable is still undefined even if some 'APPEND' applies. This might change.
  12 .. note:: All expanded data should be (or is converted to) unicode
  13 .. todo:: (OPT) Cleanup of unused undefined variables.
  14 .. todo:: (OPT) Better variable name checking (no name '.'-structural prefix of another)
  15 .. todo:: (OPT) Implemet "subtree" listing.
  16 """
  17
  18 import types, itertools, re, bisect
  19 import logging as log
  20
  21 from moe import MoeError
  22
  23
  24 "Allowed depth of recursion - includes ALL recursive calls, so should quite high."
  25 c_maxdepth = 256
  26
  27 "Maximum attained depth of recursion - for debug/testing"
  28 debug_maxdepth = 0
  29
  30 "Variable name regexp, dots (separators) must be separated from edges and each other."
  31 re_VARNAME = re.compile(r'\A([A-Za-z0-9_-]+\.)*[A-Za-z0-9_-]+\Z')
  32
  33
  34 def check_depth(depth):
  35   "Helper to check for recursion depth."
  36   global debug_maxdepth
  37   if depth > c_maxdepth:
  38     raise CyclicConfigError('Too deep recursion in config evaluation (cyclic substitution?)')
  39   if depth > debug_maxdepth:
  40     debug_maxdepth = depth
  41
  42
  43 class ConfigError(MoeError):
  44   pass
  45
  46 class UndefinedError(ConfigError):
  47   pass
  48
  49 class VariableNameError(ConfigError):
  50   pass
  51
  52 class VariableFixedError(ConfigError):
  53   pass
  54
  55 class CyclicConfigError(ConfigError):
  56   pass
  57
  58
  59 class ConfigTree(object):
  60   """
  61   Configuration tree containing all the variables.
  62
  63   The variables in `self.variables` are referenced directly by the full name.
  64   """
  65
  66   def __init__(self):
  67     self.variables = {}
  68
  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
  82   def __getitem__(self, key):
  83     """
  84     Return the value of an existing variable.
  85     """
  86     return self.lookup(key, create=False).value()
  87
  88   def dump(self, prefix=''):
  89     """
  90     Pretty printing of the tree.
  91     Returns an iterator of lines (strings).
  92     """
  93     return itertools.chain(*[
  94       self.variables[k].dump(prefix) for k in sorted(self.variables.keys())
  95       ])
  96
  97   def fix(self, keys):
  98     "Fix value of variable or list of variables. Fixing undefined variable raises `UndefinedError`."
  99     if isinstance(keys, types.StringTypes):
 100       keys = [keys]
 101     for key in keys:
 102       self.lookup(key, create=True).fix()
 103
 104   def remove(self, parsed):
 105     """Given a list [(varname, `Operation`)] as returned by `parse` or `parse_file`,
 106     removes the operations from the respective variables config tree.
 107     Variables/operations not present int the tree raise ValueError.
 108     """
 109     for vname, o in parsed:
 110       v = self.lookup(vname, create = True)
 111       v.remove_operation(o)
 112
 113   def parse(self, s, source=None, level=0):
 114     """Parse `s` (stream/string) into the tree, see `moe.confparser.ConfigParser` for details.
 115     Returns list of parset operations: [(varname, `Operation`)]"""
 116     import moe.config_parser
 117     p = moe.config_parser.ConfigParser(s, self, source=source, level=level)
 118     return p.parse()
 119
 120   def parse_file(self, filename, desc=None, level=0):
 121     """Parse an utf-8 file into the tree, see `moe.confparser.ConfigParser` for details.
 122     Names the source "`filename` <`desc`>". """
 123     with open(filename, 'rt') as f:
 124       if desc:
 125         filename += " <" + desc + ">"
 126       return self.parse(f, source=filename, level=level)
 127
 128
 129 class ConfigElem(object):
 130   """
 131   Base class for cahed config elements - variables and conditions
 132   """
 133
 134   def __init__(self, name):
 135     # Full name with separators, definition for conditions
 136     self.name = name
 137     # Vars and conditions depending on value of this one
 138     self.dependants = set([])
 139     # Cached value (may be None in case of evaluation error)
 140     self.cached = False
 141     self.cached_val = None
 142
 143   def invalidate(self, depth=0):
 144     """
 145     Invalidate cached data and invalidate all dependants.
 146     Does nothing if not cached.
 147     """
 148     check_depth(depth)
 149     if self.cached:
 150       log.debug('invalidating %s', self)
 151       self.cached = False
 152       for d in self.dependants:
 153         d.invalidate(depth + 1)
 154
 155   def value(self, depth=0):
 156     "Caching helper calling self.evaluate(), returns a value or throws an exception."
 157     check_depth(depth)
 158     if not self.cached:
 159       self.cached_val = self.evaluate(depth=depth+1)
 160       self.cached = True
 161     if self.cached_val == None:
 162       raise UndefinedError("Unable to evaluate %r."%(self.name,))
 163     return self.cached_val
 164
 165   def __str__(self):
 166     return self.name
 167
 168
 169 class ConfigCondition(ConfigElem):
 170   """
 171   Condition using equality and logic operators.
 172   Clause is a tuple-tree in the following recursive form::
 173
 174     ('AND', c1, c1), ('OR', c1, c2), ('NOT', c1), ('==', e1, e2), ('!=', e1, e2)
 175
 176   where e1, e2 are `ConfigExpression`, c1, c2, `ConfigCondition`.
 177   """
 178
 179   def __init__(self, formula, text=None, parent=None):
 180     """
 181     Condition defined by `text` (informative), `formula` as in class definition,
 182     `parent` is the parent condition (if any).
 183     """
 184     if not text:
 185       text = self.formula_string(formula)
 186     super(ConfigCondition, self).__init__(text)
 187     self.formula = formula
 188     self.parent = parent
 189     # Setup dependencies on used variables (not on the parent condition)
 190     for v in self.variables():
 191       v.dependants.add(self)
 192     if self.parent:
 193       self.parent.dependants.add(self)
 194
 195   def variables(self, cl=None):
 196     "Return an iterator of variables used in formula `cl`"
 197     if not cl:
 198       cl = self.formula
 199     if cl[0] in ['==','!=']:
 200       return itertools.chain(cl[1].variables(), cl[2].variables())
 201     if cl[0] in ['AND','OR']:
 202       return itertools.chain(self.variables(cl[1]), self.variables(cl[2]))
 203     return self.variables(cl[1]) # only 'NOT' left
 204
 205   def remove_dependencies(self):
 206     "Remove self as a dependant from all used variables"
 207     for v in self.variables():
 208       v.dependants.discard(self)
 209     if self.parent:
 210       self.parent.dependants.discard(self)
 211
 212   def evaluate(self, cl=None, depth=0):
 213     """Evaluate formula `cl` (or the entire condition).
 214     Partial evaluation for AND and OR. Tests the parent condition first."""
 215     check_depth(depth)
 216     if not cl:
 217       cl = self.formula
 218     if self.parent and not self.parent.value():
 219       return False
 220     if cl[0] in ['==','!=']:
 221       v = cl[1].evaluate(depth=depth+1) == cl[2].evaluate(depth=depth+1)
 222       if cl[0] == '!=': v = not v
 223       return v
 224     v1 = self.evaluate(cl=cl[1], depth=depth+1)
 225     if cl[0] == 'NOT':
 226       return not v1
 227     if cl[0] == 'OR' and v1: return True
 228     if cl[0] == 'AND' and not v1: return False
 229     return self.evaluate(cl=cl[2], depth=depth+1)
 230
 231   def formula_string(self, formula):
 232     "Create a string representation of a formula."
 233     if formula[0] == 'AND':
 234       return itertools.chain(['('], self.formula_string(formula[1]), [' and '], self.formula_string(formula[2]),[')'])
 235     elif formula[0] == 'OR':
 236       return itertools.chain(['('], self.formula_string(formula[1]), [' or '], self.formula_string(formula[2]),[')'])
 237     elif formula[0] == 'NOT':
 238       return itertools.chain(['(not '], self.formula_string(formula[1]),[')'])
 239     elif formula[0] in ['==', '!=']:
 240       return itertools.chain(formula[1], formula[0], formula[2])
 241     return iter(['<invalid formula>'])
 242
 243   def str(self, parents=False):
 244     "Retur the defining expression, if `parents` set, then prefixed with parent conditions."
 245     if parents and self.parent:
 246       return self.parent.str(parents=True) + u' && ' + self.name
 247     return self.name
 248
 249   def __str__(self):
 250     return self.str(parents=False)
 251
 252
 253 class Operation(object):
 254   "Helper class for operation data. Must not be present in more variables or present multiple times."
 255
 256   def __init__(self, operation, condition, expression, level=0, source='?'):
 257     # operation is currently 'SET' and 'APPEND'
 258     self.operation = operation
 259     self.condition = condition
 260     self.expression = expression
 261     self.level = level
 262     self.source = source
 263
 264   def __str__(self):
 265     return "%s <%d, %s> [%s] %r" % ( {'SET':'=', 'APPEND':'+'}[self.operation], self.level, self.source,
 266       (self.condition and self.condition.str(parents=True)) or '', unicode(self.expression))
 267
 268
 269 class ConfigVar(ConfigElem):
 270
 271   def __init__(self, name):
 272     super(ConfigVar, self).__init__(name)
 273     # Ordered list of `Operations` (ascending by `level`)
 274     self.operations = []
 275     # Fixed to value (may be None)
 276     self.fixed = False
 277     self.fixed_val = None
 278
 279   def variables(self):
 280     "Return a set of variables used in the expressions"
 281     if not self.operations:
 282       return set([])
 283     return set.union(*[ op.expression.variables() for op in self.operations ])
 284
 285   def fix(self):
 286     """
 287     Fixes the value of the variable. Exception is raised should the variable
 288     evaluate to a different value while fixed.
 289     """
 290     if self.fixed:
 291       return
 292     self.fixed_val = self.value()
 293     self.fixed = True
 294
 295   def unfix(self):
 296     "Make the variable modifiable again."
 297     self.fixed = False
 298
 299   def value(self, depth=0):
 300     "Handle the case when fixed, raise exc. on different evaluation"
 301     val = super(ConfigVar,self).value(depth)
 302     if self.fixed and self.fixed_val != val:
 303       raise VariableFixedError("value of var %r was fixed to %r but evaluated to %r", self.name, self.fixed_val, val)
 304     return val
 305
 306   def add_operation(self, operation):
 307     """
 308     Inserts an operation. The operations are sorted by `level` (ascending), new operation goes last among
 309     these with the same level.
 310     Adds the variable as a dependant of the conditions and variables used in the expressions.
 311     """
 312     # Invalidate cached value
 313     self.invalidate()
 314     # Add the operation
 315     pos = bisect.bisect_right([o.level for o in self.operations], operation.level)
 316     self.operations.insert(pos, operation)
 317     # Create dependencies
 318     for v in operation.expression.variables():
 319       v.dependants.add(self)
 320     if operation.condition:
 321       operation.condition.dependants.add(self)
 322
 323   def remove_operation(self, operation):
 324     """
 325     Remove the Operation.
 326     Also removes the variable as dependant from all conditions and variables used in this
 327     operation that are no longer used.
 328     """
 329     # Invalidate cached value
 330     self.invalidate()
 331     # Remove the operation
 332     self.operations.remove(operation)
 333     # Remove dependencies on variables unused in other defining operations
 334     vs = self.variables()
 335     for v in operation.expression.variables():
 336       if v not in vs:
 337         v.dependants.remove(self)
 338     # Remove the dependency on the conditions (if not used in another operation)
 339     if operation.condition and operation.condition not in [op.condition for op in self.operations]:
 340       operation.condition.dependants.remove(self)
 341
 342   def evaluate(self, depth=0):
 343     """
 344     Find the last 'SET' operation that applies and return the result of concatenating with all
 345     subsequent applicable 'APPEND' operations. The result is the same as performing the operations
 346     first-to-last.
 347     NOTE: undefined if some 'APPEND' apply but no 'SET' applies.
 348     """
 349     check_depth(depth)
 350     log.debug('evaluating var %r', self.name)
 351     # List of strings to be concatenated
 352     val = []
 353     # Scan for last applicable expression - try each starting from the end, concatenate extensions
 354     for i in range(len(self.operations)-1, -1, -1):
 355       op = self.operations[i]
 356       # Check the guarding condition
 357       if (not op.condition) or op.condition.value(depth+1):
 358         val.insert(0, op.expression.evaluate(depth=depth+1))
 359         if op.operation == 'SET':
 360           return u''.join(val)
 361     return None
 362
 363   def dump(self, prefix=''):
 364     """
 365     Pretty printing of the variable. Includes all operations.
 366     Returns iterator of lines (unicode strings).
 367     """
 368     # Try to evaluate the variable, but avoid undefined exceptions
 369     v = None
 370     try:
 371       v = self.value(depth=0)
 372     except ConfigError:
 373       pass
 374     yield prefix+u'%s = %r' % (self.name, v)
 375     for op in self.operations:
 376       #yield prefix+u'  %s [%s] %s' % (op.operation, op.condition and op.condition.str(parents=True), op.expression)
 377       yield prefix + u'  ' + unicode(op)
 378
 379
 380 class ConfigExpression(object):
 381   """
 382   String expression with some unexpanded config variables. Used in variable operations and conditions.
 383   Expression is given as a list of unicode strings and ConfigVar variables to be expanded.
 384   """
 385
 386   def __init__(self, exprlist, original = u'<unknown>'):
 387     self.exprlist = list(exprlist)
 388     # Original defining string
 389     self.original = original
 390     # Replace strings with unicode
 391     for i in range(len(self.exprlist)):
 392       e = self.exprlist[i]
 393       if isinstance(e, types.StringTypes):
 394         if not isinstance(e, unicode):
 395           self.exprlist[i] = unicode(e, 'ascii')
 396
 397   def variables(self):
 398     "Return a set of variables used in the expression"
 399     return set([e for e in self.exprlist if isinstance(e, ConfigVar)])
 400
 401   def __str__(self):
 402     return self.original
 403
 404   def evaluate(self, depth):
 405     check_depth(depth)
 406     "Return unicode result of expansion of the variables."
 407     s = []
 408     for e in self.exprlist:
 409       if isinstance(e, ConfigVar):
 410         s.append(e.value(depth+1))
 411       elif isinstance(e, unicode):
 412         s.append(e)
 413       else:
 414         raise ConfigError('Invalid type %s in expression \'%s\'.'%(type(e), self))
 415     return u''.join(s)
 416
 417