This PR represents an attempt to address issue #970. It also represents

a portion of the meta issue for fuzzing #972.

The code base reflected here uses quickcheck to generate C headers that
include a variety of types including basic types, structs, unions,
function
prototypes and function pointers. The headers generated by quickcheck
are
passed to the `csmith-fuzzing/predicate.py` script. Examples of headers
generated by this iteration of the tooling can be viewed
[here](https://gist.github.com/snewt/03ce934f35c5b085807d2d5cf11d1d5c).

At the top of each header are two simple struct definitions,
`whitelistable`
and `blacklistable`. Those types are present in the vector that
represents
otherwise primitive types used to generate. They represent a naive
approach to
exposing custom types without having to intuit generated type names like
`struct_21_8` though _any actual whitelisting logic isn't implemented
here_.

Test success is measured by the success of the
`csmith-fuzzing/predicate.py`
script. This means that for a test to pass the following must be true:
- bindgen doesn't panic
- the resulting bindings compile
- the resulting bindings layout tests pass

```bash
cd tests/property_test
cargo test
```

Some things I'm unsure of:
At the moment it lives in `tests/property_test` but isn't run when
`cargo test`
is invoked from bindgen's cargo manifest directory.

At this point, the source is genereated in ~1 second but the files are
large
enough that it takes the `predicate.py` script ~30 seconds to run
through each
one. In order for the tests to run in under a minute only 2 are
generated by
quickcheck by default. This can be changed in the `test_bindgen`
function of the
`tests/property_test/tests/fuzzed-c-headers.rs` file.

For now the `run_predicate_script` function in the
`tests/property_test/tests/fuzzed-c-headers.rs` file contains a
commented block
that will copy generated source in the `tests/property_test/tests`
directory.
Should it be easier?

There is some logic in the fuzzer that disallows 0 sized arrays because
tests
will regulary fail due to issues documented in #684 and #1153. Should
this be
special casing?

After any iterations the reviewers are interested in required to make
this
a functional testing tool, should/could the fuzzing library be made into
its own
crate? I didn't move in that direction yet because having it all in one
place
seemed like the best way to figure out what works an doesn't but I'm
interested
in whether it might be useful as a standalone library.

I'm looking forward to feedback on how to make this a more useful tool
and one
that provides the right configurability.

Thanks!

r? @fitzgen

4 files changed, 564 insertions, 0 deletions

diff --git a/tests/property_test/Cargo.toml b/tests/property_test/Cargo.toml
new file mode 100644
index 00000000..fa644b4b
--- /dev/null
+++ b/tests/property_test/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "property_test"
+description = "Bindgen property tests. Generate random valid C code and pass it to the csmith/predicate.py script"
+version = "0.1.0"
+authors = ["Shea Newton <snewton@polysync.io>"]
+
+[dependencies]
+quickcheck = "0.4"
+tempdir = "0.3"
+rand = "0.3"
diff --git a/tests/property_test/src/fuzzers.rs b/tests/property_test/src/fuzzers.rs
new file mode 100644
index 00000000..113c9f33
--- /dev/null
+++ b/tests/property_test/src/fuzzers.rs
@@ -0,0 +1,468 @@
+use quickcheck::{Arbitrary, Gen, StdGen};
+use std::fmt;
+use rand::thread_rng;
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct BaseTypeC {
+    pub def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct TypeQualifierC {
+    pub def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct PointerLevelC {
+    pub def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct ArrayDimensionC {
+    pub def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct BasicTypeDeclarationC {
+    pub type_name: String,
+    pub type_qualifier: String,
+    pub pointer_level: String,
+    pub ident_id: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct StructDeclarationC {
+    pub fields: String,
+    pub ident_id: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct UnionDeclarationC {
+    pub fields: String,
+    pub ident_id: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct FunctionPointerDeclarationC {
+    pub type_qualifier: String,
+    pub type_name: String,
+    pub pointer_level: String,
+    pub params: String,
+    pub ident_id: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct FunctionPrototypeC {
+    pub type_qualifier: String,
+    pub type_name: String,
+    pub pointer_level: String,
+    pub params: String,
+    pub ident_id: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct ParameterC {
+    pub type_qualifier: String,
+    pub type_name: String,
+    pub pointer_level: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct ParameterListC {
+    def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+pub struct HeaderC {
+    pub def: String,
+}
+
+#[derive(PartialEq, Debug, Clone)]
+enum DeclarationC {
+    FunctionDecl(FunctionPrototypeC),
+    FunctionPtrDecl(FunctionPointerDeclarationC),
+    StructDecl(StructDeclarationC),
+    UnionDecl(UnionDeclarationC),
+    VariableDecl(BasicTypeDeclarationC),
+}
+
+trait MakeUnique {
+    fn make_unique(&mut self, stamp: usize);
+}
+
+impl MakeUnique for DeclarationC {
+    fn make_unique(&mut self, stamp: usize) {
+        match self {
+            &mut DeclarationC::FunctionDecl(ref mut d) => d.make_unique(stamp),
+            &mut DeclarationC::FunctionPtrDecl(ref mut d) => d.make_unique(stamp),
+            &mut DeclarationC::StructDecl(ref mut d) => d.make_unique(stamp),
+            &mut DeclarationC::UnionDecl(ref mut d) => d.make_unique(stamp),
+            &mut DeclarationC::VariableDecl(ref mut d) => d.make_unique(stamp),
+        }
+    }
+}
+
+impl Arbitrary for DeclarationC {
+    fn arbitrary<G: Gen>(g: &mut G) -> DeclarationC {
+        match usize::arbitrary(g) % 5 {
+            0 => DeclarationC::FunctionDecl(FunctionPrototypeC::arbitrary(g)),
+            1 => DeclarationC::FunctionPtrDecl(FunctionPointerDeclarationC::arbitrary(g)),
+            2 => DeclarationC::StructDecl(StructDeclarationC::arbitrary(g)),
+            3 => DeclarationC::UnionDecl(UnionDeclarationC::arbitrary(g)),
+            _ => DeclarationC::VariableDecl(BasicTypeDeclarationC::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for DeclarationC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            &DeclarationC::FunctionPtrDecl(ref d) => write!(f, "{}", d),
+            &DeclarationC::StructDecl(ref d) => write!(f, "{}", d),
+            &DeclarationC::UnionDecl(ref d) => write!(f, "{}", d),
+            &DeclarationC::VariableDecl(ref d) => write!(f, "{}", d),
+            &DeclarationC::FunctionDecl(ref d) => write!(f, "{}", d),
+        }
+    }
+}
+
+impl Arbitrary for BaseTypeC {
+    fn arbitrary<G: Gen>(g: &mut G) -> BaseTypeC {
+        let base_type = vec![
+            "char",
+            "signed char",
+            "unsigned char",
+            "short",
+            "short int",
+            "signed short",
+            "signed short int",
+            "unsigned short",
+            "unsigned short int",
+            "int",
+            "signed",
+            "signed int",
+            "unsigned",
+            "unsigned int",
+            "long",
+            "long int",
+            "signed long",
+            "signed long int",
+            "unsigned long",
+            "unsigned long int",
+            "long long",
+            "long long int",
+            "signed long long",
+            "signed long long int",
+            "unsigned long long",
+            "unsigned long long int",
+            "float",
+            "double",
+            "long double",
+            "void*",
+            "whitelistable",
+            "blacklistable",
+        ];
+        match base_type.iter().nth(usize::arbitrary(g) % base_type.len()) {
+            Some(s) => BaseTypeC {
+                def: String::from(*s),
+            },
+            None => BaseTypeC {
+                def: String::from("int"),
+            },
+        }
+    }
+}
+
+impl fmt::Display for BaseTypeC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
+
+impl Arbitrary for TypeQualifierC {
+    fn arbitrary<G: Gen>(g: &mut G) -> TypeQualifierC {
+        let qualifier = vec!["const", ""];
+        match qualifier.iter().nth(usize::arbitrary(g) % qualifier.len()) {
+            Some(s) => TypeQualifierC {
+                def: String::from(*s),
+            },
+            None => TypeQualifierC {
+                def: String::from(""),
+            },
+        }
+    }
+}
+
+impl fmt::Display for TypeQualifierC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
+
+impl Arbitrary for PointerLevelC {
+    fn arbitrary<G: Gen>(g: &mut G) -> PointerLevelC {
+        PointerLevelC {
+            def: (0..usize::arbitrary(g)).map(|_| "*").collect::<String>(),
+        }
+    }
+}
+
+impl fmt::Display for PointerLevelC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
+
+impl Arbitrary for ArrayDimensionC {
+    fn arbitrary<G: Gen>(g: &mut G) -> ArrayDimensionC {
+        // keep these small, they clang complains when they get too big
+        let dimensions = usize::arbitrary(g) % 5;
+        let mut def = String::new();
+        // don't allow size 0 dimension until #684 and #1153 are closed
+        for _ in 1..dimensions {
+            def += &format!("[{}]", (usize::arbitrary(g) % 15) + 1);
+        }
+        ArrayDimensionC { def: def }
+    }
+}
+
+impl fmt::Display for ArrayDimensionC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
+
+impl MakeUnique for BasicTypeDeclarationC {
+    fn make_unique(&mut self, stamp: usize) {
+        self.ident_id += &format!("_{}", stamp);
+    }
+}
+
+impl Arbitrary for BasicTypeDeclarationC {
+    fn arbitrary<G: Gen>(g: &mut G) -> BasicTypeDeclarationC {
+        BasicTypeDeclarationC {
+            type_qualifier: TypeQualifierC::arbitrary(g).def,
+            type_name: BaseTypeC::arbitrary(g).def,
+            pointer_level: PointerLevelC::arbitrary(g).def,
+            ident_id: format!("{}", usize::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for BasicTypeDeclarationC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            f,
+            "{} {} {} ident_{};",
+            self.type_qualifier,
+            self.type_name,
+            self.pointer_level,
+            self.ident_id
+        )
+    }
+}
+
+impl MakeUnique for StructDeclarationC {
+    fn make_unique(&mut self, stamp: usize) {
+        self.ident_id += &format!("_{}", stamp);
+    }
+}
+
+impl Arbitrary for StructDeclarationC {
+    fn arbitrary<G: Gen>(g: &mut G) -> StructDeclarationC {
+        let mut fields_string = String::new();
+        // reduce generator size as a method of putting a bound on recursion.
+        // when size < 1 the empty list is generated.
+        let reduced_size: usize = (g.size() / 2) as usize + 1;
+        let mut decls: Vec<DeclarationC> =
+            Arbitrary::arbitrary(&mut StdGen::new(thread_rng(), reduced_size));
+
+        for (i, decl) in decls.iter_mut().enumerate() {
+            match decl {
+                &mut DeclarationC::FunctionDecl(_) => {}
+                decl => {
+                    decl.make_unique(i);
+                    fields_string += &format!("{}", decl);
+                }
+            }
+        }
+
+        StructDeclarationC {
+            fields: fields_string,
+            ident_id: format!("{}", usize::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for StructDeclarationC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "struct {{ {} }} struct_{};", self.fields, self.ident_id)
+    }
+}
+
+impl MakeUnique for UnionDeclarationC {
+    fn make_unique(&mut self, stamp: usize) {
+        self.ident_id += &format!("_{}", stamp);
+    }
+}
+
+impl Arbitrary for UnionDeclarationC {
+    fn arbitrary<G: Gen>(g: &mut G) -> UnionDeclarationC {
+        let mut fields_string = String::new();
+        // reduce generator size as a method of putting a bound on recursion.
+        // when size < 1 the empty list is generated.
+        let reduced_size: usize = (g.size() / 2) as usize + 1;
+        let mut decls: Vec<DeclarationC> =
+            Arbitrary::arbitrary(&mut StdGen::new(thread_rng(), reduced_size));
+
+        for (i, decl) in decls.iter_mut().enumerate() {
+            match decl {
+                &mut DeclarationC::FunctionDecl(_) => {}
+                decl => {
+                    decl.make_unique(i);
+                    fields_string += &format!("{}", decl);
+                }
+            }
+        }
+
+        UnionDeclarationC {
+            fields: fields_string,
+            ident_id: format!("{}", usize::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for UnionDeclarationC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "union {{ {} }} union_{};", self.fields, self.ident_id)
+    }
+}
+
+impl MakeUnique for FunctionPointerDeclarationC {
+    fn make_unique(&mut self, stamp: usize) {
+        self.ident_id += &format!("_{}", stamp);
+    }
+}
+
+impl Arbitrary for FunctionPointerDeclarationC {
+    fn arbitrary<G: Gen>(g: &mut G) -> FunctionPointerDeclarationC {
+        FunctionPointerDeclarationC {
+            type_qualifier: format!("{}", TypeQualifierC::arbitrary(g)),
+            type_name: format!("{}", BaseTypeC::arbitrary(g)),
+            pointer_level: format!("{}", PointerLevelC::arbitrary(g)),
+            params: format!("{}", ParameterListC::arbitrary(g)),
+            ident_id: format!("{}", usize::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for FunctionPointerDeclarationC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            f,
+            "{} {} {} (*func_ptr_{})({});",
+            self.type_qualifier,
+            self.type_name,
+            self.pointer_level,
+            self.ident_id,
+            self.params
+        )
+    }
+}
+
+impl MakeUnique for FunctionPrototypeC {
+    fn make_unique(&mut self, stamp: usize) {
+        self.ident_id += &format!("_{}", stamp);
+    }
+}
+
+impl Arbitrary for FunctionPrototypeC {
+    fn arbitrary<G: Gen>(g: &mut G) -> FunctionPrototypeC {
+        FunctionPrototypeC {
+            type_qualifier: format!("{}", TypeQualifierC::arbitrary(g)),
+            type_name: format!("{}", BaseTypeC::arbitrary(g)),
+            pointer_level: format!("{}", PointerLevelC::arbitrary(g)),
+            params: format!("{}", ParameterListC::arbitrary(g)),
+            ident_id: format!("{}", usize::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for FunctionPrototypeC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            f,
+            "{} {} {} func_{}({});",
+            self.type_qualifier,
+            self.type_name,
+            self.pointer_level,
+            self.ident_id,
+            self.params
+        )
+    }
+}
+
+impl Arbitrary for ParameterC {
+    fn arbitrary<G: Gen>(g: &mut G) -> ParameterC {
+        ParameterC {
+            type_qualifier: format!("{}", TypeQualifierC::arbitrary(g)),
+            type_name: format!("{}", BaseTypeC::arbitrary(g)),
+            pointer_level: format!("{}", PointerLevelC::arbitrary(g)),
+        }
+    }
+}
+
+impl fmt::Display for ParameterC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            f,
+            "{} {} {}",
+            self.type_qualifier,
+            self.type_name,
+            self.pointer_level
+        )
+    }
+}
+
+impl Arbitrary for ParameterListC {
+    fn arbitrary<G: Gen>(g: &mut G) -> ParameterListC {
+        let mut params_string = String::new();
+        let params: Vec<ParameterC> = Arbitrary::arbitrary(g);
+        for (i, p) in params.iter().enumerate() {
+            match i {
+                0 => params_string += &format!("{}", p),
+                _ => params_string += &format!(",{}", p),
+            }
+        }
+
+        ParameterListC { def: params_string }
+    }
+}
+
+impl fmt::Display for ParameterListC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
+
+impl Arbitrary for HeaderC {
+    fn arbitrary<G: Gen>(g: &mut G) -> HeaderC {
+        let known_types = "typedef struct { short s; } whitelistable; \
+                           typedef struct { float f;} blacklistable;";
+        let mut header_c = String::from(known_types);
+        let mut decls: Vec<DeclarationC> = Arbitrary::arbitrary(g);
+
+        for (i, decl) in decls.iter_mut().enumerate() {
+            decl.make_unique(i);
+            header_c += &format!("{}", decl);
+        }
+
+        HeaderC { def: header_c }
+    }
+}
+
+impl fmt::Display for HeaderC {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.def)
+    }
+}
diff --git a/tests/property_test/src/lib.rs b/tests/property_test/src/lib.rs
new file mode 100644
index 00000000..c9bc9053
--- /dev/null
+++ b/tests/property_test/src/lib.rs
@@ -0,0 +1,5 @@
+extern crate quickcheck;
+extern crate rand;
+extern crate tempdir;
+
+pub mod fuzzers;
diff --git a/tests/property_test/tests/fuzzed-c-headers.rs b/tests/property_test/tests/fuzzed-c-headers.rs
new file mode 100644
index 00000000..b132a759
--- /dev/null
+++ b/tests/property_test/tests/fuzzed-c-headers.rs
@@ -0,0 +1,81 @@
+extern crate property_test;
+extern crate quickcheck;
+extern crate rand;
+extern crate tempdir;
+
+use property_test::fuzzers;
+use quickcheck::{QuickCheck, StdGen, TestResult};
+use std::fs::File;
+use std::io::Write;
+use tempdir::TempDir;
+use std::process::{Command, Output};
+use std::path::PathBuf;
+use std::error::Error;
+use rand::thread_rng;
+
+fn run_predicate_script(header: fuzzers::HeaderC, header_name: &str) -> Result<Output, Box<Error>> {
+    let dir = TempDir::new("bindgen_prop")?;
+    let header_path = dir.path().join(header_name);
+
+    let mut header_file = File::create(&header_path)?;
+    header_file.write_all(header.def.as_bytes())?;
+    header_file.sync_all()?;
+
+    let header_path_string;
+    match header_path.into_os_string().into_string() {
+        Ok(s) => header_path_string = s,
+        Err(_) => return Err(From::from("error converting path into String")),
+    }
+
+    let mut predicate_script_path = PathBuf::from(env!("CARGO_MANIFEST_DIR"));
+    predicate_script_path.push("../../csmith-fuzzing/predicate.py");
+
+    let predicate_script_path_string;
+    match predicate_script_path.into_os_string().into_string() {
+        Ok(s) => predicate_script_path_string = s,
+        Err(_) => return Err(From::from("error converting path into String")),
+    }
+
+    // Copy generated temp files to test directory for inspection.
+    // Preserved for anyone interested in validating the behavior.
+
+    // let mut debug_output_path = PathBuf::from(env!("CARGO_MANIFEST_DIR"));
+    // debug_output_path.push("tests");
+    // Command::new("cp")
+    //     .arg("-a")
+    //     .arg(&dir.path().to_str().unwrap())
+    //     .arg(&debug_output_path.to_str().unwrap())
+    //     .output()?;
+
+    Ok(Command::new(&predicate_script_path_string)
+        .arg(&header_path_string)
+        .output()?)
+
+    // omit close, from tempdir crate's docs:
+    // "Closing the directory is actually optional, as it would be done on drop."
+}
+
+fn bindgen_prop(header: fuzzers::HeaderC) -> TestResult {
+    match run_predicate_script(header, "prop_test.h") {
+        Ok(o) => return TestResult::from_bool(o.status.success()),
+        Err(e) => {
+            println!("{:?}", e);
+            return TestResult::from_bool(false);
+        }
+    }
+}
+
+#[test]
+fn test_bindgen() {
+    // enough to generate any value in the PrimitiveTypeC `base_type` list
+    let generate_range: usize = 32;
+    QuickCheck::new()
+        // generating is relatively quick (generate_range 150 takes ~5 seconds)
+        // but running predicate.py takes ~30 seconds per source file / test
+        // when the generation range is just 32. It can take a lot longer with a
+        // higher generate_range. Up the number of tests or generate_range if
+        // you're willing to wait awhile.
+        .tests(2)
+        .gen(StdGen::new(thread_rng(), generate_range))
+        .quickcheck(bindgen_prop as fn(fuzzers::HeaderC) -> TestResult)
+}