// Implementation of checked_array and char_array.
// (c) 2006 David Manura, Licensed under the MIT license.
//
// This implements the checked_array template class, which is an array
// of variable-length (length) stored in a buffer of static size
// (capacity).  This class is essentially an efficient replacement for
// C arrays (and in particular C strings) but with robust bounds
// checking.  capacity is known at compile time and is contained in
// the type, so it will never grow.
//
//   // char buffer of capacity 10 containing string of length 4+1.
//   checked_array<char, 10> s = "test";
//
// check_array is implemented basically as
//
//   template<class T, size_t N>
//   struct {
//     static const int m_capacity = N;
//     T[N] m_buf;
//     size_t m_length;
//     size_t m_maxlength;
//   };
//
// The class does not internally use malloc.  Rather the buffer in the
// example above is allocated entirely on the stack.  checked_array is
// therefore quite similar to boost::array
// (http://www.boost.org/doc/html/array.html).  The intention of the
// boost::array approach is efficiency and semantics similar to value
// types for situations that can handle it.
//
// Unlike boost::array, length can be modified at run-time (up to
// capacity).  checked_array is also specifically designed to handle
// null-terminated arrays, particularly null-terminated (C-like)
// character strings.  Even though the length may be deduced from the
// terminal character, we explicitly store the length inside the
// object for O(1) determination of length.  A class char_array is
// subclassed for this purpose.
//
//   char_array<10> s = "test";  // same as above
//
// In the interest of robust bounds checking, a unique feature of
// checked_array is that it stores not just capacity and length but
// also the maximum length (maxlength) that the array might have at a
// given time given all possible run-time conditions.  For example,
//
//   bool b = ...;
//   char_array<10> s(b ? "test" : "test5678");
//
// Here, the capacity is 10.  If b is true, the length is 4+1.
// However, the maximum length, which depends on b, is 8+1.  As in the
// case above, we specify maxlength explicitly if it is not deduced:
//
//   s.maxlength(9);
//
// If we attempt for append more than one character to the string, a
// run-time assertion will trigger:
//
//   strcat_t(s, "90"); // asserts
//
// Here, the buffer can store these additional characters, so the
// (length <= capacity) check passes under the current run-time
// conditions (b true).  However, it would not be possible to store
// them under different run-time conditions (b false), and this is an
// error in the program.  We really want to ensure that the program
// runs correctly under all run-time conditions, and this is where
// maxlength comes in.  The maxlength check (maxlength <= capacity)
// will assert regardless of the run-time condition and therefore
// provides a more aggressive means of error detection in the program.
//
// This class has various other compile-time and run-time error checking.
//
// Additional classes checked_array_ref and char_array_ref are provided
// for cases where the array is stored external to the object.
//
//   char s[6] = "test";
//   char_array_ref s2(s, false);
//   strcat_t(s2, "!"); // s is now "test!"
//   strcat_t(s2, "!"); // this will fail
//
// As shown above (strcat_t), various inline template functions
// analogous to C string functions (and wrappers around them) are
// provided for more safely manipulating strings.
//
//  template <class D, class S>
//  inline void strcat_t(D & d, const S& s);
//
// This code makes use of templates (metaprogramming) and the boost
// libraries (www.boost.org).  Therefore it may only work on recent
// C++ compilers.
//
// This code is still under development.  Errors are likely.  A
// possible improvement is to templatize the error checking
// (e.g. allow assert, throw, or silent truncate behavior to be
// selected).

#include <iostream>
#include <string>
#include <cassert>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_const.hpp>
#include <boost/type_traits/add_reference.hpp>//test
#include <boost/type_traits/add_const.hpp>//test
#include <boost/type_traits/remove_reference.hpp>//test

template<class T, size_t N> class checked_array_ref;
template <size_t N, class T> class char_array_ref;

#ifdef removed // not fully working
// implement add_reference for check_array_ref
namespace boost { namespace detail {
    // based on BOOST_TT_AUX_TYPE_TRAIT_IMPL_SPEC1
    template <class T, size_t N>
    struct add_reference_impl< checked_array_ref<T,N> > {
        typedef checked_array_ref<T,N> type;
    };
    template <class T, size_t N>
    struct add_reference_impl< const checked_array_ref<T,N> > {
        typedef const checked_array_ref<T,N> type;
    };
}}
#endif

// Type traits used by checked_array and others.

template <class S>
struct info {
    static const int m_capacity = S::m_capacity;
    static const bool is_maxlength_known = true;
    static const bool is_capacity_known = true;
    static std::string debug_type() { return "S"; }
    static int length(const S& s) { return s.length(); }
    static int maxlength(const S& s) { return s.maxlength(); }
    static typename S::value_type * c_str(S& s) { return s.c_str(); }
    static const typename S::value_type * c_str_const(const S& s) { return s.c_str_const(); }

    static void lengths(S& s, int maxlength, int length) {
        s.lengths(maxlength, length);
    }
};
template <class T, int N>
struct info<T[N]> {
    typedef T value_type;
    static const bool is_maxlength_known = true;
    static const bool is_capacity_known = true;
    static const int m_capacity = N;
    static std::string debug_type() {
        const char * base = boost::is_same<T,char>::value ? "char"
                          : boost::is_same<T,const char>::value ? "const char"
                          : "T";
        char s[100];
        sprintf(s, "%s [%d]", base, int(N));
        return s;
    }
    static int length(const T s[N]) { return strlen(s)+1; } // FIX:generic?
    static int maxlength(const T s[N]) { return N; }
    static T * c_str(T s[N]) { return s; }
    static const T * c_str_const(const T s[N]) { return s; }
    static void lengths(T s[N], int maxlength, int length) {
        assert(N >= maxlength);
        assert(maxlength >= length);
        assert(length >= 1);
    }
};

template <class T>
struct info<T *> {
    static const bool is_maxlength_known = false;
    static const bool is_capacity_known = false;
    static const int m_capacity = 0; //fix?
    static const std::string debug_type() { return "T *"; }
    static int length(T * s) { return strlen(s)+1; }
    static char * c_str(T * s) { return s; }
    static const char * c_str_const(T * s) { return s; }

    static int maxlength(T * s) { assert(0); return 0; } // disabled
private: //disable
    static void lengths(T * s, int maxlength, int length) { } // unused
};

// checked array.
template<class T, size_t N> class checked_array
{
private:
    char m_buf[N];
    size_t m_length;
    size_t m_maxlength;
public:
    typedef char value_type;

    static const size_t m_capacity = N;

    /* default constructor */
    checked_array() : m_length(1), m_maxlength(1) {
        assert(m_capacity >= 1);
        m_buf[0] = 0;
    }

    /* copy constructors */
    // examples for S: char[5], char *, const char *, char * const, const char * const,
    //   [const] checked_array<T,10>.
    template <class S>
    checked_array(const S & s, bool max = true) {
        typedef S S1;
        m_length = info<S1>::length(s);
        //FIX: assert when max true and max length not known?
        m_maxlength = max ? (info<S1>::is_maxlength_known ? info<S1>::maxlength(s) : N)
                          : m_length;
        assert(m_capacity >= m_maxlength);
        assert(m_maxlength >= m_length);
        memcpy(m_buf, info<S1>::c_str_const(s), m_length * sizeof(T));
    }

    template< template<size_t M> class checked_array2, size_t M >
    checked_array& operator=(const checked_array2<M>& other)
    {
        m_length = other.m_length; m_maxlength = other.m_maxlength;
        memcpy(m_buf, other.m_buf, other.m_length * sizeof(T));
        return *this;
    }

    char * c_str() { return m_buf;} 
    const char * c_str_const() const { return m_buf; }
    int length() const { return m_length; }
    void length(int n) {
        assert(m_capacity >= n);
        assert(m_maxlength >= n);
        m_length = n;
    } 
    int maxlength() const { return m_maxlength; }
    void maxlength(int n) {
        assert(m_capacity >= n);
        assert(m_length <= n);
        m_maxlength = n;
    }
    void lengths(int maxlength, int length) {
        assert(m_capacity >= maxlength);
        assert(maxlength >= length);
        assert(length >= 1);
        m_maxlength = maxlength;
        m_length = length;
    }

    size_t capacity() const { return m_capacity; }

    template <class T2, size_t M> friend class checked_array;
};

// checked array reference.
// This is like checked_array but stores only a reference to the
// array buffer (rather than the array buffer itself).
template<class T, size_t N> class checked_array_ref
{
private:
    T * m_buf;
    size_t m_length;
    size_t m_maxlength;

    checked_array_ref(); // disabled
public:
    typedef T value_type;
    static const size_t m_capacity = N;

    /* copy constructors */
    template <class S>
    checked_array_ref(S& s, bool max = true) : m_buf(s) {
        //improve:assert if capacity not known?
        BOOST_STATIC_ASSERT(!info<S>::is_capacity_known || info<S>::m_capacity >= N);
        m_length = info<S>::length(s);
        m_maxlength = max ? N : m_length;
        assert(m_capacity >= m_maxlength);
        assert(m_maxlength >= m_length);
    }

    checked_array_ref& operator=(const checked_array_ref& other) {
        m_buf = other.m_buf;
        m_length = other.m_length;
        m_maxlength = other.m_maxlength;
    }

    T * c_str() const { return m_buf;} 
    const T * c_str_const() const { return m_buf; }
    int length() const { return m_length; }
    checked_array_ref<T,N>& length(int n) {
        assert(m_capacity >= n);
        assert(m_maxlength >= n);
        m_length = n;
        return *this;
    } 
    int maxlength() const { return m_maxlength; }
    checked_array_ref<T,N>& maxlength(int n) {
        assert(m_capacity >= n);
        assert(m_length <= n);
        m_maxlength = n;
        return *this;
    }
    checked_array_ref<T,N>& lengths(int maxlength, int length) {
        assert(m_capacity >= maxlength);
        assert(maxlength >= length);
        assert(length >= 1);
        m_maxlength = maxlength;
        m_length = length;
        return *this;
    }
    size_t capacity() const { return m_capacity; }
};

// checked char array.
// This is an implementation of checked_array for character strings.
// T should normally be char.
template <size_t N, class T = char>
class char_array : public checked_array<char, N>
{
public:
    char_array() : checked_array<char,N>() { }

    template <class S>
    char_array(const S & s, bool max = true) : checked_array<char,N>(s, max) { }
};


// checked char array reference.
// This is an implementation fo checked_array_ref for character strings.
// T should usually be char or const char.
template <size_t N, class T = char>
class char_array_ref : public checked_array_ref<T, N>
{
private:
    char_array_ref(); // disabled
public:

    template <class S>
    char_array_ref(S& s, bool max = true) : checked_array_ref<T,N>(s, max) { }
};


// safer template version of of strcat.
template <class D, class S>
inline void strcat_t(D & d, const S& s) {
    //typedef typename boost::add_reference<D>::type D2;
    typedef D D2;
    BOOST_STATIC_ASSERT(!boost::is_const<D2>::value);
    info<D2>::lengths(
        d, 
        info<D2>::maxlength(d) + info<const S>::maxlength(s) - 1,
        info<D2>::length(d) + info<const S>::length(s) - 1
    );
    strcat(info<D2>::c_str(d), info<const S>::c_str_const(s));
}

// safer template version of of strcpy.
template <class D, class S>
inline void strcpy_t(D & d, const S& s) {
    typedef D D2;
    //typedef typename boost::add_reference<D>::type D2;
    BOOST_STATIC_ASSERT(!boost::is_const<D2>::value);
    info<D2>::lengths(
        d,
        info<const S>::maxlength(s),
        info<const S>::length(s)
    );
    strcpy(info<D2>::c_str(d), info<const S>::c_str_const(s));
}

// truncate string
// fix:include zero char?
template <class D>
inline void strtruncate_t(D& d, size_t n) {
    BOOST_STATIC_ASSERT(!boost::is_const<D>::value);
    info<D>::lengths(
        d,
        n,
        n
    );
    assert(n > 0);
    d.c_str()[n - 1] = '\0';
}

// T should normally be char or const char.
template <class T, size_t N>
char_array_ref<N,T> char_array_ref_cast(T (&s)[N], bool max = true)
{
  return char_array_ref<N,T>(s, max);
}