Source file expand.ml

(*********************************************************************************)
(*                OCaml-RDF                                                      *)
(*                                                                               *)
(*    Copyright (C) 2012-2024 Institut National de Recherche en Informatique     *)
(*    et en Automatique. All rights reserved.                                    *)
(*                                                                               *)
(*    This program is free software; you can redistribute it and/or modify       *)
(*    it under the terms of the GNU Lesser General Public License version        *)
(*    3 as published by the Free Software Foundation.                            *)
(*                                                                               *)
(*    This program is distributed in the hope that it will be useful,            *)
(*    but WITHOUT ANY WARRANTY; without even the implied warranty of             *)
(*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              *)
(*    GNU General Public License for more details.                               *)
(*                                                                               *)
(*    You should have received a copy of the GNU General Public License          *)
(*    along with this program; if not, write to the Free Software                *)
(*    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA                   *)
(*    02111-1307  USA                                                            *)
(*                                                                               *)
(*    Contact: Maxence.Guesdon@inria.fr                                          *)
(*                                                                               *)
(*********************************************************************************)

(** Context processing and expansion. *)

module L = Log
open Rdf
module Log = L
open T
open J

let gen_delim_chars = [':' ; '/' ; '?' ; '#' ; '[' ; ']' ; '@' ]

type term_def = {
    iri : iri_mapping ;
    prefix: bool ;
    protected: bool;
    reverse_prop: bool ;
    base_url : Iri.t option ;
    local_ctx : J.json option ;
    container : string list option;
    direction : direction option option ; (* None: not specfied; Some None: explicitly no direction *)
    index : string option ;
    lang : string option option ; (* None: not specified; Some None: explicity no language *)
    nest_value : string option ;
    typ : type_mapping option ;
  }
and ctx = {
    defs : term_def SMap.t ;
    base : Iri.t option ;
    orig_base : Iri.t ;
    inverse_ctx : ctx option ;
    vocab : string option ;
    default_lang : string option ;
    default_base_direction : direction option ;
    prev_ctx : ctx option ;
  }

let rec json_of_term_def d =
  J.obj [
    ranged "iri", J.string (string_of_iri_mapping d.iri);
    ranged "prefix", J.bool d.prefix ;
    ranged "protected", J.bool d.protected ;
    ranged "reverse_prop", J.bool d.reverse_prop ;
    ranged "base_url", (match d.base_url with None -> J.null | Some i -> J.string (Iri.to_string i));
    ranged "local_ctx", (match d.local_ctx with None -> J.null | Some j -> j) ;
    ranged "container", J.list (List.map J.string (Option.value ~default:[] d.container)) ;
    ranged "direction", (match d.direction with None -> J.string "None"
     | Some None -> J.null
     | Some (Some d) -> J.string (string_of_direction d));
    ranged "index", J.string_of_opt d.index ;
    ranged "lang", (match d.lang with None -> J.string "None" | Some o -> J.string_of_opt o);
    ranged "nest_value", J.string_of_opt d.nest_value ;
    ranged "typ", J.string (string_of_type_mapping_opt d.typ) ;
  ]

and json_of_ctx ctx =
  J.obj [
    ranged "base", J.string_of_opt (Option.map Iri.to_string ctx.base);
    ranged "vocab", J.string_of_opt ctx.vocab;
    ranged "defs", J.obj (SMap.fold
     (fun k d acc -> (ranged k, json_of_term_def d) :: acc) ctx.defs []) ;
  ]

let pp_ctx ppf ctx =
  let j = json_of_ctx ctx in
  Format.fprintf ppf "%s" (J.to_string j)

let init_ctx base = {
    defs = SMap.empty ;
    base = Some base ; orig_base = base ;
    inverse_ctx = None ;
    vocab = None ;
    default_lang = None ;
    default_base_direction = None ;
    prev_ctx = None ;
  }

let equal_def_container l1 l2 =
  match l1, l2 with
  | Some l1, Some l2 ->
      (List.compare String.compare)
        (List.sort String.compare l1)
        (List.sort String.compare l2) = 0
  | None, None -> true
  | _ -> false

let def_equal d1 d2 =
  let b =
    d1.iri = d2.iri
      && d1.prefix = d2.prefix
      && d1.reverse_prop = d2.reverse_prop
      && Option.compare Iri.compare d1.base_url d2.base_url = 0
      && Option.compare J.compare d1.local_ctx d2.local_ctx = 0
      && equal_def_container d1.container d2.container
      && d1.direction = d2.direction
      && d1.index = d2.index
      && d1.lang = d2.lang
      && d1.nest_value = d2.nest_value
      && d1.typ = d2.typ
  in
  if not b then Log.debug (fun m -> m "definitions differ: %s <> %s"
       (J.to_string (json_of_term_def d1))
       (J.to_string (json_of_term_def d2)));
  b

let rec clone_def d = d
and clone_defs defs = SMap.map clone_def defs
and clone_ctx ctx =
  { ctx with
    defs = clone_defs ctx.defs ;
    prev_ctx = Option.map clone_ctx ctx.prev_ctx }

(* https://www.w3.org/TR/json-ld11-api/#dfn-add-value *)
let rec add_value =
  fun ?(as_array=false) map key value ->
    let map = (* 1) *)
      match as_array with
      | false -> map
      | true ->
          match SMap.find_opt key map with
          | None -> SMap.add key (J.list []) map
          | Some { data = `List _ } -> map
          | Some v -> SMap.add key (J.list [v]) map
    in
    match value.data with
    | `List elts (* 2) *) ->
        List.fold_left (fun map v -> add_value map key v) map elts
    | _ (* 3) *) ->
        match SMap.find_opt key map with
        | None -> (* 3.1) *) SMap.add key value map
        | Some v -> (* 3.2) *)
            let l = match v.data with
              | `List l -> l
              | _ -> [v]
            in
            let v = J.list (l @ [value]) in
            SMap.add key v map

let load_remote_context options remote_ctxs iri =
  match Iri.Map.find_opt iri remote_ctxs with
  | Some c -> Lwt.return (remote_ctxs, c)
  | None ->
      let%lwt remote_json = load_remote_json options.document_loader iri in
      match J.(remote_json -?>"@context") with
      | None -> error (Invalid_remote_context (iri, "Missing @context entry"))
      | Some json ->
          let remote_ctxs = Iri.Map.add iri json remote_ctxs in
          Lwt.return (remote_ctxs, json)


(* 19.1) to 19.3) in https://www.w3.org/TR/json-ld11-api/#create-term-definition *)
let to_container_mapping options json =
  (if options.processing_mode = "json-ld-1.0" then
     match json.data with
     | `String ("@graph"|"@id"|"@type") -> error (Invalid_container_mapping json)
     | `String _ -> ()
     | _ -> error (Invalid_container_mapping json)
  );

  let strings = List.map
    (function { data = `String s } -> s | _ -> error (Invalid_container_mapping json))
      (J.values json)
  in
  match List.sort String.compare strings with
  | [ "@graph"|"@id"|"@index"|"@language"|"@list"|"@set"|"@type" ] -> strings
  | [ "@graph" ; ("@id"|"@index") ]
  | [ "@graph" ; ("@id"|"@index") ; "@set" ] -> strings
  | _ ->
      if List.length strings >=2 && List.mem "@set" strings &&
        (List.for_all
         (function "@set"|"@index"|"@graph"|"@id"|"@type"|"@language"-> true | _ -> false)
           strings)
      then
        strings
      else
        error (Invalid_container_mapping json)

let authorized_def_entries = SSet.of_list
  [ "@id"; "@reverse"; "@container"; "@context"; "@direction";
    "@index"; "@language"; "@nest" ; "@prefix" ; "@protected" ; "@type" ]

let iri_mapping_of_json term j =
 match j.data with
  | `String iri when str_is_iri iri -> `Iri iri
  | `String "@context" -> error (Invalid_keyword_alias (term, "@context"))
  | `String kw when str_is_kw kw -> `Keyword kw
  | `String id when str_is_blank_node_id id -> `Bnode id
  | _ -> error (Invalid_iri_mapping j)

    (* https://www.w3.org/TR/json-ld11-api/#create-term-definition *)
let rec create_term_definition options ?(protected=false)
  ?(override_protected=false) ?(base_url=iri_of_string "") ?(remote_ctxs=Iri.Map.empty)
    ?(validate_scoped_ctx=true) active_ctx local_ctx term defined =
    Log.warn (fun m -> m "create_term_definition term=%S" term);
  match SMap.find_opt term defined with
  | Some true -> Lwt.return (active_ctx, defined) (* 1) *)
  | Some false ->
      Log.debug (fun m -> m "create_term_definition 1) defined=%s"
         (String.concat ", " (List.map (fun (s,b) -> Printf.sprintf "%s:%b" s b)
           (SMap.bindings defined))));
      error (Cyclic_iri_mapping defined) (* 1) *)
  | None ->
      match term with
      | "" -> error (Invalid_term_definition term) (* 2) *)
      | _ ->
          let defined = SMap.add term false defined (* 2) *) in
          (* 3) *)
          let value = match J.map_get local_ctx term with
            | None -> `Null
                (*Log.err (fun m -> m "%S not found in local_ctx=%a" term map_pp local_ctx);
                assert false*)
            | Some v -> v.data
          in
          (* 4) *)
          (match term with
           | "@type" when options.processing_mode = "json-ld-1.0" ->
               error (Keyword_redefinition term)
           | "@type" ->
               (match value with
               | `Obj entries ->
                   let b = List.length entries >= 1 && List.for_all
                     (fun (e,v) ->
                        match e.data with
                        | "@container" when v.data = `String "@set" -> true
                        | "@protected" -> true
                        | _ -> false)
                       entries
                   in
                   if not b then error (Keyword_redefinition term)
                | _ ->  error (Keyword_redefinition term)
               )
           | _ when str_is_kw term ->
               error (Keyword_redefinition term)
           | _ -> ()
          );
          if term <> "@type" && str_has_keyword_form term then
            ( (* 5) *)
             Log.warn (fun m -> m "ignoring keyword-like term definition %S" term);
             Lwt.return (active_ctx, defined)
            )
          else
            (
             let active_ctx, prev_def = (* 6) *)
               match SMap.find_opt term active_ctx.defs with
               | None -> active_ctx, None
               | Some d ->
                   Log.debug (fun m -> m "create_term_definition 6) removing previous definiton for %s" term);
                   let defs = SMap.remove term active_ctx.defs in
                   { active_ctx with defs }, Some d
             in
             let value, simple_term = match value with
               | `Null -> [ ranged "@id", J.null ], true (* 7) *)
               | `String str -> [ ranged "@id", J.json value ], true (* 8) *)
               | `Obj map -> map, false
               | json -> error (Invalid_term_definition_value (J.json json))
             in
             let def = { prefix = false ; protected ; reverse_prop = false ;
                 iri = `Null ; base_url = None ; local_ctx = None ;
                 container = None ; direction = None ;
                 index = None ; lang = None ;
                 nest_value = None ; typ = None ;
               }
             in
             let def = (* 11) *)
               match J.map_get value "@protected" with
               | None -> def
               | Some _ when options.processing_mode = "json-ld-1.0" ->
                   error (Invalid_term_definition term)
               | Some { data = `Bool protected } -> { def with protected }
               | Some json -> error (Invalid_protected_value json)
             in
             let%lwt (active_ctx, defined, def) = (* 12) *)
               match J.map_get value "@type" with
               | None -> Lwt.return (active_ctx, defined, def)
               | Some ({ data = `String _ } as type_) ->
                   let%lwt type_mapping =
                     let%lwt (active_ctx,defined,type_) =
                       iri_expansion options ~local_ctx ~defined active_ctx type_
                     in
                     let res =
                       match options.processing_mode with
                       | "json-ld-1.0" when is_kw_json type_ || is_kw_none type_ -> (* 12.3) *)
                           error (Invalid_type_mapping type_)
                       | _ ->
                           match type_.data with
                           | `String "@id" -> `Id
                           | `String "@json" -> `Json
                           | `String "@none" -> `None
                           | `String "@vocab" -> `Vocab
                           | `String iri when str_is_iri iri -> `Iri iri
                           | _ -> error (Invalid_type_mapping type_) (* 12.4) *)
                     in
                     Lwt.return res
                   in
                   Lwt.return (active_ctx, defined, { def with typ = Some type_mapping })
               | Some json -> error (Invalid_type_mapping_value json)
             in
             Log.debug (fun m -> m "create_term_definition after 12) def=%s"
                (J.to_string (json_of_term_def def)));
             let%lwt ret =
               match J.map_get value "@reverse" with
               | None -> Lwt.return None
               | Some ({ data = `String str } as v_reverse) -> (* 13) *)
                   (
                    match J.map_get value "@id", J.map_get value "@nest" with
                    | Some _, _ | _, Some _ ->
                        error Invalid_reverse_property (* 13.1 *)
                    | None, None ->
                        if str_has_keyword_form str then (* 13.3) *)
                          (Log.warn (fun m -> m
                              "Ignoring definition %s as its @reverse is a keyword %S" term str);
                           Lwt.return_some (active_ctx, defined)
                          )
                        else
                          let%lwt (active_ctx, defined, exp) =
                            iri_expansion options ~local_ctx ~defined active_ctx v_reverse
                          in
                          let def = (* 13.4) *)
                            match exp.data with
                            | `String iri when str_is_iri iri -> { def with iri = `Iri iri }
                            | `String id when str_is_blank_node_id id -> { def with iri = `Bnode id }
                            | _ -> error (Invalid_iri_mapping exp)
                          in
                          let def = (* 13.5) *)
                            match J.map_get value "@container" with
                            | None -> def
                            | Some { data = `String str } when str = "@set" || str = "@index" || str = "null" ->
                                { def with container = Some [ str ] }
                            | _ -> error Invalid_reverse_property
                          in
                          let def = { def with reverse_prop = true } (* 13.6) *) in
                          let defs = SMap.add term def active_ctx.defs in
                          let active_ctx = { active_ctx with defs } in
                          let defined = SMap.add term true defined in
                          Lwt.return_some (active_ctx, defined)
                   )
               | Some json -> error (Invalid_iri_mapping json) (* 13.2) *)
             in
             let len_term = Rdf.Utf8.utf8_length term in
             match ret with
             | Some x -> Lwt.return x
             | None ->
                 let%lwt next =
                   match J.map_get value "@id" with
                   | Some v when v.data <> `String term -> (* 14) *)
                       (
                        Log.warn (fun m -> m "create_term_definition: 14) v=%s, term=%S" (J.to_string v) term);
                        match v.data with
                        | `Null -> (* 14.1) *)
                            Log.debug (fun m -> m "create_term_definition 14.1 term=%S def=%s active_ctx=%a"
                               term (J.to_string (json_of_term_def def)) pp_ctx active_ctx);
                            let defs = SMap.add term def active_ctx.defs in
                            let active_ctx = { active_ctx with defs } in
                            Lwt.return (`Return (active_ctx, defined))
                        | `String str ->
                            if not (str_is_kw str) && str_has_keyword_form str then
                              ( (* 14.2.2) *)
                               Log.warn (fun m -> m "Ignoring def %s as its @id is a keyword %S" term str);
                               Lwt.return (`Return (active_ctx, defined))
                              )
                            else
                              (
                               let%lwt (active_ctx, defined, exp) =
                                 iri_expansion options ~local_ctx ~defined active_ctx v
                               in
                               Log.warn (fun m -> m "%s expanded to %s" str (J.to_string exp));
                               let def = (* 14.2.3) *)
                                 let iri = iri_mapping_of_json term exp in
                                 { def with iri }
                               in
                               let%lwt defined = (* 14.2.4) *)
                                 if len_term > 0 &&
                                   (Rdf.Utf8.utf8_contains term "/" ||
                                    (let s = Rdf.Utf8.utf8_substr term 1
                                       (if len_term > 1 then len_term - 2 else len_term - 1)
                                    in
                                     Rdf.Utf8.utf8_contains s ":")
                                   )
                                 then
                                   let defined = SMap.add term true defined in
                                   let%lwt (active_ctx, defined, exp) =
                                     iri_expansion options ~local_ctx ~defined active_ctx (J.string term)
                                   in
                                   let irimap = iri_mapping_of_json term exp in
                                   let same = (* 14.2.4.2) *)
                                     match irimap, def.iri with
                                     | `Iri iri1, `Iri iri2 -> Iri.equal (iri_of_string iri1) (iri_of_string iri2)
                                     | `Bnode id1, `Bnode id2 -> id1 = id2
                                     | `Keyword k1, `Keyword k2 -> k1 = k2
                                     | `Null, `Null -> true
                                     | _  -> false
                                   in
                                   if same then Lwt.return defined
                                   else
                                     error (Invalid_iri_mapping exp)
                                 else
                                   Lwt.return defined
                               in
                               let def = (* 14.2.5) *)
                                 if (not (String.contains term ':')) &&
                                   (not (String.contains term '/')) && simple_term
                                     && match def.iri with
                                     | `Bnode _ -> true
                                     | `Iri s ->
                                         let leni = String.length s in
                                         leni > 0 && (List.mem s.[leni-1] gen_delim_chars)
                                     | _ -> false
                                 then
                                  {def with prefix = true }
                                 else
                                   def
                               in
                               Lwt.return (`Continue (active_ctx, defined, def))
                              )
                        | _ -> error (Invalid_iri_mapping v) (* 14.2.1) *)
                       )
                   | _ when len_term > 0 && String.contains_from term 1 ':' -> (* 15) *)
                       (
                        Log.debug (fun m -> m "create_term_definition 15) term=%S" term);
                        let p = String.index_from term 1 ':' in
                        let prefix = String.sub term 0 p in
                        let%lwt active_ctx, defined =
                          match J.map_get local_ctx prefix with
                          | Some entry when is_compact_iri term -> (* 15.1) *)
                              Log.debug (fun m -> m "create_term_definition 15.1) term=%S prefix=%S" term prefix);
                              create_term_definition options
                              active_ctx local_ctx prefix defined
                          | _ -> Lwt.return (active_ctx, defined)
                        in
                        match SMap.find_opt prefix active_ctx.defs with
                        | Some d -> (* 15.2) *)
                            let suffix = String.sub term (p+1) (len_term - p - 1) in
                            let iri = match d.iri with
                              | `Iri i -> `Iri ( i ^ suffix)
                              | `Keyword kw -> `Keyword (kw ^ suffix) (* ?? *)
                              | `Bnode id -> `Bnode (id ^ suffix)
                              | `Null -> assert false
                            in
                            let def = { def with iri } in
                            Lwt.return (`Continue (active_ctx, defined, def))
                        | None -> (* 15.3) *)
                            let iri =
                              if str_is_iri term then
                                `Iri term
                              else
                                `Bnode term
                            in
                            Lwt.return (`Continue (active_ctx, defined, { def with iri }))
                       )
                   | _ when len_term > 0 && String.contains term '/' -> (* 16) *)
                       (* beware not to pass active_ctx and defined here *)
                       let%lwt (__active_ctx, __defined, exp) =
                         iri_expansion options active_ctx (J.string term)
                       in
                       (match exp.data with (* 16.2) *)
                        | `String i when str_is_iri i ->
                            Lwt.return
                              (`Continue (active_ctx, defined, { def with iri = `Iri i }))
                        | _ ->
                            error (Invalid_iri_mapping exp)
                       )
                   | _ when term = "@type" -> (* 17) *)
                       Lwt.return
                       (`Continue (active_ctx, defined, { def with iri = `Keyword "@type" }))
                   | _ -> (* 18) *)
                       match active_ctx.vocab with
                       | Some iri ->
                           let iri = iri ^ term in
                           Lwt.return
                             (`Continue (active_ctx, defined, { def with iri = `Iri iri }))
                       | None ->
                           let json = J.string term in
                           error (Invalid_iri_mapping json)
                 in
                 match next with
                 | `Return x -> Lwt.return x
                 | `Continue (active_ctx, defined, def) -> (* 19) *)
                     let def =
                       match J.map_get value "@container" with
                       | None -> def
                       | Some json -> (* 19.1 *)
                           let cont = to_container_mapping options json in
                           let def =
                             if List.mem "@type" cont then
                               let def =
                                 match def.typ with
                                 | None -> (* 19.4.1) *) { def with typ = Some `Id }
                                 | _ -> def
                               in
                               match def.typ with (* 19.4.2) *)
                               | None -> assert false
                               | Some (`Id|`Vocab) -> def
                               | _ -> error (Invalid_type_mapping_value json)
                             else
                               def
                           in
                           { def with container = Some cont }
                     in
                     let%lwt (active_ctx, defined, def) = (* 20) *)
                       match J.map_get value "@index", def.container with
                       | None, _ -> Lwt.return (active_ctx, defined, def)
                       | _, None -> (* 20.1) *)
                           error (Invalid_term_definition term)
                       | Some _, Some cont_mapping when options.processing_mode = "json-ld-1.0"
                             || not (List.mem "@index" cont_mapping) -> (* 20.1) *)
                           error (Invalid_term_definition term)
                       | Some ({ data = `String str } as v_index), _ ->
                           let%lwt (active_ctx, defined, exp) =
                             iri_expansion options ~local_ctx ~defined active_ctx v_index
                           in
                           Log.debug (fun m -> m "create_term_definition 20.2 expanded index = %s"
                              (J.to_string exp));
                           (match exp.data with (* 20.2) *)
                            | `String i when str_is_iri i ->
                                (* 20.3) *)
                                Lwt.return
                                  (active_ctx, defined, { def with index = Some str })
                            | _ ->
                                error (Invalid_term_definition_value exp)
                           )
                       | Some json, _ -> error (Invalid_term_definition_value json)
                     in
                     let%lwt def = (* 21) *)
                       match J.map_get value "@context" with
                       | None -> Lwt.return def
                       | Some _ when options.processing_mode = "json-ld-1.0" ->
                           error (Invalid_term_definition term)
                       | Some context ->
                           try%lwt
                             let%lwt _ = process_ctx options
                               ~override_protected:true
                                 ~validate_scoped_ctx:false
                                 active_ctx base_url remote_ctxs context
                             in
                             let base_url = if Iri.to_string base_url = "" then None else Some base_url in
                             Lwt.return { def with local_ctx = Some context ; base_url }
                           with _ -> error Invalid_scoped_context
                     in
                     let def = (* 22) *)
                       match J.map_get value "@language", J.map_get value "@type" with
                       | Some { data = `Null}, None -> { def with lang = Some None }
                       | Some { data = `String str}, None ->
                           if not (Rdf.Lang.is_valid_language_tag str) then
                             warn_invalid_language_tag str ;
                           { def with lang = Some (Some str) }
                       | Some json, None -> error (Invalid_language_mapping json)
                       | _ -> def
                     in
                     let def = (* 23) *)
                       match J.map_get value "@direction", J.map_get value "@type" with
                       | Some {data = `Null}, None -> { def with direction = Some None }
                       | Some {data = `String "ltr"}, None -> { def with direction = Some (Some `Ltr) }
                       | Some {data =`String "rtl"}, None -> { def with direction = Some (Some `Rtl) }
                       | Some json, None -> error (Invalid_base_direction json)
                       | _ -> def
                     in
                     let def = (* 24) *)
                       match J.map_get value "@nest" with
                       | None -> def
                       | Some _ when options.processing_mode = "json-ld-1.0" ->
                           error (Invalid_term_definition term)
                       | Some {data=`String str} when not (str_has_keyword_form str) || str = "@nest" ->
                           { def with nest_value = Some str }
                       | Some json -> error (Invalid_nest_value json)
                     in
                     let def = (* 25) *)
                       match J.map_get value "@prefix" with
                       | None -> def
                       | Some _ when options.processing_mode = "json-ld-1.0" ||
                             (String.contains term ':') ||
                             (String.contains term '/') ->
                           error (Invalid_term_definition term)
                       | Some {data=`Bool b} -> { def with prefix = b }
                       | Some json -> (* 25.2) *) error (Invalid_prefix_value json)
                     in
                     (match def.iri with (* 25.3) *)
                      | `Keyword _ when def.prefix -> error (Invalid_term_definition term)
                      | _ -> ());
                     Log.debug (fun m -> m "create_term_definition 26) value=%a" J.pp (J.obj value));
                     if not (List.for_all (fun (e,_) -> SSet.mem e.data authorized_def_entries) value) then
                       (
                        Log.debug (fun m -> m "unauthorized def entry in %a; authorized entries are %s"
                           J.pp (J.obj value)
                             (String.concat ", " (SSet.elements authorized_def_entries))
                        );
                        error (Invalid_term_definition term); (* 26) *)
                       );
                     Log.warn (fun m -> m "create_term_definition 27) def=%s prev_def=%s override_protected=%b"
                        (J.to_string (json_of_term_def def))
                          (match prev_def with None -> "None" | Some d -> J.to_string (json_of_term_def d))
                          override_protected);
                     let def = (* 27) *)
                       match prev_def with
                       | Some d when d.protected && not override_protected ->
                           if not (def_equal d def) then (* 27.1) *)
                             error (Protected_term_redefinition term)
                           else (* 27.2) *)
                             { def with protected = d.protected }
                       | _ -> def
                     in
                     let defs = SMap.add term def active_ctx.defs in
                     let active_ctx = { active_ctx with defs } in
                     let defined = SMap.add term true defined in
                     Lwt.return (active_ctx, defined)
            )

(* https://www.w3.org/TR/json-ld11-api/#iri-expansion *)
and iri_expansion options ?(document_relative=false) ?(vocab=true)
  ?local_ctx ?(defined=SMap.empty) active_ctx (value:J.json) =
  Log.warn (fun m -> m "iri_expansion ctx=%a value=%a document_relative=%b, vocab=%b local_ctx=%a"
       pp_ctx active_ctx J.pp value document_relative vocab opt_map_pp local_ctx);
  let%lwt result =
    match value.data with
    | `Null -> Lwt.return (active_ctx, defined, value) (* 1) *)
    | _ when is_kw value ->
        Lwt.return (active_ctx, defined, value) (* 1) *)
    | _ when has_keyword_form value ->
        Log.warn (fun m -> m "Json-ld: ignoring keyword-like field %a" J.pp value);
        Lwt.return (active_ctx, defined, J.null) (* 2) *)
    | `Obj _ | `List _ | `Float _ | `Bool _ -> Lwt.return (active_ctx, defined, value) (* 9) *)
    | `String str ->
        let%lwt (active_ctx, defined) = (* 3) *)
          match local_ctx with
          | Some map ->
              (match J.map_get map str, SMap.find_opt str defined with
               | Some _, (None | Some false) ->
                   create_term_definition options active_ctx map str defined
               | _ -> Lwt.return (active_ctx, defined)
              )
          | None -> Lwt.return (active_ctx, defined)
        in
        match
          match SMap.find_opt str active_ctx.defs with
          | Some d ->
              (
               match d.iri with
               | `Keyword x -> Some (J.string x) (* 4) *)
               | (`Iri str | `Bnode str) when vocab -> Some (J.string str) (* 5) *)
               | `Null when vocab -> Some J.null (* 5) *)
               | _ -> None
              )
          | _ -> None
        with
        | Some x -> Lwt.return (active_ctx, defined, x)
        | None ->
            let len = String.length str in
            let%lwt (active_ctx, defined, ret) =
              if len <= 1 then
                Lwt.return (active_ctx, defined, None)
              else
                match String.index_from_opt str 1 ':' with
                | None -> Lwt.return (active_ctx, defined, None)
                | Some p ->
                    let prefix = String.sub str 0 p in
                    let suffix = String.sub str (p+1) (len - p - 1) in
                    if prefix = "_" || Utf8.utf8_is_prefix suffix "//" then
                      Lwt.return (active_ctx, defined, Some value) (* 6.2) *)
                    else
                       let%lwt (active_ctx, defined) =
                          match local_ctx with
                          | Some map ->
                              (match J.map_get map prefix, SMap.find_opt prefix defined with
                               | Some _, (None | Some false) -> (* 6.3) *)
                                   create_term_definition options
                                   active_ctx map prefix defined
                               | _ -> Lwt.return (active_ctx, defined)
                              )
                          | None -> Lwt.return (active_ctx, defined)
                        in
                        match SMap.find_opt prefix active_ctx.defs with
                        | Some d when d.prefix && d.iri <> `Null ->
                            let str = match d.iri with
                              | `Iri i -> i
                              | `Keyword str | `Bnode str -> str
                              | `Null -> assert false
                            in
                            let iri = str ^ suffix in
                            Lwt.return (active_ctx, defined, Some (J.string iri)) (* 6.4) *)
                        | _ ->
                            if str_is_iri str then
                              Lwt.return (active_ctx, defined, Some (J.string str)) (* 6.5) *)
                            else
                              (
                               Log.debug (fun m -> m "iri_expansion not 6.5: str=%S" str);
                               Lwt.return (active_ctx, defined, None)
                              )
            in
            match ret with
            | Some x -> Lwt.return (active_ctx, defined, x)
            | None ->
                Log.debug (fun m -> m "iri_expansion before 7)");
                match active_ctx.vocab with
                | Some iri when vocab ->
                    Log.debug (fun m -> m "iri_expansion 7) active_ctx.vocab=%s" iri);
                    let iri = iri ^ str in
                    Lwt.return (active_ctx, defined, (J.string iri)) (* 7) *)
                | _ ->
                    if document_relative then
                     (
                      Log.warn (fun m -> m "iri_expansion, steps 8/9: active_ctx=%a, str=%S, document_relative=%b"
                                pp_ctx active_ctx str document_relative);
                      match active_ctx.base with
                      | None ->
                          (* case not specified in json-ld spec *)
                          Lwt.return (active_ctx, defined, J.string str)
                      | Some base ->
                                   (* test c021 has "ex:" has vocab and expects "ex:..." as keys
                                      in expanded document, which seems incorrect. To allow this,
                                      by now if str cannot be parsed as a string, we do not resolve
                                      it against base iri and return it as is. *)
                          let iri =
                            match iri_of_string str with
                            | exception e ->
                               Log.warn (fun m -> m "%s: %s" str (Printexc.to_string e));
                               str
                            | iri ->
                               Iri.to_string (iri_resolve ~base iri)
                          in
                          Lwt.return (active_ctx, defined, J.string iri) (* 8) *)
                      )
                    else
                      Lwt.return (active_ctx, defined, J.string str) (* 9) *)
  in
  let (_,_,exp) = result in
  Log.debug (fun m -> m "iri_expansion %a => %a" J.pp value J.pp exp);
  Lwt.return result

(* https://www.w3.org/TR/json-ld11-api/#context-processing-algorithm *)
and process_local_ctx
  options ~override_protected ~propagate ~validate_scoped_ctx
    active_ctx base_url (remote_ctxs, result) ctx =
      match ctx.data with
      | `Null -> (* 5.1) *)
          (
           if not override_protected && SMap.exists
             (fun _ d -> d.protected) active_ctx.defs
           then (* 5.1.1) *)
             error (Invalid_context_nullification ctx.loc) ;
           (* 5.1.2) *)
           let result = { (init_ctx active_ctx.orig_base) with
               prev_ctx = if propagate then None else Some result ;
             }
           in
           (* 5.1.3) *)
           Lwt.return (remote_ctxs, result)
          )
      | `String str -> (* 5.2) *)
          (
           (* 5.2.1) *)
           let iri = iri_resolve ~base:base_url (iri_of_string str) in
           match validate_scoped_ctx, Iri.Map.find_opt iri remote_ctxs with
           | false, Some _ -> (* 5.2.2) *) Lwt.return (remote_ctxs, result)
           | _, remote ->
               (* 5.2.3) and 5.2.4) *)
               let%lwt (remote_ctxs, remote_json) =
                 load_remote_context options remote_ctxs iri
               in
               (* 5.2.5) and 5.2.6) *)
               let%lwt (remote_ctxs, result) = process_ctx_result options
                 (*~override_protected ~propagate*) ~validate_scoped_ctx
                 result iri (remote_ctxs, result)
                   (remote_json : J.json)
               in
               Lwt.return (remote_ctxs, result)
          )

      | `Obj fields ->
          let%lwt (remote_ctxs, result) = process_context_entry options
            ~override_protected active_ctx base_url (remote_ctxs, result) fields
          in
          Lwt.return (remote_ctxs, result)
      | _ -> error (Invalid_local_context ctx.loc)

and process_context_entry options ~override_protected
  active_ctx base_url (remote_ctxs, result) fields(*=context variable in spec*) =
    let is_1_1 =
      match J.map_get fields "@version" with
     | None -> false
     | Some { data = (`String "1.1" | `Float 1.1) } -> true
     | Some json -> (* 5.5.1) *)
         error (Invalid_version json)
    in
    if is_1_1 && options.processing_mode = "json-ld-1.0" then
       (* 5.5.2) *)
       error Processing_mode_conflict;

              let%lwt fields =
                match J.map_get fields "@import" with
                | None -> Lwt.return fields
                | Some _ when options.processing_mode = "json-ld-1.0" -> (* 5.6.1) *)
                      error (Invalid_context_entry "@import")
                | Some { data = `String str } ->
                    let iri = iri_resolve ~base:base_url (iri_of_string str) in
                    (* 5.6.4) to 5.6.6) *)
                    let%lwt (_, remote_json) =
                      load_remote_context options remote_ctxs iri
                    in
                    (match remote_json.data with
                     | `Obj rem_fields ->
                         (match J.map_get rem_fields "@import" with
                          | Some _ -> error (Invalid_context_entry "@import")
                          | None -> ());
                         let pred ({data=entry1},_) ({data=entry2},_) = entry1 = entry2 in
                         let fields = List.fold_left (fun acc e ->
                              match List.find_opt (pred e) acc with
                              | None -> e :: acc
                              | Some _ -> acc
                           ) fields rem_fields
                         in
                         Lwt.return fields
                     | _ -> error (Invalid_remote_context (iri, "not a map"))
                    )
                | Some json -> error (Invalid_import json)
              in
              let result =
                (* 5.7) *)
                match J.map_get fields "@base", Iri.Map.is_empty remote_ctxs with
                | None, _ -> result
                | Some _, false -> result
                | Some value, true ->
                    match value.data with
                    | `Null -> { result with base = None } (* 5.7.2) *)
                    | `String str ->
                        (
                         if is_iri value then
                           let iri = iri_of_string str in
                           { result with base = Some iri } (* 5.7.3) *)
                         else
                           match result.base with
                           | Some base ->
                               (match iri_of_string str with
                                | iri -> { result with base = Some (iri_resolve ~base iri) } (* 5.7.4) *)
                                | exception _ -> error (Invalid_base_iri value)
                               )
                           | _ ->
                               (* See https://github.com/w3c/json-ld-api/issues/533 for a discussion
                                  about accepting "invalid IRIs". We choose here to say that a string
                                  is an IRI or not an IRI, and not have the dubious concept of
                                  "invalid IRI". *)
                               error (Invalid_base_iri value)
                        )
                    | _ -> error (Invalid_base_iri value)

              in
              let%lwt result =
                match J.map_get fields "@vocab" with
                | None -> Lwt.return result
                | Some value ->  (* 5.8) *)
                    match value.data with
                    | `Null -> Lwt.return { result with vocab = None } (* 5.8.2) *)
                    | _ ->
                        (* 5.8.3) *)
                        Log.debug (fun m -> m "process_context_entry 5.8.3) value=%a" J.pp value);
                        (* Spec if incomplete here, and it seems from jsonld.js code that
                           the value has to be expanded in all cases and we check that
                           expanded value is an iri of blank node. *)
                        let%lwt (_,_,expanded) = iri_expansion options
                          ~document_relative:true result value
                        in
                        Log.debug (fun m -> m "process_context_entry 5.8.3) expanded=%a" J.pp expanded);
                        if is_iri expanded || is_blank_node_id expanded then
                          (
                           (* Bnode allowed only in json-ld 1.0 *)
                           match expanded.data with
                           | `String iri -> Lwt.return { result with vocab = Some iri }
                           | _ -> error (Invalid_vocab_mapping (J.to_string value))
                          )
                        else
                          (* not clear: does "it" in "If it is not an IRI, or a blank node
                             identifier, an invalid vocab mapping error has been detected and
                             processing is aborted" refers to str or the result of iri expansion ?
                             Answer: https://github.com/w3c/json-ld-api/issues/567 *)
                          error (Invalid_vocab_mapping (J.to_string value))
              in
              let result =
                match J.map_get fields "@language" with
                | None -> result
                | Some value -> (* 5.9) *)
                    match value.data with
                    | `Null -> (* 5.9.2) *) { result with default_lang = None }
                    | `String str -> (* 5.9.3) *)
                        if not (Rdf.Lang.is_valid_language_tag str) then
                          warn_invalid_language_tag str;
                        { result with default_lang = Some str }
                    | _ -> error (Invalid_default_language value)
              in
              let result =
                match J.map_get fields "@direction" with
                | None -> result
                    (* 5.10) *)
                | Some _ when options.processing_mode = "json-ld-1.0" -> (* 5.10.1) *)
                    error (Invalid_context_entry "@direction")
                | Some value -> (* 5.10.2) *)
                    match value.data with
                    | `Null -> (* 5.10.3) *) { result with default_base_direction = None }
                    | `String "ltr" -> (* 5.10.4) *)
                        { result with default_base_direction = Some `Ltr }
                    | `String "rtl" -> (* 5.10.4) *)
                        { result with default_base_direction = Some `Rtl }
                    | _ ->
                        error (Invalid_base_direction value)
              in
              let () =
                match J.map_get fields "@propagate" with
                | None -> ()
                    (* 5.11) *)
                | Some _ when options.processing_mode = "json-ld-1.0" -> (* 5.11.1) *)
                    error (Invalid_context_entry "@propagate")
                | Some { data = `Bool _ } -> () (* 5.11.2) *)
                | Some json -> error (Invalid_propagate_value json) (* 5.11.2) *)
              in
              (* 5.12) *)
              let defined = SMap.empty in
              let protected = match J.map_get fields "@protected" with
                | Some { data = `Bool b } -> Some b
                | _ -> None
              in
              (* 5.13) *)
              let create_def (active_ctx, defined) (key, _value) =
                match key.data with
                | "@base" | "@direction" | "@import" | "@language"
                | "@propagate" | "@protected" | "@version" | "@vocab" ->
                    Lwt.return (active_ctx, defined)
                | str ->
                    create_term_definition options
                      ?protected ~override_protected
                      ~base_url ~remote_ctxs
                      active_ctx fields str defined
              in
              let%lwt (result, _) = Lwt_list.fold_left_s create_def (result, defined) fields in
              Lwt.return (remote_ctxs, result)

and process_ctx_result options
  ?(override_protected=false) ?(propagate=true)
    ?(validate_scoped_ctx=true)
      active_ctx base_url (remote_ctxs, result) (local_ctx:J.json) =
              let open Json in
              (* 2) *)
              let propagate =
                match local_ctx -?>"@propagate" with
                | None -> propagate
                | Some { data = `Bool b } -> b
                | Some j ->
                    Log.warn (fun m -> m "Invalid @propagate value: %a" J.pp j);
                    propagate
              in
              (* 3) *)
              let result = match result.prev_ctx with
                | None when not propagate -> { result with prev_ctx = Some active_ctx }
                | _ -> result
              in
              (* 4) *)
              let elts = match local_ctx.data with
                | `List l -> l
                | _ -> [local_ctx]
              in
              (* 5) *)
              Lwt_list.fold_left_s (process_local_ctx options
               ~override_protected ~propagate ~validate_scoped_ctx
                 active_ctx base_url)
                (remote_ctxs, result) elts

and process_ctx options
  ?(override_protected=false) ?(propagate=true)
    ?(validate_scoped_ctx=true)
      active_ctx base_url remote_ctxs (local_ctx:J.json) =
              (* 1) *)
              let result = let c = clone_ctx active_ctx in { c with inverse_ctx = None } in
              process_ctx_result options
                ~override_protected ~propagate
                ~validate_scoped_ctx
                active_ctx base_url (remote_ctxs, result) local_ctx

  (* https://www.w3.org/TR/json-ld11-api/#value-expansion *)
let value_expansion options ctx prop value : J.json Lwt.t =
  Log.warn (fun m -> m "value_expansion prop=%S ctx=%a\n, value=%a"
     prop pp_ctx ctx J.pp value);
  match SMap.find_opt prop ctx.defs, value.data with
  | Some { typ = Some `Id }, `String _ -> (* 1) *)
      let%lwt (_,_,v) = iri_expansion options
        ~document_relative:true ~vocab:false ctx value
      in
      let fields = [ ranged "@id", v ] in
      Lwt.return (J.obj fields)
  | Some { typ = Some `Vocab }, `String _ -> (* 2) *)
      let%lwt (_,_,v) = iri_expansion options
        ~document_relative:true ctx value
      in
      let fields = [ ranged "@id", v ] in
      Lwt.return (J.obj fields)
  | d, _ ->
      (* 3) *)
      let result = SMap.singleton "@value" value in
      let result =
        let tv =
          match d with
          | Some { typ = Some tm } ->
              (match tm with
               | `Id | `Vocab | `None -> None
               | `Iri iri -> Some (J.string iri)
               | `Json -> Some (J.string "@json")
              )
          | _ -> None
        in
        match tv with
        | Some v -> (* 4) *)
            Log.debug (fun m -> m "value_expansion 4) @type added: %a" J.pp v);
            SMap.add "@type" v result
        | None -> (* 5) *)
            match value.data with
            | `String str ->
                (* 5.1) *)
                let language = match d with
                  | Some { lang = Some None } -> None
                  | Some { lang = Some (Some lang) } -> Some (J.string lang)
                  | _ -> Option.map J.string ctx.default_lang
                in
                (* 5.2) *)
                let direction = match d with
                  | Some { direction = Some (Some dir) } ->
                      Some (J.string (string_of_direction dir))
                  | Some { direction = Some None } -> None
                  | _ -> Option.map J.string
                      (Option.map string_of_direction ctx.default_base_direction)
                in
                (* 5.3) *)
                let result = match language with
                  | None -> result
                  | Some v -> SMap.add "@language" v result
                in
                (* 5.4) *)
                let result = match direction with
                  | None -> result
                  | Some v -> SMap.add "@direction" v result
                in
                result
            | _ -> result
      in
      Lwt.return (smap_to_json result)

let return_null = Lwt.return J.null


(* 13.7) of https://www.w3.org/TR/json-ld11-api/#expansion-algorithm *)
let expand_language options ~ordered ctx key langmap =
  let direction = (* 13.7.2) and 13.7.3) *)
    match SMap.find_opt key ctx.defs with
    | Some { direction = Some d } -> d
    | _ -> ctx.default_base_direction
  in
  let%lwt l = Lwt_list.fold_left_s (fun exp_value (lang, lang_value) ->
       let lang_value_items = (* 13.7.4.1) *)
         match lang_value.data with
         | `List l -> l
         | _ -> [lang_value]
       in
       Lwt_list.fold_left_s
         (fun exp_value item ->
            match item.data with
            | `Null (* 13.7.4.2.1) *) -> Lwt.return exp_value
            | `String str ->
                (* 13.7.4.2.3) and 13.7.4.2.2)*)
                let value = ranged "@value", item in
                let%lwt language =
                  match lang.data with
                  | "@none" -> (* 13.7.4.2.4) *)
                      Lwt.return []
                  | s -> (* spec is not clear regarding what is meant by
                         "if language expands to @none"; let's expand it using
                         iri expanding *)
                      if not (Rdf.Lang.is_valid_language_tag s) then
                        warn_invalid_language_tag s ;
                      let json_str = J.string ?loc:lang.loc s in
                      let%lwt (_,_,exp) =  iri_expansion options ctx json_str in
                      if is_kw_none exp then
                        Lwt.return []
                      else
                        Lwt.return [ ranged "@language", json_str]
                in
                let fields = value :: language in
                let fields = (* 13.7.4.2.5) *)
                  match direction with
                  | None -> fields
                  | Some dir ->
                      (ranged "@direction",
                       J.string (string_of_direction dir)) :: fields
                in
                let v = J.obj fields in
                Lwt.return (v :: exp_value)
            | _ -> (* 13.7.4.2.2) *) error (Invalid_language_map_value item)
         )
         exp_value lang_value_items
    )
    [] (if ordered then sort_map langmap else langmap)
  in
  Lwt.return (J.list (List.rev l))

    (* 13.8) of https://www.w3.org/TR/json-ld11-api/#expansion-algorithm *)
let rec expand_index_map options ~frame_expansion ~ordered ctx base_url cont_mapping key map =
  Log.warn (fun m -> m "expand_index_map key=%S" key);
  let index_key = (* 13.8.2) *)
    match SMap.find_opt key ctx.defs with
    | Some { index = Some str } -> str
    | _ -> "@index"
  in
  let has_type = List.mem "@type" cont_mapping in
  let has_id = List.mem "@id" cont_mapping in
  let has_index = List.mem "@index" cont_mapping in
  let f exp_value ((index:string ranged), index_value) = (* 13.8.3) *)
    let map_ctx = (* 13.8.3.1) *)
      match ctx.prev_ctx with
      | Some c when has_type || has_index -> c
      | _ -> ctx (* 13.8.3) "otherwise" in 13.8.3.1 is not clear,
             since map context could be used in 13.8.3.2 before being defined.
             *)
    in
    let%lwt map_ctx = (* 13.8.3.2) *)
      match SMap.find_opt index.data map_ctx.defs with
      | Some ({ local_ctx = Some local_ctx } as d) ->
          let index_base_url =
            match d.base_url with
            | Some iri -> iri
            | None -> iri_of_string ""
          in
          let%lwt _, ctx = process_ctx options
            map_ctx index_base_url Iri.Map.empty local_ctx
          in
          Lwt.return ctx
      | _ -> Lwt.return map_ctx
    in
    (* 13.8.3.4) we iri expand using active ctx, but context to use
       is not specified. *)
    let%lwt (_,_,exp_index) = iri_expansion options ctx (J.string index.data) in
    let index_value = (* 13.8.3.5) *) J.to_array index_value in
    let%lwt index_value = (* 13.8.3.6) *)
      expansion options
      ~from_map:true ~ordered ~frame_expansion
        map_ctx (Some key) index_value base_url
    in
    let items = match index_value.data with
      | `List items -> items
      | _ -> assert false
    in
    let f_13_8_3_7 exp_value item =
      let item =  (* 13.8.3.7.1) *)
        if List.mem "@graph" cont_mapping && not (is_graph_object item) then
          (Log.debug (fun m -> m "expansion 13.8.3.7.1 (@@graph)");
           (* "ensuring that the value is represented using an array." is not clear:
              should we test that item is an array or embed item in an array ?? *)
           (* by now, let's put it in an array if it is not an array *)
           J.obj [ ranged "@graph", J.to_array item ]
          )
        else
          item
      in
      (* It seems that item have to be a map, here, though not specified
         in shitty specification *)
      let map =
        match item.data with
        | `Obj map -> map
        | json -> failwith "item not a map, shitty spec does not specify what to do"
      in
      let%lwt item =
        if has_index && index_key <> "@index" &&
          not (is_kw_none exp_index)
        then (* 13.8.3.7.2) *)
          (
           (* 13.8.3.7.2.1) *)
           let%lwt re_exp_index = value_expansion options ctx index_key (J.string index.data) in
           (* 13.8.3.7.2.2) *)
           let%lwt (_,_,exp_index_key) = iri_expansion options ctx (J.string index_key) in
           let exp_index_key = match exp_index_key.data with
             | `String str -> str
             | `Null -> failwith "null expanded key??"
             | _ -> assert false
           in
           (* 13.8.3.7.2.3) *)
           Log.debug (fun m -> m "expansion 13.8.3.7.2.3) re_exp_index=%a, exp_index_key=%s, item=%a"
              J.pp re_exp_index exp_index_key J.pp item);
           let index_prop_values =
             match J.map_get map exp_index_key with
               | None -> J.list [re_exp_index]
               | Some v -> J.list (re_exp_index :: J.values v)
             (* FIXME: spec is not clear, is it ok ? *)
           in
           (* 13.8.3.7.2.4) *)
           let map = map_add_value map exp_index_key index_prop_values in
           let item = { item with data = `Obj map } in
           (* 13.8.3.7.2.5) *)
           if is_value_object item &&
             not (List.for_all (function ({data="@value"},_) -> true | _ ->  false) map)
           then
             error (Invalid_value_object item)
           else
             Lwt.return item
          )
        else
          if has_index &&
            (J.map_get map "@index" = None) &&
              not (is_kw_none exp_index)
          then (* 13.8.3.7.3) *)
            let map = map_add_value map "@index" (J.string ?loc:index.loc index.data) in
            Lwt.return { item with data = `Obj map }
          else if has_id &&
              (J.map_get map "@id" = None) &&
                not (is_kw_none exp_index)
            then (* 13.8.3.7.4) *)
              let%lwt (_,_,exp_index) = iri_expansion options
                ~document_relative:true ~vocab:false ctx (J.string index.data)
              in
              let map = map_add_value map "@id" exp_index in
              Lwt.return { item with data = `Obj map }
            else
              if has_type && not (is_kw_none exp_index) then
                (* 13.8.3.7.5) *)
                let types = match J.map_get map "@type" with
                  | None -> [exp_index]
                  | Some {data = (`List l)} -> exp_index :: l
                  | Some x -> [exp_index ; x]
                in
                let map = map_add_value map "@type" (J.list types) in
                Lwt.return { item with data = `Obj map }
              else
                Lwt.return item
      in
      Lwt.return (item :: exp_value)
    in
    Lwt_list.fold_left_s f_13_8_3_7 exp_value items
  in
  let%lwt l = Lwt_list.fold_left_s f []
    (if ordered then sort_map map else map)
  in
  Lwt.return (J.list (List.rev l))

(* https://www.w3.org/TR/json-ld11-api/#expansion-algorithm *)
and expansion options
  ?(frame_expansion=false) ?(ordered=false) ?(from_map=false)
    ctx prop element base_url =
    Log.warn (fun m -> m "expansion prop=%s ctx=%a element=%a"
       (Option.value ~default:"None" prop) pp_ctx ctx J.ppm element);
    match element.data with
    | `Null -> return_null (* 1) *)
    | json ->
        let frame_expansion, property_scoped_ctx, prop_base_url, cont_map =
          match prop with
          | None -> frame_expansion, None, None, None (* 2) and 3) *)
          | Some prop_str ->
              let frame_expansion =
                match prop_str with
                | "@default" -> false (* 2) *)
                | _ -> frame_expansion
              in
              let property_scoped_ctx, prop_base_url, cont_map = (* 3) *)
                match SMap.find_opt prop_str ctx.defs with
                | None -> None, None, None
                | Some d -> d.local_ctx, d.base_url, d.container
              in
              (frame_expansion, property_scoped_ctx, prop_base_url, cont_map)
        in
        let prop_base_url = match prop_base_url with
          | None -> (fun () -> failwith "no property base url")
          | Some i -> (fun () -> i)
        in
        match json with
        | `Null -> assert false
        | `String _ | `Bool _ | `Float _ -> (* 4) *)
            (match prop with
             | None | Some "@graph" -> (* 4.1) *)
               Log.debug (fun m -> m "expansion: 4.1, return null");
               return_null
             | Some prop ->
                 let%lwt ctx=
                   match property_scoped_ctx with
                   | None -> Lwt.return ctx
                   | Some psctx -> (* 4.2) *)
                       let%lwt _, ctx = process_ctx options ctx (prop_base_url()) Iri.Map.empty psctx in
                       Lwt.return ctx
                 in
                 (* 4.3) *)
                 let%lwt v = value_expansion options ctx prop element in
                 Lwt.return v
            )
        | `List items -> (* 5) *)
            let%lwt items = Lwt_list.fold_right_s
              (fun elt acc ->
                 (* 5.2.1.) *)
                 let%lwt expanded_item = expansion options
                   ~frame_expansion ~ordered ~from_map ctx prop elt base_url
                 in
                 let expanded_item =
                   match cont_map with (* 5.2.2) *)
                   | Some l when List.mem "@list" l ->
                       (match expanded_item.data with
                        | (`List _) -> J.obj [ranged "@list", expanded_item]
                        | _ -> expanded_item
                       )
                   | _ -> expanded_item
                 in
                 (* 5.2.3) *)
                 match expanded_item.data with
                 | `List l -> Lwt.return (l @ acc)
                 | `Null -> Lwt.return acc
                 | _ -> Lwt.return (expanded_item :: acc)
              )
                items []
            in
          let json = J.list items in
          Log.debug (fun m -> m "expansion 5) items=%a" J.pp json);
          Lwt.return json
        | `Obj map -> (* 6) *)
            Log.debug (fun m -> m "expansion, before step 7, ctx=%a" pp_ctx ctx);
            let%lwt ctx = (* 7) *)
              match ctx.prev_ctx with
              | None -> Lwt.return ctx
              | Some prev_ctx ->
                  if not from_map then
                    let%lwt expanded_entries = Lwt_list.fold_left_s
                      (fun acc (key, _) ->
                         let%lwt (_,_,v) =  iri_expansion options ~vocab:true ctx (J.string key.data) in
                         Lwt.return (v :: acc)) [] map
                    in
                    match expanded_entries with
                    | [v] when is_kw_id v -> Lwt.return ctx
                    | l when List.exists is_kw_value l -> Lwt.return ctx
                    | _ -> Lwt.return prev_ctx
                  else
                    Lwt.return ctx
            in
            Log.debug (fun m -> m "expansion, before step 8, ctx=%a" pp_ctx ctx);
            let%lwt ctx = (* 8) *)
              match property_scoped_ctx with
              | None -> Lwt.return ctx
              | Some psctx ->
                  let%lwt _, ctx = process_ctx options ~override_protected:true
                    ctx (prop_base_url()) Iri.Map.empty psctx
                  in
                  Lwt.return ctx
            in
            let%lwt ctx = (* 9) *)
              match J.map_get map "@context" with
              | None -> Lwt.return ctx
              | Some local_ctx ->
                  let%lwt _, ctx = process_ctx options
                    ctx base_url Iri.Map.empty local_ctx
                  in
                  Lwt.return ctx
            in
          Log.debug (fun m -> m "expansion 10) setting type_scoped_ctx = ctx => %a" pp_ctx ctx);
          let type_scoped_ctx = ctx (* 10) *) in
          let%lwt ctx, to_expand = (* 11) *)
            let f (ctx, to_expand) (key, value) =
                let%lwt (_,_,exp) = iri_expansion options ctx (J.string key.data) in
                match exp.data with
                | `String "@type" ->
                  (* 11.1 *)
                  let type_values = List.sort J.compare (J.values value) in
                  let on_term (ctx, to_expand2) term = (* 11.2 *)
                    match term.data with
                    | `String str ->
                        Log.debug (fun m -> m "expansion 11.2) process local ctx for term %s" str);
                        let%lwt ctx =
                          match SMap.find_opt str type_scoped_ctx.defs with
                          | Some { local_ctx = Some lctx } ->
                              (* spec talks about "base URL from the term definition for value in active context,"
                                 but how to get base url from a value ? It seems from
                                 https://github.com/w3c/json-ld-api/issues/304 that type_scoped_ctx must
                                 be used instead of active_ctx *)
                              let base_url = match SMap.find_opt str type_scoped_ctx.defs with
                                | None -> assert false
                                | Some { base_url = Some iri } -> iri
                                | Some { base_url = None } -> (* FIXME: warning ?*)
                                    Log.warn (fun m -> m "expansion, step 11.: no base url in term's de finition");
                                    iri_of_string ""
                              in
                              let%lwt (_, ctx) = process_ctx options ~propagate:false
                                ctx base_url Iri.Map.empty lctx
                              in
                              Lwt.return ctx
                          | _ -> Lwt.return ctx
                        in
                        let to_expand = match to_expand with
                          | Some _ -> to_expand
                          | None -> Some str
                        in
                        Lwt.return (ctx, to_expand)
                    | _ ->
                        (* we can't iri-expand something else than strings; 12) of spec is
                           inconsistent on this point *)
                        Lwt.return (ctx, to_expand2)
                    in
                  Lwt_list.fold_left_s on_term (ctx, to_expand) type_values
              | _ -> Lwt.return (ctx, to_expand)
            in
            Lwt_list.fold_left_s f (ctx, None) (sort_map map)
          in
          Log.debug (fun m -> m "expansion 12) ctx=%a" pp_ctx ctx);
          (* 12) *)
          let%lwt input_type =
            match to_expand with
            | None -> Lwt.return_none
            | Some str ->
                let%lwt (_,_,exp) = iri_expansion options ctx (J.string str) in
                Lwt.return_some exp
          in
          let f_13 (result, nests) (key, value) = (* 13) *)
            Log.debug (fun m -> m "expansion 13) key=%s, value=%a result=%a"
               key.data J.ppm value J.pp (smap_to_json result));
            match key.data with
            | "@context" -> (* 13.1) *) Lwt.return (result, nests)
            | _ ->
                let%lwt (_,_,expanded_prop) = iri_expansion options ctx (J.string key.data) (* 13.2) *) in
                Log.debug (fun m -> m "expansion 13.2) expanded_prop=%a" J.pp expanded_prop);
                match expanded_prop.data with
                | `Null  (* 13.3) *) -> Lwt.return (result, nests)
                | `String str when (not (String.contains str ':')) && not (is_kw expanded_prop) (* 13.3) *)->
                    Log.debug (fun m -> m "expanded 13.3) %S does not contain ':' and is not a keyword" str);
                    Lwt.return (result, nests)
                | _ ->
                    let%lwt next =
                      match expanded_prop.data with
                      | `Null -> assert false
                      | `String kw when str_is_kw kw (* 13.4) *) ->
                          (
                           Log.debug(fun m -> m "expansion 13.4) key is keyword %S" kw);
                           if prop = Some "@reverse" (* 13.4.1) *) then error Invalid_reverse_property_map;
                           if kw <> "@included" && kw <> "@type"
                             && SMap.find_opt kw result <> None (* 13.4.2) *) then
                             error (Colliding_keywords kw);
                           let%lwt next =
                             match kw with
                             | "@id" (* 13.4.3) *) ->
                                 let%lwt v = match value.data with
                                   | `List [] -> Lwt.return value
                                   | `List l when frame_expansion ->
                                       (* 13.4.3.2) *)
                                       let%lwt l = Lwt_list.fold_right_s
                                         (fun v acc ->
                                            match v.data with
                                            | `String str ->
                                                let%lwt (_,_,v) = iri_expansion options
                                                  ~document_relative:true ~vocab:false
                                                    ctx v in
                                                Lwt.return (v :: acc)
                                            | _ -> (* 13.4.3.1) *) error (Invalid_id_value value)
                                           ) l []
                                       in
                                       Lwt.return (J.list l)
                                   | `Obj _ | `Bool _ | `Float _ | `Null | `List _ -> (* 13.4.3.1) *)
                                       error (Invalid_id_value value)
                                   | `String str ->
                                       (* 13.4.3.2) *)
                                       let%lwt (_,_,v) = iri_expansion options
                                         ~document_relative:true ~vocab:false
                                           ctx value in
                                       Lwt.return v
                                 in
                                 Log.debug (fun m -> m "expansion 13.4.3 return %a" J.pp v);
                                 Lwt.return (`V v)
                             | "@type" (* 13.4.4) *)->
                                 let%lwt exp_value =
                                   match value.data with
                                   | `Obj [] when frame_expansion (* 13.4.4.2) *) ->
                                       Lwt.return value
                                   | `Obj l when frame_expansion (* 13.4.4.3) *) ->
                                       (match J.map_get l "@default" with
                                        | Some v when is_iri v ->
                                            let%lwt (_,_,v) = iri_expansion options
                                              ~document_relative:true type_scoped_ctx v
                                            in
                                            let v = J.obj [ranged "@default", v] in
                                            Lwt.return v
                                        | _ -> error (Invalid_type_value value)
                                       )
                                   | `List l ->
                                       (* 13.4.4.4) *)
                                       let%lwt l = Lwt_list.fold_right_s
                                         (fun v acc ->
                                            match v.data with
                                            | `String _ ->
                                                let%lwt (_,_,v) = iri_expansion options
                                                  ~document_relative:true type_scoped_ctx v
                                                in
                                                Lwt.return (v :: acc)
                                            | _ -> (* 13.4.4.1) *) error (Invalid_type_value value)
                                         ) l []
                                       in
                                       Lwt.return (J.list l)
                                   | `String _ ->
                                       (* 13.4.4.4) *)
                                       let%lwt (_,_,v) = iri_expansion options
                                         ~document_relative: true type_scoped_ctx value
                                       in
                                       Lwt.return v
                                   | _ -> (* 13.4.3.1) *) error (Invalid_type_value value)
                                 in
                                 (* 13.4.4.5) *)
                                 let exp_value =
                                   match SMap.find_opt "@type" result, exp_value.data with
                                   | None, _ -> exp_value
                                   | Some ({ data = `String s1 } as v), `String s2 ->
                                       J.list [ v ; exp_value ]
                                   | Some { data = `List l1 }, `String s2 ->
                                       J.list (l1 @ [exp_value])
                                   | Some ({ data = `String s1 } as v), `List l2 ->
                                       J.list (v :: l2)
                                   |  Some { data = `List l1 }, `List l2 ->
                                       J.list (l1 @ l2)
                                   | Some v, _ -> error (Invalid_type_value v)
                                 in
                                 Lwt.return (`V exp_value)
                             | "@graph" (* 13.4.5) *) ->
                                 let%lwt res = expansion options
                                   ~frame_expansion ~ordered
                                     ctx (Some "@graph") value base_url
                                 in
                                 (
                                  Log.debug (fun m -> m "expansion 13.4.5 (@@graph): res=%a" J.pp res);
                                  match res.data with
                                  | `List l when List.for_all
                                      (function { data = `Obj _ } -> true | _ -> false) l ->
                                      Lwt.return (`V res)
                                  | `Obj _ ->
                                      Lwt.return (`V (J.to_array res))
                                  | _ -> error (Expanded_graph_bad_result res)
                                 )
                             | "@included" (* 13.4.6) *) ->
                                 if options.processing_mode = "json-ld-1.0" then
                                   (* 13.4.6.1) *)
                                   Lwt.return (`Next result)
                                 else
                                   (
                                    let%lwt expanded_value = (* 13.4.6.2) *)
                                      expansion options
                                      ~frame_expansion ~ordered ctx None value base_url
                                    in
                                    Log.debug (fun m -> m "expansion 13.4.6) value=%a expanded_value=%a"
                                       J.pp value J.pp expanded_value);
                                    let expanded_value = J.to_array expanded_value in
                                    let values = J.values expanded_value in
                                    (* It seems that expanded value should contain at least
                                       one element, to pass test tin08 *)
                                    if List.length values = 0 ||
                                      not (List.for_all is_node_object values)
                                    then
                                      (* 13.4.6.3) *)
                                      error (Invalid_included_value expanded_value);
                                    let v =
                                      match SMap.find_opt "@included" result with (* 13.4.6.4) *)
                                      | None -> expanded_value
                                      | Some { data = `List lres } -> J.list (lres @ values)
                                      | Some v -> error (Invalid_included_value v)
                                    in
                                    Lwt.return (`V v)
                                   )
                             | "@value" (* 13.4.7) *) ->
                                 let expanded_value =
                                   match input_type with
                                   | Some v when is_kw_json v (* 13.4.7.1) *) -> value
                                   | _ ->
                                       match value.data with (* 13.4.7.3) *)
                                       | `List l when frame_expansion && List.for_all is_scalar l -> value
                                       | `Obj [] when frame_expansion -> J.list [value]
                                       | _ when is_scalar value -> value
                                       | `Null -> value
                                       | _ -> (* 13.4.7.2) *)
                                           error (Invalid_value_object_value value)
                                 in
                                 (
                                  match expanded_value.data with
                                  | `Null (* 13.4.7.4) *) ->
                                      let result = SMap.add "@value" J.null result in
                                      Lwt.return (`Next result)
                                  | _ -> Lwt.return (`V expanded_value)
                                 )
                             | "@language" (* 13.4.8) *) ->
                                 let v = match value.data with (* 13.4.8.{1,2}) *)
                                   | _ when frame_expansion && is_string_array value -> value
                                   | `Obj [] when frame_expansion -> J.list [value]
                                   | `String str ->
                                       if not (Rdf.Lang.is_valid_language_tag str) then
                                         warn_invalid_language_tag str ;
                                       value
                                   | _ -> error (Invalid_language_tagged_string value)
                                 in
                                 Lwt.return (`V v)
                             | "@direction" (* 13.4.9) *) ->
                                 if options.processing_mode = "json-ld-1.0" then (* 13.4.9.1) *)
                                   Lwt.return (`Next result)
                                 else
                                   let v = match value.data with
                                     | `String ("ltr" | "rtl") -> value
                                     | `Obj [] when frame_expansion -> J.list [value]
                                     | _ when frame_expansion && is_string_array value -> value
                                     | _ -> error (Invalid_base_direction value)
                                   in
                                   Lwt.return (`V v)
                             | "@index" (* 13.4.10) *) ->
                                 let v = match value.data with
                                   | `String _ -> value
                                   | _ -> error (Invalid_index_value value)
                                 in
                                 Lwt.return (`V v)
                             | "@list" (* 13.4.11) *) ->
                                 (match prop with
                                  | None | Some "@graph" (* 13.4.11.1) *) ->
                                      Lwt.return (`Next result)
                                  | _ -> (* 13.4.11.2) *)
                                      let%lwt v = expansion options
                                        ~frame_expansion ~ordered ctx prop value base_url
                                      in
                                      Lwt.return (`V (J.to_array v))
                                 )
                             | "@set" (* 13.4.12) *) ->
                                 let%lwt v = expansion options
                                   ~frame_expansion ~ordered ctx prop value base_url
                                 in
                                 Lwt.return (`V v)
                             | "@reverse" (* 13.4.13) *) ->
                                 let%lwt (result, reverse_map) =
                                   match value.data with
                                   | `Obj map ->
                                       (* 13.4.13.2) *)
                                       let%lwt exp_value = expansion options
                                         ~frame_expansion ~ordered ctx (Some "@reverse")
                                           value base_url
                                       in
                                       (
                                        match exp_value.data with
                                        | `Obj exp_map -> (* 13.4.13.3) *)
                                            let result =
                                              match J.map_get exp_map "@reverse" with
                                              | Some { data = `Obj props } ->
                                                  List.fold_left
                                                    (fun res (prop,item) ->
                                                       add_value ~as_array:true res prop.data item)
                                                    result props
                                              | Some { data = `List vals } ->
                                                  (* it seems that @reverse entry in exp_value
                                                     may have as value a list with one object *)
                                                  List.fold_left
                                                    (fun res v ->
                                                       match v.data with
                                                       | `Obj props ->
                                                           List.fold_left
                                                             (fun res (prop,item) ->
                                                                add_value ~as_array:true res prop.data item)
                                                             res props
                                                       | _ ->
                                                           error (Invalid_reverse_value v)
                                                    )
                                                    result vals
                                              | Some v -> error (Invalid_reverse_value v)
                                              | None -> result
                                            in
                                            (* 13.4.13.4) *)
                                            let props = List.filter (fun (k,_) -> k.data <> "@reverse") exp_map in
                                            let rev_map =
                                              match props with
                                              | [] -> SMap.empty
                                              | _ ->
                                                  (* 13.4.13.4.1) *)
                                                  let reverse_map =
                                                    match SMap.find_opt "@reverse" result with
                                                    | None -> SMap.empty
                                                    | Some { data = `Obj m } ->
                                                        List.fold_left (fun acc (k,v) -> SMap.add k.data v acc)
                                                          SMap.empty m
                                                    | Some v -> error (Invalid_reverse_value v)
                                                  in
                                                  (* 13.4.13.4.2) *)
                                                  List.fold_left
                                                    (fun rmap (prop, items) ->
                                                       match items.data with
                                                       | `List items ->
                                                           List.fold_left (fun rmap item ->
                                                              if is_value_object item || is_list_object item then
                                                                (* 13.4.13.4.2.1.1) *)
                                                                error (Invalid_reverse_property_value item);
                                                              (* 13.4.13.4.2.1.2) *)
                                                              add_value ~as_array:true rmap prop.data item
                                                           )
                                                             rmap items
                                                       | _ -> error (Invalid_reverse_property_value items)
                                                    )
                                                    reverse_map props
                                            in
                                            Lwt.return (result, rev_map)
                                        | _ -> error (Invalid_reverse_value exp_value)
                                       )
                                   | _ (* 13.4.13.1) *) -> error (Invalid_reverse_value value)
                                 in
                                 Lwt.return (`Next_with_reverse (result, reverse_map))
                             | "@nest" (* 13.4.14) *) ->
                                 let nests = key.data :: nests in
                                 Lwt.return (`Next_with_nests (result, nests))
                             | "@default" | "@embed" | "@explicit" | "@omitDefault" | "@requireAll"
                                   when frame_expansion -> (* 13.4.15) *)
                                 let%lwt v = expansion options
                                   ~frame_expansion ~ordered ctx prop value base_url
                                 in
                                 Lwt.return (`V v)
                             | _ -> Lwt.return (`V J.null)
                           in
                           let (result, nests) =
                             match next with
                             | `V v -> (* 13.4.16) condition not clear *)
                                 let cond = v.data = `Null && kw = "@value" &&
                                    (match input_type with Some v -> not (is_kw_json v) | _ -> true)
                                 in
                                 Log.debug (fun m -> m "expansion 13.4.16): %ssetting %s entry in result to %a"
                                    (if cond then "NOT" else "") kw J.pp v);
                                 if cond then
                                   (result, nests)
                                 else
                                   let result = SMap.add kw v result in
                                   (result, nests)
                             | `Next result -> (result, nests)
                             | `Next_with_reverse (result, reverse_map) ->
                                 (* badly specified in 13.4.13.4.1): reverse map looks like it is used
                                    as a reference to the @reverse entry in result. So we add reverse_map
                                    to @reverse entry in result here. *)
                                 let o = smap_to_json reverse_map in
                                 let result = SMap.add "@reverse" o result in
                                 (result, nests)
                             | `Next_with_nests (result, nests) -> (result, nests)
                           in
                           Lwt.return (`Next_key (result, nests))
                          )
                      | _ -> Lwt.return `Continue
                    in
                    match next with
                    | `Next_key x -> Lwt.return x
                    | `Continue -> (* 13.5 *)
                        Log.debug(fun m -> m "expansion 13.5 result=%s" (J.to_string (smap_to_json result)) );
                        let container_mapping =
                          match SMap.find_opt key.data ctx.defs with
                          | None -> []
                          | Some { container = None } -> []
                          | Some { container = Some l } -> l
                        in
                        Log.debug (fun m -> m "expansion 13.5) container_mapping=%s"
                           (String.concat ", " container_mapping));
                        let%lwt expanded_value =
                          match SMap.find_opt key.data ctx.defs with
                          | Some { typ = Some `Json } -> (* 13.6) *)
                              let v = J.obj
                                 [ ranged "@value", value ;
                                   ranged "@type", J.string "@json" ;
                                 ]
                              in
                              Lwt.return v
                          | _ ->
                              match value.data with
                              | `Obj langmap when List.mem "@language" container_mapping (* 13.7) *) ->
                                  let%lwt v = expand_language options ~ordered ctx key.data langmap in
                                  Lwt.return v
                              | `Obj map when List.exists
                                    (function "@index" | "@type" | "@id" -> true | _ -> false) container_mapping  ->
                                  (* 13.8) *)
                                  expand_index_map options ~frame_expansion ~ordered
                                    ctx base_url container_mapping key.data map
                              | _ -> (* 13.9) *)
                                  Log.debug (fun m -> m "expansion 13.9) key=%s value=%s" key.data
                                     (J.to_string value));
                                  expansion options
                                  ~frame_expansion ~ordered ctx  (Some key.data) value base_url
                        in
                        match expanded_value.data with
                        | `Null -> (* 13.10) *)
                            Log.debug (fun m -> m "expansion 13.10: return `Null");
                            Lwt.return (result, nests)
                        | _ ->
                            let expanded_value =
                              if List.mem "@list" container_mapping &&
                                not (is_list_object expanded_value)
                              then
                                (* 13.11) *)
                                let a = J.to_array expanded_value in
                                J.obj [ranged "@list", a]
                              else expanded_value
                            in
                            let expanded_value =
                              if List.mem "@graph" container_mapping
                                && not (List.mem "@id" container_mapping)
                                  && not (List.mem "@index" container_mapping)
                              then (* 13.12) *)
                                (
                                 Log.debug (fun m -> m "expansion 13.12) creating graphs");
                                 let l = match expanded_value.data with
                                   | `List l -> l
                                   | _ -> [ expanded_value ]
                                 in
                                 let l = List.map (fun ev ->
                                      J.obj [ranged "@graph", J.to_array ev]) l
                                 in
                                 J.list l
                                )
                              else
                                expanded_value
                            in
                            match expanded_prop.data with
                            | `String eprop ->
                                (match SMap.find_opt key.data ctx.defs with
                                | Some { reverse_prop = true } (* 13.13) *) ->
                                    (
                                     (* 13.13.1) and 13.13.2) *)
                                     let rev_map = match SMap.find_opt "@reverse" result with
                                       | None -> SMap.empty
                                       | Some {data=`Obj l} -> List.fold_left
                                           (fun acc (k, v) -> SMap.add k.data v acc)
                                             SMap.empty l
                                       | Some x -> error (Invalid_reverse_value x)
                                     in
                                     Log.debug (fun m -> m "expansion 13.13 rev_map=%s" (J.to_string (smap_to_json rev_map)));
                                     let expanded_value = (* 13.13.3) *) J.to_array expanded_value in
                                     match expanded_value.data with
                                     | `List items ->
                                         let rev_map = List.fold_left (fun rev_map item ->
                                              Log.debug (fun m -> m "expansion 13.13 item=%s" (J.to_string item));
                                              if is_value_object item || is_list_object item then
                                                (* 13.13.4.1) *)
                                                error (Invalid_reverse_property_value item);
                                              add_value ~as_array:true rev_map eprop item
                                           )
                                           rev_map items
                                         in
                                         let v = smap_to_json rev_map in
                                         Log.debug (fun m -> m "expansion 13.13 @reverse=>%s" (J.to_string v));
                                         let result = SMap.add "@reverse" v result in
                                         Lwt.return (result, nests)
                                     | _ -> assert false
                                    )
                                | _ (* 13.14) *) ->
                                    let result = add_value ~as_array:true
                                      result eprop expanded_value
                                    in
                                    Lwt.return (result, nests)
                                )
                            | _ ->
                                Log.err (fun m -> m "Unexpected expanded prop %s" (J.to_string expanded_prop));
                                assert false
          in
          let rec steps_13_14 result map =
            Log.debug (fun m -> m "steps_13_14 ctx=%a" pp_ctx ctx);
            (* 13) *)
              let%lwt (result, nests) =
              Lwt_list.fold_left_s f_13 (result, [])
                (if ordered then sort_map map else map)
            in
            (* remove @reverse entry in result if it's an empty object *)
            let result =
              match SMap.find_opt "@reverse" result with
              | None -> result
              | Some { data = `Obj [] } -> SMap.remove "@reverse" result
              | _ -> result
            in
            Log.debug (fun m -> m "expansion/steps_13_14 nests=[%s], result=%s, map=%s"
               (String.concat ", " nests)
               (J.to_string (smap_to_json result))
                 (J.to_string (J.obj map))
            );
            (* 14) *)
            let f_nest_key result key =
              (* 14.1) *)
              let nested_values = match J.map_get map key with
                | None -> []
                | Some { data = `List l } -> l
                | Some x -> [x]
              in
              Log.debug (fun m -> m "result=%s key=%s => nested_values = %s"
                 (J.to_string (smap_to_json result))
                  key (J.to_string (J.list nested_values)));
              (* 14.2) *)
              Lwt_list.fold_left_s
                (fun result nested_value ->
                   match nested_value.data with
                   | `Obj nest_map ->
                       (
                        if%lwt Lwt_list.exists_s (fun (key,_) ->
                             let%lwt (_,_,e) = iri_expansion options ctx nested_value in
                             Lwt.return (is_value_object e)) nest_map
                        then (* 14.2.1) *)
                          error (Invalid_nest_value nested_value);
                        (* 14.2.2) *)
                        steps_13_14 result nest_map
                       )
                   | _ (* 14.2.1) nested value not a map *) ->
                       error (Invalid_nest_value nested_value)
                )
                result nested_values
            in
            Lwt_list.fold_left_s f_nest_key
              result
              (if ordered then List.sort String.compare nests else nests)
          in
          let%lwt result = steps_13_14 SMap.empty map in
          (* 15) *)
          Log.debug (fun m -> m "expansion 15) result=%s"
             (J.to_string (smap_to_json result)));
          let result =
            match SMap.find_opt "@value" result with
              | Some v (* 15.1) *) ->
                (if not (SMap.for_all (fun k _ -> match k with
                      | "@direction"| "@index" | "@language" | "@type" | "@value" -> true
                        | _ -> false) result)
                   ||
                     ((SMap.mem "@language" result || SMap.mem "@direction" result)
                      && SMap.mem "@type" result)
                 then
                   error (Invalid_value_object (smap_to_json result));
                 match SMap.find_opt "@type" result with
                 | Some {data=`String "@json"} ->
                     (* 15.2) v is json literal *)
                     Some (smap_to_json result)
                 | vtype ->
                     match v.data with
                     | `Null | `List [] -> (* 15.3) *) None
                     | `Obj _ | `Float _ | `Bool _ when SMap.mem "@language" result ->
                         (* 15.4) *)
                         error (Invalid_language_tagged_value v)
                     | _ -> (* 15.5) *)
                         match vtype with
                         | Some { data = `String str } when str_is_iri str ->
                             Log.debug (fun m -> m "expansion 15.5 str=%S (is_iri)" str);
                             Some (smap_to_json result)
                         | Some vt -> error (Invalid_typed_value vt)
                         | None -> Some (smap_to_json result)
                )
            | None (* 16) *) ->
                match SMap.find_opt "@type" result with
                | Some ({data=(`Obj _|`String _ | `Bool _ | `Float _ | `Null)} as v) ->
                      (* 16) *)
                    Some (smap_to_json (SMap.add "@type" (J.to_array v) result))
                | _ ->
                    if SMap.mem "@set" result || SMap.mem "@list" result then
                      (* 17) *)
                      (
                       if SMap.cardinal result >= 2 && not (SMap.mem "@index" result) then
                         (* 17.1) *)
                         error (Invalid_set_or_list_object (smap_to_json result));
                       match SMap.find_opt "@set" result with
                       | Some v -> (* 17.2) *) Some v
                       | None -> Some (smap_to_json result)
                      )
                    else
                      Some (smap_to_json result)
          in
          match result with
          | None -> return_null
          | Some result ->
              Log.debug (fun m -> m "expansion: result=%s" (J.to_string result));
              match result.data with
              | `Obj map when List.length map = 1 && J.map_get map "@language" <> None ->
                  Log.debug (fun m -> m "expansion 18): return null (result.data is map of length 1 and not @langage)");
                  return_null
              | _ ->
                  let result =
                    match prop with
                    | None | Some "@graph" (* 19) *) ->
                        (match result.data with
                         | `Obj [] ->
                             Log.debug (fun m -> m "expansion 19.1)");
                             J.null (* 19.1) *)
                         | `Obj l when
                               List.exists (function {data=("@value"|"@list")}, _ -> true | _ -> false) l &&
                               (List.for_all (function {data=("@value"|"@list"|"@type"|"@language"|"@index")}, _ -> true | _ -> false) l)
                               -> (* 19.1) fixed according to
                                https://github.com/w3c/json-ld-api/issues/496#issuecomment-1280053987 *)
                             Log.debug (fun m -> m "expansion: 19.1)");
                             J.null
                         | `Obj l when List.length l = 1 && J.map_get l "@id" <> None -> (* 19.2) *)
                             Log.debug (fun m -> m "expansion: 19.2)");
                             if frame_expansion then result else J.null
                         | _ -> result
                        )
                    | _ -> result
                  in
                  (* not clear in spec but it seems that "return null" should return...null, but
                     setting result to null then returning result means that result must be
                     converted to an empty array if it is null.
                     https://github.com/w3c/json-ld-api/issues/175
                     *)
                  match result.data with
                  | `Null -> Lwt.return (J.list [])
                  | _ -> Lwt.return result

                      (* Expansion entry point. According to tests, expansion should always return an array.
                         Spec is not clear about that. It seems that calling expansion should return an
                         array or null, but internal recursive call should return the expanded value.

                         Also from https://github.com/w3c/json-ld-api/issues/175#issuecomment-545164987,
                         someting is not clear regarding @graph. Expand test 0009 seems to indicate that
                         a rsult containing a single @graph entry should be replaced by its content.
                      *)

let expansion options
  ?frame_expansion ?ordered ?from_map ctx prop element base_url =
  let%lwt v = expansion options
    ?frame_expansion ?ordered ?from_map ctx prop element base_url
  in
  match v.data with
  | `Null -> Lwt.return v
  | `Obj map when List.length map = 1 ->
      let v = match J.map_get map "@graph" with
       | None -> v
       | Some v -> v
      in
      Lwt.return (J.to_array v)
  | _ -> Lwt.return (J.to_array v)

let ctx_of_options options base_url =
   let ctx = init_ctx base_url in
   match options.expand_context with
    | None -> Lwt.return ctx
    | Some c ->
      let%lwt json =
        match c with
        | `Json json -> Lwt.return json
        | `Iri iri ->
            Log.info (fun m -> m "option expandContext: %a" Iri.pp iri);
            let%lwt (_, json)= load_remote_context options Iri.Map.empty iri in
            Lwt.return json
      in
      let%lwt (_,ctx) = process_ctx options ctx base_url Iri.Map.empty json in
      Lwt.return ctx