parse.c

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