1 /*
2  * This file and its contents are supplied under the terms of the
3  * Common Development and Distribution License ("CDDL"), version 1.0.
4  * You may only use this file in accordance with the terms of version
5  * 1.0 of the CDDL.
6  *
7  * A full copy of the text of the CDDL should have accompanied this
8  * source.  A copy of the CDDL is also available via the Internet at
9  * http://www.illumos.org/license/CDDL.
10  */
11 
12 /*
13  * Copyright 2019, Joyent, Inc.
14  */
15 
16 #include <errno.h>
17 #include <libcustr.h>
18 #include <limits.h>
19 #include <string.h>
20 #include <sys/ctype.h>	/* We want the C locale ISXXX() versions */
21 #include <sys/debug.h>
22 #include <stdio.h>
23 #include <sys/sysmacros.h>
24 
25 #include "strview.h"
26 #include "demangle_int.h"
27 
28 /*
29  * Unfortunately, there is currently no official specification for the rust
30  * name mangling.  This is an attempt to document the understanding of the
31  * mangling used here.  It is based off examination of
32  *     https://docs.rs/rustc-demangle/0.1.13/rustc_demangle/
33  *
34  * A mangled rust name is:
35  *     <prefix> <name> <hash> E
36  *
37  * <prefix>	::=	_Z
38  *			__Z
39  *
40  * <name>	::= <name-segment>+
41  *
42  * <name-segment> ::= <len> <name-chars>{len}
43  *
44  * <len>	::= [1-9][0-9]+
45  *
46  * <name-chars>	::=	<[A-Za-z]> <[A-Za-z0-9]>*
47  *			<separator>
48  *			<special>
49  *
50  * <separator>	::=	'..'	# '::'
51  *
52  * <special>	::=	$SP$	# ' '
53  *			$BP$	# '*'
54  *			$RF$	# '&'
55  *			$LT$	# '<'
56  *			$GT$	# '>'
57  *			$LP$	# '('
58  *			$RP$	# ')'
59  *			$C$	# ','
60  *			$u7e$	# '~'
61  *			$u20$	# ' '
62  *			$u27$	# '\''
63  *			$u3d$	# '='
64  *			$u5b$	# '['
65  *			$u5d$	# ']'
66  *			$u7b$	# '{'
67  *			$u7d$	# '}'
68  *			$u3b$	# ';'
69  *			$u2b$	# '+'
70  *			$u22$	# '"'
71  *
72  * <hash>	:= <len> h <hex-digits>+
73  *
74  * <hex-digits>	:= <[0-9a-f]>
75  */
76 
77 typedef struct rustdem_state {
78 	const char	*rds_str;
79 	custr_t		*rds_demangled;
80 	sysdem_ops_t	*rds_ops;
81 	int		rds_error;
82 } rustdem_state_t;
83 
84 static const struct rust_charmap {
85 	const char	*ruc_seq;
86 	char		ruc_ch;
87 } rust_charmap[] = {
88 	{ "$SP$", '@' },
89 	{ "$BP$", '*' },
90 	{ "$RF$", '&' },
91 	{ "$LT$", '<' },
92 	{ "$GT$", '>' },
93 	{ "$LP$", '(' },
94 	{ "$RP$", ')' },
95 	{ "$C$", ',' },
96 	{ "$u7e$", '~' },
97 	{ "$u20$", ' ' },
98 	{ "$u27$", '\'' },
99 	{ "$u3d$", '=' },
100 	{ "$u5b$", '[' },
101 	{ "$u5d$", ']' },
102 	{ "$u7b$", '{' },
103 	{ "$u7d$", '}' },
104 	{ "$u3b$", ';' },
105 	{ "$u2b$", '+' },
106 	{ "$u22$", '"' }
107 };
108 static const size_t rust_charmap_sz = ARRAY_SIZE(rust_charmap);
109 
110 static void *rustdem_alloc(custr_alloc_t *, size_t);
111 static void rustdem_free(custr_alloc_t *, void *, size_t);
112 
113 static boolean_t rustdem_append_c(rustdem_state_t *, char);
114 static boolean_t rustdem_all_ascii(const strview_t *);
115 
116 static boolean_t rustdem_parse_prefix(rustdem_state_t *, strview_t *);
117 static boolean_t rustdem_parse_name(rustdem_state_t *, strview_t *);
118 static boolean_t rustdem_parse_hash(rustdem_state_t *, strview_t *);
119 static boolean_t rustdem_parse_num(rustdem_state_t *, strview_t *, uint64_t *);
120 static boolean_t rustdem_parse_special(rustdem_state_t *, strview_t *);
121 static boolean_t rustdem_add_sep(rustdem_state_t *);
122 
123 char *
124 rust_demangle(const char *s, size_t slen, sysdem_ops_t *ops)
125 {
126 	rustdem_state_t st = {
127 		.rds_str = s,
128 		.rds_ops = ops,
129 	};
130 	custr_alloc_ops_t custr_ops = {
131 		.custr_ao_alloc = rustdem_alloc,
132 		.custr_ao_free = rustdem_free
133 	};
134 	custr_alloc_t custr_alloc = {
135 		.cua_version = CUSTR_VERSION
136 	};
137 	strview_t sv;
138 	int ret;
139 
140 	if (custr_alloc_init(&custr_alloc, &custr_ops) != 0)
141 		return (NULL);
142 	custr_alloc.cua_arg = &st;
143 
144 	sv_init_str(&sv, s, s + slen);
145 
146 	if (sv_remaining(&sv) < 1 || sv_peek(&sv, -1) != 'E') {
147 		DEMDEBUG("ERROR: string is either too small or does not end "
148 		    "with 'E'");
149 		errno = EINVAL;
150 		return (NULL);
151 	}
152 
153 	if (!rustdem_parse_prefix(&st, &sv)) {
154 		DEMDEBUG("ERROR: could not parse prefix");
155 		errno = EINVAL;
156 		return (NULL);
157 	}
158 	DEMDEBUG("parsed prefix; remaining='%.*s'", SV_PRINT(&sv));
159 
160 	if (!rustdem_all_ascii(&sv)) {
161 		/* rustdem_all_ascii() provides debug output */
162 		errno = EINVAL;
163 		return (NULL);
164 	}
165 
166 	if ((ret = custr_xalloc(&st.rds_demangled, &custr_alloc)) != 0)
167 		return (NULL);
168 
169 	while (sv_remaining(&sv) > 1) {
170 		if (rustdem_parse_name(&st, &sv))
171 			continue;
172 		if (st.rds_error != 0)
173 			goto fail;
174 	}
175 
176 	if (st.rds_error != 0 || !sv_consume_if_c(&sv, 'E'))
177 		goto fail;
178 
179 	char *res = xstrdup(ops, custr_cstr(st.rds_demangled));
180 	if (res == NULL) {
181 		st.rds_error = errno;
182 		goto fail;
183 	}
184 
185 	custr_free(st.rds_demangled);
186 	DEMDEBUG("result = '%s'", res);
187 	return (res);
188 
189 fail:
190 	custr_free(st.rds_demangled);
191 	errno = st.rds_error;
192 	return (NULL);
193 }
194 
195 static boolean_t
196 rustdem_parse_prefix(rustdem_state_t *st, strview_t *svp)
197 {
198 	strview_t pfx;
199 
200 	sv_init_sv(&pfx, svp);
201 
202 	DEMDEBUG("checking for '_ZN' or '__ZN' in '%.*s'", SV_PRINT(&pfx));
203 
204 	if (st->rds_error != 0)
205 		return (B_FALSE);
206 
207 	if (!sv_consume_if_c(&pfx, '_'))
208 		return (B_FALSE);
209 
210 	(void) sv_consume_if_c(&pfx, '_');
211 
212 	if (!sv_consume_if_c(&pfx, 'Z') || !sv_consume_if_c(&pfx, 'N'))
213 		return (B_FALSE);
214 
215 	/* Update svp with new position */
216 	sv_init_sv(svp, &pfx);
217 	return (B_TRUE);
218 }
219 
220 static boolean_t
221 rustdem_parse_name_segment(rustdem_state_t *st, strview_t *svp, boolean_t first)
222 {
223 	strview_t sv;
224 	strview_t name;
225 	uint64_t len;
226 	size_t rem;
227 	boolean_t last = B_FALSE;
228 
229 	if (st->rds_error != 0 || sv_remaining(svp) == 0)
230 		return (B_FALSE);
231 
232 	sv_init_sv(&sv, svp);
233 
234 	if (!rustdem_parse_num(st, &sv, &len)) {
235 		DEMDEBUG("ERROR: no leading length");
236 		st->rds_error = EINVAL;
237 		return (B_FALSE);
238 	}
239 
240 	rem = sv_remaining(&sv);
241 
242 	if (rem < len || len == SIZE_MAX) {
243 		st->rds_error = EINVAL;
244 		return (B_FALSE);
245 	}
246 
247 	/* Is this the last segment before the terminating E? */
248 	if (rem == len + 1) {
249 		VERIFY3U(sv_peek(&sv, -1), ==, 'E');
250 		last = B_TRUE;
251 	}
252 
253 	if (!first && !rustdem_add_sep(st))
254 		return (B_FALSE);
255 
256 	/* Reduce length of seg to the length we parsed */
257 	(void) sv_init_sv_range(&name, &sv, len);
258 
259 	DEMDEBUG("%s: segment='%.*s'", __func__, SV_PRINT(&name));
260 
261 	/*
262 	 * A rust hash starts with 'h', and is the last component of a name
263 	 * before the terminating 'E'
264 	 */
265 	if (sv_peek(&name, 0) == 'h' && last) {
266 		if (!rustdem_parse_hash(st, &name))
267 			return (B_FALSE);
268 		goto done;
269 	}
270 
271 	while (sv_remaining(&name) > 0) {
272 		switch (sv_peek(&name, 0)) {
273 		case '$':
274 			if (rustdem_parse_special(st, &name))
275 				continue;
276 			break;
277 		case '_':
278 			if (sv_peek(&name, 1) == '$') {
279 				/*
280 				 * Only consume/ignore '_'.  Leave
281 				 * $ for next round.
282 				 */
283 				sv_consume_n(&name, 1);
284 				continue;
285 			}
286 			break;
287 		case '.':
288 			/* Convert '..' to '::' */
289 			if (sv_peek(&name, 1) != '.')
290 				break;
291 
292 			if (!rustdem_add_sep(st))
293 				return (B_FALSE);
294 
295 			sv_consume_n(&name, 2);
296 			continue;
297 		default:
298 			break;
299 		}
300 
301 		if (custr_appendc(st->rds_demangled,
302 		    sv_consume_c(&name)) != 0) {
303 			st->rds_error = ENOMEM;
304 			return (B_FALSE);
305 		}
306 	}
307 
308 done:
309 	DEMDEBUG("%s: consumed '%.*s'", __func__, (int)len, svp->sv_first);
310 	sv_consume_n(&sv, len);
311 	sv_init_sv(svp, &sv);
312 	return (B_TRUE);
313 }
314 
315 static boolean_t
316 rustdem_parse_name(rustdem_state_t *st, strview_t *svp)
317 {
318 	strview_t name;
319 	boolean_t first = B_TRUE;
320 
321 	if (st->rds_error != 0)
322 		return (B_FALSE);
323 
324 	sv_init_sv(&name, svp);
325 
326 	if (sv_remaining(&name) == 0)
327 		return (B_FALSE);
328 
329 	while (sv_remaining(&name) > 0 && sv_peek(&name, 0) != 'E') {
330 		if (!rustdem_parse_name_segment(st, &name, first))
331 			return (B_FALSE);
332 		first = B_FALSE;
333 	}
334 
335 	sv_init_sv(svp, &name);
336 	return (B_TRUE);
337 }
338 
339 static boolean_t
340 rustdem_parse_hash(rustdem_state_t *st, strview_t *svp)
341 {
342 	strview_t sv;
343 
344 	sv_init_sv(&sv, svp);
345 
346 	VERIFY(sv_consume_if_c(&sv, 'h'));
347 	if (!rustdem_append_c(st, 'h'))
348 		return (B_FALSE);
349 
350 	while (sv_remaining(&sv) > 0) {
351 		char c = sv_consume_c(&sv);
352 
353 		switch (c) {
354 		/*
355 		 * The upper-case hex digits (A-F) are excluded as valid
356 		 * hash values for several reasons:
357 		 *
358 		 * 1. It would result in two different possible names for
359 		 * the same function, leading to ambiguity in linking (among
360 		 * other things).
361 		 *
362 		 * 2. It would cause potential ambiguity in parsing -- is a
363 		 * trailing 'E' part of the hash, or the terminating character
364 		 * in the mangled name?
365 		 *
366 		 * 3. No examples were able to be found in the wild where
367 		 * uppercase digits are used, and other rust demanglers all
368 		 * seem to assume the hash must contain lower-case hex digits.
369 		 */
370 		case '0': case '1': case '2': case '3':
371 		case '4': case '5': case '6': case '7':
372 		case '8': case '9': case 'a': case 'b':
373 		case 'c': case 'd': case 'e': case 'f':
374 			if (!rustdem_append_c(st, c))
375 				return (B_FALSE);
376 			break;
377 		default:
378 			return (B_FALSE);
379 		}
380 	}
381 
382 	sv_init_sv(svp, &sv);
383 	return (B_TRUE);
384 }
385 
386 /*
387  * A 10 digit value would imply a name 1Gb or larger in size.  It seems
388  * unlikely to the point of absurdity any such value could every possibly
389  * be valid (or even have compiled properly).  This also prevents the
390  * uint64_t conversion from possibly overflowing since the value must always
391  * be below 10 * UINT32_MAX.
392  */
393 #define	MAX_DIGITS 10
394 
395 static boolean_t
396 rustdem_parse_num(rustdem_state_t *restrict st, strview_t *restrict svp,
397     uint64_t *restrict valp)
398 {
399 	strview_t snum;
400 	uint64_t v = 0;
401 	size_t ndigits = 0;
402 	char c;
403 
404 	if (st->rds_error != 0)
405 		return (B_FALSE);
406 
407 	sv_init_sv(&snum, svp);
408 
409 	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(&snum));
410 
411 	c = sv_peek(&snum, 0);
412 	if (!ISDIGIT(c)) {
413 		DEMDEBUG("%s: ERROR no digits in str\n", __func__);
414 		st->rds_error = EINVAL;
415 		return (B_FALSE);
416 	}
417 
418 	/*
419 	 * Since there is currently no official specification on rust name
420 	 * mangling, only that it has been stated that rust follows what
421 	 * C++ mangling does.  In the Itanium C++ ABI (what practically
422 	 * every non-Windows C++ implementation uses these days), it
423 	 * explicitly disallows leading 0s in numeric values (except for
424 	 * substition and template indexes, which aren't relevant here).
425 	 * We enforce the same restriction -- if a rust implementation allowed
426 	 * leading zeros in numbers (basically segment lengths) it'd
427 	 * cause all sorts of ambiguity problems with names that likely lead
428 	 * to much bigger problems with linking and such, so this seems
429 	 * reasonable.
430 	 */
431 	if (c == '0') {
432 		DEMDEBUG("%s: ERROR number starts with leading 0\n", __func__);
433 		st->rds_error = EINVAL;
434 		return (B_FALSE);
435 	}
436 
437 	while (sv_remaining(&snum) > 0 && ndigits <= MAX_DIGITS) {
438 		c = sv_consume_c(&snum);
439 
440 		if (!ISDIGIT(c))
441 			break;
442 
443 		v *= 10;
444 		v += c - '0';
445 		ndigits++;
446 	}
447 
448 	if (ndigits > MAX_DIGITS) {
449 		DEMDEBUG("%s: value %llu is too large\n", __func__, v);
450 		st->rds_error = ERANGE;
451 		return (B_FALSE);
452 	}
453 
454 	DEMDEBUG("%s: num=%llu", __func__, v);
455 
456 	*valp = v;
457 	sv_consume_n(svp, ndigits);
458 	return (B_TRUE);
459 }
460 
461 static boolean_t
462 rustdem_parse_special(rustdem_state_t *restrict st, strview_t *restrict svp)
463 {
464 	if (st->rds_error != 0)
465 		return (B_FALSE);
466 
467 	if (sv_peek(svp, 0) != '$')
468 		return (B_FALSE);
469 
470 	for (size_t i = 0; i < rust_charmap_sz; i++) {
471 		if (sv_consume_if(svp, rust_charmap[i].ruc_seq)) {
472 			if (!rustdem_append_c(st, rust_charmap[i].ruc_ch))
473 				return (B_FALSE);
474 			return (B_TRUE);
475 		}
476 	}
477 	return (B_FALSE);
478 }
479 
480 static boolean_t
481 rustdem_add_sep(rustdem_state_t *st)
482 {
483 	if (st->rds_error != 0)
484 		return (B_FALSE);
485 
486 	if (!rustdem_append_c(st, ':') ||
487 	    !rustdem_append_c(st, ':'))
488 		return (B_FALSE);
489 
490 	return (B_TRUE);
491 }
492 
493 static boolean_t
494 rustdem_append_c(rustdem_state_t *st, char c)
495 {
496 	if (st->rds_error != 0)
497 		return (B_FALSE);
498 
499 	if (custr_appendc(st->rds_demangled, c) == 0)
500 		return (B_TRUE);
501 
502 	st->rds_error = errno;
503 	return (B_FALSE);
504 }
505 
506 static boolean_t
507 rustdem_all_ascii(const strview_t *svp)
508 {
509 	strview_t p;
510 
511 	sv_init_sv(&p, svp);
512 
513 	while (sv_remaining(&p) > 0) {
514 		char c = sv_consume_c(&p);
515 
516 		/*
517 		 * #including <sys/ctype.h> conflicts with <ctype.h>.  Since
518 		 * we want the C locale macros (ISDIGIT, etc), it also means
519 		 * we can't use isascii(3C).
520 		 */
521 		if ((c & 0x80) != 0) {
522 			DEMDEBUG("%s: found non-ascii character 0x%02hhx at "
523 			    "offset %tu", __func__, c,
524 			    (ptrdiff_t)(p.sv_first - svp->sv_first));
525 			return (B_FALSE);
526 		}
527 	}
528 	return (B_TRUE);
529 }
530 
531 static void *
532 rustdem_alloc(custr_alloc_t *cao, size_t len)
533 {
534 	rustdem_state_t *st = cao->cua_arg;
535 	return (zalloc(st->rds_ops, len));
536 }
537 
538 static void
539 rustdem_free(custr_alloc_t *cao, void *p, size_t len)
540 {
541 	rustdem_state_t *st = cao->cua_arg;
542 	xfree(st->rds_ops, p, len);
543 }
544