Branch data Line data Source code
1 : : // Copyright (C) 2020-2024 Free Software Foundation, Inc.
2 : :
3 : : // This file is part of GCC.
4 : :
5 : : // GCC is free software; you can redistribute it and/or modify it under
6 : : // the terms of the GNU General Public License as published by the Free
7 : : // Software Foundation; either version 3, or (at your option) any later
8 : : // version.
9 : :
10 : : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : : // for more details.
14 : :
15 : : // You should have received a copy of the GNU General Public License
16 : : // along with GCC; see the file COPYING3. If not see
17 : : // <http://www.gnu.org/licenses/>.
18 : :
19 : : #ifndef RUST_HIR_PATTERN_ANALYSIS_H
20 : : #define RUST_HIR_PATTERN_ANALYSIS_H
21 : :
22 : : #include "rust-system.h"
23 : : #include "rust-hir-expr.h"
24 : : #include "rust-hir-type-check.h"
25 : : #include "rust-system.h"
26 : : #include "rust-tyty.h"
27 : : #include "optional.h"
28 : : #include "rust-hir-visitor.h"
29 : : #include "rust-name-resolver.h"
30 : :
31 : : namespace Rust {
32 : : namespace Analysis {
33 : :
34 : : using namespace HIR;
35 : :
36 : : void check_match_usefulness (Resolver::TypeCheckContext *ctx,
37 : : TyTy::BaseType *scrutinee_ty,
38 : : HIR::MatchExpr &expr);
39 : :
40 : : class PatternChecker : public HIR::HIRFullVisitor
41 : : {
42 : : public:
43 : : PatternChecker ();
44 : :
45 : : void go (HIR::Crate &crate);
46 : :
47 : : private:
48 : : Resolver::TypeCheckContext &tyctx;
49 : : Resolver::Resolver &resolver;
50 : : Analysis::Mappings &mappings;
51 : :
52 : : virtual void visit (Lifetime &lifetime) override;
53 : : virtual void visit (LifetimeParam &lifetime_param) override;
54 : : virtual void visit (PathInExpression &path) override;
55 : : virtual void visit (TypePathSegment &segment) override;
56 : : virtual void visit (TypePathSegmentGeneric &segment) override;
57 : : virtual void visit (TypePathSegmentFunction &segment) override;
58 : : virtual void visit (TypePath &path) override;
59 : : virtual void visit (QualifiedPathInExpression &path) override;
60 : : virtual void visit (QualifiedPathInType &path) override;
61 : : virtual void visit (LiteralExpr &expr) override;
62 : : virtual void visit (BorrowExpr &expr) override;
63 : : virtual void visit (DereferenceExpr &expr) override;
64 : : virtual void visit (ErrorPropagationExpr &expr) override;
65 : : virtual void visit (NegationExpr &expr) override;
66 : : virtual void visit (ArithmeticOrLogicalExpr &expr) override;
67 : : virtual void visit (ComparisonExpr &expr) override;
68 : : virtual void visit (LazyBooleanExpr &expr) override;
69 : : virtual void visit (TypeCastExpr &expr) override;
70 : : virtual void visit (AssignmentExpr &expr) override;
71 : : virtual void visit (CompoundAssignmentExpr &expr) override;
72 : : virtual void visit (GroupedExpr &expr) override;
73 : : virtual void visit (ArrayElemsValues &elems) override;
74 : : virtual void visit (ArrayElemsCopied &elems) override;
75 : : virtual void visit (ArrayExpr &expr) override;
76 : : virtual void visit (ArrayIndexExpr &expr) override;
77 : : virtual void visit (TupleExpr &expr) override;
78 : : virtual void visit (TupleIndexExpr &expr) override;
79 : : virtual void visit (StructExprStruct &expr) override;
80 : : virtual void visit (StructExprFieldIdentifier &field) override;
81 : : virtual void visit (StructExprFieldIdentifierValue &field) override;
82 : : virtual void visit (StructExprFieldIndexValue &field) override;
83 : : virtual void visit (StructExprStructFields &expr) override;
84 : : virtual void visit (StructExprStructBase &expr) override;
85 : : virtual void visit (CallExpr &expr) override;
86 : : virtual void visit (MethodCallExpr &expr) override;
87 : : virtual void visit (FieldAccessExpr &expr) override;
88 : : virtual void visit (BlockExpr &expr) override;
89 : : virtual void visit (AnonConst &expr) override;
90 : : virtual void visit (ConstBlock &expr) override;
91 : : virtual void visit (ClosureExpr &expr) override;
92 : : virtual void visit (ContinueExpr &expr) override;
93 : : virtual void visit (BreakExpr &expr) override;
94 : : virtual void visit (RangeFromToExpr &expr) override;
95 : : virtual void visit (RangeFromExpr &expr) override;
96 : : virtual void visit (RangeToExpr &expr) override;
97 : : virtual void visit (RangeFullExpr &expr) override;
98 : : virtual void visit (RangeFromToInclExpr &expr) override;
99 : : virtual void visit (RangeToInclExpr &expr) override;
100 : : virtual void visit (ReturnExpr &expr) override;
101 : : virtual void visit (UnsafeBlockExpr &expr) override;
102 : : virtual void visit (LoopExpr &expr) override;
103 : : virtual void visit (WhileLoopExpr &expr) override;
104 : : virtual void visit (WhileLetLoopExpr &expr) override;
105 : : virtual void visit (IfExpr &expr) override;
106 : : virtual void visit (IfExprConseqElse &expr) override;
107 : : virtual void visit (HIR::MatchExpr &expr) override;
108 : : virtual void visit (AwaitExpr &expr) override;
109 : : virtual void visit (AsyncBlockExpr &expr) override;
110 : : virtual void visit (InlineAsm &expr) override;
111 : : virtual void visit (LlvmInlineAsm &expr) override;
112 : : virtual void visit (OffsetOf &expr) override;
113 : : virtual void visit (TypeParam ¶m) override;
114 : : virtual void visit (ConstGenericParam ¶m) override;
115 : : virtual void visit (LifetimeWhereClauseItem &item) override;
116 : : virtual void visit (TypeBoundWhereClauseItem &item) override;
117 : : virtual void visit (Module &module) override;
118 : : virtual void visit (ExternCrate &crate) override;
119 : : virtual void visit (UseTreeGlob &use_tree) override;
120 : : virtual void visit (UseTreeList &use_tree) override;
121 : : virtual void visit (UseTreeRebind &use_tree) override;
122 : : virtual void visit (UseDeclaration &use_decl) override;
123 : : virtual void visit (Function &function) override;
124 : : virtual void visit (TypeAlias &type_alias) override;
125 : : virtual void visit (StructStruct &struct_item) override;
126 : : virtual void visit (TupleStruct &tuple_struct) override;
127 : : virtual void visit (EnumItem &item) override;
128 : : virtual void visit (EnumItemTuple &item) override;
129 : : virtual void visit (EnumItemStruct &item) override;
130 : : virtual void visit (EnumItemDiscriminant &item) override;
131 : : virtual void visit (Enum &enum_item) override;
132 : : virtual void visit (Union &union_item) override;
133 : : virtual void visit (ConstantItem &const_item) override;
134 : : virtual void visit (StaticItem &static_item) override;
135 : : virtual void visit (TraitItemFunc &item) override;
136 : : virtual void visit (TraitItemConst &item) override;
137 : : virtual void visit (TraitItemType &item) override;
138 : : virtual void visit (Trait &trait) override;
139 : : virtual void visit (ImplBlock &impl) override;
140 : : virtual void visit (ExternalStaticItem &item) override;
141 : : virtual void visit (ExternalFunctionItem &item) override;
142 : : virtual void visit (ExternalTypeItem &item) override;
143 : : virtual void visit (ExternBlock &block) override;
144 : : virtual void visit (LiteralPattern &pattern) override;
145 : : virtual void visit (IdentifierPattern &pattern) override;
146 : : virtual void visit (WildcardPattern &pattern) override;
147 : : virtual void visit (RangePatternBoundLiteral &bound) override;
148 : : virtual void visit (RangePatternBoundPath &bound) override;
149 : : virtual void visit (RangePatternBoundQualPath &bound) override;
150 : : virtual void visit (RangePattern &pattern) override;
151 : : virtual void visit (ReferencePattern &pattern) override;
152 : : virtual void visit (StructPatternFieldTuplePat &field) override;
153 : : virtual void visit (StructPatternFieldIdentPat &field) override;
154 : : virtual void visit (StructPatternFieldIdent &field) override;
155 : : virtual void visit (StructPattern &pattern) override;
156 : : virtual void visit (TupleStructItemsNoRange &tuple_items) override;
157 : : virtual void visit (TupleStructItemsRange &tuple_items) override;
158 : : virtual void visit (TupleStructPattern &pattern) override;
159 : : virtual void visit (TuplePatternItemsMultiple &tuple_items) override;
160 : : virtual void visit (TuplePatternItemsRanged &tuple_items) override;
161 : : virtual void visit (TuplePattern &pattern) override;
162 : : virtual void visit (SlicePattern &pattern) override;
163 : : virtual void visit (AltPattern &pattern) override;
164 : : virtual void visit (EmptyStmt &stmt) override;
165 : : virtual void visit (LetStmt &stmt) override;
166 : : virtual void visit (ExprStmt &stmt) override;
167 : : virtual void visit (TraitBound &bound) override;
168 : : virtual void visit (ImplTraitType &type) override;
169 : : virtual void visit (TraitObjectType &type) override;
170 : : virtual void visit (ParenthesisedType &type) override;
171 : : virtual void visit (TupleType &type) override;
172 : : virtual void visit (NeverType &type) override;
173 : : virtual void visit (RawPointerType &type) override;
174 : : virtual void visit (ReferenceType &type) override;
175 : : virtual void visit (ArrayType &type) override;
176 : : virtual void visit (SliceType &type) override;
177 : : virtual void visit (InferredType &type) override;
178 : : virtual void visit (BareFunctionType &type) override;
179 : : };
180 : :
181 : : struct IntRange
182 : : {
183 : : int64_t lo;
184 : : int64_t hi;
185 : : };
186 : :
187 : : class Constructor
188 : : {
189 : : public:
190 : : enum class ConstructorKind
191 : : {
192 : : // tuple or struct
193 : : STRUCT,
194 : : // enum variant
195 : : VARIANT,
196 : : // integers
197 : : INT_RANGE,
198 : : // user-provided wildcard
199 : : WILDCARD,
200 : : // references
201 : : REFERENCE,
202 : : };
203 : :
204 : 7207 : static Constructor make_wildcard ()
205 : : {
206 : 7207 : return Constructor (ConstructorKind::WILDCARD);
207 : : }
208 : :
209 : : static Constructor make_reference ()
210 : : {
211 : : return Constructor (ConstructorKind::REFERENCE);
212 : : }
213 : :
214 : 888 : static Constructor make_struct ()
215 : : {
216 : 888 : Constructor c (ConstructorKind::STRUCT);
217 : 888 : c.variant_idx = 0;
218 : 888 : return c;
219 : : }
220 : :
221 : 2134 : static Constructor make_variant (int variant_idx)
222 : : {
223 : 2134 : Constructor c (ConstructorKind::VARIANT);
224 : 2134 : c.variant_idx = variant_idx;
225 : 2134 : return c;
226 : : }
227 : :
228 : 4943 : ConstructorKind get_kind () const { return kind; }
229 : :
230 : 2683 : int get_variant_index () const
231 : : {
232 : 2683 : rust_assert (kind == ConstructorKind::VARIANT
233 : : || kind == ConstructorKind::STRUCT);
234 : 2683 : return variant_idx;
235 : : }
236 : :
237 : : bool is_covered_by (const Constructor &o) const;
238 : :
239 : 9786 : bool is_wildcard () const { return kind == ConstructorKind::WILDCARD; }
240 : :
241 : : // Requrired by std::set<T>
242 : : bool operator< (const Constructor &o) const;
243 : :
244 : : std::string to_string () const;
245 : :
246 : : private:
247 : 4152 : Constructor (ConstructorKind kind) : kind (kind), variant_idx (0) {}
248 : : ConstructorKind kind;
249 : :
250 : : union
251 : : {
252 : : // for enum variants, the variant index (always 0 for structs)
253 : : int variant_idx;
254 : :
255 : : // for integer ranges, the range
256 : : IntRange int_range;
257 : : };
258 : : };
259 : :
260 : 82080 : class DeconstructedPat
261 : : {
262 : : public:
263 : 863 : DeconstructedPat (Constructor ctor, int arity,
264 : : std::vector<DeconstructedPat> fields, location_t locus)
265 : 863 : : ctor (ctor), arity (arity), fields (fields)
266 : : {}
267 : :
268 : 2384 : static DeconstructedPat make_wildcard (location_t locus)
269 : : {
270 : 2384 : return DeconstructedPat (Constructor::make_wildcard (), locus);
271 : : }
272 : :
273 : : static DeconstructedPat make_reference (location_t locus)
274 : : {
275 : : return DeconstructedPat (Constructor::make_reference (), locus);
276 : : }
277 : :
278 : 0 : const Constructor &get_ctor () const { return ctor; }
279 : :
280 : : int get_arity () const { return arity; }
281 : :
282 : : std::vector<DeconstructedPat> specialize (const Constructor &other_ctor,
283 : : int other_ctor_arity) const;
284 : :
285 : : std::string to_string () const;
286 : :
287 : : private:
288 : 6071 : DeconstructedPat (Constructor ctor, location_t locus)
289 : 6071 : : ctor (ctor), arity (0), locus (locus)
290 : : {}
291 : :
292 : : Constructor ctor;
293 : : int arity;
294 : : std::vector<DeconstructedPat> fields;
295 : : location_t locus;
296 : : };
297 : :
298 : 126037 : class PatOrWild
299 : : {
300 : : public:
301 : 3873 : static PatOrWild make_pattern (DeconstructedPat pat)
302 : : {
303 : 3873 : return PatOrWild (pat);
304 : : }
305 : :
306 : 0 : static PatOrWild make_wildcard () { return PatOrWild ({}); }
307 : :
308 : : bool is_wildcard () const
309 : : {
310 : : return !(pat.has_value () && !pat.value ().get_ctor ().is_wildcard ());
311 : : }
312 : :
313 : : bool is_covered_by (const Constructor &c) const;
314 : :
315 : : // Returns the pattern if it is not a wildcard.
316 : : const tl::optional<DeconstructedPat> &get_pat () const
317 : : {
318 : : rust_assert (pat.has_value ());
319 : : return pat;
320 : : }
321 : :
322 : 13910 : Constructor ctor () const
323 : : {
324 : 13910 : if (pat.has_value ())
325 : 13910 : return pat.value ().get_ctor ();
326 : : else
327 : 0 : return Constructor::make_wildcard ();
328 : : }
329 : :
330 : : std::vector<PatOrWild> specialize (const Constructor &other_ctor,
331 : : int other_ctor_arity) const;
332 : :
333 : : std::string to_string () const;
334 : :
335 : : private:
336 : 3873 : PatOrWild (tl::optional<DeconstructedPat> pat) : pat (pat) {}
337 : :
338 : : tl::optional<DeconstructedPat> pat;
339 : : };
340 : :
341 : 21391 : class PatStack
342 : : {
343 : : public:
344 : 2268 : PatStack () : relevant (false) {}
345 : :
346 : 2268 : void push (PatOrWild pat) { pats.push_back (pat); }
347 : :
348 : : bool empty () const { return pats.empty (); }
349 : :
350 : 14587 : PatOrWild &head ()
351 : : {
352 : 14587 : rust_assert (!pats.empty ());
353 : 14587 : return pats.front ();
354 : : }
355 : :
356 : 3875 : const PatOrWild &head () const
357 : : {
358 : 3875 : rust_assert (!pats.empty ());
359 : 3875 : return pats.front ();
360 : : }
361 : :
362 : : // Only called if the head is a constructor which is convered by o.
363 : : void pop_head_constructor (const Constructor &other_ctor,
364 : : int other_ctor_arity);
365 : :
366 : 6820 : const std::deque<PatOrWild> &get_subpatterns () const { return pats; }
367 : :
368 : : private:
369 : 4552 : void pop_head () { pats.pop_front (); }
370 : :
371 : : std::deque<PatOrWild> pats;
372 : : bool relevant;
373 : : };
374 : :
375 : 54982 : class MatrixRow
376 : : {
377 : : public:
378 : 6820 : MatrixRow (PatStack pats, bool is_under_guard_)
379 : 6820 : : pats (pats), is_under_guard_ (is_under_guard_)
380 : : // useful (false),
381 : : // head_is_branch (false),
382 : : {}
383 : :
384 : : PatStack &get_pats () { return pats; }
385 : :
386 : 5483 : PatStack get_pats_clone () const { return pats; }
387 : :
388 : 3875 : const PatOrWild &head () const { return pats.head (); }
389 : : PatOrWild &head () { return pats.head (); }
390 : :
391 : 4552 : bool is_under_guard () const { return is_under_guard_; }
392 : :
393 : : std::string to_string () const;
394 : :
395 : : private:
396 : : PatStack pats;
397 : : bool is_under_guard_;
398 : : // TODO: manage usefulness
399 : : };
400 : :
401 : : class PlaceInfo
402 : : {
403 : : public:
404 : 1772 : PlaceInfo (TyTy::BaseType *ty) : ty (ty) {}
405 : :
406 : 4931 : TyTy::BaseType *get_type () const { return ty; }
407 : :
408 : : std::vector<PlaceInfo> specialize (const Constructor &c) const;
409 : :
410 : : private:
411 : : TyTy::BaseType *ty;
412 : : };
413 : :
414 : 3455 : class Matrix
415 : : {
416 : : public:
417 : 3455 : Matrix (std::vector<MatrixRow> rows, std::vector<PlaceInfo> place_infos)
418 : 3455 : : rows (rows), place_infos (place_infos)
419 : : {}
420 : :
421 : : Matrix () {}
422 : :
423 : 3455 : std::vector<MatrixRow> &get_rows () { return rows; }
424 : :
425 : : void push_row (const MatrixRow &row) { rows.push_back (row); }
426 : :
427 : 5225 : std::vector<PlaceInfo> &get_place_infos () { return place_infos; }
428 : :
429 : 1776 : std::vector<PatOrWild> heads () const
430 : : {
431 : 1776 : std::vector<PatOrWild> ret;
432 : 5651 : for (const MatrixRow &row : rows)
433 : 3875 : ret.push_back (row.head ());
434 : :
435 : 1776 : return ret;
436 : : }
437 : :
438 : : Matrix specialize (const Constructor &ctor) const;
439 : :
440 : : std::string to_string () const;
441 : :
442 : : private:
443 : : std::vector<MatrixRow> rows;
444 : : std::vector<PlaceInfo> place_infos;
445 : : };
446 : :
447 : 2268 : class MatchArm
448 : : {
449 : : public:
450 : 2268 : MatchArm (DeconstructedPat pat, bool has_guard_)
451 : 2268 : : pat (pat), has_guard_ (has_guard_)
452 : : {}
453 : :
454 : 2268 : DeconstructedPat get_pat () const { return pat; }
455 : :
456 : 2268 : bool has_guard () const { return has_guard_; }
457 : :
458 : : private:
459 : : DeconstructedPat pat;
460 : : bool has_guard_;
461 : : };
462 : :
463 : 125 : class WitnessPat
464 : : {
465 : : public:
466 : 17 : WitnessPat (Constructor ctor, std::vector<WitnessPat> fields,
467 : : TyTy::BaseType *ty)
468 : 17 : : ctor (ctor), fields (fields), ty (ty)
469 : : {}
470 : :
471 : 6 : static WitnessPat make_wildcard (TyTy::BaseType *ty)
472 : : {
473 : 6 : return WitnessPat (Constructor::make_wildcard (), {}, ty);
474 : : }
475 : :
476 : : const Constructor &get_ctor () const { return ctor; }
477 : :
478 : : const std::vector<WitnessPat> &get_fields () const { return fields; }
479 : :
480 : : TyTy::BaseType *get_type () const { return ty; }
481 : :
482 : : std::string to_string () const;
483 : :
484 : : private:
485 : : Constructor ctor;
486 : : std::vector<WitnessPat> fields;
487 : : TyTy::BaseType *ty;
488 : : };
489 : :
490 : 5231 : class WitnessMatrix
491 : : {
492 : : public:
493 : : // Create an empty witness matrix.
494 : 3449 : static WitnessMatrix make_empty () { return WitnessMatrix ({}); }
495 : :
496 : : // Create a unit witness matrix, a new single witness.
497 : 6 : static WitnessMatrix make_unit ()
498 : : {
499 : 18 : return WitnessMatrix ({std::vector<WitnessPat> ()});
500 : : }
501 : :
502 : 998 : bool empty () const { return patstacks.empty (); }
503 : :
504 : 6 : const std::vector<std::vector<WitnessPat>> &get_stacks () const
505 : : {
506 : 6 : return patstacks;
507 : : }
508 : :
509 : : // Reverses specialization.
510 : : void apply_constructor (const Constructor &ctor,
511 : : const std::set<Constructor> &missings,
512 : : TyTy::BaseType *ty);
513 : :
514 : : void extend (const WitnessMatrix &other);
515 : :
516 : : private:
517 : 3455 : WitnessMatrix (std::vector<std::vector<WitnessPat>> patstacks)
518 : 3455 : : patstacks (patstacks)
519 : : {}
520 : :
521 : : std::vector<std::vector<WitnessPat>> patstacks;
522 : : };
523 : :
524 : : } // namespace Analysis
525 : : } // namespace Rust
526 : :
527 : : #endif
|
