Introduction

Framing Algorithm

The framing algorithm takes an JSON-LD input (expanded input), which MUST be a JSON-LD document in expanded form, an input frame (expanded frame), which MUST be a JSON-LD frame in expanded form, a context (context), and a number of options and produces JSON-LD output.

If an error is detected in the expanded frame, a invalid frame error has been detected and processing is aborted. Need more specifics as to what constitutes a valid frame.

Set graph map to the result of performing the Node Map Generation algorithm on expanded input.

If the frameDefault option is present with the value true, set graph name to @default. Otherwise, create merged node map using the Merge Node Maps algorithm with graph map and add merged node map as the value of @merged in graph map and set graph name to @merged.

The recursive algorithm operates with a framing state (state), created initially using the object embed flag set to true, the explicit inclusion flag set to false, the require all flag set to true, the omit default flag set to false, graph map, graph name, along with map of flattened subjects set to the property associated with graph name in graph map, and graph stack set to an empty array. The initial values of the object embed flag, require all flag, and omit default flag MUST be overridden by values set in options. Also initialize results as an empty array.

Processors MAY use other runtime options to set different framing state defaults for values of state.

Invoke the recursive algorithm using framing state (state), the keys from the map of flattened subjects as subjects, expanded frame (frame), result as parent, and null as active property.

The recursive algorithm adds elements to parent either by appending the element to parent, if it is an array, or by appending it to an array associated with active property in parent, if it is a dictionary. Note that if parent is an array, active property MUST be null, and if it is a dictionary, it MUST NOT be null.

The following series of steps is the recursive portion of the framing algorithm:

1. If frame is an array, set frame to the first member of the array, which MUST be a valid frame.
2. Initialize flags embed, explicit, and requireAll from object embed flag, explicit inclusion flag, and require all flag in state overriding from any property values for @embed, @explicit, and @requireAll in frame.
3. Create a list of matched subjects by filtering subjects against frame using the Frame Matching algorithm with state, subjects, frame, and requireAll.
4. For each id and associated node object node from the set of matched subjects, ordered by id:

   Can we remove sorting, or make it subject to a processing flag? In general, sorting is a performance problem for JSON-LD, and inhibits stream processing.

   1. Initialize output to a new dictionary with @id and id.
   2. Otherwise, if embed is @never or if a circular reference would be created by an embed, add output to parent and do not perform additional processing for this node.
   3. Otherwise, if embed is @last, remove any existing embedded node from parent associate with graph name in state. Requires sorting of subjects. We could consider @sample, to embed just the first matched node. With sorting, we could also consider @first.
   4. If embed is @last or @always
      1. If graph map in state has an entry for id:
         1. If frame does not have the key @graph, set recurse to true, unless graph name in state is @merged and set subframe to a new empty dictionary.
         2. Otherwise, set subframe to the first entry for @graph in frame, or a new empty dictionary, if it does not exist, and set recurse to true, unless id is @merged or @default.
         3. If recurse is true:
            1. Push graph name from state onto graph stack in state.
            2. Set the value of graph name in state to id.
            3. Invoke the recursive algorithm using state, the keys from the graph map in state associated with id as subjects, subframe as frame, output as parent, and @graph as active property.
            4. Pop the value from graph stack in state and set graph name in state back to that value.
      2. For each property and objects in node, ordered by property:
         1. If property is a keyword, add property and objects to output.
         2. Otherwise, if property is not in frame, and explicit is true, processors MUST NOT add any values for property to output, and the following steps are skipped.
         3. For each item in objects:
            1. If item is a dictionary with the property @list, then each listitem in the list is processed in sequence and added to a new list dictionary in output:
               1. If listitem is a node reference, invoke the recursive algorithm using state, the value of @id from listitem as the sole member of a new subjects array, the first value from @list in frame as frame, list as parent, and @list as active property. If frame does not exist, create a new frame using a new dictionary with properties for @embed, @explicit and @requireAll taken from embed, explicit and requireAll. Could this use the list array, and null for active property?
               2. Otherwise, append a copy of listitem to @list in list.
            2. If item is a node reference, invoke the recursive algorithm using state, the value of @id from item as the sole member of a new subjects array, the first value from property in frame as frame, output as parent, and property as active property. If frame does not exist, create a new frame using a new dictionary with properties for @embed, @explicit and @requireAll taken from embed, explicit and requireAll.
            3. Otherwise, append a copy of item to active property in output.
      3. For each non-keyword property and objects in frame that is not in output:
         1. Let item be the first element in objects, which MUST be a frame object.
         2. Set property frame to the first item in objects or a newly created frame object if value is objects. property frame MUST be a dictionary.
         3. Skip property and property frame if property frame contains @omitDefault with a value of true, or does not contain @omitDefault and the value of the omit default flag is true.
         4. Add property to output with a new dictionary having a property @preserve and a value that is a copy of the value of @default in frame if it exists, or the string @null otherwise.
      4. If frame has the property @reverse, then for each reverse property and sub frame that are the values of @reverse in frame:
         1. Create a @reverse property in output with a new dictionary reverse dict as its value.
         2. For each reverse id and node in the map of flattened subjects that has the property reverse property containing a node reference with an @id of id:
            1. Add reverse property to reverse dict with a new empty array as its value.
            2. Invoke the recursive algorithm using state, the reverse id as the sole member of a new subjects array, sub frame as frame, null as active property, and the array value of reverse property in reverse dict as parent.
      5. Once output has been set are required in the previous steps, add output to parent.

If the processing mode is json-ld-1.1, remove the @id member of each node object where the member value is a blank node identifier which appears only once in any property value within result.

Using result from the recursive algorithm, set compacted results to the result of using the compact method using results, context, and options.

If the omit graph flag is false and compacted results does not have a top-level @graph member, or its value is not an array, modify compacted results to place the non @context properties of compacted results into a dictionary contained within the array value of @graph. If the omit graph flag is true, a top-level @graph member is used only to contain multiple node objects.

Recursively, replace all key-value pairs in compacted results where the key is @preserve with the value from the key-pair. If the value from the key-pair is @null, replace the value with null. If, after replacement, an array contains a single array value, replace the array with that value. If, after replacement, an array contains only the value null remove the value, leaving an empty array.

Return compacted results.