Home

The GrGen User Manual

1. Declares NodeType and subtypes of NodeType as group node type All the differently typed nodes that point to a node of type NodeType i e there is a directed edge between such nodes will be grouped and visibly enclosed by the NodeType node GroupMode is one of no incoming outgoing any hidden causes hiding of the edges by which grouping happens The EdgeType constrains the type of the edges which cause grouping the with clause addi tionally constrains the type of the adjacent node only excludes subtypes Only apply group commands on a graph if they indeed lead to a containment tree of groups If the group commands would lead to a directed acyclic or even cyclic containment graph the results are undefined You may get duplicate edges and nodes the implementation is free to choose indeterministically between the possible nestings it may even grow an arm and stab you in your back A conflict resultion heuristic used is to give the earlier executed add group command priority But this mechanism is incomplete you d better refine your groups or change the model in that case Using a model separating edges denoting direct containment from cross linking edges by type is normally the better design even disregarding visual node nesting The following example shows metropolis ungrouped and grouped Frankfurt metropolis N 2 Edge S1 Edge Pi a A A Pd FA y AS_south highway 7 AS_north
2. empty gt sA_O new sA_O moveLeft gt sB new sA_1 WriteOne new sA one gt sA_1 new sA_1 moveLeft gt sD new sB_0 WriteOne new sB empty gt sB_0 new sB_0 moveRight gt sC new sB_1 WriteEmpty new sB one gt sB_1 new sB_1 moveRight gt sE new sC_0 WriteEmpty new sC empty gt sC_0 new sC_0 moveLeft gt sA new sC_1 WriteEmpty new sC one gt sC_1 new sC_1 moveRight gt sB new sD_O WriteOne new sD empty gt sD_0 new sD_O moveLeft gt sE new sD_1 WriteOne new sD one gt sD_1 new sD_1 moveLeft gt sH new sE_0 WriteOne new sE empty gt sE_0 new sE_0 moveRight gt sC new sE_1 WriteOne Examples 9 2 Busy Beaver 125 s lnew sE one gt sE_1 62 new sE_1 moveLeft gt sC Our busy beaver looks like this 0 empty 1 RWHead 6 0ne Astate lt D move Left 3 empty 4 move Left Y ES 10 moveRight 18 move Left 18 empty 1B one 13 moveLeft 16 moveLeft 12 empty We have an initial host graph now The graph rewrite sequence is quite straight forward and generic to the Turing graph model Note that for each state the Empty One selection is unambiguous xgrs readOneRule readEmptyRule writeOneRule writeEmptyRule amp ensureMoveLeftValidRule ensureMoveRightValidRule amp moveLeftRule moveRightRule 32 We interrupt the machine after 32 iterations and look at the result
3. Modelldent Typeldent NodeType Edge Type These are semantic specializations of Ident Typeldent matches every type identifier i e a node type an edge type an enumeration type or a primitive type All the type identifiers are actually type expressions See Section 6 9 for the use of type expressions 4 1 1 Graphlets Graphlet GraphletNode sa Continuation A graphlet specifies a connected subgraph GRGEN NET provides graphlets as a descriptive notation to define both patterns to search for as well as the subgraphs that replace or modify matched spots in a host graph Any graph can be specified piecewise by a set of graphlets In Example 4 line 7 the statement n1 gt n2 is the node identifier n1 followed by the continuation graphlet gt n2 All the graph elements of a graphlet have names The name is either user assigned or a unique internal non accessible name In the second case the graph element is called anony mous For illustration purposes we use a lt number gt notation to denote anonymous graph elements in this document For example the graphlet n1 gt n2 contains an anonymous edge thus can be understood as n1 1 Edge gt n2 Names must not be redefined once defined a name is bound to a graph element We use the term binding of names because a name not only denotes a graph element of a graphlet but also denotes the mapping of the abstract graph element of a graphlet to a concrete g
4. The initial breakpoint and choicepoint assignment is given with the characters in the sequences after the debug xgrs commands in the grs file The breakpoint and choicepoint commands of the debugger allow to toggle them at runtime overriding the initial assignment notationally yielding a sequence with added or removed characters The user input commands type define choice points which can t be toggled off s tep Execute the current rewrite rule match and rewrite in case it matched the resulting graph is shown d etailed step Execute the current rewrite rule in a three step procedure matching highlighting the found match rewriting highlighting the changing elements and doing the rewrite showing the result ing graph In addtion afterwards the execution of subrules from embedded xgrs exec is shown step by step step o ut Continue execution until the end of the current loop If the ex ecution is not in a loop at this moment the complete sequence will be executed step u p Ascend one level up within the Kantorowitsch tree of the current rewrite sequence i e rule see Example 55 n ext Go to the next rewrite rule which matches make it current toggle b reakpoint Toggle a breakpoint at one of the breakpointable locations toggle c choicepoint Toggle a choicepoint at one of the choicepointable locations r un Continue execution until the end or a breakpoint a bort Cancel the execution immediat
5. You can check the result of your build with the test suite we use to check against regres sions It is split into syntactic tests in frontend test checking that example model and rule files can get compiled by grgen or not compiled or only compiled emitting warnings and 10 5 A very short tour of the code 133 the resulting code can get compiled by csc The tests get executed by calling test sh or testpar sh from bash or cygwin bash testpar sh executes them in parallel speeding up execution on multi core systems considerably at the price of potential false positive reports deviations from a gold standard are reported And semantic tests in engine net 2 tests checking that executing example shell scripts on example models and rules yields the expected results They get executed by calling test sh You must check that all tests are reported as Success 10 5 A very short tour of the code The frontend is spread over the directories parser ast ir be and util with their code being used from Main java The directory parser contains parser helpers like the symbol table and scopes and within the antlr subdirectory the ANTLR parser grammar of GRGEN NET in the file Grgen g The semantic actions of the parser build an abstract syntax tree consisting of instances of a multiple classes as given in the directory ast with the base class BaseNode The AST is operated upon in three passes first resolving by resolve and resolveLocal mainly re
6. formation Volume 3 1999 H Marxen and J Buntrock Old list of record TMs http www drb insel de heiner BB index html 8 2000 Microsoft NET aa497336 aspx 2007 http msdn2 microsoft com de de netframework Andrew B Mickel James F Miner Kathleen Jensen and Niklaus Wirth Pascal user manual and report 4th ed ISO Pascal standard Springer Verlag New York Inc New York NY USA 1991 Ulrich Nickel J rg Niere and Albert Z ndorf The FUJABA environment In ICSE 00 Proceedings of the 22nd international conference on Software engineer ing pages 742 745 2000 Detlef Plump The Graph Programming Language GP In Proc Algebraic Informatics CAI 2009 pages 99 122 2009 Arend Rensink The GROOVE Simulator A Tool for State Space Generation Applications of Graph Transformation with Industrial Relevance AGTIVE 03 Proceedings 2004 G Rozenberg editor Handbook of Graph Grammars and Computing by Graph Transformation World Scientific 1999 Arend Rensink and Pieter Van Gorp Graph based tools The contest Proceed ings 4th Int Conf on Graph Transformation ICGT 08 2008 Herbert Schildt American National Standards Institute International Organiza tion for Standardization International Electrotechnical Commission and ISO IEC JTC 1 The annotated ANSI C standard American National Standard for Programming Languages C ANSI ISO 9899 1990 1990 Georg Sander VCG Visualization of
7. 5 matching strategies 10 modifier 42 modify mode 39 multiplicity see connection assertion NAC see negative application condition name 28 38 104 negative application condition 50 nested pattern rewrite 60 nested transaction see transaction Node 24 node graphlet 29 node type 24 non determinism 36 object 69 one of set braces 88 order of precedence 71 73 76 81 organic see layout algorithm orthogonal see layout algorithm overview system 4 PAC see positive application condition parameter 33 112 116 pattern 36 pattern cardinality 52 53 pattern graph 5 28 pattern modifiers 42 persistent graph 99 persistent name 87 96 106 positive application condition 52 pragma see annotation precedence see order of precedence preservation 38 preservation morphism 5 38 primitive types 69 prio 46 quickstart 13 rail diagram 19 random match selector 86 random all of operators 88 10 5 A very short tour of the code re evaluation see attribute evaluation recursive pattern 57 redefine 28 redirecting 30 regular expression syntax 66 85 replace mode 39 replacement graph 5 28 38 return type 33 return value 37 retype 29 retyping 45 rewrite rule 4 33 RHS see right hand side right hand side 5 38 rule application see application rule application language 83 rule modifiers 42 rule set 27 31 112 rule set language 27 r
8. B iff A is greater than or equal B Table 6 5 Compare operators on arithmetic expressions iff A and B are identical iff A and B are not identical iff A is a subset map of B but A and B are not identical iff A is a superset map of B but A and B are not identical iff A is a subset map of B or A and B are identical iff A is a superset map of B or A and B are identical Table 6 6 Compare operators on set map expressions A lt Bcorresponds to the direction of the arrow in an UML class diagram Node and Edge are the least specific thus bottom elements of the type hierarchy i e the following holds e Vn Types Node Node lt n e Ve Types Edge Edge lt e 6 5 Arithmetic and Bitwise Expressions The arithmetic and bitwise expressions combinde integer and floating point values with the arithmetic operations usually available in programming languages and integer values with bitwise logical operations interpreting integer values as bit vectors True iff A and B are identical Different types in a type hierarchy are not identical True iff A and B are not identical True iff A is a supertype of B but A and B are not identical True iff A is a subtype of B but A and B are not identical True iff A is a supertype of B or A and B are identical True iff A is a subtype of B or A and B are identical Table 6 7 Compare operators on type expressions 6 5 Arithmetic and Bitwise Expre
9. Type constraints are allowed in the pattern part only Retyping is allowed in the replace modify part only Graphlet Meaning x NodeType The name x is bound to a node of type NodeType or one of its subtypes NodeType 1 NodeType S 1 Node n The node x is bound to GraphletEdge eS OP O EdgeRefinement 30 Rule Set Language EdgeRefinement A GraphletEdge specifies an edge Anonymous edges are specified by an empty Edgeke finement clause i e gt lt lt gt or T gt lt T for an edge type T respectively A non empty EdgeRefinement clause allows for detailed edge type specification Type constraints are allowed in the pattern part only see Section 4 6 TypeConstraint Retyping is allowed in the replace modify part only see Section 4 8 Retyping The different kind of arrow tips distinguish between directed undirected and arbitrary edges see also Section 3 1 1 The arrows gt and lt are used for directed edges with a defined source and target The arrow is used for undirected edges The pattern part allows for further arrow tips namely for arbitrary edges and lt gt for directed edges with undefined direction Note that lt gt is not equivalent to the gt lt statements In order to produce a match for the arrow lt gt it is sufficient that one of the statements gt lt matches If an edge type is spec
10. home profile file export PATH opt grgen bin PATH Furthermore we create a directory for our GRGEN NET data for instance by mkdir home grgen If you re using Microsoft Windows Extract the zip archive to a directory of your choice and add the bin subdirectory to your search path via control panel system properties environment variables Execute the GRGEN NET assemblies from a command line window Start gt Run cmd For MS NET the mono prefix is neither applicable nor needed You might be interested in the syntax highlighting specifications of the GRGEN NET languages supplied for the vim and Notepad editors in the syntaxhighlighting sub directory 13 14 Quickstart 2 2 Creating a Graph Model In the directory home grgen we create a text file StateMachine gm that contains the graph meta model for our state machine By graph meta model we mean a set of node types and edge types which are available for building state machine graphs see Chapter 3 Figure 2 1 shows the meta model What have we done You can see two base types State for node class State id int abstract node class SpecialState extends State node class StartState extends SpecialState node class FinalState extends SpecialState node class StartFinalState extends StartState FinalState oO oo ND a FF OU N e edge class Transition Trigger string e e N e oO e e O const edge class EpsilonTran
11. which of them will be deleted and which graph elements have to be newly created 4 4 1 Implicit Definition of the Preservation Morphism r In theory the transformation specification is done by defining the preservation morphism r In GRGEN NET the preservation morphism r is defined implicitly by using names both in Pattern Graph Rewrite Graph Preservation Morphism r L oo R Rul Match m H _ H Rule Application Host Graph Result Graph Figure 4 1 Process of Graph Transformation pattern graphlets and replace graphlets Remember that to each of the graph elements a name is bound to either user defined or internally defined If such a name is used in a replace graphlet the denoted graph element will be kept Otherwise the graph element will be deleted By defining a name in a replace graphlet a corresponding graph element will be newly created So in a replace pattern anonymous graph elements will always be created Using a name multiple times has the same effect as a single using occurrence In case of a conflict between deletion and preservation deletion is prioritized If an incident node of an edge gets deleted the edge will be deleted as well in compliance to the SPO semantics 4 4 Replace Modify Part 39 Pattern LHS Replace RHS r L R Meaning zT x r ulbs x gt rhs Preservation AT lhs x E def r Deletion zT rhs x ran r Creation xT iT Illegal redefinition of x e T
12. 3 alternative a feature of the class is either 4 5 FeatureMethod 1 a method 6 c gt Method 7 8 FeatureVariable or a variable 9 c gt Variable 10 11 FeatureConstant 1 or a constant 12 c gt Constant test variableMaybeInitialized aN 3 v Variable match variable 4 alternative and an initialization with a different one if available 5 Empty 6 the empty pattern matches always 7 negative so prevent it to match if initialization is available 8 v lt otherV Variable 9 Initialized initialization v lt otherV Variable Rh a e e HM BB wo NN pa al 5 5 Subpattern Declaration and Subpattern Entity Declaration Subpatterns were introduced to factor out a common recurring pattern a shape into a named subpattern type ready to be reused at points the pattern should get matched T he common recurring pattern is specified in a subpattern declaration and used by a subpattern entity declaration 96 Nested and Subpatterns SubpatternDeclaration D Sipaiermbody HO SubpatternBody i PatternStatement B E SubpatternRewriting y Subpattern declarations define a subpattern type denoting the specified shape in global namespace the parameters specify some context elements the pattern may refer to but which are not part of the pattern itself So they are only syntactically the same as test rule parameters which are members of
13. 6 10 Binary set operators in ascending order of precedence The binary set operators require the left and right operands to be of identical type set lt T gt The operator x in s denotes set membership x s returning whether the set contains the given element as boolean Furthermore there are two operations on sets available in method call notation MethodSelector size returns the number of elements in the set as int peek num returns the element which comes at position num int in the sequence of enumeration as T for set lt T gt The declarative rule language comes without the imperative set s add x or s rem x meth ods known from the XGRS to add a value to a set use set union with a single valued set constructor to remove a value from a set use set difference with a single valued set constructor for set constructors cf 6 10 ils 4 foo JO Used in this way they get internally optimized to set addition and removal 6 8 Map Expression Map expressions consist of the known mathematical set operations extended to maps plus map value lookup and size counting 76 Types and Expressions Expr Ga MapExpr Map union returns new map with elements which are in at least one of the maps with the value of map2 taking precedence Map intersection returns new map with elements which are in both maps with the value of map2 taking precedence Map difference returns new map with el
14. AB I 11C BC 126 CA 127 AB 128 BC PY 12 CA A 132 CA _ 133 AB 134 BC gt 13 AB 13E CA 13F AB Calo en Figure 9 1 Sierpinski triangle ANDO yComp Version 1 3 1 File Edit View Navigate Layout Help n STE Edge 50 Edge l ICESGL den Speer S7O EdgeScer S4C Edgel SHE Eigel IAEA gigas 20 EdgeSce Root gt 0 Node1 gt 10 Node gt 16 Nodel 17 Node gt 18 Node 1 Nodel 21 Nodel 22 Node ia 23 Node 26 EG gt 29 Nodel 2 Nodel _ 2A Node gt 2B Node gt 31 Nodel gt 32 Node la 33 Node OE gt 39 Nodel ne Tresen S26 Egel Be Lu j siede lla 3A Node HER s sl _ 3B Node cd 41 Nodel 56 Edge 6 HAZ hipo S IFES gessen 60 Edge S45 Edat S2E Edget SSC Edgel SSOE does SF Edel PUT a Figure 9 2 Koch snowflake oO 0 nn 0 pp W WD O 9 2 Busy Beaver 121 9 2 Busy Beaver We want GRGEN NET to work as hard as a busy beaver Kro07 Dew84 Our busy beaver is a Turing machine that has got five states plus a halt state it writes 1 471 bars onto the tape and terminates MBOO So first of all we design a Turing machine as graph model Besides this example shows that GRGEN NET is Turing complete We use the graph model and the rewrite rules to define a general Turing machine Our approach is to basically draw the machine as a graph The busy beaver logic is implemented by rule applica
15. AttributeOverwrite Attribute Type V PrimitiveType T EnumType GenericType AttributeOverwrite Ten JO presion Defines a node or edge attribute Possible types are enumeration types enum and primitive types or generic types See Section 6 1 for a list of built in primitive and generic types Optionally attributes may be initialized with a constant expression The expression has to be of a compatible type of the declared attribute See Chapter 6 for the GRGEN NE T types and expressions reference The AttributeOverwrite clause lets you overwrite initialization values for attributes of super classes The initialization values are evaluated in the order as they appear in the rule set file The following attribute declarations are illegal because of the order of evaluation of initial ization values CHAPTER 4 RULE SET LANGUAGE 1 The rule set language forms the core of GRGEN NET Rule files refer to zero or more graph models and specify a set of rewrite rules The rule language covers the pattern specification and the replace modify specification Attributes of graph elements can be re evaluated during an application of a rule The following rewrite rule mentioned in Gei et al GBG 06 gives a rough picture of the language 1 3 using SomeModel rule SomeRule n1 NodeTypeA n2 NodeTypeA hom n1 n2 il LS n3 NodeTypeB negative n3 el EdgeTypeA gt n1 if In3 al 424n2 a1 negativ
16. Compiler Graphs User Documentation v 1 30 Technical report Universitat des Saarlandes 1995 Jochen Schimmel Tom Gelhausen and Christoph A Schaefer Gene Expression with General Purpose Graph Rewriting Systems In Proceedings of the 8th GT VMT Workshop 2009 A Schurr A Winter and A Z ndorf Progres Language and environment In G Rozenberg editor Handbook on Graph Grammars volume Applications Vol 2 pages 487 550 World Scientific 1999 Adam M Szalkowski Negative Anwendungsbedingungen f r das suchpro srammbasierte Backend von GrGen 2005 Studienarbeit Universitat Karlsruhe The Mono Team Mono http www mono project com 2007 Martin Trapp Gotz Lindenmaier and Boris Boesler Documentation of the intermediate representation firm Technical Report 1999 14 Universitat Karl sruhe Fakultat fur Informatik Dec 1999 Daniel Varr and Andras Balogh The Model Transformation Language of the VIATRA2 Framework Science of Computer Programming 68 3 214 234 2007 138 VHVOS vsvos IV VFO06 WKRO2 ly Wo07 Application Programming Interface Gergely Varr Akos Horvath and Daniel Varr Recursive Graph Pattern Matching In Applications of Graph Transformations with Industrial Relevance pages 456 470 2008 G Varr A Schurr and D Varr Benchmarking for Graph Transformation Technical report Department of Computer Science and Information Theory Budapest University of Tec
17. NamedGraph which is a wrapper for the LGSPGraph behind it exposed via the IGraph interface of libGr If you don t need the persistent names get rid of them by casting to the named graph getting the wrapped graph and forgetting any 10 3 Import Export and miscellaneous stuff 131 references to the named graph If you want to keep it you should get the wrapped graph casting it to LGSPGraph and set its property NamedGraph to the named graph this will cause the nameof operator to work as known i e as if using GrShell which employs named graphs Please be aware that naming is rather expensive A named graph supplying the name to element and element to name mappings normally uses up about the same amount of memory as the wrapped LGSPGraph defining the real graph There are further examples available in the examples api folder of the GRGEN NET distribution e How to use the graph rewrite sequences offered by the libGr on API level is shown in examples api BusyBeaverExample BusyBeaverExample cs But normally you want to use your favourite NET programming language for control together with the type safe interface when working on API level e How to use the old and new interface for accessing a match on API level is shown in examples api ProgramGraphsExample ProgramGraphsExample cs e How to use the visited flags on API level is shown in examples api VisitedExample VisitedExample cs e How to analyze the graph and generate hopefully b
18. RootNamespace now it is ensured that y must be different from x I o gt W Wd Btw the x is not a special construct it s a normal graphlet cf 4 1 1 If there are several patterns which should not occur use several negatives If there are exceptions to the forbidden pattern use nested negatives As a straight forward generaliza tion of negatives within positive patterns negatives may get nested to an arbitrary depth Matching of the nested negative pattern causes the matching of the nesting pattern to fail A fabricated example using parallel as well as nested negatives test only neChildOrAllChildrenHaveExactly neCommonChild root Class negative root extending gt Class root does not extend another class root lt extending c1 Class a class c1 extends root negative ele root lt extending c2 Class there is no c2 which extends root negative c1 lt extending child Class extending gt c2 except c1 and c2 have a common child negative and cl has no further children child cl lt extending Class negative and c2 has no further children child c2 lt extending Class oO 0 NOD on FF W N Hr N N N N Rh Be Be RR RR a mE Be pp CIL O ICC COI II SS E A O 52 Nested and Subpatterns 5 2 Positive Application Condition PAC PositiveA pplicationCondition PatternStatement With positive application conditions keyword independent we can s
19. a Assign IteratedPath a Rh e Pp wo N e ds 5 5 Subpattern Declaration and Subpattern Entity Declaration 59 rule removeMiddleAssignment al Assign gt a2 Assign gt a3 Assign independent IteratedPath a1 a3 J replace al a3 oO a JD 0 PR QQ N Hr J Rh e e N e O pattern IteratedPath begin Assign end Assign alternative an iterated path from begin to end is either Found the begin assignment directly linked to the end assignment base case begin gt end Further or an iterated path from the node after begin to end recursive case begin gt intermediate Assign IteratedPath intermediate end II O a a A Y 0 0 IS A E9 This is once more a fabricated example for an iterated path from a source node to a distinc tive target node and an example for the interplay of subpatterns and positive application conditions to chech complex conditions independent from the pattern already matched Here three nodes a1 a2 a3 of type Assign forming a list connected by edges are searched and if found a2 gets deleted but only if there is an iterated path of directed edges from al to a3 The path may contain the host graph node matched to a2 again Without the independent this would not be possible as all pattern elements including the ones originating from sub patterns get matched isomorphically The same path specified in the pattern of the rule not
20. a transaction rollback thus saving one from debugging problems due to zombie elements you may use the def O operator to check during execution if this happened Sequence local variables are typed so type errors are caught at compile time parsing time for the interpreted sequences an assignment of an untyped variable to a typed variable is checked at runtime They belong to the sequence they appear in their life ends when the sequence finishes execution so there is no persistency available for them as for the graph global variables neither do they get nulled on element deletion as the graph does not know about them If used in some rule i e within an exec named graph elements of the enclosing rule are available as read only variables Note that we have two kinds of return values in graph rewrite sequences Every rewrite sequence returns a boolean value indicating whether the rewriting could be successfully processed i e denoting success or failure Additionally rules may return graph elements These return values can be assigned to variables on the fly see example 47 83 84 Rule application control language XGRS The graph rewrite sequence la b c R x y z is valid It assigns returned graph elements from rule R to variables b and c and the infor mation whether R mached or not to variable a 7 1 Logical connectives rewrite sequence RewriteSequence RewriteNeg Term Rewri
21. and Subpatterns N oa a A O N e EXAMPLE 28 test variableMaybelnitialized v Variable match variable optional and an initialization with a different one if available v lt otherV Variable Pattern cardinality constructs are match rewrite all enumeration blockers For every pattern instance the iterated yields only one match even ifin all mode used in from all bracketed rules 5 4 Alternative Patterns AlternativePatterns O With the alternative block you can specify several nested alternative patterns One of them must get matched for the matching of the alternative and thus its directly nesting pattern to succeed and only one of them is matched per match of the alternative overall pattern The order of matching the alternative patterns is unspecified especially it is not guaranteed that a case gets matched before the case textually following if you want to ensure that a case cannot get matched if another case could be matched you must explicitely prevent that from happening by adding negatives to the cases In contrast to the iterated which locally matches everything available and inserts this combined match into the current match the alternative decides for one case match which it inserts into the current match tree ignoring other possible matches by other cases 5 5 Subpattern Declaration and Subpattern Entity Declaration 55 1 test feature c Class 2
22. and per node of TargetNodeType or a subtype it is counted how often it was covered by a match of the pattern ending at it The numbers must be in the range specified at the SourceNodeType and the TargetNodeType for the connection assertion to be fulfilled Giving no multiplicity constraint is equivalent to i e 0 o i e unconstrained Please take care of non disjoint source target types subtypes in the case of undirected and especially arbitrary edges In the case of multiple connection assertions all are checked and errors for each one reported for strict validation to succeed at least one of them must match It might happen that none of the connection assertions of an EdgeType are matching an edge of this type in the graph This is accepted in the case of normal validation throwing connection assertions without multiplicities effectively back to nops but as you normally want to see only the specified connections occuring in the graph there is the additional mode of strict validation if an edge is not covered by a single matching connection validation fails Furtheron there is the strict only specified mode which only does strict validation of the edges for which connection assertions are given See Section 8 2 2 validate for an example The arrow syntax is based on the GRGEN NET graphlet specification see Section 4 1 1 The different kinds of arrows distinguish between directed undirected and arbitrary edges The gt arrow me
23. by grgen exe which only calls the grgen jar of the frontend You may call the Java archive on your own to get a visualization of the model and rewrite rules from a vcg dump of the IR cf Note2 The real matcher code is generated by the backend given in engine net 2 in the src lgspBackend subdirectory The processing is done in several passes in 1gspMatcher Generator cs the base data structure is the PatternGraph resp the nesting of the PatternGraph objects contained in the RulePattern objects of the rules tests or the Matching Pattern objects of the subpatterns First a PlanGraph is created from the PatternGraph and data from analysing the host graph for generating the initial matcher some default data given from the frontend is used A mimimum spanning arborescent is searched defin ing a hopefully optimal set of operations for matching the pattern the hopes are founded see BKG08 A SearchPlanGraph is built from the arborescent marked in the PlanGraph and used thereafter for scheduling the operations into a ScheduledSearchPlan Out of the ScheduledSearchPlan a SearchProgran is built by the SearchProgramBuilder in a further pass the SearchProgram is completed by the SearchProgramCompleter before the C code gets finally generated by calling the emit methods of the SearchProgram The compiled graph rewrite sequences are handled by the lgspSequenceChecker and lgspSequenceGenerator together with the sequence parser from the
24. compile the model and rule set files So execute in GRGEN NE T s bin directory GrGen exe specs sierpinski grg GrGen exe specs snowflake grg or mono GrGen exe specs sierpinski grg mono GrGen exe specs snowflake grg respectively If you are on a Unix like system you have to adjust the path separators of the GRSHELL scripts Just edit the first three lines of test Sierpinski grs and test Snowflake grs And as we have the file Sierpinski grs already opened we can increase the number of iterations to get even more beautiful graphs Just follow the com ments Be careful when increasing the number of iterations of Koch s snowflake yCOMP s layout algorithm might need some time and attempts to layout it nicely We execute the Sierpinski script by GrShell exe test Sierpinski grs or mono GrShell exe test Sierpinski grs respectively Because both of the scripts are using the debug mode we complete execution by typing r un See Section 8 2 8 for further information The resulting graphs should look like Figures 9 1 and 9 2 Be careful The running time increases exponentially in the number of iterations 119 120 Examples 606 yComp Version 1 3 1 File Edit View Navigate Layout Help Fie ee feud A A on da Por EA x ry FR fees Ar ER 1 i gt A PR nm NR au PAR ABLA AR E Find Root gt 0 B 102 CA 103 AB gt 104 BC 10E CA 10F AB 110 BC I 11A CA 11B
25. dpo and by O n for induced respectively where n is the number of specified nodes 4 6 Static Type Constraint Node edge declaration with type constraint 4 6 Static Type Constraint 43 Modifier Meaning dpo Switches to DPO semantics This modifier affects only nodes that are to be deleted during the rewrite DPO says roughly spoken that implicit deletions must not occur by all means To ensure this the dangling condition see dangling below and the identification condi tion see identification below get enforced i e dpo dangling identification In contrast to exact and induced this modi fier applies neither to a pattern as such can t be used with a test nor to a single statement but only to an entire rule See Corradini et al CMR 99 for a DPO reference dangling Ensures the dangling condition T his modifier aftects only nodes that are to be deleted during the rewrite Nodes going to be deleted due to the rewrite part have to be specified exactly with all their incident edges exact semantics in order to be matched As with dpo this modifier applies only to rules identification Ensures the identification condition This modifier affects only nodes that are to be deleted during the rewrite If you specify two pattern graph elements to be homomorphically matched but only one of them is subject to deletion during rewrite those pattern graph elements will never actually be matched to the same host graph e
26. e if s is successful t will not be executed Execute s then t Success if s and t succeeded The same ass amp t but with lazy evaluation i e if s fails t will not be executed Execute s then t Success if s or t succeeded but not both Execute r If r succeeded execute s and return the result of s Otherwise execute t and return the result of t Same as if r s true Execute s transactionally rollback on failure Switch the result of s from successful to fail and vice versa Use random instead of left associative execution order for lt op gt Execute s repeatedly as long as its execution does not fail Same ass amp amp sx Execute s repeatedly as long as its execution does not fail but n times at most Same as s n but fails if executed less than m times Same as s but fails if executed less than m times Switches Rule to a test This is the multi purpose flag when accessed from LIBGR Also used for graph dumping and break points Rewrite every pattern match produced by the action Rule Check if all the variables are defined A constant acting as a successful match A constant acting as a failed match Tries to match all contained rules then rewrites one of the rules which matched True if at least one matched Allocates a visited flag returns its id Frees the visited flag given Resets the visited flag given in all graph elements Create storage set and assign to u Add v to storage set u Remove
27. examples For the alternative construct the rewrite is specified directly at every nested pattern i e alternative case as shown in the second of the following two examples the rewrite of the matched case will be applied Nodes and edges from the pattern containing the nested pattern containing the nested rewrite are not available for deletion inside the nested rewrite only the rewrite part of the pattern in which they are declared is allowed to delete them They are available for retyping though but only in case the retyping is unambigous it must be guaranteed that only one retyping can occur So only the rewrites of alternative cases and optional patterns may contain retypings of elements not declared in the alternative case or optional pattern in contrast to iterated and multiple pattern rewrites 5 6 Nested Pattern Rewriting 1 rule methods ji o a N 9 00 A W N e 12 13 14 15 c Class iterated 4 c gt m Method replace E lt 2m replace C o 0 N QA a A W N N ye re e Ra RR RR mE e psp e tk Ca AA a Ss ES Ww A 22 23 24 25 26 2 28 29 30 31 32 rule methodWithTwoOrThreeParameters m Method alternative Two m lt n Name m lt el Edge vi Variable m lt e2 Edge v2 Variable negative vi v2 m lt Variable modify delete el m gt vi delete e2 m gt v2 i Three m lt n Name
28. info uni karlsruhe de software php id 6 2007 Moritz Kroll and Rubino Gei Developing Graph Transformations with Gr Gen NET In Applications of Graph Transformation with Industrial rele VancE AGTIVE 2007 2007 preliminary version submitted to AGTIVE 2007 Ole Kniemeyer and Winfried Kurth The Modelling Platform GroIMP and the Programming Language XL Applications of Graph Transformation with Industrial Relevance AGTIVE 07 Proceedings 2007 Moritz Kroll G GrGen NET in C Master s thesis Universitat Karlsruhe TH Moritz Kroll GrGen NET Portierung und Erweiterung des Grapherset zungssystems GrGen 5 2007 Studienarbeit Universitat Karlsruhe Gotz Lindenmaier libFIRM A Library for Compiler Optimization Research Implementing FIRM Technical Report 2002 5 Universitat Karlsruhe Fakultat fur Informatik Sep 2002 Tiham r Levendovszky L szl Lengyel Gergely Mezei and Hassan Charaf A Systematic Approach to Metamodeling Environments and Model Transforma tion Systems in VMTS In Electronic Notes in Theoretical Computer Science pages 65 75 2005 10 5 A very short tour of the code 137 LMS99 MB00 Mic07 MMJW91 INNZOO PIu09 Ren04 Roz99 RVG08 ISAI 90 San95 SGS09 SWZ99 Sza05 Tea07 ITLB99 VBO07 Litovsky M tivier and Sopena Graph Relabelling Systems and Distributed Algorithms Handbook of Graph Grammars and Computing by Graph Trans
29. language code is illegal node class t_node node class t_node Using an identifier before defining it is allowed Every used identifier has to be defined exactly once 3 2 Type Declarations 21 NodeType EdgeType Enum Type These are semantic specializations of Ident to restrict an identifier to denote a node type an edge type or an enum type respectively 3 1 1 Base Types The GRGEN NET model language has built in types for nodes and edges All nodes have the attribute less built in type Node as their ancestor All edges have the abstract see Section 3 2 attribute less built in type AEdge as their ancestor The AEdge has two non abstract built in children UEdge as base type for undirected edges and Edge as base type for directed edges The direction for AEdge and its anchestors that do not inherit from Edge or UEdge is undefined or arbitrary Because there is the magic of direction linked to the edge base types its recommended to use the keywords directed undirected and arbitrary in order to specify inheritance see Section 3 2 As soon as you decided for directed or undirected edge classes within your type hierarchie you are not able to let anchestor classes inherited from a contradicting base type of course That is no edge may be directed and undirected This is an exception of the concept multi inheritance Figure 3 1 shows the edge type hierarchy user defined arbitrar
30. libGr The src GrGen subdirectory contains the grgen exe compiler driver procedure The src libGr subdirectory contains the libGr offering the base interfaces a user of GRGEN NE T sees on the API level for the model the 134 Application Programming Interface actions the pattern graphs and the host graph They get implemented in code from the lesp backend and in the generated code The libGr further offers a generic name string and object based interface to access the named entities of the generated code In addition it offers the rewrite sequence parser which gets generated out of SequenceParser csc building the rewrite sequence AST from the classes in Sequence cs further utilizing SymbolTable cs The rewrite sequence classes contain a method ApplyImpl IGraph graph which executes them Finally the libGr offers several importers and exporters in the src libGr IO and src libGr GRSImporter subfolders The src GrShell subdirectory contains the GrShell application which builds upon the generic interface as it must be capable of coping with arbitrary used defined models and actions at runtime and the sequence interpretation fa cilities offered by the libGr The command line parser of GrShell gets generated out of GrShell csc the shell implementation is given in GrShellImpl cs Graphical debugging is offered by the Debugger cs together with the YCompClient cs The examples subdirectory of engine net 2 contains a bunch of exampl
31. m lt el Edge v1 Variable m lt e2 Edge v2 Variable m lt e3 Edge v3 Variable modify delete el delete e2 delete e3 modify ne gt wrk m gt v2 MS 61 62 Nested and Subpatterns 1 2 O A NW ow RW 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 This is an example which shows how to decide with an alternative on the target type of a retyping depending on the context rule alternativeRelabeling ik m Method alternative private if m access Access private modify pm PrivateMethod lt m gt static negative MISS C modify sm StaticMethod lt m gt modify 5 7 Subpattern rewriting Alongside the separation into subpattern declaration and subpattern entity declaration sub pattern rewriting is separated into a nested rewrite specification given within the subpattern declaration defining how the rewrite looks like and a subpattern rewrite application given within the rewrite part of the pattern containing the subpattern entity declaration request ing the rewrite to be actually applied SubpatternRewriting replace J modify The subpattern rewriting specifications within the subpattern declaration looks like a nested rewriting specification but additionally there may be rewrite parameters given in the subpattern header cf 5 5 which can be referenced in the rewrite body Most elements can be handed i
32. non commercial areas You ll find the tools in the bin subdirectory of your GRGEN NET installation 1 7 1 GrGen exe The GrGen exe assembly implements the GRGEN NET generator The GR GEN NET generator parses a rule set and its model files and compiles them into NET assemblies The compiled assemblies form a specific graph rewriting system together with the GRGEN NE T backend Usage mono GrGen exe keep lt dest dir gt use lt existing dir gt debug b lt backend d11 gt o lt output dir gt lt rule set gt rule set is a file containing a rule set specification according to Chapter 4 Usually such a file has the suffix grg The suffix grg may be omitted By default GRGEN NET tries to write the compiled assemblies into the same directory as the rule set file This can be changed by the optional parameter output dir Options 8 Introduction keep Keep the generated C source files If dest dir is omitted a subdirectory tmpgrgenn within the current directory will be created The destination directory contains e printOutput txt a snapshot of stdout during program execution e NameModel cs the C source file s of the rule setModell d11 as sembly e NameActions_intermediate cs a preliminary version of the C source file of the rule set s actions assembly This file is for internal debug purposes only it contains the frontend actions output e NameActions cs the C source file of the rule setAc
33. only a RHS value To add a key value pair to a map use map union with a single valued map constructor to remove a value from a map use map difference with a single valued set or map constructor for map constructors cf 6 10 iim foo gt 42 2lm n a gt n b orm n a Used in this way they get internally optimized to map addition and removal 6 9 Type Expressions TypeEzxpr A O NodeOrEdge D A type expression identifies a type and in terms of matching also its subtypes A type expression is either a type identifier itself or the type of a graph element The type expression typeof x stands for the type of the host graph element x is actually bound to The expression typeof x lt T2 applied to the type hierarchy on the left side yields true if x is a graph element of type T or T1 or T2 The expression typeof x gt T2 only yields true for x being a graph element of type T4 The expression T1 lt T3 always yields true 6 10 Primary expressions After we ve seen the all the ways to combine expressions finally we ll have a look at the atoms the expressions are built of 18 Types and Expressions PrimaryExpr 8 CO de FlagNumber Eb Expression The visited query returns the status of the visited flag of the given number for the given graph element as boolean If no flag number is given the default number for the first visited flag of O is used The visited flags are written in the assignments of
34. optimizations of search state space stepping and the host graph sensitive search plans In order to accelerate the matching step we internally introduce search plans to represent different matching strategies and equip these search plans with a cost model taking the present host graph into account The task of selecting a good search plan is then considered as an optimiza tion problem BKG08 Bat06 In contrast to systems like Fujaba Fuj07 NNZOO our strongest competitor regarding performance our pattern matching algorithm is fully automatic and does not need to be tuned nor to be implemented in parts by hand According to Varr s benchmark VSV05 it is at least one order of magnitude faster than any other tool known to us Development Convenience is gained by interactive and graphical debugging of the rule application capable of visualizing the matched pattern the rewrite which will be applied and the currently active rule out of the rewrite sequence A further point easening development is the application programming interface of the generated code which offers access to named statically typed entities catching most errors before runtime and allowing the code completion mechanisms of modern IDEs to excel In addition a generic interface oper ating on name strings and NET objects is available for applications where the rules may change at runtime as e g the GRSHELL Another important factor regarding devel opment convenience is cur
35. out parameters are of exactly the type declared non 00 Although a variable of a supertype would be fully sufficient the variable is only assigned So for node class Bla extends Bar and action bar Bar x Bla from the rules file rules Foo grg we can t use a desired target variable of type Bar as out argument but are forced to introduce a temporary variable of type Bla and assign this variable to the desired target variable after the call using de unika ipd grGen libGr using de unika ipd grGen lgsp using de unika ipd grGen Action_Foo using de unika ipd grGen Model_Foo FooGraph graph new FooGraph FooActions actions new FooActions graph Bar b graph CreateNodeBar IMatchesExact lt Rule_bar IMatch_bar gt matches actions bar Match graph 1 b actions bar Modify graph matches First out b wont work needed Bla bla null actions bar Modify graph matches First out bla b bla 10 4 How to build In case you want to build GRGEN NET on your own you should recall the system layout 1 1 The graph rewrite generator consists of a frontend written in Java and a backend written in C The frontend was extended and changed since its first version but not replaced In contrast to the backend which has seen multiple engines and versions a MySQL database based version a PSQL database based version a C version executing a search plan with a virtual machine a C engine executing code generated from
36. redirecting of edge e lt gt There must be at least a node between the edges 4 2 Rules and Tests 33 RuleDeclaration dangling identification Declares a single rewrite rule such as SomeRule It consists of a pattern part see Section 4 3 in conjunction with its rewrite modify part see Section 4 4 A test has no rewrite specifi cation It s intended to check whether and maybe how many times a pattern occurs see example 8 For an explanation of the exact induced dangling identification and dpo pattern modifiers see Section 4 5 ActionSignature EXAMPLE 8 We define a test SomeCond l test SomeCond 4 2 n SeldomNodeType 3 and execute in GRSHELL 1 grs SomeCond amp SomeRule SomeRule will only be executed if a node of type SeldomNodeType exists For graph rewrite sequences in GRSHELL see Section 8 2 8 ActionSignature Ident Decl or ReturnTypes y The signature sets the name of a rewrite rule to IdentDecl and optionally names and types of formal parameters as well as a list of return types Parameters and return types provide users with the ability to exchange graph elements between rules similar to parameters of procedural languages This way it is possible to specify where a rule should be applied P arameters Parameters re 34 Rule Set Language Parameter q Input TypeSpecification y Input TypeSpecification 7 NodeEdg
37. s also possible to specify a rule set file as Filename In this case the necessary assemblies will be created on the fly Opens the graph Text stored in the backend However the LGSPBackend doesn t support persistent graphs and as the LGSPBackend is the only backend available at the moment this command is currently useless You may achieve persistence by using import export or save include instead Displays a list of currently available graphs Selects the current working graph This graph acts as host graph for graph rewrite sequences see also Sections 1 5 and 8 2 8 Though you can define multiple graphs only one graph can be the active working graph Deletes all graph elements of the current working graph resp the graph Graph Deletes the graph Graph from the backend storage 100 GrShell Language 8 2 3 Validation Commands GRGEN NE T offers two different graph validation mechanisms the first checks against the connection assertions specified in the model the second checks against an arbitrary graph rewrite sequence containing arbitrary tests and rules validate GEER Validates if the current working graph fulfills the connection assertions specified in the corre sponding graph model cf 3 2 Validate without the strict modifier checks the multiplicities of the connections it finds in the host graph it ignores node edge node connections which are available in the host graph but have not been s
38. see Chapter 7 We add the following line to our shell script removeEpsilons grs 1 debug xgrs checkStartState amp amp checkDoublettes amp amp lt forwardTransition addStartFinalState addFinalState removeEpsilonTransition gt This looks like a boolean expression and in fact it behaves similar The whole expression is evaluated from left to right A rule is successfully evaluated if a match could be found We first check for a valid state machine i e if the host graph contains exactly one start state and no redundant transitions Thereafter we do the actual rewriting These three steps are connected by lazy evaluation ands amp amp i e if one of them fails the evaluation will be canceled We continue by disjunctively connected rules connected by The angle brackets lt gt around the transformation rules indicate transactional processing If the enclosed sequence returns false for some reason all the already performed graph operations will be rolled back That means not all of the rules must find a match The is used to apply the rule repeatedly as long as a match can be found This includes applying the rule zero times Even in this case Rulex is still successful 2 5 Debugging and Output If you execute the modified GRSHELL script GRGEN NET starts its debugger This way you can follow the evaluation of the graph rewrite sequence step by step in YCOMP Just play around with the keys d s and r in GRSHELL
39. state 2 Write a new value into the current cell according to the sub type of the WriteValue node 3 Move the read write head along the tape and select a new state as current state o oan QA 0 A OQ 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 122 Examples As you can see a transition of the Turing machine is split into two graph rewrite steps Writing the new value onto the tape and performing the state transition We need eleven rules Three rules for each step for zero one and empty and two rules for extending the tape to the left and the right respectively c rule readZeroRule s State h RWHead gt tp TapePosition zero gt tp s zero gt wv WriteValue modify delete h wv RWHead gt tp We take the current state s and the current cell tp which is implicitly given by the unique RWHead edge and check whether the cell value is zero Furthermore we check if the state has a transition for zero The replacement part deletes the RWHead edge between s and tp and adds it between wv and tp The remaining rules are analogous rule readOneRule s State h RWHead gt tp TapePosition one gt tp s one gt wv WriteValue modify delete h wv RWHead gt tp rule readEmptyRule s State h RWHead gt tp TapePosition empty gt tp
40. the allowed explicit type casts Of course you are free to express an implicit type cast by an explicit type cast as well as cast a type to itself e o enum boolean int float double string object enum boolean int implicit int int float implicit implicit float double implicit implicit implicit string implicit implicit implicit implicit implicit implicit object Table 6 3 GRGEN NET type casts 69 70 Types and Expressions According to table 6 3 neither implicit nor explicit casts from int to any enum type are allowed This is because the range of an enum type is very sparse in general For the same reason implicit and explicit casts between enum types are also forbidden Thus enum values can only be assigned to attributes having the same enum type A cast of an enum value to a string value will return the declared name of the enum value A cast of an object value to a string value will return null or it will call the toString method of the NET object Be careful with assignments of objects GRGEN NET does not know your NET type hierarchy and therefore it cannot check two objects for type compatibility Objects of type object are not very useful for GRGEN NET processing and the im exporters can t handle them but they can be used on the API level e Allowed x myfloat x myint x mydouble float x myint x mystring string x mybool e Forbidden x myfloat x mydouble and x myin
41. the d key lets you follow a single rewrite operation in multiple steps the s key jumps to the next rule and the r key runs to the end of the graph rewrite sequence Finally you should get a graph like the one in figure 2 5 yComp Version 1 3 4 mygraph vcg File Edit View Navigate Layout Help Rana e XDA 818 9 Bix A Ei A 2 Transition Find i Next y Options y 1 Transition Eu Root 6 Transition 1 FinalState 2 State F FinalState 0 Transition S StartFinalState Figure 2 5 A state machine without e transitions If everything is working fine you can delete the debug keyword in front of xgrs Maybe you want to save a visualization of the resulting graph This is possible by typing dump graph mygraph vcg in GRSHELL writing mygraph vcg into the current directory in VCG format readable by YCOMP Feel free to browse the examples folder shiped with GRGEN NET esp the succession of examples in FiniteStateMachine and ProgramGraphs is recommended to have a look at giving a nice overview of the capabilities of the software CHAPTER 3 GRAPH MODEL LANGUAGE The key features of GRGEN NET graph models as described by Gei et al GBG 06 KG07 are given below Types Nodes and edges are typed This is similar to classes in common programming lan guages except for the concept of methods that GRGEN NET nodes and edges don t support GRGEN NE T edge types can be directed and undirected Attributes Nodes an
42. the debugger Same as xgrs SimpleRewriteSequence in the previous section but allows tracing the rewriting process step by step 8 3 2 Using the Debugger The debugging process follows of a series of debug situations which result from a user selection of the underlying execution situations accoring to interest During each debugging step the debugger which is a part of the GRSHELL prints the debugged sequence with the currently focused active rule highlighted yellow What will be shown from executing this rule depends on the commands chosen by the user and on the fact whether the focused rule matches or not An active rule which is already known to match is highlighted green The rules which matched during sequence execution are shown on dark green background the rules which failed during sequence execution are shown on dark red background at the begin of a new loop iteration the highlighting state of the contained rules is reset During execution 114 GrShell Language YCoMP will display the changes to the graph from every single step Besides deciding on what is shown from the execution of the current rule the user determines with the debug commands where to continue the execution the rule focused next but again this depends on success failure of the currently active rule The debug commands are given in Table 8 1 A run is shown in the following example 55 In addition to the commands for actively steppin
43. the eval statements see section 4 4 Make sure to allocate 7 6 10 3 visited flags before you try to use them and deallocate them afterwards as they are a sparse resource stored in some excess bits of the graph elements or in some dictionary if the needed number of flags exceeds the number of available bits per graph element The nameof query returns the name persistent name see example 51 of the given graph element as string graphs elements at the API level bear no name the operator can only sensibly be used with Shell graphs NamedGraph unless you decide to use the NamedGraph on API level too If no graph element is given the name of the graph is returned The random function returns a double random value in between 0 0 and 1 0 if called without an argument or if an integer argument value is given an integer random value in between O and the value given excluding the value itself CastExpr de PrimitiveType 3 Primary Expr Member Access NodeO rd OH ident The cast expression returns the original value casted to the new prefixed type The member access n a returns the value of the attribute a of the graph element n Literal Ense 6 10 Primary expressions 19 Constant HexNum m i DoubleNum E FloatNum a QuotedText j BoolLit The Constants are Enumlit Is the value of an enum type given in notation EnumType EnumValue Number Is an int number in decimal notation without decimal poi
44. the pattern part a further difference is the lack of Re turnTypes due to the fact that a subpattern can t return anything they are not actions just a helper in constructing complex patterns Subpatterns can receive additional rewrite parameters in contrast to the actions they can be used to hand in elements which are created in the rewrite part of the action or subpattern which contains the subpattern entity The nested body will be explained in Section 5 7 SubpatternEntityDeclaration ent Subpatienitype ODA Subpattern entity declarations instantiate an entity of the subpattern type i e specified shape which means the subpattern must get matched for the matching of the enclosing pattern to succeed The arguments given are bound to the corresponding parameters of the subpattern If you prefer a syntactical point of view you may see the subpattern entity as a placeholder which gets substituted in place by the textual body of the subpattern declaration under renaming of the parameters to the arguments 5 5 Subpattern Declaration and Subpattern Entity Declaration 57 o a NID 0 A O N Be E O pattern TwoParameters mp Method mp lt Variable mp lt Variable est methodAndFurther m Method lt n Name tp TwoParameters m In the given example a subpattern TwoParameters is declared connecting the context element mp via two edges to two variable nodes The test methodAndFurther is
45. the variables x and y on the host graph and assigns the return elements from the rule to the variables u and v the parenthesis around the out variables are always needed even if there s only one variable assigned to The sequence t determines all matches of the parameterless rule t on the host graph then one of the matches is randomly chosen and executed 1 4 Variable handling 87 7 4 Variable handling VariableHandling Variable otro Variable GOO Nu Variable JOH Attribute Variables can hold graph elements or values of value attribute types including booleans The typed explicit declaration introduces a sequence local variable if the double colon and the type are missing a graph global variable gets implicitely declared if not existing yet Graph elments are initially assigned to the variables by the element returns of the RuleEzxecution statement or by the by name access denoted with the at operator Assigning graph elements by their persistent name to variables is not supported in compiled sequences names are not available on this level The random number assignment v 42 assigns a random number in between 0 and 41 to the variable v Appending a changes random selection to user selection defining a choice point The user input assignment v string queries the user for a string value this only works in the GrShell The user input assignment v Node queries the user for a node from t
46. with semantic nets transformation of natural language to UML models model transformation processing of program graphs genome simulation or pattern matching in social nets Several of them are worked on you may have a look at BG09 or GDG08 or SGS09 12 Introduction CHAPTER 2 QUICKSTART In this chapter we ll build a GRGEN NET system from scratch You should already have read Chapter 1 to have a glimpse of the GRGEN NET system and its components We will use GRGEN NET to construct non deterministic state machines We further show some actual graph rewriting by removing e transitions from our state machines This chapter is mostly about the GRGEN NET look and feel please take a look at the succeeding chapters for comprehensive specifications 2 1 Downloading amp Installing If you are reading this document you probably did already download the GRGEN NET soft ware from our website http www grgen net Make sure you have the following system requirements installed and available in the search path e Java 1 5 or above e Mono 1 2 3 or above Microsoft NET 2 0 or above If you re using Linux Unpack the package to a directory of your choice for example into opt grgen mkdir opt grgen tar xvfj GrGenNET V1_3_1 2007 12 06 tar bz2 mv GrGenNET V1_3_1 2007 12 06 opt grgen rmdir GrGenNET V1_3_1 2007 12 06 Add the opt grgen bin directory to your search paths for instance if you use bash add a line to your
47. 2 negative 93 tp right gt 94 95 modify 96 tp right gt rtp TapePosition empty gt rtp 97 98 Have a look at the negative conditions within the ensureMove rules They ensure that the current cell is indeed at the end of the tape An edge to a right left neighboring cell must not exist Now don t forget to compile your model and the rule set with GrGen exe see Section 9 1 9 2 3 Rule Execution with GRSHELL Finally we construct the busy beaver and let it work with GRSHELL The following script starts with building the Turing machine that is modeling the six states with their transitions in our Turing machine model i select backend bin lgspBackend d11 o a nn ow A WB WD D DD e MH re Ra Pp RR pp e gt sp HM O o 0 nN DO a FP y N e O 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 124 new graph lib lgsp TuringModel d11 Busy Beaver select actions lib lgsp TuringActions d11 Initialize tape new tp TapePosition Startposition new tp empty gt tp States new sA State A new sB State B new sC State C new sD State D new sE State E new sH State Halt new sA RWHead gt tp Transitions three lines per state and input symbol for updating cell value moving read write head respectively new sA_O WriteOne new s
48. 6 3 Boolean Expressions nn ee ee ee Tl 6 4 Relational Expressions nn nen TM 6 5 Arithmetic and Bitwise Expressions 72 6 6 String Expressions 0 0 2 ee ee ee 14 6 7 Set Expression 2 1 1 2 a ee ee A 6 8 Map Expression ww u a wa a Ew ee oe we ee Kee we Ee 5 6 9 Type Expressions nn nn ee ee ee ee MM 6 10 Primary expressions on onen TT 6 11 Operator Priorities eee ee 80 7 Rule application control language XGRS 83 7 1 Logical connectives rewrite sequence 4 A 7 2 Loops rewrite term oo one 85 7 3 Rule application rewrite factor 2 nommen 85 7 4 Variable handling nennen 87 7 0 Extended control u u un nn nn 88 TO Visited Pies s s s e pew we YS Bee Ass s BY 17 7 Storages E ol 7 8 Quick reference NN E eee oe OZ 8 GrShell Language 95 8 1 Building Blocks 2 2 2 2 2 2 985 8 2 GRSHELL Commands 2 2 2 ee ee ee 7 8 2 1 Common Commands 0 a ee a 97 622 taph Commands 22 50 4 een aan 99 8 2 3 Validation Commands 64 6 4 s s se ca midosa paraire ma 100 8 2 4 Graph Input and Output Commands a 102 8 2 5 Graph Manipulation Commands e a a 104 8 2 6 Graph and Model Query Commands 106 8 2 7 Graph Visualization Commands a a 108 8 2 8 Action Commands XGRS o 112 8 3 Graphic
49. 93 106 93 amp 93 98 action see graph rewrite sequence action command 112 adjacent 35 AEdge 21 all bracketing 86 alternative patterns 54 analyzing graph 116 141 annotation 20 28 46 anonymous 28 38 39 96 API 4 9 127 application 5 36 application programming interface see API arbitrary 21 30 attribute 26 106 107 111 attribute condition 37 attribute evaluation 40 41 backend 4 69 112 116 backslash 97 binding of names 28 boolean 69 break point 86 88 114 building GrGen 132 built in generic types see generic types built in types see primitive types busy beaver 121 by reference 34 by value 34 cardinality see pattern cardinality case sensitive 20 27 95 choice point 84 86 89 114 color 96 109 command line 98 comment 95 compatible types see type compatible compiler graph see layout algorithm conditional sequence 88 connection assertion 24 25 100 constructor 96 106 continuation see graphlet dangling condition 43 debug mode 113 debugger 113 declaration 20 22 36 default graph model 27 default search plan 117 default value 106 definition 20 46 deletion 38 40 determinism see non determinism directed 30 double 69 double pushout approach 10 DPO see double pushout approach dumping graph 102 dynamic type 44 EBNF see rail diagram see regular expres sion syntax 142 Edge 21 24 e
50. GRGEN NET as s domain specific language into C Kro resulting in GRGEN NET v2 0 Then Dr Rubino Geif finished his dissertation Gei08 and left Prof Goos retired The succeeding Professor had no commitment to graph rewriting so GRGEN NET switched from a university project developed by students in their bachelor masters thesis s to an open source project which is still hosted at the IPD reachable from www grgen net But development continued With the introduction of generic set and map types in the model language to facilitate uses in computer linguistics and in the rule control language to allow for more concise rule combinations With the 2 n pushdown automaton for matching patterns with structural recursion extended to handle pattern cardinality specifications and positive applications conditions JBK10 With massive API improvements now featuring an interface of typed named entities in addition to the old name string and object based interface With the introduction of importers and exporters for GXL the quasi standard graph exchange format in graph rewriting but only in theory and for GRS a much easier and less chatty format Most of these features were introduced due to feedback from users and use cases We want to thank the organizers of GraBaTs RVGO8 the annual meeting of the graph rewrite tool community which gave us the possibility to ruthlessly steal the best ideas of the competing tools Thanks to Berthold
51. GraphletEdge 30 GraphletNode 29 Group Constraints 110 IdentDecl 46 IncAdjTypeConstraints 110 Input TypeSpecification 34 IntExpr 73 Literal 79 MapConst 106 MapConstructor 80 MapEzxpr 76 MemberAccess 78 Multiplicity Constraint 25 NegativeApplicationCondition 50 NestedPattern 50 NestedPattern WithCardinality 53 NestedRewriting 60 NodeClass 24 NodeConstraint 25 Parameter 34 Parameters 95 Pattern 36 PatternStatement 36 PositiveA pplicationCondition 52 PrimaryExpr 78 PrimitiveAttribute Value 106 RHS 91 RangeConstraint 25 RelationalExpr 71 Replace 40 ReplaceStatement 40 ReturnStatement 37 ReturnTypes 34 Retyping 45 RewriteFactor 85 92 RewriteNeg Term 84 RewriteSequence 84 Rewrite Term 85 Rule 86 10 5 A very short tour of the code RuleDeclaration 33 RuleExecution 86 RuleSet 31 Script 97 SequencesList 88 SetConstr 106 SetConstructor 80 SetExpr 75 SetMapCreation 91 SetMapStateChange 41 SetMap TypeDecl 90 SpacedParameters 95 StringExpr 74 SubpatternBody 56 SubpatternDeclaration 56 SubpatternEntityDeclaration 56 SubpatternRewriteA pplication 63 SubpatternRewriting 62 TestDeclaration 33 Type 44 TypeConstraint 44 TypeExpr 77 VariableHandling 87 90 VisitedFlags Management 89 General Index gm 4 erg 4 7 ers 4 8 93 98 93 80 33 97 52 93 lt 93 lt gt 88 O 96 95 lt number gt 28 lt op gt 36
52. Hoffmann for his french courses and the ideas about how to handle program graphs And thanks to several early users giving valu able feedback or even code code is of course the best contribution you can give to an open source project by name Tom Gelhausen and Bugra Derre you may have a look at https svn ipd uni karlsruhe de trac mx wiki Home for their work at the other IPD Paul Bedaride Normen Miiller Pieter van Gorp and Nicholas Tung Regarding questions please contact the GRGEN NET Team via email to grgen at the host given by ipd info uni karlsruhe de We hope you enjoy using GRGEN NET even more than we enjoyed developing it it was fun but aging projects with code traces from many people are not always nice to work with Thank you for using GRGEN NET Karlsruhe in October 2010 Edgar Jakumeit on behalf of the GRGEN NE T Team vil viil 1 Introduction i 1 2 1 3 1 4 1 5 1 6 1 7 1 8 What is GRGEN NET When to use GRGEN NET and e not Features of GRGEN NET System Overview i l What is Graph Rewriting l An Example The Tools 1 7 1 GrGen exe cono oc mesas 1 7 2 GrShell exe coo 4 28 sas u en Lil Pee aa a ee RR LIO yOonp jar ssa scet etar dya de Development goals 2 Quickstart 2l 2 2 2 3 2 4 2 0 Downloading amp Installing Creating a Graph Model Creating Graphs The Rewrite Rules Debugging and Output 3 Graph Model Language 3 1 3 2 Building Bloc
53. Universitat Karlsruhe TH Forschungsuniversitat gegrundet 1825 Fakultat fur Informatik Institut fur Programmstrukturen und Datenorganisation Lehrstuhl Prof Goos The GRGEN NET User Manual Refers to GRGEN NET Release 2 6 4 DRAFT www grgen net Jakob Blomer Rubino Geib Edgar Jakumeit October 30 2010 11 ABSTRACT GRGEN NET transformation of structures made easy with languages for graph modeling pattern matching and rewrit ing as well as rule control brought to life by a compiler and a rapid prototyping environment offering graphical and step wise debugging The Graph Rewrite Generator is a tool en abling elegant and convenient development of graph rewriting applications with comparable performance to conventionally developed ones This user manual contains both normative statements in the sense of a reference manual as well as an informal guide to the features and usage of GRGEN NET O This manual is licensed under the terms of the Creative Commons cc Attribution Share Alike 3 0 Germany license The license is available BY SA at http creativecommons org licenses by sa 3 0 de 111 1V FOREWORD FOR RELEASE 1 4 First of all a word about the term graph rewriting Some would rather say graph trans formation some even think there is a difference between these two We don t see such differences and use graph rewriting for consistency The GRGEN project started
54. a search plan and finally the current C engine version 2 capable of matching nested and subpatterns The frontend is available in the frontend subdirectory of the source distribution or the public subversion repository at https pp info uni karlsruhe de svn grgen public trunk grgen It can be build with the included Makefile on Linux or the Makefile_Cygwin on Windows with the cygwin environment yielding a grgen jar Alternatively you may add the de subfolder and the jars in the jars subfolder to your favourite IDE but then you must take care of the ANTLR parser generation pre build step on your own The backend is available in the engine net 2 subdirectory It contains a VisualStudio 2005 solution file containing projects for the libGr the lgspBackend libGr Search Plan Backend and the GrShell Before you can build the solution you must execute src libGr genparser bat src libGr GRSImporter genparser bat and src GrShell genparser bat to get the CSharpCC parsers for the rewrite sequences the GRS importer and the shell generated Under LINUX you may use make_linux sh to get a complete build To get the API examples generated you must execute genlibs bat The doc subdirectory contains the sources of the user manual for building say build_cygwin sh grgen on Windows in cygwin bash or build grgen on Linux in bash The syntaxhighlighting subdirectory contains syntax highlighting specifications for the GrGen files for Notepad and vim
55. a specific set of nodes Accordingly the list of identifiers for a pattern modifier must not contain any edge identifier See Section 4 5 for an explanation of the exact and induced modifiers NestedPattern will be explained in 5 1 5 2 5 3 5 4 SubpatternEntityDeclaration will be explained in 5 5 Keep in mind that using type constraints or the typeof operator might be helpful See Section 6 9 for further information ReturnStatement return Expression Returned graph elements given by their name and value entities given by an expression computing them must appear in the same order as defined by the return types in the sig nature see Section 4 2 ActionSignature Their types must be compatible to the return types specified 38 Rule Set Language o 0 XD wow FF O N Hr Rh pap N fF Oo If you are using a graph at the API level without shell provided names accessible by the nameof operator you may want to number the graph elements for dumping like this rule numberNode var id int int n NodeWithIntId if n id 0 modify 1 eval n id id return id 1 4 4 Replace Modify Part Besides specifying the pattern a main task of a rule is to specify the transformation of a matched subgraph within the host graph Such a transformation specification defines the transition from the left hand side LHS to the right hand side RHS i e which graph elements of a match will be kept
56. able 33 34 35 49 50 Nested and Subpatterns Until now we have seen rules and tests with one left hand side static pattern specification in a direct 1 1 correspondence with its dynamic match in the host graph on a successful application From now on we will increase the expressiveness of the pattern language and dependent on it the rewrite language to describe much finer and more flexible what patterns to accept This will be done by pattern specifications built up from multiple static pattern piece specifications where the pieces may be matched dynamically zero one or multiple times or are forbidden to exists for the entire pattern to be matched These rule set lan guage constructs can be split into nested patterns negative application condition positive application condition nested pattern with cardinality alternative patterns and subpatterns subpattern declaration and subpattern entity declaration subrule declaration and usage we will start with the nested patterns NestedPattern retten erg AlternativePatterns 5 1 Negative Application Condition NAC Negative ApplicationCondition ER PatternStatement With negative application conditions keyword negative we can specify graph patterns which forbid the application of a rule if any of them is present in the host graph cf Sza05 NACs possess a scope of their own i e names defined within a NAC do not exist outside the NAC Identifiers from surroun
57. ables Map addition m add k v adds the pair k v to the map m succeeds always Map removal m rem k removes the pair k unknown from the map m succeeds always Map clearing m clear removes all key value pairs from the map m succeeds always There are further operations which are only available in variable assignments 92 Rule application control language XGRS Size assignment v sm size writes the number of entries in the set or map sm to the variable v succeeds always Emptyness assignment v sm empty writes to the variable v whether the set or map sm is empty succeeds always Map lookup assignemt v m el assigns the result of the map lookup to the variable v succeeds iff el is contained in m fails otherwise not touching the variable v RewriteFactor Handling of the storages is completed by the rewrite factors for membership query and storage iteration The binary operator el in sm checks for set map membership it returns true if el is contained in the set or the domain of the map otherwise false The for command iterates over all elements in the set or all key value pairs in the map and executes for each element key value pair the nested graph rewrite sequence it completes successfully iff all sequences were executed successfully an empty set map causes immediate successful completion The following XGRS is a typical storage usage First an empty set x is created which gets popul
58. ace part and a modify part is that a replace part deletes every graph element of the pattern which is not explicitly mentioned within its body The modify part in contrast deletes nothing by default but just adds or adjusts graph elements However the modify part allows for explicit deletion of graph elements by using the delete statement What else can we do We have negative application conditions NACs expressed by negative they prevent rules to be applied if the negative pattern is found We also have attribute conditions expressed by if a rule is only applicable if all such condi tions yield true Note the dot notation to access attributes as in e Trigger The emit statement prints a string to stdout The hom x y and hom x y z statements mean match the embraced nodes homomorphically i e they can but they don t have to actually be matched to the same node within the host graph The eval statement is used to re calculate attributes of graph elements Have a look at the statement y StartFinalState lt x gt in addStartFinalState we retype the node x That means the newly created node y is actually the node x including its incident edges and attribute values except for the node type which is changed to StartFinalState Imagine retyping as a kind of a type cast The created rewrite rules might be considered as rewrite primitives In order to implement more complex functionality we will compos
59. al Debugger Peed eae ee eae ae oe 2 eo ode 8 3 1 Debugging Related nae eee eee eee ee eee ee 113 8 3 2 Using the Debugger 4 00 0 et 0 wos ew DSS we EE Ses 113 10 8 4 Backend Commands 8 4 1 Backend selection and custom commands 8 4 2 LGSPBackend Custom Commands Examples 9 1 Fractals ur 9 2 Busy Beaver 2 u da amp 9 2 1 Graph Model 922 Buleset 2 0 1 u dw vo 9 2 3 Rule Execution with GRSHELL Application Programming Interface 10 1 Interface to the host graph 10 2 Interface to rules 10 3 Import Export and miscellaneous stuff 10 4 How to build u 10 5 A very short tour ofthe code Bibliography Index xi 115 116 116 119 119 sdl 121 121 123 127 127 128 130 192 133 135 139 xil CHAPTER 1 INTRODUCTION 1 1 What is GRGEN NET GRGEN Graph Rewrite GENerator is a generative programming system for graph rewriting which considerably eases the transformation of complex graph structured data comparable to other programming tools like parser generators which ease the task of formal language recognition or databases which ease the task of persistent data storage and querying It is combined from two groups of components The first consists of the compiler grgen transforming declarative graph rewrite rule specifications into highly efficient NET assemblies and the execution envir
60. ams see MMJW91 Extended Backus Naur Form 19 20 Graph Model Language oO a nn a FF O N Hr The following toy example of a model of road maps gives a rough picture of the language enum Resident VILLAGE 500 TOWN 5000 CITY 50000 node class Sight node class City Size Resident const node class Metropolis extends City River String abstract node class AbandonedCity extends City node class GhostTown extends AbandonedCity edge class Street edge class Trail extends Street edge class Highway extends Street connect Metropolis gt Metropolis Jam boolean false Basic elements of the GRGEN NET graph model language are identifiers to denominate nodes edges and attributes The model s name itself is given by its file name The GR GEN NET graph model language is case sensitive Ident IdentDecl A non empty character sequence of arbitrary length consisting of letters digits or under scores The first character must not be a digit Ident and IdentDecl differ in their role While IdentDecl is a defining occurrence of an identifier Ident is a using occurrence An IdentDecl non terminal may be annotated See Section 4 9 for annotations of declarations eA N m The GRGEN NE T model language does not distinguish between declarations and definitions More precisely every declaration is also a definition For instance the following C like pseudo GRGEN NET model
61. an be enumerated Key Value Type Applies to Meaning int node edge Changes the ranking of a graph element for search plans The default is prio 1000 Graph elements with high values are likely to appear prior to graph elements with low values in search plans Table 4 5 Annotations EXAMPLE 18 We search the pattern v NodeTypeA e EdgeType gt w NodeTypeB We have a host graph with about 100 nodes of NodeTypeA 1 000 nodes of NodeTypeB and 10 000 edges of EdgeType Furthermore we know that between each pair of NodeTypeA and NodeTypeB there exists at most one edge of EdgeType GRGEN NET can use this information to improve the initial search plan if we adjust the pattern like v prio 10000 NodeTypeA e prio 5000 EdgeType gt w NodeTypeB 4 10 Imperative Statements 47 4 10 Imperative Statements ExecStatement The statements emit and exec as well as the set map modification statements enhance the declarative rewrite part by imperative clauses That means these statements are executed in the same order as they appear within the rule The execution statements take place after all the rewrite operations are done i e they operate on the modified host graph However attribute values of deleted graph elements are still available for reading The eval statements are executed before the execution statements i e the execution statements work on the recalculated attributes XGRS Execution The exec statement execute
62. andom choice applied matches all contained rules and then executes at random one of the rules which matched i e the one match of a rule all matches of an all bracketed rule or one randomly chosen match of an all bracketed rule with random choice The one some of set is true if at least one rule matched and false if no contained rule matched A choice point may be used on the one of set it allows you to inspect the matches available graphically before deciding on the one to apply 7 6 Visited Flags VisitedFlags Management Loge Oy BEI COLORO OOOO 3 sited DH Variable O O Bam ee O ED O G E The visited flags are stored in some excess bits of the graph elements but if this pool is exceeded they are stored in additional dictionaries one per visited flag requested Due to this flags must get allocated deallocated and all flag related operations require an integer number the flag id specifying the flag to operate on with exception of the allocation operation returning this flag id The operations always return true as sequence results with exception of the operation reading the flag it fails iff the visited flag is not set for the graph element if you try to access a not previously allocated visited flag an exception is thrown The operations managing the visited flags are Variable vfree GraphElement Flag allocation By valloc allocates space for a visited flag in the
63. ans a directed edge aiming towards a node of the target node type or one of its subtypes The A lt B connection assertion is equivalent to the B gt A connection assertion The arrow is used for undirected edges The arrow means an arbitrary edge i e directed as well as undirected possible fixed by the concrete type inheriting from it in case of an directed edge the connection pattern gets matched in both directions Number is an int constant as defined in Chapter 6 Table 3 1 describes the multiplicity definitions In order to apply the connection assertions of the supertypes to an EdgeType you may use the keywords copy extends The copy extends assertion imports the connection asser tions of the direct ancestors of the declaring edge This is a purely syntactical simplification 26 Graph Model Language The number of edges incident to a node of that type is unbounded At least n edges must be incident to nodes of that type At least n edges must be incident to nodes of that type but at most m edges may be incident to nodes of that type m gt n gt 0 must hold Abbreviation for 0 Abbreviation for 1 Abbreviation for n n Abbreviation for 1 Table 3 1 GRGEN NET node constraint multiplicities i e the effect of using copy extends is the same as copying the connection assertions from the direct ancestors by hand 3 2 1 Attribute Types AttributeDeclaration Expression
64. aph model and rewrite rules their elements can be of node or edge type Storing nodes and edges is in fact their primary usage They allow to decouple processing phases the first run collects all graph elements relevant for the second run which consists of a sequence executed for each graph element in the set A further difference to the sets and maps in the rewrite rules is that they only offer imperative addition and removal instead of union intersection difference and construction VariableHandling aoe a _ O a y SetMap TypeDecl 7 7 Storages 91 RHS UN _ N A set map must be created and assigned to a variable before it can be used EXAMPLE 49 1 x set lt NodeTypeA gt 2 y map lt Node Edge gt map lt Node Edge gt The first line declares or references a variable x without static type and assigns the newly created empty set of type set lt NodeTypeA gt to it as value The second line declares a variable y of type map lt Node Edge gt and assigns the newly created empty map of the same type to it as value There are several operations on set variables available in method call notation these are Set addition s add v adds the value v to the set s succeeds always Set removal s rem v removes the value v from the set s succeeds always Set clearing s clear removes all values from the set s succeeds always Very similar operations are available on map vari
65. at into the file Filename The following commands control the style of the VCG output This affects dump graph show graph and enable debug See Section 1 7 4 8 2 GRSHELL Commands 109 dump node NodeType DEA Eg Sets the color text color border color the shape or the label of the nodes of type NodeType and all of its subtypes The keyword only excludes the subtypes The available colors are specified at the begin of this chapter The following shapes are supported box triangle circle ellipse rhomb hexagon trapeze uptrapeze lparallelogram rparallelogram Those are shape names of YCOMP for a VCG definition see San95 The default labeling is set to on with Name Type it can be overwritten by an specified label string e g the source code line originating the node in a program graph or switched off OOL vn Tel Sets the color text color or label of the edges of type EdgeType and all of its subtypes The keyword only excludes the subtypes The available colors are specified at the begin of this chapter The default labeling is set to on with Name Type it can be overwritten by an specified label string or switched off 110 GrShell Language Excludes nodes edges of type Node Type Edge Type and all of its subtypes from output for a node it also excludes its incident edges The keyword only excludes the subtypes from exlusion i e subtypes of Node Type Edge Type are dumped
66. ateCriticalEdge 9 exec MaxCapacityIncidentEdge t 10 emit Redundancy added CHAPTER 5 NESTED AND SUBPATTERNS The extension of the rule set language described in the previous chapter by nested patterns and subpatterns greatly enhances the flexibility and expressiveness of pattern matching and rewriting The following patterns to match a simplified abstract syntax tree give a rough picture of the language of nested and subpatterns test method i m Method lt n Name signature of method consisting of name iterated and O n parameters m lt Variable J AssignmentList m body consisting of a list of assignment statements oO a N 9 00 Pp W WD E pattern AssignmentList prev Node e N E optional 1 nothing or a linked assignment and again a list prev gt a Assign assignment node a target gt v Variable which has a variable as target Expression a and an expression which defines the left hand side AssignmentList a next one plz Rh e e SS op a o O 1s 19 20 21 pattern Expression root Expr za 23 alternative expression may be 24 Binary 1 a binary expression of an operator and two expresions 25 root lt expri Expr 26 Expression expr1 27 root lt expr2 Expr 28 Expression expr2 29 root lt Qperator 30 31 Unary or a unary expression which is a variable reading it 32 root lt v Vari
67. ated by an rule t executed iteratedly returning a node which is written to the set Then another rule is executed iteratedly for every member of the set doing the main work and finally the set gets cleared to prevent memory leaks or later mistakes If the graph should stay untouched during set filling you may need visited flags to prevent endless looping x set lt Node gt gt v tO amp amp x add v amp amp for v in x r v lt x clear Handing in the storage to the rule and using the set add method as introduced in 4 10 within the rule to fill the storage allows to shorten the sequence to x set lt Node gt gt t x amp amp fortv in x r v lt x clear The set map over which the for loop iterates must stay untouched during iteration 7 8 Quick reference table Table 7 2 lists most of the operations of the graph rewrite expressions at a glance 1 8 Quick reference table 93 nun u ct ct un R amp P ct s t if r s t if r s lt s gt Is lt op gt Sk s s n s m n s m Rule Rule Rule def Parameters true false 171 r21z r3 id valloc vfree id vreset id u set lt Node gt u add v u rem v for v in u tj u clear v in u u map lt N Edge gt v ulw Execute s then t Success if t succeeded Execute s then t Success if s succeeded Execute s then t Success if s or t succeeded The same as s t but with lazy evaluation i
68. ayed The only keyword excludes inherited attributes The show nodes edges attributes command covers types and inherited types This is in contrast to the other show commands where types and subtypes are specified or the direction in the type hierarchy is specified explicitly respectively Gets the attribute types and values of a specific graph element GraphElement o AttributeName Displays the value of the specified attribute Gets the information whether the first element is type compatible to the second element 108 GrShell Language 8 2 7 Graph Visualization Commands ExecutableName Dumps the current graph in VCG format into a temporary file The temporary VCG file will be passed to the program ExrecutableName as first parameter further parameters such as program options can be specified by Text If you use YCOMP as executable show graph ycomp this may look like yComp Version 1 3 1 tmpgraphO vcg File Edit View Navigate Layout Help BSEBIEKBEAAAHA A 14 12 D ih Find Next Options Root 0 AB 102 AB 105 CA 108 AB 10B CA 10E CA 111 CA 114 CA 117 CA S11A CA 11D CA 120 CA 123 BC N 126 BC Ir 129 BC 12 CA iy 12C BC 12F BC 132 BC 2125 AR gt NE The temporary file will be deleted when the application Filename is terminated if GRSHELL is still running at this time camp Dumps the current graph in VCG form
69. ble to the well known term rewriting Normally you use one or more graph rewrite rules to accomplish a certain task GRGEN NET implements an SPO based approach as default In the simplest case such a graph rewrite rule consists of a tuple L gt R whereas L the left hand side of the rule is called pattern graph and R the right hand side of the rule is the replacement graph Pattern Graph Rewrite Graph Preservation Morphism r L ao q SR 0 Rul Match m H G Rule Application ae Host Graph Result Graph Figure 1 3 Basic Idea of Graph Rewriting Moreover we need to identify graph elements nodes or edges of L and R for preserving them during rewrite This is done by a preservation morphism r mapping elements from L to R the morphism r is injective but needs to be neither surjective nor total Together with a rule name p we have p L gt R The transformation is done by application of a rule to a host graph H To do so we have to find an occurrence of the pattern graph in the host graph Mathematically speaking such a match m is an isomorphism from L to a subgraph of H This morphism may not be unique i e there may be several matches Afterwards we change the matched spot m L of the host graph such that it becomes an isomorphic subgraph of the replacement graph R Elements of L not mapped by r are deleted from m L during rewrite Elements of R not in the image of r are inserted into H all others elements that are mapped b
70. by the parameter specification itself 36 Rule Set Language 4 3 Pattern Part Pattern q PatternStatement B p ReturnStatement y A pattern consists of zero or more pattern statements and in case of a test an optional return statement All the pattern statements must be fulfilled by a subgraph of the host graph in order to form a match An empty pattern always produces exactly one empty match This is caused by the uniqueness of the total and totally undefined function For an explanation of the pattern modifiers dpo identification dangling induced and exact see Section 4 5 Names defined for graph elements may be used by other pattern statements as well as by replace modify statements Like all identifier definitions such names may be used before their declaration See Section 4 1 for a detailed explanation of names and graphlets The application of a rule is not deterministic remember the example of the introduction in Section 1 6 in particular there may be more than one subgraph that matches the pattern Whereas the GRSHELL selects one of them arbitrarily without further abilities to control the selection the underlying LIBGR provides a mechanism to deal with such ambiguities Also notice that graph rewrite sequences introduce a further variant of non determinism on rule application level The lt op gt flag marks the operator lt op gt as commutative i e the execution order of its operands rules is non determini
71. constructs introduced in this chapter NestedRewriting replace R eplaceStatement modify Syntactically the rewrite is specified by a modify or replace clause nested directly within the scope of each nested pattern in addition to the rewrite clause nested within the top level pattern which must be present even if the top level pattern is empty Semantically for every instance of a pattern piece matched its dependent rewrite is applied So in the same manner the complete pattern is assembled from pattern pieces the complete rewrite gets assembled from rewrite pieces or operationally rewriting is done along the match tree by rewriting one pattern piece after the other Note that neither exec statements nor return statements are available as in the top level rewrite part of a rule For a static pattern specification like the iterated block yielding dynamically a combined match of zero to many pattern matches every submatch is rewritten according to the rewrite specification applied to the host graph elements of the match bound to the pattern elements if the pattern was matched zero times no dependent rewrite will be triggered but note that zero matches still means success for an iterated so the dependent rewrite piece of the enclosing pattern will be applied This allows e g for reversing all edges in the iterated example denoting containment in the class as it is shown in the first of the following two
72. d edges may possess attributes The set of attributes assigned to a node or edge is determined by its type The attributes themselves are typed too Inheritance Node and edge types classes can be composed by multiple inheritance Node and Edge are built in root types of node and edge types respectively Inheritance eases the specification of attributes because subtypes inherit the attributes of their super types Note that GRGEN NE T lacks a concept of overwriting On a path in the type hierarchy graph from a type up to the built in root type there must be exactly one declaration for each attribute identifier Furthermore if multiple paths from a type up to the built in root type exist the declaring types for an attribute identifier must be the same on all such paths Connection Assertions To specify that certain edge types should only connect specific node types a given number of times we include connection assertions In this chapter as well as in Chapter 8 GRSHELL we use excerpts of Example 1 the Map model for illustration purposes 3 1 Building Blocks The following syntax specifications make heavy use of syntax diagrams also known as rail diagrams Syntax diagrams provide a visualization of EBNF grammars Follow a path along the arrows through a diagram to get a valid sentence or subsentence of the language Ellipses represent terminals whereas rectangles represent non terminals For further information on syntax diagr
73. d to the constructor Available attribute names are specified by the graph model of the current working graph All the undeclared attributes will be initialized with default values depending on their type int 0 boolean lt false float 0 0f double 0 0 string set lt T gt set lt T gt map lt S T gt map lt S T gt enum unspecified The is a special attribute name a unique identifier of the new graph element This identifier is also called persistent name see Example 51 This name can be specified by a constructor only Deletes the node Node from the current graph Incident edges will be deleted as well Deletes the edge Edge from the current graph Set the attribute AttributeName of the graph element GraphElement to the value of Text or Number 8 2 6 Graph and Model Query Commands Gets the persistent names and the types of all the nodes edges of the current graph If a node type or edge type is supplied only elements compatible to this type are considered The only keyword excludes subtypes Nodes edges without persistent names are shown with a pseudo name If the command is specified with num only the number of nodes edges will be displayed Gets the node edge types of the current graph model 8 2 GRSHELL Commands 107 np Gets the available node edge attribute types If NodeType Edge Type is supplied only at tributes defined in Node Type Edge Type are dipl
74. d true executes the true case Xgrs otherwise the false case xgrs The sequence if Condition TrueCase is equivalent to if Condition TrueCase true thus giving a lazy implication Graph rewrite sequences can be processed transactionally by using angle brackets lt gt i e if the return value is false all the related operations on the host graph will be rolled back Nested transac tions are supported Forcing execution order can be achived by parentheses Boolean literals true false come in handy if a sequence is to be evaluated but its result must be a predefined value furtheron a break point may be attached to them The random all of operators given in function call notation with the dollar sign plus operator symbol as name have the follow ing semantics The strict operators and amp evaluate all their subsequences in random order returning the disjunction resp conjunction of their truth values The lazy operators and amp amp evaluate the subsequences in random order as long as the outcome is not fixed or every subsequence was executed which holds for the disjunction as long as there was no succeeding rule and for the conjunction as long as there was no failing rule A choice point may be used to define the subsequence to be executed next The some of set braces r s t matches all contained rules and then executes the ones which matched The one of set braces 7 6 Visited Flags 89 r s t some of set with r
75. dge graphlet 30 edge type 24 empty pattern 5 36 enum item 22 70 enum type 22 70 evaluation see attribute evaluation exact dynamic type see dynamic type example 5 13 119 121 export 102 130 expression 70 expression variable 78 see name 104 features 2 float 69 generator 4 generic types 69 eraph global variable 96 eraph global variables 83 graph model 4 19 21 27 31 99 graph model language 19 eraph rewrite rules 5 graph rewrite script 4 8 98 102 graph rewrite sequence 36 83 100 112 113 eraph rewriting 5 graphlet 28 36 38 40 GrGen exe 7 group node 110 GRS see graph rewrite sequence GrShell 4 8 23 95 GrShell script see graph rewrite script GrShell variable see graph global variable GrShell exe 8 hierarchic see layout algorithm see group node homomorphic matching 28 37 host graph 5 38 99 identification condition 43 identifier 20 28 imperative see attribute evaluation imperative statements 47 import 102 130 indeterministic choice 88 info tag 111 inheritance 19 24 107 int 69 isomorphic matching 37 Kantorowitsch tree 114 Koch snowflake 119 label 97 111 Application Programming Interface layout see layout algorithm see visualization layout algorithm 9 113 119 left hand side 5 38 LGPL 7 LGSPBackend 69 116 LHS see left hand side libGr 4 9 23 36 95 loop 85 map 69 90 match
76. ding scopes must not be redefined If they are not explicitely mentioned the NAC gets matched independent from them i e elements inside a negative are hom everything from the outside by default But referencing the element from the outside within the negative pattern causes it to get matched isomorphically distinct to the other elements in the negative pattern This is a bit unintuitive if you think of extending the pattern by negative elements but cleaner and more powerful just think of NACs to simply specify a pattern which should not be in the graph with the possibility of forcing elements to be the same as in the enclosing pattern by name equality Bb N pa We specify a variable which is not badly typed i e a node x of type Variable which must not be target of an edge of type type with a source node of type BadType x Variable negative x lt type BadType J 5 1 Negative Application Condition NAC 51 Because NACs have their own binding using NACs leads to specifications which might look a bit redundant Let s check the singleton condition meaning there s exactly one node of the type to check for the type RootNamespace The following specification is wrong it will never return a match x RootNamespace negative y RootNamespace J x Ww N Instead we have to specify the complete forbidden pattern inside the NAC This is done by x RootNamespace negative x y
77. e n4 Node NodeTypeB n3 el EdgeTypeB gt n4 if typeof e1 gt EdgeTypeA y gt replace nd NodeTypeC lt n1 gt n3 el EdgeTypeB gt n5 eval n5 a3 n3 al n1 a2 F In this chapter we use excerpts of Example 4 SomeRule for illustration purposes The nested negative which specify a pattern which must not be available in the host graph are described in the following Chapter 5 4 1 Building Blocks The GRGEN NET rule set language is case sensitive The language makes use of several identifier specializations in order to denominate all the GRGEN NE T entities Omitting a graph meta model means that GRGEN NET uses a default graph model The default model consists of the base type Node for vertices and the base type Edge for edges 21 28 Rule Set Language Ident IdentDecl A non empty character sequence of arbitrary length consisting of letters digits or under scores The first character must not be a digit dent may be an identifier defined in a graph model see Section 3 1 Ident and IdentDecl differ in their role While dentDecl is a defining occurrence of an identifier Ident is a using occurrence An dentDecl non terminal can be annotated See Section 4 9 for annotations of declarations As in the GRGEN NET model language see note 5 every declaration is also a definition Using an identifier before defining it is allowed Every used identifier has to be defined exactly once
78. e prev lt next ipr oO 0 ND 0 PR oa N HM t Rh e pap o FH replace T Ir Rh pp oa 5 7 Subpattern rewriting 65 EXAMPLE 40 This is an example for rewrite parameters connecting every node on an iterated path to a common node i e the local rewrite graph to the containing rewrite graph It can t be simulated by subpattern parameters which get defined at matching time because the common element is only created later on at rewrite time 1 pattern ChainFromToReverseToCommon from Node to Node replace common Node o 0 VN 9 ao Pp W N y y vy y y y y y b es e H E B S E EEE E ow oO A SSS S oO Aa nn oa PB W N Hr a O alternative rec from gt intermediate Node cftrtc ChainFromToReverseToCommon intermediate to replace from lt intermediate from gt common cftrtc common base 1 from gt to replace from lt to from gt common to gt common I replace from to J rule chainFromToReverseToCommon from Node to Node cftrtc ChainFromToReverseToCommon from to modify common Node cftrtc common 5 7 1 Deletion and Preservation of Subpatterns In addition to the fine grain dependent replacement subpatterns may get deleted or kept as a whole 66 Nested and Subpatterns SubpatternOccurence Tat HO e O a OO In modify mode they are kept by default but deleted if the name of th
79. e 2 4 See Chapter 4 for the rule set language reference In detail The rule set file consists of a number of rules and tests each of them bearing a name like forwardTransition Rules contain a pattern expressed as several semicolon separated pattern statements and a modify part or a rewrite part Tests contain only a pattern they are used to check for a certain pattern without doing any rewrite operation If a rule is applied GRGEN NET tries to find the pattern within a host graph for instance within the graph we created in Section 2 3 Of course there could be several matches for a pattern GRGEN NET will choose one of them arbitrarily Figure 2 4 also shows the syntax x NodeType for nodes and e EdgeType gt for Edges which we have already seen in Section 2 3 There are also statements like FinalState or EpsilonTransistion gt i e we are searching for a node of type FinalState resp an edge of type EpsilonTransition but we are not assigning these graph elements to a name like x or e above Defining of names is a key concept of the GRGEN NET rule sets names work as connection points between several pattern statements and between the pattern and the replace modify part As a rule of thumb If you want to do something with your found graph element define a name otherwise an anonymous graph element will do fine Also have a look at example 7 on page 32 for additional pattern specifications The difference between a repl
80. e a loop e Edge gt The edge e is certainly not a loop Although both the pattern part and the replace modify part use graphlets there are subtle differences between them These concern the TypeConstraint and Retyping clause plus the allowed arrow tips for edges 4 2 Rules and Tests The structure of a rule set file is as follows RuleSet FileHeader Test Declaration RuleDeclaration SubpatternDeclaration FileHeader DR WEA u kin A rule set consists of the underlying graph models and several rewrite rules and tests subpatterns will be introduced in 5 5 Additionally you may include further rule set files without using directives we prefer to suffix them with gri in this case In case of multiple graph models GRGEN NET uses the union of these models In this case beware of conflicting declarations There is no built in conflict resolution mechanism like packages or namespaces for models If necessary you can use prefixes as you might do in C TestDeclaration ActionSignature 32 Rule Set Language Some graphlets ode SE Ze SS x Node gt 0 A o gt lt cel stem ni Node e2 Edge gt e3 Edge gt e4 Edge gt eb Edge gt n1 ni gt n2 Node iL oa al gt lt lt gt e e Edge gt S een On lt lt e gt And some illegal graphlets e Edge gt e gt Would affect redirecting of edge e A Gee ur Would affect
81. e a sequence of rewrite rules out of them For o 0 XA 9 oa FF O N Hr O 11 21 51 2 4 The Rewrite Rules using StateMachine test checkStartState x StartState negative x y StartState test checkDoublettes negative x State e Transition gt y State hom x y x doublette Transition gt y if typeof doublette typeof e if typeof e EpsilonTransition e Trigger doublette Trigger rule forwardTransition x State EpsilonTransition gt y State e Transition gt z State hom x y Z negative x exists Transition gt Z if typeof exists typeof e if typeof e EpsilonTransition e Trigger exists Trigger modify x forward typeof e gt z eval forward Trigger e Trigger rule addStartFinalState x StartState EpsilonTransition gt FinalState modify y StartFinalState lt x gt emit Start state x id mutated into a start and final state rule addFinalState x State EpsilonTransition gt FinalState if typeof x lt SpecialState modify y FinalState lt x gt rule removeEpsilonTransition EpsilonTransition gt replace Figure 2 4 Rule set for removing e transitions 17 18 Quickstart instance we don t want to forward just one e transition as forwardTransition would do we want to forward them all Such a rule composing is called graph rewrite sequence
82. e declared sub pattern entity is mentioned within a delete statement In replace mode they are deleted by default but kept if the name of the declared subpattern entity is mentioned using occurence same as with nodes or edges rule R mi Method m2 Method tp1 TwoParameters m1 tp2 TwoParameters m2 replace tpl is kept tp2 not included here will be deleted tp1 or tp2 would apply dependent replacement 10 m1 m2 al T 12 Oi o E gt SS OE a You may even give a SubpatternEntityDeclaration within a rewrite part which causes the subpattern to be created but this employment has several issues which can only be overcome by introducing explicit creation only subpatterns so you better only use it if you think it should obviously work and you are willing to adapt your code in a later version attern ForCreationOnly mp Method some complex pattern you want to instantiate several times connecting it to the mp handed in m Method modify ForCreationOnly m instantiate pattern ForCreationOnly 5 8 Regular Expression Syntax In addition to the already introduced syntax for the nested patterns with the keywords negative independent alternative iterated multiple and optional there is a more 5 8 Regular Expression Syntax 67 lightweight syntax resembling regular expressions using it together with the subpatterns gives graph rewrite specifications which look
83. e g arithmetic expressions to the attributes Retyping of nodes edges a more general version of casts known from common programming languages Creation of new nodes edges of only dynamically known types 1 3 Features of GRGEN NET 3 Two modes of specification A rule can either express changes to be made to the match or replace the whole match Embedded graph rewrite sequences capable of calling other rules with access to the nodes edges of the rule Emitting user defined text to stdout or files during the rewrite steps A rewrite part for the nested patterns and subpatterns so that complex structures can not only get matched but also get rewritten Visited flags which can be written here in addition to reading them in the pattern language Parameter passing out of rules e The rule application control language grs graph rewrite sequences supports Logical and sequential connectives Loops Rule execution Variable handling Extended control e g decisions transactions indeterministic choice Visited flags management Storages i e sets and maps capable of storing graph elements and allowing element wise iteration These were the features of the core of GRGEN NET System the generator grgen exe and its languages plus its runtime environment libGr In addition the GRGEN NET system offers a shell application the GRSHELL which features commands for e gra
84. eType Oe a NodeEdgeType Within a rule graph element parameters are treated as graph elements of the pattern just predefined But in contrast to pervious versions it is the task of the user to ensure the elements handed in satisfy the interface i e parameters must not be null and must be of the type specified or a subtype of the type specified If you need more flexibility and want to call the rule with parameters not fullfilling the interface you can append an input type specification to the relevant parameters which consists of the type to accept at the action interface or null or both enclosed in left and right angles If the input type specification type is given but the more specific pattern element type is not satisfied matching simply fails If null is declared in the input type specification and given at runtime the element is searched in the host graph Don t use null parameters unless you need them because every null parameter doubles the number of matcher routines which get generated Non graph element parameters must be prefixed by the var or ref keyword VarType is one of the attribute types supported by GRGEN NET 6 1 The primitive types require the var prefix and are handed in by value the generic types require the ref prefix and are handed in by reference Please note that the effect of assigning to a var ref parameter in eval see 4 4 is undefined concerning the parameters as well as the argument they are onl
85. elements of the graph and returns the id of the visited flag integer number starting at 0 Afterwards the visited flag of the id can be read and written within the rules by the visited expression and the visited assignment as well as by the visited flag reading and writing rewrite factors The first visited flags are stored in some excess bits of the graph elements and are thus essentially for free but if this implementation defined space is used up completely the information is stored in graph element external dictionaries Flag deallocation By vfree frees the space previously allocated for the visited flag afterwards you must not access it anymore The value stored in the variable must be of integer type stemming from a previous allocation Flag writing By e visited f b sets the visited status of the flag given by the flag id variable 90 Rule application control language XGRS f of the graph element e to the given boolean value b visited flags are normally written by rules of the rule language Flag reading By e visitedlf returns the visited status of the flag given by the flag id variable f of the graph element e visited flags are normally read by tests and rules of the rule language Flag resetting By vreset resets the visitor flag given by the flag id variable in all graph elements 71 7 Storages Storages are variables of set or map type used in the sequences in contrast to the sets in the gr
86. ely Table 8 1 GRSHELL debug commands Make sure that the path to your yComp jar package is set correctly in the ycomp shell script within GRGEN NET s bin directory 8 4 Backend Commands 115 We demonstrate the debug commands with a slightly adjusted script for the Koch snowflake from GRGEN NE T s examples see also Section 9 1 The graph rewriting sequence is 1 debug xgrs makeFlakei amp beautify doNothing amp makeFlake2 amp beautify 1 YCOMP will be opened with an initial graph resulting from grs init 4 gel 5 Edgel SN 3 Edgel We type d etailed step to apply makeFlake1 step by step resulting in the following graphs C Edge2 3 Edgel a A 9 Edge2 A EdgeSpe 4 Edgel de 5 Edgel 9 Edge2 sider 5 3 Edge1 7 C Edge2 N 4 Edgel es B Edge2 The following table shows the break points of further debug commands entered one after another S makeFlakel beautify doNothing beautify beautify makeFlake2 8 4 Backend Commands GRGEN NET is built to support multiple backends implementing the model and action interfaces of libGr This is roughly comparable to the different storage engines MySQL offers Currently only one backend is available the libGr search plan backend or short LGSP Backend 116 GrShell Language 8 4 1 Backend selection and custom commands Parameters Selects a backend t
87. ements from mapl without the elements with a key contained in map2 Table 6 11 Binary map operators in ascending order of precedence The binary map operators require the left and right operands to be of identical type map lt S T gt with one exception for map difference this operator accepts for a left operand of type map lt S T gt a right operand of type set lt S gt too The operator x in s denotes map domain membership x dom s returning whether the domain of the set contains the given element as boolean The operator m x denotes map lookup i e it returns the value y which is stored in the map m for the value x domain value x is mapped by the mapping m to range value y The value x must be in the map i e x in m must hold There are several operations on maps available in method call notation MethodSelector these are size returns the number of elements in the map as int domain returns the set of elements in the domain of the map as set lt S gt for map lt S T gt range returns the set of elements in the range of the map as set lt T gt for map lt S T gt peek num returns the key of the element which comes at position num int in the sequence of enumeration as S for map lt S T gt 6 9 Type Expressions 1 The declarative rule language comes without the imperative map m add x y or m rem x methods known from the XGRS and without a mapping assignment operator m x y map lookup returns
88. ern WithCardinality NestedBody 5 3 Pattern Cardinality 53 NestedBody 7 PatternStatement B The blocks allow to specify how often the nested pattern opening a scope is to be matched Matching will be carried out eagerly i e if the construct is not limiting the number of matches and a further match is possible it will be done The nested body will be explained in Section 5 6 N estedRewriting The iterated block is matching the contained subpattern as often as possible succeeding even in the case the contained pattern is not available thus it will never fail It was included in the language to allow for matching breadth splitting structures as in capturing all methods of a class in a program graph test methods c Class iterated c gt m Method Ir N ODO oa A O N E The multiple block is working like the iterated block but expects the contained subpattern to be available at least once if it is not matching of the multiple block and thus its enclosing pattern fails test oneOrMoreMethods c Class multiple c gt m Method TS O The optional block is working like the iterated block but matches the contained subpattern at most once further occurences of the subpattern are left unmatched If the nested pattern is available it will get matched otherwise it won t matching of the optional block will succeed either way 54 Nested
89. es for using GRGEN NET with GrShell The examples api subdirectory contains several examples of how to use GRGEN NE T from the API In case you want to contribute and got further questions don t hesitate to contact us via email to grgen at the host given by ipd info uni karlsruhe de Ass00 Bat05a Bat05b Bat06 BG09 BKGos Buc08 CMR 99 Dew84 Dia D r95 EHKt 99 ERT99 Fuj07 BIBLIOGRAPHY Uwe Assmann Graph rewrite systems for program optimization ACM Transac tions on Programming Languages and Systems TOPLAS 22 4 583 637 2000 Gernot Veit Batz Graphersetzung f r eine Zwischendarstellung im Ubersetzer bau Master s thesis Universitat Karlsruhe 2005 Veit Batz Generierung von Graphersetzungen mit programmierbarem Suchal gorithmus Studienarbeit 2005 Gernot Veit Batz An Optimization Technique for Subgraph Matching Strate gies Technical Report 2006 7 Universitat Karlsruhe Fakult t f r Informatik April 2006 Paul B daride and Claire Gardent Semantic Normalisation a Framework and an Experiment In Eighth International Conference on Computational Seman tics 2009 Gernot Veit Batz Moritz Kroll and Rubino Gei A First Experimental Evalu ation of Search Plan Driven Graph Pattern Matching In Applications of Graph Transformation with Industrial Relevance AGTIVE 07 Proceedings 2008 pre liminary version submitted to AGTIVE 2007 Sebast
90. etter performing matchers based on this information is shown in examples api BusyBeaverExample BusyBeaverExample cs e How to compile a grg specification at runtime and dump a graph for visualization in vcg format on the API level is shown in examples api HelloMutex HelloMutex cs e How to access the annotations at API level is shown in examples api MutexDirectExample MutexDirectExample cs e How to communicate with yComp on the API level from your own code is shown in examples api YCompExample YCompExample cs LIBGR allows for splitting a rule application into two steps Find all the subgraphs of the host graph that match the pattern first then rewrite one of these matches By returning a collection of all matches the LIBGR retains the complete graph rewrite process under control As a LIBGR user have a look at the following methods of the TAction interface IMatches Match IGraph graph int maxMatches objectl parameters object l Modify IGraph graph IMatch match In C this might look like IMatches myMatches myAction Match myGraph 1 null 1 get all the matches for int i 0 i lt myMatches NumMatches i if inspectCarefully myMatches GetMatch i 1 myAction Modify myGraph myMatches GetMatch i break 132 Application Programming Interface While C allows input arguments values to be of a subtype of the declared interface parameter type 00 it requires that the argument variables for the
91. executed or 2 if a validate with exitonfailure failed 3n is an increasing number 1 8 Development goals 9 Options N Enables non debug non gui mode which exits on error with an error code instead of waiting for user input C Execute the quoted GRSHELL commands immediately before the first script file Instead of a line break use a double semicolon to separate commands Requires NET 2 0 or above or Mono 1 2 3 or above 1 7 3 LibGr dll The LIBGR is a NET assembly implementing GRGEN NE T s API See the extracted HTML documentation for interface descriptions at http www grgen net doc API_2_6 a short introduction is given in chaper 10 1 7 4 yComp jar YComP KBG 07 is a graph visualization tool based on YFILES yWo07 It is well integrated and shipped with GRGEN NET but it s not a part of GRGEN NET YCOMP implements several graph layout algorithms and has file format support for VCG GML and YGF among others Usage Usually YComP will be loaded by the GRSHELL You might want to open YCOMP manually by typing java jar yComp jar lt graph file gt Or by executing the batch file ycomp under Linux ycomp bat under Windows which will start YCOMP on the given file with increased heap space The graph file may be any graph file in a supported format YCOMP will open this file on startup Hints The layout algorithm compiler graph yCOMP s default setting a version of hierarchic optimized for graph based compi
92. first time you execute the script it might take a while because GRGEN NET has to compile the meta model and the rule set into NET assemblies The graph viewer YCOMP opens and after clicking the blue layout graph button on the very right side of the button bar you get a window similiar to figure 2 3 see also Section 1 7 4 The graph looks still a bit confusing In fact it is quite normal that YCOMP s automatic layout algorithm needs manual adjustments Quit YCOMP and exit the GRSHELL by typing exit You ll find the source code of this quick start example shipped with the GRGEN NET package in the examples FiniteStateMachine directory 2 3 Creating Graphs ua graph removeEpsilons StateMachineGraph new StartState S id 0 new FinalState F id 3 new State 1 id 1 new State 2 id 2 new S Transition Trigger a gt 1 new 0 1 Transition Trigger b gt 2 new 2 Transition Trigger c gt F new S EpsilonTransition gt 2 new 1 EpsilonTransition gt F new S EpsilonTransition gt F o A ND ow A UU N Rh e e ke Hm e N F O show graph ycomp Figure 2 2 Constructing a state machine graph in GRSHELL yComp Version 1 3 4 tmpgraph0 vcg File Edit View Navigate Layout Help Rana Je XD 48 9 Ela AK ED F FinalState ion Find EpsilonTransition q _ _ Next Options 5 EpsilonTransition sition Eu Ro
93. flexibility of the old input parameters semantics of silently failing rule application on a wrong type you must declare it explic itly with the syntax r x ExactType lt InexactType gt then the rule parameter in the exact interface will be of type InexactType Normally you want to use the type safe interface of the generated code as it is much more convenient Only if your application must get along with models and actions unknown before it is compiled you have to fall back to the generic interface An extensive example showing how to cope with the latter is shipped with GRGEN NET in form of the GrShell Here we ll show a short example on how to use GRGEN NET with the type safe API further examples are given in the examples api folder of the GRGEN NET distribution We ll start with including the namespaces of the libGr and the lgsp backend shipped with GRGEN NET plus the namespaces of our actions and models generated from Foo grg using de unika ipd grGen libGr using de unika ipd grGen lgsp using de unika ipd grGen Action_Foo using de unika ipd grGen Model_Foo Then we create a graph with model bound at generation time and create actions to operate on this graph Afterwards we create a single node of type Bar in the graph and save it to the variable b Finally we apply the action bar Bar x Bar to the graph with b as input receiving the output as well The rule is taken from the actions via the member named as the action Fo
94. g or skipping through the sequence exec tion there are breakpoints and choicepoints available toggled with the b and c commands which are only processed when they are reached but on the other hand are also processed if a user command would skip them The break points halt execution focus the reached sequence and cause the debugger to wait for further commands e g d to inspect the rule execution en detail versus s for just applying it The choice points halt execution focus the reached sequence in magenta and ask for some user input after the input was received exe cution continues according to the command previously issued Both break points and choice points are denoted by the modifier The modifier works as a break point if it is given before a rule an all bracketed rule a variable predicate or the constants true false The 7 modifier works as a choice point if it is appended to the randomize modifier switching a random decision into a user decision This holds for the binary operators the random match selector of all bracketed rules the random all of operators and the one of set braces The concept behind this is you need some randomization for simulation purposes then use the randomize modifier You want to force a certain decision overriding the random decision to try out another execution path while debugging the simulation flow then modify the randomize modifier with the user choice modifier
95. graph must be compatible to the gm model If the gz suffix is given the graph is expected to be zipped Normally you are not only interested in importing a GXL graph and viewing it but you want to execute actions on it The problem is that the actions are model dependent So in order to apply actions you must use a model override which works this way l new graph YourName grg This creates the model library lesp YourNameModel dll and the actions library lgsp YourNameA ctions dll which depends on the model library generated from the using YourName 2 import InstanceGraphOnly gxl YourName gm This imports the instance graph from the gxl but uses the model specified in Your Name gm it must fit to the model in the gxl in order to work 3 select actions lgsp YourNameActions d1l This loads the actions from the actions library in addition to the already loaded model and instance graph cf 8 2 8 4 Now you are ready to use the actions Further formats available for import are ecore plus xmi These are formats common to the model transformation community which are not directly geared towards graphs so they can t be imported directly Instead during the import process an intermediate gm is written which is equivalent to the ecore given you may inspect it to see how the content gets mapped the importer maps classes to GrGen node classes their attributes to corresponding GrGen attributes and their references t
96. gt e gt x Node Illegal redirection of e x N e E gt y N x e gt r lhs x gt rhs 2 Deletion of y Hence del etion of e Table 4 1 Definition of the preservation morphism r 4 4 2 Specification Modes for Graph Transformation For the task of rewriting GRGEN NET provides two different modes A replace mode and a modify mode Replace mode The semantics of this mode is to delete every graph element of the pattern that is not used occur in the replace part keep every graph element that is used and create every additionally defined graph elements Using means that the name of a graph element occurs in a replace graphlet Attribute calculations are no using occurrences In Example 10 the nodes varnode and n3 will be kept The node n1 is replaced by the node n5 preserving n1 s edges The anonymous edge instance between n1 and n2 only occurs in the pattern and therefore gets deleted See Section 4 4 1 for a detailed explanation of the transformation semantics Modify mode The modify mode can be regarded as a replace part in replace mode where every pattern graph element is added occurs before the first replace statement In particular all the anonymous graph elements are kept Additionally this mode supports the delete operator that deletes every element given as an argument Deletion takes place after all other rewrite operations Multiple deletion of the same graph element is allowed but pointless a
97. h elements are alive Specifically both of them are available for evaluation a respective evaluation could e g look like this eval y b 2 x i 42 f a e a Furthermore the source and destination types need not to be on a path in the directed type hierarchy graph rather their relation can be arbitrary However if source and destination 46 Rule Set Language type have one ore more common super types then the respective attribute values are adopted by the retyped version of the respective node or edge The edge specification as well as ReplaceNode supports retyping In Example 4 node n5 is a retyped node stemming from node ni Note that conceptually the retyping is performed after the SPO conform rewrite gd oo a WwW N The following rule will promote the matched city x from a City to a Metropolis keeping all its incident edges streets with exception of the matched street y which will get promoted from Street to Highway keeping all its adjacent nodes cities rule oneway x City y Street gt replace x_rt Metropolies lt x gt y_rt Highway lt y gt gt 4 9 Annotations Identifier definitions can be annotated by pragmas Annotations are key value pairs IdentDecl Although you can use any key value pairs between the brackets only the identifier prio has an effect so far You may use the annotations to transmit information from the specification files to API level where they c
98. hat handles graph and rule representation Filename has to be a NET assembly e g lgspBackend d11 Comma separated parameters can be supplied optionally if so the backend must support these parameters By default the LGSPBackend is used List all the parameters supported by the currently selected backend The parameters can be provided to the select backend command SpacedParameters Executes a command specific to the current backend If SpacedParameters is omitted a list of available commands will be displayed for the LGSP backend see Sections 8 4 2 8 4 2 LGSPBackend Custom Commands The LGSPBackend supports the following custom commands analyzegraph ee Analyzes the current working graph The analysis data provides vital information for efficient search plans Analysis data is available as long as GRSHELL is running i e when the working graph changes the analysis data is still available but maybe obsolete Sets the maximum amount of possible pattern matches to Number This command affects the expression Rule If Number is less or equal to zero the constraint is reset If set to false it prevents deleted elements from getting reused in a rewrite i e it disables a performance optimization If set to true new elements may not be discriminable anymore from already deleted elements using object equality hash maps etc custom actions gensearchplan ser 8 4 Backend Commands 117 Creates a search pla
99. he host graph this only works in the GrShell in debug mode Each of the VarAssignment rewrite factors yields always true The variable in the variable predicate a sequence consisting of only a variable read must contain a boolean value a prepended attaches a break point to it The variable predicate together with the sequence result assignment allow to directly transmit execution results from one part of the sequence to another one A def term is successful iff all the variables are defined A yield term yields the variable values to the containing exec which can include the yielded values into the RHS pattern but as of now they are then only accesible from the rule return statement Yielding is only possible from compiled sequences It always succeeds assigning the output elements not returning from the sequence Preliminary implementation you get internal errors if yielded and expected types are not equal or if there is not a yield on any control flow path leaving the sequence 88 Rule application control language XGRS 1 5 Extended control ExtendedControl 7 RewriteSequence 3 The extended control constructs offer further rule application control in the form of conditional sequences transactions parenthesis sequence constants and indeterministic choice from a sets of rules or sequences The condition execution decision statement if executes the condition sequence and if it yielde
100. highway 4 Y Karlsruhe metropolis m 0 Edge u u nn 8 2 GRSHELL Commands 111 right side dumped with dump add node metropolis group Dy au d Declares the attribute AttributeName to be an info tag or short info tag Info tags are displayed like additional node edge labels in format Name Value or Value only for short info tags The keyword only excludes the subtypes of NodeType resp EdgeType In the following example river and jam are info tags A3 highway Jam False e AS north highway Jam False A5_south highway jam True dump Resets all style options dump set and dump add to their default values Small graphs allow for fast visual understanding but with an increasing number of nodes and edges they quickly loose this property The group commands are of outstanding importance to keep readability with increasing graph sizes e g for program graphs it allows to lump together expressions of a method inside the method node and attributes of the class inside the class node Additional helpers in keeping the graph readable are the capability to exclude elements from dumping the less hay in the stack the easier to find the needle the different colors and shapes to quickly find the elements of interest as well as the labels in fotags shortinfotags to display the most important information directly Choose the layout algorithm and the options delivering the best res
101. his low level pointer fiddling code can be generated automatically for you by GRGEN NET You specify your transformation task on a higher level of nodes connected by edges and rewrite rules of patterns to be searched plus modifications to be carried out and then let GRGEN NET generate the algorithmic core of your application There is nothing to gain from GRGEN NET if scalars lists and trees are sufficient to adequately model your domain which is the case for a lot of tasks in computing indeed but which is not the case for others which would be better modeled with graphs but aren t because of the cost of maintaining graph structures by hand The graph rewrite generator is not the right tool for you if you re searching for a visual environment to teach children programming it s a tool for software engineers Neither is it what you need if your graph structured data is to be interactively edited by an end user instead of being automatically transformed by rules the editor generator DiaGen Dia may be of interest in this case Introduction 1 3 Features of GRGEN NET The process of graph rewriting can be divided into four steps Representing a graph according to a model creating an instance graph searching a pattern aka finding a match perform ing changes to the matched spot in the host graph and finally selecting which rule s to apply where next We have organized the presentation of the features of the GRGEN NET
102. hnology and Economics March 2005 Gergely Varr Daniel Varr and Katalin Friedl Adaptive Graph Pattern Matching for Model Transformations using Model sensitive Search Plans In G Karsai and G Taentzer editors GraMot 2005 International Workshop on Graph and Model Transformations volume 152 of ENTCS pages 191 205 El sevier 2006 Winter Kullbach and Riediger An Overview of the GXL Graph Exchange Language Software Visualization International Seminar Dagstuhl Castle 2002 yWorks yFiles http www yworks com 2007 Keywords SubpatternOccurence 66 abstract 23 actions 112 117 add 103 110 111 alternative 54 analyze 116 analyzegraph 116 arbitrary 23 askfor 98 attributes 107 backend 116 bordercolor 109 by 110 class 24 clear 99 color 109 connect 25 const 23 26 copy 25 custom 112 116 117 dangling 33 debug 113 def 87 delete 40 66 99 106 directed 23 disable 113 dpo 33 dump 108 111 dumpsourcecode 117 echo 98 edge 24 106 107 109 111 edges 106 emit 47 85 99 emithere 63 enable 113 enum 22 eval 40 exact 33 36 exclude 110 exec 47 exit 98 INDEX exitonfailure 100 export 102 extends 24 25 for 92 gensearchplan 117 get 113 graph 99 102 108 116 group 110 help 97 hidden 110 hom 36 identification 33 if 36 88 import 102 103 in 75 76 90 92 include 31 98 independent 52 induced 33 36 infotag 111
103. iable 8 2 GRSHELL Commands This section describes the GRSHELL commands Commands are assembled from basic ele ments As stated before commands are terminated by line breaks Alternatively commands can be terminated by the symbol Like an operating system shell the GRSHELL al lows you to span a single command over n lines by terminating the first n 1 lines with a backslash Script lt end of file gt as 8 2 1 Common Commands ma Displays an information message describing all the supported commands A command Command displayed with has further help available which can be displayed with help Command 98 GrShell Language Quits GRSHELL If GRSHELL is opened in debug mode a currently active graph viewer such as YCOMP will be closed as well Executes the GRSHELL script Filename A GRSHELL script is just a plain text file containing GRSHELL commands They are treated as they would be entered interactively except for parser error If a parser error occurs execution of the script will stop immediately Prints Text onto the GRSHELL command prompt Variable OGak Type The askfor command interactively asks the user for a value of the specified type The entered value is type checked against the expected type and assigned to the given variable in case it matches If the type is a value type the user is prompted to enter a value literal with the keyboard If the type is a graph element type the user
104. ian Buchwald Erweiterung von GrGen NET um DPO Semantik und un gerichtete Kanten 6 2008 Studienarbeit A Corradini U Montanari F Rossi H Ehrig R Heckel and M Lowe Alge braic Approaches to Graph Transformation Part I Basic concepts and double pushout approach In Roz99 volume 1 pages 163 245 1999 A K Dewdney A computer trap for the busy beaver the hardest working turing machine Scientic American 251 2 10 12 16 17 8 1984 DiaGen Developer Team The Diagram Editor Generator http www unibw de inf2 DiaGen Heiko Dorr Efficient Graph Rewriting and its Implementation volume 922 of LNCS Springer Verlag New York Inc Secaucus NJ USA 1995 H Ehrig R Heckel M Korff M Lowe L Ribeiro A Wagner and A Corra dini Algebraic Approaches to Graph Transformation Part II Single Pushout A and Comparison with Double Pushout A In Roz99 volume 1 pages 247 312 1999 C Ermel M Rudolf and G Taentzer The AGG Approach Language and Environment In Roz99 volume 2 pages 551 603 1999 Fujaba Developer Team Fujaba Homepage http www fujaba de 2007 135 136 IGBG 06 IGDG08 Gei08 Hac03 HJGO08 HSESWO5 Jak08 JBK10 IKBG 07 KGO07 IKKO7 Kro Kro07 Lin02 LLMCO05 Application Programming Interface Rubino Gei Gernot Veit Batz Daniel Grund Sebastian Hack and Adam Sza lkowski GrGen A Fast SPO Based Graph Rewriting T
105. ified through the EdgeRefinement clause this type has to correspond to the arrow tips of course Graphlet Meaning e EdgeType gt The name e is bound to an edge of type EdgeType or one of its subtypes EdgeType gt 1 EdgeType gt gt 1 Edge gt lt gt 1 Edge gt or lt 1 Edge E 1 UEdge gt Gat 3 1 AEdge gt e gt The edge e is bound to As the above table shows edges can be defined and used separately i e without their incident nodes Beware of accidentally redirecting an edge The graphlets e Edge gt x Node e gt y Node are illegal because the edge e would have two destinations an anonymous node and y However the graphlets e gt x Node e Edge gt y Node are allowed but the first graphlet e gt is superfluous In particular this graphlet does not identify or create any copies neither if the graphlet occurs in the pattern part nor if it occurs in the replace part You cannot directly express the redirection of edges This a direct consequence of the SPO approach Redirection of edges can be simulated by either deleting and re inserting an edge or more indirect by re typing of nodes 4 2 Rules and Tests 31 Some attempts to specify a loop edge Graphlet Meaning x Node e Edge gt x The edge e is a loop x Node e Edge gt e gt x The edge e is a loop e Edge gt x Node The edge e may or may not b
106. ifiers and rule modifiers Such modifiers add certain conditions to the applicability of a pattern The idea is to match only parts of the host graph that look more or less exactly like the pattern The level of exact ness depends on the choosen modifier A pattern modifier in front of the rule test keyword is equivalent to one modifier statement inside the pattern containing all the specified nodes including anonymous nodes Table 4 2 lists the pattern modifiers with their semantics ta ble 4 3 lists the rule only modifiers with their semantics Example 14 explains the modifiers by small toy graphs Modifier Meaning exact Switches to the most restricitive mode An exactly matched node is matched if all its incident edges in the host graph are specified in the pattern induced Switches to the induced mode where nodes contained in the same induced statement require their induced subgraph within the host graph to be spec ified in order to be matched In particular this means that in general induced a b c differs from induced a b induced b c Table 4 2 Semantics of pattern modifiers Internally all the modifier annotated rules are resolved into equivalent rules in standard SPO semantics The semantics of the modifiers is mostly implemented by NACs In particular you might want to use such modifiers in order to avoid writing a bunch of NACs yourself The number of internally created NACs is bounded by O n for exact and
107. in spring 2003 with the diploma thesis of Sebastian Hack un der supervision of Rubino Gei At that time we needed a tool to find patterns in graph based intermediate representations used in compiler construction We imagined a tool that is fast expressive and easy to integrate into our compiler infrastructure So far Optimix Ass00 was the only tool that brought together the areas of compiler construction and graph rewriting However its approach is to feature many provable properties of the system per se such as termination confluence of derivations and complete coverage of graphs This is achieved by restricting the expressiveness of the whole formalism below Turing completeness Our tool GRGEN in contrast should be Turing complete Thus GRGEN NE T provides the user with strong expressiveness but leaves the task of proving such properties to the user To get a prototype quickly we delegated the costly task of subgraph matching to a relational database system Hac03 Albeit the performance of this implementation could be improved substantially over the years we believed that there was more to come Inspired by the PhD thesis of Heiko D rr D r95 we reimplemented our tool to use search plan driven graph pattern matching of its own This matching algorithm evolved over time Sza05 Bat05b BatO5a Bat06 BKGO08 and has been ported from C to C KG07 Kro07 In the year 2005 Varr VVF06 independently proposed a similar search plan ba
108. in the independent would not get matched if it would go through the host graph node matched to b as it is locked by the isomorphy constraint With recursive subpatterns you can already capture neatly structures extending into depth as iterated paths and also structures extending into breadth as forking patterns although the cardinality statements are often better suited to this task But combined with an iterated block you may even match structures extending into breadth and depth like e g a hierarchy of classes i e match a spanning tree in the graph giving you a very powerful and flexible notation to capture large complex patterns built up in a structured way from simple connected pieces as e g abstract syntax trees of programming languages If you are working with hierarchic structures like that you might be intersted in the capa blities of GrShell yComp for nested layout as described and shown in 8 2 7 32 60 Nested and Subpatterns II a A O N e pattern SpanningTree root Class iterated 4 root lt extending next Class SpanningTree next 7 5 6 Nested Pattern Rewriting Until now we focused on the pattern matching of nested and subpatterns but we re not only interested in finding patterns combined from several pattern pieces we want to rewrite the pattern pieces too This does not hold for the application conditions which are pure conditions but for all the other language
109. ing formally about the language Platform Independence is achived by using languages compiled to byte code for virtual machines backed by large standardized libraries specifically Java and C This should prevent the fate of the grandfather of all graph rewrite systems PROGRES SWZ99 which achieved a high level of sophistication but is difficult to run by now or simply outdated General Purpose Graph Transformation in contrast to special purpose graph transformation A lot of other graph based tools are geared towards special purpose applications e g verification GROOVE Ren04 or biology XL KK07 or model transformation VIATRA2 VB07 This means that design decisions were taken to ease uses in this application areas at the cost of rendering uses in other domains more difficult And that features were added in a way which just satisfies the needs of the domain at hand instead of striving for a more general solution which would have caused higher costs at designing and implementing this features While the old GRGEN was built as a special purpose compiler construction tool for internal use optimizations on the graph based compiler intermediate representation FIRM see www libfirm org the new GRGEN NET was built from the beginning as a general purpose graph transformation tool for external use to be used in areas as diverse as computer linguistics software engineering computational biology or sociology for reasoning
110. ions y o AttributeDeclarations D Defines a new edge type Edge types can inherit from other edge types defined within the same file If the extends clause is omitted Edge Type will inherit from the built in type Edge Optionally edges can possess attributes A connection assertion specifies that certain edge types should only connect specific nodes a given number of times see Section 3 1 1 It is not forbidden to create graphs that are invalid according to connection assertions GR GEN NET just enables you to check whether a graph is valid or not See also Section 8 2 2 validate Connection Assertions connect NodeConstraint NodeConstraint 3 2 Type Declarations 25 NodeConstraint E MultiplicityConstraint y MultiplicityConstraint B ToT umber RangeConstraint RangeConstraint ey A connection assertion is denoted as a pair of node types optionally with their multiplicities It allows you to specify the node types an edge may connect and the multiplicities with which such edges appear on the nodes It is best understood as a simple pattern of the form cf 4 1 1 SourceNodeType EdgeType gt TargetNodeType of which every occurrence in the graph is searched In contrast to a real such pattern and the node types only edges of exactly the given edge type are taken into account Per node of SourceNodeType or a subtype it is counted how often it was covered by a match of the pattern starting at it
111. is 107 iterated 53 labels 109 layout 113 modify 40 56 60 62 multiple 53 nameof 78 negative 50 new 99 104 node 24 106 107 109 111 nodes 106 null 34 num 106 off 98 109 on 98 109 only 100 106 107 109 111 open 99 optimizereuse 116 option 113 optional 53 options 113 pattern 56 quit 98 randomseed 99 139 140 redirect 99 ref 34 replace 40 56 60 62 reset 111 return 37 rule 33 save 102 select 99 112 116 set 109 113 setmaxmatches 116 shape 109 shortinfotag 111 show 97 99 106 108 112 116 silence 98 specified 100 strict 100 sub 107 super 107 test 33 textcolor 109 time 99 type 107 typeof 44 77 types 106 107 undirected 23 using 31 validate 25 100 valloc 89 var 34 97 vfree 89 visited 41 78 89 vreset 89 with 110 withvariables 102 xgrs 100 112 113 Non Terminals ActionSignature 33 AlternativePattern 54 Assignment 41 AttributeDeclaration 26 AttributeOverwrite 26 Attribute Type 26 Attribute Value 106 Attributes 106 BoolExpr 71 CastExpr 78 ClassDeclaration 23 Command 97 ConnectionAssertion 25 Constant 79 Constructor 106 Application Programming Interface Continuation 28 EdgeClass 24 EdgeRefinement 30 EnumDeclaration 22 ExecStatement 47 Expression 71 ExtendedControl 88 FileHeader 31 FloatExpr 73 GraphElement 96 GraphModel 21 GraphRewriteSequence 112 113 Graphlet 28
112. is prompted to enter the graph element by double clicking in yComp Note that in this case the debug mode must have been enabled before The command is equivalent to debug xgrs Variable 7 Type x askfor int asks the user to enter an integer value pressing 4 then 2 then enter will do fine x askfor Node asks the user to select a graph element in yComp double clicking any node will do fine DH Gommendtine CommandLine is an arbitrary text the operating system attempts to execute On a Linux machine you might execute 1 sh c ls l grep stuff silence 7 Switches the new node edge created deleted messages on default or off Switching them off allows for much faster execution of scripts containing a lot of creation commands 8 2 GRSHELL Commands 99 Number Sets the random seed to the given number for reproducible results when using the operator prefix or the random match selector whereas time sets the random seed to the current time in ms redirect emit Filename Redirects the output of the emit statements in the rules from stdout to the given file redirect emit Redirects the output of the emit statements in the rules to stdout again 8 2 2 Graph Commands Creates a new graph with the model specified in Filename Its name is set to Text The model file can be either source code e g turing machineModel cs or a NET assembly e g lgsp turing_machineModel d11 It
113. ity node class GhostTown extends AbandonedCity You will be able to create nodes of type GhostTown but not of type City or AbandonedCity However nodes of type GhostTown are also of type AbandonedCity as well as of type City and they have the attribute Size hence The keyword const indicates that rules may not write to attributes see also Section 4 4 eval However such attributes are still writable by LIBGR and GRSHELL directly This property applies to attributes defined in the current class only It does not apply to inherited attributes The const property will not be inherited by subclasses either If you want a subclass to have the const property you have to set the const modifier explicitly The keywords arbitrary directed and undirected specify the direction attribute of an edge class and thus its inheritance An arbitrary edge inherits from AEdge it is always abstract and neither directed nor undirected A directed edge inherits from Edge An undirected edge inherits from UEdge If you do not specify any of those keywords a directed edge is choosen by default See also Section 3 1 1 24 Graph Model Language NodeClass a A i KO Defines a new node type Node types can inherit from other node types defined within the same file If the extends clause is omitted NodeType will inherit from the built in type Node Optionally nodes can possess attributes EdgeClass La Be o ConnectionAssert
114. izations Node and Edge of GraphElement require the corresponding graph element to be a node or an edge respectively We insert a node anonymously and with a constructor see also Section 8 2 5 gt new graph lib lgsp TuringModel d1l G New graph G of model Turing created insert an anonymous node it will get a persistent pseudo name gt new State New node 0 of type State has been created gt delete node 0 oO a y QA a FP Ww N Hr and now with constructor gt new v State start new node start of type State has been created Now we have a node named start and a variable vu assigned to start Rh e pop MW N fF OO 8 2 GRSHELL Commands 97 Persistent names will be saved save graph see Section 8 2 4 and exported and if you visualize a graph dump graph see Section 8 2 4 graph elements will be labeled with their persistent names Persistent names have to be unique for a graph the graph they belong to GraphElement ae Assigns the variable or persistent name GraphElement or literal to Variable If Variable has not been defined yet it will be defined implicitly As usual for scripting languages variables have neither static types nor declarations The variables known to GRSHELL are the graph global variables see 7 for the distinction between graph global and sequence local variables Ghow war Variable Prints the content of the specified var
115. k y y typeof x gt a Remember that we have several subtypes of street By the aid of the typeof operator the reverse edge will be automatically typed correctly the same type as the one way edge This behavior is not possible without the typeof operator 4 8 Retyping In addition to graph rewriting GRGEN NET allows graph relabeling LMS99 too we prefer to call it retyping Nodes as well as edges may be retyped to a different type attributes common to the initial and final type are kept The target type does not need to be a subtype or supertype of the original type Retyping is useful for rewriting a node but keeping its incident edges without it you d need to remember and restore those Syntacically it is specified by giving the original node enclosed in left and right angles Retyping Met O Pattern LHS Replace RHS r L R Meaning x Nis y N2 lt x gt r lhs x gt rhs r Preserve x then retype x from Ni to N2 and bind name y to retyped version of x esEl f E2 lt e gt r lhs e gt rhs e Preserve e then retype e from El to E2 and bind name f to the retyped version of e Table 4 4 Retyping of preserved nodes and edges Retyping enables us to keep all adjacent nodes and all attributes stemming from common super types of a graph element while changing its type table 4 4 shows how retyping can be expressed both for nodes and edges Retyping differs from a type cast During replacement both of the grap
116. ks 31 1 DOS TIMES on eee sepamos Type Declarations 3 2 1 Attribute Types 4 Rule Set Language 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 Building Blocks 4 1 1 Graphlets Rules and Tests Pattern Part Replace Modify Part 4 4 1 Implicit Definition of the Per ee r 4 42 Specification Modes for Graph Transformation Ll DIM ne ewe eee ED ES Rule and Pattern Modifiers Static Type Constraint Exact Dynamic Type Retyping Annotations 4 10 Imperative usa CONTENTS O OO ONN Clo BR NY FF R 13 13 14 14 16 18 19 19 ESTATE 21 2l EE eo ea ae os 26 2 27 raras 28 31 36 38 ae ee ee 38 soe eee e ep eeaes 39 ENEE 40 42 42 44 45 46 47 5 Nested and Subpatterns 49 5 1 Negative Application Condition NAC 2 2 2 2 50 5 2 Positive Application Condition PAC 2 2 2 2 2 2 52 Do Patten DARIA gt s s a s e a fo p ka woa S ee dos ane OZ 5 4 Alternative Patterns aaa ass e OA 5 5 Subpattern Declaration and en Entity bi Loss J 9d Recursive Patterns s cosas EMS ae 57 5 6 Nested Pattern Rewriting aaa 60 5 7 Subpattern rewriting se ee ee oe ee eee 0 5 7 1 Deletion and Preservation of en Ass 65 5 8 Regular Expression Syntax a ee ee 66 6 Types and Expressions 69 6 1 Built In Types u 2 65 we 0 ee He Ewe we we we we e 009 6 2 Expressions 1 1 we ee ee ee ee O
117. l null the object literal foo bar a constant set lt string gt constructor map lt string int gt n strVal m strVal gt m intVal n intVal intVal gt strVal fool gt 42 y a non constant map constructor with type prefix oO 0 ND a FF O N Hr E 6 11 Operator Priorities The priorities of all available operators are shown in ascending order in the table below the dots mark the positions of the operands the commas separate the operators available on the respective priority level 6 11 Operator Priorities 06 07 lt lt gt gt in lt lt 22 22 Table 6 12 All operators in ascending order of precedence 31 32 Types and Expressions CHAPTER 7 RULE APPLICATION CONTROL LANGUAGE XGRS Graph rewrite sequences GRS better extended graph rewrite sequences XGRS to distin guish them from the older graph rewrite sequences are a domain specific GRGEN NET lan guage used for controlling the application of graph rewrite rules They are available e as an imperative enhancement to the rule set language e for controlled rule application within the GRSHELL e for controlled rule application on the API level out of user programms If they appear in rules they get compiled otherwise they get interpreted Iff used within GRSHELL they are amenable to debugging Graph rewrite sequences are written down with a syntax similar to boolean and regular expressions The
118. languages e The e The e The according to this breakdown of graph rewriting graph model meta model language supports Typed nodes and edges with multiple inheritance on types Directed multigraphs including multiple edges of the same type Undirected and arbitrarily directed edges Node and edge types can be equipped with typed attributes like structs including powerful set and map types Connection assertions to restrict the shape of graphs Turing complete language for checking complex conditions pattern language supports Plain isomorphic subgraph matching injective mapping Homomorphic matching for a selectable set of nodes edges so that the matching is not injective Attribute conditions e g arithmetic boolean string or set expressions on the attributes Type conditions including powerful instanceof like type expressions Nested patterns specifying negative and positive application conditions as well as iterated optional or alternative structures Subpatterns for pattern reuse allowing via recursion to match substructures of arbitraty depth e g iterated paths and breadth e g multinodes Parameter passing to rules rewrite language supports Keeping adding and deleting graph elements according to the SPO approach Choosing out of three additional rule application semantics DPO or exact patterns only or induced subgraphs only Attribute re calculation assigning the result of
119. le deletion of the same graph element is allowed but pointless as well as deletion of just created elements pointless too Attribute Evaluation If a rule is applied then the attributes of matched and inserted graph elements will be recalculated according to the eval statements SubpatternRewriteA pplication will be explained in 5 7 4 4 Replace Modify Part 41 Assignment ToT O ia Ea O9 SetMapStateChange SetParameter MapParameter Several evaluation parts are allowed within the replace part Multiple evaluation statements will be internally concatenated preserving their order Evaluation statements have impera tive semantics In particular GRGEN NET does not care about data dependencies Evalu ation takes place before any graph element gets deleted and after all the new elements have been created You may read and write although this is pointless attributes of graph el ements to be deleted Assignment is carried out using value semantics even for entities of set lt K gt and map lt K V gt or string type The only exception is the type object there ref erence semantics is used In addition there are by ref parameters available which can be operated upon by the set map state change methods which allow to only partially change the set map by adding and removing elements resp pairs of elements they are especially useful for storages 1 e sets or maps containing nodes or edges The visited flag as
120. lement As with dpo this modifier applies only to rules Table 4 3 Semantics of rule only modifiers Host Graph Pattern Rule Effect cape MI Produces no match for exact nor induced x node gt y node Produces three matches for induced x y but no match for exact x y x node induced x Produces no match gt x gt e petten iab Produces no match in DPO mode modify delete x because of edge e 44 Rule Set Language TypeConstraint N CO 7 TypeExpr B TypeExpr A type constraint is used to exclude parts of the type hierarchy The operator is used to create a union of its operand types So the following pattern statements are identical Xil x T T1 Tn if typeof x gt T1 Qe amp amp typeof x gt Tn The type constraint T T2 T3 applied to the type hierarchy on the left side yields only the types T and T1 as valid 4 7 Exact Dynamic Type Type T O oO NodeOrEdge D The type of a graph element may be given by a type identifier or a typeof denoting the exact dynamic type of a matched graph element The element declaration el typeof x introduces a graph element of the type the host graph element x is actually bound to 4 8 Retyping 45 oO A ND wo PR OO N Hr a The following rule will add a reverse edge to a one way street rule oneway a Node x street gt y Node negative y typeof x gt a replace a c
121. ler intermediate representations may not be a good choice for your graph at hand Instead organic or orthogonal might be worth trying Use the rightmost blue play button to start the layout process Depending on the graph size this may take a while yComp Version 1 3 1 tmpgraph0 vcg e yComp Version 1 3 1 tmpgraph0 vcg File Edit View Navigate ETI Help File Edit View Navigate Layout Help A G f 80 t DADA 2 e HELA j Random 1D aDa9c XbA Hr A FER h Layout Options Hierarc hic gt Do Layout DR Organic Sees Select Edge Router aa nel oS u los le se Circular len es nn es eel ee e gene Route Edges F Tree gt pam a ul gt a z oes H Fold Subgraphs 2Q Diagonal a i po ec rre la la la Unfold Subgraph Aw Incrementa Hierarc hic eco gt gt gt mm an E e Compilergraph eo e e do So g Graph Analysi gt GE a a a N o Saye AD N GpianE u colo 0 Reverse dges AQF 0 dL ei GridNode Edge Classes ridNode Soc ns gt 103 GridNode Show All Edges PS 103 GridNode pa ro E le Adl idi 106 GridNode Reset All Reference Nodes 2 05 106 GridNode e ma o ec e len len 5109 Markedric APPEN 35 sseecranode Be ela An liste aaah elle AN I 10E GridNode 5 10E GridNode ial BE E TEE EE ARE 1 zum un un lA eo et et htt 114 MarkedGridN 114 MarkedGridN clan zn el ln on ul Haren mi eh sla _ Sll MarkedGridNe 11 MarkedGridNc m Ema o
122. like EBNF grammars with embedded actions Exceeding the more verbose syntax they offer constructs for matching the pattern a bounded number of times same notation as the one for the bounded iteration in the xgrs Table 5 1 lists the corresponding equivalent language constructs Example 5 8 is a version of the introductionary example 5 modified to use the new syntax iterated P multiple P optional P alternative 11 Pi 1k f Pk negative P independent P modify R R replace R R pe OT A 7 Table 5 1 Map of nested patterns in keyword syntax to regular expression syntax test method m Method lt n Name signature of method consisting of name m lt Variable and O n parameters AssignmentList m body consisting of a list of assignment statements o ND 0 A O N Hr pattern AssignmentList prev Node a O nothing or a linked assignment and again a list prev gt a Assign assignment node a target gt v Variable which has a variable as target Expression a and an expression which defines the left hand side AssignmentList a next one plz ye e e e e pa pp CoN OD a Bb O N e pattern Expression root Expr expression may be a binary expression of an operator and two expresions root lt expri Expr Expression expr1 root lt expr2 Expr Expression expr2 root lt Qperator or a unar
123. luation Table 6 4 Binary Boolean operators in ascending order of precedence to true the operator returns the second BoolExpr otherwise it returns the third BoolErpr 6 4 Relational Expressions The relational expressions compare enitites of different kinds mapping them to the type boolean The bind stronger than the boolean expressions but weaker than all the other non boolean expressions RelationalExpr The CompareOperator is one of the following operators Their semantics are type dependent For arithmetic expressions on int and float or double types the semantics is given by Table 6 5 by implicit casting they can also by used with all enum types String types boolean types and object types support only the and the operators for strings they denote whether the strings are the same or not on boolean values they denote equivalence and antivalence and on object types the tell whether the references are the same thus the objects identical For set and map expressions table 6 6 describes the semantics of the compare operators For type expressions the semantics of compare operators are given by table 6 7 the rule to remember is types grow larger with extension refinement An example is given in 6 9 12 Types and Expressions iff A is the same number as B iff A is a different number than B iff A is smaller than and not equal B iff A is greater than and not equal B iff A is smaller than or equal
124. meters of the rule Furtheron there is but meant only for internal use the class Action_bar implementing the exact action interface as well as the generic TAction interface from libGr it contains the generated matcher code searching for the patterns Moreover the namespace contains an action class FooActions implementing the abstract class de unika ipd grGen 1libGr BaseActions in fact de unika ipd grGen lgsp LGSPActions which supports iteration over the entities defined in the actions using further generic i e in exact interfaces from libGr Additionally at runtime it contains the instances of the actions singletons as member bar of the exact type IAction bar If you want to use the type safe interface your entry point is the member bar of type IAction_bar from FooActions or Action bar Instance Actions are used with named parameters of exact types If you want to use the generic interface your entry point is the method GetAction bar of the interface BaseActions implemented by FooActions returning an IAction Actions are used with object arrays for parameter passing 10 2 Interface to rules 129 The old generic interface of string names and entities of node edge and object type is im plemented with the new interface of exactly typed named entities Thus you will receive runtime exceptions when doing operations which are not type safe with the generic interface in contrast to GRGEN NET lt v2 5 If you need the
125. n and executable code from it for each rewrite rule Action using the data from analyzing the graph custom graph analyze Otherwise a default search plan is used Analyzing and search plan code generation themselves take some time but they can lead to massively faster pattern matching thus overall execution times the less uniform the type distribution and edge wiring between the nodes is the higher are the improvements to be expected During the analysis phase the host graph must be in a shape similar to its shape when the main amount of work is done there may be some trial and error steps at different time points needed to get the overall most efficient search plan A search plan is available as long as the current rule set remains loaded Specify multiple rewrite rules instead of using multiple commands for each rule to improve the search plan generation performance If set to true C files will be dumped for the newly generated searchplans similar to the keep option of the generator 118 GrShell Language CHAPTER 9 EXAMPLES 9 1 Fractals The GRGEN NET package ships with samples for fractal generation We will construct the Sierpinski triangle and the Koch snowflake They are created by consecutive rule applications starting with the initial host graphs BR 3 E0 N N 1 EO 5 E0 4 Edge ity Suge f d ss sanoden Eo for the Sierpinski triangle resp the Koch snowflake First of all we have to
126. n with normal parameters but elements created in the rewrite part of the user of the subpattern can only be handed in at rewrite time R eplaceStatement 5 7 Subpattern rewriting 63 SubpatternRewriteA pplication O o SubpatternOccurence emithere EE StringExpr O P The SubpatternRewriteApplication is part of a ReplaceStatement The subpattern rewrite application is given within the rewrite part of the pattern containing the subpattern entity declaration in call notation on the declared subpattern identifier The emithere statements are executed before the emit statements and in the order in between the subpattern rewrite applications they are specified syntactically oO nn wo A O N Hr e e e e e eE pa E Hm o 0 JO a A A O N e O EXAMPLE 38 This is an example for a subpattern rewrite application pattern TwoParametersAddDelete mp Method mp lt vi Variable mp lt Variable modify delete v1 mp lt Variable rule methodAndFurtherAddDelete m Method lt n Name tp TwoParametersAddDelete m modify 1 tpO trigger rewriting of the TwoParametersAddDelete instance 64 Nested and Subpatterns This is another example for a subpattern rewrite application reversing the direction of the edges on an iterated path pattern IteratedPathReverse prev Node optional prev gt next Node ipr IteratedPathReverse next replac
127. nt HexNum Is an int number in hexadecimal notation starting with Ox DoubleNum Is a double number in decimal notation with decimal point maybe postfixed with d FloatNum Is a float number in decimal notation with decimal point postfixed with f Quoted Text Is a string constant It consists of a sequence of characters enclosed by double quotes BoolLit Is a constant of boolean type i e one of the literals true or false NullLit Is the one constant of object type the literal null SetConstructor SEE 80 Types and Expressions MapConstructor and do The set map constructors are constant if only primitive type literals enum literals or constant expressions are used this is required for set map initializations in the model They are non constant if they contain member accesses which is the common case if used in rules If the type of the set map is given before the constructor the elements given in the type constructor are casted to the specified member types if needed and possible Without the type prefix all elements given in the constructor must be of the same type u Expression O Expression u EXAMPLE 46 Some examples of literals Apple ToffeeApple an enum literal 42 an integer number in decimal notation Oxdeadbeef an integer number in hexadecimal notation 3 14159 a double number 3 14159f a float number ve rule and Own ze vorld a text literal true a bool litera
128. o GrGen edge classes inheritance is transferred one to one and enumerations are mapped to GrGen enums class names are prefixed by the names of the packages they are contained in to prevent name clashes After this metamodel transformation the instance graph XMI adhering to the Ecore model thus adhering to the just generated equivalent GrGen graph model gets imported Furthermore you can give specify a grg containing the rules to apply using further rule and model files The importer was added for a GraBaTs challenge and is available as is it may or may not work for you if you need more it s on you to improve it An export is not available we coded the export we needed with emit statements Filename grg Filename aa Fiesp Imports the graph in the specified file and adds it to the current graph instead of overwriting the old graph with the new graph The FileSpec is of the same format as the file specification 104 GrShell Language in the other two imports The withvariables argument only yields an effect if the file to import contains variable specifications the content of old variables of the same name is overwritten 8 2 5 Graph Manipulation Commands Graph manipulation commands alter existing graphs they allow to create and delete graph elements and change attributes These are tasks which should be carried by the rules of the rule language the commands are mainly used as elementary instructi
129. oGraph graph new FooGraph FooActions actions new FooActions graph Bar b graph CreateNodeBar actions bar Apply graph b ref b input of type Bar output of type Bar 130 Application Programming Interface This is an example doing mostly the same as the previous example 56 in a slightly more complicated way allowing for more control Here we create the model separate from the graph then the graph with a model not bound at generation time We create the actions to apply on the graph and a single node of type Bar in the graph which we assign again to a variable b Then we get the action from the actions and save it to an action variable bar afterwards we use the action for finding all available matches of bar with input b which is different from the first version and remember the found matches in the matches variable with its exact type Finally we take the first match from the matches and execute the rewrite with it We could have inspected the nodes and edges of the match or their attributes before using element names prefixed with node_ edge_ or attribute names to get exactly typed entities IGraphModel model new FooGraphModel LGSPGraph graph new LGSPGraph model FooActions actions new FooActions graph Bar b Bar CreateNode graph IAction_bar bar Action_bar Instance IMatchesExact lt Rule_bar IMatch_bar gt matches bar Match graph 0 b bar Modify graph matche
130. onally to the variable assignment in rule embedded graph rewrite se quences you are also able to assign persistent names to parameters via Variable Text Graph elements returned by rules can be assigned to variables using Parameters Action The desired variable identifiers have to be listed in Parameters Graph elements required by rules must be provided using Action Parameters where Parameters is a list of variable identifiers For undefined variables see Section 4 2 Parameters 8 3 Graphical Debugger 113 8 3 Graphical Debugger The GRSHELL together with YCOMP build GRGEN NE T s graphical debugger 8 3 1 Debugging Related Commands Enables and disables the debug mode The debug mode shows the current working graph in a YCOMP window All changes to the working graph are tracked by YCOMP immediately Sets the default graph layout algorithm to Text If Text is omitted a list of available layout algorithms is displayed See Section 1 7 4 on YCOMP layouters The option version allows to specify layout options by name value pairs The available layout options can be listed by the following command debug get layout options Prints a list of the available layout options of the layout algorithm Forces re layout of the graph shown in yComp same as pressing the play button within yComp GraphRewriteSequence SimpleRewriteSequence This executes the graph rewrite sequence SimpleRewriteSequence in
131. onment libGr which offer the basic functionality of the system The second consists of the interactive command line GrShell and the graph viewer yComp which offer a rapid prototyping environment supporting graphical and stepwise debugging of programmed rule applications GRGEN NET is the successor of the GRGEN tool presented at ICGT 2006 GBG 06 The NE T postfix of the new name indicates that GRGEN has been reimplemented in C for the Microsoft NET or Mono environment Mic07 Tea07 it is open source licensed under LGPL3 www gnu org licenses lgpl html and available for download at www grgen net Starting as a compiler construction helper tool it has grown into a software development tool for general purpose graph transformation which offers the highest combined speed of development and execution for graph based algorithms through its declarative languages with automatic optimization 1 2 When to use GRGEN NET and when not You may be interested in using GRGEN NET if you have to tackle the task of transforming meshes of massively linked objects i e graph like data structures as is the case in e g model transformation computer linguistics or modern compiler construction any time there is more than one relation of interest in between the data entities your algorithm operates upon These tasks are traditionally handled by pointer structures and pointer structure navigation search and replacement routines written by hand t
132. ons in graph input and output Creates a new node within the current graph Optionally a variable Text is assigned to the new node If NodeType is supplied the new node will be of type NodeType and attributes can be initialized by a constructor Otherwise the node will be of the base node class type Node The GRSHELL can reassign variables This is in contrast to the rule language Chapter 4 where we use names Creates a new edge within the current graph between the specified nodes directed from the first to the second Node in the case of gt directed from the second to the first Node in the case of lt or undirected in the case of Optionally a variable Text is assigned to the new edge If Edge Type is supplied the new edge will be of type Edge Type and attributes can be initialized by a constructor Otherwise the edge will be of the base edge class type Edge for gt or UEdge for 8 2 GRSHELL Commands Constructor Attributes Attributes og Attribute Value f Attribute Value PrimitiveAttributeValue PrimitiveAttribute Value HeH k DoubleNum El E FloatNum s E Juoted Text j E BoolLit a NullLit SetConstr a MapConstr Gap OH Type PG gt Type PO e Expression o Expression y 105 106 GrShell Language A constructor is used to initialize a new graph element see new below A comma separated list of attribute declarations is supplie
133. oo cer a 1 a ee s u Soo mom 125 GridNode 128 MarkedGridN se rn LI a 132 MarkedGridN Yn 132 MarkedGridN v lt gt lt gt Requires Java Runtime Environment 1 5 or above 1 8 Development goals The development goals of GRGEN NET were 10 Introduction Expressiveness is achieved by powerful and declarative specification languages for pattern matching and rewriting by rewrite rules builing upon a rich graph model language In addi tion to the unmatched expressiveness of the basic actions the rule language now offers nested and subpatterns which allow to handle substructures of arbitrary depth and ar bitrary breadth declaratively within the rules by now even surpassing the capabilities of the VIATRA2 VB07 VHV08 graph rewriting tool the strongest competitor in rule expressiveness The rules can be combined by graph rewrite sequences a rule appli cation control language with variables and logical as well as iterative control flow it was recently extended by storages as pioneered by the VMTS LLMCO05 graph rewriting tool allowing for more concise and faster solutions Performance i e high speed at modest memory consumption is needed to tackle real world prob lems It is achieved by typing easening the life of the programmer by eliminating large classes or errors as well as speeding up the pattern matcher by the generative approach compiling the rules into executable code and by the heuristic
134. ool In Andrea Corra dini Hartmut Ehrig Ugo Montanari Leila Ribeiro and Grzegorz Rozenberg editors CGT volume 4178 of Lecture Notes in Computer Science pages 383 397 Springer 2006 Tom Gelhausen Bugra Derre and Rubino Gei Customizing GrGen NET for Model Transformation In GraMoT pages 17 24 2008 Rubino Gei Graphersetzung mit Anwendungen im bersetzerbau PhD thesis Universit t Karlsruhe Nov 2008 Sebastian Hack Graphersetzung f r Optimierungen in der Codeerzeugung Mas ter s thesis IPD Goos 12 2003 Berthold Hoffmann Edgar Jakumeit and Rubino Gei Graph Rewrite Rules with Structural Recursion 2nd Intl Workshop on Graph Computational Models GCM 2008 2008 http www info uni karlsruhe de papers GCM2008 pdf Richard C Holt Andy Sch rr Susan Elliott Sim and Andreas Winter GXL A sraph based standard exchange format for reengineering Science of Computer Programming 2005 Edgar Jakumeit Mit GrGen NET zu den Sternen Erweiterung der Regel sprache eines Graphersetzungswerkzeugs um rekursive Regeln mittels Stern eraphgrammatiken und Paargraphgrammatiken Master s thesis Universitat Karlsruhe jul 2008 Edgar Jakumeit Sebastian Buchwald and Moritz Kroll GrGen NET Interna tional Journal on Software Tools for Technology Transfer STTT 12 263 271 2010 10 1007 s10009 010 0148 8 Moritz Kroll Michael Beck Rubino Gei Sebastian Hack and Philipp Lei yComp http www
135. opolises to be connected by highways Now have a look at the following graph A3 highway A5_south highway AS _north highway trail street This graph is valid but not strict valid gt validate The graph is valid gt validate strict only specified The graph is NOT valid CAE city Eppstein highway A3 gt metropolis Frankfurt not specified Ea gt validate strict The graph is NOT valid CAE city Eppstein highway A3 gt metropolis Frankfurt not specified CAE metropolis Karlsruhe street trail gt metropolis Frankfurt not specified gt o A XA 9 wn Pp W N O 102 GrShell Language 8 2 4 Graph Input and Output Commands Dumps the current graph as GRSHELL script into Filename The created script includes e selecting the backend e creating a new graph with all nodes and edges including their persistent names e restoring the graph global variables e restoring the visualisation styles but not necessarily using the same commands you typed in during construction Such a script can be loaded and executed by the include command see Section 8 2 1 Filename Exports an instance graph in GRS grs grsi format which is a reduced GRSHELL script it can get imported and exported on API level10 3 without using the GRSHELL It contains the new graph command followed by new node commands followed by new edge commands If the gz suffix is given the graph is saved zipped If
136. ot 1 State ansition 2 State F FinalState ansition S StartState Figure 2 3 A first state machine 15 16 Quickstart This script starts with creating an empty graph of the meta model StateMachine which is referenced by the rule set removeEpsilons grg with the name StateMachineGraph There after we create nodes and edges The colon notation indicates a node or edge type Also note the inplace arrow notation for edges Edge gt resp EdgeType gt As you can see attributes of graph elements can be set during creation with a call like syntax The and notation is due to the fact that we have two kinds of names in the GRSHELL Namely we have graph variables which we did not use no graph variable is explicitly defined in this script and persistent names that denote a specific graph element Persistent names are set by Identifier on creation and they are accessed by Identifier The quote chars around 1 and 2 are used to type these characters as identifier strings rather than numbers 2 4 The Rewrite Rules We will now add the real rewrite rules to the rule set file removeEpsilons grg The idea is to forward the e transitions one after another i e if we have a pattern like a State EpsilonTransition gt b State e Transition gt c State we forward to a e gt c Af ter all such transitions are forwarded we can remove the e transitions alltogether The com plete rule set is shown in figur
137. pBackend dll e and implementing the generic interface from de unika ipd grGen libGr using the entities mentioned in both points above If you work on the API level it is helpful to keep the generated source code which nor mally is thrown away after it was compiled into the assemblies lesp FooModel dll and lgsp FooActions dll Use the keep option when you call grgen exe to do so 10 1 Interface to the host graph The generated file FooModel cs opens the namespace de unika ipd grGen Model_Foo con taining all the generated entities It contains for every node or edge class Bar an interface IBar which offers C properties giving access to the attributes and is inheriting in the same way as specified in the model file This builds the exact interface of the model it is implemented by a sealed class Bar with generated code and with code from the lgsp backend Furtheron the namespace contains a model class FooGraphModel implementing the inter face de unika ipd grGen libGr IGraphModel which supports iteration over the entities defined in the model using further generic i e inexact interfaces from libGr Finally the namespace contains a class FooGraph which defines an lgsp graph of a model equivalent to FooGraphModel it contains convenience functions to easily create nodes and edges of exact type in the graph 127 128 Application Programming Interface If you want to use the type safe interface use the interface IBar and
138. pecified in the model The strict mode additionally requires that all the edges available in the host graph must have been specified in the model This requirement is too harsh for models where only certain parts are considered critical enough to be checked or might be a too big step in tightening the level of structural checking in an already existing large model So some form of selective strict checking is supported The strict only specified mode requires strict matching i e that all edges are covered only of the edges for which connection assertions have been specified in the model validate Py Validates if the current working graph satisfies the graph rewrite sequence given Before the graph rewrite sequence is executed the instance graph gets cloned the sequence operates on the clone allowing you to change the graph as you want to without influence on the host graph Validation fails iff the xgrs fails This gives a rather costly but extremely flexible and powerful mechanism to specify graph constraints The GrShell is exited with an error code if exitonfailure is specified and the validation fails 8 2 GRSHELL Commands 101 We reuse a simplified version of the road map model from Chapter 3 1 model Map node class city node class metropolis edge class street edge class highway connect metropolis gt metropolis 0 ND oa FP W N The node constraint on highway requires all the metr
139. pecify graph pat terns which in contrast to negative application conditions must be present in the host graph to cause the matching of the enclosing pattern to succeed Together with NACs they share the property of opening a scope with elements being independent from the surrounding scope i e a host graph element can easily get matched to a pattern element and a PAC element with a different name unless the pattern element is referenced in the PAC They are used to improve the logical structure of rules by separating a pure condition from the main pattern of the rule amenable to rewriting They are really needed if subpatterns want to match elements which were already matched during the subpattern derivation A further fabricated example rather giving the intention using independent patterns to check some conditions with only the main pattern available to rewriting 1 rule moveMethod 2 3 c Class gt m Method 4 csub extending gt c 5 csub Class e Edge gt msub Method 6 7 independent 8 a complicated pattern to find out that m and msub have same signatures 9 10 independent 11 a complicated pattern to find out that msub is only using variables available in c 2 13 independent 14 a complicated pattern to find out that m is not used 5 16 17 modify move method upwards 18 delete m 19 delete e 20 C gt msub a 5 3 Pattern Cardinality NestedPatt
140. pers to denote positions in the strings and giving the result of length counting StringExpr PrimaryExpr E MethodSelector E The operator concatenates two strings There are several operations on strings available in method call notation MethodSelector these are length returns length of string as int indexOf strToSearchFor returns first position strToSearchFor string appears at as int or 1 if not found lastInderOf strToSearchFor returns last position strToSearchFor string appears at as int or 1 if not found substring startInder length returns substring of given length int from startIndex int on replace startIndez length replaceStr returns string with substring from startIndex int on of given length int replaced by replaceStr int EXAMPLE 44 For n str foo bar foo the operations yield n str length 11 str indexOf foo 0 str lastIndexOf foo 8 str substring 4 3 bar str replace 4 3 foo foo foo foo D BBB 6 7 Set Expression Set expressions consist of the known mathematical set operations and size counting 6 8 Map Expression 19 SetExpr E LJ MethodSelector Set union contained in resulting set as soon as contained in one of the sets Set intersection contained in resulting set only if contained in both of the sets Set difference contained in resulting set iff contained in left but not right set Table
141. ph management e graph validation e graph input and output e graph manipulation e graph and model queries e graph visualisation e action execution e debugging e backend selection and usage The debugging and graph visualisation commands are implemented in cooperation with the graph viewer YCOMP Alternatively to GRSHELL you can access the match and rewrite facility through LIBGR This way you can build your own algorithmic rule applications in a NET language of your choice 4 Introduction 1 4 System Overview Figure 1 1 gives an overview of the GRGEN NET system components call Graph Rewrite Script grs GRSHELL C LIBGR C Backend Run Time Graph Model a ee CF read generate A ae Compile Time l Graph Model gm GRGEN NET Graph M Generator rap a Java CH agement C Rewrite Rewrite Rules C Figure 1 1 GRGEN NET system components Kro07 Rules grg A graph rewrite system is defined by a rule set file grg which may include further rule set files and zero or more graph model description files gm It is generated from these specifications by GrGen exe and can be used by applications such as GRSHELL Figure 1 2 shows the generation process referencing read generate model3 gm backend dll rules Model dll gt rules1 Actions dll model2 gm rulesl grg modell gm Figure 1 2 Generating a g
142. placing identifier nodes by their declaration nodes in an largely preorder walk Afterwards the AST is checked by check and checkLocal in an largely postorder walk for type and other semantic constraints Finally an intermediate representation is built from the abstract syntax tree by the getIR and constructIR methods The IR classes given in the ir folder can be seen as more lightweight AST classes their name is often the same as for their corresponding AST classes but without the Node suffix which is appended to all AST classes The IR classes are the input to the two backends of the frontend as given in the folders be C and be Csharp The directory be C contains the code generator for the C based backend integrated into the IPD C compiler The compiler transforms a C program into a graph and SSA based compiler intermediate representation named FIRM using libFirm see libfirm org TLB99 Lin02 and further on to x86 machine code The directory be Csharp contains the code generator for the C based backend of GRGEN NET It generates the model source code FooModel cs with the node and edge classes for a rule file named Foo grg and the intermediate rules source code FooActions_intermediate with a description of the patterns to match a description of the embedded graph rewrite sequences and the rewriting code It does not generate the complete rules source code with the matcher code or the code for the embedded rewrite sequences this is done
143. raph element of a host graph So graph elements of different names are pair wise distinct except for homomorphically matched graph elements see Section 4 3 For instance v NodeType1 e EdgeType gt w NodeType2 selects some node of type NodeType1 that is connected to a node of type NodeType2 by an edge 4 1 Building Blocks 29 of type EdgeType and binds the names v w and e If v and w are not explicitly marked as homomorphic the graph elements they bind to are distinct Binding of names allows for splitting a single graphlet into multiple graphlets as well as defining cyclic structures The following graphlet n1 n2 and n3 are defined somewhere else ial 92 e ne is equivalent to icky gt Sie DTM in plies gt jae and ni gt n3 is equivalent to n3 lt n1 of course The visibility of names is determined by scopes Scopes can be nested Names of surrounding scopes are visible in inner scopes Usually a scope is defined by and In Example 4 lines 13 to 17 the negative condition uses n3 from the surrounding scope and defines n4 and el We may safely reuse the variable name el in the replace part GraphletNode Specifies a node of type NodeType maybe constrained in type with a TypeConstraint see Section 4 6 TypeConstraint maybe retyped with a Reytping see Section 4 8 Retyping The is an anonymous node of the base type Node remember that every node type has Node as super type
144. raph rewrite system In general you have to distinguish carefully between a graph model meta level a host graph a pattern graph and a rewrite rule In GRGEN NE T pattern graphs are implicitly defined by rules i e each rule defines its pattern On the technical side specification docu ments for a graph rewrite system can be available as source documents for graph models and rule sets plain text gm and grg files or as their translated NET modules either C source files or their compiled assemblies dll Generating a GRGEN NET graph rewrite system may be considered a preliminary task The actual process of rewriting as well as dealing with host graphs is performed by GR GEN NET s backend GRGEN NET provides a backend API in two versions the named and typed entities which get generated plus the name string and object based interface offered by the NET library LIBGR For most issues in particular for experimental purposes you might rather want to work with the GRSHELL because of its rapid prototyping support How ever GRSHELL does not provide the full power of the LIBGR see also note 13 on page 36 In this context system is not a CHO like grammar rewrite system but rather a set of interacting software components 1 5 What is Graph Rewriting 5 1 5 What is Graph Rewriting The notion of graph rewriting as understood by GRGEN NET is a method for declaratively specifying changes to a graph This is compara
145. re MyEnum is the name of the other enum type enum Color RED GREEN BLUE enum Resident VILLAGE 500 TOWN 5000 CITY 50000 enum AsInC A 2 B C 1 D e int Resident VILLAGE C Consider e g the declaration of the enum item e By implicit casts of Resident VILLAGE and C to int we get the int value 501 which is assigned to E Moreover the semantics is as in C SAI 90 So the following holds RED 0 GREEN 1 BLUE 2 A 2 B 3 C 1 Dr OD and E 501 The C like semantics of enum item declarations implies that multiple items of one enum type can be associated with the same same int value Moreover it implies that an enum item must not be used before its definition This also holds for items of other enum types meaning that the items of another enum type can only be used in the definition of an enum item when the other enum type is defined before the enum type currently defined 3 2 Type Declarations 23 ClassDeclaration y const arbitrary directed Defines a new node type or edge type The keyword abstract indicates that you cannot instantiate graph elements of this type Instead you have to derive non abstract types to create graph elements The abstract property will not be inherited by subclasses of course ao PR O N RA We adjust our map model and make city abstract abstract node class City 1 Size int abstract node class AbandonedCity extends C
146. rently read by you There s one convenience not offered you might expect a visual rule language and an editor This brings a clear benefit graph transformation specifications to be processed by GRGEN NET can be easily generated but especially is a good deal cheaper to implement Given the limited resources of an university project this is an important point as can be seen with the AGG ERT99 tool offering a nice graphical editor but delivering performance only up to simple toy examples causing the wrong impression that graph rewriting is notoriously inefficient in the heads of users Well Founded Semantics to ease formal but especially human reasoning The semantics of GRGEN NET are specified in Gei08 based upon graph homomorphisms denotational evaluation func tions and category theory The GRGEN NE T rewrite step is based by default on the single pushout approach SPO for explanation see EHK 99 with the double pushout approach DPO for explanation see CMR 99 available on request too The seman tics of the recursive rules introduced in version 2 0 are given in Jak08 utilizing pair star graph grammars on the meta level to assemble the rules of the object level The for mal semantics are not as complete as for the graph programming language GP P1u09 1 8 Development goals 11 though mainly due to the large amount of features the convenience at using the language had priority over the convenience at reason
147. s empty gt wv WriteValue modify delete h wv RWHead gt tp rule writeZeroRule wv WriteZero rw RWHead gt tp TapePosition value gt tp replace WV rw gt tp zero gt tp rule writeOneRule wv WriteOne rw RWHead gt tp TapePosition value gt tp replace wv IW gt tp one gt tp rule writeEmptyRule wv WriteEmpty rw RWHead gt tp TapePosition value gt tp replace wv rw gt tp empty gt tp rule moveLeftRule wv WriteValue moveLeft gt s State 9 2 Busy Beaver 123 53 wv h RWHead gt tp TapePosition lt r right ltp TapePosition 54 modify 55 delete h 56 s RWHead gt 1tp 57 58 59 60 rule moveRightRule 61 wv WriteValue moveRight gt s State 62 wv h RWHead gt tp TapePosition r right gt rtp TapePosition 63 modify 64 delete h 65 s RWHead gt rtp 66 67 68 69 rule dontMoveRule 70 wv WriteValue dontMove gt s State 71 wv h RWHead gt tp TapePosition 72 modify 73 delete h 74 s RWHead gt tp 75 76 7 78 rule ensureMoveLeftValidRule 79 wv WriteValue moveLeft gt State 80 wv RWHead gt tp TapePosition 81 negative 82 tp lt right 83 84 modify 85 tp lt right ltp TapePosition empty gt ltp 86 87 so rule ensureMoveRightValidRule 90 wv WriteValue moveRight gt State 91 wv RWHead gt tp TapePosition 9
148. s First 10 3 Import Export and miscellaneous stuff GrGen natively supports the following formats GRS GRSI Reduced GrShell script files graph only model from gm a very limited version of the normal grs GXL Graph eXchange Language gx1 files see http www gupro de GXL ECORE XMI Ecore ecore model files and XMI xmi graph file Import only export must be programmed with emit statements In an intermediate step a gm file is generated for the model While both GRS and GXL importers expect one file the GXL importer allows to specify a model override see GrShell import Note 27 the EMF ECORE importer expects first one or more ecore files and following optionally a xmi files and or a grg file cf Note 28 To use additional custom graph models you should supply an own grg file which may be based on the automatically generated grg file if none was supplied see the Program Comprehension example in examples ProgramComprehension GraBaTs09 To import a graph model and or a graph instance you can use Porter Import from the libGr API the GrShell command import is mapped to it The file format is determined by the file extensions To export a graph instance you can use Porter Export from the libGr API the GrShell command export is mapped to it For an example of how to use the importer exporter on API level see examples api JavaProgramGraphsExample JavaProgramGraphs Example cs The GRS I importer returns a
149. s a graph rewrite sequence which is a composition of graph rewrite rules Yielded graph elements may be included into the RHS pattern but as of now they are only accessible from the return statement See Chapter 7 for a description of graph rewrite sequences Text Output The emit statement prints a string to the currently associated output stream default is stdout See Chapter 6 for a description of string expressions For emitting in between the emits from subpatterns there is an additional emithere statement available This is an example for returning elements yielded from an exec statement The results of the rule bar are written to the variables a and b The yield statement is similar to a return but does not jump out The anonymous output variables written in the yield statement are assigned in the given order to the pattern variables specified after the assign to operator gt modify 1 exec a b bar amp amp yield a b gt u A v B return u v 48 Rule Set Language The following example works on a hypothetical network flow We don t define all the rules nor the graph meta model It s just about the look and feel of the exec and emit statements 1 rule AddRedundancy 3 s SourceNode 4 t DestinationNode 5 modify 6 emit Source node is s name Destination node is t name 7 exec x SourceNode DuplicateNode s ConnectNeighbors s x 8 exec Duplic
150. s and priorities of rewrite sequence operators 7 2 Loops rewrite term Rewrite Term RewriteFactor A rewrite term consists of a rewrite factor which can be executed multiple times The star executes a sequence repeatedly as long as its execution does not fail Such a sequence always returns true A sequence s is equivalent to s amp amp s The brackets m execute a sequence repeatedly as long as its execution does not fail but m times at most the min max brackets n m additionally fail if the minimum amount n of iterations was not reached 7 3 Rule application rewrite factor RewriteFactor A TOLO Rewrite factors are the building blocks of graph rewrite sequences They split into four major areas rule application variable assignment extended control and visited flags man agement plus the special area of storages to be described separately Further on there s 86 Rule application control language XGRS the emit sequence it writes a double quoted string or the value of a variable to the emit target stdout as default or a file specified with the shell command redirect emit RuleExecution O Variable gt o ATA ATT ES amp Ch AS G Variable O O The RuleExecution clause applies a single rule or test In case of a rule the first found pattern match will be rewritten Variables and named graph elements from the enclosing rule can be passed The returned graph element
151. s can be assigned to variables again The operator switches the rule to a test i e the rule application does not perform the rewrite part of the rule but only tests if a match exists The operator is a multi purpose flag In the GRSHELL see Chapter 8 it dumps the matched graph elements to stdout in debug mode see Section 8 3 it acts as a break point which is its main use in fact you are also able to use this flag for your own purposes when using GRGEN NET via its API interface see Section 1 7 3 The sqare braces introduce a special kind of multiple rule application Every pattern match produced by the will be rewritten Attention This all bracketing is not equal to Rulex Instead this operator collects all the matches first before starting to rewrite In particular the semantics is unsafe i e one needs to avoid deleting or retyping a graph element that is bound by another match If Rule returns values the values of one of the executed rules will be returned The random match selector v searches for all matches and then randomly selects v of them to be rewritten but at most as much as are available with r1 being equivalent to anonymousTempVar 1 amp anonymousTempVar ri An appended to the denotes a choice point allowing the user to choose the match to be applied from the available ones in the debugger see Section 8 3 Rule EXAMPLE 48 The sequence u v r x y applies the rule r with input from
152. s well as deletion of just created elements pointless too How might Example 10 look in modify mode We have to denominate the anonymous edge between n1 and n2 in order to delete it The node varnode should be kept and does not need to appear in the modify part So we have 1 rule SomeRuleExtModify varnode Node Node EdgeTypeB ni e0 Edge gt n2 modify n5 NodeTypeC lt n1 gt n3 e1 EdgeTypeB gt n5 delete e0 eval oO A Nn wow Pp W N a O 40 Rule Set Language 4 4 3 Syntax Replace Y IAS ReplaceStatement ReturnStatement q ExecStatement B Selects whether the replace mode or the modify mode is used Several replace statements describe the transformation from the pattern subgraph to the destination subgraph ReplaceStatement SubpatternRewriteApplication The semantics of the various replace statements are given below Graphlet Analogous to a pattern graphlet a specification of a connected subgraph Its graph elements are either kept because they are elements of the pattern or added otherwise Names defined in the pattern part must not be redefined in the replace graphlet See Section 4 1 for a detailed explanation of graphlets Deletion The delete operator is only available in the modify mode It deletes the specified pattern graph elements Multiple occurrences of delete statements are allowed Dele tion statements are executed after all other replace statements Multip
153. sed approach Though we started four years ago to facilitate some compiler construction problems in the meantime GRGEN NET has grown into a general purpose tool for graph rewriting We want to thank all co workers and students that helped during the design and imple mentation of GRGEN NE T as well as the writing of this manual Especially we want to thank Dr Sebastian Hack G Veit Batz Michael Beck Tom Gelhausen Moritz Kroll Dr Andreas Ludwig and Dr Markus Noga Finally all this would not happened without the productive atmosphere and the generous support that Prof Goos provides at his chair We wish all readers of the manual and especially all users of GRGEN NET a pleasant graph rewrite experience We hope you enjoy using GRGEN NET as much as we enjoy de veloping 16 Thank you for using GRGEN NET Karlsruhe in July 2007 Rubino Geif on behalf of the GRGEN NET Team vl FOREWORD Since the last version of this manual which was written for GRGEN NET v1 4 a lot has hap pened as can be seen quite easily in the fact that this manual describes GRGEN NET v2 6 The porting of C to C Kro07 allowed for a faster pace of development which yielded al ternatives and subpatterns allowing for structural recursion Jak08 HJG08 undirected edge support plus fine grain pattern conditions Buc08 a data model that is more user friendly at the API support for visited flags and an prototypical implementation of an embedding of
154. signment sets the boolean status of the visited flag of the given number for the given graph element If no flag number is given the default number for the first visited flag of 0 is used Make sure to allocate7 6 10 3 visited flags before you try to use them and deallocate them after wards as they are a sparse resource stored in some excess bits of the graph elements or in some dictionary if the needed number of flags exceeds the number of available bits per graph element modify eval y i eval y j x Il JNode y 1JNode delete x eval x i y j Z yi o nn a Pp O N HH Rh e psp e DE A S me oa Ha This toy example yields y i 42 y j 1 42 Rule Set Language The set map state change methods add and rem allow to add graph elements to storages or remove graph elements from storages i e sets or maps holding nodes and edges used for rewrite in the calling sequence cf 7 7 This way you can write transformations consisting of several passes with one pass operating on nodes edges determined in a previous pass without the need to mark the element in the graph by helper edges or visited flags rule foo ref storage set lt Node gt n Node modify storage add n J n O A S O 4 5 Rule and Pattern Modifiers By default GRGEN NET performs rewriting according to semantics as explained in Sec tion 4 4 1 This behaviour can be changed with pattern mod
155. sition extends Transition Figure 2 1 Meta Model for State Machines state nodes and Transition for transition edges that will connect the state nodes State has an integer attribute id and Transition has a string attribute Trigger which indicates the character sequence for switching from the source state node to the destination state node For the rest of the types we use inheritance keyword extends which works more or less like inheritance in object oriented languages Accordingly the abstract modifier for SpecialState means that you cannot create a node of that precise type but you might create nodes of non abstract subtypes As you can see GRGEN NET supports multiple inheritance and with StartFinalState we have constructed a diamond type hierarchy 2 3 Creating Graphs Let s test our graph meta model by creating a state machine graph We will use the GRSHELL see Chapter 8 and for visualization YComP To get everything working we need a rule set file too For the moment we just create an almost empty file removeEpsilons grg in the home grgen directory containing only the line 1 using StateMachine Now we could start by launching the GRSHELL and typing the commands interactively This is however in most of the cases not the preferred way We rather create a GRSHELL script say removeEpsilons grs in the home grgen directory Figure 2 2 shows this script Run the script by executing grshell removeEpsilons grs The
156. so far In order to improve the performance we generate better search plans This is a crucial step for execution time With the initial search plans the beaver runs for 1 minute and 30 seconds With improved search plans after the first 32 steps he takes about 8 5 seconds On a Pentium 4 3 2Ghz with 2GiB RAM 126 Examples 56 custom graph analyze_graph 67 custom actions gen_searchplan readUneRule readEmptyRule writeQneRule writeEmptyRule ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule Let the beaver run xgrs readOneRule readEmptyRule amp writeQneRule writeEmptyRule amp ensureMoveLeftValidRule ensureMoveRightValidRule moveLeftRule moveRightRule CHAPTER 10 APPLICATION PROGRAMMING INTERFACE This chapter describes the Application Programming Interface of GRGEN NET i e of the system runtime the LibGr and of the assemblies generated from the model and rule specifications We ll have a look at e the interface to the graph and model e the interface to the rules and matches e the porter module for importing and exporting of graphs and miscellaneous stuff From the input file Foo grg grgen exe generates the output files FooModel cs for the model and FooActions cs for the actions e defining the exact interface e implementing the exact interface with generated code and code from the lgsp backend i e entities from de unika ipd grGen lgsp available from lgs
157. ssions 13 IntExpr PrimaryExpr BoolExpr nn IntExpr EA IntExpr a IntExpr gt BinIntOperator gt IntExpr The operator is the bitwise complement That means every bit of an integer value will be flipped The operator is a simple if then else If the BoolExpr is evaluated to true the op erator returns the first IntExpr otherwise it returns the second ntExpr The BinIntOperator is one of the operators in Table 6 8 Bitwise XOR AND and OR Bitwise shift left bitwise shift right and bitwise shift right preserving the sign Addition and subtraction Multiplication integer division and modulo Table 6 8 Binary integer operators in ascending order of precedence FloatExpr PrimaryExpr BoolExpr yl FloatExpr A FloatExpr j FloatExpr BinFloatOperator H FloatExpr The operator is a simple if then else If the BoolExpr is evaluated to true the operator returns the first FloatExpr otherwise it returns the second FloatExpr The BinFloatOperator is one of the operators in Table 6 9 The operator on float values works analogous to the integer modulo operator For instance 4 5 2 3 2 2 74 Types and Expressions E Addition and subtraction Multiplication division and modulo Table 6 9 Binary float operators in ascending order of precedence 6 6 String Expressions String expressions combine string values by string operations with integer numbers used as hel
158. stic See Chapter 7 for further information on graph rewrite sequences PatternStatement NestedPattern SubpatternEntity Declaration The semantics of the various pattern statements are given below Graphlet Graphlets specify connected subgraphs See Section 4 1 for a detailed explanation of eraphlets 4 3 Pattern Part 31 Isomorphic Homomorphic Matching The hom operator specifies the nodes or edges that may be matched homomorphically In contrast to the default isomorphic matching the specified graph elements may be mapped to the same graph element in the host graph Note that the graph elements must have a common subtype Several homomorphically matched graph elements will be mapped to a graph element of a common subtype In Example 4 nodes n1 and n2 may be the same node This is possible because they are of the same type NodeTypeA Inside a NAC the hom operator may only operate on graph elements that are either defined or used in the NAC Nested negative independent blocks inherit the hom declarations of their nesting pattern In contrast to previous versions hom delarations are non transitive i e hom a b and hom b c don t cause hom a c unless specified Attribute Conditions The Java like attribute conditions keyword if in the pattern part allow for further restriction of the applicability of a rule Pattern Modifiers Additionally to modifiers that apply to a pattern as a whole you may also specify pattern modifiers for
159. t int x mybool MyEnumi MyEnumiType int and MyEnum2 MyEnum2Type MyEnum1 where myenum1 and myenum2 are different enum types Unlike an eval part which must not contain assignments to node or edge attributes the declaration of an enum type can contain assignments of int values to enum items see Sec tion 3 2 The reason is that the range of an enum type is just defined in that context 6 2 Expressions GRGEN NE T supports numerous operations on the entities of the types introduced above which are organized into left associative expressions In the following they will be explained with their semantics and relative priorities one type after another in the order of the rail diagram below Expression Mansa FloatExpr StringExpr MapExpr TypeExpr Primary Expr 6 3 Boolean Expressions 71 6 3 Boolean Expressions The boolean expressions combine boolean values with logical operations They bind weaker than the relational expressions which bind weaker than the other expressions BoolExpr Primary Expr EN RelationalExpr The unary operator negates a Boolean The binary BinBoolOperator is one of the operators in Table 6 4 The ternary operator is a simple if then else If the first BoolExpr is evaluated Logical XOR True iff either the first or the second Boolean expression is true 2 Logical AND and OR Lazy evaluation Logical AND and OR Strict eva
160. t enclosed by single quotes Number Is an int or float constant in decimal notation see also Section 6 1 Parameters u SpacedParameters A In order to describe the commands more precisely the following semantic specializations of Text are defined Filename A fully qualified file name without spaces e g Users Bob amazing file txt or a single quoted or double quoted fully qualified file name that may contain spaces Users Bob amazing file txt 95 96 GrShell Language Variable Identifier of a graph global variable that contains a graph element or a value Node Type Edge Type Identifier of a node type resp edge type defined in the model of the current graph AttributeName Identifier of an attribute Graph Identifies a graph by its name Action Identifies a rule by its name Color One of the following color identifiers Black Blue Green Cyan Red Purple Brown Grey LightGrey LightBlue LightGreen LightCyan LightRed LightPurple Yel low White DarkBlue DarkRed DarkGreen DarkYellow DarkMagenta DarkCyan Gold Lilac Turquoise Aquamarine Khaki Pink Orange Orchid These are the same color identifiers as in VCG yCompP files for a VCG definition see San95 GraphElement The elements of a graph nodes and edges can be accessed both by their graph global variable identifier and by their persistent name specified through a constructor see Sec tion 8 2 5 The special
161. teNegTerm A graph rewrite sequence consists of several rewrite terms linked by operators Table 7 1 gives the priorities and semantics of the operators priorities in ascending order The modifier changes the semantics of the following operator to randomly execute the left or the right operand first i e flags the operator to act commutative usually operands are executed evaluated from left to right if not altered by bracketing In contrast the sequences s t u in s lt op gt t lt op gt u are executed evaluated in arbitrary order The modifier appended to the overrides the random selection by a user selection cf see Section 8 3 choice points 7 2 Loops rewrite term 85 Operator Meaning si lt s2 Then Left evaluates s1 then s2 and returns projects out the result of s1 s1 gt s2 Then Right evaluates s1 then s2 and returns projects out the result of s2 s1 s2 Lazy Or the result is the logical disjunction evaluates s1 only if s1 is false s2 gets evaluated si amp amp s2 Lazy And the result is the logical conjunction evaluates s1 only if s1 is true s2 gets evaluated si s2 Strict Or evaluates s1 then s2 the result is the logical disjunction si s2 Strict Xor evaluates s1 then s2 the result is the logical antivalence si amp s2 Strict And evaluates s1 then s2 the result is the logical conjunction Is Negation evaluates s and returns its logical negation Table 7 1 Semantic
162. the CreateNodeBar methods of FooGraph or the CreateNode method of Bar If you want to use the generic interface your entry point is the IGraphModel with INodeModel GetType Bar returning a NodeType used in IGraph AddNode NodeType returning an INode 10 2 Interface to rules The generated file FooActions cs opens the namespace de unika ipd grGen Action_Foo containing all the generated entities It contains for every rule or test bar e a class Rule_bar inheriting from de unika ipd grGen 1gsp LGSPRulePattern which contains the exact match interface IMatch_bar which defines how a match of the rule looks like extending the generic rule unspecific IMatch interface Furtheron there are but meant only for internal use a match class Match_bar implementing the exact and inexact interface a description of the pattern to match and the modify methods doing the rewriting e an exact action interface IAction_bar which contains the methods Match to match the pattern in the host graph with in parameters corresponding to the in parameters of the rule name and type returning matches of the exact type Rule_bar IMatch_bar Modify to modify a given match according to the rewrite specification with out parameters corresponding to the out parameters of the rule Apply to match and modify the found match with in parameters corresponding to the in parameters of the rule and with ref parameters corresponding to the out para
163. tions dll as sembly use Don t re generate C source files Instead use the files in eristing dir to build the assemblies debug Compile the assemblies with debug information b Use the backend library backend dll default is LGSPBackend 0 Store generated assemblies in output dir Requires NET 2 0 or above or Mono 1 2 3 or above Java Runtime Environment 1 5 or above Regarding the column information in the error reports of the compiler please note that tabs count as one character The grgen compiler consists of a Java frontend used by the C backend grgen exe The java frontend can be executed itself to get a visualization of the model and the rewrite rules in the form of a dump of the compiler IR as a vcg file java jar grgen jar 1 yourfile grg 1 7 2 GrShell exe The GrShell exe is a shell application on top of the LIBGR GRSHELL is capable of creating manipulating and dumping graphs as well as performing graph rewriting with graphical debug support For further information about the GRSHELL language see Chapter 8 Usage mono grShell exe N C lt commands gt lt grshell script gt Opens the interactive shell The GRSHELL will include and execute the commands in the optional list of grshell scripts usually grs files in the given order The grs suffixes may be omitted GRSHELL returns 0 on successful execution or in non interactive mode 1 if the specified shell script could not be
164. tions in GRSHELL 9 2 1 Graph Model The tape will be a chain of TapePosition nodes connected by right edges A cell value is modeled by a reflexive value edge attached to a TapePosition node The leftmost and the rightmost cells TapePosition do not have an incoming and outgoing edge respectively Therefore we have the node constraint 0 1 node class TapePosition edge class right connect TapePosition 0 1 gt TapePosition 0 1 edge class value connect TapePosition 1 gt TapePosition 1 edge class zero extends value edge class one extends value edge class empty extends value Furthermore we need states and transitions The machine s current configuration is modeled with a RWHead edge pointing to a TapePosition node State nodes are connected with WriteValue nodes via value edges a moveLeft moveRight dontMove edge leads from a WriteValue node to the next state cf the picture on page 125 node class State edge class RWHead node class WriteValue node class WriteZero extends WriteValue node class WriteOne extends WriteValue node class WriteEmpty extends WriteValue edge class moveLeft edge class moveRight edge class dontMove 9 2 2 Rule Set Now the rule set We begin the rule set file Turing grg with 1 using TuringModel We need rewrite rules for the following steps of the Turing machine 1 Read the value of the current tape cell and select an outgoing edge of the current
165. ule set language nested and subpatterns 49 scope 29 50 52 script see graph rewrite script search plan 46 116 125 search plans 10 sequence constant 88 sequence local variables 83 set 69 90 shell see GrShell short info tag 111 Sierpinski triangle 119 signature 33 simulation 114 single pushout approach 10 30 38 some of set braces 88 spanning tree 59 SPO see single pushout approach 42 spot 5 28 storage 90 string 69 structural recursion 57 subpattern 55 subpattern declaration 56 subpattern entity declaration 56 subrule 62 syntax diagram see rail diagram test 33 35 transaction 88 transformation specification 38 Turing complete 121 type cast see retyping 69 type constraint 29 30 44 143 type expression 28 71 77 type hierarchy 19 21 44 45 type compatible 107 UEdge 21 UML class diagram 72 undefined variables 112 undirected 30 user input assignment 87 validate 100 variable see expression variable 78 see graph global variables see sequence local variables 96 104 112 variable predicate 87 Varr s benchmark 10 VCG 9 96 108 visited flag 41 78 89 visualization see group node 108 working graph 99 yComp 9 108 114 yComp jar 114
166. ults for your needs organic and hierarchic or compiler graph an extension of hierarchic with automatic edge cutting marking cut edges by fat dots showing the edge only on mouse over and allowing to jump to the other end on a mouse click should be tried first 112 GrShell Language The following example shows several of the layout options employed to considerably in crease the readability of a program graph as given in examples JavaProgramGraphs GraBaTs08 J _ 1 wu zu _ ee Jere Kor ill i A Iffr S E Overview of the initial program graph and some details of the Node class 8 2 8 Action Commands XGRS An action denotes a graph rewrite rule select actions Filename Selects a rule set Filename can either be a NET assembly e g rules dll or a source file rules cs Only one rule set can be loaded simultaneously show actions Lists all the rules of the loaded rule set their parameters and their return values Rules can return a set of graph elements i SpacedParameters y Executes an action specific to the current backend If SpacedParameters is omitted a list of available commands will be displayed for the LGSPBackend see Section 8 4 2 actions custom GraphRewriteSequence SimpleRewriteSequence This executes the graph rewrite sequence SimpleRewriteSequence See Chapter 7 for graph rewrite sequences Additi
167. using the subpattern via the declaration of the entity tp of type TwoParameters binding the context element to its local node m The resulting test after subpattern derivation is equivalent to the test methodWithTwoParameters test methodWithTwoParameters m Method lt n Name m lt Variable m lt Variable 5 5 1 Recursive Patterns Subpatterns can be combined with alternative patterns or the cardinality patterns into re cursive subpatterns i e subpatterns which may contain themselves Subpatterns containing themselves alone directly or indirectly would never yield a match 58 Nested and Subpatterns 1 test iteratedPath 2 3 root Assign 4 negative gt root 5 IteratedPath root match iterated path assignment list 6 7 s pattern IteratedPath prev Node 9 optional nothing or a linked assignment and again a list prev gt a Assign assignment node IteratedPath a next one plz e e HM e SY ds Searches an iterated path from the root node on here an assinment list The iterated path with the optional is equivalent to the code below note the negative which ensures you get a longest match without it the empty case may be chosen lazily just in the beginning pattern IteratedPath prev Node j ajal 3 alternative 4 Empty 1 5 negative 6 prev gt a Assign 7 8 9 Further ja prev gt
168. v from storage set u Execute t for every v in storage set u One t failing pins the execution result to failure Clears the storage set u Membership query succeeds if v is element of u otherwise fails Create storage map and assign to u Operations are the same or similar to the operations of storage sets Assign target value of win u to v Fails if w in u Let r s t be sequences u v w variable identifiers lt op gt 7 amp amp amp Table 7 2 GRS expressions at a glance 94 Rule application control language XGRS CHAPTER 8 GRSHELL LANGUAGE GRSHELL is a shell application built on top of LIBGR It belongs to GRGEN NET s standard equipment GRSHELL is capable of creating manipulating and dumping graphs as well as performing and debugging graph rewriting The GRSHELL provides a line oriented scripting language GRSHELL scripts are structured by simple statements separated by line breaks 8 1 Building Blocks GRSHELL is case sensitive A line may be empty may contain a shell command or may con tain a comment A comment starts with a and is terminated by end of line or end of file The following items are required for representing text numbers and rule parameters Text May be one of the following e A non empty character sequence consisting of letters digits and underscores The first character must not be a digit e Arbitrary text enclosed by double quotes e Arbitrary tex
169. withvariables is specified the graph global variables are exported too The export is only complete with the model of the graph given in the gm file Exporting fails if the graph model contains attributes of object type The save command is for saving about a GRSHELL session including graph global variables and visualization commands the goal of the export command is basic graph rewrite system interoperability The persistent names are saved in contrast to the following format GXL Filename Exports an instance graph and a graph model in GXL format WKR02 HSESW05 which is somewhat of a standard format for graphs of graph rewrite systems but suffers from the well known XML problems it is barely human readable and bloated Exporting fails if the graph model contains attributes of set lt S gt map lt S T gt or object type If the gz suffix is given the graph is saved zipped Imports the specified graph instance in GRS grs grsi format the reduced GRSHELL script a saved graph can only be imported by include but an exported graph can be imported by include too The referenced graph model must be available as gm file If the gz suffix is given the graph is expected to be zipped Filename 8 2 GRSHELL Commands 103 Imports the specified graph instance and model in GXL format If a model override of the form Filename gm is specified the given model will be used instead of the model in the GXL file The gxl
170. y are a means of composing complex graph operations out of single graph rewrite rules they determine the control flow by the evaluation order of the operands Graph rewrite sequences have a boolean return value for a single rule true means the rule was successfully applied to the host graph A false return value means that the pattern was not found in the host graph In order to store and reuse return values of rewrite sequences and most importantly for passing return values of rules to other rules variables can be defined A variable is an arbitrary identifier which can hold a graph element or a value of one of the attribute or value types GRGEN NET knows There are two kinds of variables available in GRGEN NET i graph global variables and ii sequence local variables A variable is alive from its first declaration on graph global variables are implicitely declared upon first assignment to their name sequence local variables are explicitely declared with a typed variable declaration of the form name type Graph global variables are untyped their values are typed though so type errors cause an exception at runtime They belong to and are stored in the graph if you save the graph in GRSHELL or export to grs using the withvariables option then the variables are saved too and restored next time you load the saved graph Further on they are nulled if the graph element assigned to them gets deleted even if this happens due to
171. y available for reading the by ref parameters additionally for set map addition and removal cf 4 10 Return Types ae 7 EdgeType J VarType The return types specify edge and node types of graph elements that are returned by the replace modify part If return types are specified the return statement is mandatory Oth erwise no return statement must occur See also Section 4 4 return 4 2 Rules and Tests 35 The test t that checks whether node n1 is adjacent to n2 connected by an undirected edge or incoming directed edge or outgoing directed edge test t n1 Node lt null gt n2 Node lt null gt Tien is equivalent to the tests t1 t4 which are chosen dependent on what parameters are defined test t1 n1 Node n2 Node 4 al te a I test t2 n1 Node ni n2 Node test t3 n2 Node 4 n1 Node n2 test t4 n1 Node n2 Node OONN TOOU Rh pap N e O So if both parameters are not defined t4 is chosen which succeeds as soon as there are two distinct nodes in the graph connected by some edge We extend SomeRule Example 4 with a user defined node to match and we want it to return the rewritten graph elements n5 and e1 rule SomeRuleExt varnode Node Node EdgeTypeB 1 n1 NodeTypeA replace varnode return n5 el eval oO A ND wo FF Ww N Hr ea We do not define varnode within the pattern part because this is already covered
172. y edge classes user defined user defined directed edge classes undirected edge classes y IN user defined directed edge class n Figure 3 1 Type Hierarchy of GRGEN NET Edges 3 2 Type Declarations GraphModel ClassDeclaration u Enum Declaration The graph model consists of zero or multiple type declarations Whereas ClassDeclaration defines a node type or an edge type EnumDeclaration defines an enum type to be used as a 22 Graph Model Language type for a attributes of nodes or edges Like all identifier definitions types do not need to be declared before they are used EnumDeclaration Ident Decl Ident Decl Loy Defines an enum type An enum type is a collection of so called enum items that are associated with integral numbers each Accordingly a GRGEN NET enum is internally represented as int see Section 6 1 An enum type and an int are different things but in expressions enum values are implicitly casted to int values see Section 6 1 Normally assignments of int values to something that has an enum type are forbidden see Section 6 1 Only inside a declaration of an enum type an int value may be assigned to the enum item that is currently declared This also includes the usage of items taken from other enum types because they are implicitly casted to int However items from other enum types must be written fully qualified in this case which e g looks like MyEnum a whe
173. y expression which is a variable reading it root lt v Variable N N N N N N N N N HM CI A OT gt CI A ES w N amp 68 Nested and Subpatterns CHAPTER 6 TYPES AND EXPRESSIONS 6 1 Built In Types Besides user defined node types edge types and enumeration types as introduced in Chap ter 3 GRGEN NET supports the built in primitive types in Table 6 1 and the built in generic types in Table 6 2 The exact type format is backend specific The LGSPBackend maps the GRGEN NET primitive types to the corresponding C primitive types and the generic types to generic C Dictionaries of their corresponding primitive types i e hashmaps with de unika ipd grGen libGr SetValueType as target type for sets only used with the value null boolean Covers the values true and false int A signed integer with at least 32 bits float double A floating point number with single precision or double precision respec tively string A character sequence of arbitrary length object Contains a NET object Table 6 1 GRGEN NE T built in primitive types set lt T gt A mathematical set of type T where T may be an enumeration type or one of the primitive types from above map lt S T gt A mathematical map from type S to type T where S and T may be enumer ation types or one of the primitive types from above Table 6 2 GRGEN NET built in generic types Table 6 3 lists GRGEN NET s implicit type casts and
174. y r are retained The outcome of these steps is the resulting graph H In symbolic language H 5 MH 1 6 An Example We ll have a look at a small example Graph elements nodes and edges are labeled with and identifier If a type is necessary then it is stated after a colon We start using a special case to construct our host graph an empty pattern always produces exactly one match Because of the uniqueness of the total and totally undefined morphism 6 Introduction independent of the host graph So we construct an apple by applying po 0 Zu to the empty host graph As the result we get an apple as new host graph H Now we want to rewrite our apple with stem to an apple with a leaflet So we apply E E to H and get the new host graph H1 something like this What happened GRGEN NE T has arbitrarily chosen one match out of the set of possible matches because x matches edge ez as well as e A correct solution could make use of edge type information We have to change rule po to generate the edge e with a special type stem And this time we will even keep the stem So let o Co 1 7 The Tools I If we apply pa to the modified H this leads to 1 7 The Tools All the programs and libraries of GRGEN NET are licensed under LGPL Notice that the YCOMP graph viewer is not a part of GRGEN NET YCOMP ships with its own license Although YCOMP is not free software it s free for use in academic and

The GrGen User Manual

Contents

Download Pdf Manuals

Related Search

Related Contents