Trees of Objects & Meta


Tree data structures provide the foundation for most interactive systems. In most cases one can take an existing app, class, or collection of objects and represent it with a tree structure. HTML, XML, JSON, DOM, Flash displayList, file systems, and programming languages are all hierarchical in nature.

I have been interested in serializing & deserializing tree based systems for a long time and feel like there is a gap in terms of file formats. Tag based formats (XML/HTML) tend to be fragile given closing tags and are generally hard to read and edit accurately without tools. Minimalistic formats like JSON and YAML lack type metadata and can be confusing to read and edit as well. Also parsers for these formats tend to lean towards generating a complete object hierarchy as a result vs emitting stream of events allowing a single pass of object generation.

Long story short, I haven’t found somethings that fits well and decided to build one. I settled on calling the format “Meta”. Here is the base definition:

Meta – A simple readable ASCII based format for typed tree serialization & deserialization.

The driving use case for Meta was storing levels of a game where you would simply clear the display list and generate objects representing a level of the game. The key was having an event based parser that allowed for type generation on a line by line basis. I tested this in JavaScript, ActionScript, Lua, and Python and in every case it was trivial to generate typed objects from a single .meta file. This is when I started to think about this as a file format and generally how the project came to mind.

Basics:

//comment
<NAME>:<TYPE>=<VALUE>
<NAME>:<TYPE>
	<NAME>:<TYPE>=<VALUE>
	<NAME>:<TYPE>
		<NAME>:<TYPE>=<VALUE>

Rules:

  • <NAME>,<TYPE>,<VALUE> are strings using any non-whitespace char, must quote if “:” or “=” is used.
  • Indention denotes object heirarchy
  • Types follows the colon “:” similar to type declarations in ActionScript 3
  • Values follows the “=” and vary in syntax to the type used.

Examples:

s1:String = "Hello"
n1:Number = 1234
b1:Boolean = true
//comment
innerobj:Object
	src = logo.png
	x : Number = 0
	y : Number = 0
	isFullResolution : Boolean = true
	rotation : Number = -30
	alpha : Number = 0.5
c1 : Color = #FF00FF55
an1 : Array = [1,2,3,4,5,6,7]
obj0:Object
	1:Number = 1
	2 = 2
	3 = 0
	4: Boolean = true
obj1:Object
	src = "logo.png"
	//comment
	x : Number = 0
	y : Number = 0
	isFullResolution : Boolean = true
	rotation : Number = -30
	innerObj:Object
		src = "logo.png"
		x : Number = 0
		y : Number = 0
		isFullResolution : Boolean = true
		rotation : Number = -30
		alpha : Number = 0.5

One thing I really like about the format is that it is streamable in that parsing of the file can start as soon as downloading begins, all you need is a complete line regardless of hierarchy. This makes it very useful for data exchange as sometimes it is handy to stream data(large array collections or ui) to a client. Within the game usage the format sets up large object trees of box2b enabled displayobjects (think of a level in Angry Birds…). Combined with a class that manages object creation/destruction/recycling and it gets really scalable. I especially like the readability aspect, just glancing at the file you can see the object tree and all you need is a text editor. Within the game engine I implemented Library and Reference types to allow for reuse of generated objects within downstream objects and properties. This sort of mapping made wiring up function handlers and material types far easier.

Obviously Meta is far from complete but I have found it very useful thus far. As soon as I apply a bit more polish to the codebase I will post the Lua and ActionScript classes for parsing and serialization.

Thoughts and comments always welcome.

Cheers,

Ted :)

11 thoughts on “Trees of Objects & Meta

  1. Sho Kuwamoto

    Ted: what about extending something like JSON in a way that is compatible? For example:

    {
    “s1″: “Hello” /* String */,
    “n1″: 12345 /* Number */
    }

    It’s obviously not as pretty, but it seems like it might be a worthwhile trade for the ease of deserialization.

    Reply
    1. Ted Patrick Post author

      Initially I went down that path. I found JSON/XML became cumbersome to edit due to readability. I then switched to YAML but had very subtle issues with types and how the parser worked. Since I needed to have objects created as lines were read (streaming) that mandated a new parser. The good part is it is tiny and fast in JS/AS/Lua as a library and thus is easy to port as needed.

      Great to hear from you Sho!

      cheers,

      Ted :)

      Reply
  2. Angel Medrano

    Super! I recently got into Python after attending a talk you did at FITC. I’m in love with it. I love the simplicity, the indentation, readability. Can’t wait to see some examples of Meta in action!

    Reply
  3. Sho Kuwamoto

    Thanks, Ted.

    I’m actually interested in this for a practical reason, which is that we need this for Phile, which is kind of like a database in a way.

    Today, we do this:

    Page: http://library.101cookbooks.com/page/1607/Vegetarian_Cooking_for_Everyone

    Data (JSON): http://library.101cookbooks.com/page/1607/api/json

    By reading the JSON data, you can tell that this page belongs to stack 12, and you get the schema this way:

    Schema: http://library.101cookbooks.com/stack/12/api/json

    The full schema is needed for full functionality, but it would be nice to be able to notate the original data with types.

    Reply
    1. Ted Patrick Post author

      Let me get things cleaned up and posted to GIT.

      We should grab lunch and chat about Phile.com and NOOK. We are always looking for great services to integrate especially around books/reading reviews etc.

      Ted :)

      Reply
  4. Sven

    i wonder, since the format is not far from ActionScript, why not using ActionScript in the first place. You would only have to add some brackets and braces.

    Reply
  5. Erik

    Looks nice and clean.

    For objects (or HashMaps) you could introduce the {} literals like you use for arrays.

    The other way around is that it should be possible to use array like types like this:

    test:Array
    0=value

    Maybe add literals for the common types (saves typing the obvious).

    When you use real types it becomes quite annoying to type the package names. Maybe introduce something like import?

    Reply
  6. ianchia

    Hey Ted,

    (Sho too, hello!)

    Ted: Just found you’re blogging seriously bout Corona.

    Looks very handy. I’ll be keeping an eye out for it when you post the code to github or whatever.

    So it’s a streaming parser that’s extensible? Would be extremely handy to build into various parts of a toolchain for Lua/Corona – I can see all sorts of useful contexts for use – server side parsing of content for downstream consumption, or tools based generation – leverage mature IDEs like Flash or Fireworks to author assets with a MXP to spit out the framework for a .meta file. I’m *really* interested to see this. Thank you for wanting to share the codebase.

    – Ian

    Reply
  7. cm

    I love+ this idea! Its perfect solution for AS3 developers and you have really done a perfect comparison for the options… please get this avail I am super eager to try this out and help develop. “.meta” really perfect name :)

    Really a great idea!!!!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s