]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/Python/Common/RangeExpression.py
540f95728072b8b8666e56e0eff757ae11753104
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 Common
.GlobalData
import *
16 from CommonDataClass
.Exceptions
import BadExpression
17 from CommonDataClass
.Exceptions
import WrnExpression
20 ERR_STRING_EXPR
= 'This operator cannot be used in string expression: [%s].'
21 ERR_SNYTAX
= 'Syntax error, the rest of expression cannot be evaluated: [%s].'
22 ERR_MATCH
= 'No matching right parenthesis.'
23 ERR_STRING_TOKEN
= 'Bad string token: [%s].'
24 ERR_MACRO_TOKEN
= 'Bad macro token: [%s].'
25 ERR_EMPTY_TOKEN
= 'Empty token is not allowed.'
26 ERR_PCD_RESOLVE
= 'PCD token cannot be resolved: [%s].'
27 ERR_VALID_TOKEN
= 'No more valid token found from rest of string: [%s].'
28 ERR_EXPR_TYPE
= 'Different types found in expression.'
29 ERR_OPERATOR_UNSUPPORT
= 'Unsupported operator: [%s]'
30 ERR_REL_NOT_IN
= 'Expect "IN" after "not" operator.'
31 WRN_BOOL_EXPR
= 'Operand of boolean type cannot be used in arithmetic expression.'
32 WRN_EQCMP_STR_OTHERS
= '== Comparison between Operand of string type and Boolean/Number Type always return False.'
33 WRN_NECMP_STR_OTHERS
= '!= Comparison between Operand of string type and Boolean/Number Type always return True.'
34 ERR_RELCMP_STR_OTHERS
= 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].'
35 ERR_STRING_CMP
= 'Unicode string and general string cannot be compared: [%s %s %s]'
36 ERR_ARRAY_TOKEN
= 'Bad C array or C format GUID token: [%s].'
37 ERR_ARRAY_ELE
= 'This must be HEX value for NList or Array: [%s].'
38 ERR_EMPTY_EXPR
= 'Empty expression is not allowed.'
39 ERR_IN_OPERAND
= 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).'
41 def MaxOfType(DataType
):
42 if DataType
== 'UINT8':
43 return int('0xFF', 16)
44 if DataType
== 'UINT16':
45 return int('0xFFFF', 16)
46 if DataType
== 'UINT32':
47 return int('0xFFFFFFFF', 16)
48 if DataType
== 'UINT64':
49 return int('0xFFFFFFFFFFFFFFFF', 16)
51 class RangeObject(object):
52 def __init__(self
, start
, end
, empty
= False):
54 if int(start
) < int(end
):
55 self
.start
= int(start
)
62 class RangeContainer(object):
66 def push(self
, RangeObject
):
67 self
.rangelist
.append(RangeObject
)
68 self
.rangelist
= sorted(self
.rangelist
, key
= lambda rangeobj
: rangeobj
.start
)
72 for item
in self
.rangelist
:
77 for rangeobj
in self
.rangelist
:
78 if rangeobj
.empty
== True:
81 newrangelist
.append(rangeobj
)
82 self
.rangelist
= newrangelist
85 for i
in range(0, len(self
.rangelist
) - 1):
86 if self
.rangelist
[i
+ 1].start
> self
.rangelist
[i
].end
:
89 self
.rangelist
[i
+ 1].start
= self
.rangelist
[i
].start
90 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
91 self
.rangelist
[i
].empty
= True
96 print "----------------------"
98 for object in self
.rangelist
:
99 rangelist
= rangelist
+ "[%d , %d]" % (object.start
, object.end
)
103 class XOROperatorObject(object):
106 def Calculate(self
, Operand
, DataType
, SymbolTable
):
107 if type(Operand
) == type('') and not Operand
.isalnum():
109 raise BadExpression(ERR_SNYTAX
% Expr
)
110 rangeId
= str(uuid
.uuid1())
111 rangeContainer
= RangeContainer()
112 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
113 rangeContainer
.push(RangeObject(int(Operand
) + 1, MaxOfType(DataType
)))
114 SymbolTable
[rangeId
] = rangeContainer
117 class LEOperatorObject(object):
120 def Calculate(self
, Operand
, DataType
, SymbolTable
):
121 if type(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
)))
127 SymbolTable
[rangeId1
] = rangeContainer
129 class LTOperatorObject(object):
132 def Calculate(self
, Operand
, DataType
, SymbolTable
):
133 if type(Operand
) == type('') and not Operand
.isalnum():
135 raise BadExpression(ERR_SNYTAX
% Expr
)
136 rangeId1
= str(uuid
.uuid1())
137 rangeContainer
= RangeContainer()
138 rangeContainer
.push(RangeObject(0, int(Operand
) - 1))
139 SymbolTable
[rangeId1
] = rangeContainer
142 class GEOperatorObject(object):
145 def Calculate(self
, Operand
, DataType
, SymbolTable
):
146 if type(Operand
) == type('') and not Operand
.isalnum():
148 raise BadExpression(ERR_SNYTAX
% Expr
)
149 rangeId1
= str(uuid
.uuid1())
150 rangeContainer
= RangeContainer()
151 rangeContainer
.push(RangeObject(int(Operand
), MaxOfType(DataType
)))
152 SymbolTable
[rangeId1
] = rangeContainer
155 class GTOperatorObject(object):
158 def Calculate(self
, Operand
, DataType
, SymbolTable
):
159 if type(Operand
) == type('') and not Operand
.isalnum():
161 raise BadExpression(ERR_SNYTAX
% Expr
)
162 rangeId1
= str(uuid
.uuid1())
163 rangeContainer
= RangeContainer()
164 rangeContainer
.push(RangeObject(int(Operand
) + 1, MaxOfType(DataType
)))
165 SymbolTable
[rangeId1
] = rangeContainer
168 class EQOperatorObject(object):
171 def Calculate(self
, Operand
, DataType
, SymbolTable
):
172 if type(Operand
) == type('') and not Operand
.isalnum():
174 raise BadExpression(ERR_SNYTAX
% Expr
)
175 rangeId1
= str(uuid
.uuid1())
176 rangeContainer
= RangeContainer()
177 rangeContainer
.push(RangeObject(int(Operand
) , int(Operand
)))
178 SymbolTable
[rangeId1
] = rangeContainer
181 def GetOperatorObject(Operator
):
183 return GTOperatorObject()
184 elif Operator
== '>=':
185 return GEOperatorObject()
186 elif Operator
== '<':
187 return LTOperatorObject()
188 elif Operator
== '<=':
189 return LEOperatorObject()
190 elif Operator
== '==':
191 return EQOperatorObject()
192 elif Operator
== '^':
193 return XOROperatorObject()
195 raise BadExpression("Bad Operator")
197 class RangeExpression(object):
198 # Logical operator mapping
200 '&&' : 'and', '||' : 'or',
201 '!' : 'not', 'AND': 'and',
202 'OR' : 'or' , 'NOT': 'not',
203 'XOR': '^' , 'xor': '^',
204 'EQ' : '==' , 'NE' : '!=',
205 'GT' : '>' , 'LT' : '<',
206 'GE' : '>=' , 'LE' : '<=',
210 NonLetterOpLst
= ['+', '-', '&', '|', '^', '!', '=', '>', '<']
212 PcdPattern
= re
.compile(r
'[_a-zA-Z][0-9A-Za-z_]*\.[_a-zA-Z][0-9A-Za-z_]*$')
213 HexPattern
= re
.compile(r
'0[xX][0-9a-fA-F]+')
215 RangePattern
= re
.compile(r
'[0-9]+ - [0-9]+')
217 def preProcessRangeExpr(self
, expr
):
219 # convert interval to object index. ex. 1 - 10 to a GUID
222 for HexNumber
in self
.HexPattern
.findall(expr
):
223 Number
= str(int(HexNumber
, 16))
224 NumberDict
[HexNumber
] = Number
225 for HexNum
in NumberDict
:
226 expr
= expr
.replace(HexNum
, NumberDict
[HexNum
])
229 for validrange
in self
.RangePattern
.findall(expr
):
230 start
, end
= validrange
.split(" - ")
231 start
= start
.strip()
233 rangeid
= str(uuid
.uuid1())
234 rangeContainer
= RangeContainer()
235 rangeContainer
.push(RangeObject(start
, end
))
236 self
.operanddict
[str(rangeid
)] = rangeContainer
237 rangedict
[validrange
] = str(rangeid
)
239 for validrange
in rangedict
:
240 expr
= expr
.replace(validrange
, rangedict
[validrange
])
246 def EvalRange(self
, Operator
, Oprand
):
248 operatorobj
= GetOperatorObject(Operator
)
249 return operatorobj
.Calculate(Oprand
, self
.PcdDataType
, self
.operanddict
)
251 def Rangeintersection(self
, Oprand1
, Oprand2
):
252 rangeContainer1
= self
.operanddict
[Oprand1
]
253 rangeContainer2
= self
.operanddict
[Oprand2
]
254 rangeContainer
= RangeContainer()
255 for range1
in rangeContainer1
.pop():
256 for range2
in rangeContainer2
.pop():
257 start1
= range1
.start
259 start2
= range2
.start
262 start1
, start2
= start2
, start1
263 end1
, end2
= end2
, end1
265 rangeid
= str(uuid
.uuid1())
266 rangeContainer
.push(RangeObject(0, 0, True))
268 rangeid
= str(uuid
.uuid1())
269 rangeContainer
.push(RangeObject(0, 0, True))
271 rangeid
= str(uuid
.uuid1())
272 rangeContainer
.push(RangeObject(end1
, end1
))
273 elif end1
<= end2
and end1
> start2
:
274 rangeid
= str(uuid
.uuid1())
275 rangeContainer
.push(RangeObject(start2
, end1
))
277 rangeid
= str(uuid
.uuid1())
278 rangeContainer
.push(RangeObject(start2
, end2
))
280 self
.operanddict
[rangeid
] = rangeContainer
281 # rangeContainer.dump()
284 def Rangecollections(self
, Oprand1
, Oprand2
):
286 rangeContainer1
= self
.operanddict
[Oprand1
]
287 rangeContainer2
= self
.operanddict
[Oprand2
]
288 rangeContainer
= RangeContainer()
290 for rangeobj
in rangeContainer2
.pop():
291 rangeContainer
.push(rangeobj
)
292 for rangeobj
in rangeContainer1
.pop():
293 rangeContainer
.push(rangeobj
)
295 rangeid
= str(uuid
.uuid1())
296 self
.operanddict
[rangeid
] = rangeContainer
298 # rangeContainer.dump()
302 def NegtiveRange(self
, Oprand1
):
303 rangeContainer1
= self
.operanddict
[Oprand1
]
308 for rangeobj
in rangeContainer1
.pop():
309 rangeContainer
= RangeContainer()
310 rangeid
= str(uuid
.uuid1())
312 rangeContainer
.push(RangeObject(0, MaxOfType(self
.PcdDataType
)))
314 if rangeobj
.start
> 0:
315 rangeContainer
.push(RangeObject(0, rangeobj
.start
- 1))
316 if rangeobj
.end
< MaxOfType(self
.PcdDataType
):
317 rangeContainer
.push(RangeObject(rangeobj
.end
+ 1, MaxOfType(self
.PcdDataType
)))
318 self
.operanddict
[rangeid
] = rangeContainer
319 rangeids
.append(rangeid
)
321 if len(rangeids
) == 0:
322 rangeContainer
= RangeContainer()
323 rangeContainer
.push(RangeObject(0, MaxOfType(self
.PcdDataType
)))
324 rangeid
= str(uuid
.uuid1())
325 self
.operanddict
[rangeid
] = rangeContainer
328 if len(rangeids
) == 1:
331 re
= self
.Rangeintersection(rangeids
[0], rangeids
[1])
332 for i
in range(2, len(rangeids
)):
333 re
= self
.Rangeintersection(re
, rangeids
[i
])
335 rangeid2
= str(uuid
.uuid1())
336 self
.operanddict
[rangeid2
] = self
.operanddict
[re
]
339 def Eval(self
, Operator
, Oprand1
, Oprand2
= None):
341 if Operator
in ["!", "NOT", "not"]:
342 if not gGuidPattern
.match(Oprand1
.strip()):
343 raise BadExpression(ERR_STRING_EXPR
% Operator
)
344 return self
.NegtiveRange(Oprand1
)
346 if Operator
in ["==", ">=", "<=", ">", "<", '^']:
347 return self
.EvalRange(Operator
, Oprand1
)
348 elif Operator
== 'and' :
349 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
350 raise BadExpression(ERR_STRING_EXPR
% Operator
)
351 return self
.Rangeintersection(Oprand1
, Oprand2
)
352 elif Operator
== 'or':
353 if not gGuidPatternEnd
.match(Oprand1
.strip()) or not gGuidPatternEnd
.match(Oprand2
.strip()):
354 raise BadExpression(ERR_STRING_EXPR
% Operator
)
355 return self
.Rangecollections(Oprand1
, Oprand2
)
357 raise BadExpression(ERR_STRING_EXPR
% Operator
)
360 def __init__(self
, Expression
, PcdDataType
, SymbolTable
= {}):
361 self
._NoProcess
= False
362 if type(Expression
) != type(''):
363 self
._Expr
= Expression
364 self
._NoProcess
= True
367 self
._Expr
= Expression
.strip()
369 if not self
._Expr
.strip():
370 raise BadExpression(ERR_EMPTY_EXPR
)
373 # The symbol table including PCD and macro mapping
375 self
._Symb
= SymbolTable
376 self
._Symb
.update(self
.LogicalOperators
)
378 self
._Len
= len(self
._Expr
)
380 self
._WarnExcept
= None
383 # Literal token without any conversion
384 self
._LiteralToken
= ''
386 # store the operand object
387 self
.operanddict
= {}
388 # The Pcd max value depends on PcdDataType
389 self
.PcdDataType
= PcdDataType
391 # Public entry for this class
392 # @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression
393 # True : return the evaluated str(value), used for PCD value
395 # @return: True or False if RealValue is False
396 # Evaluated value of string format if RealValue is True
398 def __call__(self
, RealValue
= False, Depth
= 0):
404 self
._Expr
= self
._Expr
.strip()
406 self
.preProcessRangeExpr(self
._Expr
)
408 # check if the expression does not need to evaluate
409 if RealValue
and Depth
== 0:
410 self
._Token
= self
._Expr
411 if gGuidPatternEnd
.match(self
._Expr
):
412 return [self
.operanddict
[self
._Expr
] ]
420 RangeIdList
= RealVal
.split("or")
422 for rangeid
in RangeIdList
:
423 RangeList
.append(self
.operanddict
[rangeid
.strip()])
427 # Template function to parse binary operators which have same precedence
428 # Expr [Operator Expr]*
429 def _ExprFuncTemplate(self
, EvalFunc
, OpLst
):
431 while self
._IsOperator
(OpLst
):
434 Val
= self
.Eval(Op
, Val
, EvalFunc())
435 except WrnExpression
, Warn
:
436 self
._WarnExcept
= Warn
442 return self
._ExprFuncTemplate
(self
._AndExpr
, ["OR", "or"])
446 return self
._ExprFuncTemplate
(self
._NeExpr
, ["AND", "and"])
449 Val
= self
._RelExpr
()
450 while self
._IsOperator
([ "!=", "NOT", "not"]):
452 if Op
in ["!", "NOT", "not"]:
453 if not self
._IsOperator
(["IN", "in"]):
454 raise BadExpression(ERR_REL_NOT_IN
)
455 Op
+= ' ' + self
._Token
457 Val
= self
.Eval(Op
, Val
, self
._RelExpr
())
458 except WrnExpression
, Warn
:
459 self
._WarnExcept
= Warn
465 if self
._IsOperator
(["NOT" , "LE", "GE", "LT", "GT", "EQ", "XOR"]):
469 return self
.Eval(Token
, Val
)
470 except WrnExpression
, Warn
:
471 self
._WarnExcept
= Warn
473 return self
._IdenExpr
()
475 # Parse identifier or encapsulated expression
477 Tk
= self
._GetToken
()
481 # _GetToken may also raise BadExpression
482 if self
._GetToken
() != ')':
483 raise BadExpression(ERR_MATCH
)
484 except BadExpression
:
485 raise BadExpression(ERR_MATCH
)
489 # Skip whitespace or tab
491 for Char
in self
._Expr
[self
._Idx
:]:
492 if Char
not in ' \t':
496 # Try to convert string to number
497 def __IsNumberToken(self
):
499 if self
._Token
.lower()[0:2] == '0x' and len(self
._Token
) > 2:
502 self
._Token
= int(self
._Token
, Radix
)
510 def __GetArray(self
):
513 self
.__GetNList
(True)
514 Token
+= self
._LiteralToken
515 if self
._Idx
>= self
._Len
or self
._Expr
[self
._Idx
] != '}':
516 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
519 # All whitespace and tabs in array are already stripped.
520 IsArray
= IsGuid
= False
521 if len(Token
.split(',')) == 11 and len(Token
.split(',{')) == 2 \
522 and len(Token
.split('},')) == 1:
523 HexLen
= [11, 6, 6, 5, 4, 4, 4, 4, 4, 4, 6]
524 HexList
= Token
.split(',')
525 if HexList
[3].startswith('{') and \
526 not [Index
for Index
, Hex
in enumerate(HexList
) if len(Hex
) > HexLen
[Index
]]:
528 if Token
.lstrip('{').rstrip('}').find('{') == -1:
529 if not [Hex
for Hex
in Token
.lstrip('{').rstrip('}').split(',') if len(Hex
) > 4]:
531 if not IsArray
and not IsGuid
:
532 raise BadExpression(ERR_ARRAY_TOKEN
% Token
)
534 self
._Token
= self
._LiteralToken
= Token
537 # Parse string, the format must be: "..."
538 def __GetString(self
):
544 # Replace escape \\\", \"
545 Expr
= self
._Expr
[self
._Idx
:].replace('\\\\', '//').replace('\\\"', '\\\'')
550 self
._Token
= self
._LiteralToken
= self
._Expr
[Idx
:self
._Idx
]
551 if not self
._Token
.endswith('"'):
552 raise BadExpression(ERR_STRING_TOKEN
% self
._Token
)
553 self
._Token
= self
._Token
[1:-1]
556 # Get token that is comprised by alphanumeric, underscore or dot(used by PCD)
557 # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...)
558 def __GetIdToken(self
, IsAlphaOp
= False):
560 for Ch
in self
._Expr
[self
._Idx
:]:
561 if not self
.__IsIdChar
(Ch
):
566 self
._Token
= self
._LiteralToken
= IdToken
568 self
.__ResolveToken
()
571 # Try to resolve token
572 def __ResolveToken(self
):
574 raise BadExpression(ERR_EMPTY_TOKEN
)
577 if self
.PcdPattern
.match(self
._Token
):
578 if self
._Token
not in self
._Symb
:
579 Ex
= BadExpression(ERR_PCD_RESOLVE
% self
._Token
)
582 self
._Token
= RangeExpression(self
._Symb
[self
._Token
], self
._Symb
)(True, self
._Depth
+ 1)
583 if type(self
._Token
) != type(''):
584 self
._LiteralToken
= hex(self
._Token
)
587 if self
._Token
.startswith('"'):
588 self
._Token
= self
._Token
[1:-1]
589 elif self
._Token
in ["FALSE", "false", "False"]:
591 elif self
._Token
in ["TRUE", "true", "True"]:
594 self
.__IsNumberToken
()
596 def __GetNList(self
, InArray
= False):
597 self
._GetSingleToken
()
598 if not self
.__IsHexLiteral
():
600 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
604 Expr
= self
._Expr
[self
._Idx
:]
605 if not Expr
.startswith(','):
608 NList
= self
._LiteralToken
609 while Expr
.startswith(','):
613 self
._GetSingleToken
()
614 if not self
.__IsHexLiteral
():
615 raise BadExpression(ERR_ARRAY_ELE
% self
._Token
)
616 NList
+= self
._LiteralToken
618 Expr
= self
._Expr
[self
._Idx
:]
619 self
._Token
= self
._LiteralToken
= NList
622 def __IsHexLiteral(self
):
623 if self
._LiteralToken
.startswith('{') and \
624 self
._LiteralToken
.endswith('}'):
627 if self
.HexPattern
.match(self
._LiteralToken
):
628 Token
= self
._LiteralToken
[2:]
629 Token
= Token
.lstrip('0')
631 self
._LiteralToken
= '0x0'
633 self
._LiteralToken
= '0x' + Token
.lower()
638 return self
.__GetNList
()
642 return Ch
in '._/:' or Ch
.isalnum()
645 def _GetSingleToken(self
):
647 Expr
= self
._Expr
[self
._Idx
:]
648 if Expr
.startswith('L"'):
651 UStr
= self
.__GetString
()
652 self
._Token
= 'L"' + UStr
+ '"'
658 Match
= gGuidPattern
.match(Expr
)
659 if Match
and not Expr
[Match
.end():Match
.end() + 1].isalnum() \
660 and Expr
[Match
.end():Match
.end() + 1] != '_':
661 self
._Idx
+= Match
.end()
662 self
._Token
= Expr
[0:Match
.end()]
664 elif self
.__IsIdChar
(Ch
):
665 return self
.__GetIdToken
()
666 elif Ch
== '(' or Ch
== ')':
671 raise BadExpression(ERR_VALID_TOKEN
% Expr
)
674 def _GetOperator(self
):
676 LegalOpLst
= ['&&', '||', '!=', '==', '>=', '<='] + self
.NonLetterOpLst
679 Expr
= self
._Expr
[self
._Idx
:]
681 # Reach end of expression
685 # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not
686 if Expr
[0].isalpha():
687 return self
.__GetIdToken
(True)
689 # Start to get regular operator: +, -, <, > ...
690 if Expr
[0] not in self
.NonLetterOpLst
:
695 if Ch
in self
.NonLetterOpLst
:
696 if '!' == Ch
and OpToken
:
703 if OpToken
not in LegalOpLst
:
704 raise BadExpression(ERR_OPERATOR_UNSUPPORT
% OpToken
)
705 self
._Token
= OpToken
708 # Check if current token matches the operators given from OpList
709 def _IsOperator(self
, OpList
):
712 if self
._Token
in OpList
:
713 if self
._Token
in self
.LogicalOperators
:
714 self
._Token
= self
.LogicalOperators
[self
._Token
]