[PATCH 0/7] www: avoid recursion for thread walking

[PATCH 0/7] www: avoid recursion for thread walking

[Eric Wong]

Deep message threads can cause problems for perl since stack
seems to be much more expensive than arrays.  Switch to a
non-recursive thread walking design and commonalize some
common idioms, too.

Eric Wong (7):
      view: remove upfx parameter from thread skeleton dump
      view: remove dst parameter from thread skeleton dump
      view: remove recursion from thread skeleton dump
      view: remove recursion from expanded thread view
      searchview: remove recursion from thread view
      view: avoid recursion in topic index
      view: common thread walking interface

 lib/PublicInbox/SearchView.pm |  9 ++------
 lib/PublicInbox/View.pm       | 53 +++++++++++++++++++++----------------------
 2 files changed, 28 insertions(+), 34 deletions(-)

[PATCH 1/7] view: remove upfx parameter from thread skeleton dump

[Eric Wong]

This makes the string creation somewhat simpler hopefully
makes the code easier-to-reason with.
---
 lib/PublicInbox/View.pm | 17 +++++++++--------
 1 file changed, 9 insertions(+), 8 deletions(-)

diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index dfae44f..9095c50 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -383,9 +383,10 @@ sub thread_skel {
 		cur => $mid,
 		prev_attr => '',
 		prev_level => 0,
+		upfx => "$tpfx../",
 	};
 	for (thread_results(load_results($sres))->rootset) {
-		skel_dump($dst, $state, $tpfx, $_, 0);
+		skel_dump($dst, $state, $_, 0);
 	}
 	$ctx->{next_msg} = $state->{next_msg};
 	$ctx->{parent_msg} = $parent;
@@ -663,7 +664,7 @@ sub _msg_date {
 sub fmt_ts { POSIX::strftime('%Y-%m-%d %k:%M', gmtime($_[0])) }
 
 sub _skel_header {
-	my ($dst, $state, $upfx, $hdr, $level) = @_;
+	my ($dst, $state, $hdr, $level) = @_;
 
 	my $cur = $state->{cur};
 	my $mid = mid_clean($hdr->header_raw('Message-ID'));
@@ -705,18 +706,18 @@ sub _skel_header {
 		$s = $s->as_html;
 	}
 	my $m = PublicInbox::Hval->new_msgid($mid);
-	$m = $upfx . '../' . $m->as_href . '/';
+	$m = $state->{upfx} . $m->as_href . '/';
 	$$dst .= "$pfx<a\nhref=\"$m\">";
 	$$dst .= defined($s) ? "$s</a> $f\n" : "$f</a>\n";
 }
 
 sub skel_dump {
-	my ($dst, $state, $upfx, $node, $level) = @_;
+	my ($dst, $state, $node, $level) = @_;
 	return unless $node;
 	if (my $mime = $node->message) {
 		my $hdr = $mime->header_obj;
 		my $mid = mid_clean($hdr->header_raw('Message-ID'));
-		_skel_header($dst, $state, $upfx, $hdr, $level);
+		_skel_header($dst, $state, $hdr, $level);
 	} else {
 		my $mid = $node->messageid;
 		if ($mid eq 'subject dummy') {
@@ -725,13 +726,13 @@ sub skel_dump {
 			$$dst .= '     [not found] ';
 			$$dst .= indent_for($level) . th_pfx($level);
 			$mid = PublicInbox::Hval->new_msgid($mid);
-			my $href = "$upfx../" . $mid->as_href . '/';
+			my $href = $state->{upfx} . $mid->as_href . '/';
 			my $html = $mid->as_html;
 			$$dst .= qq{&lt;<a\nhref="$href">$html</a>&gt;\n};
 		}
 	}
-	skel_dump($dst, $state, $upfx, $node->child, $level+1);
-	skel_dump($dst, $state, $upfx, $node->next, $level);
+	skel_dump($dst, $state, $node->child, $level+1);
+	skel_dump($dst, $state, $node->next, $level);
 }
 
 sub sort_ts {

[PATCH 2/7] view: remove dst parameter from thread skeleton dump

[Eric Wong]

We can stuff this into the state hash to reduce stack size and
hopefully improve readability.
---
 lib/PublicInbox/View.pm | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index 9095c50..a1b45e9 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -384,9 +384,10 @@ sub thread_skel {
 		prev_attr => '',
 		prev_level => 0,
 		upfx => "$tpfx../",
+		dst => $dst,
 	};
 	for (thread_results(load_results($sres))->rootset) {
-		skel_dump($dst, $state, $_, 0);
+		skel_dump($state, $_, 0);
 	}
 	$ctx->{next_msg} = $state->{next_msg};
 	$ctx->{parent_msg} = $parent;
@@ -664,8 +665,9 @@ sub _msg_date {
 sub fmt_ts { POSIX::strftime('%Y-%m-%d %k:%M', gmtime($_[0])) }
 
 sub _skel_header {
-	my ($dst, $state, $hdr, $level) = @_;
+	my ($state, $hdr, $level) = @_;
 
+	my $dst = $state->{dst};
 	my $cur = $state->{cur};
 	my $mid = mid_clean($hdr->header_raw('Message-ID'));
 	my $f = ascii_html($hdr->header('X-PI-From'));
@@ -712,14 +714,15 @@ sub _skel_header {
 }
 
 sub skel_dump {
-	my ($dst, $state, $node, $level) = @_;
+	my ($state, $node, $level) = @_;
 	return unless $node;
 	if (my $mime = $node->message) {
 		my $hdr = $mime->header_obj;
 		my $mid = mid_clean($hdr->header_raw('Message-ID'));
-		_skel_header($dst, $state, $hdr, $level);
+		_skel_header($state, $hdr, $level);
 	} else {
 		my $mid = $node->messageid;
+		my $dst = $state->{dst};
 		if ($mid eq 'subject dummy') {
 			$$dst .= "\t[no common parent]\n";
 		} else {
@@ -731,8 +734,8 @@ sub skel_dump {
 			$$dst .= qq{&lt;<a\nhref="$href">$html</a>&gt;\n};
 		}
 	}
-	skel_dump($dst, $state, $node->child, $level+1);
-	skel_dump($dst, $state, $node->next, $level);
+	skel_dump($state, $node->child, $level+1);
+	skel_dump($state, $node->next, $level);
 }
 
 sub sort_ts {

[PATCH 3/7] view: remove recursion from thread skeleton dump

[Eric Wong]

This should help prevent OOM errors from arbitrarily
deep threads and will make our streaming interface
easier-to-implement.
---
 lib/PublicInbox/View.pm | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index a1b45e9..e09fbd5 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -386,8 +386,12 @@ sub thread_skel {
 		upfx => "$tpfx../",
 		dst => $dst,
 	};
-	for (thread_results(load_results($sres))->rootset) {
-		skel_dump($state, $_, 0);
+	my @q = map { (0, $_) } thread_results(load_results($sres))->rootset;
+	while (@q) {
+		my $level = shift @q;
+		my $node = shift @q or next;
+		skel_dump($state, $level, $node);
+		unshift @q, $level+1, $node->child, $level, $node->next;
 	}
 	$ctx->{next_msg} = $state->{next_msg};
 	$ctx->{parent_msg} = $parent;
@@ -714,8 +718,7 @@ sub _skel_header {
 }
 
 sub skel_dump {
-	my ($state, $node, $level) = @_;
-	return unless $node;
+	my ($state, $level, $node) = @_;
 	if (my $mime = $node->message) {
 		my $hdr = $mime->header_obj;
 		my $mid = mid_clean($hdr->header_raw('Message-ID'));
@@ -734,8 +737,6 @@ sub skel_dump {
 			$$dst .= qq{&lt;<a\nhref="$href">$html</a>&gt;\n};
 		}
 	}
-	skel_dump($state, $node->child, $level+1);
-	skel_dump($state, $node->next, $level);
 }
 
 sub sort_ts {

[PATCH 4/7] view: remove recursion from expanded thread view

[Eric Wong]

This should let us generate HTML for arbitrarily deep
threads without blowing the stack.

How it renders on the client side is another matter...
---
 lib/PublicInbox/View.pm | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index e09fbd5..bc4a443 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -177,8 +177,13 @@ sub emit_thread_html {
 		pre_anchor_entry($seen, $_) for (@$msgs);
 		__thread_entry($state, $_, 0) for (@$msgs);
 	} else {
-		my $th = thread_results($msgs);
-		thread_entry($state, $_, 0) for $th->rootset;
+		my @q = map { (0, $_) } thread_results($msgs)->rootset;
+		while (@q) {
+			my $level = shift @q;
+			my $node = shift @q or next;
+			thread_entry($state, $level, $node);
+			unshift @q, $level+1, $node->child, $level, $node->next;
+		}
 		if (my $max = $state->{cur_level}) {
 			$state->{fh}->write(
 				('</ul></li>' x ($max - 1)) . '</ul>');
@@ -618,8 +623,7 @@ sub __ghost_prepare {
 }
 
 sub thread_entry {
-	my ($state, $node, $level) = @_;
-	return unless $node;
+	my ($state, $level, $node) = @_;
 	if (my $mime = $node->message) {
 		unless (__thread_entry($state, $mime, $level)) {
 			__ghost_prepare($state, $node, $level);
@@ -627,9 +631,6 @@ sub thread_entry {
 	} else {
 		__ghost_prepare($state, $node, $level);
 	}
-
-	thread_entry($state, $node->child, $level + 1);
-	thread_entry($state, $node->next, $level);
 }
 
 sub load_results {

[PATCH 5/7] searchview: remove recursion from thread view

[Eric Wong]

As before, recursion can cause problems sooner than unshifting
objects into the head of a queue.
---
 lib/PublicInbox/SearchView.pm | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/lib/PublicInbox/SearchView.pm b/lib/PublicInbox/SearchView.pm
index 6f67a37..ba25827 100644
--- a/lib/PublicInbox/SearchView.pm
+++ b/lib/PublicInbox/SearchView.pm
@@ -151,7 +151,6 @@ sub tdump {
 		$m;
 	} ($mset->items);
 
-	my @rootset;
 	my $th = PublicInbox::Thread->new(@m);
 	$th->thread;
 	if ($q->{r}) { # order by relevance
@@ -164,7 +163,6 @@ sub tdump {
 	} else { # order by time (default for threaded view)
 		$th->order(*PublicInbox::View::sort_ts);
 	}
-	@rootset = $th->rootset;
 	my $state = {
 		ctx => $ctx,
 		anchor_idx => 0,
@@ -174,7 +172,13 @@ sub tdump {
 		fh => $fh,
 	};
 	$ctx->{searchview} = 1;
-	tdump_ent($state, $_, 0) for @rootset;
+	my @q = map { (0, $_) } $th->rootset;
+	while (@q) {
+		my $level = shift @q;
+		my $node = shift @q or next;
+		tdump_ent($state, $level, $node);
+		unshift @q, $level+1, $node->child, $level, $node->next;
+	}
 	PublicInbox::View::thread_adj_level($state, 0);
 
 	$fh->write(search_nav_bot($mset, $q). "\n\n" .
@@ -184,8 +188,7 @@ sub tdump {
 }
 
 sub tdump_ent {
-	my ($state, $node, $level) = @_;
-	return unless $node;
+	my ($state, $level, $node) = @_;
 	my $mime = $node->message;
 
 	if ($mime) {
@@ -202,8 +205,6 @@ sub tdump_ent {
 		my $mid = $node->messageid;
 		PublicInbox::View::ghost_flush($state, '', $mid, $level);
 	}
-	tdump_ent($state, $node->child, $level + 1);
-	tdump_ent($state, $node->next, $level);
 }
 
 sub foot {

[PATCH 6/7] view: avoid recursion in topic index

[Eric Wong]

Recursion can cause problems, so do our best to avoid it
even in the topic index.
---
 lib/PublicInbox/View.pm | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index bc4a443..8075e4a 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -757,8 +757,7 @@ sub _tryload_ghost ($$) {
 # accumulate recent topics if search is supported
 # returns 1 if done, undef if not
 sub add_topic {
-	my ($state, $node, $level) = @_;
-	return unless $node;
+	my ($state, $level, $node) = @_;
 	my $child_adjust = 1;
 	my $srch = $state->{srch};
 	my $x = $node->message || _tryload_ghost($srch, $node);
@@ -784,9 +783,6 @@ sub add_topic {
 		# ghost message, do not bump level
 		$child_adjust = 0;
 	}
-
-	add_topic($state, $node->child, $level + $child_adjust);
-	add_topic($state, $node->next, $level);
 }
 
 sub emit_topics {
@@ -850,9 +846,13 @@ sub emit_index_topics {
 	while (scalar @{$state->{order}} < $max) {
 		my $sres = $state->{srch}->query('', \%opts);
 		my $nr = scalar @{$sres->{msgs}} or last;
-
-		for (thread_results(load_results($sres))->rootset) {
-			add_topic($state, $_, 0);
+		$sres = load_results($sres);
+		my @q = map { (0, $_) } thread_results($sres)->rootset;
+		while (@q) {
+			my $level = shift @q;
+			my $node = shift @q or next;
+			add_topic($state, $level, $node);
+			unshift @q, $level+1, $node->child, $level, $node->next;
 		}
 		$opts{offset} += $nr;
 	}

[PATCH 7/7] view: common thread walking interface

[Eric Wong]

Since we have a common pattern, for walking threads,
extract it into a function and reduce the amount of code
we haev.

This will make it easier to switch to an event-driven interface
for getline, too.
---
 lib/PublicInbox/SearchView.pm |  8 +-------
 lib/PublicInbox/View.pm       | 35 ++++++++++++++---------------------
 2 files changed, 15 insertions(+), 28 deletions(-)

diff --git a/lib/PublicInbox/SearchView.pm b/lib/PublicInbox/SearchView.pm
index ba25827..ae875bf 100644
--- a/lib/PublicInbox/SearchView.pm
+++ b/lib/PublicInbox/SearchView.pm
@@ -172,13 +172,7 @@ sub tdump {
 		fh => $fh,
 	};
 	$ctx->{searchview} = 1;
-	my @q = map { (0, $_) } $th->rootset;
-	while (@q) {
-		my $level = shift @q;
-		my $node = shift @q or next;
-		tdump_ent($state, $level, $node);
-		unshift @q, $level+1, $node->child, $level, $node->next;
-	}
+	PublicInbox::View::walk_thread($th, $state, *tdump_ent);
 	PublicInbox::View::thread_adj_level($state, 0);
 
 	$fh->write(search_nav_bot($mset, $q). "\n\n" .
diff --git a/lib/PublicInbox/View.pm b/lib/PublicInbox/View.pm
index 8075e4a..b6fa2a3 100644
--- a/lib/PublicInbox/View.pm
+++ b/lib/PublicInbox/View.pm
@@ -152,6 +152,17 @@ sub thread_html {
 	sub { emit_thread_html($_[0], $ctx, $foot, $srch) }
 }
 
+sub walk_thread {
+	my ($th, $state, $cb) = @_;
+	my @q = map { (0, $_) } $th->rootset;
+	while (@q) {
+		my $level = shift @q;
+		my $node = shift @q or next;
+		$cb->($state, $level, $node);
+		unshift @q, $level+1, $node->child, $level, $node->next;
+	}
+}
+
 # only private functions below.
 
 sub emit_thread_html {
@@ -177,13 +188,7 @@ sub emit_thread_html {
 		pre_anchor_entry($seen, $_) for (@$msgs);
 		__thread_entry($state, $_, 0) for (@$msgs);
 	} else {
-		my @q = map { (0, $_) } thread_results($msgs)->rootset;
-		while (@q) {
-			my $level = shift @q;
-			my $node = shift @q or next;
-			thread_entry($state, $level, $node);
-			unshift @q, $level+1, $node->child, $level, $node->next;
-		}
+		walk_thread(thread_results($msgs), $state, *thread_entry);
 		if (my $max = $state->{cur_level}) {
 			$state->{fh}->write(
 				('</ul></li>' x ($max - 1)) . '</ul>');
@@ -391,13 +396,7 @@ sub thread_skel {
 		upfx => "$tpfx../",
 		dst => $dst,
 	};
-	my @q = map { (0, $_) } thread_results(load_results($sres))->rootset;
-	while (@q) {
-		my $level = shift @q;
-		my $node = shift @q or next;
-		skel_dump($state, $level, $node);
-		unshift @q, $level+1, $node->child, $level, $node->next;
-	}
+	walk_thread(thread_results(load_results($sres)), $state, *skel_dump);
 	$ctx->{next_msg} = $state->{next_msg};
 	$ctx->{parent_msg} = $parent;
 }
@@ -847,13 +846,7 @@ sub emit_index_topics {
 		my $sres = $state->{srch}->query('', \%opts);
 		my $nr = scalar @{$sres->{msgs}} or last;
 		$sres = load_results($sres);
-		my @q = map { (0, $_) } thread_results($sres)->rootset;
-		while (@q) {
-			my $level = shift @q;
-			my $node = shift @q or next;
-			add_topic($state, $level, $node);
-			unshift @q, $level+1, $node->child, $level, $node->next;
-		}
+		walk_thread(thread_results($sres), $state, *add_topic);
 		$opts{offset} += $nr;
 	}