hphp/hack/src/hhbc/jump_targets.ml

   1 (**
   2  * Copyright (c) 2017, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under the MIT license found in the
   6  * LICENSE file in the "hack" directory of this source tree.
   7  *
   8 *)
   9
  10 open Hh_core
  11
  12 module A = Ast
  13
  14 let labels_in_function_: (bool SMap.t) ref = ref SMap.empty
  15 let function_has_goto_ = ref false
  16
  17 let get_labels_in_function () = !labels_in_function_
  18 let get_function_has_goto () = !function_has_goto_
  19
  20 let set_labels_in_function s = labels_in_function_ := s
  21 let set_function_has_goto f = function_has_goto_ := f
  22
  23 let rec collect_valid_target_labels_aux is_hh_file acc s =
  24   match snd s with
  25   | A.Declare (_, _, block)
  26   | A.Block block ->
  27     collect_valid_target_labels_for_block_aux is_hh_file acc block
  28   (* can jump into the try block but not to finally *)
  29   | A.Try (block, cl, _) ->
  30     let acc = collect_valid_target_labels_for_block_aux is_hh_file acc block in
  31     List.fold_left cl
  32       ~init:acc
  33       ~f:(fun acc (_, _, block) ->
  34         collect_valid_target_labels_for_block_aux is_hh_file acc block)
  35   | A.GotoLabel (_, s) ->
  36     SSet.add s acc
  37   | A.If (_, then_block, else_block) ->
  38     let acc = collect_valid_target_labels_for_block_aux is_hh_file acc then_block in
  39     collect_valid_target_labels_for_block_aux is_hh_file acc else_block
  40   | A.Let _
  41   | A.Unsafe
  42   | A.Fallthrough
  43   | A.Expr _
  44   | A.Break _
  45   | A.Continue _
  46   | A.Throw _
  47   | A.Return _
  48   | A.Goto _
  49   | A.Static_var _
  50   | A.Global_var _
  51   | A.Markup _
  52   | A.Noop
  53   | A.Foreach _
  54   | A.Do _
  55   | A.For _
  56   | A.Def_inline _ -> acc
  57   (* jump to while loops/switches/usings are disallowed in php files
  58      and permitted in hh - assuming that they can only appear there
  59      as a result of source to source transformation that has validated
  60      correctness of the target *)
  61   | A.While (_, block)
  62   | A.Using { A.us_block = block; _ } ->
  63     if is_hh_file
  64     then collect_valid_target_labels_for_block_aux is_hh_file acc block
  65     else acc
  66   | A.Switch (_, cl) ->
  67     if is_hh_file
  68     then collect_valid_target_labels_for_switch_cases_aux is_hh_file acc cl
  69     else acc
  70
  71 and collect_valid_target_labels_for_block_aux is_hh_file acc block =
  72   List.fold_left block ~init:acc ~f:(collect_valid_target_labels_aux is_hh_file)
  73
  74 and collect_valid_target_labels_for_switch_cases_aux is_hh_file acc cl =
  75   List.fold_left cl ~init:acc ~f:(fun acc s ->
  76     match s with
  77     | A.Default block
  78     | A.Case (_, block) -> collect_valid_target_labels_for_block_aux is_hh_file acc block)
  79
  80 let rec collect_valid_target_labels_for_def_aux is_hh_file acc def =
  81   match def with
  82   | A.Stmt s -> collect_valid_target_labels_aux is_hh_file acc s
  83   | A.Namespace (_, defs) -> collect_valid_target_labels_for_defs_aux is_hh_file acc defs
  84   | _ -> acc
  85 and collect_valid_target_labels_for_defs_aux is_hh_file acc defs =
  86   List.fold_left defs ~init:acc ~f:(collect_valid_target_labels_for_def_aux is_hh_file)
  87
  88 let collect_valid_target_labels_for_stmt is_hh_file s =
  89   if not (!function_has_goto_) then SSet.empty
  90   else collect_valid_target_labels_aux is_hh_file SSet.empty s
  91
  92 let collect_valid_target_labels_for_defs is_hh_file defs =
  93   if not (!function_has_goto_) then SSet.empty
  94   else collect_valid_target_labels_for_defs_aux is_hh_file SSet.empty defs
  95
  96 let collect_valid_target_labels_for_switch_cases is_hh_file cl =
  97   if not (!function_has_goto_) then SSet.empty
  98   else collect_valid_target_labels_for_switch_cases_aux is_hh_file SSet.empty cl
  99
 100 type iterator = (*is mutable*) bool * Iterator.t
 101
 102 type loop_labels =
 103 { label_break: Label.t
 104 ; label_continue: Label.t
 105 ; iterator: iterator option
 106 }
 107
 108 type region =
 109   | Loop of loop_labels * SSet.t
 110   | Switch of (*end switch*) Label.t * SSet.t
 111   | TryFinally of (*finally start*) Label.t * SSet.t
 112   | Finally of SSet.t
 113   | Function of SSet.t
 114   | Using of (*finally start*) Label.t * SSet.t
 115
 116 type t = region list
 117
 118 let empty = []
 119
 120 type id_key = IdReturn | IdLabel of Label.t
 121 module LabelIdMap: MyMap.S with type key = id_key = MyMap.Make(struct
 122   type t = id_key
 123   let compare = Pervasives.compare
 124 end)
 125
 126 (* HHVM assigns ids to labels sequentially as break/continue to labels appear
 127    in the source code. When emitter is done with scope that contains
 128    break/continue - label ids associated with the scope are freed and can be reused.
 129    One exception from the rule is return - it is treated as if it is  jump to a label that
 130   finishes the function so once id for return is assigned - it is never released.
 131   Label ids are used in finally epilogue to determine how control flow got into
 132   the finally body.
 133
 134   while (true) {
 135     try {
 136       if ($a) { continue; }
 137       if ($b) { return 100; }
 138     }
 139     finally {
 140       print "finally";
 141     }
 142   }
 143
 144   will be emitted roughly as:
 145
 146   While_Start:
 147     CGetL $a
 148     JmpZ L1
 149
 150     Int 0 ; push id of the target label "continue label for while loop"
 151     SetL _1; save it in dedicated local
 152     PopC
 153     Jmp FinallyStart:
 154
 155   L1:
 156     CGetL $b
 157     JmpZ FinallyStart
 158     Int 100 ; push return value
 159     Int 1; push id of the 'return' label
 160     SetL _1; save id in decicated local
 161     PopC
 162     SetL _2; save return value in dedicated local
 163     PopC
 164     Jmp FinallyStart
 165
 166   FinallyStart:
 167     String "finally"
 168     Print
 169     PopC
 170     IssetL _1; if check if state local is set
 171     JmpZ FinallyEnd
 172     CGetL _1; load state
 173     Switch Unbounded 0 <Case0 Case1>
 174
 175   Case0:
 176     UnsetL _1; new iteration - clean local for state id
 177     Jmp FinallyEnd
 178   Case1:
 179     CGetL _2; load return value
 180     RetC
 181
 182   FinallyEnd:
 183     Jmp White_Start
 184   *)
 185 let label_to_id = ref LabelIdMap.empty
 186
 187 let new_id k =
 188   match LabelIdMap.get k !label_to_id with
 189   | Some id -> id
 190   | None ->
 191   let rec aux n =
 192     if LabelIdMap.exists (fun _ id -> n = id) !label_to_id then aux (n + 1)
 193     else (label_to_id := LabelIdMap.add k n !label_to_id; n)
 194   in aux 0
 195
 196 let reset () =
 197   label_to_id := LabelIdMap.empty
 198
 199 let get_id_for_return () = new_id IdReturn
 200 let get_id_for_label l = new_id (IdLabel l)
 201
 202 let release_id l =
 203   label_to_id := LabelIdMap.remove (IdLabel l) !label_to_id
 204
 205 (* runs a given function and then released label ids that were possibly assigned
 206    to labels at the head of the list *)
 207 let run_and_release_ids _labels f s t =
 208   let r = f t s in
 209   begin match t with
 210   | Loop ({ label_break; label_continue; _ }, _) ::_ ->
 211     release_id label_break;
 212     release_id label_continue;
 213   | (Switch (l, _) | TryFinally (l, _) | Using (l, _)) :: _ ->
 214     release_id l
 215   | (Function _ | Finally _) :: _ -> ()
 216   | [] -> failwith "impossible"
 217   end;
 218   (* CONSIDER: now HHVM does not release state ids for named labels
 219      even after leaving the scope where labels are accessible
 220      Do the same for now for compatibility reasons *)
 221   (* SSet.iter (fun l -> release_id (Label.Named l)) labels; *)
 222   r
 223
 224 let with_loop is_hh_file label_break label_continue iterator t s f =
 225   let labels = collect_valid_target_labels_for_stmt is_hh_file s in
 226   Loop ({ label_break; label_continue; iterator }, labels) :: t
 227   |> run_and_release_ids labels f s
 228
 229 let with_switch is_hh_file end_label t cl f =
 230   let labels = collect_valid_target_labels_for_switch_cases is_hh_file cl in
 231   (* CONSIDER: now HHVM eagerly reserves state id for the switch end label
 232     which does not seem to be necessary - do it for now for HHVM compatibility *)
 233   let _ = get_id_for_label end_label in
 234   Switch (end_label, labels) :: t
 235   |> run_and_release_ids labels f ()
 236
 237 let with_try is_hh_file finally_label t s f =
 238   let labels = collect_valid_target_labels_for_stmt is_hh_file s in
 239   TryFinally (finally_label, labels) :: t
 240   |> run_and_release_ids labels f s
 241
 242 let with_finally is_hh_file t s f =
 243   let labels = collect_valid_target_labels_for_stmt is_hh_file s in
 244   Finally labels :: t
 245   |> run_and_release_ids labels f s
 246
 247 let with_function is_hh_file t s f =
 248   let labels = collect_valid_target_labels_for_defs is_hh_file s in
 249   Function labels :: t
 250   |> run_and_release_ids labels f s
 251
 252 let with_using is_hh_file finally_label t s f =
 253   let labels = collect_valid_target_labels_for_stmt is_hh_file s in
 254   Using (finally_label, labels) :: t
 255   |> run_and_release_ids labels f s
 256
 257 type resolved_try_finally =
 258 { target_label: Label.t
 259 ; finally_label: Label.t
 260 ; adjusted_level: int
 261 ; iterators_to_release: iterator list
 262 }
 263
 264 type resolved_jump_target =
 265   | NotFound
 266   | ResolvedTryFinally of resolved_try_finally
 267   | ResolvedRegular of Label.t * iterator list
 268
 269 let add_iterator it_opt iters =
 270   Option.value_map it_opt ~default:iters ~f:(fun v -> v :: iters)
 271
 272 (* Tries to find a target label given a level and a jump kind (break or continue) *)
 273 let get_target_for_level ~is_break level t =
 274   (* skip_try_finally is true if we've already determined that we need to jump out of
 275      finally and now we are looking for the actual target label (break label of the
 276      while loop in the example below: )
 277
 278      while (1) {
 279         try {
 280            break;
 281         }
 282         finally {
 283            ...
 284         }
 285      }
 286     *)
 287   let rec aux ~skip_try_finally n l iters =
 288     match l with
 289     | [] | Function _ :: _ ->
 290       (* looked through the entires list of jump targets and still cannot find a
 291          target for a requested level - bad luck *)
 292       NotFound
 293     | (Using (finally_label, _) | TryFinally (finally_label, _)) :: tl ->
 294       if skip_try_finally then aux ~skip_try_finally n tl iters
 295       else
 296       (* we need to jump out of try body in try/finally - in order to do this
 297          we should go through the finally block first.*)
 298       (* try to final target label where we would've jumped if there were no finally blocks *)
 299       let result = aux ~skip_try_finally:true n tl iters in
 300       begin match result with
 301       | NotFound -> NotFound
 302       | ResolvedRegular (target_label, _) ->
 303         ResolvedTryFinally
 304           { target_label = target_label
 305           ; finally_label
 306           ; adjusted_level = n
 307           ; iterators_to_release = iters }
 308       | _ -> failwith "impossible: TryFinally should be skipped"
 309       end
 310     | Switch (end_label, _) :: _ when n = 1 -> ResolvedRegular (end_label, iters)
 311     | Loop ({ label_break; label_continue; iterator }, _) :: _ when n = 1 ->
 312         let label, iters =
 313           if is_break then label_break, add_iterator iterator iters
 314           else label_continue, iters
 315         in
 316         ResolvedRegular (label, iters)
 317     | Loop ({ iterator; _ }, _) :: tl ->
 318       aux ~skip_try_finally (n - 1) tl (add_iterator iterator iters)
 319     | Switch _ :: tl ->
 320       aux ~skip_try_finally (n - 1) tl iters
 321     | Finally _ :: _ ->
 322       (* jumps out of finally body are disallowed *)
 323       NotFound
 324   in
 325   aux ~skip_try_finally:false level t []
 326
 327 let get_closest_enclosing_finally_label t =
 328   let rec aux l iters =
 329     match l with
 330     | [] -> None
 331     | (Using (l, _) | TryFinally (l, _)) :: _ -> Some (l, iters)
 332     | Loop ({ iterator; _ }, _) :: tl -> aux tl (add_iterator iterator iters)
 333     | _ :: tl -> aux tl iters
 334   in aux t []
 335
 336 let collect_iterators t =
 337   List.filter_map t ~f:(function | Loop ({ iterator; _ }, _) -> iterator | _ -> None)
 338
 339 type resolved_goto_finally = {
 340   rgf_finally_start_label: Label.t;
 341   rgf_iterators_to_release: iterator list
 342 }
 343
 344 type resolved_goto_target =
 345   | ResolvedGoto_label of iterator list
 346   | ResolvedGoto_finally of resolved_goto_finally
 347   | ResolvedGoto_goto_from_finally
 348   | ResolvedGoto_goto_invalid_label
 349
 350 let find_goto_target t label =
 351   let rec aux t iters =
 352     match t with
 353     | Loop ({ iterator; _ }, labels) :: tl ->
 354       if SSet.mem label labels then ResolvedGoto_label iters
 355       else aux tl (add_iterator iterator iters)
 356     | Switch (_, labels) :: tl ->
 357       if SSet.mem label labels then ResolvedGoto_label iters
 358       else aux tl iters
 359     | (Using (finally_start, labels) | TryFinally (finally_start, labels)) :: _ ->
 360       if SSet.mem label labels then ResolvedGoto_label iters
 361       else ResolvedGoto_finally {
 362         rgf_finally_start_label = finally_start;
 363         rgf_iterators_to_release = iters }
 364     | Finally labels :: _ ->
 365       if SSet.mem label labels then ResolvedGoto_label iters
 366       else ResolvedGoto_goto_from_finally
 367     | Function labels :: _  ->
 368       if SSet.mem label labels then ResolvedGoto_label iters
 369       else ResolvedGoto_goto_invalid_label
 370     | [] -> failwith "impossible" in
 371   aux t []