United States Patent 11
`Schmidtetal.
`
`[11] Patent Number:
`[45] Date of Patent:
`
`4,558,413
`Dec. 10, 1985
`
`[54] SOFTWARE VERSION MANAGEMENT
`SYSTEM
`
`[75]
`
`Inventors: Eric E, Schmidt, Los Altos, Calif.;
`Butler W. Lampson, Philadelphia, Pa.
`[73] Assignee: Xerox Corporation, Stamford, Conn.
`[21] Appl. No.: 553,724
`(22] Filed:
`Nov. 21, 1983
`Tint, C14 oocceccssccssseccccsrserensenenseeerenseseneta GO6F 15/20
`[SU]
`
`[52]. USEC anna.
`364/300; 364/200
`[58] Field of Search ...........:-ccsecssecseerereeernseets 364/300
`[56]
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,309,756
`
`1/1982 Beckler ......ccccecenecseeeeee 364/300
`
`OTHER PUBLICATIONS
`
`Morse et al., DOS/AMAP Model of the DOS Control
`Program, /.B.M. Technical Disclosure Bulletin, vol. 14,
`No. 3, Aug. 1971, pp. 852-853.
`Alan L. Glasser, ‘The Evolution of a Source Code
`Control System”, Proc. Software Quality and Assur-
`ance Workshop, Software Engineering Notes, vol. 3,
`No. 5 pp. 122-125, Nov. 1978.
`Ira P. Goldstein & Daniel G. Bobrow, “Representing
`Design Alternatives”, Proceedings of the Artificial
`Intelligence and Simulation of Behavior Conference,
`Amsterdam, Jul. 1980.
`Raul
`Ellison,
`Robert
`A. Nico Habermann,
`Medina-Mora, Peter Feiler, David S. Notkin, Gail E.
`Kaiser, David B. Garlan & Steven Popovich, “The
`Second Compendium of Gandall Documentation”
`CMUDepartment of Computer Science, May 24, 1982.
`Gail E. Kaiser & A. Nico Habermann, “An Environ-
`ment for System Version Control” in The Second Com-
`pendium of Gandalf Documentation, CMU Department
`of Computer Science, Feb. 4, 1982.
`B. W. Lampsonetal., “Practical Use of a Polymorhic
`Applicative Language”, Proceedings of the 10th Sym-
`posium on Principles of Programming Languages, Aus-
`tin, Texas, Jan. 1983.
`W. F. Tichy, “Design Implementation and Evaluation
`of a Revision Control System”, Proceedings of the 6th
`International Conference on Software Engineering,
`Tokyo, Japan, Sep. 1982.
`
`Dissertation of Eric Emerson Schmidt, entitled “Con-
`trolling Large Software Developmentin a Distributed
`Environment”, approved Nov. 1982.
`Xerox Palo Alto Research Centers Publication, CSL-8-
`2-7, dated Dec. 1982, “Controlling Large .
`.
`. Environ-
`ment”, Schmidt.
`Ira P. Goldstein & Daniel G. Bobrow, “A Layered
`Approach to Software Design,” Xerox Parc. Tech.
`Report, CSL-80-5, Dec. 1980.
`James G. Mitchell et al., “Mesa Language Manual,
`Version 5.0” Xerox Parc. Tech. Report, CSL-79-3,
`Apr. 1979.
`
`(List continued on next page.)
`
`Primary Examiner—Raulfe B. Zache
`Attorney, Agent, or Firm—W. Douglas Carothers, Jr.
`[57]
`ABSTRACT
`A software version management system, also called
`system modeller, provides for automatically collecting
`and recompiling updated versions of componentsoft-
`ware objects comprising a software program for opera-
`tion on a plurality of personal computers coupled to-
`getherin a distributed software environmentvia a local
`area network. The component software objects include
`the source and binary files for the software program,
`which stored in various different local and remote stor-
`age means through the environment. The component
`software objects are periodically updated, via a system
`editor, by various users at their personal computers and
`then stored in designated storage means. The manage-
`ment system includes models which are also objects.
`Eachof the models is representative of the source ver-
`sions of a particular component software object and
`contain object pointers including a unique nameofthe
`object, a unique identifier descriptive of the cronologi-
`cal updating ofits current version, information as to an
`object’s dependencies on other objects and a pathname
`representative of the residence storage means of the
`object. Means are provided in the system editor to no-
`tify the management system when any one of the ob-
`jects is being edited by a user and the management
`system is responsive to such notification to track the
`edited objects and alter their respective models to the
`current version thereof.
`
`6 Claims, 29 Drawing Figures
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`

`

`4,558,413
`
`Page 2
`
`OTHER PUBLICATIONS
`;
`A. Nico Habermann,“Tools for Software System Con-
`struction”, Proceedings of the Software Tools Work-
`shop, Boulder, Colorado, May 1979.
`Arra Avakian, Sam Haradhvala, Julian Horn & Bruce
`Knobe, “The Design of an Integrated Support Software
`System”, Proceedings of the SIGPLAN "82 Sympo-
`sium on Compiler Construction, pp. 308-317, Jun.
`23-25, 1982.
`Lee W. Cooprider, The Representation of Families of
`Software Systems, Ph.D Thesis, CMU Computer Sci-
`ence Department, CMU-CS-79-116, Apr. 14, 1979.
`Eugene Cristofor, T. A. Wendt & B. C. Wonsiewicz,
`“Source Control+Tools=Stable Systems”, Proceed-
`ings of the Fourth Computer Software and Applica-
`tions Conference, pp. 527-532, Oct. 29-31, 1980.
`A. Demers & J. Dononhue, “Data Types, Parameters,
`and Type Checking”, Proceedingsofthe Seventh Sym-
`posium on Principles of Programming Languages, Las
`Vegas, Nevada, pp. 12-23, 1980.
`Frank DeRemer & H. Kron, “Programming-in--
`the-Large Versus Programming-in-the-Small”, IEEE
`Transactions on Software Engineering, vol. 2, No. 2,
`pp. 80-86, Jun. 1976.
`Stuart I. Feldman, “Make-A Program for Maintaining
`Computer Programs”, Software Practice and Experi-
`ence, vol. 9, No. 4, pp. 255-256, Apr. 1979.
`Ira P. Goldstein & Daniel G. Bobrow, “Descriptions
`for a Programming Environment”, Proceedings of the
`
`First Annual Conferenceof the National Association of
`Artificial Intelligence, Stanford, California, Aug. 1980.
`Eric Harslem and LeRoyE. Nelson, “A Retrospective
`on the Developmentof Star”, Proceedings of the 6th
`International Conference on Software Engineering,
`Tokyo, Japan, Sep. 1982.
`Thomas R. Horsley & William C. Lynch, “Pilot: A
`Software Engineering Case Study”, Proceedings of the
`4th International Conference on Software Engineering,
`pp. 94-99, 1979.
`Evan L. Ivie, “The Programmer’s Workbench-A Ma-
`chine for Software Development”, Communications of
`the ACM,vol. 20, No. 10, pp. 746-753, Oct. 1977.
`Hugh C, Lauer & Edwin H. Satterthwaite, “The Im-
`pact of Mesa on System Design”, Proceedings of the
`4th International Conference on Software Engineering,
`pp. 174-182, 1979.
`D. Redell, Y. Dalal, T. Horsley, H. Lauer, W. Lynch,
`P. McJones, H. Murray & S. Purcell, “Pilot: An Operat-
`ing System for a Personal Computer”, Proceedings of
`the Seventh Symposium on Operating System Princi-
`ples, Dec. 1979.
`Marc J, Rochkind, “The Source Code Control Sys-
`tem”, IEEE Transactions on Software Engineering,
`vol. 1, No. 4, pp. 364-370, Dec. 1975.
`Walter F. Tichy, Software Development Control Based
`on System Structure Description, PH.D., Thesis, CMU
`Computer Science Department, CMU-CS-80- 120, Jan.
`1980.
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet 1 of24
`
`4,558,413
`
`
`
`PRIOR
`
`ART
`
`FIG.
`
`17
`
`ab.sl
`
`ab.s1
`
`a.sl
`
`b.sl
`
`Makefile
`
`4.7
`
`1.2
`
`3.5
`
`b.s]
`
`x2.0
`
`x2.c
`
`
`
`
`
`Makefile 3.5
`
`Makefile
`
`PRIOR ART
`
`FIG. 2
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet20f24
`
`4,558,413
`
`
`
`
`
`
`Composition C1
`
`
`Other modules and boxes
`
`Other modules and boxes
`
`Version 2(std)
`
`Other modules
`
`PRIOR
`
`ART
`
`FIG. 3
`
`Configuration Object File
`
`— a
`
`Source File
`
`Implementation Object Files
`
`Source File
`
`Object files for Interfaces
`
`FIG. 6
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 3 of 24
`
`4,558,413
`
`Client:PROGRAM IMPORTS SqrtInt =
`
`..code to compute sqrt of a number
`
`}3
`
`{
`
`
`
`Implementor:
`PROGRAM EXPORTS SqrtInt ={
`
`
`
`Sqrt: PUBLIC PROC(s: REAL ]RETURN[REAL J={
`
`
`SqrtInt:DEFINITIONS = {
`
`
`Sqrt: PROC[REAL ]RETURNS[REAL];
`
`}.
`
`FIG. 4
`
`Impelementation object file
`
`d
`
`Source file
`
`Object files for interfaces
`
`FIG. 5
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`

`

`U.S. Patent
`
`Dec.10, 1985
`
`Sheet 40f24
`
`4,558,413
`
`
`
`
`Storage
`Disk
`
`
`
`
`
`Server
`Computer
`
`
`
`Personal
`Computer
`
`
`
`FIG. 7
`
`To other networks
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 5 of 24
`
`4,558,413
`
`Users make changes while
`running on released software
`
`Release Master sends
`call for submissions
`
`DF files in boot file
`are all announced as ready
`
`Boot file for new
`release is prepared
`
`Remaining DF Files are
`all announced as ready
`
`Release Master prepares
`top-level DF file
`
`Phases One and Two
`are run at least once
`
`Phase Three is run
`
`Release Master announces
`release is complete
`
`
`
`Users make changes to
`their software in response
`to errors reported by
`Phases One and Two
`
`
`
`
`
`
`
`FIG. 8
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet60f24
`
`4,558,413
`
`PriorityQuene.DF
`
`CedarControl .DF
`
`UserExec.DF BBV.DF
`
`_ B
`
`ugBane.DF
`
`FileTool.DF
`
`
`TTYIO.DF
`
`
`
`
`
`ViewersAndTioga.DF
`
`ColorPackage.DF onjineMergeSort.DF
`
`MesaScanner.DF
`Graphics .DF
`Inscript.DF
`RiggingMaker.DF
`
`SpecialBringOver.DF
`
`IQ.DF, WoridVM.DF,
`Runtime.DOF,
`ListsAndAtoms.DF, CIFS.DF
`
`RPCRuntime.DF
`
`DateAndT ime. DF
`
`GrapevineUser.DF|CedarSnapshot.DF
`
`
`
`
`
`
`
`
`Rigging.DF
`
`Loader .DF
`
`
`
`
`
`
`Random.DF
`
`
`
`
`
`Pine.DF CedarReals.DF|BasicHeads*.DF CFW.DF
`
`FTP.DF
`
`Bcd. DF
`
`
`a,DF TerminalMultiples.DF
`4DF
`catDF
`1centerrackeDF
`
`FIG. 9
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 7 of 24
`
`4,558,413
`
`
`
`IO.DF, World.DF, VersionMap.DF,
`Runtime.DF,
`ListsAndAtoms.DF, CIFS.DF
`
`
`
`stands for
`
`||
`
`
`
`CIFS.DF
`
`10.DF
`A
`
`ListsAndAtoms . DF
`
`Runtime. DF> Wor 1d VM. DF
`
`VisionMap.DF
`
`FIG. 10
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 9
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 9
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet8 of 24.
`
`4,558,413
`
`TTYIO.DF
`
`FileTool.OF
`
`BBY.DF
`
`| ;-————
`
`ViewersAndTioga.DF
`
`ColorPackage.DF
`
`TIP.DOF
`
`UserExec.DF
`
`Graphics.DF
`
`I0.DF
`
`BugBane.DF
`
`MesaScanner. DF
`
`Loader .DF
`
`SpecialBring
`Over .DF
`
`
`
`
`Pine.DF
`ListsAndAtoms.DF
`
`Inscript.DF
`Runtime .DF— WorldVM.D
`
`
` VisionMap.DF
`
`CIFS.DF
`RPCRuntime.DF
`
`GrapevineUser .DF
`
`
`
`CompatibilityPackage.DF
`
`PriorityQueue.DF
`
`Communication*.DF
`
`TerminalMultiplex.DF
`
`CedarReals.DF
`
`BTrees.DF
`
`
`
`
`
`DateAndT ime. DF
`CedarSnapshot.OF
`
`BasicHeads®.DF
`
`
`
`FIG.
`
`117
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 10
`
`Rigg tgs OE
`
`Cedar
`FTP.DF Bed.DF Control.DF
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 10
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 9 of 24
`
`4,558,413
`
`VisionMapBuilder.DF
`
`UECP.DF
`
`
`Chat.DF
`
`CIFSCommands .DF
`
`
`DFFiles.DF
`
`i
`Sequin.DF
`
`—————
`
`i
`IFSFile.DF odeller.DF
`
`Boot
`
`File
`
`Compiler.DF
`
`Binder .DF
`Lister .DF
`
`Packager.DF
`PGS . DF
`PressPackage.DF ~—— Print.DF
`PerfStats .DF ~——— CedarDB.DF
`
`CoFork.DF ~—————PlotPackage.DF
`Spy .OF ~————— Lupine. DF
`SirPress.DF ~——— PressScreen.df
`
`BrovoToTioga.DF
`CedarRealTest.DF
`
`IncludeChecker .DF
`
`Maintain.DF
`
`MakeBoot.DF
`
`MCross.DF
`Othello*.DF |
`
`PupWatch.DF
`
`RedBlackTreeRef . DF
`
`Set.DF
`
`STPServer.DF
`
`TJamGraphics.DF
`
`Unique.DF
`WalnutSend.DF
`
`WaterLily.DF
`
`RedBlack
`Tree.DF
`
`FIG. 12
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 11
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 11
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 10 of24 4,558,413
`
`Clientimp].Mesa
`
`DIRECTORY
`
`Sort;
`
`Clientmp1:PROGRAM IMPORTS Sort={
`
`TestThem:PROC[I:LIST OF Object]={
`
`--call USortList with this list
`
`T+Sort.USortList[1,CompareObject];
`
`}3
`
`CompareObject:PROC[a,b:Object]
`
`RETURNS[Comparison]={
`--compares the two objects
`
`--returns less, equal, or greater };
`
`FROM
`FIG. 13B
`
`Sort.Mesa
`
`Sort: DEFINITIONS={
`
`Object: TYPE=RECORD[
`
`xX, y:INT
`
`a
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`RETURNS[LIST OF Object];
`
`FIG. 13A
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 12
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 12
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 11 of 24 4,558,413
`
`SortImp1].Mesa
`
`DIRECTORY
`
`Sort;
`
`SortImp1:PROGRAM EXPORTS Sort={
`
`USortList:PROC[I:LIST OF Object,
`
`3
`
`compareProc: CompareProc]
`
`RETURNS[newl:LIST OF Objectj={
`
`--code to sort the list I,
`
`eliminating duplicates
`
`TO FIG. 13A
`
`FIG. 13B
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 13
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 13
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 12 of 24 4,558,413
`
`SortCoord.Mesa
`
`Sort:DEFINITIONS={
`
`Object: TYPE=RECORD[
`
`x,y: INT
`
`1:
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`RETURNS[LIST OF Object];
`RETURNS[LIST OF Object];
`
`SortNames.Mesa
`
`Sort:DEFINITIONS={
`
`Object: TYPE=RECORD[
`
`x: STRING
`
`J:
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`FIG. 14
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 14
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 14
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 13 of 24 4,558,413
`
`SortQuickImp!].Mesa
`
`DIRECTORY
`
`Sort;
`
`SortQuickImp1:PROGRAM EXPORTS Sort={
`
`USortList:PUBLIC PROC[I:LIST OF Object,
`
`compareProc:CompareProc]
`
`RETURNS(newI:LIST OF ObjectJj={
`
`--code to sort the list I, eliminating duplicates
`
`--use QuickSort
`
`‘3
`33
`
`SortHeapImp!.Mesa
`
`DIRECTORY
`
`Sort;
`
`SortHeapImp1:PROGRAM EXPORTS Sort={
`
`USortList:PUBLIC PROC[I:LIST OF Object,
`
`compareProc:CompareProc]
`
`RETURNS[newl:LIST OF Object]={
`
`--code to sort the list I, eliminating duplicates
`
`--use HeapSort
`
`FIG. 15A
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 15
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 15
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 14 of 24 4,558,413
`
`ClientImp].Mesa
`
`DIRECTORY
`
`Sort;
`
`ClientImp1: IMPORTS SortQuickInst:Sort.SortHeapInst:Sort=
`
`TestThem:PROC[I:LIST OF Object]={
`
`--call USortList with this list,
`
`try QuickSort
`
`newl+SortQuickInst.USortList[1.CompareObject];
`
`};
`
`---now try HeapSort
`
`newl+SortHeapInst.USortList[1.CompareObject]:
`
`}:
`
`CompareObject:PROC[a,b:Object]
`
`RETURNS[Comparison]={
`
`--compares the two objects
`--returns less, equal, or greater
`
`FIG. 15B
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 16
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 16
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 15 of 24 4,558,413
`
`ClientImp].Mesa
`
`DIRECTORY
`
`SortCoord: INTERFACE Sort,
`
`SortNames: INTERFACE Sort;
`
`--compares a and b, returns less, equal, or greater
`
`ClientImp1:PROGRAM IMPORTS SortQuickCoordiInst:SortCoord,
`
`SortQuickNamesInst:SortNames , SortHeapCoordInst:SortCoord,
`
`SortHeapNamesInst={
`
`TestThem:PROC[I1:LIST OF SortCoord.Object,12:LIST OF SortNames.Object]=
`
`newl*SortQuickCoordInst.USortList[I1, CompareCoordinateObjects];
`
`newl+SortHeapCoordInst.USortList[I1, CompareCoordinateObjects);
`
`newl+SortQuickNamesInst.USortList[I2, CompareNameObjects],
`
`newl+SortHeapNamesInst.USortList[I2, CompareNamesObjects]:
`
`}3
`
`CompareCoordinateObjects:PROC[a,b:7SortCoord.Object ]JRETURNS[Compar ison)={
`
`--compares a and b, returns less, equal, or greater
`
`}s
`
`CompareNameOb jects: PROC[a,b: SortNames.Ob ject JRETURNS[Compar ison ]={
`
`FIG. 16
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 17
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 17
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 16 of24 4,558,413
`
`Btree.model!(Jan 14, 1983, 14:44:11)
`
`LET @[Indigo}<Cedar>Cedarinsiaces.model{July 25, 1982, 14:03:03)IN
`
`LETinstances~ @[Indigo}<Cedar>Cedar Instandes.model!(July 25, 1982, 14°10:12)IN
`
`8Tree:INTERFACE 8Tree~ @[Ivy]<Schmidt>STree.cedar!(Sept 9,1982, 13:52:55)
`
`[Ascii],
`
`BTreelnst: BTree~@[Ivy]}<SchmidbSTree!mpl.cedar!(Jan 14, 1983, 14:44:09)
`
`*[] [instances.Aope, Instances./O, instances.Space] )
`
`)
`
`Cedarlinterfaces.model!(July, 25, 1982, 14:03:03)
`
`[
`
`Ascii:INTERFACE~ @[Indigo}<Cedar>Ascii.cedar!(July 10, 1982, 12:25:00)[],
`
`Rope:INTERFACE ~ @[Indigo]<Cedar>Rope.cecar!(July 10, 1982, 17:00:00)*{],
`
`IO:INTERFACE ~ @[Indigo}<Cedar>l0.cedar!(July 12, 1982, 11:00:00)"[].
`
`Space: INTERFACE ~ @[Indigo]<Cedar>Space. Cedar!(June 10, 1982, 8:35:00)"[]]
`
`Cedarinstances.model!(July 25, 1982, 14:10:12)
`
`(Ascii, Rope, 10, Space]~
`
`LET @Cedarinterface.mode!!(July 25, 1982, 14:03:03) IN [
`
`@[Indigo)<Cedar>Asciiimp!.cedar\(July 10, 1982, 12:30:00)()[],
`
`@[Indigo]<Cedat>Ropelmpl. cedat!{July 10, 1982, 17:10:24)*!]* [],
`
`@[Indigo}<Cedar>/O/mpl.cedar!(July 20, 1982, 13:03:03) *[)*[],
`
`@[Indigo}<Cedar>Space.cedar!(June 11, 1982, 15:00:00) *{}"{) ]
`
`FIG. 17
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 18
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 18
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet 17 of24 4,558,413
`
`Object type table
`
`Source object
`Type
`
`
`8Tree,Cedar!(Sept 9, 1982, 13:52:55)
`
`{INTERFACEAscii]- [INTERFACESTree]
`
`8Treeimpi.cedar!(Jan 9, 1983, 14:44:09)
`
`[Rope:INTERFACEAope, i0,Space: INTERFACE Space.
`
`BTree:INTERFACES Tree]
`
`[{Ropelnst:Rope., (0, Spaceinst:Space)
`BTree]}
`
`[BTreeinst:
`
`Projection table
`
`
`
`Source object
`Parameter values
`Results object
`
`
`BTree.cedar!(Sept 9.1982,
`13:52:55)
`
`[Ascii.binary!23ACD904EFFA]
`
`BTree.binary!43956A3C32F0
`
`BTreelmpl.cedar!(Jan 14, 1983,
`14:44:09)
`
`[Rope. binary! AC9O23E76FA6.
`10. binary!23843396A24f,
`
`BTreelmpl.binary!2045FFD283C
`
`Space. binary!8348823FF761,
`BTree. binary!43956A3C32F0]
`
`
`FIG. 18
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 19
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 19
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 18 of24 4,558,413
`
`Version map
`
`
`
`Object name
`File location
`
`
`8Tree.cedar\(Sept 9, 1982, 13:52:55)
`
`[lvy]<Schmidt>BTree.cedar4
`
`BTree./mpl.cedar!(Jan 14,1983, 14:44:09)
`
`[lvy]<Schmidt>BTreelmpl.cedar!g9
`
`BTree.binary!43956A3C32F0
`
`{lvy]<Schmidt>BTree.binary!2
`
`BTreelmpl.binary!2045FFD283C
`
`[Ilvy]}<Schmidt>BTreelmpl.binary!5
`
`Ascii.binary!23ACDS04EFFA
`[Indigo]<Cedar>Ascii.binary23
`
`
`FIG. 19
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 20
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 20
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 19 of 24 4,558,413
`
`
`
`Cedar Modeller, started on 3-Feb-83 16:16:01 PST
`
`StoreBack Unload StopModel
`StartModelBegin Continue
`MakeModelBcd Bind
`NewModeller
`Compile Load Start
`
`
`
`ModelName:
`
`Example,Model
`
`Compiling: ExampleImplA.Mesa .... no errors.
`Compiling: ExampleImp1B.Mesa ...
`
`StarModel Example.Model
`Prasing Example.Model
`
`Analyzing Parameters
`
`eee eee eee ee ee ee ee ee
`
`eee ee ee ee ee ee ee ee ee ee
`
`
`
`
`
`
`
`
`
`Begin Example.Model
`Try for compilation:
`
`
`ExampleImp1lA.Mesa:Confirm Compilation 7? Yes
`Compilation completed, no errors.
`
`Examplelmp1B.Mesa: Confirm Compilation ? Yes
`
`
`
`
`
`A F
`
`IG. 20
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 21
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 21
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet 20 of24 4,558,413
`
`StartModel
`
`User T Files ~
`Notice Operation __
`
`
`
`User Test Program
`
`
`User Edits Files
`
`Notice Operation
`
`
` Succeeds
`
`StoreBack
`
`
`
`FIG. 21
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 22
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 22
`
`

`

`Lookup in File Type Table
`
`
`
`
`
`
`
`
`
`
`U.S. Patent Dec. 10, 1985
`
`Sheet 21 of 24 4,558,413
`
`@[Ivy]<Schmidt>X.Mesal(July 25, 1982 14:03:02)
`
`
`
`
`
`
`
`Found
`
`Not found
`
`Lookup file in Version map
`
`Not found
`
` Search [Ivy]<Schmidt> for all
`"X.Mesa"
`
`Not found
`
`Enter in version map
`
`Read File
`
`Enter
`
`in File Type Table
`
`
`
`
`FIG. 22
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 23
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 23
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 22 of24 4,558,413
`
`Look for X.Mesa of July 25, 1982 14:03:02 with
`no parameters in projection table
`
`Found
`
`Not found
`
`Generate unique id it would have = X.Bed of
`1ABCD2346DED Lookup in Version Map
`
`
`
`Not found
`
`Enumerate [Ivy]<Schmitd> looking for
`X.Bed of 1ABCD2346DED
`
`Not found
`
`Enter
`
`in version map
`
`
`
`
`
`
`
`
`
`
`
`
`
` Object file X.Bcd of 1ABCD2346DED exists
`
`Compile X.Mesa with no parameters
`
`Enter X.Bced of 1ABCD2346DED
`in projection table
`
`
`
`FIG. 23
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 24
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 24
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet 23 of24 4,558,413
`
`
`
`Load XImp1.Bcd Of 2ADEF345EDCA
`
`
`
`Lookup in Version Map
`
`
`
`
`
`
`
`Found
`
`Not found
`
`
`
` Enumerate [Ivy]<Schmidt>
`look for XImp1.Bcd OF 2ADFE245EDCA
`
`
`
`
`
`Not found
`
`Enter
`
`in Version map
`
`Read file [Ivy]<Schmidt>XImp1.Bcd!22 and load
`
`FIG. 24
`
`Release Tool: Phase Move
`
`[Iivy]<Schmidt>X.Mesal4
`
`[Indigo]<Cedar>X.Mesal2
`
`[Ivy ]<Schmidt>XImp1.Mesal6
`
`[Indigo]<Cedar>XImp1.Mesal3
`
`LIvy]<Schmidt>Y.Mesal43
`
`[Indigo]<Cedar>Y.Mesall [Ivy ]<Schmidt>YImp1.Mesal34
`
`[Indigo]<Cedar>YImp1.Mesal2
`
`FIG. 25
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 25
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 25
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 24 of 24 4,558,413
`
`Release Tool: Phase Build
`
`[ivy]<Schmidt>X.Bed!23
`
`[Indigo]<Cedar>X.Bcd!2
`
`[Ivy ]<Schmidt>XImp1.Bcd!22
`
`[Indigo}<Cedar>XImp1.8cd!1
`
`[Ivy]<Schmidt>Y.Bcd!16
`
`[Indigo]<Cedar>Y.Bed!1 [Ivy]<Schmidt>YImp1].Bcd!12
`
`[Indigo]<Cedar>YImp1.Bcd!2
`
`FIG. 26
`
`Version Map After Release
`
`File Location
`
`X.Mesa of July 26,1982 14:03:02
`
`[Indigo]<Cedar>X.Mesal2
`
`XImp}.Mesa of July 26,1982 14:06:06]
`
`[Indigo]<Cedar>XImp1].Mesal3
`
`Y.Mesa of July 25,1982 15:05:08
`
`[Indigo]<Cedar>Y.Mesali
`
`[Indigo]<Cedar>Y¥Imp1.Bcd)2
`
`YImp1.Mesa of July 25,1962 16:07:03|[Indigo]<Cedar>YImp1.Mesal2
`
`X.Bed of 1ABCD2346DED
`
`[Indigo]<Cedar>X.8cd!12
`
`XImp1.Bcd of 2ADEF345EDCA
`
`[Indigo}<Cedar>XImp1.8cd!1
`
`Y.Bcd of 3421ABD4235A
`
`[Indigo]<Cedar>Y.Bcd!1
`
`YImp}.Bcd of 23455BBDC63B
`
`FIG. 27
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 26
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 26
`
`

`

`1
`
`4,558,413
`
`SOFTWARE VERSION MANAGEMENT SYSTEM
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to software version manage-
`ment system and method for handling and maintaining
`software, e.g. software updating uniformily across the
`system, particularly in a large software development
`environment having a group of users or programmers.
`The system is also referred to as the “System Mo-
`deiler”.
`Programs consisting of a large number of modules
`need to be managed. When the number of modules
`making up a software environment and system exceeds
`some small, manageable set, a programmer cannot be
`sure that every new version of each modulein his pro-
`gram will be handled correctly. After each versionis
`created, it must be compiled and loaded.In a distributed
`computing environment,files containing the sourcetext
`of a module can be stored in many places in a distributed
`system. The programmer may haveto save it some-
`where so others may use it. Without some automatic
`tool to help, the programmercannot be sure that ver-
`sions of software being transferred to another user or
`programmerare the versions intended to be used.
`A programmer unfamiliar with the composition of
`the program is more likely to make mistakes when a
`simple change is made. Giving this new programmera
`list of the files involved is not sufficient, since he needs
`to know where they are stored and which versions are
`needed. A tool to verify a list of files, locations and
`correct versions would help to allow the program to be
`built correctly and accurately. A program can be so
`large that simply verifying a description is not suffi-
`cient, since the description of the program is so large
`that it is impractical to maintain it by hand.
`The confusion of a single programmer becomes much
`worse, and the cost of mistakes much higher, when
`many programmers collaborate on a software project.
`In multi-person projects, changes to one part ofa soft-
`ware system can have far-reaching effects. There is
`often confusion about the number of modules affected
`and howto rebuild affected pieces. For example, user-
`visible changes to heavily-used parts of an operating
`system are made very seldom and only at great cost,
`since other programs that depend on the old version of
`the operating system have to be changed to use the
`newer version. To change these programs, the “cor-
`rect” versions of each have to be found, each has to be
`modified, tested, and the new versions installed with the
`new operating system. Changes ofthis type often have
`to be made quickly because the new system may be
`useless until all components have been converted. Mem-
`bers or users of large software projects are unlikely to
`make such changes without some automatic support.
`The software management problemsfaced by a pro-
`grammer when he is developing software are made
`worse bythe size of the software, the numberofrefer-
`ences to modules that must agree in version, and the
`need for explicit file movement between computers.
`For example, a programming environment and system
`used at the Palo Alto Research Center of Xerox Corpo-
`ration at Palo Alto, Calif., called “Cedar” now has
`approximately 447,000 lines of Cedar code, and approx-
`imately 2000 source and 2000 object files. Almost all
`binary or objectfiles refer to other binary or object files
`by explicit version stamp. A program will not run until
`all references to an binary or object file refer to the
`
`25
`
`30
`
`40
`
`45
`
`50
`
`65
`
`2
`same version of that file. Cedar is too large to storeall
`Cedar software on thefile system of each programmer's
`machine, so each Cedar programmerhas to explicitly
`retrieve the versions he needs to run his system from
`remote storagefacilities or file servers.
`Thus, the problem falls in the realm of “Program-
`ming-the-Large” wherein the unit of discourses the
`software module,
`instead of “Programming-in-the-
`Small”, where units include scalorvariables, statements,
`expressions and the like. See the Article of Frank
`DeRemer and H. Kron, “Programming-in-the-Large
`versus Programming in the small”, IEEE Transactions
`on Software Engineering, Vol. 2(2), pp. 80-86, June 1976.
`To provide solutions solving these problems over-
`viewed above, consider the following:
`1. Languages are provided in which the user can
`describe his system.
`2. Tools are provided for the individual programmer
`that automate managementof versions of his programs.
`These tools are used to acquire the desired versions of
`files, automatically recompile and load aprogram, save
`new versions of software for others to use, and provide
`useful information for other program analysis tools such
`as cross-reference programs.
`3.
`In a large programming project, software is
`grouped together as a release when the versionsare all
`compatible and the programs in the release run cor-
`rectly. The languages and tools for the individual pro-
`grammer are extended to include information about
`cross-package dependencies. The release process is
`designed so production of release does not lower the
`productivity of programmers while the release is occur-
`ring.
`To accomplish the foregoing, one must identify the
`kinds of information that must be maintained to describe
`the software systems being developed. The information
`needed can be broken downinto three categories:
`1. File Information: For each version of a system, the
`versions of each file in the system must be specified.
`There must be a way oflocating a copy of each version
`in a distributed environment. Because the software is
`always changing,thefile information must be change-
`able to reflect new versions as they are created.
`2. Compilation Information: All files needed to com-
`pile the system mustbe identified. It must be possible to
`compute which files need to be translated or compiled
`or loaded and which are already in machine runnable
`format. This is called “Dependency Analysis.” The
`compilation information must also include other param-
`eters of compilation such as compiler switches or flags
`that affect the operation of the compiler whenitis run.
`3. Interface Information: In languages that require
`explicit delineation of interconnections between mod-
`ules (e.g. Mesa, Ada), there must be means to express
`these interconnections.
`There has beenlittle research in version control and
`automatic software management. Ofthat, almost none
`has built on other research in the field. Despite good
`reasons forit, e.g. the many differences between pro-
`gram environments, and the fact
`that programming
`environments ususally emphasize one or two program-
`ming languages, so the management systems available
`are often closely related to those programming lan-
`guages, this fact reinforces the singularity of this re-
`search. The followingis brief review of previous work
`in this area.
`(1) Make Program
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 27
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 27
`
`

`

`3
`The Make program,discussed in the Article of Stuart
`J. Feldman, “Make-A Program for Maintaining Com-
`puter Programs”, Software Practice & Experience, Vol. 9
`(4), April, 1979, uses a system description called the
`Makefile, which lists an acyclic dependency graph ex-
`plicitly given by the programmer. For each nodein the
`dependency graph, the Makefile contains a Make Rule,
`whichis to be executed to produce a new version of the
`parent nodeif any of the son nodes change.
`For example the dependency graph illustrated in
`FIG. 1 shows that xl.o depends on xl.c, and the file
`a.out depends on x1.o and x2.0. The Makefile that rep-
`resents this graph is shown in Table I below.
`TABLEI
`xl.o
`ec
`alec
`cc
`a2.
`52.0:
`
`—ccc x2.c
`
`a.out:
`
`x10:
`
`x2.0
`x2.0
`
`xhe
`
`slo
`xlo
`
`—c
`
`
`
`In Table I, the expression, “‘cc-c xl.c” is the com-
`mand to execute and produce a new version of xl.o
`when xl.c is changed. Make decides to execute the
`make rule i.e., compile xI.c, if the file modification time
`of xl.c is newer than thatof x1.o.
`Thedescription mechanism shownin Table I is intu-
`itively easy to use and explain. The simple notion of
`dependency, e.g., a file xl.o, that depends on x1.c must
`be recompiled if x1.c is newer, works correctly vitually
`all the time. The Makefile can also be used as a place to
`keep useful commands the programmer might want to
`execute, ¢.g.,
`print:
`pr xl.c x2.c
`defines a name “print” that depends on no other files
`(names). The command “make print” will print
`the
`source files xl.c and x2.c. There is usually only one
`Makefile per directory, and, by convention, the soft-
`warein that directory is described by the Makefile. This
`makes it easy to examine unfamiliar directories simply
`by reading the Makefile.
`Makeis an extremely fast and versatile tool that has
`become very popular among UNIX users. Unfortu-
`nately, Make uses modification times from thefile sys-
`tem to tell which files need to be re-made. These times
`are easily changed by accident and are a very crude
`way ofestablishing consistency. Often the programmer
`omits some of the dependencies in the dependency
`graph, sometimes by choice. Thus, even if Make em-
`ployed a better algorithm to determine the consistency
`of a system, the Makefile could still omit many impor-
`tant files of a system.
`(2) Source Code Control System (SCCS)
`The Source Code Control System (SCCS) manages
`versions of C source programs enforcing a check-in and
`check-out regimen, controlling access to versions of
`programs being changed. For a description of such
`systems, see the Articles of Alan L. Glasser, “The Evo-
`lution of a Source Code Control System”, Proc. Soft-
`ware Quality & Assurance Workshop, Software Engi-
`neering Notes, Vol. 3(5), pp. 122-125, November 1978;
`EvanL. Ivie, “The Programmer’s Workbench-A Ma-
`chine for Software Development”, Communications of
`the ACM, Vol. 20(10) pp. 746-753, October, 1977; and
`Marc J. Rochkind ‘The Source Code Control System”,
`
`4,558,413
`
`4
`IEEE Transactions on Software Engineering, Vol. 1(4),
`pp. 25-34, April 1981.
`A programmer who wants to change a file under
`SCCS control does so by (1) gaining exclusive access to
`the file by issuing a “get” command, (2) making his
`changes, and (3) saving his changed version as part of
`the SCCS-controlled file by issuing a “delta” command.
`His changes are called a “delta” and are identified by a
`release and level number,e.g., 2.3". Subsequent users
`of this file can obtain a version with or without the
`changes made as part of “delta 2.3". While the program-
`mer has “checked-out”the file, no other programmers
`may store new deltas. Other programmers may obtain
`copies ofthe file for reading, however. SCCS requires
`that there be only one modification ofa file at a time.
`There is much evidence this is a useful restriction in
`multi-person projects. See Glasser, Supra. SCCS stores
`all versions of a file in a special file that has a name
`prefixed by “s.”. This ‘‘s.” file represents these deltas as
`insertions, modifications, and deletions of lines in the
`file. Their representation allows the “get” commandto
`be very fast.
`(3) Software Manufacturing Facility (SMF)
`Make and SCCSwere unified in special tools