1	/*=============================================================================
2	Copyright (c) 2001-2011 Joel de Guzman
3	Copyright (c) 2001-2011 Hartmut Kaiser
4	Copyright (c) 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_DETAIL2)
10	#define BOOST_SPIRIT_UTREE_DETAIL2
11
12	#include <boost/type_traits/remove_pointer.hpp>
13	#include <boost/type_traits/is_pointer.hpp>
14	#include <boost/utility/enable_if.hpp>
15	#include <boost/throw_exception.hpp>
16	#include <boost/iterator/iterator_traits.hpp>
17	#include <cstring> // for std::memcpy
18
19	#ifdef _MSC_VER
20	# pragma warning(push)
21	# pragma warning(disable: 4800) // forcing value to bool 'true' or 'false'
22	# if _MSC_VER < 1800
23	# pragma warning(disable: 4702) // unreachable code
24	# endif
25	#endif
26
27	namespace boost { namespace spirit { namespace detail
28	{
29	inline char& fast_string::info()
30	{
31	return buff[small_string_size];
32	}
33
34	inline char fast_string::info() const
35	{
36	return buff[small_string_size];
37	}
38
39	inline int fast_string::get_type() const
40	{
41	return info() >> 1;
42	}
43
44	inline void fast_string::set_type(int t)
45	{
46	info() = (t << 1) | (info() & 1);
47	}
48
49	inline short fast_string::tag() const
50	{
51	boost::int16_t tmp;
52	std::memcpy(dest: &tmp, src: &buff[small_string_size-2], n: sizeof(tmp));
53	return tmp;
54	}
55
56	inline void fast_string::tag(short tag)
57	{
58	boost::int16_t tmp = tag;
59	std::memcpy(dest: &buff[small_string_size-2], src: &tmp, n: sizeof(tmp));
60	}
61
62	inline bool fast_string::is_heap_allocated() const
63	{
64	return info() & 1;
65	}
66
67	inline std::size_t fast_string::size() const
68	{
69	if (is_heap_allocated())
70	return heap.size;
71	else
72	return max_string_len - buff[max_string_len];
73	}
74
75	inline char const* fast_string::str() const
76	{
77	if (is_heap_allocated())
78	return heap.str;
79	else
80	return buff;
81	}
82
83	template <typename Iterator>
84	inline void fast_string::construct(Iterator f, Iterator l)
85	{
86	std::size_t const size = static_cast<std::size_t>(l-f);
87	char* str;
88	if (size < max_string_len)
89	{
90	// if it fits, store it in-situ; small_string_size minus the length
91	// of the string is placed in buff[small_string_size - 1]
92	str = buff;
93	buff[max_string_len] = static_cast<char>(max_string_len - size);
94	info() &= ~0x1;
95	}
96	else
97	{
98	// else, store it in the heap
99	str = new char[size + 1]; // add one for the null char
100	heap.str = str;
101	heap.size = size;
102	info() |= 0x1;
103	}
104	for (std::size_t i = 0; i != size; ++i)
105	{
106	*str++ = *f++;
107	}
108	*str = '\0'; // add the null char
109	}
110
111	inline void fast_string::swap(fast_string& other)
112	{
113	std::swap(a&: *this, b&: other);
114	}
115
116	inline void fast_string::free()
117	{
118	if (is_heap_allocated())
119	{
120	delete [] heap.str;
121	}
122	}
123
124	inline void fast_string::copy(fast_string const& other)
125	{
126	construct(f: other.str(), l: other.str() + other.size());
127	}
128
129	inline void fast_string::initialize()
130	{
131	for (std::size_t i = 0; i != buff_size / (sizeof(long)/sizeof(char)); ++i)
132	lbuff[i] = 0;
133	}
134
135	struct list::node : boost::noncopyable
136	{
137	template <typename T>
138	node(T const& val, node* next, node* prev)
139	: val(val), next(next), prev(prev) {}
140
141	void unlink()
142	{
143	prev->next = next;
144	next->prev = prev;
145	}
146
147	utree val;
148	node* next;
149	node* prev;
150	};
151
152	template <typename Value>
153	class list::node_iterator
154	: public boost::iterator_facade<
155	node_iterator<Value>
156	, Value
157	, boost::bidirectional_traversal_tag>
158	{
159	public:
160
161	node_iterator()
162	: node(0), prev(0) {}
163
164	node_iterator(list::node* node, list::node* prev)
165	: node(node), prev(prev) {}
166
167	private:
168
169	friend class boost::iterator_core_access;
170	friend class boost::spirit::utree;
171	friend struct boost::spirit::detail::list;
172
173	void increment()
174	{
175	if (node != 0) // not at end
176	{
177	prev = node;
178	node = node->next;
179	}
180	}
181
182	void decrement()
183	{
184	if (prev != 0) // not at begin
185	{
186	node = prev;
187	prev = prev->prev;
188	}
189	}
190
191	bool equal(node_iterator const& other) const
192	{
193	return node == other.node;
194	}
195
196	typename node_iterator::reference dereference() const
197	{
198	return node->val;
199	}
200
201	list::node* node;
202	list::node* prev;
203	};
204
205	template <typename Value>
206	class list::node_iterator<boost::reference_wrapper<Value> >
207	: public boost::iterator_facade<
208	node_iterator<boost::reference_wrapper<Value> >
209	, boost::reference_wrapper<Value>
210	, boost::bidirectional_traversal_tag>
211	{
212	public:
213
214	node_iterator()
215	: node(0), prev(0), curr(nil_node) {}
216
217	node_iterator(list::node* node, list::node* prev)
218	: node(node), prev(prev), curr(node ? node->val : nil_node) {}
219
220	private:
221
222	friend class boost::iterator_core_access;
223	friend class boost::spirit::utree;
224	friend struct boost::spirit::detail::list;
225
226	void increment()
227	{
228	if (node != 0) // not at end
229	{
230	prev = node;
231	node = node->next;
232	curr = boost::ref(node ? node->val : nil_node);
233	}
234	}
235
236	void decrement()
237	{
238	if (prev != 0) // not at begin
239	{
240	node = prev;
241	prev = prev->prev;
242	curr = boost::ref(node ? node->val : nil_node);
243	}
244	}
245
246	bool equal(node_iterator const& other) const
247	{
248	return node == other.node;
249	}
250
251	typename node_iterator::reference dereference() const
252	{
253	return curr;
254	}
255
256	list::node* node;
257	list::node* prev;
258
259	static Value nil_node;
260	mutable boost::reference_wrapper<Value> curr;
261	};
262
263	template <typename Value>
264	Value list::node_iterator<boost::reference_wrapper<Value> >::nil_node = Value();
265
266	inline void list::free()
267	{
268	node* p = first;
269	while (p != 0)
270	{
271	node* next = p->next;
272	delete p;
273	p = next;
274	}
275	}
276
277	inline void list::copy(list const& other)
278	{
279	node* p = other.first;
280	while (p != 0)
281	{
282	push_back(val: p->val);
283	p = p->next;
284	}
285	}
286
287	inline void list::default_construct()
288	{
289	first = last = 0;
290	size = 0;
291	}
292
293	template <typename T, typename Iterator>
294	inline void list::insert(T const& val, Iterator pos)
295	{
296	if (!pos.node)
297	{
298	push_back(val);
299	return;
300	}
301
302	detail::list::node* new_node =
303	new detail::list::node(val, pos.node, pos.node->prev);
304
305	if (pos.node->prev)
306	pos.node->prev->next = new_node;
307	else
308	first = new_node;
309
310	pos.node->prev = new_node;
311	++size;
312	}
313
314	template <typename T>
315	inline void list::push_front(T const& val)
316	{
317	detail::list::node* new_node;
318	if (first == 0)
319	{
320	new_node = new detail::list::node(val, 0, 0);
321	first = last = new_node;
322	++size;
323	}
324	else
325	{
326	new_node = new detail::list::node(val, first, first->prev);
327	first->prev = new_node;
328	first = new_node;
329	++size;
330	}
331	}
332
333	template <typename T>
334	inline void list::push_back(T const& val)
335	{
336	if (last == 0)
337	push_front(val);
338	else {
339	detail::list::node* new_node =
340	new detail::list::node(val, last->next, last);
341	last->next = new_node;
342	last = new_node;
343	++size;
344	}
345	}
346
347	inline void list::pop_front()
348	{
349	BOOST_ASSERT(size != 0);
350	if (first == last) // there's only one item
351	{
352	delete first;
353	size = 0;
354	first = last = 0;
355	}
356	else
357	{
358	node* np = first;
359	first = first->next;
360	first->prev = 0;
361	delete np;
362	--size;
363	}
364	}
365
366	inline void list::pop_back()
367	{
368	BOOST_ASSERT(size != 0);
369	if (first == last) // there's only one item
370	{
371	delete first;
372	size = 0;
373	first = last = 0;
374	}
375	else
376	{
377	node* np = last;
378	last = last->prev;
379	last->next = 0;
380	delete np;
381	--size;
382	}
383	}
384
385	inline list::node* list::erase(node* pos)
386	{
387	BOOST_ASSERT(pos != 0);
388	if (pos == first)
389	{
390	pop_front();
391	return first;
392	}
393	else if (pos == last)
394	{
395	pop_back();
396	return 0;
397	}
398	else
399	{
400	node* next(pos->next);
401	pos->unlink();
402	delete pos;
403	--size;
404	return next;
405	}
406	}
407
408	///////////////////////////////////////////////////////////////////////////
409	// simple binder for binary visitation (we don't want to bring in the big guns)
410	template <typename F, typename X>
411	struct bind_impl
412	{
413	typedef typename F::result_type result_type;
414	X& x; // always by reference
415	F f;
416	bind_impl(F f, X& x) : x(x), f(f) {}
417
418	template <typename Y>
419	typename F::result_type operator()(Y& y) const
420	{
421	return f(x, y);
422	}
423
424	template <typename Y>
425	typename F::result_type operator()(Y const& y) const
426	{
427	return f(x, y);
428	}
429	};
430
431	template <typename F, typename X>
432	bind_impl<F, X const> bind(F f, X const& x)
433	{
434	return bind_impl<F, X const>(f, x);
435	}
436
437	template <typename F, typename X>
438	bind_impl<F, X> bind(F f, X& x)
439	{
440	return bind_impl<F, X>(f, x);
441	}
442
443	template <typename UTreeX, typename UTreeY = UTreeX>
444	struct visit_impl
445	{
446	template <typename F>
447	typename F::result_type
448	static apply(UTreeX& x, F f) // single dispatch
449	{
450	typedef typename
451	boost::mpl::if_<boost::is_const<UTreeX>,
452	typename UTreeX::const_iterator,
453	typename UTreeX::iterator>::type
454	iterator;
455
456	typedef boost::iterator_range<iterator> list_range;
457	typedef utree_type type;
458
459	switch (x.get_type())
460	{
461	default:
462	BOOST_THROW_EXCEPTION(
463	bad_type_exception("corrupt utree type", x.get_type()));
464	break;
465
466	case type::invalid_type:
467	return f(invalid);
468
469	case type::nil_type:
470	return f(nil);
471
472	case type::bool_type:
473	return f(x.b);
474
475	case type::int_type:
476	return f(x.i);
477
478	case type::double_type:
479	return f(x.d);
480
481	case type::list_type:
482	return f(list_range(iterator(x.l.first, 0), iterator(0, x.l.last)));
483
484	case type::range_type:
485	return f(list_range(iterator(x.r.first, 0), iterator(0, x.r.last)));
486
487	case type::string_type:
488	return f(utf8_string_range_type(x.s.str(), x.s.size()));
489
490	case type::string_range_type:
491	return f(utf8_string_range_type(x.sr.first, x.sr.last));
492
493	case type::symbol_type:
494	return f(utf8_symbol_range_type(x.s.str(), x.s.size()));
495
496	case type::binary_type:
497	return f(binary_range_type(x.s.str(), x.s.size()));
498
499	case type::reference_type:
500	return apply(*x.p, f);
501
502	case type::any_type:
503	return f(any_ptr(x.v.p, x.v.i));
504
505	case type::function_type:
506	return f(*x.pf);
507	}
508	}
509
510	template <typename F>
511	typename F::result_type
512	static apply(UTreeX& x, UTreeY& y, F f) // double dispatch
513	{
514	typedef typename
515	boost::mpl::if_<boost::is_const<UTreeX>,
516	typename UTreeX::const_iterator,
517	typename UTreeX::iterator>::type
518	iterator;
519
520	typedef boost::iterator_range<iterator> list_range;
521	typedef utree_type type;
522
523	switch (x.get_type())
524	{
525	default:
526	BOOST_THROW_EXCEPTION(
527	bad_type_exception("corrupt utree type", x.get_type()));
528	break;
529
530	case type::invalid_type:
531	return visit_impl::apply(y, detail::bind(f, invalid));
532
533	case type::nil_type:
534	return visit_impl::apply(y, detail::bind(f, nil));
535
536	case type::bool_type:
537	return visit_impl::apply(y, detail::bind(f, x.b));
538
539	case type::int_type:
540	return visit_impl::apply(y, detail::bind(f, x.i));
541
542	case type::double_type:
543	return visit_impl::apply(y, detail::bind(f, x.d));
544
545	case type::list_type:
546	return visit_impl::apply(
547	y, detail::bind<F, list_range>(f,
548	list_range(iterator(x.l.first, 0), iterator(0, x.l.last))));
549
550	case type::range_type:
551	return visit_impl::apply(
552	y, detail::bind<F, list_range>(f,
553	list_range(iterator(x.r.first, 0), iterator(0, x.r.last))));
554
555	case type::string_type:
556	return visit_impl::apply(y, detail::bind(
557	f, utf8_string_range_type(x.s.str(), x.s.size())));
558
559	case type::string_range_type:
560	return visit_impl::apply(y, detail::bind(
561	f, utf8_string_range_type(x.sr.first, x.sr.last)));
562
563	case type::symbol_type:
564	return visit_impl::apply(y, detail::bind(
565	f, utf8_symbol_range_type(x.s.str(), x.s.size())));
566
567	case type::binary_type:
568	return visit_impl::apply(y, detail::bind(
569	f, binary_range_type(x.s.str(), x.s.size())));
570
571	case type::reference_type:
572	return apply(*x.p, y, f);
573
574	case type::any_type:
575	return visit_impl::apply(
576	y, detail::bind(f, any_ptr(x.v.p, x.v.i)));
577
578	case type::function_type:
579	return visit_impl::apply(y, detail::bind(f, *x.pf));
580	}
581	}
582	};
583
584	struct index_impl
585	{
586	static utree& apply(utree& ut, std::size_t i)
587	{
588	switch (ut.get_type())
589	{
590	case utree_type::reference_type:
591	return apply(ut&: ut.deref(), i);
592	case utree_type::range_type:
593	return apply(node: ut.r.first, i);
594	case utree_type::list_type:
595	return apply(node: ut.l.first, i);
596	default:
597	BOOST_THROW_EXCEPTION(
598	bad_type_exception
599	("index operation performed on non-list utree type",
600	ut.get_type()));
601	}
602	}
603
604	static utree const& apply(utree const& ut, std::size_t i)
605	{
606	switch (ut.get_type())
607	{
608	case utree_type::reference_type:
609	return apply(ut: ut.deref(), i);
610	case utree_type::range_type:
611	return apply(node: ut.r.first, i);
612	case utree_type::list_type:
613	return apply(node: ut.l.first, i);
614	default:
615	BOOST_THROW_EXCEPTION(
616	bad_type_exception
617	("index operation performed on non-list utree type",
618	ut.get_type()));
619	}
620	}
621
622	static utree& apply(list::node* node, std::size_t i)
623	{
624	for (; i > 0; --i)
625	node = node->next;
626	return node->val;
627	}
628
629	static utree const& apply(list::node const* node, std::size_t i)
630	{
631	for (; i > 0; --i)
632	node = node->next;
633	return node->val;
634	}
635	};
636	}}}
637
638	namespace boost { namespace spirit
639	{
640	template <typename F>
641	stored_function<F>::stored_function(F f)
642	: f(f)
643	{
644	}
645
646	template <typename F>
647	stored_function<F>::~stored_function()
648	{
649	}
650
651	template <typename F>
652	utree stored_function<F>::operator()(utree const& env) const
653	{
654	return f(env);
655	}
656
657	template <typename F>
658	utree stored_function<F>::operator()(utree& env) const
659	{
660	return f(env);
661	}
662
663	template <typename F>
664	function_base*
665	stored_function<F>::clone() const
666	{
667	return new stored_function<F>(f);
668	}
669
670	template <typename F>
671	referenced_function<F>::referenced_function(F& f)
672	: f(f)
673	{
674	}
675
676	template <typename F>
677	referenced_function<F>::~referenced_function()
678	{
679	}
680
681	template <typename F>
682	utree referenced_function<F>::operator()(utree const& env) const
683	{
684	return f(env);
685	}
686
687	template <typename F>
688	utree referenced_function<F>::operator()(utree& env) const
689	{
690	return f(env);
691	}
692
693	template <typename F>
694	function_base*
695	referenced_function<F>::clone() const
696	{
697	return new referenced_function<F>(f);
698	}
699
700	inline utree::utree(utree::invalid_type)
701	{
702	s.initialize();
703	set_type(type::invalid_type);
704	}
705
706	inline utree::utree(utree::nil_type)
707	{
708	s.initialize();
709	set_type(type::nil_type);
710	}
711
712	inline utree::utree(bool b_)
713	{
714	s.initialize();
715	b = b_;
716	set_type(type::bool_type);
717	}
718
719	inline utree::utree(char c)
720	{
721	s.initialize();
722	// char constructs a single element string
723	s.construct(f: &c, l: &c+1);
724	set_type(type::string_type);
725	}
726
727	inline utree::utree(unsigned int i_)
728	{
729	s.initialize();
730	i = i_;
731	set_type(type::int_type);
732	}
733
734	inline utree::utree(int i_)
735	{
736	s.initialize();
737	i = i_;
738	set_type(type::int_type);
739	}
740
741	inline utree::utree(double d_)
742	{
743	s.initialize();
744	d = d_;
745	set_type(type::double_type);
746	}
747
748	inline utree::utree(char const* str)
749	{
750	s.initialize();
751	s.construct(f: str, l: str + strlen(s: str));
752	set_type(type::string_type);
753	}
754
755	inline utree::utree(char const* str, std::size_t len)
756	{
757	s.initialize();
758	s.construct(f: str, l: str + len);
759	set_type(type::string_type);
760	}
761
762	inline utree::utree(std::string const& str)
763	{
764	s.initialize();
765	s.construct(f: str.begin(), l: str.end());
766	set_type(type::string_type);
767	}
768
769	template <typename Base, utree_type::info type_>
770	inline utree::utree(basic_string<Base, type_> const& bin)
771	{
772	s.initialize();
773	s.construct(bin.begin(), bin.end());
774	set_type(type_);
775	}
776
777	inline utree::utree(boost::reference_wrapper<utree> ref)
778	{
779	s.initialize();
780	p = ref.get_pointer();
781	set_type(type::reference_type);
782	}
783
784	inline utree::utree(any_ptr const& p)
785	{
786	s.initialize();
787	v.p = p.p;
788	v.i = p.i;
789	set_type(type::any_type);
790	}
791
792	inline utree::utree(function_base const& pf_)
793	{
794	s.initialize();
795	pf = pf_.clone();
796	set_type(type::function_type);
797	}
798
799	inline utree::utree(function_base* pf_)
800	{
801	s.initialize();
802	pf = pf_;
803	set_type(type::function_type);
804	}
805
806	template <typename Iter>
807	inline utree::utree(boost::iterator_range<Iter> r)
808	{
809	s.initialize();
810
811	assign(r.begin(), r.end());
812	}
813
814	inline utree::utree(range r, shallow_tag)
815	{
816	s.initialize();
817	this->r.first = r.begin().node;
818	this->r.last = r.end().prev;
819	set_type(type::range_type);
820	}
821
822	inline utree::utree(const_range r, shallow_tag)
823	{
824	s.initialize();
825	this->r.first = r.begin().node;
826	this->r.last = r.end().prev;
827	set_type(type::range_type);
828	}
829
830	inline utree::utree(utf8_string_range_type const& str, shallow_tag)
831	{
832	s.initialize();
833	this->sr.first = str.begin();
834	this->sr.last = str.end();
835	set_type(type::string_range_type);
836	}
837
838	inline utree::utree(utree const& other)
839	{
840	s.initialize();
841	copy(other);
842	}
843
844	inline utree::~utree()
845	{
846	free();
847	}
848
849	inline utree& utree::operator=(utree const& other)
850	{
851	if (this != &other)
852	{
853	free();
854	copy(other);
855	}
856	return *this;
857	}
858
859	inline utree& utree::operator=(nil_type)
860	{
861	free();
862	set_type(type::nil_type);
863	return *this;
864	}
865
866	inline utree& utree::operator=(bool b_)
867	{
868	free();
869	b = b_;
870	set_type(type::bool_type);
871	return *this;
872	}
873
874	inline utree& utree::operator=(char c)
875	{
876	// char constructs a single element string
877	free();
878	s.construct(f: &c, l: &c+1);
879	set_type(type::string_type);
880	return *this;
881	}
882
883	inline utree& utree::operator=(unsigned int i_)
884	{
885	free();
886	i = i_;
887	set_type(type::int_type);
888	return *this;
889	}
890
891	inline utree& utree::operator=(int i_)
892	{
893	free();
894	i = i_;
895	set_type(type::int_type);
896	return *this;
897	}
898
899	inline utree& utree::operator=(double d_)
900	{
901	free();
902	d = d_;
903	set_type(type::double_type);
904	return *this;
905	}
906
907	inline utree& utree::operator=(char const* s_)
908	{
909	free();
910	s.construct(f: s_, l: s_ + strlen(s: s_));
911	set_type(type::string_type);
912	return *this;
913	}
914
915	inline utree& utree::operator=(std::string const& s_)
916	{
917	free();
918	s.construct(f: s_.begin(), l: s_.end());
919	set_type(type::string_type);
920	return *this;
921	}
922
923	template <typename Base, utree_type::info type_>
924	inline utree& utree::operator=(basic_string<Base, type_> const& bin)
925	{
926	free();
927	s.construct(bin.begin(), bin.end());
928	set_type(type_);
929	return *this;
930	}
931
932	inline utree& utree::operator=(boost::reference_wrapper<utree> ref)
933	{
934	free();
935	p = ref.get_pointer();
936	set_type(type::reference_type);
937	return *this;
938	}
939
940	inline utree& utree::operator=(any_ptr const& p_)
941	{
942	free();
943	v.p = p_.p;
944	v.i = p_.i;
945	set_type(type::any_type);
946	return *this;
947	}
948
949	inline utree& utree::operator=(function_base const& pf_)
950	{
951	free();
952	pf = pf_.clone();
953	set_type(type::function_type);
954	return *this;
955	}
956
957	inline utree& utree::operator=(function_base* pf_)
958	{
959	free();
960	pf = pf_;
961	set_type(type::function_type);
962	return *this;
963	}
964
965	template <typename Iter>
966	inline utree& utree::operator=(boost::iterator_range<Iter> r)
967	{
968	free();
969	assign(r.begin(), r.end());
970	return *this;
971	}
972
973	template <typename F>
974	typename boost::result_of<F(utree const&)>::type
975	inline utree::visit(utree const& x, F f)
976	{
977	return detail::visit_impl<utree const>::apply(x, f);
978	}
979
980	template <typename F>
981	typename boost::result_of<F(utree&)>::type
982	inline utree::visit(utree& x, F f)
983	{
984	return detail::visit_impl<utree>::apply(x, f);
985	}
986
987	template <typename F>
988	typename boost::result_of<F(utree const&, utree const&)>::type
989	inline utree::visit(utree const& x, utree const& y, F f)
990	{
991	return detail::visit_impl<utree const, utree const>::apply(x, y, f);
992	}
993
994	template <typename F>
995	typename boost::result_of<F(utree const&, utree&)>::type
996	inline utree::visit(utree const& x, utree& y, F f)
997	{
998	return detail::visit_impl<utree const, utree>::apply(x, y, f);
999	}
1000
1001	template <typename F>
1002	typename boost::result_of<F(utree&, utree const&)>::type
1003	inline utree::visit(utree& x, utree const& y, F f)
1004	{
1005	return detail::visit_impl<utree, utree const>::apply(x, y, f);
1006	}
1007
1008	template <typename F>
1009	typename boost::result_of<F(utree&, utree&)>::type
1010	inline utree::visit(utree& x, utree& y, F f)
1011	{
1012	return detail::visit_impl<utree, utree>::apply(x, y, f);
1013	}
1014
1015	inline utree::reference get(utree::reference ut, utree::size_type i)
1016	{ return detail::index_impl::apply(ut, i); }
1017
1018	inline utree::const_reference
1019	get(utree::const_reference ut, utree::size_type i)
1020	{ return detail::index_impl::apply(ut, i); }
1021
1022	template <typename T>
1023	inline void utree::push_front(T const& val)
1024	{
1025	if (get_type() == type::reference_type)
1026	return p->push_front(val);
1027
1028	ensure_list_type(failed_in: "push_front()");
1029	l.push_front(val);
1030	}
1031
1032	template <typename T>
1033	inline void utree::push_back(T const& val)
1034	{
1035	if (get_type() == type::reference_type)
1036	return p->push_back(val);
1037
1038	ensure_list_type(failed_in: "push_back()");
1039	l.push_back(val);
1040	}
1041
1042	template <typename T>
1043	inline utree::iterator utree::insert(iterator pos, T const& val)
1044	{
1045	if (get_type() == type::reference_type)
1046	return p->insert(pos, val);
1047
1048	ensure_list_type(failed_in: "insert()");
1049	if (!pos.node)
1050	{
1051	l.push_back(val);
1052	return utree::iterator(l.last, l.last->prev);
1053	}
1054	l.insert(val, pos);
1055	return utree::iterator(pos.node->prev, pos.node->prev->prev);
1056	}
1057
1058	template <typename T>
1059	inline void utree::insert(iterator pos, std::size_t n, T const& val)
1060	{
1061	if (get_type() == type::reference_type)
1062	return p->insert(pos, n, val);
1063
1064	ensure_list_type(failed_in: "insert()");
1065	for (std::size_t i = 0; i != n; ++i)
1066	insert(pos, val);
1067	}
1068
1069	template <typename Iterator>
1070	inline void utree::insert(iterator pos, Iterator first, Iterator last)
1071	{
1072	if (get_type() == type::reference_type)
1073	return p->insert(pos, first, last);
1074
1075	ensure_list_type(failed_in: "insert()");
1076	while (first != last)
1077	insert(pos, *first++);
1078	}
1079
1080	template <typename Iterator>
1081	inline void utree::assign(Iterator first, Iterator last)
1082	{
1083	if (get_type() == type::reference_type)
1084	return p->assign(first, last);
1085
1086	clear();
1087	set_type(type::list_type);
1088
1089	while (first != last)
1090	{
1091	push_back(*first);
1092	++first;
1093	}
1094	}
1095
1096	inline void utree::clear()
1097	{
1098	if (get_type() == type::reference_type)
1099	return p->clear();
1100
1101	// clear will always make this an invalid type
1102	free();
1103	set_type(type::invalid_type);
1104	}
1105
1106	inline void utree::pop_front()
1107	{
1108	if (get_type() == type::reference_type)
1109	return p->pop_front();
1110	if (get_type() != type::list_type)
1111	BOOST_THROW_EXCEPTION(
1112	bad_type_exception
1113	("pop_front() called on non-list utree type",
1114	get_type()));
1115
1116	l.pop_front();
1117	}
1118
1119	inline void utree::pop_back()
1120	{
1121	if (get_type() == type::reference_type)
1122	return p->pop_back();
1123	if (get_type() != type::list_type)
1124	BOOST_THROW_EXCEPTION(
1125	bad_type_exception
1126	("pop_back() called on non-list utree type",
1127	get_type()));
1128
1129	l.pop_back();
1130	}
1131
1132	inline utree::iterator utree::erase(iterator pos)
1133	{
1134	if (get_type() == type::reference_type)
1135	return p->erase(pos);
1136	if (get_type() != type::list_type)
1137	BOOST_THROW_EXCEPTION(
1138	bad_type_exception
1139	("erase() called on non-list utree type",
1140	get_type()));
1141
1142	detail::list::node* np = l.erase(pos: pos.node);
1143	return iterator(np, np?np->prev:l.last);
1144	}
1145
1146	inline utree::iterator utree::erase(iterator first, iterator last)
1147	{
1148	if (get_type() == type::reference_type)
1149	return p->erase(first, last);
1150
1151	if (get_type() != type::list_type)
1152	BOOST_THROW_EXCEPTION(
1153	bad_type_exception
1154	("erase() called on non-list utree type",
1155	get_type()));
1156	while (first != last)
1157	erase(pos: first++);
1158	return last;
1159	}
1160
1161	inline utree::iterator utree::begin()
1162	{
1163	if (get_type() == type::reference_type)
1164	return p->begin();
1165	else if (get_type() == type::range_type)
1166	return iterator(r.first, 0);
1167
1168	// otherwise...
1169	ensure_list_type(failed_in: "begin()");
1170	return iterator(l.first, 0);
1171	}
1172
1173	inline utree::iterator utree::end()
1174	{
1175	if (get_type() == type::reference_type)
1176	return p->end();
1177	else if (get_type() == type::range_type)
1178	return iterator(0, r.first);
1179
1180	// otherwise...
1181	ensure_list_type(failed_in: "end()");
1182	return iterator(0, l.last);
1183	}
1184
1185	inline utree::ref_iterator utree::ref_begin()
1186	{
1187	if (get_type() == type::reference_type)
1188	return p->ref_begin();
1189	else if (get_type() == type::range_type)
1190	return ref_iterator(r.first, 0);
1191
1192	// otherwise...
1193	ensure_list_type(failed_in: "ref_begin()");
1194	return ref_iterator(l.first, 0);
1195	}
1196
1197	inline utree::ref_iterator utree::ref_end()
1198	{
1199	if (get_type() == type::reference_type)
1200	return p->ref_end();
1201	else if (get_type() == type::range_type)
1202	return ref_iterator(0, r.first);
1203
1204	// otherwise...
1205	ensure_list_type(failed_in: "ref_end()");
1206	return ref_iterator(0, l.last);
1207	}
1208
1209	inline utree::const_iterator utree::begin() const
1210	{
1211	if (get_type() == type::reference_type)
1212	return ((utree const*)p)->begin();
1213	if (get_type() == type::range_type)
1214	return const_iterator(r.first, 0);
1215
1216	// otherwise...
1217	if (get_type() != type::list_type)
1218	BOOST_THROW_EXCEPTION(
1219	bad_type_exception
1220	("begin() called on non-list utree type",
1221	get_type()));
1222
1223	return const_iterator(l.first, 0);
1224	}
1225
1226	inline utree::const_iterator utree::end() const
1227	{
1228	if (get_type() == type::reference_type)
1229	return ((utree const*)p)->end();
1230	if (get_type() == type::range_type)
1231	return const_iterator(0, r.first);
1232
1233	// otherwise...
1234	if (get_type() != type::list_type)
1235	BOOST_THROW_EXCEPTION(
1236	bad_type_exception
1237	("end() called on non-list utree type",
1238	get_type()));
1239
1240	return const_iterator(0, l.last);
1241	}
1242
1243	inline bool utree::empty() const
1244	{
1245	type::info t = get_type();
1246	if (t == type::reference_type)
1247	return ((utree const*)p)->empty();
1248
1249	if (t == type::range_type)
1250	return r.first == 0;
1251	if (t == type::list_type)
1252	return l.size == 0;
1253
1254	return t == type::nil_type || t == type::invalid_type;
1255	}
1256
1257	inline std::size_t utree::size() const
1258	{
1259	type::info t = get_type();
1260	if (t == type::reference_type)
1261	return ((utree const*)p)->size();
1262
1263	if (t == type::range_type)
1264	{
1265	// FIXME: O(n), and we have the room to store the size of a range
1266	// in the union if we compute it when assigned/constructed.
1267	std::size_t size = 0;
1268	detail::list::node* n = r.first;
1269	while (n)
1270	{
1271	n = n->next;
1272	++size;
1273	}
1274	return size;
1275	}
1276	if (t == type::list_type)
1277	return l.size;
1278
1279	if (t == type::string_type)
1280	return s.size();
1281
1282	if (t == type::symbol_type)
1283	return s.size();
1284
1285	if (t == type::binary_type)
1286	return s.size();
1287
1288	if (t == type::string_range_type)
1289	return sr.last - sr.first;
1290
1291	if (t != type::nil_type)
1292	BOOST_THROW_EXCEPTION(
1293	bad_type_exception
1294	("size() called on non-list and non-string utree type",
1295	get_type()));
1296
1297	return 0;
1298	}
1299
1300	inline utree_type::info utree::which() const
1301	{
1302	return get_type();
1303	}
1304
1305	inline utree& utree::front()
1306	{
1307	if (get_type() == type::reference_type)
1308	return p->front();
1309	if (get_type() == type::range_type)
1310	{
1311	if (!r.first)
1312	BOOST_THROW_EXCEPTION(
1313	empty_exception("front() called on empty utree range"));
1314	return r.first->val;
1315	}
1316
1317	// otherwise...
1318	if (get_type() != type::list_type)
1319	BOOST_THROW_EXCEPTION(
1320	bad_type_exception
1321	("front() called on non-list utree type", get_type()));
1322	else if (!l.first)
1323	BOOST_THROW_EXCEPTION(
1324	empty_exception("front() called on empty utree list"));
1325
1326	return l.first->val;
1327	}
1328
1329	inline utree& utree::back()
1330	{
1331	if (get_type() == type::reference_type)
1332	return p->back();
1333	if (get_type() == type::range_type)
1334	{
1335	if (!r.last)
1336	BOOST_THROW_EXCEPTION(
1337	empty_exception("back() called on empty utree range"));
1338	return r.last->val;
1339	}
1340
1341	// otherwise...
1342	if (get_type() != type::list_type)
1343	BOOST_THROW_EXCEPTION(
1344	bad_type_exception
1345	("back() called on non-list utree type", get_type()));
1346	else if (!l.last)
1347	BOOST_THROW_EXCEPTION(
1348	empty_exception("back() called on empty utree list"));
1349
1350	return l.last->val;
1351	}
1352
1353	inline utree const& utree::front() const
1354	{
1355	if (get_type() == type::reference_type)
1356	return ((utree const*)p)->front();
1357	if (get_type() == type::range_type)
1358	{
1359	if (!r.first)
1360	BOOST_THROW_EXCEPTION(
1361	empty_exception("front() called on empty utree range"));
1362	return r.first->val;
1363	}
1364
1365	// otherwise...
1366	if (get_type() != type::list_type)
1367	BOOST_THROW_EXCEPTION(
1368	bad_type_exception
1369	("front() called on non-list utree type", get_type()));
1370	else if (!l.first)
1371	BOOST_THROW_EXCEPTION(
1372	empty_exception("front() called on empty utree list"));
1373
1374	return l.first->val;
1375	}
1376
1377	inline utree const& utree::back() const
1378	{
1379	if (get_type() == type::reference_type)
1380	return ((utree const*)p)->back();
1381	if (get_type() == type::range_type)
1382	{
1383	if (!r.last)
1384	BOOST_THROW_EXCEPTION(
1385	empty_exception("back() called on empty utree range"));
1386	return r.last->val;
1387	}
1388
1389	// otherwise...
1390	if (get_type() != type::list_type)
1391	BOOST_THROW_EXCEPTION(
1392	bad_type_exception
1393	("back() called on non-list utree type", get_type()));
1394	else if (!l.last)
1395	BOOST_THROW_EXCEPTION(
1396	empty_exception("back() called on empty utree list"));
1397
1398	return l.last->val;
1399	}
1400
1401	inline void utree::swap(utree& other)
1402	{
1403	s.swap(other&: other.s);
1404	}
1405
1406	inline utree::type::info utree::get_type() const
1407	{
1408	// the fast string holds the type info
1409	return static_cast<utree::type::info>(s.get_type());
1410	}
1411
1412	inline void utree::set_type(type::info t)
1413	{
1414	// the fast string holds the type info
1415	s.set_type(t);
1416	}
1417
1418	inline void utree::ensure_list_type(char const* failed_in)
1419	{
1420	type::info t = get_type();
1421	if (t == type::invalid_type)
1422	{
1423	set_type(type::list_type);
1424	l.default_construct();
1425	}
1426	else if (get_type() != type::list_type)
1427	{
1428	std::string msg = failed_in;
1429	msg += "called on non-list and non-invalid utree type";
1430	BOOST_THROW_EXCEPTION(bad_type_exception(msg.c_str(), get_type()));
1431	}
1432	}
1433
1434	inline void utree::free()
1435	{
1436	switch (get_type())
1437	{
1438	case type::binary_type:
1439	case type::symbol_type:
1440	case type::string_type:
1441	s.free();
1442	break;
1443	case type::list_type:
1444	l.free();
1445	break;
1446	case type::function_type:
1447	delete pf;
1448	break;
1449	default:
1450	break;
1451	};
1452	s.initialize();
1453	}
1454
1455	inline void utree::copy(utree const& other)
1456	{
1457	set_type(other.get_type());
1458	switch (other.get_type())
1459	{
1460	default:
1461	BOOST_THROW_EXCEPTION(
1462	bad_type_exception("corrupt utree type", other.get_type()));
1463	break;
1464	case type::invalid_type:
1465	case type::nil_type:
1466	s.tag(tag: other.s.tag());
1467	break;
1468	case type::bool_type:
1469	b = other.b;
1470	s.tag(tag: other.s.tag());
1471	break;
1472	case type::int_type:
1473	i = other.i;
1474	s.tag(tag: other.s.tag());
1475	break;
1476	case type::double_type:
1477	d = other.d;
1478	s.tag(tag: other.s.tag());
1479	break;
1480	case type::reference_type:
1481	p = other.p;
1482	s.tag(tag: other.s.tag());
1483	break;
1484	case type::any_type:
1485	v = other.v;
1486	s.tag(tag: other.s.tag());
1487	break;
1488	case type::range_type:
1489	r = other.r;
1490	s.tag(tag: other.s.tag());
1491	break;
1492	case type::string_range_type:
1493	sr = other.sr;
1494	s.tag(tag: other.s.tag());
1495	break;
1496	case type::function_type:
1497	pf = other.pf->clone();
1498	s.tag(tag: other.s.tag());
1499	break;
1500	case type::string_type:
1501	case type::symbol_type:
1502	case type::binary_type:
1503	s.copy(other: other.s);
1504	s.tag(tag: other.s.tag());
1505	break;
1506	case type::list_type:
1507	l.copy(other: other.l);
1508	s.tag(tag: other.s.tag());
1509	break;
1510	}
1511	}
1512
1513	template <typename T>
1514	struct is_iterator_range
1515	: boost::mpl::false_
1516	{};
1517
1518	template <typename Iterator>
1519	struct is_iterator_range<boost::iterator_range<Iterator> >
1520	: boost::mpl::true_
1521	{};
1522
1523	template <typename To>
1524	struct utree_cast
1525	{
1526	typedef To result_type;
1527
1528	template <typename From>
1529	To dispatch(From const& val, boost::mpl::true_) const
1530	{
1531	return To(val); // From is convertible to To
1532	}
1533
1534	template <typename From>
1535	BOOST_NORETURN To dispatch(From const&, boost::mpl::false_) const
1536	{
1537	// From is NOT convertible to To !!!
1538	throw std::bad_cast();
1539	BOOST_UNREACHABLE_RETURN(To())
1540	}
1541
1542	template <typename From>
1543	To operator()(From const& val) const
1544	{
1545	// boost::iterator_range has a templated constructor, accepting
1546	// any argument and hence any type is 'convertible' to it.
1547	typedef typename boost::mpl::eval_if<
1548	is_iterator_range<To>
1549	, boost::is_same<From, To>, boost::is_convertible<From, To>
1550	>::type is_convertible;
1551	return dispatch(val, is_convertible());
1552	}
1553	};
1554
1555	template <typename T>
1556	struct utree_cast<T*>
1557	{
1558	typedef T* result_type;
1559
1560	template <typename From>
1561	BOOST_NORETURN T* operator()(From const&) const
1562	{
1563	// From is NOT convertible to T !!!
1564	throw std::bad_cast();
1565	BOOST_UNREACHABLE_RETURN(NULL)
1566	}
1567
1568	T* operator()(any_ptr const& p) const
1569	{
1570	return p.get<T*>();
1571	}
1572	};
1573
1574	template <typename T>
1575	inline T utree::get() const
1576	{
1577	return utree::visit(*this, utree_cast<T>());
1578	}
1579
1580	inline utree& utree::deref()
1581	{
1582	return (get_type() == type::reference_type) ? *p : *this;
1583	}
1584
1585	inline utree const& utree::deref() const
1586	{
1587	return (get_type() == type::reference_type) ? *p : *this;
1588	}
1589
1590	inline short utree::tag() const
1591	{
1592	return s.tag();
1593	}
1594
1595	inline void utree::tag(short tag)
1596	{
1597	s.tag(tag);
1598	}
1599
1600	inline utree utree::eval(utree const& env) const
1601	{
1602	if (get_type() == type::reference_type)
1603	return deref().eval(env);
1604
1605	if (get_type() != type::function_type)
1606	BOOST_THROW_EXCEPTION(
1607	bad_type_exception(
1608	"eval() called on non-function utree type", get_type()));
1609	return (*pf)(env);
1610	}
1611
1612	inline utree utree::eval(utree& env) const
1613	{
1614	if (get_type() == type::reference_type)
1615	return deref().eval(env);
1616
1617	if (get_type() != type::function_type)
1618	BOOST_THROW_EXCEPTION(
1619	bad_type_exception(
1620	"eval() called on non-function utree type", get_type()));
1621	return (*pf)(env);
1622	}
1623
1624	inline utree utree::operator() (utree const& env) const
1625	{
1626	return eval(env);
1627	}
1628
1629	inline utree utree::operator() (utree& env) const
1630	{
1631	return eval(env);
1632	}
1633	}}
1634
1635	#ifdef _MSC_VER
1636	# pragma warning(pop)
1637	#endif
1638	#endif
1639