diff options
| author | Jakob L. Kreuze | 2023-10-21 13:53:43 -0400 |
|---|---|---|
| committer | Jakob L. Kreuze | 2023-10-21 13:53:43 -0400 |
| commit | 5d7f7009e9e556a34467d65bee2e02aa4b48a95a (patch) | |
| tree | dfc33fc81047a604e0f533ba8c19afce1bc2af0f | |
| parent | c29a790f63c578ee1059e0d73b5cff4036de90ab (diff) | |
ocamlformat
| -rw-r--r-- | rego-proofs/compiler-rewrite/.ocamlformat | 1 | ||||
| -rw-r--r-- | rego-proofs/compiler-rewrite/bin/main.ml | 17 | ||||
| -rw-r--r-- | rego-proofs/compiler-rewrite/lib/compiler.ml | 311 | ||||
| -rw-r--r-- | rego-proofs/compiler-rewrite/lib/compiler.mli | 29 | ||||
| -rw-r--r-- | rego-proofs/compiler-rewrite/test/compiler_rewrite.ml | 64 |
5 files changed, 224 insertions, 198 deletions
diff --git a/rego-proofs/compiler-rewrite/.ocamlformat b/rego-proofs/compiler-rewrite/.ocamlformat new file mode 100644 index 0000000..c870de9 --- /dev/null +++ b/rego-proofs/compiler-rewrite/.ocamlformat @@ -0,0 +1 @@ +version=0.26.1 diff --git a/rego-proofs/compiler-rewrite/bin/main.ml b/rego-proofs/compiler-rewrite/bin/main.ml index bbc8541..3390ac7 100644 --- a/rego-proofs/compiler-rewrite/bin/main.ml +++ b/rego-proofs/compiler-rewrite/bin/main.ml @@ -1,18 +1,21 @@ open Core open Compiler_rewrite.Compiler -let invoke ?(stdin="") ?(env=[| |]) cmd = - let ic, oc, ec = UnixLabels.open_process_full cmd ~env:env in - Out_channel.output_string oc stdin ; +let invoke ?(stdin = "") ?(env = [||]) cmd = + let ic, oc, ec = UnixLabels.open_process_full cmd ~env in + Out_channel.output_string oc stdin; Out_channel.close oc; - (In_channel.input_all ic, - In_channel.input_all ec) + (In_channel.input_all ic, In_channel.input_all ec) let () = let file_name = Array.get (Sys.get_argv ()) 1 in let policy_code = In_channel.read_all file_name in - let (stdout, _) = invoke ("/home/jakob/.local/bin/opa parse -f json /dev/stdin") ~stdin:policy_code ~env:[| |] in + let stdout, _ = + invoke "/home/jakob/.local/bin/opa parse -f json /dev/stdin" + ~stdin:policy_code ~env:[||] + in let ast = Yojson.Basic.from_string stdout |> parse_tree in match ast with - | { policy = [{ body = body; _ }]; _ } -> (extract_local_variables_wrapper body) |> List.iter ~f:print_endline + | { policy = [ { body; _ } ]; _ } -> + extract_local_variables_wrapper body |> List.iter ~f:print_endline | _ -> print_endline "failed" diff --git a/rego-proofs/compiler-rewrite/lib/compiler.ml b/rego-proofs/compiler-rewrite/lib/compiler.ml index 53992b8..4af14d1 100644 --- a/rego-proofs/compiler-rewrite/lib/compiler.ml +++ b/rego-proofs/compiler-rewrite/lib/compiler.ml @@ -1,123 +1,117 @@ open Core open Yojson.Basic.Util -type expr = Term of term - | Every of (string option) * string * term * query +type expr = Term of term | Every of string option * string * term * query [@@deriving show] -and literal = Exists of (expr list) * (with_modifier option) - | Expr of expr * (with_modifier option) - | Negate of expr * (with_modifier option) -[@@deriving show] -and query = literal list -[@@deriving show] -and term = Scalar of scalar - | Var of string - | Ref of reference - | Array of term list - | Object of (object_key * term) list - | Set of term list - | ArrayComprehension of term * query - | ObjectComprehension of (object_key * term) * query - | SetComprehension of term * query - | Call of reference * (term list) -[@@deriving show] -and scalar = String of string - | Number of float - | Bool of bool - | Null -[@@deriving show] -and reference = ref_target * (term list) -[@@deriving show] -and ref_target = Var of string - | Array of term list - | Object of (object_key * term) list - | Set of term list - | ArrayComprehension of term * query - | ObjectComprehension of (object_key * term) * query - | SetComprehension of term * query - | Call of reference * (term list) -[@@deriving show] -and object_key = Scalar of scalar - | Ref of reference - | Var of string + +and literal = + | Exists of expr list * with_modifier option + | Expr of expr * with_modifier option + | Negate of expr * with_modifier option [@@deriving show] -and with_modifier = (term * term) list + +and query = literal list [@@deriving show] + +and term = + | Scalar of scalar + | Var of string + | Ref of reference + | Array of term list + | Object of (object_key * term) list + | Set of term list + | ArrayComprehension of term * query + | ObjectComprehension of (object_key * term) * query + | SetComprehension of term * query + | Call of reference * term list [@@deriving show] -type assign_operator = Assign | Unify +and scalar = String of string | Number of float | Bool of bool | Null [@@deriving show] -type rule_head_lhs = reference +and reference = ref_target * term list [@@deriving show] + +and ref_target = + | Var of string + | Array of term list + | Object of (object_key * term) list + | Set of term list + | ArrayComprehension of term * query + | ObjectComprehension of (object_key * term) * query + | SetComprehension of term * query + | Call of reference * term list [@@deriving show] -type rule_head_rhs = Assignment of assign_operator * term - | Function of assign_operator * (string list) * term - | Set of term + +and object_key = Scalar of scalar | Ref of reference | Var of string [@@deriving show] -type rule_head = rule_head_lhs * rule_head_rhs + +and with_modifier = (term * term) list [@@deriving show] + +type assign_operator = Assign | Unify [@@deriving show] +type rule_head_lhs = reference [@@deriving show] + +type rule_head_rhs = + | Assignment of assign_operator * term + | Function of assign_operator * string list * term + | Set of term [@@deriving show] -type rule = - { default : bool; - head : rule_head; - body: query; - otherwise : rule option; - } + +type rule_head = rule_head_lhs * rule_head_rhs [@@deriving show] + +type rule = { + default : bool; + head : rule_head; + body : query; + otherwise : rule option; +} [@@deriving fields, show] -type import = - { alias : string option; - path : reference; - } -[@@deriving show] +type import = { alias : string option; path : reference } [@@deriving show] -type package = - { path : reference; - imports: import list; - policy : rule list; - } +type package = { path : reference; imports : import list; policy : rule list } [@@deriving fields, show] -module Environ = Map.Make(String);; +module Environ = Map.Make (String) + type environ = string Environ.t let rec term_ground (env : environ) (term : term) : bool = match term with - | Var name -> (Map.find env name) |> Option.is_some - | Ref ((Var name), _) -> (Map.find env name) |> Option.is_some - | Call (_, subterms) -> List.reduce_exn ~f:(&&) (List.map ~f:(term_ground env) subterms) + | Var name -> Map.find env name |> Option.is_some + | Ref (Var name, _) -> Map.find env name |> Option.is_some + | Call (_, subterms) -> + List.reduce_exn ~f:( && ) (List.map ~f:(term_ground env) subterms) | _ -> true let map_with_environment_updates env xs fn = - List.fold xs - ~init:(env, []) - ~f:(fun (env, ys) x -> - let (env', y) = fn env x in - (env', List.append ys [y])) + List.fold xs ~init:(env, []) ~f:(fun (env, ys) x -> + let env', y = fn env x in + (env', List.append ys [ y ])) let extract_local_variables (env : environ) (q : query) : string list = let handle_term env = function - | Call (((Var func), []), [(Var name); rhs]) when (String.equal func "assign") || (String.equal func "eq") -> - if ((Map.find env name) |> Option.is_none) && term_ground env rhs then - match Map.add env ~key:name ~data:name with - | `Duplicate -> failwith "should shadow?" - | `Ok env' -> (env', [name]) - else - (env, []) + | Call ((Var func, []), [ Var name; rhs ]) + when String.equal func "assign" || String.equal func "eq" -> + if Map.find env name |> Option.is_none && term_ground env rhs then + match Map.add env ~key:name ~data:name with + | `Duplicate -> failwith "should shadow?" + | `Ok env' -> (env', [ name ]) + else (env, []) | _ -> (env, []) in let handle_expr env = function | Term t -> handle_term env t - | Every ((Some _key), _value, _, _q) -> failwith "unimplemented" + | Every (Some _key, _value, _, _q) -> failwith "unimplemented" | Every (None, _value, _, _q) -> failwith "unimplemented" in let handle_literal env = function | Exists (exprs, _) -> - let (env', ys) = map_with_environment_updates env exprs handle_expr in - (env', ys |> List.concat) + let env', ys = map_with_environment_updates env exprs handle_expr in + (env', ys |> List.concat) | Expr (expr, _) -> handle_expr env expr | Negate (expr, _) -> handle_expr env expr in - let (_env', identifiers) = map_with_environment_updates env q handle_literal in + let _env', identifiers = map_with_environment_updates env q handle_literal in List.concat identifiers let extract_local_variables_wrapper (q : query) : string list = @@ -125,9 +119,7 @@ let extract_local_variables_wrapper (q : query) : string list = (* --- *) -let is_null : Yojson.Basic.t -> bool = function - | `Null -> true - | _ -> false +let is_null : Yojson.Basic.t -> bool = function `Null -> true | _ -> false let to_bool_or_false : Yojson.Basic.t -> bool = function | `Bool b -> b @@ -152,71 +144,82 @@ let rec parse_term (tree : Yojson.Basic.t) : term = | "boolean" -> Scalar (Bool (tree |> member "value" |> to_bool)) | "number" -> Scalar (Number (tree |> member "value" |> to_number)) | "string" -> Scalar (String (tree |> member "value" |> to_string)) - | "array" -> Array (tree |> member "value" |> to_list |> List.map ~f:parse_term) + | "array" -> + Array (tree |> member "value" |> to_list |> List.map ~f:parse_term) | "set" -> Set (tree |> member "value" |> to_list |> List.map ~f:parse_term) | "object" -> - Object - (tree - |> member "value" - |> to_list + Object + (tree |> member "value" |> to_list |> List.map ~f:(function - | `List [x; y] -> - (x |> parse_term |> object_key_of_term, y |> parse_term) - | _ -> failwith "ill-formed object")) + | `List [ x; y ] -> + (x |> parse_term |> object_key_of_term, y |> parse_term) + | _ -> failwith "ill-formed object")) | "arraycomprehension" -> - ArrayComprehension - (tree |> member "value" |> member "term" |> parse_term, - tree |> member "value" |> member "body" |> to_list |> List.map ~f:parse_literal) + ArrayComprehension + ( tree |> member "value" |> member "term" |> parse_term, + tree |> member "value" |> member "body" |> to_list + |> List.map ~f:parse_literal ) | "setcomprehension" -> - SetComprehension - (tree |> member "value" |> member "term" |> parse_term, - tree |> member "value" |> member "body" |> to_list |> List.map ~f:parse_literal) + SetComprehension + ( tree |> member "value" |> member "term" |> parse_term, + tree |> member "value" |> member "body" |> to_list + |> List.map ~f:parse_literal ) | "objectcomprehension" -> - ObjectComprehension - ((tree |> member "value" |> member "key" |> parse_term |> object_key_of_term, - tree |> member "value" |> member "value" |> parse_term), - tree |> member "value" |> member "body" |> to_list |> List.map ~f:parse_literal) - | "call" -> - (match tree |> member "value" |> to_list with + ObjectComprehension + ( ( tree |> member "value" |> member "key" |> parse_term + |> object_key_of_term, + tree |> member "value" |> member "value" |> parse_term ), + tree |> member "value" |> member "body" |> to_list + |> List.map ~f:parse_literal ) + | "call" -> ( + match tree |> member "value" |> to_list with | func :: args -> - Call (func |> member "value" |> to_list |> parse_ref, - List.map ~f:parse_term args) + Call + ( func |> member "value" |> to_list |> parse_ref, + List.map ~f:parse_term args ) | _ -> failwith "ill-formed call") | _ -> failwith ("unsupported term type " ^ term_type) and parse_literal tree : literal = let with_expr = tree |> member "with" in - let with_expr = match with_expr with + let with_expr = + match with_expr with | `Null -> None | `List xs -> - Some - (List.map xs ~f:(fun x -> (x |> member "target" |> parse_term, - x |> member "value" |> parse_term))) - | _ -> failwith ("ill-formed with expression " ^ (Yojson.Basic.to_string with_expr)) + Some + (List.map xs ~f:(fun x -> + ( x |> member "target" |> parse_term, + x |> member "value" |> parse_term ))) + | _ -> + failwith + ("ill-formed with expression " ^ Yojson.Basic.to_string with_expr) in match tree |> member "terms" with | `List (func :: args) -> - Expr (Term (Call (func |> member "value" |> to_list |> parse_ref, - List.map ~f:parse_term args)), - with_expr) + Expr + ( Term + (Call + ( func |> member "value" |> to_list |> parse_ref, + List.map ~f:parse_term args )), + with_expr ) | `List _ -> failwith "ill-formed call" | x -> - if not (x |> member "symbols" |> is_null) then - Exists (x |> member "symbols" - |> to_list - |> List.map ~f:(fun x -> Term (parse_term x)), - with_expr) - else if x |> member "domain" |> is_null then - Expr (Term (parse_term x), with_expr) - else - Expr (Every ((if x |> member "key" |> is_null then - None - else - Some (x |> member "key" |> member "value" |> to_string)), - x |> member "value" |> member "value" |> to_string, - x |> member "domain" |> parse_term, - (List.map ~f:parse_literal (x |> member "body" |> to_list))), - with_expr) + if not (x |> member "symbols" |> is_null) then + Exists + ( x |> member "symbols" |> to_list + |> List.map ~f:(fun x -> Term (parse_term x)), + with_expr ) + else if x |> member "domain" |> is_null then + Expr (Term (parse_term x), with_expr) + else + Expr + ( Every + ( (if x |> member "key" |> is_null then None + else Some (x |> member "key" |> member "value" |> to_string)), + x |> member "value" |> member "value" |> to_string, + x |> member "domain" |> parse_term, + List.map ~f:parse_literal (x |> member "body" |> to_list) ), + with_expr ) and parse_ref_target tree : ref_target = let term = parse_term tree in @@ -229,7 +232,7 @@ and parse_ref_target tree : ref_target = | ObjectComprehension (term, y) -> ObjectComprehension (term, y) | SetComprehension (term, y) -> SetComprehension (term, y) | Call (term, y) -> Call (term, y) - | _ -> failwith ("unsupported ref_target " ^ (show_term term)) + | _ -> failwith ("unsupported ref_target " ^ show_term term) and parse_ref tree = match tree with @@ -239,52 +242,56 @@ and parse_ref tree = let parse_head tree = (* Variables are desugared to empty references. *) let lhs = tree |> member "ref" |> to_list |> parse_ref in - let assign_operator = if tree |> member "assign" |> to_bool_or_false then - Assign - else - Unify in + let assign_operator = + if tree |> member "assign" |> to_bool_or_false then Assign else Unify + in let rhs = if not (tree |> member "key" |> is_null) then Set (tree |> member "key" |> parse_term) else if tree |> member "args" |> to_bool_or_false then - Function (assign_operator, - (tree |> member "args" |> to_list |> List.map ~f:(fun x -> (x |> member "value" |> to_string))), - (tree |> member "value" |> parse_term)) - else - Assignment (assign_operator, (tree |> member "value" |> parse_term)) - in (lhs, rhs) + Function + ( assign_operator, + tree |> member "args" |> to_list + |> List.map ~f:(fun x -> x |> member "value" |> to_string), + tree |> member "value" |> parse_term ) + else Assignment (assign_operator, tree |> member "value" |> parse_term) + in + (lhs, rhs) let rec parse_rule tree = - { default = tree |> member "default" |> to_bool_or_false; + { + default = tree |> member "default" |> to_bool_or_false; head = tree |> member "head" |> parse_head; body = List.map ~f:parse_literal (tree |> member "body" |> to_list_or_empty); otherwise = - match tree |> member "else" with + (match tree |> member "else" with | `Null -> None - | else_branch -> Some (parse_rule else_branch) + | else_branch -> Some (parse_rule else_branch)); } (* --- *) let parse_import_path tree = - match (tree |> member "type" |> to_string) with + match tree |> member "type" |> to_string with | "ref" -> tree |> member "value" |> to_list |> parse_ref | _ -> failwith "unimplemented" let parse_import tree = - { alias = tree |> member "alias" |> to_string_option; - path = tree |> member "path" |> parse_import_path + { + alias = tree |> member "alias" |> to_string_option; + path = tree |> member "path" |> parse_import_path; } (* --- *) -let parse_package tree = - tree |> member "path" |> to_list |> parse_ref +let parse_package tree = tree |> member "path" |> to_list |> parse_ref (* --- *) let parse_tree tree = - { path = tree |> member "package" |> parse_package; - imports = List.map ~f:parse_import (tree |> member "imports" |> to_list_or_empty); - policy = List.map ~f:parse_rule (tree |> member "rules" |> to_list_or_empty) + { + path = tree |> member "package" |> parse_package; + imports = + List.map ~f:parse_import (tree |> member "imports" |> to_list_or_empty); + policy = List.map ~f:parse_rule (tree |> member "rules" |> to_list_or_empty); } diff --git a/rego-proofs/compiler-rewrite/lib/compiler.mli b/rego-proofs/compiler-rewrite/lib/compiler.mli index 35b6ba1..b7b14dc 100644 --- a/rego-proofs/compiler-rewrite/lib/compiler.mli +++ b/rego-proofs/compiler-rewrite/lib/compiler.mli @@ -1,12 +1,16 @@ type environ + type expr = Term of term | Every of string option * string * term * query + and literal = - Exists of expr list * with_modifier option + | Exists of expr list * with_modifier option | Expr of expr * with_modifier option | Negate of expr * with_modifier option + and query = literal list + and term = - Scalar of scalar + | Scalar of scalar | Var of string | Ref of reference | Array of term list @@ -16,10 +20,12 @@ and term = | ObjectComprehension of (object_key * term) * query | SetComprehension of term * query | Call of reference * term list + and scalar = String of string | Number of float | Bool of bool | Null and reference = ref_target * term list + and ref_target = - Var of string + | Var of string | Array of term list | Object of (object_key * term) list | Set of term list @@ -27,26 +33,29 @@ and ref_target = | ObjectComprehension of (object_key * term) * query | SetComprehension of term * query | Call of reference * term list + and object_key = Scalar of scalar | Ref of reference | Var of string and with_modifier = (term * term) list + type assign_operator = Assign | Unify type rule_head_lhs = reference + type rule_head_rhs = - Assignment of assign_operator * term + | Assignment of assign_operator * term | Function of assign_operator * string list * term | Set of term + type rule_head = rule_head_lhs * rule_head_rhs + type rule = { default : bool; head : rule_head; body : query; otherwise : rule option; } -type import = { alias : string option; path : reference; } -type package = { - path : reference; - imports : import list; - policy : rule list; -} + +type import = { alias : string option; path : reference } +type package = { path : reference; imports : import list; policy : rule list } + val extract_local_variables_wrapper : query -> string list val parse_tree : Yojson.Basic.t -> package diff --git a/rego-proofs/compiler-rewrite/test/compiler_rewrite.ml b/rego-proofs/compiler-rewrite/test/compiler_rewrite.ml index e447473..e9484a6 100644 --- a/rego-proofs/compiler-rewrite/test/compiler_rewrite.ml +++ b/rego-proofs/compiler-rewrite/test/compiler_rewrite.ml @@ -4,24 +4,27 @@ module To_test = struct let extract_locals = Compiler_rewrite.Compiler.extract_local_variables_wrapper end -let strings = Alcotest.testable - (Format.pp_print_list Format.pp_print_string) - (List.equal String.equal) +let strings = + Alcotest.testable + (Format.pp_print_list Format.pp_print_string) + (List.equal String.equal) -let invoke ?(stdin="") ?(env=[| |]) cmd = - let ic, oc, ec = UnixLabels.open_process_full cmd ~env:env in - Out_channel.output_string oc stdin ; +let invoke ?(stdin = "") ?(env = [||]) cmd = + let ic, oc, ec = UnixLabels.open_process_full cmd ~env in + Out_channel.output_string oc stdin; Out_channel.close oc; - (In_channel.input_all ic, - In_channel.input_all ec) + (In_channel.input_all ic, In_channel.input_all ec) let rego_to_ast policy_code = - let (stdout, _) = invoke ("/home/jakob/.local/bin/opa parse -f json /dev/stdin") ~stdin:policy_code ~env:[| |] in + let stdout, _ = + invoke "/home/jakob/.local/bin/opa parse -f json /dev/stdin" + ~stdin:policy_code ~env:[||] + in Yojson.Basic.from_string stdout |> Compiler_rewrite.Compiler.parse_tree let extract_query policy = - match (rego_to_ast policy) with - | { policy = [{ body = body; _ }]; _ } -> body + match rego_to_ast policy with + | { policy = [ { body; _ } ]; _ } -> body | _ -> failwith "failed to parse" let test_local_extraction_simple_1 () = @@ -33,8 +36,7 @@ q { } |} in Alcotest.(check strings) - "expected identifier list" - ["x"] + "expected identifier list" [ "x" ] (To_test.extract_locals (extract_query policy_code)) let test_local_extraction_simple_2 () = @@ -48,8 +50,7 @@ q { } |} in Alcotest.(check strings) - "expected identifier list" - ["x"; "y"; "z"] + "expected identifier list" [ "x"; "y"; "z" ] (To_test.extract_locals (extract_query policy_code)) let test_local_dependent_on_previously_defined_local () = @@ -62,8 +63,7 @@ q { } |} in Alcotest.(check strings) - "expected identifier list" - ["x"; "y"] + "expected identifier list" [ "x"; "y" ] (To_test.extract_locals (extract_query policy_code)) let test_local_not_ground_because_of_ordering () = @@ -76,20 +76,26 @@ q { } |} in Alcotest.(check strings) - "expected identifier list" - ["x"] + "expected identifier list" [ "x" ] (To_test.extract_locals (extract_query policy_code)) - let () = let open Alcotest in run "Compiler" - [ "local extraction", [ - test_case "local extraction simple (1)" - `Quick test_local_extraction_simple_1; - test_case "local extraction simple (2)" - `Quick test_local_extraction_simple_2; - test_case "local extraction with local dependent on previously-defined local (1)" - `Quick test_local_dependent_on_previously_defined_local; - test_case "local extraction with local dependent on previously-defined local (2)" - `Quick test_local_not_ground_because_of_ordering ] ] + [ + ( "local extraction", + [ + test_case "local extraction simple (1)" `Quick + test_local_extraction_simple_1; + test_case "local extraction simple (2)" `Quick + test_local_extraction_simple_2; + test_case + "local extraction with local dependent on previously-defined local \ + (1)" + `Quick test_local_dependent_on_previously_defined_local; + test_case + "local extraction with local dependent on previously-defined local \ + (2)" + `Quick test_local_not_ground_because_of_ordering; + ] ); + ] |