1 // cycle.js

     2 // 2011-02-23

     3 

     4 /*jslint evil: true, regexp: false */

     5 

     6 /*members $ref, apply, call, decycle, hasOwnProperty, length, prototype, push,

     7     retrocycle, stringify, test, toString

     8 */

     9 

    10 if (typeof JSON.decycle !== 'function') {

    11     JSON.decycle = function decycle(object) {

    12         "use strict";

    13 

    14 // Make a deep copy of an object or array, assuring that there is at most

    15 // one instance of each object or array in the resulting structure. The

    16 // duplicate references (which might be forming cycles) are replaced with

    17 // an object of the form

    18 //      {$ref: PATH}

    19 // where the PATH is a JSONPath string that locates the first occurance.

    20 // So,

    21 //      var a = [];

    22 //      a[0] = a;

    23 //      return JSON.stringify(JSON.decycle(a));

    24 // produces the string '[{"$ref":"$"}]'.

    25 

    26 // JSONPath is used to locate the unique object. $ indicates the top level of

    27 // the object or array. [NUMBER] or [STRING] indicates a child member or

    28 // property.

    29 

    30         var objects = [],   // Keep a reference to each unique object or array

    31             paths = [];     // Keep the path to each unique object or array

    32 

    33         return (function derez(value, path) {

    34 

    35 // The derez recurses through the object, producing the deep copy.

    36 

    37             var i,          // The loop counter

    38                 name,       // Property name

    39                 nu;         // The new object or array

    40 

    41             switch (typeof value) {

    42             case 'object':

    43 

    44 // typeof null === 'object', so get out if this value is not really an object.

    45 

    46                 if (!value) {

    47                     return null;

    48                 }

    49 

    50 // If the value is an object or array, look to see if we have already

    51 // encountered it. If so, return a $ref/path object. This is a hard way,

    52 // linear search that will get slower as the number of unique objects grows.

    53 

    54                 for (i = 0; i < objects.length; i += 1) {

    55                     if (objects[i] === value) {

    56                         return {$ref: paths[i]};

    57                     }

    58                 }

    59 

    60 // Otherwise, accumulate the unique value and its path.

    61 

    62                 objects.push(value);

    63                 paths.push(path);

    64 

    65 // If it is an array, replicate the array.

    66 

    67                 if (Object.prototype.toString.apply(value) === '[object Array]') {

    68                     nu = [];

    69                     for (i = 0; i < value.length; i += 1) {

    70                         nu[i] = derez(value[i], path + '[' + i + ']');

    71                     }

    72                 } else {

    73 

    74 // If it is an object, replicate the object.

    75 

    76                     nu = {};

    77                     for (name in value) {

    78                         if (Object.prototype.hasOwnProperty.call(value, name)) {

    79                             nu[name] = derez(value[name],

    80                                 path + '[' + JSON.stringify(name) + ']');

    81                         }

    82                     }

    83                 }

    84                 return nu;

    85             case 'number':

    86             case 'string':

    87             case 'boolean':

    88                 return value;

    89             }

    90         }(object, '$'));

    91     };

    92 }

    93 

    94 

    95 if (typeof JSON.retrocycle !== 'function') {

    96     JSON.retrocycle = function retrocycle($) {

    97         "use strict";

    98 

    99 // Restore an object that was reduced by decycle. Members whose values are

   100 // objects of the form

   101 //      {$ref: PATH}

   102 // are replaced with references to the value found by the PATH. This will

   103 // restore cycles. The object will be mutated.

   104 

   105 // The eval function is used to locate the values described by a PATH. The

   106 // root object is kept in a $ variable. A regular expression is used to

   107 // assure that the PATH is extremely well formed. The regexp contains nested

   108 // * quantifiers. That has been known to have extremely bad performance

   109 // problems on some browsers for very long strings. A PATH is expected to be

   110 // reasonably short. A PATH is allowed to belong to a very restricted subset of

   111 // Goessner's JSONPath.

   112 

   113 // So,

   114 //      var s = '[{"$ref":"$"}]';

   115 //      return JSON.retrocycle(JSON.parse(s));

   116 // produces an array containing a single element which is the array itself.

   117 

   118         var px =

   119             /^\$(?:\[(?:\d?|\"(?:[^\\\"\u0000-\u001f]|\\([\\\"\/bfnrt]|u[0-9a-zA-Z]{4}))*\")\])*$/;

   120 

   121         (function rez(value) {

   122 

   123 // The rez function walks recursively through the object looking for $ref

   124 // properties. When it finds one that has a value that is a path, then it

   125 // replaces the $ref object with a reference to the value that is found by

   126 // the path.

   127 

   128             var i, item, name, path;

   129 

   130             if (value && typeof value === 'object') {

   131                 if (Object.prototype.toString.apply(value) === '[object Array]') {

   132                     for (i = 0; i < value.length; i += 1) {

   133                         item = value[i];

   134                         if (item && typeof item === 'object') {

   135                             path = item.$ref;

   136                             if (typeof path === 'string' && px.test(path)) {

   137                                 value[i] = eval(path);

   138                             } else {

   139                                 rez(item);

   140                             }

   141                         }

   142                     }

   143                 } else {

   144                     for (name in value) {

   145                         if (typeof value[name] === 'object') {

   146                             item = value[name];

   147                             if (item) {

   148                                 path = item.$ref;

   149                                 if (typeof path === 'string' && px.test(path)) {

   150                                     value[name] = eval(path);

   151                                 } else {

   152                                     rez(item);

   153                                 }

   154                             }

   155                         }

   156                     }

   157                 }

   158             }

   159         }($));

   160         return $;

   161     };

   162 }