mirror of https://github.com/djcb/mu.git
935 lines
32 KiB
C++
935 lines
32 KiB
C++
/*
|
|
** Copyright (C) 2021 Dirk-Jan C. Binnema <djcb@djcbsoftware.nl>
|
|
**
|
|
** This program is free software; you can redistribute it and/or modify it
|
|
** under the terms of the GNU General Public License as published by the
|
|
** Free Software Foundation; either version 3, or (at your option) any
|
|
** later version.
|
|
**
|
|
** This program is distributed in the hope that it will be useful,
|
|
** but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
** GNU General Public License for more details.
|
|
**
|
|
** You should have received a copy of the GNU General Public License
|
|
** along with this program; if not, write to the Free Software Foundation,
|
|
** Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
|
**
|
|
*/
|
|
|
|
#include "mu-query-threads.hh"
|
|
#include "mu-msg-fields.h"
|
|
|
|
#include <set>
|
|
#include <unordered_set>
|
|
#include <list>
|
|
#include <cassert>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
#include <iomanip>
|
|
|
|
|
|
#include <utils/mu-option.hh>
|
|
|
|
using namespace Mu;
|
|
|
|
struct Container {
|
|
using Containers = std::vector<Container*>;
|
|
|
|
Container() = default;
|
|
Container(Option<QueryMatch&> msg): query_match{msg} {}
|
|
Container(const Container&) = delete;
|
|
Container(Container&&) = default;
|
|
|
|
void add_child (Container& new_child) {
|
|
new_child.parent = this;
|
|
children.emplace_back(&new_child);
|
|
}
|
|
void remove_child (Container& child) {
|
|
children.erase(find_child(child));
|
|
assert(!has_child(child));
|
|
}
|
|
|
|
Containers::iterator find_child (Container& child) {
|
|
return std::find_if(children.begin(), children.end(),
|
|
[&](auto&& c){ return c == &child; });
|
|
}
|
|
Containers::const_iterator find_child (Container& child) const {
|
|
return std::find_if(children.begin(), children.end(),
|
|
[&](auto&& c){ return c == &child; });
|
|
}
|
|
bool has_child (Container& child) const {
|
|
return find_child(child) != children.cend();
|
|
}
|
|
|
|
bool is_reachable(Container* other) const {
|
|
auto up{ur_parent()};
|
|
return up && up == other->ur_parent();
|
|
}
|
|
template <typename Func> void for_each_child (Func&& func) {
|
|
auto it{children.rbegin()};
|
|
while (it != children.rend()) {
|
|
auto next = std::next(it);
|
|
func(*it);
|
|
it = next;
|
|
}
|
|
}
|
|
// During sorting, this is the cached value for the (recursive) date-key
|
|
// of this container -- ie.. either the one from the first of its
|
|
// children, or from its query-match, if it has no children.
|
|
//
|
|
// Note that the sub-root-levels of threads are always sorted by date,
|
|
// in ascending order, regardless of whatever sorting was specified for
|
|
// the root-level.
|
|
|
|
|
|
std::string thread_date_key;
|
|
|
|
|
|
Option<QueryMatch&> query_match;
|
|
bool is_nuked{};
|
|
Container* parent{};
|
|
Containers children;
|
|
|
|
using ContainerVec = std::vector<Container*>;
|
|
|
|
private:
|
|
const Container* ur_parent() const {
|
|
assert(this->parent != this);
|
|
return parent ? parent->ur_parent() : this;
|
|
}
|
|
};
|
|
|
|
using Containers = Container::Containers;
|
|
using ContainerVec = Container::ContainerVec;
|
|
|
|
static std::ostream&
|
|
operator<<(std::ostream& os, const Container& container)
|
|
{
|
|
os << "container: " << std::right << std::setw(10) << &container
|
|
<< ": parent: " << std::right << std::setw(10) << container.parent
|
|
<< " [" << container.thread_date_key << "]"
|
|
<< "\n children: ";
|
|
|
|
for (auto&& c: container.children)
|
|
os << std::right << std::setw(10) << c << " ";
|
|
|
|
os << (container.is_nuked ? " nuked" : "");
|
|
|
|
if (container.query_match)
|
|
os << "\n " << container.query_match.value();
|
|
|
|
return os;
|
|
}
|
|
|
|
|
|
using IdTable = std::unordered_map<std::string, Container>;
|
|
using DupTable = std::multimap<std::string, Container>;
|
|
|
|
static void
|
|
handle_duplicates (IdTable& id_table, DupTable& dup_table)
|
|
{
|
|
size_t n{};
|
|
|
|
for (auto&& dup: dup_table) {
|
|
const auto msgid{dup.first};
|
|
auto it = id_table.find(msgid);
|
|
if (it == id_table.end())
|
|
continue;
|
|
|
|
// add duplicates as fake children
|
|
char buf[32];
|
|
::snprintf(buf, sizeof(buf), "dup-%zu", ++n);
|
|
it->second.add_child(
|
|
id_table.emplace(buf, std::move(dup.second)).first->second);
|
|
}
|
|
}
|
|
|
|
template <typename QueryResultsType>
|
|
static IdTable
|
|
determine_id_table (QueryResultsType& qres)
|
|
{
|
|
// 1. For each query_match
|
|
IdTable id_table;
|
|
DupTable dups;
|
|
for (auto&& mi: qres) {
|
|
const auto msgid{mi.message_id().value_or(*mi.path())};
|
|
// Step 0 (non-JWZ): filter out dups, handle those at the end
|
|
if (mi.query_match().has_flag(QueryMatch::Flags::Duplicate)) {
|
|
dups.emplace(msgid, mi.query_match());
|
|
continue;
|
|
}
|
|
// 1.A If id_table contains an empty Container for this ID:
|
|
// Store this query_match (query_match) in the Container's query_match (value) slot.
|
|
// Else:
|
|
// Create a new Container object holding this query_match (query-match);
|
|
// Index the Container by Query_Match-ID
|
|
auto c_it = id_table.find(msgid);
|
|
auto& container = [&]()->Container& {
|
|
if (c_it != id_table.end()) {
|
|
if (!c_it->second.query_match) // hmm, dup?
|
|
c_it->second.query_match = mi.query_match();
|
|
return c_it->second;
|
|
} else {
|
|
// Else:
|
|
// Create a new Container object holding this query_match (query-match);
|
|
// Index the Container by Query_Match-ID
|
|
return id_table.emplace(msgid, mi.query_match()).first->second;
|
|
}
|
|
}();
|
|
|
|
// We sort by date (ascending), *except* for the root; we don't
|
|
// know what query_matchs will be at the root level yet, so remember
|
|
// both. Moreover, even when sorting the top-level in descending
|
|
// order, still sort the thread levels below that in ascending
|
|
// order.
|
|
container.thread_date_key = container.query_match->date_key =
|
|
mi.date().value_or("");
|
|
// initial guess for the thread-date; might be updated
|
|
// later.
|
|
|
|
// remember the subject, we use it to determine the (sub)thread subject
|
|
container.query_match->subject = mi.subject().value_or("");
|
|
|
|
// 1.B
|
|
// For each element in the query_match's References field:
|
|
Container* parent_ref_container{};
|
|
for (const auto& ref: mi.references()) {
|
|
// grand_<n>-parent -> grand_<n-1>-parent -> ... -> parent.
|
|
|
|
// Find a Container object for the given Query_Match-ID; If it exists, use it;
|
|
// otherwise make one with a null Query_Match.
|
|
auto ref_container = [&]()->Container* {
|
|
auto ref_it = id_table.find(ref);
|
|
if (ref_it == id_table.end())
|
|
ref_it = id_table.emplace(ref,Nothing).first;
|
|
return &ref_it->second;
|
|
}();
|
|
|
|
// Link the References field's Containers together in the order implied
|
|
// by the References header.
|
|
// * If they are already linked, don't change the existing links.
|
|
//
|
|
// * Do not add a link if adding that link would introduce a loop: that is,
|
|
// before asserting A->B, search down the children of B to see if A is
|
|
// reachable, and also search down the children of A to see if B is
|
|
// reachable. If either is already reachable as a child of the other,
|
|
// don't add the link.
|
|
if (parent_ref_container && !ref_container->parent) {
|
|
if (!parent_ref_container->is_reachable(ref_container))
|
|
parent_ref_container->add_child(*ref_container);
|
|
// else
|
|
// g_message ("%u: reachable %s -> %s", __LINE__, msgid.c_str(), ref.c_str());
|
|
}
|
|
|
|
parent_ref_container = ref_container;
|
|
}
|
|
|
|
// Add the query_match to the chain.
|
|
if (parent_ref_container && !container.parent) {
|
|
if (!parent_ref_container->is_reachable(&container))
|
|
parent_ref_container->add_child(container);
|
|
// else
|
|
// g_message ("%u: reachable %s -> parent", __LINE__, msgid.c_str());
|
|
}
|
|
}
|
|
|
|
// non-JWZ: add duplicate messages.
|
|
handle_duplicates (id_table, dups);
|
|
|
|
return id_table;
|
|
}
|
|
|
|
/// Recursively walk all containers under the root set.
|
|
/// For each container:
|
|
///
|
|
/// If it is an empty container with no children, nuke it.
|
|
///
|
|
/// Note: Normally such containers won't occur, but they can show up when two
|
|
/// query_matchs have References lines that disagree. For example, assuming A and
|
|
/// B are query_matchs, and 1, 2, and 3 are references for query_matchs we haven't
|
|
/// seen:
|
|
///
|
|
/// A has references: 1, 2, 3
|
|
/// B has references: 1, 3
|
|
///
|
|
/// There is ambiguity as to whether 3 is a child of 1 or of 2. So,
|
|
/// depending on the processing order, we might end up with either
|
|
///
|
|
/// -- 1
|
|
/// |-- 2
|
|
/// \-- 3
|
|
/// |-- A
|
|
/// \-- B
|
|
///
|
|
/// or
|
|
///
|
|
/// -- 1
|
|
/// |-- 2 <--- non root childless container!
|
|
/// \-- 3
|
|
/// |-- A
|
|
/// \-- B
|
|
///
|
|
/// If the Container has no Query_Match, but does have children, remove this
|
|
/// container but promote its children to this level (that is, splice them in
|
|
/// to the current child list.)
|
|
///
|
|
/// Do not promote the children if doing so would promote them to the root
|
|
/// set -- unless there is only one child, in which case, do.
|
|
|
|
static void
|
|
prune (Container* child)
|
|
{
|
|
Container *container{child->parent};
|
|
|
|
for (auto& grandchild: child->children) {
|
|
grandchild->parent = container;
|
|
if (container)
|
|
container->children.emplace_back(grandchild);
|
|
}
|
|
|
|
child->children.clear();
|
|
child->is_nuked = true;
|
|
|
|
if (container)
|
|
container->remove_child(*child);
|
|
}
|
|
|
|
|
|
static bool
|
|
prune_empty_containers (Container& container)
|
|
{
|
|
Containers to_prune;
|
|
|
|
container.for_each_child([&](auto& child){
|
|
if (prune_empty_containers(*child))
|
|
to_prune.emplace_back(child);
|
|
});
|
|
|
|
for (auto& child: to_prune)
|
|
prune (child);
|
|
|
|
// Never nuke these.
|
|
if (container.query_match)
|
|
return false;
|
|
|
|
// If it is an empty container with no children, nuke it.
|
|
//
|
|
// If the Container is empty, but does have children, remove this
|
|
// container but promote its children to this level (that is, splice them in
|
|
// to the current child list.)
|
|
//
|
|
// Do not promote the children if doing so would promote them to the root
|
|
// set -- unless there is only one child, in which case, do.
|
|
//const auto rootset_child{!container.parent->parent};
|
|
if (container.parent || container.children.size() <= 1)
|
|
return true; // splice/nuke it.
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
static void
|
|
prune_empty_containers (IdTable& id_table)
|
|
{
|
|
for (auto&& item: id_table) {
|
|
|
|
auto& child(item.second);
|
|
if (child.parent)
|
|
continue; // not a root child.
|
|
|
|
if (prune_empty_containers(item.second))
|
|
prune(&child);
|
|
}
|
|
}
|
|
|
|
//
|
|
// Sorting.
|
|
//
|
|
|
|
|
|
/// Register some information about a match (i.e., message) that we can use for
|
|
/// subsequent queries.
|
|
using ThreadPath = std::vector<unsigned>;
|
|
inline std::string
|
|
to_string (const ThreadPath& tpath, size_t digits)
|
|
{
|
|
std::string str;
|
|
str.reserve(tpath.size() * digits);
|
|
|
|
bool first{true};
|
|
for (auto&& segm: tpath) {
|
|
str += format("%s%0*x", first ? "" : ":", (int)digits, segm);
|
|
first = false;
|
|
}
|
|
|
|
return str;
|
|
}
|
|
|
|
|
|
static bool
|
|
update_container (Container& container, bool descending,
|
|
ThreadPath& tpath, size_t seg_size,
|
|
const std::string& prev_subject="")
|
|
{
|
|
if (!container.children.empty()) {
|
|
Container* first = container.children.front();
|
|
if (first->query_match)
|
|
first->query_match->flags |= QueryMatch::Flags::First;
|
|
Container* last = container.children.back();
|
|
if (last->query_match)
|
|
last->query_match->flags |= QueryMatch::Flags::Last;
|
|
}
|
|
|
|
if (!container.query_match)
|
|
return false; // nothing else to do.
|
|
|
|
auto& qmatch(*container.query_match);
|
|
|
|
if (!container.parent)
|
|
qmatch.flags |= QueryMatch::Flags::Root;
|
|
else if (!container.parent->query_match)
|
|
qmatch.flags |= QueryMatch::Flags::Orphan;
|
|
|
|
if (!container.children.empty())
|
|
qmatch.flags |= QueryMatch::Flags::HasChild;
|
|
|
|
// see whether this message has the has the thread
|
|
// subject, ie.. the first message in this thread with the
|
|
// given subject.
|
|
if (qmatch.has_flag(QueryMatch::Flags::Root) ||
|
|
//qmatch.has_flag(QueryMatch::Flags::Orphan) ||
|
|
prev_subject.empty() ||
|
|
(qmatch.subject.find(prev_subject) > 5))
|
|
qmatch.flags |= QueryMatch::Flags::ThreadSubject;
|
|
|
|
// g_debug ("%c%c: '%s' vs '%s'",
|
|
// any_of(qmatch.flags & QueryMatch::Flags::Root) ? 'r' : 'c',
|
|
// any_of(qmatch.flags & QueryMatch::Flags::ThreadSubject) ? 'y' : 'n',
|
|
// qmatch.subject.c_str(),
|
|
// prev_subject.c_str());
|
|
|
|
if (descending && container.parent) {
|
|
// trick xapian by giving it "inverse" sorting key so our
|
|
// ascending-date sorted threads stay in that order
|
|
tpath.back() = ((1U << (4 * seg_size)) - 1) - tpath.back();
|
|
}
|
|
|
|
qmatch.thread_path = to_string(tpath, seg_size);
|
|
qmatch.thread_level = tpath.size() - 1;
|
|
|
|
// ensure thread root comes before its children
|
|
if (descending)
|
|
qmatch.thread_path += ":z";
|
|
|
|
return true;
|
|
}
|
|
|
|
|
|
static void
|
|
update_containers (Containers& children, bool descending, ThreadPath& tpath,
|
|
size_t seg_size)
|
|
{
|
|
size_t idx{0};
|
|
std::string last_subject;
|
|
|
|
for (auto&& c: children) {
|
|
tpath.emplace_back(idx++);
|
|
|
|
if (c->query_match) {
|
|
update_container(*c, descending, tpath, seg_size,
|
|
last_subject);
|
|
last_subject = c->query_match->subject;
|
|
}
|
|
update_containers(c->children, descending, tpath, seg_size);
|
|
tpath.pop_back();
|
|
}
|
|
}
|
|
|
|
static void
|
|
update_containers (ContainerVec& root_vec, bool descending, size_t n)
|
|
{
|
|
ThreadPath tpath;
|
|
tpath.reserve (n);
|
|
|
|
const auto seg_size = static_cast<size_t>(std::ceil(std::log2(n)/4.0));
|
|
/*note: 4 == std::log2(16)*/
|
|
|
|
size_t idx{0};
|
|
for (auto&& c: root_vec) {
|
|
tpath.emplace_back(idx++);
|
|
update_container(*c, descending, tpath, seg_size);
|
|
update_containers(c->children, descending, tpath, seg_size);
|
|
tpath.pop_back();
|
|
}
|
|
}
|
|
|
|
|
|
static void
|
|
sort_container (Container& container)
|
|
{
|
|
// 1. childless container.
|
|
if (container.children.empty())
|
|
return; // no children; nothing to sort.
|
|
|
|
// 2. container with children.
|
|
// recurse, depth-first: sort the children
|
|
for (auto& child: container.children)
|
|
sort_container(*child);
|
|
|
|
// now sort this level.
|
|
std::sort(container.children.begin(), container.children.end(),
|
|
[&](auto&& c1, auto&& c2) {
|
|
return c1->thread_date_key < c2->thread_date_key;
|
|
});
|
|
|
|
// and 'bubble up' the date of the *newest* message with a date. We
|
|
// reasonably assume that it's later than its parent.
|
|
const auto& newest_date = container.children.back()->thread_date_key;
|
|
if (!newest_date.empty())
|
|
container.thread_date_key = newest_date;
|
|
}
|
|
|
|
|
|
static void
|
|
sort_siblings (IdTable& id_table, bool descending)
|
|
{
|
|
if (id_table.empty())
|
|
return;
|
|
|
|
// unsorted vec of root containers. We can
|
|
// only sort these _after_ sorting the children.
|
|
ContainerVec root_vec;
|
|
for (auto&& item: id_table) {
|
|
if (!item.second.parent && !item.second.is_nuked)
|
|
root_vec.emplace_back(&item.second);
|
|
}
|
|
|
|
// now sort all threads _under_ the root set (by date/ascending)
|
|
for (auto&& c: root_vec)
|
|
sort_container(*c);
|
|
|
|
// and then sort the root set.
|
|
//
|
|
// The difference with the sub-root containers is that at the top-level,
|
|
// we can sort either in ascending or descending order, while on the
|
|
// subroot level it's always in ascending order.
|
|
//
|
|
// Note that unless we're testing, _xapian_ will handle
|
|
// the ascending/descending of the top level.
|
|
std::sort(root_vec.begin(), root_vec.end(), [&](auto&& c1, auto&& c2) {
|
|
#ifdef BUILD_TESTS
|
|
if (descending)
|
|
return c2->thread_date_key < c1->thread_date_key;
|
|
else
|
|
#endif /*BUILD_TESTS*/
|
|
return c1->thread_date_key < c2->thread_date_key;
|
|
});
|
|
|
|
// now all is sorted... final step is to determine thread paths and
|
|
// other flags.
|
|
update_containers (root_vec, descending, id_table.size());
|
|
}
|
|
|
|
static std::ostream&
|
|
operator<<(std::ostream& os, const IdTable& id_table)
|
|
{
|
|
os << "------------------------------------------------\n";
|
|
for (auto&& item: id_table) {
|
|
os << item.first << " => " << item.second << "\n";
|
|
}
|
|
os << "------------------------------------------------\n";
|
|
|
|
std::set<std::string> ids;
|
|
for (auto&& item: id_table) {
|
|
if (item.second.query_match)
|
|
ids.emplace(item.second.query_match->thread_path);
|
|
}
|
|
|
|
for (auto&& id: ids) {
|
|
auto it = std::find_if(id_table.begin(), id_table.end(), [&](auto&& item) {
|
|
return item.second.query_match &&
|
|
item.second.query_match->thread_path == id;
|
|
});
|
|
assert(it != id_table.end());
|
|
os << it->first << ": " << it->second << '\n';
|
|
}
|
|
return os;
|
|
}
|
|
|
|
|
|
template<typename Results> static void
|
|
calculate_threads_real (Results& qres, bool descending)
|
|
{
|
|
// Step 1: build the id_table
|
|
auto id_table{determine_id_table(qres)};
|
|
|
|
if (g_test_verbose())
|
|
std::cout << "*** id-table(1):\n" << id_table << "\n";
|
|
|
|
// // Step 2: get the root set
|
|
// // Step 3: discard id_table
|
|
// Nope: id-table owns the containers.
|
|
// Step 4: prune empty containers
|
|
prune_empty_containers(id_table);
|
|
|
|
// Step 5: group root-set by subject.
|
|
// Not implemented.
|
|
|
|
// Step 6: we're done threading
|
|
|
|
// Step 7: sort siblings. The segment-size is the number of hex-digits
|
|
// in the thread-path string (so we can lexically compare them.)
|
|
sort_siblings(id_table, descending);
|
|
|
|
// Step 7a:. update querymatches
|
|
for (auto&& item: id_table) {
|
|
Container& c{item.second};
|
|
if (c.query_match)
|
|
c.query_match->thread_date = c.thread_date_key;
|
|
}
|
|
// if (g_test_verbose())
|
|
// std::cout << "*** id-table(2):\n" << id_table << "\n";
|
|
}
|
|
|
|
void
|
|
Mu::calculate_threads (Mu::QueryResults& qres, bool descending)
|
|
{
|
|
calculate_threads_real(qres, descending);
|
|
}
|
|
|
|
#ifdef BUILD_TESTS
|
|
|
|
struct MockQueryResult {
|
|
MockQueryResult(const std::string& message_id_arg,
|
|
const std::string& date_arg,
|
|
const std::vector<std::string>& refs_arg={}):
|
|
message_id_{message_id_arg},
|
|
date_{date_arg},
|
|
refs_{refs_arg}
|
|
{}
|
|
MockQueryResult(const std::string& message_id_arg,
|
|
const std::vector<std::string>& refs_arg={}):
|
|
MockQueryResult(message_id_arg, "", refs_arg) {}
|
|
Option<std::string> message_id() const { return message_id_;}
|
|
Option<std::string> path() const { return path_;}
|
|
Option<std::string> date() const { return date_;}
|
|
Option<std::string> subject() const { return subject_;}
|
|
QueryMatch& query_match() { return query_match_;}
|
|
const QueryMatch& query_match() const { return query_match_;}
|
|
const std::vector<std::string>& references() const { return refs_;}
|
|
|
|
std::string path_;
|
|
std::string message_id_;
|
|
QueryMatch query_match_{};
|
|
std::string date_;
|
|
std::string subject_;
|
|
std::vector<std::string> refs_;
|
|
};
|
|
|
|
using MockQueryResults = std::vector<MockQueryResult>;
|
|
|
|
|
|
G_GNUC_UNUSED static std::ostream&
|
|
operator<<(std::ostream& os, const MockQueryResults& qrs)
|
|
{
|
|
for (auto&& mi: qrs)
|
|
os << mi.query_match().thread_path << " :: "
|
|
<< mi.message_id().value_or("<none>") << std::endl;
|
|
|
|
return os;
|
|
}
|
|
|
|
static void
|
|
calculate_threads (MockQueryResults& qres, bool descending)
|
|
{
|
|
calculate_threads_real(qres, descending);
|
|
}
|
|
|
|
using Expected = std::vector<std::pair<std::string, std::string>>;
|
|
|
|
|
|
static void
|
|
assert_thread_paths (const MockQueryResults& qrs, const Expected& expected)
|
|
{
|
|
for (auto&& exp: expected) {
|
|
auto it = std::find_if(qrs.begin(), qrs.end(), [&](auto&& qr){
|
|
return qr.message_id().value_or("") == exp.first ||
|
|
qr.path().value_or("") == exp.first;
|
|
});
|
|
g_assert_true (it != qrs.end());
|
|
g_assert_cmpstr(exp.second.c_str(), ==,
|
|
it->query_match().thread_path.c_str());
|
|
}
|
|
}
|
|
|
|
static void
|
|
test_sort_ascending()
|
|
{
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "1", {"m2"} },
|
|
MockQueryResult{ "m2", "2", {"m3"} },
|
|
MockQueryResult{ "m3", "3", {}},
|
|
MockQueryResult{ "m4", "4", {}}
|
|
};
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m1", "0:0:0"},
|
|
{ "m2", "0:0" },
|
|
{ "m3", "0" },
|
|
{ "m4", "1" }
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_sort_descending()
|
|
{
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "1", {"m2"} },
|
|
MockQueryResult{ "m2", "2", {"m3"} },
|
|
MockQueryResult{ "m3", "3", {}},
|
|
MockQueryResult{ "m4", "4", {}}
|
|
};
|
|
|
|
calculate_threads(results, true);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m1", "1:f:f:z"},
|
|
{ "m2", "1:f:z" },
|
|
{ "m3", "1:z" },
|
|
{ "m4", "0:z" }
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_id_table_inconsistent()
|
|
{
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "1", {"m2"} }, // 1->2
|
|
MockQueryResult{ "m2", "2", {"m1"} }, // 2->1
|
|
MockQueryResult{ "m3", "3", {"m3"} }, // self ref
|
|
MockQueryResult{ "m4", "4", {"m3", "m5"} },
|
|
MockQueryResult{ "m5", "5", {"m4", "m4"} }, // dup parent
|
|
};
|
|
|
|
calculate_threads(results, false);
|
|
assert_thread_paths (results, {
|
|
{ "m2", "0"},
|
|
{ "m1", "0:0"},
|
|
{ "m3", "1"},
|
|
{ "m5", "1:0"},
|
|
{ "m4", "1:0:0"},
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_dups_dup_last()
|
|
{
|
|
MockQueryResult r1 { "m1", "1", {} };
|
|
r1.query_match().flags |= QueryMatch::Flags::Leader;
|
|
r1.path_ = "/path1";
|
|
|
|
MockQueryResult r1_dup { "m1", "1", {} };
|
|
r1_dup.query_match().flags |= QueryMatch::Flags::Duplicate;
|
|
r1_dup.path_ = "/path2";
|
|
|
|
auto results = MockQueryResults {r1, r1_dup };
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "/path1", "0"},
|
|
{ "/path2", "0:0" },
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_dups_dup_first()
|
|
{
|
|
// now dup becomes the leader; this will _demote_
|
|
// r1.
|
|
|
|
MockQueryResult r1_dup { "m1", "1", {} };
|
|
r1_dup.query_match().flags |= QueryMatch::Flags::Duplicate;
|
|
r1_dup.path_ = "/path1";
|
|
|
|
MockQueryResult r1 { "m1", "1", {} };
|
|
r1.query_match().flags |= QueryMatch::Flags::Leader;
|
|
r1.path_ = "/path2";
|
|
|
|
auto results = MockQueryResults { r1_dup, r1 };
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "/path2", "0"},
|
|
{ "/path1", "0:0" },
|
|
});
|
|
}
|
|
|
|
|
|
static void
|
|
test_do_not_prune_root_empty_with_children()
|
|
{
|
|
// m7 should not be nuked
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "x1", "1", {"m7"} },
|
|
MockQueryResult{ "x2", "2", {"m7"} },
|
|
};
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "x1", "0:0"},
|
|
{ "x2", "0:1" },
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_prune_root_empty_with_child()
|
|
{
|
|
// m7 should be nuked
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "1", {"m7"} },
|
|
};
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m1", "0"},
|
|
});
|
|
}
|
|
|
|
static void
|
|
test_prune_empty_with_children()
|
|
{
|
|
// m6 should be nuked
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "1", {"m7", "m6"} },
|
|
MockQueryResult{ "m2", "2", {"m7", "m6"} },
|
|
};
|
|
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m1", "0:0"},
|
|
{ "m2", "0:1" },
|
|
});
|
|
}
|
|
|
|
|
|
static void
|
|
test_thread_info_ascending()
|
|
{
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "5", {}},
|
|
MockQueryResult{ "m2", "1", {}},
|
|
MockQueryResult{ "m3", "3", {"m2"}},
|
|
MockQueryResult{ "m4", "2", {"m2"}},
|
|
// orphan siblings
|
|
MockQueryResult{ "m10", "6", {"m9"}},
|
|
MockQueryResult{ "m11", "7", {"m9"}},
|
|
};
|
|
calculate_threads(results, false);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m2", "0" }, // 2
|
|
{ "m4", "0:0" }, // 2
|
|
{ "m3", "0:1" }, // 3
|
|
{ "m1", "1" }, // 5
|
|
|
|
{ "m10", "2:0" }, // 6
|
|
{ "m11", "2:1" }, // 7
|
|
});
|
|
|
|
g_assert_true (results[0].query_match().has_flag(
|
|
QueryMatch::Flags::Root));
|
|
g_assert_true (results[1].query_match().has_flag(
|
|
QueryMatch::Flags::Root | QueryMatch::Flags::HasChild));
|
|
g_assert_true (results[2].query_match().has_flag(
|
|
QueryMatch::Flags::Last));
|
|
g_assert_true (results[3].query_match().has_flag(
|
|
QueryMatch::Flags::First));
|
|
g_assert_true (results[4].query_match().has_flag(
|
|
QueryMatch::Flags::Orphan | QueryMatch::Flags::First));
|
|
g_assert_true (results[5].query_match().has_flag(
|
|
QueryMatch::Flags::Orphan | QueryMatch::Flags::Last));
|
|
}
|
|
|
|
static void
|
|
test_thread_info_descending()
|
|
{
|
|
auto results = MockQueryResults {
|
|
MockQueryResult{ "m1", "5", {}},
|
|
MockQueryResult{ "m2", "1", {}},
|
|
MockQueryResult{ "m3", "3", {"m2"}},
|
|
MockQueryResult{ "m4", "2", {"m2"}},
|
|
// orphan siblings
|
|
MockQueryResult{ "m10", "6", {"m9"}},
|
|
MockQueryResult{ "m11", "7", {"m9"}},
|
|
};
|
|
calculate_threads(results, true/*descending*/);
|
|
|
|
assert_thread_paths (results, {
|
|
{ "m1", "1:z" }, // 5
|
|
{ "m2", "2:z" }, // 2
|
|
{ "m4", "2:f:z" }, // 2
|
|
{ "m3", "2:e:z" }, // 3
|
|
|
|
{ "m10", "0:f:z" }, // 6
|
|
{ "m11", "0:e:z" }, // 7
|
|
});
|
|
g_assert_true (results[0].query_match().has_flag(
|
|
QueryMatch::Flags::Root));
|
|
g_assert_true (results[1].query_match().has_flag(
|
|
QueryMatch::Flags::Root | QueryMatch::Flags::HasChild));
|
|
g_assert_true (results[2].query_match().has_flag(
|
|
QueryMatch::Flags::Last));
|
|
g_assert_true (results[3].query_match().has_flag(
|
|
QueryMatch::Flags::First));
|
|
|
|
g_assert_true (results[4].query_match().has_flag(
|
|
QueryMatch::Flags::Orphan | QueryMatch::Flags::Last));
|
|
g_assert_true (results[5].query_match().has_flag(
|
|
QueryMatch::Flags::Orphan | QueryMatch::Flags::First));
|
|
|
|
}
|
|
|
|
|
|
int
|
|
main (int argc, char *argv[]) try
|
|
{
|
|
g_test_init (&argc, &argv, NULL);
|
|
|
|
g_test_add_func ("/threader/sort/ascending", test_sort_ascending);
|
|
g_test_add_func ("/threader/sort/decending", test_sort_descending);
|
|
|
|
g_test_add_func ("/threader/id-table-inconsistent", test_id_table_inconsistent);
|
|
g_test_add_func ("/threader/dups/dup-last", test_dups_dup_last);
|
|
g_test_add_func ("/threader/dups/dup-first", test_dups_dup_first);
|
|
|
|
g_test_add_func ("/threader/prune/do-not-prune-root-empty-with-children",
|
|
test_do_not_prune_root_empty_with_children);
|
|
g_test_add_func ("/threader/prune/prune-root-empty-with-child",
|
|
test_prune_root_empty_with_child);
|
|
g_test_add_func ("/threader/prune/prune-empty-with-children",
|
|
test_prune_empty_with_children);
|
|
|
|
g_test_add_func ("/threader/thread-info/ascending",
|
|
test_thread_info_ascending);
|
|
g_test_add_func ("/threader/thread-info/descending",
|
|
test_thread_info_descending);
|
|
|
|
return g_test_run ();
|
|
} catch (const std::runtime_error& re) {
|
|
std::cerr << re.what() << "\n";
|
|
return 1;
|
|
} catch (...) {
|
|
std::cerr << "caught exception\n";
|
|
return 1;
|
|
}
|
|
|
|
#endif /*BUILD_TESTS*/
|