5 Lazy conditional string evaluation module for Moe configuration variables.
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).
11 NOTE: If no 'SET' applies, a variable is still undefined even if some 'APPEND' applies. This might change.
13 * Each condition is a formula (tree consisting of 'AND', 'OR', 'NOT' and '==', '!=' between two expressions.
15 * Expression is a list of strings and variables to be expanded.
17 NOTE: All expanded data should be (or is converted to) unicode
20 TODO (OPT): Cleanup of unused undefined variables.
21 TODO (OPT): Better variable name checking (no name '.'-structural prefix of another)
22 TODO (OPT): Implemet "subtree" listing.
25 import types, itertools, re, bisect
27 from moe import MoeError
29 "Allowed depth of recursion - includes ALL recursive calls, so should quite high."
32 "Maximum attained depth of recursion - for debug/testing"
35 "Variable name regexp, dots (separators) must be separated from edges and each other."
36 re_VARNAME = re.compile(r'\A([A-Za-z0-9_-]+\.)*[A-Za-z0-9_-]+\Z')
38 def check_depth(depth):
39 "Helper to check for recursion depth."
41 if depth > c_maxdepth:
42 raise CyclicConfigError('Too deep recursion in config evaluation (cyclic substitution?)')
43 if depth > debug_maxdepth:
44 debug_maxdepth = depth
47 class ConfigError(MoeError):
50 class UndefinedError(ConfigError):
53 class VariableNameError(ConfigError):
56 class VariableFixedError(ConfigError):
59 class CyclicConfigError(ConfigError):
63 class ConfigTree(object):
65 Configuration tree containing all the variables.
67 The variables in `self.variables` are referenced directly by the full name.
73 def lookup(self, key, create = True):
75 Lookup and return a variable.
76 If not found and `create` set, check the name and transparently create a new one.
78 if key not in self.variables:
79 if not re_VARNAME.match(key):
80 raise VariableNameError('Invalid variable identifier %r in config', key)
82 raise UndefinedError('Config variable %r undefined.', key)
83 self.variables[key] = ConfigVar(key)
84 return self.variables[key]
86 def dump(self, prefix=''):
88 Pretty printing of the tree.
89 Returns an iterator of lines (strings).
91 return itertools.chain(*[
92 self.variables[k].dump(prefix) for k in sorted(self.variables.keys())
96 class ConfigElem(object):
98 Base class for cahed config elements - variables and conditions
101 def __init__(self, name):
102 # Full name with separators, definition for conditions
104 # Vars and conditions depending on value of this one
105 self.dependants = set([])
106 # Cached value (may be None in case of evaluation error)
108 self.cached_val = None
110 def invalidate(self, depth=0):
112 Invalidate cached data and invalidate all dependants.
113 Does nothing if not cached.
117 log.debug('invalidating %s', self)
119 for d in self.dependants:
120 d.invalidate(depth + 1)
122 def value(self, depth=0):
123 "Caching helper calling self.evaluate(), returns a value or throws an exception."
126 self.cached_val = self.evaluate(depth=depth+1)
128 if self.cached_val == None:
129 raise UndefinedError("Unable to evaluate %r."%(self.name,))
130 return self.cached_val
136 class ConfigCondition(ConfigElem):
138 Condition using equality and logic operators.
139 Clause is a tuple-tree in the following recursive form:
140 ('AND', c1, c1), ('OR', c1, c2), ('NOT', c1),
141 ('==', e1, e2), ('!=', e1, e2) where e1, e2 are `ConfigExpression`s.
144 def __init__(self, formula, text=None, parent=None):
146 Condition defined by `text` (informative), `formula` as in class definition,
147 `parent` is the parent condition (if any).
150 text = self.formula_string(formula)
151 super(ConfigCondition, self).__init__(text)
152 self.formula = formula
154 # Setup dependencies on used variables (not on the parent condition)
155 for v in self.variables():
156 v.dependants.add(self)
158 self.parent.dependants.add(self)
160 def variables(self, cl=None):
161 "Return an iterator of variables used in formula `cl`"
164 if cl[0] in ['==','!=']:
165 return itertools.chain(cl[1].variables(), cl[2].variables())
166 if cl[0] in ['AND','OR']:
167 return itertools.chain(self.variables(cl[1]), self.variables(cl[2]))
168 return self.variables(cl[1]) # only 'NOT' left
170 def remove_dependencies(self):
171 "Remove self as a dependant from all used variables"
172 for v in self.variables():
173 v.dependants.discard(self)
175 self.parent.dependants.discard(self)
177 def evaluate(self, cl=None, depth=0):
178 """Evaluate formula `cl` (or the entire condition).
179 Partial evaluation for AND and OR. Tests the parent condition first."""
183 if self.parent and not self.parent.value():
185 if cl[0] in ['==','!=']:
186 v = cl[1].evaluate(depth=depth+1) == cl[2].evaluate(depth=depth+1)
187 if cl[0] == '!=': v = not v
189 v1 = self.evaluate(cl=cl[1], depth=depth+1)
192 if cl[0] == 'OR' and v1: return True
193 if cl[0] == 'AND' and not v1: return False
194 return self.evaluate(cl=cl[2], depth=depth+1)
196 def formula_string(self, formula):
197 "Create a string representation of a formula."
198 if formula[0] == 'AND':
199 return itertools.chain(['('], self.formula_string(formula[1]), [' and '], self.formula_string(formula[2]),[')'])
200 elif formula[0] == 'OR':
201 return itertools.chain(['('], self.formula_string(formula[1]), [' or '], self.formula_string(formula[2]),[')'])
202 elif formula[0] == 'NOT':
203 return itertools.chain(['(not '], self.formula_string(formula[1]),[')'])
204 elif formula[0] in ['==', '!=']:
205 return itertools.chain(formula[1], formula[0], formula[2])
206 return iter(['<invalid formula>'])
208 def str(self, parents=False):
209 "Retur the defining expression, if `parents` set, then prefixed with parent conditions."
210 if parents and self.parent:
211 return self.parent.str(parents=True) + u' && ' + self.name
215 return self.str(parents=False)
218 class Operation(object):
219 "Helper class for operation data. Must not be present in more variables or present multiple times."
221 def __init__(self, operation, condition, expression, level=0, source='?'):
222 # operation is currently 'SET' and 'APPEND'
223 self.operation = operation
224 self.condition = condition
225 self.expression = expression
230 return "%s <%d, %s> [%s] %r" % ( {'SET':'=', 'APPEND':'+'}[self.operation], self.level, self.source,
231 (self.condition and self.condition.str(parents=True)) or '', unicode(self.expression))
234 class ConfigVar(ConfigElem):
236 def __init__(self, name):
237 super(ConfigVar, self).__init__(name)
238 # Ordered list of `Operations` (ascending by `level`)
240 # Fixed to value (may be None)
242 self.fixed_val = None
245 "Return a set of variables used in the expressions"
246 return set(sum([ list(op.expression.variables()) for op in self.operations ], []))
250 Fixes the value of the variable. Exception is raised should the variable
251 evaluate to a different value while fixed.
255 self.fixed_val = self.value()
259 "Set the variable to be modifiable again."
262 def value(self, depth=0):
263 "Handle the case when fixed, raise exc. on different evaluation"
264 val = super(ConfigVar,self).value(depth)
265 if self.fixed and self.fixed_val != val:
266 raise VariableFixedError("value of var %s was fixed to %r but evaluated to %r", self.name, self.fixed_val, val)
269 def add_operation(self, operation):
271 Inserts an operation. The operations are sorted by `level` (ascending), new operation goes last among
272 these with the same level.
273 Adds the variable as a dependant of the conditions and variables used in the expressions.
275 # Invalidate cached value
278 pos = bisect.bisect_right([o.level for o in self.operations], operation.level)
279 self.operations.insert(pos, operation)
280 # Create dependencies
281 for v in operation.expression.variables():
282 v.dependants.add(self)
283 if operation.condition:
284 operation.condition.dependants.add(self)
286 def remove_operation(self, operation):
288 Remove the Operation.
289 Also removes the variable as dependant from all conditions and variables used in this
290 operation that are no longer used.
292 # Invalidate cached value
294 # Remove the operation
295 self.operations.remove(operation)
296 # Remove dependencies on variables unused in other operations
297 vs = self.variables()
298 for v in operation.expression.variables():
300 v.dependants.remove(self)
301 # Remove the dependency on the conditions (if not used in another operation)
302 if operation.condition and operation.condition not in [op.condition for op in self.operations]:
303 operation.condition.dependants.remove(self)
305 def evaluate(self, depth=0):
307 Find the last 'SET' operation that applies and return the result of concatenating with all
308 subsequent applicable 'APPEND' operations. The result is the same as performing the operations
310 NOTE: undefined if some 'APPEND' apply but no 'SET' applies.
313 log.debug('evaluating var %r', self.name)
314 # List of strings to be concatenated
316 # Scan for last applicable expression - try each starting from the end, concatenate extensions
317 for i in range(len(self.operations)-1, -1, -1):
318 op = self.operations[i]
319 # Check the guarding condition
320 if (not op.condition) or op.condition.value(depth+1):
321 val.insert(0, op.expression.evaluate(depth=depth+1))
322 if op.operation == 'SET':
326 def dump(self, prefix=''):
328 Pretty printing of the variable. Includes all operations.
329 Returns iterator of lines (unicode strings).
331 # Try to evaluate the variable, but avoid undefined exceptions
334 v = self.value(depth=0)
337 yield prefix+u'%s = %r' % (self.name, v)
338 for op in self.operations:
339 #yield prefix+u' %s [%s] %s' % (op.operation, op.condition and op.condition.str(parents=True), op.expression)
340 yield prefix + u' ' + unicode(op)
343 class ConfigExpression(object):
345 String expression with some unexpanded config variables. Used in variable operations and conditions.
346 Expression is given as a list of unicode strings and ConfigVar variables to be expanded.
349 def __init__(self, exprlist, original = u'<unknown>'):
350 self.exprlist = list(exprlist)
351 # Original defining string
352 self.original = original
353 # Replace strings with unicode
354 for i in range(len(self.exprlist)):
356 if isinstance(e, types.StringTypes):
357 if not isinstance(e, unicode):
358 self.exprlist[i] = unicode(e, 'ascii')
361 "Return an iterator of variables user in the expression"
362 return itertools.ifilter(lambda e: isinstance(e, ConfigVar), self.exprlist)
367 def evaluate(self, depth):
369 "Return unicode result of expansion of the variables."
371 for e in self.exprlist:
372 if isinstance(e, ConfigVar):
373 s.append(e.value(depth+1))
374 elif isinstance(e, unicode):
377 raise ConfigError('Invalid type %s in expression \'%s\'.'%(type(e), self))