1 /**
2  * Do mangling for C++ linkage.
3  *
4  * This is the POSIX side of the implementation.
5  * It exports two functions to C++, `toCppMangleItanium` and `cppTypeInfoMangleItanium`.
6  *
7  * Copyright: Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved
8  * Authors: Walter Bright, http://www.digitalmars.com
9  * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
10  * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/cppmangle.d, _cppmangle.d)
11  * Documentation:  https://dlang.org/phobos/dmd_cppmangle.html
12  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/cppmangle.d
13  *
14  * References:
15  *  Follows Itanium C++ ABI 1.86 section 5.1
16  *  http://refspecs.linux-foundation.org/cxxabi-1.86.html#mangling
17  *  which is where the grammar comments come from.
18  *
19  * Bugs:
20  *  https://issues.dlang.org/query.cgi
21  *  enter `C++, mangling` as the keywords.
22  */
23 
24 module dmd.cppmangle;
25 
26 import core.stdc.string;
27 import core.stdc.stdio;
28 
29 import dmd.arraytypes;
30 import dmd.attrib;
31 import dmd.declaration;
32 import dmd.dsymbol;
33 import dmd.dtemplate;
34 import dmd.errors;
35 import dmd.expression;
36 import dmd.func;
37 import dmd.globals;
38 import dmd.id;
39 import dmd.identifier;
40 import dmd.mtype;
41 import dmd.nspace;
42 import dmd.root.array;
43 import dmd.root.outbuffer;
44 import dmd.root.rootobject;
45 import dmd.root.string;
46 import dmd.target;
47 import dmd.tokens;
48 import dmd.typesem;
49 import dmd.visitor;
50 
51 
52 // helper to check if an identifier is a C++ operator
53 enum CppOperator { Cast, Assign, Eq, Index, Call, Unary, Binary, OpAssign, Unknown }
54 package CppOperator isCppOperator(Identifier id)
55 {
56     __gshared const(Identifier)[] operators = null;
57     if (!operators)
58         operators = [Id._cast, Id.assign, Id.eq, Id.index, Id.call, Id.opUnary, Id.opBinary, Id.opOpAssign];
59     foreach (i, op; operators)
60     {
61         if (op == id)
62             return cast(CppOperator)i;
63     }
64     return CppOperator.Unknown;
65 }
66 
67 ///
68 extern(C++) const(char)* toCppMangleItanium(Dsymbol s)
69 {
70     //printf("toCppMangleItanium(%s)\n", s.toChars());
71     OutBuffer buf;
72     scope CppMangleVisitor v = new CppMangleVisitor(&buf, s.loc);
73     v.mangleOf(s);
74     return buf.extractChars();
75 }
76 
77 ///
78 extern(C++) const(char)* cppTypeInfoMangleItanium(Dsymbol s)
79 {
80     //printf("cppTypeInfoMangle(%s)\n", s.toChars());
81     OutBuffer buf;
82     buf.writestring("_ZTI");    // "TI" means typeinfo structure
83     scope CppMangleVisitor v = new CppMangleVisitor(&buf, s.loc);
84     v.cpp_mangle_name(s, false);
85     return buf.extractChars();
86 }
87 
88 /******************************
89  * Determine if sym is the 'primary' destructor, that is,
90  * the most-aggregate destructor (the one that is defined as __xdtor)
91  * Params:
92  *      sym = Dsymbol
93  * Returns:
94  *      true if sym is the primary destructor for an aggregate
95  */
96 bool isPrimaryDtor(const Dsymbol sym)
97 {
98     const dtor = sym.isDtorDeclaration();
99     if (!dtor)
100         return false;
101     const ad = dtor.isMember();
102     assert(ad);
103     return dtor == ad.primaryDtor;
104 }
105 
106 /// Context used when processing pre-semantic AST
107 private struct Context
108 {
109     /// Template instance of the function being mangled
110     TemplateInstance ti;
111     /// Function declaration we're mangling
112     FuncDeclaration fd;
113     /// Current type / expression being processed (semantically analyzed)
114     RootObject res;
115 
116     @disable ref Context opAssign(ref Context other);
117     @disable ref Context opAssign(Context other);
118 
119     /**
120      * Helper function to track `res`
121      *
122      * Params:
123      *   next = Value to set `this.res` to.
124      *          If `this.res` is `null`, the expression is not evalutated.
125      *          This allow this code to be used even when no context is needed.
126      *
127      * Returns:
128      *   The previous state of this `Context` object
129      */
130     private Context push(lazy RootObject next)
131     {
132         auto r = this.res;
133         if (r !is null)
134             this.res = next;
135         return Context(this.ti, this.fd, r);
136     }
137 
138     /**
139      * Reset the context to a previous one, making any adjustment necessary
140      */
141     private void pop(ref Context prev)
142     {
143         this.res = prev.res;
144     }
145 }
146 
147 private final class CppMangleVisitor : Visitor
148 {
149     /// Context used when processing pre-semantic AST
150     private Context context;
151 
152     ABITagContainer abiTags;    /// Container for already-written ABI tags
153     Objects components;         /// array of components available for substitution
154     OutBuffer* buf;             /// append the mangling to buf[]
155     Loc loc;                    /// location for use in error messages
156 
157     /**
158      * Constructor
159      *
160      * Params:
161      *   buf = `OutBuffer` to write the mangling to
162      *   loc = `Loc` of the symbol being mangled
163      */
164     this(OutBuffer* buf, Loc loc)
165     {
166         this.buf = buf;
167         this.loc = loc;
168     }
169 
170     /*****
171      * Entry point. Append mangling to buf[]
172      * Params:
173      *  s = symbol to mangle
174      */
175     void mangleOf(Dsymbol s)
176     {
177         if (VarDeclaration vd = s.isVarDeclaration())
178         {
179             mangle_variable(vd, vd.cppnamespace !is null);
180         }
181         else if (FuncDeclaration fd = s.isFuncDeclaration())
182         {
183             mangle_function(fd);
184         }
185         else
186         {
187             assert(0);
188         }
189     }
190 
191     /**
192      * Mangle the return type of a function
193      *
194      * This is called on a templated function type.
195      * Context is set to the `FuncDeclaration`.
196      *
197      * Params:
198      *   preSemantic = the `FuncDeclaration`'s `originalType`
199      */
200     void mangleReturnType(TypeFunction preSemantic)
201     {
202         auto tf = cast(TypeFunction)this.context.res.asFuncDecl().type;
203         Type rt = preSemantic.nextOf();
204         if (tf.isref)
205             rt = rt.referenceTo();
206         auto prev = this.context.push(tf.nextOf());
207         scope (exit) this.context.pop(prev);
208         this.headOfType(rt);
209     }
210 
211     /**
212      * Write a seq-id from an index number, excluding the terminating '_'
213      *
214      * Params:
215      *   idx = the index in a substitution list.
216      *         Note that index 0 has no value, and `S0_` would be the
217      *         substitution at index 1 in the list.
218      *
219      * See-Also:
220      *  https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangle.seq-id
221      */
222     private void writeSequenceFromIndex(size_t idx)
223     {
224         if (idx)
225         {
226             void write_seq_id(size_t i)
227             {
228                 if (i >= 36)
229                 {
230                     write_seq_id(i / 36);
231                     i %= 36;
232                 }
233                 i += (i < 10) ? '0' : 'A' - 10;
234                 buf.writeByte(cast(char)i);
235             }
236 
237             write_seq_id(idx - 1);
238         }
239     }
240 
241     /**
242      * Attempt to perform substitution on `p`
243      *
244      * If `p` already appeared in the mangling, it is stored as
245      * a 'part', and short references in the form of `SX_` can be used.
246      * Note that `p` can be anything: template declaration, struct declaration,
247      * class declaration, namespace...
248      *
249      * Params:
250      *   p = The object to attempt to substitute
251      *   nested = Whether or not `p` is to be considered nested.
252      *            When `true`, `N` will be prepended before the substitution.
253      *
254      * Returns:
255      *   Whether `p` already appeared in the mangling,
256      *   and substitution has been written to `this.buf`.
257      */
258     bool substitute(RootObject p, bool nested = false)
259     {
260         //printf("substitute %s\n", p ? p.toChars() : null);
261         auto i = find(p);
262         if (i >= 0)
263         {
264             //printf("\tmatch\n");
265             /* Sequence is S_, S0_, .., S9_, SA_, ..., SZ_, S10_, ...
266              */
267             if (nested)
268                 buf.writeByte('N');
269             buf.writeByte('S');
270             writeSequenceFromIndex(i);
271             buf.writeByte('_');
272             return true;
273         }
274         return false;
275     }
276 
277     /******
278      * See if `p` exists in components[]
279      *
280      * Note that components can contain `null` entries,
281      * as the index used in mangling is based on the index in the array.
282      *
283      * If called with an object whose dynamic type is `Nspace`,
284      * calls the `find(Nspace)` overload.
285      *
286      * Returns:
287      *  index if found, -1 if not
288      */
289     int find(RootObject p)
290     {
291         //printf("find %p %d %s\n", p, p.dyncast(), p ? p.toChars() : null);
292         scope v = new ComponentVisitor(p);
293         foreach (i, component; components)
294         {
295             if (component)
296                 component.visitObject(v);
297             if (v.result)
298                 return cast(int)i;
299         }
300         return -1;
301     }
302 
303     /*********************
304      * Append p to components[]
305      */
306     void append(RootObject p)
307     {
308         //printf("append %p %d %s\n", p, p.dyncast(), p ? p.toChars() : "null");
309         components.push(p);
310     }
311 
312     /**
313      * Write an identifier preceded by its length
314      *
315      * Params:
316      *   ident = `Identifier` to write to `this.buf`
317      */
318     void writeIdentifier(const ref Identifier ident)
319     {
320         const name = ident.toString();
321         this.buf.print(name.length);
322         this.buf.writestring(name);
323     }
324 
325     /**
326      * Insert the leftover ABI tags to the buffer
327      *
328      * This inset ABI tags that hasn't already been written
329      * after the mangled name of the function.
330      * For more details, see the `abiTags` variable.
331      *
332      * Params:
333      *   off  = Offset to insert at
334      *   fd   = Type of the function to mangle the return type of
335      */
336     void writeRemainingTags(size_t off, TypeFunction tf)
337     {
338         scope remainingVisitor = new LeftoverVisitor(&this.abiTags.written);
339         tf.next.accept(remainingVisitor);
340         OutBuffer b2;
341         foreach (se; remainingVisitor.toWrite)
342         {
343             auto tag = se.peekString();
344             // We can only insert a slice, and each insert is a memmove,
345             // so use a temporary buffer to keep it efficient.
346             b2.reset();
347             b2.writestring("B");
348             b2.print(tag.length);
349             b2.writestring(tag);
350             this.buf.insert(off, b2[]);
351             off += b2.length;
352         }
353     }
354 
355     /************************
356      * Determine if symbol is indeed the global ::std namespace.
357      * Params:
358      *  s = symbol to check
359      * Returns:
360      *  true if it is ::std
361      */
362     static bool isStd(Dsymbol s)
363     {
364         if (!s)
365             return false;
366 
367         if (auto cnd = s.isCPPNamespaceDeclaration())
368             return isStd(cnd);
369 
370         return (s.ident == Id.std &&    // the right name
371                 s.isNspace() &&         // g++ disallows global "std" for other than a namespace
372                 !getQualifier(s));      // at global level
373     }
374 
375     /// Ditto
376     static bool isStd(CPPNamespaceDeclaration s)
377     {
378         return s && s.cppnamespace is null && s.ident == Id.std;
379     }
380 
381     /************************
382      * Determine if type is a C++ fundamental type.
383      * Params:
384      *  t = type to check
385      * Returns:
386      *  true if it is a fundamental type
387      */
388     static bool isFundamentalType(Type t)
389     {
390         // First check the target whether some specific ABI is being followed.
391         bool isFundamental = void;
392         if (target.cpp.fundamentalType(t, isFundamental))
393             return isFundamental;
394 
395         if (auto te = t.isTypeEnum())
396         {
397             // Peel off enum type from special types.
398             if (te.sym.isSpecial())
399                 t = te.memType();
400         }
401 
402         // Fundamental arithmetic types:
403         // 1. integral types: bool, char, int, ...
404         // 2. floating point types: float, double, real
405         // 3. void
406         // 4. null pointer: std::nullptr_t (since C++11)
407         if (t.ty == Tvoid || t.ty == Tbool)
408             return true;
409         else if (t.ty == Tnull && global.params.cplusplus >= CppStdRevision.cpp11)
410             return true;
411         else
412             return t.isTypeBasic() && (t.isintegral() || t.isreal());
413     }
414 
415     /******************************
416      * Write the mangled representation of a template argument.
417      * Params:
418      *  ti  = the template instance
419      *  arg = the template argument index
420      */
421     void template_arg(TemplateInstance ti, size_t arg)
422     {
423         TemplateDeclaration td = ti.tempdecl.isTemplateDeclaration();
424         assert(td);
425         TemplateParameter tp = (*td.parameters)[arg];
426         RootObject o = (*ti.tiargs)[arg];
427 
428         auto prev = this.context.push({
429                 TemplateInstance parentti;
430                 if (this.context.res.dyncast() == DYNCAST.dsymbol)
431                     parentti = this.context.res.asFuncDecl().parent.isTemplateInstance();
432                 else
433                     parentti = this.context.res.asType().toDsymbol(null).parent.isTemplateInstance();
434                 return (*parentti.tiargs)[arg];
435             }());
436         scope (exit) this.context.pop(prev);
437 
438         if (tp.isTemplateTypeParameter())
439         {
440             Type t = isType(o);
441             assert(t);
442             t.accept(this);
443         }
444         else if (TemplateValueParameter tv = tp.isTemplateValueParameter())
445         {
446             // <expr-primary> ::= L <type> <value number> E  # integer literal
447             if (tv.valType.isintegral())
448             {
449                 Expression e = isExpression(o);
450                 assert(e);
451                 buf.writeByte('L');
452                 tv.valType.accept(this);
453                 auto val = e.toUInteger();
454                 if (!tv.valType.isunsigned() && cast(sinteger_t)val < 0)
455                 {
456                     val = -val;
457                     buf.writeByte('n');
458                 }
459                 buf.print(val);
460                 buf.writeByte('E');
461             }
462             else
463             {
464                 ti.error("Internal Compiler Error: C++ `%s` template value parameter is not supported", tv.valType.toChars());
465                 fatal();
466             }
467         }
468         else if (tp.isTemplateAliasParameter())
469         {
470             // Passing a function as alias parameter is the same as passing
471             // `&function`
472             Dsymbol d = isDsymbol(o);
473             Expression e = isExpression(o);
474             if (d && d.isFuncDeclaration())
475             {
476                 // X .. E => template parameter is an expression
477                 // 'ad'   => unary operator ('&')
478                 // L .. E => is a <expr-primary>
479                 buf.writestring("XadL");
480                 mangle_function(d.isFuncDeclaration());
481                 buf.writestring("EE");
482             }
483             else if (e && e.op == TOK.variable && (cast(VarExp)e).var.isVarDeclaration())
484             {
485                 VarDeclaration vd = (cast(VarExp)e).var.isVarDeclaration();
486                 buf.writeByte('L');
487                 mangle_variable(vd, true);
488                 buf.writeByte('E');
489             }
490             else if (d && d.isTemplateDeclaration() && d.isTemplateDeclaration().onemember)
491             {
492                 if (!substitute(d))
493                 {
494                     cpp_mangle_name(d, false);
495                 }
496             }
497             else
498             {
499                 ti.error("Internal Compiler Error: C++ `%s` template alias parameter is not supported", o.toChars());
500                 fatal();
501             }
502         }
503         else if (tp.isTemplateThisParameter())
504         {
505             ti.error("Internal Compiler Error: C++ `%s` template this parameter is not supported", o.toChars());
506             fatal();
507         }
508         else
509         {
510             assert(0);
511         }
512     }
513 
514     /******************************
515      * Write the mangled representation of the template arguments.
516      * Params:
517      *  ti = the template instance
518      *  firstArg = index of the first template argument to mangle
519      *             (used for operator overloading)
520      * Returns:
521      *  true if any arguments were written
522      */
523     bool template_args(TemplateInstance ti, int firstArg = 0)
524     {
525         /* <template-args> ::= I <template-arg>+ E
526          */
527         if (!ti || ti.tiargs.dim <= firstArg)   // could happen if std::basic_string is not a template
528             return false;
529         buf.writeByte('I');
530         foreach (i; firstArg .. ti.tiargs.dim)
531         {
532             TemplateDeclaration td = ti.tempdecl.isTemplateDeclaration();
533             assert(td);
534             TemplateParameter tp = (*td.parameters)[i];
535 
536             /*
537              * <template-arg> ::= <type>               # type or template
538              *                ::= X <expression> E     # expression
539              *                ::= <expr-primary>       # simple expressions
540              *                ::= J <template-arg>* E  # argument pack
541              *
542              * Reference: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangle.template-arg
543              */
544             if (TemplateTupleParameter tt = tp.isTemplateTupleParameter())
545             {
546                 buf.writeByte('J');     // argument pack
547 
548                 // mangle the rest of the arguments as types
549                 foreach (j; i .. (*ti.tiargs).dim)
550                 {
551                     Type t = isType((*ti.tiargs)[j]);
552                     assert(t);
553                     t.accept(this);
554                 }
555 
556                 buf.writeByte('E');
557                 break;
558             }
559 
560             template_arg(ti, i);
561         }
562         buf.writeByte('E');
563         return true;
564     }
565 
566     /**
567      * Write the symbol `p` if not null, then execute the delegate
568      *
569      * Params:
570      *   p = Symbol to write
571      *   dg = Delegate to execute
572      */
573     void writeChained(Dsymbol p, scope void delegate() dg)
574     {
575         if (p && !p.isModule())
576         {
577             buf.writestring("N");
578             source_name(p, true);
579             dg();
580             buf.writestring("E");
581         }
582         else
583             dg();
584     }
585 
586     /**
587      * Write the name of `s` to the buffer
588      *
589      * Params:
590      *   s = Symbol to write the name of
591      *   haveNE = Whether `N..E` is already part of the mangling
592      *            Because `Nspace` and `CPPNamespaceAttribute` can be
593      *            mixed, this is a mandatory hack.
594      */
595     void source_name(Dsymbol s, bool haveNE = false)
596     {
597         version (none)
598         {
599             printf("source_name(%s)\n", s.toChars());
600             auto sl = this.buf.peekSlice();
601             assert(sl.length == 0 || haveNE || s.cppnamespace is null || sl != "_ZN");
602         }
603         if (TemplateInstance ti = s.isTemplateInstance())
604         {
605             bool needsTa = false;
606 
607             // https://issues.dlang.org/show_bug.cgi?id=20413
608             // N..E is not needed when substituting members of the std namespace.
609             // This is observed in the GCC and Clang implementations.
610             // The Itanium specification is not clear enough on this specific case.
611             // References:
612             //   https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangle.name
613             //   https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling-compression
614             Dsymbol q = getQualifier(ti.tempdecl);
615             Dsymbol ns = ti.tempdecl.cppnamespace;
616             const inStd = ns && isStd(ns) || q && isStd(q);
617             const isNested = !inStd && (ns || q);
618 
619             if (substitute(ti.tempdecl, !haveNE && isNested))
620             {
621                 template_args(ti);
622                 if (!haveNE && isNested)
623                     buf.writeByte('E');
624             }
625             else if (this.writeStdSubstitution(ti, needsTa))
626             {
627                 this.abiTags.writeSymbol(ti, this);
628                 if (needsTa)
629                     template_args(ti);
630             }
631             else
632             {
633                 this.writeNamespace(
634                     s.cppnamespace, () {
635                         this.writeIdentifier(ti.tempdecl.toAlias().ident);
636                         append(ti.tempdecl);
637                         this.abiTags.writeSymbol(ti.tempdecl, this);
638                         template_args(ti);
639                     }, haveNE);
640             }
641         }
642         else
643             this.writeNamespace(s.cppnamespace, () {
644                     this.writeIdentifier(s.ident);
645                     this.abiTags.writeSymbol(s, this);
646                 },
647                 haveNE);
648     }
649 
650     /********
651      * See if s is actually an instance of a template
652      * Params:
653      *  s = symbol
654      * Returns:
655      *  if s is instance of a template, return the instance, otherwise return s
656      */
657     static Dsymbol getInstance(Dsymbol s)
658     {
659         Dsymbol p = s.toParent();
660         if (p)
661         {
662             if (TemplateInstance ti = p.isTemplateInstance())
663                 return ti;
664         }
665         return s;
666     }
667 
668     /// Get the namespace of a template instance
669     CPPNamespaceDeclaration getTiNamespace(TemplateInstance ti)
670     {
671         // If we receive a pre-semantic `TemplateInstance`,
672         // `cppnamespace` is always `null`
673         return ti.tempdecl ? ti.cppnamespace
674             : this.context.res.asType().toDsymbol(null).cppnamespace;
675     }
676 
677     /********
678      * Get qualifier for `s`, meaning the symbol
679      * that s is in the symbol table of.
680      * The module does not count as a qualifier, because C++
681      * does not have modules.
682      * Params:
683      *  s = symbol that may have a qualifier
684      *      s is rewritten to be TemplateInstance if s is one
685      * Returns:
686      *  qualifier, null if none
687      */
688     static Dsymbol getQualifier(Dsymbol s)
689     {
690         Dsymbol p = s.toParent();
691         return (p && !p.isModule()) ? p : null;
692     }
693 
694     // Detect type char
695     static bool isChar(RootObject o)
696     {
697         Type t = isType(o);
698         return (t && t.equals(Type.tchar));
699     }
700 
701     // Detect type ::std::char_traits<char>
702     bool isChar_traits_char(RootObject o)
703     {
704         return isIdent_char(Id.char_traits, o);
705     }
706 
707     // Detect type ::std::allocator<char>
708     bool isAllocator_char(RootObject o)
709     {
710         return isIdent_char(Id.allocator, o);
711     }
712 
713     // Detect type ::std::ident<char>
714     bool isIdent_char(Identifier ident, RootObject o)
715     {
716         Type t = isType(o);
717         if (!t || t.ty != Tstruct)
718             return false;
719         Dsymbol s = (cast(TypeStruct)t).toDsymbol(null);
720         if (s.ident != ident)
721             return false;
722         Dsymbol p = s.toParent();
723         if (!p)
724             return false;
725         TemplateInstance ti = p.isTemplateInstance();
726         if (!ti)
727             return false;
728         Dsymbol q = getQualifier(ti);
729         const bool inStd = isStd(q) || isStd(this.getTiNamespace(ti));
730         return inStd && ti.tiargs.dim == 1 && isChar((*ti.tiargs)[0]);
731     }
732 
733     /***
734      * Detect template args <char, ::std::char_traits<char>>
735      * and write st if found.
736      * Returns:
737      *  true if found
738      */
739     bool char_std_char_traits_char(TemplateInstance ti, string st)
740     {
741         if (ti.tiargs.dim == 2 &&
742             isChar((*ti.tiargs)[0]) &&
743             isChar_traits_char((*ti.tiargs)[1]))
744         {
745             buf.writestring(st.ptr);
746             return true;
747         }
748         return false;
749     }
750 
751 
752     void prefix_name(Dsymbol s)
753     {
754         //printf("prefix_name(%s)\n", s.toChars());
755         if (substitute(s))
756             return;
757         if (isStd(s))
758             return buf.writestring("St");
759 
760         auto si = getInstance(s);
761         Dsymbol p = getQualifier(si);
762         if (p)
763         {
764             if (isStd(p))
765             {
766                 bool needsTa;
767                 auto ti = si.isTemplateInstance();
768                 if (this.writeStdSubstitution(ti, needsTa))
769                 {
770                     this.abiTags.writeSymbol(ti, this);
771                     if (needsTa)
772                     {
773                         template_args(ti);
774                         append(ti);
775                     }
776                     return;
777                 }
778                 buf.writestring("St");
779             }
780             else
781                 prefix_name(p);
782         }
783         source_name(si, true);
784         if (!isStd(si))
785             /* Do this after the source_name() call to keep components[]
786              * in the right order.
787              * https://issues.dlang.org/show_bug.cgi?id=17947
788              */
789             append(si);
790     }
791 
792     /**
793      * Write common substitution for standard types, such as std::allocator
794      *
795      * This function assumes that the symbol `ti` is in the namespace `std`.
796      *
797      * Params:
798      *   ti = Template instance to consider
799      *   needsTa = If this function returns `true`, this value indicates
800      *             if additional template argument mangling is needed
801      *
802      * Returns:
803      *   `true` if a special std symbol was found
804      */
805     bool writeStdSubstitution(TemplateInstance ti, out bool needsTa)
806     {
807         if (!ti)
808             return false;
809         if (!isStd(this.getTiNamespace(ti)) && !isStd(getQualifier(ti)))
810             return false;
811 
812         if (ti.name == Id.allocator)
813         {
814             buf.writestring("Sa");
815             needsTa = true;
816             return true;
817         }
818         if (ti.name == Id.basic_string)
819         {
820             // ::std::basic_string<char, ::std::char_traits<char>, ::std::allocator<char>>
821             if (ti.tiargs.dim == 3 &&
822                 isChar((*ti.tiargs)[0]) &&
823                 isChar_traits_char((*ti.tiargs)[1]) &&
824                 isAllocator_char((*ti.tiargs)[2]))
825 
826             {
827                 buf.writestring("Ss");
828                 return true;
829             }
830             buf.writestring("Sb");      // ::std::basic_string
831             needsTa = true;
832             return true;
833         }
834 
835         // ::std::basic_istream<char, ::std::char_traits<char>>
836         if (ti.name == Id.basic_istream &&
837             char_std_char_traits_char(ti, "Si"))
838             return true;
839 
840         // ::std::basic_ostream<char, ::std::char_traits<char>>
841         if (ti.name == Id.basic_ostream &&
842             char_std_char_traits_char(ti, "So"))
843             return true;
844 
845         // ::std::basic_iostream<char, ::std::char_traits<char>>
846         if (ti.name == Id.basic_iostream &&
847             char_std_char_traits_char(ti, "Sd"))
848             return true;
849 
850         return false;
851     }
852 
853 
854     void cpp_mangle_name(Dsymbol s, bool qualified)
855     {
856         //printf("cpp_mangle_name(%s, %d)\n", s.toChars(), qualified);
857         Dsymbol p = s.toParent();
858         Dsymbol se = s;
859         bool write_prefix = true;
860         if (p && p.isTemplateInstance())
861         {
862             se = p;
863             if (find(p.isTemplateInstance().tempdecl) >= 0)
864                 write_prefix = false;
865             p = p.toParent();
866         }
867         if (p && !p.isModule())
868         {
869             /* The N..E is not required if:
870              * 1. the parent is 'std'
871              * 2. 'std' is the initial qualifier
872              * 3. there is no CV-qualifier or a ref-qualifier for a member function
873              * ABI 5.1.8
874              */
875             if (isStd(p) && !qualified)
876             {
877                 TemplateInstance ti = se.isTemplateInstance();
878                 if (s.ident == Id.allocator)
879                 {
880                     buf.writestring("Sa"); // "Sa" is short for ::std::allocator
881                     template_args(ti);
882                 }
883                 else if (s.ident == Id.basic_string)
884                 {
885                     // ::std::basic_string<char, ::std::char_traits<char>, ::std::allocator<char>>
886                     if (ti.tiargs.dim == 3 &&
887                         isChar((*ti.tiargs)[0]) &&
888                         isChar_traits_char((*ti.tiargs)[1]) &&
889                         isAllocator_char((*ti.tiargs)[2]))
890                     {
891                         buf.writestring("Ss");
892                         return;
893                     }
894                     buf.writestring("Sb");      // ::std::basic_string
895                     template_args(ti);
896                 }
897                 else
898                 {
899                     // ::std::basic_istream<char, ::std::char_traits<char>>
900                     if (s.ident == Id.basic_istream)
901                     {
902                         if (char_std_char_traits_char(ti, "Si"))
903                             return;
904                     }
905                     else if (s.ident == Id.basic_ostream)
906                     {
907                         if (char_std_char_traits_char(ti, "So"))
908                             return;
909                     }
910                     else if (s.ident == Id.basic_iostream)
911                     {
912                         if (char_std_char_traits_char(ti, "Sd"))
913                             return;
914                     }
915                     buf.writestring("St");
916                     source_name(se, true);
917                 }
918             }
919             else
920             {
921                 buf.writeByte('N');
922                 if (write_prefix)
923                 {
924                     if (isStd(p))
925                         buf.writestring("St");
926                     else
927                         prefix_name(p);
928                 }
929                 source_name(se, true);
930                 buf.writeByte('E');
931             }
932         }
933         else
934             source_name(se, false);
935         append(s);
936     }
937 
938     /**
939      * Write CV-qualifiers to the buffer
940      *
941      * CV-qualifiers are 'r': restrict (unused in D), 'V': volatile, 'K': const
942      *
943      * See_Also:
944      *   https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangle.CV-qualifiers
945      */
946     void CV_qualifiers(const Type t)
947     {
948         if (t.isConst())
949             buf.writeByte('K');
950     }
951 
952     /**
953      * Mangles a variable
954      *
955      * Params:
956      *   d = Variable declaration to mangle
957      *   isNested = Whether this variable is nested, e.g. a template parameter
958      *              or within a namespace
959      */
960     void mangle_variable(VarDeclaration d, bool isNested)
961     {
962         // fake mangling for fields to fix https://issues.dlang.org/show_bug.cgi?id=16525
963         if (!(d.storage_class & (STC.extern_ | STC.field | STC.gshared)))
964         {
965             d.error("Internal Compiler Error: C++ static non-`__gshared` non-`extern` variables not supported");
966             fatal();
967         }
968         Dsymbol p = d.toParent();
969         if (p && !p.isModule()) //for example: char Namespace1::beta[6] should be mangled as "_ZN10Namespace14betaE"
970         {
971             buf.writestring("_ZN");
972             prefix_name(p);
973             source_name(d, true);
974             buf.writeByte('E');
975         }
976         else if (isNested)
977         {
978             buf.writestring("_Z");
979             source_name(d, false);
980         }
981         else
982         {
983             if (auto varTags = ABITagContainer.forSymbol(d))
984             {
985                 buf.writestring("_Z");
986                 source_name(d, false);
987                 return;
988             }
989             if (auto typeTags = ABITagContainer.forSymbol(d.type.toDsymbol(null)))
990             {
991                 buf.writestring("_Z");
992                 source_name(d, false);
993                 this.abiTags.write(*this.buf, typeTags);
994                 return;
995             }
996             //char beta[6] should mangle as "beta"
997             buf.writestring(d.ident.toString());
998         }
999     }
1000 
1001     void mangle_function(FuncDeclaration d)
1002     {
1003         //printf("mangle_function(%s)\n", d.toChars());
1004         /*
1005          * <mangled-name> ::= _Z <encoding>
1006          * <encoding> ::= <function name> <bare-function-type>
1007          *            ::= <data name>
1008          *            ::= <special-name>
1009          */
1010         TypeFunction tf = cast(TypeFunction)d.type;
1011         buf.writestring("_Z");
1012 
1013         if (TemplateDeclaration ftd = getFuncTemplateDecl(d))
1014         {
1015             /* It's an instance of a function template
1016              */
1017             TemplateInstance ti = d.parent.isTemplateInstance();
1018             assert(ti);
1019             this.mangleTemplatedFunction(d, tf, ftd, ti);
1020         }
1021         else
1022         {
1023             Dsymbol p = d.toParent();
1024             if (p && !p.isModule() && tf.linkage == LINK.cpp)
1025             {
1026                 this.mangleNestedFuncPrefix(tf, p);
1027 
1028                 if (auto ctor = d.isCtorDeclaration())
1029                     buf.writestring(ctor.isCpCtor ? "C2" : "C1");
1030                 else if (d.isPrimaryDtor())
1031                     buf.writestring("D1");
1032                 else if (d.ident && d.ident == Id.assign)
1033                     buf.writestring("aS");
1034                 else if (d.ident && d.ident == Id.eq)
1035                     buf.writestring("eq");
1036                 else if (d.ident && d.ident == Id.index)
1037                     buf.writestring("ix");
1038                 else if (d.ident && d.ident == Id.call)
1039                     buf.writestring("cl");
1040                 else
1041                     source_name(d, true);
1042                 buf.writeByte('E');
1043             }
1044             else
1045             {
1046                 source_name(d, false);
1047             }
1048 
1049             // Save offset for potentially writing tags
1050             const size_t off = this.buf.length();
1051 
1052             // Template args accept extern "C" symbols with special mangling
1053             if (tf.linkage == LINK.cpp)
1054                 mangleFunctionParameters(tf.parameterList.parameters, tf.parameterList.varargs);
1055 
1056             if (!tf.next.isTypeBasic())
1057                 this.writeRemainingTags(off, tf);
1058         }
1059     }
1060 
1061     /**
1062      * Recursively mangles a non-scoped namespace
1063      *
1064      * Parameters:
1065      *   ns = Namespace to mangle
1066      *   dg = A delegate to write the identifier in this namespace
1067      *   haveNE = When `false` (the default), surround the namespace / dg
1068      *            call with nested name qualifier (`N..E`).
1069      *            Otherwise, they are already present (e.g. `Nspace` was used).
1070      */
1071     void writeNamespace(CPPNamespaceDeclaration ns, scope void delegate() dg,
1072                         bool haveNE = false)
1073     {
1074         void runDg () { if (dg !is null) dg(); }
1075 
1076         if (ns is null)
1077             return runDg();
1078 
1079         if (isStd(ns))
1080         {
1081             if (!substitute(ns))
1082                 buf.writestring("St");
1083             runDg();
1084         }
1085         else if (dg !is null)
1086         {
1087             if (!haveNE)
1088                 buf.writestring("N");
1089             if (!substitute(ns))
1090             {
1091                 this.writeNamespace(ns.cppnamespace, null);
1092                 this.writeIdentifier(ns.ident);
1093                 append(ns);
1094             }
1095             dg();
1096             if (!haveNE)
1097                 buf.writestring("E");
1098         }
1099         else if (!substitute(ns))
1100         {
1101             this.writeNamespace(ns.cppnamespace, null);
1102             this.writeIdentifier(ns.ident);
1103             append(ns);
1104         }
1105     }
1106 
1107     /**
1108      * Mangles a function template to C++
1109      *
1110      * Params:
1111      *   d = Function declaration
1112      *   tf = Function type (casted d.type)
1113      *   ftd = Template declaration (ti.templdecl)
1114      *   ti = Template instance (d.parent)
1115      */
1116     void mangleTemplatedFunction(FuncDeclaration d, TypeFunction tf,
1117                                  TemplateDeclaration ftd, TemplateInstance ti)
1118     {
1119         Dsymbol p = ti.toParent();
1120         // Check if this function is *not* nested
1121         if (!p || p.isModule() || tf.linkage != LINK.cpp)
1122         {
1123             this.context.ti = ti;
1124             this.context.fd = d;
1125             this.context.res = d;
1126             TypeFunction preSemantic = cast(TypeFunction)d.originalType;
1127             auto nspace = ti.toParent();
1128             if (nspace && nspace.isNspace())
1129                 this.writeChained(ti.toParent(), () => source_name(ti, true));
1130             else
1131                 source_name(ti, false);
1132             this.mangleReturnType(preSemantic);
1133             this.mangleFunctionParameters(preSemantic.parameterList.parameters, tf.parameterList.varargs);
1134             return;
1135         }
1136 
1137         // It's a nested function (e.g. a member of an aggregate)
1138         this.mangleNestedFuncPrefix(tf, p);
1139 
1140         if (d.isCtorDeclaration())
1141         {
1142             buf.writestring("C1");
1143         }
1144         else if (d.isPrimaryDtor())
1145         {
1146             buf.writestring("D1");
1147         }
1148         else
1149         {
1150             int firstTemplateArg = 0;
1151             bool appendReturnType = true;
1152             bool isConvertFunc = false;
1153             string symName;
1154 
1155             // test for special symbols
1156             CppOperator whichOp = isCppOperator(ti.name);
1157             final switch (whichOp)
1158             {
1159             case CppOperator.Unknown:
1160                 break;
1161             case CppOperator.Cast:
1162                 symName = "cv";
1163                 firstTemplateArg = 1;
1164                 isConvertFunc = true;
1165                 appendReturnType = false;
1166                 break;
1167             case CppOperator.Assign:
1168                 symName = "aS";
1169                 break;
1170             case CppOperator.Eq:
1171                 symName = "eq";
1172                 break;
1173             case CppOperator.Index:
1174                 symName = "ix";
1175                 break;
1176             case CppOperator.Call:
1177                 symName = "cl";
1178                 break;
1179             case CppOperator.Unary:
1180             case CppOperator.Binary:
1181             case CppOperator.OpAssign:
1182                 TemplateDeclaration td = ti.tempdecl.isTemplateDeclaration();
1183                 assert(td);
1184                 assert(ti.tiargs.dim >= 1);
1185                 TemplateParameter tp = (*td.parameters)[0];
1186                 TemplateValueParameter tv = tp.isTemplateValueParameter();
1187                 if (!tv || !tv.valType.isString())
1188                     break; // expecting a string argument to operators!
1189                 Expression exp = (*ti.tiargs)[0].isExpression();
1190                 StringExp str = exp.toStringExp();
1191                 switch (whichOp)
1192                 {
1193                 case CppOperator.Unary:
1194                     switch (str.peekString())
1195                     {
1196                     case "*":   symName = "de"; goto continue_template;
1197                     case "++":  symName = "pp"; goto continue_template;
1198                     case "--":  symName = "mm"; goto continue_template;
1199                     case "-":   symName = "ng"; goto continue_template;
1200                     case "+":   symName = "ps"; goto continue_template;
1201                     case "~":   symName = "co"; goto continue_template;
1202                     default:    break;
1203                     }
1204                     break;
1205                 case CppOperator.Binary:
1206                     switch (str.peekString())
1207                     {
1208                     case ">>":  symName = "rs"; goto continue_template;
1209                     case "<<":  symName = "ls"; goto continue_template;
1210                     case "*":   symName = "ml"; goto continue_template;
1211                     case "-":   symName = "mi"; goto continue_template;
1212                     case "+":   symName = "pl"; goto continue_template;
1213                     case "&":   symName = "an"; goto continue_template;
1214                     case "/":   symName = "dv"; goto continue_template;
1215                     case "%":   symName = "rm"; goto continue_template;
1216                     case "^":   symName = "eo"; goto continue_template;
1217                     case "|":   symName = "or"; goto continue_template;
1218                     default:    break;
1219                     }
1220                     break;
1221                 case CppOperator.OpAssign:
1222                     switch (str.peekString())
1223                     {
1224                     case "*":   symName = "mL"; goto continue_template;
1225                     case "+":   symName = "pL"; goto continue_template;
1226                     case "-":   symName = "mI"; goto continue_template;
1227                     case "/":   symName = "dV"; goto continue_template;
1228                     case "%":   symName = "rM"; goto continue_template;
1229                     case ">>":  symName = "rS"; goto continue_template;
1230                     case "<<":  symName = "lS"; goto continue_template;
1231                     case "&":   symName = "aN"; goto continue_template;
1232                     case "|":   symName = "oR"; goto continue_template;
1233                     case "^":   symName = "eO"; goto continue_template;
1234                     default:    break;
1235                     }
1236                     break;
1237                 default:
1238                     assert(0);
1239                 continue_template:
1240                     firstTemplateArg = 1;
1241                     break;
1242                 }
1243                 break;
1244             }
1245             if (symName.length == 0)
1246                 source_name(ti, true);
1247             else
1248             {
1249                 buf.writestring(symName);
1250                 if (isConvertFunc)
1251                     template_arg(ti, 0);
1252                 appendReturnType = template_args(ti, firstTemplateArg) && appendReturnType;
1253             }
1254             buf.writeByte('E');
1255             if (appendReturnType)
1256                 headOfType(tf.nextOf());  // mangle return type
1257         }
1258         mangleFunctionParameters(tf.parameterList.parameters, tf.parameterList.varargs);
1259     }
1260 
1261     /**
1262      * Mangle the parameters of a function
1263      *
1264      * For templated functions, `context.res` is set to the `FuncDeclaration`
1265      *
1266      * Params:
1267      *   parameters = Array of `Parameter` to mangle
1268      *   varargs = if != 0, this function has varargs parameters
1269      */
1270     void mangleFunctionParameters(Parameters* parameters, VarArg varargs)
1271     {
1272         int numparams = 0;
1273 
1274         int paramsCppMangleDg(size_t n, Parameter fparam)
1275         {
1276             Type t = target.cpp.parameterType(fparam);
1277             if (t.ty == Tsarray)
1278             {
1279                 // Static arrays in D are passed by value; no counterpart in C++
1280                 .error(loc, "Internal Compiler Error: unable to pass static array `%s` to extern(C++) function, use pointer instead",
1281                     t.toChars());
1282                 fatal();
1283             }
1284             auto prev = this.context.push({
1285                     TypeFunction tf;
1286                     if (isDsymbol(this.context.res))
1287                         tf = cast(TypeFunction)this.context.res.asFuncDecl().type;
1288                     else
1289                         tf = this.context.res.asType().isTypeFunction();
1290                     assert(tf);
1291                     return (*tf.parameterList.parameters)[n].type;
1292                 }());
1293             scope (exit) this.context.pop(prev);
1294             headOfType(t);
1295             ++numparams;
1296             return 0;
1297         }
1298 
1299         if (parameters)
1300             Parameter._foreach(parameters, &paramsCppMangleDg);
1301         if (varargs == VarArg.variadic)
1302             buf.writeByte('z');
1303         else if (!numparams)
1304             buf.writeByte('v'); // encode (void) parameters
1305     }
1306 
1307     /****** The rest is type mangling ************/
1308 
1309     void error(Type t)
1310     {
1311         const(char)* p;
1312         if (t.isImmutable())
1313             p = "`immutable` ";
1314         else if (t.isShared())
1315             p = "`shared` ";
1316         else
1317             p = "";
1318         .error(loc, "Internal Compiler Error: %stype `%s` cannot be mapped to C++\n", p, t.toChars());
1319         fatal(); //Fatal, because this error should be handled in frontend
1320     }
1321 
1322     /****************************
1323      * Mangle a type,
1324      * treating it as a Head followed by a Tail.
1325      * Params:
1326      *  t = Head of a type
1327      */
1328     void headOfType(Type t)
1329     {
1330         if (t.ty == Tclass)
1331         {
1332             mangleTypeClass(cast(TypeClass)t, true);
1333         }
1334         else
1335         {
1336             // For value types, strip const/immutable/shared from the head of the type
1337             auto prev = this.context.push(this.context.res.asType().mutableOf().unSharedOf());
1338             scope (exit) this.context.pop(prev);
1339             t.mutableOf().unSharedOf().accept(this);
1340         }
1341     }
1342 
1343     /******
1344      * Write out 1 or 2 character basic type mangling.
1345      * Handle const and substitutions.
1346      * Params:
1347      *  t = type to mangle
1348      *  p = if not 0, then character prefix
1349      *  c = mangling character
1350      */
1351     void writeBasicType(Type t, char p, char c)
1352     {
1353         // Only do substitutions for non-fundamental types.
1354         if (!isFundamentalType(t) || t.isConst())
1355         {
1356             if (substitute(t))
1357                 return;
1358             else
1359                 append(t);
1360         }
1361         CV_qualifiers(t);
1362         if (p)
1363             buf.writeByte(p);
1364         buf.writeByte(c);
1365     }
1366 
1367 
1368     /****************
1369      * Write structs and enums.
1370      * Params:
1371      *  t = TypeStruct or TypeEnum
1372      */
1373     void doSymbol(Type t)
1374     {
1375         if (substitute(t))
1376             return;
1377         CV_qualifiers(t);
1378 
1379         // Handle any target-specific struct types.
1380         if (auto tm = target.cpp.typeMangle(t))
1381         {
1382             buf.writestring(tm);
1383         }
1384         else
1385         {
1386             Dsymbol s = t.toDsymbol(null);
1387             Dsymbol p = s.toParent();
1388             if (p && p.isTemplateInstance())
1389             {
1390                  /* https://issues.dlang.org/show_bug.cgi?id=17947
1391                   * Substitute the template instance symbol, not the struct/enum symbol
1392                   */
1393                 if (substitute(p))
1394                     return;
1395             }
1396             if (!substitute(s))
1397                 cpp_mangle_name(s, false);
1398         }
1399         if (t.isConst())
1400             append(t);
1401     }
1402 
1403 
1404 
1405     /************************
1406      * Mangle a class type.
1407      * If it's the head, treat the initial pointer as a value type.
1408      * Params:
1409      *  t = class type
1410      *  head = true for head of a type
1411      */
1412     void mangleTypeClass(TypeClass t, bool head)
1413     {
1414         if (t.isImmutable() || t.isShared())
1415             return error(t);
1416 
1417         /* Mangle as a <pointer to><struct>
1418          */
1419         if (substitute(t))
1420             return;
1421         if (!head)
1422             CV_qualifiers(t);
1423         buf.writeByte('P');
1424 
1425         CV_qualifiers(t);
1426 
1427         {
1428             Dsymbol s = t.toDsymbol(null);
1429             Dsymbol p = s.toParent();
1430             if (p && p.isTemplateInstance())
1431             {
1432                  /* https://issues.dlang.org/show_bug.cgi?id=17947
1433                   * Substitute the template instance symbol, not the class symbol
1434                   */
1435                 if (substitute(p))
1436                     return;
1437             }
1438         }
1439 
1440         if (!substitute(t.sym))
1441         {
1442             cpp_mangle_name(t.sym, false);
1443         }
1444         if (t.isConst())
1445             append(null);  // C++ would have an extra type here
1446         append(t);
1447     }
1448 
1449     /**
1450      * Mangle the prefix of a nested (e.g. member) function
1451      *
1452      * Params:
1453      *   tf = Type of the nested function
1454      *   parent = Parent in which the function is nested
1455      */
1456     void mangleNestedFuncPrefix(TypeFunction tf, Dsymbol parent)
1457     {
1458         /* <nested-name> ::= N [<CV-qualifiers>] <prefix> <unqualified-name> E
1459          *               ::= N [<CV-qualifiers>] <template-prefix> <template-args> E
1460          */
1461         buf.writeByte('N');
1462         CV_qualifiers(tf);
1463 
1464         /* <prefix> ::= <prefix> <unqualified-name>
1465          *          ::= <template-prefix> <template-args>
1466          *          ::= <template-param>
1467          *          ::= # empty
1468          *          ::= <substitution>
1469          *          ::= <prefix> <data-member-prefix>
1470          */
1471         prefix_name(parent);
1472     }
1473 
1474     /**
1475      * Helper function to write a `T..._` template index.
1476      *
1477      * Params:
1478      *   idx   = Index of `param` in the template argument list
1479      *   param = Template parameter to mangle
1480      */
1481     private void writeTemplateArgIndex(size_t idx, TemplateParameter param)
1482     {
1483         // expressions are mangled in <X..E>
1484         if (param.isTemplateValueParameter())
1485             buf.writeByte('X');
1486         buf.writeByte('T');
1487         writeSequenceFromIndex(idx);
1488         buf.writeByte('_');
1489         if (param.isTemplateValueParameter())
1490             buf.writeByte('E');
1491     }
1492 
1493     /**
1494      * Given an array of template parameters and an identifier,
1495      * returns the index of the identifier in that array.
1496      *
1497      * Params:
1498      *   ident = Identifier for which substitution is attempted
1499      *           (e.g. `void func(T)(T param)` => `T` from `T param`)
1500      *   params = `TemplateParameters` of the enclosing symbol
1501      *           (in the previous example, `func`'s template parameters)
1502      *
1503      * Returns:
1504      *   The index of the identifier match in `params`,
1505      *   or `params.length` if there wasn't any match.
1506      */
1507     private static size_t templateParamIndex(
1508         const ref Identifier ident, TemplateParameters* params)
1509     {
1510         foreach (idx, param; *params)
1511             if (param.ident == ident)
1512                 return idx;
1513         return params.length;
1514     }
1515 
1516     /**
1517      * Given a template instance `t`, write its qualified name
1518      * without the template parameter list
1519      *
1520      * Params:
1521      *   t = Post-parsing `TemplateInstance` pointing to the symbol
1522      *       to mangle (one level deep)
1523      *   dg = Delegate to execute after writing the qualified symbol
1524      *
1525      */
1526     private void writeQualified(TemplateInstance t, scope void delegate() dg)
1527     {
1528         auto type = isType(this.context.res);
1529         if (!type)
1530         {
1531             this.writeIdentifier(t.name);
1532             return dg();
1533         }
1534         auto sym1 = type.toDsymbol(null);
1535         if (!sym1)
1536         {
1537             this.writeIdentifier(t.name);
1538             return dg();
1539         }
1540         // Get the template instance
1541         auto sym = getQualifier(sym1);
1542         auto sym2 = getQualifier(sym);
1543         if (sym2 && isStd(sym2)) // Nspace path
1544         {
1545             bool unused;
1546             assert(sym.isTemplateInstance());
1547             if (this.writeStdSubstitution(sym.isTemplateInstance(), unused))
1548                 return dg();
1549             // std names don't require `N..E`
1550             buf.writestring("St");
1551             this.writeIdentifier(t.name);
1552             this.append(t);
1553             return dg();
1554         }
1555         else if (sym2)
1556         {
1557             buf.writestring("N");
1558             if (!this.substitute(sym2))
1559                 sym2.accept(this);
1560         }
1561         this.writeNamespace(
1562             sym1.cppnamespace, () {
1563                 this.writeIdentifier(t.name);
1564                 this.append(t);
1565                 dg();
1566             });
1567         if (sym2)
1568             buf.writestring("E");
1569     }
1570 
1571 extern(C++):
1572 
1573     alias visit = Visitor.visit;
1574 
1575     override void visit(TypeNull t)
1576     {
1577         if (t.isImmutable() || t.isShared())
1578             return error(t);
1579 
1580         writeBasicType(t, 'D', 'n');
1581     }
1582 
1583     override void visit(TypeBasic t)
1584     {
1585         if (t.isImmutable() || t.isShared())
1586             return error(t);
1587 
1588         // Handle any target-specific basic types.
1589         if (auto tm = target.cpp.typeMangle(t))
1590         {
1591             // Only do substitutions for non-fundamental types.
1592             if (!isFundamentalType(t) || t.isConst())
1593             {
1594                 if (substitute(t))
1595                     return;
1596                 else
1597                     append(t);
1598             }
1599             CV_qualifiers(t);
1600             buf.writestring(tm);
1601             return;
1602         }
1603 
1604         /* <builtin-type>:
1605          * v        void
1606          * w        wchar_t
1607          * b        bool
1608          * c        char
1609          * a        signed char
1610          * h        unsigned char
1611          * s        short
1612          * t        unsigned short
1613          * i        int
1614          * j        unsigned int
1615          * l        long
1616          * m        unsigned long
1617          * x        long long, __int64
1618          * y        unsigned long long, __int64
1619          * n        __int128
1620          * o        unsigned __int128
1621          * f        float
1622          * d        double
1623          * e        long double, __float80
1624          * g        __float128
1625          * z        ellipsis
1626          * Dd       64 bit IEEE 754r decimal floating point
1627          * De       128 bit IEEE 754r decimal floating point
1628          * Df       32 bit IEEE 754r decimal floating point
1629          * Dh       16 bit IEEE 754r half-precision floating point
1630          * Di       char32_t
1631          * Ds       char16_t
1632          * u <source-name>  # vendor extended type
1633          */
1634         char c;
1635         char p = 0;
1636         switch (t.ty)
1637         {
1638             case Tvoid:                 c = 'v';        break;
1639             case Tint8:                 c = 'a';        break;
1640             case Tuns8:                 c = 'h';        break;
1641             case Tint16:                c = 's';        break;
1642             case Tuns16:                c = 't';        break;
1643             case Tint32:                c = 'i';        break;
1644             case Tuns32:                c = 'j';        break;
1645             case Tfloat32:              c = 'f';        break;
1646             case Tint64:
1647                 c = target.c.longsize == 8 ? 'l' : 'x';
1648                 break;
1649             case Tuns64:
1650                 c = target.c.longsize == 8 ? 'm' : 'y';
1651                 break;
1652             case Tint128:                c = 'n';       break;
1653             case Tuns128:                c = 'o';       break;
1654             case Tfloat64:               c = 'd';       break;
1655             case Tfloat80:               c = 'e';       break;
1656             case Tbool:                  c = 'b';       break;
1657             case Tchar:                  c = 'c';       break;
1658             case Twchar:        p = 'D'; c = 's';       break;  // since C++11
1659             case Tdchar:        p = 'D'; c = 'i';       break;  // since C++11
1660             case Timaginary32:  p = 'G'; c = 'f';       break;  // 'G' means imaginary
1661             case Timaginary64:  p = 'G'; c = 'd';       break;
1662             case Timaginary80:  p = 'G'; c = 'e';       break;
1663             case Tcomplex32:    p = 'C'; c = 'f';       break;  // 'C' means complex
1664             case Tcomplex64:    p = 'C'; c = 'd';       break;
1665             case Tcomplex80:    p = 'C'; c = 'e';       break;
1666 
1667             default:
1668                 return error(t);
1669         }
1670         writeBasicType(t, p, c);
1671     }
1672 
1673     override void visit(TypeVector t)
1674     {
1675         if (t.isImmutable() || t.isShared())
1676             return error(t);
1677 
1678         if (substitute(t))
1679             return;
1680         append(t);
1681         CV_qualifiers(t);
1682 
1683         // Handle any target-specific vector types.
1684         if (auto tm = target.cpp.typeMangle(t))
1685         {
1686             buf.writestring(tm);
1687         }
1688         else
1689         {
1690             assert(t.basetype && t.basetype.ty == Tsarray);
1691             assert((cast(TypeSArray)t.basetype).dim);
1692             version (none)
1693             {
1694                 buf.writestring("Dv");
1695                 buf.print((cast(TypeSArray *)t.basetype).dim.toInteger()); // -- Gnu ABI v.4
1696                 buf.writeByte('_');
1697             }
1698             else
1699                 buf.writestring("U8__vector"); //-- Gnu ABI v.3
1700             t.basetype.nextOf().accept(this);
1701         }
1702     }
1703 
1704     override void visit(TypeSArray t)
1705     {
1706         if (t.isImmutable() || t.isShared())
1707             return error(t);
1708 
1709         if (!substitute(t))
1710             append(t);
1711         CV_qualifiers(t);
1712         buf.writeByte('A');
1713         buf.print(t.dim ? t.dim.toInteger() : 0);
1714         buf.writeByte('_');
1715         t.next.accept(this);
1716     }
1717 
1718     override void visit(TypePointer t)
1719     {
1720         if (t.isImmutable() || t.isShared())
1721             return error(t);
1722 
1723         // Check for const - Since we cannot represent C++'s `char* const`,
1724         // and `const char* const` (a.k.a `const(char*)` in D) is mangled
1725         // the same as `const char*` (`const(char)*` in D), we need to add
1726         // an extra `K` if `nextOf()` is `const`, before substitution
1727         CV_qualifiers(t);
1728         if (substitute(t))
1729             return;
1730         buf.writeByte('P');
1731         auto prev = this.context.push(this.context.res.asType().nextOf());
1732         scope (exit) this.context.pop(prev);
1733         t.next.accept(this);
1734         append(t);
1735     }
1736 
1737     override void visit(TypeReference t)
1738     {
1739         if (substitute(t))
1740             return;
1741         buf.writeByte('R');
1742         CV_qualifiers(t.nextOf());
1743         headOfType(t.nextOf());
1744         if (t.nextOf().isConst())
1745             append(t.nextOf());
1746         append(t);
1747     }
1748 
1749     override void visit(TypeFunction t)
1750     {
1751         /*
1752          *  <function-type> ::= F [Y] <bare-function-type> E
1753          *  <bare-function-type> ::= <signature type>+
1754          *  # types are possible return type, then parameter types
1755          */
1756         /* ABI says:
1757             "The type of a non-static member function is considered to be different,
1758             for the purposes of substitution, from the type of a namespace-scope or
1759             static member function whose type appears similar. The types of two
1760             non-static member functions are considered to be different, for the
1761             purposes of substitution, if the functions are members of different
1762             classes. In other words, for the purposes of substitution, the class of
1763             which the function is a member is considered part of the type of
1764             function."
1765 
1766             BUG: Right now, types of functions are never merged, so our simplistic
1767             component matcher always finds them to be different.
1768             We should use Type.equals on these, and use different
1769             TypeFunctions for non-static member functions, and non-static
1770             member functions of different classes.
1771          */
1772         if (substitute(t))
1773             return;
1774         buf.writeByte('F');
1775         if (t.linkage == LINK.c)
1776             buf.writeByte('Y');
1777         Type tn = t.next;
1778         if (t.isref)
1779             tn = tn.referenceTo();
1780         tn.accept(this);
1781         mangleFunctionParameters(t.parameterList.parameters, t.parameterList.varargs);
1782         buf.writeByte('E');
1783         append(t);
1784     }
1785 
1786     override void visit(TypeStruct t)
1787     {
1788         if (t.isImmutable() || t.isShared())
1789             return error(t);
1790         //printf("TypeStruct %s\n", t.toChars());
1791         doSymbol(t);
1792     }
1793 
1794     override void visit(TypeEnum t)
1795     {
1796         if (t.isImmutable() || t.isShared())
1797             return error(t);
1798 
1799         /* __c_(u)long(long) get special mangling
1800          */
1801         const id = t.sym.ident;
1802         //printf("enum id = '%s'\n", id.toChars());
1803         if (id == Id.__c_long)
1804             return writeBasicType(t, 0, 'l');
1805         else if (id == Id.__c_ulong)
1806             return writeBasicType(t, 0, 'm');
1807         else if (id == Id.__c_wchar_t)
1808             return writeBasicType(t, 0, 'w');
1809         else if (id == Id.__c_longlong)
1810             return writeBasicType(t, 0, 'x');
1811         else if (id == Id.__c_ulonglong)
1812             return writeBasicType(t, 0, 'y');
1813 
1814         doSymbol(t);
1815     }
1816 
1817     override void visit(TypeClass t)
1818     {
1819         mangleTypeClass(t, false);
1820     }
1821 
1822     /**
1823      * Performs template parameter substitution
1824      *
1825      * Mangling is performed on a copy of the post-parsing AST before
1826      * any semantic pass is run.
1827      * There is no easy way to link a type to the template parameters
1828      * once semantic has run, because:
1829      * - the `TemplateInstance` installs aliases in its scope to its params
1830      * - `AliasDeclaration`s are resolved in many places
1831      * - semantic passes are destructive, so the `TypeIdentifier` gets lost
1832      *
1833      * As a result, the best approach with the current architecture is to:
1834      * - Run the visitor on the `originalType` of the function,
1835      *   looking up any `TypeIdentifier` at the template scope when found.
1836      * - Fallback to the post-semantic `TypeFunction` when the identifier is
1837      *   not a template parameter.
1838      */
1839     override void visit(TypeIdentifier t)
1840     {
1841         auto decl = cast(TemplateDeclaration)this.context.ti.tempdecl;
1842         assert(decl.parameters !is null);
1843         auto idx = templateParamIndex(t.ident, decl.parameters);
1844         // If not found, default to the post-semantic type
1845         if (idx >= decl.parameters.length)
1846             return this.context.res.visitObject(this);
1847 
1848         auto param = (*decl.parameters)[idx];
1849         if (auto type = this.context.res.isType())
1850             CV_qualifiers(type);
1851         // Otherwise, attempt substitution (`S_` takes precedence on `T_`)
1852         if (this.substitute(param))
1853             return;
1854 
1855         // If substitution failed, write `TX_` where `X` is the index
1856         this.writeTemplateArgIndex(idx, param);
1857         this.append(param);
1858         // Write the ABI tags, if any
1859         if (auto sym = this.context.res.isDsymbol())
1860             this.abiTags.writeSymbol(sym, this);
1861     }
1862 
1863     /// Ditto
1864     override void visit(TypeInstance t)
1865     {
1866         assert(t.tempinst !is null);
1867         t.tempinst.accept(this);
1868     }
1869 
1870     /**
1871      * Mangles a `TemplateInstance`
1872      *
1873      * A `TemplateInstance` can be found either in the parameter,
1874      * or the return value.
1875      * Arguments to the template instance needs to be mangled but the template
1876      * can be partially substituted, so for example the following:
1877      * `Container!(T, Val) func16479_12 (alias Container, T, int Val) ()`
1878      * will mangle the return value part to "T_IT0_XT1_EE"
1879      */
1880     override void visit(TemplateInstance t)
1881     {
1882         // Template names are substituted, but args still need to be written
1883         void writeArgs ()
1884         {
1885             buf.writeByte('I');
1886             // When visiting the arguments, the context will be set to the
1887             // resolved type
1888             auto analyzed_ti = this.context.res.asType().toDsymbol(null).isInstantiated();
1889             auto prev = this.context;
1890             scope (exit) this.context.pop(prev);
1891             foreach (idx, RootObject o; *t.tiargs)
1892             {
1893                 this.context.res = (*analyzed_ti.tiargs)[idx];
1894                 o.visitObject(this);
1895             }
1896             if (analyzed_ti.tiargs.dim > t.tiargs.dim)
1897             {
1898                 // If the resolved AST has more args than the parse one,
1899                 // we have default arguments
1900                 auto oparams = (cast(TemplateDeclaration)analyzed_ti.tempdecl).origParameters;
1901                 foreach (idx, arg; (*oparams)[t.tiargs.dim .. $])
1902                 {
1903                     this.context.res = (*analyzed_ti.tiargs)[idx + t.tiargs.dim];
1904 
1905                     if (auto ttp = arg.isTemplateTypeParameter())
1906                         ttp.defaultType.accept(this);
1907                     else if (auto tvp = arg.isTemplateValueParameter())
1908                         tvp.defaultValue.accept(this);
1909                     else if (auto tvp = arg.isTemplateThisParameter())
1910                         tvp.defaultType.accept(this);
1911                     else if (auto tvp = arg.isTemplateAliasParameter())
1912                         tvp.defaultAlias.visitObject(this);
1913                     else
1914                         assert(0, arg.toString());
1915                 }
1916             }
1917             buf.writeByte('E');
1918         }
1919 
1920         // `name` is used, not `ident`
1921         assert(t.name !is null);
1922         assert(t.tiargs !is null);
1923 
1924         bool needsTa;
1925         auto decl = cast(TemplateDeclaration)this.context.ti.tempdecl;
1926         // Attempt to substitute the template itself
1927         auto idx = templateParamIndex(t.name, decl.parameters);
1928         if (idx < decl.parameters.length)
1929         {
1930             auto param = (*decl.parameters)[idx];
1931             if (auto type = t.getType())
1932                 CV_qualifiers(type);
1933             if (this.substitute(param))
1934                 return;
1935             this.writeTemplateArgIndex(idx, param);
1936             this.append(param);
1937             writeArgs();
1938         }
1939         else if (this.writeStdSubstitution(t, needsTa))
1940         {
1941             if (needsTa)
1942                 writeArgs();
1943         }
1944         else if (!this.substitute(t))
1945             this.writeQualified(t, &writeArgs);
1946     }
1947 
1948     /// Ditto
1949     override void visit(IntegerExp t)
1950     {
1951         this.buf.writeByte('L');
1952         t.type.accept(this);
1953         this.buf.print(t.getInteger());
1954         this.buf.writeByte('E');
1955     }
1956 
1957     override void visit(Nspace t)
1958     {
1959         if (auto p = getQualifier(t))
1960             p.accept(this);
1961 
1962         if (isStd(t))
1963             buf.writestring("St");
1964         else
1965         {
1966             this.writeIdentifier(t.ident);
1967             this.append(t);
1968         }
1969     }
1970 
1971     override void visit(Type t)
1972     {
1973         error(t);
1974     }
1975 
1976     void visit(Tuple t)
1977     {
1978         assert(0);
1979     }
1980 }
1981 
1982 /// Helper code to visit `RootObject`, as it doesn't define `accept`,
1983 /// only its direct subtypes do.
1984 private void visitObject(V : Visitor)(RootObject o, V this_)
1985 {
1986     assert(o !is null);
1987     if (Type ta = isType(o))
1988         ta.accept(this_);
1989     else if (Expression ea = isExpression(o))
1990         ea.accept(this_);
1991     else if (Dsymbol sa = isDsymbol(o))
1992         sa.accept(this_);
1993     else if (TemplateParameter t = isTemplateParameter(o))
1994         t.accept(this_);
1995     else if (Tuple t = isTuple(o))
1996         // `Tuple` inherits `RootObject` and does not define accept
1997         // For this reason, this uses static dispatch on the visitor
1998         this_.visit(t);
1999     else
2000         assert(0, o.toString());
2001 }
2002 
2003 /// Helper function to safely get a type out of a `RootObject`
2004 private Type asType(RootObject o)
2005 {
2006     Type ta = isType(o);
2007     assert(ta !is null, o.toString());
2008     return ta;
2009 }
2010 
2011 /// Helper function to safely get a `FuncDeclaration` out of a `RootObject`
2012 private FuncDeclaration asFuncDecl(RootObject o)
2013 {
2014     Dsymbol d = isDsymbol(o);
2015     assert(d !is null);
2016     auto fd = d.isFuncDeclaration();
2017     assert(fd !is null);
2018     return fd;
2019 }
2020 
2021 /// Helper class to compare entries in components
2022 private extern(C++) final class ComponentVisitor : Visitor
2023 {
2024     /// Only one of the following is not `null`, it's always
2025     /// the most specialized type, set from the ctor
2026     private Nspace namespace;
2027 
2028     /// Ditto
2029     private CPPNamespaceDeclaration namespace2;
2030 
2031     /// Ditto
2032     private TypePointer tpointer;
2033 
2034     /// Ditto
2035     private TypeReference tref;
2036 
2037     /// Ditto
2038     private TypeIdentifier tident;
2039 
2040     /// Least specialized type
2041     private RootObject object;
2042 
2043     /// Set to the result of the comparison
2044     private bool result;
2045 
2046     public this(RootObject base)
2047     {
2048         switch (base.dyncast())
2049         {
2050         case DYNCAST.dsymbol:
2051             if (auto ns = (cast(Dsymbol)base).isNspace())
2052                 this.namespace = ns;
2053             else if (auto ns = (cast(Dsymbol)base).isCPPNamespaceDeclaration())
2054                 this.namespace2 = ns;
2055             else
2056                 goto default;
2057             break;
2058 
2059         case DYNCAST.type:
2060             auto t = cast(Type)base;
2061             if (t.ty == Tpointer)
2062                 this.tpointer = cast(TypePointer)t;
2063             else if (t.ty == Treference)
2064                 this.tref = cast(TypeReference)t;
2065             else if (t.ty == Tident)
2066                 this.tident = cast(TypeIdentifier)t;
2067             else
2068                 goto default;
2069             break;
2070 
2071         // Note: ABI tags are also handled here (they are TupleExp of StringExp)
2072         default:
2073             this.object = base;
2074         }
2075     }
2076 
2077     /// Introduce base class overloads
2078     alias visit = Visitor.visit;
2079 
2080     /// Least specialized overload of each direct child of `RootObject`
2081     public override void visit(Dsymbol o)
2082     {
2083         this.result = this.object && this.object == o;
2084     }
2085 
2086     /// Ditto
2087     public override void visit(Expression o)
2088     {
2089         this.result = this.object && this.object == o;
2090     }
2091 
2092     /// Ditto
2093     public void visit(Tuple o)
2094     {
2095         this.result = this.object && this.object == o;
2096     }
2097 
2098     /// Ditto
2099     public override void visit(Type o)
2100     {
2101         this.result = this.object && this.object == o;
2102     }
2103 
2104     /// Ditto
2105     public override void visit(TemplateParameter o)
2106     {
2107         this.result = this.object && this.object == o;
2108     }
2109 
2110     /**
2111      * This overload handles composed types including template parameters
2112      *
2113      * Components for substitutions include "next" type.
2114      * For example, if `ref T` is present, `ref T` and `T` will be present
2115      * in the substitution array.
2116      * But since we don't have the final/merged type, we cannot rely on
2117      * object comparison, and need to recurse instead.
2118      */
2119     public override void visit(TypeReference o)
2120     {
2121         if (!this.tref)
2122             return;
2123         if (this.tref == o)
2124             this.result = true;
2125         else
2126         {
2127             // It might be a reference to a template parameter that we already
2128             // saw, so we need to recurse
2129             scope v = new ComponentVisitor(this.tref.next);
2130             o.next.visitObject(v);
2131             this.result = v.result;
2132         }
2133     }
2134 
2135     /// Ditto
2136     public override void visit(TypePointer o)
2137     {
2138         if (!this.tpointer)
2139             return;
2140         if (this.tpointer == o)
2141             this.result = true;
2142         else
2143         {
2144             // It might be a pointer to a template parameter that we already
2145             // saw, so we need to recurse
2146             scope v = new ComponentVisitor(this.tpointer.next);
2147             o.next.visitObject(v);
2148             this.result = v.result;
2149         }
2150     }
2151 
2152     /// Ditto
2153     public override void visit(TypeIdentifier o)
2154     {
2155         /// Since we know they are at the same level, scope resolution will
2156         /// give us the same symbol, thus we can just compare ident.
2157         this.result = (this.tident && (this.tident.ident == o.ident));
2158     }
2159 
2160     /**
2161      * Overload which accepts a Namespace
2162      *
2163      * It is very common for large C++ projects to have multiple files sharing
2164      * the same `namespace`. If any D project adopts the same approach
2165      * (e.g. separating data structures from functions), it will lead to two
2166      * `Nspace` objects being instantiated, with different addresses.
2167      * At the same time, we cannot compare just any Dsymbol via identifier,
2168      * because it messes with templates.
2169      *
2170      * See_Also:
2171      *  https://issues.dlang.org/show_bug.cgi?id=18922
2172      *
2173      * Params:
2174      *   ns = C++ namespace to do substitution for
2175      */
2176     public override void visit(Nspace ns)
2177     {
2178         this.result = isNamespaceEqual(this.namespace, ns)
2179             || isNamespaceEqual(this.namespace2, ns);
2180     }
2181 
2182     /// Ditto
2183     public override void visit(CPPNamespaceDeclaration ns)
2184     {
2185         this.result = isNamespaceEqual(this.namespace, ns)
2186             || isNamespaceEqual(this.namespace2, ns);
2187     }
2188 }
2189 
2190 /// Transitional functions for `CPPNamespaceDeclaration` / `Nspace`
2191 /// Remove when `Nspace` is removed.
2192 private bool isNamespaceEqual (Nspace a, Nspace b)
2193 {
2194     if (a is null || b is null)
2195         return false;
2196     return a.equals(b);
2197 }
2198 
2199 /// Ditto
2200 private bool isNamespaceEqual (Nspace a, CPPNamespaceDeclaration b)
2201 {
2202     return isNamespaceEqual(b, a);
2203 }
2204 
2205 /// Ditto
2206 private bool isNamespaceEqual (CPPNamespaceDeclaration a, Nspace b, size_t idx = 0)
2207 {
2208     if ((a is null) != (b is null))
2209         return false;
2210     if (!a.ident.equals(b.ident))
2211         return false;
2212 
2213     // We need to see if there's more ident enclosing
2214     if (auto pb = b.toParent().isNspace())
2215         return isNamespaceEqual(a.cppnamespace, pb);
2216     else
2217         return a.cppnamespace is null;
2218 }
2219 
2220 /// Returns:
2221 ///   Whether  two `CPPNamespaceDeclaration` are equals
2222 private bool isNamespaceEqual (CPPNamespaceDeclaration a, CPPNamespaceDeclaration b)
2223 {
2224     if (a is null || b is null)
2225         return false;
2226 
2227     if ((a.cppnamespace is null) != (b.cppnamespace is null))
2228         return false;
2229     if (a.ident != b.ident)
2230         return false;
2231     return a.cppnamespace is null ? true : isNamespaceEqual(a.cppnamespace, b.cppnamespace);
2232 }
2233 
2234 /**
2235  * A container for ABI tags
2236  *
2237  * At its hearth, there is a sorted array of ABI tags having been written
2238  * already. ABI tags can be present on parameters, template parameters,
2239  * return value, and varaible. ABI tags for a given type needs to be written
2240  * sorted. When a function returns a type that has ABI tags, only the tags that
2241  * haven't been printed as part of the mangling (e.g. arguments) are written
2242  * directly after the function name.
2243  *
2244  * This means that:
2245  * ---
2246  * /++ C++ type definitions:
2247  * struct [[gnu::abi_tag("tag1")]] Struct1 {};
2248  * struct [[gnu::abi_tag("tag2")]] Struct2 {};
2249  * // Can also be: "tag2", "tag1", since tags are sorted.
2250  * struct [[gnu::abi_tag("tag1", "tag2")]] Struct3 {};
2251  * +/
2252  * // Functions definitions:
2253  * Struct3 func1 (Struct1);
2254  * Struct3 func2 (Struct2);
2255  * Struct3 func3 (Struct2, Struct1);
2256  * ---
2257  * Will be respectively pseudo-mangled (part of interest between stars) as:
2258  * "_Z4 func1 *B4tag2* ParamsMangling" (ParamsMangling includes tag1),
2259  * "_Z4 func2 *B4tag1* ParamsMangling" (ParamsMangling includes tag2),
2260  * "_Z4 func2 *B4tag1* ParamsMangling" (ParamsMangling includes both).
2261  *
2262  * This is why why need to keep a list of tags that were written,
2263  * and insert the missing one after parameter mangling has been written.
2264  * Since there's a lot of operations that are not easily doable in DMD
2265  * (since we can't use Phobos), this special container is implemented.
2266  */
2267 private struct ABITagContainer
2268 {
2269     private Array!StringExp written;
2270 
2271     static ArrayLiteralExp forSymbol (Dsymbol s)
2272     {
2273         if (!s)
2274             return null;
2275         // If this is a template instance, we want the declaration,
2276         // as that's where the UDAs are
2277         if (auto ti = s.isTemplateInstance())
2278             s = ti.tempdecl;
2279         if (!s.userAttribDecl || !s.userAttribDecl.atts)
2280             return null;
2281 
2282         foreach (exp; *s.userAttribDecl.atts)
2283         {
2284             if (UserAttributeDeclaration.isGNUABITag(exp))
2285                 return (*exp.isStructLiteralExp().elements)[0]
2286                     .isArrayLiteralExp();
2287         }
2288         return null;
2289     }
2290 
2291     void writeSymbol(Dsymbol s, CppMangleVisitor self)
2292     {
2293         auto tale = forSymbol(s);
2294         if (!tale) return;
2295         if (self.substitute(tale))
2296             return;
2297         this.write(*self.buf, tale);
2298     }
2299 
2300     /**
2301      * Write an ArrayLiteralExp (expected to be an ABI tag) to the buffer
2302      *
2303      * Params:
2304      *   buf = Buffer to write mangling to
2305      *   ale = GNU ABI tag array literal expression, semantically analyzed
2306      */
2307     void write (ref OutBuffer buf, ArrayLiteralExp ale, bool skipKnown = false)
2308     {
2309         void writeElem (StringExp exp)
2310         {
2311             const tag = exp.peekString();
2312             buf.writestring("B");
2313             buf.print(tag.length);
2314             buf.writestring(tag);
2315         }
2316 
2317         bool match;
2318         foreach (exp; *ale.elements)
2319         {
2320             auto elem = exp.toStringExp();
2321             auto idx = closestIndex(this.written[], elem, match);
2322             if (!match)
2323             {
2324                 writeElem(elem);
2325                 this.written.insert(idx, elem);
2326             }
2327             else if (!skipKnown)
2328                 writeElem(elem);
2329         }
2330     }
2331 }
2332 
2333 /**
2334  * Returns the closest index to to `exp` in `slice`
2335  *
2336  * Performs a binary search on `slice` (assumes `slice` is sorted),
2337  * and returns either `exp`'s index in `slice` if `exact` is `true`,
2338  * or the index at which `exp` can be inserted in `slice` if `exact is `false`.
2339  * Inserting `exp` at the return value will keep the array sorted.
2340  *
2341  * Params:
2342  *   slice = The sorted slice to search into
2343  *   exp   = The string expression to search for
2344  *   exact = If `true` on return, `exp` was found in `slice`
2345  *
2346  * Returns:
2347  *   Either the index to insert `exp` at (if `exact == false`),
2348  *   or the index of `exp` in `slice`.
2349  */
2350 private size_t closestIndex (const(StringExp)[] slice, StringExp exp, out bool exact)
2351 {
2352     if (!slice.length) return 0;
2353 
2354     const StringExp* first = slice.ptr;
2355     while (true)
2356     {
2357         int res = dstrcmp(exp.peekString(), slice[$ / 2].peekString());
2358         if (res == 0)
2359         {
2360             exact = true;
2361             return (&slice[$/2] - first);
2362         }
2363 
2364         if (slice.length == 1)
2365             return (slice.ptr - first) + (res > 0);
2366         slice = slice[(res > 0 ? $ / 2 : 0) .. (res > 0 ? $ : $ / 2)];
2367     }
2368 }
2369 
2370 //
2371 unittest
2372 {
2373     bool match;
2374     auto s1 = new StringExp(Loc.initial, "Amande");
2375     auto s2 = new StringExp(Loc.initial, "Baguette");
2376     auto s3 = new StringExp(Loc.initial, "Croissant");
2377     auto s4 = new StringExp(Loc.initial, "Framboises");
2378     auto s5 = new StringExp(Loc.initial, "Proscuitto");
2379 
2380     // Found, odd size
2381     assert(closestIndex([s1, s2, s3, s4, s5], s1, match) == 0 && match);
2382     assert(closestIndex([s1, s2, s3, s4, s5], s2, match) == 1 && match);
2383     assert(closestIndex([s1, s2, s3, s4, s5], s3, match) == 2 && match);
2384     assert(closestIndex([s1, s2, s3, s4, s5], s4, match) == 3 && match);
2385     assert(closestIndex([s1, s2, s3, s4, s5], s5, match) == 4 && match);
2386 
2387     // Not found, even size
2388     assert(closestIndex([s2, s3, s4, s5], s1, match) == 0 && !match);
2389     assert(closestIndex([s1, s3, s4, s5], s2, match) == 1 && !match);
2390     assert(closestIndex([s1, s2, s4, s5], s3, match) == 2 && !match);
2391     assert(closestIndex([s1, s2, s3, s5], s4, match) == 3 && !match);
2392     assert(closestIndex([s1, s2, s3, s4], s5, match) == 4 && !match);
2393 
2394     // Found, even size
2395     assert(closestIndex([s1, s2, s3, s4], s1, match) == 0 && match);
2396     assert(closestIndex([s1, s2, s3, s4], s2, match) == 1 && match);
2397     assert(closestIndex([s1, s2, s3, s4], s3, match) == 2 && match);
2398     assert(closestIndex([s1, s2, s3, s4], s4, match) == 3 && match);
2399     assert(closestIndex([s1, s3, s4, s5], s5, match) == 3 && match);
2400 
2401     // Not found, odd size
2402     assert(closestIndex([s2, s4, s5], s1, match) == 0 && !match);
2403     assert(closestIndex([s1, s4, s5], s2, match) == 1 && !match);
2404     assert(closestIndex([s1, s2, s4], s3, match) == 2 && !match);
2405     assert(closestIndex([s1, s3, s5], s4, match) == 2 && !match);
2406     assert(closestIndex([s1, s2, s4], s5, match) == 3 && !match);
2407 }
2408 
2409 /**
2410  * Visits the return type of a function and writes leftover ABI tags
2411  */
2412 extern(C++) private final class LeftoverVisitor : Visitor
2413 {
2414     /// List of tags to write
2415     private Array!StringExp toWrite;
2416     /// List of tags to ignore
2417     private const(Array!StringExp)* ignore;
2418 
2419     ///
2420     public this(const(Array!StringExp)* previous)
2421     {
2422         this.ignore = previous;
2423     }
2424 
2425     /// Reintroduce base class overloads
2426     public alias visit = Visitor.visit;
2427 
2428     /// Least specialized overload of each direct child of `RootObject`
2429     public override void visit(Dsymbol o)
2430     {
2431         auto ale = ABITagContainer.forSymbol(o);
2432         if (!ale) return;
2433 
2434         bool match;
2435         foreach (elem; *ale.elements)
2436         {
2437             auto se = elem.toStringExp();
2438             closestIndex((*this.ignore)[], se, match);
2439             if (match) continue;
2440             auto idx = closestIndex(this.toWrite[], se, match);
2441             if (!match)
2442                 this.toWrite.insert(idx, se);
2443         }
2444     }
2445 
2446     /// Ditto
2447     public override void visit(Type o)
2448     {
2449         if (auto sym = o.toDsymbol(null))
2450             sym.accept(this);
2451     }
2452 
2453     /// Composite type
2454     public override void visit(TypePointer o)
2455     {
2456         o.next.accept(this);
2457     }
2458 
2459     public override void visit(TypeReference o)
2460     {
2461         o.next.accept(this);
2462     }
2463 }