• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/python3
2
3# Copyright 2022-2023 The Khronos Group Inc.
4# Copyright 2003-2019 Paul McGuire
5# SPDX-License-Identifier: MIT
6
7# apirequirements.py - parse 'depends' expressions in API XML
8# Supported methods:
9#   dependency - the expression string
10#
11# evaluateDependency(dependency, isSupported) evaluates the expression,
12# returning a boolean result. isSupported takes an extension or version name
13# string and returns a boolean.
14#
15# dependencyLanguage(dependency) returns an English string equivalent
16# to the expression, suitable for header file comments.
17#
18# dependencyNames(dependency) returns a set of the extension and
19# version names in the expression.
20#
21# dependencyMarkup(dependency) returns a string containing asciidoctor
22# markup for English equivalent to the expression, suitable for extension
23# appendices.
24#
25# All may throw a ParseException if the expression cannot be parsed or is
26# not completely consumed by parsing.
27
28# Supported expressions at present:
29#   - extension names
30#   - '+' as AND connector
31#   - ',' as OR connector
32#   - parenthesization for grouping
33
34# Based on https://github.com/pyparsing/pyparsing/blob/master/examples/fourFn.py
35
36from pyparsing import (
37    Literal,
38    Word,
39    Group,
40    Forward,
41    alphas,
42    alphanums,
43    Regex,
44    ParseException,
45    CaselessKeyword,
46    Suppress,
47    delimitedList,
48    infixNotation,
49)
50import math
51import operator
52import pyparsing as pp
53import re
54
55def nameMarkup(name):
56    """Returns asciidoc markup to generate a link to an API version or
57       extension anchor.
58
59       - name - version or extension name"""
60
61    # Could use ApiConventions.is_api_version_name, but that does not split
62    # out the major/minor version numbers.
63    match = re.search("[A-Z]+_VERSION_([0-9]+)_([0-9]+)", name)
64    if match is not None:
65        major = match.group(1)
66        minor = match.group(2)
67        version = major + '.' + minor
68        return f'<<versions-{major}.{minor}, Version {version}>>'
69    else:
70        return 'apiext:' + name
71
72exprStack = []
73
74def push_first(toks):
75    """Push a token on the global stack
76
77       - toks - first element is the token to push"""
78
79    exprStack.append(toks[0])
80
81# An identifier (version or extension name)
82dependencyIdent = Word(alphanums + '_')
83
84# Infix expression for depends expressions
85dependencyExpr = pp.infixNotation(dependencyIdent,
86    [ (pp.oneOf(', +'), 2, pp.opAssoc.LEFT), ])
87
88# BNF grammar for depends expressions
89_bnf = None
90def dependencyBNF():
91    """
92    boolop  :: '+' | ','
93    extname :: Char(alphas)
94    atom    :: extname | '(' expr ')'
95    expr    :: atom [ boolop atom ]*
96    """
97    global _bnf
98    if _bnf is None:
99        and_, or_ = map(Literal, '+,')
100        lpar, rpar = map(Suppress, '()')
101        boolop = and_ | or_
102
103        expr = Forward()
104        expr_list = delimitedList(Group(expr))
105        atom = (
106            boolop[...]
107            + (
108                (dependencyIdent).setParseAction(push_first)
109                | Group(lpar + expr + rpar)
110            )
111        )
112
113        expr <<= atom + (boolop + atom).setParseAction(push_first)[...]
114        _bnf = expr
115    return _bnf
116
117
118# map operator symbols to corresponding arithmetic operations
119_opn = {
120    '+': operator.and_,
121    ',': operator.or_,
122}
123
124# map operator symbols to corresponding words
125_opname = {
126    '+': 'and',
127    ',': 'or',
128}
129
130def evaluateStack(stack, isSupported):
131    """Evaluate an expression stack, returning a boolean result.
132
133     - stack - the stack
134     - isSupported - function taking a version or extension name string and
135       returning True or False if that name is supported or not."""
136
137    op, num_args = stack.pop(), 0
138    if isinstance(op, tuple):
139        op, num_args = op
140
141    if op in '+,':
142        # Note: operands are pushed onto the stack in reverse order
143        op2 = evaluateStack(stack, isSupported)
144        op1 = evaluateStack(stack, isSupported)
145        return _opn[op](op1, op2)
146    elif op[0].isalpha():
147        return isSupported(op)
148    else:
149        raise Exception(f'invalid op: {op}')
150
151def evaluateDependency(dependency, isSupported):
152    """Evaluate a dependency expression, returning a boolean result.
153
154     - dependency - the expression
155     - isSupported - function taking a version or extension name string and
156       returning True or False if that name is supported or not."""
157
158    global exprStack
159    exprStack = []
160    results = dependencyBNF().parseString(dependency, parseAll=True)
161    val = evaluateStack(exprStack[:], isSupported)
162    return val
163
164def evalDependencyLanguage(stack, specmacros):
165    """Evaluate an expression stack, returning an English equivalent
166
167     - stack - the stack
168     - specmacros - if True, prepare the language for spec inclusion"""
169
170    op, num_args = stack.pop(), 0
171    if isinstance(op, tuple):
172        op, num_args = op
173    if op in '+,':
174        # Could parenthesize, not needed yet
175        rhs = evalDependencyLanguage(stack, specmacros)
176        return evalDependencyLanguage(stack, specmacros) + f' {_opname[op]} ' + rhs
177    elif op[0].isalpha():
178        # This is an extension or feature name
179        if specmacros:
180            return nameMarkup(op)
181        else:
182            return op
183    else:
184        raise Exception(f'invalid op: {op}')
185
186def dependencyLanguage(dependency, specmacros = False):
187    """Return an API dependency expression translated to a form suitable for
188       asciidoctor conditionals or header file comments.
189
190     - dependency - the expression
191     - specmacros - if False, return a string that can be used as an
192       asciidoctor conditional.
193       If True, return a string suitable for spec inclusion with macros and
194       xrefs included."""
195
196    global exprStack
197    exprStack = []
198    results = dependencyBNF().parseString(dependency, parseAll=True)
199    return evalDependencyLanguage(exprStack, specmacros)
200
201def evalDependencyNames(stack):
202    """Evaluate an expression stack, returning the set of extension and
203       feature names used in the expression.
204
205     - stack - the stack"""
206
207    op, num_args = stack.pop(), 0
208    if isinstance(op, tuple):
209        op, num_args = op
210    if op in '+,':
211        # Do not evaluate the operation. We only care about the names.
212        return evalDependencyNames(stack) | evalDependencyNames(stack)
213    elif op[0].isalpha():
214        return { op }
215    else:
216        raise Exception(f'invalid op: {op}')
217
218def dependencyNames(dependency):
219    """Return a set of the extension and version names in an API dependency
220       expression. Used when determining transitive dependencies for spec
221       generation with specific extensions included.
222
223     - dependency - the expression"""
224
225    global exprStack
226    exprStack = []
227    results = dependencyBNF().parseString(dependency, parseAll=True)
228    # print(f'names(): stack = {exprStack}')
229    return evalDependencyNames(exprStack)
230
231def markupTraverse(expr, level = 0, root = True):
232    """Recursively process a dependency in infix form, transforming it into
233       asciidoctor markup with expression nesting indicated by indentation
234       level.
235
236       - expr - expression to process
237       - level - indentation level to render expression at
238       - root - True only on initial call"""
239
240    if level > 0:
241        prefix = '{nbsp}{nbsp}' * level * 2 + ' '
242    else:
243        prefix = ''
244    str = ''
245
246    for elem in expr:
247        if isinstance(elem, pp.ParseResults):
248            if not root:
249                nextlevel = level + 1
250            else:
251                # Do not indent the outer expression
252                nextlevel = level
253
254            str = str + markupTraverse(elem, level = nextlevel, root = False)
255        elif elem in ('+', ','):
256            str = str + f'{prefix}{_opname[elem]} +\n'
257        else:
258            str = str + f'{prefix}{nameMarkup(elem)} +\n'
259
260    return str
261
262def dependencyMarkup(dependency):
263    """Return asciidoctor markup for a human-readable equivalent of an API
264       dependency expression, suitable for use in extension appendix
265       metadata.
266
267     - dependency - the expression"""
268
269    parsed = dependencyExpr.parseString(dependency)
270    return markupTraverse(parsed)
271
272if __name__ == "__main__":
273
274    termdict = {
275        'VK_VERSION_1_1' : True,
276        'false' : False,
277        'true' : True,
278    }
279    termSupported = lambda name: name in termdict and termdict[name]
280
281    def test(dependency, expected):
282        val = False
283        try:
284            val = evaluateDependency(dependency, termSupported)
285        except ParseException as pe:
286            print(dependency, f'failed parse: {dependency}')
287        except Exception as e:
288            print(dependency, f'failed eval: {dependency}')
289
290        if val == expected:
291            print(f'{dependency} = {val} (as expected)')
292        else:
293            print(f'{dependency} ERROR: {val} != {expected}')
294
295    # Verify expressions are evaluated left-to-right
296
297    test('false,false+false', False)
298    test('false,false+true', False)
299    test('false,true+false', False)
300    test('false,true+true', True)
301    test('true,false+false', False)
302    test('true,false+true', True)
303    test('true,true+false', False)
304    test('true,true+true', True)
305
306    test('false,(false+false)', False)
307    test('false,(false+true)', False)
308    test('false,(true+false)', False)
309    test('false,(true+true)', True)
310    test('true,(false+false)', True)
311    test('true,(false+true)', True)
312    test('true,(true+false)', True)
313    test('true,(true+true)', True)
314
315
316    test('false+false,false', False)
317    test('false+false,true', True)
318    test('false+true,false', False)
319    test('false+true,true', True)
320    test('true+false,false', False)
321    test('true+false,true', True)
322    test('true+true,false', True)
323    test('true+true,true', True)
324
325    test('false+(false,false)', False)
326    test('false+(false,true)', False)
327    test('false+(true,false)', False)
328    test('false+(true,true)', False)
329    test('true+(false,false)', False)
330    test('true+(false,true)', True)
331    test('true+(true,false)', True)
332    test('true+(true,true)', True)
333
334
335    #test('VK_VERSION_1_1+(false,true)', True)
336    #test('true', True)
337    #test('(true)', True)
338    #test('false,false', False)
339    #test('false,true', True)
340    #test('false+true', False)
341    #test('true+true', True)
342
343    # Check formatting
344    for dependency in [
345        #'true',
346        #'true+true+false',
347        'true+(true+false),(false,true)',
348        'true+((true+false),(false,true))',
349        #'VK_VERSION_1_1+(true,false)',
350    ]:
351        print(f'expr = {dependency}\n{dependencyMarkup(dependency)}')
352        print(f'  language = {dependencyLanguage(dependency)}')
353        print(f'  names = {dependencyNames(dependency)}')
354        print(f'  value = {evaluateDependency(dependency, termSupported)}')
355