import json
import traceback
import unittest
import json
from copy import deepcopy


def merge(x: dict, y: dict) -> dict:
    'Merge subtrees x y, and return the results as a new output.'
    return merge_inplace(deepcopy(x), y)


def merge_inplace(dest: dict, src: dict) -> dict:
    'Merge subtree src into dest, and return dest.'

    # perform sanity checks to make the code more rock solid
    # feel free to remove all those 6 lines if you don't need
    assert dest.get('id'), 'Cannot merge anonymous subtrees!'
    assert dest.get('id') == src.get('id'), 'Identity mismatch!'
    if not src.get('children'):  # nothing to do, exit
        return dest
    elif not dest.get('children'):  # if the children list didn't exist
        dest['children'] = []  # then create an empty list for it

    named_dest_children = {
        child['id']: child
        for child in dest['children']
        if 'id' in child
    }
    # merge starts
    for child in src['children']:
        if 'id' not in child:  # anonymous child, just append it
            dest['children'].append(child)
        elif child['id'] in named_dest_children:  # override a named subtree
            merge_inplace(named_dest_children[child['id']], child)
        else:  # create a new subtree
            dest['children'].append(child)
            named_dest_children[child['id']] = child
    return dest


class Test(unittest.TestCase):

    def setUp(self):
        pass

    def tearDown(self):
        pass

    def test0(self):
        subtree1 = {
            "id": "root",
            "children": [
                {
                    "id": "file",
                    "caption": "File",
                    "children": []
                },
                {
                    "id": "edit",
                    "caption": "Edit",
                    "children": []
                },
                {
                    "id": "tools",
                    "caption": "Tools",
                    "children": [
                        {
                            "id": "packages",
                            "caption": "Packages",
                            "children": []
                        }
                    ]
                },
                {
                    "id": "help",
                    "caption": "Help",
                    "children": []
                },
            ]
        }

        subtree2 = {
            "id": "root",
            "children": [
                {
                    "id": "file",
                    "caption": "File",
                    "children": [
                        {"caption": "New"},
                        {"caption": "Exit"},
                    ]
                }
            ]
        }

        subtree3 = {
            "id": "root",
            "children": [
                {
                    "id": "edit",
                    "children": [
                        {"caption": "Copy"},
                        {"caption": "Cut"},
                        {"caption": "Paste"},
                    ]
                },
                {
                    "id": "help",
                    "children": [
                        {"caption": "About"},
                    ]
                }
            ]
        }

        subtree4 = {
            "id": "root",
            "children": [
                {
                    "id": "edit",
                    "children": [
                        {
                            "id": "text",
                            "caption": "Text",
                            "children": [
                                {"caption": "Insert line before"},
                                {"caption": "Insert line after"}
                            ]
                        }
                    ]
                }
            ]
        }

        expected_output = {
            "id": "root",
            "children": [
                {
                    "id": "file",
                    "caption": "File",
                    "children": [
                        {
                            "caption": "New"
                        },
                        {
                            "caption": "Exit"
                        }
                    ]
                },
                {
                    "id": "edit",
                    "caption": "Edit",
                    "children": [
                        {
                            "caption": "Copy"
                        },
                        {
                            "caption": "Cut"
                        },
                        {
                            "caption": "Paste"
                        },
                        {
                            "id": "text",
                            "caption": "Text",
                            "children": [
                                {
                                    "caption": "Insert line before"
                                },
                                {
                                    "caption": "Insert line after"
                                }
                            ]
                        }
                    ]
                },
                {
                    "id": "tools",
                    "caption": "Tools",
                    "children": [
                        {
                            "id": "packages",
                            "caption": "Packages",
                            "children": []
                        }
                    ]
                },
                {
                    "id": "help",
                    "caption": "Help",
                    "children": [
                        {
                            "caption": "About"
                        }
                    ]
                }
            ]
        }

        output = merge(subtree1, subtree2)
        output = merge(output, subtree3)
        output = merge(output, subtree4)
        self.assertEqual(output, expected_output)

    def test1(self):
        subtree1 = {
            "id": "root",
            "children": [
                {
                    "id": "preferences",
                    "caption": "Preferences",
                    "children":
                    [
                        {
                            "caption": "Package Settings",
                            "mnemonic": "P",
                            "id": "package-settings",
                            "children":
                            [
                                {
                                    "caption": "Package1",
                                    "children":
                                    [
                                    ]
                                }
                            ]
                        }
                    ]
                }
            ]
        }

        subtree2 = {
            "id": "root",
            "children": [
                {
                    "id": "preferences",
                    "children":
                    [
                        {
                            "id": "package-settings",
                            "children":
                            [
                                {
                                    "caption": "Package2",
                                    "children":
                                    [
                                    ]
                                }
                            ]
                        }
                    ]
                }
            ]
        }

        expected_output = {
            "id": "root",
            "children": [
                {
                    "id": "preferences",
                    "caption": "Preferences",
                    "children": [
                        {
                            "caption": "Package Settings",
                            "mnemonic": "P",
                            "id": "package-settings",
                            "children": [
                                {
                                    "caption": "Package1",
                                    "children": []
                                },
                                {
                                    "caption": "Package2",
                                    "children": []
                                }
                            ]
                        }
                    ]
                }
            ]
        }

        output = merge(subtree1, subtree2)
        self.assertEqual(output, expected_output)

    def test2(self):
        subtree1 = {
            "id": "root",
            "children": [
                {
                    "id": "preferences",
                    "caption": "Preferences"
                }
            ]
        }

        subtree2 = {
            "id": "root",
            "children": [
                {
                    "id": "preferences",
                    "command": "do_something",
                    "caption": "NewPreferences"
                }
            ]
        }

        output = merge(subtree1, subtree2)
        print(json.dumps(output, indent=4))
        # self.assertEqual(output, expected_output)


if __name__ == "__main__":
    unittest.main()