<commit_before>%% -*- coding: utf-8 -*-
-module(ds).
-author("<NAME> <<EMAIL>>").

%% `dumpsterl' derives a spec of data based on a stream of values.
%% It can be used to eg. `discover' the data type stored in a table
%% (column, etc.)

-export([ add/2
        , new/0
        , new/1
        , new/2
        , join/2
        , compact/1
        , join_up/1
        ]).

-ifdef(TEST).
-export([ eq/2 ]).
-include_lib("eunit/include/eunit.hrl").
-endif.

%% A data spec is a list of type specs.
%% It is most often hierarchically nested, hence we have
%% a hierarchical tree of type classes.
%% Nodes of this tree are represented as tuples:
%%
%% {Class, Data, SubSpec}
%%
%% - Class is a term (in most cases an atom) describing
%%   the type this node represents in the type hierarchy.
%%   Toplevel type examples: integer, atom, list.
%% - Data is node-specific data as a tuple:
%%
%%   {Stats, Ext}
%%
%%   - Stats is a tuple of general statistics data, eg.:
%%     - an integer count of data items covered by this type class.
%%     - an even sampling of the data values
%%   - Ext is class-specific extra/extended data to hold
%%     further statistics.
%%
%% - SubSpec is a list of child nodes. Depending on the kind of type
%%   denoted by Class, this may be a list of subtypes or in case of
%%   compound types, a list of specs corresponding to the elements
%%   or fields of this type. The exact semantics of SubSpec are left
%%   up to Class, but the tree is uniformly recursive through SubSpecs.

%% Initialize a new data spec
new() -> new(term).

new(Class) ->
    Data = {ds_stats:new(), ds_types:ext_new(Class)},
    {Class, Data, []}.

%% Initialize, immediately adding one data term
new(Class, Data) -> add(Data, new(Class)).

%% Add the value V with attributes A to Spec.
%% add/2 is written so it can be used as a function to lists:foldl/3.
add({V,_A}=VA, {Class, Data, SubSpec}) ->
    add(VA, {Class, Data, SubSpec}, ds_types:subtype(V, Class)).

add(VA, {Class, Data0, SubSpec}, '$null') -> % leaf type
    {Class, update(VA, Class, Data0), SubSpec};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$fields', Fields}) -> % many subtypes
    {Class, update(VA, Class, Data0), merge_fields({Fields, A}, SubSpec)};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$elements', Items}) -> % one subtype
    {Class, update(VA, Class, Data0), merge_items({Items, A}, SubSpec)};
add({_V, A}=VA, {Class, Data0, SubSpec0}, {'$attrs', Dict}) -> % dict of subtypes
    %% The attribute spec is stored in Ext, merge_attrs needs to modify it.
    {Stats, Ext0} = update(VA, Class, Data0),
    {Ext, SubSpec} = merge_attrs({Dict, A}, Ext0, SubSpec0),
    {Class, {Stats, Ext}, SubSpec};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$improper_list', Items, Tail}) ->
    %% one subtype for list items, one for tail
    {Class, update(VA, Class, Data0), merge_improper({Items, Tail, A}, SubSpec)};
add(VA, {Class, Data0, SubSpec}, SubType) -> % abstract type
    {Class, Data0, merge(VA, SubType, SubSpec)}.

update(VA, Class, {Stats, Ext}) ->
    {ds_stats:add(VA, Stats), ds_types:ext_add(VA, Class, Ext)}.

%% choose subspec given by Class or create it from scratch,
%% add V to it and return the resulting Spec.
merge(VA, Class, Spec) ->
    case lists:keyfind(Class, 1, Spec) of
        false   -> [new(Class, VA) | Spec];
        SubSpec -> lists:keystore(Class, 1, Spec, add(VA, SubSpec))
    end.

%% merge the per-field sub-specs of compound types
merge_fields({Vs, A}, []) ->
    lists:map(fun(V) -> new(term, {V, A}) end, Vs);
merge_fields({Vs, A}, SubSpec) ->
    lists:map(fun({V, S}) -> add({V, A}, S) end, lists:zip(Vs, SubSpec)).

%% merge elements of container types into the single inferior spec
merge_items({Vs, A}, []) ->
    [lists:foldl(fun(V, Spec) -> add({V, A}, Spec) end, new(term), Vs)];
merge_items({Vs, A}, [SubSpec]) ->
    [lists:foldl(fun(V, Spec) -> add({V, A}, Spec) end, SubSpec, Vs)].

%% merge a [{Key, Value}] dictionary into a list of sub-specs.
%% Attrs contains a key list [Key] so that if the N-th item of
%% Attrs is Key, then the N-th item of SpecL corresponds to the
%% values associated with Key.
%% Return {Attrs, SpecL} with updated data.
merge_attrs({Dict, A}, Attrs, SpecL) ->
    lists:foldl(fun({K, V}, Acc) -> merge_attr({K, V}, A, Acc) end,
                {Attrs, SpecL}, Dict).

merge_attr({K, V}, A, {Attrs0, SpecL0}) ->
    case ds_utils:index(K, Attrs0) of
        error ->
            Attrs = lists:sort([K|Attrs0]),
            Index = ds_utils:index(K, Attrs),
            {SpecL1, SpecL2} = lists:split(Index-1, SpecL0),
            SpecL = lists:append([SpecL1, [new(term, {V, A})], SpecL2]),
            {Attrs, SpecL};
        Index ->
            {SpecL1, [Spec0|SpecL2]} = lists:split(Index-1, SpecL0),
            Spec = add({V, A}, Spec0),
            SpecL = lists:append([SpecL1, [Spec], SpecL2]),
            {Attrs0, SpecL}
    end.

%% merge spec for improper list
merge_improper(VA, []) ->
    merge_improper(VA, [new(term), new(term)]);
merge_improper({Vs, Vt, A}, [ListSpec0, TailSpec0]) ->
    [ListSpec] = merge_items({Vs, A}, [ListSpec0]),
    TailSpec = add({Vt, A}, TailSpec0),
    [ListSpec, TailSpec].


%% Join two spec trees into one.
%% Depending on class kind, subspec trees are either joined (by class)
%% or zipped (by position).
join({Class, {Stats1, Ext1}, ChildL1},
     {Class, {Stats2, Ext2}, ChildL2}) ->
    ChildL = case ds_types:kind(Class) of
                 generic -> lists:zipwith(fun join/2, ChildL1, ChildL2);
                 _       -> join_specs(ChildL1, ChildL2)
             end,
    {Class,
     {ds_stats:join(Stats1, Stats2), ds_types:ext_join(Class, Ext1, Ext2)},
     ChildL}.

join_specs(Acc, []) -> Acc;
join_specs(Acc0, [{Class,_Data,_ChildL}=Spec | Rest]) ->
    Acc = case lists:keyfind(Class, 1, Acc0) of
              false   -> [Spec | Acc0];
              AccSpec -> lists:keystore(Class, 1, Acc0, join(AccSpec, Spec))
          end,
    join_specs(Acc, Rest).

%% Compact the tree by cutting unnecessary abstract types
%% (those having a single child and no terms captured themselves)
%% from the tree. E.g. if all terms are tuples of three, the tree
%%   term -> tuple -> {tuple, 3} -> ...
%% will be simplified to
%%   {tuple, 3} -> ...
%% without any loss of information.
compact({Class, {Stats,_Ext} = Data, [SubSpec1]}) ->
    Kind = ds_types:kind(Class),
    Count = ds_stats:get_count(Stats),
    if Kind =/= generic andalso Count =:= 0 ->
            compact(SubSpec1);
       true ->
            {Class, Data, [compact(SubSpec1)]}
    end;<commit_msg>Correct spec join for maps<commit_after>%% -*- coding: utf-8 -*-
-module(ds).
-author("<NAME> <<EMAIL>>").

%% `dumpsterl' derives a spec of data based on a stream of values.
%% It can be used to eg. `discover' the data type stored in a table
%% (column, etc.)

-export([ add/2
        , new/0
        , new/1
        , new/2
        , join/2
        , compact/1
        , join_up/1
        ]).

-ifdef(TEST).
-export([ eq/2 ]).
-include_lib("eunit/include/eunit.hrl").
-endif.

%% A data spec is a list of type specs.
%% It is most often hierarchically nested, hence we have
%% a hierarchical tree of type classes.
%% Nodes of this tree are represented as tuples:
%%
%% {Class, Data, SubSpec}
%%
%% - Class is a term (in most cases an atom) describing
%%   the type this node represents in the type hierarchy.
%%   Toplevel type examples: integer, atom, list.
%% - Data is node-specific data as a tuple:
%%
%%   {Stats, Ext}
%%
%%   - Stats is a tuple of general statistics data, eg.:
%%     - an integer count of data items covered by this type class.
%%     - an even sampling of the data values
%%   - Ext is class-specific extra/extended data to hold
%%     further attributes and/or statistics.
%%
%% - SubSpec is a list of child nodes. Depending on the kind of type
%%   denoted by Class, this may be a list of subtypes or in case of
%%   compound types, a list of specs corresponding to the elements
%%   or fields of this type. The exact semantics of SubSpec are left
%%   up to Class, but the tree is uniformly recursive through SubSpecs.

%% Initialize a new data spec
new() -> new(term).

new(Class) ->
    Data = {ds_stats:new(), ds_types:ext_new(Class)},
    {Class, Data, []}.

%% Initialize, immediately adding one data term
new(Class, Data) -> add(Data, new(Class)).

%% Add the value V with attributes A to Spec.
%% add/2 is written so it can be used as a function to lists:foldl/3.
add({V,_A}=VA, {Class, Data, SubSpec}) ->
    add(VA, {Class, Data, SubSpec}, ds_types:subtype(V, Class)).

add(VA, {Class, Data0, SubSpec}, '$null') -> % leaf type
    {Class, update(VA, Class, Data0), SubSpec};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$fields', Fields}) -> % many subtypes
    {Class, update(VA, Class, Data0), merge_fields({Fields, A}, SubSpec)};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$elements', Items}) -> % one subtype
    {Class, update(VA, Class, Data0), merge_items({Items, A}, SubSpec)};
add({_V, A}=VA, {Class, Data0, SubSpec0}, {'$attrs', Dict}) -> % dict of subtypes
    %% The attribute spec is stored in Ext, merge_attrs needs to modify it.
    {Stats, Ext0} = update(VA, Class, Data0),
    {Ext, SubSpec} = merge_attrs({Dict, A}, Ext0, SubSpec0),
    {Class, {Stats, Ext}, SubSpec};
add({_V, A}=VA, {Class, Data0, SubSpec}, {'$improper_list', Items, Tail}) ->
    %% one subtype for list items, one for tail
    {Class, update(VA, Class, Data0), merge_improper({Items, Tail, A}, SubSpec)};
add(VA, {Class, Data0, SubSpec}, SubType) -> % abstract type
    {Class, Data0, merge(VA, SubType, SubSpec)}.

update(VA, Class, {Stats, Ext}) ->
    {ds_stats:add(VA, Stats), ds_types:ext_add(VA, Class, Ext)}.

%% choose subspec given by Class or create it from scratch,
%% add V to it and return the resulting Spec.
merge(VA, Class, Spec) ->
    case lists:keyfind(Class, 1, Spec) of
        false   -> [new(Class, VA) | Spec];
        SubSpec -> lists:keystore(Class, 1, Spec, add(VA, SubSpec))
    end.

%% merge the per-field sub-specs of compound types
merge_fields({Vs, A}, []) ->
    lists:map(fun(V) -> new(term, {V, A}) end, Vs);
merge_fields({Vs, A}, SubSpec) ->
    lists:map(fun({V, S}) -> add({V, A}, S) end, lists:zip(Vs, SubSpec)).

%% merge elements of container types into the single inferior spec
merge_items({Vs, A}, []) ->
    [lists:foldl(fun(V, Spec) -> add({V, A}, Spec) end, new(term), Vs)];
merge_items({Vs, A}, [SubSpec]) ->
    [lists:foldl(fun(V, Spec) -> add({V, A}, Spec) end, SubSpec, Vs)].

%% merge a [{Key, Value}] dictionary into a list of sub-specs.
%% Attrs contains a key list [Key] so that if the N-th item of
%% Attrs is Key, then the N-th item of SpecL corresponds to the
%% values associated with Key.
%% Return {Attrs, SpecL} with updated data.
merge_attrs({Dict, A}, Attrs, SpecL) ->
    lists:foldl(fun({K, V}, Acc) -> merge_attr({K, V}, A, Acc) end,
                {Attrs, SpecL}, Dict).

merge_attr({K, V}, A, {Attrs0, SpecL0}) ->
    case ds_utils:index(K, Attrs0) of
        error ->
            Attrs = lists:sort([K|Attrs0]),
            Index = ds_utils:index(K, Attrs),
            {SpecL1, SpecL2} = lists:split(Index-1, SpecL0),
            SpecL = lists:append([SpecL1, [new(term, {V, A})], SpecL2]),
            {Attrs, SpecL};
        Index ->
            {SpecL1, [Spec0|SpecL2]} = lists:split(Index-1, SpecL0),
            Spec = add({V, A}, Spec0),
            SpecL = lists:append([SpecL1, [Spec], SpecL2]),
            {Attrs0, SpecL}
    end.

%% merge spec for improper list
merge_improper(VA, []) ->
    merge_improper(VA, [new(term), new(term)]);
merge_improper({Vs, Vt, A}, [ListSpec0, TailSpec0]) ->
    [ListSpec] = merge_items({Vs, A}, [ListSpec0]),
    TailSpec = add({Vt, A}, TailSpec0),
    [ListSpec, TailSpec].


%% Join two spec trees into one.
%% This clause is for maps where the children lists are joined
%% based on attributes stored in Ext.
join({map=Class, {Stats1, Ext1}, ChildL1},
         {Class, {Stats2, Ext2}, ChildL2}) ->
    Stats = ds_stats:join(Stats1, Stats2),
    Ext = lists:usort(Ext1 ++ Ext2), % joined attribute list
    AttrDict1 = lists:zip(Ext1, ChildL1),
    AttrDict2 = lists:zip(Ext2, ChildL2),
    ChildL =
        %% For each attribute in joined Ext, look it up in both children
        %% and join appropriately into the result child spec list.
        lists:foldl(
          fun(Attr, Acc) ->
                  case {lists:keyfind(Attr, 1, AttrDict1),
                        lists:keyfind(Attr, 1, AttrDict2)} of
                      { {Attr, Spec1}, {Attr, Spec2} } ->
                          [join(Spec1, Spec2) | Acc];
                      { {Attr, Spec1}, false } ->
                          [Spec1 | Acc];
                      { false, {Attr, Spec2} } ->
                          [Spec2 | Acc]
                  end
          end, [], lists:reverse(Ext)),
    {Class, {Stats, Ext}, ChildL};
%% Subspec (child) trees are joined in a class-specific manner:
%%   - joined by attributes stored in Ext for maps (see above clause);
%%   - zipped (by position) for other generic types;
%%   - joined (by class) for all other types.
join({Class, {Stats1, Ext1}, ChildL1},
     {Class, {Stats2, Ext2}, ChildL2}) ->
    Stats = ds_stats:join(Stats1, Stats2),
    Ext = ds_types:ext_join(Class, Ext1, Ext2),
    ChildL = case ds_types:kind(Class) of
                 generic -> lists:zipwith(fun join/2, ChildL1, ChildL2);
                 _       -> join_specs(ChildL1, ChildL2)
             end,
    {Class, {Stats, Ext}, ChildL}.

join_specs(Acc, []) -> Acc;
join_specs(Acc0, [{Class,_Data,_ChildL}=Spec | Rest]) ->
    Acc = case lists:keyfind(Class, 1, Acc0) of
              false   -> [Spec | Acc0];
              AccSpec -> lists:keystore(Class, 1, Acc0, join(AccSpec, Spec))
          end,
    join_specs(Acc, Rest).

%% Compact the tree by cutting unnecessary abstract types
%% (those having a single child and no terms captured themselves)
%% from the tree. E.g. if all terms are tuples of three, the tree
%%   term -> tuple -> {tuple, 3} -> ...
%% will be simplified to
%%   {tuple, 3} -> ...
%% without any loss of information.
compact({Class, {Stats,_Ext} = Data, [SubSpec1]}) ->
    Kind = ds_types:kind(Class),
    Count = ds_stats:get_count(Stats),
    if Kind =/= generic andalso Count =:= 0 ->
            compact(SubSpec1);
       true ->
            {Class, Data, [compact(SubSpec1)]}
    end;
{'fraction_non_alphanumeric': 0.15857291305853827, 'fraction_numerical': 0.012885348112227225, 'mean_word_length': 2.9757642522721013, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 100, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7001278', 'n_tokens_mistral': 4947, 'n_tokens_neox': 4815, 'n_words': 1629}