hphp/hack/src/typing/typing_lenv.ml

   1   (**
   2  * Copyright (c) 2015, 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 Env = Typing_env
  13 open Env
  14 module TUtils = Typing_utils
  15 module Type = Typing_ops
  16 module Reason = Typing_reason
  17 module LMap = Local_id.Map
  18
  19 (*****************************************************************************)
  20 (* Module dealing with local environments. *)
  21 (*****************************************************************************)
  22
  23 let equiv env ty1 ty2 =
  24    let _, ety1 = expand_type env ty1 in
  25    let _, ety2 = expand_type env ty2 in
  26    Typing_defs.ty_equal ety1 ety2
  27
  28 (*****************************************************************************)
  29 (* Functions dealing with old style local environment *)
  30 (*****************************************************************************)
  31
  32 (* Intersects the set of valid fake_members.
  33  * Fake members are introduced when we know that a member is not null.
  34  * Example: if($this->x) { ... $this->x is a fake member now ... }
  35  * What it means in practice is that the member behaves like a local, it can
  36  * change type.
  37  *)
  38 let intersect_fake fake1 fake2 =
  39   let valid = SSet.inter fake1.Env.valid fake2.Env.valid in
  40   let fake_members = { fake1 with Env.valid = valid } in
  41   fake_members
  42
  43 (* Used when we want the new local environment to be the intersection
  44  * of 2 local environments. Typical use case is an if statement.
  45  * $x = 0;
  46  * if(...) { $x = ''; } else { $x = 'foo'; }
  47  * We want $x to be a string past this point.
  48  * The intersection checks that the locals are defined in both branches
  49  * when that is the case, their type becomes:
  50  * Tunresolved [type_in_the_left_branch; type_in_the_right_branch].
  51  * If the type is missing in either of the branches, we fall back on
  52  * the type that was defined in the parent environment.
  53  *)
  54 let intersect env parent_lenv lenv1 lenv2 =
  55   let fake_members = intersect_fake lenv1.fake_members lenv2.fake_members in
  56   let local_using_vars = parent_lenv.local_using_vars in
  57   let tpenv = env.lenv.tpenv in
  58   let lenv1_locals_with_hist = Env.merge_locals_and_history lenv1 in
  59   let lenv2_locals_with_hist = Env.merge_locals_and_history lenv2 in
  60   let parent_locals_with_hist = Env.merge_locals_and_history parent_lenv in
  61   let local_mutability = Typing_mutability_env.intersect_mutability
  62     parent_lenv.local_mutability lenv1.local_mutability lenv2.local_mutability in
  63   let local_reactive = parent_lenv.local_reactive in
  64   let env, new_locals =
  65     LMap.fold begin fun local_id (all_types1, ty1, eid1) (env, locals) ->
  66       match LMap.get local_id lenv2_locals_with_hist with
  67       | None -> env, locals
  68       | Some (all_types2, ty2, eid2) ->
  69           (* If the local has different expression ids then we generate a
  70            * new one when intersecting
  71            *)
  72           let eid = if eid1 = eid2 then eid1 else Ident.tmp() in
  73           let (all_small, all_large) =
  74             if List.length all_types1 < List.length all_types2
  75             then (all_types1, all_types2)
  76             else (all_types2, all_types1) in
  77           let all_types =
  78             List.fold_left ~f:begin fun acc ty ->
  79               if List.exists acc (equiv env ty) then acc else ty::acc
  80             end ~init:all_large all_small in
  81           let env, ty =
  82             if Typing_defs.ty_equal ty1 ty2
  83             then env, ty1
  84             else
  85               let env, ty1 = TUtils.unresolved env ty1 in
  86               let env, ty2 = TUtils.unresolved env ty2 in
  87               Type.unify env.Env.pos Reason.URnone env ty1 ty2 in
  88           env, LMap.add local_id (all_types, ty, eid) locals
  89     end lenv1_locals_with_hist (env, parent_locals_with_hist)
  90   in
  91   let locals, history = Env.separate_locals_and_history new_locals in
  92   { env with Env.lenv =
  93     { fake_members;
  94       local_types = locals;
  95       local_type_history = history;
  96       local_using_vars;
  97       tpenv;
  98       local_mutability;
  99       local_reactive;
 100     }
 101   }
 102
 103 (* Integration is subtle. It consists in remembering all the types that
 104  * a local has had in a branch.
 105  * We need to keep this information because of constructions that disrupt
 106  * the control flow.
 107  * Example:
 108  * if(...) {
 109  *   $x = 0;
 110  * }
 111  * else {
 112  *   $x = '';
 113  *   throw new Exception('');
 114  * }
 115  * At this point, $x is an int, because the else branch is terminal.
 116  * But we still 'integrate the branch', that is, we remember that $x can have
 117  * type int OR string.
 118  * The integration will become useful on a try:
 119  * try {
 120  *   if(...) {
 121  *     $x = 0;
 122  *   }
 123  *   else {
 124  *     $x = '';
 125  *     throw new Exception('');
 126  *   }
 127  * }
 128  * catch(Exception $e) {
 129  *   What is the type of $x? <-----------------------------
 130  * }
 131  * You can see that we will need the types collected during the integration.
 132  * Because we collected all the possible types taken by $x, we can build the
 133  * local environment where $x is of type Tunresolved[int, string].
 134  * The conservative local environment is built with fully_integrate.
 135  *)
 136 let integrate env parent_lenv child_lenv =
 137   let local_using_vars = parent_lenv.local_using_vars in
 138   let parent_locals_with_hist = Env.merge_locals_and_history parent_lenv in
 139   let child_locals_with_hist = Env.merge_locals_and_history child_lenv in
 140   let new_locals =
 141     LMap.fold begin fun local_id (child_all_types, child_ty, child_eid) locals ->
 142       match LMap.get local_id locals with
 143       | None ->
 144           LMap.add local_id (child_all_types, child_ty, child_eid) locals
 145       | Some (parent_all_types, _, parent_eid)
 146             when child_all_types == parent_all_types ->
 147           let eid = if child_eid = parent_eid then child_eid else Ident.tmp() in
 148           LMap.add local_id (child_all_types, child_ty, eid) locals
 149       | Some (parent_all_types, _, parent_eid) ->
 150           let eid = if child_eid = parent_eid then child_eid else Ident.tmp() in
 151           let all_types = List.fold_left ~f:begin fun all_types ty ->
 152             if List.exists all_types (equiv env ty) then all_types else ty::all_types
 153           end ~init:child_all_types parent_all_types in
 154           LMap.add local_id (all_types, child_ty, eid) locals
 155     end child_locals_with_hist parent_locals_with_hist
 156   in
 157   let locals, history = Env.separate_locals_and_history new_locals in
 158   { env with Env.lenv =
 159     { fake_members = child_lenv.fake_members;
 160       local_types = locals;
 161       local_type_history = history;
 162       local_using_vars;
 163       tpenv = env.lenv.tpenv;
 164       (* The mutability of the entire block is always that of the child *)
 165       local_mutability = child_lenv.local_mutability;
 166       (* always grab reactive context from child *)
 167       local_reactive = child_lenv.local_reactive;
 168     }
 169   }
 170
 171 let integrate_list env parent_lenv lenv_l =
 172   List.fold lenv_l ~init:env ~f:(fun env lenv -> integrate env parent_lenv lenv)
 173
 174 (* Same as intersect, but with a list of local environments *)
 175 let intersect_list env parent_lenv lenv_l =
 176   match lenv_l with
 177   | [] -> env
 178   | [x] -> { env with Env.lenv = x }
 179   | lenv1 :: rl ->
 180     List.fold rl
 181       ~init:{ env with Env.lenv = lenv1 }
 182       ~f:(fun env lenv2 -> intersect env parent_lenv env.Env.lenv lenv2)
 183
 184 (* Similar to intersect_list, but lenvs from terminal branches are integrated
 185  * instead of intersected (so that the locals history from terminal branches is
 186  * remembered, but terminal branches do not contribute to the intersected types
 187  * of locals).
 188  *)
 189 let intersect_nonterminal_branches env parent_lenv term_lenv_l =
 190   let to_integrate, to_intersect =
 191     List.partition_map term_lenv_l begin fun (term, lenv) ->
 192       if term then `Fst lenv else `Snd lenv
 193     end in
 194   let env = integrate_list env parent_lenv to_integrate in
 195   intersect_list env parent_lenv to_intersect
 196
 197 (* Function that changes the types of locals to a more conservative value.
 198  * When exiting from a construction that could have disrupted the
 199  * "natural" control-flow, we need to be more conservative with the
 200  * values of locals (cf: integrate).
 201  *)
 202 let fully_integrate env parent_lenv =
 203   let local_using_vars = parent_lenv.local_using_vars in
 204   let child_lenv = env.Env.lenv in
 205   let parent_locals_with_hist = Env.merge_locals_and_history parent_lenv in
 206   let child_locals_with_hist = Env.merge_locals_and_history child_lenv in
 207   let fake_members =
 208     intersect_fake parent_lenv.fake_members child_lenv.fake_members in
 209   let env, new_locals =
 210     LMap.fold begin fun local_id (child_all_types,_, child_eid) (env, locals) ->
 211       let parent_all_types, parent_eid =
 212         match LMap.get local_id parent_locals_with_hist with
 213         | None -> [], -1
 214         | Some (parent_all_types, _, parent_eid) ->
 215             parent_all_types, parent_eid
 216       in
 217       if child_all_types == parent_all_types && parent_eid = child_eid
 218       then env, locals
 219       else if child_all_types == parent_all_types
 220       then
 221         match LMap.get local_id parent_locals_with_hist with
 222         | None -> env, locals
 223         | Some (_, parent_ty, _) ->
 224             let lcl = parent_all_types, parent_ty, Ident.tmp() in
 225             env, LMap.add local_id lcl locals
 226       else
 227         let eid = if child_eid = parent_eid then child_eid else Ident.tmp() in
 228         let env, ty =
 229           match child_all_types with
 230           | [] -> assert false
 231           | [first] -> env, first
 232           | first :: rest ->
 233               let env, first = TUtils.unresolved env first in
 234               let env, rest = List.map_env env rest TUtils.unresolved in
 235               List.fold_left ~f:begin fun (env, ty_acc) ty ->
 236                 Type.unify env.Env.pos Reason.URnone env ty_acc ty
 237               end ~init:(env, first) rest
 238         in
 239         let parent_all_types =
 240           if List.exists parent_all_types (equiv env ty)
 241           then parent_all_types
 242           else ty :: parent_all_types in
 243         env, LMap.add local_id (parent_all_types, ty, eid) locals
 244     end child_locals_with_hist (env, parent_locals_with_hist)
 245   in
 246   let locals, history = Env.separate_locals_and_history new_locals in
 247   { env with Env.lenv =
 248     { fake_members;
 249       local_types = locals;
 250       local_type_history = history;
 251       local_using_vars;
 252       tpenv = child_lenv.tpenv;
 253       local_mutability = child_lenv.local_mutability;
 254       local_reactive = child_lenv.local_reactive;
 255       } }
 256
 257 let env_with_empty_fakes env =
 258   { env with Env.lenv = {
 259       env.Env.lenv with Env.fake_members = Env.empty_fake_members;
 260     }
 261   }