common/misc/glob.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#pragma prototyped

/*
 * file name expansion - posix.2 glob with gnu and ast extensions
 *
 *  David Korn
 *  Glenn Fowler
 *  AT&T Research
 */

#include <ast.h>
#include <ls.h>
#include <stak.h>
#include <ast_dir.h>
#include <error.h>
#include <ctype.h>
#include <regex.h>

#define GLOB_MAGIC  0xaaaa0000

#define MATCH_RAW   1
#define MATCH_MAKE  2
#define MATCH_META  4

#define MATCHPATH(g)    (offsetof(globlist_t,gl_path)+(g)->gl_extra)

typedef int (*GL_error_f)(const char*, int);
typedef void* (*GL_opendir_f)(const char*);
typedef struct dirent* (*GL_readdir_f)(void*);
typedef void (*GL_closedir_f)(void*);
typedef int (*GL_stat_f)(const char*, struct stat*);

#define _GLOB_PRIVATE_ \
    GL_error_f  gl_errfn; \
    int     gl_error; \
    char*       gl_nextpath; \
    globlist_t* gl_rescan; \
    globlist_t* gl_match; \
    Stak_t*     gl_stak; \
    int     re_flags; \
    int     re_first; \
    regex_t*    gl_ignore; \
    regex_t*    gl_ignorei; \
    regex_t     re_ignore; \
    regex_t     re_ignorei; \
    unsigned long   gl_starstar; \
    char*       gl_opt; \
    char*       gl_pat; \
    char*       gl_pad[4];

#include <glob.h>

/*
 * default gl_diropen
 */

static void*
gl_diropen(glob_t* gp, const char* path)
{
    return (*gp->gl_opendir)(path);
}

/*
 * default gl_dirnext
 */

static char*
gl_dirnext(glob_t* gp, void* handle)
{
    struct dirent*  dp;

    while (dp = (struct dirent*)(*gp->gl_readdir)(handle))
    {
#ifdef D_TYPE
        if (D_TYPE(dp) != DT_UNKNOWN && D_TYPE(dp) != DT_DIR && D_TYPE(dp) != DT_LNK)
            gp->gl_status |= GLOB_NOTDIR;
#endif
        return dp->d_name;
    }
    return 0;
}

/*
 * default gl_dirclose
 */

static void
gl_dirclose(glob_t* gp, void* handle)
{
    (gp->gl_closedir)(handle);
}

/*
 * default gl_type
 */

static int
gl_type(glob_t* gp, const char* path, int flags)
{
    register int    type;
    struct stat st;

    if ((flags & GLOB_STARSTAR) ? (*gp->gl_lstat)(path, &st) : (*gp->gl_stat)(path, &st))
        type = 0;
    else if (S_ISDIR(st.st_mode))
        type = GLOB_DIR;
    else if (!S_ISREG(st.st_mode))
        type = GLOB_DEV;
    else if (st.st_mode & (S_IXUSR|S_IXGRP|S_IXOTH))
        type = GLOB_EXE;
    else
        type = GLOB_REG;
    return type;
}

/*
 * default gl_attr
 */

static int
gl_attr(glob_t* gp, const char* path, int flags)
{
    return strchr(astconf("PATH_ATTRIBUTES", path, NiL), 'c') ? GLOB_ICASE : 0;
}

/*
 * default gl_nextdir
 */

static char*
gl_nextdir(glob_t* gp, char* dir)
{
    if (!(dir = gp->gl_nextpath))
        dir = gp->gl_nextpath = stakcopy(pathbin());
    switch (*gp->gl_nextpath)
    {
    case 0:
        dir = 0;
        break;
    case ':':
        while (*gp->gl_nextpath == ':')
            gp->gl_nextpath++;
        dir = ".";
        break;
    default:
        while (*gp->gl_nextpath)
            if (*gp->gl_nextpath++ == ':')
            {
                *(gp->gl_nextpath - 1) = 0;
                break;
            }
        break;
    }
    return dir;
}

/*
 * error intercept
 */

static int
errorcheck(register glob_t* gp, const char* path)
{
    int r = 1;

    if (gp->gl_errfn)
        r = (*gp->gl_errfn)(path, errno);
    if (gp->gl_flags & GLOB_ERR)
        r = 0;
    if (!r)
        gp->gl_error = GLOB_ABORTED;
    return r;
}

/*
 * remove backslashes
 */

static void
trim(register char* sp, register char* p1, int* n1, register char* p2, int* n2)
{
    register char*  dp = sp;
    register int    c;

    if (p1)
        *n1 = 0;
    if (p2)
        *n2 = 0;
    do
    {
        if ((c = *sp++) == '\\')
            c = *sp++;
        if (sp == p1)
        {
            p1 = 0;
            *n1 = sp - dp - 1;
        }
        if (sp == p2)
        {
            p2 = 0;
            *n2 = sp - dp - 1;
        }
    } while (*dp++ = c);
}

static void
addmatch(register glob_t* gp, const char* dir, const char* pat, register const char* rescan, char* endslash, int meta)
{
    register globlist_t*    ap;
    int         offset;
    int         type;

    stakseek(MATCHPATH(gp));
    if (dir)
    {
        stakputs(dir);
        stakputc(gp->gl_delim);
    }
    if (endslash)
        *endslash = 0;
    stakputs(pat);
    if (rescan)
    {
        if ((*gp->gl_type)(gp, stakptr(MATCHPATH(gp)), 0) != GLOB_DIR)
            return;
        stakputc(gp->gl_delim);
        offset = staktell();
        /* if null, reserve room for . */
        if (*rescan)
            stakputs(rescan);
        else
            stakputc(0);
        stakputc(0);
        rescan = stakptr(offset);
        ap = (globlist_t*)stakfreeze(0);
        ap->gl_begin = (char*)rescan;
        ap->gl_next = gp->gl_rescan;
        gp->gl_rescan = ap;
    }
    else
    {
        if (!endslash && (gp->gl_flags & GLOB_MARK) && (type = (*gp->gl_type)(gp, stakptr(MATCHPATH(gp)), 0)))
        {
            if ((gp->gl_flags & GLOB_COMPLETE) && type != GLOB_EXE)
            {
                stakseek(0);
                return;
            }
            else if (type == GLOB_DIR && (gp->gl_flags & GLOB_MARK))
                stakputc(gp->gl_delim);
        }
        ap = (globlist_t*)stakfreeze(1);
        ap->gl_next = gp->gl_match;
        gp->gl_match = ap;
        gp->gl_pathc++;
    }
    ap->gl_flags = MATCH_RAW|meta;
    if (gp->gl_flags & GLOB_COMPLETE)
        ap->gl_flags |= MATCH_MAKE;
}

/*
 * this routine builds a list of files that match a given pathname
 * uses REG_SHELL of <regex> to match each component
 * a leading . must match explicitly
 */

static void
glob_dir(glob_t* gp, globlist_t* ap, int re_flags)
{
    register char*      rescan;
    register char*      prefix;
    register char*      pat;
    register char*      name;
    register int        c;
    char*           dirname;
    void*           dirf;
    char            first;
    regex_t*        ire;
    regex_t*        pre;
    regex_t         rec;
    regex_t         rei;
    int         notdir;
    int         t1;
    int         t2;
    int         bracket;

    int         anymeta = ap->gl_flags & MATCH_META;
    int         complete = 0;
    int         err = 0;
    int         meta = ((gp->re_flags & REG_ICASE) && *ap->gl_begin != '/') ? MATCH_META : 0;
    int         quote = 0;
    int         savequote = 0;
    char*           restore1 = 0;
    char*           restore2 = 0;
    regex_t*        prec = 0;
    regex_t*        prei = 0;
    char*           matchdir = 0;
    int         starstar = 0;

    if (*gp->gl_intr)
    {
        gp->gl_error = GLOB_INTR;
        return;
    }
    pat = rescan = ap->gl_begin;
    prefix = dirname = ap->gl_path + gp->gl_extra;
    first = (rescan == prefix);
again:
    bracket = 0;
    for (;;)
    {
        switch (c = *rescan++)
        {
        case 0:
            if (meta)
            {
                rescan = 0;
                break;
            }
            if (quote)
            {
                trim(ap->gl_begin, rescan, &t1, NiL, NiL);
                rescan -= t1;
            }
            if (!first && !*rescan && *(rescan - 2) == gp->gl_delim)
            {
                *(rescan - 2) = 0;
                c = (*gp->gl_type)(gp, prefix, 0);
                *(rescan - 2) = gp->gl_delim;
                if (c == GLOB_DIR)
                    addmatch(gp, NiL, prefix, NiL, rescan - 1, anymeta);
            }
            else if ((anymeta || !(gp->gl_flags & GLOB_NOCHECK)) && (*gp->gl_type)(gp, prefix, 0))
                addmatch(gp, NiL, prefix, NiL, NiL, anymeta);
            return;
        case '[':
            if (!bracket)
            {
                bracket = MATCH_META;
                if (*rescan == '!' || *rescan == '^')
                    rescan++;
                if (*rescan == ']')
                    rescan++;
            }
            continue;
        case ']':
            meta |= bracket;
            continue;
        case '(':
            if (!(gp->gl_flags & GLOB_AUGMENTED))
                continue;
        case '*':
        case '?':
            meta = MATCH_META;
            continue;
        case '\\':
            if (!(gp->gl_flags & GLOB_NOESCAPE))
            {
                quote = 1;
                if (*rescan)
                    rescan++;
            }
            continue;
        default:
            if (c == gp->gl_delim)
            {
                if (meta)
                    break;
                pat = rescan;
                bracket = 0;
                savequote = quote;
            }
            continue;
        }
        break;
    }
    anymeta |= meta;
    if (matchdir)
        goto skip;
    if (pat == prefix)
    {
        prefix = 0;
        if (!rescan && (gp->gl_flags & GLOB_COMPLETE))
        {
            complete = 1;
            dirname = 0;
        }
        else
            dirname = ".";
    }
    else
    {
        if (pat == prefix + 1)
            dirname = "/";
        if (savequote)
        {
            quote = 0;
            trim(ap->gl_begin, pat, &t1, rescan, &t2);
            pat -= t1;
            if (rescan)
                rescan -= t2;
        }
        *(restore1 = pat - 1) = 0;
    }
    if (!complete && (gp->gl_flags & GLOB_STARSTAR))
        while (pat[0] == '*' && pat[1] == '*' && (pat[2] == '/'  || pat[2]==0))
        {
            matchdir = pat;
            if (pat[2])
            {
                pat += 3;
                while (*pat=='/')
                    pat++;
                if (*pat)
                    continue;
            }
            rescan = *pat?0:pat;
            pat = "*";
            goto skip;
        }
    if (matchdir)
    {
        rescan = pat;
        goto again;
    }
skip:
    if (rescan)
        *(restore2 = rescan - 1) = 0;
    if (rescan && !complete && (gp->gl_flags & GLOB_STARSTAR))
    {
        register char*  p = rescan;

        while (p[0] == '*' && p[1] == '*' && (p[2] == '/'  || p[2]==0))
        {
            rescan = p;
            if (starstar = (p[2]==0))
                break;
            p += 3;
            while (*p=='/')
                p++;
            if (*p==0)
            {
                starstar = 2;
                break;
            }
        }
    }
    if (matchdir)
        gp->gl_starstar++;
    if (gp->gl_opt)
        pat = strcpy(gp->gl_opt, pat);
    for (;;)
    {
        if (complete)
        {
            if (!(dirname = (*gp->gl_nextdir)(gp, dirname)))
                break;
            prefix = streq(dirname, ".") ? (char*)0 : dirname;
        }
        if ((!starstar && !gp->gl_starstar || (*gp->gl_type)(gp, dirname, GLOB_STARSTAR) == GLOB_DIR) && (dirf = (*gp->gl_diropen)(gp, dirname)))
        {
            if (!(gp->re_flags & REG_ICASE) && ((*gp->gl_attr)(gp, dirname, 0) & GLOB_ICASE))
            {
                if (!prei)
                {
                    if (err = regcomp(&rei, pat, gp->re_flags|REG_ICASE))
                        break;
                    prei = &rei;
                    if (gp->re_first)
                    {
                        gp->re_first = 0;
                        gp->re_flags = regstat(prei)->re_flags & ~REG_ICASE;
                    }
                }
                pre = prei;
            }
            else
            {
                if (!prec)
                {
                    if (err = regcomp(&rec, pat, gp->re_flags))
                        break;
                    prec = &rec;
                    if (gp->re_first)
                    {
                        gp->re_first = 0;
                        gp->re_flags = regstat(prec)->re_flags;
                    }
                }
                pre = prec;
            }
            if ((ire = gp->gl_ignore) && (gp->re_flags & REG_ICASE))
            {
                if (!gp->gl_ignorei)
                {
                    if (regcomp(&gp->re_ignorei, gp->gl_fignore, re_flags|REG_ICASE))
                    {
                        gp->gl_error = GLOB_APPERR;
                        break;
                    }
                    gp->gl_ignorei = &gp->re_ignorei;
                }
                ire = gp->gl_ignorei;
            }
            if (restore2)
                *restore2 = gp->gl_delim;
            while ((name = (*gp->gl_dirnext)(gp, dirf)) && !*gp->gl_intr)
            {
                if (notdir = (gp->gl_status & GLOB_NOTDIR))
                    gp->gl_status &= ~GLOB_NOTDIR;
                if (ire && !regexec(ire, name, 0, NiL, 0))
                    continue;
                if (matchdir && (name[0] != '.' || name[1] && (name[1] != '.' || name[2])) && !notdir)
                    addmatch(gp, prefix, name, matchdir, NiL, anymeta);
                if (!regexec(pre, name, 0, NiL, 0))
                {
                    if (!rescan || !notdir)
                        addmatch(gp, prefix, name, rescan, NiL, anymeta);
                    if (starstar==1 || (starstar==2 && !notdir))
                        addmatch(gp, prefix, name, starstar==2?"":NiL, NiL, anymeta);
                }
                errno = 0;
            }
            (*gp->gl_dirclose)(gp, dirf);
            if (err || errno && !errorcheck(gp, dirname))
                break;
        }
        else if (!complete && !errorcheck(gp, dirname))
            break;
        if (!complete)
            break;
        if (*gp->gl_intr)
        {
            gp->gl_error = GLOB_INTR;
            break;
        }
    }
    if (restore1)
        *restore1 = gp->gl_delim;
    if (restore2)
        *restore2 = gp->gl_delim;
    if (prec)
        regfree(prec);
    if (prei)
        regfree(prei);
    if (err == REG_ESPACE)
        gp->gl_error = GLOB_NOSPACE;
}

int
glob(const char* pattern, int flags, int (*errfn)(const char*, int), register glob_t* gp)
{
    register globlist_t*    ap;
    register char*      pat;
    globlist_t*     top;
    Stak_t*         oldstak;
    char**          argv;
    char**          av;
    size_t          skip;
    unsigned long       f;
    int         n;
    int         x;
    int         re_flags;

    const char*     nocheck = pattern;
    int         optlen = 0;
    int         suflen = 0;
    int         extra = 1;
    unsigned char       intr = 0;

    gp->gl_rescan = 0;
    gp->gl_error = 0;
    gp->gl_errfn = errfn;
    if (flags & GLOB_APPEND)
    {
        if ((gp->gl_flags |= GLOB_APPEND) ^ (flags|GLOB_MAGIC))
            return GLOB_APPERR;
        if (((gp->gl_flags & GLOB_STACK) == 0) == (gp->gl_stak == 0))
            return GLOB_APPERR;
        if (gp->gl_starstar > 1)
            gp->gl_flags |= GLOB_STARSTAR;
        else
            gp->gl_starstar = 0;
    }
    else
    {
        gp->gl_flags = (flags&0xffff)|GLOB_MAGIC;
        gp->re_flags = REG_SHELL|REG_NOSUB|REG_LEFT|REG_RIGHT|((flags&GLOB_AUGMENTED)?REG_AUGMENTED:0);
        gp->gl_pathc = 0;
        gp->gl_ignore = 0;
        gp->gl_ignorei = 0;
        gp->gl_starstar = 0;
        if (!(flags & GLOB_DISC))
        {
            gp->gl_fignore = 0;
            gp->gl_suffix = 0;
            gp->gl_intr = 0;
            gp->gl_delim = 0;
            gp->gl_handle = 0;
            gp->gl_diropen = 0;
            gp->gl_dirnext = 0;
            gp->gl_dirclose = 0;
            gp->gl_type = 0;
            gp->gl_attr = 0;
            gp->gl_nextdir = 0;
            gp->gl_stat = 0;
            gp->gl_lstat = 0;
            gp->gl_extra = 0;
        }
        if (!(flags & GLOB_ALTDIRFUNC))
        {
            gp->gl_opendir = (GL_opendir_f)opendir;
            gp->gl_readdir = (GL_readdir_f)readdir;
            gp->gl_closedir = (GL_closedir_f)closedir;
            if (!gp->gl_stat)
                gp->gl_stat = (GL_stat_f)pathstat;
        }
        if (!gp->gl_lstat)
            gp->gl_lstat = (GL_stat_f)lstat;
        if (!gp->gl_intr)
            gp->gl_intr = &intr;
        if (!gp->gl_delim)
            gp->gl_delim = '/';
        if (!gp->gl_diropen)
            gp->gl_diropen = gl_diropen;
        if (!gp->gl_dirnext)
            gp->gl_dirnext = gl_dirnext;
        if (!gp->gl_dirclose)
            gp->gl_dirclose = gl_dirclose;
        if (!gp->gl_type)
            gp->gl_type = gl_type;
        if (!gp->gl_attr)
            gp->gl_attr = gl_attr;
        if (flags & GLOB_GROUP)
            gp->re_flags |= REG_SHELL_GROUP;
        if (flags & GLOB_ICASE)
            gp->re_flags |= REG_ICASE;
        if (!gp->gl_fignore)
            gp->re_flags |= REG_SHELL_DOT;
        else if (*gp->gl_fignore)
        {
            if (regcomp(&gp->re_ignore, gp->gl_fignore, gp->re_flags))
                return GLOB_APPERR;
            gp->gl_ignore = &gp->re_ignore;
        }
        if (gp->gl_flags & GLOB_STACK)
            gp->gl_stak = 0;
        else if (!(gp->gl_stak = stakcreate(0)))
            return GLOB_NOSPACE;
        if ((gp->gl_flags & GLOB_COMPLETE) && !gp->gl_nextdir)
            gp->gl_nextdir = gl_nextdir;
    }
    skip = gp->gl_pathc;
    if (gp->gl_stak)
        oldstak = stakinstall(gp->gl_stak, 0);
    if (flags & GLOB_DOOFFS)
        extra += gp->gl_offs;
    if (gp->gl_suffix)
        suflen =  strlen(gp->gl_suffix);
    if (*(pat = (char*)pattern) == '~' && *(pat + 1) == '(')
    {
        f = gp->gl_flags;
        n = 1;
        x = 1;
        pat += 2;
        for (;;)
        {
            switch (*pat++)
            {
            case 0:
            case ':':
                break;
            case '-':
                n = 0;
                continue;
            case '+':
                n = 1;
                continue;
            case 'i':
                if (n)
                    f |= GLOB_ICASE;
                else
                    f &= ~GLOB_ICASE;
                continue;
            case 'M':
                if (n)
                    f |= GLOB_BRACE;
                else
                    f &= ~GLOB_BRACE;
                continue;
            case 'N':
                if (n)
                    f &= ~GLOB_NOCHECK;
                else
                    f |= GLOB_NOCHECK;
                continue;
            case 'O':
                if (n)
                    f |= GLOB_STARSTAR;
                else
                    f &= ~GLOB_STARSTAR;
                continue;
            case ')':
                flags = (gp->gl_flags = f) & 0xffff;
                if (f & GLOB_ICASE)
                    gp->re_flags |= REG_ICASE;
                else
                    gp->re_flags &= ~REG_ICASE;
                if (x)
                    optlen = pat - (char*)pattern;
                break;
            default:
                x = 0;
                continue;
            }
            break;
        }
    }
    top = ap = (globlist_t*)stakalloc((optlen ? 2 : 1) * strlen(pattern) + sizeof(globlist_t) + suflen + gp->gl_extra);
    ap->gl_next = 0;
    ap->gl_flags = 0;
    ap->gl_begin = ap->gl_path + gp->gl_extra;
    pat = strcopy(ap->gl_begin, pattern + optlen);
    if (suflen)
        pat = strcopy(pat, gp->gl_suffix);
    if (optlen)
        strlcpy(gp->gl_pat = gp->gl_opt = pat + 1, pattern, optlen);
    else
        gp->gl_pat = 0;
    suflen = 0;
    if (!(flags & GLOB_LIST))
        gp->gl_match = 0;
    re_flags = gp->re_flags;
    gp->re_first = 1;
    do
    {
        gp->gl_rescan = ap->gl_next;
        glob_dir(gp, ap, re_flags);
    } while (!gp->gl_error && (ap = gp->gl_rescan));
    gp->re_flags = re_flags;
    if (gp->gl_pathc == skip)
    {
        if (flags & GLOB_NOCHECK)
        {
            gp->gl_pathc++;
            top->gl_next = gp->gl_match;
            gp->gl_match = top;
            strcopy(top->gl_path + gp->gl_extra, nocheck);
        }
        else
            gp->gl_error = GLOB_NOMATCH;
    }
    if (flags & GLOB_LIST)
        gp->gl_list = gp->gl_match;
    else
    {
        argv = (char**)stakalloc((gp->gl_pathc + extra) * sizeof(char*));
        if (gp->gl_flags & GLOB_APPEND)
        {
            skip += --extra;
            memcpy(argv, gp->gl_pathv, skip * sizeof(char*));
            av = argv + skip;
        }
        else
        {
            av = argv;
            while (--extra > 0)
                *av++ = 0;
        }
        gp->gl_pathv = argv;
        argv = av;
        ap = gp->gl_match;
        while (ap)
        {
            *argv++ = ap->gl_path + gp->gl_extra;
            ap = ap->gl_next;
        }
        *argv = 0;
        if (!(flags & GLOB_NOSORT) && (argv - av) > 1)
        {
            strsort(av, argv - av, strcoll);
            if (gp->gl_starstar > 1)
                av[gp->gl_pathc = struniq(av, argv - av)] = 0;
            gp->gl_starstar = 0;
        }
    }
    if (gp->gl_starstar > 1)
        gp->gl_flags &= ~GLOB_STARSTAR;
    if (gp->gl_stak)
        stakinstall(oldstak, 0);
    return gp->gl_error;
}

void
globfree(glob_t* gp)
{
    if ((gp->gl_flags & GLOB_MAGIC) == GLOB_MAGIC)
    {
        gp->gl_flags &= ~GLOB_MAGIC;
        if (gp->gl_stak)
            stkclose(gp->gl_stak);
        if (gp->gl_ignore)
            regfree(gp->gl_ignore);
        if (gp->gl_ignorei)
            regfree(gp->gl_ignorei);
    }
}