Rewrote how the balance command displays accounts

The previous method bent over backwards to try and avoid multiple passes
through the account tree, but the result was a horribly complicated mess
that never ceased to dredge up obscure bugs.  The new scheme is a very,
very simple two-pass algorithm, with multiple subpasses during the
second pass for refining the output based on the report options.

5 files changed, 133 insertions, 120 deletions

diff --git a/src/account.cc b/src/account.cc
index 23ce2e68..b463968b 100644
--- a/src/account.cc
+++ b/src/account.cc
@@ -127,22 +127,18 @@ string account_t::fullname() const
 
 string account_t::partial_name() const
 {
-  string name;
+  string pname = name;
 
-  for (const account_t * acct = this;
+  for (const account_t * acct = parent;
        acct && acct->parent;
        acct = acct->parent) {
-    if (acct->has_xdata() &&
-	acct->xdata().has_flags(ACCOUNT_EXT_DISPLAYED))
+    std::size_t count = acct->children_with_flags(ACCOUNT_EXT_MATCHING);
+    assert(count > 0);
+    if (count > 1)
       break;
-
-    if (name.empty())
-      name = acct->name;
-    else
-      name = acct->name + ":" + name;
+    pname = acct->name + ":" + pname;
   }
-
-  return name;
+  return pname;
 }
 
 std::ostream& operator<<(std::ostream& out, const account_t& account)
@@ -193,13 +189,20 @@ namespace {
 
   value_t get_depth_spacer(account_t& account)
   {
+    std::size_t depth = 0;
+    for (const account_t * acct = account.parent;
+	 acct && acct->parent;
+	 acct = acct->parent) {
+      std::size_t count = acct->children_with_flags(ACCOUNT_EXT_MATCHING);
+      assert(count > 0);
+      if (count > 1)
+	depth++;
+    }
+
     std::ostringstream out;
-    for (account_t * acct = &account;
-	 acct;
-	 acct = acct->parent)
-      if (acct->has_xdata() &&
-	  acct->xdata().has_flags(ACCOUNT_EXT_DISPLAYED))
-	out << "  ";
+    for (std::size_t i = 0; i < depth; i++)
+      out << "  ";
+
     return string_value(out.str());
   }
 
@@ -274,6 +277,25 @@ bool account_t::valid() const
   return true;
 }
 
+std::size_t account_t::children_with_flags(xdata_t::flags_t flags) const
+{
+  std::size_t count = 0;
+  bool        grandchildren_visited = false;
+
+  foreach (const accounts_map::value_type& pair, accounts) {
+    if (pair.second->has_flags(flags) ||
+	pair.second->children_with_flags(flags))
+      count++;
+  }
+
+  // Although no immediately children were visited, if any progeny at all were
+  // visited, it counts as one.
+  if (count == 0 && grandchildren_visited)
+    count = 1;
+
+  return count;
+}
+
 void account_t::calculate_sums(expr_t& amount_expr)
 {
   xdata_t& xd(xdata());
diff --git a/src/account.h b/src/account.h
index dfa6eba5..bd0210db 100644
--- a/src/account.h
+++ b/src/account.h
@@ -122,19 +122,18 @@ class account_t : public scope_t
 #define ACCOUNT_EXT_SORT_CALC	     0x02
 #define ACCOUNT_EXT_HAS_NON_VIRTUALS 0x04
 #define ACCOUNT_EXT_HAS_UNB_VIRTUALS 0x08
+#define ACCOUNT_EXT_VISITED          0x10
+#define ACCOUNT_EXT_MATCHING         0x20
 
     value_t	  value;
     value_t	  total;
     std::size_t   count;	// xacts counted toward amount
     std::size_t   total_count;	// xacts counted toward total
     std::size_t   virtuals;
-    uint_least8_t dflags;
 
     std::list<sort_value_t> sort_values;
 
-    xdata_t()
-      : supports_flags<>(), count(0), total_count(0),
-	virtuals(0), dflags(0)
+    xdata_t() : supports_flags<>(), count(0), total_count(0), virtuals(0)
     {
       TRACE_CTOR(account_t::xdata_t, "");
     }
@@ -145,7 +144,6 @@ class account_t : public scope_t
 	count(other.count),
 	total_count(other.total_count),
 	virtuals(other.virtuals),
-	dflags(other.dflags),
 	sort_values(other.sort_values)
     {
       TRACE_CTOR(account_t::xdata_t, "copy");
@@ -178,6 +176,11 @@ class account_t : public scope_t
     return *xdata_;
   }
 
+  bool has_flags(xdata_t::flags_t flags) const {
+    return xdata_ && xdata_->has_flags(flags);
+  }
+  std::size_t children_with_flags(xdata_t::flags_t flags) const;
+
   void calculate_sums(expr_t& amount_expr);
 };
 
diff --git a/src/filters.cc b/src/filters.cc
index 1deffffb..22231d18 100644
--- a/src/filters.cc
+++ b/src/filters.cc
@@ -108,6 +108,10 @@ void set_account_value::operator()(xact_t& xact)
   if (xact.has_flags(XACT_VIRTUAL))
     xdata.virtuals++;
 
+  DEBUG("account.display",
+	"Visiting account: " << xact.account->fullname());
+  xact.account->xdata().add_flags(ACCOUNT_EXT_VISITED);
+
   item_handler<xact_t>::operator()(xact);
 }
 
diff --git a/src/output.cc b/src/output.cc
index cd28e58c..35633889 100644
--- a/src/output.cc
+++ b/src/output.cc
@@ -210,23 +210,54 @@ void format_entries::operator()(xact_t& xact)
   last_entry = xact.entry;
 }
 
-bool format_accounts::should_display(account_t& account)
+void format_accounts::post_accounts(account_t& account)
 {
-  if (! disp_pred.predicate && report.HANDLED(display_))
-    disp_pred.predicate.parse(report.HANDLER(display_).str());
+  // Don't ever print the top-most account
+  if (account.parent) {
+    bind_scope_t bound_scope(report, account);
+    bool	 format_account = false;
+
+    DEBUG("account.display", "Should we display " << account.fullname());
+
+    if (account.has_flags(ACCOUNT_EXT_MATCHING) ||
+	account.children_with_flags(ACCOUNT_EXT_MATCHING) > 1) {
+      DEBUG("account.display", "  Yes, because it matched");
+      format_account = true;
+    }
+    else if (account.children_with_flags(ACCOUNT_EXT_VISITED) &&
+	     ! account.children_with_flags(ACCOUNT_EXT_MATCHING)) {
+      DEBUG("account.display",
+	    "  Maybe, because it has visited, but no matching, children");
+      if (disp_pred(bound_scope)) {
+	DEBUG("account.display",
+	      "    And yes, because it matches the display predicate");
+	format_account = true;
+      } else {
+	DEBUG("account.display",
+	      "    And no, because it didn't match the display predicate");
+      }
+    }
+    else {
+      DEBUG("account.display",
+	    "  No, neither it nor its children were eligible for display");
+    }
 
-  bind_scope_t bound_scope(report, account);
-  return disp_pred(bound_scope);
+    if (format_account)
+      format.format(report.output_stream, bound_scope);
+  }
+
+  foreach (accounts_map::value_type pair, account.accounts)
+    post_accounts(*pair.second);
 }
 
 void format_accounts::flush()
 {
   std::ostream& out(report.output_stream);
 
+  post_accounts(*report.session.master.get());
+
   if (print_final_total) {
-    assert(out);
     assert(report.session.master->has_xdata());
-
     account_t::xdata_t& xdata(report.session.master->xdata());
 
     if (! report.HANDLED(collapse) && xdata.total) {
@@ -242,71 +273,23 @@ void format_accounts::flush()
 
 void format_accounts::operator()(account_t& account)
 {
-  // Never display the top-most account (the "root", or master, account)
-  if (account.parent && display_account(account)) {
-    bind_scope_t bound_scope(report, account);
-    format.format(report.output_stream, bound_scope);
-    account.xdata().add_flags(ACCOUNT_EXT_DISPLAYED);
-  }
-}
+  DEBUG("account.display",
+	"Proposing to format account: " << account.fullname());
 
-bool format_accounts::disp_subaccounts_p(account_t&   account,
-					 account_t *& to_show)
-{
-  bool	      display  = false;
-  std::size_t counted  = 0;
-  bool        matches  = should_display(account);
-  bool        computed = false;
-  value_t     acct_total;
-  value_t     result;
-
-  to_show = NULL;
-
-  bind_scope_t account_scope(report, account);
-
-  foreach (accounts_map::value_type pair, account.accounts) {
-    if (! should_display(*pair.second))
-      continue;
-
-    bind_scope_t bound_scope(report, *pair.second);
-    call_scope_t args(bound_scope);
-    result = report.fn_total_expr(args);
-    if (! computed) {
-      call_scope_t args(account_scope);
-      acct_total = report.fn_total_expr(args);
-      computed = true;
-    }
+  if (account.has_flags(ACCOUNT_EXT_VISITED)) {
+    DEBUG("account.display",
+	  "  Account or its children visited by sum_all_accounts");
 
-    if ((result != acct_total) || counted > 0) {
-      display = matches;
-      break;
+    bind_scope_t bound_scope(report, account);
+    if (disp_pred(bound_scope)) {
+      DEBUG("account.display",
+	    "  And the account matched the display predicate");
+      account.xdata().add_flags(ACCOUNT_EXT_MATCHING);
+    } else {
+      DEBUG("account.display",
+	    "  But it did not match the display predicate");
     }
-    to_show = pair.second;
-    counted++;
   }
-
-  return display;
-}
-
-bool format_accounts::display_account(account_t& account)
-{
-  // Never display an account that has already been displayed.
-  if (account.has_xdata() &&
-      account.xdata().has_flags(ACCOUNT_EXT_DISPLAYED))
-    return false;
-
-  // At this point, one of two possibilities exists: the account is a
-  // leaf which matches the predicate restrictions; or it is a parent
-  // and two or more children must be subtotaled; or it is a parent
-  // and its child has been hidden by the predicate.  So first,
-  // determine if it is a parent that must be displayed regardless of
-  // the predicate.
-
-  account_t * account_to_show = NULL;
-  if (disp_subaccounts_p(account, account_to_show))
-    return true;
-
-  return ! account_to_show && should_display(account);
 }
 
 format_equity::format_equity(report_t& _report, const string& _format)
@@ -358,35 +341,33 @@ void format_equity::flush()
   out.flush();
 }
 
-void format_equity::operator()(account_t& account)
+void format_equity::post_accounts(account_t& account)
 {
   std::ostream& out(report.output_stream);
 
-  if (display_account(account)) {
-    if (account.has_xdata()) {
-      value_t val = account.xdata().value;
-
-      if (val.type() >= value_t::BALANCE) {
-	const balance_t * bal;
-	if (val.is_type(value_t::BALANCE))
-	  bal = &(val.as_balance());
-	else
-	  assert(false);
-
-	foreach (balance_t::amounts_map::value_type pair, bal->amounts) {
-	  account.xdata().value = pair.second;
-	  bind_scope_t bound_scope(report, account);
-	  next_lines_format.format(out, bound_scope);
-	}
-	account.xdata().value = val;
-      } else {
-	bind_scope_t bound_scope(report, account);
-	next_lines_format.format(out, bound_scope);
-      }
-      total += val;
+  if (! account.has_flags(ACCOUNT_EXT_MATCHING))
+    return;
+
+  value_t val = account.xdata().value;
+
+  if (val.type() >= value_t::BALANCE) {
+    const balance_t * bal;
+    if (val.is_type(value_t::BALANCE))
+      bal = &(val.as_balance());
+    else
+      assert(false);
+
+    foreach (balance_t::amounts_map::value_type pair, bal->amounts) {
+      account.xdata().value = pair.second;
+      bind_scope_t bound_scope(report, account);
+      next_lines_format.format(out, bound_scope);
     }
-    account.xdata().add_flags(ACCOUNT_EXT_DISPLAYED);
+    account.xdata().value = val;
+  } else {
+    bind_scope_t bound_scope(report, account);
+    next_lines_format.format(out, bound_scope);
   }
+  total += val;
 }
 
 } // namespace ledger
diff --git a/src/output.h b/src/output.h
index d62a77b1..6952a4a5 100644
--- a/src/output.h
+++ b/src/output.h
@@ -165,9 +165,6 @@ protected:
   item_predicate disp_pred;
   bool		 print_final_total;
 
-  bool disp_subaccounts_p(account_t& account, account_t *& to_show);
-  bool display_account(account_t& account);
-
 public:
   format_accounts(report_t&	_report,
 		  const string& _format = "",
@@ -176,14 +173,20 @@ public:
       print_final_total(_print_final_total)
   {
     TRACE_CTOR(format_accounts, "report&, const string&, const bool");
+
+    if (report.HANDLED(display_)) {
+      DEBUG("account.display",
+	    "Account display predicate: " << report.HANDLER(display_).str());
+      disp_pred.predicate.parse(report.HANDLER(display_).str());
+    }
   }
   virtual ~format_accounts() {
     TRACE_DTOR(format_accounts);
   }
 
-  bool should_display(account_t& account);
-
+  virtual void post_accounts(account_t& account);
   virtual void flush();
+
   virtual void operator()(account_t& account);
 };
 
@@ -207,7 +210,7 @@ class format_equity : public format_accounts
   }
 
   virtual void flush();
-  virtual void operator()(account_t& account);
+  virtual void post_accounts(account_t& account);
 };
 
 } // namespace ledger