parse.c

   1 /*
   2  * wiggle - apply rejected patches
   3  *
   4  * Copyright (C) 2003-2012 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; if not, write to the Free Software Foundation, Inc.,
  19  *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  *    Author: Neil Brown
  22  *    Email: <neilb@suse.de>
  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 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                         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                                 Cmd, strip, pl[i].file);
  83                         return 0;
  84                 }
  85                 pl[i].file = p;
  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                 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         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].chunks = pl[n].wiggles = 0; pl[n].conflicts = 100;
 167         pl[n].open = 1;
 168         pl[n].calced = 0;
 169         pl[n].is_merge = 0;
 170         *np = n+1;
 171         return pl;
 172 }
 173
 174 static struct plist *add_dir(struct plist *pl, int *np, char *file, char *curr)
 175 {
 176         /* any parent of file that is not a parent of curr
 177          * needs to be added to pl
 178          */
 179         int d = common_depth(file, curr);
 180         char *buf = curr;
 181         while (d) {
 182                 char *c = strchr(file, '/');
 183                 int l;
 184                 if (c)
 185                         l = c-file;
 186                 else
 187                         l = strlen(file);
 188                 file += l;
 189                 curr += l;
 190                 while (*file == '/')
 191                         file++;
 192                 while (*curr == '/')
 193                         curr++;
 194                 d--;
 195         }
 196         while (*file) {
 197                 if (curr > buf && curr[-1] != '/')
 198                         *curr++ = '/';
 199                 while (*file && *file != '/')
 200                         *curr++ = *file++;
 201                 while (*file == '/')
 202                         file++;
 203                 *curr = '\0';
 204                 if (*file)
 205                         pl = patch_add_file(pl, np, strdup(buf),
 206                                             0, 0);
 207         }
 208         return pl;
 209 }
 210
 211 struct plist *sort_patches(struct plist *pl, int *np)
 212 {
 213         /* sort the patches, add directory names, and re-sort */
 214         char curr[1024];
 215         char *prev;
 216         int parents[100];
 217         int prevnode[100];
 218         int i, n;
 219         qsort(pl, *np, sizeof(struct plist), pl_cmp);
 220         curr[0] = 0;
 221         n = *np;
 222         for (i = 0; i < n; i++)
 223                 pl = add_dir(pl, np, pl[i].file, curr);
 224
 225         qsort(pl, *np, sizeof(struct plist), pl_cmp);
 226
 227         /* array is now stable, so set up parent pointers */
 228         n = *np;
 229         curr[0] = 0;
 230         prevnode[0] = -1;
 231         prev = "";
 232         for (i = 0; i < n; i++) {
 233                 int d = common_depth(prev, pl[i].file);
 234                 if (d == 0)
 235                         pl[i].parent = -1;
 236                 else {
 237                         pl[i].parent = parents[d-1];
 238                         pl[pl[i].parent].last = i;
 239                 }
 240                 pl[i].prev = prevnode[d];
 241                 if (pl[i].prev > -1)
 242                         pl[pl[i].prev].next = i;
 243                 prev = pl[i].file;
 244                 parents[d] = i;
 245                 prevnode[d] = i;
 246                 prevnode[d+1] = -1;
 247         }
 248         return pl;
 249 }
 250
 251 struct plist *parse_patch(FILE *f, FILE *of, int *np)
 252 {
 253         /* read a multi-file patch from 'f' and record relevant
 254          * details in a plist.
 255          * if 'of' >= 0, fd might not be seekable so we write
 256          * to 'of' and use lseek on 'of' to determine position
 257          */
 258         struct plist *plist = NULL;
 259
 260         *np = 0;
 261         while (!feof(f)) {
 262                 /* first, find the start of a patch: "\n+++ "
 263                  * grab the file name and scan to the end of a line
 264                  */
 265                 char *target = "\n+++ ";
 266                 char *target2 = "\n--- ";
 267                 char *pos = target;
 268                 int c = EOF;
 269                 char name[1024];
 270                 unsigned start, end;
 271
 272                 while (*pos && (c = fgetc(f)) != EOF) {
 273                         if (of)
 274                                 fputc(c, of);
 275                         if (c == *pos)
 276                                 pos++;
 277                         else
 278                                 pos = target;
 279                 }
 280                 if (c == EOF)
 281                         break;
 282                 assert(c == ' ');
 283                 /* now read a file name */
 284                 pos = name;
 285                 while ((c = fgetc(f)) != EOF
 286                        && c != '\t' && c != '\n' && c != ' ' &&
 287                        pos - name < 1023) {
 288                         *pos++ = c;
 289                         if (of)
 290                                 fputc(c, of);
 291                 }
 292                 *pos = 0;
 293                 if (c == EOF)
 294                         break;
 295                 if (of)
 296                         fputc(c, of);
 297                 while (c != '\n' && (c = fgetc(f)) != EOF)
 298                         if (of)
 299                                 fputc(c, of);
 300
 301                 start = ftell(of ?: f);
 302
 303                 if (c == EOF)
 304                         break;
 305
 306                 /* now skip to end - "\n--- " */
 307                 pos = target2+1;
 308
 309                 while (*pos && (c = fgetc(f)) != EOF) {
 310                         if (of)
 311                                 fputc(c, of);
 312                         if (c == *pos)
 313                                 pos++;
 314                         else
 315                                 pos = target2;
 316                 }
 317                 end = ftell(of ?: f);
 318                 if (pos > target2)
 319                         end -= (pos - target2) - 1;
 320                 plist = patch_add_file(plist, np,
 321                                        strdup(name), start, end);
 322         }
 323         return plist;
 324 }