ITK/Proposals:Concept Checking

Introduction

The generic nature of ITK has the positive effect of facilitating code reuse by allowing algorithms to be instantiated over different types of images. Even images that ITK developers may have never tried before. One of the drawbacks of such generality is that users may attempt to use filters on image types for which they are not suitable. These attempts may result in one of the following unpleasant experiences:

1. The code will not compile and will produce error messages with more than ten lines of references to templated code
2. The code may compile but the program may crash at run time.
3. The code may run but the output may not be correct.

These types of failures are directly associated to three different levels of conceptual requirements in the algorithm that the user is attempting to use. We refer to these levels as

1. Programming level
2. Mathematical level
3. Semantic level

Programming Level

The programming level refers to the API functionalities that a pixel type or an image type must provide in order to match the expectations of a filter or algorithm. In practical terms it comes down to the functions and operations that the filter invokes on the image type and or the pixel type. For example, if the filter perfoms additions between pixel values, then this requires the pixel type to provide an addition operator. These requirements can be tested at compile time, and are the object of the Concept Checking implementation described in this page.

Mathematical Level

The mathematical level is more abstract than the programming level and refers to the consitency of operations performed over types. For example, the fact that pixel types can be sorted by using a "<" operator, require at the programming level that the pixel type provides an "operator<()" method. However, at the mathematical level it also requires that a number of logical consistency rules are satisfied, such as:

1. if ( a > b ) is true, then ( b > a ) is false
2. if ( a > b ) and ( b > c ) then ( a > c )

The programming level cannot verify the validity of the conditions above without incurring in a very expensive effort. It is not reasonable to subject users to the price of that effort when they are instantiating filters over commonly used image types. This type of conditions can simply be documented in the filter by placing statements such as

        The pixel type should be "Sortable".

Users would have to use their knowledge of the pixel type that they are using in order to "manually" confirm that the pixel type fits the requirements of the filter.

When the user provides a type that satisfies the programming level but fails the mathematical level, the code will compile, but will fail at run time, maybe by producing segmentation faults, memory overrides, infinite loops or triggering exceptions.

Semantic Level

The semantic level is more abstract than the mathematical level, and refers to the interpretation or the meaning of the types in the context of an application. This level cannot be verified at the programming level, and cannot be documented because it pertains to the almost infinite combinations of possible uses of an image type, which of course, cannot be anticipated by developers.

The semantic level will refer to matters such as using a Vector type for representing a sampling of the spectrum of a microscopy image. Even though at first sight, a Vector may seem to be the appropriate mathematical type for representing this concept, a more detailed analysis will reveal that the spectrum of absorption of light must not have any negative numbers, and that therefore the operations of additions and subtraction have to be defined in a way different from the standard mathematical conception of Vector addition and subtraction.

When users take classes that have a valid mathematical foundation that is appropriate for a specific algorithm, but use them for a semantic interpretation that is not appropriate, then the results produced by the filter or algorithm will be mathematically valid, but their interpretation in the semantical context will be erroneous.

For example, if we take a microscope and using pass-band optical filters we acquire color images in 10 different color bands, then group those individual images n the form of an image of Vectors where every pixel is a vector of 10 components; we can claim that performing operations such as mean and variance are valid in the semantical context of spectral images, but we should not take this vector image and use it as a deformation field in a WarpImageFilter because despite the fact that the Vector pixel type is appropriate for that mathematical operation, the content of the image is not representing the concept of a deformation field.

The semantic level is certainly the most challenging of the three levels of conceptual checking, and it should probably be managed by discussions in the community forums such as the Insight Journal and the ITK users and developers mailing lists.

The Programming Level & C++ Templates

One of the characteristics of Generic Programming is that classes and methods can be instantiated over any type. This freedom however, is still restricted by a number of characteristics that those types must satisfy in order to work properly with the classes that they are instantiating.

For example, a templated class has template parameter T and internally perform addition operations on that type, will require T to have an operator+() defined, or to be a basic type such as int, float or char, for which such operator is already defined in the language.

When a templated class is instantiated over a type that do no satisfy the requirement, most compilers will generate error messages that are difficult to interpret. It is then desirable to have a mechanism for making those messages simpler or at least easier to understand for the users of the software.

Concept checking is an approach by which language structures are introduced in templated classes in order to test early for the expected characteristics of a template parameter. When a user instantiate this templated class over a type that does not satisfy the concept, then the compiler will generate an error message that is easier to interpret, and that will convey to the user the message that the type is not an appropriate template argument for this class.

Macro Implementation

Implementation Mechanism

The implementation mechanism of concept checking in ITK is inspired on the method used by the BOOST library

http://www.boost.org/libs/concept_check/concept_check.htm

This is based in a three stages process

1. Auxiliary classes that exercise a concept. ("Constraints")
2. Auxiliary classes that instantiate the Checkers. ("Instantiators")
3. Macros that name the concept and insert the Instantiators.

Constraints

A set of Constraints is defined for capturing the common requirements of pixel types and value types. Such constraints include features like, having an assignment operator, being castable to double, having addition operators, having multiplication operators and so on.

Instantiators

The Instantiators provide a specific naming for the concept being checked and for triggering the evaluation of the concept at compiling time.

Macro Invocations

The Macros are the final element that is inserted on every specific ITK class in order to indicate the concepts that must be checked in its template arguments. It is common for an ITK class to have multiple concepts in its header.

Example

In order to illustrate this mechanism, a simple concept checking sequence is presented here, for the case of multiplication. This is a case in which a templated class of type

  template <typename T>
  class ImageFilter< T >

internally performs multiplication operations with variables of type "T".

The Constraint

The Constraint class that checks for this multiplication concept is the following

 struct Constraints
 {
   void constraints()
     {
     a = static_cast<T3>(b * c);
     const_constraints(b, c);
     }
   void const_constraints(const T1& d, const T2& e)
     {
     a = static_cast<T3>(d * e);
     }
   T3 a;  
   T1 b;
   T2 c;
  };

This class checks that a variable of type T1 can be multiplied by a variable of type T2 and the result be assigned to a variable of Type T3.

The Instantiator

This constraint is then embeded into a structure whose name clearly and distinctively identifies the concept. In the case of multiplication this structure is named: "MultiplyOperator", and its code looks like:

  /** Concept requiring T to have operator * in the form T1 op T2 = T3. */
  template <typename T1, typename T2=T1, typename T3=T1>
  struct MultiplyOperator
  {
    struct Constraints
    {
     ...
    };

    itkConceptConstraintsMacro();
  };

Naming of this class is critical in the working of Concept Checking because that name is the first word that will appear in the compiler error message if a user instantiate the ITK filter with a type that does not satisfy the requirement of having a multiplication operator.

The Macro in the Filter

In order to specify that a particular templated class in ITK requires the multiplicative operator to be available for the pixel type, the followin code is inserted in the header of that ITK templated class:

 itkConceptMacro(Input1Input2OutputMultiplyOperatorCheck,
   (Concept::MultiplyOperator<typename TInputImage1::PixelType,
                              typename TInputImage2::PixelType,
                              typename TOutputImage::PixelType>));

This macro will be expanded by the C preprocessor into a group of lines of code that declare the Instantiator and therefore forces the compiler to evaluate the concept in question.

Usage

The following code attempts to use a Multiplication filter with an image whose pixel type doesn't have a product operator defined. This attempt will result in a compiler error that will inform the user about the requirements imposed on the pixel type by this particular ITK filter

  #include "itkImage.h"
  #include "itkMultiplyImageFilter.h"
  class K
  {
  };
  int main()
  {
  typedef itk::Image< K, 2 > ImageType;
  typedef itk::MultiplyImageFilter<
                             ImageType,
                             ImageType,
                             ImageType > FilterType;
  FilterType::Pointer filter = FilterType::New();
  return 0;
  }

The Compiler Error Message

The error message produced by the code above, in GCC 3.4 is the following:

 /home/ibanez/src/Insight/Code/Common/itkConceptChecking.h: In member function 
   `void itk::Concept::MultiplyOperator<T1, T2, T3>::Constraints::constraints()[with T1 = K, T2 = K, T3 = K]':
 /home/ibanez/src/Insight/Code/Common/itkConceptChecking.h:339:   
  instantiated from `itk::Concept::MultiplyOperator<K, K, K>'
 /home/ibanez/src/Insight/Code/BasicFilters/itkMultiplyImageFilter.h:81:   
  instantiated from `itk::MultiplyImageFilter<main()::ImageType, main()::ImageType, main()::ImageType>'
 /home/ibanez/src/UsersITK/LuisIbanez/ConceptChecker.cxx:19:   
  instantiated from here
 /home/ibanez/src/Insight/Code/Common/itkConceptChecking.h:327: 
  error: no match for 'operator*' in '
  ((itk::Concept::MultiplyOperator<K, K, K>::Constraints*)this)->
  itk::Concept::MultiplyOperator<K, K, K>::Constraints::b * 
((itk::Concept::MultiplyOperator<K, K, K>::Constraints*)this)->
  itk::Concept::MultiplyOperator<K, K, K>::Constraints::c'

The first line of the message refers to the "ConceptChecking" file, and list the concept that is being violated, in this case "Concept::MultiplyOperator<T1, T2, T3>"

List of Concepts

The following table list all the concepts for which ITK is checking in its filters.

For full implementation detail please see the file

      Insight/Code/Common/itkConceptChecking.h.

Current Concepts

Index	Concept	Description
1	DefaultConstructible	Concept requiring T to have a default constructor.
2	CopyConstructible	Concept requiring T to have a copy constructor.
3	Convertible	Concept requiring T1 to be convertible to T2.
4	Assignable	Concept requiring T to have operator =.
5	LessThanComparable	Concept requiring T1 to have operators < and <= with a right-hand operator of type T2.
6	EqualityComparable	Concept requiring T1 to have operators == and != with a right-hand operator of type T2.
7	Comparable	Concept requiring T1 to have operators <, >, <=, >=, ==, != with a right-hand operator of type T2.
8	AdditiveOperators	Concept requiring T1 to have operators +, -, +=, -= in the form T3 = T1 op T2.
9	MultiplyOperator	Concept requiring T1 to have operator * in the form T3 = T1 op T2.
10	Signed	Concept requiring T to be signed.
11	SameType	Concept requiring T1 and T2 to be the same type.
12	SameDimension	Concept requiring D1 and D2 to be the same dimension.
13	GreaterThanComparable	Concept requiring T1 to have operators > and >= with a right-hand operator of type T2.
14	LogicalOperators	Concept requiring T1 to have operators &, I, ^, &=, I=, ^= in the form T3 = T1 op T2.
15	NotOperator	Concept requiring T to have operator !.
16	IncrementDecrementOperators	Concept requiring T to have operators ++ and --.
17	OStreamWritable	Concept requiring T to be writable to an ostream.
18	HasNumericTraits	Concept requiring T to have NumericTraits.
19	HasPixelTraits	Concept requiring T to have PixelTraits.
20	HasJoinTraits	Concept requiring T to have JoinTraits.
21	SameDimensionOrMinusOne	Concept requiring D1 and D2 to be the same dimension or D2-1 = D2.
22	MultiplyAndAssignOperator	Concept requiring T1 to have operator *= in the form T2 op= T1.
23	DivisionOperators	Concept requiring T1 to have operators / and /= in the form T3 = T1 op T2.
24	IsInteger	Concept requiring T to be inteter.
25	IsNonInteger	Concept requiring T to be non-inteter.
26	IsFloatingPoint	Concept requiring T to be floating point.
27	IsFixedPoint	Concept requiring T to be fixed point.

Proposed concept additions

Additional concepts for requiring integer or noninteger datatypes should be added to the toolkit. NumericTraits defines static boolean constants

• is_bounded
• is_exact
• is_iec559 (???)
• is_integer
• is_modulo
• is_signed
• is_specialized
• tinyness_before

These traits can be used to define concepts in a manner similar to the Signed concept. We should consider separating the concepts of integer, non-integer, floating point so that we can expand our native datatypes to include a fixed point representation.

The concepts below are poorly named. We should not have a concept called Integer since a user could confuse the name of the concept with a datatype. Unfortunately, none of the current concepts have the word concept in their name. We could follow NumericTraits, and make the new concepts called IsInteger.

Index	Concept	Description
13	Integer	Concept requiring T to be an integer.
14	Noninteger	Concept requiring T to be noninteger (floating point or fixed point).
15	FloatingPoint	Concept requiring T to be floating point (not integer and not fixed point)
16	FixedPoint	Concept requiring T to be an ITK fixed point representation (not integer and not floating point)

Integration into Filters

The concepts listed in the table above were introduced in ITK filters.

Please follow the link below for a detailed list of filters and their associated concepts.

List of Filters

Enabling Concept Checking

During the experimental phase of implementing concept checking, the code was conditionally compiled under control of the CMake configuration. This prevented to break builds of many users during the early stages of the concept checking implementation.

In order to enable concept checking, the ITK user must do the following:

• Rerun CMake in its ITK configuration
• Go to the Advanced options
• Select ITK_USE_CONCEPT_CHECKING

This settings will be captured by the user projects that use ITK, and will be actively checking for the concepts every time that the user recompiles her/his project.

Limitations

The Concept Checking was not supported by the Borland compiler. This option is therefore disabled in this specific compiler.

---

ITK: [Welcome | Site Map]