United States Patent
`
`[19]
`
`[11] Patent Number:
`
`4,558,413
`
`Dec. 10, 1985
`Schmidt et al.
`[45] Date of Patent:
`
`[54] SOFTWARE VERSION MANAGEMENT
`SYSTEM
`
`[75]
`
`Inventors: Eric E. Schmidt, Los Altos, Calif.;
`Butler W. Lampaon. Philadelphia. Pa.
`
`[T3] Assignee: Xerox Corporation, Stamford. Conn.
`[21] Appl. No.: 553,724
`
`[22] Filed:
`
`Nov. 21, 1933
`
`Int. cu
`[51]
`......... .. GIIEF 15/20
`[52] U.S. Cl. ............. ..
`. 364/300; 364/203
`[58] Field of Search ....................................... .. 364/300
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,309,756
`
`12‘ 1932 Bccltler ............................. .. 364/300
`
`OTHER PUBLICATIONS
`
`Morse et al.. DOS/AMAP Model of the DOS Control
`Program. LEM. Technical Discfosure Bulletin. vol. I4,
`NO. 3. Aug. I971. pp. 352-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 Haberrnann,
`Medina—Mora, Peter Feiler. David S. Notltin, Gail E.
`Kaiser, David B. Garlan & Steven Popovich, “The
`Second Compendium of Gandall Documentation”
`CMU Depanment of Computer Science, May 24, I982.
`Gail E. Kaiser 8:. A. Nico Habennann. "An Environ-
`ment for System Version Control" in The Second Com-
`pendium ofGa.ndalf Documentation, CMU Department
`of Computer Science. Feb. 4, 1982.
`B. W. Lampson et al., “Practical Use of a Polymorhic
`Applicative Language". Proceedings of the |0th Sym-
`posium on Principles of Programming Languages. Aus-
`tin, Texas, Jan. 1983.
`W. F. Tichy. “Design Implementation and Evaluation
`of :1 Revision Control System". Proceedings of the 6th
`international Conference on Software Engineering.
`Tokyo. Japan. Sep. 1932.
`
`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—8-
`2-7. dated Dec. I982, "Controlling Large .
`.
`. Environ-
`ment". Schmidt.
`Ira P. Goldstein & Daniel G. B-obrow, “A Layered
`Approach to Software Design,“ Xerox Parc. Tech.
`Report. CSI..—80—S, Dec. I980.
`James G. Mitchell et al.. "Mesa Language Manual.
`Version 5.0" Xerox Parc. Tech. Report. CSI.—?9—3.
`Apr. 1979.
`
`{List continued on next page.)
`
`Primary Examinm-—-Raulfe B. Zache
`Attorney. Agent. or Fr‘.-m—W. Douglas Carothers. Jr.
`
`ABSTRACT
`[57]
`A software version manaizement 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 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 includcs models which are also objects.
`Each of the models is representative of the source 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, 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
`|PR2016-00753
`
`
`
`Page 1
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`

`
`4,558,413
`
`Page 2
`
` _
`
`OTHER PUBLICATIONS
`A. Nico Habermanrt. "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. Ph.D Thesis. CMU Computer Sci-
`ence Department, CMU-CS-79-1 I6. Apr. 14. 1979.
`Eugene Cristofor. T. A. Wendi 8: B. C. Wonsiewicz.
`"Source Conr.rol+Tools=Stable Systems", Proceed-
`ings of the Fourth Computer Software and Applica-
`tions Conference. pp. 527-532. Oct. 29-31. I930.
`A. Demers &. J. Dononhue. “Data Types. Parameters.
`and Type Checking”. Proceedings of the Seventh Sym-
`posium on Principles of Programming Languages. Las
`Vegas, Nevada. pp. 12-23. 1980.
`Frank Dekemer S: H. Kron. "Programming-in-
`the-Large Versus Prograrnming—in—the-Small“, IEEE
`Transactions on Software Engineering, vol. 2. No. 2.
`pp. 30-86, Jun. 1976.
`Stuart 1. Feldman, "Mal:e—A Program for Maintaining
`Computer Programs“, Software Practice and Experi-
`ence, vol. 9, No. 4, pp. 255-256, Apr. 1979.
`[ra 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. 1980.
`Eric I-{arslem and Lelloy 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. I979.
`Evan L. Ivie, "The Programmers Workbench—A Ma-
`chine for Software Development". Communications of
`the ACM, vol. 20. No. 10. pp. 746-753. Oct.
`I9‘.-'7.
`Hugh C. Lauer & Edwin H. Satterthwaite. “The Im-
`pact of Mesa on System Design", Proceedings of the
`4th International Conference on Software Engineering.
`pp.
`l74—132, 1979.
`D. Redell. Y. Dalal, T. Horsley. H. Lauer. W. Lynch.
`P. Molones, H. Murray & S. Purcell. "Pilot: An Operat-
`ing System for a Personal Computer“. Proceedings of
`the Seventh Symposium on Operating System Princi-
`ples, 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
`Computer Science Department. CMU-CS—80- l 20. Jan.
`I980.
`
`PMC Exhibit 2073
`
`Apple v. PMC
`
`|PR2016-00753
`
`
`
`Page 2
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`

`
`U.S. Patent Dec. 10,1985
`
`Sheet! of24
`
`4,558,413
`
`
`
`PRIOR
`
`ART
`
`Fq(3'
`
`1
`
`Iilakeffle
`
`4.?
`
`1.2
`
`3.5
`
`11.51
`
`x2.o
`
`xZ.c
`
`Makefile 3.5
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page 3
`
`
`
`PRIOR ART
`
`FIG. 2
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`

`
`U.S. Patent Dec. 10,1935
`
`Shoet2of24
`
`4,558,413
`
`
`
`other modules and boxes
`
`Other modules and boxes
`
`
`
` Cornpos1t'ion C1
`Version Zfstd)
`
` other modu‘l es
`
`PRIOR
`
`ART
`
`FIG. 3
`
`Configuration Object F'i1a
`
`H L7L“T_,
`
`Source F119
`
`Imp‘leInent.at1on Object F1195
`
`Source F119
`
`Object f1'Ies for Interfaces
`
`FIG. 6
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page 4
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet3of24
`
`4,558,413
`
`C1iBnt:PRUGRAH IMPORTS Sqrtlnt =
`
`{
`
`Irnp'lemantor-:
`
`PROGRAM EXPORTS Sqrtlnt ={
`
`
`
`}:
`
`$qr'tInt.:DEFINITI0NS '' {
`
`Sqrt: PROC[REAL]RETURHS[REAL]:
`
`f7l(3.
`
`-4
`
`}.
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page5
`
`
`
`Impa1amentat1on object f11e
`
`.H
`
`Source f-He
`
`Object H195 for interfaces
`
`f7!C3.
`
`£5
`
`
`
`
`Sqrt: PUBLIC PRDC[s: HEAL]R£TURN[REAL]={
`
`..coda to compute sqrt of a number
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet4of24
`
`4,558,413
`
`
`
`Persnna1
`
`Computer
`
`To other networks
`
`
`FIG. 7
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page6
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`

`
`U.S. Patent Dec. 10,1935
`
`SheetSof24
`
`4,558,413
`
`Users make changes while
`running on re1eased software
`
`Re1ease Master sends
`ca11 for subm1ss1ons
`
`0? files in boot fiie
`
`are e31 announced as ready
`
`Boot f11e for new
`
`re1ease is prepared
`
`Remaining DF F1195 are
`all announced as ready
`
`Rs1ease Hester prepares
`top-1eve1 DF f11e
`
`
`
`
`Users make changes to
`their software 1n response
`
`to errors reported by
`
`Phases One and Two
`
`
`Phases one and Two
`are run at 1east once
`
`Phase Three is run
`
`Rs1ease Hester announces
`
`reiease 1s comp1ete
`
`FIG. 8
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page?
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet6of24
`
`4,558,413
`
`Fi1eToo1.DF
`
`UserExec.DF BBV.DF
`
`PH
`
`BugBane.DF
`
`r1or1tyQuene.DF
`
`TP
`
`
`TTYID.DF
`
`l
`
`ViewersAndT1oga.DF
`I
`l
`
`
`
`CedarCcntro1.DF
`W
`Specia1Bring0ver.DF
`
`C°1°“Pa°k39°-BF 0n11neMergeSort.DF
`F‘
`W
`
`HesaScanner.DF
`
`Graph1cs.DF
`
`Inscript.DF
`
`RiggingMakar.DF
`
`IO.DF. WDr1dVH.DF.
`Runtime.DF.
`L1stsAndAtoms.DF. CIFS.DF
`
`DateAndT1ma.DF
`
`
`
`RPCRunt1me.DF
`¢
`Grapev1naUser.DF CedarSnapshot.DF
`
`l
`
`
`
`R1991]-‘g_D|:
`
`l
`
`Loader.DF
`
`Pine.DF
`
`CedarRea1s.DF Bas1cHands'.DF
`
`CFW.DF
`
`I
`3°”-“F
`'
`rrranr
`Cnmpat1b11ityPackaga.DF W
`
`
`Random.DF
`
`Pup.DF
`
`Term1aa1Mult1p1as.DF
`
`|
`
`Commun1fat1on'.DF
`
`P11ot.Interfaces.DF
`
`F’G- 9
`
`PMC Exhibit 2073
` Apple v. PMC
`IPR2016-00753
`
`
`
`Page8
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`

`
`U.S. Patent Dec.l0,1985
`
`Sheet7of24
`
`4,558,413
`
`I0.DF. wor'1d.DF. Vers1‘onMap.DF,
`Runt1'me.DF.
`L1stsAndAtoms.DF. CIFS.DF
`
`
`
`stands for
`
`CIFS.DF
`
`10-”
`L
`
`Li stsAndAtoms . DF
`
`\
`
`Runt.'lma.DF<j-‘—->'Hor1dVM.DF
`
`Vi51onHap.DF
`
`FIG. 10
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page9
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 9
`
`

`
`U. S. Patent Dec. 10,1935
`
`Sheet8 of24
`
`4,558,413
`
`TTYIO.DF
`
`FiTeToo1.DF
`
`BBV.DF
`
`%¢lr%
`
`V1ewersAndT1oga.DF
`:
`TIP.DF
`
`Co1orIackage.DFN
`
`UserExec.OF
`
`%+H%
`
`Graphics.DF
`
`I0.DF
`
`BugBane.DF
`
`
`
`
`P1ne.DF
`
`ListsAndAtoms.DF
`
`
`Inscr1pt.DF
`
`Runtime.DF-Hor1dVM.D
`
`
`
`
` Vis1onHap.DF
`HesaScanner.D'
`
`Loader.DF
`
`RPCRunt1ma.DF
`¢
`Grapev1naUsar.DF
`
`Spaciaiaring
`0V9"-OF
`
`R1gg1ng.DF
`
`FTP.DF
`
`Cedar
`Bcd.DF Contro1.DF
`
`1 W
`
`P
`Com at1b111tyPackaga.DF
`
`Commun1cat1on'.DF
`
`Term1na1Mu1t1p1ex.DF
`
`
`
`
`BTreas.DF
`
`CedarSnapshot.DF
`Bas1cRaads'.DF
`
`
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page10
`
`
`
`FIG. 11
`
` Pr1or1tyOuaua.DF
`
`CodarRea1s.DF
`
`DataAndT1me.DF
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 10
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet9of24
`
`4,558,413
`
`
`
`Vis1cnMapBu11der.DF
`
`Chat.DF
`
`CIFSCummands.DF
`
` UECP.DF
`
`Sequ'in.DF"*':-'*-* IFS‘r'1'1e.DF
`
`DFF11es.DF
`
`J »
`
`4r-*'Mode1Ier.DF
`
`Comp11ar.DF
`
`Boot
`
`B1nder.DF
`
`L1ster.DF
`
`Packager.DF
`
`PGS.DF
`
`PressPackage.DF -4— Pr--int.DF
`Per'fSt.ats.DF <j CadarDB.DF
`
`CoFork.DF 4----P1otPackaga.DF
`
`Spy.DF'4-““-————*Lupine.DF
`S~ir-Pr*ess.DF *—*'PressScraen.df
`
`BrovoToT1oga.DF
`CedarRea1Test.DF
`
`Inc1udeChacker.DF
`
`Hainta1n.DF
`
`MakeBoot.DF
`
`HCross.DF
`
`0the11u'.DF '
`
`PupHatch.DF
`
`RedB1ackTreeRaf.DF
`
`Set,DF
`
`STPServar.DF
`
`TJnmGraph1cs.DF
`
`Un1qua.DF
`wa1nutSand.DF
`
`RedB1ack
`Trae.DF
`
`HatarL11y.DF
`
`I7!(3.
`
`12?
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page11
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 11
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet lOof24 4,558,413
`
`C1ient1mp1.Hesa
`
` DIRECTORY
` Sort:
`
`C1ientmp1:PROGRAM IMPORTS Sort={
`
`TastTham:PROC[I:LIST OF Dbject]={
`
`--ca1I USortList with this 11st
`
`
`
`
`Ihsort.USortL1st[I.Compare0bjact];
`
`
`
`
`}:
`
`Compara0bject:PROC[n.b:0bject]
`
` RETURNS[Compar1son]-{
`
`
`--compares the two objects
`
`--returns less. equa1. or greater
`
`
`
`}: Sort.Mesa
`
`USortL1st:PRDC[LIST OF Object. CompareProc]
`
`RETURNS[LIST OF Object]:
`
`Sort:DEFINITIOHS-{
`
`0bject:TYPE-RECOflD[
`
`x.y:INT
`
`]:
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page12
`
`
`
`FIG.
`
`'!3A
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 12
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheetllof24 4,558,413
`
`SurtImp1.Mesa
`
`DIRECTORY
`
`Sort:
`
`SortImp‘l:PRDGRAM EXPORTS Sort={
`
`USortL1st:PROC[I:LIST OF Object.
`
`compareProc: ComparePruc]
`
`RETURl'lS[nevrI:LIST or Object]-{
`
`--code to sort the 1151'. I.
`
`e‘! 'im1nat1ng dup'l icates
`
`};
`
`T0 FIG. 13A
`
`FIG. 138
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page13
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 13
`
`

`
`U.S. Patent Dec. 10, 1935
`
`sheeuz of24 4,558,413
`
`SortCoord.Mesa
`
`Sort:DEFINITIONS'{
`
`0bject:TYPE=RECORD[
`
`x.y:INT
`
`]:
`
`RETURNS[L1ST OF Object]:
`
`USortL1st:PROC[LI5T OF Object. CompareProc]
`
`Sortflames .Masa
`
`Sort:DEFINITIONS-{
`
`0bject:TYPE-RECORD{
`
`x:STRIHG
`
`]:
`
`RETURNSELIST OF Object]:
`
`USurtL'ist:Pfi0C[LIST OF Object. CumpareProc]
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page14
`
`
`
`FIG. 14
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 14
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheetl3 of24 4,558,413
`
`SortQuickImp1.Masa
`
`DIRECTORY
`
`Sort:
`
`SortQu1ckImp1:PROGRAH EXPORTS Sort={
`
`USortList:PUBLIC PROC[I:LIST OF Object.
`
`compareProc:Cumpare?roc]
`
`RETURNS[newI:LIST OF 0bject]={
`
`--code to sort the list I. e1im1nating dup11cates
`
`--use Quicksort
`
`}:
`}:
`
`SortHeapImp1.Masa
`
`DIRECTORY
`
`Sort;
`
`SortHBapImp1:PROGRAH EXPORTS Sort-{
`
`USortL1st:PUBLIC PROC[I:LIST OF Object.
`
`comparaProc:CompareProc]
`
`RETURNS[newI:LIST OF Object]-{
`
`--code to sort the 11st I. e11m1nat1ng dup11cate5
`
`--use Heapsort
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page15
`
`
`
`FIG. 15A
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 15
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet14 of24 4,558,413
`
`CliantImp1.Masa
`
`DIRECTORY
`
`Sort:
`
`C11‘entImp1:IMP0RTS SortQu'ickInst.-Sort.SnrtHeapInst:Sor't.=
`
`TestThem:PROC[I:LIST OF Objact}={
`
`--ca11 USortL1st with this 11st.
`
`try Quicksort
`
`newI+SortQu1ckInst.USortList[I.ComparaObject]:
`
`---now try Haapsort
`
`newI+SortHeapInst.USortL1st[I.Compare0bject]:
`
`}:
`
`CompareobjectzPROC[a.b:0bject]
`
`RETURHS[Compar1son]-{
`
`--compares the two objects
`~-returns 1955. equal. or greater
`
`}:
`
`FIG. 15B
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page16
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 16
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet15 of24 4,558,413
`
`C1ientImp1.Hesa
`
`DIRECTORY
`
`SortCoord:INTERFfiCE Sort.
`
`SortNames:INTERFACE Sort:
`
`C1ientImp1:PROGRAH IMPORTS SortQuickCooruInst:SortCoord.
`
`SortQu1ckHamesInst:Sortflames.Sortneaptoordlnst:SartCoord.
`
`SartHeapNamesInst={
`
`TestThem:PROC[I1:LIST OF SortCaord.Dbject.I2:LIST OF SartNames.0bject]=
`
`newi-SortQuickcoordlnst.USortList[I1. Comparecoordinateobjects]:
`
`newI~SortHeapCourdInst.USurtList[I1. Comparecoardinateobjectsj:
`
`nauI~SortQuickName5Inst.USortList{I2. Campereflamaobjects].
`
`newI~SortHeapNamesInst.USortList[I2. Compereflamesflbjectsj:
`
`Comparecoordinate0bjects:PflDC[a.b:?SortCoord.0bject]RETURNS[Compar1sun]={
`
`--compares a and b. returns 1e55, equa1, or greater
`
`}:
`
`Compareflameobjects:PRDC[a.b:Sortflames.Dbject]RETURN5[Comparison]={
`
`--compares a and b. returns 1ess. equal.
`
`fir greater
`
`FIG. 16
`
`PMC Exhibit 2073
`
`
`
`Apple v. PMC
`|PR2016-00753
`
`Page 17
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 17
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet 16 of24 4,558,413
`
`Btree.rru:Ide¥!(Jan14,1983.14:44:11}
`
`LET@IIncligcI]<Cedar)Ced-armsracas.mode-I!{Ju1~,r 25. 1932. 'I4:O3‘.O3)|N
`
`LET.InsIan::es--@[|ndigo]<Cedar)Cedar.fnsIandes.modeH{Ju1y £5. 1982. 14"10:12)|N
`
`BTree:!NTEFIFACE BTree-@[Ivy]<Scl1midt>BTree.cedar![Sept9.1982.18:52:55}
`
`[Ascif].
`
`Bheelnsr: BTree~@[lvy](SI:hrnid1>BTreeJms:.cedar!{.Jan 14, ‘t3B3,14:44:O9}
`
`'[] [msrances..»'1‘ope, mstancemo. ms:ances.Space]] ]
`
`Cedarlnlerfaces.model!{July, 25. 1982.14:O3:03)
`
`I
`
`Ascn':iNTEF{FACE-@[|undigo]<Cedar>Ascii.cedar!(.!u|y 10.1982. 12-.25:00)[].
`
`Ham-:INTEFIFACE-—@[1n:Iigo]<Cedar>Rope.cedartuuly ‘I0. 19El2.1?:D0:00)"[].
`
`IO:|NTEFIFACE-@[lndigD](Ceda.r)|O.ceI:far!{Ju|y12.1982.11:00:DD)'[].
`
`Space:|NTEFlFACE*-@[Indigo}(Cedar>Space.Ce-darI{June 10. 1932. 3:35:00)‘ []]
`
`Cedarlnstances.n1ode1!{Ju|y 25, ‘I982. 14:10:12)
`
`[Asch-'. Hope, :0. Space]-
`
`LET@Cedann:erfac e.modeI![Ju!y 25. 1932. 14:03:03] IN [
`
`@{|ndigo]<Cedar)AscmmpJ.cedar!(Ju|y10.19B2.‘12:30:0D}[][].
`
`@findigc:}<Ceda'l)Fh;=pe.'mpa‘.cedal!tJu|y10.‘1982.1T:10:2d}'{]' [].
`
`@{Indigo](Ceda:>.'OImp='.cedar![July 20. 1982. 13:D3:D3J'[]'[].
`
`@[Indigo]<Cedar)5aace.cedarfidune 11,1932. 15:00:00] '[] '[]]
`
`FIG. 17
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page 18
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 18
`
`

`
`U.S. Patent Dec. 10, 1935
`
`Sheet 17 of24 4,558,413
`
`Objecttype table
`
`
`Source omecl
`Type
`
`
`BTree.Ceo'arE(Sept 9. 1982. 13:52:55]
`
`[|NTEFlFACE£scn}- [INTERFACES Tree]
`
`BTreeFmp!.cedar![Jan 9. ‘I983. 14:44:09)
`
`[F~'ope;|NTERFACERope. e'O,Space:INTEFIFACE Space.
`
`BTree:tNTERFACEBTree]
`
`[[Ropernsl.-Rope. JD. Spacemsr.-Space]
`EiTree]I
`
`IBTree.=nsr:
`
`Projection table
`
`Source object
`
`Parameter values
`
`Results object
`
`BTree.cedar![Sept9.l982.
`13:52:55)
`
`[Ascftbinar-,r!23ACD904EFFA]
`
`8Tree.binary!43956A3C32F0
`
`Brreermmcedariilan 14. 1983.
`14:4-4:09]
`
`[Ropebn'nary!AC9023ET6FA6.
`.‘O.b:'nary!23843396A24f.
`
`8Tree.*mp:,bIraary!2(}45FFD2B3C
`
`Space.b:'nrary!S348823FF?61.
`BTree.bmary{43956A3C32FU]
`
`FIG.
`
`1 8
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page 19
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 19
`
`

`
`U.S. Patent Dec. 10, 1935
`
`Sheet18of24 4,558,413
`
`Version map
`
`Object name
`File location
`
`
`8Tree.cedar![Sept 9. 1982. 13:52:55}
`
`[Ivy](Sch:-nidt>BTree.cedar4
`
`BTree.!mpr.cedar!(.Jan 14,1983. 14:44:09}
`
`[ivy]<Sc:hmid!>BTree|rnpl.cedar!9
`
`BTree.bmary!43956A3C32F0
`
`[ivy}<Schmidt>BTree.binary!2
`
`BTreel'rnpI.binary!2045FFD283C
`
`[Ivy](SChrnidt>BTreelI'np1.binatylfi
`
`Ascii.binary!23ACD904EFFA
`
`[Indigo]<Cedar>AscEi.binary23
`
`FIG. 19
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`
`
`Page 20
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 20
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet 19 of24 4,558,413
`
`
`
`Cedar Mude11er. started on 3—Feb-83 16:16:01 PST
`
`Storefiack Un'!oad StopHode1
`Start}'«‘.ude'iBeg'in Continue
`Makeflod-=e1Bcd B-ind Newflodefler
`
`Comp11e Load Start
`
`Hodelflame:
`
`Examp1a.Hoda1
`
`
`
`Compiling: Examp1eImp1A.Mesa .... no errors.
`Ccmp'i'|'ing: Exan:p1eImpTB.Mesa
`
`Star-Mode‘t Exarnp'|e.Mode‘I
`Prasing Examp1e.Hoda1
`Ana'lyz~ing Parameters
`
`
`
`
`
`q — o . q — — — _ _ _ _ _ _ _ _ _ _ _ --
`
`- — u _ — — — u p — _ _ __._——___-
`
`
`
`
`Begin Examp‘Ie.Mode'|
`Try for compilation:
`Examp1aImp1A.Hesa:Conf1rrn Compflation ? Yes
`Compilation completed. no errors.
`Examp'|e1mp1B.Hesa: Confirm Cc-mp1'Iat1on ? Yes
`
`
`
`FIG. 20
`
`
`
`
`
`
`
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-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
`
`StartMode1
`
`User Efifts FiTes'<--W
`
`
`
`Not1ce Operation
`
`User Test Program
`
`i
`
`User Edits F1195
`
`l
`
` Succeeds
` Continue
`
`Storeflack
`
`Notice Operation
`
`
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page22
`
`
`
`Stoprdodal
`
`FIG. 2 1
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 22
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet2l of24 4,558,413
`
`
`
`@[Ivy]<5chmidt>x.Mesal(July 25. 1982 14:03:02}
`
`
`
`
`
`
`
`Lnokup in F119 Type Tab1e
`
`
`
`Found
`
`Not found
`
`Lookup f11e in Version map
`
`Not found
`
`Search [Ivy]<Schm1dt> for a11 "x.Mesa"
`
`Not found
`
`
`
`
`
`
`
`Enter in version map
`
`Read F113
`
`Enter 1n F113 Type Tab1e
`
`FIG. 22
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page23
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 23
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet 22 of24 4,558,413
`
`Look for X.Mesa of Ju1y 25. 1932 14:03:02 with
`no parameters in projection table
`
`
`
`
`
`Found
`
`Not found
`
`
`
`
`
`
`Generate unique id it wou1d have = x.Bcd of
`1ABCDZ346DED Lookup in Version Map
`
`Not found
`
`Enumerate [Ivy]<Schm1td> 1ooking for
`x.Bcd of 1ABCD2346DED
`
`
`
`Not found
`
`Enter
`
`in version map
`
`Compi1e x.Hesa with no parameters
`
`
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page24
`
`
`
`FIG. 23
`
`Enter X.Bcd of 1ABCD2a46DED
`
`in projection table
`
`
` Object fi1e X.Bcd of 1ABCDZ346DED exists
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 24
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet 23 of24 4,558,413
`
`
`
`Load XImp1.Bcd Of 2ADEF345EDCA
`
`
`
`
`
`Lonkup in Version Map
`
`Found
`
`Not found
`
`
`
` Enumerate [Ivy](Schm1dt>
`100k for XImp1.Bcd OF ZADFE245EDCA
`
`
`
`Not found
`
`
`
`in Version map
`
`Enter
`
`
`
`
`
`Read f11e [Ivy]<Schmidt>XImp1.BcdI22 and 1oad
`
`FIG. 24
`
`Re1ease T001: Phase Hove
`
`[Ivy]<Schm1at)X.Mesa!4
`
`[Ind1go]<Cedar>X.Nasa!2
`
`[Ind1go]<Cedar>YImp1.Mesal2
`
`[Ivy]<Schmidt>XImp1.Masa16
`
`[Ind1go]<Cedar>XImp1.Mesal3
`
`[Ivy]<Schmidt>Y.Hesal43
`
`[Ind1go](Cedar>Y.Hasar1
`
`[Ivy]<Schm1dt>YImp1.Mesal34
`
`FIG. 25
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page25
`
`
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 25
`
`

`
`U.S. Patent Dec. 10,1935
`
`Sheet 24 0:24 4,558,413
`
`Re1ease Too1: Phase Buiid
`
`[Ivy]<5chm1'dt)J<.Bcdl23
`
`[Ind'igo]<Cedar>X.BcdI2
`
`[Ivy](Schm1'dt>XImp1.Bcd! 22
`
`[Ind1'go]<Cedar>XImp1.Bcd11
`
`[Ivy]<Schmidt)Y.Bcdl16
`
`[Indigo]<Cedar>Y.BcdI1 [Ivy]<5chn11'dt)YImp'| .Bcdl1Z
`
`[Ind1'gn](Cedar>YImp‘I .Bcd!2
`
`FIG. 26
`
`Version Map After Re1aase
`
`Fiie Location
`
`x.Mesa of Ju'ly 25.1982 14:03:02
`
`[Ind1'go]<Cedar>X.Mesal2
`
`XIrnp'|.Hasa of Ju'|y 25.1982 14:05:06 [Ind'igo]<Cedar'>xImp1.MesaI3
`
`Y.Masa of July 25.1982 15:06:08
`
`[In:!'igo]<Cedar>Y.hIesal1
`
`YImp1.Mesa of July 25,1982 15:07:03
`
`[Ind'igo]<Cedar'>YInIp'I.Mesa!2
`
`X.Bcd of IABCDZ34-6DED
`
`[Ind'igo]<Cedar>X.Bcd!2
`
`XImp1.Bcd of 2ADEF345EDCA
`
`[Ind-igu]<Cedar'>xImp1.Bcdl1
`
`Y.Bcd of 342.1ABD4235A
`
`[Ind1go]<Cedar>Y.Bcdl1
`
`[Ind1go]<Cedar)YImp1.Bcd12
`
`YImp1.Bcd of 23455BBDC63B
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page 26
`
`
`
`FIG. 27
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 26
`
`

`
`1
`
`4,558,413
`
`SOFTWARE VERSION MANAGEINIENT 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 urtiformily 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 "Ceclar“ now has
`approximately 44‘l‘,CI]0 lines of Cedar code. and approx-
`imately 2(Il0 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
`
`S5
`
`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
`software module.
`instead of “Programming-in-the
`Small", where units include scalor variables. statements.
`expressions and the like. See the Article of Frank
`Dekemer and H.
`l(rorI, "Programming-in-the-Large
`versus Programming in the small". IEEE Transactions
`on Software Engineering. Vol. 2(2). pp. 80-86, J une 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 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 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 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 down into three categories:
`I. 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 a 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. Of 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 2073
`
`Apple v. PMC
`
`|PR2016-00753
`
`
`
`Page 27
`
`PMC Exhibit 2073
`Apple v. PMC
`IPR2016-00753
`Page 27
`
`

`
`4,558,413
`
`4
`IEEE Transactions on Software Engr‘neen'ng, 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-ou " 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 “s.“ 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 (SMFJ
`Make and SCCS were unified in special tools for a
`development project at Bell Labs called the Software
`Manufacturing Facility {SMF) and discussed in the
`Article of Eugene Cristofer, F. A. Wendt and B. C.
`Wonsiewicz, "Source Control & Tools=Stab|e Sys-
`tems", Proceedings of the Fourth Computer Software &
`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 consists 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 (1) 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.s| 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 software 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 Corpo-
`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-30-5.
`December 1980; Ira P. Goldstein and Daniel G. Bo-
`brow, "Descriptions for a Programming Environment".
`Proceedings of the First Annual Conference of the Na-
`tiara! Association of Anijficial Intelligence. Stanford.
`Calif., August 1980; Ira P. Goldstein and Daniel G.
`Bobrow, "Representing Design Alternatives”, Proceed-
`
`PMC Exhibit 2073
`
`Apple v. PMC
`|PR2016-00753
`
`Page 28
`
`
`
`5
`
`10
`
`I5
`
`20
`
`25
`
`In Table I. the expression, “cc-c xl.c" is the com-
`mand to execute and produce a new version of xI.o
`when xl.c is changed. Make decides to execute the
`make rule i.e., compile xI.c, if the file modification time
`ofxl.c is newer th