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