United States Patent 15
`Schmidt et al.
`
`(11] Patent Number:
`[45] Date of Patent:
`
`4,558,413
`Dec. 10, 1985
`
`[54] SOFTWARE VERSION MANAGEMENT
`SYSTEM
`
`[75]
`
`Inventors: Eric E, Schmidt, Los Altos, Calif.;
`Butler W. Lampson, Philadelphia, Pa.
`[73] Assignee: Xerox Corporation, Stamford, Conn.
`[21] Appl. No.: 553,724
`{22] Filed:
`Nov.21, 1983
`
`[S21]
`Tint, Ch.8 cc cceeeeeeneseeetseeeeseeenenes GO6F 15/20
`[52] U.S. Ch. on.eee eeeteeerertereeee
`.. 364/300; 364/200
`(58] Field of Search ............:.c:sscceecereetneees 364/300
`(56]
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,309,756
`
`1/1982 Beckler .........ccseeeeeeeee 364/300
`
`OTHER PUBLICATIONS
`
`Morse et al., DOS/AMAP Model of the DOS Control
`Program, £.B.M. Technical Disclosure Bulletin, vol. 14,
`No. 3, Aug. 1971, pp. 852-853.
`Alan L. Glasser, “The Evolution of a Source Code
`Control System”, Proc. Software Quality and Assur-
`ance Workshop, Software Engineering Notes, vol. 3,
`No. 5 pp. 122-125, Nov. 1978.
`Ira P. Goldstein & Daniel G. Bobrow, “Representing
`Design Alternatives”, Proceedings of the Artificial
`Intelligence and Simulation of Behavior Conference,
`Amsterdam, Jul. 1980.
`Raul
`Ellison,
`Robert
`A.
`Nico Habermann,
`Medina—Mora, Peter Feiler, David S. Notkin, Gail E.
`Kaiser, David B. Garlan & Steven Popovich, “The
`Second Compendium of Gandall Documentation”
`CMUDepartmentof Computer Science, May 24, 1982.
`Gail E. Kaiser & A. Nico Habermann, “An Environ-
`mentfor System Version Control” in The Second Com-
`pendium of Gandalf Documentation, CMU Department
`of Computer Science, Feb. 4, 1982.
`B. W. Lampsonet 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 a Revision Control System”, Proceedings of the 6th
`International Conference on Software Engineering,
`Tokyo, Japan, Sep. 1982.
`
`Dissertation of Eric Emerson Schmidt, entitled “Con-
`trolling Large Software 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 Parc. Tech.
`Report, CSL-80-5, Dec. 1980.
`James G. Mitchell et al., “Mesa Language Manual,
`Version 5.0” Xerox Parc. Tech. Report, CSL-79-3,
`Apr. 1979.
`
`(List continued on next page.)
`
`Primary Examiner—Raulfe B. Zache
`Attorney, Agent, or Firm—W. Douglas Carothers, Jr.
`[57]
`ABSTRACT
`A software version management system, also called
`system modeller, provides for automatically collecting
`and recompiling updated versions of componentsoft-
`ware objects comprising a software program for opera-
`tion on a plurality of personal computers coupled to-
`gether in a distributed software environment via a local
`area network. The componentsoftware 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 nameofthe
`object, a unique identifier descriptive of the cronologi-
`cal updating ofits current version, informationas 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 | 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. 308-317, Jun.
`23-25, 1982.
`Lee W. Cooprider, The Representation of Families of
`Software Systems, Ph.D Thesis, CMU Computer Sci-
`ence Department, CMU-CS-79-116, Apr. 14, 1979.
`Eugene Cristofor, T. A. Wendt & B. C. Wonsiewicz,
`“Source Control+Tools=Stable Systems”, Proceed-
`ings of the Fourth Computer Software and Applica-
`tions Conference, pp. 527-532, Oct. 29-31, 1980.
`A. Demers & J. Dononhue, “Data Types, Parameters,
`and Type Checking”, Proceedings of the Seventh Sym-
`posium on Principles of Programming Languages, Las
`Vegas, Nevada, pp. 12-23, 1980.
`Frank DeRemer & H. Kron,
`“Programming-in—-
`the-Large Versus Programming-in-the-Smail”, IEEE
`Transactions on Software Engineering, vol. 2, No. 2,
`pp. 80-86, Jun. 1976.
`Stuart I. Feldman, ““Make-A Program for Maintaining
`Computer Programs”, Software Practice and Experi-
`ence, vol. 9, No. 4, pp. 255-256, Apr. 1979.
`Ira P. Goldstein & Daniel G. Bobrow, “Descriptions
`for a Programming Environment”, Proceedings of the
`
`First Annual Conferenceofthe 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-80-120,Jan.
`1980.
`
`Page 2 of 58
`
`Page 2 of 58
`
`

`

`U.S. Patent Dec.10, 1985
`
`Sheet 1 of24
`
`4,558,413
`
`ab.sl
`
`ab.s1
`
`a.$]
`
`b.s]
`
`3.6
`
`4.7
`
`2.3
`
`
`Makefile 4.9 4.7
`
`2.3
`
`b.s]
`
`
`
`3.6
`
`
`Makefile 3.5
`Makefile 4.5
`
`1.2
`
`x2.0
`
`x2.c
`
`1.3
`
`1.4
`
`PRIOR ART
`
`FIG. 2
`
`Page 3 of 58
`
`Page 3 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet2 0f24
`
`4,558,413
`
`
`
`
`
`
`Composition C1
`
`
`Other modules and boxes
`
`Other modules and boxes
`
`Version 2(std)
`
`Other modules
`
`PRIOR
`
`ART
`
`FIG. 3
`
`Configuration Object File
`
`a4
`
`Source File
`
`Implementation Object Files
`
`Source File
`
`Object files for Interfaces
`
`FIG. 6
`
`Page 4 of 58
`
`Page 4 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 3 0f24
`
`4,558,413
`
`
`
`Client:PROGRAM IMPORTS SqrtInt =
`pee eo eee
`
`phe ee oe
`
`..code to compute sqrt of a number
`
`
`
`}3
`
`{
`
`
`Implementor:
`PROGRAM EXPORTS SqrtInt ={
`
`
`
`Sqrt: PUBLIC PROC(s: REAL ]JRETURN[REAL ]={
`
`
` SqrtInt:DEFINITIONS = {
`
`
`
`Sqrt: PROC[REAL ]RETURNS[ REAL];
`
`
`eee ener
`
`}.
`
`FIG. 4
`
`Impelementation object file
`
`od
`
`Source file
`
`Object files for interfaces
`
`FIG. 5
`
`Page 5 of 58
`
`Page 5 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 4 of24
`
`4,558,413
`
`
`
`
`Personal
`Storage
`
`Computer
`Disk
`
`
`
`
`
`
`
`[centeteee}
`Server
`[—|
`
`
`Computer
`
`
`Personal
` 10
`
`Computer
`
`To other networks
`
`
`40~{
`
`Personal
`Computer
`
`FIG. 7
`
`Page 6 of 58
`
`Page 6 of 58
`
`

`

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

`

`U.S. Patent Dec. 10, 1985
`
`Sheet60f24
`
`4,558,413
`
`FileTool.DF
`
`
`UserExec.DF BBV.OF
`
`TTYIO.DF
`
`BugBane.DF
`
`ViewersAndTioga.DF
`
`PriorityQuene.DF
`
`ColorPackage.DF Qn1ineMergeSort.DF
`
`CedarControl.DF
`
`MesaScanner.DF
`Graphics .DF
`Inscript.OF
`Rigg ingMaker . DF
`
`SpecialBringOver.DF
`
`IO.DF, WorldVM.DF,
`Runtime.OF,
`ListsAndAtoms.DF, CIFS.ODF
`
`RPCRuntime.DF
`
`DateAndT ime. DF
`
`GrapevineUser.DF|CedarSnapshot.DF
`
`
`
`
`\_
`
`
`
`
`
`
`
`
`
`_DF TerminalMultiples.DF
`Random.DF
`sDF
`cmtDF
` certorracksDF
`
`
`
`
`
`
`
`
`
`Pine. DF CedarReals.DF|BasicHeads*.DF CFW.DF
`
`BTrees.DF
`
`FTP.DF
`
`Bcd.DF
`
`FIG. 9
`
`Page 8 of 58
`
`Page 8 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 7 0f24
`
`4,558,413
`
`
`
`I0.DF, World.DF, VersionMap.DF,
`Runtime.DF,
`ListsAndAtoms.DF, CIFS.DF
`
`
`
`stands for
`
`CIFS.DF
`
`10. DF
`
`
`
`
`ListsAndAtoms.DF
`
`Runtime .DF <<—————— Wor 1d VM. DF
`
`VistonMap.DF
`
`FIG. 10
`
`Page 9 of 58
`
`Page 9 of 58
`
`

`

`
`BBY.DFwortDFTTYIO.DFaDF
`“—TDF
`wat[ UserExec.DF
`
`te 4DF BugBane.DF
`foueDF ListsAndAtoms .DF
`
`
`Inscript.DF
`
`
`Runtime.DF— WorldVM.D
`
`
` VisionMap.DF
`
`Loader .0F
`
`CIFS.DF
`RPCRuntime.DF
`
`
`
`GrapevineUser .DF
`
`
`SpecialBring
`Over .DF
`
`Rigging.DOF
`
`Cedar
`FTP.DF Bed.DF Control.DF
`
`U.S. Patent Dee. 10, 1985
`
`Sheet80f24
`
`4,558,413
`
`MesaScanner.DF
`
`
`
`
`
`
`
`CedarSnapshot.OF
`DateAndT ime. DF
`
`BasicHeads*.DF
`
` PilotInterfaces.DF
`
`PriorityQueue.DF
`
`Communication*.DF
`
`TerminalMultiplex.DF
`
`CompatibilityPackage.DF
`
`CedarReals.DF
`
`BTrees .DF
`
`FIG. 11
`
`Page 10 of 58
`
`Page 10 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet9 of 24
`
`4,558,413
`
`VisionMapBuilder.DF
`
`UECP.DF
`
`
`Chat.DF
`
`CIFSCommands .DF
`
`
`DFFiles.DF
`
`i —— i
`Sequin.DF
`TFSFI1e.DF wogeller.DF
`
`Boot
`
`File
`
`Compiler.DF
`
`Binder .DF
`Lister .DF
`
`Packager .DF
`PGS .DF
`PressPackage.DF “——Print.DF
`PerfStats.DF ~———CedarDB.DF
`
`CoFork.DF ~————PlotPackage. DF
`Spy .DF ~———————— Lupine. DF
`
`SirPress.DF ~————PressScreen.df
`
`BrovoToTioga.DF
`CedarRealTest.DF
`
`InciudeChecker .DF
`
`Maintain.DF
`
`MakeBoot.DF
`
`MCross .DF
`
`Othello*.DF
`
`PupWatch.DF
`
`RedBiackTreeRef .DF
`
`Set.DF
`
`STPServer.DF
`
`TJamGraphics.DF
`
`Unique .DF
`WalnutSend.DF
`
`RedBlack
`Tree.DF
`
`WaterLily.DF
`
`FIG. 12
`
`Page 11 of 58
`
`Page 11 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 10 of24 4,558,413
`
`Clientimp1.Mesa
`
`DIRECTORY
`
`Sort;
`
`Clientmp1:PROGRAM IMPORTS Sorte{
`
`TestThem:PROCLI:LIST OF ObjectJ={
`
`--call USortList with this list
`
`IT¢+Sort.USortList[1,CompareObject];
`
`};
`
`CompareObject:PROC[a,b:O0bject]
`
`RETURNS[Compar ison ]={
`--compares the two objects
`
`~-returns less, equal, or greater }:
`
`FROM
`FIG.
`13B
`
`Sort.Mesa
`
`Sort: DEFINITIONS={
`
`Object: TYPE=RECORD[
`
`x,y: INT
`
`};
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`RETURNS[LIST OF Object];
`
`FIG. 13A
`
`Page 12 of 58
`
`Page 12 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 11 of 24 4,558,413
`
`SortImp].Mesa
`
`DIRECTORY
`
`Sort;
`
`Sortimp1:PROGRAM EXPORTS Sort={
`
`USortList:PROC[I:LIST OF Object,
`
`}:
`
`compareProc: CompareProc]
`
`RETURNS[newl:LIST OF Object]*{
`
`--code to sort the list I,
`
`eliminating duplicates
`
`JO FIG.
`
`13A
`
`FIG. 13B
`
`Page 13 of 58
`
`Page 13 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 12 of 24 4,558,413
`
`SortCoord.Mesa
`
`Sort: DEFINITIONS={
`
`Object: TYPE=RECORD[E
`
`xX, yt INT
`
`3;
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`RETURNS[LIST OF Object];
`RETURNS[LIST OF Object];
`
`SortNames.Mesa
`
`Sort: DEFINITIONS={
`
`Object: TYPE=RECORD[
`
`x:STRING
`
`];
`
`USortList:PROC[LIST OF Object, CompareProc]
`
`FIG. 14
`
`Page 14 of 58
`
`Page 14 of 58
`
`

`

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

`

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

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 15 of24 4,558,413
`
`ClientImp1].Mesa
`
`DIRECTORY
`
`SortCoord: INTERFACE Sort,
`
`SortNames: INTERFACE Sort;
`
`--compares a and b, returns less, equal, or greater
`
`ClientImp1:PROGRAM IMPORTS SortQuickCoordInst:SortCoord,
`
`SortQuickNamesInst: SortNames, SortHeapCoordInst:SortCoord,
`
`SortHeapNamesInst={
`
`TestThem:PROC[I1:LIST OF SortCoord.Object,I2:LIST OF SortNames.Object]={
`
`newI+SortQuickCoordInst.USortList[I1, CompareCoordinateObjects];
`
`newl+SortHeapCoordInst.USurtList[I1, CompareCoordinateObjects);
`
`newl+SortQuickNamesInst .USortList{I2, CompareNameObjects},
`
`newl+SortHeapNamesInst.USortList[I2, CompareNamesObjects];
`
`}:
`
`CompareCoord inateOb jects: PROC[a,b: 7SortCoord. Object JRETURNS[Comparison]={
`
`--compares a and b, returns less, equal, or greater
`
`}3
`
`CompareNameOb jects: PROC([a,6:SortNames. Ob ject JRETURNS[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!(Jan 14, 1983, 14:44:11}
`
`LET @[Indigo}<Cedar>Cedarinsiaces.modell{July 25, 1982, 14:03:03)IN
`
`LETinstances~ @[Indigo}<Cedar>Cegar Instandes.model|(July 25, 1982, 14:10:12)IN
`
`8Tree:INTERFACE 8Tree~ @[Ivy]<Schmidt87ree. cedar!(Sept 9,1982, 13:52:55)
`
`[Asciij,
`
`BTreelnst: BTree~ @[Ivy]<Schmict>87ree/mp).cedar!(Jan 14, 1983, 14:44:09)
`
`*[] [instances. Rope, instances./O, instances.Space] } }
`
`CedarInterfaces.model!(July, 25, 1982, 14:03:03)
`
`[
`
`Ascii:INTERFACE~ @{Indigo}<Cedar>Ascii.cedar!(July 10, 1982, 12:25:00)(],
`
`Rope:INTERFACE ~ @[Indigo]<Cedar>Rape.cedar!(July 10, 1982, 17:00:00)*[]j,
`
`lO:INTERFACE ~ @[Indigo}<CedarriO.cedar!(July 12, 1982, 11:00:00) *[],
`
`Space:INTERFACE ~ @[Indigo]<Cedar>Space.Cedar!(June 10, 1982, 8:35:00)*[] ]
`
`Cedarinstances.model!(July 25, 1982, 14:10:12)
`
`{Ascii, Rope, 10, Space]~
`
`LET @Cedarinterface.model!(July 25, 1982, 14:03:03)IN [
`
`@[indigo}<Cedar>Asciiimp!.cedar!(July 10, 1982, 12:30:00)[][],
`
`@[Indigo}<Cedat>Ropeimpi.cedati{July 10, 1982, 17:10:24)*f]* (],
`
`@[!ndigo}<Cedar>/O/mpl.cedar!(July 20, 1982, 13:03:03) °()*[],
`
`@[Indigo}<Cedar>Space.cedar!(June 11, 1982, 15:00:00) *{]*{} }
`
`FIG. 17
`
`Page 18 of 58
`
`Page 18 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 17 of24 4,558,413
`
`Object type table
`
`
`Source object
`Type
`
`
`8Tree.Cedarl(Sept 9, 1982, 13:52:55)
`
`(INTERFACEAsceii]- [INTERFACES Tree]
`
`8Treeimpi.cedar!(Jan 9, 1983, 14:44:09)
`
`{[Rope:INTERFACERope, /O,Space:INTERFACE Space,
`
`BTree:INTERFACE8 Tree}
`
`([Ropelnst:Rope, !0, Spaceinst:Space} ([BTreeinst:
`BTree]j
`
`Projection table
`
`Source object
`Parameter values
`Results object
`
`
`BTree,cedar!(Sept 9.1982,
`13:52:55)
`
`[Ascii.binary!23ACD904EFFA]
`
`BTree. binary!43956A3C3I2F0
`
`BTreeimpl.cedar'(Jan 14, 1983,
`14:44:09)
`
`[Rope. binary!AC9O23E76FA6,
`10. binary!$23843396A24f,
`
`BTreelmpl.binary!2045FFD283C
`
`Space. binary!8348823FF761,
`BTree. binary!43956A3C32F0]
`
`
`FIG. 18
`
`Page 19 of 58
`
`Page 19 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 18 of 24 4,558,413
`
`Version map
`SR
`
`Object name
`File location
`
`
`BTree.cedar!(Sept 9, 1982, 13:52:55)
`
`[lvy]<Schmidt>BTree.cedar4
`
`BTree.impl.cedar!(Jan 14,1983, 14:44:09)
`
`[lvy]<Schmidt>BTreelmpl.cedar!9
`
`BTree. binary!43Q56A3C32F0
`
`{lvy]<Schmidt>BTree.binary!2
`
`BTreeimpl.binary!2045FFD283C
`
`{lvy]}<Schmidt>BTreeimpl.binary!5
`
`[Indigo]<Cedar>Ascii.binary23
`Ascii.binary!\23ACDSO04EFFA
`
`
`FIG. 19
`
`Page 20 of 58
`
`Page 20 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 19 of 24 4,558,413
`
`
`
`Cedar Modeller, started on 3-Feb-83 16:16:01 PST
`
`
`
`
`
`StoreBack Unload StopModel
`StartModelBegin Continue
`MakeModelBcd Bind
`NewModeller
`Compile Load Start
`
`
`
`
`ModelName: Example,Model
`
`
`Compiling: ExampleImplA.Mesa .... no errors.
`Compiling: ExampleImp18.Mesa ...
`
`
`
`StarModel Example.Model
`Prasing Example.Model
`Analyzing Parameters
`
`
`
`
`
`
`
`
`
`Begin Example.Model
`Try for compilation:
`
`ExampleImplA.Mesa:Confirm Compilation ? Yes
`Compilation completed, no errors.
`ExampleImp1B.Mesa: Confirm Compilation 7? Yes
`
`
`
`
`
`
`
`LL
`
`
`
`
`FIG. 20
`
`30
`
`32
`
`34
`
`36
`
`4
`
`
`
`Page 21 of 58
`
`Page 21 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 20 of 24 4,558,413
`
`StartModel
`
`User Edits Files
`
`Notice Operation
`
`User Test Program
`
`User Edits Files
`
`Notice Operation
`
`i]Fails
`
`Succeeds
`
`StoreBack
`
`FIG. 21
`
`Page 22 of 58
`
`Page 22 of 58
`
`

`

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

`

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

`

`U.S. Patent Dec.10, 1985
`
`Sheet 23 of24 4,558,413
`
`
`
`
`Load XImp1.Bcd Of 2ADEF345EDCA
`
`
`
`Lookup in Version Map
`
`
`
`
`
`
`
` Enumerate [Ivy]}<Schmidt>
`
`look for XImp1.Bcd OF 2ADFE245EDCA
`
`Found
`
`Not found
`
`Not found
`
`
`
`Enter
`
`in Version map
`
`Read file [Ivy]<Schmidt>XImp1.Bcd!22 and load
`
`FIG. 24
`
`
`
`Release Tool: Phase Move
`
`[Ivy ]<Schmidt>X.Mesal 4
`
`[indigo ]<Cedar>X.Mesal2
`
`[Ivy]<Schmidt>XImp1.Mesal6
`
`[Indigo]<Cedar>XImp1.Mesal3
`
`[Ivy]<Schmidt>Y¥.Mesa!l43
`
`[Indigo]<Cedar>¥.Mesall
`
`[Indigo]<Cedar>YImp1.Mesal2
`
`[ivy]<Schmidt>YImp?.Mesala4
`
`FIG. 25
`
`Page 25 of 58
`
`Page 25 of 58
`
`

`

`U.S. Patent Dec. 10, 1985
`
`Sheet 24 of 24 4,558,413
`
`Release Tool: Phase Build
`
`[ivy]<Schmidt>X.Bed!23
`
`[Indigo]<Cedar>X.Bedl2
`
`[ivy]<Schmidt>XIimp1.Bed!22
`
`[Indigo]<Cedar>XImp1.B8cd!1
`
`[Ivy ]<Schmidt>Y.Bed!16
`
`Cindigo}<Cedar>Y.Bed!1
`
`[Indigo]<Cedar>YImp}.Bed!2
`
`[ivy ]<Schmidt>YImp1].Bed!12
`
`FIG. 26
`
`Version Map After Release
`
`File Location
`
`[Indigo]<Cedar>Y¥Imp1.Bcd!2
`
`X.Mesa of July 26,1982 14:03:02
`
`[Indigo]<Cedar>X.Mesa!2
`
`XImp1.Mesa of July 26,1982 14:06:06}
`
`[Indigo}<Cedar>XImp1.Mesal3
`
`Y.Mesa of July 25,1982 18:05:08
`
`[Indigo]}<Cedar>Y.Mesal1
`
`YImp].Mesa of July 25,1962 16:07:03]
`
`[Indigo]<Cedar>YImp1.Mesa!2
`
`X.Bcd of 1ABCD2346DED
`
`[Indigo]<Cedar>X.Bed!2
`
`XImp1.Bcd of 2ADEF345E0CA
`
`[Indigo]<Cedar>XImp1.Bcd!1
`
`Y.Bed of 3421ABD4235A
`
`[Indigo]<Cedar>Y.Bcd!1
`
`YImp?.Bcd of 23455BBDC63B
`
`FIG. 27
`
`Page 26 of 58
`
`Page 26 of 58
`
`

`

`1
`
`4,558,413
`
`2
`same version of that file. Cedar is too large to store all
`Cedar software onthefile system of each programmer’s
`machine, so each Cedar programmer has to explicitly
`retrieve the versions he needs to run his system from
`remote storagefacilities or file servers.
`Thus, the problem falls in the realm of “Program-
`ming-the-Large” wherein the unit of discourses the
`software module,
`instead of
`‘“Programming-in-the-
`Small’, where units include 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 managementofversions 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
`kindsof 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 mustbe identified. It must be possible to
`compute whichfiles 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 whenit is run.
`3. Interface Information: In languages that require
`explicit delineation of interconnections between mod-
`ules (e.g. Mesa, Ada), there must be means to express
`these interconnections.
`There has beenlittle research in version control and
`automatic software management. 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 systemsavailable
`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
`
`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 modulein 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 manyplaces 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
`programmerare the versions intended to be used.
`A programmer unfamiliar with the composition of
`the program is more likely to make mistakes when a
`simple change is made. Giving this new 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 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 ofa soft-
`ware system can have far-reaching effects. There is
`often confusion about the number of modules affected
`and howto rebuild affected pieces. For example, user-
`visible changes to heavily-used parts of an operating
`system are made very seldom and only at great cost,
`since other programsthat 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 versionsinstalled 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 numberofrefer-
`ences to modules that must agree in version, and the
`need for explicit file movement between computers.
`For example, a programming environment and system
`used at the Palo Alto Research Center of Xerox Corpo-
`ration at Palo Alto, Calif., called “Cedar” now has
`approximately 447,000 lines of Cedar code, and approx-
`imately 2000 source and 2000 object files. Almost all
`binary or object files refer to other binary or objectfiles
`by explicit version stamp. A program will not run until
`all references to an binary or object file refer to the
`
`25
`
`35
`
`40
`
`45
`
`55
`
`Page 27 of 58
`
`Page 27 of 58
`
`

`

`3
`The Make program,discussed in the Article of Stuart
`J. Feldman, “Make-A Program for Maintaining Com-
`puter Programs”, Software Practice & Experience, Vol. 9
`(4), April, 1979, uses a system description called the
`Makefile, which lists an acyclic dependency graph ex-
`plicitly given by the programmer. For each nodein the
`dependency graph, the Makefile contains a Make Rule,
`whichis to be executed to produce a new version of the
`parent node if any of the son nodes change.
`For example the dependency graph illustrated in
`FIG. 1 shows that x1.0 depends on x1.c, and thefile
`a.out depends on x1.0 and 22.0. The Makefile that rep-
`resents this graph is shown in Table I below.
`TABLEI
`xl.o
`ce
`xLe
`ce
`x2.c
`x2.0
`
`—c¢ce x2.c
`
`a.out:
`
`x1.0:
`
`x2.0
`x2.0
`
`xlc
`
`xl.o
`xlo
`
`—¢
`
`
`
`4,558,413
`
`4
`IEEE Transactions on Software Engineering, Vol. 1(4),
`pp. 25-34, April 1981.
`A programmer who wants to change a file under
`SCCScontrol 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 changesare 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 madeas part of “delta 2.3". While the program-
`merhas “checked-out” the file, no other programmers
`may store new deltas. Other programmers may obtain
`copies of thefile for reading, however. SCCS requires
`that there be only one modification ofa file at a time.
`There is much evidence this is a useful restriction in
`multi-person projects. See Glasser, Supra. SCCSstores
`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 (SMF)
`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=Stable Sys-
`tems”, Proceedings of the Fourth Computer Software &
`Applications Conference, pp. 527-532, Oct. 29-31, 1980.
`The SMF uses Make and SCCS augmentedbyspecial
`files called slists, which list desired versions offiles by
`their SCCS version number.
`A slist may refer to otherslists as well as files. In the
`SMF,a system consists of a masterslist and references
`to a set of slists that describe subsystems. Each subsys-
`tem may in turn describe other subsystemsorfiles that
`are part of the system. The SMFintroduces the notion
`of a consistent software system: only one version of a
`file can be presentin all slists that are part of the system.
`Part of the process of building a system is checking the
`consistency.
`SMFalso requires that eachslist refer to at least one
`Makefile. Building a system involves (1) obtaining the
`SCCSversions of each file, as described in eachslists,
`(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 ofslists, where ab.sl is the masterslist.
`SMFincludes 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-
`grammeris making changesto 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 Approachto Soft-
`ware Design”, Xerox PARC Technical Report CSL-80-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-
`tional Association of Artificial Intelligence, Stanford,
`Calif., August 1980; Ira P. Goldstein and Daniel G.
`Bobrow,“Representing Design Alternatives”, Proceed-
`
`0
`
`20
`
`35
`
`45
`
`35
`
`65
`
`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
`makerule i.e., compile x1.c,if the file modification time
`of x1.c is newer than that of x1.o.
`The description mechanism shownin Table I is intu-
`itively easy to use and explain. The simple notion of
`dependency,e.g., a file x1.o, that depends on xl.c must
`be recompiled if x1.c is newer, works correctly vitually
`all the time. The Makefile can also be used as a place to
`‘keep useful commands the programmer might want to
`execute, €.g.,
`print:
`pr xl.c x2.c
`defines a name “print” that depends on no otherfiles
`(names). The command “make print” will print the
`source files xi.c and x2.c. There is usually only one
`Makefile per directory, and, by convention, the soft-
`warein that directory is described by the Makefile. This
`makes it easy to examine unfamiliar directories simply
`by reading the Makefile.
`Makeis an extremely fast and versatile tool that has
`become very popular among UNIX users. Unfortu-
`nately, Make uses modification times from thefile sys-
`tem to tell which files need to be re-made. These times
`are easily changed by accident and are a very crude
`way ofestablishing consistency. Often the programmer
`omits some of the dependencies in the dependency
`graph, sometimes by choice. Thus, even if Make em-
`ployed a better algorithm to determine the consistency
`of a system, the Makefile could still omit many impor-
`tant files of a system.
`(2) Source Code Control System (SCCS)
`The Source Code Control System (SCCS) manages
`versions of C source programsenforcing a check-in and
`check-out regimen, controlling access to versions of
`programs being changed. For a description of such
`systems, see the Articles of Alan L. Glasser, ‘The Evo-
`lution of a Source Code Control System”, Proc. Soft-
`ware Quality & Assurance Workshop, Software Engi-
`neering Notes, Vo