Quelle  tsquery_util.c   Sprache: C

/*-------------------------------------------------------------------------
 *
 * tsquery_util.c
 *   Utilities for tsquery datatype
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *   src/backend/utils/adt/tsquery_util.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "miscadmin.h"
#include "tsearch/ts_utils.h"
#include "varatt.h"

/*
 * Build QTNode tree for a tsquery given in QueryItem array format.
 */
QTNode *
QT2QTN(QueryItem *in, char *operand)
{
 QTNode    *node = (QTNode *) palloc0(sizeof(QTNode));

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 node->valnode = in;

 if (in->type == QI_OPR)
 {
  node->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
  node->child[0] = QT2QTN(in + 1, operand);
  node->sign = node->child[0]->sign;
  if (in->qoperator.oper == OP_NOT)
   node->nchild = 1;
  else
  {
   node->nchild = 2;
   node->child[1] = QT2QTN(in + in->qoperator.left, operand);
   node->sign |= node->child[1]->sign;
  }
 }
 else if (operand)
 {
  node->word = operand + in->qoperand.distance;
  node->sign = ((uint32) 1) << (((unsigned int) in->qoperand.valcrc) % 32);
 }

 return node;
}

/*
 * Free a QTNode tree.
 *
 * Referenced "word" and "valnode" items are freed if marked as transient
 * by flags.
 */
void
QTNFree(QTNode *in)
{
 if (!in)
  return;

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (in->valnode->type == QI_VAL && in->word && (in->flags & QTN_WORDFREE) != 0)
  pfree(in->word);

 if (in->valnode->type == QI_OPR)
 {
  int   i;

  for (i = 0; i < in->nchild; i++)
   QTNFree(in->child[i]);
 }
 if (in->child)
  pfree(in->child);

 if (in->flags & QTN_NEEDFREE)
  pfree(in->valnode);

 pfree(in);
}

/*
 * Sort comparator for QTNodes.
 *
 * The sort order is somewhat arbitrary.
 */
int
QTNodeCompare(QTNode *an, QTNode *bn)
{
 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (an->valnode->type != bn->valnode->type)
  return (an->valnode->type > bn->valnode->type) ? -1 : 1;

 if (an->valnode->type == QI_OPR)
 {
  QueryOperator *ao = &an->valnode->qoperator;
  QueryOperator *bo = &bn->valnode->qoperator;

  if (ao->oper != bo->oper)
   return (ao->oper > bo->oper) ? -1 : 1;

  if (an->nchild != bn->nchild)
   return (an->nchild > bn->nchild) ? -1 : 1;

  {
   int   i,
      res;

   for (i = 0; i < an->nchild; i++)
    if ((res = QTNodeCompare(an->child[i], bn->child[i])) != 0)
     return res;
  }

  if (ao->oper == OP_PHRASE && ao->distance != bo->distance)
   return (ao->distance > bo->distance) ? -1 : 1;

  return 0;
 }
 else if (an->valnode->type == QI_VAL)
 {
  QueryOperand *ao = &an->valnode->qoperand;
  QueryOperand *bo = &bn->valnode->qoperand;

  if (ao->valcrc != bo->valcrc)
  {
   return (ao->valcrc > bo->valcrc) ? -1 : 1;
  }

  return tsCompareString(an->word, ao->length, bn->word, bo->length, false);
 }
 else
 {
  elog(ERROR, "unrecognized QueryItem type: %d", an->valnode->type);
  return 0;    /* keep compiler quiet */
 }
}

/*
 * qsort comparator for QTNode pointers.
 */
static int
cmpQTN(const void *a, const void *b)
{
 return QTNodeCompare(*(QTNode *const *) a, *(QTNode *const *) b);
}

/*
 * Canonicalize a QTNode tree by sorting the children of AND/OR nodes
 * into an arbitrary but well-defined order.
 */
void
QTNSort(QTNode *in)
{
 int   i;

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (in->valnode->type != QI_OPR)
  return;

 for (i = 0; i < in->nchild; i++)
  QTNSort(in->child[i]);
 if (in->nchild > 1 && in->valnode->qoperator.oper != OP_PHRASE)
  qsort(in->child, in->nchild, sizeof(QTNode *), cmpQTN);
}

/*
 * Are two QTNode trees equal according to QTNodeCompare?
 */
bool
QTNEq(QTNode *a, QTNode *b)
{
 uint32  sign = a->sign & b->sign;

 if (!(sign == a->sign && sign == b->sign))
  return false;

 return (QTNodeCompare(a, b) == 0);
}

/*
 * Remove unnecessary intermediate nodes. For example:
 *
 * OR   OR
 * a  OR -> a b c
 *  b c
 */
void
QTNTernary(QTNode *in)
{
 int   i;

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (in->valnode->type != QI_OPR)
  return;

 for (i = 0; i < in->nchild; i++)
  QTNTernary(in->child[i]);

 /* Only AND and OR are associative, so don't flatten other node types */
 if (in->valnode->qoperator.oper != OP_AND &&
  in->valnode->qoperator.oper != OP_OR)
  return;

 for (i = 0; i < in->nchild; i++)
 {
  QTNode    *cc = in->child[i];

  if (cc->valnode->type == QI_OPR &&
   in->valnode->qoperator.oper == cc->valnode->qoperator.oper)
  {
   int   oldnchild = in->nchild;

   in->nchild += cc->nchild - 1;
   in->child = (QTNode **) repalloc(in->child, in->nchild * sizeof(QTNode *));

   if (i + 1 != oldnchild)
    memmove(in->child + i + cc->nchild, in->child + i + 1,
      (oldnchild - i - 1) * sizeof(QTNode *));

   memcpy(in->child + i, cc->child, cc->nchild * sizeof(QTNode *));
   i += cc->nchild - 1;

   if (cc->flags & QTN_NEEDFREE)
    pfree(cc->valnode);
   pfree(cc);
  }
 }
}

/*
 * Convert a tree to binary tree by inserting intermediate nodes.
 * (Opposite of QTNTernary)
 */
void
QTNBinary(QTNode *in)
{
 int   i;

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (in->valnode->type != QI_OPR)
  return;

 for (i = 0; i < in->nchild; i++)
  QTNBinary(in->child[i]);

 while (in->nchild > 2)
 {
  QTNode    *nn = (QTNode *) palloc0(sizeof(QTNode));

  nn->valnode = (QueryItem *) palloc0(sizeof(QueryItem));
  nn->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);

  nn->nchild = 2;
  nn->flags = QTN_NEEDFREE;

  nn->child[0] = in->child[0];
  nn->child[1] = in->child[1];
  nn->sign = nn->child[0]->sign | nn->child[1]->sign;

  nn->valnode->type = in->valnode->type;
  nn->valnode->qoperator.oper = in->valnode->qoperator.oper;

  in->child[0] = nn;
  in->child[1] = in->child[in->nchild - 1];
  in->nchild--;
 }
}

/*
 * Count the total length of operand strings in tree (including '\0'-
 * terminators) and the total number of nodes.
 * Caller must initialize *sumlen and *nnode to zeroes.
 */
static void
cntsize(QTNode *in, int *sumlen, int *nnode)
{
 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 *nnode += 1;
 if (in->valnode->type == QI_OPR)
 {
  int   i;

  for (i = 0; i < in->nchild; i++)
   cntsize(in->child[i], sumlen, nnode);
 }
 else
 {
  *sumlen += in->valnode->qoperand.length + 1;
 }
}

typedef struct
{
 QueryItem  *curitem;
 char    *operand;
 char    *curoperand;
} QTN2QTState;

/*
 * Recursively convert a QTNode tree into flat tsquery format.
 * Caller must have allocated arrays of the correct size.
 */
static void
fillQT(QTN2QTState *state, QTNode *in)
{
 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 if (in->valnode->type == QI_VAL)
 {
  memcpy(state->curitem, in->valnode, sizeof(QueryOperand));

  memcpy(state->curoperand, in->word, in->valnode->qoperand.length);
  state->curitem->qoperand.distance = state->curoperand - state->operand;
  state->curoperand[in->valnode->qoperand.length] = '\0';
  state->curoperand += in->valnode->qoperand.length + 1;
  state->curitem++;
 }
 else
 {
  QueryItem  *curitem = state->curitem;

  Assert(in->valnode->type == QI_OPR);

  memcpy(state->curitem, in->valnode, sizeof(QueryOperator));

  Assert(in->nchild <= 2);
  state->curitem++;

  fillQT(state, in->child[0]);

  if (in->nchild == 2)
  {
   curitem->qoperator.left = state->curitem - curitem;
   fillQT(state, in->child[1]);
  }
 }
}

/*
 * Build flat tsquery from a QTNode tree.
 */
TSQuery
QTN2QT(QTNode *in)
{
 TSQuery  out;
 int   len;
 int   sumlen = 0,
    nnode = 0;
 QTN2QTState state;

 cntsize(in, &sumlen, &nnode);

 if (TSQUERY_TOO_BIG(nnode, sumlen))
  ereport(ERROR,
    (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
     errmsg("tsquery is too large")));
 len = COMPUTESIZE(nnode, sumlen);

 out = (TSQuery) palloc0(len);
 SET_VARSIZE(out, len);
 out->size = nnode;

 state.curitem = GETQUERY(out);
 state.operand = state.curoperand = GETOPERAND(out);

 fillQT(&state, in);
 return out;
}

/*
 * Copy a QTNode tree.
 *
 * Modifiable copies of the words and valnodes are made, too.
 */
QTNode *
QTNCopy(QTNode *in)
{
 QTNode    *out;

 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 out = (QTNode *) palloc(sizeof(QTNode));

 *out = *in;
 out->valnode = (QueryItem *) palloc(sizeof(QueryItem));
 *(out->valnode) = *(in->valnode);
 out->flags |= QTN_NEEDFREE;

 if (in->valnode->type == QI_VAL)
 {
  out->word = palloc(in->valnode->qoperand.length + 1);
  memcpy(out->word, in->word, in->valnode->qoperand.length);
  out->word[in->valnode->qoperand.length] = '\0';
  out->flags |= QTN_WORDFREE;
 }
 else
 {
  int   i;

  out->child = (QTNode **) palloc(sizeof(QTNode *) * in->nchild);

  for (i = 0; i < in->nchild; i++)
   out->child[i] = QTNCopy(in->child[i]);
 }

 return out;
}

/*
 * Clear the specified flag bit(s) in all nodes of a QTNode tree.
 */
void
QTNClearFlags(QTNode *in, uint32 flags)
{
 /* since this function recurses, it could be driven to stack overflow. */
 check_stack_depth();

 in->flags &= ~flags;

 if (in->valnode->type != QI_VAL)
 {
  int   i;

  for (i = 0; i < in->nchild; i++)
   QTNClearFlags(in->child[i], flags);
 }
}