Debugging a complex problem is tough, and it can be especially difficult when it's not obvious which chunk of code is responsible. It's common to attempt to produce a reduced test case in order to narrow it down. It's tedious to do this manually, but it's also the sort of thing computers are really good at. C-Reduce is a program which automatically takes programs and pares them down to produce a reduced test case. Let's take a look at how to use it.
Overview
C-Reduce is based on two main ideas.
First, there's the idea of a reduction pass. This is a transformation performed on some source code which produces a reduced version of that code. C-Reduce has a bunch of different passes, including things like deleting lines or renaming tokens to shorter versions.
Second, there's the idea of an interestingness test. The reduction passes are blind, and often produce programs which no longer contain the bug, or which don't compile at all. When you use C-Reduce, you provide not only a program to reduce but also a small script which tests whether a reduced program is "interesting." Exactly what "interesting" means is up to you. If you're trying to isolate a bug, then "interesting" would mean that the bug still occurs in the program. You can define it to mean whatever you want, as long as you can script it. Whatever test you provide, C-Reduce will try to provide a reduced version of the program that still passes the test.
Installation
C-Reduce has a lot of dependencies and can be difficult to install. Thankfully, Homebrow has it, so you can let it take care of things:
brewinstallcreduce
If you'd rather do it yourself,take a look at C-Reduce's INSTALL file.
Simple Example
It's difficult to come up with small examples for C-Reduce, since its whole purpose is to start from something large andproduce a small example, but we'll give it our best try. Here's a simple C program that produces a somewhat cryptic warning:
$cattest.c#include<stdio.h>structStuff{char*name;intage;}main(intargc,char**argv){printf("Hello, world!\n");}$clangtest.ctest.c:3:1:warning:returntypeof'main'isnot'int'[-Wmain-return-type]structStuff{^test.c:3:1:note:changereturntypeto'int'structStuff{^~~~~~~~~~~~inttest.c:10:1:warning:controlreachesendofnon-voidfunction[-Wreturn-type]}^2warningsgenerated.
Somehow ourstruct is messing withmain! How could that be? Maybe reducing it would help us figure it out.
We need an interestingness test. We'll write a small shell script to compile this program and check for the warning in the output. C-Reduce is eager to please and can easily reduce a program far beyond what we really want. To keep it under control, we'll write a script that not only checks for the warning, but also rejects any program that produces an error, and requiresstruct Stuff to be somewhere in the compiler output. Here's the script:
#!/bin/bashclangtest.c&>output.txtgreperroroutput.txt&&exit1grep"warning: return type of 'main' is not 'int'"output.txt&&grep"struct Stuff"output.txt
First, it compiles the program and saves the compiler output intooutput.txt. If the output contains the text "error" then it immediately signals that this program is not interesting by exiting with error code 1. Otherwise it checks for both the warning and forstruct Stuff in the output.grep exits with code0 if it finds a match, so the result is that this script exits with code0 if both of those match, and code1 if either one fails. Exit code0 signals to C-Reduce that the reduced program is interesting, while code1 signals that it's not interesting and should be discarded.
Now we have enough to run C-Reduce:
$creduceinterestingness.shtest.c===<4907>===running3interestingnesstestsinparallel===<pass_includes::0>===(14.6%,111bytes)...lotsofoutput...===<pass_clex::rename-toks>======<pass_clex::delete-string>======<pass_indent::final>===(78.5%,28bytes)=====================done====================passstatistics:methodpass_balanced::parens-insideworked1timesandfailed0timesmethodpass_includes::0worked1timesandfailed0timesmethodpass_blank::0worked1timesandfailed0timesmethodpass_indent::finalworked1timesandfailed0timesmethodpass_indent::regularworked2timesandfailed0timesmethodpass_lines::3worked3timesandfailed30timesmethodpass_lines::8worked3timesandfailed30timesmethodpass_lines::10worked3timesandfailed30timesmethodpass_lines::6worked3timesandfailed30timesmethodpass_lines::2worked3timesandfailed30timesmethodpass_lines::4worked3timesandfailed30timesmethodpass_lines::0worked4timesandfailed20timesmethodpass_balanced::curly-insideworked4timesandfailed0timesmethodpass_lines::1worked6timesandfailed33times********.../test.c********structStuff{}main(){}
At the end, it outputs the reduced version of the program that it came up with. It also saves the reduced version into the original file. Beware of this when working on real code! Be sure to run C-Reduce on a copy of the code (or on a file that's already checked into version control), not on an irreplaceable original.
This reduced version makes the problem more apparent: we forgot the semicolon at the end of the declaration ofstruct Stuff, and we forgot the return type onmain, which causes the compiler to interpretstruct Stuff as the return type tomain. This is bad, becausemain has to returnint, thus the warning.
Xcode Projects
That's fine for something we've already reduced to a single file, but what about something more complex? Most of us have Xcode projects, so what if we want to reduce one of those?
This gets awkward because of the way C-Reduce works. It copies the file to reduce into a new directory, then runs your interestingness script there. This allows it to run a lot of tests in parallel, but this breaks if you need other stuff for it to work. Since your interestingness script can run arbitrary commands, you can work around this by copying the rest of the project into the temporary directory.
I created a standard Cocoa Objective-C app project in Xcode and then modified theAppDelegate.m file like so:
#import"AppDelegate.h"@interfaceAppDelegate(){NSWindow*win;}@property(weak)IBOutletNSWindow*window;@end@implementationAppDelegate-(void)applicationDidFinishLaunching:(NSRect)visibleRect{NSLog(@"Starting up");visibleRect=NSInsetRect(visibleRect,10,10);visibleRect.size.height*=2.0/3.0;win=[[NSWindowalloc]initWithContentRect:NSMakeRect(0,0,100,100)styleMask:NSWindowStyleMaskTitledbacking:NSBackingStoreBuffereddefer:NO];[winmakeKeyAndOrderFront:nil];NSLog(@"Off we go");}@end
This strange code crashes the app on startup:
*thread#1,queue='com.apple.main-thread',stopreason=EXC_BAD_ACCESS(code=EXC_I386_GPFLT)*frame#0:0x00007fff3ab3bf2dCoreFoundation`__CFNOTIFICATIONCENTER_IS_CALLING_OUT_TO_AN_OBSERVER__+13
This is not a very informative backtrace. We could try to debug (or just notice the problem), but instead let's reduce!
The interestingness test needs to do some more work here. Let's start with a helper to run the app with a timeout. We're looking for a crash, and if the appdoesn't crash it'll just stay open, so we need to kill it after a few seconds. I found this handy perl snippet repeated all over the internet:
functiontimeout(){perl-e'alarmshift;exec@ARGV'"$@";}
Next, we need to copy the Xcode project over:
cp-a~/Development/creduce-examples/Crasher.
TheAppDelegate.m file isn't automatically placed in the appropriate location, so copy that across. (Note: C-Reduce will copy the file back if it finds a reduction, so be sure to usecp here rather thanmv. Usingmv will result in a cryptic fatal error.)
cpAppDelegate.mCrasher/Crasher
Then switch into theCrasher directory and build the project, exiting on failure:
cdCrasherxcodebuild||exit1
If it worked, run the app with a timeout. My system is configured so thatxcodebuild places the build result in a localbuild directory. Yours may be configured differently, so check first. Note that if your configuration builds to a shared build directory, you'll want to disable C-Reduce's parallel builds by adding--n 1 to the command line when invoking it.
timeout5./build/Release/Crasher.app/Contents/MacOS/Crasher
If it crashes, it'll exit with the special code139. Translate that into an exit code of0, and in all other cases exit with code1:
if[$?-eq139];thenexit0elseexit1fi
Now we're ready to run C-Reduce:
$creduceinterestingness.shCrasher/AppDelegate.m...(78.1%,151bytes)=====================done====================passstatistics:methodpass_ints::aworked1timesandfailed2timesmethodpass_balanced::curlyworked1timesandfailed3timesmethodpass_clex::rm-toks-7worked1timesandfailed74timesmethodpass_clex::rename-toksworked1timesandfailed24timesmethodpass_clex::delete-stringworked1timesandfailed3timesmethodpass_blank::0worked1timesandfailed1timesmethodpass_comments::0worked1timesandfailed0timesmethodpass_indent::finalworked1timesandfailed0timesmethodpass_indent::regularworked2timesandfailed0timesmethodpass_lines::8worked3timesandfailed43timesmethodpass_lines::2worked3timesandfailed43timesmethodpass_lines::6worked3timesandfailed43timesmethodpass_lines::10worked3timesandfailed43timesmethodpass_lines::4worked3timesandfailed43timesmethodpass_lines::3worked3timesandfailed43timesmethodpass_lines::0worked4timesandfailed23timesmethodpass_lines::1worked6timesandfailed45times********/Users/mikeash/Development/creduce-examples/Crasher/Crasher/AppDelegate.m********#import"AppDelegate.h"@implementationAppDelegate-(void)applicationDidFinishLaunching:(NSRect)a{a=NSInsetRect(a,0,10);NSLog(@"");}@end
That's a lot shorter! TheNSLog line looks harmless, although it must be part of the crash if C-Reduce didn't remove it. Thea = NSInsetRect(a, 0, 10); line is the only other thing that actually does something. Where doesa come from and why would writing to it do something bad? It's just the parameter toapplicationDidFinishLaunching: which... is not anNSRect.
-(void)applicationDidFinishLaunching:(NSNotification*)notification;
Oops! The parameter type mismatch resulted in stack corruption that caused the uninformative crash.
C-Reduce took a long time to run on this example, because building an Xcode project takes longer than compiling a single file, and because a lot of the test cases hit the five-second timeout when running. C-Reduce copies the reduced file back to the original directory on every success, so you can leave it open in a text editor to watch it at work. If you think it's gone far enough, you can ^C it and you'll be left with the partially-reduced file. If you decide you want to run it some more, re-run it and it will continue from there.
Swift
What if you're using Swift and want to reduce a problem? Given the name, I originally thought that C-Reduce only worked on C (and maybe C++, since so many tools do both).
Thankfully, I was wrong. C-Reduce does have some C-specific reduction passes, but it has a lot of others that are relatively language agnostic. It may be less effective, but as long as you can write an interestingness test for your problem, C-Reduce can probably work on it no matter what language you're using.
Let's try it. I found anice compiler bug on bugs.swift.org. It's already been fixed, but Xcode 9.3's Swift crashes on it and I happen to have that version handy. Here's a slightly modified version of the example from that bug:
importFoundationfunccrash(){letblah=ProblematicEnum.problematicCase.problematicMethod()NSLog("\(blah)")}enumProblematicEnum{casefirst,second,problematicCasefuncproblematicMethod()->SomeClass{letsomeVariable:SomeClassswitchself{case.first:someVariable=SomeClass()case.second:someVariable=SomeClass()case.problematicCase:someVariable=SomeClass(someParameter:NSObject())_=NSObject().descriptionreturnsomeVariable// EXC_BAD_ACCESS (simulator: EXC_I386_GPFLT, device: code=1)}let_=[someVariable]returnSomeClass(someParameter:NSObject())}}classSomeClass:NSObject{overrideinit(){}init(someParameter:NSObject){}}crash()
Let's try running it with optimizations enabled:
$swift-Otest.swift<unknown>:0:error:fatalerrorencounteredduringcompilation;pleasefileabugreportwithyourprojectandthecrashlog<unknown>:0:note:Programusedexternalfunction'__T04test15ProblematicEnumON'whichcouldnotberesolved!...
The interestingness test is fairly simple for this one. Run that command and check the exit code:
swift-Otest.swiftif[$?-eq134];thenexit0elseexit1fi
Running C-Reduce on this, it produces the following example:
enuma{caseb,c,dfunce()->f{switchself{case.b:0case.c:0case.d:0}returnf()}}classf{}
Diving into the actual compiler bug is beyond the scope of this article, but this reduction would be really handy if we actually set out to fix it. We have a considerably simpler test case to work with. We can also infer that there's some interaction between the swift statement and the instantiation of the class, since C-Reduce probably would have removed one of them if it were unnecessary. This would give us some good hints about what might be happening in the compiler to cause this crash.
Conclusion
Blind reduction of a test case is not a very sophisticated debugging technique, but the ability to automate it can make it extremely useful. C-Reduce can be a fantastic addition to your debugging toolbox. It's not suitable for everything, but what is? For problems where it's useful, it can help enormously. It can be a bit tricky to get it to work with multi-file test cases, but some cleverness with the interestingness script solves the problem. Despite the name, it works out of the box on Swift and many other languages, so don't give up on it just because you're not working in C.
That's it for today. Check back next time for more fun, games, and code. Friday Q&A is driven by reader ideas, so if you have something you'd like to see covered here next time or some other time, pleasesend it in!
Add your thoughts, post a comment:
Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.