ceph/src/boost/boost/spirit/home/support/utree/utree.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2011 Joel de Guzman
   3     Copyright (c) 2001-2011 Hartmut Kaiser
   4     Copyright (c) 2010-2011 Bryce Lelbach
   5
   6     Distributed under the Boost Software License, Version 1.0. (See accompanying
   7     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8 =============================================================================*/
   9 #if !defined(BOOST_SPIRIT_UTREE)
  10 #define BOOST_SPIRIT_UTREE
  11
  12 #include <cstddef>
  13 #include <algorithm>
  14 #include <string>
  15 #include <iostream>
  16 #include <ios>
  17 #include <sstream>
  18 #include <typeinfo>
  19
  20 #include <boost/io/ios_state.hpp>
  21 #include <boost/integer.hpp>
  22 #include <boost/throw_exception.hpp>
  23 #include <boost/assert.hpp>
  24 #include <boost/noncopyable.hpp>
  25 #include <boost/iterator/iterator_facade.hpp>
  26 #include <boost/range/iterator_range.hpp>
  27 #include <boost/type_traits/remove_pointer.hpp>
  28 #include <boost/type_traits/is_polymorphic.hpp>
  29 #include <boost/utility/enable_if.hpp>
  30 #include <boost/utility/result_of.hpp>
  31 #include <boost/ref.hpp>
  32
  33 #include <boost/spirit/home/support/utree/detail/utree_detail1.hpp>
  34
  35 #if defined(BOOST_MSVC)
  36 # pragma warning(push)
  37 # pragma warning(disable: 4804)
  38 # pragma warning(disable: 4805)
  39 # pragma warning(disable: 4244)
  40 #endif
  41
  42 namespace boost { namespace spirit
  43 {
  44     //[utree_exceptions
  45     /*` All exceptions thrown by utree are derived from utree_exception. */
  46     struct utree_exception : std::exception {};
  47
  48     /*`The `bad_type_exception` is thrown whenever somebody calls a member
  49        function, which applies to certain stored utree_type's only, but this
  50        precondition is violated as the `utree` instance holds some other type.
  51     */
  52     struct bad_type_exception /*: utree_exception*/;
  53
  54     /*`The `empty_exception` is thrown whenever a precondition of a list
  55        or range utree method is violated due to the list or range being empty.
  56     */
  57     struct empty_exception /*: utree_exception*/;
  58     //]
  59
  60     //[utree_types
  61     /*`Each instance of an `utree` data structure can store exactly one of the
  62        following data types at a time:
  63     */
  64     struct utree_type
  65     {
  66         enum info
  67         {
  68             invalid_type,       // the utree has not been initialized (it's
  69                                 // default constructed)
  70             nil_type,           // nil is the sentinel (empty) utree type.
  71             list_type,          // A doubly linked list of utrees.
  72             range_type,         // A range of list::iterators.
  73             reference_type,     // A reference to another utree.
  74             any_type,           // A pointer or reference to any C++ type.
  75             function_type,      // A utree holding a stored_function<F> object,
  76                                 // where F is an unary function object taking a
  77                                 // utree as it's parameter and returning a
  78                                 // utree.
  79
  80             // numeric atoms
  81             bool_type,          // An utree holding a boolean value
  82             int_type,           // An utree holding a integer (int) value
  83             double_type,        // An utree holding a floating point (double) value
  84
  85             // text atoms (utf8)
  86             string_type,        // An UTF-8 string
  87             string_range_type,  // A pair of iterators into an UTF-8 string
  88             symbol_type,        // An UTF-8 symbol name
  89
  90             binary_type         // Arbitrary binary data
  91         };
  92         typedef boost::uint_t<sizeof(info)*8>::exact exact_integral_type;
  93         typedef boost::uint_t<sizeof(info)*8>::fast fast_integral_type;
  94     };
  95     //]
  96
  97     // streaming operator for utree types - essential for diagnostics
  98     inline std::ostream& operator<<(std::ostream& out, utree_type::info t)
  99     {
 100         boost::io::ios_all_saver saver(out);
 101         switch (t) {
 102             case utree_type::invalid_type: { out << "invalid"; break; }
 103             case utree_type::nil_type: { out << "nil"; break; }
 104             case utree_type::list_type: { out << "list"; break; }
 105             case utree_type::range_type: { out << "range"; break; }
 106             case utree_type::reference_type: { out << "reference"; break; }
 107             case utree_type::any_type: { out << "any"; break; }
 108             case utree_type::function_type: { out << "function"; break; }
 109             case utree_type::bool_type: { out << "bool"; break; }
 110             case utree_type::int_type: { out << "int"; break; }
 111             case utree_type::double_type: { out << "double"; break; }
 112             case utree_type::string_type: { out << "string"; break; }
 113             case utree_type::string_range_type: { out << "string_range"; break; }
 114             case utree_type::symbol_type: { out << "symbol"; break; }
 115             case utree_type::binary_type: { out << "binary"; break; }
 116             default: { out << "unknown"; break; }
 117         }
 118         out << std::hex << "[0x"
 119             << static_cast<utree_type::fast_integral_type>(t) << "]";
 120         return out;
 121     }
 122
 123     struct bad_type_exception : utree_exception
 124     {
 125         std::string msg;
 126
 127         bad_type_exception(char const* error, utree_type::info got)
 128           : msg()
 129         {
 130             std::ostringstream oss;
 131             oss << "utree: " << error
 132                 << " (got utree type '" << got << "')";
 133             msg = oss.str();
 134         }
 135
 136         bad_type_exception(char const* error, utree_type::info got1,
 137                            utree_type::info got2)
 138           : msg()
 139         {
 140             std::ostringstream oss;
 141             oss << "utree: " << error
 142                 << " (got utree types '" << got1 << "' and '" << got2 << "')";
 143             msg = oss.str();
 144         }
 145
 146         virtual ~bad_type_exception() throw() {}
 147
 148         virtual char const* what() const throw()
 149         { return msg.c_str(); }
 150     };
 151
 152     struct empty_exception : utree_exception
 153     {
 154         char const* msg;
 155
 156         empty_exception(char const* error) : msg(error) {}
 157
 158         virtual ~empty_exception() throw() {}
 159
 160         virtual char const* what() const throw()
 161         { return msg; }
 162     };
 163
 164     ///////////////////////////////////////////////////////////////////////////
 165     // A typed string with parametric Base storage. The storage can be any
 166     // range or (stl container) of chars.
 167     ///////////////////////////////////////////////////////////////////////////
 168     template <typename Base, utree_type::info type_>
 169     struct basic_string : Base
 170     {
 171         static utree_type::info const type = type_;
 172
 173         basic_string()
 174           : Base() {}
 175
 176         basic_string(Base const& base)
 177           : Base(base) {}
 178
 179         template <typename Iterator>
 180         basic_string(Iterator bits, std::size_t len)
 181           : Base(bits, bits + len) {}
 182
 183         template <typename Iterator>
 184         basic_string(Iterator first, Iterator last)
 185           : Base(first, last) {}
 186
 187         basic_string& operator=(basic_string const& other)
 188         {
 189             Base::operator=(other);
 190             return *this;
 191         }
 192
 193         basic_string& operator=(Base const& other)
 194         {
 195             Base::operator=(other);
 196             return *this;
 197         }
 198     };
 199
 200     //[utree_strings
 201     /*`The `utree` string types described below are used by the `utree` API
 202        only. These are not used to store information in the `utree` itself.
 203        Their purpose is to refer to different internal `utree` node types
 204        only. For instance, creating a `utree` from a binary data type will
 205        create a `binary_type` utree node (see above).
 206     */
 207     /*`The binary data type can be represented either verbatim as a sequence
 208        of bytes or as a pair of iterators into some other stored binary data
 209        sequence. Use this string type to access/create a `binary_type` `utree`.
 210     */
 211     typedef basic_string<
 212         boost::iterator_range<char const*>, utree_type::binary_type
 213     > binary_range_type;
 214     typedef basic_string<
 215         std::string, utree_type::binary_type
 216     > binary_string_type;
 217
 218     /*`The UTF-8 string can be represented either verbatim as a sequence of
 219        characters or as a pair of iterators into some other stored binary data
 220        sequence. Use this string type to access/create a `string_type` `utree`.
 221     */
 222     typedef basic_string<
 223         boost::iterator_range<char const*>, utree_type::string_type
 224     > utf8_string_range_type;
 225     typedef basic_string<
 226         std::string, utree_type::string_type
 227     > utf8_string_type;
 228
 229     /*`The UTF-8 symbol can be represented either verbatim as a sequence of
 230        characters or as a pair of iterators into some other stored binary data
 231        sequence. Use this string type to access/create a `symbol_type` `utree`.
 232     */
 233     typedef basic_string<
 234         boost::iterator_range<char const*>, utree_type::symbol_type
 235     > utf8_symbol_range_type;
 236     typedef basic_string<
 237         std::string, utree_type::symbol_type
 238     > utf8_symbol_type;
 239     //]
 240
 241     ///////////////////////////////////////////////////////////////////////////
 242     // Our function type
 243     ///////////////////////////////////////////////////////////////////////////
 244     class utree;
 245
 246     //[utree_function_object_interface
 247     struct function_base
 248     {
 249         virtual ~function_base() {}
 250         virtual utree operator()(utree const& env) const = 0;
 251         virtual utree operator()(utree& env) const = 0;
 252
 253         // Calling f.clone() must return a newly allocated function_base
 254         // instance that is equal to f.
 255         virtual function_base* clone() const = 0;
 256     };
 257
 258     template <typename F>
 259     struct stored_function : function_base
 260     {
 261         F f;
 262         stored_function(F f = F());
 263         virtual ~stored_function();
 264         virtual utree operator()(utree const& env) const;
 265         virtual utree operator()(utree& env) const;
 266         virtual function_base* clone() const;
 267     };
 268
 269     template <typename F>
 270     struct referenced_function : function_base
 271     {
 272         F& f;
 273         referenced_function(F& f);
 274         virtual ~referenced_function();
 275         virtual utree operator()(utree const& env) const;
 276         virtual utree operator()(utree& env) const;
 277         virtual function_base* clone() const;
 278     };
 279     //]
 280
 281     ///////////////////////////////////////////////////////////////////////////
 282     // Shallow tag. Instructs utree to hold an iterator_range
 283     // as-is without deep copying the range.
 284     ///////////////////////////////////////////////////////////////////////////
 285     struct shallow_tag {};
 286     shallow_tag const shallow = {};
 287
 288     ///////////////////////////////////////////////////////////////////////////
 289     // A void* plus type_info
 290     ///////////////////////////////////////////////////////////////////////////
 291     class any_ptr
 292     {
 293     public:
 294         template <typename Ptr>
 295         typename boost::disable_if<
 296             boost::is_polymorphic<
 297                 typename boost::remove_pointer<Ptr>::type>,
 298             Ptr>::type
 299         get() const
 300         {
 301             if (*i == typeid(Ptr))
 302             {
 303                 return static_cast<Ptr>(p);
 304             }
 305             boost::throw_exception(std::bad_cast());
 306         }
 307
 308         template <typename T>
 309         any_ptr(T* p)
 310           : p(p), i(&typeid(T*))
 311         {}
 312
 313         friend bool operator==(any_ptr const& a, any_ptr const& b)
 314         {
 315             return (a.p == b.p) && (*a.i == *b.i);
 316         }
 317
 318     private:
 319         // constructor is private
 320         any_ptr(void* p, std::type_info const* i)
 321           : p(p), i(i) {}
 322
 323         template <typename UTreeX, typename UTreeY>
 324         friend struct detail::visit_impl;
 325
 326         friend class utree;
 327
 328         void* p;
 329         std::type_info const* i;
 330     };
 331
 332     //[utree
 333     class utree {
 334     public:
 335         ///////////////////////////////////////////////////////////////////////
 336         // The invalid type
 337         struct invalid_type {};
 338
 339         ///////////////////////////////////////////////////////////////////////
 340         // The nil type
 341         struct nil_type {};
 342
 343         ///////////////////////////////////////////////////////////////////////
 344         // The list type, this can be used to initialize an utree to hold an
 345         // empty list
 346         struct list_type;
 347
 348         //[utree_container_types
 349         typedef utree value_type;
 350         typedef utree& reference;
 351         typedef utree const& const_reference;
 352         typedef std::ptrdiff_t difference_type;
 353         typedef std::size_t size_type;
 354
 355         typedef detail::list::node_iterator<utree> iterator;
 356         typedef detail::list::node_iterator<utree const> const_iterator;
 357         //]
 358
 359         typedef detail::list::node_iterator<boost::reference_wrapper<utree> >
 360           ref_iterator;
 361
 362         typedef boost::iterator_range<iterator> range;
 363         typedef boost::iterator_range<const_iterator> const_range;
 364
 365         // dtor
 366         ~utree();
 367
 368         ////////////////////////////////////////////////////////////////////////
 369         //[utree_initialization
 370         /*`A `utree` can be constructed or initialized from a wide range of
 371            data types, allowing to create `utree` instances for every
 372            possible node type (see the description of `utree_type::info` above).
 373            For this reason it exposes a constructor and an assignment operator
 374            for each of the allowed node types as shown below. All constructors
 375            are non-explicit on purpose, allowing to use an utree instance as
 376            the attribute to almost any Qi parser.
 377         */
 378         // This constructs an `invalid_type` node. When used in places
 379         // where a boost::optional is expected (i.e. as an attribute for the
 380         // optional component), this represents the 'empty' state.
 381         utree(invalid_type = invalid_type());
 382
 383         // This initializes a `nil_type` node, which represents a valid,
 384         // 'initialized empty' utree (different from invalid_type!).
 385         utree(nil_type);
 386         reference operator=(nil_type);
 387
 388         // This initializes a `boolean_type` node, which can hold 'true' or
 389         // 'false' only.
 390         explicit utree(bool);
 391         reference operator=(bool);
 392
 393         // This initializes an `integer_type` node, which can hold arbitrary
 394         // integers. For convenience these functions are overloaded for signed
 395         // and unsigned integer types.
 396         utree(unsigned int);
 397         utree(int);
 398         reference operator=(unsigned int);
 399         reference operator=(int);
 400
 401         // This initializes a `double_type` node, which can hold arbitrary
 402         // floating point (double) values.
 403         utree(double);
 404         reference operator=(double);
 405
 406         // This initializes a `string_type` node, which can hold a narrow
 407         // character sequence (usually an UTF-8 string).
 408         utree(char);
 409         utree(char const*);
 410         utree(char const*, std::size_t);
 411         utree(std::string const&);
 412         reference operator=(char);
 413         reference operator=(char const*);
 414         reference operator=(std::string const&);
 415
 416         // This constructs a `string_range_type` node, which does not copy the
 417         // data but stores the iterator range to the character sequence the
 418         // range has been initialized from.
 419         utree(utf8_string_range_type const&, shallow_tag);
 420
 421         // This initializes a `reference_type` node, which holds a reference to
 422         // another utree node. All operations on such a node are automatically
 423         // forwarded to the referenced utree instance.
 424         utree(boost::reference_wrapper<utree>);
 425         reference operator=(boost::reference_wrapper<utree>);
 426
 427         // This initializes an `any_type` node, which can hold a pointer to an
 428         // instance of any type together with the typeid of that type. When
 429         // accessing that pointer the typeid will be checked, causing a
 430         // std::bad_cast to be thrown if the typeids do not match.
 431         utree(any_ptr const&);
 432         reference operator=(any_ptr const&);
 433
 434         // This initializes a `range_type` node, which holds an utree list node
 435         // the elements of which are copy constructed (assigned) from the
 436         // elements referenced by the given range of iterators.
 437         template <class Iterator>
 438         utree(boost::iterator_range<Iterator>);
 439         template <class Iterator>
 440         reference operator=(boost::iterator_range<Iterator>);
 441
 442         // This initializes a `function_type` node from a polymorphic function
 443         // object pointer (takes ownership) or reference.
 444         utree(function_base const&);
 445         reference operator=(function_base const&);
 446         utree(function_base*);
 447         reference operator=(function_base*);
 448
 449         // This initializes either a `string_type`, a `symbol_type`, or a
 450         // `binary_type` node (depending on the template parameter `type_`),
 451         // which will hold the corresponding narrow character sequence (usually
 452         // an UTF-8 string).
 453         template <class Base, utree_type::info type_>
 454         utree(basic_string<Base, type_> const&);
 455         template <class Base, utree_type::info type_>
 456         reference operator=(basic_string<Base, type_> const&);
 457         //]
 458
 459         // copy
 460         utree(const_reference);
 461         reference operator=(const_reference);
 462
 463         // range
 464         utree(range, shallow_tag);
 465         utree(const_range, shallow_tag);
 466
 467         // assign dispatch
 468         template <class Iterator>
 469         void assign(Iterator, Iterator);
 470
 471         ////////////////////////////////////////////////////////////////////////
 472
 473         ////////////////////////////////////////////////////////////////////////
 474         // function object visitation interface
 475
 476         // single dispatch
 477         template <class F>
 478         typename boost::result_of<F(utree const&)>::type
 479         static visit(utree const&, F);
 480
 481         template <class F>
 482         typename boost::result_of<F(utree&)>::type
 483         static visit(utree&, F);
 484
 485         // double dispatch
 486         template <class F>
 487         typename boost::result_of<F(utree const&, utree const&)>::type
 488         static visit(utree const&, utree const&, F);
 489
 490         template <class F>
 491         typename boost::result_of<F(utree&, utree const&)>::type
 492         static visit(utree&, utree const&, F);
 493
 494         template <class F>
 495         typename boost::result_of<F(utree const&, utree&)>::type
 496         static visit(utree const&, utree&, F);
 497
 498         template <class F>
 499         typename boost::result_of<F(utree&, utree&)>::type
 500         static visit(utree&, utree&, F);
 501
 502         ////////////////////////////////////////////////////////////////////////
 503
 504         ///////////////////////////////////////////////////////////////////////
 505         //[utree_container_functions
 506         // STL Container interface
 507
 508         // insertion
 509         template <class T>
 510         void push_back(T const&);
 511         template <class T>
 512         void push_front(T const&);
 513         template <class T>
 514         iterator insert(iterator, T const&);
 515         template <class T>
 516         void insert(iterator, std::size_t, T const&);
 517         template <class Iterator>
 518         void insert(iterator, Iterator, Iterator);
 519
 520         // erasure
 521         void pop_front();
 522         void pop_back();
 523         iterator erase(iterator);
 524         iterator erase(iterator, iterator);
 525
 526         // front access
 527         reference front();
 528         const_reference front() const;
 529         iterator begin();
 530         const_iterator begin() const;
 531         ref_iterator ref_begin();
 532
 533         // back access
 534         reference back();
 535         const_reference back() const;
 536         iterator end();
 537         const_iterator end() const;
 538         ref_iterator ref_end();
 539         //]
 540
 541         // This clears the utree instance and resets its type to `invalid_type`
 542         void clear();
 543
 544         void swap(utree&);
 545
 546         bool empty() const;
 547
 548         size_type size() const;
 549         /*`[warning `size()` has O(n) complexity on `utree` ranges. On utree
 550             lists, it has O(1) complexity.]`*/
 551
 552         ////////////////////////////////////////////////////////////////////////
 553
 554         //[utree_variant_functions
 555         // return the data type (`utree_type::info`) of the currently stored
 556         // data item
 557         utree_type::info which() const;
 558
 559         // access the currently stored data in a type safe manner, this will
 560         // throw a `std::bad_cast()` if the currently stored data item is not
 561         // default convertible to `T`.
 562         template <class T>
 563         T get() const;
 564         //]
 565
 566         reference deref();
 567         const_reference deref() const;
 568
 569         short tag() const;
 570         void tag(short);
 571
 572         utree eval(utree const&) const;
 573         utree eval(utree&) const;
 574
 575         utree operator() (utree const&) const;
 576         utree operator() (utree&) const;
 577     //<-
 578     protected:
 579         void ensure_list_type(char const* failed_in = "ensure_list_type()");
 580
 581     private:
 582         typedef utree_type type;
 583
 584         template <class UTreeX, class UTreeY>
 585         friend struct detail::visit_impl;
 586         friend struct detail::index_impl;
 587
 588         type::info get_type() const;
 589         void set_type(type::info);
 590         void free();
 591         void copy(const_reference);
 592
 593         union {
 594             detail::fast_string s;
 595             detail::list l;
 596             detail::range r;
 597             detail::string_range sr;
 598             detail::void_ptr v;
 599             bool b;
 600             int i;
 601             double d;
 602             utree* p;
 603             function_base* pf;
 604         };
 605     //->
 606     };
 607     //]
 608
 609     //[utree_tuple_interface
 610     /*<-*/inline/*->*/
 611     utree::reference get(utree::reference, utree::size_type);
 612     /*<-*/inline/*->*/
 613     utree::const_reference get(utree::const_reference, utree::size_type);
 614     /*`[warning `get()` has O(n) complexity.]`*/
 615     //]
 616
 617     struct utree::list_type : utree
 618     {
 619         using utree::operator=;
 620
 621         list_type() : utree() { ensure_list_type("list_type()"); }
 622
 623         template <typename T0>
 624         list_type(T0 t0) : utree(t0) {}
 625
 626         template <typename T0, typename T1>
 627         list_type(T0 t0, T1 t1) : utree(t0, t1) {}
 628     };
 629
 630     ///////////////////////////////////////////////////////////////////////////
 631     // predefined instances for singular types
 632     utree::invalid_type const invalid = {};
 633     utree::nil_type const nil = {};
 634     utree::list_type const empty_list = utree::list_type();
 635 }}
 636
 637 #if defined(BOOST_MSVC)
 638   #pragma warning(pop)
 639 #endif
 640
 641 #endif
 642