1#!/usr/bin/env python3
2
3from __future__ import print_function
4
5import argparse
6import collections
7import copy
8import csv
9import itertools
10import json
11import os
12import re
13import shutil
14import stat
15import struct
16import sys
17
18
19#------------------------------------------------------------------------------
20# Python 2 and 3 Compatibility Layer
21#------------------------------------------------------------------------------
22
23if sys.version_info >= (3, 0):
24    from os import makedirs
25    from mmap import ACCESS_READ, mmap
26else:
27    from mmap import ACCESS_READ, mmap
28
29    def makedirs(path, exist_ok):
30        if exist_ok and os.path.isdir(path):
31            return
32        return os.makedirs(path)
33
34    class mmap(mmap):
35        def __enter__(self):
36            return self
37
38        def __exit__(self, exc, value, tb):
39            self.close()
40
41        def __getitem__(self, key):
42            res = super(mmap, self).__getitem__(key)
43            if type(key) == int:
44                return ord(res)
45            return res
46
47    FileNotFoundError = OSError
48
49try:
50    from sys import intern
51except ImportError:
52    pass
53
54
55#------------------------------------------------------------------------------
56# Collections
57#------------------------------------------------------------------------------
58
59def defaultnamedtuple(typename, field_names, default):
60    """Create a namedtuple type with default values.
61
62    This function creates a namedtuple type which will fill in default value
63    when actual arguments to the constructor were omitted.
64
65    >>> Point = defaultnamedtuple('Point', ['x', 'y'], 0)
66    >>> Point()
67    Point(x=0, y=0)
68    >>> Point(1)
69    Point(x=1, y=0)
70    >>> Point(1, 2)
71    Point(x=1, y=2)
72    >>> Point(x=1, y=2)
73    Point(x=1, y=2)
74    >>> Point(y=2, x=1)
75    Point(x=1, y=2)
76
77    >>> PermSet = defaultnamedtuple('PermSet', 'allowed disallowed', set())
78    >>> s = PermSet()
79    >>> s
80    PermSet(allowed=set(), disallowed=set())
81    >>> s.allowed is not s.disallowed
82    True
83    >>> PermSet({1})
84    PermSet(allowed={1}, disallowed=set())
85    >>> PermSet({1}, {2})
86    PermSet(allowed={1}, disallowed={2})
87    """
88
89    if isinstance(field_names, str):
90        field_names = field_names.replace(',', ' ').split()
91    field_names = list(map(str, field_names))
92    num_fields = len(field_names)
93
94    base_cls = collections.namedtuple(typename, field_names)
95    def __new__(cls, *args, **kwargs):
96        args = list(args)
97        for i in range(len(args), num_fields):
98            arg = kwargs.get(field_names[i])
99            if arg:
100                args.append(arg)
101            else:
102                args.append(copy.copy(default))
103        return base_cls.__new__(cls, *args)
104    return type(typename, (base_cls,), {'__new__': __new__})
105
106
107#------------------------------------------------------------------------------
108# ELF Parser
109#------------------------------------------------------------------------------
110
111Elf_Hdr = collections.namedtuple(
112        'Elf_Hdr',
113        'ei_class ei_data ei_version ei_osabi e_type e_machine e_version '
114        'e_entry e_phoff e_shoff e_flags e_ehsize e_phentsize e_phnum '
115        'e_shentsize e_shnum e_shstridx')
116
117
118Elf_Shdr = collections.namedtuple(
119        'Elf_Shdr',
120        'sh_name sh_type sh_flags sh_addr sh_offset sh_size sh_link sh_info '
121        'sh_addralign sh_entsize')
122
123
124Elf_Dyn = collections.namedtuple('Elf_Dyn', 'd_tag d_val')
125
126
127class Elf_Sym(collections.namedtuple(
128    'ELF_Sym', 'st_name st_value st_size st_info st_other st_shndx')):
129
130    STB_LOCAL = 0
131    STB_GLOBAL = 1
132    STB_WEAK = 2
133
134    SHN_UNDEF = 0
135
136    @property
137    def st_bind(self):
138        return (self.st_info >> 4)
139
140    @property
141    def is_local(self):
142        return self.st_bind == Elf_Sym.STB_LOCAL
143
144    @property
145    def is_global(self):
146        return self.st_bind == Elf_Sym.STB_GLOBAL
147
148    @property
149    def is_weak(self):
150        return self.st_bind == Elf_Sym.STB_WEAK
151
152    @property
153    def is_undef(self):
154        return self.st_shndx == Elf_Sym.SHN_UNDEF
155
156
157class ELFError(ValueError):
158    pass
159
160
161class ELF(object):
162    # ELF file format constants.
163    ELF_MAGIC = b'\x7fELF'
164
165    EI_CLASS = 4
166    EI_DATA = 5
167
168    ELFCLASSNONE = 0
169    ELFCLASS32 = 1
170    ELFCLASS64 = 2
171
172    ELFDATANONE = 0
173    ELFDATA2LSB = 1
174    ELFDATA2MSB = 2
175
176    DT_NEEDED = 1
177    DT_RPATH = 15
178    DT_RUNPATH = 29
179
180    _ELF_CLASS_NAMES = {
181        ELFCLASS32: '32',
182        ELFCLASS64: '64',
183    }
184
185    _ELF_DATA_NAMES = {
186        ELFDATA2LSB: 'Little-Endian',
187        ELFDATA2MSB: 'Big-Endian',
188    }
189
190    _ELF_MACHINE_IDS = {
191        0: 'EM_NONE',
192        3: 'EM_386',
193        8: 'EM_MIPS',
194        40: 'EM_ARM',
195        62: 'EM_X86_64',
196        183: 'EM_AARCH64',
197    }
198
199
200    @staticmethod
201    def _dict_find_key_by_value(d, dst):
202        for key, value in d.items():
203            if value == dst:
204                return key
205        raise KeyError(dst)
206
207    @staticmethod
208    def get_ei_class_from_name(name):
209        return ELF._dict_find_key_by_value(ELF._ELF_CLASS_NAMES, name)
210
211    @staticmethod
212    def get_ei_data_from_name(name):
213        return ELF._dict_find_key_by_value(ELF._ELF_DATA_NAMES, name)
214
215    @staticmethod
216    def get_e_machine_from_name(name):
217        return ELF._dict_find_key_by_value(ELF._ELF_MACHINE_IDS, name)
218
219
220    __slots__ = ('ei_class', 'ei_data', 'e_machine', 'dt_rpath', 'dt_runpath',
221                 'dt_needed', 'exported_symbols', 'imported_symbols',)
222
223
224    def __init__(self, ei_class=ELFCLASSNONE, ei_data=ELFDATANONE, e_machine=0,
225                 dt_rpath=None, dt_runpath=None, dt_needed=None,
226                 exported_symbols=None, imported_symbols=None):
227        self.ei_class = ei_class
228        self.ei_data = ei_data
229        self.e_machine = e_machine
230        self.dt_rpath = dt_rpath if dt_rpath is not None else []
231        self.dt_runpath = dt_runpath if dt_runpath is not None else []
232        self.dt_needed = dt_needed if dt_needed is not None else []
233        self.exported_symbols = \
234                exported_symbols if exported_symbols is not None else set()
235        self.imported_symbols = \
236                imported_symbols if imported_symbols is not None else set()
237
238    def __repr__(self):
239        args = (a + '=' + repr(getattr(self, a)) for a in self.__slots__)
240        return 'ELF(' + ', '.join(args) + ')'
241
242    def __eq__(self, rhs):
243        return all(getattr(self, a) == getattr(rhs, a) for a in self.__slots__)
244
245    @property
246    def elf_class_name(self):
247        return self._ELF_CLASS_NAMES.get(self.ei_class, 'None')
248
249    @property
250    def elf_data_name(self):
251        return self._ELF_DATA_NAMES.get(self.ei_data, 'None')
252
253    @property
254    def elf_machine_name(self):
255        return self._ELF_MACHINE_IDS.get(self.e_machine, str(self.e_machine))
256
257    @property
258    def is_32bit(self):
259        return self.ei_class == ELF.ELFCLASS32
260
261    @property
262    def is_64bit(self):
263        return self.ei_class == ELF.ELFCLASS64
264
265    @property
266    def sorted_exported_symbols(self):
267        return sorted(list(self.exported_symbols))
268
269    @property
270    def sorted_imported_symbols(self):
271        return sorted(list(self.imported_symbols))
272
273    def dump(self, file=None):
274        """Print parsed ELF information to the file"""
275        file = file if file is not None else sys.stdout
276
277        print('EI_CLASS\t' + self.elf_class_name, file=file)
278        print('EI_DATA\t\t' + self.elf_data_name, file=file)
279        print('E_MACHINE\t' + self.elf_machine_name, file=file)
280        for dt_rpath in self.dt_rpath:
281            print('DT_RPATH\t' + dt_rpath, file=file)
282        for dt_runpath in self.dt_runpath:
283            print('DT_RUNPATH\t' + dt_runpath, file=file)
284        for dt_needed in self.dt_needed:
285            print('DT_NEEDED\t' + dt_needed, file=file)
286        for symbol in self.sorted_exported_symbols:
287            print('EXP_SYMBOL\t' + symbol, file=file)
288        for symbol in self.sorted_imported_symbols:
289            print('IMP_SYMBOL\t' + symbol, file=file)
290
291    # Extract zero-terminated buffer slice.
292    def _extract_zero_terminated_buf_slice(self, buf, offset):
293        """Extract a zero-terminated buffer slice from the given offset"""
294        end = buf.find(b'\0', offset)
295        if end == -1:
296            return buf[offset:]
297        return buf[offset:end]
298
299    # Extract c-style interned string from the buffer.
300    if sys.version_info >= (3, 0):
301        def _extract_zero_terminated_str(self, buf, offset):
302            """Extract a c-style string from the given buffer and offset"""
303            buf_slice = self._extract_zero_terminated_buf_slice(buf, offset)
304            return intern(buf_slice.decode('utf-8'))
305    else:
306        def _extract_zero_terminated_str(self, buf, offset):
307            """Extract a c-style string from the given buffer and offset"""
308            return intern(self._extract_zero_terminated_buf_slice(buf, offset))
309
310    def _parse_from_buf_internal(self, buf):
311        """Parse ELF image resides in the buffer"""
312
313        # Check ELF ident.
314        if buf.size() < 8:
315            raise ELFError('bad ident')
316
317        if buf[0:4] != ELF.ELF_MAGIC:
318            raise ELFError('bad magic')
319
320        self.ei_class = buf[ELF.EI_CLASS]
321        if self.ei_class not in (ELF.ELFCLASS32, ELF.ELFCLASS64):
322            raise ELFError('unknown word size')
323
324        self.ei_data = buf[ELF.EI_DATA]
325        if self.ei_data not in (ELF.ELFDATA2LSB, ELF.ELFDATA2MSB):
326            raise ELFError('unknown endianness')
327
328        # ELF structure definitions.
329        endian_fmt = '<' if self.ei_data == ELF.ELFDATA2LSB else '>'
330
331        if self.is_32bit:
332            elf_hdr_fmt = endian_fmt + '4x4B8xHHLLLLLHHHHHH'
333            elf_shdr_fmt = endian_fmt + 'LLLLLLLLLL'
334            elf_dyn_fmt = endian_fmt + 'lL'
335            elf_sym_fmt = endian_fmt + 'LLLBBH'
336        else:
337            elf_hdr_fmt = endian_fmt + '4x4B8xHHLQQQLHHHHHH'
338            elf_shdr_fmt = endian_fmt + 'LLQQQQLLQQ'
339            elf_dyn_fmt = endian_fmt + 'QQ'
340            elf_sym_fmt = endian_fmt + 'LBBHQQ'
341
342        def parse_struct(cls, fmt, offset, error_msg):
343            try:
344                return cls._make(struct.unpack_from(fmt, buf, offset))
345            except struct.error:
346                raise ELFError(error_msg)
347
348        def parse_elf_hdr(offset):
349            return parse_struct(Elf_Hdr, elf_hdr_fmt, offset, 'bad elf header')
350
351        def parse_elf_shdr(offset):
352            return parse_struct(Elf_Shdr, elf_shdr_fmt, offset,
353                                'bad section header')
354
355        def parse_elf_dyn(offset):
356            return parse_struct(Elf_Dyn, elf_dyn_fmt, offset,
357                                'bad .dynamic entry')
358
359        if self.is_32bit:
360            def parse_elf_sym(offset):
361                return parse_struct(Elf_Sym, elf_sym_fmt, offset, 'bad elf sym')
362        else:
363            def parse_elf_sym(offset):
364                try:
365                    p = struct.unpack_from(elf_sym_fmt, buf, offset)
366                    return Elf_Sym(p[0], p[4], p[5], p[1], p[2], p[3])
367                except struct.error:
368                    raise ELFError('bad elf sym')
369
370        def extract_str(offset):
371            return self._extract_zero_terminated_str(buf, offset)
372
373        # Parse ELF header.
374        header = parse_elf_hdr(0)
375        self.e_machine = header.e_machine
376
377        # Check section header size.
378        if header.e_shentsize == 0:
379            raise ELFError('no section header')
380
381        # Find .shstrtab section.
382        shstrtab_shdr_off = \
383                header.e_shoff + header.e_shstridx * header.e_shentsize
384        shstrtab_shdr = parse_elf_shdr(shstrtab_shdr_off)
385        shstrtab_off = shstrtab_shdr.sh_offset
386
387        # Parse ELF section header.
388        sections = dict()
389        header_end = header.e_shoff + header.e_shnum * header.e_shentsize
390        for shdr_off in range(header.e_shoff, header_end, header.e_shentsize):
391            shdr = parse_elf_shdr(shdr_off)
392            name = extract_str(shstrtab_off + shdr.sh_name)
393            sections[name] = shdr
394
395        # Find .dynamic and .dynstr section header.
396        dynamic_shdr = sections.get('.dynamic')
397        if not dynamic_shdr:
398            raise ELFError('no .dynamic section')
399
400        dynstr_shdr = sections.get('.dynstr')
401        if not dynstr_shdr:
402            raise ELFError('no .dynstr section')
403
404        dynamic_off = dynamic_shdr.sh_offset
405        dynstr_off = dynstr_shdr.sh_offset
406
407        # Parse entries in .dynamic section.
408        assert struct.calcsize(elf_dyn_fmt) == dynamic_shdr.sh_entsize
409        dynamic_end = dynamic_off + dynamic_shdr.sh_size
410        for ent_off in range(dynamic_off, dynamic_end, dynamic_shdr.sh_entsize):
411            ent = parse_elf_dyn(ent_off)
412            if ent.d_tag == ELF.DT_NEEDED:
413                self.dt_needed.append(extract_str(dynstr_off + ent.d_val))
414            elif ent.d_tag == ELF.DT_RPATH:
415                self.dt_rpath.extend(
416                        extract_str(dynstr_off + ent.d_val).split(':'))
417            elif ent.d_tag == ELF.DT_RUNPATH:
418                self.dt_runpath.extend(
419                        extract_str(dynstr_off + ent.d_val).split(':'))
420
421        # Parse exported symbols in .dynsym section.
422        dynsym_shdr = sections.get('.dynsym')
423        if dynsym_shdr:
424            exp_symbols = self.exported_symbols
425            imp_symbols = self.imported_symbols
426
427            dynsym_off = dynsym_shdr.sh_offset
428            dynsym_end = dynsym_off + dynsym_shdr.sh_size
429            dynsym_entsize = dynsym_shdr.sh_entsize
430
431            # Skip first symbol entry (null symbol).
432            dynsym_off += dynsym_entsize
433
434            for ent_off in range(dynsym_off, dynsym_end, dynsym_entsize):
435                ent = parse_elf_sym(ent_off)
436                symbol_name = extract_str(dynstr_off + ent.st_name)
437                if ent.is_undef:
438                    imp_symbols.add(symbol_name)
439                elif not ent.is_local:
440                    exp_symbols.add(symbol_name)
441
442    def _parse_from_buf(self, buf):
443        """Parse ELF image resides in the buffer"""
444        try:
445            self._parse_from_buf_internal(buf)
446        except IndexError:
447            raise ELFError('bad offset')
448
449    def _parse_from_file(self, path):
450        """Parse ELF image from the file path"""
451        with open(path, 'rb') as f:
452            st = os.fstat(f.fileno())
453            if not st.st_size:
454                raise ELFError('empty file')
455            with mmap(f.fileno(), st.st_size, access=ACCESS_READ) as image:
456                self._parse_from_buf(image)
457
458    def _parse_from_dump_lines(self, path, lines):
459        patt = re.compile('^([A-Za-z_]+)\t+(.*)$')
460        for line_no, line in enumerate(lines):
461            match = patt.match(line)
462            if not match:
463                print('error: {}: {}: failed to parse'
464                        .format(path, line_no + 1), file=sys.stderr)
465                continue
466            key = match.group(1)
467            value = match.group(2)
468
469            if key == 'EI_CLASS':
470                self.ei_class = ELF.get_ei_class_from_name(value)
471            elif key == 'EI_DATA':
472                self.ei_data = ELF.get_ei_data_from_name(value)
473            elif key == 'E_MACHINE':
474                self.e_machine = ELF.get_e_machine_from_name(value)
475            elif key == 'DT_RPATH':
476                self.dt_rpath.append(intern(value))
477            elif key == 'DT_RUNPATH':
478                self.dt_runpath.append(intern(value))
479            elif key == 'DT_NEEDED':
480                self.dt_needed.append(intern(value))
481            elif key == 'EXP_SYMBOL':
482                self.exported_symbols.add(intern(value))
483            elif key == 'IMP_SYMBOL':
484                self.imported_symbols.add(intern(value))
485            else:
486                print('error: {}: {}: unknown tag name: {}'
487                        .format(path, line_no + 1, key), file=sys.stderr)
488
489    def _parse_from_dump_file(self, path):
490        """Load information from ELF dump file."""
491        with open(path, 'r') as f:
492            self._parse_from_dump_lines(path, f)
493
494    def _parse_from_dump_buf(self, buf):
495        """Load information from ELF dump buffer."""
496        self._parse_from_dump_lines('<str:0x{:x}>'.format(id(buf)),
497                                    buf.splitlines())
498
499    @staticmethod
500    def load(path):
501        """Create an ELF instance from the file path"""
502        elf = ELF()
503        elf._parse_from_file(path)
504        return elf
505
506    @staticmethod
507    def loads(buf):
508        """Create an ELF instance from the buffer"""
509        elf = ELF()
510        elf._parse_from_buf(buf)
511        return elf
512
513    @staticmethod
514    def load_dump(path):
515        """Create an ELF instance from a dump file path"""
516        elf = ELF()
517        elf._parse_from_dump_file(path)
518        return elf
519
520    @staticmethod
521    def load_dumps(buf):
522        """Create an ELF instance from a dump file buffer"""
523        elf = ELF()
524        elf._parse_from_dump_buf(buf)
525        return elf
526
527
528#------------------------------------------------------------------------------
529# NDK and Banned Libraries
530#------------------------------------------------------------------------------
531
532class NDKLibDict(object):
533    NOT_NDK = 0
534    LL_NDK = 1
535    SP_NDK = 2
536    HL_NDK = 3
537
538    LL_NDK_LIB_NAMES = (
539        'libc.so',
540        'libdl.so',
541        'liblog.so',
542        'libm.so',
543        'libstdc++.so',
544        'libvndksupport.so',
545        'libandroid_net.so',
546        'libz.so',
547    )
548
549    SP_NDK_LIB_NAMES = (
550        'libEGL.so',
551        'libGLESv1_CM.so',
552        'libGLESv2.so',
553        'libGLESv3.so',
554        'libnativewindow.so',
555        'libsync.so',
556        'libvulkan.so',
557    )
558
559    HL_NDK_LIB_NAMES = (
560        'libOpenMAXAL.so',
561        'libOpenSLES.so',
562        'libandroid.so',
563        'libcamera2ndk.so',
564        'libjnigraphics.so',
565        'libmediandk.so',
566    )
567
568    @staticmethod
569    def _create_pattern(names):
570        return '|'.join('(?:^\\/system\\/lib(?:64)?\\/' + re.escape(i) + '$)'
571                        for i in names)
572
573    @staticmethod
574    def _compile_path_matcher(names):
575        return re.compile(NDKLibDict._create_pattern(names))
576
577    @staticmethod
578    def _compile_multi_path_matcher(name_lists):
579        patt = '|'.join('(' + NDKLibDict._create_pattern(names) + ')'
580                        for names in name_lists)
581        return re.compile(patt)
582
583    def __init__(self):
584        self.ll_ndk_patterns = self._compile_path_matcher(self.LL_NDK_LIB_NAMES)
585        self.sp_ndk_patterns = self._compile_path_matcher(self.SP_NDK_LIB_NAMES)
586        self.hl_ndk_patterns = self._compile_path_matcher(self.HL_NDK_LIB_NAMES)
587        self.ndk_patterns = self._compile_multi_path_matcher(
588                (self.LL_NDK_LIB_NAMES, self.SP_NDK_LIB_NAMES,
589                 self.HL_NDK_LIB_NAMES))
590
591    def is_ll_ndk(self, path):
592        return self.ll_ndk_patterns.match(path)
593
594    def is_sp_ndk(self, path):
595        return self.sp_ndk_patterns.match(path)
596
597    def is_hl_ndk(self, path):
598        return self.hl_ndk_patterns.match(path)
599
600    def is_ndk(self, path):
601        return self.ndk_patterns.match(path)
602
603    def classify(self, path):
604        match = self.ndk_patterns.match(path)
605        if not match:
606            return 0
607        return match.lastindex
608
609NDK_LIBS = NDKLibDict()
610
611
612BannedLib = collections.namedtuple(
613        'BannedLib', ('name', 'reason', 'action',))
614
615BA_WARN = 0
616BA_EXCLUDE = 1
617
618class BannedLibDict(object):
619    def __init__(self):
620        self.banned_libs = dict()
621
622    def add(self, name, reason, action):
623        self.banned_libs[name] = BannedLib(name, reason, action)
624
625    def get(self, name):
626        return self.banned_libs.get(name)
627
628    def is_banned(self, path):
629        return self.get(os.path.basename(path))
630
631    @staticmethod
632    def create_default():
633        d = BannedLibDict()
634        d.add('libbinder.so', 'un-versioned IPC', BA_WARN)
635        d.add('libselinux.so', 'policydb might be incompatible', BA_WARN)
636        return d
637
638
639#------------------------------------------------------------------------------
640# ELF Linker
641#------------------------------------------------------------------------------
642
643def is_accessible(path):
644    try:
645        mode = os.stat(path).st_mode
646        return (mode & (stat.S_IRUSR | stat.S_IRGRP | stat.S_IROTH)) != 0
647    except FileNotFoundError:
648        return False
649
650
651def scan_accessible_files(root):
652    for base, dirs, files in os.walk(root):
653        for filename in files:
654            path = os.path.join(base, filename)
655            if is_accessible(path):
656                yield path
657
658
659def scan_elf_files(root):
660    for path in scan_accessible_files(root):
661        try:
662            yield (path, ELF.load(path))
663        except ELFError:
664            pass
665
666
667def scan_elf_dump_files(root):
668    for path in scan_accessible_files(root):
669        if not path.endswith('.sym'):
670            continue
671        yield (path[0:-4], ELF.load_dump(path))
672
673
674PT_SYSTEM = 0
675PT_VENDOR = 1
676NUM_PARTITIONS = 2
677
678
679SPLibResult = collections.namedtuple(
680        'SPLibResult',
681        'sp_hal sp_hal_dep vndk_sp_hal sp_ndk sp_ndk_indirect '
682        'vndk_sp_both')
683
684def print_sp_lib(sp_lib, file=sys.stdout):
685    # SP-NDK
686    for lib in sorted_lib_path_list(sp_lib.sp_ndk):
687        print('sp-ndk:', lib, file=file)
688    for lib in sorted_lib_path_list(sp_lib.sp_ndk_indirect):
689        print('sp-ndk-indirect:', lib, file=file)
690
691    # SP-HAL
692    for lib in sorted_lib_path_list(sp_lib.sp_hal):
693        print('sp-hal:', lib, file=file)
694    for lib in sorted_lib_path_list(sp_lib.sp_hal_dep):
695        print('sp-hal-dep:', lib, file=file)
696    for lib in sorted_lib_path_list(sp_lib.vndk_sp_hal):
697        print('vndk-sp-hal:', lib, file=file)
698
699    # SP-both
700    for lib in sorted_lib_path_list(sp_lib.vndk_sp_both):
701        print('vndk-sp-both:', lib, file=file)
702
703
704class ELFResolver(object):
705    def __init__(self, lib_set, default_search_path):
706        self.lib_set = lib_set
707        self.default_search_path = default_search_path
708
709    def get_candidates(self, name, dt_rpath=None, dt_runpath=None):
710        if dt_rpath:
711            for d in dt_rpath:
712                yield os.path.join(d, name)
713        if dt_runpath:
714            for d in dt_runpath:
715                yield os.path.join(d, name)
716        for d in self.default_search_path:
717            yield os.path.join(d, name)
718
719    def resolve(self, name, dt_rpath=None, dt_runpath=None):
720        for path in self.get_candidates(name, dt_rpath, dt_runpath):
721            try:
722                return self.lib_set[path]
723            except KeyError:
724                continue
725        return None
726
727
728class ELFLinkData(object):
729    NEEDED = 0  # Dependencies recorded in DT_NEEDED entries.
730    DLOPEN = 1  # Dependencies introduced by dlopen().
731
732    def __init__(self, partition, path, elf):
733        self.partition = partition
734        self.path = path
735        self.elf = elf
736        self._deps = (set(), set())
737        self._users = (set(), set())
738        self.imported_ext_symbols = collections.defaultdict(set)
739        self._ndk_classification = NDK_LIBS.classify(path)
740        self.unresolved_symbols = set()
741        self.linked_symbols = dict()
742
743    @property
744    def is_ndk(self):
745        return self._ndk_classification != NDKLibDict.NOT_NDK
746
747    @property
748    def is_ll_ndk(self):
749        return self._ndk_classification == NDKLibDict.LL_NDK
750
751    @property
752    def is_sp_ndk(self):
753        return self._ndk_classification == NDKLibDict.SP_NDK
754
755    @property
756    def is_hl_ndk(self):
757        return self._ndk_classification == NDKLibDict.HL_NDK
758
759    def add_dep(self, dst, ty):
760        self._deps[ty].add(dst)
761        dst._users[ty].add(self)
762
763    def remove_dep(self, dst, ty):
764        self._deps[ty].remove(dst)
765        dst._users[ty].remove(self)
766
767    @property
768    def num_deps(self):
769        """Get the number of dependencies.  If a library is linked by both
770        NEEDED and DLOPEN relationship, then it will be counted twice."""
771        return sum(len(deps) for deps in self._deps)
772
773    @property
774    def deps(self):
775        return itertools.chain.from_iterable(self._deps)
776
777    @property
778    def deps_with_type(self):
779        dt_deps = zip(self._deps[self.NEEDED], itertools.repeat(self.NEEDED))
780        dl_deps = zip(self._deps[self.DLOPEN], itertools.repeat(self.DLOPEN))
781        return itertools.chain(dt_deps, dl_deps)
782
783    @property
784    def dt_deps(self):
785        return self._deps[self.NEEDED]
786
787    @property
788    def dl_deps(self):
789        return self._deps[self.DLOPEN]
790
791    @property
792    def num_users(self):
793        """Get the number of users.  If a library is linked by both NEEDED and
794        DLOPEN relationship, then it will be counted twice."""
795        return sum(len(users) for users in self._users)
796
797    @property
798    def users(self):
799        return itertools.chain.from_iterable(self._users)
800
801    @property
802    def users_with_type(self):
803        dt_users = zip(self._users[self.NEEDED], itertools.repeat(self.NEEDED))
804        dl_users = zip(self._users[self.DLOPEN], itertools.repeat(self.DLOPEN))
805        return itertools.chain(dt_users, dl_users)
806
807    @property
808    def dt_users(self):
809        return self._users[self.NEEDED]
810
811    @property
812    def dl_users(self):
813        return self._users[self.DLOPEN]
814
815    def has_dep(self, dst):
816        return any(dst in deps for deps in self._deps)
817
818    def has_user(self, dst):
819        return any(dst in users for users in self._users)
820
821    def is_system_lib(self):
822        return self.partition == PT_SYSTEM
823
824    def get_dep_linked_symbols(self, dep):
825        symbols = set()
826        for symbol, exp_lib in self.linked_symbols.items():
827            if exp_lib == dep:
828                symbols.add(symbol)
829        return sorted(symbols)
830
831    def __lt__(self, rhs):
832        return self.path < rhs.path
833
834
835def sorted_lib_path_list(libs):
836    libs = [lib.path for lib in libs]
837    libs.sort()
838    return libs
839
840_VNDK_RESULT_FIELD_NAMES = (
841        'll_ndk', 'll_ndk_indirect', 'sp_ndk', 'sp_ndk_indirect',
842        'vndk_sp', 'vndk_sp_unused', 'vndk_sp_indirect',
843        'vndk_sp_indirect_unused', 'vndk_sp_indirect_private', 'vndk',
844        'vndk_indirect', 'fwk_only', 'fwk_only_rs', 'sp_hal', 'sp_hal_dep',
845        'vnd_only', 'vndk_ext', 'vndk_sp_ext', 'vndk_sp_indirect_ext',
846        'extra_vendor_libs')
847
848VNDKResult = defaultnamedtuple('VNDKResult', _VNDK_RESULT_FIELD_NAMES, set())
849
850_SIMPLE_VNDK_RESULT_FIELD_NAMES = (
851        'vndk_sp', 'vndk_sp_ext', 'extra_vendor_libs')
852
853SimpleVNDKResult = defaultnamedtuple(
854        'SimpleVNDKResult', _SIMPLE_VNDK_RESULT_FIELD_NAMES, set())
855
856
857class ELFLibDict(defaultnamedtuple('ELFLibDict', ('lib32', 'lib64'), {})):
858    def get_lib_dict(self, elf_class):
859        return self[elf_class - 1]
860
861    def add(self, path, lib):
862        self.get_lib_dict(lib.elf.ei_class)[path] = lib
863
864    def remove(self, lib):
865        del self.get_lib_dict(lib.elf.ei_class)[lib.path]
866
867    def get(self, path, default=None):
868        for lib_set in self:
869            res = lib_set.get(path, None)
870            if res:
871                return res
872        return default
873
874    def keys(self):
875        return itertools.chain(self.lib32.keys(), self.lib64.keys())
876
877    def values(self):
878        return itertools.chain(self.lib32.values(), self.lib64.values())
879
880    def items(self):
881        return itertools.chain(self.lib32.items(), self.lib64.items())
882
883
884class ELFLinker(object):
885    def __init__(self):
886        self.lib_pt = [ELFLibDict() for i in range(NUM_PARTITIONS)]
887
888    def _add_lib_to_lookup_dict(self, lib):
889        self.lib_pt[lib.partition].add(lib.path, lib)
890
891    def _remove_lib_from_lookup_dict(self, lib):
892        self.lib_pt[lib.partition].remove(lib)
893
894    def add_lib(self, partition, path, elf):
895        lib = ELFLinkData(partition, path, elf)
896        self._add_lib_to_lookup_dict(lib)
897        return lib
898
899    def rename_lib(self, lib, new_partition, new_path):
900        self._remove_lib_from_lookup_dict(lib)
901        lib.path = new_path
902        lib.partition = new_partition
903        self._add_lib_to_lookup_dict(lib)
904
905    def add_dep(self, src_path, dst_path, ty):
906        for elf_class in (ELF.ELFCLASS32, ELF.ELFCLASS64):
907            src = self.get_lib_in_elf_class(elf_class, src_path)
908            dst = self.get_lib_in_elf_class(elf_class, dst_path)
909            if src and dst:
910                src.add_dep(dst, ty)
911                return
912        print('error: cannot add dependency from {} to {}.'
913              .format(src_path, dst_path), file=sys.stderr)
914
915    def get_lib_in_elf_class(self, elf_class, path, default=None):
916        for partition in range(NUM_PARTITIONS):
917            res = self.lib_pt[partition].get_lib_dict(elf_class).get(path)
918            if res:
919                return res
920        return default
921
922    def get_lib(self, path):
923        for lib_set in self.lib_pt:
924            lib = lib_set.get(path)
925            if lib:
926                return lib
927        return None
928
929    def get_libs(self, paths, report_error=None):
930        result = set()
931        for path in paths:
932            lib = self.get_lib(path)
933            if not lib:
934                if report_error is None:
935                    raise ValueError('path not found ' + path)
936                report_error(path)
937                continue
938            result.add(lib)
939        return result
940
941    def all_libs(self):
942        for lib_set in self.lib_pt:
943            for lib in lib_set.values():
944                yield lib
945
946    def _compute_lib_dict(self, elf_class):
947        res = dict()
948        for lib_pt in self.lib_pt:
949            res.update(lib_pt.get_lib_dict(elf_class))
950        return res
951
952    @staticmethod
953    def _compile_path_matcher(root, subdirs):
954        dirs = [os.path.normpath(os.path.join(root, i)) for i in subdirs]
955        patts = ['(?:' + re.escape(i) + os.sep + ')' for i in dirs]
956        return re.compile('|'.join(patts))
957
958    def add_executables_in_dir(self, partition_name, partition, root,
959                               alter_partition, alter_subdirs, ignored_subdirs,
960                               scan_elf_files):
961        root = os.path.abspath(root)
962        prefix_len = len(root) + 1
963
964        if alter_subdirs:
965            alter_patt = ELFLinker._compile_path_matcher(root, alter_subdirs)
966        if ignored_subdirs:
967            ignored_patt = ELFLinker._compile_path_matcher(root, ignored_subdirs)
968
969        for path, elf in scan_elf_files(root):
970            short_path = os.path.join('/', partition_name, path[prefix_len:])
971            if ignored_subdirs and ignored_patt.match(path):
972                continue
973            if alter_subdirs and alter_patt.match(path):
974                self.add_lib(alter_partition, short_path, elf)
975            else:
976                self.add_lib(partition, short_path, elf)
977
978    def load_extra_deps(self, path):
979        patt = re.compile('([^:]*):\\s*(.*)')
980        with open(path, 'r') as f:
981            for line in f:
982                match = patt.match(line)
983                if match:
984                    self.add_dep(match.group(1), match.group(2),
985                                 ELFLinkData.DLOPEN)
986
987    def _find_exported_symbol(self, symbol, libs):
988        """Find the shared library with the exported symbol."""
989        for lib in libs:
990            if symbol in lib.elf.exported_symbols:
991                return lib
992        return None
993
994    def _resolve_lib_imported_symbols(self, lib, imported_libs, generic_refs):
995        """Resolve the imported symbols in a library."""
996        for symbol in lib.elf.imported_symbols:
997            imported_lib = self._find_exported_symbol(symbol, imported_libs)
998            if not imported_lib:
999                lib.unresolved_symbols.add(symbol)
1000            else:
1001                lib.linked_symbols[symbol] = imported_lib
1002                if generic_refs:
1003                    ref_lib = generic_refs.refs.get(imported_lib.path)
1004                    if not ref_lib or not symbol in ref_lib.exported_symbols:
1005                        lib.imported_ext_symbols[imported_lib].add(symbol)
1006
1007    def _resolve_lib_dt_needed(self, lib, resolver):
1008        imported_libs = []
1009        for dt_needed in lib.elf.dt_needed:
1010            dep = resolver.resolve(dt_needed, lib.elf.dt_rpath,
1011                                   lib.elf.dt_runpath)
1012            if not dep:
1013                candidates = list(resolver.get_candidates(
1014                    dt_needed, lib.elf.dt_rpath, lib.elf.dt_runpath))
1015                print('warning: {}: Missing needed library: {}  Tried: {}'
1016                      .format(lib.path, dt_needed, candidates), file=sys.stderr)
1017                continue
1018            lib.add_dep(dep, ELFLinkData.NEEDED)
1019            imported_libs.append(dep)
1020        return imported_libs
1021
1022    def _resolve_lib_deps(self, lib, resolver, generic_refs):
1023        # Resolve DT_NEEDED entries.
1024        imported_libs = self._resolve_lib_dt_needed(lib, resolver)
1025
1026        if generic_refs:
1027            for imported_lib in imported_libs:
1028                if imported_lib.path not in generic_refs.refs:
1029                    # Add imported_lib to imported_ext_symbols to make sure
1030                    # non-AOSP libraries are in the imported_ext_symbols key
1031                    # set.
1032                    lib.imported_ext_symbols[imported_lib].update()
1033
1034        # Resolve imported symbols.
1035        self._resolve_lib_imported_symbols(lib, imported_libs, generic_refs)
1036
1037    def _resolve_lib_set_deps(self, lib_set, resolver, generic_refs):
1038        for lib in lib_set:
1039            self._resolve_lib_deps(lib, resolver, generic_refs)
1040
1041    SYSTEM_SEARCH_PATH = (
1042        '/system/${LIB}',
1043        '/vendor/${LIB}',
1044    )
1045
1046    VENDOR_SEARCH_PATH = (
1047        '/vendor/${LIB}',
1048        '/vendor/${LIB}/vndk-sp',
1049        '/system/${LIB}/vndk-sp',
1050        '/system/${LIB}',  # For degenerated VNDK libs.
1051    )
1052
1053    VNDK_SP_SEARCH_PATH = (
1054        '/vendor/${LIB}/vndk-sp',
1055        '/system/${LIB}/vndk-sp',
1056        '/vendor/${LIB}',  # To discover missing vndk-sp dependencies.
1057        '/system/${LIB}',  # To discover missing vndk-sp dependencies.
1058    )
1059
1060    @staticmethod
1061    def _subst_search_path(search_path, elf_class):
1062        lib_dir_name = 'lib' if elf_class == ELF.ELFCLASS32 else 'lib64'
1063        return [path.replace('${LIB}', lib_dir_name) for path in search_path]
1064
1065    @staticmethod
1066    def _is_in_vndk_sp_dir(path):
1067        return os.path.basename(os.path.dirname(path)).startswith('vndk-sp')
1068
1069    def _resolve_elf_class_deps(self, elf_class, generic_refs):
1070        system_lib_dict = self.lib_pt[PT_SYSTEM].get_lib_dict(elf_class)
1071        vendor_lib_dict = self.lib_pt[PT_VENDOR].get_lib_dict(elf_class)
1072        lib_dict = self._compute_lib_dict(elf_class)
1073
1074        # Resolve system libs.
1075        system_libs = [lib for lib in system_lib_dict.values()
1076                       if not self._is_in_vndk_sp_dir(lib.path)]
1077        search_path = self._subst_search_path(
1078                self.SYSTEM_SEARCH_PATH, elf_class)
1079        resolver = ELFResolver(lib_dict, search_path)
1080        self._resolve_lib_set_deps(system_libs, resolver, generic_refs)
1081
1082        # Resolve vendor libs.
1083        vendor_libs = [lib for lib in vendor_lib_dict.values()
1084                       if not self._is_in_vndk_sp_dir(lib.path)]
1085        search_path = self._subst_search_path(
1086                self.VENDOR_SEARCH_PATH, elf_class)
1087        resolver = ELFResolver(lib_dict, search_path)
1088        self._resolve_lib_set_deps(vendor_libs, resolver, generic_refs)
1089
1090        # Resolve vndk-sp libs
1091        vndk_sp = [lib for lib in lib_dict.values()
1092                   if self._is_in_vndk_sp_dir(lib.path)]
1093        search_path = self._subst_search_path(
1094                self.VNDK_SP_SEARCH_PATH, elf_class)
1095        resolver = ELFResolver(lib_dict, search_path)
1096        self._resolve_lib_set_deps(vndk_sp, resolver, generic_refs)
1097
1098    def resolve_deps(self, generic_refs=None):
1099        self._resolve_elf_class_deps(ELF.ELFCLASS32, generic_refs)
1100        self._resolve_elf_class_deps(ELF.ELFCLASS64, generic_refs)
1101
1102    def compute_path_matched_lib(self, path_patterns):
1103        patt = re.compile('|'.join('(?:' + p + ')' for p in path_patterns))
1104        return set(lib for lib in self.all_libs() if patt.match(lib.path))
1105
1106    def compute_predefined_fwk_only_rs(self):
1107        """Find all fwk-only-rs libraries."""
1108        path_patterns = (
1109            '^/system/lib(?:64)?/(?:vndk-sp/)?libft2\\.so$',
1110            '^/system/lib(?:64)?/(?:vndk-sp/)?libmediandk\\.so',
1111        )
1112        return self.compute_path_matched_lib(path_patterns)
1113
1114    def compute_predefined_vndk_sp(self):
1115        """Find all vndk-sp libraries."""
1116        path_patterns = (
1117            # Visible to SP-HALs
1118            '^.*/android\\.hardware\\.graphics\\.allocator@2\\.0\\.so$',
1119            '^.*/android\\.hardware\\.graphics\\.common@1\\.0\\.so$',
1120            '^.*/android\\.hardware\\.graphics\\.mapper@2\\.0\\.so$',
1121            '^.*/android\\.hardware\\.renderscript@1\\.0\\.so$',
1122            '^.*/libRSCpuRef\\.so$',
1123            '^.*/libRSDriver\\.so$',
1124            '^.*/libRS_internal\\.so$',
1125            '^.*/libbase\\.so$',
1126            '^.*/libbcinfo\\.so$',
1127            '^.*/libc\\+\\+\\.so$',
1128            '^.*/libcompiler_rt\\.so$',
1129            '^.*/libcutils\\.so$',
1130            '^.*/libhardware\\.so$',
1131            '^.*/libhidlbase\\.so$',
1132            '^.*/libhidltransport\\.so$',
1133            '^.*/libhwbinder\\.so$',
1134            '^.*/libutils\\.so$',
1135
1136            # Only for o-release
1137            '^.*/android\\.hidl\\.base@1\\.0\\.so$',
1138        )
1139        return self.compute_path_matched_lib(path_patterns)
1140
1141    def compute_predefined_vndk_sp_indirect(self):
1142        """Find all vndk-sp-indirect libraries."""
1143        path_patterns = (
1144            # Invisible to SP-HALs
1145            '^.*/libbacktrace\\.so$',
1146            '^.*/libblas\\.so$',
1147            '^.*/liblzma\\.so$',
1148            '^.*/libpng\\.so$',
1149            '^.*/libunwind\\.so$',
1150        )
1151        return self.compute_path_matched_lib(path_patterns)
1152
1153    def compute_predefined_sp_hal(self):
1154        """Find all same-process HALs."""
1155        path_patterns = (
1156            # OpenGL-related
1157            '^/vendor/.*/libEGL_.*\\.so$',
1158            '^/vendor/.*/libGLES_.*\\.so$',
1159            '^/vendor/.*/libGLESv1_CM_.*\\.so$',
1160            '^/vendor/.*/libGLESv2_.*\\.so$',
1161            '^/vendor/.*/libGLESv3_.*\\.so$',
1162            # Vulkan
1163            '^/vendor/.*/vulkan.*\\.so$',
1164            # libRSDriver
1165            '^.*/android\\.hardware\\.renderscript@1\\.0-impl\\.so$',
1166            '^/vendor/.*/libPVRRS\\.so$',
1167            '^/vendor/.*/libRSDriver.*\\.so$',
1168            # Gralloc mapper
1169            '^.*/gralloc\\..*\\.so$',
1170            '^.*/android\\.hardware\\.graphics\\.mapper@\\d+\\.\\d+-impl\\.so$',
1171        )
1172        return self.compute_path_matched_lib(path_patterns)
1173
1174    def compute_sp_ndk(self):
1175        """Find all SP-NDK libraries."""
1176        return set(lib for lib in self.all_libs() if lib.is_sp_ndk)
1177
1178    def compute_sp_lib(self, generic_refs):
1179        def is_ndk(lib):
1180            return lib.is_ndk
1181
1182        sp_ndk = self.compute_sp_ndk()
1183        sp_ndk_closure = self.compute_closure(sp_ndk, is_ndk)
1184        sp_ndk_indirect = sp_ndk_closure - sp_ndk
1185
1186        sp_hal = self.compute_predefined_sp_hal()
1187        sp_hal_closure = self.compute_closure(sp_hal, is_ndk)
1188
1189        def is_aosp_lib(lib):
1190            return (not generic_refs or \
1191                    generic_refs.classify_lib(lib) != GenericRefs.NEW_LIB)
1192
1193        vndk_sp_hal = set()
1194        sp_hal_dep = set()
1195        for lib in sp_hal_closure - sp_hal:
1196            if is_aosp_lib(lib):
1197                vndk_sp_hal.add(lib)
1198            else:
1199                sp_hal_dep.add(lib)
1200
1201        vndk_sp_both = sp_ndk_indirect & vndk_sp_hal
1202        sp_ndk_indirect -= vndk_sp_both
1203        vndk_sp_hal -= vndk_sp_both
1204
1205        return SPLibResult(sp_hal, sp_hal_dep, vndk_sp_hal, sp_ndk,
1206                           sp_ndk_indirect, vndk_sp_both)
1207
1208    def _po_sorted(self, lib_set, get_successors):
1209        result = []
1210        visited = set()
1211        def traverse(lib):
1212            for succ in get_successors(lib):
1213                if succ in lib_set and succ not in visited:
1214                    visited.add(succ)
1215                    traverse(succ)
1216            result.append(lib)
1217        for lib in lib_set:
1218            if lib not in visited:
1219                visited.add(lib)
1220                traverse(lib)
1221        return result
1222
1223    def _deps_po_sorted(self, lib_set):
1224        return self._po_sorted(lib_set, lambda x: x.deps)
1225
1226    def _users_po_sorted(self, lib_set):
1227        return self._po_sorted(lib_set, lambda x: x.users)
1228
1229    def normalize_partition_tags(self, sp_hals, generic_refs):
1230        system_libs = set(self.lib_pt[PT_SYSTEM].values())
1231        system_libs_po = self._deps_po_sorted(system_libs)
1232
1233        def is_system_lib_or_sp_hal(lib):
1234            return lib.is_system_lib() or lib in sp_hals
1235
1236        for lib in system_libs_po:
1237            if all(is_system_lib_or_sp_hal(dep) for dep in lib.deps):
1238                # Good system lib.  Do nothing.
1239                continue
1240            if not generic_refs or generic_refs.refs.get(lib.path):
1241                # If lib is in AOSP generic reference, then we assume that the
1242                # non-SP-HAL dependencies are errors.  Emit errors and remove
1243                # the dependencies.
1244                for dep in list(lib.dt_deps):
1245                    if not is_system_lib_or_sp_hal(dep):
1246                        print('error: {}: system exe/lib must not depend on '
1247                              'vendor lib {}.  Assume such dependency does '
1248                              'not exist.'.format(lib.path, dep.path),
1249                              file=sys.stderr)
1250                        lib.remove_dep(dep, ELFLinkData.NEEDED)
1251                for dep in list(lib.dl_deps):
1252                    if not is_system_lib_or_sp_hal(dep):
1253                        print('error: {}: system exe/lib must not dlopen() '
1254                              'vendor lib {}.  Assume such dependency does '
1255                              'not exist.'.format(lib.path, dep.path),
1256                              file=sys.stderr)
1257                        lib.remove_dep(dep, ELFLinkData.DLOPEN)
1258            else:
1259                # If lib is not in AOSP generic reference, then we assume that
1260                # lib must be moved to vendor partition.
1261                for dep in lib.deps:
1262                    if not is_system_lib_or_sp_hal(dep):
1263                        print('warning: {}: system exe/lib must not depend on '
1264                              'vendor lib {}.  Assuming {} should be placed in '
1265                              'vendor partition.'
1266                              .format(lib.path, dep.path, lib.path),
1267                              file=sys.stderr)
1268                new_path = lib.path.replace('/system/', '/vendor/')
1269                self.rename_lib(lib, PT_VENDOR, new_path)
1270
1271    @staticmethod
1272    def _parse_action_on_ineligible_lib(arg):
1273        follow = False
1274        warn = False
1275        for flag in arg.split(','):
1276            if flag == 'follow':
1277                follow = True
1278            elif flag == 'warn':
1279                warn = True
1280            elif flag == 'ignore':
1281                continue
1282            else:
1283                raise ValueError('unknown action \"{}\"'.format(flag))
1284        return (follow, warn)
1285
1286    def compute_degenerated_vndk(self, generic_refs, tagged_paths=None,
1287                                 action_ineligible_vndk_sp='warn',
1288                                 action_ineligible_vndk='warn'):
1289        # Find LL-NDK and SP-NDK libs.
1290        ll_ndk = set(lib for lib in self.all_libs() if lib.is_ll_ndk)
1291        sp_ndk = set(lib for lib in self.all_libs() if lib.is_sp_ndk)
1292
1293        # Find SP-HAL libs.
1294        sp_hal = self.compute_predefined_sp_hal()
1295
1296        # Normalize partition tags.  We expect many violations from the
1297        # pre-Treble world.  Guess a resolution for the incorrect partition
1298        # tag.
1299        self.normalize_partition_tags(sp_hal, generic_refs)
1300
1301        # Find SP-HAL-Dep libs.
1302        def is_aosp_lib(lib):
1303            if not generic_refs:
1304                # If generic reference is not available, then assume all system
1305                # libs are AOSP libs.
1306                return lib.partition == PT_SYSTEM
1307            return generic_refs.has_same_name_lib(lib)
1308
1309        def is_not_sp_hal_dep(lib):
1310            if lib.is_ll_ndk or lib.is_sp_ndk or lib in sp_hal:
1311                return True
1312            return is_aosp_lib(lib)
1313
1314        sp_hal_dep = self.compute_closure(sp_hal, is_not_sp_hal_dep)
1315        sp_hal_dep -= sp_hal
1316
1317        # Find FWK-ONLY-RS libs.
1318        fwk_only_rs = self.compute_predefined_fwk_only_rs()
1319
1320        # Find VNDK-SP libs.
1321        def is_not_vndk_sp(lib):
1322            return lib.is_ll_ndk or lib.is_sp_ndk or lib in sp_hal or \
1323                   lib in sp_hal_dep
1324
1325        follow_ineligible_vndk_sp, warn_ineligible_vndk_sp = \
1326                self._parse_action_on_ineligible_lib(action_ineligible_vndk_sp)
1327        predefined_vndk_sp = self.compute_predefined_vndk_sp()
1328        vndk_sp = set()
1329        for lib in itertools.chain(sp_hal, sp_hal_dep):
1330            for dep in lib.deps:
1331                if is_not_vndk_sp(dep):
1332                    continue
1333                if dep in predefined_vndk_sp:
1334                    vndk_sp.add(dep)
1335                    continue
1336                if warn_ineligible_vndk_sp:
1337                    print('error: SP-HAL {} depends on non vndk-sp '
1338                          'library {}.'.format(lib.path, dep.path),
1339                          file=sys.stderr)
1340                if follow_ineligible_vndk_sp:
1341                    vndk_sp.add(dep)
1342
1343        # Find VNDK-SP-Indirect libs.
1344        def is_not_vndk_sp_indirect(lib):
1345            return lib.is_ll_ndk or lib.is_sp_ndk or lib in vndk_sp or \
1346                   lib in fwk_only_rs
1347
1348        vndk_sp_indirect = self.compute_closure(
1349                vndk_sp, is_not_vndk_sp_indirect)
1350        vndk_sp_indirect -= vndk_sp
1351
1352        # Find unused predefined VNDK-SP libs.
1353        vndk_sp_unused = set(lib for lib in predefined_vndk_sp
1354                             if self._is_in_vndk_sp_dir(lib.path))
1355        vndk_sp_unused -= vndk_sp
1356        vndk_sp_unused -= vndk_sp_indirect
1357
1358        # Find dependencies of unused predefined VNDK-SP libs.
1359        def is_not_vndk_sp_indirect_unused(lib):
1360            return is_not_vndk_sp_indirect(lib) or lib in vndk_sp_indirect
1361        vndk_sp_indirect_unused = self.compute_closure(
1362                vndk_sp_unused, is_not_vndk_sp_indirect_unused)
1363        vndk_sp_indirect_unused -= vndk_sp_unused
1364
1365        # TODO: Compute VNDK-SP-Indirect-Private.
1366        vndk_sp_indirect_private = set()
1367
1368        # Define helper functions for vndk_sp sets.
1369        def is_vndk_sp_public(lib):
1370            return lib in vndk_sp or lib in vndk_sp_unused or \
1371                   lib in vndk_sp_indirect or \
1372                   lib in vndk_sp_indirect_unused
1373
1374        def is_vndk_sp(lib):
1375            return is_vndk_sp_public(lib) or lib in vndk_sp_indirect_private
1376
1377        def is_vndk_sp_unused(lib):
1378            return lib in vndk_sp_unused or lib in vndk_sp_indirect_unused
1379
1380        def relabel_vndk_sp_as_used(lib):
1381            assert is_vndk_sp_unused(lib)
1382
1383            if lib in vndk_sp_unused:
1384                vndk_sp_unused.remove(lib)
1385                vndk_sp.add(lib)
1386            else:
1387                vndk_sp_indirect_unused.remove(lib)
1388                vndk_sp_indirect.add(lib)
1389
1390            closure = self.compute_closure({lib}, is_not_vndk_sp_indirect)
1391            closure -= vndk_sp
1392            vndk_sp_indirect_unused.difference_update(closure)
1393            vndk_sp_indirect.update(closure)
1394
1395        # Find VNDK-SP-Ext libs.
1396        vndk_sp_ext = set()
1397        def collect_vndk_ext(libs):
1398            result = set()
1399            for lib in libs:
1400                for dep in lib.imported_ext_symbols:
1401                    if dep in vndk_sp and dep not in vndk_sp_ext:
1402                        result.add(dep)
1403            return result
1404
1405        candidates = collect_vndk_ext(self.lib_pt[PT_VENDOR].values())
1406        while candidates:
1407            vndk_sp_ext |= candidates
1408            candidates = collect_vndk_ext(candidates)
1409
1410        # Find VNDK-SP-Indirect-Ext libs.
1411        predefined_vndk_sp_indirect = self.compute_predefined_vndk_sp_indirect()
1412        vndk_sp_indirect_ext = set()
1413        def collect_vndk_sp_indirect_ext(libs):
1414            result = set()
1415            for lib in libs:
1416                exts = set(lib.imported_ext_symbols.keys())
1417                for dep in lib.deps:
1418                    if not is_vndk_sp_public(dep):
1419                        continue
1420                    if dep in vndk_sp_ext or dep in vndk_sp_indirect_ext:
1421                        continue
1422                    # If lib is using extended definition from deps, then we
1423                    # have to make a copy of dep.
1424                    if dep in exts:
1425                        result.add(dep)
1426                        continue
1427                    # If lib is using non-predefined VNDK-SP-Indirect, then we
1428                    # have to make a copy of dep.
1429                    if dep not in predefined_vndk_sp and \
1430                            dep not in predefined_vndk_sp_indirect:
1431                        result.add(dep)
1432                        continue
1433            return result
1434
1435        def is_not_vndk_sp_indirect(lib):
1436            return lib.is_ll_ndk or lib.is_sp_ndk or lib in vndk_sp or \
1437                   lib in fwk_only_rs
1438
1439        candidates = collect_vndk_sp_indirect_ext(vndk_sp_ext)
1440        while candidates:
1441            vndk_sp_indirect_ext |= candidates
1442            candidates = collect_vndk_sp_indirect_ext(candidates)
1443
1444        # Find VNDK libs (a.k.a. system shared libs directly used by vendor
1445        # partition.)
1446        def is_not_vndk(lib):
1447            if lib.is_ll_ndk or lib.is_sp_ndk or is_vndk_sp_public(lib) or \
1448               lib in fwk_only_rs:
1449                return True
1450            return lib.partition != PT_SYSTEM
1451
1452        def is_eligible_lib_access(lib, dep):
1453            return not tagged_paths or \
1454                    tagged_paths.is_path_visible(lib.path, dep.path)
1455
1456        follow_ineligible_vndk, warn_ineligible_vndk = \
1457                self._parse_action_on_ineligible_lib(action_ineligible_vndk)
1458        vndk = set()
1459        extra_vendor_libs = set()
1460        def collect_vndk(vendor_libs):
1461            next_vendor_libs = set()
1462            for lib in vendor_libs:
1463                for dep in lib.deps:
1464                    if is_vndk_sp_unused(dep):
1465                        relabel_vndk_sp_as_used(dep)
1466                        continue
1467                    if is_not_vndk(dep):
1468                        continue
1469                    if not is_aosp_lib(dep):
1470                        # The dependency should be copied into vendor partition
1471                        # as an extra vendor lib.
1472                        if dep not in extra_vendor_libs:
1473                            next_vendor_libs.add(dep)
1474                            extra_vendor_libs.add(dep)
1475                        continue
1476                    if is_eligible_lib_access(lib, dep):
1477                        vndk.add(dep)
1478                        continue
1479                    if warn_ineligible_vndk:
1480                        print('warning: vendor lib/exe {} depends on '
1481                              'ineligible framework shared lib {}.'
1482                              .format(lib.path, dep.path), file=sys.stderr)
1483                    if follow_ineligible_vndk:
1484                        vndk.add(dep)
1485            return next_vendor_libs
1486
1487        candidates = collect_vndk(self.lib_pt[PT_VENDOR].values())
1488        while candidates:
1489            candidates = collect_vndk(candidates)
1490
1491        vndk_indirect = self.compute_closure(vndk, is_not_vndk)
1492        vndk_indirect -= vndk
1493
1494        def is_vndk(lib):
1495            return lib in vndk or lib in vndk_indirect
1496
1497        # Find VNDK-EXT libs (VNDK libs with extended definitions and the
1498        # extended definitions are used by the vendor modules (including
1499        # extra_vendor_libs).
1500
1501        # FIXME: DAUX libraries won't be found by the following algorithm.
1502        vndk_ext = set()
1503
1504        def collect_vndk_ext(libs):
1505            result = set()
1506            for lib in libs:
1507                for dep in lib.imported_ext_symbols:
1508                    if dep in vndk and dep not in vndk_ext:
1509                        result.add(dep)
1510            return result
1511
1512        candidates = collect_vndk_ext(self.lib_pt[PT_VENDOR].values())
1513        candidates |= collect_vndk_ext(extra_vendor_libs)
1514
1515        while candidates:
1516            vndk_ext |= candidates
1517            candidates = collect_vndk_ext(candidates)
1518
1519        # Compute LL-NDK-Indirect and SP-NDK-Indirect.
1520        def is_not_ll_ndk_indirect(lib):
1521            return lib.is_ll_ndk or is_vndk_sp(lib) or is_vndk(lib)
1522
1523        ll_ndk_indirect = self.compute_closure(ll_ndk, is_not_ll_ndk_indirect)
1524        ll_ndk_indirect -= ll_ndk
1525
1526        def is_not_sp_ndk_indirect(lib):
1527            return lib.is_ll_ndk or lib.is_sp_ndk or lib in ll_ndk_indirect or \
1528                   is_vndk_sp(lib) or is_vndk(lib)
1529
1530        sp_ndk_indirect = self.compute_closure(sp_ndk, is_not_sp_ndk_indirect)
1531        sp_ndk_indirect -= sp_ndk
1532
1533        # Return the VNDK classifications.
1534        return VNDKResult(
1535                ll_ndk=ll_ndk,
1536                ll_ndk_indirect=ll_ndk_indirect,
1537                sp_ndk=sp_ndk,
1538                sp_ndk_indirect=sp_ndk_indirect,
1539                vndk_sp=vndk_sp,
1540                vndk_sp_indirect=vndk_sp_indirect,
1541                # vndk_sp_indirect_private=vndk_sp_indirect_private,
1542                vndk_sp_unused=vndk_sp_unused,
1543                vndk_sp_indirect_unused=vndk_sp_indirect_unused,
1544                vndk=vndk,
1545                vndk_indirect=vndk_indirect,
1546                # fwk_only=fwk_only,
1547                fwk_only_rs=fwk_only_rs,
1548                sp_hal=sp_hal,
1549                sp_hal_dep=sp_hal_dep,
1550                # vnd_only=vnd_only,
1551                vndk_ext=vndk_ext,
1552                vndk_sp_ext=vndk_sp_ext,
1553                vndk_sp_indirect_ext=vndk_sp_indirect_ext,
1554                extra_vendor_libs=extra_vendor_libs)
1555
1556    def compute_vndk_cap(self, banned_libs):
1557        # ELF files on vendor partitions are banned unconditionally.  ELF files
1558        # on the system partition are banned if their file extensions are not
1559        # '.so' or their file names are listed in banned_libs.  LL-NDK and
1560        # SP-NDK libraries are treated as a special case which will not be
1561        # considered as banned libraries at the moment.
1562        def is_banned(lib):
1563            if lib.is_ndk:
1564                return lib.is_hl_ndk
1565            return (banned_libs.is_banned(lib.path) or
1566                    not lib.is_system_lib() or
1567                    not lib.path.endswith('.so'))
1568
1569        # Find all libraries that are banned.
1570        banned_set = set()
1571        for lib_set in self.lib_pt:
1572            for lib in lib_set.values():
1573                if is_banned(lib):
1574                    banned_set.add(lib)
1575
1576        # Find the transitive closure of the banned libraries.
1577        stack = list(banned_set)
1578        while stack:
1579            lib = stack.pop()
1580            for user in lib.users:
1581                if not user.is_ndk and user not in banned_set:
1582                    banned_set.add(user)
1583                    stack.append(user)
1584
1585        # Find the non-NDK non-banned libraries.
1586        vndk_cap = set()
1587        for lib in self.lib_pt[PT_SYSTEM].values():
1588            if not lib.is_ndk and lib not in banned_set:
1589                vndk_cap.add(lib)
1590
1591        return vndk_cap
1592
1593    @staticmethod
1594    def compute_closure(root_set, is_excluded):
1595        closure = set(root_set)
1596        stack = list(root_set)
1597        while stack:
1598            lib = stack.pop()
1599            for dep in lib.deps:
1600                if is_excluded(dep):
1601                    continue
1602                if dep not in closure:
1603                    closure.add(dep)
1604                    stack.append(dep)
1605        return closure
1606
1607    @staticmethod
1608    def _create_internal(scan_elf_files, system_dirs, system_dirs_as_vendor,
1609                         system_dirs_ignored, vendor_dirs,
1610                         vendor_dirs_as_system, vendor_dirs_ignored,
1611                         extra_deps, generic_refs):
1612        graph = ELFLinker()
1613
1614        if system_dirs:
1615            for path in system_dirs:
1616                graph.add_executables_in_dir('system', PT_SYSTEM, path,
1617                                             PT_VENDOR, system_dirs_as_vendor,
1618                                             system_dirs_ignored,
1619                                             scan_elf_files)
1620
1621        if vendor_dirs:
1622            for path in vendor_dirs:
1623                graph.add_executables_in_dir('vendor', PT_VENDOR, path,
1624                                             PT_SYSTEM, vendor_dirs_as_system,
1625                                             vendor_dirs_ignored,
1626                                             scan_elf_files)
1627
1628        if extra_deps:
1629            for path in extra_deps:
1630                graph.load_extra_deps(path)
1631
1632        graph.resolve_deps(generic_refs)
1633
1634        return graph
1635
1636    @staticmethod
1637    def create(system_dirs=None, system_dirs_as_vendor=None,
1638               system_dirs_ignored=None, vendor_dirs=None,
1639               vendor_dirs_as_system=None, vendor_dirs_ignored=None,
1640               extra_deps=None, generic_refs=None):
1641        return ELFLinker._create_internal(
1642                scan_elf_files, system_dirs, system_dirs_as_vendor,
1643                system_dirs_ignored, vendor_dirs, vendor_dirs_as_system,
1644                vendor_dirs_ignored, extra_deps, generic_refs)
1645
1646    @staticmethod
1647    def create_from_dump(system_dirs=None, system_dirs_as_vendor=None,
1648                         vendor_dirs=None, vendor_dirs_as_system=None,
1649                         extra_deps=None, generic_refs=None):
1650        return ELFLinker._create_internal(
1651                scan_elf_dump_files, system_dirs, system_dirs_as_vendor,
1652                vendor_dirs, vendor_dirs_as_system, extra_deps, generic_refs)
1653
1654
1655#------------------------------------------------------------------------------
1656# Generic Reference
1657#------------------------------------------------------------------------------
1658
1659class GenericRefs(object):
1660    NEW_LIB = 0
1661    EXPORT_EQUAL = 1
1662    EXPORT_SUPER_SET = 2
1663    MODIFIED = 3
1664
1665    def __init__(self):
1666        self.refs = dict()
1667        self._lib_names = set()
1668
1669    def add(self, path, elf):
1670        self.refs[path] = elf
1671        self._lib_names.add(os.path.basename(path))
1672
1673    def _load_from_sym_dir(self, root):
1674        root = os.path.abspath(root)
1675        prefix_len = len(root) + 1
1676        for base, dirnames, filenames in os.walk(root):
1677            for filename in filenames:
1678                if not filename.endswith('.sym'):
1679                    continue
1680                path = os.path.join(base, filename)
1681                lib_path = '/' + path[prefix_len:-4]
1682                with open(path, 'r') as f:
1683                    self.add(lib_path, ELF.load_dump(path))
1684
1685    @staticmethod
1686    def create_from_sym_dir(root):
1687        result = GenericRefs()
1688        result._load_from_sym_dir(root)
1689        return result
1690
1691    def _load_from_image_dir(self, root, prefix):
1692        root = os.path.abspath(root)
1693        root_len = len(root) + 1
1694        for path, elf in scan_elf_files(root):
1695            self.add(os.path.join(prefix, path[root_len:]), elf)
1696
1697    @staticmethod
1698    def create_from_image_dir(root, prefix):
1699        result = GenericRefs()
1700        result._load_from_image_dir(root, prefix)
1701        return result
1702
1703    def classify_lib(self, lib):
1704        ref_lib = self.refs.get(lib.path)
1705        if not ref_lib:
1706            return GenericRefs.NEW_LIB
1707        exported_symbols = lib.elf.exported_symbols
1708        if exported_symbols == ref_lib.exported_symbols:
1709            return GenericRefs.EXPORT_EQUAL
1710        if exported_symbols > ref_lib.exported_symbols:
1711            return GenericRefs.EXPORT_SUPER_SET
1712        return GenericRefs.MODIFIED
1713
1714    def is_equivalent_lib(self, lib):
1715        return self.classify_lib(lib) == GenericRefs.EXPORT_EQUAL
1716
1717    def has_same_name_lib(self, lib):
1718        return os.path.basename(lib.path) in self._lib_names
1719
1720
1721#------------------------------------------------------------------------------
1722# Commands
1723#------------------------------------------------------------------------------
1724
1725class Command(object):
1726    def __init__(self, name, help):
1727        self.name = name
1728        self.help = help
1729
1730    def add_argparser_options(self, parser):
1731        pass
1732
1733    def main(self, args):
1734        return 0
1735
1736
1737class ELFDumpCommand(Command):
1738    def __init__(self):
1739        super(ELFDumpCommand, self).__init__(
1740                'elfdump', help='Dump ELF .dynamic section')
1741
1742    def add_argparser_options(self, parser):
1743        parser.add_argument('path', help='path to an ELF file')
1744
1745    def main(self, args):
1746        try:
1747            ELF.load(args.path).dump()
1748        except ELFError as e:
1749            print('error: {}: Bad ELF file ({})'.format(args.path, e),
1750                  file=sys.stderr)
1751            sys.exit(1)
1752        return 0
1753
1754
1755class CreateGenericRefCommand(Command):
1756    def __init__(self):
1757        super(CreateGenericRefCommand, self).__init__(
1758                'create-generic-ref', help='Create generic references')
1759
1760    def add_argparser_options(self, parser):
1761        parser.add_argument('dir')
1762
1763        parser.add_argument(
1764                '--output', '-o', metavar='PATH', required=True,
1765                help='output directory')
1766
1767    def main(self, args):
1768        root = os.path.abspath(args.dir)
1769        print(root)
1770        prefix_len = len(root) + 1
1771        for path, elf in scan_elf_files(root):
1772            name = path[prefix_len:]
1773            print('Processing:', name, file=sys.stderr)
1774            out = os.path.join(args.output, name) + '.sym'
1775            makedirs(os.path.dirname(out), exist_ok=True)
1776            with open(out, 'w') as f:
1777                elf.dump(f)
1778        return 0
1779
1780
1781class ELFGraphCommand(Command):
1782    def add_argparser_options(self, parser):
1783        parser.add_argument(
1784                '--load-extra-deps', action='append',
1785                help='load extra module dependencies')
1786
1787        parser.add_argument(
1788                '--system', action='append',
1789                help='path to system partition contents')
1790
1791        parser.add_argument(
1792                '--vendor', action='append',
1793                help='path to vendor partition contents')
1794
1795        parser.add_argument(
1796                '--system-dir-as-vendor', action='append',
1797                help='sub directory of system partition that has vendor files')
1798
1799        parser.add_argument(
1800                '--system-dir-ignored', action='append',
1801                help='sub directory of system partition that must be ignored')
1802
1803        parser.add_argument(
1804                '--vendor-dir-as-system', action='append',
1805                help='sub directory of vendor partition that has system files')
1806
1807        parser.add_argument(
1808                '--vendor-dir-ignored', action='append',
1809                help='sub directory of vendor partition that must be ignored')
1810
1811        parser.add_argument(
1812                '--load-generic-refs',
1813                help='compare with generic reference symbols')
1814
1815        parser.add_argument(
1816                '--aosp-system',
1817                help='compare with AOSP generic system image directory')
1818
1819    def get_generic_refs_from_args(self, args):
1820        if args.load_generic_refs:
1821            return GenericRefs.create_from_sym_dir(args.load_generic_refs)
1822        if args.aosp_system:
1823            return GenericRefs.create_from_image_dir(args.aosp_system,
1824                                                     '/system')
1825        return None
1826
1827    def _check_arg_dir_exists(self, arg_name, dirs):
1828        for path in dirs:
1829            if not os.path.exists(path):
1830                print('error: Failed to find the directory "{}" specified in {}'
1831                        .format(path, arg_name), file=sys.stderr)
1832                sys.exit(1)
1833            if not os.path.isdir(path):
1834                print('error: Path "{}" specified in {} is not a directory'
1835                        .format(path, arg_name), file=sys.stderr)
1836                sys.exit(1)
1837
1838    def check_dirs_from_args(self, args):
1839        self._check_arg_dir_exists('--system', args.system)
1840        self._check_arg_dir_exists('--vendor', args.vendor)
1841
1842    def create_from_args(self, args):
1843        self.check_dirs_from_args(args)
1844
1845        generic_refs = self.get_generic_refs_from_args(args)
1846
1847        graph = ELFLinker.create(args.system, args.system_dir_as_vendor,
1848                                 args.system_dir_ignored,
1849                                 args.vendor, args.vendor_dir_as_system,
1850                                 args.vendor_dir_ignored,
1851                                 args.load_extra_deps,
1852                                 generic_refs=generic_refs)
1853
1854        return (generic_refs, graph)
1855
1856
1857class VNDKCommandBase(ELFGraphCommand):
1858    def add_argparser_options(self, parser):
1859        super(VNDKCommandBase, self).add_argparser_options(parser)
1860
1861        parser.add_argument('--no-default-dlopen-deps', action='store_true',
1862                help='do not add default dlopen dependencies')
1863
1864        parser.add_argument('--tag-file', help='lib tag file')
1865
1866        parser.add_argument(
1867                '--action-ineligible-vndk-sp', default='warn',
1868                help='action when a sp-hal uses non-vndk-sp libs '
1869                     '(option: follow,warn,ignore)')
1870
1871        parser.add_argument(
1872                '--action-ineligible-vndk', default='warn',
1873                help='action when a vendor lib/exe uses fwk-only libs '
1874                     '(option: follow,warn,ignore)')
1875
1876    def create_from_args(self, args):
1877        """Create all essential data structures for VNDK computation."""
1878
1879        generic_refs, graph = \
1880                super(VNDKCommandBase, self).create_from_args(args)
1881
1882        if not args.no_default_dlopen_deps:
1883            script_dir = os.path.dirname(os.path.abspath(__file__))
1884            minimum_dlopen_deps = os.path.join(script_dir, 'datasets',
1885                                               'minimum_dlopen_deps.txt')
1886            graph.load_extra_deps(minimum_dlopen_deps)
1887
1888        if args.tag_file:
1889            tagged_paths = TaggedPathDict.create_from_csv_path(args.tag_file)
1890        else:
1891            tagged_paths = None
1892
1893        return (generic_refs, graph, tagged_paths)
1894
1895
1896class VNDKCommand(VNDKCommandBase):
1897    def __init__(self):
1898        super(VNDKCommand, self).__init__(
1899                'vndk', help='Compute VNDK libraries set')
1900
1901    def add_argparser_options(self, parser):
1902        super(VNDKCommand, self).add_argparser_options(parser)
1903
1904        parser.add_argument(
1905                '--warn-incorrect-partition', action='store_true',
1906                help='warn about libraries only have cross partition linkages')
1907
1908        parser.add_argument(
1909                '--full', action='store_true',
1910                help='print all classification')
1911
1912        parser.add_argument(
1913                '--output-format', default='tag',
1914                help='output format for vndk classification')
1915
1916    def _warn_incorrect_partition_lib_set(self, lib_set, partition, error_msg):
1917        for lib in lib_set.values():
1918            if not lib.num_users:
1919                continue
1920            if all((user.partition != partition for user in lib.users)):
1921                print(error_msg.format(lib.path), file=sys.stderr)
1922
1923    def _warn_incorrect_partition(self, graph):
1924        self._warn_incorrect_partition_lib_set(
1925                graph.lib_pt[PT_VENDOR], PT_VENDOR,
1926                'warning: {}: This is a vendor library with framework-only '
1927                'usages.')
1928
1929        self._warn_incorrect_partition_lib_set(
1930                graph.lib_pt[PT_SYSTEM], PT_SYSTEM,
1931                'warning: {}: This is a framework library with vendor-only '
1932                'usages.')
1933
1934    def _check_ndk_extensions(self, graph, generic_refs):
1935        for lib_set in graph.lib_pt:
1936            for lib in lib_set.values():
1937                if lib.is_ndk and not generic_refs.is_equivalent_lib(lib):
1938                    print('warning: {}: NDK library should not be extended.'
1939                            .format(lib.path), file=sys.stderr)
1940
1941    @staticmethod
1942    def _extract_simple_vndk_result(vndk_result):
1943        field_name_tags = [
1944            ('vndk_sp', 'vndk_sp'),
1945            ('vndk_sp_unused', 'vndk_sp'),
1946            ('vndk_sp_indirect', 'vndk_sp'),
1947            ('vndk_sp_indirect_unused', 'vndk_sp'),
1948            ('vndk_sp_indirect_private', 'vndk_sp'),
1949
1950            ('vndk_sp_ext', 'vndk_sp_ext'),
1951            ('vndk_sp_indirect_ext', 'vndk_sp_ext'),
1952
1953            ('vndk_ext', 'extra_vendor_libs'),
1954            ('extra_vendor_libs', 'extra_vendor_libs'),
1955        ]
1956        results = SimpleVNDKResult()
1957        for field_name, tag in field_name_tags:
1958            getattr(results, tag).update(getattr(vndk_result, field_name))
1959        return results
1960
1961    def _print_tags(self, vndk_lib, full, file=sys.stdout):
1962        if full:
1963            result_tags = _VNDK_RESULT_FIELD_NAMES
1964            results = vndk_lib
1965        else:
1966            # Simplified VNDK output with only three sets.
1967            result_tags = _SIMPLE_VNDK_RESULT_FIELD_NAMES
1968            results = self._extract_simple_vndk_result(vndk_lib)
1969
1970        for tag in result_tags:
1971            libs = getattr(results, tag)
1972            tag += ':'
1973            for lib in sorted_lib_path_list(libs):
1974                print(tag, lib, file=file)
1975
1976    def _print_make(self, vndk_lib, file=sys.stdout):
1977        def get_module_name(path):
1978            name = os.path.basename(path)
1979            root, ext = os.path.splitext(name)
1980            return root
1981
1982        def get_module_names(lib_set):
1983            return sorted({ get_module_name(lib.path) for lib in lib_set })
1984
1985        results = self._extract_simple_vndk_result(vndk_lib)
1986        vndk_sp = get_module_names(results.vndk_sp)
1987        vndk_sp_ext = get_module_names(results.vndk_sp_ext)
1988        extra_vendor_libs= get_module_names(results.extra_vendor_libs)
1989
1990        def format_module_names(module_names):
1991            return '\\\n    ' +  ' \\\n    '.join(module_names)
1992
1993        script_dir = os.path.dirname(os.path.abspath(__file__))
1994        template_path = os.path.join(script_dir, 'templates', 'vndk.txt')
1995        with open(template_path, 'r') as f:
1996            template = f.read()
1997
1998        template = template.replace('##_VNDK_SP_##',
1999                                    format_module_names(vndk_sp))
2000        template = template.replace('##_VNDK_SP_EXT_##',
2001                                    format_module_names(vndk_sp_ext))
2002        template = template.replace('##_EXTRA_VENDOR_LIBS_##',
2003                                    format_module_names(extra_vendor_libs))
2004
2005        file.write(template)
2006
2007    def main(self, args):
2008        generic_refs, graph, tagged_paths = self.create_from_args(args)
2009
2010        # Check the API extensions to NDK libraries.
2011        if generic_refs:
2012            self._check_ndk_extensions(graph, generic_refs)
2013
2014        if args.warn_incorrect_partition:
2015            self._warn_incorrect_partition(graph)
2016
2017        # Compute vndk heuristics.
2018        vndk_lib = graph.compute_degenerated_vndk(
2019                generic_refs, tagged_paths, args.action_ineligible_vndk_sp,
2020                args.action_ineligible_vndk)
2021
2022        # Print results.
2023        if args.output_format == 'make':
2024            self._print_make(vndk_lib)
2025        else:
2026            self._print_tags(vndk_lib, args.full)
2027
2028        return 0
2029
2030
2031class DepsInsightCommand(VNDKCommandBase):
2032    def __init__(self):
2033        super(DepsInsightCommand, self).__init__(
2034                'deps-insight', help='Generate HTML to show dependencies')
2035
2036    def add_argparser_options(self, parser):
2037        super(DepsInsightCommand, self).add_argparser_options(parser)
2038
2039        parser.add_argument(
2040                '--output', '-o', help='output directory')
2041
2042    def main(self, args):
2043        generic_refs, graph, tagged_paths = self.create_from_args(args)
2044
2045        # Compute vndk heuristics.
2046        vndk_lib = graph.compute_degenerated_vndk(
2047                generic_refs, tagged_paths, args.action_ineligible_vndk_sp,
2048                args.action_ineligible_vndk)
2049
2050        # Serialize data.
2051        strs = []
2052        strs_dict = dict()
2053
2054        libs = list(graph.all_libs())
2055        libs.sort(key=lambda lib: lib.path)
2056        libs_dict = {lib: i for i, lib in enumerate(libs)}
2057
2058        def get_str_idx(s):
2059            try:
2060                return strs_dict[s]
2061            except KeyError:
2062                idx = len(strs)
2063                strs_dict[s] = idx
2064                strs.append(s)
2065                return idx
2066
2067        def collect_path_sorted_lib_idxs(libs):
2068            return [libs_dict[lib] for lib in sorted(libs)]
2069
2070        def collect_deps(lib):
2071            queue = list(lib.deps)
2072            visited = set(queue)
2073            visited.add(lib)
2074            deps = []
2075
2076            # Traverse dependencies with breadth-first search.
2077            while queue:
2078                # Collect dependencies for next queue.
2079                next_queue = []
2080                for lib in queue:
2081                    for dep in lib.deps:
2082                        if dep not in visited:
2083                            next_queue.append(dep)
2084                            visited.add(dep)
2085
2086                # Append current queue to result.
2087                deps.append(collect_path_sorted_lib_idxs(queue))
2088
2089                queue = next_queue
2090
2091            return deps
2092
2093        def collect_tags(lib):
2094            tags = []
2095            for field_name in _VNDK_RESULT_FIELD_NAMES:
2096                if lib in getattr(vndk_lib, field_name):
2097                    tags.append(get_str_idx(field_name))
2098            return tags
2099
2100        mods = []
2101        for lib in libs:
2102            mods.append([get_str_idx(lib.path),
2103                         32 if lib.elf.is_32bit else 64,
2104                         collect_tags(lib),
2105                         collect_deps(lib),
2106                         collect_path_sorted_lib_idxs(lib.users)])
2107
2108        # Generate output files.
2109        makedirs(args.output, exist_ok=True)
2110        script_dir = os.path.dirname(os.path.abspath(__file__))
2111        for name in ('index.html', 'insight.css', 'insight.js'):
2112            shutil.copyfile(os.path.join(script_dir, 'assets', name),
2113                            os.path.join(args.output, name))
2114
2115        with open(os.path.join(args.output, 'insight-data.js'), 'w') as f:
2116            f.write('''(function () {
2117    var strs = ''' + json.dumps(strs) + ''';
2118    var mods = ''' + json.dumps(mods) + ''';
2119    insight.init(document, strs, mods);
2120})();''')
2121
2122        return 0
2123
2124
2125class VNDKCapCommand(ELFGraphCommand):
2126    def __init__(self):
2127        super(VNDKCapCommand, self).__init__(
2128                'vndk-cap', help='Compute VNDK set upper bound')
2129
2130    def add_argparser_options(self, parser):
2131        super(VNDKCapCommand, self).add_argparser_options(parser)
2132
2133    def main(self, args):
2134        generic_refs, graph = self.create_from_args(args)
2135
2136        banned_libs = BannedLibDict.create_default()
2137
2138        vndk_cap = graph.compute_vndk_cap(banned_libs)
2139
2140        for lib in sorted_lib_path_list(vndk_cap):
2141            print(lib)
2142
2143
2144class DepsCommand(ELFGraphCommand):
2145    def __init__(self):
2146        super(DepsCommand, self).__init__(
2147                'deps', help='Print binary dependencies for debugging')
2148
2149    def add_argparser_options(self, parser):
2150        super(DepsCommand, self).add_argparser_options(parser)
2151
2152        parser.add_argument(
2153                '--revert', action='store_true',
2154                help='print usage dependency')
2155
2156        parser.add_argument(
2157                '--leaf', action='store_true',
2158                help='print binaries without dependencies or usages')
2159
2160        parser.add_argument(
2161                '--symbols', action='store_true',
2162                help='print symbols')
2163
2164    def main(self, args):
2165        generic_refs, graph = self.create_from_args(args)
2166
2167        results = []
2168        for partition in range(NUM_PARTITIONS):
2169            for name, lib in graph.lib_pt[partition].items():
2170                if args.symbols:
2171                    def collect_symbols(user, definer):
2172                        return user.get_dep_linked_symbols(definer)
2173                else:
2174                    def collect_symbols(user, definer):
2175                        return ()
2176
2177                data = []
2178                if args.revert:
2179                    for assoc_lib in sorted(lib.users):
2180                        data.append((assoc_lib.path,
2181                                     collect_symbols(assoc_lib, lib)))
2182                else:
2183                    for assoc_lib in sorted(lib.deps):
2184                        data.append((assoc_lib.path,
2185                                     collect_symbols(lib, assoc_lib)))
2186                results.append((name, data))
2187        results.sort()
2188
2189        if args.leaf:
2190            for name, deps in results:
2191                if not deps:
2192                    print(name)
2193        else:
2194            for name, assoc_libs in results:
2195                print(name)
2196                for assoc_lib, symbols in assoc_libs:
2197                    print('\t' + assoc_lib)
2198                    for symbol in symbols:
2199                        print('\t\t' + symbol)
2200        return 0
2201
2202
2203class DepsClosureCommand(ELFGraphCommand):
2204    def __init__(self):
2205        super(DepsClosureCommand, self).__init__(
2206                'deps-closure', help='Find transitive closure of dependencies')
2207
2208    def add_argparser_options(self, parser):
2209        super(DepsClosureCommand, self).add_argparser_options(parser)
2210
2211        parser.add_argument('lib', nargs='+',
2212                            help='root set of the shared libraries')
2213
2214        parser.add_argument('--exclude-lib', action='append', default=[],
2215                            help='libraries to be excluded')
2216
2217        parser.add_argument('--exclude-ndk', action='store_true',
2218                            help='exclude ndk libraries')
2219
2220    def main(self, args):
2221        generic_refs, graph = self.create_from_args(args)
2222
2223        # Find root/excluded libraries by their paths.
2224        def report_error(path):
2225            print('error: no such lib: {}'.format(path), file=sys.stderr)
2226        root_libs = graph.get_libs(args.lib, report_error)
2227        excluded_libs = graph.get_libs(args.exclude_lib, report_error)
2228
2229        # Compute and print the closure.
2230        if args.exclude_ndk:
2231            def is_excluded_libs(lib):
2232                return lib.is_ndk or lib in excluded_libs
2233        else:
2234            def is_excluded_libs(lib):
2235                return lib in excluded_libs
2236
2237        closure = graph.compute_closure(root_libs, is_excluded_libs)
2238        for lib in sorted_lib_path_list(closure):
2239            print(lib)
2240        return 0
2241
2242
2243class TaggedDict(object):
2244    TAGS = {
2245        'll_ndk', 'll_ndk_indirect', 'sp_ndk', 'sp_ndk_indirect',
2246        'vndk_sp', 'vndk_sp_indirect', 'vndk_sp_indirect_private',
2247        'vndk',
2248        'fwk_only', 'fwk_only_rs',
2249        'sp_hal', 'sp_hal_dep',
2250        'vnd_only',
2251        'remove',
2252    }
2253
2254    _TAG_ALIASES = {
2255        'hl_ndk': 'fwk_only',  # Treat HL-NDK as FWK-ONLY.
2256        'vndk_indirect': 'vndk',  # Legacy
2257        'vndk_sp_hal': 'vndk_sp',  # Legacy
2258        'vndk_sp_both': 'vndk_sp',  # Legacy
2259    }
2260
2261    @classmethod
2262    def _normalize_tag(cls, tag):
2263        tag = tag.lower().replace('-', '_')
2264        tag = cls._TAG_ALIASES.get(tag, tag)
2265        if tag not in cls.TAGS:
2266            raise ValueError('unknown lib tag ' + tag)
2267        return tag
2268
2269    _LL_NDK_VIS = {'ll_ndk', 'll_ndk_indirect'}
2270    _SP_NDK_VIS = {'ll_ndk', 'll_ndk_indirect', 'sp_ndk', 'sp_ndk_indirect'}
2271    _VNDK_SP_VIS = {'ll_ndk', 'sp_ndk', 'vndk_sp', 'vndk_sp_indirect',
2272                    'vndk_sp_indirect_private', 'fwk_only_rs'}
2273    _FWK_ONLY_VIS = {'ll_ndk', 'll_ndk_indirect', 'sp_ndk', 'sp_ndk_indirect',
2274                     'vndk_sp', 'vndk_sp_indirect', 'vndk_sp_indirect_private',
2275                     'vndk', 'fwk_only', 'fwk_only_rs', 'sp_hal'}
2276    _SP_HAL_VIS = {'ll_ndk', 'sp_ndk', 'vndk_sp', 'sp_hal', 'sp_hal_dep'}
2277
2278    _TAG_VISIBILITY = {
2279        'll_ndk': _LL_NDK_VIS,
2280        'll_ndk_indirect': _LL_NDK_VIS,
2281        'sp_ndk': _SP_NDK_VIS,
2282        'sp_ndk_indirect': _SP_NDK_VIS,
2283
2284        'vndk_sp': _VNDK_SP_VIS,
2285        'vndk_sp_indirect': _VNDK_SP_VIS,
2286        'vndk_sp_indirect_private': _VNDK_SP_VIS,
2287
2288        'vndk': {'ll_ndk', 'sp_ndk', 'vndk_sp', 'vndk_sp_indirect', 'vndk'},
2289
2290        'fwk_only': _FWK_ONLY_VIS,
2291        'fwk_only_rs': _FWK_ONLY_VIS,
2292
2293        'sp_hal': _SP_HAL_VIS,
2294        'sp_hal_dep': _SP_HAL_VIS,
2295
2296        'vnd_only': {'ll_ndk', 'sp_ndk', 'vndk_sp', 'vndk_sp_indirect',
2297                     'vndk', 'sp_hal', 'sp_hal_dep', 'vnd_only'},
2298
2299        'remove': set(),
2300    }
2301
2302    del _LL_NDK_VIS, _SP_NDK_VIS, _VNDK_SP_VIS, _FWK_ONLY_VIS, _SP_HAL_VIS
2303
2304    @classmethod
2305    def is_tag_visible(cls, from_tag, to_tag):
2306        return to_tag in cls._TAG_VISIBILITY[from_tag]
2307
2308    def __init__(self):
2309        self._path_tag = dict()
2310        for tag in self.TAGS:
2311            setattr(self, tag, set())
2312
2313    def add(self, tag, lib):
2314        lib_set = getattr(self, tag)
2315        lib_set.add(lib)
2316        self._path_tag[lib] = tag
2317
2318    def get_path_tag(self, lib):
2319        try:
2320            return self._path_tag[lib]
2321        except KeyError:
2322            return self.get_path_tag_default(lib)
2323
2324    def get_path_tag_default(self, lib):
2325        raise NotImplementedError()
2326
2327    def is_path_visible(self, from_lib, to_lib):
2328        return self.is_tag_visible(self.get_path_tag(from_lib),
2329                                   self.get_path_tag(to_lib))
2330
2331
2332class TaggedPathDict(TaggedDict):
2333    def load_from_csv(self, fp):
2334        reader = csv.reader(fp)
2335
2336        # Read first row and check the existence of the header.
2337        try:
2338            row = next(reader)
2339        except StopIteration:
2340            return
2341
2342        try:
2343            path_col = row.index('Path')
2344            tag_col = row.index('Tag')
2345        except ValueError:
2346            path_col = 0
2347            tag_col = 1
2348            self.add(self._normalize_tag(row[tag_col]), row[path_col])
2349
2350        # Read the rest of rows.
2351        for row in reader:
2352            self.add(self._normalize_tag(row[tag_col]), row[path_col])
2353
2354    @staticmethod
2355    def create_from_csv(fp):
2356        d = TaggedPathDict()
2357        d.load_from_csv(fp)
2358        return d
2359
2360    @staticmethod
2361    def create_from_csv_path(path):
2362        with open(path, 'r') as fp:
2363            return TaggedPathDict.create_from_csv(fp)
2364
2365    @staticmethod
2366    def _enumerate_paths(pattern):
2367        if '${LIB}' in pattern:
2368            yield pattern.replace('${LIB}', 'lib')
2369            yield pattern.replace('${LIB}', 'lib64')
2370        else:
2371            yield pattern
2372
2373    def add(self, tag, path):
2374        for path in self._enumerate_paths(path):
2375            super(TaggedPathDict, self).add(tag, path)
2376
2377    def get_path_tag_default(self, path):
2378        return 'vnd_only' if path.startswith('/vendor') else 'fwk_only'
2379
2380
2381class TaggedLibDict(TaggedDict):
2382    @staticmethod
2383    def create_from_graph(graph, tagged_paths, generic_refs=None):
2384        d = TaggedLibDict()
2385
2386        for lib in graph.lib_pt[PT_SYSTEM].values():
2387            d.add(tagged_paths.get_path_tag(lib.path), lib)
2388
2389        sp_lib = graph.compute_sp_lib(generic_refs)
2390        for lib in graph.lib_pt[PT_VENDOR].values():
2391            if lib in sp_lib.sp_hal:
2392                d.add('sp_hal', lib)
2393            elif lib in sp_lib.sp_hal_dep:
2394                d.add('sp_hal_dep', lib)
2395            else:
2396                d.add('vnd_only', lib)
2397        return d
2398
2399    def get_path_tag_default(self, lib):
2400        return 'vnd_only' if lib.path.startswith('/vendor') else 'fwk_only'
2401
2402
2403class ModuleInfo(object):
2404    def __init__(self, module_info_path=None):
2405        if not module_info_path:
2406            self.json = dict()
2407        else:
2408            with open(module_info_path, 'r') as f:
2409                self.json = json.load(f)
2410
2411    def get_module_path(self, installed_path):
2412        for name, module in  self.json.items():
2413            if any(path.endswith(installed_path)
2414                   for path in module['installed']):
2415                return module['path']
2416        return []
2417
2418
2419class CheckDepCommand(ELFGraphCommand):
2420    def __init__(self):
2421        super(CheckDepCommand, self).__init__(
2422                'check-dep', help='Check the eligible dependencies')
2423
2424    def add_argparser_options(self, parser):
2425        super(CheckDepCommand, self).add_argparser_options(parser)
2426
2427        parser.add_argument('--tag-file', required=True)
2428
2429        parser.add_argument('--module-info')
2430
2431    @staticmethod
2432    def _dump_dep(lib, bad_deps, module_info):
2433        print(lib.path)
2434        for module_path in sorted(module_info.get_module_path(lib.path)):
2435            print('\tMODULE_PATH:', module_path)
2436        for dep in sorted(bad_deps):
2437            print('\t' + dep.path)
2438            for symbol in lib.get_dep_linked_symbols(dep):
2439                print('\t\t' + symbol)
2440
2441    def _check_eligible_vndk_dep(self, graph, tagged_libs, module_info):
2442        """Check whether eligible sets are self-contained."""
2443        num_errors = 0
2444
2445        indirect_libs = (tagged_libs.ll_ndk_indirect | \
2446                         tagged_libs.sp_ndk_indirect | \
2447                         tagged_libs.vndk_sp_indirect_private | \
2448                         tagged_libs.fwk_only_rs)
2449
2450        eligible_libs = (tagged_libs.ll_ndk | tagged_libs.sp_ndk | \
2451                         tagged_libs.vndk_sp | tagged_libs.vndk_sp_indirect | \
2452                         tagged_libs.vndk)
2453
2454        # Check eligible vndk is self-contained.
2455        for lib in sorted(eligible_libs):
2456            bad_deps = []
2457            for dep in lib.deps:
2458                if dep not in eligible_libs and dep not in indirect_libs:
2459                    print('error: eligible lib "{}" should not depend on '
2460                          'non-eligible lib "{}".'.format(lib.path, dep.path),
2461                          file=sys.stderr)
2462                    bad_deps.append(dep)
2463                    num_errors += 1
2464            if bad_deps:
2465                self._dump_dep(lib, bad_deps, module_info)
2466
2467        # Check the libbinder dependencies.
2468        for lib in sorted(eligible_libs):
2469            bad_deps = []
2470            for dep in lib.deps:
2471                if os.path.basename(dep.path) == 'libbinder.so':
2472                    print('error: eligible lib "{}" should not depend on '
2473                          'libbinder.so.'.format(lib.path), file=sys.stderr)
2474                    bad_deps.append(dep)
2475                    num_errors += 1
2476            if bad_deps:
2477                self._dump_dep(lib, bad_deps, module_info)
2478
2479        return num_errors
2480
2481    def _check_vendor_dep(self, graph, tagged_libs, module_info):
2482        """Check whether vendor libs are depending on non-eligible libs."""
2483        num_errors = 0
2484
2485        vendor_libs = set(graph.lib_pt[PT_VENDOR].values())
2486
2487        eligible_libs = (tagged_libs.ll_ndk | tagged_libs.sp_ndk | \
2488                         tagged_libs.vndk_sp | tagged_libs.vndk_sp_indirect | \
2489                         tagged_libs.vndk)
2490
2491        for lib in sorted(vendor_libs):
2492            bad_deps = []
2493            for dep in lib.deps:
2494                if dep not in vendor_libs and dep not in eligible_libs:
2495                    print('error: vendor lib "{}" depends on non-eligible '
2496                          'lib "{}".'.format(lib.path, dep.path),
2497                          file=sys.stderr)
2498                    bad_deps.append(dep)
2499                    num_errors += 1
2500            if bad_deps:
2501                self._dump_dep(lib, bad_deps, module_info)
2502
2503        return num_errors
2504
2505    def main(self, args):
2506        generic_refs, graph = self.create_from_args(args)
2507
2508        tagged_paths = TaggedPathDict.create_from_csv_path(args.tag_file)
2509        tagged_libs = TaggedLibDict.create_from_graph(graph, tagged_paths)
2510
2511        module_info = ModuleInfo(args.module_info)
2512
2513        num_errors = self._check_eligible_vndk_dep(graph, tagged_libs,
2514                                                   module_info)
2515        num_errors += self._check_vendor_dep(graph, tagged_libs, module_info)
2516
2517        return 0 if num_errors == 0 else 1
2518
2519
2520class DepGraphCommand(ELFGraphCommand):
2521    def __init__(self):
2522        super(DepGraphCommand, self).__init__(
2523                'dep-graph', help='Show the eligible dependencies graph')
2524
2525    def add_argparser_options(self, parser):
2526        super(DepGraphCommand, self).add_argparser_options(parser)
2527
2528        parser.add_argument('--tag-file', required=True)
2529        parser.add_argument('--output', '-o', help='output directory')
2530
2531    def _get_tag_from_lib(self, lib, tagged_paths):
2532        tag_hierarchy = dict()
2533        for tag in TaggedPathDict.TAGS:
2534            if tag in {'sp_hal', 'sp_hal_dep', 'vnd_only'}:
2535                tag_hierarchy[tag] = 'vendor.private.{}'.format(tag)
2536            else:
2537                vendor_visible = TaggedPathDict.is_tag_visible('vnd_only', tag)
2538                pub = 'public' if vendor_visible else 'private'
2539                tag_hierarchy[tag] = 'system.{}.{}'.format(pub, tag)
2540
2541        return tag_hierarchy[tagged_paths.get_path_tag(lib.path)]
2542
2543    def _check_if_allowed(self, my_tag, other_tag):
2544        my = my_tag.split('.')
2545        other = other_tag.split('.')
2546        if my[0] == 'system' and other[0] == 'vendor':
2547            return False
2548        if my[0] == 'vendor' and other[0] == 'system' \
2549                             and other[1] == 'private':
2550            return False
2551        return True
2552
2553    def _get_dep_graph(self, graph, tagged_paths):
2554        data = []
2555        violate_libs = dict()
2556        system_libs = graph.lib_pt[PT_SYSTEM].values()
2557        vendor_libs = graph.lib_pt[PT_VENDOR].values()
2558        for lib in itertools.chain(system_libs, vendor_libs):
2559            tag = self._get_tag_from_lib(lib, tagged_paths)
2560            violate_count = 0
2561            lib_item = {
2562                'name': lib.path,
2563                'tag': tag,
2564                'depends': [],
2565                'violates': [],
2566            }
2567            for dep in lib.deps:
2568                if self._check_if_allowed(tag,
2569                        self._get_tag_from_lib(dep, tagged_paths)):
2570                    lib_item['depends'].append(dep.path)
2571                else:
2572                    lib_item['violates'].append(dep.path)
2573                    violate_count += 1;
2574            lib_item['violate_count'] = violate_count
2575            if violate_count > 0:
2576                if not tag in violate_libs:
2577                    violate_libs[tag] = []
2578                violate_libs[tag].append((lib.path, violate_count))
2579            data.append(lib_item)
2580        return data, violate_libs
2581
2582    def main(self, args):
2583        generic_refs, graph = self.create_from_args(args)
2584
2585        tagged_paths = TaggedPathDict.create_from_csv_path(args.tag_file)
2586        data, violate_libs = self._get_dep_graph(graph, tagged_paths)
2587        data.sort(key=lambda lib_item: (lib_item['tag'],
2588                                        lib_item['violate_count']))
2589        for libs in violate_libs.values():
2590            libs.sort(key=lambda libs: libs[1], reverse=True)
2591
2592        makedirs(args.output, exist_ok=True)
2593        script_dir = os.path.dirname(os.path.abspath(__file__))
2594        for name in ('index.html', 'dep-graph.js', 'dep-graph.css'):
2595            shutil.copyfile(os.path.join(script_dir, 'assets/visual', name),
2596                            os.path.join(args.output, name))
2597        with open(os.path.join(args.output, 'dep-data.js'), 'w') as f:
2598            f.write('var violatedLibs = ' + json.dumps(violate_libs) +
2599                    '\nvar depData = ' + json.dumps(data) + ';')
2600
2601        return 0
2602
2603
2604class VNDKSPCommand(ELFGraphCommand):
2605    def __init__(self):
2606        super(VNDKSPCommand, self).__init__(
2607                'vndk-sp', help='List pre-defined VNDK-SP')
2608
2609    def add_argparser_options(self, parser):
2610        super(VNDKSPCommand, self).add_argparser_options(parser)
2611
2612    def main(self, args):
2613        generic_refs, graph = self.create_from_args(args)
2614
2615        vndk_sp = graph.compute_predefined_vndk_sp()
2616        for lib in sorted_lib_path_list(vndk_sp):
2617            print('vndk-sp:', lib)
2618        vndk_sp_indirect = graph.compute_predefined_vndk_sp_indirect()
2619        for lib in sorted_lib_path_list(vndk_sp_indirect):
2620            print('vndk-sp-indirect:', lib)
2621        return 0
2622
2623
2624class SpLibCommand(ELFGraphCommand):
2625    def __init__(self):
2626        super(SpLibCommand, self).__init__(
2627                'sp-lib', help='Define sp-ndk, sp-hal, and vndk-sp')
2628
2629    def add_argparser_options(self, parser):
2630        super(SpLibCommand, self).add_argparser_options(parser)
2631
2632    def main(self, args):
2633        generic_refs, graph = self.create_from_args(args)
2634        print_sp_lib(graph.compute_sp_lib(generic_refs))
2635        return 0
2636
2637
2638def main():
2639    parser = argparse.ArgumentParser()
2640    subparsers = parser.add_subparsers(dest='subcmd')
2641    subcmds = dict()
2642
2643    def register_subcmd(cmd):
2644        subcmds[cmd.name] = cmd
2645        cmd.add_argparser_options(
2646                subparsers.add_parser(cmd.name, help=cmd.help))
2647
2648    register_subcmd(ELFDumpCommand())
2649    register_subcmd(CreateGenericRefCommand())
2650    register_subcmd(VNDKCommand())
2651    register_subcmd(VNDKCapCommand())
2652    register_subcmd(DepsCommand())
2653    register_subcmd(DepsClosureCommand())
2654    register_subcmd(DepsInsightCommand())
2655    register_subcmd(CheckDepCommand())
2656    register_subcmd(DepGraphCommand())
2657    register_subcmd(SpLibCommand())
2658    register_subcmd(VNDKSPCommand())
2659
2660    args = parser.parse_args()
2661    if not args.subcmd:
2662        parser.print_help()
2663        sys.exit(1)
2664    return subcmds[args.subcmd].main(args)
2665
2666if __name__ == '__main__':
2667    sys.exit(main())
2668