editors/sed.c

   1 /*
   2  * sed.c - very minimalist version of sed
   3  *
   4  * Copyright (C) 1999,2000,2001 by Lineo, inc. and Mark Whitley
   5  * Copyright (C) 1999,2000,2001 by Mark Whitley <markw@codepoet.org>
   6  * Copyright (C) 2002  Matt Kraai
   7  * Copyright (C) 2003 by Glenn McGrath <bug1@optushome.com.au>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17  * General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  22  *
  23  */
  24
  25 /*
  26         Supported features and commands in this version of sed:
  27
  28          - comments ('#')
  29          - address matching: num|/matchstr/[,num|/matchstr/|$]command
  30          - commands: (p)rint, (d)elete, (s)ubstitue (with g & I flags)
  31          - edit commands: (a)ppend, (i)nsert, (c)hange
  32          - file commands: (r)ead
  33          - backreferences in substitution expressions (\1, \2...\9)
  34          - grouped commands: {cmd1;cmd2}
  35          - transliteration (y/source-chars/dest-chars/)
  36          - pattern space hold space storing / swapping (g, h, x)
  37          - labels / branching (: label, b, t)
  38
  39          (Note: Specifying an address (range) to match is *optional*; commands
  40          default to the whole pattern space if no specific address match was
  41          requested.)
  42
  43         Unsupported features:
  44
  45          - GNU extensions
  46          - and more.
  47
  48         Bugs:
  49
  50          - lots
  51
  52         Reference http://www.opengroup.org/onlinepubs/007904975/utilities/sed.html
  53 */
  54
  55 #include <stdio.h>
  56 #include <unistd.h>             /* for getopt() */
  57 #include <regex.h>
  58 #include <string.h>             /* for strdup() */
  59 #include <errno.h>
  60 #include <ctype.h>              /* for isspace() */
  61 #include <stdlib.h>
  62 #include "busybox.h"
  63
  64 typedef struct sed_cmd_s {
  65         /* Order by alignment requirements */
  66
  67         /* address storage */
  68         regex_t *beg_match;     /* sed -e '/match/cmd' */
  69         regex_t *end_match;     /* sed -e '/match/,/end_match/cmd' */
  70
  71         int beg_line;           /* 'sed 1p'   0 == no begining line, apply commands to all lines */
  72         int end_line;           /* 'sed 1,3p' 0 == no end line, use only beginning. -1 == $ */
  73
  74         /* inversion flag */
  75         int invert;                     /* the '!' after the address */
  76
  77         /* Runtime flag no not if the current command match's */
  78         int still_in_range;
  79
  80         /* SUBSTITUTION COMMAND SPECIFIC FIELDS */
  81
  82         /* sed -e 's/sub_match/replace/' */
  83         regex_t *sub_match;
  84         char *replace;
  85
  86         /* EDIT COMMAND (a,i,c) SPECIFIC FIELDS */
  87         char *editline;
  88
  89         /* FILE COMMAND (r) SPECIFIC FIELDS */
  90         char *filename;
  91
  92         /* SUBSTITUTION COMMAND SPECIFIC FIELDS */
  93
  94         unsigned int num_backrefs:4;    /* how many back references (\1..\9) */
  95         /* Note:  GNU/POSIX sed does not save more than nine backrefs, so
  96          * we only use 4 bits to hold the number */
  97         unsigned int sub_g:1;   /* sed -e 's/foo/bar/g' (global) */
  98         unsigned int sub_p:1;   /* sed -e 's/foo/bar/p' (print substitution) */
  99
 100         /* TRANSLATE COMMAND */
 101         char *translate;
 102
 103         /* GENERAL FIELDS */
 104         /* the command */
 105         char cmd;                       /* p,d,s (add more at your leisure :-) */
 106
 107         /* Branch commands */
 108         char *label;
 109
 110         /* next command in list (sequential list of specified commands) */
 111         struct sed_cmd_s *next;
 112
 113 } sed_cmd_t;
 114
 115
 116 /* externs */
 117 extern void xregcomp(regex_t * preg, const char *regex, int cflags);
 118 extern int optind;              /* in unistd.h */
 119 extern char *optarg;    /* ditto */
 120
 121 /* globals */
 122 /* options */
 123 static int be_quiet = 0;
 124 static const char bad_format_in_subst[] =
 125         "bad format in substitution expression";
 126
 127 /* linked list of sed commands */
 128 static sed_cmd_t sed_cmd_head;
 129 static sed_cmd_t *sed_cmd_tail = &sed_cmd_head;
 130
 131 const char *const semicolon_whitespace = "; \n\r\t\v\0";
 132 static regex_t *previous_regex_ptr = NULL;
 133
 134
 135 #ifdef CONFIG_FEATURE_CLEAN_UP
 136 static void destroy_cmd_strs(void)
 137 {
 138         sed_cmd_t *sed_cmd = sed_cmd_head.next;
 139
 140         while (sed_cmd) {
 141                 sed_cmd_t *sed_cmd_next = sed_cmd->next;
 142
 143                 if (sed_cmd->beg_match) {
 144                         regfree(sed_cmd->beg_match);
 145                         free(sed_cmd->beg_match);
 146                 }
 147                 if (sed_cmd->end_match) {
 148                         regfree(sed_cmd->end_match);
 149                         free(sed_cmd->end_match);
 150                 }
 151                 if (sed_cmd->sub_match) {
 152                         regfree(sed_cmd->sub_match);
 153                         free(sed_cmd->sub_match);
 154                 }
 155                 free(sed_cmd->replace);
 156                 free(sed_cmd->editline);
 157                 free(sed_cmd->filename);
 158                 free(sed_cmd->translate);
 159                 free(sed_cmd->label);
 160                 free(sed_cmd);
 161                 sed_cmd = sed_cmd_next;
 162         }
 163 }
 164 #endif
 165
 166 /*
 167  * index_of_next_unescaped_regexp_delim - walks left to right through a string
 168  * beginning at a specified index and returns the index of the next regular
 169  * expression delimiter (typically a forward * slash ('/')) not preceeded by
 170  * a backslash ('\').
 171  */
 172 static int index_of_next_unescaped_regexp_delim(const char delimiter,
 173         const char *str)
 174 {
 175         int bracket = -1;
 176         int escaped = 0;
 177         int idx = 0;
 178         char ch;
 179
 180         for (; (ch = str[idx]); idx++) {
 181                 if (bracket != -1) {
 182                         if (ch == ']' && !(bracket == idx - 1 || (bracket == idx - 2
 183                                                 && str[idx - 1] == '^')))
 184                                 bracket = -1;
 185                 } else if (escaped)
 186                         escaped = 0;
 187                 else if (ch == '\\')
 188                         escaped = 1;
 189                 else if (ch == '[')
 190                         bracket = idx;
 191                 else if (ch == delimiter)
 192                         return idx;
 193         }
 194
 195         /* if we make it to here, we've hit the end of the string */
 196         return -1;
 197 }
 198
 199 /*
 200  *  Returns the index of the third delimiter
 201  */
 202 static int parse_regex_delim(const char *cmdstr, char **match, char **replace)
 203 {
 204         const char *cmdstr_ptr = cmdstr;
 205         char delimiter;
 206         int idx = 0;
 207
 208         /* verify that the 's' or 'y' is followed by something.  That something
 209          * (typically a 'slash') is now our regexp delimiter... */
 210         if (*cmdstr == '\0')
 211                 bb_error_msg_and_die(bad_format_in_subst);
 212         else
 213                 delimiter = *cmdstr_ptr;
 214
 215         cmdstr_ptr++;
 216
 217         /* save the match string */
 218         idx = index_of_next_unescaped_regexp_delim(delimiter, cmdstr_ptr);
 219         if (idx == -1) {
 220                 bb_error_msg_and_die(bad_format_in_subst);
 221         }
 222         *match = bb_xstrndup(cmdstr_ptr, idx);
 223
 224         /* save the replacement string */
 225         cmdstr_ptr += idx + 1;
 226         idx = index_of_next_unescaped_regexp_delim(delimiter, cmdstr_ptr);
 227         if (idx == -1) {
 228                 bb_error_msg_and_die(bad_format_in_subst);
 229         }
 230         *replace = bb_xstrndup(cmdstr_ptr, idx);
 231
 232         return ((cmdstr_ptr - cmdstr) + idx);
 233 }
 234
 235 /*
 236  * returns the index in the string just past where the address ends.
 237  */
 238 static int get_address(char *my_str, int *linenum, regex_t ** regex)
 239 {
 240         char *pos=my_str;
 241
 242         if (isdigit(*my_str)) {
 243                 *linenum = strtol(my_str, &pos, 10);
 244                 /* endstr shouldnt ever equal NULL */
 245         } else if (*my_str == '$') {
 246                 *linenum = -1;
 247                 pos++;
 248         } else if (*my_str == '/' || *my_str == '\\') {
 249                 int next, idx_start = 1;
 250                 char delimiter;
 251
 252                 delimiter = '/';
 253                 if (*my_str == '\\') {
 254                         idx_start++;
 255                         delimiter = *(++pos);
 256                 }
 257                 next = index_of_next_unescaped_regexp_delim(delimiter, ++pos);
 258                 if (next == -1) {
 259                         bb_error_msg_and_die("unterminated match expression");
 260                 }
 261                 pos += next;
 262                 *pos = '\0';
 263
 264                 *regex = (regex_t *) xmalloc(sizeof(regex_t));
 265                 xregcomp(*regex, my_str + idx_start, REG_NEWLINE);
 266                 pos++;                  /* so it points to the next character after the last '/' */
 267         }
 268         return pos - my_str;
 269 }
 270
 271 static int parse_subst_cmd(sed_cmd_t * const sed_cmd, const char *substr)
 272 {
 273         int cflags = 0;
 274         char *match;
 275         int idx = 0;
 276         int j;
 277
 278         /*
 279          * the string that gets passed to this function should look like this:
 280          *    s/match/replace/gIp
 281          *    ||     |        |||
 282          *    mandatory       optional
 283          *
 284          *    (all three of the '/' slashes are mandatory)
 285          */
 286         idx = parse_regex_delim(substr, &match, &sed_cmd->replace);
 287
 288         /* determine the number of back references in the match string */
 289         /* Note: we compute this here rather than in the do_subst_command()
 290          * function to save processor time, at the expense of a little more memory
 291          * (4 bits) per sed_cmd */
 292
 293         for (j = 0; match[j]; j++) {
 294                 /* GNU/POSIX sed does not save more than nine backrefs */
 295                 if (match[j] == '\\' && match[j + 1] == '('
 296                         && sed_cmd->num_backrefs <= 9)
 297                         sed_cmd->num_backrefs++;
 298         }
 299
 300         /* process the flags */
 301         while (substr[++idx]) {
 302                 switch (substr[idx]) {
 303                 case 'g':
 304                         if (match[0] != '^') {
 305                                 sed_cmd->sub_g = 1;
 306                         }
 307                         break;
 308                         /* Hmm, i dont see the I option mentioned in the standard */
 309                 case 'I':
 310                         cflags |= REG_ICASE;
 311                         break;
 312                 case 'p':
 313                         sed_cmd->sub_p = 1;
 314                         break;
 315                 default:
 316                         /* any whitespace or semicolon trailing after a s/// is ok */
 317                         if (strchr(semicolon_whitespace, substr[idx]))
 318                                 goto out;
 319                         /* else */
 320                         bb_error_msg_and_die("bad option in substitution expression");
 321                 }
 322         }
 323
 324   out:
 325         /* compile the match string into a regex */
 326         if (*match != '\0') {
 327                 /* If match is empty, we use last regex used at runtime */
 328                 sed_cmd->sub_match = (regex_t *) xmalloc(sizeof(regex_t));
 329                 xregcomp(sed_cmd->sub_match, match, cflags);
 330         }
 331         free(match);
 332
 333         return idx;
 334 }
 335
 336 static void replace_slash_n(char *string)
 337 {
 338         char *dest;
 339
 340         for (dest = string; *string; string++, dest++) {
 341                 if ((string[0] == '\\') && (string[1] == 'n')) {
 342                         *dest = '\n';
 343                         string++;
 344                 } else {
 345                         *dest = *string;
 346                 }
 347         }
 348         *dest=0;
 349 }
 350
 351 static int parse_translate_cmd(sed_cmd_t * const sed_cmd, const char *cmdstr)
 352 {
 353         char *match;
 354         char *replace;
 355         int idx;
 356         int i;
 357
 358         idx = parse_regex_delim(cmdstr, &match, &replace);
 359         replace_slash_n(match);
 360         replace_slash_n(replace);
 361         sed_cmd->translate = xcalloc(1, (strlen(match) + 1) * 2);
 362         for (i = 0; (match[i] != 0) && (replace[i] != 0); i++) {
 363                 sed_cmd->translate[i * 2] = match[i];
 364                 sed_cmd->translate[(i * 2) + 1] = replace[i];
 365         }
 366         return (idx + 1);
 367 }
 368
 369 static int parse_edit_cmd(sed_cmd_t * sed_cmd, const char *editstr)
 370 {
 371         int i, j;
 372
 373         /*
 374          * the string that gets passed to this function should look like this:
 375          *
 376          *    need one of these
 377          *    |
 378          *    |    this backslash (immediately following the edit command) is mandatory
 379          *    |    |
 380          *    [aic]\
 381          *    TEXT1\
 382          *    TEXT2\
 383          *    TEXTN
 384          *
 385          * as soon as we hit a TEXT line that has no trailing '\', we're done.
 386          * this means a command like:
 387          *
 388          * i\
 389          * INSERTME
 390          *
 391          * is a-ok.
 392          *
 393          */
 394         if ((*editstr != '\\') || ((editstr[1] != '\n') && (editstr[1] != '\r'))) {
 395                 bb_error_msg_and_die("bad format in edit expression");
 396         }
 397
 398         /* store the edit line text */
 399         sed_cmd->editline = xmalloc(strlen(&editstr[2]) + 2);
 400         for (i = 2, j = 0;
 401                 editstr[i] != '\0' && strchr("\r\n", editstr[i]) == NULL; i++, j++) {
 402                 if ((editstr[i] == '\\') && strchr("\n\r", editstr[i + 1]) != NULL) {
 403                         sed_cmd->editline[j] = '\n';
 404                         i++;
 405                 } else
 406                         sed_cmd->editline[j] = editstr[i];
 407         }
 408
 409         /* figure out if we need to add a newline */
 410         if (sed_cmd->editline[j - 1] != '\n')
 411                 sed_cmd->editline[j++] = '\n';
 412
 413         /* terminate string */
 414         sed_cmd->editline[j] = '\0';
 415
 416         return i;
 417 }
 418
 419
 420 static int parse_file_cmd(sed_cmd_t * sed_cmd, const char *filecmdstr)
 421 {
 422         int idx = 0;
 423         int filenamelen = 0;
 424
 425         /*
 426          * the string that gets passed to this function should look like this:
 427          *    '[ ]filename'
 428          *      |  |
 429          *      |  a filename
 430          *      |
 431          *     optional whitespace
 432
 433          *   re: the file to be read, the GNU manual says the following: "Note that
 434          *   if filename cannot be read, it is treated as if it were an empty file,
 435          *   without any error indication." Thus, all of the following commands are
 436          *   perfectly legal:
 437          *
 438          *   sed -e '1r noexist'
 439          *   sed -e '1r ;'
 440          *   sed -e '1r'
 441          */
 442
 443         /* the file command may be followed by whitespace; move past it. */
 444         while (isspace(filecmdstr[++idx])) {;
 445         }
 446
 447         /* the first non-whitespace we get is a filename. the filename ends when we
 448          * hit a normal sed command terminator or end of string */
 449         filenamelen = strcspn(&filecmdstr[idx], semicolon_whitespace);
 450         sed_cmd->filename = xmalloc(filenamelen + 1);
 451         safe_strncpy(sed_cmd->filename, &filecmdstr[idx], filenamelen + 1);
 452         return idx + filenamelen;
 453 }
 454
 455 /*
 456  *  Process the commands arguments
 457  */
 458 static char *parse_cmd_str(sed_cmd_t * sed_cmd, char *cmdstr)
 459 {
 460         /* handle (s)ubstitution command */
 461         if (sed_cmd->cmd == 's') {
 462                 cmdstr += parse_subst_cmd(sed_cmd, cmdstr);
 463         }
 464         /* handle edit cmds: (a)ppend, (i)nsert, and (c)hange */
 465         else if (strchr("aic", sed_cmd->cmd)) {
 466                 if ((sed_cmd->end_line || sed_cmd->end_match) && sed_cmd->cmd != 'c')
 467                         bb_error_msg_and_die
 468                                 ("only a beginning address can be specified for edit commands");
 469                 cmdstr += parse_edit_cmd(sed_cmd, cmdstr);
 470         }
 471         /* handle file cmds: (r)ead */
 472         else if (sed_cmd->cmd == 'r') {
 473                 if (sed_cmd->end_line || sed_cmd->end_match)
 474                         bb_error_msg_and_die("Command only uses one address");
 475                 cmdstr += parse_file_cmd(sed_cmd, cmdstr);
 476         }
 477         /* handle branch commands */
 478         else if (strchr(":bt", sed_cmd->cmd)) {
 479                 int length;
 480
 481                 cmdstr += strspn(cmdstr, " ");
 482                 length = strcspn(cmdstr, semicolon_whitespace);
 483                 if (length) {
 484                         sed_cmd->label = strndup(cmdstr, length);
 485                         cmdstr += length;
 486                 }
 487         }
 488         /* translation command */
 489         else if (sed_cmd->cmd == 'y') {
 490                 cmdstr += parse_translate_cmd(sed_cmd, cmdstr);
 491         }
 492         /* if it wasnt a single-letter command that takes no arguments
 493          * then it must be an invalid command.
 494          */
 495         else if (strchr("dgGhHnNpPqx={}", sed_cmd->cmd) == 0) {
 496                 bb_error_msg_and_die("Unsupported command %c", sed_cmd->cmd);
 497         }
 498
 499         /* give back whatever's left over */
 500         return (cmdstr);
 501 }
 502
 503 static char *add_cmd(char *cmdstr)
 504 {
 505         sed_cmd_t *sed_cmd;
 506
 507         /* Skip over leading whitespace and semicolons */
 508         cmdstr += strspn(cmdstr, semicolon_whitespace);
 509
 510         /* if we ate the whole thing, that means there was just trailing
 511          * whitespace or a final / no-op semicolon. either way, get out */
 512         if (*cmdstr == '\0') {
 513                 return (NULL);
 514         }
 515
 516         /* if this is a comment, jump past it and keep going */
 517         if (*cmdstr == '#') {
 518                 /* "#n" is the same as using -n on the command line */
 519                 if (cmdstr[1] == 'n') {
 520                         be_quiet++;
 521                 }
 522                 return (strpbrk(cmdstr, "\n\r"));
 523         }
 524
 525         /* parse the command
 526          * format is: [addr][,addr]cmd
 527          *            |----||-----||-|
 528          *            part1 part2  part3
 529          */
 530
 531         sed_cmd = xcalloc(1, sizeof(sed_cmd_t));
 532
 533         /* first part (if present) is an address: either a '$', a number or a /regex/ */
 534         cmdstr += get_address(cmdstr, &sed_cmd->beg_line, &sed_cmd->beg_match);
 535
 536         /* second part (if present) will begin with a comma */
 537         if (*cmdstr == ',') {
 538                 int idx;
 539
 540                 cmdstr++;
 541                 idx = get_address(cmdstr, &sed_cmd->end_line, &sed_cmd->end_match);
 542                 if (idx == 0) {
 543                         bb_error_msg_and_die("get_address: no address found in string\n"
 544                                 "\t(you probably didn't check the string you passed me)");
 545                 }
 546                 cmdstr += idx;
 547         }
 548
 549         /* skip whitespace before the command */
 550         while (isspace(*cmdstr)) {
 551                 cmdstr++;
 552         }
 553
 554         /* there my be the inversion flag between part2 and part3 */
 555         if (*cmdstr == '!') {
 556                 sed_cmd->invert = 1;
 557                 cmdstr++;
 558
 559 #ifdef SED_FEATURE_STRICT_CHECKING
 560                 /* According to the spec
 561                  * It is unspecified whether <blank>s can follow a '!' character,
 562                  * and conforming applications shall not follow a '!' character
 563                  * with <blank>s.
 564                  */
 565                 if (isblank(cmdstr[idx]) {
 566                         bb_error_msg_and_die("blank follows '!'");}
 567 #else
 568                 /* skip whitespace before the command */
 569                 while (isspace(*cmdstr)) {
 570                         cmdstr++;
 571                 }
 572 #endif
 573         }
 574
 575         /* last part (mandatory) will be a command */
 576         if (*cmdstr == '\0')
 577                 bb_error_msg_and_die("missing command");
 578
 579         sed_cmd->cmd = *cmdstr;
 580         cmdstr++;
 581
 582         cmdstr = parse_cmd_str(sed_cmd, cmdstr);
 583
 584         /* Add the command to the command array */
 585         sed_cmd_tail->next = sed_cmd;
 586         sed_cmd_tail = sed_cmd_tail->next;
 587
 588         return (cmdstr);
 589 }
 590
 591 static void add_cmd_str(char *cmdstr)
 592 {
 593 #ifdef CONFIG_FEATURE_SED_EMBEDED_NEWLINE
 594         char *cmdstr_ptr = cmdstr;
 595
 596         /* HACK: convert "\n" to match tranlated '\n' string */
 597         while ((cmdstr_ptr = strstr(cmdstr_ptr, "\\n")) != NULL) {
 598                 cmdstr = xrealloc(cmdstr, strlen(cmdstr) + 2);
 599                 cmdstr_ptr = strstr(cmdstr, "\\n");
 600                 memmove(cmdstr_ptr + 1, cmdstr_ptr, strlen(cmdstr_ptr) + 1);
 601                 cmdstr_ptr[0] = '\\';
 602                 cmdstr_ptr += 3;
 603         }
 604 #endif
 605         do {
 606                 cmdstr = add_cmd(cmdstr);
 607         } while (cmdstr && strlen(cmdstr));
 608 }
 609
 610
 611 static void load_cmd_file(char *filename)
 612 {
 613         FILE *cmdfile;
 614         char *line;
 615         char *nextline;
 616         char *e;
 617
 618         cmdfile = bb_xfopen(filename, "r");
 619
 620         while ((line = bb_get_line_from_file(cmdfile)) != NULL) {
 621                 /* if a line ends with '\' it needs the next line appended to it */
 622                 while (((e = last_char_is(line, '\n')) != NULL)
 623                         && (e > line) && (e[-1] == '\\')
 624                         && ((nextline = bb_get_line_from_file(cmdfile)) != NULL)) {
 625                         line = xrealloc(line, (e - line) + 1 + strlen(nextline) + 1);
 626                         strcat(line, nextline);
 627                         free(nextline);
 628                 }
 629                 /* eat trailing newline (if any) --if I don't do this, edit commands
 630                  * (aic) will print an extra newline */
 631                 chomp(line);
 632                 add_cmd_str(line);
 633                 free(line);
 634         }
 635 }
 636
 637 struct pipeline {
 638         char *buf;
 639         int idx;
 640         int len;
 641 };
 642
 643 #define PIPE_MAGIC 0x7f
 644 #define PIPE_GROW 64
 645
 646 void pipe_putc(struct pipeline *const pipeline, char c)
 647 {
 648         if (pipeline->buf[pipeline->idx] == PIPE_MAGIC) {
 649                 pipeline->buf = xrealloc(pipeline->buf, pipeline->len + PIPE_GROW);
 650                 memset(pipeline->buf + pipeline->len, 0, PIPE_GROW);
 651                 pipeline->len += PIPE_GROW;
 652                 pipeline->buf[pipeline->len - 1] = PIPE_MAGIC;
 653         }
 654         pipeline->buf[pipeline->idx++] = (c);
 655 }
 656
 657 #define pipeputc(c)     pipe_putc(pipeline, c)
 658
 659 static void print_subst_w_backrefs(const char *line, const char *replace,
 660         regmatch_t * regmatch, struct pipeline *const pipeline, int matches)
 661 {
 662         int i;
 663
 664         /* go through the replacement string */
 665         for (i = 0; replace[i]; i++) {
 666                 /* if we find a backreference (\1, \2, etc.) print the backref'ed * text */
 667                 if (replace[i] == '\\' && isdigit(replace[i + 1])) {
 668                         int j;
 669                         char tmpstr[2];
 670                         int backref;
 671
 672                         ++i;            /* i now indexes the backref number, instead of the leading slash */
 673                         tmpstr[0] = replace[i];
 674                         tmpstr[1] = 0;
 675                         backref = atoi(tmpstr);
 676                         /* print out the text held in regmatch[backref] */
 677                         if (backref <= matches && regmatch[backref].rm_so != -1)
 678                                 for (j = regmatch[backref].rm_so; j < regmatch[backref].rm_eo;
 679                                         j++)
 680                                         pipeputc(line[j]);
 681                 }
 682
 683                 /* if we find a backslash escaped character, print the character */
 684                 else if (replace[i] == '\\') {
 685                         ++i;
 686                         pipeputc(replace[i]);
 687                 }
 688
 689                 /* if we find an unescaped '&' print out the whole matched text.
 690                  * fortunately, regmatch[0] contains the indicies to the whole matched
 691                  * expression (kinda seems like it was designed for just such a
 692                  * purpose...) */
 693                 else if (replace[i] == '&') {
 694                         int j;
 695
 696                         for (j = regmatch[0].rm_so; j < regmatch[0].rm_eo; j++)
 697                                 pipeputc(line[j]);
 698                 }
 699                 /* nothing special, just print this char of the replacement string to stdout */
 700                 else
 701                         pipeputc(replace[i]);
 702         }
 703 }
 704
 705 static int do_subst_command(sed_cmd_t * sed_cmd, char **line)
 706 {
 707         char *hackline = *line;
 708         struct pipeline thepipe = { NULL, 0, 0 };
 709         struct pipeline *const pipeline = &thepipe;
 710         int altered = 0;
 711         int result;
 712         regmatch_t *regmatch = NULL;
 713         regex_t *current_regex;
 714
 715         if (sed_cmd->sub_match == NULL) {
 716                 current_regex = previous_regex_ptr;
 717         } else {
 718                 previous_regex_ptr = current_regex = sed_cmd->sub_match;
 719         }
 720         result = regexec(current_regex, hackline, 0, NULL, 0);
 721
 722         /* we only proceed if the substitution 'search' expression matches */
 723         if (result == REG_NOMATCH) {
 724                 return 0;
 725         }
 726
 727         /* whaddaya know, it matched. get the number of back references */
 728         regmatch = xmalloc(sizeof(regmatch_t) * (sed_cmd->num_backrefs + 1));
 729
 730         /* allocate more PIPE_GROW bytes
 731            if replaced string is larger than original */
 732         thepipe.len = strlen(hackline) + PIPE_GROW;
 733         thepipe.buf = xcalloc(1, thepipe.len);
 734         /* buffer magic */
 735         thepipe.buf[thepipe.len - 1] = PIPE_MAGIC;
 736
 737         /* and now, as long as we've got a line to try matching and if we can match
 738          * the search string, we make substitutions */
 739         while ((*hackline || !altered)
 740                 && (regexec(current_regex, hackline, sed_cmd->num_backrefs + 1,
 741                                 regmatch, 0) != REG_NOMATCH)) {
 742                 int i;
 743
 744                 /* print everything before the match */
 745                 for (i = 0; i < regmatch[0].rm_so; i++)
 746                         pipeputc(hackline[i]);
 747
 748                 /* then print the substitution string */
 749                 print_subst_w_backrefs(hackline, sed_cmd->replace, regmatch, pipeline,
 750                         sed_cmd->num_backrefs);
 751
 752                 /* advance past the match */
 753                 hackline += regmatch[0].rm_eo;
 754                 /* flag that something has changed */
 755                 altered++;
 756
 757                 /* if we're not doing this globally, get out now */
 758                 if (!sed_cmd->sub_g) {
 759                         break;
 760                 }
 761         }
 762         for (; *hackline; hackline++)
 763                 pipeputc(*hackline);
 764         if (thepipe.buf[thepipe.idx] == PIPE_MAGIC)
 765                 thepipe.buf[thepipe.idx] = 0;
 766
 767         /* cleanup */
 768         free(regmatch);
 769
 770         free(*line);
 771         *line = thepipe.buf;
 772         return altered;
 773 }
 774
 775 static sed_cmd_t *branch_to(const char *label)
 776 {
 777         sed_cmd_t *sed_cmd;
 778
 779         for (sed_cmd = sed_cmd_head.next; sed_cmd; sed_cmd = sed_cmd->next) {
 780                 if ((sed_cmd->cmd == ':') && (sed_cmd->label) && (strcmp(sed_cmd->label, label) == 0)) {
 781                         return (sed_cmd);
 782                 }
 783         }
 784         bb_error_msg_and_die("Can't find label for jump to `%s'", label);
 785 }
 786
 787 static void process_file(FILE * file)
 788 {
 789         char *pattern_space;    /* Posix requires it be able to hold at least 8192 bytes */
 790         char *hold_space = NULL;        /* Posix requires it be able to hold at least 8192 bytes */
 791         static int linenum = 0; /* GNU sed does not restart counting lines at EOF */
 792         int altered;
 793         int force_print;
 794
 795         pattern_space = bb_get_chomped_line_from_file(file);
 796         if (pattern_space == NULL) {
 797                 return;
 798         }
 799
 800         /* go through every line in the file */
 801         do {
 802                 char *next_line;
 803                 sed_cmd_t *sed_cmd;
 804                 int substituted = 0;
 805                 /* This enables whole blocks of commands to be mask'ed out if the lead address doesnt match */
 806                 int block_mask = 1;
 807
 808                 /* Read one line in advance so we can act on the last line, the '$' address */
 809                 next_line = bb_get_chomped_line_from_file(file);
 810                 linenum++;
 811                 altered = 0;
 812                 force_print = 0;
 813
 814                 /* for every line, go through all the commands */
 815                 for (sed_cmd = sed_cmd_head.next; sed_cmd; sed_cmd = sed_cmd->next) {
 816                         int deleted = 0;
 817
 818                         /*
 819                          * entry point into sedding...
 820                          */
 821                         int matched = (
 822                                 /* no range necessary */
 823                                 (sed_cmd->beg_line == 0 && sed_cmd->end_line == 0
 824                                         && sed_cmd->beg_match == NULL
 825                                         && sed_cmd->end_match == NULL) ||
 826                                 /* this line number is the first address we're looking for */
 827                                 (sed_cmd->beg_line > 0 && (sed_cmd->beg_line == linenum)) ||
 828                                 /* this line matches our first address regex */
 829                                 (sed_cmd->beg_match
 830                                         && (regexec(sed_cmd->beg_match, pattern_space, 0, NULL,
 831                                                         0) == 0)) ||
 832                                 /* we are currently within the beginning & ending address range */
 833                                 sed_cmd->still_in_range || ((sed_cmd->beg_line == -1)
 834                                         && (next_line == NULL))
 835                                 );
 836                         if (sed_cmd->cmd == '{') {
 837                                 block_mask = block_mask & matched;
 838                         }
 839 //                      matched &= block_mask;
 840
 841                         if (sed_cmd->invert ^ (matched & block_mask)) {
 842                                 /* Update last used regex incase a blank substitute BRE is found */
 843                                 if (sed_cmd->beg_match) {
 844                                         previous_regex_ptr = sed_cmd->beg_match;
 845                                 }
 846
 847                                 /*
 848                                  * actual sedding
 849                                  */
 850                                 switch (sed_cmd->cmd) {
 851                                 case '=':
 852                                         printf("%d\n", linenum);
 853                                         break;
 854                                 case 'P':{
 855                                         /* Write the current pattern space upto the first newline */
 856                                         char *tmp = strchr(pattern_space, '\n');
 857
 858                                         if (tmp) {
 859                                                 *tmp = '\0';
 860                                         }
 861                                 }
 862                                 case 'p':       /* Write the current pattern space to output */
 863                                         puts(pattern_space);
 864                                         break;
 865                                 case 'd':
 866                                         altered++;
 867                                         deleted = 1;
 868                                         force_print = 0;
 869                                         break;
 870
 871                                 case 's':
 872
 873                                         /*
 874                                          * Some special cases for 's' printing to make it compliant with
 875                                          * GNU sed printing behavior (aka "The -n | s///p Matrix"):
 876                                          *
 877                                          *    -n ONLY = never print anything regardless of any successful
 878                                          *    substitution
 879                                          *
 880                                          *    s///p ONLY = always print successful substitutions, even if
 881                                          *    the pattern_space is going to be printed anyway (pattern_space
 882                                          *    will be printed twice).
 883                                          *
 884                                          *    -n AND s///p = print ONLY a successful substitution ONE TIME;
 885                                          *    no other lines are printed - this is the reason why the 'p'
 886                                          *    flag exists in the first place.
 887                                          */
 888
 889 #ifdef CONFIG_FEATURE_SED_EMBEDED_NEWLINE
 890                                         /* HACK: escape newlines twice so regex can match them */
 891                                 {
 892                                         int offset = 0;
 893
 894                                         while (strchr(pattern_space + offset, '\n') != NULL) {
 895                                                 char *tmp;
 896
 897                                                 pattern_space =
 898                                                         xrealloc(pattern_space,
 899                                                         strlen(pattern_space) + 2);
 900                                                 tmp = strchr(pattern_space + offset, '\n');
 901                                                 memmove(tmp + 1, tmp, strlen(tmp) + 1);
 902                                                 tmp[0] = '\\';
 903                                                 tmp[1] = 'n';
 904                                                 offset = tmp - pattern_space + 2;
 905                                         }
 906                                 }
 907 #endif
 908                                         /* we print the pattern_space once, unless we were told to be quiet */
 909                                         substituted |= do_subst_command(sed_cmd, &pattern_space);
 910
 911 #ifdef CONFIG_FEATURE_SED_EMBEDED_NEWLINE
 912                                         /* undo HACK: escape newlines twice so regex can match them */
 913                                         {
 914                                                 char *tmp = pattern_space;
 915
 916                                                 while ((tmp = strstr(tmp, "\\n")) != NULL) {
 917                                                         memmove(tmp, tmp + 1, strlen(tmp + 1) + 1);
 918                                                         tmp[0] = '\n';
 919                                                 }
 920                                         }
 921 #endif
 922                                         if (!be_quiet && substituted && ((sed_cmd->next == NULL)
 923                                                         || (sed_cmd->next->cmd != 's'))) {
 924                                                 force_print = 1;
 925                                         }
 926
 927                                         /* we also print the line if we were given the 'p' flag
 928                                          * (this is quite possibly the second printing) */
 929                                         if ((sed_cmd->sub_p) && altered) {
 930                                                 puts(pattern_space);
 931                                         }
 932                                         break;
 933                                 case 'a':
 934                                         puts(pattern_space);
 935                                         fputs(sed_cmd->editline, stdout);
 936                                         altered++;
 937                                         break;
 938
 939                                 case 'i':
 940                                         fputs(sed_cmd->editline, stdout);
 941                                         break;
 942
 943                                 case 'c':
 944                                         /* single-address case */
 945                                         if ((sed_cmd->end_match == NULL && sed_cmd->end_line == 0)
 946                                                 /* multi-address case */
 947                                                 /* - matching text */
 948                                                 || (sed_cmd->end_match
 949                                                         && (regexec(sed_cmd->end_match, pattern_space, 0,
 950                                                                         NULL, 0) == 0))
 951                                                 /* - matching line numbers */
 952                                                 || (sed_cmd->end_line > 0
 953                                                         && sed_cmd->end_line == linenum)) {
 954                                                 fputs(sed_cmd->editline, stdout);
 955                                         }
 956                                         altered++;
 957
 958                                         break;
 959
 960                                 case 'r':{
 961                                         FILE *outfile;
 962
 963                                         outfile = fopen(sed_cmd->filename, "r");
 964                                         if (outfile) {
 965                                                 char *line;
 966
 967                                                 while ((line =
 968                                                                 bb_get_chomped_line_from_file(outfile)) !=
 969                                                         NULL) {
 970                                                         pattern_space =
 971                                                                 xrealloc(pattern_space,
 972                                                                 strlen(line) + strlen(pattern_space) + 2);
 973                                                         strcat(pattern_space, "\n");
 974                                                         strcat(pattern_space, line);
 975                                                 }
 976                                                 bb_xprint_and_close_file(outfile);
 977                                         }
 978
 979                                 }
 980                                         break;
 981                                 case 'q':       /* Branch to end of script and quit */
 982                                         deleted = 1;
 983                                         /* Exit the outer while loop */
 984                                         free(next_line);
 985                                         next_line = NULL;
 986                                         break;
 987                                 case 'n':       /* Read next line from input */
 988                                         if (next_line) {
 989                                                 free(pattern_space);
 990                                                 pattern_space = next_line;
 991                                                 next_line = bb_get_chomped_line_from_file(file);
 992                                                 linenum++;
 993                                         }
 994                                         break;
 995                                 case 'N':       /* Append the next line to the current line */
 996                                         if (next_line) {
 997                                                 pattern_space =
 998                                                         realloc(pattern_space,
 999                                                         strlen(pattern_space) + strlen(next_line) + 2);
1000                                                 strcat(pattern_space, "\n");
1001                                                 strcat(pattern_space, next_line);
1002                                                 next_line = bb_get_chomped_line_from_file(file);
1003                                                 linenum++;
1004                                         }
1005                                         break;
1006                                 case 't':
1007                                         if (substituted)
1008                                                 /* Fall through */
1009                                 case 'b':
1010                                         {
1011                                                 if (sed_cmd->label == NULL) {
1012                                                         /* Jump to end of script */
1013                                                         deleted = 1;
1014                                                 } else {
1015                                                         sed_cmd = branch_to(sed_cmd->label);
1016                                                 }
1017                                         }
1018                                         break;
1019                                 case 'y':{
1020                                         int i;
1021
1022                                         for (i = 0; pattern_space[i] != 0; i++) {
1023                                                 int j;
1024
1025                                                 for (j = 0; sed_cmd->translate[j]; j += 2) {
1026                                                         if (pattern_space[i] == sed_cmd->translate[j]) {
1027                                                                 pattern_space[i] = sed_cmd->translate[j + 1];
1028                                                         }
1029                                                 }
1030                                         }
1031                                 }
1032                                         break;
1033                                 case 'g':       /* Replace pattern space with hold space */
1034                                         free(pattern_space);
1035                                         if (hold_space) {
1036                                                 pattern_space = strdup(hold_space);
1037                                         }
1038                                         break;
1039                                 case 'G': {     /* Append newline and hold space to pattern space */
1040                                         int pattern_space_size = 2;
1041                                         int hold_space_size = 0;
1042
1043                                         if (pattern_space) {
1044                                                 pattern_space_size += strlen(pattern_space);
1045                                         }
1046                                         if (hold_space) {
1047                                                 hold_space_size = strlen(hold_space);
1048                                         }
1049                                         pattern_space = xrealloc(pattern_space, pattern_space_size + hold_space_size);
1050                                         if (pattern_space_size == 2) {
1051                                                 strcat(pattern_space, "\n");
1052                                         } else {
1053                                                 strcpy(pattern_space, "\n");
1054                                         }
1055                                         if (hold_space) {
1056                                                 strcat(pattern_space, hold_space);
1057                                         }
1058                                         break;
1059                                 }
1060                                 case 'h':       /* Replace hold space with pattern space */
1061                                         free(hold_space);
1062                                         hold_space = strdup(pattern_space);
1063                                         break;
1064                                 case 'H': {     /* Append newline and pattern space to hold space */
1065                                         int hold_space_size = 2;
1066                                         int pattern_space_size = 0;
1067
1068                                         if (hold_space) {
1069                                                 hold_space_size += strlen(hold_space);
1070                                         }
1071                                         if (pattern_space) {
1072                                                 pattern_space_size = strlen(pattern_space);
1073                                         }
1074                                         hold_space = xrealloc(hold_space, hold_space_size + pattern_space_size);
1075
1076                                         if (hold_space_size == 2) {
1077                                                 strcpy(hold_space, "\n");
1078                                         } else {
1079                                                 strcat(hold_space, "\n");
1080                                         }
1081                                         if (pattern_space) {
1082                                                 strcat(hold_space, pattern_space);
1083                                         }
1084                                         break;
1085                                 }
1086                                 case 'x':{
1087                                         /* Swap hold and pattern space */
1088                                         char *tmp = pattern_space;
1089                                         pattern_space = hold_space;
1090                                         hold_space = tmp;
1091                                         break;
1092                                 }
1093                                 }
1094                         }
1095
1096                         /*
1097                          * exit point from sedding...
1098                          */
1099                         if (matched) {
1100                                 if (
1101                                         /* this is a single-address command or... */
1102                                         (sed_cmd->end_line == 0 && sed_cmd->end_match == NULL)
1103                                         /* If only one address */
1104                                         /* we were in the middle of our address range (this
1105                                          * isn't the first time through) and.. */
1106                                         || ((sed_cmd->still_in_range == 1)
1107                                                 /* this line number is the last address we're looking for or... */
1108                                                 && ((sed_cmd->end_line > 0
1109                                                                 && (sed_cmd->end_line == linenum))
1110                                                         /* this line matches our last address regex */
1111                                                         || (sed_cmd->end_match
1112                                                                 && (regexec(sed_cmd->end_match, pattern_space,
1113                                                                                 0, NULL, 0) == 0))))) {
1114                                         /* we're out of our address range */
1115                                         sed_cmd->still_in_range = 0;
1116                                 } else {
1117                                         /* didn't hit the exit? then we're still in the middle of an address range */
1118                                         sed_cmd->still_in_range = 1;
1119                                 }
1120                         }
1121
1122                         if (sed_cmd->cmd == '}') {
1123                                 block_mask = 1;
1124                         }
1125
1126                         if (deleted)
1127                                 break;
1128
1129                 }
1130
1131                 /* we will print the line unless we were told to be quiet or if the
1132                  * line was altered (via a 'd'elete or 's'ubstitution), in which case
1133                  * the altered line was already printed */
1134                 if ((!be_quiet && !altered && !substituted) || force_print) {
1135                         puts(pattern_space);
1136                 }
1137                 free(pattern_space);
1138                 pattern_space = next_line;
1139         } while (pattern_space);
1140 }
1141
1142 extern int sed_main(int argc, char **argv)
1143 {
1144         int opt, status = EXIT_SUCCESS;
1145
1146 #if 0 /* This doesnt seem to be working */
1147 #ifdef CONFIG_FEATURE_CLEAN_UP
1148         /* destroy command strings on exit */
1149         if (atexit(destroy_cmd_strs) == -1)
1150                 bb_perror_msg_and_die("atexit");
1151 #endif
1152 #endif
1153
1154         /* do normal option parsing */
1155         while ((opt = getopt(argc, argv, "ne:f:")) > 0) {
1156                 switch (opt) {
1157                 case 'n':
1158                         be_quiet++;
1159                         break;
1160                 case 'e':{
1161                         add_cmd_str(optarg);
1162                         break;
1163                 }
1164                 case 'f':
1165                         load_cmd_file(optarg);
1166                         break;
1167                 default:
1168                         bb_show_usage();
1169                 }
1170         }
1171
1172         /* if we didn't get a pattern from a -e and no command file was specified,
1173          * argv[optind] should be the pattern. no pattern, no worky */
1174         if (sed_cmd_head.next == NULL) {
1175                 if (argv[optind] == NULL)
1176                         bb_show_usage();
1177                 else
1178                         add_cmd_str(argv[optind++]);
1179         }
1180
1181         /* argv[(optind)..(argc-1)] should be names of file to process. If no
1182          * files were specified or '-' was specified, take input from stdin.
1183          * Otherwise, we process all the files specified. */
1184         if (argv[optind] == NULL) {
1185                 process_file(stdin);
1186         } else {
1187                 int i;
1188                 FILE *file;
1189
1190                 for (i = optind; i < argc; i++) {
1191                         if(!strcmp(argv[i], "-")) {
1192                                 process_file(stdin);
1193                         } else {
1194                                 file = bb_wfopen(argv[i], "r");
1195                                 if (file) {
1196                                         process_file(file);
1197                                         fclose(file);
1198                                 } else {
1199                                         status = EXIT_FAILURE;
1200                                 }
1201                         }
1202                 }
1203         }
1204
1205 #ifdef CONFIG_FEATURE_CLEAN_UP
1206         destroy_cmd_strs();
1207 #endif
1208         return status;
1209 }