view cut.txt @ 8:1dc4a9dca829

Zwischenstand
author markus schnalke <meillo@marmaro.de>
date Tue, 05 May 2015 09:04:00 +0200
parents 21ca59543b07
children e67bd0d48bd6
line wrap: on
line source

Das Werkzeugkaestle, #1

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. Es ist ein schoenes Anschauungsobjekt fuer's Shellscripting.
Hier soll ein wenig hinter die Fassade von cut geschaut werden.


Funktionsweise

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

Der Zeichenmodus ist geeignet um Festbreitenformaten zu
zerteilen. So kann man damit beispielsweise bestimmte
Zugriffsrechte aus der Ausgabe von `ls -l' ausschneiden. Hier
die Rechte des Besitzers:

	$ 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.

	$ echo "$long" | cut -c -20

Dieser Befehl gibt die ersten maximal 20 Zeichen von
`$long' aus. (Alternativ kann man hierfuer auch `printf
"%.20s\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 als Zeichensatz und -kodierung
noch omnipraesent 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 mit der 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

Neben dem Zeichen- bzw. Byte-Modus bietet cut noch den
Feld-Modus, 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 Feld-Modus ist die
Auswahl von Information aus der passwd-Datei. So z.B. der
Benutername, seine ID und das Homeverzeichnis:

	$ cut -d: -f1,3,6 /etc/passwd

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


Dieser Feld-Modus ist fuer einfache tabellarische Dateien,
wie eben die passwd, gut geeignet. Er kommt aber schnell an
seine Grenzen. Gerade der uebliche Fall, dass an Whitespace
in Felder geteilt werden soll, wird damit nicht abgedeckt.
Der Delimiter kann nur genau ein Zeichen sein. Es kann also
nicht sowohl an Leerzeichen als auch an Tabs getrennt 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 Erweiterungen, die das gewuenschte Verhalten fuer
Whitespace-getrennte Felder bieten. Ansonsten, d.h. wenn
man portabel bleiben will, hilft awk.

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 sein. Die Felder der Ergebnismenge sind
dabei immer gleich geordnet wie sie es in der Eingabe waren.
Oder, um die Worte der Manpage in Version 8 Unix
wiederzugeben: ``In data base parlance, it projects a relation.''
Cut fuehrt also die Datenbankoperation Projektion auf
Textdateien aus. Die Wikipedia erklaert das in
verstaendlicherer Sprache:

	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 sccsid im
Quellcode von Version 1.5. Es muss also noch eine
Vorgeschichte geben. Zu dieser habe ich leider keinen Zugang
gefunden.

Aber werfen wir doch einen 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) taucht cut nicht auf.
Das darauf folgende 4.3BSD-Reno (1990) liefert aber wieder
ein cut mit aus. Dieses cut ist 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 sollte man wissen, dass POSIX.2 erst im September
1992 veroeffentlicht wurde, also gut zwei Jahren *nachdem* die
Manpage und das Programm geschrieben wurden. Das Programm
wurde also anhand von Arbeitsversionen des Standards
implementiert. Zweieinhalb Jahre Arbeit war immerhin schon in
den Standardisierungsprozess geflossen; bis zur
Fertigstellung sollte es aber noch weitere zwei Jahre dauern.

Trotz all dieser 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 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 Aufgabe von cut abdeckten.
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!
So bewaehrte sich cut. Es wurde in andere Unix Varianten
uebernommen, standardisiert und ist heutzutage ueberall
anzutreffen.

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



Multibyte-Behandlung

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 denn den POSIX korrekt?
Die Situation ist mehrschichtig. Es gibt traditionelle
Implementierungen, die nur -c und -f kennen. Dann gibt es
Implementierungen die zwar -b kennen, es aber nur als Alias
fuer -c handhaben. Diese Implementierungen funktionieren mit
Single-Byte-Encodings (z.B. US-ASCII, Latin1) korrekt, bei
Multi-Byte-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.

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

Pseude-Multibyte-Implementierungen bieten GNU und die
modernen NetBSDs und OpenBSDs. Wie sehr dort der Schein von
POSIX-konformitaet gewahrt wird, ist unterschiedlich. Nicht
immer findet man klare Aussagen wie diese:

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

[ XXX

Tatsaechlich standardkonforme Implementierungen, die
Multibytes korrekt handhaben, bekommt man bei einem modernen
FreeBSD und bei den Heirloom Tools. Bei FreeBSD hat Tim Robbins
(tjr) 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 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 dazu nachschauen,
welches Locale eingestellt ist, 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 Test explizit in bestimmte
Kodierungen konvertieren. Hier Beispiele, wie das Ergebnis
bei Latin1 und wie es 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 so verhalten:

	$ echo aä | ./cut -c -2 | od -c
	0000000   a 303 244  \n
	0000004

	$ echo aä | ./cut -b -2 | od -c
	0000000   a 303  \n
	0000003

	$ echo aä | ./cut -b -2 -n | od -c
	0000000   a  \n
	0000002

Bei einer Implementierung, die -b und -c gleich behandelt,
ist die Ausgabe in allen drei Faellen wie die mittlere: Es
werden die ersten beiden Bytes ausgegeben.



Implementierungen

Nun zum Blick auf den Code. Hier soll eine Auswahl an
Implementierungen etwas genauer betrachtet werden. 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 Unterstuetzung des Byte-Modus (-b) erfordert zwangslaeufig
mehr Code, deshalb ist zu erwarten, dass diejenigen
Implementierungen, die ihn haben, umfangreicher sind.

Codevergleich

SLOC	Zeilen	Bytes	Gehoert zu  	Dateidatum	Kategorie
-----------------------------------------------------------------
116	123	 2966	System III	1980-04-11	(trad)
118	125	 3038	4.3BSD-UWisc	1986-11-07	(trad)
200	256	 5715	4.3BSD-Reno	1990-06-25	(trad)
200	270	 6545	NetBSD	 	1993-03-21	(trad)
218	290	 6892	OpenBSD		2008-06-27	(pseudo)
224	296	 6920	FreeBSD		1994-05-27	(trad)
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)


$ awk -F'  +' '{printf("%d\t%d (%.2f)\t%d (%.2f)\t%s\t%s\t%s\n",
		$1, $2, $2/$1, $3, $3/$1, $4, $5, $6);}' <sloc                
116     123 (1.06)      2966 (25.57)    System III      1980-04-11   (trad)
118     125 (1.06)      3038 (25.75)    4.3BSD-UWisc    1986-11-07   (trad)
200     256 (1.28)      5715 (28.57)    4.3BSD-Reno     1990-06-25   (trad)
200     270 (1.35)      6545 (32.73)    NetBSD          1993-03-21   (trad)
218     290 (1.33)      6892 (31.61)    OpenBSD         2008-06-27   (pseudo)
224     296 (1.32)      6920 (30.89)    FreeBSD         1994-05-27   (trad)
232     306 (1.32)      7500 (32.33)    NetBSD          2014-02-03   (pseudo)
340     405 (1.19)      7423 (21.83)    Heirloom        2012-05-20   (POSIX)
382     586 (1.53)      14175 (37.11)   GNU coreutils   1992-11-08   (pseudo)
391     479 (1.23)      10961 (28.03)   FreeBSD         2012-11-24   (POSIX)
588     830 (1.41)      23167 (39.40)   GNU coreutils   2015-05-01   (pseudo)


Einige Auffaelligkeiten:

Das Kandidatenfeld teilt sich grob in vier Gruppen: Die zwei urspruenglichen
Implementierungen, die sich nur minimal unterscheiden, mit gut 100 SLOCs.
Dann die fuenf BSD-Versionen mit knapp ueber 200 SLOCs. Anschliessend die
zwei POSIX-konformen Programme und die alte GNU-Version mit 350-400
SLOCs. Und zum Abschluss die moderne GNU-Variante mit fast 600 SLOCs.

Die Abweichung von logischen Codezeilen (nach der Definition von
SLOCcount) und der Anzahl von Zeilenumbruechen in der Datei erstreckt 
sich ueber einen Faktor von 1.06 bei den aeltesten Vertretern bis zu
Faktor 1.5 bei GNU.

Betrachtet man die Abweichungen zwischen den logischen Codezeilen und der
Dateigroesse, so pendelt das Teilnehmerfeld zwischen 25 und 30 Bytes je
Anweisung. Die Heirloom-Implementierung weicht nach unten ab, die
GNU-Implementierungen nach oben.



Das cut in System III von 1980 ist, wie man anhand der SCCS-ID erkennen
kann bereits in Version 1.5. Die Vorversionen konnte ich aber leider nicht
ermitteln.

Schaut man sich die SCCS-IDs in den BSD-Quellen an, dann findet man dort
Versionsnummern, die die Entwicklung dokumentieren:

4.3bsd-uwisc	"@(#)cut.c      1.3";
4.3bsd-reno	"@(#)cut.c      5.3 (Berkeley) 6/24/90";
netbsd		"@(#)cut.c      5.4 (Berkeley) 10/30/90";
freebsd		"@(#)cut.c      8.1 (Berkeley) 6/6/93";

Die neueren BSD-Versionen enthalten zwar weiterhin eine SCCS-ID, diese
ist aber bei Version "8.3 (Berkeley) 5/4/95" stehen geblieben. Danach
wurde scheinbar von SCCS auf CSV oder SVN gewechselt.

Bei GNU befindet sich folgender Copyright-Vermerk im Code:

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

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




Beschreibungen

Interessant ist ein Vergleich der Kurzbeschreibungen von cut,
wie sie sich in der Titelzeile von Manpages oder manchmal auch
am Anfang der Quellcodedatei finden.

Die folgende Liste ist grob nach Zeit 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 7.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

POSIX		cut out selected fields of each line of a file

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


Die zwei mit ``(src)'' markierten Beschreibungen sind aus
dem Quellcode entnommen, und verdeutlichen den Codetransfer.
POSIX ist ein Set von Standards, keine Implementierung. Der
``Unix Reader'' ist ein rueckblickendes Textdokument von
Doug McIlroy, das das Auftreten von Tools in der Geschichte
des Research Unix zum Thema hat. Alle uebrigen Beschreibungen
entstammen den Manpages.

Zumeist ist mit der Zeit die POSIX-Beschreibung uebernommen
worden, wie beispielsweise bei FreeBSD zu sehen.
[ 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 nicht klar genug.
HP-UX hat sie deshalb praezisiert.

Auch beim Begriff, was denn nun 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)