OGP LLSD Draft 3

Open Grid Protocol: LLIDL, LLSD and Structured Data Serialization
:Draft 3
:September 2008
::Notice: This draft is for public comment. 
::Mark Lentczner (Zero Linden) Linden Lab zero.linden@secondlife.com
::Meadhbh Hamrick (Infinity Linden) Linden Lab infinity@lindenlab.com
::Copyright 2008, Linden Lab. All rights reserved. 
::This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 license. See http://creativecommons.org/licenses/by-sa/3.0/for details. 
::All contributions to this document must be contributed under the Second Life Project Contribution Agreement. See http://wiki.secondlife.com/wiki/Project:Contribution_Agreementfor details 
:Abstract
::Services in the Open Grid Protcol are defined in terms of uniquely addressable stateful resources. These resources are used by client applications to query the state of distributed objects and to request state transitions in those objects. Interfaces to these resources are defined using the Linden Lab Interface Description Language (LLIDL). Resource requests and responses are defined in terms of abstract types. The Linden Lab Structured Data (LLSD) specification defines the type system and serialization methods to convert between abstract structured data and a sequence of octets suitable for transmission across a network. 
::LLIDL and LLSD are designed to match the facilities available in many dynamic programming languages, so that data may be represented in native data structures and accessed using built-in methods. Implementations also exist for non-dynamic languages providing easy access to concrete data structures defined using LLSD's abstract type syntax. 
:Status
::As of April 2008, LLSD has been defined and in use within Linden Lab for over three years. The version in use has been documented on Linden Lab's public wiki for over a year. This version differs only in recasting that wiki document into a standard format and formal specification of LLIDL. 
 discuss
== Abstract Interface Definition ==
As described in a previous section, the Open Grid is a distributed application executing concurrently on a widely scattered collection of systems. There is no one system or server that "runs the grid" but a constellation of systems, each maintaining the state of a collection of virtual objects. These objects interconnect, defining an "object graph" that at any time defines the state of the virtual world through the state of each of the objects and the references they hold to each other. 
To insure the harmonious inter-operation of each of the systems participating in the virtual world, well defined interactions describe unambiguously how changes in state are communicated between distributed objects. 
 discuss
== Type System ==
An LLSD value is either a simple datum or a composite structure. A simple data value may be accessed as a particular type, which influences how the data is interpreted. In general, a value that is transmitted or stored as one type, can be accessed as another, in which case well defined conversions govern how the data is transformed. In particular, it is expected that LLSD data may be serialized in systems with fewer types (e.g. JSON), or stored in native programming language structures with less percise types, and yet still interoperate in a predictable, reliable manner. Similarly, the two available composite structures, arrays and maps, have a consistent semantics that can be achieved accross a wide variety of systems. 
 discuss
=== Simple Types ===
For each type, conversions are defined to that type. That is, if a process is accessing a particular LLSD value, and treating it as a particular type, but the underlying type (as transmitted, or stored in memory) is different, then the indicated conversion, if available, is applied. If a conversion is not specified from a particular type, then if a value of that type is accessed, the result is the default value for the expected type. For example: When reading a value as an integer, if the underlying value is binary, then 0 is the value read. 
::Note: A number of normative references need to be looked up, and properly referenced: UUID formats, Date formats, URI formats. 
::Note: A number of conversions need better defintions: to/from numeric values and strings, handling NaNs and Infs when converting from (to?) Real, 
::Note: Some currently implemented conversions were ommitted as they hadn't be concieved as part of the standard. These are Map and Array to Boolean, and Date to/from Integer and Real. 
::Note: There are conversions listed in the public wiki LLSD page to and from Binary that are not implemented and have never been relied on. They have also been omitted. 
==== Type: Undefined ====
Data of type undefined has only one value, called undef. The default value is undef. There are no defined conversions to undefined. 
==== Type: Booolean ====
Data of type boolean has only two values, true and false. The default value is false. 
Conversions: 
Integer	
0 -> false, all other values -> true
Real	
all NaNs, and exactly 0 -> false, all other values -> true
String	
the empty string -> false, all others are true
==== Type: Integer ====
Data of type integer contains signed integral values from the range available with a 2s complement 32-bit binary representation. Integer values outside this range may not be representable. The default value is zero (0). 
Conversions: 
Boolean	
true becomes 1, false becomes 0
Real	
rounded to closest representable number, all NaNs -> 0
String	
the string is converted first to a Real, then converted as a Real
==== Type: Real ====
Data of type integer contains signed floating percesion numeric values from the range available with IEEE 754 64-bit double percsion values. Integer values outside this range may not be representable. The default value is zero (0). 
Conversions: 
Boolean	
true becomes 1, false becomes 0
Integer	
integral value as a real
String	
if the entire string is the decimal representation of a value, then that value, othewise 0
==== Type: String ====
Data of type string contains a sequence of zero or more Unicode characters. The default value is the empty string. 
The characters are restricted to the following code points: 
* U+0009, U+000A, U+000D 
* U+0020 through U+D7FF 
* U+E000 through U+FFFD 
* U+10000 through U+10FFFF 
Strings may be normalized during transport. When an implementation does normalize, it >>> rfc2119
should use Normalization Form C (NFC). Line endings may be normalizaed during transport to U+000A. 
Conversions: 
Boolean	
true becomes "true", false becomes the empty string ""
Integer	
decimal representation of value, with leading hypen for negative values
Real	
decimal representation of vlaue, using common signed exponent notation, with enough digits to represent full percision
UUID	
36 character hexadecimal representation with hyphens, as per RFC xxx
Date	
the ISO-8601 numeric representation of the date
URI	
the URI value as a string
==== Type: UUID ====
Data of type integer contains an unsigned 128 bit number. The default value is the null UUID, consisting of 128 zero bits. 
Only conversion from String is defined: strings in the RFC xxx 36 character format are intepreted as per that specification, all others are null UUID. 
==== Type: Date ====
A specific point in UTC time. Intervals or relative dates are not supported. The default date is the common "epoch": January 1st, 1970, Midnight UTC. 
Only conversion from String is defined: strings are interpreted as per ISO-8601 if the whole string can, otherise the default date. 
==== Type: URI ====
A string of characters representing a URI, as per RFC xxxx. The default value is an empty URI. 
Only conversion from String is defined: strings that can be interpreted as a valid URI are treated as a URI, otherwise the default URI. 
==== Type: Binary ====
An ordered sequence of zero or more octets. The defalut value is the empty sequence. There are not defined conversios to Binary. 
 discuss
== Serialization ==
When used as part of a protocol, LLSD is serialized into a common form. At present, the only serialization is the XML LLSD serialization. In the future, other serializations may be supported, in particular binary LLSD and JSON. The serialization format is negotiated and indicated using the normal facilities of HTTP. 
The MIME type for the XML serialization of LLSD is: 
 application/llsd+xml
::Note: JSON only allows maps and arrays as top level elements. Do we need to impose the same restriction on LLSD as used in resource requests and responses? 
 discuss
== Linden Lab Interface Description Language (LLIDL) ==
LLIDL (pronounced "little") is the language used to describe the interface to resources in the Open Grid Protocol. LLIDL is born of the need to unambiguously define interfaces independent of serialization schemes. Rather than defining BOTH JSON and XML interfaces, the OGP specification defines interfaces in terms of LLIDL which may then be mechanically converted into message parsers and generators for supported serialization schemes. The objective of LLIDL is therefore to provide a language for describing OGP messages that is human-readable but easily parsed by automated tools. 
OGP compliant systems expose "interfaces" to "resources." Each resource is an instance of a "resource class" which defines it's interface in a manner analogous to the way a "class" defines methods exposed by an object in an object-oriented programming environment. Interaction with an OGP compliant system is through messages which conform to a resource's interface. In the same way that LLSD defines the formatting rules for a valid message, LLIDL defines which LLSD messages are valid for a particular interface. 
 discuss
=== Abstract Data Types and Name ===
The core objective of LLIDL is to define abstract data structures for OGP resorces. To achieve this objective, LLIDL defines interfaces in terms of parameter names and parameter types. The association of a parameter name with a type is created by listing the parameter name, a colon and a parameter type. 
 parameter name : parameter type
 discuss
=== Abstract Data Structures ===
Collections of abstract type and name associations are defined as either lists or maps. Arrays represent a collection of items accessed by a numeric index while maps represent a collection accessed by a string key. The first example below defines an array with three real numbers, while the second defines a map with two strings. 
 [ real real real ]
 
 { first_name: string, last_name: string }
Arrays are delimited with the >>> emph
[ and >>> emph
] (open and close square brackets) characters while maps are delimited with the >>> emph
{ and >>> emph
} (open and close brace) characters. 
It is important to note that LLIDL defines an >>> emph
abstract language. It is used to specify the "shape" and contents of valid messages; it is not used as a serialization format. LLIDL is used to define 
 discuss
=== Variant Structures ===
Often times it is advantageous to represent several different variants of a message. LLIDL defines variants with repeated assignments to the same variant name. In the example below, two "exception" variants are defined, the first with two strings, and the second with a number and a string. 
Note there is no special meaning to the name "exception" save that afforded it by the protocol that uses it. In short, the term "result" or "condition" or even "oak_tree" could have been used and there would be no difference in the result (save potential confusion by users.) 
 &exception = {
 class : string ,
 description : string
 }
 
 &exception = {
 class : int ,
 description : string
 }
==== Optional Parameters and Defaults ====
One interesting aspect to LLIDL and LLSD is that when a structure is serialized, there is no semantic difference between an item being present with its default value and the item being completely absent. For instance, given the following structure: 
 &condition = {
 error : boolean,
 description : string
 }
Each of the following XML LLSD serializations are valid: 
 <?xml version="1.0"?> 
 <llsd> 
 <map> 
 <key>error</key> 
 <boolean>true</boolean> 
 <key>description</key> 
 <string>loose nut behind keyboard</string> 
 </map> 
 </llsd> 
 
 <?xml version="1.0"?> 
 <llsd> 
 <map> 
 <key>error</key> 
 <boolean>false</boolean> 
 </map> 
 </llsd> 
 
 <?xml version="1.0"?> 
 <llsd> 
 <map> 
 </map> 
 </llsd> 
 
To recap, from a semantic perspective, deserializing a LLSD XML object in which an item is missing is identical to that item being present with the default value for it's type. 
 discuss
=== Literal Discriminators ===
In the "exception" example above, two variants of a structure differ by the type defined for the "class" structure element. We also know that assertions may be missing from the serialization of an LLIDL object. It is often useful in these situtations to use boolean or string literals to distinguish variants of an object. 
In this example we see a boolean used to differentiate the two variants. 
 &response = {
 success : false ,
 description : string ,
 err_num : integer
 }
 
 &response = {
 success : true,
 description : string
 }
In the following example, we use a string to differentiate the classes of exception. 
 &exception = {
 class : 'encoding' , 
 description : string
 }
 
 &exception = {
 class : 'method' ,
 description : string ,
 result : int
 }
 
 &exception = {
 class : 'parsing' ,
 description : string ,
 line_num : int ,
 column_num : int 
 }
 discuss
=== Defining a Resource Interface ===
Defining interfaces is the underlying purpose of LLIDL. Each interface has a name, an input definition and an output definition. They are specified using the following format: 
 %% resource name -> request <- response
As an example, a resource that takes no inputs and returns a string value could be declared as: 
 %% version -> undef <- string
 discuss
=== Full ABNF of LLIDL ===
 value = type / array / map / selector / variant
 
 type = "undef"
 type =/ "string"
 type =/ "bool"
 type =/ "int"
 type =/ "real"
 type =/ "date"
 type =/ "uri"
 type =/ "uuid" 
 type =/ "binary"
 
 array = "[" s value-list s "]"
 array =/ "[" s value-list s "..." s "]"
 
 map = "{" s member-list s "}"
 map =/ "{" s "$" s ":" s value s "}"
 
 value-list = value [ s "," [ s value-list ] ]
 
 member-list = member [ s "," [ s member-list ] ]
 member = name s ":" s value
 
 selector = quote name quote
 selector =/ "true" / "false"
 selector =/ 1*digit
 
 variant = "&" name
 
 
 definitions = *( s / variant-def / resource-def )
 
 variant-def = "&" name s "=" s value
 
 resource-def = res-name s res-request s res-response
 res-name = "%%" s name
 res-request = "->" s value
 res-response = "<-" s value
 
 
 s = *( tab / newline / sp / comment )
 comment = ";" *char newline
 newline = lf / cr / (cr lf)
 
 tab = %x0009
 lf = %x000A
 cr = %x000D
 sp = %x0020
 quote = %x0022
 digit = %x0030-0039
 char = %x09 / %x20-D7FF / %xE000-FFFD / %x10000-10FFFF
 
 name = name_start *name_continue
 name_start = id_start / "_"
 name_continue = id_continue / "_" / "/"
 id_start = %x0041-005A / %x0061-007A ; ALPHA
 id_continue = id_start / %x0030-0039 ; DIGIT