[mirror_edk2.git] / BaseTools / Source / Python / Common / RangeExpression.py

# # @file\r
# This file is used to parse and evaluate range expression in Pcd declaration.\r
#\r
# Copyright (c) 2015 - 2018, Intel Corporation. All rights reserved.<BR>\r
# This program and the accompanying materials\r
# are licensed and made available under the terms and conditions of the BSD License\r
# which accompanies this distribution.    The full text of the license may be found at\r
# http://opensource.org/licenses/bsd-license.php\r
#\r
# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
\r
# # Import Modules\r
#\r
from Common.GlobalData import *\r
from CommonDataClass.Exceptions import BadExpression\r
from CommonDataClass.Exceptions import WrnExpression\r
import uuid\r
from Common.Expression import PcdPattern\r
\r
ERR_STRING_EXPR = 'This operator cannot be used in string expression: [%s].'\r
ERR_SNYTAX = 'Syntax error, the rest of expression cannot be evaluated: [%s].'\r
ERR_MATCH = 'No matching right parenthesis.'\r
ERR_STRING_TOKEN = 'Bad string token: [%s].'\r
ERR_MACRO_TOKEN = 'Bad macro token: [%s].'\r
ERR_EMPTY_TOKEN = 'Empty token is not allowed.'\r
ERR_PCD_RESOLVE = 'PCD token cannot be resolved: [%s].'\r
ERR_VALID_TOKEN = 'No more valid token found from rest of string: [%s].'\r
ERR_EXPR_TYPE = 'Different types found in expression.'\r
ERR_OPERATOR_UNSUPPORT = 'Unsupported operator: [%s]'\r
ERR_REL_NOT_IN = 'Expect "IN" after "not" operator.'\r
WRN_BOOL_EXPR = 'Operand of boolean type cannot be used in arithmetic expression.'\r
WRN_EQCMP_STR_OTHERS = '== Comparison between Operand of string type and Boolean/Number Type always return False.'\r
WRN_NECMP_STR_OTHERS = '!= Comparison between Operand of string type and Boolean/Number Type always return True.'\r
ERR_RELCMP_STR_OTHERS = 'Operator taking Operand of string type and Boolean/Number Type is not allowed: [%s].'\r
ERR_STRING_CMP = 'Unicode string and general string cannot be compared: [%s %s %s]'\r
ERR_ARRAY_TOKEN = 'Bad C array or C format GUID token: [%s].'\r
ERR_ARRAY_ELE = 'This must be HEX value for NList or Array: [%s].'\r
ERR_EMPTY_EXPR = 'Empty expression is not allowed.'\r
ERR_IN_OPERAND = 'Macro after IN operator can only be: $(FAMILY), $(ARCH), $(TOOL_CHAIN_TAG) and $(TARGET).'\r
\r
def MaxOfType(DataType):\r
    if DataType == 'UINT8':\r
        return int('0xFF', 16)\r
    if DataType == 'UINT16':\r
        return int('0xFFFF', 16)\r
    if DataType == 'UINT32':\r
        return int('0xFFFFFFFF', 16)\r
    if DataType == 'UINT64':\r
        return int('0xFFFFFFFFFFFFFFFF', 16)\r
\r
class RangeObject(object):\r
    def __init__(self, start, end, empty = False):\r
        \r
        if int(start) < int(end):\r
            self.start = int(start)\r
            self.end = int(end)\r
        else:\r
            self.start = int(end)\r
            self.end = int(start)\r
        self.empty = empty\r
\r
class RangeContainer(object):\r
    def __init__(self):\r
        self.rangelist = []\r
        \r
    def push(self, RangeObject):\r
        self.rangelist.append(RangeObject)\r
        self.rangelist = sorted(self.rangelist, key = lambda rangeobj : rangeobj.start)\r
        self.merge()\r
        \r
    def pop(self):\r
        for item in self.rangelist:\r
            yield item\r
   \r
    def __clean__(self):   \r
        newrangelist = []\r
        for rangeobj in self.rangelist:\r
            if rangeobj.empty == True:\r
                continue\r
            else:\r
                newrangelist.append(rangeobj)\r
        self.rangelist = newrangelist      \r
    def merge(self):\r
        self.__clean__()\r
        for i in range(0, len(self.rangelist) - 1):\r
            if self.rangelist[i + 1].start > self.rangelist[i].end:\r
                continue\r
            else:\r
                self.rangelist[i + 1].start = self.rangelist[i].start\r
                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 \r
                self.rangelist[i].empty = True\r
\r
        self.__clean__()\r
        \r
    def dump(self):\r
        print "----------------------"\r
        rangelist = ""\r
        for object in self.rangelist:\r
            rangelist = rangelist + "[%d , %d]" % (object.start, object.end)\r
        print rangelist\r
        \r
        \r
class XOROperatorObject(object):   \r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable): \r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "XOR ..."\r
            raise BadExpression(ERR_SNYTAX % Expr)\r
        rangeId = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(0, int(Operand) - 1))\r
        rangeContainer.push(RangeObject(int(Operand) + 1, MaxOfType(DataType)))\r
        SymbolTable[rangeId] = rangeContainer\r
        return rangeId\r
\r
class LEOperatorObject(object):\r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable): \r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "LE ..."\r
            raise BadExpression(ERR_SNYTAX % Expr)\r
        rangeId1 = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(0, int(Operand)))\r
        SymbolTable[rangeId1] = rangeContainer\r
        return rangeId1\r
class LTOperatorObject(object):\r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable):\r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "LT ..." \r
            raise BadExpression(ERR_SNYTAX % Expr) \r
        rangeId1 = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(0, int(Operand) - 1))\r
        SymbolTable[rangeId1] = rangeContainer\r
        return rangeId1   \r
\r
class GEOperatorObject(object):\r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable): \r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "GE ..."\r
            raise BadExpression(ERR_SNYTAX % Expr)\r
        rangeId1 = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(int(Operand), MaxOfType(DataType)))\r
        SymbolTable[rangeId1] = rangeContainer\r
        return rangeId1   \r
      \r
class GTOperatorObject(object):\r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable): \r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "GT ..."\r
            raise BadExpression(ERR_SNYTAX % Expr)\r
        rangeId1 = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(int(Operand) + 1, MaxOfType(DataType)))\r
        SymbolTable[rangeId1] = rangeContainer\r
        return rangeId1   \r
    \r
class EQOperatorObject(object):\r
    def __init__(self):     \r
        pass\r
    def Calculate(self, Operand, DataType, SymbolTable): \r
        if type(Operand) == type('') and not Operand.isalnum():\r
            Expr = "EQ ..."\r
            raise BadExpression(ERR_SNYTAX % Expr)\r
        rangeId1 = str(uuid.uuid1())\r
        rangeContainer = RangeContainer()\r
        rangeContainer.push(RangeObject(int(Operand) , int(Operand)))\r
        SymbolTable[rangeId1] = rangeContainer\r
        return rangeId1   \r
    \r
def GetOperatorObject(Operator):\r
    if Operator == '>':\r
        return GTOperatorObject()\r
    elif Operator == '>=':\r
        return GEOperatorObject()\r
    elif Operator == '<':\r
        return LTOperatorObject()\r
    elif Operator == '<=':\r
        return LEOperatorObject()\r
    elif Operator == '==':\r
        return EQOperatorObject()\r
    elif Operator == '^':\r
        return XOROperatorObject()\r
    else:\r
        raise BadExpression("Bad Operator")\r
\r
class RangeExpression(object):\r
    # Logical operator mapping\r
    LogicalOperators = {\r
        '&&' : 'and', '||' : 'or',\r
        '!'  : 'not', 'AND': 'and',\r
        'OR' : 'or' , 'NOT': 'not',\r
        'XOR': '^'  , 'xor': '^',\r
        'EQ' : '==' , 'NE' : '!=',\r
        'GT' : '>'  , 'LT' : '<',\r
        'GE' : '>=' , 'LE' : '<=',\r
        'IN' : 'in'\r
    }\r
\r
    NonLetterOpLst = ['+', '-', '&', '|', '^', '!', '=', '>', '<']\r
\r
    RangePattern = re.compile(r'[0-9]+ - [0-9]+')\r
\r
    def preProcessRangeExpr(self, expr):\r
        # convert hex to int\r
        # convert interval to object index. ex. 1 - 10 to a GUID\r
        expr = expr.strip()\r
        NumberDict = {}\r
        for HexNumber in gHexPattern.findall(expr):\r
            Number = str(int(HexNumber, 16))\r
            NumberDict[HexNumber] = Number\r
        for HexNum in NumberDict:\r
            expr = expr.replace(HexNum, NumberDict[HexNum])\r
        \r
        rangedict = {}    \r
        for validrange in self.RangePattern.findall(expr):\r
            start, end = validrange.split(" - ")\r
            start = start.strip()\r
            end = end.strip()\r
            rangeid = str(uuid.uuid1())\r
            rangeContainer = RangeContainer()\r
            rangeContainer.push(RangeObject(start, end))\r
            self.operanddict[str(rangeid)] = rangeContainer\r
            rangedict[validrange] = str(rangeid)\r
            \r
        for validrange in rangedict:\r
            expr = expr.replace(validrange, rangedict[validrange])\r
         \r
        self._Expr = expr    \r
        return expr\r
            \r
        \r
    def EvalRange(self, Operator, Oprand):\r
\r
        operatorobj = GetOperatorObject(Operator)\r
        return operatorobj.Calculate(Oprand, self.PcdDataType, self.operanddict)\r
        \r
    def Rangeintersection(self, Oprand1, Oprand2):\r
        rangeContainer1 = self.operanddict[Oprand1]\r
        rangeContainer2 = self.operanddict[Oprand2]\r
        rangeContainer = RangeContainer()\r
        for range1 in rangeContainer1.pop():\r
            for range2 in rangeContainer2.pop():\r
                start1 = range1.start\r
                end1 = range1.end\r
                start2 = range2.start\r
                end2 = range2.end\r
                if start1 >= start2:\r
                    start1, start2 = start2, start1\r
                    end1, end2 = end2, end1\r
                if range1.empty:\r
                    rangeid = str(uuid.uuid1())\r
                    rangeContainer.push(RangeObject(0, 0, True))\r
                if end1 < start2:\r
                    rangeid = str(uuid.uuid1())\r
                    rangeContainer.push(RangeObject(0, 0, True))\r
                elif end1 == start2:\r
                    rangeid = str(uuid.uuid1())\r
                    rangeContainer.push(RangeObject(end1, end1))\r
                elif end1 <= end2 and end1 > start2:\r
                    rangeid = str(uuid.uuid1())\r
                    rangeContainer.push(RangeObject(start2, end1))\r
                elif end1 >= end2:\r
                    rangeid = str(uuid.uuid1())\r
                    rangeContainer.push(RangeObject(start2, end2))\r
        \r
        self.operanddict[rangeid] = rangeContainer\r
#        rangeContainer.dump()\r
        return rangeid\r
            \r
    def Rangecollections(self, Oprand1, Oprand2):\r
\r
        rangeContainer1 = self.operanddict[Oprand1]\r
        rangeContainer2 = self.operanddict[Oprand2]\r
        rangeContainer = RangeContainer()\r
        \r
        for rangeobj in rangeContainer2.pop():\r
            rangeContainer.push(rangeobj)\r
        for rangeobj in rangeContainer1.pop():\r
            rangeContainer.push(rangeobj)\r
        \r
        rangeid = str(uuid.uuid1())\r
        self.operanddict[rangeid] = rangeContainer\r
        \r
#        rangeContainer.dump()\r
        return rangeid\r
        \r
            \r
    def NegtiveRange(self, Oprand1):\r
        rangeContainer1 = self.operanddict[Oprand1]\r
        \r
        \r
        rangeids = []\r
        \r
        for rangeobj in rangeContainer1.pop():\r
            rangeContainer = RangeContainer()\r
            rangeid = str(uuid.uuid1())\r
            if rangeobj.empty:\r
                rangeContainer.push(RangeObject(0, MaxOfType(self.PcdDataType)))\r
            else:\r
                if rangeobj.start > 0:\r
                    rangeContainer.push(RangeObject(0, rangeobj.start - 1))\r
                if rangeobj.end < MaxOfType(self.PcdDataType):\r
                    rangeContainer.push(RangeObject(rangeobj.end + 1, MaxOfType(self.PcdDataType)))\r
            self.operanddict[rangeid] = rangeContainer\r
            rangeids.append(rangeid)\r
\r
        if len(rangeids) == 0:\r
            rangeContainer = RangeContainer()\r
            rangeContainer.push(RangeObject(0, MaxOfType(self.PcdDataType)))\r
            rangeid = str(uuid.uuid1())\r
            self.operanddict[rangeid] = rangeContainer\r
            return rangeid\r
\r
        if len(rangeids) == 1:\r
            return rangeids[0]\r
\r
        re = self.Rangeintersection(rangeids[0], rangeids[1])\r
        for i in range(2, len(rangeids)):\r
            re = self.Rangeintersection(re, rangeids[i])\r
            \r
        rangeid2 = str(uuid.uuid1())\r
        self.operanddict[rangeid2] = self.operanddict[re]\r
        return rangeid2\r
        \r
    def Eval(self, Operator, Oprand1, Oprand2 = None):\r
        \r
        if Operator in ["!", "NOT", "not"]:\r
            if not gGuidPattern.match(Oprand1.strip()):\r
                raise BadExpression(ERR_STRING_EXPR % Operator)\r
            return self.NegtiveRange(Oprand1)\r
        else:\r
            if Operator in ["==", ">=", "<=", ">", "<", '^']:\r
                return self.EvalRange(Operator, Oprand1)\r
            elif Operator == 'and' :\r
                if not gGuidPatternEnd.match(Oprand1.strip()) or not gGuidPatternEnd.match(Oprand2.strip()):\r
                    raise BadExpression(ERR_STRING_EXPR % Operator)\r
                return self.Rangeintersection(Oprand1, Oprand2)    \r
            elif Operator == 'or':\r
                if not gGuidPatternEnd.match(Oprand1.strip()) or not gGuidPatternEnd.match(Oprand2.strip()):\r
                    raise BadExpression(ERR_STRING_EXPR % Operator)\r
                return self.Rangecollections(Oprand1, Oprand2)\r
            else:\r
                raise BadExpression(ERR_STRING_EXPR % Operator)\r
\r
\r
    def __init__(self, Expression, PcdDataType, SymbolTable = {}):\r
        self._NoProcess = False\r
        if type(Expression) != type(''):\r
            self._Expr = Expression\r
            self._NoProcess = True\r
            return\r
\r
        self._Expr = Expression.strip()\r
\r
        if not self._Expr.strip():\r
            raise BadExpression(ERR_EMPTY_EXPR)\r
\r
        #\r
        # The symbol table including PCD and macro mapping\r
        #\r
        self._Symb = SymbolTable\r
        self._Symb.update(self.LogicalOperators)\r
        self._Idx = 0\r
        self._Len = len(self._Expr)\r
        self._Token = ''\r
        self._WarnExcept = None\r
        \r
\r
        # Literal token without any conversion\r
        self._LiteralToken = ''\r
        \r
        # store the operand object\r
        self.operanddict = {}\r
        # The Pcd max value depends on PcdDataType\r
        self.PcdDataType = PcdDataType\r
\r
    # Public entry for this class\r
    #   @param RealValue: False: only evaluate if the expression is true or false, used for conditional expression\r
    #                     True : return the evaluated str(value), used for PCD value\r
    #\r
    #   @return: True or False if RealValue is False\r
    #            Evaluated value of string format if RealValue is True\r
    #\r
    def __call__(self, RealValue = False, Depth = 0):\r
        if self._NoProcess:\r
            return self._Expr\r
\r
        self._Depth = Depth\r
\r
        self._Expr = self._Expr.strip()\r
        \r
        self.preProcessRangeExpr(self._Expr)\r
        \r
        # check if the expression does not need to evaluate\r
        if RealValue and Depth == 0:\r
            self._Token = self._Expr\r
            if gGuidPatternEnd.match(self._Expr):\r
                return [self.operanddict[self._Expr] ]\r
\r
            self._Idx = 0\r
            self._Token = ''\r
\r
        Val = self._OrExpr()\r
        RealVal = Val\r
        \r
        RangeIdList = RealVal.split("or")\r
        RangeList = []\r
        for rangeid in RangeIdList:\r
            RangeList.append(self.operanddict[rangeid.strip()])\r
            \r
        return RangeList\r
\r
    # Template function to parse binary operators which have same precedence\r
    # Expr [Operator Expr]*\r
    def _ExprFuncTemplate(self, EvalFunc, OpLst):\r
        Val = EvalFunc()\r
        while self._IsOperator(OpLst):\r
            Op = self._Token\r
            try:\r
                Val = self.Eval(Op, Val, EvalFunc())\r
            except WrnExpression, Warn:\r
                self._WarnExcept = Warn\r
                Val = Warn.result\r
        return Val\r
\r
    # A [|| B]*\r
    def _OrExpr(self):\r
        return self._ExprFuncTemplate(self._AndExpr, ["OR", "or"])\r
\r
    # A [&& B]*\r
    def _AndExpr(self):\r
        return self._ExprFuncTemplate(self._NeExpr, ["AND", "and"])\r
\r
    def _NeExpr(self):\r
        Val = self._RelExpr()\r
        while self._IsOperator([ "!=", "NOT", "not"]):\r
            Op = self._Token\r
            if Op in ["!", "NOT", "not"]:\r
                if not self._IsOperator(["IN", "in"]):\r
                    raise BadExpression(ERR_REL_NOT_IN)\r
                Op += ' ' + self._Token\r
            try:\r
                Val = self.Eval(Op, Val, self._RelExpr())\r
            except WrnExpression, Warn:\r
                self._WarnExcept = Warn\r
                Val = Warn.result\r
        return Val\r
\r
    # [!]*A\r
    def _RelExpr(self):\r
        if self._IsOperator(["NOT" , "LE", "GE", "LT", "GT", "EQ", "XOR"]):\r
            Token = self._Token\r
            Val = self._NeExpr()\r
            try:\r
                return self.Eval(Token, Val)\r
            except WrnExpression, Warn:\r
                self._WarnExcept = Warn\r
                return Warn.result\r
        return self._IdenExpr()\r
\r
    # Parse identifier or encapsulated expression\r
    def _IdenExpr(self):\r
        Tk = self._GetToken()\r
        if Tk == '(':\r
            Val = self._OrExpr()\r
            try:\r
                # _GetToken may also raise BadExpression\r
                if self._GetToken() != ')':\r
                    raise BadExpression(ERR_MATCH)\r
            except BadExpression:\r
                raise BadExpression(ERR_MATCH)\r
            return Val\r
        return Tk\r
\r
    # Skip whitespace or tab\r
    def __SkipWS(self):\r
        for Char in self._Expr[self._Idx:]:\r
            if Char not in ' \t':\r
                break\r
            self._Idx += 1\r
\r
    # Try to convert string to number\r
    def __IsNumberToken(self):\r
        Radix = 10\r
        if self._Token.lower()[0:2] == '0x' and len(self._Token) > 2:\r
            Radix = 16\r
        try:\r
            self._Token = int(self._Token, Radix)\r
            return True\r
        except ValueError:\r
            return False\r
        except TypeError:\r
            return False\r
\r
    # Parse array: {...}\r
    def __GetArray(self):\r
        Token = '{'\r
        self._Idx += 1\r
        self.__GetNList(True)\r
        Token += self._LiteralToken\r
        if self._Idx >= self._Len or self._Expr[self._Idx] != '}':\r
            raise BadExpression(ERR_ARRAY_TOKEN % Token)\r
        Token += '}'\r
\r
        # All whitespace and tabs in array are already stripped.\r
        IsArray = IsGuid = False\r
        if len(Token.split(',')) == 11 and len(Token.split(',{')) == 2 \\r
            and len(Token.split('},')) == 1:\r
            HexLen = [11, 6, 6, 5, 4, 4, 4, 4, 4, 4, 6]\r
            HexList = Token.split(',')\r
            if HexList[3].startswith('{') and \\r
                not [Index for Index, Hex in enumerate(HexList) if len(Hex) > HexLen[Index]]:\r
                IsGuid = True\r
        if Token.lstrip('{').rstrip('}').find('{') == -1:\r
            if not [Hex for Hex in Token.lstrip('{').rstrip('}').split(',') if len(Hex) > 4]:\r
                IsArray = True\r
        if not IsArray and not IsGuid:\r
            raise BadExpression(ERR_ARRAY_TOKEN % Token)\r
        self._Idx += 1\r
        self._Token = self._LiteralToken = Token\r
        return self._Token\r
\r
    # Parse string, the format must be: "..."\r
    def __GetString(self):\r
        Idx = self._Idx\r
\r
        # Skip left quote\r
        self._Idx += 1\r
\r
        # Replace escape \\\", \"\r
        Expr = self._Expr[self._Idx:].replace('\\\\', '//').replace('\\\"', '\\\'')\r
        for Ch in Expr:\r
            self._Idx += 1\r
            if Ch == '"':\r
                break\r
        self._Token = self._LiteralToken = self._Expr[Idx:self._Idx]\r
        if not self._Token.endswith('"'):\r
            raise BadExpression(ERR_STRING_TOKEN % self._Token)\r
        self._Token = self._Token[1:-1]\r
        return self._Token\r
\r
    # Get token that is comprised by alphanumeric, underscore or dot(used by PCD)\r
    # @param IsAlphaOp: Indicate if parsing general token or script operator(EQ, NE...)\r
    def __GetIdToken(self, IsAlphaOp = False):\r
        IdToken = ''\r
        for Ch in self._Expr[self._Idx:]:\r
            if not self.__IsIdChar(Ch):\r
                break\r
            self._Idx += 1\r
            IdToken += Ch\r
\r
        self._Token = self._LiteralToken = IdToken\r
        if not IsAlphaOp:\r
            self.__ResolveToken()\r
        return self._Token\r
\r
    # Try to resolve token\r
    def __ResolveToken(self):\r
        if not self._Token:\r
            raise BadExpression(ERR_EMPTY_TOKEN)\r
\r
        # PCD token\r
        if PcdPattern.match(self._Token):\r
            if self._Token not in self._Symb:\r
                Ex = BadExpression(ERR_PCD_RESOLVE % self._Token)\r
                Ex.Pcd = self._Token\r
                raise Ex\r
            self._Token = RangeExpression(self._Symb[self._Token], self._Symb)(True, self._Depth + 1)\r
            if type(self._Token) != type(''):\r
                self._LiteralToken = hex(self._Token)\r
                return\r
\r
        if self._Token.startswith('"'):\r
            self._Token = self._Token[1:-1]\r
        elif self._Token in ["FALSE", "false", "False"]:\r
            self._Token = False\r
        elif self._Token in ["TRUE", "true", "True"]:\r
            self._Token = True\r
        else:\r
            self.__IsNumberToken()\r
\r
    def __GetNList(self, InArray = False):\r
        self._GetSingleToken()\r
        if not self.__IsHexLiteral():\r
            if InArray:\r
                raise BadExpression(ERR_ARRAY_ELE % self._Token)\r
            return self._Token\r
\r
        self.__SkipWS()\r
        Expr = self._Expr[self._Idx:]\r
        if not Expr.startswith(','):\r
            return self._Token\r
\r
        NList = self._LiteralToken\r
        while Expr.startswith(','):\r
            NList += ','\r
            self._Idx += 1\r
            self.__SkipWS()\r
            self._GetSingleToken()\r
            if not self.__IsHexLiteral():\r
                raise BadExpression(ERR_ARRAY_ELE % self._Token)\r
            NList += self._LiteralToken\r
            self.__SkipWS()\r
            Expr = self._Expr[self._Idx:]\r
        self._Token = self._LiteralToken = NList\r
        return self._Token\r
\r
    def __IsHexLiteral(self):\r
        if self._LiteralToken.startswith('{') and \\r
            self._LiteralToken.endswith('}'):\r
            return True\r
\r
        if gHexPattern.match(self._LiteralToken):\r
            Token = self._LiteralToken[2:]\r
            Token = Token.lstrip('0')\r
            if not Token:\r
                self._LiteralToken = '0x0'\r
            else:\r
                self._LiteralToken = '0x' + Token.lower()\r
            return True\r
        return False\r
\r
    def _GetToken(self):\r
        return self.__GetNList()\r
\r
    @staticmethod\r
    def __IsIdChar(Ch):\r
        return Ch in '._/:' or Ch.isalnum()\r
\r
    # Parse operand\r
    def _GetSingleToken(self):\r
        self.__SkipWS()\r
        Expr = self._Expr[self._Idx:]\r
        if Expr.startswith('L"'):\r
            # Skip L\r
            self._Idx += 1\r
            UStr = self.__GetString()\r
            self._Token = 'L"' + UStr + '"'\r
            return self._Token\r
\r
        self._Token = ''\r
        if Expr:\r
            Ch = Expr[0]\r
            Match = gGuidPattern.match(Expr)\r
            if Match and not Expr[Match.end():Match.end() + 1].isalnum() \\r
                and Expr[Match.end():Match.end() + 1] != '_':\r
                self._Idx += Match.end()\r
                self._Token = Expr[0:Match.end()]\r
                return self._Token\r
            elif self.__IsIdChar(Ch):\r
                return self.__GetIdToken()\r
            elif Ch == '(' or Ch == ')':\r
                self._Idx += 1\r
                self._Token = Ch\r
                return self._Token\r
\r
        raise BadExpression(ERR_VALID_TOKEN % Expr)\r
\r
    # Parse operator\r
    def _GetOperator(self):\r
        self.__SkipWS()\r
        LegalOpLst = ['&&', '||', '!=', '==', '>=', '<='] + self.NonLetterOpLst\r
\r
        self._Token = ''\r
        Expr = self._Expr[self._Idx:]\r
\r
        # Reach end of expression\r
        if not Expr:\r
            return ''\r
\r
        # Script operator: LT, GT, LE, GE, EQ, NE, and, or, xor, not\r
        if Expr[0].isalpha():\r
            return self.__GetIdToken(True)\r
\r
        # Start to get regular operator: +, -, <, > ...\r
        if Expr[0] not in self.NonLetterOpLst:\r
            return ''\r
\r
        OpToken = ''\r
        for Ch in Expr:\r
            if Ch in self.NonLetterOpLst:\r
                if '!' == Ch and OpToken:\r
                    break\r
                self._Idx += 1\r
                OpToken += Ch\r
            else:\r
                break\r
\r
        if OpToken not in LegalOpLst:\r
            raise BadExpression(ERR_OPERATOR_UNSUPPORT % OpToken)\r
        self._Token = OpToken\r
        return OpToken\r
\r
    # Check if current token matches the operators given from OpList\r
    def _IsOperator(self, OpList):\r
        Idx = self._Idx\r
        self._GetOperator()\r
        if self._Token in OpList:\r
            if self._Token in self.LogicalOperators:\r
                self._Token = self.LogicalOperators[self._Token]\r
            return True\r
        self._Idx = Idx\r
        return False\r
\r
\r
    \r
    \r
    \r
    \r
\r
\r
\r
\r
#    UTRangeList()\r