checkbox-dev team mailing list archive

[Zygmunt Krynicki <zygmunt.krynicki@xxxxxxxxxxxxx>]

This function implements the so-called whitelist-ordering where
a sequence of jobs is selected from an available set of jobs according
to a sequence of qualifiers. Fine structure of those qualifiers is
interrogated to ensure that jobs being selected by earlier fragments
of those qualifiers appear early on the resulting list of selections.

Signed-off-by: Zygmunt Krynicki <zygmunt.krynicki@xxxxxxxxxxxxx>
---
 plainbox/plainbox/impl/secure/qualifiers.py      | 85 ++++++++++++++++++++++++
 plainbox/plainbox/impl/secure/test_qualifiers.py | 41 ++++++++++++
 2 files changed, 126 insertions(+)

diff --git a/plainbox/plainbox/impl/secure/qualifiers.py b/plainbox/plainbox/impl/secure/qualifiers.py
index 8f65ab2..1c2ade6 100644
--- a/plainbox/plainbox/impl/secure/qualifiers.py
+++ b/plainbox/plainbox/impl/secure/qualifiers.py
@@ -372,3 +372,88 @@ def get_flat_primitive_qualifier_list(qualifier_list):
     return list(itertools.chain(*[
         qual.get_primitive_qualifiers()
         for qual in qualifier_list]))
+
+
+def select_jobs(job_list, qualifier_list):
+    """
+    Select desired jobs.
+
+    :param job_list:
+        A list of JobDefinition objects
+    :param qualifier_list:
+        A list of IJobQualifier objects.
+    :returns:
+        A sub-list of JobDefinition objects, selected from job_list.
+    """
+    # Flatten the qualifier list, so that we can see the fine structure of
+    # composite objects, such as whitelists.
+    flat_qualifier_list = get_flat_primitive_qualifier_list(qualifier_list)
+    # Short-circuit if there are no jobs to select. Min is used later and this
+    # will allow us to assume that the matrix is not empty.
+    if not flat_qualifier_list:
+        return []
+    # Vote matrix, encodes the vote cast by a particular qualifier for a
+    # particular job. Visually it's a two-dimensional array like this:
+    #
+    #   ^
+    # q |
+    # u |   X
+    # a |
+    # l |  ........
+    # i |
+    # f |             .
+    # i | .
+    # e |          .
+    # r |
+    #    ------------------->
+    #                    job
+    #
+    # The vertical axis represents qualifiers from the flattened qualifier
+    # list.  The horizontal axis represents jobs from job list. Dots represent
+    # inclusion, X represents exclusion.
+    #
+    # The result of the select_job() function is a list of jobs that have at
+    # least one inclusion and no exclusions. The resulting list is ordered by
+    # increasing qualifier index.
+    #
+    # The algorithm implemented below is composed of two steps.
+    #
+    # The first step iterates over the vote matrix (row-major, meaning that we
+    # visit all columns for each visit of one row) and constructs two
+    # structures: a set of jobs that got VOTE_INCLUDE and a list of those jobs,
+    # in the order of discovery. All VOTE_EXCLUDE votes are collected in
+    # another set.
+    #
+    # The second step filters-out all items from the excluded job set from the
+    # selected job list. For extra efficiency the algorithm operates on
+    # integers representing the index of a particular job in job_list.
+    #
+    # The final complexity is O(N x M) + O(M), where N is the number of
+    # qualifiers (flattened) and M is the number of jobs. The algorithm assumes
+    # that set lookup is a O(1) operation which is true enough for python.
+    #
+    # A possible optimization would differentiate qualifiers that may select
+    # more than one job and fall-back to the current implementation while
+    # short-circuiting qualifiers that may select at most one job with a
+    # separate set lookup. That would make the algorithm "mostly" linear in the
+    # common case.
+    #
+    # As a separate feature, we might return a list of qualifiers that never
+    # matched anything. That may be helpful for debugging.
+    included_list = []
+    included_set = set()
+    excluded_set = set()
+    for qualifier in flat_qualifier_list:
+        for j_index, job in enumerate(job_list):
+            vote = qualifier.get_vote(job)
+            if vote == IJobQualifier.VOTE_INCLUDE:
+                if j_index in included_set:
+                    continue
+                included_set.add(j_index)
+                included_list.append(j_index)
+            elif vote == IJobQualifier.VOTE_EXCLUDE:
+                excluded_set.add(j_index)
+            elif vote == IJobQualifier.VOTE_IGNORE:
+                pass
+    return [job_list[index] for index in included_list
+            if index not in excluded_set]
diff --git a/plainbox/plainbox/impl/secure/test_qualifiers.py b/plainbox/plainbox/impl/secure/test_qualifiers.py
index bcc0a77..3a660e4 100644
--- a/plainbox/plainbox/impl/secure/test_qualifiers.py
+++ b/plainbox/plainbox/impl/secure/test_qualifiers.py
@@ -26,6 +26,7 @@ Test definitions for plainbox.impl.secure.qualifiers module
 
 from contextlib import contextmanager
 from io import TextIOWrapper
+from itertools import permutations
 from unittest import TestCase
 
 from plainbox.abc import IJobQualifier
@@ -35,6 +36,7 @@ from plainbox.impl.secure.qualifiers import NameJobQualifier
 from plainbox.impl.secure.qualifiers import RegExpJobQualifier
 from plainbox.impl.secure.qualifiers import SimpleQualifier
 from plainbox.impl.secure.qualifiers import WhiteList
+from plainbox.impl.secure.qualifiers import select_jobs
 from plainbox.impl.secure.rfc822 import FileTextSource
 from plainbox.impl.secure.rfc822 import Origin
 from plainbox.impl.secure.rfc822 import UnknownTextSource
@@ -516,3 +518,42 @@ class WhiteListTests(TestCase):
         self.assertEqual(WhiteList.name_from_filename("foo"), "foo")
         self.assertEqual(
             WhiteList.name_from_filename("foo.notawhitelist"), "foo")
+
+
+class FunctionTests(TestCase):
+
+    def test_select_jobs__inclusion(self):
+        """
+        verify that select_jobs() honors qualifier ordering
+        """
+        job_a = JobDefinition({'name': 'a'})
+        job_b = JobDefinition({'name': 'b'})
+        job_c = JobDefinition({'name': 'c'})
+        qual_a = NameJobQualifier("a")
+        qual_c = NameJobQualifier("c")
+        for job_list in permutations([job_a, job_b, job_c], 3):
+            # Regardless of how the list of job is ordered the result
+            # should be the same, depending on the qualifier list
+            self.assertEqual(
+                select_jobs(job_list, [qual_a, qual_c]),
+                [job_a, job_c])
+
+    def test_select_jobs__exclusion(self):
+        """
+        verify that select_jobs() honors qualifier ordering
+        """
+        job_a = JobDefinition({'name': 'a'})
+        job_b = JobDefinition({'name': 'b'})
+        job_c = JobDefinition({'name': 'c'})
+        qual_all = CompositeQualifier([
+            NameJobQualifier("a"),
+            NameJobQualifier("b"),
+            NameJobQualifier("c"),
+        ])
+        qual_not_c = NameJobQualifier("c", inclusive=False)
+        for job_list in permutations([job_a, job_b, job_c], 3):
+            # Regardless of how the list of job is ordered the result
+            # should be the same, depending on the qualifier list
+            self.assertEqual(
+                select_jobs(job_list, [qual_all, qual_not_c]),
+                [job_a, job_b])
-- 
1.8.5.3