gcc/d/dmd/lambdacomp.d

   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 }