Merge tag 'linux-kselftest-kunit-5.15-rc1' of git://git.kernel.org/pub/scm/linux...
[linux-2.6-microblaze.git] / tools / perf / util / demangle-rust.c
1 // SPDX-License-Identifier: GPL-2.0
2 #include <string.h>
3 #include "debug.h"
4
5 #include "demangle-rust.h"
6
7 /*
8  * Mangled Rust symbols look like this:
9  *
10  *     _$LT$std..sys..fd..FileDesc$u20$as$u20$core..ops..Drop$GT$::drop::hc68340e1baa4987a
11  *
12  * The original symbol is:
13  *
14  *     <std::sys::fd::FileDesc as core::ops::Drop>::drop
15  *
16  * The last component of the path is a 64-bit hash in lowercase hex, prefixed
17  * with "h". Rust does not have a global namespace between crates, an illusion
18  * which Rust maintains by using the hash to distinguish things that would
19  * otherwise have the same symbol.
20  *
21  * Any path component not starting with a XID_Start character is prefixed with
22  * "_".
23  *
24  * The following escape sequences are used:
25  *
26  *     ","  =>  $C$
27  *     "@"  =>  $SP$
28  *     "*"  =>  $BP$
29  *     "&"  =>  $RF$
30  *     "<"  =>  $LT$
31  *     ">"  =>  $GT$
32  *     "("  =>  $LP$
33  *     ")"  =>  $RP$
34  *     " "  =>  $u20$
35  *     "'"  =>  $u27$
36  *     "["  =>  $u5b$
37  *     "]"  =>  $u5d$
38  *     "~"  =>  $u7e$
39  *
40  * A double ".." means "::" and a single "." means "-".
41  *
42  * The only characters allowed in the mangled symbol are a-zA-Z0-9 and _.:$
43  */
44
45 static const char *hash_prefix = "::h";
46 static const size_t hash_prefix_len = 3;
47 static const size_t hash_len = 16;
48
49 static bool is_prefixed_hash(const char *start);
50 static bool looks_like_rust(const char *sym, size_t len);
51 static bool unescape(const char **in, char **out, const char *seq, char value);
52
53 /*
54  * INPUT:
55  *     sym: symbol that has been through BFD-demangling
56  *
57  * This function looks for the following indicators:
58  *
59  *  1. The hash must consist of "h" followed by 16 lowercase hex digits.
60  *
61  *  2. As a sanity check, the hash must use between 5 and 15 of the 16 possible
62  *     hex digits. This is true of 99.9998% of hashes so once in your life you
63  *     may see a false negative. The point is to notice path components that
64  *     could be Rust hashes but are probably not, like "haaaaaaaaaaaaaaaa". In
65  *     this case a false positive (non-Rust symbol has an important path
66  *     component removed because it looks like a Rust hash) is worse than a
67  *     false negative (the rare Rust symbol is not demangled) so this sets the
68  *     balance in favor of false negatives.
69  *
70  *  3. There must be no characters other than a-zA-Z0-9 and _.:$
71  *
72  *  4. There must be no unrecognized $-sign sequences.
73  *
74  *  5. There must be no sequence of three or more dots in a row ("...").
75  */
76 bool
77 rust_is_mangled(const char *sym)
78 {
79         size_t len, len_without_hash;
80
81         if (!sym)
82                 return false;
83
84         len = strlen(sym);
85         if (len <= hash_prefix_len + hash_len)
86                 /* Not long enough to contain "::h" + hash + something else */
87                 return false;
88
89         len_without_hash = len - (hash_prefix_len + hash_len);
90         if (!is_prefixed_hash(sym + len_without_hash))
91                 return false;
92
93         return looks_like_rust(sym, len_without_hash);
94 }
95
96 /*
97  * A hash is the prefix "::h" followed by 16 lowercase hex digits. The hex
98  * digits must comprise between 5 and 15 (inclusive) distinct digits.
99  */
100 static bool is_prefixed_hash(const char *str)
101 {
102         const char *end;
103         bool seen[16];
104         size_t i;
105         int count;
106
107         if (strncmp(str, hash_prefix, hash_prefix_len))
108                 return false;
109         str += hash_prefix_len;
110
111         memset(seen, false, sizeof(seen));
112         for (end = str + hash_len; str < end; str++)
113                 if (*str >= '0' && *str <= '9')
114                         seen[*str - '0'] = true;
115                 else if (*str >= 'a' && *str <= 'f')
116                         seen[*str - 'a' + 10] = true;
117                 else
118                         return false;
119
120         /* Count how many distinct digits seen */
121         count = 0;
122         for (i = 0; i < 16; i++)
123                 if (seen[i])
124                         count++;
125
126         return count >= 5 && count <= 15;
127 }
128
129 static bool looks_like_rust(const char *str, size_t len)
130 {
131         const char *end = str + len;
132
133         while (str < end)
134                 switch (*str) {
135                 case '$':
136                         if (!strncmp(str, "$C$", 3))
137                                 str += 3;
138                         else if (!strncmp(str, "$SP$", 4)
139                                         || !strncmp(str, "$BP$", 4)
140                                         || !strncmp(str, "$RF$", 4)
141                                         || !strncmp(str, "$LT$", 4)
142                                         || !strncmp(str, "$GT$", 4)
143                                         || !strncmp(str, "$LP$", 4)
144                                         || !strncmp(str, "$RP$", 4))
145                                 str += 4;
146                         else if (!strncmp(str, "$u20$", 5)
147                                         || !strncmp(str, "$u27$", 5)
148                                         || !strncmp(str, "$u5b$", 5)
149                                         || !strncmp(str, "$u5d$", 5)
150                                         || !strncmp(str, "$u7e$", 5))
151                                 str += 5;
152                         else
153                                 return false;
154                         break;
155                 case '.':
156                         /* Do not allow three or more consecutive dots */
157                         if (!strncmp(str, "...", 3))
158                                 return false;
159                         /* Fall through */
160                 case 'a' ... 'z':
161                 case 'A' ... 'Z':
162                 case '0' ... '9':
163                 case '_':
164                 case ':':
165                         str++;
166                         break;
167                 default:
168                         return false;
169                 }
170
171         return true;
172 }
173
174 /*
175  * INPUT:
176  *     sym: symbol for which rust_is_mangled(sym) returns true
177  *
178  * The input is demangled in-place because the mangled name is always longer
179  * than the demangled one.
180  */
181 void
182 rust_demangle_sym(char *sym)
183 {
184         const char *in;
185         char *out;
186         const char *end;
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                 switch (*in) {
197                 case '$':
198                         if (!(unescape(&in, &out, "$C$", ',')
199                                         || unescape(&in, &out, "$SP$", '@')
200                                         || unescape(&in, &out, "$BP$", '*')
201                                         || unescape(&in, &out, "$RF$", '&')
202                                         || unescape(&in, &out, "$LT$", '<')
203                                         || unescape(&in, &out, "$GT$", '>')
204                                         || unescape(&in, &out, "$LP$", '(')
205                                         || unescape(&in, &out, "$RP$", ')')
206                                         || unescape(&in, &out, "$u20$", ' ')
207                                         || unescape(&in, &out, "$u27$", '\'')
208                                         || unescape(&in, &out, "$u5b$", '[')
209                                         || unescape(&in, &out, "$u5d$", ']')
210                                         || unescape(&in, &out, "$u7e$", '~'))) {
211                                 pr_err("demangle-rust: unexpected escape sequence");
212                                 goto done;
213                         }
214                         break;
215                 case '_':
216                         /*
217                          * If this is the start of a path component and the next
218                          * character is an escape sequence, ignore the
219                          * underscore. The mangler inserts an underscore to make
220                          * sure the path component begins with a XID_Start
221                          * character.
222                          */
223                         if ((in == sym || in[-1] == ':') && in[1] == '$')
224                                 in++;
225                         else
226                                 *out++ = *in++;
227                         break;
228                 case '.':
229                         if (in[1] == '.') {
230                                 /* ".." becomes "::" */
231                                 *out++ = ':';
232                                 *out++ = ':';
233                                 in += 2;
234                         } else {
235                                 /* "." becomes "-" */
236                                 *out++ = '-';
237                                 in++;
238                         }
239                         break;
240                 case 'a' ... 'z':
241                 case 'A' ... 'Z':
242                 case '0' ... '9':
243                 case ':':
244                         *out++ = *in++;
245                         break;
246                 default:
247                         pr_err("demangle-rust: unexpected character '%c' in symbol\n",
248                                 *in);
249                         goto done;
250                 }
251
252 done:
253         *out = '\0';
254 }
255
256 static bool unescape(const char **in, char **out, const char *seq, char value)
257 {
258         size_t len = strlen(seq);
259
260         if (strncmp(*in, seq, len))
261                 return false;
262
263         **out = value;
264
265         *in += len;
266         *out += 1;
267
268         return true;
269 }