Implement multitree lunch

Test: (cd build/make/orchestrator/core ; ./test_lunch.py)
Change-Id: I4ba36a79abd13c42b986e3ba0d6d599c1cc73cb0
diff --git a/envsetup.sh b/envsetup.sh
index 87e6e0a..e7b8538 100644
--- a/envsetup.sh
+++ b/envsetup.sh
@@ -425,6 +425,61 @@
     complete -F _complete_android_module_names m
 }
 
+function multitree_lunch_help()
+{
+    echo "usage: lunch PRODUCT-VARIANT" 1>&2
+    echo "    Set up android build environment based on a product short name and variant" 1>&2
+    echo 1>&2
+    echo "lunch COMBO_FILE VARIANT" 1>&2
+    echo "    Set up android build environment based on a specific lunch combo file" 1>&2
+    echo "    and variant." 1>&2
+    echo 1>&2
+    echo "lunch --print [CONFIG]" 1>&2
+    echo "    Print the contents of a configuration.  If CONFIG is supplied, that config" 1>&2
+    echo "    will be flattened and printed.  If CONFIG is not supplied, the currently" 1>&2
+    echo "    selected config will be printed.  Returns 0 on success or nonzero on error." 1>&2
+    echo 1>&2
+    echo "lunch --list" 1>&2
+    echo "    List all possible combo files available in the current tree" 1>&2
+    echo 1>&2
+    echo "lunch --help" 1>&2
+    echo "lunch -h" 1>&2
+    echo "    Prints this message." 1>&2
+}
+
+function multitree_lunch()
+{
+    local code
+    local results
+    if $(echo "$1" | grep -q '^-') ; then
+        # Calls starting with a -- argument are passed directly and the function
+        # returns with the lunch.py exit code.
+        build/make/orchestrator/core/lunch.py "$@"
+        code=$?
+        if [[ $code -eq 2 ]] ; then
+          echo 1>&2
+          multitree_lunch_help
+          return $code
+        elif [[ $code -ne 0 ]] ; then
+          return $code
+        fi
+    else
+        # All other calls go through the --lunch variant of lunch.py
+        results=($(build/make/orchestrator/core/lunch.py --lunch "$@"))
+        code=$?
+        if [[ $code -eq 2 ]] ; then
+          echo 1>&2
+          multitree_lunch_help
+          return $code
+        elif [[ $code -ne 0 ]] ; then
+          return $code
+        fi
+
+        export TARGET_BUILD_COMBO=${results[0]}
+        export TARGET_BUILD_VARIANT=${results[1]}
+    fi
+}
+
 function choosetype()
 {
     echo "Build type choices are:"
diff --git a/orchestrator/core/lunch.py b/orchestrator/core/lunch.py
new file mode 100755
index 0000000..35dac73
--- /dev/null
+++ b/orchestrator/core/lunch.py
@@ -0,0 +1,329 @@
+#!/usr/bin/python3
+#
+# Copyright (C) 2022 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import argparse
+import glob
+import json
+import os
+import sys
+
+EXIT_STATUS_OK = 0
+EXIT_STATUS_ERROR = 1
+EXIT_STATUS_NEED_HELP = 2
+
+def FindDirs(path, name, ttl=6):
+    """Search at most ttl directories deep inside path for a directory called name."""
+    # The dance with subdirs is so that we recurse in sorted order.
+    subdirs = []
+    with os.scandir(path) as it:
+        for dirent in sorted(it, key=lambda x: x.name):
+            try:
+                if dirent.is_dir():
+                    if dirent.name == name:
+                        yield os.path.join(path, dirent.name)
+                    elif ttl > 0:
+                        subdirs.append(dirent.name)
+            except OSError:
+                # Consume filesystem errors, e.g. too many links, permission etc.
+                pass
+    for subdir in subdirs:
+        yield from FindDirs(os.path.join(path, subdir), name, ttl-1)
+
+
+def WalkPaths(path, matcher, ttl=10):
+    """Do a traversal of all files under path yielding each file that matches
+    matcher."""
+    # First look for files, then recurse into directories as needed.
+    # The dance with subdirs is so that we recurse in sorted order.
+    subdirs = []
+    with os.scandir(path) as it:
+        for dirent in sorted(it, key=lambda x: x.name):
+            try:
+                if dirent.is_file():
+                    if matcher(dirent.name):
+                        yield os.path.join(path, dirent.name)
+                if dirent.is_dir():
+                    if ttl > 0:
+                        subdirs.append(dirent.name)
+            except OSError:
+                # Consume filesystem errors, e.g. too many links, permission etc.
+                pass
+    for subdir in sorted(subdirs):
+        yield from WalkPaths(os.path.join(path, subdir), matcher, ttl-1)
+
+
+def FindFile(path, filename):
+    """Return a file called filename inside path, no more than ttl levels deep.
+
+    Directories are searched alphabetically.
+    """
+    for f in WalkPaths(path, lambda x: x == filename):
+        return f
+
+
+def FindConfigDirs(workspace_root):
+    """Find the configuration files in the well known locations inside workspace_root
+
+        <workspace_root>/build/orchestrator/multitree_combos
+           (AOSP devices, such as cuttlefish)
+
+        <workspace_root>/vendor/**/multitree_combos
+            (specific to a vendor and not open sourced)
+
+        <workspace_root>/device/**/multitree_combos
+            (specific to a vendor and are open sourced)
+
+    Directories are returned specifically in this order, so that aosp can't be
+    overridden, but vendor overrides device.
+    """
+
+    # TODO: When orchestrator is in its own git project remove the "make/" here
+    yield os.path.join(workspace_root, "build/make/orchestrator/multitree_combos")
+
+    dirs = ["vendor", "device"]
+    for d in dirs:
+        yield from FindDirs(os.path.join(workspace_root, d), "multitree_combos")
+
+
+def FindNamedConfig(workspace_root, shortname):
+    """Find the config with the given shortname inside workspace_root.
+
+    Config directories are searched in the order described in FindConfigDirs,
+    and inside those directories, alphabetically."""
+    filename = shortname + ".mcombo"
+    for config_dir in FindConfigDirs(workspace_root):
+        found = FindFile(config_dir, filename)
+        if found:
+            return found
+    return None
+
+
+def ParseProductVariant(s):
+    """Split a PRODUCT-VARIANT name, or return None if it doesn't match that pattern."""
+    split = s.split("-")
+    if len(split) != 2:
+        return None
+    return split
+
+
+def ChooseConfigFromArgs(workspace_root, args):
+    """Return the config file we should use for the given argument,
+    or null if there's no file that matches that."""
+    if len(args) == 1:
+        # Prefer PRODUCT-VARIANT syntax so if there happens to be a matching
+        # file we don't match that.
+        pv = ParseProductVariant(args[0])
+        if pv:
+            config = FindNamedConfig(workspace_root, pv[0])
+            if config:
+                return (config, pv[1])
+            return None, None
+    # Look for a specifically named file
+    if os.path.isfile(args[0]):
+        return (args[0], args[1] if len(args) > 1 else None)
+    # That file didn't exist, return that we didn't find it.
+    return None, None
+
+
+class ConfigException(Exception):
+    ERROR_PARSE = "parse"
+    ERROR_CYCLE = "cycle"
+
+    def __init__(self, kind, message, locations, line=0):
+        """Error thrown when loading and parsing configurations.
+
+        Args:
+            message: Error message to display to user
+            locations: List of filenames of the include history.  The 0 index one
+                       the location where the actual error occurred
+        """
+        if len(locations):
+            s = locations[0]
+            if line:
+                s += ":"
+                s += str(line)
+            s += ": "
+        else:
+            s = ""
+        s += message
+        if len(locations):
+            for loc in locations[1:]:
+                s += "\n        included from %s" % loc
+        super().__init__(s)
+        self.kind = kind
+        self.message = message
+        self.locations = locations
+        self.line = line
+
+
+def LoadConfig(filename):
+    """Load a config, including processing the inherits fields.
+
+    Raises:
+        ConfigException on errors
+    """
+    def LoadAndMerge(fn, visited):
+        with open(fn) as f:
+            try:
+                contents = json.load(f)
+            except json.decoder.JSONDecodeError as ex:
+                if True:
+                    raise ConfigException(ConfigException.ERROR_PARSE, ex.msg, visited, ex.lineno)
+                else:
+                    sys.stderr.write("exception %s" % ex.__dict__)
+                    raise ex
+            # Merge all the parents into one data, with first-wins policy
+            inherited_data = {}
+            for parent in contents.get("inherits", []):
+                if parent in visited:
+                    raise ConfigException(ConfigException.ERROR_CYCLE, "Cycle detected in inherits",
+                            visited)
+                DeepMerge(inherited_data, LoadAndMerge(parent, [parent,] + visited))
+            # Then merge inherited_data into contents, but what's already there will win.
+            DeepMerge(contents, inherited_data)
+            contents.pop("inherits", None)
+        return contents
+    return LoadAndMerge(filename, [filename,])
+
+
+def DeepMerge(merged, addition):
+    """Merge all fields of addition into merged. Pre-existing fields win."""
+    for k, v in addition.items():
+        if k in merged:
+            if isinstance(v, dict) and isinstance(merged[k], dict):
+                DeepMerge(merged[k], v)
+        else:
+            merged[k] = v
+
+
+def Lunch(args):
+    """Handle the lunch command."""
+    # Check that we're at the top of a multitree workspace
+    # TODO: Choose the right sentinel file
+    if not os.path.exists("build/make/orchestrator"):
+        sys.stderr.write("ERROR: lunch.py must be run from the root of a multi-tree workspace\n")
+        return EXIT_STATUS_ERROR
+
+    # Choose the config file
+    config_file, variant = ChooseConfigFromArgs(".", args)
+
+    if config_file == None:
+        sys.stderr.write("Can't find lunch combo file for: %s\n" % " ".join(args))
+        return EXIT_STATUS_NEED_HELP
+    if variant == None:
+        sys.stderr.write("Can't find variant for: %s\n" % " ".join(args))
+        return EXIT_STATUS_NEED_HELP
+
+    # Parse the config file
+    try:
+        config = LoadConfig(config_file)
+    except ConfigException as ex:
+        sys.stderr.write(str(ex))
+        return EXIT_STATUS_ERROR
+
+    # Fail if the lunchable bit isn't set, because this isn't a usable config
+    if not config.get("lunchable", False):
+        sys.stderr.write("%s: Lunch config file (or inherited files) does not have the 'lunchable'"
+                % config_file)
+        sys.stderr.write(" flag set, which means it is probably not a complete lunch spec.\n")
+
+    # All the validation has passed, so print the name of the file and the variant
+    sys.stdout.write("%s\n" % config_file)
+    sys.stdout.write("%s\n" % variant)
+
+    return EXIT_STATUS_OK
+
+
+def FindAllComboFiles(workspace_root):
+    """Find all .mcombo files in the prescribed locations in the tree."""
+    for dir in FindConfigDirs(workspace_root):
+        for file in WalkPaths(dir, lambda x: x.endswith(".mcombo")):
+            yield file
+
+
+def IsFileLunchable(config_file):
+    """Parse config_file, flatten the inheritance, and return whether it can be
+    used as a lunch target."""
+    try:
+        config = LoadConfig(config_file)
+    except ConfigException as ex:
+        sys.stderr.write("%s" % ex)
+        return False
+    return config.get("lunchable", False)
+
+
+def FindAllLunchable(workspace_root):
+    """Find all mcombo files in the tree (rooted at workspace_root) that when
+    parsed (and inheritance is flattened) have lunchable: true."""
+    for f in [x for x in FindAllComboFiles(workspace_root) if IsFileLunchable(x)]:
+        yield f
+
+
+def List():
+    """Handle the --list command."""
+    for f in sorted(FindAllLunchable(".")):
+        print(f)
+
+
+def Print(args):
+    """Handle the --print command."""
+    # Parse args
+    if len(args) == 0:
+        config_file = os.environ.get("TARGET_BUILD_COMBO")
+        if not config_file:
+            sys.stderr.write("TARGET_BUILD_COMBO not set. Run lunch or pass a combo file.\n")
+            return EXIT_STATUS_NEED_HELP
+    elif len(args) == 1:
+        config_file = args[0]
+    else:
+        return EXIT_STATUS_NEED_HELP
+
+    # Parse the config file
+    try:
+        config = LoadConfig(config_file)
+    except ConfigException as ex:
+        sys.stderr.write(str(ex))
+        return EXIT_STATUS_ERROR
+
+    # Print the config in json form
+    json.dump(config, sys.stdout, indent=4)
+
+    return EXIT_STATUS_OK
+
+
+def main(argv):
+    if len(argv) < 2 or argv[1] == "-h" or argv[1] == "--help":
+        return EXIT_STATUS_NEED_HELP
+
+    if len(argv) == 2 and argv[1] == "--list":
+        List()
+        return EXIT_STATUS_OK
+
+    if len(argv) == 2 and argv[1] == "--print":
+        return Print(argv[2:])
+        return EXIT_STATUS_OK
+
+    if (len(argv) == 2 or len(argv) == 3) and argv[1] == "--lunch":
+        return Lunch(argv[2:])
+
+    sys.stderr.write("Unknown lunch command: %s\n" % " ".join(argv[1:]))
+    return EXIT_STATUS_NEED_HELP
+
+if __name__ == "__main__":
+    sys.exit(main(sys.argv))
+
+
+# vim: sts=4:ts=4:sw=4
diff --git a/orchestrator/core/test/configs/another/bad.mcombo b/orchestrator/core/test/configs/another/bad.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/another/bad.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/another/dir/a b/orchestrator/core/test/configs/another/dir/a
new file mode 100644
index 0000000..7898192
--- /dev/null
+++ b/orchestrator/core/test/configs/another/dir/a
@@ -0,0 +1 @@
+a
diff --git a/orchestrator/core/test/configs/b-eng b/orchestrator/core/test/configs/b-eng
new file mode 100644
index 0000000..eceb3f3
--- /dev/null
+++ b/orchestrator/core/test/configs/b-eng
@@ -0,0 +1 @@
+INVALID FILE
diff --git a/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/b.mcombo b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/b.mcombo
new file mode 100644
index 0000000..8cc8370
--- /dev/null
+++ b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/b.mcombo
@@ -0,0 +1,3 @@
+{
+    "lunchable": "true"
+}
diff --git a/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/nested/nested.mcombo b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/nested/nested.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/nested/nested.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/not_a_combo.txt b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/not_a_combo.txt
new file mode 100644
index 0000000..f9805f2
--- /dev/null
+++ b/orchestrator/core/test/configs/build/make/orchestrator/multitree_combos/not_a_combo.txt
@@ -0,0 +1 @@
+not a combo file
diff --git a/orchestrator/core/test/configs/device/aa/bb/multitree_combos/b.mcombo b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/b.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/b.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/device/aa/bb/multitree_combos/d.mcombo b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/d.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/d.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/device/aa/bb/multitree_combos/v.mcombo b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/v.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/device/aa/bb/multitree_combos/v.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/device/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo b/orchestrator/core/test/configs/device/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/orchestrator/core/test/configs/device/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo
diff --git a/orchestrator/core/test/configs/parsing/cycles/1.mcombo b/orchestrator/core/test/configs/parsing/cycles/1.mcombo
new file mode 100644
index 0000000..ab8fe33
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/cycles/1.mcombo
@@ -0,0 +1,5 @@
+{
+    "inherits": [
+        "test/configs/parsing/cycles/2.mcombo"
+    ]
+}
diff --git a/orchestrator/core/test/configs/parsing/cycles/2.mcombo b/orchestrator/core/test/configs/parsing/cycles/2.mcombo
new file mode 100644
index 0000000..2b774d0
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/cycles/2.mcombo
@@ -0,0 +1,6 @@
+{
+    "inherits": [
+        "test/configs/parsing/cycles/3.mcombo"
+    ]
+}
+
diff --git a/orchestrator/core/test/configs/parsing/cycles/3.mcombo b/orchestrator/core/test/configs/parsing/cycles/3.mcombo
new file mode 100644
index 0000000..41b629b
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/cycles/3.mcombo
@@ -0,0 +1,6 @@
+{
+    "inherits": [
+        "test/configs/parsing/cycles/1.mcombo"
+    ]
+}
+
diff --git a/orchestrator/core/test/configs/parsing/merge/1.mcombo b/orchestrator/core/test/configs/parsing/merge/1.mcombo
new file mode 100644
index 0000000..a5a57d7
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/merge/1.mcombo
@@ -0,0 +1,13 @@
+{
+    "inherits": [
+        "test/configs/parsing/merge/2.mcombo",
+        "test/configs/parsing/merge/3.mcombo"
+    ],
+    "in_1": "1",
+    "in_1_2": "1",
+    "merged": {
+        "merged_1": "1",
+        "merged_1_2": "1"
+    },
+    "dict_1": { "a" : "b" }
+}
diff --git a/orchestrator/core/test/configs/parsing/merge/2.mcombo b/orchestrator/core/test/configs/parsing/merge/2.mcombo
new file mode 100644
index 0000000..00963e2
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/merge/2.mcombo
@@ -0,0 +1,12 @@
+{
+    "in_1_2": "2",
+    "in_2": "2",
+    "in_2_3": "2",
+    "merged": {
+        "merged_1_2": "2",
+        "merged_2": "2",
+        "merged_2_3": "2"
+    },
+    "dict_2": { "a" : "b" }
+}
+
diff --git a/orchestrator/core/test/configs/parsing/merge/3.mcombo b/orchestrator/core/test/configs/parsing/merge/3.mcombo
new file mode 100644
index 0000000..5fc9d90
--- /dev/null
+++ b/orchestrator/core/test/configs/parsing/merge/3.mcombo
@@ -0,0 +1,10 @@
+{
+    "in_3": "3",
+    "in_2_3": "3",
+    "merged": {
+        "merged_3": "3",
+        "merged_2_3": "3"
+    },
+    "dict_3": { "a" : "b" }
+}
+
diff --git a/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/b.mcombo b/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/b.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/b.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/v.mcombo b/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/v.mcombo
new file mode 100644
index 0000000..0967ef4
--- /dev/null
+++ b/orchestrator/core/test/configs/vendor/aa/bb/multitree_combos/v.mcombo
@@ -0,0 +1 @@
+{}
diff --git a/orchestrator/core/test/configs/vendor/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo b/orchestrator/core/test/configs/vendor/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/orchestrator/core/test/configs/vendor/this/one/is/deeper/than/will/be/found/by/the/ttl/multitree_combos/too_deep.mcombo
diff --git a/orchestrator/core/test_lunch.py b/orchestrator/core/test_lunch.py
new file mode 100755
index 0000000..3c39493
--- /dev/null
+++ b/orchestrator/core/test_lunch.py
@@ -0,0 +1,128 @@
+#!/usr/bin/env python3
+#
+# Copyright (C) 2008 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import sys
+import unittest
+
+sys.dont_write_bytecode = True
+import lunch
+
+class TestStringMethods(unittest.TestCase):
+
+    def test_find_dirs(self):
+        self.assertEqual([x for x in lunch.FindDirs("test/configs", "multitree_combos")], [
+                    "test/configs/build/make/orchestrator/multitree_combos",
+                    "test/configs/device/aa/bb/multitree_combos",
+                    "test/configs/vendor/aa/bb/multitree_combos"])
+
+    def test_find_file(self):
+        # Finds the one in device first because this is searching from the root,
+        # not using FindNamedConfig.
+        self.assertEqual(lunch.FindFile("test/configs", "v.mcombo"),
+                   "test/configs/device/aa/bb/multitree_combos/v.mcombo")
+
+    def test_find_config_dirs(self):
+        self.assertEqual([x for x in lunch.FindConfigDirs("test/configs")], [
+                    "test/configs/build/make/orchestrator/multitree_combos",
+                    "test/configs/vendor/aa/bb/multitree_combos",
+                    "test/configs/device/aa/bb/multitree_combos"])
+
+    def test_find_named_config(self):
+        # Inside build/orchestrator, overriding device and vendor
+        self.assertEqual(lunch.FindNamedConfig("test/configs", "b"),
+                    "test/configs/build/make/orchestrator/multitree_combos/b.mcombo")
+
+        # Nested dir inside a combo dir
+        self.assertEqual(lunch.FindNamedConfig("test/configs", "nested"),
+                    "test/configs/build/make/orchestrator/multitree_combos/nested/nested.mcombo")
+
+        # Inside vendor, overriding device
+        self.assertEqual(lunch.FindNamedConfig("test/configs", "v"),
+                    "test/configs/vendor/aa/bb/multitree_combos/v.mcombo")
+
+        # Inside device
+        self.assertEqual(lunch.FindNamedConfig("test/configs", "d"),
+                    "test/configs/device/aa/bb/multitree_combos/d.mcombo")
+
+        # Make sure we don't look too deep (for performance)
+        self.assertIsNone(lunch.FindNamedConfig("test/configs", "too_deep"))
+
+
+    def test_choose_config_file(self):
+        # Empty string argument
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs", [""]),
+                    (None, None))
+
+        # A PRODUCT-VARIANT name
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs", ["v-eng"]),
+                    ("test/configs/vendor/aa/bb/multitree_combos/v.mcombo", "eng"))
+
+        # A PRODUCT-VARIANT name that conflicts with a file
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs", ["b-eng"]),
+                    ("test/configs/build/make/orchestrator/multitree_combos/b.mcombo", "eng"))
+
+        # A PRODUCT-VARIANT that doesn't exist
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs", ["z-user"]),
+                    (None, None))
+
+        # An explicit file
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs",
+                        ["test/configs/build/make/orchestrator/multitree_combos/b.mcombo", "eng"]),
+                    ("test/configs/build/make/orchestrator/multitree_combos/b.mcombo", "eng"))
+
+        # An explicit file that doesn't exist
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs",
+                        ["test/configs/doesnt_exist.mcombo", "eng"]),
+                    (None, None))
+
+        # An explicit file without a variant should fail
+        self.assertEqual(lunch.ChooseConfigFromArgs("test/configs",
+                        ["test/configs/build/make/orchestrator/multitree_combos/b.mcombo"]),
+                    ("test/configs/build/make/orchestrator/multitree_combos/b.mcombo", None))
+
+
+    def test_config_cycles(self):
+        # Test that we catch cycles
+        with self.assertRaises(lunch.ConfigException) as context:
+            lunch.LoadConfig("test/configs/parsing/cycles/1.mcombo")
+        self.assertEqual(context.exception.kind, lunch.ConfigException.ERROR_CYCLE)
+
+    def test_config_merge(self):
+        # Test the merge logic
+        self.assertEqual(lunch.LoadConfig("test/configs/parsing/merge/1.mcombo"), {
+                            "in_1": "1",
+                            "in_1_2": "1",
+                            "merged": {"merged_1": "1",
+                                "merged_1_2": "1",
+                                "merged_2": "2",
+                                "merged_2_3": "2",
+                                "merged_3": "3"},
+                            "dict_1": {"a": "b"},
+                            "in_2": "2",
+                            "in_2_3": "2",
+                            "dict_2": {"a": "b"},
+                            "in_3": "3",
+                            "dict_3": {"a": "b"}
+                        })
+
+    def test_list(self):
+        self.assertEqual(sorted(lunch.FindAllLunchable("test/configs")),
+                ["test/configs/build/make/orchestrator/multitree_combos/b.mcombo"])
+
+if __name__ == "__main__":
+    unittest.main()
+
+# vim: sts=4:ts=4:sw=4
diff --git a/orchestrator/multitree_combos/test.mcombo b/orchestrator/multitree_combos/test.mcombo
new file mode 100644
index 0000000..3ad0717
--- /dev/null
+++ b/orchestrator/multitree_combos/test.mcombo
@@ -0,0 +1,16 @@
+{
+    "lunchable": true,
+    "system": {
+        "tree": "inner_tree_system",
+        "product": "system_lunch_product"
+    },
+    "vendor": {
+        "tree": "inner_tree_vendor",
+        "product": "vendor_lunch_product"
+    },
+    "modules": {
+        "com.android.something": {
+            "tree": "inner_tree_module"
+        }
+    }
+}