Dec. 10, 1985
`Schmidt et at.
`[45] Date of Patent:
`
`[19]
`
`[11] Patent Number:
`
`4,558,413
`
`[54] SOFTWARE VERSION MANAGEMENT
`SYSTEM
`
`[75]
`
`Inventors: Eric E. Schmidt, Loa Altos, Calif.;
`Butler W. Lampaon. Philadelphia. Pa.
`
`[T3] Assignee: Xerox Corporation. Stamford. Conn.
`[21] App]. No.: 553,724
`
`[22] Filed:
`
`Nov. 2!, 1983
`
`Int. CL‘
`......... .. GM]? 15/20
`[51]
`1.1.5. CL ............. ..
`. 364/300; 364/203
`[52]
`[58] Field of Search ....................................... .. 364/300
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4.309.756
`
`12‘1982 Beckler ............................. .. 364/300
`
`OTHER PUBLICATIONS
`
`Morse et al.. DOS/AMAP Model of the DOS Control
`Program. LBJ". Technical Doctorow Bulletin. vol. 14,
`No. 3. Aug. 1971. pp. 352—353.
`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 8: Steven Popovich, “The
`Second Compendium of Gandall Documentation”
`CMU Department of Camputer Science, May 24, I932.
`Gail E. Kaiser & A. Nico Habennann. "An Environ-
`ment for System Version Control" in The Second Com-
`pendium ofGandalf Documentation. CMU Department
`of Computer Science. Feb. 4, 1982.
`B. W. Lampson et al., “Practical Use of a Polymorhic
`Applicative Language". Proceedings of the l0th 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. 1932.
`
` United States Patent
`
`Dissertation of Eric Emerson Schmidt. entitled “Con-
`trolling Large Software Development in a Distributed
`Environment". approved Nov. 1982.
`Xerox Palo Alto Research Centers Publication, CSL—S-
`2-7. dated Dec. I932, "Controlling Large .
`.
`. Environ-
`ment“. Schmidt.
`Ira P. Goldstein d: Daniel G. Bobrow. “A Layered
`Approach to Software Design,“ Xerox Pare. Tech.
`Report. CSL—SO—S, Dec. I980.
`James G. Mitchell et al.. “Mesa Language Manual.
`Version 5.0" Xerox Faro. Tech. Report. CSL—79—3.
`Apr. 1979.
`
`{List continued on next page.)
`
`Primary Examiner—Raulfe B. Zache
`Attorney. Agent. or Firm—W. Douglas Carothers. J r.
`
`ABSTRACT
`[57]
`A software version management system. also called
`system modeller. provides for automatically collecting
`and recompiling updated versiOns of component soft-
`ware objects comprising a software program for opera-
`tion on a plurality of personal computers coupled to-
`gether in a distributed software environment via 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 compoaent
`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.
`Each of the models is representative of the scurce ver-
`sions of a particular component software object and
`contain object pointers including a unique name of the
`object. a unique identifier descriptive of the cronologi-
`cal updating of its current version, informatiori 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 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 1
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`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.
`Am Avakian, Sam Haradhvala. Julian Horn & Bruce
`Knobe, “The Design of an Integrated Support Sofiware
`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. PhD Thesis. CMU Computer Sci-
`ence Department. CMU—CS—79—l l6. 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. I980.
`A. Demers &. J. Donoahue. “Data Types. Parameters.
`and Type Checking”. Proceedings of the Seventh Sym-
`positun on Principles of Programming Languages. Las
`Vegas, Nevada. pp. 12-23. 1980.
`Frank DeRemer St H. Kron. “Programming-in—
`the-Large Versus Mgmming-in-th&5mall", IEEE
`Transactions on Software Engineering. vol. 2. No. 2.
`pp. 30-86. Jun. 1976.
`Stuart 1. Feldman, “Make—A Program for Maintaining
`Computer Programs“. Software Practice and Experi-
`ence. vol. 9. No. 4, pp. 255—256. Apr. 1979.
`[re P. Goldstein & Daniel G. Bobrow. “Descriptions
`for a Programming Environment". Proceedings of the
`
`First Annual Conference of the NatiOnal Association of
`Artificial Intelligence. Stanford, California. Aug. 1930.
`Eric Harslem and LeRoy E. Nelson. “A Retrospective
`on the Development of Star”, Proceedings of the 6th
`International Conference on Software Engineering,
`Tokyo. Japan. Sep. 1932.
`Thomas R. Horsley 3: 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. 1917.
`Hugh C. Latter & Edwin H. Satterthwaite. “The [m-
`pact of Mesa on System Design". Proceedings of the
`4th International Conference on Software Engineering.
`pp. 174—132, 1979.
`D. Redell. Y. Dalai, 'I‘. Horsley. H. Lauer. W. Lynch.
`P. Moiones. H. Murray & S. Purcell. “Pilot: An Operat-
`ing System for a Personal Computer“. Proceedings of
`the Seventh Symposium on Operating System Princi-
`plea, Dec. 1919.
`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
`C0mputer Science Department. CMU-CS-SO— l 20. Jan.
`1980.
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 2
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 2
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet! on4
`
`4,558,413
`
`
`
`PRIOR
`
`ART
`
`1
`
`no.3]
`
`30.81
`
`3.51
`
`b.51
`
`Makaf119
`
`4.?
`
`11.51
`
`
`
`
`O x
`
`1.2
`
` x1.
`x2.o
`
`
`1.c
`3.5
`x2.c
`
`Makefile 3.5
`Makefi'le
`
`PRIOR ART
`
`FIG. 2
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 3
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 3
`
`

`

`US. Patent Dec. 10,1985
`
`Shoet2of24
`
`4,558,413
`
`
`
`Other modules and boxes
`
`Other modules and boxes
`
`
`
` Compos1t'ion C1
`Version Zfstd)
`
` Other modules
`
`
`
`PRIOR
`
`ART
`
`FIG. 3
`
`Configuration Object F'i'la
`
`H HL—y
`
`Source F119
`
`Implementat1on Object F1135
`
`Source F119
`
`Object fnes for Interfaces
`
`FIG. 6
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 4
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`

`

`U.S. Patent Dec.10,1985
`
`Sheet30f24
`
`4,558,413
`
`C1ient:PRUGRAH IMPORTS SqrtInt =
`
`
`
`Imp'lemantor:
`
`PROGRAM EXPORTS SqrtInt ={
`
`{
`
`
`
`
`
`
`
`Sqrt: PUBLIC PRDC[s: HEAL]RETURN[REAL]={
`
`..coda to compute sqrt of a number
`
`}:
`
`Sqr‘tInt:DEFINITIONS I {
`
`
`
`f:l(3.
`
`n4
`
`
`
`Sqrt: PROCEREAL]RETURHS[REAL]:
`
`}.
`
`Impa1amentntion object f11e
`
`.fi
`
`Source H10
`
`Object H193 for intarfacas
`
`f:!C3.
`
`£5
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page5
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet4of24
`
`4,558,413
`
`Storage
`Disk
`
`Persona1
`
`
`
`
`
`
`
`Computer
`
`
`
`To other networks
`
`FIG. 7
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page6
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 5 of 24
`
`4,558,413
`
`Users make changes while
`running on re1eased software
`
`Re1ease Master sends
`ca11 for subm1ssions
`
`DF f11es in boot fiie
`
`are a31 announced as ready
`
`Boot f1le for new
`
`re1ease is prepared
`
`Remaining DF Files are
`a11 announced as ready
`
`Re1easa Hester prepares
`top-1eve1 DF f11e
`
`
`
`
`
`Phases One and Two
`are run at 1east once
`
`Phase Three is run
`
`ReIease Hester announces
`
`reiaase 1s comp1ete
`
`
`Users make changes to
`their software 1n response
`
`to errors reported by
`
`Phases One and Two
`
`
`FIG. 8
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page?
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 7
`
`

`

`
`
`US. Patent Dec. 10,1985
`
`Sheet6of24
`
`4,558,413
`
`Fi1eToo1.DF
`
`UserExec.DF BBV.DF
`
`LN
`
`BugBane.DF
`
`
`
`TTYID.DF
`
`l
`
`ViewersAndTioga.DF
`
`fi
`
`PricrityQuene.DF
`
`
`
`L__________;
`I
`C°1°FPaCk39°-DF 0n11neMergeSort.DF
`w a
`
`CedarCOntro1.DF
`VF___I
`Specia1Br1ngOver.DF
`
`MesaScanner.DF
`
`Graphics‘DF
`
`Inscript,np
`
`R1991n9Makar.DF
`
`Runtime.DF. 10.0F. Wor1dVH.DF.
`ListsAndAtoms.DF. CIFS.DF
`
`DateAndTime.DF
`
`
`
`RPCRuntime.DF
`¢
`GrapevinaUser.DF CedarSnapshot.DF
`
`l
`
`R1gg1ng_DF
`
`l
`
`Loader.DF
`
`CedarReaIs.DF Bus1cHaads'.DF
`
`CFU.DF
`
`FTP.DF
`
`'
`
`Bed-0F
`
`|
`
`
`
`Pine.DF
`
`
`
`Compat1b11ityPackaga.DF
`
`f_I
`
`Tormiaa]Mult1p1as.DF
`
`Random.DF
`
`Pup.DF
`
`|
`
`Commun1fat1on'.DF
`
`P11otInterfaces.DF
`
`FIG. 9
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Pages
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 8
`
`

`

`US. Patent Dec. 10, 1985
`
`Sheet7of24
`
`4,558,413
`
`
`
`IO.DF. wor1d.DF. VersionMap.DF,
`Runtime.DF.
`L1stsAndAtoms.DF. CIFS.DF
`
`
`
`stands for
`
`hi
`
`
`
`
`
`Runt1ma.DF*—-—->-Hor1dVM.DF
`
`CIFS.DF
`
`10-”
`;
`
`L'i stsAndAtoms . 0F
`
`i
`
`VisionHap.DF
`
`FIG. 10
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page9
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 9
`
`

`

`
`
`U. S. Patent Dec. 10,1935
`
`Sheet8 of24
`
`4,558,413
`
`TTYIO.DF
`
`F11eToo1.0F
`
`BBV.DF
`
`gm;
`
`V1ewersAndTioga.DF
`+
`TIP.DF
`
`Co]or1ackage.DF|
`
`UserExec.OF
`
`Lea
`
`Graphics.DF
`
`IO.DF
`
`BugBane.DF
`
`
`
`
`Pine.DF
`
`ListsAndAtoms.DF
`
`
`Inscript.DF
`
`Runtime.DF-—Hor1dVM.D
`
`
`
`
` Vis1onHap.DF
`HesaScanner.D'
`
`Loader.DF
`
`RPCRuntime.DF
`+
`Grapev1neUsar.DF
`
`SpaciaIBring
`0ver.DF
`
`Rigging.DF
`
`FTP.DF
`
`Cedar
`Bcd.DF Contro1.DF
`
`l W
`
`P
`Com at1b111tyPackaga.DF
`
`PriorityOuaua.DF
`
`Commun1cat1on'.DF
`
`Term1naIHu1t1p19x.DF
`
`
`
`
`
`
`CodarReaIs.DF
`
`DataAndTime.DF
`
`BTreas.DF
`
`CadarSnapshot.DF
`Basicfiaads'.DF
`
`
`
`FIG. 11
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page10
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 10
`
`

`

`US. Patent Dec.10,1985
`
`Sheet90f24
`
`4,558,413
`
`Vis1chapBu11der.DF
`
`Chat.DF
`
`UECP.DF
`
`CIFSCummands.DF
`
`
`
`
`
`Sequ'injFi—HIFSFHeJF
`
`I
`
`4F—"Mode1ler.DF
`
`DFFiles.DF
`
`Comp11er.DF
`
`Boot
`
`F113
`
`Binder.DF
`
`Lister.DF
`
`Packager.DF
`PGS.DF
`
`PressPackagB.DF '4— Print.DF
`PerfStats.DF <— CadarDB.DF
`
`CoFork.DF 4-—-————-P1otPackage.DF
`
`Spy.DF'4-‘-—-————*Lupine.DF
`SirPress.DF *——'PrassScraen.df
`
`BrovoToT1oga.DF
`CedarRaalTest.DF
`
`Inc1udeChecker.DF
`
`Haintain.DF
`
`MakeBoat.DF
`
`HCross.DF
`
`0the11o'.DF '
`
`PupHatch.DF
`
`RedBTackTreeRaf.DF
`
`Set,DF
`
`STPServar.DF
`
`TJnmGraphics.DF
`
`Unique.DF
`waInutSand.DF
`
`RedBIack
`Tree.DF
`
`"atBrLily.nF
`
`I=!(3. 1:?
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page11
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 11
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet 100m 4,558,413
`
`C1ient1mp1.Hesa
`
`
`
`
`C1ientmp1zPRDGRAM IMPORTS Sort={
`
`TastTham:PROC[I:LIST 0F Dbject]={
`
`~~ca11 USortList with this list
`
`I#Sort.USortL1st[I.Compareobjact];
`
`DIRECTORY
`
`Sort:
`
`
`
`}: Sort.Mesa
`
`
`
`}:
`
`
`
`ComparaObject:PROC[n.b:0bjact]
` RETURNSEComparisOn]-{
`
`
`--compares the two objects
`
`
`
`--raturns less. equa1. or greater
`
`Sort:DEFINITIOHS-{
`
`0bject:TYPE-RECORD[
`
`x.y:INT
`
`]:
`
`USortL1st:PRDC[LIST 0F Object. CompareProc]
`
`RETURNS[LIST 0F Object]:
`
`FIG. 13A
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page12
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 12
`
`

`

`US. Patent Dec. 10,1985
`
`Sheetllof24 4,558,413
`
`SortImp1.Mesa
`
`DIRECTORY
`
`Sort:
`
`SortImp‘l :PRDGRAM EXPORTS Sort-{I
`
`};
`
`
`
`USortList:PROC[I:LIST 0F Object.
`
`compareProc: ComparePruc]
`
`RETURNS[newI:LIST 0F Object]-{
`
`"code to sort the Hat I.
`
`e1‘im1nat1ng dupHcates
`
`T0 FIG. 13A
`
`FIG. 13B
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page13
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 13
`
`

`

`US. Patent Dec. 10, 1935
`
`Sheet120f24 4,558,413
`
`SortCoord.Mesa
`
`Sort:DEFINITIONS={
`
`0bject:TYPE=RECORD[
`
`x.y:INT
`
`]:
`
`USortList:PROC[LI5T 0F Object. CompareProc]
`
`SortNames.Masa
`
`Sort:DEFINITIONS*{
`
`0bject:TYPE-RECORD{
`
`1:5TRIHG
`
`]:
`
`RETURNSELIST 0F Object]:
`
`RETURNS[LIST OF Object]:
`
`
`
`USurtList:PROC[LIST 0F Object. CompareProc]
`
`FIG. 14
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page14
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 14
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet13 of24 4,558,413
`
`SertQuickImp1.Masa
`
`DIRECTORY
`
`Sort:
`
`SortQuickImp1:PROGRAH EXPORTS Sort={
`
`USortList:PUBLIC PROC[I:LIST 0F Object.
`
`comparePro¢zCumpareProcj
`
`RETURNSCnewI:LIST 0F Object]-{
`
`--code to sort the list I. eIiminating dup11cates
`
`--use QuickSort
`
`SortHeapImp1.Masa
`
`
`
`}:
`}:
`
`DIRECTORY
`
`Sort;
`
`SortHaapImp1:PROGRAH EXPORTS Sort-{
`
`USortListtPUBLIC PROC[I:LIST 0F Object.
`
`comparaProc:CompareProc]
`
`RETURNSEnewI:LISI OF Dbjact]={
`
`--code to sort the list I. e11m1nat1ng dup11cates
`
`--use HeapSort
`
`FIG. 15A
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page15
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 15
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet14 on4 4,558,413
`
`Clientlmp1.Masa
`
`DIRECTORY
`
`Sort:
`
`C1ient1mp1:IMPORTS SortQuickInst:Sort.SurtHeapInst:Sort=
`
`TestThem:PROC[I:LIST 0F Object}={
`
`--ca]1 USOftLiSt with this 11$t.
`
`try QuickSort
`
`newI+SortQu1cklnst.USortList[I.CompareObject]:
`
`---now try HaapSort
`
`}:
`
`
`
`newl+$ortHeapInst.USortListEI.CompareObject]:
`
`}:
`
`CompareObject:PROC[a.b:0bject]
`
`RETURHSECompar1son]-{
`
`--compares the two objects
`--returns 1955. equal. or greater
`
`FIG. 15B
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page16
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 16
`
`

`

`
`
`US. Patent Dec. 10,1985
`
`Sheet150f24 4,558,413
`
`ClientImp1.Hesa
`
`DIRECTORY
`
`SortCoord:INTERFfiCE Sort.
`
`SortNamesxlflTERFACE Sort:
`
`C1ientImpI:PROGRAH IMPORTS SortQuickCooruInst:SortCoord.
`
`SartQuickNamesInst:SortNames.SortHeapCoordInst:SortCoord.
`
`SartHeapNamesInst={
`
`--compares a and b. returns 1ess. equal. or greater
`
`TestThem:PROC[Il:LIST 0F SortCaord.Dbject.IZ:LIST 0F SartNames.0bject]=
`
`newI-SortQuickCoordInst.USortList[11. CompareCoordinataObjects];
`
`newI-SortHeapCoordInst.USurtList[11. CompareCanrdinateObjects]:
`
`nauI~SortQuickNameslnst.USortListhZ. CompereNamaObjects].
`
`newI~SortHeapNamesInst.USortListEIZ. CompereNamesObjects]:
`
`CompareCoordinateObjects:PRDC[a.b:?sgrtCoord.Object]RETURNS{Compar1son]={
`
`--compares a and b. returns 1e55, equa1. or greater
`
`}:
`
`CompereNameObjects:PRDC[a.b:SortNames.0bject]RETURN5[Comparison]={
`
`FIG. 16
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 17
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 17
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet 16 on4 4,558,413
`
`Btreemodenwan14,1983.14:44:11}
`
`LET®I|ndigaj<Cedar}Ced-armsraces.nrodef!iJuiy 25. 1932. 14:03:033IN
`
`BTmeflNTEFIFACE BTree-@[Ivy]<Schmidt>BTree.cedar![Sept9.1982.18:52:55}
`
`[Ascif].
`
`BTreeJnsr: BTree~@[Ivy](Schrnid1>BTree1msJ.cedarltJan 14. 1933.14:44:09}
`
`'[][1nsrances.fiopa InstancesJO. msmncesfipacel] ]
`
`Cedarlnterfacesmodelwuly, 25. 1982.14:03:03)
`
`I
`
`Asca‘i:iNTERFACE-@IIndigokCedarMscii.cedarEEJuly 10.1982. 1225:0010
`
`Hope:INTEFIFACE-@E1ndigo]<Cedar>Rope.cedarttJuly 1U. 1932J?:00100)‘[].
`
`10:INTEFIFACE~@[1ndigo](Cedar)IO.cedarluuly12.1982.11:00:00]'[].
`
`SpaceflNTEHFACE~@[1ndigo}<Cedar>Space.CedarI-{June 10. 1932. 3:35:00)' []]
`
`LETlnsran:es~@[lndigo](Cedar)CedarInstandesmodeflwuly 25. 1982. 14'10:12)|N
`
`
`
`Cedarlnstancesmodel!{Ju|y 25,1982.14:10112)
`
`[115ch Hope. :0. Space]-
`
`LET@Cedanmerfac e.modei![Ju!y 25. 1932. 14:03:03] IN [
`
`@{lndigo]<Cedar)Asch‘ImpLcedar!(JuIy10.1982.12:30:00}[][].
`
`@findigo}<Ceda'l)Hopelmpf.cedalltJuly10.1982.1T:10:2£}'{]' [].
`
`@{Indigo](Cedat)101mp!.cedarl[July 20. 1982. 13:03:03)’[]'[].
`
`@[lndigokCEzdaDSpacac edarfidune 11,1932. 15:00:00] '[l '[]]
`
`FIG. 17
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 18
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 18
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 17 on4 4,558,413
`
`Objecttype table
`
`Source 0019c!
`Type
`
`
`BTreeCedarEtSept 9. 1982. 13:52:55]
`
`[lNTEHFACEAscaJ- [INTERFACES Tree]
`
`BTreermpl.ceder!lJan 9. 1983‘ 14:44:09)
`
`[Rope-.INTERFACERODE. FO,Space:INTEFIFACE Space-1
`
`BTree:tNTERFACEBTree]
`
`[[Ropelnstrfiope. JO. Spacemsrfipace] {arreeinst
`arreen
`
`
`
`Space. b1nary!8348823FF?61.
`BTree.ba‘nary143956A3C32FU]
`
`
`Projection table
`
`
`
`Source object
`Parameter values
`Results object
`
`
`BTree.cedar![Sept9.l982.
`13:52:55)
`
`[145chbinaryl23ACD904EFFA]
`
`BTree.binaryE43956A3C32F0
`
`Brreeu‘mpmedariuan 14. 1983.
`14:44:09)
`
`[F1ope.bu‘nary!AC9023E76FA6.
`10.bmary!23843396A24f.
`
`BTreeimprinaryEZMSFFDZBSC
`
`FIG. 18
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 19
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 19
`
`

`

`US. Patent Dec. 10, 1985
`
`Sheet180f24 4,558,413
`
`Version map
`
`
`
`Object name
`File location
`
`
`Ascii.binary!23ACDQO4EFFA
`[lndigo]<Cedar>AscEi.binary23
`
`
`
`
`8Tree.cedar![8ept 9. 1982. 13:52:55}
`
`[Ivy](Schmidt>BTree.cedar4
`
`BTreeJmchedar!(Jan 14,1983. 14:44:09}
`
`[ivy](SchmidDBTree|rnpl.cedar!9
`
`BTree.binary!43956A3C32F0
`
`[ivy}<Schmidt>BTree.binary!2
`
`BTreelmpLbinary!2045FF0283C
`
`[Ivy](SchmidDBTreelrnpl.binaryIS
`
`FIG. 19
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 20
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 20
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 19 on4 4,558,413
`
`
`
`Cedar Mode11er. started on 3—Feb-83 16:16:01 PST
`
`StoreBack Unioad Stophlode1
`Startflode'fiBegin Continue
`MakeHodech Bind
`NewModeHer
`
`Compi1e Load Start
`
`Modelflame:
`
`Examplo.Hodai
`
`no errors.
`
`Compiling: Examplelmp1A.Mese
`Compi‘ling: ExamplelmpTB.Mesa
`
`
`StarModo‘t Examp‘lo.Mode1
`Prasing Examp1o.Hode1
`Ane1yzing Parameters
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`q a o u q - - - _ _ _ _ _ _ _ _ - _ _ __
`
`- — u — a u — u p _ _ _ __-_—___--
`
`Begin Examp1e.Moda1
`Try for compilation:
`Examp1eImp1A.Hesa:Confirm Compflation ? Yes
`Compilation completed. no errors.
`ExamplelmpIB.Hesa: Confirm Compi'lation 1‘ Yes
`
`
`
`
`
`
`
`
`
`FIG. 20
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 21
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 21
`
`

`

`
`
`U. S. Patent
`
`Dec. 10, 1985
`
`Sheet 20 of24 4,558,413
`
`StartMode1
`
`User Eéfts Fi1e5'4--]
`
`
`
`Not1ce Operation
`
`
`
`
`
`l
`
`
`User Test Program
`
`l
`
`User Edits F1195
`
`Notice Operation
`
` Succeeds
` Continue
`
` StoreBack
`
`FIG. 2 1
`
`
`StopModa'l
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page22
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 22
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet210f24 4,558,413
`
`
`
`@[Ivy]<5¢hmidt)x.flesal(July 25. 1982 14:03:02}
`
`
`
`
`
`
`
`Lnokup in F119 Type Tab1e
`
`
`
`Found
`
`Not found
`
`Lookup f11e in Version map
`
`Not found
`
` Search [Ivy]<8chm1dt> for a11 "X.Mesa"
`
`Not found
`
`
`
`
`
`
`
`
`Enter in version map
`
`
`
`Read F113
`
`
`
`
`Enter 1n F113 Type Tab1e
`
`FIG. 22
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page23
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 23
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 22 on4 4,558,413
`
`Look for X.Mesa of Juiy 25. 1932 14:03:02 with
`no parameters in projection table
`
`
`
`
`
`
`
`Found
`
`Not found
`
`Generate unique id it wou1d have = X.Bcd of
`1ABC023460£D Lookup in Version Map
`
`Not found
`
`
`
`Enumerate [Ivy]<Schmitd> 1ooking for
`X.Bcd of 1ABCDZS460ED
`
`Not found
`
`Enter
`
`in version map
`
`Compi1e X.Hosa with no parameters
`
`
`
`
`
`
`
`
`
`Enter X.Bcd of IABCDZE4SDED
`
`in projection tah1e
`
`
` Object fi1e X.Bcd of 1ABCD234GDED exists
`
`
`
`FIG. 23
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page24
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 24
`
`

`

`US. Patent Dec. 10,1935
`
`Sheet 23 on4 4,558,413
`
`
`
`Load XImp1.Bcd 0f 2ADEF345EDCA
`
`
`
`
`
`Lookup in Version Map
`
`
`
`Found
`
`Not found
`
`
`
` Enumerate [Ivy]<5chmidt>
`100k for XImpl.Bcd 0F ZADFE245EDCA
`
`Not found
`
`
`
`[Ind1go](Cedar>Y.Hasar1 [Ivy]<5chm1dt>YImp1.Mesal34
`
`
`
`Enter
`
`in Version map
`
`
`
`
`
`
`Read f11e [Ivy]<Schm1dt>XImp1.Bcdlzz and 103d
`
`
`
`FIG. 24
`
`ReIease T001: Phase Hove
`
`[Ivy]<5chmiat)x.nesal4
`
`[Indigo]<tedar>x.flasalz
`
`[Ivy]<$chmidt>XImp1.Mesalfi
`
`[Indigo]<Cedar>XImp1.Mesala
`
`[Ivy]<5chmidt>¥.flesal43
`
`[Indigo]<Cedar>YImp1.Mesalz
`
`FIG. 25
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page25
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 25
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 24 of24 4,558,413
`
`Re1ease T001: Phase Buiid
`
`[Ivy]<5chmidt)x.3cd[23
`
`[Indigo]<0edar>X.BchZ
`
`[Ivy}(Schmidt>lep1.Bcd!22
`
`[Indigo]<Cedar>XImp1.Bcdll
`
`[Ivy]<$chmidt>Y.Bcd116
`
`[Indigo]<Cedar>Y.Bchl [Ivy]<5chmidt)YImp1.Bcdllz
`
`
`
`[Ind1go]<Cedar)YImp1.Bcdlz
`
`[Indign](Cedar>YImp1.Bcdlz
`
`FIG. 26
`
`Version Map After Release
`
`File Location
`
`X.Mesa of JuTy 25.1982 14:03:02
`
`[Indigo]<Cedar>X.Mesal2
`
`XImp'l.Hasa of Ju'Iy 25.1982 14:05:06 [Indigo]<Cedar>XImp1.Mesa13
`
`Y.Masa of July 25.1982 15:06:08
`
`[Indigo]<Cedar>Y.Hesa11
`
`YImp1.Mesa of Ju'lyI 25.1962 16:07:03
`
`[Indigo]<Cedar‘>YImp1.Mesalz
`
`X.Bcd of IABCDZ346DED
`
`[Indigo]<Cedar>x.Bcd!2
`
`XImp1.Bcd of ZAD£F345EDCA
`
`[Indigo]<Cedar>XImp1.Bcdll
`
`Y.Bcd 0f 3421ABD4235A
`
`[Ind1go]<Cedar‘>Y.Bcdl1
`
`YImp1.Bcd of 234553000638
`
`FIG. 27
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page26
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 26
`
`

`

`
`
`1
`
`4,558,413
`
`SOFTWARE VERSION WAGMNT 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 uniformin 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-
`deller".
`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 module in his pro-
`gram will be handled correctly. After each version is
`created, it must be compiled and loaded. In a distributed
`computing environment. files containing the source text
`of a module can be stored in many places in a distributed
`system. The programmer may have to save it some-
`where so others may use it. Without some automatic
`tool to help. the programmer cannot be sure that ver-
`sions of software being transferred to another user or
`programmer are 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 programmer a
`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 suff-
`cient, since the description of the program is so large
`that it is impractical to maintain it by hand.
`The confusion ofa 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 of a soft-
`ware system can have far-reaching effects. There is
`often confusion about the number of modules affected
`and how to 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 of this type often have
`to be made quickly because the new system may be
`useless until all components have been convened. Mem-
`bers or users of large software projects are unlikely to
`make such changes without some automatic support.
`The software management problems faced by a pro-
`grammer when he is developing software are made
`worse by the size of the software, the number of refer-
`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 441,000 lines of Cedar code. and approx-
`imately 2030 source and 2000 object files. Almost all
`binary or object files 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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`35
`
`45
`
`50
`
`55
`
`65
`
`2
`same version of that file. Cedar is too large to store all
`Cedar software on the file system of each programmer‘s
`machine. so each Cedar programmer has to explicitly
`retrieve the versions he needs to run his system from
`remote storage facilities or file servers.
`Thus, the problem falls in the realm of "Program-
`ming-the-Large" wherein the unit of discourses the
`sofiware module.
`instead of “Programming-in-the-
`Small", where units include scalor variables. statements.
`expressions and the like. See the Article of Frank
`DeRerner and H. Kron, “Programming-in-the-Large
`versus Programming in the small". IEEE Transactions
`on Sojhvare 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 management of 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 informatiou 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 versions are all
`compatible and the programs in the release run cor-
`rectly. The languages and tools for the individual pro-
`grammer are extended to include informatiou 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 down into 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 of locating a copy of each version
`in a distributed environment. Because the software is
`always changing. the file information must be change-
`able to reflect new versions m they are created.
`2. Compilation Information: All files needed to com-
`pile the system must be 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 when it is run.
`3. interface Information: In languages that require
`explicit delineation of interconnections between mod-
`ules (e.g. Mesa. Ada}. there must he means to express
`these interconnections.
`There has been little research in version control and
`automatic software management. or that, almost none
`has built on other research in the field. Despite good
`reasons for it. 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 following is brief review of previous work
`in this area.
`
`[1} Make Program
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 27
`
`
`
`PMC Exhibit 2121
`Apple v. PMC
`IPR2016-01520
`Page 27
`
`

`

`4,558,413
`
`5
`
`10
`
`.5
`
`20
`
`25
`
`35
`
`4-0
`
`45
`
`55
`
`65
`
`4
`IEEE Transactions on Software Engineering, Vol. 1(4),
`pp. 25-34, April 198].
`A programmer who wants to change a file under
`SCCS control does so by (l) 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-on ” the file. no other programmers
`may store new deltas. Other programmers may obtain
`copies of the file for reading, however. SCCS requires
`that there be only one modification of a 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 "5." file represents these deltas as
`insertions, modifications, and deletions of lines in the
`file. Their representation allows the “get” command to
`be very fast.
`(3) Software Manufacturing Facility (SMF)
`Make and SCCS were unified in special tools for a
`development project at Bell Labs called the Software
`Manufacturing Facility {Shall-7) and discussed in the
`Article of Eugene Cristofer, F. A. Wendt and B. C.
`Wonsiewicz, "Source Control & Tools=Stable Sys-
`tems”, Proceedings of the Fourth Computer Softwre &
`Applications Conference. pp. 527-532. Oct. 29—31., I980.
`The SMF uses Make and SCCS augmented by special
`files called slists. which list desired versions of files by
`their SCCS version number.
`A slist may refer to other slists as well as files. In the
`SMF, a system coasists of a master slist and references
`to a set of slists that describe subsystems. Each subsys-
`tem may in turn describe other subsystems or files that
`are part of the system. The SMF introduces the notion
`of a consistent software system: only One version of a
`file can be present in all slists that are part of the system.
`Part of the process of building a system is checking the
`consistency.
`SMF also requires that each slist refer to at least one
`Makefile. Building a system involves (l) obtaining the
`SCCS versions of each file, as described in each slists.
`(2) performing the consistency check. (3) running the
`Make program on the version of the Makefile listed in
`the slist, and (4) moving files from this slist to an appro-
`priate directory. FIG. 2 shows an example of a hierar-
`chy of slists, where ab.sl is the master slist.
`SMF includes a database of standard versions for
`common files such as the system library. Use of SMF
`solves the problem created when more than one pro-
`grammer is making changes to the sofiware of a system
`and no one knOws exactly which files are included in
`the currently executing systems.
`(4} PIE Project
`The PIE project is an extension to Smalltalk devel—
`oped at the Palo Alto Research Center of Xerox Cpl-po-
`ratiOn and set forth in the Articles of Ira P. Goldstein
`and Daniel G. Bobrow. “A Layered Approach to Soft-
`ware Design". Xerox PARC Technical Report CSL-SO—S.
`December 1980; Ira P. Goldstein and Daniel G. Bo-
`brow, "Descriptions for a Programming Environment".
`Proceedings of the First Annual Conference of the Na-
`tional Association of Artificial Intelligence. Stanford.
`Califl, August 1980; Ira P. Goldstein and Daniel G.
`Bobrow, “Representing Design Alternatives”, Proceed-
`
`
`
`PMC Exhibit 2121
`
`Apple v. PMC
`|PR2016-01520
`
`Page 28
`
`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 xl.c, if the file modification time
`ofxlc is newer than that of xl.o.
`The description mechanism shown in Table I is intu-
`itively easy to use and explain. The si