1 /*=============================================================================
2 Copyright (c) 2010-2011 Daniel James
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 =============================================================================*/
11 #include <boost/current_function.hpp>
12 #include <boost/lexical_cast.hpp>
14 #define UNDEFINED_ERROR() \
15 throw value_undefined_method( \
16 std::string(BOOST_CURRENT_FUNCTION) +\
17 " not defined for " + \
24 ////////////////////////////////////////////////////////////////////////////
27 struct value_undefined_method
: value_error
29 value_undefined_method(std::string
const&);
32 value_error::value_error(std::string
const& x
)
33 : std::logic_error(x
) {}
35 value_undefined_method::value_undefined_method(std::string
const& x
)
38 ////////////////////////////////////////////////////////////////////////////
43 value_node::value_node(tag_type t
)
44 : ref_count_(0), tag_(t
), next_() {
47 value_node::~value_node() {
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 quickbook::string_view
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(); }
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(); }
64 ////////////////////////////////////////////////////////////////////////////
67 // A special value for marking the end of lists.
71 struct value_list_end_impl
: public value_node
73 static value_list_end_impl instance
;
76 : value_node(value::default_tag
)
78 intrusive_ptr_add_ref(&instance
);
82 virtual char const* type_name() const { return "list end"; }
83 virtual value_node
* clone() const { UNDEFINED_ERROR(); }
85 virtual bool equals(value_node
* other
) const
86 { return this == other
; }
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(); }
94 value_list_end_impl
value_list_end_impl::instance
;
97 ////////////////////////////////////////////////////////////////////////////
100 // (nil is just a special case of empty, don't be mislead by the name
101 // the type is not important).
105 struct empty_value_impl
: public value_node
107 static value_node
* new_(value::tag_type t
);
110 explicit empty_value_impl(value::tag_type t
)
114 char const* type_name() const { return "empty"; }
116 virtual value_node
* clone() const
117 { return new empty_value_impl(tag_
); }
119 virtual bool empty() const
122 virtual bool check() const
125 virtual bool equals(value_node
* other
) const
126 { return !other
->check(); }
128 friend value
quickbook::empty_value(value::tag_type
);
131 struct value_nil_impl
: public empty_value_impl
133 static value_nil_impl instance
;
136 : empty_value_impl(value::default_tag
)
138 intrusive_ptr_add_ref(&instance
);
139 next_
= &value_list_end_impl::instance
;
143 value_nil_impl
value_nil_impl::instance
;
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.
152 if (t
== value::default_tag
)
153 return &value_nil_impl::instance
;
155 return new empty_value_impl(t
);
159 value
empty_value(value::tag_type t
)
161 return value(detail::empty_value_impl::new_(t
));
164 ////////////////////////////////////////////////////////////////////////////
169 value_counted::value_counted()
170 : value_base(&value_nil_impl::instance
)
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.
176 intrusive_ptr_add_ref(value_
);
179 value_counted::value_counted(value_counted
const& x
)
182 intrusive_ptr_add_ref(value_
);
185 value_counted::value_counted(value_base
const& x
)
188 intrusive_ptr_add_ref(value_
);
191 value_counted::value_counted(value_node
* x
)
194 intrusive_ptr_add_ref(value_
);
197 value_counted::~value_counted()
199 intrusive_ptr_release(value_
);
203 ////////////////////////////////////////////////////////////////////////////
207 : detail::value_counted()
211 value::value(value
const& x
)
212 : detail::value_counted(x
)
216 value::value(detail::value_base
const& x
)
217 : detail::value_counted(x
)
221 value::value(detail::value_node
* x
)
222 : detail::value_counted(x
)
226 value
& value::operator=(value x
)
232 ////////////////////////////////////////////////////////////////////////////
237 struct int_value_impl
: public value_node
240 explicit int_value_impl(int, value::tag_type
);
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;
253 int_value_impl::int_value_impl(int v
, value::tag_type t
)
258 value_node
* int_value_impl::clone() const
260 return new int_value_impl(value_
, tag_
);
263 int int_value_impl::get_int() const
268 std::string
int_value_impl::get_encoded() const
270 return boost::lexical_cast
<std::string
>(value_
);
273 bool int_value_impl::empty() const
278 bool int_value_impl::is_encoded() const
283 bool int_value_impl::equals(value_node
* other
) const {
285 return value_
== other
->get_int();
287 catch(value_undefined_method
&) {
293 value
int_value(int v
, value::tag_type t
)
295 return value(new detail::int_value_impl(v
, t
));
298 ////////////////////////////////////////////////////////////////////////////
303 struct encoded_value_impl
: public value_node
306 explicit encoded_value_impl(std::string
const&, value::tag_type
);
308 char const* type_name() const { return "encoded text"; }
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;
320 struct qbk_value_impl
: public value_node
323 explicit qbk_value_impl(
325 string_iterator begin
,
329 char const* type_name() const { return "quickbook"; }
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 quickbook::string_view
get_quickbook() const;
336 virtual bool empty() const;
337 virtual bool equals(value_node
*) const;
340 string_iterator begin_
;
341 string_iterator end_
;
344 struct encoded_qbk_value_impl
: public value_node
347 char const* type_name() const { return "encoded text with quickbook reference"; }
349 encoded_qbk_value_impl(file_ptr
const&,
350 string_iterator
, string_iterator
,
351 std::string
const&, value::tag_type
);
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 quickbook::string_view
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;
364 string_iterator begin_
;
365 string_iterator end_
;
366 std::string encoded_value_
;
368 friend quickbook::value
quickbook::encoded_qbk_value(
369 file_ptr
const&, string_iterator
, string_iterator
,
370 std::string
const&, quickbook::value::tag_type
);
373 // encoded_value_impl
375 encoded_value_impl::encoded_value_impl(
376 std::string
const& val
,
379 : value_node(tag
), value_(val
)
383 encoded_value_impl::~encoded_value_impl()
387 value_node
* encoded_value_impl::clone() const
389 return new encoded_value_impl(value_
, tag_
);
392 std::string
encoded_value_impl::get_encoded() const
395 bool encoded_value_impl::empty() const
396 { return value_
.empty(); }
398 bool encoded_value_impl::is_encoded() const
401 bool encoded_value_impl::equals(value_node
* other
) const {
403 return value_
== other
->get_encoded();
405 catch(value_undefined_method
&) {
412 qbk_value_impl::qbk_value_impl(
414 string_iterator begin
,
417 ) : value_node(tag
), file_(f
), begin_(begin
), end_(end
)
421 qbk_value_impl::~qbk_value_impl()
425 value_node
* qbk_value_impl::clone() const
427 return new qbk_value_impl(file_
, begin_
, end_
, tag_
);
430 file_ptr
qbk_value_impl::get_file() const
433 string_iterator
qbk_value_impl::get_position() const
436 quickbook::string_view
qbk_value_impl::get_quickbook() const
437 { return quickbook::string_view(begin_
, end_
- begin_
); }
439 bool qbk_value_impl::empty() const
440 { return begin_
== end_
; }
442 bool qbk_value_impl::equals(value_node
* other
) const {
444 return this->get_quickbook() == other
->get_quickbook();
446 catch(value_undefined_method
&) {
451 // encoded_qbk_value_impl
453 encoded_qbk_value_impl::encoded_qbk_value_impl(
455 string_iterator begin
,
457 std::string
const& encoded
,
463 , encoded_value_(encoded
)
468 encoded_qbk_value_impl::~encoded_qbk_value_impl()
472 value_node
* encoded_qbk_value_impl::clone() const
474 return new encoded_qbk_value_impl(
475 file_
, begin_
, end_
, encoded_value_
, tag_
);
478 file_ptr
encoded_qbk_value_impl::get_file() const
481 string_iterator
encoded_qbk_value_impl::get_position() const
484 quickbook::string_view
encoded_qbk_value_impl::get_quickbook() const
485 { return quickbook::string_view(begin_
, end_
- begin_
); }
487 std::string
encoded_qbk_value_impl::get_encoded() const
488 { return encoded_value_
; }
490 // Should this test the quickbook, the boostbook or both?
491 bool encoded_qbk_value_impl::empty() const
492 { return encoded_value_
.empty(); }
494 bool encoded_qbk_value_impl::is_encoded() const
497 bool encoded_qbk_value_impl::equals(value_node
* other
) const {
499 return this->get_quickbook() == other
->get_quickbook();
501 catch(value_undefined_method
&) {}
504 return this->get_encoded() == other
->get_encoded();
506 catch(value_undefined_method
&) {}
512 value
qbk_value(file_ptr
const& f
, string_iterator x
, string_iterator y
, value::tag_type t
)
514 return value(new detail::qbk_value_impl(f
, x
, y
, t
));
517 value
encoded_value(std::string
const& x
, value::tag_type t
)
519 return value(new detail::encoded_value_impl(x
, t
));
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
)
526 return value(new detail::encoded_qbk_value_impl(f
,x
,y
,z
,t
));
529 //////////////////////////////////////////////////////////////////////////
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
**);
543 value_node
** list_ref_back(value_node
** back
)
545 while(*back
!= &value_list_end_impl::instance
) {
546 intrusive_ptr_add_ref(*back
);
547 back
= &(*back
)->next_
;
553 void list_ref(value_node
* ptr
)
555 while(ptr
!= &value_list_end_impl::instance
) {
556 intrusive_ptr_add_ref(ptr
);
561 void list_unref(value_node
* ptr
)
563 while(ptr
!= &value_list_end_impl::instance
) {
564 value_node
* next
= ptr
->next_
;
565 intrusive_ptr_release(ptr
);
570 value_node
** merge_sort(value_node
** l
)
572 if(*l
== &value_list_end_impl::instance
)
575 return merge_sort(l
, 9999);
578 value_node
** merge_sort(value_node
** l
, int recurse_limit
)
580 value_node
** p
= &(*l
)->next_
;
582 count
< recurse_limit
&& *p
!= &value_list_end_impl::instance
;
585 p
= merge(l
, p
, merge_sort(p
, count
));
591 value_node
** first
, value_node
** second
, value_node
** third
)
595 if(first
== second
) return third
;
596 if((*second
)->tag_
< (*first
)->tag_
) break;
597 first
= &(*first
)->next_
;
600 rotate(first
, second
, third
);
601 first
= &(*first
)->next_
;
603 // Since the two ranges were just swapped, the order is now:
604 // first...third...second
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.
611 if(first
== third
) return second
;
612 if((*third
)->tag_
<= (*first
)->tag_
) break;
613 first
= &(*first
)->next_
;
616 rotate(first
, third
, second
);
617 first
= &(*first
)->next_
;
621 void rotate(value_node
** first
, value_node
** second
, value_node
** third
)
623 value_node
* tmp
= *first
;
627 //if(*second != &value_list_end_impl::instance) back = second;
632 //////////////////////////////////////////////////////////////////////////
637 struct value_list_impl
: public value_node
639 value_list_impl(value::tag_type
);
640 value_list_impl(value_list_builder
&, value::tag_type
);
642 value_list_impl(value_list_impl
const&);
644 char const* type_name() const { return "list"; }
646 virtual ~value_list_impl();
647 virtual value_node
* clone() const;
648 virtual bool empty() const;
649 virtual bool equals(value_node
*) const;
651 virtual bool is_list() const;
652 virtual value_node
* get_list() const;
657 value_list_impl::value_list_impl(value::tag_type tag
)
658 : value_node(tag
), head_(&value_list_end_impl::instance
)
661 value_list_impl::value_list_impl(value_list_builder
& builder
,
663 : value_node(tag
), head_(builder
.release())
667 value_list_impl::value_list_impl(value_list_impl
const& x
)
668 : value_node(x
.tag_
), head_(x
.head_
)
673 value_list_impl::~value_list_impl()
678 value_node
* value_list_impl::clone() const
680 return new value_list_impl(*this);
683 bool value_list_impl::empty() const
685 return head_
== &value_list_end_impl::instance
;
688 bool value_list_impl::is_list() const
693 value_node
* value_list_impl::get_list() const
698 bool value_list_impl::equals(value_node
* other
) const {
702 x1
= other
->get_list();
704 catch(value_undefined_method
&) {
708 for(value_node
*x2
= head_
; x1
!= x2
; x1
= x1
->next_
, x2
= x2
->next_
)
710 if (x2
== &value_list_end_impl::instance
||
711 !x1
->equals(x2
)) return false;
718 //////////////////////////////////////////////////////////////////////////
723 // value_list_builder
725 value_list_builder::value_list_builder()
726 : head_(&value_list_end_impl::instance
)
730 value_list_builder::value_list_builder(value_node
* ptr
)
732 , back_(list_ref_back(&head_
))
735 value_list_builder::~value_list_builder()
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_
;
747 value_node
* value_list_builder::release() {
748 value_node
* r
= head_
;
749 head_
= &value_list_end_impl::instance
;
754 void value_list_builder::append(value_node
* item
)
756 if(item
->next_
) item
= item
->clone();
757 intrusive_ptr_add_ref(item
);
758 item
->next_
= *back_
;
760 back_
= &item
->next_
;
763 void value_list_builder::sort()
765 back_
= merge_sort(&head_
);
766 assert(*back_
== &value_list_end_impl::instance
);
769 bool value_list_builder::empty() const
771 return head_
== &value_list_end_impl::instance
;
775 //////////////////////////////////////////////////////////////////////////
778 value_builder::value_builder()
780 , list_tag(value::default_tag
)
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
);
791 void value_builder::save() {
792 boost::scoped_ptr
<value_builder
> store(new value_builder
);
797 void value_builder::restore() {
798 boost::scoped_ptr
<value_builder
> store
;
803 value
value_builder::release() {
804 return value(new detail::value_list_impl(current
, list_tag
));
807 void value_builder::insert(value
const& item
) {
808 current
.append(item
.value_
);
811 void value_builder::extend(value
const& list
) {
812 for (value::iterator begin
= list
.begin(), end
= list
.end();
813 begin
!= end
; ++begin
)
819 void value_builder::start_list(value::tag_type tag
) {
824 void value_builder::finish_list() {
825 value list
= release();
830 void value_builder::clear_list() {
834 void value_builder::sort_list()
839 bool value_builder::empty() const
841 return current
.empty();
844 ////////////////////////////////////////////////////////////////////////////
849 value::iterator::iterator()
850 : ptr_(&value_list_end_impl::instance
) {}