1 //===--- RustDemangle.cpp ---------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines a demangler for Rust v0 mangled symbols as specified in 10 // https://rust-lang.github.io/rfcs/2603-rust-symbol-name-mangling-v0.html 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Demangle/RustDemangle.h" 15 #include "llvm/Demangle/Demangle.h" 16 17 #include <algorithm> 18 #include <cassert> 19 #include <cstring> 20 #include <limits> 21 22 using namespace llvm; 23 using namespace rust_demangle; 24 25 char *llvm::rustDemangle(const char *MangledName, char *Buf, size_t *N, 26 int *Status) { 27 if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) { 28 if (Status != nullptr) 29 *Status = demangle_invalid_args; 30 return nullptr; 31 } 32 33 // Return early if mangled name doesn't look like a Rust symbol. 34 StringView Mangled(MangledName); 35 if (!Mangled.startsWith("_R")) { 36 if (Status != nullptr) 37 *Status = demangle_invalid_mangled_name; 38 return nullptr; 39 } 40 41 Demangler D; 42 if (!initializeOutputStream(nullptr, nullptr, D.Output, 1024)) { 43 if (Status != nullptr) 44 *Status = demangle_memory_alloc_failure; 45 return nullptr; 46 } 47 48 if (!D.demangle(Mangled)) { 49 if (Status != nullptr) 50 *Status = demangle_invalid_mangled_name; 51 std::free(D.Output.getBuffer()); 52 return nullptr; 53 } 54 55 D.Output += '\0'; 56 char *Demangled = D.Output.getBuffer(); 57 size_t DemangledLen = D.Output.getCurrentPosition(); 58 59 if (Buf != nullptr) { 60 if (DemangledLen <= *N) { 61 std::memcpy(Buf, Demangled, DemangledLen); 62 std::free(Demangled); 63 Demangled = Buf; 64 } else { 65 std::free(Buf); 66 } 67 } 68 69 if (N != nullptr) 70 *N = DemangledLen; 71 72 if (Status != nullptr) 73 *Status = demangle_success; 74 75 return Demangled; 76 } 77 78 Demangler::Demangler(size_t MaxRecursionLevel) 79 : MaxRecursionLevel(MaxRecursionLevel) {} 80 81 static inline bool isDigit(const char C) { return '0' <= C && C <= '9'; } 82 83 static inline bool isHexDigit(const char C) { 84 return ('0' <= C && C <= '9') || ('a' <= C && C <= 'f'); 85 } 86 87 static inline bool isLower(const char C) { return 'a' <= C && C <= 'z'; } 88 89 static inline bool isUpper(const char C) { return 'A' <= C && C <= 'Z'; } 90 91 /// Returns true if C is a valid mangled character: <0-9a-zA-Z_>. 92 static inline bool isValid(const char C) { 93 return isDigit(C) || isLower(C) || isUpper(C) || C == '_'; 94 } 95 96 // Demangles Rust v0 mangled symbol. Returns true when successful, and false 97 // otherwise. The demangled symbol is stored in Output field. It is 98 // responsibility of the caller to free the memory behind the output stream. 99 // 100 // <symbol-name> = "_R" <path> [<instantiating-crate>] 101 bool Demangler::demangle(StringView Mangled) { 102 Position = 0; 103 Error = false; 104 Print = true; 105 RecursionLevel = 0; 106 107 if (!Mangled.consumeFront("_R")) { 108 Error = true; 109 return false; 110 } 111 Input = Mangled; 112 113 demanglePath(InType::No); 114 115 // FIXME parse optional <instantiating-crate>. 116 117 if (Position != Input.size()) 118 Error = true; 119 120 return !Error; 121 } 122 123 // Demangles a path. InType indicates whether a path is inside a type. 124 // 125 // <path> = "C" <identifier> // crate root 126 // | "M" <impl-path> <type> // <T> (inherent impl) 127 // | "X" <impl-path> <type> <path> // <T as Trait> (trait impl) 128 // | "Y" <type> <path> // <T as Trait> (trait definition) 129 // | "N" <ns> <path> <identifier> // ...::ident (nested path) 130 // | "I" <path> {<generic-arg>} "E" // ...<T, U> (generic args) 131 // | <backref> 132 // <identifier> = [<disambiguator>] <undisambiguated-identifier> 133 // <ns> = "C" // closure 134 // | "S" // shim 135 // | <A-Z> // other special namespaces 136 // | <a-z> // internal namespaces 137 void Demangler::demanglePath(InType InType) { 138 if (Error || RecursionLevel >= MaxRecursionLevel) { 139 Error = true; 140 return; 141 } 142 SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1); 143 144 switch (consume()) { 145 case 'C': { 146 parseOptionalBase62Number('s'); 147 Identifier Ident = parseIdentifier(); 148 print(Ident.Name); 149 break; 150 } 151 case 'M': { 152 demangleImplPath(InType); 153 print("<"); 154 demangleType(); 155 print(">"); 156 break; 157 } 158 case 'X': { 159 demangleImplPath(InType); 160 print("<"); 161 demangleType(); 162 print(" as "); 163 demanglePath(InType::Yes); 164 print(">"); 165 break; 166 } 167 case 'Y': { 168 print("<"); 169 demangleType(); 170 print(" as "); 171 demanglePath(InType::Yes); 172 print(">"); 173 break; 174 } 175 case 'N': { 176 char NS = consume(); 177 if (!isLower(NS) && !isUpper(NS)) { 178 Error = true; 179 break; 180 } 181 demanglePath(InType); 182 183 uint64_t Disambiguator = parseOptionalBase62Number('s'); 184 Identifier Ident = parseIdentifier(); 185 186 if (isUpper(NS)) { 187 // Special namespaces 188 print("::{"); 189 if (NS == 'C') 190 print("closure"); 191 else if (NS == 'S') 192 print("shim"); 193 else 194 print(NS); 195 if (!Ident.empty()) { 196 print(":"); 197 print(Ident.Name); 198 } 199 print('#'); 200 printDecimalNumber(Disambiguator); 201 print('}'); 202 } else { 203 // Implementation internal namespaces. 204 if (!Ident.empty()) { 205 print("::"); 206 print(Ident.Name); 207 } 208 } 209 break; 210 } 211 case 'I': { 212 demanglePath(InType); 213 // Omit "::" when in a type, where it is optional. 214 if (InType == InType::No) 215 print("::"); 216 print("<"); 217 for (size_t I = 0; !Error && !consumeIf('E'); ++I) { 218 if (I > 0) 219 print(", "); 220 demangleGenericArg(); 221 } 222 print(">"); 223 break; 224 } 225 default: 226 // FIXME parse remaining productions. 227 Error = true; 228 break; 229 } 230 } 231 232 // <impl-path> = [<disambiguator>] <path> 233 // <disambiguator> = "s" <base-62-number> 234 void Demangler::demangleImplPath(InType InType) { 235 SwapAndRestore<bool> SavePrint(Print, false); 236 parseOptionalBase62Number('s'); 237 demanglePath(InType); 238 } 239 240 // <generic-arg> = <lifetime> 241 // | <type> 242 // | "K" <const> 243 // <lifetime> = "L" <base-62-number> 244 void Demangler::demangleGenericArg() { 245 if (consumeIf('K')) 246 demangleConst(); 247 else 248 demangleType(); 249 // FIXME demangle lifetimes. 250 } 251 252 // <basic-type> = "a" // i8 253 // | "b" // bool 254 // | "c" // char 255 // | "d" // f64 256 // | "e" // str 257 // | "f" // f32 258 // | "h" // u8 259 // | "i" // isize 260 // | "j" // usize 261 // | "l" // i32 262 // | "m" // u32 263 // | "n" // i128 264 // | "o" // u128 265 // | "s" // i16 266 // | "t" // u16 267 // | "u" // () 268 // | "v" // ... 269 // | "x" // i64 270 // | "y" // u64 271 // | "z" // ! 272 // | "p" // placeholder (e.g. for generic params), shown as _ 273 static bool parseBasicType(char C, BasicType &Type) { 274 switch (C) { 275 case 'a': 276 Type = BasicType::I8; 277 return true; 278 case 'b': 279 Type = BasicType::Bool; 280 return true; 281 case 'c': 282 Type = BasicType::Char; 283 return true; 284 case 'd': 285 Type = BasicType::F64; 286 return true; 287 case 'e': 288 Type = BasicType::Str; 289 return true; 290 case 'f': 291 Type = BasicType::F32; 292 return true; 293 case 'h': 294 Type = BasicType::U8; 295 return true; 296 case 'i': 297 Type = BasicType::ISize; 298 return true; 299 case 'j': 300 Type = BasicType::USize; 301 return true; 302 case 'l': 303 Type = BasicType::I32; 304 return true; 305 case 'm': 306 Type = BasicType::U32; 307 return true; 308 case 'n': 309 Type = BasicType::I128; 310 return true; 311 case 'o': 312 Type = BasicType::U128; 313 return true; 314 case 'p': 315 Type = BasicType::Placeholder; 316 return true; 317 case 's': 318 Type = BasicType::I16; 319 return true; 320 case 't': 321 Type = BasicType::U16; 322 return true; 323 case 'u': 324 Type = BasicType::Unit; 325 return true; 326 case 'v': 327 Type = BasicType::Variadic; 328 return true; 329 case 'x': 330 Type = BasicType::I64; 331 return true; 332 case 'y': 333 Type = BasicType::U64; 334 return true; 335 case 'z': 336 Type = BasicType::Never; 337 return true; 338 default: 339 return false; 340 } 341 } 342 343 void Demangler::printBasicType(BasicType Type) { 344 switch (Type) { 345 case BasicType::Bool: 346 print("bool"); 347 break; 348 case BasicType::Char: 349 print("char"); 350 break; 351 case BasicType::I8: 352 print("i8"); 353 break; 354 case BasicType::I16: 355 print("i16"); 356 break; 357 case BasicType::I32: 358 print("i32"); 359 break; 360 case BasicType::I64: 361 print("i64"); 362 break; 363 case BasicType::I128: 364 print("i128"); 365 break; 366 case BasicType::ISize: 367 print("isize"); 368 break; 369 case BasicType::U8: 370 print("u8"); 371 break; 372 case BasicType::U16: 373 print("u16"); 374 break; 375 case BasicType::U32: 376 print("u32"); 377 break; 378 case BasicType::U64: 379 print("u64"); 380 break; 381 case BasicType::U128: 382 print("u128"); 383 break; 384 case BasicType::USize: 385 print("usize"); 386 break; 387 case BasicType::F32: 388 print("f32"); 389 break; 390 case BasicType::F64: 391 print("f64"); 392 break; 393 case BasicType::Str: 394 print("str"); 395 break; 396 case BasicType::Placeholder: 397 print("_"); 398 break; 399 case BasicType::Unit: 400 print("()"); 401 break; 402 case BasicType::Variadic: 403 print("..."); 404 break; 405 case BasicType::Never: 406 print("!"); 407 break; 408 } 409 } 410 411 // <type> = | <basic-type> 412 // | <path> // named type 413 // | "A" <type> <const> // [T; N] 414 // | "S" <type> // [T] 415 // | "T" {<type>} "E" // (T1, T2, T3, ...) 416 // | "R" [<lifetime>] <type> // &T 417 // | "Q" [<lifetime>] <type> // &mut T 418 // | "P" <type> // *const T 419 // | "O" <type> // *mut T 420 // | "F" <fn-sig> // fn(...) -> ... 421 // | "D" <dyn-bounds> <lifetime> // dyn Trait<Assoc = X> + Send + 'a 422 // | <backref> // backref 423 void Demangler::demangleType() { 424 char C = look(); 425 BasicType Type; 426 if (parseBasicType(C, Type)) { 427 consume(); 428 return printBasicType(Type); 429 } 430 431 demanglePath(InType::Yes); 432 } 433 434 // <const> = <basic-type> <const-data> 435 // | "p" // placeholder 436 // | <backref> 437 void Demangler::demangleConst() { 438 BasicType Type; 439 if (parseBasicType(consume(), Type)) { 440 switch (Type) { 441 case BasicType::I8: 442 case BasicType::I16: 443 case BasicType::I32: 444 case BasicType::I64: 445 case BasicType::I128: 446 case BasicType::ISize: 447 case BasicType::U8: 448 case BasicType::U16: 449 case BasicType::U32: 450 case BasicType::U64: 451 case BasicType::U128: 452 case BasicType::USize: 453 demangleConstInt(); 454 break; 455 case BasicType::Bool: 456 demangleConstBool(); 457 break; 458 case BasicType::Char: 459 demangleConstChar(); 460 break; 461 case BasicType::Placeholder: 462 print('_'); 463 break; 464 default: 465 // FIXME demangle backreferences. 466 Error = true; 467 break; 468 } 469 } else { 470 Error = true; 471 } 472 } 473 474 // <const-data> = ["n"] <hex-number> 475 void Demangler::demangleConstInt() { 476 if (consumeIf('n')) 477 print('-'); 478 479 StringView HexDigits; 480 uint64_t Value = parseHexNumber(HexDigits); 481 if (HexDigits.size() <= 16) { 482 printDecimalNumber(Value); 483 } else { 484 print("0x"); 485 print(HexDigits); 486 } 487 } 488 489 // <const-data> = "0_" // false 490 // | "1_" // true 491 void Demangler::demangleConstBool() { 492 StringView HexDigits; 493 parseHexNumber(HexDigits); 494 if (HexDigits == "0") 495 print("false"); 496 else if (HexDigits == "1") 497 print("true"); 498 else 499 Error = true; 500 } 501 502 /// Returns true if CodePoint represents a printable ASCII character. 503 static bool isAsciiPrintable(uint64_t CodePoint) { 504 return 0x20 <= CodePoint && CodePoint <= 0x7e; 505 } 506 507 // <const-data> = <hex-number> 508 void Demangler::demangleConstChar() { 509 StringView HexDigits; 510 uint64_t CodePoint = parseHexNumber(HexDigits); 511 if (Error || HexDigits.size() > 6) { 512 Error = true; 513 return; 514 } 515 516 print("'"); 517 switch (CodePoint) { 518 case '\t': 519 print(R"(\t)"); 520 break; 521 case '\r': 522 print(R"(\r)"); 523 break; 524 case '\n': 525 print(R"(\n)"); 526 break; 527 case '\\': 528 print(R"(\\)"); 529 break; 530 case '"': 531 print(R"(")"); 532 break; 533 case '\'': 534 print(R"(\')"); 535 break; 536 default: 537 if (isAsciiPrintable(CodePoint)) { 538 char C = CodePoint; 539 print(C); 540 } else { 541 print(R"(\u{)"); 542 print(HexDigits); 543 print('}'); 544 } 545 break; 546 } 547 print('\''); 548 } 549 550 // <undisambiguated-identifier> = ["u"] <decimal-number> ["_"] <bytes> 551 Identifier Demangler::parseIdentifier() { 552 bool Punycode = consumeIf('u'); 553 uint64_t Bytes = parseDecimalNumber(); 554 555 // Underscore resolves the ambiguity when identifier starts with a decimal 556 // digit or another underscore. 557 consumeIf('_'); 558 559 if (Error || Bytes > Input.size() - Position) { 560 Error = true; 561 return {}; 562 } 563 StringView S = Input.substr(Position, Bytes); 564 Position += Bytes; 565 566 if (!std::all_of(S.begin(), S.end(), isValid)) { 567 Error = true; 568 return {}; 569 } 570 571 return {S, Punycode}; 572 } 573 574 // Parses optional base 62 number. The presence of a number is determined using 575 // Tag. Returns 0 when tag is absent and parsed value + 1 otherwise. 576 uint64_t Demangler::parseOptionalBase62Number(char Tag) { 577 if (!consumeIf(Tag)) 578 return 0; 579 580 uint64_t N = parseBase62Number(); 581 if (Error || !addAssign(N, 1)) 582 return 0; 583 584 return N; 585 } 586 587 // Parses base 62 number with <0-9a-zA-Z> as digits. Number is terminated by 588 // "_". All values are offset by 1, so that "_" encodes 0, "0_" encodes 1, 589 // "1_" encodes 2, etc. 590 // 591 // <base-62-number> = {<0-9a-zA-Z>} "_" 592 uint64_t Demangler::parseBase62Number() { 593 if (consumeIf('_')) 594 return 0; 595 596 uint64_t Value = 0; 597 598 while (true) { 599 uint64_t Digit; 600 char C = consume(); 601 602 if (C == '_') { 603 break; 604 } else if (isDigit(C)) { 605 Digit = C - '0'; 606 } else if (isLower(C)) { 607 Digit = 10 + (C - 'a'); 608 } else if (isUpper(C)) { 609 Digit = 10 + 26 + (C - 'A'); 610 } else { 611 Error = true; 612 return 0; 613 } 614 615 if (!mulAssign(Value, 62)) 616 return 0; 617 618 if (!addAssign(Value, Digit)) 619 return 0; 620 } 621 622 if (!addAssign(Value, 1)) 623 return 0; 624 625 return Value; 626 } 627 628 // Parses a decimal number that had been encoded without any leading zeros. 629 // 630 // <decimal-number> = "0" 631 // | <1-9> {<0-9>} 632 uint64_t Demangler::parseDecimalNumber() { 633 char C = look(); 634 if (!isDigit(C)) { 635 Error = true; 636 return 0; 637 } 638 639 if (C == '0') { 640 consume(); 641 return 0; 642 } 643 644 uint64_t Value = 0; 645 646 while (isDigit(look())) { 647 if (!mulAssign(Value, 10)) { 648 Error = true; 649 return 0; 650 } 651 652 uint64_t D = consume() - '0'; 653 if (!addAssign(Value, D)) 654 return 0; 655 } 656 657 return Value; 658 } 659 660 // Parses a hexadecimal number with <0-9a-f> as a digits. Returns the parsed 661 // value and stores hex digits in HexDigits. The return value is unspecified if 662 // HexDigits.size() > 16. 663 // 664 // <hex-number> = "0_" 665 // | <1-9a-f> {<0-9a-f>} "_" 666 uint64_t Demangler::parseHexNumber(StringView &HexDigits) { 667 size_t Start = Position; 668 uint64_t Value = 0; 669 670 if (!isHexDigit(look())) 671 Error = true; 672 673 if (consumeIf('0')) { 674 if (!consumeIf('_')) 675 Error = true; 676 } else { 677 while (!Error && !consumeIf('_')) { 678 char C = consume(); 679 Value *= 16; 680 if (isDigit(C)) 681 Value += C - '0'; 682 else if ('a' <= C && C <= 'f') 683 Value += 10 + (C - 'a'); 684 else 685 Error = true; 686 } 687 } 688 689 if (Error) { 690 HexDigits = StringView(); 691 return 0; 692 } 693 694 size_t End = Position - 1; 695 assert(Start < End); 696 HexDigits = Input.substr(Start, End - Start); 697 return Value; 698 } 699