parse.c

   1 /*
   2  * wiggle - apply rejected patches
   3  *
   4  * Copyright (C) 2003-2013 Neil Brown <neilb@suse.de>
   5  * Copyright (C) 2014-2020 Neil Brown <neil@brown.name>
   6  *
   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
  16  *    GNU 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.
  20  *
  21  *    Author: Neil Brown
  22  *    Email: <neil@brown.name>
  23  */
  24
  25 /*
  26  * Parse a patch file to find the names of the different
  27  * files to patch and record which parts of the patch
  28  * file applies to which target file.
  29  */
  30
  31 #include        "wiggle.h"
  32 #include        <unistd.h>
  33 #include        <fcntl.h>
  34
  35 /* determine how much we need to stripe of the front of
  36  * paths to find them from current directory.  This is
  37  * used to guess correct '-p' value.
  38  */
  39 static int get_strip(char *file)
  40 {
  41         int fd;
  42         int strip = 0;
  43
  44         while (file && *file) {
  45                 fd  = open(file, O_RDONLY);
  46                 if (fd >= 0) {
  47                         close(fd);
  48                         return strip;
  49                 }
  50                 strip++;
  51                 file = strchr(file, '/');
  52                 if (file)
  53                         while (*file == '/')
  54                                 file++;
  55         }
  56         return -1;
  57
  58 }
  59
  60 int wiggle_set_prefix(struct plist *pl, int n, int strip)
  61 {
  62         int i;
  63         for (i = 0; i < 4 && i < n  && strip < 0; i++)
  64                 strip = get_strip(pl[i].file);
  65
  66         if (strip < 0) {
  67                 fprintf(stderr, "%s: Cannot find files to patch: please specify --strip\n",
  68                         wiggle_Cmd);
  69                 return 0;
  70         }
  71         for (i = 0; i < n; i++) {
  72                 char *p = pl[i].file;
  73                 int j;
  74                 for (j = 0; j < strip; j++) {
  75                         if (p)
  76                                 p = strchr(p, '/');
  77                         while (p && *p == '/')
  78                                 p++;
  79                 }
  80                 if (p == NULL) {
  81                         fprintf(stderr, "%s: cannot strip %d segments from %s\n",
  82                                 wiggle_Cmd, strip, pl[i].file);
  83                         return 0;
  84                 }
  85                 memmove(pl[i].file, p, strlen(p)+1);
  86         }
  87         return 1;
  88 }
  89
  90 static int pl_cmp(const void *av, const void *bv)
  91 {
  92         const struct plist *a = av;
  93         const struct plist *b = bv;
  94         return strcmp(a->file, b->file);
  95 }
  96
  97 static int common_depth(char *a, char *b)
  98 {
  99         /* find number of path segments that these two have
 100          * in common
 101          */
 102         int depth = 0;
 103         while (1) {
 104                 char *c;
 105                 int al, bl;
 106                 c = strchr(a, '/');
 107                 if (c)
 108                         al = c-a;
 109                 else
 110                         al = strlen(a);
 111                 c = strchr(b, '/');
 112                 if (c)
 113                         bl = c-b;
 114                 else
 115                         bl = strlen(b);
 116                 if (al == 0 || al != bl || strncmp(a, b, al) != 0)
 117                         return depth;
 118                 a += al;
 119                 while (*a == '/')
 120                         a++;
 121                 b += bl;
 122                 while (*b == '/')
 123                         b++;
 124
 125                 depth++;
 126         }
 127 }
 128
 129 static struct plist *patch_add_file(struct plist *pl, int *np, char *file,
 130                                     unsigned int start, unsigned int end)
 131 {
 132         /* size of pl is 0, 16, n^2 */
 133         int n = *np;
 134         int asize;
 135
 136         while (*file == '/')
 137                 /* leading '/' are bad... */
 138                 memmove(file, file+1, strlen(file));
 139
 140         if (n == 0)
 141                 asize = 0;
 142         else if (n <= 16)
 143                 asize = 16;
 144         else if ((n&(n-1)) == 0)
 145                 asize = n;
 146         else
 147                 asize = n+1; /* not accurate, but not too large */
 148         if (asize <= n) {
 149                 /* need to extend array */
 150                 struct plist *npl;
 151                 if (asize < 16)
 152                         asize = 16;
 153                 else
 154                         asize += asize;
 155                 npl = realloc(pl, asize * sizeof(struct plist));
 156                 if (!npl) {
 157                         fprintf(stderr, "realloc failed - skipping %s\n", file);
 158                         return pl;
 159                 }
 160                 pl = npl;
 161         }
 162         memset(&pl[n], 0, sizeof(pl[n]));
 163         pl[n].file = file;
 164         pl[n].start = start;
 165         pl[n].end = end;
 166         pl[n].last = pl[n].next = pl[n].prev = pl[n].parent = -1;
 167         pl[n].conflicts = 100;
 168         pl[n].open = 1;
 169         *np = n+1;
 170         return pl;
 171 }
 172
 173 static struct plist *add_dir(struct plist *pl, int *np, char *file, char *curr)
 174 {
 175         /* any parent of file that is not a parent of curr
 176          * needs to be added to pl
 177          */
 178         int d = common_depth(file, curr);
 179         char *buf = curr;
 180         while (d) {
 181                 char *c = strchr(file, '/');
 182                 int l;
 183                 if (c)
 184                         l = c-file;
 185                 else
 186                         l = strlen(file);
 187                 file += l;
 188                 curr += l;
 189                 while (*file == '/')
 190                         file++;
 191                 while (*curr == '/')
 192                         curr++;
 193                 d--;
 194         }
 195         while (*file) {
 196                 if (curr > buf && curr[-1] != '/')
 197                         *curr++ = '/';
 198                 while (*file && *file != '/')
 199                         *curr++ = *file++;
 200                 while (*file == '/')
 201                         file++;
 202                 *curr = '\0';
 203                 if (*file)
 204                         pl = patch_add_file(pl, np, strdup(buf),
 205                                             0, 0);
 206         }
 207         return pl;
 208 }
 209
 210 struct plist *wiggle_sort_patches(struct plist *pl, int *np)
 211 {
 212         /* sort the patches, add directory names, and re-sort */
 213         char curr[1024];
 214         char *prev;
 215         int parents[100];
 216         int prevnode[100];
 217         int i, n;
 218         qsort(pl, *np, sizeof(struct plist), pl_cmp);
 219         curr[0] = 0;
 220         n = *np;
 221         for (i = 0; i < n; i++)
 222                 pl = add_dir(pl, np, pl[i].file, curr);
 223
 224         qsort(pl, *np, sizeof(struct plist), pl_cmp);
 225
 226         /* array is now stable, so set up parent pointers */
 227         n = *np;
 228         curr[0] = 0;
 229         prevnode[0] = -1;
 230         prev = "";
 231         for (i = 0; i < n; i++) {
 232                 int d = common_depth(prev, pl[i].file);
 233                 if (d == 0)
 234                         pl[i].parent = -1;
 235                 else {
 236                         pl[i].parent = parents[d-1];
 237                         pl[pl[i].parent].last = i;
 238                 }
 239                 pl[i].prev = prevnode[d];
 240                 if (pl[i].prev > -1)
 241                         pl[pl[i].prev].next = i;
 242                 prev = pl[i].file;
 243                 parents[d] = i;
 244                 prevnode[d] = i;
 245                 prevnode[d+1] = -1;
 246         }
 247         return pl;
 248 }
 249
 250 struct plist *wiggle_parse_patch(FILE *f, FILE *of, int *np)
 251 {
 252         /* read a multi-file patch from 'f' and record relevant
 253          * details in a plist.
 254          * if 'of' >= 0, fd might not be seekable so we write
 255          * to 'of' and use lseek on 'of' to determine position
 256          */
 257         struct plist *plist = NULL;
 258
 259         *np = 0;
 260         while (!feof(f)) {
 261                 /* first, find the start of a patch: "\n+++ "
 262                  * grab the file name and scan to the end of a line
 263                  */
 264                 char *target = "\n+++ ";
 265                 char *target2 = "\n--- ";
 266                 char *pos = target;
 267                 int c = EOF;
 268                 char name[1024];
 269                 unsigned start, end;
 270
 271                 while (*pos && (c = fgetc(f)) != EOF) {
 272                         if (of)
 273                                 fputc(c, of);
 274                         if (c == *pos)
 275                                 pos++;
 276                         else
 277                                 pos = target;
 278                 }
 279                 if (c == EOF)
 280                         break;
 281                 assert(c == ' ');
 282                 /* now read a file name */
 283                 pos = name;
 284                 while ((c = fgetc(f)) != EOF
 285                        && c != '\t' && c != '\n' && c != ' ' &&
 286                        pos - name < 1023) {
 287                         *pos++ = c;
 288                         if (of)
 289                                 fputc(c, of);
 290                 }
 291                 *pos = 0;
 292                 if (c == EOF)
 293                         break;
 294                 if (of)
 295                         fputc(c, of);
 296                 while (c != '\n' && (c = fgetc(f)) != EOF)
 297                         if (of)
 298                                 fputc(c, of);
 299
 300                 start = ftell(of ? of : f);
 301
 302                 if (c == EOF)
 303                         break;
 304
 305                 /* now skip to end - "\n--- " */
 306                 pos = target2+1;
 307
 308                 while (*pos && (c = fgetc(f)) != EOF) {
 309                         if (of)
 310                                 fputc(c, of);
 311                         if (c == *pos)
 312                                 pos++;
 313                         else
 314                                 pos = target2;
 315                 }
 316                 end = ftell(of ? of : f);
 317                 if (pos > target2)
 318                         end -= (pos - target2) - 1;
 319                 plist = patch_add_file(plist, np,
 320                                        strdup(name), start, end);
 321         }
 322         return plist;
 323 }
 324
 325 void wiggle_plist_free(struct plist *pl, int num)
 326 {
 327         int i;
 328         for (i = 0; i < num ; i++)
 329                 free(pl[i].file);
 330         free(pl);
 331 }