johannes-asal.de

In den bisherigen drei Teilen dieser Serie haben wir ein Format fuer Konfigurationsdateien erarbeitet, eine Spirit-Grammatik dafuer geschrieben und zuletzt eine Objekthierarchie fuer die Speicherung der Daten implementiert. Der wichtigste Teil fehlt jedoch noch: Die Erzeugung des Objektbaums waehrend des Parsens. Wir werden zu diesem Zweck direkt semantische Aktionen mit den einzelnen Regeln der Grammatik assoziieren.

Warum benutzen wir nicht einfach den von Spirit automatisch generierten Baum? Wir koennten den Parser bereits im jetzigen Zustand (siehe Ende des Teils 2b) benutzen und den von Spirit generierten Objektbaum im aeusseren Attribut verwenden, um nachtraeglich den von uns gewuenschten Baum aus element Objekten aufzubauen. Betrachten wir jedoch einmal beispielsweise den Typ des automatisch generierten Attributs der Regel array, die wie folgt definiert war:

arrayDefinition
  =  lit('[')
  >> -( double_ % ','
      | long_ % ','
      | bool_ % ','
      | string % ','
      )
  >  ']'
  ;

Diese Regel generiert ein Attribut vom Typ

optional<
  variant<
    vector<double>,
    vector<long>,
    vector<bool>,
    vector<string>
  >
>

Die array Regel wird in listDefinition und variableAssignment verwendet, die ebenfalls ein variant generieren, welches wiederum das oben gezeigte variant der arrayDefinition in seiner Typenliste enthaelt usw. Wir wuerden fuer die aeussere Regel also ein Attribut erhalten, dessen Typdefinition so lang und verschachtelt ist, dass niemand ernsthaft darueber nachdenken wuerde, damit ueberhaupt eine Auswertung zu versuchen. Wir muessen also eine Loesung finden, uns von der statischen Typisierung zu loesen. Unsere element Klassenhierarchie ist dazu bestens geeignet und soll daher anstelle des automatisch generierten Baums verwendet werden.

Spirit ist eine DSEL (Domain Specific Embedded Language), die auf dem Sprachraum von C++ definiert ist. Dies bringt einige Nachteile mit sich, die insbesondere bei der Implementierung der semantischen Aktionen zum Tragen kommen. Da die Grammatik mitsamt der assoziierten semantischen Aktionen vom Compiler in ein Objekt uebersetzt wird, koennen wir fuer diese nicht einfach gewoehnlichen C++ Code benutzen, sondern muessen diesen wiederum in Objekte (Funktoren) kapseln, die dann zur Laufzeit ausgewertet werden koennen. Gluecklicherweise bietet boost::phoenix bereits eine Reihe von Funktoren an, die die meisten grundlegenden Operationen abdeckt (new, delete, Konstruktorenaufrufe, …).

Beginnen wir mit der atom Regel. Wir fuegen dieser eine semantische Aktion hinzu, die mit dem gesamten Ausdruck assoziiert sein soll (dazu klammern wir die Unterregeln einfach ein):

atom
  =  ( double_
     | long_
     | bool_
     | string
     ) [ _val = new_<cfg::atom>(_1) ]
  ;

Semantische Aktionen werden in eckige Klammern eingeschlossen und der Teilregel angehaengt, fuer die das Attribut verarbeitet werden soll. Der Typ des generierten Attributs fuer den gesamten Ausdruck

( double_ | long_ | bool_ | string )

ist

variant<double, long, bool, string>

Wir erinnern uns, dass wir in unserer Atom Klasse einen Konstruktor mit genau diesem Typ als Parameter definiert hatten. Normalerweise koennten wir dann ein Objekt vom Typ atom erzeugen, indem wir

new atom(generated_attribute)

schreiben. Fuer Spirit muessen wir dies allerdings in einen phoenix Ausdruck uebersetzen (new_ ist der phoenix Funktor fuer new).

Auf das generierte Attribut koennen wir ueber den Platzhalter _1 zugreifen. Den Zeiger auf das neu erzeugte atom Objekt weisen wir dem Platzhalter _val zu, der diesen als das generierte Attribut der gesamten Regel festlegt. Fassen wir noch einmal zusammen: Ohne die semantische Aktion wuerde die atom Regel ein Attribut vom Typ variant zurueckliefern, jedoch moechten wir stattdessen ein atom Objekt aus unserer Objekthierarchie zurueckgeben, und setzen dieses mittels Zuweisung an _val als das neue generierte Attribut.

Um das Attribut der Regel string (und literal) muessen wir uns nicht kuemmern, da Spirit automatisch ein std::string Attribut erzeugt, wenn wir std::string als Rueckgabewert der Regel festlegen (die Typen sind kompatibel, d.h. es existiert bereits eine Transformationsvorschrift, die das Attribut der Regel in einen String umwandeln kann – dies ist fuer benutzerdefinierte Typen natuerlich leider nie der Fall).

Betrachten wir als naechstes die listDefinition. Fuer diese muessen wir mehrere Aktionen verwenden. Zu Beginn der Regel muss ein neues Objekt vom Typ list (aus unserer Objekthierarchie) angelegt werden, das wir in _val zwischenspeichern. Fuer jede nun folgende groupDefinition, listDefinition, arrayDefinition oder atom muss das zugehoerige Attribut an das list Objekt angehaengt werden. Wir erinnern uns, dass wir dem list Objekt eine Funktion append(element*) gegeben hatten. Diese Funktion koennen wir allerdings in der semantischen Aktion nicht ohne weiteres verwenden, sondern muessen sie zunaechst in einen Struct kapseln:

struct append_impl
{
  template <typename C, typename Arg>
  struct result { typedef void type; };
 
  template <typename C, typename Arg>
  void operator()(C* c, const Arg& data) const
  { c->append(data); }
};
 
phoenix::function<append_impl> const append = append_impl();

Damit machen wir das struct append_impl zu einem Funktor, der unter dem Namen append zur Verfuegung steht. Die gesamte arrayDefinition Regel koennen wir dann folgendermassen schreiben:

arrayDefinition
  =  lit('[')     [_val = new_<cfg::list>()]
  >> -( double_   [append(_val, new_<cfg::atom>(_1))] % ','
      | long_     [append(_val, new_<cfg::atom>(_1))] % ','
      | bool_     [append(_val, new_<cfg::atom>(_1))] % ','
      | string    [append(_val, new_<cfg::atom>(_1))] % ','
      )
  >  ']'
  ;

Diese Folge von Aktionen erzeugt also zunaechst ein neues Objekt vom Typ list und ruft dann fuer jedes Auftreten von double, long, bool oder string Werten den append Funktor auf, der dem list Objekt (in _val) ein neues atom anfuegt, dass in-place erzeugt wird. Wer sich nun fragt, warum wir das append vier Mal geschrieben haben, statt es einfach einmal hinter dem geklammerten Ausdruck zu verwenden, der moege bitte den Listenoperator am Ende der Zeilen beachten. Dieser fuehrt, zusammen mit dem “-” Operator fuer einen optionalen Ausdruck zu einem generierten Attribut mit komplexem Typ (optional< variant<...> >, siehe Beginn des Artikels), fuer das wir sicherlich keine append Funktion haetten schreiben wollen. Dadurch, dass wir die semantischen Aktionen direkt mit den POD Typen assoziieren, koennen wir einfach den Konstruktor von atom benutzen, um ein zugehoeriges Objekt zu erzeugen und fuegen dieses direkt in die Liste ein.

Die Regel listDefinition wird aehnlich implementiert, jedoch muessen wir in diesem Fall kein neues atom erzeugen, sondern koennen das generierte Attribut der Unterregel an den append Aufruf durchschleifen. Die genaue Implementierung ist dem vollstaendigen Sourcecode zu entnehmen.

Kommen wir zur groupDefinition: Hier muessen wir natuerlich zunaechst ein group Objekt erzeugen (wozu wir die lit Regel missbrauchen), und anschliessend saemtliche enthaltenen variableAssignments einfuegen. Hierbei habe ich mich fuer eine etwas andere Loesung entschieden, die ein vererbtes Attribut benutzt. Das bedeutet, dass eine Referenz auf eine lokale Variable an eine Subregel uebergeben wird, die das vererbte Attribut verwenden und ggf. auch modifizieren kann:

groupDefinition
  =  lit('{') [_val = new_<cfg::group>()]
  >> *( variableAssignment(_val) )
  >  '}'
  ;

Das Einfuegen der variableAssignments geschieht also nicht in der Regel groupDefinition, sondern in variableAssignment selbst. Die Regel file kann analog implementiert werden, allerdings haben wir hier kein lit zur Verfuegung, an dass wir die Erzeugung des group Objekts anheften koennen und muessen deshalb eine Dummyregel (eps) verwenden, die keinerlei Auswirkung auf die Grammatik hat (siehe Sourcecode).

Die letzte Regel, die wir genauer analysieren wollen, ist variableAssignment. Diese bekommt das bereits erwaehnte vererbte Attribut uebergeben (dessen Platzhalter _r1 heisst), und sieht so aus:

variableAssignment
  =  literal            [_a = _1]
  >> '='
  >> ( groupDefinition  [insert(_r1, _a, _1)]
     | listDefinition   [insert(_r1, _a, _1)]
     | arrayDefinition  [insert(_r1, _a, _1)]
     | atom             [insert(_r1, _a, _1)]
     )
  >  ';'
  ;

Der Funktor insert wird dabei aehnlich wie append implementiert. Um den Namen der Variablen zwischenzuspeichern, benutzen wir eine lokale Variable vom Typ string, deren Platzhalter _a ist (weitere lokale Variablen wuerden _b, _c, usw. heissen). Der Typ von _a muss in der Deklaration der Regel angegeben werden (siehe Sourcecode).

Damit haben wir unseren Parser komplettiert und koennen nun noch eine Klasse cfg_file schreiben, die das Oeffnen der Datei und die Verwendung des Parsers kapselt. Der vollstaendige Code inklusive einem kleinen Testprogramm kann hier heruntergeladen werden:

cfg_file library v1.0 (cfg_file_1_0.tar.gz)

Ich hoffe Ihnen hat dieses kleine Tutorial gefallen. Fuer weitere Fragen und Kritik oder Anregungen stehe ich gerne zur Verfuegung.

Als letzten Schritt zur Vervollstaendigung unserer Klassenhierarchie wollen wir nun die Klasse element implementieren. Sie soll die folgenden Use Cases abdecken:

• Interpretation eines element Objekts als group, list oder atom
• Zugriff auf die Child Elemente ueber Key (Gruppe) oder Index (Array und Liste)
• Konvertierung eines Leaf Elements in einen der unterstuetzten Typen
• Lookup eines Leaf Elements ueber Pfadangabe und optionalen Defaultwert

Der erste Punkt ist leicht zu realisieren. Wir schreiben drei Funktionen

const group& as_group() const { return dynamic_cast<const group&>(*this); }
const list& as_list() const { return dynamic_cast<const list&>(*this); }
const atom& as_atom() const { return dynamic_cast<const atom&>(*this); }

Der dynamic_cast mit einer Objektreferenz sorgt dafuer, dass automatisch eine Exception geworfen wird, wenn das Objekt nicht vom gewuenschten Typ ist. Dies sollte vom Benutzer abgefangen werden.

Auch der Zugriff auf einzelne Childelemente per Key oder Index stellt kein grosses Problem dar. Wir definieren die Indexoperatoren

const element& operator[](const std::string& key) const
{
  return this->as_group().get(key);
}
 
const element& operator[](size_t index) const
{
  return this->as_list().get(key);
}

Dabei setzen wir voraus, dass der Benutzer weiss, um welchen Typ es sich beim jeweiligen Element handelt und interpretieren es dementsprechend entweder als Gruppe oder Liste. Wird ein Operator auf einem ungeeigneten Datentyp aufgerufen, so werfen die as_group() bzw. as_list() Funktionen entsprechende Exceptions.

Falls es sich bei einem element Objekt um ein Leaf Element handelt, so muessen wir es in einen numerischen Typ oder String umwandeln koennen. Da wir bereits eine entsprechende Funktion in der atom Klasse definiert haben, koennen wir einfach durchschleifen:

template <typename T>
const T as() const
{
  return this->as_atom().as<T>();
}

Bleibt nur noch der Use Case des Wertelookups ueber eine Pfadangabe. Nehmen wir an, unsere Konfigurationsdatei sieht folgendermassen aus:

app = {
  windows = (
    {
      title = "Fenster 1";
      width = 400;
      height = 300;
    },
    {
      title = "Fenster 2";
      width = 600;
      heigh = 450;
    }
  );
};

Der Parser liefert uns ein Root Element, das wir r nennen wollen. Dann soll beispielsweise der Zugriff auf den height Wert des zweiten window Elements moeglich sein ueber

long height = r.lookup<long>("app.windows[1].height", 800);

wobei 800 der Defaultwert ist, wenn die Option nicht gefunden wurde. Weiterhin wollen wir die folgende Syntax erlauben:

long height = r["app.windows[1].height"].as<long>();

Dazu muessen wir spaeter den bereits oben definierten operator[] geeignet anpassen. Implementieren wir aber zunaechst die lookup() Funktion:

typedef std::deque<boost::variant<std::string, unsigned int> > token_list;
 
template <typename T>
const T lookup(const std::string& path) const
{
  token_list tokens = util::split(path);
  return recursive_lookup(*this, tokens).as<T>();
}
 
template <typename T>
const element& recursive_lookup(const element& e, token_list tokens) const
{
  if(tokens.empty())
    return e;
 
  boost::variant<std::string, unsigned int> t = tokens.front();
  tokens.pop_front();
 
  const element& next(boost::apply_visitor(visitor(e), t));
  return recursive_lookup(next, tokens);
}

Wir splitten hier zunaechst den Pfadstring in eine Liste von Tokens, die den einzelnen Zugriffsbezeichnern entspricht (in unserem Beispiel also ["app", "windows", 1, "height"]). Anschliessend rufen wir die Funktion recursive_lookup() mit dem aktuellen Element als Ausgangspunkt auf, die rekursiv durch den Baum traversiert und das letzte Element zurueckliefert, das schliesslich als atom interpretiert und in den gewuenschten Typ konvertiert wird. Die Implementierung der Funktion split sowie der Fall mit Defaultwert ist dem vollstaendigen Quellcode zu entnehmen.

Passen wir abschliessend noch den operator[] an, um den gleichen Lookup Mechanismus auch in der Indexschreibweise zu ermoeglichen:

const element& operator[](const std::string& key) const
{
  if(key.find_first_of('.') != std::string::npos)
  {
    token_list tokens = util::split(key);
    return recursive_lookup(*this, tokens);
  }
  else
    return this->as_group().get(key);
}

Damit haben wir nun alle folgenden (aequivalenten) Abfragemoeglichkeiten abgedeckt:

std::string title = r["app.windows[0].title"].as<std::string>();
std::string title = r["app"]["windows"][0]["title"].as<std::string>();
std::string title = r.lookup<std::string>("app.windows[0].title");

Mit Hilfe der im letzten Teil definierten Iteratoren koennen wir nun zum Beispiel auch ueber alle windows Elemente loopen und deren Eigenschaften ausgeben:

const cfg::list& windows = r["app.windows"].as_list();
cfg::list::const_iterator it1 = windows.begin();
for(; it1 != windows.end(); ++it1)
{
  const cfg::group& properties = it1->as_group();
  cfg::group::const_iterator it2 = properties.begin();
  for(; it2 != properties.end(); ++it2)
  {
    std::cout << it2->first << ": "
      << it2->second->as<std::string>() << std::endl;
  }
}

Die somit definierte Klassenstruktur ermoeglicht einen einfachen und effizienten Zugriff auf die Konfigurationsdaten, ist aber gleichzeitig noch ausreichend performant, um eine schnelle Erzeugung der Baumstruktur vom Parser aus zu gewaehrleisten. Die vollstaendige Implementierung kann hier heruntergeladen werden.

Im naechsten und letzten Teil der Serie vervollstaendigen wir endlich unsere kleine Parser Bibliothek, indem wir semantische Aktionen zum Parser hinzufuegen, um den Parsetree zu erzeugen.

Nachdem wir in Teil 1 und 2 einen Parser fuer unser Konfigurationsformat erstellt haben, wollen wir nun eine geeignete Objektstruktur implementieren, die uns zum einen erlaubt, eine hierarchische In-Memory-Abbildung unseres Formats zu schaffen und die zum anderen moeglichst leicht mit Hilfe von semantischen Aktionen durch den Parser erstellt werden kann.

Es gibt dabei prinzipiell mehrere Moeglichkeiten, wie vorgegangen werden kann. Meine erste Idee war, einen Baum aus polymorphen Objekten aufzubauen, der verschiedene Objekttypen fuer alle einzelnen Elemente der Konfigurationsstruktur enthaelt. Dies waere zwar fuer die Erstellung der Speicherstruktur durch den Parser am geeignetsten gewesen, haette jedoch den Benutzerzugriff auf die Daten unnoetig erschwert. In einem weiteren Prototyp waehlte ich als Datenstruktur einen monomorphen Baum aus nur einem einzigen Klassentyp, was allerdings Probleme bei der Abbildung der Hierarchie und der spaeteren Auswertung mit sich brachte.

Ich entschied mich daher fuer einen Kompromiss aus beiden Ansaetzen, bei dem ich die funktional gleichen Objekttypen zusammenfasse und in einen polymorphen Baum ueberfuehre. Intern wird dabei in Baum aus Zeigern erstellt (um eine hohe Performance zu gewaehrleisten), das externe Interface arbeitet jedoch ausschliesslich mit Objektreferenzen, so dass wir auch mit ueberladenen Operatoren arbeiten koennen.

Alle Konfigurationselemente erben gemeinsam von einer Klasse element, die wir zunaechst als leer definieren:

class element { };

Wir werden erst spaeter Funktionalitaet zu element hinzufuegen, wenn wir das externe Interface definieren.

Im naechsten Schritt muessen wir die hierarchiegenerierenden Elemente auf Klassen abbilden. Unser Format erlaubt Gruppen, Listen und Arrays. Listen und Arrays haben das gleiche Interface, sie unterscheiden sich lediglich in den zugelassenen Typen ihrer Subelemente. Da wir fuer dieses Tutorial keine Ruecktransformation unserer Objekthierarchie in eine Konfigurationsdatei benoetigen, koennen wir Liste und Array als gleichwertig betrachten und in einen Typ (list) zusammenfassen. Die Gruppe unterscheidet sich hingegen funktional von Liste und Array und wird deshalb getrennt abgebildet (group):

class group : public element
{
  void insert(const std::string& key, element* value)
  {
    std::string key_(key); settings_.insert(key_, value);
  }
 
  typedef boost::ptr_map<std::string, element> setting_map_t;
  setting_map_t settings_;
};
 
class list : public element
{
  void append(element* value) { settings_.push_back(value); }
 
  typedef boost::ptr_vector<element> setting_list_t;
  setting_list_t setting_;
};

Ich habe die insert bzw. append Funktionen absichtlich als private implementiert, da der Konfigurationsbaum fuer den Benutzer nicht modifizierbar sein soll. Den Parser werden wir spaeter als friend deklarieren.

Es fehlt nun nur noch eine Repraesentation der atomaren Elemente (Integer, Double, String und Bool). Wie bereits besprochen werden wir diese zu einer Klasse zusammenfassen:

class atom : public element
{
  explicit atom(const boost::variant<bool, long, double, std::string>& value) :
    value_(value)
  {}
 
  boost::variant<bool, long, double, std::string> value_;
};

Diese einfache Implementierung reicht bereits aus, um den Baum erzeugen zu koennen. Allerdings ist der Konfigurationsbaum recht nutzlos, wenn der Benutzer keine Moeglichkeit hat, diesen zu analysieren und einzelne Elemente zu extrahieren. Wir benoetigen also noch ein oeffentliches Interface, das uns eine Interaktion mit den Daten ermoeglicht.

Beginnen wir mit dem atom. Um auf den gekapselten Wert zugreifen zu koennen, koennten wir beispielsweise eine Funktion schreiben, die eine Kopie (oder konstante Referenz) des gespeicherten Variants zurueckgibt. Das hat jedoch den Nachteil, dass der Benutzer selbst boost::get aufrufen muss, um den Wert aus dem Variant zu extrahieren. Unser Ziel soll jedoch sein, die Verwendung der atom Klasse so transparent wie moeglich zu gestalten und die Implementierung nach aussen hin moeglichst zu verbergen. Daher fuegen wir besser der Klasse atom eine Funktion as() hinzu, die folgendermassen implementiert ist:

class atom : public element
{
  // ...
 
public:
  template <typename T>
  const T as() const
  {
    return boost::apply_visitor(atom_detail::visitor<T>(), value_);
  }
 
  // ...
};

Die Aufgabe des hier verwendeten Visitors ist nicht nur die Extraktion des gewuenschten Typs aus dem Variant, sondern gleichzeitig eine Konvertierung der zulaessigen Werte untereinander, um zum Beispiel einen Double Wert auch als String extrahieren zu koennen. Die Implementierung des Visitors ist etwas umfangreicher und nicht sonderlich interessant, daher verweise ich diesbezueglich auf den Quellcode, der im Teil 3b verlinkt ist.

Betrachten wir als naechstes die Klasse group. Sie benoetigt zum einen ein Interface, um ueber die Subelemente iterieren zu koennen, zum anderen eine Moeglichkeit, direkt das zugehoerige Element zu einem beliebigen Key extrahieren zu koennen. Beides ist einfach zu realisieren:

class group : public element
{
  // ...
 
public:  
  const element& get(const std::string& key) const
  {
    setting_map_t::const_iterator it = settings_.find(key);
    if(it == settings_.end())
      throw std::runtime_error("element not found");
    return *it->second;
  }
 
  typedef setting_map_t::const_iterator const_iterator;
  const_iterator begin() const { return settings_.begin(); }
  const_iterator end() const { return settings_.end(); }
 
  // ...
};

Fuer list implementieren wir die Iteratoren analog, statt der get Funktion mit einem String Key schreiben wir jedoch ein get mit Index:

class list : public element
{
  // ...
 
public:
  const element& get(size_t index) const { return settings_[index]; }
 
  // ...
};

Im naechsten Teil definieren wir das (umfangreichere) Interface fuer die Klasse element, die den zentralen Dreh- und Angelpunkt fuer den Zugriff auf die Konfigurationshierarchie darstellen wird.