úterý 31. března 2015

Uložení metody jako grafu

Dle specifikace jazyka Java metody deklarují spustitelný kód, který můžeme volat. Metody mohou být parametrizovány.

Popis deklarace metody je následující
MethodDeclaration:
    MethodHeader MethodBody
MethodHeader:
    MethodModifiersopt TypeParametersopt Result MethodDeclarator Throwsopt
MethodDeclarator:
    Identifier ( FormalParameterListopt )
Z popisu je zjevné, že metoda se skládá z hlavičky a těla metody. Hlavička může obsahovat seznam modifikátorů, parametrický typ a referenci na třídu zajišťující zachytávání vjímek. Nutný obsah hlavičky metody je návratový typ a název s případným seznamem přijímaných parametů.

Jako modifikátor metody lze použít:
  • Annotation
  • public
  • private
  • protected
  • abstract
  • static
  • final
  • synchronized
  • native
  • strictfp
První modifikátor značí anotaci metody. Nejedná se o řetězec "Annotation" nýbrž, že může před metodou být anotace, která se k této metodě vztahuje. Tato anotace bude v grafu interpretována vztahem metody s vrcholem anotace s názvem have_annotation. Modifikátory public, private a protected jsou grafem zachyceny vlastností vrcholu metody s názvem access. Dále bude mít vrchol grafu s typem metoda vlastnosti abstract, static, final, synchronized, strictfp a native značící stejnojmenné modifikátory metody.

Generickým metodám lze parametrizovat datový typ parametru, návratové hodnoty anebo třídy zajišťující zpracování vyjímek. Typové parametry se při deklaraci metody zadávají do špičatých závorek např.: <T>. Udávají tak název typového parametru v metodě. V extrémním případě může deklarace metody vypadat následovně:

1
2
3
public <T extends Exception> T method(T prom) throws T{
 return prom;
}

V grafu bude každý generický element (typ návratové hodnoty, datový typ parametru, třída pro zpracování vyjímek) navázán vztahem určujícím datový typ na speciální uzel značící typový parametr. 

Hlavička metody může obsahovat throws klauzuli pro deklaraci tříd zajišťujících zpracovávání vyjímek. Každá metoda může takto deklarovat žádnou nebo více tříd. Tato vlastnost bude v grafu zaznamenána vztahem throws mezi současnou třídou a referencovanou třídou.

Každá metody má svůj návratový datový typ. Ten může být buď void nebo jiný datový typ. Tato vlastnost bude zachycena vztahem s názvem is_type mezi metodou a referencovaným typem (resp. třídou). Dále bude mít vrchol metody vztah have_parameter se všemi svými parametry. Popis vrcholu parametru je níže.

Je popsáno ukládání hlavičky metody do grafu. Nyní je potřeba extrahovat některé informace z těla metody. Tělo metody obsahuje blok kódu. Z tohoto bloku kódu nás zejména zajímají metody volané z těla, metody volané příkazem throw, třídy využívané v klauzuli catch a používané datové typy. Abychom zachytili všechny metodou používané datové typy, označíme všechny datové typy proměnných v těle metody, parametry a návratové typy jako používané a vytvoří se vztah mezi metodou a referencovanou třídou s názvem uses. Jestliže se v těle metody najde volání jiné metody, vytvoří se vztah mezi metodou, odkud je volána metoda a volanou metodou s názvem call. Dále pokud metoda používá jinou třídu (datový typ) anebo volá metodu nějaké třídy, vytvoří se vztah uses mezi třídou, ve které je metoda deklarována a třídou, která je používaná nebo je je volána některá její metoda. Jestliže se nalezne klauzule throw v bloku kódu, bude vytvořen vztah s názvem call_throw s vrcholem metody, jež odpovídá referenci. Stejným způsobem se naváže vztah uses mezi analyzovanou třídou a třídou deklarující volanou metodu. Poslední požadovaná informace z těla kódu jsou datové typy zachytávaných vyjímek klauzulí catch. Pokud se tedy na nějaký takový datový typ narazí, vytvoří se vztah s názvem catch s patříčnou třídou.

Souhrn

Vlastnosti:
  • name (String)
  • static (yes/no)
  • final (yes/no)
  • access (public/private/protected)
  • abstract (yes/no)
  • synchronized (yes/no) 
  • native (yes/no)
  • strictfp (yes/no) 
Vztahy:
  • is_type (Třída)
  • have_parameters (Parametr)
  • call (Metoda)
  • uses (Třída)
  • throws (Třída) 
  • have_annotation (Anotace) 
  • call_throw (Metoda)
  • catch (Třída)
Totožný popis uložení do grafu platí také pro konstruktory metody. Jediný rozdíl v tomto případě je v typu vrcholu.

Parametry

Deklarace metody obsahuje také deklarace parametrů metody. Parametr může následovat po anotaci. Což se v grafu znázorní vztahem parametru s vrcholem anotace s názvem have_annotation. Dále mohou být určeny modifikátory, které však umožňují pouze řetězec final. Tento modifikátor bude tedy zařazen mezi možné vlastnosti vrcholu v grafu. Nutnou součástí je určení datového typu parametru a název parametru. V grafu bude název parametru zařazen mezi vlastnosti vrcholu a typ parametru bude interpretován hranou mezi uzlem parametru a referencovaným typem.

V jazyce Java je možné při deklaraci metody nastavit poslední parametr jako proměnlivý (variable arity parameter). Toto umožuje vložit do parametru libovolný počet parametrů deklarovaného typu. Popis této kontrukce je následující:
VariableModifiersopt Type... VariableDeclaratorId
Tedy je možné jej rozeznat pomocí třech teček mezi určením typu a názvu parametru. Toto se však může vyskytkou pouze jako poslední parametr. Proměnliné parametry budou v grafu zaznamenány jako pole odpovídajícího datového typu. Tedy pokud bude parametr deklarován podle následující ukázky, bude mít metoda jeden parametr s názvem prom, který bude mít vztah s vrcholem pole a to bude mít vztah s vrcholem String.

metoda(String...prom){}

V grafu bude parametr interpretován jako zvláštní vrchol. Podle možných modifikátorů a dalších možných vlastností parametru bude do seznamu vlastností vrcholu ukládáno dle následujícího souhrnu. Navíc se bude ukládat pozice parametru mezi ostatními parametry, protože při porovnávání reference metod je důležitý počet parametrů a posloupnost datových typů.

Souhrn pro parametr

Vlastnosti:
  • name (String)
  • final (yes/no)
  • position (int)
 
Vztahy:
  • is_type (Třída)
  • have_annotation (Anotace)

Jako komplexní příklad uložení metody a jeho parametrů do grafu nám poslouží následující kód.


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package test_package;

import java.io.IOException;

public class test_metoda <T> {

 public synchronized strictfp String metoda(T par) throws Exception{
  
  double d;
  if (par instanceof String){
   
  }else{
   throw new Exception();
  }
  
  try{
   d = 3/0;
  }catch(Exception e){
   // ...
  }
  
  
  return "";
 }
}



Zdroje:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html#jls-8.4

středa 25. března 2015

Uložení třídy jako grafu

Podle popisu třídy v dokumentaci Java7 (docs.oracle.com) deklarace třídy definuje nový referenční typ a popisuje, jak je implementována.

Existují třídy tzv. top level a naopak vnořené třídy. Vnořené třídy jsou deklarované uvnitř jiné třídy nebo rozhraní. Mezi vnořené třídy se řadí členské třídy, lokální třídy a anonymní třídy. V grafu budou mít vnitřní třídy speciální vrchol, kde anonymní třídy budou odlišeny jiným druhem vrcholu.

Třída může obsahovat atributy, metody, instance, statickou inicializaci a konstruktory. V grafu budou mít třídy vztah s atributy (have_attribute) a metodami (have_method). S konstruktory bude zacházeno jako s metodami s tím rozdílem, že budou vrcholy odlišeny typem.

Popis deklarace třídy je následující:
ClassDeclaration:
    NormalClassDeclaration
    EnumDeclaration

NormalClassDeclaration:
    ClassModifiersopt class Identifier TypeParametersopt
                                               Superopt Interfacesopt ClassBody
Z první části je zjevné, že existují dva druhy tříd. První jsou normální třídy a druhou je výčet (enum). Mezi normální třídou a výčtem je mnoho rozdílného, z hlediska grafu však ne, proto budou tyto dvě entity rozlišeny pouze typem vrcholu a dále s nimi bude zacházeno stejně.

Při deklaraci třídy jsou možné následující modifikátory:
  • Annotation
  • public
  • protected
  • private
  • abstract
  • static
  • final
  • strictfp  
Modifikátor Annotation značí anotaci třídy. Tedy, že v tomto místě bude anotace, která se vztahuje na následující třídu. Tento vztah bude symbolizován hranou mezi třídou a vrcholem anotace s názvem have_annotation. Přístupové modifikátory public, protected a private budou zachyceny v grafu vlastností access. Abstract, static a final mají v grafu speciální položku mezi vlastnostmi vrcholu. Strictfp, který striktně vynucuje plovoucí řadovou čárku u výrazů (2) bude do grafu ukládán pod stejným názvem.

S třídami, které deklarují generický typ bude zacházeno jako s ostatními třídami. Jméno třídy bude použito bez typového parametru. Java kompilátor se již postará o to aby byl typový parametr používán správně, proto není potřeba toto v grafu ošetřovat.

Třída může dědit od rodiče, kterého může mít pouze jednoho. V grafu nebude na počet předků brán zřetel (o to se stará kompilátor). Vrchol zastupující třídu tak bude mít možnost mít vztah s jinou třídou (extends), což bude charakterizovat dědění. Dále může třída implementovat rozhraní. Je možné implementovat více rozhraní, proto v grafu bude možnost navázat vztah na více vrcholů typu rozhraní.

Protože z hlediska vytváření grafu není mezi vnitřní třídou, anonymní třídou a jinou třídou rozdíl, bude s nimi pracováno stejně. Budou však rozlišeny typem vrcholu.

Protože není potřeba podrobně mapovat strukturu java balíků (package), bude tato informace uložena v každé tříde pouze jako vlastnost.


Souhrn

Vlastnosti:
  • name (String) 
  • static (yes/no)
  • abstract (yes/no)
  • final (yes/no)
  • anonym (yes/no)
  • inner (yes/no)
  • access (public/private/protected)
  • package (String) 
  • strictfp (yes/no) 
Vztahy:
  • extends (Třída)
  • uses (Třída)
  • implements (Rozhraní)
  • have_inner (Vnitřní třída)
  • have_anonym (Anonymní třída)
  • have_method (Metoda)
  • have_attribute (Atribut)
  • have_annotation (Anotace)
Stejný popis vrcholu bude mít vnitřní třída, anonymní třída a výčet.

Pro příklad je vytvořen následující kód. Třída s názvem Třída je označena modifikátory public a final. Dále tato třída dědí od třídy Object a implementuje rozhraní s názvem Runnable. Toto rozhraní vyžaduje implementaci metody run. Třída dále obsahuje jeden atribut, který je navíc typu, jež je deklarován uvnitř třídy. Obsažena je tedy také vnitřní třída s názvem VnitrniTrida, která disponuje jením atributem.

Ukážeme si, jak by mohl vypadat graf pro tento kód.



1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
package experiment;

public final class Trida extends Object implements Runnable{
    class VnitrniTrida{
        public String atribut_vnitrni_tridy;
    }

    private VnitrniTrida atribut = new VnitrniTrida();
    public void run() {
        // ..
    }
}




Zdroje:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html
http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.4

Datový typ vs třída a jejich konverze

Důvodem definování typů Datový typ a třída je oddělení typů, které jsou definovány v rámci analyzovaného kódu a neanalyzovaného kódu. Příkladem může být jednoduchý program Hello world, ve kterém je používaná konstanta typu String.


1
2
3
4
5
6
public class Main {
 public static void main(String[] args) {
  String hw = "Hello world";
  System.out.print(hw);
 } 
}

Analýzou čistě tohoto programu není k dispozici AST třídy String, proto je String do grafu zaznačen jako Datový typ. Datový typ není v grafu popsán více než názvem a vztahy, kdo jej využívá. Případně, pokud je využívána metoda této nemapované třídy, vytvoří se ješte vztah s informací, že tento datový typ disponuje volanou metodou.

Problém může nastat při větším množství dekompilovaných souborů, kde je analyzována třída, která využívá třídu, jež bude teprve dekompilována. Příkladem může být dekompilování souboru s kódem uvedeným výše jako prvního a následně dekompilací java/lang/String. Dekompilací prvního souboru tak vznikne datový typ String a později je při dekompilaci třídy String vytvořen vrchol String znovu. Proto je potřeba před každým vytvořením uzlu popisující libovolnou třídu (resp rozhraní, výčet prvků, generický typ nebo datový typ) vyhledat v databázi, zda již neexistuje vrchol Datový typ s totožným názvem. Jestliže je takový vrchol nalezen, je nutno veškeré vztahy překopírovat do nově vytvářeného vrcholu. Tímto bude zachována informace o použití této třídy jinými třídami či metodami.

Překopírováním vztahů může nastat situace, kdy první třída nejenže String využívá, ale dokonce používá některou z jejích metod. Potom by se vytvořil vrchol Datový typ se vztahem have_method. Tato metoda však bude popsána neúplým množstvím informací, protože jsme doposud více informací o dané metodě nezískali. Při dekompilaci java/lang/String se následně překopírují všechny vztahy včetně vztahu s metodou, kterou však budeme záhy vytvářet znovu. Zde je tedy potřeba také vyhledávat existenci již vytvářené metody. Java však umožňuje přetěžování funkcí a tedy nemůžeme vyhledávat pouze na základě názvu funkce. Zajímá nás tedy také počet a datový typ parametrů. Při porovnávání generických datových typů stačí porovnat hlavní typ a generické parametry ignorovat, neboť v tomto java kompilátory nedělají rozdíl.


Uložení generických typů do grafu

Je potřeba aby se generický typ choval jako obyčejný typ nebo třída kvůli dotazování. Přesto musí poskytovat navíc informace o hlavním typu a generických parametrech.

Využitý obsah ve vrcholu reprezentujícím generický typ

Vlastnosti:
  • nic
Vztahy:
  •  main_type (Třída)
  • generic_parameter (Třída)

1. Příklad uložení následujícího kódu do grafu

1
2
3
public List<String>  some_method(){
   ...
}



Graf tak obsahuje vrchol zastupující metodu se jménem some_method. Tato metoda má návratovou hodnotu List<String>, což je generický typ. Návratová hodnota je popsán vztahem is_type s uzlem "Generický typ", který je dále popsán vztahy main_type a generic_parameter.

2. Příklad uložení následujícího kódu do grafu

1
2
3
public class MapExample {
        Map<Object,String> mp;
}




Na tomto příkladu je demonstrováno uložení v případě většího počtu generických parametrů. Jediný rozdíl je tak v tom, že uzel Generický typ má další vztah generic_parameter.
Pořadí generických parametrů nás v tomto případě příliš nezajímá, proto se tato informace neukládá.


3. Příklad uložení následujícího kódu do grafu

1
2
3
public List<List<String>> creazyMethod(){
  ...
}



V případě, že bude generickým parametrem opět generický typ, je potřeba mít možnost místo konkrétního typu navázat na vztah generic_parameter další uzel Generický typ.

neděle 8. března 2015

Antlr - vygenerování potřebných souborů

Prerekvizity

Za prvé je potřeba mít vytvořený soubor s gramatikou, která bude mít koncovku .g nebo .g4. V našem příadě to bude soubor ASTquery.g. Pro začátek bude mít soubor následující obsah (obsah jenom pro otestování vygenerování):

grammar ASTquery;
r  : 'hello' ID ;// match keyword hello followed by an identifier
ID : [a-z]+ ;    // match lower-case identifiers
WS : [ \t\r\n]+ -> skip; // skip spaces, tabs, newlines


Další nezbytnou součástí je samozřejmě antlr, který je možné stáhnout z na adrese http://www.antlr.org/download.html (Complete ANTLR 4.5 Java binaries jar).

Vytvoření potřebných tříd z gramatiky.

Jestliže máme soubor s gramatikou (ASTquery.g) a antlr (antlr-4.5-complete.jar) v jedné složce můžeme spustit následující příkaz pro vygenerovánní tříd zpracovávající gramatiku:

java -classpath antlr-4.5-complete.jar org.antlr.v4.Tool ASTquery.g

budou vygenerovány soubory:
  ASTqueryParser.java
  ASTqueryLexer.java
  ASTquery.tokens
  ASTqueryBaseListener.java
  ASTqueryLexer.tokens
  ASTqueryListener.java

Testování gramatiky

1) Kompilace souborů

javac -cp antlr-4.5-complete.jar *.java

2) Spuštění

java -cp antlr-4.5-complete.jar:. org.antlr.v4.runtime.misc.TestRig ASTquery -r -tree

po tomto příkazu bude terminál očekávat zápis v zadané gramatice. Ukončení vstupu provedeme stiskem Ctrl+D a výstupem získáme syntaktický strom.

Spuštěním bez parametrů získáme nápovědu testovacího programu
$ java -cp antlr-4.5-complete.jar:. org.antlr.v4.runtime.misc.TestRig ASTquery
java org.antlr.v4.runtime.misc.TestRig GrammarName startRuleName
  [-tokens] [-tree] [-gui] [-ps file.ps] [-encoding encodingname]
  [-trace] [-diagnostics] [-SLL]
  [input-filename(s)]
Use startRuleName='tokens' if GrammarName is a lexer grammar.
Omitting input-filename makes rig read from stdin.


Zdroje:
https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Getting+Started+with+ANTLR+v4
http://www.antlr.org/download.html


čtvrtek 5. března 2015

Příklady AST dotazovacího jazyka

Nastavené aliasy/zkratky

Klasický zápisZkratkaZkratka
class[@name=“jmeno.elementu“]class[jmeno.elementu] stejně lze zkrátit zápis pro libovolný typ vrcholu
jmeno.vrcholu/>e or jmeno.vrcholu !jmeno.vrcholu
class/extends class/>extends nebo class/>e lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/extended class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/implements class/>implements nebo class/>i lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/implemented_by class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/uses class/>uses nebo class/>u lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/used_by class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/calls method/>call nebo method/>c lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/called_by method/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/type method/>type nebo method/>t lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/typed_by method/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/have_anonym class/>anonym lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/is_anonym class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/have_inner class/>inner lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/is_inner class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/have_member class/>member lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/is_member class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/have_method class/>method nebo class/>m lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/is_method class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/have_parameter method/>parameter nebo method/>p lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
method/is_parameter method/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
field/main_type field/>main_type lze použít pro uzly pole a generického typu
field/main_typed_by field/lze použít pro uzly pole a generického typu
generic type/have_generic_parameter generic type/>generic_parameter lze použít pouze pro uzly generického typu
generic type/is_generic_parameter generic type/lze použít pouze pro uzly generického typu
class/annotated class/>annotated nebo class/>a lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
class/annotated_by class/lze použít pro všechny typy vrcholů, kde je tento vztah relevantní
annotation/have_element annotation/>element lze použít pouze pro vrchol anotace
annotation/is_element_by annotation/lze použít pouze pro vrchol anotace
method/throws method/>throws lze použít pouze pro vrchol metoda
method/throws_by method/lze použít pouze pro vrchol metoda
method/call_throws method/>call_throws lze použít pouze pro vrchol metoda
method/call_throws_by method/lze použít pouze pro vrchol metoda
method/catch method/>catch lze použít pouze pro vrchol metoda
method/catch_by method/lze použít pouze pro vrchol metoda
value/is_value value/>value lze použít pouze pro vrchol hodnota
value/value_by value/lze použít pouze pro vrchol hodnota

Classes importing/extending class C.
   class[C]/<u union !C
   class[C]/<uses union !C

Interfaces extending interface I.
   !I

Classes implemeting interface I.
   interface[I]/<i
   interface[I]/<implemented

Classes calling a method of interface I.
   interface[I]/>m/<c/<m
   interface[I]/>method/<call/<method

Classes calling a method of interface which extends interface I.
   interface[>extend[I]]/>m/<c/<m
   interface[>extend[I]]/>method/<call/<method

Classes calling a method of given name of interface which extends interface I with given parameters.
   interface[>e[I]]/>m[name and >p/>t[par]]/<c/<m
   interface[>extend[I]]/>method[name AND >parameter/>type[par]]/<call/<method

Classes calling a method which implements interface I, and it is annotated with annotation @A.
   interface[I]/<i/>m[>annotated[A]]/<c/<m
   interface[I]/<implements/>method[>annotated[A]]/<call/<method

Classes calling a method which implements interface I, and it is annotated with annotation @A with parameters @A(foo="bar")
   interface[I]/<i/>m[>annotated[A]/>element[@value="bar"]/<value[foo]]/<c/<m
   interface[I]/<implements/>method[>annotated[A]/>element[@value="bar"]/<value[foo]]/<call/<method
nebo
   interface[I]/<i/>m[>annotated[A]/>element[foo and @value="bar"]]/<c/<m
   interface[I]/<implements/>method[>annotated[A]/>element[foo and @value="bar"]]/<call/<method

Classes annotated with annotation A
   class[>annotated[A]]

Classes importing a subclass of class B.
   !B/<u
   !B/<uses

Classes importing a subclass of class which implements subinterface of interface I.
   !I/<i/<e/<u
   !I/<implement/<extend/<uses

Classes contain method with name foo(string,int)
   class[>m[foo and >p[@position="1"]/>t[String] and >p[@position="2"]/>t[int]]]

Classes callmethod foo(int,string) of class C
   class[C]/>m[foo and >p[@position="2"]/>t[String] and >p[@position="1"]/>t[int]]/<c