# UNDF: UNDF-2026-000000474
# UNDF: (pending)
# hv-0001: DefaultValidationOrder.insertGroup — groupList.contains() O(N) list scan

## CWE-407 — Algorithmic Complexity: O(N) List.contains() dedup in validation group ordering

| Field        | Value |
|--------------|-------|
| ID           | hv-0001 |
| Severity     | MEDIUM |
| Ecosystem    | hibernate-validator |
| Package      | hibernate-validator |
| File         | `engine/src/main/java/org/hibernate/validator/internal/engine/groups/DefaultValidationOrder.java` |
| Lines        | 57–65 |
| Complexity   | O(N) per call; O(N²) for N groups |
| Hot path     | Called per validation group during `ValidatorImpl.validate()` |

## Defect

`DefaultValidationOrder.insertGroup` uses `List<Group>.contains()` to deduplicate groups:

```java
// DefaultValidationOrder.java:57-65 (DEFECT)
private List<Group> groupList;  // initialized with new ArrayList<>(5)

public void insertGroup(Group group) {
    if ( groupList == null ) {
        groupList = new ArrayList<>( 5 );
    }
    if ( !groupList.contains( group ) ) {    // O(N) linear scan
        groupList.add( group );
    }
}
```

Also in `ensureDefaultGroupSequenceIsExpandable` (line 119):
```java
int index = groupList.indexOf( group );  // O(N) linear scan
```

And `ValidationOrderGenerator.addGroups` (lines 166-167):
```java
if ( resolvedGroupSequence.contains( tmpGroup )          // O(N) scan #1
        && resolvedGroupSequence.indexOf( tmpGroup ) < resolvedGroupSequence.size() - 1 ) {  // O(N) scan #2
```

Two O(N) scans per group in `addGroups` — O(N²) total.

## Fix

Replace `List<Group>` with a `LinkedHashSet<Group>` for O(1) membership and preserved insertion order:

```java
// AFTER — O(1) per operation
private Set<Group> groupList;  // LinkedHashSet preserves insertion order

public void insertGroup(Group group) {
    if ( groupList == null ) {
        groupList = new LinkedHashSet<>( 5 );
    }
    groupList.add( group );  // O(1) — Set.add() deduplicates automatically
}
```

For `ensureDefaultGroupSequenceIsExpandable`, build an index map:
```java
Map<Group, Integer> groupIndex = new LinkedHashMap<>();
for (int i = 0; i < sequenceGroups.size(); i++) groupIndex.put(sequenceGroups.get(i), i);
int index = groupIndex.getOrDefault(group, -1);  // O(1)
```

For `addGroups`, build a position index before the loop:
```java
Map<Group, Integer> positionMap = new LinkedHashMap<>();
for (int i = 0; i < resolvedGroupSequence.size(); i++) positionMap.put(resolvedGroupSequence.get(i), i);
for (Group tmpGroup : groups) {
    Integer pos = positionMap.get(tmpGroup);
    if (pos != null && pos < resolvedGroupSequence.size() - 1) throw LOG.getUnableToExpandGroupSequenceException();
    resolvedGroupSequence.add(tmpGroup);
    positionMap.put(tmpGroup, resolvedGroupSequence.size() - 1);
}
```

## Speedup

| Groups (N) | Before (scans) | After (scans) | Speedup |
|------------|----------------|---------------|---------|
| 10         | 55             | 10            | 5.5×    |
| 50         | 1,275          | 50            | 25.5×   |
| 100        | 5,050          | 100           | 50.5×   |

Growth before: O(N²). Growth after: O(N).
