/* Copyright 2007 Sun Microsystems, Inc. All Rights Reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. - Neither the name of Sun Microsystems nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** * Universal mangling rules for the JVM. * * @author John Rose * @version 1.1, 03/03/08 * @see http://blogs.sun.com/jrose/entry/symbolic_freedom_in_the_vm * *

Avoiding Dangerous Characters

* *

* The JVM defines a very small set of characters which are illegal * in name spellings. We will slightly extend and regularize this set * into a group of dangerous characters. * These characters will then be replaced, in mangled names, by escape sequences. * In addition, accidental escape sequences must be further escaped. * Finally, a special prefix will be applied if and only if * the mangling would otherwise fail to begin with the escape character. * This happens to cover the corner case of the null string, * and also clearly marks symbols which need demangling. *

*

* Dangerous characters are the union of all characters forbidden * or otherwise restricted by the JVM specification, * plus their mates, if they are brackets * ([ and ], * < and >), * plus, arbitrarily, the colon character :. * There is no distinction between type, method, and field names. * This makes it easier to convert between mangled names of different * types, since they do not need to be decoded (demangled). *

*

* The escape character is backslash \ * (also known as reverse solidus). * This character is, until now, unheard of in bytecode names, * but traditional in the proposed role. * *

*

Replacement Characters

* * *

* Every escape sequence is two characters * (in fact, two UTF8 bytes) beginning with * the escape character and followed by a * replacement character. * (Since the replacement character is never a backslash, * iterated manglings do not double in size.) *

*

* Each dangerous character has some rough visual similarity * to its corresponding replacement character. * This makes mangled symbols easier to recognize by sight. *

*

* The dangerous characters are * / (forward slash, used to delimit package components), * . (dot, also a package delimiter), * ; (semicolon, used in signatures), * $ (dollar, used in inner classes and synthetic members), * < (left angle), * > (right angle), * [ (left square bracket, used in array types), * ] (right square bracket, reserved in this scheme for language use), * and : (colon, reserved in this scheme for language use). * Their replacements are, respectively, * | (vertical bar), * , (comma), * ? (question mark), * % (percent), * ^ (caret), * _ (underscore), and * { (left curly bracket), * } (right curly bracket), * ! (exclamation mark). * In addition, the replacement character for the escape character itself is * - (hyphen), * and the replacement character for the null prefix is * = (equal sign). *

*

* An escape character \ * followed by any of these replacement characters * is an escape sequence, and there are no other escape sequences. * An equal sign is only part of an escape sequence * if it is the second character in the whole string, following a backslash. * Two consecutive backslashes do not form an escape sequence. *

*

* Each escape sequence replaces a so-called original character * which is either one of the dangerous characters or the escape character. * A null prefix replaces an initial null string, not a character. *

*

* All this implies that escape sequences cannot overlap and may be * determined all at once for a whole string. Note that a spelling * string can contain accidental escapes, apparent escape * sequences which must not be interpreted as manglings. * These are disabled by replacing their leading backslash with an * escape sequence (\-). To mangle a string, three logical steps * are required, though they may be carried out in one pass: *

*
    *
  1. In each accidental escape, replace the backslash with an escape sequence * (\-).
    2. *
  2. Replace each dangerous character with an escape sequence * (\| for /, etc.).
    3. *
  3. If the first two steps introduced any change, and * if the string does not already begin with a backslash, prepend a null prefix (\=).
    4. *
* * To demangle a mangled string that begins with an escape, * remove any null prefix, and then replace (in parallel) * each escape sequence by its original character. *

Spelling strings which contain accidental * escapes must have them replaced, even if those * strings do not contain dangerous characters. * This restriction means that mangling a string always * requires a scan of the string for escapes. * But then, a scan would be required anyway, * to check for dangerous characters. * *

*

Nice Properties

* *

* If a bytecode name does not contain any escape sequence, * demangling is a no-op: The string demangles to itself. * Such a string is called self-mangling. * Almost all strings are self-mangling. * In practice, to demangle almost any name “found in nature”, * simply verify that it does not begin with a backslash. *

*

* Mangling is a one-to-one function, while demangling * is a many-to-one function. * A mangled string is defined as validly mangled if * it is in fact the unique mangling of its spelling string. * Three examples of invalidly mangled strings are \=foo, * \-bar, and baz\!, which demangle to foo, \bar, and * baz\!, but then remangle to foo, \bar, and \=baz\-!. * If a language back-end or runtime is using mangled names, * it should never present an invalidly mangled bytecode * name to the JVM. If the runtime encounters one, * it should also report an error, since such an occurrence * probably indicates a bug in name encoding which * will lead to errors in linkage. * However, this note does not propose that the JVM verifier * detect invalidly mangled names. *

*

* As a result of these rules, it is a simple matter to * compute validly mangled substrings and concatenations * of validly mangled strings, and (with a little care) * these correspond to corresponding operations on their * spelling strings. *

* *

If languages that include non-Java symbol spellings use this * mangling convention, they will enjoy the following advantages: *

* * * *

Suggestions for Human Readable Presentations

* * *

* For human readable displays of symbols, * it will be better to present a string-like quoted * representation of the spelling, because JVM users * are generally familiar with such tokens. * We suggest using single or double quotes before and after * symbols which are not valid Java identifiers, * with quotes, backslashes, and non-printing characters * escaped as if for literals in the Java language. *

*

* For example, an HTML-like spelling * <pre> mangles to * \^pre\_ and could * display more cleanly as * '<pre>', * with the quotes included. * Such string-like conventions are not suitable * for mangled bytecode names, in part because * dangerous characters must be eliminated, rather * than just quoted. Otherwise internally structured * strings like package prefixes and method signatures * could not be reliably parsed. *

*

* In such human-readable displays, invalidly mangled * names should not be demangled and quoted, * for this would be misleading. Likewise, JVM symbols * which contain dangerous characters (like dots in field * names or brackets in method names) should not be * simply quoted. The bytecode names * \=phase\,1 and * phase.1 are distinct, * and in demangled displays they should be presented as * 'phase.1' and something like * 'phase'.1, respectively. *

*/ public class StringNames { private StringNames() { } // static only class /** Given a source name, produce the corresponding bytecode name. */ public static String toBytecodeName(String s) { String bn = mangle(s); assert(bn == s || looksMangled(bn)) : bn; assert(s.equals(toSourceName(bn))) : s; return bn; } /** Given a bytecode name, produce the corresponding source name. */ public static String toSourceName(String s) { assert(isSafeBytecodeName(s)) : s; String sn = s; if (looksMangled(s)) { sn = demangle(s); assert(s.equals(mangle(sn))) : s+" => "+sn+" => "+mangle(sn); } return sn; } /** Given a bytecode name, produce the corresponding display name. * This is the source name, plus quotes if needed. */ public static String toDisplayName(String s) { if (isSafeBytecodeName(s)) { boolean isuid = Character.isUnicodeIdentifierStart(s.charAt(0)); for (int i = 1, slen = s.length(); i < slen; i++) { if (!Character.isUnicodeIdentifierPart(s.charAt(0))) { isuid = false; break; } } if (isuid) return s; String ss = toSourceName(s); if (s.equals(toBytecodeName(ss))) return quoteDisplay(ss); } // Try to demangle a prefix, up to the first dangerous char. int dci = indexOfDangerousChar(s, 0); if (dci > 0) { // At least try to demangle a prefix. String p = s.substring(0, dci); String ps = toSourceName(p); if (p.equals(toBytecodeName(ps))) { String t = s.substring(dci+1); return quoteDisplay(toSourceName(p)) + s.charAt(dci) + (t.equals("") ? "" : toDisplayName(t)); } } return "?"+quoteDisplay(s); } private static String quoteDisplay(String s) { // TO DO: Replace wierd characters in s by C-style escapes. return "'"+s.replaceAll("['\\\\]", "\\\\$0")+"'"; } private static boolean isSafeBytecodeName(String s) { if (s.length() == 0) return false; // check occurrences of each DANGEROUS char for (char xc : DANGEROUS_CHARS_A) { if (xc == ESCAPE_C) continue; // not really that dangerous if (s.indexOf(xc) >= 0) return false; } return true; } private static boolean looksMangled(String s) { return s.charAt(0) == ESCAPE_C; } private static String mangle(String s) { if (s.length() == 0) return NULL_ESCAPE; // build this lazily, when we first need an escape: StringBuilder sb = null; for (int i = 0, slen = s.length(); i < slen; i++) { char c = s.charAt(i); boolean needEscape = false; if (c == ESCAPE_C) { if (i+1 < slen) { char c1 = s.charAt(i+1); if ((i == 0 && c1 == NULL_ESCAPE_C) || c1 != originalOfReplacement(c1)) { // an accidental escape needEscape = true; } } } else { needEscape = isDangerous(c); } if (!needEscape) { if (sb != null) sb.append(c); continue; } // build sb if this is the first escape if (sb == null) { sb = new StringBuilder(s.length()+10); // mangled names must begin with a backslash: if (s.charAt(0) != ESCAPE_C && i > 0) sb.append(NULL_ESCAPE); // append the string so far, which is unremarkable: sb.append(s.substring(0, i)); } // rewrite \ to \-, / to \|, etc. sb.append(ESCAPE_C); sb.append(replacementOf(c)); } if (sb != null) return sb.toString(); return s; } private static String demangle(String s) { // build this lazily, when we first meet an escape: StringBuilder sb = null; int stringStart = 0; if (s.startsWith(NULL_ESCAPE)) stringStart = 2; for (int i = stringStart, slen = s.length(); i < slen; i++) { char c = s.charAt(i); if (c == ESCAPE_C && i+1 < slen) { // might be an escape sequence char rc = s.charAt(i+1); char oc = originalOfReplacement(rc); if (oc != rc) { // build sb if this is the first escape if (sb == null) { sb = new StringBuilder(s.length()); // append the string so far, which is unremarkable: sb.append(s.substring(stringStart, i)); } ++i; // skip both characters c = oc; } } if (sb != null) sb.append(c); } if (sb != null) return sb.toString(); return s.substring(stringStart); } static char ESCAPE_C = '\\'; // empty escape sequence to avoid a null name or illegal prefix static char NULL_ESCAPE_C = '='; static String NULL_ESCAPE = ESCAPE_C+""+NULL_ESCAPE_C; static String DANGEROUS_CHARS = ".;:$[]<>/\\"; static String REPLACEMENT_CHARS = ",?!%{}^_|-"; static char[] DANGEROUS_CHARS_A = DANGEROUS_CHARS.toCharArray(); static char[] REPLACEMENT_CHARS_A = REPLACEMENT_CHARS.toCharArray(); static final long[] SPECIAL_BITMAP = new long[2]; // 128 bits static { String SPECIAL = DANGEROUS_CHARS + REPLACEMENT_CHARS + ESCAPE_C; //System.out.println("SPECIAL = "+SPECIAL); for (char c : SPECIAL.toCharArray()) { SPECIAL_BITMAP[c >>> 6] |= 1L << c; } } static boolean isSpecial(char c) { if ((c >>> 6) < SPECIAL_BITMAP.length) return ((SPECIAL_BITMAP[c >>> 6] >> c) & 1) != 0; else return false; } static char replacementOf(char c) { if (!isSpecial(c)) return c; int i = DANGEROUS_CHARS.indexOf(c); if (i < 0) return c; return REPLACEMENT_CHARS.charAt(i); } static char originalOfReplacement(char c) { if (!isSpecial(c)) return c; int i = REPLACEMENT_CHARS.indexOf(c); if (i < 0) return c; return DANGEROUS_CHARS.charAt(i); } static boolean isDangerous(char c) { if (!isSpecial(c)) return false; if (c == ESCAPE_C) return false; // not really dangerous return (DANGEROUS_CHARS.indexOf(c) >= 0); } static int indexOfDangerousChar(String s, int from) { for (int i = from, slen = s.length(); i < slen; i++) { if (isDangerous(s.charAt(i))) return i; } return -1; } // test driver public static void main(String[] av) { // If verbose is enabled, quietly check everything. // Otherwise, print the output for the user to check. boolean verbose = false; int maxlen = 0; while (av.length > 0 && av[0].startsWith("-")) { String flag = av[0].intern(); av = java.util.Arrays.copyOfRange(av, 1, av.length); // Java 1.6 or later if (flag == "-" || flag == "--") break; else if (flag == "-q") verbose = false; else if (flag == "-v") verbose = true; else if (flag.startsWith("-l")) maxlen = Integer.valueOf(flag.substring(2)); else throw new Error("Illegal flag argument: "+flag); } if (maxlen == 0) maxlen = (verbose ? 2 : 4); if (verbose) System.out.println("Note: maxlen = "+maxlen); switch (av.length) { case 0: av = new String[] { DANGEROUS_CHARS.substring(0) + REPLACEMENT_CHARS.substring(0, 1) + NULL_ESCAPE + "x" }; // and fall through: case 1: char[] cv = av[0].toCharArray(); av = new String[cv.length]; int avp = 0; for (char c : cv) { String s = String.valueOf(c); if (c == 'x') s = "foo"; // tradition... av[avp++] = s; } } if (verbose) System.out.println("Note: Verbose output mode enabled. Use '-q' to suppress."); Tester t = new Tester(); t.maxlen = maxlen; t.verbose = verbose; t.tokens = av; t.test("", 0); } static class Tester { boolean verbose; int maxlen; java.util.Map map = new java.util.HashMap(); String[] tokens; void test(String stringSoFar, int tokensSoFar) { test(stringSoFar); if (tokensSoFar <= maxlen) { for (String token : tokens) { if (token.length() == 0) continue; // skip empty tokens if (stringSoFar.indexOf(token) != stringSoFar.lastIndexOf(token)) continue; // there are already two occs. of this token if (token.charAt(0) == ESCAPE_C && token.length() == 1 && maxlen < 4) test(stringSoFar+token, tokensSoFar); // want lots of \'s else if (tokensSoFar < maxlen) test(stringSoFar+token, tokensSoFar+1); } } } void test(String s) { // for small batches, do not test the null string if (s.length() == 0 && maxlen >=1 && maxlen <= 2) return; String bn = testSourceName(s); if (bn == null) return; if (bn == s) { //if (verbose) System.out.println(s+" == id"); } else { if (verbose) System.out.println(s+" => "+bn+" "+toDisplayName(bn)); String bnbn = testSourceName(bn); if (bnbn == null) return; if (verbose) System.out.println(bn+" => "+bnbn+" "+toDisplayName(bnbn)); /* String bn3 = testSourceName(bnbn); if (bn3 == null) return; if (verbose) System.out.println(bnbn+" => "+bn3); */ } } String testSourceName(String s) { if (map.containsKey(s)) return null; String bn = toBytecodeName(s); map.put(s, bn); String sn = toSourceName(bn); if (!sn.equals(s)) { String bad = (s+" => "+bn+" != "+sn); if (!verbose) throw new Error("Bad mangling: "+bad); System.out.println("*** "+bad); return null; } return bn; } } }