Page properties | ||
---|---|---|
| ||
This has nothing to do with CTR as a group, and everything to do with the algorithmic requirements of the STL. However, I cannot think of a better place for this rule to live (aside from MSC, and I think CTR is an improvement). If we wind up with an STL category, this should probably go there. |
The C++ standard library implements numerous common algorithms that accept a predicate function object. The C++ Standard, [algorithms.general], paragraph 10 [ISO/IEC 14882-2014], states the following:
[Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as
reference_wrapper<T>
, or some equivalent solution. — end note]
Because it is implementation-defined whether an algorithm copies a predicate function object, any such object must either
- implement a function call operator that does not mutate state related to the function object's identity, such as nonstatic data members or captured values, or
- wrap the predicate function object in a
std::reference_wrapper<T>
(or an equivalent solution).
Marking the function call operator as const
is beneficial, but insufficient, because data members with the mutable
storage class specifier may still be modified within a const
member function.
Noncompliant Code Example (Functor)
This noncompliant code example attempts to remove the third item in a container
STL containers that take predicate functors are perfectly free to make multiple copies of the predicate, and often do, because typically predicates are passed by value. [Meyers 01] Item 38) If a predicate stores and uses internal state, then its state values at the end of a predicate-based function call are implementation-defined, and usually unexpected.
Non-Compliant Code Example
This example tries to remove the 3rd item in a container of widgets by using a predicate that returns true
only on its 3rd third invocation.
Code Block | ||||
---|---|---|---|---|
| ||||
#include <algorithm> #include <functional> #include <iostream> #include <vector><iterator> using namespace std; #include <vector> class BadPredicateMutablePredicate : public std::unary_function<int, bool> { size_t timesCalled; public: BadPredicateMutablePredicate() : timesCalled(0) {} bool operator()(const int &) { return ++timesCalled == 3; } }; int main () { vector<int> v; for (int i = 0; i < 10; i++) { v.push_back(i); } cout << "Vector contains:"; for (const auto &i : v) { cout << " " << i; } cout << endltemplate <typename Iter> void print_container(Iter b, Iter e) { std::cout << "Contains: "; std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " ")); std::cout << std::endl; } void f() { std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; print_container(v.begin(), v.end()); v.erase(std::remove_if(v.begin(), v.end(), BadPredicateMutablePredicate()), v.end()); cout << "Vector contains:"; for (const auto &i : v) { cout << " " << i; } cout << endl; return 0; } print_container(v.begin(), v.end()); } |
However, std::remove_if()
is permitted However, the remove_if
is permitted by the standard to construct and use extra copies of its predicate function. Such Any such extra copies confound the timesCalled
variablemay result in unexpected output.
Implementation Details
For instance, this This program produces the following results , using gcc 4.8.1 :
...
with libstdc++.
Code Block | ||
---|---|---|
| ||
Contains: 0 1 2 3 4 5 6 7 8 9 Contains: 0 1 3 4 6 7 8 9 |
This result arises when because std::remove_if
makes two copies of the predicate before invoking it. It uses the first copy until it receives a true
response (when removing 2
), and uses the second copy. The second copy again returns true
on its 3rd invocation, causing the 5
to also be removed.
Compliant Solution (const
)
The first copy is used to determine the location of the first element in the sequence for which the predicate returns true
. The subsequent copy is used for removing other elements in the sequence. This results in the third element (2
) and sixth element (5
) being removed; two distinct predicate functions are used.
Noncompliant Code Example (Lambda)
Similar to the functor noncompliant code example, this noncompliant code example attempts to remove the third item in a container using a predicate lambda function that returns true
only on its third invocation. As with the functor, this lambda carries local state information, which it attempts to mutate within its function call operator.
Code Block | ||||
---|---|---|---|---|
| ||||
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
template <typename Iter>
void print_container(Iter b, Iter e) {
std::cout << "Contains: ";
std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " "));
std::cout << std::endl;
}
void f() {
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
print_container(v.begin(), v.end());
int timesCalled = 0;
v.erase(std::remove_if(v.begin(), v.end(), [timesCalled](const int &) mutable { return ++timesCalled == 3; }), v.end());
print_container(v.begin(), v.end());
} |
Compliant Solution (std::reference_wrapper
)
This compliant solution uses std::ref
to wrap the predicate in a std::reference_wrapper<T>
object, ensuring that copies of the wrapper object all refer to the same underlying predicate objectA simple way to prevent this behavior is to declare the predicate's operator()
to be const
.
Code Block | |||||
---|---|---|---|---|---|
| |||||
#include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> class MutablePredicate : public std::unary_function<int, bool> { size_t timesCalled; public: MutablePredicate() : timesCalled(0) {} bool operator()(const int &) const { return ++timesCalled == 3; } }; template <typename Iter> void print_container(Iter b, Iter e) { std::cout << "Contains: "; std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " ")); std::cout << std::endl; } void f() { std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; print_container(v.begin(), v.end()); MutablePredicate mp; v.erase(std::remove_if(v.begin(), v.end(), std::ref(mp)), v.end()); print_container(v.begin(), v.end()); } |
The compiler will fail to build this program because of the attempt to increment a class field within a const method.
Compliant Solution (Iterator arithmetic)
above compliant solution demonstrates using a reference wrapper over a functor object but can similarly be used with a stateful lambda. The code produces the expected results, where only the third element is removed.
Code Block | ||
---|---|---|
| ||
Contains: 0 1 2 3 4 5 6 7 8 9
Contains: 0 1 3 4 5 6 7 8 9 |
Compliant Solution (Iterator Arithmetic)
Removing a specific element of a container does not require a predicate function but can instead simply use std::vector::erase()
, as in this compliant solution.The proper way to remove a container element based on position is with iterator arithmetic:
Code Block | |||||
---|---|---|---|---|---|
| |||||
#include <algorithm> #include <iostream> #include <iterator> #include <vector> template <typename Iter> void print_container(Iter B, Iter E) { std::cout << "Contains: "; std::copy(B, E, std::ostream_iterator<decltype(*B)>(std::cout, " ")); std::cout << std::endl; } void f() { std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; print_container(v.begin(), v.end()); v.v.erase(v.begin() + 3); print_container(v.begin(), v.end()); } |
Risk Assessment
Predicates that contain internal Using a predicate function object that contains state can produce unexpected values after usage.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
---|
CTR58-CPP |
Low |
Likely |
High | P3 | L3 |
Automated Detection
Tool | Version | Checker | Description | ||||||
---|---|---|---|---|---|---|---|---|---|
Helix QAC |
| C++3225, C++3226, C++3227, C++3228, C++3229, C++3230, C++3231, C++3232, C++3233, C++3234 | |||||||
Parasoft C/C++test |
| CERT_CPP-CTR58-a | Make predicates const pure functions | ||||||
Polyspace Bug Finder |
| CERT C++: CTR58-CPP | Checks for function object that modifies its state (rule fully covered). |
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
Bibliography
[ISO/IEC 14882-2014] | Subclause 25.1, "General" |
[Meyers |
...
2001] | Item 39 |
...
, "Make Predicates Pure Functions" |
...