001/*
002 * BridJ - Dynamic and blazing-fast native interop for Java.
003 * http://bridj.googlecode.com/
004 *
005 * Copyright (c) 2010-2013, Olivier Chafik (http://ochafik.com/)
006 * All rights reserved.
007 *
008 * Redistribution and use in source and binary forms, with or without
009 * modification, are permitted provided that the following conditions are met:
010 * 
011 *     * Redistributions of source code must retain the above copyright
012 *       notice, this list of conditions and the following disclaimer.
013 *     * Redistributions in binary form must reproduce the above copyright
014 *       notice, this list of conditions and the following disclaimer in the
015 *       documentation and/or other materials provided with the distribution.
016 *     * Neither the name of Olivier Chafik nor the
017 *       names of its contributors may be used to endorse or promote products
018 *       derived from this software without specific prior written permission.
019 * 
020 * THIS SOFTWARE IS PROVIDED BY OLIVIER CHAFIK AND CONTRIBUTORS ``AS IS'' AND ANY
021 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
022 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
023 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
024 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
025 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
026 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
027 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
028 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
029 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
030 */
031package org.bridj.demangling;
032
033import java.util.ArrayList;
034import java.util.Arrays;
035import java.util.List;
036
037import org.bridj.CLong;
038import org.bridj.NativeLibrary;
039import org.bridj.demangling.Demangler.ClassRef;
040import org.bridj.demangling.Demangler.DemanglingException;
041import org.bridj.demangling.Demangler.Ident;
042import org.bridj.demangling.Demangler.MemberRef;
043import org.bridj.demangling.Demangler.NamespaceRef;
044import org.bridj.demangling.Demangler.TypeRef;
045import org.bridj.demangling.Demangler.SpecialName;
046import java.util.Collections;
047import java.util.HashMap;
048import java.util.HashSet;
049import java.util.Map;
050import java.util.Set;
051import org.bridj.demangling.Demangler.IdentLike;
052
053public class GCC4Demangler extends Demangler {
054
055    public GCC4Demangler(NativeLibrary library, String symbol) {
056        super(library, symbol);
057    }
058    private Map<String, List<IdentLike>> prefixShortcuts = new HashMap<String, List<IdentLike>>() {
059        {
060
061            // prefix shortcut: e.g. St is for std::
062            put("t", Arrays.asList((IdentLike) new Ident("std")));
063            put("a", Arrays.asList((IdentLike) new Ident("std"), new Ident("allocator")));
064            put("b", Arrays.asList((IdentLike) new Ident("std"), new Ident("basic_string")));
065            TypeRef chartype = classType(Byte.TYPE);
066            ClassRef charTraitsOfChar = enclosed("std", new ClassRef(new Ident("char_traits", new TemplateArg[]{chartype})));
067            ClassRef allocatorOfChar = enclosed("std", new ClassRef(new Ident("allocator", new TemplateArg[]{chartype})));
068            put("d", Arrays.asList((IdentLike) new Ident("std"), new Ident("basic_iostream", new TemplateArg[]{chartype, charTraitsOfChar})));
069            put("i", Arrays.asList((IdentLike) new Ident("std"), new Ident("basic_istream", new TemplateArg[]{chartype, charTraitsOfChar})));
070            put("o", Arrays.asList((IdentLike) new Ident("std"), new Ident("basic_ostream", new TemplateArg[]{chartype, charTraitsOfChar})));
071            // Ss == std::string == std::basic_string<char, std::char_traits<char>, std::allocator<char> >        
072            put("s", Arrays.asList((IdentLike) new Ident("std"), new Ident("basic_string", new TemplateArg[]{classType(Byte.TYPE), charTraitsOfChar, allocatorOfChar})));
073
074            // used, as an helper: for i in a b c d e f g h i j k l m o p q r s t u v w x y z; do c++filt _Z1_S$i; done
075        }
076
077        private ClassRef enclosed(String ns, ClassRef classRef) {
078            classRef.setEnclosingType(new NamespaceRef(new Ident(ns)));
079            return classRef;
080        }
081    };
082    private Set<String> shouldContinueAfterPrefix = new HashSet<String>(Arrays.asList("t"));
083    private Map<String, TypeRef> typeShortcuts = new HashMap<String, TypeRef>();
084
085    private <T> T ensureOfType(Object o, Class<T> type) throws DemanglingException {
086        if (type.isInstance(o)) {
087            return type.cast(o);
088        } else {
089            throw new DemanglingException("Internal error in demangler: trying to cast to " + type.getCanonicalName() + " the object '" + o.toString() + "'");
090        }
091    }
092    int nextShortcutId = -1;
093
094    private String nextShortcutId() {
095        int n = nextShortcutId++;
096        return n == -1 ? "_" : Integer.toString(n, 36).toUpperCase() + "_";
097    }
098
099    private TypeRef parsePointerType(boolean memorizePointed, boolean isConst, boolean isReference) throws DemanglingException {
100        String subId = memorizePointed ? nextShortcutId() : null;
101        TypeRef pointed = parseType();
102        if (memorizePointed)
103            typeShortcuts.put(subId, pointed);
104        TypeRef res = pointerType(pointed, isConst, isReference);
105        String id = nextShortcutId();
106        typeShortcuts.put(id, res);
107        return res;
108    }
109
110    public TemplateArg parseTemplateArg() throws DemanglingException {
111        if (consumeCharIf('L')) {
112            TypeRef tr = parseType();
113            StringBuffer b = new StringBuffer();
114            char c;
115            while (Character.isDigit(c = peekChar())) {
116                consumeChar();
117                b.append(c);
118            }
119            expectChars('E');
120            // TODO switch on type !
121            return new Constant(Integer.parseInt(b.toString()));
122        } else {
123            return parseType();
124        }
125    }
126
127    public TypeRef parseType() throws DemanglingException {
128        if (Character.isDigit(peekChar())) {
129            Ident name = ensureOfType(parseNonCompoundIdent(), Ident.class);
130            String id = nextShortcutId(); // we get the id before parsing the part (might be template parameters and we need to get the ids in the right order)
131            TypeRef res = simpleType(name);
132            typeShortcuts.put(id, res);
133            return res;
134        }
135
136        char c = consumeChar();
137        switch (c) {
138            case 'S': { // here we first check if we have a type shorcut saved, if not we fallback to the (compound) identifier case
139                char cc = peekChar();
140                int delta = 0;
141                if (Character.isDigit(cc) || Character.isUpperCase(cc) || cc == '_') {
142                    String id = "";
143                    while ((c = peekChar()) != '_' && c != 0) {
144                        id += consumeChar();
145                        delta++;
146                    }
147                    if (peekChar() == 0) {
148                        throw new DemanglingException("Encountered a unexpected end in gcc mangler shortcut '" + id + "' " + prefixShortcuts.keySet());
149                    }
150                    id += consumeChar(); // the '_'
151                    delta++;
152                    if (typeShortcuts.containsKey(id)) {
153                        if (peekChar() != 'I') {
154                            // just a shortcut
155                            return typeShortcuts.get(id);
156                        } else {
157                            // shortcut but templated
158                            List<IdentLike> nsPath = new ArrayList<IdentLike>(prefixShortcuts.get(id));
159                            String templatedId = parsePossibleTemplateArguments(nsPath);
160                            if (templatedId != null) {
161                                return typeShortcuts.get(templatedId);
162                            }
163                        }
164                    }
165                    position -= delta;
166                }
167            }
168            // WARNING/INFO/NB: we intentionally continue to the N case
169            case 'N':
170                position--; // I actually would peek()
171            {
172                List<IdentLike> ns = new ArrayList<IdentLike>();
173                String newShortcutId = parseSimpleOrComplexIdentInto(ns, false);
174                ClassRef res = new ClassRef(ensureOfType(ns.remove(ns.size() - 1), Ident.class));
175                if (!ns.isEmpty()) {
176                    res.setEnclosingType(new NamespaceRef(ns.toArray()));
177                }
178                if (newShortcutId != null) {
179                    typeShortcuts.put(newShortcutId, res);
180                }
181                return res;
182            }
183            case 'R': // Reference: TODO: treat const ref as a value.
184            case 'P': {
185                char nextChar = peekChar();
186                boolean isReference = c == 'R';
187                boolean isConst = nextChar == 'K';
188                return parsePointerType(isConst || nextChar == 'N', isConst, isReference);
189            }
190            case 'F': {
191                // TODO parse function type correctly !!!
192                MemberRef mr = new MemberRef();
193                mr.setValueType(parseType());
194                List<TypeRef> argTypes = new ArrayList<TypeRef>();
195                while (peekChar() != 'E') {
196                    argTypes.add(parseType());
197                }
198                mr.paramTypes = argTypes.toArray(new TypeRef[argTypes.size()]);
199                expectChars('E');
200                return new FunctionTypeRef(mr);
201            }
202            case 'K': // const?
203                return parseType();
204            case 'v': // char
205                return classType(Void.TYPE);
206            case 'c':
207            case 'a':
208            case 'h': // unsigned
209                return classType(Byte.TYPE);
210            case 'b': // bool
211                return classType(Boolean.TYPE);
212            case 'l':
213            case 'm': // unsigned
214                return classType(CLong.class);
215            //return classType(Platform.is64Bits() ? Long.TYPE : Integer.TYPE);
216            case 'x':
217            case 'y': // unsigned
218                return classType(Long.TYPE);
219            case 'i':
220            case 'j': // unsigned
221                return classType(Integer.TYPE);
222            case 's':
223            case 't': // unsigned
224                return classType(Short.TYPE);
225            case 'f':
226                return classType(Float.TYPE);
227            case 'd':
228                return classType(Double.TYPE);
229            case 'z': // varargs
230                return classType(Object[].class);
231            default:
232                throw error("Unexpected type char '" + c + "'", -1);
233        }
234    }
235
236    String parseName() throws DemanglingException { // parses a plain name, e.g. "4plop" (the 4 is the length)
237        char c;
238        StringBuilder b = new StringBuilder();
239        while (Character.isDigit(c = peekChar())) {
240            consumeChar();
241            b.append(c);
242        }
243        int len;
244        try {
245            len = Integer.parseInt(b.toString());
246        } catch (NumberFormatException ex) {
247            throw error("Expected a number", 0);
248        }
249        b.setLength(0);
250        for (int i = 0; i < len; i++) {
251            b.append(consumeChar());
252        }
253        return b.toString();
254    }
255
256    private String parseSimpleOrComplexIdentInto(List<IdentLike> res, boolean isParsingNonShortcutableElement) throws DemanglingException {
257        String newlyAddedShortcutForThisType = null;
258        boolean shouldContinue = false;
259        boolean expectEInTheEnd = false;
260        if (consumeCharIf('N')) { // complex (NB: they don't recursively nest (they actually can within a template parameter but not elsewhere))
261            if (consumeCharIf('S')) { // it uses some shortcut prefix or type
262                parseShortcutInto(res);
263            }
264            shouldContinue = true;
265            expectEInTheEnd = true;
266        } else { // simple
267            if (consumeCharIf('S')) { // it uses some shortcut prefix or type
268                shouldContinue = parseShortcutInto(res);
269            } else {
270                res.add(parseNonCompoundIdent());
271            }
272        }
273        if (shouldContinue) {
274            int initialNextShortcutId = nextShortcutId;
275            do {
276                String id = nextShortcutId(); // we get the id before parsing the part (might be template parameters and we need to get the ids in the right order)
277                newlyAddedShortcutForThisType = id;
278                IdentLike part = parseNonCompoundIdent();
279                res.add(part);
280                prefixShortcuts.put(id, new ArrayList<IdentLike>(res)); // the current compound name is saved by gcc as a shortcut (we do the same)
281                parsePossibleTemplateArguments(res);
282            } while (Character.isDigit(peekChar()) || peekChar() == 'C' || peekChar() == 'D');
283            if (isParsingNonShortcutableElement) {
284                //prefixShortcuts.remove(previousShortcutId()); // correct the fact that we parsed one too much
285                nextShortcutId = initialNextShortcutId;
286            }
287        }
288        parsePossibleTemplateArguments(res);
289        if (expectEInTheEnd) {
290            expectAnyChar('E');
291        }
292        return newlyAddedShortcutForThisType;
293    }
294
295    /**
296     *
297     * @param res a list of identlikes with the namespace elements and finished
298     * with an Ident which will be replaced by a new one enriched with template
299     * info
300     * @return null if res was untouched, or the new id created because of the
301     * presence of template arguments
302     */
303    private String parsePossibleTemplateArguments(List<IdentLike> res) throws DemanglingException {
304        if (consumeCharIf('I')) {
305            List<TemplateArg> args = new ArrayList<TemplateArg>();
306            while (!consumeCharIf('E')) {
307                args.add(parseTemplateArg());
308            }
309            String id = nextShortcutId(); // we get the id after parsing the template parameters
310            // It is very important that we create a new Ident as the other one has most probably been added as a shortcut and should be immutable from then
311            Ident templatedIdent = new Ident(ensureOfType(res.remove(res.size() - 1), Ident.class).toString(), args.toArray(new TemplateArg[args.size()]));
312            res.add(templatedIdent);
313            prefixShortcuts.put(id, new ArrayList<IdentLike>(res));
314            {
315                List<IdentLike> ns = new ArrayList<IdentLike>(res);
316                ClassRef clss = new ClassRef(ensureOfType(ns.remove(ns.size() - 1), Ident.class));
317                if (!ns.isEmpty()) {
318                    clss.setEnclosingType(new NamespaceRef(ns.toArray()));
319                }
320                typeShortcuts.put(id, clss);
321            }
322            return id;
323        }
324        return null;
325    }
326
327    /**
328     * @return whether we should expect more parsing after this shortcut (e.g.
329     * std::vector<...> is actually not NSt6vectorI...EE but St6vectorI...E
330     * (without trailing N)
331     */
332    private boolean parseShortcutInto(List<IdentLike> res) throws DemanglingException {
333        char c = peekChar();
334        // GCC builds shortcuts for each encountered type, they appear in the mangling as: S_, S0_, S1_, ..., SA_, SB_, ..., SZ_, S10_
335        if (c == '_') { // we encounter S_
336            List<IdentLike> toAdd = prefixShortcuts.get(Character.toString(consumeChar()));
337            if (toAdd == null) {
338                throw new DemanglingException("Encountered a yet undefined gcc mangler shortcut S_ (first one), i.e. '_' " + prefixShortcuts.keySet());
339            }
340            res.addAll(toAdd);
341            return false;
342        } else if (Character.isDigit(c) || Character.isUpperCase(c)) { // memory shorcut S[0-9A-Z]+_
343            String id = "";
344            while ((c = peekChar()) != '_' && c != 0) {
345                id += consumeChar();
346            }
347            if (peekChar() == 0) {
348                throw new DemanglingException("Encountered a unexpected end in gcc mangler shortcut '" + id + "' " + prefixShortcuts.keySet());
349            }
350            id += consumeChar(); // the '_'
351            List<IdentLike> toAdd = prefixShortcuts.get(id);
352            if (toAdd == null) {
353                throw new DemanglingException("Encountered a unexpected gcc mangler shortcut '" + id + "' " + prefixShortcuts.keySet());
354            }
355            res.addAll(toAdd);
356            return false;
357        } else if (Character.isLowerCase(c)) { // other, single character built-in shorcuts. We suppose for now that all shortcuts are lower case (e.g. Ss, St, ...)
358            String id = Character.toString(consumeChar());
359            List<IdentLike> toAdd = prefixShortcuts.get(id);
360            if (toAdd == null) {
361                throw new DemanglingException("Encountered a unexpected gcc mangler built-in shortcut '" + id + "' " + prefixShortcuts.keySet());
362            }
363            res.addAll(toAdd);
364            return shouldContinueAfterPrefix.contains(id);
365        } else {
366            throw new DemanglingException("Encountered a unexpected gcc unknown shortcut '" + c + "' " + prefixShortcuts.keySet());
367        }
368    }
369
370    IdentLike parseNonCompoundIdent() throws DemanglingException { // This is a plain name  with possible template parameters (or special like constructor C1, C2, ...)
371        if (consumeCharIf('C')) {
372            if (consumeCharIf('1')) {
373                return SpecialName.Constructor;
374            } else if (consumeCharIf('2')) {
375                return SpecialName.SpecialConstructor;
376            } else {
377                throw error("Unknown constructor type 'C" + peekChar() + "'");
378            }
379        } else if (consumeCharIf('D')) {
380            // see http://zedcode.blogspot.com/2007/02/gcc-c-link-problems-on-small-embedded.html
381            if (consumeCharIf('0')) {
382                return SpecialName.DeletingDestructor;
383            } else if (consumeCharIf('1')) {
384                return SpecialName.Destructor;
385            } else if (consumeCharIf('2')) {
386                return SpecialName.SelfishDestructor;
387            } else {
388                throw error("Unknown destructor type 'D" + peekChar() + "'");
389            }
390        } else {
391            String n = parseName();
392            return new Ident(n);
393        }
394    }
395
396    @Override
397    public MemberRef parseSymbol() throws DemanglingException {
398        MemberRef mr = new MemberRef();
399        if (!consumeCharIf('_')) {
400            mr.setMemberName(new Ident(str));
401            return mr;
402        }
403        consumeCharIf('_');
404        if (!consumeCharIf('Z'))
405            return null;
406
407        if (consumeCharIf('T')) {
408            if (consumeCharIf('V')) {
409                mr.setEnclosingType(ensureOfType(parseType(), ClassRef.class));
410                mr.setMemberName(SpecialName.VFTable);
411                return mr;
412            }
413            return null; // can be a type info, a virtual table or strange things like that
414        }
415        /*
416         Reverse engineering of C++ operators :
417         delete[] = __ZdaPv
418         delete  = __ZdlPv
419         new[] = __Znam
420         new = __Znwm
421         */
422        if (consumeCharsIf('d', 'l', 'P', 'v')) {
423            mr.setMemberName(SpecialName.Delete);
424            return mr;
425        }
426        if (consumeCharsIf('d', 'a', 'P', 'v')) {
427            mr.setMemberName(SpecialName.DeleteArray);
428            return mr;
429        }
430        if (consumeCharsIf('n', 'w', 'm')) {
431            mr.setMemberName(SpecialName.New);
432            return mr;
433        }
434        if (consumeCharsIf('n', 'a', 'm')) {
435            mr.setMemberName(SpecialName.NewArray);
436            return mr;
437        }
438
439        {
440            List<IdentLike> ns = new ArrayList<IdentLike>();
441            parseSimpleOrComplexIdentInto(ns, true);
442            mr.setMemberName(ns.remove(ns.size() - 1));
443            if (!ns.isEmpty()) {
444                ClassRef parent = new ClassRef(ensureOfType(ns.remove(ns.size() - 1), Ident.class));
445                if (mr.getMemberName() == SpecialName.Constructor || mr.getMemberName() == SpecialName.SpecialConstructor) {
446                    typeShortcuts.put(nextShortcutId(), parent);
447                }
448                if (!ns.isEmpty()) {
449                    parent.setEnclosingType(new NamespaceRef(ns.toArray()));
450                }
451                mr.setEnclosingType(parent);
452            }
453        }
454
455        //System.out.println("mr = " + mr + ", peekChar = " + peekChar());
456
457        //mr.isStatic =
458        //boolean isMethod = consumeCharIf('E');
459
460        if (consumeCharIf('v')) {
461            if (position < length) {
462                error("Expected end of symbol", 0);
463            }
464            mr.paramTypes = new TypeRef[0];
465        } else {
466            List<TypeRef> paramTypes = new ArrayList<TypeRef>();
467            while (position < length) {// && !consumeCharIf('E')) {
468                paramTypes.add(parseType());
469            }
470            mr.paramTypes = paramTypes.toArray(new TypeRef[paramTypes.size()]);
471        }
472        return mr;
473    }
474}