From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [50.116.15.146]) by inbox.vuxu.org (Postfix) with ESMTP id BCAEB3183B for ; Fri, 13 Dec 2024 19:49:52 +0100 (CET) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 69BA64272E; Sat, 14 Dec 2024 04:49:47 +1000 (AEST) Received: from mcvoy.com (mcvoy.com [192.169.23.250]) by minnie.tuhs.org (Postfix) with ESMTPS id CE4104272D for ; Sat, 14 Dec 2024 04:49:43 +1000 (AEST) Received: by mcvoy.com (Postfix, from userid 3546) id 4E4B135EA3F; Fri, 13 Dec 2024 10:49:43 -0800 (PST) Date: Fri, 13 Dec 2024 10:49:43 -0800 From: Larry McVoy To: Marc Rochkind Message-ID: <20241213184943.GX11590@mcvoy.com> References: <20241213180649.GW11590@mcvoy.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.24 (2015-08-30) Message-ID-Hash: ZCDAXBN4FCDBYXNPVXJMDNH4TAUFN6EF X-Message-ID-Hash: ZCDAXBN4FCDBYXNPVXJMDNH4TAUFN6EF X-MailFrom: lm@mcvoy.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-tuhs.tuhs.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: The UNIX Historical Society X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: SCCS roach motel List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: Yes, but note that when you see "^AcK" for varying values of "K", those are BitKeeper extensions to the file format. We figured out that SCCS treats "^Ac " the same whether there is a space or a character there. It was a way for us to add stuff to the file format where it would look weird when you printed the comments, but SCCS could, at least, read the BK file format. All of src-notes/ was true at some point but has almost certainly rotted. We wrote those as a way to get developers started in the right direction. The source code is the real reference. On Fri, Dec 13, 2024 at 11:39:03AM -0700, Marc Rochkind wrote: > Larry, I found this: > > https://www.bitkeeper.org/src-notes/SCCSWEAVE.html > > A good reference? > > Marc > > On Fri, Dec 13, 2024 at 11:32???AM Marc Rochkind wrote: > > > Larry, thanks for this. I had read some things you've written about the > > weave before, but not with this level of detail. Sounds weird, but I didn't > > really appreciate the implications of the weave even though I'm the guy who > > thought it up. I did understand the importance of not copying data if you > > can reference it, which is a principle of database design (normal forms, > > etc). > > > > In my paper, I can add a little more about the weave and its advantages. > > Aside from this TUHS post, is there something I can put in the References > > that people can find? > > > > Question: Is this right, that TeamWare was literally layered on top of > > AT&T SCCS, but BitKeeper was layered on your implementation of SCCS? Or, > > was it more complicated than that? > > > > Was your implementation of SCCS ever released by itself? > > > > Marc > > > > On Fri, Dec 13, 2024 at 11:06???AM Larry McVoy wrote: > > > >> 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 > >> > > > > > > -- > > *My new email address is mrochkind@gmail.com * > > > > > -- > *My new email address is mrochkind@gmail.com * -- --- Larry McVoy Retired to fishing http://www.mcvoy.com/lm/boat