How does awk '!a[$0]++' work?

Question

This one-liner removes duplicate lines from text input without pre-sorting.

For example:

$ cat >f
q
w
e
w
r
$ awk '!a[$0]++' <f
q
w
e
r
$ 

The original code I have found on the internets read:

awk '!_[$0]++'

This was even more perplexing to me as I took _ to have a special meaning in awk, like in Perl, but it turned out to be just a name of an array.

Now, I understand the logic behind the one-liner: each input line is used as a key in a hash array, thus, upon completion, the hash contains unique lines in the order of arrival.

What I would like to learn is how exactly this notation is interpreted by awk. E.g. what the bang sign (!) means and the other elements of this code snippet.

How does it work?

Answer 1

Here is a "intuitive" answer, for a more in depth explanation of awk's mechanism see either @Cuonglm's

In this case, !a[$0]++, the post-increment ++ can be set aside for a moment, it does not change the value of the expression. So, look at only !a[$0]. Here:

a[$0]

uses the current line $0 as key to the array a, taking the value stored there. If this particular key was never referenced before, a[$0] evaluates to the empty string.

!a[$0]

The ! negates the value from before. If it was empty or zero (false), we now have a true result. If it was non-zero (true), we have a false result. If the whole expression evaluated to true, meaning that a[$0] was not set to begin with, the whole line is printed as the default action.

Also, regardless of the old value, the post-increment operator adds one to a[$0], so the next time the same value in the array is accessed, it will be positive and the whole condition will fail.

Answer 2

Here is the processing:

• a[$0]: look at the value of key $0, in associative array a. If it does not exist, automatically create it with an empty string.

• a[$0]++: increment the value of a[$0], return the old value as value of expression. The ++ operator returns a numeric value, so if a[$0] was empty to begin with, 0 is returned and a[$0] incremented to 1.

• !a[$0]++: negate the value of expression. If a[$0]++ returned 0 (a false value), the whole expression evaluates to true, and makes awk perform the default action print $0. Otherwise, if the whole expression evaluates to false, no further action is taken.

References:

• Expression in awk
• gawk - Increment and Decrement Operators

With gawk, we can use dgawk (or awk --debug with newer version) to debug a gawk script. First, create a gawk script, named test.awk:

BEGIN {                                                                         
    a = 0;                                                                      
    !a++;                                                                       
}

Then run:

dgawk -f test.awk

or:

gawk --debug -f test.awk

In debugger console:

$ dgawk -f test.awk
dgawk> trace on
dgawk> watch a
Watchpoint 1: a
dgawk> run
Starting program: 
[     1:0x7fe59154cfe0] Op_rule             : [in_rule = BEGIN] [source_file = test.awk]
[     2:0x7fe59154bf80] Op_push_i           : 0 [PERM|NUMCUR|NUMBER]
[     2:0x7fe59154bf20] Op_store_var        : a [do_reference = FALSE]
[     3:0x7fe59154bf60] Op_push_lhs         : a [do_reference = TRUE]
Stopping in BEGIN ...
Watchpoint 1: a
  Old value: untyped variable
  New value: 0
main() at `test.awk':3
3           !a++;
dgawk> step
[     3:0x7fe59154bfc0] Op_postincrement    : 
[     3:0x7fe59154bf40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;
dgawk>

You can see, Op_postincrement was executed before Op_not.

You can also use si or stepi instead of s or step to see more clearly:

dgawk> si
[     3:0x7ff061ac1fc0] Op_postincrement    : 
3           !a++;
dgawk> si
[     3:0x7ff061ac1f40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;

Answer 3

ah the ubiquitous but also ominous awk duplicate remover

awk '!a[$0]++'

this sweet baby is the love child of awk's power and terseness. the pinacle of awk one liners. short but powerful and arcane all at once. removes duplicates while maintaining order. a feat unachieved by uniq or sort -u which either removes only adjacent duplicates or has to break order to remove duplicates.

here is my attempt to explain how this awk one liner works. i took effort in explaining things so that someone who does not know any awk can still follow along. i hope i was able to do so.

first some pseudo code. what this one liner does is basically the following:

for every line:
  if i have not seen this line before:
    print line
  take note that i have now seen this line

i hope you can see how this removes duplicates while maintaining order.

but how does a loop, an if, a print, and a mechanism for storing and retrieving strings fit in 8 characters of awk code? the answer is implicit.

the loop is implicit.

one of the core design philosophies of awk is that it does implicit loop over every line of input. most code in awk that you write is inside this implicit loop.

the print is implicit

this

awk '!a[$0]++'

is equivalent to this

awk '!a[$0]++ { print $0 }'

$0 is the awk variable for the current line. print $0 means to print the current line.

the if is implict

this thing !a[$0]++ { print $0 } is an awk "rule". a rule consists of a condition and a code block. this !a[$0]++ is the condition and this { print $0 } is the code block.

a typical awk program consists of one or more rules. for every input line awk tests the condition and if it is true it will execute the code block. if the condition is missing then it is implicit true. if the code block is missing then it is implicit { print $0 }.

so this thing !a[$0]++ somehow evaluates to either true or false. if true the line is printed. if false not.

lets look at the pseudo code again

for every line:                            # implicit by awk
  if i have not seen this line before:     # at least we know the boolean part
    print line                             # implicit by awk
  take note that i have now seen this line # ???

we understand the loop, the print, and the if. but how does it work so that it evaluates to false only at duplicate lines? and how does it take note of lines already seen?

let's take apart this beast: !a[$0]++

if you know c or java you should already know some of the symbols. the semantics are identical or at least similar.

the exclamation mark (!) is a negator. it evaluates the expression to a boolean and whatever the result it is negated. if the expression evaluates to true the end result is false and vice versa.

a[..] is an array. an associative array. other languages name it map or dictionary. in awk all arrays are associative arrays. the a has no special meaning. it is just a name for the array. it could just as well be x or eliminatetheduplicate.

$0 is the current line from the input. this is an awk specific variable.

the plus plus (++) is a post increment operator. this operator is a bit tricky because it does two things: the value in the variable is incremented. but the value "returned" for further processing is the original value.

   !        a[         $0       ]        ++
negator   array   current line      post increment

how do they work together?

roughly in this order:

1. $0 is the current line
2. a[$0] is the value in the array for the current line
3. the post increment (++) gets the value from a[$0]; increments and stores it back to a[$0]; then "returns" the original value to the next operator in line which is the negator.
4. the negator (!) gets a value from the ++ which was the original value from a[$0]; it is evaluated to a boolean then negated then passed to the if. the if then decides whether to print the line or not.

so that means whether the line gets printed or not, or in other words: whether the line is a duplicate or not, is ultimately decided by the value in a[$0].

by extension the note taking that this line has already been seen must then happen when ++ stores the incremented value back to a[$0]

lets look at the pseudo code again

for every line:
  if i have not seen this line before:     # read from a[$0]
    print line
  take note that i have now seen this line # write to a[$0]

but if we try to put this thing !a[$0]++ in the pseudo code where do we put it? in the if? what about the take note line?

for every line:
  if !a[$0]++:   # check if have seen and take note at the same time?
    print line

the problem is that this operator ++ does two things. increment the value in the variable but return the original value for further processing.

lets try to take the ++ apart. lets take the entire thing apart.

we start with

result = !a[$0]++

take the negator out

tmp = a[$0]++
result = !tmp

now we take the ++ apart. since it does two things we make two lines out of it.

tmp = a[$0]      # save the original value to use later
a[$0] = tmp + 1  # increment and store in variable
result = !tmp    # continue working with original value

now lets try to put that back in the pseudo code

for every line:
  tmp = a[$0]      # query if have seen line
  a[$0] = tmp + 1  # take note that has seen line
  if !tmp:         # decide whether to print line or not
    print line

so there we have it. we have the loop, the if, the print, the query and the take note. just in a different order than the previous pseudo code.

condensed to 8 characters

!a[$0]++

possible because of awks implicit loop, implicit if, implicit print, and because the ++ does the query and take note at the same time.

remains one question. what is the value of a[$0] for the first line? or for any line that has not been seen before? the answer is again implicit.

any variable that is used for the first time is implicitly declared and initialized to the empty string. so the value of a[$0] for the first line is the empty string. same for any following lines that are seen for the first time.

the ++ is a number operator. if given a string it is converted to a number. the empty string converts to zero. any other string would be interpreted as number by some best effort algorithm.

the ! is a boolean operator. if given a number or a string it is converted to boolean. the number zero is false. the empty string is false. anything else is true.

so that means when a line is seen for the first time then a[$0] is not set. awk does the implicit and it is set to the empty string. the empty string is converted to zero because of ++ then to false because of !. the result from ! is true so the line gets printed. the value in a[$0] is now the number 1 from ++.

if a line is seen the second time then a[$0] is the number 1 which is true and the result from ! is false so it is not printed. the value in a[$0] is now the number 2.

any further encounter of the same line increases the number. since all numbers except zero are true the result from ! is always false so the line never gets printed again.

that is how the duplicates are detected.

TL;DR: it counts how often a line has been seen. if zero then print. if any other number then no print. it can be short because of many implicits.

---

bonus: some variants of the one liner and super short explanation of what it does.

replace $0 (entire line) with $2 (second column) will remove duplicates but only based on the second column

$ cat input 
x y z
p q r
a y b

$ awk '!a[$2]++' input 
x y z
p q r

replace ! (negator) with ==1 (equal to one) will only print lines that are duplicates

$ cat input 
a
b
c
b
c
c

$ awk 'a[$0]++==1' input 
b
c

replace with >0 (greater than zero) and add {print NR":"$0} will print all duplicate lines (other than the original) with line number. NR is a special awk variable containing the line number (record number to be exact).

$ awk 'a[$0]++>0 {print NR":"$0}' input 
4:b
5:c
6:c

to print all duplicate including the original will require much more changes because you have to keep track of past line numbers.

Answer 4

Result

First, the final result. :-)

Whichever expression is written, the only thing that awk needs to know is whether it is true or false. A 0 or an empty string value is understood as false. And any other result is understood as true. So:

awk 'expression' file

Is actually a short hand of:

awk 'expression {print $0}' file

If the expression result is true (for an specific line), that line gets printed. Otherwise, nothing gets printed.
Numerically: 1 prints, 0 don't.

What we need to understand then is what is the end result of the expression, and how do we get there.

Array

The sequence to process the expression !a[$0]++ must start at the most internal part of the expression, like processing parenthesis, we must start at the most internal pair of them, where all is known.

The only thing we do know is the value of $0, the value of the line being processed by awk. That gets used in an associative array a[$0]. Associative because the indexes could be text, not only numeric. The reference to the array at some key (for example a[one] if the line is one) instantiates (creates) the array space in memory to store it. It is also initialized to the empty string (equivalent to a[one]=""). If, in the future, there is another line that also has the value of one (the same key), no new memory is used, as the array position has already been created.

For each unique line in the input file, that line is stored as an index value in the memory. If there are many unique lines, a lot of memory might get used. But that is the trade-off of not having to sort/uniq the input file.

At this point we need to resolve how a !x++ should be processed.

++

This step has raised a lot of controversy in previous posts.
It has been discussed if the next operation is the ++ or the !. And, if the result of the ++ should be used to calculate the !.

I'll try to make it crystal clear.

It is clear from the operator precedence table that at the third level are the ++ and -- and pretty lower, at the 5 th level, the +, - and !.

In the same way as a 2+3*4 must be carried out in the order of precedence: first multiply 3 by 4 and to result of that expression add 2. Why first multiply? Because it is higher in the precedence table, and then add as it is at the lowest (last) level.

The ++ is higher than ! and must be applied first. There is no way around that IMO.

However, the ++ carry an internal twist. It actually generates two results. One is the value of the variable (technically an lvalue) that is incremented. That ends stored at a memory location. The second one is the value that is given as the result of the expresion as evaluated up to that point. That is given to the next element on the expression:

1. The value of the variable (lvalue) is incremented and stored at its location in memory in the exact same way whether it is a pre-increment ++x or a post-increment x++. It doesn't matter.

2. But the value given as the result of the expression x++ or ++x is different. In one: x++, the result of the expression, and the value used for the next operator in the written expression is before being incremented. Or, said the other way around (but not necessarily the sequence of what happens) is: the value is incremented after it is used in the expression. With the ++x the sequence and explanation is the other way around.

The reason on why the exact sequence might not be exactly defined is because, in most implementations, the order of the actions is:

1. Retrieve the value of the variable (lvalue) and place it in a register (assume A).
2. Apply the ++ operator, which, as I explained above must result in two values (on post-increment):

• Copy the value in register A to register B.
• Increment register B.

The two values are the results in register A and B.

3. Some languages immediately store the value in register B into memory, And:

4. Carry on with the expression using the value on register A.

5. Some languages wait until all the parts of the expression have been evaluated (in the hopes that the value in the register B is used again somewhere in the expression and doesn't need to be retrieved again from memory) and then return the value in register B to memory.

But what should be clear by now is that the ++ is applied first.

!

Then, on the non-incremented value (for a post-increment) we apply the !.
If the value of a[$0] was null (started as empty) it is negated and generates a 1. With a result of 1, the line gets printed.

If the array element a[$0] has already been seen, the value stored at that array position is the result of a previous post-increment, so, it is numeric and greater than 0. The first time, the zero (equivalent to the empty string) is incremented to 1 and that is what the a[$0] contains. On successive lines it might be incremented to bigger numbers (unless it overflow) but it won't return to 0. The ! not of any number (except zero) is zero, and the line won't be printed.