[/==============================================================================
    Copyright (C) 2001-2011 Hartmut Kaiser
    Copyright (C) 2001-2011 Joel de Guzman
    Copyright (C) 2011      Bryce Lelbach

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
==============================================================================/]

[import ../../../../boost/spirit/home/support/utree/utree.hpp]
[import ../../example/support/utree/sexpr_parser.hpp]

[section:utree The utree data structure]

`utree` is a dynamically-typed hierarchical data structure that can represent
abstract syntax trees. It's well integrated with __qi__ and __karma__. `utree`
can be passed as an attribute to almost any grammar. `utree`'s type system is
implemented through the use of a discriminated union and type punning.

`utree` has a minimal memory footprint. The data structure size is 16 bytes on a
32-bit platform, and 32 bytes on 64-bit a platform (`4*sizeof(void*)`). Being a
container of itself, it can represent tree structures.

[utree_types]

The UTF-8 string, UTF-8 symbol, and binary data types are internally stored 
either directly as the node data (small string optimization applied), or they 
are allocated from the heap, storing the pointer to the allocated data in the 
`utree`. The maximum possible length of the data to be stored in the node data 
depends on the platform the `utree` is compiled for. It is 14 bytes for a 
32-bit platform and 30 bytes for a 64-bit platform.

[heading Class Reference]

The `utree` data structure is very versatile and can be used as an attribute
for all possible __qi__ parsers and __karma__ generators. For this reason, it 
exposes a set of typedef's making it compatible with STL containers:

[utree_container_types]

The `utree` data type exposes the functional interface of a bidirectional STL 
container. The iterators returned from `begin()` et.al. conform to the Standard 
requirements of a bidirectional iterator.

[utree_container_functions]

The exposed container interface makes the `utree` usable with all __qi__
parser and __karma__ generator components, which are compatible with an 
STL container attribute type.

[utree_initialization]

The `utree` data type exposes the functional interface compatible to 
__boost_variant__ as well. Its very nature is to hold different data types, one
at each point in time, making it functionally very similar to __boost_variant__.

[utree_variant_functions]

The exposed variant-like interface makes the `utree` usable with all __qi__
parser and __karma__ generator components, which are compatible with an 
__boost_variant__ attribute type.

[heading String Types]

[utree_strings]

[heading Function Object Interface]

The stored_function template class can to store a unary function objects with
a signature of utree(scope const&) as a utree node.

[utree_function_object_interface]

[heading Exceptions]

[utree_exceptions]

[/
  [heading Scope]

  [utree_scope]
]

[heading Example: Sexpr Parser]

Our first example demonstrates how to use `utree` to write a parser for
[@http://en.wikipedia.org/wiki/S-expression symbolic expressions].
While `utree` is capable of representing just about any AST, `utree`'s design
is based on the simple yet powerful nature of symbolic expressions. This
example introduces a number of basic and intermediate `utree` development
techniques: using __qi__ and __karma__ integration, tracking source code
locations and taking advantage of UTF8 support.

The source for this example can be found here: [@../../example/support/utree].

[utree_sexpr_parser]
 
[endsect]