1 
2 /***************************************************************************
3  *                    __            __ _ ___________                       *
4  *                    \ \          / /| |____   ____|                      *
5  *                     \ \        / / | |    | |                           *
6  *                      \ \  /\  / /  | |    | |                           *
7  *                       \ \/  \/ /   | |    | |                           *
8  *                        \  /\  /    | |    | |                           *
9  *                         \/  \/     |_|    |_|                           *
10  *                                                                         *
11  *                           Wiimms ISO Tools                              *
12  *                         http://wit.wiimm.de/                            *
13  *                                                                         *
14  ***************************************************************************
15  *                                                                         *
16  *   This file is part of the WIT project.                                 *
17  *   Visit http://wit.wiimm.de/ for project details and sources.           *
18  *                                                                         *
19  *   Copyright (c) 2009-2013 by Dirk Clemens <wiimm@wiimm.de>              *
20  *                                                                         *
21  ***************************************************************************
22  *                                                                         *
23  *   This program is free software; you can redistribute it and/or modify  *
24  *   it under the terms of the GNU General Public License as published by  *
25  *   the Free Software Foundation; either version 2 of the License, or     *
26  *   (at your option) any later version.                                   *
27  *                                                                         *
28  *   This program is distributed in the hope that it will be useful,       *
29  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
30  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
31  *   GNU General Public License for more details.                          *
32  *                                                                         *
33  *   See file gpl-2.0.txt or http://www.gnu.org/licenses/gpl-2.0.txt       *
34  *                                                                         *
35  ***************************************************************************/
36 
37 #define _GNU_SOURCE 1
38 
39 #include <stdlib.h>
40 #include <string.h>
41 
42 #include "debug.h"
43 #include "lib-std.h"
44 #include "match-pattern.h"
45 
46 //
47 ///////////////////////////////////////////////////////////////////////////////
48 ///////////////                    variables                    ///////////////
49 ///////////////////////////////////////////////////////////////////////////////
50 
51 FilePattern_t file_pattern[PAT__N];
52 
53 //
54 ///////////////////////////////////////////////////////////////////////////////
55 ///////////////                    pattern db                   ///////////////
56 ///////////////////////////////////////////////////////////////////////////////
57 
InitializeFilePattern(FilePattern_t * pat)58 void InitializeFilePattern ( FilePattern_t * pat )
59 {
60     DASSERT(pat);
61     memset(pat,0,sizeof(*pat));
62     InitializeStringField(&pat->rules);
63     pat->match_all	= true;
64 }
65 
66 ///////////////////////////////////////////////////////////////////////////////
67 
ResetFilePattern(FilePattern_t * pat)68 void ResetFilePattern ( FilePattern_t * pat )
69 {
70     DASSERT(pat);
71     ResetStringField(&pat->rules);
72     InitializeFilePattern(pat);
73 }
74 
75 ///////////////////////////////////////////////////////////////////////////////
76 
InitializeAllFilePattern()77 void InitializeAllFilePattern()
78 {
79     memset(file_pattern,0,sizeof(file_pattern));
80 
81     FilePattern_t * pat = file_pattern;
82     FilePattern_t * end = pat + PAT__N;
83     for ( ; pat < end; pat++ )
84 	InitializeFilePattern(pat);
85 }
86 
87 ///////////////////////////////////////////////////////////////////////////////
88 
89 struct macro_tab_t
90 {
91     int len;
92     ccp name;
93     ccp expand;
94 };
95 
96 static const struct macro_tab_t macro_tab[] =
97 {
98     { 4, "base",	"+/*$" },
99     { 6, "nobase",	"-/*$" },
100     { 4, "disc",	"+/disc/" },
101     { 6, "nodisc",	"-/disc/" },
102     { 3, "sys",		"+/sys/" },
103     { 5, "nosys",	"-/sys/" },
104     { 5, "files",	"+/files/" },
105     { 7, "nofiles",	"-/files/" },
106     { 3, "wit",		"2+/h3.bin;1+/sys/fst.bin;+" },
107     { 3, "wwt",		"2+/h3.bin;1+/sys/fst.bin;+" },
108     { 7, "compose",	"+/cert.bin;3+/disc/;2+/*$;1+/sys/fst.bin;+" },
109     { 4, "neek",	"3+/setup.txt;2+/h3.bin;1+/disc/;+" },
110     { 5, "sneek",	"3+/setup.txt;2+/h3.bin;1+/disc/;+" },
111 
112     {0,0,0}
113 };
114 
115 ///////////////////////////////////////////////////////////////////////////////
116 
AddFilePattern(ccp arg,int pattern_index)117 int AddFilePattern ( ccp arg, int pattern_index )
118 {
119     TRACE("AddFilePattern(%s,%d)\n",arg,pattern_index);
120     DASSERT( pattern_index >= 0 );
121     DASSERT( pattern_index < PAT__N );
122 
123     if ( !arg || (u32)pattern_index >= PAT__N )
124 	return 0;
125 
126     FilePattern_t * pat = file_pattern + pattern_index;
127 
128     pat->is_active = true;
129 
130     while (*arg)
131     {
132 	ccp start = arg;
133 	bool ok = false;
134 	if ( *arg >= '1' && *arg <= '9' )
135 	{
136 	    while ( *arg >= '0' && *arg <= '9' )
137 		arg++;
138 	    if ( *arg == '+' || *arg == '-' )
139 		ok = true;
140 	    else
141 		arg = start;
142 	}
143 
144 	// hint: '=' is obsolete and compatible to ':'
145 
146 	if ( !ok && *arg != '+' && *arg != '-' && *arg != ':' && *arg != '=' )
147 	    return ERROR0(ERR_SYNTAX,
148 		"File pattern rule must begin with '+', '-' or ':' => %.20s\n",arg);
149 
150 	while ( *arg && *arg != ';' )
151 	    arg++;
152 
153 	if ( *start == ':' || *start == '=' )
154 	{
155 	    const int len = arg - ++start;
156 	    const struct macro_tab_t *tab;
157 	    for ( tab = macro_tab; tab->len; tab++ )
158 		if ( tab->len == len && !memcmp(start,tab->name,len) )
159 		{
160 		    AddFilePattern(tab->expand,pattern_index);
161 		    break;
162 		}
163 	    if (!tab->len)
164 	    {
165 		if (!strcmp(start,"negate"))
166 		{
167 		    pat->macro_negate = true;
168 		    pat->active_negate = pat->macro_negate != pat->user_negate;
169 		}
170 		else
171 		    return ERROR0(ERR_SYNTAX,
172 			"Macro '%.*s' not found: :%.20s\n",len,start,start);
173 	    }
174 	}
175 	else
176 	{
177 	    const size_t len = arg - start;
178 	    char * pattern = MALLOC(len+1);
179 	    memcpy(pattern,start,len);
180 	    pattern[len] = 0;
181 	    TRACE(" - ADD |%s|\n",pattern);
182 	    AppendStringField(&pat->rules,pattern,true);
183 	    pat->is_dirty = true;
184 	}
185 
186 	while ( *arg == ';' )
187 	    arg++;
188     }
189 
190     return 0;
191 }
192 
193 ///////////////////////////////////////////////////////////////////////////////
194 
ScanRule(ccp arg,enumPattern pattern_index)195 int ScanRule ( ccp arg, enumPattern pattern_index )
196 {
197     return AtFileHelper(arg,pattern_index,pattern_index,AddFilePattern) != 0;
198 }
199 
200 ///////////////////////////////////////////////////////////////////////////////
201 
GetDFilePattern(enumPattern pattern_index)202 FilePattern_t * GetDFilePattern ( enumPattern pattern_index )
203 {
204     DASSERT( (u32)pattern_index < PAT__N );
205     FilePattern_t * pat = file_pattern + pattern_index;
206     if (!pat->rules.used)
207 	pat = file_pattern + PAT_DEFAULT;
208     return pat;
209 }
210 
211 ///////////////////////////////////////////////////////////////////////////////
212 
GetDefaultFilePattern()213 FilePattern_t * GetDefaultFilePattern()
214 {
215     FilePattern_t * pat = file_pattern + PAT_FILES;
216     if (!pat->rules.used)
217 	pat = file_pattern + PAT_DEFAULT;
218     return pat;
219 }
220 
221 ///////////////////////////////////////////////////////////////////////////////
222 
DefineNegatePattern(FilePattern_t * pat,bool negate)223 void DefineNegatePattern ( FilePattern_t * pat, bool negate )
224 {
225     DASSERT(pat);
226     pat->user_negate = negate;
227     pat->active_negate = pat->macro_negate != pat->user_negate;
228 }
229 
230 ///////////////////////////////////////////////////////////////////////////////
231 
MoveParamPattern(FilePattern_t * dest_pat)232 void MoveParamPattern ( FilePattern_t * dest_pat )
233 {
234     DASSERT(dest_pat);
235     FilePattern_t * src = file_pattern + PAT_PARAM;
236     SetupFilePattern(src);
237     memcpy( dest_pat, src, sizeof(*dest_pat) );
238     InitializeFilePattern(src);
239 }
240 
241 ///////////////////////////////////////////////////////////////////////////////
242 
SetupFilePattern(FilePattern_t * pat)243 bool SetupFilePattern ( FilePattern_t * pat )
244 {
245     ASSERT(pat);
246     if (pat->is_dirty)
247     {
248 	pat->is_active	= true;
249 	pat->is_dirty	= false;
250 	pat->match_all	= false;
251 	pat->match_none	= false;
252 
253 	if (!pat->rules.used)
254 	    pat->match_all = true;
255 	else
256 	{
257 	    ccp first = *pat->rules.field;
258 	    ASSERT(first);
259 	    if (   !strcmp(first,"+")
260 		|| !strcmp(first,"+*")
261 		|| !strcmp(first,"+**") )
262 	    {
263 		pat->match_all = true;
264 	    }
265 	    else if (   !strcmp(first,"-")
266 		     || !strcmp(first,"-*")
267 		     || !strcmp(first,"-**") )
268 	    {
269 		pat->match_none = true;
270 	    }
271 	}
272      #ifdef DEBUG
273 	TRACE("FILE PATTERN: N=%u, all=%d, none=%d\n",
274 		pat->rules.used, pat->match_all, pat->match_none );
275 
276 	ccp * ptr = pat->rules.field;
277 	ccp * end = ptr +  pat->rules.used;
278 	while ( ptr < end )
279 	    TRACE("  |%s|\n",*ptr++);
280      #endif
281     }
282 
283     pat->active_negate = pat->macro_negate != pat->user_negate;
284     return pat->is_active && !pat->match_none;
285 }
286 
287 ///////////////////////////////////////////////////////////////////////////////
288 
MatchFilePattern(FilePattern_t * pat,ccp text,char path_sep)289 bool MatchFilePattern
290 (
291     FilePattern_t	* pat,		// filter rules
292     ccp			text,		// text to check
293     char		path_sep	// path separator character, standard is '/'
294 )
295 {
296     if (!pat)
297 	pat = GetDefaultFilePattern(); // use default pattern if not set
298     DASSERT(pat);
299 
300     if (pat->is_dirty)
301 	SetupFilePattern(pat);
302     if (pat->match_all)
303 	return !pat->active_negate;
304     if (pat->match_none)
305 	return pat->active_negate;
306 
307     bool default_result = !pat->active_negate;
308     int skip = 0;
309 
310     ccp * ptr = pat->rules.field;
311     ccp * end = ptr + pat->rules.used;
312     while ( ptr < end )
313     {
314 	char * pattern = (char*)(*ptr++); // non const because of strtoul()
315 	DASSERT(pattern);
316 	switch (*pattern++)
317 	{
318 	    case '-':
319 		if ( skip-- <= 0 && MatchPattern(pattern,text,path_sep) )
320 		    return pat->active_negate;
321 		default_result = !pat->active_negate;
322 		break;
323 
324 	    case '+':
325 		if ( skip-- <= 0 && MatchPattern(pattern,text,path_sep) )
326 		    return !pat->active_negate;
327 		default_result = pat->active_negate;
328 		break;
329 
330 	    default:
331 		if ( skip-- <= 0 )
332 		{
333 		    pattern--;
334 		    ulong num = strtoul(pattern,&pattern,10);
335 		    switch (*pattern++)
336 		    {
337 			case '-':
338 			    if (!MatchPattern(pattern,text,path_sep))
339 				skip = num;
340 			    break;
341 
342 			case '+':
343 			    if (MatchPattern(pattern,text,path_sep))
344 				skip = num;
345 			    break;
346 		    }
347 		}
348 		break;
349 	}
350     }
351 
352     return default_result;
353 }
354 
355 ///////////////////////////////////////////////////////////////////////////////
356 
MatchFilePatternFST(struct wd_iterator_t * it)357 int MatchFilePatternFST
358 (
359 	struct wd_iterator_t *it	// iterator struct with all infos
360 )
361 {
362     DASSERT(it);
363     // result>0: ignore this file
364     return it->icm >= WD_ICM_DIRECTORY
365 	&& !MatchFilePattern(it->param,it->fst_name,'/');
366 }
367 
368 //
369 ///////////////////////////////////////////////////////////////////////////////
370 ///////////////                 MatchPattern()                  ///////////////
371 ///////////////////////////////////////////////////////////////////////////////
372 
AnalyseBrackets(ccp pattern,ccp * p_start,bool * p_negate,int * p_multiple)373 static ccp AnalyseBrackets
374 (
375     ccp		pattern,
376     ccp		* p_start,
377     bool	* p_negate,
378     int		* p_multiple
379 )
380 {
381     ASSERT(pattern);
382 
383     bool negate = false;
384     if ( *pattern == '^' )
385     {
386 	pattern++;
387 	negate = true;
388     }
389     if (p_negate)
390 	*p_negate = negate;
391 
392     int multiple = 0;
393     if ( *pattern == '+' )
394     {
395 	pattern++;
396 	multiple = 1;
397     }
398     else if ( *pattern == '*' )
399     {
400 	pattern++;
401 	multiple = 2;
402     }
403     if (p_multiple)
404 	*p_multiple = multiple;
405 
406     if (p_start)
407 	*p_start = pattern;
408 
409     if (*pattern) // ']' allowed in first position
410 	pattern++;
411     while ( *pattern && *pattern++ != ']' ) // find end
412 	;
413 
414     return pattern;
415 }
416 
417 //-----------------------------------------------------------------------------
418 
MatchBracktes(char ch,ccp pattern,bool negate)419 static bool MatchBracktes
420 (
421     char	ch,
422     ccp		pattern,
423     bool	negate
424 )
425 {
426     if (!ch)
427 	return false;
428 
429     bool ok = false;
430     ccp p = pattern;
431     for (; !ok && *p && ( p == pattern || *p != ']' ); p++ )
432     {
433 	if ( *p == '-' )
434 	{
435 	    if ( ch <= *++p && ch >= p[-2] )
436 	    {
437 		if (negate)
438 		    return false;
439 		ok = true;
440 	    }
441 	}
442 	else
443 	{
444 	    if ( *p == '\\' )
445 		p++;
446 
447 	    if ( *p == ch )
448 	    {
449 		if (negate)
450 		    return false;
451 		ok = true;
452 	    }
453 	}
454     }
455     return ok || negate;
456 }
457 
458 //-----------------------------------------------------------------------------
459 
MatchPatternHelper(ccp pattern,ccp text,bool skip_end,int alt_depth,char path_sep)460 static bool MatchPatternHelper
461 (
462     ccp		pattern,
463     ccp		text,
464     bool	skip_end,
465     int		alt_depth,
466     char	path_sep	// path separator character, standard is '/'
467 )
468 {
469     ASSERT(pattern);
470     ASSERT(text);
471     noTRACE(" - %d,%d |%s|%s|\n",skip_end,alt_depth,pattern,text);
472 
473     char ch;
474     while ( ( ch = *pattern++ ) != 0 )
475     {
476 	switch (ch)
477 	{
478 	   case '*':
479 		if ( *pattern == '*' )
480 		{
481 		    pattern++;
482 		    if (*pattern)
483 			while (!MatchPatternHelper(pattern,text,skip_end,alt_depth,path_sep))
484 			    if (!*text++)
485 				return false;
486 		}
487 		else
488 		{
489 		    while (!MatchPatternHelper(pattern,text,skip_end,alt_depth,path_sep))
490 			if ( *text == path_sep || !*text++ )
491 			    return false;
492 		}
493 		return true;
494 
495 	    case '#':
496 	 	if ( *text < '0' || *text > '9' )
497 		    return false;
498 		while ( *text >= '0' && *text <= '9' )
499 			if (MatchPatternHelper(pattern,++text,skip_end,alt_depth,path_sep))
500 			    return true;
501 		return false;
502 
503 	    case ' ':
504 		if ( *text < 1 || * text > ' ' )
505 		    return false;
506 		text++;
507 		break;
508 
509 	    case '?':
510 		if ( !*text || *text == path_sep )
511 		    return false;
512 		text++;
513 		break;
514 
515 	    case '[':
516 		{
517 		    ccp start;
518 		    bool negate;
519 		    int multiple;
520 		    TRACELINE;
521 		    pattern = AnalyseBrackets(pattern,&start,&negate,&multiple);
522 		    TRACELINE;
523 
524 		    if ( multiple < 2 && !MatchBracktes(*text++,start,negate) )
525 			return false;
526 
527 		    if (multiple)
528 		    {
529 			while (!MatchPatternHelper(pattern,text,skip_end,alt_depth,path_sep))
530 			    if (!MatchBracktes(*text++,start,negate))
531 				return false;
532 			return true;
533 		    }
534 		}
535 		break;
536 
537 	   case '{':
538 		for (;;)
539 		{
540 		    if (MatchPatternHelper(pattern,text,skip_end,alt_depth+1,path_sep))
541 			return true;
542 		    // skip until next ',' || '}'
543 		    int skip_depth = 1;
544 		    while ( skip_depth > 0 )
545 		    {
546 			ch = *pattern++;
547 			switch(ch)
548 			{
549 			    case 0:
550 				return false;
551 
552 			    case '\\':
553 				if (!*pattern)
554 				    return false;
555 				pattern++;
556 				break;
557 
558 			    case '{':
559 				skip_depth++;
560 				break;
561 
562 			    case ',':
563 				if ( skip_depth == 1 )
564 				    skip_depth--;
565 				break;
566 
567 			    case '}':
568 				if (!--skip_depth)
569 				    return false;
570 				break;
571 
572 			    case '[': // [[2do]] forgotten marker?
573 				pattern = AnalyseBrackets(pattern,0,0,0);
574 				break;
575 			}
576 		    }
577 		}
578 
579 	   case ',':
580 		if (alt_depth)
581 		{
582 		    alt_depth--;
583 		    int skip_depth = 1;
584 		    while ( skip_depth > 0 )
585 		    {
586 			ch = *pattern++;
587 			switch(ch)
588 			{
589 			    case 0:
590 				return false;
591 
592 			    case '\\':
593 				if (!*pattern)
594 				    return false;
595 				pattern++;
596 				break;
597 
598 			    case '{':
599 				skip_depth++;
600 				break;
601 
602 			    case '}':
603 				skip_depth--;
604 				break;
605 
606 			    case '[': // [[2do]] forgotten marker?
607 				pattern = AnalyseBrackets(pattern,0,0,0);
608 				break;
609 			}
610 		    }
611 		}
612 		else if ( *text++ != ch )
613 		    return false;
614 		break;
615 
616 	   case '}':
617 		if ( !alt_depth && *text++ != ch )
618 		    return false;
619 		break;
620 
621 	   case '$':
622 		if ( !*pattern && !*text )
623 		    return true;
624 		if ( *text++ != ch )
625 		    return false;
626 		break;
627 
628 	   case '\\':
629 		ch = *pattern++;
630 		// fall through
631 
632 	   default:
633 		if ( *text++ != ch )
634 		    return false;
635 		break;
636 	}
637     }
638     return skip_end || *text == 0;
639 }
640 
641 //-----------------------------------------------------------------------------
642 
MatchPattern(ccp pattern,ccp text,char path_sep)643 bool MatchPattern
644 (
645     ccp		pattern,	// pattern text
646     ccp		text,		// raw text
647     char	path_sep	// path separator character, standard is '/'
648 )
649 {
650     TRACE("MatchPattern(|%s|%s|%c|)\n",pattern,text,path_sep);
651     if ( !pattern || !*pattern )
652 	return true;
653 
654     if (!text)
655 	text = "";
656 
657     const size_t plen = strlen(pattern);
658     ccp last = pattern + plen - 1;
659     char last_ch = *last;
660     int count = 0;
661     while ( last > pattern && *--last == '\\' )
662 	count++;
663     if ( count & 1 )
664 	last_ch = 0; // no special char!
665 
666     if ( *pattern == path_sep )
667     {
668 	pattern++;
669 	return MatchPatternHelper(pattern,text++,last_ch!='$',0,path_sep);
670     }
671 
672     while (*text)
673 	if (MatchPatternHelper(pattern,text++,0,0,path_sep))
674 	    return true;
675 
676     return false;
677 }
678 
679 //
680 ///////////////////////////////////////////////////////////////////////////////
681 ///////////////                     END                         ///////////////
682 ///////////////////////////////////////////////////////////////////////////////
683