Похоже, что преобразование в DCNF является NP-полным. Поэтому вы можете рассчитывать на уступки.
Ваша сильно упрощенная подзадача просто устраняет двойные отрицания. Похоже, вы пытались сохранить стек ссылок на родительские выражения (stk), но:
- вы явно не указываете способ извлечения или возврата упрощенного выражения (исходное выражение будет без изменений)
вы пытаетесь указать узел sh uniop<> как ссылку на узел expr, который является несовпадением типов:
stk.push_back(std::ref(u)); // <<=== Fails with "no matching function for call"
Для меня это это просто еще один признак того факта, что
transformer(expr & e) {
stk.push_back(e);
}
не вписывается в подвыражения. Если это так, вы можете быть уверены, что окружающий expr& уже будет в стеке. То же самое относится и к обработчикам binop / unop, которые оба пытаются сделать pu sh ссылки на u, который в то время даже не существовал в области видимости, и, вероятно, предназначались для pu sh текущего узла, который работает к тому же виду несоответствия типов.
Первое: simplify
Я думаю, мне будет гораздо проще написать их в функциональном стиле: вместо "манипулирования" граф объектов, пусть преобразование возвращает преобразованный результат .
Это сразу означает, что вы можете оставить все типы узлов без изменений, если только вы не вложенное отрицание. Вот как это выглядит:
struct simplify {
typedef expr result_type;
// in general, just identity transform
template <typename E> auto operator()(E const& e) const { return e; }
// only handle these:
auto operator()(expr const& e) const { return apply_visitor(*this, e); }
expr operator()(unop<op_not> const& e) const {
if (auto nested_negation = boost::strict_get<unop<op_not>>(&e.exp_u)) {
return nested_negation->exp_u;
}
return e;
}
};
Простая тестовая программа, выполняющая его:
Live On Coliru
std::vector<expr> tests {
"a",
NOT{"a"},
AND{"a", "b"},
OR{"a","b"},
AND{NOT{"a"},NOT{"b"}},
NOT{{NOT{"a"}}},
};
const simplifier simplify{};
for (expr const& expr : tests) {
std::cout << std::setw(30) << str(expr) << " -> " << simplify(expr) << "\n";
}
Печать:
"a" -> "a"
NOT{"a"} -> NOT{"a"}
AND{"a","b"} -> AND{"a","b"}
OR{"a","b"} -> OR{"a","b"}
AND{NOT{"a"},NOT{"b"}} -> AND{NOT{"a"},NOT{"b"}}
NOT{NOT{"a"}} -> "a"
Использование стека / мутация
Аналогичное использование стека ** может показаться * таким же простым:
ЗДЕСЬ БУДУТ ДРАКОНЫ
struct stack_simplifier {
typedef void result_type;
std::deque<std::reference_wrapper<expr>> stk;
void operator()(expr& e) {
stk.push_back(e);
apply_visitor(*this, e);
stk.pop_back();
}
template <typename Other>
void operator()(Other&) {}
void operator()(unop<op_not>& e) {
if (auto nested_negation = boost::strict_get<unop<op_not>>(&e.exp_u)) {
stk.back().get() = nested_negation->exp_u;
}
}
};
Использование больше не будет const (потому что функции нечисты), как и аргумент expr (который будет видоизменяться):
for (expr expr : tests) {
std::cout << std::setw(30) << str(expr);
stack_simplifier{}(expr);
std::cout << " -> " << expr << "\n";
}
Он / работает /, кажется, работает ( Live On Coliru ), но есть и видимые недостатки:
- стек не предназначен для реальной цели, только проверяется верхний элемент (вы можете заменить его указателем на текущий узел выражения )
- объект функтора не является чистым / неконстантным
дерево выражений видоизменяется при обходе. Это просто бомба замедленного действия, чтобы вы могли вызвать Неопределенное поведение : через
void operator()(unop<op_not>& e) {
if (auto nested_negation = boost::strict_get<unop<op_not>>(&e.exp_u)) {
stk.back().get() = nested_negation->exp_u;
}
}
после назначения выражения в верхней части стека ссылка на e свисает. Так же как и nested_negation. Разыменование вне этой точки равно UB .
Теперь в этом простом сценарии (с двойным отрицанием) не кажется слишком сложным мысленно проверьте, что это действительно нормально. НЕПРАВИЛЬНО
Оказывается, что operator= для варианта вызывает variant_assign, который выглядит так:
void variant_assign(const variant& rhs)
{
// If the contained types are EXACTLY the same...
if (which_ == rhs.which_)
{
// ...then assign rhs's storage to lhs's content:
detail::variant::assign_storage visitor(rhs.storage_.address());
this->internal_apply_visitor(visitor);
}
else
{
// Otherwise, perform general (copy-based) variant assignment:
assigner visitor(*this, rhs.which());
rhs.internal_apply_visitor(visitor);
}
}
Посетитель assigner имеет Смертельная деталь (выбрана одна из перегрузок, не зависящих от биты):
template <typename RhsT, typename B1, typename B2>
void assign_impl(
const RhsT& rhs_content
, mpl::true_ // has_nothrow_copy
, B1 // is_nothrow_move_constructible
, B2 // has_fallback_type
) const BOOST_NOEXCEPT
{
// Destroy lhs's content...
lhs_.destroy_content(); // nothrow
// ...copy rhs content into lhs's storage...
new(lhs_.storage_.address())
RhsT( rhs_content ); // nothrow
// ...and indicate new content type:
lhs_.indicate_which(rhs_which_); // nothrow
}
OOPS Оказывается, левая сторона разрушается первой. Однако в
stk.back().get() = nested_negation->exp_u;
правая сторона является подобъектом левой стороны (!!!). Неинтуитивный способ избежать UB здесь - взять временную копию¹:
expr tmp = nested_negation->exp_u;
stk.back().get() = tmp;
Представьте, что вы применяли преобразование, подобное закону Де-Моргана. Что, если в подвыражении было (также) вложенное отрицание?
Мне кажется, что подход мутации просто излишне подвержен ошибкам.
Рекурсивное, неизменяемое преобразование aka Joy
Есть еще одна проблема с подходами до сих пор. Вложенные подвыражения здесь не преобразуются. Например,
NOT{NOT{AND{"a",NOT{NOT{"b"}}}}} -> AND{"a",NOT{NOT{"b"}}}
Вместо желаемого AND{"a","b"}. Это легко исправить в чисто функциональной аппроксимации:
struct simplifier {
typedef expr result_type;
template <typename T> auto operator()(T const& v) const { return call(v); }
private:
auto call(var const& e) const { return e; }
auto call(expr const& e) const {
auto s = apply_visitor(*this, e);
return s;
}
expr call(unop<op_not> const& e) const {
if (auto nested_negation = boost::strict_get<unop<op_not>>(&e.exp_u)) {
return call(nested_negation->exp_u);
}
return unop<op_not> {call(e.exp_u)};
}
template <typename Op> auto call(binop<Op> const& e) const {
return binop<Op> {call(e.exp_l), call(e.exp_r)};
}
};
Все остается неизменным, но мы обрабатываем все типы выражений для рекурсии их подвыражений. Теперь он печатает:
Live On Coliru
"a" -> "a"
NOT{"a"} -> NOT{"a"}
AND{"a","b"} -> AND{"a","b"}
OR{"a","b"} -> OR{"a","b"}
AND{NOT{"a"},NOT{"b"}} -> AND{NOT{"a"},NOT{"b"}}
NOT{NOT{"a"}} -> "a"
NOT{NOT{AND{"a",NOT{NOT{"b"}}}}} -> AND{"a","b"}
Для полноты, аналогичное преобразование для "stack_simplifier": http://coliru.stacked-crooked.com/a/cc5627aa37f0c969
¹ фактически может использоваться семантика перемещения, но я игнорирую для ясность