Zwabel’s Weblog

December 18, 2008

C++ Meta-Programming in KDevelop4: Another Milestone

Filed under: KDE,KDevelop — zwabel @ 5:12 am
Tags: , , , ,

Templates are one of the extremely powerful features of C++ that set it apart from most other languages. You can do most everything with them, from extremly complicated compile-time meta-programming like binary self-balanced trees, down to simple shared pointers or generic container classes.

When I switched to Linux a few years ago, I found KDevelop3 and liked it. However I noticed that it didn’t support code-completion for even the simplest C++ templates like for example a reference-counter pointer. That was my entry into KDevelop development. I implemented template support in KDevelop3 that had most of the needed features, and worked quite well when the needed libraries were processed. However the quality it could reach had some upper bounds, since there was no powerful backing structure like the DUChain, but rather just a flat completely string-based code-model.

Actually it was quite hard making the static DUChain structure compatible with dynamic templates, where a new declaration can be created with every use of a class. However I finally succeeded, and today I’ve reached a milestone that is far above of what KDevelop3, and probably even most other IDEs can reach: Full support for C++ template specialization instantiations.

Explicit Template Specializations
What basically motivated me to finish this was that even though the template support was already quite mature, the code-completion for __gnu_cxx::normal_iterator, the iterator used by std::vector, did not work correctly. The problem: It uses the template-class iterator_traits to compute its used types, which looks something like this:


template<class T>
struct Traits {
typedef T Type;
};

template<class T>
struct Traits<T*> {
typedef T Type;
};

This means that, depending one the template-parameter given, another class with different content is instantiated. This case is relatively easy, but this whole principle allows implementing most any algorithm statically, and thus can become arbitrarily complex. The good thing is that I already implemented a framework for the matching of implicit template-parameters to template-functions, that could partially be re-used to do the actual matching.

So the result of the last days is: Full code-completion for all stdc++ functions/classes that use iterator_traits, which is mainly the iterators, and well, also code-completion for any other C++ classes that use explicit specialization. And important: Without any hacks, it’s based on pure language understanding. :-) Technically this means that the internal C++ engine is now, apart from bugs and slowness, mostly feature-complete.

Meta Programming
As said above, explicit template specialization can not only be used to form new types, but also to compute numerical stuff statically. While this is not very useful in the form I’m going to present, it does serve as a utility to create really efficient code in practice. Today I’ve pushed the C++ engine in KDevelop4 so far, that it can actually evaluate such meta programs right within KDevelop. So here we go:
prime_meta
What you see on the screenshot is mainly a simple meta-program I found on the internet that can compute whether a number is a prime-number. I tuned it a little so the results can nicely be visualized graphically be KDevelop’s declaration highlighting: At the bottom, you see all the lines highlighted that were computed as prime numbers.

Useful Stuff
What I’ve presented until now is mainly backend features, that will be very helpful in practice without you noticing it, because they will make code-completion, use-building, etc. for more complex template-code “just work”.

There is also some annoying stuff about templates though. One of the main problem: They are not nice to write. You never know what types you’re actually dealing with. Even if the types are supposed to fit into some pattern, most IDEs cannot give you any code-completion while you’re writing a template class.

There is a feature in KDevelop4 to recover you from that misery though. So consider the following screenshot:
completion_within_template_1
You see a very simple template class called TemplateClass. Within its member function, you can not have any code-completion for the template type T, because it is unknown. However if you put the cursor above one of the instantiations at the bottom, in our case above “TemplateClass<Struct1>”, and push the shortcut to jump to its declaration, then KDevelop will remember that you’re interested in that specific instantiation, and will give you total correct code-completion for that instantiation within that class:
completion_within_template_2

Development Status
Apart from those features, I’ve worked a bit more on the backend, and fixed a lot of thread-safety and stability issues. This went so far that now, after a very long single-threaded time, I have enabled multi-threaded parsing again. This also leads to faster reparsing and re-highlighting while editing the document, because one parsing-thread is reserved only for parsing triggered by user-input.

About these ads

19 Comments »

  1. Congratulations. This is awesome !

    Is it realistic to expect code-completion for boost
    libraries will get as usable as for QT libraries ?

    Comment by PAW — December 18, 2008 @ 7:45 am

  2. KDevelop just keeps getting better and better :-) Really awesome work David!

    The only thing that’s still rather annoying is the highlighting color scheme, there should be one that doesn’t use quite as many colors; as it is, most of them are indistinguishable anyway. The highlighting of the current variable is also a bit much, maybe a lighter yellow?

    Cheers!

    Comment by Thorben — December 18, 2008 @ 8:14 am

  3. very impressive, i’m looking forward to trying it out. thanks for all the hard work!

    Comment by slougi — December 18, 2008 @ 9:06 am

  4. Just brilliant. What else can one say? :)

    Comment by SSJ — December 18, 2008 @ 9:40 am

  5. Awesome! Is there some roadmap or schedule for KDevelop4? I can’t wait to try it in my regular work (that means in a stable fashion or so).

    Comment by Augu — December 18, 2008 @ 9:49 am

  6. What happens if the evaluation of the template class argument doesn’t halt or takes a very large number of iterations?

    Comment by Robert Knight — December 18, 2008 @ 12:11 pm

  7. @PAW: For sure.

    @Thorben: It’ll be possible to disable the additional highlighting above the kate highlighting. The yellow could be a bit more passive, that’s true. Something more like tinting the background-color in yellow instead of making it full yellow.

    @Augu: KDevelop is getting there, but we want ot to be really good, so we’ll release it once it has reached a state that pleases us. Maybe in half a year, although like always, we could use some more support. :)

    @Rober Knight: The evaluation currently has a maximum depth of 30. What is a problem is when the expansion does not happen to the depth, but to the width. That doesn’t have a limit yet.

    Comment by zwabel — December 18, 2008 @ 12:33 pm

  8. Robert Knight: The standard require you to try for some levels n>=16, and then give up. I imagine David does the same thing.

    This is awesome news, it was the last bit it really needed. I will update my kdevelop friday just to play with it :D

    As for boost, it was actually already quite good, I only had problems with std::tr1::shared_ptr and friends. KDevelop4 is now at the point where if it doesn’t want to complete something, it is more likely because there is nothing to complete rather than something missing in KDevelop4… which is just amazing for C++.

    Thank you, David, this is something I value most highly.

    Comment by Esben Mose Hansen — December 18, 2008 @ 12:37 pm

  9. Thank you very much, David, this should be extremely useful for Eigen!

    By the way if you want a very demanding testcase for this, Eigen’s source code might be appropriate…

    About the maximum recursive template depth, the standard says it should be at least 17 but yes it’s good that you pushed it a bit farther. 30 sounds like a sensible choice.

    Anyway, in my use case, my source code is only a template library so there is (almost) no absolute instantiation of the templates, instead it’s just templates instantiating other templates depending on their own template parameters, so I don’t expect and don’t need KDevelop to try to unfold that.

    /me goes svn up and compile KDevelop now…

    Comment by Benoit Jacob — December 18, 2008 @ 1:12 pm

  10. Boost-proof code-completion == C++ IDE killer feature => KDevelop word domination :)

    Comment by PAW — December 18, 2008 @ 1:51 pm

  11. This is crazy stuff. Good job.

    For the prime numbers example, what specifically did you do to get it to highlight the prime instantiations? (Or was that just some custom code to demonstrate the feature?)

    I’m also not a huge template guru (yet), but is the code for mark_prime in that screenshot correct? With isPrime as the template parameter and prime_result in the enum, but neither of those appearing anywhere else? Aren’t those two supposed to be the same?

    Comment by illissius — December 18, 2008 @ 3:45 pm

  12. @illissius: Depending on whether i is prime or not, is_prime_real is either based on mark_prime or mark_prime, and therefore either inherits mark_prime::prime_result or mark_prime::prime_result. Hovering over one mark_prime::prime_result highlights all occurrences of mark_prime::prime_result, since it’s the same.

    Comment by Eckhart — December 18, 2008 @ 4:22 pm

  13. @illissius: Depending on whether i is prime or not, is_prime_real is either based on mark_prime or mark_prime, and therefore either inherits mark_prime::prime_result or mark_prime::prime_result. Hovering over one mark_prime::prime_result highlights all occurrences of mark_prime::prime_result.

    Comment by Eckhart — December 18, 2008 @ 4:23 pm

  14. Damn WordPress, third try:

    @illissius: Depending on whether i is prime or not, is_prime_real(i) is either based on mark_prime(true) or mark_prime(false), and therefore either inherits mark_prime(true)::prime_result or mark_prime(false)::prime_result. Hovering over one mark_prime(true)::prime_result highlights all occurrences of mark_prime(true)::prime_result.

    Replace braces.

    Comment by Eckhart — December 18, 2008 @ 4:25 pm

  15. I’ve been SVN upping kdevelop nearly daily for the last few weeks and am routinely impressed every time I do. Much thanks for all your hard work.

    As for the highlighting / context / code completion colours, perhaps a mock-up competition on the dot or kde-look or something (they’re fine with me as they are, but I have all the natural artist sensibility of a colour blind gerbil so that doesn’t mean much…).

    cheers
    Nathan

    Comment by Nathan (Borker) — December 18, 2008 @ 6:29 pm

  16. [...] C++ Meta-Programming in KDevelop4: Another Milestone Templates are one of the extremely powerful features of C++ that set it apart from most other languages. You can do [...] [...]

    Pingback by Top Posts « WordPress.com — December 20, 2008 @ 12:17 am

  17. You should come to FOSDEM and give a talk on this excellent stuff.

    Comment by Jos — January 8, 2009 @ 12:37 pm

  18. how i can download this

    Comment by arash — January 23, 2009 @ 9:47 pm

  19. Is it expected in KDevelop4 to support at least some C++0x features? Like variadic templates, lambda functions, etc?

    Comment by abcman — March 25, 2009 @ 7:41 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: