path: root/lmi/scripts/common/versioncheck/parser.py

# Copyright (C) 2013-2014 Red Hat, Inc. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice,
#    this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
#
# The views and conclusions contained in the software and documentation are
# those of the authors and should not be interpreted as representing official
# policies, either expressed or implied, of the FreeBSD Project.
#
# Authors: Michal Minar <miminar@redhat.com>
#
"""
Parser for mini-language specifying profile and class requirements. We call
the language LMIReSpL (openLMI Requirement Specification Language).

The only thing designed for use outside this module is :py:func:`bnf_parser`.

Language is generated by BNF grammer which served as a model for parser.

Formal representation of BNF grammer is following: ::

    expr          ::= term [ op expr ]*
    term          ::= '!'? req
    req           ::= profile_cond | clsreq_cond | '(' expr ')'
    profile_cond  ::= 'profile'? [ profile | profile_quot ] cond?
    clsreq_cond   ::= 'class' [ clsname | clsname_quot] cond?
    profile_quot  ::= '"' /\w+[ +.a-zA-Z0-9_-]*/ '"'
    profile       ::= /\w+[+.a-zA-Z_-]*/
    clsname_quot  ::= '"' clsname '"'
    clsname       ::= /[a-zA-Z]+_[a-zA-Z][a-zA-Z0-9_]*/
    cond          ::= cmpop version
    cmpop         ::= /(<|=|>|!)=|<|>/
    version       ::= /[0-9]+(\.[0-9]+)*/
    op            ::= '&' | '|'

String surrounded by quotes is a literal. String enclosed with slashes is a
regular expression. Square brackets encloses a group of words and limit
the scope of some operation (like iteration).
"""
import abc
import operator
from pyparsing import Literal, Combine, Optional, ZeroOrMore, \
        Forward, Regex, Keyword, FollowedBy, LineEnd, ParseException

#: Dictionary mapping supported comparison operators to a pair. First item is a
#: function making the comparison and the second can be of two values (``all``
#: or ``any``). Former sayes that each part of first version string must be in
#: relation to corresponding part of second version string in order to satisfy
#: the condition. The latter causes the comparison to end on first satisfied
#: part.
OP_MAP = {
        '==' : (operator.eq, all),
        '<=' : (operator.le, all),
        '>=' : (operator.ge, all),
        '!=' : (operator.ne, any),
        '>'  : (operator.gt, any),
        '<'  : (operator.lt, any)
}

def cmp_version(fst, snd, opsign='<'):
    """
    Compare two version specifications. Each version string shall contain
    digits delimited with dots. Empty string is also valid version. It will be
    replaced with -1.

    :param str fst: First version string.
    :param str snd: Second version string.
    :param str opsign: Sign denoting operation to be used. Supported signs
        are present in :py:attr:`OP_MAP`.
    :returns: ``True`` if the relation denoted by particular operation exists
        between two operands.
    :rtype: boolean
    """
    def splitver(ver):
        """ Converts version string to a tuple of integers. """
        return tuple(int(p) if p else -1 for p in ver.split('.'))
    aparts = splitver(fst)
    bparts = splitver(snd)
    op, which = OP_MAP[opsign]
    if which is all:
        for ap, bp in zip(aparts, bparts):
            if not op(ap, bp):
                return False
    else:
        for ap, bp in zip(aparts, bparts):
            if op(ap, bp):
                return True
            if ap != bp:
                return False
    return op(len(aparts), len(bparts))

class SemanticGroup(object):
    """
    Base class for non-terminals. Just a minimal set of non-terminals is
    represented by objects the rest is represented by strings.

    All subclasses need to define their own :py:meth:`evaluate` method. The
    parser builds a tree of these non-terminals with single non-terminal being
    a root node. This node's *evaluate* method returns a boolean saying whether
    the condition is satisfied. Root node is always an object of
    :py:class:`Expr`.
    """

    __metaclass__ = abc.ABCMeta

    def __call__(self):
        return self.evaluate()

    @abc.abstractmethod
    def evaluate(self):
        """
        :returns: ``True`` if the sub-condition represented by this non-terminal
            is satisfied.
        :rtype: boolean
        """
        pass

class Expr(SemanticGroup):
    """
    Initial non-terminal. Object of this class (or one of its subclasses) is a
    result of parsing.

    :param term: An object of :py:class:`Term` non-terminal.
    """

    def __init__(self, term):
        assert isinstance(term, Term)
        self.fst = term

    def evaluate(self):
        return self.fst()

    def __str__(self):
        return str(self.fst)

class And(Expr):
    """
    Represents logical *AND* of two expressions. Short-circuit evaluation is
    being exploited here.

    :param fst: An object of :py:class:`Term` non-terminal.
    :param snd: An object of :py:class:`Term` non-terminal.
    """

    def __init__(self, fst, snd):
        assert isinstance(snd, (Term, Expr))
        Expr.__init__(self, fst)
        self.snd = snd

    def evaluate(self):
        if self.fst():
            return self.snd()
        return False

    def __str__(self):
        return "%s & %s" % (self.fst, self.snd)

class Or(Expr):
    """
    Represents logical *OR* of two expressions. Short-circuit evaluation is being
    exploited here.

    :param fst: An object of :py:class:`Term` non-terminal.
    :param snd: An object of :py:class:`Term` non-terminal.
    """

    def __init__(self, fst, snd):
        assert isinstance(snd, (Term, Expr))
        Expr.__init__(self, fst)
        self.snd = snd

    def evaluate(self):
        if self.fst():
            return True
        return self.snd()

    def __str__(self):
        return "%s | %s" % (self.fst, self.snd)

class Term(SemanticGroup):
    """
    Represents possible negation of expression.

    :param req: An object of :py:class:`Req`.
    :param boolean negate: Whether the result of children shall be negated.
    """

    def __init__(self, req, negate):
        assert isinstance(req, Req)
        self.req = req
        self.negate = negate

    def evaluate(self):
        res = self.req()
        return not res if self.negate else res

    def __str__(self):
        if self.negate:
            return '!' + str(self.req)
        return str(self.req)

class Req(SemanticGroup):
    """
    Represents one of following subexpressions:

        * single requirement on particular profile
        * single requirement on particular class
        * a subexpression
    """
    pass

class ReqCond(Req):
    """
    Represents single requirement on particular class or profile.

    :param str kind: Name identifying kind of thing this belongs. For example
        ``'class'`` or ``'profile'``.
    :param callable version_getter: Is a function called to get version of
        either profile or CIM class. It must return corresponding version string
        if the profile or class is registered and ``None`` otherwise.
        Version string is read from ``RegisteredVersion`` property of
        ``CIM_RegisteredProfile``. If a class is being queried, version
        shall be taken from ``Version`` qualifier of given class.
    :param str name: Name of profile or CIM class to check for. In case
        of a profile, it is compared to ``RegisteredName`` property of
        ``CIM_RegisteredProfile``. If any instance of this class has matching
        name, it's version will be checked. If no matching instance is found,
        instances of ``CIM_RegisteredSubProfile`` are queried the same way.
        Failing to find it results in ``False``.
    :param str cond: Is a version requirement. Check the grammer above for
        ``cond`` non-terminal.
    """

    def __init__(self, kind, version_getter, name, cond=None):
        assert isinstance(kind, basestring)
        assert callable(version_getter)
        assert isinstance(name, basestring)
        assert cond is None or (isinstance(cond, tuple) and len(cond) == 2)
        self.kind = kind
        self.version_getter = version_getter
        self.name = name
        self.cond = cond

    def evaluate(self):
        version = self.version_getter(self.name)
        return version and (not self.cond or self._check_version(version))

    def _check_version(self, version):
        """
        Checks whether the version of profile or class satisfies the
        requirement. Version strings are first split into a list of integers
        (that were delimited with a dot) and then they are compared in
        descending order from the most signigicant down.

        :param str version: Version of profile or class to check.
        """
        opsign, cmpver = self.cond
        return cmp_version(version, cmpver, opsign)

    def __str__(self):
        return '{%s "%s"%s}' % (
                self.kind, self.name, ' %s %s' % self.cond if self.cond else '')

class Subexpr(Req):
    """
    Represents a subexpression originally enclosed in brackets.
    """

    def __init__(self, expr):
        assert isinstance(expr, Expr)
        self.expr = expr

    def evaluate(self):
        return self.expr()

    def __str__(self):
        return "(%s)" % self.expr

class TreeBuilder(object):
    """
    A stack interface for parser. It defines methods modifying the stack with
    additional checks.
    """

    def __init__(self, stack, profile_version_getter, class_version_getter):
        if not isinstance(stack, list):
            raise TypeError("stack needs to be empty!")
        if stack:
            stack[:] = []
        self.stack = stack
        self.profile_version_getter = profile_version_getter
        self.class_version_getter = class_version_getter

    def expr(self, strg, loc, toks):
        """
        Operates upon a stack. It takes either one or two *terms* there
        and makes an expression object out of them. Terms need to be delimited
        with logical operator.
        """
        assert len(self.stack) > 0
        if not isinstance(self.stack[-1], (Term, Expr)):
            raise ParseException("Invalid expression (stopped at char %d)."
                    % loc)
        if len(self.stack) >= 3 and self.stack[-2] in ('&', '|'):
            assert isinstance(self.stack[-3], Term)
            if self.stack[-2] == '&':
                expr = And(self.stack[-3], self.stack[-1])
            else:
                expr = Or(self.stack[-3], self.stack[-1])
            self.stack.pop()
            self.stack.pop()
        elif not isinstance(self.stack[-1], Expr):
            expr = Expr(self.stack[-1])
        else:
            expr = self.stack[-1]
        self.stack[-1] = expr

    def term(self, strg, loc, toks):
        """
        Creates a ``term`` out of requirement (``req`` non-terminal).
        """
        assert len(self.stack) > 0
        assert isinstance(self.stack[-1], Req)
        self.stack[-1] = Term(self.stack[-1], toks[0] == '!')

    def subexpr(self, strg, loc, toks):
        """
        Operates upon a stack. It creates an instance of :py:class:`Subexpr`
        out of :py:class:`Expr` which is enclosed in brackets.
        """
        assert len(self.stack) > 1
        assert self.stack[-2] == '('
        assert isinstance(self.stack[-1], Expr)
        assert len(toks) > 0 and toks[-1] == ')'
        self.stack[-2] = Subexpr(self.stack[-1])
        self.stack.pop()

    def push_class(self, strg, loc, toks):
        """
        Handles ``clsreq_cond`` non-terminal in one go. It extracts
        corresponding tokens and pushes an object of :py:class:`ReqCond` to a
        stack.
        """
        assert toks[0] == 'class'
        assert len(toks) >= 2
        name = toks[1]
        condition = None
        if len(toks) > 2 and toks[2] in OP_MAP:
            assert len(toks) >= 4
            condition = toks[2], toks[3]
        self.stack.append(ReqCond('class', self.class_version_getter,
            name, condition))

    def push_profile(self, strg, loc, toks):
        """
        Handles ``profile_cond`` non-terminal in one go. It behaves in the same
        way as :py:meth:`push_profile`.
        """
        index = 0
        if toks[0] == 'profile':
            index = 1
        assert len(toks) > index
        name = toks[index]
        index += 1
        condition = None
        if len(toks) > index and toks[index] in OP_MAP:
            assert len(toks) >= index + 2
            condition = toks[index], toks[index + 1]
        self.stack.append(ReqCond('profile', self.profile_version_getter,
            name, condition))

    def push_literal(self, strg, loc, toks):
        """
        Pushes operators to a stack.
        """
        assert toks[0] in ('&', '|', '(')
        if toks[0] == '(':
            assert not self.stack or self.stack[-1] in ('&', '|')
        else:
            assert len(self.stack) > 0
            assert isinstance(self.stack[-1], Term)
        self.stack.append(toks[0])

def bnf_parser(stack, profile_version_getter, class_version_getter):
    """
    Builds a parser operating on provided stack.

    :param list stack: Stack to operate on. It will contain the resulting
        :py:class:`Expr` object when the parsing is successfully over -
        it will be the only item in the list. It needs to be initially empty.
    :param callable profile_version_getter: Function returning version
        of registered profile or ``None`` if not present.
    :param callable class_version_getter: Fucntion returning version
        of registered class or ``None`` if not present.
    :returns: Parser object.
    :rtype: :py:class:`pyparsing,ParserElement`
    """
    if not isinstance(stack, list):
        raise TypeError("stack must be a list!")
    builder = TreeBuilder(stack, profile_version_getter, class_version_getter)

    ntop = ((Literal('&') | Literal('|')) + FollowedBy(Regex('["a-zA-Z\(!]'))) \
            .setName('op').setParseAction(builder.push_literal)
    ntversion = Regex(r'[0-9]+(\.[0-9]+)*').setName('version')
    ntcmpop = Regex(r'(<|=|>|!)=|<|>(?=\s*\d)').setName('cmpop')
    ntcond = (ntcmpop + ntversion).setName('cond')
    ntclsname = Regex(r'[a-zA-Z]+_[a-zA-Z][a-zA-Z0-9_]*').setName('clsname')
    ntclsname_quot = Combine(
              Literal('"').suppress()
            + ntclsname
            + Literal('"').suppress()).setName('clsname_quot')
    ntprofile_quot = Combine(
              Literal('"').suppress()
            + Regex(r'\w+[ +.a-zA-Z0-9_-]*')
            + Literal('"').suppress()).setName('profile_quot')
    ntprofile = Regex(r'\w+[+.a-zA-Z0-9_-]*').setName('profile')
    ntclsreq_cond = (
              Keyword('class')
            + (ntclsname_quot | ntclsname)
            + Optional(ntcond)).setName('clsreq_cond').setParseAction(
                    builder.push_class)
    ntprofile_cond = (
              Optional(Keyword('profile'))
            + (ntprofile_quot | ntprofile)
            + Optional(ntcond)).setName('profile_cond').setParseAction(
                    builder.push_profile)
    ntexpr = Forward().setName('expr')
    bracedexpr = (
              Literal('(').setParseAction(builder.push_literal)
            + ntexpr
            + Literal(')')).setParseAction(builder.subexpr)
    ntreq = (bracedexpr | ntclsreq_cond | ntprofile_cond).setName('req')
    ntterm = (Optional(Literal("!")) + ntreq + FollowedBy(Regex('[\)&\|]') | LineEnd()))\
            .setParseAction(builder.term)
    ntexpr << ntterm + ZeroOrMore(ntop + ntexpr).setParseAction(builder.expr)

    return ntexpr

if __name__ == '__main__':
    def get_class_version(class_name):
        try:
            version = { 'lmi_logicalfile'      : '0.1.2'
                      , 'lmi_softwareidentity' : '3.2.1'
                      , 'pg_computersystem'    : '1.1.1'
                      }[class_name.lower()]
        except KeyError:
            version = None
        return version

    def get_profile_version(profile_name):
        try:
            version = { 'openlmi software' : '0.1.2'
                      , 'openlmi-software' : '1.3.4'
                      , 'openlmi hardware' : '1.1.1'
                      , 'openlmi-hardware' : '0.2.3'
                      }[profile_name.lower()]
        except KeyError:
            version = None
        return version

    def test(s, expected):
        stack = []
        parser = bnf_parser(stack, get_profile_version, get_class_version)
        results = parser.parseString(s, parseAll=True)
        if len(stack) == 1:
            evalresult = stack[0]()
            if expected == evalresult:
                print "%s\t=>\tOK" % s
            else:
                print "%s\t=>\tFAILED" % s
        else:
            print "%s\t=>\tFAILED" % s
        print "  stack: [%s]" % ', '.join(str(i) for i in stack)

    test( 'class LMI_SoftwareIdentity == 0.2.0', False)
    test( '"OpenLMI-Software" == 0.1.2 & "OpenLMI-Hardware" < 0.1.3', False)
    test( 'OpenLMI-Software<1|OpenLMI-Hardware!=1.2.4', True)
    test( '"OpenLMI Software" & profile "OpenLMI Hardware"'
          ' | ! class LMI_LogicalFile', True)
    test( 'profile OpenLMI-Software > 0.1.2 & !(class "PG_ComputerSystem"'
          ' == 2.3.4 | "OpenLMI Hardware")', False)
    test( 'OpenLMI-Software > 1.3 & OpenLMI-Software >= 1.3.4'
          ' & OpenLMI-Software < 1.3.4.1 & OpenLMI-Software <= 1.3.4'
          ' & OpenLMI-Software == 1.3.4', True)
    test( 'OpenLMI-Software < 1.3.4 | OpenLMI-Software > 1.3.4'
          ' | OpenLMI-Software != 1.3.4', False)
    test( '(! OpenLMI-Software == 1.3.4 | OpenLMI-Software <= 1.3.4.1)'
          ' & !(openlmi-software > 1.3.4 | Openlmi-software != 1.3.4)', True)
    for badexpr in (
            'OpenLMI-Software > & OpenLMI-Hardware',
            'classs LMI_SoftwareIdentity',
            'OpenLMI-Software > 1.2.3 | == 5.4.3',
            '',
            '"OpenLMI-Software',
            'OpenLMI-Software < > OpenLMI-Hardware',
            'OpenlmiSoftware & (openLMI-Hardware ',
            'OpenLMISoftware & ) OpenLMI-Hardare (',
            'OpenLMISoftware | OpenlmiSoftware > "1.2.3"'
            ):
        try:
            test(badexpr, None)
        except ParseException:
            print "%s\t=>\tOK" % badexpr