/* Copyright (c) 2002-2018 Pigeonhole authors, see the included COPYING file

 */

/* Match-type ':matches'

 */

#include "lib.h"

#include "str.h"

#include "sieve-match-types.h"

#include "sieve-comparators.h"

#include "sieve-interpreter.h"

#include "sieve-match.h"

#include <string.h>

#include <stdio.h>

/*

 * Forward declarations

 */

static int

mcht_matches_match_key(struct sieve_match_context *mctx,

           const char *val, size_t val_size,

           const char *key, size_t key_size);

/*

 * Match-type object

 */

const struct sieve_match_type_def matches_match_type = {

  SIEVE_OBJECT("matches", &match_type_operand, SIEVE_MATCH_TYPE_MATCHES),

  .validate_context = sieve_match_substring_validate_context,

  .match_key = mcht_matches_match_key

};

/*

 * Match-type implementation

 */

/* Quick 'n dirty debug */

//#define MATCH_DEBUG

#ifdef MATCH_DEBUG

#define debug_printf(...) printf ("match debug: " __VA_ARGS__)

#else

#define debug_printf(...)

#endif

/* FIXME: Naive implementation, substitute this with dovecot src/lib/str-find.c

 *

 * The inner loop polls the interpreter CPU time limit periodically so that a

 * single O(N*M) search on a large value cannot run for many times the

 * configured sieve_max_cpu_time. Returns 1 on match, 0 on exhaustion, or -1

 * when the CPU time limit was exceeded (mctx->exec_status is set).

 */

#define SIEVE_MATCHES_CPU_CHECK_INTERVAL 4096

static int

_string_find(struct sieve_match_context *mctx,

       const struct sieve_comparator *cmp,

       const char **valp, const char *vend,

       const char **keyp, const char *kend,

       unsigned int *counter)

{

  while ((*valp < vend) && (*keyp < kend)) {

    if (!cmp->def->char_match(cmp, valp, vend, keyp, kend))

      (*valp)++;

    if (++(*counter) >= SIEVE_MATCHES_CPU_CHECK_INTERVAL) {

      *counter = 0;

      if (sieve_runtime_cpu_limit_exceeded(mctx->runenv)) {

        sieve_runtime_error(

          mctx->runenv, NULL,

          "execution exceeded CPU time limit");

        mctx->exec_status =

          SIEVE_EXEC_RESOURCE_LIMIT;

        return -1;

      }

    }

  }

  return (*keyp == kend ? 1 : 0);

}

static char

_scan_key_section(string_t *section, const char **wcardp, const char *key_end)

{

  /* Find next wildcard and resolve escape sequences */

  str_truncate(section, 0);

  while (*wcardp < key_end && **wcardp != '*' && **wcardp != '?') {

    if (**wcardp == '\\') {

      (*wcardp)++;

      if (*wcardp == key_end) {

        str_append_c(section,'\\');

        break;

      }

    }

    str_append_c(section, **wcardp);

    (*wcardp)++;

  }

  /* Record wildcard character or \0 */

  if (*wcardp < key_end) {

    return **wcardp;

  }

  i_assert(*wcardp == key_end);

  return '\0';

}

static int

mcht_matches_match_key(struct sieve_match_context *mctx,

           const char *val, size_t val_size,

           const char *key, size_t key_size)

{

  const struct sieve_comparator *cmp = mctx->comparator;

  struct sieve_match_values *mvalues;

  string_t *mvalue = NULL, *mchars = NULL;

  string_t *section, *subsection;

  const char *vend, *kend, *vp, *kp, *wp, *pvp;

  bool backtrack = FALSE; /* TRUE: match of '?'-connected sections failed

         */

  char wcard = '\0';      /* Current wildcard */

  char next_wcard = '\0'; /* Next  widlcard */

  unsigned int key_offset = 0;

  unsigned int counter = 0;

  if (cmp->def == NULL || cmp->def->char_match == NULL)

    return 0;

  /* Key sections */

  section = t_str_new(32);    /* Section (after beginning or *) */

  subsection = t_str_new(32); /* Sub-section (after ?) */

  /* Mark end of value and key */

  vend = (const char *) val + val_size;

  kend = (const char *) key + key_size;

  /* Initialize pointers */

  vp = val;                   /* Value pointer */

  kp = key;                   /* Key pointer */

  wp = key;                   /* Wildcard (key) pointer */

  /* Start match values list if requested */

  if ((mvalues = sieve_match_values_start(mctx->runenv)) != NULL) {

    /* Skip ${0} for now; added when match succeeds */

    sieve_match_values_add(mvalues, NULL);

    mvalue = t_str_new(32);     /* Match value (*) */

    mchars = t_str_new(32);     /* Match characters (.?..?.??) */

  }

  /* Match the pattern:

       <pattern> = <section>*<section>*<section>...

       <section> = <sub-section>?<sub-section>?<sub-section>...

     Escape sequences \? and \* need special attention.

   */

  debug_printf("=== Start ===\n");

  debug_printf("  key:   %s\n", t_strdup_until(key, kend));

  debug_printf("  value: %s\n", t_strdup_until(val, vend));

  /* Loop until either key or value ends */

  while (kp < kend && vp < vend) {

    const char *needle, *nend;

    if (++counter >= SIEVE_MATCHES_CPU_CHECK_INTERVAL) {

      counter = 0;

      if (sieve_runtime_cpu_limit_exceeded(mctx->runenv)) {

        sieve_runtime_error(

          mctx->runenv, NULL,

          "execution exceeded CPU time limit");

        mctx->exec_status =

          SIEVE_EXEC_RESOURCE_LIMIT;

        sieve_match_values_abort(&mvalues);

        return -1;

      }

    }

    if (!backtrack) {

      /* Search the next '*' wildcard in the key string */

      wcard = next_wcard;

      /* Find the needle to look for in the string */

      key_offset = 0;

      for (;;) {

        next_wcard =

          _scan_key_section(section, &wp, kend);

        if (wcard == '\0' || str_len(section) > 0)

          break;

        if (next_wcard == '*')

          break;

        if (wp < kend)

          wp++;

        else

          break;

        key_offset++;

      }

      debug_printf("found wildcard '%c' at pos [%d]\n",

             next_wcard, (int)(wp - key));

      if (mvalues != NULL)

        str_truncate(mvalue, 0);

    } else {

      /* Backtracked; '*' wildcard is retained */

      debug_printf("backtracked");

      backtrack = FALSE;

    }

    /* Determine what we are looking for */

    needle = str_c(section);

    nend = PTR_OFFSET(needle, str_len(section));

    debug_printf("  section needle:  '%s'\n",

           t_strdup_until(needle, nend));

    debug_printf("  section key:     '%s'\n",

           t_strdup_until(kp, kend));

    debug_printf("  section remnant: '%s'\n",

           t_strdup_until(wp, kend));

    debug_printf("  value remnant:   '%s'\n",

           t_strdup_until(vp, vend));

    debug_printf("  key offset:      %d\n", key_offset);

    pvp = vp;

    if (next_wcard == '\0') {

      if (wcard == '\0') {

        /* No current wildcard; match needs to happen

           right at the beginning */

        debug_printf("next_wcard = NULL && wcard = NUL; "

               "needle should be equal to value.\n");

        if ((vend - vp) != (nend - needle) ||

            !cmp->def->char_match(cmp, &vp, vend, &needle, nend)) {

          debug_printf("  key not equal to value\n");

          break;

        }

      } else {

        const char *qp, *qend;

        size_t slen;

        /* No more wildcards; find the needle substring

           at the end of string */

        debug_printf("next_wcard = NUL; "

               "must find needle at end\n");

        /* Check if the value is still large enough to

           contain both the '?'-matched prefix

           (key_offset chars) and the trailing section.

         */

        slen = str_len(section);

        if ((vp + slen + key_offset) > vend) {

          debug_printf("  wont match: "

                 "value is too short\n");

          break;

        }

        /* Move value pointer to where the needle should

           be */

        vp = vend - slen;

        /* Record match values */

        qend = vp;

        qp = vp - key_offset;

        /* Compare needle to end of value string */

        if (!cmp->def->char_match(cmp, &vp, vend,

                 &needle, nend)) {

          debug_printf("  match at end failed\n");

          break;

        }

        /* Add match values */

        if (mvalues != NULL) {

          i_assert(qp >= pvp);

          str_append_data(mvalue, pvp, qp - pvp);

          /* Append '*' match value */

          sieve_match_values_add(mvalues, mvalue);

          /* Append any initial '?' match values

           */

          for (; qp < qend; qp++) {

            sieve_match_values_add_char(

              mvalues, *qp);

          }

        }

      }

      /* Finish match */

      kp = kend;

      vp = vend;

      debug_printf("  matched end of value\n");

      break;

    } else {

      /* Next wildcard found; match needle before next

         wildcard */

      /* Stored value pointer for backtrack */

      const char *prv = NULL;

      /* Stored key pointer for backtrack */

      const char *prk = NULL;

      /* Stored wildcard pointer for backtrack */

      const char *prw = NULL;

      const char *chars;

      /* Reset '?' match values */

      if (mvalues != NULL)

        str_truncate(mchars, 0);

      if (wcard == '\0') {

        /* No current wildcard; match needs to happen

           right at the beginning */

        debug_printf("wcard = NUL; "

               "needle should be found at the beginning.\n");

        debug_printf("  begin needle: '%s'\n",

               t_strdup_until(needle, nend));

        debug_printf("  begin value:  '%s'\n",

               t_strdup_until(vp, vend));

        if (!cmp->def->char_match(cmp, &vp, vend, &needle, nend)) {

          debug_printf("  failed to find needle at beginning\n");

          break;

        }

      } else {

        /* Current wildcard present; match needle

           between current and next wildcard */

        debug_printf("wcard != NUL; "

               "must find needle at an offset (>= %d).\n",

               key_offset);

        /* Match may happen at any offset

           (>= key offset): find substring */

        vp += key_offset;

        if (vp >= vend) {

          debug_printf("  failed to find needle at an offset\n");

          break;

        }

        int fres = _string_find(mctx, cmp, &vp, vend,

              &needle, nend, &counter);

        if (fres < 0) {

          sieve_match_values_abort(&mvalues);

          return -1;

        }

        if (fres == 0) {

          debug_printf("  failed to find needle at an offset\n");

          break;

        }

        prv = vp - str_len(section);

        prk = kp;

        prw = wp;

        /* Append match values */

        if (mvalues != NULL) {

          const char *qend = vp - str_len(section);

          const char *qp = qend - key_offset;

          /* Append '*' match value */

          str_append_data(mvalue, pvp, qp - pvp);

          /* Append any initial '?' match values

             (those that caused the key offset).

           */

          for (; qp < qend; qp++)

            str_append_c(mchars, *qp);

        }

      }

      /* Update wildcard and key pointers for next wildcard

         scan */

      if (wp < kend)

        wp++;

      kp = wp;

      /* Scan successive '?' wildcards */

      while (next_wcard == '?') {

        bool match_failed_empty = FALSE;

        debug_printf("next_wcard = '?'; "

               "need to match arbitrary character\n");

        i_assert(vp <= vend);

        if (vp == vend)

          match_failed_empty = TRUE;

        else {

          /* Add match value */

          if (mvalues != NULL)

            str_append_c(mchars, *vp);

          vp++;

          /* Scan for next '?' wildcard */

          next_wcard = _scan_key_section(subsection, &wp, kend);

          debug_printf("found next wildcard '%c' at pos [%d] "

                 "(fixed match)\n",

                 next_wcard, (int)(wp - key));

          /* Determine what we are looking for */

          needle = str_c(subsection);

          nend = needle + str_len(subsection);

          debug_printf("  sub key:       '%s'\n",

                 t_strdup_until(needle, nend));

          debug_printf("  value remnant: '%s'\n",

                 t_strdup_until(vp, vend));

        }

        /* Try matching the needle at fixed position */

        if (match_failed_empty ||

            (needle == nend && next_wcard == '\0' && vp < vend) ||

            !cmp->def->char_match(cmp, &vp, vend, &needle, nend)) {

          /* Match failed: now we have a problem. We need to

             backtrack to the previous '*' wildcard occurrence

             and start scanning for the next possible match.

           */

          debug_printf("  failed fixed match\n");

          /* Start backtrack */

          if (prv != NULL && prv + 1 < vend) {

            /* Restore pointers */

            vp = prv;

            kp = prk;

            wp = prw;

            /* Skip forward one value character to scan

               the next possible match */

            if (mvalues != NULL)

              str_append_c(mvalue, *vp);

            vp++;

            /* Set wildcard state appropriately */

            wcard = '*';

            next_wcard = '?';

            /* Backtrack */

            backtrack = TRUE;

            debug_printf("  BACKTRACK\n");

          }

          /* Break '?' wildcard scanning loop */

          break;

        }

        /* Update wildcard and key pointers for next wildcard scan */

        if (wp < kend)

          wp++;

        kp = wp;

      }

      if (!backtrack) {

        unsigned int i;

        if (next_wcard == '?') {

          debug_printf("failed to match '?'\n");

          break;

        }

        if (mvalues != NULL) {

          if (prv != NULL)

            sieve_match_values_add(mvalues, mvalue);

          chars = (const char *) str_data(mchars);

          for (i = 0; i < str_len(mchars); i++)

            sieve_match_values_add_char(mvalues, chars[i]);

        }

        if (next_wcard != '*') {

          debug_printf("failed to match at end of string\n");

          break;

        }

      }

    }

    /* Check whether string ends in a wildcard

       (avoid scanning the rest of the string)

     */

    if (kp == kend && next_wcard == '*') {

      /* Add the rest of the string as match value */

      if (mvalues != NULL) {

        str_truncate(mvalue, 0);

        i_assert(vend >= vp);

        str_append_data(mvalue, vp, vend - vp);

        sieve_match_values_add(mvalues, mvalue);

      }

      /* Finish match */

      kp = kend;

      vp = vend;

      debug_printf("key ends with '*'\n");

      break;

    }

    debug_printf("== Loop ==\n");

  }

  /* Eat away a trailing series of *s */

  if (vp == vend) {

    while (kp < kend && *kp == '*')

      kp++;

  }

  /* By definition, the match is only successful if both value and key

     pattern are exhausted and we're not still trying to match '?' while

     the value is empty.

   */

  bool matched = (kp == kend && vp == vend && next_wcard != '?');

  debug_printf("=== Finish ===\n");

  debug_printf("  result: %s\n", matched ? "true" : "false");

  if (matched) {

    /* Activate new match values after successful match */

    if (mvalues != NULL) {

      /* Set ${0} */

      string_t *matched = str_new_const(

        pool_datastack_create(), val, val_size);

      sieve_match_values_set(mvalues, 0, matched);

      /* Commit new match values */

      sieve_match_values_commit(mctx->runenv, &mvalues);

    }

    return 1;

  }

  /* No match; drop collected match values */

  sieve_match_values_abort(&mvalues);

  return 0;

}