cut - cut out selected fields of each line of a file
----------------------------------------------------
markus schnalke <meillo@marmaro.de>
2015-05


Cut ist ein klassisches Programm im Unix-Werkzeugkasten.
In keinem ordentlichen Tutorial zur Shellprogrammierung fehlt
es, denn es ist ein schoenes, praktisches und anschauliches
Helferlein. Hier soll ein wenig hinter seine Fassade geschaut
werden.


Funktionsweise

Urspruenglich hatte cut zwei Modi, die spaeter um einen dritten
erweitert wurden. Cut schneidet entweder gewuenschte Zeichen aus
den Zeilen der Eingabe oder gewuenschte, durch Trennzeichen
definierte, Felder.

Der Zeichenmodus ist optimal geeignet um Festbreitenformate zu
zerteilen. So kann man damit beispielsweise bestimmte
Zugriffsrechte aus der Ausgabe von `ls -l' ausschneiden, in
diesem Beispiel die Rechte des Besitzers:

	$ ls -l foo
	-rw-rw-r-- 1 meillo users 0 May 12 07:32 foo

	$ ls -l foo | cut -c 2-4
	rw-

Oder die Schreibrechte des Besitzers, der Gruppe und der
Welt:

	$ ls -l | cut -c 3,6,9
	ww-

Mit cut lassen sich aber auch Strings kuerzen.

	$ long=12345678901234567890
	$ echo "$long" | cut -c -10
	1234567890

Dieser Befehl gibt die ersten maximal 10 Zeichen von
`$long' aus. (Alternativ kann man hierfuer `printf
"%.10s\n" "$long"' verwenden.)

Geht es aber nicht um die Darstellung von Zeichen, sondern um
ihre Speicherung, dann ist `-c' nicht unbedingt geeignet.
Frueher, als US-ASCII noch die omnipraesente Zeichenkodierung
war, wurde jedes Zeichen mit genau einem
Byte gespeichert. Somit selektierte `cut -c' gleichermassen
sowohl Ausgabezeichen als auch Bytes. Mit dem Aufkommen von
Multibyte-Kodierungen (wie UTF-8) musste man sich jedoch von
dieser Annahme loesen. In diesem Zug bekam cut mit
POSIX.2-1992 einen Bytemodus (Option `-b'). Will man
also nur die ersten maximal 500 Bytes vor dem
Newline-Zeichen stehen haben (und den Rest stillschweigend
ignorieren), dann macht man das mit:

	$ cut -b -500

Den Rest kann man sich mit `cut -b 501-' einfangen. Diese
Funktion ist insbesondere fuer POSIX wichtig, da man so
Textdateien mit begrenzter Zeilenlaenge erzeugen kann.
[ http://pubs.opengroup.org/onlinepubs/9699919799/utilities/cut.html#tag_20_28_17

Wenn auch der Bytemodus neu eingefuehrt worden war, so sollte
er sich doch nur so verhalten wie der alte Zeichenmodus
normalerweise schon implementiert war. Beim Zeichenmodus aber
wurde eine neue Implementierungsweise gefordert. Das Problem
war also nicht, den neuen Bytemodus zu implementieren, sondern
den Zeichenmodus neu zu implementieren.

Neben dem Zeichen- und Bytemodus bietet cut noch den
Feldmodus, den man mit `-f' einleitet. Mit ihm
koennen Felder ausgewaehlt werden. Das Trennzeichen (per
Default der Tab) kann mit `-d' geaendert werden.

Der typische Anwendungsfall fuer cut im Feldmodus ist die
Auswahl von Information aus der passwd-Datei. So z.B. der
Benutzername und seine ID:

	$ cut -d: -f1,3 /etc/passwd
	root:0
	bin:1
	daemon:2
	mail:8
	...

(Die Argumente fuer die Optionen koennen bei cut uebrigens
mit Whitespace abgetrennt oder direkt angehaengt folgen.)

Dieser Feldmodus ist fuer einfache tabellarische Dateien,
wie eben die passwd, gut geeignet. Er kommt aber schnell an
seine Grenzen. Gerade der haeufige Fall, dass an Whitespace
in Felder geteilt werden soll, wird damit nicht abgedeckt.
Der Delimiter kann bei cut nur genau ein Zeichen sein. Es kann
also nicht sowohl an Leerzeichen als auch an Tabs aufgetrennt
werden. Auch unterteilt cut an jedem Trennzeichen. Zwei aneinander
stehende Trennzeichen fuehren zu einem leeren Feld. Dieses
Verhalten widerspricht den Erwartungen, die man an die
Verarbeitung einer Datei mit Whitespace-getrennten Feldern
hat. Manche Implementierungen von cut, z.B. die von FreeBSD,
haben deshalb Erweiterungen, die das gewuenschte Verhalten
fuer Whitespace-getrennte Felder bieten. Ansonsten, d.h. wenn
man portabel bleiben will, verwendet man awk in diesen
Faellen.

Awk bietet noch eine weitere Funktion, die cut missen
laesst: Das Tauschen der Feld-Reihenfolge in der Ausgabe. Bei
cut ist die Reihenfolge der Feldauswahlangabe irrelevant; ein
Feld kann selbst mehrfach angegeben werden. So gibt der Aufruf
von `cut -c 5-8,1,4-6' die Zeichen Nummer 1, 4, 5, 6, 7 und 8
in genau dieser Reihenfolge aus. Die Auswahl entspricht damit
der Mengenlehre in der Mathematik: Jedes angegebene Feld wird
Teil der Ergebnismenge. Die Felder der Ergebnismenge sind
dabei immer gleich geordnet wie in der Eingabe. Um die Worte
der Manpage von Version 8 Unix wiederzugeben: ``In data base
parlance, it projects a relation.''
[ http://man.cat-v.org/unix_8th/1/cut
Cut fuehrt also die Datenbankoperation Projektion auf
Textdateien aus. Die Wikipedia erklaert das folgendermassen:

	Die Projektion entspricht der Projektionsabbildung aus der
	Mengenlehre und kann auch Attributbeschränkung genannt
	werden. Sie extrahiert einzelne Attribute aus der
	ursprünglichen Attributmenge und ist somit als eine Art
	Selektion auf Spaltenebene zu verstehen, das heißt, die
	Projektion blendet Spalten aus. 

[ http://de.wikipedia.org/wiki/Projektion_(Informatik)#Projektion


Geschichtliches

Cut erblickte 1982 mit dem Release von UNIX System III das
Licht der oeffentlichen Welt. Wenn man die Quellen von System
III durchforstet, findet man die Quellcodedatei cut.c mit dem
Zeitstempel 1980-04-11.
[ http://minnie.tuhs.org/cgi-bin/utree.pl?file=SysIII/usr/src/cmd
Das ist die aelteste Manifestation des Programms, die ich
aufstoebern konnte. Allerdings spricht die SCCS-ID im
Quellcode von Version 1.5. Es muss also noch eine
Vorgeschichte geben. Zu dieser habe ich leider keinen Zugang
gefunden.
XXX mail an TUHS

Nun ein Blick auf die BSD-Linie: Dort ist mein fruehester
Fund ein cut.c mit dem Dateimodifikationsdatum 1986-11-07
[ http://minnie.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-UWisc/src/usr.bin/cut
als Teil der Spezialversion 4.3BSD-UWisc,
[ http://gunkies.org/wiki/4.3_BSD_NFS_Wisconsin_Unix
die im Januar 1987 veroeffentlicht wurde.
Die Implementierung unterscheidet sich nur minimal von der
in System III.
Im bekannteren 4.3BSD-Tahoe (1988) tauchte cut nicht auf.
Das darauf folgende 4.3BSD-Reno (1990) lieferte aber wieder
ein cut mit aus. Dieses cut war ein von Adam S. Moskowitz und
Marciano Pitargue neu implementiertes cut, das 1989 in BSD
aufgenommen wurde.
[ http://minnie.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-Reno/src/usr.bin/cut
Seine Manpage
[ http://minnie.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-Reno/src/usr.bin/cut/cut.1
erwaehnt bereits die erwartete Konformitaet mit POSIX.2.
Nun muss man wissen, dass POSIX.2 erst im September
1992 veroeffentlicht wurde, also gut zwei Jahren nachdem die
Manpage und das Programm geschrieben worden waren. Das Programm
wurde folglich anhand von Arbeitsversionen des Standards
implementiert. Ein Blick in den Code bekraeftigt diese Vermutung.
In der Funktion zum parsen der Feldauswahlliste findet sich
dieser Kommentar:

	This parser is less restrictive than the Draft 9 POSIX spec.
	POSIX doesn't allow lists that aren't in increasing order or
	overlapping lists.

Im Draft 11.2 (1991-09) fordert POSIX diese Flexibilitaet bereits
ein:

	The elements in list can be repeated, can overlap, and can
	be specified in any order.

Auch listet Draft 11.2 alle drei Modi, waehrend in diesem
BSD cut nur die zwei alten implementiert sind. Es koennte also
sein, dass in Draft 9 der Bytemodus noch nicht vorhanden war.
Da ich keinen Zugang zu Draft 9 oder 10 finden konnte, war es mir
leider nicht moeglich, diese Vermutung zu pruefen. XXX

Die Versionsnummern und Aenderungsdaten der aelteren
BSD-Implementierungen kann man aus den SCCS-IDs, die vom
damaligen Versionskontrollsystem in den Code eingefuegt wurden,
ablesen. So z.B. bei 4.3BSD-Reno: ``5.3 (Berkeley) 6/24/90''.

Das cut der GNU Coreutils enthaelt folgenden Copyrightvermerk:

	Copyright (C) 1997-2015 Free Software Foundation, Inc.
	Copyright (C) 1984 David M. Ihnat

Der Code hat also recht alte Urspruenge. Wie aus weiteren
Kommentaren zu entnehmen ist, wurde der Programmcode zuerst von David
MacKenzie und spaeter von Jim Meyering ueberarbeitet. Letzterer
hat den Code 1992 auch ins Versionkontrollsystem eingestellt.
Weshalb die Jahre vor 1997, zumindest ab 1992, nicht im
Copyright-Vermerk auftauchen, ist unklar.

Trotz der vielen Jahreszahlen aus den 80er Jahren gehoert cut,
aus Sicht des urspruenglichen Unix, zu den juengeren Tools.
Wenn cut auch ein Jahrzehnt aelter als Linux, der Kernel, ist,
so war Unix doch schon ueber zehn Jahre alt, als cut das
erste Mal auftauchte. Insbesondere gehoerte cut auch noch nicht
zu Version 7 Unix, das die Ausgangsbasis aller modernen
Unix-Systeme darstellt. Die weit komplexeren Programme sed
und awk waren dort schon vertreten. Man muss sich also
fragen, warum cut ueberhaupt noch entwickelt wurde, wo es
schon zwei Programme gab, die die Funktion von cut abdecken
konnten. Ein Argument fuer cut war sicher seine Kompaktheit und
die damit verbundene Geschwindigkeit gegenueber dem damals
traegen awk. Diese schlanke Gestalt ist es auch, die der
Unix-Philosopie entspricht: Mache eine Aufgabe und die richtig!
Cut ueberzeugte. Es wurde in andere Unix Varianten uebernommen,
standardisiert und ist heutzutage ueberall anzutreffen.

Die urspruengliche Variante (ohne -b) wurde schon 1985 in
der System V Interface Definition, einer wichtigen formalen
Beschreibung von UNIX System V, spezifiziert und tauchte
anschliessend in allen relevanten Standards auf. Mit POSIX.2
im Jahre 1992 wurde cut zum ersten Mal in der heutigen Form
(mit -b) standardisiert.
XXX sicher?


Multibyte-Unterstuetzung

Nun sind der Bytemodus und die damit verbundene
Multibyte-Verarbeitung des POSIX-Zeichenmodus bereits seit
1992 standardisiert, wie steht es aber mit deren Umsetzung?
Welche Versionen implementieren POSIX korrekt?
Die Situation ist dreiteilig: Es gibt historische
Implementierungen, die nur -c und -f kennen. Dann gibt es
Implementierungen die -b zwar kennen, es aber lediglich als Alias
fuer -c handhaben. Diese Implementierungen funktionieren mit
Single-Byte-Encodings (z.B. US-ASCII, Latin1) korrekt, bei
Multibyte-Encodings (z.B. UTF-8) verhaelt sich ihr -c aber
wie -b (und -n wird ignoriert). Schliesslich gibt es noch
Implementierungen, die -b und -c tatsaechlich POSIX-konform
implementieren.

Historische Zwei-Modi-Implementierungen sind z.B. die von
System III, System V und die aller BSDs bis in die 90er.

Pseudo-Multibyte-Implementierungen bieten GNU und die
modernen NetBSDs und OpenBSDs. Man darf sich sicher fragen,
ob dort ein Schein von POSIX-Konformitaet gewahrt wird.
Teilweise findet man erst nach genauerer Suche heraus, dass
-c und -n nicht wie erwartet funktionieren; teilweise machen es
sich die Systeme auch einfach, indem sie auf
Singlebyte-Zeichenkodierungen beharren, das aber dafuer meist
klar darlegen:

	Since we don't support multi-byte characters, the -c and -b
	options are equivalent, and the -n option is meaningless.

[ http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/cut/cut.c?rev=1.18&content-type=text/x-cvsweb-markup

Tatsaechlich standardkonforme Implementierungen, die
Multibytes korrekt handhaben, bekommt man bei einem modernen
FreeBSD und bei den Heirloom Tools. Bei FreeBSD hat Tim Robbins
im Sommer 2004 den Zeichenmodus POSIX-konform reimplementiert.
[ https://svnweb.freebsd.org/base?view=revision&revision=131194
Warum die beiden anderen grossen BSDs diese Aenderung nicht
uebernommen haben, bleibt offen. Es scheint aber an der im
obigen Kommentar formulierten Grundausrichtung zu liegen.

Wie findet man nun als Nutzer heraus, ob beim cut(1) des eigenen
Systems Multibytes korrekt unterstuetzt werden? Zuerst ist
entscheidend, ob das System selbst mit einem Multibyte-Encoding
arbeitet, denn tut es das nicht, dann entsprechen sich
Zeichen und Bytes und die Frage eruebrigt sich. Man kann das
herausfinden indem man sich das Locale anschaut, aber einfacher
ist es, ein typisches Mehrbytezeichen, wie z.B. einen Umlaut,
auszugeben und zu schauen ob dieses in einem oder in mehreren
Bytes kodiert ist:

	$ echo ä | od -c
	0000000 303 244  \n
	0000003

In diesem Fall sind es zwei Bytes: oktal 303 und 244 . (Den
Zeilenumbruch fuegt echo(1) hinzu.)

Mit dem Programm iconv(1) kann man Text explizit in bestimmte
Kodierungen konvertieren. Hier Beispiele, wie die Ausgabe
bei Latin1 und wie sie bei UTF-8 aussieht.

	$ echo ä | iconv -t latin1 | od -c        
	0000000 344  \n
	0000002

	$ echo ä | iconv -t utf8 | od -c  
	0000000 303 244  \n
	0000003

Die Ausgabe auf dem eigenen System (ohne die iconv-Konvertierung)
wird recht sicher einer dieser beiden Ausgaben entsprechen.

Nun zum Test der cut-Implementierung. Hat man ein UTF-8-System,
dann sollte sich eine POSIX-konforme Implementierung folgendermassen
verhalten:

	$ echo ä | ./cut -c 1 | od -c
	0000000 303 244  \n
	0000003

	$ echo ä | ./cut -b 1 | od -c
	0000000 303  \n
	0000002

	$ echo ä | ./cut -b 1 -n | od -c
	0000000  \n
	0000001

Bei einer Pseudo-POSIX-Implementierung ist die Ausgabe in
allen drei Faellen wie die mittlere: Es wird das erste Byte
ausgegeben.


Implementierungen

Nun ein Blick auf den Code. Betrachtet wird eine Auswahl an
Implementierungen.

Fuer einen ersten Eindruck ist der Umfang des Quellcodes
hilfreich. Typischerweise steigt dieser ueber die Jahre an. Diese
Beobachtung kann hier in der Tendenz, aber nicht in jedem Fall,
bestaetigt werden. Die POSIX-konforme Umsetzung des Zeichenmodus
erfordert zwangslaeufig mehr Code, deshalb sind diese
Implementierungen tendenziell umfangreicher.


	SLOC	Zeilen	Bytes	Gehoert zu  	Dateidatum	Kategorie
	-----------------------------------------------------------------
	116	123	 2966	System III	1980-04-11	(hist)
	118	125	 3038	4.3BSD-UWisc	1986-11-07	(hist)
	200	256	 5715	4.3BSD-Reno	1990-06-25	(hist)
	200	270	 6545	NetBSD	 	1993-03-21	(hist)
	218	290	 6892	OpenBSD		2008-06-27	(pseudo)
	224	296	 6920	FreeBSD		1994-05-27	(hist)
	232	306	 7500	NetBSD 		2014-02-03	(pseudo)
	340	405	 7423	Heirloom	2012-05-20	(POSIX)
	382	586	14175	GNU coreutils	1992-11-08	(pseudo)
	391	479	10961	FreeBSD		2012-11-24	(POSIX)
	588	830	23167	GNU coreutils	2015-05-01	(pseudo)


Das Kandidatenfeld teilt sich grob in vier Gruppen: (1) Die zwei
urspruenglichen Implementierungen, die sich nur minimal
unterscheiden, mit gut 100 SLOCs. (2) Die fuenf BSD-Versionen mit
gut 200 SLOCs. (3) Die zwei POSIX-konformen Programme und
die alte GNU-Version mit 340-390 SLOCs. Und schliesslich (4) die
moderne GNU-Variante mit fast 600 SLOCs.

Die Abweichung zwischen logischen Codezeilen (SLOC, ermittelt mit
SLOCcount) und der Anzahl von Zeilenumbruechen in der Datei (`wc
-l') erstreckt sich ueber einen Faktor von 1.06 bei den aeltesten
Vertretern bis zu Faktor 1.5 bei GNU. Der groesste
Einflussfaktor darauf sind Leerzeilen, reine Kommentarzeilen und
die Groesse des Lizenzblocks am Dateianfang. 

Betrachtet man die Abweichungen zwischen den logischen Codezeilen
und der Dateigroesse (`wc -c'), so pendelt das Teilnehmerfeld
zwischen 25 und 30 Bytes je Anweisung. Die Heirloom-Implementierung
weicht mit nur 21 nach unten ab, die GNU-Implementierungen mit
fast 40 nach oben. Bei GNU liegt dies hauptsaechlich an deren
Programmierstil, mit spezieller Einrueckung und langen Bezeichnern.
Ob man die Heirloom-Implementierung als besonders kryptisch
oder als besonders elegant bezeichnen will, das soll der
eigenen Einschaetzung des Lesers ueberlassen bleiben.


Die interne Struktur der Programmcodes (in C) ist meist aehnlich.
Neben der obligatorischen main-Funktion, die die Kommandozeilenargumente
verarbeitet, gibt es im Normalfall eine Funktion, die die
Feldauswahl in eine interne Datenstruktur ueberfuehrt. Desweiteren
haben fast alle Implementierungen separate Funktionen fuer die
zwei bzw. drei Modi. Bei den POSIX-konformen Implementierungen
wird die `-b -n'-Kombination als weiterer Modus behandelt, und
damit in einer eigenen Funktion umgesetzt. Nur bei der fruehen
System III-Implementierung (und seiner 4.3BSD-UWisc-Variante)
wird ausser den Fehlerausgaben alles in der main-Funktion
erledigt.

Cut-Implementierungen haben typischerweise zwei limitierende
Groessen: Die Maximalanzahl unterstuetzter Felder und die maximale
Zeilenlaenge. Bei System III sind beide Groessen auf 512 begrenzt.
4.3BSD-Reno und die BSDs der 90er Jahre haben ebenfalls fixe
Grenzen (_BSD_LINE_MAX bzw. _POSIX2_LINE_MAX). Bei modernen
FreeBSDs, NetBSDs, bei allen GNU-Implementierungen und bei
Heirloom kann sowohl die Felderanzahl als auch die maximale
Zeilenlaenge beliebig gross werden; der Speicher dafür wird
dynamisch alloziiert. OpenBSD ist ein Hybrid aus fixer
Maximalzahl an Feldern, aber beliebiger Zeilenlaenge. Die
begrenzte Felderanzahl scheint jedoch kein Praxisproblem
darzustellen, da _POSIX2_LINE_MAX mit mindestens 2048 durchaus
gross genug sein sollte.


Beschreibungen

Interessant ist auch ein Vergleich der Kurzbeschreibungen von
cut, wie sie sich in der Titelzeile der Manpages oder manchmal
auch am Anfang der Quellcodedatei finden. Die folgende Liste
ist grob zeitlich geordnet und nach Abstammung gruppiert:


System III	cut out selected fields of each line of a file
System III (src)	cut and paste columns of a table (projection of a relation)
System V	cut out selected fields of each line of a file
HP-UX		cut out (extract) selected fields of each line of a file

4.3BSD-UWisc (src)	cut and paste columns of a table (projection of a relation)
4.3BSD-Reno	select portions of each line of a file
NetBSD		select portions of each line of a file
OpenBSD 4.6	select portions of each line of a file
FreeBSD 1.0	select portions of each line of a file
FreeBSD 10.0	cut out selected portions of each line of a file
SunOS 4.1.3	remove selected fields from each line of a file
SunOS 5.5.1	cut out selected fields of each line of a file

Heirloom Tools	cut out selected fields of each line of a file
Heirloom Tools (src)	cut out fields of lines of files

GNU coreutils	remove sections from each line of files

Minix		select out columns of a file

Version 8 Unix	rearrange columns of data
``Unix Reader''	rearrange columns of text

POSIX		cut out selected fields of each line of a file


Die mit ``(src)'' markierten Beschreibungen sind aus dem
jeweiligen Quellcode entnommen. Der POSIX-Eintrag enthaelt
die Beschreibung des Standards. Der ``Unix Reader'' ist ein
rueckblickendes Textdokument von Doug McIlroy, das das
Auftreten von Tools in der Geschichte des Research Unix zum
Thema hat.
[ http://doc.cat-v.org/unix/unix-reader/contents.pdf
Eigentlich sollte seine Beschreibung der in Version 8 Unix
entsprechen. Die Abweichung koennte sowohl ein
Uebertragungsfehler als auch eine nachtraegliche Korrektur
sein. Alle uebrigen Beschreibungen entstammen den Manpages.

Oft ist mit der Zeit die POSIX-Beschreibung uebernommen
oder an sie angeglichen worden, wie beispielsweise bei FreeBSD.
[ https://svnweb.freebsd.org/base?view=revision&revision=167101

Interessant ist, dass die GNU coreutils seit Anbeginn vom
Entfernen von Teilen der Eingabe sprechen, wohingegen die
Kommandozeilenangabe klar ein Auswaehlen darstellt. Die
Worte ``cut out'' sind vielleicht auch etwas zu
missverstaendlich. HP-UX hat sie deshalb praezisiert.

Auch beim Begriff, was selektiert wird, ist man sich
uneins. Die Einen reden von Feldern (POSIX), Andere von
Abschnitten bzw. Teilen (BSD) und wieder Andere von Spalten
(Research Unix). Ironischerweise leistet sich gerade Version
8 Unix, das eigentlich um eine sehr treffende Weltsicht
bemueht ist, mit ``rearrange columns of data'' die
unzutreffendste der Beschreibungen.


Autoreninfo

Markus Schnalke interessiert sich fuer die Hintergruende
von Unix und seinen Werkzeugen. Fuer die Erarbeitung dieses
Textes wurde er regelrecht zum Historiker.


Lizenz

CC0 (und kann damit auch unter CC BY-SA 4.0 Unported
veroeffentlicht werden)