[−][src]Crate smart_access

Smart accessors

Let's begin with a few words on naming.

What is commonly named “smart pointer” is usually associated with trivial access (dereference) semantics and nontrivial clone/drop semantics.

Smart accessors provided by this crate also serve the purpose of accessing some data but in a different way: they have trivial drop semantics and nontrivial access semantics.

Note

If you do not want to read a long text, just proceed to the essential part of the documentation.

High level overview

The goal of this crate is twofold:

  • to offer one possible solution to the problem that the current (rustc 1.44) borrowchecker doesn't understand functions with multiple exit points (Polonius doesn't have this problem but it is not stable yet)
  • to provide a way to do bidirectional programming (when updating some view of data updates the data viewed to match the updated view)

If you are aqcuainted with optics in functional languages you can think of this crate as a minimalistic "lens" (more precisely, affine traversal) library using an imperative approach.

Usage examples

This crate already implements accessors for stdlib collections:

use smart_access::Cps;

let mut foo = vec![vec![1,2,3], vec![4,5,6]];

let bar = foo.at(0).at(1).replace(7);
assert!(foo == vec![vec![1,7,3], vec![4,5,6]]);
assert!(bar == Some(2));

let baz = foo.at(2).at(1).replace(8);
assert!(foo == vec![vec![1,7,3], vec![4,5,6]]);
assert!(baz == None);  // None is returned if path doesn't make sense

A somewhat more interesting example:

let mut foo = vec![1,2,3,4,5,6];

let bar = foo.at(1..=3).replace(vec![7,8]);
assert!(foo == vec![1,7,8,5,6]);
assert!(bar == Some(vec![2,3,4]));

An arbitrary mutating operation can be used instead of replacement:

let mut foo = vec![1,2,3,4,5,6];

let bar = foo.at(1..4).access(|v| { *v = vec![v.iter().sum()]; "baz" });
assert!(foo == vec![1,9,5,6]);
assert!(bar == Some("baz"));

Usage guide

To add a smart accessor to your own datatype Data you need to:

  • choose some type Index
  • add trait At<Index> to the type Data
  • implement access_at method
  • PROFIT!

Motivation (part I: lifetimes)

Suppose you have HashMap but without “Entry API” (Entry API is an implementation feature: not every datastructure in the wild provides any analogue).

Suppose also that you want to implement something akin to |m, k, v| m.entry(k).or_insert(v).

You could write

ⓘThis example deliberately fails to compile
// for simplicity we use usize keys in the examples below
fn or_insert<V>(hm: &mut HashMap<usize,V>, k: usize, v: V) -> &mut V {
    if let Some(v) = hm.get_mut(&k) { 
        return v; 
        // this is the first exit point but the borrow checker
        // doesn't distinguish between it and the second exit point
    }     

    hm.insert(k, v);  // Oops: hm is already borrowed! 
                      // (It _MUST_ be borrowed until the exit point)

    hm.get_mut(&k).unwrap()
    // the second exit point
}

but it would not compile because of limitations of the borrow checker.

It seems there is no way to write such a function without additional queries to the HashMap and without resorting to reference-pointer-reference conversions or other unsafe techniques.

This crate provides a not-so-clumsy workaround:

use std::collections::HashMap;
use smart_access::{At, Cps};

struct Ensure<K,V> { key: K, value: V }

impl<V> At<Ensure<usize, V>> for HashMap<usize, V> 
{
    type View = V;

    fn access_at<R, F>(&mut self, kv: Ensure<usize, V>, f: F) -> Option<R> where
        F: FnOnce(&mut V) -> R
    {
        if let Some(v) = self.get_mut(&kv.key) { 
            return Some(f(v)); 
            // We use so called CPS-transformation: we wrap each 
            // return site with a call to the provided function.
        } 

        self.insert(kv.key, kv.value);
        Some(f(self.get_mut(&kv.key).unwrap()))
    }
}

// now you can write or_insert (note the return type!):
fn or_insert<'a, V>(hm: &'a mut HashMap<usize,V>, k: usize, v: V) -> impl Cps<View=V> + 'a {
    hm.at(Ensure{ key: k, value: v })
}

There are some peculiarities though:

  • &mut V is eager: all code which is needed to obtain a reference to the value is executed at the site of access
  • impl Cps<View=V> is lazy: access is a zero-cost operation and all the machinery needed to reach the value is run at the site of modification
  • &'a mut V can be reborrowed, i.e. cloned for some subperiod of 'a, making it possible to modify the value referenced more than once
  • impl Cps<View=V> can be used only once but has batching. It comes in two flavors: compile-time batching which can't be used across any control flow and
    runtime batching which can't be used in no_std contexts

Note

The forementioned accessor Ensure { key: K, value: V } is defined in stdlib_impls simply as a pair (K,V) so for example you can write

map.at( ("foo".to_string(), "bar".to_string()) ).touch();

instead of

map.entry("foo".to_string()).or_insert("bar".to_string());

Motivation (part II: bidirectional programming)

We give a simple illustration: a bidirectional vector parser.

Not only can it parse a vector but also can print it back (note that two bidirectional parsers can be combined into a bidirectional translator from one textual representation to another).

A combinator library greatly facilitating writing such parsers can be implemented but it is not a (current-time) goal of this crate.

Note

Some function definitions in the following code are hidden. To see them look at the full module source.

// A little showcase:
assert!(vector_parser().bi_left((Some(vec![1,2,3]),"".into())) == "[1,2,3]".to_string());
assert!(vector_parser().bi_right(&mut "[1,2,3] foo".into()).0  == Some(vec![1,2,3]));
assert!(vector_parser().bi_right(&mut "[1,2,3,]bar".into()).0  == Some(vec![1,2,3]));
assert!(vector_parser().bi_right(&mut "[,]".into()).0          == None);
assert!(vector_parser().bi_right(&mut "[]".into()).0           == Some(vec![]));
assert!(vector_parser().bi_right(&mut "]1,2,3[".into()).0      == None);

// The code:
use smart_access::{At, Cps};

// a minimal set of parser combinators
#[derive(Clone)] struct _Number;
#[derive(Clone)] struct _Char(char);
#[derive(Clone)] struct _Many<T>(T);
#[derive(Clone)] struct _Optional<T>(T);
#[derive(Clone)] struct _Cons<Car,Cdr>(Car,Cdr);
#[derive(Clone)] struct _Iso<Parser,F,G>(Parser,F,G);

fn vector_parser() -> impl Bidirectional<String, Parse<Vec<usize>>> {
    let grammar = 
        _Cons(_Char('['), 
        _Cons(_Many(_Cons(_Number, _Char(','))),
        _Cons(_Optional(_Number),
              _Char(']'))));
     
    let from_grammar = |(_bl, (xs, (ox, _br))): (_, (Vec<_>, (Option<_>, _)))| 
    {
        xs.into_iter().map(|(x, _comma)| x).chain(ox.into_iter()).collect()
    };

    let to_grammar = |mut vec: Vec<_>| {
        let last = vec.pop();

        ('[', (vec.into_iter().map(|x| (x, ',')).collect(), (last, ']')))
    };

    _Iso(grammar, from_grammar, to_grammar)
}

trait Bidirectional<A,B> {
    fn bi_left(self, b: B) -> A;
    fn bi_right(self, a: &mut A) -> B;
}

type Parse<T> = (Option<T>, String);

// a very simplistic blanket implementation
impl<A,B,I> Bidirectional<A,B> for I where
    A: At<I, View=B> + Default,
    B: Clone
{
    fn bi_left(self, b: B) -> A {
        let mut a = A::default();

        a.at(self).access(|x| { *x = b; });

        a
    }

    fn bi_right(self, a: &mut A) -> B {
        a.at(self).access(|b| b.clone()).unwrap()
    }
}
 
impl At<_Number> for String {
    type View = Parse<usize>;

    // access_at is hidden
}

impl At<_Char> for String {
    type View = Parse<char>;

    // access_at is hidden
}
 
impl<V, Parser> At<_Many<Parser>> for String where
    String: At<Parser, View=Parse<V>>,
    Parser: Bidirectional<String, Parse<V>> + Clone,
    V: Clone,
{
    type View = Parse<Vec<V>>;

    // access_at is hidden
}

impl<V, Parser> At<_Optional<Parser>> for String where
    String: At<Parser, View=Parse<V>>,
    Parser: Bidirectional<String, Parse<V>> + Clone,
    V: Clone,
{
    type View = Parse<Option<V>>;

    // access_at is hidden
}

impl<V1, V2, P1, P2> At<_Cons<P1, P2>> for String where
    String: At<P1, View=Parse<V1>>,
    String: At<P2, View=Parse<V2>>,
    P1: Bidirectional<String, Parse<V1>> + Clone,
    P2: Bidirectional<String, Parse<V2>> + Clone,
    V1: Clone,
    V2: Clone,
{
    type View = Parse<(V1,V2)>;

    // access_at is hidden
}

impl<Parser, FromParser, ToParser, T, V> 
At<_Iso<Parser, FromParser, ToParser>> for String where
    String: At<Parser, View=Parse<T>>,
    Parser: Bidirectional<String, Parse<T>> + Clone,
    T: Clone,
    FromParser: FnOnce(T) -> V,
    ToParser: FnOnce(V) -> T,
{
    type View = Parse<V>;

    // access_at is hidden
}

Connection to functional programming

Rust type fn(&mut V) roughly corresponds to Haskell type v -> v.

Thus Rust access_at type could be written in Haskell (after some argument-swapping) as

accessAt :: ix -> (v -> (v,r)) -> t -> (t, Maybe r)

Suppose that access_at always returns Some(..). In such a case the Haskell type of access_at can be simplified to

accessAt :: ix -> (v -> (v,r)) -> t -> (t,r)

Its type is isomorphic to any of the following

ix -> t -> (v -> (v,r))     -> (t,r)  -- by arg-swapping
ix -> t -> (v->v, v->r)     -> (t,r)  -- by universal property of products
ix -> t -> (v->v) -> (v->r) -> (t,r)  -- by currying

Recall that a lens is uniquely defined by a getter and a setter:

type Lens t v = (t -> v, t -> v -> t)

This type is isomorphic to

type Lens t v = t -> (v, v -> t)

Notice that the types (v, v->t) and forall r. (v->v) -> (v->r) -> (t,r) are rather similiar. Define

right :: (v, v->t) -> (v->v) -> (v->r) -> (t,r)
right (v, v_t) v_v v_r = (v_t (v_v v), v_r v)

left :: (forall r. (v->v) -> (v->r) -> (t,r)) -> (v, v->t)
left f = (snd (f     id        id    ),  -- getter
    \v -> fst (f (\_ -> v) (\_ -> ())))  -- setter

Now we prove (left . right) ~ id:

left (right (v, v_t)) = (v, \x -> v_t x) ~ (v, v_t)

I.e. right is an injection: every value lens :: Lens t v can be presented as left (accessAt ix): it suffices to define

accessAt ix = right lens  -- modulo aforementioned type-fu

In fact the full type (with Maybe)

accessAt ix :: (v -> (v,r)) -> t -> (t, Maybe r)

can house any lens, prism or affine traversal.

Feature flags

Currently there are three features:

  • std_collections: Provides accessors for stdlib collections.
  • batch_rt: Provides runtime batching.
  • batch_ct: Provides compile-time batching. Compatible with no_std.

All features are enabled by default.

In a no_std environment the flags std_collections and batch_rt must be disabled.

Modules

core_impls

Implementation of At for core datatypes.

stdlib_impls

Implementation of At for stdlib collections. Toggled with std_collections feature.

Structs

AT

A “reference” to some “location”.

CpsBatch

A builder for complex mutations.

Traits

At

A smart access protocol.

Cps

Anything that can provide (or refuse to provide) a mutable parameter for a function.