#our $rx_entity_hex   = m{\&([a-z]+);};
our $rx_entity_dec    = m{&\d+;};
our $rx_entity_named  = m{&[a-z]+;};
our $rx_entity        = m{$rx_entity_named|$rx_entity_dec};
our $rx_char_plain    = m{[^<>"&]};

our $rx_char          = m{$rx_char_plain|$rx_entity};
our $rx_text          = m{(?:$rx_char)+};

our $rx_name          = m{\w+};
our $rx_quoted        = m{"$rx_text"};
our $rx_attr          = m{$rx_name=$rx_quoted};
our $rx_open          = m{<$rx_name(?:\s+$rx_attr)*\s*/?>};
our $rx_close         = m{</$rx_name>};


sub find_close {
	my ($self, $i) = @_;
	my $open = $self->{ary}[$i];
	my ($tag) = $open =~ /^<(\w+)/;
	my $rx_close = qr{^</$tag>};
	my $j = $i + 1;
	while (1) {
		my $e = $self->{ary}[$j]
		  or die "closer failed: $open";
		last if $e =~ $rx_close;
		++$j;
	}
	return $j;
}

sub rules_to {
	my ($class, $to) = @_;
	no strict 'refs';
	$class = ref $class || $class;
	return ${"${class}::rules"}{cache}{to}{$to} ||= do {
		my $rules = [];
		my $pkgrules = ${"${class}::rules"};
		if ($pkgrules && $pkgrules->{to}{$to}) {
			push @$rules, @{$pkgrules->{to}{$to}}
		}
		if (defined @{"${class}::ISA"}) {
			for my $base (@{"${class}::ISA"}) {
				push @$rules, @{$base->rules_to($to)};
			}
		}
#		$rules = [sort {$a->[3] <=> $b->[3]} @$rules];
		$rules;
	};
}

package Object::RulePath;
use base 'Object';

# attrs:
# node => current node
# rule => [from, to, op, cost] or undef
# rest => rest of the path, or undef
# cost => total cost for this path including this rule
# got  => count of needed "from" nodes that have a value

sub new {
	my ($pkg, $self) = @_;
	$self = $pkg->SUPER::new($self);
	$self->{got} //= 0;
	$self->{heap} = undef;
	return $self;
}

sub cmp {
	my ($self, $other) = @_;
	return $self->{cost} <=> $other->{cost};
}

sub find_path_to {
	my ($self, $to) = @_;
#	if (defined $self->{$to}) {
#		return [];
#	}
	my $heap = Heap::Fibonacci->new;
	my $path = Object::RulePath->new({
		node => $to,
		cost => 0
	  });
	my %seen;
	$heap->add($path);
	while (my $path1 = $heap->extract_top) {
#		print D $path1;
		my $to = $path1->{node};
		$seen{$to} = 1;
		if (defined $self->{$to}) {
			warn "defined: $to = $self->{$to}\n";
		}
		my $rules_to = $self->rules_to($to);
		for my $rule (@$rules_to) {
			for my $from (@{$rule->[0]}) {
				my $path = Object::RulePath->new({
					node => $from,
					rule => $rule,
					rest => $path1,
					cost => $path1->{cost} + $rule->[3]
				  });
				$heap->add($path);
			}
		}
	}
}