Recursive parser from Binary to JSON output

Question

Background

I got this interview test and got declined due to not meeting their expectations, but never got a reason on what was bad and how they solved it. I want to improve and learn something out of it.

Question

How can this be better written and what is badly written?

Assignment description

To optimize the amount of data sent between the web browser to the web server a "clever" Javascript developer came up with the idea to translate JSON objects into binary format in the application and send them to the server. Faced with the fact that the Javascript is released in its final version to the customer it is now your task to develop the parser on the back end system.

A JSON object is a hierarchy of key-value pairs where a value in its turn can contain new key-value pairs. It consists of four basic types: numbers, strings, arrays and dictionaries. An array is a list of values and a dictionay is a list of key-value pairs. The key can only be of the type number or string while a value can be of any type.

A JSON object always starts with a value.

An example JSON object can look like:

{ 'firstName': 'John', 'lastName': 'Smith', 'age': 25, 'address': { 'streetAddress': '21 2nd Street', 'city': 'New York', 'state': 'NY', 'postalCode': '10021' }, 'phoneNumber': [ { 'type': 'home', 'number': '212 555-1234' }, { 'type': 'fax', 'number': '646 555-4567' } ] } 

A number is printed in decimal without any decoration. Example: 25

A string is printed in ASCII with single quotes in the start and end of the string. Example: 'test'

A key-value pair is printed as key followed by colon (:), a space ( ) and the value. Example: 'a': 67

A dictionary starts and ends with curly brackets ({ and }) and then has a comma (,) separated list of key-value pairs. Example: { 'name': 'Joe', 'age': 31 }

An array starts and ends with square brackets ([ and ]) and then has a comma (,) separated list of values. Example: [ 'hello', 56, 'world' ]

The binary representation of the JSON object contains a one byte identifier that describes the type of the data to follow and is then immediately followed by the data.

The identifiers and their types are as follows:

Identifier Type Description 0x01 Number 4 bytes signed integer in big endian byte order. 0x02 String N ASCII characters terminated by 0x00. 0x05 List Amount of items as a number followed by N values 0x06 Dictionary Amount of items as a number followed by N key-value pairs 

The program's task is to parse a binary file and prints it as human readable text. It should read the data from standard input and writes it the result to standard output.

Look at the files 'input_x' and their respective 'result_x' for examples of input and output. More background can be found on e.g. www.json.org

Input_4 binary

link to input_4 on gist

My solution

public class Main { private static String INPUT_FILENAME = "input_4"; private static String OUTPUT_FILENAME = "result_4"; private static String RESOURCE_INPUT_PATH = "src/main/resources/input/"; private static String RESOURCE_OUTPUT_PATH = "src/main/resources/output/"; public static void main(String[] args) { File resourcesDirectory = new File(String.format("%s%s", RESOURCE_INPUT_PATH, INPUT_FILENAME)); File file = new File(resourcesDirectory.getAbsolutePath()); try { byte[] byteArray = Files.readAllBytes(file.toPath()); RecursiveParser recursiveParser = new RecursiveParser(); try { String result = recursiveParser.parse(byteArray, 0, false).toString(); String prettyPrinted = prettyPrint(result); BufferedWriter writer = new BufferedWriter( new FileWriter( new File( String.format("%s%s%s", RESOURCE_OUTPUT_PATH, OUTPUT_FILENAME, ".json") ) ) ); writer.write(prettyPrinted); writer.close(); } catch (JSONException e) { e.printStackTrace(); } } catch (IOException e) { e.printStackTrace(); } } private static String prettyPrint(String data) throws JSONException { Object json = new JSONTokener(data).nextValue(); if (json instanceof JSONObject){ return (new JSONObject(data)).toString(4); } else if (json instanceof JSONArray){ return (new JSONArray(data)).toString(4); } else { return data; // nothing to pretty print } } } 

class RecursiveParser { private static int TERMINATE = 0x00; private static int NUMBER = 0x01; // Number 4 bytes signed integer in big endian byte order. private static int STRING = 0x02; // String N ASCII characters terminated by 0x00. private static int LIST = 0x05; // List Amount of items as a number followed by N values private static int DICTIONARY = 0x06; // Dictionary Amount of items as a number followed by N key-value pairs Object parse(byte[] byteArray, int index, boolean hasSub) throws JSONException { for(; index < byteArray.length; index++){ if(byteArray[index] == NUMBER){ return getNumber(byteArray, index); } if(byteArray[index] == STRING){ return getString(byteArray, index); } if(byteArray[index] == LIST){ return getList(byteArray, index, hasSub); } if(byteArray[index] == DICTIONARY){ return getDictionary(byteArray, index, hasSub); } } return null; // should never get here } private Object getDictionary(byte[] byteArray, int index, boolean hasSub) throws JSONException { index++; // move to size after type because dictionary size int dictionarySize = (int)parse(byteArray, index, hasSub); index += ByteBuffer.allocate(4).putInt(dictionarySize).array().length; JSONWriter jsonWriter = new JSONStringer() .object(); for(int i = 0; i < dictionarySize; i++){ index++; Object key = parse(byteArray, index, hasSub); int keyLength = 0; if(key instanceof Integer){ jsonWriter.key(String.valueOf(key)); keyLength += ByteBuffer.allocate(4).putInt((Integer) key).array().length; } else if(key instanceof String) { jsonWriter.key(String.valueOf(key)); keyLength += ((String) key).getBytes().length + 1; } index += keyLength + 1; // check if sub-array or sub-dictionary hasSub = hasSub || (byteArray[index] == DICTIONARY || byteArray[index] == LIST); Object value = parse(byteArray, index, hasSub); int valueLength = 0; if (value instanceof Integer) { jsonWriter.value(value); valueLength += ByteBuffer.allocate(4).putInt((Integer) value).array().length; } else if (value instanceof String) { jsonWriter.value(value); valueLength += String.valueOf(value).getBytes().length + 1; } else if (value instanceof AbstractMap.SimpleEntry) { valueLength = (int) ((AbstractMap.SimpleEntry) value).getKey() - index; jsonWriter.value(((AbstractMap.SimpleEntry) value).getValue()); } index += valueLength; } jsonWriter .endObject(); return hasSub && index != (byteArray.length - 1) ? new AbstractMap.SimpleEntry<>(index, new JSONObject(jsonWriter.toString())) : new JSONObject(jsonWriter.toString()); } private Object getList(byte[] byteArray, int index, boolean hasSub) throws JSONException { index++; // move to size after type because list size int listSize = (int)parse(byteArray, index, hasSub); index += ByteBuffer.allocate(4).putInt(listSize).array().length; JSONWriter jsonWriter = new JSONStringer().array(); for(int i = 0; i < listSize; i++){ index++; // check if sub-array or sub-dictionary hasSub = hasSub || byteArray[index] == DICTIONARY || byteArray[index] == LIST; Object value = parse(byteArray, index, hasSub); int valueLength = 0; if (value instanceof Integer) { jsonWriter.value(value); valueLength += ByteBuffer.allocate(4).putInt((Integer) value).array().length; } else if (value instanceof String) { jsonWriter.value(value); valueLength += String.valueOf(value).getBytes().length + 1; } else if (value instanceof AbstractMap.SimpleEntry) { valueLength = (int) ((AbstractMap.SimpleEntry) value).getKey() - index; jsonWriter.value(((AbstractMap.SimpleEntry) value).getValue()); } index += valueLength; } jsonWriter.endArray(); return hasSub && index != (byteArray.length - 1) ? new AbstractMap.SimpleEntry<>(index, new JSONArray(jsonWriter.toString())) : new JSONArray(jsonWriter.toString()); } private String getString(byte[] byteArray, int index) { int start = index + 1; // move to next value after type StringBuilder value = new StringBuilder(); for(int i = start; i < byteArray.length; i++){ if(byteArray[i] == TERMINATE){ break; } value.append((char)byteArray[i]); } return value.toString(); } private int getNumber(byte[] byteArray, int index) { int start = index + 1; // move to next value after type int offset = start + 4; byte[] numberByteArray = Arrays.copyOfRange(byteArray, start, offset); return new BigInteger(numberByteArray).intValue(); } } 

Result_4 output

{ "5": 25, "deep": { "1": "integer as key", "2": {"4": 19088743}, "mix": "it is possible to mix integers and strings" }, "first": 16777216, "second": "value for second" } 

Answer 1

There are two points that showed up immediately when looking at your implementation:

• You missed one of the goals of the task: It should read the data from standard input and writes it the result to standard output.
• You are reading in the complete binary data into memory and process it from there.

The latter is a no go, if we're talking about large structures of JSON-data, e.g. containing Base64-encoded binary data of a DVD-image (don't ask ;-) It might be unlikely in a real world example but it might let them come to the conclusion that you're not familiar with stream based processing and had another one how showed that ability which might have led to their decision.

Some remarks about the actual code:

Your reading-number-implementation:

private int getNumber(byte[] byteArray, int index) { int start = index + 1; // move to next value after type int offset = start + 4; byte[] numberByteArray = Arrays.copyOfRange(byteArray, start, offset); return new BigInteger(numberByteArray).intValue(); } 

The specification said that a number is a signed integer in big endian order which is exactly how a Java int is defined, so instead of creating temporary arrays and a BigInteger you could simply have used an int and used bit-shifting:

private int getNumber(byte[] byteArray, int index) { int ret = byteArray[index + 4] & 0xff; ret |= (byteArray[index + 3] & 0xff) < 8; ret |= (byteArray[index + 2] & 0xff) < 16; ret |= (byteArray[index + 1] & 0xff) < 24; return ret; } 

If you had implemented a stream based processing and used a DataInputStream the implementation would have been

private int getNumber(DataInputStream source) { return source.readInt(); } 

Your reading-text-implementation:

private String getString(byte[] byteArray, int index) { int start = index + 1; // move to next value after type StringBuilder value = new StringBuilder(); for(int i = start; i < byteArray.length; i++){ if(byteArray[i] == TERMINATE){ break; } value.append((char)byteArray[i]); } return value.toString(); } 

Not much that can be changed here but for good measure, I'd change (char)byteArray[i] to (char) (byteArray[i] & 0xff). For ASCII-characters that's irrelevant but still ;-)

In getDictionary:

private Object getDictionary(byte[] byteArray, int index, boolean hasSub) throws JSONException { [...] index += ByteBuffer.allocate(4).putInt(dictionarySize).array().length; 

That's a very elaborate form of

index += 4; 

because that's the number of bytes a signed integer is defined in the given specification.

keyLength += ((String) key).getBytes().length + 1; 

getBytes() uses the system's file-encoding. Because this particular example uses ASCII you won't see any effect on 99% of all systems but it would break on a system that runs e.g. with UTF-16 as file-encoding. You can see that youself by starting your Java test app with the system property -Dfile.encoding=UTF16.

This is a common Beginner's Error which might have raised a flag with them as well.

Always, ALWAYS use getBytes(encoding) unless you really want to use the system's file encoding for some reason.

hasSub = hasSub || (byteArray[index] == DICTIONARY || byteArray[index] == LIST); [...] } else if (value instanceof AbstractMap.SimpleEntry) { valueLength = (int) ((AbstractMap.SimpleEntry) value).getKey() - index; jsonWriter.value(((AbstractMap.SimpleEntry) value).getValue()); } 

This code block is duplicated in getList, you should put that into its own method and call it from the two methods. Same is true for the logic with the return-statement. This should be put into its own method so you only need to fix it once in case you find a bug in it.

General stuff:

You had to cope with the fact that your get-methods had to return a value and should change the value of the index. That's not possible, so you decided to change the index value in the calling method in dependence of the type of the returned parsed value. This is "not optimal" to say the least.