#!/usr/bin/perl -w
use strict;
sub all_cmds();
sub find( $$ );
sub find_aux( $$ );

my %fromto;
my %isa;
sub isa { $isa{$_[0]}{$_[1]} = undef }
sub same { isa($_[0], $_[1]); isa($_[1], $_[0]) }

# A portable 'anymap' (pnm) can be a pbm, ppm or pgm file.
isa($_, 'pnm') foreach qw(pbm ppm pgm);

# 'Any ppm program can read pgm (and pbm) files automatically'
#   -- ppmtopgm(1)
#
isa('pnm', 'ppm');
isa('tiffcmyk', 'tiff');
isa('epsi', 'eps');

# PPM files with at most 256 colours.
isa('ppm_256', 'ppm');

# PPM files with the classic 8 colours (TTL RGB).
isa('ppm_8rgb', 'ppm_256');

# not isa('eps', 'ps'), eg ps2ps doesn't like EPS files

# Different special effects in text files: overstrike and ANSI escape
# sequences.
#
same('text', 'txt');
same('ascii', 'txt');
isa('txt', 'overstrike');

# PDF version 1.2 and 1.3.
isa('pdf1.2', 'pdf');
isa('pdf1.3', 'pdf');
isa('pdf1.2', 'pdf1.3'); # backward compat.

# PostScript Levels 1, 2 and 3.
isa('ps1', 'ps');
isa('ps1sep', 'ps1');
isa('ps2', 'ps1');
isa('ps2sep', 'ps2');
isa('ps3', 'ps2');

# Backward compatibility of LaserJets.
isa('lj', 'lj2p');
isa('lj2p', 'lj4');
isa('lj4', 'lj4l');
isa('lj4l', 'lj6');
same('lj', 'pcl');

# Backward compatibility of PaintJets.
isa('pjxl', 'pj');

# According to the jpegtopnm(1) manpage, there are 'Adobe' and
# 'non-Adobe' conventions for CMYK in JFIF files.
#
isa('jpeg_adobe', 'jpeg');
isa('jpeg_notadobe', 'jpeg');

# Windows and OS/2 bitmaps.  I don't know how compatible these are.
isa('bmp_windows', 'bmp');
isa('bmp_os2', 'bmp');

# HP DeskJet PPA format.  Why does HP have so many?
isa('ppa7', 'ppa');
isa('ppa8', 'ppa');
isa('ppa10', 'ppa');

# BBN BitGraph terminal Display Pixel Data (DPD).
same('bg', 'bbnbg');

# Fax standards.  I don't know whether they are backwards compatible.
isa('fax1', 'fax');
same('faxg1', 'fax1');
same('g1', 'faxg1');
isa('fax2', 'fax');
same('faxg2', 'fax2');
same('g2', 'faxg2');
isa('fax3', 'fax');
same('faxg3', 'fax3');
same('g3', 'faxg3');

# GEM .img files.  It is too confusing to have a type 'img'.
same('gem', 'img_gem');

# GraphOn input data.
same('go', 'graphon');

# Sun icons (bits of C program).
isa('sunicon', 'icon');

# Windows icons.
same('icon_windows', 'winicon');
same('icon_windows', 'ico');

# DEC 'Sixel' format which appears to be printer data.
same('ln03', 'sixel_ln03');
same('sixel_ln03', 'sixel');

# MacPaint format (data fork).
same('macp', 'macpaint');

# Nokia Smart Messaging format.  Don't know if these are two different
# formats.
#
isa('nok', 'nokia');
isa('ngg', 'nokia');

# X11 is able to read X10 bitmaps.
isa('xbm11', 'xbm');
isa('xbm10', 'xbm11');
same('x10bm', 'xbm10');
same('x11bm', 'xbm11');

# Bennet Yee's "face" format.
same('ybm', 'face');

# We do not worry about distinguishing single-image GIF files from
# animated GIFs, even though many of the programs can only deal with
# individual GIF images.  It would be too much to say 'cannot convert
# gif to png', even if it is true in some cases.
#

my %avail;
foreach (all_cmds()) { $avail{$_}++ && die }

my %seen_exe;
sub cvtr( $$@ ) {
    my ($from, $to, @cmd) = @_;
    die "empty command to convert from $from to $to" if not @cmd;
    my $first = 1;
    foreach (@cmd) {
	# The first command must be an executable, plus any marked *.
	if ($first or s/\*$//) {
	    if (not $avail{$_}) {
		warn "command $_ not installed";
		return;
	    }
	    $seen_exe{$_} = 1;
	}
	$first = 0;
    }

    push @{$fromto{$from}{$to}}, \@cmd;
}

# Commands which are tested or documented to convert between two
# formats.  A * character after an argument indicates that this is an
# executable which needs to be in the PATH.
#
cvtr 'xmltv', 'latex',       'tv_to_latex';
cvtr 'latex', 'dvi',         'pip_latex';
cvtr 'latex', 'html',        qw(pip_latex2html);
cvtr 'tex', 'dvi',           'pip_tex';
cvtr 'gif', 'png',           qw(gif2png -fO);
cvtr 'gif', 'pnm',           'giftopnm'; # but pixel-shape problems
cvtr 'txt', 'ps',            qw(enscript -p -);
cvtr 'txt', 'html',          qw(enscript -p - -w html);
cvtr 'txt', 'overstrike',    qw(enscript -p - -w overstrike);
cvtr 'txt', 'rtf',           qw(enscript -p - -w rtf);
cvtr 'txt', 'ansi',          qw(enscript -p - -w ansi);
cvtr 'dvi', 'pcl',           qw(pip -I dvihp* -f);
cvtr 'dvi', 'lj',            qw(pip -I dvilj* -);
cvtr 'dvi', 'lj2p',          qw(pip -I dvilj2p* -);
cvtr 'dvi', 'lj4',           qw(pip -I dvilj4* -);
cvtr 'dvi', 'lj4l',          qw(pip -I dvilj4l* -);
cvtr 'dvi', 'lj6',           qw(pip -I dvilj6* -);
cvtr 'dvi', 'pdf',           qw(pip -io dvipdf* - -);
cvtr 'dvi', 'ps',            qw(pip -I dvips* -fR);
cvtr 'dvi', 'mpx',           qw(pip -io dvitomp* -.dvi -.mpx);
cvtr 'man', 'overstrike',    qw(groff -Tascii -mandoc);
cvtr 'man', 'ps',            qw(groff -Tps -mandoc);
cvtr 'man', 'html',          'man2html';
cvtr 'pod', 'html',          'pod2html';
cvtr 'pod', 'latex',         qw(pip -oi pod2latex* -full -o -.tex -.pl);
cvtr 'pod', 'man',           qw(pod2man --lax --quotes none);
cvtr 'pod', 'text',          qw(pod2text --sentence);
cvtr 'pod', 'ansi',          qw(pod2text --sentence --color);
cvtr 'pod', 'overstrike',    qw(pod2text --sentence --overstrike);
cvtr 'png', 'pnm',           'pngtopnm';
cvtr 'pnm', 'lex5700',       'pnm2lex5700';
cvtr 'pnm', 'lex7000',       'pnm2lex7000';
cvtr 'pnm', 'ppa7',          qw(pnm2ppa -v 710 -o -);
cvtr 'pnm', 'ppa8',          qw(pnm2ppa -v 820 -o -);
cvtr 'pnm', 'ppa10',         qw(pnm2ppa -v 1000 -o -);
cvtr 'pnm', 'ddif',          'pnmtoddif';
cvtr 'pnm', 'fiasco',        'pnmtofiasco';
cvtr 'pnm', 'fits',          'pnmtofits';
cvtr 'pnm', 'jpeg',          qw(pnmtojpeg --progressive);
cvtr 'pnm', 'palm',          'pnmtopalm';
cvtr 'pnm', 'png',           'pnmtopng';
cvtr 'pnm', 'eps',           'pnmtops'; # sic
cvtr 'pnm', 'rast',          'pnmtorast';
cvtr 'pnm', 'rle',           'pnmtorle';
cvtr 'pnm', 'sgi',           'pnmtosgi';
cvtr 'pnm', 'sir',           'pnmtosir';
cvtr 'pnm', 'tiff',          qw(pip -O pnmtotiff*);
cvtr 'pnm', 'tiffcmyk',      qw(pip -O pnmtotiffcmyk* -none);
cvtr 'pnm', 'xwd',           'pnmtoxwd';
cvtr 'ps', 'txt',            'ps2ascii';
cvtr 'pdf', 'txt',           qw(pip -i ps2ascii* -);
cvtr 'ps', 'epsi',           qw(pip -io ps2epsi* -.ps -.epsi);
cvtr 'ps', 'pdf',            qw(ps2pdf -);
cvtr 'ps', 'pdf12',          qw(ps2pdf12 -);
cvtr 'ps', 'pdf13',          qw(ps2pdf13 -);
cvtr 'ps', 'pdf',            qw(ps2pdfwr -);
cvtr 'ps', 'pnm',            qw(pstopnm -stdout);
cvtr 'html', 'txt',          qw(pip -i links* -dump -);
cvtr 'html', 'txt',          qw(pip -i lynx* -force_html -dump -);
cvtr 'pdf', 'ps',            qw(pip -I pdf2ps* - -);
cvtr 'pdf', 'ps1',           qw(pip -I pdf2ps* -dLanguageLevel=1 - -);
cvtr 'pdf', 'ps2',           qw(pip -I pdf2ps* -dLanguageLevel=2 - -);
cvtr 'pdf', 'ps',            qw(pip -io pdftops* - -);
cvtr 'pdf', 'ps1',           qw(pip -io pdftops* -level1 - -);
cvtr 'pdf', 'ps1sep',        qw(pip -io pdftops* -level1sep - -);
cvtr 'pdf', 'ps2sep',        qw(pip -io pdftops* -level2sep - -);
cvtr 'pdf', 'txt',           qw(pip -io pdftotext* - -);
cvtr 'pdf', 'html',          qw(pip -io pdftotext* -htmlmeta - -);
cvtr 'fiasco', 'pnm',        'fiascotopnm';
cvtr 'fits', 'pnm',          'fitstopnm';
cvtr 'jpeg', 'pnm',          'jpegtopnm';
cvtr 'jpeg_adobe', 'pnm',    qw(jpegtopnm -adobe);
cvtr 'jpeg_notadobe', 'pnm', qw(jpegtopnm -notadobe);
cvtr 'ppm', 'jpeg',          qw(cjpeg -progressive);
cvtr 'pgm', 'jpeg',          qw(cjpeg -progressive);
cvtr 'bmp', 'jpeg',          qw(cjpeg -progressive);
cvtr 'tga', 'jpeg',          qw(cjpeg -progressive -targa);
cvtr 'rte', 'jpeg',          qw(cjpeg -progressive);
cvtr 'jpeg', 'bmp_windows',  qw(djpeg -bmp);
cvtr 'jpeg', 'gif',          qw(djpeg -gif);
cvtr 'jpeg', 'bmp_os2',      qw(djpeg -os2);
cvtr 'jpeg', 'pnm',          qw(djpeg -pnm);
cvtr 'jpeg', 'rle',          qw(djpeg -rle);
cvtr 'jpeg', 'tga',          qw(djpeg -targa);
cvtr 'palm', 'pnm',          'palmtopnm';
cvtr 'rast', 'pnm',          'rasttopnm';
cvtr 'rle', 'pnm',           'rletopnm';
cvtr 'sgi', 'pnm',           qw(pip -I sgitopnm*);
cvtr 'sir', 'pnm',           'sirtopnm';
cvtr 'tiff', 'pnm',          qw(pip -I tifftopnm*);
cvtr 'xwd', 'pnm',           'xwdtopnm';
cvtr 'eps', 'pdf',           qw(epstopdf --filter);
#cvtr 'bmp', 'pnm',           'bmptopnm'; # needs later netpbm
cvtr 'bmp', 'ppm',           'bmptoppm';
cvtr 'ppm', 'acad',          'ppmtoacad';
cvtr 'ppm', 'dxb',           qw(ppmtoacad -dxb);
cvtr 'ppm', 'bmp_windows',   qw(ppmtobmp -windows);
cvtr 'ppm', 'bmp_os2',       qw(ppmtobmp -os2);
cvtr 'ppm', 'cpva',          'ppmtocpva';
cvtr 'ppm', 'eyuv',          'ppmtoeyuv';
cvtr 'ppm', 'gif',           'ppmtogif';
cvtr 'ppm', 'icr',           'ppmtoicr';
cvtr 'ppm', 'jpeg',          'ppmtojpeg';
cvtr 'ppm', 'leaf',          'ppmtoleaf';
cvtr 'ppm', 'lj',            'ppmtolj';
cvtr 'ppm', 'mitsu',         'ppmtomitsu';
cvtr 'ppm', 'neo',           'ppmtoneo';
cvtr 'ppm', 'pcx',           'ppmtopcx';
cvtr 'ppm', 'pgm',           'ppmtopgm';
cvtr 'ppm', 'pi1',           'ppmtopi1';
cvtr 'ppm_256', 'pict',      qw(pip -O ppmtopict*);
cvtr 'ppm', 'ppm_8rgb',      qw(ppmdither -red 2 -green 2 -blue 2);
cvtr 'ppm_8rgb', 'pj',       'ppmtopj';
cvtr 'ppm', 'pjxl',          'ppmtopjxl';
cvtr 'ppm', 'puzz',          'ppmtopuzz';
cvtr 'ppm', 'sixel',         'ppmtosixel';
cvtr 'ppm', 'tga',           'ppmtotga';
cvtr 'ppm', 'uil',           'ppmtouil';
cvtr 'ppm', 'ico',           'ppmtowinicon';
cvtr 'ppm', 'xpm',           'ppmtoxpm';
cvtr 'ppm', 'yuv',           'ppmtoyuv';
cvtr 'pgm', 'fs',            'pgmtofs';
cvtr 'pgm', 'lispmbmp',      'pgmtolispm';
cvtr 'pgm', 'pbm',           'pgmtopbm';
#cvtr 'tga', 'ppm',           'tgatoppm'; # broken
cvtr 'eyuv', 'ppm',          'eyuvtoppm';
cvtr 'leaf', 'ppm',          'leaftoppm';
cvtr 'neo', 'ppm',           'neotoppm';
cvtr 'pcx', 'ppm',           qw(pip -I pcxtoppm*);
cvtr 'pi1', 'ppm',           'pi1toppm';
cvtr 'ppm', 'ppm_256',       qw(ppmquant 256);
cvtr 'pict', 'ppm_256',      'picttoppm';
cvtr 'pj', 'ppm_8rgb',       'pjtoppm';
cvtr 'ico', 'pbm',           'icontopbm';
cvtr 'xpm', 'ppm',           'xpmtoppm';
cvtr 'lispmbmp', 'pgm',      'lispmtopgm';
cvtr 'pbm', 'lex7000',       qw(pbm2l7k -m 0);
cvtr 'pbm', 'lex5700',       qw(pbm2l7k -m 1);
cvtr 'txt', 'pbm',           'pbmtext';
cvtr 'pbm', '10x',           'pbmto10x';
cvtr 'pbm', 'atk',           'pbmtoatk';
cvtr 'pbm', 'bbnbg',         'pbmtobbnbg';
cvtr 'pbm', 'cmuwm',         'pbmtocmuwm';
cvtr 'pbm', 'epson',         'pbmtoepson';
cvtr 'pbm', 'faxg3',         'pbmtog3';
cvtr 'pbm', 'img_gem',       'pbmtogem';
cvtr 'pbm', 'graphon',       'pbmtogo';
cvtr 'pbm', 'sunicon',       'pbmtoicon';
cvtr 'pbm', 'lj',            'pbmtolj';
cvtr 'pbm', 'sixel_ln03',    'pbmtoln03';
cvtr 'pbm', 'eps',           'pbmtolps';
cvtr 'pbm', 'macp',          'pbmtomacp';
cvtr 'pbm', 'mda',           'pbmtomda';
cvtr 'pbm', 'mgr',           'pbmtomgr';
cvtr 'pbm', 'nokia',         'pbmtonokia';
cvtr 'pbm', 'pi3',           'pbmtopi3';
cvtr 'pbm', 'plot',          'pbmtoplot';
cvtr 'pbm', 'ppa7',          qw(pbmtoppa -v 720);
cvtr 'pbm', 'ppa8',          qw(pbmtoppa -v 820);
cvtr 'pbm', 'ppa10',         qw(pbmtoppa -v 1000);
cvtr 'pbm', 'ps',            'pbmtopsg3';
cvtr 'pbm', 'ptx',           'pbmtoptx';
cvtr 'pbm', 'wbmp',          'pbmtowbmp';
cvtr 'pbm', 'xbm10',         'pbmtox10bm';
cvtr 'pbm', 'xbm',           'pbmtoxbm';
cvtr 'pbm', 'ybm',           'pbmtoybm';
cvtr 'pbm', 'zinc',          'pbmtozinc';
cvtr 'atk', 'pbm',           'atktopbm';
cvtr 'cmuwm', 'pbm',         'cmuwmtopbm';
cvtr 'img_whatnot', 'ppm',   'imgtoppm';   # untested
cvtr 'gould', 'ppm',         'gouldtoppm'; # untested
cvtr 'macp', 'pbm',          'macptopbm';
cvtr 'mda', 'pbm',           'mdatopbm';
cvtr 'mdp', 'pbm',           'mdatopbm'; # also
cvtr 'mgr', 'pbm',           'mgrtopbm';
cvtr 'pi3', 'pbm',           'pi3topbm';
cvtr 'wbmp', 'pbm',          'wbmptopbm';
cvtr 'xbm', 'pbm',           'xbmtopbm';
cvtr 'ybm', 'pbm',           'ybmtopbm';
cvtr 'winicon', 'ppm',       'winicontoppm';

# Commands which are known not to work.
foreach
  (
   'dvi2fax',        # generates multiple output files
   'dvitype',        # doesn't create usable output
   'giftrans',       # wants to modify, and who cares about GIF87 anyway
   'file',           # and pnmfile etc don't produce usable output
   'pnmraw2cmyk',    # produces multiple output files
   'pnmtoplainpnm',  # is useless for us
   'ps2frag',        # is obsolete, according to its manpage
   'ps2pk',          # too complex and not testable
   'psfgettable',    # doesn't really 'convert'
   'psidtopgm',      # is obsolete, according to its manpage
   'pslatex',        # how does this differ from latex?
   'pstogif',        # gives 'command not found'
   'pstoimg',        # produces an unknown output format
   'texi2dvi',       # would require a special wrapper like pip_tex
   'texi2html',      # wait until I get some Texinfo files to try it with
   'texi2pdf',       # needs its own wrapper, I think
   'asciitopgm',     # isn't a good conversion
   'pdf2dsc',        # generates PostScript referencing the original file
   'pdfeinitex',     # needs its own wrapper
   'pdfelatex',      # needs its own wrapper
   'pdfetex',        # needs its own wrapper
   'pdfevirtex',     # needs its own wrapper
   'pdftex',         # needs its own wrapper
   'pdfinitex',      # needs its own wrapper
   'pdfvirtex',      # needs its own wrapper
   'pdftopbm',       # generates multiple output files
   'pdf',            # to eps not possible in general: eps single page.
   'lexmark2ppm.pl', # has no documentation
   'ppmtoilbm',      # has too many options I don't understand
   'ppmtolss16',     # has no documentation
   'ppmtomap',       # doesn't really convert
   'ppmtomd',        # has too many options
   'ppmtompeg',      # requires a separate parameter file
   'ppmtoterm',      # has no documentation
   'ppmtoyuvsplit',  # generates multiple output files
   'pgmtoppm',       # requires a colourmap
   'icon2ikon',      # has no documentation
   'yuvsplittoppm',  # requires multiple input files
   'yuvtoppm',       # requires # x and y size parameters
   'fs2ikon',        # has no documentation
   'fs2xbm',         # is broken, it requires ppmscale installed
   'fs2bdf',         # has no documentation
   'fs2pgm',         # may require a separate rescaling stage
   'pbm2l2030',      # has no documentation
   'pbm2lex5700',    # has no documentation
   'pbm2lwxl',       # has no documentation
   'pbm2ppa',        # appears to be obsolete
   'pbmto4425',      # is more of a display program
   'pbmtoascii',     # isn't a real conversion
   'pbmtoepsi',      # doesn't create a whole EPS file
   'pbmtopgm',       # is actually a convolution
   'pbmtopk',        # produces two output files
  ) {
    $seen_exe{$_}++
      && warn "thought that $_ was bad but it seems to be used\n";
}

# If there are any commands left over then try guessing what they do.
foreach (all_cmds()) {
    if (/^(.+)_to_(.+)$/ or /^(.+)to(.+)$/ or /^(.+)2(.+)$/) {
	cvtr $1, $2, $_ unless $seen_exe{$_}++;
    }
}

my ($from, $to) = @ARGV;
die 'usage' if not defined $to;
my $best;
foreach (find($from, $to)) {
    if (not defined $best or scalar @$best > scalar @$_) {
	$best = $_;
    }
}
if (defined $best) {
    my $types = join(' -> ', @{$best->[0]});
    print STDERR "$types\n";
    my $cmd = join(' | ', map { join(' ', @$_) } @{$best->[1]});
    print STDERR "$cmd\n";
    exit(system $cmd);
}
else {
    die "cannot convert from $from to $to\n";
}

# Breadth-first search of format conversions.
sub find( $$ ) {
    my ($from, $to) = @_;
    my $start = [ [ $from ], [] ];
    return find_aux($to, [ $start ]);
}
sub find_aux( $$ ) {
    my $to = shift;
    use vars '@so_far'; local *so_far = shift;

    return undef if not @so_far;
    my %used = ();
    foreach my $s (@so_far) {
	return $s if $s->[0]->[-1] eq $to;
	$used{$_} = 1 foreach @{$s->[0]};
    }
    my @so_far_new;
    foreach my $s (@so_far) {
	my $last = $s->[0]->[-1];
	foreach my $is ($last, sort keys %{$isa{$last}}) {
	    foreach my $to (grep { not $used{$_} }
			    (sort keys %{$fromto{$is}})) {
		foreach my $cmd (@{$fromto{$is}{$to}}) {
		    push @so_far_new, [ [ @{$s->[0]}, $to ],
					[ @{$s->[1]}, $cmd ] ];
		}
	    }
	}
    }
    return find_aux($to, \@so_far_new);
}

# List all executables in the PATH.
sub all_cmds() {
    my @r;
    my @p = split /:/, $ENV{PATH};
    my (%seen_p, %seen_cmd);
    foreach (@p) {
	if ($_ eq '') {
	    warn "skipping empty path component\n";
	    next;
	}
	if (not m!^/!) {
	    warn "skipping relative path component $_\n";
	    next;
	}
	if ($seen_p{$_}++) {
	    warn "path component $_ seen twice\n";
	    next;
	}

	chdir $_ or die "cannot chdir to $_: $!";
	foreach (sort grep { -x } <*>) {
	    if ($seen_cmd{$_}++) {
#		warn "command $_ seen twice in path\n";
		next;
	    }
	    push @r, $_;
	}
    }
    return @r;
}