AST (Abstract Syntax Tree)

AST (Abstract Syntax Tree) on lähdekoodin graafinen esitys, jota kääntäjät käyttävät ensisijaisesti koodin lukemiseen ja kohdekoodien luomiseen.

Esimerkiksi tämän koodinäytteen AST:

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

näyttää seuraavalta:

Muunnos lähdekoodista AST:ksi, on hyvin yleinen kuvio käsiteltäessä mitä tahansa tyyppistä strukturoitua tietoa. Tyypillinen työnkulku perustuu ”Parserin luomiseen, joka muuntaa raakadatan graafipohjaiseen muotoon, jota renderöintimoottori voi sitten käyttää.”

Tämä on pohjimmiltaan prosessi, jossa raakadata muunnetaan vahvasti tyypitetyiksi muistissa oleviksi objekteiksi, joita voidaan manipuloida ohjelmallisesti.

Tässä on toinen esimerkki todella siististä verkkotyökalusta astexplorer.net:

Huomaa, miten yllä olevassa kuvassa DOT-kielinen raakamuotoinen teksti on muunnettu objektipuuksi (joka voidaan myös kuluttaa/tallentaa json-tiedostona).

Kehittäjänä, jos pystyt ”näkemään koodin tai raakadatan graafina”, olet tehnyt hämmästyttävän paradigmanvaihdoksen, joka auttaa sinua valtavasti koko hoitotyössäsi.

Olen esimerkiksi käyttänyt AST:iä ja omia parsereita mm:

  • kirjoittaa testejä, jotka tarkistavat, mitä koodissa oikeasti tapahtuu (helppoa, kun sinulla on pääsy koodin objektimalliin)
  • käyttää lokitietoja, joita tavalliset ’regex’-pohjaiset jäsentimet eivät ymmärtäneet
  • suorittaa staattista analyysia koodille, joka on kirjoitettu mukautetuilla kielillä
  • muodostaa datan dumppauskappaleet in-muistiobjekteiksi (joita voidaan sitten helposti muuntaa ja suodattaa)
  • luoda muunnettuja tiedostoja, joissa on viipaleita useista lähdekooditiedostoista (joita kutsuin MethodStreams- ja CodeStreams-tiedostoiksi) – Katso alla oleva esimerkki siitä, miltä tämä näyttää käytännössä
  • suorittaa mukautettua koodin refaktorointia (esimerkiksi koodin tietoturvaongelmien automaattinen korjaaminen) – Katso alla oleva esimerkki siitä, miltä tämä näyttää käytännössä

Kun rakennat jäsentäjän tiettyä tietolähdettä varten, keskeinen virstanpylväs on kyky siirtyä AST:stä takaisin alkuperäiseen tekstiin (ilman tietojen menetystä).

Juuri näin koodin refaktorointi IDE:ssä toimii (esimerkiksi kun nimeät muuttujan uudelleen ja kaikki kyseisen muuttujan instanssit nimetään uudelleen).

Näin tämä round-trip toimii:

  1. aloita tiedostosta A (esim. lähdekoodi)
  2. luo tiedoston A AST
  3. luo tiedosto B muunnoksena AST:stä
  4. tiedosto A on yhtä kuin tiedosto B (tavu tavulta)

Kun tämä on mahdollista, koodin muuttaminen ohjelmallisesti helpottuu, koska manipuloimme vahvasti tyypiteltyjä objekteja ilman, että tarvitsisi murehtia syntaktisesti oikeanlaisen lähdekoodin luomisesta (joka nyt on muunnos AST:stä).

Testien kirjoittaminen AST-objekteja käyttäen

Kun alat nähdä lähdekoodisi (tai datan, jota kulutat) ’vain AST-parserin päässä siitä, että ne ovat objekteja, joita voit manipuloida’, sinulle avautuu kokonainen sana mahdollisuuksia ja kyvykkyyksiä.

Hyvä esimerkki on se, miten voit havaita lähdekoodista tietyn kuvion, jonka haluat varmistaa, että se esiintyy suuressa määrässä tiedostoja, sanotaan vaikka, että haluat esim: ”Varmista, että tiettyä Authorization (tai data validation) -menetelmää kutsutaan jokaisessa Web Services -menetelmässä”?

Tämä ei ole triviaali ongelma, sillä ellet pysty kirjoittamaan ohjelmallisesti testiä, joka tarkistaa tämän kutsun, ainoat vaihtoehtosi ovat:

  1. kirjoita ”standardidokumentti/wiki-sivu”, joka määrittelee tämän vaatimuksen, ja varmista, että kaikki kehittäjät lukevat sen, ymmärtävät sen ja mikä tärkeintä, noudattavat sitä
  2. manuaalisesti tarkista, onko tämä standardi/vaatimus toteutettu oikein (Pull Requests -koodin tarkistuksissa)
  3. kokeile automatisointia regexiin perustuvilla (kaupallisilla tai avoimen lähdekoodin) työkaluilla, ja ymmärtää, että on todella vaikeaa saada siitä hyviä tuloksia
  4. turvautua manuaalisiin QA-testeihin (ja tietoturva-arvosteluihin) mahdollisten sokeiden pisteiden havaitsemiseksi

Mutta kun sinulla on valmiudet kirjoittaa testejä, jotka tarkistavat tämän vaatimuksen, tapahtuu seuraavaa:

  1. kirjoittaa testejä, jotka kuluttavat koodin AST:tä, jotta voidaan hyvin eksplisiittisesti tarkistaa, onko standardi/vaatimus toteutettu/koodattu oikein
  2. testitiedostossa olevien kommenttien avulla dokumentaatio voidaan luoda testikoodista (esim.eli dokumentaation luomiseen ei tarvita ylimääräistä vaihetta kyseistä standardia/vaatimusta varten)
  3. suorita nämä testit osana paikallista rakentamista ja osana pää-CI-putkea
  4. Epäonnistuneen testin avulla kehittäjät tietävät ASAP, kun ongelma on havaittu, ja voivat korjata sen hyvin nopeasti

Tämä on täydellinen esimerkki siitä, miten arkkitehtuuria ja turvallisuusvaatimuksia voidaan skaalata ohjelmistokehityksen elinkaareen upotettavalla tavalla.

Tarvitsemme AST:itä legacy- ja pilviympäristöihin

Mitä enemmän AST:iin perehtyy, sitä enemmän tajuaa, että ne ovat abstraktiokerroksia eri kerrosten tai ulottuvuuksien välillä. Vielä tärkeämpää on, että ne mahdollistavat tietyn kerroksen datan manipuloinnin ohjelmallisesti.

Mutta kun tarkastellaan nykyisiä legacy- ja pilviympäristöjä (sitä osaa, jota kutsumme nimellä ’Infrastructure as code’), huomataan, että näissä ekosysteemeissä on suuria osia, joilla ei nykyään ole AST-parsereita, joilla niiden todellisuus voitaisiin muuntaa ohjelmoitaviksi objekteiksi.

Tämä on loistava tutkimusalue, jossa keskittyisit luomaan DSL:iä (Domain Specific Languages) joko legacy-järjestelmille tai pilvisovelluksille (valitse jompikumpi, koska kummallakin on täysin erilaiset lähdemateriaalit). Yksi esimerkki tarvitsemastamme DSL:stä on kieli, jolla voidaan kuvata ja koodata Lambda-funktioiden käyttäytymistä (eli mitä resursseja ne tarvitsevat suorittaakseen ja mikä on Lambda-funktion odotettu käyttäytyminen)

MethodStreams

Yksi tehokkaimmista esimerkeistä AST-manipulaatiosta, jonka olen nähnyt, on MethodStreams-ominaisuus, jonka lisäsin O2 Platformiin.

Tämän ominaisuuden avulla kykenin luomaan ohjelmallisesti tietyn metodin soittokutsupuuhun perustuvan tiedoston. Tämä tiedosto sisälsi kaiken kyseiseen alkuperäiseen metodiin liittyvän lähdekoodin (joka oli luotu useista tiedostoista), ja se teki valtavan eron koodikatselmuksia tehtäessä.

Ymmärtääksemme, miksi tein tämän, aloitetaan ongelmasta, joka minulla oli.

Taannoin vuonna 2010 tein koodikatselmusta .Net-sovellukselle, jossa oli miljoona riviä koodia. Tarkastelin kuitenkin vain WebServices-metodeja, jotka kattoivat vain pienen osan kyseisestä koodipohjasta (mikä oli järkevää, koska ne olivat internetille altistuvia metodeja). Tiesin, miten löydän nämä internetille altistuvat metodit, mutta ymmärtääkseni, miten ne toimivat, minun oli tarkasteltava satoja tiedostoja, jotka sisälsivät koodia kyseisten metodien suorituspolulla.

Koska O2 Platformissa minulla oli jo erittäin vahva C#-jäsennystuki ja koodin refaktorointituki (toteutettu REPL-ominaisuutta varten), pystyin kirjoittamaan nopeasti uuden moduulin, joka:

  1. alkaen verkkopalvelun metodista X
  2. laski kaikki metodit, joita kutsuttiin kyseisestä metodista X
  3. laski kaikki metodit, joita kutsuttiin metodilla 2. (rekursiivisesti)
  4. kaappasi AST-objektit kaikista edellisissä vaiheissa tunnistetuista metodeista
  5. luonut uuden tiedoston, joka sisälsi kaikki objektit kohdasta 4.

Tämä uusi tiedosto oli hämmästyttävä, koska se sisälsi AINOASTAAN sen koodin, jota minun on luettava tietoturvatarkastuksen aikana.

Mutta se sai tapahtuman paremmaksi, sillä tässä tilanteessa pystyin lisäämään validoinnin RegExit (joita sovelletaan kaikkiin WebServices-metodeihin) tiedoston yläosaan ja lisäämään asianomaisten Stored Proceduresien lähdekoodin tiedoston alaosaan.

Joissain generoiduissa tiedostoissa oli yli 3k riviä koodia, mikä oli massiivinen yksinkertaistus niitä sisältäviin yli 20 tiedostoon (joissa oli luultavasti yli 50k riviä koodia) verrattuna.

Tässä on hyvä esimerkki siitä, että pystyn tekemään parempaa työtä, kun minulla on käytössäni laaja valikoima valmiuksia ja tekniikoita (tässä tapauksessa kyky ohjelmallisesti manipuloida lähdekoodia)

Tämä AST-manipulaation tyyppi on tutkimusalue, johon suosittelen sinulle keskittymistä (joka antaa sinulle myös massiivisen työkalupakin päivittäiseen koodaustoimintaasi). Btw, jos menet tälle tielle, tutustu myös O2 Platformin CodeStreamsiin, jotka ovat MethodStreams-teknologian evoluutio. CodeStreams antaa sinulle virran kaikista muuttujista, joita tietty lähdemuuttuja koskettaa (mitä staattisessa analyysissä kutsutaan Taint flow -analyysiksi ja Taint Checkingiksi)

Koodin korjaaminen reaaliajassa (tai kääntämisaikana)

Toinen todella hieno esimerkki AST-manipulaation voimasta on PoC, jonka kirjoitin vuonna 2011 aiheesta Fixing/Encoding .NET-koodi reaaliajassa (tässä tapauksessa Response.Write), jossa näytän, miten ohjelmallisesti lisätään tietoturvakorjaus haavoittuvaan menetelmään.

Tältä näytti käyttöliittymä, jossa vasemmalla oleva koodi muunnettiin ohjelmallisesti oikealla olevaan koodiin (lisäämällä ylimääräinen AntiXSS.HtmlEncode wrapper-metodi)

Tässä on lähdekoodi, jolla muunnos ja koodin korjaaminen tehdään (huomioi koodin kiertäminen):

Vuonna 2018 tapa toteuttaa tämä työnkulku kehittäjäystävällisellä tavalla, on luoda automaattisesti Pull Request noilla ylimääräisillä muutoksilla.

Vastaa

Sähköpostiosoitettasi ei julkaista.