Method in a structure editor - Patent Review 5493678

We claim:

1. A data processing system implemented method for maintaining syntactically correct connections between a first data element and a second data element wherein said data processing system includes storage means, processing means, and operator interaction means, said method comprising the steps of:

creating a list of permitted data element types;

storing in said storage means a first level syntax rule for each data element type;

storing in said storage means second level syntax rules that refer directly or indirectly through one or more second level syntax rules to said first level syntax rules to specify valid relationships;

wherein said syntax rules define lists of relationships that may be established between said data element types, said relationships defining the number of connections that may be established, and the data element types that may be connected;

locating one of said first level syntax rules corresponding to said first data element type;

testing said second data element to determine whether said second data element is of a data element type that may be connected to said first data element; if not, no relationship may be established; and

establishing a connection between said first data element and said second data element, if permitted.

2. In a data processing system structure editor in which data elements or nodes of different types are added, copied, deleted, moved, or inserted into a hierarchical structure or tree comprised of data elements in a storage means of said data processing system, a method for connecting nodes comprising the steps of:

selecting nodes to be connected to said tree;

storing in said storage means a first set of rules specifying permitted hierarchical relationships and order relationships between nodes in said tree;

selecting a relationship to be established between said selected nodes and nodes in said tree;

testing said selected relationship using said first set of rules applied to said selected nodes and generating potential connections between said selected nodes and said nodes in said tree;

storing in said storage means a second set of rules specifying types of nodes that may be connected in said tree;

testing each of said generated connections using said second set of rules to determine whether said second set of rules is satisfied by said generated connection; and

if said second set of rules is satisfied, making said generated connection.

3. A method of manipulating data organized as a hierarchy or tree with a single root data element and one or more lower layers of subsidiary (child) data elements such that zero, one or more subsidiary data elements are related to only one parent data element in the next higher level in the hierarchy wherein said data is stored in a storage means of a data processing system, and said manipulating is performed by said data processing system in response to operator directions, said method of manipulating data comprising the steps of:

(a) selecting from said hierarchically organized data elements a plurality of data elements for manipulation, said data elements being selected without regard to their relationship to other selected data elements; and

(b) collecting said selected data elements into a collected list of subtrees that maintain the existing hierarchical relationships, said subtrees being formed by connecting said selected data elements by a simple link, said collected list containing one entry for each of said subtrees, said collecting step comprising the steps of:

(1) identifying highest-order data elements selected;

(2) creating copies of said highest-order data elements;

(3) identifying all selected data elements hierarchically related to each of said highest-order data elements;

(4) copying said related data elements; and

(5) connecting said copies of said related data elements to said copy of said each of said highest-order data elements to form a simply connected subtree wherein said hierarchical relationships are preserved.

4. The method of claim 3, comprising the further steps of:

(c) specifying a target data element and a relationship between said selected data elements and said target data element; and

(d) inserting said collected list into said hierarchy at said target data element so that said relationship is established.

5. The method of claim 3, wherein each data element is classified into a type category and wherein the method further comprises the step of specifying permitted relationships between data elements, said permitted relationships defining when and how data elements of different types may be connected.

6. The method of claim 5, wherein said collecting step (b) comprises the further step of determining whether each of said selected data elements identified as hierarchically related to a highest-order data element can be connected to said highest-order data element according to said permitted relationships, said steps (c)(4) and (c)(5) being performed only if permitted according to said relationships.

7. A method of manipulating data organized as a hierarchy or tree with a single root data element and one or more lower layers of subsidiary (child) data elements such that zero, one or more subsidiary data elements are related to only one parent data element in the next higher level in the hierarchy wherein said data is stored in a storage means of a data processing system, and said manipulating is performed by said data processing system in response to operator directions, said method of manipulating data comprising the steps of:

(a) selecting from said hierarchically organized data elements a plurality of data elements for removal, said data elements being selected without regard to their relationship to other selected data elements;

(b) grouping said selected data elements into simply connected groups such that each element of a group is connected to at most one data element in the hierarchical layer immediately above its layer while preserving existing hierarchical relationships; and

(c) for each simply connected group:

(1) identifying the highest-order data element in said group;

(2) identifying the parent data element of said highest-order data element;

(3) identifying all data elements connected to one of said selected data elements in said group but not selected;

(4) removing all data elements contained in said group from said tree; and

(5) connecting to said parent of said highest-order data elements all data elements connected to said group but not removed.

8. The method of claim 7, wherein each data element is classified into a type category and wherein the method further comprises the step of specifying permitted relationships between data elements, said permitted relationships defining when and how data elements of different types may be connected.

9. The method of 8, wherein said step (c)(5) is performed only if such connection establishes a permitted relationship.

10. The method of claim 7 in which said step (c) comprises the further step of:

(6) connecting the removed data elements in said simply connected group to previously removed data elements so that the hierarchical relationships are preserved.

11. The method of claim 10, wherein each data element is classified into a type category and wherein the method further comprises the step of specifying permitted relationships between data elements, said permitted relationships defining when and how data elements of different types may be connected.

12. The method of claim 11, wherein said steps (c)(5) and (c)(6) are performed only if such connections establish permitted relationships.

13. A method of manipulating data organized as a hierarchy or tree with a single root data element and one or more lower layers of subsidiary (child) data elements such that zero, one or more subsidiary data elements are related to only one parent data element in the next higher level in the hierarchy wherein said data is stored in a storage means of a data processing system, and said manipulating is performed by said data processing system in response to operator directions, each of said data elements being classified into a type category, said method of manipulating data comprising the steps of:

(a) specifying permitted relationships between data elements, said permitted relationships defining when and how data elements of different types may be connected, said specifying step comprising the steps of defining the type of data elements allowed, defining the nature of connections allowed and, for each data element type, specifying the types of data elements which can be connected to said data element type and the nature of connection allowed;

(b) selecting an operation to be performed;

(c) selecting from said hierarchically organized data elements or creating a plurality of data elements for manipulation, said data elements being selected without regard to their relationship to other selected data elements;

(d) performing said selected operation on said selected or created data elements only if such operation establishes permitted relations between said data elements.

14. A method of inserting a list of subtrees comprising a plurality of simply connected data elements constituting nodes into a tree in relation to a selected target node having a parent node, said list of subtrees being maintained in a storage means of a data processing system, said method being performed by said data processing system in response to selections and directions of an operator through operator interaction means, said method comprising the steps of:

(a) specifying a relationship between said list of subtrees and said target node;

(b) if said relationship is specified as "left" or "right", connecting each subtree in the list of subtrees to said parent such that said subtree is connected to said parent before said target node, if left, or after said target node, if right;

(c) if said relationship is specified as "around":

(1) disconnecting said target node from said parent node;

(2) connecting each subtree in said list of subtrees to said parent node as subsidiary data elements thereof; and

(3) connecting said disconnected target node to said list of subtrees;

(d) if said relationship is specified as "within":

(1) disconnecting the subsidiary data elements of said target node;

(2) connecting each subtree in said list of subtrees to said target node as subsidiary data elements thereof; and

(3) connecting said disconnected subsidiary data elements to each subtree in said list of subtrees.

15. The method of claim 14, wherein each of said data elements in said subtrees is classified into a type category and wherein the method further comprises the step of specifying permitted connections between data elements, said permitted connections defining the types of data elements that may be connected and the type of relationships permitted between types of data elements.

16. The method of claim 15, wherein the connecting steps of steps (b)-(d) are performed only if a permitted relationship is established.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to information handling systems, particularly computer systems for manipulating related data and more particularly to editors for editing related data where the data and relationships can be expressed as a hierarchy, or tree, with data elements forming the nodes and relationships defining the placement of a node within the tree structure. The data and relationships expressed by a tree structure are referred to as "tree structured data".

2. Background of the Invention

Editors are typically comprised of: a user interface to accept commands from the user and display the results of the action; data manipulation processes to perform the necessary editing functions; data storage means to maintain the data and relationships; and (optionally) syntax rules expressing the valid relationships between data nodes for use by the data manipulation processes in validating requested actions.

The manipulation of data represented in a tree structure includes the following functions:

inserting a new data node or set of nodes into the tree structure;

deleting a data node or set of nodes from the tree structure;

copying a data node or set of nodes to a new position in the structure; or

moving a data node or set of nodes to a new position in the structure.

The manipulation functions must preserve any existing relationships between nodes including relationships among a set of nodes to be inserted, deleted, copied or moved.

There have been many systems developed for editing tree structured data. Theme systems, called generally structure editors, have been primarily concerned with editing formally specified programming languages. These editors seek to enforce syntax rules expressing valid relationships between data nodes. Many modern programming languages, and formal languages in general, possess an underlying structure or hierarchy of statements which may be expressed as a tree, known as a parse tree. The relationships forming the tree provide a natural way for manipulating the data.

Programming languages have syntax rules governing the relationships, or trees that are valid for that language. These rules must be followed exactly or the program is meaningless. As a consequence, editors have been developed to assist in the creation and maintenance of programs by enforcing the rules of the language in which the program is written and allowing selection of data to be manipulated based on an understanding of the underlying structure of the program. These editors are known variously as "language based editors" or "syntax-directed editors".

Implementations of editors such as these that are known to the inventors fall into two broad classes. The first provides user interface very similar to that of a standard line or character oriented text editor. Editing works with a textual description of the program, from which the structure is regenerated after each editing operation. If the structure cannot be regenerated, or the regenerated structure is in violation of some syntax rule, the editor either rejects the editing operation or makes its best guess as to how to form the result so that a valid structure may be regenerated.

The advantages of such a scheme are that it is quite general, having no restrictions on what set of characters may be used in editing operations, and that the editing model can be made very familiar to programmers who are currently working with simple text editors. If the editor attempts to create a valid structure from the invalid one the programmer has given it, much of the programmers work can be done automatically as long as the editor generates the structure the programmer had intended. These advantages are also the cause of the scheme's disadvantages, however. The total generality makes it quite simple for a programmer to make the same mistakes that he or she would have made without the syntax-directed editor, and now these mistakes are caught at the moment of entry, interrupting the work, forcing the errors to be corrected. In addition, if the editor attempts to correct the error itself it is likely to do something that, while strictly correct, is not intended by the programmer. If the correction is not in the same direction the programmer had been thinking the programmer must correct not only his or her own error, but also the misinformation the editor generated. This scheme is also fairly inefficient, as little advantage may be taken of the existing structure in order to regenerate the new structure, causing a duplication of effort of the part of the editor. In the process of editing, programmers quite often create incorrect programs as short term intermediate steps in the editing process. This sort of editor either does not allow these steps or fixes them itself, with the possibility (as discussed above) of doing so incorrectly. An example of such an editor is found in the COPE Programming Environment, developed by Richard Conway et al. at Cornell University.

The other class of syntax-directed editors manipulates the structure of the tree directly. The user interface for this class of editors is typically graphical with the user able to work with graphic images representing groups of program statements. The graphic images are displayed as a tree connected according to the specified hierarchical relationships. Only operations that result in a valid tree are allowed to complete. The operations are specified in terms of complete subtrees (a complete subtree consists of a node and all of its children, and their children, and so forth, until no further children are available) and these subtrees may be moved or copied to become subtrees of other nodes, or may be deleted entirely. New nodes or predefined subtrees may be inserted as children of existing nodes as well.

This class of editors is highly efficient, as only the structure of the tree is being manipulated. It also prevents many common errors from ever being made, as only complete structures may be moved around. Unfortunately, it is very restrictive for daily use as an editor. While subtrees are indeed basic to proper manipulation of programs, single complete subtrees are rarely useful. Quite often a programmer wishes to remove a level from the node hierarchy, or insert a level into it. This operation is basic to editing a program beyond the earliest first pass at writing the program which often ends as early as five minutes past the decision to write the program at all. This disadvantage is the main one inhibiting this method from being useful as a basic editing model.

In addition, programmers almost invariably work with several ranges of subtrees (corresponding to ranges of lines) and the simple subtree operations model often doesn't support such operations. An enhancement to some editors represents a subtree following an earlier subtree as the last child of that subtree. This allows a "sequential" list of statements from an arbitrary start position to the end of the sequence at that level of the hierarchy to be represented as a proper subtree. A further enhancement, allowing the final child of a node to be considered detached from the subtree being manipulated, allows sequential statements which can be considered to be partial subtrees, to be moved in one operation with no further restrictions. However, these enhancements are difficult to fit into an editing model based on complete subtrees. Even with these enhancements, the model is still restrictive, for example, allowing nodes only to be added as subtrees of existing nodes, not as parents of existing nodes.

Examples of editors using this model are the Cornell Program Synthesizer, developed by Tim Teitlebaum et al. at Cornell University; and the Xinotech Program Composer, developed by Xinotech Research, Inc.

SUMMARY OF THE INVENTION

The present invention relates to providing a structure editor that is not limited to operations on complete subtrees. The preferred embodiment provides data manipulation methods for operating on one or more partial subtrees. The methods implement data insertion, deletion, copying and moving, improved generalized scoping methods for selecting the data for operation, and generalized targeting methods for specifying the resulting data location and relationships. In addition, the preferred embodiment relates to the performance of node insertion, deletion, copying and moving through combinations of sub-operations including collecting the set of subtrees which comprises the scope; deleting nodes comprising the scope; and grafting the nodes comprising the scope at the point indicated by the generalized target. An extension to the preferred embodiment relates to providing a syntax directed editor that enforces specified syntax rules. The methods of the preferred embodiment are operable with a variety of user interfaces, data storage schemes, and syntax rule specifications.

Accordingly, it is an object of the present invention to provide flexible insert move, copy, and delete operations in a structure editor while maintaining the valid structure of a tree. Further objects are to provide the ability to:

Move, copy, and delete arbitrary selections of nodes within a tree rather than only complete subtrees.

Maintain the relative structure (i.e. nesting and left to right relationships) of both selected and unselected nodes.

Move, copy, and insert selected nodes as the parent of an existing node (i.e. insert the new nodes around the existing node).

Move, copy, and insert selected nodes as all the children of an existing node (i.e. insert the new nodes between the parent node and its children).

Move, copy, and insert selected nodes as children of an existing node.

Maintain the rules concerning the valid structure of the tree as these and other operations are performed.

It is a still further object of the present invention to provide high speed graft and replace operations on memory efficient parse trees, while maintaining the valid structure of the trees.

It is still a further object of the present invention to provide the ability to:

Store trees using n-ary nodes (i.e. nodes that have an arbitrary number of nodes connected to them), thus saving significant storage space.

Efficiently check that the children of a node within a parse tree are of valid type and in valid order.

Graft a list of subtrees after a specific child of a node, and ensure that the resulting node with its children is syntactically correct.

Replace a list of subtrees below a specific node with a new list of subtrees, and ensure that the resulting node with its children is syntactically correct.

According to one aspect of the present invention an editing method is provided for collecting one or more groups of one or more related n-ary data elements, or nodes, for a subsequent operation. All nodes in the tree to be collected are selected, and each highest order node so selected is identified. For the identified highest order node, all selected descendants are identified. The descendants are then connected to the highest order node to form a simply connected subtree wherein the relative hierarchy is preserved as between the descendants and the highest order node.

According to a further aspect of the invention, an editing method is provided for deleting one or more groups of one or more simply connected n-ary data elements, or nodes, from a tree. One or more groups of one or more simply connected nodes of said tree are selected for deletion. The parent node of the top-most node of each selected group of nodes is identified. The children of each selected group of nodes are also identified. The selected groups of nodes are then deleted. Finally, the children of each deleted group of nodes are connected to the parent of the top-most node of each deleted group.

According to a still further aspect of the present invention a method is provided for inserting subtrees of n-ary data elements, or nodes, into a tree around a selected node. A list of subtrees is provided, and a target node is selected. The target node is disconnected from its parent node. The list of subtrees is connected to the parent node, as the children thereof. Finally the disconnected target node is connected to the list of subtrees by testing, in a predetermined sequence, to determine the first of the bottom-most nodes of the parent node to which the target node and its children may connect. The target node is connected when the determination is that such connection can be made.

According to a still further aspect of the present invention a method is provided for inserting one or more subtrees of n-ary data elements, or nodes, into a tree connected to a selected node. A list of subtrees is provided, and a target node is selected. The children of the target node are disconnected. A list of subtrees is connected to the target node, as the children thereof. Finally, the disconnected children are connected to the list of subtrees by testing, in a predetermined sequence, to determine the first of the bottom-most nodes of the list of subtrees to which the disconnected children may connect. The children are connected when the determination is that such connection can be made.

According to a still further aspect of the present invention, a method is provided in a structure editor that generates and manipulates nodes that interconnect to form a tree structure in accordance with a set of rules, for determining whether a first node can connect to a second node. According to this aspect of the invention, for at least some of a set of nodes that form a tree, one or more subsets of rules from the aforementioned set of rules are defined, regarding the type of nodes, and the arrangement thereof that are permitted to be connected to the nodes as children thereof, wherein the types of nodes are potentially different among themselves such that the rules are of a first and a second level. The first level rule is for determining whether a given node may connect upon application of the rule, without need for application of further rules. The second level rule refers directly or indirectly through other second level rules to at least one first level rule for determining whether a given node may connect. Upon performance of an operation requiring connecting two or more nodes, those rules are applied based on the node into which the other node or nodes are to connect.

Finally, according to a still further aspect of the present invention, a method for connecting nodes to one another is provided in a structure editor in which data elements or nodes are copied, deleted, moved or inserted. Nodes to be connected to a tree are selected. A first set of rules regarding hierarchical relationships and order relationship between the selected nodes and the existing tree are provided. The first set of rules are used with respect to the selected nodes to identify one or more connections to nodes in the tree. A second set of rules is provided regarding permitted arrangement of nodes in the tree. The identified connections are tested, using the second set of rules, to determine whether the second set of rules is satisfied in the connection. If the second set of rules is satisfied the connection is made.

Thus, it will be appreciated that the present invention provides an approach to providing for substantially improved flexibility in editing operations in structure editors. Arbitrary selections of nodes in a tree may be identified for operations such as collection, deletion, or insertion. Further, in editors in which a syntax is enforced, the present invention provides a powerful approach to permitting these highly flexible operations while maintaining the underlying syntax.

The foregoing and other objects, features and advantages of the invention will be apparent from the more particular description of the preferred embodiments of the invention, as illustrated in the accompanying drawing.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an example of an editing system incorporating the present invention.

FIG. 2a is an example of a tree of the type that is created and manipulated in a structured editor, presented for the purpose of illustrating scoping.

FIG. 2b shows the three subtrees resulting from the application of a collecting operation on the tree shown in FIG. 2a.

FIG. 3 shows the tree that results after a delete operation on the nodes scoped in FIG. 1.

FIG. 4 shows the tree that results from pasting the list of subtrees shown in FIG. 2 around the E2 node of the tree shown in FIG. 3.

FIG. 5 shows a parse tree representing an exemplary valid sequence of statement using simple Backus Naur Form structure.

FIG. 6 is an improved representation of the tree shown in FIG. 5, using extended BNF.

FIG. 7 is a tree structure illustrating the concept of "sockets".

FIG. 8 is a tree like that shown in FIG. 7, after an exemplary graft operation.

FIG. 9 is a tree like that shown in FIG. 7, after an exemplary replace operation.

FIG. 10 shows a table useful in illustrating the principles of the extension to preferred embodiment of the present invention.

FIG. 11 is a flowchart depicting the basic process flow of the preferred embodiment of the present invention.

FIG. 12 is a flowchart depicting the process flow of the graft operation according to an extension to the preferred embodiment.

FIG. 13 is a flowchart depicting the process flow of the replace operation according to an extension to the preferred embodiment.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Table of Contents of the Detailed Description of the Preferred Embodiment

1. Overview of the Preferred Embodiment

2. Specification Language

3. Utility Functions Used in the Preferred Embodiment

I. Tree Manipulation

II. Set Manipulation

III. List Manipulation

4. Base Function Definitions

5. Main Functions

6. Extensions to Preferred Embodiment

7. Utility Functions Used by the Extensions

8. Data Needed for the Extensions

9. Base Function Definitions for the Extensions

10. Main Functions of the Extensions

1. Overview of the Preferred Embodiment

The present invention relates to a flexible scope editing method in a structure editor. The components of a typical editing system configuration, including a structure editor, is shown in FIG. 1. The editing system has a user interface 21, a data manipulation process 26, data structure storage device 28 and, optionally, structure syntax rules 30. The user interface 21 typically includes a video display screen 20 or similar device for displaying the structure or statement to be edited, a keyboard 22 for entering information and a pointing device 24 such as a mouse for selecting data items from a screen display. Data manipulation process 26 performs the editing functions, including structure editing to create or modify data to be stored on storage device 28. In one embodiment, syntax rules governing the data structure are stored in data storage 30. Data storage 28 and 30 can be fixed or flexible magnetic disks, magnetic tape or like devices. It will be recognized that this is but one environment in which the method of the present invention could be implemented and it is not intended to limit the application of the method.

The preferred embodiment provides an inventive flexible scope editing method as part of Data Manipulation Process 26. The flexible scope editing method provides a means to insert, delete, copy, or move data nodes in hierarchically or tree structured data. The present invention relates to the provision of flexible scoping (i.e. the sel