libdemangle/common/rust-v0.c

/*
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms of version
 * 1.0 of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 */

/*
 * Copyright 2019 Joyent, Inc.
 * Copyright 2021 Jason King
 */

/* BEGIN CSTYLED */

/*
 * This implements the 'symbol_name_mangling_v2' demangling for rust as
 * described in Rust RFC 2603 as opposed to the original (now called
 * legacy) mangling older versions of rust used (implemented in rust.c).
 *
 * The specification can be viewed at:
 *     https://github.com/rust-lang/rfcs/blob/master/text/2603-rust-symbol-name-mangling-v0.md
 */

/* END CSTYLED */

#include <errno.h>
#include <libcustr.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "rust.h"

/*
 * Help track amount of additional output added to rs_demangled across
 * a function call (to allow that portion to be output for debugging)
 */
#define	SAVE_LEN(_st, _len) _len = custr_len((_st)->rs_demangled)
#define	CSTR_END(_st, _len)					\
	((int)(custr_len((_st)->rs_demangled) - (_len))),	\
	custr_cstr((_st)->rs_demangled) + (_len)

typedef enum const_type_class {
	CTC_INVALID = -1,
	CTC_UNSIGNED,
	CTC_SIGNED,
	CTC_CHAR,
	CTC_BOOL,
} const_type_class_t;

/*
 * Sometimes, parsing something is optional.  In this case a failure to
 * parse is fine, however we still want to consider a fatal error as
 * failure.
 */
#define	OPTIONAL(_st, _f) ((_f) || !HAS_ERROR(_st))

static boolean_t rustv0_valid_sym(const strview_t *);
static const_type_class_t rustv0_classify_const_type(char);
static boolean_t rustv0_parse_hex_num(rust_state_t *restrict,
    strview_t *restrict, uint64_t *restrict);
static boolean_t rustv0_parse_base62(rust_state_t *restrict,
    strview_t *restrict, uint64_t *restrict);

static boolean_t rustv0_parse_undisambiguated_identifier(
    rust_state_t *restrict, strview_t *restrict, boolean_t);
static boolean_t rustv0_parse_disambiguator(rust_state_t *restrict,
    strview_t *restrict, uint64_t *restrict);

static boolean_t rustv0_parse_path(rust_state_t *restrict, strview_t *restrict,
    boolean_t);
static boolean_t rustv0_parse_impl_path(rust_state_t *restrict,
    strview_t *restrict, boolean_t);
static boolean_t rustv0_parse_nested_path(rust_state_t *restrict,
    strview_t *restrict, boolean_t);
static boolean_t rustv0_parse_basic_type(rust_state_t *restrict,
    strview_t *restrict);
static boolean_t rustv0_parse_backref(rust_state_t *restrict,
    strview_t *restrict,
    boolean_t (*)(rust_state_t *restrict, strview_t *restrict, boolean_t),
    boolean_t);
static boolean_t rustv0_parse_lifetime(rust_state_t *restrict,
    strview_t *restrict);
static boolean_t rustv0_parse_const(rust_state_t *restrict,
    strview_t *restrict, boolean_t);
static boolean_t rustv0_parse_fnsig(rust_state_t *restrict,
    strview_t *restrict);
static boolean_t rustv0_parse_dynbounds(rust_state_t *restrict,
    strview_t *restrict);
static boolean_t rustv0_parse_generic_arg(rust_state_t *restrict,
    strview_t *restrict, boolean_t);

boolean_t
rust_demangle_v0(rust_state_t *restrict st, strview_t *restrict sv)
{
	boolean_t save_skip;
	boolean_t ret;

	/* Make sure all the characters are valid */
	if (!rustv0_valid_sym(sv)) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	/*
	 * <symbol-name> = "_R" [<decimal-number>] <path>
	 *	[<instantiating-crate>]
	 *
	 * We've already parsed the prefix in rust_demangle(), as well
	 * as made sure there's no [<decimal-number>] present, so
	 * start with <path>.
	 */
	if (!rustv0_parse_path(st, sv, B_TRUE))
		return (B_FALSE);

	/* [<instantiating crate>] -- parse but don't save */
	SKIP_BEGIN(st, save_skip);
	ret = OPTIONAL(st, rustv0_parse_path(st, sv, B_FALSE));
	SKIP_END(st, save_skip);
	if (!ret)
		return (B_FALSE);

	/* If nothing's left, we know we're done */
	if (sv_remaining(sv) == 0)
		return (!HAS_ERROR(st));

	/*
	 * LLVM sometimes will suffix symbols starting with a '.'
	 * followed by extra data. For things that start with
	 * ".llvm.", we discard the rest of the string.  For
	 * other things that start with '.', we copy the
	 * results to the final string. This matches
	 * what the rust native demangler crate does, and
	 * we don't see a reason to deviate from their
	 * behavior.
	 */
	if (sv_consume_if(sv, ".llvm."))
		return (!HAS_ERROR(st));

	if (sv_peek(sv, 0) != '.') {
		DEMDEBUG("%s: Unexpected trailing data at the end of the "
		    "name: '%.*s'", __func__, SV_PRINT(sv));
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	return (rust_append_sv(st, sv_remaining(sv), sv));
}

/*
 * Parse an optional list terminated by 'E'. Each result of 'fn' is
 * separated by 'sep' in the output.
 */
static boolean_t
rustv0_parse_opt_list(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t (*fn)(rust_state_t *restrict, strview_t *restrict, boolean_t),
    const char *restrict sep, boolean_t bval, size_t *restrict countp)
{
	size_t count = 0;

	DEMDEBUG("%s: str = '%.*s'", __func__, SV_PRINT(sv));

	while (sv_remaining(sv) > 0) {
		if (sv_consume_if_c(sv, 'E')) {
			if (countp != NULL)
				*countp += count;
			return (B_TRUE);
		}

		if (count > 0 && !rust_append(st, sep))
			return (B_FALSE);

		if (!fn(st, sv, bval))
			return (B_FALSE);

		count++;
	}

	/*
	 * An optional list should terminate with an 'E'.  If we get here,
	 * we ran out of charaters and didn't terminate as we should.
	 */
	return (B_FALSE);
}

static boolean_t
rustv0_parse_uint_type(rust_state_t *restrict st, strview_t *sv)
{
	const char *str = NULL;
	strview_t save;
	char c;

	if (HAS_ERROR(st) || sv_remaining(sv) == 0)
		return (B_FALSE);

	sv_init_sv(&save, sv);

	switch (c = sv_consume_c(sv)) {
	case 'h':
		str = "u8";
		break;
	case 't':
		str = "u16";
		break;
	case 'm':
		str = "u32";
		break;
	case 'y':
		str = "u64";
		break;
	case 'o':
		str = "u128";
		break;
	case 'j':	/* usize */
		str = "usize";
		break;
	default:
		sv_init_sv(sv, &save);
		return (B_FALSE);
	}

	DEMDEBUG("%s: %c -> %s", __func__, c, str);
	return (rust_append(st, str));
}

static boolean_t
rustv0_parse_basic_type(rust_state_t *restrict st, strview_t *restrict sv)
{
	const char *str = NULL;
	strview_t save;
	char c;

	if (HAS_ERROR(st) || sv_remaining(sv) == 0)
		return (B_FALSE);

	if (rustv0_parse_uint_type(st, sv))
		return (B_TRUE);

	sv_init_sv(&save, sv);

	switch (c = sv_consume_c(sv)) {
	case 'a':
		str = "i8";
		break;
	case 'b':
		str = "bool";
		break;
	case 'c':
		str = "char";
		break;
	case 'd':
		str = "f64";
		break;
	case 'e':
		str = "str";
		break;
	case 'f':
		str = "f32";
		break;
	case 'i':
		str = "isize";
		break;
	case 'l':
		str = "i32";
		break;
	case 'n':
		str = "i128";
		break;
	case 'p':
		str = "_";
		break;
	case 's':
		str = "i16";
		break;
	case 'u':
		str = "()";
		break;
	case 'v':
		str = "...";
		break;
	case 'x':
		str = "i64";
		break;
	case 'z':
		str = "!";
		break;
	default:
		sv_init_sv(sv, &save);
		return (B_FALSE);
	}

	DEMDEBUG("%s: %c -> %s", __func__, c, str);
	return (rust_append(st, str));
}

static boolean_t
rustv0_parse_type(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t dummy __unused)
{
	strview_t save;
	size_t len, tuple_elem_count;
	boolean_t ret;
	char c;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	SAVE_LEN(st, len);
	sv_init_sv(&save, sv);

	switch (c = sv_consume_c(sv)) {
	case 'A':
		ret = rust_appendc(st, '[') &&
		    rustv0_parse_type(st, sv, B_FALSE) &&
		    rust_append(st, "; ") &&
		    rustv0_parse_const(st, sv, B_FALSE) &&
		    rust_appendc(st, ']');
		break;
	case 'S':
		ret = rust_appendc(st, '[') &&
		    rustv0_parse_type(st, sv, B_FALSE) &&
		    rust_appendc(st, ']');
		break;
	case 'T':
		tuple_elem_count = 0;
		ret = rust_appendc(st, '(') &&
		    rustv0_parse_opt_list(st, sv, rustv0_parse_type, ", ",
		    B_FALSE, &tuple_elem_count) &&
		    rust_append(st, (tuple_elem_count == 1) ? ",)" : ")");
		break;
	case 'R':
	case 'Q':
		/* `&mut T` or `&'... mut T` */
		if (!(ret = rust_appendc(st, '&')))
			break;

		/*
		 * lifetime is optional, but we need to add a trailing
		 * space if present (so we cannot use the OPTIONAL macro).
		 */
		if (rustv0_parse_lifetime(st, sv)) {
			if (!(ret = rust_appendc(st, ' ')))
				break;
		} else if (HAS_ERROR(st)) {
			break;
		}

		ret = rust_append(st, (c == 'Q') ? "mut " : "") &&
		    rustv0_parse_type(st, sv, B_FALSE);
		break;
	case 'P':
		ret = rust_append(st, "*const ") &&
		    rustv0_parse_type(st, sv, B_FALSE);
		break;
	case 'O':
		ret = rust_append(st, "*mut ") &&
		    rustv0_parse_type(st, sv, B_FALSE);
		break;
	case 'F':
		ret = rustv0_parse_fnsig(st, sv);
		break;
	case 'D':
		ret = rust_append(st, "dyn ") &&
		    rustv0_parse_dynbounds(st, sv);
		if (!ret)
			break;

		/*
		 * Rust RFC2603 shows the lifetime as required, however
		 * it appears this is optional.
		 */
		DEMDEBUG("%s: pre-lifetime: '%*s'", __func__, SV_PRINT(sv));

		/*
		 * We only want to print a non-zero (non "'_")
		 * lifetime.
		 */
		if (sv_consume_if(sv, "L_"))
			break;

		/*
		 * But if there is a lifetime we want to print,
		 * we want to prepend " + " before it.
		 */
		if (sv_peek(sv, 0) == 'L' &&
		    !(ret = rust_append(st, " + ")))
			break;

		ret = rustv0_parse_lifetime(st, sv);
		break;
	default:
		sv_init_sv(sv, &save);

		ret = rustv0_parse_backref(st, sv, rustv0_parse_type,
		    B_FALSE) ||
		    rustv0_parse_basic_type(st, sv);
		if (ret)
			break;

		ret = rustv0_parse_path(st, sv, B_FALSE);
		break;
	}

	DEMDEBUG("%s: type='%.*s' (%s)", __func__, CSTR_END(st, len),
	    ret ? "success" : "fail");

	return (ret);
}

/*
 * <path> = "C" <identifier>		crate root
 *	| "M" <impl-path> <type>	<T>
 *	| "X" <impl-path> <type> <path>	<T as Trait> (trait impl)
 *	| "Y" <type> <path>		<T as Trait> (trait definition)
 *	| "N" <ns> <path> <identifier>	...::ident (nested path)
 *	| "I" <path> {<generic-arg>} "E" ...<T, U>
 *	| <backref>
 */
static boolean_t
rustv0_parse_path(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t in_value)
{
	strview_t save;
	uint64_t disamb = 0;
	size_t len;
	boolean_t ret = B_FALSE;
	boolean_t save_skip;
	boolean_t args_stay_save = st->rs_args_stay_open;
	boolean_t args_open_save = st->rs_args_is_open;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	SAVE_LEN(st, len);
	sv_init_sv(&save, sv);

	switch (sv_consume_c(sv)) {
	case 'C':
		if (!OPTIONAL(st, rustv0_parse_disambiguator(st, sv, &disamb)))
			goto done;

		if (!rustv0_parse_undisambiguated_identifier(st, sv, B_FALSE))
			goto done;

		if (st->rs_verbose &&
		    !rust_append_printf(st, "[%" PRIx64 "]", disamb))
			goto done;
		break;
	case 'M':
		SKIP_BEGIN(st, save_skip);
		if (!rustv0_parse_impl_path(st, sv, in_value)) {
			SKIP_END(st, save_skip);
			goto done;
		}
		SKIP_END(st, save_skip);

		if (!rust_appendc(st, '<') ||
		    !rustv0_parse_type(st, sv, B_FALSE) ||
		    !rust_appendc(st, '>'))
			goto done;
		break;
	case 'X':
		SKIP_BEGIN(st, save_skip);
		if (!rustv0_parse_impl_path(st, sv, in_value)) {
			SKIP_END(st, save_skip);
			goto done;
		}
		SKIP_END(st, save_skip);
		/*FALLTHRU*/
	case 'Y':
		if (!rust_appendc(st, '<') ||
		    !rustv0_parse_type(st, sv, B_FALSE) ||
		    !rust_append(st, " as ") ||
		    !rustv0_parse_path(st, sv, B_FALSE) ||
		    !rust_appendc(st, '>'))
			goto done;
		break;
	case 'N':
		if (!rustv0_parse_nested_path(st, sv, in_value))
			goto done;
		break;
	case 'I':
		st->rs_args_stay_open = B_FALSE;
		st->rs_args_is_open = B_FALSE;

		if (!rustv0_parse_path(st, sv, in_value))
			goto done;

		if (in_value && !rust_append(st, "::"))
			goto done;

		if (!rust_appendc(st, '<') ||
		    !rustv0_parse_opt_list(st, sv, rustv0_parse_generic_arg,
		    ", ", B_FALSE, NULL))
			goto done;

		st->rs_args_stay_open = args_stay_save;
		st->rs_args_is_open = args_open_save;

		/*
		 * If we were asked to not close our list, then don't and
		 * indicate that the list is open.
		 */
		if (st->rs_args_stay_open) {
			st->rs_args_stay_open = B_FALSE;
			st->rs_args_is_open = B_TRUE;
		} else if (!rust_appendc(st, '>')) {
			goto done;
		}
		break;
	default:
		/*
		 * Didn't recognize the letter, so it has to be a path. Restore
		 * sv to state prior to switch and continue.
		 */
		sv_init_sv(sv, &save);
		if (!rustv0_parse_backref(st, sv, rustv0_parse_path, in_value))
			goto done;
	}

	ret = B_TRUE;

done:
	DEMDEBUG("%s: path='%.*s' (%s)", __func__, CSTR_END(st, len),
	    ret ? "success" : "fail");

	return (ret);
}

static boolean_t
rustv0_parse_impl_path(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t in_value)
{
	uint64_t val = 0;

	return (OPTIONAL(st, rustv0_parse_disambiguator(st, sv, &val)) &&
	    rustv0_parse_path(st, sv, in_value));
}

/*
 * A bit of a hack -- when printing a nested path, we need to know
 * if the identifier is there or not in order to correctly format
 * the output preceeding it (when present). This peeks ahead and
 * determines this.
 */
static boolean_t
rustv0_has_name(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t *has_namep)
{
	strview_t save;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	sv_init_sv(&save, sv);

	/* For checking the length, we don't care if it's punycode or not */
	(void) sv_consume_if_c(&save, 'u');

	if (sv_remaining(sv) == 0) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	if (sv_consume_if_c(&save, '0')) {
		*has_namep = B_FALSE;
		return (B_TRUE);
	}

	*has_namep = B_TRUE;
	return (B_TRUE);
}

static boolean_t
rustv0_parse_nested_path(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t in_value)
{
	uint64_t disambiguator = 0;
	size_t len = 0;
	char ns;
	boolean_t ret = B_FALSE;
	boolean_t has_name;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	SAVE_LEN(st, len);

	ns = sv_consume_c(sv);

	if (!rustv0_parse_path(st, sv, in_value))
		goto done;

	if (!OPTIONAL(st, rustv0_parse_disambiguator(st, sv, &disambiguator)))
		goto done;

	if (!rustv0_has_name(st, sv, &has_name))
		goto done;

	if (ISUPPER(ns)) {
		if (!rust_append(st, "::{"))
			goto done;

		switch (ns) {
		case 'C':
			if (!rust_append(st, "closure"))
				goto done;
			break;
		case 'S':
			if (!rust_append(st, "shim"))
				goto done;
			break;
		default:
			if (!rust_appendc(st, ns))
				goto done;
			break;
		}

		if (has_name && !rust_appendc(st, ':'))
			goto done;

		if (!rustv0_parse_undisambiguated_identifier(st, sv, B_FALSE))
			goto done;

		ret = rust_append_printf(st, "#%" PRIu64 "}", disambiguator);
	} else {
		if (has_name) {
			if (!(ret = rust_append(st, "::")))
				goto done;
		}
		ret = rustv0_parse_undisambiguated_identifier(st, sv, B_FALSE);
	}

done:
	DEMDEBUG("%s: nested path = '%.*s' (%s)", __func__, CSTR_END(st, len),
	    ret ? "success" : "fail");

	return (ret);
}

/*
 * <disambiguator> = "s" <base-64-number>
 *
 */
static boolean_t
rustv0_parse_disambiguator(rust_state_t *restrict st, strview_t *restrict sv,
    uint64_t *valp)
{
	if (HAS_ERROR(st) || sv_remaining(sv) < 2)
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	*valp = 0;

	if (!sv_consume_if_c(sv, 's'))
		return (B_FALSE);

	if (!rustv0_parse_base62(st, sv, valp)) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	/*
	 * Rust RFC 2603 details this in Appendix A, but not the main
	 * portion of the RFC. If no disambiguator is present, the value
	 * is 0, if the decoded value is 0, the index is 1, ...
	 * rustv0_parse_base62() already adjusts _ -> 0, 0 -> 1, so we
	 * only need to add one here to complete the adjustment.
	 */
	*valp = *valp + 1;

	DEMDEBUG("%s: disambiguator=%" PRIu64, __func__, *valp);
	return (B_TRUE);
}

/* <undisambiguated-identifier> = ["u"] <decimal-number> ["_"] <bytes> */
static boolean_t
rustv0_parse_undisambiguated_identifier(rust_state_t *restrict st,
    strview_t *restrict sv, boolean_t repl_underscore)
{
	uint64_t len = 0;
	boolean_t puny = B_FALSE;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	if (sv_consume_if_c(sv, 'u'))
		puny = B_TRUE;

	if (!rust_parse_base10(st, sv, &len))
		return (B_FALSE);

	/* skip optional separator '_' */
	(void) sv_consume_if_c(sv, '_');

	if (sv_remaining(sv) < len) {
		DEMDEBUG("%s: ERROR: identifier length (%" PRIu64 ") "
		    "> remaining bytes (%zu)", __func__, len,
		    sv_remaining(sv));
		return (B_FALSE);
	}

	/* 0 length identifiers are acceptable */
	if (len == 0)
		return (B_TRUE);

	if (puny) {
		strview_t ident;

		sv_init_sv_range(&ident, sv, len);
		if (!rustv0_puny_decode(st, &ident, repl_underscore))
			return (B_FALSE);

		sv_consume_n(sv, len);
		return (B_TRUE);
	}

	/*
	 * rust identifiers do not contain '-'. However ABI identifiers
	 * are allowed to contain them (e.g. extern "foo-bar" fn ...).
	 * They are substituted with '_' in the mangled output. If we
	 * do not need to reverse this, we can just append 'len' bytes
	 * of sv.  Otherwise we need to go through and reverse this
	 * substitution.
	 */
	if (!repl_underscore)
		return (rust_append_sv(st, len, sv));

	/*
	 * We checked earlier that len < sv_remaining(sv); so this loop
	 * cannot overrun.
	 */
	for (size_t i = 0; i < len; i++) {
		char c = sv_consume_c(sv);

		if (c == '_')
			c = '-';

		if (!rust_appendc(st, c))
			return (B_FALSE);
	}

	return (B_TRUE);
}

/* <backref> = "B" <base-62-number> */
static boolean_t
rustv0_parse_backref(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t (*fn)(rust_state_t *restrict, strview_t *restrict, boolean_t b),
    boolean_t bval)
{
	strview_t backref;
	strview_t target;
	uint64_t idx = 0;
	size_t save_len;
	size_t len;

	if (HAS_ERROR(st))
		return (B_FALSE);

	sv_init_sv(&backref, sv);

	if (!sv_consume_if_c(sv, 'B'))
		return (B_FALSE);

	DEMDEBUG("%s: str='B%.*s'", __func__, SV_PRINT(sv));

	if (!rustv0_parse_base62(st, sv, &idx)) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	/*
	 * Determine how many bytes we've consumed (up to the start of
	 * the current backref token).
	 */
	VERIFY3P(backref.sv_first, >=, st->rs_orig.sv_first);
	len = (size_t)(uintptr_t)(backref.sv_first - st->rs_orig.sv_first);

	/*
	 * The backref can only refer to an index prior to the start of
	 * the current backref token -- that is must always refer back in
	 * the string, never to the current position or beyond.
	 */
	if (idx >= len) {
		DEMDEBUG("%s: ERROR: backref index (%" PRIu64 ") "
		    "is out of range [0, %zu)", __func__, idx, len);
		st->rs_error = ERANGE;
		return (B_FALSE);
	}

	/*
	 * Create a strview_t of the original string (sans prefix) by
	 * copying from st->rs_orig. The length of the target strview_t is
	 * capped to end immediately prior to this backref token. Since we
	 * enforce that backrefs must always refer to already processed
	 * portions of the string (i.e. must always refer backwards), and the
	 * length of the strview_t is set to end prior to the start of this
	 * backref token, we guarantee processing of a backref will always
	 * terminate before it can possibly encounter this backref token
	 * and cause a loop -- either the processing terminates normally or
	 * it reaches the end of the capped strview_t.
	 */
	sv_init_sv_range(&target, &st->rs_orig, len);

	/*
	 * Consume all the input in the target strview_t up to the index
	 */
	sv_consume_n(&target, idx);

	DEMDEBUG("%s: backref starting at %" PRIu64 " str='%.*s'%s", __func__,
	    idx, SV_PRINT(&target), st->rs_skip ? " (skipping)" : "");

	/*
	 * If we're skipping the output, there's no reason to bother reparsing
	 * the output -- we're not going to save it. We still setup everything
	 * so that the debug output is still emitted.
	 */
	if (st->rs_skip)
		return (B_TRUE);

	SAVE_LEN(st, save_len);
	if (!fn(st, &target, bval))
		return (B_FALSE);

	DEMDEBUG("%s: backref is '%.*s'", __func__, CSTR_END(st, save_len));
	return (B_TRUE);
}

static boolean_t
rustv0_append_lifetime(rust_state_t *restrict st, uint64_t lifetime)
{
	uint64_t bound_lt;

	if (HAS_ERROR(st))
		return (B_FALSE);

	if (!rust_appendc(st, '\''))
		return (B_FALSE);

	if (lifetime == 0)
		return (rust_appendc(st, '_'));

	if (sub_overflow(st->rs_lt_depth, lifetime, &bound_lt)) {
		DEMDEBUG("%s: ERROR: lifetime value %" PRIu64
		    " > current depth %" PRIu64, __func__, lifetime,
		    st->rs_lt_depth);
		st->rs_lt_depth = ERANGE;
		return (B_FALSE);
	}

	/*
	 * Use 'a, 'b, ...
	 */
	if (bound_lt < 26) {
		char c = (char)bound_lt + 'a';
		return (rust_append_printf(st, "%c", c));
	}

	/*
	 * Otherwise, use '_123, '_456, ...
	 */
	return (rust_append_printf(st, "_%" PRIu64, bound_lt));
}

static boolean_t
rustv0_parse_lifetime(rust_state_t *restrict st, strview_t *restrict sv)
{
	uint64_t lifetime;

	if (!sv_consume_if_c(sv, 'L'))
		return (B_FALSE);

	if (!rustv0_parse_base62(st, sv, &lifetime))
		return (B_FALSE);

	return (rustv0_append_lifetime(st, lifetime));
}

static boolean_t
rustv0_parse_const_data(rust_state_t *restrict st,
    const_type_class_t type_class, strview_t *restrict sv)
{
	uint64_t val = 0;
	size_t save_len;
	boolean_t neg = B_FALSE;
	boolean_t ret = B_FALSE;

	VERIFY3S(type_class, !=, CTC_INVALID);

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));
	SAVE_LEN(st, save_len);

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	if (type_class == CTC_SIGNED && sv_consume_if_c(sv, 'n'))
		neg = B_TRUE;

	ret = OPTIONAL(st, rustv0_parse_hex_num(st, sv, &val)) &&
	    sv_consume_if_c(sv, '_');
	if (!ret)
		goto done;

	switch (type_class) {
	case CTC_SIGNED:
	case CTC_UNSIGNED:
		ret = rust_append_printf(st, "%s%" PRIu64, neg ? "-" : "", val);
		break;
	case CTC_BOOL:
		if (val > 1) {
			DEMDEBUG("%s: invalid bool val %" PRIu64, __func__,
			    val);
			ret = B_FALSE;
			break;
		}
		ret = rust_append_printf(st, "%s",
		    (val == 0) ? "false" : "true");
		break;
	case CTC_CHAR:
		if (val > UINT32_MAX) {
			DEMDEBUG("%s: char value %" PRIu64 " out of range",
			    __func__, val);
			ret = B_FALSE;
			break;
		}

		ret = rust_appendc(st, '\'') && rust_append_utf8_c(st, val) &&
		    rust_appendc(st, '\'');
		break;
	default:
		ret = B_FALSE;
	}

done:
	DEMDEBUG("%s: const='%.*s' (%s)", __func__, CSTR_END(st, save_len),
	    ret ? "success" : "fail");

	return (ret);
}

static boolean_t
rustv0_parse_const(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t dummy __unused)
{
	strview_t type;
	size_t start_len;
	const_type_class_t ctype_class;
	char ctype;
	boolean_t save_skip;
	boolean_t ret;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));
	SAVE_LEN(st, start_len);

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	if (rustv0_parse_backref(st, sv, rustv0_parse_const, B_FALSE))
		return (B_TRUE);

	if (sv_consume_if_c(sv, 'p')) {
		ret = rust_appendc(st, '_');
		goto done;
	}

	ctype = sv_peek(sv, 0);
	ctype_class = rustv0_classify_const_type(ctype);
	if (ctype_class == CTC_INVALID) {
		DEMDEBUG("%s: const type isn't a valid const generic type",
		    __func__);
		return (B_FALSE);
	}

	/*
	 * This isn't spelled out clearly in Rust RFC 2603, but currently
	 * only unsigned int types are allowed at this point. However, we
	 * have a bit of a potential tricky situation. Unlike formatting
	 * the other tokens, if we want to display the type, we do so
	 * _after_ the value, even though the type appears first.
	 *
	 * This is bit of a hack, but we save off the input position from
	 * sv before the parse the type. We then parse it without saving
	 * the resulting value, then parse and output the constant. If
	 * we wish to then display the type, we can go back and parse
	 * the type again, this time saving the result.
	 */
	sv_init_sv(&type, sv);

	SKIP_BEGIN(st, save_skip);
	ret = rustv0_parse_type(st, sv, B_FALSE);
	SKIP_END(st, save_skip);

	if (!ret) {
		DEMDEBUG("%s: const type isn't valid", __func__);
		return (B_FALSE);
	}

	if (sv_consume_if_c(sv, 'p')) {
		ret = rust_appendc(st, '_');
	} else {
		ret = rustv0_parse_const_data(st, ctype_class, sv);
	}
	if (!ret)
		goto done;

	if (st->rs_show_const_type) {
		ret = rust_append(st, ": ") &&
		    rustv0_parse_uint_type(st, &type);
	}

done:
	DEMDEBUG("%s: const='%.*s' (%s)", __func__, CSTR_END(st, start_len),
	    ret ? "success" : "fail");
	return (ret);
}

static boolean_t
rustv0_parse_abi(rust_state_t *restrict st, strview_t *restrict sv)
{
	DEMDEBUG("%s: str = '%.*s'", __func__, SV_PRINT(sv));

	if (sv_consume_if_c(sv, 'C'))
		return (rust_appendc(st, 'C'));

	return (rustv0_parse_undisambiguated_identifier(st, sv, B_TRUE));
}

static boolean_t
rustv0_parse_binder(rust_state_t *restrict st, strview_t *restrict sv)
{
	uint64_t n, i;

	if (!sv_consume_if_c(sv, 'G'))
		return (B_FALSE);

	if (!rustv0_parse_base62(st, sv, &n))
		return (B_FALSE);
	n += 1;

	if (!rust_append(st, "for<"))
		return (B_FALSE);

	for (i = 0; i < n; i++) {
		if (i > 0 && !rust_append(st, ", "))
			return (B_FALSE);

		st->rs_lt_depth++;
		if (!rustv0_append_lifetime(st, 1))
			return (B_FALSE);
	}

	if (!rust_append(st, "> "))
		return (B_FALSE);

	return (B_TRUE);
}

/*
 * <fn-sig> := [<binder>] ["U"] ["K" <abi>] {type} "E" <type>
 *
 * Note that while the Rust RFC states the binder is manditory, based on
 * actual examples, and comparing with the rust-based demangler, it is in
 * fact optional.
 */
static boolean_t
rustv0_parse_fnsig(rust_state_t *restrict st, strview_t *restrict sv)
{
	uint64_t save_lt = st->rs_lt_depth;

	DEMDEBUG("%s: str = '%.*s'", __func__, SV_PRINT(sv));

	if (!OPTIONAL(st, rustv0_parse_binder(st, sv)))
		return (B_FALSE);

	if (sv_consume_if_c(sv, 'U') && !rust_append(st, "unsafe "))
		return (B_FALSE);

	if (sv_consume_if_c(sv, 'K') &&
	    (!rust_append(st, "extern \"") || !rustv0_parse_abi(st, sv) ||
	    !rust_append(st, "\" ")))
		return (B_FALSE);

	if (!rust_append(st, "fn("))
		return (B_FALSE);

	if (!rustv0_parse_opt_list(st, sv, rustv0_parse_type, ", ", B_FALSE,
	    NULL)) {
		return (B_FALSE);
	}

	if (!rust_appendc(st, ')'))
		return (B_FALSE);

	/* If the return type is (), don't print it */
	if (!sv_consume_if_c(sv, 'u')) {
		if (!rust_append(st, " -> "))
			return (B_FALSE);

		if (!rustv0_parse_type(st, sv, B_FALSE))
			return (B_FALSE);
	}

	st->rs_lt_depth = save_lt;

	return (B_TRUE);
}

/*
 * <dyn-trait-assoc-binding> = "p" <undisambiguated-identifier> <type>
 */
static boolean_t
rustv0_parse_dyn_trait_assoc_binding(rust_state_t *restrict st,
    strview_t *restrict sv, boolean_t open)
{
	size_t save_len;

	if (HAS_ERROR(st))
		return (B_FALSE);

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	if (!sv_consume_if_c(sv, 'p'))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));
	SAVE_LEN(st, save_len);

	if (!rust_append(st, open ? ", " : "<"))
		return (B_FALSE);

	if (!rustv0_parse_undisambiguated_identifier(st, sv, B_FALSE)) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	if (!rust_append(st, " = "))
		return (B_FALSE);

	if (!rustv0_parse_type(st, sv, B_FALSE)) {
		st->rs_error = EINVAL;
		return (B_FALSE);
	}

	DEMDEBUG("%s: binding='%.*s'", __func__, CSTR_END(st, save_len));

	return (B_TRUE);
}

static boolean_t
rustv0_parse_dyn_trait(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t dummy __unused)
{
	boolean_t stay_save = st->rs_args_stay_open;
	boolean_t open_save = st->rs_args_is_open;
	boolean_t open = B_FALSE;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	/*
	 * This is a bit subtle, but when formatting a trait in trait,
	 * we want something like this:
	 *
	 *	dyn Trait<T, U, Assoc=X>
	 *
	 * instead of
	 *
	 *	dyn Trait<T, U, <Assoc=X>>
	 *
	 * So when parsing the path, if we encounter generic arguments, we want
	 * the arg list to remain open at the end of processing the path so
	 * we can append the bindings to it. We set rs_args_stay_open to B_TRUE
	 * to indidcate to rustv0_parse_path() that a generic argument list
	 * should not be closed (i.e. don't append a '>' at the end of the
	 * list). If rustv0_parse_path() encounters a list of generic arguments,
	 * it will also set rs->args_is_open to indiciate it opened the list.
	 * We save this in 'open' so that when we process the associated
	 * bindings, we know if we need to open the list on the first binding
	 * or not -- we don't want 'dyn Trait<>' if there are no bindings,
	 * just 'dyn Trait'.
	 */
	st->rs_args_stay_open = B_TRUE;
	st->rs_args_is_open = B_FALSE;

	if (!rustv0_parse_path(st, sv, B_FALSE)) {
		st->rs_args_stay_open = stay_save;
		st->rs_args_is_open = open_save;
		return (B_FALSE);
	}

	open = st->rs_args_is_open;

	st->rs_args_stay_open = stay_save;
	st->rs_args_is_open = open_save;

	while (rustv0_parse_dyn_trait_assoc_binding(st, sv, open)) {
		open = B_TRUE;
	}

	if (HAS_ERROR(st))
		return (B_FALSE);

	if (open && !rust_appendc(st, '>'))
		return (B_FALSE);

	return (!HAS_ERROR(st));
}

static boolean_t
rustv0_parse_dynbounds(rust_state_t *restrict st, strview_t *restrict sv)
{
	uint64_t save_lt = st->rs_lt_depth;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	/*
	 * This is another case where Rust RFC2603 seems to disagree with
	 * the implementation. The RFC implies this is mandatory, while
	 * the implementations treat it as optional.
	 */
	if (!OPTIONAL(st, rustv0_parse_binder(st, sv)))
		return (B_FALSE);

	if (!rustv0_parse_opt_list(st, sv, rustv0_parse_dyn_trait, " + ",
	    B_FALSE, NULL))
		return (B_FALSE);

	st->rs_lt_depth = save_lt;

	return (B_TRUE);
}

static boolean_t
rustv0_parse_generic_arg(rust_state_t *restrict st, strview_t *restrict sv,
    boolean_t dummy __unused)
{
	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_consume_if_c(sv, 'K'))
		return (rustv0_parse_const(st, sv, B_FALSE));

	if (rustv0_parse_lifetime(st, sv))
		return (B_TRUE);

	return (rustv0_parse_type(st, sv, B_FALSE));
}

/*
 * Parse a hex value into *valp. Note that rust only uses lower case
 * hex values.
 */
static boolean_t
rustv0_parse_hex_num(rust_state_t *restrict st, strview_t *restrict sv,
    uint64_t *restrict valp)
{
	uint64_t val = 0;
	size_t ndigits = 0;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	/*
	 * Unfortunately, Rust RFC 2603 also doesn't not explicty define
	 * {hex-digits}. We follow what decimal digits does, and treat a
	 * leading 0 as a terminator.
	 */
	while (sv_remaining(sv) > 0) {
		char c = sv_peek(sv, 0);

		if (ISDIGIT(c)) {
			val *= 16;
			val += c - '0';
		} else if (c >= 'a' && c <= 'f') {
			val *= 16;
			val += c - 'a' + 10;
		} else {
			break;
		}

		sv_consume_n(sv, 1);

		if (++ndigits == 1 && val == 0)
			break;
	}

	if (ndigits > 0)
		*valp = val;

	return ((ndigits > 0) ? B_TRUE : B_FALSE);
}

/*
 * Parse a base62 number into *valp.  The number is explicitly terminated
 * by a '_'.  The values are also offset by 0 -- that is '_' == 0,
 * '0_' == 1, ...
 */
static boolean_t
rustv0_parse_base62(rust_state_t *restrict st, strview_t *restrict sv,
    uint64_t *restrict valp)
{
	uint64_t val = 0;
	char c;

	if (HAS_ERROR(st))
		return (B_FALSE);

	DEMDEBUG("%s: str='%.*s'", __func__, SV_PRINT(sv));

	if (sv_remaining(sv) == 0)
		return (B_FALSE);

	/* A terminating '_' without any digits is 0 */
	if (sv_consume_if_c(sv, '_')) {
		*valp = 0;
		return (B_TRUE);
	}

	/* Need at least one valid digit if > 0 */
	if (!ISALNUM(sv_peek(sv, 0)))
		return (B_FALSE);

	while (sv_remaining(sv) > 0) {
		c = sv_consume_c(sv);

		if (c == '_') {
			/*
			 * Because a lone '_' was already handled earlier,
			 * we know we've had at least one other digit and
			 * can increment the value and return.
			 */
			*valp = val + 1;
			return (B_TRUE);
		} else if (ISDIGIT(c)) {
			val *= 62;
			val += c - '0';
		} else if (ISLOWER(c)) {
			val *= 62;
			val += c - 'a' + 10;
		} else if (ISUPPER(c)) {
			val *= 62;
			val += c - 'A' + 36;
		} else {
			return (B_FALSE);
		}
	}

	/* We reached the end of the string without a terminating _ */
	return (B_FALSE);
}

static const_type_class_t
rustv0_classify_const_type(char type)
{
	switch (type) {
	case 'h': case 't': case 'm': case 'y': case 'o': case 'j':
		return (CTC_UNSIGNED);
	case 'a': case 'i': case 'l': case 'n': case 's': case 'x':
		return (CTC_SIGNED);
	case 'b':
		return (CTC_BOOL);
	case 'c':
		return (CTC_CHAR);
	default:
		return (CTC_INVALID);
	}
}

/*
 * Make sure the name is a plausible mangled rust symbol.
 * Non-ASCII are never allowed.  Rust itself uses [_0-9A-Za-z], however
 * some things will add a suffix starting with a '.' (e.g. LLVM thin LTO).
 * As such we proceed in two phases. We first only allow [_0-9A-Z-az] until
 * we encounter a '.'. At that point, any ASCII character is allowed.
 */
static boolean_t
rustv0_valid_sym(const strview_t *sv)
{
	size_t i;
	boolean_t check_rust = B_TRUE;

	for (i = 0; i < sv->sv_rem; i++) {
		char c = sv->sv_first[i];

		if (ISALNUM(c) || c == '_')
			continue;

		if (c == '.') {
			check_rust = B_FALSE;
			continue;
		}

		if (check_rust || (c & 0x80) != 0) {
			DEMDEBUG("%s: ERROR found invalid character '%c' "
			    "in '%.*s' at index %zu",
			    __func__, c, SV_PRINT(sv), i);
			return (B_FALSE);
		}
	}
	return (B_TRUE);
}