AST (Abstract Syntax Tree)

AST (Abstract Syntax Tree) je grafová reprezentace zdrojového kódu, kterou používají především překladače pro čtení kódu a generování cílových binárních souborů.

Například AST této ukázky kódu:

while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a

bude vypadat takto:

Transformace zdrojového kódu do AST, je velmi častým vzorem při zpracování jakéhokoliv typu strukturovaných dat. Typický pracovní postup je založen na „vytvoření parseru, který převede surová data do formátu založeného na grafech, který pak může být spotřebován vykreslovacím jádrem“.

Jde v podstatě o proces převodu surových dat na silně typované objekty v paměti, se kterými lze programově manipulovat.

Tady je další příklad z opravdu skvělého online nástroje astexplorer.net:

Všimněte si, jak byl na obrázku výše převeden surový text v jazyce DOT na strom objektů (který lze také konzumovat/ukládat jako soubor json).

Jako vývojáři, pokud jste schopni „vidět kód nebo surová data jako graf“, provedete úžasnou změnu paradigmatu, která vám nesmírně pomůže napříč vaší péčí.

Například jsem použil AST a vlastní parsery:

  • napsat testy, které kontrolují, co se v kódu skutečně děje (snadné, když máte přístup k objektovému modelu kódu)
  • převzít data z logů, kterým běžné parsery založené na ‚regexech‘ jen těžko rozuměly
  • provádět statickou analýzu kódu napsaného ve vlastních jazycích
  • převést výpisy dat na in-paměťové objekty (které pak lze snadno transformovat a filtrovat)
  • vytvářet transformované soubory s řezy více souborů zdrojového kódu (které jsem nazval MethodStreams a CodeStreams) – viz příklad níže, jak to vypadá v praxi
  • provádět vlastní refaktoring kódu (například pro automatickou opravu bezpečnostních problémů v kódu) – viz příklad níže, jak to vypadá v praxi

Při vytváření parseru pro konkrétní zdroj dat, je klíčovým milníkem schopnost round-trip, tedy schopnost přejít z AST zpět na původní text (bez ztráty dat).

Přesně takto funguje refaktorizace kódu v IDE (například když přejmenujete proměnnou a všechny instance této proměnné se přejmenují).

Takto funguje tento round-trip:

  1. začněte souborem A (tj. zdrojový kód)
  2. vytvoříme AST souboru A
  3. vytvoříme soubor B jako transformaci z AST
  4. soubor A se rovná souboru B (bajt po bajtu)

Když je to možné, bude snadné měnit kód programově, protože budeme manipulovat se silně typovanými objekty, aniž bychom se museli starat o vytváření syntakticky správného zdrojového kódu (který je nyní transformací z AST).

Psaní testů pomocí objektů AST

Jakmile začnete vnímat svůj zdrojový kód (nebo data, která spotřebováváte) jako „pouze parser AST vzdálený od objektů, se kterými můžete manipulovat“, otevře se vám celé slovo možností a schopností.

Dobrým příkladem je, jak zjistit určitý vzor ve zdrojovém kódu, o kterém se chcete ujistit, že se vyskytuje ve velkém počtu souborů, řekněme například, že chcete: „zajistit, aby se konkrétní metoda autorizace (nebo ověření dat) volala u každé vystavené metody webových služeb“?

To není triviální problém, protože pokud nejste schopni programově napsat test, který toto volání kontroluje, máte jediné možnosti:

  1. napsat „standardní dokument/wiki-stránku“, který tento požadavek definuje, a zajistit, aby si jej všichni vývojáři přečetli, porozuměli mu a hlavně se jím řídili
  2. ručně zkontrolovat, zda byl tento standard/požadavek správně implementován (při revizích kódu v rámci Pull Requests)
  3. zkusit použít automatizaci pomocí nástrojů založených na „regexu“ (komerčních nebo open source), a uvědomit si, že je opravdu těžké z ní získat dobré výsledky
  4. opět se spolehnout na manuální QA testy (a bezpečnostní revize), abyste zachytili případná slepá místa

Ale když máte možnost napsat testy, které tento požadavek kontrolují, stane se toto:

  1. napište testy, které spotřebovávají AST kódu, abyste mohli velmi explicitně zkontrolovat, zda byla norma/požadavek správně implementována/kódována
  2. přes komentáře v testovacím souboru lze z testovacího kódu vygenerovat dokumentaci (tj.tj. k vytvoření dokumentace k tomuto standardu/požadavku není zapotřebí žádný další krok)
  3. provádět tyto testy jako součást lokálního sestavení a jako součást hlavní CI pipeline
  4. díky tomu, že test selhal, se vývojáři dozvědí co nejdříve, jakmile se objeví problém, a mohou jej velmi rychle opravit

Jedná se o dokonalý příklad toho, jak škálovat architekturu a bezpečnostní požadavky, a to způsobem, který je začleněn do životního cyklu vývoje softwaru.

Potřebujeme AST pro starší a cloudová prostředí

Čím více pronikáte do AST, tím více si uvědomujete, že se jedná o abstrakční vrstvy mezi různými vrstvami nebo dimenzemi. Důležitější je, že umožňují programově manipulovat s daty určité vrstvy.

Ale když se podíváte na současná starší a cloudová prostředí (část, kterou nazýváme „Infrastruktura jako kód“), uvidíte, že velké části těchto ekosystémů dnes nemají parsery AST, které by jejich realitu převedly na programovatelné objekty.

To je skvělá oblast výzkumu, kde byste se zaměřili na vytváření DSL (Domain Specific Languages) buď pro starší systémy, nebo pro cloudové aplikace (vyberte si jednu z nich, protože každá z nich bude mít úplně jiné sady zdrojových materiálů). Jedním z příkladů takového DSL, který potřebujeme, je jazyk pro popis a kodifikaci chování lambda funkcí (konkrétně zdrojů, které potřebují ke spuštění, a toho, jaké je očekávané chování lambda funkce)

MethodStreams

Jedním z nejvýkonnějších příkladů manipulace s AST, které jsem viděl, je funkce MethodStreams, kterou jsem přidal do platformy O2.

Pomocí této funkce jsem dokázal programově vytvořit soubor na základě stromu volání konkrétní metody. Tento soubor obsahoval veškerý zdrojový kód relevantní pro danou původní metodu (vygenerovaný z více souborů) a znamenal obrovský rozdíl při provádění revizí kódu.

Abychom pochopili, proč jsem to udělal, začněme problémem, který jsem měl.

V roce 2010 jsem prováděl revizi kódu aplikace .Net, která měla milion řádků kódu. Díval jsem se však pouze na metody WebServices, které pokrývaly jen malou část této kódové základny (což dávalo smysl, protože to byly metody vystavené internetu). Věděl jsem, jak tyto metody vystavené internetu najít, ale abych pochopil, jak fungují, musel jsem se podívat do stovek souborů, což byly soubory, které obsahovaly kód v cestě provádění těchto metod.

Protože jsem v platformě O2 již měl velmi silný parser jazyka C# a podporu refaktorizace kódu (implementovanou pro funkci REPL), mohl jsem rychle napsat nový modul, který:

  1. začíná na metodě webové služby X
  2. vypočítal všechny metody volané z této metody X
  3. vypočítal všechny metody volané 2. (rekurzivně)
  4. zachytil objekty AST ze všech metod identifikovaných předchozími kroky
  5. vytvořil nový soubor se všemi objekty ze 4.

Tento nový soubor byl úžasný, protože obsahoval POUZE kód, který potřebuji přečíst při bezpečnostní kontrole.

Ale bylo to ještě lepší, protože v této situaci jsem mohl přidat validační RegExy (aplikované na všechny metody WebServices) na začátek souboru a přidat zdrojový kód příslušných uložených procedur na konec souboru.

Některé z vygenerovaných souborů měly 3k+ řádků kódu, což bylo obrovské zjednodušení více než 20 souborů, které je obsahovaly (které měly pravděpodobně 50k+ řádků kódu).

Tady je dobrý příklad toho, že jsem dokázal odvést lepší práci díky tomu, že jsem měl přístup k široké sadě možností a technik (v tomto případě k možnosti programově manipulovat se zdrojovým kódem)

Tento typ manipulace s AST je oblast výzkumu, na kterou vám vřele doporučuji se zaměřit (což vám také poskytne obrovskou sadu nástrojů pro vaše každodenní kódovací činnosti). Btw, pokud se vydáte touto cestou, podívejte se také na CodeStreams platformy O2, které jsou evolucí technologie MethodStreams. CodeStreams vám poskytnou proud všech proměnných, kterých se dotýká určitá zdrojová proměnná (což se ve statické analýze nazývá Taint flow analysis a Taint Checking)

Oprava kódu v reálném čase (nebo v době kompilace)

Dalším opravdu skvělým příkladem síly manipulace s AST je PoC, který jsem napsal v roce 2011 na téma Fixing/Encoding .NET code in real time (v tomto případě Response.Write), kde ukazuji, jak programově přidat bezpečnostní opravu do zranitelné metody by design.

Tady vypadalo uživatelské rozhraní, kde byl kód vlevo, programově transformován na kód vpravo (přidáním další obalové metody AntiXSS.HtmlEncode)

Tady je zdrojový kód, který provádí transformaci a opravu kódu (všimněte si obtékání kódu):

V roce 2018 je způsob, jak implementovat tento pracovní postup způsobem přívětivým pro vývojáře, automatické vytvoření žádosti o stažení s těmito dodatečnými změnami.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.