int subchild(int trip, int k) { // k = 1..displayable children
  int kids = op[AST[trip]-AST_BASE].Children; // eg 2
  int mask = op[AST[trip]-AST_BASE].Display_Children; // eg 3
  int bit = 1 << (kids-1); // 2,1,0
  int index = 0; // 0..1
  int child = 0;// 0..display children-1   0..1

  k = k-1; // eg 3..0  0, 1 from external loop
  for (;;) {
    if (bit & mask) {
      // this is child #child
      if (child == k) return nthchild(trip, index);
      child += 1;
    }
    bit = bit >> 1; index = index + 1;
  }
}
int countbits(int n) {
  int tot = 0;
  while (n != 0) {
    if (n&1) tot += 1; n = n>>1;
  }
  return tot;
}
//#define nameof(p) op[AST[p]-AST_BASE].C_Name
char *nameof(int t)
{
  int opc,poolptr;
  char *result = stringpool+nextstring;
  /* Extract the name of a variable or the value of a const.  */

  if (t == -1) {
    sprintf(result, "(null)");
  } else {
    opc = astop(t);
    if (opc == AST_Const) {
      sprintf(result, "%d", rightchild(t));
    } else if (opc == AST_TAG) { // for simpler diagrams, skip a level
      sprintf(result, "%s", c[leftchild(t)].s);
    } else {
      if ((opc < AST_BASE) || (opc > AST_TOP)) {
        sprintf(result, "%s", "Bad!");
      } else {
        sprintf(result, "%s", op[opc-AST_BASE].C_Name);
      }
    }
  }
  poolptr = str_to_pool(result);
  if (poolptr == nextstring) nextstring += strlen(result)+1; /* Not found, add it */
  return(stringpool+poolptr);
}

#define display_leftchild(p) ((op[(p)-AST_BASE].Children >= 2) &&	\
			      (((2 << (op[(p)-AST_BASE].Children-2)) & op[(p)-AST_BASE].Display_Children) != 0))
#define display_rightchild(p) ((op[(p)-AST_BASE].Children >= 2) &&	\
			       (((1 << (op[(p)-AST_BASE].Children-2)) & op[(p)-AST_BASE].Display_Children) != 0))
#define display_children(p) countbits(op[(p)-AST_BASE].Display_Children)
/* Ascii-art debugging procedure for drawing trees */

int del = 4/*was 1*/; /* distance of graph columns */
int eps = 3; /* distance of graph lines */

/* interface for drawing (can be replaced by "real" graphic using GD or other) */
void graphInit (void);
void graphFinish();
void graphBox (char *s, int *w, int *h);
void graphDrawBox (char *s, int c, int l);
void graphDrawArrow (int c1, int l1, int c2, int l2);

/* recursive drawing of the syntax tree */
void exNode (int trip, int c, int l, int *ce, int *cm, int depth, int *needed);

/*****************************************************************************/

/* main entry point of the manipulation of the syntax tree */

/* draw_tree is taken from the yacc/lex demo by Thomas Niemann
   at http://epaperpress.com/lexandyacc/

   I wrote an ascii tree-drawing package of my own, but it does not
   handle nodes with more than 2 children.  My package uses diagonal
   links and Niemann's uses a rectilinear grid; when possible I use
   my own package as the diagonal tree looks more natural, falling back
   to the rectilinear layout only when necessary.  They cannot be mixed
   within the one display.

   I'm in the process of adding a third option, which is to use the
   graphical layout language of DOT and generate images rather than
   ascii art, so that the images can be embedded in HTML output.

 */

void draw_tree_orig(int root);

void dottree(int root)
{
  char *operator;
  int leftkid, rightkid;
  int linkno = 0;

  operator = nameof(root);
  leftkid = leftchild(root);
  rightkid = rightchild(root);

  fprintf(stdout, "\"node%d\" [\n   label = \"<f0> %d: %s ", root, root, operator);
  if (display_leftchild(astop(root))) fprintf(stdout, "| <f%0d> %d: ", ++linkno, root+1);
  if (display_rightchild(astop(root))) fprintf(stdout, "| <f%0d> %d: ", ++linkno, root+2);
  linkno = 0;

  fprintf(stdout, "\"\n   shape = \"record\"\n];\n\n");

  if (display_leftchild(astop(root))) dottree(leftkid);
  if (display_rightchild(astop(root))) dottree(rightkid);

  if (display_leftchild(astop(root)))
      fprintf(stdout, "\"node%0d\":f1 -> \"node%0d\":f0 [\n id = %d\n];\n\n",
              root, leftchild(root), 888);
  if (display_rightchild(astop(root)))
      fprintf(stdout, "\"node%0d\":f2 -> \"node%0d\":f0 [\n id = %d\n];\n\n",
	      root, rightchild(root), 999);
}

void draw_tree(int trip) {
    int rte, rtm, needed;

    fprintf(stdout, "\nTree for AST[%d]:\n", trip);

    graphInit ();
    needed = FALSE;
    exNode (trip, 0, 0, &rte, &rtm, 0, &needed);
    if (needed) {
      graphFinish();
    } else {
      draw_tree_orig(trip);
    }

#ifdef DOT_SUPPORT
    fprintf(stdout, "digraph g {\n");
    fprintf(stdout, "graph [\n");
    fprintf(stdout, "   rankdir = \"LR\"\n");
    fprintf(stdout, "];\n\n");
    fprintf(stdout, "node [\n");
    fprintf(stdout, "   fontsize = \"16\"\n");
    fprintf(stdout, "   shape = \"ellipse\"\n");
    fprintf(stdout, "];\n\n");
    fprintf(stdout, "edge [\n");
    fprintf(stdout, "];\n\n");
    dottree(trip);
    fprintf(stdout, "}\n");
#endif

}

/*c----cm---ce---->                       drawing of leaf-nodes
 l leaf-info
 */

/*c---------------cm--------------ce----> drawing of non-leaf-nodes
 l            node-info
 *                |
 *    -------------     ...----
 *    |       |               |
 *    v       v               v
 * child1  child2  ...     child-n
 *        che     che             che
 *cs      cs      cs              cs
 *
 */

void indentsp(int d)
{
  int i;
  for (i = 0; i < d*4; i++) {
    putchar(' ');
  }
}

void exNode
    (   int trip,
        int c, int l,        /* start column and line of node */
        int *ce, int *cm,    /* resulting end column and mid of node */
        int depth, int *needed
    )
{
    int opc;
    int w, h;           /* node width and height */
    char *s;            /* node text */
    int cbar;           /* "real" start column of node (centred above subnodes) */
    int k;              /* child number */
    int che, chm;       /* end column and mid of children */
    int cs;             /* start column of children */
    char word[40];

//indentsp(depth);fprintf(stdout, "start: TRIP=%d  startcol=%d  startline=%d\n", trip, c, l);

    if (trip == -1) return;
    opc = astop(trip);
    if (display_children(opc) >= 3) *needed = TRUE;

    s = nameof(trip);
    sprintf(word, "%s", s);
    s = word;

//indentsp(depth);fprintf(stdout, "graphbox: s = %s\n", s);

    /* construct node text box */
    graphBox (s, &w, &h);
    cbar = c;
//indentsp(depth);fprintf(stdout, "assign: c=%d\n", c);
    *ce = c + w;
    *cm = c + w / 2;

    /* node is leaf */
    if (
         (opc == AST_Const ||
          opc == AST_TAG ||
          display_children(opc) == 0)
       ) {
//indentsp(depth);fprintf(stdout, "drawbox: s = %s  cbar=%d\n", s, cbar);
        graphDrawBox (s, cbar, l);
        return;
    }

    /* node has children */
    cs = c;
//indentsp(depth);fprintf(stdout, "node has %d children: cs=c=%d\n", display_children(opc), c);
    for (k = 1; k <= display_children(opc); k++) {
//indentsp(depth);fprintf(stdout, "%d: exnode1 %d  cs=%d\n", k, subchild(trip, k), cs);
        exNode (subchild(trip, k), cs, l+h+eps, &che, &chm, depth+1, needed);
        cs = che;
    }

    /* total node width */
    if (w < che - c) {
        cbar += (che - c - w) / 2;
        *ce = che;
        *cm = (c + che) / 2;
    }

    /* draw node */
//indentsp(depth);fprintf(stdout, "cbar=%d\n", cbar);
    graphDrawBox (s, cbar, l);

    /* draw arrows (not optimal: children are drawn a second time) */
    cs = c;
    for (k = 1; k <= display_children(opc); k++) {
//indentsp(depth);fprintf(stdout, "%d: exnode2 %d  cs=%d\n", k, subchild(trip, k), cs);
        exNode (subchild(trip, k), cs, l+h+eps, &che, &chm, depth+1, needed);
        graphDrawArrow (*cm, l+h, chm, l+h+eps-1);
        cs = che;
    }
}

/* interface for drawing */

#define lmax 2000
#define cmax 2000

char graph[lmax][cmax]; /* array for ASCII-Graphic */

void graphTest (int l, int c)
{   int ok;
    ok = 1;
    if (l < 0) ok = 0;
    if (l >= lmax) ok = 0;
    if (c < 0) ok = 0;
    if (c >= cmax) ok = 0;
    if (ok) return;
    printf ("\n+++error: l=%d, c=%d not in drawing rectangle 0, 0 ... %d, %d", 
        l, c, lmax, cmax);
//    fprintf (stderr, "\n+++error: l=%d, c=%d not in drawing rectangle 0, 0 ... %d, %d", 
//        l, c, lmax, cmax);
    {
    int i, j;
    int lmx=20, cmx=60;
    for (i = 0; i < lmx; i++) {
        for (j = cmx-1; j > 0 && graph[i][j] == ' '; j--);
        graph[i][cmx-1] = 0;
        if (j < cmx-1) graph[i][j+1] = 0;
        if (graph[i][j] == ' ') graph[i][j] = 0;
    }
    for (i = lmx-1; i > 0 && graph[i][0] == 0; i--);
    printf ("\n");
    for (j = 0; j <= i; j++) printf ("\n    // %s", graph[j]);
    printf("\n");
    };
    exit (1);
}

void graphInit (void) {
    int i, j;
    for (i = 0; i < lmax; i++) {
        for (j = 0; j < cmax; j++) {
            graph[i][j] = ' ';
        }
    }
}

void graphFinish() {
    int i, j;
    char *s;
    for (i = 0; i < lmax; i++) {
        for (j = cmax-1; j > 0 && graph[i][j] == ' '; j--);
        graph[i][cmax-1] = 0;
        if (j < cmax-1) graph[i][j+1] = 0;
        if (graph[i][j] == ' ') graph[i][j] = 0;
    }
    for (i = lmax-1; i > 0 && graph[i][0] == 0; i--);
    printf ("\n");

    for (j = 0; j <= i; j++) {
      char *p;
      s = graph[j];
      // hacks to slightly improve formatting
      if (j == 0) s += 2;
      else if (j == 1) s += 1;
      else if ((p=strchr(s, '|')) == NULL || p[1]=='|') s += 2;
      printf ("\n    // %s", s);
    }
    printf("\n\n");
}

void graphBox (char *s, int *w, int *h) {
    *w = strlen (s) + del;
    *h = 1;
}

void graphDrawBox (char *s, int c, int l) {
    int i;
//fprintf(stdout, "c=%d strlen=%d del=%d\n", c, strlen(s), del);
    graphTest (l, c+strlen(s)-1+del);
    for (i = 0; i < strlen (s); i++) {
        graph[l][c+i+del] = s[i];
    }
}

void graphDrawArrow (int c1, int l1, int c2, int l2) {
    int m;
    graphTest (l1, c1);
    graphTest (l2, c2);
    m = (l1 + l2) / 2;
    while (l1 != m) { graph[l1][c1] = '|'; if (l1 < l2) l1++; else l1--; }
    while (c1 != c2) { graph[l1][c1] = '-'; if (c1 < c2) c1++; else c1--; }
    while (l1 != l2) { graph[l1][c1] = '|'; if (l1 < l2) l1++; else l1--; }
    graph[l1][c1] = '|';
}

/*-----------------------------------------------------------------------*/

/*-----------------------------------------------------------------------*/
/* See drawtree.c for test harness.  Small mods made for this interface. */
/* NOTE!!! Now we have n-ary trees, this will not work.  ifthenelse breaks */
static int tree_debug = (0!=0);
static int vertical = (0==0);
static int horizontal = (0==0);
static int wide = (0==0);
static int trim = (0==0);
static int testone = (0==0);

//       row  col
long pic[256][256]; // 0..255 is char, >= 256 is ptr to string (poolptr index?)


int oldtextblit(int row, int col, char *src)
{
  // post-processing string expansion
  int l = 0;
  for (;;) {
    if (*src == '\0') break;
    if (tree_debug) fprintf(stderr, "1: Planting '%c' at [%d][%d]\n", *src, row, col);
    pic[row][col] = *src; col += 1; src += 1;
    l += 1;
  }
  return l;
}

int textblit(int row, int col, char *src)
{
  // store pointer to string, unpack later on output
  int l = strlen(src), poolptr;
  strcpy(stringpool+nextstring, src);
  poolptr = str_to_pool(src);
  if (poolptr == nextstring) nextstring += strlen(src)+1; /* Not found, add it */
  if (tree_debug) fprintf(stderr, "?: Planting string '%s' at [%d][%d]\n", src, row, col);
  pic[row][col] = 256+poolptr;
  return (l+(wide?3:1))>>(wide?2:1); // half size because on diagonal
}

void layout(int id, int idx, int rowoff, int coloff, int *depth, int *width)
{
  char *operator;
  int opc;
  int leftkid, rightkid;
  int leftkiddepth = 0, leftkidwidth = 0;
  int rightkiddepth = 0, rightkidwidth = 0;
  int deltadepth = 0, deltawidth = 0;
  int i;

  if (tree_debug) fprintf(stderr, ">> %d:layout(%d, rowcol[%d][%d], depth %d, width %d);\n", id, idx, rowoff, coloff, *depth, *width);

  if (idx == -1) return; // was NOOP, now (null)

  operator = nameof(idx);
  leftkid = leftchild(idx);
  rightkid = rightchild(idx);

  // Anchor the corner node.
  {
    static char temp[128];
    sprintf(temp, "%s", operator);
    (void)textblit(rowoff, coloff, temp); /* not strcpy - don't copy NUL */
  }
  deltawidth = 1;
  if (display_rightchild(astop(idx))) {
    int len = ((strlen(nameof(leftkid))+(wide?3:1))>>(wide?2:1))+1; // text on the diagonal
    while (len-- > 1) {
      deltawidth += 1; pic[rowoff][coloff-1+deltawidth] = (vertical ? '\\' : '-');
      if (tree_debug) fprintf(stderr, "2: Planting '%c' at [%d][%d]\n", pic[rowoff][coloff-1+deltawidth], rowoff, coloff-1+deltawidth);
    }
    // attach the RHS tree
    if (tree_debug) fprintf(stderr, "Recursing to right node %d\n", rightkid);
    layout(2*id, rightkid, rowoff, coloff+deltawidth, &rightkiddepth, &rightkidwidth);
    deltadepth = rightkiddepth;
  } else {
    deltadepth = 1; /* The op itself */
  }
// testing: correcting a typo
  if (((strlen(operator)+(wide?3:1))>>(wide?2:1)) >= deltawidth) deltawidth = ((strlen(operator)+(wide?3:1))>>(wide?2:1))+2;

  if (display_leftchild(astop(idx))) {
    // draw the down link

    // calculate extra height
    if ((((strlen(nameof(leftkid))+(wide?3:1))>>(wide?2:1))) > deltadepth) {
      deltadepth = ((strlen(nameof(leftkid))+(wide?3:1))>>(wide?2:1));
    }

    for (i = 1; i < deltadepth+1 /* +1 for spacer row */; i++) {
      pic[rowoff+i][coloff] = (horizontal ? '/' : '|');
      if (tree_debug) fprintf(stderr, "2: Planting '%c' at [%d][%d]\n", pic[rowoff+i][coloff], rowoff+i, coloff);
    }
    // recurse on the LHS tree
    if (tree_debug) fprintf(stderr, "Recursing to left node %d\n", leftkid);
    layout(2*id+1, leftkid, rowoff+deltadepth+1, coloff, &leftkiddepth, &leftkidwidth);
    *depth = (*depth) + leftkiddepth + deltadepth + 1;
  } else *depth = (*depth) + deltadepth;

  if (rightkidwidth+deltawidth > leftkidwidth) {
    *width = (rightkidwidth+deltawidth);
  } else {
    *width = leftkidwidth;
  }

  if (tree_debug) fprintf(stderr, "<< %d:layout(%d, rowcol[%d][%d], depth %d, width %d);\n", id, idx, rowoff, coloff, *depth, *width);
}

void draw_tree_orig(int root)
{
  int depth = 0, width = 0, row, col, offset, trimmable;

  fprintf(stdout, "\n");
  // Init.
  for (col = 0; col < 256; col++) {
    for (row = 0; row < 256; row++) {
      pic[row][col] = ' ';
    }
  }

  /* Generate layout */
  layout(1, root, 128, 0, &depth, &width);

  if (tree_debug) fprintf(stderr, "Dump layout: rows = %d cols = %d\n", depth, width);
  if (tree_debug) fflush(stderr);

  if (vertical) {
    /* apply vertical shear first */
    offset = 1;
    for (col = 1; col < 256; col++) {
      // move this column down by 'offset'
      for (row = 255; row > offset; row--) {
        pic[row][col] = pic[row-offset][col]; pic[row-offset][col] = ' ';
      }
      offset += 1;
    }
  }

  if (horizontal) {
    /* apply horizontal shear next */
    row = 255;  // start at bottom of drawing
    offset = 0;
    for (;;) {
      static long temp[1024];
      for (col = 0; col < 256; col++) {
        temp[col] = ' ';
      }
      for (col = 0; col < 256; col++) {
        temp[col*2+offset] = pic[row][col];
        temp[col*2+offset+1] = ' ';
      }
      for (col = 0; col < 256; col++) {
        pic[row][col] = temp[col];
      }
      if (row == 0) break;
      offset += 1; /* more shear on next row up */
      row -= 1;
    }
  }

  if (trim) {
    trimmable = (0==0);
    for (;;) {
      for (row = 0; row < 256; row++) {
        if (pic[row][0] != ' ') {
          trimmable = (0!=0);
          break;
        }
      }
      if (!trimmable) break;
      for (row = 0; row < 256; row++) {
        for (col = 0; col+1 < 256; col++) {
          pic[row][col] = pic[row][col+1];
        }
        pic[row][255] = ' ';
      }
    }
  }

  if (wide) {
    /* apply widening last */
    row = 255;  // start at bottom of drawing
    offset = 0;
    for (;;) {
      static long temp[1024];
      for (col = 0; col < 256; col++) {
        temp[col] = ' ';
      }
      for (col = 0; col < 256; col++) {
        temp[col*2+offset] = pic[row][col];
        temp[col*2+offset+1] = ' ';
      }
      for (col = 0; col < 256; col++) {
        pic[row][col] = temp[col];
      }
      if (row == 0) break;
      row -= 1;
    }
  }

  /* display tree */
  for (row = 0; row < 256; row++) {
    trimmable = (0 == 0);
    for (col = 0; col < 256; col++) {
      if (pic[row][col] != ' ') {
        trimmable = (0!=0);
        break;
      }
    }
    if (!trimmable) {
      fprintf(stdout, "  ");  // INDENT
      for (col = 255; col >= 0; col--) {
        if (pic[row][col] != ' ') break;
        pic[row][col] = '\0';
      }
      printf("  //    ");
      for (col = 0; col < 256; col++) {
        if ((pic[row][col] < -128) || (pic[row][col] > 255)) {
	  //fprintf(stderr, "Inserting \"%s\"\n", &stringpool[pic[row][col]-256]);
	  // col+1 was a hacky bugfix for losing first char of string
          oldtextblit(row, col+1, &stringpool[pic[row][col]-256]); // strings painted here...
        } else {
          if (pic[row][col] == '\0') break;
          putchar(pic[row][col]);
	}
      }
      putchar('\n');
    }
  }
  putchar('\n');
  fflush(stdout);
  return;
}