Skip to content

peter-lyons-kehl/no_std_rna_slice_patterns_presentation

Repository files navigation

Scope

  • Primary focus: Memory handling.

TODO


Prerequisites

  • nightly Rust compiler
  • the actual solutions work with stable Rust. However, the test harness (with extras on top of of Exercism's tests) needs nightly Rust (as of mid 2022).

List of patterns (and shared utils)

These examples are ordered as they progress:

(*) 05_no_heap-array-const_limit-bytes-wipe_on_clone-unsafe (as compared to the previous implementation) doesn't introduce anything new related to no_std, but it fits here. (Also, unsafe is more likely to be used with no_std anyway).

Properties of patterns

Property 01 02 03 04 (*) 05 06 07 08 09 10 11 12 13 14 15 16
Implemented part
extra work for securing observability/serialization: array or passed-in mutable slice could leak data!
fixed compile-time size limit for all instances (one type)
various compile-time size limits per instance (generic type), can have a default limit
no compile-time limit
random access & data storage (rather than sequential access only)
refer to the original (with a lifetime) (rather than copy the original)
refer to extra mutable storage (with a lifetime)
non-obvious or impractical API (*) 05 & 07 & 08
TODO mutable storage at/just before initiation, but then immutable -> shareable?
mutable & unlimited resize
--> TODO implement mutation for # 01
mutable & limited resize
mutable, but no ability to resize
immutable
extra handling of strings/UTF-8 (*) 🛆 🛆 🛆🛆 🛆 🛆
Clone is derive-d
Clone is implemented
no Clone -- needed at all?
Copy
different types for mutation and for sharing: 07 & 08
minor unsafe code
---
dyn (virtual) dispatch <-> static (compile-time) dispatch
extra dispatch methods
thread safe (Sync - if used in std) -> TODO "tests": struct EnsureSync<T: Sync>; type _EnsureSyncRna = EnsureSync<Rna>;
  • All "unlimited" properties are constrained by available memory.
  • (*) indicates a property or implementation that isn't no_std-specific, or is specific to this workspace. It's here for clarification.

TODO Group implementations?


Methods

no_std with heap

Replace use of HashSet/HashMap with BTreeSet/BTreeMap when possible. Or create different data structures. Or use 3rd party crates.

Replace Arc with Rc (since there is no multi-threading in no_std).

no_std without heap

  • Have your functions accept slices (shared or mutable), rather than Vec or String, wherever possible. Both Vec and String auto cast/expose themselves as a slice. (This is a good practice even with heap, or in std.)

  • Similarly, whenever possible, have your struct-s and enum-s store references, or slices, rather than own the data. It does involve lifetimes, but that can be a good practice, too.

  • Can't core::iter::Iterator.collect().

    • Even though collect() does exist in core (and not only in std), it can collect only to implementations of core::iter::FromIterator. (That, again, exists in core, in addition to std). However, there are no core-only implementors of FromIterator (other than collecting zero or one item to core::option::Option or to core::result::Result).
    • collect() doesn't exist for arrays nor slices (without heap). Hence we need to iterate and store in a (mutable) array or slice. New to Rust? And Worried about side effects? Good news: Safe Rust prevents unintended side effects, because we "cannot have a mutable reference while we have an immutable one to the same value."
  • there is no dynamic/resizable data storage

    • a no_std design needs to batch/buffer/limit the total data
    • use slices (instead of arrays) as parameter types wherever possible
      • design function as accepting (shared or mutable) slices
      • functions may need to write to mutable slice parameters (instead of returning).

  • New to Rust? Mutating slices or references/arrays may sound less "functional". But, in Rust any mutated parameters must be declared so. Any parameter that may be modified must be either
  • alternatively, use const generics, a subset of Rust generics, for both function parameters and return values
    • make the array size (which has to be known in compile time) a const generic parameter
    • beware that generics make the executable larger, and the build process takes longer; it helps to combine (const) generics for some functions, and slices for other
  • application's top level function(s) define the array(s), or array-containing structs/enums, on stack. Then they call the processing functions with slices, or with const generic-sized arrays (or their references)

  • this way you can re-use the same processing functions
  • if you can process the incoming data last in, first out (in LIFO/stack order), you could recurse (possibly batching the data in an array at every recursion level)
  • Have functions return an iterator wherever possible. (And use it for parameters, too. Again, a good practice even in std.)
    • may need to implement core::iter::Iterator to represents results of your transformation. Such iterators refer to the underlying iterator (data source/origin) and they may keep some state on top of it (a state machine).
    • You may want to combine/chain functions accepting and returning iterators. Use keyword impl to define types like impl Iterator<Item = YourItemType>.

no_std without heap > Alternatives to collect()

When developing for no_heap, we can't collect() from iterators. That makes some tasks that need random access (access to all items at the same time, like sorting) difficult.

This would need limit on number of items to be known at build time. Then the caller would pass a (mutable) reference to an array, or a slice, where we would manually collect the items (in a for loop, or .foreach() closure).


no_std without heap > Compound iterators

For some purposes we may not need access to all items if we don't need to access the whole collection. Then all we do needs sequential access only, for example a one-to-one transformation, and/or filtering.

For that we may need to implement a compound iterator. It would contain an underlying iterator (or several iterators) over the source data. It iterates and transforms and/or filters the source data.

Exercism Rust track > RNA Transcription

In addition to the text of the assignment, it helps to see the tests (or the same tests used for no_std version)

https://github.com/peter-kehl/x-rust/blob/main/rust/rna-transcription-std/src/lib.rs

https://github.com/peter-kehl/x-rust/blob/main/rust/rna-transcription-no_std-no_heap/src/lib.rs