{"record":{"id":"c28dacd74649b6e4","repo":"apache/hadoop","slug":"undefined-for-x","errorCode":null,"errorMessage":"Undefined for \" + x","messagePattern":"Undefined for \" \\+ x","errorType":"exception","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/QuickSort.java","lineNumber":49,"sourceCode":"\n  public QuickSort() { }\n\n  private static void fix(IndexedSortable s, int p, int r) {\n    if (s.compare(p, r) > 0) {\n      s.swap(p, r);\n    }\n  }\n\n  /**\n   * Deepest recursion before giving up and doing a heapsort.\n   * Returns 2 * ceil(log(n)).\n   *\n   * @param x x.\n   * @return MaxDepth.\n   */\n  protected static int getMaxDepth(int x) {\n    if (x <= 0)\n      throw new IllegalArgumentException(\"Undefined for \" + x);\n    return (32 - Integer.numberOfLeadingZeros(x - 1)) << 2;\n  }\n\n  /**\n   * Sort the given range of items using quick sort.\n   * {@inheritDoc} If the recursion depth falls below {@link #getMaxDepth},\n   * then switch to {@link HeapSort}.\n   */\n  @Override\n  public void sort(IndexedSortable s, int p, int r) {\n    sort(s, p, r, null);\n  }\n\n  @Override\n  public void sort(final IndexedSortable s, int p, int r,\n      final Progressable rep) {\n    sortInternal(s, p, r, rep, getMaxDepth(r - p));\n  }","sourceCodeStart":31,"sourceCodeEnd":67,"githubUrl":"https://github.com/apache/hadoop/blob/2add9630210752f88ceb1bb74eb65e37bf41da8e/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/QuickSort.java#L31-L67","documentation":"QuickSort.getMaxDepth(x) computes the quicksort recursion budget (4 * ceil(log2 x) via 32 - numberOfLeadingZeros(x - 1)) and rejects x <= 0 with IllegalArgumentException(\"Undefined for N\") because the log-based formula is meaningless there. The public sort() invokes it as getMaxDepth(r - p), so this throw means the sort range is empty or inverted — r <= p (r is exclusive).","triggerScenarios":"sort(sortable, 0, 0) — empty range, r - p == 0; sort(s, 5, 2) with p > r; calling getMaxDepth(0) directly; an off-by-one passing array.length - 1 as r instead of array.length.","commonSituations":"Generic sort wrappers forwarding user-supplied offsets without validation; index arithmetic on empty arrays; unit tests sorting zero-element ranges; refactors that changed whether the end index is inclusive or exclusive.","solutions":["Skip sorting for empty ranges: if (r - p < 2) return;","Fix off-by-one bounds — pass the exclusive end (array length, not length - 1)","Validate p >= 0 && r > p at your wrapper boundary before invoking QuickSort"],"exampleFix":"// before\nquickSort.sort(indexed, 0, records.length - 1);\n\n// after\nif (records.length > 1) {\n  quickSort.sort(indexed, 0, records.length); // r is exclusive\n}","handlingStrategy":"validation","validationCode":"if (p < 0 || r <= p) { return; } // nothing to sort; r is exclusive\nquickSort.sort(indexed, p, r);","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Treat r as an exclusive end index in all IndexedSortable code","Guard empty and single-element ranges before calling sort","Property-test wrappers with random p/r to catch inverted ranges"],"tags":["hadoop","java","sorting","off-by-one","argument-validation"],"backgroundTag":"invalid-sort-range","analyzedSha":"2add9630210752f88ceb1bb74eb65e37bf41da8e","analyzedAt":"2026-08-22T19:55:07.957Z","schemaVersion":2},"datasetVersion":"2026-08-22T20:17:22.307Z"}