defmodule RDF.Canonicalization do
@moduledoc """
An implementation of the standard RDF Dataset Canonicalization Algorithm.
See <https://www.w3.org/TR/rdf-canon/>.
"""
use RDF
alias RDF.Canonicalization.{IdentifierIssuer, State}
alias RDF.{BlankNode, Dataset, Quad, Statement, Utils}
@doc """
Canonicalizes the blank nodes of a graph or dataset according to the RDF Dataset Canonicalization spec.
This function always returns a `RDF.Dataset`. If you want to canonicalize a `RDF.Graph` and
get a `RDF.Graph` back, use `RDF.Graph.canonicalize/1`.
## Example
iex> RDF.Graph.new([{~B<foo>, EX.p(), ~B<bar>}, {~B<bar>, EX.p(), ~B<foo>}])
...> |> RDF.Canonicalization.canonicalize()
RDF.Dataset.new([{~B<c14n0>, EX.p(), ~B<c14n1>}, {~B<c14n1>, EX.p(), ~B<c14n0>}])
"""
@spec canonicalize(RDF.Graph.t() | RDF.Dataset.t()) :: RDF.Dataset.t()
def canonicalize(input) do
urdna2015(input)
end
@doc """
Checks whether two graphs or datasets are equal, regardless of the concrete names of the blank nodes they contain.
## Examples
iex> RDF.Graph.new([{~B<foo>, EX.p(), ~B<bar>}, {~B<bar>, EX.p(), 42}])
...> |> RDF.Canonicalization.isomorphic?(
...> RDF.Graph.new([{~B<b1>, EX.p(), ~B<b2>}, {~B<b2>, EX.p(), 42}]))
true
iex> RDF.Graph.new([{~B<foo>, EX.p(), ~B<bar>}, {~B<bar>, EX.p(), 42}])
...> |> RDF.Canonicalization.isomorphic?(
...> RDF.Graph.new([{~B<b1>, EX.p(), ~B<b2>}, {~B<b3>, EX.p(), 42}]))
false
"""
@spec isomorphic?(RDF.Graph.t() | RDF.Dataset.t(), RDF.Graph.t() | RDF.Dataset.t()) :: boolean
def isomorphic?(a, b) do
a |> canonicalize() |> Dataset.equal?(canonicalize(b))
end
defp urdna2015(input) do
input
|> State.new()
|> create_canonical_identifiers_for_single_node_hashes()
|> create_canonical_identifiers_for_multiple_node_hashes()
|> apply_canonicalization(input)
end
defp create_canonical_identifiers_for_single_node_hashes(state) do
# 3) Calculate hashes for first degree nodes
state =
Enum.reduce(state.bnode_to_quads, state, fn {n, _}, state ->
State.add_bnode_hash(state, n, hash_first_degree_quads(state, n))
end)
# 4) Create canonical replacements for hashes mapping to a single node
state.hash_to_bnodes
# TODO: "Sort in Unicode code point order"
|> Enum.sort()
|> Enum.reduce(state, fn {hash, identifier_list}, state ->
case MapSet.to_list(identifier_list) do
[identifier] ->
state
|> State.issue_canonical_identifier(identifier)
|> State.delete_bnode_hash(hash)
[] ->
raise "unexpected empty identifier list"
_ ->
state
end
end)
end
# 5)
defp create_canonical_identifiers_for_multiple_node_hashes(state) do
state.hash_to_bnodes
|> Enum.sort()
|> Enum.reduce(state, fn {_hash, identifier_list}, state ->
# 5.1-2) Create a hash_path_list for all bnodes using a temporary identifier used to create canonical replacements
identifier_list
|> Enum.reduce([], fn identifier, hash_path_list ->
if IdentifierIssuer.issued?(state.canonical_issuer, identifier) do
hash_path_list
else
{_issued_identifier, temporary_issuer} =
"b"
|> IdentifierIssuer.new()
|> IdentifierIssuer.issue_identifier(identifier)
[
hash_n_degree_quads(state, identifier, temporary_issuer)
| hash_path_list
]
end
end)
|> Enum.sort()
# 5.3) Create canonical replacements for nodes
|> Enum.reduce(state, fn {_hash, issuer}, state ->
issuer
|> IdentifierIssuer.issued_identifiers()
|> Enum.reduce(state, &State.issue_canonical_identifier(&2, &1))
end)
end)
end
# 6)
defp apply_canonicalization(state, data) do
Enum.reduce(data, Dataset.new(), fn statement, canonicalized_data ->
Dataset.add(
canonicalized_data,
if Statement.has_bnode?(statement) do
Statement.map(statement, fn
{_, %BlankNode{} = bnode} ->
state.canonical_issuer
|> IdentifierIssuer.identifier(bnode)
|> BlankNode.new()
{_, node} ->
node
end)
else
statement
end
)
end)
end
# see https://www.w3.org/TR/rdf-canon/#hash-1d-quads
defp hash_first_degree_quads(state, ref_bnode_id) do
state.bnode_to_quads
|> Map.get(ref_bnode_id, [])
|> Enum.map(fn quads ->
quads
|> Quad.new()
|> Statement.map(fn
{_, ^ref_bnode_id} -> ~B<a>
{_, %BlankNode{}} -> ~B<z>
{_, node} -> node
end)
|> RDF.dataset()
|> NQuads.write_string!()
end)
# TODO: "Sort nquads in Unicode code point order"
|> Enum.sort()
|> Enum.join()
|> hash()
# |> IO.inspect(label: "1deg: node: #{inspect(ref_bnode_id)}, hash_first_degree_quads")
end
# see https://www.w3.org/TR/rdf-canon/#hash-related-blank-node
defp hash_related_bnode(state, related, quad, issuer, position) do
input = to_string(position)
input =
if position != :g do
"#{input}<#{Statement.predicate(quad)}>"
else
input
end <>
if identifier =
IdentifierIssuer.identifier(state.canonical_issuer, related) ||
IdentifierIssuer.identifier(issuer, related) do
"_:" <> identifier
else
hash_first_degree_quads(state, related)
end
hash(input)
# |> IO.inspect(label: "hrel: input: #{inspect(input)}, hash_related_bnode")
end
# see https://www.w3.org/TR/rdf-canon/#hash-nd-quads
def hash_n_degree_quads(state, identifier, issuer) do
# IO.inspect(identifier, label: "ndeg: identifier")
# 1-3)
# hash_to_related_bnodes is called now H_n in the new spec
hash_to_related_bnodes =
Enum.reduce(state.bnode_to_quads[identifier], %{}, fn quad, map ->
Map.merge(
map,
hash_related_quad(state, identifier, quad, issuer),
fn _, terms, new -> terms ++ new end
)
end)
# |> IO.inspect(label: "ndeg: hash_to_related_bnodes")
{data_to_hash, issuer} =
hash_to_related_bnodes
# TODO: "Sort in Unicode code point order"
|> Enum.sort()
|> Enum.reduce({"", issuer}, fn
{related_hash, bnode_list}, {data_to_hash, issuer} ->
# 5.1)
data_to_hash = data_to_hash <> related_hash
chosen_path = ""
chosen_issuer = nil
# 5.2-4)
{chosen_path, chosen_issuer} =
bnode_list
|> Utils.permutations()
|> Enum.reduce({chosen_path, chosen_issuer}, fn
permutation, {chosen_path, chosen_issuer} ->
# IO.inspect(permutation, label: "ndeg: perm")
issuer_copy = IdentifierIssuer.copy(issuer)
chosen_path_length = String.length(chosen_path)
# 5.4.4)
{path, recursion_list, issuer_copy} =
Enum.reduce_while(permutation, {"", [], issuer_copy}, fn
related, {path, recursion_list, issuer_copy} ->
{path, recursion_list, issuer_copy} =
if issued_identifier =
IdentifierIssuer.identifier(state.canonical_issuer, related) do
{path <> "_:" <> issued_identifier, recursion_list, issuer_copy}
else
if issued_identifier = IdentifierIssuer.identifier(issuer_copy, related) do
{path <> "_:" <> issued_identifier, recursion_list, issuer_copy}
else
{issued_identifier, issuer_copy} =
IdentifierIssuer.issue_identifier(issuer_copy, related)
{
path <> "_:" <> issued_identifier,
[related | recursion_list],
issuer_copy
}
end
end
# TODO: considering code point order
if chosen_path_length != 0 and
String.length(path) >= chosen_path_length and
path > chosen_path do
{:halt, {path, recursion_list, issuer_copy}}
else
{:cont, {path, recursion_list, issuer_copy}}
end
end)
# IO.puts("ndeg: related_hash: #{related_hash}, path: #{path}, recursion: #{inspect(recursion_list)}")
# 5.4.5)
{issuer_copy, path} =
recursion_list
|> Enum.reverse()
|> Enum.reduce_while({issuer_copy, path}, fn related, {issuer_copy, path} ->
# Note: The following steps seem to be the only steps in the whole algorithm
# which really rely on global state.
# 5.4.5.1)
{result_hash, result_issuer} =
hash_n_degree_quads(state, related, issuer_copy)
# This step was added to circumvent the need for global state.
# It's unclear whether it is actually required, since all test
# of the test suite pass without it.
# see https://github.com/w3c-ccg/rdf-dataset-canonicalization/issues/31
result_issuer =
if result_issuer.id == issuer_copy.id do
{_, issuer} = IdentifierIssuer.issue_identifier(result_issuer, related)
issuer
else
result_issuer
end
# 5.4.5.2)
{issued_identifier, _issuer_copy} =
IdentifierIssuer.issue_identifier(issuer_copy, related)
path = path <> "_:" <> issued_identifier <> "<#{result_hash}>"
# TODO: considering code point order
if chosen_path_length != 0 and
String.length(path) >= chosen_path_length and
path > chosen_path do
{:halt, {result_issuer, path}}
else
{:cont, {result_issuer, path}}
end
end)
# TODO: considering code point order
if chosen_path_length == 0 or path < chosen_path do
{path, issuer_copy}
else
{chosen_path, chosen_issuer}
end
end)
# 5.5)
{data_to_hash <> chosen_path, chosen_issuer}
end)
# IO.puts("ndeg: datatohash: #{data_to_hash}, hash: #{hash(data_to_hash)}")
{hash(data_to_hash), issuer}
end
# 4.8.2.3.1) Group adjacent bnodes by hash
defp hash_related_quad(state, identifier, quad, issuer) do
[
s: Statement.subject(quad),
o: Statement.object(quad),
g: Statement.graph_name(quad)
]
|> Enum.reduce(%{}, fn
{_, ^identifier}, map ->
map
{pos, %BlankNode{} = term}, map ->
hash = hash_related_bnode(state, term, quad, issuer, pos)
Map.update(map, hash, [term], fn terms ->
if term in terms, do: terms, else: [term | terms]
end)
_, map ->
map
end)
end
defp hash(data) do
:crypto.hash(:sha256, data) |> Base.encode16(case: :lower)
end
end
