United States Patent
`
`{19]
`
`[11] Patent Number:
`
`4,558,413
`
`Dec. 10, 1985
`[45] Date of Patent:
`Schmidt et al.
`
`[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] App1.No.: 553,724
`
`[22] Filed:
`
`Nov.21,1983
`
`Int. Cl.‘ .............................................. 006]? 15/20
`[51]
`
`[52] US. CL ............................
`.. 364/300; 364/200
`[53] Field of Search ......................................... 364/300
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,309,756
`
`1/1982 Beckler ............................... 364/300
`
`OTHER PUBLICATIONS
`
`Morse et al., DOS/AMAP Model of the DOS Control
`Program, LEM. 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 Feller, David S. Notkin, Gail E.
`Kaiser, David B. Garlan & Steven Popovich, “The
`Second Compendium of Gandall Documentation"
`CMU Department 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. Lampson et al., “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 3 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 Development in 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 Pare. Tech.
`Report, CSL—80—5, Dec. 1980.
`James G. Mitchell et a1., “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.
`
`ans'rmcr
`[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 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.
`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
`
`Page 1 of 58
`
`SAMSUNG EXHIBIT 1018
`
`Page 1 of 58
`
`SAMSUNG EXHIBIT 1018
`
`

`

`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. 303-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-ll6, 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”, Proceedings of the Seventh Sym-
`posium on Principles of Programming Languages, Las
`Vegas, Nevada, pp. 12—23, 1980.
`“Programming—in—-
`Frank DeRemer & H. Kron,
`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 3 Programming Environment", Proceedings of the
`
`First Annual Conference of the National Association of
`Artificial Intelligence, Stanford, California, Aug. 1980.
`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. 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—SO—IZO, Jan.
`1980.
`
`Page 2 of 58
`
`Page 2 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheetl of24
`
`4,558,413
`
`
`
`ab.s1
`
`ab.s1
`
`5.51
`
`b.51
`
`3.5
`
`4.7
`
`2.3
`
`Makefile 4.9
`
`4.7
`
`U.31
`
`2.3
`
`x1.o
`1.2
`x2.o
`1.3
`
`
`x1.c
`1.4
`x2.c
`3.5
`
`
`
`Makefile 4.5
`Makefile 3.5
`
`
`
`
`PRIOR ART
`
`FIG. 2
`
`Page 3 of 58
`
`Page 3 of 58
`
`

`

`U.S. Patent Dec. 10,1985
`
`Sheet20f24
`
`4,558,413
`
`Other modules and boxes
`
`Other modu1es and boxes
`
`
`
`
`
`Compos1t1‘on C1
`
` Other modules
`
`Version 2(std)
`
`PRIOR
`
`ART
`
`FIG. 3
`
`Configuration Object FiTe
`
`H Lfl—j
`
`Source F119
`
`Implementation Object F1195
`
`Source FiTe
`
`Object fi1es for Interfaces
`
`FIG. 6
`
`Page 4 of 58
`
`Page 4 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet3of24
`
`4,558,413
`
`C1ient:PROGRAM IMPORTS SqrtInt =
`
` .......
`
`.......
`
`{
`
`
`ImpTementor:
`PROGRAM EXPORTS SqrtInt ={
`
`Sqrt: PUBLIC PROC[s: REAL]RETURN[REAL]={
`
`
`
`..code to compute sqrt of a number
`
`
`
`
`
`}:
`
`
`
` SqrtInt:DEFINITIONS = {
`.......
`
`
`
`Sqrt: PROC[REAL]RETURNS[REAL];
`
`}.
`
`f3lC3.
`
`l1
`
`Impelementation object f11e
`
`”H
`
`Source f11e
`
`Object f11es for interfaces
`
`I:IC3.
`
`55
`
`Page 5 of 58
`
`Page 5 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet4of24
`
`4,558,413
`
`
`
`Persona]
`
`Computer
`
`Storage
`Disk
`
`
`
`1o
`
`Persona1
`
`Computer
`
`Persona1
`
`Computer
`
`
`
`To other networks
`
`FIG. 7
`
`Page 6 of 58
`
`Page 6 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet50f24
`
`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
`
`
`
`
`
`Users make changes to
`their software in response
`
`to errors reported by
`
`Phases One and Two
`
`
`FIG. 8
`
`Phases One and Two
`are run at least once
`
`Phase Three is run
`
`Release Master announces
`
`release is complete
`
`Page 7 of 58
`
`Page 7 of 58
`
`

`

`U.S. Patent Dec. 10,1985
`
`Sheet6of24
`
`4,558,413
`
`Fi1eToo1.DF
`
`
`
`UserExec.DF BBV DF
`
`TTYID.DF
`
`BugBane.DF
`
`PriorityQuene.DF
`
`CedarContro1.DF
`
`LN
`
`
`ViewersAndTioga.DF
`
`i L—+
`Co1orPackage.DF 0n11neMergeSort.DF
`
`;
`SpecialBringOver.DF
`Graphics.DF
`
`;
`MesaScanner.DF
`
`Inscript.DF
`
`R1991n9Maker,DF
`
`IO.DF. WorldVM.DF,
`Runtime.DF,
`ListsAndAtoms.DF. CIFS.DF
`
`DateAndTime.DF
`
`RPCRuntime.DF
`¢
`GrapevineUser.DF CedarSnapshot.DF
`
`
`
`i
`
`
`
`
`
`
`Pine.DF
`
`BTrees.DF
`
`+
`CedarReals.DF BasicHeads‘.DF
`
`CFW-DF
`
`FTP.DF
`
`i
`
`BCd.DF
`
`i
`
`
`
`
`Compat1b111tyPackageDF TerminalMultiplas. DF
`
`Random DF
`
`Pup. DF
`
`Communication‘. DF
`
`P11ot1nterfaces. DF
`
`FIG. 9
`
`Page 8 of 58
`
`Page 8 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet7of24
`
`4,558,413
`
`
`
`IO.DF. Wor1d.DF, VersionMap.DF.
`Runtime.DF.
`ListsAndAtoms.DF. CIFS.DF
`
`
`
`stands for
`
`CIFS.DF
`
`10-”
`
`ListsAndAtoms.DF
`
`
`
`
`Runtime.DF <———> WorldVM.DF
`
`I
`
`VisionMap.DF
`
`FIG. 10
`
`Page 9 of 58
`
`Page 9 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet80f24
`
`4,558,413
`
`TTYIO. DF
`
`F11eT001. DF
`
`BBV.DF
`
`V1ewersAndTioga. DF
`
`Co1orPackage.BF};TIP.DF
`
`UserExec.DF
`
`Graphics.DF
`
`10. DF
`
`BugBane.DF
`
`
`P1ne.DF
`L1stsAndAtoms.DF
`
`
`
`Inscr1pt.DF
`
`
`Runt1me DF—'Wor1dVM D
`
` VisionMap.DF
`
`Loader.DF
`MesaScanner.D'
`
`CIFS.DF
`RPCRuntime.DF
`
`
`GrapevineUsar. DF
`
`SpecialBring
`0V9P~DF
`
`
`
`Rigging.DF
`
`DateAndTime.DF
`
`Cedar
`‘
`FTP.DF Bcd.DF Control.DF
`Wlf‘J
`
`Compatib111tyPackage. DF
`
`TerminalMuTtiplex.DF
`
`
`
`
` PriorityQueue.DF
`Communication‘.DF
`
`CedarReaTs.DF
`BTrees.DF
`
`CedarSnapshot.DF
`BasicHaads'.DF
`
`
`
`P11ot1nterfaces.DF
`
`FIG. 11
`
`Page 10 of 58
`
`Page 10 of 58
`
`

`

`U.S. Patent Dec. 10,1935
`
`Sheet9of24
`
`4,558,413
`
`VisionMapBuilder.DF
`
`
`
`Chat.DF
`
`UECP.DF
`
`
`Sequin.DF<———"IFSF119.DF
`
`CIFSCommands.DF
`
`DFFi1es.DF
`
`‘
`
`‘*-—-Mode11er.DF
`
`Comp11er.DF
`
`300‘
`
`FiIe
`
`Binder.DF
`
`Lister.DF
`
`Packager.DF
`PGS.DF
`
`PressPackage.DF‘*—-Print.DF
`PerfStats.DF-<---'CedarDB.DF
`
`CoFork.DF <—-—-—-—-P10tPackage.DF
`
`Spy.DF <———— Lup1ne.DF
`
`SirPress.DF <————-PressScreen.df
`
`BrovoToTiaga.DF
`CedarRea1Test.DF
`
`Inc1udeChecker.DF
`
`Maintain.DF
`
`MakeBoot.DF
`
`MCross.DF
`
`0the]10‘.DF
`
`PupWatch.DF
`
`RedBlackTreeRef.DF
`
`Set.DF
`
`STPServar.DF
`
`TJamGraphics.DF
`
`Un1que.DF
`WalnutSend.DF
`
`RedB1ack
`Tree.DF
`
`WaterL11y.DF
`
`f=I(3.
`
`12?
`
`Pagell70f58
`
`Page 11 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 10 of24 4,558,413
`
`C11ent1mp1.Mesa
`
`DIRECTORY
`
`Sort:
`
`C1ientmp1zPROGRAM IMPORTS Sort={
`
`TestThem:PROC[I:LIST 0F Object]={
`
`--ca1] USortList with this 1ist
`
`I+Sort.USortL1st[1.CompareObject]z
`
`}:
`
`CompareObject:PROC[a.b:Object]
`
`RETURNS[Comparison]={
`
`--compares the two objects
`
`FROM
`FIG. 138
`
`--returns less. equa1. or greater };
`
`Sort.Mesa
`
`Sort:DEFINITIONS={
`
`Object:TYPE=RECORD[
`
`x.y:INT
`
`];
`
`USortList:PROC[LIST OF Object. CompareProc]
`
`RETURNS[LIST OF Object]:
`
`FIG. 13A
`
`Page 12 0f58
`
`Page 12 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheetll of24 4,558,413
`
`SortImp1.Mesa
`
`DIRECTORY
`
`Sort:
`
`}:
`
`SortImp1zPROGRAM EXPORTS Sort={
`
`USortList:PROC[I:LIST 0F Object.
`
`compareProc: CompareProc]
`
`RETURNS[newI:LIST 0F 0bject]={
`
`--code to sort the 1ist I.
`
`e11m1nating dupIicates
`
`T0 FIG.
`
`13A
`
`FIG. 138
`
`Page 13 0f58
`
`Page 13 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet120f24 4,558,413
`
`SortCoord.Mesa
`
`Sort:DEFINITIONS={
`
`Object:TYPE=RECORD[
`
`x.y:INT
`
`]:
`
`RETURNSELIST OF Object]:
`
`USortList:PROC[LIST 0F Object. CompareProc]
`
`SortNames.Mesa
`
`Sort:DEFINITIONS={
`
`Object:TYPE=RECORD[
`
`x:STRING
`
`J:
`
`RETURNS[LIST 0F Object];
`
`USortList:PROC[LIST OF Object. CompareProc]
`
`FIG. 14
`
`Page 14 0f58
`
`Page 14 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet13 of24 4,558,413
`
`SortQuickImpl.Mesa
`
`DIRECTORY
`
`Sort;
`
`SortQuickImpl:PROGRAM EXPORTS Sort={
`
`USortList PUBLIC PROC[I:LIST 0F Object.
`
`compareProc:CompareProc]
`
`RETURNSEnewIzLIST 0F 0bject]={
`
`--code to sort the list I. eliminating duplicates
`
`--use QuickSort
`
`};
`}:
`
`SortHeapImpl.Mesa
`
`DIRECTORY
`
`Sort;
`
`SortHeapImpl:PROGRAM EXPORTS Sort-{
`
`USortList:PUBLIC PROC[I:LIST 0F Object.
`
`compareProc:CompareProc]
`
`RETURNS[newI:LIST 0F 0bject]={
`
`--code to sort the list I, eliminating duplicates
`
`--use HeapSort
`
`FIG. 15A
`
`Page 15 0f58
`
`Page 15 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 14 on4 4,558,413
`
`Clientlmp1.Mesa
`
`DIRECTORY
`
`Sort;
`
`Clientlmp1:IMPORTS SortQuickInst:Sort.SortHeapInst:Sort=
`
`TestThem:PROC[I:LIST OF Object]={
`
`--ca11 USortList with this list.
`
`try QuickSort
`
`newI+SortQuickInst.USortList[I.CompareObject]:
`
`---now try HeapSort
`
`newI«SortHeapInst.USortList[I.CompareObject]:
`
`}:
`
`}:
`
`CompareObject:PROC[a,b:0bject]
`
`RETURNS[Comparison]={
`
`--compares the two objects
`--returns Tess. equa1. or greater
`
`FIG. 153
`
`Page 16 of 58
`
`Page 16 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet150f24 4,558,413
`
`C1ientImp1.Mesa
`
`DIRECTORY
`
`SortCoordleTERFACE Sort.
`
`SortNames:INTERFACE Sort:
`
`ClientImplzPROGRAM IMPORTS SortQuickCoordInst:SortCoord.
`
`SortQuickNamesInst:SortNames,SortHeapCoordInst:SortCoord.
`
`SortHeapNamesInst={
`
`--compares a and b. returns 1e55, equa1. or greater
`
`TestThem:PROC[Il:LIST 0F SortCoord.0bject.I2:LIST 0F SortNames.0bject]={
`
`newI~SortQuickCoordInst.USortList[I1. CompareCoordinateObjects];
`
`newI«SortHeapCoordInst.USurtList[Il. CompareCoordinateDbjects];
`
`newI¥SortQuickNamesInst.USortList[IZ. CompareNameObjects],
`
`newI~SortHeapNamesInst.USortList[I2. CompareNamesObjects];
`
`}:
`
`CompareCoordinateObjects:PROC[a.b:?SortCoord.0bject]RETURNS[Comparison]={
`
`--compares a and b. returns 1e55, equa1. or greater
`
`}:
`
`CompareNameObjects:PROC[a,b:SortNames.0bject]RETURNS[Comparison]=(
`
`FIG. 16
`
`Page 17 of 58
`
`Page 17 of 58
`
`

`

`U.S. Patent Dec. 10,1985
`
`Sheet 16 of24 4,558,413
`
`Btree.model!(Jan14,1983,14:44:11)
`
`LET@[|ndigo}<Cedar>Cedarlnsraces,mode/NJuiy 25, 1982, 14:03:03]|N
`
`LETlnsrances~@[Indigo]<Cedar)Cedar Instandesmodellmuly 25, 1982, 14:10:12)IN
`
`BTree:lNTERFACE BTree~@[Ivy]<Schmidt>BTree.cedar!(Sept 9,1982, 13:52:55)
`
`[Ascif],
`
`BTreeInst: BTree~@[lvy]<Schmidt>BTreelmp1.cedar!(Jan 14, 1983, 14:44:09)
`
`'[] [Instancesflopa InstancesJO, Instancesfipace] ]]
`
`Cedarlnterfaces.mode|!(du1y,25,1982,14:O3:03)
`
`[
`
`AsciileTERFACE~@[1ndigo](Cedar>Ascii.cedar!(July10.1982. 12:25:00)[],
`
`Rope:lNTERFACE~@[Indigo]<Cedar>Rope.cedar!(July10,1982, 17:00:00)‘[],
`
`IO:INTERFACE~@[Indigo]<Cedar)lO.cedar!(Ju|y 12, 1982. 11:00:00)‘[],
`
`Space:lNTEFlFACE~@[lndigo]<Cedar>Space.Cedar!(June 10, 1982, B:35;00)'[]]
`
`Cedarlnstances.model!(Ju)y 25,1982,14:10:12)
`
`[Ascii, Rope, IO, Space]~
`
`LET@Cedarmrerface.mode!!(Ju|y 25, 1982, 14:03:03) IN [
`
`@[Indigo]<Cedar)Asch’!mchedar!(July 10, 1982, 12:30:00)[] [],
`
`@[1ndigo]<Cedat>Hopelmp/.cedat!(Ju|y10,1982. 17:10:24)‘[]‘ [],
`
`@[)ndigo]<Cedar>lO/mpl,cedar!(July 20, 1982. 13:03:03)'[]‘[],
`
`@[lndigo]<Cedar>Space.cedar!(June 11,1982. 15:00:00)‘[]'[]]
`
`FIG. 17
`
`Page 18 of 58
`
`Page 18 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet17of24 4,558,413
`
`Object type table
`
`
`Source owec!
`Type
`
`
`BTree,Cedar!(Sept9.1982,13:52:55)
`
`[)NTERFACEASCH) [INTERFACEBTree]
`
`BTree/mp/.cedar!(Jan 9. 1983, 14:44:09)
`
`[Rope:INTERFACERope. 10.8paceziNTEFlFACE Space.
`
`BTree:lNTERFACEBTree]
`
`[[Ropelnsr:Rope, IO, Space!nst:5pace)
`BTreeH
`
`[BTreelnsL-
`
`Projection table
`
`Source object
`Parameter values
`Results object
`
`
`BTree.cedar!(Sept 9,1982.
`13:52:55)
`
`[Ascii.binary!23ACD904EFFA]
`
`BTree.binary!43956A3C32F0
`
`BTree!mp/.cedar!(lan 14, 1983.
`14:44:09)
`
`[RopebinarylAC9023E76FA6.
`IO.binary!23843 396A24f.
`
`BTreeImpl.binary!2045FFD283C
`
`Space.binary!8348823FF761.
`BTree.binary543956A3C32F0]
`
`
`FIG. 18
`
`Page 19 of 58
`
`Page 19 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet18 of24 4,558,413
`
`Version map
`W
`
`Object name
`File location
`
`
`BTree.cedar!(Sept 9, 1982, 13:52:55)
`
`[tvy]<Schmidt>BTree.cedar4
`
`BTree./mpl.cedar!(Jan 14,1983, 14:44:09)
`
`[Ivy](Schmidt>BTreelmchedar19
`
`BTree.binary!43956A3C32FO
`
`[Ivy]<Schmidt>BTree.binary12
`
`BTree/mpl.binary!2045FFD283C
`
`[lvy](SChmidt>BTreelmp|.binary!5
`
`Ascii.binary123ACD904EFFA
`[lndigo]<Cedar>Ascii.binary23
`
`
`FIG. 19
`
`Page 20 of 58
`
`Page 20 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheetl9 on4 4,558,413
`
`
`
`Cedar Modeller, started on 3-Feb-83 16:16:01 PST
`
`
`
`StoreBack Unload StopModel
`StartModelBegin Continue
`MakeModechd Bind
`NewModeller
`
`
`
`Compile Load Start
`
`
`
`
`ModelName:
`Example,Model
`
`
`Compiling: ExampleImplA.Mesa .... no errors.
`Compiling: ExampleImplB.Mesa ...
`
`
`StarModel Example.Model
`Prasing Example.Model
`
`
`Analyzing Parameters
`
`
`
`30
`
`32
`
`34
`
`36
`
` <
`
`L
`
`Page 21 0f58
`
`
`Begin Example.Model
`Try for compilation:
`ExamplelmplA.Mesa:Confirm Compilation ? Yes
`Compilation completed. no errors.
`ExampleImplB.Mesa: Confirm Compilation ? Yes
`
`
`
`
`
`
`
`
`
`%/////A
`
`
`
`FIG. 20
`
`
`
`
`
`
`
`Page 21 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 20 of24 4,558,413
`
`StartMode1
`
`User Edits Fi1es
`
`l
`
`Notice Operation
`
`User Test Program
`
`l
`
`User Edits Fi1es
`
`l
`
`Notice Operation
`
`F
`
`'1a1 5
`
`Succeeds
`
`StoreBack
`
`FIG- 21
`
`Page 22 0f 58
`
`Page 22 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 21 of24 4,558,413
`
`@[Ivy]<5chmidt>X.Mesa!(July 25. 1982 14 03 02)
`
`
`
`
`
`Lookup 1n Fi1e Type Table
`
`Found
`
`Not found
`
`Lookup fi1e in Version map
`
`
`
`Not found
`
`
`
`
`
`
`
`
`
`
`
`
`
` Search [Ivy]<Schmidt> for a11 "X.Mesa"
`
`Not found
`
`Enter in version map
`
`Read F119
`
`Enter in File Type Table
`
`
`
`Success
`
`FIG. 22
`
`
`
`Page 23 of 58
`
`Page 23 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 22 of24 4,558,413
`
`
`
`Look for X.Mesa of Juiy 25. 1982 14:03:02 with
`no parameters in pPOJECt10n tab1e
`
`
`Found
`
`Not found
`
`
`
`Generate unique id it wou1d have = X.Bcd of
`1ABCDZS4BDED Lookup in Version Map
`
`
`
`
`
`
`Found
`
`Not found
`
`
`
`Enumerate [Ivy]<$chmitd) 1ooking for
`X.Bcd of 1ABCDZS460ED
`
`
`
`
`
`Not found
`
`Enter in version map
`
`Compile X.Mesa with no parameters
`
`Enter X.Bcd of 1ABC0234GDED
`
`in projection table
`
`Object fi1e X.Bcd of 1ABCD234BDED exists
`
`FIG. 23
`
`Page 24 0f 58
`
`Page 24 of 58
`
`

`

`U.S. Patent Dec. 10,1985
`
`Sheet 23 on4 4,558,413
`
`
`Load XImp1.Bcd Of 2ADEF345EDCA
`
`
`
`
`
`
`
`Lookup in Version Map
`
`
`
`
`Found
`Not found
`
` Enumerate [Ivy]<$chm1dt>
`look for XImp1.Bcd 0F ZADFEZ45EDCA
`
`Not found
`
`
`
`
`Enter
`
`in Version map
`
`
`Read fi1e [Ivy]<Schmidt>XImp1.BcdlZZ and 1oad
`
`
`
`FIG. 24
`
`ReIease T001: Phase Move
`
`[Ivy]<Schmidt>X.Mesal4
`
`[Indigo]<Cedar>X.Mesa!2
`
`[Ivy]<$chmidt>XImp1.Mesalfi
`
`[Indigo]<Cedar>XImp1.Masala
`
`[Ivy]<Schmidt>Y.Mesal43
`
`[Indigo]<Cedar>Y.Mesat1
`
`[Indigo](Cedar>YImp1.Mesalz
`
`[Ivy]<Schmidt>YImp1.Mesa134
`
`FIG. 25
`
`Page 25 of 58
`
`Page 25 of 58
`
`

`

`US. Patent Dec. 10,1985
`
`Sheet 24 of24 4,558,413
`
`Re1ease Too]: Phase Build
`
`[Ivy]<$chmidt>X.Bcd123
`
`[Indigo]<Cedar>X.Bcd12
`
`[Ivy]<Schmidt>XImp1.Bcd122
`
`[Indigo]<Cedar>XImp1.Bcdll
`
`[Ivy]<Schmidt>Y.Bcd116
`
`[Indigo]<Cedar>Y.Bcd!1
`
`[Indigo]<Cedar>YImp1.Bcdiz
`
`[Ivy]<Schm1dt>YImp1.Bcdllz
`
`FIG. 26
`
`Version Map After Re1ease
`
`File Location
`
`[Indigo]<Cedar>YImp1.BcdlZ
`
`X.Mesa of July 25,1982 14:03:02
`
`[Indigo]<Cedar>X.MesalZ
`
`XImp1.Mesa of Ju1y 25.1982 14:05:06 [Indigo]<Cedar>XImp1.MesalS
`
`Y.Mesa of July 25,1982 15:05:08
`
`[Indigo]<Cedar>Y.Mesa11
`
`YImp1.Mesa of Ju1y 25,1932 15:07:03
`
`[Indigo]<Cedar>YImp1.Mesalz
`
`X.Bcd of 1ABCDZ34GDED
`
`[Indigo](Cedar>X.Bcd!2
`
`XImp1.Bcd of ZADEF345EDCA
`
`[Indigo]<Cedar>XImp1.Bcd!1
`
`Y.Bcd of 3421ABD4235A
`
`[Indigo]<Cedar)Y.Bcdll
`
`YImp1.Bcd of 2345583D0638
`
`FIG. 27
`
`Page 26 of 58
`
`Page 26 of 58
`
`

`

`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-
`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 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 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 converted. 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 447,000 lines of Cedar code, and approx-
`imately 2000 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
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`Page 27 of 58
`
`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
`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 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:
`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 as 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 Ian.
`guages,
`this fact reinforces the singularity of this re-
`search. The following is brief review of previous work
`in this area.
`
`(1) Make Program
`
`Page 27 of 58
`
`

`

`4,558,413
`
`xl.c
`
`5
`
`IO
`
`IS
`
`20
`
`25
`
`35
`
`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 node in the
`dependency graph, the Makefile contains a Make Rule,
`which is to be executed to produce a new version of the
`parent node if any of the son nodes change.
`For example the dependency graph illustrated in
`FIG. 1 shows that x1.o depends on x1.c, and the file
`a.out depends on xl.o and x2.c. The Makefile that rep-
`resents this graph is shown in Table I below.
`
` TABLE I
`abut:
`xl.o
`xl.o
`x2.o
`
`cc
`xl.o
`x2.c
`x1.c
`cc
`x2.c
`x2.c:
`
`—ccc x2.c
`
`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 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)
`In Table I, the expression, “cc-c xl.c” is the com-
`Make and SCCS were unified in special tools for a
`mand to execute and produce a new version of xl.o
`development project at Bell Labs called the Software
`when xl.c is changed. Make decides to execute the
`Manufacturing Facility (SMF) and discussed in the
`make rule i.e., compile xl.c, if the file modification time
`ofxl.c is newer than that of xl.o.
`Article of Eugene Cristofer, F. A. Wendt and B. C.
`Wonsiewicz, “Source Control & Tools=Stable Sys-
`The description mechanism shown in Table I is intu-
`tems", Proceedings of the Fourth Computer Software &
`itively easy to use and explain. The simple notion of
`dependency, as” a file xl.o, that depends on xl.c must 30 Applications Conference, pp. 527—532, Oct. 29-31, [980.
`The SMF uses Make and SCCS augmented by special
`be recompiled if xl.c is newer, works correctly vitually
`files called slists, which list desired versions of files by
`all the time. The Makefile can also be used as a place to
`their SCCS version number.
`keep useful commands the programmer might want to
`A slist may refer to other slists as well as files. In the
`execute, e. g.,
`SMF, a system consists of a master slist and references
`print:
`to a set of slists that describe subsystems. Each subsys-
`pr xl.c x2.c
`tem may in turn describe other subsystems or files that
`defines a name “print” that depends on no other files
`are part of the system. The SMF introduces the notion
`(names). The command “make print” will print the
`of a consistent software system: only one version of a
`source files xl.c and x2.c. There is usually only one
`file can be present in all slists that are part of the system.
`Makefile per directory, and, by convention, the soft-
`Part of the process of building a system is checking the
`ware in that directory is described by the Makefile. This
`consistency.
`makes it easy to examine unfamiliar directories simply
`SMF also requires that each slist refer to at least one
`by reading the Makefile.
`Makefile. Building a system involves (l) obtaining the
`Make is an extremely fast and versatile tool that has
`SCCS versions of each file, as described in each slists,
`become very popular among UNIX users. Unfortu-
`(2) performing the consistency check, (3) running the
`nately, Make uses modification times from the file sys-
`Make program on the version of the Makefile listed in
`tem to tell which files need to be re-made. These times
`the slist, and (4) moving files from this slist to an appro—
`are easily changed by accident and are a very crude
`priate directory. FIG. 2 shows an example of a hierar-
`way of establishing consistency. Often the programmer
`chy of slists, where ab.sl is the master slist.
`omits some of the dependencies in the dependency
`SMF includes a database of standard versions for
`graph, sometimes by choice. Thus, even if Make em-
`common files such as the system library. Use of SMF
`ployed a better algorithm to determine the consistency
`solves the problem created when more than one pro-
`of a system, the Makefile could still omit many impor-
`grammer is making changes to the software of a system
`tant files of a system.
`and no one knows exactly which files are included in
`(2) Source Code Control System (SCCS)
`the currently executing systems.
`The Source Code Control System (SCCS) manages
`(4) PIE Project
`versions of C source programs enforcing a check—in and
`The PIE project is an extension to Smalltalk devel-
`check-out regimen, controlling access to versions of
`oped at the Palo Alto Research Center of Xerox Corpo-
`ration and set forth in the Articles of Ira P. Goldstein
`programs being changed. For a description of such
`systems, see the Articles of Alan L. Glasser, “The Evo-
`and Daniel G. Bobrow, “A Layered Approach to Soft-
`lution of a Source Code Control System", Proc. Soft-
`ware Design”, Xerox PARC Technical Report CSL—80-5,
`December 1980; Ira P. Goldstein and Daniel G. Bo.
`ware Quality & Assurance Workshop, Software Engi-
`neering Notes, Vol. 3(5), pp. 122—125, November 1978;
`brow, “Descriptions for 3 Programming Environment”,
`Evan L. Ivie, "The Programmer’s Workbench-A Ma-
`Proceedings of the First Annual Conferenc