compiletime string validator generator

GorbGorb

So, ich jetzt konnte ich auch einen AST generieren und damit einen kleinen Rechner bauen. Er kann im Moment nur + und * und nimmt auch "05" als Zahl an, aber es geht hier ja nur darum, das ganze zu demonstrieren. Auszug aus main.cpp:

#include "operators.hpp"

#include <string>
#include <iostream>

DEF_TERMINAL( MyTerminal , "asdfasdf" )

int main()
{
    //compile time parsing
    constexpr const_string< char > cstr = "2  + 54 * 2 + 83";
    constexpr addition a( cstr );
    static_assert( a.eval() == 193 , "");
    constexpr const_string< char > cstr2 = "asd fasdf";
    constexpr MyTerminal t( cstr2 );
    static_assert( !t.valid() , "" );

    //run time parsing, but I guess this is very inefficient
    std::string str;
    std::cin >> str;
    const_string< char > cstr3( &*str.begin() , &*str.end() );
    addition a_run_time( cstr3 );
    if( a_run_time.end() == str.size() )
        std::cout << a_run_time.eval() << std::endl;
    else
        std::cout << "parse error" << std::endl;
}

Den kompletten source kann man sich hier runterladen:
http://www.file-upload.net/download-4010616/compile-time-parser.zip.html

Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

Ethon

Find ich persönlich richtig genial.

Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).

Wäre es denn theoretisch möglich? Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

pyhax

Ethon schrieb:

Find ich persönlich richtig genial.
Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).
Wäre es denn theoretisch möglich? Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

Oder ein "in c++ c++ compiler xD" Lol könnte der sich dann nicht selbst kompiliern? oO Kann mir das gerade nicht so richtig vorstellen ... ein Compiler der sich während des Erstellens selbst compiled?!

GorbGorb

Ethon schrieb:

Find ich persönlich richtig genial.
Das hat jetzt vielleicht so langsam einen Sinn... vielleicht wird man irgendwann z.B. SQL in c++ compilen können (inklusive Syntaxchecks und c++ performance).
Wäre es denn theoretisch möglich?

Ich wüsste nicht, warum es nicht möglich sein sollte. Den query könnte man natürlich nicht zur Compilezeit ausführen (macht ja auch wenig Sinn), aber man kann schonmal den Befehl in c++ (und dann in Maschinencode) übersetzen.

Wenn ja, lust eine minimale Scriptsprache mit einem "print xyz" Befehl zu bauen? Würde das gerne sehen.

Wie meinst du das? Eine Sprache die nur "print string" kann, beim compilen übersetzt wird und den string dann über ein code.exec() zur Laufzeit ausgibt? Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

pyhax schrieb:

Oder ein "in c++ c++ compiler xD" Lol könnte der sich dann nicht selbst kompiliern? oO Kann mir das gerade nicht so richtig vorstellen ... ein Compiler der sich während des Erstellens selbst compiled?!

Er könnte seinen eigenen Quellcode übersetzen, ja. Aber so ungewöhnlich ist das nicht, der gcc oder javac können das auch.

camper

GorbGorb schrieb:

Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

Eine Möglichkeit:

#include <cstddef>
#include <iostream>

template <typename T> struct identity
{
    using type = T;
};
template <std::ptrdiff_t... i> struct index_list
    : identity<index_list<i...>> {};

template <typename... T> struct concat_index_lists
    : concat_index_lists<typename T::type...> {};
template <std::ptrdiff_t... i, std::ptrdiff_t... j, typename... T> struct concat_index_lists<index_list<i...>, index_list<j...>, T...>
    : concat_index_lists<index_list<i..., j...>, T...> {};
template <std::ptrdiff_t... i> struct concat_index_lists<index_list<i...>>
    : identity<index_list<i...>> {};

template <typename T, std::ptrdiff_t shift> struct shift_index_list
    : shift_index_list<typename T::type, shift> {};
template <std::ptrdiff_t... i, std::ptrdiff_t shift> struct shift_index_list<index_list<i...>, shift>
    : identity<index_list<(i + shift)...>> {};

template <std::size_t N> struct make_index_list
    : concat_index_lists<make_index_list<N / 2>, shift_index_list<make_index_list<N / 2>, N / 2>, shift_index_list<make_index_list<N % 2>, N - 1>> {};
template <> struct make_index_list<1>
    : identity<index_list<0>> {};
template <> struct make_index_list<0>
    : identity<index_list<>> {};

template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, typename = typename make_index_list<end - begin>::type> struct substr;
template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, std::ptrdiff_t... i> struct substr<str, begin, end, index_list<i...>>
{
    static constexpr char value[] = { str[ i + begin ]..., '\0' };
};
template <const char* str, std::ptrdiff_t begin, std::ptrdiff_t end, std::ptrdiff_t... i>
constexpr char substr<str, begin, end, index_list<i...>>::value[];

extern constexpr char test[] = "substr123";

int main()
{
    std::cout << substr<test, 4, 8>::value << '\n';
}

(gcc-4.7 erforderlich, Anpassung in 4.6 ist möglich).
Hier hatte ich auch ein paar Techniken verwendet, die nützlich sein könnten.

Ethon

Ich wüsste nicht, warum es nicht möglich sein sollte. Den query könnte man natürlich nicht zur Compilezeit ausführen (macht ja auch wenig Sinn), aber man kann schonmal den Befehl in c++ (und dann in Maschinencode) übersetzen.
Zitat:

...

Wie meinst du das? Eine Sprache die nur "print string" kann, beim compilen übersetzt wird und den string dann über ein code.exec() zur Laufzeit ausgibt? Es gäbe vielleicht die Möglichkeit, über ein static_assert eine Ausgabe beim compilen zu erzeugen... aber ich wüsste jetzt so spontan nicht, wie ich einen constexpr char substr[] aus einem anderen constexpr string generieren könnte...

Na das meinte ich ja ungefähr.
Mich hat interessiert wie es aussehen würde aus einem

constexpr const_string< char > cmd = "print Hallo";

ein

std::cout << "Hallo";

zu bauen (und logischerweise zu kompilieren), da du ja meintest dass soetwas möglich ist.

Für mich ist die ganze Meta-Templatespielerei noch recht schwarze Magie.

GorbGorb

Wie immer sehr kompetenter Beitrag, hab ne Weile gebraucht bis ich alles verstanden hatte (vor allem, um zu begreifen was make_index tun soll... ist es so deutlich schneller als mit der naiven Variante?).

camper schrieb:

extern constexpr char test[] = "substr123";

Kannst du das extern bisschen erklären? Warum kann man test nur damit als template Parameter verwenden?

@Ethon:

#include <iostream>

#include "terminal.hpp"
#include "concat.hpp"
#include "repet.hpp"

DEF_TERMINAL( Tprint , "print" )

struct anything
    : symbol
{
    constexpr anything( const_string< char > str , unsigned int begin = 0 )
        : symbol( str.size() ) ,
          m_str( str ) ,
          m_begin( begin )
    {
    }
    void print() const
    {
        std::cout << m_str.m_begin + m_begin;
    }
    const_string< char > m_str;
    unsigned int m_begin;
};

struct statement
    : concat
    <
        Tprint ,
        concat< terminal< ' ' > , repet< terminal< ' ' > > > ,
        anything
    >
{
    template< class ...ArgTypes >
    constexpr statement( ArgTypes ...args )
        : concat
        <
            Tprint ,
            concat< terminal< ' ' > , repet< terminal< ' ' > > > ,
            anything
        >( args... )
    {
    }
    void exec() const
    {
        get< 2 >().print();
    }
};

int main()
{
    constexpr statement s( const_string< char >( "print hello world" ) );
    static_assert( s.valid() , "" );
    s.exec();
}

Braucht die files von dem mathparser. Außerdem wirst du erst eine Fehlermeldung bekommen, dass m_begin in const_string private ist, mach es einfach public.
Diese Variante kommt natürlich nur mit einem "print" klar und gibt dann den Rest aus.

camper

GorbGorb schrieb:

Wie immer sehr kompetenter Beitrag, hab ne Weile gebraucht bis ich alles verstanden hatte (vor allem, um zu begreifen was make_index tun soll... ist es so deutlich schneller als mit der naiven Variante?).

camper schrieb:
extern constexpr char test[] = "substr123";
Kannst du das extern bisschen erklären? Warum kann man test nur damit als template Parameter verwenden?

Schnelligkeit ist nicht so sehr das Problem, Speicherverbrauch dagegen schon, und der nimmt bei linearer Implementierung ziemlich schnell zu.

Das extern gehört dahin, weil nur Zeiger auf Objekte mit externer Bindung Templateargumente sein können, deshalb können auch Stringliterale nicht direkt als Templateargumente verwendet werden.

Man könnte auch eine einfache Funktion schreiben

template <std::ptrdiff_t... i>
constexpr std::array<char, sizeof...(i)+1> substr_impl(const char* str, index_list<i...>)
{
    return std::array<char, sizeof...(i)+1>{ { str[i]..., 0 } };
}

template <ptrdiff_t begin, ptrdiff_t end>
constexpr std::array<char,end-begin+1> substr(const char* str)
{
    return substr_impl(str, typename shift_index_list<make_index_list<end - begin>, begin>::type());
}

GorbGorb

Ich seh grade dass man in static_assert einen string literal braucht... hatte erwartet dass es nur ein konstanter Ausdruck sein muss. Dann hat sich die Sache mit der Ausgabe über static_assert natürlich eh erledigt. (schade, das wäre witzig gewesen die Ausgabe eines Programms über die Fehlermeldungen des compilers laufen zu lassen)

314159265358979

Wo wir gerade bei TMP-Magie sind, ich habe vorgestern eine kleine Compiletime-Bigint Lib geschrieben. Im Moment ist nur Addition, Shifts, Vergleichsoperatoren und ein min/max implementiert, aber das kann man ja relativ einfach erweitern...
http://ideone.com/U7OzC
to_string gibt derzeit nur Binärstrings zurück und wahrscheinlich kann man am Code vieles vereinfachen. Ich hab das um 3 Uhr morgens gemacht.

camper

314159265358979 schrieb:

Wo wir gerade bei TMP-Magie sind, ich habe vorgestern eine kleine Compiletime-Bigint Lib geschrieben. Im Moment ist nur Addition, Shifts, Vergleichsoperatoren und ein min/max implementiert, aber das kann man ja relativ einfach erweitern...
http://ideone.com/U7OzC
to_string gibt derzeit nur Binärstrings zurück und wahrscheinlich kann man am Code vieles vereinfachen. Ich hab das um 3 Uhr morgens gemacht.

Gegeben sei

#include <cstddef>

template <typename T> struct identity
{
    typedef T type;
};

template <std::size_t... i> struct index_list
    : identity<index_list<i...>> {};

template <typename T>       struct append_index_list
    : append_index_list<typename T::type> {};
template <std::size_t... i> struct append_index_list<index_list<i...>>
    : identity<index_list<0, ( i + 1 )...>> {};

template <std::size_t N> struct make_index_list
    : append_index_list<make_index_list<N - 1>> {};
template <>              struct make_index_list<0>
    : identity<index_list<>> {};

template <char... c> struct string
    : identity<string<c...>>
{
    static constexpr char value[] = { c..., '\0' };
};
template <char... c>
constexpr char string<c...>::value[];

template <typename str, typename indexes> struct substr
    : substr<typename str::type, typename indexes::type> {};
template <typename str, std::size_t... i> struct substr<str, index_list<i...>>
    : identity<string<str::value[i]...>> {};

#define C( s, x )        (x<sizeof(s)?s[x]:'\0')
#define STR4( s, x )     C( s, x), C(s, x+1), C(s, x+2), C(s, x+3)
#define STR16( s, x )    STR4(   s, x), STR4(   s, x+4),    STR4(  s, x+8),     STR4(   s, x+12)
#define STR64( s, x )    STR16(  s, x), STR16(  s, x+16),   STR16( s, x+32),    STR16(  s, x+48)
#define STR256( s, x )   STR64(  s, x), STR64(  s, x+64),   STR64( s, x+128),   STR64(  s, x+192)
#define STR1024( s, x )  STR256( s, x), STR256( s, x+256),  STR256(s, x+512),   STR256( s, x+768)
#define STR4096( s, x )  STR1024(s, x), STR1024(s, x+1024), STR1024(s, x+2048), STR1024(s, x+3072)
#define STRING( x )      substr<string<STR4096(x,0), '\0'>,make_index_list<sizeof(x)>>::type

#include <iostream>
int main()
{
    std::cout << STRING("12345")::value << '\n';
}

Jetzt möchte ich eine Template-Metafunktion haben, die Strings direkt parst und ggf. Berechnungen anstellt, also z.B.

std::cout << compute<STRING("10+20+30")::value

sollte dann 60 ausgeben.

314159265358979

So blöd es klingt, aber einen Mathe-Parser kriege ich nicht mal mit "normalen" Funktionen ordentlich hin. Da kann ich einen über TMP erst recht nicht.