User:Ejls/GSoC 2012/Whiteboard Backend Refactoring
|This page is related to Summer of Code 2012|
|See the list of Summer of Code 2012 Ideas|
|This is a Summer of Code 2012 student page|
Note: This proposal is in continuous construction, if you have any remark, please drop me a line on IRC or on the talk page.
Étienne Simon - Whiteboard backend polishing
My project is to make the Whiteboard code cleaner and to redesign small parts of it to speed it up. The global design of the Whiteboard won't be changed a lot, each part will be reviewed individually. I'm not only planning to improve the Whiteboard backend, but also to document the overall design and each part of it as well as to write a wide variety of test to improve its stability. Moreover, I'll factorise action handling outside of the Whiteboard so that the same code will be usable in all Wesnoth.
Submitted to google
Address at gmail dot com: etienne.jl.simon
|Basics - Experience - Communication skills - Project - Practical considerations|
1.1) Write a small introduction to yourself.
My name is Étienne Simon (forename: Étienne), I'm 20 years old and I live in Paris, France. I really enjoy programming, particularly in C++ and I would like to use my programming skills on a big project like Wesnoth. Also, this year I'll participate in Prologin for the third time. It's the French national programming contest, which I have been 6th and two times finalist.
1.2) State your preferred email address.
Address (at gmail dot com): etienne.jl.simon
1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?
1.4) Why do you want to participate in summer of code?
First of all, I can say I have only theoretical knowledge so far and I believe thanks to a SoC on Wesnoth, I can gain lot of experience since I'll work work on a real project. In addition to that, like I said, I like programming, being paid to do what you like doing is quite cool. Besides, I'm using open source softwares a lot, so it would be nice if my first work could be for the open source community. And of course, for the T-Shirt.
1.5) What are you studying, subject, level and school?
I'm in third and last year of a bachelor's degree (licence) in computer science at Pierre et Marie Curie, Sorbonne Université (UPMC, Paris VI), I mainly took courses related to algorithm and artificial intelligence. Next year, I'll start a master's degree in artificial intelligence and decision.
1.6) What country are you from, at what time are you most likely to be able to join IRC?
I'm from France, CEST (UTC+2 during summer). I always have an irssi running on a server, but I'm more likely to answer during the afternoon and evening. However before the end of the Spring term (4th of June), I'll be able to connect at these times only the weekend and on Friday, I wont be available before 6p.m. UTC for the rest of the week.
1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.
My term (including exams) ends the 4th of June, otherwise I'm considering the GSoC as a full-time job (with more fun and week-end included), therefore I don't have any plans for this summer.
2.1) What programs/software have you worked on before?
Only school projects:
Two years ago (during my first year), we had to code a go/othelo-like game in C. I wrote the game with some extra: a curse interface, a simple AI (alpha-beta) and an AI using unsupervised learning, for this last part, I used NEAT [NeuroEvolution of Augmenting Topologies] (a genetical algorithm evolving neural networks), it didn't beat the minimax though :(. Total: 5000 SLOC [Source Lines Of Code].
Last year, we wrote a BASIC compiler in C (again). I improved the BASIC language a bit: support for array, UDT, function overload and operator overload, the support of references was buggy (poorly designed). Total: 7000 ugly, messy SLOC.
This year, we had to wrote an image manipulation program in C++ (finally!). I used Gtkmm (a C++ wrapper of Gtk+). The result was pretty good, documented with Doxygen and compilable with CMake or with a basic Makefile. Overall, It allowed me to get familiar with C++11 since before this project I've always used gcc 4.2. Total: 5000 SLOC (doxygen documentation (including code) available online).
2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)
The group projects that I worked in were about web development and database administration so I can't really say yes, but that's one of the main reasons why I want to participate in GSoC.
2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?
No, not yet. :)
2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
2.5) Gaming experience - Are you a gamer?
Yes, everyone like to play. ;)
2.5.1) What type of gamer are you?
Hum… I suppose the answers in this subsection can give you an idea about my type. If I'm playing a game it's to have fun, so I'm a "for the lulz gamer", but I suppose it's the same for most people.
2.5.2) What type of games?
Turn-based games like Nethack, Freeciv and of course Wesnoth. I enjoy both strategy and role-playing games, but I like to have time to take a decision.
I also enjoy programming games like jousting, golfing (with Vim) and programming in esoteric languages. For example, I have completed the three first questions of the French national programming contest's qualification in brainfuck, befunge and whitespace (code here, including a 5289 instructions brainfuck program).
2.5.3) What type of opponents do you prefer?
Players using original and unexpected strategy. The HODOR players were really funny, but well…
2.5.4) Are you more interested in story or gameplay?
I tend to select a game on his gameplay, but when it misses a good story I'm less likely to play it.
2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
Not that much, actually I discovered Wesnoth 1.6 two years ago and I can't really say I've played it a lot since then. I prefer to play usually as single player, after completing most of the mainline campaigns (of which I really liked DiD), I played online, but now I'm mostly playing add-ons campaigns. As an indicator: I'm still unable to list drakes units.
2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
I have been lurking the code for a good time now, in January 2011, I reported 3 bugs with 1-line patch attached:
I have also written longer patches:
- (AI) Patch #3185
power_projectionimprovement, it now takes in account future ToD and time areas, I also cleaned the code a bit (task from the EasyCoding page.)
- (WB) Patch #3201 Make leader unable to move when invalidating a planned recall (fixes Bug #19581 that I found reading the whiteboard code.)
I have gained commit access the 02/04/2012.
3) Communication skills
3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
I have studied one term in London last winter, so, my level is good enough to understand and to be understood, don't expect an error-free essay from me though. :)
3.2) What spoken languages are you fluent in?
French and English.
3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
I'm a really calm person, I always take my time to answer messages. Otherwise, I'm ignoring flamers, I think it's the best to do.
3.4) Do you give constructive advice?
I try to.
3.5) Do you receive advice well?
Well, I enjoy receiving advices and learning, otherwise I wouldn't be here. :)
3.6) Are you good at sorting useful criticisms from useless ones?
I think most criticisms are useful, I'm used to the Internet though, troll don't ambush me.
3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want
It depends of what have to be done, the bigger the work is the more it has to be discussed. However if my proposal is retained, I might be a bit more scared of doing something bad in the beginning, so I might discuss a solution more than usual. :)
4.1) Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?
This is a summary, more details can be found here.
I originally chose SoC Ideas Whiteboard Backend Refactoring 2012, however it evolved a lot thanks to Gabba and Crab. This project is the only one not adding any feature for the user, the main goal is to refactor code, write test and documentation. It follows Gabba's project and tschmitz's project on the Whiteboard. Although it doesn't add any feature for the user in itself, I hope it'll help future development of the Whiteboard.
4.2) If you have invented your own project, please describe the project and the scope.
I chose a project from the list, namely SoC Ideas Whiteboard Backend Refactoring 2012. C.f. above answer.
4.3) Why did you choose this project?
I liked the idea behind the Whiteboard, I think it might be a big plus to Wesnoth. Furthermore, I liked how C++ is used in its code (especially the heavy use of SBRM). However it looks like the Whiteboard is not widely used, and I would like to help changing that! :)
4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".
This is a summary, more details can be found here.
I separated my summer in five phases:
- Phase 0: Approach (4 weeks)
- → Start working on the design document. Start the polishing.
- Phase 1:
side_actionsrefactoring (3 weeks)
- Phase 2: Validator hierarchy refactoring (3 weeks)
- Phase 3: Transfer of the action and validation logic into the core (3 weeks)
- Phase 4: Finalisation (3 weeks)
- → Finish the design document. Finish the polishing. Test. Test. Test.
4.5) Include as much technical detail about your implementation as you can
This is a summary, more details can be found here.
I separated my project in five tasks:
- Change of the underlying container, creation of new look up functions.
- Visitor hierarchy refactoring
- Replacement of the
enable_visit_allby a new interface over all of the
- Transfer of the action and validation logic into the core
- Refactoring of
wb::actionin a Whiteboard-independent hierarchy.
- Code uniformisation, small improvements.
- Design document
- Documentation of the global Whiteboard design.
4.6) What do you expect to gain from this project?
I hope it'll help me to join the open source developer community. Actually, the preparation of this proposal already helped me a lot, for example my first patch got committed, it wasn't a big patch, but it was my first step of a (I hope) long path. :) So, I hope to continue learning to walk with the wesnoth community (sorry for the silly metaphor.)
4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
If my work is appreciated, I would rather ask: what would make me leave the Wesnoth community?.
5) Practical considerations
5.1) Are you familiar with any of the following tools or languages?
- I've already used it, but I've opted for git instead.
- C++ (language used for all the normal source code)
- I'm a big fan. I follow the WG21 publications and I often read comp.std.c++ and comp.lang.c++.moderated.
- STL, Boost, Sdl (C++ libraries used by Wesnoth)
- I'm of course used to the stdlib (not to all addition of C++11 though). I'm not familiar with all Boost (I don't have enough brain for this). But I have often used the parts of Boost that's are now (more or less) in the C++11 stdlib and the MPL. I also used a bit Asio, Filesystem and Phoenix (for being the most WTF library), and some other small libraries like Program Option and Range. I never worked on a project using the SDL, I'm not a big GUI user.
- Python (optional, mainly used for tools)
- Not really, no, really basic.
- build environments (eg cmake/scons)
- I've already wrote some CMakeList.txt, but I never worked with nor used scons.
- WML (the wesnoth specific scenario language)
- I wrote a Vim syntax file for it, so I'm already a bit familiar with it. I'm missing practice though.
- Lua (used in combination with WML to create scenarios)
- I'm familiar with it, not as much as C++ but I already used it as a scripting language for an (annoying) IRC bot I wrote. I'm not familiar with its integration in Wesnoth though.
5.2) Which tools do you normally use for development? Why do you use them?
Vim and Unix tools, Perl for big stuff. They are the most productive tools for me, I'm used to them. I'm coding with a laptop under OpenBSD (with gcc 4.2). I also compile Wesnoth on a Debian server (with gcc 4.6), but the X over ssh is a bit slow sometimes. Finally, I temporally have a laptop with FreeBSD 9.0.
5.3) What programming languages are you fluent in?
I'm good in C++, C, Lua, Perl and VimScript. I've a lack of practice in Java, Caml, Scheme, NetLogo, CLIPS and AiML (all of them learnt during my studies). On a different note, I like brainfuck, befunge, whitespace and golfscript.
5.4) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!
If you can't join me by email or on IRC, I'm probably dead but sometimes it's easier to speak than to write so I'll include my phone number in my application.
In the Whiteboard Backend Refactoring idea page, several problems are listed, here is how I'm planning to fix them:
||Visitor hierarchy refactoring, Transfer of the action and validation logic into the core and Polishing|
|Action handling decentralization||Transfer of the action and validation logic into the core|
|Friend classes vs everything in the action classes||Visitor hierarchy refactoring|
|Unit pointer recovery uniformisation||Polishing|
The current situation
The current implementation of
side_actions use a
In order to use it, iterators have been defined over it (
side_actions::iterator and the three const and reverse variants).
These “flattening” iterators let users of
side_actions iterate over all the planned actions, they are performing the zip operation on the fly.
Furthermore, some queries like
side_actions::find_first_action_of are linear in the number of action.
To simplify the code, I propose to keep the action set zipped. The container's iterators will then be usable directly. In order to delimit turns, a second container will have to keep a sequence of iterators pointing to the first action of each turn.
For example, let's say eight actions are planned: five for this turn, two for the next turn and one for the turn after. Three iterators will be kept to delimit turns. Here is a proof that I can't use gimp which also show the idea:
Of course another problem emerge: the sequence of iterator has to be kept in sync with the sequence of action.
Finally, the current implementation gives access to the
action_ptr only in sequence, in order to speed up different way of querying action (e.g. by hex, by unit's id), I propose to build several indexes on the action set.
Let's name these containers
The Whiteboard have the following invariant: an empty turn (a turn without planned action) can't be followed by a non-empty turn (with at least one planned action). It means that
distance(turn_beginnings_[i], turn_beginnings_[i+1])>0, and so we can unambiguously determine the turn number of each action.
Also, note that except when
Choice of the containers
std::deque seems to be the perfect container for
turn_beginnings_. It'll allow random access and we need to add/remove new turns only at the extremities.
On the other hand,
actions_ need three proprieties:
- Allow fast chronological iteration
- Stable iterators
- Allow fast lookup on different indexes
I propose to use a
boost::multi_index_container, this container is part of the library Boost.MultiIndex which is in Boost since version 1.32. It allows the construction of several indexes on the same set of object.
There is however one problem linked to the use of the
boost::multi_index::random_access index: insertion and deletion are in linear time when their are not done at the extremities.
So, the new members should be:
This suppose two new pure virtual functions in
Using action's attribute as key brings another drawback: we must notify the
multi_index_container when we modify a key.
However, the two used keys here (the unit's id and the hex) are never modified in the
This definition is here to give an idea, in practice other indexes will have to be built (e.g. an index on secondary hex which could be the source hex in
Note that this doesn't necessarily means a new pure virtual function in
action, a key extractor can be defined to let
action as it is and use RTTI instead (this might not be clever though.)
Here are three functions rewritten with this new design. Note that
side_actions::iterator is the one defined above.
Reconsideration of Boost.MultiIndex
As Gabba noted (#wesnoth-dev 2012/03/31 7h18), Boost.MultiIndex might be hard to debug and hard to use. This section try to reconsider the use of Boost.MultiIndex.
The major problem we would run into while considering to write a replacement for Boost.MultiIndex is how to allow the usage of the standard algorithms. Indeed, they will be usable only on the underlying container and not on its view. To overcome this, a simple solution have been used in Boost: they rewrote all the iterators. The problem is that, even if it now evolved in something bigger, the first goal with
side_actions refactoring was to remove the iterator's definitions.
While, indeed Boost.MultiIndex will make debugging harder and increase compilation time compared to an homemade solution. It offer numerous advantages:
- It's generic, adding a new key will be as easy as adding a new template parameter in the definition.
- It don't have to be rewritten. :)
- It's already used in Wesnoth (thanks Mordante for noting it.)
- It offers some advantages over the standard containers (e.g. a random-access container with stable iterators and strong exception guaranty.)
Visitor hierarchy refactoring
The current situation
The important classes and class templates of this hierarchy are:
visitor, the base class of the visitor hierarchy, it dispatches the calls to the derived classes.
enable_visit_all, which is actually an interface to the
action_ptrobjects of every single team.
action, the root class of the visitable hierarchy.
Currently, when the visitor hierarchy needs to visit the visitable hierarchy, all the actions of every sides of every turn are visited using the function
enable_visit_all::visit_all_helper (e.g. this function is called by
highlight_visitor::find_main_highlight to find the action to highlight.)
I'm favorable to the maintain of the Visitor pattern, it segregates the different components nicely.
I think the problem come from
enable_visit_all and I would like to replace it with a class offering a more fine-grained access to the actions.
For example, a look up by hex could be defined in this new structure and then used by
Actually, most of the work of this new class will have to do is to redirect the calls to the
side_actions (to one in particular or to all depending on the function).
Let's name this new class
The sole problem faced is to place
action_set, since it is mainly a proxy to a global resource (the
side_actions of each team), it makes sense to place it directly in the
Note that the access to the
action hierarchy will no more be done through inheritance.
Here is an example function that would speed up
Note: the implementation of
side_actions::find_action_at is similar to the one of
Transfer of the action and validation logic into the core
This is a (great) idea of Crab (#wesnoth-dev 2012/04/02 16h11).
The current situation
Currently, the code related to action execution and checking is duplicated in several places.
do_replay_handle() are doing the same thing: checking whether a recall is valid.
Furthermore, the latter is also executing the recall, as is
The idea is simple: factor the code.
However, we must be careful not to include too many functionalities in this new hierarchy, it must be extensible as much as possible without having to modify it.
The good thing with the current code duplication is that I'll be able to look at different code doing the same thing before choosing the best implementation. ;)
A nice point of
wb::action is that Gabba used the visitor pattern, which is exactly what we need here.
Indeed, some functions are strictly related to a module (for example the Whiteboard's highlighter), the visitor pattern will allow virtual functions to be defined outside of the visited hierarchy (the action hierarchy here), moreover the visited hierarchy doesn't need to be recompiled when a new visitor is added.
The overhead of the visitor is really small: an additional (non-virtual) function call.
Since the validation of an action is needed by all the game, it can be included as a member function
virtual bool valid() const =0; in the action hierarchy.
Changes in the Whiteboard
It's a good idea to read this part even if you're not interested in the Whiteboard, indeed this gives you an idea on to extends this new action hierarchy.
Currently, there is a Whiteboard-specific action:
Even if it's disabled for now, the new design need to consider it.
Actually, the changes to do are pretty straightforward:
- A new class
suppose_deadis derived from
- A new class
whiteboard_action_visitoris derived from
action_visitorand add a virtual function
That's all. :)
Now, the sole Whiteboard visitor (
highlight_visitor) can derive from
whiteboard_action_visitor and override
What is important here is that we can still extends the
action hierarchy which is in core, without modifying it.
Of course, I'm planing to write
the same a better explanation in the documentation. ;)
Highlighting a recruit action in the Whiteboard:
Here is the code skeleton for
Currently, each class deriving from
action has a constructor taking a
config object, this sounds good, however these constructors are called by
action::from_config after doing an if on each possible type.
This approach creates a dependency bottleneck: it collects in a single function knowledge about all classes deriving from
A more sensible approach would be to use object factories. The implementation is not very long nor difficult and the resulting code will be more elegant.
The above extension of the
action hierarchy with
suppose_dead, will only need an additional line to register itself.
Some inconsistencies are present in the code (e.g. the way units are referenced). Some other parts needs clean up or/and optimisation (e.g. usage of
The goal of this task is to find this kind of small problem and fix them. These two ones have been spotted by Gabba, but I'm planning to add other small problems to this list as I found them.
Also, they can be a good introduction to the code that's why I'm planning to start working on them before the GSoC start date.
mapbuilder refactoring was one of the main task, I'm putting it here since it'll mainly be refactored as part of the visitor hierarchy refactoring and as part of the transfer of the action and validation logic into the core.
mapbuilder isn't badly designed, all the problems are coming from the API it has to use.
Gabba, mentioned the possibility of an “incremental mapbuilding”, with the new
action_set class, this will be really easy to do.
apply_temp_modifier is called by the function
mapbuilder::process which is itself called on every action by
However, the task visitor hierarchy refactoring will replace
enable_visit_all with a class allowing a more fine grained access to the
side_actions objects, for example an access by turn (on all
side_actions objects) can easily be implemented.
Validation of action swapping
This problem is more difficult than it looks like, indeed it needs a double dispatch (AKA multimethod).
The current implementation use what Alexandrescu call a double switch-on-type, a more elegant approach would be to use a static or logarithmic dispatcher.
But do we really need it?
I don't think so, indeed, currently one of the argument is always a
move, so we can instead use a unique
dynamic_pointer_cast (to check if the action is a
move or derives from it) and then rely on a visitor doing the check for each
So we would end-up with:
Then, we can use it like this:
Usage of a PIMPL in
Here is the list of file recompiled when whiteboard/manager.hpp is modified:
That is, 20 files (as an order of comparison, there is currently 462 .cpp files in src). Although, this number might increase, I'm not sure whether the PIMPL is really necessary. For now, I'm putting it on my TODO list with a low priority.
This idea is inspired by the GUI2 design document present in the SVN.
Doxygen documents the code at a function or class level. The goal is to write a documentation at the module level. That is a document describing the Whiteboard design globally and not function-by-function. Actually it shouldn't duplicate what is in doxygen but complement it. This document could also include informations on how to extend the Whiteboard to help future contributors.
This design document will be written as a doxygen page, this will leave the documentation next to the code.
However, I'll begin to put some drafts on the wiki before committing it. Indeed, that will make reviewing easier.
Here are some possible openings to transform this Google summer of code into a Google year of code:
- Use the new action hierarchy wherever it's needed
- As suggested by Gabba, replace the current
wb::manager::on_gamestate_changeby something more generic (maybe something like
Two of my five tasks are actually best done continuously: the design document and the polishing. Although I haven't clearly placed a week for them, I set two dates at which they should have been completed.
Of course, the plan is not to have any delay and to finish each task early, however I have reserved two weeks (actually one week and a half) for unexpected delay. I named them "movable weeks", because they can move in my timeline if anything goes wrong. :)
On the other hand, I have some openings planned.
|17/03 - 20/04||-11..-5||Student application evaluation|
|17/03 - 20/04||-11..-5||Refine the proposal.|
|23/04 - 20/05||-4..-1||Community Bonding Period (4 weeks)|
|23/04 - 20/05||-4..-1||Phase 0: Approach|
|23/04 - 20/05||-4..-1||Familiarise myself with the Whiteboard, in the process start a draft of the design document.|
|23/04 - 20/05||-4..-1||Start working on the polishing.|
|21/05||0||Start of GSoC|
|21/05 - 12/08||0..11||Continuously work on the design document and on the code polishing.|
|21/05 - 15/07||0..7||First half term (8 weeks)|
|21/05 - 10/06||0..2||Phase 1: |
|21/05 - 27/05||0||Prepare |
|28/05 - 03/06||1||Change the type of |
|04/06 - 10/06||2||Debug, write unit test and documentation.|
|11/06 - 01/07||3..5||Phase 2: Validator hierarchy refactoring|
|11/06 - 17/06||3||Write the class |
|18/06 - 24/06||4||Replace the uses of |
|25/06 - 01/07||5||Debug, write unit test and documentation.|
|02/07 - 22/07||6..8||Phase 3: Transfer of the action and validation logic into the core|
|02/07 - 08/07||6||Separation of the Whiteboard specific-code from the actions. Transfer of the actions in the core.|
|09/07 - 15/07||7||Use this new API in other places, including the |
|16/07 - 26/08||8..13||Second half term (6 weeks)|
|16/07 - 22/07||8||Document the new action hierarchy. Mark @deprecated copies of it.|
|22/07 - 12/08||9..11||Phase 4: Finalisation|
|22/07 - 29/07||9||Heavy testing week.|
|30/07 - 05/08||10||Test, debug. Finish the polishing.|
|06/08 - 12/08||11||Test, debug. Finish the design document.|
|13/08 - 19/08||12||Movable week.|
|20/08 - 26/08||13||Movable week.|