[WIP][analyzer][doc] Add Container- and IteratorModeling developer docs

[gamesh411]

Summary

Container and IteratorModeling is a feature in ClangSA which handles the containers and their
iterators. Containers include arrays and STL containers, and their iterators implemented as either
pointers or class instances.

[whisperity]

In general, perhaps you should go over the rendered text once again and make use of emph and bold some more.
Explanation looks okay from my part, although I'm really not knowledgeable about CSA internals. But there are plenty of "typesetting" issues.

Do you have to stick to 80-col in the documentation file? It is customary (at least in LaTeX) that prose is organised in a "one line of code per sentence" fashion. This also makes handling the diff easier... In the latter part towards the discussion about how iterators are targeted, the "80-col" is broken anyways.

clang/docs/analyzer/developer-docs.rst

14

How come this new addition is a .rst but the rest isn't. Does the rendering work without it? We should keep a style here, either way. So turn all into proper .rst links, or drop the .rst here.

clang/docs/analyzer/developer-docs/ContainerModeling.rst

5

Can the checker's name be turned into a link, or am I mixing up individual checker documentations' availability with Tidy?

Either way, show the check's name in bold face.

6

8

11

what does it refer to here?

21

Will this appear to the reader as alpha- or alpha.?

29

35

35–36

Iterator was linked already, I don't think this needs to repeat.

37–47

What about neibloids (see right before Parameters) (callables that are explicitly disabling ADL at a call site even though they look like an ADL call, with tricks, usually found in the ranges library).

40

Existence function?

51–55

Format these as monospace too.

57

71

87

106

(While I don't at all agree with the whole put the * to the variable name, not the type name yadda, Clang prints type names with a before the *, so let's keep it consistent...ly bad.)

110

114

122

123

126

147

148

I think something is missing for here, I am incapable of decyphering this sentence.

154–155

157

158

Is typesize a defined thing in the constraint manager? Otherwise, wouldn't sizeof(T) / 4 be better readable?

159

161–162

165–166

169

180

(same with T -> T below consistently)

185

204

What does the ' do here?

210

Should be?
Is.

213

224

227

236

261–282

Perhaps it would be better if indivudal comments for each line would simply be on the line before the code?

Something like:

// No modelling needed:
Container C;

// Bla bla
foo()

263

Yeaaaaaaah...

290

290–293

Previously, lvalue was written as LValue!

292

295

299

311

312

315

LValues, RValues, incosistency

317

320

Could we turn this on its head and simply call these "user-defined iterator types" instead of this, while technically correct, rather wonky "class instance" kind of stuff?

324–325

Which directory? Previously the algorithm checker was referenced with its logical name alpha.cplusplus.SomethingSomething.

328–329

331

335

340

360

I think LLVM's RST rendering rules have a .. option:: element, which renders it in a nice style. But this might also be Tidy-specific...

363

367

369

369

typo

372

373–374

[whisperity]

Actually, while the explanation is understandable for me with additional knowledge about the representation... I think it would be useful to add the most simple example from the iterator checkers to the end of the document, how this whole thing ties together and how it is useful in a checker.

[Szelethus]

I don't have the time to comb through this doc, unfortunately, but I want to applaud this effort to make the iterator checker family more accessible. Its certainly a forerunner in modeling tricky C++ constructs, and I can't wait to be a more valuable reviewer after being a bit more knowledgeable about it.

[dkrupp]

In D91948#2411058, @whisperity wrote:

Actually, while the explanation is understandable for me with additional knowledge about the representation... I think it would be useful to add the most simple example from the iterator checkers to the end of the document, how this whole thing ties together and how it is useful in a checker.

I cannot agree more. Please add examples (with indicators where we want warning) and explain how they would be handled according to the different implementation options. Also please highlight, if possible, what are the limitations of the different solutions: potential false positives that we cannot filter out, or bugs we will not be able to find.

[Szelethus]

As far as content goes, here are my thoughts:

There is a huge block of comments in the source code: https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp#L13. You have not mentioned these iterator categories: are they still a thing? If so, lets move those comments here, if not, just remove them altogether.

Please mention these docs on the top of iterator checker files.

Everything else:

In general, you have some meaningless sentences that I always catch myself writing as well: "There are a variety of techniques.". Its better to just list them straight away.

clang/docs/analyzer/developer-docs/ContainerModeling.rst

105–106

I think const MemRegion * is implied.

107–108

Fair enough, is this true though for containers whose lifetime was extended? Maybe I should know this myself :^)

132–140

Huh, interesting, considering the earlier point about how you track iterator positions. Couldn't you just say that <end symbol> = <begin symbol> + <some concrete value>? I mean, onbviously not, because if it was that simple it would have landed already, but why is that so difficult? Half a sentence about this should suffice.

213–214

This is the juicy part. I want some more thoughts in here: why? Can I have some examples?

290–313

Ah, there it is. Move it to where I placed my other inline! :)

301–305

This example is here to explain the previous two paragraphs, yet I'm left confused. I heard these things:

"If no Region is found for an iterator value then a Symbol is used (SymbolRef)."

Do we have a region here, or not? If we do, then this example doesn't demonstrate what was said highlighted in the first paragraph, so lets do that. There is no region here? Why?

"In the case of pointer iterators, the modeling of the symbolic value is simpler. The lifetime of such values is simple to model,
there is no need for constructors, destructors and copy-elision rules to be taken into consideration."

Do I gather correctly that we need to keep around a memregion and a symbolic value implementation anyways, so we might as well pick the easier one when possible? This look clunky, even if its true. With that said, a paragraph guiding me through the example outlining why its preferable to model it as a symbolic value would be appreciated.

319

You spent long enough on pointer iterators that subsectioning here would be justified.

324–325

This should be moved out of this section. You could mention those files that have the the lowest likelihood of being split up / renamed.

327–329

Why is this an issue? Please explain.

383

Any links to a previous discussion?

[martong]

Nice work!

clang/docs/analyzer/developer-docs/ContainerModeling.rst

125

148

+1

160

Or ...comparisons still cannot be handled properly. If the ContstraintManager` was also able ... then ...

210

222

:

227

264

266

276

branch 'A'

290

Why don't we track Rvalue containers? It's not clear from this document.

310–313

Break up this sentence please.

317

I think it would be useful to have a few sentences (preceding this paragraph) that introduces the SymbolMap and RegionMap and for what they used for.

329

353

iterators

369

chain

369

371–372

These sentences are word-by-word copies of the previous two sentences.

380

I vote for the extra layer of abstraction.

clang/docs/analyzer/developer-docs.rst

 Developer Docs
 ==============
 
 Contents:
 
 .. toctree::
    :maxdepth: 2
    
    developer-docs/DebugChecks
    developer-docs/IPA
    developer-docs/InitializerLists
    developer-docs/nullability
    developer-docs/RegionStore
+   developer-docs/ContainerModeling.rst
+   
 
 

clang/docs/analyzer/developer-docs/ContainerModeling.rst

+===============================
+Container and Iterator Modeling
+===============================
+
+The goal of checker ``alpha.cplusplus.ContainerModeling`` is to provide a
+symbolic abstraction for containers to the Clang Static Analyzer. There are
+various concepts regarding containers that help formulate static analysis
+problems more concisely. The size of the container, whether is empty or not are
+the most trivial motivating examples. Standard containers can be iterated, and
+this idiom is well-adopted in case of non-standard container implementations as
+well, because it can be used to provide a compatible interface to algorithms.
+Therefore iterator modeling is closely related to containers. Iterators extend
+the range of useful properties when it comes to finding bugs, for example, which
+container an iterator belongs to, what position inside the container it is in,
+and whether it is a valid or invalid state (see rules for `iterator invalidation
+<https://en.cppreference.com/w/cpp/container#Iterator_invalidation>`_).
+Iterator modeling is implemented in checker ``alpha.cplusplus.IteratorModeling``.
+
+There are also various checkers which make use if the information provided by
+the modeling checkers mentioned:
+  * :ref:`alpha-cplusplus-InvalidatedIterator`
+  * :ref:`alpha-cplusplus-IteratorRange`
+  * :ref:`alpha-cplusplus-MismatchedIterator`
+
+
+Definition of a container
+-------------------------
+
+According to ContainerModeling, a value ``c`` with type ``C`` is considered a
+container if either of the following holds:
+  * The expression ``c.begin()`` and ``c.end()`` are both valid expressions, and
+    return an `iterator
+    <https://en.cppreference.com/w/cpp/iterator#Iterator_categories>`_.
+    This should be detected by type C having member functions ``T C::begin()``
+    and ``T C::end()``, where T is an `iterator
+    <https://en.cppreference.com/w/cpp/iterator#Iterator_categories>`_.
+  * The expression ``begin(c)`` and ``end(c)`` are both valid expressions in a
+    given scope, and return an `iterator
+    <https://en.cppreference.com/w/cpp/iterator#Iterator_categories>`_.
+    This should be detected by checking the existence functions with the
+    corresponding names, and can either be user-defined free functions or
+    template specialization of the standard-defined ``template<typename T>
+    constexpr auto std::begin(T& t) -> decltype(t.begin())`` and
+    ``template<typename T> constexpr auto std::end(T& t) ->
+    decltype(t.end())`` function templates (see `std::begin
+    <https://en.cppreference.com/w/cpp/iterator/begin>`_ and `std::end
+    <https://en.cppreference.com/w/cpp/iterator/end>`_).
+
+Example containers in STL (with different `invalidation properties
+<https://en.cppreference.com/w/cpp/container#Iterator_invalidation>`_)
+ - std::array
+ - std::vector
+ - std::deque
+ - std::list
+ - std::forward_list
+
+Example of a custom container with member functions.
+
+.. code-block:: cpp
+
+  class C {
+    std::vector<int> v;
+  public:
+    using iterator = typename std::vector<int>::iterator;
+
+    iterator begin() { return v.begin(); }
+    iterator end() { return v.end(); }
+  };
+
+
+Example of a custom container with free functions.
+
+.. code-block:: cpp
+
+  class C {
+    std::vector<int> v;
+  public:
+    using iterator = typename std::vector<int>::iterator;
+  
+    friend iterator begin(C&);
+    friend iterator end(C&);
+  };
+
+  C::iterator begin(C& c) { return c.v.begin(); }
+  C::iterator end(C& c) { return c.v.end(); }
+
+Example of a custom container with std template specialization.
+
+.. code-block:: cpp
+
+  class C {
+    std::vector<int> v;
+    auto begin() { return v.begin(); }
+    auto end() { return v.end(); }
+  public:
+    template<typename T>
+    friend constexpr auto std::begin(T& t) -> decltype(t.begin());
+    template<typename T>
+    friend constexpr auto std::end(T& t) -> decltype(t.end());    
+  };
+
+Modeling of a container
+-------------------------
+
+A container is modeled if it has an associated ``MemRegion``, and this ``MemRegion``,
+or rather the ``const MemRegion*`` (and pointers to its subclasses), that is accessible
+by the ``MemRegionManager`` is what uniquely identifies a container. Temporary
+containers do not necessarily have a ``MemRegion``, these are not modeled.
+
+A container is tracked from the ``ProgramPoint``, where either ``begin`` or ``end``
+member function (or free function) is called. Abstract modeling uses ``SymbolRef``-s for the
+begin and end positions of a container. Any relations between the two positions are tracked
+in form of assumptions (inside ``ConstraintManager``).
+For specifying positions inside the container we use one of the following expressions
+  - ``<begin-symbol> + <concrete-value>`` for specifying a position relative to the beginning of the container.
+  - ``<end-symbol> - <concrete-value>`` for specifying a position relative to the end of the container.
+  - ``<conjured-symbol>`` for unknown positions inside the container.
+
+.. note ::
+  ``using clang::ento::SymbolRef = typedef const SymExpr *``
+
+Containers are modeled in the GDM by their region (MemRegion*) as their associated key,
+this region is immutable, it cannot change during the lifetime of the modeled object.
+The begin and end symbols are conjured and are completely unrelated to the region of
+the container. For each region we store the only the begin and end symbols, other properties
+are to be computed from these, and their relationships stored in the ContstraintManager.
+
+The symbolic-value categories (``SVal`` subclasses) encountered during container modeling
+are ``Loc`` (and subclasses, most prominently ``ConcreteInt`` and ``MemRegionVal``), as
+temporary containers are not modeled.
+
+Apart from identifying the container with a ``MemRegion``, in order to interact with
+iterator modeling, the symbolic begin and end positions of the container are also tracked.
+The size (and as a special case, whether the container is empty or not) are properties that
+should also be tracked.
+
+.. note::
+  Currently, the implementation does not handle size and emptiness tracking, but patches
+  can be found for them on Phabricator: `size <https://reviews.llvm.org/D76604>`_ and
+  `empty <https://reviews.llvm.org/D76590>`_.
+
+Implementation limitations
+--------------------------
+
+There are some limitations which must be circumvented in order to effectively implement
+container modeling. The problem of RValue/LValue (more precisely prvalue, xvalue, and
+lvalue see `value categories <https://en.cppreference.com/w/cpp/language/value_category>`_)
+modeling is not prominent is case containers alone, as no temporary objects are considered.
+However, this is an issue to be solved when it comes to modeling iterators.
+
+.. note::
+  Containers as RValues are currently not relevant, but size modeling could use them, as the
+  modeling of copy constructors are needed.
+  No constructors of containers are modeled, there is a WIP
+  `patch <https://reviews.llvm.org/D87388>`_ for default constructor.
+
+There is a limitation in the size of Symbols handled by ``the ConstraintManager``, namely that
+every offset is assumed to be at most ``typesize/4`` in size, otherwise the ``ConstraintManager``
+could not reorder expressions containing the the symbol. As an orthogonal issue symbol-symbol
+comparisons still cannot be handled properly if the ``ContstraintManager`` would also be able
+answer questions like: is symbol A less than symbol B (instead of just reporting the possible
+range of the values a symbol can have).
+
+.. note::
+  There is a WIP extension: if range of 2 symbols is disjunct and the max of first is less than
+  the min of the second, report less relation. `patch <https://reviews.llvm.org/D77792>`_
+  This patch would be needed to compare the sizes of containers.
+  If the containers don't overlap in memory, then this would provide a way to determine the size
+  differences. E.g.: If we could store ``a = b + 5`` even if the ranges of a and b is unknown,
+  reordering of this would produce: ``a - b = 5`` and this can have a range attached in the
+  abstract state.
+
+=================
+Iterator Modeling
+=================
+
+Definition of an iterator
+-------------------------
+
+A value with type T is possibly considered an iterator:
+If T is
+  - copy-constructible
+  - copy-assignable
+  - destructible
+  - can be incremented (both post and prefix unary plus-plus operator are defined)
+AND
+T meets the requirements of either input or output iterator
+  - in case of input:
+
+    - dereference operator with an rvalue return type is defined (both ``operator*`` and ``operator->``)
+    - equality/inequality comparable (both bool ``operator==`` and bool ``operator!=`` are defined)
+  - in case of output:
+
+    - dereference operator with an lvalue return type is defined (both ``operator*`` and ``operator->``)
+    - (note in this case no equality/inequality is required)
+
+The iterator modeling takes these into consideration only during the detection of iterators, and the
+iterator-category is not stored explicitly.
+
+Modeling of an iterator
+-----------------------
+
+The tracking of an iterator begins if a value is detected with the preceding properties *and* its name
+has 'iterator'/'iter'/'it' postfix. In special cases pointers are also treated as iterators, namely,
+if they are results of ``begin`` or ``end`` member functions or free functions.
+
+The following heuristics are also in place to limit the tracking of many unrelated iterators:
+ - only track an iterator if its generating expression has a tracked container (and this will be the parent container of the returned iterator)
+ - only track an iterator if its generating expression is a function call which has at least 1 argument, that is an already tracked iterator (and the first iterator parameter's container will be the parent container of the returned iterator)
+If either of these heuristics matches the tracking of iterator should be skipped.
+
+Iterators are modeled in the GDM with 2 kinds of keys:
+  - Region (``const MemRegion*``)
+  - Symbol (``SymbolRef``)
+There are therefore 2 maps which model iterators, one is called the RegionMap, the other is the SymbolMap.
+
+For each iterator the following information is stored:
+  - a flag signifying the validity of the iterator
+  - a reference to the container it belongs to (parent container)
+  - the offset of this iterator inside the (parent container)
+
+The iterator offset is abstract, no ``MemRegionVal`` is associated with iterator offsets.
+
+  - a single conjured symbol (SymbolVal)
+  - a conjured symbol (SymbolVal) + a number (``ConcreteInt``) (This for is useful for reordering)
+
+Functions like find (when alpha.cplusplus.STLAlgorithmModeling is enabled) handle cases where an
+element is found, and a case where it is not
+  - found case: ``return it >= 1.parameter`` AND ``it < 2.parameter`` constraints are applied
+  - not-found case: ``it == 2.parameter`` constraint is applied
+Assert should be used if the element is KNOWN to be in the container (invariant property of the usage)
+
+There are currently 2 main categories of iterators, one is implemented with pointers, the other is via class
+instances. The goal is to handle iterators in a uniform fashion for the 2 iterator implementations.
+
+Example of a pointer iterator implementation (conceptionally no difference between inline and non-inline modes)
+
+.. code-block:: cpp
+
+  struct Cont {
+    using iterator = int*;
+    int v[8];
+    iterator end_pos;
+  
+    iterator begin() {
+      return v;
+    }
+  
+    iterator end() {
+      return end_pos;
+    }
+  
+    // methods handling container operations
+  }
+
+A detailed example of modeling a container and its iterators.
+
+.. code-block:: cpp
+
+  void f() { 
+    Cont c;              // no modeling should be done here
+
+    int* it = c.begin(); // container-modeling begins by tracking c as a container of type Cont
+                         // begin() member function call triggers the modeling
+                         // iterator-modeling also begins by tracking the value of c.begin()
+                         // as an iterator
+                         // we check if the value has the necessary iterator-properties
+                         // ExprEngine handles the binding of RValue c.begin() to the value of it.
+
+    ++it;                // it is a tracked iterator, operator++ is a relevant operation
+                         // ExprEngine creates new ElementRegion for the incremented iterator,
+                         // and binds this (RValue) SVal to variable it (LValue)
+  
+    if (!(it == c.end())) { // c.end() triggers container-modeling again, producing an iterator
+                            // position, noting it in the modeling structure for c as end position
+                            // comparion operator== triggers a state-split, branch a assuming that
+                            // it position is equal to the newly created end position, branch b
+                            // has the opposite assumption
+      use(*it);             // Iterator modeling does not do anything with this dereference
+                            // operator-call, but checkers can use the information aggregated by
+                            // modeling to ensure that the iterator is valid in this case (because
+                            // of the if guarding it)
+    }
+  }
+
+
+Implementation limitations
+--------------------------
+
+Contrary to the container-modeling, not only lvalue iterators are tracked. This is the reason
+why 2 different keys are used in the GDM for iterators. An lvalue iterator has a Region
+(``const MemRegion*``) and it is used if available. If no Region is found for an iterator value
+then a Symbol is used (``SymbolRef``).
+
+In the case of pointer iterators (where std::is_pointer<T>::value is true for the type T of the iterator),
+the modeling of the symbolic value is simpler. The lifetime of such values is simple to model,
+there is no need for constructors, destructors and copy-elision rules to be taken into consideration.
+
+Example of a pointer iterator.
+
+.. code-block:: cpp
+
+  int * it = cont.begin();
+  int * it = it + 1 + 1;
+  // SVal of it + 1 subexpression: NonLoc kind (designates an RValue)
+
+
+The operators of such iterators are built-in operators.
+
+Iterators implemented as pointer live generally in the SymbolMap (the map containing ``SymbolRef``-s as
+opposed to the map containing the ``const MemRegion*``-s), and can not be only represented with LValues (and
+consequently inside the RegionMap), as tracking the value of symbolic offset of an iterator must handle
+expressions where there may only be temporaries with no LValues associated with them.
+
+We cannot consistently track only LValues (``MemRegionVal``-s) or only ``RValues`` (``SymbolVal`` or ``LazyCompoundVal``),
+because pointer iterators have only Rvalues that always identifies them (across multiple subexpressions),
+class instance variables only have Lvalues for this role. SymbolMap always has iterator values that are RValues.
+RegionMap can have iterator values which are LVals but also values which are RValues.
+
+In case of class instance implemented iterators, the operations are ``CXXOperatorCallExpr``-s (not built-in
+operators). Also sometimes RValues of such instances are modeled as ``LazyCompoundVal`` ``SVal``-s, but can
+also appear as ``MemRegionVal`` or ``SymbolVal`` (if ``std-container-inlining`` analyzer option is off).
+
+The modeling of special container-related member functions can be found in ``Iterator.cpp``, and
+algorithm modeling in ``STLAlgorithmModeling.cpp``.
+
+The semantic difference between the 2 iterator implementation with respect to their ``SVals`` is
+that accessing a pointers ``SVal`` always return reference to a Region (no way to be a symbol, SymRegion),
+but in case if a class instance iterator can be a symbol (SymExpr).
+
+Example of a class instance iterator.
+
+.. code-block:: cpp
+
+  class cont_it {...};
+  cont_it it = cont.begin();
+  cont_it it = it + 1 + 1;
+  // SVal of it + 1 subexpression: Loc kind (designates an RValue)
+
+Example of a container which has iterators as elements.
+
+.. code-block:: cpp
+
+  using it_t = int*;
+
+  std::vector<it_t> v;
+  vector_it it = v.begin(); // container modeling detects v as container
+  it = it + 1;
+
+.. note::
+  This is the main issue right now, using these two maps in a more organized fashion, or providing a
+  straightforward way to manage the symbolic values of iterators is essential to effectively progress with the 
+  implementation. Also the case of nested iterator modeling (where there is a container which has iterator
+  as elements) the iterators that iterate a container and the iterators contained in the said container must be
+  distinguished).
+  The question is what to track in the GDM, and how to identify the correct iterator value.
+  
+  3 options have been outlined so far.
+
+  **Option 1**: use only RValues (``SymbolRef``-s) as keys
+  Class instance iterators (possibly with ``LazyCompoundVal``) can not be used as keys as they are now, because
+  they do not satisfy map key criteria (this could be maybe solved by defining an ordering on them), but the
+  main issue is that even though they wrap a SymbolVal, this wrapping is an implementation detail and should not
+  be relied upon, also meaning they should not be unwrapped.
+  Pointer iterators do not have an issue with this option.
+
+  **Option 2**: use only LValues (``const MemRegion*``) as keys
+  Class instance iterators that evaluate as a result of multiple subexpressions have RValues and these immediate
+  RValues break a cheain of value propagation. lazyCompoundVal should not be used as keys in a map (every
+  operation results in a temporary which can be tracked).
+  Pointer iterators that evaluate as a result of multiple subexpressions have RValues and these immediate RValues break
+  the chain of value propagation. lazyCompoundVal should not be used as keys in a map (every operation results in a
+  temporary which can be tracked). no temporaries are created during the evaluation of expressions (i + 1 + 2) there
+  is no intermediate lvalue for i + 1.
+
+  **Option  3**: In case of pointer iterators a solution could be to only track the RValues, and in the case of class
+  instance iterators use both RValues and LValues, and this way we track the explicit nature of being pointer based
+  or being class instance based.
+  The drawback of this approach is that the implementation for modeling the 2 families of iterators are harder to
+  share, which either leads to duplication or an extra layer of abstraction.
+  The ability of LazyCompoundVal to take the role of the key inside the map (ordering or hashing) should still be
+  solved in this case (as in Option 1).
+
+
+
+