Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
265 lines (234 sloc) 9.51 KB
%%% Copyright (C) 2006 - 2011 Willem de Jong
%%%
%%% This file is part of Erlsom.
%%%
%%% Erlsom is free software: you can redistribute it and/or modify
%%% it under the terms of the GNU Lesser General Public License as
%%% published by the Free Software Foundation, either version 3 of
%%% the License, or (at your option) any later version.
%%%
%%% Erlsom 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 Lesser General Public License for more details.
%%%
%%% You should have received a copy of the GNU Lesser General Public
%%% License along with Erlsom. If not, see
%%% <http://www.gnu.org/licenses/>.
%%%
%%% Author contact: w.a.de.jong@gmail.com
%%% ====================================================================
%%% A couple of functions used by erlsom_sax (for each encoding variant)
%%% ====================================================================
%%% Version: 20-01-2008
-module(erlsom_sax_lib).
-include("erlsom_sax.hrl").
-export([test/0]).
-export([findCycle/4]).
-export([continueFun/3]).
-export([continueFun/4]).
-export([continueFun2/4]).
-export([continueFun/5]).
-export([continueFun/6]).
-export([continueFun2/6]).
-export([mapStartPrefixMappingCallback/3]).
-export([mapEndPrefixMappingCallback/3]).
-export([createStartTagEvent/3]).
%% there are 4 variants of this function, with different numbers of arguments
%% The names of the first arguments aren't really meaningful, they can
%% be anything - they are only there to be passed to 'ParseFun'.
continueFun(V1, V2, V3, T, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(V1, V2, V3, Tail,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
continueFun2(T, V1, V2, V3, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(Tail, V1, V2, V3,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
continueFun(Prefix, Head, T, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(Prefix, Head, Tail,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
continueFun(Head, T, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(Head, Tail,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
continueFun2(T, Head, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(Tail, Head,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
continueFun(T, State, ParseFun) ->
{Tail, ContinuationState2} =
(State#erlsom_sax_state.continuation_fun)(T, State#erlsom_sax_state.continuation_state),
case Tail of
T -> throw({error, "Malformed: Unexpected end of data"});
_ ->
ParseFun(Tail,
State#erlsom_sax_state{continuation_state = ContinuationState2})
end.
%% function to call the Callback function for all elements in a list of 'new namespaces'.
%% returns State
mapStartPrefixMappingCallback([{Prefix, Uri} | Tail], State, Callback) ->
mapStartPrefixMappingCallback(Tail, Callback({startPrefixMapping, Prefix, Uri}, State), Callback);
mapStartPrefixMappingCallback([], State, _Callback) ->
State.
%% function to call the Callback function for all elements in a list of 'new namespaces'.
%% returns State
mapEndPrefixMappingCallback([{Prefix, _Uri} | Tail], State, Callback) ->
mapEndPrefixMappingCallback(Tail, Callback({endPrefixMapping, Prefix}, State), Callback);
mapEndPrefixMappingCallback([], State, _Callback) ->
State.
%% StartTag = {Prefix, LocalName, QualifiedName}
%% Attributes = list of Attribute
%% Attribute = {{Prefix, LocalName} Value}
%%
%% returns: {Name, Attributes2, NewNamespaces}
%% Name = {URI, LocalName, QualifiedName}
%% Attributes2 = list of Attribute2
%% Attribute2 = #attribute
%% NewNamespaces = list of {Prefix, URI} (prefix can be []).
%%
%% Namespaces are in such an order that namespace of the 'closest ancestors'
%% are in front. That way the right element will be found, even if a prefix is
%% used more than once in the document.
%%
createStartTagEvent(StartTag, Namespaces, Attributes) ->
%% find the namespace definitions in the attributes
{NewNamespaces, OtherAttributes} = lookForNamespaces([], [], Attributes),
AllNamespaces = NewNamespaces ++ Namespaces,
%% add the Uri to the tag name (if applicable)
Name = tagNameTuple(StartTag, AllNamespaces),
%% add the URIs to the attribute names (if applicable)
Attributes2 = attributeNameTuples([], OtherAttributes, AllNamespaces),
{Name, Attributes2, NewNamespaces}.
%% returns {Namespaces, OtherAttributes}, where
%% Namespaces = a list of tuples {Prefix, URI}
%% OtherAttributes = a list of tuples {Name, Value}
%%
lookForNamespaces(Namespaces, OtherAttributes, [Head | Tail]) ->
{{Prefix, LocalName, _QName}, Value} = Head,
if
Prefix == "xmlns" ->
lookForNamespaces([{LocalName, Value} | Namespaces],
OtherAttributes, Tail);
Prefix == [], LocalName == "xmlns" ->
lookForNamespaces([{[], Value} | Namespaces],
OtherAttributes, Tail);
true ->
lookForNamespaces(Namespaces, [Head | OtherAttributes], Tail)
end;
lookForNamespaces(Namespaces, OtherAttributes, []) ->
{Namespaces, OtherAttributes}.
%% StartTag = {Prefix, LocalName, QualifiedName}
%% Namespaces = list of {Prefix, URI} (prefix can be []).
%%
%% Returns {Uri, LocalName, Prefix}
%%
%% TODO: error if not found? special treatment of 'xml:lang'?
tagNameTuple(StartTag, Namespaces) ->
{Prefix, LocalName, _QName} = StartTag,
case lists:keysearch(Prefix, 1, Namespaces) of
{value, {Prefix, Uri}} -> {Uri, LocalName, Prefix};
false -> {[], LocalName, Prefix}
end.
%% Attributes = list of Attribute
%% Attribute = {{Prefix, LocalName} Value}
%% Namespaces = list of {Prefix, URI} (prefix can be []).
%%
%% Returns a list of #attribute records
attributeNameTuples(ProcessedAttributes,
[{AttributeName, Value} | Attributes], Namespaces) ->
{Uri, LocalName, Prefix} = attributeNameTuple(AttributeName, Namespaces),
attributeNameTuples([#attribute{localName= LocalName,
prefix = Prefix,
uri = Uri,
value = Value} | ProcessedAttributes],
Attributes, Namespaces);
attributeNameTuples(ProcessedAttributes, [], _) ->
ProcessedAttributes.
%% AttributeName = {Prefix, LocalName, QualifiedName}
%% Namespaces = list of {Prefix, URI} (prefix can be []).
%%
%% Returns {Uri, LocalName, Prefix}.
%% Difference with TagNameTuple: attributes without prefix do NOT belong
%% to the default namespace.
attributeNameTuple(AttributeName, Namespaces) ->
{Prefix, LocalName, _} = AttributeName,
if
Prefix == [] -> {[], LocalName, LocalName};
true ->
case lists:keysearch(Prefix, 1, Namespaces) of
{value, {Prefix, Uri}} ->
{Uri, LocalName, Prefix};
false ->
case Prefix of
"xml" -> {"http://www.w3.org/XML/1998/namespace", LocalName, Prefix};
_ -> {[], LocalName, Prefix}
end
end
end.
%% simplistic function to find a cycle in a list [{a, b}, {b, c}, ...]
%% or if there is a path longer than MaxDepth.
%% The edge A, B is added; the rest of the graph is known
%% to be acyclical. So we start from B (To) and look for a path
%% to A (Current).
findCycle(To, Current, Edges, MaxDepth) ->
findCycle(To, Current, Edges, MaxDepth, 1).
findCycle(_To, _Current, [], _MaxD, _CurrentD) ->
false;
findCycle(To, Current, Edges, MaxD, CurrentD) ->
%% take the next edge from edge from Current
case lists:keyfind(To, 1, Edges) of
_ when MaxD == CurrentD ->
max_depth; %% reached Max Depth
false ->
false;
{_, Current} ->
cycle; %% found a cycle
{_, B} ->
RemainingEdges = lists:keydelete(To, 1, Edges),
case findCycle(B, Current, RemainingEdges, MaxD, CurrentD + 1) of
false ->
findCycle(To, Current, RemainingEdges, MaxD, CurrentD);
Other ->
Other
end
end.
test() ->
false = findCycle(b, a, [{a, b}], 2),
max_depth = findCycle(b, a, [{a, b}, {b, c}], 2),
false = findCycle(b, a, [{a, b}, {b, c}], 3),
false = findCycle(b, a, [{a, b}, {b, c}, {c, d}, {c, e},
{c, f}, {c, g}, {f, q}, {f, r}, {f, s},
{g, z}], 12),
cycle = findCycle(b, a, [{a, b}, {c, d}, {b, c}, {c, e},
{c, f}, {f, q}, {f, r}, {f, s}, {q, s},
{g, a}, {c, g}], 12),
cycle = findCycle(b, a, [{a, b}, {b, c}, {c, d}, {c, e},
{c, a}, {c, g}, {f, q}, {f, r}, {f, s},
{g, a}], 12).
Jump to Line
Something went wrong with that request. Please try again.