Larry McVoy
lm at mcvoy.com
Sat Dec 14 04:06:49 AEST 2024
On Fri, Dec 13, 2024 at 09:52:28AM -0700, Marc Rochkind wrote: > IEEE Transactions on Software Engineering has asked me to write a > retrospective on the influence of SCCS over the last 50 years, as my SCCS > paper was published in 1975. They consider it one of the most influential > papers from TSE's first decade. > > There's a funny quote from Ken Thompson that circulates from time-to-time: > > "SCCS, the source motel! Programs check in and never check out!" > > But nobody seems to know what it means exactly. As part of my research, I > asked Ken what the quote meant, sunce I wanted to include it. He explained > that it refers to SCCS storing binary data in its repository file, > preventing UNIX text tools from operating on the file. > > Of course, this is only one of SCCS's many weaknesses. If you have anything > funny about any of the others, post it here. I already have all the boring > usual stuff (e.g., long-term locks, file-oriented, no merging). Warning, I know more about SCCS than the average person, I've reimplemented it from scratch and then built BitKeeper on top of an extended SCCS file format. So lots of info coming. Rick Smith and Wayne Scott know as much as I do, Rick knows more, he joined me and promptly started fixing my SCCS implementation. So far as I know, there is not a more knowledgable person that Rick when it comes to weave file formats. SCCS's strength is the weave format. It's largely not understood, even by other people working in source management. Here's the benefit of that weave (if people use it, which, other than BitKeeper, they don't, looking at you, Clearcase, you had a weave and didn't use it): SCCS can pass merge data by reference, everyone else copies the data. SCCS is a set based system. Each node has a revision number, like 1.5, but because SCCS, unlike RCS, limited the revisions to at most 4 fields, like 1.5.1.1, it is _impossible_ to build the history graph from the revisions, you can in simple graphs but as soon as you branch from a branch, all bets are off. The graph is built from what BitKeeper called serial numbers. Each node in the graph has at least 2 serials, one that names that node in the graph, and one that is the parent. So if I have a file with 5 revisions in straight line history, the internal stuff will look something like rev me parent 1.5 5 4 1.4 4 3 1.3 3 2 1.2 2 1 1.1 1 0 So what's the set? Pretty simple for straight line history, you walk the history from the rev that you want, adding the "me" serial and going to the parent, repeat until the parent is 0. Suppose you branch from rev 1.3. rev me parent 1.3.1.1 6 3 1.5 5 4 1.4 4 3 1.3 3 2 ... See that 1.3.1.1 is me: 6 and parent: 3. So if I were building the set for 1.3.1.1, it becomes 6, then go to parent 3, 2, 1, skipping over 5 and 4. If you understand that, you are starting to understand the set and how it is constructed. Did you know you can have an argument in the revision history without adding anything to the data part? SCCS has the ability to include and/or exclude serials as part of a delta. Lets say Marc looked at my 1.5 and thought it was garbage. He can exclude it from the set like so: rev me parent include exclude 1.6 7 5 0 5 1.3.1.1 6 3 1.5 5 4 1.4 4 3 1.3 3 2 ... That doesn't change the data part of the file AT ALL, it's just saying Marc doesn't want anyone to see the 1.5 changes. To understand that, you need to know how SCCS checks out a file. And you need to know how the data is stored. Which is in a weave. RCS, and pretty much everything that followed it, doesn't use a weave at all. RCS stores the most recent version of the file as a complete copy of the checked out file. Then each delta working backwards up the trunk is a patch, what diff produces. Think about what that means for working on a branch. You have to start with the most recent version of the file, apply backward patches to go to earlier versions all the way back to the branch point, then apply forward patches to work your way to tip of the branch. Ask Dave Miller how pleasant it is to work on gcc on a branch. It's crazy slow and painful. So how does SCCS do it? Lets say the first version of a file is 1 2 3 4 5 The data portion of the history file will look like: ^AI 1 1 2 3 4 5 ^AE 1 SCCS used ^A at the beginning of a line to mean "this is metadata for SCCS". ^AI is an insert, ^AD is a delete, and insert/delete are paired with a ^AE which means end. The number after is the serial. So that weave says "If serial 1 is in your set, everything after ^AI 1 is part of that set until you hit the matching ^AE 1. Lets say the 2nd version is 1 2 serial 2 added this 3 4 Notice that serial 2 deleted what was line 5. ^AI 1 1 2 ^AI 2 serial 2 added this ^AE 2 3 4 ^AD 2 5 ^AE 2 ^AE 1 So now we can start to see how you walk the weave. If I'm trying to check out 1.1 aka serial 1, I build a set that has only '1' in the set. I hit the ^AI 1 see that I have 1 in my set, so I'm now in print mode, which means print each data line. I hit ^AI 2, that's not in my set, so I'm now in skip mode. And I skip the stuff inserted by serial 2. I see the ^AE 2 and I revert back to print mode. I get to ^AD 2, 2 is NOT in my set, so I stay in print mode. Etc. Let's make a branch, 1.1.1.1, with lots of data. 1 2 3 branch line 1 branch line 2 ... branch line 10000 4 5 ^AI 1 1 2 ^AI 2 serial 2 added this ^AE 2 3 ^AI 3 branch line 1 branch line 2 ... branch line 10000 ^AE 3 4 ^AD 2 5 ^AE 2 ^AE 1 So if I checked out 1.1.1.1, the set is 1, 3, I walk the weave and I'll print anything inserted by either of those, delete anything deleted by those, skip anything inserted by anything not in the set, skip any deletes by anything not in the set. The delta table looks like this, notice I've added an author column: rev me parent include exclude author 1.1.1.1 3 1 lm 1.2 2 1 lm 1.1 1 0 lm If you followed all that, you can see how SCCS can merge by reference. Lets say Clem decides to merge my branch onto the trunk. The delta table will get a new entry: rev me parent include exclude author 1.3 4 2 3 clem 1.1.1.1 3 1 lm 1.2 2 1 lm 1.1 1 0 lm The weave DOES NOT CHANGE. That's the pass by reference. You do the 3 way merge, it will find the lines "3" and "5" as anchor points in both versions, so it is a simple insert with no new data added to the weave. Here's some magic that *everyone* else gets wrong when they pass by value: In a system that passes by value (copies) the data, the merge done by clem would have an annotated listing like so: lm 1 lm 2 lm 3 clem branch line 1 clem branch line 2 clem ... clem branch line 10000 lm 4 lm 5 Since it copied the data, it looks like Clem wrote it but he didn't, he just automerged it. In SCCS/BitKeeper it would look like: lm 1 lm 2 lm 3 lm branch line 1 lm branch line 2 lm ... lm branch line 10000 lm 4 lm 5 which is correct, all of those lines were authored by one person. The only time the merger should show up as an author is if there was a conflict, however the merger resolved that conflict is new work and should be authored by the merger. What BitKeeper did, that was a profound step forward, was make the idea of a repository a formal thing and introduced the concept of changesets that keeps track of all this stuff at the repository level. So it does all this stuff at the file level but you don't have to do that low level work. You could think of SCCS as assembly and BitKeeper as more like C, it upleveled things to the point that humans can manage the repository easily. Whew. That's a butt load of info. Perhaps better for COFF? Any questions? It should be obvious that I *love* SCCS, it's a dramatically better file format than a patch based one, you can get *any* version of the file in constant time, authorship can be preserved across versions, it's pretty brilliant and I consider myself blessed to be posting this in response to SCCS's creator. Hats off to Marc. And big boo, hiss, to the RCS guy, who got a PhD for RCS (give me a break) and did the world a huge disservice by bad mouthing SCCS so he could promote RCS. --lm
