utreeпредставляет собой динамически типизированную иерархическую структуру данных, которая может представлять абстрактные синтаксические деревья. Он хорошо интегрирован сДухом.QiиДухом. карма.utreeможно передать как атрибут почти любой грамматики.utree’s type system реализована с помощью дискриминационного союза и каламбура типа.

utreeимеет минимальный отпечаток памяти. Размер структуры данных составляет 16 байт на 32-битной платформе и 32 байта на 64-битной платформе4*размерпустота*. Будучи контейнером, он может представлять собой древесные структуры.

Каждый экземпляр структуры данныхutreeможет одновременно хранить один из следующих типов данных:

struct utree_type
{
    enum info
    {
        invalid_type,       // the utree has not been initialized (it's 
                            // default constructed)
        nil_type,           // nil is the sentinel (empty) utree type.
        list_type,          // A doubly linked list of utrees.
        range_type,         // A range of list::iterators. 
        reference_type,     // A reference to another utree.
        any_type,           // A pointer or reference to any C++ type. 
        function_type,      // A utree holding a stored_function<F> object,
                            // where F is an unary function object taking a 
                            // utree as it's parameter and returning a
                            // utree.
        // numeric atoms
        bool_type,          // An utree holding a boolean value
        int_type,           // An utree holding a integer (int) value
        double_type,        // An utree holding a floating point (double) value
        // text atoms (utf8)
        string_type,        // An UTF-8 string 
        string_range_type,  // A pair of iterators into an UTF-8 string
        symbol_type,        // An UTF-8 symbol name
        binary_type         // Arbitrary binary data
    };
    typedef boost::uint_t<sizeof(info)*8>::exact exact_integral_type;
    typedef boost::uint_t<sizeof(info)*8>::fast fast_integral_type;
};

Струна UTF-8, символ UTF-8 и двоичные типы данных внутренне хранятся либо непосредственно как данные узла (применяется оптимизация малой строки), либо они выделяются из кучи, сохраняя указатель на выделенные данные вутре. Максимально возможная длина данных, которые будут храниться в данных узла, зависит от платформы, для которой скомпилированоутри. Это 14 байт для 32-битной платформы и 30 байт для 64-битной платформы.

Class Reference

Структура данныхутриочень универсальна и может использоваться в качестве атрибута для всех возможныхSpirit.Qiпарсеров иДух. Кармагенераторы. По этой причине он раскрывает набор типдефов, что делает его совместимым с контейнерами STL:

typedef utree value_type;
typedef utree& reference;
typedef utree const& const_reference;
typedef std::ptrdiff_t difference_type;
typedef std::size_t size_type;
typedef detail::list::node_iterator<utree> iterator;
typedef detail::list::node_iterator<utree const> const_iterator;

Тип данныхutreeраскрывает функциональный интерфейс двунаправленного STL-контейнера. Итераторы, возвращаемые из, начинают()и т.д., соответствуют стандартным требованиям двунаправленного итератора.

// STL Container interface
// insertion 
template <class T>
void push_back(T const&);
template <class T>
void push_front(T const&);
template <class T>
iterator insert(iterator, T const&);
template <class T>
void insert(iterator, std::size_t, T const&);
template <class Iterator>
void insert(iterator, Iterator, Iterator);
// erasure
void pop_front();
void pop_back();
iterator erase(iterator);
iterator erase(iterator, iterator);
// front access
reference front();
const_reference front() const;
iterator begin();
const_iterator begin() const;
ref_iterator ref_begin();
// back access
reference back();
const_reference back() const;
iterator end();
const_iterator end() const;
ref_iterator ref_end();

Обнаруженный интерфейс контейнера позволяет использоватьутрисо всемиSpirit.Qiпарсер иДух. КармаГенераторные компоненты, которые совместимы с типом атрибута контейнера STL.

Autreeможет быть построен или инициализирован из широкого спектра типов данных, что позволяет создаватьutreeэкземпляры для каждого возможного типа узла (см. описаниеutree_type::информациявыше). По этой причине он предоставляет конструктор и оператор назначения для каждого из разрешенных типов узлов, как показано ниже. Все конструкторы неявны по назначению, что позволяет использовать экземпляр утри в качестве атрибута практически любому ци-парсеру.

// This constructs an `invalid_type` node. When used in places
// where a boost::optional is expected (i.e. as an attribute for the 
// optional component), this represents the 'empty' state.
utree(invalid_type = invalid_type());
// This initializes a `nil_type` node, which represents a valid,
// 'initialized empty' utree (different from invalid_type!).
utree(nil_type);
reference operator=(nil_type);
// This initializes a `boolean_type` node, which can hold 'true' or
// 'false' only.
explicit utree(bool);
reference operator=(bool);
// This initializes an `integer_type` node, which can hold arbitrary 
// integers. For convenience these functions are overloaded for signed
// and unsigned integer types.
utree(unsigned int);
utree(int);
reference operator=(unsigned int);
reference operator=(int);
// This initializes a `double_type` node, which can hold arbitrary 
// floating point (double) values.
utree(double);
reference operator=(double);
// This initializes a `string_type` node, which can hold a narrow 
// character sequence (usually an UTF-8 string).
utree(char);
utree(char const*);
utree(char const*, std::size_t);
utree(std::string const&);
reference operator=(char);
reference operator=(char const*);
reference operator=(std::string const&);
// This constructs a `string_range_type` node, which does not copy the 
// data but stores the iterator range to the character sequence the 
// range has been initialized from.
utree(utf8_string_range_type const&, shallow_tag);
// This initializes a `reference_type` node, which holds a reference to 
// another utree node. All operations on such a node are automatically
// forwarded to the referenced utree instance.
utree(boost::reference_wrapper<utree>);
reference operator=(boost::reference_wrapper<utree>);
// This initializes an `any_type` node, which can hold a pointer to an
// instance of any type together with the typeid of that type. When 
// accessing that pointer the typeid will be checked, causing a 
// std::bad_cast to be thrown if the typeids do not match.
utree(any_ptr const&);
reference operator=(any_ptr const&);
// This initializes a `range_type` node, which holds an utree list node
// the elements of which are copy constructed (assigned) from the 
// elements referenced by the given range of iterators.
template <class Iterator>
utree(boost::iterator_range<Iterator>);
template <class Iterator>
reference operator=(boost::iterator_range<Iterator>);
// This initializes a `function_type` node from a polymorphic function
// object pointer (takes ownership) or reference. 
utree(function_base const&);
reference operator=(function_base const&);
utree(function_base*);
reference operator=(function_base*);
// This initializes either a `string_type`, a `symbol_type`, or a 
// `binary_type` node (depending on the template parameter `type_`), 
// which will hold the corresponding narrow character sequence (usually 
// an UTF-8 string).
template <class Base, utree_type::info type_>
utree(basic_string<Base, type_> const&);
template <class Base, utree_type::info type_>
reference operator=(basic_string<Base, type_> const&);

Тип данныхutreeпредоставляет функциональный интерфейс, совместимый сBoost.Variant. Его природа заключается в том, чтобы хранить различные типы данных, по одному в каждый момент времени, что делает его функционально очень похожим наBoost.Variant.

// return the data type (`utree_type::info`) of the currently stored 
// data item
utree_type::info which() const;
// access the currently stored data in a type safe manner, this will 
// throw a `std::bad_cast()` if the currently stored data item is not 
// default convertible to `T`.
template <class T>
T get() const;

Обнаруженный вариантный интерфейс делаетутрипригодными для использования со всемиSpirit.Qiпарсер иSpirit. Компоненты генератора кармы, совместимые с типом атрибута Boost.Variant.

String Types

utreeтипы строк, описанные ниже, используются только APIutree. Они не используются для хранения информации вутре. Они предназначены для обозначения различных внутреннихутретипов узлов. Например, созданиеutreeиз двоичного типа данных создастдвоичный_typeузел utree (см. выше).

Тип двоичных данных может быть представлен либо дословно как последовательность байтов, либо как пара итераторов в некоторую другую сохраненную двоичную последовательность данных. Используйте этот тип строки для доступа/созданиядвоичного_типаутре.

typedef basic_string<
    boost::iterator_range<char const*>, utree_type::binary_type
> binary_range_type;
typedef basic_string<
    std::string, utree_type::binary_type
> binary_string_type;

Струна UTF-8 может быть представлена либо дословно как последовательность символов, либо как пара итераторов в некоторую другую сохраненную двоичную последовательность данных. Используйте этот тип строки для доступа/созданиястроки_типаутри.

typedef basic_string<
    boost::iterator_range<char const*>, utree_type::string_type
> utf8_string_range_type;
typedef basic_string<
    std::string, utree_type::string_type
> utf8_string_type;

Символ UTF-8 может быть представлен либо дословно как последовательность символов, либо как пара итераторов в некоторую другую сохраненную двоичную последовательность данных. Используйте этот тип строки для доступа/созданиясимвола_типаутре.

typedef basic_string<
    boost::iterator_range<char const*>, utree_type::symbol_type
> utf8_symbol_range_type;
typedef basic_string<
    std::string, utree_type::symbol_type
> utf8_symbol_type;

Function Object Interface

Класс шаблонов хранимых_функций может хранить унарные функциональные объекты с подписью utree (scope const&) как узел утри.

struct function_base
{
    virtual ~function_base() {}
    virtual utree operator()(utree const& env) const = 0;
    virtual utree operator()(utree& env) const = 0;
    // Calling f.clone() must return a newly allocated function_base 
    // instance that is equal to f.
    virtual function_base* clone() const = 0;
};
template <typename F>
struct stored_function : function_base
{
    F f;
    stored_function(F f = F());
    virtual ~stored_function();
    virtual utree operator()(utree const& env) const;
    virtual utree operator()(utree& env) const;
    virtual function_base* clone() const;
};
template <typename F>
struct referenced_function : function_base
{
    F& f;
    referenced_function(F& f);
    virtual ~referenced_function();
    virtual utree operator()(utree const& env) const;
    virtual utree operator()(utree& env) const;
    virtual function_base* clone() const;
};

Exceptions

Все исключения, внесенные utree, являются производными от utree_исключения.

struct utree_exception : std::exception {};

bad_type_ Exceptionвыбрасывается всякий раз, когда кто-то вызывает функцию члена, которая применяется только к определенному сохраненному типу utree_type, но это предварительное условие нарушается, поскольку экземплярutreeсодержит какой-то другой тип.

struct bad_type_exception /*: utree_exception*/;

пустое_исключениевыбрасывается всякий раз, когда предварительное условие метода списка или диапазона utree нарушается из-за того, что список или диапазон пусты.

struct empty_exception /*: utree_exception*/;

Example: Sexpr Parser

Наш первый пример показывает, как использоватьутридля написания парсера длясимволических выражений. В то время какutreeспособен представлять практически любую AST,utreeдизайн основан на простой, но мощной природе символических выражений. В этом примере представлен ряд основных и промежуточныхутриметодов развития: с использованиемSpirit.QiиSpirit. Кармаинтеграция, отслеживание местоположения исходного кода и использование поддержки UTF8.

Источник для этого примера можно найти здесь:../../пример/поддержка/utree.

namespace sexpr
{
template <typename Iterator, typename ErrorHandler = error_handler<Iterator> >
struct parser : qi::grammar<Iterator, utree(), whitespace<Iterator> >
{
    qi::rule<Iterator, utree(), whitespace<Iterator> >
        start, element, list;
    qi::rule<Iterator, utree()>
        atom;
    qi::rule<Iterator, int()>
        integer;
    qi::rule<Iterator, utf8_symbol_type()>
        symbol;
    qi::rule<Iterator, utree::nil_type()>
        nil_;
    qi::rule<Iterator, binary_string_type()>
        binary;
    utf8::parser<Iterator>
        string;
    px::function<ErrorHandler> const
        error;
    tagger<Iterator, save_line_pos>
        pos;
    parser(std::string const& source_file = "<string>"):
        parser::base_type(start), error(ErrorHandler(source_file))
    {
        using standard::char_;
        using qi::unused_type;
        using qi::lexeme;
        using qi::hex;
        using qi::oct;
        using qi::no_case;
        using qi::real_parser;
        using qi::strict_real_policies;
        using qi::uint_parser;
        using qi::bool_parser;
        using qi::on_error;
        using qi::fail;
        using qi::int_;
        using qi::lit;
        using qi::_val;
        using qi::_1;
        using qi::_2;
        using qi::_3;
        using qi::_4;
        real_parser<double, strict_real_policies<double> > strict_double;
        uint_parser<unsigned char, 16, 2, 2> hex2;
        bool_parser<bool, sexpr::bool_input_policies> boolean;
        start = element.alias();
        element = atom | list;
        list = pos(_val, '(') > *element > ')';
        atom = nil_
             | strict_double
             | integer
             | boolean
             | string
             | symbol
             | binary;
        nil_ = qi::attr_cast(lit("nil"));
        integer = lexeme[ no_case["#x"] >  hex]
                | lexeme[ no_case["#o"] >> oct]
                | lexeme[-no_case["#d"] >> int_];
        std::string exclude = std::string(" ();\"\x01-\x1f\x7f") + '\0';
        symbol = lexeme[+(~char_(exclude))];
        binary = lexeme['#' > *hex2 > '#'];
        start.name("sexpr");
        element.name("element");
        list.name("list");
        atom.name("atom");
        nil_.name("nil");
        integer.name("integer");
        symbol.name("symbol");
        binary.name("binary");
        on_error<fail>(start, error(_1, _2, _3, _4));
    }
};
} // sexpr