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) 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);
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 'P': {
184                char nextChar = peekChar();
185                return parsePointerType(nextChar == 'K' || nextChar == 'N');
186            }
187            case 'F': {
188                // TODO parse function type correctly !!!
189                MemberRef mr = new MemberRef();
190                mr.setValueType(parseType());
191                List<TypeRef> argTypes = new ArrayList<TypeRef>();
192                while (peekChar() != 'E') {
193                    argTypes.add(parseType());
194                }
195                mr.paramTypes = argTypes.toArray(new TypeRef[argTypes.size()]);
196                expectChars('E');
197                return new FunctionTypeRef(mr);
198            }
199            case 'K': 
200                return parseType();
201            case 'v': // char
202                return classType(Void.TYPE);
203            case 'c':
204            case 'a':
205            case 'h': // unsigned
206                return classType(Byte.TYPE);
207            case 'b': // bool
208                return classType(Boolean.TYPE);
209            case 'l':
210            case 'm': // unsigned
211                return classType(CLong.class);
212            //return classType(Platform.is64Bits() ? Long.TYPE : Integer.TYPE);
213            case 'x':
214            case 'y': // unsigned
215                return classType(Long.TYPE);
216            case 'i':
217            case 'j': // unsigned
218                return classType(Integer.TYPE);
219            case 's':
220            case 't': // unsigned
221                return classType(Short.TYPE);
222            case 'f':
223                return classType(Float.TYPE);
224            case 'd':
225                return classType(Double.TYPE);
226            case 'z': // varargs
227                return classType(Object[].class);
228            default:
229                throw error("Unexpected type char '" + c + "'", -1);
230        }
231    }
232
233    String parseName() throws DemanglingException { // parses a plain name, e.g. "4plop" (the 4 is the length)
234        char c;
235        StringBuilder b = new StringBuilder();
236        while (Character.isDigit(c = peekChar())) {
237            consumeChar();
238            b.append(c);
239        }
240        int len;
241        try {
242            len = Integer.parseInt(b.toString());
243        } catch (NumberFormatException ex) {
244            throw error("Expected a number", 0);
245        }
246        b.setLength(0);
247        for (int i = 0; i < len; i++) {
248            b.append(consumeChar());
249        }
250        return b.toString();
251    }
252
253    private String parseSimpleOrComplexIdentInto(List<IdentLike> res, boolean isParsingNonShortcutableElement) throws DemanglingException {
254        String newlyAddedShortcutForThisType = null;
255        boolean shouldContinue = false;
256        boolean expectEInTheEnd = false;
257        if (consumeCharIf('N')) { // complex (NB: they don't recursively nest (they actually can within a template parameter but not elsewhere))
258            if (consumeCharIf('S')) { // it uses some shortcut prefix or type
259                parseShortcutInto(res);
260            }
261            shouldContinue = true;
262            expectEInTheEnd = true;
263        } else { // simple
264            if (consumeCharIf('S')) { // it uses some shortcut prefix or type
265                shouldContinue = parseShortcutInto(res);
266            } else {
267                res.add(parseNonCompoundIdent());
268            }
269        }
270        if (shouldContinue) {
271            int initialNextShortcutId = nextShortcutId;
272            do {
273                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)
274                newlyAddedShortcutForThisType = id;
275                IdentLike part = parseNonCompoundIdent();
276                res.add(part);
277                prefixShortcuts.put(id, new ArrayList<IdentLike>(res)); // the current compound name is saved by gcc as a shortcut (we do the same)
278                parsePossibleTemplateArguments(res);
279            } while (Character.isDigit(peekChar()) || peekChar() == 'C' || peekChar() == 'D');
280            if (isParsingNonShortcutableElement) {
281                //prefixShortcuts.remove(previousShortcutId()); // correct the fact that we parsed one too much
282                nextShortcutId = initialNextShortcutId;
283            }
284        }
285        parsePossibleTemplateArguments(res);
286        if (expectEInTheEnd) {
287            expectAnyChar('E');
288        }
289        return newlyAddedShortcutForThisType;
290    }
291
292    /**
293     *
294     * @param res a list of identlikes with the namespace elements and finished
295     * with an Ident which will be replaced by a new one enriched with template
296     * info
297     * @return null if res was untouched, or the new id created because of the
298     * presence of template arguments
299     */
300    private String parsePossibleTemplateArguments(List<IdentLike> res) throws DemanglingException {
301        if (consumeCharIf('I')) {
302            List<TemplateArg> args = new ArrayList<TemplateArg>();
303            while (!consumeCharIf('E')) {
304                args.add(parseTemplateArg());
305            }
306            String id = nextShortcutId(); // we get the id after parsing the template parameters
307            // 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
308            Ident templatedIdent = new Ident(ensureOfType(res.remove(res.size() - 1), Ident.class).toString(), args.toArray(new TemplateArg[args.size()]));
309            res.add(templatedIdent);
310            prefixShortcuts.put(id, new ArrayList<IdentLike>(res));
311            {
312                List<IdentLike> ns = new ArrayList<IdentLike>(res);
313                ClassRef clss = new ClassRef(ensureOfType(ns.remove(ns.size() - 1), Ident.class));
314                if (!ns.isEmpty()) {
315                    clss.setEnclosingType(new NamespaceRef(ns.toArray()));
316                }
317                typeShortcuts.put(id, clss);
318            }
319            return id;
320        }
321        return null;
322    }
323
324    /**
325     * @return whether we should expect more parsing after this shortcut (e.g.
326     * std::vector<...> is actually not NSt6vectorI...EE but St6vectorI...E
327     * (without trailing N)
328     */
329    private boolean parseShortcutInto(List<IdentLike> res) throws DemanglingException {
330        char c = peekChar();
331        // GCC builds shortcuts for each encountered type, they appear in the mangling as: S_, S0_, S1_, ..., SA_, SB_, ..., SZ_, S10_
332        if (c == '_') { // we encounter S_
333            List<IdentLike> toAdd = prefixShortcuts.get(Character.toString(consumeChar()));
334            if (toAdd == null) {
335                throw new DemanglingException("Encountered a yet undefined gcc mangler shortcut S_ (first one), i.e. '_' " + prefixShortcuts.keySet());
336            }
337            res.addAll(toAdd);
338            return false;
339        } else if (Character.isDigit(c) || Character.isUpperCase(c)) { // memory shorcut S[0-9A-Z]+_
340            String id = "";
341            while ((c = peekChar()) != '_' && c != 0) {
342                id += consumeChar();
343            }
344            if (peekChar() == 0) {
345                throw new DemanglingException("Encountered a unexpected end in gcc mangler shortcut '" + id + "' " + prefixShortcuts.keySet());
346            }
347            id += consumeChar(); // the '_'
348            List<IdentLike> toAdd = prefixShortcuts.get(id);
349            if (toAdd == null) {
350                throw new DemanglingException("Encountered a unexpected gcc mangler shortcut '" + id + "' " + prefixShortcuts.keySet());
351            }
352            res.addAll(toAdd);
353            return false;
354        } 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, ...)
355            String id = Character.toString(consumeChar());
356            List<IdentLike> toAdd = prefixShortcuts.get(id);
357            if (toAdd == null) {
358                throw new DemanglingException("Encountered a unexpected gcc mangler built-in shortcut '" + id + "' " + prefixShortcuts.keySet());
359            }
360            res.addAll(toAdd);
361            return shouldContinueAfterPrefix.contains(id);
362        } else {
363            throw new DemanglingException("Encountered a unexpected gcc unknown shortcut '" + c + "' " + prefixShortcuts.keySet());
364        }
365    }
366
367    IdentLike parseNonCompoundIdent() throws DemanglingException { // This is a plain name  with possible template parameters (or special like constructor C1, C2, ...)
368        if (consumeCharIf('C')) {
369            if (consumeCharIf('1')) {
370                return SpecialName.Constructor;
371            } else if (consumeCharIf('2')) {
372                return SpecialName.SpecialConstructor;
373            } else {
374                throw error("Unknown constructor type 'C" + peekChar() + "'");
375            }
376        } else if (consumeCharIf('D')) {
377            // see http://zedcode.blogspot.com/2007/02/gcc-c-link-problems-on-small-embedded.html
378            if (consumeCharIf('0')) {
379                return SpecialName.DeletingDestructor;
380            } else if (consumeCharIf('1')) {
381                return SpecialName.Destructor;
382            } else if (consumeCharIf('2')) {
383                return SpecialName.SelfishDestructor;
384            } else {
385                throw error("Unknown destructor type 'D" + peekChar() + "'");
386            }
387        } else {
388            String n = parseName();
389            return new Ident(n);
390        }
391    }
392
393    @Override
394    public MemberRef parseSymbol() throws DemanglingException {
395        MemberRef mr = new MemberRef();
396        if (!consumeCharIf('_')) {
397            mr.setMemberName(new Ident(str));
398            return mr;
399        }
400        consumeCharIf('_');
401        if (!consumeCharIf('Z'))
402            return null;
403
404        if (consumeCharIf('T')) {
405            if (consumeCharIf('V')) {
406                mr.setEnclosingType(ensureOfType(parseType(), ClassRef.class));
407                mr.setMemberName(SpecialName.VFTable);
408                return mr;
409            }
410            return null; // can be a type info, a virtual table or strange things like that
411        }
412        /*
413         Reverse engineering of C++ operators :
414         delete[] = __ZdaPv
415         delete  = __ZdlPv
416         new[] = __Znam
417         new = __Znwm
418         */
419        if (consumeCharsIf('d', 'l', 'P', 'v')) {
420            mr.setMemberName(SpecialName.Delete);
421            return mr;
422        }
423        if (consumeCharsIf('d', 'a', 'P', 'v')) {
424            mr.setMemberName(SpecialName.DeleteArray);
425            return mr;
426        }
427        if (consumeCharsIf('n', 'w', 'm')) {
428            mr.setMemberName(SpecialName.New);
429            return mr;
430        }
431        if (consumeCharsIf('n', 'a', 'm')) {
432            mr.setMemberName(SpecialName.NewArray);
433            return mr;
434        }
435
436        {
437            List<IdentLike> ns = new ArrayList<IdentLike>();
438            parseSimpleOrComplexIdentInto(ns, true);
439            mr.setMemberName(ns.remove(ns.size() - 1));
440            if (!ns.isEmpty()) {
441                ClassRef parent = new ClassRef(ensureOfType(ns.remove(ns.size() - 1), Ident.class));
442                if (mr.getMemberName() == SpecialName.Constructor || mr.getMemberName() == SpecialName.SpecialConstructor) {
443                    typeShortcuts.put(nextShortcutId(), parent);
444                }
445                if (!ns.isEmpty()) {
446                    parent.setEnclosingType(new NamespaceRef(ns.toArray()));
447                }
448                mr.setEnclosingType(parent);
449            }
450        }
451
452        //System.out.println("mr = " + mr + ", peekChar = " + peekChar());
453
454        //mr.isStatic =
455        //boolean isMethod = consumeCharIf('E');
456
457        if (consumeCharIf('v')) {
458            if (position < length) {
459                error("Expected end of symbol", 0);
460            }
461            mr.paramTypes = new TypeRef[0];
462        } else {
463            List<TypeRef> paramTypes = new ArrayList<TypeRef>();
464            while (position < length) {// && !consumeCharIf('E')) {
465                paramTypes.add(parseType());
466            }
467            mr.paramTypes = paramTypes.toArray(new TypeRef[paramTypes.size()]);
468        }
469        return mr;
470    }
471}