[Feature Request] TypeTable

[jolestar]

🚀 Feature Request

Motivation

I have mentioned the idea of TypeTable in the documentation of Table, and I describe it in more detail here.

According to the implementation of Table(#150), we get:

module Std::Table {
    native struct Table<K, V: store> has store;
    native fun create<K, V>(): Table<K, V>
    native fun destroy<K, V>(t: Table<K, V>);
    native fun insert<K, V>(t: &mut Table<K, V>, k: &K, v: V);
    native fun remove<K, V>(t: &mut Table<K, V>, k: &K): V;
    native fun contains_key<K, V>(t: &Table<K, V>, k: &K): bool;
    native fun borrow<K, V>(t: &Table<K, V>, k: &K): &V;
    native fun borrow_mut<K, V>(t: &mut Table<K, V>, k: &K): &mut V;
}

But this Table can only use type K's value as the key, not type K as the key like borrow_global.

So I suggest introducing TypeTable with the basic operations described below:

module Std::TypeTable {
   native struct TypeTable has store;
   native fun create(): TypeTable
   native fun destroy(t: TypeTable);
   native fun insert<T>(t: &mut TypeTable, v: T);
   native fun remove<T>(t: &mut TypeTable<K>): T;
   native fun contains_key<T>(t: &TypeTable<T>): bool;
   native fun borrow<T>(t: &TypeTable): &T;
   native fun borrow_mut<T>(t: &mut TypeTable<T>): &mut T;
}

Now, we can define a AccountStorage struct in Move:

module Std::Account{
   struct AccountStroage{
      resources: TypeTable,
      moudles: Table<Identifer,vector<u8>>,
   }
}

Then we bind the table when Account create, such as:

module Std::Account{
    public fun create_account(addr: address){
        let resources = TypeTable::create();
        let modules = Table::create<Identifer,vector<u8>>();
        let account_storage = AccountStorage{
            resources,
            modules,
         };
         native_save_account(addr,account_storage);
    }

    public fun borrow<T>(addr:address):&T{
      let account_storage = native_get_account_staroge(addr);
      //This expression is not available in the current Move
      //We can not return ref like this, but we can ignore it now.
      return TypeTable::borrow<T>(&account_storage.resources);
    }

    public fun move_to<T>(signer:&signer, t:T){
      //if do not want to limit signer, can use address.
      let addr = Signer:address_of(signer);
      let account_storage = native_get_account_staroge(addr);
      TypeTable::insert(&mut account_storage.resources,t);
    }
   
    //We can update or deploy code in Move now, like `create2` in ethereum.
    public fun update_module(signer:&signer, name:Identifer, code:vector<u8>){
       let account_storage = native_get_account_staroge(addr);
       account_storage.modules.insert(name, code);
    }
}

• Now, borrow_global(address) = Account::borrow(address),
  and move_to(siger) = Account::move_to(siger), global_storage operation can been eliminate.
• The transaction ChangeSet are all table_changes.
• Every Move chain framework can customize their own account storage via the TypeTable and native function.

This feature can implement via an extension like Table and the backend storage is the same as Table, but TypeTable needs the same security guarantees as borrow_global.

We have two approaches to achieving this goal:

1. Introduce TypeTable into core instead of extension, add security restrictions to TypeTable::borrow similar to borrow_global.
2. Introduce the visibility of Struct and let the smart contract developer can control the access of Struct, see issue [Feature Request] Introduce Visibility to Struct #157.

[wrwg]

I like this proposal, a couple of thoughts:

• I wonder whether this would be better defined in parallel to the planned Map<T, R> type. The key table has one important difference to table: they are not large scale storage, as there is only a relative small number of types in a program.
• On the other hand, it has some similarity with tables -- you can't enumerate the keys, and neither the values.
• I think TypeTable might be better fitting as a name, as 'key" is a very generic notion.
• I'm wondering whether with this feature, you also intend to deprecate borrow_global?

[jolestar]

I like this proposal, a couple of thoughts:

• I wonder whether this would be better defined in parallel to the planned Map<T, R> type. The key table has one important difference to table: they are not large scale storage, as there is only a relative small number of types in a program.
• On the other hand, it has some similarity with tables -- you can't enumerate the keys, and neither the values.
• I think TypeTable might be better fitting as a name, as 'key" is a very generic notion.
• I'm wondering whether with this feature, you also intend to deprecate borrow_global?

• I think it similarity to Tables, can't enumerate the keys and keep the same storage API with Table.
• TypeTable is better, I will change it to TypeTable. There doesn't seem to be a similar structure in other program languages.
• I prefer to deprecate all global storage instructions, let the program explicitly indicate which table to operate on, rather than borrow or insert data from an implicit global store. Of course, borrow_global can be syntactic sugar for compatibility, but it actually gets the data from the resources table.

[sblackshear]

I think this is a cool idea and would love to see it fleshed out more. My experience with Move in Sui and the demand for tables elsewhere have made me question the prudence of using a type-indexed data structure as the top-level schema for global storage, but I think type-indexed maps can still be very useful in some cases.

[tnowacki]

Definitely a cool idea! I had been thinking for a while how a table system could replace global storage, and its rather tricky. The spots you will run into without always realizing is reference safety. It is easy to set something up without realizing it is unsafe, which is why it took us a while to build a static reference safety check in Move (and the first version of that still had dynamic reference checks for global storage references).

For example in this setup module Std::Account { public fun borrow<T>(addr:address):&T { ... } ... } is unsafe. The reference checks as is would have no way of knowing that doing something like

let x = Std::Account::borrow<R>(addr);
let R {.. } = Std::Account::move_from(addr); // unsafe! x invalidated
let f = x.f; 

(But maybe, @jolestar, you realized this and this is why Std::Account::move_from and Std::Account::borrow_global_mut were missing from your API :))

[wrwg]

Interesting thought @tnowacki and it reminds me what we need to think about if we actually would like to replace borrow_global and friends with TypeTable.

The API @jolestar is suggesting would not run into this problem because we always have a reference from which we derive subreferences, i.e. we do have borrow_mut<T>(tt: &mut TypeTable<T>): &mut T.

But how is this thing 'bootstrapped'? From somewhere you need to get a root reference to start with. Without additional measures, you can't get rid of borrow_global to obtain that root reference.

One alternative would be what Sui does, and also Async Move, and EVM Move (soonish). Top level entry points like transactions get passed in the root references from the environment. Only then we can make borrow_global obsolete...

[tnowacki]

Interesting thought @tnowacki and it reminds me what we need to think about if we actually would like to replace borrow_global and friends with TypeTable.

The API @jolestar is suggesting would not run into this problem because we always have a reference from which we derive subreferences, i.e. we do have borrow_mut<T>(tt: &mut TypeTable<T>): &mut T.

But how is this thing 'bootstrapped'? From somewhere you need to get a root reference to start with. Without additional measures, you can't get rid of borrow_global to obtain that root reference.

One alternative would be what Sui does, and also Async Move, and EVM Move (soonish). Top level entry points like transactions get passed in the root references from the environment. Only then we can make borrow_global obsolete...

Sorry, I wasn't specific enough in my reply, I now see how that was confusing (I'll edit my comment above).
I was referring to @jolestar's Std::Account proposal. The actual TypeTable itself should be safe.
I think the Std::Account was trying to answer this "bootstrapping" question you are referring to, which is indeed a tricky one. Passing in a table as a transaction/entry-point argument is a possible alternative