DEV Community: ProgramCrafter

Rust async is not very scary!

ProgramCrafter — Sun, 24 Mar 2024 18:42:38 +0000

If you know architecture of your code in advance, you can easily manage to make the code asynchronous!

Let's examine such an example: you want a function that downloads data from given URL, caches it for future use, and has a timeout for loading (so if remote server hangs the program can keep running). There are basically two solutions:

Create just an async caching-downloading function, then race it against timeout. This creates problem when function is not written in cancellation-safe way: it can be terminated at any .await point, which may be after data loading but before putting it into cache.
Apply timeout exactly to downloading part! We can do this even without factoring out a separate function - that is, without overhead on creating additional Future objects.

Coding

Let's suppose we have a separate cache for each user. If so, the downloader struct will look as below:

use tokio::time::{sleep, Duration};
use std::collections::HashMap;

mod mock;
use mock::{AsyncInChannel, AsyncOutChannel, Url};

struct CacheForUser {
    cache: HashMap<Url, String>,
    channel: AsyncOutChannel,
}

Then, we write the function we actually needed. Since downloading can timeout, it will return Result.

impl CacheForUser {
    async fn get_response(&mut self, url: Url) -> Result<(), &'static str> {
        if let Some(cached_response) = self.cache.get(&url) {
            self.channel.send(cached_response).await;
            return Ok(());
        }
        ...

Here comes the part where the deadline applies! Let's create the appropriate timeout-tracking Future.

tokio::select! awaits Futures (Promises in JS terminology) it gets and, like match block, processes the first one ready.

        let response = {
            tokio::pin! {let response_deadline = sleep(Duration::from_millis(600));}

            let in_channel;
            tokio::select! {
                c = AsyncInChannel::connect(url) => {in_channel = c;}
                _ = &mut response_deadline       => {return Err("timeout on connection");}
            }

            let data;
            tokio::select! {
                d = in_channel.read()       => {data = d;}
                _ = &mut response_deadline  => {return Err("timeout on reading data");}
            }
            data
        };        // timeout no longer applies

From the end of the block, we can be sure that timeout will not interrupt our work. Then, we don't need special consideration for order of cache write and await for sending data out.

        ...
        self.channel.send(&response).await;
        self.cache.insert(url, response);
        Ok(())
    }
}

Mocking

The easiest way to mock this is to have outbound channel write to Stdout, and inbound channel read some constant value (but with delay configured by Url). We don't even need to make Url a string during tests, we may just pass pair of millisecond delays there.

// mock.rs
use tokio::io::{stdout, Stdout, AsyncWriteExt};
use tokio::time::{sleep, Duration};


pub type Url = (u64, u64);

pub struct AsyncOutChannel {
    stdout: Stdout
}
impl AsyncOutChannel {
    pub fn new() -> AsyncOutChannel {
        AsyncOutChannel {stdout: stdout()}
    }
    pub async fn send(&mut self, s: &str) {
        self.stdout.write_all(s.as_bytes()).await
            .expect("IO error on stdout::write_all");
        self.stdout.flush().await
            .expect("IO error on stdout::flush");
    }
}


pub struct AsyncInChannel {
    read_time: u64
}
impl AsyncInChannel {
    pub async fn connect(url: Url) -> AsyncInChannel {
        sleep(Duration::from_millis(url.0)).await;
        AsyncInChannel {read_time: url.1}
    }
    pub async fn read(&self) -> String {
        sleep(Duration::from_millis(self.read_time)).await;
        "read complete\n".to_owned()
    }
}

Testing

Everything is quite straightforward here!

// main.rs
...

#[tokio::main]
async fn main() {
    let mut cfu = CacheForUser {cache: HashMap::new(),
        channel: AsyncOutChannel::new()};

    println!("100,700ms: {:?}", cfu.get_response( (100,700) ).await);
    println!("100,550ms: {:?}", cfu.get_response( (100,550) ).await);
    println!("500,150ms: {:?}", cfu.get_response( (500,150) ).await);
    println!("800,150ms: {:?}", cfu.get_response( (800,150) ).await);
    println!("100,150ms: {:?}", cfu.get_response( (100,150) ).await);
}

We'll see the following results:

100,700ms: Err("timeout on reading data")
100,550ms: Err("timeout on reading data")
500,150ms: Err("timeout on reading data")
800,150ms: Err("timeout on connection")
read complete
100,150ms: Ok(())

I highly wonder whether it's possible to write such code in languages like Python or JS and be sure about timeout working correctly!

User-inclination-guessing algorithms: registering a goal

ProgramCrafter — Wed, 20 Mar 2024 16:03:44 +0000

Reading post about Community Notes in X made me recall a recent idea and post it here.

It's commonly known that ranking algorithms based on estimating user's views and inclinations can be incredibly useful in recommendation systems, advertising, and content curation. But there must be other applications which do not require to create one's own social network, for instance!

There actually is a task which I believe to be a low-hanging fruit: predicting participant's score in olympiads; preferably with dataset available in the Internet, large scoring range and various tasks - that is, in informatics.

My thoughts about the prediction system

Olympiad tasks in informatics tend to use a lot of ideas and one or two algorithms, which makes them different both in topic and in difficulty. This may be represented by a vector in a high-dimensional space (based on task tags list on Codeforces, there might be at least 24 dimensions), where projection on each axis means usage of knowledge from the corresponding topic.

Let's make user embeddings also vectors in 24-dimensional space, and measure compatibility between a person and a task as projection of person embedding onto task vector, scaled down corresponding to the latter. If p_i is person's vector, t_j - task vector, then $compati,j=pi⋅tjtj2compat_{i,j} = \frac{p_i \cdot t_j}{t_j^2}$

I want score prediction to be straightforward, so I map compatibility from $[0; 1]$ range to $[0; 100]$ expected score, and everything outside that range to the closest bound.

I'm currently struggling how to fill variance, and guess that a good idea is to use one of embeddings' components for this. Competitions have an element of unpredictability, and I want to be able to distinguish predictions "participant will get 40-60 points" from "participant will get 20-80 points". And, while system is training, some variance is to be expected after all.

Calculation options

I'd be glad to go forward with Bayesian updates, but unfortunately the problem space is $R24(people+tasks)\reals^{24(people+tasks)}$ , and pieces of evidence are not independent as well; so it will be easier to use usual learning algorithms from neural networks.

I've also found out that calculating scores will be quite easy there! Let's demonstrate this on 4-dimensional embeddings, 3 tasks and 2 people.

    >>> import torch
    >>> tsk = torch.tensor([[1,0,0],[0,0,1],[0,3,0],[0,4,1]])
    >>> tsk
    tensor([[1, 0, 0],
            [0, 0, 1],
            [0, 3, 0],
            [0, 4, 1]])
    >>> ppl = torch.tensor([[1,1],[1,0],[1,0],[1,5]])
    >>> ppl
    tensor([[1, 1],
            [1, 0],
            [1, 0],
            [1, 5]])
    >>> (ppl.T @ tsk) * tsk.square().sum(0).reciprocal()
    tensor([[1.0000, 0.2800, 1.0000],
            [1.0000, 0.8000, 2.5000]])

So, for instance, we see that second person is well (but not exactly, only 80%) capable of solving second task.

Goal and call for help

I expect to create a somewhat working prediction system and I'm going to describe it in a separate post sometime this year! Bets whether I'll actually do this are on Manifold!

I'd like to hear if you have ideas on ML algorithm to use, or on domain to test the system next time. Criticism (except that such recommendation algorithms in social networks might be supposedly harmful) is also welcome!

Ethereum contracts system is inferior

ProgramCrafter — Sat, 09 Mar 2024 08:12:09 +0000

Let's suppose we are new to Ethereum (for instance, it is true for me) and want to write a smart contract! What should we do?

The logical thing is to start with architecture overview!

We see there are externally-owned and contract accounts; externally-owned can transfer ETH and tokens... wait... are tokens a thing defined by the blockchain structure? If tokens need a rework, blockchain will need to be changed?
Then, all accounts have nonce values; it has different meaning based on whether account is a smart contract (number of transactions sent versus number of contracts created). Also, the blockchain core somewhy takes responsibility of deduplicating transactions.
EVM code gets executed if the account gets a message call - are there other kinds of messages?
storageRoot – Sometimes known as a storage hash. A 256-bit hash of the root node of a Merkle Patricia trie that encodes the storage contents of the account (a mapping between 256-bit integer values) - contract storage is flat? What if one needed to store two mappings from user address to their data in a contract?
When going further, we notice variety of modifiers on functions (payable, view, pure, external...)

I believe system of TON Blockchain (The Open Network) here is much straighter:

TON operates on accounts as well. They are all smart contracts (contain code, balance and data).
Externally-owned Ethereum accounts translate to wallet contracts - special programs that keep user's public key in data and, upon reception of external messages, validate signature and perform the corresponding actions.
- Wallet contracts can be different and even created by developers, without any need for approval from someone else.
- Users can change signature validation method, using secp256k1 or any method they like instead of Ed25519. They may abandon asymmetric cryptography altogether!
- Wallets can include additional functionality, like restricting destination addresses to a specific set (so you can provide someone funds for staking without ability to spend them all on NFTs) or etc.
Messages are blobs of data, either imported into blockchain from the outer world (they are called external) or carrying value from one contract to another internally.
Transaction is an update on contract state when it processes incoming message. Contracts are isolated: to interact with others, they send outgoing messages.
- From validators' point of view, each transaction can be computed efficiently due to being related to one account only.
- From developers' point of view, interacting with malicious contract cannot interrupt normal operation of your (compare with reentrancy concerns in Ethereum) or cause gas exhaustion.
- From users' point of view, a malicious contract cannot do anything to their assets even if user is sending messages to it! TON, tokens (jettons) and NFTs are all kept secure.

Type system in Rust - subtypes without inheritance? pwned?

ProgramCrafter — Tue, 05 Mar 2024 18:05:59 +0000

Are there features in Rust type system beyond runtime-determined types of trait objects and ability to transmute them into others? Maybe some types have subtyping relation, which allows to safely cast them to super-s?

A fair warning: we're delving into The Rustonomicon, called also The Dark Arts of Unsafe Rust.

THE KNOWLEDGE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF UNLEASHING INDESCRIBABLE HORRORS THAT SHATTER YOUR PSYCHE AND SET YOUR MIND ADRIFT IN THE UNKNOWABLY INFINITE COSMOS.

Also, we will be assuming considerable prior knowledge, mostly on topic of references (wide and thin) and their lifetimes.

🦀 There are most definitely sub- and supertypes.

Cases of subtyping in Rust

trait Vehicle {}
trait Car : Vehicle {}

struct Chevle;
impl Vehicle for Chevle {}
impl Car for Chevle {}

Trait objects

&Chevle (read-only reference) may be casted either to &dyn Car or to &dyn Vehicle. After all, if we have read access to our car, then it's also access to an unspecified kind of car or a vehicle.
Why mutable references can't be casted so?
Let's suppose we have garage-variable that holds Chevle. If we were able to create &mut dyn Car reference to it, we'd be able to put Kia there, and after ref lifetime expiry Kia would stand in garage for Chevle!
&dyn Car to &dyn Vehicle, according to the same rationale (planned, since that requires changing vtables in wide pointers).

Lifetimes

fn bar<'a>() -> &'a str {
    let s: &'static str = "dev.to";
    s
}

References have lifetimes; a reference may have its lifetime shortened.
Why mutable references can change here?
I will demonstrate this with a sample code.

fn foo() {
  /* 'x */ {
    let mut i = 1;
    let p: &mut usize = &mut i;  // &'x mut usize
    /* 'y */ {
      let mut j = 4;
      p = &mut j;    // cannot assign twice to immutable variable `p`
    }
    *p += 1;
  }
}
fn bar() {
  /* 'x */ {
    let mut i = 1;
    let mut p: &mut usize = &mut i;  // &'x mut usize
    /* 'y */ {
      let mut j = 4;
      p = &mut j;
    }  // `j` does not live long enough, since its borrow `p` is used below 
    *p += 1;
  }
}

Generic types

That is a complex subject perhaps best explained by its page in The Rustonomicon.

F is covariant over T if T being a subtype of U implies that F is a subtype of F (subtyping "passes through")

F is contravariant over T if T being a subtype of U implies that F is a subtype of F

F is invariant over T otherwise (no subtyping relation can be derived)

A Rust safety bug

static UNIT: &'static &'static () = &&();

fn foo<'a, 'b, T>(_: &'a &'b (), v: &'b T) -> &'a T { v }

fn bad<'a, T>(x: &'a T) -> &'static T {
    let f: fn(_, &'a T) -> &'static T = foo;
    f(UNIT, x)
}

There's a code that promotes reference having any lifetime to 'static - one outliving the program, thus valid for its entire run - without memory allocation. You may notice that there's an ignored parameter creating unchecked assertion that 'b outlives 'a, which is the root of this issue. There are quite a few variants how to do this, so please remain aware (or don't use double references)!

Dynamic typing in Rust - inheritance and by-hand transmutation

ProgramCrafter — Sun, 03 Mar 2024 08:55:29 +0000

In the previous article, I've shown that some variables can have type that is determined (beyond that it's trait object) only at runtime. Let me remind how it went!

trait Animal {
  fn say(&self) -> &'static str;
  fn name(&self) -> &'static str;
}

struct Cat;
impl Animal for Cat {
  fn say(&self) -> &'static str {"meow"}
  fn name(&self) -> &'static str {"cat"}
}

struct Lion;
impl Animal for Lion {
  fn say(&self) -> &'static str {"roar"}
  fn name(&self) -> &'static str {"lion"}
}

fn main() {
  let cat = Cat;
  let animal: &dyn Animal = &cat;

  println!("{}", animal.say());  //  meow
}

Does Rust have inheritance mechanism?

It doesn't. Let's make our trait Animal subtrait of std::any::Any and try casting reference &dyn Animal to &dyn Any.

use std::any::Any;

trait Animal : Any {
  fn say(&self) -> &'static str;
  fn name(&self) -> &'static str;
}

struct Cat;
impl Animal for Cat {
  fn say(&self) -> &'static str {"meow"}
  fn name(&self) -> &'static str {"cat"}
}

struct Lion;
impl Animal for Lion {
  fn say(&self) -> &'static str {"roar"}
  fn name(&self) -> &'static str {"lion"}
}

fn main() {
  let cat = Cat;
  let animal: &dyn Animal = &cat;

  let r: &dyn Any = animal;
    //              ^^^^^^
    // error[E0658]: cannot cast `dyn Animal` to `dyn Any`, trait
    //   upcasting coercion is experimental
}

Our code doesn't compile: we cannot use subinterfaces interchangeably with their base traits. So, if we have arrays [&dyn Animal] and [&usize], we cannot merge them into [&dyn Any].

Is that a design decision or simply not-yet-implemented feature?

If you actually compile the code above, you see that error message links to Rust issue #65991 for more information: in short, upcasting is a feature not yet complete. Then, what's so hard there?

Reference of kind &dyn SomeTrait or &[ArrayValue] is actually two pointers long, and called "wide reference" (sometimes also "fat"). The first pointer there is the object's address, as is normal, and the second one contains some metadata. In case of trait objects, that's pointer to vtable.

What is a vtable?

It contains methods that can be invoked on the object. For instance, for trait Animal : Any the methods are Any::type_id, Animal::name and Animal::say. There are also three additional values, namely function drop_in_place (used to destroy object that has unknown size without moving it), type size and alignment.

To look at these, though, we'll need two things: "function labeller", converting function pointer to string, and a bit of unsafe code.

fn inspect_fn_ptr(f: usize) -> &'static str {
  if f == Cat::type_id  as usize {return "Cat::type_id";}
  if f == Lion::type_id  as usize {return "Lion::type_id";}

  if f == Cat::say  as usize {return "Cat::say";}
  if f == Cat::name as usize {return "Cat::name";}
  if f == Lion::say  as usize {return "Lion::say";}
  if f == Lion::name as usize {return "Lion::name";}
  "?"
}

use std::ptr::{read, write};
use std::mem::size_of;
unsafe fn inspect_vtable(reference: &dyn Animal) -> usize {
  let pr = &reference as *const &dyn Animal as *const usize;

  println!();
  println!("Inspecting metadata of animal {}", reference.name());
  println!("Size of reference: {}", size_of::<&dyn Animal>());

  const PTR_SIZE: usize = size_of::<usize>();
  let meta = read(pr.offset(1));

  println!("First  {PTR_SIZE} bytes are {}", read(pr));
  println!("Vtable {PTR_SIZE} bytes are {}", meta);

  let pm = meta as *const usize;
  println!("Vtable[0] = {} [{}::drop_in_place?]", read(pm), reference.name());
  println!("Vtable[1] = {} [size?]", read(pm.offset(1)));
  println!("Vtable[2] = {} [alignment?]", read(pm.offset(2)));
  println!("Vtable[3] = {} [{}]", read(pm.offset(3)), inspect_fn_ptr(read(pm.offset(3))));
  println!("Vtable[4] = {} [{}]", read(pm.offset(4)), inspect_fn_ptr(read(pm.offset(4))));
  println!("Vtable[5] = {} [{}]", read(pm.offset(5)), inspect_fn_ptr(read(pm.offset(5))));
  println!();

  meta
}

Let's also create function that can replace pointer to vtable. Obviously it is unsafe since type we've got metadata from can be incompatible.

unsafe fn change_vtable(reference: &mut &dyn Animal, meta: usize) {
  let pr = reference as *mut &dyn Animal as *mut usize;
  write(pr.offset(1), meta);
}

And it's time for the main function!

use std::hint::black_box;
fn main() {
  let cat = Cat;

  // black boxing just because reference becomes invalid later
  // and I don't need optimizations inlining Cat everywhere
  let mut animal: &dyn Animal = black_box(&cat);

  unsafe {inspect_vtable(animal)};
  println!("{}", animal.say());

  unsafe {change_vtable(&mut animal, inspect_vtable(&Lion))};
  println!("{}", animal.say());
}

The output I have got is here:

Inspecting metadata of animal cat
Size of reference: 16
First  8 bytes are 140725137267895
Vtable 8 bytes are 93885456622352
Vtable[0] = 93885456308624 [cat::drop_in_place?]
Vtable[1] = 0 [size?]
Vtable[2] = 1 [alignment?]
Vtable[3] = 93885456308512 [Cat::type_id]
Vtable[4] = 93885456308656 [Cat::say]
Vtable[5] = 93885456308672 [Cat::name]

meow

Inspecting metadata of animal lion
Size of reference: 16
First  8 bytes are 93885456560128
Vtable 8 bytes are 93885456622432
Vtable[0] = 93885456308624 [lion::drop_in_place?]
Vtable[1] = 0 [size?]
Vtable[2] = 1 [alignment?]
Vtable[3] = 93885456308480 [Lion::type_id]
Vtable[4] = 93885456308688 [Lion::say]
Vtable[5] = 93885456308704 [Lion::name]

roar

So, we've successfully "transmuted" cat to lion. Now it's quite clear why trait upcasting is not that easy: it requires to rearrange the whole vtable.

Somewhat dynamic typing in Rust - magic of traits

ProgramCrafter — Sat, 02 Mar 2024 13:57:14 +0000

Rust is statically typed language, they say. All the types are known at compilation time, they say.

That's not quite true, and I'd like to demonstrate counterexamples!

Functions working on slices (arrays of unknown size)

fn foo(arr: &mut [usize]) {
    arr[arr.len() - 1] += arr[0];
}

fn main() {
    let mut v: [usize; 4] = [7, 5, 1, 3];
    foo(&mut v);
    println!("{v:?}");    //  [7, 5, 1, 10]
}

As an example, I'll use a function that adds value of first array element to the last one. Note that it takes &mut [usize] - thing called "slice", which doesn't have length indication at all!

If you change length of array v (suitably adding or removing elements in brackets), function foo will be able to process it just as well. Thus, it can be said that foo works on values of different types!

Functions on trait objects

use std::any::Any;

fn foo(something: &dyn Any) -> &'static str {
    if something.is::<char>() {"char"} else {"not-char"}
}

fn main() {
    println!("1: {}", foo(&1));       //  1: not-char
    println!("'k': {}", foo(&'k'));   //  'k': char
}

Any is an interesting Rust trait, implemented by almost all types. It allows you to store references to values of different type in a single container, and then to check if value has a certain type.

Why not all types implement Any?
Any depends on all types having unique IDs. References (and, by extension, types containing references) are bounded by lifetimes, which are hard to put into numbers.

But perhaps the most interesting fact is that you can pass reference to a certain object (for instance, 1 of usize) to foo, it will automatically convert to reference to dyn Any, and the code will compile!

What is '&dyn Any', is there '&Any' as well?
dyn Trait represents an object of some type - unknown at compilation time, but certainly implementing Trait. Those objects may have different sizes and thus cannot be stored normally (passed to function or returned, as well). They must be behind a "smart pointer" - reference or Box, for instance.

There is also impl Trait, representing object of type known at compilation time that implements Trait as well. They may be used without restrictions.

fn maybe_max(a: impl Into<usize>, b: impl Into<usize>) -> usize {
    std::cmp::max(a.into(), b.into())
}

In next post, I'll describe how Rust works with this dynamic typing in more details!

Hack-TON-berfest 2023 Maintainer Post

ProgramCrafter — Tue, 27 Feb 2024 19:06:07 +0000

Intro

Hacktoberfest 2023 was the first where I participated actively. I had quite a lot of projects with easy tasks available, and that led to decision to be a maintainer. Also, TON blockchain community ran its branch of the event, called Hack-TON-berfest.

Project

My successful maintaining-ship was with repository MulDEX (system for swapping different currencies, but allowing to swap any supported to any other without intermediate exchanges). I have already written post about maths behind it, by the way.

ProgramCrafter / MulDEX

MulDEX

Project structure

contracts - source code of all the smart contracts of the project and their dependencies.
wrappers - wrapper classes (implementing Contract from ton-core) for the contracts, including any [de]serialization primitives and compilation functions.
tests - tests for the contracts.
scripts - scripts used by the project, mainly the deployment scripts.

How to use

Build

npx blueprint build or yarn blueprint build

Test

npx blueprint test or yarn blueprint test

Deploy or run another script

npx blueprint run or yarn blueprint run

Add a new contract

npx blueprint create ContractName or yarn blueprint create ContractName

View on GitHub

Three pull requests were there:

Smart contract reimplementation in a lower-level language, FunC. It was definitely needed, since the language I've chosen first didn't support one of TON features I needed.
Build workflow (by @MKdir98). That's always nice to have in a project!
Deploy wrapper (by @nonam3e): to start system easily.

Highs and Lows

There was a couple of exciting moments, for instance when I received a pizza for contributions! I haven't got the biggest number of contributors, though, I guess I can blame the fact that I didn't attend online workshops - nor wrote posts about my projects 😄

Next time, I'll be sure to tell everyone around about projects I maintain!

Example of Rust attribute macros: data serialization (part 2 - enums)

ProgramCrafter — Tue, 27 Feb 2024 18:43:39 +0000

In the previous article, I demonstrated how serialization function for a struct can be auto-generated.

#[tlb_serializable(u 4 3bit, workchain, hash_high, hash_low)]
pub struct Address {
    workchain: u8,      hash_high: u128,      hash_low: u128
}

{
    let mut result = ::std::vec![];
    result.push("u 4 3bit".to_owned());
    {   let mut s_field = crate::ton::CellSerialize::serialize(&self.workchain);
        result.append(&mut s_field);   }
    {   let mut s_field = crate::ton::CellSerialize::serialize(&self.hash_high);
        result.append(&mut s_field);   }
    {   let mut s_field = crate::ton::CellSerialize::serialize(&self.hash_low);
        result.append(&mut s_field);   }
    result
}

Now, let's do the same for enums!

I feel like this article may be quite hard to understand; please respond in comments whether it was really, or was I too scared?

Designing the solution

Variants of enum are determined by tag, which is stored before data of variant itself. In TON, that tag may actually be any, even non-unique or empty - if you can make your smart contracts parse that.

So, our code needs to get how to represent the tags. Let's use normal Rust attribute #[repr(u**)] if the tag is wanted or custom "attribute" #[tlb_assert_unsafe(items_prefixes_nonoverlap)] if it's not.

After that, we will also need description how to serialize each variant of the enumeration. #[tlb_item_serializable()] will be a logical name for such an attribute.

Coding

Let's start with a simple template,

#[proc_macro_attribute]
pub fn tlb_enum_serializable(_: OldTokenStream, item: OldTokenStream)
        -> OldTokenStream {
    let mut input: ItemEnum = parse_macro_input!(item);
    let name = input.ident.clone();
    ...
}

Parsing enum attributes

For clarity (including error messages), we define our enum determining if user wants automatically added tag in enum serialization, and if he does, then what numeric type is used.

Also, as we don't create procedural attribute #[tlb_assert_unsafe()], we need to remove it so Rust doesn't have to search for it. We can use retain function on input.attrs just for this!

#[derive(Debug)] enum TlbPrefix {Wanted(String), NotWanted}

    ...
    let mut need_prefix: Option<TlbPrefix> = None;
    input.attrs.retain(|attr| {
        if attr.path().is_ident("tlb_assert_unsafe") {
            ...
        } else ...
    });

Attributes can be empty, contain an assignment/comparison (for instance, #[cfg(feature = "std")], or contain arbitrary token sequences. We're interested in the third kind.

...
input.attrs.retain(|attr| {
    if attr.path().is_ident("tlb_assert_unsafe") {
        let Meta::List(MetaList {tokens: ref tokens_assert, ..}) = attr.meta else {
            panic!("#[tlb_assert_unsafe] attribute must have argument with the specific assertion");
        };
        let assertion = tokens_assert.to_string();
        if assertion == "items_prefixes_nonoverlap" {
            assert!(need_prefix.is_none());
            need_prefix = Some(TlbPrefix::NotWanted);
            false    // don't keep the attribute on enum
        } else {
            println!("Unknown assertion {assertion:?}");
            true
        }
    } else ...

The second half is written in pretty much same way:

    ... else if attr.path().is_ident("repr") {
        assert!(need_prefix.is_none(), "Two #[repr] attributes on enum are not supported");
        let Meta::List(MetaList {tokens: ref tokens_type, ..}) = attr.meta else {
            panic!("#[repr] attribute must have argument specifying the type");
        };
        need_prefix = Some(TlbPrefix::Wanted(tokens_type.to_string()));
        true    // we retain #[repr] attribute for Rust's use
    } else {
        true
    }
});

After iterating over enum's attributes, we now have field need_prefix. Let's assert it contains something and go on.

let need_prefix: TlbPrefix = need_prefix.expect(
    "Don't know how to differentiate tags of the enum");

Going over each variant

let mut variant_index = 0;
let variant_generators: Vec<V2TokenStream> = input.variants.iter_mut().map(|variant| {
    let mut store = None;
    variant.attrs.retain(|attr| {
        if !attr.path().is_ident("tlb_item_serializable") {return true;}
        let Meta::List(MetaList {tokens: ref tokens_tlb, ..}) = attr.meta else {
            panic!("#[tlb_item_serializable] attribute must have argument with the specific serialization");
        };
        let tlb = tokens_tlb.to_string();

        assert!(store.is_none(), "multiple serialization definitions found");
        store = Some(create_serialization_code(&tlb, &variant.fields));
        false
    });
    let store = store.expect(&format!("serialization definition for variant {} is required", variant.ident));
    ...

For now, we've determined how to store inner data of each option. But we may also need to store discriminant, and that's why we need variant_index.

    ...
    if let Some((_, Expr::Lit(ref idx))) = variant.discriminant {
        if let Lit::Int(ref discriminant) = idx.lit {
            variant_index = discriminant.base10_parse::<u64>()
                .unwrap();
        }
    };
    let store_tag = match need_prefix {
        TlbPrefix::NotWanted => quote! {},
        TlbPrefix::Wanted(ref discr_type) => {
            let s = &discr_type[1..];    // u64 -> 64
            quote! {
                result.push(::std::format!("u {} {}bit",
                    #variant_index, #s));
            }
        },
    };
    variant_index += 1;

You may think at this point everything is ready to create match branch for each option. Something isn't ready yet: we need to unpack data into variables + tell create_serialization_code function that self is not required. The latter can be done with a simple boolean flag, and the former is written so:

    let vident = &variant.ident;
    let fields_unpacker: Vec<_> = variant.fields.iter().map(|field| {
        let id = field.ident.clone().expect("unnamed field in enum");
        quote!{ #id, }
    }).collect();

    quote! {
        #name::#vident {#(#fields_unpacker)*} => {
            #store_tag
            #store
        }
    }

Combining all the parts

#[proc_macro_attribute]
pub fn tlb_enum_serializable(_: OldTokenStream, item: OldTokenStream)
        -> OldTokenStream {
    let mut input: ItemEnum = parse_macro_input!(item);
    let name = input.ident.clone();

    let mut need_prefix: Option<TlbPrefix> = None;
    input.attrs.retain(|attr| { ... });
    let need_prefix: TlbPrefix = need_prefix.expect(
        "Don't know how to differentiate tags of the enum");

    let mut variant_index = 0;
    let variant_generators: Vec<V2TokenStream> =
        input.variants.iter_mut().map(|variant| {...})
        .collect();

    // we need that because we could've removed some attributes
    let mut result: OldTokenStream = input.to_token_stream().into();
    result.extend(OldTokenStream::from(quote! {
        impl crate::ton::CellSerialize for #name {
            fn serialize(&self) -> ::std::vec::Vec<::std::string::String> {
                let mut result = ::std::vec![];
                match &self {
                    #(#variant_generators)*
                }
                result
            }
        }
    }));
    result
}

The full code is on my Github - ProgramCrafter/tlb-rust-serialization.

Isn't it a good idea to predict software bugs with markets?

ProgramCrafter — Tue, 27 Feb 2024 18:25:51 +0000

Can we estimate amount of bugs in a big project before finding them? Actually, it seems that we can, and there is a suitable thing to do so - prediction markets. They allow users to quantify their beliefs a bit, while rewarding correct predictions with something... like right to brag!

I know of one such platform, called Manifold Markets.
(if you'd like an affiliate link, here's one: Manifold, or enter that @AnT (Ender Ting) is the referrer)

About Manifold
Users have play-money (disconnected from real world or crypto) that's called mana. On markets, one can buy Yes or No shares to change the odds of an answer. The odds are reflected in the market price changing how much Yes and No cost. Buying pressure on each side causes the market to converge to a price that accurately forecasts the future.

Examples of markets about software bugs

How precise is that?

If someone believes they feel a bug and others don't, they will be incentivized to correct the market, so finally it is going to converge to true probability.

If you believe you have no bugs, you may put a limit order on very low probability, saying "we think probability of error in our code is less than 5%", for instance. Then if someone finds a bug, he'll very likely report it to get winnings from the market. It's a bit similar to bug bounty (but no replacement to real-world bounty, of course).

Speaking about precision, Manifold is only a bit overconfident on average questions. Here's its calibration graph:

I'd like to hear your thoughts, whether your projects will or will not use prediction markets to find bugs, whatever else! I will also feel honoured to bet on your projects.

Example of Rust attribute macros: data serialization (part 1 - structures)

ProgramCrafter — Sat, 24 Feb 2024 15:32:11 +0000

Recently, I decided to create Rust library that allows to serialize objects into "cells" (generally, bytes) for usage in TON blockchain. There are two obvious ways to do that:

For each structure, write out buffer.store_value(self.a); buffer.store_value(self.b); .... For parsing that, repeat the work once again.

Example

impl Serializable for InternalMessageHeader {
  fn write_to(&self, cell: &mut BuilderData) -> Result<()> {
    cell
        .append_bit_zero()?              //tag
        .append_bit_bool(self.ihr_disabled)?
        .append_bit_bool(self.bounce)?
        .append_bit_bool(self.bounced)?;

    self.src.write_to(cell)?;
    self.dst.write_to(cell)?;

    self.value.write_to(cell)?;         //value: CurrencyCollection

    self.ihr_fee.write_to(cell)?;       //ihr_fee
    self.fwd_fee.write_to(cell)?;       //fwd_fee

    self.created_lt.write_to(cell)?;    //created_lt
    self.created_at.write_to(cell)?;    //created_at

    Ok(())
  }
}

(quoted from ton-labs-block / messages.rs). In particular, notice ? each time. It's most definitely not normal if data serialization can fail in the middle.

Create macros that will take order in which to store fields and create serialization code automatically. When deserialization is added, it will certainly match the order of writes so fields don't mix up.
Use Serde and just write custom serializer. Unfortunately, it doesn't allow to specify order of fields serialization, nor compile-time checks that serialization could be fallible or infallible.

Rust has two kinds of macros: by-example (defined with macro_rules!) and procedural (they can be attached as attributes to structs, enums, etc, just like #[derive(...)]). I've thought that procedural macros will look cleaner in place of usage.

An attribute macros accepts two sequences of tokens: whatever is within its invocation (for Derive, that would be list of traits), and what it is applied to.

Required libraries

We need three external modules: quote+proc-macro2 to avoid forming token sequences by hand and instead having ability to substitute variables into the template, plus syn to parse code we receive (for instance, to iterate over enum variants).

[package]
name = "tlb_macro"
version = "0.1.0"
edition = "2021"

[lib]
proc-macro = true

# See more keys and their definitions at
#     https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
syn = {version = "^2.0.50", features = ["full"]}
quote = "^1.0.8"
proc-macro2 = "^1.0.78"

extern crate proc_macro;
use syn::{parse_macro_input, DeriveInput, Data, Expr,
    Fields, Ident, ItemEnum, Meta, MetaList, Lit, spanned::Spanned};
use quote::{quote_spanned, quote, ToTokens};
use proc_macro2::Span;

use std::collections::HashMap;

type OldTokenStream = proc_macro::TokenStream;
type V2TokenStream = proc_macro2::TokenStream;

Entry point

Let's call our attribute tlb_serializable (after TL-B language), and decide it should be used as follows:

#[tlb_serializable(u 4 3bit, workchain, hash_high, hash_low)]
pub struct Address {
    workchain: u8,
    hash_high: u128,
    hash_low: u128
}

Then, main function will look so:

#[proc_macro_attribute]
pub fn tlb_serializable(attr: OldTokenStream, mut item: OldTokenStream) -> OldTokenStream {
    let struct_item = item.clone();
    let input: ItemStruct = parse_macro_input!(struct_item);
    let name = input.ident;

    let serializers = create_serialization_code(
        &attr.to_string(), &input.fields);
    item.extend(OldTokenStream::from(quote! {
        impl crate::ton::CellSerialize for #name {
            fn serialize(&self) -> ::std::vec::Vec<::std::string::String> {
                let mut result : ::std::vec::Vec<::std::string::String> = ::std::vec![];
                #serializers
                result
            }
        }
    }));

    item
}

We parse the incoming thing as struct, panicking if it is not (this would result in compilation error, noting what went wrong). Then we take its name to substitute into impl template (what is serialization trait implemented on), and pass fields into next function. With the resulting sequence of store-statements, we extend struct definition (attribute macros replaces code it is applied to with whatever it returns).

The code generator itself

fn create_serialization_code(attr: &str, struct_fields: &Fields)
        -> V2TokenStream {
    let Fields::Named(ref fields) = struct_fields else {
        panic!("For unambiguous parsing, normal structs must consist of named fields");
    };
    let mut field_spans: HashMap<String, (Ident, Span)> = HashMap::new();
    for field in fields.named.iter() {
        let id = field.ident.clone().expect("unnamed field");
        field_spans.insert(id.to_string(), (id, field.span()));
    }

    // Mapping each part of serialization TL-B to block of code that stores value into cell
    let serializations = attr.split(",").map(|part_whitespaced| {
        let part = part_whitespaced.trim();
        if part.is_empty() {
            quote!{}
        } else if part.starts_with("u ") {
            quote! { result.push(#part.to_owned()); }
        } else {
            let (name, span) = &field_spans[part];
            quote_spanned! {span.clone()=>{
                let mut s_field = crate::ton::CellSerialize::serialize(&self.#name);
                result.append(&mut s_field);
            }}
        }
    });

    // Constructing function of all those code chunks
    quote!{{
        #(#serializations)*
    }}
}

The code is quite straightforward! First, we take a list of fields in struct and store identifier + span for each of them. Identifier is just handy not to create extra time, while span allows to direct any errors onto the field definition instead of macros:

error[E0277]: the trait bound `i128: CellSerialize` is not satisfied
  --> src\main.rs:17:9
   |
17 |         hash_high: i128,
   |         ^^^^^^^^^ the trait `CellSerialize` is not implemented for `i128`

If we replace quote_spanned! with quote!, we won't see even name of field that caused the error:

error[E0277]: the trait bound `i128: CellSerialize` is not satisfied
  --> src\main.rs:14:5
   |
14 |     #[tlb_serializable(u 4 3bit, workchain, hash_high, hash_low)]
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `CellSerialize` is not implemented for `i128`

One more detail I feel I should mention, is why in some places there is quote!{ code } and somewhere quote!{{ code }}. The answer is simple: the second option creates a separate block of code that isolates any local variables which are there so they don't clash with ones defined in serialization of the next field.

A disputable question

Would I be better off using macros-by-example? On one hand, they can parse text describing order of fields easier. On the other hand, it would be hard to use field names as expressions (since those macros are hygienic). And finally, I wouldn't learn how procedural macros work and wouldn't write this article!

Multi-currency swapping pool: MulDEX

ProgramCrafter — Fri, 23 Feb 2024 03:36:39 +0000

Exploring decentralized exchange algorithms, I've found out that most are focused on swap of two tokens, but theoretically they can be extended to multiple ones without loss of functionality.

Examples of two-token liquidity pools

A, B - reserve of tokens in the pool (so, they don't belong to any user, except maybe liquidity providers).

$A * B = co n s t$ .

For example, $A = 1000, B = 2000$ .

Suppose person wants to swap 5 A tokens for some B. Then, pool will have $A^{'} = 1005$ , and to maintain invariant $A * B = 2^{'} 00 0^{'} 000$ it will retain $B^{'} = 1990$ , sending 10 B out.
$A^3 * B + A * B^3 = const$ .
$A^p * B^{1-p} = const$ (Maniswap; p changes over liquidity additions and is used to keep the price same).

Natural extensions

$A * B * C * D * ... = co n s t$ .

Any swap here is equivalent to swap in basic pool, since amount of any other token except two chosen is constant. Though, I have been said that it has problems with liquidity.
$A * B + A * C + B * C + A * D + ... = co n s t$ . Sum of pairwise products of token reserves is constant.

Let's calculate how many B (dB) will pool return when receiving some A (dA).
$y_0 \newline --- \newline A * B + A * C + B * C + ... = x \newline 2 * A * B + 2 * A * C + 2 * B * C + ... = 2x \newline (A + B + C + ...)^2 = y_0^2 = 2x + A^2 + B^2 + C^2 + ... \newline (y_0 + dA + dB)^2 = 2x + A^2 + 2*A*dA + dA^2 + B^2 + 2*B*dB + dB^2 + C^2 + ... \newline --- \newline (dA + dB)(2y_0 + dA + dB) = 2*A*dA + dA^2 + 2*B*dB + dB^2 \newline dB^2 + dB(2y_0 + 2dA) + dA^2 + 2da*y_0 = dB^2 + dA^2 + 2*B*dB + 2*A*dA \newline 2dB*(y_0+dA-B) = 2*A*dA \newline dB = A * dA / (y_0 + dA - B)$
I haven't found any problems with such a pool so I think it can be used to shorten swaps (now, some can take several steps). It can even be used without computers, meaning possible replacement for barter!

EigenFlow - forming feeds based on user-to-user karma

ProgramCrafter — Thu, 22 Feb 2024 18:45:03 +0000

I've created a concept of system that allows to defer to others' judgement of what is the best feed: EigenFlow.

Each user can specify whose posts they want to see in the feed and in what proportion, plus borrow portion of that other user's feed. (In code, these are represented by coefs_see_own and coefs_defer_feeds.) That creates system of linear equations, which pretty often has a solution.

I feel like this could be useful for developers: if you have a more productive colleague or friend, you may simply take a look on what articles they read, and maybe that will help! So the discussion is welcome; and in particular, I'd like dev.to to consider this.