+/*!@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 <stdio.h> //print
+#include <errno.h> //errno
+/* Posix */
+#include <err.h> //warnx
+#include <stdlib.h> //exit
+#include <unistd.h> //chdir
+#include <dirent.h> //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();
+}
+
projects / henge / webcc.git / commitdiff