src/apc/scanner.c

   1 /*!@file
   2   \brief   APC Directory Scanner
   3   \details This hand-written parser/scanner traverses a directory tree and
   4            tokenizes elements of the structure which correspond to APC grammar.
   5            The parser is implemented as a 2D stack which populates a list of
   6            child directories at each depth, handling only the leaf nodes
   7            (regular files) of the directory open at the current depth to
   8            conserve memory and speed up traversal.
   9            The scanner works with the lexer to lexically analyze text, and
  10            assumes the existence of an external 'lex' function
  11   \author  Jordan Lavatai
  12   \date    Aug 2016
  13   ----------------------------------------------------------------------------*/
  14 /* Standard */
  15 #include <stdio.h>  //print
  16 #include <errno.h>  //errno
  17 /* Posix */
  18 #include <err.h>    //warnx
  19 #include <stdlib.h> //exit
  20 #include <unistd.h> //chdir
  21 #include <dirent.h> //opendir
  22
  23 #include "parser.tab.h"
  24 /* Public */
  25 int  scanner_init(void);
  26 void scanner_quit(void);
  27 int  scanner(void);
  28 /* Private */
  29 #ifndef DL_STACKSIZE
  30 #define DL_STACKSIZE     64
  31 #endif
  32 #ifndef DL_CD_STACKSIZE
  33 #define DL_CD_STACKSIZE  DL_STACKSIZE //square tree
  34 #endif
  35 extern //lexer.c
  36 int  lexer_lex(const char*);
  37 extern //lexer.c
  38 void lexer_pushtok(int, int);
  39 static
  40 int  dredge_current_depth(void);
  41 extern //lexer.c
  42 struct dirent* lexer_direntpa[], **lexer_direntpp;
  43 extern //SRC_DIR/bin/tools/apc.c
  44 const char* cargs['Z'];
  45
  46 struct dirlist
  47 { DIR*           dirp;
  48   struct dirent* child_directory_stack[DL_CD_STACKSIZE],** cds;
  49 } directory_list_stack[DL_STACKSIZE + 1],* dls; //+1 for the root dir
  50
  51 /* Directory Listing Stack
  52    FILO Stack for keeping an open DIR* at each directory depth for treewalk.
  53    This stack is depth-safe, checking its depth during push operations, but not
  54    during pop operations, to ensure the thread doesn't open too many files at
  55    once (512 in c runtime), or traverse too far through symbolic links.
  56    A directory listing includes a DIR* and all DIR-typed entity in the directory
  57    as recognized by dirent, populated externally (and optionally).
  58    This stack behaves abnormally by incrementing its PUSH operation prior to
  59    evaluation, and the POP operations after evaluation.  This behavior allows
  60    the 'DL_CURDEPTH' operation to map to the current element in the 'dl_stack'
  61    array, and it is always treated as the "current depth". This also allows us
  62    to init the root directory to 'directory_list_stack'[0] and pop it in a safe
  63    and explicit manner.
  64 */
  65 #define DL_STACK        (directory_list_stack)
  66 #define DL_STACKP       (dls)
  67 #define DL_CD_STACK     ((*DL_STACKP).child_directory_stack)
  68 #define DL_CD_STACKP    ((*DL_STACKP).cds)
  69 #define DL_CURDIR()     ((*DL_STACKP).dirp)
  70 #define DL_LEN()        (DL_STACKP - DL_STACK)
  71 #define DL_CD_LEN()     (DL_CD_STACKP - DL_CD_STACK)
  72 #define DL_INIT()       (DL_STACKP = DL_STACK)
  73 #define DL_CD_INIT()    (DL_CD_STACKP = DL_CD_STACK)
  74 #define DL_POP()        ((*DL_STACKP--).dirp)
  75 #define DL_CD_POP()     (*--DL_CD_STACKP)
  76 #define DL_PUSH(D)      ((*++DL_STACKP).dirp = D)
  77 #define DL_CD_PUSH(E)   (*DL_CD_STACKP++ = E)
  78
  79
  80 /* Initializer
  81    Initializer expects a function pointer to its lexical analysis function.
  82    Sets up stack pointers and returns boolean true if 'opendir' encounters an
  83    error, or if dredge_current_depth returns boolean true.
  84 */
  85 int scanner_init
  86 #define CWDSTR  "./"
  87 #define ROOTDIR (cargs['d'] ? cargs['d'] : CWDSTR)
  88 ()
  89 { DL_INIT();
  90   DL_STACK[0].dirp = opendir(ROOTDIR);
  91   printf("Root dir %s\n",ROOTDIR);
  92   return !chdir(ROOTDIR) && (DL_STACK[0].dirp == NULL || dredge_current_depth() == -1);
  93 }
  94
  95 /* Quit */
  96 void scanner_quit
  97 ()
  98 { if (DL_CURDIR())
  99     closedir(DL_CURDIR());
 100 }
 101
 102 /* Scanner
 103    The main driver of the scanner will advance the current treewalk state and
 104    tokenize tree-based push/pop operations.  It will call 'lexer_lex' to
 105    tokenize directory names prior to making a push operation. safe checking for
 106    all returns from the filesystem handler will exit on serious system errors.
 107
 108    after pushing a new directory to the directory list, the scanner will dredge
 109    the directory and alphabetically sort all file entries into the lexer's file
 110    array, while placing all subdirectory entries in the current depth's child
 111    directory stack to be scanned later.
 112
 113    Returns the number of elements added to the lexer's file array, or -1 on
 114    error
 115 */
 116 int scanner
 117 #define $($)#$ //stringifier
 118 #define ERR_CHILD  "Fatal: Maximum of " $(DL_CD_STACKSIZE)      \
 119   " child directories exceeded for directory at depth %i\n"     \
 120   ,DL_LEN()
 121 #define ERR_DEPTH  "Fatal: Maximum directory depth of " $(DL_STACKSIZE) \
 122   " exceeded during directory scan\n"
 123 #define ERR_DL     "Fatal: Directory List Stack Corruption %x\n", DL_LEN()
 124 #define TOK_CLOPEN  0x55, 1 //TODO
 125 #define TOK_CLCLOSE 0x56, 1 //TODO
 126 ()
 127 { struct dirent* direntp;
 128   struct DIR* DIRp;
 129  parse:
 130   if (DL_CD_LEN() >= DL_CD_STACKSIZE)//fail if maxchildren exceeded
 131     { fprintf(stderr, ERR_CHILD);
 132       goto fail;
 133     }
 134   if (DL_CD_LEN() > 0)               //There are entities to process
 135     { if ((direntp = DL_CD_POP()) == NULL)//If the dirent is null, the library
 136         goto libfail;                     //function in dirent has failed
 137       printf("Lexdir %s\n",direntp->d_name);
 138       lexer_lex(direntp->d_name);         //lex the directory name
 139       if (DL_LEN() >= DL_STACKSIZE)       //fail if maxdepth exceeded
 140         { fprintf(stderr, ERR_DEPTH);
 141           goto fail;
 142         }
 143       if (chdir(direntp->d_name))         //move into the new directory
 144         goto libfail;
 145       DL_PUSH(opendir(CWDSTR));
 146       if (DL_CURDIR() == NULL)            //open the cwd
 147         goto libfail;
 148       lexer_pushtok(TOK_CLOPEN);          //Push "Open Directory" token
 149       return dredge_current_depth();      //Filter and sort the current depth
 150     }
 151   else if (DL_LEN() >= 0)            //Any dirs left? (Including root)
 152     { if (closedir(DL_POP()))             //close the directory we just left
 153         goto libfail;
 154       if (DL_LEN() == -1)                 //If we just popped root,
 155         return 0;                         //we're done
 156       lexer_pushtok(TOK_CLCLOSE);         //Else push "Close Directory" token,
 157       if (!chdir(".."))                   //move up a directory and
 158         goto parse;                       //start over
 159     }
 160   fprintf(stderr, ERR_DL);
 161  libfail:
 162   perror("parsedir");
 163  fail:
 164   exit(EXIT_FAILURE);
 165 }
 166
 167 /* Directory Entity Sort and Filter (Dredge)
 168    This filter removes all unhandled file types, and places any 'DT_DIR' type
 169    files in the current Directory List's directory stack.  Upon finishing,
 170    the 'CE_STACK' is sorted alphabetically, and the current 'DL_CD_STACK' is
 171    populated.  Prints warnings for unhandled files.
 172
 173    Returns -1 if 'readdir' encounters an error, otherwise returns the number of
 174    directory entries sent to the external 'lexer_direntpa' array.
 175 */
 176 typedef
 177 int (*qcomp)(const void*, const void*);
 178 static inline
 179 int dredge_current_depth
 180 #define READDIR_ERROR (-1)
 181 #define READDIR_DONE  (0)
 182 #define DPS_LEN()     (lexer_direntpp - lexer_direntpa)
 183 #define DPS_PUSH(E)   (*lexer_direntpp++ = E)
 184 ()
 185 { struct dirent**  direntpp = lexer_direntpa;
 186   DIR*             cwd      = DL_CURDIR();
 187   struct dirent*   direntp;
 188   DL_CD_INIT();
 189  scan_next:
 190   if ((direntp = readdir(cwd)) != NULL)
 191     { switch (direntp->d_type)
 192         { case DT_REG:
 193             DPS_PUSH(direntp);
 194             goto scan_next;
 195           case DT_DIR:
 196             if (*(direntp->d_name) == '.') //skip hidden files and relative dirs
 197               goto scan_next;
 198             DL_CD_PUSH(direntp);
 199             goto scan_next;
 200           case DT_UNKNOWN:
 201             warnx("unknown file %s: ignoring", direntp->d_name);
 202           default:
 203             goto scan_next;
 204         }
 205     }
 206   if (errno)
 207     return -1;
 208   qsort(lexer_direntpa, DPS_LEN(), sizeof direntp, (qcomp)alphasort);
 209   return DPS_LEN();
 210 }
 211