1 (* Copyright (C) 2000, HELM Team.
3 * This file is part of HELM, an Hypertextual, Electronic
4 * Library of Mathematics, developed at the Computer Science
5 * Department, University of Bologna, Italy.
7 * HELM is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
12 * HELM is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with HELM; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
26 (*****************************************************************************)
30 (* Enrico Tassi <tassi@cs.unibo.it> *)
33 (* This module implements the aciclic graph of universes. *)
35 (*****************************************************************************)
37 (*****************************************************************************)
38 (** switch implementation **)
39 (*****************************************************************************)
41 let fast_implementation = ref false ;;
43 (*****************************************************************************)
45 (*****************************************************************************)
49 (*****************************************************************************)
50 (** Types and default values **)
51 (*****************************************************************************)
53 type universe = int * UriManager.uri option
55 module UniverseType = struct
57 let compare = Pervasives.compare
60 module SOF = Set.Make(UniverseType)
72 module MAL = Map.Make(UniverseType)
74 type arc_type = GE | GT | EQ
76 type bag = entry MAL.t
87 let empty_bag = MAL.empty
89 let are_set_eq s1 s2 =
92 let are_entry_eq v1 v2 =
93 (are_set_eq v1.gt_closure v2.gt_closure ) &&
94 (are_set_eq v1.ge_closure v2.ge_closure ) &&
95 (are_set_eq v1.eq_closure v2.eq_closure ) &&
96 (*(are_set_eq v1.in_gegt_of v2.in_gegt_of ) &&*)
97 (are_set_eq v1.one_s_ge v2.one_s_ge ) &&
98 (are_set_eq v1.one_s_gt v2.one_s_gt ) &&
99 (are_set_eq v1.one_s_eq v2.one_s_eq )
101 let are_ugraph_eq = MAL.equal are_entry_eq
103 (*****************************************************************************)
104 (** Pretty printings **)
105 (*****************************************************************************)
107 let string_of_universe (i,u) =
110 "(" ^ ((string_of_int i) ^ "," ^ (UriManager.string_of_uri u) ^ ")")
111 | None -> "(" ^ (string_of_int i) ^ ",None)"
113 let string_of_universe_set l =
114 SOF.fold (fun x s -> s ^ (string_of_universe x) ^ " ") l ""
116 let string_of_node n =
118 "eq_c: " ^ (string_of_universe_set n.eq_closure) ^ "; " ^
119 "ge_c: " ^ (string_of_universe_set n.ge_closure) ^ "; " ^
120 "gt_c: " ^ (string_of_universe_set n.gt_closure) ^ "; " ^
121 "i_gegt: " ^ (string_of_universe_set n.in_gegt_of) ^ "}\n"
123 let string_of_arc (a,u,v) =
124 (string_of_universe u) ^ " " ^ a ^ " " ^ (string_of_universe v)
126 let string_of_mal m =
129 rc := !rc ^ sprintf "%s --> %s" (string_of_universe k)
130 (string_of_node v)) m;
133 let string_of_bag b =
136 (*****************************************************************************)
138 (*****************************************************************************)
145 Not_found -> empty_entry
147 (* FIXME: May be faster if we make it by hand *)
148 let merge_closures f nodes m =
149 SOF.fold (fun x i -> SOF.union (f (repr x m)) i ) nodes SOF.empty
151 (*****************************************************************************)
153 (*****************************************************************************)
154 let time_spent = ref 0.0;;
155 let partial = ref 0.0 ;;
157 let reset_spent_time () = time_spent := 0.0;;
158 let get_spent_time () = !time_spent ;;
159 let begin_spending () =
160 (*assert (!partial = 0.0);*)
161 partial := Unix.gettimeofday ()
164 let end_spending () =
165 assert (!partial > 0.0);
166 let interval = (Unix.gettimeofday ()) -. !partial in
168 time_spent := !time_spent +. interval
172 (*****************************************************************************)
173 (** _fats implementation **)
174 (*****************************************************************************)
176 let rec closure_of_fast ru m =
177 let eq_c = closure_eq_fast ru m in
178 let ge_c = closure_ge_fast ru m in
179 let gt_c = closure_gt_fast ru m in
184 in_gegt_of = ru.in_gegt_of;
185 one_s_eq = ru.one_s_eq;
186 one_s_ge = ru.one_s_ge;
187 one_s_gt = ru.one_s_gt
190 and closure_eq_fast ru m =
192 let j = ru.one_s_eq in
193 let _Uj = merge_closures (fun x -> x.eq_closure) j m in
194 let one_step_eq = ru.one_s_eq in
195 (SOF.union one_step_eq _Uj)
199 and closure_ge_fast ru m =
201 let j = SOF.union ru.one_s_ge (SOF.union ru.one_s_gt ru.one_s_eq) in
202 let _Uj = merge_closures (fun x -> x.ge_closure) j m in
208 and closure_gt_fast ru m =
210 let j = ru.one_s_gt in
211 let k = ru.one_s_ge in
212 let l = ru.one_s_eq in
213 let _Uj = merge_closures (fun x -> x.ge_closure) j m in
214 let _Uk = merge_closures (fun x -> x.gt_closure) k m in
215 let _Ul = merge_closures (fun x -> x.gt_closure) l m in
216 let one_step_gt = ru.one_s_gt in
217 (SOF.union (SOF.union (SOF.union _Ul one_step_gt) _Uk) _Uj)
221 and print_rec_status u ru =
222 print_endline ("Aggiusto " ^ (string_of_universe u) ^
223 "e ottengo questa chiusura\n " ^ (string_of_node ru))
225 and adjust_fast u m =
227 let gt_c = closure_gt_fast ru m in
228 let ge_c = closure_ge_fast ru m in
229 let eq_c = closure_eq_fast ru m in
230 let changed_eq = not (are_set_eq eq_c ru.eq_closure) in
232 (not (are_set_eq gt_c ru.gt_closure)) ||
233 (not (are_set_eq ge_c ru.ge_closure))
235 if ((not changed_gegt) && (not changed_eq)) then
243 in_gegt_of = ru.in_gegt_of;
244 one_s_eq = ru.one_s_eq;
245 one_s_ge = ru.one_s_ge;
246 one_s_gt = ru.one_s_gt}
248 let m = MAL.add u ru' m in
250 SOF.fold (fun x m -> adjust_fast x m)
251 (SOF.union ru'.eq_closure ru'.in_gegt_of) m
256 m (*adjust_fast u m*)
259 and add_gt_arc_fast u v m =
261 let ru' = {ru with one_s_gt = SOF.add v ru.one_s_gt} in
262 let m' = MAL.add u ru' m in
263 let rv = repr v m' in
264 let rv' = {rv with in_gegt_of = SOF.add u rv.in_gegt_of} in
265 let m'' = MAL.add v rv' m' in
268 and add_ge_arc_fast u v m =
270 let ru' = { ru with one_s_ge = SOF.add v ru.one_s_ge} in
271 let m' = MAL.add u ru' m in
272 let rv = repr v m' in
273 let rv' = {rv with in_gegt_of = SOF.add u rv.in_gegt_of} in
274 let m'' = MAL.add v rv' m' in
277 and add_eq_arc_fast u v m =
280 let ru' = {ru with one_s_eq = SOF.add v ru.one_s_eq} in
281 (*TESI: let ru' = {ru' with in_gegt_of = SOF.add v ru.in_gegt_of} in *)
282 let m' = MAL.add u ru' m in
283 let rv' = {rv with one_s_eq = SOF.add u rv.one_s_eq} in
284 (*TESI: let rv' = {rv' with in_gegt_of = SOF.add u rv.in_gegt_of} in *)
285 let m'' = MAL.add v rv' m' in
286 adjust_fast v (*(adjust_fast u*) m'' (* ) *)
290 (*****************************************************************************)
291 (** safe implementation **)
292 (*****************************************************************************)
297 let j = ru.one_s_eq in
298 let _Uj = merge_closures (fun x -> x.eq_closure) j m in
299 let one_step_eq = ru.one_s_eq in
300 (SOF.union one_step_eq _Uj)
303 let j = SOF.union ru.one_s_ge (SOF.union ru.one_s_gt ru.one_s_eq) in
304 let _Uj = merge_closures (fun x -> x.ge_closure) j m in
309 let j = ru.one_s_gt in
310 let k = ru.one_s_ge in
311 let l = ru.one_s_eq in
312 let _Uj = merge_closures (fun x -> x.ge_closure) j m in
313 let _Uk = merge_closures (fun x -> x.gt_closure) k m in
314 let _Ul = merge_closures (fun x -> x.gt_closure) l m in
315 let one_step_gt = ru.one_s_gt in
316 (SOF.union (SOF.union (SOF.union _Ul one_step_gt) _Uk) _Uj)
322 in_gegt_of = ru.in_gegt_of;
323 one_s_eq = ru.one_s_eq;
324 one_s_ge = ru.one_s_ge;
325 one_s_gt = ru.one_s_gt
328 let rec simple_adjust m =
330 MAL.mapi (fun x _ -> closure_of x m) m
332 if not (are_ugraph_eq m m') then(
337 let add_eq_arc u v m =
340 let ru' = {ru with one_s_eq = SOF.add v ru.one_s_eq} in
341 let m' = MAL.add u ru' m in
342 let rv' = {rv with one_s_eq = SOF.add u rv.one_s_eq} in
343 let m'' = MAL.add v rv' m' in
346 let add_ge_arc u v m =
348 let ru' = { ru with one_s_ge = SOF.add v ru.one_s_ge} in
349 let m' = MAL.add u ru' m in
352 let add_gt_arc u v m =
354 let ru' = {ru with one_s_gt = SOF.add v ru.one_s_gt} in
355 let m' = MAL.add u ru' m in
359 (*****************************************************************************)
360 (** Outhern interface, that chooses between _fast and safe **)
361 (*****************************************************************************)
364 given the 2 nodes plus the current bag, adds the arc, recomputes the
365 closures and returns the new map
367 let add_eq fast u v b =
369 add_eq_arc_fast u v b
374 given the 2 nodes plus the current bag, adds the arc, recomputes the
375 closures and returns the new map
377 let add_ge fast u v b =
379 add_ge_arc_fast u v b
383 given the 2 nodes plus the current bag, adds the arc, recomputes the
384 closures and returns the new map
386 let add_gt fast u v b =
388 add_gt_arc_fast u v b
393 (*****************************************************************************)
394 (** Other real code **)
395 (*****************************************************************************)
397 exception UniverseInconsistency of string
399 let error arc node1 closure_type node2 closure =
400 let s = "\n ===== Universe Inconsistency detected =====\n\n" ^
402 "\t" ^ (string_of_arc arc) ^ "\n" ^
404 "\t" ^ (string_of_universe node1) ^ "\n" ^
405 " is in the " ^ closure_type ^ " closure\n" ^
406 "\t{" ^ (string_of_universe_set closure) ^ "}\n" ^
408 "\t" ^ (string_of_universe node2) ^ "\n\n" ^
409 " ===== Universe Inconsistency detected =====\n" in
411 raise (UniverseInconsistency s)
414 let fill_empty_nodes_with_uri g l uri =
415 let fill_empty_universe u =
417 (i,None) -> (i,Some uri)
418 | (i,Some _) as u -> u
420 let fill_empty_set s =
421 SOF.fold (fun e s -> SOF.add (fill_empty_universe e) s) s SOF.empty
423 let fill_empty_entry e = {
424 eq_closure = (fill_empty_set e.eq_closure) ;
425 ge_closure = (fill_empty_set e.ge_closure) ;
426 gt_closure = (fill_empty_set e.gt_closure) ;
427 in_gegt_of = (fill_empty_set e.in_gegt_of) ;
428 one_s_eq = (fill_empty_set e.one_s_eq) ;
429 one_s_ge = (fill_empty_set e.one_s_ge) ;
430 one_s_gt = (fill_empty_set e.one_s_gt) ;
435 MAL.add (fill_empty_universe k) (fill_empty_entry v) m) m MAL.empty
437 let l' = List.map fill_empty_universe l in
441 (*****************************************************************************)
442 (** World interface **)
443 (*****************************************************************************)
445 type universe_graph = bag
447 let empty_ugraph = empty_bag
449 let current_index_anon = ref (-1)
450 let current_index_named = ref (-1)
452 let restart_numbering () = current_index_named := (-1)
454 let fresh ?uri ?id () =
458 current_index_anon := !current_index_anon + 1;
460 | None, Some _ -> assert false
462 current_index_named := !current_index_named + 1;
464 | Some _, Some id -> id
469 prerr_endline (string_of_bag g)
471 let add_eq ?(fast=(!fast_implementation)) u v b =
472 (* should we check to no add twice the same?? *)
475 if SOF.mem v ru.gt_closure then
476 error ("EQ",u,v) v "GT" u ru.gt_closure
480 if SOF.mem u rv.gt_closure then
481 error ("EQ",u,v) u "GT" v rv.gt_closure
486 let add_ge ?(fast=(!fast_implementation)) u v b =
487 (* should we check to no add twice the same?? *)
490 if SOF.mem u rv.gt_closure then
491 error ("GE",u,v) u "GT" v rv.gt_closure
495 let add_gt ?(fast=(!fast_implementation)) u v b =
496 (* should we check to no add twice the same?? *)
498 FIXME : check the thesis... no need to check GT and EQ closure since the
499 GE is a superset of both
505 error ("GT",u,v) u "==" v SOF.empty
508 (*if SOF.mem u rv.gt_closure then
509 error ("GT",u,v) u "GT" v rv.gt_closure
512 if SOF.mem u rv.ge_closure then
513 error ("GT",u,v) u "GE" v rv.ge_closure
516 if SOF.mem u rv.eq_closure then
517 error ("GT",u,v) u "EQ" v rv.eq_closure
523 (*****************************************************************************)
524 (** START: Decomment this for performance comparisons **)
525 (*****************************************************************************)
527 let add_eq ?(fast=(!fast_implementation)) u v b =
529 let rc = add_eq ~fast u v b in
533 let add_ge ?(fast=(!fast_implementation)) u v b =
535 let rc = add_ge ~fast u v b in
539 let add_gt ?(fast=(!fast_implementation)) u v b =
541 let rc = add_gt ~fast u v b in
545 (*****************************************************************************)
546 (** END: Decomment this for performance comparisons **)
547 (*****************************************************************************)
549 let merge_ugraphs u v =
551 let merge_brutal u v =
552 if u = empty_bag then v
553 else if v = empty_bag then u
561 let m = add_gt k u x in m) v.one_s_gt
564 let m = add_ge k u x in m) v.one_s_ge
567 let m = add_eq k u x in m) v.one_s_eq x)))
573 (*****************************************************************************)
574 (** Xml sesialization and parsing **)
575 (*****************************************************************************)
577 let xml_of_universe name u =
581 None,"id",(string_of_int i) ;
582 None,"uri",(UriManager.string_of_uri u)]
584 raise (Failure "we can serialize only universes with uri")
588 List.map (xml_of_universe "node") (SOF.elements s)
590 List.fold_left (fun s x -> [< s ; x >] ) [<>] l
592 let xml_of_entry_content e =
593 let stream_of_field f name =
594 let eq_c = xml_of_set f in
596 Xml.xml_nempty name [] eq_c
601 (stream_of_field e.eq_closure "eq_closure");
602 (stream_of_field e.gt_closure "gt_closure");
603 (stream_of_field e.ge_closure "ge_closure");
604 (stream_of_field e.in_gegt_of "in_gegt_of");
605 (stream_of_field e.one_s_eq "one_s_eq");
606 (stream_of_field e.one_s_gt "one_s_gt");
607 (stream_of_field e.one_s_ge "one_s_ge")
610 let xml_of_entry u e =
616 raise (Failure "we can serialize only universes (entry) with uri")
618 let ent = Xml.xml_nempty "entry" [
619 None,"id",(string_of_int i) ;
620 None,"uri",(UriManager.string_of_uri u'')] in
621 let content = xml_of_entry_content e in
624 let write_xml_of_ugraph filename m l =
627 Xml.xml_cdata "<?xml version=\"1.0\" encoding=\"ISO-8859-1\"?>\n";
628 Xml.xml_nempty "ugraph" []
629 ([< (MAL.fold ( fun k v s -> [< s ; (xml_of_entry k v) >]) m [<>]) ;
631 (fun s u -> [< s ; xml_of_universe "owned_node" u >]) [<>] l) >])>]
633 Xml.pp ~gzip:true tokens (Some filename)
638 let rec clean_ugraph m f =
640 MAL.fold (fun k v x -> if (f k) then MAL.add k v x else x ) m MAL.empty in
641 let m'' = MAL.fold (fun k v x ->
643 eq_closure = SOF.filter f v.eq_closure;
644 ge_closure = SOF.filter f v.ge_closure;
645 gt_closure = SOF.filter f v.gt_closure;
646 in_gegt_of = SOF.filter f v.in_gegt_of;
647 one_s_eq = SOF.filter f v.one_s_eq;
648 one_s_ge = SOF.filter f v.one_s_ge;
649 one_s_gt = SOF.filter f v.one_s_gt
651 MAL.add k v' x ) m' MAL.empty in
653 MAL.fold (fun k v l -> if v = empty_entry then k::l else l) m'' []
656 clean_ugraph m'' (fun u -> (f u) && not (List.mem u e_l))
660 let clean_ugraph g l =
661 clean_ugraph g (fun u -> List.mem u l)
665 "ge_closure" -> (fun e u->{e with ge_closure=SOF.add u e.ge_closure})
666 | "gt_closure" -> (fun e u->{e with gt_closure=SOF.add u e.gt_closure})
667 | "eq_closure" -> (fun e u->{e with eq_closure=SOF.add u e.eq_closure})
668 | "in_gegt_of" -> (fun e u->{e with in_gegt_of =SOF.add u e.in_gegt_of})
669 | "one_s_ge" -> (fun e u->{e with one_s_ge =SOF.add u e.one_s_ge})
670 | "one_s_gt" -> (fun e u->{e with one_s_gt =SOF.add u e.one_s_gt})
671 | "one_s_eq" -> (fun e u->{e with one_s_eq =SOF.add u e.one_s_eq})
672 | s -> raise (Failure ("unsupported tag " ^ s))
676 let module XPP = XmlPushParser in
677 let current_node = ref (0,None) in
678 let current_entry = ref empty_entry in
679 let current_assign = ref (assigner_of "in_gegt_of") in
680 { XPP.default_callbacks with
681 XPP.end_element = Some( fun name ->
684 m := MAL.add !current_node !current_entry !m;
685 current_entry := empty_entry
688 XPP.start_element = Some( fun name attlist ->
692 let id = List.assoc "id" attlist in
693 let uri = List.assoc "uri" attlist in
694 current_node := (int_of_string id,Some (UriManager.uri_of_string uri))
696 let id = int_of_string (List.assoc "id" attlist) in
697 let uri = List.assoc "uri" attlist in
698 current_entry := !current_assign !current_entry
699 (id,Some (UriManager.uri_of_string uri))
701 let id = int_of_string (List.assoc "id" attlist) in
702 let uri = List.assoc "uri" attlist in
703 l := (id,Some (UriManager.uri_of_string uri)) :: !l
704 | s -> current_assign := assigner_of s
709 let ugraph_and_univlist_of_xml filename =
710 let module XPP = XmlPushParser in
711 let result_map = ref MAL.empty in
712 let result_list = ref [] in
713 let cb = cb_factory result_map result_list in
714 let xml_parser = XPP.create_parser cb in
715 let xml_source = `Gzip_file filename in
716 (try XPP.parse xml_parser xml_source
717 with (XPP.Parse_error err) as exn -> raise exn);
718 !result_map, !result_list
721 (*****************************************************************************)
722 (** the main, only for testing **)
723 (*****************************************************************************)
727 type arc = Ge | Gt | Eq ;;
729 let randomize_actionlist n m =
730 let ge_percent = 0.7 in
731 let gt_percent = 0.15 in
733 let node1 = Random.int m in
734 let node2 = Random.int m in
736 let r = Random.float 1.0 in
737 if r < ge_percent then
739 else (if r < (ge_percent +. gt_percent) then
749 | n -> (random_step ())::(aux (n-1))
753 let print_action_list l =
754 let string_of_step (op,node1,node2) =
759 "," ^ (string_of_int node1) ^ "," ^ (string_of_int node2)
765 ";" ^ (string_of_step a) ^ (aux tl)
768 let l_body = (String.length body) - 1 in
769 prerr_endline ("[" ^ (String.sub body 1 l_body))
772 let d_print_endline = if debug then print_endline else ignore
773 let d_print_ugraph = if debug then print_ugraph else ignore
776 (if Array.length Sys.argv < 2 then
777 prerr_endline ("Usage " ^ Sys.argv.(0) ^ " max_edges max_nodes"));
779 let max_edges = int_of_string Sys.argv.(1) in
780 let max_nodes = int_of_string Sys.argv.(2) in
781 let action_listR = randomize_actionlist max_edges max_nodes in
783 let action_list = [Ge,1,4;Ge,2,6;Ge,1,1;Eq,6,4;Gt,6,3] in
784 let action_list = action_listR in
786 print_action_list action_list;
787 let prform_step ?(fast=false) (t,u,v) g =
799 let g' = f ~fast (u,None) (v,None) g in
800 (*print_ugraph g' ;*)
803 let fail = ref false in
804 let time1 = Unix.gettimeofday () in
805 let n_safe = ref 0 in
808 d_print_endline "SAFE";
811 n_safe := !n_safe + 1;
813 ) empty_ugraph action_list
815 UniverseInconsistency s -> fail:=true;empty_bag
817 let time2 = Unix.gettimeofday () in
818 d_print_ugraph g_safe;
819 let time3 = Unix.gettimeofday () in
820 let n_test = ref 0 in
823 d_print_endline "FAST";
826 n_test := !n_test + 1;
827 prform_step ~fast:true e g
828 ) empty_ugraph action_list
830 UniverseInconsistency s -> empty_bag
832 let time4 = Unix.gettimeofday () in
833 d_print_ugraph g_test;
834 if are_ugraph_eq g_safe g_test && !n_test = !n_safe then
839 if e = Eq then s+1 else s
845 if e = Gt then s+1 else s
848 let num_ge = max_edges - num_gt - num_eq in
849 let time_fast = (time4 -. time3) in
850 let time_safe = (time2 -. time1) in
851 let gap = ((time_safe -. time_fast) *. 100.0) /. time_safe in
852 let fail = if !fail then 1 else 0 in
855 "OK %d safe %1.4f fast %1.4f %% %1.2f #eq %d #gt %d #ge %d %d"
856 fail time_safe time_fast gap num_eq num_gt num_ge !n_safe);
861 print_endline "FAIL";
874 i, Some (UriManager.uri_of_string (UriManager.string_of_uri uri))
876 let recons_entry entry =
878 SOF.fold (fun univ set -> SOF.add (recons_univ univ) set) set SOF.empty
881 eq_closure = recons_set entry.eq_closure;
882 ge_closure = recons_set entry.ge_closure;
883 gt_closure = recons_set entry.gt_closure;
884 in_gegt_of = recons_set entry.in_gegt_of;
885 one_s_eq = recons_set entry.one_s_eq;
886 one_s_ge = recons_set entry.one_s_ge;
887 one_s_gt = recons_set entry.one_s_gt;
890 let recons_graph graph =
892 (fun universe entry map ->
893 MAL.add (recons_univ universe) (recons_entry entry) map)
898 | (_,None) -> raise (UniverseInconsistency "This universe graph has a hole")
901 let assert_univs_have_uri graph univlist =
903 SOF.iter (fun u -> assert_univ u) s
906 assert_set e.eq_closure;
907 assert_set e.ge_closure;
908 assert_set e.gt_closure;
909 assert_set e.in_gegt_of;
910 assert_set e.one_s_eq;
911 assert_set e.one_s_ge;
912 assert_set e.one_s_gt;
914 MAL.iter (fun k v -> assert_univ k; assert_entry v)graph;
915 List.iter assert_univ univlist
919 | (id1, Some uri1),(id2, Some uri2) ->
920 id1 = id2 && UriManager.eq uri1 uri2
921 | (id1, None),(id2, None) -> id1 = id2
924 let compare (id1, uri1) (id2, uri2) =
925 let cmp = id1 - id2 in
930 | None, Some _ -> ~-1
931 | Some uri1, Some uri2 -> UriManager.compare uri1 uri2