use {
crate::{
col::{Col, ColProxy},
record::{Record},
header::{Header,HasCol},
relation::{RelationImpl, Relation, Queryable, Insert, QueryOutput, Delete},
transaction::{UndoLog,Transaction,RevertableOp,Accessor,SubUndoLog},
query::{
QueryPlanImpl,
request::{QueryRequest,GenericQueryRequest},
fallback::FallbackPlanner,
filter::{QueryFilter, Exact},
},
},
std::{
collections::BTreeMap,
convert::Infallible,
marker::PhantomData,
error::Error,
},
tylisp::{
sexpr, HNil,
defun_nocalc,
typenum as tn,
marker_traits::{ListOfRefs},
ops::{
list::{DifferP, Any, Collate, CollatedBy, EmptyP, BuildList},
logic::{Not, And},
Cond,
Is, Ret,
},
},
either::Either,
};
#[derive(Default,Clone)]
pub struct BTreeIndex<K:Ord,Rel>(pub BTreeMap<K,Rel>);
impl<'a, K:'a+Ord, Rel> IntoIterator for &'a BTreeIndex<K, Rel>
where Rel: Relation<'a>,
{
type IntoIter = impl Iterator<Item=Self::Item>;
type Item = Rel::QueryRow;
fn into_iter(self)->Self::IntoIter {
self.0.values().flat_map(|r| r.iter_all())
}
}
impl<K:Col+Ord, R:RelationImpl> RelationImpl for BTreeIndex<K,R>
where R::Cols: HasCol<K>, sexpr!{K}: Header {
type Cols = R::Cols;
type FastCols = sexpr!{K};
type Planner = BTreeIndexPlanner;
}
impl<'a, K:Ord, R> QueryOutput<'a> for BTreeIndex<K,R>
where Self: 'a + RelationImpl,
R:Relation<'a, Cols=Self::Cols>
{
type QueryRow = R::QueryRow;
}
#[derive(Debug, Default)]
pub struct BTreeIndexPlanner;
defun_nocalc!{() BTreeIndexPlanner {
('a, K:Col+Ord, R, Req:QueryRequest, Cols:Header)
{ _:&'a BTreeIndex<K,R>, _:Req }
where (BTreeIndex<K,R>: RelationImpl<Cols=Cols>)
=> { Cond, {{EmptyP, @Req::OrderBy},
{Ret, @BTreePassthroughPlan<&'a BTreeIndex<K,R>, Req>}},
{tn::True,
{FallbackPlanner, @&'a BTreeIndex<K,R>, @Req}}
};
}}
#[derive(Debug,Default)]
pub struct MakeBTreeLookupPlan;
defun_nocalc!{() MakeBTreeLookupPlan {
('a, K:Ord, R, Keys, SubFilt)
{ _:&'a BTreeIndex<K,R>, {_:Keys, _:SubFilt}} =>
{Ret, @BTreeLookupPlan<'a, R, GenericQueryRequest<SubFilt, HNil>>};
}}
pub struct IsExact<K>(PhantomData<K>);
defun_nocalc!{(K) IsExact<K> {
(K:Col, V:QueryFilter) { _:V } =>
{And, {Is, @V, @Exact<K>},
{Not, {DifferP, @V::ReqCols,
{BuildList, @K}}}};
}}
pub struct BTreeLookupPlan <'a,R,Q> {
subrel: Option<&'a R>,
subquery: Q
}
impl<'a,R,Q> IntoIterator for BTreeLookupPlan<'a,R,Q>
where
Q: QueryRequest+'a,
R: Queryable<'a,Q>,
{
type Item = R::QueryRow;
type IntoIter = impl Iterator<Item = Self::Item>;
fn into_iter(self)->Self::IntoIter {
match self.subrel {
Some(r) => Either::Left(r.query(self.subquery)),
None => Either::Right(std::iter::empty())
}
}
}
impl<'a,K:Ord+Col,R,F,Req,First,Rest> QueryPlanImpl<'a, BTreeIndex<K,R>, Req>
for BTreeLookupPlan<'a,R,GenericQueryRequest<F::Failed, HNil>>
where Req: QueryRequest<OrderBy = HNil, Filters = F>,
F: CollatedBy<IsExact<K>, Passed=sexpr!{Exact<First>;Rest}>,
First: ColProxy<For = K>,
Rest: QueryFilter,
K::Inner: Ord,
{
fn prepare(rel: &'a BTreeIndex<K,R>, req: Req)->Self {
let (keys, sub_filter) = req.into_filters().collate();
let subquery = GenericQueryRequest::new(sub_filter);
let idx:&K = keys.head.0.col_ref();
if !keys.tail.test_record(idx) {
return BTreeLookupPlan { subrel: None, subquery };
}
BTreeLookupPlan { subrel: rel.0.get(idx), subquery }
}
}
pub struct BTreePassthroughPlan <Rel,Q> {
rel: Rel,
subquery: Q
}
impl<'a,K,R,Q> IntoIterator for BTreePassthroughPlan<&'a BTreeIndex<K,R>,Q>
where
K:Col+Ord,
Q:QueryRequest+'a,
R:Queryable<'a,Q>,
{
type Item = R::QueryRow;
type IntoIter = impl Iterator<Item = Self::Item>;
fn into_iter(self)->Self::IntoIter {
use crate::range::RangeExt;
self.subquery.clone()
.into_filters()
.bounds_of::<K>()
.into_verified()
.get_from_map(&self.rel.0)
.flat_map(move |(_,r)| r.query(self.subquery.clone()))
}
}
impl<'a,Rel:'a,Q:'a> QueryPlanImpl<'a, Rel,Q>
for BTreePassthroughPlan<&'a Rel,Q>
{
fn prepare(rel: &'a Rel, req: Q)->Self {
BTreePassthroughPlan { rel, subquery: req }
}
}
#[test]
fn test_btree2_rel() {
col!{pub A: u32};
col!{pub B: u32};
col!{pub C: u32};
use tylisp::sexpr;
use crate::relation::Queryable;
use crate::record::Record;
assert_trait!{ ( A, (B,C)): Record };
assert_trait!{ (&A, &(B,C)): Record };
assert_trait!{ BTreeIndex<A, Vec<(A,(B,C))>>: RelationImpl };
assert_trait!{ BTreeIndex<A, Vec<(A,(B,C))>>: for<'a> Relation<'a> };
assert_trait!{ BTreeIndex<A, Vec<(B,A)>>: RelationImpl };
assert_trait!{ BTreeIndex<A, Vec<(B,A)>>: for<'a> Relation<'a> };
let mut rel: BTreeIndex<A, Vec<(B,A)>> = Default::default();
rel.insert_multi(vec![
(A(3), B(11)),
(A(7), B(5)),
(A(3), B(7)),
]).unwrap();
use crate::query::request::{BlankRequest, QueryRequest};
assert_trait!{ BlankRequest: QueryRequest };
let all:Vec<_> = rel.query(BlankRequest).collect();
assert_eq!(3, all.len());
trait Sorted {
fn sorted(self)->Self;
}
impl Sorted for Vec<u32> {
fn sorted(mut self)->Self {
self.sort();
self
}
}
assert_eq!(vec![5,7,11], rel.query(BlankRequest)
.map(|rec| **(rec.col_ref::<B>()))
.collect::<Vec<_>>()
.sorted()
);
use crate::query::filter::Exact;
use crate::query::order::{Asc, Desc};
assert_eq!(vec![11,7],
rel.query(BlankRequest.add_filter(Exact(A(3))))
.map(|rec| **rec.col_ref::<B>() )
.collect::<Vec<_>>()
);
assert_eq!(vec![7,3,3],
rel.query(BlankRequest.set_order::<sexpr!{Asc<B>}>()
)
.map(|rec| **rec.col_ref::<A>() )
.collect::<Vec<_>>()
);
assert_eq!(vec![3,3,7],
rel.query(BlankRequest.set_order::<sexpr!{Desc<B>}>()
)
.map(|rec| **rec.col_ref::<A>() )
.collect::<Vec<_>>()
);
assert_eq!(vec![7,11,5],
rel.query(BlankRequest.set_order::<sexpr!{Asc<A>, Asc<B>}>()
)
.map(|rec| **rec.col_ref::<B>() )
.collect::<Vec<_>>()
);
assert_eq!(vec![7,11],
rel.query(BlankRequest.add_filter(Exact(A(3)))
.set_order::<sexpr!{Asc<A>, Asc<B>}>())
.map(|rec| **rec.col_ref::<B>() )
.collect::<Vec<_>>()
);
assert_eq!(vec![11, 7],
rel.query(BlankRequest.set_order::<sexpr!{Desc<B>, Asc<A>}>()
.add_filter(Exact(A(3))))
.map(|rec| **rec.col_ref::<B>() )
.collect::<Vec<_>>()
);
}
#[derive(thiserror::Error, Debug)]
#[error("Error in subtransaction: {0}")]
pub struct SubtransactionError ( #[from] Box<dyn Error> );
impl<K,R,H:Header> Insert<H> for BTreeIndex<K,R>
where K: Col + Ord + Eq,
H: HasCol<K>,
R: Insert<H> + Default,
Self: RelationImpl {
type Remainder = R::Remainder;
type Op = InsertRequest<K,R,H>;
fn insert_op<FromRec:Record<Cols=H>>(rec:FromRec)
-> (Self::Op, Self::Remainder) {
let key:K = rec.col_ref().clone();
let (op, remainder) = R::insert_op(rec);
(InsertRequest { key, op, header: PhantomData }, remainder)
}
}
pub struct InsertRequest<K,R:Insert<H>,H:Header> {
key: K,
op: R::Op,
header: PhantomData<H>
}
impl<K,R,H:Header> RevertableOp<BTreeIndex<K,R>> for InsertRequest<K,R,H>
where R:Insert<H> + Default, K:Clone+Ord+Eq {
type Err = Either<Either<<R::Op as RevertableOp<R>>::Err,
Infallible>,
Either<Infallible,
Infallible>>;
type Log = (SubUndoLog<InEntry<K>, (<R::Op as RevertableOp<R>>::Log, ()), R>,
(Option<DelEntry<K>>, ())
);
fn apply(self, idx: &mut BTreeIndex<K,R>)->Result<Self::Log, Self::Err> {
let InsertRequest { key, op, header:_ } = self;
Transaction::start(idx)
.apply(CreateEntry(key.clone()))
.subtransaction(InEntry(key.clone()), move |xact|
xact.apply(op)
)
.into_undo_log()
}
}
struct CreateEntry<K>(K);
impl<K:Ord+Eq+Clone,R> RevertableOp<BTreeIndex<K,R>> for CreateEntry<K>
where R:Default {
type Err = std::convert::Infallible;
type Log = Option<DelEntry<K>>;
fn apply(self, idx: &mut BTreeIndex<K,R>)->Result<Self::Log, Self::Err> {
if idx.0.contains_key(&self.0) {
Ok(None)
} else {
idx.0.insert(self.0.clone(), Default::default());
Ok(Some(DelEntry(self.0)))
}
}
}
pub struct DelEntry<K>(K);
impl<K:Ord+Eq,R> UndoLog<BTreeIndex<K,R>> for DelEntry<K> {
fn revert(self, idx: &mut BTreeIndex<K,R>) {
idx.0.remove(&self.0);
}
}
pub struct InEntry<K>(K);
impl<K:Ord+Eq,R> Accessor<BTreeIndex<K,R>> for InEntry<K> {
type Dest = R;
fn access<F,O>(&self, idx: &mut BTreeIndex<K,R>, op:F)->O
where F: FnOnce(&mut Self::Dest)->O
{
op(idx.0.get_mut(&self.0).unwrap())
}
}
impl<K:Ord+Clone,R,Q> Delete<Q> for BTreeIndex<K,R>
where
Q:QueryFilter,
R:Delete<Q>
{
type Op = DeleteWhere<Q, R::Deleter>;
type Deleter = impl Fn(Q)->Self::Op;
fn deleter() -> Self::Deleter {
|q| DeleteWhere { q, deleter: R::deleter() }
}
}
pub struct DeleteWhere<Q, Deleter> {
q:Q,
deleter: Deleter
}
impl<K:Ord+Clone,R,Q,Deleter,Op> RevertableOp<BTreeIndex<K,R>>
for DeleteWhere<Q,Deleter>
where
Deleter: Fn(Q)->Op,
Op: RevertableOp<R>,
Q: Clone
{
type Err = impl std::error::Error;
type Log = impl UndoLog<BTreeIndex<K,R>>;
fn apply(self, target: &mut BTreeIndex<K,R>)->Result<Self::Log, Self::Err> {
let keys:Vec<_> = target.0.keys().cloned().collect();
Transaction::start(target)
.apply_multi(keys.into_iter().map(|k| OpForKey {
key: k,
op: (self.deleter)(self.q.clone())
}))
.into_undo_log()
}
}
pub struct OpForKey<K,Op>{
key:K,
op:Op
}
pub struct UndoForKey<K,Log> {
key:K,
log:Log,
}
impl<K:Ord,R,Op> RevertableOp<BTreeIndex<K,R>> for OpForKey<K,Op>
where
Op: RevertableOp<R>
{
type Err = impl std::error::Error;
type Log = impl UndoLog<BTreeIndex<K,R>>;
fn apply(self, target: &mut BTreeIndex<K,R>)->Result<Self::Log, Self::Err> {
match self.op.apply(target.0.get_mut(&self.key).unwrap()) {
Ok(log) => Ok(UndoForKey { key: self.key, log }),
Err(e) => Err(e)
}
}
}
impl<K:Ord,R,Log> UndoLog<BTreeIndex<K,R>> for UndoForKey<K,Log>
where
Log: UndoLog<R>
{
fn revert(self, target: &mut BTreeIndex<K,R>) {
self.log.revert(target.0.get_mut(&self.key).unwrap())
}
}
#[test] fn test_delete() {
use tylisp::{HNil,sexpr_val};
use crate::query::filter::Exact;
use crate::relation::RelProxy;
col!{pub A: u32};
col!{pub B: u32};
type TestRel = BTreeIndex<A, Option<sexpr!{A,B}>>;
let orig = vec![
(A(1), B(3)),
(A(2), B(2)),
(A(3), B(3)),
];
let new = || {
let mut result: TestRel = Default::default();
result.insert_multi(&orig).unwrap();
result
};
let mut v = new();
RelProxy::<&mut _>::new(&mut v).truncate().unwrap();
assert_eq!(v.iter_as::<sexpr!{A,B}>().collect::<Vec<_>>(), vec![]);
let mut v = new();
RelProxy::<&mut _>::new(&mut v).where_eq(&A(2)).truncate().unwrap();
assert_eq!(v.iter_as::<sexpr!{A,B}>().collect::<Vec<_>>(),
vec![sexpr_val!{A(1), B(3)}, sexpr_val!{A(3), B(3)}]);
let mut v = new();
RelProxy::<&mut _>::new(&mut v).where_eq(&B(3)).truncate().unwrap();
assert_eq!(v.iter_as::<sexpr!{A,B}>().collect::<Vec<_>>(),
vec![sexpr_val!{A(2), B(2)}]);
}