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 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 Visitor hierarchy refactoring The current situation The idea Implementation details Example Merging of the validation process into mapbuilder The current situation The idea Implementation details Example Polishing Design document 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. Apart from the visitor hierarchy refactoring, the global design of the whiteboard won't be changed, 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.

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 have chosen SoC Ideas Whiteboard Backend Refactoring 2012. 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: Merging of the validation process into mapbuilder (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.

Merging of the validation process into mapbuilder

Deletion of the validate_visitor class, injection of its code and other validation code from the action hierarchy into mapbuilder.

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	Merging of the validation process into mapbuilder
Highlighter slowness	side_actions refactoring and Visitor hierarchy refactoring
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 revert 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 two 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,size_t,&action::get_hex>>
        >
   > action_set;
typedef action_set::iterator iterator;

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

This suppose two new pure virtual function 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;
}

Visitor hierarchy refactoring

The current situation

The important classes and class templates of this hierarchy are:

• visitor is the base class of the visitor hierarchy, it dispatches the calls to the derived classes.
• enable_visit_all is actually an interface to the action_ptr objects of every single team.
• action is 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 interface action_inquirer, I'm not a particularly good English speaker, so if you have a better name in mind, let me know. :)

The sole problem faced is to place action_inquirer, 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.

Example

Here is an example function that would speed up highlight_visitor.

action_ptr action_inquirer::action_at(map_location const &h){
    side_actions::iterator r;
    foreach(team& t, *resources::teams){
        side_actions sa = t.get_side_actions();
        if((r=sa.find_action_at(h)) != sa.end())
            return *r;
    }
    return action_ptr();
}

Note: the implementation of side_actions::find_action_at is similar to the one of side_actions::find_first_action_of.

Merging of the validation process into mapbuilder

The current situation

Currently the validation process is separated from the mapbuilding process. However they are depending on each other. Indeed, to validate an action the previous actions have to be applied (by the mapbuilder), while in order to build the future state in the mapbuilder, the sequence of action have to be valid.

The idea

Inject the validation process into mapbuilder. This is not limited to the merging of validate_visitor into mapbuilder, indeed some validity check are also done in the action hierarchy.

Implementation details

I'm still working on this.

Example

Idem.

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.

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.

Where should this document go?

• In doxygen

This makes sense since it's where most of the code documentation is.

• In the wiki

This would make collaborative editing easier.

If you have an opinion on this, let me know. :)

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

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 and on small parts of the whiteboard in order to gain commit access.
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. Make the current iterators bidirectional.
28/05 - 03/06	1	Change the underlying container and rewrite the associated functions.
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_inquirer.
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: Merging of the validation process into mapbuilder
02/07 - 08/07	6	Merge validate_visitor into mapbuilder.
09/07 - 15/07	7	Hunt down other validity check in the action hierarchy and move them to mapbuilder.
13/07	7	Mid-term evaluation
16/07 - 26/08	8..13	Second half term (6 weeks)
16/07 - 22/07	8	Debug, write unit test and documentation.
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