xref: /freebsd/usr.bin/look/look.c (revision a223d3ed90bfe313ce5987d468a25a915d7d1254)
1 /*-
2  * Copyright (c) 1991, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * David Hitz of Auspex Systems, Inc.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 4. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  */
32 
33 #ifndef lint
34 static const char copyright[] =
35 "@(#) Copyright (c) 1991, 1993\n\
36 	The Regents of the University of California.  All rights reserved.\n";
37 #endif /* not lint */
38 
39 #ifndef lint
40 #if 0
41 static char sccsid[] = "@(#)look.c	8.2 (Berkeley) 5/4/95";
42 #endif
43 #endif /* not lint */
44 #include <sys/cdefs.h>
45 __FBSDID("$FreeBSD$");
46 
47 /*
48  * look -- find lines in a sorted list.
49  *
50  * The man page said that TABs and SPACEs participate in -d comparisons.
51  * In fact, they were ignored.  This implements historic practice, not
52  * the manual page.
53  */
54 
55 #include <sys/types.h>
56 #include <sys/mman.h>
57 #include <sys/stat.h>
58 
59 #include <err.h>
60 #include <errno.h>
61 #include <fcntl.h>
62 #include <limits.h>
63 #include <locale.h>
64 #include <stdint.h>
65 #include <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68 #include <unistd.h>
69 #include <wchar.h>
70 #include <wctype.h>
71 
72 #include "pathnames.h"
73 
74 static char _path_words[] = _PATH_WORDS;
75 
76 #define	EQUAL		0
77 #define	GREATER		1
78 #define	LESS		(-1)
79 
80 static int dflag, fflag;
81 
82 static char	*binary_search(wchar_t *, unsigned char *, unsigned char *);
83 static int	 compare(wchar_t *, unsigned char *, unsigned char *);
84 static char	*linear_search(wchar_t *, unsigned char *, unsigned char *);
85 static int	 look(wchar_t *, unsigned char *, unsigned char *);
86 static wchar_t	*prepkey(const char *, wchar_t);
87 static void	 print_from(wchar_t *, unsigned char *, unsigned char *);
88 
89 static void usage(void);
90 
91 int
92 main(int argc, char *argv[])
93 {
94 	struct stat sb;
95 	int ch, fd, match;
96 	wchar_t termchar;
97 	unsigned char *back, *front;
98 	unsigned const char *file;
99 	wchar_t *key;
100 
101 	(void) setlocale(LC_CTYPE, "");
102 
103 	file = _path_words;
104 	termchar = L'\0';
105 	while ((ch = getopt(argc, argv, "adft:")) != -1)
106 		switch(ch) {
107 		case 'a':
108 			/* COMPATIBILITY */
109 			break;
110 		case 'd':
111 			dflag = 1;
112 			break;
113 		case 'f':
114 			fflag = 1;
115 			break;
116 		case 't':
117 			if (mbrtowc(&termchar, optarg, MB_LEN_MAX, NULL) !=
118 			    strlen(optarg))
119 				errx(2, "invalid termination character");
120 			break;
121 		case '?':
122 		default:
123 			usage();
124 		}
125 	argc -= optind;
126 	argv += optind;
127 
128 	if (argc == 0)
129 		usage();
130 	if (argc == 1) 			/* But set -df by default. */
131 		dflag = fflag = 1;
132 	key = prepkey(*argv++, termchar);
133 	if (argc >= 2)
134 		file = *argv++;
135 
136 	match = 1;
137 
138 	do {
139 		if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb))
140 			err(2, "%s", file);
141 		if ((uintmax_t)sb.st_size > (uintmax_t)SIZE_T_MAX)
142 			errx(2, "%s: %s", file, strerror(EFBIG));
143 		if (sb.st_size == 0) {
144 			close(fd);
145 			continue;
146 		}
147 		if ((front = mmap(NULL, (size_t)sb.st_size, PROT_READ, MAP_SHARED, fd, (off_t)0)) == MAP_FAILED)
148 			err(2, "%s", file);
149 		back = front + sb.st_size;
150 		match *= (look(key, front, back));
151 		close(fd);
152 	} while (argc-- > 2 && (file = *argv++));
153 
154 	exit(match);
155 }
156 
157 static wchar_t *
158 prepkey(const char *string, wchar_t termchar)
159 {
160 	const char *readp;
161 	wchar_t *key, *writep;
162 	wchar_t ch;
163 	size_t clen;
164 
165 	/*
166 	 * Reformat search string and convert to wide character representation
167 	 * to avoid doing it multiple times later.
168 	 */
169 	if ((key = malloc(sizeof(wchar_t) * (strlen(string) + 1))) == NULL)
170 		err(2, NULL);
171 	readp = string;
172 	writep = key;
173 	while ((clen = mbrtowc(&ch, readp, MB_LEN_MAX, NULL)) != 0) {
174 		if (clen == (size_t)-1 || clen == (size_t)-2)
175 			errc(2, EILSEQ, NULL);
176 		if (fflag)
177 			ch = towlower(ch);
178 		if (!dflag || iswalnum(ch))
179 			*writep++ = ch;
180 		readp += clen;
181 	}
182 	*writep = L'\0';
183 	if (termchar != L'\0' && (writep = wcschr(key, termchar)) != NULL)
184 		*++writep = L'\0';
185 	return (key);
186 }
187 
188 static int
189 look(wchar_t *string, unsigned char *front, unsigned char *back)
190 {
191 
192 	front = binary_search(string, front, back);
193 	front = linear_search(string, front, back);
194 
195 	if (front)
196 		print_from(string, front, back);
197 	return (front ? 0 : 1);
198 }
199 
200 
201 /*
202  * Binary search for "string" in memory between "front" and "back".
203  *
204  * This routine is expected to return a pointer to the start of a line at
205  * *or before* the first word matching "string".  Relaxing the constraint
206  * this way simplifies the algorithm.
207  *
208  * Invariants:
209  * 	front points to the beginning of a line at or before the first
210  *	matching string.
211  *
212  * 	back points to the beginning of a line at or after the first
213  *	matching line.
214  *
215  * Base of the Invariants.
216  * 	front = NULL;
217  *	back = EOF;
218  *
219  * Advancing the Invariants:
220  *
221  * 	p = first newline after halfway point from front to back.
222  *
223  * 	If the string at "p" is not greater than the string to match,
224  *	p is the new front.  Otherwise it is the new back.
225  *
226  * Termination:
227  *
228  * 	The definition of the routine allows it return at any point,
229  *	since front is always at or before the line to print.
230  *
231  * 	In fact, it returns when the chosen "p" equals "back".  This
232  *	implies that there exists a string is least half as long as
233  *	(back - front), which in turn implies that a linear search will
234  *	be no more expensive than the cost of simply printing a string or two.
235  *
236  * 	Trying to continue with binary search at this point would be
237  *	more trouble than it's worth.
238  */
239 #define	SKIP_PAST_NEWLINE(p, back) \
240 	while (p < back && *p++ != '\n');
241 
242 static char *
243 binary_search(wchar_t *string, unsigned char *front, unsigned char *back)
244 {
245 	unsigned char *p;
246 
247 	p = front + (back - front) / 2;
248 	SKIP_PAST_NEWLINE(p, back);
249 
250 	/*
251 	 * If the file changes underneath us, make sure we don't
252 	 * infinitely loop.
253 	 */
254 	while (p < back && back > front) {
255 		if (compare(string, p, back) == GREATER)
256 			front = p;
257 		else
258 			back = p;
259 		p = front + (back - front) / 2;
260 		SKIP_PAST_NEWLINE(p, back);
261 	}
262 	return (front);
263 }
264 
265 /*
266  * Find the first line that starts with string, linearly searching from front
267  * to back.
268  *
269  * Return NULL for no such line.
270  *
271  * This routine assumes:
272  *
273  * 	o front points at the first character in a line.
274  *	o front is before or at the first line to be printed.
275  */
276 static char *
277 linear_search(wchar_t *string, unsigned char *front, unsigned char *back)
278 {
279 	while (front < back) {
280 		switch (compare(string, front, back)) {
281 		case EQUAL:		/* Found it. */
282 			return (front);
283 		case LESS:		/* No such string. */
284 			return (NULL);
285 		case GREATER:		/* Keep going. */
286 			break;
287 		}
288 		SKIP_PAST_NEWLINE(front, back);
289 	}
290 	return (NULL);
291 }
292 
293 /*
294  * Print as many lines as match string, starting at front.
295  */
296 static void
297 print_from(wchar_t *string, unsigned char *front, unsigned char *back)
298 {
299 	for (; front < back && compare(string, front, back) == EQUAL; ++front) {
300 		for (; front < back && *front != '\n'; ++front)
301 			if (putchar(*front) == EOF)
302 				err(2, "stdout");
303 		if (putchar('\n') == EOF)
304 			err(2, "stdout");
305 	}
306 }
307 
308 /*
309  * Return LESS, GREATER, or EQUAL depending on how the string1 compares with
310  * string2 (s1 ??? s2).
311  *
312  * 	o Matches up to len(s1) are EQUAL.
313  *	o Matches up to len(s2) are GREATER.
314  *
315  * Compare understands about the -f and -d flags, and treats comparisons
316  * appropriately.
317  *
318  * The string "s1" is null terminated.  The string s2 is '\n' terminated (or
319  * "back" terminated).
320  */
321 static int
322 compare(wchar_t *s1, unsigned char *s2, unsigned char *back)
323 {
324 	wchar_t ch1, ch2;
325 	size_t len2;
326 
327 	for (; *s1 && s2 < back && *s2 != '\n'; ++s1, s2 += len2) {
328 		ch1 = *s1;
329 		len2 = mbrtowc(&ch2, s2, back - s2, NULL);
330 		if (len2 == (size_t)-1 || len2 == (size_t)-2) {
331 			ch2 = *s2;
332 			len2 = 1;
333 		}
334 		if (fflag)
335 			ch2 = towlower(ch2);
336 		if (dflag && !iswalnum(ch2)) {
337 			/* Ignore character in comparison. */
338 			--s1;
339 			continue;
340 		}
341 		if (ch1 != ch2)
342 			return (ch1 < ch2 ? LESS : GREATER);
343 	}
344 	return (*s1 ? GREATER : EQUAL);
345 }
346 
347 static void
348 usage(void)
349 {
350 	(void)fprintf(stderr, "usage: look [-df] [-t char] string [file ...]\n");
351 	exit(2);
352 }
353