src/Tools/Code/code_namespace.ML
author haftmann
Sun Feb 23 10:33:43 2014 +0100 (2014-02-23)
changeset 55683 5732a55b9232
parent 55681 7714287dc044
child 55684 ee49b4f7edc8
permissions -rw-r--r--
explicit option for "open" code generation
     1 (*  Title:      Tools/Code/code_namespace.ML
     2     Author:     Florian Haftmann, TU Muenchen
     3 
     4 Mastering target language namespaces.
     5 *)
     6 
     7 signature CODE_NAMESPACE =
     8 sig
     9   datatype export = Private | Opaque | Public
    10   val is_public: export -> bool
    11   val not_private: export -> bool
    12 
    13   type flat_program
    14   val flat_program: Proof.context
    15     -> { module_prefix: string, module_name: string,
    16     reserved: Name.context, identifiers: Code_Target.identifier_data, empty_nsp: 'a,
    17     namify_stmt: Code_Thingol.stmt -> string -> 'a -> string * 'a,
    18     modify_stmt: Code_Thingol.stmt -> Code_Thingol.stmt option }
    19       -> Code_Symbol.T list -> Code_Thingol.program
    20       -> { deresolver: string -> Code_Symbol.T -> string,
    21            flat_program: flat_program }
    22 
    23   datatype ('a, 'b) node =
    24       Dummy
    25     | Stmt of export * 'a
    26     | Module of ('b * (string * ('a, 'b) node) Code_Symbol.Graph.T)
    27   type ('a, 'b) hierarchical_program
    28   val hierarchical_program: Proof.context
    29     -> { module_name: string,
    30     reserved: Name.context, identifiers: Code_Target.identifier_data,
    31     empty_nsp: 'c, namify_module: string -> 'c -> string * 'c,
    32     namify_stmt: Code_Thingol.stmt -> string -> 'c -> string * 'c,
    33     cyclic_modules: bool, empty_data: 'b, memorize_data: Code_Symbol.T -> 'b -> 'b,
    34     modify_stmts: (Code_Symbol.T * Code_Thingol.stmt) list -> 'a option list }
    35       -> Code_Symbol.T list -> Code_Thingol.program
    36       -> { deresolver: string list -> Code_Symbol.T -> string,
    37            hierarchical_program: ('a, 'b) hierarchical_program }
    38   val print_hierarchical: { print_module: string list -> string -> 'b -> 'c list -> 'c,
    39     print_stmt: string list -> Code_Symbol.T * (export * 'a) -> 'c,
    40     lift_markup: (Pretty.T -> Pretty.T) -> 'c -> 'c }
    41       -> ('a, 'b) hierarchical_program -> 'c list
    42 end;
    43 
    44 structure Code_Namespace : CODE_NAMESPACE =
    45 struct
    46 
    47 (** export **)
    48 
    49 datatype export = Private | Opaque | Public;
    50 
    51 fun is_public Public = true
    52   | is_public _ = false;
    53 
    54 fun not_private Public = true
    55   | not_private Opaque = true
    56   | not_private _ = false;
    57 
    58 
    59 (** fundamental module name hierarchy **)
    60 
    61 fun module_fragments' { identifiers, reserved } name =
    62   case Code_Symbol.lookup_module_data identifiers name of
    63       SOME (fragments, _) => fragments
    64     | NONE => map (fn fragment => fst (Name.variant fragment reserved)) (Long_Name.explode name);
    65 
    66 fun module_fragments { module_name, identifiers, reserved } =
    67   if module_name = ""
    68   then module_fragments' { identifiers = identifiers, reserved = reserved }
    69   else K (Long_Name.explode module_name);
    70 
    71 fun build_module_namespace ctxt { module_prefix, module_name, identifiers, reserved } program =
    72   let
    73     val module_names = Code_Symbol.Graph.fold (insert (op =) o Code_Symbol.default_prefix ctxt o fst) program [];
    74     val module_fragments' = module_fragments
    75       { module_name = module_name, identifiers = identifiers, reserved = reserved };
    76   in
    77     fold (fn name => Symtab.update (name, Long_Name.explode module_prefix @ module_fragments' name))
    78       module_names Symtab.empty
    79   end;
    80 
    81 fun prep_symbol ctxt { module_namespace, force_module, identifiers } sym =
    82   case Code_Symbol.lookup identifiers sym of
    83       NONE => ((the o Symtab.lookup module_namespace o Code_Symbol.default_prefix ctxt) sym,
    84         Code_Symbol.default_base sym)
    85     | SOME prefix_name => if null force_module then prefix_name
    86         else (force_module, snd prefix_name);
    87 
    88 fun has_priority identifiers = is_some o Code_Symbol.lookup identifiers;
    89 
    90 fun build_proto_program { empty, add_stmt, add_dep } program =
    91   empty
    92   |> Code_Symbol.Graph.fold (fn (sym, (stmt, _)) => add_stmt sym stmt) program
    93   |> Code_Symbol.Graph.fold (fn (sym, (_, (_, syms))) =>
    94       Code_Symbol.Graph.Keys.fold (add_dep sym) syms) program;
    95 
    96 fun prioritize has_priority = uncurry append o List.partition has_priority;
    97 
    98 
    99 (** flat program structure **)
   100 
   101 type flat_program = ((string * (export * Code_Thingol.stmt) option) Code_Symbol.Graph.T * (string * Code_Symbol.T list) list) Graph.T;
   102 
   103 fun flat_program ctxt { module_prefix, module_name, reserved,
   104     identifiers, empty_nsp, namify_stmt, modify_stmt } exports program =
   105   let
   106 
   107     (* building module name hierarchy *)
   108     val module_namespace = build_module_namespace ctxt { module_prefix = module_prefix,
   109       module_name = module_name, identifiers = identifiers, reserved = reserved } program;
   110     val prep_sym = prep_symbol ctxt { module_namespace = module_namespace,
   111       force_module = Long_Name.explode module_name, identifiers = identifiers }
   112       #>> Long_Name.implode;
   113     val sym_priority = has_priority identifiers;
   114 
   115     (* distribute statements over hierarchy *)
   116     fun add_stmt sym stmt =
   117       let
   118         val (module_name, base) = prep_sym sym;
   119       in
   120         Graph.default_node (module_name, (Code_Symbol.Graph.empty, []))
   121         #> (Graph.map_node module_name o apfst)
   122           (Code_Symbol.Graph.new_node (sym, (base, (Public, stmt))))
   123       end;
   124     fun add_dep sym sym' =
   125       let
   126         val (module_name, _) = prep_sym sym;
   127         val (module_name', _) = prep_sym sym';
   128       in if module_name = module_name'
   129         then (Graph.map_node module_name o apfst) (Code_Symbol.Graph.add_edge (sym, sym'))
   130         else (Graph.map_node module_name o apsnd)
   131           (AList.map_default (op =) (module_name', []) (insert (op =) sym'))
   132       end;
   133     val proto_program = build_proto_program
   134       { empty = Graph.empty, add_stmt = add_stmt, add_dep = add_dep } program;
   135 
   136     (* name declarations and statement modifications *)
   137     fun declare sym (base, (_, stmt)) (gr, nsp) = 
   138       let
   139         val (base', nsp') = namify_stmt stmt base nsp;
   140         val gr' = (Code_Symbol.Graph.map_node sym o apfst) (K base') gr;
   141       in (gr', nsp') end;
   142     fun declarations gr = (gr, empty_nsp)
   143       |> fold (fn sym => declare sym (Code_Symbol.Graph.get_node gr sym))
   144           (prioritize sym_priority (Code_Symbol.Graph.keys gr))
   145       |> fst
   146       |> Code_Symbol.Graph.map_strong_conn (fn syms_bases_exports_stmts =>
   147         map snd syms_bases_exports_stmts
   148         |> (map o apsnd) (fn (export, stmt) => Option.map (pair export) (modify_stmt stmt)));
   149     val flat_program = proto_program
   150       |> (Graph.map o K o apfst) declarations;
   151 
   152     (* qualified and unqualified imports, deresolving *)
   153     fun base_deresolver sym = fst (Code_Symbol.Graph.get_node
   154       (fst (Graph.get_node flat_program (fst (prep_sym sym)))) sym);
   155     fun classify_names gr imports =
   156       let
   157         val import_tab = maps
   158           (fn (module_name, syms) => map (rpair module_name) syms) imports;
   159         val imported_syms = map fst import_tab;
   160         val here_syms = Code_Symbol.Graph.keys gr;
   161       in
   162         Code_Symbol.Table.empty
   163         |> fold (fn sym => Code_Symbol.Table.update (sym, base_deresolver sym)) here_syms
   164         |> fold (fn sym => Code_Symbol.Table.update (sym,
   165             Long_Name.append (the (AList.lookup (op =) import_tab sym))
   166               (base_deresolver sym))) imported_syms
   167       end;
   168     val deresolver_tab = Symtab.make (AList.make
   169       (uncurry classify_names o Graph.get_node flat_program)
   170         (Graph.keys flat_program));
   171     fun deresolver "" sym =
   172           Long_Name.append (fst (prep_sym sym)) (base_deresolver sym)
   173       | deresolver module_name sym =
   174           the (Code_Symbol.Table.lookup (the (Symtab.lookup deresolver_tab module_name)) sym)
   175           handle Option.Option => error ("Unknown statement name: "
   176             ^ Code_Symbol.quote ctxt sym);
   177 
   178   in { deresolver = deresolver, flat_program = flat_program } end;
   179 
   180 
   181 (** hierarchical program structure **)
   182 
   183 datatype ('a, 'b) node =
   184     Dummy
   185   | Stmt of export * 'a
   186   | Module of ('b * (string * ('a, 'b) node) Code_Symbol.Graph.T);
   187 
   188 type ('a, 'b) hierarchical_program = (string * ('a, 'b) node) Code_Symbol.Graph.T;
   189 
   190 fun the_stmt (Stmt (export, stmt)) = (export, stmt);
   191 
   192 fun map_module_content f (Module content) = Module (f content);
   193 
   194 fun map_module [] = I
   195   | map_module (name_fragment :: name_fragments) =
   196       apsnd o Code_Symbol.Graph.map_node (Code_Symbol.Module name_fragment) o apsnd o map_module_content
   197         o map_module name_fragments;
   198 
   199 fun map_module_stmts f_module f_stmts sym_base_nodes =
   200   let
   201     val some_modules =
   202       sym_base_nodes
   203       |> map (fn (sym, (base, Module content)) => SOME (base, content) | _ => NONE)
   204       |> (burrow_options o map o apsnd) f_module;
   205     val some_export_stmts =
   206       sym_base_nodes
   207       |> map (fn (sym, (base, Stmt export_stmt)) => SOME ((sym, export_stmt), base) | _ => NONE)
   208       |> (burrow_options o burrow_fst) (fn [] => [] | xs => f_stmts xs)
   209   in
   210     map2 (fn SOME (base, content) => (K (base, Module content))
   211       | NONE => fn SOME (some_export_stmt, base) =>
   212           (base, case some_export_stmt of SOME export_stmt => Stmt export_stmt | NONE => Dummy))
   213       some_modules some_export_stmts
   214   end;
   215 
   216 fun hierarchical_program ctxt { module_name, reserved, identifiers, empty_nsp,
   217       namify_module, namify_stmt, cyclic_modules, empty_data, memorize_data, modify_stmts }
   218       exports program =
   219   let
   220 
   221     (* building module name hierarchy *)
   222     val module_namespace = build_module_namespace ctxt { module_prefix = "",
   223       module_name = module_name, identifiers = identifiers, reserved = reserved } program;
   224     val prep_sym = prep_symbol ctxt { module_namespace = module_namespace,
   225       force_module = Long_Name.explode module_name, identifiers = identifiers }
   226     val sym_priority = has_priority identifiers;
   227 
   228     (* building empty module hierarchy *)
   229     val empty_module = (empty_data, Code_Symbol.Graph.empty);
   230     fun ensure_module name_fragment (data, nodes) =
   231       if can (Code_Symbol.Graph.get_node nodes) (Code_Symbol.Module name_fragment) then (data, nodes)
   232       else (data,
   233         nodes |> Code_Symbol.Graph.new_node (Code_Symbol.Module name_fragment, (name_fragment, Module empty_module)));
   234     fun allocate_module [] = I
   235       | allocate_module (name_fragment :: name_fragments) =
   236           ensure_module name_fragment
   237           #> (apsnd o Code_Symbol.Graph.map_node (Code_Symbol.Module name_fragment) o apsnd o map_module_content o allocate_module) name_fragments;
   238     val empty_program =
   239       empty_module
   240       |> Symtab.fold (fn (_, fragments) => allocate_module fragments) module_namespace
   241       |> Code_Symbol.Graph.fold (allocate_module o these o Option.map fst
   242           o Code_Symbol.lookup identifiers o fst) program;
   243 
   244     (* distribute statements over hierarchy *)
   245     fun add_stmt sym stmt =
   246       let
   247         val (name_fragments, base) = prep_sym sym;
   248       in
   249         (map_module name_fragments o apsnd)
   250           (Code_Symbol.Graph.new_node (sym, (base, Stmt (Public, stmt))))
   251       end;
   252     fun add_edge_acyclic_error error_msg dep gr =
   253       Code_Symbol.Graph.add_edge_acyclic dep gr
   254         handle Graph.CYCLES _ => error (error_msg ())
   255     fun add_dep sym sym' =
   256       let
   257         val (name_fragments, _) = prep_sym sym;
   258         val (name_fragments', _) = prep_sym sym';
   259         val (name_fragments_common, (diff, diff')) =
   260           chop_prefix (op =) (name_fragments, name_fragments');
   261         val is_cross_module = not (null diff andalso null diff');
   262         val dep = pairself hd (map Code_Symbol.Module diff @ [sym], map Code_Symbol.Module diff' @ [sym']);
   263         val add_edge = if is_cross_module andalso not cyclic_modules
   264           then add_edge_acyclic_error (fn _ => "Dependency "
   265             ^ Code_Symbol.quote ctxt sym ^ " -> "
   266             ^ Code_Symbol.quote ctxt sym'
   267             ^ " would result in module dependency cycle") dep
   268           else Code_Symbol.Graph.add_edge dep;
   269       in (map_module name_fragments_common o apsnd) add_edge end;
   270     val proto_program = build_proto_program
   271       { empty = empty_program, add_stmt = add_stmt, add_dep = add_dep } program;
   272 
   273     (* name declarations, data and statement modifications *)
   274     fun make_declarations nsps (data, nodes) =
   275       let
   276         val (module_fragments, stmt_syms) =
   277           Code_Symbol.Graph.keys nodes
   278           |> List.partition
   279               (fn sym => case Code_Symbol.Graph.get_node nodes sym
   280                 of (_, Module _) => true | _ => false)
   281           |> pairself (prioritize sym_priority)
   282         fun declare namify sym (nsps, nodes) =
   283           let
   284             val (base, node) = Code_Symbol.Graph.get_node nodes sym;
   285             val (base', nsps') = namify node base nsps;
   286             val nodes' = Code_Symbol.Graph.map_node sym (K (base', node)) nodes;
   287           in (nsps', nodes') end;
   288         val (nsps', nodes') = (nsps, nodes)
   289           |> fold (declare (K namify_module)) module_fragments
   290           |> fold (declare (namify_stmt o snd o the_stmt)) stmt_syms;
   291         fun modify_stmts' syms_stmts =
   292           let
   293             val stmts' = modify_stmts syms_stmts
   294           in stmts' @ replicate (length syms_stmts - length stmts') NONE end;
   295         fun modify_stmts'' syms_exports_stmts =
   296           syms_exports_stmts
   297           |> map (fn (sym, (export, stmt)) => ((sym, stmt), export))
   298           |> burrow_fst modify_stmts'
   299           |> map (fn (SOME stmt, export) => SOME (export, stmt) | _ => NONE);
   300         val nodes'' =
   301           nodes'
   302           |> Code_Symbol.Graph.map_strong_conn (map_module_stmts (make_declarations nsps') modify_stmts'');
   303         val data' = fold memorize_data stmt_syms data;
   304       in (data', nodes'') end;
   305     val (_, hierarchical_program) = make_declarations empty_nsp proto_program;
   306 
   307     (* deresolving *)
   308     fun deresolver prefix_fragments sym =
   309       let
   310         val (name_fragments, _) = prep_sym sym;
   311         val (_, (_, remainder)) = chop_prefix (op =) (prefix_fragments, name_fragments);
   312         val nodes = fold (fn name_fragment => fn nodes => case Code_Symbol.Graph.get_node nodes (Code_Symbol.Module name_fragment)
   313          of (_, Module (_, nodes)) => nodes) name_fragments hierarchical_program;
   314         val (base', _) = Code_Symbol.Graph.get_node nodes sym;
   315       in Long_Name.implode (remainder @ [base']) end
   316         handle Code_Symbol.Graph.UNDEF _ => error ("Unknown statement name: "
   317           ^ Code_Symbol.quote ctxt sym);
   318 
   319   in { deresolver = deresolver, hierarchical_program = hierarchical_program } end;
   320 
   321 fun print_hierarchical { print_module, print_stmt, lift_markup } =
   322   let
   323     fun print_node _ (_, Dummy) =
   324           NONE
   325       | print_node prefix_fragments (sym, Stmt stmt) =
   326           SOME (lift_markup (Code_Printer.markup_stmt sym)
   327             (print_stmt prefix_fragments (sym, stmt)))
   328       | print_node prefix_fragments (Code_Symbol.Module name_fragment, Module (data, nodes)) =
   329           let
   330             val prefix_fragments' = prefix_fragments @ [name_fragment]
   331           in
   332             Option.map (print_module prefix_fragments'
   333               name_fragment data) (print_nodes prefix_fragments' nodes)
   334           end
   335     and print_nodes prefix_fragments nodes =
   336       let
   337         val xs = (map_filter (fn sym => print_node prefix_fragments
   338           (sym, snd (Code_Symbol.Graph.get_node nodes sym))) o rev o flat o Code_Symbol.Graph.strong_conn) nodes
   339       in if null xs then NONE else SOME xs end;
   340   in these o print_nodes [] end;
   341 
   342 end;