summaryrefslogtreecommitdiffstats
path: root/src/lib-imap/imap-match.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib-imap/imap-match.c')
-rw-r--r--src/lib-imap/imap-match.c382
1 files changed, 382 insertions, 0 deletions
diff --git a/src/lib-imap/imap-match.c b/src/lib-imap/imap-match.c
new file mode 100644
index 0000000..8603e00
--- /dev/null
+++ b/src/lib-imap/imap-match.c
@@ -0,0 +1,382 @@
+/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
+
+/* imap_match_init() logic originates from Cyrus, but the code is fully
+ rewritten. */
+
+#include "lib.h"
+#include "array.h"
+#include "imap-match.h"
+
+#include <ctype.h>
+
+struct imap_match_pattern {
+ const char *pattern;
+ bool inboxcase;
+};
+
+struct imap_match_glob {
+ pool_t pool;
+
+ struct imap_match_pattern *patterns;
+
+ char sep;
+ char patterns_data[FLEXIBLE_ARRAY_MEMBER];
+};
+
+struct imap_match_context {
+ const char *inboxcase_end;
+
+ char sep;
+ bool inboxcase;
+};
+
+/* name of "INBOX" - must not have repeated substrings */
+static const char inbox[] = "INBOX";
+#define INBOXLEN (sizeof(inbox) - 1)
+
+struct imap_match_glob *
+imap_match_init(pool_t pool, const char *pattern,
+ bool inboxcase, char separator)
+{
+ const char *patterns[2];
+
+ patterns[0] = pattern;
+ patterns[1] = NULL;
+ return imap_match_init_multiple(pool, patterns, inboxcase, separator);
+}
+
+static const char *pattern_compress(const char *pattern)
+{
+ char *dest, *ret;
+
+ dest = ret = t_strdup_noconst(pattern);
+
+ /* @UNSAFE: compress the pattern */
+ while (*pattern != '\0') {
+ if (*pattern == '*' || *pattern == '%') {
+ /* remove duplicate hierarchy wildcards */
+ while (*pattern == '%') pattern++;
+
+ /* "%*" -> "*" */
+ if (*pattern == '*') {
+ /* remove duplicate wildcards */
+ while (*pattern == '*' || *pattern == '%')
+ pattern++;
+ *dest++ = '*';
+ } else {
+ *dest++ = '%';
+ }
+ } else {
+ *dest++ = *pattern++;
+ }
+ }
+ *dest = '\0';
+ return ret;
+}
+
+static bool pattern_is_inboxcase(const char *pattern, char separator)
+{
+ const char *p = pattern, *inboxp = inbox;
+
+ /* skip over exact matches */
+ while (*inboxp == i_toupper(*p) && *p != '\0') {
+ inboxp++; p++;
+ }
+ if (*p != '%') {
+ return *p == '*' || *p == separator ||
+ (*inboxp == '\0' && *p == '\0');
+ }
+
+ /* handle 'I%B%X' style checks */
+ for (; *p != '\0' && *p != '*' && *p != separator; p++) {
+ if (*p != '%') {
+ inboxp = strchr(inboxp, i_toupper(*p));
+ if (inboxp == NULL)
+ return FALSE;
+
+ if (*++inboxp == '\0') {
+ /* now check that it doesn't end with
+ any invalid chars */
+ if (*++p == '%') p++;
+ if (*p != '\0' && *p != '*' &&
+ *p != separator)
+ return FALSE;
+ break;
+ }
+ }
+ }
+ return TRUE;
+}
+
+static struct imap_match_glob *
+imap_match_init_multiple_real(pool_t pool, const char *const *patterns,
+ bool inboxcase, char separator)
+{
+ struct imap_match_glob *glob;
+ struct imap_match_pattern *match_patterns;
+ unsigned int i, patterns_count;
+ size_t len, pos, patterns_data_len = 0;
+
+ patterns_count = str_array_length(patterns);
+ match_patterns = p_new(pool, struct imap_match_pattern,
+ patterns_count + 1);
+
+ /* compress the patterns */
+ for (i = 0; i < patterns_count; i++) {
+ match_patterns[i].pattern = pattern_compress(patterns[i]);
+ match_patterns[i].inboxcase = inboxcase &&
+ pattern_is_inboxcase(match_patterns[i].pattern,
+ separator);
+
+ patterns_data_len += strlen(match_patterns[i].pattern) + 1;
+ }
+ patterns_count = i;
+
+ /* now we know how much memory we need */
+ glob = p_malloc(pool, sizeof(struct imap_match_glob) +
+ patterns_data_len);
+ glob->pool = pool;
+ glob->sep = separator;
+
+ /* copy pattern strings to our allocated memory */
+ for (i = 0, pos = 0; i < patterns_count; i++) {
+ len = strlen(match_patterns[i].pattern) + 1;
+ i_assert(pos + len <= patterns_data_len);
+
+ /* @UNSAFE */
+ memcpy(glob->patterns_data + pos,
+ match_patterns[i].pattern, len);
+ match_patterns[i].pattern = glob->patterns_data + pos;
+ pos += len;
+ }
+ glob->patterns = match_patterns;
+ return glob;
+}
+
+struct imap_match_glob *
+imap_match_init_multiple(pool_t pool, const char *const *patterns,
+ bool inboxcase, char separator)
+{
+ struct imap_match_glob *glob;
+
+ if (pool->datastack_pool) {
+ return imap_match_init_multiple_real(pool, patterns,
+ inboxcase, separator);
+ }
+ T_BEGIN {
+ glob = imap_match_init_multiple_real(pool, patterns,
+ inboxcase, separator);
+ } T_END;
+ return glob;
+}
+
+void imap_match_deinit(struct imap_match_glob **glob)
+{
+ if (glob == NULL || *glob == NULL)
+ return;
+ p_free((*glob)->pool, (*glob)->patterns);
+ p_free((*glob)->pool, *glob);
+ *glob = NULL;
+}
+
+static struct imap_match_glob *
+imap_match_dup_real(pool_t pool, const struct imap_match_glob *glob)
+{
+ ARRAY_TYPE(const_string) patterns;
+ const struct imap_match_pattern *p;
+ bool inboxcase = FALSE;
+
+ t_array_init(&patterns, 8);
+ for (p = glob->patterns; p->pattern != NULL; p++) {
+ if (p->inboxcase)
+ inboxcase = TRUE;
+ array_push_back(&patterns, &p->pattern);
+ }
+ array_append_zero(&patterns);
+ return imap_match_init_multiple_real(pool, array_front(&patterns),
+ inboxcase, glob->sep);
+}
+
+struct imap_match_glob *
+imap_match_dup(pool_t pool, const struct imap_match_glob *glob)
+{
+ struct imap_match_glob *new_glob;
+
+ if (pool->datastack_pool) {
+ return imap_match_dup_real(pool, glob);
+ } else {
+ T_BEGIN {
+ new_glob = imap_match_dup_real(pool, glob);
+ } T_END;
+ return new_glob;
+ }
+}
+
+bool imap_match_globs_equal(const struct imap_match_glob *glob1,
+ const struct imap_match_glob *glob2)
+{
+ const struct imap_match_pattern *p1 = glob1->patterns;
+ const struct imap_match_pattern *p2 = glob2->patterns;
+
+ if (glob1->sep != glob2->sep)
+ return FALSE;
+
+ for (; p1->pattern != NULL && p2->pattern != NULL; p1++, p2++) {
+ if (strcmp(p1->pattern, p2->pattern) != 0)
+ return FALSE;
+ if (p1->inboxcase != p2->inboxcase)
+ return FALSE;
+ }
+ return p1->pattern == p2->pattern;
+}
+
+#define CMP_CUR_CHR(ctx, data, pattern) \
+ (*(data) == *(pattern) || \
+ (i_toupper(*(data)) == i_toupper(*(pattern)) && \
+ (data) < (ctx)->inboxcase_end))
+
+static enum imap_match_result
+match_sub(struct imap_match_context *ctx, const char **data_p,
+ const char **pattern_p)
+{
+ enum imap_match_result ret, match;
+ unsigned int i;
+ const char *data = *data_p, *pattern = *pattern_p;
+
+ /* match all non-wildcards */
+ i = 0;
+ while (pattern[i] != '\0' && pattern[i] != '*' && pattern[i] != '%') {
+ if (!CMP_CUR_CHR(ctx, data+i, pattern+i)) {
+ if (data[i] != '\0')
+ return IMAP_MATCH_NO;
+ if (pattern[i] == ctx->sep)
+ return IMAP_MATCH_CHILDREN;
+ if (i > 0 && pattern[i-1] == ctx->sep) {
+ /* data="foo/" pattern = "foo/bar/%" */
+ return IMAP_MATCH_CHILDREN;
+ }
+ return IMAP_MATCH_NO;
+ }
+ i++;
+ }
+ data += i;
+ pattern += i;
+
+ if (*data == '\0' && *data_p != data && data[-1] == ctx->sep &&
+ *pattern != '\0') {
+ /* data="/" pattern="/%..." */
+ match = IMAP_MATCH_CHILDREN;
+ } else {
+ match = IMAP_MATCH_NO;
+ }
+ while (*pattern == '%') {
+ pattern++;
+
+ if (*pattern == '\0') {
+ /* match, if this is the last hierarchy */
+ while (*data != '\0' && *data != ctx->sep)
+ data++;
+ break;
+ }
+
+ /* skip over this hierarchy */
+ while (*data != '\0') {
+ if (CMP_CUR_CHR(ctx, data, pattern)) {
+ ret = match_sub(ctx, &data, &pattern);
+ if (ret == IMAP_MATCH_YES)
+ break;
+
+ match |= ret;
+ }
+
+ if (*data == ctx->sep)
+ break;
+
+ data++;
+ }
+ }
+
+ if (*pattern != '*') {
+ if (*data == '\0' && *pattern != '\0') {
+ if (*pattern == ctx->sep)
+ match |= IMAP_MATCH_CHILDREN;
+ return match;
+ }
+
+ if (*data != '\0') {
+ if (*pattern == '\0' && *data == ctx->sep)
+ match |= IMAP_MATCH_PARENT;
+ return match;
+ }
+ }
+
+ *data_p = data;
+ *pattern_p = pattern;
+ return IMAP_MATCH_YES;
+}
+
+static enum imap_match_result
+imap_match_pattern(struct imap_match_context *ctx,
+ const char *data, const char *pattern)
+{
+ enum imap_match_result ret, match;
+
+ ctx->inboxcase_end = data;
+ if (ctx->inboxcase && strncasecmp(data, inbox, INBOXLEN) == 0 &&
+ (data[INBOXLEN] == '\0' || data[INBOXLEN] == ctx->sep)) {
+ /* data begins with INBOX/, use case-insensitive comparison
+ for it */
+ ctx->inboxcase_end += INBOXLEN;
+ }
+
+ if (*pattern != '*') {
+ /* handle the pattern up to the first '*' */
+ ret = match_sub(ctx, &data, &pattern);
+ if (ret != IMAP_MATCH_YES || *pattern == '\0')
+ return ret;
+ }
+
+ match = IMAP_MATCH_CHILDREN;
+ while (*pattern == '*') {
+ pattern++;
+
+ if (*pattern == '\0')
+ return IMAP_MATCH_YES;
+
+ while (*data != '\0') {
+ if (CMP_CUR_CHR(ctx, data, pattern)) {
+ ret = match_sub(ctx, &data, &pattern);
+ if (ret == IMAP_MATCH_YES)
+ break;
+ match |= ret;
+ }
+
+ data++;
+ }
+ }
+
+ return *data == '\0' && *pattern == '\0' ?
+ IMAP_MATCH_YES : match;
+}
+
+enum imap_match_result
+imap_match(struct imap_match_glob *glob, const char *data)
+{
+ struct imap_match_context ctx;
+ unsigned int i;
+ enum imap_match_result ret, match;
+
+ match = IMAP_MATCH_NO;
+ ctx.sep = glob->sep;
+ for (i = 0; glob->patterns[i].pattern != NULL; i++) {
+ ctx.inboxcase = glob->patterns[i].inboxcase;
+
+ ret = imap_match_pattern(&ctx, data, glob->patterns[i].pattern);
+ if (ret == IMAP_MATCH_YES)
+ return IMAP_MATCH_YES;
+
+ match |= ret;
+ }
+
+ return match;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 12:25:38 +0000