explain what can be done with the new data

record package metadata that describes co-installability

Specifically all entries in the Conflicts header are saved in the
conflict table, all entries in the Provides header are saved in the
provide table (to cover conflicts with virtual packages) and packages
using dpkg-divert in preinst get a magic "_dpkg-divert" entry in their
conflict table. With this metadata it should be possible to compute
undeclared file conflicts.

Merge branch updatesharing-eqclass

spell check comments

fix spelling mistake

Reported-By: Stefan Kaltenbrunner

webapp: fix eqclass usage in package comparison

When comparing two packages, objects would be considered duplicates
without considering whether the respective hash functions are comparable
by checking their equivalence classes. The current set of hash functions
does not expose this bug.

update_sharing: weaken assumptions about db layout

Hash functions are partitioned into equivalence classes. We are
generally only interested in sharing among hash functions with the same
equivalence class, but the algorithm would compute any sharing. While
the current layout never produces the same hashes for functions in
difference equivalence classes (for different output length), that may
change in future.

Also allow hash functions, that belong to no equivalence class at all
(eqclass = NULL) as a means to add additional metadata to content
without computing any sharing for it.

blacklist content rather than hashes

Otherwise the gzip hash cannot tell the empty stream and the
compressed empty stream apart.

GzipDecompressor: don't treat checksum as garbage trailer

DecompressedHash should fail on trailing input

Otherwise all files smaller than 10 bytes are successfully hashed to the
hash of the empty input when using the GzipDecompressor.

Reported-By: Olly Betts

work around python-debian's #670679

webapp: open cursors less often

On the main instance opening cursors equals initiating a connection.
Unfortunately sqlite3.Connection.close does not close filedescriptors.
So just open less cursors to leak filedescriptors less often.

webapp: close database cursors

Leaking them can result in running out of available filedescriptors.

webapp: serve static files from /static

add option -d --database for db path to all scripts

autoimport: avoid hard coded temporary directory

importpkg: move library-like parts to dedup.debpkg

importpkg: don't blacklist boring gzip_sha512 hashes

 * In practise there are very few compressed files with trivial hashes.
 * Blacklisting these values results in false positives in the gzip
   issues.

make debian version_compare available in sql

webapp templates: add an anchor for file issues

model comparability as an equivalence relation

webapp has had a relation hash_functions, that modeled "comparable
functions". Images should not be compares to other files, since it makes
no sense to store them as the RGBA stream, that is being hashed. This
comparability property resembles an equivalence relation. So the
function table gains a column eqclass. Each class is represented by a
number and functions are statically assigned to these classes. Now the
filtering happens in SQL instead of Python.

support hashing gif images

 * Rename "image_sha512" to "png_sha512".
 * dedup.image.ImageHash is now a base class for image hashes such as
   PNGHash and GIFHash.
 * Enable both hashes in importpkg.
 * Fix README.
 * Add new hash combinations to webapp.
 * Add "gif file not named *.gif" to issues in update_sharing.
 * Add redirect for "image_sha512" to webapp for backwards
   compatibility.

templates/binary: space between package and compare

templates: wiki.d.o redirects to https now

fix update_sharing to work after functionid merge

importpkg.py: support uncompressed data.tar

also move the static directory into the dedup package

move templates to dedup package

They cluttered webapp.py and now vim can give proper highlighting for
the templates.

verify package hashes when importing via http

Merge branch functionid

Actual savings on the full data set are around 7%.

Conflicts:
README

display "issues" with files in package view

Currently this is invalid .gz files and png files not named .png.

README: foo.PNG is also a valid png name

readyaml: cache the whole function table

This should reduce the query bandwidth to the rdbms.

webapp: make html for index valid

README: fix typo in query

webapp: remove unused function

adapt queries in README to new schema

schema: reference hash functions by integer key

This already worked quite well for package.id. On a test data set of 5%
size this transformation reduces the database size by about 4%.

schema: extend content_package_index

We can avoid a b-tree sort in the package comparison of the web app, if
the package index, also provides a size.

Merge branch 'packageid'

importpkg: simplify state logic

importpkg: split process_package to process_control

schema: reference package table by integer key

One approach to improve performance is to reduce the database size. A
package name takes up 15 bytes in average. A number of a package takes
up two bytes. Multiply that difference with the number of references and
it should be noticeably. A small test set show a reduction by 10%.

schema.sql: drop unused index

sharing_package_index is a sub-index of sharing_insert_index and
therefore unnecessary.

README: explain update_sharing.py

Merge branch yamlimport

 + Way faster on multiple cores.
 + More reliable, cause http connections do not time out when the db
   blocks.
 - Way slower on single core with contended io path. No clue why.
   Still update_sharing.py makes up the bulk of processing time.

webapp: fix hash example link after git upload

The git binary changed and so did its hash. Choosing a more stable
example now: The GPL-3.

autoimport: don't fork for readyaml

This appears to be a huge performance boost.

autoimport: support processing individual files

This gets back the original functionality of importpkg.py.

split the import phase to a yaml stream

importpkg.py now emits a yaml stream instead of updating the database.
The acutual updating now happens in readyaml.py. In this process
autoimport.py was significantly reworked to import packages in parallel.

dedup.image: img.convert can also raise that crazy stuff

webapp: declare html5 and utf-8

webapp: enrich comparison page with version info

fix attribution of logo

I remembered the wrong name. The logo was made by Sune Vuorela.

webapp: markup error in /source template

webapp: validator complained about <link> with sizes

webapp: reference favicon from base.html

added favicon.ico

Authored: Cyril Brulebois

webapp: use jinja's filesizeformat

Except it doesn't work, so replace it with our version. At least we
might be able to drop this code in a future update.

webapp: reduce size of comparison output

Only add rowspan when it carries a meaning.

webapp: add a css class binary-package

webapp: total_size is None if num_files is 0

webapp: color filenames when hovering them

webapp: turn the <br> after filename into a style

move css to /style.css

webapp: make filenames css styleable

webapp: top-align fields in /compare pages

Suggested by Paul Wise.

fix markup in base.html

implement the /compare/pkg1/pkg2 page differently

The original version had two major drawbacks:
 1) The SQL query used would cause a btree sort, so the time waiting
    for the first output was rather long.
 2) For packages with many equal files, the output would grow with
    O(n^2).

Thanks to the suggestions by Christine Grohne and Klaus Aehlig. The
approach now groups files in package1 by their main hash value (sha512).
It also does some work SQL was designed to solve manually now. To speed
up page generation a new caching table was added identifying which files
have corresponding shared files.

webapp: added some useful notes

base.html: add link to wiki.debian.org

README: improve query after schemachange

webapp: fix problem from the previous merge

Merge branch schemachange

webapp: report correct sizes

webapp: remove broken assert

Fails on long inputs.

dedup.image: mask errors from PIL

dedup.arreader: missing bytes marker

move ArReader from importpkg to dedup.arreader

Also document it.

README: update queries to match content table split

split content table to a hash table

In the old content table (package, filename, size) would be the same for
multiple hash functions. Now the schema represents that each file has
precisely one size, but multiple hashes.

webapp: drop unused function compute_sharedstats

The sharing table works great and I don't want to adapt it for the next
step in the schema change.

use "ON DELETE CASCADE" clauses

enable enforcing foreign keys

schema.sql: remove unsatisfiable foreign key

In the dependency table we will insert dependencies on packages which
are not tracked. This happens during initial import and for virtual
packages. Therefore the "required" column cannot be a foreign key.

schema.sql: annotat foreign keys of sharing

integrate the source table into the package table

README: explain queries

README: added interesting query

webapp: added /source/<pkg> page

webapp: helper function function_combination

importpkg: source header may contain a version

webapp: fix index template

Apparently not all browsers understand <a ... /> in all rendering modes.

webapp: use caching table "shared" for /binary page

webapp: generate /comparison pages in constant-space

importpkg: record the source package relationship

update_sharing: wrong database name

add sharing table

The sharing table is a cache for the /binary web pages. It essentially
contains the numbers presented. This caching table is not automatically
populated. It needs to be reconstructed after every (group of) package
imports.

update README

 * Tell about schema.sql.
 * Explain WAL.

move fetchiter from webapp to dedup.utils