DiaGenA Generator for Diagram Editors Providing Direct Manipulation and Execution of Diagra

DiaGen:A Generator for Diagram EditorsProviding Direct Manipulation and Execution of DiagramsM.Minas G.ViehstaedtLehrstuhl f¨u r ProgrammiersprachenUniversit¨a t Erlangen-N¨u rnbergMartensstr.3,91058Erlangen,Germanyemail:minas,viehstae@informatik.uni-erlangen.deAbstractDiagrams(e.g.,flowcharts,trees for hierarchical struc-tures,or graphs forfinite state machines)are often needed as part of visual language systems and advanced user in-terfaces,and are frequently application specific.The im-plementation of editors for diagrams should be supported by a tool and based on a formal model.This paper gives an overview of DiaGen,our generator for diagram editors. An editor for a certain kind of diagrams is generated from a specification,which includes a hypergraph grammar to describe the structure of diagrams.The user of a diagram editor does not have to be concerned with the grammar,but can manipulate diagrams very conveniently by direct ma-nipulation.As an additional and important feature in the context of visual languages editors generated by DiaGen can not only be used for editing,but also for executing,i.e., animating diagrams.1IntroductionAn easily comprehensible representation of complex structures is desirable in every application and especially in visual language ing some kind of diagram as a graphical representation of the complex structures is often the best choice.Wellknown examples are Nassi-Shneiderman diagrams(NSDs),flowcharts,orfinite state machines.However,using those diagrams also means constructing and modifying them with a diagram editor. Diagram editors have to be distinguished from interface builders for Graphical User Interfaces(GUIs)and general purpose drawing editors:Interface builders are restricted to quite a small class of “diagrams”:they mainly focus on widgets like buttons, menus,etc.,which does not make interfaces very graph-ical,also stated in a recent CACM issue on GUIs[1]: What the market considers a GUI is little more than a glorified menu system,having no graphics.This leavesthe graphical representation of the application domain as an exercise for the developerDiagrams usually have a semantical meaning for the ap-plication.Thus,changes to a diagram have to be trans-formations from one consistent state into another.The set of valid diagrams,e.g.,the set of NSDs,is termed a diagram class.A general purpose drawing editor can-not give the user support on creating and editing only correct diagrams.As a consequence,the diagram class should be described by a formal model.A syntax-directed diagram editor tai-lored to some diagram class ensures that a diagram con-structed by the user always has a valid structure,and can support complex editing operations and layout.Just some tools,e.g.,Garnet[2],support simple kinds of diagrams.The structure of valid diagrams,however,has to be maintained by the programmer using Garnet and is more or less hidden in the code.There are only very few sys-tems for generating a diagram editor that are based on a for-mal model.A concept is presented in[3],but not a genera-tor.In the P AGG system[4]layout of diagrams is trouble-some and editing inconvenient.The Constraint system[5] uses a grammar model based on context-free grammars and constraints for automatic layout of diagrams.Context-free grammars,however,do not permit direct representation of multidimensional relationships,as needed for the layout of diagrams.Furthermore,the editing capabilities are very re-stricted.We propose using hyperedges and hypergraphs [6],which have,e.g.,been used by Harel for Statecharts[7], as a much more intuitive and advantageous model for rep-resentation of diagrams.This paper gives an overview on DiaGen,our imple-mented generator for diagram editors from a specification, which has partially been introduced before in[8,9]and which is based on a hypergraph grammar model for specify-ing a diagram class.The main features stressed here are itsFigure1:Snapshot of a NSD editor session:a group of two subsequent statements(consisting of a simple state-ment and an if)is selected in the lower NSD,as indicated by the handles.natural way to edit diagrams by direct manipulation,i.e.,by simply grabbing and dragging diagram parts from one place on the screen to another,and executing diagrams.This fea-ture exceeds the tasks of regular editors which are solely built for editing,but not for animating what has been edited.Section2gives a brief overview of the system.The grammar model is the topic of Section3.Editing dia-grams by direct manipulation will be addressed in Sec-tion4.Section5will then address transformations,the in-ternal concept of diagram modification,which can also be used for diagram execution,i.e.,animation in Section6. Section7eventually will present an extension of DiaGen which adds drawing tool behavior and a parser which al-lows for shorter specifications and makes dealing with in-consistent diagrams possible.2The Generator DiaGenDiaGen generates a diagram editor like the NSD editor depicted in Fig.1from a specification,which consists of the parts shown in Fig.3.A major part is the grammar for the diagram class.Some particular diagram shown on the screen is internally represented in the diagram editor by a hypergraph.This hypergraph is referred to as derivation graph in Fig.3and is the main data yout con-ditions are attached to grammar productions in the specifi-cation.Terminal symbols in a derivation graph are mapped on the screen.Their image is composed of primitive ele-ments(lines,text,etc.)and is also part of the specification.4Direct ManipulationThe main feature concerning user interaction is that a di-agram can be modified very conveniently in a direct manip-ulation style by just moving diagram elements around on the screen.This is not the case for other systems like PAGG or Constraints[4,5],in which editing operations have to be chosen from a menu.In a diagram editor generated with DiaGen the interaction module(see Fig.3)is responsible for the reaction on a user’s actions with mouse and key-board.They can,e.g.,cause layout changes,selection of di-agram elements,or transformations of the diagram’s yout changes have been discussed in[8].Selection of diagram elements is possible in different ways and part of the specification.In this sample editor subsequent selected statements(which may be complex)are automatically com-bined into a single entity called a group,see Fig.1and[9]. Transformations will be presented in section5A diagram editor for NSDs,which was generated with DiaGen,serves for demonstrating direct manipulation.As an example,we now want to remove the group in Fig.1 from its position and insert it into the upper NSD as the first statements of the while.Fig.7shows the result.The only way to achieve this in other systems like[4,5]is solely based on selection and pressing buttons or choosing menu items in the following style:Press the Cut-buttonSelect the line immediately below the while’s condition to indicate the destinationPress the Insert-buttonThe concept is the same as in the Synthesizer Generator [13]for syntax-directed text editing.It is sufficient there, but for diagrams a more natural way of editing is desirable.With DiaGen diagram editors offering true direct manip-ulation can be specified.E.g.,the modification from Fig.1 to Fig.7can be made by simplypressing the mouse button while the mouse pointer is lo-cated over the selected group,dragging this group to its destination,and releasing the mouse button over the line below the while’s condition.In the same way any part of a diagram can be removed and inserted at any other spot.A diagram part can also be made a new NSD of its own or an entire NSD can be in-serted into another diagram in a similar fashion.A number of other editing operations by direct manipu-lation have been specified for the NSD editor:The then-and else-branch of an if can be switched by pressing the mouse button over the if’s triangle with‘y’inside,dragging it to the right,and releasing it over the corresponding‘n’(or the other wayaround).Figure7:Situation after moving the group selected in Fig.1 to the beginning of the while.A while can be changed into an until by moving thewhile’s condition down to the end of the while and re-leasing the mouse button there.Similarly,an until can be modified into a while.5TransformationsDiagram modifications initiated by direct manipulation are described by transformations:a transformation is a transition from a set of diagrams to another set of diagrams. The structure of one or more diagrams can be changed,but the user of a diagram editor only sees valid diagrams,i.e., diagrams belonging to the specified diagram class.In con-trast to[5],transformations in DiaGen can be complex and consist of several primitive steps.This enables more pow-erful transformations and reuse of primitives.E.g.,many transformations in the NSD editor are based on primitives for deleting or inserting a sequence of(compound)state-ments.An example of a simple transformation rule in the NSD editor is given in Fig.8.Transformation rules describe the modification of the derivation which stands behind each diagram being displayed on the screen.In these rules a derivation(like that in Fig.5)is written as a tree.A trans-formation consists of a sequence of rules.The user of a dia-gram editor indicates by mouse and keyboard actions which transformation shall be applied and the location where this shall be ing direct manipulation the user would in-dicate the text t and the line l where t has to be inserted innew diagram structure.Fig.9a shows the situation after constructing an automa-ton and Fig.9b the situation after pressing button Start. The user was asked to provide an input string for the au-tomaton,and the current state was set to the initial state.If there is a suitable transition for the currentlyfirst charac-ter in the input string,each press on button Step causes a transition and removes thefirst character from the input, see Fig.9c.After repeatedly pressing on button Step the automaton reaches itsfinal state as in Fig.9d.Ok visualizes the automaton to have accepted the initial string.7Extending DiaGen by a parserAn extension and modification to DiaGen beyond the descriptions so far is to add behavior of standard drawing tools,i.e.,to allow arbitrarily moving and combining dia-gram components.Of course,as a consequence,not only valid diagrams,but also inconsistent and even invalid dia-grams violating syntactic rules can be created.Therefore,a parser that concurrently checks the current drawing against the diagram class’s syntax whenever the diagram is modi-fied has also to be part of DiaGen’s extension.The advantages of allowing standard drawing tool be-havior and using a parser are:As we have experienced from sample editors we have generated,the most effective way to reduce specifica-tion size is to reduce the size of transformation specifi-cations.With this extension specification of tree trans-formations can be omitted.The user can“draw”his di-agram,and it is the parser’s task to identify valid di-agram parts.Or the specification can be restricted to some transformations.The user can carry out modifi-cations other than these predefined ones by using the drawing tool properties.Without this extension,DiaGen denies transformations that have not been specified.Due to the size of transfor-mation specifications forgetting to specify transforma-tions is not uncommon.The extension to DiaGen soft-ens the effect of forgetting to specify transformations.In certain situations temporarily inconsistent editing states make sense[14].The user can then modify dia-grams step by step where single steps may be inconsis-tent.When using a parser,the editor can distinguish be-tween inconsistent and consistent editing states.With-out a parser,syntax-directed editing cannot permit in-consistent editing states.As a parser,we are using an incremental adaptation of Cocke-Younger-Casami’s parser[15]to context-free hy-pergraph grammars[16]with the following properties: For each editing state the parser identifies the maxi-mal syntax trees.These trees represent correct diagram parts.Figure10:An inconsistent editing state of the NSD editor. The diagram parts identified as valid have been highlighted by a thick border line.A possible completion suggested by the parser is the text block with the dotted border line.The parser also identifies those parts of the editing state that are inconsistent or invalid.In case of inconsistency the parser is able to suggest components that would complete the editing state to valid diagrams.The parser does not only keep track of syntax trees for valid sub-diagrams of the current editing state.It rather maintains information of every possible(incomplete) derivation of parts of the current editing state.This information is eagerly used when constructing syntax trees whenever hypergraphs are modified.The idea of DiaGen using a drawing tool behavior and a parser is as follows:during generation of the editor the set of terminal hyperedges mapped to the screen build a repository of graphical objects which are internally repre-sented by their terminal hyperedge together with an appro-priate number of nodes visited by the ing the drawing tool component the user can create and combine as many of these objects as she wants.When objects are combined on the screen,i.e.,when they are positioned at adjacent positions,the internal hypergraph is constructed: nodes of the different graphical objects being mapped to the same screen position are simply identified.Nodes being unnecessarily identified do not cause problems since our in-cremental parser can easily deal with that.Whenever the internal hypergraphs are modified by an editing operation, the incremental parser updates and/or reconstructs the syn-tax trees.The information created by the parser can be used to highlight correct diagrams of the current editing state and to suggest components to be added in order to remove in-consistencies(see Fig.10).The extensions to DiaGen described above are partially implemented but not yet incorporated into DiaGen.We are currently implementing the drawing tool behavior.How-ever,the incremental parser is already existing and has been tested outside of DiaGen.The numbers shown in Tab.1have been measured using our C++implementa-tion on Sparc Stations2for parsing hypergraphs represent-ing NSDs.We have split valid hypergraphs of reasonable#edges time21.07secs393 4.80secs。