#!/usr/bin/perl -Tw -Ilib -I../lib
#
# noid - a Perl script that mints and binds nice opaque identifiers
#   using the Noid.pm module.  This script can be invoked additionally
#   (via a links) as "web" to format output for the web.
#
# Author:  John A. Kunze, jak@ucop.edu, California Digital Library
#    Orginally created Nov. 2002 at UCSF Center for Knowledge Management
# 
# ---------
# Copyright (c) 2002-2004 UC Regents
# 
# Permission to use, copy, modify, distribute, and sell this software and
# its documentation for any purpose is hereby granted without fee, provided
# that (i) the above copyright notices and this permission notice appear in
# all copies of the software and related documentation, and (ii) the names
# of the UC Regents and the University of California are not used in any
# advertising or publicity relating to the software without the specific,
# prior written permission of the University of California.
# 
# THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
# EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
# WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
# 
# IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE FOR ANY
# SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
# OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
# WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY
# THEORY OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE
# OR PERFORMANCE OF THIS SOFTWARE.
# ---------

use strict;

sub get_untainted_PERL5LIB {
	my $key;
	my $perl_5_lib = $ENV{"PERL5LIB"};
	my @lib_list = ('./Noid/lib');
	! defined($perl_5_lib) and
		return(@lib_list);
	if ($perl_5_lib =~ /^(\/\S+)$/) {
		push @lib_list, $1;
		return(@lib_list);
	}
	die(qq@Format of variable "PERL5LIB" ($perl_5_lib) invalid.\n@);
}

#use lib './Noid/lib';
use lib	get_untainted_PERL5LIB( );

use Text::ParseWords;
use Getopt::Long;
use BerkeleyDB;
use Noid;

my $web = 0;
my ($dbdir, $dbname, $debug, $ver, $help, $contact, $bulkcmd);
my ($template, $snaa, $total);
my (@valid_helptopics, %info);		# purposely undefined for now
my @valid_commands = qw(
	bind dbinfo dbcreate fetch get hello help hold
	mint note peppermint queue validate
);

# yyy make a noidmail (email robot interface?)
# xxx location field for redirect should include a discriminant
#     eg, ^c for client choice, ^i for ipaddr, ^f format, ^l language
#     and ^b for browser type, ^xyz for any http header??
# yyy add "file" command, like bind, but stores a file, either as file or
#     in a big concatenation stream (binding offset, length, checksum)?
# xxx figure out whether validate needs to open the database, and if not,
#     what that means
# xxx to notify: include Giarlo, Giaretta, Stack, OCKHAM, Juha, weibel, lannom
#     all ARK users, DC-p.Id list, DC-pres., ERC list,
#     max planck society: suckfuell@gv.mpg.de, schimmer@mpg-gv.mpg.de,
#                       i.overkamp@bm.mpg.de, bowman@biochem.mpg.de

# main
{
	my $line;
	if ($0 =~ m|noidu[^/]*$|) {	# if called with the URL interface
		$web = 1;			# orient output for HTTP
		print "Content-Type: text/plain\n\n";
		open(STDERR, ">&STDOUT")
			or die("Can't combine stderr and stdout: $!\n");
		! defined($ENV{'QUERY_STRING'}) and
			die("No QUERY_STRING (hence no command) defined.\n");
		($line = $ENV{'QUERY_STRING'}) =~ tr/+/ /;
		@ARGV = shellwords($line);
		#print "ARGV: " . join("|", @ARGV) . "\n";
	}
	if ($0 =~ m|noidr[^/]*$|) {	# if called for RewriteMap resolving,
					# see Apache Rewrite mod documentation
		$| = 1;		# very important to unbuffer the output
		$bulkcmd = 1;
		# xxx should we set a timeout to prevent hanging the server?
	}

	if (! ($contact = who_are_you($web))) {
		print STDERR "Can't tell who you are: $!\n";
		exit(1);
	}

	if (! GetOptions(
		'debug'		=> \$debug,	# flag
		'f=s'		=> \$dbdir,	# filesystem directory name
		'version'	=> \$ver,	# flag
		'help'		=> \$help,	# flag
	)) {
		print "error: GetOptions\n";
		usage(1, 1, "intro");
		exit(1);
	}
	$web && $debug and
		print "contact=$contact, pwd=", `pwd`;

	# Handle -v or -h, and exit early.
	if ($ver) {
		# We take our version number from the Noid module version.
		print qq@This is "noid" version $Noid::VERSION.\n@;
		exit(0);
	}
	if ($help) {
		# xxx should we encode help output?   print "help:\n";
		usage(0, 0, "intro");
		exit(0);
	}

	# Now try to find a database directory string.
	# In the special case of dbcreate, we may create
	# and name the directory on behalf of the user.
	#
	if (! defined($dbdir)) {
		defined($ENV{'NOID'}) and	# is NOID env variable defined?
			$dbdir = $ENV{'NOID'},
		1 or
		$0 =~ m|_([^/]+)$| and		# executable link reveals dbdir?
			$dbdir = $1,
		1 or
			$dbdir = '.',		# else try current directory
		;
		if (! defined($dbdir) || $dbdir !~ /\S/) {
			print "error: no Dbdir\n";
			usage(1, 1, "intro");
			exit(1);
		}
	}
	elsif ($web) {
		print qq@-f option not allowed in URL interface.\n@;
		return(0);
	}
	# Now untaint $dbdir.  xxx we can do better?
	$dbdir =~ m|^(.*)$| and
		$dbdir = $1
	or
		print("error: bad Dbdir\n"),
		usage(1, 1, "intro"),
		exit(1)
	;
	$dbname = "$dbdir/NOID/noid.bdb";

	# Bulk command mode is signified by a single final argument of "-".
	# If we're _not_ in bulk command mode, expect a single command
	# represented by the remaining arguments; do it and exit.
	#
	$bulkcmd ||= ($#ARGV == 0 && $ARGV[0] eq "-");
	if (! $bulkcmd) {
		do_command(@ARGV);
		exit(0);
	}

	# If we get here, we're in bulk command mode.  Read, tokenize,
	# and execute commands from the standard input.  Test with
	#   curl --data-binary @cmd_file http://dot.ucop.edu/nd/noidu_kt5\?-
	# where cmd_file contains newline-separated commands.
	# xxx do HTTP Post version of this...!
	# XXX make sure to %-decode web QUERY_STRING, so we don't have
	#     to always put +'s for spaces
	#
	while (($line = <STDIN>)) {
		do_command(shellwords($line));
	}
	exit(0);
}

sub do_command {

	# Any remaining args should form a noid command.
	# Look at the command part (if any) now, and complain about
	# a non-existent database unless the command is "dbcreate".
	#
	my $command = shift;
	if (! defined($command)) {	# if no command arg
		usage(1, 1, "intro");
		return(0);
	}
	if (! -f $dbname
			&& $command ne 'dbcreate' && $command ne 'help') {
		# if the database doesn't exist when it needs to
		bprint(*STDERR, "error: no database ($dbname) "
			. "-- use dbcreate?\n\n");
		usage(1, 1, "intro");
		return(0)
	}
	if (grep(/^$command$/, @valid_commands) != 1) {
		print "error: no such command: $command (",
			join(" ", @_), ")\n";
		usage(1, 1, "intro");
		return(0);
	}
	# Perform extra checks in $web case.
	if ($web && $command eq 'dbcreate') {
		print qq@error: command "$command" not allowed in URL interface.\n@;
		usage(1, 1, "intro");
		return(0);
	}
	# It should now be safe to turn off strict 'refs' when we
	# invoke a command via its subroutine name.
	#if ($#_ < 0) {
	#	usage(1);	# xxx say something senstive about $command
	#usage(1, 1, "intro");
	#	return(0);
	#}

	no strict 'refs';
	&$command(@_);
}

#
# --- begin almost alphabetic listing of functions ---
#

# yyy what is the sensible thing to do if (a) no element given,
#     (b) if no value, or (c) if there are multiple values?
# xxx vbind(..., template, ...)?  nvbind()?
#
# Returns number of elements successfully bound.
#
# XXX what about append at the list vs the string level?
sub bind { my( $how, $id, $elem, $value )=@_;

	my $validate = 1;
	my $noid = Noid::dbopen($dbname, 0);
	if (! $noid) {
		print STDERR Noid::errmsg($noid);
		return(0);
	}
	my $report;
	! defined($elem) and
		$elem = "";
	if ($elem eq ":") {	# expect name/value pairs up to blank line
		defined($value) and
			print(STDERR "Why give a value ($value) with an "
				. qq@element "$elem"?\n@),
			Noid::dbclose($noid),
			return(0);

		# To slurp paragraph, apparently safest to use local $/, which
		local $/;			# disappears when scope exits.
		$/ = "\n\n";			# Means paragraph mode.
		my $para = <STDIN> || "";
		chop $para;	# XXX needed?
		$para =~ s/^#.*\n//g;		# remove comment lines
		$para =~ s/\n\s+/ /g;		# merge continuation lines
		my @elemvals = split(/^([^:]+)\s*:\s*/m, $para);
		shift @elemvals;		# throw away first null
		my ($bound, $total) = (0, 0);
		while (1) {
			($elem, $value) = (shift @elemvals, shift @elemvals);
			! defined($elem) && ! defined($value) and
				last;
			$total++;
			! defined($elem) and
				Noid::addmsg($noid,
					"error: $id: bad element associated "
						. qq@with value "$value".@),
				last;
			! defined($value) and
				$value = "",
			1 or
				chop $value
			;
			$report = Noid::bind($noid, $contact, $validate,
				$how, $id, $elem, $value);
			! defined($report) and
				print(STDERR $report, "\n"),
				usage(1, 1, "bind"),
				# XXX how/who should log failures in "hard" case
			or
				$bound++,
				print($report, "\n"),
			;
		}
		# XXX summarize for log $total and $bound
		Noid::dbclose($noid);
		return(defined($report) ? 1 : 0);
	}
	elsif ($elem eq ":-") {		# expect name/value to be rest of file
		defined($value) and
			print(STDERR "Why give a value ($value) with an "
				. qq@element "$elem"?\n@),
			Noid::dbclose($noid),
			return(0);
#		while (<STDIN>) {
#			next if /^#/ || /^\s*\n/;
#			last;		# end at first non-blank, non-comment
#		}
#		chop;
#		! defined($_) || ! s/^(\w+)\s*:\s*// and
#			Noid::addmsg($noid, "error: $id no element to bind."),
#			Noid::dbclose($noid),
#			return(0);
#		$elem = $1;
#		$value = $_;
#		# To slurp file, apparently safest is to use local $/, which
#		local $/;			# disappears when scope exits.
#		$value .= <STDIN>;		# $/==undef means file mode.

		# Read all of STDIN into array "@input_lines".
		my @input_lines = <STDIN>;

		# Remove all newlines.
		foreach (@input_lines) {
			chomp;
			}

		# Ignore any leading lines that start with a pound sign
		# or contain nothing but white space.
		while (scalar(@input_lines) > 0) {
			if ((substr($input_lines[0], 0, 1) eq "#") ||
				($input_lines[0] =~ /^\s*$/)) {
				shift @input_lines;
				next;
				}
			last;
			}

		# If we don't have any lines, there's a problem.
		if (scalar(@input_lines) == 0) {
			print STDERR "error:  no non-blank, non-comment ",
				"input.\n";
			Noid::dbclose($noid);
			return(0);
			}

		# There must be an element and a colon on the first line.
		unless ($input_lines[0] =~ /^\s*(\w+)\s*:\s*(.*)$/) {
			print STDERR "error:  missing element or colon on ",
				"first non-blank, non-comment line.\n";
			Noid::dbclose($noid);
			return(0);
			}

		# Save the element, and any part of the value that there
		# might be on the first line.
		$elem = $1;
		$value = $2;

		# Remove the first line from the array.
		shift @input_lines;

		# Append any additional lines to the value.
		foreach (@input_lines) {
			$value .= "\n" . $_;
			}

		# Put on the final newline.
		$value .= "\n";

		#
		# Now drop through to end of if-elsif clause to real binding.
	}
	# yyy eg, :fragment:Offset:Length:Path
	# yyy eg, :fragment:Offset:Length:Path
	# yyy eg, :file:Path
	# yyy eg, ":xml",
	elsif ($elem =~ /^:/) {
		print(STDERR qq@Binding to element syntax "$elem" @
			. "not supported.\n");
		Noid::dbclose($noid);
		return(0);
	}
	$report = Noid::bind($noid, $contact, $validate,
			$how, $id, $elem, $value);
	! defined($report) and
		print(STDERR Noid::errmsg($noid)),
		usage(0, 1, "bind")
	or
		print($report, "\n")
	;
	# xxx make sure return(0)'s do dbclose...
	Noid::dbclose($noid);
	return(defined($report) ? 1 : 0);
}

# This routine may not make sense in the URL interface.
#
sub dbcreate { my( $template, $policy, $naan, $naa, $subnaa )=@_;

	my $dbreport = Noid::dbcreate($dbdir, $contact, $template, $policy,
			$naan, $naa, $subnaa);
	if (! $dbreport) {
		print Noid::errmsg(), "\n";
		return(0);
	}
	print $dbreport, "\n";
	return(1);
}

sub dbinfo { my( $level )=@_;

	$level = "brief"
		if (! defined($level));
	my $noid = Noid::dbopen($dbname, DB_RDONLY);
	if (! $noid) {
		print Noid::errmsg($noid);
		return(0);
	}
	Noid::dbinfo($noid, $level);
	Noid::dbclose($noid);
	return(1);
}

sub fetch { my( $id, @elems )=@_;

	return(getfetch(1, $id, @elems));
}

sub get { my( $id, @elems )=@_;

	return(getfetch(0, $id, @elems));
}

# xxx RewriteLock /path/toLockFile
# xxx RewriteMap prg:/path/toBDB
# xxx id->stdin; NULL or 1-line->stdout
sub rmap { my( $id, @elems )=@_;

	return(getfetch(0, $id, @elems));
}

sub getfetch { my( $verbose, $id, @elems )=@_;

	my $noid = Noid::dbopen($dbname, DB_RDONLY);
	if (! $noid) {
		print STDERR Noid::errmsg($noid);
		return(0);
	}
	my $fetched = Noid::fetch($noid, $verbose, $id, @elems);
	! defined($fetched) and
		print(STDERR Noid::errmsg($noid))
	or
		print($fetched),
		$verbose && print("\n")
	;
	Noid::dbclose($noid);
	return(1);
}

sub hello {
	print "Hello.\n";
}

sub help { my( $topic )=@_;

	my $in_error = 0;
	my $brief = 0;
	return(usage($in_error, $brief, $topic));
}

# yyy what about a "winnow" routine that is either started
#     from cron or is started when an exiting noid call notices
#     that there's some harvesting/garbage collecting to do and
#     schedules it for, say, 10 minutes hence (by not exiting,
#     but sleeping for 10 minutes and then harvesting)?

sub hold { my( $on_off, @ids )=@_;

	my $noid = Noid::dbopen($dbname, 0);
	if (! $noid) {
		print STDERR Noid::errmsg($noid);
		return(0);
	}
	if (! Noid::hold($noid, $contact, $on_off, @ids)) {
		print(STDERR Noid::errmsg($noid));
		usage(1, 1, "hold");
		Noid::dbclose($noid);
		return(0);
	}
	print(Noid::errmsg($noid), "\n");	# no error message at all
	Noid::dbclose($noid);
	return(1);
}

sub peppermint { my( $n, $elem, $value )=@_;
	mint($n, $elem, $value, 1);
}

sub mint { my( $n, $elem, $value, $pepper )=@_;

	if (defined($pepper)) {
		print STDERR
			"The peppermint command is not implemented yet.\n";
		return(0);
	}
	if (! defined($n) || $n !~ /^\d+$/) {
		print STDERR "Argument error: expected positive integer, got ",
			(defined($n) ? qq@"$n"@ : "nothing"), "\n";
		usage(1, 1, "mint");
		return(0);
	}
	my $noid = Noid::dbopen($dbname, 0);
	if (! $noid) {
		print Noid::errmsg($noid);
		return(0);
	}
	my $id;
	while ($n--) {
		if (! defined($id = Noid::mint($noid, $contact, $pepper))) {
			print STDERR Noid::errmsg($noid);
			Noid::dbclose($noid);
			return(0);
		}
		print "id: $id\n";
	}
	Noid::dbclose($noid);
	print "\n";
	return(1);

}

sub note { my( $key, $value )=@_;

	if (! defined($key) || ! defined($value)) {
		print STDERR
			"You must supply a key and a value.\n";
		usage(1, 1, "note");
		return(0);
	}
	my $noid = Noid::dbopen($dbname, 0);
	! Noid::note($noid, $contact, $key, $value)
		and print Noid::errmsg($noid);
	Noid::dbclose($noid);
	return(1);
}

sub queue { my( $when, @ids )=@_;

	my $noid = Noid::dbopen($dbname, 0);
	if (! $noid) {
		print STDERR Noid::errmsg($noid);
		return(0);
	}
	my @queued = Noid::queue($noid, $contact, $when, @ids);
	my $retval;
	! @queued and
		$retval = 0,
		print(STDERR Noid::errmsg($noid), "\n"),
	1 or
		$retval = 1,
		print(join("\n", @queued), "\n"),
	;
	my $n = scalar(grep(! /^error:/, @queued));
	print("note: $n identifier", ($n == 1 ? "" : "s"), " queued\n");
	Noid::dbclose($noid);
	return($retval);
}

# Returns the number of valid ids.
sub validate { my( $template, @ids )=@_;

	my $noid = Noid::dbopen($dbname, DB_RDONLY);
	if (! $noid) {
		print Noid::errmsg($noid);
		return(0);
	}
	my @valids = Noid::validate($noid, $template, @ids);
	! @valids and
		print(STDERR Noid::errmsg($noid)),
		Noid::dbclose($noid),
		usage(1, 1, "validate"),
		return(0);

	my @iderrs = grep(/^error:/, @valids);
	print($_, "\n")
		for (@valids);
	Noid::dbclose($noid);
	return(scalar(@ids) - scalar(@iderrs));
}

# Print a blank (space) in front of every newline.
# First arg must be a filehandle.
#
sub bprint { my( $out, @args )=@_;
	map {s/\n/\n /g} @args;
	return print $out @args;
}

# Always returns 1 so it can be used in boolean blocks.
#
sub usage { my( $in_error, $brief, $topic )=@_;

	! defined($in_error) and
		$in_error = 1;		# default is to treat as error
	$in_error and
		$| = 1;			# flush any pending output
	my $out =			# where to send output
		($in_error ? *STDERR : *STDOUT);
	! defined($brief) and
		$brief = 1;		# default is to be brief
	$topic ||= "intro";
	$topic = lc($topic);

	# Initialize info topics if need be.
	#
	! @valid_helptopics and
		init_help();
	my @blurbs = grep(/^$topic/, @valid_helptopics);
	if (scalar(@blurbs) != 1) {
		print $out (scalar(@blurbs) < 1
			? qq@Sorry: nothing under "$topic".\n@
			: "Help: Your request ($topic), matches more than one "
				. "topic:\n\t(" . join(", ", @blurbs) . ").\n"
			),
			" You might try one of these topics:";
		my @topics = @valid_helptopics;
		my $n = 0;
		my $topics_per_line = 8;
		while (1) {
			! @topics and
				print("\n "),
				last
			or
			$n++ % $topics_per_line == 0 and
				print("\n\t")
			or
				print(" ", shift(@topics))
			;
		}
		print "\n\n";
		return(1);
	}
	# If we get here, @blurbs names one story.
	my $blurb = shift @blurbs;

	# Big if-elsif clause to switch on requested topic.
	#
	# Note that we try to make the output conform to ANVL syntax;
	# in the case of help output, every line tries to be a continuation
	# line for the value of an element called "Usage".  To do this we
	# pass all output through a routine that just adds a space after
	# every newline.  The end of the output should end the ANVL record,
	# so we print "\n\n" at the end.
	#
	my ($t, $i);
	if ($blurb eq "intro") {
		bprint $out,
qq@Usage:
              noid [-f Dbdir] [-v] [-h] Command Arguments@, ($brief ? qq@
              noid -h             (for help with a Command summary).@
	: qq@

Dbdir defaults to "." if not found from -f or a NOID environment variable.
For more information try "perldoc noid" or "noid help Command".  Summary:
@);
		$brief and
			print("\n\n"),
			return(1);
		for $t (@valid_commands) {
			$i = $info{"$t/brief"};
			! defined($i) || ! $i and
				next;
			bprint $out, $i;
		}
bprint $out, qq@
If invoked as "noidu...", output is formatted for a web client.  Give Command
as "-" to run a block of noid Commands read from stdin or from POST data.@;
		print "\n\n";
		return(1);
	}
	#elsif $blurb eq "dbcreate" and print $out $info{$blurb}
	#or
	#$blurb eq "bind" and print $out
	$brief and
		$blurb .= "/brief";
	$t = $info{$blurb};
	if (! defined($t) || ! $t) {
		print $out qq@Sorry: no information on "$blurb".\n\n@;
		return(1);
	}
	bprint $out, $t;
	print "\n";
	return(1);

# XXX fix these verbose messages

my $yyyy = qq@
Called as "noid", an id generator accompanies every COMMAND.  Called as
"noi", the id generator is supplied implicitly by looking first for a
NOID environment variable and, failing that, for a file calld ".noid" in
the current directory.  Examples show the explicit form.  To create a
generator, use

	noid ck8 dbcreate TPL SNAA

where you replace TPL with a template that defines the shape and number
of all identifiers to be minted by this generator.  You replace SNAA with
the name (eg, the initials) of the sub NAA (Name Assigning Authority) that
will be responsible for this generator; for example, if the Online Archive
of California is the sub-authority for a template, SNAA could be "oac".
This example of generator intialization,

	noid oac.noid dbcreate pd2.wwdwwdc oac

sets up the "oac.noid" identifier generator.  It can create "nice opaque
identifiers", such as "pd2pq5dk9z", suitable for use as persistent
identifiers should the supporting organization wish to provide such a
level of commitment.  This generator is also capable of holding a simple
sequential counter (starting with 1), which some callers may wish to use
as an internal number to keep track of minted external identifiers.
[ currently accessible only via the count() routine ]

In the example template, "pd2" is a constant prefix for an identifier
generator capable of producing 70,728,100 identifiers before it runs out.
A template has the form "prefix.mask", where 'prefix' is a literal string
prepended to each identifier and 'mask' specifies the form of the generated
identifier that will appear after the prefix (but with no '.' between).
Mask characters are 'd' (decimal digit), 'w' (limited alpha-numeric
digit), 'c' (a generated check character that may only appear in the
terminal position).

Alternatively, if the mask contains an 's' (and no other letters), dbcreate
initializes a generator of sequential numbers.  Instead of seemingly random
creates sequentially generated number.  Use '0s'
to indicate a constant width number padded on the left with zeroes.
@;
	return(1);
}

sub init_help {

	# For convenient maintenance, we store individual topics in separate
	# array elements.  So as not to slow down script start up, we don't
	# pre-load anything.  In this way only the requester of help info,
	# who does not need speed for this purpose, pays for it.
	#
	@valid_helptopics = qw(
		intro all templates
	);
	push(@valid_helptopics, @valid_commands);
	%info = (
		'bind/brief' =>
q@
   noid bind How Id Element Value	# to bind an Id's Element, where
      How is set|add|insert|new|replace|mint|append|prepend|delete|purge.
      Use an Id of :idmap/Idpattern, Value=PerlReplacementPattern so that
      fetch returns variable values.  Use ":" as Element to read Elements
      and Values up to a blank line from stdin (up to EOF with ":-").
@,
		'bind' =>
q@@,
		'dbinfo/brief' =>
q@@,
		'dbinfo' =>
q@@,
		'dbcreate/brief' =>
q@
   noid dbcreate [ Template (long|-|short) [ NAAN NAA SubNAA ] ]
      where Template=prefix.Tmask, T=(r|s|z), and mask=string of (e|d|k)
@,

		'dbcreate' =>
q|
To create an identifier minter governed by Template and Term ("long" or "-"),

   noid dbcreate [ Template Term [ NAAN NAA SubNAA ] ]

The Template gives the number and form of generated identifiers.  Examples:

    .rddd        minter of random 3-digit numbers that stops after the 1000th
    .zd          sequential numbers without limit, adding new digits as needed
  bc.sdddd       sequential 4-digit numbers with constant prefix "bc"
    .rdedeede    .7 billion random ids, extended-digits at chars 2, 4, 5 and 7
  fk.rdeeek      .24 million random ids with prefix "fk" and final check char

For persistent identifiers, use "long" for Term, and specify the NAAN, NAA,
and SubNAA.  Otherwise, use "-" for Term or omit it.  The NAAN is a globally
registered Name Assigning Authority Number; for identifiers conforming to the
ARK scheme, this is a 5-digit number registered with ark@cdlib.org, or 00000.
The NAA is the character string equivalent registered for the NAAN; for
example, the NAAN, 13030, corresponds to the NAA, "cdlib.org".  The SubNAA
is also a character string, but it is a locally determined and possibly
structured subauthority string (e.g., "oac", "ucb/dpg", "practice_area") that
is not globablly registered.
|,
		'fetch/brief' =>
q@
   noid fetch Id Element ...		# fetch/map one or more Elements
@,
		'fetch' =>
q@
To bind,

   noid bind replace fk0wqkb myGoto http://www.cdlib.org/foobar.html

sets "myGoto" element of identifier "fk0wqkb" to a string (here a URL).
@,
		'get/brief' =>
q@
   noid get Id Element ...		# fetch/map Elements without labels
@,
		'get' =>
q@@,
		'hello/brief' =>
q@@,
		'hello' =>
q@@,
		'hold/brief' =>
q@
   noid hold (set|release) Id ...	# place or remove a "hold" on Id(s)
@,
		'hold' =>
q@@,
		'mint/brief' =>
q@
   noid mint N [ Elem Value ]	# to mint N identifiers (optionally binding)
@,
		'mint' =>
q@@,
		'note/brief' =>
q@@,
		'note' =>
q@@,
		'peppermint/brief' =>
q@@,
		'peppermint' =>
q@@,
		'queue/brief' =>
q@
   noid queue (now|first|lvf|Time) Id ...	# queue (eg, recycle) Id(s)
      Time is NU, meaning N units, where U= d(ays) | s(econds).
      With "lvf" (Lowest Value First) lowest value of id will mint first.
@,
		'queue' =>
q@@,

		'validate/brief' =>
q@
   noid validate Template Id ...	# to check if Ids are valid
      Use Template of "-" to use the minter's native template.
@,
		'validate' =>
q@@,
	);
	return(1);
}

sub who_are_you { my( $web )=@_;

	my $user;
	if ($web) {
		$user = $ENV{'REMOTE_USER'} || '';
		my $host = $ENV{'REMOTE_HOST'} || $ENV{'REMOTE_ADDR'} || '';
		$user .= '@' . $host;
	}

	# Look up by REAL_USER_ID first.
	my ($name, undef, undef, $gid) = getpwuid($<);
	my $ugid = getlogin() || $name;
	! $ugid and
		return "";
	$ugid .= "/" . ((getgrgid($gid))[0] || "");

	# If EFFECTIVE_USER_ID differs from REAL_USER_ID, get its info too.
	if ($> ne $<) {
		($name, undef, undef, $gid) = getpwuid($>);
		! $name and
			return "";
		$ugid .= " ($name/" . ((getgrgid($gid))[0] || "") . ")";
	}
	$user = ($user ? "$user $ugid" : $ugid);
	return $user;
}

exit 0;

1;

# yyy Possible for 'c' mask char:
#	ASCII 33 to 126 (no SPACE, no DEL)  --> 94 (not prime)
#	MINUS the 5 chars:  / \ - % "       --> 89 (prime)
#    or MINUS the 5 chars:  / \ - % .       --> 89 (prime)
#    or MINUS the 5 chars:  / \ - % SPACE   --> 89 (prime)
#
# Note: current (1/2004) restrictions on ARKs are alphanums plus
#	= @ $ _ * + #
# with the following reserved for special purposes
#	/ . - %

# xxx noid example:  shuffle play (as in random song list)
# xxx bind is pair-wise or triple-wise?  (how to explain consistently)
# xxx mail to Evan Owens when noid is ready

__END__

=head1 NAME

noid - nice opaque identifier generator commands

=head1 SYNOPSIS

B<noid> [ B<-f> I<Dbdir> ] [ B<-vh> ] I<Command> I<Arguments>

=head1 DESCRIPTION

The B<noid> utility creates minters (identifier generators) and accepts
commands that operate them.  A minter efficiently generates, tracks,
and binds unique identifiers, which are produced without replacement
in random or sequential order, with or without a check character (for
detecting transcription errors).  A minter can bind identifiers to
arbitrary element names and element values that are either stored or
produced upon retrieval from rule-based transformations of requested
identifiers (e.g., with application to URL redirection).

Identifiers generated by these minters are also known as "noids" (nice
opaque identifiers).  Noid minters are suitable for the production and
management of identifiers ranging from persistent, globally unique
names -- ARKs, PURLs, URNs, Handles, LSIDs, etc. -- to short-lived,
compact session keys (cf. UUIDs).  Noid minters are very fast, scalable,
easy to create and tear down, and have a relatively small footprint.
They use BerkeleyDB as the underlying database, with locking and
transactions for concurrency control.

The form, number, and longevity of a minter's identifiers are determined
by a Template and a Term supplied when the generator database is created.
A supplied Term of "long" establishes extra restrictions and logging
appropriate for identifiers that are intended to be persistent.  Across
successive minting operations, the generator "uses up" its namespace
(the pool of identifiers it is capable of minting) such that no identifier
will ever be generated twice unless the supplied Term is "short" and the
namespace is finite and completely exhausted.
The default Term is "medium".

The B<noid> utility parameters -- flags, I<Dbdir> (database location),
I<Command>, I<Arguments> -- are described later in the COMMANDS section.
There are other sections covering TEMPLATES, RULEZ<>-BASED MAPPING,
and the URL INTERFACE.

=head1 TUTORIAL INTRODUCTION

To create a minter for an unlimited number of identifiers, you could try

	noid dbcreate s.zd

This produces a generator for medium term identifiers (the default) with
the Template, "s.zd", governing the order, number, and form of minted
identifier strings.  These identifiers will begin with the constant part
"s" and end in a digit (the final 'd'), all within an unbounded sequential
('z') namespace.  The TEMPLATES section gives a full explanation.
This generator will mint the identifiers, in order,

	s0, s1, s2, ..., s9, s10, ..., s99, s100, ...

and never run out.  To mint the first ten identifiers,

	noid mint 10

When you're done, on a UNIX platform you can remove that minter with

	rm -fr NOID

Now let's create a second minter with a more complex template.

	noid dbcreate f5.reedeedk long 13030 cdlib.org oac/cmp

This creates a generator for long term identifiers that begin with the
constant part "13030/f5".  Identifiers will emerge in "quasi-random"
order, each consisting of six characters matching up one-for-one with
the letters "eedeed".  The template's final 'k' causes a computed
check character to be added to the end of every generated identifier.
Exactly 70,728,100 identifiers will be minted before running out.

The 13030 parameter is the registered Name Assigning Authority Number
(NAAN) for the assigning authority known as "cdlib.org", and "oac/cmp"
is a string chosen by the person setting up this minter to identify the
project that will be operating it.  This particular minter generates
identifiers that start with the prefix "f5" in the 13030 namespace.
To register for a NAAN, request one by email to ark at cdlib dot org.

Although the order of minting is not obvious, it is "quasi-random" in the
sense that on your machine a minter created with the same Template will
always produce the same sequence of noids over its lifetime.  For example,
our second minter will generate identifiers that range from 13030/f5000000s
to 13030/f5zz9zz94.  The first two generated will be

	13030/f54x54g11    and    13030/f5154dn7k

Quasi-random is a shade more predictable than pseudo-random (which,
techically, is as random as computers get).  This is a feature designed
to help identifier managers in case they are forced to start minting again
from scratch; they simply process their objects over in the same order as
before to recover the original assignments.

	rm NOID/noid.bdb

The above command removes just enough of the minter to allow you to create
another minter in its place.

=head1 IDENTIFIER = ASSOCIATION = BINDING

An identifier is not a string of character data.  An identifier is an
association between a string of data and an object.  It doesn't matter
whether the object is physical, digital, or abstract -- without an
association, a string of data is just data.  The association can be
anything you say, but because it is an abstraction, that association
is easy to lose track of unless you write down your assertions.
To record the assertions supporting the association that defines an
identifier, a noid minter allows you to bind arbitrary named elements
and values to the identifier.  Noid element values (and names for that
matter) can be up to 4 gigabytes in length.

You don't have to use the noid binding features at all if you prefer to
keep track of your bindings elsewhere, such as in a separate database
management system (DBMS) or on a piece of paper.  At a minimum, for each
noid generated, the minter automatically stores a "circulation" record
asserting who generated it and when.

An arbitrary database system can complement a noid minter without any
awareness or dependency on noids.  Associations, the I<sine qua non> of
identifiers, last only as long as they (in particular, their bindings)
are maintained.  On computers, identifier bindings are typically managed
using methods that at some point map identifier strings to database records
and/or to filesystem entries (effectively using the filesystem as a DBMS).
The structures and logistics for bindings maintenance may reside entirely
with the minter database, entirely outside the minter database, or
anywhere in between.  An individual organization defines whatever
maintenance configuration suits it best.

A persistent identifier is an identifier that an organization commits
to retain in perpetuity.  Often maintaining identifiers goes hand in
hand with maintaining the objects to which they are bound.  No technology
exists that automatically maintains objects and associations; persistence
is a matter of service commitment, tools that support that commitment,
and information that allows users receiving identifiers to make the best
judgments regarding an organization's ability and intention to maintain
those identifiers.

It will be normal for other organizations to maintain their own assertions
about identifiers that you issue, and vice versa.  In general there is
nothing to prevent discrepancies among sets of assertions.  Effectively,
the association -- the identifier -- is in the eye of the beholder.  As a
simple example, authors create bibliography entries for cited works, and
in that process they make their claims (sometimes in error) about such
things as the author and title of the identified thing.  A conscientious
provider of an identifier-driven service (such as digital object retrieval)
will allow users to review the assertions it makes about identifiers that
it services, whether it minted none, some, or all of them.  We call such
an organization a Name Mapping Authority because it "maps" identifiers
to services.

For persistence across decades or centuries, an archiving organization
must be able to assert its views about the identity and support policy for
an object inherited through a chain of stewardship all the way back to
a completely unrelated and now defunct issuing organization.  For that
identifier to have persisted across the intervening years, it must look
the same as when first minted.  At that time global uniqueness would have
required the minted identifier to bear the imprint of the original issuing
organization, or Name Assigning Authority, which long ago ceased to have
any responsibility for its persistence.  There is thus no conflict in a
mapping authority servicing identifiers that originate in many different
assigning authorities.

These notions of service and persistence are built into the ARK (Archival
Resource Key) naming scheme that noid minters were designed, among other
things, to support; see L<http://ark.cdlib.org/> for more information.

=head1 COMMANDS

Once again, the overall utility summary is

=over 5

B<noid> [ B<-f> I<Dbdir> ] [ B<-vh> ] I<Command> I<Arguments>

=back

In all invocations, output is intended to be both human- and
machine-readable.  Bulk operations are possible, allowing multiple
minting and binding commands within one invocation.  In particular,
if I<Command> is given as an "-" argument, then actual I<Commands>
are read from the standard input.

The database directory string, I<Dbdir>, may be given with the B<NOID>
environment variable, overridable with the B<-f> option.  If those strings
are empty, the name or link name of the B<noid> executable (argv[0] for C
programmers) is checked to see if it reveals I<Dbdir>.  If that check
(described next) fails, I<Dbdir> is taken to be the current directory.

To check the executable for I<Dbdir>, the final pathname component (tail)
of its name is examined and split at the first '_' encountered.  If none,
the check fails.  Otherwise, the check is considered successful and the
latter half is taken as naming I<Dbdir> relative to the current directory.
This mechanism is designed for cases when it is inconvenient to specify
I<Dbdir> (such as in the URL interface) or when you are running several
minters at once.  As an example, F</usr/bin/noid_fk9> specifies a
I<Dbdir> of F<fk9>.

All files associated with a minter will be organized in a subdirectory,
F<NOID>, of I<Dbdir>; this has the consequence that there can be at most
one minter in a directory.  To allow B<noid> to create a new minter in
a directory already containing a F<NOID> subdirectory, it is sufficient
to remove the file, F<NOID/noid.bdb>, which is the heart of the minter
database.

The B<noid> utility may be run as a URL-driven web server application,
such as in a CGI that allows name assignment via remote operator.
If the executable begins B<noidu...>, the noid URL mode is in effect.
Input parameters, separated by a '+' sign, are expected to arrive
embedded in the query part of a URL, and output will be formatted
for display on an ordinary web browser.  An executable of B<noidu_xk4>,
for example, would turn on URL mode and set I<Dbdir> to I<xk4>.

At minter creation time, a report summarizing its properties is produced
and stored in the file, F<NOID/README>.  This report may be useful to the
organization articulating the operating policy of the minter.  In a formal
context, such as the creation of a minter for long term identifiers, that
organization is the Name Assigning Authority.

The B<-v> option prints the current version of the B<noid> utility and
B<-h> prints a help message.

In the I<Command> list below, capitalized symbols indicate values to be
replaced by the caller.
Optional arguments are in [brackets] and (A|B|C) means one of A or B or C.

=over 4

=item B<noid dbcreate> [ I<Template> [ I<Term> [ I<NAAN NAA SubNAA> ] ] ]

Create a database that will mint (generate) identifiers according to the
given Template and Term.  As a side-effect this causes the creation of
a directory, F<NOID>, within I<Dbdir>.  If you have several generators,
it may be convenient to operate each from within a I<Dbdir> that uniquely
identifies each Template; for example, you might change to a directory
that you named "fk6" after the Template "fk.rdeedde" ("fk" followed by
6 variable characters) of the minter that resides there.

The Term declares whether the identifiers are intended to be "long",
"medium" (the default), or "short".  A short term identifier minter is
the only one that will re-mint identifiers after the namespace is
exhausted, simply returning the oldest previously minted identifier.
As mentioned earlier, however, some namespaces are unbounded and never
run out of identifiers.

If Term is "long", the arguments NAAN, NAA, and SubNAA are required,
and all minted identifiers will be returned with the NAAN and a '/'
prepended to them.  The NAAN is a namespace identifier and should be a
globally unique Name Assigning Authority (NAA) number.  Apply for one
by email to ark at cdlib dot org.

If Template is not supplied, the minter becomes a "free binder", binding
any identifier that you submit without validating it first.  If you ask,
it also mints medium term identifiers under the default Template, ".zd".

=item B<noid mint> I<N> [ I<Element Value> ]

Generate N identifiers.  If other arguments are specified, for each
generated identifier, add the given Element and bind it to the given Value.
[Element-Value binding upon minting is not implemented yet.]

There is no "unmint" command.  Once an identifier has been circulated in
the outside world, it may be hard to withdraw because external users and
systems will have bound it with their own assertions.
Even within the minting organization, removing all of the identifier's
supporting bindings could entail actions such as file deletion that are
outside the scope of the minter.  While there is no command capable of
withdrawing a circulated identifier, it is nonetheless easy to B<queue>
an identifier for reminting and to B<hold> it against the possibility of
minting at all.  Identifiers that are long term should be treated as
non-renewable resources except when you are absolutely sure about
recycling them.

=item B<noid peppermint> I<N> [ I<Element Value> ]

[This command is not implemented yet.]
Generate N "peppered" identifiers.  A peppered identifier is a regular
identifier concatenated with a '!' character and a randomly generated
cookie -- the pepper -- which serves as a kind of per-identifier password.
(Salt is a technical term for some extra data that makes it harder to
crack encrypted values; we use pepper for some extra data that makes it
harder to crack unencrypted values.)  To provide an extra level of
database security, the base identifier, which is everything up to the '!',
should be used in all public communication, but the complete peppered
identifier is required for all noid operations that would change values
in the database.

As with the B<mint> command, if other arguments are specified, for each
generated identifier, add the given Element and bind it to the given Value.

=item B<noid bind> I<How Id Element Value>

For the given Id, bind the Element to Value according to How.  The
Element and Value may be arbitrary strings.  There are two reserved
Element names allowing Values to be entered that are too large or
syntactically inconvenient (depending on the calling environment's
quoting restrictions) to pass in conveniently as command-line tokens.

If the Element is ":" and no Value is present, lines are read
from the standard input up to a blank line; they will contain
Element-colon-Value pairs in essentially email header format,
with long values continued on indented lines.  If the Element is ":-"
and no Value is present, lines are read from the standard input up
to end-of-file; the first non-comment, non-blank line must have an
Element-colon to specify an Element name, and all the remaining input
(up to EOF) is taken as its corresponding Value.  Lines beginning
with '#' are considered "comment" lines and are skipped.

=for later XXX test the "and no Value is present" in the both cases above

The I<How> argument specifies one of following kinds of binding.  Of
these, the B<set>, B<add>, B<insert>, and B<purge> kinds "don't care"
if there is no current binding.

=over 6

=item B<new>

Only if Element does not exist, create a new binding.

=item B<replace>

Only if Element exists, undo any old bindings and create a new binding.

=item B<set>

Means B<new> or, failing that, B<replace>.

=item B<append>

Only if Element exists, place Value at the end of the old binding.

=item B<add>

Means B<new> or, failing that, B<append>.

=item B<prepend>

Only if Element exists, place Value at the beginning of the old binding.

=item B<insert>

Means B<new> or, failing that, B<prepend>.

=item B<delete>

Remove any trace of Element, returning an error if it did not exist to
begin with.

=item B<purge>

Remove any trace of Element, returning success whether or not it existed
to begin with.

=item B<mint>

Means B<new>, but discard Id (which must be given as B<new>)
and mint a new Id first.

=item B<peppermint>

[This kind of binding is not implemented yet.]
Means B<new>, but discard Id (which must be given as B<new>)
and peppermint a new Id first.

=back

The RULEZ<>-Z<>BASED MAPPING section explains how to set up retrieval
using non-stored values.

=item B<noid fetch> I<Id> [ I<Element> ... ]

For the identifier, Id, print with labels all bindings for the given
Elements.  If no Element is given, find and print all bindings for the
given Id.  This is the verbose version of the B<get> command, in that it
prints headers and labels for everything it finds.

=item B<noid get> I<Id> [ I<Element> ... ]

For the identifier, Id, print without labels all bindings for the given
Elements.  If no Element is given, find and print all bindings for the
given Id.  This is the quiet version of the B<fetch> command, in that it
suppresses all headers and labels.  For each Element requested, output
will be terminated by one newline (usually two newlines).

=item B<noid rmap> I<Id> [ I<Element> ... ]

For the identifier, Id, print all bindings for the given Elements on
exactly one line in a manner suitable for a web server RewriteMap
directive that calls the B<noid> utility to compute the mapping.
If no Element is given, find and print all bindings for the given Id.
This is a special version of the B<fetch> command that returns the
string "NULL" on a failed lookup.

=for later XXXXXX make the above true, and add refs to rmap under RULE-BASED MAPPING

=item B<noid hold> (B<set>|B<release>) I<Id> ...

Place or remove a "hold" on one or more Ids.  A hold placed on an Id that
has not been minted will cause it to be skipped when its turn to be minted
comes around.  A hold placed on an Id that has been minted will make it
impossible to queue (typically for recycling).  Minters of long term
identifiers automatically place a hold on every minted identifier.
Holds can be placed or removed manually at any time.

=item B<noid queue> (B<now>|B<first>|B<lvf>|I<Time>) I<Id> ...

Queue one or more Ids for minting.  Time is a number followed by units,
which can be "d" for days or "s" for seconds (the default units).  This
can be used to recycle identifiers B<now> or after a delay period.  With
B<first>, the Id(s) will be queued such that they will be minted before
any of the time delayed entries.  With B<lvf> (Lowest Value First), the
lowest valued identifier (intended for use with numeric identifiers) will
be taken from the queue for minting before all others.  [ needs testing ]

=for comment XXX is lvf tested enough?

=item B<noid validate> (I<Template>|B<->) I<Id> ...

Validate one or more Ids against a given Template, which, if given as
"B<->", causes the minter's native I<Template> to be used.

=back

=head1 TEMPLATES

A Template is a coded string of the form Prefix.Mask that is given to
the noid B<dbcreate> command to govern how identifiers will be minted.
The Prefix, which may be empty, specifies an initial constant string.
For example, upon database creation, in the Template

	tb7r.zdd

the Prefix says that every minted identifier will begin with the literal
string "tb7r".  Each identifier will end in at least two digits ("dd"),
and because of the 'z' they will be sequentially generated without limit.
Beyond the first 100 mint operations, more digits will be added as needed.
The minted identifiers will be, in order,

   tb7r00, tb7r01, ..., tb7r99, tb7r100, tb7r101, ..., tb7r1000, ...

The period ('.') in the Template does not appear in the identifiers but
serves to separate the constant first part (Prefix) from the variable
second part (Mask).  In the Mask, the first letter determines either
random or sequential ordering and the remaining letters each match up
with characters in a generated identifier.  Perhaps the best way to
introduce templates is with examples ranging from the simpler to the
more complex.

=over 10

=item B<.rddd>

to mint random 3-digit numbers, stopping after 1000th

=item B<.sdddddd>

to mint sequential 6-digit numbers, stopping after millionth

=item B<.zd>

sequential numbers without limit, adding new digits as needed
 
=item B<bc.rdddd>

random 4-digit numbers with constant prefix "bc"

=item B<8rf.sdd>

sequential 2-digit numbers with constant prefix "8rf"

=item B<.se>

sequential extended-digits (from 0123456789bcdfghjkmnpqrstvwxz)

=item B<h9.reee>

random 3-extended-digit numbers with constant prefix "h9"

=item B<.zeee>

unlimited sequential numbers with at least 3 extended-digits

=item B<.rdedeedd>

random 7-char numbers, extended-digits at chars 2, 4, and 5

=item B<.zededede>

unlimited mixed digits, adding new extended-digits as needed

=item B<sdd.sdede>

sequential 4-mixed-digit numbers with constant prefix "sdd"

=item B<.rdedk>

random 3 mixed digits plus final (4th) computed check character

=item B<.sdeeedk>

5 sequential mixed digits plus final extended-digit check char

=item B<.zdeek>

sequential digits plus check char, new digits added as needed

=item B<63q.redek>

prefix plus random 4 mixed digits, one of them a check char

=back

The first letter of the Mask, the generator type, determines the order
and boundedness of the namespace.  For example, in the Template ".sddd",
the Prefix is empty and the 's' says that the namespace is sequentially
generated but bounded.  The generator type may be one of,

=over 4

=item B<r>

for quasi-randomly generated identifiers,

=item B<s>

for sequentially generated identifiers, limited in length and
number by the length of the Mask,

=item B<z>

for sequentially generated identifiers, unlimited in length or
number, re-using the most significant mask character (the second
character of the Mask) as needed.

=back

After the generator type, the rest of the Mask determines the form of
the non-Prefix part, matching up letter-for-character with each generated
identifier character with an exception in the 'z' case described below.
In the case of the Template "xv.sdddd", the last four 'd' Mask characters
say that all identifiers will end with four digits, so the last identifier
in the namespace is "xv9999".

When 'z' is used, the namespace is unbounded, and the second character
('e' or 'd') of the Mask will be repeated as often as needed when
lengthening the identifier with new digits; for instance, when all
4-digit numbers are used up a 5th digit will be added.  After the
generator type character, Mask characters have the following meanings:

=over 4

=item B<d>

a pure digit, one of { 0123456789 }

=item B<e>

an "extended digit", one of { 0123456789bcdfghjkmnpqrstvwxz }
(lower case only)

=item B<k>

a computed check character, which will be an extended digit;
if present, this must be the final Mask character

=back

The set of extended digits is designed to help create more compact
identifiers (a larger namespace for the same length of identifier) and
discourage "accidental semantics", namely, the introduction of strings that
have unintended but commonly recognized meanings.  Opaque identifiers are
desirable in many situations and the absence of vowels in extended digits
is a step in that direction.  To reduce visual mismatches, there is also
no letter 'l' (ell) because it is often mistaken for the digit '1'.

The optional 'k' Mask character, which may only appear at the end, enables
detection of cases when a single character is mistyped and when two
adjacent characters have been transposed -- the most common transcription
errors.  A final 'k' in the Mask will cause a check character to be
appended after first computing it on the entire identifier generated so
far, including the NAAN if one was specified at database creation time.
For example, in

	13030/f54x54g11 

the final digit '1' was first computed over the string "13030/f54x54g1"
and then added to the end.

=head1 RULEZ<>-Z<>BASED MAPPING

Any Element may be bound to a class of Ids such that retrieval
against that Element for any Id in the class returns a computed value when
no stored value exists.  The class of Ids is specified via a Perl regular
expression that will be checked for a match against Ids submitted via a
retreival operation (B<get>, B<fetch>, or B<rmap>) that names any Element
bound in this manner.  If the match succeeds, the element Value that was
bound with the Id class is used as the right-hand side of a Perl
substitution, and the resulting transformation is returned.  Here we call
this rule-based mapping.  It is probably best explained by working through
the examples below.

To set up rule-based mapping for an Id class, construct a bind operation
with an Id of the form ":idmap/I<Idpattern>", where I<Idpattern> is a Perl
regular expression.  Then choose an Element name that you wish to have
trigger the pattern match check whenever that Element is requested via a
retrieval operation and a stored value does NOT exist; any Element will
work as long as you use it for both binding and retrieving.  Finally,
specify a Value to be used as replacement text that transforms matching
Ids into computed values via a Perl s/// substitution.  As a simple example,

       noid bind set :idmap/^ft redirect g7h

would cause any subsequent retrieval request against the Element named
"redirect" to try pattern matching when no stored value is found.
If the Id begins with "ft", it would then try to replace the "ft" with
"g7h" and return the result as if it were a stored value.  So if the Id
were "ft89xr2t", the command

       noid get ft89xr2t redirect

would return "g7h89xr2t".  Fancier substitutions are possible, including
replacement patterns that reference subexpressions in the original
matching I<Idpattern>.  For example, the second command below,

       noid bind set ':idmap/^ft([^x]+)x(.*)' my_elem '$2/g7h/$1'
       noid get ft89xr2t my_elem

would return "r2t/g7h/89".  For ease of implementation, internally this kind
of binding is stored and reported (which can be confusing) as the special
identifier, :idmap/I<Element>, under an element name of I<Idpattern>.

=head1 URL INTERFACE

Any number of minters can be operated behind a web server from a browser
or any tool that activates URLs.  This section describes a one-time set up
procedure to make your server aware of minters, followed by another set up
procedure for each minter.  The one-time procedure involves creating a
directory in your web server document tree where you will place one or
more noid minter databases.  In this example, we use I<htdocs/nd>:

	mkdir htdocs/nd
	cp -p /usr/local/bin/noid htdocs/nd/

The second command above creates an executable copy of the noid script
that will be linked to for each minter you intend to expose to the web.
To make your server recognize such links, include the line

	ScriptAliasMatch ^/nd/noidu(.*) "/srv/www/htdocs/nd/noidu$1"

in your server configuration file and restart the server before trying the
commands that follow.  If you did not install the supporting I<Noid.pm>
module normally, you may also have to store a copy of it next to the script.
This completes the one-time server set up.

Thereafter, for each minter that you wish to expose, it must first be
allowed to write to its own database when invoked via the web server.
Because it will be running under a special user at that time, before you
create it, first become the user that your server runs under.  In this
example that user is "wwwrun".

	cd htdocs/nd
	su wwwrun
	noid dbcreate kt.reeded
	mkdir kt5
	mv NOID kt5/
	ln noid noidu_kt5

The third command above creates a minter for identifiers beginning with
"kt" followed by 5 characters.  The minter is then moved into its own
directory within "htdocs/nd".  Finally, the last command makes a hard
link (not a soft link) to the noid script, which for this minter, will
be invoked under the name "noidu_kt5".

The URL interface is similar to the command line interface, but
I<Commands> are passed in via the query string of a URL where by
convention a plus sign ('+') is used instead of spaces to separate
arguments.  There is no B<dbcreate> command available from the URL
interface.

To mint one identifier, you could enter the following URL into your
web browser, but replace "foo.ucop.edu" with your server's name:

    http://foo.ucop.edu/nd/noidu_kt5?mint+1 

Reload to mint again. If you change the 1 to 20, you get twenty new and
different noids.

    http://foo.ucop.edu/nd/noidu_kt5?mint+20 

To bind some data to an element called "myGoto" under one of the noids
already minted, 

    http://foo.ucop.edu/nd/noidu_kt5?
	bind+set+13030/fk1bk16wb+myGoto+http://foo.ucsd.edu/ 

In this case we stored a URL in "myGoto".  This kind of convention can
underly a redirection mechanism that is part of an organization's overall
identifier resolution mechanism.  To retrieve that stored data, 

    http://foo.ucop.edu/nd/noidu_kt5?get+13030/fk1bk16wb+myGoto 

Bulk operations can be performed over the web by invoking the URL with a
query string of just "-", which will cause the minter to look for noid
commands, one per line, in the POST data part of the HTTP request.  If
you put noid commands in a file I<myCommands> and ran the Unix utility

    curl --data-binary @myCommands 'http://dot.ucop.edu/nd/noidu_kt5?-'

you could, for example, change the "myGoto" bindings for 500 identifiers
in that one shell command.  The output from each noid command in the file
will be separated from the next (on the standard output) by a blank line.

=head1 NAME RESOLUTION AND REDIRECTION

	ScriptAliasMatch ^/nd/noidr(.*) "/srv/www/htdocs/nd/noidr$1"

XXXXXXX
Note noidr_kt5, not noidu_kt5:

	ln noid noid_kt5

 RewriteEngine on
 RewriteMap    resolver         prg:/srv/www/htdocs/nd/noidr_kt5 -
 RewriteRule   ^ark:/(.*)$      ${resolver:get $1 myGoto}
 RewriteRule   ^$               not found
 RewriteRule   ^http://(.*)$    http://$1 [R]

xxx set timeout to prevent apache from hanging??
xxx use $|= 1; to unbuffer!

# RedirectMap   ^ark:/12025/(.*)$    http://ark.nlm.nih.gov/ark:/12025/$1

=head1 NOID CHECK DIGIT ALGORITHM

The following describes the Noid Check Digit Algorithm (NCDA).  Digits
in question are actually "extended digits", an ordered set of digits
and characters of radix (cardinality) R.  In the example described below
we use a specific set of R=29 characters.

When applied to substrings of well-formed identifiers, where the length
of the substring is less than R, the NCDA is "perfect" for single digit
and transposition errors, by far the most common user transcription errors
(see David Bressoud, Stan Wagon, "Computational Number Theory, 2000, Key
College Publishing").  The NCDA is complemented by well-formedness rules
that confirm the placement of constant data, including fixed labels and
any characters that are not extended digits.  After running the NCDA on
the selected substring, the resulting check (extended) digit is used
either for comparing with a received check digit or for appending to
the substring prior to issuing the identifier that will contain it.

For the algorithm to work, the substring in question must be less than
R characters.  The extended digit set used in the current instance is a
sequence of R=29 printable characters, or "xdigits", defined as follows:

  xdigit:   0   1   2   3   4   5   6   7   8   9   b   c   d   f   g
   value:   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

  xdigit:   h   j   k   m   n   p   q   r   s   t   v   w   x   z
   value:  15  16  17  18  19  20  21  22  23  24  25  26  27  28

Each xdigit in the identifier has the corresponding ordinal value shown.
Any character not in the xdigit set is considered in the algorithm to
have an ordinal value of zero.

A check digit is an xdigit computed from the base substring and then
appended to form the "checked substring" (less than R+1 characters long).
To determine if a received identifier has been corrupted by a single
digit or transposition error, the relevant substring is extracted and
its last character is compared to the result of the same computation
performed on the preceding substring characters.

The computation has two steps.  Consider a base substring (that has no
check digit appended to it) such as

    13030/xf93gt2	(base substring)

Step 1.  Check that the substring is well-formed, that is, that all
non-xdigit characters (often constant character data) are exactly
where expected; if not, the substring is not well-formed and the
computation aborts.  (This step is required to accommodate characters
such as '/' that contribute nothing to the overall computation.)

Step 2.  Multiply each character's ordinal value by its position number
(starting at position 1), and sum the products.  For example,

  character:   1   3   0   3   0   /   x   f   9   3   g   t   2
    ordinal:   1   3   0   3   0   0  27  13   9   3  14  24   2
   position:   1   2   3   4   5   6   7   8   9  10  11  12  13
    product:   1 + 6 + 0 +12 + 0 + 0+189+104 +81 +30+154+288 +26 = 891

Step 3.  The check digit is the xdigit whose ordinal value is that sum
modulo R (divide the sum by R and take the remainder).

In the example, 891 = 21 mod R (29) and so the check digit is 'q'.
This is appended to obtain the "checked substring", which is

    13030/xf93gt2q	(substring with check digit appended)

What follows is a two-part proof that this algorithm is "perfect" with
respect to single digit and transposition errors.

B<Lemma 1:>  The NCDA is guaranteed against single-character errors.

Proof:  We must prove that if two strings differ in one single char,
then the check digit (xdigit) also differs.  If the n-th xdigit's ordinal
is d in one string and e in another, the sums of products differ only by

    (... + nd + ...) - (... + ne + ...) = n(d - e)

The check digits differ only if n(d - e) is not 0 mod R.  Assume
(contrapositively) that n(d - e) does equal 0 mod R.  First, we know
that n(d - e) is not zero because n is positive and d is different from e.
Therefore, there must be at least one positive integer i such that

    n(d - e) = Ri    =>    (n/i)(d - e) = R

Now, because R is prime,

    either   (a)  n/i = 1    and   d - e = R
    or       (b)  n/i = R    and   d - e = 1

But (a) cannot hold because xdigit ordinals differ by at most R-1.  This
leaves (b), which implies that there is an integer i = n/R.  But since R
is prime and n (a position number) is a positive integer less than R,
then 0 < i < 1, which cannot be true.  So the check digits must differ.

B<Lemma 2:>  The NCDA is guaranteed against transposition of two single
characters.

Proof:  Non-contributing characters (non-xdigits) transposed with other
characters will be detected in Step 1 when checking the constraints for
well-formedness (e.g., the '/' must be at position 6 and only at position
6).  Therefore we need only consider transposition of two xdigit
characters.  We must prove that if one string has an xdigit of ordinal
e in position i and an xdigit of ordinal d in position j, and if another
string is the same except for having d in position i and e in position j,
then the check digits also differ.  The sums of the products differ by

    (... + ie + ... + jd + ...) - (... + id + ... + je + ...)
       = (ie + jd) - (id + je) = e(i - j) + d(j - i)
       = d(j - i) - e(j - i)   = n(d - e)

where n = j - i > 0 and n < R.  The check digits differ only if
n(d - e) = 0 mod R.  This reduces to the central statement of Lemma 1,
which has been proven.

=head1 TO DO

Add features that are documented but not implemented yet:  Element-Value
binding upon minting; the B<peppermint> command.  The B<append> and
B<prepend> kinds of binding currently have string-level semantics
(new data is added as characters to an existing element); should there
also be list-level semantics (new data added as an extra subelement)?

Add extra options for B<dbcreate>.  An option to specify one or more
identifier labels to strip from requests, and one canonical label to
add upon minting and reporting.  An option to set the initial seed for
quasi-random ordering.  An option to disable the locking subsystem gives
you more speed if you take responsibility for serializing minter access.

Extend the Template Mask to allow for other character repertoires with
prime numbers of elements.  These would trade a some eye-friendliness
for much more compact identifiers.

 { 0-9 a-z _ }			   cardinality 37, mask character 'v'
 { 0-9 a-z A-Z _ + * @ # }	   cardinality 67, mask character 'w'
 Visible ASCII - { / . \ % - } 	   cardinality 89, mask character 'c'

Add support for simple file management associated with identifiers.
For example, minting (and reminting) the noid "xv8t984" could result in
the creation (and re-creation) of a corresponding canonical directory
"xv/8t/98/4/".

=head1 BETA SOFTWARE

This utility is in the beta phase of development.  It is open source
software written in the Perl scripting language with strictest type,
value, and security checking enabled.  While its readiness for
long term application is still being evaluated, it comes with a
growing suite of regression tests (currently about 250).

=head1 COPYRIGHT

Copyright (c) 2002-2004 UC Regents.  All rights reserved.

=head1 BUGS

Probably.  Please report to jak at ucop dot edu.

=head1 FILES

=over 17

=item F<NOID>

directory containing all database files related to a minter

=item F<NOID/noid.bdb>

the BerkeleyDB database file at the heart of a minter

=item F<NOID/README>

the creation record containing minter analysis details

=back

=head1 SEE ALSO

L<perl(1)>, L<uuidgen(1)>

=over 4

=head1 PREREQUISITES

Perl Modules: L<Noid>, L<BerkeleyDB>, L<Text::ParseWords>, L<Getopt::Long>

Script Categories:

=pod SCRIPT CATEGORIES

CGI
UNIX : System_administration
Web

=back

=head1 AUTHORS

John A. Kunze, Michael A. Russell.

=cut