Andrey Karpov

Aug 06 2009

PVS-Studio and testing Loki

In PVS-Studio 3.10, support parsing of complex constructions based on templates will be improved what will allow you to efficiently search errors even in the code of those programs which use complex template libraries such as Loki. But let's start with the beginning.

Not so long ago, when our product for testing 64-bit code was called Viva64, we were addressed by the manager of the open library Loki* with an offer to check compatibility of the library with 64-bit Windows systems. For that moment the Windows-version of this library was represented only in 32-bit mode. We agreed and set about the new task bating our breath. The point is that compiler developers often use Loki library as a perfect testing model allowing you to estimate compatibility with C++ standard. We were not sure that we would be lucky. So, we consider it a great achievement that our analyzer did not hang on it, did not crash with a critical error and was able to provide normal diagnosing.

But the results of the diagnosing showed a great disadvantage of Viva64 analyzer: it cannot instantiate templates and cannot detect many errors in them. Here is an example to make it clear:

01 template <class T, class M>
02 class TemplateClass
03 {
04 public:
05   char m_char;
06   T *m_t;
07   M m_m;
08   T Get(int index) { return m_t[index]; }
09   void Set(int value) { m_t[m_m] = value; }
10 };
11
12 TemplateClass <char, int> A;

Only one potential error in line 8 was detected. In this line a variable of int type is used as an array index and it is potentially dangerous when working with large data arrays. When diagnosing this error it does not matter what relates to T type. But two other errors we will describe further have never been detected by Viva64 analyzer. One can say that Viva64 checks the code of templates rather superficially and detects only those errors which are present in it independently from the arguments with which an array will be instantiated.

This disadvantage arises from OpenCxx library on whose basis VivaCore library has been created being the base of Viva64 analyzer. The reason is very simple - OpenCxx simply cannot instantiate templates. It looks rather strange for it restricts abilities of the library. But we have a suspicion that there had been support of template instantiating in OpenCxx library but then was deliberately removed before the project became open and accessible. Some strange stubs and near-empty classes relating to template processing are an indirect evidence of this.

We have known about this drawback and its effects on diagnostics for a long time but it was Loki library that urged us to engage into implementing a mechanism for testing instantiated templates. We have created a mechanism which instantiates a template and analyzes it again on the basis of new knowledge about types. Implementation is not very good yet and needs to be improved but it already allows us to detect many new errors. Let's discuss it on the basis of the example given above.

After implementing the instantiating mechanism the analyzer immediately gave three diagnostic messages:

Line 3: error V401: Instantiate TemplateClass <char, int>: The structure's size can be decreased via changing the fields' order. The size can be reduced from 24 to 16 bytes.

Line 8: error V108: Incorrect index type for "m_t". Use memsize type instead.

Line 9: error V108: Instantiate TemplateClass <char, int> : Incorrect index type for "m_t". Use memsize type instead.

Having met the line "TemplateClass <char, int> A;" the analyzer instantiated this template and analyzed it possessing the information about T and M types. As a result, it warned that the data structure in the class is non-optimal (V401) and the size of this class in a 64-bit system can be reduced from 24 bytes to 16. For this we need to rearrange the members of the class. Pay attention that this diagnostics is possible only when you know what types the members have. For there can be no warning if, for example, m_m members have size_t type. In this case field rearranging will not help reduce the class' size.

The error in line 8 is detected as before because knowledge about T and M types does not matter here.

The last error in line 9 also relates to indexing of the array with the use of a variable of int type. Here information about M type does play an important role and is used by the analyzer.

The improvements made enabled us to perform fuller testing of Loki library. You may learn more about this work in the article "64-bit Loki" at which we are working together with the library's manager Rich Sposato.

Analysis of Loki has been performed by a special research version of Viva64. But now we decided to integrate the new abilities into the new version PVS-Studio 3.10 ** which will be released in the near future. Users will be able to use a new option DoTemplateInstantiate which enables the mode of deep template analysis.

*Note. Loki library for C++ programming language was written by Andrei Alexandrescu as part of the book "Modern C++ Design: Generic Programming and Design Patterns Applied". The library is built on template meta-programming and actively uses C++ abilities for generalized programming. (Wikipedia. Loki.)

**Note. PVS-Studio is a program product uniting and extending abilities of Viva64 and VivaMP static analyzers. Numbering of PVS-Studio begins with the version 3.00 to emphasize that this is evolution of the existing tools. In 3.00 version we did not hurry to implement template instantiating support but decided to introduce this ability in PVS-Studio 3.10.

0

0

0

0

SHARE

We can email you a selection of our best articles once a month