Efficient computation of line information in a token-oriented representation of program code

• US 20040225997A1
• Filed: 05/06/2003
• Published: 11/11/2004
• Est. Priority Date: 05/06/2003
• Status: Abandoned Application

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Urquhart, Kenneth B., Van De Vanter, Michael L.
• Application Number:
  US10/430,538
• Publication Number:
  US 20040225997A1
• Time in Patent Office: Days
• US Class Current: 717/109
• CPC Class Codes: G06F 8/33 Intelligent editors

Abstract

An editor, software engineering tool or collection of such tools may be configured to encode (or employ an encoding of) an insertion point representation that identifies a particular token of a token-oriented representation and offset thereinto, together with at least some line-oriented coordinates. Efficient implementations of insert and remove operations that employ such a representation are described herein. Computational costs of such operations typically scale at worst with the size of fragments inserted into and/or removed from such a token-oriented representation, rather than with buffer size. Accordingly, such implementations are particularly well-suited to providing efficient support for programming tool environments in which a token stream is updated incrementally in correspondence with user edits.

Claims

1. A software engineering tool encoded in one or more computer readable media as instructions executable to represent program code as a doubly-linked list of lexical tokens including at least some line demarcations corresponding to line boundaries in the represented program code, the instructions further executable to maintain, consistent with operations thereon, both a token-coordinates representation and a line-coordinates representation of an insertion point.

2. The software engineering tool of claim 1,

wherein the line-coordinates representation encodes both a line and a line offset therein corresponding to the insertion point.

3. The software engineering tool of claim 1,

wherein the line demarcations are embodied as end-of-line (EOL) tokens.

4. The software engineering tool of claim 1,

wherein forward and backward pointers at least partially define the doubly-linked list;

and

wherein additional line-related pointers are associated with the line demarcations, the line-related pointers identifying respective previous and next line demarcations of the doubly-linked list.

5. The software engineering tool of claim 1,

wherein for a given line of the program code, a character count therefor is encoded in, or in association with, a corresponding one of the line demarcations.

6. The software engineering tool of claim 1,

wherein the operations include insertion point repositioning operations.

7. The software engineering tool of claim 1,

wherein the operations include edit operations.

8. The software engineering tool of claim 7, wherein the edit operations include one or more of:

insertion operations; and

removal operations.

9. The software engineering tool of claim 1,

wherein the token-coordinates representation identifies both a particular one of the lexical tokens and a substring offset into a substring associated with the particular lexical token.

10. The software engineering tool of claim 1,

wherein, coincident with movement of the insertion point to a new position in the program code, the maintaining includes traversing from a particular position in the doubly-linked list toward the new position, and updating both the token-coordinates representation and line-coordinates representation of the insertion point in correspondence therewith.

11. The software engineering tool of claim 10,

wherein the particular position corresponds to the insertion point.

12. The software engineering tool of claim 10,

wherein the particular position corresponds to one of:

a first line of represented program code,

the insertion point, and

a last line of the represented program code,

selected based on comparison with the new position to generally minimize computational overhead associated with the scanning and updating.

13. The software engineering tool of claim 10,

wherein computational overhead associated with the scanning and updating is generally insensitive to length of the represented program code, and instead exhibits no greater than O(L)+O(T) scaling behavior, where L corresponds to scale of line displacement from the particular position to the new position and T corresponds to scale of character displacement in a line that includes the new position.

14. The software engineering tool of claim 1,

wherein the instructions are further executable to maintain, consistent with each operation that modifies the program code, a total line count.

15. The software engineering tool of claim 1, configured as one or more of:

an editor;

a source level debugger;

a class viewer;

a profiler;

a style checker,

a compiler or interpreter; and

an integrated development environment.

16. The software engineering tool of claim 1,

wherein the one or more computer readable media are selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium and a network, wireline, wireless or other communications medium.

17. A method of identifying an insertion point in an edit buffer represented as a sequence of lexical tokens, the method comprising:

representing the edit buffer as a doubly-linked list of nodes, each node corresponding to a respective one of the lexical tokens; and

representing the insertion point in the edit buffer, the insertion point representation identifying;

(i) a particular one of the lexical tokens corresponding to the insertion point; and

(ii) line coordinates for the insertion point.

18. The method of claim 17, further comprising:

including in the doubly-linked list, nodes corresponding to end-of-line (EOL) tokens that mark respective line boundaries in the edit buffer.

19. The method of claim 17,

wherein the line coordinates encode both a row and a column corresponding to the insertion point.

20. The method of claim 17,

associating with the EOL tokens line-related pointers that identify respective prior and later EOL tokens of the doubly-linked list and that facilitate line-by-line traversal of the edit buffer.

21. The method of claim 17,

wherein for a given line of the edit buffer, a character count therefor is encoded in, or in association with, a corresponding one of the EOL tokens.

22. The method of claim 17, further comprising:

maintaining, coincident with an operation that modifies contents of the edit buffer, the insertion point representation.

23. The method of claim 22,

wherein the operation that modifies contents of the edit buffer includes one or more of an insert, remove, split, join or replace operation performed at the insertion point.

24. The method of claim 17, further comprising:

maintaining, coincident with movement of the insertion point to a new position, the insertion point representation.

25. The method of claim 24,

wherein the maintaining includes scanning from a particular position in the doubly-linked list toward the new position, and updating the identification of both the particular lexical token and the line coordinates.

26. The method of claim 25,

wherein the particular position corresponds to the insertion point.

27. The method of claim 25,

further comprising maintaining a representation of total character count for the edit buffer;

and

wherein the particular position corresponds to one of;

a first line of the edit buffer,

the insertion point, and

a last line of the edit buffer,

selected based on comparison with the new position to generally minimize computational overhead associated with the scanning and updating.

28. One or more computer readable media encoding a data structure that represents contents of an edit buffer as a sequence of lexical tokens, the encoded data structure comprising:

a doubly linked list of nodes;

token representations each corresponding to at least one respective node of the list, wherein at least some of the token representations have associated string encodings; and

an insertion point representation identifying, for the insertion point, both a particular one of the lexical tokens and a particular line in which the particular token resides.

29. The encoded data structure of claim 28,

wherein the particular line identification encodes both a row and a column corresponding to the insertion point.

30. The encoded data structure of claim 28,

wherein the insertion point representation further includes an offset in to a text string associated with the particular token.

31. The encoded data structure of claim 28, embodied as a software object that defines at least one operation that repositions the insertion point,

wherein performance of the repositioning operation updates both the particular lexical token and the particular line.

32. The encoded data structure of claim 28, embodied as a software object that defines edit operations on contents of the edit buffer,

wherein, consistent with semantics thereof, each of the edit operations performed on the edit buffer updates the particular lexical token and the particular line.

33. The encoded data structure of claim 28,

wherein the one or more computer readable media are selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium and a network, wireline, wireless or other communications medium.

34. A method of supporting access by one or more software engineering tools to program code, wherein at least one such tool operates on the program code as a token sequence and at least one such tool operates on the program code as a line-delimited character sequence, the method comprising:

maintaining a representation of the program code as a doubly-linked list of nodes, each node corresponding to a lexical token thereof; and

responsive to repositioning of an insertion point, updating a representation thereof that identifies;

a particular one of the lexical tokens;

a character offset into a string associated with the particular lexical token; and

line coordinates corresponding to the identified token and character offset.

35. The method of claim 34, further comprising:

including in the program code representation at least some end-of-line (EOL) tokens corresponding to line boundaries therein.

36. The method of claim 35,

wherein forward and backward pointers at least partially define the doubly-linked list;

and

wherein additional line-related pointers are associated with the EOL tokens, the line-related pointers identifying respective previous and next EOL tokens of the doubly-linked list.

37. The method of claim 36, further comprising:

for a given line of program code, encoding a character count in, or in association with, a corresponding one of the EOL tokens.

38. The method of claim 34,

wherein the updating includes updating both a row component and a column component of the line coordinates.

39. The method of claim 34,

wherein the repositioning includes traversing from a particular position in the doubly-linked list toward a new position and updating the insertion point representation in correspondence therewith.

40. The method of claim 34,

wherein the tool that operates on the program code as a token sequence and the tool that operates on the program code as a line-delimited character sequence are different tools.

41. The method of claim 34,

wherein the tool that operates on the program code as a token sequence and the tool that operates on the program code as a line-delimited character sequence are a same tool.

42. The method of claim 34, wherein the tool that operates on the program code as a line-delimited character sequence is configured as one or more of a:

source-level debugger;

a style analyzer; and

a compiler or interpreter.

43. An apparatus comprising:

storage for a computer readable encoding of an edit buffer represented as a sequence of lexical tokens; and

means for representing an insertion point in the edit buffer, the insertion point identifying both a particular one of the lexical tokens and line coordinates.

44. The apparatus of claim 43, further comprising:

means for repositioning the insertion point, the repositioning means traversing the edit buffer line-by-line, and without with traversal of each lexical token of each intervening line so traversed.

45. The apparatus of claim 43,

wherein the insertion point representation means further identifies row and column components of the line coordinates.

46. The apparatus of claim 43,

wherein the insertion point representation means further identifies a substring offset into a substring associated with the particular lexical token.

47. The apparatus of claim 43, further comprising:

means for updating the insertion point in correspondence with a repositioning operation.

48. The apparatus of claim 43, further comprising:

means for maintaining the insertion point in correspondence with an edit operation on the edit buffer.