tools/fidlcat/lib/comparator.cc - fuchsia - Git at Google

 // Copyright 2019 The Fuchsia Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "tools/fidlcat/lib/comparator.h"

 #include <zircon/assert.h>

 #include <iostream>
 #include <string>
 #include <utility>
 #include <vector>

 namespace fidlcat {

 void Comparator::CompareInput(std::string_view syscall_inputs, std::string_view actual_process_name,
                               uint64_t actual_pid, uint64_t actual_tid) {
   // remove header from the message
   syscall_inputs = AnalyzesAndRemovesHeader(syscall_inputs);
   auto actual_message_node = actual_message_graph_.InsertMessage(actual_process_name, actual_pid,
                                                                  actual_tid, syscall_inputs);
   // Is there a unique match for this message in the golden messages? If so, we propagate this
   // match.
   std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
   if (matching_golden_node) {
     PropagateMatch(actual_message_node, matching_golden_node, false);
   }
   last_unmatched_input_from_tid_[actual_tid] = actual_message_node;
 }

 void Comparator::CompareOutput(std::string_view syscall_outputs,
                                std::string_view actual_process_name, uint64_t actual_pid,
                                uint64_t actual_tid) {
   // If present, remove header from message
   syscall_outputs = AnalyzesAndRemovesHeader(syscall_outputs);

   // Create the output node, linking it to its corresponding input node if there is one.
   auto matching_input = last_unmatched_input_from_tid_.find(actual_tid);
   auto actual_message_node =
       matching_input != last_unmatched_input_from_tid_.end()
           ? actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
                                                 syscall_outputs, matching_input->second)
           : actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
                                                 syscall_outputs);

   // Is there a unique match for this message in the golden messages? If so, we propagate this
   // match.
   std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
   if (matching_golden_node) {
     PropagateMatch(actual_message_node, matching_golden_node, false);
   }
 }

 void Comparator::DecodingError(std::string_view error) {
   compare_results_ << "Unexpected decoding error in the current execution:\n" << error;
 }

 std::shared_ptr<GoldenMessageNode> Comparator::UniqueMatchToGolden(
     std::shared_ptr<ActualMessageNode> actual_message_node) {
   auto poss_golden_messages =
       golden_message_graph_.message_nodes().find(actual_message_node->message());
   if (poss_golden_messages == golden_message_graph_.message_nodes().end()) {  // No message matched
     compare_results_ << "No golden message could match " << *actual_message_node;
     return nullptr;
   }
   if (poss_golden_messages->second.size() == 1) {
     // exactly one message from golden matched this string
     return poss_golden_messages->second[0];
   }
   // More than one golden message matched
   return nullptr;
 }

 bool Comparator::PropagateMatch(std::shared_ptr<ActualNode> actual_node,
                                 std::shared_ptr<GoldenNode> golden_node, bool reverse_propagate) {
   if (!actual_node || !golden_node) {
     return false;
   }
   if (actual_node->matching_golden_node()) {
     if (actual_node->matching_golden_node() == golden_node) {
       return true;
     }
     compare_results_ << "Conflicting matches for " << *actual_node << "matched to " << *golden_node
                      << " and " << *(actual_node->matching_golden_node()) << "\n";
     return false;
   }
   if (golden_node->has_matching_actual_node()) {
     compare_results_ << *golden_node << "was matched twice.\n";
     return false;
   }
   if (golden_node->dependencies().size() != actual_node->dependencies().size()) {
     compare_results_ << *actual_node << " with " << actual_node->dependencies().size()
                      << " dependencies was matched with " << *golden_node << " which has "
                      << golden_node->dependencies().size() << " dependencies \n";
     return false;
   }
   actual_node->set_matching_golden_node(golden_node);
   golden_node->set_has_matching_actual_node();

   auto golden_i = golden_node->dependencies().begin();

   for (auto i = actual_node->dependencies().begin(); i != actual_node->dependencies().end(); i++) {
     auto actual_dependency_node = i->second;
     // The golden node that should match actual_dependency_node according to the dependency links
     // of golden_node
     auto golden_dependency_node = golden_i->second;

     if (!PropagateMatch(actual_dependency_node, golden_dependency_node, reverse_propagate)) {
       return false;
     }
     golden_i++;
   }
   if (reverse_propagate) {
     return ReversePropagateMatch(actual_node);
   }
   return true;
 }

 bool Comparator::ReversePropagateMatch(std::shared_ptr<ActualNode> actual_node) {
   // Should only be called after Propagate has been called on actual_node, so actual_node should
   // have a matching golden_node.
   auto golden_node = actual_node->matching_golden_node();
   ZX_ASSERT(golden_node != nullptr);

   // We can only propagate along a reverse dependency if it is the only one of its type.
   for (auto actual_link_type_pair = actual_node->reverse_dependencies().begin();
        actual_link_type_pair != actual_node->reverse_dependencies().end();
        actual_link_type_pair++) {
     size_t actual_nb_link_of_type = actual_link_type_pair->second.size();
     if (actual_nb_link_of_type > 1) {
       // multiple links with same type, we can't do any propagation
       continue;
     }
     auto golden_link_type_pair =
         golden_node->get_reverse_dependencies_by_type(actual_link_type_pair->first);
     // This reverse link is not present in golden_node, there is no possible matching between the
     // current execution and the one stored in the golden file.
     if (golden_link_type_pair == golden_node->reverse_dependencies().end()) {
       compare_results_ << *actual_node << " with a reverse dependency of type "
                        << actual_link_type_pair->first.second << " was matched to " << *golden_node
                        << " which has no such reverse dependency \n";
       return false;
     }
     size_t golden_nb_link_of_type = golden_link_type_pair->second.size();
     // golden node also has more reverse dependencies than actual_node, this means the matching is
     // not possible as we only call ReversePropagate when the actual_message_graph_ is complete
     if (golden_nb_link_of_type > 1) {
       compare_results_ << *actual_node << " with one reverse dependency of type "
                        << actual_link_type_pair->first.second << " was matched to " << *golden_node
                        << " which has " << golden_nb_link_of_type
                        << " such reverse dependencies \n";
       return false;
     }
     auto actual_dependency_node = actual_link_type_pair->second[0].lock();
     auto golden_dependency_node = golden_link_type_pair->second[0].lock();
     if (!PropagateMatch(actual_dependency_node, golden_dependency_node, true)) {
       return false;
     }
   }
   return true;
 }

 void Comparator::ParseGolden(std::string_view golden_file_contents) {
   size_t processed_char_count = 0;
   // We use this map to link output messages to their corresponding input messages.
   std::map<uint64_t, std::shared_ptr<GoldenMessageNode>> last_unmatched_input_from_tid_golden;

   std::string_view cur_msg = GetMessage(golden_file_contents, &processed_char_count);
   uint64_t previous_pid = 0;
   uint64_t previous_tid = 0;
   std::string previous_process_name;
   while (!cur_msg.empty()) {
     uint64_t pid = 0, tid = 0;
     std::string process_name;

     cur_msg = AnalyzesAndRemovesHeader(cur_msg, &process_name, &pid, &tid);

     // AnalyzesAndRemovesHeader did not update the values of pid, tid and process_name, as there was
     // no header to the message (or it could not be parsed).
     if (pid == 0) {
       pid = previous_pid;
       tid = previous_tid;
       process_name = previous_process_name;
     }

     auto last_unmatched = last_unmatched_input_from_tid_golden.find(tid);
     if (last_unmatched != last_unmatched_input_from_tid_golden.end()) {
       // This is an output message, with a corresponding input messge
       auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg,
                                                               last_unmatched->second);
       last_unmatched_input_from_tid_golden.erase(tid);
     } else {
       auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg);
       if (HasReturn(cur_msg)) {
         last_unmatched_input_from_tid_golden[tid] = message_node;
       }
     }

     golden_file_contents = golden_file_contents.substr(processed_char_count);
     cur_msg = GetMessage(golden_file_contents, &processed_char_count);
     previous_pid = pid;
     previous_tid = tid;
     previous_process_name = process_name;
   }
 }

 std::string_view Comparator::GetMessage(std::string_view messages, size_t* processed_char_count) {
   // begin points to the beginning of the line, end to its end.
   size_t begin = 0;
   size_t end = messages.find('\n', begin);
   // Ignore fidlcat startup lines or empty lines.
   while (end != std::string::npos) {
     if (!IgnoredLine(messages.substr(begin, end - begin))) {
       break;
     }
     begin = end + 1;
     end = messages.find('\n', begin);
   }

   // Now we get the message.
   size_t bpos = begin;
   while (end != std::string::npos) {
     // New line indicates end of syscall input or output.
     if (bpos < begin && end == begin && messages[begin] == '\n') {
       break;
     }
     // Beginning of syscall output display.
     if (bpos < begin && messages.substr(begin, end - begin).find("  ->") == 0) {
       break;
     }
     // If the current line is the beginning of a multiline "sent " or "received ", we skip lines
     // until we get to the closing "  }". To find this closing "}", we rely on fidl_codec printing
     // indentation: if the message is a request (begins with "  sent"), indentation is 2 spaces, if
     // it is a response ("    received"), indentation is 4. Note: if fidl_codec fails to find the
     // direction fo the message (request or response), this may fail to separate the messages
     // properly, or if the first line of the message contains an opening { and some more {} couples,
     // we mail fail to detect this as the beginning of a mutliline message. This should be removed
     // when we can get access to a serialized version of the messages, and not only their text
     // representation.
     std::string_view cur_line = messages.substr(begin, end - begin);
     bool is_received = cur_line.rfind("    received ", 0) != std::string::npos;
     bool is_sent = cur_line.rfind("  sent ", 0) != std::string::npos;
     if (is_sent || is_received) {
       // This is the beginning of a request/response message
       size_t pos_open = cur_line.find('{');
       if (pos_open != std::string::npos &&
           cur_line.substr(pos_open).find('}') == std::string::npos) {
         // We have an open '{', we hence skip lines until we find the matching closing '}'
         size_t indentation = is_sent ? 2 : 4;
         while (end != std::string::npos &&
                !ClosingSequence(messages.substr(begin, end - begin), indentation)) {
           begin = end + 1;
           end = messages.find('\n', begin);
         }
       }
     }
     begin = end + 1;
     end = messages.find('\n', begin);
   }
   *processed_char_count = begin;

   // Note that as expected_output_ is a string_view, substr() returns a string_view as well.
   return messages.substr(bpos, begin - bpos);
 }

 bool Comparator::ClosingSequence(std::string_view line, size_t indentation) {
   if (line.length() < indentation + 1) {
     return false;
   }
   // exactly one tabulation before the first closing ] or }
   for (size_t i = 0; i < indentation; i++) {
     if (line[i] != ' ') {
       return false;
     }
   }
   if (line[indentation] != ']' && line[indentation] != '}') {
     return false;
   }
   // then a sequence of " ]" or " }"
   size_t pos = indentation + 1;
   while (pos + 2 <= line.length()) {
     if (line[pos] != ' ') {
       return false;
     }
     if (line[pos + 1] != '}' && line[pos + 1] != ']') {
       return false;
     }
     pos += 2;
   }
   return true;
 }

 bool Comparator::IgnoredLine(std::string_view line) {
   if (line.length() == 0) {
     return true;
   }
   if (line.length() == 1 && line[0] == '\n') {
     return true;
   }
   static std::vector<std::string> to_be_ignored = {"Checking", "Debug", "Launched", "Monitoring",
                                                    "Stop"};
   for (size_t i = 0; i < to_be_ignored.size(); i++) {
     if (line.find(to_be_ignored[i]) == 0) {
       return true;
     }
   }
   return false;
 }

 std::string_view Comparator::AnalyzesAndRemovesHeader(std::string_view message,
                                                       std::string* process_name, uint64_t* pid,
                                                       uint64_t* tid) {
   constexpr size_t kMinNbCharHeader = 5;
   // The message is a syscall output with no header.
   if (message.find("->") <= kMinNbCharHeader) {
     return message;
   }

   size_t pos_pid = message.find(' ');
   size_t pos_tid = message.find(':');
   // Either there is no header, or we cannot parse it so leave it as is.
   if (pos_pid == std::string::npos || pos_tid == std::string::npos) {
     return message;
   }

   // If we have pointers to pid, tid and process_name, update those.
   if (pid) {
     *pid = ExtractUint64(message.substr(pos_pid + 1));
   }
   if (tid) {
     *tid = ExtractUint64(message.substr(pos_tid + 1));
   }
   if (process_name) {
     *process_name = message.substr(0, pos_pid);
   }
   size_t end_header = message.find(' ', pos_tid);
   if (end_header != std::string::npos) {
     return message.substr(end_header + 1);
   }
   return message;
 }

 uint64_t Comparator::ExtractUint64(std::string_view str) {
   uint64_t result = 0;
   for (size_t i = 0; i < str.size(); ++i) {
     char value = str[i];
     if ((value < '0') || (value > '9')) {
       break;
     }
     result = 10 * result + (value - '0');
   }
   return result;
 }

 bool Comparator::HasReturn(std::string_view message) {
   // Only three syscalls have no return value. Besides as we removed the header from the message,
   // the syscall name is the first word of the message.
   if (message.find("zx_thread_exit") == 0 || message.find("zx_process_exit") == 0 ||
       message.find("zx_futex_wake_handle_close_thread_exit") == 0) {
     return false;
   }
   return true;
 }

 void Comparator::FinishComparison() {
   // All the messages have been intercepted, we now want to check our graph:
   // - First propagates matchings along reverse dependencies now that the graph is complete,
   // - Then checks if there still are unmatched nodes, either golden or actual.

   for (auto i = actual_message_graph_.message_nodes().begin();
        i != actual_message_graph_.message_nodes().end(); i++) {
     for (size_t j = 0; j < i->second.size(); j++) {
       if (i->second[j]->matching_golden_node() && !ReversePropagateMatch(i->second[j])) {
         // The matching failed, with a proper error message
         return;
       }
     }
   }

   for (auto i = actual_message_graph_.pid_nodes().begin();
        i != actual_message_graph_.pid_nodes().end(); i++) {
     if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
       return;
     }
   }

   for (auto i = actual_message_graph_.tid_nodes().begin();
        i != actual_message_graph_.tid_nodes().end(); i++) {
     if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
       return;
     }
   }

   for (auto i = actual_message_graph_.handle_nodes().begin();
        i != actual_message_graph_.handle_nodes().end(); i++) {
     if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
       return;
     }
   }

   // We check that all message nodes are matched to a golden node.
   bool unmatched_message = false;
   for (auto i = actual_message_graph_.message_nodes().begin();
        i != actual_message_graph_.message_nodes().end(); i++) {
     for (size_t j = 0; j < i->second.size(); j++) {
       if (!i->second[j]->matching_golden_node()) {
         compare_results_ << "Unmatched actual message " << i->second[j]->message();
         unmatched_message = true;
       }
     }
   }
   for (auto i = golden_message_graph_.message_nodes().begin();
        i != golden_message_graph_.message_nodes().end(); i++) {
     for (size_t j = 0; j < i->second.size(); j++) {
       if (!i->second[j]->has_matching_actual_node()) {
         compare_results_ << "Unmatched golden message " << i->second[j]->message();
         unmatched_message = true;
       }
     }
   }

   // There is no need to check that handles, pids and tids are matched: as all of them have at least
   // one message that depends from them, if all messages are matched, so are they.
   if (!unmatched_message) {
     compare_results_ << "Messages from the current execution matched the golden file.\n";
   }
 }
 }  // namespace fidlcat
	// Copyright 2019 The Fuchsia Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "tools/fidlcat/lib/comparator.h"

	#include <zircon/assert.h>

	#include <iostream>
	#include <string>
	#include <utility>
	#include <vector>

	namespace fidlcat {

	void Comparator::CompareInput(std::string_view syscall_inputs, std::string_view actual_process_name,
	uint64_t actual_pid, uint64_t actual_tid) {
	// remove header from the message
	syscall_inputs = AnalyzesAndRemovesHeader(syscall_inputs);
	auto actual_message_node = actual_message_graph_.InsertMessage(actual_process_name, actual_pid,
	actual_tid, syscall_inputs);
	// Is there a unique match for this message in the golden messages? If so, we propagate this
	// match.
	std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
	if (matching_golden_node) {
	PropagateMatch(actual_message_node, matching_golden_node, false);
	}
	last_unmatched_input_from_tid_[actual_tid] = actual_message_node;
	}

	void Comparator::CompareOutput(std::string_view syscall_outputs,
	std::string_view actual_process_name, uint64_t actual_pid,
	uint64_t actual_tid) {
	// If present, remove header from message
	syscall_outputs = AnalyzesAndRemovesHeader(syscall_outputs);

	// Create the output node, linking it to its corresponding input node if there is one.
	auto matching_input = last_unmatched_input_from_tid_.find(actual_tid);
	auto actual_message_node =
	matching_input != last_unmatched_input_from_tid_.end()
	? actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
	syscall_outputs, matching_input->second)
	: actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
	syscall_outputs);

	// Is there a unique match for this message in the golden messages? If so, we propagate this
	// match.
	std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
	if (matching_golden_node) {
	PropagateMatch(actual_message_node, matching_golden_node, false);
	}
	}

	void Comparator::DecodingError(std::string_view error) {
	compare_results_ << "Unexpected decoding error in the current execution:\n" << error;
	}

	std::shared_ptr<GoldenMessageNode> Comparator::UniqueMatchToGolden(
	std::shared_ptr<ActualMessageNode> actual_message_node) {
	auto poss_golden_messages =
	golden_message_graph_.message_nodes().find(actual_message_node->message());
	if (poss_golden_messages == golden_message_graph_.message_nodes().end()) { // No message matched
	compare_results_ << "No golden message could match " << *actual_message_node;
	return nullptr;
	}
	if (poss_golden_messages->second.size() == 1) {
	// exactly one message from golden matched this string
	return poss_golden_messages->second[0];
	}
	// More than one golden message matched
	return nullptr;
	}

	bool Comparator::PropagateMatch(std::shared_ptr<ActualNode> actual_node,
	std::shared_ptr<GoldenNode> golden_node, bool reverse_propagate) {
	if (!actual_node \|\| !golden_node) {
	return false;
	}
	if (actual_node->matching_golden_node()) {
	if (actual_node->matching_golden_node() == golden_node) {
	return true;
	}
	compare_results_ << "Conflicting matches for " << actual_node << "matched to " << golden_node
	<< " and " << *(actual_node->matching_golden_node()) << "\n";
	return false;
	}
	if (golden_node->has_matching_actual_node()) {
	compare_results_ << *golden_node << "was matched twice.\n";
	return false;
	}
	if (golden_node->dependencies().size() != actual_node->dependencies().size()) {
	compare_results_ << *actual_node << " with " << actual_node->dependencies().size()
	<< " dependencies was matched with " << *golden_node << " which has "
	<< golden_node->dependencies().size() << " dependencies \n";
	return false;
	}
	actual_node->set_matching_golden_node(golden_node);
	golden_node->set_has_matching_actual_node();

	auto golden_i = golden_node->dependencies().begin();

	for (auto i = actual_node->dependencies().begin(); i != actual_node->dependencies().end(); i++) {
	auto actual_dependency_node = i->second;
	// The golden node that should match actual_dependency_node according to the dependency links
	// of golden_node
	auto golden_dependency_node = golden_i->second;

	if (!PropagateMatch(actual_dependency_node, golden_dependency_node, reverse_propagate)) {
	return false;
	}
	golden_i++;
	}
	if (reverse_propagate) {
	return ReversePropagateMatch(actual_node);
	}
	return true;
	}

	bool Comparator::ReversePropagateMatch(std::shared_ptr<ActualNode> actual_node) {
	// Should only be called after Propagate has been called on actual_node, so actual_node should
	// have a matching golden_node.
	auto golden_node = actual_node->matching_golden_node();
	ZX_ASSERT(golden_node != nullptr);

	// We can only propagate along a reverse dependency if it is the only one of its type.
	for (auto actual_link_type_pair = actual_node->reverse_dependencies().begin();
	actual_link_type_pair != actual_node->reverse_dependencies().end();
	actual_link_type_pair++) {
	size_t actual_nb_link_of_type = actual_link_type_pair->second.size();
	if (actual_nb_link_of_type > 1) {
	// multiple links with same type, we can't do any propagation
	continue;
	}
	auto golden_link_type_pair =
	golden_node->get_reverse_dependencies_by_type(actual_link_type_pair->first);
	// This reverse link is not present in golden_node, there is no possible matching between the
	// current execution and the one stored in the golden file.
	if (golden_link_type_pair == golden_node->reverse_dependencies().end()) {
	compare_results_ << *actual_node << " with a reverse dependency of type "
	<< actual_link_type_pair->first.second << " was matched to " << *golden_node
	<< " which has no such reverse dependency \n";
	return false;
	}
	size_t golden_nb_link_of_type = golden_link_type_pair->second.size();
	// golden node also has more reverse dependencies than actual_node, this means the matching is
	// not possible as we only call ReversePropagate when the actual_message_graph_ is complete
	if (golden_nb_link_of_type > 1) {
	compare_results_ << *actual_node << " with one reverse dependency of type "
	<< actual_link_type_pair->first.second << " was matched to " << *golden_node
	<< " which has " << golden_nb_link_of_type
	<< " such reverse dependencies \n";
	return false;
	}
	auto actual_dependency_node = actual_link_type_pair->second[0].lock();
	auto golden_dependency_node = golden_link_type_pair->second[0].lock();
	if (!PropagateMatch(actual_dependency_node, golden_dependency_node, true)) {
	return false;
	}
	}
	return true;
	}

	void Comparator::ParseGolden(std::string_view golden_file_contents) {
	size_t processed_char_count = 0;
	// We use this map to link output messages to their corresponding input messages.
	std::map<uint64_t, std::shared_ptr<GoldenMessageNode>> last_unmatched_input_from_tid_golden;

	std::string_view cur_msg = GetMessage(golden_file_contents, &processed_char_count);
	uint64_t previous_pid = 0;
	uint64_t previous_tid = 0;
	std::string previous_process_name;
	while (!cur_msg.empty()) {
	uint64_t pid = 0, tid = 0;
	std::string process_name;

	cur_msg = AnalyzesAndRemovesHeader(cur_msg, &process_name, &pid, &tid);

	// AnalyzesAndRemovesHeader did not update the values of pid, tid and process_name, as there was
	// no header to the message (or it could not be parsed).
	if (pid == 0) {
	pid = previous_pid;
	tid = previous_tid;
	process_name = previous_process_name;
	}

	auto last_unmatched = last_unmatched_input_from_tid_golden.find(tid);
	if (last_unmatched != last_unmatched_input_from_tid_golden.end()) {
	// This is an output message, with a corresponding input messge
	auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg,
	last_unmatched->second);
	last_unmatched_input_from_tid_golden.erase(tid);
	} else {
	auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg);
	if (HasReturn(cur_msg)) {
	last_unmatched_input_from_tid_golden[tid] = message_node;
	}
	}

	golden_file_contents = golden_file_contents.substr(processed_char_count);
	cur_msg = GetMessage(golden_file_contents, &processed_char_count);
	previous_pid = pid;
	previous_tid = tid;
	previous_process_name = process_name;
	}
	}

	std::string_view Comparator::GetMessage(std::string_view messages, size_t* processed_char_count) {
	// begin points to the beginning of the line, end to its end.
	size_t begin = 0;
	size_t end = messages.find('\n', begin);
	// Ignore fidlcat startup lines or empty lines.
	while (end != std::string::npos) {
	if (!IgnoredLine(messages.substr(begin, end - begin))) {
	break;
	}
	begin = end + 1;
	end = messages.find('\n', begin);
	}

	// Now we get the message.
	size_t bpos = begin;
	while (end != std::string::npos) {
	// New line indicates end of syscall input or output.
	if (bpos < begin && end == begin && messages[begin] == '\n') {
	break;
	}
	// Beginning of syscall output display.
	if (bpos < begin && messages.substr(begin, end - begin).find(" ->") == 0) {
	break;
	}
	// If the current line is the beginning of a multiline "sent " or "received ", we skip lines
	// until we get to the closing " }". To find this closing "}", we rely on fidl_codec printing
	// indentation: if the message is a request (begins with " sent"), indentation is 2 spaces, if
	// it is a response (" received"), indentation is 4. Note: if fidl_codec fails to find the
	// direction fo the message (request or response), this may fail to separate the messages
	// properly, or if the first line of the message contains an opening { and some more {} couples,
	// we mail fail to detect this as the beginning of a mutliline message. This should be removed
	// when we can get access to a serialized version of the messages, and not only their text
	// representation.
	std::string_view cur_line = messages.substr(begin, end - begin);
	bool is_received = cur_line.rfind(" received ", 0) != std::string::npos;
	bool is_sent = cur_line.rfind(" sent ", 0) != std::string::npos;
	if (is_sent \|\| is_received) {
	// This is the beginning of a request/response message
	size_t pos_open = cur_line.find('{');
	if (pos_open != std::string::npos &&
	cur_line.substr(pos_open).find('}') == std::string::npos) {
	// We have an open '{', we hence skip lines until we find the matching closing '}'
	size_t indentation = is_sent ? 2 : 4;
	while (end != std::string::npos &&
	!ClosingSequence(messages.substr(begin, end - begin), indentation)) {
	begin = end + 1;
	end = messages.find('\n', begin);
	}
	}
	}
	begin = end + 1;
	end = messages.find('\n', begin);
	}
	*processed_char_count = begin;

	// Note that as expected_output_ is a string_view, substr() returns a string_view as well.
	return messages.substr(bpos, begin - bpos);
	}

	bool Comparator::ClosingSequence(std::string_view line, size_t indentation) {
	if (line.length() < indentation + 1) {
	return false;
	}
	// exactly one tabulation before the first closing ] or }
	for (size_t i = 0; i < indentation; i++) {
	if (line[i] != ' ') {
	return false;
	}
	}
	if (line[indentation] != ']' && line[indentation] != '}') {
	return false;
	}
	// then a sequence of " ]" or " }"
	size_t pos = indentation + 1;
	while (pos + 2 <= line.length()) {
	if (line[pos] != ' ') {
	return false;
	}
	if (line[pos + 1] != '}' && line[pos + 1] != ']') {
	return false;
	}
	pos += 2;
	}
	return true;
	}

	bool Comparator::IgnoredLine(std::string_view line) {
	if (line.length() == 0) {
	return true;
	}
	if (line.length() == 1 && line[0] == '\n') {
	return true;
	}
	static std::vector<std::string> to_be_ignored = {"Checking", "Debug", "Launched", "Monitoring",
	"Stop"};
	for (size_t i = 0; i < to_be_ignored.size(); i++) {
	if (line.find(to_be_ignored[i]) == 0) {
	return true;
	}
	}
	return false;
	}

	std::string_view Comparator::AnalyzesAndRemovesHeader(std::string_view message,
	std::string* process_name, uint64_t* pid,
	uint64_t* tid) {
	constexpr size_t kMinNbCharHeader = 5;
	// The message is a syscall output with no header.
	if (message.find("->") <= kMinNbCharHeader) {
	return message;
	}

	size_t pos_pid = message.find(' ');
	size_t pos_tid = message.find(':');
	// Either there is no header, or we cannot parse it so leave it as is.
	if (pos_pid == std::string::npos \|\| pos_tid == std::string::npos) {
	return message;
	}

	// If we have pointers to pid, tid and process_name, update those.
	if (pid) {
	*pid = ExtractUint64(message.substr(pos_pid + 1));
	}
	if (tid) {
	*tid = ExtractUint64(message.substr(pos_tid + 1));
	}
	if (process_name) {
	*process_name = message.substr(0, pos_pid);
	}
	size_t end_header = message.find(' ', pos_tid);
	if (end_header != std::string::npos) {
	return message.substr(end_header + 1);
	}
	return message;
	}

	uint64_t Comparator::ExtractUint64(std::string_view str) {
	uint64_t result = 0;
	for (size_t i = 0; i < str.size(); ++i) {
	char value = str[i];
	if ((value < '0') \|\| (value > '9')) {
	break;
	}
	result = 10 * result + (value - '0');
	}
	return result;
	}

	bool Comparator::HasReturn(std::string_view message) {
	// Only three syscalls have no return value. Besides as we removed the header from the message,
	// the syscall name is the first word of the message.
	if (message.find("zx_thread_exit") == 0 \|\| message.find("zx_process_exit") == 0 \|\|
	message.find("zx_futex_wake_handle_close_thread_exit") == 0) {
	return false;
	}
	return true;
	}

	void Comparator::FinishComparison() {
	// All the messages have been intercepted, we now want to check our graph:
	// - First propagates matchings along reverse dependencies now that the graph is complete,
	// - Then checks if there still are unmatched nodes, either golden or actual.

	for (auto i = actual_message_graph_.message_nodes().begin();
	i != actual_message_graph_.message_nodes().end(); i++) {
	for (size_t j = 0; j < i->second.size(); j++) {
	if (i->second[j]->matching_golden_node() && !ReversePropagateMatch(i->second[j])) {
	// The matching failed, with a proper error message
	return;
	}
	}
	}

	for (auto i = actual_message_graph_.pid_nodes().begin();
	i != actual_message_graph_.pid_nodes().end(); i++) {
	if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
	return;
	}
	}

	for (auto i = actual_message_graph_.tid_nodes().begin();
	i != actual_message_graph_.tid_nodes().end(); i++) {
	if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
	return;
	}
	}

	for (auto i = actual_message_graph_.handle_nodes().begin();
	i != actual_message_graph_.handle_nodes().end(); i++) {
	if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
	return;
	}
	}

	// We check that all message nodes are matched to a golden node.
	bool unmatched_message = false;
	for (auto i = actual_message_graph_.message_nodes().begin();
	i != actual_message_graph_.message_nodes().end(); i++) {
	for (size_t j = 0; j < i->second.size(); j++) {
	if (!i->second[j]->matching_golden_node()) {
	compare_results_ << "Unmatched actual message " << i->second[j]->message();
	unmatched_message = true;
	}
	}
	}
	for (auto i = golden_message_graph_.message_nodes().begin();
	i != golden_message_graph_.message_nodes().end(); i++) {
	for (size_t j = 0; j < i->second.size(); j++) {
	if (!i->second[j]->has_matching_actual_node()) {
	compare_results_ << "Unmatched golden message " << i->second[j]->message();
	unmatched_message = true;
	}
	}
	}

	// There is no need to check that handles, pids and tids are matched: as all of them have at least
	// one message that depends from them, if all messages are matched, so are they.
	if (!unmatched_message) {
	compare_results_ << "Messages from the current execution matched the golden file.\n";
	}
	}
	} // namespace fidlcat