<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/120559>120559</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [lld][MachO] llvm::upper_bound called on not correctly sorted input
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          karka228
      </td>
    </tr>
</table>

<pre>
    When building llvm-project with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON with a recent libstdc++ (e.g. from gcc 13.3.0) the testcases:
```
  lld :: MachO/local-alias-to-weak.s
  lld :: MachO/symtab.s
  lld :: MachO/weak-definition-gc.s
```
fail with the message:

```
.../include/c++/13.3.0/bits/stl_algo.h:2100:
In function:
 _ForwardIterator std::upper_bound(_ForwardIterator, _ForwardIterator, 
 const _Tp &, _Compare) [_ForwardIterator = lld::macho::Defined **, _Tp = 
 unsigned long, _Compare = (lambda at 
 ../../lld/MachO/SymbolTable.cpp:77:15)]

Error: elements in iterator range [first, last) are not partitioned by the 
predicate __comp and value __val.

Objects involved in the operation:
    iterator "first" @ 0x7ffc2bfd9af8 {
    }
    iterator "last" @ 0x7ffc2bfd9af0 {
 }
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /repo/llvm-project/llvm/build/bin/ld64.lld -arch x86_64 -platform_version macos 11.0 11.0 -syslibroot /repo/llvm-project/lld/test/MachO/Inputs/MacOSX.sdk -lSystem -fatal_warnings -lSystem -dylib /repo/llvm-project/llvm/build/tools/lld/test/MachO/Output/local-alias-to-weak.s.tmp/no-subsections.o /repo/llvm-project/llvm/build/tools/lld/test/MachO/Output/local-alias-to-weak.s.tmp/local-then-weak.o -o /repo/llvm-project/llvm/build/tools/lld/test/MachO/Output/local-alias-to-weak.s.tmp/nosub-sub
 #0 0x000055af1d9c8706 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4d89706)
 #1 0x000055af1d9c60ce llvm::sys::RunSignalHandlers() (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4d870ce)
 #2 0x000055af1d9c8f79 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007efebf8c7cf0 __restore_rt (/lib64/libpthread.so.0+0x12cf0)
 #4 0x00007efebe980acf raise (/lib64/libc.so.6+0x4eacf)
 #5 0x00007efebe953ea5 abort (/lib64/libc.so.6+0x21ea5)
 #6 0x000055af223cfa43 (/repo/llvm-project/llvm/build/bin/ld64.lld+0x9790a43)
 #7 0x000055af1df2aab1 transplantSymbolsAtOffset(lld::macho::InputSection*, lld::macho::InputSection*, lld::macho::Defined*, unsigned long, unsigned long) SymbolTable.cpp:0:0
 #8 0x000055af1df29519 lld::macho::SymbolTable::addDefined(llvm::StringRef, lld::macho::InputFile*, lld::macho::InputSection*, unsigned long, unsigned long, bool, bool, bool, bool, bool) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x52ea519)
 #9 0x000055af1de8a33e void lld::macho::ObjFile::parseSymbols<lld::macho::LP64>(llvm::ArrayRef<lld::macho::LP64::section>, llvm::ArrayRef<lld::macho::LP64::nlist>, char const*, bool) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x524b33e)
#10 0x000055af1de78214 void lld::macho::ObjFile::parse<lld::macho::LP64>() (/repo/llvm-project/llvm/build/bin/ld64.lld+0x5239214)
#11 0x000055af1de77cc8 lld::macho::ObjFile::ObjFile(llvm::MemoryBufferRef, unsigned int, llvm::StringRef, bool, bool, bool, bool) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x5238cc8)
#12 0x000055af1de492dc lld::macho::ObjFile* lld::make<lld::macho::ObjFile, llvm::MemoryBufferRef&, unsigned int, char const (&) [1], bool&>(llvm::MemoryBufferRef&, unsigned int&&, char const (&) [1], bool&) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x520a2dc)
#13 0x000055af1de43090 addFile(llvm::StringRef, LoadType, bool, bool, bool, bool) Driver.cpp:0:0
#14 0x000055af1de40cdd lld::macho::link(llvm::ArrayRef<char const*>, llvm::raw_ostream&, llvm::raw_ostream&, bool, bool) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x5201cdd)
#15 0x000055af1d9cafbe lld::unsafeLldMain(llvm::ArrayRef<char const*>, llvm::raw_ostream&, llvm::raw_ostream&, llvm::ArrayRef<lld::DriverDef>, bool) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4d8bfbe)
#16 0x000055af1d8f6f1b lld_main(int, char**, llvm::ToolContext const&) (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4cb7f1b)
#17 0x000055af1d8f76a6 main (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4cb86a6)
#18 0x00007efebe96cd85 __libc_start_main (/lib64/libc.so.6+0x3ad85)
#19 0x000055af1d8f6cae _start (/repo/llvm-project/llvm/build/bin/ld64.lld+0x4cb7cae)
Aborted (core dumped)
```

The reason for this is that the requirement for calling llvm::upper_bound (std::upper_bound) in function transplantSymbolsAtOffset() in file lld/MachO/SymbolTable.cpp is not fulfilled. The input to std::upper_bound needs sorted vector because it implements binary search to find the value.

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8WFtv27gS_jXMC2FBou4PeXDiGFuctCk2wZ59M0YkZXNDkTokldb__oCUXF-TdtvsAkkUU8OZb765kB6wVqwV59cov0H54goGt9Hm-hnMMxBSXTWaba__u-EKN4OQTKg1lvKlm_VG_8Wpw1-E2-DZ4v7-j4-ru0_zm_u71d2fn-8-PX744251-9vd7X8eUbp4-DQKAjaccuWwFI11jCJyg8gNRqTi0TrCrdEdXlOKkzRKoxiRGrsNx45bR8Fyi9I5iueoiKefeI6xlAz79XSOPwLdPCCylJqCnIEUYGdOz75weI7sa8J22zloXn_vd88Yb4USTmg1W9MgewiiBSFH_zzajlsLaz5hPZaMogiRpVBUDowjspwIQGS583jZCGc9LCdXINc62qB0TpI4HvV9ULgdFPVIxgW8WmrzBQz74LgBpw22jo0uDH3PzarRg2KIVKdyiNye7fVrXifVyjq8euoxIkUQvNVdD4b7iKD85swmSheeu9FuB3Sjx38XnjfOMCLz8HM7Kk0XwcygQu4xLLVaH5oZJUgloWsYYHBBPHAX_nhTZLmL0OO2a7R8gkbyiPY9SudlidJ5kiNSo3wxRuHOGG18XLnkHVfOYqGw2OE3oNbce9YKY52HIsE_a-zRKO1wD8aFBOAMN9sQaBTPe8OZoOA4Xq2o7noMiuEXkINfeAEZjcYfGl8r3uSLli-cedteg-69_X0sMd5DQoRMYAhGWYzjr2XbUtK0rIa2wqi8mXagcnFh74j_wtZ4t3Xc9_n-bv54h-3QdMJhwM2wxob32jjsNN4414eqI0tElmvhNkMTUd2FGLzsHrtm4FPb2oH7_A1MTIkefKUG7AY3QJ-dAco9M48O6DNmQ9eP_scRiuvPRq8NdBjMegiB8kFDZOlBndubUITeFIpH-UVWZJEv5RkYusFfq2JVZHjWS3CtNt3qhRsrtMIdUG1xkkTx-Gdmt1aKxmjt3rLoDfmWdJCCH1Q_hLL9CPTh8c_Ismc8k49b63iHZy04kKsvYJRQa3vwgm2laH7YOae1tK8heBhcP7jXml_kuh6RpdIzOzSWh_5hI_0vmh7fuQ1X47rGs3_TvNJ2aLzzIfNJ6osijuM4z6FNWE2rMi7CwTb2Lbu14z-fjVAu5OmTz1rfk74JGfiy0tYZDt3UJoUKPQOR6ucSFpGb-GvGqrqMC9-8RqzJCdYipvwS1t8H9SjWCuRvoJjkxgYc7wCnjL3nOzjklLq2rPGRYUSqiYlx2U5tOQ6_o5Z00lLyljdtRUvaxni1Mtw6bfjKuAm2FE2Rjc_ebQwHFlntD8qb-GtCaBvvgWWHKnldxUBbbEBYfq6Lei3F6CAH2u615Mda8pRDjqHRlxAdaCEJh3yvpTggiZCUtpClvxiIuqxjyNK9jfIoEC0BaBLsDCjbS1BuPBbt3D20reUupO75CR061-PYEaYj-hfEpvN-kjg7308Wanx-dB_mSHXiYJ0n9UWzB2rGBWDsG5SDin10Rqj177x9082lkPzvUfE9R29xo7X8_vNXazUnHPKk3qdIfcQgryBNOX7Rgl307KH5K_gePvRgLJ9yCKW3l-TvPxcZSu-OKJ4bA1vP8FtbQtuaGPT7b_FPKFBSWDdtpxsw4611ish78Zk1aTr1Pt-Jj48NXlYkyf4On98l8j0wpzVJsj3m5ARzSWn1fbi7D4ex_cg7bbY3Q9tyMxXRt0QPDf8wjke19k-nfVpRWu1dPj6ieFYTRt90mcwPXz-_Fqdv4oeOnrFSXCJmn6Gjs8X0VSrx31C-MVGcltOPKC-m1R818Q58x0D8l_cd3-kJ32lcxxgYO8ugo6S418Cetj3_kQRZGPHCzckZ4U1nJ6Zjyi4XoxTq-bVOddw-TjvS-T3vrXfvndpxQhnbU52f3L6gbfje30FZaPm9ZB_B6_rnvX27b49RW_jFu_fjJGNV0zYHXbk44qRqizZpPCerbmThoAT3g4g98iet5a1Wjn91O1reoUgy2pRt0uxRlicoywIK7BH-uqGqgGJvqDq-wRaUVTlerfx9dWUdGLc6sHr5NpsCq_K9xvqUYAocj7regSUKUyzn_pYdpkUV1YaHyQDf5f7BFA3F86cNx4aD1Qq32mC3ERYLi90GXJg2GP6_QZgw6QkCFKTczS7PpmPe4OWpWY3FfuD25t16JyvkWI6vjqc8TKUdbgfZCik5i7B3RvhbJXb64vgOK86ZxXak54VTpw1uOIXBciwcFl2_m2o1QoHZYsvD6MNp3ArFAiVhLBWheH7FrlNWpzVc8eukTLMirpIiv9pcF4TGRQYt0JrlLS-TKsvLjLWUF2nLc3IlrklMsoQkdZKkRZxHGSloRsqybUlVMFahLOYdCBl5niNt1ldhIHSdkDjP6ysJDZd2N2o21yFdmmFtURb725zd73PCyTCU9mTmC5TfjHzmi1di6CPMGdYqsEu1MZw6ud2RFvi9Goy8_vmZ1uTFyzX5fwAAAP__sqAnAw">