libisofs-legacy/libisofs/ecma119_tree.c

/* vim: set noet ts=8 sts=8 sw=8 : */

#include <string.h>
#include <wchar.h>
#include <stdlib.h>
#include <assert.h>

#include "ecma119.h"
#include "ecma119_tree.h"
#include "tree.h"
#include "util.h"
#include "eltorito.h"

static size_t calc_dirent_len(struct ecma119_tree_node *n)
{
	int ret = n->iso_name ? strlen(n->iso_name) + 33 : 34;
	if (ret % 2) ret++;
	return ret;
}

static void 
replace_node_mode(struct ecma119_write_target *t, struct stat *st) 
{
	if ( S_ISDIR(st->st_mode) ) {
		if ( t->replace_mode & 0x02 ) {
			/* replace dir mode with specific */
			st->st_mode &= S_IFMT;
			st->st_mode |= t->dir_mode;
		} else if (t->replace_mode & 0x01) {
			/* replace dir mode with default */
			/* read perm */
			mode_t new_mode = (st->st_mode & S_IFMT) | 0444;
			/* search bit if any */
			if ( st->st_mode & 0111)
				new_mode |= 0111;
			st->st_mode = new_mode;
		}
	} else {
		if ( t->replace_mode & 0x04 ) {
			/* replace file mode with specific */
			st->st_mode &= S_IFMT;
			st->st_mode |= t->file_mode;
		} else if (t->replace_mode & 0x01) {
			/* replace file mode with default */
			/* read perm */
			mode_t new_mode = (st->st_mode & S_IFMT) | 0444;
			/* execute bit if any */
			if ( st->st_mode & 0111)
				new_mode |= 0111;
			st->st_mode = new_mode;
		}
		
	} 
	if ( t->replace_mode & 0x08 ) {
		/* replace gid mode with specific */
		st->st_gid = t->gid;
	} else if (t->replace_mode & 0x01) {
		st->st_gid = 0;
	}
	if ( t->replace_mode & 0x10 ) {
		/* replace gid mode with specific */
		st->st_uid = t->uid;
	} else if (t->replace_mode & 0x01) {
		st->st_uid = 0;
	}
}

static struct ecma119_tree_node*
create_ecma119_node(struct ecma119_write_target *t,
                    struct ecma119_tree_node *parent,
                    struct iso_tree_node *iso)
{
	struct ecma119_tree_node *ret;
	char *(*iso_name)(const char *, const char *) = ISO_ISDIR(iso) ?
		 ((t->iso_level == 1) ? iso_1_dirid : iso_2_dirid)
	   : ((t->iso_level == 1) ? iso_1_fileid : iso_2_fileid);
	char *(*iso_r_name)(const char *, const char *, int) = 
		ISO_ISDIR(iso) ? iso_r_dirid : iso_r_fileid;

	assert(t && (!parent || parent->type == ECMA119_DIR) && iso );

	ret = calloc(1, sizeof(struct ecma119_tree_node));
	
	/*
	 * If selected one ISO relaxed constraints other than NO_DIR_REALOCATION,
	 * we use the function that computes the relaxed name, otherwise normal
	 * function for specified level is used.
	 */
	ret->iso_name = iso->name ? 
		( t->relaxed_constraints & ~ECMA119_NO_DIR_REALOCATION ? 
		  iso_r_name(iso->name, t->input_charset, t->relaxed_constraints) :
		  iso_name(iso->name, t->input_charset)
		) : NULL;
	ret->dirent_len = calc_dirent_len(ret);
	ret->attrib = iso->attrib;
	if ( t->rockridge && t->replace_mode ) 
		replace_node_mode(t, &ret->attrib);
		
	if (!iso->name)
		ret->full_name = NULL;	
	else if ( strcmp(t->input_charset,t->ouput_charset) )
		ret->full_name = convert_str(iso->name, t->input_charset, 
		                             t->ouput_charset);
	else
		ret->full_name = strdup(iso->name);
	ret->target = t;
	ret->parent = parent;
	return ret;
}

static struct ecma119_tree_node*
create_dir(struct ecma119_write_target *t,
	   struct ecma119_tree_node *parent,
	   struct iso_tree_node_dir *iso)
{
	struct ecma119_tree_node *ret;

	assert(t && (!parent || parent->type == ECMA119_DIR)
			&& iso && S_ISDIR(iso->node.attrib.st_mode));

	ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
	ret->type = ECMA119_DIR;
	ret->info.dir.real_parent = parent;
	ret->info.dir.depth = parent ? parent->info.dir.depth + 1 : 1;
	ret->info.dir.nchildren = 0;
	ret->info.dir.children = calloc(1, sizeof(void*) * iso->nchildren);
	return ret;
}

static struct ecma119_tree_node*
create_file(struct ecma119_write_target *t,
	    struct ecma119_tree_node *parent,
	    struct iso_tree_node_file *iso)
{
	struct ecma119_tree_node *ret;
	struct iso_file *file;

	assert(t && iso && parent && parent->type == ECMA119_DIR);

	ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
	ret->type = ECMA119_FILE;
	
	/* get iso_file struct */
	file = iso_file_table_lookup(t->file_table, iso);
	if ( file == NULL ) {
		file = iso_file_new(iso);
		iso_file_table_add_file(t->file_table, file);
		file->ino = ++t->ino;
	} else {
		/* increment number of hard-links */
		file->nlink++;
	}
	
	ret->attrib.st_nlink = file->nlink;
	ret->attrib.st_ino = file->ino;
	ret->info.file = file;
	return ret;
}

static struct ecma119_tree_node*
create_placeholder(struct ecma119_write_target *t,
	    struct ecma119_tree_node *parent,
	    struct ecma119_tree_node *real)
{
	struct ecma119_tree_node *ret;

	assert(t && real && real->type == ECMA119_DIR 
	       && parent && parent->type == ECMA119_DIR);

	ret = calloc(1, sizeof(struct ecma119_tree_node));
	ret->iso_name = real->iso_name; /* TODO strdup? */
	/* FIXME
	 * if we strdup above, if name changes in mangle_all, 
	 * this probably keeps as original.
	 * if not, both change, but we need to update dirent_len.
	 * I think that attributes of a placeholder must be taken from
	 * real_me, not keept here.
	 * FIXME
	 * Another question is that real is a dir, while placeholder is
	 * a file, and ISO name restricctions are different, what to do? 
	 */
	ret->dirent_len = real->dirent_len;
	ret->attrib = real->attrib;
	ret->full_name = strdup(real->full_name);
	ret->target = t;
	ret->parent = parent;
	ret->type = ECMA119_PLACEHOLDER;
	ret->info.real_me = real;
	ret->attrib.st_nlink = 1;
	ret->attrib.st_ino = ++t->ino;
	return ret;
}

static struct ecma119_tree_node*
create_symlink(struct ecma119_write_target *t,
	    struct ecma119_tree_node *parent,
	    struct iso_tree_node_symlink *iso)
{
	struct ecma119_tree_node *ret;

	assert(t && iso && parent && parent->type == ECMA119_DIR);

	ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
	ret->iso_name = iso->node.name ? ((t->iso_level == 1) ? 
	                           iso_1_fileid(iso->node.name, t->input_charset)
						     : iso_2_fileid(iso->node.name, t->input_charset))
			      : NULL;
	ret->type = ECMA119_SYMLINK;
	ret->info.dest = iso->dest; /* TODO strdup? */
	ret->attrib.st_nlink = 1;
	ret->attrib.st_ino = ++t->ino;
	return ret;
}

static struct ecma119_tree_node*
create_boot_catalog(struct ecma119_write_target *t,
	                struct ecma119_tree_node *parent,
	                struct iso_tree_node_boot_catalog *iso)
{
	struct ecma119_tree_node *ret;
	struct iso_file *file;

	assert(t && iso && parent && parent->type == ECMA119_DIR);

    /* 
     * This will simply create a ECMA119 file, with the only difference
     * that the iso_file is not taken from table, but from boot catalog
     */

	ret = create_ecma119_node(t, parent, (struct iso_tree_node*) iso);
	ret->type = ECMA119_FILE;
	
	file = iso->catalog->file;
	file->ino = ++t->ino;
	
	ret->attrib.st_nlink = file->nlink;
	ret->attrib.st_ino = file->ino;
	ret->info.file = file;
	return ret;
}

static struct ecma119_tree_node*
create_tree(struct ecma119_write_target *t,
	    struct ecma119_tree_node *parent,
	    struct iso_tree_node *iso)
{
	struct ecma119_tree_node *ret = NULL;

	assert(t && iso);
	
	if ( iso->hide_flags & LIBISO_HIDE_ON_RR ) 
		return NULL;
	
	switch ( iso->type ) {
		case LIBISO_NODE_FILE:
			ret = create_file(t, parent, (struct iso_tree_node_file*)iso);
			break;
		case LIBISO_NODE_SYMLINK:
			if ( !t->rockridge ) 
				printf("Can't add symlinks to a non ISO tree. Skipping %s \n",
				      iso->name);
			else 
				ret = create_symlink(t, parent, (struct iso_tree_node_symlink*)iso);
			break;
		case LIBISO_NODE_DIR:
			{
			size_t i;
			struct iso_tree_node_dir *dir = (struct iso_tree_node_dir*)iso;
			ret = create_dir(t, parent, dir);
			for (i = 0; i < dir->nchildren; i++) {
				struct ecma119_tree_node *child;
				child = create_tree(t, ret, dir->children[i]);
				if (child) 
					ret->info.dir.children[ret->info.dir.nchildren++] = child;
			}
			}
			break;
		case LIBISO_NODE_BOOTCATALOG:
			ret = create_boot_catalog(t, parent, 
			                          (struct iso_tree_node_boot_catalog*)iso);
			break;
		default:
			/* should never happen */
			assert( 0 );
			break;
	}
	return ret;
}

void
ecma119_tree_free(struct ecma119_tree_node *root)
{
	size_t i;

	if (root->type == ECMA119_DIR) {
		for (i=0; i < root->info.dir.nchildren; i++) {
			ecma119_tree_free(root->info.dir.children[i]);
		}
		free(root->info.dir.children);
	}
	free(root->iso_name);
	free(root->full_name);
	free(root);
}

static size_t
max_child_name_len(struct ecma119_tree_node *root)
{
	size_t ret = 0, i;

	assert(root->type == ECMA119_DIR);
	for (i=0; i < root->info.dir.nchildren; i++) {
		size_t len = strlen(root->info.dir.children[i]->iso_name);
		ret = MAX(ret, len);
	}
	return ret;
}

static void
reparent(struct ecma119_tree_node *child,
	 struct ecma119_tree_node *parent)
{
	int found = 0;
	size_t i;
	struct ecma119_tree_node *placeholder;

	assert(child && parent && parent->type == ECMA119_DIR && child->parent);

	/* replace the child in the original parent with a placeholder */
	for (i=0; i < child->parent->info.dir.nchildren; i++) {
		if (child->parent->info.dir.children[i] == child) {
			placeholder = create_placeholder(child->target,
						child->parent, child);
			child->parent->info.dir.children[i] = placeholder;
			found = 1;
			break;
		}
	}
	assert(found);

	/* add the child to its new parent */
	child->parent = parent;
	parent->info.dir.nchildren++;
	parent->info.dir.children = realloc( parent->info.dir.children,
				sizeof(void*) * parent->info.dir.nchildren );
	parent->info.dir.children[parent->info.dir.nchildren-1] = child;
}

/**
 * Reorder the tree, if necessary, to ensure that
 *  - the depth is at most 8
 *  - each path length is at most 255 characters
 */
static void
reorder_tree(struct ecma119_write_target *t, 
		 struct ecma119_tree_node *root,
	     struct ecma119_tree_node *cur)
{
	size_t max_path;

	assert(root && cur && cur->type == ECMA119_DIR);

	cur->info.dir.depth = cur->parent ? cur->parent->info.dir.depth + 1 : 1;
	cur->info.dir.path_len = cur->parent ? cur->parent->info.dir.path_len
					+ strlen(cur->iso_name) : 0;
	max_path = cur->info.dir.path_len + cur->info.dir.depth 
	           + max_child_name_len(cur);

	if (cur->info.dir.depth > 8 || max_path > 255) {
		
		if (t->rockridge) {
			reparent(cur, root);
			/* we are appended to the root's children now, so there is no
			 * need to recurse (the root will hit us again) */
		} else {
			/* we need to delete cur */
			size_t i,j;
			struct ecma119_tree_node *parent = cur->parent;
			
			printf("Can't dirs deeper than 8 without RR. Skipping %s\n", 
			      cur->full_name);
			for (i=0; i < parent->info.dir.nchildren; ++i) {
				if (parent->info.dir.children[i] == cur) {
					break;
				}
			}
			assert ( i < parent->info.dir.nchildren);
			for ( j = i; j < parent->info.dir.nchildren - 1; ++j)
				parent->info.dir.children[j] = parent->info.dir.children[j+1];
			parent->info.dir.nchildren--;
			ecma119_tree_free(cur);
		}
	} else {
		size_t i;

		for (i=0; i < cur->info.dir.nchildren; i++) {
			if (cur->info.dir.children[i]->type == ECMA119_DIR)
				reorder_tree(t, root, cur->info.dir.children[i]);
		}
	}
}

static int
cmp_node(const void *f1, const void *f2)
{
	struct ecma119_tree_node *f = *((struct ecma119_tree_node**)f1);
	struct ecma119_tree_node *g = *((struct ecma119_tree_node**)f2);
	return strcmp(f->iso_name, g->iso_name);
}

static void
sort_tree(struct ecma119_tree_node *root)
{
	size_t i;

	assert(root && root->type == ECMA119_DIR);

	qsort(root->info.dir.children, root->info.dir.nchildren, 
	      sizeof(void*), cmp_node);
	for (i=0; i < root->info.dir.nchildren; i++) {
		if (root->info.dir.children[i]->type == ECMA119_DIR)
			sort_tree(root->info.dir.children[i]);
	}
}

/**
 * Change num_change characters of the given filename in order to ensure the
 * name is unique. If the name is short enough (depending on the ISO level),
 * we can append the characters instead of changing them.
 *
 * \p seq_num is the index of this file in the sequence of identical filenames.
 *
 * For example, seq_num=3, num_change=2, name="HELLOTHERE.TXT" changes name to
 * "HELLOTHE03.TXT"
 */
static void
mangle_name(char **name, int num_change, int level, int seq_num)
{
	char *dot = strrchr(*name, '.');
	char *semi = strrchr(*name, ';');
	size_t len = strlen(*name);
	char base[len+1], ext[len+1];
	char fmt[12];
	size_t baselen, extlen;

	if (num_change >= len) {
		return;
	}
	strncpy(base, *name, len+1);
	if (dot) {
		base[dot - *name] = '\0';
		strncpy(ext, dot+1, len+1);
		if (semi) {
			ext[semi - dot - 1] = '\0';
		}
	} else {
		base[len-2] = '\0';
		ext[0] = '\0';
	}
	baselen = strlen(base);
	extlen = strlen(ext);
	if (level == 1 && baselen + num_change > 8) {
		base[8 - num_change] = '\0';
	} else if (level != 1 && baselen + extlen + num_change > 30) {
		base[30 - extlen - num_change] = '\0';
	}

	sprintf(fmt, "%%s%%0%1dd.%%s;1", num_change);
	*name = realloc(*name, baselen + extlen + num_change + 4);
	sprintf(*name, fmt, base, seq_num, ext);
}

static void
mangle_all(struct ecma119_tree_node *dir)
{
	size_t i, j, k;
	struct ecma119_dir_info d = dir->info.dir;
	size_t n_change;
	int changed;

	assert(dir->type == ECMA119_DIR);
	do {
		changed = 0;
		for (i=0; i < d.nchildren; i++) {
			/* find the number of consecutive equal names */
			j = 1;
			while ( i+j < d.nchildren &&
					!strcmp(d.children[i]->iso_name,
						d.children[i+j]->iso_name) )
				j++;
			if (j == 1) continue;

			/* mangle the names */
			changed = 1;
			n_change = j / 10 + 1;
			for (k=0; k < j; k++) {
				mangle_name(&(d.children[i+k]->iso_name),
						n_change,
						dir->target->iso_level,
						k);
				d.children[i+k]->dirent_len =
					calc_dirent_len(d.children[i+k]);
			}

			/* skip ahead by the number of mangled names */
			i += j - 1;
		}
	} while (changed);

	for (i=0; i < d.nchildren; i++) {
		if (d.children[i]->type == ECMA119_DIR)
			mangle_all(d.children[i]);
	}
}

struct ecma119_tree_node*
ecma119_tree_create(struct ecma119_write_target *t,
		    struct iso_tree_node *iso_root)
{
	t->root = create_tree(t, NULL, iso_root);
	if ( !(t->relaxed_constraints & ECMA119_NO_DIR_REALOCATION) )
		reorder_tree(t, t->root, t->root);
	sort_tree(t->root);
	mangle_all(t->root);
	return t->root;
}

void
ecma119_tree_print(struct ecma119_tree_node *root, int spaces)
{
	size_t i;
	char sp[spaces+1];

	memset(sp, ' ', spaces);
	sp[spaces] = '\0';

	printf("%s%s\n", sp, root->iso_name);
	if (root->type == ECMA119_DIR)
		for (i=0; i < root->info.dir.nchildren; i++)
			ecma119_tree_print(root->info.dir.children[i], spaces+2);
}