/*
 * colorings of characters
 * This file is #included by regcomp.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/backend/regex/regc_color.c
 *
 *
 * Note that there are some incestuous relationships between this code and
 * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
 */



#define CISERR() VISERR(cm->v)
#define CERR(e)  VERR(cm->v, (e))



/*
 * initcm - set up new colormap
 */
static void
initcm(struct vars *v,
    struct colormap *cm)
{
 struct colordesc *cd;

 cm->magic = CMMAGIC;
 cm->v = v;

 cm->ncds = NINLINECDS;
 cm->cd = cm->cdspace;
 cm->max = 0;
 cm->free = 0;

 cd = cm->cd;    /* cm->cd[WHITE] */
 cd->nschrs = MAX_SIMPLE_CHR - CHR_MIN + 1;
 cd->nuchrs = 1;
 cd->sub = NOSUB;
 cd->arcs = NULL;
 cd->firstchr = CHR_MIN;
 cd->flags = 0;

 cm->locolormap = (color *)
  MALLOC((MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
 if (cm->locolormap == NULL)
 {
  CERR(REG_ESPACE);
  cm->cmranges = NULL; /* prevent failure during freecm */
  cm->hicolormap = NULL;
  return;
 }
 /* this memset relies on WHITE being zero: */
 memset(cm->locolormap, WHITE,
     (MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));

 memset(cm->classbits, 0, sizeof(cm->classbits));
 cm->numcmranges = 0;
 cm->cmranges = NULL;
 cm->maxarrayrows = 4;  /* arbitrary initial allocation */
 cm->hiarrayrows = 1;  /* but we have only one row/col initially */
 cm->hiarraycols = 1;
 cm->hicolormap = (color *) MALLOC(cm->maxarrayrows * sizeof(color));
 if (cm->hicolormap == NULL)
 {
  CERR(REG_ESPACE);
  return;
 }
 /* initialize the "all other characters" row to WHITE */
 cm->hicolormap[0] = WHITE;
}

/*
 * freecm - free dynamically-allocated things in a colormap
 */
static void
freecm(struct colormap *cm)
{
 cm->magic = 0;
 if (cm->cd != cm->cdspace)
  FREE(cm->cd);
 if (cm->locolormap != NULL)
  FREE(cm->locolormap);
 if (cm->cmranges != NULL)
  FREE(cm->cmranges);
 if (cm->hicolormap != NULL)
  FREE(cm->hicolormap);
}

/*
 * pg_reg_getcolor - slow case of GETCOLOR()
 */
color
pg_reg_getcolor(struct colormap *cm, chr c)
{
 int   rownum,
    colnum,
    low,
    high;

 /* Should not be used for chrs in the locolormap */
 assert(c > MAX_SIMPLE_CHR);

 /*
  * Find which row it's in.  The colormapranges are in order, so we can use
  * binary search.
 */
 rownum = 0;     /* if no match, use array row zero */
 low = 0;
 high = cm->numcmranges;
 while (low < high)
 {
  int   middle = low + (high - low) / 2;
  const colormaprange *cmr = &cm->cmranges[middle];

  if (c < cmr->cmin)
   high = middle;
  else if (c > cmr->cmax)
   low = middle + 1;
  else
  {
   rownum = cmr->rownum; /* found a match */
   break;
  }
 }

 /*
  * Find which column it's in --- this is all locale-dependent.
 */
 if (cm->hiarraycols > 1)
 {
  colnum = cclass_column_index(cm, c);
  return cm->hicolormap[rownum * cm->hiarraycols + colnum];
 }
 else
 {
  /* fast path if no relevant cclasses */
  return cm->hicolormap[rownum];
 }
}

/*
 * maxcolor - report largest color number in use
 */
static color
maxcolor(struct colormap *cm)
{
 if (CISERR())
  return COLORLESS;

 return (color) cm->max;
}

/*
 * newcolor - find a new color (must be assigned at once)
 * Beware: may relocate the colordescs.
 */
static color     /* COLORLESS for error */
newcolor(struct colormap *cm)
{
 struct colordesc *cd;
 size_t  n;

 if (CISERR())
  return COLORLESS;

 if (cm->free != 0)
 {
  assert(cm->free > 0);
  assert((size_t) cm->free < cm->ncds);
  cd = &cm->cd[cm->free];
  assert(UNUSEDCOLOR(cd));
  assert(cd->arcs == NULL);
  cm->free = cd->sub;
 }
 else if (cm->max < cm->ncds - 1)
 {
  cm->max++;
  cd = &cm->cd[cm->max];
 }
 else
 {
  /* oops, must allocate more */
  struct colordesc *newCd;

  if (cm->max == MAX_COLOR)
  {
   CERR(REG_ECOLORS);
   return COLORLESS; /* too many colors */
  }

  n = cm->ncds * 2;
  if (n > MAX_COLOR + 1)
   n = MAX_COLOR + 1;
  /* the MAX_COLOR+1 limit ensures these alloc sizes can't overflow: */
  if (cm->cd == cm->cdspace)
  {
   newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
   if (newCd != NULL)
    memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
        sizeof(struct colordesc));
  }
  else
   newCd = (struct colordesc *)
    REALLOC(cm->cd, n * sizeof(struct colordesc));
  if (newCd == NULL)
  {
   CERR(REG_ESPACE);
   return COLORLESS;
  }
  cm->cd = newCd;
  cm->ncds = n;
  assert(cm->max < cm->ncds - 1);
  cm->max++;
  cd = &cm->cd[cm->max];
 }

 cd->nschrs = 0;
 cd->nuchrs = 0;
 cd->sub = NOSUB;
 cd->arcs = NULL;
 cd->firstchr = CHR_MIN;  /* in case never set otherwise */
 cd->flags = 0;

 return (color) (cd - cm->cd);
}

/*
 * freecolor - free a color (must have no arcs or subcolor)
 */
static void
freecolor(struct colormap *cm,
    color co)
{
 struct colordesc *cd = &cm->cd[co];
 color  pco,
    nco;   /* for freelist scan */

 assert(co >= 0);
 if (co == WHITE)
  return;

 assert(cd->arcs == NULL);
 assert(cd->sub == NOSUB);
 assert(cd->nschrs == 0);
 assert(cd->nuchrs == 0);
 cd->flags = FREECOL;

 if ((size_t) co == cm->max)
 {
  while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
   cm->max--;
  assert(cm->free >= 0);
  while ((size_t) cm->free > cm->max)
   cm->free = cm->cd[cm->free].sub;
  if (cm->free > 0)
  {
   assert(cm->free < cm->max);
   pco = cm->free;
   nco = cm->cd[pco].sub;
   while (nco > 0)
    if ((size_t) nco > cm->max)
    {
     /* take this one out of freelist */
     nco = cm->cd[nco].sub;
     cm->cd[pco].sub = nco;
    }
    else
    {
     assert(nco < cm->max);
     pco = nco;
     nco = cm->cd[pco].sub;
    }
  }
 }
 else
 {
  cd->sub = cm->free;
  cm->free = (color) (cd - cm->cd);
 }
}

/*
 * pseudocolor - allocate a false color, to be managed by other means
 */
static color
pseudocolor(struct colormap *cm)
{
 color  co;
 struct colordesc *cd;

 co = newcolor(cm);
 if (CISERR())
  return COLORLESS;
 cd = &cm->cd[co];
 cd->nschrs = 0;
 cd->nuchrs = 1;    /* pretend it is in the upper map */
 cd->sub = NOSUB;
 cd->arcs = NULL;
 cd->firstchr = CHR_MIN;
 cd->flags = PSEUDO;
 return co;
}

/*
 * subcolor - allocate a new subcolor (if necessary) to this chr
 *
 * This works only for chrs that map into the low color map.
 */
static color
subcolor(struct colormap *cm, chr c)
{
 color  co;    /* current color of c */
 color  sco;   /* new subcolor */

 assert(c <= MAX_SIMPLE_CHR);

 co = cm->locolormap[c - CHR_MIN];
 sco = newsub(cm, co);
 if (CISERR())
  return COLORLESS;
 assert(sco != COLORLESS);

 if (co == sco)    /* already in an open subcolor */
  return co;    /* rest is redundant */
 cm->cd[co].nschrs--;
 if (cm->cd[sco].nschrs == 0)
  cm->cd[sco].firstchr = c;
 cm->cd[sco].nschrs++;
 cm->locolormap[c - CHR_MIN] = sco;
 return sco;
}

/*
 * subcolorhi - allocate a new subcolor (if necessary) to this colormap entry
 *
 * This is the same processing as subcolor(), but for entries in the high
 * colormap, which do not necessarily correspond to exactly one chr code.
 */
static color
subcolorhi(struct colormap *cm, color *pco)
{
 color  co;    /* current color of entry */
 color  sco;   /* new subcolor */

 co = *pco;
 sco = newsub(cm, co);
 if (CISERR())
  return COLORLESS;
 assert(sco != COLORLESS);

 if (co == sco)    /* already in an open subcolor */
  return co;    /* rest is redundant */
 cm->cd[co].nuchrs--;
 cm->cd[sco].nuchrs++;
 *pco = sco;
 return sco;
}

/*
 * newsub - allocate a new subcolor (if necessary) for a color
 */
static color
newsub(struct colormap *cm,
    color co)
{
 color  sco;   /* new subcolor */

 sco = cm->cd[co].sub;
 if (sco == NOSUB)
 {       /* color has no open subcolor */
  /* optimization: singly-referenced color need not be subcolored */
  if ((cm->cd[co].nschrs + cm->cd[co].nuchrs) == 1)
   return co;
  sco = newcolor(cm);  /* must create subcolor */
  if (sco == COLORLESS)
  {
   assert(CISERR());
   return COLORLESS;
  }
  cm->cd[co].sub = sco;
  cm->cd[sco].sub = sco; /* open subcolor points to self */
 }
 assert(sco != NOSUB);

 return sco;
}

/*
 * newhicolorrow - get a new row in the hicolormap, cloning it from oldrow
 *
 * Returns array index of new row.  Note the array might move.
 */
static int
newhicolorrow(struct colormap *cm,
     int oldrow)
{
 int   newrow = cm->hiarrayrows;
 color    *newrowptr;
 int   i;

 /* Assign a fresh array row index, enlarging storage if needed */
 if (newrow >= cm->maxarrayrows)
 {
  color    *newarray;

  if (cm->maxarrayrows >= INT_MAX / (cm->hiarraycols * 2))
  {
   CERR(REG_ESPACE);
   return 0;
  }
  newarray = REALLOC_ARRAY(cm->hicolormap, color,
         cm->maxarrayrows * 2 * cm->hiarraycols);
  if (newarray == NULL)
  {
   CERR(REG_ESPACE);
   return 0;
  }
  cm->hicolormap = newarray;
  cm->maxarrayrows *= 2;
 }
 cm->hiarrayrows++;

 /* Copy old row data */
 newrowptr = &cm->hicolormap[newrow * cm->hiarraycols];
 memcpy(newrowptr,
     &cm->hicolormap[oldrow * cm->hiarraycols],
     cm->hiarraycols * sizeof(color));

 /* Increase color reference counts to reflect new colormap entries */
 for (i = 0; i < cm->hiarraycols; i++)
  cm->cd[newrowptr[i]].nuchrs++;

 return newrow;
}

/*
 * newhicolorcols - create a new set of columns in the high colormap
 *
 * Essentially, extends the 2-D array to the right with a copy of itself.
 */
static void
newhicolorcols(struct colormap *cm)
{
 color    *newarray;
 int   r,
    c;

 if (cm->hiarraycols >= INT_MAX / (cm->maxarrayrows * 2))
 {
  CERR(REG_ESPACE);
  return;
 }
 newarray = REALLOC_ARRAY(cm->hicolormap, color,
        cm->maxarrayrows * cm->hiarraycols * 2);
 if (newarray == NULL)
 {
  CERR(REG_ESPACE);
  return;
 }
 cm->hicolormap = newarray;

 /* Duplicate existing columns to the right, and increase ref counts */
 /* Must work backwards in the array because we realloc'd in place */
 for (r = cm->hiarrayrows - 1; r >= 0; r--)
 {
  color    *oldrowptr = &newarray[r * cm->hiarraycols];
  color    *newrowptr = &newarray[r * cm->hiarraycols * 2];
  color    *newrowptr2 = newrowptr + cm->hiarraycols;

  for (c = 0; c < cm->hiarraycols; c++)
  {
   color  co = oldrowptr[c];

   newrowptr[c] = newrowptr2[c] = co;
   cm->cd[co].nuchrs++;
  }
 }

 cm->hiarraycols *= 2;
}

/*
 * subcolorcvec - allocate new subcolors to cvec members, fill in arcs
 *
 * For each chr "c" represented by the cvec, do the equivalent of
 * newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);
 *
 * Note that in typical cases, many of the subcolors are the same.
 * While newarc() would discard duplicate arc requests, we can save
 * some cycles by not calling it repetitively to begin with.  This is
 * mechanized with the "lastsubcolor" state variable.
 */
static void
subcolorcvec(struct vars *v,
    struct cvec *cv,
    struct state *lp,
    struct state *rp)
{
 struct colormap *cm = v->cm;
 color  lastsubcolor = COLORLESS;
 chr   ch,
    from,
    to;
 const chr  *p;
 int   i;

 /* ordinary characters */
 for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
 {
  ch = *p;
  subcoloronechr(v, ch, lp, rp, &lastsubcolor);
  NOERR();
 }

 /* and the ranges */
 for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
 {
  from = *p;
  to = *(p + 1);
  if (from <= MAX_SIMPLE_CHR)
  {
   /* deal with simple chars one at a time */
   chr   lim = (to <= MAX_SIMPLE_CHR) ? to : MAX_SIMPLE_CHR;

   while (from <= lim)
   {
    color  sco = subcolor(cm, from);

    NOERR();
    if (sco != lastsubcolor)
    {
     newarc(v->nfa, PLAIN, sco, lp, rp);
     NOERR();
     lastsubcolor = sco;
    }
    from++;
   }
  }
  /* deal with any part of the range that's above MAX_SIMPLE_CHR */
  if (from < to)
   subcoloronerange(v, from, to, lp, rp, &lastsubcolor);
  else if (from == to)
   subcoloronechr(v, from, lp, rp, &lastsubcolor);
  NOERR();
 }

 /* and deal with cclass if any */
 if (cv->cclasscode >= 0)
 {
  int   classbit;
  color    *pco;
  int   r,
     c;

  /* Enlarge array if we don't have a column bit assignment for cclass */
  if (cm->classbits[cv->cclasscode] == 0)
  {
   cm->classbits[cv->cclasscode] = cm->hiarraycols;
   newhicolorcols(cm);
   NOERR();
  }
  /* Apply subcolorhi() and make arc for each entry in relevant cols */
  classbit = cm->classbits[cv->cclasscode];
  pco = cm->hicolormap;
  for (r = 0; r < cm->hiarrayrows; r++)
  {
   for (c = 0; c < cm->hiarraycols; c++)
   {
    if (c & classbit)
    {
     color  sco = subcolorhi(cm, pco);

     NOERR();
     /* add the arc if needed */
     if (sco != lastsubcolor)
     {
      newarc(v->nfa, PLAIN, sco, lp, rp);
      NOERR();
      lastsubcolor = sco;
     }
    }
    pco++;
   }
  }
 }
}

/*
 * subcoloronechr - do subcolorcvec's work for a singleton chr
 *
 * We could just let subcoloronerange do this, but it's a bit more efficient
 * if we exploit the single-chr case.  Also, callers find it useful for this
 * to be able to handle both low and high chr codes.
 */
static void
subcoloronechr(struct vars *v,
      chr ch,
      struct state *lp,
      struct state *rp,
      color *lastsubcolor)
{
 struct colormap *cm = v->cm;
 colormaprange *newranges;
 int   numnewranges;
 colormaprange *oldrange;
 int   oldrangen;
 int   newrow;

 /* Easy case for low chr codes */
 if (ch <= MAX_SIMPLE_CHR)
 {
  color  sco = subcolor(cm, ch);

  NOERR();
  if (sco != *lastsubcolor)
  {
   newarc(v->nfa, PLAIN, sco, lp, rp);
   *lastsubcolor = sco;
  }
  return;
 }

 /*
  * Potentially, we could need two more colormapranges than we have now, if
  * the given chr is in the middle of some existing range.
 */
 newranges = MALLOC_ARRAY(colormaprange, cm->numcmranges + 2);
 if (newranges == NULL)
 {
  CERR(REG_ESPACE);
  return;
 }
 numnewranges = 0;

 /* Ranges before target are unchanged */
 for (oldrange = cm->cmranges, oldrangen = 0;
   oldrangen < cm->numcmranges;
   oldrange++, oldrangen++)
 {
  if (oldrange->cmax >= ch)
   break;
  newranges[numnewranges++] = *oldrange;
 }

 /* Match target chr against current range */
 if (oldrangen >= cm->numcmranges || oldrange->cmin > ch)
 {
  /* chr does not belong to any existing range, make a new one */
  newranges[numnewranges].cmin = ch;
  newranges[numnewranges].cmax = ch;
  /* row state should be cloned from the "all others" row */
  newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
  numnewranges++;
 }
 else if (oldrange->cmin == oldrange->cmax)
 {
  /* we have an existing singleton range matching the chr */
  newranges[numnewranges++] = *oldrange;
  newrow = oldrange->rownum;
  /* we've now fully processed this old range */
  oldrange++, oldrangen++;
 }
 else
 {
  /* chr is a subset of this existing range, must split it */
  if (ch > oldrange->cmin)
  {
   /* emit portion of old range before chr */
   newranges[numnewranges].cmin = oldrange->cmin;
   newranges[numnewranges].cmax = ch - 1;
   newranges[numnewranges].rownum = oldrange->rownum;
   numnewranges++;
  }
  /* emit chr as singleton range, initially cloning from range */
  newranges[numnewranges].cmin = ch;
  newranges[numnewranges].cmax = ch;
  newranges[numnewranges].rownum = newrow =
   newhicolorrow(cm, oldrange->rownum);
  numnewranges++;
  if (ch < oldrange->cmax)
  {
   /* emit portion of old range after chr */
   newranges[numnewranges].cmin = ch + 1;
   newranges[numnewranges].cmax = oldrange->cmax;
   /* must clone the row if we are making two new ranges from old */
   newranges[numnewranges].rownum =
    (ch > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
    oldrange->rownum;
   numnewranges++;
  }
  /* we've now fully processed this old range */
  oldrange++, oldrangen++;
 }

 /* Update colors in newrow and create arcs as needed */
 subcoloronerow(v, newrow, lp, rp, lastsubcolor);

 /* Ranges after target are unchanged */
 for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
 {
  newranges[numnewranges++] = *oldrange;
 }

 /* Assert our original space estimate was adequate */
 assert(numnewranges <= (cm->numcmranges + 2));

 /* And finally, store back the updated list of ranges */
 if (cm->cmranges != NULL)
  FREE(cm->cmranges);
 cm->cmranges = newranges;
 cm->numcmranges = numnewranges;
}

/*
 * subcoloronerange - do subcolorcvec's work for a high range
 */
static void
subcoloronerange(struct vars *v,
     chr from,
     chr to,
     struct state *lp,
     struct state *rp,
     color *lastsubcolor)
{
 struct colormap *cm = v->cm;
 colormaprange *newranges;
 int   numnewranges;
 colormaprange *oldrange;
 int   oldrangen;
 int   newrow;

 /* Caller should take care of non-high-range cases */
 assert(from > MAX_SIMPLE_CHR);
 assert(from < to);

 /*
  * Potentially, if we have N non-adjacent ranges, we could need as many as
  * 2N+1 result ranges (consider case where new range spans 'em all).
 */
 newranges = MALLOC_ARRAY(colormaprange, cm->numcmranges * 2 + 1);
 if (newranges == NULL)
 {
  CERR(REG_ESPACE);
  return;
 }
 numnewranges = 0;

 /* Ranges before target are unchanged */
 for (oldrange = cm->cmranges, oldrangen = 0;
   oldrangen < cm->numcmranges;
   oldrange++, oldrangen++)
 {
  if (oldrange->cmax >= from)
   break;
  newranges[numnewranges++] = *oldrange;
 }

 /*
  * Deal with ranges that (partially) overlap the target.  As we process
  * each such range, increase "from" to remove the dealt-with characters
  * from the target range.
 */
 while (oldrangen < cm->numcmranges && oldrange->cmin <= to)
 {
  if (from < oldrange->cmin)
  {
   /* Handle portion of new range that corresponds to no old range */
   newranges[numnewranges].cmin = from;
   newranges[numnewranges].cmax = oldrange->cmin - 1;
   /* row state should be cloned from the "all others" row */
   newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
   numnewranges++;
   /* Update colors in newrow and create arcs as needed */
   subcoloronerow(v, newrow, lp, rp, lastsubcolor);
   /* We've now fully processed the part of new range before old */
   from = oldrange->cmin;
  }

  if (from <= oldrange->cmin && to >= oldrange->cmax)
  {
   /* old range is fully contained in new, process it in-place */
   newranges[numnewranges++] = *oldrange;
   newrow = oldrange->rownum;
   from = oldrange->cmax + 1;
  }
  else
  {
   /* some part of old range does not overlap new range */
   if (from > oldrange->cmin)
   {
    /* emit portion of old range before new range */
    newranges[numnewranges].cmin = oldrange->cmin;
    newranges[numnewranges].cmax = from - 1;
    newranges[numnewranges].rownum = oldrange->rownum;
    numnewranges++;
   }
   /* emit common subrange, initially cloning from old range */
   newranges[numnewranges].cmin = from;
   newranges[numnewranges].cmax =
    (to < oldrange->cmax) ? to : oldrange->cmax;
   newranges[numnewranges].rownum = newrow =
    newhicolorrow(cm, oldrange->rownum);
   numnewranges++;
   if (to < oldrange->cmax)
   {
    /* emit portion of old range after new range */
    newranges[numnewranges].cmin = to + 1;
    newranges[numnewranges].cmax = oldrange->cmax;
    /* must clone the row if we are making two new ranges from old */
    newranges[numnewranges].rownum =
     (from > oldrange->cmin) ? newhicolorrow(cm, oldrange->rownum) :
     oldrange->rownum;
    numnewranges++;
   }
   from = oldrange->cmax + 1;
  }
  /* Update colors in newrow and create arcs as needed */
  subcoloronerow(v, newrow, lp, rp, lastsubcolor);
  /* we've now fully processed this old range */
  oldrange++, oldrangen++;
 }

 if (from <= to)
 {
  /* Handle portion of new range that corresponds to no old range */
  newranges[numnewranges].cmin = from;
  newranges[numnewranges].cmax = to;
  /* row state should be cloned from the "all others" row */
  newranges[numnewranges].rownum = newrow = newhicolorrow(cm, 0);
  numnewranges++;
  /* Update colors in newrow and create arcs as needed */
  subcoloronerow(v, newrow, lp, rp, lastsubcolor);
 }

 /* Ranges after target are unchanged */
 for (; oldrangen < cm->numcmranges; oldrange++, oldrangen++)
 {
  newranges[numnewranges++] = *oldrange;
 }

 /* Assert our original space estimate was adequate */
 assert(numnewranges <= (cm->numcmranges * 2 + 1));

 /* And finally, store back the updated list of ranges */
 if (cm->cmranges != NULL)
  FREE(cm->cmranges);
 cm->cmranges = newranges;
 cm->numcmranges = numnewranges;
}

/*
 * subcoloronerow - do subcolorcvec's work for one new row in the high colormap
 */
static void
subcoloronerow(struct vars *v,
      int rownum,
      struct state *lp,
      struct state *rp,
      color *lastsubcolor)
{
 struct colormap *cm = v->cm;
 color    *pco;
 int   i;

 /* Apply subcolorhi() and make arc for each entry in row */
 pco = &cm->hicolormap[rownum * cm->hiarraycols];
 for (i = 0; i < cm->hiarraycols; pco++, i++)
 {
  color  sco = subcolorhi(cm, pco);

  NOERR();
  /* make the arc if needed */
  if (sco != *lastsubcolor)
  {
   newarc(v->nfa, PLAIN, sco, lp, rp);
   NOERR();
   *lastsubcolor = sco;
  }
 }
}

/*
 * okcolors - promote subcolors to full colors
 */
static void
okcolors(struct nfa *nfa,
   struct colormap *cm)
{
 struct colordesc *cd;
 struct colordesc *end = CDEND(cm);
 struct colordesc *scd;
 struct arc *a;
 color  co;
 color  sco;

 for (cd = cm->cd, co = 0; cd < end; cd++, co++)
 {
  sco = cd->sub;
  if (UNUSEDCOLOR(cd) || sco == NOSUB)
  {
   /* has no subcolor, no further action */
  }
  else if (sco == co)
  {
   /* is subcolor, let parent deal with it */
  }
  else if (cd->nschrs == 0 && cd->nuchrs == 0)
  {
   /*
    * Parent is now empty, so just change all its arcs to the
    * subcolor, then free the parent.
    *
    * It is not obvious that simply relabeling the arcs like this is
    * OK; it appears to risk creating duplicate arcs.  We are
    * basically relying on the assumption that processing of a
    * bracket expression can't create arcs of both a color and its
    * subcolor between the bracket's endpoints.
 */
   cd->sub = NOSUB;
   scd = &cm->cd[sco];
   assert(scd->nschrs > 0 || scd->nuchrs > 0);
   assert(scd->sub == sco);
   scd->sub = NOSUB;
   while ((a = cd->arcs) != NULL)
   {
    assert(a->co == co);
    uncolorchain(cm, a);
    a->co = sco;
    colorchain(cm, a);
   }
   freecolor(cm, co);
  }
  else
  {
   /* parent's arcs must gain parallel subcolor arcs */
   cd->sub = NOSUB;
   scd = &cm->cd[sco];
   assert(scd->nschrs > 0 || scd->nuchrs > 0);
   assert(scd->sub == sco);
   scd->sub = NOSUB;
   for (a = cd->arcs; a != NULL; a = a->colorchain)
   {
    assert(a->co == co);
    newarc(nfa, a->type, sco, a->from, a->to);
   }
  }
 }
}

/*
 * colorchain - add this arc to the color chain of its color
 */
static void
colorchain(struct colormap *cm,
     struct arc *a)
{
 struct colordesc *cd = &cm->cd[a->co];

 assert(a->co >= 0);
 if (cd->arcs != NULL)
  cd->arcs->colorchainRev = a;
 a->colorchain = cd->arcs;
 a->colorchainRev = NULL;
 cd->arcs = a;
}

/*
 * uncolorchain - delete this arc from the color chain of its color
 */
static void
uncolorchain(struct colormap *cm,
    struct arc *a)
{
 struct colordesc *cd = &cm->cd[a->co];
 struct arc *aa = a->colorchainRev;

 assert(a->co >= 0);
 if (aa == NULL)
 {
  assert(cd->arcs == a);
  cd->arcs = a->colorchain;
 }
 else
 {
  assert(aa->colorchain == a);
  aa->colorchain = a->colorchain;
 }
 if (a->colorchain != NULL)
  a->colorchain->colorchainRev = aa;
 a->colorchain = NULL;  /* paranoia */
 a->colorchainRev = NULL;
}

/*
 * rainbow - add arcs of all full colors (but one) between specified states
 *
 * If there isn't an exception color, we now generate just a single arc
 * labeled RAINBOW, saving lots of arc-munging later on.
 */
static void
rainbow(struct nfa *nfa,
  struct colormap *cm,
  int type,
  color but,    /* COLORLESS if no exceptions */
  struct state *from,
  struct state *to)
{
 struct colordesc *cd;
 struct colordesc *end = CDEND(cm);
 color  co;

 if (but == COLORLESS)
 {
  newarc(nfa, type, RAINBOW, from, to);
  return;
 }

 /* Gotta do it the hard way.  Skip subcolors, pseudocolors, and "but" */
 for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
  if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
   !(cd->flags & PSEUDO))
   newarc(nfa, type, co, from, to);
}

/*
 * colorcomplement - add arcs of complementary colors
 *
 * We add arcs of all colors that are not pseudocolors and do not match
 * any of the "of" state's PLAIN outarcs.
 *
 * The calling sequence ought to be reconciled with cloneouts().
 */
static void
colorcomplement(struct nfa *nfa,
    struct colormap *cm,
    int type,
    struct state *of,
    struct state *from,
    struct state *to)
{
 struct colordesc *cd;
 struct colordesc *end = CDEND(cm);
 color  co;
 struct arc *a;

 assert(of != from);

 /*
  * A RAINBOW arc matches all colors, making the complement empty.  But we
  * can't just return without making any arcs, because that would leave the
  * NFA disconnected which would break any future delsub().  Instead, make
  * a CANTMATCH arc.  Also set the HASCANTMATCH flag so we know we need to
  * clean that up at the start of NFA optimization.
 */
 if (findarc(of, PLAIN, RAINBOW) != NULL)
 {
  newarc(nfa, CANTMATCH, 0, from, to);
  nfa->flags |= HASCANTMATCH;
  return;
 }

 /* Otherwise, transiently mark the colors that appear in of's out-arcs */
 for (a = of->outs; a != NULL; a = a->outchain)
 {
  if (a->type == PLAIN)
  {
   assert(a->co >= 0);
   cd = &cm->cd[a->co];
   assert(!UNUSEDCOLOR(cd));
   cd->flags |= COLMARK;
  }

  /*
   * There's no syntax for re-complementing a color set, so we cannot
   * see CANTMATCH arcs here.
 */
  assert(a->type != CANTMATCH);
 }

 /* Scan colors, clear transient marks, add arcs for unmarked colors */
 for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
 {
  if (cd->flags & COLMARK)
   cd->flags &= ~COLMARK;
  else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
   newarc(nfa, type, co, from, to);
 }
}


#ifdef REG_DEBUG

/*
 * dumpcolors - debugging output
 */
static void
dumpcolors(struct colormap *cm,
     FILE *f)
{
 struct colordesc *cd;
 struct colordesc *end;
 color  co;
 chr   c;

 fprintf(f, "max %ld\n", (long) cm->max);
 end = CDEND(cm);
 for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
 {
  if (!UNUSEDCOLOR(cd))
  {
   assert(cd->nschrs > 0 || cd->nuchrs > 0);
   if (cd->flags & PSEUDO)
    fprintf(f, "#%2ld(ps): ", (long) co);
   else
    fprintf(f, "#%2ld(%2d): ", (long) co, cd->nschrs + cd->nuchrs);

   /*
    * Unfortunately, it's hard to do this next bit more efficiently.
 */
   for (c = CHR_MIN; c <= MAX_SIMPLE_CHR; c++)
    if (GETCOLOR(cm, c) == co)
     dumpchr(c, f);
   fprintf(f, "\n");
  }
 }
 /* dump the high colormap if it contains anything interesting */
 if (cm->hiarrayrows > 1 || cm->hiarraycols > 1)
 {
  int   r,
     c;
  const color *rowptr;

  fprintf(f, "other:\t");
  for (c = 0; c < cm->hiarraycols; c++)
  {
   fprintf(f, "\t%ld", (long) cm->hicolormap[c]);
  }
  fprintf(f, "\n");
  for (r = 0; r < cm->numcmranges; r++)
  {
   dumpchr(cm->cmranges[r].cmin, f);
   fprintf(f, "..");
   dumpchr(cm->cmranges[r].cmax, f);
   fprintf(f, ":");
   rowptr = &cm->hicolormap[cm->cmranges[r].rownum * cm->hiarraycols];
   for (c = 0; c < cm->hiarraycols; c++)
   {
    fprintf(f, "\t%ld", (long) rowptr[c]);
   }
   fprintf(f, "\n");
  }
 }
}

/*
 * dumpchr - print a chr
 *
 * Kind of char-centric but works well enough for debug use.
 */
static void
dumpchr(chr c,
  FILE *f)
{
 if (c == '\\')
  fprintf(f, "\\\\");
 else if (c > ' ' && c <= '~')
  putc((char) c, f);
 else
  fprintf(f, "\\u%04lx", (long) c);
}

#endif       /* REG_DEBUG */