// vi:set ft=cpp: -*- Mode: C++ -*-
/*
 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * License: see LICENSE.spdx (in this directory or the directories above)
 */

/**
 * Strings.
 */
#pragma once

#include <l4/cxx/minmax>
#include <l4/cxx/basic_ostream>
#include <l4/sys/cxx/limits>
#include <l4/sys/err.h>


namespace cxx {

/**
 * Allocation free string class with explicit length field.
 *
 * This class is used to group characters of a string which belong
 * to one syntactical token types number, identifier, string,
 * whitespace or another single character.
 *
 * Strings in this class can contain null bytes and may denote parts of
 * other strings.
 */
class String
{
public:

  /// Character index type.
  typedef char const *Index;

  /// Initialize from a zero-terminated string.
  String(char const *s) noexcept : _start(s), _len(__builtin_strlen(s)) {}
  /// Initialize from a pointer to first character and a length.
  String(char const *s, unsigned long len) noexcept : _start(s), _len(len) {}

  /**
   * Initialize with start and end pointer.
   *
   * \param s  first character of the string
   * \param e  pointer to first byte behind the string
   */
  String(char const *s, char const *e) noexcept : _start(s), _len(e - s) {}

  /// Zero-initialize. Create an invalid string.
  String() : _start(0), _len(0) {}

  /// Pointer to first character.
  Index start() const { return _start; }
  /// Pointer to first byte behind the string.
  Index end() const { return _start + _len; }
  /// Length.
  int len() const { return _len; }

  /// Set start.
  void start(char const *s) { _start = s; }
  /// Set length.
  void len(unsigned long len) { _len = len; }
  /// Check if the string has length zero.
  bool empty() const { return !_len; }

  /// Return prefix up to index.
  String head(Index end) const
  {
    if (end < _start)
      return String();

    if (eof(end))
      return *this;

    return String(_start, end - _start);
  }

  /// Prefix of length `end`.
  String head(unsigned long end) const
  { return head(start() + end); }

  /// Substring of length `len` starting at `idx`.
  String substr(unsigned long idx, unsigned long len = ~0UL) const
  {
    if (idx >= _len)
      return String(end(), 0UL);

    return String(_start + idx, cxx::min(len, _len - idx));
  }

  /// Substring of length `len` starting at `start`.
  String substr(char const *start, unsigned long len = 0) const
  {
    if (start >= _start && !eof(start))
      {
	unsigned long nlen = _start + _len - start;
	if (len != 0)
	  nlen = cxx::min(nlen, len);
	return String(start, nlen);
      }

    return String(end(), 0UL);
  }

  /// Find matching character. `match` should be a function such as `isspace`.
  template< typename F >
  char const *find_match(F &&match) const
  {
    String::Index s = _start;
    while (1)
      {
	if (eof(s))
	  return s;

	if (match(*s))
	  return s;

	++s;
      }
  }

  /// Find character. Return end() if not found.
  char const *find(char const *c) const
  { return find(c, start());  }

  /// Find character. Return end() if not found.
  char const *find(int c) const
  { return find(c, start());  }

  /// Find right-most character. Return end() if not found.
  char const *rfind(char const *c) const
  {
    if (!_len)
      return end();

    char const *p = end();
    --p;
    while (p >= _start)
      {
	if (*p == *c)
	  return p;
	--p;
      }
    return end();

  }

  /**
   * Check if `c` is a prefix of string.
   *
   * \return 0 if `c` is not a prefix, if it is a prefix, return
   *         first position not in `c` (which might be end()).
   */
  Index starts_with(cxx::String const &c) const
  {
    unsigned long i;
    for (i = 0; i < c._len && i < _len; ++i)
      if (_start[i] != c[i])
	return 0;
    return i == c._len ? start() + i : 0;
  }

  /// Find character `c` starting at position `s`. Return end() if not found.
  char const *find(int c, char const *s) const
  {
    if (s < _start)
      return end();

    while (1)
      {
	if (eof(s))
	  return s;

	if (*s == c)
	  return s;

	++s;
      }
  }

  /**
   * Find character set at position.
   *
   * \param c  zero-terminated string of characters to search for
   * \param s  start position of search in string
   *
   * \retval end()     if no char in `c` is contained in string at or behind `s`.
   * \retval position  in string of some character in `c`.
   */
  char const *find(char const *c, char const *s) const
  {
    if (s < _start)
      return end();

    while (1)
      {
	if (eof(s))
	  return s;

	for (char const *x = c; *x; ++x)
	  if (*s == *x)
	    return s;

	++s;
      }
  }

  /// Get character at `idx`.
  char const &operator [] (unsigned long idx) const { return _start[idx]; }
  /// Get character at `idx`.
  char const &operator [] (int idx) const { return _start[idx]; }
  /// Get character at `idx`.
  char const &operator [] (Index idx) const { return *idx; }

  /// Check if pointer `s` points behind string.
  bool eof(char const *s) const { return s >= _start + _len || !*s; }

  /**
   * Convert decimal string to integer.
   *
   * \tparam     INT  result integer type
   * \param[out] v    conversion result
   *
   * \return position of first character not converted.
   */
  template<typename INT>
  int from_dec(INT *v) const
  {
    *v = 0;
    Index c;
    for (c = start(); !eof(c); ++c)
      {
	unsigned char n;
	if (*c >= '0' && *c <= '9')
	  n = *c - '0';
	else
	  return c - start();

        *v *= 10;
	*v += n;
      }
    return c - start();
  }

  /**
   * Convert hex string to integer.
   *
   * \tparam     INT  result integer type
   * \param[out] v    conversion result
   *
   * \retval -1        if the maximal amount of digits fitting into `INT` have
   *                   been read,
   * \retval position  of first character not converted otherwise.
   */
  template<typename INT>
  int from_hex(INT *v) const
  {
    *v = 0;
    unsigned shift = 0;
    Index c;
    for (c = start(); !eof(c); ++c)
      {
	shift += 4;
	if (shift > sizeof(INT) * 8)
	  return -1;
	unsigned char n;
	if (*c >= '0' && *c <= '9')
	  n = *c - '0';
	else if (*c >= 'A' && *c <= 'F')
	  n = *c - 'A' + 10;
	else if (*c >= 'a' && *c <= 'f')
	  n = *c - 'a' + 10;
	else
	  return c - start();

        *v <<= 4;
	*v |= n;
      }
    return c - start();
  }

  /**
   * Convert a number string to an integer.
   *
   * Converts the initial part of the string to a number, according to the
   * given `base`. The string may start with an arbitrary amount of white space
   * followed by a single optional `+` or `-` sign. If base is zero or 16, the
   * string may then include a "0x" or "0X" prefix, and the number will be read
   * in base 16; otherwise, a zero base is taken as 10 (decimal) unless the
   * next character is '0', in which case it is taken as 8 (octal).
   *
   * Conversion stops at the first character that is not a valid digit for the
   * chosen `base`. If the string does not contain any digit at all, zero is
   * returned and `v` is left unmodified.
   *
   * \tparam      INT   result integer type
   * \param[out]  v     conversion result
   * \param       base  Base of the number (0, 2..36)
   *
   * \retval >0         Success. Position of first character after the number.
   * \retval 0          The string does not contain a number.
   * \retval -L4_EINVAL Invalid `base` parameter
   * \retval -L4_ERANGE Parsed number too large to be stored in `v`
   */
  template<typename INT>
  int from_number(INT *v, unsigned base = 0) const
  {
    // Accumulate in the widest unsigned type. This way the magnitude of the
    // most negative number of a signed INT can be represented too.
    typedef unsigned long long Acc;

    if (base == 1 || base > 36)
      return -L4_EINVAL;

    // Value of character `c` in `b`, or -1 if it is not a valid digit.
    auto to_digit = [](char c, unsigned b) -> int
      {
        int d;
        if (c >= '0' && c <= '9')
          d = c - '0';
        else if (c >= 'a' && c <= 'z')
          d = c - 'a' + 10;
        else if (c >= 'A' && c <= 'Z')
          d = c - 'A' + 10;
        else
          return -1;

        return d < static_cast<int>(b) ? d : -1;
      };

    Index i = start();
    bool negate = false;
    bool have_digits = false;

    // skip leading space
    while (!eof(i) && (*i == ' ' || *i == '\t'))
      ++i;

    // optional sign
    if (!eof(i) && (*i == '-' || *i == '+'))
      {
        negate = *i == '-';
        ++i;
      }

    // Optional base prefix. The leading '0' is a valid number of its own, so
    // the "0x" prefix is only consumed if a hexadecimal digit follows.
    if ((base == 0 || base == 16) && !eof(i) && *i == '0')
      {
        have_digits = true;
        ++i;

        if (   !eof(i)     && (*i == 'x' || *i == 'X')
            && !eof(i + 1) && to_digit(i[1], 16) >= 0)
          {
            base = 16;
            ++i;
          }
        else if (base == 0)
          base = 8;
      }
    else if (base == 0)
      base = 10;

    constexpr INT Max = L4::Types::numeric_limits<INT>::max();
    constexpr INT Min = L4::Types::numeric_limits<INT>::min();

    // Upper bound of the magnitude. For signed types the negative range is one
    // larger than the positive one. Unsigned types wrap around on negation.
    Acc const limit = static_cast<Acc>(Max) + ((Min != 0 && negate) ? 1U : 0U);
    Acc const lim_div = limit / base;
    Acc const lim_mod = limit % base;

    // feed the numbers
    Acc acc = 0;
    while (!eof(i))
      {
        int d = to_digit(*i, base);
        if (d < 0)
          break;

        if (acc > lim_div || (acc == lim_div && static_cast<Acc>(d) > lim_mod))
          return -L4_ERANGE;

        acc = acc * base + static_cast<Acc>(d);
        have_digits = true;
        ++i;
      }

    if (!have_digits)
      return 0;

    if (!negate)
      *v = static_cast<INT>(acc);
    else if (Min != 0 && acc == static_cast<Acc>(Max) + 1U)
      *v = Min;
    else
      *v = static_cast<INT>(-static_cast<INT>(acc));

    return i - start();
  }

  /// Equality.
  bool operator == (String const &o) const
  {
    if (len() != o.len())
      return false;

    for (unsigned long i = 0; i < _len; ++i)
      if (_start[i] != o._start[i])
	return false;

    return true;
  }

  /// Inequality.
  bool operator != (String const &o) const
  { return ! (operator == (o)); }

private:
  char const *_start;
  unsigned long _len;
};

}

/// Write `str` on `s`.
inline
L4::BasicOStream &operator << (L4::BasicOStream &s, cxx::String const &str)
{
  s.write(str.start(), str.len());
  return s;
}
