]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/Python/Common/RangeExpression.py
e9296e03f6a1d7101714634d13eb65bd7df3dea8
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 # SPDX-License-Identifier: BSD-2-Clause-Patent
9 from __future__
import print_function
10 from Common
.GlobalData
import *
11 from CommonDataClass
.Exceptions
import BadExpression
12 from CommonDataClass
.Exceptions
import WrnExpression
14 from Common
.Expression
import PcdPattern
, BaseExpression
15 from Common
.DataType
import *
16 from re
import compile
18 ERR_STRING_EXPR
= 'This operator cannot be used in string expression: [%s].'
19 ERR_SNYTAX
= 'Syntax error, the rest of expression cannot be evaluated: [%s].'
20 ERR_MATCH
= 'No matching right parenthesis.'
21 ERR_STRING_TOKEN
= 'Bad string token: [%s].'
22 ERR_MACRO_TOKEN
= 'Bad macro token: [%s].'
23 ERR_EMPTY_TOKEN
= 'Empty token is not allowed.'
24 ERR_PCD_RESOLVE
= 'The PCD should be FeatureFlag type or FixedAtBuild type: [%s].'
25 ERR_VALID_TOKEN
= 'No more valid token found from rest of string: [%s].'
26 ERR_EXPR_TYPE
= 'Different types found in expression.'
27 ERR_OPERATOR_UNSUPPORT
= 'Unsupported operator: [%s]'
28 ERR_REL_NOT_IN
= 'Expect "IN" after "not" operator.'
29 WRN_BOOL_EXPR
= 'Operand of boolean type cannot be used in arithmetic expression.'
30 WRN_EQCMP_STR_OTHERS
= '== Comparison between Operand of string type and Boolean/Number Type always return False.'
31 WRN_NECMP_STR_OTHERS
= '!= Comparison between Operand of string type and Boolean/Number Type always return True.'
32 ERR_RELCMP_STR_OTHERS
= 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].'
33 ERR_STRING_CMP
= 'Unicode string and general string cannot be compared: [%s %s %s]'
34 ERR_ARRAY_TOKEN
= 'Bad C array or C format GUID token: [%s].'
35 ERR_ARRAY_ELE
= 'This must be HEX value for NList or Array: [%s].'
36 ERR_EMPTY_EXPR
= 'Empty expression is not allowed.'
37 ERR_IN_OPERAND
= 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).'
39 class RangeObject(object):
40 def __init__(self
, start
, end
, empty
= False):
42 if int(start
) < int(end
):
43 self
.start
= int(start
)
50 class RangeContainer(object):
54 def push(self
, RangeObject
):
55 self
.rangelist
.append(RangeObject
)
56 self
.rangelist
= sorted(self
.rangelist
, key
= lambda rangeobj
: rangeobj
.start
)
60 for item
in self
.rangelist
:
65 for rangeobj
in self
.rangelist
:
66 if rangeobj
.empty
== True:
69 newrangelist
.append(rangeobj
)
70 self
.rangelist
= newrangelist
73 for i
in range(0, len(self
.rangelist
) - 1):
74 if self
.rangelist
[i
+ 1].start
> self
.rangelist
[i
].end
:
77 self
.rangelist
[i
+ 1].start
= self
.rangelist
[i
].start
78 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
79 self
.rangelist
[i
].empty
= True
84 print("----------------------")
86 for object in self
.rangelist
:
87 rangelist
= rangelist
+ "[%d , %d]" % (object.start
, object.end
)
91 class XOROperatorObject(object):
94 def Calculate(self
, Operand
, DataType
, SymbolTable
):
95 if isinstance(Operand
, type('')) and not Operand
.isalnum():
97 raise BadExpression(ERR_SNYTAX
% Expr
)
98 rangeId
= str(uuid
.uuid1())
99 rangeContainer
= RangeContainer()
100 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
101 rangeContainer
.push(RangeObject(int(Operand
) + 1, MAX_VAL_TYPE
[DataType
]))
102 SymbolTable
[rangeId
] = rangeContainer
105 class LEOperatorObject(object):
108 def Calculate(self
, Operand
, DataType
, SymbolTable
):
109 if isinstance(Operand
, type('')) and not Operand
.isalnum():
111 raise BadExpression(ERR_SNYTAX
% Expr
)
112 rangeId1
= str(uuid
.uuid1())
113 rangeContainer
= RangeContainer()
114 rangeContainer
.push(RangeObject(0, int(Operand
)))
115 SymbolTable
[rangeId1
] = rangeContainer
117 class LTOperatorObject(object):
120 def Calculate(self
, Operand
, DataType
, SymbolTable
):
121 if isinstance(Operand
, type('')) and not Operand
.isalnum():
123 raise BadExpression(ERR_SNYTAX
% Expr
)
124 rangeId1
= str(uuid
.uuid1())
125 rangeContainer
= RangeContainer()
126 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
127 SymbolTable
[rangeId1
] = rangeContainer
130 class GEOperatorObject(object):
133 def Calculate(self
, Operand
, DataType
, SymbolTable
):
134 if isinstance(Operand
, type('')) and not Operand
.isalnum():
136 raise BadExpression(ERR_SNYTAX
% Expr
)
137 rangeId1
= str(uuid
.uuid1())
138 rangeContainer
= RangeContainer()
139 rangeContainer
.push(RangeObject(int(Operand
), MAX_VAL_TYPE
[DataType
]))
140 SymbolTable
[rangeId1
] = rangeContainer
143 class GTOperatorObject(object):
146 def Calculate(self
, Operand
, DataType
, SymbolTable
):
147 if isinstance(Operand
, type('')) and not Operand
.isalnum():
149 raise BadExpression(ERR_SNYTAX
% Expr
)
150 rangeId1
= str(uuid
.uuid1())
151 rangeContainer
= RangeContainer()
152 rangeContainer
.push(RangeObject(int(Operand
) + 1, MAX_VAL_TYPE
[DataType
]))
153 SymbolTable
[rangeId1
] = rangeContainer
156 class EQOperatorObject(object):
159 def Calculate(self
, Operand
, DataType
, SymbolTable
):
160 if isinstance(Operand
, type('')) and not Operand
.isalnum():
162 raise BadExpression(ERR_SNYTAX
% Expr
)
163 rangeId1
= str(uuid
.uuid1())
164 rangeContainer
= RangeContainer()
165 rangeContainer
.push(RangeObject(int(Operand
), int(Operand
)))
166 SymbolTable
[rangeId1
] = rangeContainer
169 def GetOperatorObject(Operator
):
171 return GTOperatorObject()
172 elif Operator
== '>=':
173 return GEOperatorObject()
174 elif Operator
== '<':
175 return LTOperatorObject()
176 elif Operator
== '<=':
177 return LEOperatorObject()
178 elif Operator
== '==':
179 return EQOperatorObject()
180 elif Operator
== '^':
181 return XOROperatorObject()
183 raise BadExpression("Bad Operator")
185 class RangeExpression(BaseExpression
):
186 # Logical operator mapping
188 '&&' : 'and', '||' : 'or',
189 '!' : 'not', 'AND': 'and',
190 'OR' : 'or' , 'NOT': 'not',
191 'XOR': '^' , 'xor': '^',
192 'EQ' : '==' , 'NE' : '!=',
193 'GT' : '>' , 'LT' : '<',
194 'GE' : '>=' , 'LE' : '<=',
198 NonLetterOpLst
= ['+', '-', '&', '|', '^', '!', '=', '>', '<']
200 RangePattern
= compile(r
'[0-9]+ - [0-9]+')
202 def preProcessRangeExpr(self
, expr
):
204 # convert interval to object index. ex. 1 - 10 to a GUID
207 for HexNumber
in gHexPattern
.findall(expr
):
208 Number
= str(int(HexNumber
, 16))
209 NumberDict
[HexNumber
] = Number
210 for HexNum
in NumberDict
:
211 expr
= expr
.replace(HexNum
, NumberDict
[HexNum
])
214 for validrange
in self
.RangePattern
.findall(expr
):
215 start
, end
= validrange
.split(" - ")
216 start
= start
.strip()
218 rangeid
= str(uuid
.uuid1())
219 rangeContainer
= RangeContainer()
220 rangeContainer
.push(RangeObject(start
, end
))
221 self
.operanddict
[str(rangeid
)] = rangeContainer
222 rangedict
[validrange
] = str(rangeid
)
224 for validrange
in rangedict
:
225 expr
= expr
.replace(validrange
, rangedict
[validrange
])
231 def EvalRange(self
, Operator
, Oprand
):
233 operatorobj
= GetOperatorObject(Operator
)
234 return operatorobj
.Calculate(Oprand
, self
.PcdDataType
, self
.operanddict
)
236 def Rangeintersection(self
, Oprand1
, Oprand2
):
237 rangeContainer1
= self
.operanddict
[Oprand1
]
238 rangeContainer2
= self
.operanddict
[Oprand2
]
239 rangeContainer
= RangeContainer()
240 for range1
in rangeContainer1
.pop():
241 for range2
in rangeContainer2
.pop():
242 start1
= range1
.start
244 start2
= range2
.start
247 start1
, start2
= start2
, start1
248 end1
, end2
= end2
, end1
250 rangeid
= str(uuid
.uuid1())
251 rangeContainer
.push(RangeObject(0, 0, True))
253 rangeid
= str(uuid
.uuid1())
254 rangeContainer
.push(RangeObject(0, 0, True))
256 rangeid
= str(uuid
.uuid1())
257 rangeContainer
.push(RangeObject(end1
, end1
))
258 elif end1
<= end2
and end1
> start2
:
259 rangeid
= str(uuid
.uuid1())
260 rangeContainer
.push(RangeObject(start2
, end1
))
262 rangeid
= str(uuid
.uuid1())
263 rangeContainer
.push(RangeObject(start2
, end2
))
265 self
.operanddict
[rangeid
] = rangeContainer
266 # rangeContainer.dump()
269 def Rangecollections(self
, Oprand1
, Oprand2
):
271 rangeContainer1
= self
.operanddict
[Oprand1
]
272 rangeContainer2
= self
.operanddict
[Oprand2
]
273 rangeContainer
= RangeContainer()
275 for rangeobj
in rangeContainer2
.pop():
276 rangeContainer
.push(rangeobj
)
277 for rangeobj
in rangeContainer1
.pop():
278 rangeContainer
.push(rangeobj
)
280 rangeid
= str(uuid
.uuid1())
281 self
.operanddict
[rangeid
] = rangeContainer
283 # rangeContainer.dump()
287 def NegativeRange(self
, Oprand1
):
288 rangeContainer1
= self
.operanddict
[Oprand1
]
293 for rangeobj
in rangeContainer1
.pop():
294 rangeContainer
= RangeContainer()
295 rangeid
= str(uuid
.uuid1())
297 rangeContainer
.push(RangeObject(0, MAX_VAL_TYPE
[self
.PcdDataType
]))
299 if rangeobj
.start
> 0:
300 rangeContainer
.push(RangeObject(0, rangeobj
.start
- 1))
301 if rangeobj
.end
< MAX_VAL_TYPE
[self
.PcdDataType
]:
302 rangeContainer
.push(RangeObject(rangeobj
.end
+ 1, MAX_VAL_TYPE
[self
.PcdDataType
]))
303 self
.operanddict
[rangeid
] = rangeContainer
304 rangeids
.append(rangeid
)
306 if len(rangeids
) == 0:
307 rangeContainer
= RangeContainer()
308 rangeContainer
.push(RangeObject(0, MAX_VAL_TYPE
[self
.PcdDataType
]))
309 rangeid
= str(uuid
.uuid1())
310 self
.operanddict
[rangeid
] = rangeContainer
313 if len(rangeids
) == 1:
316 re
= self
.Rangeintersection(rangeids
[0], rangeids
[1])
317 for i
in range(2, len(rangeids
)):
318 re
= self
.Rangeintersection(re
, rangeids
[i
])
320 rangeid2
= str(uuid
.uuid1())
321 self
.operanddict
[rangeid2
] = self
.operanddict
[re
]
324 def Eval(self
, Operator
, Oprand1
, Oprand2
= None):
326 if Operator
in ["!", "NOT", "not"]:
327 if not gGuidPattern
.match(Oprand1
.strip()):
328 raise BadExpression(ERR_STRING_EXPR
% Operator
)
329 return self
.NegativeRange(Oprand1
)
331 if Operator
in ["==", ">=", "<=", ">", "<", '^']:
332 return self
.EvalRange(Operator
, Oprand1
)
333 elif Operator
== 'and' :
334 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
335 raise BadExpression(ERR_STRING_EXPR
% Operator
)
336 return self
.Rangeintersection(Oprand1
, Oprand2
)
337 elif Operator
== 'or':
338 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
339 raise BadExpression(ERR_STRING_EXPR
% Operator
)
340 return self
.Rangecollections(Oprand1
, Oprand2
)
342 raise BadExpression(ERR_STRING_EXPR
% Operator
)
345 def __init__(self
, Expression
, PcdDataType
, SymbolTable
= {}):
346 super(RangeExpression
, self
).__init
__(self
, Expression
, PcdDataType
, SymbolTable
)
347 self
._NoProcess
= False
348 if not isinstance(Expression
, type('')):
349 self
._Expr
= Expression
350 self
._NoProcess
= True
353 self
._Expr
= Expression
.strip()
355 if not self
._Expr
.strip():
356 raise BadExpression(ERR_EMPTY_EXPR
)
359 # The symbol table including PCD and macro mapping
361 self
._Symb
= SymbolTable
362 self
._Symb
.update(self
.LogicalOperators
)
364 self
._Len
= len(self
._Expr
)
366 self
._WarnExcept
= None
369 # Literal token without any conversion
370 self
._LiteralToken
= ''
372 # store the operand object
373 self
.operanddict
= {}
374 # The Pcd max value depends on PcdDataType
375 self
.PcdDataType
= PcdDataType
377 # Public entry for this class
378 # @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression
379 # True : return the evaluated str(value), used for PCD value
381 # @return: True or False if RealValue is False
382 # Evaluated value of string format if RealValue is True
384 def __call__(self
, RealValue
= False, Depth
= 0):
390 self
._Expr
= self
._Expr
.strip()
392 self
.preProcessRangeExpr(self
._Expr
)
394 # check if the expression does not need to evaluate
395 if RealValue
and Depth
== 0:
396 self
._Token
= self
._Expr
397 if gGuidPatternEnd
.match(self
._Expr
):
398 return [self
.operanddict
[self
._Expr
] ]
406 RangeIdList
= RealVal
.split("or")
408 for rangeid
in RangeIdList
:
409 RangeList
.append(self
.operanddict
[rangeid
.strip()])
413 # Template function to parse binary operators which have same precedence
414 # Expr [Operator Expr]*
415 def _ExprFuncTemplate(self
, EvalFunc
, OpSet
):
417 while self
._IsOperator
(OpSet
):
420 Val
= self
.Eval(Op
, Val
, EvalFunc())
421 except WrnExpression
as Warn
:
422 self
._WarnExcept
= Warn
428 return self
._ExprFuncTemplate
(self
._AndExpr
, {"OR", "or"})
432 return self
._ExprFuncTemplate
(self
._NeExpr
, {"AND", "and"})
435 Val
= self
._RelExpr
()
436 while self
._IsOperator
({"!=", "NOT", "not"}):
438 if Op
in ["!", "NOT", "not"]:
439 if not self
._IsOperator
({"IN", "in"}):
440 raise BadExpression(ERR_REL_NOT_IN
)
441 Op
+= ' ' + self
._Token
443 Val
= self
.Eval(Op
, Val
, self
._RelExpr
())
444 except WrnExpression
as Warn
:
445 self
._WarnExcept
= Warn
451 if self
._IsOperator
({"NOT", "LE", "GE", "LT", "GT", "EQ", "XOR"}):
455 return self
.Eval(Token
, Val
)
456 except WrnExpression
as Warn
:
457 self
._WarnExcept
= Warn
459 return self
._IdenExpr
()
461 # Parse identifier or encapsulated expression
463 Tk
= self
._GetToken
()
467 # _GetToken may also raise BadExpression
468 if self
._GetToken
() != ')':
469 raise BadExpression(ERR_MATCH
)
470 except BadExpression
:
471 raise BadExpression(ERR_MATCH
)
475 # Skip whitespace or tab
477 for Char
in self
._Expr
[self
._Idx
:]:
478 if Char
not in ' \t':
482 # Try to convert string to number
483 def __IsNumberToken(self
):
485 if self
._Token
.lower()[0:2] == '0x' and len(self
._Token
) > 2:
488 self
._Token
= int(self
._Token
, Radix
)
496 def __GetArray(self
):
499 self
.__GetNList
(True)
500 Token
+= self
._LiteralToken
501 if self
._Idx
>= self
._Len
or self
._Expr
[self
._Idx
] != '}':
502 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
505 # All whitespace and tabs in array are already stripped.
506 IsArray
= IsGuid
= False
507 if len(Token
.split(',')) == 11 and len(Token
.split(',{')) == 2 \
508 and len(Token
.split('},')) == 1:
509 HexLen
= [11, 6, 6, 5, 4, 4, 4, 4, 4, 4, 6]
510 HexList
= Token
.split(',')
511 if HexList
[3].startswith('{') and \
512 not [Index
for Index
, Hex
in enumerate(HexList
) if len(Hex
) > HexLen
[Index
]]:
514 if Token
.lstrip('{').rstrip('}').find('{') == -1:
515 if not [Hex
for Hex
in Token
.lstrip('{').rstrip('}').split(',') if len(Hex
) > 4]:
517 if not IsArray
and not IsGuid
:
518 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
520 self
._Token
= self
._LiteralToken
= Token
523 # Parse string, the format must be: "..."
524 def __GetString(self
):
530 # Replace escape \\\", \"
531 Expr
= self
._Expr
[self
._Idx
:].replace('\\\\', '//').replace('\\\"', '\\\'')
536 self
._Token
= self
._LiteralToken
= self
._Expr
[Idx
:self
._Idx
]
537 if not self
._Token
.endswith('"'):
538 raise BadExpression(ERR_STRING_TOKEN
% self
._Token
)
539 self
._Token
= self
._Token
[1:-1]
542 # Get token that is comprised by alphanumeric, underscore or dot(used by PCD)
543 # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...)
544 def __GetIdToken(self
, IsAlphaOp
= False):
546 for Ch
in self
._Expr
[self
._Idx
:]:
547 if not self
.__IsIdChar
(Ch
):
552 self
._Token
= self
._LiteralToken
= IdToken
554 self
.__ResolveToken
()
557 # Try to resolve token
558 def __ResolveToken(self
):
560 raise BadExpression(ERR_EMPTY_TOKEN
)
563 if PcdPattern
.match(self
._Token
):
564 if self
._Token
not in self
._Symb
:
565 Ex
= BadExpression(ERR_PCD_RESOLVE
% self
._Token
)
568 self
._Token
= RangeExpression(self
._Symb
[self
._Token
], self
._Symb
)(True, self
._Depth
+ 1)
569 if not isinstance(self
._Token
, type('')):
570 self
._LiteralToken
= hex(self
._Token
)
573 if self
._Token
.startswith('"'):
574 self
._Token
= self
._Token
[1:-1]
575 elif self
._Token
in ["FALSE", "false", "False"]:
577 elif self
._Token
in ["TRUE", "true", "True"]:
580 self
.__IsNumberToken
()
582 def __GetNList(self
, InArray
= False):
583 self
._GetSingleToken
()
584 if not self
.__IsHexLiteral
():
586 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
590 Expr
= self
._Expr
[self
._Idx
:]
591 if not Expr
.startswith(','):
594 NList
= self
._LiteralToken
595 while Expr
.startswith(','):
599 self
._GetSingleToken
()
600 if not self
.__IsHexLiteral
():
601 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
602 NList
+= self
._LiteralToken
604 Expr
= self
._Expr
[self
._Idx
:]
605 self
._Token
= self
._LiteralToken
= NList
608 def __IsHexLiteral(self
):
609 if self
._LiteralToken
.startswith('{') and \
610 self
._LiteralToken
.endswith('}'):
613 if gHexPattern
.match(self
._LiteralToken
):
614 Token
= self
._LiteralToken
[2:]
615 Token
= Token
.lstrip('0')
617 self
._LiteralToken
= '0x0'
619 self
._LiteralToken
= '0x' + Token
.lower()
624 return self
.__GetNList
()
628 return Ch
in '._/:' or Ch
.isalnum()
631 def _GetSingleToken(self
):
633 Expr
= self
._Expr
[self
._Idx
:]
634 if Expr
.startswith('L"'):
637 UStr
= self
.__GetString
()
638 self
._Token
= 'L"' + UStr
+ '"'
644 Match
= gGuidPattern
.match(Expr
)
645 if Match
and not Expr
[Match
.end():Match
.end() + 1].isalnum() \
646 and Expr
[Match
.end():Match
.end() + 1] != '_':
647 self
._Idx
+= Match
.end()
648 self
._Token
= Expr
[0:Match
.end()]
650 elif self
.__IsIdChar
(Ch
):
651 return self
.__GetIdToken
()
652 elif Ch
== '(' or Ch
== ')':
657 raise BadExpression(ERR_VALID_TOKEN
% Expr
)
660 def _GetOperator(self
):
662 LegalOpLst
= ['&&', '||', '!=', '==', '>=', '<='] + self
.NonLetterOpLst
665 Expr
= self
._Expr
[self
._Idx
:]
667 # Reach end of expression
671 # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not
672 if Expr
[0].isalpha():
673 return self
.__GetIdToken
(True)
675 # Start to get regular operator: +, -, <, > ...
676 if Expr
[0] not in self
.NonLetterOpLst
:
681 if Ch
in self
.NonLetterOpLst
:
682 if '!' == Ch
and OpToken
:
689 if OpToken
not in LegalOpLst
:
690 raise BadExpression(ERR_OPERATOR_UNSUPPORT
% OpToken
)
691 self
._Token
= OpToken