src/pcre2_compile_cgroup.c

/*************************************************
*      Perl-Compatible Regular Expressions       *
*************************************************/

/* PCRE is a library of functions to support regular expressions whose syntax
and semantics are as close as possible to those of the Perl 5 language.

                       Written by Philip Hazel
     Original API code Copyright (c) 1997-2012 University of Cambridge
          New API code Copyright (c) 2016-2024 University of Cambridge

-----------------------------------------------------------------------------
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice,
      this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.

    * Neither the name of the University of Cambridge nor the names of its
      contributors may be used to endorse or promote products derived from
      this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 THE COPYRIGHT OWNER OR CONTRIBUTORS 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.
-----------------------------------------------------------------------------
*/


#include "pcre2_compile.h"

/*************************************************
*   Compute the hash code from a capture name    *
*************************************************/

/* This function returns with a simple hash code
computed from the name of a capture group.

Arguments:
  name         name of the capture group
  length       the length of the name

Returns:       hash code
*/

uint16_t
PRIV(compile_get_hash_from_name)(PCRE2_SPTR name, uint32_t length)
{
uint16_t hash;

PCRE2_ASSERT(length > 0);

hash = (uint16_t)((name[0] & 0x7f) | ((name[length - 1] & 0xff) << 7));
PCRE2_ASSERT(hash <= NAMED_GROUP_HASH_MASK);
return hash;
}


/*************************************************
*   Get the descriptor of a known named capture  *
*************************************************/

/* This function returns the descriptor in the
named group list of a known capture group.

Arguments:
  name         name of the capture group
  length       the length of the name

Returns:       pointer to the descriptor when found,
               NULL otherwise
 */

named_group *
PRIV(compile_find_named_group)(PCRE2_SPTR name,
  uint32_t length, compile_block *cb)
{
uint16_t hash = PRIV(compile_get_hash_from_name)(name, length);
named_group *ng;
named_group *end = cb->named_groups + cb->names_found;

for (ng = cb->named_groups; ng < end; ng++)
  if (length == ng->length && hash == NAMED_GROUP_GET_HASH(ng) &&
      PRIV(strncmp)(name, ng->name, length) == 0) return ng;

return NULL;
}


/*************************************************
*     Add an entry to the name/number table      *
*************************************************/

/* This function is called between compiling passes to add an entry to the
name/number table, maintaining alphabetical order. Checking for permitted
and forbidden duplicates has already been done.

Arguments:
  cb           the compile data block
  nb           named group entry
  tablecount   the count of names in the table so far

Returns:       new tablecount
*/

uint32_t
PRIV(compile_add_name_to_table)(compile_block *cb,
  named_group *ng, uint32_t tablecount)
{
uint32_t i;
PCRE2_SPTR name = ng->name;
int length = ng->length;
uint32_t duplicate_count = 1;

PCRE2_UCHAR *slot = cb->name_table;

PCRE2_ASSERT(length > 0);

if ((ng->hash_dup & NAMED_GROUP_IS_DUPNAME) != 0)
  {
  named_group *ng_it;
  named_group *end = cb->named_groups + cb->names_found;

  for (ng_it = ng + 1; ng_it < end; ng_it++)
    if (ng_it->name == name) duplicate_count++;
  }

for (i = 0; i < tablecount; i++)
  {
  int crc = memcmp(name, slot + IMM2_SIZE, CU2BYTES(length));
  if (crc == 0 && slot[IMM2_SIZE + length] != 0)
    crc = -1; /* Current name is a substring */

  /* Make space in the table and break the loop for an earlier name. For a
  duplicate or later name, carry on. We do this for duplicates so that in the
  simple case (when ?(| is not used) they are in order of their numbers. In all
  cases they are in the order in which they appear in the pattern. */

  if (crc < 0)
    {
    (void)memmove(slot + cb->name_entry_size * duplicate_count, slot,
      CU2BYTES((tablecount - i) * cb->name_entry_size));
    break;
    }

  /* Continue the loop for a later or duplicate name */

  slot += cb->name_entry_size;
  }

tablecount += duplicate_count;

while (TRUE)
  {
  PUT2(slot, 0, ng->number);
  memcpy(slot + IMM2_SIZE, name, CU2BYTES(length));

  /* Add a terminating zero and fill the rest of the slot with zeroes so that
  the memory is all initialized. Otherwise valgrind moans about uninitialized
  memory when saving serialized compiled patterns. */

  memset(slot + IMM2_SIZE + length, 0,
    CU2BYTES(cb->name_entry_size - length - IMM2_SIZE));

  if (--duplicate_count == 0) break;

  while (TRUE)
    {
    ++ng;
    if (ng->name == name) break;
    }

  slot += cb->name_entry_size;
  }

return tablecount;
}


/*************************************************
*    Find details of duplicate group names       *
*************************************************/

/* This is called from compile_branch() when it needs to know the index and
count of duplicates in the names table when processing named backreferences,
either directly, or as conditions.

Arguments:
  name          points to the name
  length        the length of the name
  indexptr      where to put the index
  countptr      where to put the count of duplicates
  errorcodeptr  where to put an error code
  cb            the compile block

Returns:        TRUE if OK, FALSE if not, error code set
*/

BOOL
PRIV(compile_find_dupname_details)(PCRE2_SPTR name, uint32_t length,
  int *indexptr, int *countptr, int *errorcodeptr, compile_block *cb)
{
uint32_t i, groupnumber;
int count;
PCRE2_UCHAR *slot = cb->name_table;

/* Find the first entry in the table */

for (i = 0; i < cb->names_found; i++)
  {
  if (PRIV(strncmp)(name, slot + IMM2_SIZE, length) == 0 &&
      slot[IMM2_SIZE + length] == 0) break;
  slot += cb->name_entry_size;
  }

/* This should not occur, because this function is called only when we know we
have duplicate names. Give an internal error. */

/* LCOV_EXCL_START */
if (i >= cb->names_found)
  {
  PCRE2_DEBUG_UNREACHABLE();
  *errorcodeptr = ERR53;
  cb->erroroffset = name - cb->start_pattern;
  return FALSE;
  }
/* LCOV_EXCL_STOP */

/* Record the index and then see how many duplicates there are, updating the
backref map and maximum back reference as we do. */

*indexptr = i;
count = 0;

for (;;)
  {
  count++;
  groupnumber = GET2(slot, 0);
  cb->backref_map |= (groupnumber < 32)? (1u << groupnumber) : 1;
  if (groupnumber > cb->top_backref) cb->top_backref = groupnumber;
  if (++i >= cb->names_found) break;
  slot += cb->name_entry_size;
  if (PRIV(strncmp)(name, slot + IMM2_SIZE, length) != 0 ||
    (slot + IMM2_SIZE)[length] != 0) break;
  }

*countptr = count;
return TRUE;
}


/* Process the capture list of scan substring and recurse
operations. Since at least one argument must be present,
a 0 return value represents error. */

static size_t
PRIV(compile_process_capture_list)(uint32_t *pptr, PCRE2_SIZE offset,
  int *errorcodeptr, compile_block *cb)
{
size_t i, size = 0;
named_group *ng;
PCRE2_SPTR name;
uint32_t length;
named_group *end = cb->named_groups + cb->names_found;

while (TRUE)
  {
  ++pptr;

  switch (META_CODE(*pptr))
    {
    case META_OFFSET:
    GETPLUSOFFSET(offset, pptr);
    continue;

    case META_CAPTURE_NAME:
    offset += META_DATA(*pptr);
    length = *(++pptr);
    name = cb->start_pattern + offset;

    ng = PRIV(compile_find_named_group)(name, length, cb);

    if (ng == NULL)
      {
      *errorcodeptr = ERR15;
      cb->erroroffset = offset;
      return 0;
      }

    if ((ng->hash_dup & NAMED_GROUP_IS_DUPNAME) == 0)
      {
      pptr[-1] = META_CAPTURE_NUMBER;
      pptr[0] = ng->number;
      size++;
      continue;
      }

    /* Remains only for duplicated names. */
    pptr[-1] = META_CAPTURE_NAME;
    pptr[0] = (uint32_t)(ng - cb->named_groups);
    size++;
    name = ng->name;

    while (++ng < end)
      if (ng->name == name) size++;
    continue;

    case META_CAPTURE_NUMBER:
    offset += META_DATA(*pptr);

    i = *(++pptr);
    if (i > cb->bracount)
      {
      *errorcodeptr = ERR15;
      cb->erroroffset = offset;
      return 0;
      }
    if (i > cb->top_backref) cb->top_backref = (uint16_t)i;
    size++;
    continue;

    default:
    break;
    }

  PCRE2_ASSERT(size > 0);
  return size;
  }
}


/*******************************************************
*   Parse the arguments of scan substring operations   *
********************************************************/

/* This function parses the arguments of scan substring operations.

Arguments:
  pptr_start    points to the current parsed pattern pointer
  offset        argument starting offset in the pattern
  errorcodeptr  where to put an error code
  cb            the compile block
  lengthptr     NULL during the real compile phase
                points to length accumulator during pre-compile phase

Returns:        TRUE if OK, FALSE if not, error code set
*/

uint32_t *
PRIV(compile_parse_scan_substr_args)(uint32_t *pptr,
  int *errorcodeptr, compile_block *cb, PCRE2_SIZE *lengthptr)
{
uint8_t *captures;
uint8_t *capture_ptr;
uint8_t bit;
PCRE2_SPTR name;
named_group *ng;
named_group *end = cb->named_groups + cb->names_found;
BOOL all_found;
size_t size;

PCRE2_ASSERT(*pptr == META_OFFSET);
if (PRIV(compile_process_capture_list)(pptr - 1, 0, errorcodeptr, cb) == 0)
  return NULL;

/* Align to bytes. Since the highest capture can
be equal to bracount, +1 is added before the aligning. */
size = (cb->bracount + 1 + 7) >> 3;
captures = (uint8_t*)cb->cx->memctl.malloc(size, cb->cx->memctl.memory_data);
if (captures == NULL)
  {
  *errorcodeptr = ERR21;
  READPLUSOFFSET(cb->erroroffset, pptr);
  return NULL;
  }

memset(captures, 0, size);

while (TRUE)
  {
  switch (META_CODE(*pptr))
    {
    case META_OFFSET:
    pptr++;
    SKIPOFFSET(pptr);
    continue;

    case META_CAPTURE_NAME:
    ng = cb->named_groups + pptr[1];
    PCRE2_ASSERT((ng->hash_dup & NAMED_GROUP_IS_DUPNAME) != 0);
    pptr += 2;
    name = ng->name;

    all_found = TRUE;
    do
      {
      if (ng->name != name) continue;

      capture_ptr = captures + (ng->number >> 3);
      PCRE2_ASSERT(capture_ptr < captures + size);
      bit = (uint8_t)(1 << (ng->number & 0x7));

      if ((*capture_ptr & bit) == 0)
        {
        *capture_ptr |= bit;
        all_found = FALSE;
        }
      }
    while (++ng < end);

    if (!all_found)
      {
      *lengthptr += 1 + 2 * IMM2_SIZE;
      continue;
      }

    pptr[-2] = META_CAPTURE_NUMBER;
    pptr[-1] = 0;
    continue;

    case META_CAPTURE_NUMBER:
    pptr += 2;

    capture_ptr = captures + (pptr[-1] >> 3);
    PCRE2_ASSERT(capture_ptr < captures + size);
    bit = (uint8_t)(1 << (pptr[-1] & 0x7));

    if ((*capture_ptr & bit) != 0)
      {
      pptr[-1] = 0;
      continue;
      }

    *capture_ptr |= bit;
    *lengthptr += 1 + IMM2_SIZE;
    continue;

    default:
    break;
    }

  break;
  }

cb->cx->memctl.free(captures, cb->cx->memctl.memory_data);
return pptr - 1;
}


/* Implement heapsort heapify algorithm. */

static void do_heapify_u16(uint16_t *captures, size_t size, size_t i)
{
size_t max;
size_t left;
size_t right;
uint16_t tmp;

while (TRUE)
  {
  max = i;
  left = (i << 1) + 1;
  right = left + 1;

  if (left < size && captures[left] > captures[max]) max = left;
  if (right < size && captures[right] > captures[max]) max = right;
  if (i == max) return;

  tmp = captures[i];
  captures[i] = captures[max];
  captures[max] = tmp;
  i = max;
  }
}

void test_do_heapify_u16(uint16_t *captures, size_t size, size_t i){
    do_heapify_u16(captures, size, i);
}

/*************************************************
*   Parse the arguments of recurse operations    *
*************************************************/

/* This function parses the arguments of recurse operations.

Arguments:
  pptr_start    the current parsed pattern pointer
  offset        argument starting offset in the pattern
  errorcodeptr  where to put an error code
  cb            the compile block
  lengthptr     NULL during the real compile phase
                points to length accumulator during pre-compile phase

Returns:        TRUE if OK, FALSE if not, error code set
*/

BOOL
PRIV(compile_parse_recurse_args)(uint32_t *pptr_start,
  PCRE2_SIZE offset, int *errorcodeptr, compile_block *cb)
{
uint32_t *pptr = pptr_start;
size_t i, size;
PCRE2_SPTR name;
named_group *ng;
named_group *end = cb->named_groups + cb->names_found;
recurse_arguments *args;
uint16_t *captures;
uint16_t *current;
uint16_t *captures_end;
uint16_t tmp;

/* Process all arguments, compute the required size. */

size = PRIV(compile_process_capture_list)(pptr, offset, errorcodeptr, cb);
if (size == 0) return FALSE;

args = cb->cx->memctl.malloc(
  sizeof(recurse_arguments) + size * sizeof(uint16_t), cb->cx->memctl.memory_data);

if (args == NULL)
  {
  *errorcodeptr = ERR21;
  cb->erroroffset = offset;
  return FALSE;
  }

args->header.next = NULL;
#ifdef PCRE2_DEBUG
args->header.type = CDATA_RECURSE_ARGS;
#endif
args->size = size;

/* Caching the pre-processed capture list. */
if (cb->last_data != NULL)
  cb->last_data->next = &args->header;
else
  cb->first_data = &args->header;

cb->last_data = &args->header;

/* Create the capture list size. */

captures = (uint16_t*)(args + 1);

while (TRUE)
  {
  ++pptr;

  switch (META_CODE(*pptr))
    {
    case META_OFFSET:
    SKIPOFFSET(pptr);
    continue;

    case META_CAPTURE_NAME:
    ng = cb->named_groups + *(++pptr);
    PCRE2_ASSERT((ng->hash_dup & NAMED_GROUP_IS_DUPNAME) != 0);
    *captures++ = (uint16_t)(ng->number);

    name = ng->name;

    while (++ng < end)
      if (ng->name == name) *captures++ = (uint16_t)(ng->number);
    continue;

    case META_CAPTURE_NUMBER:
    *captures++ = *(++pptr);
    continue;

    default:
    break;
    }

  break;
  }

PCRE2_ASSERT(size == (size_t)(captures - (uint16_t*)(args + 1)));
args->skip_size = (size_t)(pptr - pptr_start) - 1;

if (size == 1) return TRUE;

/* Sort captures. */

captures = (uint16_t*)(args + 1);
i = (size >> 1) - 1;
while (TRUE)
  {
  do_heapify_u16(captures, size, i);
  if (i == 0) break;
  i--;
  }

for (i = size - 1; i > 0; i--)
  {
  tmp = captures[0];
  captures[0] = captures[i];
  captures[i] = tmp;

  do_heapify_u16(captures, i, 0);
  }

/* Remove duplicates. */

captures_end = captures + size;
tmp = *captures++;
current = captures;

while (current < captures_end)
  {
  if (*current != tmp)
    {
    tmp = *current;
    *captures++ = tmp;
    }

  current++;
  }

args->size = (size_t)(captures - (uint16_t*)(args + 1));
return TRUE;
}

/* End of pcre2_compile_cgroup.c */