I wouldn't worry about licence issues right now since we're using the GPL anyway
(although I'm not too sure about whether we'd prefer v2 or v3). Just something
we should keep in mind.

I checked the updated docs on the website, and they look good. Excellent job!

I've opened the new issue232 for automated doc generation, which we discussed a
while ago.

Marking this one as resolved. :-)

The author of tree.hh seems to be open to licensing under other
conditions:
http://tree.phi-sci.com/ "However, if you would like to use tree.hh
under different conditions, contact me and we will work something out."

IIRC, he considered releasing it under a Boost License anyway.

And if he unexpectedly refuses, I can still re-implement the parse tree.

Done.

BTW, the tree.hh and tree_util.hh libraries are GPLv3, which means we can no
longer distribute the planner under a non-GPL license, or under an older version
of the GPL than v3. I'm pointing this out because we recently got a request to
grant the planner to ESA under a non-GPL license.

Good point, I forgot about that.

I think you are right, we can keep the "ext" name for the directory -- it
shouldn't be a problem at all that some gcc system includes are also in a
directory called "ext".

We shouldn't use #include "ext/boost/..." since Boost itself uses #include
<boost/...> internally, which means we have to make this work in any case.

I'll work on this straight away. Actually, the notebook I'm using right now is a
good testbed because the current code fails to compile on it.

Will do the rest tomorrow. Maybe sometime the planner will be able to
generate all this documentation by itself.

I just remembered the boost dependencies.
Currently, the planner will not compile on systems without boost
installed.
To change this, the "ext" directory has to be included (we considered
renaming this because there's already an ext namespace - although in the
way I imagine it, our ext-stuff wouldn't have its own namespace), and
the corresponding includes for any.hpp may need to be changed.

Malte: I can do this tomorrow if the naming is resolved. But it might be
quicker for both of us if you do it directly.

Looking good so far; if you can update the rest of the pages too, we can mark
this as resolved.

I started with http://www.fast-downward.org/DocumentationStyle.
Can do more later or tomorrow.

Merged. The new option syntax is now used in default! :-)

Moritz has documented the changes on
http://www.fast-downward.org/NewConfigurationSyntax
but we also need to update old documentation itself, e.g. fix the cases where
they use round parentheses or variable numbers or arguments.
One page that needs to be fixed is
http://www.fast-downward.org/DocumentationStyle, but also all pages with example
configurations or that use syntax that is now spelled differently.

Moritz's page should also be linked from our main documentation hub.

Who can take care of this?

Excellent! I'll look into merging this later today.

"old_greedy" has been deleted recently and "pdb" is from a Master's project that
is not yet done. I guess we should delete the old_greedy configs from
downward_configs.py; pdb can stay, as we'll integrate that in the medium term
anyway.

Okay, I managed to extract 234 configurations and ran them. The only
parsing errors where caused by missing "pdb()" and "old_greedy()".
Hopefully, these are supposed to be nonexistent.

There's no direct way at the moment. You will have to write a new 
function that concatenates the lists of other functions and single 
configurations I guess.

Is there a simple way to output all configurations that are
defined/generated in downward_configs.py? 

I have translated this to use the new syntax, but would like to run
every configuration on a simple problem to check for mismatched brackets
etc.

Sorry, my fault.
I had to retranslate/preprocess the problem files, I made them a while
ago. It seems it's better to make them on demand. Additionally there was
an unitialized value in my version, that I introduced when fixing stuff
related to your comments.
Works now in both versions.

It should work. Can you send the precise command-line syntax that you're using,
including how you specify the input?

Question: 
Running "./search/downward ipc seq-sat-lama-2011 " segfaults in both my
version and e.g. the ipc-2011-submission, when applied to satellite1,
elevator3, mystery2, openstacks-sat08-strips01, or stacks10 (did not
test more). Is this configuration not suited to these problems? If yes,
then what problems can I use to test this config?

No objections.

I prefer 1., mainly because it will help keep the option parser code
easier to maintain. As long as 1.0 is not released, I think it's
reasonable to break a bit of backward compatibility. Comparisons between
the before and after code versions should still be easy, since we'll
have the config files for both, and for new configs it's easy to write
both versions if necessary.

So if you don't have any objection, I'll start updating the config files
now.

It would be good to run the tests by the mid of the week, since I'll
only have sporadic computer access from 9/10.04 to 2x.04. 

I'll write a wiki-entry documenting the changes after updating the
config files, probably tomorrow.

OK, everything's now almost ready.

Moritz: I pushed your branch to the master repository and made another round of
merges from default, so it'd be good if you could pull the changes to the branch
from there.

There's one thing that still keeps me from merging this into the default branch,
and that's that there are still some files that use the old option syntax and
hence won't work any more for cases where we made backward-incompatible changes:

 * src/search/downward
 * new-scripts/downward_configs.py
 * new-scripts/downward_configs_nightly.py

(If there are others, I'm not aware of them at the moment.)

I think the only thing that would need to be changed there is to change "()"
used for lists to "[]". There are two ways to proceed:

 1. Update these files. (Note that there are also some cases where
    configuration strings are built programmatically.)
 2. Change the code so that it also accepts "()" syntax for lists.

I'm not sure what I should prefer. The advantage of 1. is that we don't have a
"legacy syntax" which we'll have to keep supporting. The advantage of 2. is that
the new syntax would be backward-compatible, allowing us to more easily compare
before-new-option-parser code versions to after-new-option-parser code versions.

What are your preferences?

[Actually, I now realize that there's a further difference in that the old code
in some cases used "varargs" where the new one requires lists, for example when
using something like eager_greedy(h1, h2, h3) which now has to be
eager_greedy([h1, h2, h3]). So please take that into account in your answers.]

Once this is done, we should also do more thorough tests. I suggest doing a
complete run of all configs we submitted to the IPC and comparing that to the
results we generated for them just before the IPC.

And finally we will have to update the documentation on www.fast-downward.org.

First impression: looks very nice! I'll wait with a proper review and detailed
comments until it's done, but so far, so good. :-)

> Registry<T> stores name-constructor pairs for type *T. Note on
> registration: everything except openlists is registered via this static
> _plugin thing. For templated classes, such a mechanism or similar is not
> possible (at least I didn't find I way, because static members of
> template classes are not necessarily initialized when the template class
> is instantiated). So now, openlists have to be registered on demand, see
> for example the function _parse in general_eager_...cc .

The template use in the open lists is a bit of a pain for several reasons --
maybe we'll find a way to do things a bit differently there eventually. Until
then, I guess we shouldn't worry too much about this.

> Looks great! Can we have a look at your code so far to see the direction that
> everything is taking? Are you working in a repository where we could get read
> access? (I'm sure it's fine code, but with larger modifications/additions it's
> always important to get everyone sold on the design of the code.)

https://bitbucket.org/mogron/fast-downward/src/

Since it's not cleaned up yet, a short outline:

OP::parse_cmd_line(...) is the entry point for parsing.

parser.start_parsing<T>(...) initiates parsing a parse tree as type T.

parser.add_option<T>(...) takes care of administrative stuff that is the
same for every argument, then calls TokenParser<T>::parse(), which uses
template specializations to deal with parsing specific types. Results
are collected in opts.

Registry<T> stores name-constructor pairs for type *T. Note on
registration: everything except openlists is registered via this static
_plugin thing. For templated classes, such a mechanism or similar is not
possible (at least I didn't find I way, because static members of
template classes are not necessarily initialized when the template class
is instantiated). So now, openlists have to be registered on demand, see
for example the function _parse in general_eager_...cc .

For config parameters, I have decided that every parameter has a
keyword, but you can pass the first arguments (until you use a keyword)
by position. IIRC, that's how it's done in python.

> I have worked on the --help option. I've pasted the current output to
> this wiki page:
> http://www.fast-downward.org/ConfigurationOptions

Looks great! Can we have a look at your code so far to see the direction that
everything is taking? Are you working in a repository where we could get read
access? (I'm sure it's fine code, but with larger modifications/additions it's
always important to get everyone sold on the design of the code.)

> Next step is testing if everything is parsed correctly. There isn't any
> big repertoire of configuration options that I could base this on, is
> there?

No, I don't think so. Would definitely be worth having, though.

More generally, I think we should think about moving towards more sane
development practices w.r.t. unit testing.

> Regarding the dry-run stuff, I have a vague idea how this could be
> improved by using some kind of lazy factory. But I will use the old
> method for now, because there are enough small things to get right
> already. Maybe we can talk about this again when the parser is finished
> - it shouldn't be too difficult to change the parser to use another
> method.

Sounds good, I'm a big fan of "one thing at a time". :-) Also, the best design
for this might be more apparent once everything else is in place.

I have worked on the --help option. I've pasted the current output to
this wiki page:
http://www.fast-downward.org/ConfigurationOptions

Next step is testing if everything is parsed correctly. There isn't any
big repertoire of configuration options that I could base this on, is
there?

Regarding the dry-run stuff, I have a vague idea how this could be
improved by using some kind of lazy factory. But I will use the old
method for now, because there are enough small things to get right
already. Maybe we can talk about this again when the parser is finished
- it shouldn't be too difficult to change the parser to use another
method.

Yes -- that's also the only real reason why we have the "dry run".
A better way to support this functionality (separating parsing and argument
checking from object creation) would be great.

We want to delay object creation until needed because some of the things we
create can be very expensive. However, our current solution is not perfect
anyway. For example, if we want to use the same heuristic in the second and
third search iteration, we have to predefine it, which means it'll be created
before the first iteration. (There would be ways around that, but this is not a
problem for our current use cases, so so far we don't care.)

I'm currently converting everything to use the new syntax. I have a
question concerning iterated.cc:
Here, parsing is also happening during execution. Is the (only) reason
for this that each search engine is supposed to be created only when
needed?

Not C++ namespace.

> If it's the latter, I currently allow objects of different types to register
> themselves by the same name - preventing that would take some effort.
> "--help foo" will print help for every object registered as "foo".

OK, that's fine.

Very good, I favored 2 too. I'll use that, including your two slight
preferences.

Regarding the namespace issue, I'm confused: Do you mean C++-namespaces
or just concerning the names given by _plugin(name, _parse)? If it's the
latter, I currently allow objects of different types to register
themselves by the same name - preventing that would take some effort.
"--help foo" will print help for every object registered as "foo".

For what it's worth, I was thinking that we should go to option 2 eventually, so
we might as well do it right away.

I have a slight preference to distinguish between add_option and add_list_option
(or something like that) though rather than using vector as part of the template
parameter, since I find the vector/no-vector distinction different from the
other distinctions in some ways. (For example because those have a special
syntax in the command line.) That would still allow for automatically supporting
vector arguments for all supported arguments, which is indeed a nice feature.

Also, I think that since we need polymorphism for the object types, we should
explicitly talk about pointers since we will need pointers there. So I have a
(slight) preference for:

add_option<int>
add_list_option<Heuristic *>
add_option<Openlist<Entry> >
get<int>
etc.

I have two possibilities for the interface, and can't decide:

1. as in the mockup:
add_int_option, add_heuristics_option, add_openlist_option<Entry>, ...,
get_int, ...

2. templated: 
add_option<int>, add_option<vector<Heuristic > >,
add_option<Openlist<Entry>>, ..., get<int>, ... (and a compile time
error when trying to use a type not supported)

add_enum_otion is included in both

pros/cons I see:
1: 
+ immediately clear what's supported
- clutters up the code with at least ~15 small functions, and internally
those just call the templated version anyway

2:
+ less clutter
+ a bit less to do when extending the parser to support a new type 
+ lists of any supported type can be automatically supported too
- from the class declaration it's not immediately clear what's supported

Preferences?

More generally, it would be nice if
    --help
displayed the list of available search algorithms, heuristics, etc., and
    --help astar
    --help mas
etc. gave explanations on the parameters of the respective search
algorithm/heuristic/whatever.

This is not a must-have since our primary documentation is on the wiki anyway,
but it would be nice to have.

(BTW, we haven't discussed yet whether there should be one global namespace or
whether the different kinds of objects each have their own namespace, i.e., if
it should be possible to have a search algorithm named "foo" and also a
heuristic named "foo". I'm largely indifferent on this, but if it makes the
implementation simpler, I'm definitely not against having a single namespace for
all constructs. If we have separate namespaces, I guess the best thing to do with
    --help foo
would be to give help for all things called "foo".)

The help string was included into the code in case that we want to use it later
for --help messages. Currently it is not used.

When should the help-strings supplied via add_option() be printed? The
current parser just seems to collect them, but maybe I missed something.
Should there be an extra cmd-line option, e.g. --help astar ?

So that we don't forget this: the "dry-run" functionality should remain
supported in some way or other (although it'd be fine if the same/a similar
effect is achieved by a different approach).

Pasting from msg768:

   When using an option string like
      ./downward --landmarks 'x=lmgraph_hm(m=2)' --search "astar(lmcount(x,
       invalid_option=true))" < output
   the planner spends a lot of time computing the landmark graph and then
   complains about the invalid option. Can we go through the complete command
   line in dry run mode once before doing anything else?

> With the enums, I was expecting the first entry in the vector to map to 0, the
> second to 1, the third to 2, etc., so the numbers would come from vector
> position. The option parser wouldn't work with (or no about) the actual enum
> definitions; I was just using the word "enum" in the method name to indicate the
> intended purpose of this.
> 

Okay. So, conf.get_enum(...) returns an int. There is no implicit
conversion from int to enum, so a cast is needed, e.g.
merge_strategy(MergeStrategy(opts.get_enum("merge_strategy"))) in the
initialization list.

With the enums, I was expecting the first entry in the vector to map to 0, the
second to 1, the third to 2, etc., so the numbers would come from vector
position. The option parser wouldn't work with (or no about) the actual enum
definitions; I was just using the word "enum" in the method name to indicate the
intended purpose of this.

An alternative would be for the option parser to nut use numbers there at all,
but rather use strings for everything and leave it to the heuristic constructor
to match this to enum values if desired.

Thanks. 
I'm not sure if the add_enum_option stuff is possible in this way. There
is no way to look up an enum value by a string (or vice-versa), at least
not without using ugly macros. The usual solution for this seems to be
to use a lookup table, e.g. a map<string, MergeStrategy>. Passing that
to the parser would work, but it's a bit more typing again. E.g.,
instead of:
vector<string> merge_choices;
merge_choices.push_back("linear_cg_goal_level");
merge_choices.push_back("linear_cg_goal_random");
...

it would be necessary to write

map<string, MergeStrategy> merge_choices;
merge_choices["linear_cg_goal_level"] = MERGE_LINEAR_CG_GOAL_LEVEL;
merge_choices["linear_cg_goal_random"] = MERGE_LINEAR_CG_GOAL_RANDOM;
...

Other than that, it all seems possible, and mostly congruent with what I
tried this weekend. In case of interest, I have uploaded the current
state of my implementation experiments to
http://dl.dropbox.com/u/9599789/parser_exp.zip (not cleaned up, because
it's late). The relevant files are parser_test.* and test.cpp.
Currently, it's only possible to parse built-in types and vectors of
them. And there's no error handling. But essentially it could work like
this, I think, and with barely any code duplication.

I've posted a mockup for new parser usage for merge-and-shrink heuristics here:

    http://codereview.appspot.com/3470041

The side-by-side diff view is probably the best comparison of old vs. new.

The new code would be much shorter than the old if it didn't include all the
enum names in the parser code (which is a new feature compared to the old code).

It's still a bit complicated due to the complicated way that the max_states and
max_states_before_merge options depend on each other in terms of default values
etc. Maybe that code belongs into the constructor instead; not sure.

I'm not fully clear on how we should support the old "dry_run" feature, which
probably means we should handle it in a similar way as before for now. (Which is
what I did.)

Moritz, let us know if you want another mockup for another part of the planner.

In reply to msg740: I'm not sure how much I like the option string idea; it
looks to me a bit more general that we might want to support. For the most part,
our syntax is inspired by/identical to function call syntax in Python, and I
don't think it needs to support more generality than that.

Regarding bison: I've had a number of incompatibility issues with bison in the
past, so I'd rather avoid it. I think the syntax is still simple enough to
handle with a direct parser implementation (e.g. a simple recursive descent parser).

Maybe before doing anything else, we should specify the actual option language
we want to parse? I guess we'll need some kind of high-level documentation of
that anyway for other people who are going to extend the planner.

Moritz, if you want to write up a draft for that in the wiki or by email, that
would be good. Alternatively, I could do this, or we could meet between the two
or three of us.

I think that some kind of abstract syntax tree data structure would be useful
(independently of whether we want to refactor or rewrite from scratch).

"Regarding the internals of the parser, I see two possibilities:
1. keep (most of) the old code, build abstractions (like parse(inp,
format)) on top of it
2. replace old code, use a parsing library"

Of course a third option is to build a new parser myself from scratch. Instead of just tokenizing the input before further processing, I would parse it into a tree-like structure.

I've thought about this a bit now, and here's how I imagine one of the
create()-functions could look like:

SearchEngine *GeneralLazyBestFirstSearch::create(const string &config,
bool dry_run) {
      ostringstream configFormat;
      configFormat << "(openlist(Openlist), reopen_closed(bool)=false,
g_bound(int)=" 
                   << [numeric_limits<int>::max()] 
                   << ", preferred_list(vector<Heuristic *>))";

      ConfigurationObject configuration = 
          Parser::instance()->parse(&config, configFormat.str());

      GeneralLazyBestFirstSearch *engine = 0;
      if (!dry_run) {
                  engine = new
        GeneralLazyBestFirstSearch(configuration.getOpenlist("openlist"),          configuration.getBool("reopen_closed"),                         configuration.getInt("g_bound"));	

engine->set_pref_operator_heuristics(configuration.getHeuristicVector("preferred_list"));
      }

      return engine;
  }

So when implementing a new SearchEngine/Heuristic/..., the implementor
only has to specify the format of the configuration string
(configFormat), and then decide what to do with the parsed configuration
values.

A ConfigurationObject would be a collection of maps (one for each
datatype - int, bool, double, OpenList, vector<Heuristic>, ...) and
corresponding get()s. Might have to be templated, because of the
templated OpenList. Something simpler would be better, but I couldn't
think of anything (except a map using boost::variant, but apparently you
do not like boost).

The parse(string inp, string format) function would analyze format and
parse inp accordingly, using lower level functions like
parse_heuristic() etc.

Regarding the internals of the parser, I see two possibilities:
1. keep (most of) the old code, build abstractions (like parse(inp,
format)) on top of it
2. replace old code, use a parsing library: since the general
configuration format seems to be not that simple (is it correct that
"()"-nesting can be arbitrarily deep?), a general parser for
context-free languages (like Bison) might be necessary for this
approach. This appears to me as a bit of an overkill, but the result
might still be nice.

Now before I continue thinking about this, I wanted some feedback.

In the current implementation, the definition of a parser for a new
heuristic/search/open list/... is still very low-level. It would be nice to have
a more abstract way of specifying the parameters and their types.