Does any widely-known program to extract template parameters requirements from source code already e

[Pavel Shved]

Is there a program of wide use that automatically extracts template
parameters requirements from source code of template functions?

I mean the following: assume we have a template function that demands
its template parameter(s) to meet certain requirements. For example
simple sorting function

template <typename T> void sort(T* t, int N)
{
for (int i=0;i<N-1; i++)
for (int j=N-1;j>i;j--)
if (t[j-1] < t[j]) {
T temp=t[j];
t[j]=t[j-1];
t[j-1]=temp;
}
}

requires T to have the following members: a) operator<(T) returning
bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
these operators use passing-by-reference, but this assumption is way
too strict).

I know (or at least I'm sure I do) there is a way to formalize and
extract strict requirements (which the above axample doesn't
intgroduce) as there is also possibility to form unstrict, common ones
(common is that hardly anyone would write T:perator= returning
something instead of T). Of course i mean automatic extraction
procedures.

The question is whether someone has done it already.

 

[Mike Wahler]

Is there a program of wide use that automatically extracts template
parameters requirements from source code of template functions?

I mean the following: assume we have a template function that demands
its template parameter(s) to meet certain requirements. For example
simple sorting function

template <typename T> void sort(T* t, int N)
{
for (int i=0;i<N-1; i++)
for (int j=N-1;j>i;j--)
if (t[j-1] < t[j]) {
T temp=t[j];
t[j]=t[j-1];
t[j-1]=temp;
}
}

requires T to have the following members: a) operator<(T) returning
bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
these operators use passing-by-reference, but this assumption is way
too strict).

I know (or at least I'm sure I do) there is a way to formalize and
extract strict requirements (which the above axample doesn't
intgroduce) as there is also possibility to form unstrict, common ones
(common is that hardly anyone would write T:perator= returning
something instead of T). Of course i mean automatic extraction
procedures.

The question is whether someone has done it already.

I think that if you write code which instantiates such a template,
a compiler will issue diagnostics if its requirements are not
met. Or perhaps I misunderstand your question.

As for your specific example above, the only thing a compiler
would complain about would be operator<(), since lacking
a definition of copy ctor and operator=(), the compiler will
synthesize them. Of course those default semantics might
not be what you need.

template <typename T> void sort(T* t, int N)
{
for (int i=0;i<N-1; i++)
for (int j=N-1;j>i;j--)
if (t[j-1] < t[j]) {
T temp=t[j];
t[j]=t[j-1];
t[j-1]=temp;
}
}

class T
{
};


int main()
{
T t;
sort(&t, 42);
return 0;
}

..\usenet.cpp(475) : error C2676: binary '<' : 'T' does not define this
operator or a conversion to a type acceptable to the predefined operator
.\usenet.cpp(490) : see reference to function template instantiation
'void sort<T>(T *,int)' being compiled
with
[
T=T
]


Modify type T to:

class T
{
public:
bool operator<(const T& rhs)
{
return true;
}
};

No errors or warnings. (VC++ 2005 Express)


-Mike

 

[Pavel Shved]

I think that if you write code which instantiates such a template,
a compiler will issue diagnostics if its requirements are not
met. Or perhaps I misunderstand your question.

What i need is to deduce TEXT like 'parameter T must have the
following members: etc. etc.' from the source code.

Modify type T to:

class T
{
public:
bool operator<(const T& rhs)
{
return true;
}

};

No errors or warnings. (VC++ 2005 Express)

But this class does have default operator= and copy-constructor
granted him by the compiler. Anyway that's not the essence of the
problem.

PS. I'm noob and i can only hope that my message will appear in a
proper place of this topic. :-\

 

[Victor Bazarov]

What i need is to deduce TEXT like 'parameter T must have the
following members: etc. etc.' from the source code.


But this class does have default operator= and copy-constructor
granted him by the compiler. Anyway that's not the essence of the
problem.

PS. I'm noob and i can only hope that my message will appear in a
proper place of this topic. :-\

Sorry, I haven't followed the thread. I just have a couple of cents
worth of a note: when C++ gets the "concept" support (some of that is
already included in G++ in research form, IIRC), there will be plenty
of tools that would reverse-engineer classes to extract "concepts"
from them (I can see a tool that extracts a common concept from more
than one class).

It can be worth asking in a G++ discussion forum, the folks who right
now are involved with adding "concepts" to G++ might know a simple
way (or have thought about it) to reverse the process.

Right now I don't know of any tool which would do that.

V

 

[Pavel Shved]

Sorry, I haven't followed the thread. I just have a couple of cents
worth of a note: when C++ gets the "concept" support (some of that is
already included in G++ in research form, IIRC), there will be plenty
of tools that would reverse-engineer classes to extract "concepts"
from them (I can see a tool that extracts a common concept from more
than one class).

Thank you for the info. Discarding these mysterious 'concepts' from
my search results was a true mistake.

 

[James Kanze]

Is there a program of wide use that automatically extracts
template parameters requirements from source code of template
functions?

It's fundamentally impossible. How can a program divine the
intent of the author?

I mean the following: assume we have a template function that
demands its template parameter(s) to meet certain
requirements. For example simple sorting function

template <typename T> void sort(T* t, int N)
{
for (int i=0;i<N-1; i++)
for (int j=N-1;j>i;j--)
if (t[j-1] < t[j]) {
T temp=t[j];
t[j]=t[j-1];
t[j-1]=temp;
}
}

requires T to have the following members: a) operator<(T) returning
bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
these operators use passing-by-reference, but this assumption is way
too strict).

First, your requirements are far more restrictive than the code
requires. All that the code requires is that the specified
operations are supported. Taking all implicit conversions into
account. Secondly, of course, the function has very definite
requirements with regards to the semantics of some of the
operators. Requirements which I don't think any tool could
deduce. And finally, in most real cases, the author will define
the required concepts as part of the requirements; the actual
implementation may not use them all but he has a right to use
them in the next version. The standard lists a return type of
T& as part of the Assignable concept; it's quite possible for an
implementation never to use it, but it remains a requirement.
And std::list requires Assignable, although most implementations
never use assignment. For class templates, some requirements
apply to the class itself, others just to specific functions in
the class---how would you distinguish?

 

[Pavel Shved]

It's fundamentally impossible. How can a program divine the
intent of the author?

Fundamentally - it IS possible. Imagine the (infinite) set of all
possible C++ types; we are to deduce a subset of it: which of them can
be used as template parameters. We have a procedure to check whether
a single class statisfies original requirements - mere experiment
(compiling our class against the function in question). So we should
only invent proper terms in which we describe the subset. Is english
(or any other human language) rich enough to describe it? I think it
is.

One can argue that the ability of compiling t[j-1] < t[j] depends on
the environment. It truly does, but then let's expand our set to the
set of all possible C++ programs, and add environment descrioption to
it.

I mean the following: assume we have a template function that
demands its template parameter(s) to meet certain
requirements. For example simple sorting function
template <typename T> void sort(T* t, int N)
{
for (int i=0;i<N-1; i++)
for (int j=N-1;j>i;j--)
if (t[j-1] < t[j]) {
T temp=t[j];
t[j]=t[j-1];
t[j-1]=temp;
}
}
requires T to have the following members: a) operator<(T) returning
bool; b) copy-constructor, accepting T, and c) operator=(T) (usually
these operators use passing-by-reference, but this assumption is way
too strict).

First, your requirements are far more restrictive than the code
requires. All that the code requires is that the specified
operations are supported. Taking all implicit conversions into
account.

Would the following form of requirement statisfy you?
vv
a) T has member function operator<(.) visible in public scope which
return type is implicitely castable to bool and which argument is
implicitely castable from T with no ambiguity that cannot be resolved
by standard rules; or there is [bool] operator>( ]T[ , ]T[ ) in one of
the wrapping namespaces with no ambiguity etc...
^^
We are only to define in english (which is done in standard!) two
terms denoted above like ]something[ and [something] with aid of known
implicit casting rules. By ther way, defining LessThanComparable, C++
Standard uses the same terms, referring to them as 'convertible to
bool'.
As we can see, this description involves some restrictions to the
environment which our class is in.

Secondly, of course, the function has very definite
requirements with regards to the semantics of some of the
operators. Requirements which I don't think any tool could
deduce.

Does the persistance of unsolvable equations forces us not to solve
linear ones? ;-)

And finally, in most real cases, the author will define
the required concepts as part of the requirements; the actual
implementation may not use them all but he has a right to use
them in the next version. The standard lists a return type of
T& as part of the Assignable concept; it's quite possible for an
implementation never to use it, but it remains a requirement.
And std::list requires Assignable, although most implementations
never use assignment.

You are very right when we deal with something that a) is already
standartized; b) should be implementation-independent. In my certain
case neither the former nor the latter takes place. Moreover, the
study of the discreapancies between author's and real requirements is
valuable, both when checking what can we do wrong failing then to
compile against 'future versions' and aiding the author to test
whether his implementation is covered by the concepts he wrote in
documentaion.

For class templates, some requirements
apply to the class itself, others just to specific functions in
the class---how would you distinguish?

Why should we distinguish? We'd rather gather them!

 

[James Kanze]

Fundamentally - it IS possible.

Fundamentally, it is NOT. The information simply isn't there
for any tool to extract.

I gave a simple example in my posting: std::list requires that
the class over which it is instantiated by Assignable. Most
implementations never use assignment. How could a tool
determine that an assignment operator is necessary (and that it
must return T&) if there isn't the slightest reference to it in
the code.

Imagine the (infinite) set of all possible C++ types; we are
to deduce a subset of it: which of them can be used as
template parameters. We have a procedure to check whether a
single class statisfies original requirements - mere
experiment (compiling our class against the function in
question).

The problem is where to find the original requirements. There's
not necessarily any trace of them in the code, so the procedure
will have to read the comments. Except that the requirements
may not even have been copied into the source as comments; most
of the implementations of std::list simply refer to the standard
for the requirements.

[...]

Would the following form of requirement statisfy you?
vv
a) T has member function operator<(.) visible in public scope which
return type is implicitely castable to bool and which argument is
implicitely castable from T with no ambiguity that cannot be resolved
by standard rules; or there is [bool] operator>( ]T[ , ]T[ ) in one of
the wrapping namespaces with no ambiguity etc...

Certainly not. First, it requires operator< to be a member
function, which certainly isn't necessary. Secondly, it doesn't
take into account possible conversions. A class like:

class C
{
public:
explicit C( int i ) : myI( i ) {}
operator int() const { return myI ; }

private:
int myI ;
} ;

will work for your function, for example, and there's not an
operator< in site.

Most importantly, of course, even a human, just reading your
code, cannot determine what the requirements are. Do you
"require" support for all of the comparison operators, or simply
<? (In other words, is the fact that you just use <, and none
of the others, an accident of the implementation, or is it a
contractual restriction.)

Does the persistance of unsolvable equations forces us not to solve
linear ones? ;-)

False analogy. In this case, we have the requirements. They
must exist before anyone can write the code. Rather than asking
a tool to produce a necessarily incomplete, and possibly
incorrect version of them, doesn't it make more sense to require
the author to publish them with his code?

Why should we distinguish? We'd rather gather them!

Because it's important. The implementations of std::list that
I've seen all use operator<, and very few use operator=. Never
the less, it is legal to instantiate an std::list over a type
which doesn't support operator<, but not over a type which
doesn't support operator=. The requirement for the first is
limited to certain functions; the requirement for the second
applies to the class.

 

[Victor Bazarov]

Fundamentally - it IS possible.

Fundamentally, it is NOT. The information simply isn't there
for any tool to extract.

I gave a simple example in my posting: std::list requires [..]

I believe you're arguing different points. Pavel (as I see it)
says that extracting at least something would be possible and in
many cases enough. James says that it is impossible to capture
*all* requirements in *every* case. Would you agree that both
are correct?

V

 

[James Kanze]

Is there a program of wide use that automatically extracts
template parameters requirements from source code of template
functions?
It's fundamentally impossible. How can a program divine the
intent of the author?
Fundamentally - it IS possible.

Fundamentally, it is NOT. The information simply isn't there
for any tool to extract.
I gave a simple example in my posting: std::list requires [..]

I believe you're arguing different points. Pavel (as I see
it) says that extracting at least something would be possible
and in many cases enough.

Extracting something is certainly possible, but what you can
extract is of absolutely no use at all, ever. It has no real
advantage over just trying and seeing if it compiles. And as we
all know, the fact that something compiles without errors
doesn't mean that it is correct.

 

[Victor Bazarov]

Is there a program of wide use that automatically extracts
template parameters requirements from source code of template
functions?
It's fundamentally impossible. How can a program divine the
intent of the author?
Fundamentally - it IS possible.
Fundamentally, it is NOT. The information simply isn't there
for any tool to extract.
I gave a simple example in my posting: std::list requires [..]

I believe you're arguing different points. Pavel (as I see
it) says that extracting at least something would be possible
and in many cases enough.

Extracting something is certainly possible, but what you can
extract is of absolutely no use at all, ever. It has no real
advantage over just trying and seeing if it compiles. And as we
all know, the fact that something compiles without errors
doesn't mean that it is correct.

What's the term for a person who continues arguing even though it
is apparent that there is no argument to be continued? Here are
two principles you might consider: "never say 'never' (or 'ever')",
and "one man's trash is another man's treasure". OK?

V

 

[Pavel Shved]

"one man's trash is another man's treasure". OK?

True.
I must thank James though, his arguments are of much use and I really
should to review what I'm trying to achieve.