Tiempo de compilación de traducción de texto a número (atoi)

8

Quiero implementar la función atoi () en tiempo de compilación (en lenguaje C ++, usando el estándar C ++ 11 o C ++ 14). Por lo tanto, debería poder analizar el texto encerrado entre comillas dobles como número o informar un error. Más específicamente, es parte de un sistema más grande, que es capaz de analizar el formato tipo printf en tiempo de compilación. Y quiero dividir cadenas de formato en palabras y, si alguna palabra en particular se puede representar por número, número de salida en lugar de la cadena (detrás de la escena hay una clase de serializador, que puede serializar números de manera más efectiva que las cadenas, y que es más importante, el deserializador no debería intentar analizar cada cadena como un número, porque todos los numeradores impresos dentro de la cadena de formato siempre se representan como números, pero no como cadenas) ...

Como sé dos, puede haber dos enfoques para resolver la tarea:

1) mediante el uso de funciones constexpr;

2) por metaprogramación de plantilla.

¿Qué camino puede ser mejor? Lo he intentado por primera vez, y puedo ver que hay muchos obstáculos de esta manera: especialmente pocas limitaciones relacionadas con c ++ 11. Parece que el segundo puede ser preferible, pero requiere algunos trucos (es necesario dividir la cadena en C para separar los caracteres mediante el operador "", que es compatible con gcc a partir de c ++ 14 y en clangs a partir de c ++ 11 ) Además, la solución basada completamente en TMP puede ser demasiado grande y demasiado enredada.

A continuación se muestra mi solución, me alegra escuchar algunas sugerencias al respecto.

http://coliru.stacked-crooked.com/a/0b8f1fae9d9b714b


#include <stdio.h>

template <typename T> struct Result
{
    T value;
    bool valid;

    constexpr Result(T v) : value(v), valid(true) {}
    constexpr Result() : value(), valid(false) {}
};

template <typename T>
constexpr Result<T> _atoi_oct(const char *s, size_t n, T val, int sign)
{
    return n == 0 ? Result<T>(sign < 0 ? -val : val)
        : *s >= '0' && *s <= '7' 
            ? _atoi_oct(s+1, n-1, val*T(010) + *s - '0', sign)
            : Result<T>();
}

template <typename T>
constexpr Result<T> _atoi_dec(const char *s, size_t n, T val, int sign)
{
    return n == 0 ? Result<T>(sign < 0 ? -val : val)
        : *s >= '0' && *s <= '9'
            ? _atoi_dec(s+1, n-1, val*T(10) + *s - '0', sign)
            : Result<T>();
}

template <typename T>
constexpr Result<T> _atoi_hex(const char *s, size_t n, T val, int sign)
{
    return n == 0 ? Result<T>(sign < 0 ? -val : val)
        : *s >= '0' && *s <= '9'
            ? _atoi_hex(s+1, n-1, val*T(0x10) + *s - '0', sign)
            : *s >= 'a' && *s <= 'f'
                ? _atoi_hex(s+1, n-1, val*T(0x10) + *s - 'a' + 10, sign)
                : *s >= 'A' && *s <= 'F'
                    ? _atoi_hex(s+1, n-1, val*T(0x10) + *s - 'A' + 10, sign)
                    : Result<T>();
}

template <typename T>
constexpr Result<T> _atoi_zero(const char *s, size_t n, int sign = 1)
{
    return n == 0 ? Result<T>()
        : *s >= '0' && *s <= '7'
            ? _atoi_oct(s+1, n-1, T(*s - '0'), sign)
            : *s == 'x' || *s == 'X'
                ? _atoi_hex(s+1, n-1, T(0), sign)
                : Result<T>();
}

template <typename T>
constexpr Result<T> _atoi_sign(const char *s, size_t n, int sign = 1)
{
    return n == 0 ? Result<T>()
        : *s == '0'
            ? _atoi_zero<T>(s+1, n-1, sign)
            : *s > '0' && *s <= '9'
                ? _atoi_dec(s+1, n-1, T(*s - '0'), sign)
                : Result<T>();
}

template <typename T>
constexpr Result<T> _atoi_space(const char *s, size_t n)
{
    return n == 0 ? Result<T>()
        : (*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r' || *s == '\v')
            ? _atoi_space<T>(s+1, n-1)
            : *s == '-'
                ? _atoi_sign<T>(s+1, n-1, -1)
                : *s == '+'
                    ? _atoi_sign<T>(s+1, n-1)
                    : *s == '0'
                        ? _atoi_zero<T>(s+1, n-1)
                        : _atoi_dec(s, n, T(0), 1);
}

template <size_t N> void pstr(const char (&s)[N])
{
    printf("s '%.*s'\n", int(N-1), s);
}

template <typename Str>
__attribute__((always_inline))
void _atoi(Str s)
{
    constexpr auto result = _atoi_space<long>(s.cstr(), sizeof(s.cstr())-1);
    if (result.valid)
        printf("i %ld\n", result.value);
    else
        pstr(reinterpret_cast<const char (&)[sizeof(s.cstr())]>(s.cstr()));
}

#define atoi(STR) _atoi([]() { \
                        struct S { \
                            static constexpr const char (&cstr())[sizeof(STR)] { return STR; } \
                        }; \
                        return S();  \
                    }())

int main()
{
    atoi("42");
    atoi("-1");
    atoi("+1");
    atoi("010");
    atoi("-0x10");
    atoi("--1");
    atoi("x");
    atoi("3x");
    return 0;   
}

Básicamente quiero preguntar, ¿cómo puedo transformar en el número de tiempo de compilación (como "42") escrito entre comillas dobles en el valor del tipo integral. Mi solución parece demasiado engorrosa.

fk0
fuente
En realidad he estado buscando algo como esto. Puede tener sus usos con cadenas de hashing en tiempo de compilación o algo. También otro enfoque podría ser la programación api del compilador pero sería específico del compilador.
Marcin Poloczek
C ++ 17 no es una opción ¿verdad?
Timo
Entonces, ¿qué tiene de malo su solución? ¿Y qué quieres saber exactamente? ¿Mejor en qué sentido?
florestan
@MarcinPoloczek como mencionó hashing de cadenas en tiempo de compilación: tal vez le guste esta publicación que escribí hace algún tiempo aquí en SO: stackoverflow.com/a/47081012/8494588
florestan
Versión actualizada, con comprobación de errores: coliru.stacked-crooked.com/a/9f67878a7be4310c
fk0

Respuestas:

0

Con C ++ 14 podemos deshacernos de la macro y algunos operadores ternarios. Así es como lo haría, el código debería ser autoexplicativo (también he agregado algunos comentarios). El código a continuación también se puede encontrar aquí (con algunos ejemplos) para la comparación del compilador.

#include <cstdint>
#include <iostream>

template <typename T>
struct Result
{
    T value{};
    bool valid = false;

    constexpr explicit Result(T v) : value(v), valid(true) {}
    constexpr Result() = default;
};

// converts upper case chars to lower case
constexpr char to_lower(char c)
{
    return c >= 'A' && c <= 'Z'
        ? c - 'A' + 'a'
        : c;
}

// converts a digit char to its numeric value (eg. 'F' -> 15)
constexpr int to_digit(char c)
{
    c = to_lower(c);
    return c >= 'a'
        ? c - 'a' + 10
        : c - '0';
}

// checks whether the given digit fits in the given base (eg. 'A' in 16 (hex) -> true, but '9' in 8 (oct) -> false)
constexpr bool is_digit(char c, int base)
{
    int digit = to_digit(c);
    return 0 <= digit && digit < base;
}

namespace detail
{
    // returns true if c is a sign character (+ or -), sign will hold a valid factor (1 or -1) regardless of the return value
    constexpr bool get_sign(char c, int& sign)
    {
        if (c == '-')
        {
            sign = -1;
            return true;
        }
        else
        {
            sign = 1;
            return c == '+';
        }
    }

    // adds a digit to the right side of the a number
    template <typename T>
    constexpr T append_digit(T value, int base, int digit)
    {
        return value * base + digit;
    }

    // create the actual number from the given string
    template <typename T>
    constexpr T construct_integral(const char* str, std::size_t size, int base)
    {
        T value = 0;
        for (std::size_t i = 0; i < size; i++)        
            value = append_digit(value, base, to_digit(str[i]));

        return value;
    }

    // how many chars are necessary to specify the base (ex. hex -> 0x -> 2) 
    constexpr std::size_t get_base_offset(int base)
    {
        if (base == 8) return 1;
        if (base == 16) return 2;
        return 0;
    }

    // gets the base value according to the number prefix (eg. 0x -> 16 (hex))
    constexpr int get_base(const char* str, std::size_t size)
    {
        return str[0] == '0'
            ? size > 2 && to_lower(str[1]) == 'x'
                ? 16
                : 8
            : 10;
    }

    // checks whether all digits in the string can fit in the given base
    constexpr bool verify_base(const char* str, std::size_t size, int base)
    {
        for (std::size_t i = 0; i < size; i++)
            if (!is_digit(str[i], base))
                return false;

        return true;
    }
}

template <typename T = int>
constexpr Result<T> to_integral(const char* str, std::size_t size)
{
    using namespace detail;

    // remove the sign from the string
    auto sign = 0;    
    if (get_sign(str[0], sign)) 
    {
        ++str;
        --size;
    }

    // get the base and remove its prefix from the string
    auto base = get_base(str, size);
    auto offset = get_base_offset(base);
    str += offset;
    size -= offset;

    // check if the string holds a valid number with respect to its base
    if (!verify_base(str, size, base))
        return {};

    // create the number and apply the sign
    auto unsigned_value = construct_integral<T>(str, size, base);
    return Result<T>(unsigned_value * sign);
}

template <typename T = int, std::size_t N>
constexpr Result<T> to_integral(const char(&str)[N])
{
    static_assert(N > 1, "Empty strings are not allowed");
    return to_integral<T>(str, N - 1);
}

C ++ 17 podría reducir la cantidad de código aún más mediante el uso std::string_view. Tu Result<T>también podría ser reemplazado por std::optional.

Timo
fuente