1 /**
2  * Lazily evaluate static conditions for `static if`, `static assert` and template constraints.
3  *
4  * Copyright:   Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
5  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
6  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/staticcond.d, _staticcond.d)
8  * Documentation:  https://dlang.org/phobos/dmd_staticcond.html
9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/staticcond.d
10  */
11 
12 module dmd.staticcond;
13 
14 import dmd.arraytypes;
15 import dmd.dmodule;
16 import dmd.dscope;
17 import dmd.dsymbol;
18 import dmd.errors;
19 import dmd.expression;
20 import dmd.expressionsem;
21 import dmd.globals;
22 import dmd.identifier;
23 import dmd.mtype;
24 import dmd.root.array;
25 import dmd.root.outbuffer;
26 import dmd.tokens;
27 
28 
29 
30 /********************************************
31  * Semantically analyze and then evaluate a static condition at compile time.
32  * This is special because short circuit operators &&, || and ?: at the top
33  * level are not semantically analyzed if the result of the expression is not
34  * necessary.
35  * Params:
36  *      sc  = instantiating scope
37  *      original = original expression, for error messages
38  *      e =  resulting expression
39  *      errors = set to `true` if errors occurred
40  *      negatives = array to store negative clauses
41  * Returns:
42  *      true if evaluates to true
43  */
44 bool evalStaticCondition(Scope* sc, Expression original, Expression e, out bool errors, Expressions* negatives = null)
45 {
46     if (negatives)
47         negatives.setDim(0);
48 
49     bool impl(Expression e)
50     {
51         if (e.op == TOK.not)
52         {
53             NotExp ne = cast(NotExp)e;
54             return !impl(ne.e1);
55         }
56 
57         if (e.op == TOK.andAnd || e.op == TOK.orOr)
58         {
59             LogicalExp aae = cast(LogicalExp)e;
60             bool result = impl(aae.e1);
61             if (errors)
62                 return false;
63             if (e.op == TOK.andAnd)
64             {
65                 if (!result)
66                     return false;
67             }
68             else
69             {
70                 if (result)
71                     return true;
72             }
73             result = impl(aae.e2);
74             return !errors && result;
75         }
76 
77         if (e.op == TOK.question)
78         {
79             CondExp ce = cast(CondExp)e;
80             bool result = impl(ce.econd);
81             if (errors)
82                 return false;
83             Expression leg = result ? ce.e1 : ce.e2;
84             result = impl(leg);
85             return !errors && result;
86         }
87 
88         Expression before = e;
89         const uint nerrors = global.errors;
90 
91         sc = sc.startCTFE();
92         sc.flags |= SCOPE.condition;
93 
94         e = e.expressionSemantic(sc);
95         e = resolveProperties(sc, e);
96         e = e.toBoolean(sc);
97 
98         sc = sc.endCTFE();
99         e = e.optimize(WANTvalue);
100 
101         if (nerrors != global.errors ||
102             e.op == TOK.error ||
103             e.type.toBasetype() == Type.terror)
104         {
105             errors = true;
106             return false;
107         }
108 
109         e = e.ctfeInterpret();
110 
111         if (e.isBool(true))
112             return true;
113         else if (e.isBool(false))
114         {
115             if (negatives)
116                 negatives.push(before);
117             return false;
118         }
119 
120         e.error("expression `%s` is not constant", e.toChars());
121         errors = true;
122         return false;
123     }
124     return impl(e);
125 }
126 
127 /********************************************
128  * Format a static condition as a tree-like structure, marking failed and
129  * bypassed expressions.
130  * Params:
131  *      original = original expression
132  *      instantiated = instantiated expression
133  *      negatives = array with negative clauses from `instantiated` expression
134  *      full = controls whether it shows the full output or only failed parts
135  *      itemCount = returns the number of written clauses
136  * Returns:
137  *      formatted string or `null` if the expressions were `null`, or if the
138  *      instantiated expression is not based on the original one
139  */
140 const(char)* visualizeStaticCondition(Expression original, Expression instantiated,
141     const Expression[] negatives, bool full, ref uint itemCount)
142 {
143     if (!original || !instantiated || original.loc !is instantiated.loc)
144         return null;
145 
146     OutBuffer buf;
147 
148     if (full)
149         itemCount = visualizeFull(original, instantiated, negatives, buf);
150     else
151         itemCount = visualizeShort(original, instantiated, negatives, buf);
152 
153     return buf.extractChars();
154 }
155 
156 private uint visualizeFull(Expression original, Expression instantiated,
157     const Expression[] negatives, ref OutBuffer buf)
158 {
159     // tree-like structure; traverse and format simultaneously
160     uint count;
161     uint indent;
162 
163     static void printOr(uint indent, ref OutBuffer buf)
164     {
165         buf.reserve(indent * 4 + 8);
166         foreach (i; 0 .. indent)
167             buf.writestring("    ");
168         buf.writestring("    or:\n");
169     }
170 
171     // returns true if satisfied
172     bool impl(Expression orig, Expression e, bool inverted, bool orOperand, bool unreached)
173     {
174         TOK op = orig.op;
175 
176         // lower all 'not' to the bottom
177         // !(A && B) -> !A || !B
178         // !(A || B) -> !A && !B
179         if (inverted)
180         {
181             if (op == TOK.andAnd)
182                 op = TOK.orOr;
183             else if (op == TOK.orOr)
184                 op = TOK.andAnd;
185         }
186 
187         if (op == TOK.not)
188         {
189             NotExp no = cast(NotExp)orig;
190             NotExp ne = cast(NotExp)e;
191             assert(ne);
192             return impl(no.e1, ne.e1, !inverted, orOperand, unreached);
193         }
194         else if (op == TOK.andAnd)
195         {
196             BinExp bo = cast(BinExp)orig;
197             BinExp be = cast(BinExp)e;
198             assert(be);
199             const r1 = impl(bo.e1, be.e1, inverted, false, unreached);
200             const r2 = impl(bo.e2, be.e2, inverted, false, unreached || !r1);
201             return r1 && r2;
202         }
203         else if (op == TOK.orOr)
204         {
205             if (!orOperand) // do not indent A || B || C twice
206                 indent++;
207             BinExp bo = cast(BinExp)orig;
208             BinExp be = cast(BinExp)e;
209             assert(be);
210             const r1 = impl(bo.e1, be.e1, inverted, true, unreached);
211             printOr(indent, buf);
212             const r2 = impl(bo.e2, be.e2, inverted, true, unreached);
213             if (!orOperand)
214                 indent--;
215             return r1 || r2;
216         }
217         else if (op == TOK.question)
218         {
219             CondExp co = cast(CondExp)orig;
220             CondExp ce = cast(CondExp)e;
221             assert(ce);
222             if (!inverted)
223             {
224                 // rewrite (A ? B : C) as (A && B || !A && C)
225                 if (!orOperand)
226                     indent++;
227                 const r1 = impl(co.econd, ce.econd, inverted, false, unreached);
228                 const r2 = impl(co.e1, ce.e1, inverted, false, unreached || !r1);
229                 printOr(indent, buf);
230                 const r3 = impl(co.econd, ce.econd, !inverted, false, unreached);
231                 const r4 = impl(co.e2, ce.e2, inverted, false, unreached || !r3);
232                 if (!orOperand)
233                     indent--;
234                 return r1 && r2 || r3 && r4;
235             }
236             else
237             {
238                 // rewrite !(A ? B : C) as (!A || !B) && (A || !C)
239                 if (!orOperand)
240                     indent++;
241                 const r1 = impl(co.econd, ce.econd, inverted, false, unreached);
242                 printOr(indent, buf);
243                 const r2 = impl(co.e1, ce.e1, inverted, false, unreached);
244                 const r12 = r1 || r2;
245                 const r3 = impl(co.econd, ce.econd, !inverted, false, unreached || !r12);
246                 printOr(indent, buf);
247                 const r4 = impl(co.e2, ce.e2, inverted, false, unreached || !r12);
248                 if (!orOperand)
249                     indent--;
250                 return (r1 || r2) && (r3 || r4);
251             }
252         }
253         else // 'primitive' expression
254         {
255             buf.reserve(indent * 4 + 4);
256             foreach (i; 0 .. indent)
257                 buf.writestring("    ");
258 
259             // find its value; it may be not computed, if there was a short circuit,
260             // but we handle this case with `unreached` flag
261             bool value = true;
262             if (!unreached)
263             {
264                 foreach (fe; negatives)
265                 {
266                     if (fe is e)
267                     {
268                         value = false;
269                         break;
270                     }
271                 }
272             }
273             // write the marks first
274             const satisfied = inverted ? !value : value;
275             if (!satisfied && !unreached)
276                 buf.writestring("  > ");
277             else if (unreached)
278                 buf.writestring("  - ");
279             else
280                 buf.writestring("    ");
281             // then the expression itself
282             if (inverted)
283                 buf.writeByte('!');
284             buf.writestring(orig.toChars);
285             buf.writenl();
286             count++;
287             return satisfied;
288         }
289     }
290 
291     impl(original, instantiated, false, true, false);
292     return count;
293 }
294 
295 private uint visualizeShort(Expression original, Expression instantiated,
296     const Expression[] negatives, ref OutBuffer buf)
297 {
298     // simple list; somewhat similar to long version, so no comments
299     // one difference is that it needs to hold items to display in a stack
300 
301     static struct Item
302     {
303         Expression orig;
304         bool inverted;
305     }
306 
307     Array!Item stack;
308 
309     bool impl(Expression orig, Expression e, bool inverted)
310     {
311         TOK op = orig.op;
312 
313         if (inverted)
314         {
315             if (op == TOK.andAnd)
316                 op = TOK.orOr;
317             else if (op == TOK.orOr)
318                 op = TOK.andAnd;
319         }
320 
321         if (op == TOK.not)
322         {
323             NotExp no = cast(NotExp)orig;
324             NotExp ne = cast(NotExp)e;
325             assert(ne);
326             return impl(no.e1, ne.e1, !inverted);
327         }
328         else if (op == TOK.andAnd)
329         {
330             BinExp bo = cast(BinExp)orig;
331             BinExp be = cast(BinExp)e;
332             assert(be);
333             bool r = impl(bo.e1, be.e1, inverted);
334             r = r && impl(bo.e2, be.e2, inverted);
335             return r;
336         }
337         else if (op == TOK.orOr)
338         {
339             BinExp bo = cast(BinExp)orig;
340             BinExp be = cast(BinExp)e;
341             assert(be);
342             const lbefore = stack.length;
343             bool r = impl(bo.e1, be.e1, inverted);
344             r = r || impl(bo.e2, be.e2, inverted);
345             if (r)
346                 stack.setDim(lbefore); // purge added positive items
347             return r;
348         }
349         else if (op == TOK.question)
350         {
351             CondExp co = cast(CondExp)orig;
352             CondExp ce = cast(CondExp)e;
353             assert(ce);
354             if (!inverted)
355             {
356                 const lbefore = stack.length;
357                 bool a = impl(co.econd, ce.econd, inverted);
358                 a = a && impl(co.e1, ce.e1, inverted);
359                 bool b;
360                 if (!a)
361                 {
362                     b = impl(co.econd, ce.econd, !inverted);
363                     b = b && impl(co.e2, ce.e2, inverted);
364                 }
365                 const r = a || b;
366                 if (r)
367                     stack.setDim(lbefore);
368                 return r;
369             }
370             else
371             {
372                 bool a;
373                 {
374                     const lbefore = stack.length;
375                     a = impl(co.econd, ce.econd, inverted);
376                     a = a || impl(co.e1, ce.e1, inverted);
377                     if (a)
378                         stack.setDim(lbefore);
379                 }
380                 bool b;
381                 if (a)
382                 {
383                     const lbefore = stack.length;
384                     b = impl(co.econd, ce.econd, !inverted);
385                     b = b || impl(co.e2, ce.e2, inverted);
386                     if (b)
387                         stack.setDim(lbefore);
388                 }
389                 return a && b;
390             }
391         }
392         else // 'primitive' expression
393         {
394             bool value = true;
395             foreach (fe; negatives)
396             {
397                 if (fe is e)
398                 {
399                     value = false;
400                     break;
401                 }
402             }
403             const satisfied = inverted ? !value : value;
404             if (!satisfied)
405                 stack.push(Item(orig, inverted));
406             return satisfied;
407         }
408     }
409 
410     impl(original, instantiated, false);
411 
412     foreach (i; 0 .. stack.length)
413     {
414         // write the expression only
415         buf.writestring("       ");
416         if (stack[i].inverted)
417             buf.writeByte('!');
418         buf.writestring(stack[i].orig.toChars);
419         // here with no trailing newline
420         if (i + 1 < stack.length)
421             buf.writenl();
422     }
423     return cast(uint)stack.length;
424 }