TODO:
* cast and transform the return values
* handle errors
* generate help from the information in the registry
* add the option to access (enriched) ASTNode
* allow validation and rewriting options
* add let syntax and variables
* rewrite command line string in the presence of predefinitions
* use the new option parser instead of the old one for all existing plugins
* fix differences in generated help compared to the old version
* determine type of expression based on expression
* check bounds
* reimplement or get rid of get_unparsed_config
* Generate correct help if no document_title was not used
* check TODOs added in the branch
* remove code that is no longer used (in particular, src/search/ext/*; also 
requires update of License in README.md)
* fix issues in Lama
* make the code pass our automated tests
* merging issue1073 first will make this issue easier to review

Errors to check
Lexer
- Invalid token:  single line, multiple lines

Syntax Analyzer
- General
-- Empty input
-- Unconsumed tokens after parsing
-- Exhausted input stream
-- Incorrect next token
- Argument Parsing
-- Duplicate keys in keyword arguments
-- Positional argument after keyword argument
-- Keyword argument without value
- Let Parsing
-- Invalid identifier
-- Too few parameters
-- No trailing commas after elements
- Function
-- Comma without arguments
-- Comma forgotten between arguments
-- no trailing commas after arguments
- Literal
-- parse_literal is only called for valid tokens
- Nodes General
-- type of next node can be converted to required type

Semantic Parser
- Let
-- Variable of let expression is not used
-- Variable is used multiple times, first with correct and second with 
~~incorrect type
- FunctionCall
~~-- Argument does not evaluate to an object of valid type
-- Missing mandatory argument
-- Definition of argument via positional and keyword argument
-- more arguments defined than the feature has
-- float value used as argument for an integer
- List
-- arguments of incompatible types (i.e. multiple evaluators are compatible, 
evaluator and patterngenerators are not)
- Literals
-- value is not a valid enum choice

We handled the remaining reviewing comments. As part of this we changed the way we create a traceback. Previously, we manually opened and closed blocks. Now we generalized an existing class in the utils namespace called TraceBlock. It was specialized to trace memory usage which is still possible as a special case now.
Creating a TraceBlock in a scope now opens a block that is automatically closed when the TraceBlock object goes out of scope.

With these final changes, we re-ran experiments from msg10937. The data replaces the old experiment data online and is available under the same link:
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1040/data/

After initial problems where we observed a ~5% slowdown in most configs, we confirmed that this was caused by the specific compiler (g++-8.3), possibly an unfortunate order in which the files are linked or some other compiler/linker magic. There are no problematic changes with g++-10 and clang-12, so we accepted the change with the old compiler and merged.

Thanks everyone!

I finished reviewing the parser and also took a quick look at  
src/search/command_line.* and src/search/planner.cc. I left some small comments in 
the pull request, but I'm also happy if you merge it as is.

Great! :-)

The results of the experiments look fine to me. There are some unexplained errors but all of them can be explained by things other than the code change (warnings about large logs, translator crashing in organic synthesis, configs that do not support axioms/conditional effects ran on domains with those features). The new and oold code have roughly the same coverage (+-1) and report the same types of errors. The timing scatter plots look like the noise we are used to, and I didn't see any spikes in memory usage.

Most importantly, all the aliases and portfolio configurations parse :-)

So I think from the experiment-side, this issue is ready to merge.

I ran an experiment with all aliases, all portfolios, and some handcrafted configs to cover operator-counting, potential heuristics, and CEGAR, which are not used in the aliases.

I didn't check it in but instead used our in-progress archival solution, so we can test this out as well:
https://ai.dmi.unibas.ch/_experiments/ai/downward/issue1040/data/

Just to keep this up to date:

Simon reviewed the changes in driver/* and misc/*. Remo and Salome will review the new code in src/search/plugins and src/search/parser. Someone will also check src/search/command_line.* and src/search/planner.cc.

We will also set up a short experiment to test the aliases and portfolios.

The code is now ready for review. Since it is a large diff, that might look scary, I'll suggest a reviewing strategy here. Going through the files in this order should make reviewing easier. Note that if you start a review in Github (I think the first time you write a comment, Github suggests this), you can mark files as "viewed". Those files will collapse and you can concentrate on the rest better. This is specific to your account and you can undo it if you want to consider a file again.

src/search/utils/language.h
---------------------------
A new function to get a type name before we register it. This should
only be necessary in cases where a plugin registering a type is missing.

src/search/plugins
------------------
While some files already exist, I think it makes sense to review this as new code.
The descriptions in https://www.fast-downward.org/ForDevelopers/Blog/TheNewOptionParser
can guide you through the code.

For the first part (features, plugins), the relevant code is in
  plugin.*, plugin_info.*, bounds.*, and to some degree types.*

For the next part (registries), I'd look at
  raw_registry.*, registry.*, and registry_types.h

The remainder of this directory is
  doc_printer.* (used to generate the wiki pages)
  options.*, any.*, and construct_context.* (used in the construction of features)


src/search/parser
-----------------
The blog article also explains the general setup and you can review the code in this order.

Maybe start with errors.* before looking at the actual parsing.

The first step is in token_stream.* and lexical analyzer.*.

The next step then is in syntax_analyzer.* and abstract_syntax_tree.h
(The header of abstract_syntax_tree.h should be sufficient to see what is generated, the cc file is mainly important for the next step).

The final step is in abstract_syntax_tree.* and decorated_abstract_syntax_tree.*


src/search/command_line.* and  src/search/planner.cc
----------------------------------------------------
How to deal with the command line, the old --evaluator syntax, and calling the new code.


Actual plugin definitions
-------------------------
The changes in all of the following files define the new features and plugins.

    src/search/{cegar,evaluators,heuristics,landmarks,lp,merge_and_shrink,
                open_lists_operator_counting,pdbs,potentials,pruning,
                search_engines,tasks}/*
    src/search/utils/{logging,rng_options}/*
    src/search/{abstract_task,evaluator,heuristic,open_list_factory,
                operator_cost,pruning_method,search_engine}.*

One small special case is in merge_and_shrink_algorithm and
merge_scoring_function_miasm where we can get rid of an option that was a bit of
a hack previously.
Another special case is iterated_search that was a big hack before and is a
smaller hack now.

Adapting Calls to new Syntax
----------------------------
All changes in driver/* and misc/* adapt configurations we have (aliases,
portfolios, test cases) to the new syntax.


Other Changes
-------------
* src/search/ext/tree* --> We don't use this code anymore.
* README.md, src/search/DownwardFiles.cmake --> These changes deal with the removed files

I'm also in favor of a smaller issue. We can defer the ifunitcost() syntax for now.

I also scratched out "check TODOs added in the branch" in the summary because we handled this. I added one point about issue1073 and one point to make our tests pass. Currently, compilation on Windows and Mac fails, and our style and standard config tests fail on Linux.

(and I forgot to update the summary)

I conclude we choose something like option `C` with an `if` syntax. 

Should we include the `if` in this issue? We still support the old syntax, thus, excluding it has no impact on the functionality and makes the issue smaller.

I vote for a smaller issue (`if` syntax in new issue), this makes reviewing easier and increases the chances of finishing before the sprint.

I checked that the list of errors from the issue summary is successfully detected and ''understandably'' reported.

> Malte, what's you opinion on the "--evaluator" syntax? Should we
> treat this as syntactic sugar that we plan to support in the future,
> or as a deprecated syntax that will be removed eventually?

Deprecated syntax that will be removed eventually.

> We printed a deprecation warning if this syntax was used and had some
> text in the automatically generated doc about using the let-syntax instead,
> but I think Patrick removed the warning after my message about treating it
> as syntactic sugar. I'm fine with both options, and it will not make a
> functional difference for the pull request, only the way we communicate this.

We don't really have a tradition of printing deprecation warnings from the code,
so I don't think it's necessary. I think it's generally enough to tell people how to adjust their command-line strings in the release comments.

Let's go with the version that has the repetition for now then.

Malte, what's you opinion on the "--evaluator" syntax? Should we treat this as syntactic sugar that we plan to support in the future, or as a deprecated syntax that will be removed eventually? We printed a deprecation warning if this syntax was used and had some text in the automatically generated doc about using the  let-syntax instead, but I think Patrick removed the warning after my message about treating it as syntactic sugar. I'm fine with both options, and it will not make a functional difference for the pull request, only the way we communicate this.

Regarding the "if unit cost" switch, since this is currently the only check that can be made, I don't think repetition is a big deal.

The natural progression of where we're going is a conditional expression. You mentioned an "if(condition, x, y)" syntax. For what we currently support, I think a more restricted "ifunitcost(x, y)" syntax would make more sense.

And of course we can have something like
--if-unit-cost x
--else y
or some variant of this as a stepping stone.
(We could have actually have "--if-unit-cost x y" without the "--else" because unlike previously, we'll always have a single expression in between and therefore don't need delimiters for the conditional blocks like we did before.)

What you described is roughly what we currently do in `parse_cmd_line` and `replace_deprecated_predefinitions`.
1. check which commandline arguments are applicable
2. parse them from front to back. Every predefinition is transformed to a let expression around the `--search` argument.

But additionally, we output a deprecated warning:

            utils::g_log << "Deprecated predefinition format '"
                         << arg << " variable_name=variable_definition'." << endl
                         << "Use: let(variables_name, variable_definition, expression)" << endl
                         << "Example: let(h, lmcut(), astar(h))" << endl;

 Easiest is then to say, we still accept this syntax and remove the deprecated warning.

Did we decide to make the --evaluator syntax deprecated? We could also keep it but treat it as syntactic sugar, i.e., it is something that will always be resolved before passing anything to the parser. We could then rewrite the options in two steps: first resolve all --if-unit-cost , --if-not-unit-cost, and --always. then handle all predefinitions in the resulting list. I guess this is also more or less what is done in the old code.

In the long term, I like option C, the if-then-else block. It should be easy enough to add and fits the general theme. But I would not add this as part of this issue.

Our new `let` syntax lose functionality regarding `--if-unit-cost`. 
Previously, you could predefine an evaluator/landmark factory based on 
whether the given task has unit costs or not and then use one of the predefined in the search, e.g.
```
--if-unit-cost --evaluator h=ff() --if-not-unit-cost --evaluator h=lmcut() --always --search "astar(h)"
```
To achieve the same, we need to write now:
```
--if-unit-cost --search "let(h, ff(), astar(h))" --if-non-unit-costs --search "let(h, ff(), astar(h))"
```
It is strange to mark the old syntax as deprecated when the new one is 
less powerful. We can achieve the old effect with our automatic translation 
from old syntax to new syntax, but then we are using again the old style 
predefinitions:
```
--heuristic h=ff() --search astar(h)
->
--search let(h, ff(), astar(h))
```

I see the following options:
A: So be it (for now).
B: Introduce `--predefine key=value` instead of 
`-evaluator/heuristic/landmark key=value`. `value` can be a `let` expression.
Predefine checks nothing. It just applies the transformation 
`--search let(key, value, SEARCH)`. If multiple `--predefine` are given, 
then are just nested. This would be a very simple solution.
C: Introduce an `if(cnd, true-block, false-block)` in our syntax. 
Just use it inplace:
`astar(if(unitcost,ff(),lmcut()))`
Use it with a let expression:
`let(h,if(unitcost, ff(), lmcut()), astar(h))`
But this becomes repetitive if you want to predefine multiple things for 
unit cost tasks respectively for non-unit-cost tasks:
`let(h1,if(unitcost, ff(), lmcut()), let(h2, if(unitcost, ipdb(), m&s()), eager_greedy([h1,h2])))`
This rephrasing
`eager_greedy(if(unitcost, [ff(), ipdb()], [lmcut(), m&s()])`
is not possible, if you want to use an object multiple times
(e.g. as heuristic and for the preferred operators)

To simplify the merge, I suggest to merge some of the changes we did here first. I created issue1073 for this.

The issue with Lama was caused by the way we handled lazily constructed values. It works now.

I also implemented some version of get_unparsed_config that just passes the unparsed config along for function nodes specifically.

While testing this, I ran into an issue with the alias "lama". I didn't have time to look into it, but from first glance it looks like iterated search is not accessing the nested searches yet.

We worked on checking bounds. We first tried a way where arbitrary constraints could be passed on a function argument but that turned out to hide a lot of subtle usage errors like passing an int bound to a double parameter or using the "infinity" value of int when you would like to use a double. We now left the system as it is and only introduced a node to check the bounds on the enriched AST level.

These two points on the TODO list are now done at least in a first iteration.
* fix differences in generated help compared to the old version
* determine type of expression based on expression

Patrick, Simon and I worked on determining the type of an expression based on the expression alone. This required adding classes to describe our types with more detail than type_index can. With these classes, we could also cover some functionality that was implemented in the registry so far. For example, we added the option to ask a type for it's name rather than asking the registry for the name of a type. For types that are defined by CategoryPlugins and the new EnumPlugins, we also included the documentation in the type (like a doc string in Python).

We unfortunately had to introduce another global singleton to have a central place for managing types. If we want to avoid this, the problematic case is how to access the already registered types in calls to `add_option`. We could pass them through to there but that would mean changing all plugins and `add_option` calls. An alternative would be to store a reference to a type registry in all Feature objects but we were not sure if this duplication would be too bad.

There are some other rough edges in this new code. One thing that seems a bit odd is the inheritance in the type classes.  The base class offers virtual functions to check if the object is of a certain derived type and functions to access the content of the derived type. Malte, you mentioned that this is fine to avoid having to cast the objects, but this was when there were fewer cases and less functionality in the base class. Is this still a good idea even though the number of derived classes grew and their functionality is almost completely distinct? You can see the code here, if you want to have a look:
https://github.com/aibasel/downward/blob/8fce6605/src/search/plugins/types.h
https://github.com/aibasel/downward/blob/8fce6605/src/search/plugins/types.cc

I also removed the old options code, since the new code now can stand on it's own.

I added a first list of user input errors we want to catch (and thus check) to the summary. Feel free to adapt with checks I have forgotten.

I wrote a file which triggers the errors, only for the semantic part some checks are not finished. See attachment

> * Generate correct help if no document_title was not used
>   I'm not sure if this is still the case but leaving out a document title
>   used to generate sections with an empty heading. it should fall back to the
>   key of the plugin instead.

This was already fixed.

I added the following points to the summary based on previous discussions and reviews:

* determine type of expression based on expression
  This will require a slight redesign of the parser classes as now a node in
  parse tree should be able to determine it's own type. This gets a bit
  complicated with nodes for "[]" (list of ???) and "42" (int?, float?).
  We already discussed this and I think we came to a solution, but I cannot
  remember what it was.

* check bounds
  Currently we set bounds on arguments but never check them 

* reimplement or get rid of get_unparsed_config
  We used get_unparsed_config to give a description to heuristics.
  Currently, this always returns the string "TODO".

* Generate correct help if no document_title was not used
  I'm not sure if this is still the case but leaving out a document title
  used to generate sections with an empty heading. it should fall back to the
  key of the plugin instead.

* check TODOs added in the branch
  When implementing the first iteration, we added a lot of "TODO"s. Before
  merging, we should make sure we covered them all.

All old plugins are now switched to the new classes. The generated help is not exactly identical, though:
* In some places the order of some notes changed, (I don't think this is a problem).
* Enums without item documentation still generate lists it the wiki (I would suggest to just add the missing documentation).
* Values with a default value of "NO_DEFAULT" used to generate "= <none>" but don't do so anymore. Is this how we want to display this? As background information: in this case, the argument can be left unspecified and will then not be present in the parsed options. Arguments without a default value generate an error if they are left unspecified, so using the default value "NO_DEFAULT" makes the argument optional without specifying a default.

 

I updated the summary to deal with those differences in the help output.

Help is now generated from the new registry. We will only be able to check if it does the same thing as the old code once we switch over all plugins, though.

A split into two directories sounds good to me. The more the two parts can be decoupled, the more sense it makes. From what I know so far about the code, I can only comment on this in general terms.

Looking at this again, options.* and any.h belong to "plugins", not "parser", so that would also mean that most classes only need to include headers from "plugins".

One thing Patrick and I discussed was that we could probably split the directory "parser" into two directories (= CMake plugins):

parser:
  lexical_analyzer.*
  syntax_analyzer.*
  abstract_syntax_tree.*
  enriched_abstract_syntax_tree.*
  options.*
  any.h
  errors.*

plugins:
  plugin_info.*
  plugin.*
  bounds.*
  raw_registry.*
  registry_types.h 
  registry.*

If we are not overlooking something "parser" would depend on "plugin" but not the other way around. To define a plugin, you'd probably still need includes from both modules (plugins/plugin.h for the plugin class, parser/options.h for constructing the object).

Should we still split the code to decouple it a bit more?

We are done with the let/var syntax and rewriting the old-style predefinitions.

Error-handling and help generation is still missing before we can start switching classes to the new parser.

Malte if you have time for a review, this would be a good time to review the main part of the changes (the missing parts are relatively independent and if we want to do some major changes it would be good to know this before we touch the existing plugins). The "reviewing guide" in msg10580 is still up to date. By now we removed the unused semantic_analyzer files that are mentioned at the end of that message.

I added a TODO to the summary: once we have all the functionality in place, we have to use the new code for all plugins.

Yes, the plan is to get rid of this again once we no longer need it for the iterated search. I also put comments about this in the code. So let's leave it in this state for now.

The virtual clone method is one of the oldest design patterns. Makes sense to me. I understand correctly that the intention is to remove this again later? In that case, I'd do it this way and move on. Otherwise I'd spend more time on the design. (I haven't looked at the diff.)

I added a hack to support the lazy parsing we use for the iterated search. In theory, this is not that complicated, but in practice, we have to make our parse tree copyable.

This is complicated by the fact that the parse tree is not a single class but a tree of objects that are from different derived classes (ListNode, FunctionCallNode, etc. all derived from EnrichedASTNode). When copying, we only have a polymorphic pointer to the base class, so we don't know what class to construct. This page (https://www.fluentcpp.com/2017/09/08/make-polymorphic-copy-modern-cpp/) mentioned the "classical solution" to this problem is a virtual "clone" method, that is overridden in the derived classes, so they construct the correct type. Like this:

unique_ptr<EnrichedASTNode> ListNode::clone() {
  return make_unique_ptr<ListNode>(*this);
}

The clone methods work for creating a copy of the parse tree as a polymorphic unique_ptr<EnrichedASTNode> but we then also have to store it in an Options object, which nests it inside an Any object. Any requires its content to be copyable, so the unique_ptr doesn't work and we want a shared pointer instead. To do so, I added a second set of clone methods to all classes that return a shared pointer instead of a unique pointer. I don't see a way around this, because internally unique pointers are used, so we cannot just clone everything with shared pointers.

Anyway, my point with this rant is that the hack requires a lot of code changes that we only need for the hack. I would have liked to keep the hack more local so it doesn't infect too many other parts while we are still working on the component interaction problem (it can disappear after that). But I could not think of a way that would lead to a smaller diff. 

If you want to see the diff, it is in this commit:
https://github.com/aibasel/downward/pull/95/commits/2a5799b4f28f8d8869db0532e9c165602a187564

We added a way to preprocess the options. This can be used for validation (like opts.verify_list_not_empty() in the old code) or for creating a new options object based on the old one (as ipdb and astar do).

I've added that removing ext also requires updating README.md.

One more TODO: once we are done, we should remove code that is only used in the old parser. The directory src/search/ext/* can probably go completely and is easy to forget.

Casting and transforming the return values from an options object is now implemented.

I agree that once we switch to the builders, both of the points you mentioned should not be necessary anymore on the parser side. If we want to do this in two steps, we need them as a temporary solution.

I'll ask around if anyone else wants to do a review. I would be good if more people are familiar with the design anyway.

Thanks, Florian! I had a look at the pull request, but I won't find enough time to look at it in detail during the sprint, it's too much for that. If you want, we can arrange a meeting to talk about things.

I looked at the pull request a little bit and have no further comment from this, but this might be different with more time. Perhaps someone else can review it?

Regarding the summary:

"* add the option to access (enriched) ASTNode"

The way this is currently done in the iterated search is absolutely terrible. Once all pieces are in place, there should be no need for something like this; this is one of the things we want to fix while addressing the component interaction problem. In the meantime of course it's fine to design something temporary to address the need we have, but this shouldn't influence the final design.

"* allow validation and rewriting options"

Many of the things mentioned here sound to me like things that would happen on the builder side and are not relevant to the option parser. Perhaps this is also something where the design will need to evolve over time, but my instinct would be to be minimalistic with these kinds of things on the option parser side.

I added the major TODOs that are still left. 

* cast and transform the return values
  A vector<vector<int>> is currently generated as a vector<Any>, where the Any holds
  another vector<Any>, where this Any holds an int. We have find a way to turn this
  into a vector<vector<int>> inside options.get<vector<vector<int>>>().

* handle errors
  We completely ignored this so far and have only placeholder error messages.

* generate help from the information in the registry
  We also completely ignored this so far.

* add the option to access (enriched) ASTNode.
  The plan is to allow not parsing part of the config. The iterated search current
  needs this, so the (potentially expensive) components of the second search are not
  constructed before the first search finished. This is probably no longer needed
  once we handle the component interaction problem, so for now, we could live with a
  hacky solution.

* allow validation and rewriting options
  Our plan here is to call a virtual function in Plugin<>::construct() after the
  options are constructed and before the object itself is constructed. This function
  should work like a filter in lab, i.e., it can validate the options and fail if they
  are not acceptable (e.g., empty list of heuristics). But it can also change things
  in the options (e.g., set an argument that functionally depends on a other
  arguments) or even construct some objects, set them into a new Options object and
  return the new one. This way, we could handle almost all of the special cases we
  have so far.

* add let syntax and variables
  See msg10476. We have not worked on this so far.

* rewrite command line string in the presence of predefinitions
  See msg10476. We have not worked on this so far.

Most of what I wrote in msg10510 and 10509 is still up to date but we had to change the details a bit. For example, it is not possible to call a virtual method in the constructor of plugin as we planned, so we now handle the code in the constructor. This means that the plugin is registered before the meta-data is filled in but this is OK, as the raw registry stores the plugin as a pointer, so the order of filling in the data and registering doesn't matter.

We also added an additional step in the parsing process that creates an enriched version of the abstract syntax tree from the original AST. This way, we do not have to modify the objects as the information about function signatures is added from the registry.

We prepared a pull request for the current state at:
https://github.com/aibasel/downward/pull/95
it adds the new code in a new CMake plugin and namespace, so it doesn't conflict with the old code, while we are working on it. In command_line.cc and parser_tests.h we hacked in a test case that should not stay like this, but it shows how the external interface should change (we might hide some of the individual steps used in command_line.cc behind a nicer interface).

For reviewing the changes, I would recommend following the order of the parser:

1) lexical_analyzer.* parses the string into a stream of tokens.
2) syntax_analyzer.* parser the token stream into an abstract syntax tree
3) abstract_syntax_tree.* represents this tree and has methods to create an "enriched" copy of itself.
4) enriched_abstract_syntax_tree.* represents this enriched data and has methods to construct the objects. In this step we use the classes Options and Any (from options.*, any.h). So far, these are copied from the old module and probably need some more work.

Steps 3 and 4 rely on the plugin data which is collected in the registry, which has its own life cycle and can be reviewed independently:

1) plugin_info.*, plugin.*, bounds.* define the classes we create and store in the registry. There are three kinds of plugins: TypePlugins define the types of plugins that can be created (SearchEngine, Evaluator, ...), Plugins define the actual things we want to parse (EagerSearch, BlindHeuristic, ...), GroupPlugins define groups that we can sort plugins into for structuring in the wiki (PDB heuristics, Potential heuristics, ...)

2) In the plugin constructor, the plugin registers itself in the raw registry (raw_registry.*) that collects all of this data without error checking. It uses types from registry_types.h 

3) The raw registry then can create a Registry (registry.*) that contains the curated information of the raw registry. (We need this two-step process because we don't know in which orders plugins are created).

There are two more files that I didn't mention so far:
- errors.* should do error handling for things going wrong in the parser. We didn't work on this yet and everything related to errors is still inconsistent (we have to think this trough once the other parts are in place).
- semantic_analyzer.* is an old version of the third level of parsing. We probably do not need it anymore.

On the parser side, we plan to do two passes through our parsed data with the registry. The first one checks that all parameters are well-typed, transforms positional arguments into keyword arguments and  sets default values for unspecified arguments. At this point, we also check that no arguments were given to the function that the function did not expect.

In the second pass, we create the actual objects (or the builders once we introduce those). This will look roughly like this.

Any parse(parser::Function f, Registry registy, type_index type_id) {
    unique_ptr<PluginBase> plugin = registry.get(type_id, f.name);
    Options opts;
    for (auto parameter : plugin->get_paremeters()) {
        opts.set(parameter.name) = parse(f.get_parameter(parameter.name), registry, parameter.type);
    }
    return plugin.construct(opts);
}

We use Any to pass parameters from `plugin.construct` to the options object because they are stored as Any within options anyway and we could not figure out how to do this with templates. Since the type safety is checked in the first pass, we think this is acceptable.

We started writing a lexical and syntactical parse to parse the command line text first into a stream of tokens and then into a recursive data structure that consists of literals (a single token, e.g. "infinity"), lists (e.g., [1,2,3]), and "functions" (e.g., ff()). Functions have a list of posititional and keyword arguments which are themselves literals, lists or functions.

As a next step, we want to change the way plugins are defined, so we can extract the necessary meta data
to this abstract data structure into something more concrete. Currently, a plugin definition mixes parsing and this meta data definition so we will have to change this in all plugins. But we think we found a way that is not that disruptive and also works with our future plans for the component interaction problem.

We plan to use the actual plugin objects but with a new Plugin class (currently these static objects are just created so their constructor is called and registers the plugin). The new class will look roughly as follows and will be stored in the registry. We have the same issue as the current code that we don't know the creation order of the static objects and will use the same solution of first storing everything in a provisional list and then transform this into the real registry before parsing.

class PluginBase:
    PluginInfo metadata;
public:
    PluginBase() {
        initialize_metadata();
        RawRegistry::instance()->register_plugin(this);
    }
    virtual type_index get_type() = 0;
    virtual Any construct(const Options &opts) = 0;
    virtual void initialize_metadata() = 0;

    add_document_synopsis(string, string);
    add_document_language_support(string, string);
    add_document_property(string, string);
    add_document_note(string, string);    
    add_option<T>(string key, string help, string default, ...);
}

The `add_*` methods are equivalent to the ones currently used in the OptionParser so the diffs should remain readable. In contrast to the current implementation, they should only store the data in the plugin instance. The new method `get_type` is used to communicate the `return type` of the plugin (e.g., SearchEngine for `astar()`). The method `initialize_metadata` should be overridden in derived classes and replaces our current `_parse` methods. In it the `add_*` methods are used to set up all documentation and options. It is called in the constructor before registering the plugin. The `construct` methods currently should just construct the actual parsed object (and possibly do error checking). Later, they will return the builder objects instead. To avoid some code duplication with the most common case, we can implement a derived class like this: 

template<typename Base, typename Constructed>
class Plugin<T> : PluginBase
    Any construct(const Options &opts) override {
        return Any(make_shared<Constructed>(opts));
    }

    type_index get_type() {
        return typeid(Base);
    }
}

The FF heuristic for example would then be defined like this:

class FFPlugin: Plugin<Evaluator, FFHeuristic> {
    void initialize_metadata() override {
        /*
          Use add_* methods from Plugin base class to set
          documentation and options. This should be a small
          diff to the current _parse method.
        */ 
    }
}

static FFPlugin _plugin;

We had an initial meeting about this and discussed the general parser design. In a first step, we have to do a lexical analysis, splitting the string into tokens.

We support the following tokens: ( ) [ ] = , NUMBER WORD
- NUMBER can be any integer or float and we also support numbers like "1e8", "1M", "0.1k", "infinity"
- WORD can be any identifier starting with an underscore or letter and containing only underscores letters and numbers ("infinity" is a reserved word, and not allowed as a WORD).

We plan to use regular expressions for the lexical analysis.

After the lexical analysis, we have to parse the string recursively into a parse tree and then transform the parse tree by adding more information. To do so, we have to adapt our plugin mechanism to make the information about names and types of parameters of each plugin available to the parser. Previously, this was integrated into the actual parsing but for this issue, we aim for a stronger separation of parser and parsed content.

In issue559 we discussed a new design for our option syntax that we will eventually need to support our solution to the component interaction problem.

The new parser should support the following syntax
  let(h1, ff(), let(h2, cg(), eager_greedy([var(h1), var(h2)], preferred=[var(h1),var(h2)])))
and otherwise support all the old features.

Predefinitions (--evaluator h=ff()) should be rewritten to the new syntax internally before parsing.