Undo/redo technique for token-oriented representation of program code Number:7,386,834 from the United States Patent and Trademark Office (PTO) owispatent An editor or software engineering tool may be configured to represent program code as a doubly-linked list of lexical tokens and to maintain, coincident with an operation that modifies contents of the list, an undo object that identifies opposing end nodes of a sublist of one or more lexical tokens corresponding to a substring that is either inserted into or removed from the list by the operation. In this way, lexical tokens corresponding to an inserted substring can be readily and efficiently excised to restore a pre-insertion tokenized list state. Similarly, lexical tokens corresponding to a removed substring can be readily and efficiently reinstated to restore a pre-deletion tokenized list state. Advantageously, undo support once employed to restore a prior tokenized list state is symmetrically available to support redo operations. In some embodiments in accordance with the present invention, undo-redo entries are maintained in an operation ordered set that is traversed to support one or more operations in either the undo or redo directions. In some realizations, such an ordered set of undo-redo entries is maintained by, or in conjunction with, an undo-redo manager.<H representation, technique, Undo, redo, techn, 7386834.html, Patent, pto, 7386834

Title: Undo/redo technique for token-oriented representation of program code

Abstract: An editor or software engineering tool may be configured to represent program code as a doubly-linked list of lexical tokens and to maintain, coincident with an operation that modifies contents of the list, an undo object that identifies opposing end nodes of a sublist of one or more lexical tokens corresponding to a substring that is either inserted into or removed from the list by the operation. In this way, lexical tokens corresponding to an inserted substring can be readily and efficiently excised to restore a pre-insertion tokenized list state. Similarly, lexical tokens corresponding to a removed substring can be readily and efficiently reinstated to restore a pre-deletion tokenized list state. Advantageously, undo support once employed to restore a prior tokenized list state is symmetrically available to support redo operations. In some embodiments in accordance with the present invention, undo-redo entries are maintained in an operation ordered set that is traversed to support one or more operations in either the undo or redo directions. In some realizations, such an ordered set of undo-redo entries is maintained by, or in conjunction with, an undo-redo manager.

Patent Number: 7,386,834 Issued on 06/10/2008 to Van De Vanter, et al.

Inventors: Van De Vanter; Michael L. (Mountain View, CA), Urquhart; Kenneth B. (Holly Springs, NC)
Assignee: Sun Microsystems, Inc. (Santa Clara, CA)

Appl. No.: 10/185,761

Filed: June 28, 2002

Current U.S. Class: 717/110

Field of Search: 717/110-113,530

References Cited [Referenced By]

U.S. Patent Documents


3893084	July 1975	Kotok et al.
4558413	December 1985	Schmidt et al.
4809170	February 1989	Leblang et al.
4809710	March 1989	Williamson
4931928	June 1990	Greenfeld
4989145	January 1991	Kyushima
5006992	April 1991	Skeirik
5070478	December 1991	Abbott
5079700	January 1992	Kozoll et al.
5140521	August 1992	Kozol et al.
5155847	October 1992	Kirouac et al.
5224038	June 1993	Bespalko
5239298	August 1993	Wei
5263174	November 1993	Layman
5287501	February 1994	Lomet
5293629	March 1994	Conley et al.
5311422	May 1994	Loftin et al.
5313387	May 1994	McKeeman et al.
5377318	December 1994	Wolber
5386559	January 1995	Eisenberg et al.
5386570	January 1995	Lindhorst
5410701	April 1995	Gopalraman
5430836	July 1995	Wolf et al.
5446895	August 1995	White et al.
5481711	January 1996	Sotani
5481712	January 1996	Silver et al.
5485618	January 1996	Smith
5487000	January 1996	Takahashi et al.
5487147	January 1996	Brisson
5490097	February 1996	Swenson et al.
5493678	February 1996	Arcuri et al.
5502805	March 1996	Anderson et al.
5504902	April 1996	McGrath et al.
5513305	April 1996	Maghbouleh
5537630	July 1996	Berry et al.
5557730	September 1996	Frid-Nielsen
5574898	November 1996	Leblang et al.
5577241	November 1996	Spencer
5579469	November 1996	Pike
5583762	December 1996	Shafer
5604853	February 1997	Nagashima
5625773	April 1997	Bespalko et al.
5627958	May 1997	Potts et al.
5628016	May 1997	Kukol
5644737	July 1997	Tuniman et al.
5649192	July 1997	Stucky
5649200	July 1997	Leblang et al.
5649222	July 1997	Mogilevsky
5652899	July 1997	Mays et al.
5671403	September 1997	Shekita et al.
5673390	September 1997	Mueller
5680619	October 1997	Gudmundson et al.
5680630	October 1997	Saint-Laurent
5694559	December 1997	Hobson et al.
5724593	March 1998	Hargrave, III et al.
5734749	March 1998	Yamada et al.
5737608	April 1998	Van De Vanter
5740444	April 1998	Frid-Nielsen
5748975	May 1998	Van De Vanter
5752058	May 1998	Van De Vanter
5754737	May 1998	Gipson
5778402	July 1998	Gipson
5781720	July 1998	Parker et al.
5781732	July 1998	Adams
5790778	August 1998	Bush et al.
5798757	August 1998	Smith
5802262	September 1998	Van De Vanter
5805889	September 1998	Van De Vanter
5813019	September 1998	Van De Vanter
5825355	October 1998	Palmer et al.
5832494	November 1998	Egger et al.
5844554	December 1998	Geller et al.
5845120	December 1998	Reddy et al.
5845300	December 1998	Comer et al.
5848394	December 1998	D'Arrigo et al.
5850561	December 1998	Church et al.
5857212	January 1999	Van De Vanter
5859638	January 1999	Coleman et al.
5870608	February 1999	Gregory
5872974	February 1999	Mezick
5877758	March 1999	Seybold
5890103	March 1999	Carus
5905892	May 1999	Nielsen et al.
5911059	June 1999	Profit, Jr.
5911075	June 1999	Glaser et al.
5924089	July 1999	Mocek et al.
5959629	September 1999	Masui
5960196	September 1999	Carrier, III et al.
5990906	November 1999	Hudson et al.
5991799	November 1999	Yen et al.
6002874	December 1999	Bahrs et al.
6012075	January 2000	Fein et al.
6014135	January 2000	Fernandes
6016467	January 2000	Newsted et al.
6018524	January 2000	Turner et al.
6023715	February 2000	Burkes et al.
6026233	February 2000	Shulman et al.
6053951	April 2000	McDonald et al.
6061513	May 2000	Scandura
6071317	June 2000	Nagel
6115544	September 2000	Mueller
6119120	September 2000	Miller
6154847	November 2000	Schofield et al.
6163879	December 2000	Mackey
6185591	February 2001	Baker et al.
6205579	March 2001	Southgate
6212534	April 2001	Lo et al.
6226785	May 2001	Peterson et al.
6247020	June 2001	Minard
6266665	July 2001	Vaidyanathan et al.
6275976	August 2001	Scandura
6282551	August 2001	Anderson et al.
6286138	September 2001	Purcell
6305008	October 2001	Vaidyanathan et al.
6311323	October 2001	Shulman et al.
6349327	February 2002	Tang et al.
6425016	July 2002	Banavar et al.
6426761	July 2002	Kanevsky et al.
6470306	October 2002	Pringle et al.
6470349	October 2002	Heninger et al.
6507845	January 2003	Cohen et al.
6519763	February 2003	Kaufer et al.
6604109	August 2003	Federighi et al.
6643661	November 2003	Polizzi et al.
6658624	December 2003	Savitzky et al.
6658643	December 2003	Bera
6678882	January 2004	Hurley et al.
6760695	July 2004	Kuno et al.
6792595	September 2004	Storistenau et al.
6795826	September 2004	Flinn et al.
6801026	October 2004	Schrom et al.
6901448	May 2005	Zhu et al.
6993723	January 2006	Danielsen et al.
7127704	October 2006	Van De Vanter et al.
7159207	January 2007	Tang et al.
2001/0052190	December 2001	Duncan
2001/0052910	December 2001	Parekh et al.
2002/0100016	July 2002	Van De Vanter et al.
2002/0106991	August 2002	Foore et al.
2002/0107866	August 2002	Cousins et al.
2003/0061046	March 2003	Zhao et al.
2003/0066058	April 2003	Van De Vanter et al.
2003/0208427	November 2003	Peters et al.
2003/0229648	December 2003	Tang et al.
2004/0003373	January 2004	Van De Vanter et al.
2004/0003374	January 2004	Van De Vanter et al.
2004/0006763	January 2004	Van De Vanter et al.
2004/0030741	February 2004	Wolton et al.
2004/0054644	March 2004	Ganesh et al.
2004/0225997	November 2004	Van Der Vanter et al.
2004/0225998	November 2004	Van Der Vanter et al.
2005/0022132	January 2005	Herzberg et al.

Other References

Charles Crowley, "Data Structues for Text Sequences", 1998, CiteSeer, Accessed on Sep. 22, 2005 at <http://citeseer.ist.psu.edu/crowley98data.html>. cited by examiner .
Martin Sevior, "Re: UCS-2 vs. UCS-4", Jun. 23, 2001, abiword-dev mailing list archive, accessed on Sep. 23, 2005 at <http://www.abisource.com/mailinglists/abiword-dev/01/June/0610.html&g- t;. cited by examiner .
Conner and Coskun, "Undo Model", Nov. 1993, IBM Technical Disclosure Bulletin, vol. 36, No. 11, pp. 85-87. cited by examiner .
Carrano et al., "Data Abstraction and Problem Solving with C++", Aug. 1998, Addison-Wesley, Chapter 4. cited by examiner .
Brun et al., "The Token-Oriented Approach to Program Editing", Feb. 1985, SIGPLAN Notices, vol. 20, No. 2, pp. 17-20. cited by examiner .
Gutknecht, "Concepts of the Text Editor Lara", Sep. 1985, Communications of the ACM, vol. 28, No. 9, pp. 942-960. cited by examiner .
Balance, Robert A. et al, "The Pan Language-Based Editing System," ACM Transactions on Software Engineering and Methodology, vol. 1, Issue 1, Jan. 1992, pp. 95-127. cited by other .
Finseth, Craig A, "The Craft of Text Editing," Springer-Verlag, New York, 1991. cited by other .
Teitelbaum, Tim et al., "The Cornell Program Synthesizer: A Syntax-Directed Programming Environment," Communications of the ACM, vol. 24, Issue 9, Sep. 1981, pp. 563-573. cited by other .
Bahlke, Rolf, et al., "the PSG System: From Formal Langauge Definitions to Interactive Programming Environments," ACM Transactions on Programming Languages and Systems, vol. 8, No. 4 (Oct. 1986), pp. 547-576. cited by other .
Borras, P., et al., "Centaur: the system," Proceedings ACM SIGSOFT '88: Third Symposium on Software Development Environment (Nov. 1988), pp. 14-24. cited by other .
Donzeau-Gouge, V. et al., "Programming Environments Based on Structured Editors: the Mentor Experience," Interactive Programming Enviroments, David R. Barstow et al., editors, McGraw-Hill, New York, NY (1984), pp. 128-140. cited by other .
Franke, Charles H., III et al., "Authoring a Hypertext UNIX Help Manual," ACM, 1995, pp. 238-245. cited by other .
Friendly, Lisa, "The Design of Distributed Hyperlinked Programming Documentation," Sun Microsystems, 1995, 25 pages. cited by other .
Jordan, Mick, et al., "Modular System Building with JavaTM Packages," 8th Conference on Software Engineering Environment, Apr. 1997. cited by other .
Jordan, Mick, et al., "Software Configuration Management in an Object Oriented Database," USENIX Conference on Object-Oriented Technologies (COOTS), Jun. 1995. cited by other .
Lang, Bernard, "On the Usefulness of Syntax Directed Editors," Advanced Programming Environments, Lecture Notes in Computer Science, vol. 244, Reldar Conradi et al, editors, Springer Verlag, Berlin (1986), pp. 47-51. cited by other .
Letovsky, S., et al., "Delocalized Plans and Program Comprehension," IEEE Software EE (May 1986), pp. 41-49. cited by other .
McFedries, Paul, Visual Basic for Applications Unleashed, Sams MacMillian Computer Publishing, ISBN 0672310465, Published Mar. 21, 1997 (excerpts). cited by other .
Meyrowitz, et al., "Interactive Editing Systems: Part I," 1982, ACM, vol. 14, No. 3, pp. 321-352. cited by other .
Meyrowitz, et al., "Interactive Editing Systems: Part II," 1982, ACM, vol. 14, No. 3, pp. 353-415. cited by other .
Murer, Tobias, et al., "Replacing Copies With Connections: Managing Software across the Virtual Organization," IEEE 8th International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, Stanford University, California, USA, Jun. 16-18, 1999. cited by other .
Neal, Lisa Rubin, "Cognition-Sensitive Design and User Modeling for Syntax-Directed Editors," Proceedings SIG-CHI Conference on Human Factors in Computing Systems, Toronto, Canada (Apr. 1987), pp. 99-102. cited by other .
Notkin, David, "The GANDALF Project," Journal of Systems and Software, vol. 5, No. 2 (May 1985), pp. 91-105. cited by other .
Reps, T., "Maximal-Munch' Tokenization in Linear Time," 1998, ACM, vol. 20, No. 2, pp. 259-273. cited by other .
Reps, T., et al., The Synthesizer Generator Reference Manual, Texts and Monographs in Computer Science, 3rd Ed., Springer-Verlag, NY, 1989, 180 pages. cited by other .
Simonis, Volker, ProgDOC--A Program Documentation System, Wilhelm-Schickard-Institut Fur Informatik, 2003, 27 pages. cited by other .
Soloway, E., et al., "Empirical Studies of Programming Knowledge," IEEE Transactions on Software Engineering, vol. SE-10, No. 5 (Sep. 1984), pp. 595-609. cited by other .
Stallman, Richard M., "EMACS: The Extensible, Customizable, Self-Documenting Display Editor," Proceedings of the ACM-SIGPLAN SIGOA Symposium on Text Manipulation, SIGPLAN Notices, vol. 16, No. 6 (Jun. 8-10, 1981), pp. 147-156. cited by other .
Van De Vanter, M. et al., "Coherent User Interfaces for Language-Based Editing Systems," International Journal of Man-Machine Studies, vol. 37, No. 4 (1992), pp. 431-466 (reprinted in Structure-Based Editors and Environments, Gerd Szwillus and Lisa Neal Eds., Academic Press, 1996). cited by other .
Van De Vanter, Michael L., "Biblio Text Version 5.0: A Hypertext Browser for Bibliographic Data and Notes," UC Berkeley Technical Report No. UCB/CSD 90/603, 47 pp., Nov. 1990. cited by other .
Van De Vanter, Michael L., "Coordinated Editing of Versioned Packages in the JP Programming Environment," 8th International Symposium on System Configuration Management, Jul. 1998. cited by other .
Van De Vanter, Michael L., "Practical Language-Based Editing for Software Engineers," Software Engineering and Human-Computer Interaction: ICSE '94 Workshop on SE-HCI: Joint Research Issues, Sorrento, Italy, May 1994 Proceedings, Lecture Notes in Computer Science, vol. 896, Richard N. Taylor and Joelle Coutaz, editors, Springer Verlag, Berlin (1995), pp. 251-267. cited by other .
Van De Vanter, Michael L., "The Documentary Structure of Source Code," Information & Software Technology, vol. 44, iss. 13, pp. 767-782, Oct. 1, 2002. cited by other .
Van De Vanter, Michael L., "User Interaction in Language-Based Editing Systems," Ph.D. Dissertation, UC Berkeley, Dec. 1992. cited by other .
Van De Vanter, Michael L., et al., "Displaying and Editing Source Code on Software Engineering Environments," Second International Symposium on Constructing Software Engineering Tools (CoSET'2000), Limerick, Ireland, Jun. 5, 2000. cited by other .
Van De Vanter, Michael L., et al., "Global Names: Support for Managing Software in a World of Virtual Organizations," Ninth International Symposium on System Configuration Management (SCM-9) , Toulouse, France, Sep. 5-7, 1999. cited by other .
Crowley, Charles, "Data Structures for Text Sequences", 1998, CiteSeer, accessed on Sep. 22, 2005 at <http://citeseer.ist.psu.edu/crowley98data.html>. cited by other .
Sevoir, Martin, "Re: UCS-2 vs. UCS-4", Jun. 23, 2001, abiword-dev mailing list archive, accessed on Sep. 23, 2005 at <http://www.abisource.com/mailinglists/abiword-dev/01/June/0610.html&g- t;. cited by other .
Conner, M.H., et al., "Undo Model", Nov. 1993, IBM Technical Disclosure Bulletin, vol. 36, No. 11, pp. 85-87. cited by other .
Carrano, Frank, et al., "Data Abstraction and Problem Solving with C++", Aug. 1998, Addison-Wesley, Chapter 4., pp. 147-214. cited by other .
Arefi, F. et al., "Automatically Generating Visual Syntax-Directed Editors," Communications ACM, vol. 33, No. 3, Mar. 1990, pp. 349-360. cited by other .
Ford, Bryan, "Packrat, parsing, simple, powerful, lazy, linear time," ACM ICFP, pp. 36-47, 2002. cited by other .
Ramsey, Norman, "Literate Programming Simplified," IEEE Software, vol. 11, Issue 5 (Sep. 1994), pp. 97-105. cited by other .
Baecker, R.M., et al., "Human Factors and Typography for More Readable Programs", ACM Press, 1990, p. 334-337. cited by other .
Baker, N. et al., "An Object Model for Product and Workflow Data Management," Database and Expert Systems Applications, 1998, 4 pgs. cited by other .
Proceedings: Ninth International Workshop on Database and Expert Systems Applications, Aug. 26-28, 1998, pp. 731-738. cited by other .
Grundy, John C. et al., "Support for Collaborative, Integrated Software Development," IEEE 1995, pp. 84-94. cited by other .
Lee, Byong G. et al., "An Integrated Approach to Version Control Management in Computer Supported Collaborative Writing," ACM 1998, pp. 34-43. cited by other .
Prakash, Atul et al., "DistView: Support for Building Efficient Collaborative Applications using Replicated Objects," ACM 1994, pp. 153-164. cited by other .
Kitchovitch, Milosh M., "Parsing Method Supporting the Process of Program Editing with Online Syntax Checking," Jan. 1993, Problems of Engineering Cybernetics and Robotics, vol. 40, pp. 49-59. cited by other .
Shilling, John J., "Incremental LL(1) parsing in Language-Based Editors," Sep. 1992, IEEE Transactions on Software Engineering, vol. 19, No. 9, pp. 935-940. cited by other .
Lunney, T.F. et al., "Syntax-Directed Editing," Mar. 1988, Software Engineering Journal, vol. 3, No. 2, pp. 37-46. cited by other .
Madhavji, Nazim H. et al., "Semi-Structured Cursor Movements in MUPE-2," Nov. 1989, Software Engineering Journal, vol. 4, No. 6, pp. 309-317. cited by other .
Zelkowitz, Marvin V. et al., "Experiences Buiding a Syntax-Directed Editor," Nov. 1989, Software Engineering Journal, vol. 4, No. 6, pp. 294-300. cited by other .
Video DVD: Siggraph Video Review: Magpie--Tektronix. (Item #9), Issue 9, CHI'95, Jun. 1985. cited by other .
Oman, Paul W. et al., "Typographic Style Is More Than Cosmetic," Communications of the ACM, May 1990, vol. 33, No. 5, pp. 506-520. cited by other .
Reps, Thomas et al., "The Synthesizer Generator Reference Manual," Dept. of Computer Science, Jul. 1987, Section 3, pp. 79-106. cited by other .
Ballance, Robert A. et al., "Grammatical Abstraction and Incremental Syntax Analysis in a Language-Based Editor," Jun. 1988, pp. 185-198. cited by other .
Calliss, Frank W., "Problems with Automatic Restructurers," Nov. 1987, University of Durham, Durham, England, pp. 13-21. cited by other .
Schwartz, Mayer D. et al., "Incremental Compilation in Magpie," Jun. 1984, vol. 19, No. 6, pp. 122-131. cited by other .
Levin, Roy et al., "The Vesta Approach to Precise Confuguration of Large Software Systems," Jun. 14, 1993, Digital Systems Research Center, pp. 1-38. cited by other .
Ballance, Robert A. et al., "The Pan Language-Based Editing System," Sep. 1991, ACM Transactions on Software Engineering & Methodology, vol. 1, pp. 95-127. cited by other .
Gray, Robert W: ".lamda. -GLA: A Generator for Lexical Analyzers That Programmers Can Use," Jun. 1988, Proceedings of the Summer 1988 Usenix Conference, San Franciso, CA, USA, pp. 147-160. cited by other .
Reiss, Steven P: "Automatic Compiler Production: The Front End," IEEE Transactions on Sofware Engineering, Jun. 1987, vol. SE-13, No. 6, , pp. 609-627. cited by other .
Levine, John R. et al., Doug Brown Lex & Yacc O'Reilly & Associates Inc, Subostopal, CA 1992, I pg. cited by other .
Thiemann, Peter, "Grammar-Based Analysis of String Expressions," ACM 2005, pp. 59-70. cited by other .
Ford, Bryan "Parsing Expression Grammars: A Recognition Based Syntactic Foundation," ACM 2004, pp. 111-122. cited by other .
"Re: Piece Tables," Apr. 4, 2000, http://www.abisource.com/mailinglists/abiword-dev/00/April/0055.html, 4 pages. cited by other .
Timoshkina, Uljana et al., "Structured Documents Processing using Lex and Yacc," 2001, http://citeseer.ist.psu.edu/475903.html, 1 pg. cited by other.

Primary Examiner: Dam; Tuan
Assistant Examiner: Rutten; J. Derek
Attorney, Agent or Firm: Darby & Darby PC Ream; M. David

Claims

What is claimed is:

1. A method of providing undo operation support in an edit buffer, the method comprising: representing the edit buffer as a doubly-linked list of nodes for a tokenized program representation, each node corresponding to a respective lexical token in the tokenized program representation; and maintaining, as a side-effect of operations that modify contents of the list, an ordered set of undo objects that identify at least respective opposing-end nodes of respective sublists of one or more lexical tokens in the tokenized program representation corresponding to respective substrings inserted into the list by respective insert-type operations, wherein at least one of the sublists comprises different opposing end nodes stored non-contiguously and each of the sublists is a doubly linked list.

2. The method of claim 1, further comprising: maintaining the ordered set of undo objects to further identify at least respective opposing-end nodes of respective doubly-linked sublists of one or more lexical tokens corresponding to respective substrings removed from the list by respective remove-type operations.

3. The method of claim 2, wherein the opposing-end nodes of a particular sublist removed from the list by execution of a particular one of the remove-type operations maintain an identification of respective predecessor and successor nodes of the list prior to the execution of the particular remove-type operation.

4. The method of claim 2, further comprising: restoring, coincident with an undo directive, the doubly-linked list of lexical tokens to a state that existed prior to execution of a particular remove-type operation at least in part by reintroducing thereinto the sublist identified by a corresponding one of the undo objects; and maintaining as a redo object, identification of at least the opposing end nodes of the reintroduced sublist.

5. The method of claim 1, wherein, for a particular lexical token of the list replaced by a replace-type operation, the maintaining includes encoding in a corresponding one of the undo objects an identification of the replaced token.

6. The method of claim 1, wherein, for a particular lexical token of the list split by an insert-type operation, the maintaining includes replicating in a sublist inserted into the list, substrings corresponding to the split token; and wherein the corresponding one of the undo objects further identifies a particular node corresponding to the split token.

7. The method of claim 1, further comprising: restoring, coincident with an undo directive, the doubly-linked list of lexical tokens to a state that existed prior to execution of a particular insert-type operation at least in part by removing therefrom the sublist identified by a corresponding one of the undo objects; and maintaining as a redo object, identification of at least the opposing end nodes of the removed sublist.

8. The method of claim 7, wherein the corresponding one of the undo objects and the redo object are encoded as a same object.

9. The method of claim 1, wherein at least one of the undo objects identifies a sublist that includes a single lexical token, and wherein opposing-end nodes of the sublist are a same node.

10. A software engineering tool encoded in one or more computer readable media, the software engineering tool comprising: a representation of program code encoded in a computer readable medium as a doubly-linked list of nodes for a tokenized program representation, each node corresponding to a respective token in the tokenized program representation recognized in accordance with an operative set of lexical rules; functional encodings of edit methods, including at least insert-type and remove-type methods, the edit methods executable to operate on the list of nodes; and an undo-redo manager that maintains an ordered set of undo-redo objects in correspondence with operation of the edit methods, the undo-redo objects identifying opposing-end nodes of sublists of tokens inserted into the list and removed therefrom by operation of the insert-type and remove-type methods, respectively, wherein at least one of the sublists comprises different opposing end nodes stored non-contiguously and each of the sublists is a doubly-linked list.

11. The software engineering tool of claim 10, further comprising: a functional encoding of an undo directive that reverses effects of a previously executed edit method on state of the list, while maintaining the identification of opposing-end nodes of a corresponding doubly-linked sublist of tokens for use in a subsequent redo directive.

12. The software engineering tool of claim 10, a functional encoding of a redo directive that reinstates effects of a previously executed edit method on state of the list, while maintaining the identification of opposing-end nodes of a corresponding sublist of tokens for use in a subsequent undo directive.

13. A software engineering tool encoded in one or more tangible computer readable media as instructions executable to represent program code as a doubly-linked list of lexical tokens for a tokenized program representation and to maintain, coincident with an operation that modifies contents of the list, a first undo object that identifies at least opposing end nodes of a sublist of one or more lexical tokens in the tokenized program representation corresponding to a substring that is either introduced into or removed from the list by the operation, wherein the sublist comprises different opposing end nodes stored non-contiguously and is a doubly-linked list.

14. The software engineering tool of claim 13, wherein the operation is an insert-type operation and the sublist of lexical tokens corresponds to a substring introduced by the insert-type operation.

15. The software engineering tool of claim 13, wherein the operation is an remove-type operation and the sublist of lexical tokens corresponds to a substring removed by the remove-type operation.

16. The software engineering tool of claim 13, wherein the instructions are further executable, coincident with an undo directive, to restore the doubly-linked list of lexical tokens to a prior state using the sublist identified by the first undo object, and to maintain as a redo object identification of at least the opposing end nodes of the sublist.

17. The software engineering tool of claim 16, wherein the first undo object and the redo object are encoded as a same object.

18. The software engineering tool of claim 13, wherein an operation-ordered store of undo objects, including the first undo object, is maintained for use by the software engineering tool.

19. The software engineering tool of claim 13, further comprising: an operation-ordered store of undo-redo objects, including the first undo object.

20. The software engineering tool of claim 13, wherein the one or more tangible computer readable media are selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium.

21. One or more tangible 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 for a tokenized program representation; token representations, each corresponding to at least one respective node of the list, wherein at least some of the token representations have associated substring encodings; and an edit-operation-ordered representation of undo objects that each identify at least opposing end nodes of respective sublists of one or more lexical tokens in the tokenized program representation that correspond to substrings that are either introduced into or removed from the list by edit operations, wherein at least one of the sublists comprises different opposing end nodes stored non-contiguously and each of the sublists is a doubly-linked list.

22. The encoded data structure of claim 21, wherein the identification of opposing end nodes allows reversal of substring introductions and removals in response to respective undo directives with a computational burden that is independent of size of the edit buffer and independent of size of the substrings introduced and removed.

23. The encoded data structure of claim 21, embodied as a software object that defines at least one of the edit operations.

24. The encoded data structure of claim 21, wherein the one or more tangible computer readable media are selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium.

25. An apparatus comprising: storage for a computer readable encoding of an edit buffer represented as a sequence of lexical tokens for a tokenized program representation; and means for maintaining an edit-operation-ordered representation of undo objects that each identify at least opposing end nodes of respective sublists of one or more lexical tokens in the tokenized program representation that correspond to substrings that are either introduced into or removed from the list by edit operations, wherein at least one of the sublists comprises different opposing end nodes stored non-contiguously and each of the sublists is a doubly-linked list.

26. The apparatus of claim 25, further comprising: means for reversing a particular execution of one of the edit operations using the opposing-end nodes identification of a corresponding one of the undo objects.

27. The apparatus of claim 26, further comprising: means for maintaining the opposing-end nodes identification corresponding to the reversed edit operation for use in reinstatement of the reversed edit operation.

Description

CROSS-REFERENCE TO RELATED APPLICATION(S)

This application is related to commonly owned U.S. patent application Ser. No. 10/185,752, entitled "TOKEN-ORIENTED REPRESENTATION OF PROGRAM CODE WITH SUPPORT FOR TEXTUAL EDITING THEREOF," naming Van De Vanter and Urquhart as inventors and filed on even date herewith, Ser. No. 10/185,753, entitled "EFFICIENT COMPUTATION OF CHARACTER OFFSETS FOR TOKEN-ORIENTED REPRESENTATION OF PROGRAM CODE," naming Van De Vanter and Urquhart as inventors and filed on even date herewith and Ser. No. 10/185,754, entitled "UNDO/REDO TECHNIQUE WITH INSERTION POINT STATE HANDLING FOR TOKEN-ORIENTED REPRESENTATION OF PROGRAM CODE," naming Van De Vanter and Urquhart as inventors and filed on even date herewith.

BACKGROUND

1. Field of the Invention

The present invention relates generally to interactive software engineering tools including editors for source code such as a programming or mark-up language, and more particularly to facilities for supporting undo and/or redo operations on a token-oriented representation.

2. Description of the Related Art

In an editor for computer programs, it may be desirable to represent program code using a token-oriented repres