Cppcoreguidelines: Implementing vector: bounds.1: Don't use pointer arithmetic. Use span instead.

[gnzlbg]

Most of my projects contain at least 3 implementations of std::vector-like containers, and clang-tidy just complained about using pointer arithmetic in all of them.

That's ok I guess, but what has me baffled is the proposed solution. I was expecting something like "prefer not to use pointer arithmetic, or turn this lint off if you need to, here is how", but the proposed solution is: "use span instead".

Should I really implement vector on top of span? Not that it is impossible, but it seems like a very complex solution to a problem that's actually simple (give me two spans and some pointer arithmetic... oh wait).

Anyhow, either the recommendation needs some work, or the guideline needs some work. Implementing vector is actually something "very simple", and the guideline should at least be able to make its point there. If I was implementing a graph with pointers, and clang-tidy tells me to use span, i'll probably just uninstall it.

For the time being I just turned this lint off. And if people turn it off, its not of much help either :/

[galik]

If you are implementing your own containers then I think you need to deal with low level programming techniques that application programmers do better to avoid. I suspect higher level constructs like gsl::span are intended for application programmers rather than library designers. I am curious why you are creating your own containers for every project though. What is std::vector lacking that you reimpliment it several times in one project?

[scraimer]

@gnzlbg, may I assume your pointer math is on some contiguous spans of memory? Wouldn't your code be improved by accessing it in a bounds-checked way? After all, arrays too easily decay into pointer, with no length information.

[gnzlbg]

I am not implementing them for every project, but I am using them in every project, so every project gets the warnings.

What is std::vector lacking that you reimpliment it several times in one project?

1. Small vector optimization -> boost::small_vector / llvm::SmallVector
2. fixed_capacity optimization -> boost::static_vector
3. Ability to store bools as `bools -> boost::vector
4. Better debug assertions / __builtin_assume optimizations in release
5. Better cold code annotations / likely/unlikely (for stuff like vector grow which happens rarely)
6. Alignment that doesn't segfault for SIMD types
7. Constexpr friendly
8. Ability to default/value initialize elements when desired (on construction, resize,...)

I don't know, that's from the top of my head. I have replacements for:

• std::vector (SIMD alignment, default/value initialization for network buffers)
• boost::small_vector (cause they used clang intrinsics for too many releases that got removed from clang, and released, so its broken in clang 3.9, SIMD alignment)
• fixed_capacity_vector (cause boost::static_vector is not constexpr, SIMD alignment)
• array (because its not constexpr friendly, SIMD alignment)
• boost::flat_set (as a sorted vector, because I want to be able to bulk insert, and then sort unique afterwards, and also, because boost::flat_set is not a container adaptor.... so I cannot have a boost::small_flat_set or fixed_capacity_set when needed, but with mine I can, and I do use them often)

and since I can easily modify them, I've gotten used to really good assertions and performance, that the standard libraries typically do not deliver because they cannot. For example, assertion that says "Index {} is out of bounds [0, {})" ... when indexing. A standard library would need to make their uses rely on iostream or something else for that, but since I rely on fmtlib anyways, I can do a bit better.

I also have a vector_view to pass vectors for reading/writing (without increasing the capacity) through APIs independently of the vector type.

I don't know, when it comes to containers, vector is my weapon of choice, and when you have such a large vector toolbox available, you end up choosing the right vector for the right problem.

For example, I needed to cast some rays and store some degenerate intersections. The easiest way is to store the tree nodes where they happen in a set, but casting millions of ray per second, I cannot allocate a std::set and heap allocate each node and what not. I put a small_flat_set on the stack with capacity for 20 ints, added an assertion for its size getting close to 20 (so that I can notice a potential performance problem), and went on with my life: zero run time cost, vs 99% of time spent on malloc and accessing memory if I switch it to a std::set...

[gnzlbg]

@gnzlbg, may I assume your pointer math is on some contiguous spans of memory? Wouldn't your code be improved by accessing it in a bounds-checked way? After all, arrays too easily decay into pointer, with no length information.

You would at least need 2 spans to implement vector, and to be able to move their bounds (or do pointer arithmetic on them...). I also don't know how span handles uninitialized memory, but you would need one of the spans to at least cover a region of uninitialized memory to get vector semantics :/

Nothing is impossible, but using spans feels to me like using the worst tool for the job. When the only thing you have is a hammer though...

[jwakely]

I agree that using span to implement vector doesn't make sense, vector::operator[] needs to be able to do unchecked access and it already provides its own (optional) checking.
But I also think if you're implementing something like vector then you need to selectively apply the guidelines, e.g. by teaching your checker to ignore certain code. That doesn't seem like a problem with the guidelines themselves, but the checker and/or your use of it.

[scraimer]

IIRC, you can use -isystem instead of -I when including a directory to disable warning on files included from that directory.

[gnzlbg]

@jwakely I'll see if I can disable that particular check in the required places only via clang-tidy. I just have a .clang-tidy file, and for now just enable/disable them globally.

My point was more than maybe "Use span" is too much of a black/white recommendation, and clang-tidy just copies the recommendations from here. Nothing is black and white.

If clang-tidy tells me "Prefer to use span, or if you really need pointer arithmetic, write // NO-TIDY CHECKXYZ123 on this line to disable it", then I might keep the check.

If it tells me "Use span"... I'm like, this check is broken.

@scraimer that's even worse than just disabling a single check globally, since it disables _all warnings_ as well :/

EDIT: One can write //NO-LINT to disable all checks for one line, but the docs don't say how to disable a single check.

[MikeGitb]

Personally I'm not a big fan of gal::span anymore, but I think it would be more helpful to make a feature request against clang tidy to allow suppression of specific checks than arguing about how strictly the guidelines should be worded.

Even if you'd change the rule to be less black and white, clang tidy would still warn about it and you'd still need a way to deactivate it. Also, I guess a lot of other checks could profit from such a mechanism.

[hsutter]

I think the primary question here is how to not get warnings on 'other people's code' that we don't control (e.g., we're not going to ask people to reimplement their implementation of vector).

MSVC /analyze allows you to skip headers. This sounds like a request for the clang-tidy team?

[neilmacintosh]

To the original point by @gnzlbg, the Guidelines are designed to apply to the majority of user code. People who implement libraries, or have sections of very low-level code (e.g. OS kernels or hardware access in device drivers) may find that some specific guidelines do not apply to them. That doesn't limit the usefulness of the Guidelines as most people use a vector or graph data structure, fewer people implement one.

Nonetheless, the fact we can't allow for every context in a rule is why we hope that tools that check the Guidelines will provide flexible mechanisms for excluding code from analysis and suppressing individual warnings. I'm pretty sure clang-tidy does offer such mechanisms, although I'm no expert in them. If it doesn't, I'm sure the clang-tidy folks would be interested in a feature request ;-)

And just to answer the observation about implementing a vector using span:

If you were implementing a vector-like class, then such a class is an owner of memory. So applying the Guidelines would lead you to use an owner<T> (or better yet unique_ptr<T>) to hold the memory that was allocated for the vector. You could then use one or more spans to refer to regions within that allocation if you wanted (e.g. the in-use region of the vector).

[djarek]

I'm wondering - perhaps it would be beneficial to assign special meaning (from the guidelines' point of view) to any namespace (or nested namespace) named unsafe somewhat like it's done in Rust with unsafe blocks (it won't have syntactic support, but I believe it would be more readable than littering code with linter-disabling comments). This approach would allow clean separation of low level code from higher level constructs. As an example:

namespace xyz {
namespace unsafe {
struct custom_vector_impl
{
    // methods using pointer arithmetic to get the job done efficiently
};
} //namespace unsafe

class custom_vector : private unsafe::custom_vector_impl
{
public:
    // "safe" public interface
};
} //namespace xyz

Instead of disabling all checks for unsafe namespaces we might as well consider "annotating" them and explicitly specifying what the checker should allow.

The rationale for this approach is that most code should be in the default ("safe") category. Unsafe details should be separated out so that it's easier for a human to analyze their correctess.

[neilmacintosh]

@djarek The MSVC-based implementation of checks for the Core Guidelines respects a C++ annotation for suppressing its warnings: [[gsl::suppress(bounds.1)]]. This is allows fine (or broader) grained suppressions depending on the syntax element that is annotated and has no effect on compilation.

[MikeGitb]

@neilmacintosh: Regarding the implementation of vector like types: I first thought about something similar, but that would mean that your vector is bigger (span + owning pointer + capacity = 4*sizeof(void*) vs 3*sizeof(void*) for a typical implemenation) and that you have now two pointers you have to keep in sync throughout reallocations, movements etc.

Have you considered adding some sort of a mixin/CRTP- utility class to the gsl that provides the interface of a span but relies on the user type to provide the pointer and size via member functions? Internally the user class could then derive that pointer from whatever fits the requirements - be it a T*, a unique_ptr<T>, a owner<T*> or just some stackallocated buffer.

[neilmacintosh]

@MikeGitb Yes, there may be a size difference over a raw pointer-based implementation. My point was not to seriously suggest the implementation strategy, but to illustrate what the guidelines would suggest for that particular problem. Specifically, I was trying to remind everyone that vector owns, so you'd need an owner<T> in there.

But I think discussing how to implement vector using span is not really a very valuable direction.
vector is really another fundamental vocabulary type - just like span. I would expect it to use a fairly low-level and careful implementation approach. And I believe that it should not be implemented very often. Of more interest (I would think) would be discussing how you use span outside of standard library implementations ;-)

[MikeGitb]

Well, obviously the issue was not about implementing std::vector, but vector/array like types in general. Certainly not something you'd do every day, but a lot of projects have such containers.

But ok, I probably got carried away with my mixin suggestion.

[gnzlbg]

Hey guys, thank you all for the feedback. I've filled a couple of clang-tidy issues related to finer grained control about how to disable specific checks.

Right now clang-tidy only offers two options:

• a // NOLINT annotation that disables all lints in a given line,
• a suppression file that contains a sequence of filenames and line numbers.

The suppression file is not really maintainable, and the // NOLINT annotation is to coarse-grained (it disables all lints), and doesn't play good with a formatting tool (e.g. clang-format will move comments around to make them conform to a style guide, and if they end up in a different line, the annotation will refer to the wrong line and stop working).

All in all after using the guidelines for about one week, which is not much, I actually think that at least for me the major issues with the guidelines are:

• 90% of the code we write are on libraries, that is, we build libraries to solve our problems, and then, use them to write applications. Application code is kept as small as possible, and reusable parts are always moved to a library sooner or later (and made generic). @neilmacintosh mentioned that the guidelines might not be suitable for library writers, and I think this hits us hard.

• Most guidelines say "Don't do that", and that's it. This is a bit shocking to me, maybe because I am used to Rust's linting tool (clippy) which tells you "You are doing this, but because of X it would probably be better to do this or that instead. However, in this or that case what you are doing is correct, and you can make it explicit by doing this, or you can disable this lint locally by doing that". And Rust's is a language with some "black and white" cases where something is objectively better than something else; C++ is never black and white. When clang-tidy, which copies the text 1:1 from this repo, tells me "Don't do that." in a piece of code where it is debatable (or actually the best thing to do), my first reaction is to think "this lint is broken / this tool is broken" and go for disabling the lint globally. It takes _extra effort_ to step back, consider what the lint is doing, why, go read the cpp guidelines, evaluate in which cases this lint makes sense, evaluate whether I want to be warned about these cases, evaluate the effort required to disable the lint in all the cases in which it will be wrong (mostly because the examples considers in the cppguidelines repo are "too simple" or do not consider "corners of the language" [0, 1]), and then make an informed decision of whether disable it locally or globally. This is obviously partially a clang-tidy thing, but the wording part "Don't do that. Period.", is a cppguidelines thing, and IMO a more important bug than any clang-tidy bug that I've found (clang-tidy just copies this wording).

[0] One example of a "corner" of the language that might be easy to miss is unions with destructors. Clang tidy recommends writing ~type() {} as ~type() = default;, always. If type is an union, this will end up badly.

[1] Another one is the C-array to pointer decay check. I got lots of errors on variadic perfect forwarding functions from clang-tidy because "sometimes" they were correctly decaying char arrays to const char* (consider apply(fprintf, args...) where the args are forwarded to a C function and thus decay). Implementing apply or anything like it in a way that the C-array to const char* are explicit is not only hard, but also completely unidiomatic. This check is _not_ useless, but trying to enforce it in the implementation of apply (and many others) is wrong. The guideline wording doesn't even consider such cases, in which implicit decay is the better solution. This "naivity" wouldn't be bad if the check wording wouldn't sound as a black or white "Don't ever do that"-thing.

I don't know. Maybe with MSVC the situation is better than with clang-tidy, but after trying it for a week and reporting ~20 bugs, I'll wait six months and give it a try again then. Sadly, I did that six months ago, and six months before that, each time reporting ~10-20 bugs, most of which are not fixed (or closed or anything) yet, so I doubt the experience will improve significantly.

If these tools are always going to miss some corner cases, which I believe they will do, having good wording that doesn't give the feeling of wishful thinking becomes even more critical to the tool's success.

[neilmacintosh]

@gnzlbg thanks for the helpful feedback about the wording of guidelines and the issues you've observed with tooling that enforces them. That will definitely be considered as we go forward with development of both.

Just to clarify my point about where the guidelines are meant to apply. When I said "library implementers" you have helped me realize I used too broad a phrase. I meant "implementers of foundational libraries" (things like the standard library or GSL), rather than libraries for higher-level facilities or common tasks (XML parsing or HTTP communication etc). Apologies for any confusion I may have caused there.