xref: /freebsd/usr.bin/col/col.c (revision ef36b3f75658d201edb495068db5e1be49593de5)
1 /*-
2  * Copyright (c) 1990, 1993, 1994
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Michael Rendell of the Memorial University of Newfoundland.
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  * 3. 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) 1990, 1993, 1994\n\
36 	The Regents of the University of California.  All rights reserved.\n";
37 #endif
38 
39 #if 0
40 #ifndef lint
41 static char sccsid[] = "@(#)col.c	8.5 (Berkeley) 5/4/95";
42 #endif
43 #endif
44 
45 #include <sys/cdefs.h>
46 __FBSDID("$FreeBSD$");
47 
48 #include <sys/capsicum.h>
49 
50 #include <capsicum_helpers.h>
51 #include <err.h>
52 #include <errno.h>
53 #include <locale.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <string.h>
57 #include <termios.h>
58 #include <unistd.h>
59 #include <wchar.h>
60 #include <wctype.h>
61 
62 #define	BS	'\b'		/* backspace */
63 #define	TAB	'\t'		/* tab */
64 #define	SPACE	' '		/* space */
65 #define	NL	'\n'		/* newline */
66 #define	CR	'\r'		/* carriage return */
67 #define	ESC	'\033'		/* escape */
68 #define	SI	'\017'		/* shift in to normal character set */
69 #define	SO	'\016'		/* shift out to alternate character set */
70 #define	VT	'\013'		/* vertical tab (aka reverse line feed) */
71 #define	RLF	'7'		/* ESC-7 reverse line feed */
72 #define	RHLF	'8'		/* ESC-8 reverse half-line feed */
73 #define	FHLF	'9'		/* ESC-9 forward half-line feed */
74 
75 /* build up at least this many lines before flushing them out */
76 #define	BUFFER_MARGIN		32
77 
78 typedef char CSET;
79 
80 typedef struct char_str {
81 #define	CS_NORMAL	1
82 #define	CS_ALTERNATE	2
83 	short		c_column;	/* column character is in */
84 	CSET		c_set;		/* character set (currently only 2) */
85 	wchar_t		c_char;		/* character in question */
86 	int		c_width;	/* character width */
87 } CHAR;
88 
89 typedef struct line_str LINE;
90 struct line_str {
91 	CHAR	*l_line;		/* characters on the line */
92 	LINE	*l_prev;		/* previous line */
93 	LINE	*l_next;		/* next line */
94 	int	l_lsize;		/* allocated sizeof l_line */
95 	int	l_line_len;		/* strlen(l_line) */
96 	int	l_needs_sort;		/* set if chars went in out of order */
97 	int	l_max_col;		/* max column in the line */
98 };
99 
100 static void	addto_lineno(int *, int);
101 static LINE   *alloc_line(void);
102 static void	dowarn(int);
103 static void	flush_line(LINE *);
104 static void	flush_lines(int);
105 static void	flush_blanks(void);
106 static void	free_line(LINE *);
107 static void	usage(void);
108 
109 static CSET	last_set;		/* char_set of last char printed */
110 static LINE    *lines;
111 static int	compress_spaces;	/* if doing space -> tab conversion */
112 static int	fine;			/* if `fine' resolution (half lines) */
113 static int	max_bufd_lines;		/* max # of half lines to keep in memory */
114 static int	nblank_lines;		/* # blanks after last flushed line */
115 static int	no_backspaces;		/* if not to output any backspaces */
116 static int	pass_unknown_seqs;	/* pass unknown control sequences */
117 
118 #define	PUTC(ch) \
119 	do {					\
120 		if (putwchar(ch) == WEOF)	\
121 			errx(1, "write error");	\
122 	} while (0)
123 
124 int
125 main(int argc, char **argv)
126 {
127 	wint_t ch;
128 	CHAR *c;
129 	CSET cur_set;			/* current character set */
130 	LINE *l;			/* current line */
131 	int extra_lines;		/* # of lines above first line */
132 	int cur_col;			/* current column */
133 	int cur_line;			/* line number of current position */
134 	int max_line;			/* max value of cur_line */
135 	int this_line;			/* line l points to */
136 	int nflushd_lines;		/* number of lines that were flushed */
137 	int adjust, opt, warned, width;
138 	const char *errstr;
139 
140 	(void)setlocale(LC_CTYPE, "");
141 
142 	if (caph_limit_stdio() == -1)
143 		err(1, "unable to limit stdio");
144 
145 	if (cap_enter() < 0 && errno != ENOSYS)
146 		err(1, "unable to enter capability mode");
147 
148 	max_bufd_lines = 256;
149 	compress_spaces = 1;		/* compress spaces into tabs */
150 	while ((opt = getopt(argc, argv, "bfhl:px")) != -1)
151 		switch (opt) {
152 		case 'b':		/* do not output backspaces */
153 			no_backspaces = 1;
154 			break;
155 		case 'f':		/* allow half forward line feeds */
156 			fine = 1;
157 			break;
158 		case 'h':		/* compress spaces into tabs */
159 			compress_spaces = 1;
160 			break;
161 		case 'l':		/* buffered line count */
162 			max_bufd_lines = strtonum(optarg, 1,
163 			    (INT_MAX - BUFFER_MARGIN) / 2, &errstr) * 2;
164 			if (errstr != NULL)
165 				errx(1, "bad -l argument, %s: %s", errstr,
166 					optarg);
167 			break;
168 		case 'p':		/* pass unknown control sequences */
169 			pass_unknown_seqs = 1;
170 			break;
171 		case 'x':		/* do not compress spaces into tabs */
172 			compress_spaces = 0;
173 			break;
174 		case '?':
175 		default:
176 			usage();
177 		}
178 
179 	if (optind != argc)
180 		usage();
181 
182 	adjust = cur_col = extra_lines = warned = 0;
183 	cur_line = max_line = nflushd_lines = this_line = 0;
184 	cur_set = last_set = CS_NORMAL;
185 	lines = l = alloc_line();
186 
187 	while ((ch = getwchar()) != WEOF) {
188 		if (!iswgraph(ch)) {
189 			switch (ch) {
190 			case BS:		/* can't go back further */
191 				if (cur_col == 0)
192 					continue;
193 				--cur_col;
194 				continue;
195 			case CR:
196 				cur_col = 0;
197 				continue;
198 			case ESC:		/* just ignore EOF */
199 				switch(getwchar()) {
200 				/*
201 				 * In the input stream, accept both the
202 				 * XPG5 sequences ESC-digit and the
203 				 * traditional BSD sequences ESC-ctrl.
204 				 */
205 				case '\007':
206 					/* FALLTHROUGH */
207 				case RLF:
208 					addto_lineno(&cur_line, -2);
209 					break;
210 				case '\010':
211 					/* FALLTHROUGH */
212 				case RHLF:
213 					addto_lineno(&cur_line, -1);
214 					break;
215 				case '\011':
216 					/* FALLTHROUGH */
217 				case FHLF:
218 					addto_lineno(&cur_line, 1);
219 					if (cur_line > max_line)
220 						max_line = cur_line;
221 				}
222 				continue;
223 			case NL:
224 				addto_lineno(&cur_line, 2);
225 				if (cur_line > max_line)
226 					max_line = cur_line;
227 				cur_col = 0;
228 				continue;
229 			case SPACE:
230 				++cur_col;
231 				continue;
232 			case SI:
233 				cur_set = CS_NORMAL;
234 				continue;
235 			case SO:
236 				cur_set = CS_ALTERNATE;
237 				continue;
238 			case TAB:		/* adjust column */
239 				cur_col |= 7;
240 				++cur_col;
241 				continue;
242 			case VT:
243 				addto_lineno(&cur_line, -2);
244 				continue;
245 			}
246 			if (iswspace(ch)) {
247 				if ((width = wcwidth(ch)) > 0)
248 					cur_col += width;
249 				continue;
250 			}
251 			if (!pass_unknown_seqs)
252 				continue;
253 		}
254 
255 		/* Must stuff ch in a line - are we at the right one? */
256 		if (cur_line + adjust != this_line) {
257 			LINE *lnew;
258 
259 			/* round up to next line */
260 			adjust = !fine && (cur_line & 1);
261 
262 			if (cur_line + adjust < this_line) {
263 				while (cur_line + adjust < this_line &&
264 				    l->l_prev != NULL) {
265 					l = l->l_prev;
266 					this_line--;
267 				}
268 				if (cur_line + adjust < this_line) {
269 					if (nflushd_lines == 0) {
270 						/*
271 						 * Allow backup past first
272 						 * line if nothing has been
273 						 * flushed yet.
274 						 */
275 						while (cur_line + adjust
276 						    < this_line) {
277 							lnew = alloc_line();
278 							l->l_prev = lnew;
279 							lnew->l_next = l;
280 							l = lines = lnew;
281 							extra_lines++;
282 							this_line--;
283 						}
284 					} else {
285 						if (!warned++)
286 							dowarn(cur_line);
287 						cur_line = this_line - adjust;
288 					}
289 				}
290 			} else {
291 				/* may need to allocate here */
292 				while (cur_line + adjust > this_line) {
293 					if (l->l_next == NULL) {
294 						l->l_next = alloc_line();
295 						l->l_next->l_prev = l;
296 					}
297 					l = l->l_next;
298 					this_line++;
299 				}
300 			}
301 			if (this_line > nflushd_lines &&
302 			    this_line - nflushd_lines >=
303 			    max_bufd_lines + BUFFER_MARGIN) {
304 				if (extra_lines) {
305 					flush_lines(extra_lines);
306 					extra_lines = 0;
307 				}
308 				flush_lines(this_line - nflushd_lines -
309 				    max_bufd_lines);
310 				nflushd_lines = this_line - max_bufd_lines;
311 			}
312 		}
313 		/* grow line's buffer? */
314 		if (l->l_line_len + 1 >= l->l_lsize) {
315 			int need;
316 
317 			need = l->l_lsize ? l->l_lsize * 2 : 90;
318 			if ((l->l_line = realloc(l->l_line,
319 			    (unsigned)need * sizeof(CHAR))) == NULL)
320 				err(1, NULL);
321 			l->l_lsize = need;
322 		}
323 		c = &l->l_line[l->l_line_len++];
324 		c->c_char = ch;
325 		c->c_set = cur_set;
326 		c->c_column = cur_col;
327 		c->c_width = wcwidth(ch);
328 		/*
329 		 * If things are put in out of order, they will need sorting
330 		 * when it is flushed.
331 		 */
332 		if (cur_col < l->l_max_col)
333 			l->l_needs_sort = 1;
334 		else
335 			l->l_max_col = cur_col;
336 		if (c->c_width > 0)
337 			cur_col += c->c_width;
338 	}
339 	if (ferror(stdin))
340 		err(1, NULL);
341 	if (extra_lines)
342 		flush_lines(extra_lines);
343 
344 	/* goto the last line that had a character on it */
345 	for (; l->l_next; l = l->l_next)
346 		this_line++;
347 	flush_lines(this_line - nflushd_lines + 1);
348 
349 	/* make sure we leave things in a sane state */
350 	if (last_set != CS_NORMAL)
351 		PUTC(SI);
352 
353 	/* flush out the last few blank lines */
354 	if (max_line > this_line)
355 		nblank_lines = max_line - this_line;
356 	if (max_line & 1)
357 		nblank_lines++;
358 	flush_blanks();
359 	exit(0);
360 }
361 
362 static void
363 flush_lines(int nflush)
364 {
365 	LINE *l;
366 
367 	while (--nflush >= 0) {
368 		l = lines;
369 		lines = l->l_next;
370 		if (l->l_line) {
371 			flush_blanks();
372 			flush_line(l);
373 		}
374 		if (l->l_line || l->l_next)
375 			nblank_lines++;
376 		if (l->l_line)
377 			(void)free(l->l_line);
378 		free_line(l);
379 	}
380 	if (lines)
381 		lines->l_prev = NULL;
382 }
383 
384 /*
385  * Print a number of newline/half newlines.  If fine flag is set, nblank_lines
386  * is the number of half line feeds, otherwise it is the number of whole line
387  * feeds.
388  */
389 static void
390 flush_blanks(void)
391 {
392 	int half, i, nb;
393 
394 	half = 0;
395 	nb = nblank_lines;
396 	if (nb & 1) {
397 		if (fine)
398 			half = 1;
399 		else
400 			nb++;
401 	}
402 	nb /= 2;
403 	for (i = nb; --i >= 0;)
404 		PUTC('\n');
405 	if (half) {
406 		PUTC(ESC);
407 		PUTC(FHLF);
408 		if (!nb)
409 			PUTC('\r');
410 	}
411 	nblank_lines = 0;
412 }
413 
414 /*
415  * Write a line to stdout taking care of space to tab conversion (-h flag)
416  * and character set shifts.
417  */
418 static void
419 flush_line(LINE *l)
420 {
421 	CHAR *c, *endc;
422 	int i, j, nchars, last_col, save, this_col, tot;
423 
424 	last_col = 0;
425 	nchars = l->l_line_len;
426 
427 	if (l->l_needs_sort) {
428 		static CHAR *sorted;
429 		static int count_size, *count, sorted_size;
430 
431 		/*
432 		 * Do an O(n) sort on l->l_line by column being careful to
433 		 * preserve the order of characters in the same column.
434 		 */
435 		if (l->l_lsize > sorted_size) {
436 			sorted_size = l->l_lsize;
437 			if ((sorted = realloc(sorted,
438 			    (unsigned)sizeof(CHAR) * sorted_size)) == NULL)
439 				err(1, NULL);
440 		}
441 		if (l->l_max_col >= count_size) {
442 			count_size = l->l_max_col + 1;
443 			if ((count = realloc(count,
444 			    (unsigned)sizeof(int) * count_size)) == NULL)
445 				err(1, NULL);
446 		}
447 		memset(count, 0, sizeof(int) * l->l_max_col + 1);
448 		for (i = nchars, c = l->l_line; --i >= 0; c++)
449 			count[c->c_column]++;
450 
451 		/*
452 		 * calculate running total (shifted down by 1) to use as
453 		 * indices into new line.
454 		 */
455 		for (tot = 0, i = 0; i <= l->l_max_col; i++) {
456 			save = count[i];
457 			count[i] = tot;
458 			tot += save;
459 		}
460 
461 		for (i = nchars, c = l->l_line; --i >= 0; c++)
462 			sorted[count[c->c_column]++] = *c;
463 		c = sorted;
464 	} else
465 		c = l->l_line;
466 	while (nchars > 0) {
467 		this_col = c->c_column;
468 		endc = c;
469 		do {
470 			++endc;
471 		} while (--nchars > 0 && this_col == endc->c_column);
472 
473 		/* if -b only print last character */
474 		if (no_backspaces) {
475 			c = endc - 1;
476 			if (nchars > 0 &&
477 			    this_col + c->c_width > endc->c_column)
478 				continue;
479 		}
480 
481 		if (this_col > last_col) {
482 			int nspace = this_col - last_col;
483 
484 			if (compress_spaces && nspace > 1) {
485 				while (1) {
486 					int tab_col, tab_size;
487 
488 					tab_col = (last_col + 8) & ~7;
489 					if (tab_col > this_col)
490 						break;
491 					tab_size = tab_col - last_col;
492 					if (tab_size == 1)
493 						PUTC(' ');
494 					else
495 						PUTC('\t');
496 					nspace -= tab_size;
497 					last_col = tab_col;
498 				}
499 			}
500 			while (--nspace >= 0)
501 				PUTC(' ');
502 			last_col = this_col;
503 		}
504 
505 		for (;;) {
506 			if (c->c_set != last_set) {
507 				switch (c->c_set) {
508 				case CS_NORMAL:
509 					PUTC(SI);
510 					break;
511 				case CS_ALTERNATE:
512 					PUTC(SO);
513 				}
514 				last_set = c->c_set;
515 			}
516 			PUTC(c->c_char);
517 			if ((c + 1) < endc)
518 				for (j = 0; j < c->c_width; j++)
519 					PUTC('\b');
520 			if (++c >= endc)
521 				break;
522 		}
523 		last_col += (c - 1)->c_width;
524 	}
525 }
526 
527 /*
528  * Increment or decrement a line number, checking for overflow.
529  * Stop one below INT_MAX such that the adjust variable is safe.
530  */
531 void
532 addto_lineno(int *lno, int offset)
533 {
534 	if (offset > 0) {
535 		if (*lno >= INT_MAX - offset)
536 			errx(1, "too many lines");
537 	} else {
538 		if (*lno < INT_MIN - offset)
539 			errx(1, "too many reverse line feeds");
540 	}
541 	*lno += offset;
542 }
543 
544 #define	NALLOC 64
545 
546 static LINE *line_freelist;
547 
548 static LINE *
549 alloc_line(void)
550 {
551 	LINE *l;
552 	int i;
553 
554 	if (!line_freelist) {
555 		if ((l = realloc(NULL, sizeof(LINE) * NALLOC)) == NULL)
556 			err(1, NULL);
557 		line_freelist = l;
558 		for (i = 1; i < NALLOC; i++, l++)
559 			l->l_next = l + 1;
560 		l->l_next = NULL;
561 	}
562 	l = line_freelist;
563 	line_freelist = l->l_next;
564 
565 	memset(l, 0, sizeof(LINE));
566 	return (l);
567 }
568 
569 static void
570 free_line(LINE *l)
571 {
572 
573 	l->l_next = line_freelist;
574 	line_freelist = l;
575 }
576 
577 static void
578 usage(void)
579 {
580 
581 	(void)fprintf(stderr, "usage: col [-bfhpx] [-l nline]\n");
582 	exit(1);
583 }
584 
585 static void
586 dowarn(int line)
587 {
588 
589 	warnx("warning: can't back up %s",
590 		line < 0 ? "past first line" : "-- line already flushed");
591 }
592