summaryrefslogtreecommitdiff
path: root/shell/match.c
blob: e77c5d7327681e9f0e59b09a5612d7be1d543633 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
 * ##/%% variable matching code ripped out of ash shell for code sharing
 *
 * This code is derived from software contributed to Berkeley by
 * Kenneth Almquist.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
 *
 * Copyright (c) 1989, 1991, 1993, 1994
 *      The Regents of the University of California.  All rights reserved.
 *
 * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
 * was re-ported from NetBSD and debianized.
 */
#ifdef STANDALONE
# include <stdbool.h>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <unistd.h>
# define FAST_FUNC /* nothing */
# define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
# define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
#else
# include "libbb.h"
#endif
#include <fnmatch.h>
#include "match.h"

#define pmatch(a, b) !fnmatch((a), (b), 0)

char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags)
{
	char *loc;
	char *end;
	unsigned len = strlen(string);
	int early_exit;

	/* We can stop the scan early only if the string part
	 * we are matching against is shrinking, and the pattern has
	 * an unquoted "star" at the corresponding end. There are two cases.
	 * Case 1:
	 * "qwerty" does not match against pattern "*zy",
	 * no point in trying to match "werty", "erty" etc:
	 */
	early_exit = (flags == (SCAN_MOVE_FROM_LEFT + SCAN_MATCH_RIGHT_HALF) && pattern[0] == '*');

	if (flags & SCAN_MOVE_FROM_LEFT) {
		loc = string;
		end = string + len + 1;
	} else {
		loc = string + len;
		end = string - 1;
		if (flags == (SCAN_MOVE_FROM_RIGHT + SCAN_MATCH_LEFT_HALF)) {
			/* Case 2:
			 * "qwerty" does not match against pattern "qz*",
			 * no point in trying to match "qwert", "qwer" etc:
			 */
			const char *p = pattern + strlen(pattern);
			if (--p >= pattern && *p == '*') {
				early_exit = 1;
				while (--p >= pattern && *p == '\\')
					early_exit ^= 1;
			}
		}
	}

	while (loc != end) {
		char c;
		int match;

		c = *loc;
		if (flags & SCAN_MATCH_LEFT_HALF) {
			*loc = '\0';
			match = pmatch(pattern, string);
			*loc = c;
		} else {
			match = pmatch(pattern, loc);
		}
		if (match)
			return loc;
		if (early_exit) {
#ifdef STANDALONE
			printf("(early exit) ");
#endif
			break;
		}

		if (flags & SCAN_MOVE_FROM_LEFT) {
			loc++;
		} else {
			loc--;
		}
	}
	return NULL;
}

#ifdef STANDALONE
int main(int argc, char *argv[])
{
	char *string;
	char *op;
	char *pattern;
	char *loc;

	setvbuf(stdout, NULL, _IONBF, 0);

	if (!argv[1]) {
		puts(
			"Usage: match <test> [test...]\n\n"
			"Where a <test> is the form: <string><op><match>\n"
			"This is to test the shell ${var#val} expression type.\n\n"
			"e.g. `match 'abc#a*'` -> bc"
		);
		return 1;
	}

	while (*++argv) {
		size_t off;
		unsigned scan_flags;

		string = *argv;
		off = strcspn(string, "#%");
		if (!off) {
			printf("invalid format\n");
			continue;
		}
		op = string + off;
		scan_flags = pick_scan(op[0], op[1]);

		printf("'%s': flags:%x, ", string, scan_flags);
		pattern = op + 1;
		if (op[0] == op[1])
			pattern++;
		op[0] = '\0';

		loc = scan_and_match(string, pattern, scan_flags);

		if (scan_flags & SCAN_MATCH_LEFT_HALF) {
			printf("'%s'\n", loc);
		} else {
			if (loc)
				*loc = '\0';
			printf("'%s'\n", string);
		}
	}

	return 0;
}
#endif