From f8d924b76a3dfbaaa9e92dacbc4992a7ab6dc8f2 Mon Sep 17 00:00:00 2001 From: ksg Date: Sat, 27 Aug 2016 19:33:34 -0700 Subject: [PATCH] Lexer WIP --- src/apc/lexer.c | 225 +++++++++++++++++++++++++++++---- src/apc/main.c | 8 +- style/snippets/pointer_array.c | 11 ++ 3 files changed, 214 insertions(+), 30 deletions(-) create mode 100644 style/snippets/pointer_array.c diff --git a/src/apc/lexer.c b/src/apc/lexer.c index 0d408b9..47d2c35 100644 --- a/src/apc/lexer.c +++ b/src/apc/lexer.c @@ -5,44 +5,202 @@ \author Jordan Lavatai \date Aug 2016 ----------------------------------------------------------------------------*/ -//stdc +/* Standard */ #include #include #include -//posix +/* Posix */ #include #include -//bison -#include "fileparser.tab.h" -#define TOKEN_BUF_SIZE 1024 -#define DIRP_STACK_SIZE 512 +#include +/* Local */ +#include "parser.tab.h" +#define TOKEN_BUF_SIZE 1024 +#define ENTITY_BUF_SIZE 512 +#define SCANDIR_ERROR -1 int lexer_init(void); int lexer(void); +extern //main.c +const char* cargs['Z']; + +static inline +int scan(void); +static inline +int qcomp(const void*, const void*); + +/* 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 S(S)#S +#ifndef DL_DEPTHMAX +#define DL_DEPTHMAX 64 +#endif +#ifndef DL_CHILDMAX +#define DL_CHILDMAX DL_DEPTHMAX //square tree +#endif +#define DL_STACK (directory_list_stack) +#define DL_STACKP (dls) +#define DL_STACKSIZE (DL_DEPTHMAX + 1) //+1 because push increments early +#define DL_LEN (DL_STACKP - DL_STACK) +#define DL_CURDEPTH (DL_LEN) +#define DL_CD_STACK ((*DL_STACKP).child_entity_stack) +#define DL_CD_STACKP ((*DL_STACKP).cds) +#define DL_CD_STACKSIZE (DL_DEPTHMAX) //square tree +#define DL_CD_LEN (DL_CD_STACKP - DL_CD_STACK) +#define ERR_CHILD "Fatal: Maximum of " S(MAX_CHILD) \ + " child directories exceeded for directory %s at depth %i\n" \ + ,DL_STACK[DL_DEPTH()].label,DL_DEPTH() +#define ERR_DEPTH "Fatal: Maximum directory depth of " S(DL_DEPTHMAX) \ + " exceeded during directory scan\n" +#define DL_INIT() (DL_STACKP = DL_STACK) +#define DL_CD_INIT() (DL_CD_STACKP = DL_CD_STACK) +#define DL_POP() ((DIR*)(*DL_STACKP--)) +#define DL_CD_POP() (*--DL_CD_STACKP) +#define DL_PUSH(D) (*(DIR**)(++DL_STACKP) = DIRP) +#define DL_CD_PUSH(E) (*DL_CD_STACKP++ = E) +#define DL_SAFEPUSH(D) \ + do { \ + if (DL_DEPTH() >= DL_DEPTHMAX) \ + { fprintf(stderr, ERR_DEPTH); \ + exit(EXIT_FAILURE); \ + } \ + if ((*(DIR**)(++DL_STACKP) = D) == NULL) \ + { perror("DL_SAFEPUSH"); \ + exit(EXIT_FAILURE); \ + } \ + } while(0) +#define DL_CD_POPULATE() \ + do { \ + DL_CD_INIT(); \ + while ((*DL_CD_STACKP = readdir(*DL_STACKP)) != NULL) \ + { switch((*DL_CD_STACKP)->d_type) \ + { case DT_REG: \ + case DT_DIR: \ + DL_CD_STACKP++; \ + break; \ + default: \ + } \ + } \ + qsort(DL_CD_STACKP, DL_CD_LEN, sizeof *DL_CD_STACKP, qcomp); \ + } while (0) + +static +struct dirlist +{ DIR* dirp; + struct dirent** child_directory_stack[DL_CD_STACKSIZE],*** cds; + const char* label; +} directory_list_stack[DL_STACKSIZE],* dls; static -int lexer_scan(void); +/* Directory Entity Stack + Simple stack for keeping track of dirents still being processed at the + current depth. +*/ +#define CE_STACK (child_entity_stack) +#define CE_STACKP (ces) +#define CE_STACKSIZE 1024 static -int token_buf[TOKEN_BUF_SIZE], *tbp, *tbx; +struct dirent** child_entity_stack[CE_STACKSIZE],*** ces; +#define CE_INIT() (CE_STACKP = CE_STACK) +#define CE_POP() (*--CE_STACK) +#define CE_PUSH(E) (*CE_STACK++ = E) + +/* Token Stack + This is a FIFO stack whose pointers are a union of either a pointer to an + integer, or a pointer to two integers (a struct tok). This way, integers may + be added or removed from the stack either singularly (IPUSH/IPOP), or as a + full token of two integers (PUSH/POP). + An alignment error will occur if IPOP or IPUSH are used a non-even number of + times in a sequence! +*/ +#define TK_STACK (token_stack) +#define TK_STACKP (tks.t) +#define TK_STACKPI (tks.i) +#define TK_STACKX (tkx.t) +#define TK_STACKXI (tkx.i) +#ifndef TK_STACKSIZE +#define TK_STACKSIZE 1024 +#endif +#define TK_EMPTY (TK_STACKP == TK_STACKX) +#define TK_INIT() (TK_STACKP = TK_STACKX = TK_STACK) +#define TK_POP() (*TK_STACKP++) +#define TK_IPOP() (*TK_STACKPI++); +#define TK_PUSH(TOK,LVAL) (*TKSTACKX++ = (struct tok){(LVAL),(TOK)}) +#define TK_IPUSH(I) (*TKSTACKXI++ = (I)) +static +struct tok +{ int lval; + int tok; +} token_stack[TK_STACKSIZE]; static -DIR* dirp_stack[DIRP_STACK_SIZE], *dsp; - -/* Initialize pointers */ -int -lexer_init() -{ tbp = tbx = token_buf; - dsp = dirp_stack; - return 0; +union tokp +{ int* i; + struct tok* t; +} tks, tkx; + + +/* Initializer + The initializer returns boolean true if opendir contains an error. +*/ +int lexer_init() +#define ERR_UF "Fatal: Unknown file [%s] encountered in directory %s", \ + DL_CD_STACK[i]->d_name, DL_STACK[DL_DEPTH] +{ int i = 0; + TK_INIT(); + DL_INIT(); + DL_STACK[0].label = cargs['r'] ? cargs['r'] : "./"; + if ((DL_STACK[0].dirp = opendir(DL_STACK[0].label)) == NULL) + return -1; + errno = 0; + while ((DL_CD_STACK[i] = readdir(DL_STACK[0].dirp)) != NULL) + switch(DL_CD_STACK[i]->d_type) + { + default: + fprintf(stderr, "Fatal: Unkown File %s\n", DL_CD_STACK[i]->d_name); + } + return (errno); +} + +/* Lexer + If the token buffer is empty, 'lexer' will initialize the token buffer and + call 'lexer_scandir'. If #SCANDIR_ERROR is returned, an error is printed + before sending a null return to bison. If 0 tokens are generated, the error + printing is skipped. In all other cases, 'yylval' is set, and the token's + integer representation is returned. +*/ +int lexer() +{ if (TOK_BUF_EMPTY) + { TOK_BUF_INIT(); + switch (lexer_scan) + { case SCANDIR_ERROR: + perror("lexer_scan"); + case 0: + yylval = 0; + return 0; + default: + } + } + yylval = TOK_BUF_IPOP(); + return TOK_BUF_IPOP(); } -/* Returns a token identifier and sets yylval */ -int -lexer() -{ if (lexer_scan() == 0) - return 0; - yylval = *tbp++; - return *tbp++; + +static inline +int lexer_scan() +{ static DIR* } /* Scanner @@ -56,10 +214,12 @@ lexer() static int lexer_scan() { static struct dirent* entity; - static struct dirent* files[MAX_ENTITIES]; - static struct dirent* dirs = files + MAX_ENTITIES - 1; + static struct dirent* files[MAX_ENTITIES] = {0}; static int num_files = 0; - static int num_dirs = 0; +#define NO_FILES (num_files == 0) + + if (NO_FILES) + //sort out files and directories, grow directories from bottom up while ((entity = readdir(dirp)) != NULL) @@ -88,5 +248,18 @@ int lexer_scan() //process files //recurse into directories + return tbx - tbp; +} +/* Quicksort comparison function + sort each dirent encountered first by its file type (regular files first) + and then by their alphabetical ordering. +*/ +static +int qcompar +( const void* a, + const void* b + ) +{ } + diff --git a/src/apc/main.c b/src/apc/main.c index 95e9ea9..a22975d 100644 --- a/src/apc/main.c +++ b/src/apc/main.c @@ -19,10 +19,10 @@ #include //exit #include //getopt -int main(int, char*[]); - const char* cargs['Z'] = {0}; +int main(int, char*[]); + extern //bison void yyparse(void); extern //lexer.c @@ -35,9 +35,9 @@ int main ( int argc, char* argv[] ) -#define S(S)#S +#define S(S)#S //stringifier #define MAXSTR 255 -#define MAXERR "-%c allows at most " S(MAXSTR) " input characters", opt +#define MAXERR "-%c allows at most " S(MAXSTR) " input characters\n", opt #define USAGE "Usage: %s [-r root]\n", argv[0] #define DONE -1 { int opt; diff --git a/style/snippets/pointer_array.c b/style/snippets/pointer_array.c new file mode 100644 index 0000000..913f3b6 --- /dev/null +++ b/style/snippets/pointer_array.c @@ -0,0 +1,11 @@ +/* Inverse 2d array population */ +#include +int main(void); +int main() +{ int** ipp,* ip,* ipa[16], ia[16<<4], i; + for (ipp = ipa, i = 0; ((*ipp++ = ip = ia + (i++ << 4)) - ia < 16 << 4);) + { while ((*ip++ = ip - ia) < (ipp - ipa) << 4) + printf("%i\n",*(ip-1)); + } +} + -- 2.18.0