import copy


def merge_facts(orig, new, additive_facts_to_overwrite):
    """ Recursively merge facts dicts

        Args:
            orig (dict): existing facts
            new (dict): facts to update

            additive_facts_to_overwrite (list): additive facts to overwrite in jinja
                                                '.' notation ex: ['master.named_certificates']

        Returns:
            dict: the merged facts
    """
    additive_facts = ['named_certificates']
    facts = dict()
    for key, value in orig.iteritems():
        if key in new:
            if isinstance(value, dict) and isinstance(new[key], dict):
                relevant_additive_facts = []
                # Keep additive_facts_to_overwrite if key matches
                for item in additive_facts_to_overwrite:
                    if '.' in item and item.startswith(key + '.'):
                        relevant_additive_facts.append(item)
                facts[key] = merge_facts(value, new[key], relevant_additive_facts)
            elif key in additive_facts and key not in [x.split('.')[-1] for x in additive_facts_to_overwrite]:
                # Fact is additive so we'll combine orig and new.
                if isinstance(value, list) and isinstance(new[key], list):
                    new_fact = []
                    for item in copy.deepcopy(value) + copy.copy(new[key]):
                        if item not in new_fact:
                            new_fact.append(item)
                    facts[key] = new_fact
            else:
                facts[key] = copy.copy(new[key])
        else:
            facts[key] = copy.deepcopy(value)
    new_keys = set(new.keys()) - set(orig.keys())
    for key in new_keys:
        facts[key] = copy.deepcopy(new[key])
    return facts