# UNDF: UNDF-2026-000000314
# UNDF: (pending)
# tinkerpop-0001: MutablePath.isSimple — missing O(P) override, falls back to O(P²) default

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | tinkerpop-0001 |
| Severity | MEDIUM |
| Ecosystem | tinkerpop |
| Package | gremlin-core |
| File | `gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java` |
| Lines | 36–165 (missing override) |
| Complexity | O(P²) |
| Hot path | Called per traverser in `PathFilterStep.filter()` when `.simplePath().by(...)` or `.cyclicPath().by(...)` is used |

## Defect

`MutablePath` does not override `isSimple()`. The default implementation in `Path.java` uses a
nested double-loop over `objects()`:

```java
// Path.java default — O(P²)
public default boolean isSimple() {
    final List<Object> objects = this.objects();
    for (int i = 0; i < objects.size() - 1; i++) {
        for (int j = i + 1; j < objects.size(); j++) {
            if (Objects.equals(objects.get(i), objects.get(j)))
                return false;
        }
    }
    return true;
}
```

`ImmutablePath` already has the correct O(P) override using a `HashSet`:

```java
// ImmutablePath — O(P) ✓
public boolean isSimple() {
    final Set<Object> objects = new HashSet<>();
    ImmutablePath currentPath = this;
    while (true) {
        if (currentPath.isTail()) return true;
        else if (objects.contains(currentPath.currentObject)) return false;
        else { objects.add(currentPath.currentObject); currentPath = currentPath.previousPath; }
    }
}
```

`MutablePath` is used in `PathFilterStep.filter()` (line 65) and `PathStep` (line 119) when a
`by()` modulator is present. `byPath.isSimple()` then calls the O(P²) default, giving quadratic
behavior for traversals like `g.V().simplePath().by(...)` with long paths.

## Fix

Add the O(P) override to `MutablePath`:

```java
// MutablePath.java — add this override
@Override
public boolean isSimple() {
    final Set<Object> seenObjects = new HashSet<>();
    for (final Object object : this.objects) {
        if (!seenObjects.add(object)) {
            return false;
        }
    }
    return true;
}
```

## Speedup

| P (path length) | Before (comparisons) | After (comparisons) | Speedup |
|-----------------|---------------------|---------------------|---------|
| 10 | 45 | 10 | 4.5× |
| 50 | 1,225 | 50 | 24.5× |
| 100 | 4,950 | 100 | 49.5× |
| 500 | 124,750 | 500 | 249.5× |
