git.sesse.net Git - pgn-extract/blob - fenmatcher.c

   1 /*
   2  *  Program: pgn-extract: a Portable Game Notation (PGN) extractor.
   3  *  Copyright (C) 1994-2014 David Barnes
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 1, or (at your option)
   7  *  any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with this program; if not, write to the Free Software
  16  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  *  David Barnes may be contacted as D.J.Barnes@kent.ac.uk
  19  *  http://www.cs.kent.ac.uk/people/staff/djb/
  20  *
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include "bool.h"
  26 #include "mymalloc.h"
  27 #include "defs.h"
  28 #include "typedef.h"
  29 #include "apply.h"
  30 #include "fenmatcher.h"
  31
  32 /* Character on an encoded board representing an empty square. */
  33 #define EMPTY_SQUARE '_'
  34 /* Pattern meta characters. */
  35 #define NON_EMPTY_SQUARE '!'
  36 #define ANY_SQUARE_STATE '?'
  37 #define ZERO_OR_MORE_OF_ANYTHING '*'
  38 #define ANY_WHITE_PIECE 'A'
  39 #define ANY_BLACK_PIECE 'a'
  40
  41 /* Symbols for closures. */
  42 #define CCL_START '['
  43 #define CCL_END ']'
  44 #define NCCL '^'
  45
  46 /**
  47  * Based on original pattern matching code by Rob Pike.
  48  * Taken from:
  49  *     http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
  50  * and ideas from Kernighan and Plauger's "Software Tools".
  51  */
  52
  53 static Boolean matchhere(const char *regexp, const char *text);
  54 static Boolean matchstar(const char *regexp, const char *text);
  55 static Boolean matchccl(const char *regexp, const char *text);
  56 static Boolean matchnccl(const char *regexp, const char *text);
  57 static Boolean matchone(char regchar, char textchar);
  58 static char *convert_board_to_text(const Board *board);
  59
  60 /* The list of FEN-based patterns to match. */
  61 static StringList *fen_patterns = NULL;
  62
  63 void
  64 add_fen_pattern(const char *fen_pattern)
  65 {
  66     /* Check the pattern a reasonable syntax. */
  67     /* Count the number of rank dividers. */
  68     int dividors = 0;
  69     /* Count the number of symbols in each rank - must be
  70      * at least one.
  71      */
  72     int rankSymbols = 0;
  73     Boolean ok = TRUE;
  74     const char *p = fen_pattern;
  75     Boolean in_closure = FALSE;
  76     while(*p != '\0' && ok) {
  77         if(*p == '/') {
  78             dividors++;
  79             if(rankSymbols == 0) {
  80                 /* Nothing on the previous rank. */
  81                 ok = FALSE;
  82             }
  83             rankSymbols = 0;
  84         }
  85         else if(*p == CCL_START) {
  86             if(!in_closure) {
  87                 in_closure = TRUE;
  88             }
  89             else {
  90                 ok = FALSE;
  91                 fprintf(GlobalState.logfile,
  92                         "Nested closures not allowed: %s\n",
  93                         fen_pattern);
  94             }
  95         }
  96         else if(*p == CCL_END) {
  97             if(in_closure) {
  98                 in_closure = FALSE;
  99             }
 100             else {
 101                 ok = FALSE;
 102                 fprintf(GlobalState.logfile,
 103                         "Missing %c to match %c: %s\n",
 104                         CCL_START, CCL_END,
 105                         fen_pattern);
 106             }
 107         }
 108         else if(*p == NCCL) {
 109             if(!in_closure) {
 110                 ok = FALSE;
 111                 fprintf(GlobalState.logfile,
 112                         "%c not allowed outside %c...%c: %s\n",
 113                         NCCL,
 114                         CCL_START, CCL_END,
 115                         fen_pattern);
 116             }
 117         }
 118         else {
 119             rankSymbols++;
 120         }
 121         p++;
 122     }
 123     if(dividors != 7) {
 124         ok = FALSE;
 125     }
 126     else if(rankSymbols == 0) {
 127         ok = FALSE;
 128     }
 129     if(ok) {
 130         const char *pattern = copy_string(fen_pattern);
 131         fen_patterns = save_string_list_item(fen_patterns, pattern);
 132     }
 133     else {
 134         fprintf(GlobalState.logfile, "FEN Pattern: %s badly formed.\n",
 135                 fen_pattern);
 136     }
 137 }
 138
 139     /*
 140      * Try to match the board against one of the FEN patterns.
 141      * Return the matching pattern, if there is one, otherwise NULL.
 142      */
 143 const char *
 144 matchBoard(const Board *board)
 145 {
 146     Boolean match = FALSE;
 147     const char *pattern = NULL;
 148     if(fen_patterns != NULL) {
 149         const char *text = convert_board_to_text(board);
 150
 151         StringList *item = fen_patterns;
 152
 153         while(item != NULL && !match) {
 154             if(0) printf("Try %s against %s\n", item->str, text);
 155             pattern = item->str;
 156             if(matchhere(pattern, text)) {
 157                 if(0) fprintf(stdout, "%s matches\n%s\n", pattern, text);
 158                 match = TRUE;
 159             }
 160             else {
 161                 item = item->next;
 162             }
 163         }
 164         (void) free((void *) text);
 165         if(match) {
 166             return pattern;
 167         }
 168         else {
 169             return (const char *) NULL;
 170         }
 171     }
 172     else {
 173         return (const char *) NULL;
 174     }
 175 }
 176
 177 /**
 178  * matchhere: search for regexp at beginning of text
 179  */
 180 static Boolean
 181 matchhere(const char *regexp, const char *text)
 182 {
 183     if (regexp[0] == '\0' && text[0] == '\0') {
 184         return TRUE;
 185     }
 186     if (regexp[0] == ZERO_OR_MORE_OF_ANYTHING) {
 187         return matchstar(regexp+1, text);
 188     }
 189     if (*text !='\0') {
 190         switch(*regexp) {
 191             case ANY_SQUARE_STATE:
 192                 return matchhere(regexp+1, text+1);
 193                 break;
 194             case NON_EMPTY_SQUARE:
 195             case ANY_WHITE_PIECE:
 196             case ANY_BLACK_PIECE:
 197                 if(matchone(*regexp, *text)) {
 198                     return matchhere(regexp+1, text+1);
 199                 }
 200                 break;
 201             case CCL_START:
 202                 /* Closure */
 203                 if(regexp[1] == NCCL) {
 204                     return matchnccl(regexp + 2, text);
 205                 }
 206                 else {
 207                     return matchccl(regexp + 1, text);
 208                 }
 209                 break;
 210             case '1': case '2': case '3': case '4':
 211             case '5': case '6': case '7': case '8':
 212                 {
 213                     /* The number of empty squares required. */
 214                     int empty = regexp[0] - '0';
 215                     Boolean matches = TRUE;
 216                     /* The number matched. */
 217                     int match_count = 0;
 218                     while(matches && match_count < empty) {
 219                         if(text[match_count] == EMPTY_SQUARE) {
 220                             match_count++;
 221                         }
 222                         else {
 223                             matches = FALSE;
 224                         }
 225                     }
 226                     if(matches) {
 227                         return matchhere(regexp+1, text + match_count);
 228                     }
 229                 }
 230                 break;
 231             default:
 232                 if(*regexp == *text) {
 233                     return matchhere(regexp+1, text+1);
 234                 }
 235                 break;
 236         }
 237     }
 238     /* No match. */
 239     return FALSE;
 240 }
 241
 242 /**
 243  * matchstar: leftmost longest search on a single rank.
 244  */
 245 static Boolean
 246 matchstar(const char *regexp, const char *text)
 247 {
 248     const char *t;
 249
 250     /* Find the end of this rank. */
 251     for (t = text; *t != '\0' && *t != '/'; t++) {
 252             ;
 253     }
 254     /* Try from the longest match to the shortest until success. */
 255     do {
 256         /* * matches zero or more */
 257         if (matchhere(regexp, t)) {
 258             return TRUE;
 259         }
 260     } while (t-- > text);
 261     return FALSE;
 262 }
 263
 264     /*
 265      * Return TRUE if regchar matches textchar, FALSE otherwise.
 266      */
 267 static Boolean
 268 matchone(char regchar, char textchar)
 269 {
 270     if(regchar == textchar) {
 271         return TRUE;
 272     }
 273     else {
 274         switch(regchar) {
 275             case NON_EMPTY_SQUARE:
 276                 return textchar != EMPTY_SQUARE;
 277             case ANY_WHITE_PIECE:
 278                 /* Match any white piece. */
 279                 switch(textchar) {
 280                     case 'K':
 281                     case 'Q':
 282                     case 'R':
 283                     case 'N':
 284                     case 'B':
 285                     case 'P':
 286                         return TRUE;
 287                     default:
 288                         return FALSE;
 289                 }
 290             case ANY_BLACK_PIECE:
 291                 /* Match any black piece. */
 292                 switch(textchar) {
 293                     case 'k':
 294                     case 'q':
 295                     case 'r':
 296                     case 'n':
 297                     case 'b':
 298                     case 'p':
 299                         return TRUE;
 300                     default:
 301                         return FALSE;
 302                 }
 303             case ANY_SQUARE_STATE:
 304                 return TRUE;
 305             default:
 306                 return FALSE;
 307         }
 308     }
 309 }
 310
 311     /*
 312      * Match any of the character closure.
 313      */
 314 static Boolean
 315 matchccl(const char *regexp, const char *text)
 316 {
 317     while(*regexp != CCL_END &&
 318           !matchone(*regexp,*text) && *regexp != '\0') {
 319         regexp++;
 320     }
 321     if(matchone(*regexp, *text)) {
 322         do {
 323             regexp++;
 324         }
 325         while(*regexp != CCL_END && *regexp != '\0');
 326         return matchhere(regexp + 1, text + 1);
 327     }
 328     else {
 329         return FALSE;
 330     }
 331 }
 332
 333     /*
 334      * Match any of the characters not in the closure.
 335      */
 336 static Boolean
 337 matchnccl(const char *regexp, const char *text)
 338 {
 339     while(*regexp != CCL_END &&
 340           !matchone(*regexp,*text) && *regexp != '\0') {
 341         regexp++;
 342     }
 343     if(*regexp == CCL_END) {
 344         return matchhere(regexp + 1, text + 1);
 345     }
 346     else {
 347         return FALSE;
 348     }
 349 }
 350
 351
 352     /* Build a basic EPD string from the given board. */
 353 static char *
 354 convert_board_to_text(const Board *board)
 355 {   Rank rank;
 356     int ix = 0;
 357     /* Allow space for a full board and '/' separators in between. */
 358     char *text = (char *) MallocOrDie(8 * 8 + 8);
 359     for(rank = LASTRANK; rank >= FIRSTRANK; rank--){
 360         Col col;
 361         for(col = FIRSTCOL; col <= LASTCOL; col++){
 362             int coloured_piece = board->board[RankConvert(rank)]
 363                                              [ColConvert(col)];
 364             if(coloured_piece != EMPTY){
 365                 text[ix] = coloured_piece_to_SAN_letter(coloured_piece);
 366             }
 367             else{
 368                 text[ix] = EMPTY_SQUARE;
 369             }
 370             ix++;
 371         }
 372         if(rank != FIRSTRANK){
 373             text[ix] = '/';
 374             ix++;
 375         }
 376     }
 377     text[ix]  = '\0';
 378     return text;
 379 }