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