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