xref: /dports/editors/e93/e93/xgui/glob.c

// File name globbing
// Copyright (C) 2000 Core Technologies.

// This file is part of e93.
//
// e93 is free software; you can redistribute it and/or modify
// it under the terms of the e93 LICENSE AGREEMENT.
//
// e93 is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// e93 LICENSE AGREEMENT for more details.
//
// You should have received a copy of the e93 LICENSE AGREEMENT
// along with e93; see the file "LICENSE.TXT".

#include	"includes.h"

enum
{
	NO_USER=0,
	MATCH_FAILED,
	PATH_TOO_LONG,
	UNBALANCED_SQUARE_BRACKET,
	DANGLING_QUOTE
};

static const char *errorDescriptions[]=
{
	"Failed to locate user",
	"Nothing matched",
	"Path grew too large",
	"Unbalanced [ or [^",
	"Incomplete \\ expression"
};

typedef struct
{
	bool
		dontGlobLast,	// if true, the last element of the pattern will not be checked for existence if it contains no meta characters
		passNoMeta;		// if true, the entire pattern will not be checked for existence if it contains no meta characters
	bool
		hadMeta;		// tells if we have seen a meta character in the path so far
	UINT32
		numPaths;		// count of total paths so far
	char
		**paths;		// list of paths matching pattern
} GLOB_DATA;

static void ExtractFileName(char *fullPath,char *filePart)
// given fullPath which is considered to be a complete path and file name,
// truncate fullPath to just the path part, and copy the file part
// to filePart
// NOTE: filePart must be at least as large an array as fullPath
{
	int
		length;

	length=strlen(fullPath);
	while(length>=0&&fullPath[length]!=PATH_SEP)
	{
		length--;
	}
	if(length>0)
	{
		strcpy(filePart,&(fullPath[length+1]));
		fullPath[length]='\0';
	}
	else
	{
		if(fullPath[0]==PATH_SEP)			// / at 0 is special
		{
			strcpy(filePart,&(fullPath[1]));
			fullPath[1]='\0';
		}
		else
		{
			strcpy(filePart,fullPath);
			fullPath[0]='\0';
		}
	}
}

void SplitPathAndFile(char *fullPath,char *pathPart,char *filePart)
// split fullPath into pathPart, and filePart
// NOTE: pathPart and filePart must be at least MAXPATHLEN+1
// bytes long
// if fullPath is longer than MAXPATHLEN, parts will get truncated when copied
// NOTE: if fullPath is not a valid path, return the whole thing as filePart,
// and the current directory as the pathPart
{
	struct stat
		statOut;
	char
		tempPath[MAXPATHLEN+1];

	if(realpath2(fullPath,pathPart))
	{
		if((stat(pathPart,&statOut)!=-1)&&S_ISDIR(statOut.st_mode))		// point to a file, or a directory?
		{
			filePart[0]='\0';					// points to a directory, so no file part, this is done
		}
		else
		{
			ExtractFileName(pathPart,filePart);	// pointed to a file, so separate them
		}
	}
	else
	{
		strncpy(tempPath,fullPath,MAXPATHLEN);	// copy this to separate it
		tempPath[MAXPATHLEN]='\0';
		ExtractFileName(tempPath,filePart);		// separate the pieces
		if(!realpath2(tempPath,pathPart))		// try to get the path to the unknown file part
		{
			if(!realpath2(".",pathPart))		// get the current directory
			{
				pathPart[0]='\0';				// just return empty string
			}
			strncpy(filePart,fullPath,MAXPATHLEN);
			filePart[MAXPATHLEN]='\0';
		}
	}
}

void ConcatPathAndFile(const char *path,const char *file,char *result)
// merge path and file to form a fully qualified file name
// result must be at least MAXPATHLEN+1 characters long
// NOTE: if path and file combine into a string longer than MAXPATHLEN,
// the combined string will be truncated
// NOTE ALSO, if file specifies a complete Path (starts with a PATH_SEP) then
// it alone is added to result
{
	int
		pathLength,
		fileLength;

	if(file[0]!=PATH_SEP)
	{
		pathLength=strlen(path);
		if(pathLength>MAXPATHLEN)
		{
			pathLength=MAXPATHLEN;
		}
		strncpy(result,path,pathLength);
		if(pathLength&&(path[pathLength-1]!=PATH_SEP)&&(pathLength<MAXPATHLEN))
		{
			result[pathLength++]=PATH_SEP;
		}
	}
	else
	{
		pathLength=0;
	}
	fileLength=strlen(file);
	if(pathLength+fileLength>MAXPATHLEN)
	{
		fileLength=(MAXPATHLEN-pathLength);
	}
	strncpy(&(result[pathLength]),file,fileLength);
	result[pathLength+fileLength]='\0';
}

// string list functions

void FreeStringList(char **list)
// free a list of strings created by calling NewStringList
{
	UINT32
		index;

	index=0;
	while(list&&list[index])
	{
		MDisposePtr(list[index]);
		index++;
	}
	MDisposePtr(list);
}

static int CompareStrings(const void *i,const void *j)
// compare two elements of the list
{
	char
		*elementA,
		*elementB;

	elementA=*((char **)i);
	elementB=*((char **)j);

	return(strcmp(elementA,elementB));
}

void SortStringList(char **list,UINT32 numElements)
// run through any elements of list, and sort them
// by calling qsort
{
	if(list)
	{
		qsort((char *)list,numElements,sizeof(char **),CompareStrings);
	}
}

bool ReplaceStringInList(const char *string,char **list,UINT32 element)
// place string into list at the given position, freeing
// any string that was there
// NOTE: element must be in range
// if there is a problem leave the entry untouched, SetError, and return false
{
	char
		*newElement;

	if((newElement=(char *)MNewPtr(strlen(string)+1)))
	{
		strcpy(newElement,string);
		MDisposePtr(list[element]);
		list[element]=newElement;
		return(true);
	}
	return(false);
}

bool AddStringToList(const char *string,char ***list,UINT32 *numElements)
// add string to list
// at any point, list can be deleted by calling FreeStringList
// if there is a problem, do not add the element, SetError, and return false
{
	char
		**newList;
	UINT32
		newLength;

	newLength=sizeof(char *)*((*numElements)+2);
	if((newList=(char **)MResizePtr(*list,newLength)))
	{
		(*list)=newList;
		if(((*list)[*numElements]=(char *)MNewPtr(strlen(string)+1)))
		{
			strcpy((*list)[(*numElements)++],string);
			(*list)[*numElements]=NULL;									// keep the list terminated with a NULL
			return(true);
		}
	}
	return(false);
}

char **NewStringList()
// Create an empty string list
// if there is a problem, SetError, return NULL
{
	char
		**list;

	if((list=(char **)MNewPtr(sizeof(char *))))
	{
		list[0]=NULL;
	}
	return(list);
}

// tilde expansion routines

static bool ExpandTildes(const char *pattern,char *newPattern,UINT32 newPatternLength)
// expand tilde sequences in pattern, write output into newPattern
// if there is a problem, SetError, and return false
{
	bool
		done,
		fail;
	char
		character;
	UINT32
		inIndex,
		outIndex;
	char
		*home;
	struct passwd
		*passwordEntry;
	UINT32
		length;

	fail=false;
	if(pattern[0]=='~')		// see if a tilde exists at the start of pattern
	{
		inIndex=1;			// skip the tilde
		outIndex=0;
		done=false;
		while(!done&&!fail&&(character=pattern[inIndex])&&outIndex<(newPatternLength-1))
		{
			switch(character)
			{
				case PATH_SEP:
					inIndex++;
					done=true;
					break;
				case '\\':
					inIndex++;
					if(!(newPattern[outIndex++]=pattern[inIndex]))
					{
						SetError(errorDescriptions[DANGLING_QUOTE]);
						fail=true;
					}
					break;
				default:
					newPattern[outIndex++]=character;
					inIndex++;
					break;
			}
		}
		if(!fail)
		{
			newPattern[outIndex]='\0';		// terminate the user name string
			home=NULL;						// no home found yet
			if(outIndex)					// name was specified
			{
				if((passwordEntry=getpwnam(newPattern)))
				{
					home=passwordEntry->pw_dir;
				}
			}
			else
			{
				if(!(home=getenv("HOME")))	// try to find environment variable
				{
					if((passwordEntry=getpwuid(getuid())))	// if no environment, try to get from password database
					{
						home=passwordEntry->pw_dir;
					}
				}
			}
			if(home)
			{
				strncpy(newPattern,home,newPatternLength-1);
				newPattern[newPatternLength-1]='\0';
				length=strlen(newPattern);
				if(length&&length<newPatternLength-1)
				{
					if(newPattern[length-1]!=PATH_SEP)	// add path separator if needed
					{
						newPattern[length++]=PATH_SEP;
						newPattern[length]='\0';
					}
				}
				strncat(newPattern,&pattern[inIndex],newPatternLength-length);
			}
			else
			{
				SetError(errorDescriptions[NO_USER]);	// user not there
				fail=true;
			}
		}
	}
	else
	{
		strncpy(newPattern,pattern,newPatternLength-1);
		newPattern[newPatternLength-1]='\0';
	}
	return(!fail);
}

// wildcard expansion routines

static bool MatchRange(char character,const char *pattern,UINT32 *patternIndex,bool *haveMatch)
// a range is starting in pattern, so attempt to match character
// against it
{
	bool
		fail,
		done,
		isNot;
	char
		testChar,
		lastChar;

	isNot=done=fail=false;
	if(pattern[*patternIndex]=='^')					// check for not flag
	{
		isNot=true;
		(*patternIndex)++;
	}
	lastChar='\0';									// start with bottom of range at 0
	*haveMatch=false;
	while(!done&&!fail&&(testChar=pattern[(*patternIndex)++]))
	{
		switch(testChar)
		{
			case '\\':
				if((testChar=pattern[(*patternIndex)++]))	// get next character to test
				{
					if(character==testChar)			// test it literally
					{
						*haveMatch=true;
					}
				}
				else
				{
					SetError(errorDescriptions[DANGLING_QUOTE]);
					fail=true;						// got \ at the end of the pattern
				}
				break;
			case '-':
				if((testChar=pattern[(*patternIndex)++]))		// get the next character for the range (if there is one)
				{
					switch(testChar)
					{
						case '\\':
							if((testChar=pattern[(*patternIndex)++]))
							{
								if(character>=lastChar&&character<=testChar)
								{
									*haveMatch=true;
								}
							}
							else
							{
								SetError(errorDescriptions[DANGLING_QUOTE]);
								fail=true;						// got \ at the end of the pattern
							}
							break;
						case ']':
							if(character>=lastChar)				// empty range at end, so take as infinite end
							{
								*haveMatch=true;
							}
							done=true;
							break;
						default:
							if(character>=lastChar&&character<=testChar)
							{
								*haveMatch=true;
							}
							break;
					}
				}
				else
				{
					SetError(errorDescriptions[UNBALANCED_SQUARE_BRACKET]);
					fail=true;
				}
				break;
			case ']':
				done=true;							// scanning is done (empty lists are allowed)
				break;
			default:								// otherwise it is normal, and just gets tested
				if(character==testChar)
				{
					*haveMatch=true;
				}
				break;
		}
		lastChar=testChar;							// remember this for next time around the loop
	}
	if(!done&&!fail)								// ran out of things to scan
	{
		SetError(errorDescriptions[UNBALANCED_SQUARE_BRACKET]);
		fail=true;
	}
	if(!fail)
	{
		if(isNot)
		{
			*haveMatch=!*haveMatch;
		}
	}
	return(!fail);
}

static bool MatchName(const char *name,const char *pattern,UINT32 *patternIndex,bool *haveMatch)
// match name against pattern
// pattern points to the start of a pattern terminated with a '\0', or a PATH_SEP
// update patternIndex to point to the character that stopped the match
// if a match occurs, return true if have match
// if there is a problem SetError, and return false
{
	UINT32
		nameIndex;
	UINT32
		startPatternIndex;
	bool
		fail,
		done,
		matching;
	char
		character;

	fail=*haveMatch=done=false;
	matching=true;
	nameIndex=0;
	while(!done&&matching)
	{
		switch(pattern[*patternIndex])
		{
			case '\0':				// ran out of characters of the pattern
			case PATH_SEP:
				matching=(name[nameIndex]=='\0');
				done=true;
				break;
			case '*':
				(*patternIndex)++;	// move past the *
				matching=false;
				do
				{
					startPatternIndex=*patternIndex;
					fail=!MatchName(&name[nameIndex],pattern,&startPatternIndex,&matching);
				}
				while(name[nameIndex++]&&!fail&&!matching);			// recurse trying to make a match
				if(matching)
				{
					*patternIndex=startPatternIndex;
					done=true;
				}
				break;
			case '?':
				(*patternIndex)++;
				matching=(name[nameIndex++]!='\0');
				break;
			case '[':
				(*patternIndex)++;
				if((character=name[nameIndex++]))
				{
					fail=!MatchRange(character,pattern,patternIndex,&matching);
				}
				else
				{
					matching=false;
				}
				break;
			case '\\':
				(*patternIndex)++;
				if((character=pattern[(*patternIndex)++]))
				{
					matching=(name[nameIndex++]==character);
				}
				else
				{
					SetError(errorDescriptions[DANGLING_QUOTE]);
					fail=true;
				}
				break;
			default:
				matching=(name[nameIndex++]==pattern[(*patternIndex)++]);
				break;
		}
	}
	if(!fail)
	{
		*haveMatch=matching;
	}
	return(!fail);
}

// prototype this because it is mutually recursive with MoveFurther
static bool GlobAgainstDirectory(const char *pattern,UINT32 patternIndex,char *pathBuffer,UINT32 pathIndex,GLOB_DATA *data);

static bool MoveFurther(const char *pattern,UINT32 patternIndex,char *pathBuffer,UINT32 pathIndex,GLOB_DATA *data)
// this attempts to add to pathBuffer by reading from pattern at patternIndex
// pattern data is added to pathBuffer so that all data containing no meta characters is copied
// up to the first PATH_SEP before data that does contain meta characters
// if there is a problem, SetError, and return false
{
	bool
		fail;
	bool
		done;
	UINT32
		lastPatternIndex,
		lastPathIndex;
	bool
		nextSpecial;
	bool
		hadMeta;					// tells if locally, we have seen any meta characters yet

	fail=done=nextSpecial=hadMeta=false;
	lastPatternIndex=patternIndex;
	lastPathIndex=pathIndex;
	while(!done&&pathIndex<MAXPATHLEN)
	{
		// copy all of pattern that contains no meta characters until the next PATH_SEP into pathBuffer
		pathBuffer[pathIndex]=pattern[patternIndex];
		switch(pattern[patternIndex])
		{
			case '\0':				// ran out of characters of the pattern, so this is not path information
				if((!hadMeta&&data->dontGlobLast)||(!data->hadMeta&&data->passNoMeta))		// if no meta characters, then this IS the path (assuming we dont glob the last one)
				{
					pathBuffer[pathIndex]='\0';	// terminate the current path
					fail=!AddStringToList(pathBuffer,&data->paths,&data->numPaths);	// add this to the list
				}
				done=true;
				break;
			case '*':							// meta character (this means we stop here)
			case '?':
			case '[':
				if(nextSpecial)
				{
					patternIndex++;
					pathIndex++;
					nextSpecial=false;
				}
				else
				{
					hadMeta=true;				// remember locally that there were meta characters
					data->hadMeta=true;			// remember it globally as well
					done=true;
				}
				break;
			case PATH_SEP:
				patternIndex++;
				pathIndex++;
				lastPatternIndex=patternIndex;	// remember these
				lastPathIndex=pathIndex;
				nextSpecial=false;
				break;
			case '\\':
				if(nextSpecial)
				{
					patternIndex++;
					pathIndex++;
					nextSpecial=false;
				}
				else
				{
					nextSpecial=true;
					patternIndex++;				// skip the \, but do not move forward in path
				}
				break;
			default:
				patternIndex++;
				pathIndex++;
				nextSpecial=false;
				break;
		}
	}
	if(done)									// we got something
	{
		if(!((!hadMeta&&data->dontGlobLast)||(!data->hadMeta&&data->passNoMeta)))	// if we aren't passing this verbatim, then glob against it
		{
			patternIndex=lastPatternIndex;		// move back
			pathIndex=lastPathIndex;
			pathBuffer[pathIndex]='\0';			// terminate the current path
			fail=!GlobAgainstDirectory(pattern,patternIndex,pathBuffer,pathIndex,data);	// expand the pattern at the end of the current path
		}
	}
	else										// path was about to overflow output
	{
		SetError(errorDescriptions[PATH_TOO_LONG]);
		fail=true;
	}
	return(!fail);

}

static bool GlobAgainstDirectory(const char *pattern,UINT32 patternIndex,char *pathBuffer,UINT32 pathIndex,GLOB_DATA *data)
// try pattern against all files at pathBuffer, adding each that matches completely, and calling
// move further on each one
// if there is some sort of problem, SetError, and return false
{
	DIR
		*directory;
	struct dirent
		*entry;
	bool
		fail;
	const char
		*path;
	UINT32
		length;
	UINT32
		newIndex;
	bool
		haveMatch;

	fail=false;
	if(pathBuffer[0])
	{
		path=pathBuffer;						// point at the passed path if one given
	}
	else
	{
		path="./";								// if passed path is empty, it means current directory
	}
	if((directory=opendir(path)))				// if it does not open, assume it is because path did not point to something valid
	{
		while(!fail&&(entry=readdir(directory)))
		{
			newIndex=patternIndex;
			if(entry->d_name[0]!='.'||pattern[patternIndex]=='.')			// the first . must be matched exactly
			{
				if(MatchName(entry->d_name,pattern,&newIndex,&haveMatch))
				{
					if(haveMatch)				// was there a match?
					{
						length=strlen(entry->d_name);
						if(pathIndex+length<MAXPATHLEN)	// append to path (if there's room)
						{
							strcpy(&(pathBuffer[pathIndex]),entry->d_name);
							if(pattern[newIndex])		// see if there's more pattern left
							{
								fail=!MoveFurther(pattern,newIndex,pathBuffer,pathIndex+length,data);
							}
							else
							{
								fail=!AddStringToList(pathBuffer,&data->paths,&data->numPaths);
							}
						}
						else
						{
							SetError(errorDescriptions[PATH_TOO_LONG]);
							fail=true;
						}
					}
				}
				else
				{
					fail=true;
				}
			}
		}
		closedir(directory);
	}
	return(!fail);
}

char **Glob(const char *path,const char *pattern,bool dontGlobLast,bool passNoMeta,UINT32 *numElements)
// glob pattern into an array of paths, and return it
// if there is a problem, SetError, and return NULL
// path is the initial path to begin globbing at if pattern
// does not specify an absolute path
// NOTE: the returned paths must be deleted by a call to
// FreeStringList
// if dontGlobLast is true, the last element of pattern (if it contains
// no meta characters) will not be checked against its directory,
// but instead will be taken to exist, and will be placed into the output
// this is useful when trying to save to a globbed path, and the last element
// of the path is the name of a file which does not necessarily exist yet.
// if passNoMeta is true, any pattern that contains no wild card
// characters will be placed into the output without being checked
{
	GLOB_DATA
		data;
	char
		newPattern[MAXPATHLEN+1];					// tilde expand the pattern into here
	char
		pathBuffer[MAXPATHLEN+1];					// this is the place to build the output path
	UINT32
		length;

	*numElements=0;									// no elements yet
	if((data.paths=NewStringList()))
	{
		data.numPaths=0;							// no paths so far
		data.dontGlobLast=dontGlobLast;				// set up flags that tell how to glob
		data.passNoMeta=passNoMeta;
		data.hadMeta=false;							// no meta characters seen so far
		if(ExpandTildes(pattern,&newPattern[0],MAXPATHLEN+1))	// expand tilde sequences in pattern, write output into newPattern
		{
			if(newPattern[0]==PATH_SEP)
			{
				pathBuffer[0]='\0';					// pattern is absolute, so ignore given path
			}
			else
			{
				strncpy(pathBuffer,path,MAXPATHLEN);	// use the passed path as a prefix to the glob
			}
			length=strlen(pathBuffer);
			if(length&&length<MAXPATHLEN)			// if we have something, check to see if it needs a PATH_SEP
			{
				if(pathBuffer[length-1]!=PATH_SEP)	// add separator to end of path
				{
					pathBuffer[length++]=PATH_SEP;
					pathBuffer[length]='\0';
				}
			}
			if(MoveFurther(&newPattern[0],0,pathBuffer,length,&data))
			{
				if(data.numPaths)
				{
					SortStringList(data.paths,data.numPaths);
					*numElements=data.numPaths;
					return(data.paths);
				}
				else
				{
					SetError(errorDescriptions[MATCH_FAILED]);
				}
			}
		}
		FreeStringList(data.paths);
	}
	return(NULL);
}

char **GlobAll(const char *path,UINT32 *numElements)
// return a sorted list of all of the directories/files at the end of path
// path is not expanded in any way.
// NOTE: the list will contain ONLY the last component of the path
// if there is a problem, SetError, and return NULL
// NOTE: the returned list must be later deleted by a call to
// FreeStringList
{
	char
		**files;
	DIR
		*directory;
	struct dirent
		*entry;
	bool
		fail;

	fail=false;
	*numElements=0;								// no paths so far
	if((files=NewStringList()))
	{
		if((directory=opendir(path)))			// if it does not open, assume it is because path did not point to something valid, and return NULL
		{
			while(!fail&&(entry=readdir(directory)))
			{
				fail=!AddStringToList(entry->d_name,&files,numElements);
			}
			closedir(directory);
			if(!fail)
			{
				SortStringList(files,*numElements);
				return(files);
			}
		}
		else
		{
			SetStdCLibError();
		}
		FreeStringList(files);
	}
	*numElements=0;
	return(NULL);
}