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