ceph/src/boost/tools/quickbook/src/values.cpp

   1 /*=============================================================================
   2     Copyright (c) 2010-2011 Daniel James
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #include "values.hpp"
  10 #include "files.hpp"
  11 #include <boost/current_function.hpp>
  12 #include <boost/lexical_cast.hpp>
  13
  14 #define UNDEFINED_ERROR() \
  15     throw value_undefined_method( \
  16         std::string(BOOST_CURRENT_FUNCTION) +\
  17         " not defined for " + \
  18         this->type_name() + \
  19         " values." \
  20         );
  21
  22 namespace quickbook
  23 {
  24     ////////////////////////////////////////////////////////////////////////////
  25     // Value Error
  26
  27     struct value_undefined_method : value_error
  28     {
  29         value_undefined_method(std::string const&);
  30     };
  31
  32     value_error::value_error(std::string const& x)
  33         : std::logic_error(x) {}
  34
  35     value_undefined_method::value_undefined_method(std::string const& x)
  36         : value_error(x) {}
  37
  38     ////////////////////////////////////////////////////////////////////////////
  39     // Node
  40
  41     namespace detail
  42     {
  43         value_node::value_node(tag_type t)
  44             : ref_count_(0), tag_(t), next_() {
  45         }
  46
  47         value_node::~value_node() {
  48         }
  49
  50         file_ptr value_node::get_file() const { UNDEFINED_ERROR(); }
  51         string_iterator value_node::get_position() const { UNDEFINED_ERROR(); }
  52         int value_node::get_int() const { UNDEFINED_ERROR(); }
  53         boost::string_ref value_node::get_quickbook() const { UNDEFINED_ERROR(); }
  54         std::string value_node::get_encoded() const { UNDEFINED_ERROR(); }
  55         value_node* value_node::get_list() const { UNDEFINED_ERROR(); }
  56
  57         bool value_node::empty() const { return false; }
  58         bool value_node::check() const { return true; }
  59         bool value_node::is_list() const { return false; }
  60         bool value_node::is_encoded() const { return false; }
  61         bool value_node::equals(value_node*) const { UNDEFINED_ERROR(); }
  62     }
  63
  64     ////////////////////////////////////////////////////////////////////////////
  65     // List end value
  66     //
  67     // A special value for marking the end of lists.
  68
  69     namespace detail
  70     {
  71         struct value_list_end_impl : public value_node
  72         {
  73             static value_list_end_impl instance;
  74         private:
  75             value_list_end_impl()
  76                 : value_node(value::default_tag)
  77             {
  78                 intrusive_ptr_add_ref(&instance);
  79                 next_ = this;
  80             }
  81
  82             virtual char const* type_name() const { return "list end"; }
  83             virtual value_node* clone() const { UNDEFINED_ERROR(); }
  84
  85             virtual bool equals(value_node* other) const
  86             { return this == other; }
  87
  88             bool empty() const { UNDEFINED_ERROR(); }
  89             bool check() const { UNDEFINED_ERROR(); }
  90             bool is_list() const { UNDEFINED_ERROR(); }
  91             bool is_encoded() const { UNDEFINED_ERROR(); }
  92         };
  93
  94         value_list_end_impl value_list_end_impl::instance;
  95     }
  96
  97     ////////////////////////////////////////////////////////////////////////////
  98     // Empty/nil values
  99     //
 100     // (nil is just a special case of empty, don't be mislead by the name
 101     //  the type is not important).
 102
 103     namespace detail
 104     {
 105         struct empty_value_impl : public value_node
 106         {
 107             static value_node* new_(value::tag_type t);
 108
 109         protected:
 110             explicit empty_value_impl(value::tag_type t)
 111                 : value_node(t) {}
 112
 113         private:
 114             char const* type_name() const { return "empty"; }
 115
 116             virtual value_node* clone() const
 117                 { return new empty_value_impl(tag_); }
 118
 119             virtual bool empty() const
 120                 { return true; }
 121
 122             virtual bool check() const
 123                 { return false; }
 124
 125             virtual bool equals(value_node* other) const
 126                 { return !other->check(); }
 127
 128             friend value quickbook::empty_value(value::tag_type);
 129         };
 130
 131         struct value_nil_impl : public empty_value_impl
 132         {
 133             static value_nil_impl instance;
 134         private:
 135             value_nil_impl()
 136                 : empty_value_impl(value::default_tag)
 137             {
 138                 intrusive_ptr_add_ref(&instance);
 139                 next_ = &value_list_end_impl::instance;
 140             }
 141         };
 142
 143         value_nil_impl value_nil_impl::instance;
 144
 145         value_node* empty_value_impl::new_(value::tag_type t) {
 146             // The return value from this function is always placed in an
 147             // intrusive_ptr which will manage the memory correctly.
 148             // Note that value_nil_impl increments its reference count
 149             // in its constructor, so that it will never be deleted by the
 150             // intrusive pointer.
 151
 152             if (t == value::default_tag)
 153                 return &value_nil_impl::instance;
 154             else
 155                 return new empty_value_impl(t);
 156         }
 157     }
 158
 159     value empty_value(value::tag_type t)
 160     {
 161         return value(detail::empty_value_impl::new_(t));
 162     }
 163
 164     ////////////////////////////////////////////////////////////////////////////
 165     // value_counted
 166
 167     namespace detail
 168     {
 169         value_counted::value_counted()
 170             : value_base(&value_nil_impl::instance)
 171         {
 172             // Even though empty is not on the heap, its reference
 173             // counter needs to be incremented so that the destructor
 174             // doesn't try to delete it.
 175
 176             intrusive_ptr_add_ref(value_);
 177         }
 178
 179         value_counted::value_counted(value_counted const& x)
 180             : value_base(x)
 181         {
 182             intrusive_ptr_add_ref(value_);
 183         }
 184
 185         value_counted::value_counted(value_base const& x)
 186             : value_base(x)
 187         {
 188             intrusive_ptr_add_ref(value_);
 189         }
 190
 191         value_counted::value_counted(value_node* x)
 192             : value_base(x)
 193         {
 194             intrusive_ptr_add_ref(value_);
 195         }
 196
 197         value_counted::~value_counted()
 198         {
 199             intrusive_ptr_release(value_);
 200         }
 201     }
 202
 203     ////////////////////////////////////////////////////////////////////////////
 204     // value
 205
 206     value::value()
 207         : detail::value_counted()
 208     {
 209     }
 210
 211     value::value(value const& x)
 212         : detail::value_counted(x)
 213     {
 214     }
 215
 216     value::value(detail::value_base const& x)
 217         : detail::value_counted(x)
 218     {
 219     }
 220
 221     value::value(detail::value_node* x)
 222         : detail::value_counted(x)
 223     {
 224     }
 225
 226     value& value::operator=(value x)
 227     {
 228         swap(x);
 229         return *this;
 230     }
 231
 232     ////////////////////////////////////////////////////////////////////////////
 233     // Integers
 234
 235     namespace detail
 236     {
 237         struct int_value_impl : public value_node
 238         {
 239         public:
 240             explicit int_value_impl(int, value::tag_type);
 241         private:
 242             char const* type_name() const { return "integer"; }
 243             virtual value_node* clone() const;
 244             virtual int get_int() const;
 245             virtual std::string get_encoded() const;
 246             virtual bool empty() const;
 247             virtual bool is_encoded() const;
 248             virtual bool equals(value_node*) const;
 249
 250             int value_;
 251         };
 252
 253         int_value_impl::int_value_impl(int v, value::tag_type t)
 254             : value_node(t)
 255             , value_(v)
 256         {}
 257
 258         value_node* int_value_impl::clone() const
 259         {
 260             return new int_value_impl(value_, tag_);
 261         }
 262
 263         int int_value_impl::get_int() const
 264         {
 265             return value_;
 266         }
 267
 268         std::string int_value_impl::get_encoded() const
 269         {
 270             return boost::lexical_cast<std::string>(value_);
 271         }
 272
 273         bool int_value_impl::empty() const
 274         {
 275             return false;
 276         }
 277
 278         bool int_value_impl::is_encoded() const
 279         {
 280             return true;
 281         }
 282
 283         bool int_value_impl::equals(value_node* other) const {
 284             try {
 285                 return value_ == other->get_int();
 286             }
 287             catch(value_undefined_method&) {
 288                 return false;
 289             }
 290         }
 291     }
 292
 293     value int_value(int v, value::tag_type t)
 294     {
 295         return value(new detail::int_value_impl(v, t));
 296     }
 297
 298     ////////////////////////////////////////////////////////////////////////////
 299     // Strings
 300
 301     namespace detail
 302     {
 303         struct encoded_value_impl : public value_node
 304         {
 305         public:
 306             explicit encoded_value_impl(std::string const&, value::tag_type);
 307         private:
 308             char const* type_name() const { return "encoded text"; }
 309
 310             virtual ~encoded_value_impl();
 311             virtual value_node* clone() const;
 312             virtual std::string get_encoded() const;
 313             virtual bool empty() const;
 314             virtual bool is_encoded() const;
 315             virtual bool equals(value_node*) const;
 316
 317             std::string value_;
 318         };
 319
 320         struct qbk_value_impl : public value_node
 321         {
 322         public:
 323             explicit qbk_value_impl(
 324                     file_ptr const&,
 325                     string_iterator begin,
 326                     string_iterator end,
 327                     value::tag_type);
 328         private:
 329             char const* type_name() const { return "quickbook"; }
 330
 331             virtual ~qbk_value_impl();
 332             virtual value_node* clone() const;
 333             virtual file_ptr get_file() const;
 334             virtual string_iterator get_position() const;
 335             virtual boost::string_ref get_quickbook() const;
 336             virtual bool empty() const;
 337             virtual bool equals(value_node*) const;
 338
 339             file_ptr file_;
 340             string_iterator begin_;
 341             string_iterator end_;
 342         };
 343
 344         struct encoded_qbk_value_impl : public value_node
 345         {
 346         private:
 347             char const* type_name() const { return "encoded text with quickbook reference"; }
 348
 349             encoded_qbk_value_impl(file_ptr const&,
 350                     string_iterator, string_iterator,
 351                     std::string const&, value::tag_type);
 352
 353             virtual ~encoded_qbk_value_impl();
 354             virtual value_node* clone() const;
 355             virtual file_ptr get_file() const;
 356             virtual string_iterator get_position() const;
 357             virtual boost::string_ref get_quickbook() const;
 358             virtual std::string get_encoded() const;
 359             virtual bool empty() const;
 360             virtual bool is_encoded() const;
 361             virtual bool equals(value_node*) const;
 362
 363             file_ptr file_;
 364             string_iterator begin_;
 365             string_iterator end_;
 366             std::string encoded_value_;
 367
 368             friend quickbook::value quickbook::encoded_qbk_value(
 369                     file_ptr const&, string_iterator, string_iterator,
 370                     std::string const&, quickbook::value::tag_type);
 371         };
 372
 373         // encoded_value_impl
 374
 375         encoded_value_impl::encoded_value_impl(
 376                 std::string const& val,
 377                 value::tag_type tag
 378             )
 379             : value_node(tag), value_(val)
 380         {
 381         }
 382
 383         encoded_value_impl::~encoded_value_impl()
 384         {
 385         }
 386
 387         value_node* encoded_value_impl::clone() const
 388         {
 389             return new encoded_value_impl(value_, tag_);
 390         }
 391
 392         std::string encoded_value_impl::get_encoded() const
 393             { return value_; }
 394
 395         bool encoded_value_impl::empty() const
 396             { return value_.empty(); }
 397
 398         bool encoded_value_impl::is_encoded() const
 399             { return true; }
 400
 401         bool encoded_value_impl::equals(value_node* other) const {
 402             try {
 403                 return value_ == other->get_encoded();
 404             }
 405             catch(value_undefined_method&) {
 406                 return false;
 407             }
 408         }
 409
 410         // qbk_value_impl
 411
 412         qbk_value_impl::qbk_value_impl(
 413                 file_ptr const& f,
 414                 string_iterator begin,
 415                 string_iterator end,
 416                 value::tag_type tag
 417             ) : value_node(tag), file_(f), begin_(begin), end_(end)
 418         {
 419         }
 420
 421         qbk_value_impl::~qbk_value_impl()
 422         {
 423         }
 424
 425         value_node* qbk_value_impl::clone() const
 426         {
 427             return new qbk_value_impl(file_, begin_, end_, tag_);
 428         }
 429
 430         file_ptr qbk_value_impl::get_file() const
 431             { return file_; }
 432
 433         string_iterator qbk_value_impl::get_position() const
 434             { return begin_; }
 435
 436         boost::string_ref qbk_value_impl::get_quickbook() const
 437             { return boost::string_ref(begin_, end_ - begin_); }
 438
 439         bool qbk_value_impl::empty() const
 440             { return begin_ == end_; }
 441
 442         bool qbk_value_impl::equals(value_node* other) const {
 443             try {
 444                 return this->get_quickbook() == other->get_quickbook();
 445             }
 446             catch(value_undefined_method&) {
 447                 return false;
 448             }
 449         }
 450
 451         // encoded_qbk_value_impl
 452
 453         encoded_qbk_value_impl::encoded_qbk_value_impl(
 454                 file_ptr const& f,
 455                 string_iterator begin,
 456                 string_iterator end,
 457                 std::string const& encoded,
 458                 value::tag_type tag)
 459             : value_node(tag)
 460             , file_(f)
 461             , begin_(begin)
 462             , end_(end)
 463             , encoded_value_(encoded)
 464
 465         {
 466         }
 467
 468         encoded_qbk_value_impl::~encoded_qbk_value_impl()
 469         {
 470         }
 471
 472         value_node* encoded_qbk_value_impl::clone() const
 473         {
 474             return new encoded_qbk_value_impl(
 475                     file_, begin_, end_, encoded_value_, tag_);
 476         }
 477
 478         file_ptr encoded_qbk_value_impl::get_file() const
 479             { return file_; }
 480
 481         string_iterator encoded_qbk_value_impl::get_position() const
 482             { return begin_; }
 483
 484         boost::string_ref encoded_qbk_value_impl::get_quickbook() const
 485             { return boost::string_ref(begin_, end_ - begin_); }
 486
 487         std::string encoded_qbk_value_impl::get_encoded() const
 488             { return encoded_value_; }
 489
 490         // Should this test the quickbook, the boostbook or both?
 491         bool encoded_qbk_value_impl::empty() const
 492             { return encoded_value_.empty(); }
 493
 494         bool encoded_qbk_value_impl::is_encoded() const
 495             { return true; }
 496
 497         bool encoded_qbk_value_impl::equals(value_node* other) const {
 498             try {
 499                 return this->get_quickbook() == other->get_quickbook();
 500             }
 501             catch(value_undefined_method&) {}
 502
 503             try {
 504                 return this->get_encoded() == other->get_encoded();
 505             }
 506             catch(value_undefined_method&) {}
 507
 508             return false;
 509         }
 510     }
 511
 512     value qbk_value(file_ptr const& f, string_iterator x, string_iterator y, value::tag_type t)
 513     {
 514         return value(new detail::qbk_value_impl(f, x, y, t));
 515     }
 516
 517     value encoded_value(std::string const& x, value::tag_type t)
 518     {
 519         return value(new detail::encoded_value_impl(x, t));
 520     }
 521
 522     value encoded_qbk_value(
 523             file_ptr const& f, string_iterator x, string_iterator y,
 524             std::string const& z, value::tag_type t)
 525     {
 526         return value(new detail::encoded_qbk_value_impl(f,x,y,z,t));
 527     }
 528
 529     //////////////////////////////////////////////////////////////////////////
 530     // List methods
 531
 532     namespace detail
 533     {
 534     namespace {
 535         value_node** list_ref_back(value_node**);
 536         void list_ref(value_node*);
 537         void list_unref(value_node*);
 538         value_node** merge_sort(value_node**);
 539         value_node** merge_sort(value_node**, int);
 540         value_node** merge(value_node**, value_node**, value_node**);
 541         void rotate(value_node**, value_node**, value_node**);
 542
 543         value_node** list_ref_back(value_node** back)
 544         {
 545             while(*back != &value_list_end_impl::instance) {
 546                 intrusive_ptr_add_ref(*back);
 547                 back = &(*back)->next_;
 548             }
 549
 550             return back;
 551         }
 552
 553         void list_ref(value_node* ptr)
 554         {
 555             while(ptr != &value_list_end_impl::instance) {
 556                 intrusive_ptr_add_ref(ptr);
 557                 ptr = ptr->next_;
 558             }
 559         }
 560
 561         void list_unref(value_node* ptr)
 562         {
 563             while(ptr != &value_list_end_impl::instance) {
 564                 value_node* next = ptr->next_;
 565                 intrusive_ptr_release(ptr);
 566                 ptr = next;
 567             }
 568         }
 569
 570         value_node** merge_sort(value_node** l)
 571         {
 572             if(*l == &value_list_end_impl::instance)
 573                 return l;
 574             else
 575                 return merge_sort(l, 9999);
 576         }
 577
 578         value_node** merge_sort(value_node** l, int recurse_limit)
 579         {
 580             value_node** p = &(*l)->next_;
 581             for(int count = 0;
 582                 count < recurse_limit && *p != &value_list_end_impl::instance;
 583                 ++count)
 584             {
 585                 p = merge(l, p, merge_sort(p, count));
 586             }
 587             return p;
 588         }
 589
 590         value_node** merge(
 591                 value_node** first, value_node** second, value_node** third)
 592         {
 593             for(;;) {
 594                 for(;;) {
 595                     if(first == second) return third;
 596                     if((*second)->tag_ < (*first)->tag_) break;
 597                     first = &(*first)->next_;
 598                 }
 599
 600                 rotate(first, second, third);
 601                 first = &(*first)->next_;
 602
 603                 // Since the two ranges were just swapped, the order is now:
 604                 // first...third...second
 605                 //
 606                 // Also, that since the second section of the list was
 607                 // originally before the first, if the heads are equal
 608                 // we need to swap to maintain the order.
 609
 610                 for(;;) {
 611                     if(first == third) return second;
 612                     if((*third)->tag_ <= (*first)->tag_) break;
 613                     first = &(*first)->next_;
 614                 }
 615
 616                 rotate(first, third, second);
 617                 first = &(*first)->next_;
 618             }
 619         }
 620
 621         void rotate(value_node** first, value_node** second, value_node** third)
 622         {
 623             value_node* tmp = *first;
 624             *first = *second;
 625             *second = *third;
 626             *third = tmp;
 627             //if(*second != &value_list_end_impl::instance) back = second;
 628         }
 629     }
 630     }
 631
 632     //////////////////////////////////////////////////////////////////////////
 633     // Lists
 634
 635     namespace detail
 636     {
 637         struct value_list_impl : public value_node
 638         {
 639             value_list_impl(value::tag_type);
 640             value_list_impl(value_list_builder&, value::tag_type);
 641         private:
 642             value_list_impl(value_list_impl const&);
 643
 644             char const* type_name() const { return "list"; }
 645
 646             virtual ~value_list_impl();
 647             virtual value_node* clone() const;
 648             virtual bool empty() const;
 649             virtual bool equals(value_node*) const;
 650
 651             virtual bool is_list() const;
 652             virtual value_node* get_list() const;
 653
 654             value_node* head_;
 655         };
 656
 657         value_list_impl::value_list_impl(value::tag_type tag)
 658             : value_node(tag), head_(&value_list_end_impl::instance)
 659         {}
 660
 661         value_list_impl::value_list_impl(value_list_builder& builder,
 662                 value::tag_type tag)
 663             : value_node(tag), head_(builder.release())
 664         {
 665         }
 666
 667         value_list_impl::value_list_impl(value_list_impl const& x)
 668             : value_node(x.tag_), head_(x.head_)
 669         {
 670             list_ref(head_);
 671         }
 672
 673         value_list_impl::~value_list_impl()
 674         {
 675             list_unref(head_);
 676         }
 677
 678         value_node* value_list_impl::clone() const
 679         {
 680             return new value_list_impl(*this);
 681         }
 682
 683         bool value_list_impl::empty() const
 684         {
 685             return head_ == &value_list_end_impl::instance;
 686         }
 687
 688         bool value_list_impl::is_list() const
 689         {
 690             return true;
 691         }
 692
 693         value_node* value_list_impl::get_list() const
 694         {
 695             return head_;
 696         }
 697
 698         bool value_list_impl::equals(value_node* other) const {
 699             value_node* x1;
 700
 701             try {
 702                  x1 = other->get_list();
 703             }
 704             catch(value_undefined_method&) {
 705                 return false;
 706             }
 707
 708             for(value_node *x2 = head_; x1 != x2; x1 = x1->next_, x2 = x2->next_)
 709             {
 710                 if (x2 == &value_list_end_impl::instance ||
 711                     !x1->equals(x2)) return false;
 712             }
 713
 714             return true;
 715         }
 716     }
 717
 718     //////////////////////////////////////////////////////////////////////////
 719     // List builder
 720
 721     namespace detail
 722     {
 723         // value_list_builder
 724
 725         value_list_builder::value_list_builder()
 726             : head_(&value_list_end_impl::instance)
 727             , back_(&head_)
 728         {}
 729
 730         value_list_builder::value_list_builder(value_node* ptr)
 731             : head_(ptr)
 732             , back_(list_ref_back(&head_))
 733         {}
 734
 735         value_list_builder::~value_list_builder()
 736         {
 737             list_unref(head_);
 738         }
 739
 740         void value_list_builder::swap(value_list_builder& other) {
 741             std::swap(head_, other.head_);
 742             std::swap(back_, other.back_);
 743             if(back_ == &other.head_) back_ = &head_;
 744             if(other.back_ == &head_) other.back_ = &other.head_;
 745         }
 746
 747         value_node* value_list_builder::release() {
 748             value_node* r = head_;
 749             head_ = &value_list_end_impl::instance;
 750             back_ = &head_;
 751             return r;
 752         }
 753
 754         void value_list_builder::append(value_node* item)
 755         {
 756             if(item->next_) item = item->clone();
 757             intrusive_ptr_add_ref(item);
 758             item->next_ = *back_;
 759             *back_ = item;
 760             back_ = &item->next_;
 761         }
 762
 763         void value_list_builder::sort()
 764         {
 765             back_ = merge_sort(&head_);
 766             assert(*back_ == &value_list_end_impl::instance);
 767         }
 768
 769         bool value_list_builder::empty() const
 770         {
 771             return head_ == &value_list_end_impl::instance;
 772         }
 773     }
 774
 775     //////////////////////////////////////////////////////////////////////////
 776     // Value builder
 777
 778     value_builder::value_builder()
 779         : current()
 780         , list_tag(value::default_tag)
 781         , saved()
 782     {
 783     }
 784
 785     void value_builder::swap(value_builder& other) {
 786         current.swap(other.current);
 787         std::swap(list_tag, other.list_tag);
 788         saved.swap(other.saved);
 789     }
 790
 791     void value_builder::save() {
 792         boost::scoped_ptr<value_builder> store(new value_builder);
 793         swap(*store);
 794         saved.swap(store);
 795     }
 796
 797     void value_builder::restore() {
 798         boost::scoped_ptr<value_builder> store;
 799         store.swap(saved);
 800         swap(*store);
 801     }
 802
 803     value value_builder::release() {
 804         return value(new detail::value_list_impl(current, list_tag));
 805     }
 806
 807     void value_builder::insert(value const& item) {
 808         current.append(item.value_);
 809     }
 810
 811     void value_builder::extend(value const& list) {
 812         for (value::iterator begin = list.begin(), end = list.end();
 813             begin != end; ++begin)
 814         {
 815             insert(*begin);
 816         }
 817     }
 818
 819     void value_builder::start_list(value::tag_type tag) {
 820         save();
 821         list_tag = tag;
 822     }
 823
 824     void value_builder::finish_list() {
 825         value list = release();
 826         restore();
 827         insert(list);
 828     }
 829
 830     void value_builder::clear_list() {
 831         restore();
 832     }
 833
 834     void value_builder::sort_list()
 835     {
 836         current.sort();
 837     }
 838
 839     bool value_builder::empty() const
 840     {
 841         return current.empty();
 842     }
 843
 844     ////////////////////////////////////////////////////////////////////////////
 845     // Iterator
 846
 847     namespace detail
 848     {
 849         value::iterator::iterator()
 850             : ptr_(&value_list_end_impl::instance) {}
 851     }
 852 }