/*
 * Compute optimal quoting.
 *
 * Input is a string and a FILE *.  Output consists of printing
 *  characters to the FILE * to generate a quoted version of the
 *  string.
 *
 * Inside ' ', any character represents itself except another '.
 *  Inside " ", any character represents itself except ", \, or $, and
 *  \ quotes any of them.  Outside ' ' or " ", \ quotes any character.
 *  This module computes optimal quoting in the sense of a
 *  minimum-length string that represents the input string.  Characters
 *  %+,-./:=@_, letters, and digits do not need any quoting (though
 *  they can be quoted if it is convenient); all other characters
 *  cannot appear unquoted.
 *
 * Let the input string be S, of length L, and let C(l,e) be the
 *  minimum-length way to write the first l characters of S, ending
 *  with a single quote, a double quote, or no quote (or a backslashed
 *  quote), according as e is 1, 2, or 0.  Then, depending on S[i], we
 *  can express C(i,e) in terms of C(i-1,e') for various <e,e'> pairs,
 *  where the particular expressions depend on whether S[i] is
 *
 *	- Letter, digit, or one of the above punctuation characters.
 *	- ', single quote.
 *	- ", double quote.
 *	- \, backslash.
 *	- $, dollar sign.
 *	- Other.
 *
 * An optimum result can then be obtained as the minimum of C(L,e) for
 *  all possible values of e.  By attaching a little additional data,
 *  this can be extended to yield the actual quoting methods used.
 *
 * As a special case, a zero-length string turns into '' rather than
 *  zero characters.
 */

#include <stdlib.h>
#include <strings.h>

#include "quote.h"

typedef struct cell CELL;

struct cell {
  unsigned int val;
  unsigned char from;
  unsigned char how;
#define HOW_NULL        1 // Nothing
#define HOW_DOUBLE_S    2 // Append ''
#define HOW_DOUBLE_D    3 // Append ""
#define HOW_SIMPLE      4 // Just append
#define HOW_INSIDE_S    5 // Append inside the trailing '
#define HOW_INSIDE_D    6 // Append inside the trailing "
#define HOW_S_QUOTE     7 // Append with ' ' around it
#define HOW_D_QUOTE     8 // Append with " " around it
#define HOW_B_QUOTE     9 // Append \ and the char
#define HOW_S_QUOTE_B  10 // Append with '\ ' around it
#define HOW_D_QUOTE_B  11 // Append with "\ " around it
#define HOW_INSIDE_D_B 12 // Append with \ inside trailing "
#define HOW_B_S_S_S    13 // Append \'''
  } ;
#define MK(v,f,h) ((CELL){.val=(v),.from=(f),.how=(h)})

static unsigned int how_cost[][3]
 = { [HOW_NULL] = { 0, 1000000, 1000000 },
     [HOW_DOUBLE_S] = { 20, 1000000, 1000000 },
     [HOW_DOUBLE_D] = { 20, 1000000, 1000000 },
     [HOW_SIMPLE] = { 10, 11, 11 },
     [HOW_INSIDE_S] = { 1000000, 10, 1000000 },
     [HOW_INSIDE_D] = { 1000000, 1000000, 10 },
     [HOW_S_QUOTE] = { 31, 1000000, 31 },
     [HOW_D_QUOTE] = { 31, 31, 1000000 },
     [HOW_B_QUOTE] = { 20, 21, 21 },
     [HOW_S_QUOTE_B] = { 41, 40, 41 },
     [HOW_D_QUOTE_B] = { 41, 41, 40 },
     [HOW_INSIDE_D_B] = { 1000000, 1000000, 20 },
     [HOW_B_S_S_S] = { 1000000, 40, 1000000 } };

static CELL best(const CELL *p, int h0, int h1, int h2)
{
 int t0;
 int t1;
 int t2;

 t0 = p[0].val + how_cost[h0][0];
 t1 = p[1].val + how_cost[h1][1];
 t2 = p[2].val + how_cost[h2][2];
 /*
  * There are 13 possible orders for t0, t1, t2:
  *
  *	A: t0 == t1 == t2
  *	B: t0 == t1 < t2
  *	C: t0 == t2 < t1
  *	D: t1 == t2 < t0
  *	E: t0 < t1 == t2
  *	F: t1 < t0 == t2
  *	G: t2 < t0 == t1
  *	H: t0 < t1 < t2
  *	I: t0 < t2 < t1
  *	J: t1 < t0 < t2
  *	K: t1 < t2 < t0
  *	L: t2 < t0 < t1
  *	M: t2 < t1 < t0
  *
  * However, we don't care about distinctions beyond "lowest" and
  *  "non-lowest".  For example, we don't care about the difference
  *  between E and H.  This reduces the cases to seven:
  *
  *	A: t0 == t1 == t2
  *	B: t0 == t1 < t2
  *	C: t0 == t2 < t1
  *	D: t1 == t2 < t0
  *	E: t0 < ...
  *	F: t1 < ...
  *	G: t2 < ...
  *
  * Even though there are only seven cases, there is no way to tell
  *  them apart in only three comparisons.  Proof: first comparison
  *  must be of the form tX==tY or tX<tY.  WLOG, tX can be t0 and tY
  *  can be t1, by symmetry.  And t0==t1 or t0<t1 each have at least
  *  five cases in one arm of the comparison.  (In each case, it is
  *  important to note that at least one case splits, with some of its
  *  subcases appearing in each of the resulting arms.)  Because of
  *  case splitting, I threw in the towel on optimal comparison trees
  *  and went with easy-to-understand code instead.  This is hardly
  *  performance-critical every-cycle code, after all.
  */
 if ((t0 == t1) && (t0 == t2))
  { // A
    return(MK(t0,0,h0));
  }
 else if ((t0 == t1) && (t0 < t2))
  { // B
    return(MK(t0,0,h0));
  }
 else if ((t0 == t2) && (t0 < t1))
  { // C
    return(MK(t0,0,h0));
  }
 else if ((t1 == t2) && (t1 < t0))
  { // D
    return(MK(t1,1,h1));
  }
 else if ((t0 < t1) && (t0 < t2))
  { // E
    return(MK(t0,0,h0));
  }
 else if ((t1 < t0) && (t1 < t2))
  { // F
    return(MK(t1,1,h1));
  }
 else if ((t2 < t0) && (t2 < t1))
  { // G
    return(MK(t2,2,h2));
  }
 abort();
}

void optimal_quote(FILE *f, const char *s)
{
 int l;
 CELL (*c)[3];
 CELL *path;
 int i;
 int k;
 CELL cur;
 int trail;

 l = strlen(s);
 if (l < 1)
  { fprintf(f,"''");
    return;
  }
 c = malloc((l+1)*sizeof(*c));
 path = malloc((l+1)*sizeof(*path));
 c[0][0] = MK(how_cost[HOW_NULL][0],0,HOW_NULL);
 c[0][1] = MK(how_cost[HOW_DOUBLE_S][0],0,HOW_DOUBLE_S);
 c[0][2] = MK(how_cost[HOW_DOUBLE_D][0],0,HOW_DOUBLE_D);
 for (i=1;i<=l;i++)
  { switch (s[i-1])
     { case '%': case '+': case ',': case '-': case '.': case '/':
       case ':': case '=': case '@': case '_':
       case '0': case '1': case '2': case '3': case '4':
       case '5': case '6': case '7': case '8': case '9':
       case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
       case 'G': case 'H': case 'I': case 'J': case 'K': case 'L':
       case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R':
       case 'S': case 'T': case 'U': case 'V': case 'W': case 'X':
       case 'Y': case 'Z':
       case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
       case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
       case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
       case 's': case 't': case 'u': case 'v': case 'w': case 'x':
       case 'y': case 'z':
	  c[i][0] = best(&c[i-1][0],HOW_SIMPLE,HOW_SIMPLE,HOW_SIMPLE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE,HOW_INSIDE_S,HOW_S_QUOTE);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE,HOW_D_QUOTE,HOW_INSIDE_D);
	  break;
       case '"':
	  c[i][0] = best(&c[i-1][0],HOW_B_QUOTE,HOW_B_QUOTE,HOW_B_QUOTE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE,HOW_INSIDE_S,HOW_S_QUOTE);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE_B,HOW_D_QUOTE_B,HOW_INSIDE_D_B);
	  break;
       case '$':
	  c[i][0] = best(&c[i-1][0],HOW_B_QUOTE,HOW_B_QUOTE,HOW_B_QUOTE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE,HOW_INSIDE_S,HOW_S_QUOTE);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE_B,HOW_D_QUOTE_B,HOW_INSIDE_D_B);
	  break;
       case '\'':
	  c[i][0] = best(&c[i-1][0],HOW_B_QUOTE,HOW_B_QUOTE,HOW_B_QUOTE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE_B,HOW_B_S_S_S,HOW_S_QUOTE_B);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE,HOW_D_QUOTE,HOW_INSIDE_D);
	  break;
       case '\\':
	  c[i][0] = best(&c[i-1][0],HOW_B_QUOTE,HOW_B_QUOTE,HOW_B_QUOTE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE,HOW_INSIDE_S,HOW_S_QUOTE);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE_B,HOW_D_QUOTE_B,HOW_INSIDE_D_B);
	  break;
       default:
	  c[i][0] = best(&c[i-1][0],HOW_B_QUOTE,HOW_B_QUOTE,HOW_B_QUOTE);
	  c[i][1] = best(&c[i-1][0],HOW_S_QUOTE,HOW_INSIDE_S,HOW_S_QUOTE);
	  c[i][2] = best(&c[i-1][0],HOW_D_QUOTE,HOW_D_QUOTE,HOW_INSIDE_D);
	  break;
     }
  }
 k = 0;
 if (c[l][1].val < c[l][0].val) k = 1;
 if (c[l][2].val < c[l][k].val) k = 2;
 for (i=l;i>=0;i--)
  { cur = c[i][k];
    path[i] = cur;
    k = cur.from;
  }
 trail = -1;
 for (i=0;i<=l;i++)
  { cur = path[i];
    switch (cur.how)
     { case HOW_NULL:
	  if (i) abort();
	  break;
       case HOW_DOUBLE_S:
	  if (i) abort();
	  putc('\'',f);
	  trail = '\'';
	  break;
       case HOW_DOUBLE_D:
	  if (i) abort();
	  putc('"',f);
	  trail = '"';
	  break;
       case HOW_SIMPLE:
	  if (trail >= 0) putc(trail,f);
	  trail = s[i-1];
	  break;
       case HOW_INSIDE_S:
	  if (trail != '\'') abort();
	  putc(s[i-1],f);
	  break;
       case HOW_INSIDE_D:
	  if (trail != '"') abort();
	  putc(s[i-1],f);
	  break;
       case HOW_S_QUOTE:
	  if (trail >= 0) putc(trail,f);
	  fprintf(f,"'%c",s[i-1]);
	  trail = '\'';
	  break;
       case HOW_D_QUOTE:
	  if (trail >= 0) putc(trail,f);
	  fprintf(f,"\"%c",s[i-1]);
	  trail = '"';
	  break;
       case HOW_B_QUOTE:
	  if (trail >= 0) putc(trail,f);
	  putc('\\',f);
	  trail = s[i-1];
	  break;
       case HOW_S_QUOTE_B:
	  if (trail >= 0) putc(trail,f);
	  fprintf(f,"'\\%c",s[i-1]);
	  trail = '\'';
	  break;
       case HOW_D_QUOTE_B:
	  if (trail >= 0) putc(trail,f);
	  fprintf(f,"\"\\%c",s[i-1]);
	  trail = '"';
	  break;
       case HOW_INSIDE_D_B:
	  if (trail != '"') abort();
	  fprintf(f,"\\%c",s[i-1]);
	  break;
       case HOW_B_S_S_S:
	  if (trail >= 0) putc(trail,f);
	  fprintf(f,"\\''");
	  trail = '\'';
	  break;
       default:
	  abort();
	  break;
     }
  }
 if (trail < 0) abort();
 putc(trail,f);
 free(c);
 free(path);
}

#ifdef TESTBED

int main(void);
int main(void)
{
 char str[64];
 int l;

 while (1)
  { if (! fgets(&str[0],sizeof(str),stdin)) break;
    l = strlen(&str[0]);
    if ((l > 0) && (str[l-1] == '\n')) str[--l] = '\0';
    optimal_quote(stdout,&str[0]);
    printf("\n");
  }
 return(0);
}

#endif