3
\$\begingroup\$

I'm trying to get my head around recursion in Rust. I've put together a basic implementation of cat here to play with the basics.

Here's my recursive version:

use std::env;
use std::fs::File;
use std::fmt::Display;
use std::io;
use std::io::BufReader;
use std::io::prelude::*;
use std::path::Path;

const STDIN: &'static str = "-";
const BUFFER_SIZE: usize = 4096;

enum Method {
    File,
    Line,
}

fn main() {
    // skip the first element as it is the program name
    let args = env::args();
    if args.len() == 1 {
        cat(io::stdin(), "stdin", Method::Line);
    } else {
        for arg in args.skip(1) {
            if arg.eq(STDIN) {
                cat(io::stdin(), "stdin", Method::Line);
            } else {
                let path = Path::new(&arg);
                let display = path.display();
                let file = File::open(path)
                    .expect(format!("cat: failed to open: {}", display).as_str());
                cat(file, display, Method::File);
            }
        }
    }
    io::stdout().flush().unwrap();
}

// Read from `input` and print to stdout.
// `name` is used in error messages.
// `m` selects whether to read line-by-line or to read the entire input.
fn cat<R, N>(input: R, name: N, m: Method) where R: Read, N: Display {
    let mut reader = BufReader::with_capacity(BUFFER_SIZE, input);
    cat_recurse(&mut reader, name, m);
}

fn cat_recurse<R, N>(reader: &mut BufReader<R>, name: N, m: Method) where R: Read, N: Display {
    let mut s = String::new();
    let n = match m {
        Method::Line => reader.read_line(&mut s),
        Method::File => reader.read_to_string(&mut s),
    }.expect(format!("cat: failed to open {}", name).as_str());
    if n > 0 {
        print!("{}", s);
        // recurse
        cat_recurse(reader, name, m);
    }
}

I know passing around the Method enum is a bit ugly but it was the best way I could come up with to get the app to work with stdin properly. I'm interested in feedback on the design of the recursion pattern specifically. Does it seem about right or is there a simpler way to represent this that I haven't thought of yet? I'd also appreciate any more general feedback you can offer, but the recursion bit is where I'm trying to learn right now.

\$\endgroup\$
1
\$\begingroup\$
  1. Where clauses go on separate lines; easier to see them as they change the functionality so much.
  2. Move the actual argument skipping near to the comment.
  3. There's no need to call eq; use == instead.
  4. String::as_str can often be avoided, just take a reference via &.
  5. The code always builds the failure string, even when it doesn't fail! To avoid this, use unwrap_or_else, which allows access to the specific error as a closure argument.
  6. Similarly, the code always gets Path::display, even when there is no failure.
  7. There's no need to get the display anyway, the code already has the user-provided arg.
  8. There's no need for Path at all; strings are convertable to OsStr, which is what File::open needs.
  9. The name argument and the Method enum are always correlated one-to-one and they should be combined.
  10. The error text in cat_recursive is incorrect; the file / stdin are already open, this error denotes failure to read from it.
  11. Remove useless comments ("recurse"). As an aside, it was pointed out to me many years ago that the verb form is "recur", and an algorithm is "recursive"; "recurse" isn't really a word.
  12. If you are going to document a function, use Rustdoc formatting.
  13. If you are going to document an argument that is a standalone type, consider documenting the type instead. This is one reason to have types at all - to has a package of related meaning.
use std::{env, io};
use std::fs::File;
use std::io::BufReader;
use std::io::prelude::*;

const STDIN: &'static str = "-";
const BUFFER_SIZE: usize = 4096;

/// Read line-by-line or to read the entire input
enum Method<'a> {
    File(&'a str),
    Line,
}

impl<'a> Method<'a> {
    fn name(&self) -> &str {
        match *self {
            Method::File(name) => name,
            Method::Line => "stdin",
        }
    }
}

fn main() {
    // skip the first element as it is the program name
    let args = env::args().skip(1);
    if args.len() == 0 {
        cat(io::stdin(), Method::Line);
    } else {
        for arg in args {
            if arg == STDIN {
                cat(io::stdin(), Method::Line);
            } else {
                let file = File::open(&arg)
                    .unwrap_or_else(|e| panic!("cat: failed to open {}: {}", &arg, e));
                cat(file, Method::File(&arg));
            }
        }
    }
    io::stdout().flush().unwrap();
}

/// Read from `input` and print to stdout.
fn cat<R>(input: R, m: Method)
    where R: Read,
{
    let mut reader = BufReader::with_capacity(BUFFER_SIZE, input);
    cat_recursive(&mut reader, m);
}

fn cat_recursive<R>(reader: &mut BufReader<R>, m: Method)
    where R: Read,
{
    let mut s = String::new();
    let n = match m {
        Method::Line => reader.read_line(&mut s),
        Method::File(..) => reader.read_to_string(&mut s),
    };
    let n = n.unwrap_or_else(|e| panic!("cat: failed to read {}: {}", m.name(), e));
    if n > 0 {
        print!("{}", s);
        cat_recursive(reader, m);
    }
}

The big points

  1. The algorithm isn't really recursive for files. The entire file is read in via read_to_string. This means that memory is allocated to hold the entire file. Then we recur once to read nothing and end.

  2. When reading line-by-line, the String is reallocated for every call. This will increase memory usage with each call, up to the last call, at which point we will have allocated the entire input size again.

  3. Which leads to the important point: Rust doesn't have tail recursion! Writing an unbounded recursive function is eventually going to end in tears for someone.

  4. Additionally, this cat doesn't support binary files, as it crams everything into a String.

  5. I'm not sure why there are two methods of reading, one for files and one for stdin. Why not always read line-by-line or as one big blob?

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice. The two methods came about because I started with files only, reading directly to a string, then tried to replicate the behaviour of existing cat apps for stdin. I know recursion makes no sense for this problem, I just wanted to play with the idea in rust. \$\endgroup\$ – IanGilham Jan 4 '17 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.