[apt.git] / methods / rred.cc

// Copyright (c) 2014 Anthony Towns
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.

#include <config.h>

#include <apt-pkg/fileutl.h>
#include <apt-pkg/error.h>
#include <apt-pkg/acquire-method.h>
#include <apt-pkg/strutl.h>
#include <apt-pkg/hashes.h>
#include <apt-pkg/configuration.h>

#include <stddef.h>
#include <iostream>
#include <string>
#include <list>
#include <vector>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/time.h>

#include <apti18n.h>

#define BLOCK_SIZE (512*1024)

class MemBlock {
   char *start;
   size_t size;
   char *free;
   struct MemBlock *next;

   MemBlock(size_t size) : size(size), next(NULL)
   {
      free = start = new char[size];
   }

   size_t avail(void) { return size - (free - start); }

   public:

   MemBlock(void) {
      free = start = new char[BLOCK_SIZE];
      size = BLOCK_SIZE;
      next = NULL;
   }

   ~MemBlock() {
      delete [] start;
      delete next;
   }

   void clear(void) {
      free = start;
      if (next)
	 next->clear();
   }

   char *add_easy(char *src, size_t len, char *last)
   {
      if (last) {
	 for (MemBlock *k = this; k; k = k->next) {
	    if (k->free == last) {
	       if (len <= k->avail()) {
		  char *n = k->add(src, len);
		  assert(last == n);
		  if (last == n)
		     return NULL;
		  return n;
	       } else {
		  break;
	       }
	    } else if (last >= start && last < free) {
	       break;
	    }
	 }
      }
      return add(src, len);
   }

   char *add(char *src, size_t len) {
      if (len > avail()) {
	 if (!next) {
	    if (len > BLOCK_SIZE)  {
	       next = new MemBlock(len);
	    } else {
	       next = new MemBlock;
	    }
	 }
	 return next->add(src, len);
      }
      char *dst = free;
      free += len;
      memcpy(dst, src, len);
      return dst;
   }
};

struct Change {
   /* Ordering:
    *
    *   1. write out <offset> lines unchanged
    *   2. skip <del_cnt> lines from source
    *   3. write out <add_cnt> lines (<add>/<add_len>)
    */
   size_t offset;
   size_t del_cnt;
   size_t add_cnt; /* lines */
   size_t add_len; /* bytes */
   char *add;

   Change(int off)
   {
      offset = off;
      del_cnt = add_cnt = add_len = 0;
      add = NULL;
   }

   /* actually, don't write <lines> lines from <add> */
   void skip_lines(size_t lines)
   {
      while (lines > 0) {
	 char *s = (char*) memchr(add, '\n', add_len);
	 assert(s != NULL);
	 s++;
	 add_len -= (s - add);
	 add_cnt--;
	 lines--;
	 if (add_len == 0) {
	    add = NULL;
	    assert(add_cnt == 0);
	    assert(lines == 0);
	 } else {
	    add = s;
	    assert(add_cnt > 0);
	 }
      }
   }
};

class FileChanges {
   std::list<struct Change> changes;
   std::list<struct Change>::iterator where;
   size_t pos; // line number is as far left of iterator as possible

   bool pos_is_okay(void) const
   {
#ifdef POSDEBUG
      size_t cpos = 0;
      std::list<struct Change>::const_iterator x;
      for (x = changes.begin(); x != where; ++x) {
	 assert(x != changes.end());
	 cpos += x->offset + x->add_cnt;
      }
      return cpos == pos;
#else
      return true;
#endif
   }

   public:
   FileChanges() {
      where = changes.end();
      pos = 0;
   }

   std::list<struct Change>::iterator begin(void) { return changes.begin(); }
   std::list<struct Change>::iterator end(void) { return changes.end(); }

   std::list<struct Change>::reverse_iterator rbegin(void) { return changes.rbegin(); }
   std::list<struct Change>::reverse_iterator rend(void) { return changes.rend(); }

   void add_change(Change c) {
      assert(pos_is_okay());
      go_to_change_for(c.offset);
      assert(pos + where->offset == c.offset);
      if (c.del_cnt > 0)
	 delete_lines(c.del_cnt);
      assert(pos + where->offset == c.offset);
      if (c.add_len > 0) {
	 assert(pos_is_okay());
	 if (where->add_len > 0)
	    new_change();
	 assert(where->add_len == 0 && where->add_cnt == 0);

	 where->add_len = c.add_len;
	 where->add_cnt = c.add_cnt;
	 where->add = c.add;
      }
      assert(pos_is_okay());
      merge();
      assert(pos_is_okay());
   }

   private:
   void merge(void)
   {
      while (where->offset == 0 && where != changes.begin()) {
	 left();
      }
      std::list<struct Change>::iterator next = where;
      ++next;

      while (next != changes.end() && next->offset == 0) {
	 where->del_cnt += next->del_cnt;
	 next->del_cnt = 0;
	 if (next->add == NULL) {
	    next = changes.erase(next);
	 } else if (where->add == NULL) {
	    where->add = next->add;
	    where->add_len = next->add_len;
	    where->add_cnt = next->add_cnt;
	    next = changes.erase(next);
	 } else {
	    ++next;
	 }
      }
   }

   void go_to_change_for(size_t line)
   {
      while(where != changes.end()) {
	 if (line < pos) {
	    left();
	    continue;
	 }
	 if (pos + where->offset + where->add_cnt <= line) {
	    right();
	    continue;
	 }
	 // line is somewhere in this slot
	 if (line < pos + where->offset) {
	    break;
	 } else if (line == pos + where->offset) {
	    return;
	 } else {
	    split(line - pos);
	    right();
	    return;
	 }
      }
      /* it goes before this patch */
      insert(line-pos);
   }

   void new_change(void) { insert(where->offset); }

   void insert(size_t offset)
   {
      assert(pos_is_okay());
      assert(where == changes.end() || offset <= where->offset);
      if (where != changes.end())
	 where->offset -= offset;
      changes.insert(where, Change(offset));
      --where;
      assert(pos_is_okay());
   }

   void split(size_t offset)
   {
      assert(pos_is_okay());

      assert(where->offset < offset);
      assert(offset < where->offset + where->add_cnt);

      size_t keep_lines = offset - where->offset;

      Change before(*where);

      where->del_cnt = 0;
      where->offset = 0;
      where->skip_lines(keep_lines);

      before.add_cnt = keep_lines;
      before.add_len -= where->add_len;

      changes.insert(where, before);
      --where;
      assert(pos_is_okay());
   }

   void delete_lines(size_t cnt)
   {
      std::list<struct Change>::iterator x = where;
      assert(pos_is_okay());
      while (cnt > 0)
      {
	 size_t del;
	 del = x->add_cnt;
	 if (del > cnt)
	    del = cnt;
	 x->skip_lines(del);
	 cnt -= del;

	 ++x;
	 if (x == changes.end()) {
	    del = cnt;
	 } else {
	    del = x->offset;
	    if (del > cnt)
	       del = cnt;
	    x->offset -= del;
	 }
	 where->del_cnt += del;
	 cnt -= del;
      }
      assert(pos_is_okay());
   }

   void left(void) {
      assert(pos_is_okay());
      --where;
      pos -= where->offset + where->add_cnt;
      assert(pos_is_okay());
   }

   void right(void) {
      assert(pos_is_okay());
      pos += where->offset + where->add_cnt;
      ++where;
      assert(pos_is_okay());
   }
};

class Patch {
   FileChanges filechanges;
   MemBlock add_text;

   static bool retry_fwrite(char *b, size_t l, FILE *f, Hashes *hash)
   {
      size_t r = 1;
      while (r > 0 && l > 0)
      {
         r = fwrite(b, 1, l, f);
	 if (hash)
	    hash->Add((unsigned char*)b, r);
	 l -= r;
	 b += r;
      }
      return l == 0;
   }

   static void dump_rest(FILE *o, FILE *i, Hashes *hash)
   {
      char buffer[BLOCK_SIZE];
      size_t l;
      while (0 < (l = fread(buffer, 1, sizeof(buffer), i))) {
	 if (!retry_fwrite(buffer, l, o, hash))
	    break;
      }
   }

   static void dump_lines(FILE *o, FILE *i, size_t n, Hashes *hash)
   {
      char buffer[BLOCK_SIZE];
      while (n > 0) {
	 if (fgets(buffer, sizeof(buffer), i) == 0)
	    buffer[0] = '\0';
	 size_t const l = strlen(buffer);
	 if (l == 0 || buffer[l-1] == '\n')
	    n--;
	 retry_fwrite(buffer, l, o, hash);
      }
   }

   static void skip_lines(FILE *i, int n)
   {
      char buffer[BLOCK_SIZE];
      while (n > 0) {
	 if (fgets(buffer, sizeof(buffer), i) == 0)
	    buffer[0] = '\0';
	 size_t const l = strlen(buffer);
	 if (l == 0 || buffer[l-1] == '\n')
	    n--;
      }
   }

   static void dump_mem(FILE *o, char *p, size_t s, Hashes *hash) {
      retry_fwrite(p, s, o, hash);
   }

   public:

   void read_diff(FileFd &f, Hashes * const h)
   {
      char buffer[BLOCK_SIZE];
      bool cmdwanted = true;

      Change ch(0);
      while(f.ReadLine(buffer, sizeof(buffer)))
      {
	 if (h != NULL)
	    h->Add(buffer);
	 if (cmdwanted) {
	    char *m, *c;
	    size_t s, e;
	    s = strtol(buffer, &m, 10);
	    if (m == buffer) {
	       s = e = ch.offset + ch.add_cnt;
	       c = buffer;
	    } else if (*m == ',') {
	       m++;
	       e = strtol(m, &c, 10);
	    } else {
	       e = s;
	       c = m;
	    }
	    switch(*c) {
	       case 'a':
		  cmdwanted = false;
		  ch.add = NULL;
		  ch.add_cnt = 0;
		  ch.add_len = 0;
		  ch.offset = s;
		  ch.del_cnt = 0;
		  break;
	       case 'c':
		  cmdwanted = false;
		  ch.add = NULL;
		  ch.add_cnt = 0;
		  ch.add_len = 0;
		  ch.offset = s - 1;
		  ch.del_cnt = e - s + 1;
		  break;
	       case 'd':
		  ch.offset = s - 1;
		  ch.del_cnt = e - s + 1;
		  ch.add = NULL;
		  ch.add_cnt = 0;
		  ch.add_len = 0;
		  filechanges.add_change(ch);
		  break;
	    }
	 } else { /* !cmdwanted */
	    if (buffer[0] == '.' && buffer[1] == '\n') {
	       cmdwanted = true;
	       filechanges.add_change(ch);
	    } else {
	       char *last = NULL;
	       char *add;
	       size_t l;
	       if (ch.add)
		  last = ch.add + ch.add_len;
	       l = strlen(buffer);
	       add = add_text.add_easy(buffer, l, last);
	       if (!add) {
		  ch.add_len += l;
		  ch.add_cnt++;
	       } else {
		  if (ch.add) {
		     filechanges.add_change(ch);
		     ch.del_cnt = 0;
		  }
		  ch.offset += ch.add_cnt;
		  ch.add = add;
		  ch.add_len = l;
		  ch.add_cnt = 1;
	       }
	    }
	 }
      }
   }

   void write_diff(FILE *f)
   {
      unsigned long long line = 0;
      std::list<struct Change>::reverse_iterator ch;
      for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
	 line += ch->offset + ch->del_cnt;
      }

      for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
	 std::list<struct Change>::reverse_iterator mg_i, mg_e = ch;
	 while (ch->del_cnt == 0 && ch->offset == 0)
	    ++ch;
	 line -= ch->del_cnt;
	 if (ch->add_cnt > 0) {
	    if (ch->del_cnt == 0) {
	       fprintf(f, "%llua\n", line);
	    } else if (ch->del_cnt == 1) {
	       fprintf(f, "%lluc\n", line+1);
	    } else {
	       fprintf(f, "%llu,%lluc\n", line+1, line+ch->del_cnt);
	    }

	    mg_i = ch;
	    do {
	       dump_mem(f, mg_i->add, mg_i->add_len, NULL);
	    } while (mg_i-- != mg_e);

	    fprintf(f, ".\n");
	 } else if (ch->del_cnt == 1) {
	    fprintf(f, "%llud\n", line+1);
	 } else if (ch->del_cnt > 1) {
	    fprintf(f, "%llu,%llud\n", line+1, line+ch->del_cnt);
	 }
	 line -= ch->offset;
      }
   }

   void apply_against_file(FILE *out, FILE *in, Hashes *hash = NULL)
   {
      std::list<struct Change>::iterator ch;
      for (ch = filechanges.begin(); ch != filechanges.end(); ++ch) {
	 dump_lines(out, in, ch->offset, hash);
	 skip_lines(in, ch->del_cnt);
	 dump_mem(out, ch->add, ch->add_len, hash);
      }
      dump_rest(out, in, hash);
   }
};

class RredMethod : public pkgAcqMethod {
   private:
      bool Debug;

      struct PDiffFile {
	 std::string FileName;
	 HashStringList ExpectedHashes;
	 PDiffFile(std::string const &FileName, HashStringList const &ExpectedHashes) :
	    FileName(FileName), ExpectedHashes(ExpectedHashes) {}
      };

      HashStringList ReadExpectedHashesForPatch(unsigned int const patch, std::string const &Message)
      {
	 HashStringList ExpectedHashes;
	 for (char const * const * type = HashString::SupportedHashes(); *type != NULL; ++type)
	 {
	    std::string tagname;
	    strprintf(tagname, "Patch-%d-%s-Hash", patch, *type);
	    std::string const hashsum = LookupTag(Message, tagname.c_str());
	    if (hashsum.empty() == false)
	       ExpectedHashes.push_back(HashString(*type, hashsum));
	 }
	 return ExpectedHashes;
      }

   protected:
      virtual bool URIAcquire(std::string const &Message, FetchItem *Itm) {
	 Debug = _config->FindB("Debug::pkgAcquire::RRed", false);
	 URI Get = Itm->Uri;
	 std::string Path = Get.Host + Get.Path; // rred:/path - no host

	 FetchResult Res;
	 Res.Filename = Itm->DestFile;
	 if (Itm->Uri.empty())
	 {
	    Path = Itm->DestFile;
	    Itm->DestFile.append(".result");
	 } else
	    URIStart(Res);

	 std::vector<PDiffFile> patchfiles;
	 Patch patch;

	 if (FileExists(Path + ".ed") == true)
	 {
	    HashStringList const ExpectedHashes = ReadExpectedHashesForPatch(0, Message);
	    std::string const FileName = Path + ".ed";
	    if (ExpectedHashes.usable() == false)
	       return _error->Error("No hashes found for uncompressed patch: %s", FileName.c_str());
	    patchfiles.push_back(PDiffFile(FileName, ExpectedHashes));
	 }
	 else
	 {
	    _error->PushToStack();
	    std::vector<std::string> patches = GetListOfFilesInDir(flNotFile(Path), "gz", true, false);
	    _error->RevertToStack();

	    std::string const baseName = Path + ".ed.";
	    unsigned int seen_patches = 0;
	    for (std::vector<std::string>::const_iterator p = patches.begin();
		  p != patches.end(); ++p)
	    {
	       if (p->compare(0, baseName.length(), baseName) == 0)
	       {
		  HashStringList const ExpectedHashes = ReadExpectedHashesForPatch(seen_patches, Message);
		  if (ExpectedHashes.usable() == false)
		     return _error->Error("No hashes found for uncompressed patch %d: %s", seen_patches, p->c_str());
		  patchfiles.push_back(PDiffFile(*p, ExpectedHashes));
		  ++seen_patches;
	       }
	    }
	 }

	 std::string patch_name;
	 for (std::vector<PDiffFile>::iterator I = patchfiles.begin();
	       I != patchfiles.end();
	       ++I)
	 {
	    patch_name = I->FileName;
	    if (Debug == true)
	       std::clog << "Patching " << Path << " with " << patch_name
		  << std::endl;

	    FileFd p;
	    // all patches are compressed, even if the name doesn't reflect it
	    if (p.Open(patch_name, FileFd::ReadOnly, FileFd::Gzip) == false) {
	       std::cerr << "Could not open patch file " << patch_name << std::endl;
	       _error->DumpErrors(std::cerr);
	       abort();
	    }
	    Hashes patch_hash(I->ExpectedHashes);
	    patch.read_diff(p, &patch_hash);
	    p.Close();
	    HashStringList const hsl = patch_hash.GetHashStringList();
	    if (hsl != I->ExpectedHashes)
	       return _error->Error("Patch %s doesn't have the expected hashsum", patch_name.c_str());
	 }

	 if (Debug == true)
	    std::clog << "Applying patches against " << Path
	       << " and writing results to " << Itm->DestFile
	       << std::endl;

	 FILE *inp = fopen(Path.c_str(), "r");
	 FILE *out = fopen(Itm->DestFile.c_str(), "w");

	 Hashes hash(Itm->ExpectedHashes);

	 patch.apply_against_file(out, inp, &hash);

	 fclose(out);
	 fclose(inp);

	 if (Debug == true) {
	    std::clog << "rred: finished file patching of " << Path  << "." << std::endl;
	 }

	 struct stat bufbase, bufpatch;
	 if (stat(Path.c_str(), &bufbase) != 0 ||
	       stat(patch_name.c_str(), &bufpatch) != 0)
	    return _error->Errno("stat", _("Failed to stat"));

	 struct timeval times[2];
	 times[0].tv_sec = bufbase.st_atime;
	 times[1].tv_sec = bufpatch.st_mtime;
	 times[0].tv_usec = times[1].tv_usec = 0;
	 if (utimes(Itm->DestFile.c_str(), times) != 0)
	    return _error->Errno("utimes",_("Failed to set modification time"));

	 if (stat(Itm->DestFile.c_str(), &bufbase) != 0)
	    return _error->Errno("stat", _("Failed to stat"));

	 Res.LastModified = bufbase.st_mtime;
	 Res.Size = bufbase.st_size;
	 Res.TakeHashes(hash);
	 URIDone(Res);

	 return true;
      }

   public:
      RredMethod() : pkgAcqMethod("2.0",SingleInstance | SendConfig), Debug(false) {}
};

int main(int argc, char **argv)
{
   int i;
   bool just_diff = true;
   Patch patch;

   if (argc <= 1) {
      RredMethod Mth;
      return Mth.Run();
   }

   if (argc > 1 && strcmp(argv[1], "-f") == 0) {
      just_diff = false;
      i = 2;
   } else {
      i = 1;
   }

   for (; i < argc; i++) {
      FileFd p;
      if (p.Open(argv[i], FileFd::ReadOnly) == false) {
	 _error->DumpErrors(std::cerr);
	 exit(1);
      }
      patch.read_diff(p, NULL);
   }

   if (just_diff) {
      patch.write_diff(stdout);
   } else {
      FILE *out, *inp;
      out = stdout;
      inp = stdin;

      patch.apply_against_file(out, inp);
   }
   return 0;
}
Commit	Line	Data
dbd5418b AT	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
ea542140 DK	8	#include <config.h>
ea542140 DK	9
2e178d1c MV	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>
472ff00e	15	#include <apt-pkg/configuration.h>
2e178d1c	16
453b82a3 DK	17	#include <stddef.h>
453b82a3 DK	18	#include <iostream>
dbd5418b AT	19	#include <string>
	20	#include <list>
	21	#include <vector>
dbd5418b AT	22
	23	#include <assert.h>
	24	#include <stdio.h>
	25	#include <stdlib.h>
	26	#include <string.h>
2e178d1c	27	#include <sys/stat.h>
246bbb61	28	#include <sys/time.h>
dbd5418b	29
2e178d1c	30	#include <apti18n.h>
dbd5418b AT	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
25d99f3b	40	MemBlock(size_t size) : size(size), next(NULL)
dbd5418b AT	41	{
dbd5418b AT	42	free = start = new char[size];
dbd5418b AT	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	}
2e178d1c	104	};
dbd5418b AT	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	}
d84cd865 MV	144	}
d84cd865 MV	145	}
bb1293d9	146	};
dbd5418b AT	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
9dd940ed	153	bool pos_is_okay(void) const
dbd5418b AT	154	{
	155	#ifdef POSDEBUG
	156	size_t cpos = 0;
9dd940ed	157	std::list<struct Change>::const_iterator x;
25d99f3b	158	for (x = changes.begin(); x != where; ++x) {
dbd5418b AT	159	assert(x != changes.end());
	160	cpos += x->offset + x->add_cnt;
	161	}
	162	return cpos == pos;
bb1293d9	163	#else
dbd5418b	164	return true;
bb1293d9	165	#endif
dbd5418b AT	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;
25d99f3b	209	++next;
dbd5418b AT	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 {
25d99f3b	222	++next;
dbd5418b AT	223	}
	224	}
	225	}
	226
	227	void go_to_change_for(size_t line)
47d2bc78	228	{
dbd5418b AT	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;
47d2bc78	247	}
bb1293d9	248	}
dbd5418b AT	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));
25d99f3b	262	--where;
dbd5418b AT	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);
47d2bc78	276
dbd5418b AT	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);
25d99f3b	285	--where;
dbd5418b	286	assert(pos_is_okay());
3de9ff77	287	}
dbd5418b	288
dbd5418b AT	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
25d99f3b	302	++x;
dbd5418b AT	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	}
47d2bc78	316
dbd5418b AT	317	void left(void) {
dbd5418b AT	318	assert(pos_is_okay());
25d99f3b	319	--where;
dbd5418b AT	320	pos -= where->offset + where->add_cnt;
	321	assert(pos_is_okay());
	322	}
47d2bc78	323
dbd5418b AT	324	void right(void) {
	325	assert(pos_is_okay());
	326	pos += where->offset + where->add_cnt;
25d99f3b	327	++where;
dbd5418b AT	328	assert(pos_is_okay());
	329	}
	330	};
	331
	332	class Patch {
	333	FileChanges filechanges;
	334	MemBlock add_text;
	335
2fd754cf AT	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
dbd5418b AT	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))) {
2fd754cf AT	355	if (!retry_fwrite(buffer, l, o, hash))
2fd754cf AT	356	break;
dbd5418b AT	357	}
	358	}
	359
	360	static void dump_lines(FILE o, FILE i, size_t n, Hashes *hash)
	361	{
	362	char buffer[BLOCK_SIZE];
dbd5418b AT	363	while (n > 0) {
	364	if (fgets(buffer, sizeof(buffer), i) == 0)
	365	buffer[0] = '\0';
25d99f3b	366	size_t const l = strlen(buffer);
dbd5418b AT	367	if (l == 0 \|\| buffer[l-1] == '\n')
dbd5418b AT	368	n--;
2fd754cf	369	retry_fwrite(buffer, l, o, hash);
dbd5418b AT	370	}
	371	}
	372
	373	static void skip_lines(FILE *i, int n)
	374	{
	375	char buffer[BLOCK_SIZE];
dbd5418b AT	376	while (n > 0) {
	377	if (fgets(buffer, sizeof(buffer), i) == 0)
	378	buffer[0] = '\0';
25d99f3b	379	size_t const l = strlen(buffer);
dbd5418b AT	380	if (l == 0 \|\| buffer[l-1] == '\n')
	381	n--;
	382	}
	383	}
	384
2fd754cf AT	385	static void dump_mem(FILE o, char p, size_t s, Hashes *hash) {
2fd754cf AT	386	retry_fwrite(p, s, o, hash);
dbd5418b AT	387	}
	388
	389	public:
	390
36795154	391	void read_diff(FileFd &f, Hashes * const h)
dbd5418b AT	392	{
	393	char buffer[BLOCK_SIZE];
	394	bool cmdwanted = true;
	395
	396	Change ch(0);
50bd6fd3	397	while(f.ReadLine(buffer, sizeof(buffer)))
dbd5418b	398	{
36795154 DK	399	if (h != NULL)
36795154 DK	400	h->Add(buffer);
dbd5418b AT	401	if (cmdwanted) {
	402	char m, c;
	403	size_t s, e;
	404	s = strtol(buffer, &m, 10);
	405	if (m == buffer) {
	406	s = e = ch.offset + ch.add_cnt;
	407	c = buffer;
	408	} else if (*m == ',') {
	409	m++;
	410	e = strtol(m, &c, 10);
	411	} else {
	412	e = s;
	413	c = m;
	414	}
	415	switch(*c) {
	416	case 'a':
	417	cmdwanted = false;
	418	ch.add = NULL;
	419	ch.add_cnt = 0;
	420	ch.add_len = 0;
	421	ch.offset = s;
	422	ch.del_cnt = 0;
	423	break;
	424	case 'c':
	425	cmdwanted = false;
	426	ch.add = NULL;
	427	ch.add_cnt = 0;
	428	ch.add_len = 0;
	429	ch.offset = s - 1;
	430	ch.del_cnt = e - s + 1;
	431	break;
	432	case 'd':
	433	ch.offset = s - 1;
	434	ch.del_cnt = e - s + 1;
	435	ch.add = NULL;
	436	ch.add_cnt = 0;
	437	ch.add_len = 0;
	438	filechanges.add_change(ch);
	439	break;
	440	}
2fd754cf	441	} else { /* !cmdwanted */
dbd5418b AT	442	if (buffer[0] == '.' && buffer[1] == '\n') {
	443	cmdwanted = true;
	444	filechanges.add_change(ch);
	445	} else {
	446	char *last = NULL;
	447	char *add;
	448	size_t l;
	449	if (ch.add)
	450	last = ch.add + ch.add_len;
	451	l = strlen(buffer);
	452	add = add_text.add_easy(buffer, l, last);
	453	if (!add) {
	454	ch.add_len += l;
	455	ch.add_cnt++;
	456	} else {
	457	if (ch.add) {
	458	filechanges.add_change(ch);
	459	ch.del_cnt = 0;
	460	}
	461	ch.offset += ch.add_cnt;
	462	ch.add = add;
	463	ch.add_len = l;
	464	ch.add_cnt = 1;
	465	}
	466	}
	467	}
	468	}
	469	}
	470
	471	void write_diff(FILE *f)
	472	{
6298ff8b	473	unsigned long long line = 0;
dbd5418b	474	std::list<struct Change>::reverse_iterator ch;
25d99f3b	475	for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
dbd5418b AT	476	line += ch->offset + ch->del_cnt;
	477	}
	478
25d99f3b	479	for (ch = filechanges.rbegin(); ch != filechanges.rend(); ++ch) {
dbd5418b AT	480	std::list<struct Change>::reverse_iterator mg_i, mg_e = ch;
dbd5418b AT	481	while (ch->del_cnt == 0 && ch->offset == 0)
25d99f3b	482	++ch;
dbd5418b AT	483	line -= ch->del_cnt;
	484	if (ch->add_cnt > 0) {
	485	if (ch->del_cnt == 0) {
6298ff8b	486	fprintf(f, "%llua\n", line);
dbd5418b	487	} else if (ch->del_cnt == 1) {
6298ff8b	488	fprintf(f, "%lluc\n", line+1);
dbd5418b	489	} else {
6298ff8b	490	fprintf(f, "%llu,%lluc\n", line+1, line+ch->del_cnt);
dbd5418b AT	491	}
	492
	493	mg_i = ch;
	494	do {
	495	dump_mem(f, mg_i->add, mg_i->add_len, NULL);
	496	} while (mg_i-- != mg_e);
	497
	498	fprintf(f, ".\n");
	499	} else if (ch->del_cnt == 1) {
6298ff8b	500	fprintf(f, "%llud\n", line+1);
dbd5418b	501	} else if (ch->del_cnt > 1) {
6298ff8b	502	fprintf(f, "%llu,%llud\n", line+1, line+ch->del_cnt);
dbd5418b AT	503	}
	504	line -= ch->offset;
	505	}
	506	}
47d2bc78	507
dbd5418b AT	508	void apply_against_file(FILE out, FILE in, Hashes *hash = NULL)
	509	{
	510	std::list<struct Change>::iterator ch;
25d99f3b	511	for (ch = filechanges.begin(); ch != filechanges.end(); ++ch) {
dbd5418b AT	512	dump_lines(out, in, ch->offset, hash);
	513	skip_lines(in, ch->del_cnt);
	514	dump_mem(out, ch->add, ch->add_len, hash);
	515	}
	516	dump_rest(out, in, hash);
47d2bc78	517	}
dbd5418b AT	518	};
dbd5418b AT	519
dbd5418b AT	520	class RredMethod : public pkgAcqMethod {
	521	private:
	522	bool Debug;
dbd5418b	523
36795154 DK	524	struct PDiffFile {
	525	std::string FileName;
	526	HashStringList ExpectedHashes;
	527	PDiffFile(std::string const &FileName, HashStringList const &ExpectedHashes) :
	528	FileName(FileName), ExpectedHashes(ExpectedHashes) {}
	529	};
	530
	531	HashStringList ReadExpectedHashesForPatch(unsigned int const patch, std::string const &Message)
	532	{
	533	HashStringList ExpectedHashes;
	534	for (char const * const * type = HashString::SupportedHashes(); *type != NULL; ++type)
	535	{
	536	std::string tagname;
	537	strprintf(tagname, "Patch-%d-%s-Hash", patch, *type);
	538	std::string const hashsum = LookupTag(Message, tagname.c_str());
	539	if (hashsum.empty() == false)
	540	ExpectedHashes.push_back(HashString(*type, hashsum));
	541	}
	542	return ExpectedHashes;
	543	}
	544
dbd5418b	545	protected:
36795154	546	virtual bool URIAcquire(std::string const &Message, FetchItem *Itm) {
dbd5418b AT	547	Debug = _config->FindB("Debug::pkgAcquire::RRed", false);
	548	URI Get = Itm->Uri;
	549	std::string Path = Get.Host + Get.Path; // rred:/path - no host
	550
	551	FetchResult Res;
	552	Res.Filename = Itm->DestFile;
50bd6fd3 DK	553	if (Itm->Uri.empty())
50bd6fd3 DK	554	{
dbd5418b AT	555	Path = Itm->DestFile;
	556	Itm->DestFile.append(".result");
	557	} else
	558	URIStart(Res);
	559
36795154	560	std::vector<PDiffFile> patchfiles;
dbd5418b AT	561	Patch patch;
dbd5418b AT	562
50bd6fd3	563	if (FileExists(Path + ".ed") == true)
36795154 DK	564	{
	565	HashStringList const ExpectedHashes = ReadExpectedHashesForPatch(0, Message);
	566	std::string const FileName = Path + ".ed";
	567	if (ExpectedHashes.usable() == false)
	568	return _error->Error("No hashes found for uncompressed patch: %s", FileName.c_str());
	569	patchfiles.push_back(PDiffFile(FileName, ExpectedHashes));
	570	}
50bd6fd3 DK	571	else
	572	{
	573	_error->PushToStack();
	574	std::vector<std::string> patches = GetListOfFilesInDir(flNotFile(Path), "gz", true, false);
	575	_error->RevertToStack();
	576
	577	std::string const baseName = Path + ".ed.";
36795154	578	unsigned int seen_patches = 0;
50bd6fd3 DK	579	for (std::vector<std::string>::const_iterator p = patches.begin();
50bd6fd3 DK	580	p != patches.end(); ++p)
36795154	581	{
50bd6fd3	582	if (p->compare(0, baseName.length(), baseName) == 0)
36795154 DK	583	{
	584	HashStringList const ExpectedHashes = ReadExpectedHashesForPatch(seen_patches, Message);
	585	if (ExpectedHashes.usable() == false)
	586	return _error->Error("No hashes found for uncompressed patch %d: %s", seen_patches, p->c_str());
	587	patchfiles.push_back(PDiffFile(*p, ExpectedHashes));
	588	++seen_patches;
	589	}
	590	}
dbd5418b AT	591	}
	592
	593	std::string patch_name;
36795154 DK	594	for (std::vector<PDiffFile>::iterator I = patchfiles.begin();
36795154 DK	595	I != patchfiles.end();
25d99f3b	596	++I)
dbd5418b	597	{
36795154	598	patch_name = I->FileName;
dbd5418b AT	599	if (Debug == true)
	600	std::clog << "Patching " << Path << " with " << patch_name
	601	<< std::endl;
	602
50bd6fd3 DK	603	FileFd p;
	604	// all patches are compressed, even if the name doesn't reflect it
	605	if (p.Open(patch_name, FileFd::ReadOnly, FileFd::Gzip) == false) {
	606	std::cerr << "Could not open patch file " << patch_name << std::endl;
	607	_error->DumpErrors(std::cerr);
dbd5418b AT	608	abort();
dbd5418b AT	609	}
36795154 DK	610	Hashes patch_hash(I->ExpectedHashes);
36795154 DK	611	patch.read_diff(p, &patch_hash);
50bd6fd3	612	p.Close();
36795154 DK	613	HashStringList const hsl = patch_hash.GetHashStringList();
	614	if (hsl != I->ExpectedHashes)
	615	return _error->Error("Patch %s doesn't have the expected hashsum", patch_name.c_str());
dbd5418b AT	616	}
	617
	618	if (Debug == true)
	619	std::clog << "Applying patches against " << Path
	620	<< " and writing results to " << Itm->DestFile
	621	<< std::endl;
	622
	623	FILE *inp = fopen(Path.c_str(), "r");
	624	FILE *out = fopen(Itm->DestFile.c_str(), "w");
	625
9224ce3d	626	Hashes hash(Itm->ExpectedHashes);
dbd5418b AT	627
	628	patch.apply_against_file(out, inp, &hash);
	629
	630	fclose(out);
	631	fclose(inp);
	632
	633	if (Debug == true) {
	634	std::clog << "rred: finished file patching of " << Path << "." << std::endl;
	635	}
	636
	637	struct stat bufbase, bufpatch;
	638	if (stat(Path.c_str(), &bufbase) != 0 \|\|
	639	stat(patch_name.c_str(), &bufpatch) != 0)
	640	return _error->Errno("stat", _("Failed to stat"));
	641
246bbb61	642	struct timeval times[2];
25d99f3b DK	643	times[0].tv_sec = bufbase.st_atime;
25d99f3b DK	644	times[1].tv_sec = bufpatch.st_mtime;
246bbb61 DK	645	times[0].tv_usec = times[1].tv_usec = 0;
	646	if (utimes(Itm->DestFile.c_str(), times) != 0)
	647	return _error->Errno("utimes",_("Failed to set modification time"));
dbd5418b AT	648
	649	if (stat(Itm->DestFile.c_str(), &bufbase) != 0)
	650	return _error->Errno("stat", _("Failed to stat"));
	651
	652	Res.LastModified = bufbase.st_mtime;
	653	Res.Size = bufbase.st_size;
	654	Res.TakeHashes(hash);
	655	URIDone(Res);
	656
	657	return true;
	658	}
	659
	660	public:
25d99f3b	661	RredMethod() : pkgAcqMethod("2.0",SingleInstance \| SendConfig), Debug(false) {}
bb1293d9	662	};
dbd5418b AT	663
	664	int main(int argc, char **argv)
	665	{
	666	int i;
	667	bool just_diff = true;
	668	Patch patch;
	669
	670	if (argc <= 1) {
	671	RredMethod Mth;
	672	return Mth.Run();
	673	}
	674
	675	if (argc > 1 && strcmp(argv[1], "-f") == 0) {
	676	just_diff = false;
	677	i = 2;
	678	} else {
	679	i = 1;
	680	}
	681
	682	for (; i < argc; i++) {
50bd6fd3 DK	683	FileFd p;
	684	if (p.Open(argv[i], FileFd::ReadOnly) == false) {
	685	_error->DumpErrors(std::cerr);
dbd5418b AT	686	exit(1);
dbd5418b AT	687	}
36795154	688	patch.read_diff(p, NULL);
dbd5418b AT	689	}
	690
	691	if (just_diff) {
	692	patch.write_diff(stdout);
	693	} else {
	694	FILE out, inp;
	695	out = stdout;
	696	inp = stdin;
	697
	698	patch.apply_against_file(out, inp);
	699	}
	700	return 0;
2e178d1c	701	}