2 # This file is used to parse and evaluate range expression in Pcd declaration.
4 # Copyright (c) 2015 - 2018, Intel Corporation. All rights reserved.<BR>
5 # This program and the accompanying materials
6 # are licensed and made available under the terms and conditions of the BSD License
7 # which accompanies this distribution. The full text of the license may be found at
8 # http://opensource.org/licenses/bsd-license.php
10 # THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
15 from __future__
import print_function
16 from Common
.GlobalData
import *
17 from CommonDataClass
.Exceptions
import BadExpression
18 from CommonDataClass
.Exceptions
import WrnExpression
20 from Common
.Expression
import PcdPattern
, BaseExpression
21 from Common
.DataType
import *
23 ERR_STRING_EXPR
= 'This operator cannot be used in string expression: [%s].'
24 ERR_SNYTAX
= 'Syntax error, the rest of expression cannot be evaluated: [%s].'
25 ERR_MATCH
= 'No matching right parenthesis.'
26 ERR_STRING_TOKEN
= 'Bad string token: [%s].'
27 ERR_MACRO_TOKEN
= 'Bad macro token: [%s].'
28 ERR_EMPTY_TOKEN
= 'Empty token is not allowed.'
29 ERR_PCD_RESOLVE
= 'PCD token cannot be resolved: [%s].'
30 ERR_VALID_TOKEN
= 'No more valid token found from rest of string: [%s].'
31 ERR_EXPR_TYPE
= 'Different types found in expression.'
32 ERR_OPERATOR_UNSUPPORT
= 'Unsupported operator: [%s]'
33 ERR_REL_NOT_IN
= 'Expect "IN" after "not" operator.'
34 WRN_BOOL_EXPR
= 'Operand of boolean type cannot be used in arithmetic expression.'
35 WRN_EQCMP_STR_OTHERS
= '== Comparison between Operand of string type and Boolean/Number Type always return False.'
36 WRN_NECMP_STR_OTHERS
= '!= Comparison between Operand of string type and Boolean/Number Type always return True.'
37 ERR_RELCMP_STR_OTHERS
= 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].'
38 ERR_STRING_CMP
= 'Unicode string and general string cannot be compared: [%s %s %s]'
39 ERR_ARRAY_TOKEN
= 'Bad C array or C format GUID token: [%s].'
40 ERR_ARRAY_ELE
= 'This must be HEX value for NList or Array: [%s].'
41 ERR_EMPTY_EXPR
= 'Empty expression is not allowed.'
42 ERR_IN_OPERAND
= 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).'
44 class RangeObject(object):
45 def __init__(self
, start
, end
, empty
= False):
47 if int(start
) < int(end
):
48 self
.start
= int(start
)
55 class RangeContainer(object):
59 def push(self
, RangeObject
):
60 self
.rangelist
.append(RangeObject
)
61 self
.rangelist
= sorted(self
.rangelist
, key
= lambda rangeobj
: rangeobj
.start
)
65 for item
in self
.rangelist
:
70 for rangeobj
in self
.rangelist
:
71 if rangeobj
.empty
== True:
74 newrangelist
.append(rangeobj
)
75 self
.rangelist
= newrangelist
78 for i
in range(0, len(self
.rangelist
) - 1):
79 if self
.rangelist
[i
+ 1].start
> self
.rangelist
[i
].end
:
82 self
.rangelist
[i
+ 1].start
= self
.rangelist
[i
].start
83 self
.rangelist
[i
+ 1].end
= self
.rangelist
[i
+ 1].end
> self
.rangelist
[i
].end
and self
.rangelist
[i
+ 1].end
or self
.rangelist
[i
].end
84 self
.rangelist
[i
].empty
= True
89 print("----------------------")
91 for object in self
.rangelist
:
92 rangelist
= rangelist
+ "[%d , %d]" % (object.start
, object.end
)
96 class XOROperatorObject(object):
99 def Calculate(self
, Operand
, DataType
, SymbolTable
):
100 if isinstance(Operand
, type('')) and not Operand
.isalnum():
102 raise BadExpression(ERR_SNYTAX
% Expr
)
103 rangeId
= str(uuid
.uuid1())
104 rangeContainer
= RangeContainer()
105 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
106 rangeContainer
.push(RangeObject(int(Operand
) + 1, MAX_VAL_TYPE
[DataType
]))
107 SymbolTable
[rangeId
] = rangeContainer
110 class LEOperatorObject(object):
113 def Calculate(self
, Operand
, DataType
, SymbolTable
):
114 if isinstance(Operand
, type('')) and not Operand
.isalnum():
116 raise BadExpression(ERR_SNYTAX
% Expr
)
117 rangeId1
= str(uuid
.uuid1())
118 rangeContainer
= RangeContainer()
119 rangeContainer
.push(RangeObject(0, int(Operand
)))
120 SymbolTable
[rangeId1
] = rangeContainer
122 class LTOperatorObject(object):
125 def Calculate(self
, Operand
, DataType
, SymbolTable
):
126 if isinstance(Operand
, type('')) and not Operand
.isalnum():
128 raise BadExpression(ERR_SNYTAX
% Expr
)
129 rangeId1
= str(uuid
.uuid1())
130 rangeContainer
= RangeContainer()
131 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
132 SymbolTable
[rangeId1
] = rangeContainer
135 class GEOperatorObject(object):
138 def Calculate(self
, Operand
, DataType
, SymbolTable
):
139 if isinstance(Operand
, type('')) and not Operand
.isalnum():
141 raise BadExpression(ERR_SNYTAX
% Expr
)
142 rangeId1
= str(uuid
.uuid1())
143 rangeContainer
= RangeContainer()
144 rangeContainer
.push(RangeObject(int(Operand
), MAX_VAL_TYPE
[DataType
]))
145 SymbolTable
[rangeId1
] = rangeContainer
148 class GTOperatorObject(object):
151 def Calculate(self
, Operand
, DataType
, SymbolTable
):
152 if isinstance(Operand
, type('')) and not Operand
.isalnum():
154 raise BadExpression(ERR_SNYTAX
% Expr
)
155 rangeId1
= str(uuid
.uuid1())
156 rangeContainer
= RangeContainer()
157 rangeContainer
.push(RangeObject(int(Operand
) + 1, MAX_VAL_TYPE
[DataType
]))
158 SymbolTable
[rangeId1
] = rangeContainer
161 class EQOperatorObject(object):
164 def Calculate(self
, Operand
, DataType
, SymbolTable
):
165 if isinstance(Operand
, type('')) and not Operand
.isalnum():
167 raise BadExpression(ERR_SNYTAX
% Expr
)
168 rangeId1
= str(uuid
.uuid1())
169 rangeContainer
= RangeContainer()
170 rangeContainer
.push(RangeObject(int(Operand
), int(Operand
)))
171 SymbolTable
[rangeId1
] = rangeContainer
174 def GetOperatorObject(Operator
):
176 return GTOperatorObject()
177 elif Operator
== '>=':
178 return GEOperatorObject()
179 elif Operator
== '<':
180 return LTOperatorObject()
181 elif Operator
== '<=':
182 return LEOperatorObject()
183 elif Operator
== '==':
184 return EQOperatorObject()
185 elif Operator
== '^':
186 return XOROperatorObject()
188 raise BadExpression("Bad Operator")
190 class RangeExpression(BaseExpression
):
191 # Logical operator mapping
193 '&&' : 'and', '||' : 'or',
194 '!' : 'not', 'AND': 'and',
195 'OR' : 'or' , 'NOT': 'not',
196 'XOR': '^' , 'xor': '^',
197 'EQ' : '==' , 'NE' : '!=',
198 'GT' : '>' , 'LT' : '<',
199 'GE' : '>=' , 'LE' : '<=',
203 NonLetterOpLst
= ['+', '-', '&', '|', '^', '!', '=', '>', '<']
205 RangePattern
= re
.compile(r
'[0-9]+ - [0-9]+')
207 def preProcessRangeExpr(self
, expr
):
209 # convert interval to object index. ex. 1 - 10 to a GUID
212 for HexNumber
in gHexPattern
.findall(expr
):
213 Number
= str(int(HexNumber
, 16))
214 NumberDict
[HexNumber
] = Number
215 for HexNum
in NumberDict
:
216 expr
= expr
.replace(HexNum
, NumberDict
[HexNum
])
219 for validrange
in self
.RangePattern
.findall(expr
):
220 start
, end
= validrange
.split(" - ")
221 start
= start
.strip()
223 rangeid
= str(uuid
.uuid1())
224 rangeContainer
= RangeContainer()
225 rangeContainer
.push(RangeObject(start
, end
))
226 self
.operanddict
[str(rangeid
)] = rangeContainer
227 rangedict
[validrange
] = str(rangeid
)
229 for validrange
in rangedict
:
230 expr
= expr
.replace(validrange
, rangedict
[validrange
])
236 def EvalRange(self
, Operator
, Oprand
):
238 operatorobj
= GetOperatorObject(Operator
)
239 return operatorobj
.Calculate(Oprand
, self
.PcdDataType
, self
.operanddict
)
241 def Rangeintersection(self
, Oprand1
, Oprand2
):
242 rangeContainer1
= self
.operanddict
[Oprand1
]
243 rangeContainer2
= self
.operanddict
[Oprand2
]
244 rangeContainer
= RangeContainer()
245 for range1
in rangeContainer1
.pop():
246 for range2
in rangeContainer2
.pop():
247 start1
= range1
.start
249 start2
= range2
.start
252 start1
, start2
= start2
, start1
253 end1
, end2
= end2
, end1
255 rangeid
= str(uuid
.uuid1())
256 rangeContainer
.push(RangeObject(0, 0, True))
258 rangeid
= str(uuid
.uuid1())
259 rangeContainer
.push(RangeObject(0, 0, True))
261 rangeid
= str(uuid
.uuid1())
262 rangeContainer
.push(RangeObject(end1
, end1
))
263 elif end1
<= end2
and end1
> start2
:
264 rangeid
= str(uuid
.uuid1())
265 rangeContainer
.push(RangeObject(start2
, end1
))
267 rangeid
= str(uuid
.uuid1())
268 rangeContainer
.push(RangeObject(start2
, end2
))
270 self
.operanddict
[rangeid
] = rangeContainer
271 # rangeContainer.dump()
274 def Rangecollections(self
, Oprand1
, Oprand2
):
276 rangeContainer1
= self
.operanddict
[Oprand1
]
277 rangeContainer2
= self
.operanddict
[Oprand2
]
278 rangeContainer
= RangeContainer()
280 for rangeobj
in rangeContainer2
.pop():
281 rangeContainer
.push(rangeobj
)
282 for rangeobj
in rangeContainer1
.pop():
283 rangeContainer
.push(rangeobj
)
285 rangeid
= str(uuid
.uuid1())
286 self
.operanddict
[rangeid
] = rangeContainer
288 # rangeContainer.dump()
292 def NegtiveRange(self
, Oprand1
):
293 rangeContainer1
= self
.operanddict
[Oprand1
]
298 for rangeobj
in rangeContainer1
.pop():
299 rangeContainer
= RangeContainer()
300 rangeid
= str(uuid
.uuid1())
302 rangeContainer
.push(RangeObject(0, MAX_VAL_TYPE
[self
.PcdDataType
]))
304 if rangeobj
.start
> 0:
305 rangeContainer
.push(RangeObject(0, rangeobj
.start
- 1))
306 if rangeobj
.end
< MAX_VAL_TYPE
[self
.PcdDataType
]:
307 rangeContainer
.push(RangeObject(rangeobj
.end
+ 1, MAX_VAL_TYPE
[self
.PcdDataType
]))
308 self
.operanddict
[rangeid
] = rangeContainer
309 rangeids
.append(rangeid
)
311 if len(rangeids
) == 0:
312 rangeContainer
= RangeContainer()
313 rangeContainer
.push(RangeObject(0, MAX_VAL_TYPE
[self
.PcdDataType
]))
314 rangeid
= str(uuid
.uuid1())
315 self
.operanddict
[rangeid
] = rangeContainer
318 if len(rangeids
) == 1:
321 re
= self
.Rangeintersection(rangeids
[0], rangeids
[1])
322 for i
in range(2, len(rangeids
)):
323 re
= self
.Rangeintersection(re
, rangeids
[i
])
325 rangeid2
= str(uuid
.uuid1())
326 self
.operanddict
[rangeid2
] = self
.operanddict
[re
]
329 def Eval(self
, Operator
, Oprand1
, Oprand2
= None):
331 if Operator
in ["!", "NOT", "not"]:
332 if not gGuidPattern
.match(Oprand1
.strip()):
333 raise BadExpression(ERR_STRING_EXPR
% Operator
)
334 return self
.NegtiveRange(Oprand1
)
336 if Operator
in ["==", ">=", "<=", ">", "<", '^']:
337 return self
.EvalRange(Operator
, Oprand1
)
338 elif Operator
== 'and' :
339 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
340 raise BadExpression(ERR_STRING_EXPR
% Operator
)
341 return self
.Rangeintersection(Oprand1
, Oprand2
)
342 elif Operator
== 'or':
343 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
344 raise BadExpression(ERR_STRING_EXPR
% Operator
)
345 return self
.Rangecollections(Oprand1
, Oprand2
)
347 raise BadExpression(ERR_STRING_EXPR
% Operator
)
350 def __init__(self
, Expression
, PcdDataType
, SymbolTable
= {}):
351 super(RangeExpression
, self
).__init
__(self
, Expression
, PcdDataType
, SymbolTable
)
352 self
._NoProcess
= False
353 if not isinstance(Expression
, type('')):
354 self
._Expr
= Expression
355 self
._NoProcess
= True
358 self
._Expr
= Expression
.strip()
360 if not self
._Expr
.strip():
361 raise BadExpression(ERR_EMPTY_EXPR
)
364 # The symbol table including PCD and macro mapping
366 self
._Symb
= SymbolTable
367 self
._Symb
.update(self
.LogicalOperators
)
369 self
._Len
= len(self
._Expr
)
371 self
._WarnExcept
= None
374 # Literal token without any conversion
375 self
._LiteralToken
= ''
377 # store the operand object
378 self
.operanddict
= {}
379 # The Pcd max value depends on PcdDataType
380 self
.PcdDataType
= PcdDataType
382 # Public entry for this class
383 # @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression
384 # True : return the evaluated str(value), used for PCD value
386 # @return: True or False if RealValue is False
387 # Evaluated value of string format if RealValue is True
389 def __call__(self
, RealValue
= False, Depth
= 0):
395 self
._Expr
= self
._Expr
.strip()
397 self
.preProcessRangeExpr(self
._Expr
)
399 # check if the expression does not need to evaluate
400 if RealValue
and Depth
== 0:
401 self
._Token
= self
._Expr
402 if gGuidPatternEnd
.match(self
._Expr
):
403 return [self
.operanddict
[self
._Expr
] ]
411 RangeIdList
= RealVal
.split("or")
413 for rangeid
in RangeIdList
:
414 RangeList
.append(self
.operanddict
[rangeid
.strip()])
418 # Template function to parse binary operators which have same precedence
419 # Expr [Operator Expr]*
420 def _ExprFuncTemplate(self
, EvalFunc
, OpSet
):
422 while self
._IsOperator
(OpSet
):
425 Val
= self
.Eval(Op
, Val
, EvalFunc())
426 except WrnExpression
as Warn
:
427 self
._WarnExcept
= Warn
433 return self
._ExprFuncTemplate
(self
._AndExpr
, {"OR", "or"})
437 return self
._ExprFuncTemplate
(self
._NeExpr
, {"AND", "and"})
440 Val
= self
._RelExpr
()
441 while self
._IsOperator
({"!=", "NOT", "not"}):
443 if Op
in ["!", "NOT", "not"]:
444 if not self
._IsOperator
({"IN", "in"}):
445 raise BadExpression(ERR_REL_NOT_IN
)
446 Op
+= ' ' + self
._Token
448 Val
= self
.Eval(Op
, Val
, self
._RelExpr
())
449 except WrnExpression
as Warn
:
450 self
._WarnExcept
= Warn
456 if self
._IsOperator
({"NOT", "LE", "GE", "LT", "GT", "EQ", "XOR"}):
460 return self
.Eval(Token
, Val
)
461 except WrnExpression
as Warn
:
462 self
._WarnExcept
= Warn
464 return self
._IdenExpr
()
466 # Parse identifier or encapsulated expression
468 Tk
= self
._GetToken
()
472 # _GetToken may also raise BadExpression
473 if self
._GetToken
() != ')':
474 raise BadExpression(ERR_MATCH
)
475 except BadExpression
:
476 raise BadExpression(ERR_MATCH
)
480 # Skip whitespace or tab
482 for Char
in self
._Expr
[self
._Idx
:]:
483 if Char
not in ' \t':
487 # Try to convert string to number
488 def __IsNumberToken(self
):
490 if self
._Token
.lower()[0:2] == '0x' and len(self
._Token
) > 2:
493 self
._Token
= int(self
._Token
, Radix
)
501 def __GetArray(self
):
504 self
.__GetNList
(True)
505 Token
+= self
._LiteralToken
506 if self
._Idx
>= self
._Len
or self
._Expr
[self
._Idx
] != '}':
507 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
510 # All whitespace and tabs in array are already stripped.
511 IsArray
= IsGuid
= False
512 if len(Token
.split(',')) == 11 and len(Token
.split(',{')) == 2 \
513 and len(Token
.split('},')) == 1:
514 HexLen
= [11, 6, 6, 5, 4, 4, 4, 4, 4, 4, 6]
515 HexList
= Token
.split(',')
516 if HexList
[3].startswith('{') and \
517 not [Index
for Index
, Hex
in enumerate(HexList
) if len(Hex
) > HexLen
[Index
]]:
519 if Token
.lstrip('{').rstrip('}').find('{') == -1:
520 if not [Hex
for Hex
in Token
.lstrip('{').rstrip('}').split(',') if len(Hex
) > 4]:
522 if not IsArray
and not IsGuid
:
523 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
525 self
._Token
= self
._LiteralToken
= Token
528 # Parse string, the format must be: "..."
529 def __GetString(self
):
535 # Replace escape \\\", \"
536 Expr
= self
._Expr
[self
._Idx
:].replace('\\\\', '//').replace('\\\"', '\\\'')
541 self
._Token
= self
._LiteralToken
= self
._Expr
[Idx
:self
._Idx
]
542 if not self
._Token
.endswith('"'):
543 raise BadExpression(ERR_STRING_TOKEN
% self
._Token
)
544 self
._Token
= self
._Token
[1:-1]
547 # Get token that is comprised by alphanumeric, underscore or dot(used by PCD)
548 # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...)
549 def __GetIdToken(self
, IsAlphaOp
= False):
551 for Ch
in self
._Expr
[self
._Idx
:]:
552 if not self
.__IsIdChar
(Ch
):
557 self
._Token
= self
._LiteralToken
= IdToken
559 self
.__ResolveToken
()
562 # Try to resolve token
563 def __ResolveToken(self
):
565 raise BadExpression(ERR_EMPTY_TOKEN
)
568 if PcdPattern
.match(self
._Token
):
569 if self
._Token
not in self
._Symb
:
570 Ex
= BadExpression(ERR_PCD_RESOLVE
% self
._Token
)
573 self
._Token
= RangeExpression(self
._Symb
[self
._Token
], self
._Symb
)(True, self
._Depth
+ 1)
574 if not isinstance(self
._Token
, type('')):
575 self
._LiteralToken
= hex(self
._Token
)
578 if self
._Token
.startswith('"'):
579 self
._Token
= self
._Token
[1:-1]
580 elif self
._Token
in ["FALSE", "false", "False"]:
582 elif self
._Token
in ["TRUE", "true", "True"]:
585 self
.__IsNumberToken
()
587 def __GetNList(self
, InArray
= False):
588 self
._GetSingleToken
()
589 if not self
.__IsHexLiteral
():
591 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
595 Expr
= self
._Expr
[self
._Idx
:]
596 if not Expr
.startswith(','):
599 NList
= self
._LiteralToken
600 while Expr
.startswith(','):
604 self
._GetSingleToken
()
605 if not self
.__IsHexLiteral
():
606 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
607 NList
+= self
._LiteralToken
609 Expr
= self
._Expr
[self
._Idx
:]
610 self
._Token
= self
._LiteralToken
= NList
613 def __IsHexLiteral(self
):
614 if self
._LiteralToken
.startswith('{') and \
615 self
._LiteralToken
.endswith('}'):
618 if gHexPattern
.match(self
._LiteralToken
):
619 Token
= self
._LiteralToken
[2:]
620 Token
= Token
.lstrip('0')
622 self
._LiteralToken
= '0x0'
624 self
._LiteralToken
= '0x' + Token
.lower()
629 return self
.__GetNList
()
633 return Ch
in '._/:' or Ch
.isalnum()
636 def _GetSingleToken(self
):
638 Expr
= self
._Expr
[self
._Idx
:]
639 if Expr
.startswith('L"'):
642 UStr
= self
.__GetString
()
643 self
._Token
= 'L"' + UStr
+ '"'
649 Match
= gGuidPattern
.match(Expr
)
650 if Match
and not Expr
[Match
.end():Match
.end() + 1].isalnum() \
651 and Expr
[Match
.end():Match
.end() + 1] != '_':
652 self
._Idx
+= Match
.end()
653 self
._Token
= Expr
[0:Match
.end()]
655 elif self
.__IsIdChar
(Ch
):
656 return self
.__GetIdToken
()
657 elif Ch
== '(' or Ch
== ')':
662 raise BadExpression(ERR_VALID_TOKEN
% Expr
)
665 def _GetOperator(self
):
667 LegalOpLst
= ['&&', '||', '!=', '==', '>=', '<='] + self
.NonLetterOpLst
670 Expr
= self
._Expr
[self
._Idx
:]
672 # Reach end of expression
676 # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not
677 if Expr
[0].isalpha():
678 return self
.__GetIdToken
(True)
680 # Start to get regular operator: +, -, <, > ...
681 if Expr
[0] not in self
.NonLetterOpLst
:
686 if Ch
in self
.NonLetterOpLst
:
687 if '!' == Ch
and OpToken
:
694 if OpToken
not in LegalOpLst
:
695 raise BadExpression(ERR_OPERATOR_UNSUPPORT
% OpToken
)
696 self
._Token
= OpToken