%%           -*-Mode: prolog;-*-

:- multifile rx/2.
:- multifile macro/2.

:- discontiguous macro/2.
:- discontiguous rx/2.

macro(not(X),ext_sigma* - X).
macro($$(X),[ext_sigma*,X,ext_sigma*]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Leftmost/Longest Contexted Replacement %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

macro(replace(T0,Left0,Right), pragma([T-T0,Left-Left0],cleanup(
      non_markers
          o
       m(r(Right))
          o
      f(domain(T))
          o
 left_to_right(domain(T))
          o
 longest_match(domain(T))
          o
    aux_replace(T)
          o
       l1(Left)
          o
       l2(Left)
          o
   inverse(non_markers) ))
     ).

macro(replace(T0), pragma([T-T0], cleanup(
      non_markers
          o
       m(r([]))
          o
      f(domain(T))
          o
 left_to_right(domain(T))
          o
 longest_match(domain(T))
          o
    aux_replace(T)
          o
        l1([])
          o
        l2([])
          o
   inverse(non_markers)))
     ).

%%%%%%%%%%%%%%%%%%%%%%%
%%% Special Symbols %%%
%%%%%%%%%%%%%%%%%%%%%%%

macro(bool,{0,1}).

macro(Marker,[Mrk,1]) :-
    marker_symbol(Marker,Mrk).

marker_symbol(lbrack1,'<1').
marker_symbol(lbrack2,'<2').
marker_symbol(rbrack2,'2>').
marker_symbol(rbrack1,'1>').

macro(lbrack,{lbrack1,lbrack2}).
macro(rbrack,{rbrack1,rbrack2}).
macro(brack1,{lbrack1,rbrack1}).
macro(brack2,{lbrack2,rbrack2}).

macro(brack, {rbrack, lbrack }).

macro(ext_sigma,[?,bool]).
macro(sigma,ext_sigma - brack).

macro(non_markers, [identity(?),[] x 0]*).
macro(non_markers(Expr), 
      range(identity(Expr) o [identity(?),[] x 0]*)).


%%%%%%%%%%%%%
%%% Utils %%%
%%%%%%%%%%%%%

macro(intro_(E2),{ext_sigma,[] x E2}*).
macro(xintro_(E2),{[],[ext_sigma,intro_(E2)]}).
macro(intro_x(E2),{[],[intro_(E2),ext_sigma]}).
macro(xintro_x(E2),{[],[ext_sigma],[ext_sigma,
					    intro_(E2),
					    ext_sigma]}).

macro(ignore_(E1,E2),  range(E1 o intro_(E2))).
macro(xignore_(E1,E2), range(E1 o xintro_(E2))).
macro(ignore_x(E1,E2), range(E1 o intro_x(E2))).
macro(xignore_x(E1,E2),range(E1 o xintro_x(E2))).

%%%%%%%%%%%%%%%%%%%%%%%
%%% Main Procedures %%%
%%%%%%%%%%%%%%%%%%%%%%%

macro(r(R),
   if_right_then_insert_m(rbrack2,non_markers(R))).

%% This diverges from Mohri & Sproat. Here we just insert just lbrack2
%% and not {lbrack1,lbrack2}.
%macro(f(F),
%   if_right_then_insert_m(lbrack2,
%                          [xignore_(non_markers(F),rbrack2),rbrack2])).


macro(intro(S0),pragma([S-S0], {ext_sigma-S,[] x S}*)).

macro(f(F), intro(lbrack2)
               o
       l_iff_r(lbrack2,[[xignore_x(non_markers(F),
					       brack2),
			 lbrack2^]-lbrack2, % Modified from
             rbrack2])).                    % published version

macro(if_p_then_s(L1,L2), 
      not([L1,not(L2)])).
macro(if_s_then_p(L1,L2), 
      not([not(L1),L2])).
macro(p_iff_s(V1,V2), pragma([L1-V1,L2-V2],
      if_p_then_s(L1,L2) 
            & 
      if_s_then_p(L1,L2))).

macro(l_iff_r(L,R), 
   p_iff_s([ext_sigma*,L],[R,ext_sigma*])).



macro(left_to_right(Phi), 
      [[ext_sigma*,
        [lbrack2 x lbrack1,
          (  ignore_(non_markers(Phi),brack2)   %% was ignore_x
                     o 
           [[{sigma,rbrack2}*,
	     lbrack2 x []]*,
	    {sigma,rbrack2}*]
         ),
         rbrack2 x rbrack1]
        ]*,
        ext_sigma*]
     ).

macro(longest_match(Phi0), pragma([Phi-Phi0], 
      not($$([lbrack1,
           (ignore_x(non_markers(Phi),brack)
                        &
           [ignore_(non_markers(Phi),brack),rbrack1,? *]),
           rbrack
          ]))
              o
   [[(ext_sigma - rbrack2)*,
     rbrack2 x []]*,
    (	ext_sigma - rbrack2)*]
     )).

macro(aux_replace(T), 
      {{sigma,lbrack2}, 
       [lbrack1,
        ( inverse(non_markers)
                 o
                 T
                 o
             non_markers
        ),
	rbrack1 x []
       ]
      }*).

macro(l1(L), 
      ignore_(if_m_then_left(lbrack1,non_markers(L)),
		  lbrack2)
                            o
      [[{sigma,lbrack2}*,lbrack1 x []]*,{sigma,lbrack2}*]
     ).

macro(l2(L),
   if_m_then_not_left_delete(lbrack2,non_markers(L))).

%%%%%%%%%%%%%
%%% Tests %%%
%%%%%%%%%%%%%

%% Use this test with the string abababa
macro(test1,replace(([a,b] x x),[a,b],a)).

%% Use this test with the string <1 <2 <1 <2 <1 <2 <1 
macro(test2,replace((['<1','<2'] x '1>'),['<1','<2'],'<1')).

%% Use test string: abbaa
macro(test3,replace(({[a,b],b,[b,a],[a,b],a} x x),{[a,b],b},a)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% User Marker Functions %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% The basic maker functions as defined by Mohri & Sproat are too
%% low level to be easily used directly. The following high-level
%% macros should simplify use in four ways:
%% 
%% 1. The macros provide mnemonic names.
%%
%% 2. The macros are designed to handle markers which are a sequence
%%    of a some special symbol followed by a 1. This allows special
%%    marker symbols to be distinguished from ordinary symbols, which
%%    are followed by 0. So any special marker symbol followed by a 0
%%    will also be interpreted a just another ordinary symbol.
%%
%% 3. The macros encapsulate the need for the tricky use of reverse
%%    embedded inside of reverse in the case of markers sensitive to
%%    right context.
%%
%% 4. For marker2 and marker3, the option is provided of either just
%%    checking the markers or checking and simultaneously deleting the
%%    markers.

macro(if_left_then_insert_m(Marker0,Left),
   marker1( [{[? - Marker,bool],[Marker,0]}*,Left],
            seq(Marker,1))) :-
   marker_symbol(Marker0,Marker).

macro(if_right_then_insert_m(Marker0,Right),
   reverse(
      marker1(reverse([Right,{[? - Marker,bool],[Marker,0]}*]),
              seq(1,Marker)))) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_left(Marker0,Left),
   marker2( [{[? - Marker,bool],[Marker,0]}*,Left],
            seq(Marker,1),
            filter)) :-
   marker_symbol(Marker0,Marker).
       
macro(if_m_then_left_delete(Marker0,Left),
   marker2( [{[? - Marker,bool],[Marker,0]}*,Left],
            seq(Marker,1),
            delete)) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_right(Marker0,Right),
   reverse(
      marker2(reverse([Right,{[? - Marker,bool],[Marker,0]}*]),
              seq(1,Marker),
              filter))) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_right_delete(Marker0,Right),
   reverse(
      marker2(reverse([Right,{[? - Marker,bool],[Marker,0]}*]),
              seq(1,Marker),
              delete))) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_not_left(Marker0,Left),
   marker3( [{[? - Marker,bool],[Marker,0]}*,Left],
            seq(Marker,1),
            filter)) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_not_left_delete(Marker0,Left),
   marker3( [{[? - Marker,bool],[Marker,0]}*,Left],
            seq(Marker,1),
            delete)) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_not_right(Marker0,Right),
   reverse(
      marker2(reverse([Right,{[? - Marker,bool],[Marker,0]}*]),
              seq(1,Marker),
              filter))) :-
   marker_symbol(Marker0,Marker).

macro(if_m_then_not_right_delete(Marker0,Right),
   reverse(
      marker2(reverse([Right,{[? - Marker,bool],[Marker,0]}*]),
              seq(1,Marker),
              delete))) :-
   marker_symbol(Marker0,Marker).

%%%%%%%%%%%%%%
%%% type 1 %%%
%%%%%%%%%%%%%%

%% Type 1 has now been simplified so that it will insert just one kind
%% of marker in the appropriate position. This is no longer sufficient
%% to implement Mohri & Sproat's algorithm, since in their step f,
%% they the markers <1 and <2. 

rx(marker1(Expr,Change),Fa) :-
   fsa_regex:rx(identity(determinize(Expr)),Fa0),
   mark1(Change,Fa0,Fa).

mark1(seq(A0,B0),Fa1,Fa) :-
    fsa_data:fsa_symbols_decl(Fa1,Sigma),
    (	Sigma=r(Module)
    ;   Sigma=t(Module,_)
    ),
    Module:regex_notation_to_predicate(A0,A),
    Module:regex_notation_to_predicate(B0,B),    
    fsa_data:fsa_start_states(Fa1,Starts),
    fsa_data:fsa_transitions(Fa1,Trans0),
    fsa_data:fsa_final_states(Fa1,Finals),
    fsa_data:fsa_states_set(Fa1,AllStates),
    ordsets:ord_subtract(AllStates,Finals,NewFinals0),
    add_insertions(Finals,seq(A,B),NewFinals,NewFinals0,Trans,Trans1),
    replace_transitions_starting_final(Trans0,Trans1,Fa1),
    fsa_data:fsa_construct_rename_states(Sigma,Starts,NewFinals,Trans,[],Fa).

%% this is slow for large automata
%% in such cases it's worthwhile creating a thing for final_states
%% moreover it creates symbolic names first, which are renamed later
%% it would be better to create larger integers for state names here
%% immediately
replace_transitions_starting_final([],[],_).
replace_transitions_starting_final([trans(A0,B,C)|T0],[trans(A,B,C)|T],Fa):-
    (	fsa_data:fsa_final_state(Fa,A0)
    ->	A=q(A0)
    ;	A=A0
    ),
    replace_transitions_starting_final(T0,T,Fa).

add_insertions([],_,F,F) --> [].
add_insertions([F0|Fs],seq(A,B),[q(F0)|NewF0],NewF) -->
    [trans(F0,[]/A,q1(F0)),trans(q1(F0),[]/B,q(F0))],
    add_insertions(Fs,seq(A,B),NewF0,NewF).

%%%%%%%%%%%%%%
%%% type 2 %%%
%%%%%%%%%%%%%%

%% Type 2 and Type 3 are now provided with a flag to determine
%% whether or not the markeer should be deleted after checking.

rx(marker2(Expr,Change,Flag),Fa) :-
    (	Flag == filter
    ->	fsa_regex:rx(determinize(Expr),Fa0)
    ;	fsa_regex:rx(identity(determinize(Expr)),Fa0)
    ),
    mark2(Change,Flag,Fa0,Fa).

mark2(seq(A0,B0),Flag,Fa1,Fa) :-
    fsa_data:fsa_symbols_decl(Fa1,Sigma),
    (	Sigma=r(Module)
    ;   Sigma=t(Module,_)
    ),
    Module:regex_notation_to_predicate(A0,A),
    Module:regex_notation_to_predicate(B0,B),    
    fsa_data:fsa_copy_except(transitions,Fa1,Fa2,Trans0,Trans),
    fsa_data:fsa_copy_except(final_states,Fa2,Fa3,Finals,AllStates),
    fsa_data:fsa_copy_except(states,Fa3,Fa,Num0,Num),
    fsa_data:fsa_states_set(Fa1,AllStates),
    (	Flag == filter
    ->	add_2_filters(Finals,seq(A,B),Num0,Num,Trans1,Trans0)
    ;	add_2_deletions(Finals,seq(A,B),Num0,Num,Trans1,Trans0)
    ),
    sort(Trans1,Trans).

%%%%%%%%%%%%%%
%%% type 3 %%%
%%%%%%%%%%%%%%

rx(marker3(Expr,Change,Flag),Fa) :-
    (	Flag == filter
    ->	fsa_regex:rx(determinize(Expr),Fa0)
    ;	fsa_regex:rx(identity(determinize(Expr)),Fa0)
    ),
    mark3(Change,Flag,Fa0,Fa).

mark3(seq(A0,B0),Flag,Fa1,Fa) :-
    fsa_data:fsa_symbols_decl(Fa1,Sigma),
    (	Sigma=r(Module)
    ;   Sigma=t(Module,_)
    ),
    Module:regex_notation_to_predicate(A0,A),
    Module:regex_notation_to_predicate(B0,B),    
    fsa_data:fsa_copy_except(transitions,Fa1,Fa2,Trans0,Trans),
    fsa_data:fsa_copy_except(final_states,Fa2,Fa3,Finals,AllStates),
    fsa_data:fsa_copy_except(states,Fa3,Fa,Num0,Num),
    fsa_data:fsa_states_set(Fa1,AllStates),
    ordsets:ord_subtract(AllStates,Finals,NonFinals),
    (	Flag == filter
    ->	add_2_filters(NonFinals,seq(A,B),Num0,Num,Trans1,Trans0)
    ;	add_2_deletions(NonFinals,seq(A,B),Num0,Num,Trans1,Trans0)
    ),
    sort(Trans1,Trans).

add_2_filters([],_,Num,Num) --> [].
add_2_filters([Final|Fs],seq(A,B),Num0,Num) -->
    [trans(Final,A,Num0),trans(Num0,B,Final)],
    {user:is(Num1,+(Num0,1))},
    add_2_filters(Fs,seq(A,B),Num1,Num).

add_2_deletions([],_,Num,Num) --> [].
add_2_deletions([Final|Fs],seq(A,B),Num0,Num) -->
    [trans(Final,A/[],Num0),trans(Num0,B/[],Final)],
    {user:is(Num1,+(Num0,1))},
    add_2_deletions(Fs,seq(A,B),Num1,Num).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Longest-Match Concatenate %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

macro(lm_concat(Ts),mark_boundaries(Domains) o ConcatTs) :-
   extract_domains(Ts,Domains),
   concatT(Ts,ConcatTs).

extract_domains([],[]).
extract_domains([F|R0],[domain(F)|R]) :-
   extract_domains(R0,R).

concatT([],[]).
concatT([T|Ts], 
        [inverse(non_markers) o T,mark x []|RestConcat]) :-
   concatT(Ts,RestConcat).

macro(mark,[#,1]).

%% mark_boundaries
%% ---------------
%% This defines the markup transducer. As an example try:
%%
%% mark_boundaries([a1,a2,a3])
%% 
%% Then try out the transducer with the string (set option 'chars' to
%% on first):
%% 
%% topological
%%
%% The result you should get is:
%% 
%% top#o#logical
%%
%% The marker used is the letter "#". The placement of the two #'s
%% indicates that a1 matched against "top", a2 matched against "o"
%% and a3 matched against "logical".

macro(mark_boundaries(L),[Exp,[] x mark]):-
   boundaries(L,Exp0),
   greed(L,Exp0,Exp).

%% boundaries
%% ----------
%% The markup proceeds in a generate-and-test fashion. The
%% "boundaries" macro is a generator, which guesses a markup for the
%% string.

macro(boundaries(L),Exp) :-
   boundaries(L,Exp).

boundaries([H|T],Output) :-
    boundaries(T,H,Output).

boundaries([],F,[F o non_markers]).
boundaries([H|R0],F,[F o non_markers, [] x mark |R]) :-
   boundaries(R0,H,R).

%% greed(ListOfRegexes,Alphabet,Exp2BFiltered,ComposedFilters)
%% -----------------------------------------------------------
%% The ComposedFilters will check a marked-up string of the form
%% x1mx2m...xn, where x1 ... xn are sequences and 'm' is the
%% character 'm' used as a marker. Each x_i is accepted by
%% Regex_i. The filters ensure that, going from left to right through
%% ListOfRegexes, each Regex has applied as greedily as possible in
%% marking up x1 ... xn.
%%
%% As an example, for the goal greed([a1,a2,a3],regex,Result),
%% Result will be bound to:
%%
%%                            regex 
%%
%%                              o 
%%
%%  identity( ~ [ignore_spx(a1,#),ignore_s(a2,#),ignore_s(a3,#)]))
%%
%%                               o 
%%
%% identity( ~ [non_markers(a1),#,ignore_spx(a2,#),ignore_s(a3,#)])) 
%%
%% Filter 1 forces a1 to be as greedy as possible, while Filter 2
%% forces a2 to be as greedy as possible. 

greed(L,Exp2BFiltered,ComposedFilters) :-
   aux_greed(L,[],Filters),
   compose_filters(Filters,Exp2BFiltered,ComposedFilters).

aux_greed([H|T],Front,Filters):-
    aux_greed(T,H,Front,Filters,_CurrentFilter).

aux_greed([],F,_,[],[ignore_(non_markers(F),mark)]).
aux_greed([H|R0],F,Front,[~ L1|R],[ignore_(non_markers(F),mark)|R1]) :-
   lists:append(Front,[ignorex_1(non_markers(F),mark)|R1],L1),
   lists:append(Front,[non_markers(F),mark],NewFront),
   %% R is for the rest of the filters to be constructed
   %% R1 is for the rest of the current filter being constructed
   aux_greed(R0,H,NewFront,R,R1).

%% extension '_1': ignore at least one instance
macro(ignorex_1(E1,E2),
   range(identity(E1) o [[identity(?)*,[] x E2]+,identity(?)+])#).

%% compose_filters(Patterns,Exp2BFiltered,ComposedFilters)
%% ------------------------------------------------------
%% Patterns is a list of patterns to be filtered out by
%% ComposedFilters.

compose_filters([], SoFar, SoFar). %% :- !.
compose_filters([F|R], SoFar, Composed) :-
   compose_filters(R,(SoFar o identity(F)),Composed).

%% (this is an example from Jeffrey Friedl's Mastering Regular
%% Expressions, O'Reilly, 1997, page 177. 
%% the objective being to mimic a `longest match' preference')
%%
%% This was implemented as one part of an algorithm for compiling
%% an extended form of rewrite rules into transducers. See:
%% 
%%     Dale Gerdemann, Gertjan van Noord, "Transducers From Rewrite
%%     Rules with Backreferences" EACL 99.
%%
%% a1, a2, a3
%% ----------
%% This defines the three regexes used in Jeffrey Friedl's example
%% on p. 117. The idea is that the string:
%%   
%%     t o p o l o g i c a l
%%
%% can be partitioned in various ways into x1.x2.x3 such that x1
%% is recognized by a1, x2 by a2 and x3 by a3. The goal is to find 
%% the partitioning that allows a1 to match as long a string as
%% possible, with a2 matching the maximum possible of what's left
%% and so on. 
%% If we simply match "t o p o l o g i c a l" against [a1,a2,a3], we
%% get a yes/no answer, with no clue as to what portion of the string
%% was matched by a1, a2 and a3. So instead what we will do is to use
%% the sequence [a1,a2,a3] to build a transducer which inserts some
%% kind of marker after the portion of the string matched by a1 and
%% a2. Filters are defined to ensure that this transducer will only
%% output the "longest-match" partitioning.

%%%%%%%%%%%%%
%%% Tests %%%
%%%%%%%%%%%%%

macro(a1,minimize({[t,o],[t,o,p]})).
macro(a2,minimize({[o],[p,o,l,o]}^)).
macro(a3,minimize({[g,i,c,a,l],[o^,l,o,g,i,c,a,l]})).

macro(t1,minimize({[t,o] x to,[t,o,p] x top})).
macro(t2,minimize({[] x epsilon, o x o,[p,o,l,o] x polo})).
macro(t3,minimize({[g,i,c,a,l] x gical,
                     [o,l,o,g,i,c,a,l] x ological,
                     [l,o,g,i,c,a,l] x logical})).

macro(test0,lm_concat([t1,t2,t3])).


%% or:
%% fsa -v -aux replace -r 'range(word(topological) o test0)' \
%%           | fsa symbol_separator=32 -p
