constexpr Argument-Wrapper

[Wilhelm M. (wimalopaan)]

Eine sehr interessante Möglichkeit, constexpr-Argumente zu deklarieren.

Hintergrund: klassische Baumstrukturen mit Zeigern können nur dann 
constexpr sein, wenn die Objekte der statischen Speicherklasse 
angehören. Ein möglicher Ausweg könnte sein, den Baum nicht mit Hilfe 
von Zeigern, sondern mit heterogenen Containern wie etwa std::tuple<> 
aufzubauen. Dann ist der Baum aber schlecht zu traversieren. Also macht 
man aus dem Baum eine Liste. Dabei kann es vorkommen, dass man 
Funktionsparameter als constexpr-Werte verwenden möchte (etwa als 
Nicht-Typ-Parameter eines Templates). Zwar ist das Argument beim 
Funktionsaufruf constexpr, innerhalb der (constexpr) Funktion ja aber 
nicht mehr.

Dazu ein einfaches Beispiel aus einem anderen Kontext: value ist 
constexpr, innerhalb des Funktionstemplate transform1 ist v aber 
nicht mehr constexpr, da das Funktionstemplate ja auch in einem 
non-constexpr Kontext aufgerufen werden kann. Insofern kann man v 
nicht als nicht-Typ Parameter von std::integral_constant verwenden.

Abhilfe: man verpackt den constexpr-Ausdruck in einen (constexpr) 
lambda-Ausdruck (C++17) und packt das Argument innerhalb der 
constexpr-Funktion wieder aus.

#include <type_traits>

constexpr auto transform1(auto v) {
    return std::integral_constant<int, v>{};
}

constexpr auto transform2(const auto& callable) {
    constexpr auto v = callable();
    return std::integral_constant<decltype(v), v>{};
}

int main() {
    constexpr int value = 42;

    //    constexpr auto result1 = transform1(value);  // not possible
    
    [[maybe_unused]] constexpr auto result2 = transform2([&]{return value;}); // constant lambda argument wrapper
}

Ich finde es genial ... (damit konnte ich etwa ein ganzes Menu (als 
Baumstruktur) in eine heterogene List (tuple) umwandeln und war jeden 
Overhead (bspw. vtables im RAM und sonstige Zeiger-Indirektion) los. 
Mehr Flash, weniger RAM).

[mh (Gast)]

Vielen Dank für die Info. Ich werde mir den Link (aus deinem anderen 
Post) bei Gelegenheit durchlesen.

Was mir beim Überfliegen aufgefallen ist:

transform2(const auto& callable)

Seit wann sind auto Parameter erlaubt? Gcc ist damit zufrieden, clang 
nicht.

Mache ich daraus ein

template<typename foo>
transform2(const foo& callable)

ist gcc weiterhin damit zufrieden, clang sagt:

error: constexpr variable 'v' must be initialized by a constant expression

[mh (Gast)]

Ok das war zu schnell. Mit pass-by-value

template<typename foo>
constexpr auto transform2(foo callable)

ist auch clang zufrieden.

[Wilhelm M. (wimalopaan)]

mh schrieb:
> Vielen Dank für die Info. Ich werde mir den Link (aus deinem anderen
> Post) bei Gelegenheit durchlesen.
>
> Was mir beim Überfliegen aufgefallen ist:
>

transform2(const auto& callable)

> Seit wann sind auto Parameter erlaubt? Gcc ist damit zufrieden, clang
> nicht.

Sorry. Das geht nur, weil der gcc schon concepts unterstützt, der clang 
aber noch nicht. Weil ich aber schon concepts heftigst einsetze, ist mir 
das gar nicht aufgefallen.

[Wilhelm M. (wimalopaan)]

Das eigentliche Beispiel unter Verwendung von concepts sieht auch so 
aus:

#include <cstddef>
#include <type_traits>

constexpr auto transform1(const auto& v) {
    return std::integral_constant<int, v>{}; // v ist not constexpr in this context
}

template<typename C, typename T>
concept bool Callable() {
    return requires(C l) {
        {l()} -> T;
    };
}
constexpr auto transform2(const Callable<size_t>& callable) {
    constexpr auto v = callable();
    return std::integral_constant<decltype(v), v>{};
}

int main() {
    constexpr int value = 42;

    //    constexpr auto result1 = transform1(value);  // not possible
    
    [[maybe_unused]] constexpr auto result2 = transform2([&]{return value;}); // constant lambda argument wrapper
    
//    transform2(value); // constraint not satisfied
//    transform2([&]{return std::byte{0};}); // constraint not satisfied
}

Geht natürlich im Moment auch nur mit gcc (und -fconcepts).

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> klassische Baumstrukturen mit Zeigern können nur dann
> constexpr sein, wenn die Objekte der statischen Speicherklasse
> angehören.

Und wie hilft der Code dabei, eine "klassische" Baumstruktur constexpr 
zu machen?  So eine Struktur hat man ja statisch verzeigert, z.B. als 
Liste oder (Menü-)Baum), etwa in C:

typedef struct T
{
    int val;
    const struct T *leaf[2];
} T;

const T a, b, c;

const T a = { 'a', { &c, &b } };
const T b = { 'b', { &a, &b } };
const T c = { 'c', { &b, &a } };

int get1 (void)
{
    return a.leaf[0]->leaf[0]->leaf[1]->leaf[1]->leaf[0]->val;
}

Die 3 Knoten a, b und c ergeben ein Konstrukt, das kein RAM belegt[*]:

.section  .rodata
.global  c
c:
  .word  99
  .word  b
  .word  a
.global  b
b:
  .word  98
  .word  a
  .word  b
.global  a
a:
  .word  97
  .word  c
  .word  b

Und auch der Zugriff in get1() wird effizient umgesetzt (hier avr):

get1:
  ldi r24,lo8(97)   ;  9  *movhi/5  [length = 2]
  ldi r25,0
  ret

Mit constexpr hätte man zunächst das Problem, dass die Link-Time 
Konstanten &a, &b und &c keine Compile-Time Konstanten sind, d.h. nicht 
constexpr sein können.  Man müsste also die 3 Adressen durch Skalare 
ersetzen, aber dann würde ich nicht mehr von einem "klassischen" Baum 
reden.

Und ich seh auch nicht, wie man hier RAM sparen kann, denn es wird gar 
kein RAM zur Speicherung benötigt...

Falls die genaue Art der Verwendung der Struktur erst zur Laufzeit 
feststeht — etwa Menü-Auswahl per Eingabe vom Anwender — dann kann man 
auch nur zur Laufzeit entscheiden, was zu tun ist (hier für avr):

int get2 (int id)
{
    return a.leaf[1]->leaf[0]->leaf[id]->leaf[1]->leaf[0]->val;
}

Was aber die Datenablage in keinster Weise berührt. Oder geht es um 
Optimierungen wie die folgende, die einen dynamischen Lookup vermeidet?

int get3 (int id)
{
    return id
        ? a.leaf[1]->leaf[0]->leaf[1]->leaf[1]->leaf[0]->val
        : a.leaf[1]->leaf[0]->leaf[0]->leaf[1]->leaf[0]->val;
}

was je nach Silizium / Compiler kleineren / schnelleren Code gibt (und 
immer noch kein RAM braucht):

get3:
  or r24,r25
  brne .L5
  ldi r24,lo8(99)
  ldi r25,0
  ret
.L5:
  ldi r24,lo8(97)
  ldi r25,0
  ret

> Ich finde es genial ...

Ich versteh ehrlich gesagt überhaupt nicht, was da passiert — oder nicht 
passiert...  Im obigen Beispiel müsste man dann &a, &b und &c in 
std::integral_constant einpacken, damit es Compile-Time Konstanten 
werden, damit man die überhaupt verwenden darf?

[*] Bei schrägem[tm] Silizium wie AVR legt man händisch ins Flash:

#if !defined (__FLASH) || !defined (__AVR__) || !defined (__GNUC__)
#define __flash /* empty */
#endif

typedef struct T
{
    int val;
    const __flash struct T *leaf[2];
} T;

const __flash T a, b, c;
...

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:

> Die 3 Knoten a, b und c ergeben ein Konstrukt, das kein RAM belegt[*]:
>
>

.section  .rodata
> .global  c
> c:
>   .word  99
>   .word  b
>   .word  a
> .global  b
> b:
>   .word  98
>   .word  a
>   .word  b
> .global  a
> a:
>   .word  97
>   .word  c
>   .word  b

>

Kein RAM? (section .rodata) Für mich sind das 18-Bytes.

> [*] Bei schrägem[tm] Silizium wie AVR legt man händisch ins Flash:
>
>

> #if !defined (__FLASH) || !defined (__AVR__) || !defined (__GNUC__)
> #define __flash /* empty */
> #endif
> 
> typedef struct T
> {
>     int val;
>     const __flash struct T *leaf[2];
> } T;
> 
> const __flash T a, b, c;
> ...

... die Daten sollten aber schon geändert werden können ...

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> ... die Daten sollten aber schon geändert werden können ...

Dann können sie natürlich nicht const und auch nicht constexpr sein.

Und wenn die Daten in .rodata liegen kannst du sie auch nicht ändern, 
selbst wenn eine Implementation .rodata im RAM ablegt: Solche Daten zu 
ändern ist Undefined Behaviour.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
> Wilhelm M. schrieb:
>> ... die Daten sollten aber schon geändert werden können ...
>
> Dann können sie natürlich nicht const und auch nicht constexpr sein.
>
> Und wenn die Daten in .rodata liegen kannst du sie auch nicht ändern,
> selbst wenn eine Implementation .rodata im RAM ablegt: Solche Daten zu
> ändern ist Undefined Behaviour.

Da sollen sie ja auch gar nicht hin ;-) Sie sollten schon non-const sein 
...

[Wilhelm M. (wimalopaan)]

Das Beispiel, das ich angeführt hatte, über führt die Baum- struktur 
in eine Typ-Information (zur Laufzeit nicht mehr existent), die Objekte 
selbst sind aber non-const.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> Das Beispiel, das ich angeführt hatte, über führt die Baum- /struktur/
> in eine Typ-Information (zur Laufzeit nicht mehr existent), die Objekte
> selbst sind aber non-const.

Wenn die Info in Typen steckt, dann brauch ich doch darkeine Objekte 
diesen Type mehr?  Und auch keine Argumente diesen Typs zu übergeben? 
Da kann man doch einfach den Typ selbst nutzen?

So wie wenn ich sizeof verwende.

size_t get_size (int i)
{
    return sizeof (i);
}

Hier brauch ich gar kein Objekt und kein Argument, da die Info im Typ 
selber steckt:

size_t get_size (void)
{
    return sizeof (int);
}

Irgendwie versteh ich die ganze Denke nicht, und da werden wohl Probleme 
gelöst, die durch ein Übermaß an Sprachmitteln erste entstehen, und 
durch noch kompliziertere — Verzeihung, genialere — Features umgangen 
werden müssen.

[Wilhelm M. (wimalopaan)]

Was hat das jetzt mit bspw. einem Baum zu tun?

Das Beispiel war etwa ein Baum, der weder in Tiefe noch Knoten-Arität 
prinzipiellen Beschränkungen unterliegt, dessen Struktur aber fix ist. 
"Normalerweise" realisiert man das mit Zeigern oder anderen 
"Referenzen", und der Anwender soll sich dabei nicht um Details kümmern 
müssen. Sowas könnte man etwa mit folgender Schnittstelle machen:

Node root;
root.add(Node(1));

Node nt;
nt.add(Node(2));
root.add(nt);

// ...

Wird der Baum in seiner Struktur zur Laufzeit nicht verändert, sondern 
nur die Daten der Knoten, dann besteht eigentlich kein Grund, die 
Struktur durch Objekte zur Laufzeit (Zeiger, Knotenindizes, etc.) im 
Ram abzubilden. Man könnte also die fixe Struktur vom Compiler zur 
Compilezeit in eine Typ-Information überführen 
(Template-Meta-Programmierung: mit Meta-Funktionen kann man Typen (nicht 
Werte) zur Compilezeit "berechnen") lassen.

Aus dem Obigen könnte man in etwa den Typ

Tree<2, Data, Tree<1, Data>>

ableiten. Dann braucht man in diesem Typ nur noch Datenelemente etwa vom 
Typ Data oder was auch immer die Knotendaten für einen Typ haben. Die 
Struktur steckt aber in dem Datentyp des Baumes selbst drin. Dies führt 
dazu, dass die fixe Struktur des Baumes im Code enthalten ist (und 
deswegen selbstverständlich Flash belegt: s.o. meine Bemerkung: mehr 
Flash, weniger Ram). Etwa so, als hätte man die Anzahl der Kinder, Tiefe 
und den Datentyp der Knotenwerte zu Fuß hart codiert.

Natürlich kann man den Code für eine fixe Baumstruktur auch zu Fuß 
schreiben.  Das muss man dann aber für jeden Anwendungsfall neu machen. 
Genau diese Arbeit kann man aber zur Compilezeit den Compiler machen 
lassen - wenn man möchte.
Im Grunde ist das so ähnlich wie eine DSEL.

Und genau dabei war der "kleine Trick" wie man an Funktionen constexpr 
Objekte übergeben kann, sehr hilfreich. Nicht mehr und nicht weniger ...

Wer ein komplexeres Beispiel einer derartigen Anwendung haben möchte, 
der sollte sich den Vortrag von Jason Turner und Ben Deane auf den 
CppCon2017 ansehen: dort wird ein constexpr JSON-Parser vorgestellt. Mit 
dem kann man eine JSON-Definition (als String) zur Compilezeit parsen.

[Vincent H. (vinci)]

Johann L. schrieb:
> Irgendwie versteh ich die ganze Denke nicht, und da werden wohl Probleme
> gelöst, die durch ein Übermaß an Sprachmitteln erste entstehen, und
> durch noch kompliziertere — Verzeihung, genialere — Features umgangen
> werden müssen.

https://gitlab.com/higaski/TypeTree

Ich hab hier mal ein kleines Beispiel runtergetippt wie man Typen-Info 
nutzen kann um folgenden (sinnlosen) Binärbaum abzubilden.

       +---+
       |   |
       | a |
       |   |
  +----+---+----+
+-v-+         +-v-+
|   |         |   |
| b |         | c |
|   |         |   |
+---+      +--+---+--+
           |         |
         +-v-+     +-v-+
         |   |     |   |
         | d |     | e |
         |   |     |   |
         +---+--+  +---+
                |
              +-v-+
              |   |
              | f |
              |   |
              +---+

Statt Nodes wia Pointern zu verbinden nutze ich std::pair, um jeweils 
eine Node und deren Sub-Typen miteinaner in Verbindung zu bringen.

pair(Node{"a"},pair(
                    pair(Node{"b"}, pair(
                                         empty(),
                                         empty()
                                        )
                         ),
                    pair(Node{"c"}, pair(
                                         pair(Node{"d"}, pair(
                                                              empty(),
                                                              pair(Node{"f"}, pair(
                                                                                   empty(),
                                                                                   empty()
                                                                                  )
                                                                  )
                                                             )
                                              ),
                                         pair(Node{"e"}, pair(
                                                              empty(),
                                                              empty()
                                                             )
                                             )
                                        )
                         )
                  )
    )

Mangels Kreativität blieb ich dann auch bei dem Beispiel einer 
Menü-Struktur. Es wird ein Kommandozeilen-Tool gebaut, dass via Numpad 
den Baum wie ein Menü durchsteppen lässt. Die faszinierende 
Hauptschleife benutzt getchar um auf User-Eingaben zu warten... es gilt:

4 - links
6 - rechts
8 - zurück
0 - beenden

Ich vermute, dass die klassische C-Variante für jenes Beispiel schneller 
und kleiner ist. Bei anderen Datenstrukturen, die sowohl komplexer als 
auch größer sind, dürfte sich das Blatt recht schnell in Richtung 
Typen-Baum drehen.

Was man abgesehn davon beim Typen-Baum gewinnt ist:

a) Compile-Time Sicherheit
Ich kann jederzeit zur Compile-Zeit prüfen, ob mein Typ tatsächlich ein 
Binärbaum ist.

b) Verbindung von Konstaten und Variablen
Die Möglichkeiten Konstanten und Variablen via Type-Info zu Verbinden. 
Ich könnte von dem Typen-Baum eine konstante Version und eine variable 
Version erzeugen, wobei die konstante Version Menü-Infos (z.B. Strings) 
enthält und die variable Version die notwendigen Daten (z.B. Messwerte). 
Die beiden Bäume spiegeln sich sozusagen. Durch die vorhandene Type-Info 
kann ich aber jederzeit vom konstanten auf den variablen Typen und 
umgekehrt zugreifen...

Beides Features, die man mit C schlichtweg nicht realisieren kann.

[Wilhelm M. (wimalopaan)]

Ich habe es statt mit std::pair<> mit std::tuple<> gemacht, um n-äre 
Bäume darstellen zu können. Anschließend wird der Baum in eine 
indizierte Knotenliste transformiert (natürlich auch als std::tuple<>). 
Die Indizes der Kindknoten werden dabei als std::integral_constant<> als 
Typ-Parameter dargestellt. Also die gesamte Struktur des Baumes bzw. 
eben der Liste steckt im Typ. Nur die non-const Datenelemente sind im 
Ram: keine Indizes, keine Zeiger. Also natürlich auf jeden Fall weniger 
Ram-Verbrauch und das war das Ziel. Natürlich steckt nun die Struktur im 
generierten Maschinencode selbst.
In einem Test bewegte sich die reine Codegröße im Vergleich zu 
verschiedenen klassischen OOP Varianten bei etwa 60% - 120% Flash und 
immer dem Minimum an Ram (also nur die tatsächlich non-const 
Datenelemente), die OOP Varianten benötigten eben sehr viel mehr Ram. 
Das ganze war bisher nur ein proof-of-concept zu bestimmten 
Metafunktionen und zur Traversion von std::tuple<> zur Laufzeit als 
generischer Visitor. Übrigens auch ganz spannend wozu man generische 
Lambdas gebrauchen kann ...

[Johann L. (gjlayde)]

Vincent H. schrieb:
> Ich hab hier mal ein kleines Beispiel runtergetippt wie man Typen-Info
> nutzen kann um folgenden (sinnlosen) Binärbaum abzubilden.
> [...]
> Statt Nodes wia Pointern zu verbinden nutze ich std::pair, um jeweils
> eine Node und deren Sub-Typen miteinaner in Verbindung zu bringen.
>
> pair(Node{"a"},pair(
> [...]

Ok, wie man einen Baum austexten kann ist mir prinzipiell klar.

Ich hätt's halt schön gefunden, wenn der eigentliche Code erklärt worden 
wäre.  So dass man ihn auch verstehen kann, wenn man ihn nicht vorher 
schon verstanden hat. (Zu wiederholen, wo das alles verwendbar ist und 
wie toll und nützlich, trägt zum Verständnis nun mal nix bei.  So wie 
ein asm-Klotz, den man ohne weiteres nicht versteht, wo aber die 
Nützlichkeit als solche nichts zum Verständnis beiträgt).

[MitLeserin (Gast)]

Johann L. schreibt

>Ich hätt's halt schön gefunden, wenn der eigentliche Code erklärt worden wäre. 
So dass man ihn auch verstehen kann, wenn man ihn nicht vorher schon verstanden 
hat.

Ich teile diese Aussage zu 100%.

Es wäre ganz einfach wirklich konstruktive Beiträge zu erstellen. Jede 
These mit einem kleinen kompilierbaren Stück Code konkret vorstellen.

Damit wäre ein Beitrag von einer abstrakten in eine nachvollziehbare 
Ebene verschoben...

[Wilhelm M. (wimalopaan)]

MitLeserin schrieb:
> Johann L. schreibt
>
>>Ich hätt's halt schön gefunden, wenn der eigentliche Code erklärt worden wäre.
> So dass man ihn auch verstehen kann, wenn man ihn nicht vorher schon verstanden
> hat.
>
> Ich teile diese Aussage zu 100%.
>
> Es wäre ganz einfach wirklich konstruktive Beiträge zu erstellen. Jede
> These mit einem kleinen kompilierbaren Stück Code konkret vorstellen.
>
> Damit wäre ein Beitrag von einer abstrakten in eine nachvollziehbare
> Ebene verschoben...

Habt Ihr es überlesen?

https://gitlab.com/higaski/TypeTree

[Vincent H. (vinci)]

Johann L. schrieb:
> Ich hätt's halt schön gefunden, wenn der eigentliche Code erklärt worden
> wäre.  So dass man ihn auch verstehen kann, wenn man ihn nicht vorher
> schon verstanden hat. (Zu wiederholen, wo das alles verwendbar ist und
> wie toll und nützlich, trägt zum Verständnis nun mal nix bei.  So wie
> ein asm-Klotz, den man ohne weiteres nicht versteht, wo aber die
> Nützlichkeit als solche nichts zum Verständnis beiträgt).

Die Hauptfunktionalität steckt in der Funktion "visit", aber dazu komm 
ich später. Wichtig ist, dass man sich am Anfang einmal klar macht, wie 
die Baum-Struktur traversiert werden könnte.

In der std gibt es für den (compile-time) Zugriff in eine Typenliste die 
Funktion "std::get". Damit geht etwa folgendes:

auto t = std::make_tuple(10, 42, 100);
printf("%d", std::get<1>(t));  // print 42

Der Baum selbst ist nichts anderes als eine verschachtelte Typenliste. 
Es wäre also möglich folgendermaßen auf Node c zuzugreifen:

get<1, 1, 0>(tree);  // c

Der implizierte Left- und Right-Pointer von Node c wäre dann:

get<1, 1, 1, 0>(tree) << "\n";  // c left
get<1, 1, 1, 1>(tree) << "\n";  // c right

Disclaimer: Die std bietet keine get Version für mehrere Template 
Parameter, die lässt sich aber natürlich selbst schreiben.


Soweit so gut. Schreibt man sich diese Indizes für ein paar Nodes und 
Sub-Nodes auf, dann erkennt man recht schnell ein Muster. Um etwa nach 
links zu gehen, muss der aktuelle Index von 0 auf 1 geändert werden und 
anschließend 2x 0er angehängt werden. Das passiert (unschön) in der 
Funktion vector_left, bzw. vector_right.

void vector_left(std::vector<value_type>& v) {
  v.back() = 1;
  v.push_back(0);
  v.push_back(0);
}

Um retour zu gehen macht man dann genau das Gegenteil davon... siehe 
vector_previous. Die Abfrage nach der Größe verhindert nur, dass ich den 
Vektor nicht aus versehen ins negative schrumpfe... (Vektor lässt sich 
übrigens natürlich nach belieben Substituieren, ich habs nur gewählt, 
damit ich für das Beispiel die std nutzen kann)

bool vector_previos(std::vector<value_type>& v) {
  if (v.size() >= 3) {
    v.pop_back();
    v.pop_back();
    v.back() = 0;
    return true;
  } else
    return false;
}

Was nun nur noch übrig bleibt ist die vom User eingegebenen Indizes zu 
nutzen um den Baum zu traversieren. Das geschieht via "visit". Visit 
vergleicht die User-Eingaben rekursiv mit kleiner werdenden Konstanten 
und nutzt diese dann, um eine ebene Tiefer in die Struktur zu steigen... 
solang, solang noch Indizes vorhanden sind. Auf die gefundene Node wird 
dann eine Funktion angewandt, in dem Fall einfach nur ein simples 
Lambda, mit dem ich mir den String der Node zurück geben lasse. Auch 
wenn visit auf den ersten Blick recht böse aussieht, so begnügt es sich 
pro "Such"-Rekursion (auf einem Cortex M4 etwa) mit nur 4x Befehlen.

Der gsl::span Parameter der visit Funktion ist lediglich ein View auf 
einen Container, vergleichbar mit std::string_view aus dem aktuellen 
Standard für Strings. Das macht die visit Funktion unabhängig vom 
gewählten Container-Typen.


Wilhelm M. schrieb:
> Ich habe es statt mit std::pair<> mit std::tuple<> gemacht, um n-äre
> Bäume darstellen zu können.

Ja natürlich könnte man tuple nutzen. Ich hab jetzt mal absichtlich pair 
genommen, damit ein Großteil an Herumspielen am Baum, dass 
"Strukturfehler" erzeugen würde, schon nicht durch den Compiler schlüft.


Wilhelm M. schrieb:
> Anschließend wird der Baum in eine  indizierte Knotenliste transformiert > 
(natürlich auch als std::tuple<>).
> Die Indizes der Kindknoten werden dabei als std::integral_constant<> als
> Typ-Parameter dargestellt. Also die gesamte Struktur des Baumes bzw.
> eben der Liste steckt im Typ.

Da bin ich ausgestiegen. Kannst du das vielleicht in ein paar Zeilen 
näher erläutern? Das heißt du nutzt die im Typ mitgespeicherten Indizes 
dann direkt zum traversieren? Ich versteh nicht so ganz wie man dann zur 
Laufzeit auf einen gesuchten Konten zugreifen könnte. Um einen Vergleich 
von Lautzeit-Werten mit den Indizes kommt man ja trotzdem nicht herum 
oder?

Wenn etwa der User sagen würde: "Bitte Node an 3 - 1 - 2 - 0 ... "?

[Wilhelm M. (wimalopaan)]

Beim einer normalen OO Repräsentation eines Baumes mit Zeigern kann 
man den aktiven Knoten etwa eben durch einen Zeiger auf diesen Knoten 
darstellen (falls man so etwas braucht wie etwa in einem Menu-Baum 
odgl.). Oder man kann es eben wie bei Dir durch einen Pfad machen. Oder 
man könnte es auch durch eine Knoten-ID machen. Wenn man nun ganz 
platzsparend mit dem Ram umgehen will, reicht für Bäume mit 
Knotenanzahlen unter 256 auch einfach ein uint8_t als ID.

Den Baum kann man z.B. pre-order in eine lineare Struktur (Liste) 
umformen: dabei erhält jeder Knoten als ID seinen Index.

Der Baum

         Node<A>
        /       \
     Node<B>    Node<C>
               /       \
            Node<D>    Node<E>

ist dann als Liste:

[ B D E IndexNode<C,1,2> IndexNode<A,0,3>]

Dabei werden die terminalen Knotentypen direkt in die Liste (besser: 
heterogener linearer Container) (std::tuple<>) übernommen und aus den 
nicht-terminalen Knotentypen werden Typen gemacht, die als non-const 
Daten den Knotentyp haben und die Indizes der Kinder als 
Non-Type-Template-Parameter.
Damit steckt die Struktur in den Typen und man braucht zur 
Identifizierung eines Knotens (des aktiven) nur einen Index (z.B. ein 
uint8_t).

Im Baum sind die Knoten:

template<typename T, typename... C>
struct Node {
    typedef T node_type;
    constexpr Node(T&& n, C&&... c) : mData{std::forward<T>(n)}, mChildren(std::forward<C>(c)...) {}
    inline static constexpr auto size = sizeof...(C);
    T mData;
    std::tuple<C...> mChildren;
};

In der Liste werden aus den nicht-terminalen:

template<typename T, auto... II>
struct IndexNode {
    typedef T type;
    typedef IndexNode index_type;
    T mData;
};

Es bleiben also nur die reinen Datenelemente (hier jeweils vom 
Typ-Parameter T) übrig.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> MitLeserin schrieb:
>> Johann L. schreibt
>>
>>>Ich hätt's halt schön gefunden, wenn der eigentliche Code erklärt worden wäre.
>>> So dass man ihn auch verstehen kann, wenn man ihn nicht vorher schon 
verstanden
>>> hat.
>
> Habt Ihr es überlesen?
>
> https://gitlab.com/higaski/TypeTree

Ich bezog mich auf den HIER geposteten Code. Und:

> So dass man ihn auch verstehen kann, wenn man ihn nicht vorher schon
> verstanden hat.

Was für den von dir verlinkten Code zutrifft.

Beispiel 1:

constexpr auto transform2(const auto& callable)
{
    constexpr auto v = callable();
    return std::integral_constant<decltype(v), v>{};
}

Der Code in "transform1" hat das Problem, dass der Parameter nicht zur 
Compilezeit bekannt ist.  Bei "transform2" gilt das immer noch: callable 
ist nicht zur Compilezeit bekannt.  Wenn also eine Funktion 
/ Callable / Funktor nicht (zur Compilezeit) bekannt ist, wie kann seine 
Auswertung (zur Compilezeit) bekannt sein?

Hängt das nur von Compileroptimierungen bzw. dem Optimierungsgrad ab, 
ist es ein Feature der Sprache (welches), etc.

Und: Wenn ich alle Werte einer Funktion (zur Compilezeit) kenne, dann 
kenn ich doch auch die Funktion selbst (zur Compilezeit)?

Beispiel 2:

template<typename C, typename T>
concept bool Callable()
{
    return requires (C l)
    {
        { l() } -> T;
    };
}

Was wird hier festgelegt? "template", "typename", "Callable", "concept", 
"bool", "requires" und "return" sind sämtlich Schlüsselworte in C++20 
bzw. von Standard festgelegt; das einzige, was zu definieren übrig 
bleibt, sind "C", "l", und "T" und ein paar Operatoren.

Zudem passt die Syntax nicht zu der, wie man sie zum Beispiel in 
http://en.cppreference.com/w/cpp/language/constraints findet:

template<typename T>
concept EqualityComparable = requires(T a, T b)
{
    { a == b } -> bool;
};

Hier wird "EqualityComparable" festgelegt, es folgt ein "=", ganz nach 
der Festlegung ein ";" und "EqualityComparable" hat keinen Typ ("bool" 
im Code von oben), die Klammerung ist anders (oben in "{}" gefasst, 
unten nicht), etc etc etc.

Da man als C++ Progger immer einen kompletten C++ Lexer und -Parser in 
seiner Birne rumschleppen muss, bringt der bei mir nur nen Syntax-Error.

Und da helfen hunderte Zeilen verlinkter und minimal-kommentierter Code 
auch nicht, egal ob der übersetzt oder nicht.  Das durch einen Compiler 
zu jagen oder ein unverständlichen Konglomerat zu Deguggen, bringt mir 
zumindest nix. (Debugger gehört ohnehin nicht zu meinen 
"Design-Pattern").

Beispiel 3:

Wie sieht der Code ohne "auto" aus?

Es wird ja ständig betont, dass C++ Typ-sicher sei, was aber durch 
"auto" unterminiert wird.  Auch wenn es weniger bequem ist und mehr 
Tipparbeirt, würde mich auto-freier Code interessieren.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:

> Beispiel 1:
>
>

constexpr auto transform2(const auto& callable)
> {
>     constexpr auto v = callable();
>     return std::integral_constant<decltype(v), v>{};
> }

> Der Code in "transform1" hat das Problem, dass der Parameter nicht zur
> Compilezeit bekannt ist.

Genau: das steht ja auch dort oben im Code als Kommentar.

> Bei "transform2" gilt das immer noch: callable
> ist nicht zur Compilezeit bekannt.  Wenn also eine Funktion
> / Callable / Funktor nicht (zur Compilezeit) bekannt ist, wie kann seine
> Auswertung (zur Compilezeit) bekannt sein?

Das kommt jetzt darauf an, ob das Callable constexpr ist. In meinem 
Beispiel ist es das. Und genau das ist der entscheidende Punkt an der 
ganzen Sache: lambda-expressions liefern in C++ constexpr-Closures

> Hängt das nur von Compileroptimierungen bzw. dem Optimierungsgrad ab,
> ist es ein Feature der Sprache (welches), etc.

Es ist ein feature der Sprache.

> Beispiel 2:
>
>

template<typename C, typename T>
> concept bool Callable()
> {
>     return requires (C l)
>     {
>         { l() } -> T;
>     };
> }

>
>
> Was wird hier festgelegt? "template", "typename", "Callable", "concept",
> "bool", "requires" und "return" sind sämtlich Schlüsselworte in C++20

Richtig, hat der Gcc aber schon seit Version 6.3 und ist die 
Referenzimplementierung für C++20 (ähnlich wie clang schon Modules 
beinhaltet)

> Zudem passt die Syntax nicht zu der, wie man sie zum Beispiel in
> http://en.cppreference.com/w/cpp/language/constraints findet:
>
>

template<typename T>
> concept EqualityComparable = requires(T a, T b)
> {
>     { a == b } -> bool;
> };

Da ist genaues Lesen wichtig: gcc realisiert die Concept-TS, für C++20 
sind syntaktische Änderungen vorgeschlagen worden. Ob die aber so 
umgesetzt werden, ist wohl noch offen.

> Und da helfen hunderte Zeilen verlinkter und minimal-kommentierter Code
> auch nicht, egal ob der übersetzt oder nicht.

Wie schon mal erwähnt, ist es ja auch keine Pflicht, sich damit 
auseinander zu setzen. Und ja: ich höre jetzt schon wieder die Einwände: 
das ist ja noch gar nicht standardisiert, der arme 
Wartungsprogrammierer, etc.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
>
> Beispiel 3:
>
> Wie sieht der Code ohne "auto" aus?
>
> Es wird ja ständig betont, dass C++ Typ-sicher sei, was aber durch
> "auto" unterminiert wird.  Auch wenn es weniger bequem ist und mehr
> Tipparbeirt, würde mich auto-freier Code interessieren.

Großes Mißverständnis: auto ist eine Typ-Inferenz und kein Duck-typing. 
Die Typsicherheit bleibt vollkommen erhalten.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> Johann L. schrieb:
>>
>> Beispiel 3:
>>
>> Wie sieht der Code ohne "auto" aus?
>>
>> Es wird ja ständig betont, dass C++ Typ-sicher sei, was aber durch
>> "auto" unterminiert wird.  Auch wenn es weniger bequem ist und mehr
>> Tipparbeirt, würde mich auto-freier Code interessieren.
>
> Großes Mißverständnis: auto ist eine Typ-Inferenz und kein Duck-typing.
> Die Typsicherheit bleibt vollkommen erhalten.

Ich meinte nicht Duck-Typing, sondern explizit vs. implizit.  Wenn man 
einen Typ explizit austextet, ist man sicher, das es genau das ist, 
was man will.  Anstatt das ein Typ automatisch vom Compiler bestimmt 
wird.  Beim Lesen ist es auch klarer, was man meint.


Wilhelm M. schrieb:
> Johann L. schrieb:
>
>> Beispiel 1:
>>
>>

constexpr auto transform2(const auto& callable)
>> {
>>     constexpr auto v = callable();
>>     return std::integral_constant<decltype(v), v>{};
>> }

>> Der Code in "transform1" hat das Problem, dass der Parameter nicht zur
>> Compilezeit bekannt ist.
>
> Genau: das steht ja auch dort oben im Code als Kommentar.
>
>> Bei "transform2" gilt das immer noch: callable
>> ist nicht zur Compilezeit bekannt.  Wenn also eine Funktion
>>  Callable  Funktor nicht (zur Compilezeit) bekannt ist, wie kann seine
>> Auswertung (zur Compilezeit) bekannt sein?
>
> Das kommt jetzt darauf an, ob das Callable constexpr ist. In meinem
> Beispiel ist es das.

Im Caller (also in main) ja, das gilt auch für "value".  Als Parameter 
des Callee ist es dann aber nicht mehr constexpr?  Jedenfalls kann man 
den Parameter nicht als constexpr deklarieren.

Etwas klarer wird's vielleicht, wenn man versucht, transform2 extern zu 
machen:

error: use of ‘constexpr auto transform2(const auto:2&) [with auto:2 = main()::<lambda()>]’ before deduction of ‘auto’
     constexpr auto result2 = transform2([&]{ return value; });

D.h. transform2 wird als "abstrakter" (?) Code gespeichert, und erst bei 
Verwendung wird der Typ des Parameters ermittelt und der Code von 
transfrom2 — ja was? Instanziiert?

Wie nennt sich dieser Vorgang, und warum ist das nur bei Lambdas 
möglich? Bei nicht-Lanbdas müsste das doch noch viel einfacher sein und 
analog möglich sein?  Erst wenn "transform1" verwendet wird, wird das 
"auto" aufgelöst, und das ist "constexpr value = 42", was dann weiter 
verwendet wird.

Folgender Code

#include <type_traits>

constexpr auto transform3 (const auto val)
{
    constexpr auto v = decltype(val)::value;
    return std::integral_constant<decltype(v), v>::value;
}

int main()
{
    constexpr int value = 42;

    constexpr auto result3 = transform3 (std::integral_constant<int,value>{});
    return result3;
}

übersetzt und erzeugt den erwarteten Code:

main:
  movl  $84, %eax
  ret

Bemerkenswert ist, dass nicht "val" verwendet wird, sondern nur dessen 
Typ; wie bereits angemerkt in 
Beitrag "Re: constexpr Argument-Wrapper"

Oder noch einfacher per

#include <type_traits>

constexpr auto transform4 (const auto val)
{
    return 1 + val;
}

int main()
{
    constexpr int value = 42;

    constexpr auto result4 = transform4 (std::integral_constant<int,value>{});
    return result4;
}

Warum brauch man dann ein Lambda?

Dass "val" hier keine Referenz ist, ist auch Wurscht. Wenn ich's recht 
verstehe, sind constexpr Funktionen non-public und implizit inline, und 
ob ein Integer als Referenz oder Wert übergeben wird spielt mithin keine 
Rolle (und da es um constexpr geht, bleibt nicht viel anderes über als 
Integer).

Oder noch einfacher ohne type_traits:

constexpr auto transform5 (const auto val)
{
    return 1 + val;
}

int main()
{
    constexpr int value = 42;

    constexpr auto result5 = transform5 (value);
    return result5;
}

Es ging darum, eine constexpr in einer constexpr-Funktion zu verwenden, 
weshalb taugt dann taransform 5 nicht? Und transform5 geht auch mit 
"const auto& val" wenn man vom &-Reflex garnicht lassen will.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
> Wilhelm M. schrieb:
>> Johann L. schrieb:
>>>
>>> Beispiel 3:
>>>
>>> Wie sieht der Code ohne "auto" aus?
>>>
>>> Es wird ja ständig betont, dass C++ Typ-sicher sei, was aber durch
>>> "auto" unterminiert wird.  Auch wenn es weniger bequem ist und mehr
>>> Tipparbeirt, würde mich auto-freier Code interessieren.
>>
>> Großes Mißverständnis: auto ist eine Typ-Inferenz und kein Duck-typing.
>> Die Typsicherheit bleibt vollkommen erhalten.
>
> Ich meinte nicht Duck-Typing, sondern explizit vs. implizit.  Wenn man
> einen Typ explizit austextet, ist man sicher, das es genau das ist,
> was man will.  Anstatt das ein Typ automatisch vom Compiler bestimmt
> wird.  Beim Lesen ist es auch klarer, was man meint.

Du hattest aber oben davon gesprochen, dass dann C++ nicht mehr 
typsicher sei. Aber genau das bleibt es dadurch.

>
> Wilhelm M. schrieb:
>> Johann L. schrieb:
>>
>>> Beispiel 1:
>>>
>>>

constexpr auto transform2(const auto& callable)
>>> {
>>>     constexpr auto v = callable();
>>>     return std::integral_constant<decltype(v), v>{};
>>> }

>>> Der Code in "transform1" hat das Problem, dass der Parameter nicht zur
>>> Compilezeit bekannt ist.
>>
>> Genau: das steht ja auch dort oben im Code als Kommentar.
>>
>>> Bei "transform2" gilt das immer noch: callable
>>> ist nicht zur Compilezeit bekannt.  Wenn also eine Funktion
>>>  Callable  Funktor nicht (zur Compilezeit) bekannt ist, wie kann seine
>>> Auswertung (zur Compilezeit) bekannt sein?
>>
>> Das kommt jetzt darauf an, ob das Callable constexpr ist. In meinem
>> Beispiel ist es das.
>
> Im Caller (also in main) ja, das gilt auch für "value".  Als Parameter
> des Callee ist es dann aber nicht mehr constexpr?  Jedenfalls kann man
> den Parameter nicht als constexpr deklarieren.

Es ist ja auch nicht ein Parameter des Callee, sondern ein Capture.


> Etwas klarer wird's vielleicht, wenn man versucht, transform2 extern zu
> machen:

Was meinst Du damit? Ein extern-Instanziierung des template transform2?

>

error: use of ‘constexpr auto transform2(const auto:2&) [with 
> auto:2 = main()::<lambda()>]’ before deduction of ‘auto’
>      constexpr auto result2 = transform2([&]{ return value; });

> D.h. transform2 wird als "abstrakter" (?) Code gespeichert, und erst bei
> Verwendung wird der Typ des Parameters ermittelt und der Code von
> transfrom2 — ja was? Instanziiert?
>
> Wie nennt sich dieser Vorgang,

Welcher?

> Folgender Code
>

#include <type_traits>
> 
> constexpr auto transform3 (const auto val)
> {
>     constexpr auto v = decltype(val)::value;
>     return std::integral_constant<decltype(v), v>::value;
> }
> 
> int main()
> {
>     constexpr int value = 42;
> 
>     constexpr auto result3 = transform3 
> (std::integral_constant<int,value>{});
>     return result3;
> }

Da wir ja schon integral_constant in main instanziiert. Darum geht es 
aber gar nicht.

> Warum brauch man dann ein Lambda?

Es darum, dass ein Funktionsparameter in einer constexpr-Funktion kein 
core-constant expression sein kann, die zur Parametrierung eines 
Templates verwendet wird.

> Es ging darum, eine constexpr in einer constexpr-Funktion zu verwenden,
> weshalb taugt dann taransform 5 nicht?

s.o.

> Und transform5 geht auch mit
> "const auto& val" wenn man vom &-Reflex garnicht lassen will.

Das ist weniger ein Reflex als sinnvoll: man könnte ja auch mal größere 
Objekte verwenden. In generischem Code kann das vorkommen.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> Da wir ja schon integral_constant in main instanziiert. Darum geht es
> aber gar nicht.

Es ging darum, ein constexpr in einer constexpr-Funktion zu nutzen, oder 
nicht?  So wie in transform5 kommt man auch komplett ohne Templates aus.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
> Wilhelm M. schrieb:
>> Da wir ja schon integral_constant in main instanziiert. Darum geht es
>> aber gar nicht.
>
> Es ging darum, ein constexpr in einer constexpr-Funktion zu nutzen, oder
> nicht?  So wie in transform5 kommt man auch komplett ohne Templates aus.

Es ging darum, das in transform1 gezeigte zu ermöglichen.

transform5 macht etwas ganz anderes: das ist einfach eine Funktion, die 
in einem constexpr-Kontext ausgewertet werden kann. Dazu braucht es auch 
das sinnlose const in der Parameterliste nicht.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> Es darum, dass ein Funktionsparameter in einer constexpr-Funktion kein
> core-constant expression sein kann, die zur Parametrierung eines
> Templates verwendet wird.

Ah. Es geht also darum, den Parameter einer constexpr-Funktion als 
Template-Paramater zu verwenden?

#include <type_traits>

template<unsigned N>
struct Bitsize
{
    enum { value = 1 + Bitsize<N/2>::value };
};

template<>
struct Bitsize<0>
{
    enum { value = 0 };
};

constexpr auto trafo1 (const auto val) // oder const auto&
{
    return Bitsize<val>::value;
}

constexpr auto trafo2 (const auto val)
{
    return Bitsize<decltype(val)::value>::value;
}

int main()
{
    constexpr int val0 = 123456789;

    constexpr auto val1
        = trafo1 (std::integral_constant<int,val0>{});

    constexpr auto val2
        = trafo2 (std::integral_constant<int,val1>{});

    constexpr auto result
        = trafo1 (std::integral_constant<int,val2>{});

    return result;
}

Die Quintessenz ist jetzt, dass in main std::integral_constant "böse" 
ist und ein Lambde "nicht-böse", aber warum?

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
> Wilhelm M. schrieb:
>> Es darum, dass ein Funktionsparameter in einer constexpr-Funktion kein
>> core-constant expression sein kann, die zur Parametrierung eines
>> Templates verwendet wird.
>
> Ah. Es geht also darum, den Parameter einer constexpr-Funktion als
> Template-Paramater zu verwenden?

So stand es in transform1 drin, ja.

> Die Quintessenz ist jetzt, dass in main std::integral_constant "böse"
> ist und ein Lambde "nicht-böse", aber warum?

Nehmen wir mal an, Du wolltest nicht nur integrale Werte auf diese Weise 
einer Funktion übergeben, sondern etwa ein std::array und aus den 
Array-Werten sollen Parametrierungen für andere Typen berechnet werden.

Etwa:

template<typename T>
constexpr auto transform3(T v) {
    return std::integral_constant<typename T::value_type, v[0] + v[v.size - 1]>{};
}

constexpr auto transform4(const auto& callable) {
    constexpr auto v = callable();
    typedef decltype(v) T;
    return std::integral_constant<typename T::value_type, v[0] + v[v.size - 1]>{};
}


constexpr auto calculateSomeMagic(auto v) {
    std::array<uint8_t, 10> array;
    for(auto& e : array) {
        e = v;
    }
    return array;
}

namespace  {
    constexpr auto a = calculateSomeMagic(42);
    
//    auto b = transform3(a); // NOK
    auto b = transform4([&]{return a;});
}

Wenn diese Berechnung nun nicht mehr trivial ist, wird man sie gerne in 
Funktionen teilen. Und dann hat man das Problem irgendwann.

Du hast das Problem ausgeklammert, indem Du Deine Berechnung 
"hart-codiert" hast in main().

[Vincent H. (vinci)]

Sry für den Necro, aber mir ist gerade aufgefallen dass GCC (7.3.0) 
schon jetzt nicht vollkommen Standard-Konform sein dürfte was das 
"Propagieren" von Constexpr-Ness angeht.

Folgendes Schnipsel etwa compiliert mim GCC fehlerfrei durch

template<typename T>
constexpr auto to_array(T&& a) {
  return detail::to_array(std::forward<T>(a),
                          range_c<size_t, 1_c, length(a)>);
}

Interessant ist vor allem der "length(a)" Teil, der eine constexpr 
Funktion aufruft aber den Parameter "a" übergibt.


Wenn ich den selben Teil mit Clang compilieren will, so muss ich direkt 
auf den Template Parameter T zurückgreifen (length<T>()).

[Vincent H. (vinci)]

Necro :)

Clang schluckt den "constexpr argument wrapper" auch in 7.0 nicht.

Copy & paste von Willhelms Beispiel in Compiler Explorer:
https://godbolt.org/z/Tpvt5Z

/edit
GCC <-> Clang nebeneinander
https://godbolt.org/z/xHzheD

[Wilhelm M. (wimalopaan)]

Wenn Du das Funktionsobjekt nicht per universal-ref sondern per value 
nimmst, geht es auch mit dem clang ...

[Vincent H. (vinci)]

Tatsächlich!
Danke ;)