1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
class ParseError(Exception):
pass
class AstOp(object):
def __init__(self, op, sub):
self.op = op
self.sub = sub
def __repr__(self):
if len(self.sub) == 1:
return self.op + str(self.sub[0])
return "(" + (" " + self.op + " ").join([str(x) for x in self.sub]) + ")"
class AstSym(object):
def __init__(self, name):
assert type(name) is type("")
self.name = name
def __repr__(self):
return self.name
Arity = { "!": 1, "&&": 2, "||": 2 }
Precedence = { "!": 3, "&&": 2, "||": 1 }
Tokens = list(Arity.keys()) + ["(", ")"]
# return (token, rest), or (None, "") if nothing left
def read_tok(expr):
expr = expr.strip()
for t in Tokens:
if expr.startswith(t):
return (t, expr[len(t):])
if expr == "":
return (None, "")
sym = ""
while len(expr) and ((expr[0].lower() >= 'a' and expr[0].lower() <= 'z') or
(expr[0] >= '0' and expr[0] <= '9') or
(expr[0] in ["_", "-", "."])):
sym += expr[0]
expr = expr[1:]
if len(sym):
return sym, expr
raise ParseError("unknown token in '%s'" % expr)
def parse_expr(expr):
opstack = []
outstack = []
def out(sym):
if sym in Arity:
sub = []
for i in range(Arity[sym]):
if len(outstack) == 0:
raise ParseError("missing operator argument")
sub.insert(0, outstack.pop())
outstack.append(AstOp(sym, sub))
elif sym == "(":
raise ParseError("missing closing ')'")
elif not isinstance(sym, AstSym):
raise ParseError("bogus symbol '%s'" % sym)
else:
outstack.append(sym)
while True:
tok, expr = read_tok(expr)
if tok is None:
break
if tok in Arity:
while len(opstack) and opstack[-1] != '(' and \
Precedence[opstack[-1]] > Precedence[tok]:
out(opstack.pop())
opstack.append(tok)
elif tok == "(":
opstack.append(tok)
elif tok == ")":
while True:
if not len(opstack):
raise ParseError("missing '(' for ')'")
sym = opstack.pop()
if sym == "(":
break
out(sym)
else:
out(AstSym(tok)) # Assume a terminal
while len(opstack):
out(opstack.pop())
if len(outstack) != 1:
raise ParseError("empty expression or extra symbols (%s)" % outstack)
return outstack.pop()
def convert_dnf(ast):
# no nested ! (negation normal form)
def simplify_negation(ast):
if isinstance(ast, AstOp):
if ast.op == "!":
sub = ast.sub[0]
if isinstance(sub, AstOp):
if sub.op == "!":
return sub.sub[0]
elif sub.op in ["&&", "||"]:
sub.op = "||" if sub.op == "&&" else "&&"
sub.sub = [AstOp("!", [x]) for x in sub.sub]
return simplify_negation(sub)
else:
ast.sub = [simplify_negation(x) for x in ast.sub]
return ast
# a && (b && c) => a && b && c
def flatten(ast):
if isinstance(ast, AstOp):
can_flatten = ast.op in ["&&", "||"]
nsub = []
for sub in ast.sub:
sub = flatten(sub)
if isinstance(sub, AstOp) and sub.op == ast.op and can_flatten:
nsub.extend(sub.sub)
else:
nsub.append(sub)
ast.sub = nsub
if len(ast.sub) == 1 and can_flatten:
return ast.sub[0]
return ast
# a && (b || c) && d => (a && d && b) || (a && d && c)
def redist(ast):
def recombine(a, stuff):
return AstOp("||", [AstOp("&&", [a, n]) for n in stuff])
if isinstance(ast, AstOp):
ast.sub = [flatten(redist(x)) for x in ast.sub]
if ast.op == "&&":
for sub in ast.sub:
if isinstance(sub, AstOp) and sub.op == "||":
if len(ast.sub) == 1:
return redist(sub)
other = None
for n in ast.sub:
if n is not sub:
if other is None:
other = n
else:
other = flatten(AstOp("&&", [other, n]))
return flatten(redist(recombine(other, sub.sub)))
return ast
return redist(flatten(simplify_negation(ast)))
# Returns (success_as_bool, failure_reason_as_string)
def check_dependency_expr(expr, deps):
ast = parse_expr(expr)
def eval_ast(ast):
if isinstance(ast, AstSym):
return ast.name in deps
elif isinstance(ast, AstOp):
vals = [eval_ast(x) for x in ast.sub]
if ast.op == "&&":
return vals[0] and vals[1]
elif ast.op == "||":
return vals[0] or vals[1]
elif ast.op == "!":
return not vals[0]
assert False
if eval_ast(ast):
return True, None
# Now the same thing again, but more complicated, and informing what is
# missing.
ast = convert_dnf(ast)
# ast now is a or-combined list of and-combined deps. Each dep can have a
# negation (marking a conflict). Each case of and-combined deps is a way
# to satisfy the deps expression. Instead of dumping full information,
# distinguish the following cases, and only mention the one that applies,
# in order:
# 1. the first missing dep of a case that has missing deps only
# 2. the first conflicting dep at all
def get_sub_list(node, op):
if isinstance(node, AstOp) and node.op == op:
return node.sub
else:
return [node]
conflict_dep = None
missing_dep = None
for group in get_sub_list(ast, "||"):
group_conflict = None
group_missing_dep = None
for elem in get_sub_list(group, "&&"):
neg = False
if isinstance(elem, AstOp) and elem.op == "!":
neg = True
elem = elem.sub[0]
if not isinstance(elem, AstSym):
continue # broken DNF?
name = elem.name
present = name in deps
if (not present) and (not neg) and (group_missing_dep is None):
group_missing_dep = name
if present and neg and (group_conflict is None):
group_conflict = name
if (missing_dep is None) and (group_conflict is None):
missing_dep = group_missing_dep
if conflict_dep is None:
conflict_dep = group_conflict
reason = "unknown"
if missing_dep is not None:
reason = "%s not found" % (missing_dep)
elif conflict_dep is not None:
reason = "%s found" % (conflict_dep)
return False, reason
|
