X-Git-Url: https://www.kengrimes.com/gitweb/?p=henge%2Fwebcc.git;a=blobdiff_plain;f=src%2Fapc%2Fscanner.c;fp=src%2Fapc%2Fscanner.c;h=b039cdafa9aca16424705c5ebc2864c3fbd50d6d;hp=0000000000000000000000000000000000000000;hb=882513ad6569a640cb5c90b83e27e742ace71b63;hpb=f8d924b76a3dfbaaa9e92dacbc4992a7ab6dc8f2 diff --git a/src/apc/scanner.c b/src/apc/scanner.c new file mode 100644 index 0000000..b039cda --- /dev/null +++ b/src/apc/scanner.c @@ -0,0 +1,194 @@ +/*!@file + \brief APC Directory Scanner + \details This hand-written parser/scanner traverses a directory tree and + tokenizes elements of the structure which correspond to APC grammar. + The parser is implemented as a 2D stack which populates a list of + child directories at each depth, handling only the leaf nodes + (regular files) of the directory open at the current depth to + conserve memory and speed up traversal. + The scanner works with the lexer to lexically analyze text, and + assumes the existence of an external 'lex' function + \author Jordan Lavatai + \date Aug 2016 + ----------------------------------------------------------------------------*/ +/* Standard */ +#include //print +#include //errno +/* Posix */ +#include //warnx +#include //exit +#include //chdir +#include //opendir +/* Public */ +int scanner_init(); +int scanner(void); +/* Private */ +#ifndef DL_STACKSIZE +#define DL_STACKSIZE 64 +#endif +#ifndef DL_CD_STACKSIZE +#define DL_CD_STACKSIZE DL_STACKSIZE //square tree +#endif +extern //lexer.c +int lexer_lex(const char*); +extern //lexer.c +void lexer_pushtok(int, int); +static +int dredge_current_depth(void); +extern //lexer.c +struct dirent* lexer_direntpa[]; +extern //main.c +const char* cargs['Z']; + +struct dirlist +{ DIR* dirp; + struct dirent* child_directory_stack[DL_CD_STACKSIZE],** cds; +} directory_list_stack[DL_STACKSIZE + 1],* dls; //+1 for the root dir + +/* Directory Listing Stack + FILO Stack for keeping an open DIR* at each directory depth for treewalk. + This stack is depth-safe, checking its depth during push operations, but not + during pop operations, to ensure the thread doesn't open too many files at + once (512 in c runtime), or traverse too far through symbolic links. + A directory listing includes a DIR* and all DIR-typed entity in the directory + as recognized by dirent, populated externally (and optionally). + This stack behaves abnormally by incrementing its PUSH operation prior to + evaluation, and the POP operations after evaluation. This behavior allows + the 'DL_CURDEPTH' operation to map to the current element in the 'dl_stack' + array, and it is always treated as the "current depth". This also allows us + to init the root directory to 'directory_list_stack'[0] and pop it in a safe + and explicit manner. +*/ +#define DL_STACK (directory_list_stack) +#define DL_STACKP (dls) +#define DL_CD_STACK ((*DL_STACKP).child_directory_stack) +#define DL_CD_STACKP ((*DL_STACKP).cds) +#define DL_CURDIR() ((*DL_STACKP).dirp) +#define DL_LEN() (DL_STACKP - DL_STACK) +#define DL_CD_LEN() (DL_CD_STACKP - DL_CD_STACK) +#define DL_INIT() (DL_STACKP = DL_STACK) +#define DL_CD_INIT() (DL_CD_STACKP = DL_CD_STACK) +#define DL_POP() ((*DL_STACKP--).dirp) +#define DL_CD_POP() (*--DL_CD_STACKP) +#define DL_PUSH(D) ((*++DL_STACKP).dirp = D) +#define DL_CD_PUSH(E) (*DL_CD_STACKP++ = E) + + +/* Initializer + Initializer expects a function pointer to its lexical analysis function. + Sets up stack pointers and returns boolean true if 'opendir' encounters an + error, or if dredge_current_depth returns boolean true. +*/ +int scanner_init +#define CWDSTR "./" +#define ROOTDIR (cargs['r'] ? cargs['r'] : CWDSTR) +() +{ DL_INIT(); + DL_STACK[0].dirp = opendir(ROOTDIR); + return DL_STACK[0].dirp == NULL || dredge_current_depth() == 0; +} + +/* Scanner + The main driver of the scanner will advance the current treewalk state and + tokenize tree-based push/pop operations. It will call 'lexer_lex' to + tokenize directory names prior to making a push operation. safe checking for + all returns from the filesystem handler will exit on serious system errors. + + after pushing a new directory to the directory list, the scanner will dredge + the directory and alphabetically sort all file entries into the lexer's file + array, while placing all subdirectory entries in the current depth's child + directory stack to the scanned later. + + Returns the number of elements added to the lexer's file array. +*/ +int scanner +#define S(S)#S //stringifier +#define ERR_CHILD "Fatal: Maximum of " S(DL_CD_STACKSIZE) \ + " child directories exceeded for directory at depth %i\n" \ + ,DL_LEN() +#define ERR_DEPTH "Fatal: Maximum directory depth of " S(DL_STACKSIZE) \ + " exceeded during directory scan\n" +#define ERR_DL "Fatal: Directory List Stack Corruption %x\n", DL_LEN() +#define TOK_CLOPEN 0x55, 0 //TODO +#define TOK_CLCLOSE 0x56, 0 //TODO +() +{ struct dirent* direntp; + parse: + if (DL_CD_LEN() >= DL_CD_STACKSIZE)//fail if maxchildren exceeded + { fprintf(stderr, ERR_CHILD); + goto fail; + } + if (DL_CD_LEN() > 0) //There are entities to process at this depth + { if (direntp = DL_CD_POP()) //If the dirent is null, the library + goto libfail; //function in dirent has failed + lexer_lex(direntp->d_name); //lex the directory name + if (DL_LEN() >= DL_STACKSIZE) //fail if maxdepth exceeded + { fprintf(stderr, ERR_DEPTH); + goto fail; + } + if (chdir(direntp->d_name)) //move into the new directory + goto libfail; + if (DL_PUSH(opendir(CWDSTR))) //open the cwd + goto libfail; + lexer_pushtok(TOK_CLOPEN); //Push "Open Directory" token + return dredge_current_depth(); //Filter and sort the current depth + } + else if (DL_LEN() >= 0) //Any dirs left? (Including root) + { if (closedir(DL_POP())) //close the directory we just left + goto libfail; + lexer_pushtok(TOK_CLCLOSE); //Push "Close Directory" token + if (DL_LEN() == -1) //If we just popped root, we're done + return 0; + if (!chdir("..")) //Move up a directory and start over + goto parse; + } + fprintf(stderr, ERR_DL); + libfail: + perror("parsedir"); + fail: + exit(EXIT_FAILURE); +} + +/* Directory Entity Sort and Filter (Dredge) + This filter removes all unhandled file types, and places any 'DT_DIR' type + files in the current Directory List's directory stack. Upon finishing, + the 'CE_STACK' is sorted alphabetically, and the current 'DL_CD_STACK' is + populated. Prints warnings for unhandled files. + + Returns -1 if 'readdir' encounters an error, otherwise returns the number of + directory entries sent to the external 'lexer_direntpa' array. +*/ +typedef +int (*qcomp)(const void*, const void*); +static inline +int dredge_current_depth +#define READDIR_ERROR (-1) +#define READDIR_DONE (0) +#define DPS_LEN() (direntpp - lexer_direntpa) +#define DPS_PUSH(E) (*direntpp++ = E) +() +{ struct dirent** direntpp = lexer_direntpa; + DIR* cwd = DL_CURDIR(); + struct dirent* direntp; + DL_CD_INIT(); + scan_next: + if ((direntp = readdir(cwd)) != NULL) + { switch (direntp->d_type) + { case DT_REG: + DPS_PUSH(direntp); + goto scan_next; + case DT_DIR: + DL_CD_PUSH(direntp); + goto scan_next; + case DT_UNKNOWN: + warnx("unknown file %s: ignoring", direntp->d_name); + default: + goto scan_next; + } + } + if (errno) + return -1; + qsort(lexer_direntpa, DPS_LEN(), sizeof direntp, (qcomp)alphasort); + return DPS_LEN(); +} +