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 itertools
 import logging
 import time
 
 from .parser import parse_filterlist, Comment, Metadata
 from .sources import NotFound
 
-__all__ = ['IncludeError', 'MissingHeader', 'render_filterlist']
+__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 135 matching lines @@
         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,
                  _validate]:
         lines = proc(lines)
     return lines
+
+
+def _split_list_for_diff(list_in):
+    filterlist, metadata, keys = (set() for i in range(3))

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

I'm not sure if maybe a slightly more readable version of this line would be:

    filterlist, metadata, keys = set(), set(), set()

or even:

    filterlist = set()
    metadata = set()
    keys = set()

I don't feel too strongly about it so feel free to keep your original version or
choose one of the proposals above as you like.

[rhowell, 2018/08/27 22:06:27]

Done.

+    for line in parse_filterlist(list_in):

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

When parsing generated filter lists in order to generate diffs, we might want to
make the parser ignore includes/instructions.

[Vasily Kuznetsov, 2018/08/22 13:10:50]

Theoretically there should be no includes/instructions in the final lists (and
we're not planning to produce diffs of fragments of filter lists), so this is
not really necessary. And even if there were includes, the code below ignores
them, which achieves the same outcome as the parsing ignoring them, so it seems
that things are ok as is.

[Sebastian Noack, 2018/08/22 14:31:06]

Granted, this is quite an edge case. But in theory if we'll find  "%include" in
the input the diff is generated from, then it seems somewhat more accurate to
just treat it as a filter (like Adblock Plus would) rather than stripping this
line (or perhaps a warning would be in order). But I don't feel too strong.

[Vasily Kuznetsov, 2018/08/24 13:03:19]

To do this we would need to start parsing fragments of filter lists differently
from rendered filter lists. It does make sense but it also makes things more
complicated and the cases where it's relevant seem to be pretty unrealistic and
edge-casey.

I lean towards keeping the code unified and parsing "%include"s as instructions
everywhere until we have evidence that there are cases where it would be useful
to make the distinction.

[rhowell, 2018/08/27 22:06:27]

Yeah, I was working under the assumption that the full lists wouldn't have
%includes in them, and `%include` appears to be the only instruction the parser
knows. Are there any other instructions that might appear, that we might need to
handle? If not, I would agree with Vasily, that it's not necessary to handle
this case.

+        if line.type == 'metadata' and 'Checksum' not in line.to_string():
+            metadata.add(line.to_string())
+            keys.add(line.key)
+        elif line.type == 'filter':
+            filterlist.add(line.to_string())
+    return filterlist, metadata, keys
+
+
+def render_diff(base, latest):
+    """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_fl, latest_md, latest_keys = _split_list_for_diff(latest)
+    base_fl, base_md, base_keys = _split_list_for_diff(base)
+
+    new_md = latest_md - base_md
+    removed_keys = base_keys - latest_keys
+    add_fl = latest_fl - base_fl
+    remove_fl = base_fl - latest_fl
+
+    yield '[Adblock Plus Diff]'
+    for item in new_md:
+        yield item
+    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
+        yield '! {}:'.format(key)
+    for item in add_fl:
+        yield '+ {}'.format(item)
+    for item in remove_fl:
+        yield '- {}'.format(item)

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

In the specification, we demand the client to process removed filters first. But
given this implementation, it seems simpler if we'd rather make the diff list
the removed filters first, so that the client can process the diff in one pass.

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

After discussing this on IRC, Vasily agrees. I updated the spec accordingly.

[Vasily Kuznetsov, 2018/08/24 13:03:19]

👍

[rhowell, 2018/08/27 22:06:27]

Done.