Boost :: Spirit :: Qi autorules - избегание повторного копирования структур данных АСТ

Question

Я использовал Ци и Карму, чтобы выполнить некоторую обработку на нескольких небольших языках. Большинство грамматик довольно малы (20-40 правил). Я мог использовать autorules почти исключительно, поэтому мои деревья синтаксического анализа состоят исключительно из вариантов, структур и std :: векторов.

Эта установка работает отлично подходит для общего случая:
1) разобрать что-то (Qi),
2) внести незначительные манипуляции к дереву синтаксического анализа (посетителя), и
3) выход что-то (карма).

Однако я обеспокоен тем, что произойдет, если я хочу внести сложные структурные изменения в дерево синтаксиса, например, перемещение больших поддеревьев. Рассмотрим следующий пример: игрушечный

Грамматика для s-выражение в стиле логических выражений, которые использует autorules ...

// Inside grammar class; rule names match struct names... 
pexpr %= pand | por | var | bconst; 
pand %= lit("(and ") >> (pexpr % lit(" ")) >> ")"; 
por %= lit("(or ") >> (pexpr % lit(" ")) >> ")"; 
pnot %= lit("(not ") >> pexpr >> ")"; 

... что приводит к синтаксический представление дерева, которое выглядит, как это ...

struct var { 
    std::string name; 
}; 
struct bconst { 
    bool val; 
}; 

struct pand; 
struct por; 
struct pnot;        

typedef boost::variant<bconst, 
         var, 
         boost::recursive_wrapper<pand>, 
         boost::recursive_wrapper<por>, 
         boost::recursive_wrapper<pnot> > pexpr; 
struct pand { 
    std::vector<pexpr> operands;      
}; 

struct por { 
    std::vector<pexpr> operands;      
}; 

struct pnot { 
    pexpr victim; 
}; 

// Many Fusion Macros here 

Пусть у меня есть дерево разбора, который выглядит примерно так:

 pand 
    /... \ 
    por  por 
/\ /\ 
var var var var 

(T он эллипсис "гораздо больше детей подобной формы для pand. средства)

Теперь предположим, что я хочу свести на нет каждый из por узлов, так что конечный результат:

 pand 
    /... \ 
    pnot  pnot 
    |  | 
    por  por 
/\ /\ 
var var var var 

Прямой подход будет для каждого por подзаголовок:
- создать pnot узел
(копии por в строительстве);
- переустановите соответствующий векторный слот в pand узел
(копия pnot узла и его por поддерева).

В качестве альтернативы, я мог бы построить отдельный вектор, а затем заменить (обменивать) векторный вектор pand, исключив второй раунд копирования.

Все это кажется громоздким по сравнению с представлением дерева на основе указателя, которое позволяет вставлять узлы pnot без копирования существующих узлов. Мой вопрос:

Есть ли способ избежать манипуляций с тяжелым деревом с использованием данных, соответствующих требованиям автовладельца? Должен ли я укусить пулю и просто использовать неавторатуры для создания АСТ на основе указателей (например, http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/)?

Answer 1

Копирование поддеревьев не должно быть таким дорогостоящим, как вы предполагаете, поскольку рекурсивный_вариант является по существу оберткой вокруг shared_ptr. Я считаю, что это не только лучшее, но и самое простое решение.