methods/rred.cc

   1 // Copyright (c) 2014 Anthony Towns
   2 //
   3 // This program is free software; you can redistribute it and/or modify
   4 // it under the terms of the GNU General Public License as published by
   5 // the Free Software Foundation; either version 2 of the License, or
   6 // (at your option) any later version.
   7
   8 #include <config.h>
   9
  10 #include <apt-pkg/fileutl.h>
  11 #include <apt-pkg/error.h>
  12 #include <apt-pkg/acquire-method.h>
  13 #include <apt-pkg/strutl.h>
  14 #include <apt-pkg/hashes.h>
  15 #include <apt-pkg/configuration.h>
  16
  17 #include <stddef.h>
  18 #include <iostream>
  19 #include <string>
  20 #include <list>
  21 #include <vector>
  22
  23 #include <assert.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <sys/stat.h>
  28 #include <sys/time.h>
  29
  30 #include <apti18n.h>
  31
  32 #define BLOCK_SIZE (512*1024)
  33
  34 class MemBlock {
  35    char *start;
  36    size_t size;
  37    char *free;
  38    struct MemBlock *next;
  39
  40    MemBlock(size_t size) : size(size), next(NULL)
  41    {
  42       free = start = new char[size];
  43    }
  44
  45    size_t avail(void) { return size - (free - start); }
  46
  47    public:
  48
  49    MemBlock(void) {
  50       free = start = new char[BLOCK_SIZE];
  51       size = BLOCK_SIZE;
  52       next = NULL;
  53    }
  54
  55    ~MemBlock() {
  56       delete [] start;
  57       delete next;
  58    }
  59
  60    void clear(void) {
  61       free = start;
  62       if (next)
  63          next->clear();
  64    }
  65
  66    char *add_easy(char *src, size_t len, char *last)
  67    {
  68       if (last) {
  69          for (MemBlock *k = this; k; k = k->next) {
  70             if (k->free == last) {
  71                if (len <= k->avail()) {
  72                   char *n = k->add(src, len);
  73                   assert(last == n);
  74                   if (last == n)
  75                      return NULL;
  76                   return n;
  77                } else {
  78                   break;
  79                }
  80             } else if (last >= start && last < free) {
  81                break;
  82             }
  83          }
  84       }
  85       return add(src, len);
  86    }
  87
  88    char *add(char *src, size_t len) {
  89       if (len > avail()) {
  90          if (!next) {
  91             if (len > BLOCK_SIZE)  {
  92                next = new MemBlock(len);
  93             } else {
  94                next = new MemBlock;
  95             }
  96          }
  97          return next->add(src, len);
  98       }
  99       char *dst = free;
 100       free += len;
 101       memcpy(dst, src, len);
 102       return dst;
 103    }
 104 };
 105
 106 struct Change {
 107    /* Ordering:
 108     *
 109     *   1. write out <offset> lines unchanged
 110     *   2. skip <del_cnt> lines from source
 111     *   3. write out <add_cnt> lines (<add>/<add_len>)
 112     */
 113    size_t offset;
 114    size_t del_cnt;
 115    size_t add_cnt; /* lines */
 116    size_t add_len; /* bytes */
 117    char *add;
 118
 119    Change(int off)
 120    {
 121       offset = off;
 122       del_cnt = add_cnt = add_len = 0;
 123       add = NULL;
 124    }
 125
 126    /* actually, don't write <lines> lines from <add> */
 127    void skip_lines(size_t lines)
 128    {
 129       while (lines > 0) {
 130          char *s = (char*) memchr(add, '\n', add_len);
 131          assert(s != NULL);
 132          s++;
 133          add_len -= (s - add);
 134          add_cnt--;
 135          lines--;
 136          if (add_len == 0) {
 137             add = NULL;
 138             assert(add_cnt == 0);
 139             assert(lines == 0);
 140          } else {
 141             add = s;
 142             assert(add_cnt > 0);
 143          }
 144       }
 145    }
 146 };
 147
 148 class FileChanges {
 149    std::list<struct Change> changes;
 150    std::list<struct Change>::iterator where;
 151    size_t pos; // line number is as far left of iterator as possible
 152
 153    bool pos_is_okay(void)
 154    {
 155 #ifdef POSDEBUG
 156       size_t cpos = 0;
 157       std::list<struct Change>::iterator x;
 158       for (x = changes.begin(); x != where; ++x) {
 159          assert(x != changes.end());
 160          cpos += x->offset + x->add_cnt;
 161       }
 162       return cpos == pos;
 163 #else
 164       return true;
 165 #endif
 166    }
 167
 168    public:
 169    FileChanges() {
 170       where = changes.end();
 171       pos = 0;
 172    }
 173
 174    std::list<struct Change>::iterator begin(void) { return changes.begin(); }
 175    std::list<struct Change>::iterator end(void) { return changes.end(); }
 176
 177    std::list<struct Change>::reverse_iterator rbegin(void) { return changes.rbegin(); }
 178    std::list<struct Change>::reverse_iterator rend(void) { return changes.rend(); }
 179
 180    void add_change(Change c) {
 181       assert(pos_is_okay());
 182       go_to_change_for(c.offset);
 183       assert(pos + where->offset == c.offset);
 184       if (c.del_cnt > 0)
 185          delete_lines(c.del_cnt);
 186       assert(pos + where->offset == c.offset);
 187       if (c.add_len > 0) {
 188          assert(pos_is_okay());
 189          if (where->add_len > 0)
 190             new_change();
 191          assert(where->add_len == 0 && where->add_cnt == 0);
 192
 193          where->add_len = c.add_len;
 194          where->add_cnt = c.add_cnt;
 195          where->add = c.add;
 196       }
 197       assert(pos_is_okay());
 198       merge();
 199       assert(pos_is_okay());
 200    }
 201
 202    private:
 203    void merge(void)
 204    {
 205       while (where->offset == 0 && where != changes.begin()) {
 206          left();
 207       }
 208       std::list<struct Change>::iterator next = where;
 209       ++next;
 210
 211       while (next != changes.end() && next->offset == 0) {
 212          where->del_cnt += next->del_cnt;
 213          next->del_cnt = 0;
 214          if (next->add == NULL) {
 215             next = changes.erase(next);
 216          } else if (where->add == NULL) {
 217             where->add = next->add;
 218             where->add_len = next->add_len;
 219             where->add_cnt = next->add_cnt;
 220             next = changes.erase(next);
 221          } else {
 222             ++next;
 223          }
 224       }
 225    }
 226
 227    void go_to_change_for(size_t line)
 228    {
 229       while(where != changes.end()) {
 230          if (line < pos) {
 231             left();
 232             continue;
 233          }
 234          if (pos + where->offset + where->add_cnt <= line) {
 235             right();
 236             continue;
 237          }
 238          // line is somewhere in this slot
 239          if (line < pos + where->offset) {
 240             break;
 241          } else if (line == pos + where->offset) {
 242             return;
 243          } else {
 244             split(line - pos);
 245             right();
 246             return;
 247          }
 248       }
 249       /* it goes before this patch */
 250       insert(line-pos);
 251    }
 252
 253    void new_change(void) { insert(where->offset); }
 254
 255    void insert(size_t offset)
 256    {
 257       assert(pos_is_okay());
 258       assert(where == changes.end() || offset <= where->offset);
 259       if (where != changes.end())
 260          where->offset -= offset;
 261       changes.insert(where, Change(offset));
 262       --where;
 263       assert(pos_is_okay());
 264    }
 265
 266    void split(size_t offset)
 267    {
 268       assert(pos_is_okay());
 269
 270       assert(where->offset < offset);
 271       assert(offset < where->offset + where->add_cnt);
 272
 273       size_t keep_lines = offset - where->offset;
 274
 275       Change before(*where);
 276
 277       where->del_cnt = 0;
 278       where->offset = 0;
 279       where->skip_lines(keep_lines);
 280
 281       before.add_cnt = keep_lines;
 282       before.add_len -= where->add_len;
 283
 284       changes.insert(where, before);
 285       --where;
 286       assert(pos_is_okay());
 287    }
 288
 289    void delete_lines(size_t cnt)
 290    {
 291       std::list<struct Change>::iterator x = where;
 292       assert(pos_is_okay());
 293       while (cnt > 0)
 294       {
 295          size_t del;
 296          del = x->add_cnt;
 297          if (del > cnt)
 298             del = cnt;
 299          x->skip_lines(del);
 300          cnt -= del;
 301
 302          ++x;
 303          if (x == changes.end()) {
 304             del = cnt;
 305          } else {
 306             del = x->offset;
 307             if (del > cnt)
 308                del = cnt;
 309             x->offset -= del;
 310          }
 311          where->del_cnt += del;
 312          cnt -= del;
 313       }
 314       assert(pos_is_okay());
 315    }
 316
 317    void left(void) {
 318       assert(pos_is_okay());
 319       --where;
 320       pos -= where->offset + where->add_cnt;
 321       assert(pos_is_okay());
 322    }
 323
 324    void right(void) {
 325       assert(pos_is_okay());
 326       pos += where->offset + where->add_cnt;
 327       ++where;
 328       assert(pos_is_okay());
 329    }
 330 };
 331
 332 class Patch {
 333    FileChanges filechanges;
 334    MemBlock add_text;
 335
 336    static bool retry_fwrite(char *b, size_t l, FILE *f, Hashes *hash)
 337    {
 338       size_t r = 1;
 339       while (r > 0 && l > 0)
 340       {
 341          r = fwrite(b, 1, l, f);
 342          if (hash)
 343             hash->Add((unsigned char*)b, r);
 344          l -= r;
 345          b += r;
 346       }
 347       return l == 0;
 348    }
 349
 350    static void dump_rest(FILE *o, FILE *i, Hashes *hash)
 351    {
 352       char buffer[BLOCK_SIZE];
 353       size_t l;
 354       while (0 < (l = fread(buffer, 1, sizeof(buffer), i))) {
 355          if (!retry_fwrite(buffer, l, o, hash))
 356             break;
 357       }
 358    }
 359
 360    static void dump_lines(FILE *o, FILE *i, size_t n, Hashes *hash)
 361    {
 362       char buffer[BLOCK_SIZE];
 363       while (n > 0) {
 364          if (fgets(buffer, sizeof(buffer), i) == 0)
 365             buffer[0] = '\0';
 366          size_t const l = strlen(buffer);
 367          if (l == 0 || buffer[l-1] == '\n')
 368             n--;
 369          retry_fwrite(buffer, l, o, hash);
 370       }
 371    }
 372
 373    static void skip_lines(FILE *i, int n)
 374    {
 375       char buffer[BLOCK_SIZE];
 376       while (n > 0) {
 377          if (fgets(buffer, sizeof(buffer), i) == 0)
 378             buffer[0] = '\0';
 379          size_t const l = strlen(buffer);
 380          if (l == 0 || buffer[l-1] == '\n')
 381             n--;
 382       }
 383    }
 384
 385    static void dump_mem(FILE *o, char *p, size_t s, Hashes *hash) {
 386       retry_fwrite(p, s, o, hash);
 387    }
 388
 389    public:
 390
 391    void read_diff(FileFd &f)
 392    {
 393       char buffer[BLOCK_SIZE];
 394       bool cmdwanted = true;
 395
 396       Change ch(0);
 397       while(f.ReadLine(buffer, sizeof(buffer)))
 398       {
 399          if (cmdwanted) {
 400             char *m, *c;
 401             size_t s, e;
 402             s = strtol(buffer, &m, 10);
 403             if (m == buffer) {
 404                s = e = ch.offset + ch.add_cnt;
 405                c = buffer;
 406             } else if (*m == ',') {
 407                m++;
 408                e = strtol(m, &c, 10);
 409             } else {
 410                e = s;
 411                c = m;
 412             }
 413             switch(*c) {
 414                case 'a':
 415                   cmdwanted = false;
 416                   ch.add = NULL;
 417                   ch.add_cnt = 0;
 418                   ch.add_len = 0;
 419                   ch.offset = s;
 420                   ch.del_cnt = 0;
 421                   break;
 422                case 'c':
 423                   cmdwanted = false;
 424                   ch.add = NULL;
 425                   ch.add_cnt = 0;
 426                   ch.add_len = 0;
 427                   ch.offset = s - 1;
 428                   ch.del_cnt = e - s + 1;
 429                   break;
 430                case 'd':
 431                   ch.offset = s - 1;
 432                   ch.del_cnt = e - s + 1;
 433                   ch.add = NULL;
 434                   ch.add_cnt = 0;
 435                   ch.add_len = 0;
 436                   filechanges.add_change(ch);
 437                   break;
 438             }
 439          } else { /* !cmdwanted */
 440             if (buffer[0] == '.' && buffer[1] == '\n') {
 441                cmdwanted = true;
 442                filechanges.add_change(ch);
 443             } else {
 444                char *last = NULL;
 445                char *add;
 446                size_t l;
 447                if (ch.add)
 448                   last = ch.add + ch.add_len;
 449                l = strlen(buffer);
 450                add = add_text.add_easy(buffer, l, last);
 451                if (!add) {
 452                   ch.add_len += l;
 453                   ch.add_cnt++;
 454                } else {
 455                   if (ch.add) {
 456                      filechanges.add_change(ch);
 457                      ch.del_cnt = 0;
 458                   }
 459                   ch.offset += ch.add_cnt;
 460                   ch.add = add;
 461                   ch.add_len = l;
 462                   ch.add_cnt = 1;
 463                }
 464             }
 465          }
 466       }
 467    }
 468
 469    void write_diff(FILE *f)
 470    {
 471       unsigned long long line = 0;
 472       std::list<struct Change>::reverse_iterator ch;
 473       for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
 474          line += ch->offset + ch->del_cnt;
 475       }
 476
 477       for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
 478          std::list<struct Change>::reverse_iterator mg_i, mg_e = ch;
 479          while (ch->del_cnt == 0 && ch->offset == 0)
 480             ++ch;
 481          line -= ch->del_cnt;
 482          if (ch->add_cnt > 0) {
 483             if (ch->del_cnt == 0) {
 484                fprintf(f, "%llua\n", line);
 485             } else if (ch->del_cnt == 1) {
 486                fprintf(f, "%lluc\n", line+1);
 487             } else {
 488                fprintf(f, "%llu,%lluc\n", line+1, line+ch->del_cnt);
 489             }
 490
 491             mg_i = ch;
 492             do {
 493                dump_mem(f, mg_i->add, mg_i->add_len, NULL);
 494             } while (mg_i-- != mg_e);
 495
 496             fprintf(f, ".\n");
 497          } else if (ch->del_cnt == 1) {
 498             fprintf(f, "%llud\n", line+1);
 499          } else if (ch->del_cnt > 1) {
 500             fprintf(f, "%llu,%llud\n", line+1, line+ch->del_cnt);
 501          }
 502          line -= ch->offset;
 503       }
 504    }
 505
 506    void apply_against_file(FILE *out, FILE *in, Hashes *hash = NULL)
 507    {
 508       std::list<struct Change>::iterator ch;
 509       for (ch = filechanges.begin(); ch != filechanges.end(); ++ch) {
 510          dump_lines(out, in, ch->offset, hash);
 511          skip_lines(in, ch->del_cnt);
 512          dump_mem(out, ch->add, ch->add_len, hash);
 513       }
 514       dump_rest(out, in, hash);
 515    }
 516 };
 517
 518 class RredMethod : public pkgAcqMethod {
 519    private:
 520       bool Debug;
 521
 522    protected:
 523       virtual bool Fetch(FetchItem *Itm) {
 524          Debug = _config->FindB("Debug::pkgAcquire::RRed", false);
 525          URI Get = Itm->Uri;
 526          std::string Path = Get.Host + Get.Path; // rred:/path - no host
 527
 528          FetchResult Res;
 529          Res.Filename = Itm->DestFile;
 530          if (Itm->Uri.empty())
 531          {
 532             Path = Itm->DestFile;
 533             Itm->DestFile.append(".result");
 534          } else
 535             URIStart(Res);
 536
 537          std::vector<std::string> patchpaths;
 538          Patch patch;
 539
 540          if (FileExists(Path + ".ed") == true)
 541             patchpaths.push_back(Path + ".ed");
 542          else
 543          {
 544             _error->PushToStack();
 545             std::vector<std::string> patches = GetListOfFilesInDir(flNotFile(Path), "gz", true, false);
 546             _error->RevertToStack();
 547
 548             std::string const baseName = Path + ".ed.";
 549             for (std::vector<std::string>::const_iterator p = patches.begin();
 550                   p != patches.end(); ++p)
 551                if (p->compare(0, baseName.length(), baseName) == 0)
 552                   patchpaths.push_back(*p);
 553          }
 554
 555          std::string patch_name;
 556          for (std::vector<std::string>::iterator I = patchpaths.begin();
 557                I != patchpaths.end();
 558                ++I)
 559          {
 560             patch_name = *I;
 561             if (Debug == true)
 562                std::clog << "Patching " << Path << " with " << patch_name
 563                   << std::endl;
 564
 565             FileFd p;
 566             // all patches are compressed, even if the name doesn't reflect it
 567             if (p.Open(patch_name, FileFd::ReadOnly, FileFd::Gzip) == false) {
 568                std::cerr << "Could not open patch file " << patch_name << std::endl;
 569                _error->DumpErrors(std::cerr);
 570                abort();
 571             }
 572             patch.read_diff(p);
 573             p.Close();
 574          }
 575
 576          if (Debug == true)
 577             std::clog << "Applying patches against " << Path
 578                << " and writing results to " << Itm->DestFile
 579                << std::endl;
 580
 581          FILE *inp = fopen(Path.c_str(), "r");
 582          FILE *out = fopen(Itm->DestFile.c_str(), "w");
 583
 584          Hashes hash;
 585
 586          patch.apply_against_file(out, inp, &hash);
 587
 588          fclose(out);
 589          fclose(inp);
 590
 591          if (Debug == true) {
 592             std::clog << "rred: finished file patching of " << Path  << "." << std::endl;
 593          }
 594
 595          struct stat bufbase, bufpatch;
 596          if (stat(Path.c_str(), &bufbase) != 0 ||
 597                stat(patch_name.c_str(), &bufpatch) != 0)
 598             return _error->Errno("stat", _("Failed to stat"));
 599
 600          struct timeval times[2];
 601          times[0].tv_sec = bufbase.st_atime;
 602          times[1].tv_sec = bufpatch.st_mtime;
 603          times[0].tv_usec = times[1].tv_usec = 0;
 604          if (utimes(Itm->DestFile.c_str(), times) != 0)
 605             return _error->Errno("utimes",_("Failed to set modification time"));
 606
 607          if (stat(Itm->DestFile.c_str(), &bufbase) != 0)
 608             return _error->Errno("stat", _("Failed to stat"));
 609
 610          Res.LastModified = bufbase.st_mtime;
 611          Res.Size = bufbase.st_size;
 612          Res.TakeHashes(hash);
 613          URIDone(Res);
 614
 615          return true;
 616       }
 617
 618    public:
 619       RredMethod() : pkgAcqMethod("2.0",SingleInstance | SendConfig), Debug(false) {}
 620 };
 621
 622 int main(int argc, char **argv)
 623 {
 624    int i;
 625    bool just_diff = true;
 626    Patch patch;
 627
 628    if (argc <= 1) {
 629       RredMethod Mth;
 630       return Mth.Run();
 631    }
 632
 633    if (argc > 1 && strcmp(argv[1], "-f") == 0) {
 634       just_diff = false;
 635       i = 2;
 636    } else {
 637       i = 1;
 638    }
 639
 640    for (; i < argc; i++) {
 641       FileFd p;
 642       if (p.Open(argv[i], FileFd::ReadOnly) == false) {
 643          _error->DumpErrors(std::cerr);
 644          exit(1);
 645       }
 646       patch.read_diff(p);
 647    }
 648
 649    if (just_diff) {
 650       patch.write_diff(stdout);
 651    } else {
 652       FILE *out, *inp;
 653       out = stdout;
 654       inp = stdin;
 655
 656       patch.apply_against_file(out, inp);
 657    }
 658    return 0;
 659 }