1# -*- coding: utf-8 -*-
2#
3# Copyright (c) 2015 OpenStack Foundation.
4# All Rights Reserved.
5#
6#    Licensed under the Apache License, Version 2.0 (the "License"); you may
7#    not use this file except in compliance with the License. You may obtain
8#    a copy of the License at
9#
10#         http://www.apache.org/licenses/LICENSE-2.0
11#
12#    Unless required by applicable law or agreed to in writing, software
13#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
14#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
15#    License for the specific language governing permissions and limitations
16#    under the License.
17
18import logging
19import re
20
21from oslo_policy import _checks
22
23
24LOG = logging.getLogger(__name__)
25
26
27def reducer(*tokens):
28    """Decorator for reduction methods.
29
30    Arguments are a sequence of tokens, in order, which should trigger running
31    this reduction method.
32    """
33
34    def decorator(func):
35        # Make sure we have a list of reducer sequences
36        if not hasattr(func, 'reducers'):
37            func.reducers = []
38
39        # Add the tokens to the list of reducer sequences
40        func.reducers.append(list(tokens))
41
42        return func
43
44    return decorator
45
46
47class ParseStateMeta(type):
48    """Metaclass for the :class:`.ParseState` class.
49
50    Facilitates identifying reduction methods.
51    """
52
53    def __new__(mcs, name, bases, cls_dict):
54        """Create the class.
55
56        Injects the 'reducers' list, a list of tuples matching token sequences
57        to the names of the corresponding reduction methods.
58        """
59
60        reducers = []
61
62        for key, value in cls_dict.items():
63            if not hasattr(value, 'reducers'):
64                continue
65            for reduction in value.reducers:
66                reducers.append((reduction, key))
67
68        cls_dict['reducers'] = reducers
69
70        return super(ParseStateMeta, mcs).__new__(mcs, name, bases, cls_dict)
71
72
73class ParseState(metaclass=ParseStateMeta):
74    """Implement the core of parsing the policy language.
75
76    Uses a greedy reduction algorithm to reduce a sequence of tokens into
77    a single terminal, the value of which will be the root of the
78    :class:`Check` tree.
79
80    .. note::
81
82        Error reporting is rather lacking.  The best we can get with this
83        parser formulation is an overall "parse failed" error. Fortunately, the
84        policy language is simple enough that this shouldn't be that big a
85        problem.
86    """
87
88    def __init__(self):
89        """Initialize the ParseState."""
90
91        self.tokens = []
92        self.values = []
93
94    def reduce(self):
95        """Perform a greedy reduction of the token stream.
96
97        If a reducer method matches, it will be executed, then the
98        :meth:`reduce` method will be called recursively to search for any more
99        possible reductions.
100        """
101
102        for reduction, methname in self.reducers:
103            if (len(self.tokens) >= len(reduction) and
104                    self.tokens[-len(reduction):] == reduction):
105                # Get the reduction method
106                meth = getattr(self, methname)
107
108                # Reduce the token stream
109                results = meth(*self.values[-len(reduction):])
110
111                # Update the tokens and values
112                self.tokens[-len(reduction):] = [r[0] for r in results]
113                self.values[-len(reduction):] = [r[1] for r in results]
114
115                # Check for any more reductions
116                return self.reduce()
117
118    def shift(self, tok, value):
119        """Adds one more token to the state.
120
121        Calls :meth:`reduce`.
122        """
123
124        self.tokens.append(tok)
125        self.values.append(value)
126
127        # Do a greedy reduce...
128        self.reduce()
129
130    @property
131    def result(self):
132        """Obtain the final result of the parse.
133
134        :raises ValueError: If the parse failed to reduce to a single result.
135        """
136
137        if len(self.values) != 1:
138            raise ValueError('Could not parse rule')
139        return self.values[0]
140
141    @reducer('(', 'check', ')')
142    @reducer('(', 'and_expr', ')')
143    @reducer('(', 'or_expr', ')')
144    def _wrap_check(self, _p1, check, _p2):
145        """Turn parenthesized expressions into a 'check' token."""
146
147        return [('check', check)]
148
149    @reducer('check', 'and', 'check')
150    def _make_and_expr(self, check1, _and, check2):
151        """Create an 'and_expr'.
152
153        Join two checks by the 'and' operator.
154        """
155
156        return [('and_expr', _checks.AndCheck([check1, check2]))]
157
158    @reducer('or_expr', 'and', 'check')
159    def _mix_or_and_expr(self, or_expr, _and, check):
160        """Modify the case 'A or B and C'"""
161
162        or_expr, check1 = or_expr.pop_check()
163        if isinstance(check1, _checks.AndCheck):
164            and_expr = check1
165            and_expr.add_check(check)
166        else:
167            and_expr = _checks.AndCheck([check1, check])
168        return [('or_expr', or_expr.add_check(and_expr))]
169
170    @reducer('and_expr', 'and', 'check')
171    def _extend_and_expr(self, and_expr, _and, check):
172        """Extend an 'and_expr' by adding one more check."""
173
174        return [('and_expr', and_expr.add_check(check))]
175
176    @reducer('check', 'or', 'check')
177    @reducer('and_expr', 'or', 'check')
178    def _make_or_expr(self, check1, _or, check2):
179        """Create an 'or_expr'.
180
181        Join two checks by the 'or' operator.
182        """
183
184        return [('or_expr', _checks.OrCheck([check1, check2]))]
185
186    @reducer('or_expr', 'or', 'check')
187    def _extend_or_expr(self, or_expr, _or, check):
188        """Extend an 'or_expr' by adding one more check."""
189
190        return [('or_expr', or_expr.add_check(check))]
191
192    @reducer('not', 'check')
193    def _make_not_expr(self, _not, check):
194        """Invert the result of another check."""
195
196        return [('check', _checks.NotCheck(check))]
197
198
199def _parse_check(rule):
200    """Parse a single base check rule into an appropriate Check object."""
201
202    # Handle the special checks
203    if rule == '!':
204        return _checks.FalseCheck()
205    elif rule == '@':
206        return _checks.TrueCheck()
207
208    try:
209        kind, match = rule.split(':', 1)
210    except Exception:
211        LOG.exception('Failed to understand rule %s', rule)
212        # If the rule is invalid, we'll fail closed
213        return _checks.FalseCheck()
214
215    # Find what implements the check
216    extension_checks = _checks.get_extensions()
217    if kind in extension_checks:
218        return extension_checks[kind](kind, match)
219    elif kind in _checks.registered_checks:
220        return _checks.registered_checks[kind](kind, match)
221    elif None in _checks.registered_checks:
222        return _checks.registered_checks[None](kind, match)
223    else:
224        LOG.error('No handler for matches of kind %s', kind)
225        return _checks.FalseCheck()
226
227
228def _parse_list_rule(rule):
229    """Translates the old list-of-lists syntax into a tree of Check objects.
230
231    Provided for backwards compatibility.
232    """
233
234    # Empty rule defaults to True
235    if not rule:
236        return _checks.TrueCheck()
237
238    # Outer list is joined by "or"; inner list by "and"
239    or_list = []
240    for inner_rule in rule:
241        # Skip empty inner lists
242        if not inner_rule:
243            continue
244
245        # Handle bare strings
246        if isinstance(inner_rule, str):
247            inner_rule = [inner_rule]
248
249        # Parse the inner rules into Check objects
250        and_list = [_parse_check(r) for r in inner_rule]
251
252        # Append the appropriate check to the or_list
253        if len(and_list) == 1:
254            or_list.append(and_list[0])
255        else:
256            or_list.append(_checks.AndCheck(and_list))
257
258    # If we have only one check, omit the "or"
259    if not or_list:
260        return _checks.FalseCheck()
261    elif len(or_list) == 1:
262        return or_list[0]
263
264    return _checks.OrCheck(or_list)
265
266
267# Used for tokenizing the policy language
268_tokenize_re = re.compile(r'\s+')
269
270
271def _parse_tokenize(rule):
272    """Tokenizer for the policy language.
273
274    Most of the single-character tokens are specified in the
275    _tokenize_re; however, parentheses need to be handled specially,
276    because they can appear inside a check string.  Thankfully, those
277    parentheses that appear inside a check string can never occur at
278    the very beginning or end ("%(variable)s" is the correct syntax).
279    """
280
281    for tok in _tokenize_re.split(rule):
282        # Skip empty tokens
283        if not tok or tok.isspace():
284            continue
285
286        # Handle leading parens on the token
287        clean = tok.lstrip('(')
288        for i in range(len(tok) - len(clean)):
289            yield '(', '('
290
291        # If it was only parentheses, continue
292        if not clean:
293            continue
294        else:
295            tok = clean
296
297        # Handle trailing parens on the token
298        clean = tok.rstrip(')')
299        trail = len(tok) - len(clean)
300
301        # Yield the cleaned token
302        lowered = clean.lower()
303        if lowered in ('and', 'or', 'not'):
304            # Special tokens
305            yield lowered, clean
306        elif clean:
307            # Not a special token, but not composed solely of ')'
308            if len(tok) >= 2 and ((tok[0], tok[-1]) in
309                                  [('"', '"'), ("'", "'")]):
310                # It's a quoted string
311                yield 'string', tok[1:-1]
312            else:
313                yield 'check', _parse_check(clean)
314
315        # Yield the trailing parens
316        for i in range(trail):
317            yield ')', ')'
318
319
320def _parse_text_rule(rule):
321    """Parses policy to the tree.
322
323    Translates a policy written in the policy language into a tree of
324    Check objects.
325    """
326
327    # Empty rule means always accept
328    if not rule:
329        return _checks.TrueCheck()
330
331    # Parse the token stream
332    state = ParseState()
333    for tok, value in _parse_tokenize(rule):
334        state.shift(tok, value)
335
336    try:
337        return state.result
338    except ValueError:
339        # Couldn't parse the rule
340        LOG.exception('Failed to understand rule %s', rule)
341
342        # Fail closed
343        return _checks.FalseCheck()
344
345
346def parse_rule(rule):
347    """Parses a policy rule into a tree of :class:`.Check` objects."""
348
349    # If the rule is a string, it's in the policy language
350    if isinstance(rule, str):
351        return _parse_text_rule(rule)
352    return _parse_list_rule(rule)
353