from typing import Dict
from typing import Tuple
from typing import List
from typing import Any


def _traverse_foreign_key_tree(
    tree: Dict[str, Dict[Tuple[str, ...], dict]], name: str, fields: Tuple[str, ...]
) -> List[Dict[str, Any]]:
    """Traverse foreign key tree.

    Args:
        tree: Foreign key tree (see :func:`_build_foreign_key_tree`).
        name: Local resource name.
        fields: Local resource fields.

    Returns:
        Sequence of foreign keys starting from `name` and `fields`:

        * `fields` (List[str]): Local fields.
        * `reference['resource']` (str): Reference resource name.
        * `reference['fields']` (List[str]): Reference primary key fields.
    """
    keys = []
    if name not in tree or fields not in tree[name]:
        return keys
    ref = tree[name][fields]
    keys.append({"fields": list(fields), "reference": ref})
    if ref["resource"] not in tree:
        return keys
    for next_fields in tree[ref["resource"]]:
        if set(next_fields) <= set(ref["fields"]):
            for key in _traverse_foreign_key_tree(tree, ref["resource"], next_fields):
                mapped_fields = [
                    fields[ref["fields"].index(field)] for field in key["fields"]
                ]
                keys.append({"fields": mapped_fields, "reference": key["reference"]})
    return keys