C language concept domain check
Dr. Dobb's Journal June 2001
Source: http://hyper.vcsun.org/hypernews/rlingard/get/cs380f2002/sharing/201.html
Use the template for better practice.
.
(WQ Note: This article can see "More Exceptional C " Item 4.)
-------------------------------------------------- ------------------------------
The type of generic programming manifestation of C is the type of abstract data type, which is also the term "Concept)" in the documentation of SGI STL (see "Generic Programming and the STL", Mhaustern, Addison- Wesley, 1999, SGI implementation in the standard template library, http: // www.sgi.com/technology/stl/). Unfortunately, the flexibility provided by the template is to sacrifice the security of the interface. In this article, we will introduce a technique to re-introducing interface security into template functions.
Look at the Example 1 (a) (WQ Note: In the version I found, these examples of the code are missing). If a function acts on an integer STACK container, you can use an object-oriented way to describe this requirement for a Stack type: uses an abstract base class. The subsequent function call foo (y) is only established when the parameter Y is derived from STACK. This ensures that the type y has at least the Push () and POP () member functions, so that the call to them can be guaranteed to be well defined in the foo ().
Using templates, interface security becomes very vague. For example, it is assumed that there is an example 1 (b) such a function template. In this case, the compiler allows any type of object to be passed as a parameter to bar (), and it is not in turn it is a Stack object (that is, there is a PUSH () and POP () member functions). If an incorrect type is used, compiling errors will occur. However, the error is not to be captured where the BAR () is called, but is somewhere in Bar (). You need a mechanism to make the template function to provide interface security as the abstract base class method. We can do this with some new C customary methods to specify and check the needs of the template parameters. We use the term "concept" to indicate the demand set, and our method is "Concept Checking".
A group of people working in SGI and THE UNIVERSITY OF NOTRE DAME began research in conceptual domain checking mechanisms a year ago, and produced now in the conceptual domain check in the SGI STL release. This work is further developed (see "Concept Checking: Binding Parametric Polymorphism In C ", by J. Siek and A. Lumsdaine, First Workshop ON C Template Programming, October 2000, (WQ Note: http://www.osl .iu.edu / ~ jsiek / concept_checking.pdf)) and presenting available forms such as Boost Concept Checking Library (http: // www .boost.org / libs / concept_check / concept_check.htm). In this article, we will involve two complementary faces of conceptual domain checks: conceptual domain checks and conceptual domain coverage (Concept covers). The conceptual domain check is handled by the concept of the concept, confirming that the template parameters meet these needs, and provides appropriate error messages when the user provides the template parameters that do not satisfy the demand. The demand for the conceptual domain coverage confirmation template is effective; that is, check all the ways to use template parameters to confirm that there is no unnecessary demand. Conceptual domain
The concept domain is a demand set (effective expression, related types, semantic constant, complexity assurance, etc. Valid Expressions, Associated Types, Semantic Invariants, Complexity Guarantees), one type must be met to be used as generic operation Parameters. However, there is no explicit expression mechanism for the conceptual domain in the C language, and the template-shaped parameter is only a placeholder, and any constraint cannot be expressed. Based on habits, template-shaped parameters will be given a name that meets conceptual domain needs, but the C compiler does not force this to meet this when template-shaped reference is set to actual types.
Naturally, if the generic operation is called, the type does not satisfy the grammar requirements of the concept domain, and a compile period error will happen. However, this error will not be reflected as the type of not satisfied with the concept domain. Errors may occur on expressions that will be invalid for this type, or when a assigned correlation type is not available. Error messages generated usually do not provide useful information and difficult to understand.
Mechanisms forces "conceptual domain safety" are required during instantiation. Boost Concept Checking Library (BCCL) uses standard C language structures to force the concept domain and provide more information amount error messages when not satisfied. The techniques described herein only relate to grammatical needs (effective expressions and related types) of the concept domain, do not involve language constant or complexity guarantees (although this is an active topic of our research team).
Example expansion
It happened to all of us: using a small error in the standard library (SL) generic algorithm, the compiler produces a number of incorrect error messages. Of course, this problem is not SL unique, it affects all template classes and template functions. Example 2 illustrates a such error. It calls the generic algorithm std :: stable_sort () in SL, applies it to the list.
Compiling errors by GNU C compiler compile. For this example, the fundamental error lies in std :: list :: Iterator does not satisfy the concept of randomaccessItemrator. List's iTerator is just two-way selection, and cannot be randomly access (like std :: Vector :: Iterator). Unfortunately, there is no thing in the error message to point out this. In the view of the C programmers who have experienced experience in the template library, the error may be obvious. However, no matter what, based on several reasons, this error message can be considered to be difficult to understand. l Location error. The 5th line of Example 2 was not mentioned by the error message, even GNU C printed the 4-layer call stack.
l
l There is no text connection between the error message and std :: stable_sort () and the RandomAccessFteerator.
l The error message is too long, lists the functions inside the SL, and they are not users who do not (and should not) know or care.
l Since so many library internal functions are listed, the user is easy to inject the error is from the library itself, not their code.
Example 4 illustrates what you expect from valuable information (in fact, this is also generated by BCCL). This information makes up for the shortcomings of the previous error information.
l The location of the error occurred in the error message.
l The information clearly refers to the concept of the user who can find in the SL document (RandomaccessItemrator).
l The error message is very short and does not mention the internal functions of the STL.
l Check.hpp and constraints appearing in the error message, remind the user error located in the user code, not the template implementation.
Conceptual domain check class
In order to check a concept, we use a special class (a conceptual domain check class) to ensure a (or a group) given a given type to meet a given concept. An example of a concept domain check class from BCCL is EqualityComparableConcept, corresponding to the EqualityComparable demand described in C standard 20.1.1 and the EqualityComparable concept in the SGI STL document.
Template
Struct EqualityComparableConcept;
Template parameter t is the type to be checked. That is, the purpose of EqualityComparableConcept is to ensure the given template parameter T, meet the concept of equalitycomparable. Each conceptual domain check class has a member function constraints (), which contains a valid expression of the concept domain. In order to check if a type is equalitycomparable, we need to instantiate the concept domain check class with this type and find a way to make the compiler to compile the constraints () function without having to execute it. BCCL defines two tools to make it easy: function_requires () and boost_class_requires. The function_requires () function can be used inside the function, and Boost_ Class_Requires can be used in the category.
Function_Requires () Function There is no parameters, but there is a template parameter for use in the conceptual domain check class. This means that an explicit template parameter must be given when instantiated conceptual domain check classes; see Listing One (a). After inserting this concept domain check, if the class foo does not satisfy EqualityComparable (no == and! = Operation), Function_Requires () will capture errors at the beginning, rather than let the error occur in somewhere within the template function. Boost_class_requires macros can be used in a class definition to check if a type meets a concept; see Listing One (b).
Conceptual domain check application
A good concept domain checkprou will insert function_requires () in the start of std :: stable_sort () to ensure that the template parameters meet the RandomaccessItemrator. Also, std :: stable_sort () requires that Iterators pointing to the type of LessthanComparable, so you should also use function_requires () to check this; see Listing TWO (a).
As an example using Boost_Class_Requires, let's take a look at the conceptual domain check on the std :: vector. A requirement is that the element type must be Assignable. You can check the boost_class_requires inserting boost_class_requires at Std :: Vector, see Listing TWO (B).
Although conceptual domain checks are designed to be used by power-to-fling libraries, they are equally useful for end users. Sometimes you are not sure if a type meets a specific concept. By creating a small program, using function_requires () for the type and concepts of the problem domain, it is easy to check this. BCCL file STL_CONCEPT_CHECKS.CPP provides an example of conceptual inspection of the SL container.
achieve
Ideally, we want to capture (and pointed out) the conceptual domain violations in the instantiated point. As mentioned by Bjarne Stroustrup "C Language, 1994), the error can be captured by all the needs of the Exercise function template. How to properly exercise these needs (especially effective expressions), which is subtle because we want the code to be compiled but not executed. Our approach is to exercise in a stand-alone function and assign this function to a function pointer. This way, the compiler instantiates the function but doesn't really call it. In addition, optimization compile time will assign the value as a dead code (although the value of the operation is negligible). It is necessary to consider compiling the compiler to compile it in the first place where the constraint function is first appearing, which will cause the function pointer technology to fail. However, this is unlikely because removed unnecessary code and functions are usually done in the post-compilation. We successfully utilize function pointer techniques on GNU C , Microsoft Visual C and EDG-based compilers (Kai C , SGI MIPSPRO). Listing Four shows how to use this technology to the std :: stable_sort () function.
Usually there is a large group of needs that need to be checked, and for the implementation of the library, it is also very troublesome to write a constraint function such as stable_sort_constrainst () for each public function. In fact, we can aggregate the corresponding effective expressions based on the conceptual domain. For each concept domain, a conceptual domain check class template is defined, and the template parameters are the type being checked. Such a class contains a constraints () member function, which is a valid expression of the concept of concept. Objects used inside the constraints () function, such as N and I, are declared as a data member of the conceptual domain check class; see Listing Five. You can still use a function pointer system to cause instantiation constraints () functions, but now is a member function pointer. In order to simplify the implementation of the library, we put the member function pointer system package into the function function_requires (). Listing Six (a) shows how to use function_requires () to ensure that the selection is a RandomaccessItemrator. The definition of function_requires () is as follows; Concept is an instantiated conceptual domain check class. We assume the address of the constraints () member function to the function pointer X, which results in instantiation of the constraints () function and checks the valid expression of the concept domain. The X is then passed to the ignore_unused_variable_warning () function and puts this ingeneration into a loop to prevent DO-WHILE conflicts; see Listing Six (B).
To check the type parameters of the class template, we provide a boost_class_requirs macro that can be used for a class definition body (and function_requires () can only be used in the functional body). This macro declares a nested type template, and its template parameters are a function pointer. Then use this nested class with a TypeDef, see Listing Six (C), will point to the constructs () function type pointer as the template parameter. We use Type_var and Concept and TypeDef to avoid name conflicts in nested classes.
In addition, there are various versions of Boost_Class_Requires that accept more parameters to handle the concepts involving two and more types of interactions. BOOST_CLASS_REQUIRES is not used for the implementation of the BCCL concept domain check class, because there are several compilers do not support function pointers as template parameters.
Construction concept inspection
As an example of creating a concept check class, look at how to create a corresponding check for the RandomaccessITerator concept. First of all, based on habits, our naming conceptual domain check class is a concept name plus "concept". Then, define a member function constraints () and a valid expression of the exercise concept. Function_Requires () expects the signature of this function such as Listing Three: No reference, no parameters, non-Const member functions.
The first part of Constraints () contains those needs, corresponds to the contact between RandomaccessITerator and its established concept: BidirectionAriterator and Lessthancomparable. We can use boost_class_requires instead of placing these needs in the category, however, boost_ class_requires uses a slightly unmatched C feature.
Then, we check if the category of the Iterator is std :: random_access_iterator or it is a class. Again, we write some code that meets the effective expression of the RandomaccessITerator concept, TypeDef can also be added to check the relevant types of the concept; see Listing Three. A easy error is that the expression used in the constraints () function is exceeded in the constraints () function when designing a conceptual domain check class. For example, it is easy to accidentally use the default constructor to create an object to express use (but not all concepts require a default constructor). This is the reason why Constraints () is written to a class. The object corresponding to the expression is declared as a class of data members. Because constraints () class templates are unregified, the default constructor of the concept domain check class is also unregified. Therefore, the default constructor of the data will also be unregified (C Language Standard Section 14.7.19)
Conceptual coverage and prototype
Like the component's input to select the minimum demand set (concept), the concept of checking the coverage of generic operations is equally important. That is, any possible user errors should be captured by the concept domain without missing, and the conceptual area coverage can be verified by using the prototype class. The prototype class is an accurate implementation of an interface related to a particular concept. The runtime behavior of prototype class is not important, and the function can be empty. Use the prototype class as the component's input, a simple test program can be compiled. If the program is compiled, it will be considered that the concept covers the component.
Listing seven displays prototypes for TrivialItemrator concepts. Ensure that prototypes are accurately matched to the concept. For example, the concept states that the return value of Operator * () must be converted to value_type. It does not force the return type must be T & or Const T &. The correct way is to create a (indirect) return type, which can be converted to T, such as the INPUT_PROXY used here. The validity of prototype testing is completely dependent on its precise matching, which must be checked by careful (manual) check.
The generic operation is usually tested with a large number of normal input types. For example, you might use the basic pointer type to Iterator for std :: stable_sort (). Although it is suitable for the test generic algorithm, it is suitable for ensuring that the conceptual area coverage is unable, because C types are never matching specific concepts, they usually provide the smallest demand for far exceeding a concept. Features. That is, even if the function template compiles with a given type, the conceptual needs may still fail to meet the real needs of the function. This is why it is important to compile the prototype class in addition to the typical input type test.
Listing EIGHT is taken from BCCL file STL_CONCEPT_COVERING.CPP, which shows how prototypes are used to check the requirements of std :: stable_sort (). In this case, it seems that the document of the SGI STL leaks the needs of CopyConstructible and Assignable (try removing those prototypes). The BOOST prototype is designed to be stacked. In this example, the value_type of the Iterator is combined by two prototypes. In Listing Eight, a template parameter named BSASE indicates where the layered prototype can be used.
Demand minimization
Decides how to aggregate the concept domain and determine which concept domain for each generic operation may be the most difficult (most important) in the process of building generic library. A guideline for this process is called "minimization of demand", minimizing the need to enter the input parameter to increase its reusability.
There is a natural opposite side in this statement. Depending on the definition, the input parameters must be used to be used to complete its tasks ("Components" refer to a function template or class template). The challenge is to achieve the same task with the least hypothetical (minimum requirement) to implement the components. Traditional abstract methods are directly associated with demand. The more abstract, the less demand. Therefore, the concept is that the abstract data type is simply present in the C template program. When designing concepts for certain issues, focusing on their purpose (that is, the requirements for the component inputs) are important. Based on the principle of minimization, this means we minimize concepts. The concept of the concept is a feature that is associated with the inherent semantic semantic semanties of the problem domain. For problem domains of basic containers, the requirements for one-way traverses are weaker than two-way traverses (the difference between ForwardITerator and BidirectionALATERATOR). The semantics can be easily seen from the difference between the specific data structure between the FORWARD ITERAL ITERATOR. For example, a one-way linked list will produce a data structure with Forward Iterator without a Bidirectional Iterator. In addition to this, only generic operations with forward selectors are quite different from generic operations using bidirectional selection. For this reason, it is important to classify the demand family into a well-defined concept. For example, the demand for selectors can be divided into six SL Iterator Concepts (Trivial, Input, Output, Forward, Bidirectional, and Random Access).
Boost concept domain check library
Boost's conceptual domain check library contains conceptual domain check classes for all concepts in the C standard library (more). In addition, other BOOST libraries also include conceptual domain check classes for their unique concepts. For example, the Boost Graph library contains checks for the information provided and the Property Map concept. We encourage you to check the conceptual domain to develop a generic operation. When implementing generic operations with existing concepts, you can simply reuse related conceptual domain checks. When introducing new concepts, you should develop the corresponding conceptual domain check for yourself and users.
Looking forward to the future
Design, implement and verify conceptual domain checks for C generic library, and must also be done by hand. As a result, this process takes time and (very likely) error. If some or all of the steps of this process can be automated, the implementation will be better.
The first step is to have a tool to static analysis of a class template or function template and record all kinds of expressions involving template parameters. Such tools can simplify the tasks covered by the verification concept domain. The second step will be moderately matched with the necessary expressions with the standard concept set (or the custom set of the library) to summarize the needs of the concept domain. This information can then be used in two ways. First, it can be used to generate a readable report used by the library document. Second, it can be used to provide valuable compilation error information without requiring manual insertion concept. Finally, we have found that there are too many work in generic programming. In addition to the C language, there are many ways to design a language that directly supports the concept.
thank
Thanks to Alexander Stepanov for originating the idea of using function pointers to trigger the instantiation of concept checking code Thanks also to Matthew Austern for establishing the concepts of the SGI STL;. Beman Dawes for managing the Boost review of the BCCL; and to all the Boost members for reviewing BCCL. Parts of this work were performed while Jeremy was interning at SGI, and Andrew was on sabbatical at Lawrence Berkeley National Lab. This work was partially funded by NSF grant ACI-9982205.Listing One
(a)
// in My Library:
Template
Void Some_function_template (T x)
{
Function_Requires
// ...
}
// in the user's code:
Class foo {
// ...
}
Int main () {
Foo F;
Some_Function_Template (f);
Return 0;
}
(b)
// in My Library:
Template
Struct Some_Class_Template
{
Boost_class_requires (t, equalitycomparableconcept);
// ...
}
// in the user's code:
Class foo {
// ...
}
Int main () {
Some_Class_Template
// ...
Return 0;
}
Listing TWO
(a)
Template
Void Stable_Sort (Randomaccessiter First, Randomaccessiter Last)
{
Function_requires
TypeDef Typename Std :: item_traits
Value_type value_type;
Function_Requires
...
}
(b)
Namespace std {
Template
Struct vector {
BOOST_CLASS_REQUIRES (T, AssignableConcept);
...
}
}
Listing three
Template
Struct RandomaccessITerConcept
{
Void constraints () {
Function_requires
Function_requires
Function_Requires TypeName Std :: item_traits Std :: random_access_iterator_tag>> (); i = n; i = i n; i = n i; I - = n; i = i - n; N = i - j; i [n]; } ITer a, b; ITer i, j; TypeName Std :: item_traits } } Listing Four Template Void Stable_Sort_Constraints (RandomaccessITerator i) { TypeName Std :: itemarator_traits :: DIFCERENCE_TYPE N; i = n; // EXERCISE The Requirements for randomaccessITerator ... } Template Void Stable_Sort (RandomaccessIitrator First, RandomaccessItemrator Last) { TypeDef void (* fptr_type) (RandomaccessItemrator); FPTR_TYPE X = & Stable_Sort_constraints; ... } Listing FIVE Template Struct randomaccessITerator_Concept { Void constraints () { i = n; ... } TypeName Std :: itemarator_traits :: DIFCERENCE_TYPE N; ITer i; ... } Listing Six (a) Template Void Stable_Sort (Iter First, Iter Last) { Function_Requires ... } (b) Template Void function_requires () { Void (Concept :: * x) () = boost_fptr concepter :: connection Ignore_unused_variable_warning (x); } (c) #define boost_class_requires (Type_var, Concept) / Typedef void (Concept Template Struct concept_checking _ ## type_var ## concept {}; / Typedef concept_checking _ ## type_var ## concept :: Constraints> / Concept_checking_typedef _ ## type_var ## concept Listing seven Template Struct Input_Proxy { Operator const t & () { Return static_object } } Template Class Trivial_Iterator_archettype { Typedef trivial_iterator_archtype self; PUBLIC: Trivial_iterator_archetype () {} Trivial_iterator_archetpe (const self) {} Self & Operator = (const self) {return * this;} Friend Bool Operator == (Const Self &, Const Self &) {Return True;} Friend Bool Operator! = (const self ") {return true;} Input_Proxy } Namespace std { Template Struct itrator_traits { Typedef t value_type; } } Listing elech { Typedef Less_than_comparable_archetpe < SGI_ASSIGNABLE_ARCHETYPE <>> ValyEType; Random_access_iterator_archtype Std :: Stable_sort (ri, ri); }
