#!/bin/ksh
#!/bin/ksh93
#^^^ Make this line be the first line if the ksh you want to use is installed
#    as /bin/ksh.
# ksh88 can be used to interpret this program, but the autoincrementing
# (t and l) operators to the -m option will not work.
#
#@ This program came from: ftp://ftp.armory.com/pub/scripts/ren
#@ Look there for the latest version.
#@ If you don't find it, look through http://www.armory.com/~ftp/
#
# @(#) rename files by changing selected parts of filenames. (3.3.2 2004-08-16)
# 1990-06-01 John H. DuBois III (john@armory.com)
# 1991-02-25 Improved help info
# 1992-06-07 Remove quotes from around shell pattern as required by new ksh
# 1994-05-10 Exit if no globbing chars given.
# 1995-01-23 Allow filename set to be given on command line.
# 1997-09-24 1.4 Let [] be used for globbing.  Added x option.
# 1997-11-26 1.4.1 Notice if the sequences of globbing chars aren't the same.
# 1999-05-13 Changed name to ren to avoid conflict with /etc/rename
# 2000-01-01 1.4.2 Let input patterns that contain whitespace be used.
# 2001-02-14 1.5 Better test for whether old & new globbing seqs are identical.
# 2001-02-20 1.6 Added pP options.
# 2001-02-27 1.7 Added qf options.  Improved interpretation of rename patterns.
# 2001-05-10 1.8 Allow multiple pP options.  Added Qr options.
# 2001-07-25 2.0 Added mz options.
# 2001-11-25 2.1 Allow segment ranges to be given with -m.  Work under ksh93.
# 2002-03-17 2.1.1 Fixed bug in test for legal expressions.
# 2002-10-25 3.0 Overhauled to work with all ksh globbing patterns.
#            Bugfix: Do not act on explicitly named files unless they match
#            pattern.
# 2002-10-26 3.0.1 Treat arguments that begin with + as non-option arguments,
# 2003-01-25 3.1 Added s and t operators to -m.
#            Do not allow -z to truncate fields.
#            Allow math operations that evaluate to zero.
# 2003-09-21 3.2 Operate on files in all-or-nothing mode, and do intelligent
#            rename ordering.
#            Added i option.
# 2004-03-11 3.3 Added l operator to -m.
#            Made t operator work properly with intelligent rename ordering.
#            Make identity renaming always succeed.
# 2004-04-01 3.3.1 ksh93 compatibility bugfix.
# 2004-08-16 3.3.2 Prevent text that begins with 0 from being interpreted as
#            an octal value

# todo: Allow use of extended regexps, with () to enumerate pieces and \num to
# todo: select them.
# todo: Let input & output base be specified for -m option.
# todo: Let bases & leading-zeroes be specified for each instance of -m.
# todo: Option like -m for string ops (performing general substitutions,
#       setting case, length, etc.)
# todo: For -m, alternative to -z to indicate that number should include at
#       least as many characters as the source did.
# todo: Allow renaming of a file to itself to always succeed (and be a noop)
# todo: Options to set starting value and increment for -m variables.
# bug: ren '*' '*-'  renames files to '*\-' ??

### Start pattern library
# @(#) pattern 1.0.1 2003-06-26
# 2002-10-25 John H. DuBois III (john@armory.com
# 2003-06-26 1.0.1 ksh93 port - escape ] in @()
#
# getpiece
#
# Usage:
# getpiece filename-pattern
# This function finds the smallest prefix of filename-pattern that contains
# an optional fixed-text prefix followed by a minimal complete globbing
# pattern (as described below).
# Returns values in globals:
# getpiece_fixed is set to any fixed-text prefix.
# getpiece_pat is set to the globbing pattern, if found.
# getpiece_suffix is set to the remainder of the filename-pattern, which may
# contain more globbing patterns.
#
# Both getpiece_fixed and getpiece_pat include quoting such that they can be
# eval'ed.  Globbing characters are left unquoted.
#
# Return value:
# On success, 0.
# On error, 1.  The only error is for a pattern to have an unclosed
# parenthesized globbing operator: that is, a !(, +(, ?(,, *(, or @(
# that is not closed with a ).
#
# The globbing patterns understood by the following code and the manner in
# which the end of the patterns is recognized are as follows:
#
# ?, *:	Single character pattern.
# [set]	If a ] follows the opening [ either immediately or after a ! that
# 	itself immediately follows the [, it is taken to be part of the
# 	set rather than a closing ].  Other than this, the ONLY way that ] may
# 	be embedded in the set is by escaping it with a \.
# c(pattern), where c is one of the characters !+?*@:  Since this type of
# 	pattern may be nested, the pattern continues until each c( has been
# 	balanced by a ).  Within a pattern, the only way to include a literal
# 	) is by escaping it with a \.
# For both [] and c(), \ is escaped by preceding it with another \.
#
# Quoting:
# For simplicity, this code uses \ for all quoting except for that of newline,
# which is quoted with ''.  To be safe, all characters except globbing chars
# and -0-9A-Za-z_.,/:+!=@% are quoted.
# For some of those, quoting is benign, but e.g. - and ! inside of
# [] must not be quoted if they are to have their desired effect.
function getpiece {
    typeset inbracket=false opiece
    integer parenlevel=0

    getpiece_suffix=$1 
    getpiece_pat=
    getpiece_fixed=

    while [[ -n $getpiece_suffix ]]; do
	# If string begins with [!], the token consists of three chars.
	# If it begins with \x, c( or [], the token consists of two chars.
	# The special cases for [!] and [] are recognized because the ] in
	# theses cases does not close the bracket set.
	# Otherwise it consists of one.
	opiece=$getpiece_suffix
	if [[ $getpiece_suffix == "[!]"* ]]; then
	    getpiece_suffix=${getpiece_suffix#???}
	elif [[ $getpiece_suffix == @(\\?|[+!?*@]\(|\[\])* ]]; then
	    getpiece_suffix=${getpiece_suffix#??}
	else
	    getpiece_suffix=${getpiece_suffix#?}
	fi
	# $getpiece_suffix is quoted to prevent it from being interpreted as a
	# pattern
	token="${opiece%"$getpiece_suffix"}"
	# Quoting of non-globbing chars
	if (( ${#token} == 1 )); then
	    if [[ $token == '
' ]]; then
		token="'$token'"
	    elif [[ $token != [-'][)|_.,/:+!=@%*?'0-9A-Za-z] || parenlevel -eq 0 && $token == ['|)'] ]]; then
		token="\\$token"
	    fi
	fi
	if $inbracket; then
	    getpiece_pat="$getpiece_pat$token"
	    [[ $token == \] ]] && break
	elif (( parenlevel > 0 )); then
	    getpiece_pat="$getpiece_pat$token"
	    case "$token" in
	    \))
		(( $((parenlevel-=1)) == 0 )) && break
		;;
	    [+!?*@]\()	# make sure we do not match "\("
		((parenlevel+=1))
		;;
	    esac
	else
	    # Still looking at the fixed-string prefix.
	    case "$token" in
	    \[*)
		inbracket=true
		getpiece_pat=$token
		;;
	    [+!?*@]\()
		parenlevel=1
		getpiece_pat=$token
		;;
	    [?*])
		getpiece_pat=$token
		break
		;;
	    *)
		getpiece_fixed="$getpiece_fixed$token"
		;;
	    esac
	fi
    done
    (( parenlevel == 0 ))
    return 
}

# Usage: quotepat <pattern>
# <pattern> is a ksh globbing pattern.  It is quoted such that it is safe to
# eval.  The quoted pattern is stored in the global quotepat.
# Return value:
# On success, 0.
# On error, 1.  The only error is for a pattern to have an unclosed
# parenthesized globbing operator: that is, a !(, +(, ?(,, *(, or @(
# that is not closed with a ).
function quotepat {
    typeset pattern=$1

    quotepat=
    while [[ -n $pattern ]]; do
	getpiece "$pattern"
	quotepat="$quotepat$getpiece_fixed$getpiece_pat" || return 1
	pattern=$getpiece_suffix
    done
    return 0
}

# patsplit: Split text into two pieces according to a pair of patterns.
# Usage: patsplit pat1 pat2 text
# text must match pat1pat2.
# The patterns must have already been preprocessed so that they can be eval'd.
#
# Results:
# The text that matches pat1 is stored in global patsplit_left
# The text that matches pat2 is stored in global patsplit_right
#
# Failure status is returned in the case that this splitting cannot be done.
# This should never occur if text matches pat1pat2.
#
# Operation:
# Given a pattern of the form pat1pat2, pat1 should get the maximum possible
# match while still allowing pat2 to match.  Unfortunately using shell pattern
# matching it is difficult to determine how the text should be split between
# them.
# Ugly solution:
# Get minimal trailing text that matches pat2.  Move this from text to suffix.
# Test whether the entire remaining text matches pat1.
# If so, we're done.
# If not, move characters one by one from the end of text to the start of
# suffix until we once again have a suffix that matches pat2.
# Test whether the remaining text matches pat1.
# Repeat until this works.
# If we reach a point where there is no remaining text and this does not match
# pat1, something went terribly wrong...

function patsplit {
    typeset pat1=$1 pat2=$2 text=$3 tm

    if [[ -z $pat1 && -z $pat2 && -z $text ]]; then
	patsplit_left=
	patsplit_right=
	return 0
    fi
    eval patsplit_left=\${text%$pat2}
    patsplit_right=${text#"$patsplit_left"}

    # The \'\' ensure proper operation if pat2 or pat1 is empty.
    while eval [[ \$patsplit_right != "$pat2"\'\' '||' \$patsplit_left != "$pat1"\'\' ]]; do
	[[ -z $patsplit_left ]] && return 1
	tm=$patsplit_left
	patsplit_left=${patsplit_left%?}
	patsplit_right=${tm#"$patsplit_left"}$patsplit_right
    done
    return 0
}
### End pattern library

## Start of main program

name=${0##*/}
Usage="Usage:
$name [-fhqtv] [-m<segstart[:segend]=operation>] [-z<len>] [-[pP]<pattern>] 
    oldpattern [newpattern [filename ...]]
or
$name -r [same options as above] oldpattern newpattern directory ..."
tell=false
verbose=false
warn=true
warnNoFiles=true
debug=false
recurse=false
integer inclCt=0 exclCt=0
check=true
integer z_var op_end_seg
autoinc=false
integer mvct=0
immediate=false

# The following are used to deal with +options
# OPTIND is set to the index of next argument to be processed.  This may or
# may not be the same argument as that which is currently being processed,
# depending on whether the current option is the last option in the
# argument.  We need to know the index of the current argument, so we track
# it separately by initializing curind and updating it after processing
# each option.
integer curind=1
set -A args -- "" "$@"

while getopts :hitvxp:P:fqQrm:z: opt; do
    case $opt in
    h)
	print -r -- \
"$name: rename files by changing selected parts of filenames.
$Usage

     oldpattern and newpattern are filename globbing patterns.  The globbing
operators understood are those of ksh: ?, *, [], ?(), *(), @(), +(), !().  The
special meaning of these operators can be overridden by preceding them with a
backslash (\\).  A literal backslash may be included as \\\\.
     All filenames that match oldpattern will be renamed with the filename
characters that match the constant (non-globbing) characters of oldpattern
changed to the corresponding constant characters of newpattern.  The characters
of the filename that match the globbing operators of oldpattern will be
preserved.  Globbing operators in oldpattern must occur in the same order in
newpattern; for every globbing operator in newpattern there must be an
identical globbing operator in oldpattern in the same sequence.  All characters
within a parenthesized globbing operator are considered to be part of the
globbing operator.  newpattern is required in all cases except when -m is given
and no further arguments are given.  Both pattern arguments should be quoted
because globbing operators are special to the shell.  In zsh, you can set up an
alias to avoid having to quote arguments every time you use $name:
alias ren='noglob ren'
ksh has no noglob builtin, but you can create a noglob command in ksh88 with:
alias noglob='set -f; trap \"trap - DEBUG; set +f\" DEBUG;'
Note that both of these will also prevent the use of globbing to generate a
list of explicit filenames for $name to operate on.

     If filenames are given, only those named are acted on; if not, all
filenames that match oldpattern are acted on unless -p is used.
    If you are unsure whether a $name command will do what you intend, issue it
with the -t option first to determine whether it will have the desired effect.

    Renames are done on an all-or-nothing basis: if any rename would fail as a
result of a filename collision, no renames are done.  Also, files will be
renamed in any order that will allow the renames to succeed.  For example, if
foo1 is being renamed to foo2 and foo2 is being renamed to foo3, foo2 will be
renamed first, then foo1.  The -i option turns off both the all-or-nothing
behavior and the intelligent-rename-order behavior, and intelligent rename
ordering does not apply if any autoincrementing operators are given with the -m
option.
    Files are always allowed to be \"renamed\" to themselves; in this case no
rename action is taken.

Examples:
$name \"/tmp/foo*.ba.?\" \"/tmp/new*x?\"
    All filenames in /tmp that match foo*.ba.? will have the \"foo\" part
    replaced by \"new\" and the \".ba.\" part replaced by \"x\".
    For example, /tmp/fooblah.ba.baz would be renamed to /tmp/newblahxbaz.
$name \* \*- foo bar baz
    foo, bar, and baz will be renamed to foo-, bar-, and baz-.
$name '????????' '????-??-??'
    All filenames that are 8 characters long will be changed such that dashes
    are inserted after the 4th and 6th characters.
$name 'foo+([0-9]).c' 'bar+([0-9]).c'
    All filenames that consist of foo followed by 1 or more digits followed by
    .c are renamed with bar instead of foo.  See the ksh man page for more
    details of its extended patterns.
Options:
-h: Print this help.
-r: Recursive operation.  Filenames given on the command line after oldpattern
    and newpattern are taken to be directories to traverse recursively.  For
    each subdirectory found, the specified renaming is applied to any matching
    filenames.  oldpattern and newpattern should not include any directory
    components.  The files within each directory are renamed on in an
    all-or-nothing basis, but failure to rename the files in one directory does
    not prevent renaming in others.
-p<pattern>, -P<pattern>: Act only on filenames that do (if -p is given) or do
    not (if -P is given) match the ksh-style filename globbing pattern
    <pattern>.  This further restricts the filenames that are acted on, beyond
    the filename selection produced by oldpattern and the filename list (if
    any).  <pattern> must be quoted to prevent it from being interpreted by the
    shell.  Multiple instances of these options may be given.  In this case,
    filenames are acted on only if they match at least one of the patterns
    given with -p and do not match any of the patterns given with -P.
-m<segstart[:segend]=operation>: For each file being renamed, perform a
    mathematical operation on the string that results from concatenating
    together the filename segments that matched globbing operator numbers
    segstart through segend and replace the string with the result of the
    operation.  If segend is not given, the only segment acted on is startseg
    (this is the usual case, since ordinarily only one segment is to be acted
    on).  If segend is given, any fixed text in newpattern that occurs between
    the staring and ending segments is discarded.  If there are fewer globbing
    segments than segend, no complaint is issued; the string is formed from
    segment segstart through the last segment that does exist.  Multiple -m
    options may be given, each acting on a different range of segments; no more
    than one -m option may apply to any particular segment.  If -m is used,
    newpattern may be an empty string or not given at all (if no directory/file
    names are given).  In this case, it is taken to be the same as oldpattern.

    Segments are numbered in order of occurrence from the left.  For example,
    in the pattern a?b*c[0-9]f, segment 1 consists of the character that
    matched ?, segment 2 consists of the character(s) that matched *, and
    segment 3 consists of the character that matched [0-9].  If nested
    operators are used (operators within a parenthesized operator), the entire
    contents of the outermost operator are counted as one operator.  For
    example, this is one operator: @(x|+(0-9)|[x-z])

    These variables are provided to generate an output number from:
    i: If the concatenated string of segments consists entirely of characters
       that can be interpreted as a decimal integer, the value is assigned to
       the variable 'i'.  If the concatenated string does not have this form
       and any operation that includes 'i' is given, the file is skipped.
    s: A sequence number is provided as the variable 's'.  For the first
       file acted on, s is set to 1, for the next it set to 2, etc.  If a
       collision occurs (a file with the target filename already exists), s is
       incremented whether or not the operation succeeds (which in turn depends
       on whether the -f option was given).
    t: 't' is like 's', except that if a filename generated from a operation
       that includes 't' would result in a collision (a file with the target
       name already exists), 't' is autoincremented until a filename is
       generated that does not result in collision.
    l: Lowest available number.  Each time a filename is generated, numbers are
       tried starting from 1, and the first available filename is used.  This
       allows the simultaneous renaming of multiple filename sequences.

    The difference between t and l is simply that l restarts its number search
    from 1 each time a file is acted on.  If the intent is to have a single
    sequence of numbers in files regardless of what the rest of the filename
    is, 't' should be used; if each file should be independently renamed with
    the lowest possible number, l should be used.

    The mathematical operations available are those understood by the ksh
    interpreter, which includes most of the operators and syntax of the C
    language.

    Examples:
    $name -m3=i+6 '??*.ppm'
	This is equivalent to:
	$name -m3=i+6 '??*.ppm' '??*.ppm'
	Since the old pattern and new pattern are identical, this would
	normally be a no-op.  But in this case, if a filename of ab079.ppm is
	acted on, it is changed to ab85.ppm.
    $name '-m1:2=i*2' 'foo??bar'
	This will change a file named foo16bar to foo23bar
    $name '-m1:2=i*2' 'foo?xyz?bar'
	This will change a file named foo1xyz9bar to foo38bar
    $name '-m1=i+36' 'foo.+([0-9]).ppm'
	This will add 36 to the string of digits in any foo.<digits>.ppm file.
    $name -m1=s 'src/img*.jpg' 'dest/img*.jpg'
        Renames all of the img*.jpg files in the src directory to have
	sequentially numbered filenames starting with dest/img1.jpg.
    $name -m1=s 'src/img*.jpg' 'dest/img*.jpg' src/img?.jpg src/img??.jpg
        Like the above, except that filenames are given explicitly so that
        names with single digits are acted on before those with two digits.
        Without this, filenames would be acted on in lexicographical order,
        which places e.g. img10.jpg before img2.jpg.  If there are also
        filenames with three digits, src/img???.jpg would have to be included.
        If the order that files are named in is not important, this is not
        neccessary.  This problem can be avoided by always naming files so
        that the maximum number of digits is included, using leading zeroes as
        nececssary (see the -z option).
    $name -z2 -m1=s+8 'src/*.jpg' 'dest/img*.jpg'
    	Like the above, except that target filenames start with dest/img09.jpg,
	and all source filenames are assumed to include leading zeroes as
	neccessarry to make the lexicographic and numeric sorting identical.
    $name -z2 -m1=t 'src/*.jpg' 'dest/img*.jpg'
    	Like the above, except that target filenames start with the first
	available target name, \"filling in\" missing names.
    $name -z2 -q -m1=s 'img*.jpg'
	This can be used to \"compress\" a range of filenames.  For example,
	a range of filenames might originally have included everything from
	img01.jpg through img60.jpg.  If some files are removed, gaps are
	created in the number sequence.  When the above command is executed,
	it will first try to move img01.jpg to img01.jpg, which will fail since
	the target filename exists.  Since -q is given, no complaint will be
	issued.  This will continue until the first gap is reached, at which
	point higher-numbered files will begin to be moved down.
    $name -z2 -m1=l 'img*.*'
	This will simultaneous compress all of the filename sequences that
	match the pattern.  For example, you might have three sequences, giving
	various forms for the same set of images: img*.jpg, img*.thumb.jpg, and
	img*.tif.  If you remove a particular image number from all of the
	sequences, the above command will renumber them all so that there is no
	numbering gap.
-z<len>: Set the minimum size of the number fields that result when -m is used.
    The field is padded on the left to <len> digits with leading zeroes.  If
    a value that results from a -m operation has more than <len> digits, all of
    the digits are preserved (the value is not truncated to <len> digits).
    In the ab079.ppm example above, if -z3 is given, the output filename will
    be ab085.ppm.
-i: Independent, immediate rename.  Each file is renamed independent of whether
    other files can be renamed without collision.  This also turns off
    intelligent rename ordering.  This option can be used if $name fails
    because there are too many files to do batched (all-or-nothing) renaming.
-f: Force rename.  By default, $name will not rename files if a file with the
    new filename already exists.  If -f is given, $name will carry out the
    rename anyway.  This turns on the -i option.
-q: Quiet operation.  By default, $name will notify the user if a rename
    results in a collision, whether or not the target file is replaced (as
    determined by whether -f is given).  If -q is given, no notification is
    issued, again regardless of whether or not the target file is replaced.
-Q: Suppress other warnings.  By default, a warning is issued if no files are
    selected for acting upon.  If -Q is given, no warning is issued.
-v: Show the rename commands being executed.
-t: Show what renamings would be done, but do not carry them out."
	exit 0
	;;
    f)
	check=false
	immediate=true
	;;
    i)
	immediate=true
	;;
    q)
	warn=false
	;;
    Q)
	warnNoFiles=false
	;;
    r)
	warnNoFiles=false
	recurse=true
	;;
    t)
	tell=true
	;;
    v)
	verbose=true
	;;
    x)
	verbose=true
	debug=true
	;;
    p)
	quotepat "$OPTARG"
	inclusionPats[inclCt]=$quotepat
	((inclCt+=1))
	;;
    P)
	quotepat "$OPTARG"
	exclusionPats[exclCt]=$quotepat
	((exclCt+=1))
	;;
    m)
	# Store operation for each segment number in ops[num]
	# Store ending segment number in op_end_seg[num]
	range=${OPTARG%%=*}
	op=${OPTARG#*=}
	start=${range%%:*}
	end=${range#*:}
	if [[ $start != +([0-9]) || $start -eq 0 ]]; then
	    print -ru2 -- "$name: Bad starting segment number given with -m: $start"
	    exit 1
	fi
	if [[ "$end" != +([0-9]) || "$end" -eq 0 ]]; then
	    print -ru2 -- "$name: Bad ending segment number given with -m: $end"
	    exit 1
	fi
	if (( start > end )); then
	    print -ru2 -- "$name: Ending segment ($end) is less than starting segment ($start)"
	    exit 1
	fi
	if [[ "$op" != @(|*[!_a-zA-Z0-9])[istl]@(|[!_a-zA-Z0-9]*) ]]; then
	    print -ru2 -- \
	    "$name: Operation given with -m does not reference 'i', 's', 't', or 'l': $op"
	    exit 1
	fi
	# Test whether operation is legal.  let returns 1 both for error
	# indication and when last expression evaluates to 0, so evaluate 1
	# after test expression.
	i=1 s=1 t=1 l=1
	let "$op" 1 2>/dev/null || {
	    print -ru2 -- \
	    "$name: Bad operation given with -m: $op"
	    exit 1
	}
	ops[start]=$op
	op_end_seg[start]=$end
	;;
    z)
	if [[ "$OPTARG" != +([0-9]) || "$OPTARG" -eq 0 ]]; then
	    print -ru2 -- "$name: Bad length given with -z: $OPTARG"
	    exit 1
	fi
	# This also changes z_var from integer type to string type
	typeset -Z$OPTARG z_var || exit 1
	;;
    +?)
	# Patterns are liable to be given with a leading +, as in '+(foo)'.
	# Since there is no way to tell getopts to not treat +x as an option,
	# +option where o is a legal option will show up here.
	OPTIND=$curind
	break
	;;
    :) 
	print -r -u2 \
"$name: Option -$OPTARG requires a value.
$Usage
Use -h for help."
	exit 1
	;;
    \?) 
	# +option where o is not a legal option will show up here.
	# See +? case.
	if [[ ${args[curind]} == +* ]]; then
	    OPTIND=$curind
	    break
	fi
	print -r -u2 \
"$name: -$OPTARG: no such option.
$Usage
Use -h for help."
	exit 1
	;;
    esac
    curind=OPTIND
done
 
# remove args that were options
((OPTIND-=1))
shift $OPTIND

if (( $# < 1 )); then
    print -r -u2 -- "$Usage
Use -h for help."
    exit 1
fi

oldpat=$1
newpat=$2

# If -m is given, a non-existant or null newpat should be set to oldpat
if (( ${#ops[*]} > 0 )); then
    case $# in
    1)
	set -- "$oldpat" "$oldpat"
	newpat=$oldpat
	$debug && print -ru2 -- "Set new pattern to: $newpat"
	;;
    *)
	if [[ -z $newpat ]]; then
	    shift 2
	    set -- "$oldpat" "$oldpat" "$@"
	    newpat=$oldpat
	    $debug && print -ru2 -- "Set new pattern to: $newpat"
	fi
	;;
    esac
fi

origPat=$oldpat

# Make sure input patterns that contain whitespace can be expanded properly
IFS=

integer patSegNum=1 numPatSegs

# Build list of non-pattern segments and globbing segments found in arguments.
# Also builds up a quoted (eval-able) version of oldpat.
#
# The patterns given are used to get the list of filenames to act on,
# to delimit constant segments, and to determine which parts of filenames are
# to be replaced.
#
# Examples given for first iteration (in the example, the only iteration)
# Example oldpat: foo*.a  Example newpat: bar*.b
#
# The || newpat  is to ensure that new pattern does not have more globbing
# segments than old pattern
quoted_oldpat=
while [[ -n $oldpat || -n $newpat ]]; do
    ## Get leftmost globbing pattern in oldpat
    getpiece "$oldpat" || {
	print -ru2 -- \
	"$name: Unclosed parenthesized globbing operator in this pattern:
$origPat"
	exit 1
    }
    pat=$getpiece_pat			# pat=*
    # oldpre[] stores the old constant part before the pattern,
    # so that it can be removed and replaced with the new constant part.
    oldpre[patSegNum]=$getpiece_fixed	# oldpre[1]=foo
    # oldsuf stores the part that follows the globbing pattern,
    # so that it too can be removed.
    # After oldpre[] & oldsuf[] have been removed from a filename, what remains
    # is the part matched by the globbing pattern, which is to be retained.
    oldsuf[patSegNum]=$getpiece_suffix	# oldsuf[1]=.a
    oldpat=$getpiece_suffix
    quoted_oldpat="$quoted_oldpat$getpiece_fixed$getpiece_pat"

    getpiece "$newpat"

    if [[ "$pat" != "$getpiece_pat" ]]; then
	print -ru2 -- \
"$name: Old-pattern and new-pattern do not have the same sequence of globbing chars.
Pattern segment $patSegNum: Old pattern: $pat  New pattern: $getpiece_pat"
	exit 1
    fi

    # newpre[] stores the new constant part before the pattern,
    # so that it can be used to replace the old constant part.
    newpre[patSegNum]=$getpiece_fixed	# newpre[1]=bar
    newpat=$getpiece_suffix		# newpat=.b
    # Store either * or ? in pats[], depending on whether this segment matches 1
    # or any number of characters.
    [[ "$pat" == \[* ]] && pat=?
    pats[patSegNum]=$pat
#    $debug && print -ru2 -- \
#	    "oldsuf[$patSegNum]=\"${oldsuf[$patSegNum]}\"	pats[$patSegNum]=\"${pats[patSegNum]}\""
    ((patSegNum+=1))
done

if (( patSegNum == 1 )); then
    print -u2 "No globbing chars in pattern."
    exit 1
fi

oldpre[patSegNum]=${oldpat%%"$pat"*}	# oldpre[2]=.a
oldsuf[patSegNum]=${oldpat#*"$pat"}	# oldsuf[2]=.a
newpre[patSegNum]=${newpat%%"$pat"*}	# newpre[2]=.b

numPatSegs=patSegNum

# Any autoincrementing sequence numbers given in ops?
integer patSegNum=0
while (( patSegNum <= numPatSegs )); do
    if [[ "${ops[patSegNum]}" == @(|*[!_a-zA-Z0-9])[tl]@(|[!_a-zA-Z0-9]*) ]]; then
	# Must do this in a subshell; causes ksh88 to exit
	( typeset -A zorch ) 2>/dev/null || {
	    print -ru2 -- \
"$name: The ksh interpreting this program does not support associative arrays,
so autoincrementing operators can not be used.
Exiting."
	    exit 1
	}
	autoinc=true

	# These must have global scope, so declare them here
	typeset -A removed_files added_files

	break
    fi
    ((patSegNum+=1))
done

if $debug; then
    print -r "Quoted oldpat: $quoted_oldpat"
    patSegNum=1
    while (( patSegNum <= numPatSegs )); do
	print -ru2 -- \
"$patSegNum: Old prefix: <${oldpre[patSegNum]}>   Old suffix: <${oldsuf[patSegNum]}>   New prefix: <${newpre[patSegNum]}>   Pattern: <${pats[patSegNum]}>"
	((patSegNum+=1))
    done
fi

# Example filename: foox.a
# Example oldpat: foo*.a
# Example newpat: bar*.b

integer numFiles=0 s=0 t=0 l

# Usage: renameFile filename [dirname]
# [dirname] is a directory name to prefix filenames with when they are printed
# for informational purposes.
# Uses globals:
#     inclCt exclCt inclusionPats[] exclusionPats[] ops[]
#     numPatSegs oldpre[] oldsuf[] newpre[] pats[]
#     check warn tell verbose name
# Modifies globals: numFiles
function renameFile {
    typeset file=$1 subdir=$2 good_gen_name formatted
    integer patSegNum patnum
    typeset origname porigname newfile matchtext pnewfile matchsegs op
    integer startseg endseg result

    if eval [[ \$1 != "$quoted_oldpat" ]]; then
	print -ru2 -- "Filename '$1' does not match the given pattern '$origPat'"
	return 1
    fi
    origname=$file	# origname=foox.a
    porigname=$subdir$file
    # Unfortunately, ksh88 does not do a good job of allowing for patterns
    # stored in variables.  Without the conditional expression being eval'ed,
    # only sh patterns are recognized.  If the expression is eval'ed, full
    # ksh expressions can be used, but then expressions that contain whitespace
    # break unless the user passed a pattern with the whitespace properly
    # quoted, which is not intuititive.  This is fixed in ksh93; full patterns
    # work without being eval'ed.
    if (( inclCt > 0 )); then
	# Check whether the filename given matches any of the inclusion
	# patterns
	patnum=0
	while (( patnum < inclCt )); do
	    eval [[ \$file == "${inclusionPats[patnum]}" ]] && break
	    ((patnum+=1))
	done
	if (( patnum == inclCt )); then
	    $debug && print -ru2 -- "Skipping not-included filename '$porigname'"
	    return 1
	fi
    fi
    patnum=0
    while (( patnum < exclCt )); do
	# Check whether the filename given matches any of the exclusion
	# patterns
	if eval [[ \$file == ${exclusionPats[patnum]} ]]; then
	    $debug && print -ru2 -- "Skipping excluded filename '$porigname'"
	    return 1
	fi
	((patnum+=1))
    done
    # Extract matching segments from filename
    ((numFiles+=1))
    patSegNum=1
    while (( patSegNum < numPatSegs )); do
        # Remove a fixed prefix iteration:	     1            2
	file=${file#${oldpre[patSegNum]}}	# file=x.a	file=

	$debug && print -ru2 "Splitting \"$file\" into segments matching \"${pats[patSegNum]}\" and \"${oldsuf[patSegNum]}\""
	patsplit "${pats[patSegNum]}" "${oldsuf[patSegNum]}" "$file" || {
	    # Should never happen, but might on systems with whacked filesystem
	    # semantics (case insensitive, etc.).
	    print -ru2 -- \
"$name: Pattern matching failure - how odd!
patsplit '${pats[patSegNum]}' '${oldsuf[patSegNum]}' '$file' failed.
Pattern segment number was $((patSegNum+1)) of $numPatSegs."
	    exit 1
	}
	$debug && print -ru2 -- "Left part: \"$patsplit_left\"   Right part: \"$patsplit_right\""
	matchtext=$patsplit_left
	file=$patsplit_right
	$debug && print -ru2 -- "Matching segment $patSegNum: <$matchtext>"
	matchsegs[patSegNum]=$matchtext
	((patSegNum+=1))
    done

    ((s+=1))	# increment sequence number if we get this far
    l=0		# l always starts from beginning

    good_gen_name=false
    
    # If we're using an autoincrementing operator, we will iterate until it
    # succeeds; otherwise this loop is only executed once.
    while ! $good_gen_name; do
	# Paste fixed and matching segments together to form new filename.
	patSegNum=0
	newfile=
	((t+=1))
	((l+=1))
	while (( patSegNum <= numPatSegs )); do		# For each globbing pattern
	    matchtext=${matchsegs[patSegNum]}
	    startseg=patSegNum

	    if [[ -n ${ops[startseg]} ]]; then
		endseg=${op_end_seg[startseg]}
		op=${ops[startseg]}
		while (( patSegNum < endseg )); do
		    ((patSegNum+=1))
		    matchtext=$matchtext${matchsegs[patSegNum]}
		done
		if [[ "$matchtext" != +([-0-9]) &&
		"$op" == @(|*[!_a-zA-Z0-9])i@(|[!_a-zA-Z0-9]*) ]]; then
		    print -ru2 -- \
"Segment(s) $startseg - $endseg ($matchtext) of file '$porigname' do not form an integer; skipping this file."
		    return 2
		fi
		# Ensure that text is not interpreted as an octal value
		[[ $matchtext != +(0) ]] && matchtext=${matchtext##+(0)}
		i=$matchtext
                # let returns 1 both for error indication and when last
                # expression evaluates to 0, so evaluate 1 after test
                # expression.
		let "result=$op" 1 || {
		    print -ru2 -- \
"Operation failed on segment(s) $startseg - $endseg ($matchtext) of file '$porigname'; skipping this file."
		    return 2
		}
		# If -z is given and a result has more digits than were given
		# with -z, the typeset -Z formatting will truncated it, which
		# we do not want.  Test for this by checking whether the value
		# assigned to z_var is still equal to result. 
		((z_var=result))
		(( z_var == result )) && formatted=$z_var || formatted=$result
		$debug && print -ru2 -- "Converted $matchtext to $formatted"
		matchtext=$formatted
	    fi

	    newfile=$newfile${newpre[startseg]}$matchtext		# newfile=barx	newfile=barx.b
	    ((patSegNum+=1))
	done

	# If we are using an autoincrementing operator, we must keep iterating
	# until we find a filename that is available.
	if $autoinc; then
	    if $immediate; then
		[[ "$newfile" == "$origname" || ! -e "$newfile" ]] && good_gen_name=true
	    else
		# If doing intelligent rename ordering, we must keep track of
		# what files will exist and what files will have been removed.
		# removed_files[] records files that have been (virtually) removed;
		# added_files[] records files that have been (virtually) added.
		# A filename is available if it:
		# (is not in added_files[]) AND (it does not exist OR is in removed_files[]) 
		if [[ ! -n ${added_files["$newfile"]} &&
			( "$newfile" == "$origname" || -n ${removed_files["$newfile"]} || ! -e "$newfile" ) ]]; then
		    good_gen_name=true
		    # Ordering here is important in the case that $newfile == $origname
		    added_files["$newfile"]=1
		    removed_files["$origname"]=1
		    added_files["$origname"]=
		    removed_files["$newfile"]=
		fi
	    fi
	else
	    good_gen_name=true
	fi
    done

    pnewfile=$subdir$newfile

    if $immediate; then
	doMove $check $warn "$origname" "$newfile" "$porigname" "$pnewfile"
    else
	$debug && print -ru2 -- "Recording rename of $origname to $newfile"
	orignames[mvct]=$origname
	if (( $? != 0 )); then
	    print -ru2 -- \
"$name: Too many files for batched (all-or-nothing) renaming.
Try the -i option (see the description of it first!"
	    exit 1
	fi
	newfiles[mvct]=$newfile
	porignames[mvct]=$porigname
	pnewfiles[mvct]=$pnewfile
	((mvct+=1))
    fi
}

# Usage: doMove check warn old-name new-name printable-old-name printable-new-name
# check:   Files should not be renamed if it would result in a collision.
# warn:    Warn about collisions (otherwise be quiet).
# Globals:
# name:	   Name of the program, for messages.
# tell:    Tell what we would do, but do not actually do the rename.
# verbose: Tell what we're doing.
function doMove {
    typeset check=$1 warn=$2 origname=$3 newfile=$4 porigname=$5 pnewfile=$6

    if $check && [[ -e $newfile && $newfile != "$origname" ]]; then
	$warn &&
	print -ru2 -- "$name: Not renaming \"$porigname\"; destination filename \"$pnewfile\" already exists."
	return 2
    fi
    if $tell; then
	if [[ $newfile == "$origname" ]]; then
	    print -r -- "Would take no action for: $porigname -> $pnewfile"
	else
	    print -n -r -- "Would move: $porigname -> $pnewfile"
	    $warn && [[ -e $newfile ]] && print -n -r " (destination filename already exists; would replace it)"
	    print ""
	fi
    else
	if $verbose; then
	    if [[ $newfile == "$origname" ]]; then
		print -r -- "Taking no action for: $porigname -> $pnewfile"
	    else
		print -n -r -- "Moving: $porigname -> $pnewfile"
		$warn && [[ -e $newfile ]] && print -n -r -- " (replacing old destination filename \"$pnewfile\")"
		print ""
	    fi
	elif [[ $newfile == "$origname" ]]; then
	    return 0
	elif $warn && [[ -e $newfile ]]; then
	    print -r -- "$name: Note: Replacing old file \"$pnewfile\""
	fi
	mv -f -- "$origname" "$newfile"
    fi
}

# usage:
# inset check-word word-list
# Return value:
# If check-word is in word-list, 0.
# If not, 1.
function inset {
    typeset checkword=$1 word

    shift
    for word; do
	[[ $checkword == "$word" ]] && return 0
    done
    return 1
}

# This could do with all sorts of optimization.
# Also, we could detect cycles & deal with them by using a tempfile name.
function batchMove {
    integer i order_i=0 filenum order
    typeset newfile movedfiles check_l warn_l

    $immediate && return 0

    # ksh88 bug: "${array[@]}" is not expanded properly if IFS is set to empty
    # string.
    IFS=' '
    $debug && print -ru2 -- "Generating sequence for ${#orignames[*]} file renames"

    # While there are files to move...
    while (( order_i < mvct )); do
	# Find a file that can be moved
	i=0
	while ((i < mvct)); do
	    # If this file has not yet been dealt with, and either there is no
	    # file in the way of its move or there is but that file will have
	    # been moved by the time we get to this one...
	    if [[ -z ${movedfiles[i]} ]]; then
		if [[ ${orignames[i]} == ${newfiles[i]} || ! -e ${newfiles[i]} ]] ||
			inset "${newfiles[i]}" "${movedfiles[@]}"; then
		    break
		fi
	    fi
	    ((i+=1))
	done
	if (( i >= mvct )); then	# Could not move any files.
	    if $warn; then
		print -ru2 -- "$name: Not renaming any files due to these destination file collisions:"
		i=0
		while ((i < mvct)); do
		    [[ -z ${movedfiles[i]} ]] &&
			    print -ru2 -- "${orignames[i]}: Destination ${newfiles[i]} exists."
		    ((i+=1))
		done
	    fi
	    return 1
	fi
	# We can move this file.  Set it up.
	order[order_i]=i
	((order_i+=1))
	movedfiles[i]=${orignames[i]}
	$debug && print -ru2 -- "Move $order_i is file $i: ${orignames[i]} -> ${newfiles[i]}"
    done

    # If we are not actually going to move files, turn these off else they are
    # liable to result in warnings about collisions that would actually be
    # avoided due to intelligent rename ordering.
    # But if we are, leave them on in case a target filename is generating
    # since the last time it was checked for.
    if $tell; then
	check_l=false 
	warn_l=false 
    else
	check_l=$check
	warn_l=$warn
    fi

    i=0
    while ((i < order_i)); do
	filenum=${order[i]}
	$debug && print -ru2 -- "Executing move $((i+1)): file $filenum: ${orignames[filenum]} -> ${newfiles[filenum]}"
	doMove $check_l $warn_l "${orignames[filenum]}" "${newfiles[filenum]}" "${porignames[filenum]}" "${pnewfiles[filenum]}"
	((i+=1))
    done

    mvct=0	# reset for next batch
}

# Generate list of filenames to act on.
case $# in
[01])
    print -u2 "$Usage\nUse -h for help."
    exit 1
    ;;
2)
    if $recurse; then
	print -r -u2 "$name: No directory names given with -r.  Use -h for help."
	exit 1
    fi
    eval set -- "$quoted_oldpat"	# Get list of all filenames that match 1st globbing pattern.
    if [[ ! -e $1 ]]; then
	$warnNoFiles && print -r -- "$name: No filenames match this pattern: $origPat"
	exit
    fi
    ;;
*)
    shift 2
    ;;
esac

if $recurse; then
    oPWD=$PWD
    find "$@" -depth -type d ! -name '*
*' -print | while read dir; do
	cd -- "$oPWD"
	if cd -- "$dir"; then
	    for file in $origPat; do
		renameFile "$file" "$dir/"
	    done
	    batchMove
	else
	    print -ru2 -- "$name: Could not access directory '$dir' - skipped."
	fi
    done
else
    for file; do
	renameFile "$file"
    done
    batchMove
fi

if (( numFiles == 0 )); then
    $warnNoFiles && print -ru2 -- \
    "$name: All filenames either did not match the given pattern
or were excluded by patterns given with -p or -P."
fi