1## @file
2# This file is used to check PCD logical expression
3#
4# Copyright (c) 2011 - 2014, Intel Corporation. All rights reserved.<BR>
5#
6# This program and the accompanying materials are licensed and made available
7# under the terms and conditions of the BSD License which accompanies this
8# distribution. The full text of the license may be found at
9# http://opensource.org/licenses/bsd-license.php
10#
11# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
12# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
13
14'''
15ExpressionValidate
16'''
17
18##
19# Import Modules
20#
21import re
22from Logger import StringTable as ST
23
24## IsValidBareCString
25#
26# Check if String is comprised by whitespace(0x20), !(0x21), 0x23 - 0x7E
27# or '\n', '\t', '\f', '\r', '\b', '\0', '\\'
28#
29# @param String: string to be checked
30#
31def IsValidBareCString(String):
32    EscapeList = ['n', 't', 'f', 'r', 'b', '0', '\\', '"']
33    PreChar = ''
34    LastChar = ''
35    for Char in String:
36        LastChar = Char
37        if PreChar == '\\':
38            if Char not in EscapeList:
39                return False
40            if Char == '\\':
41                PreChar = ''
42                continue
43        else:
44            IntChar = ord(Char)
45            if IntChar != 0x20 and IntChar != 0x09 and IntChar != 0x21 \
46                and (IntChar < 0x23 or IntChar > 0x7e):
47                return False
48        PreChar = Char
49
50    # Last char cannot be \ if PreChar is not \
51    if LastChar == '\\' and PreChar == LastChar:
52        return False
53    return True
54
55def _ValidateToken(Token):
56    Token = Token.strip()
57    Index = Token.find("\"")
58    if Index != -1:
59        return IsValidBareCString(Token[Index+1:-1])
60    return True
61
62## _ExprError
63#
64# @param      Exception:    Exception
65#
66class _ExprError(Exception):
67    def __init__(self, Error = ''):
68        Exception.__init__(self)
69        self.Error = Error
70
71## _ExprBase
72#
73class _ExprBase:
74    HEX_PATTERN = '[\t\s]*0[xX][a-fA-F0-9]+'
75    INT_PATTERN = '[\t\s]*[0-9]+'
76    MACRO_PATTERN = '[\t\s]*\$\(([A-Z][_A-Z0-9]*)\)'
77    PCD_PATTERN = \
78    '[\t\s]*[_a-zA-Z][a-zA-Z0-9_]*[\t\s]*\.[\t\s]*[_a-zA-Z][a-zA-Z0-9_]*'
79    QUOTED_PATTERN = '[\t\s]*L?"[^"]*"'
80    BOOL_PATTERN = '[\t\s]*(true|True|TRUE|false|False|FALSE)'
81    def __init__(self, Token):
82        self.Token = Token
83        self.Index = 0
84        self.Len = len(Token)
85
86    ## SkipWhitespace
87    #
88    def SkipWhitespace(self):
89        for Char in self.Token[self.Index:]:
90            if Char not in ' \t':
91                break
92            self.Index += 1
93
94    ## IsCurrentOp
95    #
96    # @param      OpList:   option list
97    #
98    def IsCurrentOp(self, OpList):
99        self.SkipWhitespace()
100        LetterOp = ["EQ", "NE", "GE", "LE", "GT", "LT", "NOT", "and", "AND",
101                    "or", "OR", "XOR"]
102        OpMap = {
103            '|' : '|',
104            '&' : '&',
105            '!' : '=',
106            '>' : '=',
107            '<' : '='
108        }
109
110        for Operator in OpList:
111            if not self.Token[self.Index:].startswith(Operator):
112                continue
113
114            self.Index += len(Operator)
115            Char = self.Token[self.Index : self.Index + 1]
116
117            if (Operator in LetterOp and (Char == '_' or Char.isalnum())) \
118                or (Operator in OpMap and OpMap[Operator] == Char):
119                self.Index -= len(Operator)
120                break
121
122            return True
123
124        return False
125
126## _LogicalExpressionParser
127#
128# @param      _ExprBase:   _ExprBase object
129#
130class _LogicalExpressionParser(_ExprBase):
131    #
132    # STRINGITEM can only be logical field according to spec
133    #
134    STRINGITEM = -1
135
136    #
137    # Evaluate to True or False
138    #
139    LOGICAL = 0
140    REALLOGICAL = 2
141
142    #
143    # Just arithmetic expression
144    #
145    ARITH = 1
146
147    def __init__(self, Token):
148        _ExprBase.__init__(self, Token)
149        self.Parens = 0
150
151    def _CheckToken(self, MatchList):
152        for Match in MatchList:
153            if Match and Match.start() == 0:
154                if not _ValidateToken(
155                            self.Token[self.Index:self.Index+Match.end()]
156                        ):
157                    return False
158
159                self.Index += Match.end()
160                if self.Token[self.Index - 1] == '"':
161                    return True
162                if self.Token[self.Index:self.Index+1] == '_' or \
163                    self.Token[self.Index:self.Index+1].isalnum():
164                    self.Index -= Match.end()
165                    return False
166
167                Token = self.Token[self.Index - Match.end():self.Index]
168                if Token.strip() in ["EQ", "NE", "GE", "LE", "GT", "LT",
169                    "NOT", "and", "AND", "or", "OR", "XOR"]:
170                    self.Index -= Match.end()
171                    return False
172
173                return True
174
175        return False
176
177    def IsAtomicNumVal(self):
178        #
179        # Hex number
180        #
181        Match1 = re.compile(self.HEX_PATTERN).match(self.Token[self.Index:])
182
183        #
184        # Number
185        #
186        Match2 = re.compile(self.INT_PATTERN).match(self.Token[self.Index:])
187
188        #
189        # Macro
190        #
191        Match3 = re.compile(self.MACRO_PATTERN).match(self.Token[self.Index:])
192
193        #
194        # PcdName
195        #
196        Match4 = re.compile(self.PCD_PATTERN).match(self.Token[self.Index:])
197
198        return self._CheckToken([Match1, Match2, Match3, Match4])
199
200
201    def IsAtomicItem(self):
202        #
203        # Macro
204        #
205        Match1 = re.compile(self.MACRO_PATTERN).match(self.Token[self.Index:])
206
207        #
208        # PcdName
209        #
210        Match2 = re.compile(self.PCD_PATTERN).match(self.Token[self.Index:])
211
212        #
213        # Quoted string
214        #
215        Match3 = re.compile(self.QUOTED_PATTERN).\
216            match(self.Token[self.Index:].replace('\\\\', '//').\
217                  replace('\\\"', '\\\''))
218
219        return self._CheckToken([Match1, Match2, Match3])
220
221    ## A || B
222    #
223    def LogicalExpression(self):
224        Ret = self.SpecNot()
225        while self.IsCurrentOp(['||', 'OR', 'or', '&&', 'AND', 'and', 'XOR', 'xor', '^']):
226            if self.Token[self.Index-1] == '|' and self.Parens <= 0:
227                raise  _ExprError(ST.ERR_EXPR_OR % self.Token)
228            if Ret not in [self.ARITH, self.LOGICAL, self.REALLOGICAL, self.STRINGITEM]:
229                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
230            Ret = self.SpecNot()
231            if Ret not in [self.ARITH, self.LOGICAL, self.REALLOGICAL, self.STRINGITEM]:
232                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
233            Ret = self.REALLOGICAL
234        return Ret
235
236    def SpecNot(self):
237        if self.IsCurrentOp(["NOT", "!", "not"]):
238            return self.SpecNot()
239        return self.Rel()
240
241    ## A < B, A > B, A <= B, A >= B
242    #
243    def Rel(self):
244        Ret = self.Expr()
245        if self.IsCurrentOp(["<=", ">=", ">", "<", "GT", "LT", "GE", "LE",
246                             "==", "EQ", "!=", "NE"]):
247            if Ret == self.STRINGITEM:
248                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
249            Ret = self.Expr()
250            if Ret == self.REALLOGICAL:
251                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
252            Ret = self.REALLOGICAL
253        return Ret
254
255    ## A + B, A - B
256    #
257    def Expr(self):
258        Ret = self.Factor()
259        while self.IsCurrentOp(["+", "-", "&", "|", "^", "XOR", "xor"]):
260            if self.Token[self.Index-1] == '|' and self.Parens <= 0:
261                raise  _ExprError(ST.ERR_EXPR_OR)
262            if Ret == self.STRINGITEM or Ret == self.REALLOGICAL:
263                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
264            Ret = self.Factor()
265            if Ret == self.STRINGITEM or Ret == self.REALLOGICAL:
266                raise _ExprError(ST.ERR_EXPR_LOGICAL % self.Token)
267            Ret = self.ARITH
268        return Ret
269
270    ## Factor
271    #
272    def Factor(self):
273        if self.IsCurrentOp(["("]):
274            self.Parens += 1
275            Ret = self.LogicalExpression()
276            if not self.IsCurrentOp([")"]):
277                raise _ExprError(ST.ERR_EXPR_RIGHT_PAREN % \
278                                 (self.Token, self.Token[self.Index:]))
279            self.Parens -= 1
280            return Ret
281
282        if self.IsAtomicItem():
283            if self.Token[self.Index - 1] == '"':
284                return self.STRINGITEM
285            return self.LOGICAL
286        elif self.IsAtomicNumVal():
287            return self.ARITH
288        else:
289            raise _ExprError(ST.ERR_EXPR_FACTOR % \
290                             (self.Token[self.Index:], self.Token))
291
292    ## IsValidLogicalExpression
293    #
294    def IsValidLogicalExpression(self):
295        if self.Len == 0:
296            return False, ST.ERR_EXPRESS_EMPTY
297        try:
298            if self.LogicalExpression() not in [self.ARITH, self.LOGICAL, self.REALLOGICAL, self.STRINGITEM]:
299                return False, ST.ERR_EXPR_LOGICAL % self.Token
300        except _ExprError, XExcept:
301            return False, XExcept.Error
302        self.SkipWhitespace()
303        if self.Index != self.Len:
304            return False, (ST.ERR_EXPR_BOOLEAN % \
305                           (self.Token[self.Index:], self.Token))
306        return True, ''
307
308## _ValidRangeExpressionParser
309#
310class _ValidRangeExpressionParser(_ExprBase):
311    INT_RANGE_PATTERN = '[\t\s]*[0-9]+[\t\s]*-[\t\s]*[0-9]+'
312    HEX_RANGE_PATTERN = \
313        '[\t\s]*0[xX][a-fA-F0-9]+[\t\s]*-[\t\s]*0[xX][a-fA-F0-9]+'
314    def __init__(self, Token):
315        _ExprBase.__init__(self, Token)
316        self.Parens = 0
317        self.HEX = 1
318        self.INT = 2
319        self.IsParenHappen = False
320        self.IsLogicalOpHappen = False
321
322    ## IsValidRangeExpression
323    #
324    def IsValidRangeExpression(self):
325        if self.Len == 0:
326            return False, ST.ERR_EXPR_RANGE_EMPTY
327        try:
328            if self.RangeExpression() not in [self.HEX, self.INT]:
329                return False, ST.ERR_EXPR_RANGE % self.Token
330        except _ExprError, XExcept:
331            return False, XExcept.Error
332
333        self.SkipWhitespace()
334        if self.Index != self.Len:
335            return False, (ST.ERR_EXPR_RANGE % self.Token)
336        return True, ''
337
338    ## RangeExpression
339    #
340    def RangeExpression(self):
341        Ret = self.Unary()
342        while self.IsCurrentOp(['OR', 'AND', 'and', 'or']):
343            self.IsLogicalOpHappen = True
344            if not self.IsParenHappen:
345                raise _ExprError(ST.ERR_PAREN_NOT_USED % self.Token)
346            self.IsParenHappen = False
347            Ret = self.Unary()
348
349        if self.IsCurrentOp(['XOR']):
350            Ret = self.Unary()
351
352        return Ret
353
354    ## Unary
355    #
356    def Unary(self):
357        if self.IsCurrentOp(["NOT"]):
358            return self.Unary()
359
360        return self.ValidRange()
361
362    ## ValidRange
363    #
364    def ValidRange(self):
365        Ret = -1
366        if self.IsCurrentOp(["("]):
367            self.IsLogicalOpHappen = False
368            self.IsParenHappen = True
369            self.Parens += 1
370            if self.Parens > 1:
371                raise _ExprError(ST.ERR_EXPR_RANGE_DOUBLE_PAREN_NESTED % self.Token)
372            Ret = self.RangeExpression()
373            if not self.IsCurrentOp([")"]):
374                raise _ExprError(ST.ERR_EXPR_RIGHT_PAREN % self.Token)
375            self.Parens -= 1
376            return Ret
377
378        if self.IsLogicalOpHappen:
379            raise _ExprError(ST.ERR_PAREN_NOT_USED % self.Token)
380
381        if self.IsCurrentOp(["LT", "GT", "LE", "GE", "EQ", "XOR"]):
382            IntMatch = \
383                re.compile(self.INT_PATTERN).match(self.Token[self.Index:])
384            HexMatch = \
385                re.compile(self.HEX_PATTERN).match(self.Token[self.Index:])
386            if HexMatch and HexMatch.start() == 0:
387                self.Index += HexMatch.end()
388                Ret = self.HEX
389            elif IntMatch and IntMatch.start() == 0:
390                self.Index += IntMatch.end()
391                Ret = self.INT
392            else:
393                raise _ExprError(ST.ERR_EXPR_RANGE_FACTOR % (self.Token[self.Index:], self.Token))
394        else:
395            IntRangeMatch = re.compile(
396                self.INT_RANGE_PATTERN).match(self.Token[self.Index:]
397            )
398            HexRangeMatch = re.compile(
399                self.HEX_RANGE_PATTERN).match(self.Token[self.Index:]
400            )
401            if HexRangeMatch and HexRangeMatch.start() == 0:
402                self.Index += HexRangeMatch.end()
403                Ret = self.HEX
404            elif IntRangeMatch and IntRangeMatch.start() == 0:
405                self.Index += IntRangeMatch.end()
406                Ret = self.INT
407            else:
408                raise _ExprError(ST.ERR_EXPR_RANGE % self.Token)
409
410        return Ret
411
412## _ValidListExpressionParser
413#
414class _ValidListExpressionParser(_ExprBase):
415    VALID_LIST_PATTERN = '(0[xX][0-9a-fA-F]+|[0-9]+)([\t\s]*,[\t\s]*(0[xX][0-9a-fA-F]+|[0-9]+))*'
416    def __init__(self, Token):
417        _ExprBase.__init__(self, Token)
418        self.NUM = 1
419
420    def IsValidListExpression(self):
421        if self.Len == 0:
422            return False, ST.ERR_EXPR_LIST_EMPTY
423        try:
424            if self.ListExpression() not in [self.NUM]:
425                return False, ST.ERR_EXPR_LIST % self.Token
426        except _ExprError, XExcept:
427            return False, XExcept.Error
428
429        self.SkipWhitespace()
430        if self.Index != self.Len:
431            return False, (ST.ERR_EXPR_LIST % self.Token)
432
433        return True, ''
434
435    def ListExpression(self):
436        Ret = -1
437        self.SkipWhitespace()
438        ListMatch = re.compile(self.VALID_LIST_PATTERN).match(self.Token[self.Index:])
439        if ListMatch and ListMatch.start() == 0:
440            self.Index += ListMatch.end()
441            Ret = self.NUM
442        else:
443            raise _ExprError(ST.ERR_EXPR_LIST % self.Token)
444
445        return Ret
446
447## _StringTestParser
448#
449class _StringTestParser(_ExprBase):
450    def __init__(self, Token):
451        _ExprBase.__init__(self, Token)
452
453    ## IsValidStringTest
454    #
455    def IsValidStringTest(self):
456        if self.Len == 0:
457            return False, ST.ERR_EXPR_EMPTY
458        try:
459            self.StringTest()
460        except _ExprError, XExcept:
461            return False, XExcept.Error
462        return True, ''
463
464    ## StringItem
465    #
466    def StringItem(self):
467        Match1 = re.compile(self.QUOTED_PATTERN)\
468            .match(self.Token[self.Index:].replace('\\\\', '//')\
469                   .replace('\\\"', '\\\''))
470        Match2 = re.compile(self.MACRO_PATTERN).match(self.Token[self.Index:])
471        Match3 = re.compile(self.PCD_PATTERN).match(self.Token[self.Index:])
472        MatchList = [Match1, Match2, Match3]
473        for Match in MatchList:
474            if Match and Match.start() == 0:
475                if not _ValidateToken(
476                            self.Token[self.Index:self.Index+Match.end()]
477                        ):
478                    raise _ExprError(ST.ERR_EXPR_STRING_ITEM % \
479                                     (self.Token, self.Token[self.Index:]))
480                self.Index += Match.end()
481                Token = self.Token[self.Index - Match.end():self.Index]
482                if Token.strip() in ["EQ", "NE"]:
483                    raise _ExprError(ST.ERR_EXPR_STRING_ITEM % \
484                             (self.Token, self.Token[self.Index:]))
485                return
486        else:
487            raise _ExprError(ST.ERR_EXPR_STRING_ITEM % \
488                             (self.Token, self.Token[self.Index:]))
489
490    ## StringTest
491    #
492    def StringTest(self):
493        self.StringItem()
494        if not self.IsCurrentOp(["==", "EQ", "!=", "NE"]):
495            raise _ExprError(ST.ERR_EXPR_EQUALITY % \
496                             (self.Token[self.Index:], self.Token))
497        self.StringItem()
498        if self.Index != self.Len:
499            raise _ExprError(ST.ERR_EXPR_BOOLEAN % \
500                             (self.Token[self.Index:], self.Token))
501
502##
503# Check syntax of string test
504#
505# @param Token: string test token
506#
507def IsValidStringTest(Token, Flag=False):
508    #
509    # Not do the check right now, keep the implementation for future enhancement.
510    #
511    if not Flag:
512        return True, ""
513    return _StringTestParser(Token).IsValidStringTest()
514
515
516##
517# Check syntax of logical expression
518#
519# @param Token: expression token
520#
521def IsValidLogicalExpr(Token, Flag=False):
522    #
523    # Not do the check right now, keep the implementation for future enhancement.
524    #
525    if not Flag:
526        return True, ""
527    return _LogicalExpressionParser(Token).IsValidLogicalExpression()
528
529##
530# Check syntax of range expression
531#
532# @param Token: range expression token
533#
534def IsValidRangeExpr(Token):
535    return _ValidRangeExpressionParser(Token).IsValidRangeExpression()
536
537##
538# Check syntax of value list expression token
539#
540# @param Token: value list expression token
541#
542def IsValidListExpr(Token):
543    return _ValidListExpressionParser(Token).IsValidListExpression()
544
545##
546# Check whether the feature flag expression is valid or not
547#
548# @param Token: feature flag expression
549#
550def IsValidFeatureFlagExp(Token, Flag=False):
551    #
552    # Not do the check right now, keep the implementation for future enhancement.
553    #
554    if not Flag:
555        return True, "", Token
556    else:
557        if Token in ['TRUE', 'FALSE', 'true', 'false', 'True', 'False',
558                     '0x1', '0x01', '0x0', '0x00']:
559            return True, ""
560        Valid, Cause = IsValidStringTest(Token, Flag)
561        if not Valid:
562            Valid, Cause = IsValidLogicalExpr(Token, Flag)
563        if not Valid:
564            return False, Cause
565        return True, ""
566
567if __name__ == '__main__':
568#    print IsValidRangeExpr('LT 9')
569    print _LogicalExpressionParser('gCrownBayTokenSpaceGuid.PcdPciDevice1BridgeAddressLE0').IsValidLogicalExpression()
570
571
572
573