/* glob 命令 --

  glob params

   在 params 中的 "*" 匹配正則表達式 ".*"
   在 params 中的 "?" 匹配正則表達式 "."
   在 params 中的 "[...]" 匹配字符類
   在 params 中的 "[!...]" 匹配字符類的補集。
   在 params 中的 "[...a-z...]" 匹配 a 到 z。

   執行命令并帶有按如下規則構造的參數列表:
       如果 param 不包含 "*"，"["，或 "?"，則按原樣使用它
       如果包含，則在當前目錄中找到匹配這個 param 的所有文件，
	   排序并使用它們。

   按需要為命令名字添加 "/bin" 或 "/usr/bin" 前綴。
*/
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include <unistd.h>
#include <dirent.h>

#define	QUOTE 0x80	/* 引用標志位 */

#define	STRSIZ _POSIX_ARG_MAX
extern char *arg0;	/* 調用 sh 的全路徑 */
static char ab[STRSIZ];	/* 生成的字符串的存儲空間 */
static char *string;	
static char *ava[STRSIZ/2];	/* 生成的參數列表 */
static char **av;
static int  ncoll;

int glob(int argc, char *argv[]);
static int gexec(char *afile, char **aarg);
static void expand(char *as);
static void sort(char **oav);
static void toolong(void);
static int match(char *s, char *p);
static int amatch(char *as, char *ap);
static int umatch(char *s, char *p);
static int compare(char *as1, char *as2);
static char* cat(char *as1, char *as2);

int glob(int argc, char *argv[])
{
	char *cp;
	int r;

	string = ab;
	av = &ava[1]; /* 有意留出一個空位 */

	if (argc < 2) {
		write(STDERR_FILENO, "Arg count\n", 10);
		exit (1);
	}
	argv++;
	*av++ = *argv; /* 指向第一個參數，它是要執行的文件的名字 */
	while (--argc >= 2) 
		expand(*++argv);  /* 展開余下的所有的參數 */

	if ((r = gexec(ava[1], &ava[1])))
		return r;
	cp = cat("/usr/bin/", ava[1]);
	if ((r = gexec(cp+4, &ava[1])))
		return r;
	if ((r = gexec(cp, &ava[1])))
		return r;
	write(STDERR_FILENO, "Command not found.\n", 19);
	return 127;
}

void expand(char *as)
{
	register char *s, *cs;
	struct dirent * dirp; 
	DIR	*dp;
	char **oav;

	ncoll = 0;
	s = cs = as;
	/* 把 cs 定位到第一個通配符 */
	while (*cs!='*' && *cs!='?' && *cs!='[') {
		if (*cs++ == 0) { /* 沒有找到通配符 */
			*av++ = cat(s, "");
			return; 
		}
	}
	for (;;) {
		if (cs==s) { /* 在通配符之前沒有'/' */
			dp = opendir(".");
			s = "";
			break;
		}
		if (*--cs == '/') {
			*cs = 0; /* 把參數分開為目錄和文件名兩個字符串 */
			dp = opendir((s==cs)? "/": s);
			*cs++ = QUOTE;	/* 做標記，在后面的 cat 操作中恢復成斜杠 */
			break;
		}
	}
	if (dp == NULL) {
		write(STDERR_FILENO, "No directory\n", 13);
		exit (1);
	}
	oav = av;
	while ((dirp = readdir(dp)) != NULL) {
		if (match(dirp->d_name, cs)) {
			*av++ = cat(s, dirp->d_name);
			ncoll++;
		}
	}
	if (!ncoll) /* 沒有匹配 */
		*av++ = cat(s, cs); /* 保持參數為原狀 */
	else /* 排序匹配的文件名字 */
		sort(oav);
	closedir(dp);

}
/* 排序 */
void sort(char **oav)
{
	register char **p1, **p2, *c;

	p1 = oav;
	while (++p1 < av) {
		c = *p1;
		p2 = p1;
		while (--p2 >= oav && compare(*p2, c) > 0)
			*(p2+1) = *p2;
		*(p2+1) = c;
	}
}
/* 執行一個命令 */
int gexec(char *afile, char **aarg)
{
	register char *file, **arg;

	arg = aarg;
	file = afile;
	execv(file, arg);

	if (errno == EACCES) {
		write(STDERR_FILENO, "Permission denied\n", 18);
		return 126;
	}
	if (errno==ENOEXEC) { /* 不是二進制可執行文件 */
		arg[0] = file;
		*--arg = arg0;
		execv(*arg, arg); /* 作為命令文件執行 */
	}
	if (errno==E2BIG) {/* 在參數列表太長的時候退出 */
		toolong();
		return E2BIG;
	}
	return 0;
}
/* 打印錯誤消息并退出 */
void toolong(void)
{
	write(2, "Arg list too long\n", 18);
}
/*匹配判斷例程 */
int match(char *s, char *p)
{
	if (*s=='.' && *p!='.') /* 對 . 開頭的文件的處理 */
		return 0;
	return amatch(s, p);
}
/* 對字符的匹配 */
int amatch(char *as, char *ap)
{
	register char *s, *p;
	register int scc;
	int c, cc, ok, lc;
	int neg = 0;

	s = as;
	p = ap;
	if ((scc = *s++) != 0) /* 文件名未終結 */
		/* 傳遞給 glob 的參數中的字符可能設置了引用位，
		這些字符在 shell 命令行中位于" "或' ' 中 */
		if ((scc &= ~QUOTE) == 0) /* 如果 scc 清除了引用位之后是 0 */
			scc = QUOTE; /* 重新把它設置為 QUOTE */
	switch (c = *p++) {

	case '[':	/* 處理字符類 */
		if (*p=='!') { /* 下個字符是 ! */
			neg = 1;
			p++;
		}
		ok = 0;
		lc = INT_MAX;
		while ((cc = *p++) != 0) {
			if (cc==']') {
				if ((ok && !neg) || (!ok && neg)) 
					return amatch(s, p); /* 如果匹配，繼續比較后面的字符 */
				else
					return 0;
			} else if (cc=='-') {
				if (lc<=scc && scc<=(c = *p++)) /* 在范圍內 */
					ok++;
			} else
				if (scc == (lc=cc))
					ok++;
		}
		return 0;

	default:
		if (c!=scc)
			return 0;

	case '?':
		if (scc)
			return amatch(s, p);
		return 0;

	case '*':
		return umatch(--s, p);

	case '\0':
		return !scc;
	}
}
/* 對閉包的匹配 */
int umatch(char *s, char *p)
{
	if(*p==0) /* 模式以 * 結束 */
		return 1;
	while(*s) /* 文件名中有字符匹配模式中 * 后面的字符 */
		if (amatch(s++,p))
			return 1;
	return 0;
}
/* 比較兩個字符串 */
int compare(char *as1, char *as2)
{
	register char *s1, *s2;

	s1 = as1;
	s2 = as2;
	while (*s1++ ==  *s2)
		if (*s2++ == 0)
			return 0;
	return (*--s1 - *s2);
}
/* 聯接兩個字符串到 string 指向的數組中并返回它，
 * 副作用是 string 指針右移，指向的數組空間減小 */
char* cat(char *as1, char *as2)
{
	register char *s1, *s2;
	register int c;

	s2 = string;
	s1 = as1;
	while ((c = *s1++) != 0) {
		if (s2 > &ab[STRSIZ])
			toolong();
		c &= ~QUOTE; /* 清除引用位 */
		if (c==0) { /* 原先是路徑分隔符 */
			*s2++ = '/'; 
			break;
		}
		*s2++ = c;
	}

	s1 = as2;
	do {
		if (s2 > &ab[STRSIZ])
			toolong();
		*s2++ = c = *s1++;
	} while (c);

	s1 = string;
	string = s2;
	return s1;
}