References in JSON

Modern object-oriented programming languages store data as objects which reference each other, in other words as a directed graph where each node is an object and each arc is a reference. JSON, on the other hand, can natively only represent trees, which are a strict subset of all possible directed graphs, specifically
$$ \begin{align*} \text{(trees)} &= \left\{ g \in \text{(directed graphs)} : \text{ one node in }g\text{ has zero predecessors and the others have exactly one} \right\} \\ &\subset \text{(directed graphs)} \end{align*} $$
In order to represent generic directed graphs in JSON, it's necessary to introduce reference semantics, in other words some mechanism to allow objects to be referenced by multiple predecessors, including objects they in turn reference (cycles).

Let's look at a few approaches that have been tried elsewhere

ID-based references

One approach is to recognise JSON dictionaries of the form

{ "$ref": <identifier> }

as a reference to the unique dictionary containing the key

{ "$id": <identifier>, ... }

This approach has the disadvantage that only JSON dictionary can be referenced, as there is no mechanism for assigning an id to an array

Path-based references

An alternative method is to reference other objects by describing where they are in relation to the referencing object. One popular proposal for doing this is JSONPath.

A simple object names-based approach

Getting back to our original problem, of how to represent an entire directed graph of objects, clearly it's necessary to have some way to retrieve at least a subset of those objects for manipulation, hence a JSON representation of the graph should have as the root object a dictionary associating names to objects.

When this is the case, it's very straightforward to reference objects via their associated names. In order to  represent any directed graph of objects, all that is needed is to assign arbitrary, unique names to multiply-referenced objects. Singly-referenced objects do not need to have names as they can be represented directly inline within the JSON document.

References can then be represented using the {"$ref": <id>} notation or even more simply by deciding on a custom marker such as the '@' sign and specifying that any string starting with that symbol is a reference to a named object. Clearly strings which are really supposed to start with '@' must be escaped, e.g. with a double '@@' which must be processed during the linking/unlinking algorithms.

Note that in reality this approach is not too dissimilar to the ID-based approach, but it provides a different way of assigning IDs which can be applied to any type of object, not just dictionaries.

C# implementation

Here is a C# implementation of the object names-based approach. Note that here it has been assumed that the JSON structure is represented in-memory with IDictionary and Array objects, but this can easily be generalized to any JSON value system. The linking and unlinking procedures act in-place, i.e. they modify the instances passed to them rather than returning new, modified instances.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace JsonUtils
{
  public class JsonLinker
  {
    public static void Link(IDictionary<string, object> vars)
    {
      Link(vars, vars);
    }

    static object Link(object obj, IDictionary<string, object> variables)
    {
      if(obj == null)
        return null;

      Type t = obj.GetType();
      if(obj is IDictionary<string, object>)
      {
        var dict = (IDictionary<string, object>) obj;
        foreach(var key in dict.Keys.ToArray())
          dict[key] = Link(dict[key], variables);
      }
      else if(obj is Array)
      {
        var a = (Array) obj;
        for(int k = 0; k < a.Length; k++)
          a.SetValue(Link(a.GetValue(k), variables), k);
      }
      else if(obj is string)
      {
        var s = (string) obj;
        if(s.Length >  0 && s[0] == '@')
        {
          if(s.Length > 1 && s[1] == '@')
            return s.Substring(1);
          else
            return variables[s.Substring(1)];
        }
      }

      return obj;
    }

    public static void Unlink(IDictionary<string, object> vars)
    {
      var context = new UnlinkContext(vars);
    }

    class UnlinkContext
    {
      IDictionary<string, object> variables;
      IDictionary<object, string> objects = new Dictionary<object, string>();
      ISet<object> visited = new HashSet<object>();

      public UnlinkContext(IDictionary<string, object> variables)
      {
        this.variables = variables;
        foreach(var kv in variables)
        {
          if(kv.Value != null && (kv.Value is IDictionary<string, object> || kv.Value is Array))
            objects[kv.Value] = kv.Key;
        }

        foreach(var v in variables.Values.ToArray())
          Traverse(v);

        foreach(var k in variables.Keys.ToArray())
          variables[k] = Unlink(variables[k], k);
      }

      void Traverse(object obj)
      {
        if(obj != null && (obj is IDictionary<string, object> || obj is Array))
        {
          if(visited.Contains(obj))
          {
            if(!objects.ContainsKey(obj))
            {
              string name = "obj" + objects.Count.ToString();
              objects.Add(obj, name);
              variables.Add(name, obj);
            }
            return;
          }

          visited.Add(obj);

          if(obj is IDictionary<string, object>)
          {
            var dict = (IDictionary<string, object>) obj;
            foreach(var value in dict.Values)
              Traverse(value);
          }
          else if(obj is Array)
          {
            var a = (Array) obj;
            for(int k = 0; k < a.Length; k++)
              Traverse(a.GetValue(k));
          }
        }
      }

      object Unlink(object obj, string label = null)
      {
        if(obj != null && (obj is IDictionary<string, object> || obj is Array))
        {
          string name;
          if(objects.TryGetValue(obj, out name) && name != label)
            return "@" + name;

          if(obj is IDictionary<string, object>)
          {
            var dict = (IDictionary<string, object>) obj;
            foreach(var key in dict.Keys.ToArray())
              dict[key] = Unlink(dict[key]);
          }
          else if(obj is Array)
          {
            var a = (Array) obj;
            for(int k = 0; k < a.Length; k++)
              a.SetValue(Unlink(a.GetValue(k)), k);
          }
          else if(obj is string)
          {
            var s = (string) obj;
            if(s.Length > 0 && s[0] == '@')
              return "@" + s;
          }
        }

        return obj;
      }
    }
  }
}