Generator function to compare two collections, and yield differences.
    This function does not currently report moved items in collections, and
    uses the :py:meth:`DiffOptions.record_id` method to decide if objects are
    to be considered the same, and differences within returned.

    Arguments are the same as :py:func:`compare_record_iter`.

    Note that ``diff_iter`` and ``compare_record_iter`` will call *both* this
    function and ``compare_record_iter`` on ``RecordList`` types.  However, as
    most ``RecordList`` types have no extra properties, no differences are
    yielded by the ``compare_record_iter`` method.

def compare_collection_iter(propval_a, propval_b, fs_a=None, fs_b=None,
                            options=None):
    """Generator function to compare two collections, and yield differences.
    This function does not currently report moved items in collections, and
    uses the :py:meth:`DiffOptions.record_id` method to decide if objects are
    to be considered the same, and differences within returned.

    Arguments are the same as :py:func:`compare_record_iter`.

    Note that ``diff_iter`` and ``compare_record_iter`` will call *both* this
    function and ``compare_record_iter`` on ``RecordList`` types.  However, as
    most ``RecordList`` types have no extra properties, no differences are
    yielded by the ``compare_record_iter`` method.
    """
    if fs_a is None:
        fs_a = FieldSelector(tuple())
        fs_b = FieldSelector(tuple())
    if options is None:
        options = DiffOptions()

    propvals = dict(a=propval_a, b=propval_b)
    values = dict()
    rev_keys = dict()
    compare_values = None
    coll_type = (
        type(propval_a) if propval_a is not _nothing else type(propval_b)
    )
    force_descent = (propval_a is _nothing) or (propval_b is _nothing)
    if isinstance(coll_type.itemtype, tuple):
        raise exc.CollectionItemTypeUnsupported()
    elif not issubclass(coll_type.itemtype, Record):
        iter_func = (
            compare_dict_iter if issubclass(coll_type, DictCollection) else
            compare_list_iter if issubclass(coll_type, ListCollection) else
            None
        )
        if not iter_func:
            raise exc.CollectionDiffUnsupported(
                coll_type=coll_type,
                item_type=coll_type.itemtype,
                item_type_name=coll_type.itemtype.__name__,
            )
        for diff in iter_func(propval_a, propval_b, fs_a, fs_b, options):
            yield diff
        return

    id_args = options.id_args(coll_type.itemtype, fs_a)
    if not callable(id_args) and 'selector' in id_args and \
            not id_args['selector']:
        # early exit shortcut
        return

    for x in "a", "b":
        propval_x = propvals[x]
        vals = values[x] = set()
        rev_key = rev_keys[x] = dict()

        seen = collections.Counter()

        for k, v in collection_generator(propval_x):
            if callable(id_args):
                if fs_a + [k] not in options.compare_filter:
                    continue
            pk = options.record_id(
                v, **(id_args(k) if callable(id_args) else id_args))
            if options.ignore_empty_items and _nested_empty(pk):
                continue
            if compare_values is None:
                # the primary key being a tuple is taken to imply that
                # the value type is a Record, and hence descent is
                # possible.
                compare_values = isinstance(pk, tuple)
            vals.add((pk, seen[pk]))
            rev_key[(pk, seen[pk])] = k
            seen[pk] += 1

    if options.recurse:
        # we can be sure that both records have these keys
        set_a = set(rev_keys["a"].values())
        set_b = set(rev_keys["b"].values())
        shared_keys = set_a.intersection(set_b)
        removed = set_a - set_b
        added = set_b - set_a
        for key in shared_keys:
            if (isinstance(propval_a, collections.Iterable) and
               isinstance(propval_b, collections.Iterable)):
                diffs = _diff_iter(propval_a[key], propval_b[key],
                                   fs_a + [key], fs_b + [key], options)

                for diff in diffs:
                    yield diff

        for key in removed:
            yield DiffInfo(diff_type=DiffTypes.REMOVED,
                           base=fs_a + [key],
                           other=fs_b)

        for key in added:
            yield DiffInfo(diff_type=DiffTypes.ADDED,
                           base=fs_a,
                           other=fs_b + [key])
    else:
        removed = values['a'] - values['b']
        added = values['b'] - values['a']
        common = values['a'].intersection(values['b'])

        if compare_values or force_descent:
            descendable = (removed | added) if force_descent else common

            for pk, seq in descendable:
                if not force_descent or propval_a is not _nothing:
                    a_key = rev_keys['a'][pk, seq]
                    a_val = propval_a[a_key]
                if not force_descent or propval_b is not _nothing:
                    b_key = rev_keys['b'][pk, seq]
                    b_val = propval_b[b_key]
                if force_descent:
                    if propval_a is _nothing:
                        a_key = b_key
                        a_val = _nothing
                    else:
                        b_key = a_key
                        b_val = _nothing
                selector_a = fs_a + a_key
                selector_b = fs_b + b_key
                for diff in _diff_iter(
                    a_val, b_val, selector_a, selector_b, options,
                ):
                    yield diff

            if not force_descent and options.fuzzy_match:
                for a_pk_seq, b_pk_seq in _fuzzy_match(removed, added):
                    removed.remove(a_pk_seq)
                    added.remove(b_pk_seq)
                    a_key = rev_keys['a'][a_pk_seq]
                    a_val = propval_a[a_key]
                    b_key = rev_keys['b'][b_pk_seq]
                    b_val = propval_b[b_key]
                    selector_a = fs_a + a_key
                    selector_b = fs_b + b_key
                    any_diffs = False
                    for diff in _diff_iter(
                        a_val, b_val, selector_a, selector_b, options,
                    ):
                        if diff.diff_type != DiffTypes.NO_CHANGE:
                            any_diffs = True
                        yield diff

                    if options.moved and a_key != b_key:
                        yield DiffInfo(
                            diff_type=DiffTypes.MOVED,
                            base=fs_a + [a_key],
                            other=fs_b + [b_key],
                        )
                    elif options.unchanged and not any_diffs:
                        yield DiffInfo(
                            diff_type=DiffTypes.NO_CHANGE,
                            base=fs_a + [a_key],
                            other=fs_b + [b_key],
                        )

        if options.unchanged or options.moved:
            unchanged = values['a'] & values['b']
            for pk, seq in unchanged:
                a_key = rev_keys['a'][pk, seq]
                b_key = rev_keys['b'][pk, seq]
                if options.moved and a_key != b_key:
                    yield DiffInfo(
                        diff_type=DiffTypes.MOVED,
                        base=fs_a + [a_key],
                        other=fs_b + [b_key],
                    )
                elif options.unchanged:
                    yield DiffInfo(
                        diff_type=DiffTypes.NO_CHANGE,
                        base=fs_a + [a_key],
                        other=fs_b + [b_key],
                    )

        if not force_descent:
            for pk, seq in removed:
                a_key = rev_keys['a'][pk, seq]
                selector = fs_a + [a_key]
                yield DiffInfo(
                    diff_type=DiffTypes.REMOVED,
                    base=selector,
                    other=fs_b,
                )

            for pk, seq in added:
                b_key = rev_keys['b'][pk, seq]
                selector = fs_b + [b_key]
                yield DiffInfo(
                    diff_type=DiffTypes.ADDED,
                    base=fs_a,
                    other=selector,
                )