/// Implement this trait to opt-in your type to `MultiGet`.
///
/// The methods should be trivial passthroughs to the existing
/// `get_mut` and `index_mut` methods.
///
/// # Safety
///
/// This trait is unsafe because by implementing it you're promising that
/// it's ok for multiple mutable references from these methods to be alive
/// at the same time so long as they're at different addresses.
pub unsafe trait SingleGet<Idx=usize> {
    type Output;
    fn single_get(&mut self, i: Idx) -> Option<&mut Self::Output>;
    fn single_index(&mut self, i: Idx) -> &mut Self::Output;
}

unsafe impl<T> SingleGet for Vec<T> {
    type Output = T;
    fn single_get(&mut self, i: usize) -> Option<&mut T> { self.get_mut(i) }
    fn single_index(&mut self, i: usize) -> &mut T { &mut self[i] }
}

pub trait MultiGet<'a, Args: internals::MultiGetArgs<'a, Self>>: Sized {
    fn multi_get(&'a mut self, args: Args) -> Option<Args::GetOutput>;
    fn multi_index(&'a mut self, args: Args) -> Args::IndexOutput;
}
impl<'a, T, A: internals::MultiGetArgs<'a, T>> MultiGet<'a, A> for T {
    fn multi_get(&'a mut self, a: A) -> Option<A::GetOutput> {
        a.get(self)
    }

    fn multi_index(&'a mut self, a: A) -> A::IndexOutput {
        a.index(self)
    }
}

mod internals {
    use super::*;

    pub trait MultiGetArgs<'a, T> {
        type GetOutput;
        fn get(self, t: &'a mut T) -> Option<Self::GetOutput>;
        type IndexOutput;
        fn index(self, t: &'a mut T) -> Self::IndexOutput;
    }

    trait TupleAsSlice<T> {
        fn on_slice<F, R>(&self, f: F) -> R
            where F: FnOnce(&[&T]) -> R;
        fn any<F>(&self, f: F) -> bool
            where F: Fn(&T) -> bool
        {
            self.on_slice(|s| s.iter().any(|&x| f(x)))
        }
    }

    trait TupleMap<T, U> {
        type Output;
        fn map<F>(self, f: F) -> Self::Output
            where F: FnMut(T) -> U;
    }

    macro_rules! replace_type {
        ($_t:tt => $sub:ty) => {$sub};
    }
    macro_rules! impl_tuple_ops {
        () => { impl_tuple_ops!(@); };
        ( $i0:ident $($i:ident)* ) => {
            impl_tuple_ops!( $($i)* );
            impl_tuple_ops!(@ $i0 $($i)* );
        };
        (@ $($i:ident)* ) => {

            impl<T> TupleAsSlice<T> for ( $( replace_type!($i => T), )* ) {
                fn on_slice<F, R>(&self, f: F) -> R
                    where F: FnOnce(&[&T]) -> R
                {
                    let &( $(ref $i,)* ) = self;
                    let slice = [ $($i,)* ];
                    f(&slice)
                }
            }

            impl<T,U> TupleMap<T,U> for ( $( replace_type!($i => T), )* ) {
                type Output = ( $( replace_type!($i => U), )* );
                #[allow(unused_variables, unused_mut)]
                fn map<F>(self, mut f: F) -> Self::Output
                    where F: FnMut(T) -> U
                {
                    let ( $($i,)* ) = self;
                    ( $(f($i),)* )
                }
            }
        };
    }
    impl_tuple_ops!(a b c d e f g h i);

    macro_rules! impl_multi_get {
        () => { impl_multi_get!(@); };
        ( $i0:ident $($i:ident)* ) => {
            impl_multi_get!( $($i)* );
            impl_multi_get!(@ $i0 $($i)* );
        };
        (@) => {
            impl<'a, T: 'a> MultiGetArgs<'a, T> for () {
                type GetOutput = ();
                fn get(self, _: &'a mut T) -> Option<()> { Some(()) }
                type IndexOutput = ();
                fn index(self, _: &'a mut T) -> () { () }
            }
        };
        (@ $($i:ident)+ ) => {

            impl<'a, T: 'a, I> MultiGetArgs<'a, T> for ( $( replace_type!($i => I), )* )
                where T: SingleGet<I>, T::Output: 'a
            {
                type GetOutput = ( $( replace_type!($i => Option<&'a mut T::Output>), )* );
                fn get(self, t: &'a mut T) -> Option<Self::GetOutput> {
                    let pointers = self.map(|i| option_as_mut_ptr(t.single_get(i)));
                    if pointers.on_slice(duplicate_positions).is_some() {
                        None
                    } else {
                        unsafe { Some(pointers.map(|p| p.as_mut())) }
                    }
                }

                type IndexOutput = ( $( replace_type!($i => &'a mut T::Output), )* );
                fn index(self, t: &'a mut T) -> Self::IndexOutput {
                    let pointers = self.map(|i| t.single_index(i) as *mut _);
                    if let Some((i, j)) = pointers.on_slice(duplicate_positions) {
                        panic!("Aliasing violation between args.{} and args.{}", i, j);
                    }
                    pointers.map(|p| unsafe { &mut* p })
                }
            }
        };
    }
    impl_multi_get!(a b c d e f g h i);

    fn option_as_mut_ptr<T>(x: Option<&mut T>) -> *mut T {
        x.map_or(std::ptr::null_mut(), |r| r as *mut _)
    }

    fn duplicate_positions<T>(s: &[&*mut T]) -> Option<(usize, usize)> {
        for (i, &p) in s.iter().enumerate() {
            if !p.is_null() {
                if let Some(j) = s[..i].iter().position(|&q| p == q) {
                    return Some((j, i));
                }
            }
        }
        None
    }
}

#[cfg(test)]
mod tests {
    use super::MultiGet;

    #[test]
    fn it_works() {
        let mut v = vec![1, 2, 3, 4, 5];
        assert_eq!(v.multi_index(()), ());
        assert_eq!(v.multi_get(()), Some(()));
        {
            let (a,) = v.multi_index((2,));
            *a = 9;
        }
        assert_eq!(v, vec![1, 2, 9, 4, 5]);
        {
            let (a, b) = v.multi_index((1, 3));
            ::std::mem::swap(a, b);
        }
        assert_eq!(v, vec![1, 4, 9, 2, 5]);
    }

    #[test]
    #[should_panic(expected = "Aliasing violation between args.0 and args.2")]
    fn foo() {
        let mut v = vec![1, 2, 3, 4, 5];
        v.multi_index((0,1,0));
    }
}