1 : #include "nixexpr.hh"
2 : #include "derivations.hh"
3 : #include "util.hh"
4 : #include "aterm.hh"
5 :
6 : #include "nixexpr-ast.hh"
7 : #include "nixexpr-ast.cc"
8 :
9 : #include <cstdlib>
10 :
11 :
12 : namespace nix {
13 :
14 :
15 20 : string showPos(ATerm pos)
16 : {
17 : ATerm path;
18 : int line, column;
19 20 : if (matchNoPos(pos)) return "undefined position";
20 18 : if (!matchPos(pos, path, line, column))
21 0 : throw badTerm("position expected", pos);
22 18 : return (format("`%1%', line %2%") % aterm2String(path) % line).str();
23 : }
24 :
25 :
26 6400 : ATerm bottomupRewrite(TermFun & f, ATerm e)
27 : {
28 6400 : checkInterrupt();
29 :
30 6400 : if (ATgetType(e) == AT_APPL) {
31 5071 : AFun fun = ATgetAFun(e);
32 5071 : int arity = ATgetArity(fun);
33 5071 : ATerm args[arity];
34 :
35 10182 : for (int i = 0; i < arity; ++i)
36 5111 : args[i] = bottomupRewrite(f, ATgetArgument(e, i));
37 :
38 5071 : e = (ATerm) ATmakeApplArray(fun, args);
39 : }
40 :
41 1329 : else if (ATgetType(e) == AT_LIST) {
42 1235 : ATermList in = (ATermList) e;
43 1235 : ATermList out = ATempty;
44 :
45 2329 : for (ATermIterator i(in); i; ++i)
46 1094 : out = ATinsert(out, bottomupRewrite(f, *i));
47 :
48 1235 : e = (ATerm) ATreverse(out);
49 : }
50 :
51 6400 : return f(e);
52 : }
53 :
54 :
55 1667 : void queryAllAttrs(Expr e, ATermMap & attrs, bool withPos)
56 : {
57 : ATermList bnds;
58 1667 : if (!matchAttrs(e, bnds))
59 0 : throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
60 :
61 11254 : for (ATermIterator i(bnds); i; ++i) {
62 : ATerm name;
63 : Expr e;
64 : ATerm pos;
65 9587 : if (!matchBind(*i, name, e, pos)) abort(); /* can't happen */
66 9587 : attrs.set(name, withPos ? makeAttrRHS(e, pos) : e);
67 : }
68 1667 : }
69 :
70 :
71 182 : Expr queryAttr(Expr e, const string & name)
72 : {
73 : ATerm dummy;
74 182 : return queryAttr(e, name, dummy);
75 : }
76 :
77 :
78 1868 : Expr queryAttr(Expr e, const string & name, ATerm & pos)
79 : {
80 : ATermList bnds;
81 1868 : if (!matchAttrs(e, bnds))
82 0 : throw TypeError(format("value is %1% while an attribute set was expected") % showType(e));
83 :
84 4511 : for (ATermIterator i(bnds); i; ++i) {
85 : ATerm name2, pos2;
86 : Expr e;
87 4510 : if (!matchBind(*i, name2, e, pos2))
88 0 : abort(); /* can't happen */
89 4510 : if (aterm2String(name2) == name) {
90 1867 : pos = pos2;
91 1867 : return e;
92 : }
93 : }
94 :
95 1 : return 0;
96 : }
97 :
98 :
99 1004 : Expr makeAttrs(const ATermMap & attrs)
100 : {
101 1004 : ATermList bnds = ATempty;
102 8175 : for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) {
103 : Expr e;
104 : ATerm pos;
105 7171 : if (!matchAttrRHS(i->value, e, pos))
106 0 : abort(); /* can't happen */
107 7171 : bnds = ATinsert(bnds, makeBind(i->key, e, pos));
108 : }
109 1004 : return makeAttrs(bnds);
110 : }
111 :
112 :
113 2101 : static void varsBoundByPattern(ATermMap & map, Pattern pat)
114 : {
115 : ATerm name;
116 : ATermList formals;
117 : Pattern pat1, pat2;
118 : ATermBool ellipsis;
119 : /* Use makeRemoved() so that it can be used directly in
120 : substitute(). */
121 2101 : if (matchVarPat(pat, name))
122 1975 : map.set(name, makeRemoved());
123 126 : else if (matchAttrsPat(pat, formals, ellipsis)) {
124 418 : for (ATermIterator i(formals); i; ++i) {
125 : ATerm d1;
126 303 : if (!matchFormal(*i, name, d1)) abort();
127 303 : map.set(name, makeRemoved());
128 : }
129 : }
130 11 : else if (matchAtPat(pat, pat1, pat2)) {
131 11 : varsBoundByPattern(map, pat1);
132 11 : varsBoundByPattern(map, pat2);
133 : }
134 0 : else abort();
135 2101 : }
136 :
137 :
138 147836 : Expr substitute(const Substitution & subs, Expr e)
139 : {
140 147836 : checkInterrupt();
141 :
142 : //if (subs.size() == 0) return e;
143 :
144 : ATerm name, pos, e2;
145 :
146 : /* As an optimisation, don't substitute in subterms known to be
147 : closed. */
148 147836 : if (matchClosed(e, e2)) return e;
149 :
150 136109 : if (matchVar(e, name)) {
151 14311 : Expr sub = subs.lookup(name);
152 14311 : if (sub == makeRemoved()) sub = 0;
153 : Expr wrapped;
154 : /* Add a "closed" wrapper around terms that aren't already
155 : closed. The check is necessary to prevent repeated
156 : wrapping, e.g., closed(closed(closed(...))), which kills
157 : caching. */
158 14311 : return sub ? (matchClosed(sub, wrapped) ? sub : makeClosed(sub)) : e;
159 : }
160 :
161 : /* In case of a function, filter out all variables bound by this
162 : function. */
163 : Pattern pat;
164 : ATerm body;
165 121798 : if (matchFunction(e, pat, body, pos)) {
166 1573 : ATermMap map(16);
167 1573 : varsBoundByPattern(map, pat);
168 1573 : Substitution subs2(&subs, &map);
169 : return makeFunction(
170 : (Pattern) substitute(subs2, (Expr) pat),
171 1573 : substitute(subs2, body), pos);
172 : }
173 :
174 : /* Idem for a mutually recursive attribute set. */
175 : ATermList rbnds, nrbnds;
176 120225 : if (matchRec(e, rbnds, nrbnds)) {
177 568 : ATermMap map(ATgetLength(rbnds) + ATgetLength(nrbnds));
178 4102 : for (ATermIterator i(rbnds); i; ++i)
179 1483 : if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
180 0 : else abort(); /* can't happen */
181 1142 : for (ATermIterator i(nrbnds); i; ++i)
182 3 : if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved());
183 0 : else abort(); /* can't happen */
184 : return makeRec(
185 : (ATermList) substitute(Substitution(&subs, &map), (ATerm) rbnds),
186 568 : (ATermList) substitute(subs, (ATerm) nrbnds));
187 : }
188 :
189 119657 : if (ATgetType(e) == AT_APPL) {
190 87759 : AFun fun = ATgetAFun(e);
191 87759 : int arity = ATgetArity(fun);
192 87759 : ATerm args[arity];
193 87759 : bool changed = false;
194 :
195 215825 : for (int i = 0; i < arity; ++i) {
196 128066 : ATerm arg = ATgetArgument(e, i);
197 128066 : args[i] = substitute(subs, arg);
198 128066 : if (args[i] != arg) changed = true;
199 : }
200 :
201 87759 : return changed ? (ATerm) ATmakeApplArray(fun, args) : e;
202 : }
203 :
204 31898 : if (ATgetType(e) == AT_LIST) {
205 13101 : unsigned int len = ATgetLength((ATermList) e);
206 13101 : ATerm es[len];
207 13101 : ATermIterator i((ATermList) e);
208 25449 : for (unsigned int j = 0; i; ++i, ++j)
209 12348 : es[j] = substitute(subs, *i);
210 13101 : ATermList out = ATempty;
211 25449 : for (unsigned int j = len; j; --j)
212 12348 : out = ATinsert(out, es[j - 1]);
213 13101 : return (ATerm) out;
214 : }
215 :
216 18797 : return e;
217 : }
218 :
219 :
220 : /* We use memoisation to prevent exponential complexity on heavily
221 : shared ATerms (remember, an ATerm is a graph, not a tree!). Note
222 : that using an STL set is fine here wrt to ATerm garbage collection
223 : since all the ATerms in the set are already reachable from
224 : somewhere else. */
225 27958 : static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
226 : {
227 27958 : if (done.find(e) != done.end()) return;
228 20900 : done.insert(e);
229 :
230 : ATerm name, pos, value;
231 : ATerm with, body;
232 : ATermList rbnds, nrbnds;
233 : Pattern pat;
234 :
235 : /* Closed terms don't have free variables, so we don't have to
236 : check by definition. */
237 20900 : if (matchClosed(e, value)) return;
238 :
239 20727 : else if (matchVar(e, name)) {
240 1277 : if (!defs.get(name))
241 : throw EvalError(format("undefined variable `%1%'")
242 2 : % aterm2String(name));
243 : }
244 :
245 19450 : else if (matchFunction(e, pat, body, pos)) {
246 506 : ATermMap defs2(defs);
247 506 : varsBoundByPattern(defs2, pat);
248 506 : set<Expr> done2;
249 506 : checkVarDefs2(done2, defs2, pat);
250 506 : checkVarDefs2(done2, defs2, body);
251 : }
252 :
253 18944 : else if (matchRec(e, rbnds, nrbnds)) {
254 140 : checkVarDefs2(done, defs, (ATerm) nrbnds);
255 140 : ATermMap defs2(defs);
256 701 : for (ATermIterator i(rbnds); i; ++i) {
257 561 : if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
258 561 : defs2.set(name, (ATerm) ATempty);
259 : }
260 142 : for (ATermIterator i(nrbnds); i; ++i) {
261 2 : if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
262 2 : defs2.set(name, (ATerm) ATempty);
263 : }
264 140 : set<Expr> done2;
265 140 : checkVarDefs2(done2, defs2, (ATerm) rbnds);
266 : }
267 :
268 18804 : else if (matchWith(e, with, body, pos)) {
269 : /* We can't check the body without evaluating the definitions
270 : (which is an arbitrary expression), so we don't do that
271 : here but only when actually evaluating the `with'. */
272 16 : checkVarDefs2(done, defs, with);
273 : }
274 :
275 18788 : else if (ATgetType(e) == AT_APPL) {
276 14669 : int arity = ATgetArity(ATgetAFun(e));
277 37946 : for (int i = 0; i < arity; ++i)
278 23282 : checkVarDefs2(done, defs, ATgetArgument(e, i));
279 : }
280 :
281 4119 : else if (ATgetType(e) == AT_LIST)
282 4571 : for (ATermIterator i((ATermList) e); i; ++i)
283 3168 : checkVarDefs2(done, defs, *i);
284 : }
285 :
286 :
287 200 : void checkVarDefs(const ATermMap & defs, Expr e)
288 : {
289 200 : set<Expr> done;
290 202 : checkVarDefs2(done, defs, e);
291 198 : }
292 :
293 :
294 : struct Canonicalise : TermFun
295 166 : {
296 2239 : ATerm operator () (ATerm e)
297 : {
298 : /* Remove position info. */
299 : ATerm path;
300 : int line, column;
301 2239 : if (matchPos(e, path, line, column))
302 37 : return makeNoPos();
303 :
304 : /* Sort attribute sets. */
305 : ATermList _;
306 2202 : if (matchAttrs(e, _)) {
307 88 : ATermMap attrs;
308 88 : queryAllAttrs(e, attrs);
309 88 : StringSet names;
310 708 : for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i)
311 266 : names.insert(aterm2String(i->key));
312 :
313 88 : ATermList attrs2 = ATempty;
314 354 : for (StringSet::reverse_iterator i = names.rbegin(); i != names.rend(); ++i)
315 : attrs2 = ATinsert(attrs2,
316 266 : makeBind(toATerm(*i), attrs.get(toATerm(*i)), makeNoPos()));
317 :
318 88 : return makeAttrs(attrs2);
319 : }
320 :
321 2114 : return e;
322 : }
323 : };
324 :
325 :
326 83 : Expr canonicaliseExpr(Expr e)
327 : {
328 83 : Canonicalise canonicalise;
329 83 : return bottomupRewrite(canonicalise, e);
330 : }
331 :
332 :
333 1359 : Expr makeBool(bool b)
334 : {
335 1359 : return b ? eTrue : eFalse;
336 : }
337 :
338 :
339 3941 : bool matchStr(Expr e, string & s, PathSet & context)
340 : {
341 : ATermList l;
342 : ATerm s_;
343 :
344 3941 : if (!matchStr(e, s_, l)) return false;
345 :
346 3282 : s = aterm2String(s_);
347 :
348 7306 : for (ATermIterator i(l); i; ++i)
349 371 : context.insert(aterm2String(*i));
350 :
351 3282 : return true;
352 : }
353 :
354 :
355 1259 : Expr makeStr(const string & s, const PathSet & context)
356 : {
357 1259 : return makeStr(toATerm(s), toATermList(context));
358 : }
359 :
360 :
361 0 : string showType(Expr e)
362 : {
363 : ATerm t1, t2;
364 : ATermList l1;
365 : ATermBlob b1;
366 : int i1;
367 : Pattern p1;
368 0 : if (matchStr(e, t1, l1)) return "a string";
369 0 : if (matchPath(e, t1)) return "a path";
370 0 : if (matchNull(e)) return "null";
371 0 : if (matchInt(e, i1)) return "an integer";
372 0 : if (matchBool(e, t1)) return "a boolean";
373 0 : if (matchFunction(e, p1, t1, t2)) return "a function";
374 0 : if (matchAttrs(e, l1)) return "an attribute set";
375 0 : if (matchList(e, l1)) return "a list";
376 0 : if (matchPrimOp(e, i1, b1, l1)) return "a partially applied built-in function";
377 0 : return "an unknown type";
378 : }
379 :
380 :
381 0 : string showValue(Expr e)
382 : {
383 0 : PathSet context;
384 0 : string s;
385 : ATerm s2;
386 : int i;
387 0 : if (matchStr(e, s, context)) {
388 0 : string u;
389 0 : for (string::iterator i = s.begin(); i != s.end(); ++i)
390 0 : if (*i == '\"' || *i == '\\') u += "\\" + *i;
391 0 : else if (*i == '\n') u += "\\n";
392 0 : else if (*i == '\r') u += "\\r";
393 0 : else if (*i == '\t') u += "\\t";
394 0 : else u += *i;
395 0 : return "\"" + u + "\"";
396 : }
397 0 : if (matchPath(e, s2)) return aterm2String(s2);
398 0 : if (matchNull(e)) return "null";
399 0 : if (matchInt(e, i)) return (format("%1%") % i).str();
400 0 : if (e == eTrue) return "true";
401 0 : if (e == eFalse) return "false";
402 : /* !!! incomplete */
403 0 : return "<unknown>";
404 : }
405 :
406 0 :
407 478 : }
|
