dmd.lambdacomp source code

1 /**
2  * Implements the serialization of a lambda function.
3  *
4  * The serializationis computed by visiting the abstract syntax subtree of the given lambda function.
5  * The serialization is a string which contains the type of the parameters and the string
6  * represantation of the lambda expression.
7  *
8  * Copyright:   Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved
9  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
10  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
11  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/lamdbacomp.d, _lambdacomp.d)
12  * Documentation:  https://dlang.org/phobos/dmd_lambdacomp.html
13  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/lambdacomp.d
14  */
15 
16 module dmd.lambdacomp;
17 
18 import core.stdc.stdio;
19 import core.stdc..string;
20 
21 import dmd.declaration;
22 import dmd.denum;
23 import dmd.dsymbol;
24 import dmd.dtemplate;
25 import dmd.expression;
26 import dmd.func;
27 import dmd.dmangle;
28 import dmd.mtype;
29 import dmd.root.outbuffer;
30 import dmd.root.rmem;
31 import dmd.root.stringtable;
32 import dmd.dscope;
33 import dmd.statement;
34 import dmd.tokens;
35 import dmd.visitor;
36 
37 enum LOG = false;
38 
39 /**
40  * The type of the visited expression.
41  */
42 private enum ExpType
43 {
44     None,
45     EnumDecl,
46     Arg
47 }
48 
49 /**
50  * Compares 2 lambda functions described by their serialization.
51  *
52  * Params:
53  *  l1 = first lambda to be compared
54  *  l2 = second lambda to be compared
55  *  sc = the scope where the lambdas are compared
56  *
57  * Returns:
58  *  `true` if the 2 lambda functions are equal, `false` otherwise
59  */
60 bool isSameFuncLiteral(FuncLiteralDeclaration l1, FuncLiteralDeclaration l2, Scope* sc)
61 {
62     bool result;
63     if (auto ser1 = getSerialization(l1, sc))
64     {
65         //printf("l1 serialization: %.*s\n", cast(int)ser1.length, &ser1[0]);
66         if (auto ser2 = getSerialization(l2, sc))
67         {
68             //printf("l2 serialization: %.*s\n", cast(int)ser2.length, &ser2[0]);
69             if (ser1 == ser2)
70                 result = true;
71             mem.xfree(cast(void*)ser2.ptr);
72         }
73         mem.xfree(cast(void*)ser1.ptr);
74     }
75     return result;
76 }
77 
78 /**
79  * Computes the string representation of a
80  * lambda function described by the subtree starting from a
81  * $(REF dmd, func, FuncLiteralDeclaration).
82  *
83  * Limitations: only IntegerExps, Enums and function
84  * arguments are supported in the lambda function body. The
85  * arguments may be of any type (basic types, user defined types),
86  * except template instantiations. If a function call, a local
87  * variable or a template instance is encountered, the
88  * serialization is dropped and the function is considered
89  * uncomparable.
90  *
91  * Params:
92  *  fld = the starting AST node for the lambda function
93  *  sc = the scope in which the lambda function is located
94  *
95  * Returns:
96  *  The serialization of `fld` allocated with mem.
97  */
98 private string getSerialization(FuncLiteralDeclaration fld, Scope* sc)
99 {
100     scope serVisitor = new SerializeVisitor(fld.parent._scope);
101     fld.accept(serVisitor);
102     const len = serVisitor.buf.length;
103     if (len == 0)
104         return null;
105 
106     return cast(string)serVisitor.buf.extractSlice();
107 }
108 
109 private extern (C++) class SerializeVisitor : SemanticTimeTransitiveVisitor
110 {
111 private:
112     StringTable!(const(char)[]) arg_hash;
113     Scope* sc;
114     ExpType et;
115     Dsymbol d;
116 
117 public:
118     OutBuffer buf;
119     alias visit = SemanticTimeTransitiveVisitor.visit;
120 
121     this(Scope* sc)
122     {
123         this.sc = sc;
124     }
125 
126     /**
127      * Entrypoint of the SerializeVisitor.
128      *
129      * Params:
130      *     fld = the lambda function for which the serialization is computed
131      */
132     override void visit(FuncLiteralDeclaration fld)
133     {
134         assert(fld.type.ty != Terror);
135         static if (LOG)
136             printf("FuncLiteralDeclaration: %s\n", fld.toChars());
137 
138         TypeFunction tf = cast(TypeFunction)fld.type;
139         uint dim = cast(uint)Parameter.dim(tf.parameterList.parameters);
140         // Start the serialization by printing the number of
141         // arguments the lambda has.
142         buf.printf("%d:", dim);
143 
144         arg_hash._init(dim + 1);
145         // For each argument
146         foreach (i; 0 .. dim)
147         {
148             auto fparam = tf.parameterList[i];
149             if (fparam.ident !is null)
150             {
151                 // the variable name is introduced into a hashtable
152                 // where the key is the user defined name and the
153                 // value is the cannonically name (arg0, arg1 ...)
154                 auto key = fparam.ident.toString();
155                 OutBuffer value;
156                 value.writestring("arg");
157                 value.print(i);
158                 arg_hash.insert(key, value.extractSlice());
159                 // and the type of the variable is serialized.
160                 fparam.accept(this);
161             }
162         }
163 
164         // Now the function body can be serialized.
165         ReturnStatement rs = fld.fbody.endsWithReturnStatement();
166         if (rs && rs.exp)
167         {
168             rs.exp.accept(this);
169         }
170         else
171         {
172             buf.setsize(0);
173         }
174     }
175 
176     override void visit(DotIdExp exp)
177     {
178         static if (LOG)
179             printf("DotIdExp: %s\n", exp.toChars());
180         if (buf.length == 0)
181             return;
182 
183         // First we need to see what kind of expression e1 is.
184         // It might an enum member (enum.value)  or the field of
185         // an argument (argX.value) if the argument is an aggregate
186         // type. This is reported through the et variable.
187         exp.e1.accept(this);
188         if (buf.length == 0)
189             return;
190 
191         if (et == ExpType.EnumDecl)
192         {
193             Dsymbol s = d.search(exp.loc, exp.ident);
194             if (s)
195             {
196                 if (auto em = s.isEnumMember())
197                 {
198                     em.value.accept(this);
199                 }
200                 et = ExpType.None;
201                 d = null;
202             }
203         }
204 
205         else if (et == ExpType.Arg)
206         {
207             buf.setsize(buf.length -1);
208             buf.writeByte('.');
209             buf.writestring(exp.ident.toString());
210             buf.writeByte('_');
211         }
212     }
213 
214     bool checkArgument(const(char)* id)
215     {
216         // The identifier may be an argument
217         auto stringtable_value = arg_hash.lookup(id, strlen(id));
218         if (stringtable_value)
219         {
220             // In which case we need to update the serialization accordingly
221             const(char)[] gen_id = stringtable_value.value;
222             buf.write(gen_id);
223             buf.writeByte('_');
224             et = ExpType.Arg;
225             return true;
226         }
227         return false;
228     }
229 
230     override void visit(IdentifierExp exp)
231     {
232         static if (LOG)
233             printf("IdentifierExp: %s\n", exp.toChars());
234 
235         if (buf.length == 0)
236             return;
237 
238         auto id = exp.ident.toChars();
239 
240         // If it's not an argument
241         if (!checkArgument(id))
242         {
243             // we must check what the identifier expression is.
244             Dsymbol scopesym;
245             Dsymbol s = sc.search(exp.loc, exp.ident, &scopesym);
246             if (s)
247             {
248                 auto v = s.isVarDeclaration();
249                 // If it's a VarDeclaration, it must be a manifest constant
250                 if (v && (v.storage_class & STC.manifest))
251                 {
252                     v.getConstInitializer.accept(this);
253                 }
254                 else if (auto em = s.isEnumDeclaration())
255                 {
256                     d = em;
257                     et = ExpType.EnumDecl;
258                 }
259                 else if (auto fd = s.isFuncDeclaration())
260                 {
261                     writeMangledName(fd);
262                 }
263                 // For anything else, the function is deemed uncomparable
264                 else
265                 {
266                     buf.setsize(0);
267                 }
268             }
269             // If it's an unknown symbol, consider the function incomparable
270             else
271             {
272                 buf.setsize(0);
273             }
274         }
275     }
276 
277     override void visit(DotVarExp exp)
278     {
279         static if (LOG)
280             printf("DotVarExp: %s, var: %s, e1: %s\n", exp.toChars(),
281                     exp.var.toChars(), exp.e1.toChars());
282 
283         exp.e1.accept(this);
284         if (buf.length == 0)
285             return;
286 
287         buf.setsize(buf.length -1);
288         buf.writeByte('.');
289         buf.writestring(exp.var.toChars());
290         buf.writeByte('_');
291     }
292 
293     override void visit(VarExp exp)
294     {
295         static if (LOG)
296             printf("VarExp: %s, var: %s\n", exp.toChars(), exp.var.toChars());
297 
298         if (buf.length == 0)
299             return;
300 
301         auto id = exp.var.ident.toChars();
302         if (!checkArgument(id))
303         {
304             buf.setsize(0);
305         }
306     }
307 
308     // serialize function calls
309     override void visit(CallExp exp)
310     {
311         static if (LOG)
312             printf("CallExp: %s\n", exp.toChars());
313 
314         if (buf.length == 0)
315             return;
316 
317         if (!exp.f)
318         {
319             exp.e1.accept(this);
320         }
321         else
322         {
323             writeMangledName(exp.f);
324         }
325 
326         buf.writeByte('(');
327         foreach (arg; *(exp.arguments))
328         {
329             arg.accept(this);
330         }
331         buf.writeByte(')');
332     }
333 
334     override void visit(UnaExp exp)
335     {
336         if (buf.length == 0)
337             return;
338 
339         buf.writeByte('(');
340         buf.writestring(Token.toString(exp.op));
341         exp.e1.accept(this);
342         if (buf.length != 0)
343             buf.writestring(")_");
344     }
345 
346     override void visit(IntegerExp exp)
347     {
348         if (buf.length == 0)
349             return;
350 
351         buf.print(exp.toInteger());
352         buf.writeByte('_');
353     }
354 
355     override void visit(RealExp exp)
356     {
357         if (buf.length == 0)
358             return;
359 
360         buf.writestring(exp.toChars());
361         buf.writeByte('_');
362     }
363 
364     override void visit(BinExp exp)
365     {
366         static if (LOG)
367             printf("BinExp: %s\n", exp.toChars());
368 
369         if (buf.length == 0)
370             return;
371 
372         buf.writeByte('(');
373         buf.writestring(Token.toChars(exp.op));
374 
375         exp.e1.accept(this);
376         if (buf.length == 0)
377             return;
378 
379         exp.e2.accept(this);
380         if (buf.length == 0)
381             return;
382 
383         buf.writeByte(')');
384     }
385 
386     override void visit(TypeBasic t)
387     {
388         buf.writestring(t.dstring);
389         buf.writeByte('_');
390     }
391 
392     void writeMangledName(Dsymbol s)
393     {
394         if (s)
395         {
396             OutBuffer mangledName;
397             mangleToBuffer(s, &mangledName);
398             buf.writestring(mangledName[]);
399             buf.writeByte('_');
400         }
401         else
402             buf.setsize(0);
403     }
404 
405     private bool checkTemplateInstance(T)(T t)
406         if (is(T == TypeStruct) || is(T == TypeClass))
407     {
408         if (t.sym.parent && t.sym.parent.isTemplateInstance())
409         {
410             buf.setsize(0);
411             return true;
412         }
413         return false;
414     }
415 
416     override void visit(TypeStruct t)
417     {
418         static if (LOG)
419             printf("TypeStruct: %s\n", t.toChars);
420 
421         if (!checkTemplateInstance!TypeStruct(t))
422             writeMangledName(t.sym);
423     }
424 
425     override void visit(TypeClass t)
426     {
427         static if (LOG)
428             printf("TypeClass: %s\n", t.toChars());
429 
430         if (!checkTemplateInstance!TypeClass(t))
431             writeMangledName(t.sym);
432     }
433 
434     override void visit(Parameter p)
435     {
436         if (p.type.ty == Tident
437             && (cast(TypeIdentifier)p.type).ident.toString().length > 3
438             && strncmp((cast(TypeIdentifier)p.type).ident.toChars(), "__T", 3) == 0)
439         {
440             buf.writestring("none_");
441         }
442         else
443             visitType(p.type);
444     }
445 
446     override void visit(StructLiteralExp e) {
447         static if (LOG)
448             printf("StructLiteralExp: %s\n", e.toChars);
449 
450         auto ty = cast(TypeStruct)e.stype;
451         if (ty)
452         {
453             writeMangledName(ty.sym);
454             auto dim = e.elements.dim;
455             foreach (i; 0..dim)
456             {
457                 auto elem = (*e.elements)[i];
458                 if (elem)
459                     elem.accept(this);
460                 else
461                     buf.writestring("null_");
462             }
463         }
464         else
465             buf.setsize(0);
466     }
467 
468     override void visit(ArrayLiteralExp) { buf.setsize(0); }
469     override void visit(AssocArrayLiteralExp) { buf.setsize(0); }
470     override void visit(CompileExp) { buf.setsize(0); }
471     override void visit(ComplexExp) { buf.setsize(0); }
472     override void visit(DeclarationExp) { buf.setsize(0); }
473     override void visit(DefaultInitExp) { buf.setsize(0); }
474     override void visit(DsymbolExp) { buf.setsize(0); }
475     override void visit(ErrorExp) { buf.setsize(0); }
476     override void visit(FuncExp) { buf.setsize(0); }
477     override void visit(HaltExp) { buf.setsize(0); }
478     override void visit(IntervalExp) { buf.setsize(0); }
479     override void visit(IsExp) { buf.setsize(0); }
480     override void visit(NewAnonClassExp) { buf.setsize(0); }
481     override void visit(NewExp) { buf.setsize(0); }
482     override void visit(NullExp) { buf.setsize(0); }
483     override void visit(ObjcClassReferenceExp) { buf.setsize(0); }
484     override void visit(OverExp) { buf.setsize(0); }
485     override void visit(ScopeExp) { buf.setsize(0); }
486     override void visit(StringExp) { buf.setsize(0); }
487     override void visit(SymbolExp) { buf.setsize(0); }
488     override void visit(TemplateExp) { buf.setsize(0); }
489     override void visit(ThisExp) { buf.setsize(0); }
490     override void visit(TraitsExp) { buf.setsize(0); }
491     override void visit(TupleExp) { buf.setsize(0); }
492     override void visit(TypeExp) { buf.setsize(0); }
493     override void visit(TypeidExp) { buf.setsize(0); }
494     override void visit(VoidInitExp) { buf.setsize(0); }
495 }