Done.

Looks good to me. I only re-checked very superficially, but we checked the
search code previously with experiments, and if there is a problem with any of
the other changes, the buildbot will complain loudly. So I think this is ready
to be merged.

That's what I meant, yes. Reverted the change and did the other changes.

I think it is header-only (at least according to
https://stackoverflow.com/questions/13604090/which-boost-libraries-are-header-only),
but perhaps you meant that it isn't single-header?

Looking at the diff it has lots of other boost dependencies, so we would have to
add dozens of files. There are 15 boost headers that are directly included, and
these might have further dependencies themselves. Yes, this is probably why we
have our own version, and in this case I wouldn't move it to ext but revert to
what we had before for "any". (Sorry!) If anyone else would rather open all
necessary boost files, I'm not dead against it; we could discuss it. What I'd
rather not add is an external dependency on boost, though.

To avoid falling into this trap again, perhaps we should add a comment near the
top of our version of "any" explaining *why* we don't use boost::any (because
that has so many dependencies that it would require adding lots of files).

This is the new pull-request:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/48/issue860/diff

I just realized that boost::any is *not* header-only (it compiled on my system
because I have a boost installation around), which is probably the reason why we
originally came up with our own copy of it. Do we still want to switch to that
version of any?

Yes. It looks like the pull request doesn't receive new commits because it has
been merged, which is something I didn't notice until I looked at
https://bitbucket.org/SilvanS/fd-dev/pull-requests/.

I left some further comments directly with the relevant commits, as I cannot
comment on them as part of the pull request. I think only you see comments
posted on these commits, so if you reply, I don't think anyone will get notified.

That's strange. Does this direct link work?
https://bitbucket.org/SilvanS/fd-dev/commits/7ddde0f0fa3a965cc1c3925a297963078e168a3a

I don't see new commits in the pull request since March 20.

Ok, I replaced any.h by boost's any.hpp. Anyone who wants to have another look?

I think simple clean-up that doesn't make the reviewing more complicated can be
done at the same time, but I don't care much either way. But I think we should
do it.

Changed the include form. I think removing any.h and using boost's any.hpp
should happend in a different issue, or shouldn't it?

If we decide to keep "ext" around, I recommend we also move "any.h" to ext and
replace our version with the original version. I don't think there's a good
reason to treat "any" and "optional" differently.

We discussed this today and decided to leave the file in the "ext" directory.
The only TODO left for this issue is to use #include <...> for all files in "ext".

Done. So all that remains is to discuss how to integrate std::optional.

Agreed. (But before merging, please fix the planner configurations in the
experiments that will break when we fix the errors in the option parser:
"astar(lmcut)" and "astar(blind)".)

I agree.

Everything looks correct:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue860-v2-issue860-base-issue860-v2-compare.html

Ok. I actually wanted to go with lmcount but thought it'd need an LP solver for
admissible=true, but that is only necessary for optimal=true.

The first one is good, except that it's a parser bug that we accept this. It
should be "lmcut()", not "lmcut".

The second one isn't so good, as LM-Cut will never change between evaluations.
You can use the seq-opt-bjolp configuration. (If you don't want the hassle of
passing in driver options, just copy the configuration from driver/aliases.py.)

Would
"astar-lmcut", ["--search", "astar(lmcut)"]), # inconsistent heuristic to test
re-opening
"astar-blind-lazy-lmcut", ["--search", "astar(blind, lazy_evaluator=lmcut)"]), #
test lazy evaluator
provide the information you want?

I think it would be good to run a small experiment testing the things you mention.

Sounds good. Are we confident about the correctness of the change? The
experiment was about speed, not correctness; it didn't exercise the bulk of the
code in the diff (lazy evaluators, reopening due to inconsistent heuristics).

If you (plural) have no concerns there, I think we can merge this once we've
decided what to do with "optional".

Addressed them. Marking this as waiting for the outcome of the discussion.

I had a look and left a few comments. I think the change makes the code cleaner
and simplifies further refactorings.

I added discussing "optional" to the Fast Downward meeting agenda.

I am somewhat in favour of the idea in general, but would like to discuss
whether or not we want to include "optional" in our codebase in this fashion
among our wider group of developers, not just in the context of this issue.

There is also the more technical question whether we want to add it to the "ext"
directory (like in your pull request) or make it a "regular" part of the code,
like we did for our version of "any".

Independently of these more general questions, can someone review Silvan's pull
request? I'm mostly interested in whether this makes the code cleaner, or
facilitates making it cleaner in the future.

This works indeed. I implemented and ran an experiment:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue860-v2-issue860-base-issue860-v2-compare.html

No changes, also no more small increase in runtime as when using unique_ptr for
search nodes.

Should we hence include this header-only file that provides C++11-support for
std::optional?

We could consider adding assignment to SearchNode. However, it's possible to use
std::optional with types without copy assignment by using emplace instead of
operator=. The following works for me:

g++-6 -std=c++1z optional_test.cc  -o optional_test && ./optional_test

where optional_test.cc is:

====================================================================================

#include <experimental/optional>

class X {
    int a;
    int b;
public:
    X(int a, int b) :
        a(a), b(b) {
    }
    X &operator=(const X& other) = delete;
};

int main(int, char **) {
    std::experimental::optional<X> optional_x;
    X x(1, 2);
    // This does not work:
    // optional_x = x;
    // This does work:
    optional_x.emplace(x);
    return 0;
}

>It's under the most liberal possible licence. I haven't looked into it much more
>deeply, let alone tested it.
It compiles with our setting, so we could include it also for other use cases.

>I'm not even sure it would address our problem here, i.e., if search nodes
>support the necessary operations to use it here. But conceptually it's what I
>always wanted when trying to get rid of this particular source of ugliness in
>the search algorithms.
It doesn't help us with our problem because we would still need to be able to
assign SearchNode objects, which we can't.

How should we proceed here?

Following up on today's live discussion: I googled for "standalone std::optional
implementation for c++11" (not in quotes) and found this, which claims to be a
single-header implementation that supports all our supported compilers:

https://github.com/TartanLlama/optional

It's under the most liberal possible licence. I haven't looked into it much more
deeply, let alone tested it.

std::experimental::optional is not available in what we support, and neither is
the "compliant and widely-used C++11-based implementation by Andrei Krzemienski"
because it also uses std::optional (I don't know what stackoverflow claims that
this supports C++11, because the github page only promises partial C++11
support). So to further pursue that idea, we would need to dig deeper to get an
implementation of std::optional.

In lazy search, there is no need to fetch a next node and potentially re-assign
it. It also has a member EvaluationContext current_evaluation_context, which is
being re-used across method (I think). So no need to take any action here.

Besides possible performance gains, I'd like std::optional (or
std::experimental::optional) because it captures the intent directly (we could
get rid of the comment explaining why we use a unique_ptr here), and I think it
could be useful in other parts of the code, too.

I'm not even sure it would address our problem here, i.e., if search nodes
support the necessary operations to use it here. But conceptually it's what I
always wanted when trying to get rid of this particular source of ugliness in
the search algorithms.

If std::experimental::optional is available in the C++ versions we want to
support (I'm not sure we can use all C++14 features yet), I'd like to try it
out. Otherwise, I'm fine either way.

Is there a similar hack in lazy search, too?

Regarding the runtime changes, they are a bit of a pity, but in my opinion not a
show-stopper. The overhead will be less pronounced in anything other than blind
search.

Here are the results with blind search:
https://ai.dmi.unibas.ch/_tmp_files/sieverss/issue860-v1-issue860-base-issue860-v1-compare.html
The search becomes slightly slower, but not very badly, I think.

Should we still go with the std::optional suggestion? According to
https://codereview.stackexchange.com/questions/175882/optionalt-implementation,
in C++14, we could directly use std::experimental::optional. (If we didn't want
to, we could use the implementation from here: https://github.com/akrzemi1/Optional)

Dynamically allocating memory for every search node that is not conceptually
necessary isn't great, but if it helps simplify the code for now, we can give it
a shot. It would be nice to check the performance impact of this change in
isolation, though. The impact is probably minimal, but it's better to be sure.
Testing with A* + blind is enough.

A better solution would be to use std::optional, but we haven't arrived at C++17
yet, I think. An option would be to include an external implementation of
std::optional as a stopgap measure, like we do with our version of "any" (that
substitutes for std::any in newer standards) and our version of
"make_unique_ptr" (that substituted for std::make_unique in newer standards).

I found a way to circumvent the problem using unique_ptr for SearchNodes. That
means that we no longer need the fetch_next_node method and that we can re-use
the EvaluationContext for lazy evaluators when reporting f-value statistics.

Maybe you can find a hacked first version that we can later improve upon?

I don't remember if we came to a conclusion during the retreat regarding of how
to continue here. I think that we more or less agreed on the long-term plan
regarding when and how to pack/unpack states, but I still don't see an easy way
to address this first, small issue here.

I started working on this but realized that since SearchNode and
EvaluationContext can't be default-constructed or assigned, this cannot be done
as easily as we anticipated.

https://bitbucket.org/SilvanS/fd-dev/pull-requests/43/issue860/diff

In the last Fast Downward meeting, we discussed where and how to unpack states
(see meta issue401). A first step to simplify existing code will be to merge the
functionality of fetch_next_node() of eager_search into step(), allowing to
reuse an existing evaluation context.