False positive <algorithm> for std::max, std::copy

[carlosgalvezp]

Hi,

We are consistently getting the following false positive:

c.cpp:10:9: warning: std::max is defined in <algorithm>, which isn't directly #included.

Somehow this failure only happens when importing the nlohmann/json library

The following code reproduces the problem:

#include <vector>

#include <nlohmann/json.hpp>

class Foo
{
 public:
    void bar()
    {
        v.push_back(0.F);  /// < IWYU warning emitted here!?
    }

 private:
    std::vector<float> v;
};

void f()
{
    nlohmann::json json;
    Foo f;
}

This warning goes away if I remove the #include <nlohmann/json.hpp> line. Why is that the case? It doesn't make sense, there's no use of std::max in this .cpp file. There's not even such a use in the json.hpp library itself, which by the way includes the algorithm header.

I have tried increasing verbosity but I can't really understand where the problem comes from. Any ideas? How can I debug further?

Thanks!!

[carlosgalvezp]

Looking more closely at the verbose output, I see:

/usr/include/c++/7.5.0/bits/stl_vector.h:1507:35: (26 in tpl) [ FunctionCall ] 0x2e90558 template<> constexpr const unsigned long &max<unsigned long>(const unsigned long &__a, const unsigned long &__b)
Marked full-info use of decl 0x1ec4098 std::max (from /usr/include/c++/7.5.0/bits/stl_algobase.h:219:5) at c.cpp:10:9

That line inside stl_vector.h indeed uses std::max:

        const size_type __len = size() + std::max(size(), __n);

But that's an internal detail of stl_vector.h, it should not affect users in any way. I'd gladly put up a patch to fix it but I'm totally unfamiliar with the code, do you have any hints?

[carlosgalvezp]

Also, if I swap the vector and json.hpp include lines, I get one more FP for std::copy:

/usr/include/c++/7.5.0/bits/stl_uninitialized.h:101:18: (44 in tpl) [ FunctionCall ] 0x7f72b1c07cc8 template<> float *copy<std::move_iterator<float *>, float *>(std::move_iterator<float *> __first, std::move_iterator<float *> __last, float *__result)
Marked full-info use of decl 0x1009448 std::copy (from /usr/include/c++/7.5.0/bits/stl_algobase.h:446:5) at c.cpp:10:9

[kimgr]

@carlosgalvezp Curious. I get the opposite behavior:

$ cat other.hpp
#include <algorithm>

namespace test {
struct json {};
}

$ cat t.cc
#include <other.hpp>
#include <vector>

class Foo {
 public:
    void bar() {
        v.push_back(0.F);
    }

 private:
    std::vector<float> v;
};

void f() {
    test::json json;
    Foo f;
}

$ include-what-you-use -I. t.cc 

t.cc should add these lines:
#include <algorithm>  // for max

t.cc should remove these lines:

The full include-list for t.cc:
#include <algorithm>  // for max
#include <other.hpp>  // for json
#include <vector>     // for vector
---

But with <other.hpp> and <vector> transposed:

$ include-what-you-use -I. t.cc 

(t.cc has correct #includes/fwd-decls)

I diffed the results between other/vector and vector/other, and the place that seems to cause the additional use is:

@@ -8443,8 +8447,8 @@
 /usr/include/c++/9/bits/stl_vector.h:1758:36: (29 in tpl) [ DeclRefExpr ]  DeclRefExpr  'const unsigned long &(const unsigned long &, const unsigned long &)' lvalue Functio
n  'max' 'const unsigned long &(const unsigned long &, const unsigned long &)' (FunctionTemplate  'max')
 
 /usr/include/c++/9/bits/stl_vector.h:1758:36: (30 in tpl) [ NestedNameSpecifier ]  std::
-/usr/include/c++/9/bits/stl_vector.h:1758:36: (29 in tpl) [ FunctionCall ]  template<> inline constexpr const unsigned long &max<unsigned long>(const unsigned long &__a, co
nst unsigned long &__b)
-Marked full-info use of decl  std::max (from /usr/include/c++/9/bits/stl_algobase.h:222:5) at /usr/include/c++/9/bits/stl_vector.h:1758:36
+/usr/include/c++/9/bits/stl_vector.h:1758:36: (29 in tpl) [ FunctionCall ]  template<> constexpr const unsigned long &max<unsigned long>(const unsigned long &__a, const uns
igned long &__b)
+Marked full-info use of decl  std::max (from /usr/include/c++/9/bits/stl_algobase.h:222:5) at t.cc:9:9
 [Uninstantiated template AST-node]  [FunctionDecl] inline constexpr const _Tp &max(const _Tp &__a, const _Tp &__b)
 
 [Uninstantiated template AST-node] const _Tp &(const _Tp &, const _Tp &)

Still doesn't really make any sense that it would attribute it to the main file instead of to <vector>. But I also found this: https://github.com/include-what-you-use/include-what-you-use/blob/master/iwyu.cc#L1103

I'm not familiar with the use of processed overloads, but it seems probable that overloads are processed in a different order depending on inclusion order, so maybe something there skews the analysis.

[ptomato]

I have another minimal reproducer for this:

a.cpp:

#include <vector>
#include "b.h"

int main() {
    std::vector<int> vec;
    vec.push_back(42);
    return 0;
}

b.h:

#pragma once
#include <algorithm>

command line:

$ include-what-you-use -std=c++17 a.cpp 

a.cpp should add these lines:
#include <algorithm>  // for max

a.cpp should remove these lines:
- #include "b.h"  // lines 2-2

The full include-list for a.cpp:
#include <algorithm>  // for max
#include <vector>     // for vector
---

The false positive shows up if std::vector::push_back() or std::vector::emplace_back() is used, and <algorithm> is included via another header, and only with -std=c++17. Here, the order of including "b.h" and <vector> does not matter.

[ptomato]

In addition, this causes other weird behaviour down the line, with a slightly expanded version of the previous example:

a.cpp:

#define CCCC 1

#include <vector>
#include "b.h"
#include "c.h"

int main() {
    std::vector<int> vec;
    vec.push_back(42);
    return 0;
}

b.h:

#pragma once
#include <algorithm>

c.h:

#pragma once

struct C {};

static void ccc() {
#ifdef CCCC
  C c;
#endif
}

command line:

$ include-what-you-use -std=c++17 a.cpp 

a.cpp should add these lines:
#include <algorithm>  // for max

a.cpp should remove these lines:
- #include "b.h"  // lines 4-4

The full include-list for a.cpp:
#include <algorithm>  // for max
#include <vector>     // for vector
#include "c.h"  // lines 5-5
---

Note that c.h is not deemed unnecessary, despite nothing from it being used in a.cpp. If you remove #include "b.h" then c.h is correctly marked as unnecessary.

[kimgr]

I think that last example is by design -- it's a common pattern with x-macros to generate code using the C preprocessor:

// x.def
struct X_NAME {
    X_NAME(X_TYPE v)
        : name(#X_NAME),
          value(v) {
    }

    std::string name;
    X_TYPE value;
}; 

// mytypes.h
#define X_NAME IntType
#define X_TYPE int
#include "x.def"

#define X_NAME FloatType
#define X_TYPE float
#include "x.def"

...

IWYU actually has a rule to detect that if an included header depends on a symbol defined in the includer, we keep that header.

[kimgr]

But let's discuss that separately if necessary, so we don't confuse these two issues.

[wscott]

I am using this as a workaround at the moment in my mapping file.

  # workaround: https://github.com/include-what-you-use/include-what-you-use/issues/908
  # the symbol is OK from either header
  { symbol: ["std::max", "private", "<vector>", "public" ] },
  { symbol: ["std::max", "private", "<algorithm>", "public" ] },

[carlosgalvezp]

I can confirm the issue is still present on latest master, not only with c++17 (we use c++14).

[argothiel]

I'm getting the same for <boost/iterator/iterator_concepts> with <vector>:

#include <boost/iterator/iterator_concepts.hpp>`

#include <vector>

class MyClass;

void
pushMyObject(std::vector<MyClass*>& objects)
{
  MyClass* myObject = nullptr;
  objects.push_back(myObject);
}

test.cpp:11:3: warning: std::max is defined in <algorithm>, which isn't directly #included.

[firewave]

It seems this is fixed/improved with 0.22:

0.21
#include <algorithm> // for std::copy, std::max, std::reverse, std::equal, std::min, std::replace

0.22
#include <algorithm> // for std::reverse, std::equal, std::min, std::replace

[kimgr]

As far as I can tell this is fixed on latest master (a82c711).

There are still some unexpected suggestions for <nlohmann/json.hpp>, but that's no longer related to <algorithm>.

If anybody has a chance to test latest master on a real code base, and can confirm the improvement, we can close this one. Thanks!

[ptomato]

I'd love to test this on a real code base but I'm having trouble building IWYU. I get a bunch of compile errors such as:

In file included from /var/home/ptomato/workspace/include-what-you-use/iwyu_preprocessor.cc:10:
/var/home/ptomato/workspace/include-what-you-use/iwyu_preprocessor.h:203:8: error: ‘void include_what_you_use::IwyuPreprocessorInfo::InclusionDirective(clang::SourceLocation, const clang::Token&, llvm::StringRef, bool, clang::CharSourceRange, clang::OptionalFileEntryRef, llvm::StringRef, llvm::StringRef, const clang::Module*, bool, clang::SrcMgr::CharacteristicKind)’ marked ‘override’, but does not override
  203 |   void InclusionDirective(clang::SourceLocation hash_loc,
      |        ^~~~~~~~~~~~~~~~~~

I suspect the latest version is not meant to work with the version of LLVM in my environment (even though Cmake accepts it.)

Do you have a suggestion for how to bootstrap an environment where I could get the correct dependencies (and also install dependencies for my codebase) without too much hassle?