Issue 6685 - Offer incremental filter list downloads

abp/filters/renderer.py

 # This file is part of Adblock Plus <https://adblockplus.org/>,
 # Copyright (C) 2006-present eyeo GmbH
 #
 # Adblock Plus is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License version 3 as
 # published by the Free Software Foundation.
 #
 # Adblock Plus is distributed in the hope that it will be useful,
 # but WITHOUT ANY WARRANTY; without even the implied warranty of
 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 # GNU General Public License for more details.
 #
 # You should have received a copy of the GNU General Public License
 # along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
 
 """Combine filter list fragments to produce filter lists."""
 
 from __future__ import unicode_literals
 
-import base64
-import hashlib
 import itertools
 import logging
 import time
 
 from .parser import parse_filterlist, Comment, Metadata
 from .sources import NotFound
 
-__all__ = ['IncludeError', 'MissingHeader', 'render_filterlist']

[Vasily Kuznetsov, 2018/08/17 10:30:54]

render_diff() should probably become a public export here.

[rhowell, 2018/08/20 18:21:27]

Done.

+__all__ = ['IncludeError', 'MissingHeader', 'render_filterlist', 'render_diff']
 
 _logger = logging.getLogger(__name__)
 
 
 class IncludeError(Exception):
     """Error in processing include instruction."""
 
     def __init__(self, error, stack):
         stack_str = ' from '.join(map("'{}'".format, reversed(stack)))
         if stack_str:
@@ skipping 79 matching lines @@
     """Insert metadata comment with version (a.k.a. date)."""
     first_line, rest = _first_and_rest(lines)
     version = Metadata('Version', time.strftime('%Y%m%d%H%M', time.gmtime()))
     return itertools.chain([first_line, version], rest)
 
 
 def _remove_duplicates(lines):
     """Remove duplicate metadata and headers."""
     # Always remove checksum -- a checksum coming from a fragment
     # will not match for the rendered list.
-    seen = {'Checksum'}
+    seen = {'checksum'}
     for i, line in enumerate(lines):
         if line.type == 'metadata':
-            if line.key not in seen:
-                seen.add(line.key)
+            key = line.key.lower()
+            if key not in seen:
+                seen.add(key)
                 yield line
         elif line.type == 'header':
             if i == 0:
                 yield line
         else:
             yield line
-
-
-def _insert_checksum(lines):
-    """Add checksum to the filter list.
-
-    See https://adblockplus.org/filters#special-comments for description
-    of the checksum algorithm.
-    """
-    md5sum = hashlib.md5()
-
-    for line in lines:
-        if line.type != 'emptyline':
-            md5sum.update(line.to_string().encode('utf-8') + b'\n')
-        yield line
-
-    checksum = base64.b64encode(md5sum.digest()).rstrip(b'=')
-    yield Metadata('Checksum', checksum.decode('utf-8'))
 
 
 def _validate(lines):
     """Validate the final list."""
     first_line, rest = _first_and_rest(lines)
     if first_line.type != 'header':
         raise MissingHeader('No header found at the beginning of the input.')
     return itertools.chain([first_line], rest)
 
 
@@ skipping 22 matching lines @@
         When any of the fragments contain lines that can't be parsed.
     MissingHeader
         If the top level fragment doesn't start with a valid header. This would
         lead to rendering an invalid filter list, so we immediately abort.
 
     """
     _logger.info('Rendering: %s', name)
     lines, default_source = _get_and_parse_fragment(name, sources, top_source)
     lines = _process_includes(sources, default_source, [name], lines)
     for proc in [_process_timestamps, _insert_version, _remove_duplicates,
-                 _insert_checksum, _validate]:
+                 _validate]:
         lines = proc(lines)
     return lines
 
 
+def _split_list_for_diff(list_in):
+    """Split a filter list into metadata, keys, and rules."""

[Vasily Kuznetsov, 2018/08/31 12:11:02]

Nit: strictly speaking this function now returns metadata and rules (the keys
are just part of metadata). The docstring could be updated.

[rhowell, 2018/08/31 21:21:02]

Ah, good point! I'll update that.

+    metadata = {}
+    rules = set()
+    for line in parse_filterlist(list_in):
+        if line.type == 'metadata':
+            metadata[line.key.lower()] = line
+        elif line.type == 'filter':
+            rules.add(line.to_string())
+    return metadata, rules
+
+
 def render_diff(base, latest):

[Vasily Kuznetsov, 2018/08/17 10:30:54]

I think it makes more sense to make `base`, `latest` and the return value
iterables of strings. This is what parse_filterlist() expects and this is what
you get when you open a file. This is also the API that other functions dealing
with filterlists take and return. It would also reduce the amount of code here
eliminating the calls to splitlines() and some others.

It would also be good to document the API of this function in the same way as
the other functions are documented.

[rhowell, 2018/08/20 18:21:27]

Done.

-    """Return a diff between two filter lists."""
-    # Collect the special comments
-    diff = ['[Adblock Plus Diff]\n']
-    latest_fl, latest_md, latest_keys = (set() for i in range(3))
-    base_fl, base_md, base_keys = (set() for i in range(3))
-
-    for line in parse_filterlist(latest.splitlines()):
-        if line.type == 'metadata' and 'Checksum' not in line.to_string():

[Vasily Kuznetsov, 2018/08/17 10:30:53]

Note: If this lands after the checksum patch, the 'Checksum' exception should be
removed. If this lands first, it should be removed by that patch.

[rhowell, 2018/08/20 18:21:27]

Are we guaranteed that no filter lists will be encountered that have a checksum?
This line and line 220 make sure that, if we ever see a checksum in either
`base` or `latest`, it will not make it into the diff. But, if we will never see
a checksum, then this check is unnecessary.

[Vasily Kuznetsov, 2018/08/21 14:59:59]

Hm. No, for now we're not guaranteed that there's no Checksum, so you're right,
we should keep this.

[Sebastian Noack, 2018/08/21 19:42:45]

Isn't python-abp stripping checksums when generating the filter lists now, and
therefore isn't it in fact guaranteed that filter lists delivered by our servers
at least won't include any checksum? Even if not, any reason we'd have to strip
them here? Clients that support diffs, will ignore checksums anyway.

[Sebastian Noack, 2018/08/22 16:03:29]

Moving the discussion from IRC over here:

16:34:47 <•vasily> snoack: the second one I agree with you. For the first one,
at the moment, I think we have other code producing filter lists in production,
so they do have checksums. But we might convert all of this to python-abp
(perhaps together with deployment of the incremental updates) so you would also
be right then... however, we haven't yet done it.
16:36:03 <•vasily> snoack: in general seems like the checksums will be ignored
by diff-aware clients, so yeah, it can be removed.  
17:24:01 <snoack> vasily: How about ignoring checksum metadata in the parser
(rather than when rendering the full list and/or diff)? That way checksums would
be stripped no matter what, without any additional complexity.

-            latest_md.add(line.to_string())
-            latest_keys.add(line.key)
-        elif line.type == 'filter':
-            latest_fl.add(line.to_string())
-
-    # Get the diff between the rest of the lines
-    for line in parse_filterlist(base.splitlines()):

[Vasily Kuznetsov, 2018/08/17 10:30:53]

It would be good to move this repeated piece of code into a small internal
function. This will also make render_diff() more compact and easy to follow.
Maybe something like:

    base_fl, base_md, base_keys = _split_list_for_diff(base)

[rhowell, 2018/08/20 18:21:27]

Done.

-        if line.type == 'metadata' and 'Checksum' not in line.to_string():
-            base_md.add(line.to_string())
-            base_keys.add(line.key)
-        elif line.type == 'filter':
-            base_fl.add(line.to_string())
-    new_md = latest_md - base_md
-    removed_keys = base_keys - latest_keys
-    add_fl = latest_fl - base_fl
-    remove_fl = base_fl - latest_fl
-    for item in new_md:
-        diff.append('{}\n'.format(item))

[Vasily Kuznetsov, 2018/08/17 10:30:53]

If we return an iterable of strings from this function we can just yield in this
and the following loops.

[rhowell, 2018/08/20 18:21:27]

Done.

-    for key in removed_keys:
-        # If a special comment has been removed, enter it with a blank value
-        # so the client will set it back to the default value
-        diff.append('! {}:\n'.format(key))
-    for item in add_fl:
-        diff.append('+ {}\n'.format(item))
-    for item in remove_fl:
-        diff.append('- {}\n'.format(item))
-    return ''.join(diff)
+    """Return a diff between two filter lists.
+
+    Parameters
+    ----------
+    base : iterator of str
+        The base (old) list that we want to update to latest.
+    lastest : iterator  of str
+        The latest (most recent) list that we want to update to.
+
+    Returns
+    -------
+    iterable of str
+        A diff between two lists (https://issues.adblockplus.org/ticket/6685)
+
+    """
+    latest_metadata, latest_rules = _split_list_for_diff(latest)
+    base_metadata, base_rules = _split_list_for_diff(base)
+
+    yield '[Adblock Plus Diff]'
+    for key, latest in latest_metadata.items():
+        base = base_metadata.get(key)
+        if not base or base.value != latest.value:
+            yield latest.to_string()
+    for key in set(base_metadata) - set(latest_metadata):
+        yield '! {}:'.format(base_metadata[key].key)
+    for rule in base_rules - latest_rules:
+        yield '- {}'.format(rule)
+    for rule in latest_rules - base_rules:
+        yield '+ {}'.format(rule)