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-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 : 7825 : static Constructor make_wildcard ()
207 : : {
208 : 7825 : return Constructor (ConstructorKind::WILDCARD);
209 : : }
210 : :
211 : : static Constructor make_reference ()
212 : : {
213 : : return Constructor (ConstructorKind::REFERENCE);
214 : : }
215 : :
216 : 945 : static Constructor make_struct ()
217 : : {
218 : 945 : Constructor c (ConstructorKind::STRUCT);
219 : 945 : c.variant_idx = 0;
220 : 945 : 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 : 5149 : ConstructorKind get_kind () const { return kind; }
231 : :
232 : 2719 : int get_variant_index () const
233 : : {
234 : 2719 : rust_assert (kind == ConstructorKind::VARIANT
235 : : || kind == ConstructorKind::STRUCT);
236 : 2719 : return variant_idx;
237 : : }
238 : :
239 : : bool is_covered_by (const Constructor &o) const;
240 : :
241 : 10494 : 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 : 4294 : 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 : 90920 : class DeconstructedPat
263 : : {
264 : : public:
265 : 902 : DeconstructedPat (Constructor ctor, int arity,
266 : : std::vector<DeconstructedPat> fields, location_t locus)
267 : 902 : : ctor (ctor), arity (arity), fields (fields)
268 : : {}
269 : :
270 : 2629 : static DeconstructedPat make_wildcard (location_t locus)
271 : : {
272 : 2629 : 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 : 6604 : DeconstructedPat (Constructor ctor, location_t locus)
291 : 6604 : : 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 : 136755 : class PatOrWild
301 : : {
302 : : public:
303 : 4200 : static PatOrWild make_pattern (DeconstructedPat pat)
304 : : {
305 : 4200 : 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 : 14891 : Constructor ctor () const
325 : : {
326 : 14891 : if (pat.has_value ())
327 : 14891 : 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 : 4200 : PatOrWild (tl::optional<DeconstructedPat> pat) : pat (pat) {}
339 : :
340 : : tl::optional<DeconstructedPat> pat;
341 : : };
342 : :
343 : 15571 : class PatStack
344 : : {
345 : : public:
346 : 2441 : PatStack () : relevant (false) {}
347 : :
348 : 2441 : void push (PatOrWild pat) { pats.push_back (pat); }
349 : :
350 : : bool empty () const { return pats.empty (); }
351 : :
352 : 15568 : PatOrWild &head ()
353 : : {
354 : 15568 : rust_assert (!pats.empty ());
355 : 15568 : return pats.front ();
356 : : }
357 : :
358 : 4202 : const PatOrWild &head () const
359 : : {
360 : 4202 : rust_assert (!pats.empty ());
361 : 4202 : 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 : 7320 : const std::deque<PatOrWild> &get_subpatterns () const { return pats; }
369 : :
370 : : private:
371 : 4879 : void pop_head () { pats.pop_front (); }
372 : :
373 : : std::deque<PatOrWild> pats;
374 : : bool relevant;
375 : : };
376 : :
377 : 44654 : class MatrixRow
378 : : {
379 : : public:
380 : 7320 : MatrixRow (PatStack pats, bool is_under_guard_)
381 : 7320 : : 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 : 5810 : PatStack get_pats_clone () const { return pats; }
389 : :
390 : 4202 : const PatOrWild &head () const { return pats.head (); }
391 : : PatOrWild &head () { return pats.head (); }
392 : :
393 : 4879 : 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 : 1875 : PlaceInfo (TyTy::BaseType *ty) : ty (ty) {}
407 : :
408 : 5199 : 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 : 3614 : class Matrix
417 : : {
418 : : public:
419 : 3614 : Matrix (std::vector<MatrixRow> rows, std::vector<PlaceInfo> place_infos)
420 : 3614 : : rows (rows), place_infos (place_infos)
421 : : {}
422 : :
423 : : Matrix () {}
424 : :
425 : 3614 : std::vector<MatrixRow> &get_rows () { return rows; }
426 : :
427 : : void push_row (const MatrixRow &row) { rows.push_back (row); }
428 : :
429 : 5487 : std::vector<PlaceInfo> &get_place_infos () { return place_infos; }
430 : :
431 : 1879 : std::vector<PatOrWild> heads () const
432 : : {
433 : 1879 : std::vector<PatOrWild> ret;
434 : 6081 : for (const MatrixRow &row : rows)
435 : 4202 : ret.push_back (row.head ());
436 : :
437 : 1879 : 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 : 2441 : class MatchArm
450 : : {
451 : : public:
452 : 2441 : MatchArm (DeconstructedPat pat, bool has_guard_)
453 : 2441 : : pat (pat), has_guard_ (has_guard_)
454 : : {}
455 : :
456 : 2441 : DeconstructedPat get_pat () const { return pat; }
457 : :
458 : 2441 : 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 : 5493 : class WitnessMatrix
493 : : {
494 : : public:
495 : : // Create an empty witness matrix.
496 : 3608 : 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 : 1054 : 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 : 3614 : WitnessMatrix (std::vector<std::vector<WitnessPat>> patstacks)
520 : 3614 : : patstacks (patstacks)
521 : : {}
522 : :
523 : : std::vector<std::vector<WitnessPat>> patstacks;
524 : : };
525 : :
526 : : } // namespace Analysis
527 : : } // namespace Rust
528 : :
529 : : #endif
|
