How uniq Works

Following is part of the manual page for the BSD version of uniq. The challenge program in this chapter will only implement the reading of a file or STDIN, writing to a file or STDOUT, and counting the lines for the -c flag:

UNIQ(1)                   BSD General Commands Manual                  UNIQ(1)

NAME
     uniq -- report or filter out repeated lines in a file

SYNOPSIS
     uniq [-c | -d | -u] [-i] [-f num] [-s chars] [input_file [output_file]]

DESCRIPTION
     The uniq utility reads the specified input_file comparing adjacent lines,
     and writes a copy of each unique input line to the output_file.  If
     input_file is a single dash ('-') or absent, the standard input is read.
     If output_file is absent, standard output is used for output.  The second
     and succeeding copies of identical adjacent input lines are not written.
     Repeated lines in the input will not be detected if they are not adja-
     cent, so it may be necessary to sort the files first.

     The following options are available:

     -c      Precede each output line with the count of the number of times
             the line occurred in the input, followed by a single space.

     -d      Only output lines that are repeated in the input.

     -f num  Ignore the first num fields in each input line when doing compar-
             isons.  A field is a string of non-blank characters separated
             from adjacent fields by blanks.  Field numbers are one based,
             i.e., the first field is field one.

     -s chars
             Ignore the first chars characters in each input line when doing
             comparisons.  If specified in conjunction with the -f option, the
             first chars characters after the first num fields will be
             ignored.  Character numbers are one based, i.e., the first char-
             acter is character one.

     -u      Only output lines that are not repeated in the input.

     -i      Case insensitive comparison of lines.

In the 06_uniq directory of the Git repository, you will find various input files I’ll use for testing. To start, note that uniq will print nothing when given an empty file:

$ uniq tests/inputs/empty.txt

Given a file with just one line, the one line will be printed:

$ uniq tests/inputs/one.txt
a

It will also print the number of times a line occurs before the line when run with the -c option. The count is right-justified in a field 4 characters wide and is followed by a single space and then the line:

$ uniq -c tests/inputs/one.txt
   1 a

Given input that contains two duplicate lines, only one line will be emitted:

$ cat tests/inputs/two.txt
a
a
$ uniq tests/inputs/two.txt
a

The line is shown to have a count of 2:

$ uniq -c tests/inputs/two.txt
   2 a

A longer input file shows that uniq only considers the lines in order and not globally as the line one shows several times in this input file:

$ cat tests/inputs/three.txt
a
a
b
b
a
c
c
c
a
d
d
d
d

When counting, uniq starts over at 1 each time it sees a new string:

$ uniq -c tests/inputs/three.txt
   2 a
   2 b
   1 a
   3 c
   1 a
   4 d

If you wanted actually unique values, you must first sort the input. Note in the following command that uniq will read STDIN by default:

$ sort tests/inputs/three.txt | uniq -c
   4 a
   2 b
   3 c
   4 d

The file tests/inputs/skip.txt contains a blank line in the input acts just like any other value and so it will reset the counter:

$ uniq -c tests/inputs/skip.txt
   1 a
   1
   1 a
   1 b

If you study the usage closely, you’ll see a very subtle indication of how to write the output to a file. Notice how input and output in the following are grouped inside square brackets to indicate that they are optional as a pair. That is, if you provide input, then you may also optionally provide output:

usage: uniq [-c | -d | -u] [-i] [-f fields] [-s chars] [input [output]]

For example, I can count tests/inputs/two.txt and place the output into out:

$ uniq -c tests/inputs/two.txt out
$ cat out
      2 a

With no positional arguments, uniq will read from STDIN by default:

$ cat tests/inputs/two.txt | uniq -c
      2 a

If you want to read from STDIN and indicate the output filename, you must use a dash (“-” for the input filename:

$ cat tests/inputs/two.txt | uniq -c - out
$ cat out
      2 a

The GNU version works basically the same while also providing many more options:

$ uniq --help
Usage: uniq [OPTION]... [INPUT [OUTPUT]]
Filter adjacent matching lines from INPUT (or standard input),
writing to OUTPUT (or standard output).

With no options, matching lines are merged to the first occurrence.

Mandatory arguments to long options are mandatory for short options too.
  -c, --count           prefix lines by the number of occurrences
  -d, --repeated        only print duplicate lines, one for each group
  -D, --all-repeated[=METHOD]  print all duplicate lines
                          groups can be delimited with an empty line
                          METHOD={none(default),prepend,separate}
  -f, --skip-fields=N   avoid comparing the first N fields
      --group[=METHOD]  show all items, separating groups with an empty line
                          METHOD={separate(default),prepend,append,both}
  -i, --ignore-case     ignore differences in case when comparing
  -s, --skip-chars=N    avoid comparing the first N characters
  -u, --unique          only print unique lines
  -z, --zero-terminated  end lines with 0 byte, not newline
  -w, --check-chars=N   compare no more than N characters in lines
      --help     display this help and exit
      --version  output version information and exit

A field is a run of blanks (usually spaces and/or TABs), then non-blank
characters.  Fields are skipped before chars.

Note: 'uniq' does not detect repeated lines unless they are adjacent.
You may want to sort the input first, or use 'sort -u' without 'uniq'.
Also, comparisons honor the rules specified by 'LC_COLLATE'.

As you can see, both the BSD and GNU versions have many more options, but this is as much as the challenge program is expected to implement.

Getting Started

Just so there are no surprises, this program will be called uniqr for a Rust version of uniq. Start by running cargo new uniqr to create a new binary package, then modify your Cargo.toml to add the following dependencies:

[dependencies]
clap = "2.33"

[dev-dependencies]
assert_cmd = "1"
predicates = "1"
tempfile = "3"
rand = "0.8"

Copy my 06_uniqr/tests directory into your projects, and then run cargo test to ensure the program compiles and that the tests run and fail.

fn main() {
    if let Err(e) = uniqr::get_args().and_then(uniqr::run) {
        eprintln!("{}", e);
        std::process::exit(1);
    }
}

use clap::{App, Arg};
use std::error::Error;

type MyResult<T> = Result<T, Box<dyn Error>>;

#[derive(Debug)]
pub struct Config {
    in_file: String, 
    out_file: Option<String>, 
    count: bool, 
}

pub fn get_args() -> MyResult<Config> {
    let matches = App::new("uniq")
        .version("0.1.0")
        .author("Ken Youens-Clark <[email protected]>")
        .about("Rust uniq")
        // What goes here?
        .get_matches();

    Ok(Config {
        in_file: ...
        out_file: ...
        count: ...
    })
}

pub fn run(config: Config) -> MyResult<()> {
    println!("{:?}", config);
    Ok(())
}

$ cargo run -- -h
uniqr 0.1.0
Ken Youens-Clark <[email protected]>
Rust uniq

USAGE:
    uniqr [FLAGS] [ARGS]

FLAGS:
    -c, --count      Show counts 
    -h, --help       Prints help information
    -V, --version    Prints version information

ARGS:
    <FILE>    Input file [default: -] 
    <FILE>    Output file 

$ cargo run
Config { in_file: "-", out_file: None, count: false }

$ cargo run -- tests/inputs/one.txt out --count
Config { in_file: "tests/inputs/one.txt", out_file: Some("out"), count: true }

pub fn get_args() -> MyResult<Config> {
    let matches = App::new("uniq")
        .version("0.1.0")
        .author("Ken Youens-Clark <[email protected]>")
        .about("Rust uniq")
        .arg(
            Arg::with_name("in_file")
                .value_name("FILE")
                .help("Input file")
                .default_value("-"),
        )
        .arg(
            Arg::with_name("out_file")
                .value_name("FILE")
                .help("Output file"),
        )
        .arg(
            Arg::with_name("count")
                .value_name("COUNT")
                .help("Show counts")
                .short("c")
                .long("count")
                .takes_value(false),
        )
        .get_matches();

    Ok(Config {
        in_file: matches.value_of("in_file").map(str::to_string).unwrap(), 
        out_file: matches.value_of("out_file").map(String::from), 
        count: matches.is_present("count"), 
    })
}

use assert_cmd::Command;
use predicates::prelude::*;
use rand::{distributions::Alphanumeric, Rng};
use std::fs;
use tempfile::NamedTempFile; 

type TestResult = Result<(), Box<dyn std::error::Error>>;

struct Test<'a> { 
    input: &'a str,
    out: &'a str,
    out_count: &'a str,
}

error[E0106]: missing lifetime specifier
 --> tests/cli.rs:8:12
  |
8 |     input: &str,
  |            ^ expected named lifetime parameter
  |
help: consider introducing a named lifetime parameter
  |
7 | struct Test<'a> {
8 |     input: &'a str,

const PRG: &str = "uniqr"; 

const EMPTY: Test = Test {
    input: "tests/inputs/empty.txt", 
    out: "tests/inputs/empty.txt.out", 
    out_count: "tests/inputs/empty.txt.c.out", 
};

fn run(test: &Test) -> TestResult { 
    let expected = fs::read_to_string(test.out)?; 
    Command::cargo_bin(PRG)? 
        .arg(test.input)
        .assert()
        .success()
        .stdout(expected);
    Ok(())
}

fn run_count(test: &Test) -> TestResult {
    let expected = fs::read_to_string(test.out_count)?; 
    Command::cargo_bin(PRG)?
        .args(&[test.input, "-c"]) 
        .assert()
        .success()
        .stdout(expected);
    Ok(())
}

fn run_stdin(test: &Test) -> TestResult {
    let input = fs::read_to_string(test.input)?; 
    let expected = fs::read_to_string(test.out)?; 
    Command::cargo_bin(PRG)? 
        .write_stdin(input)
        .assert()
        .success()
        .stdout(expected);
    Ok(())
}

fn run_stdin_count(test: &Test) -> TestResult {
    let input = fs::read_to_string(test.input)?;
    let expected = fs::read_to_string(test.out_count)?;
    Command::cargo_bin(PRG)? 
        .arg("--count")
        .write_stdin(input)
        .assert()
        .success()
        .stdout(expected);
    Ok(())
}

fn run_outfile(test: &Test) -> TestResult {
    let expected = fs::read_to_string(test.out)?;
    let outfile = NamedTempFile::new()?; 
    let outpath = &outfile.path().to_str().unwrap(); 

    Command::cargo_bin(PRG)? 
        .args(&[test.input, outpath])
        .assert()
        .success()
        .stdout("");
    let contents = fs::read_to_string(&outpath)?; 
    assert_eq!(&expected, &contents); 

    Ok(())
}

$ cat mk-outs.sh
#!/usr/bin/env bash

ROOT="tests/inputs"
OUT_DIR="tests/expected"

[[ ! -d "$OUT_DIR" ]] && mkdir -p "$OUT_DIR"

# Cf https://github.com/coreutils/coreutils/blob/master/tests/misc/uniq.pl
echo -ne "a
a
"    > $ROOT/t1.txt 
echo -ne "a
a"      > $ROOT/t2.txt 
echo -ne "a
b"      > $ROOT/t3.txt 
echo -ne "a
a
b"   > $ROOT/t4.txt 
echo -ne "b
a
a
" > $ROOT/t5.txt 
echo -ne "a
b
c
" > $ROOT/t6.txt 

for FILE in $ROOT/*.txt; do
    BASENAME=$(basename "$FILE")
    uniq      $FILE > ${OUT_DIR}/${BASENAME}.out
    uniq -c   $FILE > ${OUT_DIR}/${BASENAME}.c.out
    uniq    < $FILE > ${OUT_DIR}/${BASENAME}.stdin.out
    uniq -c < $FILE > ${OUT_DIR}/${BASENAME}.stdin.c.out
done

fn open(filename: &str) -> MyResult<Box<dyn BufRead>> {
    match filename {
        "-" => Ok(Box::new(BufReader::new(io::stdin()))),
        _ => Ok(Box::new(BufReader::new(File::open(filename)?))),
    }
}

use clap::{App, Arg};
use std::{ 
    error::Error,
    fs::File,
    io::{self, BufRead, BufReader},
};

pub fn run(config: Config) -> MyResult<()> {
    let mut file = open(&config.in_file)
        .map_err(|e| format!("{}: {}", config.in_file, e))?; 
    let mut line = String::new(); 
    loop { 
        let bytes = file.read_line(&mut line)?; 
        if bytes == 0 { 
            break;
        }
        print!("{}", line); 
        line.clear(); 
    }
    Ok(())
}

$ cargo run -- tests/inputs/one.txt
a

$ cargo run -- - < tests/inputs/one.txt
a

Solution

I’ll step you through how I arrived at a solution. Your version may be different, but it’s fine as long as it passes the test suite. Building on the last version I showed, I decided to create two additional mutable variables to hold the last line of text and the running count. For now, I will always print the count to make sure it’s working correctly:

pub fn run(config: Config) -> MyResult<()> {
    let mut file = open(&config.in_file)
        .map_err(|e| format!("{}: {}", config.in_file, e))?;
    let mut line = String::new();
    let mut last = String::new(); 
    let mut count: u64 = 0; 

    loop {
        let bytes = file.read_line(&mut line)?;
        if bytes == 0 {
            break;
        }

        if line.trim_end() != last.trim_end() { 
            if count > 0 { 
                print!("{:>4} {}", count, last); 
            }
            last = line.clone(); 
            count = 0; 
        }

        count += 1; 
        line.clear();
    }

    if count > 0 { 
        print!("{:>4} {}", count, last);
    }

    Ok(())
}

Create a mutable variable to hold the last line of text.

Create a mutable variable to hold the count.

Compare the current line to the last time, both trimmed of any possible trailing whitespace.

Only print the output when count is greater than 0.

Print the count right-justified in a column 4 characters wide followed by a space and the line value.

Set the last variable to a copy of the current line.

Reset the counter to 0.

Increment the counter by 1.

Handle the last line of the file.

If I run cargo test, this will pass a goodly number of tests. This code is clunky, though. I don’t like having to check if count > 0 twice as it violates the don’t repeat yourself (DRY) principle, so I’m thinking that needs to be put into a function. I’m also always printing the count, but I should only print this when config.count is true—another condition that could go into this function. I decided to write this as a closure inside the run function to close around the config.count value:

let print = |count: &u64, line: &String| { 
    if count > &0 { 
        if config.count { 
            print!("{:>4} {}", &count, &line); 
        } else {
            print!("{}", &line); 
        }
    };
};

The print closure will accept count and line values.

Only print if the count is greater than 0.

Check if the config.count value is true.

Use the print! macro to print the count and line to STDOUT.

Otherwise, print the line to STDOUT.

I can update the rest of the function to use this closure:

loop {
    let bytes = file.read_line(&mut line)?;
    if bytes == 0 {
        break;
    }

    if line.trim_end() != last.trim_end() {
        print(&count, &last);
        last = line.clone();
        count = 0;
    }

    count += 1;
    line.clear();
}

print(&count, &last);

With these changes, my program will pass several more tests. If I look at the failed tests, they all contain outfile because I’m failing to write a named output file. I can add this last feature with two changes. First, I would like to open the output file in the same way as I open the input file by either creating a named output file or by using STDOUT. You’ll need to add use std::io::Write for the following code, which you can place just just after the file variable:

let mut out_file: Box<dyn Write> = match &config.out_file { 
    Some(out_name) => Box::new(File::create(&out_name)?), 
    _ => Box::new(io::stdout()), 
};

The mutable out_file will be a boxed value that implements the std::io::Write trait.

When config.out_file is Some filename, use File::create to try to create the file.

Otherwise, use std::io::stdout.

If you follow the documentation for both File::create and io::stdout, you’ll see both have a Traits section showing the various traits they implement. Both show that they implement Write, and so they satisfy the type requirement Box<dyn Write> which says that the value inside the Box must implement this trait.

The second change I need to make is to use out_file for the output. I will replace the print! macro with write! to write the output to a stream like a filehandle or STDOUT. The first argument to write! must be a mutable value that implements the Write trait. The documentation shows that write! will return a std::io::Result because it might fail. As such, I changed my print closure to return MyResult. Here is the final version of my run function that passes all the tests:

pub fn run(config: Config) -> MyResult<()> {
    let mut file = open(&config.in_file)
        .map_err(|e| format!("{}: {}", config.in_file, e))?; 
    let mut out_file: Box<dyn Write> = match &config.out_file { 
        Some(out_name) => Box::new(File::create(&out_name)?),
        _ => Box::new(io::stdout()),
    };

    let mut print = |count: &u64, line: &String| -> MyResult<()> { 
        if count > &0 {
            if config.count {
                write!(out_file, "{:>4} {}", &count, &line)?;
            } else {
                write!(out_file, "{}", &line)?;
            }
        };
        Ok(())
    };

    let mut line = String::new();
    let mut last = String::new();
    let mut count: u64 = 0;
    loop {
        let bytes = file.read_line(&mut line)?;
        if bytes == 0 {
            break;
        }

        if line.trim_end() != last.trim_end() {
            print(&count, &last)?; 
            last = line.clone();
            count = 0;
        }

        count += 1;
        line.clear();
    }

    print(&count, &last)?; 

    Ok(())
}

Open either STDIN or the given input filename.

Open either STDOUT or the given output filename.

Create a mutable print closure to format the output.

Use the print closure to possibly print output. Use ? to propagate potential errors.

Handle the last line of the file.

I would think it’s highly unlikely that you would independently write something exactly like my solution. As long as your solution passes the tests, it’s perfectly acceptable. Part of what I like about writing with tests is that there is an objective determination when a program meets some level of specifications. Louis Srygley says, “Without requirements or design, programming is the art of adding bugs to an empty text file.” I would say that tests are the requirements made incarnate. Without tests, you simply have no way to know when a change to your program strays from the requirements or breaks the design.

In closing, I would share that I explored a couple of other ways to write this algorithm, one of which read all the lines of the input file into a vector and looked at pairs of lines using Vec::windows. This was interesting but could fail if the size of the input file exceeded the available memory on my machine. The solution presented here will only ever allocate memory for the current and last lines and so should scale to any size file.

Going Further

As usual, the BSD and GNU versions of uniq both have many more features than I chose to include in the challenge. I would encourage you to add all the features you would like to have in your version. Consider reading the original source code and tests to see what you can borrow. Be sure to add tests for each feature, and always run the entire test suite to verify that all previous features still work.

In my mind, uniq is closely tied with sort as I often use them together. Consider implementing your own version of sort, at least to the point of sorting values lexicographically (in dictionary order) or numerically.

Summary

I hope you found this challenge as interesting to write as I did. Let’s review some of the things you learned:

• You can now open a new file for writing or use STDOUT.

• The idea of DRY is that you move any duplicated code into a single abstraction like a function or a closure.

• You’ve seen that a closure can be used to capture values from the enclosing scope.

• You learned about the Write trait and how values that implement this trait can be used with the write! and writeln! macros.

• Sometimes you will find you need to write a temporary file. You’ve now used a Rust crate that helps find a unique filename and open a filehandle for you.

• The Rust compiler may sometimes require you to indicate the lifetime of a variable which is how long it lives in relation to other variables.