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