1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
#![deny( missing_docs, missing_debug_implementations, missing_copy_implementations, trivial_casts, trivial_numeric_casts, unsafe_code, unstable_features, unused_import_braces, unused_qualifications )] //! Tailcall is a library that adds safe, zero-cost [tail recursion] to stable Rust. //! Eventually, it will be superseded by the [`become` keyword]. //! //! # Usage //! //! To guarantee that recursive calls a function will reuse the same stack frame, //! annotate it with the [`tailcall`] attribute. //! //! ``` //! use tailcall::tailcall; //! //! fn factorial(input: u64) -> u64 { //! #[tailcall] //! fn factorial_inner(accumulator: u64, input: u64) -> u64 { //! if input > 0 { //! factorial_inner(accumulator * input, input - 1) //! } else { //! accumulator //! } //! } //! //! factorial_inner(1, input) //! } //! ``` //! //! Recursive calls which are not in tail form will result in a compile-time error. //! //! ```compile_fail //! use tailcall::tailcall; //! //! #[tailcall] //! fn factorial(input: u64) -> u64 { //! if input > 0 { //! input * factorial(input - 1) //! } else { //! 1 //! } //! } //! ``` //! //! [tail recursion]: https://en.wikipedia.org/wiki/Tail_call //! [`become` keyword]: https://internals.rust-lang.org/t/pre-rfc-explicit-proper-tail-calls/3797/16 //! [`tailcall`]: attr.tailcall.html extern crate proc_macro; mod helpers; mod transforms; use proc_macro::TokenStream; use quote::quote; use syn::{parse_macro_input, ItemFn}; /// Transforms a [function definition] so that all recursive calls within the body are /// guaranteed to use a single stack frame (via [tail recursion]). /// /// [function definition]: https://docs.rs/syn/1.0.9/syn/struct.ItemFn.html /// [tail recursion]: https://en.wikipedia.org/wiki/Tail_call /// /// # Example /// /// ``` /// use tailcall::tailcall; /// /// fn factorial(input: u64) -> u64 { /// #[tailcall] /// fn factorial_inner(accumulator: u64, input: u64) -> u64 { /// if input > 0 { /// factorial_inner(accumulator * input, input - 1) /// } else { /// accumulator /// } /// } /// /// factorial_inner(1, input) /// } /// ``` /// /// # Requirements /// /// - All recursive calls must be in [tail form]: /// /// ```compile_fail /// use tailcall::tailcall; /// /// #[tailcall] /// fn factorial(input: u64) -> u64 { /// if input > 0 { /// input * factorial(input - 1) /// // ^^^^^^^ This is not allowed. /// } else { /// 1 /// } /// } /// ``` /// /// - Methods (functions which bind `self` in the arguments list) are not supported: /// /// ```compile_fail /// trait Factorialable { /// fn factorial(self) -> Self { /// self.calc_factorial(1) /// } /// /// fn calc_factorial(self, accumulator: u64) -> u64; /// } /// /// impl Factorialable for u64 { /// #[tailcall] /// fn calc_factorial(self, accumulator: u64) -> u64 { /// // ^^^^ This is not allowed. /// if self > 0 { /// (self - 1).calc_factorial(self * accumulator) /// } else { /// accumulator /// } /// } /// } /// ``` /// /// - No identifier with the name `___tailcall___` may appear anywhere within the body: /// /// ```compile_fail /// use tailcall::tailcall; /// /// fn factorial(input: u64) -> u64 { /// #[tailcall] /// fn factorial_inner(accumulator: u64, input: u64) -> u64 { /// mod ___tailcall___ { /// // ^^^^^^^^^^^^^^ This is not allowed. /// pub fn one() -> u64 { /// 1 /// } /// } /// /// if input > 0 { /// factorial_inner(accumulator * input, input - ___tailcall___::one()) /// } else { /// accumulator /// } /// } /// /// factorial_inner(1, input) /// } /// ``` /// /// [tail form]: https://en.wikipedia.org/wiki/Tail_call #[proc_macro_attribute] pub fn tailcall(_attr: TokenStream, tokens: TokenStream) -> TokenStream { let input = parse_macro_input!(tokens as ItemFn); let output = transforms::apply_fn_tailcall_transform(input); TokenStream::from(quote! { #output }) }