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