← Back to branch summary

~jocave/checkbox/hybrid-amd-gpu-mods

« back to all changes in this revision

Viewing changes to plainbox/plainbox/impl/secure/qualifiers.py

  • Committer: Zygmunt Krynicki
  • Date: 2013-05-29 07:50:30 UTC
  • mto: This revision was merged to the branch mainline in revision 2153.
  • Revision ID: zygmunt.krynicki@canonical.com-20130529075030-ngwz245hs2u3y6us
checkbox: move current checkbox code into checkbox-old

This patch cleans up the top-level directory of the project into dedicated
sub-project directories. One for checkbox-old (the current checkbox and all the
associated stuff), one for plainbox and another for checkbox-ng.

There are some associated changes, such as updating the 'source' mode of
checkbox provider in plainbox, and fixing paths in various test scripts that we
have.

Signed-off-by: Zygmunt Krynicki <zygmunt.krynicki@canonical.com>

Show diffs side-by-side

added added

removed removed

Lines of Context:
plainbox/plainbox/impl/secure/qualifiers.py
1
 
# This file is part of Checkbox.
2
 
#
3
 
# Copyright 2013, 2014 Canonical Ltd.
4
 
# Written by:
5
 
#   Zygmunt Krynicki <zygmunt.krynicki@canonical.com>
6
 
#
7
 
# Checkbox is free software: you can redistribute it and/or modify
8
 
# it under the terms of the GNU General Public License version 3,
9
 
# as published by the Free Software Foundation.
10
 
 
11
 
#
12
 
# Checkbox is distributed in the hope that it will be useful,
13
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
 
# GNU General Public License for more details.
16
 
#
17
 
# You should have received a copy of the GNU General Public License
18
 
# along with Checkbox.  If not, see <http://www.gnu.org/licenses/>.
19
 
 
20
 
"""
21
 
:mod:`plainbox.impl.secure.qualifiers` -- Job Qualifiers
22
 
========================================================
23
 
 
24
 
Qualifiers are callable objects that can be used to 'match' a job definition to
25
 
some set of rules.
26
 
"""
27
 
 
28
 
import abc
29
 
import functools
30
 
import itertools
31
 
import logging
32
 
import operator
33
 
import os
34
 
import re
35
 
import sre_constants
36
 
 
37
 
from plainbox.abc import IJobQualifier
38
 
from plainbox.i18n import gettext as _
39
 
from plainbox.impl import pod
40
 
from plainbox.impl.secure.origin import FileTextSource
41
 
from plainbox.impl.secure.origin import Origin
42
 
from plainbox.impl.secure.origin import UnknownTextSource
43
 
 
44
 
 
45
 
_logger = logging.getLogger("plainbox.secure.qualifiers")
46
 
 
47
 
 
48
 
class SimpleQualifier(IJobQualifier):
49
 
    """
50
 
    Abstract base class that implements common features of simple (non
51
 
    composite) qualifiers. This allows two concrete subclasses below to
52
 
    have share some code.
53
 
    """
54
 
 
55
 
    def __init__(self,  origin, inclusive=True):
56
 
        if origin is not None and not isinstance(origin, Origin):
57
 
            raise TypeError(_('argument {!a}, expected {}, got {}').format(
58
 
                'origin', Origin, type(origin)))
59
 
        if not isinstance(inclusive, bool):
60
 
            raise TypeError(_('argument {!a}, expected {}, got {}').format(
61
 
                'inclusive', bool, type(inclusive)))
62
 
        self._inclusive = inclusive
63
 
        self._origin = origin
64
 
 
65
 
    @property
66
 
    def inclusive(self):
67
 
        return self._inclusive
68
 
 
69
 
    @property
70
 
    def is_primitive(self):
71
 
        return True
72
 
 
73
 
    def designates(self, job):
74
 
        return self.get_vote(job) == self.VOTE_INCLUDE
75
 
 
76
 
    @abc.abstractmethod
77
 
    def get_simple_match(self, job):
78
 
        """
79
 
        Get a simple yes-or-no boolean answer if the given job matches the
80
 
        simple aspect of this qualifier. This method should be overridden by
81
 
        concrete subclasses.
82
 
        """
83
 
 
84
 
    def get_vote(self, job):
85
 
        """
86
 
        Get one of the ``VOTE_IGNORE``, ``VOTE_INCLUDE``, ``VOTE_EXCLUDE``
87
 
        votes that this qualifier associated with the specified job.
88
 
 
89
 
        :param job:
90
 
            A IJobDefinition instance that is to be visited
91
 
        :returns:
92
 
            * ``VOTE_INCLUDE`` if the job matches the simple qualifier concept
93
 
              embedded into this qualifier and this qualifier is **inclusive**.
94
 
            * ``VOTE_EXCLUDE`` if the job matches the simple qualifier concept
95
 
              embedded into this qualifier and this qualifier is **not
96
 
              inclusive**.
97
 
            * ``VOTE_IGNORE`` otherwise.
98
 
 
99
 
        .. versionadded: 0.5
100
 
        """
101
 
        if self.get_simple_match(job):
102
 
            if self.inclusive:
103
 
                return self.VOTE_INCLUDE
104
 
            else:
105
 
                return self.VOTE_EXCLUDE
106
 
        else:
107
 
            return self.VOTE_IGNORE
108
 
 
109
 
    def get_primitive_qualifiers(self):
110
 
        """
111
 
        Return a list of primitives that constitute this qualifier.
112
 
 
113
 
        :returns:
114
 
            A list of IJobQualifier objects that each is the smallest,
115
 
            indivisible entity. Here it just returns a list of one element,
116
 
            itself.
117
 
 
118
 
        .. versionadded: 0.5
119
 
        """
120
 
        return [self]
121
 
 
122
 
    @property
123
 
    def origin(self):
124
 
        """
125
 
        Origin of this qualifier
126
 
 
127
 
        This property can be used to trace the origin of a qualifier back to
128
 
        its definition point.
129
 
        """
130
 
        return self._origin
131
 
 
132
 
 
133
 
class RegExpJobQualifier(SimpleQualifier):
134
 
    """
135
 
    A JobQualifier that designates jobs by matching their id to a regular
136
 
    expression
137
 
    """
138
 
 
139
 
    def __init__(self, pattern, origin, inclusive=True):
140
 
        """
141
 
        Initialize a new RegExpJobQualifier with the specified pattern.
142
 
        """
143
 
        super().__init__(origin, inclusive)
144
 
        try:
145
 
            self._pattern = re.compile(pattern)
146
 
        except sre_constants.error as exc:
147
 
            assert len(exc.args) == 1
148
 
            # XXX: This is a bit crazy but this lets us have identical error
149
 
            # messages across python3.2 all the way to 3.5. I really really
150
 
            # wish there was a better way at fixing this.
151
 
            exc.args = (re.sub(" at position \d+", "", exc.args[0]), )
152
 
            raise exc
153
 
        self._pattern_text = pattern
154
 
 
155
 
    def get_simple_match(self, job):
156
 
        """
157
 
        Check if the given job matches this qualifier.
158
 
 
159
 
        This method should not be called directly, it is an implementation
160
 
        detail of SimpleQualifier class.
161
 
        """
162
 
        return self._pattern.match(job.id) is not None
163
 
 
164
 
    @property
165
 
    def pattern_text(self):
166
 
        """
167
 
        text of the regular expression embedded in this qualifier
168
 
        """
169
 
        return self._pattern_text
170
 
 
171
 
    def __repr__(self):
172
 
        return "{0}({1!r}, inclusive={2})".format(
173
 
            self.__class__.__name__, self._pattern_text, self._inclusive)
174
 
 
175
 
 
176
 
class JobIdQualifier(SimpleQualifier):
177
 
    """
178
 
    A JobQualifier that designates a single job with a particular id
179
 
    """
180
 
 
181
 
    def __init__(self, id, origin, inclusive=True):
182
 
        super().__init__(origin, inclusive)
183
 
        self._id = id
184
 
 
185
 
    @property
186
 
    def id(self):
187
 
        """
188
 
        identifier to match
189
 
        """
190
 
        return self._id
191
 
 
192
 
    def get_simple_match(self, job):
193
 
        """
194
 
        Check if the given job matches this qualifier.
195
 
 
196
 
        This method should not be called directly, it is an implementation
197
 
        detail of SimpleQualifier class.
198
 
        """
199
 
        return self._id == job.id
200
 
 
201
 
    def __repr__(self):
202
 
        return "{0}({1!r}, inclusive={2})".format(
203
 
            self.__class__.__name__, self._id, self._inclusive)
204
 
 
205
 
 
206
 
class NonLocalJobQualifier(SimpleQualifier):
207
 
    """
208
 
    A JobQualifier that designates only non local jobs
209
 
    """
210
 
 
211
 
    def __init__(self, origin, inclusive=True):
212
 
        super().__init__(origin, inclusive)
213
 
 
214
 
    def get_simple_match(self, job):
215
 
        """
216
 
        Check if the given job matches this qualifier.
217
 
 
218
 
        This method should not be called directly, it is an implementation
219
 
        detail of SimpleQualifier class.
220
 
        """
221
 
        return job.plugin != 'local'
222
 
 
223
 
    def __repr__(self):
224
 
        return "{0}(inclusive={1})".format(
225
 
            self.__class__.__name__, self._inclusive)
226
 
 
227
 
 
228
 
class IMatcher(metaclass=abc.ABCMeta):
229
 
    """
230
 
    Interface for objects that perform some kind of comparison on a value
231
 
    """
232
 
 
233
 
    @abc.abstractmethod
234
 
    def match(self, value):
235
 
        """
236
 
        Match (or not) specified value
237
 
 
238
 
        :param value:
239
 
            value to match
240
 
        :returns:
241
 
            True if it matched, False otherwise
242
 
        """
243
 
 
244
 
 
245
 
@functools.total_ordering
246
 
class OperatorMatcher(IMatcher):
247
 
    """
248
 
    A matcher that applies a binary operator to the value
249
 
    """
250
 
 
251
 
    def __init__(self, op, value):
252
 
        self._op = op
253
 
        self._value = value
254
 
 
255
 
    @property
256
 
    def op(self):
257
 
        """
258
 
        the operator to use
259
 
 
260
 
        The operator is typically one of the functions from the ``operator``
261
 
        module. For example. operator.eq corresponds to the == python operator.
262
 
        """
263
 
        return self._op
264
 
 
265
 
    @property
266
 
    def value(self):
267
 
        """
268
 
        The right-hand-side value to apply to the operator
269
 
 
270
 
        The left-hand-side is the value that is passed to :meth:`match()`
271
 
        """
272
 
        return self._value
273
 
 
274
 
    def match(self, value):
275
 
        return self._op(self._value, value)
276
 
 
277
 
    def __repr__(self):
278
 
        return "{0}({1!r}, {2!r})".format(
279
 
            self.__class__.__name__, self._op, self._value)
280
 
 
281
 
    def __eq__(self, other):
282
 
        if isinstance(other, OperatorMatcher):
283
 
            return self.op == other.op and self.value == other.value
284
 
        else:
285
 
            return NotImplemented
286
 
 
287
 
    def __lt__(self, other):
288
 
        if isinstance(other, OperatorMatcher):
289
 
            if self.op < other.op:
290
 
                return True
291
 
            if self.value < other.value:
292
 
                return True
293
 
            return False
294
 
        else:
295
 
            return NotImplemented
296
 
 
297
 
 
298
 
class PatternMatcher(IMatcher):
299
 
    """
300
 
    A matcher that compares values by regular expression pattern
301
 
    """
302
 
 
303
 
    def __init__(self, pattern):
304
 
        self._pattern_text = pattern
305
 
        self._pattern = re.compile(pattern)
306
 
 
307
 
    @property
308
 
    def pattern_text(self):
309
 
        return self._pattern_text
310
 
 
311
 
    def match(self, value):
312
 
        return self._pattern.match(value) is not None
313
 
 
314
 
    def __repr__(self):
315
 
        return "{0}({1!r})".format(
316
 
            self.__class__.__name__, self._pattern_text)
317
 
 
318
 
    def __eq__(self, other):
319
 
        if isinstance(other, PatternMatcher):
320
 
            return self.pattern_text == other.pattern_text
321
 
        else:
322
 
            return NotImplemented
323
 
 
324
 
    def __lt__(self, other):
325
 
        if isinstance(other, PatternMatcher):
326
 
            return self.pattern_text < other.pattern_text
327
 
        else:
328
 
            return NotImplemented
329
 
 
330
 
 
331
 
class FieldQualifier(SimpleQualifier):
332
 
    """
333
 
    A SimpleQualifer that uses matchers to compare particular fields
334
 
    """
335
 
 
336
 
    def __init__(self, field, matcher, origin, inclusive=True):
337
 
        """
338
 
        Initialize a new FieldQualifier with the specified field, matcher and
339
 
        inclusive flag
340
 
 
341
 
        :param field:
342
 
            Name of the JobDefinition field to use
343
 
        :param matcher:
344
 
            A IMatcher object
345
 
        :param inclusive:
346
 
            Inclusive selection flag (default: True)
347
 
        """
348
 
        super().__init__(origin, inclusive)
349
 
        self._field = field
350
 
        self._matcher = matcher
351
 
 
352
 
    @property
353
 
    def field(self):
354
 
        """
355
 
        Name of the field to match
356
 
        """
357
 
        return self._field
358
 
 
359
 
    @property
360
 
    def matcher(self):
361
 
        """
362
 
        The IMatcher-implementing object to use to check for the match
363
 
        """
364
 
        return self._matcher
365
 
 
366
 
    def get_simple_match(self, job):
367
 
        """
368
 
        Check if the given job matches this qualifier.
369
 
 
370
 
        This method should not be called directly, it is an implementation
371
 
        detail of SimpleQualifier class.
372
 
        """
373
 
        field_value = getattr(job, str(self._field))
374
 
        return self._matcher.match(field_value)
375
 
 
376
 
    def __repr__(self):
377
 
        return "{0}({1!r}, {2!r}, inclusive={3})".format(
378
 
            self.__class__.__name__, self._field, self._matcher,
379
 
            self._inclusive)
380
 
 
381
 
 
382
 
class CompositeQualifier(pod.POD):
383
 
    """
384
 
    A JobQualifier that has qualifies jobs matching any inclusive qualifiers
385
 
    while not matching all of the exclusive qualifiers
386
 
    """
387
 
 
388
 
    qualifier_list = pod.Field("qualifier_list", list, pod.MANDATORY)
389
 
 
390
 
    @property
391
 
    def is_primitive(self):
392
 
        return False
393
 
 
394
 
    def designates(self, job):
395
 
        return self.get_vote(job) == IJobQualifier.VOTE_INCLUDE
396
 
 
397
 
    def get_vote(self, job):
398
 
        """
399
 
        Get one of the ``VOTE_IGNORE``, ``VOTE_INCLUDE``, ``VOTE_EXCLUDE``
400
 
        votes that this qualifier associated with the specified job.
401
 
 
402
 
        :param job:
403
 
            A IJobDefinition instance that is to be visited
404
 
        :returns:
405
 
            * ``VOTE_INCLUDE`` if the job matches at least one qualifier voted
406
 
              to select it and no qualifiers voted to deselect it.
407
 
            * ``VOTE_EXCLUDE`` if at least one qualifier voted to deselect it
408
 
            * ``VOTE_IGNORE`` otherwise or if the list of qualifiers is empty.
409
 
 
410
 
        .. versionadded: 0.5
411
 
        """
412
 
        if self.qualifier_list:
413
 
            return min([
414
 
                qualifier.get_vote(job)
415
 
                for qualifier in self.qualifier_list])
416
 
        else:
417
 
            return IJobQualifier.VOTE_IGNORE
418
 
 
419
 
    def get_primitive_qualifiers(self):
420
 
        return get_flat_primitive_qualifier_list(self.qualifier_list)
421
 
 
422
 
    @property
423
 
    def origin(self):
424
 
        raise NonPrimitiveQualifierOrigin
425
 
 
426
 
 
427
 
IJobQualifier.register(CompositeQualifier)
428
 
 
429
 
 
430
 
class NonPrimitiveQualifierOrigin(Exception):
431
 
    """
432
 
    Exception raised when IJobQualifier.origin is meaningless as it is being
433
 
    requested on a non-primitive qualifier such as the CompositeQualifier
434
 
    """
435
 
 
436
 
 
437
 
# NOTE: using CompositeQualifier seems strange but it's a tested proven
438
 
# component so all we have to ensure is that we read the whitelist files
439
 
# correctly.
440
 
class WhiteList(CompositeQualifier):
441
 
    """
442
 
    A qualifier that understands checkbox whitelist files.
443
 
 
444
 
    A whitelist file is a plain text, line oriented file. Each line represents
445
 
    a regular expression pattern that can be matched against the id of a job.
446
 
 
447
 
    The file can contain simple shell-style comments that begin with the pound
448
 
    or hash key (#). Those are ignored. Comments can span both a fraction of a
449
 
    line as well as the whole line.
450
 
 
451
 
    For historical reasons each pattern has an implicit '^' and '$' prepended
452
 
    and appended (respectively) to the actual pattern specified in the file.
453
 
    """
454
 
 
455
 
    def __init__(self, pattern_list, name=None, origin=None,
456
 
                 implicit_namespace=None):
457
 
        """
458
 
        Initialize a WhiteList object with the specified list of patterns.
459
 
 
460
 
        The patterns must be already mangled with '^' and '$'.
461
 
        """
462
 
        self._name = name
463
 
        self._origin = origin
464
 
        self._implicit_namespace = implicit_namespace
465
 
        if implicit_namespace is not None:
466
 
            # If we have an implicit namespace then transform all the patterns
467
 
            # without the namespace operator ('::')
468
 
            namespace_pattern = implicit_namespace.replace('.', '\\.')
469
 
 
470
 
            def transform_pattern(maybe_partial_id_pattern):
471
 
                if "::" not in maybe_partial_id_pattern:
472
 
                    return "^{}::{}$".format(
473
 
                        namespace_pattern, maybe_partial_id_pattern[1:-1])
474
 
                else:
475
 
                    return maybe_partial_id_pattern
476
 
            qualifier_list = [
477
 
                RegExpJobQualifier(
478
 
                    transform_pattern(pattern), origin, inclusive=True)
479
 
                for pattern in pattern_list]
480
 
        else:
481
 
            # Otherwise just use the patterns directly
482
 
            qualifier_list = [
483
 
                RegExpJobQualifier(pattern, origin, inclusive=True)
484
 
                for pattern in pattern_list]
485
 
        super().__init__(qualifier_list)
486
 
 
487
 
    def __repr__(self):
488
 
        return "<{} name:{!r}>".format(self.__class__.__name__, self.name)
489
 
 
490
 
    @property
491
 
    def name(self):
492
 
        """
493
 
        name of this WhiteList (might be None)
494
 
        """
495
 
        return self._name
496
 
 
497
 
    @name.setter
498
 
    def name(self, value):
499
 
        """
500
 
        set a new name for a WhiteList
501
 
        """
502
 
        self._name = value
503
 
 
504
 
    @property
505
 
    def origin(self):
506
 
        """
507
 
        origin object associated with this WhiteList (might be None)
508
 
        """
509
 
        return self._origin
510
 
 
511
 
    @property
512
 
    def implicit_namespace(self):
513
 
        """
514
 
        namespace used to qualify patterns without explicit namespace
515
 
        """
516
 
        return self._implicit_namespace
517
 
 
518
 
    @classmethod
519
 
    def from_file(cls, pathname, implicit_namespace=None):
520
 
        """
521
 
        Load and initialize the WhiteList object from the specified file.
522
 
 
523
 
        :param pathname:
524
 
            file to load
525
 
        :param implicit_namespace:
526
 
            (optional) implicit namespace for jobs that are using partial
527
 
            identifiers (all jobs)
528
 
        :returns:
529
 
            a fresh WhiteList object
530
 
        """
531
 
        pattern_list, max_lineno = cls._load_patterns(pathname)
532
 
        name = os.path.splitext(os.path.basename(pathname))[0]
533
 
        origin = Origin(FileTextSource(pathname), 1, max_lineno)
534
 
        return cls(pattern_list, name, origin, implicit_namespace)
535
 
 
536
 
    @classmethod
537
 
    def from_string(cls, text, *, filename=None, name=None, origin=None,
538
 
                    implicit_namespace=None):
539
 
        """
540
 
        Load and initialize the WhiteList object from the specified string.
541
 
 
542
 
        :param text:
543
 
            full text of the whitelist
544
 
        :param filename:
545
 
            (optional, keyword-only) filename from which text was read from.
546
 
            This simulates a call to :meth:`from_file()` which properly
547
 
            computes the name and origin of the whitelist.
548
 
        :param name:
549
 
            (optional) name of the whitelist, only used if filename is not
550
 
            specified.
551
 
        :param origin:
552
 
            (optional) origin of the whitelist, only used if a filename is not
553
 
            specified.  If omitted a default origin value will be constructed
554
 
            out of UnknownTextSource instance
555
 
        :param implicit_namespace:
556
 
            (optional) implicit namespace for jobs that are using partial
557
 
            identifiers (all jobs)
558
 
        :returns:
559
 
            a fresh WhiteList object
560
 
 
561
 
        The optional filename or a pair of name and origin arguments may be
562
 
        provided in order to have additional meta-data. This is typically
563
 
        needed when the :meth:`from_file()` method cannot be used as the caller
564
 
        already has the full text of the intended file available.
565
 
        """
566
 
        _logger.debug("Loaded whitelist from %r", filename)
567
 
        pattern_list, max_lineno = cls._parse_patterns(text)
568
 
        # generate name and origin if filename is provided
569
 
        if filename is not None:
570
 
            name = WhiteList.name_from_filename(filename)
571
 
            origin = Origin(FileTextSource(filename), 1, max_lineno)
572
 
        else:
573
 
            # otherwise generate origin if it's not specified
574
 
            if origin is None:
575
 
                origin = Origin(UnknownTextSource(), 1, max_lineno)
576
 
        return cls(pattern_list, name, origin, implicit_namespace)
577
 
 
578
 
    @classmethod
579
 
    def name_from_filename(cls, filename):
580
 
        """
581
 
        Compute the name of a whitelist based on the name
582
 
        of the file it is stored in.
583
 
        """
584
 
        return os.path.splitext(os.path.basename(filename))[0]
585
 
 
586
 
    @classmethod
587
 
    def _parse_patterns(cls, text):
588
 
        """
589
 
        Load whitelist patterns from the specified text
590
 
 
591
 
        :param text:
592
 
            string of text, including newlines, to parse
593
 
        :returns:
594
 
            (pattern_list, lineno) where lineno is the final line number
595
 
            (1-based) and pattern_list is a list of regular expression strings
596
 
            parsed from the whitelist.
597
 
        """
598
 
        from plainbox.impl.xparsers import Re
599
 
        from plainbox.impl.xparsers import Visitor
600
 
        from plainbox.impl.xparsers import WhiteList
601
 
 
602
 
        class WhiteListVisitor(Visitor):
603
 
 
604
 
            def __init__(self):
605
 
                self.pattern_list = []
606
 
                self.lineno = 0
607
 
 
608
 
            def visit_Re_node(self, node: Re):
609
 
                self.pattern_list.append(r"^{}$".format(node.text.strip()))
610
 
                self.lineno = max(node.lineno, self.lineno)
611
 
                return super().generic_visit(node)
612
 
 
613
 
            visit_ReFixed_node = visit_Re_node
614
 
            visit_RePattern_node = visit_Re_node
615
 
            visit_ReErr_node = visit_Re_node
616
 
 
617
 
        visitor = WhiteListVisitor()
618
 
        visitor.visit(WhiteList.parse(text))
619
 
        return visitor.pattern_list, visitor.lineno
620
 
 
621
 
    @classmethod
622
 
    def _load_patterns(cls, pathname):
623
 
        """
624
 
        Load whitelist patterns from the specified file
625
 
 
626
 
        :param pathname:
627
 
            pathname of the file to load and parse
628
 
        :returns:
629
 
            (pattern_list, lineno) where lineno is the final line number
630
 
            (1-based) and pattern_list is a list of regular expression strings
631
 
            parsed from the whitelist.
632
 
        """
633
 
        with open(pathname, "rt", encoding="UTF-8") as stream:
634
 
            return cls._parse_patterns(stream.read())
635
 
 
636
 
 
637
 
def get_flat_primitive_qualifier_list(qualifier_list):
638
 
    return list(itertools.chain(*[
639
 
        qual.get_primitive_qualifiers()
640
 
        for qual in qualifier_list]))
641
 
 
642
 
 
643
 
def select_jobs(job_list, qualifier_list):
644
 
    """
645
 
    Select desired jobs.
646
 
 
647
 
    :param job_list:
648
 
        A list of JobDefinition objects
649
 
    :param qualifier_list:
650
 
        A list of IJobQualifier objects.
651
 
    :returns:
652
 
        A sub-list of JobDefinition objects, selected from job_list.
653
 
    """
654
 
    # Flatten the qualifier list, so that we can see the fine structure of
655
 
    # composite objects, such as whitelists.
656
 
    flat_qualifier_list = get_flat_primitive_qualifier_list(qualifier_list)
657
 
    # Short-circuit if there are no jobs to select. Min is used later and this
658
 
    # will allow us to assume that the matrix is not empty.
659
 
    if not flat_qualifier_list:
660
 
        return []
661
 
    # Vote matrix, encodes the vote cast by a particular qualifier for a
662
 
    # particular job. Visually it's a two-dimensional array like this:
663
 
    #
664
 
    #   ^
665
 
    # q |
666
 
    # u |   X
667
 
    # a |
668
 
    # l |  ........
669
 
    # i |
670
 
    # f |             .
671
 
    # i | .
672
 
    # e |          .
673
 
    # r |
674
 
    #    ------------------->
675
 
    #                    job
676
 
    #
677
 
    # The vertical axis represents qualifiers from the flattened qualifier
678
 
    # list.  The horizontal axis represents jobs from job list. Dots represent
679
 
    # inclusion, X represents exclusion.
680
 
    #
681
 
    # The result of the select_job() function is a list of jobs that have at
682
 
    # least one inclusion and no exclusions. The resulting list is ordered by
683
 
    # increasing qualifier index.
684
 
    #
685
 
    # The algorithm implemented below is composed of two steps.
686
 
    #
687
 
    # The first step iterates over the vote matrix (row-major, meaning that we
688
 
    # visit all columns for each visit of one row) and constructs two
689
 
    # structures: a set of jobs that got VOTE_INCLUDE and a list of those jobs,
690
 
    # in the order of discovery. All VOTE_EXCLUDE votes are collected in
691
 
    # another set.
692
 
    #
693
 
    # The second step filters-out all items from the excluded job set from the
694
 
    # selected job list. For extra efficiency the algorithm operates on
695
 
    # integers representing the index of a particular job in job_list.
696
 
    #
697
 
    # The final complexity is O(N x M) + O(M), where N is the number of
698
 
    # qualifiers (flattened) and M is the number of jobs. The algorithm assumes
699
 
    # that set lookup is a O(1) operation which is true enough for python.
700
 
    #
701
 
    # A possible optimization would differentiate qualifiers that may select
702
 
    # more than one job and fall-back to the current implementation while
703
 
    # short-circuiting qualifiers that may select at most one job with a
704
 
    # separate set lookup. That would make the algorithm "mostly" linear in the
705
 
    # common case.
706
 
    #
707
 
    # As a separate feature, we might return a list of qualifiers that never
708
 
    # matched anything. That may be helpful for debugging.
709
 
    included_list = []
710
 
    id_to_index_map = {job.id: index for index, job in enumerate(job_list)}
711
 
    included_set = set()
712
 
    excluded_set = set()
713
 
    for qualifier in flat_qualifier_list:
714
 
        if (isinstance(qualifier, FieldQualifier)
715
 
                and qualifier.field == 'id'
716
 
                and isinstance(qualifier.matcher, OperatorMatcher)
717
 
                and qualifier.matcher.op == operator.eq):
718
 
            # optimize the super-common case where a qualifier refers to
719
 
            # a specific job by using the id_to_index_map to instantly
720
 
            # perform the requested operation on a single job
721
 
            try:
722
 
                j_index = id_to_index_map[qualifier.matcher.value]
723
 
            except KeyError:
724
 
                # The lookup can fail if the pattern is a constant reference to
725
 
                # a generated job that doens't exist yet. To maintain correctness
726
 
                # we should just ignore it, as it would not match anything yet.
727
 
                continue
728
 
            job = job_list[j_index]
729
 
            vote = qualifier.get_vote(job)
730
 
            if vote == IJobQualifier.VOTE_INCLUDE:
731
 
                if j_index in included_set:
732
 
                    continue
733
 
                included_set.add(j_index)
734
 
                included_list.append(j_index)
735
 
            elif vote == IJobQualifier.VOTE_EXCLUDE:
736
 
                excluded_set.add(j_index)
737
 
            elif vote == IJobQualifier.VOTE_IGNORE:
738
 
                pass
739
 
        else:
740
 
            for j_index, job in enumerate(job_list):
741
 
                vote = qualifier.get_vote(job)
742
 
                if vote == IJobQualifier.VOTE_INCLUDE:
743
 
                    if j_index in included_set:
744
 
                        continue
745
 
                    included_set.add(j_index)
746
 
                    included_list.append(j_index)
747
 
                elif vote == IJobQualifier.VOTE_EXCLUDE:
748
 
                    excluded_set.add(j_index)
749
 
                elif vote == IJobQualifier.VOTE_IGNORE:
750
 
                    pass
751
 
    return [job_list[index] for index in included_list
752
 
            if index not in excluded_set]