X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Fauto%2Fata.ml;h=f4f11db7a96cc612cca4629eefa01dd4e82c2466;hp=5001ebc2c4505cbba23c154e714c45fa9f5140d7;hb=8026ca9faaa968ced3c2e75ca1d6b55f7270ca50;hpb=30bc0bb1291426e5e26eb2dee1ffc41e4c246349 diff --git a/src/auto/ata.ml b/src/auto/ata.ml index 5001ebc..f4f11db 100644 --- a/src/auto/ata.ml +++ b/src/auto/ata.ml @@ -14,23 +14,29 @@ (***********************************************************************) (* - Time-stamp: + Time-stamp: *) +INCLUDE "utils.ml" open Format open Utils type move = [ `Left | `Right | `Up1 | `Up2 | `Epsilon ] -type state_ctx = { left : StateSet.t; - right : StateSet.t; - up1 : StateSet.t; - up2 : StateSet.t; - epsilon : StateSet.t} -type ctx_ = { mutable positive : state_ctx; - mutable negative : state_ctx } +type state_ctx = { mutable left : StateSet.t; + mutable right : StateSet.t; + mutable up1 : StateSet.t; + mutable up2 : StateSet.t; + mutable epsilon : StateSet.t} + type pred_ = move * bool * State.t +let make_ctx a b c d e = + { left = a; right = b; up1 = c; up2 = d; epsilon = e } + +let print_ctx fmt c = fprintf fmt "{ left : %a; right : %a; up1: %a ; up2 : %a; epsilon : %a }" + StateSet.print c.left StateSet.print c.right StateSet.print c.up1 StateSet.print c.up2 + StateSet.print c.epsilon -module Move : (Formula.PREDICATE with type data = pred_ and type ctx = ctx_ ) = +module Move : (Formula.PREDICATE with type data = pred_ and type ctx = state_ctx ) = struct module Node = @@ -40,15 +46,18 @@ struct let hash n = Hashtbl.hash n end - type ctx = ctx_ - let make_ctx a b c d e = - { left = a; right = b; up1 = c; up2 = d; epsilon = e } + type ctx = state_ctx + include Hcons.Make(Node) + let _pr_buff = Buffer.create 10 + let _str_fmt = formatter_of_buffer _pr_buff + let _flush_str_fmt () = pp_print_flush _str_fmt (); + let s = Buffer.contents _pr_buff in + Buffer.clear _pr_buff; s let print ppf a = - let _ = flush_str_formatter() in - let fmt = str_formatter in + let _ = _flush_str_fmt () in let m, b, s = a.node in let dir,num = @@ -59,26 +68,26 @@ struct | `Up1 -> Pretty.up_arrow, Pretty.subscript 1 | `Up2 -> Pretty.up_arrow, Pretty.subscript 2 in - fprintf fmt "%s%s" dir num; - State.print fmt s; - let str = flush_str_formatter() in + fprintf _str_fmt "%s%s" dir num; + State.print _str_fmt s; + let str = _flush_str_fmt () in if b then fprintf ppf "%s" str else Pretty.pp_overline ppf str let neg p = let l, b, s = p.node in make (l, not b, s) - + exception NegativeAtom of (move*State.t) let eval ctx p = let l, b, s = p.node in - let nctx = if b then ctx.positive else ctx.negative in + if not b then raise (NegativeAtom(l,s)); StateSet.mem s begin match l with - `Left -> nctx.left - | `Right -> nctx.right - | `Up1 -> nctx.up1 - | `Up2 -> nctx.up2 - | `Epsilon -> nctx.epsilon + `Left -> ctx.left + | `Right -> ctx.right + | `Up1 -> ctx.up1 + | `Up2 -> ctx.up2 + | `Epsilon -> ctx.epsilon end end @@ -92,8 +101,6 @@ type t = { transitions: (State.t, (QNameSet.t*SFormula.t) list) Hashtbl.t; } - - let next = Uid.make_maker () let create () = { id = next (); @@ -104,28 +111,54 @@ let create () = { id = next (); transitions = Hashtbl.create 17; } + +let get_trans a states tag = + StateSet.fold (fun q acc0 -> + try + let trs = Hashtbl.find a.transitions q in + List.fold_left (fun acc1 (labs, phi) -> + if QNameSet.mem tag labs then (q,phi)::acc1 else acc1) acc0 trs + with Not_found -> acc0 + ) states [] + +(* + [add_trans a q labels f] adds a transition [(q,labels) -> f] to the + automaton [a] but ensures that transitions remains pairwise disjoint +*) + let add_trans a q s f = let trs = try Hashtbl.find a.transitions q with Not_found -> [] in - let rem, ntrs = - List.fold_left (fun (rem, atrs) ((labs, phi) as tr) -> - let nlabs = QNameSet.inter labs rem in - if QNameSet.is_empty nlabs then - (rem, tr :: atrs) - else - let nrem = QNameSet.diff rem labs in - nrem, (nlabs, SFormula.or_ phi f)::atrs - ) (s, []) trs + let cup, ntrs = + List.fold_left (fun (acup, atrs) (labs, phi) -> + let lab1 = QNameSet.inter labs s in + let lab2 = QNameSet.diff labs s in + let tr1 = + if QNameSet.is_empty lab1 then [] + else [ (lab1, SFormula.or_ phi f) ] + in + let tr2 = + if QNameSet.is_empty lab2 then [] + else [ (lab2, SFormula.or_ phi f) ] + in + (QNameSet.union acup labs, tr1@ tr2 @ atrs) + ) (QNameSet.empty, []) trs in + let rem = QNameSet.diff s cup in let ntrs = if QNameSet.is_empty rem then ntrs else (rem, f) :: ntrs in Hashtbl.replace a.transitions q ntrs +let _pr_buff = Buffer.create 50 +let _str_fmt = formatter_of_buffer _pr_buff +let _flush_str_fmt () = pp_print_flush _str_fmt (); + let s = Buffer.contents _pr_buff in + Buffer.clear _pr_buff; s let print fmt a = fprintf fmt - "Unique ID: %i@\n\ - States %a@\n\ + "\nInternal UID: %i@\n\ + States: %a@\n\ Top states: %a@\n\ Bottom states: %a@\n\ Selection states: %a@\n\ @@ -141,22 +174,117 @@ let print fmt a = a.transitions [] in - let sorted_trs = List.stable_sort (fun (q1, s1, phi1) (q2, s2, phi2) -> + let sorted_trs = List.stable_sort (fun (q1, s1, _) (q2, s2, _) -> let c = State.compare q1 q2 in - (if c == 0 then QNameSet.compare s1 s2 else c)) trs in - let sfmt = str_formatter in - let _ = flush_str_formatter () in - let strs_strings, maxs = List.fold_left (fun (accl, accm) (q, s, f) -> - let s1 = State.print sfmt q; flush_str_formatter () in - let s2 = QNameSet.print sfmt s; flush_str_formatter () in - let s3 = SFormula.print sfmt f; flush_str_formatter () in - ( (s1, s2, s3) :: accl, - max - accm (2 + String.length s1 + String.length s2)) - ) ([], 0) sorted_trs + let _ = _flush_str_fmt () in + let strs_strings, max_pre, max_all = List.fold_left (fun (accl, accp, acca) (q, s, f) -> + let s1 = State.print _str_fmt q; _flush_str_fmt () in + let s2 = QNameSet.print _str_fmt s; _flush_str_fmt () in + let s3 = SFormula.print _str_fmt f; _flush_str_fmt () in + let pre = Pretty.length s1 + Pretty.length s2 in + let all = Pretty.length s3 in + ( (q, s1, s2, s3) :: accl, max accp pre, max acca all) + ) ([], 0, 0) sorted_trs in - List.iter (fun (s1, s2, s3) -> - fprintf fmt "%s, %s" s1 s2; - fprintf fmt "%s" (Pretty.padding (maxs - String.length s1 - String.length s2 - 2)); - fprintf fmt "%s %s@\n" Pretty.right_arrow s3) strs_strings + let line = Pretty.line (max_all + max_pre + 6) in + let prev_q = ref State.dummy in + List.iter (fun (q, s1, s2, s3) -> + if !prev_q != q && !prev_q != State.dummy then fprintf fmt " %s\n%!" line; + prev_q := q; + fprintf fmt " %s, %s" s1 s2; + fprintf fmt "%s" (Pretty.padding (max_pre - Pretty.length s1 - Pretty.length s2)); + fprintf fmt " %s %s@\n%!" Pretty.right_arrow s3; + ) strs_strings; + fprintf fmt " %s\n%!" line + +(* + [complete transitions a] ensures that for each state q + and each symbols s in the alphabet, a transition q, s exists. + (adding q, s -> F when necessary). +*) + +let complete_transitions a = + StateSet.iter (fun q -> + let qtrans = Hashtbl.find a.transitions q in + let rem = + List.fold_left (fun rem (labels, _) -> + QNameSet.diff rem labels) QNameSet.any qtrans + in + let nqtrans = + if QNameSet.is_empty rem then qtrans + else + (rem, SFormula.false_) :: qtrans + in + Hashtbl.replace a.transitions q nqtrans + ) a.states + +(* [normalize_negations a] removes negative atoms in the formula + complementing the sub-automaton in the negative states. + [TODO check the meaning of negative upward arrows] +*) +let normalize_negations auto = + let memo_state = Hashtbl.create 17 in + let todo = Queue.create () in + let rec flip b f = + match SFormula.expr f with + Formula.True | Formula.False -> if b then f else SFormula.not_ f + | Formula.Or(f1, f2) -> (if b then SFormula.or_ else SFormula.and_)(flip b f1) (flip b f2) + | Formula.And(f1, f2) -> (if b then SFormula.and_ else SFormula.or_)(flip b f1) (flip b f2) + | Formula.Atom(a) -> begin + let l, b', q = Move.node a in + if b == b' then begin + (* a appears positively, either no negation or double negation *) + if not (Hashtbl.mem memo_state (q,b)) then Queue.add (q,true) todo; + SFormula.atom_ (Move.make (l, true, q)) + end else begin + (* need to reverse the atom + either we have a positive state deep below a negation + or we have a negative state in a positive formula + b' = sign of the state + b = sign of the enclosing formula + *) + let not_q = + try + (* does the inverted state of q exist ? *) + Hashtbl.find memo_state (q, false) + with + Not_found -> + (* create a new state and add it to the todo queue *) + let nq = State.make () in + if not (StateSet.mem q auto.bottom_states) then + auto.bottom_states <- StateSet.add nq auto.bottom_states; + if not (StateSet.mem q auto.top_states) then + auto.top_states <- StateSet.add nq auto.top_states; + Hashtbl.add memo_state (q, false) nq; + Queue.add (q, false) todo; nq + in + SFormula.atom_ (Move.make (l, true, not_q)) + end + end + in + (* states that are not reachable from a selection stat are not interesting *) + StateSet.iter (fun q -> Queue.add (q, true) todo) auto.selection_states; + + while not (Queue.is_empty todo) do + let (q, b) as key = Queue.pop todo in + let q' = + try + Hashtbl.find memo_state key + with + Not_found -> + let nq = if b then q else + let nq = State.make () in + if not (StateSet.mem q auto.bottom_states) then + auto.bottom_states <- StateSet.add nq auto.bottom_states; + if not (StateSet.mem q auto.top_states) then + auto.top_states <- StateSet.add nq auto.top_states; + nq + in + Hashtbl.add memo_state key nq; nq + in + let trans = Hashtbl.find auto.transitions q in + let trans' = List.map (fun (lab, f) -> lab, flip b f) trans in + Hashtbl.replace auto.transitions q' trans' + done