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.

Content

Description SoC Application Contact Questionnaire 1 - Basics 2 - Experience 3 - Communication skills 4 - Project 5 - Practical considerations Proposal The problems side_actions refactoring The current situation The idea Implementation details Choice of the containers Example Reconsideration of Boost.MultiIndex Visitor hierarchy refactoring The current situation The idea Implementation details Example Transfer of the action and validation logic into the core The current situation The idea Implementation details Changes in the Whiteboard Example Deserialization Polishing mapbuilder Validation of action swapping Usage of a PIMPL in manager Design document Openings Timeline

Description

É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.

SoC Application

Submitted to google

Contact

IRC ejls  Email Address at gmail dot com: etienne.jl.simon

Forum ejls Gna ejls

Questionnaire

Basics - Experience - Communication skills - Project - Practical considerations

1) Basics

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?

ejls

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) Experience

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.

No.

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:

• Two compilation errors: Bug #17584 and Bug #17585.
• A minimap bug: Bug #17676.

I have also written longer patches:

• (AI) Patch #3185 power_projection improvement, 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) Project

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_actions refactoring (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:

side_actions refactoring

Change of the underlying container, creation of new look up functions.

Visitor hierarchy refactoring

Replacement of the enable_visit_all by a new interface over all of the side_actions objects.

Transfer of the action and validation logic into the core

Refactoring of wb::action in a Whiteboard-independent hierarchy.

Polishing

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?

• Subversion

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.

Proposal

The problems

In the Whiteboard Backend Refactoring idea page, several problems are listed, here is how I'm planning to fix them:

Problem	Solution
side_actions complexity	side_actions refactoring
Redundancy between mapbuilder and validate_visitor	Visitor hierarchy refactoring, Transfer of the action and validation logic into the core and Polishing
Highlighter slowness	side_actions refactoring and Visitor hierarchy refactoring
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
boost::dynamic_pointer_cast vs simple numeric id	Polishing
Documentation	Design document

side_actions refactoring

The current situation

The current implementation of side_actions use a std::deque<std::deque<action_ptr>>. 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.

The idea

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.

Implementation details

Let's name these containers actions_ and turn_beginnings_.

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 actions_.empty() : turn_beginnings_.front()==actions_.begin().

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:

namespace bmi = boost::multi_index;
typedef bmi::multi_index_container<
    action_ptr,
    bmi::indexed_by<
        bmi::random_access<bmi::tag<chronological> >,
        bmi::hashed_non_unique<bmi::tag<by_unit>, bmi::const_mem_fun<action,size_t,&action::get_unit_id> >,
        bmi::hashed_non_unique<bmi::tag<by_hex>, bmi::const_mem_fun<action,map_location,&action::get_hex> >
        >
    > action_set;
typedef action_set::iterator iterator;

action_set actions_;
std::deque<iterator> turn_beginnings_;

This suppose two new pure virtual functions in action: get_unit_id and get_hex.

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 action hierarchy.

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 move.) 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.)

Example

Here are three functions rewritten with this new design. Note that side_actions::iterator is the one defined above.

side_actions::iterator side_actions::end_turn(size_t turn_num){
    if(turn_num+1 >= turn_beginnings_.size())
        return actions_.end();
    else
        return turn_beginnings_[turn_num+1];
}

side_actions::iterator side_actions::raw_enqueue(size_t turn_num, action_ptr act){
    assert(turn_num <= turn_beginnings_.size());

    iterator new_action = actions_.insert(end_turn(turn_num), act).first;

    if(turn_num >= turn_beginnings_.size())
        turn_beginnings_.push_back(new_action);

    return new_action;
}

side_actions::find_first_action_of(unit const* unit, side_actions::iterator start_position){
    // First we get all the action of this unit
    typedef action_set::index<by_unit>::type::iterator unit_iterator;
    std::pair<unit_iterator, unit_iterator> act = actions_.get<by_unit>().equal_range(unit->underlying_id());

    // Then we find the first of them (chronologically) after start_position
    iterator first = actions_.end();
    for(unit_iterator it = act.first; it != act.second; ++it){
        iterator chrono_it = actions_.project<chronological>(it);
        if(chrono_it < first && chrono_it > start_position)
            first = chrono_it;
    }
    return first;
}

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_ptr objects 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.)

The idea

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 highlight_visitor. 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).

Implementation details

Let's name this new class action_set.

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 wb namespace.

Note that the access to the action hierarchy will no more be done through inheritance.

Example

Here is an example function that would speed up highlight_visitor.

action_ptr action_set::action_at(map_location const &hex){
    side_actions::iterator result;
    foreach(team& side, *resources::teams){
        side_actions actions = side.get_side_actions();
        if((result = actions.find_action_at(hex)) != actions.end())
            return *result;
    }
    return action_ptr();
}

Note: the implementation of side_actions::find_action_at is similar to the one of side_actions::find_first_action_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. For example, ai::recall_result::do_check_before(), wb::validate_visitor::visit(recall_ptr) and do_replay_handle() are doing the same thing: checking whether a recall is valid. Furthermore, the latter is also executing the recall, as is wb::recall::execute() and ai::recall_result::do_execute().

The idea

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. ;)

Implementation details

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: suppose_dead. 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_dead is derived from action
• A new class whiteboard_action_visitor is derived from action_visitor and add a virtual function visit(suppose_dead&)

That's all. :) Now, the sole Whiteboard visitor (highlight_visitor) can derive from whiteboard_action_visitor and override visit(suppose_dead&).

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. ;)

Example

Highlighting a recruit action in the Whiteboard:

recruit recruit_action(the_team, the_unit, the_hex);
highlighter_->visit(recruit_action);

Here is the code skeleton for wb::suppose_dead:

class suppose_dead: public action {
public:
    void accept(whiteboard_action_visitor &vis){ vis.visit(*this); }
    /* the code… */
};

class whiteboard_action_visitor: public action_visitor {
public:
    virtual void visit(suppose_dead&) =0;
};

class highlight_visitor: public whiteboard_action_visitor {
public:
    void visit(recruit &rec){
        /* Display some nice sign */
    }
    void visit(suppose_dead &dead){
        /* Display some scary sign */
    }
    /* … */
};

Deserialization

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 action.

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.

Polishing

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 boost::dynamic_pointer_cast).

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

Although, the 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. Indeed, the 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. Currently apply_temp_modifier is called by the function mapbuilder::process which is itself called on every action by enable_visit_all. 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 action type.

So we would end-up with:

class swapable_with_move: public visitor {
public:
    swapable_with_move(move_ptr first): first_(first), valid_(false) {}
    bool valid() const { return valid_; }
   
    // If we don't define visit for an action, the swap is necessarily valid.
    void visit(action&){
        valid_ = true;
    }
   
    void visit(move &second){
        valid_ = first_->get_dest_hex() != second.get_source_hex();
    }

    // etc…

private:
    move_ptr first_;
    bool valid_;
};

Then, we can use it like this:

// Check if we can swap the two actions
if (move_ptr bump_earlier = dynamic_pointer_cast<move>(*position)) {
    swapable_with_move swap_check(bump_earlier);
    (*previous)->accept(swap_check);
    if(!swap_check.valid())
        return end();
}

Usage of a PIMPL in manager

Here is the list of file recompiled when whiteboard/manager.hpp is modified:

actions.cpp game_display.cpp game_events.cpp menu_events.cpp mouse_events.cpp play_controller.cpp playmp_controller.cpp

playsingle_controller.cpp playturn.cpp replay.cpp reports.cpp whiteboard/highlight_visitor.cpp whiteboard/manager.cpp whiteboard/move.cpp

whiteboard/recall.cpp whiteboard/recruit.cpp whiteboard/side_actions.cpp whiteboard/suppose_dead.cpp whiteboard/utility.cpp whiteboard/validate_visitor.cpp

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.

Design document

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.

Openings

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_change by something more generic (maybe something like ai::gamestate_observer)

Timeline

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.

Date	Week	Description
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: side_actions refactoring
21/05 - 27/05	0	Prepare side_actions for the change. Add debug informations to the logs. Add the new member turn_beginnings_.
28/05 - 03/06	1	Change the type of actions_ and rewrite the associated functions. Delete the custom iterators.
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 action_set.
18/06 - 24/06	4	Replace the uses of enable_visit_all with the new interface. Then delete enable_visit_all.
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 mapbuilder.
13/07	7	Mid-term evaluation
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.
24/08	13	Final evaluation