Skip to content

Commit 101d324

Browse files
andrewjkennedyfredemmott
andrewjkennedy
authored and
fredemmott
committed
Fix type checker crash caused by large number of uses of Shape::keyExists
Summary: After a conditional we create a "union" of types. These can grow very large e.g. with shape refinement, as in this example: ``` type example_shape = shape( ?'example_1' => int, ?'example_2' => int, ?'example_3' => int, ?'example_4' => int, ?'example_5' => int, ); function takes_example_shape(example_shape $in): string { if (Shapes::keyExists($in, 'example_1')) { ... } if (Shapes::keyExists($in, 'example_2')) { ... } if (Shapes::keyExists($in, 'example_3')) { ... } if (Shapes::keyExists($in, 'example_4')) { ... } if (Shapes::keyExists($in, 'example_5')) { ... } ... ``` Eventually, Hack crashes. The crux of the problem is the "union" operation on locals that takes one very large shape type of the form `shape(?'x' => t, <more stuff>)` and computes the union with another very large shape type `shape('x' => t, <more stuff>)`. Spot the difference: just the `?`. In fact, the latter type is a subtype of the former, so the union is equivalent just to the former type. The fix is to avoid constructing an explicit union if one type is a subtype of the other. To do this, we adapt the `simplify_subtype` function to construct a helper function `is_sub_type_alt` that returns `Some b` if one type is definitely a subtype, or definitely *not* a subtype of the other, and returns `None` if it doesn't know. (There is already an `is_sub_type` function but it's quite hacky and we want to move to a more careful approach that doesn't "force" a subtype, or generate errors and then back off). Part of the diff involves changing `simplify_subtype` and helpers so that it doesn't generate errors. Fixes #8249 Reviewed By: manzyuk Differential Revision: D8731917 fbshipit-source-id: 753ddd507ad7f918c6648825a7ab1f4901044f2a
1 parent 1ec607a commit 101d324

13 files changed

Lines changed: 166 additions & 53 deletions

‎hphp/hack/src/typing/typing_lenv.ml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,10 @@ let intersect env parent_lenv lenv1 lenv2 =
8181
let env, ty =
8282
if Typing_defs.ty_equal ty1 ty2
8383
then env, ty1
84+
else if Typing_subtype.is_sub_type_alt env ty1 ty2 = Some true
85+
then env, ty2
86+
else if Typing_subtype.is_sub_type_alt env ty2 ty1 = Some true
87+
then env, ty1
8488
else
8589
let env, ty1 = TUtils.unresolved env ty1 in
8690
let env, ty2 = TUtils.unresolved env ty2 in

‎hphp/hack/src/typing/typing_subtype.ml‎

Lines changed: 37 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ module Phase = Typing_phase
4444
*)
4545
type simplification_result = {
4646
constraints: (locl ty * Ast.constraint_kind * locl ty) list;
47-
failed_subtype: (locl ty * locl ty) option;
47+
failed_subtype: (locl ty * locl ty * (unit -> unit)) option;
4848
}
4949

5050
let rec simplify_subtype
@@ -66,9 +66,12 @@ let rec simplify_subtype
6666
let again env res ty_sub =
6767
simplify_subtype ~deep ~this_ty ty_sub ty_super (env, res) in
6868
(* We *know* that the assertion is unsatisfiable *)
69-
let invalid () =
70-
(env, { constraints = acc; failed_subtype = Some (ety_sub, ety_super) }) in
71-
(* We *know* that the assertion is valid *)
69+
let invalid_with f =
70+
(env, { constraints = acc; failed_subtype = Some (ety_sub, ety_super, f) }) in
71+
let invalid () =
72+
invalid_with (fun () ->
73+
TUtils.uerror (fst ety_super) (snd ety_super) (fst ety_sub) (snd ety_sub)) in
74+
(* We *know* that the assertion is valid *)
7275
let valid () =
7376
res in
7477
(* We don't know whether the assertion is valid or not *)
@@ -267,11 +270,10 @@ let rec simplify_subtype
267270
| true, _ | false, false ->
268271
simplify_subtype ~deep ~this_ty ty_sub ty_super res
269272
| false, true ->
270-
Errors.required_field_is_optional
273+
invalid_with (fun () -> Errors.required_field_is_optional
271274
(Reason.to_pos r_sub)
272275
(Reason.to_pos r_super)
273-
(Env.get_shape_field_name name);
274-
invalid () in
276+
(Env.get_shape_field_name name)) in
275277
let on_missing_omittable_optional_field res _ _ = res in
276278
let on_missing_non_omittable_optional_field
277279
res name { sft_ty = ty_super; _ } =
@@ -285,6 +287,7 @@ let rec simplify_subtype
285287
~on_common_field
286288
~on_missing_omittable_optional_field
287289
~on_missing_non_omittable_optional_field
290+
~on_error:(fun _ f -> invalid_with f)
288291
res
289292
(r_super, fields_known_super, fdm_super)
290293
(r_sub, fields_known_sub, fdm_sub)
@@ -315,17 +318,18 @@ let rec simplify_subtype
315318
default ()
316319

317320
| Some class_sub ->
318-
let ety_env =
319-
(* We handle the case where a generic A<T> is used as A *)
320-
let tyl_sub =
321-
if tyl_sub = [] && not (Env.is_strict env)
322-
then List.map class_sub.tc_tparams (fun _ -> (p_sub, Tany))
323-
else tyl_sub
324-
in
325-
if List.length class_sub.tc_tparams <> List.length tyl_sub
326-
then
327-
Errors.expected_tparam
328-
(Reason.to_pos p_sub) (List.length class_sub.tc_tparams);
321+
(* We handle the case where a generic A<T> is used as A *)
322+
let tyl_sub =
323+
if tyl_sub = [] && not (Env.is_strict env)
324+
then List.map class_sub.tc_tparams (fun _ -> (p_sub, Tany))
325+
else tyl_sub in
326+
if List.length class_sub.tc_tparams <> List.length tyl_sub
327+
then
328+
invalid_with (fun () ->
329+
Errors.expected_tparam
330+
(Reason.to_pos p_sub) (List.length class_sub.tc_tparams))
331+
else
332+
let ety_env =
329333
(* NOTE: We rely on the fact that we fold all ancestors of
330334
* ty_sub in its class_type so we will never hit this case
331335
* again. If this ever changes then we would need to store
@@ -1126,8 +1130,8 @@ and sub_type_unwrapped
11261130
simplify_subtype ~deep:false ~this_ty ty_sub ty_super
11271131
(env, { constraints = []; failed_subtype = None }) in
11281132
match failed_subtype with
1129-
| Some (ty_sub, ty_super) ->
1130-
TUtils.uerror (fst ty_super) (snd ty_super) (fst ty_sub) (snd ty_sub);
1133+
| Some (_ty_sub, _ty_super, f) ->
1134+
f ();
11311135
env
11321136
| None ->
11331137
List.fold_right ~f:(fun (ty1,ck,ty2) env ->
@@ -1672,6 +1676,19 @@ and sub_string
16721676
| Ttuple _ | Tanon (_, _) | Tfun _ | Tshape _) ->
16731677
fst (Unify.unify env (Reason.Rwitness p, Tprim Nast.Tstring) ty2)
16741678

1679+
(* Non-side-effecting test for subtypes, using simplify_subtype.
1680+
* Result is
1681+
* result = Some true implies ty1 <: ty2
1682+
* result = Some false implies NOT ty1 <: ty2
1683+
* result = None, we don't know
1684+
*)
1685+
let is_sub_type_alt env ty1 ty2 =
1686+
match simplify_subtype ~deep:true ~this_ty:(Some ty1) ty1 ty2
1687+
(env, { constraints = []; failed_subtype = None }) with
1688+
| _, { constraints = []; failed_subtype = None } -> Some true
1689+
| _, { constraints = _; failed_subtype = Some _ }-> Some false
1690+
| _ -> None
1691+
16751692
(*****************************************************************************)
16761693
(* Exporting *)
16771694
(*****************************************************************************)

‎hphp/hack/src/typing/typing_unify.ml‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -378,13 +378,15 @@ and unify_ ?(opts=TUtils.default_unify_opt) env r1 ty1 r2 ty2 =
378378
~on_missing_non_omittable_optional_field:(
379379
on_missing_non_omittable_optional_field p2
380380
)
381+
~on_error:(fun x f -> f (); x)
381382
(env, res) (r1, fields_known1, fdm1) (r2, fields_known2, fdm2) in
382383
let env, res = TUtils.apply_shape
383384
~on_common_field
384385
~on_missing_omittable_optional_field
385386
~on_missing_non_omittable_optional_field:(
386387
on_missing_non_omittable_optional_field p1
387388
)
389+
~on_error:(fun x f -> f (); x)
388390
(env, res) (r2, fields_known2, fdm2) (r1, fields_known1, fdm1) in
389391
(* After doing apply_shape in both directions we can be sure that
390392
* fields_known1 = fields_known2 *)

‎hphp/hack/src/typing/typing_utils.ml‎

Lines changed: 17 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -352,39 +352,42 @@ let apply_shape
352352
~on_common_field
353353
~on_missing_omittable_optional_field
354354
~on_missing_non_omittable_optional_field
355+
~on_error
355356
(env, acc)
356357
(r1, fields_known1, fdm1)
357358
(r2, fields_known2, fdm2) =
359+
let (env, acc) =
358360
begin match fields_known1, fields_known2 with
359361
| FieldsFullyKnown, FieldsFullyKnown ->
360362
(* If both shapes are FieldsFullyKnown, then we must ensure that the
361363
supertype shape knows about every single field that could possibly
362364
be present in the subtype shape. *)
363-
ShapeMap.iter begin fun name _ ->
365+
ShapeMap.fold begin fun name _ (env, acc) ->
364366
if not @@ ShapeMap.mem name fdm1 then
365367
let pos1 = Reason.to_pos r1 in
366368
let pos2 = Reason.to_pos r2 in
367-
Errors.unknown_field_disallowed_in_shape
369+
on_error (env,acc) (fun () -> Errors.unknown_field_disallowed_in_shape
368370
pos1
369371
pos2
370-
(get_printable_shape_field_name name)
371-
end fdm2
372+
(get_printable_shape_field_name name))
373+
else (env, acc)
374+
end fdm2 (env, acc)
372375
| FieldsFullyKnown, FieldsPartiallyKnown _ ->
373376
let pos1 = Reason.to_pos r1 in
374377
let pos2 = Reason.to_pos r2 in
375-
Errors.shape_fields_unknown pos2 pos1
378+
on_error (env, acc) (fun () -> Errors.shape_fields_unknown pos2 pos1)
376379
| FieldsPartiallyKnown unset_fields1,
377380
FieldsPartiallyKnown unset_fields2 ->
378-
ShapeMap.iter begin fun name unset_pos ->
381+
ShapeMap.fold begin fun name unset_pos (env, acc) ->
379382
match ShapeMap.get name unset_fields2 with
380-
| Some _ -> ()
383+
| Some _ -> (env, acc)
381384
| None ->
382385
let pos2 = Reason.to_pos r2 in
383-
Errors.shape_field_unset unset_pos pos2
384-
(get_printable_shape_field_name name);
385-
end unset_fields1
386-
| _ -> ()
387-
end;
386+
on_error (env, acc) (fun () -> Errors.shape_field_unset unset_pos pos2
387+
(get_printable_shape_field_name name))
388+
end unset_fields1 (env, acc)
389+
| _ -> (env, acc)
390+
end in
388391
ShapeMap.fold begin fun name shape_field_type_1 (env, acc) ->
389392
match ShapeMap.get name fdm2 with
390393
| None when is_shape_field_optional env shape_field_type_1 ->
@@ -400,8 +403,8 @@ let apply_shape
400403
| None ->
401404
let pos1 = Reason.to_pos r1 in
402405
let pos2 = Reason.to_pos r2 in
403-
Errors.missing_field pos2 pos1 (get_printable_shape_field_name name);
404-
(env, acc)
406+
on_error (env, acc) (fun () ->
407+
Errors.missing_field pos2 pos1 (get_printable_shape_field_name name))
405408
| Some shape_field_type_2 ->
406409
on_common_field (env, acc) name shape_field_type_1 shape_field_type_2
407410
end fdm1 (env, acc)

‎hphp/hack/test/typecheck/arithmetic_any.php.exp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ File "arithmetic_any.php--file2.php", line 75, characters 35-45:
2727
File "arithmetic_any.php--file2.php", line 75, characters 48-58:
2828
_
2929
File "arithmetic_any.php--file2.php", line 84, characters 3-13:
30-
(int | ?int)
30+
?int
3131
File "arithmetic_any.php--file2.php", line 89, characters 3-13:
3232
float
3333
No errors

‎hphp/hack/test/typecheck/inout/bad_inout_use_assign4.php.exp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
File "bad_inout_use_assign4.php", line 11, characters 10-19:
1+
File "bad_inout_use_assign4.php", line 15, characters 18-25:
22
Invalid assignment to an inout parameter (Typing[4110])
33
File "bad_inout_use_assign4.php", line 7, characters 18-23:
44
This is a string (inout parameter)

‎hphp/hack/test/typecheck/is_expression/primitive.php.exp‎

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,29 +2,29 @@ File "primitive.php", line 15, characters 15-16:
22
Invalid argument (Typing[4110])
33
File "primitive.php", line 22, characters 22-25:
44
This is a bool
5-
File "primitive.php", line 8, characters 20-22:
6-
It is incompatible with an int
5+
File "primitive.php", line 3, characters 15-19:
6+
It is incompatible with a mixed value
77
File "primitive.php", line 16, characters 16-17:
88
Invalid argument (Typing[4110])
99
File "primitive.php", line 23, characters 23-27:
1010
This is a float
11-
File "primitive.php", line 4, characters 13-16:
12-
It is incompatible with a bool
11+
File "primitive.php", line 3, characters 15-19:
12+
It is incompatible with a mixed value
1313
File "primitive.php", line 17, characters 14-15:
1414
Invalid argument (Typing[4110])
1515
File "primitive.php", line 24, characters 21-23:
1616
This is an int
17-
File "primitive.php", line 4, characters 13-16:
18-
It is incompatible with a bool
17+
File "primitive.php", line 3, characters 15-19:
18+
It is incompatible with a mixed value
1919
File "primitive.php", line 18, characters 19-20:
2020
Invalid argument (Typing[4110])
2121
File "primitive.php", line 25, characters 26-33:
2222
This is a resource
23-
File "primitive.php", line 4, characters 13-16:
24-
It is incompatible with a bool
23+
File "primitive.php", line 3, characters 15-19:
24+
It is incompatible with a mixed value
2525
File "primitive.php", line 19, characters 17-18:
2626
Invalid argument (Typing[4110])
2727
File "primitive.php", line 26, characters 24-29:
2828
This is a string
29-
File "primitive.php", line 4, characters 13-16:
30-
It is incompatible with a bool
29+
File "primitive.php", line 3, characters 15-19:
30+
It is incompatible with a mixed value

‎hphp/hack/test/typecheck/is_expression/primitive_union.php.exp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,5 +8,5 @@ File "primitive_union.php", line 10, characters 14-15:
88
Invalid argument (Typing[4110])
99
File "primitive_union.php", line 14, characters 21-23:
1010
This is a num (int/float)
11-
File "primitive_union.php", line 4, characters 13-20:
12-
It is incompatible with an array key (int/string)
11+
File "primitive_union.php", line 3, characters 15-19:
12+
It is incompatible with a mixed value

‎hphp/hack/test/typecheck/recursive_non_null_3.php.exp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
File "recursive_non_null_3.php", line 20, characters 10-13:
22
Invalid return type (Typing[4110])
3-
File "recursive_non_null_3.php", line 11, characters 32-36:
4-
This is a nonnull value
53
File "recursive_non_null_3.php", line 11, characters 50-50:
6-
It is incompatible with an object of type A
4+
This is an object of type A
5+
File "recursive_non_null_3.php", line 11, characters 32-36:
6+
It is incompatible with a nonnull value

‎hphp/hack/test/typecheck/shape/disable_optional_and_unknown_shape_fields/shape26.php.exp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ File "shape26.php", line 21, characters 3-13:
33
File "shape26.php", line 29, characters 3-13:
44
^(shape('x' => ^(string | int)))
55
File "shape26.php", line 37, characters 3-13:
6-
^(shape('x' => int, ...) | shape('x' => int, 'y' => ?string, ...))
6+
shape('x' => int, ...)
77
File "shape26.php", line 45, characters 3-13:
88
^(shape('x' => ^(int)) | shape('x' => int, 'y' => ?string, ...))
99
No errors

0 commit comments

Comments
 (0)