You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@avro.apache.org by cu...@apache.org on 2009/06/25 20:53:17 UTC
svn commit: r788462 [2/3] - in /hadoop/avro/trunk: ./
src/java/org/apache/avro/generic/ src/java/org/apache/avro/io/
src/java/org/apache/avro/io/doc-files/ src/test/java/org/apache/avro/io/
Added: hadoop/avro/trunk/src/java/org/apache/avro/io/doc-files/parsing.html
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/java/org/apache/avro/io/doc-files/parsing.html?rev=788462&view=auto
==============================================================================
--- hadoop/avro/trunk/src/java/org/apache/avro/io/doc-files/parsing.html (added)
+++ hadoop/avro/trunk/src/java/org/apache/avro/io/doc-files/parsing.html Thu Jun 25 18:53:16 2009
@@ -0,0 +1,599 @@
+<html>
+<head>
+<title>Avro schemas as LL(1) CFG definitions</title>
+</head>
+<body>
+
+<center><h1>Avro schemas as LL(1) CFG definitions</h1></center>
+
+This document shows how an Avro schema can be interpreted as the definition of a context-free grammar in LL(1). We use such an interpretation for two use-cases. In one use-case, we use them to validate readers and writers of data against a single Avro schema. Specifically, sequences of <code>Encoder.writeXyz</code> methods can be validated against a schema, and similarly sequences of <code>Decoder.readXyz</code> methods can be validated against a schema.
+
+The second use-case is using grammars to perform schema resolution. For this use-case, we've developed a subclass of <code>Decoder</code> which takes two Avro schemas as input -- a reader and a writer schema. This subclass accepts an input stream written according to the writer schema, and presents it to a client expecting the reader schema. If the writer writes a long, for example, where the reader expects a double, then the <code>Decoder.readDoubl</code> method will convert the writer's long into a double.
+
+This document looks at grammars in the context of these two use-cases. We first look at the single-schema case, then the double-schema case. In the future, we believe the interpretation of Avro schemas as CFGs will find other uses (for example, to determine whether or not a schema admits finite-sized values).
+
+
+<h1>The interpretation</h1>
+
+<p> We parse a schema into a set of JSON objects. For each record, map, array, union schema inside this set, this parse is going to generate a unique identifier "n<sub>i</sub>" (the "pointer" to the schema). By convention, n<sub>0</sub> is the identifier for the "top-level" schema (i.e., the schema we want to read or write). In addition, where n<sub>i</sub> is a union, the parse will generate a unique identifier "b<sub>ij</sub>" for each branch of the union.
+
+<p> A context-free grammar (CFG) consists of a set of terminal-symbols, a set of non-terminal symbols, a set of productions, and a start symbol. Here's how we interpret an Avro schema as a CFG:
+
+<p> <b>Terminal symbols:</b> The terminal symbols of the CFG consist of <code>null</code>, <code>bool</code>, <code>int</code>, <code>long</code>, <code>float</code>, <code>double</code>, <code>string</code>, <code>bytes</code>, <code>enum</code>, <code>fixed</code>, <code>arraystart</code>, <code>arrayend</code>, <code>mapstart</code>, <code>mapend</code>, and <code>union</code>. In addition, we define the special terminals <code>"1"</code>, <code>"2"</code>, <code>"3"</code>, <code>...</code> which designate the "tag" of a union (i.e., which branch of the union is actually being written or was found in the data).
+
+<p> Below, we use the variable <i>P</i> to represent any one of <code>null</code>, <code>bool</code>, <code>int</code>, <code>long</code>, <code>double</code>, <code>string</code>, <code>bytes</code> (i.e., the "primitives").
+
+<p><b>Non-terminal symbols:</b> The non-terminal symbols of the CFG consist of the identifiers n<sub>i</sub>, u<sub>i</sub>, r<sub>i</sub>, e<sub>i</sub>, f<sub>i</sub> and r<sub>p</sub> (there is a non-terminal r<sub>p</sub> for each symbol in <i>P</i>).
+
+<p><b>Productions:</b> The productions of the CFG are as follows:
+
+<p><i>Records:</i> If n<sub>i</sub> is a record-schema, then it defines the following production:
+<br> n<sub>i</sub> ::= sym(f<sub>i1</sub>) sym(f<sub>i2</sub>) .. sym(f<sub>im</sub>)
+<br>where f<sub>ij</sub> is field "j" of record n<sub>i</sub>, and sym(f<sub>ij</sub>) is the appropriate member of <i>P</i> if f<sub>ij</sub> is a primitive type, or the appropriate n<sub>k</sub> for some k if f<sub>ij</sub> is a map, array, union, or record schema.
+
+<p><i>Arrays:</i> If n<sub>i</sub> is an array schema, then it defines the following productions:
+<br> n<sub>i</sub> ::= <code>arraystart</code> r<sub>i</sub> <code>arrayend</code>
+<br> r<sub>i</sub> ::= sym(n<sub>i</sub>) r<sub>i</sub> | ε
+<br> where "sym(n<sub>i</sub>)" is either some <i>P</i>, if this is an array of primitives, or the non-terminal associated with the schema of the element-type of n<sub>k</sub>.
+
+<p><i>Maps:</i> If n<sub>i</sub> is a map schema of element type <i>P</i>, then it defines the following production:
+<br> n<sub>i</sub> ::= <code>mapstart</code> r<sub>i</sub> <code>mapend</code>
+<br> r<sub>i</sub> ::= <code>string</code> sym(n<sub>i</sub>) r<sub>i</sub> | ε
+<br> where "sym(n<sub>i</sub>)" is either some <i>P</i>, if the value-type is a primitive, or the non-terminal associated with the schema of the value-type of n<sub>k</sub>.
+
+<p><i>Unions:</i> If n<sub>i</sub> is a union schema, then it defines the following productions:
+<br> n<sub>i</sub> ::= <code>union</code> u<sub>i</sub>
+<br> u<sub>i</sub> ::= 1 sym(b<sub>i1</sub>) | 2 sym(b<sub>i2</sub>) | ... | j sym(b<sub>ij</sub>)
+<br> where the "1", "2", "3" are the tags for the union, and the b<sub>ij</sub> is branch "j" of union "n<sub>i</sub>", and sym(b<sub>ij</sub>) is the appropriate member of <i>P</i> if b<sub>ij</sub> is a primitive type, or the appropriate n<sub>k</sub> if b<sub>ij</sub> is a map, array, union, or record schema. (The introduction of the terminal symbol "UNION" plus the introduction of the additional non-terminal "u<sub>i</sub>" is a convenience to our parsing implementation.)
+
+<p><i>Enum</i> If n<sub>i</sub> is an enum schema, then it defines the following production:
+<br> n<sub>i</sub> ::= <code>enum</code> e<sub>i</sub>
+<br> e<sub>i</sub> ::= ε
+
+<br> Here there is no real production for e<sub>i</sub>. The symbol is used to associate some meta information such as the number of values in the enumeration.
+
+<p><i>Fixed</i> If n<sub>i</sub> is an fixed binary schema, then it defines the following production:
+<br> n<sub>i</sub> ::= <code>enum</code> f<sub>i</sub>
+<br> f<sub>i</sub> ::= ε
+
+<br> Here there is no real production for f<sub>i</sub>. The symbol is used to associate some meta information such as the size of the fixed binary.
+
+<p><b>Start symbol:</b> the starting symbol of the grammar is n<sub>0</sub>.
+
+<p>
+This grammar defined by the above transformation is LL(1). (Proof: The only alternatives in these grammars are for the u<sub>i</sub> ("union") symbols and the r<sub>i</sub> ("repeating") symbols. For "union" the alternative productions correspond to each one of the branches of the union. Each alternative production for a union starts of a unique tag-terminal, so by looking at the very first terminal one can decide which of the productions to select. In the case of the r<sub>k</sub>, there are two alternative production, the second of which is ε. Since these only appear inside <code>array</code>- or <code>mapstart</code>/<code>end</code> pairs, the <code>arrayend</code> or <code>mapend</code> symbol serves to predict that the ε should be selected and any other terminal symbol predicts that the other production should be selected.)
+
+Here's an example. Consider the schema:
+<pre>
+{
+ "type":"record", "name":"foo",
+ "fields":[
+ {"name":"bar","type":"double"},
+ {"name":"baz","type":{"type":"array", "items":"string"}},
+ {"name":"zip",
+ "type":{"type":"map",
+ "values":["null",{"type":"array", "items":"bytes"},"foo"]}},
+ ]
+}
+</pre>
+This schema generates the following grammar:
+<pre>
+ n0 ::= double n1 n2
+ r1 ::= string r1 | ε
+ n1 ::= arraystart r1 arrayend
+ r2 ::= string n3 r2 | ε
+ n2 ::= mapstart r2 mapend
+ u3 ::= 1 null | 2 n4 | 3 n0
+ n3 ::= union u3
+ r4 ::= bytes r4 | ε
+ n4 ::= arraystart r4 arrayend
+</pre>
+The symbol "n0" is the start-symbol for this grammar.
+
+<H1>Reminder on LL(1) parsing</H1>
+
+While there's lots of material on the Web on table-driven LL(1) parsing, it all tends to over complicate things. The best discussion I've found is in <i><a href=http://www.amazon.com/Crafting-Compiler-C-Charles-Fischer/dp/0805321667>Crafting a compiler</a></i>, by Fischer and LeBlanc (my copy is from 1988 -- I hope they quality hasn't slid since then). Here's a quick summary.
+
+Parsing is the process of attempting to prove that a string can be derived from a grammar. Top-down parsing attempts this proof in a top-down manner. You start with the start symbol of the grammar and you ask yourself "Hey, given the input string, how can I derive this start symbol?"
+
+Now, in general, the start-symbol can be derived from one of a finite number of alternative productions:
+<br> S ::= A<sub>11</sub> A<sub>12</sub> .. A<sub>1n<sub>1</sub></sub> | A<sub>21</sub> .. A<sub>2n<sub>2</sub></sub> | ... | A<sub>m1</sub> .. A<sub>mn<sub>m</sub></sub>
+<br>So the question of deriving the symbol "S" comes down to asking "Hey, given the input I'm looking at, which of these productions for S could have produced that input?" The key property of LL(1) grammars is that this question is easy to answer. All you need to do is look at the first token in your input, and that token tells you which of these alternatives could've produced that input. (This token is sometimes called the "lookahead symbol.")
+
+<p>So the idea is that you put your start symbol on the stack to initialize things. You pop that symbol off the stack, ask which production for S could've produced the input you're looking at, push that production back on the stack, and repeat. Let's fill in the details.
+
+<p>The parsing table for this parsing procedure is a function of two inputs and one output:
+<pre>
+ T: Non-terminal x Terminal --> Production
+</pre>
+Remember, a "production" is a sequence of symbols -- a mix of terminals and non-terminals -- that derive a non-terminal in the grammar.
+
+<p>This function <code>T</code> takes a a non-terminal, a terminal, and returns a production for the non-terminal. The non-terminal is the symbol you're trying to derive (from the top of the parsing stack); the terminal is the current symbol in your input stream (the lookahead symbol). If <code>X</code> is the first input and <code>a</code>, then the output is the unique production for <code>X</code> that can produce the input symbol <code>a</code>. (This function can also return the special result "Error" to indicate there is no such production, i.e., we can't parse the input.)
+
+<p>If you have such a table, then your parsing code looks like this:
+<pre>
+parse(Table T, TokenStream in):
+ Stack stack = new Stack(Table.startSymbol);
+ for (Token t = in.next(); t != EOF; t = in.next())
+ advance(stack, T, t);
+
+advance(Stack stack, Table T, Token t):
+ X = stack.pop();
+ while (! isTerminal(X)):
+ if T(X,t) yields production Y<sub>1</sub> Y<sub>2</sub> ... Y<sub>n</sub>):
+ // push production in reverse order, so we leave looking for
+ // the first symbol of the production
+ stack.push(Y<sub>n</sub>);
+ ...;
+ stack.push(Y<sub>2</sub>);
+ stack.push(Y<sub>1</sub>);
+ else, T(X,t) is undefined, so throw an error;
+ X = stack.pop(); // Repeat until we find a terminal
+
+ if X == t then return
+ else throw an error;
+</pre>
+
+
+
+<h1>Parsing tables for Avro</h1>
+
+Traditionally, the parsing table for an LL(1) grammar defined as follows:
+<pre>
+ T(A,y) = A ::= X<sub>1</sub> ... X<sub>n</sub> -- if y is in Predict(A ::= X<sub>1</sub> ... X<sub>n</sub>)
+ T(A,y) = Error -- otherwise
+</pre>
+where <code>Predict(A ::= X<sub>1</sub> ... X<sub>n</sub>)</code> returns the unique first symbol that predicts this particular production for <code>A</code>.
+
+<p>But in our case, almost all productions have a single alternative. If a non-terminal symbol <code>A</code> is on the top of the stack, then we don't even have to look at the input to figure out which production could derive <code>A</code> because there's only one such production! Thus, we can define a special parsing table for Avro-induced grammars as follows:
+<pre>
+ T(A,y) = A ::= sym(f<sub>i1</sub>) sym(f<sub>i2</sub>) .. sym(f<sub>im</sub>) -- if A is a record schema
+ T(A,y) = A ::= <code>arraystart</code> r<sub>i</sub> <code>arrayend</code> -- if A is the non-terminal for an array schema
+ T(A,y) = A ::= <code>mapstart</code> r<sub>i</sub> <code>mapend</code> -- if A is the non-terminal for an map schema
+ T(A,y) = A ::= <code>union</code> u<sub>i</sub> -- if A is a union schema
+ T(A,y) = A ::= y sym(b<sub>ij</sub>) -- if A is a u<sub>i</sub> schema (note the "y" inside this production)
+ T(A,y) = Error -- if A is "A ::= k sym(b<sub>ij</sub>)" and "y" isn't
+ -- in any of the branches of the corresponding union
+ T(A,y) = A ::= n<sub>i</sub> r<sub>i</sub> -- if A is r<sub>i</sub> and y is neither <code>arrayend</code> nor <code>mapend</code>
+ T(A,y) = A ::= ε -- if A is r<sub>i</sub> and y is either <code>arrayend</code> or <code>mapend</code>
+</pre>
+Note that only the last three rules for <code>T(A,y)</code> consider the lookahead symbol (i.e., only the last three rules actually look at the value of <code>y</code>). These are the rules for dealing with productions that have alternatives, i.e., the rules for unions (where there is an alternative for each branch) and the rules for repeaters (where there is one alternative for the "repeat" case and another alternative for the "end" case).
+
+<p>The nice thing about this alternative formulation of the parsing table is that we don't actually have to compute the predict set, which is not super complicated, but would be a pile of code to test and maintain.
+
+<p>It should be noted that the resulting parsing table catches errors in different states than the traditional LL(1) parsing table. For example, let's say our Schema is simply an array of ints, which induces the following grammar:
+<pre>
+ n<sub>0</sub> ::= <code>arraystart</code> r<sub>int</sub> <code>arrayend</code>
+ r<sub>int</sub> ::= int r<sub>int</sub> | ε
+</pre>
+The traditional LL(1) table would be:
+<pre>
+ T(n<sub>0</sub>,<code>arraystart</code>) = n<sub>0</sub> ::= <code>arraystart</code> r<sub>int</sub> <code>arrayend</code>
+ T(r<sub>int</sub>,int) = r<sub>int</sub> ::= int r<sub>int</sub>
+ T(r<sub>int</sub>,<code>arrayend</code>) = ε
+ T(A,y) = Error -- if (A,y) is none of the above
+</pre>
+while our parser table would be:
+<pre>
+ T'(n<sub>0</sub>,y) = n<sub>0</sub> ::= <code>arraystart</code> r<sub>int</sub> <code>arrayend</code> -- for all y
+ T'(r<sub>int</sub>,y) = r<sub>int</sub> ::= int r<sub>int</sub> -- for all y other than <code>arrayend</code>
+ T'(r<sub>int</sub>,<code>arrayend</code>) = ε
+</pre>
+Note that <code>T</code> is defined as <code>Error</code> for a lot of <code>(A,y)</code> pairs, but <code>T'</code> is defined as <code>Error</code> for <i>none</i> of them. How can this be?
+
+<p>The difference is that <code>T</code> catches many errors when terminals fail to appear in Predict sets, while <code>T'</code> catches the errors when terminals fail to match corresponding terminals on the parser stack. For example, let's say <code>r<sub>int</sub></code> is on the top of the parser stack, and the symbol <code>double</code> is arrives (which means, in practice, that a <code>writeDouble</code> call is encountered). In this case, a parser with the standard table will catch the error right away, because <code>double</code> is not in the predict-set for <code>r<sub>int</sub></code>. A parser with our alternative table will first replace the <code>r<sub>int</sub></code> on the stack with the sequence <code>int r<sub>int</sub></code> (with <code>int</code> on the top of the stack). It will <em>then</em> throw an error, because the input symbol <code>double</code> does not match the non-terminal <code>int</code> that's now on the top of the stack.
+
+<p>However, we believe that our modified parser will except exactly the same set of strings as the standard parser.
+
+
+<h1>Induction rules</h1>
+
+<p>The first section ("The interpretation") informally describes the grammer generated by an Avro schema. This section provides a more formal description using a set of induction rules. The earlier description in section one is fine for describing how a single Avro schema generates a grammar. But soon we're going to describe how two schemas together define a "resolving" grammar, and for that description we'll need the more formal mechanism described here.
+
+<p>The terminal and non-terminal symbols in our grammar are as described in the first section. Our induction rules will define a function "C(S)=<G,a>", which takes an Avro schema "S" and returns a pair consisting of a set of productions "X" and a symbol "a". This symbol "a" -- which is either a terminal, or a non-terminal defined by G -- generates the values described by schema S.
+
+<p>The first rule applies to all Avro primitive types:
+
+<table align=center>
+ <tr align=center><td><i>p</i> in {<code>null</code>, <code>boolean</code>, <code>int</code>, <code>long</code>, <code>double</code>, <code>string</code>, <code>bytes</code>}</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(<i>p</i>)=<{}, <i>p</i>></td></tr>
+</table>
+
+<p>This first rule does not generate any productions, and simply returns the terminal symbol corresponding to the primitive types of the schema.
+
+<p>The next rule applies to record schemas:
+
+<table align=center>
+ <tr><td align=center>
+ <table cellspacing=0 cellpadding=0><tr><td>S=</td><td><code>{"type":"record", "name":</code>a<code>,</code></td></tr>
+ <tr><td></td><td><code>"fields":[{"name":</code>F<sub>1</sub><code>, "type":</code>S<sub>1</sub><code>},</code>...<code>, {"name":</code>F<sub>n</sub><code>, "type":</code>S<sub>n</sub><code>}]}</code></td></tr></table></td></tr>
+ <tr align=center><td>C(S<sub>j</sub>)=<G<sub>j</sub>, f<sub>j</sub>></td></tr>
+ <tr align=center><td><hr></td></tr>
+ <tr align=center><td>C(S)=<G<sub>1</sub> ∪ ... ∪ G<sub>n</sub> ∪ {a::=f<sub>1</sub> f<sub>2</sub> ... f<sub>n</sub>}, a></td></tr>
+</tr>
+</table>
+
+<p>In this case, the set of output-productions consists of all the productions generated by the element-types of the record, plus a production that defines the non-terminal "n" to be the sequence of field-types. We return "n"as the grammar symbol representing this record-schema.
+
+<p>Next, we define the rule for arrays:
+
+<table align=center>
+ <tr align=center><td>S=<code>{"type":"array", "items":S<sub>e</sub>}</code></td></tr>
+ <tr align=center><td>C(S<sub>e</sub>)=<G<sub>e</sub>,e></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(S)=<G<sub>e</sub> ∪ {r ::= e r, r ::= ε, a ::= <code>arraystart</code> r <code>arrayend</code>}, a></td></tr>
+</table>
+
+<p>For arrays, the set of output productions again contains all productions generated by the element-type. In addition, we define <em>two</em> productions for "r", which represents the repetition of this element type. The first production is the recursive case, which consists of the element-type followed by "r" all over again. The next case is the base case, which is the empty production. Having defined this repetition, we can then define "n" as this repetation bracketed by the terminal symbols <code>arraystart</code> and <code>arrayend</code>.
+
+<p>The rule for maps is almost identical to that for arrays:
+
+<table align=center>
+ <tr align=center><td>S=<code>{"type":"map", "values":S<sub>e</sub>}</code></td></tr>
+ <tr align=center><td>C(S<sub>e</sub>)=<G<sub>e</sub>,e></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(S)=<G<sub>e</sub> ∪ {r ::= <code>string</code> e r, r ::= ε, a ::= <code>mapstart</code> r <code>mapend</code>}, a></td></tr>
+</table>
+
+<p>The only difference from arrays is that map-elements consists of a <code>string</code> together with an element-type (vs. just an element type).
+
+<p>The rule for unions:
+<table align=center>
+<tr align=center>
+ <td>S=[S<sub>1</sub>, S<sub>2</sub><code>, ..., S<sub>n</sub>]</td>
+</tr>
+<tr align=center>
+ <td>C(S<sub>j</sub>)=<G<sub>j</sub>, b<sub>j</sub>></td>
+</tr>
+<tr align=center><td><hr></td></tr>
+<tr align=center><td>C(S)=<G<sub>1</sub> ∪ ... ∪ G<sub>n</sub> ∪ {u::=1 b<sub>1</sub>, u::=2 b<sub>2</sub>, ..., u::=n b<sub>n</sub>, a::=<code>union</code> u}, a></td></tr>
+</table>
+
+<p>In this rule, we again accumulate productions (G<sub>j</sub>)generated by each of the sub-schemas contained by the top-level schemas. If there are "k" branches, we define "k" different productions for the non-terminal symbol "u", one for each branch in the union. These per-branch productions consist of the index of the branch (1 for the first branch, 2 for the second, and so-forth), followed by the symbol representing the schema of that branch. With these productions for "u" defined, we can define "n" as simply the terminal-symbol <code>union</code> followed by this non-terminal "u".
+
+
+<p>The rule for fixed size binaries:
+<table align=center>
+<tr align=center>
+ <td>S=<code>{"type"="fixed", "name"=a, "size"=s}</code></td>
+</tr>
+<tr align=center><td><hr></td></tr>
+<tr align=center><td>C(S)=<{a::=<code>fixed</code> f, f::=ε}, a></td></tr>
+</table>
+
+<p>In this rule, we define a new non-termial f which has associated size of the fixed-binary.
+
+<p>The rule for enums:
+<table align=center>
+<tr align=center>
+ <td>S=<code>{"type"="enum", "name"=a, "symbols"=["s1", "s2", "s3", ...]}</code></td>
+</tr>
+<tr align=center><td><hr></td></tr>
+<tr align=center><td>C(S)=<{a::=<code>enum</code> e, e::=ε}, a></td></tr>
+</table>
+
+<p>In this rule, we define a new non-termial f which has associated range of values.
+
+<h1>Resolution using action symbols</h1>
+
+We want to use grammars to represent Avro's rules for schema resolution. To do this, we need a way to encode certain actions that the parser should perform as part of the resolution. In particular:
+
+<ul>
+<li> <b>Resolver action:</b> when the writer writes a primitive type that can be promoted into the reader's type, we use a "resolver action" to aid in this process. This is used for only a limited number of cases: int->long, int->double, long->double, and double->long.
+
+<p> <li> <b>Skip action:</b> when writer's schema for a record contains fields that are not in the reader's schema, we to skip them. "Skip actions" are used for this purpose.
+
+<p> <li> <b>Field action:</b> the fields of a record can appear in different orders in the reader's and writer's schemas. In the API we're designing, to support streaming, fields will be returned to the reader in the order generated by the writer; we need to help the reader map this back to its own field-order. Field actions support this requirement.
+
+<p> <li> <b>Reader union actions:</b> the reader's schema can have a union where the writer's schema did not. For example, the writer's schema might call for simply a long, while the reader's schema calls for a union that contains a long among other things. The reader should experience the writer's long values as if they came from a union. Reader union actions support this requirement.
+
+<p> <li> <b>Writer union actions</b> are the dual of the previous case: the writer may write a union where the reader expects just one branch of the union. Writer union actions help bridge such situations.
+
+<p> <li> <b>Enum actions:</b> when we have reader- and writer-schema has enumerations, enum actions are used to map the writer's numerical value to the reader's numeric value.
+
+<p> <li> <b>Error actions:</b> in general, errors in schema-resolution can only be detected when data is being read. For example, if the writer writers a <code>[long, string]</code> union, and the reader is expecting just a <code>long</code>, an error is only reported when the writer sends a string rather than a long. Further, the Avro spec recommends that <em>all</em> errors be detected at reading-time, even if they could be detected earlier. Error actions support the deferral of errors.
+</ul>
+
+<p>These actions will become "action symbols" in our grammar. Action symbols are symbols that cause our parser to perform special activities when they appear on the top of the parsing stack. For example, when the skip-action makes it to the top of the stack, the parser will automatically skip the next value in the input stream. (Again, Fischer and LeBlanc has a nice description of action symbols.)
+
+<p>We're going to use induction rules to define a grammar. This time, our induction rules will define a two-argument function "C(W,R)=<G,a>", which takes two schema, the writer's and reader's schemas respectively. The results of this function the same as they where for the single-schema case.
+
+<p>The first rule applies to all Avro primitive types:
+
+<table align=center>
+ <tr align=center><td><i>p</i> in {<code>null</code>, <code>boolean</code>, <code>int</code>, <code>long</code>, <code>double</code>, <code>string</code>, <code>bytes</code>}</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(<i>p</i>,<i>p</i>)=<{}, <i>p</i>></td></tr>
+</table>
+
+<p> In this case, the writer and reader schemas agree, so the resulting grammar should just expect the agreed-upon primitive type.
+
+<p>The next rule deals with resolution of primitive types:
+
+<table align=center>
+ <tr align=center><td>w in {<code>int</code>, <code>long</code>, <code>double</code>}</td></tr>
+ <tr align=center><td>r in {<code>long</code>, <code>double</code>}</td></tr>
+ <tr align=center><td>w != r</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(w,r)=<{}, ResolverAction(w,r)></td></tr>
+</table>
+
+<p> When this parameterized action is encountered, the parser will resolve the writer's value into the reader's expected-type for that value. In the parsing loop, when we encounter this symbol, we use the "r" parameter of this symbol to check that the reader is asking for the right type of value, and we use the "w" parameter to figure out how to parse the data in the input stream.
+
+<p>On final possibility for pimitive types are incompatible types:
+
+<table align=center>
+ <tr align=center><td>The w,r pair does not fit the previous two rules, AND neither</td></tr>
+ <tr align=center><td>of the pair is a union, AND the pair aren't both compounds</td></tr>
+ <tr align=center><td>of the same type (i.e., two arrays, two records, or two maps)</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(w,r)=<{}, ErrorAction></td></tr>
+</table>
+
+<p> When this parameterized action is encountered, the parser will throw an error. Keep in mind that this symbol might be generated in the middle of a recursive call to "G." For example, if the reader's schema is long, and the writers is [long, string], we'll generate an error symbol for the string-branch of the union; if this branch is occurred in actual input, an error will then be generated.
+
+<p>The next rule deals with resolution fixed size binaries:
+
+<table align=center>
+ <tr align=center><td>w = {"type"="fixed", "name":"n1", "size"=s1}</td></tr>
+ <tr align=center><td>r = {"type"="fixed", "name":"n2", "size"=s2}</td></tr>
+ <tr align=center><td>n1 != n2 or s1 != s2</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(w,r)=<{}, ErrorAction></td></tr>
+</table>
+
+<table align=center>
+ <tr align=center><td>w = {"type"="fixed", "name":"n1", "size"=s1}</td></tr>
+ <tr align=center><td>r = {"type"="fixed", "name":"n2", "size"=s2}</td></tr>
+ <tr align=center><td>n1 == n2 and s1 == s2</td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(w,r)=<{ a::=<code>fixed</code> f, f::=ε}, a></td></tr>
+</table>
+
+If the names are identical and sizes are identical, then we match otherwise an error is generated.
+
+<p>The next rule deals with resolution enums:
+
+<table align=center>
+ <tr align=center><td>w = {"type"="enum", "symbols":[sw<sub>1</sub>, sw<sub>2</sub>, ..., sw<sub>m</sub>] }</td></tr>
+ <tr align=center><td>r = {"type"="enum", "symbols":[sr<sub>1</sub>, sr<sub>2</sub>, ..., sr<sub>n</sub>] }</td></tr>
+ <tr align=center><td>f<sub>i</sub> = EnumAction(i, j) if sw<sub>i</sub> == sr<sub>j</sub></td></tr>
+ <tr align=center><td>f<sub>i</sub> = ErrorAction if sw<sub>i</sub> does not match any sr<sub>j</sub></td></tr>
+ <tr><td><hr></td></tr>
+ <tr align=center><td>C(w,r)=<{ a::=<code>enum</code> e, e::=ε}, a></td></tr>
+</table>
+
+The symbol e has the set of actions f<sub>i</sub> associated with it. It chooses the right action based on the runtime data.
+
+<p>Now that we have rules for primitive types, we can define rules for compound types. First, let's look at records:
+
+<table align=center>
+<tr>
+ <td align=center>
+ <table cellspacing=0 cellpadding=0>
+ <tr>
+ <td>W=</td>
+ <td><code>{"type":"record","name":</code>w<code>,</code></td>
+ </tr>
+ <tr>
+ <td></td>
+ <td><code>"fields":[{"name":</code>E<sub>1</sub><code>,
+ "type":</code>S<sub>1</sub><code>},</code>...<code>,
+ {"name":</code>E<sub>n</sub><code>,
+ "type":</code>S<sub>n</sub><code>}]}</code></td>
+ </tr>
+ </table>
+ </td>
+</tr>
+<tr>
+ <td align=center>
+ <table cellspacing=0 cellpadding=0>
+ <tr>
+ <td>R=</td>
+ <td><code>{"type":"record", "name":</code>r<code>,</code></td>
+ </tr>
+ <tr>
+ <td></td>
+ <td><code>"fields":[{"name":</code>F<sub>1</sub><code>,
+ "type":</code>T<sub>1</sub><code>},</code>...<code>,
+ {"name":</code>F<sub>m</sub><code>,
+ "type":</code>T<sub>m</sub><code>}]}</code>
+ </td>
+ </tr>
+ </table>
+ </td>
+</tr>
+<tr align=center>
+ <td>{F<sub>1</sub>, ..., F<sub>m</sub>} is a
+ subset of {E<sub>1</sub>, ..., E<sub>n</sub>}</td>
+</tr>
+<tr>
+ <td align=center>
+ C(S<sub>j</sub>, T<sub>i</sub>)
+ = <G<sub>j</sub>, f<sub>j</sub>>
+ -- for all E<sub>j</sub>=F<sub>i</sub></td>
+</tr>
+ <td align=center>
+ C(S<sub>j</sub>)
+ = <G<sub>j</sub>, f<sub>j</sub>>
+ -- for all E<sub>j</sub> not in {F<sub>1</sub>, ..., F<sub>m</sub>}</td>
+</tr>
+<tr>
+ <td align=center>
+ <table>
+ <tr>
+ <td rowspan=2 valign=middle>f'<sub>j</sub>=</td>
+ <td><sub>/ </sub>FieldAction(i, E<sub>i</sub>) f<sub>j</sub>
+ -- if E<sub>j</sub>=F<sub>i</sub></td>
+ </tr>
+ <tr>
+ <td><sup>\ </sup>SkipAction(f<sub>j</sub>)
+ -- if E<sub>j</sub> not in {F<sub>1</sub>, ..., F<sub>m</sub>}</td>
+ </tr>
+ </table>
+ </td>
+</tr>
+<tr align=center><td><hr></td></tr>
+<tr align=center><td>C(W,R)=<G<sub>1</sub> ∪ G<sub>2</sub> ∪ ... ∪ G<sub>n</sub> ∪ { w::=f'<sub>1</sub> f'<sub>2</sub> ... f'<sub>n</sub> }, w></td></tr>
+</table>
+
+<p>The substance of this rule lies in the definion of the "f'<sub>j</sub>". If the writer's field F<sub>j</sub> is not a member of the reader's schema, then a skip-action is generated, which will cause the parser to automatically skip over the field without the reader knowing. (In this case, note that we use the <em>single</em>-argument version of "C", i.e., the version defined in the previous section!)
+
+If the wrtier's field F<sub>j</sub> <em>is</em> a member f the reader's schema, then "f'<sub>j</sub>" is a two-symbol sequence: the first symbol is a (parameterized) field-action which is used to tell the reader which of it's own fields is coming next, followed by the symbol for parsing the value written by the writer.
+
+<p>The above rule for records works only when the reader and writer have the same name, and the reader's fields are subset of the writer's. In other cases, an error is producted.
+
+<p> The rule for arrays is straight forward:
+
+<table align=center>
+<tr align=center>
+ <td>W=<code>{"type":"array", "items":S<sub>w</sub>}</code></td>
+</tr>
+<tr align=center>
+ <td>R=<code>{"type":"array", "items":S<sub>r</sub>}</code></td>
+</tr>
+<tr align=center>
+ <td>C(S<sub>w</sub>, S<sub>r</sub>)=<G<sub>e</sub>,e>
+</tr>
+<tr><td><hr></td></tr>
+<tr align=center><td>C(W,R)=<G<sub>e</sub> U {r ::= e r, r ::= ε, a ::= <code>arraystart</code> r <code>arrayend}, a></td></tr>
+</table>
+
+<p>Here the rule is largely the same as for the single-schema case, although the recursive use of G may result in productions that are very different. The rule for maps changes in a similarly-small way, so we don't bother to detail that case in this document.
+
+<p>The final rules are for unions. Let's first look at the case where the writer is a union but the reader is not:
+
+<table align=center>
+<tr align=center>
+ <td>W=[S<sub>1</sub>, ..., S<sub>n</sub>]</td>
+</tr>
+<tr align=center>
+ <td>R is not a union schema</td>
+</tr>
+<tr align=center>
+ <td>C(S<sub>j</sub>,R)=<G<sub>j</sub>, b<sub>j</sub>></td>
+</tr>
+<tr><td><hr></td></tr>
+<tr align=center><td>C(R,W)=<G<sub>1</sub> ∪ G<sub>2</sub> ∪ ... ∪ G<sub>n</sub> ∪ {a::=WriterUnionAction(b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>)}, a></td></tr>
+</table>
+
+<p>Here, a writer-union action is generated that looks much like a union did in the single-schema case. However, unlike in that case, the writer-union action will cause the parser to automatically interpret the writer's union value.
+
+<p> Now let's look when the reader expects a union. The first of these cases is an error case:
+
+<table align=center>
+<tr align=center>
+ <td>W is not a union schema</td>
+</tr>
+<tr align=center>
+ <td>R=[R<sub>1</sub>, ..., R<sub>n</sub>]</td>
+</tr>
+<tr><td>W does not resolve to any of the branches of R</td></tr>
+<tr><td><hr></td></tr>
+<tr><td align=center>C(W,R)=<{}, ErrorAction></td></tr>
+</table>
+
+<p>In this case, there's no way to resolve the two schemas, so we generate an error action to remind us of this fact at run-time. (Again, this error action might be under a branch of a containing union, and thus might never be triggered at run-time, so it wouldn't be correct to signal an error at "compile" time.)
+
+<p> Here's the non-error case:
+
+<table align=center>
+<tr align=center>
+ <td>W is not a union schema</td>
+</tr>
+<tr align=center>
+ <td>R=[R<sub>1</sub>, ..., R<sub>n</sub>]</td>
+</tr>
+<tr><td align=center>Branch "j" of R is the best match for W</td></tr>
+<tr><td align=center>C(W,R<sub>j</sub>)=< G,w></td></tr>
+<tr><td><hr></td></tr>
+<tr><td align=center>C(W,R)=<G, ReaderUnionAction(j,w)></td></tr>
+</table>
+
+<p> In this case, we can decide at "compile time" which of the branches of the reader will be the best match for the value that's going to be written by the writer. We then generate a reader union action, which tells the parser first, which branch-number of the reader's we should report to the schema, and then second which symbol to use to parse the writer's actual value.
+
+<p> The interesting case is when the writer's and reader's schemas are both unions:
+
+<table align=center>
+<tr align=center>
+ <td>W=[W<sub>1</sub>, ..., W<sub>n</sub>]</td>
+</tr>
+<tr align=center>
+ <td>R=[R<sub>1</sub>, ..., R<sub>m</sub>]</td>
+</tr>
+<tr align=center>
+ <td>C(W<sub>j</sub>, R)=<G<sub>j</sub>, b<sub>j</sub>></td>
+</tr>
+<tr><td><hr></td></tr>
+<tr align=center><td>C(W,R)=<G<sub>1</sub> ∪ ... ∪ G<sub>n</sub> ∪ {u::=1 b<sub>1</sub>, u::=2 b<sub>2</sub>, ..., u::=n b<sub>n</sub>, a::=<code>union</code> u}, a></td></tr>
+</table>
+
+<p> Note that in the inductive case ("C(W<sub>j</sub>, R)"), each <i>branch</i> of the writer ("W<sub>j</sub>") is compared to the <em>entire union</em> of the reader ("R"). Thus, one of the two previous cases (the error case or the reader-union case) gets generated for each branch of the writer's union.
+
+
+<h1>Resolving parser</h1>
+
+Here's a stylized version of the actual parsing code, with comments, to illustrate how a resolving-grammar is actually used. To better understand this code, compare it to the simple code for "advance" given earlier in this document.
+
+<pre>
+ Symbol advance(Stack stack, Table T, Symbol t, TokenStream in):
+ Symbol X = stack.pop();
+ while (! isTerminal(X)):
+ case X:
+ FieldAction:
+ // In this case, the main parsing loop can "ask" for the
+ // field information by passing a FieldAction symbol as
+ // "t". If it does, it'll get the (parameterized) symbol
+ // from the parsing table. If it doesn't ask for this
+ // information, then the information will be ignored.
+ if (isFieldAction(t)) return X;
+
+ SkipAction(productionToSkip):
+ // In this case we automatically skip the production we've
+ // been asked to skip
+ in.skip(productionToSkip);
+
+ WriterUnionAction(b_1, b_2, ..., b_n):
+ // In this case, we read from the token input-stream to
+ // determine the actual branch witten by the writer.
+ // We then push this branch on the parsing stack, to tell
+ // the parser what type of value to look for
+ int i = in.readIndex();
+ stack.push(b_i);
+
+ NonTerminal:
+ if T(X,t) yields production Y<sub>1</sub> Y<sub>2</sub> ... Y<sub>n</sub>):
+ // push production in reverse order, so we leave looking for
+ // the first symbol of the production
+ stack.push(Y<sub>n</sub>);
+ ...;
+ stack.push(Y<sub>2</sub>);
+ stack.push(Y<sub>1</sub>);
+ else, T(X,t) is undefined, so throw an error;
+
+ X = stack.pop();
+ }
+ // We've left the loop, so X is a terminal symbol:
+ case X:
+ ResolvingTable(w,r):
+ // If reader is looking for an "r", then the reader's
+ // looking for the right thing according to the reader's
+ // schema, but return the type actually written so the
+ // proper conversion can happen.
+ if (r == t) return w;
+
+ ReaderUnionAction(index,writerSym):
+ // Reader-union actions are allowed where the reader
+ // is expecting a union. In this case, we return the
+ // (parameterized!) reader-union-action symbol and
+ // the code above figures out what to do
+ if (t == union) return X;
+
+ ErrorAction:
+ throw the deferred error;
+
+ // Fall-through case:
+ if (X == t) then return X
+ else throw an aerror
+</pre>
Added: hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestParsingTable.java
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestParsingTable.java?rev=788462&view=auto
==============================================================================
--- hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestParsingTable.java (added)
+++ hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestParsingTable.java Thu Jun 25 18:53:16 2009
@@ -0,0 +1,205 @@
+package org.apache.avro.io;
+
+import java.util.BitSet;
+
+import org.apache.avro.Schema;
+import org.testng.Assert;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+public class TestParsingTable {
+ @Test(dataProvider="data")
+ public void test(String jsonSchema, int startSymbol,
+ int[][] nonTerminals,
+ int[][] productions) {
+ BitSet bs = new BitSet();
+ ParsingTable t = new ParsingTable(Schema.parse(jsonSchema));
+ t.toString();
+ if (t.isTerminal(t.root)) {
+ Assert.assertEquals(startSymbol, t.root);
+ } else {
+ checkSymbol(startSymbol, t, t.root, bs, nonTerminals, productions);
+ }
+ }
+
+ private void checkSymbol(int n, ParsingTable t, int node, BitSet bs,
+ int[][] nonTerminals, int[][] productions) {
+ if (t.isTerminal(node)) {
+ Assert.assertEquals(n, node);
+ } else {
+ if (! bs.get(n)) {
+ bs.set(n);
+ if (t.isUnion(node)) {
+ Assert.assertEquals(nonTerminals[n].length, t.size(node));
+ for (int i = 0; i < nonTerminals[n].length; i++) {
+ checkSymbol(nonTerminals[n][i], t, t.getBranch(node, i), bs,
+ nonTerminals, productions);
+ }
+ } else {
+ Assert.assertEquals(1, nonTerminals[n].length);
+ checkProduction(productions[nonTerminals[n][0]], t, node, bs,
+ nonTerminals, productions);
+ }
+ }
+ }
+ }
+
+ private void checkProduction(int[] n, ParsingTable t, int sym, BitSet bs,
+ int[][] nonTerminals, int[][] productions) {
+ Assert.assertTrue(t.isNonTerminal(sym) || t.isRepeater(sym) || t.isUnion(sym));
+ Assert.assertEquals(n.length, t.size(sym));
+ for (int i = 0; i < n.length; i++) {
+ checkSymbol(n[i], t, t.prods[i + sym], bs, nonTerminals, productions);
+ }
+ }
+
+ @DataProvider
+ public static Object[][] data() {
+ return new Object[][] {
+ // primitives
+ makePrimitiveTestData(ParsingTable.NULL),
+ makePrimitiveTestData(ParsingTable.BOOLEAN),
+ makePrimitiveTestData(ParsingTable.INT),
+ makePrimitiveTestData(ParsingTable.LONG),
+ makePrimitiveTestData(ParsingTable.FLOAT),
+ makePrimitiveTestData(ParsingTable.DOUBLE),
+ makePrimitiveTestData(ParsingTable.STRING),
+ makePrimitiveTestData(ParsingTable.BYTES),
+
+ // Simple arrays
+ makeArrayTestData(ParsingTable.BOOLEAN),
+ makeArrayTestData(ParsingTable.INT),
+ makeArrayTestData(ParsingTable.LONG),
+ makeArrayTestData(ParsingTable.FLOAT),
+ makeArrayTestData(ParsingTable.DOUBLE),
+ makeArrayTestData(ParsingTable.STRING),
+ makeArrayTestData(ParsingTable.BYTES),
+
+ // Simple maps
+ makeMapTestData(ParsingTable.BOOLEAN),
+ makeMapTestData(ParsingTable.INT),
+ makeMapTestData(ParsingTable.LONG),
+ makeMapTestData(ParsingTable.FLOAT),
+ makeMapTestData(ParsingTable.DOUBLE),
+ makeMapTestData(ParsingTable.STRING),
+ makeMapTestData(ParsingTable.BYTES),
+
+ // Simple records
+ makeRecordTestData(ParsingTable.BOOLEAN),
+ makeRecordTestData(ParsingTable.INT),
+ makeRecordTestData(ParsingTable.LONG),
+ makeRecordTestData(ParsingTable.FLOAT),
+ makeRecordTestData(ParsingTable.DOUBLE),
+ makeRecordTestData(ParsingTable.STRING),
+ makeRecordTestData(ParsingTable.BYTES),
+ makeRecordTestData(ParsingTable.BOOLEAN, ParsingTable.BOOLEAN),
+ makeRecordTestData(ParsingTable.BOOLEAN, ParsingTable.INT,
+ ParsingTable.LONG, ParsingTable.FLOAT, ParsingTable.DOUBLE,
+ ParsingTable.STRING, ParsingTable.BYTES),
+
+ // Simple unions
+ makeUnionTestData(ParsingTable.BOOLEAN),
+ makeUnionTestData(ParsingTable.INT),
+ makeUnionTestData(ParsingTable.LONG),
+ makeUnionTestData(ParsingTable.FLOAT),
+ makeUnionTestData(ParsingTable.DOUBLE),
+ makeUnionTestData(ParsingTable.STRING),
+ makeUnionTestData(ParsingTable.BYTES),
+ makeUnionTestData(ParsingTable.BOOLEAN, ParsingTable.INT),
+ makeUnionTestData(ParsingTable.BOOLEAN, ParsingTable.INT,
+ ParsingTable.LONG, ParsingTable.FLOAT, ParsingTable.DOUBLE,
+ ParsingTable.STRING, ParsingTable.BYTES),
+
+ // TODO: test complex structures (map of arrays, arrays of records etc.)
+ };
+ }
+
+ private static Object[] makePrimitiveTestData(int sym) {
+ return new Object[] { "\"" + ParsingTable.getTerminalName(sym) + "\"",
+ sym, null, null };
+ }
+
+ private static Object[] makeArrayTestData(int sym) {
+ return new Object[] {
+ "{\"type\":\"array\", \"items\": \"" +
+ ParsingTable.getTerminalName(sym) + "\"}",
+ 0, new int[][] { { 0 }, { 1 } },
+ new int[][] {
+ { ParsingTable.ARRAYEND, 1, ParsingTable.ARRAYSTART },
+ { 1, sym },
+ },
+ };
+ }
+
+ private static Object[] makeMapTestData(int sym) {
+ return new Object[] {
+ "{\"type\":\"map\", \"values\": \"" +
+ ParsingTable.getTerminalName(sym) + "\"}",
+ 0, new int[][] { { 0 }, { 1 } },
+ new int[][] {
+ { ParsingTable.MAPEND, 1, ParsingTable.MAPSTART },
+ { 1, sym, ParsingTable.STRING },
+ },
+ };
+ }
+
+ private static Object[] makeRecordTestData(int ... syms) {
+ return new Object[] {
+ getRecordSchema(syms),
+ 0,
+ new int[][] { { 0 } },
+ new int[][] { reverse(syms) },
+ };
+ }
+
+ private static int[] reverse(int[] syms) {
+ int[] result = new int[syms.length];
+ for (int i = 0; i < syms.length; i++) {
+ result[i] = syms[syms.length - 1 - i];
+ }
+ return result;
+ }
+
+ private static Object[] makeUnionTestData(int ... syms) {
+ return new Object[] {
+ getUnionSchema(syms),
+ 0,
+ new int[][] { { 0 }, syms },
+ new int[][] { { 1, ParsingTable.UNION }},
+ };
+ }
+
+ private static String getRecordSchema(int[] syms) {
+ StringBuffer sb = new StringBuffer();
+ sb.append("{\"type\":\"record\", \"name\":\"rec\", \"fields\":[");
+ for (int i = 0; i < syms.length; i++) {
+ if (i != 0) {
+ sb.append(",");
+ }
+ sb.append("{\"name\":\"f");
+ sb.append(i);
+ sb.append("\", \"type\":\"");
+ sb.append(ParsingTable.getTerminalName(syms[i]));
+ sb.append("\"}");
+ }
+
+ sb.append("]}");
+ return sb.toString();
+ }
+
+ private static String getUnionSchema(int[] syms) {
+ StringBuffer sb = new StringBuffer();
+ sb.append("[");
+ for (int i = 0; i < syms.length; i++) {
+ if (i != 0) {
+ sb.append(",");
+ }
+ sb.append("\"");
+ sb.append(ParsingTable.getTerminalName(syms[i]));
+ sb.append("\"");
+ }
+
+ sb.append("]");
+ return sb.toString();
+ }
+}
Added: hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingIO.java
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingIO.java?rev=788462&view=auto
==============================================================================
--- hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingIO.java (added)
+++ hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingIO.java Thu Jun 25 18:53:16 2009
@@ -0,0 +1,343 @@
+package org.apache.avro.io;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.util.Vector;
+
+import org.apache.avro.Schema;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+public class TestResolvingIO {
+ @Test(dataProvider="data")
+ public void testRead(String jsonWriterSchema,
+ String writerCalls,
+ String jsonReaderSchema,
+ String readerCalls) throws IOException {
+ test(jsonWriterSchema, writerCalls, jsonReaderSchema, readerCalls, -1);
+ }
+
+ @Test(dataProvider="data")
+ public void testSkip_0(String jsonWriterSchema,
+ String writerCalls,
+ String jsonReaderSchema,
+ String readerCalls) throws IOException {
+ test(jsonWriterSchema, writerCalls, jsonReaderSchema, readerCalls, 0);
+ }
+
+ @Test(dataProvider="data")
+ public void testSkip_1(String jsonWriterSchema,
+ String writerCalls,
+ String jsonReaderSchema,
+ String readerCalls) throws IOException {
+ test(jsonWriterSchema, writerCalls, jsonReaderSchema, readerCalls, 1);
+ }
+
+ @Test(dataProvider="data")
+ public void testSkip_2(String jsonWriterSchema,
+ String writerCalls,
+ String jsonReaderSchema,
+ String readerCalls) throws IOException {
+ test(jsonWriterSchema, writerCalls, jsonReaderSchema, readerCalls, 2);
+ }
+
+ private void test(String jsonWriterSchema, String writerCalls,
+ String jsonReaderSchema, String readerCalls, int skipLevel)
+ throws IOException {
+ for (int i = 0; i < 10; i++) {
+ testOnce(jsonWriterSchema, writerCalls, jsonReaderSchema,
+ readerCalls, skipLevel);
+ }
+ }
+
+ private void testOnce(String jsonWriterSchema,
+ String writerCalls,
+ String jsonReaderSchema,
+ String readerCalls,
+ int skipLevel) throws IOException {
+ Vector<Object> values = new Vector<Object>();
+ Schema writerSchema = Schema.parse(jsonWriterSchema);
+ byte[] bytes = TestValidatingIO.make(writerSchema, writerCalls,
+ values, false);
+ Schema readerSchema = Schema.parse(jsonReaderSchema);
+ // dump(bytes);
+ check(writerSchema, readerSchema, bytes, readerCalls, values.toArray(),
+ skipLevel);
+ }
+
+ private static void check(Schema wsc, Schema rsc, byte[] bytes,
+ String calls, Object[] values, int skipLevel) throws IOException {
+ // dump(bytes);
+ Decoder bvi= new BinaryDecoder(new ByteArrayInputStream(bytes));
+ Decoder vi = new ResolvingDecoder(wsc, rsc, bvi);
+ TestValidatingIO.check(vi, calls, values, skipLevel);
+ }
+
+ @DataProvider
+ public static Object[][] data() {
+ /**
+ * The first argument is a schema.
+ * The second one is a sequence of (single character) mnemonics:
+ * N null
+ * B boolean
+ * I int
+ * L long
+ * F float
+ * D double
+ * S string
+ * b bytes
+ * [ Start array
+ * ] End array
+ * { Start map
+ * } End map
+ * s start item
+ * 0-9 branch id for union
+ */
+ return new Object[][] {
+ { "\"null\"", "N", "\"null\"", "N" },
+ { "\"boolean\"", "B", "\"boolean\"", "B" },
+ { "\"int\"", "I", "\"int\"", "I" },
+ { "\"int\"", "I", "\"long\"", "L" },
+ // { "\"int\"", "I", "\"float\"", "F" }, // These promotions make sense?
+ { "\"int\"", "I", "\"double\"", "D" },
+ { "\"long\"", "L", "\"long\"", "L" },
+ // { "\"long\"", "L", "\"float\"", "F" }, // And this?
+ { "\"long\"", "L", "\"double\"", "D" },
+ { "\"float\"", "F", "\"float\"", "F" },
+ { "\"float\"", "F", "\"double\"", "D" },
+ { "\"double\"", "D", "\"double\"", "D" },
+ { "\"double\"", "D", "\"long\"", "L" },
+ { "\"string\"", "S", "\"string\"", "S" },
+ { "\"bytes\"", "b", "\"bytes\"", "b" },
+ { "{\"type\":\"fixed\", \"name\":\"fi\", \"size\": 0}", "f0",
+ "{\"type\":\"fixed\", \"name\":\"fi\", \"size\": 0}", "f0" },
+ { "{\"type\":\"fixed\", \"name\":\"fi\", \"size\": 10}", "f10",
+ "{\"type\":\"fixed\", \"name\":\"fi\", \"size\": 10}", "f10" },
+ { "{\"type\":\"enum\", \"name\":\"en\", \"symbols\":[\"v1\", \"v2\"]}",
+ "e2",
+ "{\"type\":\"enum\", \"name\":\"en\", \"symbols\":[\"v1\", \"v2\"]}",
+ "e2"},
+
+ { "{\"type\":\"array\", \"items\": \"boolean\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"boolean\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"int\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"long\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"long\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"long\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"long\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"float\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"float\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"float\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"double\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[]", },
+ { "{\"type\":\"array\", \"items\": \"string\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"string\"}", "[]" },
+ { "{\"type\":\"array\", \"items\": \"bytes\"}", "[]",
+ "{\"type\":\"array\", \"items\": \"bytes\"}", "[]" },
+
+ { "{\"type\":\"array\", \"items\": \"boolean\"}", "[c1sB]",
+ "{\"type\":\"array\", \"items\": \"boolean\"}", "[c1sB]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[c1sI]",
+ "{\"type\":\"array\", \"items\": \"int\"}", "[c1sI]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[c1sI]",
+ "{\"type\":\"array\", \"items\": \"long\"}", "[c1sL]" },
+ { "{\"type\":\"array\", \"items\": \"int\"}", "[c1sI]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[c1sD]" },
+ { "{\"type\":\"array\", \"items\": \"long\"}", "[c1sL]",
+ "{\"type\":\"array\", \"items\": \"long\"}", "[c1sL]" },
+ { "{\"type\":\"array\", \"items\": \"long\"}", "[c1sL]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[c1sD]" },
+ { "{\"type\":\"array\", \"items\": \"float\"}", "[c1sF]",
+ "{\"type\":\"array\", \"items\": \"float\"}", "[c1sF]" },
+ { "{\"type\":\"array\", \"items\": \"float\"}", "[c1sF]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[c1sD]" },
+ { "{\"type\":\"array\", \"items\": \"double\"}", "[c1sD]",
+ "{\"type\":\"array\", \"items\": \"double\"}", "[c1sD]" },
+ { "{\"type\":\"array\", \"items\": \"string\"}", "[c1sS]",
+ "{\"type\":\"array\", \"items\": \"string\"}", "[c1sS]" },
+ { "{\"type\":\"array\", \"items\": \"bytes\"}", "[c1sb]",
+ "{\"type\":\"array\", \"items\": \"bytes\"}", "[c1sb]" },
+
+ { "{\"type\":\"map\", \"values\": \"boolean\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"boolean\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"int\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"long\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"long\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"long\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"long\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"float\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"float\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"float\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"double\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"string\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"string\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": \"bytes\"}", "{}",
+ "{\"type\":\"map\", \"values\": \"bytes\"}", "{}" },
+ { "{\"type\":\"map\", \"values\": "
+ + "{\"type\":\"array\", \"items\":\"int\"}}", "{}",
+ "{\"type\":\"map\", \"values\": "
+ + "{\"type\":\"array\", \"items\":\"int\"}}", "{}" },
+
+ { "{\"type\":\"map\", \"values\": \"boolean\"}", "{c1sSB}",
+ "{\"type\":\"map\", \"values\": \"boolean\"}", "{c1sSB}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{c1sSI}",
+ "{\"type\":\"map\", \"values\": \"int\"}", "{c1sSI}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{c1sSI}",
+ "{\"type\":\"map\", \"values\": \"long\"}", "{c1sSL}" },
+ { "{\"type\":\"map\", \"values\": \"int\"}", "{c1sSI}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{c1sSD}" },
+ { "{\"type\":\"map\", \"values\": \"long\"}", "{c1sSL}",
+ "{\"type\":\"map\", \"values\": \"long\"}", "{c1sSL}" },
+ { "{\"type\":\"map\", \"values\": \"long\"}", "{c1sSL}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{c1sSD}" },
+ { "{\"type\":\"map\", \"values\": \"float\"}", "{c1sSF}",
+ "{\"type\":\"map\", \"values\": \"float\"}", "{c1sSF}" },
+ { "{\"type\":\"map\", \"values\": \"float\"}", "{c1sSF}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{c1sSD}" },
+ { "{\"type\":\"map\", \"values\": \"double\"}", "{c1sSD}",
+ "{\"type\":\"map\", \"values\": \"double\"}", "{c1sSD}" },
+ { "{\"type\":\"map\", \"values\": \"string\"}", "{c1sSS}",
+ "{\"type\":\"map\", \"values\": \"string\"}", "{c1sSS}" },
+ { "{\"type\":\"map\", \"values\": \"bytes\"}", "{c1sSb}",
+ "{\"type\":\"map\", \"values\": \"bytes\"}", "{c1sSb}" },
+ { "{\"type\":\"map\", \"values\": "
+ + "{\"type\":\"array\", \"items\":\"int\"}}", "{c1sS[c3sIsIsI]}",
+ "{\"type\":\"map\", \"values\": "
+ + "{\"type\":\"array\", \"items\":\"int\"}}", "{c1sS[c3sIsIsI]}" },
+
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"boolean\"}]}", "B",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"boolean\"}]}", "B" },
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"int\"}]}", "I",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"int\"}]}", "I"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"int\"}]}", "I",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"long\"}]}", "L"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"int\"}]}", "I",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"double\"}]}", "D"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"long\"}]}", "L",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"long\"}]}", "L" },
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"float\"}]}", "F",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"float\"}]}", "F"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"double\"}]}", "D",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"double\"}]}", "D"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"string\"}]}", "S",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"string\"}]}", "S"},
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"bytes\"}]}", "b",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f\", \"type\":\"bytes\"}]}", "b"},
+
+ // multi-field record
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"int\"},"
+ + "{\"name\":\"f2\", \"type\":\"double\"},"
+ + "{\"name\":\"f3\", \"type\":\"string\"}]}", "IDS",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"int\"},"
+ + "{\"name\":\"f2\", \"type\":\"double\"},"
+ + "{\"name\":\"f3\", \"type\":\"string\"}]}", "IDS" },
+ // multi-field record with promotions
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f0\", \"type\":\"boolean\"},"
+ + "{\"name\":\"f1\", \"type\":\"int\"},"
+ + "{\"name\":\"f2\", \"type\":\"float\"},"
+ + "{\"name\":\"f3\", \"type\":\"string\"}]}", "BIFS",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f0\", \"type\":\"boolean\"},"
+ + "{\"name\":\"f1\", \"type\":\"long\"},"
+ + "{\"name\":\"f2\", \"type\":\"double\"},"
+ + "{\"name\":\"f3\", \"type\":\"string\"}]}", "BLDS" },
+
+ // record with array
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"long\"},"
+ + "{\"name\":\"f2\", "
+ + "\"type\":{\"type\":\"array\", \"items\":\"int\"}}]}", "L[c1sI]",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"long\"},"
+ + "{\"name\":\"f2\", "
+ + "\"type\":{\"type\":\"array\", \"items\":\"int\"}}]}", "L[c1sI]" },
+
+ // record with map
+ { "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"long\"},"
+ + "{\"name\":\"f2\", "
+ + "\"type\":{\"type\":\"map\", \"values\":\"int\"}}]}", "L{c1sSI}",
+ "{\"type\":\"record\",\"name\":\"r\",\"fields\":["
+ + "{\"name\":\"f1\", \"type\":\"long\"},"
+ + "{\"name\":\"f2\", "
+ + "\"type\":{\"type\":\"map\", \"values\":\"int\"}}]}", "L{c1sSI}" },
+
+ { "[\"boolean\"]", "u0B", "[\"boolean\"]", "u0B" },
+ { "[\"int\"]", "u0I", "[\"int\"]", "u0I" },
+ { "[\"int\"]", "u0I", "[\"long\"]", "u0L" },
+ { "[\"int\"]", "u0I", "[\"double\"]", "u0D" },
+ { "[\"long\"]", "u0L", "[\"long\"]", "u0L" },
+ { "[\"long\"]", "u0L", "[\"double\"]", "u0D" },
+ { "[\"float\"]", "u0F", "[\"float\"]", "u0F" },
+ { "[\"float\"]", "u0F", "[\"double\"]", "u0D" },
+ { "[\"double\"]", "u0D", "[\"double\"]", "u0D" },
+ { "[\"string\"]", "u0S", "[\"string\"]", "u0S" },
+ { "[\"bytes\"]", "u0b", "[\"bytes\"]", "u0b" },
+
+ { "\"int\"", "I", "[\"int\"]", "u0I" },
+
+ { "[\"int\"]", "u0I", "\"int\"", "I" },
+ { "[\"int\"]", "u0I", "\"long\"", "I" },
+
+ { "[\"null\", \"int\"]", "u0N", "[\"null\", \"int\"]", "u0N" },
+ { "[\"boolean\", \"int\"]", "u0B", "[\"boolean\", \"int\"]", "u0B" },
+ { "[\"boolean\", \"int\"]", "u1I", "[\"boolean\", \"int\"]", "u1I" },
+ { "[\"boolean\", \"int\"]", "u1I", "[\"int\", \"boolean\"]", "u0I" },
+ { "[\"boolean\", \"int\"]", "u1I", "[\"boolean\", \"long\"]", "u1L" },
+ { "[\"boolean\", \"int\"]", "u1I", "[\"long\", \"boolean\"]", "u0L" },
+ { "[\"boolean\", {\"type\":\"array\", \"items\":\"int\"} ]", "u0B",
+ "[\"boolean\", {\"type\":\"array\", \"items\":\"int\"} ]", "u0B" },
+ { "[\"boolean\", {\"type\":\"array\", \"items\":\"int\"} ]", "u1[c1sI]",
+ "[\"boolean\", {\"type\":\"array\", \"items\":\"int\"} ]", "u1[c1sI]" },
+
+ // TODO: test more complicated types such as arrays of records
+ };
+ }
+
+ protected static void dump(byte[] bb) {
+ int col = 0;
+ for (byte b : bb) {
+ if (col % 16 == 0) {
+ System.out.println();
+ }
+ col++;
+ System.out.print(Integer.toHexString(b & 0xff) + " ");
+ }
+ System.out.println();
+ }
+
+}
Added: hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingTable.java
URL: http://svn.apache.org/viewvc/hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingTable.java?rev=788462&view=auto
==============================================================================
--- hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingTable.java (added)
+++ hadoop/avro/trunk/src/test/java/org/apache/avro/io/TestResolvingTable.java Thu Jun 25 18:53:16 2009
@@ -0,0 +1,389 @@
+package org.apache.avro.io;
+
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.avro.Schema;
+import org.testng.Assert;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+public class TestResolvingTable {
+ @Test(dataProvider="data")
+ public void test(String jsonWriterSchema, String jsonReaderSchema,
+ int startSymbol,
+ int[][] nonTerminals,
+ int[][] productions) {
+ BitSet bs = new BitSet();
+ ResolvingTable t = new ResolvingTable(Schema.parse(jsonWriterSchema),
+ Schema.parse(jsonReaderSchema));
+ if (t.isTerminal(t.root)) {
+ Assert.assertEquals(startSymbol, t.root);
+ } else {
+ checkSymbol(startSymbol, t, t.root, bs, nonTerminals, productions);
+ }
+ }
+
+ private void checkSymbol(int n, ResolvingTable t, int node, BitSet bs,
+ int[][] nonTerminals, int[][] productions) {
+ if (t.isTerminal(node)) {
+ Assert.assertEquals(n, node);
+ } else {
+ if (! bs.get(n)) {
+ bs.set(n);
+ if (isAction(n, SKIP_ACTION)) {
+ Assert.assertTrue(t.isSkipAction(node));
+ checkSymbol(n - SKIP_ACTION, t, t.getProductionToSkip(node), bs,
+ nonTerminals, productions);
+ } else if (isAction(n, FIELD_ACTION)) {
+ Assert.assertTrue(t.isFieldAction(node));
+ } else if (isAction(n, ERROR_ACTION)) {
+ Assert.assertTrue(t.isErrorAction(node));
+ Assert.assertNotNull(t.getMessage(node));
+ } else if (isAction(n, RESOLVER_ACTION)) {
+ Assert.assertTrue(t.isResolverAction(node));
+ checkSymbol(n - RESOLVER_ACTION, t, t.getResolverActual(node), bs,
+ nonTerminals, productions);
+ } else if (isAction(n, READER_UNION_ACTION)) {
+ Assert.assertTrue(t.isReaderUnionAction(node));
+ checkSymbol(n - READER_UNION_ACTION, t,
+ t.getReaderUnionSym(node), bs,
+ nonTerminals, productions);
+ } else {
+ if (t.isUnion(node)) {
+ Assert.assertEquals(nonTerminals[n].length, t.size(node));
+ for (int i = 0; i < nonTerminals[n].length; i++) {
+ checkSymbol(nonTerminals[n][i], t, t.getBranch(node, i), bs,
+ nonTerminals, productions);
+ }
+ } else {
+ Assert.assertEquals(1, nonTerminals[n].length);
+ checkProduction(productions[nonTerminals[n][0]], t, node, bs,
+ nonTerminals, productions);
+ }
+ }
+ }
+ }
+ }
+
+ private static boolean isAction(int n, int group) {
+ return ((((n + 500) / 1000) * 1000) == group);
+ }
+
+ private void checkProduction(int[] n, ResolvingTable t, int sym, BitSet bs,
+ int[][] nonTerminals, int[][] productions) {
+ Assert.assertTrue(t.isNonTerminal(sym) || t.isRepeater(sym) ||
+ t.isUnion(sym) || t.isReaderUnionAction(sym) ||
+ t.isWriterUnionAction(sym));
+ Assert.assertEquals(n.length, t.size(sym));
+ for (int i = 0; i < n.length; i++) {
+ checkSymbol(n[i], t, t.prods[i + sym], bs, nonTerminals, productions);
+ }
+ }
+
+ @DataProvider
+ public static Object[][] data() {
+ return
+ concat(primitiveTestData(),
+ new Object[][] {
+
+ // identical simple arrays
+ makeArrayTestData(ParsingTable.BOOLEAN, ParsingTable.BOOLEAN),
+ makeArrayTestData(ParsingTable.INT, ParsingTable.INT),
+ makeArrayTestData(ParsingTable.LONG, ParsingTable.LONG),
+ makeArrayTestData(ParsingTable.FLOAT, ParsingTable.FLOAT),
+ makeArrayTestData(ParsingTable.DOUBLE, ParsingTable.DOUBLE),
+ makeArrayTestData(ParsingTable.STRING, ParsingTable.STRING),
+ makeArrayTestData(ParsingTable.BYTES, ParsingTable.BYTES),
+
+ // identical simple maps
+ makeMapTestData(ParsingTable.BOOLEAN, ParsingTable.BOOLEAN),
+ makeMapTestData(ParsingTable.INT, ParsingTable.INT),
+ makeMapTestData(ParsingTable.LONG, ParsingTable.LONG),
+ makeMapTestData(ParsingTable.FLOAT, ParsingTable.FLOAT),
+ makeMapTestData(ParsingTable.DOUBLE, ParsingTable.DOUBLE),
+ makeMapTestData(ParsingTable.STRING, ParsingTable.STRING),
+ makeMapTestData(ParsingTable.BYTES, ParsingTable.BYTES),
+
+ // identical simple records
+ makeRecordTestData(new int[] { 0, ParsingTable.BOOLEAN },
+ new int[] { 0, ParsingTable.BOOLEAN }),
+ makeRecordTestData(new int[] { 0, ParsingTable.INT },
+ new int[] { 0, ParsingTable.INT }),
+ makeRecordTestData(new int[] { 0, ParsingTable.LONG },
+ new int[] { 0, ParsingTable.LONG }),
+ makeRecordTestData(new int[] { 0, ParsingTable.FLOAT },
+ new int[] { 0, ParsingTable.FLOAT }),
+ makeRecordTestData(new int[] { 0, ParsingTable.DOUBLE },
+ new int[] { 0, ParsingTable.DOUBLE }),
+ makeRecordTestData(new int[] { 0, ParsingTable.STRING },
+ new int[] { 0, ParsingTable.STRING }),
+ makeRecordTestData(new int[] { 0, ParsingTable.BYTES },
+ new int[] { 0, ParsingTable.BYTES }),
+ makeRecordTestData(new int[] { 0, ParsingTable.BOOLEAN,
+ 1, ParsingTable.INT, 2, ParsingTable.LONG, 3, ParsingTable.FLOAT,
+ 4, ParsingTable.DOUBLE, 5, ParsingTable.STRING,
+ 6, ParsingTable.BYTES },
+ new int[] { 0, ParsingTable.BOOLEAN, 1, ParsingTable.INT,
+ 2, ParsingTable.LONG, 3, ParsingTable.FLOAT,
+ 4, ParsingTable.DOUBLE, 5, ParsingTable.STRING,
+ 6, ParsingTable.BYTES }),
+ // Excess fields in writer
+ makeRecordTestData(new int[] { 0, ParsingTable.BOOLEAN,
+ 1, ParsingTable.INT, 2, ParsingTable.LONG, 3, ParsingTable.FLOAT,
+ 4, ParsingTable.DOUBLE, 5, ParsingTable.STRING,
+ 6, ParsingTable.BYTES },
+ new int[] { 0, ParsingTable.BOOLEAN, 2, ParsingTable.LONG,
+ 4, ParsingTable.DOUBLE, 5, ParsingTable.STRING,
+ 6, ParsingTable.BYTES }),
+ // promotions
+ makeRecordTestData(new int[] { 0, ParsingTable.INT },
+ new int[] { 0, ParsingTable.LONG }),
+
+ makeUnionTestData(new int[] { ParsingTable.BOOLEAN, },
+ new int[] { ParsingTable.BOOLEAN, }),
+ makeUnionTestData(new int[] { ParsingTable.INT, },
+ new int[] { ParsingTable.INT, }),
+ makeUnionTestData(new int[] { ParsingTable.LONG, },
+ new int[] { ParsingTable.LONG, }),
+ makeUnionTestData(new int[] { ParsingTable.FLOAT, },
+ new int[] { ParsingTable.FLOAT, }),
+ makeUnionTestData(new int[] { ParsingTable.DOUBLE, },
+ new int[] { ParsingTable.DOUBLE, }),
+ makeUnionTestData(new int[] { ParsingTable.STRING, },
+ new int[] { ParsingTable.STRING, }),
+ makeUnionTestData(new int[] { ParsingTable.BYTES, },
+ new int[] { ParsingTable.BYTES, }),
+ makeUnionTestData(new int[] { ParsingTable.BOOLEAN, ParsingTable.INT },
+ new int[] { ParsingTable.BOOLEAN, ParsingTable.INT }),
+ makeUnionTestData(
+ new int[] { ParsingTable.BOOLEAN, ParsingTable.INT,
+ ParsingTable.LONG, ParsingTable.FLOAT, ParsingTable.DOUBLE,
+ ParsingTable.STRING,
+ ParsingTable.BYTES },
+ new int[] { ParsingTable.BOOLEAN, ParsingTable.INT,
+ ParsingTable.LONG, ParsingTable.FLOAT, ParsingTable.DOUBLE,
+ ParsingTable.STRING, ParsingTable.BYTES }),
+ /*
+ { "\"int\"", "[\"int\"]", 0,
+ new int[][] { { 0 } },
+ new int[][] { { READER_UNION_ACTION + Table.INT, 0 } } },
+ { "[\"int\", \"boolean\"]", "\"int\"", 0,
+ new int[][] { { 0 } },
+ new int[][] { { READER_UNION_ACTION + Table.INT, 0 } } },
+ makeUnionTestData(
+ new int[] { Table.BOOLEAN, Table.INT,
+ Table.FLOAT, Table.STRING, Table.BYTES },
+ new int[] { Table.BOOLEAN, Table.LONG,
+ Table.DOUBLE, Table.STRING, Table.BYTES }),
+ */
+ });
+ }
+
+ private static Object[][] concat(Object[][]... parts) {
+ int t = 0;
+ for (Object[][] p : parts) {
+ t += p.length;
+ }
+ Object[][] result = new Object[t][];
+ int pos = 0;
+ for (Object[][] p : parts) {
+ System.arraycopy(p, 0, result, pos, p.length);
+ pos += p.length;
+ }
+ return result;
+ }
+
+ private static Object[][] primitiveTestData() {
+ // Primitives
+ return concat(
+ makePrimitiveTestData(ParsingTable.NULL),
+ makePrimitiveTestData(ParsingTable.BOOLEAN),
+ makePrimitiveTestData(ParsingTable.INT),
+ makePrimitiveTestData(ParsingTable.LONG),
+ makePrimitiveTestData(ParsingTable.FLOAT),
+ makePrimitiveTestData(ParsingTable.DOUBLE),
+ makePrimitiveTestData(ParsingTable.STRING),
+ makePrimitiveTestData(ParsingTable.BYTES));
+
+ }
+
+ private static Object[][] makePrimitiveTestData(int writeSym) {
+ return new Object[][] {
+ makePrimitiveTestData(writeSym, ParsingTable.NULL),
+ makePrimitiveTestData(writeSym, ParsingTable.BOOLEAN),
+ makePrimitiveTestData(writeSym, ParsingTable.INT),
+ makePrimitiveTestData(writeSym, ParsingTable.LONG),
+ makePrimitiveTestData(writeSym, ParsingTable.FLOAT),
+ makePrimitiveTestData(writeSym, ParsingTable.DOUBLE),
+ makePrimitiveTestData(writeSym, ParsingTable.STRING),
+ makePrimitiveTestData(writeSym, ParsingTable.BYTES),
+ };
+ }
+
+ private static Object[] makePrimitiveTestData(int writerSym, int readerSym) {
+ return new Object[] { "\"" + ParsingTable.getTerminalName(writerSym) + "\"",
+ "\"" + ParsingTable.getTerminalName(readerSym) + "\"",
+ resolvePrimitive(readerSym, writerSym), null, null };
+ }
+
+ private static int resolvePrimitive(int readerSym, int writerSym) {
+ if (readerSym == writerSym) {
+ return readerSym;
+ } else if (readerSym == ParsingTable.LONG) {
+ if (writerSym == ParsingTable.INT ||
+ writerSym == ParsingTable.DOUBLE ||
+ writerSym == ParsingTable.FLOAT) {
+ return RESOLVER_ACTION + writerSym;
+ }
+ } else if (readerSym == ParsingTable.DOUBLE) {
+ if (writerSym == ParsingTable.INT || writerSym == ParsingTable.LONG
+ || writerSym == ParsingTable.FLOAT) {
+ return RESOLVER_ACTION + writerSym;
+ }
+ }
+ return ERROR_ACTION;
+ }
+
+ private static Object[] makeArrayTestData(int writerSym, int readerSym) {
+ return new Object[] {
+ "{\"type\":\"array\", \"items\": \"" +
+ ParsingTable.getTerminalName(writerSym)
+ + "\"}",
+ "{\"type\":\"array\", \"items\": \"" +
+ ParsingTable.getTerminalName(readerSym)
+ + "\"}",
+ 0, new int[][] { { 0 }, { 1 } },
+ new int[][] {
+ { ParsingTable.ARRAYEND, 1, ParsingTable.ARRAYSTART },
+ { 1, readerSym },
+ },
+ };
+ }
+
+ private static final int FIELD_ACTION = 1000;
+ private static final int SKIP_ACTION = 2000;
+ private static final int ERROR_ACTION = 3000;
+ private static final int RESOLVER_ACTION = 4000;
+ private static final int READER_UNION_ACTION = 5000;
+
+ private static Object[] makeMapTestData(int writerSym, int readerSym) {
+ return new Object[] {
+ "{\"type\":\"map\", \"values\": \"" +
+ ParsingTable.getTerminalName(writerSym) + "\"}",
+ "{\"type\":\"map\", \"values\": \"" +
+ ParsingTable.getTerminalName(readerSym) + "\"}",
+ 0, new int[][] { { 0 }, { 1 } },
+ new int[][] {
+ { ParsingTable.MAPEND, 1, ParsingTable.MAPSTART },
+ { 1, readerSym, ParsingTable.STRING },
+ },
+ };
+ }
+
+ private static Object[] makeRecordTestData(int[] writerSyms,
+ int[] readerSyms) {
+ return new Object[] {
+ getRecordSchema(writerSyms),
+ getRecordSchema(readerSyms),
+ 0,
+ new int[][] { { 0 } },
+ new int[][] { makeRecordProduction(writerSyms, readerSyms) },
+ };
+ }
+
+ private static int[] makeRecordProduction(int[] writerSyms,
+ int[] readerSyms)
+ {
+ Map<Integer, Integer> m = new HashMap<Integer, Integer>();
+ int total = 0;
+ for (int i = 0; i < readerSyms.length; i += 2) {
+ int r = readerSyms[i];
+ int v = m.get(r) == null ? 0 : m.get(r);
+ m.put(r, v + 1);
+ total++;
+ }
+ for (int i = 0; i < writerSyms.length; i += 2) {
+ int w = writerSyms[i];
+ int v = m.get(w) == null ? 0 : m.get(w);
+ m.put(w, v + 1);
+ total++;
+ }
+ int[] result = new int[total];
+ int p = result.length;
+ for (int i = 0; i < writerSyms.length; i += 2) {
+ int w = writerSyms[i + 1];
+ int v = m.get(writerSyms[i]);
+ int r = 0;
+ for (int j = 0; j < readerSyms.length; j += 2) {
+ if (readerSyms[j] == writerSyms[i]) {
+ r = readerSyms[j + 1];
+ break;
+ }
+ }
+ if (v == 1) {
+ result[--p] = SKIP_ACTION + w;
+ } else {
+ result[--p] = FIELD_ACTION;
+ result[--p] = resolvePrimitive(r, w);
+ }
+ }
+ return result;
+ }
+
+ private static Object[] makeUnionTestData(int[] writerSyms,
+ int[] readerSyms) {
+ return new Object[] {
+ getUnionSchema(writerSyms),
+ getUnionSchema(readerSyms),
+ 0,
+ new int[][] { { 0 }, makeUnionProduction(writerSyms, readerSyms) },
+ new int[][] { { 1, ParsingTable.UNION } },
+ };
+ }
+
+ private static int[] makeUnionProduction(int[] writerSyms,
+ int[] readerSyms) {
+ int[] result = new int[writerSyms.length];
+ int i = 0;
+ for (int w : writerSyms) {
+ result[i++] = READER_UNION_ACTION + w;
+ }
+ return result;
+ }
+
+ private static String getRecordSchema(int[] syms) {
+ StringBuffer sb = new StringBuffer();
+ sb.append("{\"type\":\"record\",\"name\":\"n\", \"fields\":[");
+ for (int i = 0; i < syms.length; i += 2) {
+ if (i != 0) {
+ sb.append(",");
+ }
+ sb.append("{\"name\":\"f");
+ sb.append(syms[i]);
+ sb.append("\", \"type\":\"");
+ sb.append(ParsingTable.getTerminalName(syms[i + 1]));
+ sb.append("\"}");
+ }
+
+ sb.append("]}");
+ return sb.toString();
+ }
+
+ private static String getUnionSchema(int[] syms) {
+ StringBuffer sb = new StringBuffer();
+ sb.append("[");
+ for (int i = 0; i < syms.length; i++) {
+ if (i != 0) {
+ sb.append(",");
+ }
+ sb.append("\"");
+ sb.append(ParsingTable.getTerminalName(syms[i]));
+ sb.append("\"");
+ }
+
+ sb.append("]");
+ return sb.toString();
+ }
+}