File Coverage

blib/lib/Set/Relation/V2.pm

Criterion	Covered	Total	%
statement	605	1823	33.1
branch	149	580	25.6
condition	46	277	16.6
subroutine	70	171	40.9
pod	0	78	0.0
total	870	2929	29.7

use 5.008000;
use utf8;
use strict;
use warnings;

###########################################################################
###########################################################################

{ package Set::Relation::V2; # class
    our $VERSION = '0.013002';
    $VERSION = eval $VERSION;

    use Carp 'confess';
    use Scalar::Util 'blessed', 'refaddr';
    use List::Util 'any', 'all', 'notall', 'uniqstr';

    # with Set::Relation
    sub does {
        my ($self, $role_name) = @_;
        confess q{This does() may only be invoked on an object.}
            if not blessed $self;
        confess q{does(): Bad $role_name arg; it must be a defined string.}
            if !defined $role_name;
        return 0
            if !$self->isa( __PACKAGE__ );
        return 1
            if $role_name eq 'Set::Relation';
        return 0;
    }

    # has _heading
        # isa HashRef
            # One elem per attribute:
                # hkey is Str attr name
                # hval is undef+unused
        # default {}
    sub _heading {
        my $self = shift;
        $self->{_heading} = $_[0] if scalar @_;
        return $self->{_heading};
    }

    # has _body
        # isa HashRef
            # One elem per tuple:
                # hkey is refaddr of hval
                # hval is HashRef that is the coll of separate tuple attrs:
                    # hkey is Str attr name
                    # hval is the actual tuple attr value
        # default {}
    sub _body {
        my $self = shift;
        $self->{_body} = $_[0] if scalar @_;
        return $self->{_body};
    }

    # Note, this flag expressly only applies to the object it is a
    # member of, and it doesn't say anything about this object's RVAs.
    # Note, this flag is always true when an index exists over all attrs,
    # because said index is always made in such a way to ensure this,
    # but this flag may also be true when said index doesn't exist,
    # depending on how the V2 object was created.
    # has _is_known_dup_free
        # isa Bool
        # default 0
    sub _is_known_dup_free {
        my $self = shift;
        $self->{_is_known_dup_free} = $_[0] if scalar @_;
        return $self->{_is_known_dup_free};
    }

    # has _which
        # isa Maybe[Str]
        # default undef
    sub _which {
        my $self = shift;
        $self->{_which} = $_[0] if scalar @_;
        return $self->{_which};
    }

    # has _indexes
        # isa HashRef
            # One elem per index:
                # hkey is index name;
                    # - is Str ident gen f head subset tha index ranges ovr
                # hval is 2-elem ArrayRef that is the index itself + meta
                    # [0] is HashRef of atnms that index ranges over
                        # - structure same as '_heading'
                    # [1] is index itself;
                        # - HashRef; one elem per tup of projection of body
                            # on attrs that index ranges over
                        # hkey is Str ident gen fr distinct projection tupl
                        # hval is set of body tup having projection tuples
                            # in comn; is HashRef; one elem per body tuple
                            # - structure same as '_body', is slice o _body
        # default {}
    sub _indexes {
        my $self = shift;
        $self->{_indexes} = $_[0] if scalar @_;
        return $self->{_indexes};
    }

    # has _keys
        # isa HashRef
            # One elem per key:
                # hkey is key name;
                    # - is Str ident gen f head subset tha index ranges ovr
                # hval is HashRef of atnms that index ranges over
                    # - structure same as '_heading'
        # default {}
    sub _keys {
        my $self = shift;
        $self->{_keys} = $_[0] if scalar @_;
        return $self->{_keys};
    }

###########################################################################

sub new {
    my ($class, @args) = @_;
    $class = (blessed $class) || $class;

    my $params = $class->BUILDARGS( @args );

    my $self = bless {}, $class;

    # Set attribute default values.
    $self->_heading( {} );
    $self->_body( {} );
    $self->_is_known_dup_free( 0 );
    $self->_which( undef );
    $self->_indexes( {} );
    $self->_keys( {} );

    $self->BUILD( $params );

    return $self;
}

###########################################################################

sub BUILDARGS {
    my ($class, @args) = @_;
    if (@args == 1) {
        if (ref $args[0] ne 'HASH') {
            # Constructor was called with a single positional argument.
            return { members => $args[0] };
        }
        else {
            # Constructor was called with (possibly zero) named arguments.
            return { %{$args[0]} };
        }
    }
    elsif ((scalar @args % 2) == 0) {
        # Constructor was called with (possibly zero) named arguments.
        return { @args };
    }
    else {
        # Constructor was called with odd number positional arguments >= 3.
        confess q{new(): Bad arguments list; it must either have an even}
            . q{ number of elements or exactly 1 element.};
    }
}

###########################################################################

sub BUILD {
    my ($self, $args) = @_;
    my ($members, $keys) = @{$args}{'members', 'keys'};

    # Note, $members may be in all of the same formats as a HDMD_Perl_STD
    # Relation value literal payload, but with a few extra trivial options.

    if (!defined $members) {
        # Extra option 1.
        $members = [];
    }
    elsif (!ref $members) {
        # Extra option 2.
        $members = [$members];
    }
    elsif (blessed $members and $members->can( 'does' )
            and $members->does( 'Set::Relation' )
            and !$members->isa( __PACKAGE__ )) {
        # We got a $members that is a Set::Relation-doing class where that
        # class isn't us; so clone it from a dump using public interface.
        $members = $self->_new( $members->export_for_new() );
    }
    confess q{new(): Bad :$members arg; it must be either undefined}
            . q{ or an array-ref or a non-ref or a Set::Relation object.}
        if ref $members ne 'ARRAY'
            and not (blessed $members and $members->isa( __PACKAGE__ ));

    # If we get here, $members is either a Set::Relation::V2 or an ary-ref.

    if (!defined $keys) {
        $keys = [];
    }
    elsif (ref $keys ne 'ARRAY') {
        $keys = [$keys];
    }
    if (any { ref $_ ne 'ARRAY' } @{$keys}) {
        $keys = [$keys];
    }
    for my $key (@{$keys}) {
        confess q{new(): Bad $keys arg; it is not correctly formatted.}
            if ref $key ne 'ARRAY'
                or notall { defined $_ and !ref $_ } @{$key};
    }

    # If we get here, $keys is an Array of Array of Str.

    # Note, we expressly do not set _is_known_dup_free to true when
    # we are not cloning an S::R object and we know we have an empty body
    # because often our other methods will be directly adding tuples to
    # result objects after simply asking new() to make an empty starter
    # object, and so we are trying to avoid bugs due to those other methods
    # forgetting to expressly set _is_known_dup_free to false.
    # But if we know we have exactly 1 input tuple, we set the flag to
    # true, since its unlikely the meths add tuples both on new and after.

    if (blessed $members and $members->isa( __PACKAGE__ )) {
        # We'll just shallow-clone anoth Set::Relation::V2 obj's memb-set.
        $self->_heading( $members->_heading() );
        $self->_body( $members->_body() );
        $self->_is_known_dup_free( $members->_is_known_dup_free() );
        $self->_which( $members->_which() );
        $self->_indexes( $members->_indexes() );
        $self->_keys( $members->_keys() );
    }
    elsif (@{$members} == 0) {
        # Input specifies zero attrs + zero tuples.
        # No-op; attr defaults are fine.
    }
    else {
        # Input specifies at least one attr or at least one tuple.
        my $member0 = $members->[0];
        if (!defined $member0) {
            confess q{new(): Bad :$members arg; it is an array ref}
                . q{ but it directly has an undefined element.};
        }
        elsif (!ref $member0) {
            # Input spec at least 1 attr + zero tuples.
            # Each $members elem is expected to be an atnm.
            confess q{new(): Bad :$members arg; it has a non-ref elem,}
                    . q{ indicating it should just be a list of attr}
                    . q{ names, but at least one other elem is}
                    . q{ undefined or is a ref.}
                if notall { defined $_ and !ref $_ } @{$members};
            confess q{new(): Bad :$members arg; it specifies a list of}
                    . q{ attr names with at least one duplicated name.}
                if (uniqstr @{$members}) != @{$members};
            $self->_heading( {CORE::map { ($_ => undef) } @{$members}} );
        }
        elsif (ref $member0 eq 'HASH') {
            # Input spec at least 1 tuple, in named attr format.
            my $heading
                = {CORE::map { ($_ => undef) } CORE::keys %{$member0}};
            my $body = {};
            for my $tuple (@{$members}) {
                confess q{new(): Bad :$members arg; it has a hash-ref}
                        . q{ elem, indicating it should just be a list of}
                        . q{ tuples in named-attr format, but at least one}
                        . q{ other elem is not a hash-ref, or the 2 elems}
                        . q{ don't have exactly the same set of hkeys.}
                    if ref $tuple ne 'HASH'
                        or !$self->_is_identical_hkeys( $heading, $tuple );
                confess q{new(): Bad :$members arg;}
                        . q{ at least one of its hash-ref elems is such}
                        . q{ that there exists circular refs between}
                        . q{ itself or its tuple-valued components.}
                    if $self->_tuple_arg_has_circular_refs( $tuple );
                $tuple = $self->_import_nfmt_tuple( $tuple );
                $body->{refaddr $tuple} = $tuple;
            }
            $self->_heading( $heading );
            $self->_body( $body );
            if (@{$members} == 1) {
                $self->_is_known_dup_free( 1 );
            }
        }
        elsif (ref $member0 eq 'ARRAY') {
            # Input is in ordered attr format.
            my $member1 = $members->[1];
            confess q{new(): Bad :$members arg; it has an array-ref first}
                    . q{ elem, indicating it should just be a list of}
                    . q{ tuples in ordered-attr format, but either}
                    . q{ :$members doesn't have exactly 2 elements or its}
                    . q{ second element isn't also an array-ref.}
                if @{$members} != 2 or ref $member1 ne 'ARRAY';
            # Each $member0 elem is expected to be an atnm.
            confess q{new(): Bad :$members array-ref arg array-ref}
                    . q{ first elem; it should be just be a list of}
                    . q{ attr names, but at least one name}
                    . q{ is undefined or is a ref.}
                if notall { defined $_ and !ref $_ } @{$member0};
            confess q{new(): Bad :$members arg; it specifies a list of}
                    . q{ attr names with at least one duplicated name.}
                if (uniqstr @{$member0}) != @{$member0};
            my $heading = {CORE::map { ($_ => undef) } @{$member0}};
            my $body = {};
            for my $tuple (@{$member1}) {
                confess q{new(): Bad :$members array-ref arg array-ref}
                        . q{ second elem; at least one elem isn't an}
                        . q{ array-ref, or that doesn't have the same}
                        . q{ count of elems as the :$members first elem.}
                    if ref $tuple ne 'ARRAY' or @{$tuple} != @{$member0};
                # Each $tuple elem is expected to be an atvl.
                confess q{new(): Bad :$members arg;}
                        . q{ at least one of its array-ref elems}
                        . q{ is such that there exists circular refs}
                        . q{ between its tuple-valued components.}
                    if any { ref $_ eq 'HASH'
                            and $self->_tuple_arg_has_circular_refs( $_ )
                        } (@{$tuple});
                $tuple = $self->_import_ofmt_tuple( $member0, $tuple );
                $body->{refaddr $tuple} = $tuple;
            }
            $self->_heading( $heading );
            $self->_body( $body );
            if (@{$member1} == 1) {
                $self->_is_known_dup_free( 1 );
            }
        }
        else {
            confess q{new(): Bad :$members arg; it is an array-ref but it}
                . q{ has an elem that is neither a defined scalar nor}
                . q{ an array-ref nor a hash-ref.};
        }
    }

    my $self_h = $self->_heading();

    for my $key (@{$keys}) {
        confess q{new(): At least one of the relation keys defined by the}
                . q{ $keys arg isn't a subset of the heading of the}
                . q{ relation defined by the $members arg.}
            if notall { exists $self_h->{$_} } @{$key};
        confess q{new(): The relation defined by the $members arg violates}
                . q{ at least one of the candidate unique key constraints}
                . qq{ defined by the $members arg: [@{$key}].}
            if !$self->_has_key( $key );
    }

    return;
}

###########################################################################

sub _new {
    my ($self, @args) = @_;
    return (blessed $self)->new( @args );
}

###########################################################################

sub export_for_new {
    my ($self, $want_ord_attrs, $allow_dup_tuples) = @_;
    return {
        'members' => $self->_members( 'export_for_new',
            '$want_ord_attrs', $want_ord_attrs, $allow_dup_tuples ),
        'keys' => $self->keys(),
    };
}

###########################################################################

sub which {
    my ($self) = @_;
    my $ident_str = $self->_which();
    if (!defined $ident_str) {
        my $index = $self->_dup_free_want_index_over_all_attrs();
        my $hs = $self->_heading_ident_str( $self->_heading() );
        my $bs = CORE::join qq{,\n}, sort (CORE::keys %{$index});
        my $vstr = "H=$hs;\nB={$bs}";
        $ident_str = 'Relation:' . (length $vstr) . ':{' . $vstr . '}';
        $self->_which( $ident_str );
    }
    return $ident_str;
}

###########################################################################

sub members {
    my ($self, $want_ord_attrs, $allow_dup_tuples) = @_;
    return $self->_members( 'members',
        '$want_ord_attrs', $want_ord_attrs, $allow_dup_tuples );
}

sub _members {
    my ($self, $rtn_nm, $arg_nm, $want_ord_attrs, $allow_dup_tuples) = @_;
    if (!$allow_dup_tuples and !$self->_is_known_dup_free()) {
        $self->_dup_free_want_index_over_all_attrs();
    }
    if ($want_ord_attrs) {
        my $ord_attr_names = $self->_normalize_true_want_ord_attrs_arg(
            $rtn_nm, $arg_nm, $want_ord_attrs );
        return [$ord_attr_names, [CORE::map {
                $self->_export_ofmt_tuple( $ord_attr_names, $_ )
            } values %{$self->_body()}]];
    }
    elsif ((CORE::keys %{$self->_body()}) == 0) {
        # We have zero tuples, just export attr names.
        return [sort (CORE::keys %{$self->_heading()})];
    }
    else {
        # We have at least one tuple, export in named-attr format.
        return [CORE::map { $self->_export_nfmt_tuple( $_ ) }
            values %{$self->_body()}];
    }
}

###########################################################################

sub heading {
    my ($self) = @_;
    return [sort (CORE::keys %{$self->_heading()})];
}

###########################################################################

sub body {
    my ($self, $want_ord_attrs, $allow_dup_tuples) = @_;
    if (!$allow_dup_tuples and !$self->_is_known_dup_free()) {
        $self->_dup_free_want_index_over_all_attrs();
    }
    if ($want_ord_attrs) {
        my $ord_attr_names = $self->_normalize_true_want_ord_attrs_arg(
            'body', '$want_ord_attrs', $want_ord_attrs );
        return [CORE::map { $self->_export_ofmt_tuple(
            $ord_attr_names, $_ ) } values %{$self->_body()}];
    }
    else {
        return [CORE::map { $self->_export_nfmt_tuple( $_ ) }
            values %{$self->_body()}];
    }
}

###########################################################################

sub _normalize_true_want_ord_attrs_arg {
    my ($self, $rtn_nm, $arg_nm, $want_ord_attrs) = @_;

    my $heading = $self->_heading();

    my $attr_names = [CORE::keys %{$heading}];
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be either undefined|false or the scalar value '1'}
            . q{ or an array-ref of attr names whose degree and}
            . q{ elements match the heading of the invocant.}
        if not (!ref $want_ord_attrs and $want_ord_attrs eq '1'
            or ref $want_ord_attrs eq 'ARRAY'
                and @{$want_ord_attrs} == @{$attr_names}
                and all { exists $heading->{$_} } @{$want_ord_attrs});

    return
        $want_ord_attrs eq '1' ? [sort @{$attr_names}] : $want_ord_attrs;
}

###########################################################################

sub slice {
    my ($self, $attr_names, $want_ord_attrs, $allow_dup_tuples) = @_;

    (my $proj_h, $attr_names)
        = $self->_atnms_hr_from_assert_valid_atnms_arg(
        'slice', '$attr_names', $attr_names );
    my (undef, undef, $proj_only)
        = $self->_ptn_conj_and_disj( $self->_heading(), $proj_h );
    confess q{slice(): Bad $attr_names arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if @{$proj_only} > 0;

    if (!$allow_dup_tuples and !$self->_is_known_dup_free()) {
        $self->_dup_free_want_index_over_all_attrs();
    }

    if ($want_ord_attrs) {
        confess q{slice(): Bad $want_ord_attrs arg; it must be}
                . q{ either undefined|false or the scalar value '1'.}
            if $want_ord_attrs ne '1';
        return [CORE::map { $self->_export_ofmt_tuple(
            $attr_names, $_ ) } values %{$self->_body()}];
    }
    else {
        return [CORE::map {
            my $t = $_;
            $t = {CORE::map { ($_ => $t->{$_}) } @{$attr_names}};
            $self->_export_nfmt_tuple( $t );
        } values %{$self->_body()}];
    }
}

###########################################################################

sub attr {
    my ($self, $name, $allow_dup_tuples) = @_;

    $self->_assert_valid_atnm_arg( 'attr', '$name', $name );
    confess q{attr(): Bad $name arg; that attr name}
            . q{ doesn't match an attr of the invocant's heading.}
        if !exists $self->_heading()->{$name};

    if (!$allow_dup_tuples and !$self->_is_known_dup_free()) {
        $self->_dup_free_want_index_over_all_attrs();
    }

    return [CORE::map {
            my $atvl = $_->{$name};
            if (ref $atvl eq 'HASH') {
                $atvl = $self->_export_nfmt_tuple( $atvl );
            }
            $atvl;
        } values %{$self->_body()}];
}

###########################################################################

sub keys {
    my ($self) = @_;
    return [CORE::map { [sort @{$_}] } values %{$self->_keys()}];
}

###########################################################################

sub _normalize_same_heading_tuples_arg {
    my ($r, $rtn_nm, $arg_nm, $t) = @_;

    my $r_h = $r->_heading();

    if (ref $t eq 'HASH') {
        $t = [$t];
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg; it must be}
            . q{ an array-ref or a hash-ref.}
        if ref $t ne 'ARRAY';
    for my $tuple (@{$t}) {
        confess qq{$rtn_nm(): Bad $arg_nm arg elem;}
                . q{ it isn't a hash-ref, or it doesn't have exactly the}
                . q{ same set of attr names as the invocant.}
            if ref $tuple ne 'HASH'
                or !$r->_is_identical_hkeys( $r_h, $tuple );
        confess qq{$rtn_nm(): Bad $arg_nm arg elem;}
                . q{ it is a hash-ref, and there exist circular refs}
                . q{ between itself or its tuple-valued components.}
            if $r->_tuple_arg_has_circular_refs( $tuple );
    }

    return $t;
}

###########################################################################

sub _tuple_arg_has_circular_refs {
    # This routine just checks that no Hash which would be treated as
    # being of a value type contains itself as a component, where the
    # component and any intermediate components are treated as value types.
    # It *is* fine for a Hash to contain the same other Hash more than once
    # such that the other is a sibling/cousin/etc to itself.
    my ($self, $tuple, $ancs_of_tup_atvls) = @_;
    $ancs_of_tup_atvls = $ancs_of_tup_atvls ? {%{$ancs_of_tup_atvls}} : {};
    $ancs_of_tup_atvls->{refaddr $tuple} = undef;
    for my $atvl (values %{$tuple}) {
        if (ref $atvl eq 'HASH') {
            return 1
                if exists $ancs_of_tup_atvls->{refaddr $atvl};
            return 1
                if $self->_tuple_arg_has_circular_refs(
                    $atvl, $ancs_of_tup_atvls );
        }
    }
    return 0;
}

###########################################################################

sub _is_identical_hkeys {
    my ($self, $h1, $h2) = @_;
    my $h1_hkeys = [CORE::keys %{$h1}];
    my $h2_hkeys = [CORE::keys %{$h2}];
    return (@{$h1_hkeys} == @{$h2_hkeys}
        and all { exists $h1->{$_} } @{$h2_hkeys});
}

###########################################################################

sub _heading_ident_str {
    my ($self, $heading) = @_;
    my $vstr = CORE::join q{,}, CORE::map {
            'Atnm:' . (length $_) . ':<' . $_ . '>'
        } sort (CORE::keys %{$heading});
    return 'Heading:' . (length $vstr) . ':{' . $vstr . '}';
}

sub _ident_str {
    # Note, we assume that any hash-ref arg we get is specifically in
    # internal tuple format, meaning each hval is a 2-elem array etc,
    # and that this is recursive for hash-ref hvals of said.
    my ($self, $value) = @_;
    my $ident_str;
    if (!defined $value) {
        # The Perl undef is equal to itself, distinct from all def values.
        $ident_str = 'Undef';
    }
    elsif (!ref $value) {
        # Treat all defined non-ref values as their string representation.
        $ident_str = 'Scalar:' . (length $value) . ':<' . $value . '>';
    }
    elsif (!blessed $value) {
        # By default, every non-object reference is distinct, and its
        # identity is its memory address; the exception is if the reference
        # is a hash-ref, in which case it is treated as an internal tuple.
        if (ref $value eq 'HASH') {
            my $vstr = CORE::join q{,}, CORE::map {
                my $atnm = 'Atnm:' . (length $_) . ':<' . $_ . '>';
                my $atvl = $self->_ident_str( $value->{$_} );
                "N=$atnm;V=$atvl";
            } sort (CORE::keys %{$value});
            $ident_str = 'Tuple:' . (length $vstr) . ':{' . $vstr . '}';
        }
        else {
            my $vstr = "$value";
            $ident_str = 'Ref:' . (length $vstr) . ':<' . $vstr . '>';
        }
    }
    else {
        # By default, every object instance is distinct, and its identity
        # is its memory address; the exception is if the object is a
        # Set::Relation::V2 or if it overloads stringification.
        if ($value->isa( __PACKAGE__ )) {
            $ident_str = $value->which(); # 'Relation:...'
        }
        else {
            my $vstr = "$value";
            $ident_str = 'Object[' . (blessed $value) . ']:'
                . (length $vstr) . ':<' . $vstr . '>';
        }
    }
    return $ident_str;
}

###########################################################################

sub _import_nfmt_tuple {
    my ($self, $tuple) = @_;
    return {CORE::map {
        my $atnm = $_;
        my $atvl = $tuple->{$_};
        if (ref $atvl eq 'HASH') {
            $atvl = $self->_import_nfmt_tuple( $atvl );
        }
        elsif (blessed $atvl and $atvl->can( 'does' )
                and $atvl->does( 'Set::Relation' )
                and !$atvl->isa( __PACKAGE__ )) {
            $atvl = $self->_new( $atvl );
        }
        ($atnm => $atvl);
    } CORE::keys %{$tuple}};
}

sub _export_nfmt_tuple {
    my ($self, $tuple) = @_;
    return {CORE::map {
        my $atnm = $_;
        my $atvl = $tuple->{$_};
        if (ref $atvl eq 'HASH') {
            $atvl = $self->_export_nfmt_tuple( $atvl );
        }
        ($atnm => $atvl);
    } CORE::keys %{$tuple}};
}

sub _import_ofmt_tuple {
    my ($self, $atnms, $atvls) = @_;
    return {CORE::map {
        my $atnm = $atnms->[$_];
        my $atvl = $atvls->[$_];
        if (ref $atvl eq 'HASH') {
            $atvl = $self->_import_nfmt_tuple( $atvl );
        }
        elsif (blessed $atvl and $atvl->can( 'does' )
                and $atvl->does( 'Set::Relation' )
                and !$atvl->isa( __PACKAGE__ )) {
            $atvl = $self->_new( $atvl );
        }
        ($atnm => $atvl);
    } 0..$#{$atnms}};
}

sub _export_ofmt_tuple {
    my ($self, $atnms, $tuple) = @_;
    return [CORE::map {
        my $atvl = $tuple->{$_};
        if (ref $atvl eq 'HASH') {
            $atvl = $self->_export_nfmt_tuple( $atvl );
        }
        $atvl;
    } @{$atnms}];
}

###########################################################################

sub degree {
    my ($topic) = @_;
    return scalar CORE::keys %{$topic->_heading()};
}

sub is_nullary {
    my ($topic) = @_;
    return $topic->degree() == 0;
}

sub has_attrs {
    my ($topic, $attr_names) = @_;
    (my $proj_h, $attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'has_attrs', '$attr_names', $attr_names );
    my (undef, undef, $proj_only)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $proj_h );
    return @{$proj_only} == 0;
}

sub attr_names {
    my ($topic) = @_;
    return [sort (CORE::keys %{$topic->_heading()})];
}

###########################################################################

sub cardinality {
    my ($topic, $allow_dup_tuples) = @_;
    my $on_entry_body_cardinality = scalar CORE::keys %{$topic->_body()};
    if ($topic->_is_known_dup_free()) {
        return $on_entry_body_cardinality;
    }
    elsif ($on_entry_body_cardinality == 0) {
        $topic->_is_known_dup_free( 1 );
        return 0;
    }
    elsif ($allow_dup_tuples) {
        return $on_entry_body_cardinality;
    }
    else {
        $topic->_dup_free_want_index_over_all_attrs();
        return scalar CORE::keys %{$topic->_body()};
    }
}

sub count {
    my ($self, @args) = @_;
    return $self->cardinality( @args );
}

sub is_empty {
    my ($topic) = @_;
    return $topic->cardinality( 1 ) == 0;
}

sub has_member {
    my ($r, $t) = @_;
    $t = $r->_normalize_same_heading_tuples_arg( 'has_member', '$t', $t );
    my $r_i = $r->_dup_free_want_index_over_all_attrs();
    return all {
            exists $r_i->{$r->_ident_str( $r->_import_nfmt_tuple( $_ ) )}
        } @{$t};
}

###########################################################################

sub has_key {
    my ($topic, $attr_names) = @_;
    (undef, $attr_names) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'has_key', '$attr_names', $attr_names );
    my $topic_h = $topic->_heading();
    confess q{has_key(): Bad $attr_names arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if notall { exists $topic_h->{$_} } @{$attr_names};
    return $topic->_has_key( $attr_names );
}

sub _has_key {
    my ($topic, $attr_names) = @_;

    my $subheading = {CORE::map { ($_ => undef) } @{$attr_names}};
    my $subheading_ident_str = $topic->_heading_ident_str( $subheading );
    my $keys = $topic->_keys();

    return 1
        if exists $keys->{$subheading_ident_str};

    my $index = $topic->_want_index( $attr_names );

    return 0
        if notall { (CORE::keys %{$_}) == 1 } values %{$index};

    $keys->{$subheading_ident_str} = $subheading;
    return 1;
}

###########################################################################

sub empty {
    my ($topic) = @_;
    if ($topic->is_empty()) {
        return $topic;
    }
    my $result = $topic->_new();
    $result->_heading( $topic->_heading() );
    return $result;
}

sub insertion {
    my ($r, $t) = @_;

    $t = $r->_normalize_same_heading_tuples_arg( 'insertion', '$t', $t );

    if (@{$t} == 0) {
        return $r;
    }

    my $tuples = {CORE::map {
            my $tuple = $r->_import_nfmt_tuple( $_ );
            (refaddr $tuple, $tuple);
        } @{$t}};

    my $result = $r->empty();

    $result->_body( {%{$r->_body()}, %{$tuples}} );

    return $result;
}

sub deletion {
    my ($r, $t) = @_;

    $t = $r->_normalize_same_heading_tuples_arg( 'deletion', '$t', $t );

    if (@{$t} == 0) {
        return $r;
    }

    my $tuples = {CORE::map {
            my $tuple = $r->_import_nfmt_tuple( $_ );
            ($r->_ident_str( $tuple ), $tuple);
        } @{$t}};

    my $result = $r->empty();

    my $r_i = $r->_dup_free_want_index_over_all_attrs();
    my $result_b = $result->_body();

    for my $tuple_ident_str (CORE::keys %{$r_i}) {
        if (!exists $tuples->{$tuple_ident_str}) {
            my ($tuple_refaddr, $tuple) = %{$r_i->{$tuple_ident_str}};
            $result_b->{$tuple_refaddr} = $tuple;
        }
    }

    $result->_is_known_dup_free( 1 );

    return $result;
}

###########################################################################

sub rename {
    my ($topic, $map) = @_;

    confess q{rename(): Bad $map arg; it must be a hash-ref.}
        if ref $map ne 'HASH';
    confess q{rename(): Bad $map arg;}
            . q{ its hash elem values should be just be a list of attr}
            . q{ names, but at least one name is undefined or isa ref.}
        if notall { defined $_ and !ref $_ } values %{$map};
    confess q{rename(): Bad $map arg;}
            . q{ its hash elem values specify a list of}
            . q{ attr names with at least one duplicated name.}
        if (uniqstr values %{$map}) != (CORE::keys %{$map});

    my ($topic_attrs_to_ren, $topic_attrs_no_ren, $map_hvals_not_in_topic)
        = $topic->_ptn_conj_and_disj(
            $topic->_heading(), {reverse %{$map}} );
    confess q{rename(): Bad $map arg; that list of attrs to be renamed,}
            . q{ the hash values, isn't a subset of th invocant's heading.}
        if @{$map_hvals_not_in_topic} > 0;

    my ($map_hkeys_same_as_topic_no_ren, undef, undef)
        = $topic->_ptn_conj_and_disj(
            {CORE::map { ($_ => undef) } @{$topic_attrs_no_ren}}, $map );
    confess q{rename(): Bad $map arg; at least one key of that hash,}
            . q{ a new name for an attr of the invocant to rename,}
            . q{ duplicates an attr of the invocant not being renamed.}
        if @{$map_hkeys_same_as_topic_no_ren} > 0;

    return $topic->_rename( $map );
}

sub _rename {
    my ($topic, $map) = @_;

    # Remove any explicit no-ops of an attr being renamed to the same name.
    $map = {CORE::map { ($_ => $map->{$_}) }
        grep { $map->{$_} ne $_ } CORE::keys %{$map}};

    if ((scalar CORE::keys %{$map}) == 0) {
        # Rename of zero attrs of input yields the input.
        return $topic;
    }

    # Expand map to specify all topic attrs being renamed to something.
    my $inv_map = {reverse %{$map}};
    $map = {CORE::map { ((
            exists $inv_map->{$_} ? $inv_map->{$_} : $_
        ) => $_) } CORE::keys %{$topic->_heading()}};

    my $result = $topic->_new();

    $result->_heading( {CORE::map { ($_ => undef) } CORE::keys %{$map}} );

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $result_t = {CORE::map {
                ($_ => $topic_t->{$map->{$_}})
            } CORE::keys %{$map}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub projection {
    my ($topic, $attr_names) = @_;

    (my $proj_h, $attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'projection', '$attr_names', $attr_names );
    my (undef, undef, $proj_only)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $proj_h );
    confess q{projection(): Bad $attr_names arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if @{$proj_only} > 0;

    return $topic->_projection( $attr_names );
}

sub _projection {
    my ($topic, $attr_names) = @_;

    if (@{$attr_names} == 0) {
        # Projection of zero attrs yields identity relation zero or one.
        if ($topic->is_empty()) {
            return $topic->_new();
        }
        else {
            return $topic->_new( [ {} ] );
        }
    }
    if (@{$attr_names} == $topic->degree()) {
        # Projection of all attrs of input yields the input.
        return $topic;
    }

    my $result = $topic->_new();

    $result->_heading( {CORE::map { ($_ => undef) } @{$attr_names}} );

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $result_t
            = {CORE::map { ($_ => $topic_t->{$_}) } @{$attr_names}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

sub cmpl_proj {
    my ($topic, $attr_names) = @_;

    my $topic_h = $topic->_heading();

    (my $cproj_h, $attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'cmpl_proj', '$attr_names', $attr_names );
    my (undef, undef, $cproj_only)
        = $topic->_ptn_conj_and_disj( $topic_h, $cproj_h );
    confess q{cmpl_proj(): Bad $attr_names arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if @{$cproj_only} > 0;

    return $topic->_projection(
        [grep { !$cproj_h->{$_} } CORE::keys %{$topic_h}] );
}

###########################################################################

sub wrap {
    my ($topic, $outer, $inner) = @_;

    $topic->_assert_valid_atnm_arg( 'wrap', '$outer', $outer );
    (my $inner_h, $inner) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'wrap', '$inner', $inner );

    my (undef, $topic_attrs_no_wr, $inner_attrs_not_in_topic)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $inner_h );
    confess q{wrap(): Bad $inner arg; that list of attrs to be wrapped}
            . q{ isn't a subset of the invocant's heading.}
        if @{$inner_attrs_not_in_topic} > 0;
    confess q{wrap(): Bad $outer arg; that name for a new attr to add}
            . q{ to the invocant, consisting of wrapped invocant attrs,}
            . q{ duplicates an attr of the invocant not being wrapped.}
        if any { $_ eq $outer } @{$topic_attrs_no_wr};

    return $topic->_wrap( $outer, $inner, $topic_attrs_no_wr );
}

sub _wrap {
    my ($topic, $outer, $inner, $topic_attrs_no_wr) = @_;

    my $result = $topic->_new();

    $result->_heading(
        {CORE::map { ($_ => undef) } @{$topic_attrs_no_wr}, $outer} );

    my $topic_b = $topic->_body();
    my $result_b = $result->_body();

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        # So $result_b is already correct.
    }
    elsif (@{$inner} == 0) {
        # Wrap zero $topic attrs as new attr.
        # So this is a simple static extension of $topic w static $outer.
        my $inner_t = {};
        for my $topic_t (values %{$topic_b}) {
            my $result_t = {$outer => $inner_t, {%{$topic_t}}};
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    elsif (@{$topic_attrs_no_wr} == 0) {
        # Wrap all $topic attrs as new attr.
        for my $topic_t_refaddr (CORE::keys %{$topic_b}) {
            my $result_t = {$outer => $topic_b->{$topic_t_refaddr}};
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    else {
        # Wrap at least one but not all $topic attrs as new attr.
        for my $topic_t (values %{$topic_b}) {
            my $inner_t = {CORE::map { ($_ => $topic_t->{$_}) } @{$inner}};
            my $result_t = {
                $outer => $inner_t,
                CORE::map { ($_ => $topic_t->{$_}) } @{$topic_attrs_no_wr}
            };
            $result_b->{refaddr $result_t} = $result_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

sub cmpl_wrap {
    my ($topic, $outer, $cmpl_inner) = @_;

    $topic->_assert_valid_atnm_arg( 'cmpl_wrap', '$outer', $outer );
    (my $cmpl_inner_h, $cmpl_inner)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'cmpl_wrap', '$cmpl_inner', $cmpl_inner );

    my $topic_h = $topic->_heading();

    confess q{cmpl_wrap(): Bad $cmpl_inner arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if notall { exists $topic_h->{$_} } @{$cmpl_inner};

    my $inner = [grep { !$cmpl_inner_h->{$_} } CORE::keys %{$topic_h}];
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    my (undef, $topic_attrs_no_wr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h, $inner_h );
    confess q{cmpl_wrap(): Bad $outer arg; that name for a new attr to add}
            . q{ to the invocant, consisting of wrapped invocant attrs,}
            . q{ duplicates an attr of the invocant not being wrapped.}
        if any { $_ eq $outer } @{$topic_attrs_no_wr};

    return $topic->_wrap( $outer, $inner, $topic_attrs_no_wr );
}

###########################################################################

sub unwrap {
    my ($topic, $inner, $outer) = @_;

    (my $inner_h, $inner) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'unwrap', '$inner', $inner );
    $topic->_assert_valid_atnm_arg( 'unwrap', '$outer', $outer );

    my $topic_h = $topic->_heading();

    confess q{unwrap(): Bad $outer arg; that attr name}
            . q{ doesn't match an attr of the invocant's heading.}
        if !exists $topic_h->{$outer};

    my $topic_h_except_outer = {%{$topic_h}};
    delete $topic_h_except_outer->{$outer};

    my ($inner_attrs_dupl_topic, $topic_attrs_no_uwr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h_except_outer, $inner_h );
    confess q{unwrap(): Bad $inner arg; at least one name in that attr}
            . q{ list, which the invocant would be extended with when}
            . q{ unwrapping $topic{$outer}, duplicates an attr of the}
            . q{ invocant not being unwrapped.}
        if @{$inner_attrs_dupl_topic} > 0;

    my $topic_b = $topic->_body();

    for my $topic_t (values %{$topic_b}) {
        my $inner_t = $topic_t->{$outer};
        confess q{unwrap(): Can't unwrap $topic{$outer} because there is}
                . q{ not a same-heading tuple value for the $outer attr of}
                . q{ every tuple of $topic whose heading matches $inner.}
            if ref $inner_t ne 'HASH'
                or !$topic->_is_identical_hkeys( $inner_h, $inner_t );
    }

    my $result = $topic->_new();

    $result->_heading( {%{$topic_h_except_outer}, %{$inner_h}} );

    my $result_b = $result->_body();

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        # So $result_b is already correct.
    }
    elsif (@{$topic_attrs_no_uwr} == 0) {
        # Only $topic attr is $outer, all result attrs from $outer unwrap.
        for my $topic_t (values %{$topic_b}) {
            my $result_t = $topic_t->{$outer};
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    elsif (@{$inner} == 0) {
        # Unwrap of $outer adds zero attrs to $topic.
        # So this is a simple projection of $topic excising $outer.
        for my $topic_t (values %{$topic_b}) {
            my $result_t = {
                CORE::map { ($_ => $topic_t->{$_}) } @{$topic_attrs_no_uwr}
            };
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    else {
        # Result has at least 1 attr from $outer, at least 1 not from it.
        for my $topic_t (values %{$topic_b}) {
            my $result_t = {
                %{$topic_t->{$outer}},
                CORE::map { ($_ => $topic_t->{$_}) } @{$topic_attrs_no_uwr}
            };
            $result_b->{refaddr $result_t} = $result_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub group {
    my ($topic, $outer, $inner) = @_;

    $topic->_assert_valid_atnm_arg( 'group', '$outer', $outer );
    (my $inner_h, $inner) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'group', '$inner', $inner );

    my (undef, $topic_attrs_no_gr, $inner_attrs_not_in_topic)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $inner_h );
    confess q{group(): Bad $inner arg; that list of attrs to be grouped}
            . q{ isn't a subset of the invocant's heading.}
        if @{$inner_attrs_not_in_topic} > 0;
    confess q{group(): Bad $outer arg; that name for a new attr to add}
            . q{ to the invocant, consisting of grouped invocant attrs,}
            . q{ duplicates an attr of the invocant not being grouped.}
        if any { $_ eq $outer } @{$topic_attrs_no_gr};

    return $topic->_group( $outer, $inner, $topic_attrs_no_gr, $inner_h );
}

sub _group {
    my ($topic, $outer, $inner, $topic_attrs_no_gr, $inner_h) = @_;

    my $result = $topic->_new();

    $result->_heading(
        {CORE::map { ($_ => undef) } @{$topic_attrs_no_gr}, $outer} );

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        # So result body is already correct.
    }
    elsif (@{$inner} == 0) {
        # Group zero $topic attrs as new attr.
        # So this is a simple static extension of $topic w static $outer.
        my $result_b = $result->_body();
        my $inner_r = $topic->_new( [ {} ] );
        for my $topic_t (values %{$topic->_body()}) {
            my $result_t = {$outer => $inner_r, {%{$topic_t}}};
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    elsif (@{$topic_attrs_no_gr} == 0) {
        # Group all $topic attrs as new attr.
        # So $topic is just used as sole attr of sole tuple of result.
        my $result_t = {$outer => $topic};
        $result->_body( {refaddr $result_t => $result_t} );
    }
    else {
        # Group at least one but not all $topic attrs as new attr.
        my $result_b = $result->_body();
        my $topic_index = $topic->_want_index( $topic_attrs_no_gr );
        for my $matched_topic_b (values %{$topic_index}) {

            my $inner_r = $topic->_new();
            $inner_r->_heading( $inner_h );
            my $inner_b = $inner_r->_body();
            for my $topic_t (values %{$matched_topic_b}) {
                my $inner_t
                    = {CORE::map { ($_ => $topic_t->{$_}) } @{$inner}};
                $inner_b->{refaddr $inner_t} = $inner_t;
            }

            my $any_mtpt = (values %{$matched_topic_b})[0];

            my $result_t = {
                $outer => $inner_r,
                CORE::map { ($_ => $any_mtpt->{$_}) } @{$topic_attrs_no_gr}
            };
            $result_b->{refaddr $result_t} = $result_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

sub cmpl_group {
    my ($topic, $outer, $group_per) = @_;

    $topic->_assert_valid_atnm_arg( 'cmpl_group', '$outer', $outer );
    (my $group_per_h, $group_per)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'cmpl_group', '$group_per', $group_per );

    my $topic_h = $topic->_heading();

    confess q{cmpl_group(): Bad $group_per arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if notall { exists $topic_h->{$_} } @{$group_per};

    my $inner = [grep { !$group_per_h->{$_} } CORE::keys %{$topic_h}];
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    my (undef, $topic_attrs_no_gr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h, $inner_h );
    confess q{cmpl_group(): Bad $outer arg; that name for a new attr to}
            . q{ add to th invocant, consisting of grouped invocant attrs,}
            . q{ duplicates an attr of the invocant not being grouped.}
        if any { $_ eq $outer } @{$topic_attrs_no_gr};

    return $topic->_group( $outer, $inner, $topic_attrs_no_gr, $inner_h );
}

###########################################################################

sub ungroup {
    my ($topic, $inner, $outer) = @_;

    (my $inner_h, $inner) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'ungroup', '$inner', $inner );
    $topic->_assert_valid_atnm_arg( 'ungroup', '$outer', $outer );

    my $topic_h = $topic->_heading();

    confess q{ungroup(): Bad $outer arg; that attr name}
            . q{ doesn't match an attr of the invocant's heading.}
        if !exists $topic_h->{$outer};

    my $topic_h_except_outer = {%{$topic_h}};
    delete $topic_h_except_outer->{$outer};

    my ($inner_attrs_dupl_topic, $topic_attrs_no_ugr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h_except_outer, $inner_h );
    confess q{ungroup(): Bad $inner arg; at least one name in that attr}
            . q{ list, which the invocant would be extended with when}
            . q{ ungrouping $topic{$outer}, duplicates an attr of the}
            . q{ invocant not being ungrouped.}
        if @{$inner_attrs_dupl_topic} > 0;

    my $topic_b = $topic->_body();

    for my $topic_t (values %{$topic_b}) {
        my $inner_r = $topic_t->{$outer};
        confess q{ungroup(): Can't ungroup $topic{$outer} because there is}
                . q{ not a same-heading relation val for the $outer attr}
                . q{ of every tuple of $topic whose head matches $inner.}
            if !blessed $inner_r or !$inner_r->isa( __PACKAGE__ )
                or !$topic->_is_identical_hkeys(
                    $inner_h, $inner_r->_heading() );
    }

    if ($topic->degree() == 1) {
        # Ungroup of a unary relation is the N-adic union of its sole
        # attribute's value across all tuples.
        return $topic->_new( $inner )
            ->_union( [CORE::map { $_->{$outer} } values %{$topic_b}] );
    }

    # If we get here, the input relation is not unary.

    my $result = $topic->_new();

    $result->_heading( {%{$topic_h_except_outer}, %{$inner_h}} );

    my $topic_tuples_w_nonemp_inn
        = [grep { !$_->{$outer}->is_empty() } values %{$topic_b}];

    if (@{$topic_tuples_w_nonemp_inn} == 0) {
        # An empty post-basic-filtering $topic means an empty result.
        # So result body is already correct.
    }
    elsif (@{$inner} == 0) {
        # Ungroup of $outer adds zero attrs to $topic.
        # So this is a simple proj of post-basic-filt $topic excis $outer.
        my $result_b = $result->_body();
        for my $topic_t (@{$topic_tuples_w_nonemp_inn}) {
            my $result_t = {
                CORE::map { ($_ => $topic_t->{$_}) } @{$topic_attrs_no_ugr}
            };
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    else {
        # Result has at least 1 attr from $outer, at least 1 not from it.
        my $result_b = $result->_body();
        for my $topic_t (@{$topic_tuples_w_nonemp_inn}) {
            my $no_ugr_t = {CORE::map { ($_ => $topic_t->{$_}) }
                @{$topic_attrs_no_ugr}};
            my $inner_r = $topic_t->{$outer};
            for my $inner_t (values %{$inner_r->_body()}) {
                my $result_t = {%{$inner_t}, %{$no_ugr_t}};
                $result_b->{refaddr $result_t} = $result_t;
            }
        }
    }

    return $result;
}

###########################################################################

sub tclose {
    my ($topic) = @_;

    confess q{tclose(): This method may only be invoked on a}
            . q{ Set::Relation object with exactly 2 (same-typed) attrs.}
        if $topic->degree() != 2;

    if ($topic->cardinality() < 2) {
        # Can't create paths of 2+ arcs when not more than 1 arc exists.
        return $topic;
    }

    # If we get here, there are at least 2 arcs, so there is a chance they
    # may connect into longer paths.

    my ($atnm1, $atnm2) = sort (CORE::keys %{$topic->_heading()});

    return $topic->_rename( { 'x' => $atnm1, 'y' => $atnm2 } )
        ->_tclose_of_xy()
        ->_rename( { $atnm1 => 'x', $atnm2 => 'y' } );
}

# TODO: Reimplement tclose to do all the work internally rather
# than farming out to rename/join/projection/union/etc; this should make
# performance an order of magnitude better and without being complicated.

sub _tclose_of_xy {
    my ($xy) = @_;

    if (!$xy->_is_known_dup_free()) {
        $xy->_dup_free_want_index_over_all_attrs();
    }

    my $xyz = $xy->_rename( { 'y' => 'x', 'z' => 'y' } )
        ->_regular_join( $xy, ['y'], ['z'], ['x'] );

    if ($xyz->is_empty()) {
        # No paths of xy connect to any other paths of xy.
        return $xy;
    }

    # If we get here, then at least one pair of paths in xy can connect
    # to form a longer path.

    my $ttt = $xyz->_projection( ['x', 'z'] )
        ->_rename( { 'y' => 'z' } )
        ->_union( [$xy] );

    if ($ttt->_is_identical( $xy )) {
        # All the longer paths resulting from conn were already in xy.
        return $xy;
    }

    # If we get here, then at least one longer path produced above was not
    # already in xy and was added; so now we need to check if any
    # yet-longer paths can be made from the just-produced.

    return $ttt->_tclose_of_xy();
}

###########################################################################

sub restriction {
    my ($topic, $func, $allow_dup_tuples) = @_;

    $topic->_assert_valid_func_arg( 'restriction', '$func', $func );

    if ($topic->is_empty()) {
        return $topic;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->empty();

    my $topic_b = $topic->_body();
    my $result_b = $result->_body();

    for my $topic_t_refaddr (CORE::keys %{$topic_b}) {
        my $topic_t = $topic_b->{$topic_t_refaddr};
        my $is_matched;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $is_matched = $func->();
        }
        if ($is_matched) {
            $result_b->{$topic_t_refaddr} = $topic_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

sub restr_and_cmpl {
    my ($topic, $func, $allow_dup_tuples) = @_;
    $topic->_assert_valid_func_arg( 'restr_and_cmpl', '$func', $func );
    return $topic->_restr_and_cmpl( $func, $allow_dup_tuples );
}

sub _restr_and_cmpl {
    my ($topic, $func, $allow_dup_tuples) = @_;

    if ($topic->is_empty()) {
        return [$topic, $topic];
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $pass_result = $topic->empty();
    my $fail_result = $topic->empty();

    my $topic_b = $topic->_body();
    my $pass_result_b = $pass_result->_body();
    my $fail_result_b = $fail_result->_body();

    for my $topic_t_refaddr (CORE::keys %{$topic_b}) {
        my $topic_t = $topic_b->{$topic_t_refaddr};
        my $is_matched;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $is_matched = $func->();
        }
        if ($is_matched) {
            $pass_result_b->{$topic_t_refaddr} = $topic_t;
        }
        else {
            $fail_result_b->{$topic_t_refaddr} = $topic_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $pass_result->_is_known_dup_free( 1 );
        $fail_result->_is_known_dup_free( 1 );
    }

    return [$pass_result, $fail_result];
}

sub cmpl_restr {
    my ($topic, $func, $allow_dup_tuples) = @_;

    $topic->_assert_valid_func_arg( 'cmpl_restr', '$func', $func );

    if ($topic->is_empty()) {
        return $topic;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->empty();

    my $topic_b = $topic->_body();
    my $result_b = $result->_body();

    for my $topic_t_refaddr (CORE::keys %{$topic_b}) {
        my $topic_t = $topic_b->{$topic_t_refaddr};
        my $is_matched;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $is_matched = $func->();
        }
        if (!$is_matched) {
            $result_b->{$topic_t_refaddr} = $topic_t;
        }
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub classification {
    my ($topic, $func, $class_attr_name, $group_attr_name,
        $allow_dup_tuples) = @_;

    $topic->_assert_valid_func_arg( 'classification', '$func', $func );
    $topic->_assert_valid_atnm_arg(
        'classification', '$class_attr_name', $class_attr_name );
    $topic->_assert_valid_atnm_arg(
        'classification', '$group_attr_name', $group_attr_name );

    my $result = $topic->_new();

    $result->_heading(
        {$class_attr_name => undef, $group_attr_name => undef} );

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        # So result body is already correct.
        return $result;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $topic_h = $topic->_heading();
    my $topic_b = $topic->_body();

    my $tuples_per_class = {};

    for my $topic_t (values %{$topic_b}) {
        my $class;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $class = $func->();
        }
        my $class_ident_str = $topic->_ident_str( $class );
        if (!exists $tuples_per_class->{$class_ident_str}) {
            $tuples_per_class->{$class_ident_str} = [$class, []];
        }
        push @{$tuples_per_class->{$class_ident_str}->[1]}, $topic_t;
    }

    my $result_b = $result->_body();
    for my $class_ident_str (CORE::keys %{$tuples_per_class}) {
        my ($class, $tuples_in_class)
            = @{$tuples_per_class->{$class_ident_str}};

        my $inner_r = $topic->_new();
        $inner_r->_heading( $topic_h );
        $inner_r->_body(
            {CORE::map { (refaddr $_ => $_) } @{$tuples_in_class}} );

        my $result_t = {
            $class_attr_name => $class,
            $group_attr_name => $inner_r,
        };
        $result_b->{refaddr $result_t} = $result_t;
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub extension {
    my ($topic, $attr_names, $func, $allow_dup_tuples) = @_;

    (my $exten_h, $attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        'extension', '$attr_names', $attr_names );
    $topic->_assert_valid_func_arg( 'extension', '$func', $func );

    my ($both, undef, undef)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $exten_h );
    confess q{extension(): Bad $attr_names arg; that attr list}
            . q{ isn't disjoint with the invocant's heading.}
        if @{$both} > 0;

    return $topic->_extension(
        $attr_names, $func, $exten_h, $allow_dup_tuples );
}

sub _extension {
    my ($topic, $attr_names, $func, $exten_h, $allow_dup_tuples) = @_;

    if (@{$attr_names} == 0) {
        # Extension of input by zero attrs yields the input.
        return $topic;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->_new();

    $result->_heading( {%{$topic->_heading()}, %{$exten_h}} );

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $exten_t;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $exten_t = $func->();
        }
        $topic->_assert_valid_tuple_result_of_func_arg(
            'extension', '$func', '$attr_names', $exten_t, $exten_h );
        $exten_t = $topic->_import_nfmt_tuple( $exten_t );
        my $result_t = {%{$topic_t}, %{$exten_t}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub static_exten {
    my ($topic, $attrs) = @_;

    confess q{static_exten(): Bad $attrs arg; it isn't a hash-ref.}
        if ref $attrs ne 'HASH';

    my ($both, undef, undef)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $attrs );
    confess q{static_exten(): Bad $attrs arg; that attr list}
            . q{ isn't disjoint with the invocant's heading.}
        if @{$both} > 0;

    confess q{static_exten(): Bad $attrs arg;}
            . q{ it is a hash-ref, and there exist circular refs}
            . q{ between itself or its tuple-valued components.}
        if $topic->_tuple_arg_has_circular_refs( $attrs );

    return $topic->_static_exten( $attrs );
}

sub _static_exten {
    my ($topic, $attrs) = @_;

    if ((scalar CORE::keys %{$attrs}) == 0) {
        # Extension of input by zero attrs yields the input.
        return $topic;
    }

    $attrs = $topic->_import_nfmt_tuple( $attrs );

    my $result = $topic->_new();

    $result->_heading( {%{$topic->_heading()},
        CORE::map { ($_ => undef) } CORE::keys %{$attrs}} );

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $result_t = {%{$topic_t}, %{$attrs}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    if ($topic->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub map {
    my ($topic, $result_attr_names, $func, $allow_dup_tuples) = @_;

    (my $result_h, $result_attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'map', '$result_attr_names', $result_attr_names );
    $topic->_assert_valid_func_arg( 'map', '$func', $func );

    if (@{$result_attr_names} == 0) {
        # Map to zero attrs yields identity relation zero or one.
        if ($topic->is_empty()) {
            return $topic->_new();
        }
        else {
            return $topic->_new( [ {} ] );
        }
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->_new();

    $result->_heading( $result_h );

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $result_t;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $result_t = $func->();
        }
        $topic->_assert_valid_tuple_result_of_func_arg(
            'map', '$func', '$result_attr_names', $result_t, $result_h );
        $result_t = $topic->_import_nfmt_tuple( $result_t );
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub summary {
    my ($topic, $group_per, $summ_attr_names, $summ_func,
        $allow_dup_tuples) = @_;

    (my $group_per_h, $group_per)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'summary', '$group_per', $group_per );
    (my $exten_h, $summ_attr_names)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'summary', '$summ_attr_names', $summ_attr_names );
    $topic->_assert_valid_func_arg( 'summary', '$summ_func', $summ_func );

    my $topic_h = $topic->_heading();

    confess q{summary(): Bad $group_per arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if notall { exists $topic_h->{$_} } @{$group_per};

    confess q{summary(): Bad $summ_attr_names arg; one or more of those}
            . q{ names for new summary attrs to add to the invocant }
            . q{ duplicates an attr of the invocant not being grouped.}
        if any { exists $group_per_h->{$_} } @{$summ_attr_names};

    my $inner = [grep { !$group_per_h->{$_} } CORE::keys %{$topic_h}];
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    my (undef, $topic_attrs_no_gr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h, $inner_h );

    my $result = $topic->_new();

    $result->_heading( {%{$group_per_h}, %{$exten_h}} );

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        return $result;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    # Note: We skipped a number of shortcuts that _group() has for
    # brevity, leaving just the general case; they might come back later.

    my $result_b = $result->_body();
    my $topic_index = $topic->_want_index( $topic_attrs_no_gr );
    for my $matched_topic_b (values %{$topic_index}) {

        my $inner_r = $topic->_new();
        $inner_r->_heading( $inner_h );
        my $inner_b = $inner_r->_body();
        for my $topic_t (values %{$matched_topic_b}) {
            my $inner_t = {CORE::map { ($_ => $topic_t->{$_}) } @{$inner}};
            $inner_b->{refaddr $inner_t} = $inner_t;
        }

        my $any_mtpt = (values %{$matched_topic_b})[0];
        my $group_per_t = {CORE::map { ($_ => $any_mtpt->{$_}) }
            @{$topic_attrs_no_gr}};

        my $exten_t;
        {
            local $_ = {
                'summarize' => $inner_r,
                'per' => $topic->_export_nfmt_tuple( $group_per_t ),
            };
            $exten_t = $summ_func->();
        }
        $topic->_assert_valid_tuple_result_of_func_arg( 'summary',
            '$summ_func', '$summ_attr_names', $exten_t, $exten_h );
        $exten_t = $topic->_import_nfmt_tuple( $exten_t );

        my $result_t = {%{$group_per_t}, %{$exten_t}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub cardinality_per_group {
    my ($topic, $count_attr_name, $group_per, $allow_dup_tuples) = @_;

    $topic->_assert_valid_atnm_arg(
        'cardinality_per_group', '$count_attr_name', $count_attr_name );
    (my $group_per_h, $group_per)
        = $topic->_atnms_hr_from_assert_valid_atnms_arg(
            'cardinality_per_group', '$group_per', $group_per );

    my $topic_h = $topic->_heading();

    confess q{cardinality_per_group(): Bad $group_per arg;}
            . q{ that attr list isn't a subset of the invocant's heading.}
        if notall { exists $topic_h->{$_} } @{$group_per};

    confess q{cardinality_per_group(): Bad $count_attr_name arg;}
            . q{ that name for a new attr to add to the invocant}
            . q{ duplicates an attr of the invocant not being grouped.}
        if exists $group_per_h->{$count_attr_name};

    my $inner = [grep { !$group_per_h->{$_} } CORE::keys %{$topic_h}];
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    my (undef, $topic_attrs_no_gr, undef)
        = $topic->_ptn_conj_and_disj( $topic_h, $inner_h );

    my $result = $topic->_new();

    $result->_heading( {%{$group_per_h}, $count_attr_name => undef} );

    if ($topic->is_empty()) {
        # An empty $topic means an empty result.
        return $result;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result_b = $result->_body();
    my $topic_index = $topic->_want_index( $topic_attrs_no_gr );
    for my $matched_topic_b (values %{$topic_index}) {
        my $count = scalar CORE::keys %{$matched_topic_b};
        my $any_mtpt = (values %{$matched_topic_b})[0];
        my $group_per_t = {CORE::map { ($_ => $any_mtpt->{$_}) }
            @{$topic_attrs_no_gr}};
        my $result_t = {%{$group_per_t}, $count_attr_name => $count};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

sub count_per_group {
    my ($self, @args) = @_;
    return $self->cardinality_per_group( @args );
}

###########################################################################

sub _atnms_hr_from_assert_valid_atnms_arg {
    my ($self, $rtn_nm, $arg_nm, $atnms) = @_;

    if (defined $atnms and !ref $atnms) {
        $atnms = [$atnms];
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be an array-ref or a defined non-ref.}
        if ref $atnms ne 'ARRAY';
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it should be just be a list of attr names,}
            . q{ but at least one name is undefined or is a ref.}
        if notall { defined $_ and !ref $_ } @{$atnms};
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it specifies a list of}
            . q{ attr names with at least one duplicated name.}
        if (uniqstr @{$atnms}) != @{$atnms};

    my $heading = {CORE::map { ($_ => undef) } @{$atnms}};
    return ($heading, $atnms);
}

sub _assert_valid_atnm_arg {
    my ($self, $rtn_nm, $arg_nm, $atnm) = @_;
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it should be just be an attr name,}
            . q{ but it is undefined or is a ref.}
        if !defined $atnm or ref $atnm;
}

sub _assert_valid_nnint_arg {
    my ($self, $rtn_nm, $arg_nm, $atnm) = @_;
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it should be just be a non-negative integer,}
            . q{ but it is undefined or is a ref or is some other scalar.}
        if !defined $atnm or ref $atnm or not $atnm =~ /^[0-9]+$/;
}

sub _assert_valid_func_arg {
    my ($self, $rtn_nm, $arg_nm, $func) = @_;
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be a Perl subroutine reference.}
        if ref $func ne 'CODE';
}

sub _assert_valid_tuple_result_of_func_arg {
    my ($self, $rtn_nm, $arg_nm_func, $arg_nm_attrs, $result_t, $heading)
        = @_;
    confess qq{$rtn_nm(): Bad $arg_nm_func arg;}
            . q{ at least one result of executing that Perl subroutine}
            . q{ reference was not a hash-ref or it didn't have the same}
            . qq{ set of hkeys as specified by the $arg_nm_attrs arg.}
        if ref $result_t ne 'HASH'
            or !$self->_is_identical_hkeys( $heading, $result_t );
    confess qq{$rtn_nm(): Bad $arg_nm_func arg;}
            . q{ at least one result of executing that Perl subroutine}
            . q{ reference was a hash-ref, and there exist circular refs}
            . q{ between itself or its tuple-valued components.}
        if $self->_tuple_arg_has_circular_refs( $result_t );
}

sub _normalize_same_heading_relation_arg {
    my ($self, $rtn_nm, $arg_nm, $other) = @_;
    if (blessed $other and $other->can( 'does' )
            and $other->does( 'Set::Relation' )
            and !$other->isa( __PACKAGE__ )) {
        $other = $self->_new( $other );
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg; it isn't a Set::Relation}
            . q{ object, or it doesn't have exactly the}
            . q{ same set of attr names as the invocant.}
        if !blessed $other or !$other->isa( __PACKAGE__ )
            or !$self->_is_identical_hkeys(
                $self->_heading(), $other->_heading() );
    return $other;
}

sub _normalize_relation_arg {
    my ($self, $rtn_nm, $arg_nm, $other) = @_;
    if (blessed $other and $other->can( 'does' )
            and $other->does( 'Set::Relation' )
            and !$other->isa( __PACKAGE__ )) {
        $other = $self->_new( $other );
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it isn't a Set::Relation object.}
        if !blessed $other or !$other->isa( __PACKAGE__ );
    return $other;
}

###########################################################################

sub is_identical {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_relation_arg(
        'is_identical', '$other', $other );
    return $topic->_is_identical( $other );
}

sub _is_identical {
    my ($topic, $other) = @_;
    return ($topic->degree() == $other->degree()
        and $topic->_is_identical_hkeys(
            $topic->_heading(), $other->_heading() )
        and $topic->cardinality() == $other->cardinality()
        and $topic->_is_identical_hkeys(
            $topic->_dup_free_want_index_over_all_attrs(),
            $other->_dup_free_want_index_over_all_attrs() ));
}

###########################################################################

sub is_subset {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_same_heading_relation_arg(
        'is_subset', '$other', $other );
    my $other_i = $other->_dup_free_want_index_over_all_attrs();
    return all { exists $other_i->{$_} }
        CORE::keys %{$topic->_dup_free_want_index_over_all_attrs()};
}

sub is_superset {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_same_heading_relation_arg(
        'is_superset', '$other', $other );
    my $topic_i = $topic->_dup_free_want_index_over_all_attrs();
    return all { exists $topic_i->{$_} }
        CORE::keys %{$other->_dup_free_want_index_over_all_attrs()};
}

sub is_proper_subset {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_same_heading_relation_arg(
        'is_proper_subset', '$other', $other );
    my $other_i = $other->_dup_free_want_index_over_all_attrs();
    return ($topic->cardinality() < $other->cardinality()
        and all { exists $other_i->{$_} }
            CORE::keys %{$topic->_dup_free_want_index_over_all_attrs()});
}

sub is_proper_superset {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_same_heading_relation_arg(
        'is_proper_superset', '$other', $other );
    my $topic_i = $topic->_dup_free_want_index_over_all_attrs();
    return ($other->cardinality() < $topic->cardinality()
        and all { exists $topic_i->{$_} }
            CORE::keys %{$other->_dup_free_want_index_over_all_attrs()});
}

sub is_disjoint {
    my ($topic, $other) = @_;
    $other = $topic->_normalize_same_heading_relation_arg(
        'is_disjoint', '$other', $other );
    return $topic->_intersection( [$other] )->is_empty();
}

###########################################################################

sub union {
    my ($topic, $others) = @_;
    $others = $topic->_normalize_same_heading_relations_arg(
        'union', '$others', $others );
    return $topic->_union( $others );
}

sub _union {
    my ($topic, $others) = @_;

    my $inputs = [
        grep { !$_->is_empty() } # filter out identity value instances
        $topic, @{$others}];

    if (@{$inputs} == 0) {
        # All inputs were the identity value; so is result.
        return $topic->empty();
    }
    if (@{$inputs} == 1) {
        # Only one non-identity value input; so it is the result.
        return $inputs->[0];
    }

    # If we get here, there are at least 2 non-empty input relations.

    my $result = $topic->empty();

    $result->_body( {CORE::map { %{$_->_body()} } @{$inputs}} );

    return $result;
}

###########################################################################

sub exclusion {
    # Also known as symmetric_diff().
    my ($topic, $others) = @_;

    $others = $topic->_normalize_same_heading_relations_arg(
        'exclusion', '$others', $others );

    my $inputs = [
        sort { $b->cardinality() <=> $a->cardinality() }
        grep { !$_->is_empty() } # filter out identity value instances
        $topic, @{$others}];

    if (@{$inputs} == 0) {
        # All inputs were the identity value; so is result.
        return $topic->empty();
    }
    if (@{$inputs} == 1) {
        # Only one non-identity value input; so it is the result.
        return $inputs->[0];
    }

    # If we get here, there are at least 2 non-empty input relations.

    my $largest = shift @{$inputs};
    my $largest_i = $largest->_dup_free_want_index_over_all_attrs();

    my $t_by_ident_str = {CORE::map {
            ($_ => (values %{$largest_i->{$_}})[0])
        } CORE::keys %{$largest_i}};

    for my $input (@{$inputs}) {
        my $input_i = $input->_dup_free_want_index_over_all_attrs();
        for my $tuple_ident_str (CORE::keys %{$input_i}) {
            if (exists $t_by_ident_str->{$tuple_ident_str}) {
                delete $t_by_ident_str->{$tuple_ident_str};
            }
            else {
                $t_by_ident_str->{$tuple_ident_str}
                    = (values %{$input_i->{$tuple_ident_str}})[0];
            }
        }
    }

    my $result = $topic->empty();

    $result->_body(
        {CORE::map { (refaddr $_ => $_) } values %{$t_by_ident_str}} );

    $result->_is_known_dup_free( 1 );

    return $result;
}

sub symmetric_diff {
    my ($self, @args) = @_;
    return $self->exclusion( @args );
}

###########################################################################

sub intersection {
    my ($topic, $others) = @_;
    $others = $topic->_normalize_same_heading_relations_arg(
        'intersection', '$others', $others );
    return $topic->_intersection( $others );
}

sub _intersection {
    my ($topic, $others) = @_;

    if (@{$others} == 0) {
        return $topic;
    }

    my $inputs = [
        sort { $a->cardinality( 1 ) <=> $b->cardinality( 1 ) }
        $topic, @{$others}];

    my $smallest = shift @{$inputs};

    if ($smallest->is_empty()) {
        return $smallest;
    }

    # If we get here, there are at least 2 non-empty input relations.

    my $result = $topic->empty();

    my $smallest_i = $smallest->_dup_free_want_index_over_all_attrs();
    my $larger_is = [CORE::map {
            $_->_dup_free_want_index_over_all_attrs()
        } @{$inputs}];
    my $result_b = $result->_body();

    TUPLE:
    for my $tuple_ident_str (CORE::keys %{$smallest_i}) {
        for my $larger_i (@{$larger_is}) {
            next TUPLE
                if !exists $larger_i->{$tuple_ident_str};
        }
        my ($tuple_refaddr, $tuple) = %{$smallest_i->{$tuple_ident_str}};
        $result_b->{$tuple_refaddr} = $tuple;
    }

    $result->_is_known_dup_free( 1 );

    return $result;
}

###########################################################################

sub _normalize_same_heading_relations_arg {
    my ($self, $rtn_nm, $arg_nm, $others) = @_;

    my $self_h = $self->_heading();

    if (blessed $others and $others->can( 'does' )
            and $others->does( 'Set::Relation' )) {
        $others = [$others];
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be an array-ref or a Set::Relation object.}
        if ref $others ne 'ARRAY';
    $others = [CORE::map {
        my $other = $_;
        if (blessed $other and $other->can( 'does' )
                and $other->does( 'Set::Relation' )
                and !$other->isa( __PACKAGE__ )) {
            $other = $self->_new( $other );
        }
        confess qq{$rtn_nm(): Bad $arg_nm arg elem;}
                . q{ it isn't a Set::Relation object, or it doesn't have}
                . q{ exactly the same set of attr names as the invocant.}
            if !blessed $other or !$other->isa( __PACKAGE__ )
                or !$self->_is_identical_hkeys(
                    $self_h, $other->_heading() );
        $other;
    } @{$others}];

    return $others;
}

sub _normalize_relations_arg {
    my ($self, $rtn_nm, $arg_nm, $others) = @_;

    if (blessed $others and $others->can( 'does' )
            and $others->does( 'Set::Relation' )) {
        $others = [$others];
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be an array-ref or a Set::Relation object.}
        if ref $others ne 'ARRAY';
    $others = [CORE::map {
        my $other = $_;
        if (blessed $other and $other->can( 'does' )
                and $other->does( 'Set::Relation' )
                and !$other->isa( __PACKAGE__ )) {
            $other = $self->_new( $other );
        }
        confess qq{$rtn_nm(): Bad $arg_nm arg elem;}
                . q{ it isn't a Set::Relation object.}
            if !blessed $other or !$other->isa( __PACKAGE__ );
        $other;
    } @{$others}];

    return $others;
}

###########################################################################

sub diff {
    my ($source, $filter) = @_;
    $filter = $source->_normalize_same_heading_relation_arg(
        'diff', '$other', $filter );
    return $source->_diff( $filter );
}

sub _diff {
    my ($source, $filter) = @_;
    if ($source->is_empty() or $filter->is_empty()) {
        return $source;
    }
    return $source->_regular_diff( $filter );
}

sub _regular_diff {
    my ($source, $filter) = @_;

    my $result = $source->empty();

    my $source_i = $source->_dup_free_want_index_over_all_attrs();
    my $filter_i = $filter->_dup_free_want_index_over_all_attrs();
    my $result_b = $result->_body();

    for my $tuple_ident_str (CORE::keys %{$source_i}) {
        if (!exists $filter_i->{$tuple_ident_str}) {
            my ($tuple_refaddr, $tuple) = %{$source_i->{$tuple_ident_str}};
            $result_b->{$tuple_refaddr} = $tuple;
        }
    }

    $result->_is_known_dup_free( 1 );

    return $result;
}

###########################################################################

sub semidiff {
    my ($source, $filter) = @_;
    $filter = $source->_normalize_relation_arg(
        'semidiff', '$filter', $filter );
    if ($source->is_empty() or $filter->is_empty()) {
        return $source;
    }
    return $source->_regular_diff( $source->_semijoin( $filter ) );
}

sub antijoin {
    my ($self, @args) = @_;
    return $self->semidiff( @args );
}

sub semijoin_and_diff {
    my ($source, $filter) = @_;
    $filter = $source->_normalize_relation_arg(
        'semijoin_and_diff', '$filter', $filter );
    return $source->_semijoin_and_diff( $filter );
}

sub _semijoin_and_diff {
    my ($source, $filter) = @_;
    if ($source->is_empty()) {
        return [$source, $source];
    }
    if ($filter->is_empty()) {
        return [$source->empty(), $source];
    }
    my $semijoin = $source->_semijoin( $filter );
    return [$semijoin, $source->_regular_diff( $semijoin )];
}

sub semijoin {
    my ($source, $filter) = @_;
    $filter = $source->_normalize_relation_arg(
        'semijoin', '$filter', $filter );
    return $source->_semijoin( $filter );
}

sub _semijoin {
    my ($source, $filter) = @_;

    if ($source->is_empty()) {
        return $source;
    }
    if ($filter->is_empty()) {
        return $source->empty();
    }

    # If we get here, both inputs have at least one tuple.

    if ($source->is_nullary() or $filter->is_nullary()) {
        return $source;
    }

    # If we get here, both inputs also have at least one attribute.

    my ($both, $source_only, $filter_only) = $source->_ptn_conj_and_disj(
        $source->_heading(), $filter->_heading() );

    if (@{$both} == 0) {
        # The inputs have disjoint headings; result is source.
        return $source;
    }
    if (@{$source_only} == 0 and @{$filter_only} == 0) {
        # The inputs have identical headings; result is intersection.
        return $source->_intersection( [$filter] );
    }

    # If we get here, the inputs also have overlapping non-ident headings.

    return $source->_regular_semijoin( $filter, $both );
}

sub _regular_semijoin {
    my ($source, $filter, $both) = @_;

    my $result = $source->empty();

    my ($sm, $lg) = ($source->cardinality( 1 ) < $filter->cardinality( 1 ))
        ? ($source, $filter) : ($filter, $source);

    my $sm_index = $sm->_want_index( $both );
    my $lg_index = $lg->_want_index( $both );
    my $source_index = $source->_want_index( $both );
    my $result_b = $result->_body();

    for my $subtuple_ident_str (CORE::keys %{$sm_index}) {
        if (exists $lg_index->{$subtuple_ident_str}) {
            my $matched_source_b = $source_index->{$subtuple_ident_str};
            for my $tuple_refaddr (CORE::keys %{$matched_source_b}) {
                $result_b->{$tuple_refaddr}
                    = $matched_source_b->{$tuple_refaddr};
            }
        }
    }

    if ($source->_is_known_dup_free() and $filter->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub join {
    my ($topic, $others) = @_;
    $others = $topic->_normalize_relations_arg(
        'join', '$others', $others );
    return $topic->_join( $others );
}

sub _join {
    my ($topic, $others) = @_;

    if (@{$others} == 0) {
        return $topic;
    }

    my $inputs = [$topic, @{$others}];

    if (any { $_->is_empty() } @{$inputs}) {
        # At least one input has zero tuples; so does result.
        my $result = $topic->_new();
        my $result_h = {CORE::map { %{$_->_heading()} } @{$inputs}};
        $result->_heading( $result_h );
        return $result;
    }

    # If we get here, all inputs have at least one tuple.

    $inputs = [
        sort { $a->cardinality( 1 ) <=> $b->cardinality( 1 ) }
        grep { !$_->is_nullary() } # filter out identity value instances
        @{$inputs}];

    if (@{$inputs} == 0) {
        # All inputs were the identity value; so is result.
        return $topic;
    }
    if (@{$inputs} == 1) {
        # Only one non-identity value input; so it is the result.
        return $inputs->[0];
    }

    # If we get here, there are at least 2 non-empty non-nullary inp rels.

    my $result = shift @{$inputs};
    INPUT:
    for my $input (@{$inputs}) {
        # TODO: Optimize this better by determining more strategic order
        # to join the various inputs, such as by doing intersections first,
        # then semijoins, then regular joins, then cross-products.
        # But at least we're going min to max cardinality meanwhile.

        my ($both, $result_only, $input_only)
            = $result->_ptn_conj_and_disj(
                $result->_heading(), $input->_heading() );

        if (@{$both} == 0) {
            # The inputs have disjoint headings; result is cross-product.
            $result = $result->_regular_product( $input );
            next INPUT;
        }
        if (@{$result_only} == 0 and @{$input_only} == 0) {
            # The inputs have identical headings; result is intersection.
            $result = $result->_intersection( [$input] );
            next INPUT;
        }

        # If we get here, the inputs also have overlapping non-ident heads.

        if (@{$result_only} == 0) {
            # The first input's attrs are a proper subset of the second's;
            # result has same heading as second, a subset of sec's tuples.
            $result = $input->_regular_semijoin( $result, $both );
            next INPUT;
        }
        if (@{$input_only} == 0) {
            # The second input's attrs are a proper subset of the first's;
            # result has same heading as first, a subset of first's tuples.
            $result = $result->_regular_semijoin( $input, $both );
            next INPUT;
        }

        # If we get here, both inputs also have mini one attr of their own.

        $result = $result->_regular_join(
            $input, $both, $result_only, $input_only );
    }
    return $result;
}

sub _regular_join {
    my ($topic, $other, $both, $topic_only, $other_only) = @_;

    my $result = $topic->_new();

    $result->_heading( {CORE::map { ($_ => undef) }
        @{$both}, @{$topic_only}, @{$other_only}} );

    my ($sm, $lg) = ($topic->cardinality( 1 ) < $other->cardinality( 1 ))
        ? ($topic, $other) : ($other, $topic);

    my $sm_index = $sm->_want_index( $both );
    my $lg_index = $lg->_want_index( $both );
    my $result_b = {};

    for my $subtuple_ident_str (CORE::keys %{$sm_index}) {
        if (exists $lg_index->{$subtuple_ident_str}) {
            my $matched_sm_b = $sm_index->{$subtuple_ident_str};
            my $matched_lg_b = $lg_index->{$subtuple_ident_str};
            for my $sm_t (values %{$matched_sm_b}) {
                for my $lg_t (values %{$matched_lg_b}) {
                    my $result_t = {%{$sm_t}, %{$lg_t}};
                    $result_b->{refaddr $result_t} = $result_t;
                }
            }
        }
    }
    $result->_body( $result_b );

    if ($topic->_is_known_dup_free() and $other->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub product {
    my ($topic, $others) = @_;

    $others = $topic->_normalize_relations_arg(
        'product', '$others', $others );

    if (@{$others} == 0) {
        return $topic;
    }

    my $inputs = [$topic, @{$others}];

    my $attr_names
        = [CORE::map { CORE::keys %{$_->_heading()} } @{$inputs}];

    confess q{product(): Bad $others arg;}
            . q{ one of its elems has an attr name duplicated by}
            . q{ either the invocant or another $others elem.}
        if (uniqstr @{$attr_names}) != @{$attr_names};

    if (any { $_->is_empty() } @{$inputs}) {
        # At least one input has zero tuples; so does result.
        my $result = $topic->_new();
        $result->_heading( {CORE::map { ($_ => undef) } @{$attr_names}} );
        return $result;
    }

    # If we get here, all inputs have at least one tuple.

    $inputs = [
        sort { $a->cardinality( 1 ) <=> $b->cardinality( 1 ) }
        grep { !$_->is_nullary() } # filter out identity value instances
        @{$inputs}];

    if (@{$inputs} == 0) {
        # All inputs were the identity value; so is result.
        return $topic;
    }
    if (@{$inputs} == 1) {
        # Only one non-identity value input; so it is the result.
        return $inputs->[0];
    }

    # If we get here, there are at least 2 non-empty non-nullary inp rels.

    my $result = shift @{$inputs};
    for my $input (@{$inputs}) {
        $result = $result->_regular_product( $input );
    }
    return $result;
}

sub _regular_product {
    my ($topic, $other) = @_;

    my $result = $topic->_new();

    $result->_heading( {%{$topic->_heading()}, %{$other->_heading()}} );

    my ($sm, $lg) = ($topic->cardinality( 1 ) < $other->cardinality( 1 ))
        ? ($topic, $other) : ($other, $topic);

    my $sm_b = $sm->_body();
    my $lg_b = $lg->_body();
    my $result_b = {};

    for my $sm_t (values %{$sm_b}) {
        for my $lg_t (values %{$lg_b}) {
            my $result_t = {%{$sm_t}, %{$lg_t}};
            $result_b->{refaddr $result_t} = $result_t;
        }
    }
    $result->_body( $result_b );

    if ($topic->_is_known_dup_free() and $other->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub quotient {
    my ($dividend, $divisor) = @_;

    $divisor = $dividend->_normalize_relation_arg(
        'quotient', '$divisor', $divisor );

    my (undef, $dividend_only, $divisor_only)
        = $dividend->_ptn_conj_and_disj(
            $dividend->_heading(), $divisor->_heading() );

    confess q{quotient(): Bad $divisor arg;}
            . q{ its heading isn't a subset of the invocant's heading.}
        if @{$divisor_only} > 0;

    my $proj_of_dividend_only = $dividend->_projection( $dividend_only );

    if ($dividend->is_empty() or $divisor->is_empty()) {
        # At least one input has zero tup; res has all tup o dividend proj.
        return $proj_of_dividend_only;
    }

    # If we get here, both inputs have at least one tuple.

    if ($dividend->is_nullary() or $divisor->is_nullary()) {
        # Both inputs or just divisor is ident-one rel; result is dividend.
        return $dividend;
    }

    # If we get here, divisor has at least one attribute,
    # and divisor heading is proper subset of dividend heading.

    return $proj_of_dividend_only
        ->_diff( $proj_of_dividend_only
            ->_regular_product( $divisor )
            ->_diff( $dividend )
            ->_projection( $dividend_only )
        );
}

###########################################################################

sub composition {
    my ($topic, $other) = @_;

    $other = $topic->_normalize_relation_arg(
        'composition', '$other', $other );

    my ($both, $topic_only, $other_only) = $topic->_ptn_conj_and_disj(
        $topic->_heading(), $other->_heading() );

    if ($topic->is_empty() or $other->is_empty()) {
        # At least one input has zero tuples; so does result.
        return $topic->_new( [@{$topic_only}, @{$other_only}] );
    }

    # If we get here, both inputs have at least one tuple.

    if ($topic->is_nullary()) {
        # First input is identity-one relation; result is second input.
        return $other;
    }
    if ($other->is_nullary()) {
        # Second input is identity-one relation; result is first input.
        return $topic;
    }

    # If we get here, both inputs also have at least one attribute.

    if (@{$both} == 0) {
        # The inputs have disjoint headings; result is cross-product.
        return $topic->_regular_product( $other );
    }
    if (@{$topic_only} == 0 and @{$other_only} == 0) {
        # The inputs have identical headings; result is ident-one relation.
        return $topic->_new( [ {} ] );
    }

    # If we get here, the inputs also have overlapping non-ident headings.

    if (@{$topic_only} == 0) {
        # The first input's attributes are a proper subset of the second's;
        # result has same heading as second, a subset of second's tuples.
        return $other->_regular_semijoin( $topic, $both )
            ->_projection( $other_only );
    }
    if (@{$other_only} == 0) {
        # The second input's attributes are a proper subset of the first's;
        # result has same heading as first, a subset of first's tuples.
        return $topic->_regular_semijoin( $other, $both )
            ->_projection( $topic_only );
    }

    # If we get here, both inputs also have at least one attr of their own.

    return $topic->_regular_join(
        $other, $both, $topic_only, $other_only )
            ->_projection( [@{$topic_only}, @{$other_only}] );
}

###########################################################################

sub _ptn_conj_and_disj {
    # inputs are hashes, results are arrays
    my ($self, $src1, $src2) = @_;
    my $both = [grep { exists $src1->{$_} } CORE::keys %{$src2}];
    my $both_h = {CORE::map { ($_ => undef) } @{$both}};
    my $only1 = [grep { !exists $both_h->{$_} } CORE::keys %{$src1}];
    my $only2 = [grep { !exists $both_h->{$_} } CORE::keys %{$src2}];
    return ($both, $only1, $only2);
}

###########################################################################

sub _want_index {
    my ($self, $atnms) = @_;
    if (@{$atnms} == $self->degree()) {
        # Special case; index is over all attributes of the relation, so
        # create this index in a special way that includes dup elimination.
        return $self->_dup_free_want_index_over_all_attrs();
    }
    my $subheading = {CORE::map { ($_ => undef) } @{$atnms}};
    my $subheading_ident_str = $self->_heading_ident_str( $subheading );
    my $indexes = $self->_indexes();
    if (!exists $indexes->{$subheading_ident_str}) {
        my $index_and_meta = $indexes->{$subheading_ident_str}
            = [ $subheading, {} ];
        my $index = $index_and_meta->[1];
        my $body = $self->_body();
        for my $tuple_refaddr (CORE::keys %{$body}) {
            my $tuple = $body->{$tuple_refaddr};
            my $subtuple_ident_str = $self->_ident_str(
                {CORE::map { ($_ => $tuple->{$_}) } @{$atnms}} );
            my $matched_b = $index->{$subtuple_ident_str} ||= {};
            $matched_b->{$tuple_refaddr} = $tuple;
        }
    }
    return $indexes->{$subheading_ident_str}->[1];
}

###########################################################################

sub _dup_free_want_index_over_all_attrs {
    my ($self) = @_;

    my $heading = $self->_heading();
    my $indexes = $self->_indexes();

    my $heading_ident_str = $self->_heading_ident_str( $heading );

    if (!exists $indexes->{$heading_ident_str}) {
        my $extras_to_delete = {};

        my $body = $self->_body();
        my $index_and_meta = $indexes->{$heading_ident_str}
            = [ $heading, {} ];
        my $index = $index_and_meta->[1];
        for my $tuple_refaddr (CORE::keys %{$body}) {
            my $tuple = $body->{$tuple_refaddr};
            my $tuple_ident_str = $self->_ident_str( $tuple );
            if (exists $index->{$tuple_ident_str}) {
                delete $body->{$tuple_refaddr};
                $extras_to_delete->{$tuple_refaddr} = $tuple;
                next;
            }
            $index->{$tuple_ident_str} = {$tuple_refaddr => $tuple};
        }

        if ((CORE::keys %{$extras_to_delete}) > 0) {
            for my $subheading_ident_str (CORE::keys %{$indexes}) {
                next
                    if $subheading_ident_str eq $heading_ident_str;
                my ($subheading, $index)
                    = @{$indexes->{$subheading_ident_str}};
                for my $tuple_refaddr (CORE::keys %{$extras_to_delete}) {
                    my $tuple = $extras_to_delete->{$tuple_refaddr};
                    my $subtuple_ident_str = $self->_ident_str(
                        {CORE::map { ($_ => $tuple->{$_}) }
                            CORE::keys %{$subheading}} );
                    delete $index->{$subtuple_ident_str}->{$tuple_refaddr};
                }
            }
        }

        $self->_is_known_dup_free( 1 );
    }

    return $indexes->{$heading_ident_str}->[1];
}

###########################################################################

sub join_with_group {
    my ($primary, $secondary, $group_attr) = @_;

    $secondary = $primary->_normalize_relation_arg(
        'join_with_group', '$secondary', $secondary );
    $primary->_assert_valid_atnm_arg(
        'join_with_group', '$group_attr', $group_attr );

    my $primary_h = $primary->_heading();

    confess q{join_with_group(): Bad $group_attr arg;}
            . q{ that name for a new attr to add}
            . q{ to $primary, consisting of grouped $secondary-only attrs,}
            . q{ duplicates an attr of $primary (not being grouped).}
        if exists $primary_h->{$group_attr};

    # TODO: inline+merge what join/group do for better performance.

    my ($both, $primary_only, $inner) = $primary->_ptn_conj_and_disj(
            $primary_h, $secondary->_heading() );
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    return $primary
        ->_join( [$secondary] )
        ->_group( $group_attr, $inner, [CORE::keys %{$primary_h}],
            $inner_h );
}

###########################################################################

sub rank {
    my ($topic, $name, $ord_func) = @_;

    my $topic_h = $topic->_heading();

    $topic->_assert_valid_atnm_arg( 'rank', '$name', $name );
    confess q{rank(): Bad $name arg; that name for a new attr to add}
            . q{ to the invocant, consisting of each tuple's numeric rank,}
            . q{ duplicates an existing attr of the invocant.}
        if exists $topic_h->{$name};

    $topic->_assert_valid_func_arg( 'rank', '$ord_func', $ord_func );

    my $result = $topic->_new();

    $result->_heading( {%{$topic_h}, $name => undef} );

    if ($topic->is_empty()) {
        return $result;
    }

    if (!$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $ext_topic_tuples = [];
    my $topic_tuples_by_ext_tt_ref = {};

    for my $topic_t (values %{$topic->_body()}) {
        my $ext_topic_t = $topic->_export_nfmt_tuple( $topic_t );
        push @{$ext_topic_tuples}, $ext_topic_t;
        $topic_tuples_by_ext_tt_ref->{refaddr $ext_topic_t} = $topic_t;
    }

    my $sorted_ext_topic_tuples = [sort {
        local $_ = { 'a' => $a, 'b' => $b };
        $ord_func->();
    } @{$ext_topic_tuples}];

    my $result_b = $result->_body();

    my $rank = -1;
    for my $ext_topic_t (@{$sorted_ext_topic_tuples}) {
        my $topic_t = $topic_tuples_by_ext_tt_ref->{refaddr $ext_topic_t};
        $rank ++;
        my $result_t = {$name => $rank, %{$topic_t}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub rank_by_attr_names {
    my ($topic, $name, $order_by) = @_;

    my $topic_h = $topic->_heading();

    $topic->_assert_valid_atnm_arg( 'rank_by_attr_names', '$name', $name );
    confess q{rank_by_attr_names(): Bad $name arg; that name for a new}
            . q{ attr to add to the invocant, consisting of each tuple's}
            . q{ numeric rank, duplicates an existing attr of th invocant.}
        if exists $topic_h->{$name};

    $order_by = $topic->_normalize_order_by_arg(
        'rank_by_attr_names', '$order_by', $order_by );

    my $result = $topic->_new();

    $result->_heading( {%{$topic_h}, $name => undef} );

    if ($topic->is_empty()) {
        return $result;
    }

    my $sort_func = $topic->_sort_func_from_order_by( $order_by );

    if (!$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result_b = $result->_body();

    my $rank = -1;
    for my $topic_t (@{$sort_func->( $topic )}) {
        $rank ++;
        my $result_t = {$name => $rank, %{$topic_t}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub _normalize_order_by_arg {
    my ($topic, $rtn_nm, $arg_nm, $order_by) = @_;

    if (defined $order_by and !ref $order_by) {
        $order_by = [$order_by];
    }
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it must be an array-ref or a defined non-ref.}
        if ref $order_by ne 'ARRAY';

    $order_by = [CORE::map {
              (ref $_ ne 'ARRAY') ? [$_, 0, 'cmp']
            : (@{$_} == 1)        ? [@{$_}, 0, 'cmp']
            : (@{$_} == 2)        ? [@{$_}, 'cmp']
            :                       $_
        } @{$order_by}];
    confess qq{$rtn_nm(): Bad $arg_nm arg elem;}
            . q{ it must be a 1-3 elem array-ref or a defined non-ref,}
            . q{ its first elem must be a valid attr name (defin non-ref),}
            . q{ and its third elem must be undef or one of 'cmp'|'<=>'.}
        if notall {
                ref $_ eq 'ARRAY' and @{$_} == 3
                and defined $_->[0] and !ref $_->[0]
                and (!defined $_->[2]
                    or $_->[2] eq 'cmp' or $_->[2] eq '<=>')
            } @{$order_by};

    my $atnms = [CORE::map { $_->[0] } @{$order_by}];
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ it specifies a list of}
            . q{ attr names with at least one duplicated name.}
        if (uniqstr @{$atnms}) != @{$atnms};

    my $topic_h = $topic->_heading();
    confess qq{$rtn_nm(): Bad $arg_nm arg;}
            . q{ the list of attr names it specifies isn't a subset of the}
            . q{ heading of the relation defined by the $members arg.}
        if notall { exists $topic_h->{$_} } @{$atnms};

    return $order_by;
}

###########################################################################

sub _sort_func_from_order_by {
    my ($topic, $order_by) = @_;
    my $sort_func_perl
    = "sub {\n"
        . "my (\$topic) = \@_;\n"
        . "return [sort {\n"
            . (CORE::join ' || ', '0', CORE::map {
                    my ($name, $is_reverse_order, $compare_op) = @{$_};
                    $compare_op ||= 'cmp';
                    ($is_reverse_order
                        ? "\$b->{'$name'} $compare_op \$a->{'$name'}"
                        : "\$a->{'$name'} $compare_op \$b->{'$name'}");
                } @{$order_by}) . "\n"
        . "} values \%{\$topic->_body()}];\n"
    . "}\n"
    ;
    my $sort_func = eval $sort_func_perl;
    if (my $err = $@) {
        confess qq{Oops, failed to compile Perl sort func from order by;\n}
            . qq{  error message is [[$err]];\n}
            . qq{  source code is [[$sort_func_perl]].}
    }
    return $sort_func;
}

###########################################################################

sub limit {
    my ($topic, $ord_func, $min_rank, $max_rank) = @_;

    $topic->_assert_valid_func_arg( 'limit', '$ord_func', $ord_func );

    $topic->_assert_valid_nnint_arg( 'limit', '$min_rank', $min_rank );
    $topic->_assert_valid_nnint_arg( 'limit', '$max_rank', $max_rank );
    confess q{limit(): The $max_rank arg can't be less than the $min_rank.}
        if $max_rank < $min_rank;

    if ($topic->is_empty()) {
        return $topic;
    }

    if (!$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $topic_b = $topic->_body();

    my $ext_topic_tuples = [];
    my $topic_tuples_by_ext_tt_ref = {};

    for my $topic_t_refaddr (CORE::keys %{$topic_b}) {
        my $topic_t = $topic_b->{$topic_t_refaddr};
        my $ext_topic_t = $topic->_export_nfmt_tuple( $topic_t );
        push @{$ext_topic_tuples}, $ext_topic_t;
        $topic_tuples_by_ext_tt_ref->{refaddr $ext_topic_t}
            = $topic_t_refaddr;
    }

    my $sorted_ext_topic_tuples = [sort {
        local $_ = { 'a' => $a, 'b' => $b };
        $ord_func->();
    } @{$ext_topic_tuples}];

    my $result = $topic->empty();

    my $result_b = $result->_body();

    for my $ext_topic_t
            (@{$sorted_ext_topic_tuples}[$min_rank..$max_rank]) {
        my $topic_t_refaddr
            = $topic_tuples_by_ext_tt_ref->{refaddr $ext_topic_t};
        $result_b->{$topic_t_refaddr} = $topic_b->{$topic_t_refaddr};
    }

    return $result;
}

###########################################################################

sub limit_by_attr_names {
    my ($topic, $order_by, $min_rank, $max_rank) = @_;

    $order_by = $topic->_normalize_order_by_arg(
        'limit_by_attr_names', '$order_by', $order_by );

    $topic->_assert_valid_nnint_arg(
        'limit_by_attr_names', '$min_rank', $min_rank );
    $topic->_assert_valid_nnint_arg(
        'limit_by_attr_names', '$max_rank', $max_rank );
    confess q{limit_by_attr_names():}
            . q{ The $max_rank arg can't be less than the $min_rank.}
        if $max_rank < $min_rank;

    if ($topic->is_empty()) {
        return $topic;
    }

    my $sort_func = $topic->_sort_func_from_order_by( $order_by );

    if (!$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->empty();

    my $result_b = $result->_body();

    for my $topic_t (@{$sort_func->( $topic )}[$min_rank..$max_rank]) {
        $result_b->{refaddr $topic_t} = $topic_t;
    }

    return $result;
}

###########################################################################

sub substitution {
    my ($topic, $attr_names, $func, $allow_dup_tuples) = @_;
    (my $subst_h, $attr_names)
        = $topic->_atnms_hr_from_assert_valid_subst_args(
        'substitution', '$attr_names', '$func', $attr_names, $func );
    return $topic->_substitution(
        'substitution', '$attr_names', '$func',
        $attr_names, $func, $subst_h, $allow_dup_tuples );
}

sub _atnms_hr_from_assert_valid_subst_args {
    my ($topic, $rtn_nm, $arg_nm_atnms, $arg_nm_func, $atnms, $func) = @_;

    (my $subst_h, $atnms) = $topic->_atnms_hr_from_assert_valid_atnms_arg(
        $rtn_nm, $arg_nm_atnms, $atnms );
    my (undef, undef, $subst_only)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $subst_h );
    confess qq{$rtn_nm(): Bad $arg_nm_atnms arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if @{$subst_only} > 0;

    $topic->_assert_valid_func_arg( $rtn_nm, $arg_nm_func, $func );

    return ($subst_h, $atnms);
}

sub _substitution {
    my ($topic, $rtn_nm, $arg_nm_attrs, $arg_nm_func, $attrs, $func,
        $subst_h, $allow_dup_tuples) = @_;

    if ($topic->is_empty()) {
        return $topic;
    }
    if (@{$attrs} == 0) {
        # Substitution in zero attrs of input yields the input.
        return $topic;
    }

    if (!$allow_dup_tuples and !$topic->_is_known_dup_free()) {
        $topic->_dup_free_want_index_over_all_attrs();
    }

    my $result = $topic->empty();

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $subst_t;
        {
            local $_ = $topic->_export_nfmt_tuple( $topic_t );
            $subst_t = $func->();
        }
        $topic->_assert_valid_tuple_result_of_func_arg(
            $rtn_nm, $arg_nm_func, $arg_nm_attrs, $subst_t, $subst_h );
        $subst_t = $topic->_import_nfmt_tuple( $subst_t );
        my $result_t = {%{$topic_t}, %{$subst_t}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub static_subst {
    my ($topic, $attrs) = @_;
    $topic->_assert_valid_static_subst_args(
        'static_subst', '$attrs', $attrs );
    return $topic->_static_subst( $attrs );
}

sub _assert_valid_static_subst_args {
    my ($topic, $rtn_nm, $arg_nm_attrs, $attrs) = @_;

    confess qq{$rtn_nm(): Bad $arg_nm_attrs arg; it isn't a hash-ref.}
        if ref $attrs ne 'HASH';

    my (undef, undef, $subst_only)
        = $topic->_ptn_conj_and_disj( $topic->_heading(), $attrs );
    confess qq{$rtn_nm(): Bad $arg_nm_attrs arg; that attr list}
            . q{ isn't a subset of the invocant's heading.}
        if @{$subst_only} > 0;

    confess qq{$rtn_nm(): Bad $arg_nm_attrs arg;}
            . q{ it is a hash-ref, and there exist circular refs}
            . q{ between itself or its tuple-valued components.}
        if $topic->_tuple_arg_has_circular_refs( $attrs );

    return;
}

sub _static_subst {
    my ($topic, $attrs) = @_;

    if ($topic->is_empty()) {
        return $topic;
    }
    if ((scalar CORE::keys %{$attrs}) == 0) {
        # Substitution in zero attrs of input yields the input.
        return $topic;
    }

    $attrs = $topic->_import_nfmt_tuple( $attrs );

    my $result = $topic->empty();

    my $result_b = $result->_body();

    for my $topic_t (values %{$topic->_body()}) {
        my $result_t = {%{$topic_t}, %{$attrs}};
        $result_b->{refaddr $result_t} = $result_t;
    }

    return $result;
}

###########################################################################

sub subst_in_restr {
    my ($topic, $restr_func, $subst_attr_names, $subst_func,
        $allow_dup_tuples) = @_;

    $topic->_assert_valid_func_arg(
        'subst_in_restr', '$restr_func', $restr_func );

    (my $subst_h, $subst_attr_names) = $topic
        ->_atnms_hr_from_assert_valid_subst_args( 'subst_in_restr',
            '$subst_attr_names', '$subst_func',
            $subst_attr_names, $subst_func );

    my ($topic_to_subst, $topic_no_subst)
        = @{$topic->_restr_and_cmpl( $restr_func, $allow_dup_tuples )};

    return $topic_to_subst
        ->_substitution( 'subst_in_restr', '$subst_attr_names',
            '$subst_func', $subst_attr_names, $subst_func, $subst_h,
            $allow_dup_tuples )
        ->_union( [$topic_no_subst] );
}

###########################################################################

sub static_subst_in_restr {
    my ($topic, $restr_func, $subst, $allow_dup_tuples) = @_;

    $topic->_assert_valid_func_arg(
        'static_subst_in_restr', '$restr_func', $restr_func );

    $topic->_assert_valid_static_subst_args(
        'static_subst_in_restr', '$subst', $subst );

    my ($topic_to_subst, $topic_no_subst)
        = @{$topic->_restr_and_cmpl( $restr_func, $allow_dup_tuples )};

    return $topic_to_subst
        ->_static_subst( $subst )
        ->_union( [$topic_no_subst] );
}

###########################################################################

sub subst_in_semijoin {
    my ($topic, $restr, $subst_attr_names, $subst_func, $allow_dup_tuples)
        = @_;

    $restr = $topic->_normalize_relation_arg(
        'subst_in_semijoin', '$restr', $restr );

    (my $subst_h, $subst_attr_names) = $topic
        ->_atnms_hr_from_assert_valid_subst_args( 'subst_in_semijoin',
            '$subst_attr_names', '$subst_func',
            $subst_attr_names, $subst_func );

    my ($topic_to_subst, $topic_no_subst)
        = @{$topic->_semijoin_and_diff( $restr )};

    return $topic_to_subst
        ->_substitution( 'subst_in_semijoin', '$subst_attr_names',
            '$subst_func', $subst_attr_names, $subst_func, $subst_h,
            $allow_dup_tuples )
        ->_union( [$topic_no_subst] );
}

###########################################################################

sub static_subst_in_semijoin {
    my ($topic, $restr, $subst) = @_;

    $restr = $topic->_normalize_relation_arg(
        'static_subst_in_semijoin', '$restr', $restr );

    $topic->_assert_valid_static_subst_args(
        'static_subst_in_semijoin', '$subst', $subst );

    my ($topic_to_subst, $topic_no_subst)
        = @{$topic->_semijoin_and_diff( $restr )};

    return $topic_to_subst
        ->_static_subst( $subst )
        ->_union( [$topic_no_subst] );
}

###########################################################################

sub outer_join_with_group {
    my ($primary, $secondary, $group_attr) = @_;

    $secondary = $primary->_normalize_relation_arg(
        'outer_join_with_group', '$secondary', $secondary );
    $primary->_assert_valid_atnm_arg(
        'outer_join_with_group', '$group_attr', $group_attr );

    my $primary_h = $primary->_heading();

    confess q{outer_join_with_group(): Bad $group_attr arg;}
            . q{ that name for a new attr to add}
            . q{ to $primary, consisting of grouped $secondary-only attrs,}
            . q{ duplicates an attr of $primary (not being grouped).}
        if exists $primary_h->{$group_attr};

    # TODO: inline+merge what join/group/etc do for better performance.

    my ($both, $primary_only, $inner) = $primary->_ptn_conj_and_disj(
            $primary_h, $secondary->_heading() );
    my $inner_h = {CORE::map { $_ => undef } @{$inner}};

    my ($pri_matched, $pri_nonmatched)
        = @{$primary->_semijoin_and_diff( $secondary )};

    my $result_matched = $pri_matched
        ->_join( [$secondary] )
        ->_group( $group_attr, $inner, [CORE::keys %{$primary_h}],
            $inner_h );

    my $result_nonmatched = $pri_nonmatched
        ->_static_exten( {$group_attr => $primary->_new( $inner )} );

    my $result = $result_matched->_union( [$result_nonmatched] );

    if ($primary->_is_known_dup_free()
            and $secondary->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub outer_join_with_undefs {
    my ($primary, $secondary) = @_;

    $secondary = $primary->_normalize_relation_arg(
        'outer_join_with_undefs', '$secondary', $secondary );

    my (undef, undef, $exten_attrs) = $primary->_ptn_conj_and_disj(
        $primary->_heading(), $secondary->_heading() );
    my $filler = {CORE::map { $_ => undef } @{$exten_attrs}};

    my ($pri_matched, $pri_nonmatched)
        = @{$primary->_semijoin_and_diff( $secondary )};

    my $result_matched = $pri_matched->_join( [$secondary] );

    my $result_nonmatched = $pri_nonmatched->_static_exten( $filler );

    my $result = $result_matched->_union( [$result_nonmatched] );

    if ($primary->_is_known_dup_free()
            and $secondary->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub outer_join_with_static_exten {
    my ($primary, $secondary, $filler) = @_;

    $secondary = $primary->_normalize_relation_arg(
        'outer_join_with_static_exten', '$secondary', $secondary );

    confess q{outer_join_with_static_exten(): Bad $filler arg;}
            . q{ it isn't a hash-ref.}
        if ref $filler ne 'HASH';
    confess q{outer_join_with_static_exten(): Bad $filler arg;}
            . q{ it is a hash-ref, and there exist circular refs}
            . q{ between itself or its tuple-valued components.}
        if $primary->_tuple_arg_has_circular_refs( $filler );

    my (undef, undef, $exten_attrs) = $primary->_ptn_conj_and_disj(
        $primary->_heading(), $secondary->_heading() );
    my $exten_h = {CORE::map { $_ => undef } @{$exten_attrs}};

    confess q{outer_join_with_static_exten(): Bad $filler arg elem;}
            . q{ it doesn't have exactly the}
            . q{ same set of attr names as the sub-heading of $secondary}
            . q{ that doesn't overlap with the heading of $primary.}
        if !$primary->_is_identical_hkeys( $exten_h, $filler );

    my ($pri_matched, $pri_nonmatched)
        = @{$primary->_semijoin_and_diff( $secondary )};

    my $result_matched = $pri_matched->_join( [$secondary] );

    my $result_nonmatched = $pri_nonmatched->_static_exten( $filler );

    my $result = $result_matched->_union( [$result_nonmatched] );

    if ($primary->_is_known_dup_free()
            and $secondary->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

sub outer_join_with_exten {
    my ($primary, $secondary, $exten_func, $allow_dup_tuples) = @_;

    $secondary = $primary->_normalize_relation_arg(
        'outer_join_with_exten', '$secondary', $secondary );
    $primary->_assert_valid_func_arg(
        'outer_join_with_exten', '$exten_func', $exten_func );

    my (undef, undef, $exten_attrs) = $primary->_ptn_conj_and_disj(
        $primary->_heading(), $secondary->_heading() );
    my $exten_h = {CORE::map { $_ => undef } @{$exten_attrs}};

    my ($pri_matched, $pri_nonmatched)
        = @{$primary->_semijoin_and_diff( $secondary )};

    my $result_matched = $pri_matched->_join( [$secondary] );

    # Note: if '_extension' dies due to what $exten_func did it would
    # state the error is reported by 'extension' and with some wrong
    # details; todo fix later; on correct it won't affect users though.
    my $result_nonmatched = $pri_nonmatched->_extension(
        $exten_attrs, $exten_func, $exten_h, $allow_dup_tuples );

    my $result = $result_matched->_union( [$result_nonmatched] );

    if ($primary->_is_known_dup_free()
            and $secondary->_is_known_dup_free()) {
        $result->_is_known_dup_free( 1 );
    }

    return $result;
}

###########################################################################

} # class Set::Relation::V2

###########################################################################
###########################################################################

1;