Java - 如何对 TimSort 和 "general contract violation" 问题进行单元测试
Java - How to unit test TimSort and "general contract violation" issues
这个问题与"Comparison method violates its general contract!" - TimSort and GridLayout相关
以及其他几个类似的 "general contract violation" 问题。我的问题与 Ceekay 在页面底部关于 "How to test the TimSort implementation" 的回答特别相关。就我而言，我已经修复了由于对称性违规而将我带到这里的应用程序错误，但我无法创建单元测试来暴露该违规行为（如果修复被注释掉或将来未修复）。
public class TickNumber implements Comparable<TickNumber> {
protected String zone;
protected String track;
}
public class GisTickNumber extends TickNumber implements Comparable<TickNumber> {
private String suffix;
}
我省略了所有实施细节，但基本上 Tick 号码是一个 4 位数字，其中前两位数字是区域，后两位数字是轨道。 GisTickNumbers 可以在区域和/或轨道字段中包含字母字符，并且它们可以选择包含一个或两个字符的字母后缀。有效刻度是 运行ge [0000, 9999] 中的所有整数（即使表示为字符串）。所有有效的 Tick 数字都是有效的 Gis Tick 数字，但有效的 Gis Tick 也可以看起来像 A912, R123, 0123G, A346*.
我的对称违规是在 GisTick compareTo 中，我考虑了可能的后缀，但在普通 Tick compareTo 中我没有考虑它。因此，如果 'this' 是 0000 Tick 而 'that' 是 0000* Gis Tick，则 0000.compareTo(0000*) 将 return 0。而如果 'this' 是 0000* Gis Tick，'that' 是 0000 Tick，0000*.compareTo(0000) 会 return 1. 明显的对称性违规（一旦护罩拉回）
根据 Ceekay 对链接问题的回答，
- Create a list with 32 or more objects.
- Within that list, there needs to [be] two or more runs.
- Each run must contain 3 or more objects.
Once you meet those [three] criteria you can begin testing for this failure.
我相信我已经为我的单元测试设置了这样一个 TickNumber（和 GisTickNumber）对象列表，但我似乎无法使测试失败。尽管该列表有超过 100 个对象，超过两个 运行，并且每个 运行 包含大约 10 个对象。所以，我的问题是被测对象列表还需要满足哪些其他特征才能使 Collections.sort(testList) 的调用因 "general (symmetry) contract violation"?
而失败
- 是的，我在 运行 我预计会失败的单元测试之前注释掉了修复程序。
已解决：
我最终调试到一个断点，在那里我可以查看列表中对象的 toString() 表示得到排序，然后能够从其余数据中提取 TickNumber 信息并最终在我的中使用提取的数据单元测试。最后，我返回并删除了列表项，直到我制作了一个似乎满足 "minimal requirements" 的列表以触发与 "general contract violations".
相关的对称性
我不确定如何将我的特定解决方案概括为列表必须满足的通用特征才能触发 TimsSort 和此 "general contract violation"。但是这里...
- 列表必须包含 64 个元素 (49 + 1 + 12 + 1 + 1)
- 列表必须包含 运行 50，其中 50 个元素中的 49 个比较结果为 0（即比较匹配）
- 在 "matching run" 的前半部分中，必须有 1 个元素排在 运行 中的所有其他元素之前（比较时 运行 中的所有其他元素都匹配），并且那个奇数元素也必须 "symmetry mismatch" 其他 运行s.
末尾的元素
- 该列表必须包含至少 2 个其他 运行 的三个或更多元素（我的测试列表有一个 运行 为 8，后跟一个 运行 为 4）
- "symmetry mismatch"的另一半必须是4的运行中的最后一项（第二个other运行）。
- 列表必须在 (end - 1) 位置包含一个元素，该元素排序到已排序列表的开头
- 该列表必须在（末尾）位置包含一个元素，该元素排序在已排序列表的中间某处
我很确定上面的项目符号并不是一个列表必须满足的一般要求的详尽列表，以便在对列表进行排序时暴露对称性违规，但它们在一个特定情况下对我有用。
具体来说，我精心制作的测试列表以 49 个 TickNumber 对象开始，其中 Tick =“9999”，并且在 49 个 Ticks 的前半部分的某处有一个“9910”Tick，总共有 50 个 Tick 数字开幕 pseudo-run。 （伪因为“9910”打破了 49 个匹配“9999”刻度的未排序 运行。）开口 运行 中的“9910”刻度是我正在测试的对称性不匹配的 one-half为了。然后测试列表包含 12 个 GisTickNumber 对象作为 运行 of 8 ("9915*", "9920*", "9922*", "9931*", "9933*", "9934*", "9936 *"、"9939*")，然后是 4 的 运行（"9907*"、"9908*"、"9909*"、"9910*"）。请注意，运行 of 4 中的最后一项是我正在测试的 "symmetry mismatch" 的另一半。最后，该列表以一个“9901”TickNumber 对象结束，该对象将引导排序列表，以及一个“9978*”GisTickNumber 对象，该对象在中间某处进行排序。我曾尝试删除 and/or 重新排列测试列表中的对象，但无济于事。例如，如果从测试列表中删除“9901”元素，单元测试将开始发出 false-positive（成功）结果。 （false-positive如果将“9901”移到未排序列表的前面，也会发生）
注意：我怀疑“9910”对称性不匹配的普通 TickNumber 部分可能出现在第 MIN_RUN 个元素之前的开口 运行 中的任何位置。换句话说，如果 MIN_RUN 是 32 并且我的测试列表中的前导 运行 有 50 个元素与 49 个比较 "the same"，那么“9910”对称不匹配元素可以出现在任何位置在运行位置32以下。这个假设还没有被证明；但我凭经验确定对称失配元素不能出现在前导 运行 的末尾附近，它可以出现在前导 运行 开始附近的多个位置。 （每次测试一个不同的点 运行）
一般来说，如果这些条件中的任何一个不符合 "exactly right"，即使您正在测试列表数据，其中的比较应该违反约定，您也不会触发 "general contract violation"。
就我而言，在我的测试列表中唯一匹配的 TickNumber 对象是 49 个“9999”刻度和 2 个（“9910”和“9910*”）在比较时违反对称性的刻度。
这个问题与"Comparison method violates its general contract!" - TimSort and GridLayout相关 以及其他几个类似的 "general contract violation" 问题。我的问题与 Ceekay 在页面底部关于 "How to test the TimSort implementation" 的回答特别相关。就我而言，我已经修复了由于对称性违规而将我带到这里的应用程序错误，但我无法创建单元测试来暴露该违规行为（如果修复被注释掉或将来未修复）。
public class TickNumber implements Comparable<TickNumber> {
protected String zone;
protected String track;
}
public class GisTickNumber extends TickNumber implements Comparable<TickNumber> {
private String suffix;
}
我省略了所有实施细节，但基本上 Tick 号码是一个 4 位数字，其中前两位数字是区域，后两位数字是轨道。 GisTickNumbers 可以在区域和/或轨道字段中包含字母字符，并且它们可以选择包含一个或两个字符的字母后缀。有效刻度是 运行ge [0000, 9999] 中的所有整数（即使表示为字符串）。所有有效的 Tick 数字都是有效的 Gis Tick 数字，但有效的 Gis Tick 也可以看起来像 A912, R123, 0123G, A346*.
我的对称违规是在 GisTick compareTo 中，我考虑了可能的后缀，但在普通 Tick compareTo 中我没有考虑它。因此，如果 'this' 是 0000 Tick 而 'that' 是 0000* Gis Tick，则 0000.compareTo(0000*) 将 return 0。而如果 'this' 是 0000* Gis Tick，'that' 是 0000 Tick，0000*.compareTo(0000) 会 return 1. 明显的对称性违规（一旦护罩拉回）
根据 Ceekay 对链接问题的回答，
- Create a list with 32 or more objects.
- Within that list, there needs to [be] two or more runs.
- Each run must contain 3 or more objects.
Once you meet those [three] criteria you can begin testing for this failure.
我相信我已经为我的单元测试设置了这样一个 TickNumber（和 GisTickNumber）对象列表，但我似乎无法使测试失败。尽管该列表有超过 100 个对象，超过两个 运行，并且每个 运行 包含大约 10 个对象。所以，我的问题是被测对象列表还需要满足哪些其他特征才能使 Collections.sort(testList) 的调用因 "general (symmetry) contract violation"?
- 是的，我在 运行 我预计会失败的单元测试之前注释掉了修复程序。
已解决：
我最终调试到一个断点，在那里我可以查看列表中对象的 toString() 表示得到排序，然后能够从其余数据中提取 TickNumber 信息并最终在我的中使用提取的数据单元测试。最后，我返回并删除了列表项，直到我制作了一个似乎满足 "minimal requirements" 的列表以触发与 "general contract violations".
我不确定如何将我的特定解决方案概括为列表必须满足的通用特征才能触发 TimsSort 和此 "general contract violation"。但是这里...
- 列表必须包含 64 个元素 (49 + 1 + 12 + 1 + 1)
- 列表必须包含 运行 50，其中 50 个元素中的 49 个比较结果为 0（即比较匹配）
- 在 "matching run" 的前半部分中，必须有 1 个元素排在 运行 中的所有其他元素之前（比较时 运行 中的所有其他元素都匹配），并且那个奇数元素也必须 "symmetry mismatch" 其他 运行s. 末尾的元素
- 该列表必须包含至少 2 个其他 运行 的三个或更多元素（我的测试列表有一个 运行 为 8，后跟一个 运行 为 4）
- "symmetry mismatch"的另一半必须是4的运行中的最后一项（第二个other运行）。
- 列表必须在 (end - 1) 位置包含一个元素，该元素排序到已排序列表的开头
- 该列表必须在（末尾）位置包含一个元素，该元素排序在已排序列表的中间某处
我很确定上面的项目符号并不是一个列表必须满足的一般要求的详尽列表，以便在对列表进行排序时暴露对称性违规，但它们在一个特定情况下对我有用。
具体来说，我精心制作的测试列表以 49 个 TickNumber 对象开始，其中 Tick =“9999”，并且在 49 个 Ticks 的前半部分的某处有一个“9910”Tick，总共有 50 个 Tick 数字开幕 pseudo-run。 （伪因为“9910”打破了 49 个匹配“9999”刻度的未排序 运行。）开口 运行 中的“9910”刻度是我正在测试的对称性不匹配的 one-half为了。然后测试列表包含 12 个 GisTickNumber 对象作为 运行 of 8 ("9915*", "9920*", "9922*", "9931*", "9933*", "9934*", "9936 *"、"9939*")，然后是 4 的 运行（"9907*"、"9908*"、"9909*"、"9910*"）。请注意，运行 of 4 中的最后一项是我正在测试的 "symmetry mismatch" 的另一半。最后，该列表以一个“9901”TickNumber 对象结束，该对象将引导排序列表，以及一个“9978*”GisTickNumber 对象，该对象在中间某处进行排序。我曾尝试删除 and/or 重新排列测试列表中的对象，但无济于事。例如，如果从测试列表中删除“9901”元素，单元测试将开始发出 false-positive（成功）结果。 （false-positive如果将“9901”移到未排序列表的前面，也会发生）
注意：我怀疑“9910”对称性不匹配的普通 TickNumber 部分可能出现在第 MIN_RUN 个元素之前的开口 运行 中的任何位置。换句话说，如果 MIN_RUN 是 32 并且我的测试列表中的前导 运行 有 50 个元素与 49 个比较 "the same"，那么“9910”对称不匹配元素可以出现在任何位置在运行位置32以下。这个假设还没有被证明；但我凭经验确定对称失配元素不能出现在前导 运行 的末尾附近，它可以出现在前导 运行 开始附近的多个位置。 （每次测试一个不同的点 运行）
一般来说，如果这些条件中的任何一个不符合 "exactly right"，即使您正在测试列表数据，其中的比较应该违反约定，您也不会触发 "general contract violation"。
就我而言，在我的测试列表中唯一匹配的 TickNumber 对象是 49 个“9999”刻度和 2 个（“9910”和“9910*”）在比较时违反对称性的刻度。