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 /* Libs */
  23 #include <png.h>
  24 /* Internal */
  25 #include "parser.tab.h"
  26 /* Public */
  27 int   scanner_init(void);
  28 void  scanner_quit(void);
  29 int   scanner(void);
  30 int   scanner_scanpixels(int*,int);
  31 /* Private */
  32 #ifndef DL_STACKSIZE
  33 #define DL_STACKSIZE     64
  34 #endif
  35 #ifndef DL_CD_STACKSIZE
  36 #define DL_CD_STACKSIZE  DL_STACKSIZE //square tree
  37 #endif
  38 extern //lexer.c
  39 int  lexer_lex(const char*);
  40 extern //lexer.c
  41 void lexer_pushtok(int, int);
  42 static
  43 int  dredge_current_depth(void);
  44 extern //lexer.c
  45 struct dirent* lexer_direntpa[], **lexer_direntpp;
  46 extern //SRC_DIR/bin/tools/apc.c
  47 const char* cargs['Z'];
  48
  49 struct dirlist
  50 { DIR*           dirp;
  51   struct dirent* child_directory_stack[DL_CD_STACKSIZE],** cds;
  52 } directory_list_stack[DL_STACKSIZE + 1],* dls; //+1 for the root dir
  53
  54 /* Directory Listing Stack
  55    FILO Stack for keeping an open DIR* at each directory depth for treewalk.
  56    This stack is depth-safe, checking its depth during push operations, but not
  57    during pop operations, to ensure the thread doesn't open too many files at
  58    once (512 in c runtime), or traverse too far through symbolic links.
  59    A directory listing includes a DIR* and all DIR-typed entity in the directory
  60    as recognized by dirent, populated externally (and optionally).
  61    This stack behaves abnormally by incrementing its PUSH operation prior to
  62    evaluation, and the POP operations after evaluation.  This behavior allows
  63    the 'DL_CURDEPTH' operation to map to the current element in the 'dl_stack'
  64    array, and it is always treated as the "current depth". This also allows us
  65    to init the root directory to 'directory_list_stack'[0] and pop it in a safe
  66    and explicit manner.
  67 */
  68 #define DL_STACK        (directory_list_stack)
  69 #define DL_STACKP       (dls)
  70 #define DL_CD_STACK     ((*DL_STACKP).child_directory_stack)
  71 #define DL_CD_STACKP    ((*DL_STACKP).cds)
  72 #define DL_CURDIR()     ((*DL_STACKP).dirp)
  73 #define DL_LEN()        (DL_STACKP - DL_STACK)
  74 #define DL_CD_LEN()     (DL_CD_STACKP - DL_CD_STACK)
  75 #define DL_INIT()       (DL_STACKP = DL_STACK)
  76 #define DL_CD_INIT()    (DL_CD_STACKP = DL_CD_STACK)
  77 #define DL_POP()        ((*DL_STACKP--).dirp)
  78 #define DL_CD_POP()     (*--DL_CD_STACKP)
  79 #define DL_PUSH(D)      ((*++DL_STACKP).dirp = D)
  80 #define DL_CD_PUSH(E)   (*DL_CD_STACKP++ = E)
  81
  82
  83 /* Initializer
  84    Initializer expects a function pointer to its lexical analysis function.
  85    Sets up stack pointers and returns boolean true if 'opendir' encounters an
  86    error, or if dredge_current_depth returns boolean true.
  87 */
  88 int scanner_init
  89 #define CWDSTR  "./"
  90 #define ROOTDIR (cargs['d'] ? cargs['d'] : CWDSTR)
  91 ()
  92 { DL_INIT();
  93   DL_STACK[0].dirp = opendir(ROOTDIR);
  94   printf("Root dir %s\n",ROOTDIR);
  95   return !chdir(ROOTDIR) && (DL_STACK[0].dirp == NULL || dredge_current_depth() == -1);
  96 }
  97
  98 /* Quit */
  99 void scanner_quit
 100 ()
 101 { if (DL_CURDIR())
 102     closedir(DL_CURDIR());
 103 }
 104
 105 /* Scanner
 106    The main driver of the scanner will advance the current treewalk state and
 107    tokenize tree-based push/pop operations.  It will call 'lexer_lex' to
 108    tokenize directory names prior to making a push operation. safe checking for
 109    all returns from the filesystem handler will exit on serious system errors.
 110
 111    after pushing a new directory to the directory list, the scanner will dredge
 112    the directory and alphabetically sort all file entries into the lexer's file
 113    array, while placing all subdirectory entries in the current depth's child
 114    directory stack to be scanned later.
 115
 116    Returns the number of tokens generated on success, -1 on error.
 117 */
 118 int scanner
 119 #define $($)#$ //stringifier
 120 #define ERR_CHILD  "Fatal: Maximum of " $(DL_CD_STACKSIZE)      \
 121   " child directories exceeded for directory at depth %i\n"     \
 122   ,DL_LEN()
 123 #define ERR_DEPTH  "Fatal: Maximum directory depth of " $(DL_STACKSIZE) \
 124   " exceeded during directory scan\n"
 125 #define ERR_DL     "Fatal: Directory List Stack Corruption %x\n", DL_LEN()
 126 ()
 127 { struct dirent* direntp;
 128   struct DIR* DIRp;
 129   int ntok = 0;
 130  scan:
 131   if (DL_CD_LEN() >= DL_CD_STACKSIZE)//fail if maxchildren exceeded
 132     { fprintf(stderr, ERR_CHILD);
 133       goto fail;
 134     }
 135   if (DL_CD_LEN() > 0)               //There are entities to process
 136     { if ((direntp = DL_CD_POP()) == NULL)//If the dirent is null, the library
 137         goto libfail;                     //function in dirent has failed
 138       ntok += 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(CLOPEN, 0);           //Push "Open Directory" token
 149       ntok++;
 150       return dredge_current_depth();      //Filter and sort the current depth
 151     }
 152   else if (DL_LEN() >= 0)            //Any dirs left? (Including root)
 153     { if (closedir(DL_POP()))             //close the directory we just left
 154         goto libfail;
 155       if (DL_LEN() == -1)                 //If we just popped root,
 156         goto done;                        //we're done
 157       lexer_pushtok(CLCLOSE, 0);          //Else push "Close Directory" token,
 158       ntok++;
 159       if (!chdir(".."))                   //move up a directory and
 160         goto scan;                        //start over
 161     }
 162   fprintf(stderr, ERR_DL);
 163  libfail:
 164   perror("parsedir");
 165  fail:
 166   return -1;
 167  done:
 168   return ntok;
 169 }
 170
 171 /* Directory Entity Sort and Filter (Dredge)
 172    This filter removes all unhandled file types, and places any 'DT_DIR' type
 173    files in the current Directory List's directory stack.  Upon finishing,
 174    the 'CE_STACK' is sorted alphabetically, and the current 'DL_CD_STACK' is
 175    populated.  Prints warnings for unhandled files.
 176
 177    Returns -1 if 'readdir' encounters an error, otherwise returns the number of
 178    directory entries sent to the external 'lexer_direntpa' array.
 179 */
 180 typedef //so we can typecast dirent's 'alphasort()' to take const void*s
 181 int (*qcomp)(const void*, const void*);
 182 static inline
 183 int dredge_current_depth
 184 #define READDIR_ERROR (-1)
 185 #define READDIR_DONE  (0)
 186 #define DPS_LEN()     (lexer_direntpp - lexer_direntpa)
 187 #define DPS_PUSH(E)   (*lexer_direntpp++ = E)
 188 ()
 189 { struct dirent**  direntpp = lexer_direntpa;
 190   DIR*             cwd      = DL_CURDIR();
 191   struct dirent*   direntp;
 192   DL_CD_INIT();
 193  scan_next:
 194   if ((direntp = readdir(cwd)) != NULL)
 195     { switch (direntp->d_type)
 196         { case DT_REG:
 197             DPS_PUSH(direntp);
 198             goto scan_next;
 199           case DT_DIR:
 200             if (*(direntp->d_name) == '.') //skip hidden files and relative dirs
 201               goto scan_next;
 202             DL_CD_PUSH(direntp);
 203             goto scan_next;
 204           case DT_UNKNOWN:
 205             warnx("unknown file %s: ignoring", direntp->d_name);
 206           default:
 207             goto scan_next;
 208         }
 209     }
 210   if (errno)
 211     return -1;
 212   qsort(lexer_direntpa, DPS_LEN(), sizeof direntp, (qcomp)alphasort);
 213   return DPS_LEN();
 214 }
 215
 216
 217 /* Scan Pixels
 218    Scans up to 'len' pixels from the current file into 'buf'.
 219    Returns the number of pixels scanned from the file, or -1 on error.
 220 */
 221 int scanner_scanpixels
 222 ( int* buf,
 223   int x
 224 )
 225 { int pixels = 0;
 226   //Open the current file if not yet open
 227     //Identify file type
 228     //Verify file contents and header
 229   //Read pixels into buffer
 230   return pixels;
 231 }