diff options
Diffstat (limited to 'indra/llcommon/tests/lldependencies_test.cpp')
| -rw-r--r-- | indra/llcommon/tests/lldependencies_test.cpp | 275 |
1 files changed, 275 insertions, 0 deletions
diff --git a/indra/llcommon/tests/lldependencies_test.cpp b/indra/llcommon/tests/lldependencies_test.cpp new file mode 100644 index 0000000000..f3c25de8b5 --- /dev/null +++ b/indra/llcommon/tests/lldependencies_test.cpp @@ -0,0 +1,275 @@ +/** + * @file lldependencies_tut.cpp + * @author Nat Goodspeed + * @date 2008-09-17 + * @brief Test of lldependencies.h + * + * $LicenseInfo:firstyear=2008&license=viewergpl$ + * Copyright (c) 2008, Linden Research, Inc. + * $/LicenseInfo$ + */ + +// STL headers +#include <iostream> +#include <string> +// std headers +// external library headers +#include <boost/assign/list_of.hpp> +// Precompiled header +#include "linden_common.h" +// associated header +#include "../lldependencies.h" +// other Linden headers +#include "../test/lltut.h" + +using boost::assign::list_of; + +#if LL_WINDOWS +#pragma warning (disable : 4675) // "resolved by ADL" -- just as I want! +#endif + +typedef LLDependencies<> StringDeps; +typedef StringDeps::KeyList StringList; + +// We use the very cool boost::assign::list_of() construct to specify vectors +// of strings inline. For reasons on which I'm not entirely clear, though, it +// needs a helper function. You can use list_of() to construct an implicit +// StringList (std::vector<std::string>) by conversion, e.g. for a function +// parameter -- but if you simply write StringList(list_of("etc.")), you get +// ambiguity errors. Shrug! +template<typename CONTAINER> +CONTAINER make(const CONTAINER& data) +{ + return data; +} + +// Display an arbitary value as itself... +template<typename T> +std::ostream& display(std::ostream& out, const T& value) +{ + out << value; + return out; +} + +// ...but display std::string enclosed in double quotes. +template<> +std::ostream& display(std::ostream& out, const std::string& value) +{ + out << '"' << value << '"'; + return out; +} + +// display any sequence compatible with Boost.Range +template<typename SEQUENCE> +std::ostream& display_seq(std::ostream& out, + const std::string& open, const SEQUENCE& seq, const std::string& close) +{ + out << open; + typename boost::range_const_iterator<SEQUENCE>::type + sli = boost::begin(seq), + slend = boost::end(seq); + if (sli != slend) + { + display(out, *sli); + while (++sli != slend) + { + out << ", "; + display(out, *sli); + } + } + out << close; + return out; +} + +// helper to dump a StringList to std::cout if needed +template<typename ENTRY> +std::ostream& operator<<(std::ostream& out, const std::vector<ENTRY>& list) +{ + display_seq(out, "(", list, ")"); + return out; +} + +template<typename ENTRY> +std::ostream& operator<<(std::ostream& out, const std::set<ENTRY>& set) +{ + display_seq(out, "{", set, "}"); + return out; +} + +const std::string& extract_key(const LLDependencies<>::value_type& entry) +{ + return entry.first; +} + +// helper to return a StringList of keys from LLDependencies::sort() +StringList sorted_keys(LLDependencies<>& deps) +{ + // 1. Call deps.sort(), returning a value_type range of (key, node) pairs. + // 2. Use make_transform_range() to obtain a range of just keys. + // 3. Use instance_from_range to instantiate a StringList from that range. + // 4. Return by value "slices" instance_from_range<StringList> (a subclass + // of StringList) to its base class StringList. + return instance_from_range<StringList>(make_transform_range(deps.sort(), extract_key)); +} + +template<typename RANGE> +bool is_empty(const RANGE& range) +{ + return boost::begin(range) == boost::end(range); +} + +/***************************************************************************** +* tut test group +*****************************************************************************/ +namespace tut +{ + struct deps_data + { + }; + typedef test_group<deps_data> deps_group; + typedef deps_group::object deps_object; + tut::deps_group depsgr("lldependencies"); + + template<> template<> + void deps_object::test<1>() + { + StringDeps deps; + StringList empty; + // The quick brown fox jumps over the lazy yellow dog. + // (note, "The" and "the" are distinct, else this test wouldn't work) + deps.add("lazy"); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy"))); + deps.add("jumps"); + ensure("found lazy", deps.get("lazy")); + ensure("not found dog.", ! deps.get("dog.")); + // NOTE: Maybe it's overkill to test each of these intermediate + // results before all the interdependencies have been specified. My + // thought is simply that if the order changes, I'd like to know why. + // A change to the implementation of boost::topological_sort() would + // be an acceptable reason, and you can simply update the expected + // test output. + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("jumps"))); + deps.add("The", 0, empty, list_of("fox")("dog.")); + // Test key accessors + ensure("empty before deps for missing key", is_empty(deps.get_before_range("bogus"))); + ensure("empty before deps for jumps", is_empty(deps.get_before_range("jumps"))); + ensure_equals(instance_from_range< std::set<std::string> >(deps.get_before_range("The")), + make< std::set<std::string> >(list_of("dog.")("fox"))); + // resume building dependencies + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("jumps")("The"))); + deps.add("the", 0, list_of("The")); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("jumps")("The")("the"))); + deps.add("fox", 0, list_of("The"), list_of("jumps")); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("the")("fox")("jumps"))); + deps.add("the", 0, list_of("The")); // same, see if cache works + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("the")("fox")("jumps"))); + deps.add("jumps", 0, empty, list_of("over")); // update jumps deps + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("the")("fox")("jumps"))); +/*==========================================================================*| + // It drives me nuts that this test doesn't work in the test + // framework, because -- for reasons unknown -- running the test + // framework on Mac OS X 10.5 Leopard and Windows XP Pro, the catch + // clause below doesn't catch the exception. Something about the TUT + // test framework?!? The identical code works fine in a standalone + // test program. Commenting out the test for now, in hopes that our + // real builds will be able to catch Cycle exceptions... + try + { + // We've already specified fox -> jumps and jumps -> over. Try an + // impossible constraint. + deps.add("over", 0, empty, list_of("fox")); + } + catch (const StringDeps::Cycle& e) + { + std::cout << "Cycle detected: " << e.what() << '\n'; + // It's legal to add() an impossible constraint because we don't + // detect the cycle until sort(). So sort() can't know the minimum set + // of nodes to remove to make the StringDeps object valid again. + // Therefore we must break the cycle by hand. + deps.remove("over"); + } +|*==========================================================================*/ + deps.add("dog.", 0, list_of("yellow")("lazy")); + ensure_equals(instance_from_range< std::set<std::string> >(deps.get_after_range("dog.")), + make< std::set<std::string> >(list_of("lazy")("yellow"))); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("the")("fox")("jumps")("dog."))); + deps.add("quick", 0, list_of("The"), list_of("fox")("brown")); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("the")("quick")("fox")("jumps")("dog."))); + deps.add("over", 0, list_of("jumps"), list_of("yellow")("the")); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("lazy")("The")("quick")("fox")("jumps")("over")("the")("dog."))); + deps.add("yellow", 0, list_of("the"), list_of("lazy")); + ensure_equals(sorted_keys(deps), make<StringList>(list_of("The")("quick")("fox")("jumps")("over")("the")("yellow")("lazy")("dog."))); + deps.add("brown"); + // By now the dependencies are pretty well in place. A change to THIS + // order should be viewed with suspicion. + ensure_equals(sorted_keys(deps), make<StringList>(list_of("The")("quick")("brown")("fox")("jumps")("over")("the")("yellow")("lazy")("dog."))); + + StringList keys(make<StringList>(list_of("The")("brown")("dog.")("fox")("jumps")("lazy")("over")("quick")("the")("yellow"))); + ensure_equals(instance_from_range<StringList>(deps.get_key_range()), keys); +#if (! defined(__GNUC__)) || (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ > 3) + // This is the succinct way, works on modern compilers + ensure_equals(instance_from_range<StringList>(make_transform_range(deps.get_range(), extract_key)), keys); +#else // gcc 3.3 + StringDeps::range got_range(deps.get_range()); + StringDeps::iterator kni = got_range.begin(), knend = got_range.end(); + StringList::iterator ki = keys.begin(), kend = keys.end(); + for ( ; kni != knend && ki != kend; ++kni, ++ki) + { + ensure_equals(kni->first, *ki); + } + ensure("get_range() returns proper length", kni == knend && ki == kend); +#endif // gcc 3.3 + // blow off get_node_range() because they're all LLDependenciesEmpty instances + } + + template<> template<> + void deps_object::test<2>() + { + typedef LLDependencies<std::string, int> NameIndexDeps; + NameIndexDeps nideps; + const NameIndexDeps& const_nideps(nideps); + nideps.add("def", 2, list_of("ghi")); + nideps.add("ghi", 3); + nideps.add("abc", 1, list_of("def")); + NameIndexDeps::range range(nideps.get_range()); + ensure_equals(range.begin()->first, "abc"); + ensure_equals(range.begin()->second, 1); + range.begin()->second = 0; + range.begin()->second = 1; + NameIndexDeps::const_range const_range(const_nideps.get_range()); + NameIndexDeps::const_iterator const_iterator(const_range.begin()); + ++const_iterator; + ensure_equals(const_iterator->first, "def"); + ensure_equals(const_iterator->second, 2); + NameIndexDeps::node_range node_range(nideps.get_node_range()); + ensure_equals(instance_from_range<std::vector<int> >(node_range), make< std::vector<int> >(list_of(1)(2)(3))); + *node_range.begin() = 0; + *node_range.begin() = 1; + NameIndexDeps::const_node_range const_node_range(const_nideps.get_node_range()); + ensure_equals(instance_from_range<std::vector<int> >(const_node_range), make< std::vector<int> >(list_of(1)(2)(3))); + NameIndexDeps::const_key_range const_key_range(const_nideps.get_key_range()); + ensure_equals(instance_from_range<StringList>(const_key_range), make<StringList>(list_of("abc")("def")("ghi"))); + NameIndexDeps::sorted_range sorted(const_nideps.sort()); + NameIndexDeps::sorted_iterator sortiter(sorted.begin()); + ensure_equals(sortiter->first, "ghi"); + ensure_equals(sortiter->second, 3); + + // test all iterator-flavored versions of get_after_range() + StringList def(make<StringList>(list_of("def"))); + ensure("empty abc before list", is_empty(nideps.get_before_range(nideps.get_range().begin()))); + ensure_equals(instance_from_range<StringList>(nideps.get_after_range(nideps.get_range().begin())), + def); + ensure_equals(instance_from_range<StringList>(const_nideps.get_after_range(const_nideps.get_range().begin())), + def); + ensure_equals(instance_from_range<StringList>(nideps.get_after_range(nideps.get_node_range().begin())), + def); + ensure_equals(instance_from_range<StringList>(const_nideps.get_after_range(const_nideps.get_node_range().begin())), + def); + ensure_equals(instance_from_range<StringList>(nideps.get_after_range(nideps.get_key_range().begin())), + def); + // advance from "ghi" to "def", which must come after "ghi" + ++sortiter; + ensure_equals(instance_from_range<StringList>(const_nideps.get_after_range(sortiter)), + make<StringList>(list_of("ghi"))); + } +} // namespace tut |