/**
 * @file
 * @brief Support code for Crawl des files.
**/

#include "AppHdr.h"

#include <iostream>
#include <cstdarg>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>

#include "abyss.h"
#include "artefact.h"
#include "branch.h"
#include "colour.h"
#include "coord.h"
#include "coordit.h"
#include "cluautil.h"
#include "decks.h"
#include "describe.h"
#include "directn.h"
#include "dungeon.h"
#include "dgn-height.h"
#include "end.h"
#include "exclude.h"
#include "files.h"
#include "initfile.h"
#include "invent.h"
#include "l_defs.h"
#include "libutil.h"
#include "mapdef.h"
#include "mapmark.h"
#include "maps.h"
#include "mon-cast.h"
#include "mon-death.h"
#include "mon-place.h"
#include "mon-util.h"
#include "place.h"
#include "random.h"
#include "random-weight.h"
#include "religion.h"
#include "shopping.h"
#include "spl-util.h"
#include "spl-book.h"
#include "strings.h"
#include "env.h"
#include "tags.h"
#include "terrain.h"
#include "tiledef-dngn.h"
#include "tiledef-player.h"

static const char *map_section_names[] =
{
    "",
    "north",
    "south",
    "east",
    "west",
    "northwest",
    "northeast",
    "southwest",
    "southeast",
    "encompass",
    "float",
    "centre",
};

static string_set Map_Flag_Names;

const char *traversable_glyphs =
    ".+=w@{}()[]<>BC^TUVY$%*|Odefghijk0123456789";

// atoi that rejects strings containing non-numeric trailing characters.
// returns defval for invalid input.
template <typename V>
static V strict_aton(const char *s, V defval = 0)
{
    char *end;
    const V res = strtol(s, &end, 10);
    return (!*s || *end) ? defval : res;
}

const char *map_section_name(int msect)
{
    if (msect < 0 || msect >= MAP_NUM_SECTION_TYPES)
        return "";

    return map_section_names[msect];
}

static int find_weight(string &s, int defweight = TAG_UNFOUND)
{
    int weight = strip_number_tag(s, "weight:");
    if (weight == TAG_UNFOUND)
        weight = strip_number_tag(s, "w:");
    return weight == TAG_UNFOUND ? defweight : weight;
}

void clear_subvault_stack()
{
    env.new_subvault_names.clear();
    env.new_subvault_tags.clear();
    env.new_used_subvault_names.clear();
    env.new_used_subvault_tags.clear();
}

void map_register_flag(const string &flag)
{
    Map_Flag_Names.insert(flag);
}

static bool _map_tag_is_selectable(const string &tag)
{
    return !Map_Flag_Names.count(tag)
           && tag.find("luniq_") != 0
           && tag.find("uniq_") != 0
           && tag.find("ruin_") != 0
           && tag.find("chance_") != 0;
}

string mapdef_split_key_item(const string &s, string *key, int *separator,
                             string *arg, int key_max_len)
{
    string::size_type
        norm = s.find("=", 1),
        fixe = s.find(":", 1);

    const string::size_type sep = norm < fixe? norm : fixe;
    if (sep == string::npos)
    {
        return make_stringf("malformed declaration - must use = or : in '%s'",
                            s.c_str());
    }

    *key = trimmed_string(s.substr(0, sep));
    string substitute = trimmed_string(s.substr(sep + 1));

    if (key->empty()
        || (key_max_len != -1 && (int) key->length() > key_max_len))
    {
        return make_stringf(
            "selector '%s' must be <= %d characters in '%s'",
            key->c_str(), key_max_len, s.c_str());
    }

    if (substitute.empty())
    {
        return make_stringf("no substitute defined in '%s'",
                            s.c_str());
    }

    *arg = substitute;
    *separator = s[sep];

    return "";
}

int store_tilename_get_index(const string tilename)
{
    if (tilename.empty())
        return 0;

    // Increase index by 1 to distinguish between first entry and none.
    unsigned int i;
    for (i = 0; i < env.tile_names.size(); ++i)
        if (!strcmp(tilename.c_str(), env.tile_names[i].c_str()))
            return i+1;

#ifdef DEBUG_TILE_NAMES
    mprf("adding %s on index %d (%d)", tilename.c_str(), i, i+1);
#endif
    // If not found, add tile name to vector.
    env.tile_names.push_back(tilename);
    return i+1;
}

///////////////////////////////////////////////
// subvault_place
//

subvault_place::subvault_place()
    : tl(), br(), subvault()
{
}

subvault_place::subvault_place(const coord_def &_tl,
                               const coord_def &_br,
                               const map_def &_subvault)
    : tl(_tl), br(_br), subvault(new map_def(_subvault))
{
}

subvault_place::subvault_place(const subvault_place &place)
    : tl(place.tl), br(place.br),
      subvault(place.subvault.get() ? new map_def(*place.subvault) : NULL)
{
}

subvault_place &subvault_place::operator = (const subvault_place &place)
{
    tl = place.tl;
    br = place.br;
    subvault.reset(place.subvault.get() ? new map_def(*place.subvault) : NULL);
    return *this;
}

void subvault_place::set_subvault(const map_def &_subvault)
{
    subvault.reset(new map_def(_subvault));
}

///////////////////////////////////////////////
// level_range
//

level_range::level_range(branch_type br, int s, int d)
    : branch(br), shallowest(), deepest(), deny(false)
{
    set(s, d);
}

level_range::level_range(const raw_range &r)
    : branch(r.branch), shallowest(r.shallowest), deepest(r.deepest),
      deny(r.deny)
{
}

void level_range::write(writer& outf) const
{
    marshallShort(outf, branch);
    marshallShort(outf, shallowest);
    marshallShort(outf, deepest);
    marshallBoolean(outf, deny);
}

void level_range::read(reader& inf)
{
    branch     = static_cast<branch_type>(unmarshallShort(inf));
    shallowest = unmarshallShort(inf);
    deepest    = unmarshallShort(inf);
    deny       = unmarshallBoolean(inf);
}

string level_range::str_depth_range() const
{
    if (shallowest == -1)
        return ":??";

    if (shallowest == BRANCH_END)
        return ":$";

    if (deepest == BRANCH_END)
        return shallowest == 1? "" : make_stringf("%d-", shallowest);

    if (shallowest == deepest)
        return make_stringf(":%d", shallowest);

    return make_stringf(":%d-%d", shallowest, deepest);
}

string level_range::describe() const
{
    return make_stringf("%s%s%s",
                        deny? "!" : "",
                        branch == NUM_BRANCHES ? "Any" :
                        branches[branch].abbrevname,
                        str_depth_range().c_str());
}

level_range::operator raw_range () const
{
    raw_range r;
    r.branch     = branch;
    r.shallowest = shallowest;
    r.deepest    = deepest;
    r.deny       = deny;
    return r;
}

void level_range::set(const string &br, int s, int d) throw (string)
{
    if (br == "any" || br == "Any")
        branch = NUM_BRANCHES;
    else if ((branch = str_to_branch(br)) == NUM_BRANCHES)
        throw make_stringf("Unknown branch: '%s'", br.c_str());

    shallowest = s;
    deepest    = d;

    if (deepest < shallowest || deepest <= 0)
    {
        throw make_stringf("Level-range %s:%d-%d is malformed",
                           br.c_str(), s, d);
    }
}

level_range level_range::parse(string s) throw (string)
{
    level_range lr;
    trim_string(s);

    if (s == "*")
    {
        lr.set("any", 0, BRANCH_END);
        return lr;
    }

    if (s[0] == '!')
    {
        lr.deny = true;
        s = trimmed_string(s.substr(1));
    }

    string::size_type cpos = s.find(':');
    if (cpos == string::npos)
        parse_partial(lr, s);
    else
    {
        string br    = trimmed_string(s.substr(0, cpos));
        string depth = trimmed_string(s.substr(cpos + 1));
        parse_depth_range(depth, &lr.shallowest, &lr.deepest);

        lr.set(br, lr.shallowest, lr.deepest);
    }

    return lr;
}

void level_range::parse_partial(level_range &lr, const string &s) throw (string)
{
    if (isadigit(s[0]))
    {
        lr.branch = NUM_BRANCHES;
        parse_depth_range(s, &lr.shallowest, &lr.deepest);
    }
    else
        lr.set(s, 1, BRANCH_END);
}

void level_range::parse_depth_range(const string &s, int *l, int *h)
    throw (string)
{
    if (s == "*")
    {
        *l = 1;
        *h = BRANCH_END;
        return;
    }

    if (s == "$")
    {
        *l = BRANCH_END;
        *h = BRANCH_END;
        return;
    }

    string::size_type hy = s.find('-');
    if (hy == string::npos)
    {
        *l = *h = strict_aton<int>(s.c_str());
        if (!*l)
            throw string("Bad depth: ") + s;
    }
    else
    {
        *l = strict_aton<int>(s.substr(0, hy).c_str());

        string tail = s.substr(hy + 1);
        if (tail.empty() || tail == "$")
            *h = BRANCH_END;
        else
            *h = strict_aton<int>(tail.c_str());

        if (!*l || !*h || *l > *h)
            throw string("Bad depth: ") + s;
    }
}

void level_range::set(int s, int d)
{
    shallowest = s;
    deepest    = d;

    if (deepest == -1)
        deepest = shallowest;

    if (deepest < shallowest)
        throw make_stringf("Bad depth range: %d-%d", shallowest, deepest);
}

void level_range::reset()
{
    deepest = shallowest = -1;
    branch  = NUM_BRANCHES;
}

bool level_range::matches(const level_id &lid) const
{
    if (branch == NUM_BRANCHES)
        return matches(absdungeon_depth(lid.branch, lid.depth));
    else
    {
        return branch == lid.branch
               && (lid.depth >= shallowest
                   || shallowest == BRANCH_END && lid.depth == brdepth[branch])
               && lid.depth <= deepest;
    }
}

bool level_range::matches(int x) const
{
    // [ds] The level ranges used by the game are zero-based, adjust for that.
    ++x;
    return x >= shallowest && x <= deepest;
}

bool level_range::operator == (const level_range &lr) const
{
    return deny == lr.deny
           && shallowest == lr.shallowest
           && deepest == lr.deepest
           && branch == lr.branch;
}

bool level_range::valid() const
{
    return shallowest > 0 && deepest >= shallowest;
}

////////////////////////////////////////////////////////////////////////
// map_lines

map_lines::map_lines()
    : markers(), lines(), overlay(),
      map_width(0), solid_north(false), solid_east(false),
      solid_south(false), solid_west(false), solid_checked(false)
{
}

map_lines::map_lines(const map_lines &map)
{
    init_from(map);
}

void map_lines::write_maplines(writer &outf) const
{
    const int h = height();
    marshallShort(outf, h);
    for (int i = 0; i < h; ++i)
        marshallString(outf, lines[i]);
}

void map_lines::read_maplines(reader &inf)
{
    clear();
    const int h = unmarshallShort(inf);
    ASSERT_RANGE(h, 0, GYM + 1);

    for (int i = 0; i < h; ++i)
        add_line(unmarshallString(inf));
}

rectangle_iterator map_lines::get_iter() const
{
    ASSERT(width() > 0);
    ASSERT(height() > 0);

    coord_def tl(0, 0);
    coord_def br(width() - 1, height() - 1);
    return rectangle_iterator(tl, br);
}

char map_lines::operator () (const coord_def &c) const
{
    return lines[c.y][c.x];
}

char& map_lines::operator () (const coord_def &c)
{
    return lines[c.y][c.x];
}

char map_lines::operator () (int x, int y) const
{
    return lines[y][x];
}

char& map_lines::operator () (int x, int y)
{
    return lines[y][x];
}

bool map_lines::in_bounds(const coord_def &c) const
{
    return c.x >= 0 && c.y >= 0 && c.x < width() && c.y < height();
}

bool map_lines::in_map(const coord_def &c) const
{
    return in_bounds(c) && lines[c.y][c.x] != ' ';
}

map_lines &map_lines::operator = (const map_lines &map)
{
    if (this != &map)
        init_from(map);
    return *this;
}

map_lines::~map_lines()
{
    clear_markers();
}

void map_lines::init_from(const map_lines &map)
{
    // Markers have to be regenerated, they will not be copied.
    clear_markers();
    overlay.reset(NULL);
    lines            = map.lines;
    map_width        = map.map_width;
    solid_north      = map.solid_north;
    solid_east       = map.solid_east;
    solid_south      = map.solid_south;
    solid_west       = map.solid_west;
    solid_checked    = map.solid_checked;
}

template <typename V>
void map_lines::clear_vector(V &vect)
{
    for (int i = 0, vsize = vect.size(); i < vsize; ++i)
        delete vect[i];
    vect.clear();
}

void map_lines::clear_markers()
{
    clear_vector(markers);
}

void map_lines::add_marker(map_marker *marker)
{
    markers.push_back(marker);
}

string map_lines::add_feature_marker(const string &s)
{
    string key, arg;
    int sep = 0;
    string err = mapdef_split_key_item(s, &key, &sep, &arg, -1);
    if (!err.empty())
        return err;

    map_marker_spec spec(key, arg);
    spec.apply_transform(*this);

    return "";
}

string map_lines::add_lua_marker(const string &key, const lua_datum &function)
{
    map_marker_spec spec(key, function);
    spec.apply_transform(*this);
    return "";
}

void map_lines::apply_markers(const coord_def &c)
{
    for (int i = 0, vsize = markers.size(); i < vsize; ++i)
    {
        markers[i]->pos += c;
        env.markers.add(markers[i]);
    }
    // *not* clear_markers() since we've offloaded marker ownership to
    // the crawl env.
    markers.clear();
}

void map_lines::apply_grid_overlay(const coord_def &c, bool is_layout)
{
    if (!overlay.get())
        return;

    for (int y = height() - 1; y >= 0; --y)
        for (int x = width() - 1; x >= 0; --x)
        {
            coord_def gc(c.x + x, c.y + y);
            if (is_layout && map_masked(gc, MMT_VAULT))
                continue;

            const int colour = (*overlay)(x, y).colour;
            if (colour)
                dgn_set_grid_colour_at(gc, colour);

            const int property = (*overlay)(x, y).property;
            if (property >= FPROP_BLOODY)
            {
                 // Over-ride whatever property is already there.
                env.pgrid(gc) |= property;
            }

            const int fheight = (*overlay)(x, y).height;
            if (fheight != INVALID_HEIGHT)
            {
                if (!env.heightmap.get())
                    dgn_initialise_heightmap();
                dgn_height_at(gc) = fheight;
            }

            bool has_floor = false, has_rock = false;
            string name = (*overlay)(x, y).floortile;
            if (!name.empty() && name != "none")
            {
                env.tile_flv(gc).floor_idx =
                    store_tilename_get_index(name);

                tileidx_t floor;
                tile_dngn_index(name.c_str(), &floor);
                if (colour)
                    floor = tile_dngn_coloured(floor, colour);
                int offset = random2(tile_dngn_count(floor));
                env.tile_flv(gc).floor = floor + offset;
                has_floor = true;
            }

            name = (*overlay)(x, y).rocktile;
            if (!name.empty() && name != "none")
            {
                env.tile_flv(gc).wall_idx =
                    store_tilename_get_index(name);

                tileidx_t rock;
                tile_dngn_index(name.c_str(), &rock);
                if (colour)
                    rock = tile_dngn_coloured(rock, colour);
                int offset = random2(tile_dngn_count(rock));
                env.tile_flv(gc).wall = rock + offset;
                has_rock = true;
            }

            name = (*overlay)(x, y).tile;
            if (!name.empty() && name != "none")
            {
                env.tile_flv(gc).feat_idx =
                    store_tilename_get_index(name);

                tileidx_t feat;
                tile_dngn_index(name.c_str(), &feat);

                if (colour)
                    feat = tile_dngn_coloured(feat, colour);

                int offset = 0;
                if ((*overlay)(x, y).last_tile)
                    offset = tile_dngn_count(feat) - 1;
                else
                    offset = random2(tile_dngn_count(feat));

                if (!has_floor && grd(gc) == DNGN_FLOOR)
                    env.tile_flv(gc).floor = feat + offset;
                else if (!has_rock && grd(gc) == DNGN_ROCK_WALL)
                    env.tile_flv(gc).wall = feat + offset;
                else
                {
                    if ((*overlay)(x, y).no_random)
                        offset = 0;
                    env.tile_flv(gc).feat = feat + offset;
                }
            }
        }
}

void map_lines::apply_overlays(const coord_def &c, bool is_layout)
{
    apply_markers(c);
    apply_grid_overlay(c, is_layout);
}

const vector<string> &map_lines::get_lines() const
{
    return lines;
}

vector<string> &map_lines::get_lines()
{
    return lines;
}

void map_lines::add_line(const string &s)
{
    lines.push_back(s);
    if (static_cast<int>(s.length()) > map_width)
        map_width = s.length();
}

string map_lines::clean_shuffle(string s)
{
    return replace_all_of(s, " \t", "");
}

string map_lines::check_block_shuffle(const string &s)
{
    const vector<string> segs = split_string("/", s);
    const unsigned seglen = segs[0].length();

    for (int i = 1, vsize = segs.size(); i < vsize; ++i)
    {
        if (seglen != segs[i].length())
            return "block shuffle segment length mismatch";
    }

    return "";
}

string map_lines::check_shuffle(string &s)
{
    if (s.find(',') != string::npos)
        return "use / for block shuffle, or multiple SHUFFLE: lines";

    s = clean_shuffle(s);

    if (s.find('/') != string::npos)
        return check_block_shuffle(s);

    return "";
}

string map_lines::check_clear(string &s)
{
    s = clean_shuffle(s);

    if (!s.length())
        return "no glyphs specified for clearing";

    return "";
}

string map_lines::parse_glyph_replacements(string s, glyph_replacements_t &gly)
{
    s = replace_all_of(s, "\t", " ");
    vector<string> segs = split_string(" ", s);

    for (int i = 0, vsize = segs.size(); i < vsize; ++i)
    {
        const string &is = segs[i];
        if (is.length() > 2 && is[1] == ':')
        {
            const int glych = is[0];
            int weight;
            if (!parse_int(is.substr(2).c_str(), weight) || weight < 1)
                return "Invalid weight specifier in \"" + s + "\"";
            else
                gly.push_back(glyph_weighted_replacement_t(glych, weight));
        }
        else
        {
            for (int c = 0, cs = is.length(); c < cs; ++c)
                gly.push_back(glyph_weighted_replacement_t(is[c], 10));
        }
    }

    return "";
}

template<class T>
static string _parse_weighted_str(const string &spec, T &list)
{
    vector<string> speclist = split_string("/", spec);
    for (int i = 0, vsize = speclist.size(); i < vsize; ++i)
    {
        string val = speclist[i];
        lowercase(val);

        int weight = find_weight(val);
        if (weight == TAG_UNFOUND)
        {
            weight = 10;
            // :number suffix?
            string::size_type cpos = val.find(':');
            if (cpos != string::npos)
            {
                if (!parse_int(val.substr(cpos + 1).c_str(), weight) || weight <= 0)
                    return "Invalid weight specifier in \"" + spec + "\"";
                val.erase(cpos);
                trim_string(val);
            }
        }

        if (!list.parse(val, weight))
        {
            return make_stringf("bad spec: '%s' in '%s'",
                                val.c_str(), spec.c_str());
        }
    }
    return "";
}

bool map_colour_list::parse(const string &col, int weight)
{
    const int colour = col == "none" ? BLACK : str_to_colour(col, -1);
    if (colour == -1)
        return false;

    push_back(map_weighted_colour(colour, weight));
    return true;
}

string map_lines::add_colour(const string &sub)
{
    string s = trimmed_string(sub);

    if (s.empty())
        return "";

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    map_colour_list colours;
    err = _parse_weighted_str<map_colour_list>(substitute, colours);
    if (!err.empty())
        return err;

    colour_spec spec(key, sep == ':', colours);
    overlay_colours(spec);

    return "";
}

bool map_fprop_list::parse(const string &fp, int weight)
{
    feature_property_type fprop;

    if (fp == "nothing")
        fprop = FPROP_NONE;
    else if (fp.empty())
        return false;
    else if (str_to_fprop(fp) == FPROP_NONE)
        return false;
    else
        fprop = str_to_fprop(fp);

    push_back(map_weighted_fprop(fprop, weight));
    return true;
}

bool map_featheight_list::parse(const string &fp, int weight)
{
    const int thisheight = strict_aton(fp.c_str(), INVALID_HEIGHT);
    if (thisheight == INVALID_HEIGHT)
        return false;
    push_back(map_weighted_fheight(thisheight, weight));
    return true;
}

string map_lines::add_fproperty(const string &sub)
{
    string s = trimmed_string(sub);

    if (s.empty())
        return "";

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    map_fprop_list fprops;
    err = _parse_weighted_str<map_fprop_list>(substitute, fprops);
    if (!err.empty())
        return err;

    fprop_spec spec(key, sep == ':', fprops);
    overlay_fprops(spec);

    return "";
}

string map_lines::add_fheight(const string &sub)
{
    string s = trimmed_string(sub);
    if (s.empty())
        return "";

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    map_featheight_list fheights;
    err = _parse_weighted_str(substitute, fheights);
    if (!err.empty())
        return err;

    fheight_spec spec(key, sep == ':', fheights);
    overlay_fheights(spec);

    return "";
}

bool map_string_list::parse(const string &fp, int weight)
{
    push_back(map_weighted_string(fp, weight));
    return !fp.empty();
}

string map_lines::add_subst(const string &sub)
{
    string s = trimmed_string(sub);

    if (s.empty())
        return "";

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    glyph_replacements_t repl;
    err = parse_glyph_replacements(substitute, repl);
    if (!err.empty())
        return err;

    subst_spec spec(key, sep == ':', repl);
    subst(spec);

    return "";
}

string map_lines::parse_nsubst_spec(const string &s, subst_spec &spec)
{
    string key, arg;
    int sep;
    string err = mapdef_split_key_item(s, &key, &sep, &arg, -1);
    if (!err.empty())
        return err;
    int count = 0;
    if (key == "*")
        count = -1;
    else
        parse_int(key.c_str(), count);
    if (!count)
        return make_stringf("Illegal spec: %s", s.c_str());

    glyph_replacements_t repl;
    err = parse_glyph_replacements(arg, repl);
    if (!err.empty())
        return err;

    spec = subst_spec(count, sep == ':', repl);
    return "";
}

string map_lines::add_nsubst(const string &s)
{
    vector<subst_spec> substs;

    int sep;
    string key, arg;

    string err = mapdef_split_key_item(s, &key, &sep, &arg, -1);
    if (!err.empty())
        return err;

    vector<string> segs = split_string("/", arg);
    for (int i = 0, vsize = segs.size(); i < vsize; ++i)
    {
        string &ns = segs[i];
        if (ns.find('=') == string::npos && ns.find(':') == string::npos)
        {
            if (i < vsize - 1)
                ns = "1=" + ns;
            else
                ns = "*=" + ns;
        }
        subst_spec spec;
        err = parse_nsubst_spec(ns, spec);
        if (!err.empty())
        {
            return make_stringf("Bad NSUBST spec: %s (%s)",
                                s.c_str(), err.c_str());
        }
        substs.push_back(spec);
    }

    nsubst_spec spec(key, substs);
    nsubst(spec);

    return "";
}

string map_lines::add_shuffle(const string &raws)
{
    string s = raws;
    const string err = check_shuffle(s);

    if (err.empty())
        resolve_shuffle(s);

    return err;
}

string map_lines::add_clear(const string &raws)
{
    string s = raws;
    const string err = check_clear(s);

    if (err.empty())
        clear(s);

    return err;
}

int map_lines::width() const
{
    return map_width;
}

int map_lines::height() const
{
    return lines.size();
}

void map_lines::extend(int min_width, int min_height, char fill)
{
    min_width = max(1, min_width);
    min_height = max(1, min_height);

    bool dirty = false;
    int old_width = width();
    int old_height = height();

    if (static_cast<int>(lines.size()) < min_height)
    {
        dirty = true;
        while (static_cast<int>(lines.size()) < min_height)
            add_line(string(min_width, fill));
    }

    if (width() < min_width)
    {
        dirty = true;
        lines[0] += string(min_width - width(), fill);
        map_width = max(map_width, min_width);
    }

    if (!dirty)
        return;

    normalise(fill);

    // Extend overlay matrix as well.
    if (overlay.get())
    {
        unique_ptr<overlay_matrix> new_overlay(
            new overlay_matrix(width(), height()));

        for (int y = 0; y < old_height; ++y)
            for (int x = 0; x < old_width; ++x)
                (*new_overlay)(x, y) = (*overlay)(x, y);

        overlay = move(new_overlay);
    }
}

coord_def map_lines::size() const
{
    return coord_def(width(), height());
}

int map_lines::glyph(int x, int y) const
{
    return lines[y][x];
}

int map_lines::glyph(const coord_def &c) const
{
    return glyph(c.x, c.y);
}

bool map_lines::is_solid(int gly) const
{
    return gly == 'x' || gly == 'c' || gly == 'b' || gly == 'v' || gly == 't'
           || gly == 'X';
}

void map_lines::check_borders()
{
    if (solid_checked)
        return;

    const int wide = width(), high = height();

    solid_north = solid_south = true;
    for (int x = 0; x < wide && (solid_north || solid_south); ++x)
    {
        if (solid_north && !is_solid(glyph(x, 0)))
            solid_north = false;
        if (solid_south && !is_solid(glyph(x, high - 1)))
            solid_south = false;
    }

    solid_east = solid_west = true;
    for (int y = 0; y < high && (solid_east || solid_west); ++y)
    {
        if (solid_west && !is_solid(glyph(0, y)))
            solid_west = false;
        if (solid_east && !is_solid(glyph(wide - 1, y)))
            solid_east = false;
    }

    solid_checked = true;
}

bool map_lines::solid_borders(map_section_type border)
{
    check_borders();
    switch (border)
    {
    case MAP_NORTH: return solid_north;
    case MAP_SOUTH: return solid_south;
    case MAP_EAST:  return solid_east;
    case MAP_WEST:  return solid_west;
    case MAP_NORTHEAST: return solid_north && solid_east;
    case MAP_NORTHWEST: return solid_north && solid_west;
    case MAP_SOUTHEAST: return solid_south && solid_east;
    case MAP_SOUTHWEST: return solid_south && solid_west;
    default: return false;
    }
}

void map_lines::clear()
{
    clear_markers();
    lines.clear();
    keyspecs.clear();
    overlay.reset(NULL);
    map_width = 0;
    solid_checked = false;

    // First non-legal character.
    next_keyspec_idx = 256;
}

void map_lines::subst(string &s, subst_spec &spec)
{
    string::size_type pos = 0;
    while ((pos = s.find_first_of(spec.key, pos)) != string::npos)
        s[pos++] = spec.value();
}

void map_lines::subst(subst_spec &spec)
{
    ASSERT(!spec.key.empty());
    for (int y = 0, ysize = lines.size(); y < ysize; ++y)
        subst(lines[y], spec);
}

void map_lines::bind_overlay()
{
    if (!overlay.get())
        overlay.reset(new overlay_matrix(width(), height()));
}

void map_lines::overlay_colours(colour_spec &spec)
{
    bind_overlay();
    for (iterator mi(*this, spec.key); mi; ++mi)
        (*overlay)(*mi).colour = spec.get_colour();
}

void map_lines::overlay_fprops(fprop_spec &spec)
{
    bind_overlay();
    for (iterator mi(*this, spec.key); mi; ++mi)
        (*overlay)(*mi).property |= spec.get_property();
}

void map_lines::overlay_fheights(fheight_spec &spec)
{
    bind_overlay();
    for (iterator mi(*this, spec.key); mi; ++mi)
        (*overlay)(*mi).height = spec.get_height();
}

void map_lines::fill_mask_matrix(const string &glyphs,
                                 const coord_def &tl,
                                 const coord_def &br,
                                 Matrix<bool> &flags)
{
    ASSERT(tl.x >= 0);
    ASSERT(tl.y >= 0);
    ASSERT(br.x < width());
    ASSERT(br.y < height());
    ASSERT(tl.x <= br.x);
    ASSERT(tl.y <= br.y);

    for (int y = tl.y; y <= br.y; ++y)
        for (int x = tl.x; x <= br.x; ++x)
        {
            int ox = x - tl.x;
            int oy = y - tl.y;
            flags(ox, oy) = (strchr(glyphs.c_str(), (*this)(x, y)) != NULL);
        }
}

map_corner_t map_lines::merge_subvault(const coord_def &mtl,
                                       const coord_def &mbr,
                                       const Matrix<bool> &mask,
                                       const map_def &vmap)
{
    const map_lines &vlines = vmap.map;

    // If vault is bigger than the mask region (mtl, mbr), then it gets
    // randomly centered.  (vtl, vbr) stores the vault's region.
    coord_def vtl = mtl;
    coord_def vbr = mbr;

    int width_diff = (mbr.x - mtl.x + 1) - vlines.width();
    int height_diff = (mbr.y - mtl.y + 1) - vlines.height();

    // Adjust vault coords with a random offset.
    int ox = random2(width_diff + 1);
    int oy = random2(height_diff + 1);
    vtl.x += ox;
    vtl.y += oy;
    vbr.x -= (width_diff - ox);
    vbr.y -= (height_diff - oy);

    if (!overlay.get())
        overlay.reset(new overlay_matrix(width(), height()));

    // Clear any markers in the vault's grid
    for (size_t i = 0; i < markers.size(); ++i)
    {
        map_marker *mm = markers[i];
        if (mm->pos.x >= vtl.x && mm->pos.x <= vbr.x
            && mm->pos.y >= vtl.y && mm->pos.y <= vbr.y)
        {
            const coord_def maskc = mm->pos - mtl;
            if (!mask(maskc.x, maskc.y))
                continue;

            // Erase this marker.
            markers[i] = markers[markers.size() - 1];
            markers.resize(markers.size() - 1);
            i--;
        }
    }

    // Copy markers and update locations.
    for (size_t i = 0; i < vlines.markers.size(); ++i)
    {
        map_marker *mm = vlines.markers[i];
        coord_def mapc = mm->pos + vtl;
        coord_def maskc = mapc - mtl;

        if (!mask(maskc.x, maskc.y))
            continue;

        map_marker *clone = mm->clone();
        clone->pos = mapc;
        add_marker(clone);
    }

    unsigned mask_tags = 0;

    // TODO: merge the matching of tags to MMTs into a function that is
    // called from both here and dungeon.cc::dgn_register_place.
    if (vmap.has_tag("no_monster_gen"))
        mask_tags |= MMT_NO_MONS;
    if (vmap.has_tag("no_item_gen"))
        mask_tags |= MMT_NO_ITEM;
    if (vmap.has_tag("no_pool_fixup"))
        mask_tags |= MMT_NO_POOL;
    if (vmap.has_tag("no_wall_fixup"))
        mask_tags |= MMT_NO_WALL;
    if (vmap.has_tag("no_trap_gen"))
        mask_tags |= MMT_NO_TRAP;

    // Cache keyspecs we've already pushed into the extended keyspec space.
    // If !ksmap[key], then we haven't seen the 'key' glyph before.
    keyspec_map ksmap(0);

    for (int y = mtl.y; y <= mbr.y; ++y)
        for (int x = mtl.x; x <= mbr.x; ++x)
        {
            int mx = x - mtl.x;
            int my = y - mtl.y;
            if (!mask(mx, my))
                continue;

            // Outside subvault?
            if (x < vtl.x || x > vbr.x || y < vtl.y || y > vbr.y)
                continue;

            int vx = x - vtl.x;
            int vy = y - vtl.y;
            coord_def vc(vx, vy);

            char c = vlines(vc);
            if (c == ' ')
                continue;

            // Merge keyspecs.
            // Push vault keyspecs into extended keyspecs.
            // Push MONS/ITEM into KMONS/KITEM keyspecs.
            // Generate KFEAT keyspecs for any normal glyphs.
            int idx;
            if (ksmap[c])
            {
                // Already generated this keyed_pmapspec.
                idx = ksmap[c];
            }
            else
            {
                idx = next_keyspec_idx++;
                ASSERT(idx > 0);

                if (c != SUBVAULT_GLYPH)
                    ksmap[c] = idx;

                const keyed_mapspec *kspec = vlines.mapspec_at(vc);

                // If c is a SUBVAULT_GLYPH, it came from a sub-subvault.
                // Sub-subvaults should always have mapspecs at this point.
                ASSERT(c != SUBVAULT_GLYPH || kspec);

                if (kspec)
                {
                    // Copy vault keyspec into the extended keyspecs.
                    keyspecs[idx] = *kspec;
                    keyspecs[idx].key_glyph = SUBVAULT_GLYPH;
                }
                else if (map_def::valid_monster_array_glyph(c))
                {
                    // Translate monster array into keyed_mapspec
                    keyed_mapspec &km = keyspecs[idx];
                    km.key_glyph = SUBVAULT_GLYPH;

                    km.feat.feats.clear();
                    feature_spec spec(-1);
                    spec.glyph = '.';
                    km.feat.feats.insert(km.feat.feats.begin(), spec);

                    int slot = map_def::monster_array_glyph_to_slot(c);
                    km.mons.set_from_slot(vmap.mons, slot);
                }
                else if (map_def::valid_item_array_glyph(c))
                {
                    // Translate item array into keyed_mapspec
                    keyed_mapspec &km = keyspecs[idx];
                    km.key_glyph = SUBVAULT_GLYPH;

                    km.feat.feats.clear();
                    feature_spec spec(-1);
                    spec.glyph = '.';
                    km.feat.feats.insert(km.feat.feats.begin(), spec);

                    int slot = map_def::item_array_glyph_to_slot(c);
                    km.item.set_from_slot(vmap.items, slot);
                }
                else
                {
                    // Normal glyph.  Turn into a feature keyspec.
                    // This is valid for non-array items and monsters
                    // as well, e.g. '$' and '8'.
                    keyed_mapspec &km = keyspecs[idx];
                    km.key_glyph = SUBVAULT_GLYPH;
                    km.feat.feats.clear();

                    feature_spec spec(-1);
                    spec.glyph = c;
                    km.feat.feats.insert(km.feat.feats.begin(), spec);
                }

                // Add overall tags to the keyspec.
                keyspecs[idx].map_mask.flags_set
                    |= (mask_tags & ~keyspecs[idx].map_mask.flags_unset);
            }

            // Finally, handle merging the cell itself.

            // Glyph becomes SUBVAULT_GLYPH.  (The old glyph gets merged into a
            // keyspec, above).  This is so that the glyphs that are included
            // from a subvault are immutable by the parent vault.  Otherwise,
            // latent transformations (like KMONS or KITEM) from the parent
            // vault might confusingly modify a glyph from the subvault.
            //
            // NOTE: It'd be possible to allow subvaults to be modified by the
            // parent vault, but KMONS/KITEM/KFEAT/MONS/ITEM would have to
            // apply immediately instead of latently.  They would also then
            // need to be stored per-coord, rather than per-glyph.
            (*this)(x, y) = SUBVAULT_GLYPH;

            // Merge overlays
            if (vlines.overlay.get())
                (*overlay)(x, y) = (*vlines.overlay)(vx, vy);
            else
            {
                // Erase any existing overlay, as the vault's doesn't exist.
                (*overlay)(x, y) = overlay_def();
            }

            // Set keyspec index for this subvault.
            (*overlay)(x, y).keyspec_idx = idx;
        }

    return map_corner_t(vtl, vbr);
}

void map_lines::overlay_tiles(tile_spec &spec)
{
    if (!overlay.get())
        overlay.reset(new overlay_matrix(width(), height()));

    for (int y = 0, ysize = lines.size(); y < ysize; ++y)
    {
        string::size_type pos = 0;
        while ((pos = lines[y].find_first_of(spec.key, pos)) != string::npos)
        {
            if (spec.floor)
                (*overlay)(pos, y).floortile = spec.get_tile();
            else if (spec.feat)
                (*overlay)(pos, y).tile      = spec.get_tile();
            else
                (*overlay)(pos, y).rocktile  = spec.get_tile();

            (*overlay)(pos, y).no_random = spec.no_random;
            (*overlay)(pos, y).last_tile = spec.last_tile;
            ++pos;
        }
    }
}

void map_lines::nsubst(nsubst_spec &spec)
{
    vector<coord_def> positions;
    for (int y = 0, ysize = lines.size(); y < ysize; ++y)
    {
        string::size_type pos = 0;
        while ((pos = lines[y].find_first_of(spec.key, pos)) != string::npos)
            positions.push_back(coord_def(pos++, y));
    }
    shuffle_array(positions);

    int pcount = 0;
    const int psize = positions.size();
    for (int i = 0, vsize = spec.specs.size();
         i < vsize && pcount < psize; ++i)
    {
        const int nsubsts = spec.specs[i].count;
        pcount += apply_nsubst(positions, pcount, nsubsts, spec.specs[i]);
    }
}

int map_lines::apply_nsubst(vector<coord_def> &pos, int start, int nsub,
                            subst_spec &spec)
{
    if (nsub == -1)
        nsub = pos.size();
    const int end = min(start + nsub, (int) pos.size());
    int substituted = 0;
    for (int i = start; i < end; ++i)
    {
        const int val = spec.value();
        const coord_def &c = pos[i];
        lines[c.y][c.x] = val;
        ++substituted;
    }
    return substituted;
}

string map_lines::block_shuffle(const string &s)
{
    vector<string> segs = split_string("/", s);
    shuffle_array(segs);
    return comma_separated_line(segs.begin(), segs.end(), "/", "/");
}

string map_lines::shuffle(string s)
{
    string result;

    if (s.find('/') != string::npos)
        return block_shuffle(s);

    // Inefficient brute-force shuffle.
    while (!s.empty())
    {
        const int c = random2(s.length());
        result += s[c];
        s.erase(c, 1);
    }

    return result;
}

void map_lines::resolve_shuffle(const string &shufflage)
{
    string toshuffle = shufflage;
    string shuffled = shuffle(toshuffle);

    if (toshuffle.empty() || shuffled.empty())
        return;

    for (int i = 0, vsize = lines.size(); i < vsize; ++i)
    {
        string &s = lines[i];

        for (int j = 0, len = s.length(); j < len; ++j)
        {
            const char c = s[j];
            string::size_type pos = toshuffle.find(c);
            if (pos != string::npos)
                s[j] = shuffled[pos];
        }
    }
}

void map_lines::clear(const string &clearchars)
{
    for (int i = 0, vsize = lines.size(); i < vsize; ++i)
    {
        string &s = lines[i];

        for (int j = 0, len = s.length(); j < len; ++j)
        {
            const char c = s[j];
            string::size_type pos = clearchars.find(c);
            if (pos != string::npos)
                s[j] = ' ';
        }
    }
}

void map_lines::normalise(char fillch)
{
    for (int i = 0, vsize = lines.size(); i < vsize; ++i)
    {
        string &s = lines[i];
        if (static_cast<int>(s.length()) < map_width)
            s += string(map_width - s.length(), fillch);
    }
}

// Should never be attempted if the map has a defined orientation, or if one
// of the dimensions is greater than the lesser of GXM,GYM.
void map_lines::rotate(bool clockwise)
{
    vector<string> newlines;

    // normalise() first for convenience.
    normalise();

    const int xs = clockwise? 0 : map_width - 1,
              xe = clockwise? map_width : -1,
              xi = clockwise? 1 : -1;

    const int ys = clockwise? (int) lines.size() - 1 : 0,
              ye = clockwise? -1 : (int) lines.size(),
              yi = clockwise? -1 : 1;

    for (int i = xs; i != xe; i += xi)
    {
        string line;

        for (int j = ys; j != ye; j += yi)
            line += lines[j][i];

        newlines.push_back(line);
    }

    if (overlay.get())
    {
        unique_ptr<overlay_matrix> new_overlay(
            new overlay_matrix(lines.size(), map_width));
        for (int i = xs, y = 0; i != xe; i += xi, ++y)
            for (int j = ys, x = 0; j != ye; j += yi, ++x)
                (*new_overlay)(x, y) = (*overlay)(i, j);
        overlay = move(new_overlay);
    }

    map_width = lines.size();
    lines     = newlines;
    rotate_markers(clockwise);
    solid_checked = false;
}

void map_lines::translate_marker(
    void (map_lines::*xform)(map_marker *, int),
    int par)
{
    for (int i = 0, vsize = markers.size(); i < vsize; ++i)
        (this->*xform)(markers[i], par);
}

void map_lines::vmirror_marker(map_marker *marker, int)
{
    marker->pos.y = height() - 1 - marker->pos.y;
}

void map_lines::hmirror_marker(map_marker *marker, int)
{
    marker->pos.x = width() - 1 - marker->pos.x;
}

void map_lines::rotate_marker(map_marker *marker, int clockwise)
{
    const coord_def c = marker->pos;
    if (clockwise)
        marker->pos = coord_def(width() - 1 - c.y, c.x);
    else
        marker->pos = coord_def(c.y, height() - 1 - c.x);
}

void map_lines::vmirror_markers()
{
    translate_marker(&map_lines::vmirror_marker);
}

void map_lines::hmirror_markers()
{
    translate_marker(&map_lines::hmirror_marker);
}

void map_lines::rotate_markers(bool clock)
{
    translate_marker(&map_lines::rotate_marker, clock);
}

void map_lines::vmirror()
{
    const int vsize = lines.size();
    const int midpoint = vsize / 2;

    for (int i = 0; i < midpoint; ++i)
    {
        string temp = lines[i];
        lines[i] = lines[vsize - 1 - i];
        lines[vsize - 1 - i] = temp;
    }

    if (overlay.get())
    {
        for (int i = 0; i < midpoint; ++i)
            for (int j = 0, wide = width(); j < wide; ++j)
                swap((*overlay)(j, i), (*overlay)(j, vsize - 1 - i));
    }

    vmirror_markers();
    solid_checked = false;
}

void map_lines::hmirror()
{
    const int midpoint = map_width / 2;
    for (int i = 0, vsize = lines.size(); i < vsize; ++i)
    {
        string &s = lines[i];
        for (int j = 0; j < midpoint; ++j)
        {
            int c = s[j];
            s[j] = s[map_width - 1 - j];
            s[map_width - 1 - j] = c;
        }
    }

    if (overlay.get())
    {
        for (int i = 0, vsize = lines.size(); i < vsize; ++i)
            for (int j = 0; j < midpoint; ++j)
                swap((*overlay)(j, i), (*overlay)(map_width - 1 - j, i));
    }

    hmirror_markers();
    solid_checked = false;
}

keyed_mapspec *map_lines::mapspec_for_key(int key)
{
    keyed_specs::iterator i = keyspecs.find(key);
    return i != keyspecs.end()? &i->second : NULL;
}

const keyed_mapspec *map_lines::mapspec_for_key(int key) const
{
    keyed_specs::const_iterator i = keyspecs.find(key);
    return i != keyspecs.end()? &i->second : NULL;
}

keyed_mapspec *map_lines::mapspec_at(const coord_def &c)
{
    int key = (*this)(c);

    if (key == SUBVAULT_GLYPH)
    {
        // Any subvault should create the overlay.
        ASSERT(overlay.get());
        if (!overlay.get())
            return NULL;

        key = (*overlay)(c.x, c.y).keyspec_idx;
        ASSERT(key);
        if (!key)
            return NULL;
    }

    return mapspec_for_key(key);
}

const keyed_mapspec *map_lines::mapspec_at(const coord_def &c) const
{
    int key = (*this)(c);

    if (key == SUBVAULT_GLYPH)
    {
        // Any subvault should create the overlay and set the keyspec idx.
        ASSERT(overlay.get());
        if (!overlay.get())
            return NULL;

        key = (*overlay)(c.x, c.y).keyspec_idx;
        ASSERT(key);
        if (!key)
            return NULL;
    }

    return mapspec_for_key(key);
}

string map_lines::add_key_field(
    const string &s,
    string (keyed_mapspec::*set_field)(const string &s, bool fixed),
    void (keyed_mapspec::*copy_field)(const keyed_mapspec &spec))
{
    int separator = 0;
    string key, arg;

    string err = mapdef_split_key_item(s, &key, &separator, &arg, -1);
    if (!err.empty())
        return err;

    keyed_mapspec &kmbase = keyspecs[key[0]];
    kmbase.key_glyph = key[0];
    err = ((kmbase.*set_field)(arg, separator == ':'));
    if (!err.empty())
        return err;

    size_t len = key.length();
    for (size_t i = 1; i < len; i++)
    {
        keyed_mapspec &km = keyspecs[key[i]];
        km.key_glyph = key[i];
        ((km.*copy_field)(kmbase));
    }

    return err;
}

string map_lines::add_key_item(const string &s)
{
    return add_key_field(s, &keyed_mapspec::set_item,
                         &keyed_mapspec::copy_item);
}

string map_lines::add_key_feat(const string &s)
{
    return add_key_field(s, &keyed_mapspec::set_feat,
                         &keyed_mapspec::copy_feat);
}

string map_lines::add_key_mons(const string &s)
{
    return add_key_field(s, &keyed_mapspec::set_mons,
                         &keyed_mapspec::copy_mons);
}

string map_lines::add_key_mask(const string &s)
{
    return add_key_field(s, &keyed_mapspec::set_mask,
                         &keyed_mapspec::copy_mask);
}

vector<coord_def> map_lines::find_glyph(int gly) const
{
    vector<coord_def> points;
    for (int y = height() - 1; y >= 0; --y)
    {
        for (int x = width() - 1; x >= 0; --x)
        {
            const coord_def c(x, y);
            if ((*this)(c) == gly)
                points.push_back(c);
        }
    }
    return points;
}

vector<coord_def> map_lines::find_glyph(const string &glyphs) const
{
    vector<coord_def> points;
    for (int y = height() - 1; y >= 0; --y)
    {
        for (int x = width() - 1; x >= 0; --x)
        {
            const coord_def c(x, y);
            if (glyphs.find((*this)(c)) != string::npos)
                points.push_back(c);
        }
    }
    return points;
}

coord_def map_lines::find_first_glyph(int gly) const
{
    for (int y = 0, h = height(); y < h; ++y)
    {
        string::size_type pos = lines[y].find(gly);
        if (pos != string::npos)
            return coord_def(pos, y);
    }

    return coord_def(-1, -1);
}

coord_def map_lines::find_first_glyph(const string &glyphs) const
{
    for (int y = 0, h = height(); y < h; ++y)
    {
        string::size_type pos = lines[y].find_first_of(glyphs);
        if (pos != string::npos)
            return coord_def(pos, y);
    }
    return coord_def(-1, -1);
}

bool map_lines::find_bounds(int gly, coord_def &tl, coord_def &br) const
{
    tl = coord_def(width(), height());
    br = coord_def(-1, -1);

    if (width() == 0 || height() == 0)
        return false;

    for (rectangle_iterator ri(get_iter()); ri; ++ri)
    {
        const coord_def mc = *ri;
        if ((*this)(mc) != gly)
            continue;

        tl.x = min(tl.x, mc.x);
        tl.y = min(tl.y, mc.y);
        br.x = max(br.x, mc.x);
        br.y = max(br.y, mc.y);
    }

    return br.x >= 0;
}

bool map_lines::find_bounds(const char *str, coord_def &tl, coord_def &br) const
{
    tl = coord_def(width(), height());
    br = coord_def(-1, -1);

    if (width() == 0 || height() == 0)
        return false;

    for (rectangle_iterator ri(get_iter()); ri; ++ri)
    {
        ASSERT(ri);
        const coord_def &mc = *ri;
        const size_t len = strlen(str);
        for (size_t i = 0; i < len; ++i)
        {
            if ((*this)(mc) == str[i])
            {
                tl.x = min(tl.x, mc.x);
                tl.y = min(tl.y, mc.y);
                br.x = max(br.x, mc.x);
                br.y = max(br.y, mc.y);
                break;
            }
        }
    }

    return br.x >= 0;
}

bool map_lines::fill_zone(travel_distance_grid_t &tpd, const coord_def &start,
                          const coord_def &tl, const coord_def &br, int zone,
                          const char *wanted, const char *passable) const
{
    // This is the map_lines equivalent of _dgn_fill_zone.
    // It's unfortunately extremely similar, but not close enough to combine.

    bool ret = false;
    list<coord_def> points[2];
    int cur = 0;

    for (points[cur].push_back(start); !points[cur].empty();)
    {
        for (list<coord_def>::const_iterator i = points[cur].begin();
             i != points[cur].end(); ++i)
        {
            const coord_def &c(*i);

            tpd[c.x][c.y] = zone;

            ret |= (wanted && strchr(wanted, (*this)(c)) != NULL);

            for (int yi = -1; yi <= 1; ++yi)
                for (int xi = -1; xi <= 1; ++xi)
                {
                    if (!xi && !yi)
                        continue;

                    const coord_def cp(c.x + xi, c.y + yi);
                    if (cp.x < tl.x || cp.x > br.x
                        || cp.y < tl.y || cp.y > br.y
                        || !in_bounds(cp) || tpd[cp.x][cp.y]
                        || passable && !strchr(passable, (*this)(cp)))
                    {
                        continue;
                    }

                    tpd[cp.x][cp.y] = zone;
                    points[!cur].push_back(cp);
                }
        }

        points[cur].clear();
        cur = !cur;
    }
    return ret;
}

int map_lines::count_feature_in_box(const coord_def &tl, const coord_def &br,
                                    const char *feat) const
{
    int result = 0;
    for (rectangle_iterator ri(tl, br); ri; ++ri)
    {
        if (strchr(feat, (*this)(*ri)))
            result++;
    }

    return result;
}

bool map_tile_list::parse(const string &s, int weight)
{
    tileidx_t idx = 0;
    if (s != "none" && !tile_dngn_index(s.c_str(), &idx))
        return false;

    push_back(map_weighted_tile(s, weight));
    return true;
}

string map_lines::add_tile(const string &sub, bool is_floor, bool is_feat)
{
    string s = trimmed_string(sub);

    if (s.empty())
        return "";

    bool no_random = strip_tag(s, "no_random");
    bool last_tile = strip_tag(s, "last_tile");

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(s, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    map_tile_list list;
    err = _parse_weighted_str<map_tile_list>(substitute, list);
    if (!err.empty())
        return err;

    tile_spec spec(key, sep == ':', no_random, last_tile, is_floor, is_feat, list);
    overlay_tiles(spec);

    return "";
}

string map_lines::add_rocktile(const string &sub)
{
    return add_tile(sub, false, false);
}

string map_lines::add_floortile(const string &sub)
{
    return add_tile(sub, true, false);
}

string map_lines::add_spec_tile(const string &sub)
{
    return add_tile(sub, false, true);
}

//////////////////////////////////////////////////////////////////////////
// tile_spec

string tile_spec::get_tile()
{
    if (chose_fixed)
        return fixed_tile;

    string chosen = "";
    int cweight = 0;
    for (int i = 0, size = tiles.size(); i < size; ++i)
        if (x_chance_in_y(tiles[i].second, cweight += tiles[i].second))
            chosen = tiles[i].first;

    if (fix)
    {
        chose_fixed = true;
        fixed_tile  = chosen;
    }
    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// map_lines::iterator

map_lines::iterator::iterator(map_lines &_maplines, const string &_key)
    : maplines(_maplines), key(_key), p(0, 0)
{
    advance();
}

void map_lines::iterator::advance()
{
    const int height = maplines.height();
    while (p.y < height)
    {
        string::size_type place = p.x;
        if (place < maplines.lines[p.y].length())
        {
            place = maplines.lines[p.y].find_first_of(key, place);
            if (place != string::npos)
            {
                p.x = place;
                break;
            }
        }
        ++p.y;
        p.x = 0;
    }
}

map_lines::iterator::operator bool() const
{
    return p.y < maplines.height();
}

coord_def map_lines::iterator::operator *() const
{
    return p;
}

coord_def map_lines::iterator::operator ++ ()
{
    p.x++;
    advance();
    return **this;
}

coord_def map_lines::iterator::operator ++ (int)
{
    coord_def here(**this);
    ++*this;
    return here;
}

///////////////////////////////////////////////
// dlua_set_map

dlua_set_map::dlua_set_map(map_def *map)
{
    clua_push_map(dlua, map);
    if (!dlua.callfn("dgn_set_map", 1, 1))
    {
        mprf(MSGCH_ERROR, "dgn_set_map failed for '%s': %s",
             map->name.c_str(), dlua.error.c_str());
    }
    // Save the returned map as a lua_datum
    old_map.reset(new lua_datum(dlua));
}

dlua_set_map::~dlua_set_map()
{
    old_map->push();
    if (!dlua.callfn("dgn_set_map", 1, 0))
        mprf(MSGCH_ERROR, "dgn_set_map failed: %s", dlua.error.c_str());
}

///////////////////////////////////////////////
// map_chance

string map_chance::describe() const
{
    return make_stringf("%d:%d", chance_priority, chance);
}

bool map_chance::roll() const
{
    return random2(CHANCE_ROLL) < chance;
}

void map_chance::write(writer &outf) const
{
    marshallInt(outf, chance_priority);
    marshallInt(outf, chance);
}

void map_chance::read(reader &inf)
{
    chance_priority = unmarshallInt(inf);
    chance = unmarshallInt(inf);
}

///////////////////////////////////////////////
// depth_ranges

void depth_ranges::write(writer& outf) const
{
    marshallShort(outf, depths.size());
    for (int i = 0, sz = depths.size(); i < sz; ++i)
        depths[i].write(outf);
}

void depth_ranges::read(reader &inf)
{
    depths.clear();
    const int nranges = unmarshallShort(inf);
    for (int i = 0; i < nranges; ++i)
    {
        level_range lr;
        lr.read(inf);
        depths.push_back(lr);
    }
}

depth_ranges depth_ranges::parse_depth_ranges(const string &depth_range_string)
{
    depth_ranges ranges;
    const vector<string> frags = split_string(",", depth_range_string);
    for (int j = 0, size = frags.size(); j < size; ++j)
        ranges.depths.push_back(level_range::parse(frags[j]));
    return ranges;
}

bool depth_ranges::is_usable_in(const level_id &lid) const
{
    bool any_matched = false;
    for (int i = 0, sz = depths.size(); i < sz; ++i)
    {
        const level_range &lr = depths[i];
        if (lr.matches(lid))
        {
            if (lr.deny)
                return false;
            any_matched = true;
        }
    }
    return any_matched;
}

void depth_ranges::add_depths(const depth_ranges &other_depths)
{
    depths.insert(depths.end(),
                  other_depths.depths.begin(),
                  other_depths.depths.end());
}

string depth_ranges::describe() const
{
    return comma_separated_line(depths.begin(), depths.end(), ", ", ", ");
}

///////////////////////////////////////////////
// map_def
//

const int DEFAULT_MAP_WEIGHT = 10;
map_def::map_def()
    : name(), description(), order(INT_MAX), tags(), place(), depths(),
      orient(), _chance(), _weight(DEFAULT_MAP_WEIGHT),
      map(), mons(), items(), random_mons(),
      prelude("dlprelude"), mapchunk("dlmapchunk"), main("dlmain"),
      validate("dlvalidate"), veto("dlveto"), epilogue("dlepilogue"),
      rock_colour(BLACK), floor_colour(BLACK), rock_tile(""),
      floor_tile(""), border_fill_type(DNGN_ROCK_WALL),
      index_only(false), cache_offset(0L), validating_map_flag(false)
{
    init();
}

void map_def::init()
{
    orient = MAP_NONE;
    name.clear();
    description.clear();
    order = INT_MAX;
    tags.clear();
    place.clear();
    depths.clear();
    prelude.clear();
    mapchunk.clear();
    main.clear();
    validate.clear();
    veto.clear();
    epilogue.clear();
    place_loaded_from.clear();
    reinit();

    // Subvault mask set and cleared externally.
    // It should *not* be in reinit.
    svmask = NULL;
}

void map_def::reinit()
{
    description.clear();
    order = INT_MAX;
    items.clear();
    random_mons.clear();
    level_flags.clear();
    branch_flags.clear();

    rock_colour = floor_colour = BLACK;
    rock_tile = floor_tile = "";
    border_fill_type = DNGN_ROCK_WALL;

    // Chance of using this level. Nonzero chance should be used
    // sparingly. When selecting vaults for a place, first those
    // vaults with chance > 0 are considered, in the order they were
    // loaded (which is arbitrary). If random2(100) < chance, the
    // vault is picked, and all other vaults are ignored for that
    // random selection. weight is ignored if the vault is chosen
    // based on its chance.
    _chance.clear();

    // Weight for this map. When selecting a map, if no map with a
    // nonzero chance is picked, one of the other eligible vaults is
    // picked with a probability of weight / (sum of weights of all
    // eligible vaults).
    _weight.clear(DEFAULT_MAP_WEIGHT);

    // Clearing the map also zaps map transforms.
    map.clear();
    mons.clear();
    feat_renames.clear();
    subvault_places.clear();
}

bool map_def::map_already_used() const
{
    return you.uniq_map_names.count(name)
           || env.level_uniq_maps.find(name) !=
               env.level_uniq_maps.end()
           || env.new_used_subvault_names.find(name) !=
               env.new_used_subvault_names.end()
           || has_any_tag(you.uniq_map_tags.begin(),
                          you.uniq_map_tags.end())
           || has_any_tag(env.level_uniq_map_tags.begin(),
                          env.level_uniq_map_tags.end())
           || has_any_tag(env.new_used_subvault_tags.begin(),
                          env.new_used_subvault_tags.end());
}

bool map_def::valid_item_array_glyph(int gly)
{
    return gly >= 'd' && gly <= 'k';
}

int map_def::item_array_glyph_to_slot(int gly)
{
    ASSERT(map_def::valid_item_array_glyph(gly));
    return gly - 'd';
}

bool map_def::valid_monster_glyph(int gly)
{
    return gly >= '0' && gly <= '9';
}

bool map_def::valid_monster_array_glyph(int gly)
{
    return gly >= '1' && gly <= '7';
}

int map_def::monster_array_glyph_to_slot(int gly)
{
    ASSERT(map_def::valid_monster_array_glyph(gly));
    return gly - '1';
}

bool map_def::in_map(const coord_def &c) const
{
    return map.in_map(c);
}

int map_def::glyph_at(const coord_def &c) const
{
    return map(c);
}

string map_def::name_at(const coord_def &c) const
{
    vector<string> names;
    names.push_back(this->name);
    for (int i = 0, nsubvaults = this->subvault_places.size();
         i < nsubvaults; ++i)
    {
        const subvault_place &subvault = subvault_places[i];
        if (c.x >= subvault.tl.x && c.x <= subvault.br.x &&
            c.y >= subvault.tl.y && c.y <= subvault.br.y &&
            subvault.subvault->in_map(c - subvault.tl))
        {
            names.push_back(subvault.subvault->name_at(c - subvault.tl));
        }
    }
    return comma_separated_line(names.begin(), names.end(), ", ", ", ");
}

string map_def::desc_or_name() const
{
    return description.empty()? name : description;
}

void map_def::write_full(writer& outf) const
{
    cache_offset = outf.tell();
    marshallUByte(outf, TAG_MAJOR_VERSION);
    marshallUByte(outf, TAG_MINOR_VERSION);
    marshallString4(outf, name);
    prelude.write(outf);
    mapchunk.write(outf);
    main.write(outf);
    validate.write(outf);
    veto.write(outf);
    epilogue.write(outf);
}

void map_def::read_full(reader& inf, bool check_cache_version)
{
    // There's a potential race-condition here:
    // - If someone modifies a .des file while there are games in progress,
    // - a new Crawl process will overwrite the .dsc.
    // - older Crawl processes trying to reading the new .dsc will be hosed.
    // We could try to recover from the condition (by locking and
    // reloading the index), but it's easier to save the game at this
    // point and let the player reload.

    const uint8_t major = unmarshallUByte(inf);
    const uint8_t minor = unmarshallUByte(inf);

    if (major != TAG_MAJOR_VERSION || minor > TAG_MINOR_VERSION)
        throw map_load_exception(name);

    string fp_name;
    unmarshallString4(inf, fp_name);

    if (fp_name != name)
        throw map_load_exception(name);

    prelude.read(inf);
    mapchunk.read(inf);
    main.read(inf);
    validate.read(inf);
    veto.read(inf);
    epilogue.read(inf);
}

int map_def::weight(const level_id &lid) const
{
    return _weight.depth_value(lid);
}

map_chance map_def::chance(const level_id &lid) const
{
    return _chance.depth_value(lid);
}

string map_def::describe() const
{
    return make_stringf("Map: %s\n%s%s%s%s%s%s",
                        name.c_str(),
                        prelude.describe("prelude").c_str(),
                        mapchunk.describe("mapchunk").c_str(),
                        main.describe("main").c_str(),
                        validate.describe("validate").c_str(),
                        veto.describe("veto").c_str(),
                        epilogue.describe("epilogue").c_str());
}

void map_def::strip()
{
    if (index_only)
        return;

    index_only = true;
    map.clear();
    mons.clear();
    items.clear();
    random_mons.clear();
    prelude.clear();
    mapchunk.clear();
    main.clear();
    validate.clear();
    veto.clear();
    epilogue.clear();
    feat_renames.clear();
}

void map_def::load()
{
    if (!index_only)
        return;

    const string descache_base = get_descache_path(cache_name, "");
    file_lock deslock(descache_base + ".lk", "rb", false);
    const string loadfile = descache_base + ".dsc";

    reader inf(loadfile, TAG_MINOR_VERSION);
    if (!inf.valid())
        throw map_load_exception(name);
    inf.advance(cache_offset);
    read_full(inf, true);

    index_only = false;
}

vector<coord_def> map_def::find_glyph(int glyph) const
{
    return map.find_glyph(glyph);
}

coord_def map_def::find_first_glyph(int glyph) const
{
    return map.find_first_glyph(glyph);
}

coord_def map_def::find_first_glyph(const string &s) const
{
    return map.find_first_glyph(s);
}

void map_def::write_maplines(writer &outf) const
{
    map.write_maplines(outf);
}

static void _marshall_map_chance(writer &th, const map_chance &chance)
{
    chance.write(th);
}

static map_chance _unmarshall_map_chance(reader &th)
{
    map_chance chance;
    chance.read(th);
    return chance;
}

void map_def::write_index(writer& outf) const
{
    if (!cache_offset)
    {
        end(1, false, "Map %s: can't write index - cache offset not set!",
            name.c_str());
    }
    marshallString4(outf, name);
    marshallString4(outf, place_loaded_from.filename);
    marshallInt(outf, place_loaded_from.lineno);
    marshallShort(outf, orient);
    // XXX: This is a hack. See the comment in l_dgn.cc.
    marshallShort(outf, static_cast<short>(border_fill_type));
    _chance.write(outf, _marshall_map_chance);
    _weight.write(outf, marshallInt);
    marshallInt(outf, cache_offset);
    marshallString4(outf, tags);
    place.write(outf);
    depths.write(outf);
    prelude.write(outf);
}

void map_def::read_maplines(reader &inf)
{
    map.read_maplines(inf);
}

void map_def::read_index(reader& inf)
{
    unmarshallString4(inf, name);
    unmarshallString4(inf, place_loaded_from.filename);
    place_loaded_from.lineno = unmarshallInt(inf);
    orient = static_cast<map_section_type>(unmarshallShort(inf));
    // XXX: Hack. See the comment in l_dgn.cc.
    border_fill_type =
        static_cast<dungeon_feature_type>(unmarshallShort(inf));

    _chance = range_chance_t::read(inf, _unmarshall_map_chance);
    _weight = range_weight_t::read(inf, unmarshallInt);
    cache_offset = unmarshallInt(inf);
    unmarshallString4(inf, tags);
    place.read(inf);
    depths.read(inf);
    prelude.read(inf);
    index_only = true;
}

void map_def::set_file(const string &s)
{
    prelude.set_file(s);
    mapchunk.set_file(s);
    main.set_file(s);
    validate.set_file(s);
    veto.set_file(s);
    epilogue.set_file(s);
    file = get_base_filename(s);
    cache_name = get_cache_name(s);
}

string map_def::run_lua(bool run_main)
{
    dlua_set_map mset(this);

    int err = prelude.load(dlua);
    if (err == E_CHUNK_LOAD_FAILURE)
        lua_pushnil(dlua);
    else if (err)
        return prelude.orig_error();
    if (!dlua.callfn("dgn_run_map", 1, 0))
        return rewrite_chunk_errors(dlua.error);

    if (run_main)
    {
        // Run the map chunk to set up the vault's map grid.
        err = mapchunk.load(dlua);
        if (err == E_CHUNK_LOAD_FAILURE)
            lua_pushnil(dlua);
        else if (err)
            return mapchunk.orig_error();
        if (!dlua.callfn("dgn_run_map", 1, 0))
            return rewrite_chunk_errors(dlua.error);

        // The vault may be non-rectangular with a ragged-right edge; for
        // transforms to work right at this point, we must pad out the right
        // edge with spaces, so run normalise:
        normalise();

        // Run the main Lua chunk to set up the rest of the vault
        run_hook("pre_main");
        err = main.load(dlua);
        if (err == E_CHUNK_LOAD_FAILURE)
            lua_pushnil(dlua);
        else if (err)
            return main.orig_error();
        if (!dlua.callfn("dgn_run_map", 1, 0))
            return rewrite_chunk_errors(dlua.error);
        run_hook("post_main");
    }

    return dlua.error;
}

void map_def::copy_hooks_from(const map_def &other_map, const string &hook_name)
{
    const dlua_set_map mset(this);
    if (!dlua.callfn("dgn_map_copy_hooks_from", "ss",
                     other_map.name.c_str(), hook_name.c_str()))
    {
        mprf(MSGCH_ERROR, "Lua error copying hook (%s) from '%s' to '%s': %s",
             hook_name.c_str(), other_map.name.c_str(),
             name.c_str(), dlua.error.c_str());
    }
}

// Runs Lua hooks registered by the map's Lua code, if any. Returns true if
// no errors occurred while running hooks.
bool map_def::run_hook(const string &hook_name, bool die_on_lua_error)
{
    const dlua_set_map mset(this);
    if (!dlua.callfn("dgn_map_run_hook", "s", hook_name.c_str()))
    {
        if (die_on_lua_error)
        {
            end(1, false, "Lua error running hook '%s' on map '%s': %s",
                hook_name.c_str(), name.c_str(),
                rewrite_chunk_errors(dlua.error).c_str());
        }
        else
            mprf(MSGCH_ERROR, "Lua error running hook '%s' on map '%s': %s",
                 hook_name.c_str(), name.c_str(),
                 rewrite_chunk_errors(dlua.error).c_str());
        return false;
    }
    return true;
}

bool map_def::run_postplace_hook(bool die_on_lua_error)
{
    return run_hook("post_place", die_on_lua_error);
}

bool map_def::test_lua_boolchunk(dlua_chunk &chunk, bool defval,
                                 bool die_on_lua_error)
{
    bool result = defval;
    dlua_set_map mset(this);

    int err = chunk.load(dlua);
    if (err == E_CHUNK_LOAD_FAILURE)
        return result;
    else if (err)
    {
        if (die_on_lua_error)
            end(1, false, "Lua error: %s", chunk.orig_error().c_str());
        else
            mprf(MSGCH_ERROR, "Lua error: %s", chunk.orig_error().c_str());
        return result;
    }
    if (dlua.callfn("dgn_run_map", 1, 1))
        dlua.fnreturns(">b", &result);
    else
    {
        if (die_on_lua_error)
        {
            end(1, false, "Lua error: %s",
                rewrite_chunk_errors(dlua.error).c_str());
        }
        else
        {
            mprf(MSGCH_ERROR, "Lua error: %s",
                 rewrite_chunk_errors(dlua.error).c_str());
        }
    }
    return result;
}

bool map_def::test_lua_validate(bool croak)
{
    return validate.empty() || test_lua_boolchunk(validate, false, croak);
}

bool map_def::test_lua_veto()
{
    return !veto.empty() && test_lua_boolchunk(veto, true);
}

bool map_def::run_lua_epilogue(bool die_on_lua_error)
{
    run_hook("pre_epilogue", die_on_lua_error);
    const bool epilogue_result =
        !epilogue.empty() && test_lua_boolchunk(epilogue, false,
                                                die_on_lua_error);
    run_hook("post_epilogue", die_on_lua_error);
    return epilogue_result;
}

string map_def::rewrite_chunk_errors(const string &s) const
{
    string res = s;
    if (prelude.rewrite_chunk_errors(res))
        return res;
    if (mapchunk.rewrite_chunk_errors(res))
        return res;
    if (main.rewrite_chunk_errors(res))
        return res;
    if (validate.rewrite_chunk_errors(res))
        return res;
    if (veto.rewrite_chunk_errors(res))
        return res;
    epilogue.rewrite_chunk_errors(res);
    return res;
}

string map_def::validate_temple_map()
{
    vector<coord_def> altars = find_glyph('B');

    if (has_tag_prefix("temple_overflow_"))
    {
        vector<string> tag_list = get_tags();
        string         temple_tag;

        for (unsigned int i = 0; i < tag_list.size(); i++)
        {
            if (starts_with(tag_list[i], "temple_overflow_"))
            {
                temple_tag = tag_list[i];
                break;
            }
        }

        if (temple_tag.empty())
            return make_stringf("Unknown temple tag.");

        temple_tag = strip_tag_prefix(temple_tag, "temple_overflow_");

        if (temple_tag.empty())
            return "Malformed temple_overflow_ tag";

        if (starts_with(temple_tag, "generic_"))
        {
            temple_tag = strip_tag_prefix(temple_tag, "generic_");

            int num = 0;
            parse_int(temple_tag.c_str(), num);

            if (((unsigned long) num) != altars.size())
            {
                return make_stringf("Temple should contain %u altars, but "
                                    "has %d.", (unsigned int)altars.size(), num);
            }
        }
        else
        {
            // Assume specialised altar vaults are set up correctly.
            return "";
        }
    }

    if (altars.empty())
        return "Temple vault must contain at least one altar.";

    // TODO: check for substitutions and shuffles

    vector<coord_def> b_glyphs = map.find_glyph('B');
    for (vector<coord_def>::iterator i = b_glyphs.begin();
        i != b_glyphs.end(); ++i)
    {
        const keyed_mapspec *spec = map.mapspec_at(*i);
        if (spec != NULL && !spec->feat.feats.empty())
            return "Can't change feat 'B' in temple (KFEAT)";
    }

    vector<god_type> god_list = temple_god_list();

    if (altars.size() > god_list.size())
        return "Temple vault has too many altars";

    return "";
}

string map_def::validate_map_placeable()
{
    if (has_depth() || !place.empty())
        return "";

    // Ok, the map wants to be placed by tag. In this case it should have
    // at least one tag that's not a map flag.
    const vector<string> tag_pieces = split_string(" ", tags);
    bool has_selectable_tag = false;
    for (int i = 0, tsize = tag_pieces.size(); i < tsize; ++i)
    {
        if (_map_tag_is_selectable(tag_pieces[i]))
        {
            has_selectable_tag = true;
            break;
        }
    }

    return has_selectable_tag? "" :
           make_stringf("Map '%s' has no DEPTH, no PLACE and no "
                        "selectable tag in '%s'",
                        name.c_str(), tags.c_str());
}

/**
 * Check to see if the vault can connect normally to the rest of the dungeon.
 */
bool map_def::has_exit() const
{
    map_def dup = *this;
    for (int y = 0, cheight = map.height(); y < cheight; ++y)
        for (int x = 0, cwidth = map.width(); x < cwidth; ++x)
        {
            if (!map.in_map(coord_def(x, y)))
                continue;
            const char glyph = map.glyph(x, y);
            dungeon_feature_type feat =
                map_feature_at(&dup, coord_def(x, y), -1);
            // If we have a stair, assume the vault can be disconnected.
            if (feat_is_stair(feat) && !feat_is_escape_hatch(feat))
                return true;
            const bool non_floating =
                glyph == '@' || glyph == '=' || glyph == '+';
            if (non_floating
                || !feat_is_solid(feat) || feat_is_closed_door(feat))
            {
                if (x == 0 || x == cwidth - 1 || y == 0 || y == cheight - 1)
                    return true;
                for (orth_adjacent_iterator ai(coord_def(x, y)); ai; ++ai)
                    if (!map.in_map(*ai))
                        return true;
            }
        }

    return false;
}

string map_def::validate_map_def(const depth_ranges &default_depths)
{
    unwind_bool valid_flag(validating_map_flag, true);

    string err = run_lua(true);
    if (!err.empty())
        return err;

    fixup();
    resolve();
    test_lua_validate(true);
    run_lua_epilogue(true);

    if (!has_depth() && !lc_default_depths.empty())
        depths.add_depths(lc_default_depths);

    if (place.is_usable_in(level_id(BRANCH_TEMPLE))
        || has_tag_prefix("temple_overflow_"))
    {
        err = validate_temple_map();
        if (!err.empty())
            return err;
    }

    if (has_tag("overwrite_floor_cell") && (map.width() != 1 || map.height() != 1))
        return "Map tagged 'overwrite_floor_cell' must be 1x1";

    // Abyssal vaults have additional size and orientation restrictions.
    if (has_tag("abyss") || has_tag("abyss_rune"))
    {
        if (orient == MAP_ENCOMPASS)
        {
            return make_stringf(
                "Map '%s' cannot use 'encompass' orientation in the abyss",
                name.c_str());
        }

        const int max_abyss_map_width =
            GXM / 2 - MAPGEN_BORDER - ABYSS_AREA_SHIFT_RADIUS;
        const int max_abyss_map_height =
            GYM / 2 - MAPGEN_BORDER - ABYSS_AREA_SHIFT_RADIUS;

        if (map.width() > max_abyss_map_width
            || map.height() > max_abyss_map_height)
        {
            return make_stringf(
                "Map '%s' is too big for the Abyss: %dx%d - max %dx%d",
                name.c_str(),
                map.width(), map.height(),
                max_abyss_map_width, max_abyss_map_height);
        }

        // Unless both height and width fit in the smaller dimension,
        // map rotation will be disallowed.
        const int dimension_lower_bound =
            min(max_abyss_map_height, max_abyss_map_width);
        if ((map.width() > dimension_lower_bound
             || map.height() > dimension_lower_bound)
            && !has_tag("no_rotate"))
        {
            tags += " no_rotate ";
        }
    }

    if (orient == MAP_FLOAT || is_minivault())
    {
        if (map.width() > GXM - MAPGEN_BORDER * 2
            || map.height() > GYM - MAPGEN_BORDER * 2)
        {
            return make_stringf(
                     "%s '%s' is too big: %dx%d - max %dx%d",
                     is_minivault()? "Minivault" : "Float",
                     name.c_str(),
                     map.width(), map.height(),
                     GXM - MAPGEN_BORDER * 2,
                     GYM - MAPGEN_BORDER * 2);
        }
    }
    else
    {
        if (map.width() > GXM || map.height() > GYM)
        {
            return make_stringf(
                     "Map '%s' is too big: %dx%d - max %dx%d",
                     name.c_str(),
                     map.width(), map.height(),
                     GXM, GYM);
        }
    }

    switch (orient)
    {
    case MAP_NORTH: case MAP_SOUTH:
        if (map.height() > GYM * 2 / 3)
        {
            return make_stringf("Map too large - height %d (max %d)",
                                map.height(), GYM * 2 / 3);
        }
        break;
    case MAP_EAST: case MAP_WEST:
        if (map.width() > GXM * 2 / 3)
        {
            return make_stringf("Map too large - width %d (max %d)",
                                map.width(), GXM * 2 / 3);
        }
        break;
    case MAP_NORTHEAST: case MAP_SOUTHEAST:
    case MAP_NORTHWEST: case MAP_SOUTHWEST:
    case MAP_FLOAT:     case MAP_CENTRE:
        if (map.width() > GXM * 2 / 3 || map.height() > GYM * 2 / 3)
        {
            return make_stringf("Map too large - %dx%d (max %dx%d)",
                                map.width(), map.height(),
                                GXM * 2 / 3, GYM * 2 / 3);
        }
        break;
    default:
        break;
    }

    // Encompass vaults, pure subvaults, and dummy vaults are exempt from
    // exit-checking.
    if (orient != MAP_ENCOMPASS && !has_tag("unrand") && !has_tag("dummy")
        && !has_tag("no_exits") && map.width() > 0 && map.height() > 0)
    {
        if (!has_exit())
        {
            return make_stringf(
                "Map '%s' has no (possible) exits; use TAGS: no_exits if "
                "this is intentional",
                name.c_str());
        }
    }

    dlua_set_map dl(this);
    return validate_map_placeable();
}

bool map_def::is_usable_in(const level_id &lid) const
{
    return depths.is_usable_in(lid);
}

void map_def::add_depth(const level_range &range)
{
    depths.add_depth(range);
}

bool map_def::has_depth() const
{
    return !depths.empty();
}

bool map_def::is_minivault() const
{
    return has_tag("minivault");
}

// Returns true if the map is a layout that allows other vaults to be
// built on it.
bool map_def::is_overwritable_layout() const
{
    return has_tag("overwritable");
}

// Tries to dock a floating vault - push it to one edge of the level.
// Docking will only succeed if two contiguous edges are all x/c/b/v
// (other walls prevent docking). If the vault's width is > GXM*2/3,
// it's also eligible for north/south docking, and if the height >
// GYM*2/3, it's eligible for east/west docking. Although docking is
// similar to setting the orientation, it doesn't affect 'orient'.
coord_def map_def::float_dock()
{
    const map_section_type orients[] =
        { MAP_NORTH, MAP_SOUTH, MAP_EAST, MAP_WEST,
          MAP_NORTHEAST, MAP_SOUTHEAST, MAP_NORTHWEST, MAP_SOUTHWEST };
    map_section_type which_orient = MAP_NONE;
    int norients = 0;

    for (unsigned i = 0; i < ARRAYSZ(orients); ++i)
    {
        if (map.solid_borders(orients[i]) && can_dock(orients[i])
            && one_chance_in(++norients))
        {
            which_orient = orients[i];
        }
    }

    if (which_orient == MAP_NONE || which_orient == MAP_FLOAT)
        return coord_def(-1, -1);

    dprf("Docking floating vault to %s", map_section_name(which_orient));

    return dock_pos(which_orient);
}

coord_def map_def::dock_pos(map_section_type norient) const
{
    const int minborder = 6;

    switch (norient)
    {
    case MAP_NORTH:
        return coord_def((GXM - map.width()) / 2, minborder);
    case MAP_SOUTH:
        return coord_def((GXM - map.width()) / 2,
                          GYM - minborder - map.height());
    case MAP_EAST:
        return coord_def(GXM - minborder - map.width(),
                          (GYM - map.height()) / 2);
    case MAP_WEST:
        return coord_def(minborder,
                          (GYM - map.height()) / 2);
    case MAP_NORTHEAST:
        return coord_def(GXM - minborder - map.width(), minborder);
    case MAP_NORTHWEST:
        return coord_def(minborder, minborder);
    case MAP_SOUTHEAST:
        return coord_def(GXM - minborder - map.width(),
                          GYM - minborder - map.height());
    case MAP_SOUTHWEST:
        return coord_def(minborder,
                          GYM - minborder - map.height());
    case MAP_CENTRE:
        return coord_def((GXM - map.width())  / 2,
                         (GYM - map.height()) / 2);
    default:
        return coord_def(-1, -1);
    }
}

bool map_def::can_dock(map_section_type norient) const
{
    switch (norient)
    {
    case MAP_NORTH: case MAP_SOUTH:
        return map.width() > GXM * 2 / 3;
    case MAP_EAST: case MAP_WEST:
        return map.height() > GYM * 2 / 3;
    default:
        return true;
    }
}

coord_def map_def::float_random_place() const
{
    // Try to leave enough around the float for roomification.
    int minhborder = MAPGEN_BORDER + 11,
        minvborder = minhborder;

    if (GXM - 2 * minhborder < map.width())
        minhborder = (GXM - map.width()) / 2 - 1;

    if (GYM - 2 * minvborder < map.height())
        minvborder = (GYM - map.height()) / 2 - 1;

    return coord_def(
        random_range(minhborder, GXM - minhborder - map.width()),
        random_range(minvborder, GYM - minvborder - map.height()));
}

point_vector map_def::anchor_points() const
{
    point_vector points;
    for (int y = 0, cheight = map.height(); y < cheight; ++y)
        for (int x = 0, cwidth = map.width(); x < cwidth; ++x)
            if (map.glyph(x, y) == '@')
                points.push_back(coord_def(x, y));
    return points;
}

coord_def map_def::float_aligned_place() const
{
    const point_vector our_anchors = anchor_points();
    const coord_def fail(-1, -1);

    dprf("Aligning floating vault with %u points vs %u reference points",
         (unsigned int)our_anchors.size(), (unsigned int)map_anchor_points.size());

    // Mismatch in the number of points we have to align, bail.
    if (our_anchors.size() != map_anchor_points.size())
        return fail;

    // Align first point of both vectors, then check that the others match.
    const coord_def pos = map_anchor_points[0] - our_anchors[0];

    for (int i = 1, psize = map_anchor_points.size(); i < psize; ++i)
        if (pos + our_anchors[i] != map_anchor_points[i])
            return fail;

    // Looking good, check bounds.
    if (!map_bounds(pos) || !map_bounds(pos + size() - 1))
        return fail;

    // Go us!
    return pos;
}

coord_def map_def::float_place()
{
    ASSERT(orient == MAP_FLOAT);

    coord_def pos(-1, -1);

    if (!map_anchor_points.empty())
        pos = float_aligned_place();
    else
    {
        if (coinflip())
            pos = float_dock();

        if (pos.x == -1)
            pos = float_random_place();
    }

    return pos;
}

void map_def::hmirror()
{
    if (has_tag("no_hmirror"))
        return;

    dprf("Mirroring %s horizontally.", name.c_str());
    map.hmirror();

    switch (orient)
    {
    case MAP_EAST:      orient = MAP_WEST; break;
    case MAP_NORTHEAST: orient = MAP_NORTHWEST; break;
    case MAP_SOUTHEAST: orient = MAP_SOUTHWEST; break;
    case MAP_WEST:      orient = MAP_EAST; break;
    case MAP_NORTHWEST: orient = MAP_NORTHEAST; break;
    case MAP_SOUTHWEST: orient = MAP_SOUTHEAST; break;
    default: break;
    }

    for (int i = 0, nsubvaults = this->subvault_places.size();
         i < nsubvaults; ++i)
    {
        subvault_place &sv = subvault_places[i];

        coord_def old_tl = sv.tl;
        coord_def old_br = sv.br;
        sv.tl.x = map.width() - 1 - old_br.x;
        sv.br.x = map.width() - 1 - old_tl.x;

        sv.subvault->map.hmirror();
    }
}

void map_def::vmirror()
{
    if (has_tag("no_vmirror"))
        return;

    dprf("Mirroring %s vertically.", name.c_str());
    map.vmirror();

    switch (orient)
    {
    case MAP_NORTH:     orient = MAP_SOUTH; break;
    case MAP_NORTHEAST: orient = MAP_SOUTHEAST; break;
    case MAP_NORTHWEST: orient = MAP_SOUTHWEST; break;

    case MAP_SOUTH:     orient = MAP_NORTH; break;
    case MAP_SOUTHEAST: orient = MAP_NORTHEAST; break;
    case MAP_SOUTHWEST: orient = MAP_NORTHWEST; break;
    default: break;
    }

    for (int i = 0, nsubvaults = this->subvault_places.size();
         i < nsubvaults; ++i)
    {
        subvault_place &sv = subvault_places[i];

        coord_def old_tl = sv.tl;
        coord_def old_br = sv.br;
        sv.tl.y = map.height() - 1 - old_br.y;
        sv.br.y = map.height() - 1 - old_tl.y;

        sv.subvault->map.vmirror();
    }
}

void map_def::rotate(bool clock)
{
    if (has_tag("no_rotate"))
        return;

#define GMINM ((GXM) < (GYM)? (GXM) : (GYM))
    // Make sure the largest dimension fits in the smaller map bound.
    if (map.width() <= GMINM && map.height() <= GMINM)
    {
        dprf("Rotating %s %sclockwise.", name.c_str(), !clock? "anti-" : "");
        map.rotate(clock);

        // Orientation shifts for clockwise rotation:
        const map_section_type clockrotate_orients[][2] =
        {
            { MAP_NORTH,        MAP_EAST        },
            { MAP_NORTHEAST,    MAP_SOUTHEAST   },
            { MAP_EAST,         MAP_SOUTH       },
            { MAP_SOUTHEAST,    MAP_SOUTHWEST   },
            { MAP_SOUTH,        MAP_WEST        },
            { MAP_SOUTHWEST,    MAP_NORTHWEST   },
            { MAP_WEST,         MAP_NORTH       },
            { MAP_NORTHWEST,    MAP_NORTHEAST   },
        };
        const int nrots = ARRAYSZ(clockrotate_orients);

        const int refindex = !clock;
        for (int i = 0; i < nrots; ++i)
            if (orient == clockrotate_orients[i][refindex])
            {
                orient = clockrotate_orients[i][!refindex];
                break;
            }

        for (int i = 0, nsubvaults = this->subvault_places.size();
             i < nsubvaults; ++i)
        {
            subvault_place &sv = subvault_places[i];

            coord_def p1, p2;
            if (clock) //Clockwise
            {
                p1 = coord_def(map.width() - 1 - sv.tl.y, sv.tl.x);
                p2 = coord_def(map.width() - 1 - sv.br.y, sv.br.x);
            }
            else
            {
                p1 = coord_def(sv.tl.y, map.height() - 1 - sv.tl.x);
                p2 = coord_def(sv.br.y, map.height() - 1 - sv.br.x);
            }

            sv.tl = coord_def(min(p1.x, p2.x), min(p1.y, p2.y));
            sv.br = coord_def(max(p1.x, p2.x), max(p1.y, p2.y));

            sv.subvault->map.rotate(clock);
        }
    }
}

void map_def::normalise()
{
    // Pad out lines that are shorter than max.
    map.normalise(' ');
}

string map_def::resolve()
{
    dlua_set_map dl(this);
    return "";
}

void map_def::fixup()
{
    normalise();

    // Fixup minivaults into floating vaults tagged "minivault".
    if (orient == MAP_NONE)
    {
        orient = MAP_FLOAT;
        tags += " minivault ";
    }
}

bool map_def::has_tag(const string &tagwanted) const
{
    if (tags.empty() || tagwanted.empty())
        return false;

    vector<string> wanted_tags = split_string(" ", tagwanted);

    for (unsigned int i = 0; i < wanted_tags.size(); i++)
        if (tags.find(" " + wanted_tags[i] + " ") == string::npos)
            return false;

    return true;
}

bool map_def::has_tag_prefix(const string &prefix) const
{
    return !tags.empty() && !prefix.empty()
        && tags.find(" " + prefix) != string::npos;
}

bool map_def::has_tag_suffix(const string &suffix) const
{
    return !tags.empty() && !suffix.empty()
        && tags.find(suffix + " ") != string::npos;
}

vector<string> map_def::get_tags() const
{
    return split_string(" ", tags);
}

keyed_mapspec *map_def::mapspec_at(const coord_def &c)
{
    return map.mapspec_at(c);
}

const keyed_mapspec *map_def::mapspec_at(const coord_def &c) const
{
    return map.mapspec_at(c);
}

string map_def::subvault_from_tagstring(const string &sub)
{
    string s = trimmed_string(sub);

    if (s.empty())
        return "";

    int sep = 0;
    string key;
    string substitute;

    string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
    if (!err.empty())
        return err;

    // Randomly picking a different vault per-glyph is not supported.
    if (sep != ':')
        return "SUBVAULT does not support '='.  Use ':' instead.";

    map_string_list vlist;
    err = _parse_weighted_str<map_string_list>(substitute, vlist);
    if (!err.empty())
        return err;

    bool fix = false;
    string_spec spec(key, fix, vlist);

    // Although it's unfortunate to not be able to validate subvaults except a
    // run-time, this allows subvaults to reference maps by tag that may not
    // have been loaded yet.
    if (!is_validating())
        err = apply_subvault(spec);

    if (!err.empty())
        return err;

    return "";
}

static void _register_subvault(const string name, const string spaced_tags)
{
    if (spaced_tags.find(" allow_dup ") == string::npos
        || spaced_tags.find(" luniq ") != string::npos)
    {
        env.new_used_subvault_names.insert(name);
    }

    vector<string> tags = split_string(" ", spaced_tags);
    for (int t = 0, ntags = tags.size(); t < ntags; t++)
    {
        const string &tag = tags[t];
        if (tag.find("uniq_") == 0 || tag.find("luniq_") == 0)
            env.new_used_subvault_tags.insert(tag);
    }
}

static void _reset_subvault_stack(const int reg_stack)
{
    env.new_subvault_names.resize(reg_stack);
    env.new_subvault_tags.resize(reg_stack);

    env.new_used_subvault_names.clear();
    env.new_used_subvault_tags.clear();
    for (int i = 0; i < reg_stack; i++)
    {
        _register_subvault(env.new_subvault_names[i],
                           env.new_subvault_tags[i]);
    }
}

string map_def::apply_subvault(string_spec &spec)
{
    // Find bounding box for key glyphs
    coord_def tl, br;
    if (!map.find_bounds(spec.key.c_str(), tl, br))
    {
        // No glyphs, so do nothing.
        return "";
    }

    int vwidth = br.x - tl.x + 1;
    int vheight = br.y - tl.y + 1;
    Matrix<bool> flags(vwidth, vheight);
    map.fill_mask_matrix(spec.key, tl, br, flags);

    // Remember the subvault registration pointer, so we can clear it.
    const int reg_stack = env.new_subvault_names.size();
    ASSERT(reg_stack == (int)env.new_subvault_tags.size());
    ASSERT(reg_stack >= (int)env.new_used_subvault_names.size());

    const int max_tries = 100;
    int ntries = 0;

    string tag = spec.get_property();
    while (++ntries <= max_tries)
    {
        // Each iteration, restore tags and names.  This is because this vault
        // may successfully load a subvault (registering its tag and name), but
        // then itself fail.
        _reset_subvault_stack(reg_stack);

        const map_def *orig = random_map_for_tag(tag, true);
        if (!orig)
            return make_stringf("No vault found for tag '%s'", tag.c_str());

        map_def vault = *orig;

        vault.load();

        // Temporarily set the subvault mask so this subvault can know
        // that it is being generated as a subvault.
        vault.svmask = &flags;

        if (!resolve_subvault(vault))
            continue;

        ASSERT(vault.map.width() <= vwidth);
        ASSERT(vault.map.height() <= vheight);

        const map_corner_t subvault_corners =
            map.merge_subvault(tl, br, flags, vault);

        copy_hooks_from(vault, "post_place");
        env.new_subvault_names.push_back(vault.name);
        env.new_subvault_tags.push_back(vault.tags);
        _register_subvault(vault.name, vault.tags);
        subvault_places.push_back(
            subvault_place(subvault_corners.first,
                           subvault_corners.second,
                           vault));

        return "";
    }

    // Failure, drop subvault registrations.
    _reset_subvault_stack(reg_stack);

    return make_stringf("Could not fit '%s' in (%d,%d) to (%d, %d).",
                        tag.c_str(), tl.x, tl.y, br.x, br.y);
}

bool map_def::is_subvault() const
{
    return svmask != NULL;
}

void map_def::apply_subvault_mask()
{
    if (!svmask)
        return;

    map.clear();
    map.extend(subvault_width(), subvault_height(), ' ');

    for (rectangle_iterator ri(map.get_iter()); ri; ++ri)
    {
        const coord_def mc = *ri;
        if (subvault_cell_valid(mc))
            map(mc) = '.';
        else
            map(mc) = ' ';
    }
}

bool map_def::subvault_cell_valid(const coord_def &c) const
{
    if (!svmask)
        return false;

    if (c.x < 0 || c.x >= subvault_width()
        || c.y < 0 || c.y >= subvault_height())
    {
        return false;
    }

    return (*svmask)(c.x, c.y);
}

int map_def::subvault_width() const
{
    if (!svmask)
        return 0;

    return svmask->width();
}

int map_def::subvault_height() const
{
    if (!svmask)
        return 0;

    return svmask->height();
}

int map_def::subvault_mismatch_count(const coord_def &offset) const
{
    int count = 0;
    if (!is_subvault())
        return count;

    for (rectangle_iterator ri(map.get_iter()); ri; ++ri)
    {
        // Coordinate in the subvault
        const coord_def sc = *ri;
        // Coordinate in the mask
        const coord_def mc = sc + offset;

        bool valid_subvault_cell = (map(sc) != ' ');
        bool valid_mask = (*svmask)(mc.x, mc.y);

        if (valid_subvault_cell && !valid_mask)
            count++;
    }

    return count;
}

///////////////////////////////////////////////////////////////////
// mons_list
//

mons_list::mons_list() : mons()
{
}

mons_spec mons_list::pick_monster(mons_spec_slot &slot)
{
    int totweight = 0;
    mons_spec pick;

    for (mons_spec_list::iterator i = slot.mlist.begin();
         i != slot.mlist.end(); ++i)
    {
        const int weight = i->genweight;
        if (x_chance_in_y(weight, totweight += weight))
            pick = *i;
    }

#if TAG_MAJOR_VERSION == 34
    // Force rebuild of the des cache to drop this check.
    if ((int)pick.type < -1)
        pick = (monster_type)(-100 - (int)pick.type);
#endif

    if (slot.fix_slot)
    {
        slot.mlist.clear();
        slot.mlist.push_back(pick);
        slot.fix_slot = false;
    }

    return pick;
}

mons_spec mons_list::get_monster(int index)
{
    if (index < 0 || index >= (int)mons.size())
        return mons_spec(RANDOM_MONSTER);

    return pick_monster(mons[index]);
}

mons_spec mons_list::get_monster(int slot_index, int list_index) const
{
    if (slot_index < 0 || slot_index >= (int)mons.size())
        return mons_spec(RANDOM_MONSTER);

    const mons_spec_list &list = mons[slot_index].mlist;

    if (list_index < 0 || list_index >= (int)list.size())
        return mons_spec(RANDOM_MONSTER);

    return list[list_index];
}

void mons_list::clear()
{
    mons.clear();
}

void mons_list::set_from_slot(const mons_list &list, int slot_index)
{
    clear();

    // Don't set anything if an invalid index.
    // Future calls to get_monster will just return a random monster.
    if (slot_index < 0 || (size_t)slot_index >= list.mons.size())
        return;

    mons.push_back(list.mons[slot_index]);
}

void mons_list::parse_mons_spells(mons_spec &spec, vector<string> &spells)
{
    spec.explicit_spells = true;
    spec.extra_monster_flags |= MF_SPELLCASTER;
    vector<string>::iterator spell_it;
    for (spell_it = spells.begin(); spell_it != spells.end(); ++spell_it)
    {
        monster_spells cur_spells;

        const vector<string> spell_names(split_string(";", (*spell_it)));
        if (spell_names.size() > NUM_MONSTER_SPELL_SLOTS)
        {
            error = make_stringf("Too many monster spells (max %d) in %s",
                                 NUM_MONSTER_SPELL_SLOTS,
                                 spell_it->c_str());
            return;
        }
        for (unsigned i = 0, ssize = spell_names.size(); i < ssize; ++i)
        {
            const string spname(
                lowercase_string(replace_all_of(spell_names[i], "_", " ")));
            if (spname.empty() || spname == "." || spname == "none"
                || spname == "no spell")
            {
                cur_spells[i] = SPELL_NO_SPELL;
            }
            else
            {
                const spell_type sp(spell_by_name(spname));
                if (sp == SPELL_NO_SPELL)
                {
                    error = make_stringf("Unknown spell name: '%s' in '%s'",
                                         spname.c_str(), spell_it->c_str());
                    return;
                }
                if (!is_valid_mon_spell(sp))
                {
                    error = make_stringf("Not a monster spell: '%s'",
                                         spname.c_str());
                    return;
                }
                cur_spells[i] = sp;
            }
        }

        spec.spells.push_back(cur_spells);
    }
}

mon_enchant mons_list::parse_ench(string &ench_str, bool perm)
{
    vector<string> ep = split_string(":", ench_str);
    if (ep.size() > (perm ? 2 : 3))
    {
        error = make_stringf("bad %sench specifier: \"%s\"",
                             perm ? "perm_" : "",
                             ench_str.c_str());
        return mon_enchant();
    }

    enchant_type et = name_to_ench(ep[0].c_str());
    if (et == ENCH_NONE)
    {
        error = make_stringf("unknown ench: \"%s\"", ep[0].c_str());
        return mon_enchant();
    }

    int deg = 0, dur = perm ? INFINITE_DURATION : 0;
    if (ep.size() > 1 && !ep[1].empty())
        if (!parse_int(ep[1].c_str(), deg))
        {
            error = make_stringf("invalid deg in ench specifier \"%s\"",
                                 ench_str.c_str());
            return mon_enchant();
        }
    if (ep.size() > 2 && !ep[2].empty())
        if (!parse_int(ep[2].c_str(), dur))
        {
            error = make_stringf("invalid dur in ench specifier \"%s\"",
                                 ench_str.c_str());
            return mon_enchant();
        }
    return mon_enchant(et, deg, 0, dur);
}

mons_list::mons_spec_slot mons_list::parse_mons_spec(string spec)
{
    mons_spec_slot slot;

    slot.fix_slot = strip_tag(spec, "fix_slot");

    vector<string> specs = split_string("/", spec);

    for (int i = 0, ssize = specs.size(); i < ssize; ++i)
    {
        mons_spec mspec;
        string s = specs[i];

        vector<string> spells(strip_multiple_tag_prefix(s, "spells:"));
        if (!spells.empty())
        {
            parse_mons_spells(mspec, spells);
            if (!error.empty())
                return slot;
        }

        vector<string> parts = split_string(";", s);

        if (parts.size() == 0)
        {
            error = make_stringf("Not enough non-semicolons for '%s' spec.",
                                 s.c_str());
            return slot;
        }

        string mon_str = parts[0];

        if (parts.size() > 2)
        {
            error = make_stringf("Too many semi-colons for '%s' spec.",
                                 mon_str.c_str());
            return slot;
        }
        else if (parts.size() == 2)
        {
            // TODO: Allow for a "fix_slot" type tag which will cause
            // all monsters generated from this spec to have the
            // exact same equipment.
            string items_str = parts[1];
            items_str = replace_all(items_str, "|", "/");

            vector<string> segs = split_string(".", items_str);

            if (segs.size() > NUM_MONSTER_SLOTS)
            {
                error = make_stringf("More items than monster item slots "
                                     "for '%s'.", mon_str.c_str());
                return slot;
            }

            for (int j = 0, isize = segs.size(); j < isize; ++j)
            {
                error = mspec.items.add_item(segs[j], false);
                if (!error.empty())
                    return slot;
            }
        }

        mspec.genweight = find_weight(mon_str);
        if (mspec.genweight == TAG_UNFOUND || mspec.genweight <= 0)
            mspec.genweight = 10;

        if (strip_tag(mon_str, "priest_spells"))
        {
            mspec.extra_monster_flags &= ~MF_ACTUAL_SPELLS;
            mspec.extra_monster_flags |= MF_PRIEST;
        }

        if (strip_tag(mon_str, "actual_spells"))
        {
            mspec.extra_monster_flags &= ~MF_PRIEST;
            mspec.extra_monster_flags |= MF_ACTUAL_SPELLS;
        }

        mspec.generate_awake = strip_tag(mon_str, "generate_awake");
        mspec.patrolling     = strip_tag(mon_str, "patrolling");
        mspec.band           = strip_tag(mon_str, "band");

        const string att = strip_tag_prefix(mon_str, "att:");
        if (att.empty() || att == "hostile")
            mspec.attitude = ATT_HOSTILE;
        else if (att == "friendly")
            mspec.attitude = ATT_FRIENDLY;
        else if (att == "good_neutral")
            mspec.attitude = ATT_GOOD_NEUTRAL;
        else if (att == "fellow_slime" || att == "strict_neutral")
            mspec.attitude = ATT_STRICT_NEUTRAL;
        else if (att == "neutral")
            mspec.attitude = ATT_NEUTRAL;

        // Useful for summoned monsters.
        if (strip_tag(mon_str, "seen"))
            mspec.extra_monster_flags |= MF_SEEN;

        if (strip_tag(mon_str, "always_corpse"))
            mspec.props["always_corpse"] = true;

        if (strip_tag(mon_str, "never_corpse"))
            mspec.props["never_corpse"] = true;

        if (!mon_str.empty() && isadigit(mon_str[0]))
        {
            // Look for space after initial digits.
            string::size_type pos = mon_str.find_first_not_of("0123456789");
            if (pos != string::npos && mon_str[pos] == ' ')
            {
                const string mcount = mon_str.substr(0, pos);
                const int count = atoi(mcount.c_str()); // safe atoi()
                if (count >= 1 && count <= 99)
                    mspec.quantity = count;

                mon_str = mon_str.substr(pos);
            }
        }

        // place:Elf:$ to choose monsters appropriate for that level,
        // for example.
        const string place = strip_tag_prefix(mon_str, "place:");
        if (!place.empty())
        {
            try
            {
                mspec.place = level_id::parse_level_id(place);
            }
            catch (const string &err)
            {
                error = err;
                return slot;
            }
        }

        mspec.hd = min(100, strip_number_tag(mon_str, "hd:"));
        if (mspec.hd == TAG_UNFOUND)
            mspec.hd = 0;

        mspec.hp = strip_number_tag(mon_str, "hp:");
        if (mspec.hp == TAG_UNFOUND)
            mspec.hp = 0;

        int dur = strip_number_tag(mon_str, "dur:");
        if (dur == TAG_UNFOUND)
            dur = 0;
        else if (dur < 1 || dur > 6)
            dur = 0;

        mspec.abjuration_duration = dur;

        string shifter_name = replace_all_of(strip_tag_prefix(mon_str, "shifter:"), "_", " ");

        if (!shifter_name.empty())
        {
            mspec.initial_shifter = get_monster_by_name(shifter_name);
            if (mspec.initial_shifter == MONS_PROGRAM_BUG)
                mspec.initial_shifter = RANDOM_MONSTER;
        }

        int summon_type = 0;
        string s_type = strip_tag_prefix(mon_str, "sum:");
        if (!s_type.empty())
        {
            // In case of spells!
            s_type = replace_all_of(s_type, "_", " ");
            summon_type = static_cast<int>(str_to_summon_type(s_type));
            if (summon_type == SPELL_NO_SPELL)
            {
                error = make_stringf("bad monster summon type: \"%s\"",
                                s_type.c_str());
                return slot;
            }
            if (mspec.abjuration_duration == 0)
            {
                error = "marked summon with no duration";
                return slot;
            }
        }

        mspec.summon_type = summon_type;

        string non_actor_summoner = strip_tag_prefix(mon_str, "nas:");
        if (!non_actor_summoner.empty())
        {
            non_actor_summoner = replace_all_of(non_actor_summoner, "_", " ");
            mspec.non_actor_summoner = non_actor_summoner;
            if (mspec.abjuration_duration == 0)
            {
                error = "marked summon with no duration";
                return slot;
            }
        }

        string colour = strip_tag_prefix(mon_str, "col:");
        if (!colour.empty())
        {
            if (colour == "any")
                mspec.colour = -1; // XXX: Hack
            else
            {
                mspec.colour = str_to_colour(colour, BLACK);
                if (mspec.colour == BLACK)
                {
                    error = make_stringf("bad monster colour \"%s\" in \"%s\"",
                                         colour.c_str(), specs[i].c_str());
                    return slot;
                }
            }
        }

        string mongod = strip_tag_prefix(mon_str, "god:");
        if (!mongod.empty())
        {
            const string god_name(replace_all_of(mongod, "_", " "));

            mspec.god = str_to_god(god_name);

            if (mspec.god == GOD_NO_GOD)
            {
                error = make_stringf("bad monster god: \"%s\"",
                                     god_name.c_str());
                return slot;
            }

            if (strip_tag(mon_str, "god_gift"))
                mspec.god_gift = true;
        }

        string tile = strip_tag_prefix(mon_str, "tile:");
        if (!tile.empty())
        {
            tileidx_t index;
            if (!tile_player_index(tile.c_str(), &index))
            {
                error = make_stringf("bad tile name: \"%s\".", tile.c_str());
                return slot;
            }
            // Store name along with the tile.
            mspec.props["monster_tile_name"].get_string() = tile;
            mspec.props["monster_tile"] = short(index);
        }

        string dbname = strip_tag_prefix(mon_str, "dbname:");
        if (!dbname.empty())
        {
            dbname = replace_all_of(dbname, "_", " ");
            mspec.props["dbname"].get_string() = dbname;
        }

        string name = strip_tag_prefix(mon_str, "name:");
        if (!name.empty())
        {
            name = replace_all_of(name, "_", " ");
            mspec.monname = name;

            if (strip_tag(mon_str, "name_suffix")
                || strip_tag(mon_str, "n_suf"))
            {
                mspec.extra_monster_flags |= MF_NAME_SUFFIX;
            }
            else if (strip_tag(mon_str, "name_adjective")
                     || strip_tag(mon_str, "n_adj"))
            {
                mspec.extra_monster_flags |= MF_NAME_ADJECTIVE;
            }
            else if (strip_tag(mon_str, "name_replace")
                     || strip_tag(mon_str, "n_rpl"))
            {
                mspec.extra_monster_flags |= MF_NAME_REPLACE;
            }

            if (strip_tag(mon_str, "name_definite")
                || strip_tag(mon_str, "n_the"))
            {
                mspec.extra_monster_flags |= MF_NAME_DEFINITE;
            }

            // Reasoning for setting more than one flag: suffixes and
            // adjectives need NAME_DESCRIPTOR to get proper grammar,
            // and definite names do nothing with the description unless
            // NAME_DESCRIPTOR is also set.
            const uint64_t name_flags = mspec.extra_monster_flags & MF_NAME_MASK;
            const bool need_name_desc =
                name_flags == MF_NAME_SUFFIX
                   || name_flags == MF_NAME_ADJECTIVE
                   || (mspec.extra_monster_flags & MF_NAME_DEFINITE);

            if (strip_tag(mon_str, "name_descriptor")
                || strip_tag(mon_str, "n_des")
                || need_name_desc)
            {
                mspec.extra_monster_flags |= MF_NAME_DESCRIPTOR;
            }

            if (strip_tag(mon_str, "name_species")
                || strip_tag(mon_str, "n_spe"))
            {
                mspec.extra_monster_flags |= MF_NAME_SPECIES;
            }

            if (strip_tag(mon_str, "name_zombie")
                || strip_tag(mon_str, "n_zom"))
            {
                mspec.extra_monster_flags |= MF_NAME_ZOMBIE;
            }
            if (strip_tag(mon_str, "name_nocorpse")
                || strip_tag(mon_str, "n_noc"))
            {
                mspec.extra_monster_flags |= MF_NAME_NOCORPSE;
            }
        }

        string ench_str;
        while (!(ench_str = strip_tag_prefix(mon_str, "ench:")).empty())
        {
            mspec.ench.push_back(parse_ench(ench_str, false));
            if (!error.empty())
                return slot;
        }
        while (!(ench_str = strip_tag_prefix(mon_str, "perm_ench:")).empty())
        {
            mspec.ench.push_back(parse_ench(ench_str, true));
            if (!error.empty())
                return slot;
        }

        trim_string(mon_str);

        if (mon_str == "8")
            mspec.type = RANDOM_SUPER_OOD;
        else if (mon_str == "9")
            mspec.type = RANDOM_MODERATE_OOD;
        else if (mspec.place.is_valid())
        {
            // For monster specs such as place:Orc:4 zombie, we may
            // have a monster modifier, in which case we set the
            // modifier in monbase.
            const mons_spec nspec = mons_by_name("orc " + mon_str);
            if (nspec.type != MONS_PROGRAM_BUG)
            {
                // Is this a modified monster?
                if (nspec.monbase != MONS_PROGRAM_BUG
                    && mons_class_is_zombified(static_cast<monster_type>(nspec.type)))
                {
                    mspec.monbase = static_cast<monster_type>(nspec.type);
                }
            }
            // Now check for chimera
            const mons_spec cspec = mons_by_name("rat-rat-rat " + mon_str);
            if (cspec.type != MONS_PROGRAM_BUG)
            {
                // Is this a modified monster?
                if (cspec.monbase != MONS_PROGRAM_BUG
                    && mons_class_is_chimeric(static_cast<monster_type>(cspec.type)))
                {
                    mspec.monbase = static_cast<monster_type>(cspec.type);
                }
            }
        }
        else if (mon_str != "0")
        {
            const mons_spec nspec = mons_by_name(mon_str);

            if (nspec.type == MONS_PROGRAM_BUG)
            {
                error = make_stringf("unknown monster: \"%s\"",
                                     mon_str.c_str());
                return slot;
            }

            if (mons_class_flag(nspec.type, M_CANT_SPAWN))
            {
                error = make_stringf("can't place dummy monster: \"%s\"",
                                     mon_str.c_str());
                return slot;
            }

            mspec.type    = nspec.type;
            mspec.monbase = nspec.monbase;
            mspec.number  = nspec.number;
            mspec.chimera_mons = nspec.chimera_mons;
            if (nspec.colour && !mspec.colour)
                mspec.colour = nspec.colour;
        }

        if (!mspec.items.empty())
        {
            monster_type type = (monster_type)mspec.type;
            if (type == RANDOM_DRACONIAN
                || type == RANDOM_BASE_DRACONIAN
                || type == RANDOM_NONBASE_DRACONIAN)
            {
                type = MONS_DRACONIAN;
            }

            if (type >= NUM_MONSTERS)
            {
                error = "Can't give spec items to a random monster.";
                return slot;
            }
            else if (mons_class_itemuse(type) < MONUSE_STARTING_EQUIPMENT
                     && (!mons_class_is_animated_weapon(type)
                         || mspec.items.size() > 1)
                     && (type != MONS_ZOMBIE && type != MONS_SKELETON
                         || invalid_monster_type(mspec.monbase)
                         || mons_class_itemuse(mspec.monbase)
                            < MONUSE_STARTING_EQUIPMENT))
            {
                error = make_stringf("Monster '%s' can't use items.",
                    mon_str.c_str());
            }
        }

        slot.mlist.push_back(mspec);
    }

    return slot;
}

string mons_list::add_mons(const string &s, bool fix)
{
    error.clear();

    mons_spec_slot slotmons = parse_mons_spec(s);
    if (!error.empty())
        return error;

    if (fix)
    {
        slotmons.fix_slot = true;
        pick_monster(slotmons);
    }

    mons.push_back(slotmons);

    return error;
}

string mons_list::set_mons(int index, const string &s)
{
    error.clear();

    if (index < 0)
        return error = make_stringf("Index out of range: %d", index);

    mons_spec_slot slotmons = parse_mons_spec(s);
    if (!error.empty())
        return error;

    if (index >= (int) mons.size())
    {
        mons.reserve(index + 1);
        mons.resize(index + 1, mons_spec_slot());
    }
    mons[index] = slotmons;
    return error;
}

void mons_list::get_zombie_type(string s, mons_spec &spec) const
{
    static const char *zombie_types[] =
    {
        " zombie", " skeleton", " simulacrum", " spectre", NULL
    };

    // This order must match zombie_types, indexed from one.
    static const monster_type zombie_montypes[] =
    {
        MONS_PROGRAM_BUG, MONS_ZOMBIE, MONS_SKELETON, MONS_SIMULACRUM,
        MONS_SPECTRAL_THING,
    };

    int mod = ends_with(s, zombie_types);
    if (!mod)
    {
        const string spectre("spectral ");
        if (s.find(spectre) == 0)
        {
            mod = ends_with(" spectre", zombie_types);
            s = s.substr(spectre.length());
        }
        else
        {
            spec.type = MONS_PROGRAM_BUG;
            return;
        }
    }
    else
        s = s.substr(0, s.length() - strlen(zombie_types[mod - 1]));

    trim_string(s);

    mons_spec base_monster = mons_by_name(s);
    if (base_monster.type < 0)
        base_monster.type = MONS_PROGRAM_BUG;
    spec.monbase = static_cast<monster_type>(base_monster.type);
    spec.number = base_monster.number;

    const int zombie_size = mons_zombie_size(spec.monbase);
    if (!zombie_size)
    {
        spec.type = MONS_PROGRAM_BUG;
        return;
    }
    if (mod == 1 && mons_class_flag(spec.monbase, M_NO_ZOMBIE))
    {
        spec.type = MONS_PROGRAM_BUG;
        return;
    }
    if (mod == 2 && mons_class_flag(spec.monbase, M_NO_SKELETON))
    {
        spec.type = MONS_PROGRAM_BUG;
        return;
    }

    spec.type = zombie_montypes[mod];
}

mons_spec mons_list::get_hydra_spec(const string &name) const
{
    int    nheads = -1;
    string prefix = name.substr(0, name.find("-"));

    nheads = atoi(prefix.c_str());
    if (nheads != 0)
        ;
    else if (prefix == "0")
        nheads = 0;
    else
    {
        // Might be "two-headed hydra" type string.
        for (int i = 0; i <= 20; ++i)
            if (number_in_words(i) == prefix)
            {
                nheads = i;
                break;
            }
    }

    if (nheads < 1)
        nheads = 27;  // What can I say? :P
    else if (nheads > 20)
    {
#if defined(DEBUG) || defined(DEBUG_DIAGNOSTICS)
        mprf(MSGCH_DIAGNOSTICS, "Hydra spec wants %d heads, clamping to 20.",
             nheads);
#endif
        nheads = 20;
    }

    return mons_spec(MONS_HYDRA, MONS_NO_MONSTER, nheads);
}

mons_spec mons_list::get_slime_spec(const string &name) const
{
    string prefix = name.substr(0, name.find(" slime creature"));

    int slime_size = 1;

    if (prefix == "large")
        slime_size = 2;
    else if (prefix == "very large")
        slime_size = 3;
    else if (prefix == "enormous")
        slime_size = 4;
    else if (prefix == "titanic")
        slime_size = 5;
    else
    {
#if defined(DEBUG) || defined(DEBUG_DIAGNOSTICS)
        mprf(MSGCH_DIAGNOSTICS, "Slime spec wants invalid size '%s'",
             prefix.c_str());
#endif
    }

    return mons_spec(MONS_SLIME_CREATURE, MONS_NO_MONSTER, slime_size);
}

// Handle draconians specified as:
// Exactly as in mon-data.h:
//    yellow draconian or draconian knight - the monster specified.
//
// Others:
//    any draconian => any random draconain
//    any base draconian => any unspecialised coloured draconian.
//    any nonbase draconian => any specialised coloured draconian.
//    any <colour> draconian => any draconian of the colour.
//    any nonbase <colour> draconian => any specialised drac of the colour.
//
mons_spec mons_list::drac_monspec(string name) const
{
    mons_spec spec;

    spec.type = get_monster_by_name(name);

    // Check if it's a simple drac name, we're done.
    if (spec.type != MONS_PROGRAM_BUG)
        return spec;

    spec.type = RANDOM_DRACONIAN;

    // Request for any draconian?
    if (starts_with(name, "any "))
        name = name.substr(4); // Strip "any "

    if (starts_with(name, "base "))
    {
        // Base dracs need no further work.
        return RANDOM_BASE_DRACONIAN;
    }
    else if (starts_with(name, "nonbase "))
    {
        spec.type = RANDOM_NONBASE_DRACONIAN;
        name = name.substr(8);
    }

    trim_string(name);

    // Match "any draconian"
    if (name == "draconian")
        return spec;

    // Check for recognition again to match any (nonbase) <colour> draconian.
    const monster_type colour = get_monster_by_name(name);
    if (colour != MONS_PROGRAM_BUG)
    {
        spec.monbase = colour;
        return spec;
    }

    // Only legal possibility left is <colour> boss drac.
    string::size_type wordend = name.find(' ');
    if (wordend == string::npos)
        return MONS_PROGRAM_BUG;

    string scolour = name.substr(0, wordend);
    if ((spec.monbase = draconian_colour_by_name(scolour)) == MONS_PROGRAM_BUG)
        return MONS_PROGRAM_BUG;

    name = trimmed_string(name.substr(wordend + 1));
    spec.type = get_monster_by_name(name);

    // We should have a non-base draconian here.
    if (spec.type == MONS_PROGRAM_BUG
        || mons_genus(static_cast<monster_type>(spec.type)) != MONS_DRACONIAN
        || mons_is_base_draconian(spec.type))
    {
        return MONS_PROGRAM_BUG;
    }

    return spec;
}

// As with draconians, so with demonspawn.
mons_spec mons_list::demonspawn_monspec(string name) const
{
    mons_spec spec;

    spec.type = get_monster_by_name(name);

    // Check if it's a simple demonspawn name, we're done.
    if (spec.type != MONS_PROGRAM_BUG)
        return spec;

    spec.type = RANDOM_DEMONSPAWN;

    // Request for any demonspawn?
    if (starts_with(name, "any "))
        name = name.substr(4); // Strip "any "

    if (starts_with(name, "base "))
    {
        // Base demonspawn need no further work.
        return RANDOM_BASE_DEMONSPAWN;
    }
    else if (starts_with(name, "nonbase "))
    {
        spec.type = RANDOM_NONBASE_DEMONSPAWN;
        name = name.substr(8);
    }

    trim_string(name);

    // Match "any demonspawn"
    if (name == "demonspawn")
        return spec;

    // Check for recognition again to match any (nonbase) <base> demonspawn.
    const monster_type base = get_monster_by_name(name);
    if (base != MONS_PROGRAM_BUG)
    {
        spec.monbase = base;
        return spec;
    }

    // Only legal possibility left is <base> boss demonspawn.
    string::size_type wordend = name.find(' ');
    if (wordend == string::npos)
        return MONS_PROGRAM_BUG;

    string sbase = name.substr(0, wordend);
    if ((spec.monbase = demonspawn_base_by_name(sbase)) == MONS_PROGRAM_BUG)
        return MONS_PROGRAM_BUG;

    name = trimmed_string(name.substr(wordend + 1));
    spec.type = get_monster_by_name(name);

    // We should have a non-base demonspawn here.
    if (spec.type == MONS_PROGRAM_BUG
        || mons_genus(static_cast<monster_type>(spec.type)) != MONS_DEMONSPAWN
        || spec.type == MONS_DEMONSPAWN
        || (spec.type >= MONS_FIRST_BASE_DEMONSPAWN
            && spec.type <= MONS_LAST_BASE_DEMONSPAWN))
    {
        return MONS_PROGRAM_BUG;
    }

    return spec;
}

mons_spec mons_list::soh_monspec(string name) const
{
    // "serpent of hell " is 16 characters
    name = name.substr(16);
    string abbrev =
        uppercase_first(lowercase(name)).substr(0, 3);
    switch (str_to_branch(abbrev))
    {
        case BRANCH_GEHENNA:
            return MONS_SERPENT_OF_HELL;
        case BRANCH_COCYTUS:
            return MONS_SERPENT_OF_HELL_COCYTUS;
        case BRANCH_DIS:
            return MONS_SERPENT_OF_HELL_DIS;
        case BRANCH_TARTARUS:
            return MONS_SERPENT_OF_HELL_TARTARUS;
        default:
            return MONS_PROGRAM_BUG;
    }
}

mons_spec mons_list::mons_by_name(string name) const
{
    name = replace_all_of(name, "_", " ");
    name = replace_all(name, "random", "any");

    if (name == "nothing")
        return MONS_NO_MONSTER;

    // Special casery:
    if (name == "pandemonium lord")
        return MONS_PANDEMONIUM_LORD;

    if (name == "any" || name == "any monster")
        return RANDOM_MONSTER;

    if (name == "any demon")
        return RANDOM_DEMON;

    if (name == "any lesser demon" || name == "lesser demon")
        return RANDOM_DEMON_LESSER;

    if (name == "any common demon" || name == "common demon")
        return RANDOM_DEMON_COMMON;

    if (name == "any greater demon" || name == "greater demon")
        return RANDOM_DEMON_GREATER;

    if (name == "small zombie" || name == "large zombie"
        || name == "small skeleton" || name == "large skeleton"
        || name == "small simulacrum" || name == "large simulacrum")
    {
        return MONS_PROGRAM_BUG;
    }

    if (name == "small abomination")
        return MONS_ABOMINATION_SMALL;
    if (name == "large abomination")
        return MONS_ABOMINATION_LARGE;

    if (ends_with(name, "-headed hydra") && !starts_with(name, "spectral "))
        return get_hydra_spec(name);

    if (ends_with(name, " slime creature"))
        return get_slime_spec(name);

    mons_spec spec;
    if (ends_with(name, " chimera"))
    {
        const string chimera_spec = name.substr(0, name.length() - 8);
        vector<string> components = split_string("-", chimera_spec);
        if (components.size() != 3)
            return MONS_PROGRAM_BUG;

        spec = MONS_CHIMERA;
        for (unsigned int i = 0; i < components.size(); i++)
        {
            monster_type monstype = get_monster_by_name(components[i]);
            if (monstype == MONS_PROGRAM_BUG)
                return MONS_PROGRAM_BUG;
            spec.chimera_mons.push_back(monstype);
        }
        return spec;
    }

    if (name.find(" ugly thing") != string::npos)
    {
        const string::size_type wordend = name.find(' ');
        const string first_word = name.substr(0, wordend);

        const int colour = str_to_ugly_thing_colour(first_word);
        if (colour)
        {
            spec = mons_by_name(name.substr(wordend + 1));
            spec.colour = colour;
            return spec;
        }
    }

    get_zombie_type(name, spec);
    if (spec.type != MONS_PROGRAM_BUG)
        return spec;

    if (name.find("draconian") != string::npos)
        return drac_monspec(name);

    // FIXME: cleaner way to do this?
    if (name.find("demonspawn") != string::npos
        || name.find("black sun") != string::npos
        || name.find("blood saint") != string::npos
        || name.find("chaos champion") != string::npos
        || name.find("corrupter") != string::npos
        || name.find("warmonger") != string::npos)
    {
        return demonspawn_monspec(name);
    }

    // The space is important - it indicates a flavour is being specified.
    if (name.find("serpent of hell ") != string::npos)
        return soh_monspec(name);

    return get_monster_by_name(name);
}

//////////////////////////////////////////////////////////////////////
// item_list

item_spec::item_spec(const item_spec &other)
    : _corpse_monster_spec(NULL)
{
    *this = other;
}

item_spec &item_spec::operator = (const item_spec &other)
{
    if (this != &other)
    {
        genweight = other.genweight;
        base_type = other.base_type;
        sub_type  = other.sub_type;
        plus = other.plus;
        plus2 = other.plus2;
        ego = other.ego;
        allow_uniques = other.allow_uniques;
        level = other.level;
        item_special = other.item_special;
        qty = other.qty;
        acquirement_source = other.acquirement_source;
        place = other.place;
        props = other.props;

        release_corpse_monster_spec();
        if (other._corpse_monster_spec)
            set_corpse_monster_spec(other.corpse_monster_spec());
    }
    return *this;
}

item_spec::~item_spec()
{
    release_corpse_monster_spec();
}

void item_spec::release_corpse_monster_spec()
{
    delete _corpse_monster_spec;
    _corpse_monster_spec = NULL;
}

bool item_spec::corpselike() const
{
    return base_type == OBJ_CORPSES && (sub_type == CORPSE_BODY
                                        || sub_type == CORPSE_SKELETON)
           || base_type == OBJ_FOOD && sub_type == FOOD_CHUNK;
}

const mons_spec &item_spec::corpse_monster_spec() const
{
    ASSERT(_corpse_monster_spec);
    return *_corpse_monster_spec;
}

void item_spec::set_corpse_monster_spec(const mons_spec &spec)
{
    if (&spec != _corpse_monster_spec)
    {
        release_corpse_monster_spec();
        _corpse_monster_spec = new mons_spec(spec);
    }
}

void item_list::clear()
{
    items.clear();
}

item_spec item_list::random_item()
{
    if (items.empty())
    {
        const item_spec none;
        return none;
    }

    return get_item(random2(size()));
}

typedef pair<item_spec, int> item_pair;

item_spec item_list::random_item_weighted()
{
    const item_spec none;

    vector<item_pair> pairs;
    for (int i = 0, sz = size(); i < sz; ++i)
    {
        item_spec item = get_item(i);
        pairs.push_back(item_pair(item, item.genweight));
    }

    item_spec* rn_item = random_choose_weighted(pairs);
    if (rn_item)
        return *rn_item;

    return none;
}

item_spec item_list::pick_item(item_spec_slot &slot)
{
    int cumulative = 0;
    item_spec spec;
    for (item_spec_list::const_iterator i = slot.ilist.begin();
         i != slot.ilist.end(); ++i)
    {
        const int weight = i->genweight;
        if (x_chance_in_y(weight, cumulative += weight))
            spec = *i;
    }

    if (slot.fix_slot)
    {
        slot.ilist.clear();
        slot.ilist.push_back(spec);
        slot.fix_slot = false;
    }

    return spec;
}

item_spec item_list::get_item(int index)
{
    if (index < 0 || index >= (int) items.size())
    {
        const item_spec none;
        return none;
    }

    return pick_item(items[index]);
}

string item_list::add_item(const string &spec, bool fix)
{
    error.clear();

    item_spec_slot sp = parse_item_spec(spec);
    if (error.empty())
    {
        if (fix)
        {
            sp.fix_slot = true;
            pick_item(sp);
        }

        items.push_back(sp);
    }

    return error;
}

string item_list::set_item(int index, const string &spec)
{
    error.clear();
    if (index < 0)
        return error = make_stringf("Index %d out of range", index);

    item_spec_slot sp = parse_item_spec(spec);
    if (error.empty())
    {
        if (index >= (int) items.size())
        {
            items.reserve(index + 1);
            items.resize(index + 1, item_spec_slot());
        }
        items.push_back(sp);
    }

    return error;
}

void item_list::set_from_slot(const item_list &list, int slot_index)
{
    clear();

    // Don't set anything if an invalid index.
    // Future calls to get_item will just return no item.
    if (slot_index < 0 || (size_t)slot_index >= list.items.size())
        return;

    items.push_back(list.items[slot_index]);
}

// TODO: More checking for inappropriate combinations, like the holy
// wrath brand on a demonic weapon or the running ego on a helmet.
// NOTE: Be sure to update the reference in syntax.txt if this gets moved!
static int _str_to_ego(item_spec &spec, string ego_str)
{
    const char* armour_egos[] =
    {
        "running",
        "fire_resistance",
        "cold_resistance",
        "poison_resistance",
        "see_invisible",
        "darkness",
        "strength",
        "dexterity",
        "intelligence",
        "ponderousness",
        "flying",
        "magic_resistance",
        "protection",
        "stealth",
        "resistance",
        "positive_energy",
        "archmagi",
#if TAG_MAJOR_VERSION == 34
        "preservation",
#endif
        "reflection",
        "spirit_shield",
        "archery",
        "jumping",
        NULL
    };
    COMPILE_CHECK(ARRAYSZ(armour_egos) == NUM_REAL_SPECIAL_ARMOURS);

    const char* weapon_brands[] =
    {
        "flaming",
        "freezing",
        "holy_wrath",
        "electrocution",
#if TAG_MAJOR_VERSION == 34
        "orc_slaying",
        "dragon_slaying",
#endif
        "venom",
        "protection",
        "draining",
        "speed",
        "vorpal",
        "flame",
        "frost",
        "vampirism",
        "pain",
        "antimagic",
        "distortion",
#if TAG_MAJOR_VERSION == 34
        "reaching",
        "returning",
#endif
        "chaos",
        "evasion",
#if TAG_MAJOR_VERSION == 34
        "confuse",
#endif
        "penetration",
        "reaping",
        NULL
    };
    COMPILE_CHECK(ARRAYSZ(weapon_brands) == NUM_REAL_SPECIAL_WEAPONS);

    const char* missile_brands[] =
    {
        "flame",
        "frost",
        "poisoned",
        "curare",
        "returning",
        "chaos",
        "penetration",
        "dispersal",
        "exploding",
        "steel",
        "silver",
        "paralysis",
        "slow",
        "sleep",
        "confusion",
#if TAG_MAJOR_VERSION == 34
        "sickness",
#endif
        "frenzy",
        NULL
    };
    COMPILE_CHECK(ARRAYSZ(missile_brands) == NUM_REAL_SPECIAL_MISSILES);

    const char** name_lists[3] = {armour_egos, weapon_brands, missile_brands};

    int armour_order[3]  = {0, 1, 2};
    int weapon_order[3]  = {1, 0, 2};
    int missile_order[3] = {2, 0, 1};

    int *order;

    switch (spec.base_type)
    {
    case OBJ_ARMOUR:
        order = armour_order;
        break;

    case OBJ_WEAPONS:
        order = weapon_order;
        break;

    case OBJ_MISSILES:
        // HACK to get an old save to load; remove me soon?
        if (ego_str == "sleeping")
            return SPMSL_SLEEP;
        order = missile_order;
        break;

    default:
        die("Bad base_type for ego'd item.");
        return 0;
    }

    const char** allowed = name_lists[order[0]];

    for (int i = 0; allowed[i] != NULL; i++)
    {
        if (ego_str == allowed[i])
            return i + 1;
    }

    // Incompatible or non-existent ego type
    for (int i = 1; i <= 2; i++)
    {
        const char** list = name_lists[order[i]];

        for (int j = 0; list[j] != NULL; j++)
            if (ego_str == list[j])
                // Ego incompatible with base type.
                return -1;
    }

    // Non-existent ego
    return 0;
}

int item_list::parse_acquirement_source(const string &source)
{
    const string god_name(replace_all_of(source, "_", " "));
    const god_type god(str_to_god(god_name));
    if (god == GOD_NO_GOD)
        error = make_stringf("unknown god name: '%s'", god_name.c_str());
    return god;
}

bool item_list::monster_corpse_is_valid(monster_type *mons,
                                        const string &name,
                                        bool corpse,
                                        bool skeleton,
                                        bool chunk)
{
    if (*mons == RANDOM_NONBASE_DRACONIAN || *mons == RANDOM_NONBASE_DEMONSPAWN)
    {
        error = "Can't use non-base monster for corpse/chunk items";
        return false;
    }

    // Accept randomised types without further checks:
    if (*mons >= NUM_MONSTERS)
        return true;

    // Convert to the monster species:
    *mons = mons_species(*mons);

    if (!mons_class_can_leave_corpse(*mons))
    {
        error = make_stringf("'%s' cannot leave corpses", name.c_str());
        return false;
    }

    if (skeleton && !mons_skeleton(*mons))
    {
        error = make_stringf("'%s' has no skeleton", name.c_str());
        return false;
    }

    // We're ok.
    return true;
}

item_spec item_list::parse_corpse_spec(item_spec &result, string s)
{
    const bool never_decay = strip_tag(s, "never_decay");
    const bool rotting = strip_tag(s, "rotting");

    if (never_decay)
        result.props[CORPSE_NEVER_DECAYS].get_bool() = true;
    if (rotting)
        result.item_special = ROTTING_CORPSE;

    const bool corpse = strip_suffix(s, "corpse");
    const bool skeleton = !corpse && strip_suffix(s, "skeleton");
    const bool chunk = !corpse && !skeleton && strip_suffix(s, "chunk");

    result.base_type = chunk ? OBJ_FOOD : OBJ_CORPSES;
    result.sub_type  = (chunk ? static_cast<int>(FOOD_CHUNK) :
                        static_cast<int>(corpse ? CORPSE_BODY :
                                         CORPSE_SKELETON));

    // The caller wants a specific monster, no doubt with the best of
    // motives. Let's indulge them:
    mons_list mlist;
    const string mons_parse_err = mlist.add_mons(s, true);
    if (!mons_parse_err.empty())
    {
        error = mons_parse_err;
        return result;
    }

    // Get the actual monster spec:
    mons_spec spec = mlist.get_monster(0);
    monster_type mtype = static_cast<monster_type>(spec.type);
    if (!monster_corpse_is_valid(&mtype, s, corpse, skeleton, chunk))
    {
        error = make_stringf("Requested corpse '%s' is invalid",
                             s.c_str());
        return result;
    }

    // Ok, looking good, the caller can have their requested toy.
    result.set_corpse_monster_spec(spec);
    return result;
}

// Strips the first word from s and returns it.
static string _get_and_discard_word(string* s)
{
    string result;
    const size_t spaceloc = s->find(' ');
    if (spaceloc == string::npos)
    {
        result = *s;
        s->clear();
    }
    else
    {
        result = s->substr(0, spaceloc);
        s->erase(0, spaceloc + 1);
    }

    return result;
}

static deck_rarity_type _rarity_string_to_rarity(const string& s)
{
    if (s == "common")    return DECK_RARITY_COMMON;
    if (s == "plain")     return DECK_RARITY_COMMON; // synonym
    if (s == "rare")      return DECK_RARITY_RARE;
    if (s == "ornate")    return DECK_RARITY_RARE; // synonym
    if (s == "legendary") return DECK_RARITY_LEGENDARY;
    // FIXME: log an error here.
    return DECK_RARITY_RANDOM;
}

static misc_item_type _deck_type_string_to_subtype(const string& s)
{
    if (s == "escape")      return MISC_DECK_OF_ESCAPE;
    if (s == "destruction") return MISC_DECK_OF_DESTRUCTION;
    if (s == "summoning")   return MISC_DECK_OF_SUMMONING;
    if (s == "summonings")  return MISC_DECK_OF_SUMMONING;
    if (s == "wonders")     return MISC_DECK_OF_WONDERS;
    if (s == "punishment")  return MISC_DECK_OF_PUNISHMENT;
    if (s == "war")         return MISC_DECK_OF_WAR;
    if (s == "changes")     return MISC_DECK_OF_CHANGES;
    if (s == "defence")     return MISC_DECK_OF_DEFENCE;
    // FIXME: log an error here.
    return NUM_MISCELLANY;
}

static misc_item_type _random_deck_subtype()
{
    item_def dummy;
    dummy.base_type = OBJ_MISCELLANY;
    while (true)
    {
        dummy.sub_type = random2(NUM_MISCELLANY);

        if (!is_deck(dummy))
            continue;

        if (dummy.sub_type == MISC_DECK_OF_PUNISHMENT)
            continue;

#if TAG_MAJOR_VERSION == 34
        if (dummy.sub_type == MISC_DECK_OF_DUNGEONS)
            continue;
#endif

        if ((dummy.sub_type == MISC_DECK_OF_ESCAPE
             || dummy.sub_type == MISC_DECK_OF_DESTRUCTION
             || dummy.sub_type == MISC_DECK_OF_SUMMONING
             || dummy.sub_type == MISC_DECK_OF_WONDERS)
            && !one_chance_in(5))
        {
            continue;
        }

        return static_cast<misc_item_type>(dummy.sub_type);
    }
}

void item_list::build_deck_spec(string s, item_spec* spec)
{
    spec->base_type = OBJ_MISCELLANY;
    string word = _get_and_discard_word(&s);

    // The deck description can start with either "[rarity] deck..." or
    // just "deck".
    if (word != "deck")
    {
        spec->ego = _rarity_string_to_rarity(word);
        word = _get_and_discard_word(&s);
    }
    else
        spec->ego = DECK_RARITY_RANDOM;

    // Error checking.
    if (word != "deck")
    {
        error = make_stringf("Bad spec: %s", s.c_str());
        return;
    }

    word = _get_and_discard_word(&s);
    if (word == "of")
    {
        string sub_type_str = _get_and_discard_word(&s);
        int sub_type =
            _deck_type_string_to_subtype(sub_type_str);

        if (sub_type == NUM_MISCELLANY)
        {
            error = make_stringf("Bad deck type: %s", sub_type_str.c_str());
            return;
        }

        spec->sub_type = sub_type;
    }
    else
        spec->sub_type = _random_deck_subtype();
}

item_spec item_list::parse_single_spec(string s)
{
    item_spec result;

    // If there's a colon, this must be a generation weight.
    int weight = find_weight(s);
    if (weight != TAG_UNFOUND)
    {
        result.genweight = weight;
        if (result.genweight <= 0)
        {
            error = make_stringf("Bad item generation weight: '%d'",
                                 result.genweight);
            return result;
        }
    }

    const int qty = strip_number_tag(s, "q:");
    if (qty != TAG_UNFOUND)
        result.qty = qty;

    const int fresh = strip_number_tag(s, "fresh:");
    if (fresh != TAG_UNFOUND)
        result.item_special = fresh;
    const int special = strip_number_tag(s, "special:");
    if (special != TAG_UNFOUND)
        result.item_special = special;

    // When placing corpses, use place:Elf:$ to choose monsters
    // appropriate for that level, as an example.
    const string place = strip_tag_prefix(s, "place:");
    if (!place.empty())
    {
        try
        {
            result.place = level_id::parse_level_id(place);
        }
        catch (const string &err)
        {
            error = err;
            return result;
        }
    }

    const string acquirement_source = strip_tag_prefix(s, "acquire:");
    if (!acquirement_source.empty() || strip_tag(s, "acquire"))
    {
        if (!acquirement_source.empty())
        {
            result.acquirement_source =
                parse_acquirement_source(acquirement_source);
        }
        // If requesting acquirement, must specify item base type or
        // "any".
        result.level = ISPEC_ACQUIREMENT;
        if (s == "any")
            result.base_type = OBJ_RANDOM;
        else
            parse_random_by_class(s, result);
        return result;
    }

    string ego_str  = strip_tag_prefix(s, "ego:");

    string id_str = strip_tag_prefix(s, "ident:");
    if (id_str == "all")
        result.props["ident"].get_int() = ISFLAG_IDENT_MASK;
    else if (!id_str.empty())
    {
        vector<string> ids = split_string("|", id_str);
        int id = 0;
        for (vector<string>::const_iterator is = ids.begin();
             is != ids.end(); ++is)
        {
            if (*is == "curse")
                id |= ISFLAG_KNOW_CURSE;
            else if (*is == "type")
                id |= ISFLAG_KNOW_TYPE;
            else if (*is == "pluses")
                id |= ISFLAG_KNOW_PLUSES;
            else if (*is == "properties")
                id |= ISFLAG_KNOW_PROPERTIES;
            else
            {
                error = make_stringf("Bad identify status: %s", id_str.c_str());
                return result;
            }
        }
        result.props["ident"].get_int() = id;
    }

    string unrand_str = strip_tag_prefix(s, "unrand:");

    if (strip_tag(s, "good_item"))
        result.level = MAKE_GOOD_ITEM;
    else
    {
        int number = strip_number_tag(s, "level:");
        if (number != TAG_UNFOUND)
        {
            if (number <= 0 && number != ISPEC_GOOD && number != ISPEC_SUPERB
                && number != ISPEC_DAMAGED && number != ISPEC_BAD)
            {
                error = make_stringf("Bad item level: %d", number);
                return result;
            }

            result.level = number;
        }
    }

    if (strip_tag(s, "mundane"))
    {
        result.level = ISPEC_MUNDANE;
        result.ego   = -1;
        if (strip_tag(s, "cursed"))
            result.props["cursed"] = bool(true);
    }
    if (strip_tag(s, "damaged"))
        result.level = ISPEC_DAMAGED;
    if (strip_tag(s, "cursed"))
        result.level = ISPEC_BAD; // damaged + cursed, actually
    if (strip_tag(s, "randart"))
        result.level = ISPEC_RANDART;
    if (strip_tag(s, "not_cursed"))
        result.props["uncursed"] = bool(true);
    if (strip_tag(s, "useful"))
        result.props["useful"] = bool(true);
    if (strip_tag(s, "unobtainable"))
        result.props["unobtainable"] = true;

    const int mimic = strip_number_tag(s, "mimic:");
    if (mimic != TAG_UNFOUND)
        result.props["mimic"] = mimic;
    if (strip_tag(s, "mimic"))
        result.props["mimic"] = 1;
    if (strip_tag(s, "no_mimic"))
        result.props["no_mimic"] = true;

    if (strip_tag(s, "no_pickup"))
        result.props["no_pickup"] = true;

    const short charges = strip_number_tag(s, "charges:");
    if (charges >= 0)
        result.props["charges"].get_int() = charges;

    const int plus = strip_number_tag(s, "plus:");
    if (plus != TAG_UNFOUND)
        result.props["plus"].get_int() = plus;
    const int plus2 = strip_number_tag(s, "plus2:");
    if (plus2 != TAG_UNFOUND)
        result.props["plus2"].get_int() = plus2;

    if (strip_tag(s, "no_uniq"))
        result.allow_uniques = 0;
    if (strip_tag(s, "allow_uniq"))
        result.allow_uniques = 1;
    else
    {
        int uniq = strip_number_tag(s, "uniq:");
        if (uniq != TAG_UNFOUND)
        {
            if (uniq <= 0)
            {
                error = make_stringf("Bad uniq level: %d", uniq);
                return result;
            }
            result.allow_uniques = uniq;
        }
    }

    // XXX: This is nice-ish now, but could probably do with being improved.
    if (strip_tag(s, "randbook"))
    {
        result.props["make_book_theme_randart"] = true;
        // make_book_theme_randart requires the following properties:
        // disc: <first discipline>, disc2: <optional second discipline>
        // numspells: <total number of spells>, slevels: <maximum levels>
        // spell: <include this spell>, owner:<name of owner>
        // None of these are required, but if you don't intend on using any
        // of them, use "any fixed theme book" instead.
        short disc1 = 0;
        short disc2 = 0;

        string st_disc1 = strip_tag_prefix(s, "disc:");
        if (!st_disc1.empty())
        {
            disc1 = school_by_name(st_disc1);
            if (disc1 == SPTYP_NONE)
            {
                error = make_stringf("Bad spell school: %s", st_disc1.c_str());
                return result;
            }
        }

        string st_disc2 = strip_tag_prefix(s, "disc2:");
        if (!st_disc2.empty())
        {
            disc2 = school_by_name(st_disc2);
            if (disc2 == SPTYP_NONE)
            {
                error = make_stringf("Bad spell school: %s", st_disc2.c_str());
                return result;
            }
        }

        if (disc1 != 0 && disc2 != 0)
        {
            if (disciplines_conflict(disc1, disc2))
            {
                error = make_stringf("Bad combination of spell schools: %s & %s.",
                                    st_disc1.c_str(), st_disc2.c_str());
                return result;
            }
        }

        if (disc1 == 0 && disc2 != 0)
        {
            // Don't fail, just quietly swap. Any errors in disc1's syntax will
            // have been caught above, anyway.
            disc1 = disc2;
            disc2 = 0;
        }

        short num_spells = strip_number_tag(s, "numspells:");
        if (num_spells == TAG_UNFOUND)
            num_spells = -1;
        else if (num_spells <= 0 || num_spells > SPELLBOOK_SIZE)
        {
            error = make_stringf("Bad spellbook size: %d", num_spells);
            return result;
        }

        short slevels = strip_number_tag(s, "slevels:");
        if (slevels == TAG_UNFOUND)
            slevels = -1;
        else if (slevels == 0)
        {
            error = make_stringf("Bad slevels: %d.", slevels);
            return result;
        }

        const string title = replace_all_of(strip_tag_prefix(s, "title:"),
                                            "_", " ");

        const string spells = strip_tag_prefix(s, "spells:");

        vector<string> spell_list = split_string("|", spells);
        CrawlVector &incl_spells
            = result.props["randbook_spells"].new_vector(SV_INT);

        for (unsigned int i = 0; i < spell_list.size(); ++i)
        {
            string spell_name = replace_all_of(spell_list[i], "_", " ");
            spell_type spell = spell_by_name(spell_name);
            if (spell == SPELL_NO_SPELL)
            {
                error = make_stringf("Bad spell: %s", spell_list[i].c_str());
                return result;
            }
            incl_spells.push_back(spell);
        }

        const string owner = replace_all_of(strip_tag_prefix(s, "owner:"),
                                            "_", " ");
        result.props["randbook_disc1"] = disc1;
        result.props["randbook_disc2"] = disc2;
        result.props["randbook_num_spells"] = num_spells;
        result.props["randbook_slevels"] = slevels;
        result.props["randbook_title"] = title;
        result.props["randbook_owner"] = owner;

        result.base_type = OBJ_BOOKS;
        // This is changed in make_book_theme_randart.
        result.sub_type = BOOK_MINOR_MAGIC;
        result.plus = -1;

        return result;
    }

    if (s.find("deck") != string::npos)
    {
        build_deck_spec(s, &result);
        return result;
    }

    string tile = strip_tag_prefix(s, "tile:");
    if (!tile.empty())
    {
        tileidx_t index;
        if (!tile_main_index(tile.c_str(), &index))
        {
            error = make_stringf("bad tile name: \"%s\".", tile.c_str());
            return result;
        }
        result.props["item_tile_name"].get_string() = tile;
    }

    tile = strip_tag_prefix(s, "wtile:");
    if (!tile.empty())
    {
        tileidx_t index;
        if (!tile_player_index(tile.c_str(), &index))
        {
            error = make_stringf("bad tile name: \"%s\".", tile.c_str());
            return result;
        }
        result.props["worn_tile_name"].get_string() = tile;
    }

    // Clean up after any tag brain damage.
    trim_string(s);

    if (!ego_str.empty())
        error = "Can't set an ego for random items.";

    // Completely random?
    if (s == "random" || s == "any" || s == "%")
        return result;

    if (s == "*" || s == "star_item")
    {
        result.level = ISPEC_GOOD;
        return result;
    }
    else if (s == "|" || s == "superb_item")
    {
        result.level = ISPEC_SUPERB;
        return result;
    }
    else if (s == "$" || s == "gold")
    {
        if (!ego_str.empty())
            error = "Can't set an ego for gold.";

        result.base_type = OBJ_GOLD;
        result.sub_type  = OBJ_RANDOM;
        return result;
    }

    if (s == "nothing")
    {
        error.clear();
        result.base_type = OBJ_UNASSIGNED;
        return result;
    }

    error.clear();

    // Look for corpses, chunks, skeletons:
    if (ends_with(s, "corpse") || ends_with(s, "chunk")
        || ends_with(s, "skeleton"))
    {
        return parse_corpse_spec(result, s);
    }

    // Check for "any objclass"
    if (s.find("any ") == 0)
        parse_random_by_class(s.substr(4), result);
    else if (s.find("random ") == 0)
        parse_random_by_class(s.substr(7), result);
    // Check for actual item names.
    else
        parse_raw_name(s, result);

    if (!error.empty())
        return result;

    if (!unrand_str.empty())
    {
        result.ego = get_unrandart_num(unrand_str.c_str());
        if (result.ego == SPWPN_NORMAL)
        {
            error = make_stringf("Unknown unrand art: %s", unrand_str.c_str());
            return result;
        }
        result.ego = -result.ego;
        return result;
    }

    if (ego_str.empty())
        return result;

    if (result.base_type != OBJ_WEAPONS
        && result.base_type != OBJ_MISSILES
        && result.base_type != OBJ_ARMOUR)
    {
        error = "An ego can only be applied to a weapon, missile or "
            "armour.";
        return result;
    }

    if (ego_str == "none")
    {
        result.ego = -1;
        return result;
    }

    const int ego = _str_to_ego(result, ego_str);

    if (ego == 0)
    {
        error = make_stringf("No such ego as: %s", ego_str.c_str());
        return result;
    }
    else if (ego == -1)
    {
        error = make_stringf("Ego '%s' is invalid for item '%s'.",
                             ego_str.c_str(), s.c_str());
        return result;
    }
    else if (result.sub_type == OBJ_RANDOM)
    {
        // it will be assigned among appropriate ones later
    }
    else if (result.base_type == OBJ_WEAPONS
                && !is_weapon_brand_ok(result.sub_type, ego, false)
             || result.base_type == OBJ_ARMOUR
                && !is_armour_brand_ok(result.sub_type, ego, false)
             || result.base_type == OBJ_MISSILES
                && !is_missile_brand_ok(result.sub_type, ego, false))
    {
        error = make_stringf("Ego '%s' is incompatible with item '%s'.",
                             ego_str.c_str(), s.c_str());
        return result;
    }
    result.ego = ego;

    return result;
}

void item_list::parse_random_by_class(string c, item_spec &spec)
{
    trim_string(c);
    if (c == "?" || c.empty())
    {
        error = make_stringf("Bad item class: '%s'", c.c_str());
        return;
    }

    for (int type = OBJ_WEAPONS; type < NUM_OBJECT_CLASSES; ++type)
    {
        if (c == item_class_name(type, true))
        {
            spec.base_type = static_cast<object_class_type>(type);
            return;
        }
    }

    // Random manual?
    if (c == "manual")
    {
        spec.base_type = OBJ_BOOKS;
        spec.sub_type  = BOOK_MANUAL;
        spec.plus      = -1;
        return;
    }
    else if (c == "fixed theme book")
    {
        spec.base_type = OBJ_BOOKS;
        spec.sub_type  = BOOK_RANDART_THEME;
        spec.plus      = -1;
        return;
    }
    else if (c == "fixed level book")
    {
        spec.base_type = OBJ_BOOKS;
        spec.sub_type  = BOOK_RANDART_LEVEL;
        spec.plus      = -1;
        return;
    }
    else if (c == "ring")
    {
        spec.base_type = OBJ_JEWELLERY;
        spec.sub_type = NUM_RINGS;
        return;
    }
    else if (c == "amulet")
    {
        spec.base_type = OBJ_JEWELLERY;
        spec.sub_type = NUM_JEWELLERY;
        return;
    }

    error = make_stringf("Bad item class: '%s'", c.c_str());
}

void item_list::parse_raw_name(string name, item_spec &spec)
{
    trim_string(name);
    if (name.empty())
    {
        error = make_stringf("Bad item name: '%s'", name.c_str());
        return ;
    }

    item_kind parsed = item_kind_by_name(name);
    if (parsed.base_type != OBJ_UNASSIGNED)
    {
        spec.base_type = parsed.base_type;
        spec.sub_type  = parsed.sub_type;
        spec.plus      = parsed.plus;
        spec.plus2     = parsed.plus2;
        return;
    }

    error = make_stringf("Bad item name: '%s'", name.c_str());
}

item_list::item_spec_slot item_list::parse_item_spec(string spec)
{
    // lowercase(spec);

    item_spec_slot list;

    list.fix_slot = strip_tag(spec, "fix_slot");
    vector<string> specifiers = split_string("/", spec);

    for (unsigned i = 0; i < specifiers.size() && error.empty(); ++i)
        list.ilist.push_back(parse_single_spec(specifiers[i]));

    return list;
}

/////////////////////////////////////////////////////////////////////////
// subst_spec

subst_spec::subst_spec(string _k, bool _f, const glyph_replacements_t &g)
    : key(_k), count(-1), fix(_f), frozen_value(0), repl(g)
{
}

subst_spec::subst_spec(int _count, bool dofix, const glyph_replacements_t &g)
    : key(""), count(_count), fix(dofix), frozen_value(0), repl(g)
{
}

int subst_spec::value()
{
    if (frozen_value)
        return frozen_value;

    int cumulative = 0;
    int chosen = 0;
    for (int i = 0, size = repl.size(); i < size; ++i)
        if (x_chance_in_y(repl[i].second, cumulative += repl[i].second))
            chosen = repl[i].first;

    if (fix)
        frozen_value = chosen;

    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// nsubst_spec

nsubst_spec::nsubst_spec(string _key, const vector<subst_spec> &_specs)
    : key(_key), specs(_specs)
{
}

//////////////////////////////////////////////////////////////////////////
// colour_spec

int colour_spec::get_colour()
{
    if (fixed_colour != BLACK)
        return fixed_colour;

    int chosen = BLACK;
    int cweight = 0;
    for (int i = 0, size = colours.size(); i < size; ++i)
        if (x_chance_in_y(colours[i].second, cweight += colours[i].second))
            chosen = colours[i].first;
    if (fix)
        fixed_colour = chosen;
    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// fprop_spec

feature_property_type fprop_spec::get_property()
{
    if (fixed_prop != FPROP_NONE)
        return fixed_prop;

    feature_property_type chosen = FPROP_NONE;
    int cweight = 0;
    for (int i = 0, size = fprops.size(); i < size; ++i)
        if (x_chance_in_y(fprops[i].second, cweight += fprops[i].second))
            chosen = fprops[i].first;
    if (fix)
        fixed_prop = chosen;
    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// fheight_spec

int fheight_spec::get_height()
{
    if (fixed_height != INVALID_HEIGHT)
        return fixed_height;

    int chosen = INVALID_HEIGHT;
    int cweight = 0;
    for (int i = 0, size = fheights.size(); i < size; ++i)
        if (x_chance_in_y(fheights[i].second, cweight += fheights[i].second))
            chosen = fheights[i].first;
    if (fix)
        fixed_height = chosen;
    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// string_spec

string string_spec::get_property()
{
    if (!fixed_str.empty())
        return fixed_str;

    string chosen = "";
    int cweight = 0;
    for (int i = 0, size = strlist.size(); i < size; ++i)
        if (x_chance_in_y(strlist[i].second, cweight += strlist[i].second))
            chosen = strlist[i].first;
    if (fix)
        fixed_str = chosen;
    return chosen;
}

//////////////////////////////////////////////////////////////////////////
// map_marker_spec

string map_marker_spec::apply_transform(map_lines &map)
{
    vector<coord_def> positions = map.find_glyph(key);

    // Markers with no key are not an error.
    if (positions.empty())
        return "";

    for (int i = 0, size = positions.size(); i < size; ++i)
    {
        try
        {
            map_marker *mark = create_marker();
            if (!mark)
            {
                return make_stringf("Unable to parse marker from %s",
                                    marker.c_str());
            }
            mark->pos = positions[i];
            map.add_marker(mark);
        }
        catch (const string &err)
        {
            return err;
        }
    }
    return "";
}

map_marker *map_marker_spec::create_marker()
{
    return lua_fn.get()
        ? new map_lua_marker(*lua_fn.get())
        : map_marker::parse_marker(marker);
}

//////////////////////////////////////////////////////////////////////////
// map_flags
map_flags::map_flags()
    : flags_set(0), flags_unset(0)
{
}

void map_flags::clear()
{
    flags_set = flags_unset = 0;
}

typedef map<string, unsigned long> flag_map;

map_flags map_flags::parse(const string flag_list[],
                           const string &s) throw(string)
{
    map_flags mf;

    const vector<string> segs = split_string("/", s);

    flag_map flag_vals;
    for (int i = 0; !flag_list[i].empty(); i++)
        flag_vals[flag_list[i]] = 1 << i;

    for (int i = 0, size = segs.size(); i < size; i++)
    {
        string flag   = segs[i];
        bool   negate = false;

        if (flag[0] == '!')
        {
            flag   = flag.substr(1);
            negate = true;
        }

        flag_map::const_iterator val = flag_vals.find(flag);
        if (val == flag_vals.end())
            throw make_stringf("Unknown flag: '%s'", flag.c_str());

        if (negate)
            mf.flags_unset |= val->second;
        else
            mf.flags_set |= val->second;
    }

    return mf;
}

//////////////////////////////////////////////////////////////////////////
// keyed_mapspec

keyed_mapspec::keyed_mapspec()
    :  key_glyph(-1), feat(), item(), mons()
{
}

string keyed_mapspec::set_feat(const string &s, bool fix)
{
    err.clear();
    parse_features(s);
    feat.fix_slot = fix;

    // Fix this feature.
    if (fix)
        get_feat();

    return err;
}

void keyed_mapspec::copy_feat(const keyed_mapspec &spec)
{
    feat = spec.feat;
}

void keyed_mapspec::parse_features(const string &s)
{
    feat.feats.clear();
    vector<string> specs = split_string("/", s);
    for (int i = 0, size = specs.size(); i < size; ++i)
    {
        const string &spec = specs[i];

        feature_spec_list feats = parse_feature(spec);
        if (!err.empty())
            return;
        feat.feats.insert(feat.feats.end(),
                           feats.begin(),
                           feats.end());
    }
}

/**
 * Convert a trap string into a trap_spec.
 *
 * This function converts an incoming trap specification string from a vault
 * into a trap_spec.
 *
 * @param s       The string to be parsed.
 * @param weight  The weight of this string.
 * @return        A feature_spec with the contained, parsed trap_spec stored via
 *                unique_ptr as feature_spec->trap.
**/
feature_spec keyed_mapspec::parse_trap(string s, int weight)
{
    strip_tag(s, "trap");
    const bool known = strip_tag(s, "known");

    trim_string(s);
    lowercase(s);

    const int trap = str_to_trap(s);
    if (trap == -1)
        err = make_stringf("bad trap name: '%s'", s.c_str());

    feature_spec fspec(known ? 1 : -1, weight);
    fspec.trap.reset(new trap_spec(static_cast<trap_type>(trap)));
    return fspec;
}

/**
 * Convert a shop string into a shop_spec.
 *
 * This function converts an incoming shop specification string from a vault
 * into a shop_spec.
 *
 * @param s        The string to be parsed.
 * @param weight   The weight of this string.
 * @param mimic    What kind of mimic (if any) to set for this shop.
 * @param no_mimic Whether to prohibit mimics altogether for this shop.
 * @return         A feature_spec with the contained, parsed shop_spec stored
 *                 via unique_ptr as feature_spec->shop.
**/
feature_spec keyed_mapspec::parse_shop(string s, int weight, int mimic,
                                       bool no_mimic)
{
    string orig(s);

    strip_tag(s, "shop");
    trim_string(s);

    bool use_all = strip_tag(s, "use_all");

    string shop_name = replace_all_of(strip_tag_prefix(s, "name:"), "_", " ");
    string shop_type_name = replace_all_of(strip_tag_prefix(s, "type:"),
                                           "_", " ");
    string shop_suffix_name = replace_all_of(strip_tag_prefix(s, "suffix:"),
                                             "_", " ");

    int num_items = min(20, strip_number_tag(s, "count:"));
    if (num_items == TAG_UNFOUND)
        num_items = -1;

    int greed = strip_number_tag(s, "greed:");
    if (greed == TAG_UNFOUND)
        greed = -1;

    vector<string> parts = split_string(";", s);
    string main_part = parts[0];

    const int shop = str_to_shoptype(main_part);
    if (shop == -1)
        err = make_stringf("bad shop type: '%s'", s.c_str());

    if (parts.size() > 2)
        err = make_stringf("too many semi-colons for '%s' spec", orig.c_str());

    item_list items;
    if (err.empty() && parts.size() == 2)
    {
        string item_list = parts[1];
        vector<string> str_items = split_string("|", item_list);
        for (int i = 0, sz = str_items.size(); i < sz; ++i)
        {
            err = items.add_item(str_items[i]);
            if (!err.empty())
                break;
        }
    }

    feature_spec fspec(-1, weight, mimic, no_mimic);
    fspec.shop.reset(new shop_spec(static_cast<shop_type>(shop), shop_name,
                                   shop_type_name, shop_suffix_name, greed,
                                   num_items, use_all));
    fspec.shop->items = items;
    return fspec;
}

feature_spec_list keyed_mapspec::parse_feature(const string &str)
{
    string s = str;
    int weight = find_weight(s);
    if (weight == TAG_UNFOUND || weight <= 0)
        weight = 10;

    int mimic = strip_number_tag(s, "mimic:");
    if (mimic == TAG_UNFOUND && strip_tag(s, "mimic"))
        mimic = 1;
    const bool no_mimic = strip_tag(s, "no_mimic");

    trim_string(s);

    feature_spec_list list;
    if (s.length() == 1)
    {
        feature_spec fsp(-1, weight, mimic, no_mimic);
        fsp.glyph = s[0];
        list.push_back(fsp);
        return list;
    }

    if (s.find("trap") != string::npos || s == "web")
    {
        list.push_back(parse_trap(s, weight));
        return list;
    }

    if (s.find("shop") != string::npos && s != "abandoned_shop"
        || s.find("store") != string::npos)
    {
        list.push_back(parse_shop(s, weight, mimic, no_mimic));
        return list;
    }

    const dungeon_feature_type ftype = dungeon_feature_by_name(s);

    if (ftype == DNGN_UNSEEN)
        err = make_stringf("no features matching \"%s\"", str.c_str());
    else
        list.push_back(feature_spec(ftype, weight, mimic, no_mimic));

    return list;
}

string keyed_mapspec::set_mons(const string &s, bool fix)
{
    err.clear();
    mons.clear();

    vector<string> segments = split_string(",", s);
    for (int i = 0, size = segments.size(); i < size; ++i)
    {
        const string error = mons.add_mons(segments[i], fix);
        if (!error.empty())
            return error;
    }

    return "";
}

string keyed_mapspec::set_item(const string &s, bool fix)
{
    err.clear();
    item.clear();

    vector<string> segs = split_string(",", s);

    for (int i = 0, size = segs.size(); i < size; ++i)
    {
        err = item.add_item(segs[i], fix);
        if (!err.empty())
            return err;
    }

    return err;
}

string keyed_mapspec::set_mask(const string &s, bool garbage)
{
    UNUSED(garbage);

    err.clear();

    try
    {
        static string flag_list[] =
            {"vault", "no_item_gen", "no_monster_gen", "no_pool_fixup",
             "UNUSED",
             "no_wall_fixup", "opaque", "no_trap_gen", ""};
        map_mask = map_flags::parse(flag_list, s);
    }
    catch (const string &error)
    {
        err = error;
        return err;
    }

    return err;
}

void keyed_mapspec::copy_mons(const keyed_mapspec &spec)
{
    mons = spec.mons;
}

void keyed_mapspec::copy_item(const keyed_mapspec &spec)
{
    item = spec.item;
}

void keyed_mapspec::copy_mask(const keyed_mapspec &spec)
{
    map_mask = spec.map_mask;
}

feature_spec keyed_mapspec::get_feat()
{
    return feat.get_feat('.');
}

mons_list &keyed_mapspec::get_monsters()
{
    return mons;
}

item_list &keyed_mapspec::get_items()
{
    return item;
}

map_flags &keyed_mapspec::get_mask()
{
    return map_mask;
}

bool keyed_mapspec::replaces_glyph()
{
    return !(mons.empty() && item.empty() && feat.feats.empty());
}

//////////////////////////////////////////////////////////////////////////
// feature_spec and feature_slot

feature_spec::feature_spec()
{
    genweight = 0;
    feat = 0;
    glyph = -1;
    shop.reset(NULL);
    trap.reset(NULL);
    mimic = 0;
    no_mimic = false;
}

feature_spec::feature_spec(int f, int wt, int _mimic, bool _no_mimic)
{
    genweight = wt;
    feat = f;
    glyph = -1;
    shop.reset(NULL);
    trap.reset(NULL);
    mimic = _mimic;
    no_mimic = _no_mimic;
}

feature_spec::feature_spec(const feature_spec &other)
{
    init_with(other);
}

feature_spec& feature_spec::operator = (const feature_spec& other)
{
    if (this != &other)
        init_with(other);
    return *this;
}

void feature_spec::init_with(const feature_spec& other)
{
    genweight = other.genweight;
    feat = other.feat;
    glyph = other.glyph;
    mimic = other.mimic;
    no_mimic = other.no_mimic;

    if (other.trap.get())
        trap.reset(new trap_spec(*other.trap));
    else
        trap.reset(NULL);

    if (other.shop.get())
        shop.reset(new shop_spec(*other.shop));
    else
        shop.reset(NULL);
}

feature_slot::feature_slot() : feats(), fix_slot(false)
{
}

feature_spec feature_slot::get_feat(int def_glyph)
{
    int tweight = 0;
    feature_spec chosen_feat = feature_spec(DNGN_FLOOR);

    if (def_glyph != -1)
    {
        chosen_feat.feat = -1;
        chosen_feat.glyph = def_glyph;
    }

    for (int i = 0, size = feats.size(); i < size; ++i)
    {
        const feature_spec &feat = feats[i];
        if (x_chance_in_y(feat.genweight, tweight += feat.genweight))
            chosen_feat = feat;
    }

    if (fix_slot)
    {
        feats.clear();
        feats.push_back(chosen_feat);
    }
    return chosen_feat;
}