// Copyright 2015 MaidSafe.net limited.
//
// This SAFE Network Software is licensed to you under (1) the MaidSafe.net
// Commercial License,
// version 1.0 or later, or (2) The General Public License (GPL), version 3,
// depending on which
// licence you accepted on initial access to the Software (the "Licences").
//
// By contributing code to the SAFE Network Software, or to this project
// generally, you agree to be
// bound by the terms of the MaidSafe Contributor Agreement, version 1.0.
// This, along with the
// Licenses can be found in the root directory of this project at LICENSE,
// COPYING and CONTRIBUTOR.
//
// Unless required by applicable law or agreed to in writing, the SAFE Network
// Software distributed
// under the GPL Licence is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
// OR CONDITIONS OF ANY
// KIND, either express or implied.
//
// Please review the Licences for the specific language governing permissions
// and limitations
// relating to use of the SAFE Network Software.

//! #data_blocks
//! Data blocks can be chained to provide verifiable assuredness that they contain network valid
//! data and not injected.
//!
//! This crate assumes these objects below are relevent to `close_groups` this allows integrity
//! check of the `DataChain` in so far as it will hold valid data identifiers agreed by this group
//! & all groups since the group/network started.
//!
//! These chains allow nodes to become `archive nodes` on a network and also ensure data integrity
//! AS LONG AS the data identifiers hold a validating element such as hash of the data itself.
//!
//! Another purpose of these chains is to allow network restarts with valid data. Obviously this
//! means the network nodes will have to tr and restart as the last known ID they had. Vaults
//! will require to accept or reject such nodes in normal operation. On network restart though
//! these nodes may be allowed to join a group if they can present a `DataChain` that appears
//! healthy, even if there is not yet enough consensus to `trust` the data iself just yet.
//! additional nodes will also join this group and hopefully confirm the data integrity is agreed
//! as the last `Block` should contain a majorit of existing group members that have signed.
//!
//! Nodes do no require to become `Archive nodes` if they have limited bandwidth or disk space, but
//! they are still valuable as transient nodes which may deliver data stored whle they are in the
//! group. Such nodes may only be involved in consensus and routing stability messages, returning
//! a `Nack` to any `Get` request  due to upstream bandwidth limitations.
//!
//! Several enhancement can be made to this scheme with a much deper investigation into any
//! attack vectors. Such as
#![doc(html_logo_url =
           "https://raw.githubusercontent.com/maidsafe/QA/master/Images/maidsafe_logo.png",
       html_favicon_url = "http://maidsafe.net/img/favicon.ico",
       html_root_url = "http://dirvine.github.io/data_blocks")]

// For explanation of lint checks, run `rustc -W help` or see
// https://github.com/maidsafe/QA/blob/master/Documentation/Rust%20Lint%20Checks.md
#![forbid(bad_style, exceeding_bitshifts, mutable_transmutes, no_mangle_const_items,
          unknown_crate_types, warnings)]
#![deny(deprecated, drop_with_repr_extern, improper_ctypes, missing_docs,
        non_shorthand_field_patterns, overflowing_literals, plugin_as_library,
        private_no_mangle_fns, private_no_mangle_statics, stable_features, unconditional_recursion,
        unknown_lints, unsafe_code, unused, unused_allocation, unused_attributes,
        unused_comparisons, unused_features, unused_parens, while_true)]
#![warn(trivial_casts, trivial_numeric_casts, unused_extern_crates, unused_import_braces,
        unused_qualifications, unused_results)]
#![allow(box_pointers, fat_ptr_transmutes, missing_copy_implementations,
         missing_debug_implementations, variant_size_differences)]


#![cfg_attr(feature="clippy", feature(plugin))]
#![cfg_attr(feature="clippy", plugin(clippy))]
#![cfg_attr(feature="clippy", deny(clippyclippy_pedantic))]
#![cfg_attr(feature="clippy", allow(use_debug))]

extern crate sodiumoxide;
extern crate rustc_serialize;
#[macro_use]
extern crate maidsafe_utilities;
#[cfg(test)]
extern crate itertools;
extern crate rayon;

use std::collections::HashMap;
use sodiumoxide::crypto;
// use sodiumoxide::crypto::hash;
use sodiumoxide::crypto::hash::sha256::Digest;
use sodiumoxide::crypto::hash::sha256;
use sodiumoxide::crypto::sign::{Signature, PublicKey, SecretKey};
use maidsafe_utilities::serialisation;
use rayon::prelude::*;

const GROUP_SIZE: usize = 8;

/// Error types.
///
/// Hopefully sodiumoxide eventually defines errors properly, otherwise this makes little sense.
#[allow(missing_docs)]
#[derive(Debug)]
pub enum Error {
    Serialisation(serialisation::SerialisationError),
    Crypto,
    Validation,
    Signature,
    Majority,
}

impl From<serialisation::SerialisationError> for Error {
    fn from(orig_error: serialisation::SerialisationError) -> Self {
        Error::Serialisation(orig_error)
    }
}

impl From<()> for Error {
    fn from(_: ()) -> Self {
        Error::Crypto
    }
}

/// Dummy data identifiers for this crate
#[allow(missing_docs)]
#[derive(RustcEncodable, RustcDecodable, PartialEq, Debug, Clone)]
pub enum BlockIdentifier {
    Type1(u64),
    Type2(u64),
    Link(Digest), // hash of group (all current close group id's)
}


impl BlockIdentifier {
    /// Define a name getter as data identifiers may contain more info that does
    /// not change the name (such as with structured data and versions etc.)
    /// In this module we do not care about other info and any validation is outwith this area
    /// Therefore we will delete before insert etc. based on name alone of the data element
    pub fn name(&self) -> Option<u64> {
        match *self {
            BlockIdentifier::Type1(name) => Some(name),
            BlockIdentifier::Type2(name) => Some(name),
            BlockIdentifier::Link(_) => None, // links do not have names
        }
    }

    /// Create a new chain link
    /// All group members should do this on each churn event
    /// All group members should also agree on the exact same members
    pub fn link(&mut self, group_ids: &mut [PublicKey]) -> Result<BlockIdentifier, Error> {
        let sorted = group_ids.sort();
        let serialised = try!(serialisation::serialise(&sorted));
        Ok(BlockIdentifier::Link(sha256::hash(&serialised)))
    }
}

/// Sent by any group member when data is `Put`, `Post` or `Delete` in this group
#[derive(RustcEncodable, RustcDecodable, PartialEq, Debug, Clone)]
pub struct NodeBlock {
    identifier: BlockIdentifier,
    proof: (PublicKey, Signature),
}

impl NodeBlock {
    /// Create a Block (used by nodes in network to send to holders of `DataChains`)
    pub fn new(pub_key: &PublicKey,
               secret_key: &SecretKey,
               data_identifier: BlockIdentifier)
               -> Result<NodeBlock, Error> {
        let signature =
            crypto::sign::sign_detached(&try!(serialisation::serialise(&data_identifier))[..],
                                        secret_key);

        Ok(NodeBlock {
            identifier: data_identifier,
            proof: (pub_key.clone(), signature),
        })

    }
}

/// The link is ordered
/// Block signatures are placed in the appropriate slot of the array
#[derive(RustcEncodable, RustcDecodable, PartialEq, Clone)]
pub enum Proof {
    Link([Option<(PublicKey, Signature)>; GROUP_SIZE]),
    Block([Option<Signature>; GROUP_SIZE]),
}

/// Used to validate chain `linksi`.
/// On a network churn event the latest `Block` is copied from the chain and sent
/// To new node. The `lost Nodes` signature is removed. The new node receives this - signs a
/// `NodeBlock  for this `BlockIdentifier` and returns it to the `archive node`
#[derive(RustcEncodable, RustcDecodable, PartialEq, Clone)]
pub struct Block {
    identifier: BlockIdentifier,
    proof: Proof,
}

impl Block {
    /// construct a block
    pub fn new(data_id: BlockIdentifier) -> Block {
        match data_id {
            BlockIdentifier::Link(_) => {
                Block {
                    identifier: data_id,
                    proof: Proof::Link([None; GROUP_SIZE]),
                }
            }
            _ => {
                Block {
                    identifier: data_id,
                    proof: Proof::Block([None; GROUP_SIZE]),
                }
            }

        }
    }

    /// name of block is name of identifier
    pub fn name(&self) -> Option<u64> {
        self.identifier.name()
    }

    /// Get the identifier
    pub fn identifier(&self) -> &BlockIdentifier {
        &self.identifier
    }

   // /// Add a NodeBlock (i.e. after accumulation there could be slow nodes)
   //pub fn add_node(&mut self, public_key: PublicKey, signature: Signature) -> Result<(), Error> {
   //
   //     let data = try!(serialisation::serialise(&self.identifier));
   //     if crypto::sign::verify_detached(&signature, &data[..], &public_key) {
   //         // let _ = self.proof.insert(public_key, signature);
   //         Ok(())
   //     } else {
   //         return Err(Error::Signature);
   //     }
   // }
}

/// Created by holder of chain, can be passed to others as proof of data held.
/// This object is verifiable if :
/// The last validation contains the majority of current close group
/// OR on network restart the nodes all must try and restart on
/// previous names. They can continue any validation of the holder of a chain.
/// This requires nodes to always restart as last ID and if there was no restart they are rejected
/// at vault level.
/// If there was a restart then the nodes should validate and continue.
/// N:B this means all nodes can use a named directory for data_store and clear if they restart
/// as a new id. This allows cleanup of old data_cache directories.
#[derive(RustcEncodable, RustcDecodable)]
pub struct DataChain {
    chain: Vec<Block>,
    group_size: u64,
}

impl DataChain {
    /// Create a new chain with no elements yet.
    pub fn new(group_size: u64) -> DataChain {
        DataChain {
            chain: Vec::new(),
            group_size: group_size,
        }
    }
    /// Nodes always validate a chain before accepting it
    pub fn validate(&mut self) -> Result<(), Error> {
        if self.chain.is_empty() {
            return Ok(());
        }
        Ok(try!(self.validate_majorities().and(self.validate_signatures())))
    }

    /// Size of close group (maximum proof size)
    pub fn group_size(&self) -> u64 {
        self.group_size
    }

    /// Add a Block to the chain
    pub fn add_block(&mut self, data_block: Block) -> Result<(), Error> {
        let data = try!(serialisation::serialise(&data_block.identifier));

        if let Some(last) = self.chain.last() {
            if !self.has_majority(last, &data_block) {
                return Err(Error::Majority);
            }
        }

        if !data_block.proof
            .iter()
            .all(|v| crypto::sign::verify_detached(v.1, &data[..], v.0)) {
            return Err(Error::Signature);
        }
        // TODO Remove any old copies of this data from the chain. It should not happen though
        self.chain.push(data_block);
        Ok(())
    }

    /// number of non-deleted blocks
    pub fn len(&self) -> usize {
        self.chain.len()
    }

    /// Contains no blocks that are not deleted
    pub fn empty(&self) -> bool {
        self.chain.is_empty()
    }

    /// Delete a block (will not delete a link)
    pub fn delete(&mut self, data_id: BlockIdentifier) {
        match data_id {
            BlockIdentifier::Link => {}
            _ => self.chain.retain(|x| x != data_id),
        }
    }

    /// Delete a block refered to by name
    /// Will either remove a block as long as consensus would remain intact
    /// Otherwise mark as deleted.
    /// If block is in front of container (`.fisrt()`) then we delete that.
    pub fn delete_name(&mut self, name: u64) {

        self.chain.retain(|x| if let Some(y) = x.name() {
            y != name
        } else {
            false
        });
    }

    fn validate_majorities(&self) -> Result<(), Error> {
        if self.chain
            .iter()
            .zip(self.chain.iter().skip(1))
            .all(|block| self.has_majority(block.0, block.1)) {
            Ok(())
        } else {
            Err(Error::Majority)
        }
    }

    fn validate_signatures(&self) -> Result<(), Error> {
        if self.chain
            .iter()
            .all(|x| {
                if let Ok(data) = serialisation::serialise(&x.identifier) {
                    x.proof
                        .iter()
                        .all(|v| crypto::sign::verify_detached(v.1, &data[..], v.0))
                } else {
                    false
                }
            }) {
            Ok(())
        } else {
            Err(Error::Signature)
        }
    }

    fn has_majority(&self, block0: &Block, block1: &Block) -> bool {
        block1.proof.keys().filter(|k| block0.proof.contains_key(k)).count() as u64 * 2 >
        self.group_size

    }
}



#[cfg(test)]

mod tests {
    use super::*;
    use sodiumoxide::crypto;
    use itertools::Itertools;
    use maidsafe_utilities::serialisation;
    use std::time;

    #[test]
    fn simple_node_data_block_comparisons() {
        let keys = crypto::sign::gen_keypair();
        let test_data1 = BlockIdentifier::Type1(1u64);
        let test_data2 = BlockIdentifier::Type1(1u64);
        let test_data3 = BlockIdentifier::Type2(1u64);
        let test_node_data_block1 = NodeBlock::new(&keys.0, &keys.1, test_data1).expect("fail1");
        let test_node_data_block2 = NodeBlock::new(&keys.0, &keys.1, test_data2).expect("fail2");
        let test_node_data_block3 = NodeBlock::new(&keys.0, &keys.1, test_data3).expect("fail3");
        assert_eq!(test_node_data_block1.clone(), test_node_data_block2.clone());
        assert!(test_node_data_block1 != test_node_data_block3.clone());
        assert!(test_node_data_block2 != test_node_data_block3);

    }

    fn create_data_chain(count: u64) -> DataChain {
        let group_size = 8;
        let mut chain = DataChain::new(group_size);

        let keys = (0..count + group_size)
            .map(|_| crypto::sign::gen_keypair())
            .collect_vec();




        let data_blocks = (0..count)
            .map(|x| {
                let mut block = if x % 2 == 0 {
                    Block::new(BlockIdentifier::Type1(x))
                } else {
                    Block::new(BlockIdentifier::Type2(x))
                };
                let data = serialisation::serialise(&block.identifier).expect("serialise fail");
                for y in 0..group_size {
                    let _ = block.add_node(keys[x as usize + y as usize].0,
                                           crypto::sign::sign_detached(&data[..],
                                                                       &keys[x as usize +
                                                                             y as usize]
                                                                           .1));
                }
                block
            })
            .collect_vec();

        let now = time::Instant::now();

        for i in data_blocks.iter() {
            chain.add_block(i.clone()).expect("chain fill failed");
        }
        println!("Took {:?}.{:?} seconds to add {:?} blocks",
                 now.elapsed().as_secs(),
                 now.elapsed().subsec_nanos(),
                 chain.len());
        chain
    }

    #[test]
    fn create_and_validate_chain() {
        let count = 1000;
        let mut chain = create_data_chain(count);

        let now1 = time::Instant::now();
        let _ = chain.validate().expect("validate failed");
        println!("Took {:?}.{:?} seconds to validate  {:?} blocks",
                 now1.elapsed().as_secs(),
                 now1.elapsed().subsec_nanos(),
                 count);

    }


    #[test]
    fn delete_all_and_validate() {
        let count = 100i64;
        let mut chain = create_data_chain(count as u64);

        assert_eq!(chain.len(), count as usize);
        assert_eq!(chain.chain.iter().map(|x| !x.deleted).count(),
                   count as usize);

        for i in 0..count {
            let _ = chain.delete(i as u64);
        }

        // internally all entries there, but marked deleted (entry 0 removed)
        assert_eq!(chain.chain.iter().map(|x| x.deleted).count(), 0);
        assert_eq!(chain.len(), 0);
        assert!(chain.empty());
    }

    #[test]
    fn delete_rev_and_validate() {
        let count = 100i64;
        let mut chain = create_data_chain(count as u64);

        assert_eq!(chain.len(), count as usize);
        assert_eq!(chain.chain.iter().map(|x| !x.deleted).count(),
                   count as usize);

        for i in count..0 {
            let _ = chain.delete(i as u64);
        }
        let _ = chain.delete(0);
        // internally all entries there, but marked deleted (entry 0 removed)
        assert_eq!(chain.chain.iter().map(|x| x.deleted).count() + 1,
                   count as usize);
        assert_eq!(chain.len() + 1, count as usize);
        assert!(!chain.empty());
        let _ = chain.validate().expect("validate failed");

    }



}