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-2021 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 const dim = cast(uint) tf.parameterList.length; 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, fparam; tf.parameterList) 147 { 148 if (fparam.ident !is null) 149 { 150 // the variable name is introduced into a hashtable 151 // where the key is the user defined name and the 152 // value is the cannonically name (arg0, arg1 ...) 153 auto key = fparam.ident.toString(); 154 OutBuffer value; 155 value.writestring("arg"); 156 value.print(i); 157 arg_hash.insert(key, value.extractSlice()); 158 // and the type of the variable is serialized. 159 fparam.accept(this); 160 } 161 } 162 163 // Now the function body can be serialized. 164 ReturnStatement rs = fld.fbody.endsWithReturnStatement(); 165 if (rs && rs.exp) 166 { 167 rs.exp.accept(this); 168 } 169 else 170 { 171 buf.setsize(0); 172 } 173 } 174 175 override void visit(DotIdExp exp) 176 { 177 static if (LOG) 178 printf("DotIdExp: %s\n", exp.toChars()); 179 if (buf.length == 0) 180 return; 181 182 // First we need to see what kind of expression e1 is. 183 // It might an enum member (enum.value) or the field of 184 // an argument (argX.value) if the argument is an aggregate 185 // type. This is reported through the et variable. 186 exp.e1.accept(this); 187 if (buf.length == 0) 188 return; 189 190 if (et == ExpType.EnumDecl) 191 { 192 Dsymbol s = d.search(exp.loc, exp.ident); 193 if (s) 194 { 195 if (auto em = s.isEnumMember()) 196 { 197 em.value.accept(this); 198 } 199 et = ExpType.None; 200 d = null; 201 } 202 } 203 204 else if (et == ExpType.Arg) 205 { 206 buf.setsize(buf.length -1); 207 buf.writeByte('.'); 208 buf.writestring(exp.ident.toString()); 209 buf.writeByte('_'); 210 } 211 } 212 213 bool checkArgument(const(char)* id) 214 { 215 // The identifier may be an argument 216 auto stringtable_value = arg_hash.lookup(id, strlen(id)); 217 if (stringtable_value) 218 { 219 // In which case we need to update the serialization accordingly 220 const(char)[] gen_id = stringtable_value.value; 221 buf.write(gen_id); 222 buf.writeByte('_'); 223 et = ExpType.Arg; 224 return true; 225 } 226 return false; 227 } 228 229 override void visit(IdentifierExp exp) 230 { 231 static if (LOG) 232 printf("IdentifierExp: %s\n", exp.toChars()); 233 234 if (buf.length == 0) 235 return; 236 237 auto id = exp.ident.toChars(); 238 239 // If it's not an argument 240 if (!checkArgument(id)) 241 { 242 // we must check what the identifier expression is. 243 Dsymbol scopesym; 244 Dsymbol s = sc.search(exp.loc, exp.ident, &scopesym); 245 if (s) 246 { 247 auto v = s.isVarDeclaration(); 248 // If it's a VarDeclaration, it must be a manifest constant 249 if (v && (v.storage_class & STC.manifest)) 250 { 251 v.getConstInitializer.accept(this); 252 } 253 else if (auto em = s.isEnumDeclaration()) 254 { 255 d = em; 256 et = ExpType.EnumDecl; 257 } 258 else if (auto fd = s.isFuncDeclaration()) 259 { 260 writeMangledName(fd); 261 } 262 // For anything else, the function is deemed uncomparable 263 else 264 { 265 buf.setsize(0); 266 } 267 } 268 // If it's an unknown symbol, consider the function incomparable 269 else 270 { 271 buf.setsize(0); 272 } 273 } 274 } 275 276 override void visit(DotVarExp exp) 277 { 278 static if (LOG) 279 printf("DotVarExp: %s, var: %s, e1: %s\n", exp.toChars(), 280 exp.var.toChars(), exp.e1.toChars()); 281 282 exp.e1.accept(this); 283 if (buf.length == 0) 284 return; 285 286 buf.setsize(buf.length -1); 287 buf.writeByte('.'); 288 buf.writestring(exp.var.toChars()); 289 buf.writeByte('_'); 290 } 291 292 override void visit(VarExp exp) 293 { 294 static if (LOG) 295 printf("VarExp: %s, var: %s\n", exp.toChars(), exp.var.toChars()); 296 297 if (buf.length == 0) 298 return; 299 300 auto id = exp.var.ident.toChars(); 301 if (!checkArgument(id)) 302 { 303 buf.setsize(0); 304 } 305 } 306 307 // serialize function calls 308 override void visit(CallExp exp) 309 { 310 static if (LOG) 311 printf("CallExp: %s\n", exp.toChars()); 312 313 if (buf.length == 0) 314 return; 315 316 if (!exp.f) 317 { 318 exp.e1.accept(this); 319 } 320 else 321 { 322 writeMangledName(exp.f); 323 } 324 325 buf.writeByte('('); 326 foreach (arg; *(exp.arguments)) 327 { 328 arg.accept(this); 329 } 330 buf.writeByte(')'); 331 } 332 333 override void visit(UnaExp exp) 334 { 335 if (buf.length == 0) 336 return; 337 338 buf.writeByte('('); 339 buf.writestring(Token.toString(exp.op)); 340 exp.e1.accept(this); 341 if (buf.length != 0) 342 buf.writestring(")_"); 343 } 344 345 override void visit(IntegerExp exp) 346 { 347 if (buf.length == 0) 348 return; 349 350 buf.print(exp.toInteger()); 351 buf.writeByte('_'); 352 } 353 354 override void visit(RealExp exp) 355 { 356 if (buf.length == 0) 357 return; 358 359 buf.writestring(exp.toChars()); 360 buf.writeByte('_'); 361 } 362 363 override void visit(BinExp exp) 364 { 365 static if (LOG) 366 printf("BinExp: %s\n", exp.toChars()); 367 368 if (buf.length == 0) 369 return; 370 371 buf.writeByte('('); 372 buf.writestring(Token.toChars(exp.op)); 373 374 exp.e1.accept(this); 375 if (buf.length == 0) 376 return; 377 378 exp.e2.accept(this); 379 if (buf.length == 0) 380 return; 381 382 buf.writeByte(')'); 383 } 384 385 override void visit(TypeBasic t) 386 { 387 buf.writestring(t.dstring); 388 buf.writeByte('_'); 389 } 390 391 void writeMangledName(Dsymbol s) 392 { 393 if (s) 394 { 395 OutBuffer mangledName; 396 mangleToBuffer(s, &mangledName); 397 buf.writestring(mangledName[]); 398 buf.writeByte('_'); 399 } 400 else 401 buf.setsize(0); 402 } 403 404 private bool checkTemplateInstance(T)(T t) 405 if (is(T == TypeStruct) || is(T == TypeClass)) 406 { 407 if (t.sym.parent && t.sym.parent.isTemplateInstance()) 408 { 409 buf.setsize(0); 410 return true; 411 } 412 return false; 413 } 414 415 override void visit(TypeStruct t) 416 { 417 static if (LOG) 418 printf("TypeStruct: %s\n", t.toChars); 419 420 if (!checkTemplateInstance!TypeStruct(t)) 421 writeMangledName(t.sym); 422 } 423 424 override void visit(TypeClass t) 425 { 426 static if (LOG) 427 printf("TypeClass: %s\n", t.toChars()); 428 429 if (!checkTemplateInstance!TypeClass(t)) 430 writeMangledName(t.sym); 431 } 432 433 override void visit(Parameter p) 434 { 435 if (p.type.ty == Tident 436 && (cast(TypeIdentifier)p.type).ident.toString().length > 3 437 && strncmp((cast(TypeIdentifier)p.type).ident.toChars(), "__T", 3) == 0) 438 { 439 buf.writestring("none_"); 440 } 441 else 442 visitType(p.type); 443 } 444 445 override void visit(StructLiteralExp e) { 446 static if (LOG) 447 printf("StructLiteralExp: %s\n", e.toChars); 448 449 auto ty = cast(TypeStruct)e.stype; 450 if (ty) 451 { 452 writeMangledName(ty.sym); 453 auto dim = e.elements.dim; 454 foreach (i; 0..dim) 455 { 456 auto elem = (*e.elements)[i]; 457 if (elem) 458 elem.accept(this); 459 else 460 buf.writestring("null_"); 461 } 462 } 463 else 464 buf.setsize(0); 465 } 466 467 override void visit(ArrayLiteralExp) { buf.setsize(0); } 468 override void visit(AssocArrayLiteralExp) { buf.setsize(0); } 469 override void visit(MixinExp) { buf.setsize(0); } 470 override void visit(ComplexExp) { buf.setsize(0); } 471 override void visit(DeclarationExp) { buf.setsize(0); } 472 override void visit(DefaultInitExp) { buf.setsize(0); } 473 override void visit(DsymbolExp) { buf.setsize(0); } 474 override void visit(ErrorExp) { buf.setsize(0); } 475 override void visit(FuncExp) { buf.setsize(0); } 476 override void visit(HaltExp) { buf.setsize(0); } 477 override void visit(IntervalExp) { buf.setsize(0); } 478 override void visit(IsExp) { buf.setsize(0); } 479 override void visit(NewAnonClassExp) { buf.setsize(0); } 480 override void visit(NewExp) { buf.setsize(0); } 481 override void visit(NullExp) { buf.setsize(0); } 482 override void visit(ObjcClassReferenceExp) { buf.setsize(0); } 483 override void visit(OverExp) { buf.setsize(0); } 484 override void visit(ScopeExp) { buf.setsize(0); } 485 override void visit(StringExp) { buf.setsize(0); } 486 override void visit(SymbolExp) { buf.setsize(0); } 487 override void visit(TemplateExp) { buf.setsize(0); } 488 override void visit(ThisExp) { buf.setsize(0); } 489 override void visit(TraitsExp) { buf.setsize(0); } 490 override void visit(TupleExp) { buf.setsize(0); } 491 override void visit(TypeExp) { buf.setsize(0); } 492 override void visit(TypeidExp) { buf.setsize(0); } 493 override void visit(VoidInitExp) { buf.setsize(0); } 494 }