Part of issue207. Blocked by issue724.

Thanks, Salomé! So this clearly needs some more thought. One thing to consider is that many of the ways in which evaluation contexts are created and used in the current code are really hacks, so I think we have a quite large design space for possible solutions.

For example, the question whether g-evaluator evaluations should be counted as evaluations hints at a design flaw of the current statistics output. It would make much more sense for evaluation statistics to be directly associated with specific evaluators, and an output like "There were X evaluations" with no further explanations must necessarily be confusing given that several evaluators are already involved in something like an A* search (usually a heuristic, a g evaluator, and a sum) and it is not clear what this referred to. Even more so, when instead of a simple heuristic we use a max evaluator over several heuristics etc.

I am still quite hopeful that there is a clean solution hidden among all the current complexities, but the major issues you mention don't look simple. Perhaps it is indeed the case that lazy search needs to evaluate both states and edges, and hence the 1:1 tie to the open list is not what we want. But I cannot really say much about this without having looked into this much more deeply.

I implemented a prototype for the suggested design. It seems to work, but is very ugly and hacky at the moment. This is why I didn't push it to Jendriks repo but instead made a new repo. You can see the diff here: https://github.com/salome-eriksson/downward-issue751-prototype/compare/41694b17b3117562fd9d6af1098465e954c4152f...issue751

I went with the design to template EvaluationContext with states (=StateID) or edges (=pair<StateID,OperatorID), which also enforces that OpenLists can only have EvaluationContexts of the same type (i.e. you cannot pass a StateEvaluationContext to a EdgeOpenList).
While I at first thought that this makes a lot of sense, there are quite some issues with this design:

1)If we want to evaluate a state in lazy search right before it gets expanded, we need to do this with an EdgeEvaluationContext (with OperatorID::no_operator). This goes against the idea of EdgeEvaluationContexts, which should evaluate the edge if possible and only fall back to evaluating the parent state if they can't do edge evaluation. For GEvaluator that meant that I needed to add an if in the compute_result method which returns the g-value of the parent if no operator is given, and the g-value of the child otherwise. 
2) It makes caching messy. If we could use a StateEvaluationContext for evaluating the state before expanding, then it would be clear: cache estimates from StateEvaluationContexts, and don't cache estimates from EdgeEvaluationContexts. (This works because GEvaluator actually caches its estimates in the notify-state-transition method.)
3) Since the template types are identical to the ones from OpenList, we can only pass StateIDs to the constructor of EvaluationContext, when before we passed a const State &. This means that I now need to create the state in the constructor and it lives in the EvaluationContext. If we want several contexts for the same state, we thus have several copies.

There are also several minor things that are still ugly (usually denoted with a TODO in the code):
 - EvaluationContext always has a OperatorID member, with OperatorID::no_operator being set for StateEvaluationContext. If we try to access it, we get a cerr message but return no_operator anyways (we could of course also exit instead)
 - I defined aliases for the templated EvaluationContexts, but for some reason I needed to repeat them in evaluator.h and don't really understand why this is necessary / what we can do to avoid it.
 - I duplicated a lot of code for the compute_result method of Evaluator.
 - I'm not sure if we should count it as an evaluation when GEvaluator computes the g-value for a EdgeEvaluationContext 
 - I needed to move the entire implementation of EvalutionContext in the header file and am not sure if/how we can avoid this.
 - When creating the EvaluationContext in lazy search, we had a note about why we pass preferred=true. I don't know if that note still applies.

Jendrik created a pull request and implemented the changes to GEvaluator and eager search: https://github.com/aibasel/downward/pull/52

For lazy search however the current code design does not work: Evaluators can only evaluate states. The GEvaluator needs to evaluate a state when it is put into the open list, but at that point the state does not exist yet. This is because the open list for lazy evaluation stores "edges", i.e. the parent state and operator, instead of the actual state.

In a meeting today Malte suggested that the Evaluator class can be extended to evaluate those edges. The default implementation would simply evaluate the parent state, but Evaluators like GEvaluator can actually evaluate the edge which de facto means it evaluates the successor state reached over this edge. These evaluations will not be stored (since it only stores information for states).

Instead of retrieving g values from the evaluation context, GEvaluator should 
become a path-dependent Evaluator (as it already is in theory) and store g values 
in a per-state-information.