Subject: [Boost-commit] svn:boost r60767 - in trunk/libs/spirit/example/scheme: . detail
From: joel_at_[hidden]
Date: 2010-03-22 10:19:32
Author: djowel
Date: 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
New Revision: 60767
URL: http://svn.boost.org/trac/boost/changeset/60767
Log:
best implementation so far. done.
Text files modified:
trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp | 30 +------
trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp | 154 +++++++++++++++++++-------------------
trunk/libs/spirit/example/scheme/sexpr.hpp | 19 ----
trunk/libs/spirit/example/scheme/utree.hpp | 135 ++++++++++++++++++++++++++++-------
trunk/libs/spirit/example/scheme/utree_test.cpp | 3
5 files changed, 194 insertions(+), 147 deletions(-)
Modified: trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp (original)
+++ trunk/libs/spirit/example/scheme/detail/utree_detail1.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -21,25 +21,6 @@
struct index_impl;
///////////////////////////////////////////////////////////////////////////
- // Our utree can store these types. This enum tells us what type
- // of data is stored in utree's discriminated union.
- ///////////////////////////////////////////////////////////////////////////
- struct utree_type
- {
- enum info
- {
- nil_type,
- bool_type,
- int_type,
- double_type,
- string_type,
- binary_type,
- list_type,
- reference_type
- };
- };
-
- ///////////////////////////////////////////////////////////////////////////
// Our POD double linked list. Straightforward implementation.
// This implementation is very primitive and is not meant to be
// used stand-alone. This is the internal data representation
@@ -99,7 +80,10 @@
/ sizeof(char);
static std::size_t const
- small_string_size = buff_size-(sizeof(char)*2);
+ small_string_size = buff_size-sizeof(char);
+
+ static std::size_t const
+ max_string_len = small_string_size - 1;
struct heap_store
{
@@ -113,10 +97,8 @@
heap_store heap;
};
- utree_type::info get_type() const;
- void set_type(utree_type::info t);
- int get_subtype() const;
- void set_subtype(int t);
+ int get_type() const;
+ void set_type(int t);
bool is_heap_allocated() const;
std::size_t size() const;
Modified: trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp (original)
+++ trunk/libs/spirit/example/scheme/detail/utree_detail2.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -19,29 +19,19 @@
return buff[small_string_size];
}
- inline utree_type::info fast_string::get_type() const
+ inline int fast_string::get_type() const
{
- return static_cast<utree_type::info>((info() & 0x0F) >> 1);
+ return info() >> 1;
}
- inline void fast_string::set_type(utree_type::info t)
+ inline void fast_string::set_type(int t)
{
- info() = (static_cast<char>(t) << 1) | (info() & 0xF1);
- }
-
- inline int fast_string::get_subtype() const
- {
- return info() >> 4;
- }
-
- inline void fast_string::set_subtype(int t)
- {
- info() = (t << 4) | (info() & 0x0F);
+ info() = (t << 1) | (info() & 1);
}
inline bool fast_string::is_heap_allocated() const
{
- return info() & 0x01;
+ return info() & 1;
}
inline std::size_t fast_string::size() const
@@ -49,7 +39,7 @@
if (is_heap_allocated())
return heap.size;
else
- return small_string_size - buff[small_string_size - 1];
+ return max_string_len - buff[small_string_size - 1];
}
inline char const* fast_string::str() const
@@ -70,13 +60,11 @@
// if it fits, store it in-situ; small_string_size minus the length
// of the string is placed in buff[small_string_size - 1]
str = buff;
- buff[small_string_size - 1] = small_string_size - size;
+ buff[small_string_size - 1] = max_string_len - size;
info() &= ~0x1;
}
else
{
- BOOST_ASSERT(size < 200);
-
// else, store it in the heap
str = new char[size + 1]; // add one for the null char
heap.str = str;
@@ -355,14 +343,16 @@
template <typename T>
bool operator()(const T& a, const T& b) const
{
- // This code works for lists and strings as well
+ // This code works for lists
return a == b;
}
- template <typename Base>
- bool operator()(binary<Base> const& a, binary<Base> const& b) const
+ template <typename Base, utree_type::info type_>
+ bool operator()(
+ basic_string<Base, type_> const& a,
+ basic_string<Base, type_> const& b) const
{
- return false;
+ return static_cast<Base const&>(a) == static_cast<Base const&>(b);
}
bool operator()(nil, nil) const
@@ -399,15 +389,16 @@
template <typename T>
bool operator()(const T& a, const T& b) const
{
- // This code works for lists and strings as well
+ // This code works for lists
return a < b;
}
- template <typename Base>
- bool operator()(binary<Base> const& a, binary<Base> const& b) const
+ template <typename Base, utree_type::info type_>
+ bool operator()(
+ basic_string<Base, type_> const& a,
+ basic_string<Base, type_> const& b) const
{
- BOOST_ASSERT(false);
- return false; // no less than comparison for binary
+ return static_cast<Base const&>(a) < static_cast<Base const&>(b);
}
bool operator()(nil, nil) const
@@ -440,54 +431,48 @@
out << (b ? "true" : "false");
}
- template <typename Base>
- void operator()(binary<Base> b) const
+ void operator()(binary_range const& b) const
{
out << "b";
out.width(2);
out.fill('0');
- typedef typename Base::const_iterator iterator;
+ typedef binary_range::const_iterator iterator;
for (iterator i = b.begin(); i != b.end(); ++i)
out << std::hex << int((unsigned char)*i);
out << std::dec;
}
- template <typename Range> // for lists
- void print_string_or_list(Range range, boost::mpl::false_) const
+ void operator()(utf8_string_range const& str) const
{
- typedef typename Range::const_iterator iterator;
- (*this)('(');
- for (iterator i = range.begin(); i != range.end(); ++i)
- {
- if (i != range.begin())
- (*this)(' ');
- scheme::utree::visit(*i, *this);
- }
- (*this)(')');
+ typedef utf8_string_range::const_iterator iterator;
+ iterator i = str.begin();
+ out << '"';
+ for (; i != str.end(); ++i)
+ out << *i;
+ out << '"';
}
- template <typename Range> // for strings
- void print_string_or_list(Range range, boost::mpl::true_) const
+ void operator()(utf8_symbol_range const& str) const
{
- typedef typename Range::const_iterator iterator;
- iterator i = range.begin();
- bool const is_symbol = *i == '\0'; // a 0 byte at the beginning signifies a symbol
- if (!is_symbol)
- out << '"';
- else
- ++i;
- for (; i != range.end(); ++i)
+ typedef utf8_symbol_range::const_iterator iterator;
+ iterator i = str.begin();
+ for (; i != str.end(); ++i)
out << *i;
- if (!is_symbol)
- out << '"';
}
template <typename Iterator>
void operator()(boost::iterator_range<Iterator> const& range) const
{
- // This code works for both strings and lists
- print_string_or_list(range, boost::is_pointer<Iterator>());
+ typedef typename boost::iterator_range<Iterator>::const_iterator iterator;
+ (*this)('(');
+ for (iterator i = range.begin(); i != range.end(); ++i)
+ {
+ if (i != range.begin())
+ (*this)(' ');
+ scheme::utree::visit(*i, *this);
+ }
+ (*this)(')');
}
};
@@ -499,38 +484,44 @@
static apply(UTreeX& x, F f) // single dispatch
{
typedef typename
- boost::mpl::if_<boost::is_const<UTreeX>, char const*, char*>::type
- string_type;
-
- typedef typename
boost::mpl::if_<boost::is_const<UTreeX>,
typename UTreeX::const_iterator,
typename UTreeX::iterator>::type
iterator;
typedef boost::iterator_range<iterator> list_range;
- typedef boost::iterator_range<string_type> string_range;
- typedef detail::utree_type type;
+ typedef utree_type type;
switch (x.get_type())
{
default:
BOOST_ASSERT(false); // can't happen
+
case type::nil_type:
nil arg;
return f(arg);
+
case type::bool_type:
return f(x.b);
+
case type::int_type:
return f(x.i);
+
case type::double_type:
return f(x.d);
+
case type::list_type:
return f(list_range(iterator(x.l.first), iterator(0)));
+
case type::string_type:
- return f(string_range(x.s.str(), x.s.str() + x.s.size()));
+ return f(utf8_string_range(x.s.str(), x.s.size()));
+
+ case type::symbol_type:
+ return f(utf8_symbol_range(x.s.str(), x.s.size()));
+
case type::binary_type:
return f(binary_range(x.s.str(), x.s.size()));
+
case type::reference_type:
return apply(*x.p, f);
}
@@ -541,42 +532,49 @@
static apply(UTreeX& x, UTreeY& y, F f) // double dispatch
{
typedef typename
- boost::mpl::if_<boost::is_const<UTreeX>, char const*, char*>::type
- string_type;
-
- typedef typename
boost::mpl::if_<boost::is_const<UTreeX>,
typename UTreeX::const_iterator,
typename UTreeX::iterator>::type
iterator;
typedef boost::iterator_range<iterator> list_range;
- typedef boost::iterator_range<string_type> string_range;
- typedef detail::utree_type type;
+ typedef utree_type type;
switch (x.get_type())
{
default:
BOOST_ASSERT(false); // can't happen
+
case type::nil_type:
nil x_;
return visit_impl::apply(y, detail::bind(f, x_));
+
case type::bool_type:
return visit_impl::apply(y, detail::bind(f, x.b));
+
case type::int_type:
return visit_impl::apply(y, detail::bind(f, x.i));
+
case type::double_type:
return visit_impl::apply(y, detail::bind(f, x.d));
+
case type::list_type:
return visit_impl::apply(
y, detail::bind<F, list_range>(f,
list_range(iterator(x.l.first), iterator(0))));
+
case type::string_type:
return visit_impl::apply(y, detail::bind(
- f, string_range(x.s.str(), x.s.str() + x.s.size())));
+ f, utf8_string_range(x.s.str(), x.s.size())));
+
+ case type::symbol_type:
+ return visit_impl::apply(y, detail::bind(
+ f, utf8_symbol_range(x.s.str(), x.s.size())));
+
case type::binary_type:
return visit_impl::apply(y, detail::bind(
f, binary_range(x.s.str(), x.s.size())));
+
case type::reference_type:
return apply(*x.p, y, f);
}
@@ -646,11 +644,11 @@
set_type(type::string_type);
}
- template <typename Base>
- inline utree::utree(binary<Base> const& bin)
+ template <typename Base, utree_type::info type_>
+ inline utree::utree(basic_string<Base, type_> const& bin)
{
s.construct(bin.begin(), bin.end());
- set_type(type::binary_type);
+ set_type(type_);
}
inline utree::utree(boost::reference_wrapper<utree> ref)
@@ -727,12 +725,12 @@
return *this;
}
- template <typename Base>
- inline utree& utree::operator=(binary<Base> const& bin)
+ template <typename Base, utree_type::info type_>
+ inline utree& utree::operator=(basic_string<Base, type_> const& bin)
{
free();
s.construct(bin.begin(), bin.end());
- set_type(type::binary_type);
+ set_type(type_);
return *this;
}
@@ -1039,7 +1037,7 @@
inline utree::type::info utree::get_type() const
{
// the fast string holds the type info
- return s.get_type();
+ return static_cast<utree::type::info>(s.get_type());
}
inline void utree::set_type(type::info t)
@@ -1066,6 +1064,7 @@
switch (get_type())
{
case type::binary_type:
+ case type::symbol_type:
case type::string_type:
s.free();
break;
@@ -1097,6 +1096,7 @@
p = other.p;
break;
case type::string_type:
+ case type::symbol_type:
case type::binary_type:
s.copy(other.s);
break;
Modified: trunk/libs/spirit/example/scheme/sexpr.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/sexpr.hpp (original)
+++ trunk/libs/spirit/example/scheme/sexpr.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -75,20 +75,6 @@
}
};
- struct push_symbol
- {
- template <typename S, typename C>
- struct result { typedef void type; };
-
- void operator()(std::string& utf8, char ch) const
- {
- if (utf8.size() == 0)
- utf8 += '\0'; // mark a symbol with prefix 0
- // (a 0 byte at the beginning signifies a symbol)
- utf8 += ch;
- }
- };
-
struct push_esc
{
template <typename S, typename C>
@@ -146,7 +132,6 @@
{
real_parser<double, strict_real_policies<double> > strict_double;
uint_parser<unsigned char, 16, 2, 2> hex2;
- function<detail::push_symbol> push_symbol;
start = atom | list;
@@ -160,7 +145,7 @@
;
char const* exclude = " ();\"\0-\31\127";
- symbol = +lexeme[~char_(exclude)] [push_symbol(_val, _1)];
+ symbol = lexeme[+(~char_(exclude))];
number = strict_double [_val = _1]
| lexeme[no_case["0x"] >> hex] [_val = _1]
@@ -173,7 +158,7 @@
rule<Iterator, white_space<Iterator>, utree()> start, list;
rule<Iterator, utree()> atom, number;
- rule<Iterator, std::string()> symbol;
+ rule<Iterator, utf8_symbol()> symbol;
rule<Iterator, binary_string()> byte_str;
scheme::string<Iterator> string;
};
Modified: trunk/libs/spirit/example/scheme/utree.hpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree.hpp (original)
+++ trunk/libs/spirit/example/scheme/utree.hpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -23,10 +23,105 @@
namespace scheme
{
+ ///////////////////////////////////////////////////////////////////////////
+ // Our utree can store these types. This enum tells us what type
+ // of data is stored in utree's discriminated union.
+ ///////////////////////////////////////////////////////////////////////////
+ struct utree_type
+ {
+ enum info
+ {
+ nil_type,
+ bool_type,
+ int_type,
+ double_type,
+ string_type,
+ symbol_type,
+ binary_type,
+ list_type,
+ reference_type
+ };
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // The nil type
+ ///////////////////////////////////////////////////////////////////////////
struct nil {};
- template <typename Base>
- struct binary;
+ ///////////////////////////////////////////////////////////////////////////
+ // A typed string with parametric Base storage. The storage can be any
+ // range or (stl container) of chars.
+ ///////////////////////////////////////////////////////////////////////////
+ template <typename Base, utree_type::info type_>
+ struct basic_string : Base
+ {
+ static utree_type::info const type = type_;
+
+ basic_string()
+ : Base() {}
+
+ basic_string(Base const& base)
+ : Base(base) {}
+
+ template <typename Iterator>
+ basic_string(Iterator bits, std::size_t len)
+ : Base(bits, bits + len) {}
+
+ template <typename Iterator>
+ basic_string(Iterator first, Iterator last)
+ : Base(first, last) {}
+
+ basic_string& operator=(basic_string const& other)
+ {
+ Base::operator=(other);
+ return *this;
+ }
+
+ basic_string& operator=(Base const& other)
+ {
+ Base::operator=(other);
+ return *this;
+ }
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Binary string
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::binary_type>
+ binary_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::binary_type>
+ binary_string;
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Our UTF-8 string
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::string_type>
+ utf8_string_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::string_type>
+ utf8_string;
+
+ ///////////////////////////////////////////////////////////////////////////
+ // Our UTF-8 symbol (for identifiers)
+ ///////////////////////////////////////////////////////////////////////////
+ typedef basic_string<
+ boost::iterator_range<char const*>,
+ utree_type::symbol_type>
+ utf8_symbol_range;
+
+ typedef basic_string<
+ std::string,
+ utree_type::symbol_type>
+ utf8_symbol;
///////////////////////////////////////////////////////////////////////////
// The main utree (Universal Tree) class
@@ -36,6 +131,7 @@
// - an integer
// - a double
// - a string
+ // - a symbol (identifier)
// - binary data
// - a (doubly linked) list of utree
// - a reference to a utree
@@ -56,6 +152,9 @@
typedef std::ptrdiff_t difference_type;
typedef std::size_t size_type;
+ typedef boost::iterator_range<iterator> range;
+ typedef boost::iterator_range<const_iterator> const_range;
+
utree();
explicit utree(bool b);
explicit utree(unsigned int i);
@@ -64,11 +163,11 @@
explicit utree(char const* str);
explicit utree(char const* str, std::size_t len);
explicit utree(std::string const& str);
-
- template <typename Base>
- explicit utree(binary<Base> const& bin);
explicit utree(boost::reference_wrapper<utree> ref);
+ template <typename Base, utree_type::info type_>
+ explicit utree(basic_string<Base, type_> const& bin);
+
utree(utree const& other);
~utree();
@@ -79,11 +178,11 @@
utree& operator=(double d);
utree& operator=(char const* s);
utree& operator=(std::string const& s);
-
- template <typename Base>
- utree& operator=(binary<Base> const& bin);
utree& operator=(boost::reference_wrapper<utree> ref);
+ template <typename Base, utree_type::info type_>
+ utree& operator=(basic_string<Base, type_> const& bin);
+
template <typename F>
typename F::result_type
static visit(utree const& x, F f);
@@ -152,7 +251,7 @@
private:
- typedef detail::utree_type type;
+ typedef utree_type type;
template <typename UTreeX, typename UTreeY>
friend struct detail::visit_impl;
@@ -186,24 +285,6 @@
bool operator<=(utree const& a, utree const& b);
bool operator>=(utree const& a, utree const& b);
std::ostream& operator<<(std::ostream& out, utree const& x);
-
- template <typename Base>
- struct binary : Base
- {
- binary()
- : Base() {}
-
- template <typename Iterator>
- binary(Iterator bits, std::size_t len)
- : Base(bits, bits + len) {}
-
- template <typename Iterator>
- binary(Iterator first, Iterator last)
- : Base(first, last) {}
- };
-
- typedef binary<boost::iterator_range<char const*> > binary_range;
- typedef binary<std::string> binary_string;
}
#include "detail/utree_detail2.hpp"
Modified: trunk/libs/spirit/example/scheme/utree_test.cpp
==============================================================================
--- trunk/libs/spirit/example/scheme/utree_test.cpp (original)
+++ trunk/libs/spirit/example/scheme/utree_test.cpp 2010-03-22 10:19:31 EDT (Mon, 22 Mar 2010)
@@ -5,7 +5,6 @@
int main()
{
using scheme::utree;
- using scheme::ulist;
using ::detail::println;
{
@@ -68,7 +67,7 @@
println(std::cout, val);
val3.swap(val);
println(std::cout, val);
- val.push_back("Ba Ba Black Sheep");
+ val.push_back("another string");
println(std::cout, val);
val.pop_front();
println(std::cout, val);