Skip to content

Latest commit

 

History

History
781 lines (591 loc) · 22.5 KB

0000-partial_types.md

File metadata and controls

781 lines (591 loc) · 22.5 KB

Summary

Partial types proposal is a generalization on "partial borrowing"-like proposals (more correct name is "partial not borrowing" or "qualified borrowing" since Rust allows partial borrowing already).

This proposal is a universal road-map "how to do partial not consumption (including partial not borrowing) right", and not under the hood of the Rust compiler.

Advantages: maximum type safety, maximum type control guarantee, no ambiguities, flexibility, usability and universality.

Motivation

Safe, Flexible controllable partial parameters for functions and partial not consumption (including partial not borrowing) are highly needed and this feature unlock huge amount of possibilities.

But partial parameters are forbidden now, as qualified consumption: partial not borrowing, partial not referencing, partial not moving and partial initializing.

Partial Types extension gives to type-checker a mathematical guarantee that using simultaneously partial typed variable, it multiple references and borrowing is as safe as using them at a sequence.

And since it is guarantee by type, not by values, it has zero cost in binary.

Any type error is a compiler error, so no errors in runtime.

We could apply theoretically this extension to all Product Types (PT = T1 and T2 and T3 and ...).

So, most promised candidates are Structs and Tuples.

Guide-level explanation

Let we have a structure:

struct Point {
  x: f64,
  y: f64, 
  was_x: f64, 
  was_y: f64
}
let mut pfull = Point {x: 1.0, y: 2.0, was_x: 4.0, was_y: 5.0};

If we need to write a function, which use partial parameters:

// partial parameters
type PointJustX = %{x, %any} Point;
type PointJustWasX = %{was_x, %any} Point;

fn x_restore(&mut p1 : &mut PointJustWasX, & p2 : & PointJustX) {
    *p1.x = *p2.was_x;
}

Which mean that p1 parameters could use variables with any partial type of Point, which has permit access to field was_x and we don't care of rest fields. And p2 parameters could use variables with any partial type of Point, which has permit access to field x and we don't care of rest fields.

If we try to use same variable simultaneously for that, we must insert arguments partially - we cut type by %min access-filter:

x_restore(&mut %min pfull, & %min pfull);

If we wish to write same function via implementation, we need several selves!

impl Point {
    pub fn x_restore(&mut self1 : &mut %{saved_x, %any} Self, &self2 : & %{x, %any} Self) {
        *self1.x = *self2.saved_x;
    }

Why it is useful? If we need several functions which read common field, but mutually write different fields we could use them together!

pub fn mf1_rfc(&mut self1 : &mut %{fld1, %any} Self, &self2 : & %{common, %any} Self)  
{ /* ... */ }
    
pub fn mf2_rfc(&mut self1 : &mut %{fld2, %any} Self, &self2 : & %{common, %any} Self)  
{ /* ... */ }

And Partial Types have more. They are not limited to parameters/arguments only.

let ref_was = & %{was_x, was_y, %cut} pfull;

let brwd_now = &mut %{x, y, %cut} pfull;

let refref_was = & ref_was;

So we have a read-only reference to "was"-fields and mutable "now"-fields.

It is easy, useful and universal!

Reference-level explanation

  • [Partial types by type access]
  • [Detailed access]
    • [Detailed Struct Type]
    • [Detailed Primitive Types]
    • [Detailed Tuples]
    • [Detailed Arrays]
    • [Detailed Enum Type]
  • [Partial parameters]
    • [Partial parameter styles]
    • [Partial parameters on implementations]
    • [Several selfs]
    • [Partial parameters via Access variants]
    • [Partial parameter errors]
  • [Partial not consumption]
    • [Max access filter]
    • [Min access filter]
    • [Partially Initialized Variables]
  • [Private fields]

Partial types by type access

struct PointXY {
    x: f64,
    y: f64,
}
// case (A1)
let mut foo : mut PointXY = PointXY {x:11.0, y:2.0};

I propose to extend type system by adding type access to sub-type. So, our variable will have next type:

// case (A2)
// FROM case (A1)
// foo  : mut PointXY;
// foo  : mut %a PointXY;
// foo  : mut %full PointXY;

Lifetime variants are 'static (for static lifetime), '_(don't care lifetime) and any other 'b(some "b" lifetime).

By the same analogy, access has similar names and meanings: %full(full access, soft keyword), %_(don't care how partial access is, soft keyword), %empty or %! (no access, soft keyword) and any other %a(some "a" access).

If we omit to write type access, it means %full access.

Symbol % percent mean percent or part of the whole thing (variable in our case).

Note: It is highly recommended to deprecate operator % as a remainder function (it is still no ambiguities to write "\s+%\s+"), and replace it with another operator (for example: %mod / %rem / mod / rem) to not to be confused by type access. But it is not a mandatory.

Detailed access

Unfortunately, having variants of type access is not enough to write safe implementations or other non-abstract function declarations.

We need to have more specific access by detailed access.

Detailed Struct Type

Let's try simple uninhabited type

We need for this some new quasi-fields and some field access (which should be soft keywords).

struct Point {
    x: f64,
    y: f64,
    z: f64,
    t: f64,
    w: f64,
}

// case (C1)
let &mut p1 : &mut Point = Point {x:1.0, y:2.0, z:3.0, t:4.0, w:5.0};
    //
    // p1 : &mut Point;
    // p1 : &mut %full Point;
    // p1 : &mut %{*} Point;
    // p1 : &mut %{x, y, z, t, w} Point;

Where :

  • * is an "every field" quasi-field
// case (B1)
struct Nothing {}

let mut bar : mut Nothing = Nothing {};
    //
    // bar : Nothing  
    // bar : %full Nothing;
    // bar : %{*} Nothing;
    // bar : %{self} Nothing;
    // bar : %{%permit self} Nothing;

Where :

  • self a single quasi-field for uninhabited structs

It is a compile error if we try to %deny a ::self field!

We assume, that each field could be in one of two specific field-access - %permit and %deny.

We also must reserve as a keyword a %miss field-access for future ReExtendeded Partial Types, which allows to create safe self-referential types.

%permit is default field-access (if we omit to write specific field-access) and it means we have an access to this field and could use it as we wish. But if we try to access to %deny field it cause a compiler error.

// case (C2)
// FROM case (C1)
let &mut p1 : &mut Point = Point {x:1.0, y:2.0, z:3.0, t:4.0, w:5.0};
    //
    // p1 : &mut %{%permit *} Point;
    // p1 : &mut %{%permit *, %deny _};
    // p1 : &mut %{%permit {x, y, z, w}} Point;

Where :

  • %permit access
  • %deny access
  • {<fld1>, <fld2>, } is an field-set quasi-field
  • _ is a "rest of fields" quasi-field

As we see,

  • %empty : %{%deny *} or %empty : %{} access
  • %full : %{%permit *} or %full : %{*} access

Detailed Tuples

For Tuples we assume that every variable is a struct-like objects (even if it is not) and has unnamed numbered fields.

// case (C4)
let bar = (0i16, &5i32, "some_string");
    //
    // bar : (i16, &i32, &str);
    // bar : %full (i16, &i32, &str);
    // bar : %{*} (i16, &i32, &str);
    // bar : %{%permit {0,1,2}} (i16, &i32, &str);

Detailed Arrays

For Arrays we wish to assume that every variable is a tuple-like objects (even if it is not) and has unnamed numbered fields.

Unfortunately, Arrays are a bit magical, so it is unclear if we could represent it access like a tuple access.

Detailed Enum Type

What's about Enums? Enum is not a "Product" Type, but a "Sum" Type (ST = T1 or T2 or T3 or ..).

But this proposal grant some type access, not a value access!

So, all possible constructors are permitted!

Partial parameters

We add enough access, and could write partial parameters for function declarations:

// case (D1)
fn re_ref_t (& p : & %{t, %ignore _} Point) -> &f64 {
   &p.t
}

// case (D2)
fn refmut_w (&mut p : &mut %{w, %any} Point) -> &mut f64 {
   &mut p.w
}

Where :

  • %ignore is a "don't care which exactly" quasi filed-access (%_ is a whole type access and it is unclear if we could use it in both contents)

But %ignore _ quasi-filed-access of quasi-field looks annoying, so we simplify a bit adding %any : %ignore _.

Since using %ignore filed in the function body is unsafe by type (we have no guarantee, that some field is permitted), trying to use ignoring field is a compile error.

Now type access guarantee to compiler, that only some fields has an access inside function, but not the rest of them. So, no extra lock on self is needed, only for %permit fields.

Partial parameter styles

We could write partial parameters using different styles.

Default one:

// case (D3)
// FROM case (D1)
fn re_ref_t (& p : & %{t, %any} Point) -> &f64 {
   &p.t
}

// case (D5)
struct PointExtra {
    x: f64,
    y: f64,
    saved_x: f64,
    saved_y: f64,
}

fn x_store(&mut p1 : &mut %{saved_x, %any} PointExtra, & p2 : & %{x, %any} PointExtra) {
    *p1.saved_x = *p2.x;
}

fn x_restore(&mut p1 : &mut %{x, %any} PointExtra, & p2 : & %{saved_x, %any} PointExtra) {
    *p1.x = *p2.saved_x;
}

or use where clauses if access is extra verbose:

// case (D6)
// FROM case (D5)

fn x_store(&mut p1 : &mut %permit_sv_x PointExtra, & p2 : & %permit_x PointExtra) 
    where %permit_sv_x : %{saved_x, %any},
          %permit_x : %{x, %any}
{
    *p1.saved_x = *p2.x;
}

fn x_restore(&mut p1 : &mut %permit_x PointExtra, & p2 : & %permit_sv_x PointExtra) 
    where %permit_sv_x : %{saved_x, %any},
          %permit_x : %{x, %any}
{
    *p1.x = *p2.saved_x;
}

or add type synonym

// case (D7)
// FROM case (D5)

type PointSaveX = %{saved_x, %any} PointExtra;
type PointX = %{x, %any} PointExtra;


fn x_store(&mut p1 : &mut PointSaveX, & p2 : & PointX) {
    *p1.saved_x = *p2.x;
}

fn x_restore(&mut p1 : &mut PointX, & p2 : & PointSaveX) {
    *p1.x = *p2.saved_x;
}

Partial parameters on implementations

Writing Implementation parameters is mostly the same, but we use Self type as "outer Self" type:

// case (D8)
impl Point {
    pub fn x_refmut(&mut self : &mut %{x, %any} Self) -> &mut f64 {
        &mut self.x
    }

    pub fn y_refmut(&mut self : &mut %{y, %any} Self) -> &mut f64 {
        &mut self.y
    }
}

We could also use multiple sub-parameters of same parameter

// case (D9)
    pub fn xy_swich(&mut self : &mut %{{x, y}, %any} Self) {
        let tmp = *self.x;
        *self.x = *self.y;
        *self.y = tmp;
    }

Several selfs

If we want to include x_store and x_restore from case (D5) for implementation we find something weird: we need several selfs!

Sure, they must be a keywords. It could be either self1, self2, .. or self-1, self-2, .. or self#1, self#2 or self_ref, self_refmut or any other.

// case (E1)
trait St {

    fn x_store<%a, %b>(&mut self1: &mut %a Self, &self2: & %b Self);

    fn x_restore<%a, %b>(&mut self1: &mut %a Self, &self2: & %b Self);
}

// case (E2)
    pub fn x_store(&mut self1 : &mut %{x, %any} Self, &self2 : & %{saved_x, %any} Self) 
    {
        *self1.saved_x = *self2.x
    }

    pub fn x_restore(&mut self1 : &mut %{saved_x, %any} Self, &self2 : & %{x, %any} Self) {
        *self1.x = *self2.saved_x;
    }

Sure, if we use several selfs, their permit fileds access cannot overlap!

// case (E3)
    pub fn x2_store(&mut self1 : &mut %{x, %any} Self, &self2 : & %{x, %any} Self) {
        //                                 ^~~~~~                         ^~~~~
        // error: cannot overlap permit-field 'x' on self1 and self2
        *self1.x = *self2.x;
    }

Partial parameters via Access variants

We could write Traits with safe abstract functions (with no body), which consumes partial access type having only variants of type access.

// case (B1)
pub trait Upd {
    type UpdType;

    fn summarize<%a>(&self: & %a Self) -> String;

    fn update_value<%a>(&mut self : &mut %a Self, newvalue: UpdType);

    fn update_sametype<%a, %b>(&mut self : &mut %a Self, &another: & %b Self);
}

Partial parameter errors

Now compiler can catch "out of scope parameter" errors

// case (D10)
    pub fn xt_refmut(&self : &mut %{xt, %any} Self) -> &mut f64 {
        //                               ^~~~~~
        // error: no field 'xt' on type `Self`
        &mut self.xt
    }

Since using %ignore filed is unsafe by type (we have no guarantee, that some field is permitted), trying to use ignoring field is a compile error:

// case (D11)
    pub fn t_refmut(&self : &mut %{t, %any} Self) -> &mut f64 {
        &mut self.x
        //   ^~~~~~
        // error: cannot find value 'x' in this scope
    }

Compile could catch more dead code warnings

// case (D12)
    pub fn x_refmut(&self : &mut %{x, y, %any} Self) -> &mut f64 {
        //                                   ^~~~~~
        // warning: '#[warn(dead_code)]' field is never read: `y`
        &mut self.x
    }

Fortunately, these additions is enough to write any safe function declarations.

Partial not consumption

We wrote function declaration. Could we already partially not consume variables in arguments?

Fortunately, we could qualified consume implicit self arguments.

Unfortunately, implicit self argument is the only qualified consumed argument.

Exists 5 "pseudo-function" consumption for variables in expressions:

  • &mut - (mutable-)borrowing consumption
  • & - referential (immutable borrowing) consumption
  • <_nothing> - move consumption
  • <StrucName> initialized consumption
  • . access to the filed

Partial access to the field is already granted (exept arrays).

Rust consumer use same names for action and for type clarifications, so we follow this style.

We need to add access filter to them, omiting it mean %max filter. Since it is not possibe to consume more than %max, it has no sence to use %full instead!

%full means consumer consume all fields, %max consume all permited fields.

struct A { f1: String, f2: String, f3: String }
let mut x: A;

// case (F1)
let a: &mut String = &mut x.f1; // x.f1 borrowed mutably
let b: &String = &x.f2;         // x.f2 borrowed immutably
let c: &String = &x.f2;
// error:Can borrow again
let d: String = x.f3;           // Move out of x.f3

// case (F2)
// FROM case (F1)
let a: &mut String = &mut %full x.f1;
let b: &String = & %full x.f2;
let d: String =  %full x.f3;

Trying to consume %deny field is a compile error! The consumer DO NOT consume %deny EVER.

Resulted field access is the following:

↓filter / →access %permit %deny
%permit %permit !ERROR
%deny %deny %deny 
struct S5 { f1: String, f2: String, f3: String, f4: String, f5: String }
let mut x: S5;

// case (F3)
let ref1: &mut String = &mut x.f1;
//
let ref_x23 = & %{f2, f3, %deny _} x;
    //
    // ref_x23 : & %{%permit {f2, f3}, %deny {f1, f4, f5}} S5;
    //
let move_x45 = %{{f4, f5}, %cut} x;
    //
    // move_x45 : %{%permit {f4, f5}, %deny {f1, f2, f3}} S5;

But %deny _ quasi-filed-access of quasi-field looks annoying, so we simplify a bit adding %cut : %deny _.

Max access filter

What to do if we wish to create a reference to ref_x23. Do we need to write explicitly an access or exists implicit way?

No, we could use %max(or %id) - qualified safe filter with maximum permit-fields, but technically is an id filter to variable access:

var access %max
%permit %permit
%deny %deny

Having this we could write next implicitly

// FROM case (F1)
    // ref_x23: & %{%permit {f2, f3}, %deny {f1, f4, f5}} S5;

// case (F4)
let refref_x23 = & ref_x23;
// it mean '& %max ref_x23', not '& %full ref_x23'
//
    // refref_x23: && %{%permit {f2, f3}, %deny {f1, f4, f5}} S5;

Min access filter

For function argument we add another filter %min - qualified safe filter with minimum permit-fields, but it refers not to variable access, but to parameter access, so we could use it in arguments consumption only! It is an compile error if %min is written outside of contents!

param access %min
%permit %permit
%deny %deny
%ignore %deny

Implementations always consumes self by %min filter!

// FROM case (D3)
fn re_ref_t (& p : & %{t, %any} Point) -> &f64 {
   &p.t
}
let mut p1 : mut Point = Point {x:1.0, y:2.0, z:3.0, t:4.0, w:5.0};

// case (F5)
let reft = re_ref_t(& %min p1);


// case (F6)
    fn update_sametype<%a, %b>(&mut self : &mut %a Self, & another: & %b Self);
//
p1.update_sametype(& %min p2);


// case (F7)
    fn update_another<%a, %b>(& self : & %a Self, & mut another: & %b Self);
p3.update_sametype(&mut %min p2);

Partially Initialized Variables

We must have an ability to create partially initialized variables. So we need to add a filter-access to a constructor. Default access-fiter to constructor is %full, not %max.

struct Point {
    x: f64,
    y: f64,
    z: f64,
    t: f64,
    w: f64,
}

// case (G1)
let p1_full = Point {x:1.0, y:2.0, z:3.0, t:4.0, w:5.0};
    //
    // p1_full : Point;
    // p1_full : %full Point;

// case (G2)
let p_x = %{x, %cut} Point {x:1.0};
    //
    // p_x : %{%permit x, %deny _} Point;
    //

let p_yz = %{{y,z}, %cut} Point {y:1.0, z: 2.0};
    //
    // p_yz : %{%permit {y,z}, %deny _} Point;
    //

Also it would be nice if constructor allows several filler variables (which do not overlap permit-fields)

// case (G3)
let p_xyz = %max Point {..p_x, ..p_yz};
    //
    // p_xyz : %{%permit {x,y,z}, %deny {t,w}};

// case (G4)
let p2_full = Point {t:1.0, w:2.0, ..p_xyz};
    //
    // p2_full : Point;
    // p2_fill : %full Point;

A bit unclear how to fill unused fields, so we write unused values to a fill the type for tuple constructor

// case (G5)
let t4_02 = %{{0,2}, %cut} ("str", 1i32, &0u16, 0.0f32);
    //
    // t4_02 : %{%permit {0,2}, %deny {1,3}} (&str, i32, &u16, f32);

access filter could help to deconstruct types for matching:

// case (G6)
let opt_t4_1 = Some ( %{1, %cut} ("str", 1i32, &0u16, 0.0f32));
    //
    // opt_t4_1 : Option<%{%permit {1}, %deny {1,3}} (&str, i32, &u16, f32)>;
    //
    let Some (%max (_, ref y, _, _)) = opt_t4_1;
    //              ^~~~~~~~~~^~~^~~~ if we writee variables here, it cause an error

If we try to write not "_" on deny accessed fields, but a variable - it is a compile error.

Private fields

And finally, what to do with private fields?

If variable has private fields, it has always at access %hidden private quasi-field.

mod hp {
    pub struct HiddenPoint {
        pub x: f64,
        pub y: f64,
        z: f64,
        t: f64,
        w: f64,
    }
}

use hp::HiddenPoint;

// case (H1)
let p1 : HiddenPoint;
    // p1 : %full HiddenPoint;
    // p1 : %{%permit *} HiddenPoint;

Drawbacks

  • it is definitely not a minor change
  • type system became much more complicated

Rationale and alternatives

(A) A lot of proposals that are alternatives to Partial Types in a whole:

(B) Alternative for another names or corrections for Partial Types.

  • %empty or %! name
  • self1, self2, .. or self-1, self-2, .. or self#1, self#2. Or add only 2 specific selfs: self_ref, self_refmut

Prior art

Most languages don't have such strict rules for references and links as Rust, so this feature is almost unnecessary for them.

Unresolved questions

None known.

Future possibilities

ReExtendeded Partial Types

We could add additional ReExtendeded Partial Types for safe Self-Referential Types.

Theory of types do not forbid extension of Partial Type, but internal Rust representation of variables gives significant limitations on such action.

It is need the %miss(aka %deny but extendible) field access to initialized constructor consumption only. And additional "extender" %%=.

Partly self-referential types example:

struct SR <T>{
    val : T,
    lnk : & T, // reference to val
}

// case (FP1)
let x = %{%miss lnk, %permit _} SR {val : 5i32 };
    //
    // x : %{%miss lnk, %permit val} SR<i32>
    //
x.lnk %%= & x.val;
    //
    // x : SR<i32>;
    // x : %full SR<i32>;

And even AlmostFully self-referential types: And another shortcut %unfill : %miss _

struct FSR <T>{
    val : T,
    lnk : & %{%deny lnk, %permit val} FSR<T>, 
    // reference to almost self!
}

// case (FP2)
let x = %{val, %unfill} FSR {val : 5i32 };
    //
    // x : %{%miss lnk, %permit val} FSR<i32>;
    //
x.lnk %%= & %max  x;
    //
    // x : FSR<i32>;
    // x : %full FSR<i32>;

First difficulty - %max is no longer id, %max(on %miss) ~ %deny. Both filter-%permit on %miss and filter-%ignore on %miss must cause a compiler error for 3 main consumers.

Second and most difficult, that return consumption (yes, 6th type of consumers) from function could preserve %miss, so also we need filter %max_miss, where %max_miss(on %miss) ~ %miss!

// case (FP3)
// FROM case (FP2)
fn create_var()-> %{%miss lnk, %permit _} FSR {
    let x = %{val, %unfill} FSR {val : 5i32 };
        //
        // x : %{%miss lnk, %permit val} FSR<i32>
        //
    %max_miss return x; 
    // filter access before 'return' to not to confused with `move` consumer!
}

let y = create_var();
y.lnk %%= & %max  y;
    //
    // y : FSR<i32>;
    // y : %full FSR<i32>;