Bug 691391

Summary: Enhancement: testcase minimization tool for Postscript
Product: Ghostscript Reporter: D. Wagner <daw-misc>
Component: Test FrameworkAssignee: Ray Johnston <ray.johnston>
Status: RESOLVED WONTFIX    
Severity: enhancement CC: alex
Priority: P4    
Version: master   
Hardware: PC   
OS: Linux   
Customer: Word Size: ---
Attachments: Tool for minimizing Postscript testcases

Description D. Wagner 2010-06-14 06:02:50 UTC 
Created attachment 6373 [details]
Tool for minimizing Postscript testcases

I built a prototype tool for minimizing Postscript test cases, namely, Postscript files that trigger some kind of crash in ghostscript.  I thought I'd share the tool with you, in case you find it useful.  See attachment for documentation and information about how to use it.  Feel free to use it if you like.

Note that this is very poorly tested, so if it fails, I won't be terribly surprised.  It is based upon delta debugging (http://delta.tigris.org/), but with some Postscript-specific heuristic knowledge built in.  Ghostscript developers may be able to build a much better version, if this does prove useful.
Comment 1 Alex Cherepanov 2010-07-03 03:51:57 UTC 
The idea to create a minimal PostScript sample file is attractive but
a simple experiment shows that it doesn't go too far.

One can easily construct a PostScript program where no single token can
be removed without breaking it but there are groups of tokens that
can be removed together.

The program needs to find a group of tokens that don't change the stack
depth but most PS programs start with redefining all the operators
like '/m /moveto load def'. To figure out that m consumes 2 operands
the program need to do some speculative execution.

PostScript is a legacy technology and development of advanced PostScript
analysis tools won't attract much of external interest. Minimization
of sample files has never been a significant part of Ghostscript
development.

Although the attached manages to remove some parts of PS program,
the structure and logic of the resulting text is disturbed making
further manual analysis impossible.