Difference between revisions of "User:Ejls/GSoC 2012/Whiteboard Backend Refactoring"

From The Battle for Wesnoth Wiki
(update)
(update)
Line 47: Line 47:
 
:::[[#actioncore.whiteboard|Changes in the Whiteboard]]<br />
 
:::[[#actioncore.whiteboard|Changes in the Whiteboard]]<br />
 
:::[[#actioncore.example|Example]]<br />
 
:::[[#actioncore.example|Example]]<br />
 +
:::[[#actioncore.deserialization|Deserialization]]<br />
 
:[[#polishing|Polishing]]<br />
 
:[[#polishing|Polishing]]<br />
 +
::[[#polishing.mapbuilder|<tt>mapbuilder</tt>]]<br />
 +
::[[#polishing.swap_check|Validation of action swapping]]<br />
 +
::[[#polishing.manager_pimpl|Usage of a PIMPL in <tt>manager</tt>]]<br />
 
:[[#designdoc|Design document]]<br />
 
:[[#designdoc|Design document]]<br />
 
:[[#Openings|Openings]]<br />
 
:[[#Openings|Openings]]<br />
Line 117: Line 121:
 
''This is a summary, more details can be found [http://wiki.wesnoth.org/User:Ejls/GSoC%202012/Whiteboard%20Backend%20Refactoring#Proposal here].''
 
''This is a summary, more details can be found [http://wiki.wesnoth.org/User:Ejls/GSoC%202012/Whiteboard%20Backend%20Refactoring#Proposal 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 [http://wiki.wesnoth.org/GSoC-WesnothWhiteboard_Gabba gabba's project] and [http://wiki.wesnoth.org/User:Tschmitz 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.<!--
+
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 [http://wiki.wesnoth.org/GSoC-WesnothWhiteboard_Gabba Gabba's project] and [http://wiki.wesnoth.org/User:Tschmitz 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. -->
 
-->|<!-- 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.<!--
 
I chose a project from the list, namely [[SoC Ideas Whiteboard Backend Refactoring 2012]]. C.f. above answer.<!--
Line 128: Line 132:
 
*Phase 0: Approach (4 weeks)
 
*Phase 0: Approach (4 weeks)
 
::→ Start working on the design document. Start the ''polishing''.
 
::→ Start working on the design document. Start the ''polishing''.
*Phase 1: <tt>side_actions</tt> refactoring (3 weeks)
+
*Phase 1: <code>side_actions</code> refactoring (3 weeks)
 
*Phase 2: Validator hierarchy 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 3: Transfer of the action and validation logic into the core (3 weeks)
Line 137: Line 141:
  
 
I separated my project in five tasks:
 
I separated my project in five tasks:
;<tt>side_actions</tt> refactoring
+
;<code>side_actions</code> refactoring
 
:Change of the underlying container, creation of new look up functions.
 
:Change of the underlying container, creation of new look up functions.
 
;Visitor hierarchy refactoring
 
;Visitor hierarchy refactoring
:Replacement of the <tt>enable_visit_all</tt> by a new interface over all of the <tt>side_actions</tt> objects.
+
:Replacement of the <code>enable_visit_all</code> by a new interface over all of the <code>side_actions</code> objects.
 
;Transfer of the action and validation logic into the core
 
;Transfer of the action and validation logic into the core
:Refactoring of <tt>wb::action</tt> in a Whiteboard-independent hierarchy.
+
:Refactoring of <code>wb::action</code> in a Whiteboard-independent hierarchy.
 
;Polishing
 
;Polishing
 
:Code uniformisation, small improvements.
 
:Code uniformisation, small improvements.
Line 167: Line 171:
 
!style="border:1px dotted #AAA;padding:5px;"|Solution
 
!style="border:1px dotted #AAA;padding:5px;"|Solution
 
|-
 
|-
|style="border:1px dotted #AAA;padding:5px;"|<tt>side_actions</tt> complexity
+
|style="border:1px dotted #AAA;padding:5px;"|<code>side_actions</code> complexity
 
|style="border:1px dotted #AAA;padding:5px;"|[[#side_actions|<tt>side_actions</tt> refactoring]]
 
|style="border:1px dotted #AAA;padding:5px;"|[[#side_actions|<tt>side_actions</tt> refactoring]]
 
|-
 
|-
|style="border:1px dotted #AAA;padding:5px;"|Redundancy between <tt>mapbuilder</tt> and <tt>validate_visitor</tt>
+
|style="border:1px dotted #AAA;padding:5px;"|Redundancy between <code>mapbuilder</code> and <code>validate_visitor</code>
 
|style="border:1px dotted #AAA;padding:5px;"|[[#visitorhier|Visitor hierarchy refactoring]], [[#actioncore|Transfer of the action and validation logic into the core]] and [[#Polishing|Polishing]]
 
|style="border:1px dotted #AAA;padding:5px;"|[[#visitorhier|Visitor hierarchy refactoring]], [[#actioncore|Transfer of the action and validation logic into the core]] and [[#Polishing|Polishing]]
 
|-
 
|-
Line 185: Line 189:
 
|style="border:1px dotted #AAA;padding:5px;"|[[#polishing|Polishing]]
 
|style="border:1px dotted #AAA;padding:5px;"|[[#polishing|Polishing]]
 
|-
 
|-
|style="border:1px dotted #AAA;padding:5px;"|<tt>boost::dynamic_pointer_cast</tt> vs simple numeric id
+
|style="border:1px dotted #AAA;padding:5px;"|<code>boost::dynamic_pointer_cast</code> vs simple numeric id
 
|style="border:1px dotted #AAA;padding:5px;"|[[#polishing|Polishing]]
 
|style="border:1px dotted #AAA;padding:5px;"|[[#polishing|Polishing]]
 
|-
 
|-
Line 192: Line 196:
 
|}
 
|}
  
===<span id="side_actions"><tt>side_actions</tt> refactoring</span>===
+
===<span id="side_actions"><code>side_actions</code> refactoring</span>===
 
====<span id="side_actions.situation">The current situation</span>====
 
====<span id="side_actions.situation">The current situation</span>====
The current implementation of <tt>side_actions</tt> use a <tt>std::deque&lt;std::deque&lt;action_ptr&gt;&gt;</tt>.
+
The current implementation of <code>side_actions</code> use a <code>std::deque&lt;std::deque&lt;action_ptr&gt;&gt;</code>.
In order to use it, iterators have been defined over it (<tt>side_actions::iterator</tt> and the three const and reverse variants).
+
In order to use it, iterators have been defined over it (<code>side_actions::iterator</code> and the three const and reverse variants).
These “flattening” iterators let users of <tt>side_actions</tt> iterate over all the planned actions, they are performing the ''zip'' operation on the fly.
+
These “flattening” iterators let users of <code>side_actions</code> iterate over all the planned actions, they are performing the ''zip'' operation on the fly.
  
Furthermore, some queries like <tt>side_actions::find_first_action_of</tt> are linear in the number of action.
+
Furthermore, some queries like <code>side_actions::find_first_action_of</code> are linear in the number of action.
  
 
====<span id="side_actions.idea">The idea</span>====
 
====<span id="side_actions.idea">The idea</span>====
Line 208: Line 212:
 
Of course another problem emerge: the sequence of iterator has to be kept in sync with the sequence of action.
 
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 <tt>action_ptr</tt> 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.
+
Finally, the current implementation gives access to the <code>action_ptr</code> 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.
  
 
====<span id="side_actions.implementation">Implementation details</span>====
 
====<span id="side_actions.implementation">Implementation details</span>====
Let's name these containers <tt>actions_</tt> and <tt>turn_beginnings_</tt>.
+
Let's name these containers <code>actions_</code> and <code>turn_beginnings_</code>.
  
 
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 <code>distance(turn_beginnings_[i], turn_beginnings_[i+1])&gt;0</code>, and so we can unambiguously determine the turn number of each action.
 
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 <code>distance(turn_beginnings_[i], turn_beginnings_[i+1])&gt;0</code>, and so we can unambiguously determine the turn number of each action.
  
Also, note that except when <tt>actions_.empty()</tt> : <tt>turn_beginnings_.front()==actions_.begin()</tt>.
+
Also, note that except when <code>actions_.empty()</code> : <code>turn_beginnings_.front()==actions_.begin()</code>.
  
 
=====<span id="side_actions.containers">Choice of the containers</span>=====
 
=====<span id="side_actions.containers">Choice of the containers</span>=====
<tt>std::deque</tt> seems to be the perfect container for <tt>turn_beginnings_</tt>. It'll allow random access and we need to add/remove new turns only at the extremities.
+
<code>std::deque</code> seems to be the perfect container for <code>turn_beginnings_</code>. It'll allow random access and we need to add/remove new turns only at the extremities.
  
On the other hand, <tt>actions_</tt> need three proprieties:
+
On the other hand, <code>actions_</code> need three proprieties:
 
*Allow fast chronological iteration
 
*Allow fast chronological iteration
 
*Stable iterators
 
*Stable iterators
 
*Allow fast lookup on different indexes
 
*Allow fast lookup on different indexes
I propose to use a <tt>boost::multi_index_container</tt>, this container is part of the library [http://www.boost.org/doc/libs/1_49_0/libs/multi_index Boost.MultiIndex] which is in Boost since version 1.32. It allows the construction of several indexes on the same set of object.
+
I propose to use a <code>boost::multi_index_container</code>, this container is part of the library [http://www.boost.org/doc/libs/1_49_0/libs/multi_index 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 <tt>boost::multi_index::random_access</tt> index: insertion and deletion are in linear time when their are not done at the extremities.
+
There is however one problem linked to the use of the <code>boost::multi_index::random_access</code> index: insertion and deletion are in linear time when their are not done at the extremities.
  
 
So, the new members should be:
 
So, the new members should be:
Line 245: Line 249:
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#000000; font-weight:bold">namespace</span> bmi <span style="color:#000000">=</span> boost<span style="color:#000000">::</span>multi_index<span style="color:#000000">;</span><br /><span style="color:#000000; font-weight:bold">typedef</span> bmi<span style="color:#000000">::</span>multi_index_container<span style="color:#000000">&lt;</span><br />&nbsp; &nbsp; action_ptr<span style="color:#000000">,</span><br />&nbsp; &nbsp; bmi<span style="color:#000000">::</span>indexed_by<span style="color:#000000">&lt;</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>random_access<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>chronological<span style="color:#000000">&gt; &gt;,</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>hashed_non_unique<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>by_unit<span style="color:#000000">&gt;,</span> bmi<span style="color:#000000">::</span>const_mem_fun<span style="color:#000000">&lt;</span>action<span style="color:#000000">,</span><span style="color:#0057ae">size_t</span><span style="color:#000000">,&amp;</span>action<span style="color:#000000">::</span>get_unit_id<span style="color:#000000">&gt; &gt;,</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>hashed_non_unique<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>by_hex<span style="color:#000000">&gt;,</span> bmi<span style="color:#000000">::</span>const_mem_fun<span style="color:#000000">&lt;</span>action<span style="color:#000000">,</span><span style="color:#000000">map_location</span><span style="color:#000000">,&amp;</span>action<span style="color:#000000">::</span>get_hex<span style="color:#000000">&gt; &gt;</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000">&gt;</span><br />&nbsp; &nbsp; <span style="color:#000000">&gt;</span> action_set<span style="color:#000000">;</span><br /><span style="color:#000000; font-weight:bold">typedef</span> action_set<span style="color:#000000">::</span>iterator iterator<span style="color:#000000">;</span><br /><br />action_set actions_<span style="color:#000000">;</span><br />std<span style="color:#000000">::</span>deque<span style="color:#000000">&lt;</span>iterator<span style="color:#000000">&gt;</span> turn_beginnings_<span style="color:#000000">;</span><br /></div></code><br />
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#000000; font-weight:bold">namespace</span> bmi <span style="color:#000000">=</span> boost<span style="color:#000000">::</span>multi_index<span style="color:#000000">;</span><br /><span style="color:#000000; font-weight:bold">typedef</span> bmi<span style="color:#000000">::</span>multi_index_container<span style="color:#000000">&lt;</span><br />&nbsp; &nbsp; action_ptr<span style="color:#000000">,</span><br />&nbsp; &nbsp; bmi<span style="color:#000000">::</span>indexed_by<span style="color:#000000">&lt;</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>random_access<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>chronological<span style="color:#000000">&gt; &gt;,</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>hashed_non_unique<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>by_unit<span style="color:#000000">&gt;,</span> bmi<span style="color:#000000">::</span>const_mem_fun<span style="color:#000000">&lt;</span>action<span style="color:#000000">,</span><span style="color:#0057ae">size_t</span><span style="color:#000000">,&amp;</span>action<span style="color:#000000">::</span>get_unit_id<span style="color:#000000">&gt; &gt;,</span><br />&nbsp; &nbsp; &nbsp; &nbsp; bmi<span style="color:#000000">::</span>hashed_non_unique<span style="color:#000000">&lt;</span>bmi<span style="color:#000000">::</span>tag<span style="color:#000000">&lt;</span>by_hex<span style="color:#000000">&gt;,</span> bmi<span style="color:#000000">::</span>const_mem_fun<span style="color:#000000">&lt;</span>action<span style="color:#000000">,</span><span style="color:#000000">map_location</span><span style="color:#000000">,&amp;</span>action<span style="color:#000000">::</span>get_hex<span style="color:#000000">&gt; &gt;</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000">&gt;</span><br />&nbsp; &nbsp; <span style="color:#000000">&gt;</span> action_set<span style="color:#000000">;</span><br /><span style="color:#000000; font-weight:bold">typedef</span> action_set<span style="color:#000000">::</span>iterator iterator<span style="color:#000000">;</span><br /><br />action_set actions_<span style="color:#000000">;</span><br />std<span style="color:#000000">::</span>deque<span style="color:#000000">&lt;</span>iterator<span style="color:#000000">&gt;</span> turn_beginnings_<span style="color:#000000">;</span><br /></div></code><br />
  
This suppose two new pure virtual functions in <tt>action</tt>: <tt>get_unit_id</tt> and <tt>get_hex</tt>.
+
This suppose two new pure virtual functions in <code>action</code>: <code>get_unit_id</code> and <code>get_hex</code>.
  
Using action's attribute as key brings another drawback: we must notify the <tt>multi_index_container</tt> when we modify a key.
+
Using action's attribute as key brings another drawback: we must notify the <code>multi_index_container</code> when we modify a key.
However, the two used keys here (the unit's id and the hex) are never modified in the <tt>action</tt> hierarchy.
+
However, the two used keys here (the unit's id and the hex) are never modified in the <code>action</code> 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 <tt>move</tt>.)
+
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 <code>move</code>.)
Note that this doesn't necessarily means a new pure virtual function in <tt>action</tt>, a key extractor can be defined to let <tt>action</tt> as it is and use ''RTTI'' instead (this might not be clever though.)
+
Note that this doesn't necessarily means a new pure virtual function in <code>action</code>, a key extractor can be defined to let <code>action</code> as it is and use ''RTTI'' instead (this might not be clever though.)
  
 
=====<span id="side_actions.example">Example</span>=====
 
=====<span id="side_actions.example">Example</span>=====
Here are three functions rewritten with this new design. Note that <tt>side_actions::iterator</tt> is the one defined above.
+
Here are three functions rewritten with this new design. Note that <code>side_actions::iterator</code> is the one defined above.
  
 
<!-- Original:
 
<!-- Original:
Line 296: Line 300:
  
 
=====<span id="side_actions.reconsideration">Reconsideration of Boost.MultiIndex</span>=====
 
=====<span id="side_actions.reconsideration">Reconsideration of Boost.MultiIndex</span>=====
As gabba noted ([http://www.wesnoth.org/irclogs/2012/03/%23wesnoth-dev.2012-03-31.log #wesnoth-dev 2012/03/31 7h18]), Boost.MultiIndex might be hard to debug and hard to use.
+
As Gabba noted ([http://www.wesnoth.org/irclogs/2012/03/%23wesnoth-dev.2012-03-31.log #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.
 
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 <tt>side_actions</tt> refactoring was to remove the iterator's definitions.
+
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 <code>side_actions</code> 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.
 
While, indeed Boost.MultiIndex will make debugging harder and increase compilation time compared to an homemade solution.
Line 305: Line 309:
 
*It's generic, adding a new key will be as easy as adding a new template parameter in the definition.
 
*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 don't have to be rewritten. :)
*It's already used in Wesnoth (thanks mordante for noting it.)
+
*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.)
 
*It offers some advantages over the standard containers (e.g. a random-access container with stable iterators and strong exception guaranty.)
  
Line 311: Line 315:
 
====<span id="visitorhier.situation">The current situation</span>====
 
====<span id="visitorhier.situation">The current situation</span>====
 
The important classes and class templates of this hierarchy are:
 
The important classes and class templates of this hierarchy are:
*'''<tt>visitor</tt>''', the base class of the visitor hierarchy, it dispatches the calls to the derived classes.
+
*'''<code>visitor</code>''', the base class of the visitor hierarchy, it dispatches the calls to the derived classes.
*'''<tt>enable_visit_all</tt>''', which is actually an interface to the <tt>action_ptr</tt> objects of every single team.
+
*'''<code>enable_visit_all</code>''', which is actually an interface to the <code>action_ptr</code> objects of every single team.
*'''<tt>action</tt>''', the root class of the visitable hierarchy.
+
*'''<code>action</code>''', 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 <tt>enable_visit_all::visit_all_helper</tt> (e.g. this function is called by <tt>highlight_visitor::find_main_highlight</tt> to find the action to highlight.)
+
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 <code>enable_visit_all::visit_all_helper</code> (e.g. this function is called by <code>highlight_visitor::find_main_highlight</code> to find the action to highlight.)
  
 
====<span id="visitorhier.idea">The idea</span>====
 
====<span id="visitorhier.idea">The idea</span>====
 
I'm favorable to the maintain of the Visitor pattern, it segregates the different components nicely.
 
I'm favorable to the maintain of the Visitor pattern, it segregates the different components nicely.
I think the problem come from <tt>enable_visit_all</tt> and I would like to replace it with a class offering a more fine-grained access to the actions.
+
I think the problem come from <code>enable_visit_all</code> 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 <tt>highlight_visitor</tt>.
+
For example, a look up by hex could be defined in this new structure and then used by <code>highlight_visitor</code>.
Actually, most of the work of this new class will have to do is to redirect the calls to the <tt>side_actions</tt> (to one in particular or to all depending on the function).
+
Actually, most of the work of this new class will have to do is to redirect the calls to the <code>side_actions</code> (to one in particular or to all depending on the function).
  
 
====<span id="visitorhier.implementation">Implementation details</span>====
 
====<span id="visitorhier.implementation">Implementation details</span>====
Let's name this new class <tt>action_set</tt>.
+
Let's name this new class <code>action_set</code>.
  
The sole problem faced is to place <tt>action_set</tt>, since it is mainly a proxy to a global resource (the <tt>side_actions</tt> of each team), it makes sense to place it directly in the <tt>wb</tt> namespace.
+
The sole problem faced is to place <code>action_set</code>, since it is mainly a proxy to a global resource (the <code>side_actions</code> of each team), it makes sense to place it directly in the <code>wb</code> namespace.
  
Note that the access to the <tt>action</tt> hierarchy will no more be done through inheritance.
+
Note that the access to the <code>action</code> hierarchy will no more be done through inheritance.
  
 
=====<span id="visitorhier.example">Example</span>=====
 
=====<span id="visitorhier.example">Example</span>=====
Here is an example function that would speed up <tt>highlight_visitor</tt>.
+
Here is an example function that would speed up <code>highlight_visitor</code>.
 
<!-- Original:
 
<!-- Original:
 
action_ptr action_set::action_at(map_location const &hex){
 
action_ptr action_set::action_at(map_location const &hex){
Line 344: Line 348:
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;">action_ptr action_set<span style="color:#000000">::</span><span style="color:#010181">action_at</span><span style="color:#000000">(</span>map_location <span style="color:#0057ae">const</span> <span style="color:#000000">&amp;</span>hex<span style="color:#000000">){</span><br />&nbsp; &nbsp; side_actions<span style="color:#000000">::</span>iterator result<span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#010181">foreach</span><span style="color:#000000">(</span>team<span style="color:#000000">&amp;</span> side<span style="color:#000000">, *</span>resources<span style="color:#000000">::</span>teams<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; side_actions actions <span style="color:#000000">=</span> side<span style="color:#000000">.</span><span style="color:#010181">get_side_actions</span><span style="color:#000000">();</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000; font-weight:bold">if</span><span style="color:#000000">((</span>result <span style="color:#000000">=</span> actions<span style="color:#000000">.</span><span style="color:#010181">find_action_at</span><span style="color:#000000">(</span>hex<span style="color:#000000">)) !=</span> actions<span style="color:#000000">.</span><span style="color:#010181">end</span><span style="color:#000000">())</span><br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000; font-weight:bold">return</span> <span style="color:#000000">*</span>result<span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#000000; font-weight:bold">return</span> <span style="color:#010181">action_ptr</span><span style="color:#000000">();</span><br /><span style="color:#000000">}</span><br /></div></code><br />
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;">action_ptr action_set<span style="color:#000000">::</span><span style="color:#010181">action_at</span><span style="color:#000000">(</span>map_location <span style="color:#0057ae">const</span> <span style="color:#000000">&amp;</span>hex<span style="color:#000000">){</span><br />&nbsp; &nbsp; side_actions<span style="color:#000000">::</span>iterator result<span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#010181">foreach</span><span style="color:#000000">(</span>team<span style="color:#000000">&amp;</span> side<span style="color:#000000">, *</span>resources<span style="color:#000000">::</span>teams<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; side_actions actions <span style="color:#000000">=</span> side<span style="color:#000000">.</span><span style="color:#010181">get_side_actions</span><span style="color:#000000">();</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000; font-weight:bold">if</span><span style="color:#000000">((</span>result <span style="color:#000000">=</span> actions<span style="color:#000000">.</span><span style="color:#010181">find_action_at</span><span style="color:#000000">(</span>hex<span style="color:#000000">)) !=</span> actions<span style="color:#000000">.</span><span style="color:#010181">end</span><span style="color:#000000">())</span><br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000; font-weight:bold">return</span> <span style="color:#000000">*</span>result<span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#000000; font-weight:bold">return</span> <span style="color:#010181">action_ptr</span><span style="color:#000000">();</span><br /><span style="color:#000000">}</span><br /></div></code><br />
  
Note: the implementation of <tt>side_actions::find_action_at</tt> is similar to the one of <tt>side_actions::find_first_action_of</tt>.
+
Note: the implementation of <code>side_actions::find_action_at</code> is similar to the one of <code>side_actions::find_first_action_of</code>.
  
 
===<span id="actioncore">Transfer of the action and validation logic into the core</span>===
 
===<span id="actioncore">Transfer of the action and validation logic into the core</span>===
Line 351: Line 355:
 
====<span id="actioncore.situation">The current situation</span>====
 
====<span id="actioncore.situation">The current situation</span>====
 
Currently, the code related to action execution and checking is duplicated in several places.
 
Currently, the code related to action execution and checking is duplicated in several places.
For example, <tt>ai::recall_result::do_check_before()</tt>, <tt>wb::validate_visitor::visit(recall_ptr)</tt> and <tt>do_replay_handle()</tt> are doing the same thing: checking whether a recall is valid.
+
For example, <code>ai::recall_result::do_check_before()</code>, <code>wb::validate_visitor::visit(recall_ptr)</code> and <code>do_replay_handle()</code> are doing the same thing: checking whether a recall is valid.
Furthermore, the latter is also executing the recall, as is <tt>wb::recall::execute()</tt> and <tt>ai::recall_result::do_execute()</tt>.
+
Furthermore, the latter is also executing the recall, as is <code>wb::recall::execute()</code> and <code>ai::recall_result::do_execute()</code>.
  
 
====<span id="actioncore.idea">The idea</span>====
 
====<span id="actioncore.idea">The idea</span>====
Line 362: Line 366:
  
 
====<span id="actioncore.implementation">Implementation details</span>====
 
====<span id="actioncore.implementation">Implementation details</span>====
A nice point of <tt>wb::action</tt> is that gabba used the visitor pattern, which is exactly what we need here.
+
A nice point of <code>wb::action</code> 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.
 
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.
 
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 <tt>virtual bool valid() const =0;</tt> in the action hierarchy.
+
Since the validation of an action is needed by all the game, it can be included as a member function <code>virtual bool valid() const =0;</code> in the action hierarchy.
  
 
=====<span id="actioncore.whiteboard">Changes in the Whiteboard</span>=====
 
=====<span id="actioncore.whiteboard">Changes in the Whiteboard</span>=====
 
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.
 
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: <tt>suppose_dead</tt>.
+
Currently, there is a Whiteboard-specific action: <code>suppose_dead</code>.
 
Even if it's disabled for now, the new design need to consider it.
 
Even if it's disabled for now, the new design need to consider it.
 
Actually, the changes to do are pretty straightforward:
 
Actually, the changes to do are pretty straightforward:
*A new class <tt>suppose_dead</tt> is derived from <tt>action</tt>
+
*A new class <code>suppose_dead</code> is derived from <code>action</code>
*A new class <tt>whiteboard_action_visitor</tt> is derived from <tt>action_visitor</tt> and add a virtual function <tt>visit(suppose_dead&amp;)</tt>
+
*A new class <code>whiteboard_action_visitor</code> is derived from <code>action_visitor</code> and add a virtual function <code>visit(suppose_dead&amp;)</code>
 
That's all. :)
 
That's all. :)
Now, the sole Whiteboard visitor (<tt>highlight_visitor</tt>) can derive from <tt>whiteboard_action_visitor</tt> and override <tt>visit(suppose_dead&amp;)</tt>.
+
Now, the sole Whiteboard visitor (<code>highlight_visitor</code>) can derive from <code>whiteboard_action_visitor</code> and override <code>visit(suppose_dead&amp;)</code>.
  
What is important here is that we can still extends the <tt>action</tt> hierarchy which is in core, without modifying it.
+
What is important here is that we can still extends the <code>action</code> hierarchy which is in core, without modifying it.
  
 
Of course, I'm planing to write <s>the same</s> a better explanation in the documentation. ;)
 
Of course, I'm planing to write <s>the same</s> a better explanation in the documentation. ;)
Line 391: Line 395:
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;">recruit <span style="color:#010181">recruit_action</span><span style="color:#000000">(</span>the_team<span style="color:#000000">,</span> the_unit<span style="color:#000000">,</span> the_hex<span style="color:#000000">);</span><br />highlighter_<span style="color:#000000">-&gt;</span><span style="color:#010181">visit</span><span style="color:#000000">(</span>recruit_action<span style="color:#000000">);</span><br /></div></code><br />
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;">recruit <span style="color:#010181">recruit_action</span><span style="color:#000000">(</span>the_team<span style="color:#000000">,</span> the_unit<span style="color:#000000">,</span> the_hex<span style="color:#000000">);</span><br />highlighter_<span style="color:#000000">-&gt;</span><span style="color:#010181">visit</span><span style="color:#000000">(</span>recruit_action<span style="color:#000000">);</span><br /></div></code><br />
  
Here is the code skeleton for <tt>wb::suppose_dead</tt>:
+
Here is the code skeleton for <code>wb::suppose_dead</code>:
 
<!-- Original:
 
<!-- Original:
 
class suppose_dead: public action {
 
class suppose_dead: public action {
Line 415: Line 419:
 
};
 
};
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#000000; font-weight:bold">class</span> suppose_dead<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> action <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">accept</span><span style="color:#000000">(</span>whiteboard_action_visitor <span style="color:#000000">&amp;</span>vis<span style="color:#000000">){</span> vis<span style="color:#000000">.</span><span style="color:#010181">visit</span><span style="color:#000000">(*</span><span style="color:#000000; font-weight:bold">this</span><span style="color:#000000">); }</span><br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* the code… */</span><br /><span style="color:#000000">};</span><br /><br /><span style="color:#000000; font-weight:bold">class</span> whiteboard_action_visitor<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> action_visitor <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#000000; font-weight:bold">virtual</span> <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>suppose_dead<span style="color:#000000">&amp;) =</span><span style="color:#b07e00">0</span><span style="color:#000000">;</span><br /><span style="color:#000000">};</span><br /><br /><span style="color:#000000; font-weight:bold">class</span> highlight_visitor<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> whiteboard_action_visitor <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>recruit <span style="color:#000000">&amp;</span>rec<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* Display some nice sign */</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>suppose_dead <span style="color:#000000">&amp;</span>dead<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* Display some scary sign */</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* … */</span><br /><span style="color:#000000">};</span><br /></div></code><br />
 
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#000000; font-weight:bold">class</span> suppose_dead<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> action <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">accept</span><span style="color:#000000">(</span>whiteboard_action_visitor <span style="color:#000000">&amp;</span>vis<span style="color:#000000">){</span> vis<span style="color:#000000">.</span><span style="color:#010181">visit</span><span style="color:#000000">(*</span><span style="color:#000000; font-weight:bold">this</span><span style="color:#000000">); }</span><br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* the code… */</span><br /><span style="color:#000000">};</span><br /><br /><span style="color:#000000; font-weight:bold">class</span> whiteboard_action_visitor<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> action_visitor <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#000000; font-weight:bold">virtual</span> <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>suppose_dead<span style="color:#000000">&amp;) =</span><span style="color:#b07e00">0</span><span style="color:#000000">;</span><br /><span style="color:#000000">};</span><br /><br /><span style="color:#000000; font-weight:bold">class</span> highlight_visitor<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> whiteboard_action_visitor <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>recruit <span style="color:#000000">&amp;</span>rec<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* Display some nice sign */</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>suppose_dead <span style="color:#000000">&amp;</span>dead<span style="color:#000000">){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* Display some scary sign */</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">/* … */</span><br /><span style="color:#000000">};</span><br /></div></code><br />
 +
 +
=====<span id="actioncore.deserialization">Deserialization</span>=====
 +
Currently, each class deriving from <code>action</code> has a constructor taking a <code>config</code> object, this sounds good, however these constructors are called by <code>action::from_config</code> 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 <code>action</code>.
 +
 +
A more sensible approach would be to use an ''object factory''.
 +
The implementation is not very long nor difficult and the resulting code will be more elegant.
 +
 +
The above extension of the <code>action</code> hierarchy with <code>suppose_dead</code>, will only need an additional line to register itself.
  
 
===<span id="polishing">Polishing</span>===
 
===<span id="polishing">Polishing</span>===
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 <tt>boost::dynamic_pointer_cast</tt>).
+
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 <code>boost::dynamic_pointer_cast</code>).
  
 
The goal of this task is to find this kind of small problem and fix them.
 
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.
+
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.
 
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.
  
Although, the <tt>mapbuilder</tt> refactoring was one of the main task, I'm putting it here since it'll be mainly refactored as part of the [[#visitorhier|visitor hierarchy refactoring]] and as part of the [[#actioncore|transfer of the action and validation logic into the core]]. Indeed, the <tt>mapbuilder</tt> isn't badly designed, all the problems are coming from the API it has to use.
+
====<span id="polishing.mapbuilder"><code>mapbuilder</code></span>====
 +
Although, the <code>mapbuilder</code> refactoring was one of the main task, I'm putting it here since it'll mainly be refactored as part of the [[#visitorhier|visitor hierarchy refactoring]] and as part of the [[#actioncore|transfer of the action and validation logic into the core]].
 +
Indeed, the <code>mapbuilder</code> 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 <code>action_set</code> class, this will be really easy to do.
 +
Currently <code>apply_temp_modifier</code> is called by the function <code>mapbuilder::process</code> which is itself called on every action by <code>enable_visit_all</code>.
 +
However, the task [[#visitorhier|visitor hierarchy refactoring]] will replace <code>enable_visit_all</code> with a class allowing a more fine grained access to the <code>side_actions</code> objects, for example an access by turn (on all <code>side_actions</code> objects) can easily be implemented.
 +
 
 +
====<span id="polishing.swap_check">Validation of action swapping</span>====
 +
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 <code>move</code>, so we can instead use a unique <code>dynamic_pointer_cast</code> (to check if the action is a <code>move</code> or derives from it) and then rely on a visitor doing the check for each <code>action</code> type.
 +
 
 +
So we would end-up with:
 +
<!-- Original:
 +
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_;
 +
};
 +
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#000000; font-weight:bold">class</span> swapable_with_move<span style="color:#000000">:</span> <span style="color:#000000; font-weight:bold">public</span> visitor <span style="color:#000000">{</span><br /><span style="color:#000000; font-weight:bold">public</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; <span style="color:#010181">swapable_with_move</span><span style="color:#000000">(</span>move_ptr first<span style="color:#000000">):</span> <span style="color:#010181">first_</span><span style="color:#000000">(</span>first<span style="color:#000000">),</span> <span style="color:#010181">valid_</span><span style="color:#000000">(</span><span style="color:#000000; font-weight:bold">false</span><span style="color:#000000">) {}</span><br />&nbsp; &nbsp; <span style="color:#0057ae">bool</span> <span style="color:#010181">valid</span><span style="color:#000000">()</span> <span style="color:#0057ae">const</span> <span style="color:#000000">{</span> <span style="color:#000000; font-weight:bold">return</span> valid_<span style="color:#000000">; }</span><br />&nbsp; &nbsp; <br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">// If we don't define visit for an action, the swap is necessarily valid.</span><br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>action<span style="color:#000000">&amp;){</span><br />&nbsp; &nbsp; &nbsp; &nbsp; valid_ <span style="color:#000000">=</span> <span style="color:#000000; font-weight:bold">true</span><span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br />&nbsp; &nbsp; <br />&nbsp; &nbsp; <span style="color:#0057ae">void</span> <span style="color:#010181">visit</span><span style="color:#000000">(</span>move <span style="color:#000000">&amp;</span>second<span style="color:#000000">){</span><br /> &nbsp; &nbsp; &nbsp; &nbsp; valid_ <span style="color:#000000">=</span> first_<span style="color:#000000">-&gt;</span><span style="color:#010181">get_dest_hex</span><span style="color:#000000">() !=</span> second<span style="color:#000000">.</span><span style="color:#010181">get_source_hex</span><span style="color:#000000">();</span><br />&nbsp; &nbsp; <span style="color:#000000">}</span><br /><br />&nbsp; &nbsp; <span style="color:#838183; font-style:italic">// etc…</span><br /><br /><span style="color:#000000; font-weight:bold">private</span><span style="color:#000000">:</span><br />&nbsp; &nbsp; move_ptr first_<span style="color:#000000">;</span><br />&nbsp; &nbsp; <span style="color:#0057ae">bool</span> valid_<span style="color:#000000">;</span><br /><span style="color:#000000">};</span><br /></div></code><br />
 +
 
 +
Then, we can use it like this:
 +
<!-- Original:
 +
// 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();
 +
}
 +
Formated: --><code><div style="border: 1px dashed #AAA;background:#FAF3E9;padding:7px;"><span style="color:#838183; font-style:italic">// Check if we can swap the two actions</span><br /><span style="color:#000000; font-weight:bold">if</span> <span style="color:#000000">(</span>move_ptr bump_earlier <span style="color:#000000">=</span> dynamic_pointer_cast<span style="color:#000000">&lt;</span>move<span style="color:#000000">&gt;(*</span>position<span style="color:#000000">)) {</span><br />&nbsp; &nbsp; swapable_with_move <span style="color:#010181">swap_check</span><span style="color:#000000">(</span>bump_earlier<span style="color:#000000">);</span><br />&nbsp; &nbsp; <span style="color:#000000">(*</span>previous<span style="color:#000000">)-&gt;</span><span style="color:#010181">accept</span><span style="color:#000000">(</span>swap_check<span style="color:#000000">);</span><br />&nbsp; &nbsp; <span style="color:#000000; font-weight:bold">if</span><span style="color:#000000">(!</span>swap_check<span style="color:#000000">.</span><span style="color:#010181">valid</span><span style="color:#000000">())</span><br />&nbsp; &nbsp; &nbsp; &nbsp; <span style="color:#000000; font-weight:bold">return</span> <span style="color:#010181">end</span><span style="color:#000000">();</span><br /><span style="color:#000000">}</span><br /></div></code>
 +
 
 +
====<span id="polishing.manager_pimpl">Usage of a PIMPL in <code>manager</code></span>====
 +
Here is the list of file recompiled when <tt>whiteboard/manager.hpp</tt> is modified:
 +
{|
 +
|-
 +
|<ul>
 +
<li><tt>actions.cpp</tt></li>
 +
<li><tt>game_display.cpp</tt></li>
 +
<li><tt>game_events.cpp</tt></li>
 +
<li><tt>menu_events.cpp</tt></li>
 +
<li><tt>mouse_events.cpp</tt></li>
 +
<li><tt>play_controller.cpp</tt></li>
 +
<li><tt>playmp_controller.cpp</tt></li>
 +
</ul>
 +
|<ul>
 +
<li><tt>playsingle_controller.cpp</tt></li>
 +
<li><tt>playturn.cpp</tt></li>
 +
<li><tt>replay.cpp</tt></li>
 +
<li><tt>reports.cpp</tt></li>
 +
<li><tt>whiteboard/highlight_visitor.cpp</tt></li>
 +
<li><tt>whiteboard/manager.cpp</tt></li>
 +
<li><tt>whiteboard/move.cpp</tt></li>
 +
</ul>
 +
|<ul>
 +
<li><tt>whiteboard/recall.cpp</tt></li>
 +
<li><tt>whiteboard/recruit.cpp</tt></li>
 +
<li><tt>whiteboard/side_actions.cpp</tt></li>
 +
<li><tt>whiteboard/suppose_dead.cpp</tt></li>
 +
<li><tt>whiteboard/utility.cpp</tt></li>
 +
<li><tt>whiteboard/validate_visitor.cpp</tt></li>
 +
</ul>
 +
|}
 +
 
 +
That is, 20 files (as an order of comparison, there is currently 462 <tt>.cpp</tt> 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.
  
 
===<span id="designdoc">Design document</span>===
 
===<span id="designdoc">Design document</span>===
Line 441: Line 537:
 
Here are some possible openings to transform this Google summer of code into a Google year of code:
 
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
 
*Use the new action hierarchy wherever it's needed
*As suggested by gabba, replace the current <tt>wb::manager::on_gamestate_change</tt> by something more generic (maybe something like <tt>ai::gamestate_observer</tt>)
+
*As suggested by Gabba, replace the current <code>wb::manager::on_gamestate_change</code> by something more generic (maybe something like <code>ai::gamestate_observer</code>)
  
 
===Timeline===
 
===Timeline===
Line 497: Line 593:
 
|style="border:1px dotted #AAA;padding:5px;"|'''21/05 - 10/06'''
 
|style="border:1px dotted #AAA;padding:5px;"|'''21/05 - 10/06'''
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|'''0..2'''
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|'''0..2'''
|style="border:1px dotted #AAA;padding:5px;"|'''Phase 1: <tt>side_actions</tt> refactoring'''
+
|style="border:1px dotted #AAA;padding:5px;"|'''Phase 1: <code>side_actions</code> refactoring'''
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;"|21/05 - 27/05
 
|style="border:1px dotted #AAA;padding:5px;"|21/05 - 27/05
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|0
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|0
|style="border:1px dotted #AAA;padding:5px;"|Prepare <tt>side_actions</tt> for the change. Add debug informations to the logs. Add the new member <tt>turn_beginnings_</tt>.
+
|style="border:1px dotted #AAA;padding:5px;"|Prepare <code>side_actions</code> for the change. Add debug informations to the logs. Add the new member <code>turn_beginnings_</code>.
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;"|28/05 - 03/06
 
|style="border:1px dotted #AAA;padding:5px;"|28/05 - 03/06
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|1
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|1
|style="border:1px dotted #AAA;padding:5px;"|Change the type of <tt>actions_</tt> and rewrite the associated functions. Delete the custom iterators.
+
|style="border:1px dotted #AAA;padding:5px;"|Change the type of <code>actions_</code> and rewrite the associated functions. Delete the custom iterators.
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;"|04/06 - 10/06
 
|style="border:1px dotted #AAA;padding:5px;"|04/06 - 10/06
Line 517: Line 613:
 
|style="border:1px dotted #AAA;padding:5px;"|11/06 - 17/06
 
|style="border:1px dotted #AAA;padding:5px;"|11/06 - 17/06
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|3
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|3
|style="border:1px dotted #AAA;padding:5px;"|Write the class <tt>action_set</tt>.
+
|style="border:1px dotted #AAA;padding:5px;"|Write the class <code>action_set</code>.
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;"|18/06 - 24/06
 
|style="border:1px dotted #AAA;padding:5px;"|18/06 - 24/06
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|4
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|4
|style="border:1px dotted #AAA;padding:5px;"|Replace the uses of <tt>enable_visit_all</tt> with the new interface. Then delete <tt>enable_visit_all</tt>.
+
|style="border:1px dotted #AAA;padding:5px;"|Replace the uses of <code>enable_visit_all</code> with the new interface. Then delete <code>enable_visit_all</code>.
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;"|25/06 - 01/07
 
|style="border:1px dotted #AAA;padding:5px;"|25/06 - 01/07
Line 537: Line 633:
 
|style="border:1px dotted #AAA;padding:5px;"|09/07 - 15/07
 
|style="border:1px dotted #AAA;padding:5px;"|09/07 - 15/07
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|7
 
|style="border:1px dotted #AAA;padding:5px;text-align:center;"|7
|style="border:1px dotted #AAA;padding:5px;"|Use this new API in other places, including the <tt>mapbuilder</tt>.
+
|style="border:1px dotted #AAA;padding:5px;"|Use this new API in other places, including the <code>mapbuilder</code>.
 
|-
 
|-
 
|style="border:1px dotted #AAA;padding:5px;color:#444;"|''13/07''
 
|style="border:1px dotted #AAA;padding:5px;color:#444;"|''13/07''

Revision as of 02:03, 10 April 2012


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:

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: side_actions%20idea.png

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 an object factory. 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