• 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 markupPassthrough(name):
56    """Pass a name (leaf or operator) through without applying markup"""
57    return name
58
59# A regexp matching Vulkan and VulkanSC core version names
60# The Conventions is_api_version_name() method is similar, but does not
61# return the matches.
62apiVersionNamePat = re.compile(r'(VK|VKSC)_VERSION_([0-9]+)_([0-9]+)')
63
64def apiVersionNameMatch(name):
65    """Return [ apivariant, major, minor ] if name is an API version name,
66       or [ None, None, None ] if it is not."""
67
68    match = apiVersionNamePat.match(name)
69    if match is not None:
70        return [ match.group(1), match.group(2), match.group(3) ]
71    else:
72        return [ None, None, None ]
73
74def leafMarkupAsciidoc(name):
75    """Markup a leaf name as an asciidoc link to an API version or extension
76       anchor.
77
78       - name - version or extension name"""
79
80    (apivariant, major, minor) = apiVersionNameMatch(name)
81
82    if apivariant is not None:
83        version = major + '.' + minor
84        if apivariant == 'VKSC':
85            # Vulkan SC has a different anchor pattern for version appendices
86            if version == '1.0':
87                return 'Vulkan SC 1.0'
88            else:
89                return f'<<versions-sc-{version}, Version SC {version}>>'
90        else:
91            return f'<<versions-{version}, Version {version}>>'
92    else:
93        return f'apiext:{name}'
94
95def leafMarkupC(name):
96    """Markup a leaf name as a C expression, using conventions of the
97       Vulkan Validation Layers
98
99       - name - version or extension name"""
100
101    (apivariant, major, minor) = apiVersionNameMatch(name)
102
103    if apivariant is not None:
104        return name
105    else:
106        return f'ext.{name}'
107
108opMarkupAsciidocMap = { '+' : 'and', ',' : 'or' }
109
110def opMarkupAsciidoc(op):
111    """Markup a operator as an asciidoc spec markup equivalent
112
113       - op - operator ('+' or ',')"""
114
115    return opMarkupAsciidocMap[op]
116
117opMarkupCMap = { '+' : '&&', ',' : '||' }
118
119def opMarkupC(op):
120    """Markup a operator as an C language equivalent
121
122       - op - operator ('+' or ',')"""
123
124    return opMarkupCMap[op]
125
126
127# Unfortunately global to be used in pyparsing
128exprStack = []
129
130def push_first(toks):
131    """Push a token on the global stack
132
133       - toks - first element is the token to push"""
134
135    exprStack.append(toks[0])
136
137# An identifier (version or extension name)
138dependencyIdent = Word(alphanums + '_')
139
140# Infix expression for depends expressions
141dependencyExpr = pp.infixNotation(dependencyIdent,
142    [ (pp.oneOf(', +'), 2, pp.opAssoc.LEFT), ])
143
144# BNF grammar for depends expressions
145_bnf = None
146def dependencyBNF():
147    """
148    boolop  :: '+' | ','
149    extname :: Char(alphas)
150    atom    :: extname | '(' expr ')'
151    expr    :: atom [ boolop atom ]*
152    """
153    global _bnf
154    if _bnf is None:
155        and_, or_ = map(Literal, '+,')
156        lpar, rpar = map(Suppress, '()')
157        boolop = and_ | or_
158
159        expr = Forward()
160        expr_list = delimitedList(Group(expr))
161        atom = (
162            boolop[...]
163            + (
164                (dependencyIdent).setParseAction(push_first)
165                | Group(lpar + expr + rpar)
166            )
167        )
168
169        expr <<= atom + (boolop + atom).setParseAction(push_first)[...]
170        _bnf = expr
171    return _bnf
172
173
174# map operator symbols to corresponding arithmetic operations
175_opn = {
176    '+': operator.and_,
177    ',': operator.or_,
178}
179
180def evaluateStack(stack, isSupported):
181    """Evaluate an expression stack, returning a boolean result.
182
183     - stack - the stack
184     - isSupported - function taking a version or extension name string and
185       returning True or False if that name is supported or not."""
186
187    op, num_args = stack.pop(), 0
188    if isinstance(op, tuple):
189        op, num_args = op
190
191    if op in '+,':
192        # Note: operands are pushed onto the stack in reverse order
193        op2 = evaluateStack(stack, isSupported)
194        op1 = evaluateStack(stack, isSupported)
195        return _opn[op](op1, op2)
196    elif op[0].isalpha():
197        return isSupported(op)
198    else:
199        raise Exception(f'invalid op: {op}')
200
201def evaluateDependency(dependency, isSupported):
202    """Evaluate a dependency expression, returning a boolean result.
203
204     - dependency - the expression
205     - isSupported - function taking a version or extension name string and
206       returning True or False if that name is supported or not."""
207
208    global exprStack
209    exprStack = []
210    results = dependencyBNF().parseString(dependency, parseAll=True)
211    val = evaluateStack(exprStack[:], isSupported)
212    return val
213
214def evalDependencyLanguage(stack, leafMarkup, opMarkup, parenthesize, root):
215    """Evaluate an expression stack, returning an English equivalent
216
217     - stack - the stack
218     - leafMarkup, opMarkup, parenthesize - same as dependencyLanguage
219     - root - True only if this is the outer (root) expression level"""
220
221    op, num_args = stack.pop(), 0
222    if isinstance(op, tuple):
223        op, num_args = op
224    if op in '+,':
225        # Could parenthesize, not needed yet
226        rhs = evalDependencyLanguage(stack, leafMarkup, opMarkup, parenthesize, root = False)
227        opname = opMarkup(op)
228        lhs = evalDependencyLanguage(stack, leafMarkup, opMarkup, parenthesize, root = False)
229        if parenthesize and not root:
230            return f'({lhs} {opname} {rhs})'
231        else:
232            return f'{lhs} {opname} {rhs}'
233    elif op[0].isalpha():
234        # This is an extension or feature name
235        return leafMarkup(op)
236    else:
237        raise Exception(f'invalid op: {op}')
238
239def dependencyLanguage(dependency, leafMarkup, opMarkup, parenthesize):
240    """Return an API dependency expression translated to a form suitable for
241       asciidoctor conditionals or header file comments.
242
243     - dependency - the expression
244     - leafMarkup - function taking an extension / version name and
245                    returning an equivalent marked up version
246     - opMarkup - function taking an operator ('+' / ',') name name and
247                  returning an equivalent marked up version
248     - parenthesize - True if parentheses should be used in the resulting
249                      expression, False otherwise"""
250
251    global exprStack
252    exprStack = []
253    results = dependencyBNF().parseString(dependency, parseAll=True)
254    return evalDependencyLanguage(exprStack, leafMarkup, opMarkup, parenthesize, root = True)
255
256# aka specmacros = False
257def dependencyLanguageComment(dependency):
258    """Return dependency expression translated to a form suitable for
259       comments in headers of emitted C code, as used by the
260       docgenerator."""
261    return dependencyLanguage(dependency, leafMarkup = markupPassthrough, opMarkup = opMarkupAsciidoc, parenthesize = True)
262
263# aka specmacros = True
264def dependencyLanguageSpecMacros(dependency):
265    """Return dependency expression translated to a form suitable for
266       comments in headers of emitted C code, as used by the
267       interfacegenerator."""
268    return dependencyLanguage(dependency, leafMarkup = leafMarkupAsciidoc, opMarkup = opMarkupAsciidoc, parenthesize = False)
269
270def dependencyLanguageC(dependency):
271    """Return dependency expression translated to a form suitable for
272       use in C expressions"""
273    return dependencyLanguage(dependency, leafMarkup = leafMarkupC, opMarkup = opMarkupC, parenthesize = True)
274
275def evalDependencyNames(stack):
276    """Evaluate an expression stack, returning the set of extension and
277       feature names used in the expression.
278
279     - stack - the stack"""
280
281    op, num_args = stack.pop(), 0
282    if isinstance(op, tuple):
283        op, num_args = op
284    if op in '+,':
285        # Do not evaluate the operation. We only care about the names.
286        return evalDependencyNames(stack) | evalDependencyNames(stack)
287    elif op[0].isalpha():
288        return { op }
289    else:
290        raise Exception(f'invalid op: {op}')
291
292def dependencyNames(dependency):
293    """Return a set of the extension and version names in an API dependency
294       expression. Used when determining transitive dependencies for spec
295       generation with specific extensions included.
296
297     - dependency - the expression"""
298
299    global exprStack
300    exprStack = []
301    results = dependencyBNF().parseString(dependency, parseAll=True)
302    # print(f'names(): stack = {exprStack}')
303    return evalDependencyNames(exprStack)
304
305def markupTraverse(expr, level = 0, root = True):
306    """Recursively process a dependency in infix form, transforming it into
307       asciidoctor markup with expression nesting indicated by indentation
308       level.
309
310       - expr - expression to process
311       - level - indentation level to render expression at
312       - root - True only on initial call"""
313
314    if level > 0:
315        prefix = '{nbsp}{nbsp}' * level * 2 + ' '
316    else:
317        prefix = ''
318    str = ''
319
320    for elem in expr:
321        if isinstance(elem, pp.ParseResults):
322            if not root:
323                nextlevel = level + 1
324            else:
325                # Do not indent the outer expression
326                nextlevel = level
327
328            str = str + markupTraverse(elem, level = nextlevel, root = False)
329        elif elem in ('+', ','):
330            str = str + f'{prefix}{opMarkupAsciidoc(elem)} +\n'
331        else:
332            str = str + f'{prefix}{leafMarkupAsciidoc(elem)} +\n'
333
334    return str
335
336def dependencyMarkup(dependency):
337    """Return asciidoctor markup for a human-readable equivalent of an API
338       dependency expression, suitable for use in extension appendix
339       metadata.
340
341     - dependency - the expression"""
342
343    parsed = dependencyExpr.parseString(dependency)
344    return markupTraverse(parsed)
345
346if __name__ == "__main__":
347
348    termdict = {
349        'VK_VERSION_1_1' : True,
350        'false' : False,
351        'true' : True,
352    }
353    termSupported = lambda name: name in termdict and termdict[name]
354
355    def test(dependency, expected):
356        val = False
357        try:
358            val = evaluateDependency(dependency, termSupported)
359        except ParseException as pe:
360            print(dependency, f'failed parse: {dependency}')
361        except Exception as e:
362            print(dependency, f'failed eval: {dependency}')
363
364        if val == expected:
365            True
366            # print(f'{dependency} = {val} (as expected)')
367        else:
368            print(f'{dependency} ERROR: {val} != {expected}')
369
370    # Verify expressions are evaluated left-to-right
371
372    test('false,false+false', False)
373    test('false,false+true', False)
374    test('false,true+false', False)
375    test('false,true+true', True)
376    test('true,false+false', False)
377    test('true,false+true', True)
378    test('true,true+false', False)
379    test('true,true+true', True)
380
381    test('false,(false+false)', False)
382    test('false,(false+true)', False)
383    test('false,(true+false)', False)
384    test('false,(true+true)', True)
385    test('true,(false+false)', True)
386    test('true,(false+true)', True)
387    test('true,(true+false)', True)
388    test('true,(true+true)', True)
389
390
391    test('false+false,false', False)
392    test('false+false,true', True)
393    test('false+true,false', False)
394    test('false+true,true', True)
395    test('true+false,false', False)
396    test('true+false,true', True)
397    test('true+true,false', True)
398    test('true+true,true', True)
399
400    test('false+(false,false)', False)
401    test('false+(false,true)', False)
402    test('false+(true,false)', False)
403    test('false+(true,true)', False)
404    test('true+(false,false)', False)
405    test('true+(false,true)', True)
406    test('true+(true,false)', True)
407    test('true+(true,true)', True)
408
409    # Check formatting
410    for dependency in [
411        #'true',
412        #'true+true+false',
413        'true+false',
414        'true+(true+false),(false,true)',
415        #'true+((true+false),(false,true))',
416        'VK_VERSION_1_0+VK_KHR_display',
417        #'VK_VERSION_1_1+(true,false)',
418    ]:
419        print(f'expr = {dependency}\n{dependencyMarkup(dependency)}')
420        print(f'  spec language = {dependencyLanguageSpecMacros(dependency)}')
421        print(f'  comment language = {dependencyLanguageComment(dependency)}')
422        print(f'  C language = {dependencyLanguageC(dependency)}')
423        print(f'  names = {dependencyNames(dependency)}')
424        print(f'  value = {evaluateDependency(dependency, termSupported)}')
425