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)
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.
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.
18 * David Barnes may be contacted as D.J.Barnes@kent.ac.uk
19 * http://www.cs.kent.ac.uk/people/staff/djb/
30 #include "fenmatcher.h"
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'
41 /* Symbols for closures. */
47 * Based on original pattern matching code by Rob Pike.
49 * http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
50 * and ideas from Kernighan and Plauger's "Software Tools".
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);
60 /* The list of FEN-based patterns to match. */
61 static StringList *fen_patterns = NULL;
64 add_fen_pattern(const char *fen_pattern)
66 /* Check the pattern a reasonable syntax. */
67 /* Count the number of rank dividers. */
69 /* Count the number of symbols in each rank - must be
74 const char *p = fen_pattern;
75 Boolean in_closure = FALSE;
76 while(*p != '\0' && ok) {
79 if(rankSymbols == 0) {
80 /* Nothing on the previous rank. */
85 else if(*p == CCL_START) {
91 fprintf(GlobalState.logfile,
92 "Nested closures not allowed: %s\n",
96 else if(*p == CCL_END) {
102 fprintf(GlobalState.logfile,
103 "Missing %c to match %c: %s\n",
108 else if(*p == NCCL) {
111 fprintf(GlobalState.logfile,
112 "%c not allowed outside %c...%c: %s\n",
126 else if(rankSymbols == 0) {
130 const char *pattern = copy_string(fen_pattern);
131 fen_patterns = save_string_list_item(fen_patterns, pattern);
134 fprintf(GlobalState.logfile, "FEN Pattern: %s badly formed.\n",
140 * Try to match the board against one of the FEN patterns.
141 * Return the matching pattern, if there is one, otherwise NULL.
144 matchBoard(const Board *board)
146 Boolean match = FALSE;
147 const char *pattern = NULL;
148 if(fen_patterns != NULL) {
149 const char *text = convert_board_to_text(board);
151 StringList *item = fen_patterns;
153 while(item != NULL && !match) {
154 if(0) printf("Try %s against %s\n", item->str, text);
156 if(matchhere(pattern, text)) {
157 if(0) fprintf(stdout, "%s matches\n%s\n", pattern, text);
164 (void) free((void *) text);
169 return (const char *) NULL;
173 return (const char *) NULL;
178 * matchhere: search for regexp at beginning of text
181 matchhere(const char *regexp, const char *text)
183 if (regexp[0] == '\0' && text[0] == '\0') {
186 if (regexp[0] == ZERO_OR_MORE_OF_ANYTHING) {
187 return matchstar(regexp+1, text);
191 case ANY_SQUARE_STATE:
192 return matchhere(regexp+1, text+1);
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);
203 if(regexp[1] == NCCL) {
204 return matchnccl(regexp + 2, text);
207 return matchccl(regexp + 1, text);
210 case '1': case '2': case '3': case '4':
211 case '5': case '6': case '7': case '8':
213 /* The number of empty squares required. */
214 int empty = regexp[0] - '0';
215 Boolean matches = TRUE;
216 /* The number matched. */
218 while(matches && match_count < empty) {
219 if(text[match_count] == EMPTY_SQUARE) {
227 return matchhere(regexp+1, text + match_count);
232 if(*regexp == *text) {
233 return matchhere(regexp+1, text+1);
243 * matchstar: leftmost longest search on a single rank.
246 matchstar(const char *regexp, const char *text)
250 /* Find the end of this rank. */
251 for (t = text; *t != '\0' && *t != '/'; t++) {
254 /* Try from the longest match to the shortest until success. */
256 /* * matches zero or more */
257 if (matchhere(regexp, t)) {
260 } while (t-- > text);
265 * Return TRUE if regchar matches textchar, FALSE otherwise.
268 matchone(char regchar, char textchar)
270 if(regchar == textchar) {
275 case NON_EMPTY_SQUARE:
276 return textchar != EMPTY_SQUARE;
277 case ANY_WHITE_PIECE:
278 /* Match any white piece. */
290 case ANY_BLACK_PIECE:
291 /* Match any black piece. */
303 case ANY_SQUARE_STATE:
312 * Match any of the character closure.
315 matchccl(const char *regexp, const char *text)
317 while(*regexp != CCL_END &&
318 !matchone(*regexp,*text) && *regexp != '\0') {
321 if(matchone(*regexp, *text)) {
325 while(*regexp != CCL_END && *regexp != '\0');
326 return matchhere(regexp + 1, text + 1);
334 * Match any of the characters not in the closure.
337 matchnccl(const char *regexp, const char *text)
339 while(*regexp != CCL_END &&
340 !matchone(*regexp,*text) && *regexp != '\0') {
343 if(*regexp == CCL_END) {
344 return matchhere(regexp + 1, text + 1);
352 /* Build a basic EPD string from the given board. */
354 convert_board_to_text(const Board *board)
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--){
361 for(col = FIRSTCOL; col <= LASTCOL; col++){
362 int coloured_piece = board->board[RankConvert(rank)]
364 if(coloured_piece != EMPTY){
365 text[ix] = coloured_piece_to_SAN_letter(coloured_piece);
368 text[ix] = EMPTY_SQUARE;
372 if(rank != FIRSTRANK){