• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python3
2
3#
4# Copyright (C) 2018 The Android Open Source Project
5#
6# Licensed under the Apache License, Version 2.0 (the "License");
7# you may not use this file except in compliance with the License.
8# You may obtain a copy of the License at
9#
10#      http://www.apache.org/licenses/LICENSE-2.0
11#
12# Unless required by applicable law or agreed to in writing, software
13# distributed under the License is distributed on an "AS IS" BASIS,
14# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15# See the License for the specific language governing permissions and
16# limitations under the License.
17#
18
19"""This module implements a Android.bp parser."""
20
21import collections
22import glob
23import itertools
24import os
25import re
26import sys
27
28
29#------------------------------------------------------------------------------
30# Python 2 compatibility
31#------------------------------------------------------------------------------
32
33if sys.version_info >= (3,):
34    py3_chr = chr  # pylint: disable=invalid-name
35else:
36    def py3_chr(codepoint):
37        """Convert an integer character codepoint into a utf-8 string."""
38        return unichr(codepoint).encode('utf-8')
39
40try:
41    from enum import Enum
42except ImportError:
43    class _Enum(object):  # pylint: disable=too-few-public-methods
44        """A name-value pair for each enumeration."""
45
46        __slot__ = ('name', 'value')
47
48
49        def __init__(self, name, value):
50            """Create a name-value pair."""
51            self.name = name
52            self.value = value
53
54
55        def __repr__(self):
56            """Return the name of the enumeration."""
57            return self.name
58
59
60    class _EnumMeta(type):  # pylint: disable=too-few-public-methods
61        """Metaclass for Enum base class."""
62
63        def __new__(mcs, name, bases, attrs):
64            """Collects enumerations from attributes of the derived classes."""
65            enums = []
66            new_attrs = {'_enums': enums}
67
68            for key, value in attrs.iteritems():
69                if key.startswith('_'):
70                    new_attrs[key] = value
71                else:
72                    item = _Enum(key, value)
73                    enums.append(item)
74                    new_attrs[key] = item
75
76            return type.__new__(mcs, name, bases, new_attrs)
77
78
79        def __iter__(cls):
80            """Iterate the list of enumerations."""
81            return iter(cls._enums)
82
83
84    class Enum(object):  # pylint: disable=too-few-public-methods
85        """Enum base class."""
86        __metaclass__ = _EnumMeta
87
88
89#------------------------------------------------------------------------------
90# Lexer
91#------------------------------------------------------------------------------
92
93class Token(Enum):  # pylint: disable=too-few-public-methods
94    """Token enumerations."""
95
96    EOF = 0
97
98    IDENT = 1
99    LPAREN = 2
100    RPAREN = 3
101    LBRACKET = 4
102    RBRACKET = 5
103    LBRACE = 6
104    RBRACE = 7
105    COLON = 8
106    ASSIGN = 9
107    ASSIGNPLUS = 10
108    PLUS = 11
109    COMMA = 12
110    STRING = 13
111    INTEGER = 14
112
113    COMMENT = 15
114    SPACE = 16
115
116
117class LexerError(ValueError):
118    """Lexer error exception class."""
119
120    def __init__(self, buf, pos, message):
121        """Create a lexer error exception object."""
122        super(LexerError, self).__init__(message)
123        self.message = message
124        self.line, self.column = Lexer.compute_line_column(buf, pos)
125
126
127    def __str__(self):
128        """Convert lexer error to string representation."""
129        return 'LexerError: {}:{}: {}'.format(
130            self.line, self.column, self.message)
131
132
133class Lexer(object):
134    """Lexer to tokenize the input string."""
135
136    def __init__(self, buf, offset=0, path=None):
137        """Tokenize the source code in buf starting from offset.
138
139        Args:
140            buf (string) The source code to be tokenized.
141            offset (int) The position to start.
142        """
143
144        self.buf = buf
145
146        self.start = None
147        self.end = offset
148        self.token = None
149        self.literal = None
150        self.path = path
151
152        self._next()
153
154
155    def consume(self, *tokens):
156        """Consume one or more token."""
157
158        for token in tokens:
159            if token == self.token:
160                self._next()
161            else:
162                raise LexerError(self.buf, self.start,
163                                 'unexpected token ' + self.token.name)
164
165
166    def _next(self):
167        """Read next non-comment non-space token."""
168
169        buf_len = len(self.buf)
170        while self.end < buf_len:
171            self.start = self.end
172            self.token, self.end, self.literal = self.lex(self.buf, self.start)
173            if self.token != Token.SPACE and self.token != Token.COMMENT:
174                return
175
176        self.start = self.end
177        self.token = Token.EOF
178        self.literal = None
179
180
181    @staticmethod
182    def compute_line_column(buf, pos):
183        """Compute the line number and the column number of a given position in
184        the buffer."""
185
186        prior = buf[0:pos]
187        newline_pos = prior.rfind('\n')
188        if newline_pos == -1:
189            return (1, pos + 1)
190        return (prior.count('\n') + 1, pos - newline_pos)
191
192
193    UNICODE_CHARS_PATTERN = re.compile('[^\\\\\\n"]+')
194
195
196    ESCAPE_CHAR_TABLE = {
197        'a': '\a', 'b': '\b', 'f': '\f', 'n': '\n', 'r': '\r', 't': '\t',
198        'v': '\v', '\\': '\\', '\'': '\'', '\"': '\"',
199    }
200
201
202    OCT_TABLE = {str(i) for i in range(8)}
203
204
205    @staticmethod
206    def decode_oct(buf, offset, start, end):
207        """Read characters from buf[start:end] and interpret them as an octal
208        integer."""
209
210        if end > len(buf):
211            raise LexerError(buf, offset, 'bad octal escape sequence')
212        try:
213            codepoint = int(buf[start:end], 8)
214        except ValueError:
215            raise LexerError(buf, offset, 'bad octal escape sequence')
216        if codepoint > 0xff:
217            raise LexerError(buf, offset, 'bad octal escape sequence')
218        return codepoint
219
220
221    @staticmethod
222    def decode_hex(buf, offset, start, end):
223        """Read characters from buf[start:end] and interpret them as a
224        hexadecimal integer."""
225
226        if end > len(buf):
227            raise LexerError(buf, offset, 'bad hex escape sequence')
228        try:
229            return int(buf[start:end], 16)
230        except ValueError:
231            raise LexerError(buf, offset, 'bad hex escape sequence')
232
233
234    @classmethod
235    def lex_interpreted_string(cls, buf, offset):
236        """Tokenize a golang interpreted string.
237
238        Args:
239            buf (str)    The source code buffer.
240            offset (int) The position to find a golang interpreted string
241                         literal.
242
243        Returns:
244            A tuple with the end of matched buffer and the interpreted string
245            literal.
246        """
247
248        buf_len = len(buf)
249        pos = offset + 1
250        literal = ''
251        while pos < buf_len:
252            # Match unicode characters
253            match = cls.UNICODE_CHARS_PATTERN.match(buf, pos)
254            if match:
255                literal += match.group(0)
256                pos = match.end()
257            # Read the next character
258            try:
259                char = buf[pos]
260            except IndexError:
261                raise LexerError(buf, pos,
262                                 'unclosed interpreted string literal')
263            if char == '\\':
264                # Escape sequences
265                try:
266                    char = buf[pos + 1]
267                except IndexError:
268                    raise LexerError(buf, pos, 'bad escape sequence')
269                if char in cls.OCT_TABLE:
270                    literal += chr(cls.decode_oct(buf, pos, pos + 1, pos + 4))
271                    pos += 4
272                elif char == 'x':
273                    literal += chr(cls.decode_hex(buf, pos, pos + 2, pos + 4))
274                    pos += 4
275                elif char == 'u':
276                    literal += py3_chr(
277                        cls.decode_hex(buf, pos, pos + 2, pos + 6))
278                    pos += 6
279                elif char == 'U':
280                    literal += py3_chr(
281                        cls.decode_hex(buf, pos, pos + 2, pos + 10))
282                    pos += 10
283                else:
284                    try:
285                        literal += cls.ESCAPE_CHAR_TABLE[char]
286                        pos += 2
287                    except KeyError:
288                        raise LexerError(buf, pos, 'bad escape sequence')
289                continue
290            if char == '"':
291                # End of string literal
292                return (pos + 1, literal)
293            raise LexerError(buf, pos, 'unclosed interpreted string literal')
294
295
296    @classmethod
297    def lex_string(cls, buf, offset):
298        """Tokenize a golang string literal.
299
300        Args:
301            buf (str)    The source code buffer.
302            offset (int) The position to find a golang string literal.
303
304        Returns:
305            A tuple with the end of matched buffer and the interpreted string
306            literal.
307        """
308
309        char = buf[offset]
310        if char == '`':
311            try:
312                end = buf.index('`', offset + 1)
313                return (end + 1, buf[offset + 1 : end])
314            except ValueError:
315                raise LexerError(buf, len(buf), 'unclosed raw string literal')
316        if char == '"':
317            return cls.lex_interpreted_string(buf, offset)
318        raise LexerError(buf, offset, 'no string literal start character')
319
320
321    LEXER_PATTERNS = (
322        (Token.IDENT, '[A-Za-z_][0-9A-Za-z_]*'),
323        (Token.LPAREN, '\\('),
324        (Token.RPAREN, '\\)'),
325        (Token.LBRACKET, '\\['),
326        (Token.RBRACKET, '\\]'),
327        (Token.LBRACE, '\\{'),
328        (Token.RBRACE, '\\}'),
329        (Token.COLON, ':'),
330        (Token.ASSIGN, '='),
331        (Token.ASSIGNPLUS, '\\+='),
332        (Token.PLUS, '\\+'),
333        (Token.COMMA, ','),
334        (Token.STRING, '["`]'),
335        (Token.INTEGER, '-{0,1}[0-9]+'),
336
337        (Token.COMMENT,
338         '/(?:(?:/[^\\n]*)|(?:\\*(?:(?:[^*]*)|(?:\\*+[^/*]))*\\*+/))'),
339        (Token.SPACE, '\\s+'),
340    )
341
342
343    LEXER_MATCHER = re.compile('|'.join(
344        '(' + pattern + ')' for _, pattern in LEXER_PATTERNS))
345
346
347    @classmethod
348    def lex(cls, buf, offset):
349        """Tokenize a token from buf[offset].
350
351        Args:
352            buf (string) The source code buffer.
353            offset (int) The position to find and tokenize a token.
354
355        Return:
356            A tuple with three elements.  The first element is the token id.
357            The second element is the end of the token.  The third element is
358            the value for strings or identifiers.
359        """
360
361        match = cls.LEXER_MATCHER.match(buf, offset)
362        if not match:
363            raise LexerError(buf, offset, 'unknown token')
364        token = cls.LEXER_PATTERNS[match.lastindex - 1][0]
365
366        if token == Token.STRING:
367            end, literal = cls.lex_string(buf, offset)
368        else:
369            end = match.end()
370            if token in {Token.IDENT, Token.INTEGER}:
371                literal = buf[offset:end]
372            else:
373                literal = None
374
375        return (token, end, literal)
376
377
378#------------------------------------------------------------------------------
379# AST
380#------------------------------------------------------------------------------
381
382class Expr(object):  # pylint: disable=too-few-public-methods
383    """Base class for all expressions."""
384
385    def eval(self, env):
386        """Evaluate the expression under an environment."""
387        raise NotImplementedError()
388
389
390class String(Expr, str):
391    """String constant literal."""
392
393    def eval(self, env):
394        """Evaluate the string expression under an environment."""
395        return self
396
397
398class Bool(Expr):  # pylint: disable=too-few-public-methods
399    """Boolean constant literal."""
400
401    __slots__ = ('value',)
402
403
404    def __init__(self, value):
405        """Create a boolean constant literal."""
406        self.value = value
407
408
409    def __repr__(self):
410        """Convert a boolean constant literal to string representation."""
411        return repr(self.value)
412
413
414    def __bool__(self):
415        """Convert boolean constant literal to Python bool type."""
416        return self.value
417
418    __nonzero__ = __bool__
419
420
421    def __eq__(self, rhs):
422        """Compare whether two instances are equal."""
423        return self.value == rhs.value
424
425
426    def __hash__(self):
427        """Compute the hashed value."""
428        return hash(self.value)
429
430
431    def eval(self, env):
432        """Evaluate the boolean expression under an environment."""
433        return self
434
435
436class Integer(Expr):  # pylint: disable=too-few-public-methods
437    """Integer constant literal."""
438
439    __slots__ = ('value',)
440
441
442    def __init__(self, value):
443        """Create an integer constant literal."""
444        self.value = value
445
446
447    def __repr__(self):
448        """Convert an integer constant literal to string representation."""
449        return repr(self.value)
450
451
452    def __bool__(self):
453        """Convert an integer constant literal to Python bool type."""
454        return bool(self.value)
455
456    __nonzero__ = __bool__
457
458
459    def __int__(self):
460        """Convert an integer constant literal to Python int type."""
461        return self.value
462
463
464    def __eq__(self, rhs):
465        """Compare whether two instances are equal."""
466        return self.value == rhs.value
467
468
469    def __hash__(self):
470        """Compute the hashed value."""
471        return hash(self.value)
472
473
474    def eval(self, env):
475        """Evaluate the integer expression under an environment."""
476        return self
477
478
479class VarRef(Expr):  # pylint: disable=too-few-public-methods
480    """A reference to a variable."""
481
482    def __init__(self, name, value):
483        """Create a variable reference with a name and the value under static
484        scoping."""
485        self.name = name
486        self.value = value
487
488
489    def __repr__(self):
490        """Convert a variable reference to string representation."""
491        return self.name
492
493
494    def eval(self, env):
495        """Evaluate the identifier under an environment."""
496        if self.value is None:
497            return env[self.name].eval(env)
498        return self.value.eval(env)
499
500
501class List(Expr, list):
502    """List expression."""
503
504    def eval(self, env):
505        """Evaluate list elements under an environment."""
506        return List(item.eval(env) for item in self)
507
508
509class Dict(Expr, collections.OrderedDict):
510    """Dictionary expression."""
511
512    def __repr__(self):
513        attrs = ', '.join(key + ': ' + repr(value)
514                          for key, value in self.items())
515        return '{' + attrs + '}'
516
517
518    def eval(self, env):
519        """Evaluate dictionary values under an environment."""
520        return Dict((key, value.eval(env)) for key, value in self.items())
521
522
523class Concat(Expr):  # pylint: disable=too-few-public-methods
524    """List/string/integer plus operator."""
525
526    __slots__ = ('lhs', 'rhs')
527
528
529    def __init__(self, lhs, rhs):
530        """Create a list/string/integer plus expression."""
531        self.lhs = lhs
532        self.rhs = rhs
533
534
535    def __repr__(self):
536        return '(' + repr(self.lhs) + ' + ' + repr(self.rhs) + ')'
537
538
539    def eval(self, env):
540        """Evaluate list/string/integer plus operator under an environment."""
541        lhs = self.lhs.eval(env)
542        rhs = self.rhs.eval(env)
543        if isinstance(lhs, List) and isinstance(rhs, List):
544            return List(itertools.chain(lhs, rhs))
545        if isinstance(lhs, String) and isinstance(rhs, String):
546            return String(lhs + rhs)
547        if isinstance(lhs, Integer) and isinstance(rhs, Integer):
548            return Integer(int(lhs) + int(rhs))
549        raise TypeError('bad plus operands')
550
551
552#------------------------------------------------------------------------------
553# Parser
554#------------------------------------------------------------------------------
555
556class ParseError(ValueError):
557    """Parser error exception class."""
558
559    def __init__(self, lexer, message):
560        """Create a parser error exception object."""
561        super(ParseError, self).__init__(message)
562        self.message = message
563        self.line, self.column = \
564            Lexer.compute_line_column(lexer.buf, lexer.start)
565
566
567    def __str__(self):
568        """Convert parser error to string representation."""
569        return 'ParseError: {}:{}: {}'.format(
570            self.line, self.column, self.message)
571
572
573class Parser(object):
574    """Parser to parse Android.bp files."""
575
576    def __init__(self, lexer, inherited_env=None):
577        """Initialize the parser with the lexer."""
578        self.lexer = lexer
579
580        self.var_defs = []
581        self.vars = {} if inherited_env is None else dict(inherited_env)
582        self.modules = []
583
584
585    def parse(self):
586        """Parse AST from tokens."""
587        lexer = self.lexer
588        while lexer.token != Token.EOF:
589            if lexer.token == Token.IDENT:
590                ident = self.parse_ident_lvalue()
591                if lexer.token in {Token.ASSIGN, Token.ASSIGNPLUS}:
592                    self.parse_assign(ident, lexer.token)
593                elif lexer.token in {Token.LBRACE, Token.LPAREN}:
594                    self.parse_module_definition(ident)
595                else:
596                    raise ParseError(lexer,
597                                     'unexpected token ' + lexer.token.name)
598            else:
599                raise ParseError(lexer, 'unexpected token ' + lexer.token.name)
600        lexer.consume(Token.EOF)
601
602
603    def create_var_ref(self, name):
604        """Create a variable reference."""
605        return VarRef(name, self.vars.get(name))
606
607
608    def define_var(self, name, value):
609        """Define a variable."""
610        self.var_defs.append((name, value))
611        self.vars[name] = value
612
613
614    def parse_assign(self, ident, assign_token):
615        """Parse an assignment statement."""
616        lexer = self.lexer
617        lexer.consume(assign_token)
618        value = self.parse_expression()
619        if assign_token == Token.ASSIGNPLUS:
620            value = Concat(self.create_var_ref(ident), value)
621        self.define_var(ident, value)
622
623
624    def parse_module_definition(self, module_ident):
625        """Parse a module definition."""
626        properties = self.parse_dict()
627        properties['_path'] = String(self.lexer.path)
628        self.modules.append((module_ident, properties))
629
630
631    def parse_ident_lvalue(self):
632        """Parse an identifier as an l-value."""
633        ident = self.lexer.literal
634        self.lexer.consume(Token.IDENT)
635        return ident
636
637
638    def parse_ident_rvalue(self):
639        """Parse an identifier as a r-value.
640
641        Returns:
642            Returns VarRef if the literal is not 'true' nor 'false'.
643
644            Returns Bool(true/false) if the literal is either 'true' or 'false'.
645        """
646        lexer = self.lexer
647        if lexer.literal in {'true', 'false'}:
648            result = Bool(lexer.literal == 'true')
649        else:
650            result = self.create_var_ref(lexer.literal)
651        lexer.consume(Token.IDENT)
652        return result
653
654
655    def parse_string(self):
656        """Parse a string."""
657        lexer = self.lexer
658        string = String(lexer.literal)
659        lexer.consume(Token.STRING)
660        return string
661
662
663    def parse_integer(self):
664        """Parse an integer."""
665        lexer = self.lexer
666        integer = Integer(int(lexer.literal))
667        lexer.consume(Token.INTEGER)
668        return integer
669
670
671    def parse_operand(self):
672        """Parse an operand."""
673        lexer = self.lexer
674        token = lexer.token
675        if token == Token.STRING:
676            return self.parse_string()
677        if token == Token.IDENT:
678            return self.parse_ident_rvalue()
679        if token == Token.INTEGER:
680            return self.parse_integer()
681        if token == Token.LBRACKET:
682            return self.parse_list()
683        if token == Token.LBRACE:
684            return self.parse_dict()
685        if token == Token.LPAREN:
686            lexer.consume(Token.LPAREN)
687            operand = self.parse_expression()
688            lexer.consume(Token.RPAREN)
689            return operand
690        raise ParseError(lexer, 'unexpected token ' + token.name)
691
692
693    def parse_expression(self):
694        """Parse an expression."""
695        lexer = self.lexer
696        expr = self.parse_operand()
697        while lexer.token == Token.PLUS:
698            lexer.consume(Token.PLUS)
699            expr = Concat(expr, self.parse_operand())
700        return expr
701
702
703    def parse_list(self):
704        """Parse a list."""
705        result = List()
706        lexer = self.lexer
707        lexer.consume(Token.LBRACKET)
708        while lexer.token != Token.RBRACKET:
709            result.append(self.parse_expression())
710            if lexer.token == Token.COMMA:
711                lexer.consume(Token.COMMA)
712        lexer.consume(Token.RBRACKET)
713        return result
714
715
716    def parse_dict(self):
717        """Parse a dict."""
718        result = Dict()
719        lexer = self.lexer
720
721        is_func_syntax = lexer.token == Token.LPAREN
722        if is_func_syntax:
723            lexer.consume(Token.LPAREN)
724        else:
725            lexer.consume(Token.LBRACE)
726
727        while lexer.token != Token.RBRACE and lexer.token != Token.RPAREN:
728            if lexer.token != Token.IDENT:
729                raise ParseError(lexer, 'unexpected token ' + lexer.token.name)
730            key = self.parse_ident_lvalue()
731
732            if lexer.token == Token.ASSIGN:
733                lexer.consume(Token.ASSIGN)
734            else:
735                lexer.consume(Token.COLON)
736
737            value = self.parse_expression()
738            result[key] = value
739
740            if lexer.token == Token.COMMA:
741                lexer.consume(Token.COMMA)
742
743        if is_func_syntax:
744            lexer.consume(Token.RPAREN)
745        else:
746            lexer.consume(Token.RBRACE)
747
748        return result
749
750
751class RecursiveParser(object):
752    """This is a recursive parser which will parse blueprint files
753    recursively."""
754
755
756    # Default Blueprint file name
757    _DEFAULT_SUB_NAME = 'Android.bp'
758
759
760    def __init__(self):
761        """Initialize a recursive parser."""
762        self.visited = set()
763        self.modules = []
764
765
766    @staticmethod
767    def glob_sub_files(pattern, sub_file_name):
768        """List the sub file paths that match with the pattern with
769        wildcards."""
770
771        for path in glob.glob(pattern):
772            if os.path.isfile(path):
773                if os.path.basename(path) == sub_file_name:
774                    yield path
775            else:
776                sub_file_path = os.path.join(path, sub_file_name)
777                if os.path.isfile(sub_file_path):
778                    yield sub_file_path
779
780
781    @classmethod
782    def find_sub_files_from_env(cls, rootdir, env, use_subdirs,
783                                default_sub_name=_DEFAULT_SUB_NAME):
784        """Find the sub files from the names specified in build, subdirs, and
785        optional_subdirs."""
786
787        subs = []
788
789        if 'build' in env:
790            subs.extend(os.path.join(rootdir, filename)
791                        for filename in env['build'].eval(env))
792        if use_subdirs:
793            sub_name = env['subname'] if 'subname' in env else default_sub_name
794
795            if 'subdirs' in env:
796                for path in env['subdirs'].eval(env):
797                    subs.extend(cls.glob_sub_files(os.path.join(rootdir, path),
798                                                   sub_name))
799            if 'optional_subdirs' in env:
800                for path in env['optional_subdirs'].eval(env):
801                    subs.extend(cls.glob_sub_files(os.path.join(rootdir, path),
802                                                   sub_name))
803        return subs
804
805
806    @staticmethod
807    def _read_file(path, env):
808        """Read a blueprint file and return modules and the environment."""
809        with open(path, 'r') as bp_file:
810            content = bp_file.read()
811        parser = Parser(Lexer(content, path=path), env)
812        parser.parse()
813        return (parser.modules, parser.vars)
814
815
816    def _parse_file(self, path, env, evaluate):
817        """Parse a blueprint file and append to self.modules."""
818        modules, sub_env = self._read_file(path, env)
819        if evaluate:
820            modules = [(ident, attrs.eval(env)) for ident, attrs in modules]
821        self.modules += modules
822        return sub_env
823
824
825    def _parse_file_recursive(self, path, env, evaluate, use_subdirs):
826        """Parse a blueprint file and recursively."""
827
828        self.visited.add(path)
829
830        sub_env = self._parse_file(path, env, evaluate)
831
832        rootdir = os.path.dirname(path)
833
834        sub_file_paths = self.find_sub_files_from_env(rootdir, sub_env,
835                                                      use_subdirs)
836
837        sub_env.pop('build', None)
838        sub_env.pop('subdirs', None)
839        sub_env.pop('optional_subdirs', None)
840
841        for sub_file_path in sub_file_paths:
842            if sub_file_path not in self.visited:
843                self._parse_file_recursive(sub_file_path, sub_env, evaluate,
844                                           use_subdirs)
845        return sub_env
846
847
848    def _scan_and_parse_all_file_recursive(self, filename, path, env, evaluate):
849        """Scan all files with the specified name and parse them."""
850
851        rootdir = os.path.dirname(path)
852        assert rootdir, 'rootdir is empty but must be non-empty'
853
854        envs = [(rootdir, env)]
855        assert env is not None
856
857        # Scan directories for all blueprint files
858        for basedir, dirnames, filenames in os.walk(rootdir):
859            # Drop irrelevant environments
860            while not basedir.startswith(envs[-1][0]):
861                envs.pop()
862
863            # Filter sub directories
864            if '.out-dir' in filenames:
865                # Stop at OUT_DIR
866                dirnames[:] = []
867                continue
868            new_dirnames = []
869            for name in dirnames:
870                if name in {'.git', '.repo'}:
871                    continue
872                if basedir == rootdir and name == 'out':
873                    continue
874                new_dirnames.append(name)
875            dirnames[:] = new_dirnames
876
877            # Parse blueprint files
878            if filename in filenames:
879                try:
880                    path = os.path.join(basedir, filename)
881                    sys.stdout.flush()
882                    sub_env = self._parse_file_recursive(path, envs[-1][1],
883                                                         evaluate, False)
884                    assert sub_env is not None
885                    envs.append((basedir, sub_env))
886                except IOError:
887                    pass
888
889
890    def parse_file(self, path, env=None, evaluate=True,
891                   default_sub_name=_DEFAULT_SUB_NAME):
892        """Parse blueprint files recursively."""
893
894        if env is None:
895            env = {}
896
897        path = os.path.abspath(path)
898
899        sub_env = self._read_file(path, env)[1]
900
901        if 'subdirs' in sub_env or 'optional_subdirs' in sub_env:
902            self._parse_file_recursive(path, env, evaluate, True)
903        else:
904            self._scan_and_parse_all_file_recursive(
905                default_sub_name, path, env, evaluate)
906
907
908#------------------------------------------------------------------------------
909# Transformation
910#------------------------------------------------------------------------------
911
912def _build_named_modules_dict(modules):
913    """Build a name-to-module dict."""
914    named_modules = {}
915    for i, (ident, attrs) in enumerate(modules):
916        name = attrs.get('name')
917        if name is not None:
918            named_modules[name] = [ident, attrs, i]
919    return named_modules
920
921
922def _po_sorted_modules(modules, named_modules):
923    """Sort modules in post order."""
924    modules = [(ident, attrs, i) for i, (ident, attrs) in enumerate(modules)]
925
926    # Build module dependency graph.
927    edges = {}
928    for ident, attrs, module_id in modules:
929        defaults = attrs.get('defaults')
930        if defaults:
931            edges[module_id] = set(
932                named_modules[default][2] for default in defaults)
933
934    # Traverse module graph in post order.
935    post_order = []
936    visited = set()
937
938    def _traverse(module_id):
939        visited.add(module_id)
940        for next_module_id in edges.get(module_id, []):
941            if next_module_id not in visited:
942                _traverse(next_module_id)
943        post_order.append(modules[module_id])
944
945    for module_id in range(len(modules)):
946        if module_id not in visited:
947            _traverse(module_id)
948
949    return post_order
950
951
952def evaluate_default(attrs, default_attrs):
953    """Add default attributes if the keys do not exist."""
954    for key, value in default_attrs.items():
955        if key not in attrs:
956            attrs[key] = value
957        else:
958            attrs_value = attrs[key]
959            if isinstance(value, Dict) and isinstance(attrs_value, Dict):
960                attrs[key] = evaluate_default(attrs_value, value)
961    return attrs
962
963
964def evaluate_defaults(modules):
965    """Add default attributes to all modules if the keys do not exist."""
966    named_modules = _build_named_modules_dict(modules)
967    for ident, attrs, i in _po_sorted_modules(modules, named_modules):
968        for default in attrs.get('defaults', []):
969            attrs = evaluate_default(attrs, named_modules[default][1])
970        modules[i] = (ident, attrs)
971    return modules
972
973
974def fill_module_namespaces(root_bp, modules):
975    """Collect soong_namespace definition and set a `_namespace` property to
976    each module definitions."""
977
978    # Collect all namespaces
979    rootdir = os.path.dirname(os.path.abspath(root_bp))
980    namespaces = {rootdir}
981    for ident, attrs in modules:
982        if ident == 'soong_namespace':
983            namespaces.add(os.path.dirname(attrs['_path']))
984
985    # Build a path matcher for module namespaces
986    namespaces = sorted(namespaces, reverse=True)
987    path_matcher = re.compile(
988        '|'.join('(' + re.escape(x) + '/.*)' for x in namespaces))
989
990    # Trim the root directory prefix
991    rootdir_prefix_len = len(rootdir) + 1
992    namespaces = [path[rootdir_prefix_len:] for path in namespaces]
993
994    # Fill in module namespaces
995    for ident, attrs in modules:
996        match = path_matcher.match(attrs['_path'])
997        attrs['_namespace'] = namespaces[match.lastindex - 1]
998
999    return modules
1000