对数据结构的内部状态进行单元测试

Question

我有一个任务，需要为大量度量数据结构创建实现（即quadtree和k-d tree变体）。我已经完成了其中的四个实现，但我目前的测试方法不好。

我需要一种干净的方式来测试这些树/trie结构的数据插入和删除，以便我可以测试节点的内部结构（检查父节点、子节点、排序等）。这些实现遵循单独的正确性证明和运行时分析，因此我需要确保不仅一个节点被正确地插入（即从树中检索出来），而且在树中处于非常“正确”的位置。

“单元测试”似乎不是正确的方法，因为它的目的，如果我没有弄错的话，是测试结构或系统的外部API。我看到了很多与单元测试相关的问题，例如“如何在单元测试中访问私有字段”或“如何测试非公共方法的返回值”，答案通常是“不要”，我同意这个答案。

因此，为了不让任何愿意帮助的人感到困惑，我的树实现的接口如下（基于Java集合的Map接口）：

public interface SpatialMap<K, V> extends Iterable<SpatialMap.Entry<K, V>>
{
// Query Operations

/**
 * Returns the number of key-value mappings in this map. If the map contains more than
 * <tt>Integer.MAX_VALUE</tt> elements, returns <tt>Integer.MAX_VALUE</tt>.
 * 
 * @return The number of key-value mappings in this map.
 */
int size();

/**
 * Returns <tt>true</tt> if this map contains no key-value mappings.
 * 
 * @return <tt>true</tt> if this map contains no key-value mappings.
 */
boolean isEmpty();

/**
 * Returns <tt>true</tt> if this map contains a mapping for the specified key.
 * 
 * @param key
 *            The key whose presence in this map is to be tested.
 * @return <tt>true</tt> if this map contains a mapping for the specified key.
 */
boolean containsKey(K key);

/**
 * Returns the value to which the specified key is mapped, or {@code null} if this map contains
 * no mapping for the key.
 * 
 * <p>A return value of {@code null} does not <i>necessarily</i> indicate that the map contains
 * no mapping for the key; it's also possible that the map explicitly maps the key to
 * {@code null}. The {@link #containsKey containsKey} operation may be used to distinguish these
 * two cases.
 * 
 * @see #put(Comparable, Comparable, Object)
 * 
 * @param key
 *            The key whose associated value is to be returned.
 * @return The value to which the specified key is mapped, or {@code null} if this map contains
 *         no mapping for the key.
 */
V get(K key);

// Modification Operations

/**
 * Associates the specified value with the specified key in this map. If the map previously
 * contained a mapping for the key, the old value is replaced.
 * 
 * @param key
 *            The key with which the specified value is to be associated.
 * @param data
 *            The value to be associated with the specified key.
 * @return The previous value associated with the key, or <tt>null</tt> if there was no mapping
 *         for the key. (A <tt>null</tt> return can also indicate that the map previously
 *         associated <tt>null</tt> with <tt>key</tt>.)
 */
V put(K key, V data);

/**
 * Removes the mapping for the specified key from this map if present.
 * 
 * @param key
 *            The key whose mapping is to be removed from the map.
 * @return The previous value associated with the key, or <tt>null</tt> if there was no mapping
 *         for the key. (A <tt>null</tt> return can also indicate that the map previously
 *         associated <tt>null</tt> with <tt>key</tt>.)
 */
V remove(K key);

// Bulk Operations

/**
 * Removes all of the mappings from this map. The map will be empty after this call returns.
 */
void clear();
}

这使得仅使用公共方法进行测试变得困难，因为我需要某些数据（子/父指针）而该数据在公共接口中不可用。此外，在基数树结构（PR Quadtree、PRKDTree、MX变体等）中，有与数据分离的节点，因此创建一个返回“节点”的公共方法也会被抽象化太远以致于无法获得正确的数据。

我正在寻找哪种类型的测试方法（或技术），可以与JUnit一起使用，而不会感觉自己破坏了美丽的认知界限？

- efritz

Answer 1

有时候会出现这样的情况，你确实需要测试一个结构的内部状态。在这种情况下，我会使用反射来访问内部变量。有一些JUnit插件（PrivateAccessor http://junit-addons.sourceforge.net/junitx/util/PrivateAccessor.html）可以使这个过程更加简单。

不过，这样做的代价是你的测试会更加脆弱，因为如果内部状态发生了变化，你的测试可能会失败。但是，如果你想要确信内部状态是正确的，有时候你需要这样做。

- Jeff Storey

---

只要我的正确性证明是正确的，就应该永远不会改变节点排序方面的内部状态 ;) - efritz

如果变量名称发生更改，测试可能会出现问题。这更像是白盒单元测试（而不是黑盒）。有时候这种风格是合适的，听起来在你的情况下也是这样。 - Jeff Storey

Answer 2

在这种情况下，我使用的一种方法是将这些内部字段设置为受保护的，并创建一个测试子类。通过这个子类，您可以暴露任何白盒测试所需的状态。

- mnuss

Answer 3

如果您将接口及其实现单独放在一个专用包中，并使该实现的内部状态方法为包保护，则您的测试可以访问它们，并可能对其进行测试，而系统的其余部分则无法访问。

这对于单元测试“纯粹主义者”来说并不好，但通常情况下，当我不想将类的内部细节暴露给系统的其余部分，但仍然希望对其内部行为进行断言时，我会采取这种方式。

- Guillaume