Debian Bug report logs - #848049
diffoscope: Add detection of order-only differences in plain text formats

Toggle useless messages

Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: Emanuel Bronshtein <e3amn2l@gmx.com>

To: Debian Bug Tracking System <submit@bugs.debian.org>

Subject: diffoscope: Add detection for order only differnce by lines

Date: Tue, 13 Dec 2016 18:16:56 +0200

Package: diffoscope
Severity: wishlist

Please add detection of order only variations in plain text files (TXT/HTML files)
in similar way like the recent addition of order only difference in JSON output in:
https://anonscm.debian.org/cgit/reproducible/diffoscope.git/commit/?id=8faf040767b892e1cf19d4ec2965a29301b9ae40

Thus allows easier/faster classification of issues, for example the below issues:

random_order_in_md5sums
clilibs_line_order
varying_ordering_in_data_tar_gz_or_control_tar_gz
random_order_in_tarball
qt_translate_noop_nondeterminstic_ordering
random_order_in_ibus_table_createdb_output
db_ordering_noop_detect
random_ordering_in_pom
random_order_in_sisu_javax_inject_named
sphinx_htmlhelp_readdir_sensitive
nondeterminstic_ordering_in_gsettings_glib_enums_xml
valac_permutes_get_type_calls

share the same 'order only difference', it can be implemented by merging all the changed lines in file A (first build) vs same file B (second build), if there is the same amount of lines it's means that there is no other difference except ordering.

Message #12 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Маша Глухова <siamezzze@gmail.com>

To: 848049@bugs.debian.org

Subject: Re: diffoscope: Add detection of order-only differences in plain text formats

Date: Sat, 24 Dec 2016 18:14:16 +0000

[Message part 1 (text/plain, inline)]

I believe the attached patch would provide the requested functionality.

[Message part 2 (text/html, inline)]

[0001-Add-detection-of-order-only-difference-in-plain-text.patch (text/x-diff, attachment)]

Message #17 received at 848049-close@bugs.debian.org (full text, mbox, reply):

From: Chris Lamb <lamby@debian.org>

To: 848049-close@bugs.debian.org

Subject: Bug#848049: fixed in diffoscope 66

Date: Sat, 24 Dec 2016 19:48:23 +0000

Source: diffoscope
Source-Version: 66

We believe that the bug you reported is fixed in the latest version of
diffoscope, which is due to be installed in the Debian FTP archive.

A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 848049@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Chris Lamb <lamby@debian.org> (supplier of updated diffoscope package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@ftp-master.debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Format: 1.8
Date: Sat, 24 Dec 2016 19:18:30 +0000
Source: diffoscope
Binary: diffoscope
Architecture: source
Version: 66
Distribution: unstable
Urgency: medium
Maintainer: Reproducible builds folks <reproducible-builds@lists.alioth.debian.org>
Changed-By: Chris Lamb <lamby@debian.org>
Description:
 diffoscope - in-depth comparison of files, archives, and directories
Closes: 848049 849142
Changes:
 diffoscope (66) unstable; urgency=medium
 .
   [ Chris Lamb ]
   * Update dex_expected_diffs and test requirement to ensure test compatibility
     with enjarify >= 1.0.3. (Closes: #849142)
   * Print the detected version in @skip_unless_tool_is_at_least test utility.
 .
   [ Maria Glukhova ]
   * Add detection of order-only difference in plain text format. (Closes: #848049)
 .
   [ anthraxx ]
   * Add OpenSSH Arch package to Recommends.
Checksums-Sha1:
 90f5202c59082bfa9f446c9cb61f785b82537c98 2923 diffoscope_66.dsc
 a83d0ae72f61eeb2ac8166b313d7c0d38103f90c 315872 diffoscope_66.tar.xz
Checksums-Sha256:
 7a5e88ce749f0b3169e2fdb46b3e6fd5c13df26d6e54762fb73deff281f3ee84 2923 diffoscope_66.dsc
 fe41876d0c1889663b963090cc2f30d58e1afe8bb3a16e61118d6ad81deed3f4 315872 diffoscope_66.tar.xz
Files:
 da0c63fe0280c90dd49ff0efb54903ea 2923 devel optional diffoscope_66.dsc
 fbfb52a82f331a5bd8ebd6ebcbdb45f5 315872 devel optional diffoscope_66.tar.xz

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCAAdFiEEwv5L0nHBObhsUz5GHpU+J9QxHlgFAlhezDEACgkQHpU+J9Qx
Hlg4XxAAwhkGTmPkmIEQ7Gph01RCKCjtkOdjagwDIPE3nBzp0NBjSksbyi8QkY4n
yfjk8bLjX01YRGegqaT0CXLtbsCjsTBabaKgh4X1mKn/51nghuOFChIeQRG/rsA0
/eYLAJAAQ/ag2siEiPoISa5YCWRNLYV8K0JUtJnEKCmqPvVxk5Q8zKFaJqUBO8QV
Om1rV1RBUGb863UUMpOYZCXkaN1gvtv+/u3l4yhr3SyV0cEquh5JiDMLcl27yAlB
7gDw4Nb5UuwkNTlUr+5Fkc5GsTeW3A9lsI61VEQPTqc7zwGRB5LjjMVr2+muGfjR
x9ZNtrDZozjwB/6ufnueVoPIE9sHv4IgXvyU5biSk19oN6ZXYHmw7ekZwXKyI7Rm
zGzfJIkIC7Fu4LL5bsUYD6atjQWpyxwvcFCVFv3wmAhN/sQsUs/V/ljUehfUTnEw
rOloYZdALE8E8TBTMpPXIAJNrnM73wMIOpI1wOrFgYYCTsaSVf/NTLzKZAm7FDXy
JWTM5UXeI8wDT30hvCQCFNxVgEMR3KeR3ipN/YqUWBdlilFU4WAEVlsdReV2PC9t
DpYF69VX0J7+UId+O8frmW9jDwyBpqR3TmnCmd9OL99Oozg595nL+rwX2ZLMCoFU
+m6nBaU9/Q/l8bEKcjnXoSncsbHtuJ0la4RqTr20opEiRLRSAQM=
=M1F+
-----END PGP SIGNATURE-----

Message #22 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Daniel Shahaf <danielsh@apache.org>

To: 848049@bugs.debian.org

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Sat, 24 Dec 2016 20:28:34 +0000

Маша Глухова wrote on Sat, Dec 24, 2016 at 18:14:16 +0000:
> +def order_only_difference(unified_diff):
> +    diff_lines = unified_diff.splitlines()
> +    added_lines = [line[1:] for line in diff_lines if line.startswith('+')]
> +    removed_lines = [line[1:] for line in diff_lines if line.startswith('-')]
> +    # Faster check: does number of lines match?
> +    if len(added_lines) != len(removed_lines):
> +        return False
> +    # Counter stores line and number of its occurrences.
> +    return sorted(added_lines) == sorted(removed_lines)

What happens if one of the files has a trailing newline and one does
not?  Strictly speaking, that's not an "ordering only difference", but
this function doesn't seem to handle this case.

Example:

% diff -u <(echo foo) <(printf foo) 
--- /proc/self/fd/11	2016-12-24 20:24:22.064115616 +0000
+++ /proc/self/fd/12	2016-12-24 20:24:22.064115616 +0000
@@ -1 +1 @@
-foo
+foo
\ No newline at end of file

Cheers,

Daniel

Message #27 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: Маша Глухова <siamezzze@gmail.com>, 848049@bugs.debian.org

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Sun, 25 Dec 2016 12:37:21 +0100

[Message part 1 (text/plain, inline)]

Маша Глухова:
> I believe the attached patch would provide the requested functionality.

Nice work! :)

> From: Maria Glukhova <siamezzze@gmail.com>
> Date: Sat, 24 Dec 2016 12:29:57 +0200
> Subject: [PATCH] Add detection of order-only difference in plain text format.
> 
> Detect if the text files' contents differ only in line ordering, and give an appropriate comment.
> […]
> +def order_only_difference(unified_diff):
> +    diff_lines = unified_diff.splitlines()
> +    added_lines = [line[1:] for line in diff_lines if line.startswith('+')]
> +    removed_lines = [line[1:] for line in diff_lines if line.startswith('-')]
> +    # Faster check: does number of lines match?
> +    if len(added_lines) != len(removed_lines):
> +        return False
> +    # Counter stores line and number of its occurrences.
> +    return sorted(added_lines) == sorted(removed_lines)

I guess it's a fine approach to the problem, but I wonder if it would
not be better to use a slightly less accurate strategy that would be
nicer to memory and CPU.

What I have in mind is to incrementally compute a hash value that would
give the same result even if the lines are in different order.

Drawing from discussions on StackOverflow [1], I think doing a sum of
Python's hash() would work. My test was:

    def unordered_hash(lines):
        h = 0
        for line in lines:
            h += hash(line)
        return h

    h1 = unordered_hash(open('tests/data/text_order1').readlines())
    h2 = unordered_hash(open('tests/data/text_order2').readlines())
    print(h1, h2, h1 == h2)

That way, it could probably be implemented directly in the difference
module and work for other file types than just text files.

 [1]: https://stackoverflow.com/questions/30734848/order-independant-hash-algorithm

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[signature.asc (application/pgp-signature, inline)]

Message #32 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Маша Глухова <siamezzze@gmail.com>

To: 848049@bugs.debian.org

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Sun, 25 Dec 2016 14:17:21 +0000

[Message part 1 (text/plain, inline)]

Jeremy,
Thank you for sharing that!
The reason why I did not use some algorihm like that is that it requires to
read files for the second time. Right now, all the actual work with the
content of the files (except for the quick check for has_same_content) is
delegated to diff, and on big files, it occupies most of the time. Assuming
that for big files, reading them from drive would be the bottleneck, I
tried to avoid reading them again, instead working with the result of the
diff.
Still, I would be happily mistaken. I will implement your version and
compare the performance.
Thank you again :)

Maria Glukhova

вс, 25 дек. 2016, 13:37 Jérémy Bobbio <lunar@debian.org>:

> Маша Глухова:
> > I believe the attached patch would provide the requested functionality.
>
> Nice work! :)
>
> > From: Maria Glukhova <siamezzze@gmail.com>
> > Date: Sat, 24 Dec 2016 12:29:57 +0200
> > Subject: [PATCH] Add detection of order-only difference in plain text
> format.
> >
> > Detect if the text files' contents differ only in line ordering, and
> give an appropriate comment.
> > […]
> > +def order_only_difference(unified_diff):
> > +    diff_lines = unified_diff.splitlines()
> > +    added_lines = [line[1:] for line in diff_lines if
> line.startswith('+')]
> > +    removed_lines = [line[1:] for line in diff_lines if
> line.startswith('-')]
> > +    # Faster check: does number of lines match?
> > +    if len(added_lines) != len(removed_lines):
> > +        return False
> > +    # Counter stores line and number of its occurrences.
> > +    return sorted(added_lines) == sorted(removed_lines)
>
> I guess it's a fine approach to the problem, but I wonder if it would
> not be better to use a slightly less accurate strategy that would be
> nicer to memory and CPU.
>
> What I have in mind is to incrementally compute a hash value that would
> give the same result even if the lines are in different order.
>
> Drawing from discussions on StackOverflow [1], I think doing a sum of
> Python's hash() would work. My test was:
>
>     def unordered_hash(lines):
>         h = 0
>         for line in lines:
>             h += hash(line)
>         return h
>
>     h1 = unordered_hash(open('tests/data/text_order1').readlines())
>     h2 = unordered_hash(open('tests/data/text_order2').readlines())
>     print(h1, h2, h1 == h2)
>
> That way, it could probably be implemented directly in the difference
> module and work for other file types than just text files.
>
>  [1]:
> https://stackoverflow.com/questions/30734848/order-independant-hash-algorithm
>
> --
> Lunar                                .''`.
> lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
>                                     `. `'`
>                                       `-
>

[Message part 2 (text/html, inline)]

Message #37 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: Маша Глухова <siamezzze@gmail.com>, 848049@bugs.debian.org

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Sun, 25 Dec 2016 15:28:52 +0100

[Message part 1 (text/plain, inline)]

Hi!

Маша Глухова:
> The reason why I did not use some algorihm like that is that it requires to
> read files for the second time. Right now, all the actual work with the
> content of the files (except for the quick check for has_same_content) is
> delegated to diff, and on big files, it occupies most of the time. Assuming
> that for big files, reading them from drive would be the bottleneck, I
> tried to avoid reading them again, instead working with the result of the
> diff.
> Still, I would be happily mistaken. I will implement your version and
> compare the performance.

You would not have to read the file twice as long as you do the hash
in the difference module, when each line is actually fed to diff.
A similar trick is already used to cope with files that are too long,
see diffoscope.difference.make_feeder_from_raw_reader()

I don't know if my suggestions is a good one. It might not be a good
idea at all. Feel free to discuss it with your mentor before spending
too much time on it.

> Thank you again :)

PS: Please call me Lunar. :)

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[signature.asc (application/pgp-signature, inline)]

Message #42 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Chris Lamb <lamby@debian.org>

To: Jérémy Bobbio <lunar@debian.org>, 848049@bugs.debian.org, Маша Глухова <siamezzze@gmail.com>

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Sun, 25 Dec 2016 15:18:58 +0000

Jérémy Bobbio wrote:

[…]
>             h += hash(line)
[…]

Watch out, using hash() often leads to unreproducible output. :)


Regards,

-- 
      ,''`.
     : :'  :     Chris Lamb
     `. `'`      lamby@debian.org / chris-lamb.co.uk
       `-

Message #47 received at 848049@bugs.debian.org (full text, mbox, reply):

From: Maria Glukhova <siamezzze@gmail.com>

To: Jérémy Bobbio <lunar@debian.org>, "848049@bugs.debian.org" <848049@bugs.debian.org>

Subject: Re: Bug#848049: diffoscope: Add detection of order-only differences in plain text formats

Date: Thu, 12 Jan 2017 10:13:14 +0000

[Message part 1 (text/plain, inline)]

On Sun, 25 Dec 2016 15:28:52 +0100 Jérémy Bobbio <lunar@debian.org> wrote:

Hi Lunar!

> You would not have to read the file twice as long as you do the hash
> in the difference module, when each line is actually fed to diff.
> A similar trick is already used to cope with files that are too long,
> see diffoscope.difference.make_feeder_from_raw_reader()
>

I implemented what I believe was your idea in the attached patch. Thank you
for pointing me to it!
Still, I don't think that feature worth invading into diff.py/diffoscope.py
modules. It doesn't speed up comparison significantly, because call to diff
still takes most of the time on big files with difference only in line
order. Besides, I can't think of many examples of where that feature would
be needed, save from text files.

In any case, thank you again for taking time to provide me with that idea!


Maria

[Message part 2 (text/html, inline)]

[0001-Generic-order-line-difference-for-all-kind-of-inputs.patch (text/x-diff, attachment)]

Send a report that this bug log contains spam.