1 // Copyright (c) 2014 Anthony Towns
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.
10 #include <apt-pkg/init.h>
11 #include <apt-pkg/fileutl.h>
12 #include <apt-pkg/error.h>
13 #include <apt-pkg/strutl.h>
14 #include <apt-pkg/hashes.h>
15 #include <apt-pkg/configuration.h>
16 #include "aptmethod.h"
34 #define BLOCK_SIZE (512*1024)
42 explicit MemBlock(size_t size
) : size(size
), next(NULL
)
44 free
= start
= new char[size
];
47 size_t avail(void) { return size
- (free
- start
); }
52 free
= start
= new char[BLOCK_SIZE
];
68 char *add_easy(char *src
, size_t len
, char *last
)
71 for (MemBlock
*k
= this; k
; k
= k
->next
) {
72 if (k
->free
== last
) {
73 if (len
<= k
->avail()) {
74 char *n
= k
->add(src
, len
);
82 } else if (last
>= start
&& last
< free
) {
90 char *add(char *src
, size_t len
) {
93 if (len
> BLOCK_SIZE
) {
94 next
= new MemBlock(len
);
99 return next
->add(src
, len
);
103 memcpy(dst
, src
, len
);
111 * 1. write out <offset> lines unchanged
112 * 2. skip <del_cnt> lines from source
113 * 3. write out <add_cnt> lines (<add>/<add_len>)
117 size_t add_cnt
; /* lines */
118 size_t add_len
; /* bytes */
121 explicit Change(size_t off
)
124 del_cnt
= add_cnt
= add_len
= 0;
128 /* actually, don't write <lines> lines from <add> */
129 void skip_lines(size_t lines
)
132 char *s
= (char*) memchr(add
, '\n', add_len
);
135 add_len
-= (s
- add
);
140 assert(add_cnt
== 0);
151 std::list
<struct Change
> changes
;
152 std::list
<struct Change
>::iterator where
;
153 size_t pos
; // line number is as far left of iterator as possible
155 bool pos_is_okay(void) const
159 std::list
<struct Change
>::const_iterator x
;
160 for (x
= changes
.begin(); x
!= where
; ++x
) {
161 assert(x
!= changes
.end());
162 cpos
+= x
->offset
+ x
->add_cnt
;
172 where
= changes
.end();
176 std::list
<struct Change
>::iterator
begin(void) { return changes
.begin(); }
177 std::list
<struct Change
>::iterator
end(void) { return changes
.end(); }
179 std::list
<struct Change
>::reverse_iterator
rbegin(void) { return changes
.rbegin(); }
180 std::list
<struct Change
>::reverse_iterator
rend(void) { return changes
.rend(); }
182 void add_change(Change c
) {
183 assert(pos_is_okay());
184 go_to_change_for(c
.offset
);
185 assert(pos
+ where
->offset
== c
.offset
);
187 delete_lines(c
.del_cnt
);
188 assert(pos
+ where
->offset
== c
.offset
);
190 assert(pos_is_okay());
191 if (where
->add_len
> 0)
193 assert(where
->add_len
== 0 && where
->add_cnt
== 0);
195 where
->add_len
= c
.add_len
;
196 where
->add_cnt
= c
.add_cnt
;
199 assert(pos_is_okay());
201 assert(pos_is_okay());
207 while (where
->offset
== 0 && where
!= changes
.begin()) {
210 std::list
<struct Change
>::iterator next
= where
;
213 while (next
!= changes
.end() && next
->offset
== 0) {
214 where
->del_cnt
+= next
->del_cnt
;
216 if (next
->add
== NULL
) {
217 next
= changes
.erase(next
);
218 } else if (where
->add
== NULL
) {
219 where
->add
= next
->add
;
220 where
->add_len
= next
->add_len
;
221 where
->add_cnt
= next
->add_cnt
;
222 next
= changes
.erase(next
);
229 void go_to_change_for(size_t line
)
231 while(where
!= changes
.end()) {
236 if (pos
+ where
->offset
+ where
->add_cnt
<= line
) {
240 // line is somewhere in this slot
241 if (line
< pos
+ where
->offset
) {
243 } else if (line
== pos
+ where
->offset
) {
251 /* it goes before this patch */
255 void new_change(void) { insert(where
->offset
); }
257 void insert(size_t offset
)
259 assert(pos_is_okay());
260 assert(where
== changes
.end() || offset
<= where
->offset
);
261 if (where
!= changes
.end())
262 where
->offset
-= offset
;
263 changes
.insert(where
, Change(offset
));
265 assert(pos_is_okay());
268 void split(size_t offset
)
270 assert(pos_is_okay());
272 assert(where
->offset
< offset
);
273 assert(offset
< where
->offset
+ where
->add_cnt
);
275 size_t keep_lines
= offset
- where
->offset
;
277 Change
before(*where
);
281 where
->skip_lines(keep_lines
);
283 before
.add_cnt
= keep_lines
;
284 before
.add_len
-= where
->add_len
;
286 changes
.insert(where
, before
);
288 assert(pos_is_okay());
291 void delete_lines(size_t cnt
)
293 std::list
<struct Change
>::iterator x
= where
;
294 assert(pos_is_okay());
305 if (x
== changes
.end()) {
313 where
->del_cnt
+= del
;
316 assert(pos_is_okay());
320 assert(pos_is_okay());
322 pos
-= where
->offset
+ where
->add_cnt
;
323 assert(pos_is_okay());
327 assert(pos_is_okay());
328 pos
+= where
->offset
+ where
->add_cnt
;
330 assert(pos_is_okay());
335 FileChanges filechanges
;
338 static bool retry_fwrite(char *b
, size_t l
, FileFd
&f
, Hashes
*hash
)
340 if (f
.Write(b
, l
) == false)
343 hash
->Add((unsigned char*)b
, l
);
347 static void dump_rest(FileFd
&o
, FileFd
&i
, Hashes
*hash
)
349 char buffer
[BLOCK_SIZE
];
350 unsigned long long l
= 0;
351 while (i
.Read(buffer
, sizeof(buffer
), &l
)) {
352 if (l
==0 || !retry_fwrite(buffer
, l
, o
, hash
))
357 static void dump_lines(FileFd
&o
, FileFd
&i
, size_t n
, Hashes
*hash
)
359 char buffer
[BLOCK_SIZE
];
361 if (i
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
363 size_t const l
= strlen(buffer
);
364 if (l
== 0 || buffer
[l
-1] == '\n')
366 retry_fwrite(buffer
, l
, o
, hash
);
370 static void skip_lines(FileFd
&i
, int n
)
372 char buffer
[BLOCK_SIZE
];
374 if (i
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
376 size_t const l
= strlen(buffer
);
377 if (l
== 0 || buffer
[l
-1] == '\n')
382 static void dump_mem(FileFd
&o
, char *p
, size_t s
, Hashes
*hash
) {
383 retry_fwrite(p
, s
, o
, hash
);
388 bool read_diff(FileFd
&f
, Hashes
* const h
)
390 char buffer
[BLOCK_SIZE
];
391 bool cmdwanted
= true;
393 Change
ch(std::numeric_limits
<size_t>::max());
394 if (f
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
395 return _error
->Error("Reading first line of patchfile %s failed", f
.Name().c_str());
403 s
= strtoul(buffer
, &m
, 10);
404 if (unlikely(m
== buffer
|| s
== std::numeric_limits
<unsigned long>::max() || errno
!= 0))
405 return _error
->Error("Parsing patchfile %s failed: Expected an effected line start", f
.Name().c_str());
406 else if (*m
== ',') {
408 e
= strtol(m
, &c
, 10);
409 if (unlikely(m
== c
|| e
== std::numeric_limits
<unsigned long>::max() || errno
!= 0))
410 return _error
->Error("Parsing patchfile %s failed: Expected an effected line end", f
.Name().c_str());
412 return _error
->Error("Parsing patchfile %s failed: Effected lines end %lu is before start %lu", f
.Name().c_str(), e
, s
);
418 return _error
->Error("Parsing patchfile %s failed: Effected line is after previous effected line", f
.Name().c_str());
429 if (unlikely(s
== 0))
430 return _error
->Error("Parsing patchfile %s failed: Change command can't effect line zero", f
.Name().c_str());
436 ch
.del_cnt
= e
- s
+ 1;
439 if (unlikely(s
== 0))
440 return _error
->Error("Parsing patchfile %s failed: Delete command can't effect line zero", f
.Name().c_str());
442 ch
.del_cnt
= e
- s
+ 1;
446 filechanges
.add_change(ch
);
449 return _error
->Error("Parsing patchfile %s failed: Unknown command", f
.Name().c_str());
451 } else { /* !cmdwanted */
452 if (strcmp(buffer
, ".\n") == 0) {
454 filechanges
.add_change(ch
);
460 last
= ch
.add
+ ch
.add_len
;
462 add
= add_text
.add_easy(buffer
, l
, last
);
468 filechanges
.add_change(ch
);
471 ch
.offset
+= ch
.add_cnt
;
478 } while(f
.ReadLine(buffer
, sizeof(buffer
)));
482 void write_diff(FileFd
&f
)
484 unsigned long long line
= 0;
485 std::list
<struct Change
>::reverse_iterator ch
;
486 for (ch
= filechanges
.rbegin(); ch
!= filechanges
.rend(); ++ch
) {
487 line
+= ch
->offset
+ ch
->del_cnt
;
490 for (ch
= filechanges
.rbegin(); ch
!= filechanges
.rend(); ++ch
) {
491 std::list
<struct Change
>::reverse_iterator mg_i
, mg_e
= ch
;
492 while (ch
->del_cnt
== 0 && ch
->offset
== 0)
495 if (unlikely(ch
== filechanges
.rend()))
500 if (ch
->add_cnt
> 0) {
501 if (ch
->del_cnt
== 0) {
502 strprintf(buf
, "%llua\n", line
);
503 } else if (ch
->del_cnt
== 1) {
504 strprintf(buf
, "%lluc\n", line
+1);
506 strprintf(buf
, "%llu,%lluc\n", line
+1, line
+ch
->del_cnt
);
508 f
.Write(buf
.c_str(), buf
.length());
512 dump_mem(f
, mg_i
->add
, mg_i
->add_len
, NULL
);
513 } while (mg_i
-- != mg_e
);
516 f
.Write(buf
.c_str(), buf
.length());
517 } else if (ch
->del_cnt
== 1) {
518 strprintf(buf
, "%llud\n", line
+1);
519 f
.Write(buf
.c_str(), buf
.length());
520 } else if (ch
->del_cnt
> 1) {
521 strprintf(buf
, "%llu,%llud\n", line
+1, line
+ch
->del_cnt
);
522 f
.Write(buf
.c_str(), buf
.length());
528 void apply_against_file(FileFd
&out
, FileFd
&in
, Hashes
*hash
= NULL
)
530 std::list
<struct Change
>::iterator ch
;
531 for (ch
= filechanges
.begin(); ch
!= filechanges
.end(); ++ch
) {
532 dump_lines(out
, in
, ch
->offset
, hash
);
533 skip_lines(in
, ch
->del_cnt
);
534 dump_mem(out
, ch
->add
, ch
->add_len
, hash
);
536 dump_rest(out
, in
, hash
);
541 class RredMethod
: public aptMethod
{
546 std::string FileName
;
547 HashStringList ExpectedHashes
;
548 PDiffFile(std::string
const &FileName
, HashStringList
const &ExpectedHashes
) :
549 FileName(FileName
), ExpectedHashes(ExpectedHashes
) {}
552 HashStringList
ReadExpectedHashesForPatch(unsigned int const patch
, std::string
const &Message
)
554 HashStringList ExpectedHashes
;
555 for (char const * const * type
= HashString::SupportedHashes(); *type
!= NULL
; ++type
)
558 strprintf(tagname
, "Patch-%d-%s-Hash", patch
, *type
);
559 std::string
const hashsum
= LookupTag(Message
, tagname
.c_str());
560 if (hashsum
.empty() == false)
561 ExpectedHashes
.push_back(HashString(*type
, hashsum
));
563 return ExpectedHashes
;
567 virtual bool URIAcquire(std::string
const &Message
, FetchItem
*Itm
) APT_OVERRIDE
{
568 Debug
= _config
->FindB("Debug::pkgAcquire::RRed", false);
570 std::string Path
= Get
.Host
+ Get
.Path
; // rred:/path - no host
573 Res
.Filename
= Itm
->DestFile
;
574 if (Itm
->Uri
.empty())
576 Path
= Itm
->DestFile
;
577 Itm
->DestFile
.append(".result");
581 std::vector
<PDiffFile
> patchfiles
;
584 if (FileExists(Path
+ ".ed") == true)
586 HashStringList
const ExpectedHashes
= ReadExpectedHashesForPatch(0, Message
);
587 std::string
const FileName
= Path
+ ".ed";
588 if (ExpectedHashes
.usable() == false)
589 return _error
->Error("No hashes found for uncompressed patch: %s", FileName
.c_str());
590 patchfiles
.push_back(PDiffFile(FileName
, ExpectedHashes
));
594 _error
->PushToStack();
595 std::vector
<std::string
> patches
= GetListOfFilesInDir(flNotFile(Path
), "gz", true, false);
596 _error
->RevertToStack();
598 std::string
const baseName
= Path
+ ".ed.";
599 unsigned int seen_patches
= 0;
600 for (std::vector
<std::string
>::const_iterator p
= patches
.begin();
601 p
!= patches
.end(); ++p
)
603 if (p
->compare(0, baseName
.length(), baseName
) == 0)
605 HashStringList
const ExpectedHashes
= ReadExpectedHashesForPatch(seen_patches
, Message
);
606 if (ExpectedHashes
.usable() == false)
607 return _error
->Error("No hashes found for uncompressed patch %d: %s", seen_patches
, p
->c_str());
608 patchfiles
.push_back(PDiffFile(*p
, ExpectedHashes
));
614 std::string patch_name
;
615 for (std::vector
<PDiffFile
>::iterator I
= patchfiles
.begin();
616 I
!= patchfiles
.end();
619 patch_name
= I
->FileName
;
621 std::clog
<< "Patching " << Path
<< " with " << patch_name
625 Hashes
patch_hash(I
->ExpectedHashes
);
626 // all patches are compressed, even if the name doesn't reflect it
627 if (p
.Open(patch_name
, FileFd::ReadOnly
, FileFd::Gzip
) == false ||
628 patch
.read_diff(p
, &patch_hash
) == false)
630 _error
->DumpErrors(std::cerr
, GlobalError::DEBUG
, false);
634 HashStringList
const hsl
= patch_hash
.GetHashStringList();
635 if (hsl
!= I
->ExpectedHashes
)
636 return _error
->Error("Hash Sum mismatch for uncompressed patch %s", patch_name
.c_str());
640 std::clog
<< "Applying patches against " << Path
641 << " and writing results to " << Itm
->DestFile
645 if (inp
.Open(Path
, FileFd::ReadOnly
, FileFd::Extension
) == false)
647 std::cerr
<< "FAILED to open inp " << Path
<< std::endl
;
648 return _error
->Error("Failed to open inp %s", Path
.c_str());
650 if (out
.Open(Itm
->DestFile
, FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
, FileFd::Extension
) == false)
652 std::cerr
<< "FAILED to open out " << Itm
->DestFile
<< std::endl
;
653 return _error
->Error("Failed to open out %s", Itm
->DestFile
.c_str());
656 Hashes
hash(Itm
->ExpectedHashes
);
657 patch
.apply_against_file(out
, inp
, &hash
);
662 if (_error
->PendingError() == true) {
663 std::cerr
<< "FAILED to read or write files" << std::endl
;
668 std::clog
<< "rred: finished file patching of " << Path
<< "." << std::endl
;
671 struct stat bufbase
, bufpatch
;
672 if (stat(Path
.c_str(), &bufbase
) != 0 ||
673 stat(patch_name
.c_str(), &bufpatch
) != 0)
674 return _error
->Errno("stat", _("Failed to stat %s"), Path
.c_str());
676 struct timeval times
[2];
677 times
[0].tv_sec
= bufbase
.st_atime
;
678 times
[1].tv_sec
= bufpatch
.st_mtime
;
679 times
[0].tv_usec
= times
[1].tv_usec
= 0;
680 if (utimes(Itm
->DestFile
.c_str(), times
) != 0)
681 return _error
->Errno("utimes",_("Failed to set modification time"));
683 if (stat(Itm
->DestFile
.c_str(), &bufbase
) != 0)
684 return _error
->Errno("stat", _("Failed to stat %s"), Itm
->DestFile
.c_str());
686 Res
.LastModified
= bufbase
.st_mtime
;
687 Res
.Size
= bufbase
.st_size
;
688 Res
.TakeHashes(hash
);
695 RredMethod() : aptMethod("rred", "2.0", SendConfig
), Debug(false) {}
698 int main(int argc
, char **argv
)
701 bool just_diff
= true;
706 return RredMethod().Run();
709 // Usage: rred -t input output diff ...
710 if (argc
> 1 && strcmp(argv
[1], "-t") == 0) {
711 // Read config files so we see compressors.
712 pkgInitConfig(*_config
);
716 } else if (argc
> 1 && strcmp(argv
[1], "-f") == 0) {
723 for (; i
< argc
; i
++) {
725 if (p
.Open(argv
[i
], FileFd::ReadOnly
) == false) {
726 _error
->DumpErrors(std::cerr
);
729 if (patch
.read_diff(p
, NULL
) == false)
731 _error
->DumpErrors(std::cerr
);
738 std::cerr
<< "Patching " << argv
[2] << " into " << argv
[3] << "\n";
739 inp
.Open(argv
[2], FileFd::ReadOnly
,FileFd::Extension
);
740 out
.Open(argv
[3], FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
, FileFd::Extension
);
741 patch
.apply_against_file(out
, inp
);
743 } else if (just_diff
) {
745 out
.OpenDescriptor(STDOUT_FILENO
, FileFd::WriteOnly
| FileFd::Create
);
746 patch
.write_diff(out
);
750 out
.OpenDescriptor(STDOUT_FILENO
, FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
);
751 inp
.OpenDescriptor(STDIN_FILENO
, FileFd::ReadOnly
);
752 patch
.apply_against_file(out
, inp
);