wimlib.net Git - wimlib/blob - src/wildcard.c

   1 /*
   2  * wildcard.c
   3  *
   4  * Wildcard matching functions.
   5  */
   6
   7 /*
   8  * Copyright (C) 2013 Eric Biggers
   9  *
  10  * This file is part of wimlib, a library for working with WIM files.
  11  *
  12  * wimlib is free software; you can redistribute it and/or modify it under the
  13  * terms of the GNU General Public License as published by the Free
  14  * Software Foundation; either version 3 of the License, or (at your option)
  15  * any later version.
  16  *
  17  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  18  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  19  * A PARTICULAR PURPOSE. See the GNU General Public License for more
  20  * details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with wimlib; if not, see http://www.gnu.org/licenses/.
  24  */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #  include "config.h"
  28 #endif
  29
  30 #include "wimlib/dentry.h"
  31 #include "wimlib/encoding.h"
  32 #include "wimlib/error.h"
  33 #include "wimlib/metadata.h"
  34 #include "wimlib/wildcard.h"
  35
  36 struct match_dentry_ctx {
  37         int (*consume_path)(const tchar *, void *, bool);
  38         void *consume_path_ctx;
  39         size_t consume_path_count;
  40         tchar *expanded_path;
  41         size_t expanded_path_len;
  42         size_t expanded_path_alloc_len;
  43         tchar *wildcard_path;
  44         size_t cur_component_offset;
  45         size_t cur_component_len;
  46         bool case_insensitive;
  47 };
  48
  49 #ifdef __WIN32__
  50 static bool
  51 match_wildcard_case_sensitive(const tchar *string, size_t string_len,
  52                               const tchar *wildcard, size_t wildcard_len)
  53 {
  54         for (;;) {
  55                 if (string_len == 0) {
  56                         while (wildcard_len != 0 && *wildcard == T('*')) {
  57                                 wildcard++;
  58                                 wildcard_len--;
  59                         }
  60                         return (wildcard_len == 0);
  61                 } else if (wildcard_len == 0) {
  62                         return false;
  63                 } else if (*string == *wildcard || *wildcard == '?') {
  64                         string++;
  65                         string_len--;
  66                         wildcard_len--;
  67                         wildcard++;
  68                         continue;
  69                 } else if (*wildcard == '*') {
  70                         return match_wildcard_case_sensitive(
  71                                               string, string_len,
  72                                               wildcard + 1, wildcard_len - 1) ||
  73                                 match_wildcard_case_sensitive(
  74                                                string + 1, string_len - 1,
  75                                                wildcard, wildcard_len);
  76                 } else {
  77                         return false;
  78                 }
  79         }
  80 }
  81 #endif
  82
  83 static bool
  84 match_wildcard(const tchar *string, tchar *wildcard,
  85                size_t wildcard_len, bool case_insensitive)
  86 {
  87         /* Note: in Windows builds fnmatch() calls a replacement function.
  88          * It does support case-sensitive globbing.  */
  89 #ifdef __WIN32__
  90         if (case_insensitive)
  91 #endif
  92         {
  93                 char orig;
  94                 int ret;
  95                 int flags = FNM_NOESCAPE;
  96                 if (case_insensitive)
  97                         flags |= FNM_CASEFOLD;
  98
  99                 orig = wildcard[wildcard_len];
 100                 wildcard[wildcard_len] = T('\0');
 101
 102                 ret = fnmatch(wildcard, string, flags);
 103
 104                 wildcard[wildcard_len] = orig;
 105                 return (ret == 0);
 106         }
 107 #ifdef __WIN32__
 108         else
 109         {
 110                 return match_wildcard_case_sensitive(string,
 111                                                      tstrlen(string),
 112                                                      wildcard,
 113                                                      wildcard_len);
 114         }
 115 #endif
 116 }
 117
 118 static int
 119 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
 120                           struct match_dentry_ctx *ctx);
 121
 122 enum {
 123         WILDCARD_STATUS_DONE_FULLY,
 124         WILDCARD_STATUS_DONE_TRAILING_SLASHES,
 125         WILDCARD_STATUS_NOT_DONE,
 126 };
 127
 128 static int
 129 wildcard_status(const tchar *wildcard)
 130 {
 131         if (*wildcard == T('\0'))
 132                 return WILDCARD_STATUS_DONE_FULLY;
 133         while (is_any_path_separator(*wildcard))
 134                 wildcard++;
 135         if (*wildcard == T('\0'))
 136                 return WILDCARD_STATUS_DONE_TRAILING_SLASHES;
 137
 138         return WILDCARD_STATUS_NOT_DONE;
 139 }
 140
 141 static int
 142 match_dentry(struct wim_dentry *cur_dentry, void *_ctx)
 143 {
 144         struct match_dentry_ctx *ctx = _ctx;
 145         tchar *name;
 146         size_t name_len;
 147         int ret;
 148
 149         if (cur_dentry->file_name_nbytes == 0)
 150                 return 0;
 151
 152 #if TCHAR_IS_UTF16LE
 153         name = cur_dentry->file_name;
 154         name_len = cur_dentry->file_name_nbytes;
 155 #else
 156         ret = utf16le_to_tstr(cur_dentry->file_name,
 157                               cur_dentry->file_name_nbytes,
 158                               &name, &name_len);
 159         if (ret)
 160                 return ret;
 161 #endif
 162         name_len /= sizeof(tchar);
 163
 164         if (match_wildcard(name,
 165                            &ctx->wildcard_path[ctx->cur_component_offset],
 166                            ctx->cur_component_len,
 167                            ctx->case_insensitive))
 168         {
 169                 size_t len_needed = ctx->expanded_path_len + 1 + name_len + 1;
 170                 size_t expanded_path_len_save;
 171
 172                 if (len_needed > ctx->expanded_path_alloc_len) {
 173                         tchar *expanded_path;
 174
 175                         expanded_path = REALLOC(ctx->expanded_path,
 176                                                 len_needed * sizeof(ctx->expanded_path[0]));
 177                         if (expanded_path == NULL) {
 178                                 ret = WIMLIB_ERR_NOMEM;
 179                                 goto out_free_name;
 180                         }
 181                         ctx->expanded_path = expanded_path;
 182                         ctx->expanded_path_alloc_len = len_needed;
 183                 }
 184                 expanded_path_len_save = ctx->expanded_path_len;
 185
 186                 ctx->expanded_path[ctx->expanded_path_len++] = WIM_PATH_SEPARATOR;
 187                 tmemcpy(&ctx->expanded_path[ctx->expanded_path_len],
 188                         name, name_len);
 189                 ctx->expanded_path_len += name_len;
 190                 ctx->expanded_path[ctx->expanded_path_len] = T('\0');
 191
 192                 switch (wildcard_status(&ctx->wildcard_path[
 193                                 ctx->cur_component_offset +
 194                                 ctx->cur_component_len]))
 195                 {
 196                 case WILDCARD_STATUS_DONE_TRAILING_SLASHES:
 197                         if (!dentry_is_directory(cur_dentry)) {
 198                                 ret = 0;
 199                                 break;
 200                         }
 201                         /* Fall through  */
 202                 case WILDCARD_STATUS_DONE_FULLY:
 203                         ret = (*ctx->consume_path)(ctx->expanded_path,
 204                                                    ctx->consume_path_ctx,
 205                                                    false);
 206                         ctx->consume_path_count++;
 207                         break;
 208                 case WILDCARD_STATUS_NOT_DONE:
 209                         ret = expand_wildcard_recursive(cur_dentry, ctx);
 210                         break;
 211                 }
 212                 ctx->expanded_path_len = expanded_path_len_save;
 213                 ctx->expanded_path[expanded_path_len_save] = T('\0');
 214         } else {
 215                 ret = 0;
 216         }
 217
 218 out_free_name:
 219 #if !TCHAR_IS_UTF16LE
 220         FREE(name);
 221 #endif
 222         return ret;
 223 }
 224
 225 static int
 226 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
 227                           struct match_dentry_ctx *ctx)
 228 {
 229         tchar *w;
 230         size_t begin;
 231         size_t end;
 232         size_t len;
 233         size_t offset_save;
 234         size_t len_save;
 235         int ret;
 236
 237         w = ctx->wildcard_path;
 238
 239         begin = ctx->cur_component_offset + ctx->cur_component_len;
 240         while (is_any_path_separator(w[begin]))
 241                 begin++;
 242
 243         end = begin;
 244
 245         while (w[end] != T('\0') && !is_any_path_separator(w[end]))
 246                 end++;
 247
 248         len = end - begin;
 249
 250         if (len == 0)
 251                 return 0;
 252
 253         offset_save = ctx->cur_component_offset;
 254         len_save = ctx->cur_component_len;
 255
 256         ctx->cur_component_offset = begin;
 257         ctx->cur_component_len = len;
 258
 259         ret = for_dentry_child(cur_dentry, match_dentry, ctx);
 260
 261         ctx->cur_component_len = len_save;
 262         ctx->cur_component_offset = offset_save;
 263
 264         return ret;
 265 }
 266
 267 static int
 268 expand_wildcard(WIMStruct *wim,
 269                 const tchar *wildcard_path,
 270                 int (*consume_path)(const tchar *, void *, bool),
 271                 void *consume_path_ctx,
 272                 u32 flags)
 273 {
 274         struct wim_dentry *root;
 275         int ret;
 276
 277         root = wim_root_dentry(wim);
 278         if (root == NULL)
 279                 goto no_match;
 280
 281         struct match_dentry_ctx ctx = {
 282                 .consume_path = consume_path,
 283                 .consume_path_ctx = consume_path_ctx,
 284                 .consume_path_count = 0,
 285                 .expanded_path = MALLOC(256 * sizeof(ctx.expanded_path[0])),
 286                 .expanded_path_len = 0,
 287                 .expanded_path_alloc_len = 256,
 288                 .wildcard_path = TSTRDUP(wildcard_path),
 289                 .cur_component_offset = 0,
 290                 .cur_component_len = 0,
 291                 .case_insensitive = ((flags & WILDCARD_FLAG_CASE_INSENSITIVE) != 0),
 292         };
 293
 294         if (ctx.expanded_path == NULL || ctx.wildcard_path == NULL) {
 295                 FREE(ctx.expanded_path);
 296                 FREE(ctx.wildcard_path);
 297                 return WIMLIB_ERR_NOMEM;
 298         }
 299
 300         ret = expand_wildcard_recursive(root, &ctx);
 301         FREE(ctx.expanded_path);
 302         FREE(ctx.wildcard_path);
 303         if (ret == 0 && ctx.consume_path_count == 0)
 304                 goto no_match;
 305         return ret;
 306
 307 no_match:
 308         ret = 0;
 309         if (flags & WILDCARD_FLAG_USE_LITERAL_IF_NO_MATCHES)
 310                 ret = (*consume_path)(wildcard_path, consume_path_ctx, true);
 311
 312         if (flags & WILDCARD_FLAG_WARN_IF_NO_MATCH)
 313                 WARNING("No matches for wildcard path \"%"TS"\"", wildcard_path);
 314
 315         if (flags & WILDCARD_FLAG_ERROR_IF_NO_MATCH) {
 316                 ERROR("No matches for wildcard path \"%"TS"\"", wildcard_path);
 317                 ret = WIMLIB_ERR_PATH_DOES_NOT_EXIST;
 318         }
 319         return ret;
 320 }
 321
 322 struct expanded_paths_ctx {
 323         tchar **expanded_paths;
 324         size_t num_expanded_paths;
 325         size_t alloc_length;
 326 };
 327
 328 static int
 329 append_path_cb(const tchar *path, void *_ctx, bool may_need_trans)
 330 {
 331         struct expanded_paths_ctx *ctx = _ctx;
 332         tchar *path_dup;
 333
 334         if (ctx->num_expanded_paths == ctx->alloc_length) {
 335                 tchar **new_paths;
 336                 size_t new_alloc_length = max(ctx->alloc_length + 8,
 337                                               ctx->alloc_length * 3 / 2);
 338
 339                 new_paths = REALLOC(ctx->expanded_paths,
 340                                     new_alloc_length * sizeof(new_paths[0]));
 341                 if (new_paths == NULL)
 342                         return WIMLIB_ERR_NOMEM;
 343                 ctx->expanded_paths = new_paths;
 344                 ctx->alloc_length = new_alloc_length;
 345         }
 346         path_dup = TSTRDUP(path);
 347         if (path_dup == NULL)
 348                 return WIMLIB_ERR_NOMEM;
 349         if (may_need_trans) {
 350                 for (tchar *p = path_dup; *p; p++)
 351                         if (is_any_path_separator(*p))
 352                                 *p = WIM_PATH_SEPARATOR;
 353         }
 354         ctx->expanded_paths[ctx->num_expanded_paths++] = path_dup;
 355         return 0;
 356 }
 357
 358 int
 359 expand_wildcard_wim_paths(WIMStruct *wim,
 360                           const tchar * const *wildcards,
 361                           size_t num_wildcards,
 362                           tchar ***expanded_paths_ret,
 363                           size_t *num_expanded_paths_ret,
 364                           u32 flags)
 365 {
 366         int ret;
 367         struct expanded_paths_ctx ctx = {
 368                 .expanded_paths = NULL,
 369                 .num_expanded_paths = 0,
 370                 .alloc_length = 0,
 371         };
 372         for (size_t i = 0; i < num_wildcards; i++) {
 373                 ret = expand_wildcard(wim, wildcards[i], append_path_cb, &ctx,
 374                                       flags);
 375                 if (ret)
 376                         goto out_free;
 377         }
 378         *expanded_paths_ret = ctx.expanded_paths;
 379         *num_expanded_paths_ret = ctx.num_expanded_paths;
 380         return 0;
 381
 382 out_free:
 383         for (size_t i = 0; i < ctx.num_expanded_paths; i++)
 384                 FREE(ctx.expanded_paths[i]);
 385         FREE(ctx.expanded_paths);
 386         return ret;
 387 }