Check for unbounded recursion during dropck #22777

pnkfelix · 2015-02-24T17:37:52Z

Check for unbounded recursion during dropck.

Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support.

Fix #22443

rust-highfive · 2015-02-24T17:38:02Z

r? @nikomatsakis

(rust_highfive has picked a reviewer for you, use r? to override)

nikomatsakis · 2015-02-24T17:41:13Z

src/test/compile-fail/dropck_no_diverge_on_nonregular_2.rs

+// except according to those terms.
+
+// Issue 22443: Reject code using non-regular types that would
+// otherwise cause dropck to loop infinitely.


what is the difference between this and the first test?

the comment below says why. (The bug report observed different behaviors, both bad, depending on the order of Digit versus Box)

I see, I think it'd be helpful to write in the comment something like "In contrast to Digit after Box, which is the other test."

Okay, will do

nikomatsakis · 2015-02-25T15:15:35Z

r+ modulo nit

pnkfelix · 2015-02-26T14:56:13Z

@bors r=nikomatsakis ed18e6b rollup

pnkfelix · 2015-02-26T14:57:16Z

(Note for rollup builders: I marked this as rollup, but do note that it adds a new error code, which increases its chances for collision with another PR that also adds the same error code, especially since the same error code might be added in a different file.)

Check for unbounded recursion during dropck. Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support. Fix rust-lang#22443

Manishearth · 2015-02-27T07:08:31Z

This caused a slew of dropck overflows in the rollup.

a sample:

/opt/rust/src/libsyntax/fold.rs:992:17: 992:56 error: overflow while adding drop-check rules for util::small_vector::IntoIter<ast::ImplItem> [E0320]
/opt/rust/src/libsyntax/fold.rs:992                 folder.fold_impl_item(item).into_iter()
                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/rust/src/libsyntax/fold.rs:992:17: 992:56 note: overflowed on struct ast::StructField_ field kind type: ast::StructFieldKind
/opt/rust/src/libsyntax/fold.rs:992                 folder.fold_impl_item(item).into_iter()
                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/rust/src/libsyntax/fold.rs:992:17: 992:44 error: overflow while adding drop-check rules for util::small_vector::SmallVector<ast::ImplItem> [E0320]
/opt/rust/src/libsyntax/fold.rs:992                 folder.fold_impl_item(item).into_iter()
                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/rust/src/libsyntax/fold.rs:992:17: 992:44 note: overflowed on struct ast::StructField_ field kind type: ast::StructFieldKind
/opt/rust/src/libsyntax/fold.rs:992                 folder.fold_impl_item(item).into_iter()
                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/rust/src/libsyntax/fold.rs:1028:13: 1029:44 error: overflow while adding drop-check rules for core::iter::Map<util::small_vector::IntoIter<ptr::P<ast::Method>>, [closure /opt/rust/src/libsyntax/fold.rs:1029:22: 1029:43]> [E0320]
/opt/rust/src/libsyntax/fold.rs:1028             folder.fold_method(method).into_iter()
/opt/rust/src/libsyntax/fold.rs:1029                 .map(|m| ProvidedMethod(m)).collect()
/opt/rust/src/libsyntax/fold.rs:1028:13: 1029:44 note: overflowed on struct ast::StructField_ field kind type: ast::StructFieldKind
/opt/rust/src/libsyntax/fold.rs:1028             folder.fold_method(method).into_iter()
/opt/rust/src/libsyntax/fold.rs:1029                 .map(|m| ProvidedMethod(m)).collect()

Manishearth · 2015-02-27T07:11:34Z

Full log

Looks like they were caused during make check for various crates

pnkfelix · 2015-02-28T07:10:57Z

weird! Okay, I'll look into that.

pnkfelix · 2015-02-28T07:12:08Z

@bors r-

pnkfelix · 2015-02-28T08:41:39Z

@Manishearth wow, I totally failed to make rustc-stage2 (and apparently nothing in run-pass has a structure that exercises something like this for make check-stage1-rpass...) ; sorry about that!

Manishearth · 2015-02-28T08:45:02Z

Hah. I don't think anyone expects rustc-stage2 from anything but large PRs.

So, this PR needs rustc-stage2 to be tested properly? I don't envy your next few days 😬 (I had to do the same for -Z extra-plugins)

pnkfelix · 2015-02-28T08:46:07Z

@Manishearth no, now that I know about it, I can make a test applicable for the stage1 compiler (and put it into run-pass). (Also, make check-stage1 would have caught this; but not check-stage1-rpass)

Manishearth · 2015-02-28T08:47:25Z

That sounds less painful 😃

pnkfelix · 2015-02-28T15:54:28Z

Reduced test case:

#![allow(non_camel_case_types)]

pub fn noop_fold_impl_item() -> SmallVector<ImplItem> {
    loop  { }
}

pub struct SmallVector<T>(P<T>);
pub struct ImplItem(P<S01_Method>);

struct P<T>(Box<T>);

struct S01_Method(P<S02_Generics>);
struct S02_Generics(P<S03_TyParam>);
struct S03_TyParam(P<S04_TyParamBound>);
struct S04_TyParamBound(S05_PolyTraitRef);
struct S05_PolyTraitRef(S06_TraitRef);
struct S06_TraitRef(S07_Path);
struct S07_Path(Vec<S08_PathSegment>);
struct S08_PathSegment(S09_PathParameters);
struct S09_PathParameters(P<S10_ParenthesizedParameterData>);
struct S10_ParenthesizedParameterData(Option<P<S11_Ty>>);
struct S11_Ty(P<S12_Expr>);
struct S12_Expr(P<S13_Block>);
struct S13_Block(Vec<P<S14_Stmt>>);
struct S14_Stmt(P<S15_Decl>);
struct S15_Decl(P<S16_Local>);
struct S16_Local(P<S17_Pat>);
struct S17_Pat(P<S18_Mac>);
struct S18_Mac(Vec<P<S19_TokenTree>>);
struct S19_TokenTree(P<S20_Token>);
struct S20_Token(P<S21_Nonterminal>);
struct S21_Nonterminal(P<S22_Item>);
struct S22_Item(P<S23_EnumDef>);
struct S23_EnumDef(Vec<P<S24_Variant>>);
struct S24_Variant(P<S25_VariantKind>);
struct S25_VariantKind(P<S26_StructDef>);
struct S26_StructDef(Vec<P<S27_StructField>>);
struct S27_StructField(P<S28_StructFieldKind>);
struct S28_StructFieldKind;

pub fn main() {}

bors · 2015-02-28T16:24:38Z

☔ The latest upstream changes (presumably #22895) made this pull request unmergeable. Please resolve the merge conflicts.

pnkfelix · 2015-02-28T23:56:53Z

So, after walking through the debug log, I see that a likely problem here is that I am incrementing the recursion counter even for the recursion that descends from struct A(B); to the definition of struct B { ... }. So the counter is being increased too fast in this analysis, and even simple programs like the one above (which was derived from the libsyntax crate) will fail to compile.

BUT that kind of recursive descent is just standard traversal over the inductive structure of the type; i.e., it cannot lead to infinite loops.

The only kind of traversal that can lead to infinite loops are those that go through references, i.e. cases like &B, Box, Vec, ....; such references fall into two categories: non-owning references and owning references. Non-owning references like &B are ignored by dropck. Owning references are captured by Box and PhantomData (and in the future, Box should just be another instance of PhantomData.

SO: For the short term, my plan is to keep a separate counter that is incremented only when the recursion traverses through an owning reference, as outlined above.

For the long term, however, I am a little worried that such an approach does not scale up properly. I.e. one is still going to be able to make programs (probably real programs) that will exceed the threshold, and I am not convinced the solution of "just tell such crates to increase the value of the recursion counter" will be satisfying in practice.

Instead of just using a fixed recursion limit, we may want to instead make the recursion threshold a function of the number of nodes in the AST, or some similar value that can be easily derived from the static text. E.g. we instead made the threshold where we signal an error be equal to #nodes * recursion_limit (where we of course would use saturated multiply there, and perhaps even 64-bit arithmetic for it).

Anyway, that's just a stray thought. For this PR, I'm certainly going to take the short-cut of just not increasing this counter so fast.

pnkfelix · 2015-03-01T08:47:32Z

hmm, my simplistic attempt to apply the strategy from the previous comment does not seem to actually catch the test from #22443

Update: ah, I somehow forgot that we still treat Box specially and thus the PhantomData in its definition does not yet have an effect here.

Count recursion across phantom data separately from all recursion, and treat `Box<T>` just as if it were carrying `PhantomData<T>`. (Regression tests are in followup commit.) The practical effect of this is just to increment the `xref_depth` counter, the same way that `Vec` and other types carrying `PhantomData` do.

Fix rust-lang#22443.

pnkfelix · 2015-03-01T16:35:41Z

@bors r=nikomatsakis

bors · 2015-03-01T16:35:43Z

@bors r=pnkfelix 180ef47

pnkfelix · 2015-03-01T16:39:28Z

(Note again for rollup builders: I marked this as rollup, but do note that it adds a new error code, which increases its chances for collision with another PR that also adds the same error code, especially since the same error code might be added in a different file. On the bright side, I did run make check-stage2 ahead of time this time. :) )

pnkfelix · 2015-03-01T16:47:19Z

@bors r=nikomatsakis 180ef47

Check for unbounded recursion during dropck. Such recursion can be introduced by the erroneous use of non-regular types (aka types employing polymorphic recursion), which Rust does not support. Fix rust-lang#22443

rust-highfive assigned nikomatsakis Feb 24, 2015

nikomatsakis reviewed Feb 24, 2015
View reviewed changes

pnkfelix force-pushed the issue-22443 branch from 2369945 to ed18e6b Compare February 26, 2015 14:54

steveklabnik mentioned this pull request Feb 26, 2015

Rollup of 11 pull requests #22842

Closed

pnkfelix force-pushed the issue-22443 branch from ed18e6b to 1471a1a Compare March 1, 2015 00:58

pnkfelix added 2 commits March 1, 2015 11:15

Add regression tests for issue 22443.

180ef47

Fix rust-lang#22443.

pnkfelix force-pushed the issue-22443 branch from 1471a1a to 180ef47 Compare March 1, 2015 10:16

bors merged commit 180ef47 into rust-lang:master Mar 2, 2015

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Check for unbounded recursion during dropck #22777

Check for unbounded recursion during dropck #22777

pnkfelix commented Feb 24, 2015

rust-highfive commented Feb 24, 2015

nikomatsakis Feb 24, 2015

pnkfelix Feb 24, 2015

nikomatsakis Feb 25, 2015

pnkfelix Feb 25, 2015

nikomatsakis commented Feb 25, 2015

pnkfelix commented Feb 26, 2015

pnkfelix commented Feb 26, 2015

Manishearth commented Feb 27, 2015

Manishearth commented Feb 27, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

Manishearth commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

Manishearth commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

bors commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Mar 1, 2015

pnkfelix commented Mar 1, 2015

bors commented Mar 1, 2015

pnkfelix commented Mar 1, 2015

pnkfelix commented Mar 1, 2015

Check for unbounded recursion during dropck #22777

Check for unbounded recursion during dropck #22777

Conversation

pnkfelix commented Feb 24, 2015

rust-highfive commented Feb 24, 2015

nikomatsakis Feb 24, 2015

Choose a reason for hiding this comment

pnkfelix Feb 24, 2015

Choose a reason for hiding this comment

nikomatsakis Feb 25, 2015

Choose a reason for hiding this comment

pnkfelix Feb 25, 2015

Choose a reason for hiding this comment

nikomatsakis commented Feb 25, 2015

pnkfelix commented Feb 26, 2015

pnkfelix commented Feb 26, 2015

Manishearth commented Feb 27, 2015

Manishearth commented Feb 27, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

Manishearth commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

Manishearth commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

bors commented Feb 28, 2015

pnkfelix commented Feb 28, 2015

pnkfelix commented Mar 1, 2015

pnkfelix commented Mar 1, 2015

bors commented Mar 1, 2015

pnkfelix commented Mar 1, 2015

pnkfelix commented Mar 1, 2015