@@ -15,6 +15,10 @@ import sys
__all__ = [ 'KconfigParserError', 'KconfigData', 'KconfigParser' ]
+def debug_print(*args):
+ #print ' '.join(str(x) for x in args)
+ pass
+
# -------------------------------------------
# KconfigData implements the Kconfig semantics. For now it can only
# detect undefined symbols, i.e. symbols that were referenced in
@@ -34,6 +38,12 @@ class KconfigData:
def __invert__(self):
return KconfigData.NOT(self)
+ # Abstract methods
+ def add_edges_to(self, var):
+ pass
+ def evaluate(self):
+ assert False
+
class AND(Expr):
def __init__(self, lhs, rhs):
self.lhs = lhs
@@ -41,6 +51,12 @@ class KconfigData:
def __str__(self):
return "(%s && %s)" % (self.lhs, self.rhs)
+ def add_edges_to(self, var):
+ self.lhs.add_edges_to(var)
+ self.rhs.add_edges_to(var)
+ def evaluate(self):
+ return self.lhs.evaluate() and self.rhs.evaluate()
+
class OR(Expr):
def __init__(self, lhs, rhs):
self.lhs = lhs
@@ -48,22 +64,62 @@ class KconfigData:
def __str__(self):
return "(%s || %s)" % (self.lhs, self.rhs)
+ def add_edges_to(self, var):
+ self.lhs.add_edges_to(var)
+ self.rhs.add_edges_to(var)
+ def evaluate(self):
+ return self.lhs.evaluate() or self.rhs.evaluate()
+
class NOT(Expr):
def __init__(self, lhs):
self.lhs = lhs
def __str__(self):
return "!%s" % (self.lhs)
+ def add_edges_to(self, var):
+ self.lhs.add_edges_to(var)
+ def evaluate(self):
+ return not self.lhs.evaluate()
+
class Var(Expr):
def __init__(self, name):
self.name = name
self.value = None
+ self.outgoing = set()
def __str__(self):
return self.name
+ def has_value(self):
+ return not (self.value is None)
+ def set_value(self, val):
+ if self.has_value() and self.value != val:
+ raise Exception('contradiction between clauses when setting %s' % self)
+ debug_print("=> %s is now %s" % (self.name, val))
+ self.value = val
+
+ # depth first search of the dependency graph
+ def dfs(self, visited, f):
+ if self in visited:
+ return
+ visited.add(self)
+ for v in self.outgoing:
+ v.dfs(visited, f)
+ f(self)
+
+ def add_edges_to(self, var):
+ self.outgoing.add(var)
+ def evaluate(self):
+ if not self.has_value():
+ raise Exception('cycle found including %s' % self)
+ return self.value
+
class Clause:
def __init__(self, dest):
self.dest = dest
+ def priority(self):
+ return 0
+ def process(self):
+ pass
class AssignmentClause(Clause):
def __init__(self, dest, value):
@@ -72,11 +128,16 @@ class KconfigData:
def __str__(self):
return "%s=%s" % (self.dest, 'y' if self.value else 'n')
+ def process(self):
+ self.dest.set_value(self.value)
+
class DefaultClause(Clause):
def __init__(self, dest, value, cond=None):
KconfigData.Clause.__init__(self, dest)
self.value = value
self.cond = cond
+ if not (self.cond is None):
+ self.cond.add_edges_to(self.dest)
def __str__(self):
value = 'y' if self.value else 'n'
if self.cond is None:
@@ -84,20 +145,38 @@ class KconfigData:
else:
return "config %s default %s if %s" % (self.dest, value, self.cond)
+ def priority(self):
+ # Defaults are processed just before leaving the variable
+ return -1
+ def process(self):
+ if not self.dest.has_value() and \
+ (self.cond is None or self.cond.evaluate()):
+ self.dest.set_value(self.value)
+
class DependsOnClause(Clause):
def __init__(self, dest, expr):
KconfigData.Clause.__init__(self, dest)
self.expr = expr
+ self.expr.add_edges_to(self.dest)
def __str__(self):
return "config %s depends on %s" % (self.dest, self.expr)
+ def process(self):
+ if not self.expr.evaluate():
+ self.dest.set_value(False)
+
class SelectClause(Clause):
def __init__(self, dest, cond):
KconfigData.Clause.__init__(self, dest)
self.cond = cond
+ self.cond.add_edges_to(self.dest)
def __str__(self):
return "select %s if %s" % (self.dest, self.cond)
+ def process(self):
+ if self.cond.evaluate():
+ self.dest.set_value(True)
+
def __init__(self):
self.previously_included = []
self.incl_info = None
@@ -115,6 +194,50 @@ class KconfigData:
undef = True
return undef
+ def compute_config(self):
+ if self.check_undefined():
+ raise Exception(parser, "there were undefined symbols")
+ return None
+
+ debug_print("Input:")
+ for clause in self.clauses:
+ debug_print(clause)
+
+ debug_print("\nDependency graph:")
+ for i in self.referenced_vars:
+ debug_print(i, "->", [str(x) for x in self.referenced_vars[i].outgoing])
+
+ # The reverse of the depth-first order is the topological sort
+ dfo = dict()
+ visited = set()
+ debug_print("\n")
+ def visit_fn(var):
+ debug_print(var, "has DFS number", len(dfo))
+ dfo[var] = len(dfo)
+
+ for name in self.referenced_vars:
+ v = self.referenced_vars[name]
+ v.dfs(visited, visit_fn)
+
+ # Put higher DFS numbers and higher priorities first. This
+ # places the clauses in topological order and places defaults
+ # after assignments and dependencies.
+ self.clauses.sort(key=lambda x: (-dfo[x.dest], -x.priority()))
+
+ debug_print("\nSorted clauses:")
+ for clause in self.clauses:
+ debug_print(clause)
+ clause.process()
+
+ debug_print("")
+ values = dict()
+ for name in self.referenced_vars:
+ debug_print("Evaluating", name)
+ v = self.referenced_vars[name]
+ values[name] = v.evaluate()
+
+ return values
+
# semantic actions -------------
def do_declaration(self, var):
@@ -188,9 +311,6 @@ class KconfigParser:
data = KconfigData()
parser = KconfigParser(data)
parser.parse_file(fp)
- if data.check_undefined():
- raise KconfigParserError(parser, "there were undefined symbols")
-
return data
def __init__(self, data):
@@ -499,5 +619,4 @@ class KconfigParser:
if __name__ == '__main__':
fname = len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test'
data = KconfigParser.parse(open(fname, 'r'))
- for i in data.clauses:
- print i
+ print data.compute_config()