def stable_topological_sort(problem):
    """Topologically sort items with dependencies

    The concrete algorithm is to first identify all roots, then
    do a DFS. Children are visited in the order they appear in
    the input. This ensures that there is a predictable output
    for every input. If no constraints are given the output order
    is the same as the input order.

    The items to sort must be hashable and unique.

    Parameters
    ----------
    
    problem : list of dict(id=..., before=..., ...)
        Each object is a dictionary which is preserved to the output.
        The `id` key is each objects identity, and the `before` is a list
        of ids of objects that a given object must come before in
        the ordered output.

    Returns
    -------

    solution : list
        The input `problem` in a possibly different order
    """
    # record order to use for sorting `before`
    id_to_obj = {}
    order = {}
    for i, obj in enumerate(problem):
        if obj['id'] in order:
            raise ValueError('%r appears twice in input' % obj['id'])
        order[obj['id']] = i
        id_to_obj[obj['id']] = obj

    # turn into dict-based graph, and find the roots
    graph = {}
    roots = set(order.keys())
    for obj in problem:
        graph[obj['id']] = sorted(obj['before'], key=order.__getitem__)
        roots.difference_update(obj['before'])

    result = []

    def dfs(obj_id):
        if obj_id not in result:
            result.append(obj_id)
            for child in graph[obj_id]:
                dfs(child)

    for obj_id in sorted(roots, key=order.__getitem__):
        dfs(obj_id)

    # cycles will have been left entirely out at this point
    if len(result) != len(problem):
        raise ValueError('provided constraints forms a graph with cycles')

    return [id_to_obj[obj_id] for obj_id in result]