glob_helper(
    const char *path,
    int dirsep, /* '/' should be placed before appending child entry's name to 'path'. */
    enum answer exist, /* Does 'path' indicate an existing entry? */
    enum answer isdir, /* Does 'path' indicate a directory or a symlink to a directory? */
    struct glob_pattern **beg,
    struct glob_pattern **end,
    int flags,
    ruby_glob_func *func,
    VALUE arg,
    rb_encoding *enc)
{
    struct stat st;
    int status = 0;
    struct glob_pattern **cur, **new_beg, **new_end;
    int plain = 0, magical = 0, recursive = 0, match_all = 0, match_dir = 0;
    int escape = !(flags & FNM_NOESCAPE);
    long pathlen;

    for (cur = beg; cur < end; ++cur) {
	struct glob_pattern *p = *cur;
	if (p->type == RECURSIVE) {
	    recursive = 1;
	    p = p->next;
	}
	switch (p->type) {
	  case PLAIN:
	    plain = 1;
	    break;
	  case ALPHA:
#if USE_NAME_ON_FS == 1
	    plain = 1;
#else
	    magical = 1;
#endif
	    break;
	  case MAGICAL:
	    magical = 2;
	    break;
	  case MATCH_ALL:
	    match_all = 1;
	    break;
	  case MATCH_DIR:
	    match_dir = 1;
	    break;
	  case RECURSIVE:
	    rb_bug("continuous RECURSIVEs");
	}
    }

    pathlen = strlen(path);
    if (*path) {
	if (match_all && exist == UNKNOWN) {
	    if (do_lstat(path, &st, flags, enc) == 0) {
		exist = YES;
		isdir = S_ISDIR(st.st_mode) ? YES : S_ISLNK(st.st_mode) ? UNKNOWN : NO;
	    }
	    else {
		exist = NO;
		isdir = NO;
	    }
	}
	if (match_dir && isdir == UNKNOWN) {
	    if (do_stat(path, &st, flags, enc) == 0) {
		exist = YES;
		isdir = S_ISDIR(st.st_mode) ? YES : NO;
	    }
	    else {
		exist = NO;
		isdir = NO;
	    }
	}
	if (match_all && exist == YES) {
	    status = glob_call_func(func, path, arg, enc);
	    if (status) return status;
	}
	if (match_dir && isdir == YES) {
	    char *tmp = join_path(path, pathlen, dirsep, "", 0);
	    if (!tmp) return -1;
	    status = glob_call_func(func, tmp, arg, enc);
	    GLOB_FREE(tmp);
	    if (status) return status;
	}
    }

    if (exist == NO || isdir == NO) return 0;

    if (magical || recursive) {
	struct dirent *dp;
	DIR *dirp;
# if USE_NAME_ON_FS == 2
	char *plainname = 0;
# endif
	IF_NORMALIZE_UTF8PATH(int norm_p);
# if USE_NAME_ON_FS == 2
	if (cur + 1 == end && (*cur)->type <= ALPHA) {
	    plainname = join_path(path, pathlen, dirsep, (*cur)->str, strlen((*cur)->str));
	    if (!plainname) return -1;
	    dirp = do_opendir(plainname, flags, enc);
	    GLOB_FREE(plainname);
	}
	else
# endif
	dirp = do_opendir(*path ? path : ".", flags, enc);
	if (dirp == NULL) {
# if FNM_SYSCASE || NORMALIZE_UTF8PATH
	    if ((magical < 2) && !recursive && (errno == EACCES)) {
		/* no read permission, fallback */
		goto literally;
	    }
# endif
	    return 0;
	}
	IF_NORMALIZE_UTF8PATH(norm_p = need_normalization(dirp, *path ? path : "."));

# if NORMALIZE_UTF8PATH
	if (!(norm_p || magical || recursive)) {
	    closedir(dirp);
	    goto literally;
	}
# endif
# ifdef HAVE_GETATTRLIST
	if (is_case_sensitive(dirp) == 0)
	    flags |= FNM_CASEFOLD;
# endif
	while ((dp = READDIR(dirp, enc)) != NULL) {
	    char *buf;
	    enum answer new_isdir = UNKNOWN;
	    const char *name;
	    size_t namlen;
	    int dotfile = 0;
	    IF_NORMALIZE_UTF8PATH(VALUE utf8str = Qnil);

	    if (recursive && dp->d_name[0] == '.') {
		++dotfile;
		if (!dp->d_name[1]) {
		    /* unless DOTMATCH, skip current directories not to recurse infinitely */
		    if (!(flags & FNM_DOTMATCH)) continue;
		    ++dotfile;
		}
		else if (dp->d_name[1] == '.' && !dp->d_name[2]) {
		    /* always skip parent directories not to recurse infinitely */
		    continue;
		}
	    }

	    name = dp->d_name;
	    namlen = NAMLEN(dp);
# if NORMALIZE_UTF8PATH
	    if (norm_p && has_nonascii(name, namlen)) {
		if (!NIL_P(utf8str = rb_str_normalize_ospath(name, namlen))) {
		    RSTRING_GETMEM(utf8str, name, namlen);
		}
	    }
# endif
	    buf = join_path(path, pathlen, dirsep, name, namlen);
	    IF_NORMALIZE_UTF8PATH(if (!NIL_P(utf8str)) rb_str_resize(utf8str, 0));
	    if (!buf) {
		status = -1;
		break;
	    }
	    name = buf + pathlen + (dirsep != 0);
	    if (recursive && dotfile < ((flags & FNM_DOTMATCH) ? 2 : 1)) {
		/* RECURSIVE never match dot files unless FNM_DOTMATCH is set */
#ifndef _WIN32
		if (do_lstat(buf, &st, flags, enc) == 0)
		    new_isdir = S_ISDIR(st.st_mode) ? YES : S_ISLNK(st.st_mode) ? UNKNOWN : NO;
		else
		    new_isdir = NO;
#else
		new_isdir = dp->d_isdir ? (!dp->d_isrep ? YES : UNKNOWN) : NO;
#endif
	    }

	    new_beg = new_end = GLOB_ALLOC_N(struct glob_pattern *, (end - beg) * 2);
	    if (!new_beg) {
		GLOB_FREE(buf);
		status = -1;
		break;
	    }

	    for (cur = beg; cur < end; ++cur) {
		struct glob_pattern *p = *cur;
		if (p->type == RECURSIVE) {
		    if (new_isdir == YES) /* not symlink but real directory */
			*new_end++ = p; /* append recursive pattern */
		    p = p->next; /* 0 times recursion */
		}
		switch (p->type) {
		  case ALPHA:
# if USE_NAME_ON_FS == 2
		    if (plainname) {
			*new_end++ = p->next;
			break;
		    }
# endif
		  case PLAIN:
		  case MAGICAL:
		    if (fnmatch(p->str, enc, name, flags) == 0)
			*new_end++ = p->next;
		  default:
		    break;
		}
	    }

	    status = glob_helper(buf, 1, YES, new_isdir, new_beg, new_end,
				 flags, func, arg, enc);
	    GLOB_FREE(buf);
	    GLOB_FREE(new_beg);
	    if (status) break;
	}

	closedir(dirp);
    }
    else if (plain) {
	struct glob_pattern **copy_beg, **copy_end, **cur2;

# if FNM_SYSCASE || NORMALIZE_UTF8PATH
      literally:
# endif
	copy_beg = copy_end = GLOB_ALLOC_N(struct glob_pattern *, end - beg);
	if (!copy_beg) return -1;
	for (cur = beg; cur < end; ++cur)
	    *copy_end++ = (*cur)->type <= ALPHA ? *cur : 0;

	for (cur = copy_beg; cur < copy_end; ++cur) {
	    if (*cur) {
		char *buf;
		char *name;
		size_t len = strlen((*cur)->str) + 1;
		name = GLOB_ALLOC_N(char, len);
		if (!name) {
		    status = -1;
		    break;
		}
		memcpy(name, (*cur)->str, len);
		if (escape)
		    len = remove_backslashes(name, name+len-1, enc) - name;

		new_beg = new_end = GLOB_ALLOC_N(struct glob_pattern *, end - beg);
		if (!new_beg) {
		    GLOB_FREE(name);
		    status = -1;
		    break;
		}
		*new_end++ = (*cur)->next;
		for (cur2 = cur + 1; cur2 < copy_end; ++cur2) {
		    if (*cur2 && fnmatch((*cur2)->str, enc, name, flags) == 0) {
			*new_end++ = (*cur2)->next;
			*cur2 = 0;
		    }
		}

		buf = join_path(path, pathlen, dirsep, name, len);
		GLOB_FREE(name);
		if (!buf) {
		    GLOB_FREE(new_beg);
		    status = -1;
		    break;
		}
#if USE_NAME_ON_FS == 1
		if ((*cur)->type == ALPHA) {
		    long base = pathlen + (dirsep != 0);
		    buf = replace_real_basename(buf, base, enc, IF_NORMALIZE_UTF8PATH(1)+0);
		}
#endif
		status = glob_helper(buf, 1, UNKNOWN, UNKNOWN, new_beg,
				     new_end, flags, func, arg, enc);
		GLOB_FREE(buf);
		GLOB_FREE(new_beg);
		if (status) break;
	    }
	}

	GLOB_FREE(copy_beg);
    }

    return status;
}