From nobody Mon Feb 9 17:58:58 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; dkim=fail; spf=pass (zoho.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com Return-Path: Received: from lists.gnu.org (209.51.188.17 [209.51.188.17]) by mx.zohomail.com with SMTPS id 1548412704263479.9262292712714; Fri, 25 Jan 2019 02:38:24 -0800 (PST) Received: from localhost ([127.0.0.1]:41685 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gmysF-0006Ql-4Z for importer@patchew.org; Fri, 25 Jan 2019 05:38:11 -0500 Received: from eggs.gnu.org ([209.51.188.92]:58240) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gmyOr-0007hc-P7 for qemu-devel@nongnu.org; Fri, 25 Jan 2019 05:07:53 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gmyOn-0001u7-64 for qemu-devel@nongnu.org; Fri, 25 Jan 2019 05:07:49 -0500 Received: from mail-wm1-x32d.google.com ([2a00:1450:4864:20::32d]:36406) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gmyOm-0001sc-Rv for qemu-devel@nongnu.org; Fri, 25 Jan 2019 05:07:45 -0500 Received: by mail-wm1-x32d.google.com with SMTP id p6so6035689wmc.1 for ; Fri, 25 Jan 2019 02:07:44 -0800 (PST) Received: from 640k.lan ([93.56.166.5]) by smtp.gmail.com with ESMTPSA id p4sm88048455wrs.74.2019.01.25.02.07.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 25 Jan 2019 02:07:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=P7EUL1dtqlvCawn9iblER8oQehVwWW5sdULoxFBNhiQ=; b=HddvZnxaBv9W/v9wpP9TlQLlaYyb94869i77Q5leJDA5dBBJL/XQLJljv5581whxmI 56dYfjxjE7EkFiMTs/Xmy3VFBjv6JilxxzAk9fQjw/NPV6GfeWn1DgtCqxYGTTR3Z5tt QAxydRCv4/tG+/fexLd+gv4uDyg0GGOUzXloekY1Wj9lzFWL1vWeqIAkaWR3aJbnE8/V JX3+sbtyizlBRqx54mltZI/kB0eZXoiGTNICToswIAwwHlTJcdfgb5dQ1zk76zLsc8ob gTJaEmYc1A8foXrA4fhdc6hwko4xijbpmzvQsvhYoJ3SeSGqypsZRw8+Rhm5Dso56J3m 9zFg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=P7EUL1dtqlvCawn9iblER8oQehVwWW5sdULoxFBNhiQ=; b=QaVGLbLh3OOmmkM/WsEbzwT7wH2ClD2BSthJfs7X/2BhyxWz0yhFitvuzY7EwNN+Jv RUrqO1Xf6CoNZY1SRCsP4GxxUFmqTZyTSM4u7cgV02VhHcyQ7Woyo8/eTRI8nEsAw1eu 2hDNAbtnIjqVyrD5eaLj0prQmVG/GRi/orov0ONp+3ygZNxxk0VEh95VCnjVnjnhhpSg TLyTJi5xLkvdGd0y1L/8jJTtdD064tec6iYgW5P+Rqkcitxhs974YxPyHcRhtLjxiBnB N7+Bn8v4g2Nag0JndgTcaDK3QsxWSo9lHjFerbuocWx9Nw5e8b0gHWvLx9E64mJPV08Q EEoQ== X-Gm-Message-State: AJcUukc8cb4QVdw0A7HGHKW0BlUc+XHVCUGLqtS/xWPNi43s1aUX8/aD ZPMzp83xFp+oKfFLwIFcaEq3YejR X-Google-Smtp-Source: ALg8bN671bBTZzv0JbdePsGcnSy2j62C+Me9lgff/eHPWgXZyyuB7v+VKJ0OmL6r8B70Lsjzq13big== X-Received: by 2002:a1c:7dd7:: with SMTP id y206mr6239853wmc.50.1548410863341; Fri, 25 Jan 2019 02:07:43 -0800 (PST) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Fri, 25 Jan 2019 11:06:49 +0100 Message-Id: <1548410831-19553-31-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1548410831-19553-1-git-send-email-pbonzini@redhat.com> References: <1548410831-19553-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::32d Subject: [Qemu-devel] [PATCH 30/52] minikconfig: add semantic analysis X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: yang.zhong@intel.com, thuth@redhat.com Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: fail (Header signature does not verify) Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" There are three parts in the semantic analysis: 1) evaluating expressions. This is done as a simple visit of the Expr nodes. 2) ordering clauses. This is done by constructing a graph of variables. There is an edge from X to Y if Y depends on X, if X selects Y, or if X appears in a conditional selection of Y; in other words, if the value of X can affect the value of Y. Each clause has a "destination" variable whose value can be affected by the clause, and clauses will be processed according to a topological sorting of their destination variables. Defaults are processed after all other clauses with the same destination. 3) deriving the value of the variables. This is done by processing the clauses in the topological order provided by the previous step. A "depends on" clause will force a variable to False, a "select" clause will force a variable to True, an assignment will force a variable to its RHS. A default will set a variable to its RHS if it has not been set before. Because all variables have a default, after visiting all clauses all variables will have been set. Signed-off-by: Paolo Bonzini Message-Id: <20190123065618.3520-25-yang.zhong@intel.com> Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 136 +++++++++++++++++++++++++++++++++++++++++++++++= +--- 1 file changed, 130 insertions(+), 6 deletions(-) diff --git a/scripts/minikconf.py b/scripts/minikconf.py index eeecac1..7fd1438 100644 --- a/scripts/minikconf.py +++ b/scripts/minikconf.py @@ -16,6 +16,10 @@ import sys =20 __all__ =3D [ 'KconfigParserError', 'KconfigData', 'KconfigParser' ] =20 +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 @@ -35,6 +39,12 @@ class KconfigData: def __invert__(self): return KconfigData.NOT(self) =20 + # Abstract methods + def add_edges_to(self, var): + pass + def evaluate(self): + assert False + class AND(Expr): def __init__(self, lhs, rhs): self.lhs =3D lhs @@ -42,6 +52,12 @@ class KconfigData: def __str__(self): return "(%s && %s)" % (self.lhs, self.rhs) =20 + 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 =3D lhs @@ -49,35 +65,85 @@ class KconfigData: def __str__(self): return "(%s || %s)" % (self.lhs, self.rhs) =20 + 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 =3D lhs def __str__(self): return "!%s" % (self.lhs) =20 + 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 =3D name self.value =3D None + self.outgoing =3D set() + self.clauses_for_var =3D list() def __str__(self): return self.name =20 + def has_value(self): + return not (self.value is None) + def set_value(self, val, clause): + self.clauses_for_var.append(clause) + if self.has_value() and self.value !=3D val: + print("The following clauses were found for " + self.name) + for i in self.clauses_for_var: + print(" " + str(i), file=3Dsys.stderr) + raise Exception('contradiction between clauses when settin= g %s' % self) + debug_print("=3D> %s is now %s" % (self.name, val)) + self.value =3D 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 =3D dest + def priority(self): + return 0 + def process(self): + pass =20 class AssignmentClause(Clause): def __init__(self, dest, value): KconfigData.Clause.__init__(self, dest) self.value =3D value def __str__(self): - return "%s=3D%s" % (self.dest, 'y' if self.value else 'n') + return "CONFIG_%s=3D%s" % (self.dest, 'y' if self.value else '= n') + + def process(self): + self.dest.set_value(self.value, self) =20 class DefaultClause(Clause): def __init__(self, dest, value, cond=3DNone): KconfigData.Clause.__init__(self, dest) self.value =3D value self.cond =3D cond + if not (self.cond is None): + self.cond.add_edges_to(self.dest) def __str__(self): value =3D 'y' if self.value else 'n' if self.cond is None: @@ -85,20 +151,38 @@ class KconfigData: else: return "config %s default %s if %s" % (self.dest, value, s= elf.cond) =20 + 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, self) + class DependsOnClause(Clause): def __init__(self, dest, expr): KconfigData.Clause.__init__(self, dest) self.expr =3D expr + self.expr.add_edges_to(self.dest) def __str__(self): return "config %s depends on %s" % (self.dest, self.expr) =20 + def process(self): + if not self.expr.evaluate(): + self.dest.set_value(False, self) + class SelectClause(Clause): def __init__(self, dest, cond): KconfigData.Clause.__init__(self, dest) self.cond =3D cond + self.cond.add_edges_to(self.dest) def __str__(self): return "select %s if %s" % (self.dest, self.cond) =20 + def process(self): + if self.cond.evaluate(): + self.dest.set_value(True, self) + def __init__(self): self.previously_included =3D [] self.incl_info =3D None @@ -116,6 +200,50 @@ class KconfigData: undef =3D True return undef =20 + 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 =3D dict() + visited =3D set() + debug_print("\n") + def visit_fn(var): + debug_print(var, "has DFS number", len(dfo)) + dfo[var] =3D len(dfo) + + for name in self.referenced_vars: + v =3D 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=3Dlambda x: (-dfo[x.dest], -x.priority())) + + debug_print("\nSorted clauses:") + for clause in self.clauses: + debug_print(clause) + clause.process() + + debug_print("") + values =3D dict() + for name in self.referenced_vars: + debug_print("Evaluating", name) + v =3D self.referenced_vars[name] + values[name] =3D v.evaluate() + + return values + # semantic actions ------------- =20 def do_declaration(self, var): @@ -190,9 +318,6 @@ class KconfigParser: data =3D KconfigData() parser =3D KconfigParser(data) parser.parse_file(fp) - if data.check_undefined(): - raise KconfigParserError(parser, "there were undefined symbols= ") - return data =20 def __init__(self, data): @@ -501,5 +626,4 @@ class KconfigParser: if __name__ =3D=3D '__main__': fname =3D len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test' data =3D KconfigParser.parse(open(fname, 'r')) - for i in data.clauses: - print i + print data.compute_config() --=20 1.8.3.1