123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404
/**
 *   D symbol name demangling
 *
 *   Attempts to demangle D symbols generated by the DMD frontend.
 *   (Which is not always technically possible)
 *
 *  A sample program demangling the names passed as arguments
 * {{{
 *   module demangle;
 *   import tango.core.tools.Demangler;
 *   import tango.io.Stdout;
 *
 *   void usage(){
 *       Stdout("demangle [--help] [--level 0-9] mangledName1 [mangledName2...]").newline;
 *   }
 *
 *   int main(char[][]args){
 *       uint start=1;
 *       if (args.length>1) {
 *           if (args[start]=="--help"){
 *               usage();
 *               ++start;
 *           }
 *           if (args[start]=="--level"){
 *               ++start;
 *               if (args.length==start || args[start].length!=1 || args[start][0]<'0' || 
 *                   args[start][0]>'9') {
 *                   Stdout("invalid level '")((args.length==start)?"*missing*":args[start])
 *                       ("' (must be 0-9)").newline;
 *                   usage();
 *                   return 2;
 *               }
 *               demangler.verbosity=args[start+1][0]-'0';
 *               ++start;
 *           }
 *       } else {
 *           usage();
 *           return 0;
 *       }
 *       foreach (n;args[start..$]){
 *           Stdout(demangler.demangle(n)).newline;
 *       }
 *       return 0;
 *   }
 * }}}
 *  Copyright: Copyright (C) 2007-2008 Zygfryd (aka Hxal), Fawzi. All rights reserved.
 *  License:   tango license, apache 2.0
 *  Authors:   Zygfryd (aka Hxal), Fawzi
 *
 */

module tango.core.tools.Demangler;

import tango.core.Traits: ctfe_i2a;
import tango.stdc.string: memmove,memcpy;

debug(traceDemangler) import tango.io.Stdout;



version(DigitalMars) version(Windows) {
    bool isMD5Hashed(char[] name) {
        if (name.length < 34 || (name.length >= 2 && name[0..2] != "_D")) {
            return false;
        }
        
        foreach (c; name[$-32..$]) {
            if ((c < '0' || c > '9') && (c < 'A' || c > 'F')) {
                return false;
            }
        }
        
        return true;
    }
    

    char[] decompressOMFSymbol(char[] garbled, char[]* buf) {
        int ungarbledLength = 0;
        bool compressed = false;

        for (int ci = 0; ci < garbled.length; ++ci) {
            char c = garbled[ci];
            if (0 == (c & 0x80)) {
                ++ungarbledLength;
            } else {
                compressed = true;
                int matchLen = void;

                if (c & 0x40) {
                    matchLen = (c & 0b111) + 1;
                } else {
                    if (ci+2 >= garbled.length) {
                        return garbled;
                    } else {
                        matchLen = cast(int)(c & 0x38) << 4;
                        matchLen += garbled[ci+1] & ~0x80;
                        ci += 2;
                    }
                }

                ungarbledLength += matchLen;
            }
        }

        if (!compressed || ungarbledLength > (*buf).length) {
            return garbled;
        } else {
            char[] ungarbled = (*buf)[$-ungarbledLength..$];
            *buf = (*buf)[0..$-ungarbledLength];
            int ui = 0;

            for (int ci = 0; ci < garbled.length; ++ci) {
                char c = garbled[ci];
                if (0 == (c & 0x80)) {
                    ungarbled[ui++] = c;
                } else {
                    int matchOff = void;
                    int matchLen = void;

                    if (c & 0x40) {
                        matchOff = ((c >> 3) & 0b111) + 1;
                        matchLen = (c & 0b111) + 1;
                    } else {
                        matchOff = cast(int)(c & 0b111) << 7;
                        matchLen = cast(int)(c & 0x38) << 4;
                        matchLen += garbled[ci+1] & ~0x80;
                        matchOff += garbled[ci+2] & ~0x80;
                        ci += 2;
                    }

                    int matchStart = ui - matchOff;
                    if (matchStart + matchLen > ui) {
                        // fail
                        return garbled;
                    }

                    char[] match = ungarbled[matchStart .. matchStart + matchLen];
                    ungarbled[ui .. ui+matchLen] = match;
                    ui += matchLen;
                }
            }

            return ungarbled;
        }
    }
}


/// decompresses a symbol and returns the full symbol, and possibly a reduced buffer space
/// (does something only on windows with DMD)
char[] decompressSymbol(char[]func,char[]*buf){
    version(DigitalMars) version(Windows){
        if (isMD5Hashed(func)) {
            func = func[0..$-32];
        }
        func = decompressOMFSymbol(func, buf);
    }
    return func;
}

uint toUint(char[]s){
    uint res=0;
    for (int i=0;i<s.length;++i){
        if (s[i]>='0'&& s[i]<='9'){
            res*=10;
            res+=s[i]-'0';
        } else {
            assert(false);
        }
    }
    return res;
}

/**
 *   Flexible demangler
 *   Attempts to demangle D symbols generated by the DMD frontend.
 *   (Which is not always technically possible)
 */
public class Demangler
{
    /** How deeply to recurse printing template parameters,
      * for depths greater than this, an ellipsis is used */
    uint templateExpansionDepth = 1;

    /** Skip default members of templates (sole members named after
      * the template) */
    bool foldDefaults = false;

    /** Print types of functions being part of the main symbol */
    bool expandFunctionTypes = false;

    /** For composite types, print the kind (class|struct|etc.) of the type */
    bool printTypeKind = false;

    /** sets the verbosity level of the demangler (template expansion level,...) */
    public void verbosity (uint level)
    {
        switch (level)
        {
            case 0:
                templateExpansionDepth = 0;
                expandFunctionTypes = false;
                printTypeKind = false;
                break;

            case 1:
                templateExpansionDepth = 1;
                expandFunctionTypes = false;
                printTypeKind = false;
                break;

            case 2:
                templateExpansionDepth = 1;
                expandFunctionTypes = false;
                printTypeKind = true;
                break;

            case 3:
                templateExpansionDepth = 1;
                expandFunctionTypes = true;
                printTypeKind = true;
                break;

            default:
                templateExpansionDepth = level - 2;
                expandFunctionTypes = true;
                printTypeKind = true;
        }
    }

    /** creates a demangler */
    this ()
    {
        verbosity (1);
    }

    /** creates a demangler with the given verbosity level */
    this (uint verbosityLevel)
    {
        verbosity (verbosityLevel);
    }
    
    /** demangles the given string */
    public char[] demangle (char[] input)
    {
        char[4096] buf=void;
        auto res=DemangleInstance(this,input,buf);
        if (res.mangledName() && res.input.length==0){
            return res.slice.dup;
        } else {
            if (res.slice.length) res.output.append(" ");
            if (res.type() && res.input.length==0){
                return res.slice.dup;
            } else {
                return input;
            }
        }
    }

    /** demangles the given string using output to hold the result */
    public char[] demangle (char[] input, char[] output)
    {
        auto res=DemangleInstance(this,input,output);
        if (res.mangledName () && res.input.length==0) {
            return res.slice;
        } else {
            if (res.slice.length) res.output.append(" ");
            if (res.type() && res.input.length==0) {
                return res.slice;
            } else {
                return input;
            }
        }
    }

    /// this represents a single demangling request, and is the place where the real work is done
    /// some more cleanup would probably be in order (maybe remove Buffer)
    struct DemangleInstance{
        debug(traceDemangler) private char[][] _trace;
        private char[] input;
        private uint _templateDepth;
        Buffer output;
        Demangler prefs;
        
        struct BufState{
            DemangleInstance* dem;
            char[] input;
            size_t len;
            static BufState opCall(DemangleInstance* dem){
                BufState res;
                res.dem=dem;
                res.len=dem.output.length;
                res.input=dem.input;
                return res;
            }
            // resets input and output buffers and returns false
            bool reset(){
                dem.output.length=len;
                dem.input=input;
                return false;
            }
            // resets only the output buffer and returns false
            bool resetOutput(){
                dem.output.length=len;
                return false;
            }
            char[] sliceFrom(){
                return dem.output.data[len..dem.output.length];
            }
        }
        
        BufState checkpoint(){
            return BufState(this);
        }

        static DemangleInstance opCall(Demangler prefs,char[] input,char[]output){
            input = decompressSymbol(input, &output);

            DemangleInstance res;
            res.prefs=prefs;
            res.input=input;
            res._templateDepth=0;
            res.output.data=output;
            debug(traceDemangler) res._trace=null;
            return res;
        }

        debug (traceDemangler)
        {
            private void trace (char[] where)
            {
                if (_trace.length > 500)
                    throw new Exception ("Infinite recursion");
                
                int len=_trace.length;
                char[] spaces = "            ";
                spaces=spaces[0 .. ((len<spaces.length)?len:spaces.length)];
                if (input.length < 50)
                    Stdout.formatln ("{}{} : {{{}}", spaces, where, input);
                else
                    Stdout.formatln ("{}{} : {{{}}", spaces, where, input[0..50]);
                _trace ~= where;
            }

            private void report (T...) (char[] fmt, T args)
            {
                int len=_trace.length;
                char[] spaces = "            ";
                spaces=spaces[0 .. ((len<spaces.length)?len:spaces.length)];
                Stdout (spaces);
                Stdout.formatln (fmt, args);
            }

            private void trace (bool result)
            {
                //auto tmp = _trace[$-1];
                _trace = _trace[0..$-1];
                int len=_trace.length;
                char[] spaces = "            ";
                spaces=spaces[0 .. ((len<spaces.length)?len:spaces.length)];
                Stdout(spaces);
                if (!result)
                    Stdout.formatln ("fail");
                else
                    Stdout.formatln ("success");
            }
        }

        char[] slice(){
            return output.slice;
        }

        private char[] consume (uint amt)
        {
            char[] tmp = input[0 .. amt];
            input = input[amt .. $];
            return tmp;
        }

        bool mangledName ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("mangledName");
            
            if (input.length<2)
                return false;
            if (input[0]=='D'){
                consume(1);
            } else if (input[0..2] == "_D") {
                consume(2);
            } else {
                return false;
            }

            if (! typedqualifiedName ())
                return false;

            if (input.length > 0) {
                auto pos1=checkpoint();
                output.append("<");
                if (! type ())
                    pos1.reset(); // return false??
                else if (prefs.printTypeKind){
                    output.append(">");
                } else {
                    pos1.resetOutput();
                }
            }

            //Stdout.formatln ("mangledName={}", namebuf.slice);

            return true;
        }

        bool typedqualifiedName ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("typedqualifiedName");

            auto posCar=checkpoint();
            if (! symbolName ())
                return false;
            char[] car=posCar.sliceFrom();
            
            // undocumented
            auto pos=checkpoint();
            output.append ("{");
            if (typeFunction ()){
                if (!prefs. expandFunctionTypes){
                    pos.resetOutput();
                } else {
                    output.append ("}");
                }
            } else {
                pos.reset();
            }

            pos=checkpoint();
            output.append (".");
            if (typedqualifiedName ())
            {
                if (prefs.foldDefaults && car.length<pos.sliceFrom().length &&
                    car==pos.sliceFrom()[1..car.length+1]){
                    memmove(&output.data[posCar.len],&output.data[pos.len+1],output.length-pos.len);
                    output.length+=posCar.len-pos.len-1;
                }
            } else {
                pos.reset();
            }

            return true;
        }

        bool qualifiedName (bool aliasHack = false)
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace (aliasHack ? "qualifiedNameAH" : "qualifiedName");

            auto pos=checkpoint();
            if (! symbolName (aliasHack))
                return false;
            char[] car=pos.sliceFrom();

            auto pos1=checkpoint();
            output.append (".");
            if (typedqualifiedName ())
            {
                char[] cdr=pos1.sliceFrom()[1..$];
                if (prefs.foldDefaults && cdr.length>=car.length && cdr[0..car.length]==car){
                    memmove(&output.data[pos.len],&output.data[pos1.len+1],output.length-pos1.len);
                    output.length+=pos.len-pos1.len-1;
                }
            } else {
                pos1.reset();
            }

            return true;
        }

        bool symbolName ( bool aliasHack = false)
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace (aliasHack ? "symbolNameAH" : "symbolName");

    //      if (templateInstanceName (output))
    //          return true;

            if (aliasHack){
                if (lNameAliasHack ())
                    return true;
            }
            else
            {
                if (lName ())
                    return true;
            }

            return false;
        }

        bool lName ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("lName");
            auto pos=checkpoint;
            uint chars;
            if (! number (chars))
                return false;

            char[] original = input;
            version(all){
                if (input.length < chars) {
                    // this may happen when the symbol gets hashed by MD5
                    input = null;
                    return true;        // try to continue
                }
            }
            
            input = input[0 .. chars];
            uint len = input.length;
            if (templateInstanceName())
            {
                input = original[len - input.length .. $];
                return true;
            }
            input = original;

            if(!name (chars)){
                return pos.reset();
            }
            return true;
        }

        /* this hack is ugly and guaranteed to break, but the symbols
           generated for template alias parameters are broken:
           the compiler generates a symbol of the form S(number){(number)(name)}
           with no space between the numbers; what we do is try to match
           different combinations of division between the concatenated numbers */

        bool lNameAliasHack ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("lNameAH");

    //      uint chars;
    //      if (! number (chars))
    //          return false;

            uint chars;
            auto pos=checkpoint();
            if (! numberNoParse ())
                return false;
            char[10] numberBuf;
            char[] str = pos.sliceFrom();
            if (str.length>numberBuf.length){
                return pos.reset();
            }
            numberBuf[0..str.length]=str;
            str=numberBuf[0..str.length];
            pos.resetOutput();
            
            int i = 0;

            bool done = false;

            char[] original = input;
            char[] working = input;

            while (done == false)
            {
                if (i > 0)
                {
                    input = working = original[0 .. toUint(str[0..i])];
                }
                else
                    input = working = original;

                chars = toUint(str[i..$]);

                if (chars < input.length && chars > 0)
                {
                    // cut the string from the right side to the number
                    // char[] original = input;
                    // input = input[0 .. chars];
                    // uint len = input.length;
                    debug(traceDemangler) report ("trying {}/{}", chars, input.length);
                    done = templateInstanceName ();
                    //input = original[len - input.length .. $];

                    if (!done)
                    {
                        input = working;
                        debug(traceDemangler) report ("trying {}/{}", chars, input.length);
                        done = name (chars);
                    }

                    if (done)
                    {
                        input = original[working.length - input.length .. $];
                        return true;
                    }
                    else
                        input = original;
                }

                i += 1;
                if (i == str.length)
                    return false;
            }

            return true;
        }

        bool number (ref uint value)
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("number");

            if (input.length == 0)
                return false;

            value = 0;
            if (input[0] >= '0' && input[0] <= '9')
            {
                while (input.length > 0 && input[0] >= '0' && input[0] <= '9')
                {
                    value = value * 10 + cast(uint) (input[0] - '0');
                    consume (1);
                }
                return true;
            }
            else
                return false;
        }

        bool numberNoParse ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("numberNP");

            if (input.length == 0)
                return false;

            if (input[0] >= '0' && input[0] <= '9')
            {
                while (input.length > 0 && input[0] >= '0' && input[0] <= '9')
                {
                    output.append (input[0]);
                    consume (1);
                }
                return true;
            }
            else
                return false;
        }

        bool name (uint count)
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("name");

            //if (input.length >= 3 && input[0 .. 3] == "__T")
            //  return false; // workaround

            if (count > input.length)
                return false;

            char[] name = consume (count);
            output.append (name);
            debug(traceDemangler) report (">>> name={}", name);

            return count > 0;
        }

        bool type ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("type");
            if (! input.length) return false;
            auto pos=checkpoint();
            switch (input[0])
            {
                case 'x':
                    consume (1);
                    output.append ("const ");
                    if (!type ()) return pos.reset();
                    return true;

                case 'y':
                    consume (1);
                    output.append ("invariant ");
                    if (!type ()) return pos.reset();
                    return true;

                case 'A':
                    consume (1);
                    if (type ())
                    {
                        output.append ("[]");
                        return true;
                    }
                    return pos.reset();

                case 'G':
                    consume (1);
                    uint size;
                    if (! number (size))
                        return false;
                    if (type ()) {
                        output.append ("[" ~ ctfe_i2a(size) ~ "]");
                        return true;
                    }
                    return pos.reset();

                case 'H':
                    consume (1);
                    auto pos2=checkpoint();
                    if (! type ())
                        return false;
                    char[] keytype=pos2.sliceFrom();
                    output.append ("[");
                    auto pos3=checkpoint();
                    if (type ())
                    {
                        char[]subtype=pos3.sliceFrom();
                        output.append ("]");
                        if (subtype.length<=keytype.length){
                            auto pos4=checkpoint();
                            output.append (keytype);
                            memmove(&output.data[pos2.len],&output.data[pos3.len],subtype.length);
                            output.data[pos2.len+keytype.length]='[';
                            memcpy(&output.data[pos2.len],&output.data[pos4.len],keytype.length);
                            pos4.reset();
                        }
                        return true;
                    }
                    return pos.reset();

                case 'P':
                    consume (1);
                    if (type ())
                    {
                        output.append ("*");
                        return true;
                    }
                    return false;
                case 'F': case 'U': case 'W': case 'V': case 'R': case 'D': case 'M':
                    return typeFunction ();
                case 'I': case 'C': case 'S': case 'E': case 'T':
                    return typeNamed ();
                case 'n':
                    consume (1);
                    output.append ("none");
                    return true;
                case 'v':
                    consume (1);
                    output.append ("void");
                    return true;
                case 'g':
                    consume (1);
                    output.append ("byte");
                    return true;
                case 'h':
                    consume (1);
                    output.append ("ubyte");
                    return true;
                case 's':
                    consume (1);
                    output.append ("short");
                    return true;
                case 't':
                    consume (1);
                    output.append ("ushort");
                    return true;
                case 'i':
                    consume (1);
                    output.append ("int");
                    return true;
                case 'k':
                    consume (1);
                    output.append ("uint");
                    return true;
                case 'l':
                    consume (1);
                    output.append ("long");
                    return true;
                case 'm':
                    consume (1);
                    output.append ("ulong");
                    return true;
                case 'f':
                    consume (1);
                    output.append ("float");
                    return true;
                case 'd':
                    consume (1);
                    output.append ("double");
                    return true;
                case 'e':
                    consume (1);
                    output.append ("real");
                    return true;
                case 'q':
                    consume(1);
                    output.append ("cfloat");
                    return true;
                case 'r':
                    consume(1);
                    output.append ("cdouble");
                    return true;
                case 'c':
                    consume(1);
                    output.append ("creal");
                    return true;
                case 'o':
                    consume(1);
                    output.append ("ifloat");
                    return true;
                case 'p':
                    consume(1);
                    output.append ("idouble");
                    return true;
                case 'j':
                    consume(1);
                    output.append ("ireal");
                    return true;
                case 'b':
                    consume (1);
                    output.append ("bool");
                    return true;
                case 'a':
                    consume (1);
                    output.append ("char");
                    return true;
                case 'u':
                    consume (1);
                    output.append ("wchar");
                    return true;
                case 'w':
                    consume (1);
                    output.append ("dchar");
                    return true;
                case 'B':
                    consume (1);
                    uint count;
                    if (! number (count))
                        return pos.reset();
                    output.append ('(');
                    if (! arguments ())
                        return pos.reset();
                    output.append (')');
                    return true;

                default:
                    return pos.reset();
            }

            //return true;
        }

        bool typeFunction ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("typeFunction");
            
            auto pos=checkpoint();
            bool isMethod = false;
            bool isDelegate = false;

            if (input.length == 0)
                return false;

            if (input[0] == 'M')
            {
                consume (1);
                isMethod = true;
            }
            if (input[0] == 'D')
            {
                consume (1);
                isDelegate = true;
                assert (! isMethod);
            }

            switch (input[0])
            {
                case 'F':
                    consume (1);
                    break;

                case 'U':
                    consume (1);
                    output.append ("extern(C) ");
                    break;

                case 'W':
                    consume (1);
                    output.append ("extern(Windows) ");
                    break;

                case 'V':
                    consume (1);
                    output.append ("extern(Pascal) ");
                    break;

                case 'R':
                    consume (1);
                    output.append ("extern(C++) ");
                    break;

                default:
                    return pos.reset();
            }
            
            auto pos2=checkpoint();
            if (isMethod)
                output.append (" method (");
            else if (isDelegate)
                output.append (" delegate (");
            else
                output.append (" function (");
            
            arguments ();
            version (all){
                if (0 == input.length) {
                    // probably MD5 symbol hashing. try to continue
                    return true;
                }
            }
            switch (input[0])
            {
                case 'X': case 'Y': case 'Z':
                    consume (1);
                    break;
                default:
                    return pos.reset();
            }
            output.append (")");
            
            auto pos3=checkpoint();
            if (! type ())
                return pos.reset();
            char[] retT=pos3.sliceFrom();
            auto pos4=checkpoint();
            output.append(retT);
            memmove(&output.data[pos2.len+retT.length],&output.data[pos2.len],pos3.len-pos2.len+1);
            memcpy(&output.data[pos2.len],&output.data[pos4.len],retT.length);
            pos4.reset();
            return true;
        }

        bool arguments ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("arguments");

            if (! argument ())
                return false;

            auto pos=checkpoint();
            output.append (", ");
            if (!arguments ()){
                pos.reset;
            }

            return true;
        }

        bool argument ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("argument");

            if (input.length == 0)
                return false;
            auto pos=checkpoint();
            switch (input[0])
            {
                case 'K':
                    consume (1);
                    output.append ("ref ");
                    break;

                case 'J':
                    consume (1);
                    output.append ("out ");
                    break;

                case 'L':
                    consume (1);
                    output.append ("lazy ");
                    break;

                default:
            }

            if (! type ())
                return pos.reset();

            return true;
        }

        bool typeNamed ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("typeNamed");
            auto pos=checkpoint();
            char[] kind;
            switch (input[0])
            {
                case 'I':
                    consume (1);
                    kind = "interface";
                    break;

                case 'S':
                    consume (1);
                    kind = "struct";
                    break;

                case 'C':
                    consume (1);
                    kind = "class";
                    break;

                case 'E':
                    consume (1);
                    kind = "enum";
                    break;

                case 'T':
                    consume (1);
                    kind = "typedef";
                    break;

                default:
                    return false;
            }

            //output.append (kind);
            //output.append ("=");

            if (! qualifiedName ())
                return pos.reset();

            if (prefs. printTypeKind)
            {
                output.append ("<");
                output.append (kind);
                output.append (">");
            }

            return true;
        }

        bool templateInstanceName ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("templateInstanceName");
            auto pos=checkpoint();
            if (input.length < 4 || input[0..3] != "__T")
                return false;

            consume (3);

            if (! lName ())
                return checkpoint.reset();

            output.append ("!(");

            _templateDepth++;
            if (_templateDepth <= prefs.templateExpansionDepth) {
                templateArgs ();
            } else {
                auto pos2=checkpoint();
                templateArgs ();
                pos2.resetOutput();
                output.append ("...");
            }
            _templateDepth--;

            if (input.length > 0 && input[0] != 'Z')
                return pos.reset();

            output.append (")");

            consume (1);
            return true;
        }

        bool templateArgs ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("templateArgs");

            if (! templateArg ())
                return false;
            auto pos1=checkpoint();
            output.append (", ");
            if (! templateArgs ())
            {
                pos1.reset();
            }

            return true;
        }

        bool templateArg ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("templateArg");

            if (input.length == 0)
                return false;
            auto pos=checkpoint();
            switch (input[0])
            {
                case 'T':
                    consume (1);
                    if (! type ())
                        return pos.reset();
                    return true;

                case 'V':
                    consume (1);
                    auto pos2=checkpoint();
                    if (! type ())
                        return pos.reset();
                    pos2.resetOutput();
                    if (! value ())
                        return pos.reset();
                    return true;

                case 'S':
                    consume (1);
                    if (! qualifiedName (true))
                        return pos.reset();
                    return true;

                default:
                    return pos.reset();
            }

            //return pos.reset;
        }

        bool value ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("value");

            if (input.length == 0)
                return false;

            auto pos=checkpoint();

            switch (input[0])
            {
                case 'n':
                    consume (1);
                    return true;

                case 'N':
                    consume (1);
                    output.append ('-');
                    if (! numberNoParse ())
                        return pos.reset();
                    return true;

                case 'e':
                    consume (1);
                    if (! hexFloat ())
                        return pos.reset();
                    return true;

                case 'c': //TODO

                case 'A':
                    consume (1);
                    uint count;
                    if (! number (count))
                        return pos.reset();
                    if (count>0) {
                        output.append ("[");
                        for (uint i = 0; i < count-1; i++)
                        {
                            if (! value ())
                                return pos.reset();
                            output.append (", ");
                        }
                        if (! value ())
                            return pos.reset();
                    }
                    output.append ("]");
                    return true;

                default:
                    if (! numberNoParse ())
                        return pos.reset();
                    return true;
            }

            //return pos.reset();
        }

        bool hexFloat ()
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("hexFloat");

            auto pos=checkpoint();
            if (input[0 .. 3] == "NAN")
            {
                consume (3);
                output.append ("nan");
                return true;
            }
            else if (input[0 .. 3] == "INF")
            {
                consume (3);
                output.append ("+inf");
                return true;
            }
            else if (input[0 .. 3] == "NINF")
            {
                consume (3);
                output.append ("-inf");
                return true;
            }

            bool negative = false;
            if (input[0] == 'N')
            {
                consume (1);
                negative = true;
            }

            ulong num;
            if (! hexNumber (num))
                return false;

            if (input[0] != 'P')
                return false;
            consume (1);

            bool negative_exponent = false;
            if (input[0] == 'N')
            {
                consume (1);
                negative_exponent = true;
            }

            uint exponent;
            if (! number (exponent))
                return pos.reset();

            return true;
        }

        static bool isHexDigit (char c)
        {
            return (c > '0' && c <'9') || (c > 'a' && c < 'f') || (c > 'A' && c < 'F');
        }

        bool hexNumber (ref ulong value)
        out (result)
        {
            debug(traceDemangler) trace (result);
        }
        body
        {
            debug(traceDemangler) trace ("hexFloat");

            if (isHexDigit (input[0]))
            {
                while (isHexDigit (input[0]))
                {
                    //output.append (input[0]);
                    consume (1);
                }
                return true;
            }
            else
                return false;
        }
    }
}


private struct Buffer
{
    char[] data;
    size_t     length;

    void append (char[] s)
    {
        assert(this.length+s.length<=data.length);
        size_t len=this.length+s.length;
        if (len>data.length) len=data.length;
        data[this.length .. len] = s[0..len-this.length];
        this.length = len;
    }

    void append (char c)
    {
        assert(this.length<data.length);
        data[this.length .. this.length + 1] = c;
        this.length += 1;
    }

    void append (Buffer b)
    {
        append (b.slice);
    }

    char[] slice ()
    {
        return data[0 .. this.length];
    }
}

/// the default demangler
static Demangler demangler;

static this(){
    demangler=new Demangler(1);
}