Page MenuHomePhabricator

[Analyzer] Iterator Checkers - Model `empty()` method of containers
Needs ReviewPublic

Authored by baloghadamsoftware on May 30 2019, 9:24 AM.

Details

Reviewers
NoQ
Szelethus
Summary

Modeling of the empty() method is essential for more accurate reporting past-the-end iterator access.

Diff Detail

Event Timeline

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

// RUN: %clang_analyzer_cc1 -analyzer-checker=core,debug.IteratorInspection

template <class Cont>
void clang_analyzer_container_size(const Cont &);

template <class It, class Cont>
void clang_analyzer_is_attached_to_container(const It &, const Cont &);

void non_empty1(const std::vector<int> &V) {
  assert(!V.empty());
  for (auto n: V) {}
  clang_analyzer_container_size(V); // expected-warning{{[1, intmax]}}
}

void non_empty2(const std::vector<int> &V) {
  for (auto n: V) {}
  assert(V.empty());
  clang_analyzer_container_size(V); // expected-warning{{[0, 0]}}
}

void foo(std::vector<int> v1, std::vector<int> v2) {
  clang_analyzer_is_attached_to_container(v1.begin(), v2); // expected-warning{{FALSE}}
}

etc etc.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
714

We seem to retrieve the CXXInstanceCall here too?

Szelethus added inline comments.Jun 18 2019, 7:39 PM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1741–1763

But what if we have a container for which the iterator isn't an inline class, or we don't even have an in-class alias for it? I think whether the record has a begin/end method would be a better heuristic.

test/Analysis/iterator-range.cpp
247

Aha, the for loop is here to force a state split on whether V is empty or not, correct?

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

// RUN: %clang_analyzer_cc1 -analyzer-checker=core,debug.IteratorInspection

template <class Cont>
void clang_analyzer_container_size(const Cont &);

template <class It, class Cont>
void clang_analyzer_is_attached_to_container(const It &, const Cont &);

void non_empty1(const std::vector<int> &V) {
  assert(!V.empty());
  for (auto n: V) {}
  clang_analyzer_container_size(V); // expected-warning{{[1, intmax]}}
}

void non_empty2(const std::vector<int> &V) {
  for (auto n: V) {}
  assert(V.empty());
  clang_analyzer_container_size(V); // expected-warning{{[0, 0]}}
}

void foo(std::vector<int> v1, std::vector<int> v2) {
  clang_analyzer_is_attached_to_container(v1.begin(), v2); // expected-warning{{FALSE}}
}

etc etc.

baloghadamsoftware marked 3 inline comments as done.EditedJul 30 2019, 5:36 AM

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

Good idea! However, I would do it in a way that we can reuse our existing debug functions in the tests:

template <typename Iter> long clang_iterator_position(const Iter&);
template <typename Iter, typename Cont> const Cont& clang_iterator_container(const Iter&);
template <typename Iter> long clang_container_begin(const Iter&);
template <typename Iter> long clang_container_end(const Iter&);

Then we can nest calls for these functions into call of clang_analyzer_dump(), clang_analyzer_eval(), clang_analyzer_denote() etc.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
714

Eventually this function needs refactoring.

1741–1763

Or maybe both, or maybe either. I am not sure here.

test/Analysis/iterator-range.cpp
247

Yes.

Hmm, an idea just popped into my head. I'm not sure whether we have a single checker that does so much complicated (and totally awesome) modeling as IteratorChecker. What do you think about a debug checker similar to debug.ExprInspection, like debug.IteratorInspection?

Good idea! However, I would do it in a way that we can reuse our existing debug functions in the tests:

template <typename Iter> long clang_iterator_position(const Iter&);
template <typename Iter, typename Cont> const Cont& clang_iterator_container(const Iter&);
template <typename Iter> long clang_container_begin(const Iter&);
template <typename Iter> long clang_container_end(const Iter&);

Then we can nest calls for these functions into call of clang_analyzer_dump(), clang_analyzer_eval(), clang_analyzer_denote() etc.

Sounds awesome! I personally struggle a bit with these patches because the problem is so complex, I think this would help with reviewing tremendously.