diff options
Diffstat (limited to 'pigeonhole/src/lib-sieve/mcht-matches.c')
| -rw-r--r-- | pigeonhole/src/lib-sieve/mcht-matches.c | 440 |
1 files changed, 440 insertions, 0 deletions
diff --git a/pigeonhole/src/lib-sieve/mcht-matches.c b/pigeonhole/src/lib-sieve/mcht-matches.c new file mode 100644 index 0000000..050fce9 --- /dev/null +++ b/pigeonhole/src/lib-sieve/mcht-matches.c @@ -0,0 +1,440 @@ +/* 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-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 + */ +static inline bool _string_find(const struct sieve_comparator *cmp, + const char **valp, const char *vend, const char **keyp, const char *kend) +{ + while ( (*valp < vend) && (*keyp < kend) ) { + if ( !cmp->def->char_match(cmp, valp, vend, keyp, kend) ) + (*valp)++; + } + + return (*keyp == kend); +} + +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)++; + } + 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; + + 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 ( !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 */ + slen = str_len(section); + if ( (vp + slen) > 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; + + if ( mvalues != NULL ) + str_append_data(mvalue, pvp, qp-pvp); + + /* 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 ) { + /* 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 */ + + const char *prv = NULL; /* Stored value pointer for backtrack */ + const char *prk = NULL; /* Stored key pointer for backtrack */ + const char *prw = NULL; /* Stored wildcard pointer for backtrack */ + 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) || !_string_find(cmp, &vp, vend, &needle, nend) ) { + 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 == '?' ) { + debug_printf("next_wcard = '?'; need to match arbitrary character\n"); + + /* 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", vp <= vend ? t_strdup_until(vp, vend) : ""); + + /* Try matching the needle at fixed position */ + if ( (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); + 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. + */ + + debug_printf("=== Finish ===\n"); + debug_printf(" result: %s\n", (kp == kend && vp == vend) ? "true" : "false"); + + if (kp == kend && vp == vend) { + /* 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; +} + |