[Bug]: check_intervals will not validate correctly in certain nested txn scenarios

[bsbds]

Description about the bug

In the current implementation of check_intervals in txn request validation, it may not validate the request correctly.

/// Check if puts and deletes overlap
fn check_intervals(ops: &[RequestOp]) -> Result<(HashSet<&[u8]>, Vec<KeyRange>), ValidationError> {
    // TODO: use interval tree is better?

    let mut dels = Vec::new();

    for op in ops {
        if let Some(Request::RequestDeleteRange(ref req)) = op.request {
            // collect dels
            let del = KeyRange::new(req.key.as_slice(), req.range_end.as_slice());
            dels.push(del);
        }
    }

    let mut puts: HashSet<&[u8]> = HashSet::new();

    for op in ops {
        if let Some(Request::RequestTxn(ref req)) = op.request {
            // handle child txn request
            let (success_puts, mut success_dels) = check_intervals(&req.success)?;
            let (failure_puts, mut failure_dels) = check_intervals(&req.failure)?;

            for k in &success_puts {
                if !puts.insert(k) {
                    return Err(ValidationError::new("duplicate key given in txn request"));
                }
                if dels.iter().any(|del| del.contains_key(k)) {
                    return Err(ValidationError::new("duplicate key given in txn request"));
                }
            }

            for k in failure_puts {
                if !puts.insert(k) && !success_puts.contains(k) {
                    // only keys in the puts and not in the success_puts is overlap
                    return Err(ValidationError::new("duplicate key given in txn request"));
                }
                if dels.iter().any(|del| del.contains_key(k)) {
                    return Err(ValidationError::new("duplicate key given in txn request"));
                }
            }

            dels.append(&mut success_dels);
            dels.append(&mut failure_dels);
        }
    }

    for op in ops {
        if let Some(Request::RequestPut(ref req)) = op.request {
            // check puts in this level
            if !puts.insert(&req.key) {
                return Err(ValidationError::new("duplicate key given in txn request"));
            }
            if dels.iter().any(|del| del.contains_key(&req.key)) {
                return Err(ValidationError::new("duplicate key given in txn request"));
            }
        }
    }
    Ok((puts, dels))
}

Consider the following senerio(assume all requests are in the success branch): If a txn S contains two sub txn A and B. A contains a put, B contains a delete, and the put overlaps with the delete. Then S[A(put), B(del)] will return a ok but S[B(del), A(put) will return an error.

The reason this inconsistency exist is that the sub txn requests are checked in a specific order, and append the deletes from sub txn to dels in this order. The put checks dels for overlapping. So if the put is checked before the delete, it will not know that the delete is overlap with itself.

Version

0.1.0

Relevant log output

No response

Code of Conduct

• I agree to follow this project's Code of Conduct

[bsbds]

Also tracked in etcd-io/etcd#16380

[bsbds]

Closing as fixed by #963.