common/formatting/tree_unwrapper.cc - third_party/verible - Git at Google

 // Copyright 2017-2020 The Verible Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //      http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "common/formatting/tree_unwrapper.h"

 #include <algorithm>
 #include <functional>
 #include <iterator>
 #include <memory>
 #include <vector>

 #include "common/formatting/format_token.h"
 #include "common/formatting/token_partition_tree.h"
 #include "common/formatting/unwrapped_line.h"
 #include "common/text/concrete_syntax_tree.h"
 #include "common/text/symbol.h"
 #include "common/text/text_structure.h"
 #include "common/text/token_info.h"
 #include "common/text/token_stream_view.h"
 #include "common/util/logging.h"
 #include "common/util/value_saver.h"
 #include "common/util/vector_tree.h"

 namespace verible {

 void TreeUnwrapper::VerifyFullTreeFormatTokenRanges() const {
   verible::VerifyFullTreeFormatTokenRanges(unwrapped_lines_,
                                            preformatted_tokens_.begin());
 }

 TreeUnwrapper::TreeUnwrapper(
     const TextStructureView& view,
     const preformatted_tokens_type& preformatted_tokens)
     : text_structure_view_(view),
       preformatted_tokens_(preformatted_tokens),
       next_unfiltered_token_(text_structure_view_.TokenStream().begin()),
       unwrapped_lines_(UnwrappedLine(current_indentation_spaces_,
                                      preformatted_tokens_.begin(),
                                      PartitionPolicyEnum::kAlwaysExpand)),
       // The "top-most" UnwrappedLine spans the entire file, so the first
       // unwrapped line should be a considered a partition (child) thereof.
       // This acts like 'pushing' the first child onto a stack.
       active_unwrapped_lines_(unwrapped_lines_.NewChild(UnwrappedLine(
           current_indentation_spaces_,
           unwrapped_lines_.Value().TokensRange().begin()
           // TODO(fangism): set partition policy here?
           ))) {
   // Every new unwrapped line will be initially empty, but the range
   // will point to the correct starting position in the preformatted_tokens_
   // array, and be able to 'extend' into the array of preformatted_tokens_.
 }

 const TokenPartitionTree* TreeUnwrapper::Unwrap() {
   // Collect tokens that appear before first syntax tree leaf, e.g. comments.
   CollectLeadingFilteredTokens();

   // Traverse the concrete syntax tree to build up token partitions.
   ABSL_DIE_IF_NULL(text_structure_view_.SyntaxTree())->Accept(this);

   // After traversing the ConcreteSyntaxTree, collect possible tokens filtered
   // after the right-most leaf until the end-of-file.
   CollectTrailingFilteredTokens();

   // No action needed to close out the most recent UnwrappedLine.
   if (!preformatted_tokens_.empty()) {
     const auto iter = CurrentFormatTokenIterator() - 1;
     const auto back = preformatted_tokens_.end() - 1;
     // Ensure that we have spanned the last significant token (used for
     // formatting).  It is possible that unfiltered tokens include trailing
     // newlines after the last leaf, which is why the iterators may not
     // necessarily line up exactly.
     CHECK(iter >= back) << "missing " << std::distance(iter, back)
                         << " format tokens at the end.  got: " << *iter->token
                         << " vs. " << *back->token;
   }

   {
     // This 'pops' the tree node stack once more to balance the initial
     // child 'push' that was done in the constructor's initialization
     // of active_unwrapped_lines_.
     active_unwrapped_lines_ = active_unwrapped_lines_->Parent();
     // Confirm that tree visitation is balanced.
     CHECK_EQ(active_unwrapped_lines_, &unwrapped_lines_);
     FinishUnwrappedLine();
   }

   VerifyFullTreeFormatTokenRanges();

   return &unwrapped_lines_;
 }

 std::vector<UnwrappedLine> TreeUnwrapper::FullyPartitionedUnwrappedLines()
     const {
   // If a node of the ExpandedTree<UnwrappedLine> has children,
   // visit only the node's children.
   std::vector<UnwrappedLine> result;
   unwrapped_lines_.ApplyPostOrder([&result](const TokenPartitionTree& node) {
     if (node.Children().empty()) {
       result.push_back(node.Value());
     }
   });

   // Filter out trailing blank UnwrappedLines.
   while (!result.empty() && result.back().IsEmpty()) {
     result.pop_back();
   }
   return result;
 }

 TokenSequence::const_iterator TreeUnwrapper::NextUnfilteredToken() const {
   const auto& origin_tokens = text_structure_view_.TokenStream();
   CHECK(next_unfiltered_token_ >= origin_tokens.begin());
   CHECK(next_unfiltered_token_ <= origin_tokens.end());
   return next_unfiltered_token_;
 }

 TreeUnwrapper::preformatted_tokens_type::const_iterator
 TreeUnwrapper::CurrentFormatTokenIterator() const {
   // Caution to caller: this could return preformatted_tokens_.end()
   return CurrentUnwrappedLine().TokensRange().end();
 }

 UnwrappedLine& TreeUnwrapper::CurrentUnwrappedLine() {
   return ABSL_DIE_IF_NULL(CurrentTokenPartition())->Value();
 }

 const UnwrappedLine& TreeUnwrapper::CurrentUnwrappedLine() const {
   return ABSL_DIE_IF_NULL(CurrentTokenPartition())->Value();
 }

 void TreeUnwrapper::RemoveTrailingEmptyPartitions(TokenPartitionTree* node) {
   auto& children = node->Children();
   while (!children.empty() && children.back().Value().IsEmpty()) {
     children.pop_back();
   }
 }

 void TreeUnwrapper::CloseUnwrappedLineTreeNode(
     TokenPartitionTree* node,
     preformatted_tokens_type::const_iterator token_iter) {
   const auto& children = node->Children();
   if (!children.empty()) {
     const auto last_child_end = children.back().Value().TokensRange().end();
     CHECK(last_child_end >= token_iter)
         << "Child range should never have to catch up to parent.";
     if (token_iter < last_child_end) {
       // Parent needs to catch up to child.
       // This can occur because we're only updating one active_unwrapped_line_
       // node at a time, so this is needed to maintain the parent-child
       // range equivalence.
       node->Value().SpanUpToToken(last_child_end);
     }
   }
 }

 void TreeUnwrapper::FinishUnwrappedLine() {
   RemoveTrailingEmptyPartitions(active_unwrapped_lines_);

   const auto iter = CurrentFormatTokenIterator();
   CloseUnwrappedLineTreeNode(active_unwrapped_lines_, iter);

   // At this point, the current active_unwrapped_lines_ is finalized because
   // we are starting a new one.  Now is the right time to verify invariants.
   VerifyTreeNodeFormatTokenRanges(*active_unwrapped_lines_,
                                   preformatted_tokens_.begin());
 }

 void TreeUnwrapper::StartNewUnwrappedLine(PartitionPolicyEnum partitioning,
                                           const Symbol* origin) {
   // TODO(fangism): Take an optional indentation depth override parameter.
   auto& current_unwrapped_line = CurrentUnwrappedLine();
   if (current_unwrapped_line.IsEmpty()) {  // token range is empty
     // Re-use previously created unwrapped line.
     current_unwrapped_line.SetIndentationSpaces(current_indentation_spaces_);
     current_unwrapped_line.SetPartitionPolicy(partitioning);
     current_unwrapped_line.SetOrigin(origin);
     VLOG(4) << "re-using node at " << NodePath(*active_unwrapped_lines_) << ": "
             << current_unwrapped_line;
     // There may have been subtrees created with empty ranges, e.g.
     // for the sake of being able to correctly indent comments inside blocks.
     // If so, delete those so that token partition range invariants are
     // maintained through re-use of an existing node.
     if (!active_unwrapped_lines_->Children().empty()) {
       VLOG(4) << "removed pre-existing child partitions.";
       active_unwrapped_lines_->Children().clear();
     }
   } else {
     // To maintain the invariant that a parent range's upper-bound is equal
     // to the upper-bound of its last child, we may have to add one more
     // child whose range spans up to the parent's upper-bound.
     // The right time to do this is when an UnwrappedLine is finalized,
     // which is the same time that a new UnwrappedLine is added, here.
     FinishUnwrappedLine();

     // Create new sibling to current unwrapped line, maintaining same level.
     active_unwrapped_lines_ = active_unwrapped_lines_->NewSibling(
         UnwrappedLine(current_indentation_spaces_, CurrentFormatTokenIterator(),
                       partitioning));
     CurrentUnwrappedLine().SetOrigin(origin);
     VLOG(4) << "new sibling node " << NodePath(*active_unwrapped_lines_) << ": "
             << CurrentUnwrappedLine();
   }
 }

 void TreeUnwrapper::MergeLastTwoPartitions() {
   auto* parent =
       MergeLeafIntoPreviousLeaf(unwrapped_lines_.RightmostDescendant());
   if (parent != nullptr) {
     // Pre-existing partition no longer exists, update active_unwrapped_lines_
     // to point to a new empty partition at the current indentation level.
     const auto current_token_iter =
         unwrapped_lines_.RightmostDescendant()->Value().TokensRange().end();
     active_unwrapped_lines_ = parent->NewChild(UnwrappedLine(
         current_indentation_spaces_, current_token_iter
         // TODO(fangism): partitioning policy?
         // TODO(fangism): origin?
         ));
   }
 }

 void TreeUnwrapper::AddTokenToCurrentUnwrappedLine() {
   CHECK(NextUnfilteredTokenIsRetained());
   // Advance CurrentFormatTokenIterator().
   CurrentUnwrappedLine().SpanNextToken();
   VLOG(4) << "appended: " << *CurrentUnwrappedLine().TokensRange().back().token;
   ++next_unfiltered_token_;
 }

 bool TreeUnwrapper::NextUnfilteredTokenIsRetained() const {
   const auto iter = CurrentFormatTokenIterator();
   // (iter->token == &*next_unfiltered_token_) implies that is was one of the
   // tokens preserved in the subset array of filtered tokens, as determined
   // by a predication function (keeper), but without having to re-check
   // (and maintain a copy/reference of) the keeper predicate, nor perform
   // a set membership check (e.g. binary search).
   // This works only because we maintain that next_unfiltered_token_
   // will never lead nor lag CurrentFormatTokenIterator() by more than one
   // filtered token.
   return iter != preformatted_tokens_.end() &&  // possible if array is empty
          iter->token == &*next_unfiltered_token_;
 }

 void TreeUnwrapper::SkipUnfilteredTokens(
     std::function<bool(const verible::TokenInfo&)> predicate) {
   while (predicate(*next_unfiltered_token_)) {
     ++next_unfiltered_token_;
   }
 }

 // Advances next_unfiltered_token_ and also places the token into the
 // CurrentUnwrappedLine() if it is a non-whitespace token, like a comment.
 void TreeUnwrapper::AdvanceNextUnfilteredToken() {
   if (next_unfiltered_token_->isEOF()) return;
   if (NextUnfilteredTokenIsRetained()) {
     // This is a non-syntax-tree token, such as a comment or attribute.
     // Based on the KeepNonWhitespace predicate, next_unfiltered_token_
     // must point to the next PreFormatToken.
     // This already advances next_unfiltered_token_.
     AddTokenToCurrentUnwrappedLine();
   } else {
     // The inverse condition implies that the token pointed to was filtered
     // out, e.g. whitespace.
     ++next_unfiltered_token_;
   }
 }

 void TreeUnwrapper::TraverseChildren(const verible::SyntaxTreeNode& node) {
   // Can't just use TreeContextVisitor::Visit(node) because we need to
   // call a visit hook between children.
   const verible::SyntaxTreeContext::AutoPop p(&current_context_, &node);
   InterChildNodeHook(node);
   for (const auto& child : node.children()) {
     if (child) {
       child->Accept(this);
       InterChildNodeHook(node);
     }
   }
 }

 TreeUnwrapper::preformatted_tokens_type::const_iterator
 TreeUnwrapper::VisitIndentedChildren(const SyntaxTreeNode& node,
                                      int indentation_delta,
                                      PartitionPolicyEnum partitioning) {
   // Visit subtree with increased indentation level.
   const ValueSaver<int> depth_saver(
       &current_indentation_spaces_,
       current_indentation_spaces_ + indentation_delta);

   // Mark a new sibling at the new indentation level, apply partition policy.
   StartNewUnwrappedLine(partitioning, &node);

   // Start first child right away.
   const ValueSaver<TokenPartitionTree*> tree_saver(
       &active_unwrapped_lines_,
       active_unwrapped_lines_->NewChild(UnwrappedLine(
           current_indentation_spaces_, CurrentFormatTokenIterator(),
           PartitionPolicyEnum::kFitOnLineElseExpand /* default */)));
   VLOG(3) << __FUNCTION__ << ", new child node "
           << NodePath(*active_unwrapped_lines_) << ": "
           << CurrentUnwrappedLine();
   TraverseChildren(node);

   return CurrentFormatTokenIterator();

   // To maintain the invariant that a parent range's upper-bound is equal
   // to the upper-bound of its last child, we may have to add one more
   // child whose range spans up to the parent's upper-bound.
   // The right time to do this is when an UnwrappedLine is finalized,
   // which is the same time that a new UnwrappedLine is added.
   // See StartNewUnwrappedLine().
 }

 void TreeUnwrapper::VisitIndentedSection(const SyntaxTreeNode& node,
                                          int indentation_delta,
                                          PartitionPolicyEnum partitioning) {
   const auto last_ftoken_iter =
       VisitIndentedChildren(node, indentation_delta, partitioning);

   // TODO(fangism): do we ever need to remove trailing empty partitions here?

   // Update parent's end() format token iterator to match that of
   // its last child.  It can still be advanced later.
   active_unwrapped_lines_->Value().SpanUpToToken(last_ftoken_iter);

   // Start new empty UnwrappedLine at the previous indentation level.
   StartNewUnwrappedLine(PartitionPolicyEnum::kUninitialized, nullptr);
 }

 std::ostream& operator<<(std::ostream& stream, const TreeUnwrapper& unwrapper) {
   for (const auto& uwline : unwrapper.FullyPartitionedUnwrappedLines()) {
     stream << uwline << std::endl;
   }
   return stream;
 }

 }  // namespace verible
	// Copyright 2017-2020 The Verible Authors.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "common/formatting/tree_unwrapper.h"

	#include <algorithm>
	#include <functional>
	#include <iterator>
	#include <memory>
	#include <vector>

	#include "common/formatting/format_token.h"
	#include "common/formatting/token_partition_tree.h"
	#include "common/formatting/unwrapped_line.h"
	#include "common/text/concrete_syntax_tree.h"
	#include "common/text/symbol.h"
	#include "common/text/text_structure.h"
	#include "common/text/token_info.h"
	#include "common/text/token_stream_view.h"
	#include "common/util/logging.h"
	#include "common/util/value_saver.h"
	#include "common/util/vector_tree.h"

	namespace verible {

	void TreeUnwrapper::VerifyFullTreeFormatTokenRanges() const {
	verible::VerifyFullTreeFormatTokenRanges(unwrapped_lines_,
	preformatted_tokens_.begin());
	}

	TreeUnwrapper::TreeUnwrapper(
	const TextStructureView& view,
	const preformatted_tokens_type& preformatted_tokens)
	: text_structure_view_(view),
	preformatted_tokens_(preformatted_tokens),
	next_unfiltered_token_(text_structure_view_.TokenStream().begin()),
	unwrapped_lines_(UnwrappedLine(current_indentation_spaces_,
	preformatted_tokens_.begin(),
	PartitionPolicyEnum::kAlwaysExpand)),
	// The "top-most" UnwrappedLine spans the entire file, so the first
	// unwrapped line should be a considered a partition (child) thereof.
	// This acts like 'pushing' the first child onto a stack.
	active_unwrapped_lines_(unwrapped_lines_.NewChild(UnwrappedLine(
	current_indentation_spaces_,
	unwrapped_lines_.Value().TokensRange().begin()
	// TODO(fangism): set partition policy here?
	))) {
	// Every new unwrapped line will be initially empty, but the range
	// will point to the correct starting position in the preformatted_tokens_
	// array, and be able to 'extend' into the array of preformatted_tokens_.
	}

	const TokenPartitionTree* TreeUnwrapper::Unwrap() {
	// Collect tokens that appear before first syntax tree leaf, e.g. comments.
	CollectLeadingFilteredTokens();

	// Traverse the concrete syntax tree to build up token partitions.
	ABSL_DIE_IF_NULL(text_structure_view_.SyntaxTree())->Accept(this);

	// After traversing the ConcreteSyntaxTree, collect possible tokens filtered
	// after the right-most leaf until the end-of-file.
	CollectTrailingFilteredTokens();

	// No action needed to close out the most recent UnwrappedLine.
	if (!preformatted_tokens_.empty()) {
	const auto iter = CurrentFormatTokenIterator() - 1;
	const auto back = preformatted_tokens_.end() - 1;
	// Ensure that we have spanned the last significant token (used for
	// formatting). It is possible that unfiltered tokens include trailing
	// newlines after the last leaf, which is why the iterators may not
	// necessarily line up exactly.
	CHECK(iter >= back) << "missing " << std::distance(iter, back)
	<< " format tokens at the end. got: " << *iter->token
	<< " vs. " << *back->token;
	}

	{
	// This 'pops' the tree node stack once more to balance the initial
	// child 'push' that was done in the constructor's initialization
	// of active_unwrapped_lines_.
	active_unwrapped_lines_ = active_unwrapped_lines_->Parent();
	// Confirm that tree visitation is balanced.
	CHECK_EQ(active_unwrapped_lines_, &unwrapped_lines_);
	FinishUnwrappedLine();
	}

	VerifyFullTreeFormatTokenRanges();

	return &unwrapped_lines_;
	}

	std::vector<UnwrappedLine> TreeUnwrapper::FullyPartitionedUnwrappedLines()
	const {
	// If a node of the ExpandedTree<UnwrappedLine> has children,
	// visit only the node's children.
	std::vector<UnwrappedLine> result;
	unwrapped_lines_.ApplyPostOrder([&result](const TokenPartitionTree& node) {
	if (node.Children().empty()) {
	result.push_back(node.Value());
	}
	});

	// Filter out trailing blank UnwrappedLines.
	while (!result.empty() && result.back().IsEmpty()) {
	result.pop_back();
	}
	return result;
	}

	TokenSequence::const_iterator TreeUnwrapper::NextUnfilteredToken() const {
	const auto& origin_tokens = text_structure_view_.TokenStream();
	CHECK(next_unfiltered_token_ >= origin_tokens.begin());
	CHECK(next_unfiltered_token_ <= origin_tokens.end());
	return next_unfiltered_token_;
	}

	TreeUnwrapper::preformatted_tokens_type::const_iterator
	TreeUnwrapper::CurrentFormatTokenIterator() const {
	// Caution to caller: this could return preformatted_tokens_.end()
	return CurrentUnwrappedLine().TokensRange().end();
	}

	UnwrappedLine& TreeUnwrapper::CurrentUnwrappedLine() {
	return ABSL_DIE_IF_NULL(CurrentTokenPartition())->Value();
	}

	const UnwrappedLine& TreeUnwrapper::CurrentUnwrappedLine() const {
	return ABSL_DIE_IF_NULL(CurrentTokenPartition())->Value();
	}

	void TreeUnwrapper::RemoveTrailingEmptyPartitions(TokenPartitionTree* node) {
	auto& children = node->Children();
	while (!children.empty() && children.back().Value().IsEmpty()) {
	children.pop_back();
	}
	}

	void TreeUnwrapper::CloseUnwrappedLineTreeNode(
	TokenPartitionTree* node,
	preformatted_tokens_type::const_iterator token_iter) {
	const auto& children = node->Children();
	if (!children.empty()) {
	const auto last_child_end = children.back().Value().TokensRange().end();
	CHECK(last_child_end >= token_iter)
	<< "Child range should never have to catch up to parent.";
	if (token_iter < last_child_end) {
	// Parent needs to catch up to child.
	// This can occur because we're only updating one active_unwrapped_line_
	// node at a time, so this is needed to maintain the parent-child
	// range equivalence.
	node->Value().SpanUpToToken(last_child_end);
	}
	}
	}

	void TreeUnwrapper::FinishUnwrappedLine() {
	RemoveTrailingEmptyPartitions(active_unwrapped_lines_);

	const auto iter = CurrentFormatTokenIterator();
	CloseUnwrappedLineTreeNode(active_unwrapped_lines_, iter);

	// At this point, the current active_unwrapped_lines_ is finalized because
	// we are starting a new one. Now is the right time to verify invariants.
	VerifyTreeNodeFormatTokenRanges(*active_unwrapped_lines_,
	preformatted_tokens_.begin());
	}

	void TreeUnwrapper::StartNewUnwrappedLine(PartitionPolicyEnum partitioning,
	const Symbol* origin) {
	// TODO(fangism): Take an optional indentation depth override parameter.
	auto& current_unwrapped_line = CurrentUnwrappedLine();
	if (current_unwrapped_line.IsEmpty()) { // token range is empty
	// Re-use previously created unwrapped line.
	current_unwrapped_line.SetIndentationSpaces(current_indentation_spaces_);
	current_unwrapped_line.SetPartitionPolicy(partitioning);
	current_unwrapped_line.SetOrigin(origin);
	VLOG(4) << "re-using node at " << NodePath(*active_unwrapped_lines_) << ": "
	<< current_unwrapped_line;
	// There may have been subtrees created with empty ranges, e.g.
	// for the sake of being able to correctly indent comments inside blocks.
	// If so, delete those so that token partition range invariants are
	// maintained through re-use of an existing node.
	if (!active_unwrapped_lines_->Children().empty()) {
	VLOG(4) << "removed pre-existing child partitions.";
	active_unwrapped_lines_->Children().clear();
	}
	} else {
	// To maintain the invariant that a parent range's upper-bound is equal
	// to the upper-bound of its last child, we may have to add one more
	// child whose range spans up to the parent's upper-bound.
	// The right time to do this is when an UnwrappedLine is finalized,
	// which is the same time that a new UnwrappedLine is added, here.
	FinishUnwrappedLine();

	// Create new sibling to current unwrapped line, maintaining same level.
	active_unwrapped_lines_ = active_unwrapped_lines_->NewSibling(
	UnwrappedLine(current_indentation_spaces_, CurrentFormatTokenIterator(),
	partitioning));
	CurrentUnwrappedLine().SetOrigin(origin);
	VLOG(4) << "new sibling node " << NodePath(*active_unwrapped_lines_) << ": "
	<< CurrentUnwrappedLine();
	}
	}

	void TreeUnwrapper::MergeLastTwoPartitions() {
	auto* parent =
	MergeLeafIntoPreviousLeaf(unwrapped_lines_.RightmostDescendant());
	if (parent != nullptr) {
	// Pre-existing partition no longer exists, update active_unwrapped_lines_
	// to point to a new empty partition at the current indentation level.
	const auto current_token_iter =
	unwrapped_lines_.RightmostDescendant()->Value().TokensRange().end();
	active_unwrapped_lines_ = parent->NewChild(UnwrappedLine(
	current_indentation_spaces_, current_token_iter
	// TODO(fangism): partitioning policy?
	// TODO(fangism): origin?
	));
	}
	}

	void TreeUnwrapper::AddTokenToCurrentUnwrappedLine() {
	CHECK(NextUnfilteredTokenIsRetained());
	// Advance CurrentFormatTokenIterator().
	CurrentUnwrappedLine().SpanNextToken();
	VLOG(4) << "appended: " << *CurrentUnwrappedLine().TokensRange().back().token;
	++next_unfiltered_token_;
	}

	bool TreeUnwrapper::NextUnfilteredTokenIsRetained() const {
	const auto iter = CurrentFormatTokenIterator();
	// (iter->token == &*next_unfiltered_token_) implies that is was one of the
	// tokens preserved in the subset array of filtered tokens, as determined
	// by a predication function (keeper), but without having to re-check
	// (and maintain a copy/reference of) the keeper predicate, nor perform
	// a set membership check (e.g. binary search).
	// This works only because we maintain that next_unfiltered_token_
	// will never lead nor lag CurrentFormatTokenIterator() by more than one
	// filtered token.
	return iter != preformatted_tokens_.end() && // possible if array is empty
	iter->token == &*next_unfiltered_token_;
	}

	void TreeUnwrapper::SkipUnfilteredTokens(
	std::function<bool(const verible::TokenInfo&)> predicate) {
	while (predicate(*next_unfiltered_token_)) {
	++next_unfiltered_token_;
	}
	}

	// Advances next_unfiltered_token_ and also places the token into the
	// CurrentUnwrappedLine() if it is a non-whitespace token, like a comment.
	void TreeUnwrapper::AdvanceNextUnfilteredToken() {
	if (next_unfiltered_token_->isEOF()) return;
	if (NextUnfilteredTokenIsRetained()) {
	// This is a non-syntax-tree token, such as a comment or attribute.
	// Based on the KeepNonWhitespace predicate, next_unfiltered_token_
	// must point to the next PreFormatToken.
	// This already advances next_unfiltered_token_.
	AddTokenToCurrentUnwrappedLine();
	} else {
	// The inverse condition implies that the token pointed to was filtered
	// out, e.g. whitespace.
	++next_unfiltered_token_;
	}
	}

	void TreeUnwrapper::TraverseChildren(const verible::SyntaxTreeNode& node) {
	// Can't just use TreeContextVisitor::Visit(node) because we need to
	// call a visit hook between children.
	const verible::SyntaxTreeContext::AutoPop p(&current_context_, &node);
	InterChildNodeHook(node);
	for (const auto& child : node.children()) {
	if (child) {
	child->Accept(this);
	InterChildNodeHook(node);
	}
	}
	}

	TreeUnwrapper::preformatted_tokens_type::const_iterator
	TreeUnwrapper::VisitIndentedChildren(const SyntaxTreeNode& node,
	int indentation_delta,
	PartitionPolicyEnum partitioning) {
	// Visit subtree with increased indentation level.
	const ValueSaver<int> depth_saver(
	&current_indentation_spaces_,
	current_indentation_spaces_ + indentation_delta);

	// Mark a new sibling at the new indentation level, apply partition policy.
	StartNewUnwrappedLine(partitioning, &node);

	// Start first child right away.
	const ValueSaver<TokenPartitionTree*> tree_saver(
	&active_unwrapped_lines_,
	active_unwrapped_lines_->NewChild(UnwrappedLine(
	current_indentation_spaces_, CurrentFormatTokenIterator(),
	PartitionPolicyEnum::kFitOnLineElseExpand /* default */)));
	VLOG(3) << __FUNCTION__ << ", new child node "
	<< NodePath(*active_unwrapped_lines_) << ": "
	<< CurrentUnwrappedLine();
	TraverseChildren(node);

	return CurrentFormatTokenIterator();

	// To maintain the invariant that a parent range's upper-bound is equal
	// to the upper-bound of its last child, we may have to add one more
	// child whose range spans up to the parent's upper-bound.
	// The right time to do this is when an UnwrappedLine is finalized,
	// which is the same time that a new UnwrappedLine is added.
	// See StartNewUnwrappedLine().
	}

	void TreeUnwrapper::VisitIndentedSection(const SyntaxTreeNode& node,
	int indentation_delta,
	PartitionPolicyEnum partitioning) {
	const auto last_ftoken_iter =
	VisitIndentedChildren(node, indentation_delta, partitioning);

	// TODO(fangism): do we ever need to remove trailing empty partitions here?

	// Update parent's end() format token iterator to match that of
	// its last child. It can still be advanced later.
	active_unwrapped_lines_->Value().SpanUpToToken(last_ftoken_iter);

	// Start new empty UnwrappedLine at the previous indentation level.
	StartNewUnwrappedLine(PartitionPolicyEnum::kUninitialized, nullptr);
	}

	std::ostream& operator<<(std::ostream& stream, const TreeUnwrapper& unwrapper) {
	for (const auto& uwline : unwrapper.FullyPartitionedUnwrappedLines()) {
	stream << uwline << std::endl;
	}
	return stream;
	}

	} // namespace verible