# UNDF: UNDF-2026-000000430
# janusgraph-0001: MultiCondition extends ArrayList — O(C²) condition deduplication in query builder

## Severity
MEDIUM

## Location
`janusgraph-core/src/main/java/org/janusgraph/graphdb/query/condition/MultiCondition.java`
Line 29 — class declaration

`janusgraph-core/src/main/java/org/janusgraph/graphdb/query/QueryUtil.java`
Line 339 — call site

## Description
`MultiCondition<E>` is the base class for both `And` and `Or` condition nodes in
JanusGraph's query tree.  It **extends `ArrayList<Condition<E>>`**, inheriting
`ArrayList.contains()` which is an O(N) linear scan.

`QueryUtil.addConstraint()` (line 339) calls `conditions.contains(pc)` before
adding a new `PredicateCondition` to guard against duplicates.  This method is
called once per predicate being added to a query's condition tree.

For a query with C conditions, building the tree costs O(1 + 2 + … + C) = O(C²)
comparisons.  Since JanusGraph queries often carry dozens of predicate conditions
(property filters, label constraints, range queries), this is a realistic
quadratic bottleneck in the query planning path.

## Defective Code
```java
// MultiCondition.java:29
public abstract class MultiCondition<E extends JanusGraphElement>
        extends ArrayList<Condition<E>> implements Condition<E> {
    // inherits O(N) contains() from ArrayList
}

// QueryUtil.java:339 — called once per predicate addition
if (!conditions.contains(pc)) conditions.add(pc);
```

## Root Cause
Extending `ArrayList` for a semantic "set of conditions" conflates ordered list
storage with membership testing.  The design choice to back conditions with a
`List` means every duplicate-check is O(C).

## Fix
Change `MultiCondition` to maintain a parallel `HashSet` for O(1) membership
testing:

```java
public abstract class MultiCondition<E extends JanusGraphElement>
        extends ArrayList<Condition<E>> implements Condition<E> {

    private final Set<Condition<E>> conditionSet = new HashSet<>();

    @Override
    public boolean add(Condition<E> condition) {
        assert condition != null;
        if (conditionSet.add(condition)) {
            return super.add(condition);
        }
        return false;
    }

    @Override
    public boolean contains(Object o) {
        return conditionSet.contains(o);
    }
}
```

This keeps insertion order (for any callers that iterate conditions in order)
while making `contains()` O(1).  The `QueryUtil.addConstraint()` call site
requires no change.

Alternatively, replace the backing structure with `LinkedHashSet` entirely
and change the `getChildren()` return type — but that is a larger API change.

## Complexity
| Operation | Before | After |
|-----------|--------|-------|
| `conditions.contains(pc)` per call | O(C) | O(1) |
| Build C-condition query tree | O(C²) | O(C) |
