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-immutable-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::NameResolutionContext &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 (TupleStructItemsNoRest &tuple_items) override;
157 : virtual void visit (TupleStructItemsHasRest &tuple_items) override;
158 : virtual void visit (TupleStructPattern &pattern) override;
159 : virtual void visit (TuplePatternItemsNoRest &tuple_items) override;
160 : virtual void visit (TuplePatternItemsHasRest &tuple_items) override;
161 : virtual void visit (TuplePattern &pattern) override;
162 : virtual void visit (SlicePatternItemsNoRest &items) override;
163 : virtual void visit (SlicePatternItemsHasRest &items) override;
164 : virtual void visit (SlicePattern &pattern) override;
165 : virtual void visit (AltPattern &pattern) override;
166 : virtual void visit (EmptyStmt &stmt) override;
167 : virtual void visit (LetStmt &stmt) override;
168 : virtual void visit (ExprStmt &stmt) override;
169 : virtual void visit (TraitBound &bound) override;
170 : virtual void visit (ImplTraitType &type) override;
171 : virtual void visit (TraitObjectType &type) override;
172 : virtual void visit (ParenthesisedType &type) override;
173 : virtual void visit (TupleType &type) override;
174 : virtual void visit (NeverType &type) override;
175 : virtual void visit (RawPointerType &type) override;
176 : virtual void visit (ReferenceType &type) override;
177 : virtual void visit (ArrayType &type) override;
178 : virtual void visit (SliceType &type) override;
179 : virtual void visit (InferredType &type) override;
180 : virtual void visit (BareFunctionType &type) override;
181 : };
182 :
183 : struct IntRange
184 : {
185 : int64_t lo;
186 : int64_t hi;
187 : };
188 :
189 : class Constructor
190 : {
191 : public:
192 : enum class ConstructorKind
193 : {
194 : // tuple or struct
195 : STRUCT,
196 : // enum variant
197 : VARIANT,
198 : // integers
199 : INT_RANGE,
200 : // user-provided wildcard
201 : WILDCARD,
202 : // references
203 : REFERENCE,
204 : };
205 :
206 7946 : static Constructor make_wildcard ()
207 : {
208 7946 : return Constructor (ConstructorKind::WILDCARD);
209 : }
210 :
211 : static Constructor make_reference ()
212 : {
213 : return Constructor (ConstructorKind::REFERENCE);
214 : }
215 :
216 965 : static Constructor make_struct ()
217 : {
218 965 : Constructor c (ConstructorKind::STRUCT);
219 965 : c.variant_idx = 0;
220 965 : return c;
221 : }
222 :
223 2134 : static Constructor make_variant (int variant_idx)
224 : {
225 2134 : Constructor c (ConstructorKind::VARIANT);
226 2134 : c.variant_idx = variant_idx;
227 2134 : return c;
228 : }
229 :
230 5211 : ConstructorKind get_kind () const { return kind; }
231 :
232 2737 : int get_variant_index () const
233 : {
234 2737 : rust_assert (kind == ConstructorKind::VARIANT
235 : || kind == ConstructorKind::STRUCT);
236 2737 : return variant_idx;
237 : }
238 :
239 : bool is_covered_by (const Constructor &o) const;
240 :
241 10641 : bool is_wildcard () const { return kind == ConstructorKind::WILDCARD; }
242 :
243 : // Requrired by std::set<T>
244 : bool operator< (const Constructor &o) const;
245 :
246 : std::string to_string () const;
247 :
248 : private:
249 4336 : Constructor (ConstructorKind kind) : kind (kind), variant_idx (0) {}
250 : ConstructorKind kind;
251 :
252 : union
253 : {
254 : // for enum variants, the variant index (always 0 for structs)
255 : int variant_idx;
256 :
257 : // for integer ranges, the range
258 : IntRange int_range;
259 : };
260 : };
261 :
262 92475 : class DeconstructedPat
263 : {
264 : public:
265 913 : DeconstructedPat (Constructor ctor, int arity,
266 : std::vector<DeconstructedPat> fields, location_t locus)
267 913 : : ctor (ctor), arity (arity), fields (fields)
268 : {}
269 :
270 2675 : static DeconstructedPat make_wildcard (location_t locus)
271 : {
272 2675 : return DeconstructedPat (Constructor::make_wildcard (), locus);
273 : }
274 :
275 : static DeconstructedPat make_reference (location_t locus)
276 : {
277 : return DeconstructedPat (Constructor::make_reference (), locus);
278 : }
279 :
280 0 : const Constructor &get_ctor () const { return ctor; }
281 :
282 : int get_arity () const { return arity; }
283 :
284 : std::vector<DeconstructedPat> specialize (const Constructor &other_ctor,
285 : int other_ctor_arity) const;
286 :
287 : std::string to_string () const;
288 :
289 : private:
290 6703 : DeconstructedPat (Constructor ctor, location_t locus)
291 6703 : : ctor (ctor), arity (0), locus (locus)
292 : {}
293 :
294 : Constructor ctor;
295 : int arity;
296 : std::vector<DeconstructedPat> fields;
297 : location_t locus;
298 : };
299 :
300 139029 : class PatOrWild
301 : {
302 : public:
303 4264 : static PatOrWild make_pattern (DeconstructedPat pat)
304 : {
305 4264 : return PatOrWild (pat);
306 : }
307 :
308 0 : static PatOrWild make_wildcard () { return PatOrWild ({}); }
309 :
310 : bool is_wildcard () const
311 : {
312 : return !(pat.has_value () && !pat.value ().get_ctor ().is_wildcard ());
313 : }
314 :
315 : bool is_covered_by (const Constructor &c) const;
316 :
317 : // Returns the pattern if it is not a wildcard.
318 : const tl::optional<DeconstructedPat> &get_pat () const
319 : {
320 : rust_assert (pat.has_value ());
321 : return pat;
322 : }
323 :
324 15083 : Constructor ctor () const
325 : {
326 15083 : if (pat.has_value ())
327 15083 : return pat.value ().get_ctor ();
328 : else
329 0 : return Constructor::make_wildcard ();
330 : }
331 :
332 : std::vector<PatOrWild> specialize (const Constructor &other_ctor,
333 : int other_ctor_arity) const;
334 :
335 : std::string to_string () const;
336 :
337 : private:
338 4264 : PatOrWild (tl::optional<DeconstructedPat> pat) : pat (pat) {}
339 :
340 : tl::optional<DeconstructedPat> pat;
341 : };
342 :
343 15751 : class PatStack
344 : {
345 : public:
346 2467 : PatStack () : relevant (false) {}
347 :
348 2467 : void push (PatOrWild pat) { pats.push_back (pat); }
349 :
350 : bool empty () const { return pats.empty (); }
351 :
352 15760 : PatOrWild &head ()
353 : {
354 15760 : rust_assert (!pats.empty ());
355 15760 : return pats.front ();
356 : }
357 :
358 4266 : const PatOrWild &head () const
359 : {
360 4266 : rust_assert (!pats.empty ());
361 4266 : return pats.front ();
362 : }
363 :
364 : // Only called if the head is a constructor which is convered by o.
365 : void pop_head_constructor (const Constructor &other_ctor,
366 : int other_ctor_arity);
367 :
368 7410 : const std::deque<PatOrWild> &get_subpatterns () const { return pats; }
369 :
370 : private:
371 4943 : void pop_head () { pats.pop_front (); }
372 :
373 : std::deque<PatOrWild> pats;
374 : bool relevant;
375 : };
376 :
377 45200 : class MatrixRow
378 : {
379 : public:
380 7410 : MatrixRow (PatStack pats, bool is_under_guard_)
381 7410 : : pats (pats), is_under_guard_ (is_under_guard_)
382 : // useful (false),
383 : // head_is_branch (false),
384 : {}
385 :
386 : PatStack &get_pats () { return pats; }
387 :
388 5874 : PatStack get_pats_clone () const { return pats; }
389 :
390 4266 : const PatOrWild &head () const { return pats.head (); }
391 : PatOrWild &head () { return pats.head (); }
392 :
393 4943 : bool is_under_guard () const { return is_under_guard_; }
394 :
395 : std::string to_string () const;
396 :
397 : private:
398 : PatStack pats;
399 : bool is_under_guard_;
400 : // TODO: manage usefulness
401 : };
402 :
403 : class PlaceInfo
404 : {
405 : public:
406 1906 : PlaceInfo (TyTy::BaseType *ty) : ty (ty) {}
407 :
408 5279 : TyTy::BaseType *get_type () const { return ty; }
409 :
410 : std::vector<PlaceInfo> specialize (const Constructor &c) const;
411 :
412 : private:
413 : TyTy::BaseType *ty;
414 : };
415 :
416 3658 : class Matrix
417 : {
418 : public:
419 3658 : Matrix (std::vector<MatrixRow> rows, std::vector<PlaceInfo> place_infos)
420 3658 : : rows (rows), place_infos (place_infos)
421 : {}
422 :
423 : Matrix () {}
424 :
425 3658 : std::vector<MatrixRow> &get_rows () { return rows; }
426 :
427 : void push_row (const MatrixRow &row) { rows.push_back (row); }
428 :
429 5562 : std::vector<PlaceInfo> &get_place_infos () { return place_infos; }
430 :
431 1910 : std::vector<PatOrWild> heads () const
432 : {
433 1910 : std::vector<PatOrWild> ret;
434 6176 : for (const MatrixRow &row : rows)
435 4266 : ret.push_back (row.head ());
436 :
437 1910 : return ret;
438 : }
439 :
440 : Matrix specialize (const Constructor &ctor) const;
441 :
442 : std::string to_string () const;
443 :
444 : private:
445 : std::vector<MatrixRow> rows;
446 : std::vector<PlaceInfo> place_infos;
447 : };
448 :
449 2467 : class MatchArm
450 : {
451 : public:
452 2467 : MatchArm (DeconstructedPat pat, bool has_guard_)
453 2467 : : pat (pat), has_guard_ (has_guard_)
454 : {}
455 :
456 2467 : DeconstructedPat get_pat () const { return pat; }
457 :
458 2467 : bool has_guard () const { return has_guard_; }
459 :
460 : private:
461 : DeconstructedPat pat;
462 : bool has_guard_;
463 : };
464 :
465 103 : class WitnessPat
466 : {
467 : public:
468 17 : WitnessPat (Constructor ctor, std::vector<WitnessPat> fields,
469 : TyTy::BaseType *ty)
470 17 : : ctor (ctor), fields (fields), ty (ty)
471 : {}
472 :
473 6 : static WitnessPat make_wildcard (TyTy::BaseType *ty)
474 : {
475 6 : return WitnessPat (Constructor::make_wildcard (), {}, ty);
476 : }
477 :
478 : const Constructor &get_ctor () const { return ctor; }
479 :
480 : const std::vector<WitnessPat> &get_fields () const { return fields; }
481 :
482 : TyTy::BaseType *get_type () const { return ty; }
483 :
484 : std::string to_string () const;
485 :
486 : private:
487 : Constructor ctor;
488 : std::vector<WitnessPat> fields;
489 : TyTy::BaseType *ty;
490 : };
491 :
492 5568 : class WitnessMatrix
493 : {
494 : public:
495 : // Create an empty witness matrix.
496 3652 : static WitnessMatrix make_empty () { return WitnessMatrix ({}); }
497 :
498 : // Create a unit witness matrix, a new single witness.
499 6 : static WitnessMatrix make_unit ()
500 : {
501 18 : return WitnessMatrix ({std::vector<WitnessPat> ()});
502 : }
503 :
504 1067 : bool empty () const { return patstacks.empty (); }
505 :
506 6 : const std::vector<std::vector<WitnessPat>> &get_stacks () const
507 : {
508 6 : return patstacks;
509 : }
510 :
511 : // Reverses specialization.
512 : void apply_constructor (const Constructor &ctor,
513 : const std::set<Constructor> &missings,
514 : TyTy::BaseType *ty);
515 :
516 : void extend (const WitnessMatrix &other);
517 :
518 : private:
519 3658 : WitnessMatrix (std::vector<std::vector<WitnessPat>> patstacks)
520 3658 : : patstacks (patstacks)
521 : {}
522 :
523 : std::vector<std::vector<WitnessPat>> patstacks;
524 : };
525 :
526 : } // namespace Analysis
527 : } // namespace Rust
528 :
529 : #endif
|
