search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
28.64k stars 11.84k forks source link

clang-tidy reports use-after-move in `std::ranges::sort` and `std::sort` #78132

Open vogelsgesang opened 9 months ago

vogelsgesang commented 9 months ago

When running the clang-tidy pass clang-analyzer-cplusplus.Move against the following program, it reports a move-after-free within std::ranges::sort.

clang-tidy version 17.0.6 libc++ version 17.0.6

Program:

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

static bool lessSize(const string& a, const string& b) {
   return a.length() < b.length();
}

int main(int, char**) {
   vector<string> files;
   ranges::sort(files, lessSize);
}

clang-tidy output:

example.cpp:8:24: warning: Method called on moved-from object of type 'std::basic_string' [clang-analyzer-cplusplus.Move]
    8 |    return a.length() < b.length();
      |                        ^
example.cpp:13:4: note: Calling '__fn::operator()'
   13 |    ranges::sort(files, lessSize);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/ranges_sort.h:64:12: note: Calling '__fn::__sort_fn_impl'
   64 |     return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/ranges_sort.h:48:5: note: Calling '__sort_impl<std::_RangeAlgPolicy, std::__wrap_iter<std::string *>, bool (*)(const std::string &, const std::string &)>'
   48 |     std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:942:7: note: Assuming the condition is false
  942 |   if (__libcpp_is_constant_evaluated()) {
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:942:3: note: Taking false branch
  942 |   if (__libcpp_is_constant_evaluated()) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:946:5: note: Calling '__sort_dispatch<std::_RangeAlgPolicy, std::string *, bool (*)(const std::string &, const std::string &)>'
  946 |     std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:878:3: note: Calling '__introsort<std::_RangeAlgPolicy, bool (*&)(const std::string &, const std::string &), std::string *, false>'
  878 |   std::__introsort<_AlgPolicy,
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
  879 |                    _Comp&,
      |                    ~~~~~~~
  880 |                    _RandomAccessIterator,
      |                    ~~~~~~~~~~~~~~~~~~~~~~
  881 |                    __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  882 |       __first, __last, __comp, __depth_limit);
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:731:3: note: Loop condition is true.  Entering loop body
  731 |   while (true) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:733:5: note: 'Default' branch taken. Execution continues on line 755
  733 |     switch (__len) {
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:755:9: note: Assuming '__len' is >= '__limit'
  755 |     if (__len < __limit) {
      |         ^~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:755:5: note: Taking false branch
  755 |     if (__len < __limit) {
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:763:9: note: Assuming '__depth' is not equal to 0
  763 |     if (__depth == 0) {
      |         ^~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:763:5: note: Taking false branch
  763 |     if (__depth == 0) {
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:773:11: note: Assuming '__len' is <= '__ninther_threshold'
  773 |       if (__len > __ninther_threshold) {
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:773:7: note: Taking false branch
  773 |       if (__len > __ninther_threshold) {
      |       ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:794:10: note: '__leftmost' is true
  794 |     if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
      |          ^~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:794:21: note: Left side of '&&' is false
  794 |     if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
      |                     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:801:9: note: '?' condition is false
  801 |         _UseBitSetPartition
      |         ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:803:15: note: Calling '__partition_with_equals_on_right<std::_RangeAlgPolicy, std::string *, bool (*&)(const std::string &, const std::string &)>'
  803 |             : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp);
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:594:3: note: '?' condition is true
  594 |   _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), "");
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED'
  314 | #    define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message)             _LIBCPP_ASSERT(expression, message)
      |                                                                           ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT'
   21 |   (__builtin_expect(static_cast<bool>(expression), 1)                                                                  \
      |    ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:597:14: note: Object of type 'std::basic_string' is left in a valid but unspecified state after move
  597 |   value_type __pivot(_Ops::__iter_move(__first));
      |              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:603:5: note: Assuming the condition is true
  603 |     _LIBCPP_ASSERT_UNCATEGORIZED(
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED'
  314 | #    define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message)             _LIBCPP_ASSERT(expression, message)
      |                                                                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT'
   21 |   (__builtin_expect(static_cast<bool>(expression), 1)                                                                  \
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:603:5: note: '?' condition is true
  603 |     _LIBCPP_ASSERT_UNCATEGORIZED(
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED'
  314 | #    define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message)             _LIBCPP_ASSERT(expression, message)
      |                                                                           ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT'
   21 |   (__builtin_expect(static_cast<bool>(expression), 1)                                                                  \
      |    ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:601:3: note: Loop condition is false.  Exiting loop
  601 |   do {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:609:3: note: Taking true branch
  609 |   if (__begin == __first - difference_type(1)) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:610:12: note: Assuming '__first' is >= '__last'
  610 |     while (__first < __last && !__comp(*--__last, __pivot))
      |            ^~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:610:29: note: Left side of '&&' is false
  610 |     while (__first < __last && !__comp(*--__last, __pivot))
      |                             ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:629:3: note: Loop condition is false. Execution continues on line 645
  629 |   while (__first < __last) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:646:7: note: '__begin' is equal to '__pivot_pos'
  646 |   if (__begin != __pivot_pos) {
      |       ^~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:646:3: note: Taking false branch
  646 |   if (__begin != __pivot_pos) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:803:15: note: Returning from '__partition_with_equals_on_right<std::_RangeAlgPolicy, std::string *, bool (*&)(const std::string &, const std::string &)>'
  803 |             : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp);
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:807:9: note: Assuming field 'second' is true
  807 |     if (__ret.second) {
      |         ^~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:807:5: note: Taking true branch
  807 |     if (__ret.second) {
      |     ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:808:19: note: Calling '__insertion_sort_incomplete<std::_RangeAlgPolicy, bool (*&)(const std::string &, const std::string &), std::string *>'
  808 |       bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp);
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:314:3: note: Control jumps to 'case 2:'  at line 318
  314 |   switch (__last - __first) {
      |   ^
/Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:319:9: note: Calling 'lessSize'
  319 |     if (__comp(*--__last, *__first))
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~
example.cpp:8:24: note: Method called on moved-from object of type 'std::basic_string'
    8 |    return a.length() < b.length();
      |                        ^~~~~~~~~~
llvmbot commented 9 months ago

@llvm/issue-subscribers-clang-static-analyzer

Author: Adrian Vogelsgesang (vogelsgesang)

When running the clang-tidy pass `clang-analyzer-cplusplus.Move` against the following program, it reports a move-after-free within `std::ranges::sort`. clang-tidy version 17.0.6 libc++ version 17.0.6 Program: ```cplusplus #include <algorithm> #include <string> #include <vector> using namespace std; static bool lessSize(const string& a, const string& b) { return a.length() < b.length(); } int main(int, char**) { vector<string> files; ranges::sort(files, lessSize); } ``` clang-tidy output: ``` example.cpp:8:24: warning: Method called on moved-from object of type 'std::basic_string' [clang-analyzer-cplusplus.Move] 8 | return a.length() < b.length(); | ^ example.cpp:13:4: note: Calling '__fn::operator()' 13 | ranges::sort(files, lessSize); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/ranges_sort.h:64:12: note: Calling '__fn::__sort_fn_impl' 64 | return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/ranges_sort.h:48:5: note: Calling '__sort_impl<std::_RangeAlgPolicy, std::__wrap_iter<std::string *>, bool (*)(const std::string &, const std::string &)>' 48 | std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:942:7: note: Assuming the condition is false 942 | if (__libcpp_is_constant_evaluated()) { | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:942:3: note: Taking false branch 942 | if (__libcpp_is_constant_evaluated()) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:946:5: note: Calling '__sort_dispatch<std::_RangeAlgPolicy, std::string *, bool (*)(const std::string &, const std::string &)>' 946 | std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:878:3: note: Calling '__introsort<std::_RangeAlgPolicy, bool (*&)(const std::string &, const std::string &), std::string *, false>' 878 | std::__introsort<_AlgPolicy, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ 879 | _Comp&, | ~~~~~~~ 880 | _RandomAccessIterator, | ~~~~~~~~~~~~~~~~~~~~~~ 881 | __use_branchless_sort<_Comp, _RandomAccessIterator>::value>( | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 882 | __first, __last, __comp, __depth_limit); | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:731:3: note: Loop condition is true. Entering loop body 731 | while (true) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:733:5: note: 'Default' branch taken. Execution continues on line 755 733 | switch (__len) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:755:9: note: Assuming '__len' is >= '__limit' 755 | if (__len < __limit) { | ^~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:755:5: note: Taking false branch 755 | if (__len < __limit) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:763:9: note: Assuming '__depth' is not equal to 0 763 | if (__depth == 0) { | ^~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:763:5: note: Taking false branch 763 | if (__depth == 0) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:773:11: note: Assuming '__len' is <= '__ninther_threshold' 773 | if (__len > __ninther_threshold) { | ^~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:773:7: note: Taking false branch 773 | if (__len > __ninther_threshold) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:794:10: note: '__leftmost' is true 794 | if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) { | ^~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:794:21: note: Left side of '&&' is false 794 | if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:801:9: note: '?' condition is false 801 | _UseBitSetPartition | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:803:15: note: Calling '__partition_with_equals_on_right<std::_RangeAlgPolicy, std::string *, bool (*&)(const std::string &, const std::string &)>' 803 | : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:594:3: note: '?' condition is true 594 | _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), ""); | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED' 314 | # define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message) _LIBCPP_ASSERT(expression, message) | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT' 21 | (__builtin_expect(static_cast<bool>(expression), 1) \ | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:597:14: note: Object of type 'std::basic_string' is left in a valid but unspecified state after move 597 | value_type __pivot(_Ops::__iter_move(__first)); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:603:5: note: Assuming the condition is true 603 | _LIBCPP_ASSERT_UNCATEGORIZED( | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED' 314 | # define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message) _LIBCPP_ASSERT(expression, message) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT' 21 | (__builtin_expect(static_cast<bool>(expression), 1) \ | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:603:5: note: '?' condition is true 603 | _LIBCPP_ASSERT_UNCATEGORIZED( | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__config:314:75: note: expanded from macro '_LIBCPP_ASSERT_UNCATEGORIZED' 314 | # define _LIBCPP_ASSERT_UNCATEGORIZED(expression, message) _LIBCPP_ASSERT(expression, message) | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__assert:21:4: note: expanded from macro '_LIBCPP_ASSERT' 21 | (__builtin_expect(static_cast<bool>(expression), 1) \ | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:601:3: note: Loop condition is false. Exiting loop 601 | do { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:609:3: note: Taking true branch 609 | if (__begin == __first - difference_type(1)) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:610:12: note: Assuming '__first' is >= '__last' 610 | while (__first < __last && !__comp(*--__last, __pivot)) | ^~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:610:29: note: Left side of '&&' is false 610 | while (__first < __last && !__comp(*--__last, __pivot)) | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:629:3: note: Loop condition is false. Execution continues on line 645 629 | while (__first < __last) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:646:7: note: '__begin' is equal to '__pivot_pos' 646 | if (__begin != __pivot_pos) { | ^~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:646:3: note: Taking false branch 646 | if (__begin != __pivot_pos) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:803:15: note: Returning from '__partition_with_equals_on_right<std::_RangeAlgPolicy, std::string *, bool (*&)(const std::string &, const std::string &)>' 803 | : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:807:9: note: Assuming field 'second' is true 807 | if (__ret.second) { | ^~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:807:5: note: Taking true branch 807 | if (__ret.second) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:808:19: note: Calling '__insertion_sort_incomplete<std::_RangeAlgPolicy, bool (*&)(const std::string &, const std::string &), std::string *>' 808 | bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:314:3: note: Control jumps to 'case 2:' at line 318 314 | switch (__last - __first) { | ^ /Users/avogelsgesang/bazel-cache/bazel/bazel_user_root/0a6b6ee4727d75e1dd322c74e148faf8/execroot/__main__/external/clang_darwin/include/c++/v1/__algorithm/sort.h:319:9: note: Calling 'lessSize' 319 | if (__comp(*--__last, *__first)) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~ example.cpp:8:24: note: Method called on moved-from object of type 'std::basic_string' 8 | return a.length() < b.length(); | ^~~~~~~~~~ ```
justincady commented 6 months ago

I see the same issue in std::sort, also using clang-tidy 17.0.6:

#include <algorithm>
#include <string.h>
#include <string>
#include <vector>

bool custom(const char *lhs, const char *rhs) { return ::strcmp(lhs, rhs) < 0; }

static bool custom_sort(const std::string &lhs, const std::string &rhs) {
  return custom(lhs.c_str(), rhs.c_str());
}

int main() {
  std::vector<std::string> v;
  std::sort(v.begin(), v.end(), custom_sort);
  return 0;
}
sort.cc:9:30: warning: Method called on moved-from object of type 'std::basic_string' [clang-analyzer-cplusplus.Move]
    9 |   return custom(lhs.c_str(), rhs.c_str());
      |                              ^
[...]
steakhal commented 6 months ago

Confirmed https://godbolt.org/z/WxbrsE74o

steakhal commented 6 months ago

We inline the stdlib implementation and then get lost inside, and we eventually end up calling the comparator on an item we already "moved" once.

I can see two solutions:

1) Simply disable inlining for std::sort and std::ranges::sort respectively. This would save signifficant time and also save us from these FPs. 2) Mark "length" and "size" as "isMoveSafeMethod" member functions inside the MoveChecker. This would only mitigate from these FPs; but not from more nuanced ones where the comporator would call other member functions.

I think both of these improvements would be great to have, but arguably option 1 would be ideal for getting rid of these "sort" FPs.

NagyDonat commented 6 months ago

I'm seconding that disabling inlining for std::sort and std::ranges::sort is a reasonable solution.

haoNoQ commented 6 months ago

Yes, this sounds perfectly reasonable to me as well. Intense aliasing causes a lot of problems of this kind for us and std::sort is exactly that kind of nightmare.

steakhal commented 6 months ago

It turns out matching std::ranges functions might be tricky for libc++. They use constexpr global variables referring to a struct that has an overloaded (call) operator():

 namespace __attribute__((__type_visibility__("default"))) std { inline namespace __1 {

namespace ranges {
namespace __sort {

struct __fn {
  template <class _Iter, class _Sent, class _Comp, class _Proj>
  __attribute__((__visibility__("hidden"))) __attribute__((__exclude_from_explicit_instantiation__)) __attribute__((__abi_tag__("ne190000"))) constexpr static _Iter
  __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
    auto __last_iter = ranges::next(__first, __last);

    auto&& __projected_comp = std::__make_projected(__comp, __proj);
    std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);

    return __last_iter;
  }

  template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
    requires sortable<_Iter, _Comp, _Proj>
  __attribute__((__visibility__("hidden"))) __attribute__((__exclude_from_explicit_instantiation__)) __attribute__((__abi_tag__("ne190000"))) constexpr _Iter
  operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
    return __sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
  }

  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
    requires sortable<iterator_t<_Range>, _Comp, _Proj>
  __attribute__((__visibility__("hidden"))) __attribute__((__exclude_from_explicit_instantiation__)) __attribute__((__abi_tag__("ne190000"))) constexpr borrowed_iterator_t<_Range>
  operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
    return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
  }
}; // struct __fn

}

inline namespace __cpo {
inline constexpr auto sort = __sort::__fn{};
} // inline __cpo
} // ranges
} // inline v1
} // std

This problem might occur to other std library functions, I figure. We might want to generalize CallDescriptions to implicitly match these as if the operator() was directly invoked. Note that inlining worked this out because the global constant is initialized with a known value, thus the engine trusted it and followed the call.

steakhal commented 6 months ago

It turns out matching std::ranges functions might be tricky for libc++. They use constexpr global variables referring to a struct that has an overloaded (call) operator(): [...] This problem might occur to other std library functions, I figure. We might want to generalize CallDescriptions to implicitly match these as if the operator() was directly invoked. Note that inlining worked this out because the global constant is initialized with a known value, thus the engine trusted it and followed the call.

Imagine this: Have a special hidden checker implement the check::ASTDecl<TranslationUnitDecl> callback. It would do an AST traversal, an collect all global vardecls that are constant and has initializer. If the initializer type is a CXXRecordDecl, then it could add a mapping to a private map as CXXRecordDecl -> VarDecl.

The CallDescriptions could refer to this private map and do lookups in it. When we have a CallDescription::matches(Call) invocation, it could check if the Call is an instance call, and in that case take the decl of it and get to the CXXRecordDecl it corresponds to. It could use that as a key in the map I referred to in the previous paragraph. So, the lookup will result in the VarDecl that we can now match against the CallDescription rule, as if it had a name of a FunctionDecl.

This approach of course wouldn't be always correct, as in CTU, we might actually load definitions of (previously) constant global variable declarations; but this technique should still work for the libc++ case at least.

After we can match std::ranges::sort, then we can write a checker that basically conservatively eval calls a set of matched functions; thus achieve force opaque calls. However, it might be a good place to ensure that certain other functions always get inlined, such as lightweight container member functions, such as std::span and std::string_view for instance, but I don't have specific ideas achieving that.