Main :: Activity Log

Boring news about Federico

You may want to look at a reading list for particularly interesting posts.

Fri 2017/Jun/09

• MY BLOG HAS MOVED! Please visit the new blog here!

Fri 2017/Apr/28

• gboolean is not Rust bool

  I ran into an interesting bug in my Rust code for librsvg. I had these structures in the C code and in the Rust code, respectively; they are supposed to be bit-compatible with each other.

  /* C code */
  
  /* Keep this in sync with rust/src/viewbox.rs::RsvgViewBox */
  typedef struct {
      cairo_rectangle_t rect;
      gboolean active;
  } RsvgViewBox;
  
  
  
  /* Rust code */
  
  /* Keep this in sync with rsvg-private.h:RsvgViewBox */
  #[repr(C)]
  pub struct RsvgViewBox {
      pub rect: cairo::Rectangle,
      pub active: bool
  }
  	    

  After I finished rustifying one of the SVG element types, a test started failing in an interesting way. The Rust code was generating a valid RsvgViewBox structure, but the C code was receiving it with a garbled active field.

  It turns out that Rust's bool is not guaranteed to repr(C) as anything in particular. Rust chooses to do it as a single byte, with the only possible values being 0 or 1. In contrast, C code that uses gboolean assumes that gboolean is an int (... which C allows to be zero or anything else to represent a boolean value). Both structs have the same sizeof or mem::size_of, very likely due to struct alignment.

  I'm on x86_64, which is of course a little-endian platform, so the low byte of my gboolean active field had the correct value, but the higher bytes were garbage from the stack.

  The solution is obvious in retrospect: if the C code says you have a gboolean, bite the bullet and use a glib_sys::gboolean.

  There are impl FromGlib<gboolean> for bool and the corresponding impl ToGlib for bool trait implementations, so you can do this:

  extern crate glib;
  extern crate glib_sys;
  
  use self::glib::translate::*
  
  let my_gboolean: glib_sys::gboolean = g_some_function_that_returns_gboolean ();
  
  let my_rust_bool: bool = from_glib (my_gboolean);
  
  g_some_function_that_takes_gboolean (my_rust_bool.to_glib ());
  	    

  ... Which is really no different from the other from_glib() and to_glib() conversions you use when interfacing with the basic glib types.

  Interestingly enough, when I had functions exported from Rust to C with repr(C), or C functions imported into Rust with extern "C", my naive assumption of gboolean <-> bool worked fine for passed arguments and return values. This is probably because C promotes chars to ints in function calls, and Rust was looking only at the first char in the value. Maybe? And maybe it wouldn't have worked on a big-endian platform? Either way, I was into undefined behavior (bool is not something you repr(C)), so anything goes. I didn't disassemble things to see what was actually happening.

  There is an interesting, albeit extremely pedantic discussion, in this bug I filed about wanting a compiler warning for bool in a repr(C). People suggested that bool should just be represented as C's _Bool or bool if you include <stdbool.h>. BUT! Glib's gboolean predates C99, and therefore stdbool.h.

  Instead of going into a pedantic rabbit hole of whether Glib is non-standard (I mean, it has only been around for over 20 years), or whether C99 is too new to use generally, I'll go with just using the appropriate conversions from gtk-rs.

  Alternative conclusion: C99 is the Pont Neuf of programming languages.

Wed 2017/Apr/05

• The Rust+GNOME Hackfest in Mexico City, part 1

  Last week we had a Rust + GNOME hackfest in Mexico City (wiki page), kindly hosted by the Red Hat office there, in its very new and very cool office in the 22nd floor of a building and with a fantastic view of the northern part of the city. Allow me to recount the event briefly.

  

  Inexplicably, in GNOME's 20 years of existence, there has never been a hackfest or event in Mexico. This was the perfect chance to remedy that and introduce people to the wonders of Mexican food.

  My friend Joaquín Rosales, also from Xalapa, joined us as he is working on a very cool Rust-based monitoring system for small-scale spirulina farms using microcontrollers.

  Alberto Ruiz started getting people together around last November, with a couple of video chats with Rust maintainers to talk about making it possible to write GObject implementations in Rust. Niko Matsakis helped along with the gnarly details of making GObject's and Rust's memory management play nicely with each other.

  GObject implementations in Rust

  During the hackfest, I had the privilege of sitting next to Niko to do an intensive session of pair programming to function as a halfway-reliable GObject reference while I fixed my non-working laptop (intermission: kids, never update all your laptop's software right before traveling. It will not work once you reach your destination.).

  The first thing was to actually derive a new class from GObject, but in Rust. In C there is a lot of boilerplate code to do this, starting with the my_object_get_type() function. Civilized C code now defines all that boilerplate with the G_DEFINE_TYPE() macro. You can see a bit of the expanded code here.

  What G_DEFINE_TYPE() does is to define a few functions that tell the GType system about your new class. You then write a class_init() function where you define your table of virtual methods (just function pointers in C), you register signals which your class can emit (like "clicked" for a GtkButton), and you can also define object properties (like "text" for the textual contents of a GtkEntry) and whether they are readable/writable/etc.

  You also define an instance_init() function which is responsible for initializing the memory allocated to instances of your class. In C this is quite normal: you allocate some memory, and then you are responsible for initializing it. In Rust things are different: you cannot have uninitialized memory unless you jump through some unsafe hoops; you create fully-initialized objects in a single shot.

  Finally, you define a finalize function which is responsible for freeing your instance's data and chaining to the finalize method in your superclass.

  In principle, Rust lets you do all of this in the same way that you would in C, by calling functions in libgobject. In practice it is quite cumbersome. All the magic macros we have to define the GObject implementation boilerplate in gtype.h are there precisely because doing it in "plain C" is quite a drag. Rust makes this no different, but you can't use the C macros there.

  A GObject in Rust

  The first task was to write an actual GObject-derived class in Rust by hand, just to see how it could be done. Niko took care of this. You can see this mock object here. For example, here are some bits:

  #[repr(C)]
  pub struct Counter {
      parent: GObject,
  }
  
  struct CounterPrivate {
      f: Cell<u32>,
      dc: RefCell<Option<DropCounter>>,
  }
  
  #[repr(C)]
  pub struct CounterClass {
      parent_class: GObjectClass,
      add: Option<extern fn(&Counter, v: u32) -> u32>,
      get: Option<extern fn(&Counter) -> u32>,
      set_drop_counter: Option<extern fn(&Counter, DropCounter)>,
  }
  	    

  Here, Counter and CounterClass look very similar to the GObject boilerplate you would write in C. Both structs have GObject and GObjectClass as their first fields, so when doing C casts they will have the proper size and fields within those sub-structures.

  CounterPrivate is what you would declare as the private structure with the actual fields for your object. Here, we have an f: Cell<u32> field, used to hold an int which we will mutate, and a DropCounter, an utility struct which we will use to assert that our Rust objects get dropped only once from the C-like implementation of the finalize() function.

  Also, note how we are declaring two virtual methods in the CounterClass struct, add() and get(). In C code that defines GObjects, that is how you can have overridable methods: by exposing them in the class vtable. Since GObject allows "abstract" methods by setting their vtable entries to NULL, we use an Option around a function pointer.

  The following code is the magic that registers our new type with the GObject machinery. It is what would go in the counter_get_type() function if it were implemented in C:

  lazy_static! {
      pub static ref COUNTER_GTYPE: GType = {
          unsafe {
              gobject_sys::g_type_register_static_simple(
                  gobject_sys::g_object_get_type(),
                  b"Counter\0" as *const u8 as *const i8,
                  mem::size_of::<CounterClass>() as u32,
                  Some(CounterClass::init),
                  mem::size_of::<Counter>() as u32,
                  Some(Counter::init),
                  GTypeFlags::empty())
          }
  };
  	    

  If you squint a bit, this looks pretty much like the corresponding code in G_DEFINE_TYPE(). That lazy_static!() means, "run this only once, no matter how many times it is called"; it is similar to g_once_*(). Here, gobject_sys::g_type_register_static_simple() and gobject_sys::g_object_get_type() are the direct Rust bindings to the corresponding C functions; they come from the low-level gobject-sys module in gtk-rs.

  Here is the equivalent to counter_class_init():

  impl CounterClass {
      extern "C" fn init(klass: gpointer, _klass_data: gpointer) {
          unsafe {
              let g_object_class = klass as *mut GObjectClass;
              (*g_object_class).finalize = Some(Counter::finalize);
  
              gobject_sys::g_type_class_add_private(klass, mem::size_of::<CounterPrivate>>());
  
              let klass = klass as *mut CounterClass;
              let klass: &mut CounterClass = &mut *klass;
              klass.add = Some(methods::add);
              klass.get = Some(methods::get);
              klass.set_drop_counter = Some(methods::set_drop_counter);
          }
      }
  }	    

  Again, this is pretty much identical to the C implementation of a class_init() function. We even set the standard g_object_class.finalize field to point to our finalizer, written in Rust. We add a private structure with the size of our CounterPrivate...

  ... which we later are able to fetch like this:

  impl Counter {
     fn private(&self) -> &CounterPrivate {
          unsafe {
              let this = self as *const Counter as *mut GTypeInstance;
              let private = gobject_sys::g_type_instance_get_private(this, *COUNTER_GTYPE);
              let private = private as *const CounterPrivate;
              &*private
          }
      }
  }
  	    

  I.e. we call g_type_instance_get_private(), just like C code would, to get the private structure. Then we cast it to our CounterPrivate and return that.

  But that's all boilerplate

  Yeah, pretty much. But don't worry! Niko made it possible to get rid of it in a comfortable way! But first, let's look at the non-boilerplate part of our Counter object. Here are its two interesting methods:

  mod methods {
      #[allow(unused_imports)]
      use super::{Counter, CounterPrivate, CounterClass};
  
      pub(super) extern fn add(this: &Counter, v: u32) -> u32 {
          let private = this.private();
          let v = private.f.get() + v;
          private.f.set(v);
          v
      }
  
      pub(super) extern fn get(this: &Counter) -> u32 {
          this.private().f.get()
      }
  }
  	    

  These should be familar to people who implement GObjects in C. You first get the private structure for your instance, and then frob it as needed.

  No boilerplate, please

  Niko spent the following two days writing a plugin for the Rust compiler so that we can have a mini-language to write GObject implementations comfortably. Instead of all the gunk above, you can simply write this:

  extern crate gobject_gen;
  use gobject_gen::gobject_gen;
  
  use std::cell::Cell;
  
  gobject_gen! {
      class Counter {
          struct CounterPrivate {
              f: Cell<u32>
          }
  
          fn add(&self, x: u32) -> u32 {
              let private = self.private();
              let v = private.f.get() + x;
              private.f.set(v);
              v
          }
  
          fn get(&self) -> u32 {
              self.private().f.get()
          }
      }
  }	      
  	    

  This call to gobject_gen!() gets expanded to the the necessary boilerplate code. That code knows how to register the GType, how to create the class_init() and instance_init() functions, how to register the private structure and the utility private() to get it, and how to define finalize(). It will fill the vtable as appropriate with the methods you create.

  We figured out that this looks pretty much like Vala, except that it generates GObjects in Rust, callable by Rust itself or by any other language, once the GObject Introspection machinery around this is written. That is, just like Vala, but for Rust.

  And this is pretty good! We are taking an object system in C, which we must keep around for compatibility reasons and for language bindings, and making an easy way to write objects for it in a safe, maintained language. Vala is safer than plain C, but it doesn't have all the machinery to guarantee correctness that Rust has. Finally, Rust is definitely better maintained than Vala.

  There is still a lot of work to do. We have to support registering and emitting signals, registering and notifying GObject properties, and probably some other GType arcana as well. Vala already provides nice syntax to do this, and we can probably use it with only a few changes.

  Finally, the ideal situation would be for this compiler plugin, or an associated "cargo gir" step, to emit the necessary GObject Introspection information so that these GObjects can be called from other languages automatically. We could also spit C header files to consume the Rust GObjects from C.

  

  And the other people in the hackfest?

  I'll tell you in the next blog post!

Tue 2017/Feb/28

• Porting librsvg's tree of nodes to Rust

  Earlier I wrote about how librsvg exports reference-counted objects from Rust to C. That was the preamble to this post, in which I'll write about how I ported librsvg's tree of nodes from C to Rust.

  There is a lot of talk online about writing recursive data structures in Rust, as there are various approaches to representing the links between your structure's nodes. You can use shared references and lifetimes. You can use an arena allocator and indices or other kinds of identifiers into that arena. You can use reference-counting. Rust really doesn't like C's approach of pointers-to-everything-everywhere; you must be very explicit about who owns what and for how long things live.

  Librsvg keeps an N-ary tree of Node structures, each of which corresponds to an XML element in the SVG file. Nodes can be of various kinds: "normal" shapes that know how to draw themselves like Bézier paths and ellipses; "reference-only" objects like markers, which get referenced from paths to draw arrowheads and the like; "paint server" objects like gradients and fill patterns which also don't draw themselves, but only get referenced for a fill or stroke operation on other shapes; filter objects like Gaussian blurs which get referenced after rendering a sub-group of objects.

  Even though these objects are of different kinds, they have some things in common. They can be nested — a marker contains other shapes or sub-groups or shapes so you can draw multi-part arrowheads, for example; or a filter can be a Gaussian blur of the alpha channel of the referencing shape, followed by a light-source operation, to create an embossed effect on top of a shape. Objects can also be referenced by name in different places: you can declare a gradient and give it a name like #mygradient, and then use it for the fill or stroke of other shapes without having to declare it again.

  Also, all the objects maintain CSS state. This state gets inherited from an object's ancestors in the N-ary tree, and finally gets overriden with whatever specific CSS properties the object has for itself. You could declare a Group (a <g> element) with a black 4 pixel-wide outline, and then into it put a bunch of other shapes, but each with a fill of a different color. Those shapes will inherit the black outline, but use their own fill.

  Librsvg's representation of tree nodes, in C

  The old C code had a simple representation of nodes. There is an RsvgNodeType enum which just identifies the type of each node, and an RsvgNode structure for each node in the tree. Each RsvgNode also keeps a small vtable of methods.

  typedef enum {
      RSVG_NODE_TYPE_INVALID = 0,
  
      RSVG_NODE_TYPE_CHARS,
      RSVG_NODE_TYPE_CIRCLE,
      RSVG_NODE_TYPE_CLIP_PATH,
      RSVG_NODE_TYPE_COMPONENT_TRANFER_FUNCTION,
      ...
  } RsvgNodeType;
  
  
  typedef struct {
      void (*free) (RsvgNode *self);
      void (*draw) (RsvgNode *self, RsvgDrawingCtx *draw_ctx, int dominate);
      void (*set_atts) (RsvgNode *self, RsvgHandle *handle, RsvgPropertyBag *pbag);
  } RsvgNodeVtable;
  
  typedef struct _RsvgNode RsvgNode;
  
  typedef struct _RsvgNode {
      RsvgState      *state;
      RsvgNode       *parent;
      GPtrArray      *children;
      RsvgNodeType    type;
      RsvgNodeVtable *vtable;
  };
  	    

  What about memory management? A node keep an array pointers to its children, and also a pointer to its parent (which of course can be NULL for the root node). The master RsvgHandle object, which is what the caller gets from the public API, maintains a big array of pointers to all the nodes, in addition to a pointer to the root node of the tree. Nodes are created while reading an SVG file, and they don't get freed until the toplevel RsvgHandle gets freed. So, it is okay to keep shared references to nodes and not worry about memory management within the tree: the RsvgHandle will free all the nodes by itself when it is done.

  Librsvg's representation of tree nodes, in Rust

  In principle I could have done something similar in Rust: have the master handle object keep an array to all the nodes, and make it responsible for their memory management. However, when I started porting that code, I wasn't very familiar with how Rust handles lifetimes and shared references to objects in the heap. The syntax is logical once you understand things, but I didn't back then.

  So, I chose to use reference-counted structures instead. It gives me a little peace of mind that for some time I'll need to keep references from the C code to Rust objects, and I am already comfortable with writing C code that uses reference counting. Once everything is ported to Rust and C code no longer has references to Rust objects, I can probably move away from refcounts into something more efficient.

  I needed to have a way to hook the existing C implementations of nodes into Rust, so that I can port them gradually. That is, I need to have a way to have nodes implemented both in C and Rust, while I port them one by one to Rust. We'll see how this is done.

  Here is the first approach to the C code above. We have an enum that matches RsvgNodeType from C, a trait that defines methods on nodes, and the Node struct itself.

  /* Keep this in sync with rsvg-private.h:RsvgNodeType */
  #[repr(C)]
  #[derive(Debug, Copy, Clone, PartialEq)]
  pub enum NodeType {
      Invalid = 0,
  
      Chars,
      Circle,
      ClipPath,
      ComponentTransferFunction,
      ...
  }
  
  /* A *const RsvgCNodeImpl is just an opaque pointer to the C code's
   * struct for a particular node type.
   */
  pub enum RsvgCNodeImpl {}
  
  pub type RsvgNode = Rc<Node>;
  
  pub trait NodeTrait: Downcast {
      fn set_atts   (&self, node: &RsvgNode, handle: *const RsvgHandle, pbag: *const RsvgPropertyBag);
      fn draw       (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32);
      fn get_c_impl (&self) -> *const RsvgCNodeImpl;
  }
  
  impl_downcast! (NodeTrait);
  
  pub struct Node {
      node_type: NodeType,
      parent:    Option<Weak<Node>>,       // optional; weak ref to parent
      children:  RefCell<Vec<Rc<Node>>>,   // strong references to children
      state:     *mut RsvgState,
      node_impl: Box<NodeTrait>
  }
  	    

  The Node struct is analogous to the old C structure above. The parent field holds an optional weak reference to another node: it's weak to avoid circular reference counts, and it's optional because not all nodes have a parent. The children field is a vector of strong references to nodes; it is wrapped in a RefCell so that I can add children (i.e. mutate the vector) while the rest of the node remains immutable.

  RsvgState is a C struct that holds the CSS state for nodes. I haven't ported that code to Rust yet, so the state field is just a raw pointer to that C struct.

  Finally, there is a node_impl: Box<NodeTrait> field. This has a reference to a boxed object which implements NodeTrait. In effect, we are separating the "tree stuff" (the basic Node struct) from the "concrete node implementation stuff", and the Node struct has a reference inside it to the node type's concrete implemetation.

  The vtable turns into a trait, more or less

  Let's look again at the old C code for a node's vtable:

  typedef struct {
      void (*free) (RsvgNode *self);
      void (*draw) (RsvgNode *self, RsvgDrawingCtx *draw_ctx, int dominate);
      void (*set_atts) (RsvgNode *self, RsvgHandle *handle, RsvgPropertyBag *pbag);
  } RsvgNodeVtable;
  	    

  The free method is responsible for freeing the node itself and all of its inner data; this is common practice in C vtables.

  The draw method gets called, well, to draw a node. It gets passed a drawing context, plus a magic dominate argument which we can ignore for now (it has to do with CSS cascading).

  Finally, the set_atts method is just a helper at construction time: after a node gets allocated, it is initialized from its XML attributes by the set_atts method. The pbag argument is just a dictionary XML attributes for this node, represented as key-value pairs; the method pulls the key-value pairs out of the pbag and initializes its own fields from the values.

  The NodeTrait in Rust is similar, but has a few differences:

  pub trait NodeTrait: Downcast {
      fn set_atts (&self, node: &RsvgNode, handle: *const RsvgHandle, pbag: *const RsvgPropertyBag);
      fn draw (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32);
      fn get_c_impl (&self) -> *const RsvgCNodeImpl;
  }
  	    

  You'll note that there is no free method. Rust objects know how to free themselves and their fields automatically, so we don't need that method anymore. We will need a way to free the C data that corresponds to the C implementations of nodes — those are external resources not managed by Rust, so we need to tell it about them; see below.

  The set_atts and draw methods are similar to the C ones, but they also have an extra node argument. Read on.

  There is a new get_c_impl method. This is a temporary thing to accomodate C implementations of nodes; read on.

  Finally, what about the "NodeTrait: Downcast" in the first line? We'll get to it in the end.

  Separation of concerns?

  So, we have the basic Node struct, which forms the N-ary tree of SVG elements. We also have a NodeTrait with a few of methods that nodes must implement. The Node struct has a node_impl field, which holds a reference to an object in the heap which implements NodeTrait.

  I think I saw this pattern in the source code for Servo; I was looking at its representation of the DOM to see how to do an N-ary tree in Rust. I *think* it splits things in the same way; or maybe I'm misremembering and using the pattern from another tree-of-multiple-node-types implementation in Rust.

  How should things look from C?

  This is easy to answer: they should look exactly as they were before the conversion to Rust, or as close to that as possible, since I don't want to change all the C code at once!

  In the post about exposing reference-counted objects from Rust to C, we already saw the new rsvg_node_ref() and rsvg_node_unref() functions, which hand out pointers to boxed Rc<Node>.

  Previously I had made accessor functions for all of RsvgNode's fields, so the C code doesn't touch them directly. There are functions like rsvg_node_get_type(), rsvg_node_get_parent(), rsvg_node_foreach_child(), that the C code already uses. I want to keep them exactly the same, with only the necessary changes. For example, when the C code did not reference-count nodes, the implementation of rsvg_node_get_parent() simply returned the value of the node->parent field. The new implementation returns a strong reference to the parent (upgraded from the node's weak reference to its parent), and the caller is responsible for unref()ing it.

  Rust implementation of Node

  Let's look at two "trivial" methods of Node:

  impl Node {
      ...
  
      pub fn get_type (&self) -> NodeType {
          self.node_type
      }
  
      pub fn get_state (&self) -> *mut RsvgState {
          self.state
      }
  
      ...
  }
  	    

  Nothing special there; just accessor functions for the node's fields. Given that Rust makes those fields immutable in the presence of shared references, I'm not 100% sure that I actually need those accessors. If it turns out that I don't, I'll remove them and let the code access the fields directly.

  Now, the method that adds a child to a Node:

      pub fn add_child (&self, child: &Rc<Node>) {
          self.children.borrow_mut ().push (child.clone ());
      }
  	    

  The children field is a RefCell<Vec<Rc<Node>>>. We ask to borrow it mutably with borrow_mut(), and then push a new item into the array. What we push is a new strong reference to the child, which we get with child.clone(). Think of this as "g_ptr_array_add (self->children, g_object_ref (child))".

  And now, two quirky methods that call into the node_impl:

  impl Node {
      ...
  
      pub fn set_atts (&self, node: &RsvgNode, handle: *const RsvgHandle, pbag: *const RsvgPropertyBag) {
          self.node_impl.set_atts (node, handle, pbag);
      }
  
      pub fn draw (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32) {
          self.node_impl.draw (node, draw_ctx, dominate);
      }
  
      ...
  }
  	    

  The &self argument is implicitly a &Node. But we also pass a node: &RsvgNode argument! Remember the type declaration for RsvgNode; it is just "pub type RsvgNode = Rc<Node>". What these prototypes mean is:

      pub fn set_atts (&self: reference to the Node, node: refcounter for the Node, ...) {
          ... call the actual implementation in self.node_impl ...
      }
  	    

  This is because of the following. In objects that implement NodeTrait, the actual implementations of set_atts() and draw() still need to call into C code for a few things. And the only view that the C code has into the Rust world is through pointers to RsvgNode, that is, pointers to the Rc<Node> — the refcounting wrapper for nodes. We need to be able to pass this refcounting wrapper to C from somewhere, but once we are down in the concrete implementations of the trait, we don't have the refcounts anymore. So, we pass them as arguments to the trait's methods.

  This may look strange; at first sight it may look as if you are passing self twice to a method call, but not really! The self argument is implicit in the method call, and the first node argument is something rather different: it is a reference count to the node, not the node itself. I may be able to remove this strange argument once all the nodes are implemented in Rust and there is no interfacing to C code anymore.

  Accomodating C implementations of nodes

  Now we get to the part where the Node and NodeTrait, implemented in Rust, both need to accomodate the existing C implementations of node types.

  Instead of implementing a node type in Rust (i.e. implement NodeTrait for some struct), we will implement a Rust wrapper for node implementations in C, which implements NodeTrait. Here is the declaration of CNode:

  /* A *const RsvgCNodeImpl is just an opaque pointer to the C code's
   * struct for a particular node type.
   */
  pub enum RsvgCNodeImpl {}
  
  type CNodeSetAtts = unsafe extern "C" fn (node: *const RsvgNode, node_impl: *const RsvgCNodeImpl, handle: *const RsvgHandle, pbag: *const RsvgPropertyBag);
  type CNodeDraw = unsafe extern "C" fn (node: *const RsvgNode, node_impl: *const RsvgCNodeImpl, draw_ctx: *const RsvgDrawingCtx, dominate: i32);
  type CNodeFree = unsafe extern "C" fn (node_impl: *const RsvgCNodeImpl);
  
  struct CNode {
      c_node_impl: *const RsvgCNodeImpl,
  
      set_atts_fn: CNodeSetAtts,
      draw_fn:     CNodeDraw,
      free_fn:     CNodeFree,
  }
  	    

  This struct CNode has essentially a void* to the C struct that will hold a node's data, and three function pointers. These function pointers (set_atts_fn, draw_fn, free_fn) are very similar to the original vtable we had, and that we turned into a trait.

  We implement NodeTrait for this CNode wrapper as follows, by just calling the function pointers to the C functions:

  impl NodeTrait for CNode {
      fn set_atts (&self, node: &RsvgNode, handle: *const RsvgHandle, pbag: *const RsvgPropertyBag) {
          unsafe { (self.set_atts_fn) (node as *const RsvgNode, self.c_node_impl, handle, pbag); }
      }
  
      fn draw (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32) {
          unsafe { (self.draw_fn) (node as *const RsvgNode, self.c_node_impl, draw_ctx, dominate); }
      }
  
      ...
  }
  	    

  Maybe this will make it easier to understand why we neeed that "extra" node argument with the refcount: it is the actual first argument ot the C functions, which don't get the luxury of a self parameter.

  And the free_fn()? Who frees the C implementation data? Rust's Drop trait, of course! When Rust decides to free CNode, it will see if it implements Drop. Our implementation thereof calls into the C code to free its own data:

  impl Drop for CNode {
      fn drop (&mut self) {
          unsafe { (self.free_fn) (self.c_node_impl); }
      }
  }
  	    

  What does it look like in memory?

  

  This is the basic layout. A Node gets created and put on the heap. Its node_impl points to a CNode in the heap (or to any other thing which implements NodeTrait, really). In turn, CNode is our wrapper for C implementations of SVG nodes; its c_node_impl field is a raw pointer to data on the C side — in this example, an RsvgNodeEllipse. We'll see how that one looks like shortly.

  So how does C create a node?

  I'm glad you asked! This is the rsvg_rust_cnode_new() function, which is implemented in Rust but exported to C. The C code uses it when it needs to create a new node.

  #[no_mangle]
  pub extern fn rsvg_rust_cnode_new (node_type:   NodeType,
                                     raw_parent:  *const RsvgNode,
                                     state:       *mut RsvgState,
                                     c_node_impl: *const RsvgCNodeImpl,
                                     set_atts_fn: CNodeSetAtts,
                                     draw_fn:     CNodeDraw,
                                     free_fn:     CNodeFree) -> *const RsvgNode {
      assert! (!state.is_null ());
      assert! (!c_node_impl.is_null ());
  
      let cnode = CNode {                                             // 1
          c_node_impl: c_node_impl,
          set_atts_fn: set_atts_fn,
          draw_fn:     draw_fn,
          free_fn:     free_fn
      };
  
      box_node (Rc::new (Node::new (node_type,                        // 2
                                    node_ptr_to_weak (raw_parent),    // 3
                                    state,
                                    Box::new (cnode))))               // put the CNode in the heap; pass it to the Node
  }
  	    

  1. We create a CNode structure and fill it in from the parameters that got passed to rsvg_rust_cnode_new().

  2. We create a new Node with Node::new(), wrap it with a reference counter with Rc::new(), box that ("put it in the heap") and return a pointer to the box's contents. The boxificator is just this; it's similar to what we used before:

  pub fn box_node (node: RsvgNode) -> *mut RsvgNode {
      Box::into_raw (Box::new (node))
  }
  	    

  3. We create a weak reference to the parent node. Here, raw_parent comes in as a pointer to a strong reference. To obtain a weak reference, we do this:

  pub fn node_ptr_to_weak (raw_parent: *const RsvgNode) -> Option<Weak<Node>> {
      if raw_parent.is_null () {
          None
      } else {
          let p: &RsvgNode = unsafe { & *raw_parent };
          Some (Rc::downgrade (&p.clone ()))               // 5
      }
  }
  	    

  5. Here, we take a strong reference to the parent with p.clone(). Then we turn it into a weak reference with Rc::downgrade(). We stuff that in an Option with the Some() — remember that not all nodes have a parent, and we represent this with an Option<Weak<Node>>.

  Creating a C implementation of a node

  This is the C code for rsvg_new_group(), the function that creates nodes for SVG's <g> element.

  RsvgNode *
  rsvg_new_group (const char *element_name, RsvgNode *parent)
  {
      RsvgNodeGroup *group;
  
      group = g_new0 (RsvgNodeGroup, 1);
  
      /* ... fill in the group struct ... */
  
      return rsvg_rust_cnode_new (RSVG_NODE_TYPE_GROUP,
                                  parent,
                                  rsvg_state_new (),
                                  group,
                                  rsvg_group_set_atts,
                                  rsvg_group_draw,
                                  rsvg_group_free);
  }
  	    

  The resulting RsvgNode*, which from C's viewpoint is an opaque pointer to something on the Rust side — the boxed Rc<Node> — gets stored in a couple of places. It gets put in the toplevel RsvgHandle's array of all-the-nodes. It gets hooked, as a child, to its parent node. It may get referenced in other places as well, for example, in the dictionary of string-to-node for nodes that have an id="name" attribute. All those are strong references created with rsvg_node_ref().

  Getting the implementation structs from C

  Let's look again at the implementation of NodeTrait for CNode. This is one of the methods:

  impl NodeTrait for CNode {
      ...
  
      fn draw (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32) {
          unsafe { (self.draw_fn) (node as *const RsvgNode, self.c_node_impl, draw_ctx, dominate); }
      }
  
      ...
  }
  	    

  In self.draw_fn we have a function pointer to a C function. We call it, and we pass the self.c_node_impl. This gives the function access to its own implementation data.

  But what about cases where we need to access an object's data outside of the methods, and so we don't have that c_node_impl argument? If you are cringing because This Is Not Something That Is Done in OOP, well, you are right, but this is old code with impurities. Maybe once it is Rustified thoroughly, I'll have a chance to clean up those inconsistencies. Anyway, here is a helper function that the C code can call to get ahold of its c_node_impl:

  #[no_mangle]
  pub extern fn rsvg_rust_cnode_get_impl (raw_node: *const RsvgNode) -> *const RsvgCNodeImpl {
      assert! (!raw_node.is_null ());
      let node: &RsvgNode = unsafe { & *raw_node };
  
      node.get_c_impl ()
  }
  	    

  That get_c_impl() method is the temporary thing I mentioned above. It's one of the methods in NodeTrait, and of course CNode implements it like this:

  impl NodeTrait for CNode {
      ...
  
      fn get_c_impl (&self) -> *const RsvgCNodeImpl {
          self.c_node_impl
      }
  }
  	    

  You may be thinking that is is an epic hack: not only do we provide a method in the base trait to pull an obscure field from a particular implementation; we also return a raw pointer from it! And a) you are absolutely right, but b) it's a temporary hack, and it is about the easiest way I found to shove the goddamned C implementation around. It will be gone once all the node types are implemented in Rust.

  Now, from C's viewpoint, the return value of that rsvg_rust_cnode_get_impl() is just a void*, which needs to be casted to the actual struct we want. So, the proper way to use this function is first to assert that we have the right type:

  g_assert (rsvg_node_get_type (handle->priv->treebase) == RSVG_NODE_TYPE_SVG);
  RsvgNodeSvg *root = rsvg_rust_cnode_get_impl (handle->priv->treebase);
  	    

  This is no different or more perilous than the usual downcasting one does when faking OOP with C. It's dangerous, sure, but we know how to deal with it.

  Creating a Rust implementation of a node

  Aaaah, the fun part! I am porting the SVG node types one by one to Rust. I'll show you the simple implementation of NodeLine, which is for SVG's <line> element.

  struct NodeLine {
      x1: Cell<RsvgLength>,
      y1: Cell<RsvgLength>,
      x2: Cell<RsvgLength>,
      y2: Cell<RsvgLength>
  }
  	    

  Just x1/y1/x2/y2 fields with our old friend RsvgLength, no problem. They are in Cells to make them mutable after the NodeLine is constructed and referenced all over the place.

  Now let's look at its three methods of NodeTrait.

  impl NodeTrait for NodeLine {
  
      fn set_atts (&self, _: &RsvgNode, _: *const RsvgHandle, pbag: *const RsvgPropertyBag) {
          self.x1.set (property_bag::lookup_length (pbag, "x1", LengthDir::Horizontal));
          self.y1.set (property_bag::lookup_length (pbag, "y1", LengthDir::Vertical));
          self.x2.set (property_bag::lookup_length (pbag, "x2", LengthDir::Horizontal));
          self.y2.set (property_bag::lookup_length (pbag, "y2", LengthDir::Vertical));
      }
  }
  	    

  The set_atts() method just sets the fields of the NodeLine to the corresponding values that it gets in the property bag. This pbag is of key-value pairs from XML attributes. That lookup_length() function looks for a specific key, and parses it into an RsvgLength. If the key is not available, or if parsing yields an error, the function returns RsvgLength::default() — the default value for lengths, which is zero pixels. This is where we "bump" into the C code that doesn't know how to propagate parsing errors yet. Internally, the length parser in Rust yields a proper Result value, with error information if parsing fails. Once all the code is on the Rust side of things, I'll start thinking about propagating errors to the toplevel RsvgHandle. For now, librsvg is a very permissive parser/renderer indeed.

  I'm starting to realize that set_atts() only gets called immediately after a new node is allocated. After that, I *think* that nodes don't mutate their internal fields. So, it may be possible to move the "pull stuff out of the pbag and set the fields" code from set_atts() to the actual constructors, remove the Cell wrappers around all the fields, and thus get immutable objects.

  Maybe it is that I'm actually going through all of librsvg's code, so I get to know it better; or maybe it is that porting it to Rust is actually clarifying my thinking on how the code works and how it ought to work. If all nodes are immutable after creation... and they are a recursive tree... which already does Porter-Duff compositing... which is associative... that sounds very parallelizable, doesn't it? (I would never dare to do it in C. Rust is making it feel quite feasible, without data races.)

  impl NodeTrait for NodeLine {
  
      fn draw (&self, node: &RsvgNode, draw_ctx: *const RsvgDrawingCtx, dominate: i32) {
          let x1 = self.x1.get ().normalize (draw_ctx);
          let y1 = self.y1.get ().normalize (draw_ctx);
          let x2 = self.x2.get ().normalize (draw_ctx);
          let y2 = self.y2.get ().normalize (draw_ctx);
  
          let mut builder = RsvgPathBuilder::new ();
          builder.move_to (x1, y1);
          builder.line_to (x2, y2);
  
          render_path_builder (&builder, draw_ctx, node.get_state (), dominate, true);
      }
  
  }
  	    

  The draw() method normalizes the x1/y1/x2/y2 values to the current viewport from the drawing context. Then it creates a path builder and feeds it commands to draw a line. It calls a helper function, render_path_builder(), which renders it using the appropriate CSS cascaded values, and which adds SVG markers like arrowheads if they were specified in the SVG file.

  Finally, our little hack for the benefit of the C code:

  impl NodeTrait for NodeLine {
  
      fn get_c_impl (&self) -> *const RsvgCNodeImpl {
          unreachable! ();
      }
  
  }
  	    

  In this purely-Rust implementation of NodeLine, there is no c_impl. So, this method asserts that nobody ever calls it. This is to guard myself against C code which may be trying to peek at an impl when there is no longer one.

  Downcasting to concrete types

  Remember rsvg_rust_cnode_get_impl(), which the C code can use to get its implementation data outside of the normal NodeTrait methods?

  Well, since I am doing a mostly straight port from C to Rust, i.e. I am not changing the code's structure yet, just changing languages — it turns out that sometimes the Rust code needs access to the Rust structs outside of the NodeTrait methods as well.

  I am using downcast-rs, a tiny crate that lets one do exactly this: go from a boxed trait object to a concrete type. Librsvg uses it like this:

  use downcast_rs::*;
  
  pub trait NodeTrait: Downcast {
      fn set_atts (...);
      ...
  }
  
  impl_downcast! (NodeTrait);
  
  impl Node {
      ...
  
      pub fn with_impl<T: NodeTrait, F: FnOnce (&T)> (&self, f: F) {
          if let Some (t) = (&self.node_impl).downcast_ref::<T> () {
              f (t);
          } else {
              panic! ("could not downcast");
          }
      }
  
      ...
  }
  	    

  The basic Node has a with_impl() method, which takes a lambda that accepts a concrete type that implements NodeTrait. The lambda gets called with your Rust-side impl, with the right type.

  Where the bloody hell is this used? Let's take markers as an example. Even though SVG markers are implemented as a node, they don't draw themselves: they can get referenced from paths/lines/etc. and there is special machinery to decide just where to draw them.

  So, in the implementation for markers, the draw() method is empty. The code that actually computes a marker's position uses this to render the marker:

  node.with_impl (|marker: &NodeMarker| marker.render (c_node, draw_ctx, xpos, ypos, computed_angle, line_width));
  	    

  That is, it calls node.with_impl() and passes it an anonymous function which calls marker.render() — a special function just for rendering markers.

  This is kind of double plus unclean, yes. I can think of a few solutions:

  • Instead of assuming that every node type is really a NodeTrait, make Node know about element implementations that can draw themselves normally and those that can't. Maybe Node can have an enum to discriminate that, and NodeTrait can lose the draw() method. Maybe there needs to be Drawable trait which "normal" elements implement, and something else for markers and other elements which are only used by reference?

  • Instead of having a single dictionary of named nodes — those that have an id="name" attribute, which is later used to reference markers, filters, etc. — have separate dictionaries for every reference-able element type. One dict for markers, one dict for patterns, one dict for filters, and so on. The SVG spec already says, for example, that it is an error to reference a marker but to specify an id for an element that is not a marker — and so on for the other reference-able types. After doing a lookup by id in the dictionary-of-all-named-nodes, librsvg checks the type of the found Node. It could avoid doing this check if the dictionaries were separate, since each dictionary would only contain objects of a known type.

  Conclusion

  Apologies for the long post! Here's a summary:

  • Node objects are reference-counted. Librsvg uses them to build up the tree of nodes.

  • There is a NodeTrait for SVG element implementations. It has methods to set an element's attributes, and to draw the element.

  • SVG elements already implemented in Rust have no problems; they just implement NodeTrait and that's it.

  • For the rest of the SVG elements, which are still implemented in C, I have a CNode which implements NodeTrait. The CNode holds an opaque pointer to the implementation data on the C side, and function pointers to the C implementations of NodeTrait.

  • There is some temporary-but-clean hackery to let C code obtain its implementation pointers outside of the normal method implementations.

  • Downcasting to concrete types is a necessary evil, but it is the easiest way to transform this C code into Rust. It may be possible to eliminate it with some refactoring.

  The git history for the conversion of nodes into Rust is interesting, I hope; I've tried to write explanatory comments in the commits. If you want to read this history, start at this commit. Before it there is a lot of C-side refactoring to turn field accesses into accesor functions, for example. In that commit and a few that follow, there are some false starts as I learned how to represent recursive data structures in Rust. Then there is a lot of refactoring to make the existing C implementations all use rsvg_rust_cnode_new(), and to hook them to the Rust-side machinery. Finally, there are commits to actually port complete elements into Rust and eliminate the C implementations. Enjoy!

• Addendum: how did I do the refactoring above?

  To move the librsvg code towards a state where I could do mostly mechanical transformations, from the old C-based RsvgNode structures into Rust-based Node and the CNode shim, I had to do a lot of refactoring.

  The first thing was to add accessor functions for all of a node's fields: create rsvg_node_get_type(), rsvg_node_get_parent(), etc., instead of accessing node->type and node->parent directly. This is so that, once the basic Node structure was moved to Rust, the C code would have a way to access its fields. I do not want to have parallel structs in C and in Rust with the same memory layouts, although Rust makes it possible to do things that way if you wish.

  I had to change the way in which new nodes are created, when they are parsed out of the SVG file. Instead of a big switch() statement, I parametrized the node creator functions based on the name of the SVG element being created.

  I moved the node destructors around, so that they really were only callable in a single way, instead of differently all over the place.

  Some of the changes caused ripples throughout the code, and I had to review things carefully. For this, I kept a to-do list in a text file. Here is part of that to-do list, with some explanations.

  * TODO Rust node:
  
  ** DONE RsvgNode - remove struct declaration from the C code; leave as
     an opaque type.
  
  ** DONE Audit calls to rsvg_drawing_ctx_acquire_node_of_type() -
     returns opaque RsvgNode*, not a castable thing.
  
  ** DONE Audit all casts; grep for "*)".  It turns out that once
     rsvg_rust_cnode_get_impl() was in place, all the casts disappeared
     from the code!
  
  ** DONE Look for casts to (RsvgNode *) - those are most likely wrong
     now.
  
  ** DONE rsvg_node_free() - remove; replace with unref().
  
  ** TODO pattern_new() - implemented in Rust, takes a RsvgNode argument
     from C - what to do with it?
  
  ** TODO rsvg_pattern_node_has_children() - move to Rust?
  
  ** DONE Audit calls to rsvg_node_get_parent() - unref when done.
  
  ** DONE rsvg_drawing_ctx_free() - unref the nodes in drawsub_stack.
  
  ** DONE rsvg_node_add_child() - use it when creating a new node.
  
  ** DONE Audit "node_a == node_b" as node references can't be compared
     anymore; use rsvg_node_is_same().
  	    

  (You may recognize this format as Emacs org-mode - it's awesome.)

  That to-do list was especially useful when the code was in the middle of being refactored maybe it would compile, but it would definitely not be correct. I suggest that if you try to do a similar port/refactor, you keep a detailed to-do list of sweeping changes.

Fri 2017/Feb/24

• Griping about parsers and shitty specifications

  The last time, I wrote about converting librsvg's tree of SVG element nodes from C to Rust — basically, the N-ary tree that makes up librsvg's view of an SVG file's structure. Over the past week I've been porting the code that actually implements specific shapes. I ran into the problem of needing to port the little parser that librsvg uses for SVG's list-of-points data type; this is what SVG uses for the points in a polygon or a polyline. In this post, I want to tell you my story of writing Rust parsers, and I also want to vent a bit.

  My history of parsing in Rust

  I've been using hand-written parsers in librsvg, basically learning how to write parsers in Rust as I go. In a rough timeline, this is what I've done:

  1. First was the big-ass parser for Bézier path data, an awkward recursive-descent monster that looks very much like what I would have written in C, and which is in dire need of refactoring (the tests are awesome, though, if you (hint, hint) want to lend a hand).

  2. Then was the simple parser for RsvgLength values, in which the most expedient thing, if not the prettiest, was to reimplement strtod() in Rust. You know how C and/or glib have a wealth of functions to write half-assed parsers quickly? Yeah, that's what I went for here. However, with this I learned that strtod()'s behavior of returning a pointer to the thing-after-the-number can be readily implemented with Rust's string slices.

  3. Then was the little parser for preserveAspectRatio values, which actually uses Rust idioms like using a split_whitespace() iterator and returing a custom error inside a Result.

  4. Lastly, I've implemented a parser for SVG's list-of-points data type. While shapes like rect and circle simply use RsvgLength values which can have units, like percentages or points:

     <rect x="5pt" y="6pt" width="7.5 pt" height="80%/">
     
     <circle cx="25.0" cy="30.0" r="10.0"/>
     		

     In contrast, polygon and polyline elements let you specify lists of points using a simple but quirky grammar that does not use units; the numbers are relative to the object's current coordinate system:

     <polygon points="100,60 120,140 140,60 160,140 180,60 180,100 100,100"/>
     		

  Quirky grammars and shitty specs

  The first inconsistency in the above is that some object types let you specify their positions and sizes with actual units (points, centimeters, ems), while others don't — for these last ones, the coordinates you specify are relative to the object's current transformation. This is not a big deal; I suspect it is either an oversight in the spec, or they didn't want to think of a grammar that would accomodate units like that.

  The second inconsistency is in SVG's quirky grammars. These are equivalent point lists:

  points="100,-60 120,-140 140,60 160,140"
  
  points="100 -60 120 -140 140 60 160 140"
  
  points="100-60,120-140,140,60 160,140"
  
  points="100-60,120, -140,140,60 160,140"
  	    

  Within an (x, y) coordinate pair, the space is optional if the y coordinate is negative. Or you can separate the x and y with a space, with an optional comma.

  But between coordinate pairs, the separator is not optional. You must have any of whitespace or a comma, or both. Even if an x coordinate is negative, it must be separated from its preceding y coordinate.

  But this is not true for path specifications! The following are paths that start with a Move_to comamnd and follow with three Line_to commands, and they are equivalent:

  M 1 2 L -3 -4 5 -6 7 -8
  
  M1,2 L-3 -4, 5,-6,7 -8
  
  M1,2L-3-4, 5-6,7-8
  
  M1 2-3,-4,5-6 7,-8
  
  M1,2-3-4 5-6 7-8
  	    

  Inside (x, y) pairs, you can have whitespace with an optional comma, or nothing if the y is negative. Between coordinate pairs you can have whitespace with an optional comma, or nothing at all! As you wish! And also, since all subpaths start with a single move_to anyway, you can compress a "M point L point point" to just "M point point point" — the line_to is implied.

  I think this is a misguided attempt by the SVG spec to allow compressibility of the path data. But they might have gotten more interesting gains, oh, I don't know, by not using XML and just nesting things with parentheses.

  

  Also, while the grammar for the point lists in polygon and polyline clearly implies that you must have an even number of floats in your list (for the x/y coordinate pairs), the description of the polygon element says that if you have an odd number of coordinates, the element is "in error" and should be treated the same as an erroneous path description. But the implementation notes for paths say that you should "render a path element up to (but not including) the path command containing the first error in the path data specification", i.e. just ignore the orphan coordinate and somehow indicate an error.

  So which one is it? Should we a) count the floats and ignore the odd one out? Or b) should we follow the grammar and ditch the whole string if it isn't matched by the grammar? Or c) put special handling in the grammar for the last odd coordinate?

  I mean, it's no big deal to actually handle this in the code, but it's annoying to have a spec that can't make up its mind.

  The expediency of half-assed parsers

  How would you parse a string that has an array of floating-point numbers separated by whitespace? In Python you could split() the string and then apply float() to each item, and catch an exception if the value does not parse to float. Or something like that.

  The C code in librsvg has a rather horrible rsvg_css_parse_number_list() function, complete with a "/* TODO: some error checking */" comment, that is implemented in terms of an equally horrible rsvg_css_parse_list() function. This last one is the one that handles the "optional whitespace and comma" shenanigans... with strtok_r(). Between both functions there are like a million temporary copies of the whole string and the little substrings. Or something like that.

  Neither version is fully conformant to the quirks in the SVG spec. I'm replacing all that shit with "proper" parsers written in Rust. And what could be more proper than to actually use a parser-generating library instead of writing them from scratch?

  The score is Nom: 2 - Federico: 1

  This is the second time I have tried to use nom, a library for parser combinators. I like the idea of parser combinators instead of writing a grammar and then generating a parser out of that: supposedly your specification of a parser combinator closely resembles your grammar, but the whole thing is written and embedded in the same language as the rest of your code.

  There is a good number of parsers already written with nom, so clearly it works.

  But nom has been... hard. A few months ago I tried rewriting the path data parser for librsvg, from C to Rust with nom, and it was a total failure. I couldn't even parse a floating-point number out of a string. I ditched it after a week of frustration, and wrote my own parser by hand.

  Last week I tried nom again. Sebastian Dröge was very kind to jumpstart me with some nom-based code to parse floating-point numbers. I then discovered that the latest nom actually has that out of the box, but it is buggy, and after some head-scratching I was able to propose a fix. Apparently my fix won't work if nom is being used for a streaming parser, but I haven't gotten around to learning those yet.

  I've found nom code to be very hard to write. Nom works by composing macros which then call recognizer functions and other macros. To be honest, I find the compiler errors for that kind of macros quite intractable. And I'm left with not knowing if the problem is in my use of the macros, or in the macro definitions themselves.

  After much, much trial-and-error, and with the vital help of Sebastian Köln from the #nom IRC channel, I have a nom function that can match SVG's comma-whitespace construct and two others that can match coordinate pairs and lists of points for the polygon and polyline elements. This last one is not even complete: it still doesn't handle a list of points that has whitespace around the list itself (SVG allows that, as in "   1 2, 3 4   ").

  While I can start using those little nom-based parsers to actually build implementations of librsvg's objects, I don't want to battle nom anymore. The documentation is very sketchy. The error messages from macros don't make sense to me. I really like the way nom wants to handle things, with an IResult type that holds the parsing state, but it's just too hard for me to even get things to compile with it.

  So what are you gonna use?

  I don't know yet. There are other parser libraries for Rust; pom, lalrpop, and pest among them. I hope they are easier to try out than nom. If not, "when in doubt, use brute force" may apply well here — hand-written parsers in Rust are as cumbersome as in any other language, but at least they are memory-safe, and writing tests for them is a joy in Rust.

Fri 2017/Feb/17

• How librsvg exports reference-counted objects from Rust to C

  Librsvg maintains a tree of RsvgNode objects; each of these corresponds to an SVG element. An RsvgNode is a node in an n-ary tree; for example, a node for an SVG "group" can have any number of children that represent various shapes. The toplevel element is the root of the tree, and it is the "svg" XML element at the beginning of an SVG file.

  Last December I started to sketch out the Rust code to replace the C implementation of RsvgNode. Today I was able to push a working version to the librsvg repository. This is a major milestone for myself, and this post is a description of that journey.

  Nodes in librsvg in C

  Librsvg used to have a very simple scheme for memory management and its representation of SVG objects. There was a basic RsvgNode structure:

  typedef enum {
      RSVG_NODE_TYPE_INVALID,
      RSVG_NODE_TYPE_CHARS,
      RSVG_NODE_TYPE_CIRCLE,
      RSVG_NODE_TYPE_CLIP_PATH,
      /* ... a bunch of other node types */
  } RsvgNodeType;
  	      
  typedef struct {
      RsvgState    *state;
      RsvgNode     *parent;
      GPtrArray    *children;
      RsvgNodeType  type;
  
      void (*free)     (RsvgNode *self);
      void (*draw)     (RsvgNode *self, RsvgDrawingCtx *ctx, int dominate);
      void (*set_atts) (RsvgNode *self, RsvgHandle *handle, RsvgPropertyBag *pbag);
  } RsvgNode;
  	    

  This is a no-frills base struct for SVG objects; it just has the node's parent, its children, its type, the CSS state for the node, and a virtual function table with just three methods. In typical C fashion for derived objects, each concrete object type is declared similar to the following one:

  typedef struct {
      RsvgNode super;
      RsvgLength cx, cy, r;
  } RsvgNodeCircle;
  	    

  The user-facing object in librsvg is an RsvgHandle: that is what you get out of the API when you load an SVG file. Internally, the RsvgHandle has a tree of RsvgNode objects — actually, a tree of concrete implementations like the RsvgNodeCircle above or others like RsvgNodeGroup (for groups of objects) or RsvgNodePath (for Bézier paths).

  Also, the RsvgHandle has an all_nodes array, which is a big list of all the RsvgNode objects that it is handling, regardless of their position in the tree. It also has a hash table that maps string IDs to nodes, for when the XML elements in the SVG have an "id" attribute to name them. At various times, the RsvgHandle or the drawing-time machinery may have extra references to nodes within the tree.

  Memory management is simple. Nodes get allocated at loading time, and they never get freed or moved around until the RsvgHandle is destroyed. To free the nodes, the RsvgHandle code just goes through its all_nodes array and calls the node->free() method on each of them. Any references to the nodes that remain in other places will dangle, but since everything is being freed anyway, things are fine. Before the RsvgHandle is freed, the code can copy pointers around with impunity, as it knows that the all_nodes array basically stores the "master" pointers that will need to be freed in the end.

  But Rust doesn't work that way

  Not so, indeed! C lets you copy pointers around all you wish; it lets you modify all the data at any time; and forces you to do all the memory-management bookkeeping yourself. Rust has simple and strict rules for data access, with profound implications. You may want to read up on ownership (where variable bindings own the value they refer to, there is one and only one binding to a value at any time, and values are deleted when their variable bindings go out of scope), and on references and borrowing (references can't outlive their parent scope; and you can either have one or more immutable references to a resource, or exactly one mutable reference, but not both at the same time). Together, these rules avoid dangling pointers, data races, and other common problems from C.

  So while the C version of librsvg had a sea of carefully-managed shared pointers, the Rust version needs something different.

  And it all started with how to represent the tree of nodes.

  How to represent a tree

  Let's narrow down our view of RsvgNode from C above:

  typedef struct {
      ...
      RsvgNode  *parent;
      GPtrArray *children;
      ...
  } RsvgNode;
  	    

  A node has pointers to all its children, and each child has a pointer back to the parent node. This creates a bunch of circular references! We would need a real garbage collector to deal with this, or an ad-hoc manual memory management scheme like librsvg's and its all_nodes array.

  Rust is not garbage-collected and it doesn't let you have shared pointers easily or without unsafe code. Instead, we'll use reference counting. To avoid circular references, which a reference-counting scheme cannot handle, we use strong references from parents to children, and weak references from the children to point back to parent nodes.

  In Rust, you can add reference-counting to your type Foo by using Rc<Foo> (if you need atomic reference-counting for multi-threading, you can use an Arc<Foo>). An Rc represents a strong reference count; conversely, a Weak<Foo> is a weak reference. So, the Rust Node looks like this:

  pub struct Node {
      ...
      parent:    Option<Weak<Node>>,
      children:  RefCell<Vec<Rc<Node>>>,
      ...
  }
  	    

  Let's unpack that bit by bit.

  "parent: Option<Weak<Node>>". The Weak<Node> is a weak reference to the parent Node, since a strong reference would create a circular refcount, which is wrong. Also, not all nodes have a parent (i.e. the root node doesn't have a parent), so put the Weak reference inside an Option. In C you would put a NULL pointer in the parent field; Rust doesn't have null references, and instead represents lack-of-something via an Option set to None.

  "children: RefCell<Vec<Rc<Node>>>". The Vec<Rc<Node>>> is an array (vector) of strong references to child nodes. Since we want to be able to add children to that array while the rest of the Node structure remains immutable, we wrap the array in a RefCell. This is an object that can hand out a mutable reference to the vector, but only if there is no other mutable reference at the same time (so two places of the code don't have different views of what the vector contains). You may want to read up on interior mutability.

  Strong Rc references and Weak refs behave as expected. If you have an Rc<Foo>, you can ask it to downgrade() to a Weak reference. And if you have a Weak<Foo>, you can ask it to upgrade() to a strong Rc, but since this may fail if the Foo has already been freed, that upgrade() returns an Option<Rc<Foo>> — if it is None, then the Foo was freed and you don't get a strong Rc; if it is Some(x), then x is an Rc<Foo>, which is your new strong reference.

  Handing out Rust reference-counted objects to C

  In the post about Rust constructors exposed to C, we talked about how a Box is Rust's primitive to put objects in the heap. You can then ask the Box for the pointer to its heap object, and hand out that pointer to C.

  If we want to hand out an Rc to the C code, we therefore need to put our Rc in the heap by boxing it. And going back, we can unbox an Rc and let it fall out of scope in order to free the memory from that box and decrease the reference count on the underlying object.

  First we will define a type alias, so we can write RsvgNode instead of Rc<Node> and make function prototypes closer to the ones in the C code:

  pub type RsvgNode = Rc<Node>;
  	    

  Then, a convenience function to box a refcounted Node and extract a pointer to the Rc, which is now in the heap:

  pub fn box_node (node: RsvgNode) -> *mut RsvgNode {
      Box::into_raw (Box::new (node))
  }
  	    

  Now we can use that function to implement ref():

  #[no_mangle]
  pub extern fn rsvg_node_ref (raw_node: *mut RsvgNode) -> *mut RsvgNode {
      assert! (!raw_node.is_null ());
      let node: &RsvgNode = unsafe { & *raw_node };
  
      box_node (node.clone ())
  }
  	    

  Here, the node.clone () is what increases the reference count. Since that gives us a new Rc, we want to box it again and hand out a new pointer to the C code.

  You may want to read that twice: when we increment the refcount, the C code gets a new pointer! This is like creating a hardlink to a Unix file — it has two different names that point to the same inode. Similarly, our boxed, cloned Rc will have a different heap address than the original one, but both will refer to the same Node in the end.

  This is the implementation for unref():

  #[no_mangle]
  pub extern fn rsvg_node_unref (raw_node: *mut RsvgNode) -> *mut RsvgNode {
      if !raw_node.is_null () {
          let _ = unsafe { Box::from_raw (raw_node) };
      }
  
      ptr::null_mut () // so the caller can do "node = rsvg_node_unref (node);" and lose access to the node
  }
  	    

  This is very similar to the destructor from a few blog posts ago. Since the Box owns the Rc it contains, letting the Box go out of scope frees it, which in turn decreases the refcount in the Rc. However, note that this rsvg_node_unref(), intended to be called from C, always returns a NULL pointer. Together, both functions are to be used like this:

  RsvgNode *node = ...; /* acquire a node from Rust */
  
  RsvgNode *extra_ref = rsvg_node_ref (node);
  
  /* ... operate on the extra ref; now discard it ... */
  
  extra_ref = rsvg_node_unref (extra_ref);
  
  /* Here extra_ref == NULL and therefore you can't use it anymore! */
  	    

  This is a bit different from g_object_ref(), which returns the same pointer value as what you feed it. Also, the pointer that you would pass to g_object_unref() remains usable if you didn't take away the last reference... although of course, using it directly after unreffing it is perilous as hell and probably a bug.

  In these functions that you call from C but are implemented in Rust, ref() gives you a different pointer than what you feed it, and unref() gives you back NULL, so you can't use that pointer anymore.

  To ensure that I actually used the values as intended and didn't fuck up the remaining C code, I marked the function prototypes with the G_GNUC_WARN_UNUSED_RESULT attribute. This way gcc will complain if I just call rsvg_node_ref() or rsvg_node_unref() without actually using the return value:

  RsvgNode *rsvg_node_ref (RsvgNode *node) G_GNUC_WARN_UNUSED_RESULT;
  
  RsvgNode *rsvg_node_unref (RsvgNode *node) G_GNUC_WARN_UNUSED_RESULT;
  	    

  And this actually saved my butt in three places in the code when I was converting it to reference counting. Twice when I forgot to just use the return values as intended; once when the old code was such that trivially adding refcounting made it use a pointer after unreffing it. Make the compiler watch your back, kids!

  Testing

  One of the things that makes me giddy with joy is how easy it is to write unit tests in Rust. I can write a test for the refcounting machinery above directly in my node.rs file, without needing to use C.

  This is the test for ref and unref:

  #[test]
  fn node_refs_and_unrefs () {
      let node = Rc::new (Node::new (...));
  
      let mut ref1 = box_node (node);                            // "hand out a pointer to C"
  
      let new_node: &mut RsvgNode = unsafe { &mut *ref1 };       // "bring back a pointer from C"
      let weak = Rc::downgrade (new_node);                       // take a weak ref so we can know when the node is freed
  
      let mut ref2 = unsafe { rsvg_node_ref (new_node) };        // first extra reference
      assert! (weak.upgrade ().is_some ());                      // "you still there?"
  
      ref2 = unsafe { rsvg_node_unref (ref2) };                  // drop the extra reference
      assert! (weak.upgrade ().is_some ());                      // "you still have life left in you, right?"
  
      ref1 = unsafe { rsvg_node_unref (ref1) };                  // drop the last reference
      assert! (weak.upgrade ().is_none ());                      // "you are dead, aren't you?
  }
  	    

  And this is the test for two refcounts indeed pointing to the same Node:

  #[test]
  fn reffed_node_is_same_as_original_node () {
      let node = Rc::new (Node::new (...));
  
      let mut ref1 = box_node (node);                         // "hand out a pointer to C"
  
      let mut ref2 = unsafe { rsvg_node_ref (ref1) };         // "C takes an extra reference and gets a new pointer"
  
      unsafe { assert! (rsvg_node_is_same (ref1, ref2)); }    // but they refer to the same thing, correct?
  
      ref1 = rsvg_node_unref (ref1);
      ref2 = rsvg_node_unref (ref2);
  }
  	    

  Hold on! Where did that rsvg_node_is_same() come from? Since calling rsvg_node_ref() now gives a different pointer to the original ref, we can no longer just do "some_node == tree_root" to check for equality and implement a special case. We need to do "rsvg_node_is_same (some_node, tree_root)" instead. I'll just point you to the source for this function.

Fri 2017/Feb/03

• Algebraic data types in Rust, and basic parsing

  Some SVG objects have a preserveAspectRatio attribute, which they use to let you specify how to scale the object when it is inserted into another one. You know when you configure the desktop's wallpaper and you can set whether to Stretch or Fit the image? It's kind of the same thing here.

  

  The SVG spec specifies a simple syntax for the preserveAspectRatio attribute; a valid one looks like "[defer] <align> [meet | slice]". An optional defer string, an alignment specifier, and an optional string which can be meet or slice. The alignment specifier can be any one of these strings:

  none
  xMinYMin
  xMidYMin
  xMaxYMin
  xMinYMid
  xMidYMid
  xMaxYMid
  xMinYMax
  xMidYMax
  xMaxYMax

  (Boy oh boy, I just hate camelCase.)

  The C code in librsvg would parse the attribute and encode it as a bitfield inside an int:

  #define RSVG_ASPECT_RATIO_NONE (0)
  #define RSVG_ASPECT_RATIO_XMIN_YMIN (1 << 0)
  #define RSVG_ASPECT_RATIO_XMID_YMIN (1 << 1)
  #define RSVG_ASPECT_RATIO_XMAX_YMIN (1 << 2)
  #define RSVG_ASPECT_RATIO_XMIN_YMID (1 << 3)
  #define RSVG_ASPECT_RATIO_XMID_YMID (1 << 4)
  #define RSVG_ASPECT_RATIO_XMAX_YMID (1 << 5)
  #define RSVG_ASPECT_RATIO_XMIN_YMAX (1 << 6)
  #define RSVG_ASPECT_RATIO_XMID_YMAX (1 << 7)
  #define RSVG_ASPECT_RATIO_XMAX_YMAX (1 << 8)
  #define RSVG_ASPECT_RATIO_SLICE (1 << 30)
  #define RSVG_ASPECT_RATIO_DEFER (1 << 31)

  That's probably not the best way to do it, but it works.

  The SVG spec says that the meet and slice values (represented by the absence or presence of the RSVG_ASPECT_RATIO_SLICE bit, respectively) are only valid if the value of the align field is not none. The code has to be careful to ensure that condition. Those values specify whether the object should be scaled to fit inside the given area, or stretched so that the area slices the object.

  When translating that this C code to Rust, I had two choices: keep the C-like encoding as a bitfield, while adding tests to ensure that indeed none excludes meet|slice; or take advantage of the rich type system to encode this condition in the types themselves.

  Algebraic data types

  If one were to not use a bitfield in C, we could represent a preserveAspectRatio value like this:

  typedef struct {
      defer: gboolean;
      
      enum {
          None,
          XminYmin,
          XminYmid,
          XminYmax,
          XmidYmin,
          XmidYmid,
          XmidYmax,
          XmaxYmin,
          XmaxYmid,
          XmaxYmax
      } align;
      
      enum {
          Meet,
          Slice
      } meet_or_slice;
  } PreserveAspectRatio;
  	    

  One would still have to be careful that meet_or_slice is only taken into account if align != None.

  Rust has algebraic data types; in particular, enum variants or sum types.

  First we will use two normal enums; nothing special here:

  pub enum FitMode {
      Meet,
      Slice
  }
  
  pub enum AlignMode {
      XminYmin,
      XmidYmin,
      XmaxYmin,
      XminYmid,
      XmidYmid,
      XmaxYmid,
      XminYmax,
      XmidYmax,
      XmaxYmax
  }

  And the None value for AlignMode? We'll encode it like this in another type:

  pub enum Align {
      None,
      Aligned {
          align: AlignMode,
          fit: FitMode
      }
  }

  This means that a value of type Align has two variants: None, which has no extra parameters, and Aligned, which has two extra values align and fit. These two extra values are of the "simple enum" types we saw above.

  If you "let myval: Align", you can only access the align and fit subfields if myval is in the Aligned variant. The compiler won't let you access them if myval is None. Your code doesn't need to be "careful"; this is enforced by the compiler.

  With this in mind, the final type becomes this:

  pub struct AspectRatio {
      pub defer: bool,
      pub align: Align
  }

  That is, a struct with a boolean field for defer, and an Align variant type for align.

  Default values

  Rust does not let you have uninitialized variables or fields. For a compound type like our AspectRatio above, it would be nice to have a way to create a "default value" for it.

  In fact, the SVG spec says exactly what the default value should be if a preserveAspectRatio attribute is not specified for an SVG object; it's just "xMidYMid", which translates to an enum like this:

  let aspect = AspectRatio {
      defer: false,
      align: Align::Aligned {
          align: AlignMode::XmidYmid,
  	fit: FitMode::Meet
      }
  }

  One nice thing about Rust is that it lets us define default values for our custom types. You implement the Default trait for your type, which has a single default() method, and make it return a value of your type initialized to whatever you want. Here is what librsvg uses for the AspectRatio type:

  impl Default for Align {
      fn default () -> Align {
          Align::Aligned {
              align: AlignMode::XmidYmid,
              fit: FitMode::Meet
          }
      }
  }
  
  impl Default for AspectRatio {
      fn default () -> AspectRatio {
          AspectRatio {
              defer: false,
              align: Default::default ()    // this uses the value from the trait implementation above!
          }
      }
  }

  Librsvg implements the Default trait for both the Align variant type and the AspectRatio struct, as it needs to generate default values for both types at different times. Within the implementation of Default for AspectRatio, we invoke the default value for the Align variant type in the align field.

  Simple parsing, the Rust way

  Now we have to implement a parser for the preserveAspectRatio strings that come in an SVG file.

  The Result type

  Rust has a FromStr trait that lets you take in a string and return a Result. Now that we know about variant types, it will be easier to see what Result is about:

  #[must_use]
  enum Result<T, E> {
     Ok(T),
     Err(E),
  }

  This means the following. Result is an enum with two variants, Ok and Err. The first variant contains a value of whatever type you want to mean, "this is a valid parsed value". The second variant contains a value that means, "these are the details of an error that happened during parsing".

  Note the #[must_use] tag in Result's definition. This tells the Rust compiler that return values of this type must not be ignored: you can't ignore a Result returned from a function, as you would be able to do in C. And then, the fact that you must see if the value is an Ok(my_value) or an Err(my_error) means that the only way ignore an error value is to actually write an empty stub to catch it... at which point you may actually write the error handler properly.

  The FromStr trait

  But we were talking about the FromStr trait as a way to parse strings into values! This is what it looks like for our AspectRatio:

  pub struct ParseAspectRatioError { ... };
  
  impl FromStr for AspectRatio {
      type Err = ParseAspectRatioError;
  
      fn from_str(s: &str) -> Result<AspectRatio, ParseAspectRatioError> {
          ... parse the string in s ...
  
          if parsing succeeded {
              return Ok (AspectRatio { ... fields set to the right values ... });
          } else {
              return Err (ParseAspectRatioError { ... fields set to error description ... });
          }
      }
  }

  To implement FromStr for a type, you implement a single from_str() method that returns a Result<MyType, MyErrorType>. If parsing is successful you return the Ok variant of Result with your parsed value as Ok's contents. If parsing fails, you return the Err variant with your error type.

  Once you have that implementation, you can simply call "let my_result = AspectRatio::from_str ("xMidyMid");" and piece apart the Result as with any other Rust code. The language provides facilities to chain successful results or errors so that you don't have nested if()s and such.

  Testing the parser

  Rust makes it very easy to write tests. Here are some for our little parser above.

  #[test]
  fn parsing_invalid_strings_yields_error () {
      assert_eq! (AspectRatio::from_str (""), Err(ParseAspectRatioError));
  
      assert_eq! (AspectRatio::from_str ("defer foo"), Err(ParseAspectRatioError));
  }
  
  #[test]
  fn parses_valid_strings () {
      assert_eq! (AspectRatio::from_str ("defer none"),
                  Ok (AspectRatio { defer: true,
                                    align: Align::None }));
  
      assert_eq! (AspectRatio::from_str ("XmidYmid"),
                  Ok (AspectRatio { defer: false,
                                    align: Align::Aligned { align: AlignMode::XmidYmid,
                                                            fit: FitMode::Meet } }));
  }

  Using C-friendly wrappers for those fancy Rust enums and structs, the remaining C code in librsvg now parses and uses AspectRatio values that are fully implemented in Rust. As a side benefit, the parser doesn't use temporary allocations; the old C code built up a temporary list from split()ting the string. Rust's iterators and string slices essentially let you split() a string with no temporary values in the heap, which is pretty awesome.

Go backward in time to January 2017.

Federico Mena-Quintero <[email protected]> Fri 2017/Jun/09 13:21:26 CDT
This is a personal web page and it does not represent the position of my employer.