Chris X Edwards

In previous posts I introduced SnowC and explained how it works and what challenges had to be overcome. In this post let’s look at SnowC in action and see what it’s capable of.

Recall that the most challenging project goal was to be able to convert wild C source code into sensible SnowC. That was phase one. Phase two was relatively easy, just following the SnowC rules to convert SnowC back to C. Let’s have a closer look at phase three which was to get both of these programs working well enough that the SnowC conversion programs' source code themselves could be both converted.

We can start by downloading the SnowC project from…

https://xed.ch/project/snowc/snowc.tgz

Here is a good way to get to a directory with the SnowC source code.

To test the round trip conversions, I’ve created a script. The script is pretty illustrative and kind of interesting in a mind bending kind of way, but you can also ignore its details and skip ahead to just focus on the big picture.

Basically this script compiles the SnowC conversion programs from the original C source code (the code I originally wrote) and then uses those executables to convert the same source code to SnowC and then back to C. After a new set of C source code files has been generated, you can start the process again with the new files. You can specify how many times you want to make this round trip.

If I run this with a single round trip, it works. The outputs of the new version and the original version match.

This means the newly generated C source code behaves exactly like the original source code. And if I run the script 99 times and check the 99th executable, it also functions identically to the first.

Hmm, shouldn’t those md5 summaries be the same? Probably, it would be nice for sure. When the script is run with a high number of cycles you can easily see the problem. Those diff checks show that trailing comments are somehow getting pushed to the right by one space every iteration.

It looks like when braces are removed to make the SnowC, all the spaces around them stay, and then when a brace is added back to make the C again, it gets a polite space to format/separate it from the previous characters but all the spaces from the last round are still there too. So the line grows. An interesting bug for sure but minor enough to really be a serious issue only if you’re doing hundreds of round trip conversions!

I’ll fix this bug but it does not affect the critical goal of phase three. With the code supporting a functional round trip, it is now reasonable from here on to be able to continue development in SnowC. Hopefully we’ll see how that turns out sometime in the future.

Getting to phase three where a round trip is possible was the main original goal and now that I have done that, I’ll probably take a break from this project. Besides the issue I just mentioned, I have some known bugs I’d like to fix and I would like to try working directly in SnowC to see what that’s actually like. But what is next? What is phase four?

I think the next major milestone is improving and proving the robustness of the system by having it try to do round trips with C code in the wild. My main target is the Linux kernel.

Ignoring header files (for now) the 7.1.5 Linux kernel is distributed with 36684 C source code files. I used c2snowc to convert all but 11 of them. In just a quick inspection of those, I discovered a nasty configuration of nugatory else matching (see yesterday’s post). Since those 11 all hung (and not, say, a seg fault) I’m hoping they might all have the same problem. That’s only the first half of the mission. I also converted the 36673 Linux kernel SnowC files back into C. No trouble there. But Linux isn’t just some test code. Does that generated C compile? No. Even make tinyconfig dies pretty quickly into the process. But it’s a superb platform for catching C code that is difficult to translate. So I’ll probably work on whatever deficiencies that strategy reveals.

One thing converting 36673 files did answer is how fast is SnowC? Converting the C to SnowC took 2min 55sec or 4.8ms per file. With its simple algorithm, converting those SnowC files back to C was 25% quicker at 2min 12sec or 3.6ms per file. For reference, on my computer just a simple ls or cal take about 12ms. Just showing me the date takes about twice as long as converting SnowC code. So I’m pretty happy with the performance. If you come up with a much quicker way to pull the inherent redundancy out of well written C code, I’d love to see it!

[If you’ve made it this far, thank you for reading all this! Or any of it! I hope you learned something, even if only about my ability to get a little too obsessive about my projects!]

There is actually a point to this series on challenges I faced when creating a decent implementation of SnowC. I think the SnowC idea is very sensible and it is worth pursuing but while I’m proud of what I’ve accomplished, I’m not claiming to be our species' best candidate to implement the idea. And one day in the future — but not today! — maybe our robot friends can even improve on what I’ve done. So these posts serve as a guide for what someone will need to think about if they want to create a SnowC conversion system of their own. This post will round out some of the other random challenges I ran into. Some were expected, some not so much.

Literals

Let’s start with the first thing you need to start with. It may come as a slight surprise that the first thing to deal with is character and string literals. I take a special interest in specifying text in programming languages so it came as no surprise to me to discover that strings must be isolated and dealt with first. It’s pretty easy to see why if we imagine a string talking about the syntax of specifying strings.

Obviously that’s annoying but really SnowC doesn’t care what your string says, it just needs your strings to not confuse things. That could happen in an example like this.

You can use the c2snowc map diagnostic option (-m) to show how the characters of this line get classified, or mapped into general categories.

With the characters of the string properly identified it’s much easier to see that there are only two proper semicolons here to worry about. The same idea applies to this line involving character literals.

It may seem odd, but since strings can say any crazy thing, they must be neutralized before anything else is touched. And although the fail cases are subtle, character literals should be immediately neutralized next.

Comments

The next thing to isolate and neutralize must be modern double slash comments. This was originally a C++ thing and looks like this.

This (everything after //) is the primary comment style that takes precedence over a secondary comment style. Old school K&R comments (/* which look like this */) are very clever. Too clever. Probably the biggest source of real problems is C’s classic comment style. It’s bad enough looking for the last meaningful character of a line knowing that any random junk can follow in the form of a comment. For example, the last meaningful character here is the first semicolon.

But the problems get infinitely worse when you consider that classic C commenting can be mischievously injected anywhere. Looking for a thing that needs to follow a thing? Well, you better count on it following a near random collection of obfuscating garbage in the form of a comment.

So identify all the characters that are double slash comments and then identify all the other comment characters. Then don’t forget about them, because they could possibly be causing mischief damn near anywhere!

Just remember that you can comment out preprocessor syntax, so deal with comments first. Which brings us to preprocessor problems.

Preprocessor

Comments are hard because they can lurk anywhere muddling important semantic details. But preprocessor directives have a different problem. They are often used to swap in chunks of real C code at the last minute. I actually did not do a super deep dive into insane preprocessor abuse. I am pretty tame with my usage personally and, well, it was a lower priority for me. Sorry.

Basically if the first significant character of a line is a # I’m calling it a preprocessor directive and it gets ignored much like a comment. If there is some kind of #if, #ifdef, #elif, #else or similar construction with some ugly confusing code hiding inside, well, you’ll probably need to take special care.

One conceptual problem is that the SnowC to C conversion injects the missing C syntax (braces, semicolons) back into the code. If a preprocessor range isn’t anticipating this, there can be problems. Here’s a simplified example equivalent to something I found in the Linux kernel starting with the original C.

The SnowC is fine.

But look what happens when it goes back to C.

Leaving out all the closing braces when the fancy feature is not enabled will be a serious problem. Comments also can be moved to undesired locations in this way but that’s less problematic.

I could have all closing brace generation wait until after any preprocessor lines (and comments) but this is sometimes not the right choice either. I suspect it is the more common choice and I may switch the default to it. I’m starting to think that the correct solution is for SnowC to insist you place your preprocessor statement’s level intentions the same way as everything else — with indent level. Consider it on the to do list.

Labels

C has a quirky syntax for "labels" which are targets for the goto statement. Using goto in the first place is not really encouraged so labels aren’t even all that common. But they’re common enough that they need to be dealt with.

In C, a label is generally a word followed by a colon. Like this.

Easy, right? Well, not so fast! Have a look at some of my test code where I try to anticipate label problems.

C has a way of making you think it’s simple and obvious. And then you dig into it and find out, yikes, a lot can be taken for granted by the programmer.

So why exactly do we need to know what text is a label? Because SnowC needs to mostly ignore them sometimes. For example when they are between a singleton control word and the resolving statement.

Unfortunately C has another use for colons. A couple in fact. Look at this syntax — which I checked does actually compile.

Fortunately, despite failing to realize that not_a_label: is not a label, the SnowC conversion just happens to work because of, well, luck. I am walking away from this one.

Nugatory

If you don’t know what the word "nugatory" means, I suggest you look it up (click here!) and start using it. It’s a great word!

You can probably figure it out from my test file called nugatory.c which gave me a surprising amount of grief. Here it is with the generated SnowC on the right.

Dang that’s gnarly! But if you follow the simple SnowC rules to convert that back to C, it will produce semantically equivalent C code.

Note the final line is blank. I also have several tests for blank lines at the beginning and end and other inconvenient places. It’s little things like that which can be a real pain in the ass.

I’m sure there are other challenges I could highlight but that concludes my tour of the main problems that one must deal with when trying to pull the redundancy out of C code. It may not be easy, but for practical use, I have demonstrated that it is possible.

In the last post we looked at how challenging it was to just track level depth. To understand the problem better let’s review how singletons can cause mischief. The classic singleton is something like this conceptual code.

The SINGLETON_KEYWORD can be if, for, while, switch, do, or else. When the resolving statement completes, the singleton is complete. But what if the resolving_statement is also another SINGLETON_KEYWORD?

The resolving statement closes out the nearest singleton which then closes out the next and the whole chain unwinds. Now that I’ve explained it to you, you’re ready to believe that’s how it truly works, right? If you don’t know anything about C you are certainly ready to believe this. Even if you are a professional C programmer, you might still be fooled because no sane person ever writes code like this!

The resolving statement unraveling all the nested singletons is a nice neat concept, but unfortunately, it is not C’s nice neat concept. Let’s see how C really behaves. Check out this singleton puzzle paying attention to the indent levels.

That does look like the neat algorithm I described. The level of the first if has been fully reset because the entire chain of singletons has been resolved. Seems reasonable, right? C then puts you in the uncomfortable position of thinking the following code is also reasonable even though there is a kind of inconsistency to it.

The else resolves with a single statement clearly making it a singleton keyword. But there is more to it. It turns out that else is a special singleton keyword that has its own ideas about indent level.

This inconsistent feature of C’s control keywords introduces the need to track if the last singleton keyword was specifically an if and then on closing out that if, the levels get adjusted differently if a look ahead can find an else nearby. Good times.

If you think all that sounds challenging, I’ve got some bad news for you because it turns out to be a lot worse than that. I realized that any else must align with any inner if regardless of either executing a braced clause or not. This actually requires a FILO stack to keep track of any pending if that might possibly go with an else at every level of brace depth. And these must be politely dropped once there is no possibility for an else at that brace level. Don’t worry if that takes you several days to get your head around; been there.

At this point I was seriously starting to question my judgment at taking on this project. But I pressed on and figured out a way. The need for this quirky syntax tracking should almost never arise in any sane modern production code. For that reason each tracked level on the stack gets a leisurely heap allocation and I’m not even going to apologize.

When I finally implemented that, my test setup caught another error in the K&R sample from page 132! There already was a missing semicolon in that code but also I realized line 20 is incorrectly indented! Fortunately SnowC caught it nicely. And of course it must be said that in C, this is not technically an error — it does compile fine. But it sure is a faux pas!

(KR132-cat.c)

I already noted their page 51 example which highlights this exact problem deliberately. The SnowC on the right is automatically corrected.

Hopefully you now have a better understanding of just how wrong I was when I originally thought of the SnowC concept and I thought it surely couldn’t be all that hard. It was a hell of a challenge but I’m glad I stuck with it and I am very happy with the results.

I’ll leave you with a couple of extra awful conversion tests that I used during development, starting with an example of singletons, braces, and a mix. Remember, SnowC is ignoring all the (possibly spurious) indentation of the original and recreating it with structural rigor.

(nested_if_else.c)

Here is another challenging test for the if/else matching. The B is brace level and the S is singleton level.

(badelse.c)

Back in 2015 when I conceived of the idea for SnowC, I first thought it would be so easy to convert from SnowC to C that I could do it by storing the state of the indentation level in the call stack using recursion. That turned out to be too ambitious but it was close.

However what was really delusional and naive was thinking that converting from C might be possible using recursion too. While I got over that quickly, even starting on it fresh this year, I thought, surely this conversion can not be that difficult. Wow, was I profoundly wrong! Over two months later I now know an unhealthy amount about pathological C code and I have been humbled. When it comes to the entire possibility space of C source code, nothing is simple.

Which brings us to indent levels. Easy, right? Well let’s just say that it’s easy when it’s easy. Like this example (C left, SnwoC right).

And without the comments, the SnowC is pretty legible.

Those comments are there to show how the core concept works. You basically need a simple integer variable that stores the indent level. When you find an opening brace ({), increment the indent level, and when you find a closing brace (}), decrement the indent level. Easy, right? Right? Ohhhhh no.

It gets pretty bad. Let’s start with relatively simple singleton hassles. In a recent post we just covered how the C creators loved to do level nesting with no braces at all. I call those cases singletons. Ok, fine, so that is a thing. Sure, whatever. Surely there’s a solution, I thought.

Usually SnowC can happily not really care one bit what your C code is actually doing. But because of this issue, I realized there needed to be a complex parsing effort so all the singleton (braceless) control syntax could correctly contribute to the indent levels being adjusted properly. Not easy but doable. So I dug in and got to it.

Single line singletons are easily handled by just ignoring them. They are resolved before they can even make an impact on the code’s indentation structure.

Multi-line singletons are a different story, so let’s start with them.

An interesting property of SnowC is that a round trip will completely remove multi-line singletons! For example, consider this authentic K&R example (from page 92).

In SnowC it becomes.

Note how close this actually is to what K&R imagined! But there is no way to hint that you do not want the more ordinary and predictable C you will get on the return conversion. Here is what converting back to C produces.

Note that this C produces the exact same SnowC shown above.

What if the entire singleton resolves on one line? And importantly what of subsequent additional elements like b() in this line of C code?

In theory this could be done by leaving it mostly as is with the non-trailing semicolons intact.

That is actually valid SnowC and will convert to the previous C one liner. However, when that C one liner converts to SnowC, it will get broken up.

The reason for this choice can be seen when there are line breaks which can cause trouble. Consider this SnowC.

If you are a real C programmer, hopefully that did not cause some life threatening allergic reaction. Which of these two possibilities is correct when it converts to C?

Or…

Both are reasonable interpretations.

While the first looks good at a glance, the second follows the simple SnowC rules. And for a few good reasons. What we can be sure about is that the following C code won’t ever be possible to generate by converting from SnowC.

Currently converting from C to SnowC, the rule is that singletons get split up if they resolve on the same line as another statement that would not share its level.

To see why this must be consider the following round trip sequences of conversions. Following the conversions vertically, on the left is C → SnowC → C and on the right is SnowC → C → SnowC.

Note how the SnowC can mostly preserve its form into C and back. But the C structured like this is confusing to begin with, and must get sorted out in SnowC for the braces to actually work when converted back. Because the C style in the upper left is confusing and discouraged (heck, K&R don’t even do it!) it is better to just cut up singletons packed on a line which will prepare them for how SnowC needs them to be. If you want SnowC as found on the right, use braces in the C like a normal person i.e. like the C code in the middle on the right.

If you want to see some serious SnowC puzzles check out my test file called spaceless.c and its corresponding SnowC.

Like many of my test files, it is a reminder that polite indenting is a choice in C; in SnowC it is a promise. It’s also an unusual example of a conversion to SnowC that results in more lines.

But those single singletons are relatively easy. Let’s take a look at more serious level hassles.

Check out this normal example from K&R p56, where the braces of the do control keyword control the indent. Also note that the indent is properly controlled for the two if statements too even though there are no braces. (C left, SnowC right)

To pull this off requires parsing the code deeply enough to recognize all 6 of the possible control words that can trigger a singleton (if, while, for, switch, do, else) and recognize when they are not going to be using braces. Just identifying those is a big job. When I finally got that working I was pretty relieved. Mostly that it was even possible.

But it gets worse. The C language allows an unhealthy mix of brace levels and singleton levels. While experimenting with demented code that nobody would ever use (I hope!) I discovered something very unnerving. I slowly started to realize that simply tracking the brace depth and the singleton level depth was not going to do the job. (Theoretically; in practice it mostly would.)

Check out this sample program where I’ve labeled the conditions to reflect the brace depth (e.g. B1) and also the singleton depth (e.g. S1). (mixed_lvls.c, C left, SnowC right)

What’s important to note here is that although chains of braceless singletons like if (a) if (b) if (c) do_this(); do increase indent depth, when the do_this() finally runs you can’t just set the singleton depth to zero and call it a day. That whole thing may be nested in one or more sets of braces that each have their own chain of singletons to unwind!

When I realized this, I had to scrap a lot of work and rethink the whole deal. And for what? A crazy obscure problem that in practice would hardly ever come up. But damn it, I was committed to doing it as well as I could.

The solution I came up with is that I create a heap array where I can store the singleton depth for each brace level. This is the only way an accurate unraveling of the most complex structures can be done. The initial allocation allows for ten brace levels deep. Is that the nesting depth limit then? No. If you go beyond ten, it will allocate twenty; if you fill that up, forty more, etc. until you run out of RAM.

This is my test of the dynamic array provision storing a long chain of singletons in a clause 11 brace levels deep.

If you understand how ugly that is, buckle up, it gets quite a bit worse! I’ll save that for the next post.

Today is the first in a series on challenges I ran into while designing and working on SnowC. My hope is that these can offer insight into how the system really works and what the thinking was behind my design decisions. These posts also highlight how challenging this project actually is — if you’re keen to improve on my system — and what I did to overcome those challenges.

Instead of starting at the beginning let’s look at the last major challenge I tackled: aggregate types.

When I had the realization that braces are redundant in good code, I was naively thinking that the function of braces was to control nesting levels. And that is something they do. Usually.

It turns out that — in C specifically — braces are also used for Other Things. After carefully studying those my personal opinion is that this is a questionable stylistic language design choice. I get it — space is tight with a limited number of characters and a lot of functions to perform. But overloading braces with some bonus meanings is none too cool. Fortunately SnowC improves the situation quite a bit!

Which brings us to a feature of C that I procrastinated dealing with until the last possible moment. While writing c2snowc.c I actually had no idea how I was going to deal with aggregate types until everything else was finished! These are (possibly) complex definitions and declarations of struct, union, and enum types that often use curly braces in a quirky way. Programmers generally do not have strong feelings about how those braces correspond to indentation if they have any at all.

Let’s carefully unravel the solution because it also helps explain effective SnowC usage generally. Remember that SnowC is basically stripped down C that easily reconstitutes back to C if you follow some very simple rules.

Consider an analogy — if I ask some kind of robot chef to convert some dehydrated fruit into regular fruit and then I mischievously give it some fresh fruit, I’m likely to get back well-soaked regular fruit. And maybe that’s a good trick if what you really wanted was washed fruit. If you know the simple rules you can use them to your advantage.

SnowC is like that with braces. Generally the point of SnowC is to allow you to not fuss with braces. If you really want them however that’s fine but the conversion isn’t going to think too hard about what you really are trying to do. It will just follow the simple rules for converting back to normal C. Making sure the C is correct and makes sense is on you.

Consider this SnowC on the left and it’s corresponding automatically generated C on the right.

It follows the simple rules. Braces are added because of the indent, and a semicolon is tacked on because the conversion sees no reason not to. The for line isn’t scrutinized to see if you’re an intelligent C programmer. Look what happens if you add some clumsy braces to the SnowC.

The same simple rules are correctly applied but now the C is invalid. Getting that part right is up to you!

If you understand and anticipate the conversion rules, you can try adventurous tricks to produce valid C.

This is now correct C. The exact same simple rules were used — the programmer just did a better job of playing the game.

However note that when you convert this generated C back to SnowC it will get looked at more carefully and cleaned up. When starting with wild C code, those rules are not so simple! (Now input C on the left and generated SnowC on the right.)

If you suspect that a conversion to SnowC and then back to C can help clean up badly structured C code, you’re right! Even if you never use or look at SnowC code, the conversion programs can highlight and unravel badly structured C code.

Now that we’ve seen how braces can be dropped into SnowC code and mostly ignored, it’s easier to imagine how this could be useful for aggregate types. Let’s look at some examples. Consider the conversion of this complex badly formatted C struct (left) to SnowC (right).

The conversion pulls out semicolons and braces that the simple rules of SnowC to C conversion can easily replace. The random styling and indentation is not so random in SnowC. Compare old original C (left above) to the new C (below on the right) after a round trip conversion.

If you’re not a C programmer and have just been following along roughly looking at the structure (bravo BTW!) then this code may not seem remarkable. SnowC conversions are just doing what they’ve been doing in all code we’ve seen. Well, with one tiny exception.

We have not seen a C to SnowC conversion leave an isolated semicolon when it is the last effective character of a line. Normally, the conversion to SnowC drops ending semicolons. This one represents a genuine special case rule that was created for aggregate types. The rule is: if a removable closing brace effectively (ignoring comments and whitespace) immediately precedes a semicolon which is the last effective character, then the semicolon stays.

If you think about it, a closing brace followed immediately by a semicolon is kind of a weird construction. As far as I can tell, it actually only ever shows up when defining types in situations like this.

The nice thing about the SnowC to C conversion is that it remains simple and follows the rules. If the last effective character is a semicolon in SnowC clearly that’s weird and it must be there for a reason, so it is left alone (and a second semicolon is not added to it).

Thank goodness we’ve solved the puzzle of aggregate types! Whew! What a relief.

Wait, what? We still haven’t? Ugh. It was about here that I (like anyone reading this) started to despair that maybe there were an infinite number of awful edge cases. I worried that maybe the whole concept was intractable. Luckily that wasn’t true! Let’s take a look at the last tricky problem involving aggregate types.

So far we have seen a pretty normal struct definition but there’s something else that can happen in type related syntax that involves braces and that is actually filling in values. It doesn’t even have to be fancy aggregate types. Here’s a simple array getting its values preloaded at definition time.

Gah! Who invited those braces?! And here are some typical aggregate types with similar syntax.

Clearly if those braces are converted to indents, that’s going to be a mess. This is where being able to leave braces in SnowC becomes critical. Let’s fast forward and show what c2snowc actually does with those lines. Here are the SnowC conversions.

That’s right, it just pulls the trailing semicolons off and says have a nice day! This means of course that SnowC can follow it’s reliable rules back to C and just add the semicolon back. But how is this possible?

What I realized is that this kind of thing only ever happens when the contents of the braces do not contain semicolons. Contrast with the earlier struct example. I created a function that scans brace pairs and if they contain no semicolons or other braces between the last characters of other C code (if any) and the closing brace, the braces are remapped as normal non-brace miscellaneous C code. I call this kind of brace, weak braces. Once their special meaning as a true brace is taken off the map of what’s going on, everything behaves very nicely. It’s like internally pretending to switch those braces out for some other kind of syntax while still in fact using the braces characters.

Unfortunately that still leaves nasty situations like this.

I realized that only the innermost {0} would get converted to weak braces. But! Once that conversion was done, if I ran the conversion again the next pair would get converted. I realized that if I returned how many conversions took place, I could elegantly solve the entire problem with this single line.

That basically says, keep doing this conversion over and over until there is nothing left to convert. And once that is done, everything works very nicely. This may be the one place where I traded execution time for code elegance and my own sanity.