Line data Source code
1 : // Copyright (C) 2020-2026 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-finalized-name-resolution-context.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 : const Resolver2_0::FinalizedNameResolutionContext &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 (BoxExpr &expr) override;
101 : virtual void visit (ReturnExpr &expr) override;
102 : virtual void visit (UnsafeBlockExpr &expr) override;
103 : virtual void visit (LoopExpr &expr) override;
104 : virtual void visit (WhileLoopExpr &expr) override;
105 : virtual void visit (WhileLetLoopExpr &expr) override;
106 : virtual void visit (IfExpr &expr) override;
107 : virtual void visit (IfExprConseqElse &expr) override;
108 : virtual void visit (HIR::MatchExpr &expr) override;
109 : virtual void visit (AwaitExpr &expr) override;
110 : virtual void visit (AsyncBlockExpr &expr) override;
111 : virtual void visit (InlineAsm &expr) override;
112 : virtual void visit (LlvmInlineAsm &expr) override;
113 : virtual void visit (OffsetOf &expr) override;
114 : virtual void visit (TypeParam ¶m) override;
115 : virtual void visit (ConstGenericParam ¶m) override;
116 : virtual void visit (LifetimeWhereClauseItem &item) override;
117 : virtual void visit (TypeBoundWhereClauseItem &item) override;
118 : virtual void visit (Module &module) override;
119 : virtual void visit (ExternCrate &crate) override;
120 : virtual void visit (UseTreeGlob &use_tree) override;
121 : virtual void visit (UseTreeList &use_tree) override;
122 : virtual void visit (UseTreeRebind &use_tree) override;
123 : virtual void visit (UseDeclaration &use_decl) override;
124 : virtual void visit (Function &function) override;
125 : virtual void visit (TypeAlias &type_alias) override;
126 : virtual void visit (StructStruct &struct_item) override;
127 : virtual void visit (TupleStruct &tuple_struct) override;
128 : virtual void visit (EnumItem &item) override;
129 : virtual void visit (EnumItemTuple &item) override;
130 : virtual void visit (EnumItemStruct &item) override;
131 : virtual void visit (EnumItemDiscriminant &item) override;
132 : virtual void visit (Enum &enum_item) override;
133 : virtual void visit (Union &union_item) override;
134 : virtual void visit (ConstantItem &const_item) override;
135 : virtual void visit (StaticItem &static_item) override;
136 : virtual void visit (TraitItemFunc &item) override;
137 : virtual void visit (TraitItemConst &item) override;
138 : virtual void visit (TraitItemType &item) override;
139 : virtual void visit (Trait &trait) override;
140 : virtual void visit (ImplBlock &impl) override;
141 : virtual void visit (ExternalStaticItem &item) override;
142 : virtual void visit (ExternalFunctionItem &item) override;
143 : virtual void visit (ExternalTypeItem &item) override;
144 : virtual void visit (ExternBlock &block) override;
145 : virtual void visit (LiteralPattern &pattern) override;
146 : virtual void visit (IdentifierPattern &pattern) override;
147 : virtual void visit (WildcardPattern &pattern) override;
148 : virtual void visit (RangePatternBoundLiteral &bound) override;
149 : virtual void visit (RangePatternBoundPath &bound) override;
150 : virtual void visit (RangePatternBoundQualPath &bound) override;
151 : virtual void visit (RangePattern &pattern) override;
152 : virtual void visit (ReferencePattern &pattern) override;
153 : virtual void visit (StructPatternFieldTuplePat &field) override;
154 : virtual void visit (StructPatternFieldIdentPat &field) override;
155 : virtual void visit (StructPatternFieldIdent &field) override;
156 : virtual void visit (StructPattern &pattern) override;
157 : virtual void visit (TupleStructItemsNoRest &tuple_items) override;
158 : virtual void visit (TupleStructItemsHasRest &tuple_items) override;
159 : virtual void visit (TupleStructPattern &pattern) override;
160 : virtual void visit (TuplePatternItemsNoRest &tuple_items) override;
161 : virtual void visit (TuplePatternItemsHasRest &tuple_items) override;
162 : virtual void visit (TuplePattern &pattern) override;
163 : virtual void visit (SlicePatternItemsNoRest &items) override;
164 : virtual void visit (SlicePatternItemsHasRest &items) override;
165 : virtual void visit (SlicePattern &pattern) override;
166 : virtual void visit (AltPattern &pattern) override;
167 : virtual void visit (EmptyStmt &stmt) override;
168 : virtual void visit (LetStmt &stmt) override;
169 : virtual void visit (ExprStmt &stmt) override;
170 : virtual void visit (TraitBound &bound) override;
171 : virtual void visit (ImplTraitType &type) override;
172 : virtual void visit (TraitObjectType &type) override;
173 : virtual void visit (ParenthesisedType &type) override;
174 : virtual void visit (TupleType &type) override;
175 : virtual void visit (NeverType &type) override;
176 : virtual void visit (RawPointerType &type) override;
177 : virtual void visit (ReferenceType &type) override;
178 : virtual void visit (ArrayType &type) override;
179 : virtual void visit (SliceType &type) override;
180 : virtual void visit (InferredType &type) override;
181 : virtual void visit (BareFunctionType &type) override;
182 : };
183 :
184 : struct IntRange
185 : {
186 : int64_t lo;
187 : int64_t hi;
188 : };
189 :
190 : class Constructor
191 : {
192 : public:
193 : enum class ConstructorKind
194 : {
195 : // tuple or struct
196 : STRUCT,
197 : // enum variant
198 : VARIANT,
199 : // integers
200 : INT_RANGE,
201 : // user-provided wildcard
202 : WILDCARD,
203 : // references
204 : REFERENCE,
205 : };
206 :
207 8011 : static Constructor make_wildcard ()
208 : {
209 8011 : return Constructor (ConstructorKind::WILDCARD);
210 : }
211 :
212 : static Constructor make_reference ()
213 : {
214 : return Constructor (ConstructorKind::REFERENCE);
215 : }
216 :
217 972 : static Constructor make_struct ()
218 : {
219 972 : Constructor c (ConstructorKind::STRUCT);
220 972 : c.variant_idx = 0;
221 972 : return c;
222 : }
223 :
224 2137 : static Constructor make_variant (int variant_idx)
225 : {
226 2137 : Constructor c (ConstructorKind::VARIANT);
227 2137 : c.variant_idx = variant_idx;
228 2137 : return c;
229 : }
230 :
231 5247 : ConstructorKind get_kind () const { return kind; }
232 :
233 2747 : int get_variant_index () const
234 : {
235 2747 : rust_assert (kind == ConstructorKind::VARIANT
236 : || kind == ConstructorKind::STRUCT);
237 2747 : return variant_idx;
238 : }
239 :
240 : bool is_covered_by (const Constructor &o) const;
241 :
242 10707 : bool is_wildcard () const { return kind == ConstructorKind::WILDCARD; }
243 :
244 : // Requrired by std::set<T>
245 : bool operator< (const Constructor &o) const;
246 :
247 : std::string to_string () const;
248 :
249 : private:
250 4359 : Constructor (ConstructorKind kind) : kind (kind), variant_idx (0) {}
251 : ConstructorKind kind;
252 :
253 : union
254 : {
255 : // for enum variants, the variant index (always 0 for structs)
256 : int variant_idx;
257 :
258 : // for integer ranges, the range
259 : IntRange int_range;
260 : };
261 : };
262 :
263 93075 : class DeconstructedPat
264 : {
265 : public:
266 917 : DeconstructedPat (Constructor ctor, int arity,
267 : std::vector<DeconstructedPat> fields, location_t locus)
268 917 : : ctor (ctor), arity (arity), fields (fields)
269 : {}
270 :
271 2700 : static DeconstructedPat make_wildcard (location_t locus)
272 : {
273 2700 : return DeconstructedPat (Constructor::make_wildcard (), locus);
274 : }
275 :
276 : static DeconstructedPat make_reference (location_t locus)
277 : {
278 : return DeconstructedPat (Constructor::make_reference (), locus);
279 : }
280 :
281 0 : const Constructor &get_ctor () const { return ctor; }
282 :
283 : int get_arity () const { return arity; }
284 :
285 : std::vector<DeconstructedPat> specialize (const Constructor &other_ctor,
286 : int other_ctor_arity) const;
287 :
288 : std::string to_string () const;
289 :
290 : private:
291 6755 : DeconstructedPat (Constructor ctor, location_t locus)
292 6755 : : ctor (ctor), arity (0), locus (locus)
293 : {}
294 :
295 : Constructor ctor;
296 : int arity;
297 : std::vector<DeconstructedPat> fields;
298 : location_t locus;
299 : };
300 :
301 139961 : class PatOrWild
302 : {
303 : public:
304 4294 : static PatOrWild make_pattern (DeconstructedPat pat)
305 : {
306 4294 : return PatOrWild (pat);
307 : }
308 :
309 0 : static PatOrWild make_wildcard () { return PatOrWild ({}); }
310 :
311 : bool is_wildcard () const
312 : {
313 : return !(pat.has_value () && !pat.value ().get_ctor ().is_wildcard ());
314 : }
315 :
316 : bool is_covered_by (const Constructor &c) const;
317 :
318 : // Returns the pattern if it is not a wildcard.
319 : const tl::optional<DeconstructedPat> &get_pat () const
320 : {
321 : rust_assert (pat.has_value ());
322 : return pat;
323 : }
324 :
325 15176 : Constructor ctor () const
326 : {
327 15176 : if (pat.has_value ())
328 15176 : return pat.value ().get_ctor ();
329 : else
330 0 : return Constructor::make_wildcard ();
331 : }
332 :
333 : std::vector<PatOrWild> specialize (const Constructor &other_ctor,
334 : int other_ctor_arity) const;
335 :
336 : std::string to_string () const;
337 :
338 : private:
339 4294 : PatOrWild (tl::optional<DeconstructedPat> pat) : pat (pat) {}
340 :
341 : tl::optional<DeconstructedPat> pat;
342 : };
343 :
344 15858 : class PatStack
345 : {
346 : public:
347 2489 : PatStack () : relevant (false) {}
348 :
349 2489 : void push (PatOrWild pat) { pats.push_back (pat); }
350 :
351 : bool empty () const { return pats.empty (); }
352 :
353 15854 : PatOrWild &head ()
354 : {
355 15854 : rust_assert (!pats.empty ());
356 15854 : return pats.front ();
357 : }
358 :
359 4296 : const PatOrWild &head () const
360 : {
361 4296 : rust_assert (!pats.empty ());
362 4296 : return pats.front ();
363 : }
364 :
365 : // Only called if the head is a constructor which is convered by o.
366 : void pop_head_constructor (const Constructor &other_ctor,
367 : int other_ctor_arity);
368 :
369 7463 : const std::deque<PatOrWild> &get_subpatterns () const { return pats; }
370 :
371 : private:
372 4974 : void pop_head () { pats.pop_front (); }
373 :
374 : std::deque<PatOrWild> pats;
375 : bool relevant;
376 : };
377 :
378 45529 : class MatrixRow
379 : {
380 : public:
381 7463 : MatrixRow (PatStack pats, bool is_under_guard_)
382 7463 : : pats (pats), is_under_guard_ (is_under_guard_)
383 : // useful (false),
384 : // head_is_branch (false),
385 : {}
386 :
387 : PatStack &get_pats () { return pats; }
388 :
389 5906 : PatStack get_pats_clone () const { return pats; }
390 :
391 4296 : const PatOrWild &head () const { return pats.head (); }
392 : PatOrWild &head () { return pats.head (); }
393 :
394 4974 : bool is_under_guard () const { return is_under_guard_; }
395 :
396 : std::string to_string () const;
397 :
398 : private:
399 : PatStack pats;
400 : bool is_under_guard_;
401 : // TODO: manage usefulness
402 : };
403 :
404 : class PlaceInfo
405 : {
406 : public:
407 1923 : PlaceInfo (TyTy::BaseType *ty) : ty (ty) {}
408 :
409 5320 : TyTy::BaseType *get_type () const { return ty; }
410 :
411 : std::vector<PlaceInfo> specialize (const Constructor &c) const;
412 :
413 : private:
414 : TyTy::BaseType *ty;
415 : };
416 :
417 3687 : class Matrix
418 : {
419 : public:
420 3687 : Matrix (std::vector<MatrixRow> rows, std::vector<PlaceInfo> place_infos)
421 3687 : : rows (rows), place_infos (place_infos)
422 : {}
423 :
424 : Matrix () {}
425 :
426 3687 : std::vector<MatrixRow> &get_rows () { return rows; }
427 :
428 : void push_row (const MatrixRow &row) { rows.push_back (row); }
429 :
430 5608 : std::vector<PlaceInfo> &get_place_infos () { return place_infos; }
431 :
432 1927 : std::vector<PatOrWild> heads () const
433 : {
434 1927 : std::vector<PatOrWild> ret;
435 6223 : for (const MatrixRow &row : rows)
436 4296 : ret.push_back (row.head ());
437 :
438 1927 : return ret;
439 : }
440 :
441 : Matrix specialize (const Constructor &ctor) const;
442 :
443 : std::string to_string () const;
444 :
445 : private:
446 : std::vector<MatrixRow> rows;
447 : std::vector<PlaceInfo> place_infos;
448 : };
449 :
450 2489 : class MatchArm
451 : {
452 : public:
453 2489 : MatchArm (DeconstructedPat pat, bool has_guard_)
454 2489 : : pat (pat), has_guard_ (has_guard_)
455 : {}
456 :
457 2489 : DeconstructedPat get_pat () const { return pat; }
458 :
459 2489 : bool has_guard () const { return has_guard_; }
460 :
461 : private:
462 : DeconstructedPat pat;
463 : bool has_guard_;
464 : };
465 :
466 103 : class WitnessPat
467 : {
468 : public:
469 17 : WitnessPat (Constructor ctor, std::vector<WitnessPat> fields,
470 : TyTy::BaseType *ty)
471 17 : : ctor (ctor), fields (fields), ty (ty)
472 : {}
473 :
474 6 : static WitnessPat make_wildcard (TyTy::BaseType *ty)
475 : {
476 6 : return WitnessPat (Constructor::make_wildcard (), {}, ty);
477 : }
478 :
479 : const Constructor &get_ctor () const { return ctor; }
480 :
481 : const std::vector<WitnessPat> &get_fields () const { return fields; }
482 :
483 : TyTy::BaseType *get_type () const { return ty; }
484 :
485 : std::string to_string () const;
486 :
487 : private:
488 : Constructor ctor;
489 : std::vector<WitnessPat> fields;
490 : TyTy::BaseType *ty;
491 : };
492 :
493 5614 : class WitnessMatrix
494 : {
495 : public:
496 : // Create an empty witness matrix.
497 3681 : static WitnessMatrix make_empty () { return WitnessMatrix ({}); }
498 :
499 : // Create a unit witness matrix, a new single witness.
500 6 : static WitnessMatrix make_unit ()
501 : {
502 18 : return WitnessMatrix ({std::vector<WitnessPat> ()});
503 : }
504 :
505 1078 : bool empty () const { return patstacks.empty (); }
506 :
507 6 : const std::vector<std::vector<WitnessPat>> &get_stacks () const
508 : {
509 6 : return patstacks;
510 : }
511 :
512 : // Reverses specialization.
513 : void apply_constructor (const Constructor &ctor,
514 : const std::set<Constructor> &missings,
515 : TyTy::BaseType *ty);
516 :
517 : void extend (const WitnessMatrix &other);
518 :
519 : private:
520 3687 : WitnessMatrix (std::vector<std::vector<WitnessPat>> patstacks)
521 3687 : : patstacks (patstacks)
522 : {}
523 :
524 : std::vector<std::vector<WitnessPat>> patstacks;
525 : };
526 :
527 : } // namespace Analysis
528 : } // namespace Rust
529 :
530 : #endif
|
