First implementation of K2V (#293)

**Specification:**

View spec at [this URL](https://git.deuxfleurs.fr/Deuxfleurs/garage/src/branch/k2v/doc/drafts/k2v-spec.md)

- [x] Specify the structure of K2V triples
- [x] Specify the DVVS format used for causality detection
- [x] Specify the K2V index (just a counter of number of values per partition key)
- [x] Specify single-item endpoints: ReadItem, InsertItem, DeleteItem
- [x] Specify index endpoint: ReadIndex
- [x] Specify multi-item endpoints: InsertBatch, ReadBatch, DeleteBatch
- [x] Move to JSON objects instead of tuples
- [x] Specify endpoints for polling for updates on single values (PollItem)

**Implementation:**

- [x] Table for K2V items, causal contexts
- [x] Indexing mechanism and table for K2V index
- [x] Make API handlers a bit more generic
- [x] K2V API endpoint
- [x] K2V API router
- [x] ReadItem
- [x] InsertItem
- [x] DeleteItem
- [x] PollItem
- [x] ReadIndex
- [x] InsertBatch
- [x] ReadBatch
- [x] DeleteBatch

**Testing:**

- [x] Just a simple Python script that does some requests to check visually that things are going right (does not contain parsing of results or assertions on returned values)
- [x] Actual tests:
  - [x] Adapt testing framework
  - [x] Simple test with InsertItem + ReadItem
  - [x] Test with several Insert/Read/DeleteItem + ReadIndex
  - [x] Test all combinations of return formats for ReadItem
  - [x] Test with ReadBatch, InsertBatch, DeleteBatch
  - [x] Test with PollItem
  - [x] Test error codes
- [ ] Fix most broken stuff
  - [x] test PollItem broken randomly
  - [x] when invalid causality tokens are given, errors should be 4xx not 5xx

**Improvements:**

- [x] Descending range queries
  - [x] Specify
  - [x] Implement
  - [x] Add test
- [x] Batch updates to index counter
- [x] Put K2V behind `k2v` feature flag

Co-authored-by: Alex Auvolat <alex@adnab.me>
Reviewed-on: https://git.deuxfleurs.fr/Deuxfleurs/garage/pulls/293
Co-authored-by: Alex <alex@adnab.me>
Co-committed-by: Alex <alex@adnab.me>

1 files changed, 190 insertions, 0 deletions

diff --git a/src/api/router_macros.rs b/src/api/router_macros.rs
new file mode 100644
index 00000000..8471407c
--- /dev/null
+++ b/src/api/router_macros.rs
@@ -0,0 +1,190 @@
+/// This macro is used to generate very repetitive match {} blocks in this module
+/// It is _not_ made to be used anywhere else
+macro_rules! router_match {
+    (@match $enum:expr , [ $($endpoint:ident,)* ]) => {{
+        // usage: router_match {@match my_enum, [ VariantWithField1, VariantWithField2 ..] }
+        // returns true if the variant was one of the listed variants, false otherwise.
+        use Endpoint::*;
+        match $enum {
+            $(
+            $endpoint { .. } => true,
+            )*
+            _ => false
+        }
+    }};
+    (@extract $enum:expr , $param:ident, [ $($endpoint:ident,)* ]) => {{
+        // usage: router_match {@extract my_enum, field_name, [ VariantWithField1, VariantWithField2 ..] }
+        // returns Some(field_value), or None if the variant was not one of the listed variants.
+        use Endpoint::*;
+        match $enum {
+            $(
+            $endpoint {$param, ..} => Some($param),
+            )*
+            _ => None
+        }
+    }};
+    (@gen_parser ($keyword:expr, $key:ident, $query:expr, $header:expr),
+        key: [$($kw_k:ident $(if $required_k:ident)? $(header $header_k:expr)? => $api_k:ident $(($($conv_k:ident :: $param_k:ident),*))?,)*],
+        no_key: [$($kw_nk:ident $(if $required_nk:ident)? $(if_header $header_nk:expr)? => $api_nk:ident $(($($conv_nk:ident :: $param_nk:ident),*))?,)*]) => {{
+        // usage: router_match {@gen_parser (keyword, key, query, header),
+        //   key: [
+        //      SOME_KEYWORD => VariantWithKey,
+        //      ...
+        //   ],
+        //   no_key: [
+        //      SOME_KEYWORD => VariantWithoutKey,
+        //      ...
+        //   ]
+        // }
+        // See in from_{method} for more detailed usage.
+        use Endpoint::*;
+        use keywords::*;
+        match ($keyword, !$key.is_empty()){
+            $(
+            ($kw_k, true) if true $(&& $query.$required_k.is_some())? $(&& $header.contains_key($header_k))? => Ok($api_k {
+                $key,
+                $($(
+                    $param_k: router_match!(@@parse_param $query, $conv_k, $param_k),
+                )*)?
+            }),
+            )*
+            $(
+            ($kw_nk, false) $(if $query.$required_nk.is_some())? $(if $header.contains($header_nk))? => Ok($api_nk {
+                $($(
+                    $param_nk: router_match!(@@parse_param $query, $conv_nk, $param_nk),
+                )*)?
+            }),
+            )*
+            (kw, _) => Err(Error::BadRequest(format!("Invalid endpoint: {}", kw)))
+        }
+    }};
+
+    (@@parse_param $query:expr, query_opt, $param:ident) => {{
+        // extract optional query parameter
+		$query.$param.take().map(|param| param.into_owned())
+    }};
+    (@@parse_param $query:expr, query, $param:ident) => {{
+        // extract mendatory query parameter
+        $query.$param.take().ok_or_bad_request("Missing argument for endpoint")?.into_owned()
+    }};
+    (@@parse_param $query:expr, opt_parse, $param:ident) => {{
+        // extract and parse optional query parameter
+        // missing parameter is file, however parse error is reported as an error
+		$query.$param
+            .take()
+            .map(|param| param.parse())
+            .transpose()
+            .map_err(|_| Error::BadRequest("Failed to parse query parameter".to_owned()))?
+    }};
+    (@@parse_param $query:expr, parse, $param:ident) => {{
+        // extract and parse mandatory query parameter
+        // both missing and un-parseable parameters are reported as errors
+        $query.$param.take().ok_or_bad_request("Missing argument for endpoint")?
+            .parse()
+            .map_err(|_| Error::BadRequest("Failed to parse query parameter".to_owned()))?
+    }};
+    (@func
+    $(#[$doc:meta])*
+     pub enum Endpoint {
+        $(
+            $(#[$outer:meta])*
+            $variant:ident $({
+                $($name:ident: $ty:ty,)*
+            })?,
+        )*
+    }) => {
+    $(#[$doc])*
+        pub enum Endpoint {
+            $(
+                $(#[$outer])*
+                $variant $({
+                    $($name: $ty, )*
+                })?,
+            )*
+        }
+        impl Endpoint {
+            pub fn name(&self) -> &'static str {
+                match self {
+                    $(Endpoint::$variant $({ $($name: _,)* .. })? => stringify!($variant),)*
+                }
+            }
+        }
+    };
+    (@if ($($cond:tt)+) then ($($then:tt)*) else ($($else:tt)*)) => {
+        $($then)*
+    };
+    (@if () then ($($then:tt)*) else ($($else:tt)*)) => {
+        $($else)*
+    };
+}
+
+/// This macro is used to generate part of the code in this module. It must be called only one, and
+/// is useless outside of this module.
+macro_rules! generateQueryParameters {
+    ( $($rest:expr => $name:ident),* ) => {
+        /// Struct containing all query parameters used in endpoints. Think of it as an HashMap,
+        /// but with keys statically known.
+        #[derive(Debug, Default)]
+        struct QueryParameters<'a> {
+            keyword: Option<Cow<'a, str>>,
+            $(
+            $name: Option<Cow<'a, str>>,
+            )*
+        }
+
+        impl<'a> QueryParameters<'a> {
+            /// Build this struct from the query part of an URI.
+            fn from_query(query: &'a str) -> Result<Self, Error> {
+                let mut res: Self = Default::default();
+                for (k, v) in url::form_urlencoded::parse(query.as_bytes()) {
+                    let repeated = match k.as_ref() {
+                        $(
+                            $rest => if !v.is_empty() {
+                                res.$name.replace(v).is_some()
+                            } else {
+                                false
+                            },
+                        )*
+                        _ => {
+                            if k.starts_with("response-") || k.starts_with("X-Amz-") {
+                                false
+                            } else if v.as_ref().is_empty() {
+                                if res.keyword.replace(k).is_some() {
+                                    return Err(Error::BadRequest("Multiple keywords".to_owned()));
+                                }
+                                continue;
+                            } else {
+                                debug!("Received an unknown query parameter: '{}'", k);
+                                false
+                            }
+                        }
+                    };
+                    if repeated {
+                        return Err(Error::BadRequest(format!(
+                            "Query parameter repeated: '{}'",
+                            k
+                        )));
+                    }
+                }
+                Ok(res)
+            }
+
+            /// Get an error message in case not all parameters where used when extracting them to
+            /// build an Enpoint variant
+            fn nonempty_message(&self) -> Option<&str> {
+                if self.keyword.is_some() {
+                    Some("Keyword not used")
+                } $(
+                    else if self.$name.is_some() {
+                        Some(concat!("'", $rest, "'"))
+                    }
+                )* else {
+                    None
+                }
+            }
+        }
+    }
+}
+
+pub(crate) use generateQueryParameters;
+pub(crate) use router_match;