Hlavní navigace

JSON pro C++11 s immutabilním DOMem.

12. 1. 2017 1:52 | Ondřej Novák

Po dlouhé době jsem se rozhodl, že zaseněco napíšu na blog zde na Rootu a i tentokrát to bude něco z mé vlastní programátorské tvorby. Jde o knihovnu ImtJSON která je určena k práci s formátem JSON a je k dispozici zcela zdarma pod licencí MIT. Odkaz najdete na konci článku.

Důvody vzniku další knihovny pro práci s JSONem mohou být pro „přespolního“ programátora nejasné. Vždyť se stačí podívat na stránky www.json.org, které jsou výživným zdrojem informací o tomto populárním formátu, a lze zde najít také stovky odkazů na rozličné knihovny ve všech možných programovacích jazycích, z nichž pro jazyk C a C++ jich jsou desítky. A tak k čemu další knihovna? Pokusím se v tomto článku stručně shrnout  zajímavé vlastnosti právě knihovny ImtJSON a  vysvětlit motivace k jejímu vzniku.

Úvod méně zasvecené

Parsovat a serializovat formát JSON je jednoduché, proto zpracovat takové zadání zvládne každý programátor za odpoledne. Je to tak snadné, že existují minimální implementace ve formě jednoho hlavičkového souboru, který se pouze vloží do zdrojového kódu a mohu začít pracovat s JSONem. Nicméně jsem přesvědčen o tom, že to k vytvoření dobrého nástroje nestačí. Důležitý je i způsob, jak jsou parserem načtená data organizovaná v paměti a skrze jaké funkce se přistupuje k dílčím datům. Tady existují dva přistupy. První, jednodušší, avšak v případě formátu JSON ne tak často užívaný (častěji jsem ho viděl u XML) je parser, který při průchodu JSONem volá programátorem určené události, ve kterých se data přímo zpracovávají. Tyto implementace mají svůj význam, bývají jednodušší a slouží víceméně k takovému rychlému načtení dat z JSONu, něco ve stylu „zajímá mne jen tady to pole, zbytek ignoruj“, případně ke zpracování nekonečných streamů v JSONu. Druhým přístupem je vytvoření DOMu . Parser v tomto případě ukládá data do vnitřní reprezentace, která se označuje zkratkou DOM (Document Object Model) a stejně tak serializátor převádí DOM reprezentaci zpět do formátu JSON. Programátor tak nepracuje s JSONem přímo, ale s nějakou vnitřní reprezentací, byť ta má často podobnou strukturu jako původní JSON. Konečně, zkratka JSON znamená JavaScript Object Notation, což není nic jiného, než textová reprezentace objektového DOMu v JavaScriptu.

Motivace

Motivací bylo několik. V původní verzi článku jsem je tu měl všechny popsané, ale bylo to dlouhý, tak to zkrátím. Hlavní motivací zavést imutabilní DOM bylo aby se zabránilo modifikacím již vytvořené struktury. Na začátku přitom stál systém cachování výsledků jedné NoSQL databáze. Dokud bylo možné měnit kontejnery DOMu (což znamená objekty a pole), pak se snadno dal měnit obsah cache. Skutečnost, že se kontejnery při vkládání do dalších kontejnerů zpravidla předávají jako odkazy (nebo chcete-li reference), tak jak je běžné v JavaScriptu, klade na programátora potažmo na vlastní kód povinnost vědět, s čím zrovna pracuje a jak budou fungovat různé operace s dílčím kontejnerem. Že vložit do kontejneru kontejner je něco jiného, než vložit tam konstantu. Že lze vytvořit cyklus, atd.

Hodnota proměnné by měla být identifikována svým obsahem, nikoliv nějakou referencí. Pokud do kontejneru vložím číslo 42, zůstane číslem 42 i když ho později – mimo kontejner – změním na číslo 56. Totéž by mělo platit i o vloženém poli nebo objektu. V C++ mám dostatečné vyjadřovací nástroje, abych mohl vyjádřit, zda některá proměnná může být měněna nebo nesmí. Mohu do funkcí předávat proměnnou volanou hodnotou nebo referencí. Nesmí se mi tedy stát, že proměnnou volanou hodnotou budu moci změnit tak, že se změna projeví i u volajícího.

Zavedením pravidla neměnitelnosti se spoustu věcí zjednodušilo. Zmizely totiž reference, zmizela nutnost neustále kopírovat DOM tam, kde jsem chtěl mít jistotu, že existuje jediný vlastník DOMu, a zmizely pointery. A přestože interně je DOM implementován  pomocí pointerů a polymorfizmu, uživatel knihovny toto nemusí vůbec znát ani se tím zabývat. Všechny proměnné, bez ohledu na obsah, se chovají jednotně. 

Samozřejmě to znamenalo trochu změnit přístup k práci. Díky tomu, že s každou změnou vzniká nový DOM, jsou v knihovně nástroje (třídy), které umožňují zaznamenat dílčí změny, než jsou použity na vytvoření nového DOMu. Tyto třídy nejsou součástí DOMu, takže se nedají moc dobře sdílet. I tak se mi s tím pracuje dobře a nemám pocit, že by neustále vytváření nových a nových DOMů při každé změně znamenalo významný výkonový zásah. Je to částečně dáno tím, že knihovna využívá neměnitelnost k tomu, aby se redukovalo vytváření zbytečných kopii. Pokud by toto pravidlo nebylo vynuceno, pak každý nový DOM by musel být hlubokou kopii původního DOMu, protože by stále hrozilo nebezpečí, že někdo nebo něco dokáže změnit obsah nějakého vnitřního kontejneru tím, že drží jeho referenci.

Ještě se zmíním o jedné z motivací a tou bylo napsat knihovnu co nejvíce KISS (Keep it simple stupid), tak aby práce s formátem i s výsledným DOMem byla maximálně jednoduchá. intuitivní a výsledkem byl stabilní kód. Nenajdete v ní žádné pointery, minimum šablon, většinu moderních prvků C++, lambdy, iterátory a jak jsem napsal výše, jednotlivé hodnoty DOMu se při manipulaci chovají jednotně a předvídatelně.

Výhody imutabilního DOMu

  • Neměnnost garantována, tedy všechny části programu mají zaručeno, že se data v DOMu nebudou měnit „pod rukama“, z toho dále vyplývají možnosti: 
  • Kopírování sdílením. Díky výše uvedené vlastnosti, se mohou hodnoty kopírovat sdílením reference. Tato optimalizace se vně nikterak neprojeví, kopie je zdánlivě nezávislá na originálu
  • Správné chování proměnných. Proměnné obsahující element DOMu se chovají tak, jak se od nich očekává. Není třeba hlídat, zda vkládám hodnotu nebo referenci, protože díky neměnnosti to nehraje roli.
  • MT Safe. Immutabilní objekty jsou vždycky bezpečné pro sdílení mezi vlánky bez nutnosti používat zámky. To platí do té doby, dokud se samotná sdílená proměnná nemění. Při změně sdílené proměnné je samozřejmě nutné zámek použít, avšak na samotnou změnu té proměnné, není třeba zamykat celý DOM
  • Neexistence cyklů. JSON formát cykly neumožňuje, ale DOM, který pracuje jako orientovaný graf, zacyklit lze. Stačí do vnořeného kontejneru vložit odkaz na vnější kontejner. Takový DOM není validní a špatně se s ním pracuje (rekurzivní algoritmy se v něm zacyklí). Navíc se nedá serializovat do JSONu. Immutabliní verze neumožňuje vytvářet cykly. Není totiž možné vložit do vnořeného kontejneru vnější kontejner, protože tím vznikne nový kontejner, který již není nikam vnořen.
  • Jednoduchy GC. Uživatel knihovny o existenci garbage collectoru nemusí nic tušit, protože se navenek neprojevuje. GC zajišťuje uvolnění paměti elementů DOMu, které nejsou nikde sdílené. Díky neexistenci cyklů si vystačí s počítáním referencí.
  • Mělké kopie. Při jakékoliv změně kontejneru se vytváří mělká kopie. Je to dáno tím, že u hodnot v kontejneru, pokud to jsou samy kontejnery, máme opět jistotu, že se měnit nemohou

Nevýhody immutabilního DOMu

Immutablní řešení má samozřejmě nějaké nevýhody:

  • Každá změna znamená vytvoření kopie
  • Při změně na N té úrovni DOMu je třeba vytvořit kopii všech úrovní nad. Výsledkem je pak upravená kopie původního DOMu
  • Vytváření kopíí vyžaduje víc paměti
  • Někdy těžkopádné zacházení při změně jednoho prvku.

Příklady práce s knihovnou

Příklad vytváří celočíselnou hodnotu, float hodnotu, stringovou hodnotu, boolovskou hodnotu a poslední příklad vytváří hodnotu null.

using namespace json;

Value a(10), b(12.3), c("Ahoj svete"),d(true), e(false), f(nullptr);

Vytvoření pole

using namespace json;

Value pole = {10, 12.3, "Ahoj svete", true, false, nullptr};

Vytvoření objektu

using namespace json;

Value objekt = Object("foo", 10)
                     ("bar", 12.3)
                     ("baz", "Ahoj svete")
                     ("damn", nullptr);

Změny v kontejnerech.

Měnit lze pole nebo objekt. Pro změnu pole se použije třída Array, pro změnu objektu pak třída Object. Instance obou tříd lze zpět převést na Value čímž vznikne kopie upravené verze kontejneru. Instance tříd Array a Object nemohou být součástí DOMu.

Object e(objekt);   // uprav objekt v promenne e
e.set("flag",false); // nastav klic
e.unset("damn");  // smaz klic
objekt = e;  //prepis promennou objekt novou verzi

Array a(pole);
a.push_back(42);
pole = a;

Iterace a čtení hodnot

Pro iteraci kontejnery lze použít standardní begin() a end() a tedy i nové range-based for

for (Value v: pole) {
  std::cout << "value:" << v.toString() << std::endl;
 }

Iterovat lze i objekt

for (Value v: objekt) {
  StrViewA key = v.getKey();
  std::cout << "key:" << key << ", value:" << v.toString() << std::endl;
}

U iterace objektů se klíč získává z hodnoty. Je vracen jako typ StrViewA, což je typedef na StringView<char>. Tento typ je v knihovně zaveden pro rychlé a univerzální předávání řetězců a lze jej velice jednoduše převést na std::string

Iterovat lze i přes index

for (std::size_t i = 0, cnt = pole.size(); i < cnt; ++i) {
   Value v = pole[i];   std::cout << "value:" << v.toString() << std::endl;
}

Iterovat lze i přes index i objekty

for (std::size_t i = 0, cnt = objekt.size(); i < cnt; ++i) {
  Value v = objekt[i];
  StrViewA key = v.getKey();
  std::cout << "key:" << key << ", value:" << v.toString() << std::endl;
}

Hodnoty se vyzvedávají pomocí funkcí:

v.getUInt() → uintptr
v.getInt() → intptr
v.getNumber() → double
v.getString() → StrViewA
v.getBool() → bool
v.isNull() → bool
v.defined() → bool

Použití metod pro vyzvedávání hodnot je zavedeno čistě záměrně. Šlo by samozřejmě použít konverzní operátor, ale mám vyzkoušeno, že to dělá neplechu. Samotná třída Value přijímá mnoho typů a pokud by se potkala s proměnnou, která se dá konvertovat do mnoho typů, překladač bude protestovat.

Pro použití v šablonách, kdy je třeba vyzvednout určitý typ podle T je k dispozici metoda as<T>(). K tomu lze pomocí specializace třídy ConvValueAs<T> rozšiřovat schopnost automatické konverze přes tuto metodu.

v.as<unsigned int>();
v.as<bool>()
v.as<std::string>();

K prvkům kontejneru lze přistoupit přes hranaté závorky. K dispozici jsou i funkce na zjištění velikosti kontejneru (size), typu objektu (type) a další. Nechci zabíhat do podrobností, mnohem víc se dozvíte na stránkách projektu.

objekt["foo"].getUInt();
pole[1].getNumber();

Pár implementačních detailů

  • Používá se ve velkém měřítku sdílení a čítání referencí (nepoužívá se std::shared_ptr, ale intrusivní čítač) + atomické incrementy a decrementy
  • Klíče a řetězce nejsou uloženy ve std::string (byl by to kanon na vrabce). Přímo se ukládají v elementu DOMu jako pole znaků.
  • Objekty nemají klíče uloženy v mapě, jak se nabízí, ale ve vektoru. Položky jsou seřazeny a hledá se v nich půlením intervalu. Použití vektoru zjednodušuje iteraci. Při iteraci objektem jsou vráceny klíče řazené podle ascii
  • Při vytváření kopie změněného objektu se dělá operace merge, která jedním průchodem vytvoří nový objekt ze kterého se vymažou odstraněné položky a přidají nově zavedené položky.
  • Instance třídy Object funguje jako diff. Lze jej aplikovat i na jiný objekt, než na původní.
  • Instance třídy Array lze také použít jako diff, tam se však změna aplikuje na všechny položky s indexem větším než je nejmenší změněný index.
  • Nepřiřazená proměnná má hodnotu „undefined“. Dereference takové proměnné nezpůsobí výjimku ani pád aplikace, pouze zpravidla vrací nuly, nebo se tváří jako prázdná. Funkcí defined() lze testovat zda je proměnná definována. Při dotazu kontejneru na neexistující klíč nebo index je též vrácena hodnota undefined
  • Objekt String – vznikl trochu bokem, využívá schopnost DOMu uchovávat stringy. Definuje rozhraní pro práci s JSON stringem, ale má širší využití, lze jej použít mimo DOM, jako immutabilní náhradu std::string. Hodí se pro uložení finální stringů, třeba jako klíčů v mapách, nebo v hodnotách. Na rozdíl od std::string se v paměti drží jen jednou a kopírováním se sdílí. 

Serializace a parsování

Na závěr se krátcezmíním o parseru a serializatoru. Nejsem totiž velký fanda standardní knihovny a zejména iostreamů. Přesto je mi jasné, že by knihovna měla umět serializovat do ostreamu a parsovat z istreamu. Proto zde najdete funkce Value::toStream() a Va­lue::fromStream(). Ale to nestačí. V knihovně najdete mnohem univerzálnější nástroj pro serializaci do čehokoliv a parsování z čehokoliv. A nejde o definici nějakých nových speciálních streamů. Naopak, snažil jsem se to maximálně zjednodušit.

Funkce Value::parse() a Va­lue.serialize() jsou totiž šablony, obě přijímají funkci nebo objekt který implementuje volaní funkce.

  • Value::parse() očekává funkci int(void)
  • Value::serialize() očekává funkci void(int)

V obou případech se předpokládá, že programátor použije lambda funkci. Při serializaci se parametrem předává znak, pro zápis. Při parsování se očekává že funkce vrátí další znak, nebo znak –1 pro konec souboru.

Příklad čtení z stdin a zápis na stdout (v C variantě)

Value v = Value::parse(
          []{return getchar();}
);
v.serialize(
          [](int c){putchar(c);}
);

Tímto jednoduchým způsobem lze implementovat například posílání JSONu rourou, síťovým spojením, nebo uložení JSONu do sdílené paměti. V rámci knihovny ImtJSON je k dispozici také jednoduchý komprimační nástroj, o kterém bych se zmínil v příštím článku.

Závěrem…

Aktuální verzi, která by se měla dát přeložit jak v Linuxu tak ve Windows najdete na Githubu. Pokud by někdo našel chybu, nemusí váhat využít issue tracker nebo napsat pull request. Potěší mě, když to bude někdo používat a zašle mi zpětnou vazbu. Na všechny otázky v diskuzi se pokusím odpovědět.

Připravil jsem si ještě dva články o některých featurách. Příště by to bylo o binárním formátu JSONu a ten další pak o popisu struktury dat uložené v JSONu a validaci dat (dokumentu) oproti tomu popisu.

Děkuji za pozornost.