libiberty/rust-demangle.c

   1 /* Demangler for the Rust programming language
   2    Copyright (C) 2016-2019 Free Software Foundation, Inc.
   3    Written by David Tolnay (dtolnay@gmail.com).
   4
   5 This file is part of the libiberty library.
   6 Libiberty is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Library General Public
   8 License as published by the Free Software Foundation; either
   9 version 2 of the License, or (at your option) any later version.
  10
  11 In addition to the permissions in the GNU Library General Public
  12 License, the Free Software Foundation gives you unlimited permission
  13 to link the compiled version of this file into combinations with other
  14 programs, and to distribute those combinations without any restriction
  15 coming from the use of this file.  (The Library Public License
  16 restrictions do apply in other respects; for example, they cover
  17 modification of the file, and distribution when not linked into a
  18 combined executable.)
  19
  20 Libiberty is distributed in the hope that it will be useful,
  21 but WITHOUT ANY WARRANTY; without even the implied warranty of
  22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23 Library General Public License for more details.
  24
  25 You should have received a copy of the GNU Library General Public
  26 License along with libiberty; see the file COPYING.LIB.
  27 If not, see <http://www.gnu.org/licenses/>.  */
  28
  29
  30 #ifdef HAVE_CONFIG_H
  31 #include "config.h"
  32 #endif
  33
  34 #include "safe-ctype.h"
  35
  36 #include <sys/types.h>
  37 #include <string.h>
  38 #include <stdio.h>
  39
  40 #ifdef HAVE_STRING_H
  41 #include <string.h>
  42 #else
  43 extern size_t strlen(const char *s);
  44 extern int strncmp(const char *s1, const char *s2, size_t n);
  45 extern void *memset(void *s, int c, size_t n);
  46 #endif
  47
  48 #include <demangle.h>
  49 #include "libiberty.h"
  50 #include "rust-demangle.h"
  51
  52
  53 /* Mangled (legacy) Rust symbols look like this:
  54      _$LT$std..sys..fd..FileDesc$u20$as$u20$core..ops..Drop$GT$::drop::hc68340e1baa4987a
  55
  56    The original symbol is:
  57      <std::sys::fd::FileDesc as core::ops::Drop>::drop
  58
  59    The last component of the path is a 64-bit hash in lowercase hex,
  60    prefixed with "h". Rust does not have a global namespace between
  61    crates, an illusion which Rust maintains by using the hash to
  62    distinguish things that would otherwise have the same symbol.
  63
  64    Any path component not starting with a XID_Start character is
  65    prefixed with "_".
  66
  67    The following escape sequences are used:
  68
  69    ","  =>  $C$
  70    "@"  =>  $SP$
  71    "*"  =>  $BP$
  72    "&"  =>  $RF$
  73    "<"  =>  $LT$
  74    ">"  =>  $GT$
  75    "("  =>  $LP$
  76    ")"  =>  $RP$
  77    "\u{XY}"  =>  $uXY$
  78
  79    A double ".." means "::" and a single "." means "-".
  80
  81    The only characters allowed in the mangled symbol are a-zA-Z0-9 and _.:$  */
  82
  83 static const char *hash_prefix = "::h";
  84 static const size_t hash_prefix_len = 3;
  85 static const size_t hash_len = 16;
  86
  87 static int is_prefixed_hash (const char *start);
  88 static int parse_lower_hex_nibble (char nibble);
  89 static char parse_legacy_escape (const char **in);
  90
  91 /* INPUT: sym: symbol that has been through C++ (gnu v3) demangling
  92
  93    This function looks for the following indicators:
  94
  95    1. The hash must consist of "h" followed by 16 lowercase hex digits.
  96
  97    2. As a sanity check, the hash must use between 5 and 15 of the 16
  98       possible hex digits. This is true of 99.9998% of hashes so once
  99       in your life you may see a false negative. The point is to
 100       notice path components that could be Rust hashes but are
 101       probably not, like "haaaaaaaaaaaaaaaa". In this case a false
 102       positive (non-Rust symbol has an important path component
 103       removed because it looks like a Rust hash) is worse than a false
 104       negative (the rare Rust symbol is not demangled) so this sets
 105       the balance in favor of false negatives.
 106
 107    3. There must be no characters other than a-zA-Z0-9 and _.:$  */
 108
 109 int
 110 rust_is_mangled (const char *sym)
 111 {
 112   size_t len, len_without_hash;
 113   const char *end;
 114
 115   if (!sym)
 116     return 0;
 117
 118   len = strlen (sym);
 119   if (len <= hash_prefix_len + hash_len)
 120     /* Not long enough to contain "::h" + hash + something else */
 121     return 0;
 122
 123   len_without_hash = len - (hash_prefix_len + hash_len);
 124   if (!is_prefixed_hash (sym + len_without_hash))
 125     return 0;
 126
 127   end = sym + len_without_hash;
 128
 129   while (sym < end)
 130     {
 131       if (*sym == '$' || *sym == '.' || *sym == '_' || *sym == ':'
 132           || ISALNUM (*sym))
 133         sym++;
 134       else
 135         return 0;
 136     }
 137
 138   return 1;
 139 }
 140
 141 /* A hash is the prefix "::h" followed by 16 lowercase hex digits. The
 142    hex digits must contain at least 5 distinct digits.  */
 143
 144 static int
 145 is_prefixed_hash (const char *str)
 146 {
 147   const char *end;
 148   char seen[16];
 149   size_t i;
 150   int count, nibble;
 151
 152   if (strncmp (str, hash_prefix, hash_prefix_len))
 153     return 0;
 154   str += hash_prefix_len;
 155
 156   memset (seen, 0, sizeof(seen));
 157   for (end = str + hash_len; str < end; str++)
 158     {
 159       nibble = parse_lower_hex_nibble (*str);
 160       if (nibble < 0)
 161         return 0;
 162       seen[nibble] = 1;
 163     }
 164
 165   /* Count how many distinct digits seen */
 166   count = 0;
 167   for (i = 0; i < 16; i++)
 168     if (seen[i])
 169       count++;
 170
 171   return count >= 5;
 172 }
 173
 174 /*
 175   INPUT: sym: symbol for which rust_is_mangled(sym) returned 1.
 176
 177   The input is demangled in-place because the mangled name is always
 178   longer than the demangled one.  */
 179
 180 void
 181 rust_demangle_sym (char *sym)
 182 {
 183   const char *in;
 184   char *out;
 185   const char *end;
 186   char unescaped;
 187
 188   if (!sym)
 189     return;
 190
 191   in = sym;
 192   out = sym;
 193   end = sym + strlen (sym) - (hash_prefix_len + hash_len);
 194
 195   while (in < end)
 196     {
 197       if (*in == '$')
 198         {
 199           unescaped = parse_legacy_escape (&in);
 200           if (unescaped)
 201             *out++ = unescaped;
 202           else
 203             /* unexpected escape sequence, skip the rest of this segment. */
 204             while (in < end && *in != ':')
 205               *out++ = *in++;
 206         }
 207       else if (*in == '_')
 208         {
 209           /* If this is the start of a path component and the next
 210              character is an escape sequence, ignore the underscore. The
 211              mangler inserts an underscore to make sure the path
 212              component begins with a XID_Start character. */
 213           if ((in == sym || in[-1] == ':') && in[1] == '$')
 214             in++;
 215           else
 216             *out++ = *in++;
 217         }
 218       else if (*in == '.')
 219         {
 220           if (in[1] == '.')
 221             {
 222               /* ".." becomes "::" */
 223               *out++ = ':';
 224               *out++ = ':';
 225               in += 2;
 226             }
 227           else
 228             {
 229               /* "." becomes "-" */
 230               *out++ = '-';
 231               in++;
 232             }
 233         }
 234       else if (*in == ':' || ISALNUM (*in))
 235         *out++ = *in++;
 236       else
 237         {
 238           /* unexpected character in symbol, not rust_is_mangled.  */
 239           *out++ = '?'; /* This is pretty lame, but it's hard to do better. */
 240           *out = '\0';
 241           return;
 242         }
 243     }
 244
 245   *out = '\0';
 246 }
 247
 248 /* Return a 0x0-0xf value if the char is 0-9a-f, and -1 otherwise. */
 249 static int
 250 parse_lower_hex_nibble (char nibble)
 251 {
 252   if ('0' <= nibble && nibble <= '9')
 253     return nibble - '0';
 254   if ('a' <= nibble && nibble <= 'f')
 255     return 0xa + (nibble - 'a');
 256   return -1;
 257 }
 258
 259 /* Return the unescaped character for a "$...$" escape, or 0 if invalid. */
 260 static char
 261 parse_legacy_escape (const char **in)
 262 {
 263   char c = 0;
 264   const char *e;
 265   size_t escape_len = 0;
 266   int lo_nibble = -1, hi_nibble = -1;
 267
 268   if ((*in)[0] != '$')
 269     return 0;
 270
 271   e = *in + 1;
 272
 273   if (e[0] == 'C')
 274     {
 275       escape_len = 1;
 276
 277       c = ',';
 278     }
 279   else
 280     {
 281       escape_len = 2;
 282
 283       if (e[0] == 'S' && e[1] == 'P')
 284         c = '@';
 285       else if (e[0] == 'B' && e[1] == 'P')
 286         c = '*';
 287       else if (e[0] == 'R' && e[1] == 'F')
 288         c = '&';
 289       else if (e[0] == 'L' && e[1] == 'T')
 290         c = '<';
 291       else if (e[0] == 'G' && e[1] == 'T')
 292         c = '>';
 293       else if (e[0] == 'L' && e[1] == 'P')
 294         c = '(';
 295       else if (e[0] == 'R' && e[1] == 'P')
 296         c = ')';
 297       else if (e[0] == 'u')
 298         {
 299           escape_len = 3;
 300
 301           hi_nibble = parse_lower_hex_nibble (e[1]);
 302           if (hi_nibble < 0)
 303             return 0;
 304           lo_nibble = parse_lower_hex_nibble (e[2]);
 305           if (lo_nibble < 0)
 306             return 0;
 307
 308           /* Only allow non-control ASCII characters. */
 309           if (hi_nibble > 7)
 310             return 0;
 311           c = (hi_nibble << 4) | lo_nibble;
 312           if (c < 0x20)
 313             return 0;
 314         }
 315     }
 316
 317   if (!c || e[escape_len] != '$')
 318     return 0;
 319
 320   *in += 2 + escape_len;
 321   return c;
 322 }