1# Copyright (C) 2020 Red Hat Inc.
2#
3# Authors:
4#  Eduardo Habkost <ehabkost@redhat.com>
5#
6# This work is licensed under the terms of the GNU GPL, version 2.  See
7# the COPYING file in the top-level directory.
8import re
9from itertools import chain
10from typing import *
11
12from .regexps import *
13from .patching import *
14from .utils import *
15
16import logging
17logger = logging.getLogger(__name__)
18DBG = logger.debug
19INFO = logger.info
20WARN = logger.warning
21
22# simple expressions:
23
24RE_CONSTANT = OR(RE_STRING, RE_NUMBER)
25
26class ConstantDefine(FileMatch):
27    """Simple #define preprocessor directive for a constant"""
28    # if the macro contents are very simple, it might be included
29    # in the match group 'value'
30    regexp = S(r'^[ \t]*#[ \t]*define', CPP_SPACE, NAMED('name', RE_IDENTIFIER),
31               CPP_SPACE, NAMED('value', RE_CONSTANT), r'[ \t]*\n')
32
33    def provided_identifiers(self) -> Iterable[RequiredIdentifier]:
34        yield RequiredIdentifier('constant', self.group('name'))
35
36class TypeIdentifiers(NamedTuple):
37    """Type names found in type declarations"""
38    # TYPE_MYDEVICE
39    typename: Optional[str]
40    # MYDEVICE
41    uppercase: Optional[str] = None
42    # MyDevice
43    instancetype: Optional[str] = None
44    # MyDeviceClass
45    classtype: Optional[str] = None
46    # my_device
47    lowercase: Optional[str] = None
48
49    def allfields(self):
50        return tuple(getattr(self, f) for f in self._fields)
51
52    def merge(self, other: 'TypeIdentifiers') -> Optional['TypeIdentifiers']:
53        """Check if identifiers match, return new identifier with complete list"""
54        if any(not opt_compare(a, b) for a,b in zip(self, other)):
55            return None
56        return TypeIdentifiers(*(merge(a, b) for a,b in zip(self, other)))
57
58    def __str__(self) -> str:
59        values = ((f, getattr(self, f)) for f in self._fields)
60        s = ', '.join('%s=%s' % (f,v) for f,v in values if v is not None)
61        return f'{s}'
62
63    def check_consistency(self) -> List[str]:
64        """Check if identifiers are consistent with each other,
65        return list of problems (or empty list if everything seems consistent)
66        """
67        r = []
68        if self.typename is None:
69            r.append("typename (TYPE_MYDEVICE) is unavailable")
70
71        if self.uppercase is None:
72            r.append("uppercase name is unavailable")
73
74        if (self.instancetype is not None
75            and self.classtype is not None
76            and self.classtype != f'{self.instancetype}Class'):
77                r.append("class typedef %s doesn't match instance typedef %s" %
78                         (self.classtype, self.instancetype))
79
80        if (self.uppercase is not None
81            and self.typename is not None
82            and f'TYPE_{self.uppercase}' != self.typename):
83            r.append("uppercase name (%s) doesn't match type name (%s)" %
84                     (self.uppercase, self.typename))
85
86        return r
87
88class TypedefMatch(FileMatch):
89    """typedef declaration"""
90    def provided_identifiers(self) -> Iterable[RequiredIdentifier]:
91        yield RequiredIdentifier('type', self.group('name'))
92
93class SimpleTypedefMatch(TypedefMatch):
94    """Simple typedef declaration
95    (no replacement rules)"""
96    regexp = S(r'^[ \t]*typedef', SP,
97               NAMED('typedef_type', RE_TYPE), SP,
98               NAMED('name', RE_IDENTIFIER), r'\s*;[ \t]*\n')
99
100RE_MACRO_DEFINE = S(r'^[ \t]*#\s*define\s+', NAMED('name', RE_IDENTIFIER),
101                    r'\s*\(\s*', RE_IDENTIFIER, r'\s*\)', CPP_SPACE)
102
103RE_STRUCT_ATTRIBUTE = r'QEMU_PACKED'
104
105# This doesn't parse the struct definitions completely, it just assumes
106# the closing brackets are going to be in an unindented line:
107RE_FULL_STRUCT = S('struct', SP, M(RE_IDENTIFIER, n='?', name='structname'), SP,
108                   NAMED('body', r'{\n',
109                         # acceptable inside the struct body:
110                         # - lines starting with space or tab
111                         # - empty lines
112                         # - preprocessor directives
113                         # - comments
114                         OR(r'[ \t][^\n]*\n',
115                            r'#[^\n]*\n',
116                            r'\n',
117                            S(r'[ \t]*', RE_COMMENT, r'[ \t]*\n'),
118                            repeat='*?'),
119                         r'}', M(RE_STRUCT_ATTRIBUTE, SP, n='*')))
120RE_STRUCT_TYPEDEF = S(r'^[ \t]*typedef', SP, RE_FULL_STRUCT, SP,
121                      NAMED('name', RE_IDENTIFIER), r'\s*;[ \t]*\n')
122
123class FullStructTypedefMatch(TypedefMatch):
124    """typedef struct [SomeStruct] { ...} SomeType
125    Will be replaced by separate struct declaration + typedef
126    """
127    regexp = RE_STRUCT_TYPEDEF
128
129    def make_structname(self) -> str:
130        """Make struct name for struct+typedef split"""
131        name = self.group('structname')
132        if not name:
133            name = self.name
134        return name
135
136    def strip_typedef(self) -> Patch:
137        """generate patch that will strip typedef from the struct declartion
138
139        The caller is responsible for readding the typedef somewhere else.
140        """
141        name = self.make_structname()
142        body = self.group('body')
143        return self.make_patch(f'struct {name} {body};\n')
144
145    def make_simple_typedef(self) -> str:
146        structname = self.make_structname()
147        name = self.name
148        return f'typedef struct {structname} {name};\n'
149
150    def move_typedef(self, position) -> Iterator[Patch]:
151        """Generate patches to move typedef elsewhere"""
152        yield self.strip_typedef()
153        yield Patch(position, position, self.make_simple_typedef())
154
155    def split_typedef(self) -> Iterator[Patch]:
156        """Split into struct definition + typedef in-place"""
157        yield self.strip_typedef()
158        yield self.append(self.make_simple_typedef())
159
160class StructTypedefSplit(FullStructTypedefMatch):
161    """split struct+typedef declaration"""
162    def gen_patches(self) -> Iterator[Patch]:
163        if self.group('structname'):
164            yield from self.split_typedef()
165
166class DuplicatedTypedefs(SimpleTypedefMatch):
167    """Delete ALL duplicate typedefs (unsafe)"""
168    def gen_patches(self) -> Iterable[Patch]:
169        other_td = [td for td in chain(self.file.matches_of_type(SimpleTypedefMatch),
170                                       self.file.matches_of_type(FullStructTypedefMatch))
171                    if td.name == self.name]
172        DBG("other_td: %r", other_td)
173        if any(td.start() < self.start() for td in other_td):
174            # patch only if handling the first typedef
175            return
176        for td in other_td:
177            if isinstance(td, SimpleTypedefMatch):
178                DBG("other td: %r", td.match.groupdict())
179                if td.group('typedef_type') != self.group('typedef_type'):
180                    yield td.make_removal_patch()
181            elif isinstance(td, FullStructTypedefMatch):
182                DBG("other td: %r", td.match.groupdict())
183                if self.group('typedef_type') == 'struct '+td.group('structname'):
184                    yield td.strip_typedef()
185
186class QOMDuplicatedTypedefs(DuplicatedTypedefs):
187    """Delete duplicate typedefs if used by QOM type"""
188    def gen_patches(self) -> Iterable[Patch]:
189        qom_macros = [TypeCheckMacro, DeclareInstanceChecker, DeclareClassCheckers, DeclareObjCheckers]
190        qom_matches = chain(*(self.file.matches_of_type(t) for t in qom_macros))
191        in_use = any(RequiredIdentifier('type', self.name) in m.required_identifiers()
192                     for m in qom_matches)
193        if in_use:
194            yield from DuplicatedTypedefs.gen_patches(self)
195
196class QOMStructTypedefSplit(FullStructTypedefMatch):
197    """split struct+typedef declaration if used by QOM type"""
198    def gen_patches(self) -> Iterator[Patch]:
199        qom_macros = [TypeCheckMacro, DeclareInstanceChecker, DeclareClassCheckers, DeclareObjCheckers]
200        qom_matches = chain(*(self.file.matches_of_type(t) for t in qom_macros))
201        in_use = any(RequiredIdentifier('type', self.name) in m.required_identifiers()
202                     for m in qom_matches)
203        if in_use:
204            yield from self.split_typedef()
205
206def typedefs(file: FileInfo) -> Iterable[TypedefMatch]:
207    return (cast(TypedefMatch, m)
208            for m in chain(file.matches_of_type(SimpleTypedefMatch),
209                           file.matches_of_type(FullStructTypedefMatch)))
210
211def find_typedef(f: FileInfo, name: Optional[str]) -> Optional[TypedefMatch]:
212    if not name:
213        return None
214    for td in typedefs(f):
215        if td.name == name:
216            return td
217    return None
218
219CHECKER_MACROS = ['OBJECT_CHECK', 'OBJECT_CLASS_CHECK', 'OBJECT_GET_CLASS']
220CheckerMacroName = Literal['OBJECT_CHECK', 'OBJECT_CLASS_CHECK', 'OBJECT_GET_CLASS']
221
222RE_CHECK_MACRO = \
223    S(RE_MACRO_DEFINE,
224      OR(*CHECKER_MACROS, name='checker'),
225      M(r'\s*\(\s*', OR(NAMED('typedefname', RE_IDENTIFIER), RE_TYPE, name='c_type'), r'\s*,', CPP_SPACE,
226        OPTIONAL_PARS(RE_IDENTIFIER), r',', CPP_SPACE,
227        NAMED('qom_typename', RE_IDENTIFIER), r'\s*\)\n',
228        n='?', name='check_args'))
229
230EXPECTED_CHECKER_SUFFIXES: List[Tuple[CheckerMacroName, str]] = [
231    ('OBJECT_GET_CLASS', '_GET_CLASS'),
232    ('OBJECT_CLASS_CHECK', '_CLASS'),
233]
234
235class TypeCheckMacro(FileMatch):
236    """OBJECT_CHECK/OBJECT_CLASS_CHECK/OBJECT_GET_CLASS macro definitions
237    Will be replaced by DECLARE_*_CHECKERS macro
238    """
239    #TODO: handle and convert INTERFACE_CHECK macros
240    regexp = RE_CHECK_MACRO
241
242    @property
243    def checker(self) -> CheckerMacroName:
244        """Name of checker macro being used"""
245        return self.group('checker')
246
247    @property
248    def typedefname(self) -> Optional[str]:
249        return self.group('typedefname')
250
251    def find_typedef(self) -> Optional[TypedefMatch]:
252        return find_typedef(self.file, self.typedefname)
253
254    def sanity_check(self) -> None:
255        DBG("groups: %r", self.match.groups())
256        if not self.group('check_args'):
257            self.warn("type check macro not parsed completely: %s", self.name)
258            return
259        DBG("type identifiers: %r", self.type_identifiers)
260        if self.typedefname and self.find_typedef() is None:
261            self.warn("typedef used by %s not found", self.name)
262
263    def find_matching_macros(self) -> List['TypeCheckMacro']:
264        """Find other check macros that generate the same macro names
265
266        The returned list will always be sorted.
267        """
268        my_ids = self.type_identifiers
269        assert my_ids
270        return [m for m in self.file.matches_of_type(TypeCheckMacro)
271                if m.type_identifiers is not None
272                   and my_ids.uppercase is not None
273                   and (my_ids.uppercase == m.type_identifiers.uppercase
274                        or my_ids.typename == m.type_identifiers.typename)]
275
276    def merge_ids(self, matches: List['TypeCheckMacro']) -> Optional[TypeIdentifiers]:
277        """Try to merge info about type identifiers from all matches in a list"""
278        if not matches:
279            return None
280        r = matches[0].type_identifiers
281        if r is None:
282            return None
283        for m in matches[1:]:
284            assert m.type_identifiers
285            new = r.merge(m.type_identifiers)
286            if new is None:
287                self.warn("macro %s identifiers (%s) don't match macro %s (%s)",
288                          matches[0].name, r, m.name, m.type_identifiers)
289                return None
290            r = new
291        return r
292
293    def required_identifiers(self) -> Iterable[RequiredIdentifier]:
294        yield RequiredIdentifier('include', '"qom/object.h"')
295        if self.type_identifiers is None:
296            return
297        # to make sure typedefs will be moved above all related macros,
298        # return dependencies from all of them, not just this match
299        for m in self.find_matching_macros():
300            yield RequiredIdentifier('type', m.group('c_type'))
301            yield RequiredIdentifier('constant', m.group('qom_typename'))
302
303    @property
304    def type_identifiers(self) -> Optional[TypeIdentifiers]:
305        """Extract type identifier information from match"""
306        typename = self.group('qom_typename')
307        c_type = self.group('c_type')
308        if not typename or not c_type:
309            return None
310        typedef = self.group('typedefname')
311        classtype = None
312        instancetype = None
313        uppercase = None
314        expected_suffix = dict(EXPECTED_CHECKER_SUFFIXES).get(self.checker)
315
316        # here the available data depends on the checker macro being called:
317        # - we need to remove the suffix from the macro name
318        # - depending on the macro type, we know the class type name, or
319        #   the instance type name
320        if self.checker in ('OBJECT_GET_CLASS', 'OBJECT_CLASS_CHECK'):
321            classtype = c_type
322        elif self.checker == 'OBJECT_CHECK':
323            instancetype = c_type
324            uppercase = self.name
325        else:
326            assert False
327        if expected_suffix and self.name.endswith(expected_suffix):
328            uppercase = self.name[:-len(expected_suffix)]
329        return TypeIdentifiers(typename=typename, classtype=classtype,
330                               instancetype=instancetype, uppercase=uppercase)
331
332    def gen_patches(self) -> Iterable[Patch]:
333        if self.type_identifiers is None:
334            self.warn("couldn't extract type information from macro %s", self.name)
335            return
336
337        if self.name == 'INTERFACE_CLASS':
338            # INTERFACE_CLASS is special and won't be patched
339            return
340
341        for checker,suffix in EXPECTED_CHECKER_SUFFIXES:
342            if self.name.endswith(suffix):
343                if self.checker != checker:
344                    self.warn("macro %s is using macro %s instead of %s", self.name, self.checker, checker)
345                    return
346                break
347
348        matches = self.find_matching_macros()
349        DBG("found %d matching macros: %s", len(matches), ' '.join(m.name for m in matches))
350        # we will generate patches only when processing the first macro:
351        if matches[0].start != self.start:
352            DBG("skipping %s (will patch when handling %s)", self.name, matches[0].name)
353            return
354
355
356        ids = self.merge_ids(matches)
357        if ids is None:
358            DBG("type identifier mismatch, won't patch %s", self.name)
359            return
360
361        if not ids.uppercase:
362            self.warn("macro %s doesn't follow the expected name pattern", self.name)
363            return
364        if not ids.typename:
365            self.warn("macro %s: couldn't extract type name", self.name)
366            return
367
368        #issues = ids.check_consistency()
369        #if issues:
370        #    for i in issues:
371        #        self.warn("inconsistent identifiers: %s", i)
372
373        names = [n for n in (ids.instancetype, ids.classtype, ids.uppercase, ids.typename)
374                 if n is not None]
375        if len(set(names)) != len(names):
376            self.warn("duplicate names used by macro: %r", ids)
377            return
378
379        assert ids.classtype or ids.instancetype
380        assert ids.typename
381        assert ids.uppercase
382        if ids.classtype and ids.instancetype:
383            new_decl = (f'DECLARE_OBJ_CHECKERS({ids.instancetype}, {ids.classtype},\n'
384                        f'                     {ids.uppercase}, {ids.typename})\n')
385        elif ids.classtype:
386            new_decl = (f'DECLARE_CLASS_CHECKERS({ids.classtype}, {ids.uppercase},\n'
387                        f'                       {ids.typename})\n')
388        elif ids.instancetype:
389            new_decl = (f'DECLARE_INSTANCE_CHECKER({ids.instancetype}, {ids.uppercase},\n'
390                        f'                         {ids.typename})\n')
391        else:
392            assert False
393
394        # we need to ensure the typedefs are already available
395        issues = []
396        for t in [ids.instancetype, ids.classtype]:
397            if not t:
398                continue
399            if re.fullmatch(RE_STRUCT_TYPE, t):
400                self.info("type %s is not a typedef", t)
401                continue
402            td = find_typedef(self.file, t)
403            #if not td and self.allfiles.find_file('include/qemu/typedefs.h'):
404            #
405            if not td:
406                # it is OK if the typedef is in typedefs.h
407                f = self.allfiles.find_file('include/qemu/typedefs.h')
408                if f and find_typedef(f, t):
409                    self.info("typedef %s found in typedefs.h", t)
410                    continue
411
412                issues.append("couldn't find typedef %s" % (t))
413            elif td.start() > self.start():
414                issues.append("typedef %s need to be moved earlier in the file" % (td.name))
415
416        for issue in issues:
417            self.warn(issue)
418
419        if issues and not self.file.force:
420            return
421
422        # delete all matching macros and add new declaration:
423        for m in matches:
424            yield m.make_patch('')
425        for issue in issues:
426            yield self.prepend("/* FIXME: %s */\n" % (issue))
427        yield self.append(new_decl)
428
429class DeclareInstanceChecker(FileMatch):
430    """DECLARE_INSTANCE_CHECKER use
431    Will be replaced with DECLARE_OBJ_CHECKERS if possible
432    """
433    #TODO: replace lonely DECLARE_INSTANCE_CHECKER with DECLARE_OBJ_CHECKERS
434    #      if all types are found.
435    #      This will require looking up the correct class type in the TypeInfo
436    #      structs in another file
437    regexp = S(r'^[ \t]*DECLARE_INSTANCE_CHECKER\s*\(\s*',
438               NAMED('instancetype', RE_TYPE), r'\s*,\s*',
439               NAMED('uppercase', RE_IDENTIFIER), r'\s*,\s*',
440               OR(RE_IDENTIFIER, RE_STRING, RE_MACRO_CONCAT, RE_FUN_CALL, name='typename'), SP,
441               r'\)[ \t]*;?[ \t]*\n')
442
443    def required_identifiers(self) -> Iterable[RequiredIdentifier]:
444        yield RequiredIdentifier('include', '"qom/object.h"')
445        yield RequiredIdentifier('constant', self.group('typename'))
446        yield RequiredIdentifier('type', self.group('instancetype'))
447
448class DeclareClassCheckers(FileMatch):
449    """DECLARE_INSTANCE_CHECKER use"""
450    regexp = S(r'^[ \t]*DECLARE_CLASS_CHECKERS\s*\(\s*',
451               NAMED('classtype', RE_TYPE), r'\s*,\s*',
452               NAMED('uppercase', RE_IDENTIFIER), r'\s*,\s*',
453               OR(RE_IDENTIFIER, RE_STRING, RE_MACRO_CONCAT, RE_FUN_CALL, name='typename'), SP,
454               r'\)[ \t]*;?[ \t]*\n')
455
456    def required_identifiers(self) -> Iterable[RequiredIdentifier]:
457        yield RequiredIdentifier('include', '"qom/object.h"')
458        yield RequiredIdentifier('constant', self.group('typename'))
459        yield RequiredIdentifier('type', self.group('classtype'))
460
461class DeclareObjCheckers(FileMatch):
462    """DECLARE_OBJ_CHECKERS use
463    Will be replaced with OBJECT_DECLARE_TYPE if possible
464    """
465    #TODO: detect when OBJECT_DECLARE_SIMPLE_TYPE can be used
466    regexp = S(r'^[ \t]*DECLARE_OBJ_CHECKERS\s*\(\s*',
467               NAMED('instancetype', RE_TYPE), r'\s*,\s*',
468               NAMED('classtype', RE_TYPE), r'\s*,\s*',
469               NAMED('uppercase', RE_IDENTIFIER), r'\s*,\s*',
470               OR(RE_IDENTIFIER, RE_STRING, RE_MACRO_CONCAT, RE_FUN_CALL, name='typename'), SP,
471               r'\)[ \t]*;?[ \t]*\n')
472
473    def required_identifiers(self) -> Iterable[RequiredIdentifier]:
474        yield RequiredIdentifier('include', '"qom/object.h"')
475        yield RequiredIdentifier('constant', self.group('typename'))
476        yield RequiredIdentifier('type', self.group('classtype'))
477        yield RequiredIdentifier('type', self.group('instancetype'))
478
479    def gen_patches(self):
480        ids = TypeIdentifiers(uppercase=self.group('uppercase'),
481                              typename=self.group('typename'),
482                              classtype=self.group('classtype'),
483                              instancetype=self.group('instancetype'))
484        issues = ids.check_consistency()
485        if issues:
486            for i in issues:
487                self.warn("inconsistent identifiers: %s", i)
488            return
489
490        if self.group('typename') != 'TYPE_'+self.group('uppercase'):
491            self.warn("type %s mismatch with uppercase name %s", ids.typename, ids.uppercase)
492            return
493
494        typedefs = [(t,self.file.find_match(SimpleTypedefMatch, t))
495                    for t in (ids.instancetype, ids.classtype)]
496        for t,td in typedefs:
497            if td is None:
498                self.warn("typedef %s not found", t)
499                break
500            if td.start() > self.start():
501                self.warn("typedef %s needs to be move earlier in the file", t)
502                break
503            #HACK: check if typedef is used between its definition and the macro
504            #TODO: check if the only match is inside the "struct { ... }" declaration
505            if re.search(r'\b'+t+r'\b', self.file.original_content[td.end():self.start()]):
506                self.warn("typedef %s can't be moved, it is used before the macro", t)
507                break
508        else:
509            for t,td in typedefs:
510                yield td.make_removal_patch()
511
512            lowercase = ids.uppercase.lower()
513            # all is OK, we can replace the macro!
514            c = (f'OBJECT_DECLARE_TYPE({ids.instancetype}, {ids.classtype},\n'
515                 f'                    {lowercase}, {ids.uppercase})\n')
516            yield self.make_patch(c)
517
518class TrivialClassStruct(FileMatch):
519    """Trivial class struct"""
520    regexp = S(r'^[ \t]*struct\s*', NAMED('name', RE_IDENTIFIER),
521               r'\s*{\s*', NAMED('parent_struct', RE_IDENTIFIER), r'\s*parent(_class)?\s*;\s*};\n')
522
523class DeclareTypeName(FileMatch):
524    """DECLARE_TYPE_NAME usage"""
525    regexp = S(r'^[ \t]*DECLARE_TYPE_NAME\s*\(',
526               NAMED('uppercase', RE_IDENTIFIER), r'\s*,\s*',
527               OR(RE_IDENTIFIER, RE_STRING, RE_MACRO_CONCAT, RE_FUN_CALL, name='typename'),
528               r'\s*\);?[ \t]*\n')
529
530class ObjectDeclareType(FileMatch):
531    """OBJECT_DECLARE_TYPE usage
532    Will be replaced with OBJECT_DECLARE_SIMPLE_TYPE if possible
533    """
534    regexp = S(r'^[ \t]*OBJECT_DECLARE_TYPE\s*\(',
535               NAMED('instancetype', RE_TYPE), r'\s*,\s*',
536               NAMED('classtype', RE_TYPE), r'\s*,\s*',
537               NAMED('lowercase', RE_IDENTIFIER), r'\s*,\s*',
538               NAMED('uppercase', RE_IDENTIFIER), SP,
539               r'\)[ \t]*;?[ \t]*\n')
540
541    def gen_patches(self):
542        DBG("groups: %r", self.match.groupdict())
543        trivial_struct = self.file.find_match(TrivialClassStruct, self.group('classtype'))
544        if trivial_struct:
545            d = self.match.groupdict().copy()
546            d['parent_struct'] = trivial_struct.group("parent_struct")
547            yield trivial_struct.make_removal_patch()
548            c = ("OBJECT_DECLARE_SIMPLE_TYPE(%(instancetype)s, %(lowercase)s,\n"
549                 "                           %(uppercase)s, %(parent_struct)s)\n" % d)
550            yield self.make_patch(c)
551
552def find_type_declaration(files: FileList, typename: str) -> Optional[FileMatch]:
553    """Find usage of DECLARE*CHECKER macro"""
554    for c in (DeclareInstanceChecker, DeclareClassCheckers, DeclareObjCheckers, DeclareTypeName):
555        d = files.find_match(c, name=typename, group='typename')
556        if d:
557            return d
558    return None
559
560
561class Include(FileMatch):
562    """#include directive"""
563    regexp = RE_INCLUDE
564    def provided_identifiers(self) -> Iterable[RequiredIdentifier]:
565        yield RequiredIdentifier('include', self.group('includepath'))
566
567class InitialIncludes(FileMatch):
568    """Initial #include block"""
569    regexp = S(RE_FILE_BEGIN,
570               M(SP, RE_COMMENTS,
571                 r'^[ \t]*#[ \t]*ifndef[ \t]+', RE_IDENTIFIER, r'[ \t]*\n',
572                 n='?', name='ifndef_block'),
573               M(SP, RE_COMMENTS,
574                 OR(RE_INCLUDE, RE_SIMPLEDEFINE),
575                 n='*', name='includes'))
576
577class SymbolUserList(NamedTuple):
578    definitions: List[FileMatch]
579    users: List[FileMatch]
580
581class MoveSymbols(FileMatch):
582    """Handle missing symbols
583    - Move typedefs and defines when necessary
584    - Add missing #include lines when necessary
585    """
586    regexp = RE_FILE_BEGIN
587
588    def gen_patches(self) -> Iterator[Patch]:
589        index: Dict[RequiredIdentifier, SymbolUserList] = {}
590        definition_classes = [SimpleTypedefMatch, FullStructTypedefMatch, ConstantDefine, Include]
591        user_classes = [TypeCheckMacro, DeclareObjCheckers, DeclareInstanceChecker, DeclareClassCheckers]
592
593        # first we scan for all symbol definitions and usage:
594        for dc in definition_classes:
595            defs = self.file.matches_of_type(dc)
596            for d in defs:
597                DBG("scanning %r", d)
598                for i in d.provided_identifiers():
599                    index.setdefault(i, SymbolUserList([], [])).definitions.append(d)
600        DBG("index: %r", list(index.keys()))
601        for uc in user_classes:
602            users = self.file.matches_of_type(uc)
603            for u in users:
604                for i in u.required_identifiers():
605                    index.setdefault(i, SymbolUserList([], [])).users.append(u)
606
607        # validate all symbols:
608        for i,ul in index.items():
609            if not ul.users:
610                # unused symbol
611                continue
612
613            # symbol not defined
614            if len(ul.definitions) == 0:
615                if i.type == 'include':
616                   includes, = self.file.matches_of_type(InitialIncludes)
617                   #FIXME: don't do this if we're already inside qom/object.h
618                   yield includes.append(f'#include {i.name}\n')
619                else:
620                    u.warn("definition of %s %s not found in file", i.type, i.name)
621                continue
622
623            # symbol defined twice:
624            if len(ul.definitions) > 1:
625                ul.definitions[1].warn("%s defined twice", i.name)
626                ul.definitions[0].warn("previously defined here")
627                continue
628
629            # symbol defined.  check if all users are after its definition:
630            assert len(ul.definitions) == 1
631            definition = ul.definitions[0]
632            DBG("handling repositioning of %r", definition)
633            earliest = min(ul.users, key=lambda u: u.start())
634            if earliest.start() > definition.start():
635                DBG("%r is OK", definition)
636                continue
637
638            DBG("%r needs to be moved", definition)
639            if isinstance(definition, SimpleTypedefMatch) \
640               or isinstance(definition, ConstantDefine):
641                # simple typedef or define can be moved directly:
642                yield definition.make_removal_patch()
643                yield earliest.prepend(definition.group(0))
644            elif isinstance(definition, FullStructTypedefMatch) \
645                 and definition.group('structname'):
646                # full struct typedef is more complex: we need to remove
647                # the typedef
648                yield from definition.move_typedef(earliest.start())
649            else:
650                definition.warn("definition of %s %s needs to be moved earlier in the file", i.type, i.name)
651                earliest.warn("definition of %s %s is used here", i.type, i.name)
652
653